StringTable

pub const StringTable = struct

File

Code

pub const StringTable = struct {
    /// Blocks are written to the .res file in order depending on when the first string
    /// was added to the block (i.e. `STRINGTABLE { 16 "b" 0 "a" }` would then get written
    /// with block ID 2 (the one with "b") first and block ID 1 (the one with "a") second).
    /// Using an ArrayHashMap here gives us this property for free.
    blocks: std.array_hash_map.Auto(u16, Block) = .empty,

    pub const Block = struct {
        strings: std.ArrayList(Token) = .empty,
        set_indexes: std.bit_set.Integer(16) = .{ .mask = 0 },
        memory_flags: MemoryFlags = MemoryFlags.defaults(res.RT.STRING),
        characteristics: u32,
        version: u32,

        /// Returns the index to insert the string into the `strings` list.
        /// Returns null if the string should be appended.
        fn getInsertionIndex(self: *Block, index: u8) ?u8 {
            std.debug.assert(!self.set_indexes.isSet(index));

            const first_set = self.set_indexes.findFirstSet() orelse return null;
            if (first_set > index) return 0;

            const last_set = 15 - @clz(self.set_indexes.mask);
            if (index > last_set) return null;

            var bit = first_set + 1;
            var insertion_index: u8 = 1;
            while (bit != index) : (bit += 1) {
                if (self.set_indexes.isSet(bit)) insertion_index += 1;
            }
            return insertion_index;
        }

        fn getTokenIndex(self: *Block, string_index: u8) ?u8 {
            const count = self.strings.items.len;
            if (count == 0) return null;
            if (count == 1) return 0;

            const first_set = self.set_indexes.findFirstSet() orelse unreachable;
            if (first_set == string_index) return 0;
            const last_set = 15 - @clz(self.set_indexes.mask);
            if (last_set == string_index) return @intCast(count - 1);

            if (first_set == last_set) return null;

            var bit = first_set + 1;
            var token_index: u8 = 1;
            while (bit < last_set) : (bit += 1) {
                if (!self.set_indexes.isSet(bit)) continue;
                if (bit == string_index) return token_index;
                token_index += 1;
            }
            return null;
        }

        fn dump(self: *Block) void {
            var bit_it = self.set_indexes.iterator(.{});
            var string_index: usize = 0;
            while (bit_it.next()) |bit_index| {
                const token = self.strings.items[string_index];
                std.debug.print("{}: [{}] {any}\n", .{ bit_index, string_index, token });
                string_index += 1;
            }
        }

        pub fn applyAttributes(self: *Block, string_table: *Node.StringTable, source: []const u8, code_page_lookup: *const CodePageLookup) void {
            Compiler.applyToMemoryFlags(&self.memory_flags, string_table.common_resource_attributes, source);
            var dummy_language: res.Language = undefined;
            Compiler.applyToOptionalStatements(&dummy_language, &self.version, &self.characteristics, string_table.optional_statements, source, code_page_lookup);
        }

        fn trimToDoubleNUL(comptime T: type, str: []const T) []const T {
            var last_was_null = false;
            for (str, 0..) |c, i| {
                if (c == 0) {
                    if (last_was_null) return str[0 .. i - 1];
                    last_was_null = true;
                } else {
                    last_was_null = false;
                }
            }
            return str;
        }

        test "trimToDoubleNUL" {
            try std.testing.expectEqualStrings("a\x00b", trimToDoubleNUL(u8, "a\x00b"));
            try std.testing.expectEqualStrings("a", trimToDoubleNUL(u8, "a\x00\x00b"));
        }

        pub fn writeResData(self: *Block, compiler: *Compiler, language: res.Language, block_id: u16, writer: *std.Io.Writer) !void {
            var data_buffer: std.Io.Writer.Allocating = .init(compiler.allocator);
            defer data_buffer.deinit();
            const data_writer = &data_buffer.writer;

            var i: u8 = 0;
            var string_i: u8 = 0;
            while (true) : (i += 1) {
                if (!self.set_indexes.isSet(i)) {
                    try data_writer.writeInt(u16, 0, .little);
                    if (i == 15) break else continue;
                }

                const string_token = self.strings.items[string_i];
                const slice = string_token.slice(compiler.source);
                const column = string_token.calculateColumn(compiler.source, 8, null);
                const code_page = compiler.input_code_pages.getForToken(string_token);
                const bytes = SourceBytes{ .slice = slice, .code_page = code_page };
                const utf16_string = try literals.parseQuotedStringAsWideString(compiler.allocator, bytes, .{
                    .start_column = column,
                    .diagnostics = compiler.errContext(string_token),
                    .output_code_page = compiler.output_code_pages.getForToken(string_token),
                });
                defer compiler.allocator.free(utf16_string);

                const trimmed_string = trim: {
                    // Two NUL characters in a row act as a terminator
                    // Note: This is only the case for STRINGTABLE strings
                    const trimmed = trimToDoubleNUL(u16, utf16_string);
                    // We also want to trim any trailing NUL characters
                    break :trim std.mem.trimEnd(u16, trimmed, &[_]u16{0});
                };

                // String literals are limited to maxInt(u15) codepoints, so these UTF-16 encoded
                // strings are limited to maxInt(u15) * 2 = 65,534 code units (since 2 is the
                // maximum number of UTF-16 code units per codepoint).
                // This leaves room for exactly one NUL terminator.
                var string_len_in_utf16_code_units: u16 = @intCast(trimmed_string.len);
                // If the option is set, then a NUL terminator is added unconditionally.
                // We already trimmed any trailing NULs, so we know it will be a new addition to the string.
                if (compiler.null_terminate_string_table_strings) string_len_in_utf16_code_units += 1;
                try data_writer.writeInt(u16, string_len_in_utf16_code_units, .little);
                try data_writer.writeAll(std.mem.sliceAsBytes(trimmed_string));
                if (compiler.null_terminate_string_table_strings) {
                    try data_writer.writeInt(u16, 0, .little);
                }

                if (i == 15) break;
                string_i += 1;
            }

            // This intCast will never be able to fail due to the length constraints on string literals.
            //
            // - STRINGTABLE resource definitions can can only provide one string literal per index.
            // - STRINGTABLE strings are limited to maxInt(u16) UTF-16 code units (see 'string_len_in_utf16_code_units'
            //   above), which means that the maximum number of bytes per string literal is
            //   2 * maxInt(u16) = 131,070 (since there are 2 bytes per UTF-16 code unit).
            // - Each Block/RT_STRING resource includes exactly 16 strings and each have a 2 byte
            //   length field, so the maximum number of total bytes in a RT_STRING resource's data is
            //   16 * (131,070 + 2) = 2,097,152 which is well within the u32 max.
            //
            // Note: The string literal maximum length is enforced by the lexer.
            const data_size: u32 = @intCast(data_buffer.written().len);

            const header = Compiler.ResourceHeader{
                .name_value = .{ .ordinal = block_id },
                .type_value = .{ .ordinal = @backingInt(res.RT.STRING) },
                .memory_flags = self.memory_flags,
                .language = language,
                .version = self.version,
                .characteristics = self.characteristics,
                .data_size = data_size,
            };
            // The only variable parts of the header are name and type, which in this case
            // we fully control and know are numbers, so they have a fixed size.
            try header.writeAssertNoOverflow(writer);

            var data_fbs: std.Io.Reader = .fixed(data_buffer.written());
            try Compiler.writeResourceData(writer, &data_fbs, data_size);
        }
    };

    pub fn deinit(self: *StringTable, allocator: Allocator) void {
        var it = self.blocks.iterator();
        while (it.next()) |entry| {
            entry.value_ptr.strings.deinit(allocator);
        }
        self.blocks.deinit(allocator);
    }

    const SetError = error{StringAlreadyDefined} || Allocator.Error;

    pub fn set(
        self: *StringTable,
        allocator: Allocator,
        id: u16,
        string_token: Token,
        node: *Node,
        source: []const u8,
        code_page_lookup: *const CodePageLookup,
        version: u32,
        characteristics: u32,
    ) SetError!void {
        const block_id = (id / 16) + 1;
        const string_index: u8 = @intCast(id & 0xF);

        var get_or_put_result = try self.blocks.getOrPut(allocator, block_id);
        if (!get_or_put_result.found_existing) {
            get_or_put_result.value_ptr.* = Block{ .version = version, .characteristics = characteristics };
            get_or_put_result.value_ptr.applyAttributes(node.cast(.string_table).?, source, code_page_lookup);
        } else {
            if (get_or_put_result.value_ptr.set_indexes.isSet(string_index)) {
                return error.StringAlreadyDefined;
            }
        }

        var block = get_or_put_result.value_ptr;
        if (block.getInsertionIndex(string_index)) |insertion_index| {
            try block.strings.insert(allocator, insertion_index, string_token);
        } else {
            try block.strings.append(allocator, string_token);
        }
        block.set_indexes.set(string_index);
    }

    pub fn get(self: *StringTable, id: u16) ?Token {
        const block_id = (id / 16) + 1;
        const string_index: u8 = @intCast(id & 0xF);

        const block = self.blocks.getPtr(block_id) orelse return null;
        const token_index = block.getTokenIndex(string_index) orelse return null;
        return block.strings.items[token_index];
    }

    pub fn dump(self: *StringTable) !void {
        var it = self.iterator();
        while (it.next()) |entry| {
            std.debug.print("block: {}\n", .{entry.key_ptr.*});
            entry.value_ptr.dump();
        }
    }
}