Something went wrong. Try again.
Something went wrong. Try again.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189const std = @import("std");const assert = std.debug.assert;const Allocator = std.mem.Allocator;
// This whole file is based on the algorithm described here:// https://here-be-braces.com/fast-lookup-of-unicode-properties/
/// Creates a type that is able to generate a 3-level lookup table/// from a Unicode codepoint to a mapping of type Elem. The lookup table/// generally is expected to be codegen'd and then reloaded, although it/// can in theory be generated at runtime.////// Context must have two functions:/// - `get(Context, u21) Elem`: returns the mapping for a given codepoint/// - `eql(Context, Elem, Elem) bool`: returns true if two mappings are equal///pub fn Generator( comptime Elem: type, comptime Context: type,) type { return struct { const Self = @This();
const block_size = 256; const Block = [block_size]u16;
/// Mapping of a block to its index in the stage2 array. const BlockMap = std.HashMap( Block, u16, struct { pub fn hash(ctx: @This(), k: Block) u64 { _ = ctx; var hasher = std.hash.Wyhash.init(0); std.hash.autoHashStrat(&hasher, k, .DeepRecursive); return hasher.final(); }
pub fn eql(ctx: @This(), a: Block, b: Block) bool { _ = ctx; return std.mem.eql(u16, &a, &b); } }, std.hash_map.default_max_load_percentage, );
ctx: Context = undefined,
/// Generate the lookup tables. The arrays in the return value /// are owned by the caller and must be freed. pub fn generate(self: *const Self, alloc: Allocator) !Tables(Elem) { // Maps block => stage2 index var blocks_map = BlockMap.init(alloc); defer blocks_map.deinit();
// Our stages var stage1: std.ArrayList(u16) = .empty; var stage2: std.ArrayList(u16) = .empty; var stage3: std.ArrayList(Elem) = .empty; defer { stage1.deinit(alloc); stage2.deinit(alloc); stage3.deinit(alloc); }
var block: Block = undefined; var block_len: u16 = 0; for (0..std.math.maxInt(u21) + 1) |cp| { // Get our block value and find the matching result value // in our list of possible values in stage3. This way, each // possible mapping only gets one entry in stage3. const elem = try self.ctx.get(@as(u21, @intCast(cp))); const block_idx = block_idx: { for (stage3.items, 0..) |item, i| { if (self.ctx.eql(item, elem)) break :block_idx i; }
const idx = stage3.items.len; try stage3.append(alloc, elem); break :block_idx idx; };
// The block stores the mapping to the stage3 index block[block_len] = std.math.cast(u16, block_idx) orelse return error.BlockTooLarge; block_len += 1;
// If we still have space and we're not done with codepoints, // we keep building up the block. Conversely: we finalize this // block if we've filled it or are out of codepoints. if (block_len < block_size and cp != std.math.maxInt(u21)) continue; if (block_len < block_size) @memset(block[block_len..block_size], 0);
// Look for the stage2 index for this block. If it doesn't exist // we add it to stage2 and update the mapping. const gop = try blocks_map.getOrPut(block); if (!gop.found_existing) { gop.value_ptr.* = std.math.cast( u16, stage2.items.len, ) orelse return error.Stage2TooLarge; for (block[0..block_len]) |entry| try stage2.append(alloc, entry); }
// Map stage1 => stage2 and reset our block try stage1.append(alloc, gop.value_ptr.*); block_len = 0; }
// All of our lengths must fit in a u16 for this to work assert(stage1.items.len <= std.math.maxInt(u16)); assert(stage2.items.len <= std.math.maxInt(u16)); assert(stage3.items.len <= std.math.maxInt(u16));
const stage1_owned = try stage1.toOwnedSlice(alloc); errdefer alloc.free(stage1_owned); const stage2_owned = try stage2.toOwnedSlice(alloc); errdefer alloc.free(stage2_owned); const stage3_owned = try stage3.toOwnedSlice(alloc); errdefer alloc.free(stage3_owned);
return .{ .stage1 = stage1_owned, .stage2 = stage2_owned, .stage3 = stage3_owned, }; } };}
/// Creates a type that given a 3-level lookup table, can be used to/// look up a mapping for a given codepoint, encode it out to Zig, etc.pub fn Tables(comptime Elem: type) type { return struct { const Self = @This();
stage1: []const u16, stage2: []const u16, stage3: []const Elem,
/// Given a codepoint, returns the mapping for that codepoint. pub inline fn get(self: *const Self, cp: u21) Elem { const high = cp >> 8; const low = cp & 0xFF; return self.stage3[self.stage2[self.stage1[high] + low]]; }
/// Writes the lookup table as Zig to the given writer. The /// written file exports three constants: stage1, stage2, and /// stage3. These can be used to rebuild the lookup table in Zig. pub fn writeZig(self: *const Self, writer: *std.Io.Writer) !void { try writer.print( \\//! This file is auto-generated. Do not edit. \\ \\pub fn Tables(comptime Elem: type) type {{ \\ return struct {{ \\pub const stage1: [{}]u16 = .{{ , .{self.stage1.len}); for (self.stage1) |entry| try writer.print("{},", .{entry});
try writer.print( \\ \\}}; \\ \\pub const stage2: [{}]u16 = .{{ , .{self.stage2.len}); for (self.stage2) |entry| try writer.print("{},", .{entry}); try writer.writeAll("};");
try writer.print( \\ \\pub const stage3: [{}]Elem = .{{ , .{self.stage3.len}); for (self.stage3) |entry| { if (@typeInfo(@TypeOf(entry)) == .@"struct" and @hasDecl(@TypeOf(entry), "format")) try writer.print("{f},", .{entry}) else try writer.print("{},", .{entry}); } try writer.writeAll( \\}; \\ }; \\} \\ ); } };}