// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie // SPDX-License-Identifier: MIT //! Compiles the parser's AST into bytecode shared by all four engines. //! //! The compiler runs in two modes over identical code paths: a counting pass //! that only measures (`counting = true`), and an emitting pass that writes //! into an exactly-sized buffer. Determinism guarantees both passes agree, //! which is what lets comptime compilation size its arrays without an //! allocator. const std = @import("std"); const common = @import("common.zig"); const parser = @import("parser.zig"); /// Hard cap on program length; counted repeats can expand a lot. pub const max_insts: u32 = 1 << 16; /// Ceiling on instructions times empty-loop-guard masks; see `count`. pub const max_visited_keys: usize = 1 << 20; pub const CharOp = struct { cp: u21, /// ASCII case-insensitive. ci: bool, }; pub const ClassOp = struct { start: u32, len: u32, negated: bool, ci: bool, }; pub const BackrefOp = struct { group: u8, ci: bool, }; /// An iteration that consumed nothing ends the loop — it does not fail. The /// distinction is observable: `(a*)*` against "aa" must report the final /// empty iteration's capture, and `(a*?)*` must match empty rather than be /// forced to consume. PCRE and Python agree on both. pub const ExitIfSame = struct { slot: u16, /// The instruction after the loop. target: u32, }; /// Fused single-element repeat, emitted only into backtracker programs /// (`for_backtrack`). The repeated element is the NEXT instruction (a char, /// class, or any), keeping `Inst` small; execution continues at pc + 2. The /// interpreter consumes greedily in one tight loop and backtracking retries /// are a single range frame instead of one frame per iteration. The Pike VM /// and DFA never see this instruction. pub const RepOp = struct { min: u32, /// `unbounded` (maxInt) means no upper bound. max: u32, greedy: bool, pub const unbounded = std.math.maxInt(u32); }; pub const LookOp = struct { kind: parser.LookKind, /// pc of the sub-program, which ends with its own `match`. target: u32, }; pub const Inst = union(enum) { /// Consume one codepoint equal to this (mod case folding). char: CharOp, /// Consume any codepoint. any, /// Consume any codepoint except '\n'. any_not_nl, /// Consume one codepoint matching the class. class: ClassOp, /// Try [0] first (higher priority), then [1]. split: [2]u32, jmp: u32, /// slots[n] = current position. save: u16, assert: common.Assertion, match, /// Consume text equal to what the capture group matched. backref: BackrefOp, /// Zero-width lookaround running a sub-program. look: LookOp, /// Fused repeat (backtracker programs only). rep: RepOp, /// Scratch slot write, guards empty-body loops. set_pos: u16, /// Leave the loop if the body consumed nothing since `set_pos`. exit_if_same: ExitIfSame, }; /// A compiled program plus everything needed to run it. pub const Program = struct { insts: []const Inst, ranges: []const common.ClassRange, /// 2 per capture group (slots 0 and 1, for group 0, are written by the /// engines rather than by save instructions), then scratch slots for /// loop guards. slot_count: u16, /// Includes group 0. group_count: u8, prefilter: Prefilter, }; pub const CompileError = error{ProgramTooLarge}; /// A class of at most two single ASCII codepoints, plus possibly members at /// or above 0x80: the shape every caseless letter's case-equivalence class /// takes once the parser rewrites it -- `(?i)s` is `{S, s, ſ}`. The JIT /// backends test it as two register compares with the high members behind /// the existing helper path, instead of the general 128-bit table, which is /// what keeps a caseless ASCII scan near its pre-Unicode speed. pub const AsciiPair = struct { cps: [2]u8, n: u8, has_high: bool, }; /// See `AsciiPair`; null when the class is not that shape. pub fn asciiPairOf(ranges: []const common.ClassRange, negated: bool, ci: bool) ?AsciiPair { if (negated or ci) return null; var out: AsciiPair = .{ .cps = undefined, .n = 0, .has_high = false }; for (ranges) |r| { if (r.hi < 0x80) { // A real ASCII range is what the bit table is for. if (r.lo != r.hi or out.n == 2) return null; out.cps[out.n] = @intCast(r.lo); out.n += 1; } else if (r.lo >= 0x80) { out.has_high = true; } else { return null; // straddles the boundary } } return if (out.n == 0) null else out; } pub const Counts = struct { insts: u32, slots: u16, }; pub const Compiler = struct { nodes: []const parser.Node, counting: bool, /// Emit backtracker-only instructions (fused repeats). for_backtrack: bool, insts: []Inst, len: u32 = 0, next_slot: u16, /// Empty-loop guards currently open, and the deepest that got. guard_depth: u8 = 0, max_guard_depth: u8 = 0, const Self = @This(); /// Append (or, in the counting pass, merely count) one instruction and /// return its pc. fn emit(self: *Self, inst: Inst) CompileError!u32 { if (self.len >= max_insts) return error.ProgramTooLarge; // `set_pos`/`exit_if_same` pairs bracket empty-loop guards, and the // pairs nest, so emission order tracks their depth. The Pike VM's // visited table doubles for each level; see `count`. switch (inst) { .set_pos => { self.guard_depth += 1; self.max_guard_depth = @max(self.max_guard_depth, self.guard_depth); }, .exit_if_same => self.guard_depth -|= 1, else => {}, } if (!self.counting) self.insts[self.len] = inst; self.len += 1; return self.len - 1; } fn patchSplit(self: *Self, at: u32, targets: [2]u32) void { if (!self.counting) self.insts[at] = .{ .split = targets }; } fn patchJmp(self: *Self, at: u32, target: u32) void { if (!self.counting) self.insts[at] = .{ .jmp = target }; } fn patchExit(self: *Self, at: u32, slot: u16, target: u32) void { if (!self.counting) self.insts[at] = .{ .exit_if_same = .{ .slot = slot, .target = target } }; } /// Emit the whole program: the unanchored `.*?`-style prefix is the /// engines' job, so this is just the pattern followed by `match`. fn compileRoot(self: *Self, root: parser.NodeIndex) CompileError!void { // Group 0 is not compiled as save instructions: both engines track // the match span directly (seed position and position at `match`), // so threads that never enter a capture group touch no slots at all. // Slots 0 and 1 stay reserved in the layout and are filled by the // engines on success. try self.emitNode(root); _ = try self.emit(.match); } /// Emit one AST node. Recursive over the tree, which the parser keeps /// balanced so this stays log-deep in the pattern's length. fn emitNode(self: *Self, idx: parser.NodeIndex) CompileError!void { switch (self.nodes[idx]) { .empty => {}, .literal => |l| _ = try self.emit(.{ .char = .{ .cp = l.cp, .ci = l.ci } }), .any => |nl| _ = try self.emit(if (nl) .any else .any_not_nl), .class => |cl| _ = try self.emit(.{ .class = .{ .start = cl.start, .len = cl.len, .negated = cl.negated, .ci = cl.ci, } }), .concat => |ab| { try self.emitNode(ab[0]); try self.emitNode(ab[1]); }, .alt => |ab| { const s = try self.emit(.{ .split = .{ 0, 0 } }); const a_start = self.len; try self.emitNode(ab[0]); const j = try self.emit(.{ .jmp = 0 }); const b_start = self.len; try self.emitNode(ab[1]); self.patchSplit(s, .{ a_start, b_start }); self.patchJmp(j, self.len); }, .repeat => |r| { if (self.for_backtrack) { if (self.fusableChild(r.child)) |child_inst| { _ = try self.emit(.{ .rep = .{ .min = r.min, .max = r.max orelse RepOp.unbounded, .greedy = r.greedy, } }); _ = try self.emit(child_inst); return; } } // An iteration that consumes nothing ends the loop, but // only once the minimum is met: below it the repeat has to // keep going however little it matches. So for `e{n,}` the // copy that meets the minimum carries a guard of its own, // and an empty one skips the unbounded tail entirely rather // than letting it run further iterations. Without this, // `(?:()|a\1)+` would keep looping past an empty first // iteration and let a later one read what it captured. var min_guard: ?u32 = null; var min_slot: u16 = 0; var i: u32 = 0; while (i < r.min) : (i += 1) { const guard_this = r.max == null and i + 1 == r.min and self.nullable(r.child); if (guard_this) { min_slot = self.next_slot; self.next_slot += 1; _ = try self.emit(.{ .set_pos = min_slot }); } try self.emitNode(r.child); if (guard_this) { min_guard = try self.emit(.{ .exit_if_same = .{ .slot = min_slot, .target = 0 } }); } } if (r.max) |m| { try self.emitOptChain(m - r.min, r.child, r.greedy); } else { try self.emitStar(r.child, r.greedy); } // The star's exit is wherever emission has reached. if (min_guard) |g| self.patchExit(g, min_slot, self.len); }, .group => |g| { if (g.index) |gi| { _ = try self.emit(.{ .save = 2 * @as(u16, gi) }); try self.emitNode(g.child); _ = try self.emit(.{ .save = 2 * @as(u16, gi) + 1 }); } else { try self.emitNode(g.child); } }, .assertion => |a| _ = try self.emit(.{ .assert = a }), .backref => |b| _ = try self.emit(.{ .backref = .{ .group = b.index, .ci = b.ci } }), .look => |l| { const j = try self.emit(.{ .jmp = 0 }); const sub = self.len; try self.emitNode(l.child); _ = try self.emit(.match); self.patchJmp(j, self.len); _ = try self.emit(.{ .look = .{ .kind = l.kind, .target = sub } }); }, } } /// A repeat body that is a single codepoint test can be fused; unwrap /// non-capturing groups on the way (captures inside a repeat cannot fuse). fn fusableChild(self: *Self, idx: parser.NodeIndex) ?Inst { var i = idx; while (true) switch (self.nodes[i]) { .group => |g| { if (g.index != null) return null; i = g.child; }, .literal => |l| return .{ .char = .{ .cp = l.cp, .ci = l.ci } }, .class => |cl| return .{ .class = .{ .start = cl.start, .len = cl.len, .negated = cl.negated, .ci = cl.ci, } }, .any => |nl| return if (nl) .any else .any_not_nl, else => return null, }; } /// `e*` (or the unbounded tail of `e{n,}`). Bodies that can match empty /// get a progress guard so backtracking terminates. fn emitStar(self: *Self, child: parser.NodeIndex, greedy: bool) CompileError!void { const guarded = self.nullable(child); var slot: u16 = 0; if (guarded) { slot = self.next_slot; self.next_slot += 1; } const top = self.len; const s = try self.emit(.{ .split = .{ 0, 0 } }); const body = self.len; if (guarded) _ = try self.emit(.{ .set_pos = slot }); try self.emitNode(child); var guard: u32 = 0; if (guarded) guard = try self.emit(.{ .exit_if_same = .{ .slot = slot, .target = 0 } }); _ = try self.emit(.{ .jmp = top }); const exit = self.len; self.patchSplit(s, if (greedy) .{ body, exit } else .{ exit, body }); if (guarded) self.patchExit(guard, slot, exit); } /// `e{0,n}` as a chain of nested options: skipping one copy skips them all. fn emitOptChain(self: *Self, n: u32, child: parser.NodeIndex, greedy: bool) CompileError!void { if (n == 0) return; const s = try self.emit(.{ .split = .{ 0, 0 } }); const body = self.len; try self.emitNode(child); try self.emitOptChain(n - 1, child, greedy); const exit = self.len; self.patchSplit(s, if (greedy) .{ body, exit } else .{ exit, body }); } /// Can this subtree match the empty string? fn nullable(self: *Self, idx: parser.NodeIndex) bool { return switch (self.nodes[idx]) { .empty, .assertion, .look => true, .literal, .class, .any => false, .concat => |ab| self.nullable(ab[0]) and self.nullable(ab[1]), .alt => |ab| self.nullable(ab[0]) or self.nullable(ab[1]), .repeat => |r| r.min == 0 or self.nullable(r.child), .group => |g| self.nullable(g.child), .backref => true, }; } }; /// Counting pass: how many instructions and slots `root` compiles to. pub fn count( nodes: []const parser.Node, root: parser.NodeIndex, group_count: u8, for_backtrack: bool, ) CompileError!Counts { var c = Compiler{ .nodes = nodes, .counting = true, .for_backtrack = for_backtrack, .insts = &.{}, .next_slot = 2 * @as(u16, group_count), }; try c.compileRoot(root); // The Pike VM's visited table is one entry per instruction per guard // mask -- it doubles for each level of empty-loop guard nesting, up to // six -- and its thread lists are sized alongside it at roughly eighty // bytes a key. Accepting a program that is at once near the instruction // ceiling and six levels deep in nullable loops means accepting a // half-gigabyte allocation from a 381-byte pattern, so such a program is // turned away here with the same error as any other that is too big to // run. Every pattern up to sixteen thousand instructions keeps all six // levels, which is far past anything not built to hit this. const guard_bits: u5 = @intCast(@min(c.max_guard_depth, 6)); if ((@as(usize, c.len) << guard_bits) > max_visited_keys) return error.ProgramTooLarge; return .{ .insts = c.len, .slots = c.next_slot }; } /// Emitting pass: writes exactly `count().insts` instructions into `insts`. pub fn emitInto( nodes: []const parser.Node, root: parser.NodeIndex, group_count: u8, for_backtrack: bool, insts: []Inst, ) CompileError!void { var c = Compiler{ .nodes = nodes, .counting = false, .for_backtrack = for_backtrack, .insts = insts, .next_slot = 2 * @as(u16, group_count), }; try c.compileRoot(root); std.debug.assert(c.len == insts.len); } // --------------------------------------------------------------------------- // Tests /// Parse and compile in one step for this file's tests, sized like the real /// path. fn compileForTest( gpa: std.mem.Allocator, pattern: []const u8, flags: common.Flags, ) !struct { insts: []Inst, slots: u16, p: u8 } { if (pattern.len > parser.max_pattern_len) return error.PatternTooLong; const sizes = parser.bufferSizes(pattern.len, parser.mayBeCaseless(pattern, flags)); const nodes = try gpa.alloc(parser.Node, sizes.nodes); defer gpa.free(nodes); const ranges = try gpa.alloc(common.ClassRange, sizes.ranges); defer gpa.free(ranges); var names: [parser.max_groups]parser.NamedGroup = undefined; var p = parser.Parser{ .pattern = pattern, .flags = flags, .nodes = nodes, .ranges = ranges, .names = &names, }; const root = try p.parse(); const counts = try count(p.nodes[0..p.nodes_len], root, p.group_count, p.has_backref or p.has_look); const insts = try gpa.alloc(Inst, counts.insts); errdefer gpa.free(insts); try emitInto(p.nodes[0..p.nodes_len], root, p.group_count, p.has_backref or p.has_look, insts); return .{ .insts = insts, .slots = counts.slots, .p = p.group_count }; } test "count matches emit and programs are well-formed" { const gpa = std.testing.allocator; const patterns = [_][]const u8{ "abc", "a|b|c", "a*b+?c{2,4}d{3}e{2,}", "(a(?b))\\1\\k", "[^a-z]\\d\\S.", "(?=ab)c(?= 1); try std.testing.expect(r.insts[r.insts.len - 1] == .match); // All jump targets must be in range. for (r.insts) |inst| switch (inst) { .split => |t| { try std.testing.expect(t[0] < r.insts.len); try std.testing.expect(t[1] < r.insts.len); }, .jmp => |t| try std.testing.expect(t < r.insts.len), .look => |l| try std.testing.expect(l.target < r.insts.len), .save => |s| try std.testing.expect(s < r.slots), .set_pos => |s| try std.testing.expect(s < r.slots), .exit_if_same => |g| { try std.testing.expect(g.slot < r.slots); try std.testing.expect(g.target <= r.insts.len); }, else => {}, }; } } test "nullable star bodies get progress guards" { const gpa = std.testing.allocator; const r = try compileForTest(gpa, "(?:a*)*", .{}); defer gpa.free(r.insts); var has_guard = false; for (r.insts) |inst| { if (inst == .exit_if_same) has_guard = true; } try std.testing.expect(has_guard); // Non-nullable body: no guard. const r2 = try compileForTest(gpa, "a*", .{}); defer gpa.free(r2.insts); for (r2.insts) |inst| try std.testing.expect(inst != .exit_if_same); } test "program size cap" { const gpa = std.testing.allocator; try std.testing.expectError( error.ProgramTooLarge, compileForTest(gpa, "(?:(?:(?:a{1000}){1000}){1000})", .{}), ); } // --------------------------------------------------------------------------- // First-byte prefilter /// The set of bytes a match can possibly start with, computed from the /// program. Lets the engines skip start positions instead of seeding a match /// attempt at every one. pub const Prefilter = struct { bytes: [256]bool, /// False when the analysis bailed (`.`, negated class, leading backref, /// or a pattern that can match empty): every position is a candidate. usable: bool, /// No candidate byte is a UTF-8 continuation byte, so a scan may step one /// byte at a time rather than decoding to find the next boundary. /// /// Landing inside a multi-byte sequence is harmless when this holds: the /// bytes inside one are all 0x80..0xBF, none of them is a candidate, and /// the scan simply steps past. Requiring every candidate to be ASCII, as /// this used to, gave up the cheap loop for any class reaching past /// ASCII -- which, once `(?i)s` grew to include the long s, meant an /// ordinary caseless literal. byte_steppable: bool, /// Exactly one candidate byte (ASCII): use a vectorized memchr scan. single: ?u8, /// How many bytes are candidates; a small count means byte-skipping /// alone is highly selective. count: u16, pub const unusable: Prefilter = .{ .bytes = @splat(true), .usable = false, .byte_steppable = false, .single = null, .count = 256, }; /// First position >= `start` where a match could begin (input.len if /// none). Only stops at positions our decoder treats as boundaries. pub fn scan(pf: *const Prefilter, input: []const u8, start: usize) usize { if (pf.single) |b| { return std.mem.indexOfScalarPos(u8, input, start, b) orelse input.len; } var pos = start; if (pf.byte_steppable) { while (pos < input.len and !pf.bytes[input[pos]]) pos += 1; return pos; } while (pos < input.len and !pf.bytes[input[pos]]) { pos += common.decode(input, pos).len; } return pos; } }; const FirstBytes = struct { bytes: [256]bool = @splat(false), ok: bool = true, fn addByte(fb: *FirstBytes, b: u8) void { fb.bytes[b] = true; } /// A codepoint a match may start with: its byte if ASCII (both cases /// under `ci`), otherwise its UTF-8 lead byte -- and, for the decoder's /// invalid-byte fallback, the raw byte value too. fn addChar(fb: *FirstBytes, cp: u21, ci: bool) void { if (cp < 0x80) { fb.addByte(@intCast(cp)); if (ci) fb.addByte(@intCast(common.foldLower(cp))); if (ci and cp >= 'a' and cp <= 'z') fb.addByte(@intCast(cp - 32)); return; } // UTF-8 lead byte. var buf: [4]u8 = undefined; _ = std.unicode.utf8Encode(cp, &buf) catch return fb.bail(); fb.addByte(buf[0]); // Our decoder degrades an invalid byte to a codepoint of its own // value, so a raw byte can also start (be all of) this codepoint. if (cp <= 0xFF) fb.addByte(@intCast(cp)); } /// Every first byte a codepoint range can produce, per UTF-8 length /// class. fn addRange(fb: *FirstBytes, lo: u21, hi: u21, ci: bool) void { // ASCII portion: exact bytes (with case folding). var cp: u21 = lo; while (cp <= @min(hi, 0x7F)) : (cp += 1) fb.addChar(cp, ci); // Lead bytes per UTF-8 length class. if (hi >= 0x80 and lo <= 0x7FF) { const a: u32 = @max(lo, 0x80) >> 6; const b: u32 = @min(hi, 0x7FF) >> 6; for (a..b + 1) |x| fb.addByte(@intCast(0xC0 | x)); } if (hi >= 0x800 and lo <= 0xFFFF) { const a: u32 = @max(lo, 0x800) >> 12; const b: u32 = @min(hi, 0xFFFF) >> 12; for (a..b + 1) |x| fb.addByte(@intCast(0xE0 | x)); } if (hi >= 0x10000) { const a: u32 = @max(lo, 0x10000) >> 18; const b: u32 = @min(hi, parser.max_codepoint) >> 18; for (a..b + 1) |x| fb.addByte(@intCast(0xF0 | x)); } // Raw invalid-byte fallback values. if (hi >= 0x80 and lo <= 0xFF) { const a: u32 = @max(lo, 0x80); const b: u32 = @min(hi, 0xFF); for (a..b + 1) |x| fb.addByte(@intCast(x)); } } /// Give up: mark every byte a candidate, which `finish` reports as an /// unusable prefilter. fn bail(fb: *FirstBytes) void { fb.ok = false; } }; /// Walk the epsilon structure from pc 0 and collect possible first bytes. /// `visited` and `stack` must both be `insts.len` long. pub fn computeFirstBytes( insts: []const Inst, ranges: []const common.ClassRange, visited: []bool, stack: []u32, ) Prefilter { @memset(visited, false); var fb = FirstBytes{}; var sp: usize = 0; stack[sp] = 0; sp += 1; visited[0] = true; while (sp > 0 and fb.ok) { sp -= 1; const pc = stack[sp]; const push = struct { fn f(v: []bool, st: []u32, p: *usize, t: u32) void { if (!v[t]) { v[t] = true; st[p.*] = t; p.* += 1; } } }.f; switch (insts[pc]) { .jmp => |t| push(visited, stack, &sp, t), .split => |t| { push(visited, stack, &sp, t[0]); push(visited, stack, &sp, t[1]); }, // Zero-width: keep walking. Lookarounds only constrain a match, // so skipping over them keeps the byte set an over-approximation. .save, .set_pos, .assert, .look => push(visited, stack, &sp, pc + 1), // Either way out of the loop can begin a match. .exit_if_same => |g| { push(visited, stack, &sp, pc + 1); push(visited, stack, &sp, g.target); }, .char => |c| fb.addChar(c.cp, c.ci), .class => |cl| { if (cl.negated) { fb.bail(); } else { for (ranges[cl.start..][0..cl.len]) |r| fb.addRange(r.lo, r.hi, cl.ci); } }, .rep => |r| { // The child (next instruction) supplies the first bytes. push(visited, stack, &sp, pc + 1); // A rep with min == 0 is skippable: what follows can also start. if (r.min == 0) push(visited, stack, &sp, pc + 2); }, .any, .any_not_nl, .backref => fb.bail(), // Match reachable without consuming: the pattern can match empty // anywhere, so every position is a candidate. .match => fb.bail(), } } if (!fb.ok) return .unusable; var n: usize = 0; var byte_steppable = true; var single: ?u8 = null; for (fb.bytes, 0..) |set, b| { if (!set) continue; n += 1; single = if (n == 1) @intCast(b) else null; // A continuation byte as a candidate is the only thing that makes // stepping unsafe; a lead byte never appears inside a sequence. if (b >= 0x80 and b < 0xC0) byte_steppable = false; } if (n == 0 or n == 256) return .unusable; return .{ .bytes = fb.bytes, .usable = true, .byte_steppable = byte_steppable, // `memchr` finds a byte anywhere, so the single-byte scan needs the // candidate to be one a match can actually start at. .single = if (byte_steppable and single != null and single.? < 0x80) single else null, .count = @intCast(n), }; } // --------------------------------------------------------------------------- // Alphabet compression for the lazy DFA /// Partition of all codepoints into equivalence classes: two codepoints in /// the same class are indistinguishable to every consuming instruction in the /// program (including under ASCII case folding) and agree on the properties /// assertions care about (word char, newline). DFA states then need one /// transition per class instead of per codepoint. pub const Alphabet = struct { ok: bool, /// Class of every cp < 256 (covers ASCII and the invalid-byte fallback). low: [256]u8, /// Sorted interval start points; interval i covers [starts[i], starts[i+1]). /// starts[0] is always 0. Class i == interval i. starts: []const u21, pub const disabled: Alphabet = .{ .ok = false, .low = @splat(0), .starts = &.{} }; /// Number of real classes; the DFA uses `numClasses()` itself as the /// end-of-input pseudo-class. pub fn numClasses(a: *const Alphabet) u16 { return @intCast(a.starts.len); } /// The equivalence class a codepoint falls in; codepoints in one class /// are indistinguishable to the program. pub fn classOf(a: *const Alphabet, cp: u21) u16 { if (cp < 256) return a.low[cp]; // Greatest starts[i] <= cp. var lo: usize = 0; var hi: usize = a.starts.len; while (hi - lo > 1) { const mid = lo + (hi - lo) / 2; if (a.starts[mid] <= cp) lo = mid else hi = mid; } return @intCast(lo); } /// A representative codepoint of class k. pub fn sample(a: *const Alphabet, k: u16) u21 { return a.starts[k]; } }; /// Required size of the boundary scratch buffer for `computeAlphabet`. pub fn alphabetBufferSize(inst_count: usize) usize { return 6 * inst_count + 24; } /// Compute the codepoint partition. The returned `starts` slice aliases /// `bounds_buf`; the caller copies it into owned storage. Returns a disabled /// alphabet when the partition would exceed 254 classes. pub fn computeAlphabet( insts: []const Inst, ranges: []const common.ClassRange, bounds_buf: []u21, ) Alphabet { var n: usize = 0; const add = struct { fn f(buf: []u21, len: *usize, cp: u21) void { if (len.* < buf.len) { buf[len.*] = cp; len.* += 1; } } }.f; const addCp = struct { fn f(buf: []u21, len: *usize, cp: u21) void { f2(buf, len, cp); if (cp < parser.max_codepoint) f2(buf, len, cp + 1); } fn f2(buf: []u21, len: *usize, cp: u21) void { if (len.* < buf.len) { buf[len.*] = cp; len.* += 1; } } }; _ = add; // Always present: 0, word-char set edges, newline (assertion context). addCp.f2(bounds_buf, &n, 0); for ([_][2]u21{ .{ '0', '9' }, .{ 'A', 'Z' }, .{ '_', '_' }, .{ 'a', 'z' } }) |w| { addCp.f2(bounds_buf, &n, w[0]); addCp.f2(bounds_buf, &n, w[1] + 1); } addCp.f(bounds_buf, &n, '\n'); for (insts) |inst| switch (inst) { .char => |c| { addCp.f(bounds_buf, &n, c.cp); // Case-fold image so ci equality stays uniform per class. if (c.cp >= 'a' and c.cp <= 'z') addCp.f(bounds_buf, &n, c.cp - 32); if (c.cp >= 'A' and c.cp <= 'Z') addCp.f(bounds_buf, &n, c.cp + 32); }, .class => |cl| for (ranges[cl.start..][0..cl.len]) |r| { addCp.f2(bounds_buf, &n, r.lo); addCp.f2(bounds_buf, &n, r.hi + 1); // Fold images of the letter intersections. if (r.hi >= 'a' and r.lo <= 'z') { addCp.f2(bounds_buf, &n, @max(r.lo, 'a') - 32); addCp.f2(bounds_buf, &n, @min(r.hi, 'z') - 32 + 1); } if (r.hi >= 'A' and r.lo <= 'Z') { addCp.f2(bounds_buf, &n, @max(r.lo, 'A') + 32); addCp.f2(bounds_buf, &n, @min(r.hi, 'Z') + 32 + 1); } }, else => {}, }; if (n >= bounds_buf.len) return .disabled; // overflowed scratch space std.mem.sort(u21, bounds_buf[0..n], {}, std.sort.asc(u21)); // Unique in place; drop anything above the codepoint space. var m: usize = 0; for (bounds_buf[0..n]) |b| { if (b > parser.max_codepoint) break; if (m == 0 or bounds_buf[m - 1] != b) { bounds_buf[m] = b; m += 1; } } if (m == 0 or m > 254) return .disabled; var a = Alphabet{ .ok = true, .low = undefined, .starts = bounds_buf[0..m] }; for (0..256) |cp| { var lo: usize = 0; var hi: usize = m; while (hi - lo > 1) { const mid = lo + (hi - lo) / 2; if (a.starts[mid] <= cp) lo = mid else hi = mid; } a.low[cp] = @intCast(lo); } return a; } test computeAlphabet { // "[a-c]x" style program. const insts = [_]Inst{ .{ .class = .{ .start = 0, .len = 1, .negated = false, .ci = false } }, .{ .char = .{ .cp = 'x', .ci = false } }, .match, }; const rs = [_]common.ClassRange{.{ .lo = 'a', .hi = 'c' }}; var buf: [alphabetBufferSize(insts.len)]u21 = undefined; const a = computeAlphabet(&insts, &rs, &buf); try std.testing.expect(a.ok); // Same class within [a-c], different from 'd' and from 'x'. try std.testing.expectEqual(a.classOf('a'), a.classOf('c')); try std.testing.expect(a.classOf('a') != a.classOf('d')); try std.testing.expect(a.classOf('x') != a.classOf('a')); // Fold images of [a-c] are isolated too. try std.testing.expectEqual(a.classOf('A'), a.classOf('C')); try std.testing.expect(a.classOf('A') != a.classOf('D')); // Word/newline properties are uniform per class. try std.testing.expect(a.classOf('\n') != a.classOf(' ')); try std.testing.expect(a.classOf('_') != a.classOf('-')); // High codepoints hit the search path. try std.testing.expectEqual(a.classOf(0x1F600), a.classOf(0x1F601)); }