const std = @import("std");const unicode_letter = @import("json_schema_unicode_letter.zig"); const Allocator = std.mem.Allocator;const invalid_index = std.math.maxInt(usize); pub const Limits = struct { max_depth: usize, max_states: usize, max_repeat: usize, max_steps: usize,}; pub const Error = error{ InvalidPattern, PatternLimitExceeded, InvalidUtf8,} || Allocator.Error; const Pair = struct { left: usize, right: usize };const Repeat = struct { child: usize, min: usize, max: ?usize };const Atom = struct { node: usize, quantifiable: bool = true }; const Node = union(enum) { empty, literal: u21, any, class: usize, concat: Pair, alternate: Pair, repeat: Repeat, assert_start, assert_end,}; const Range = struct { first: u21, last: u21 }; fn isEcmascriptWhitespace(codepoint: u21) bool { return switch (codepoint) { 0x0009...0x000D, 0x0020, 0x00A0, 0x1680, 0x2000...0x200A, 0x2028, 0x2029, 0x202F, 0x205F, 0x3000, 0xFEFF, => true, else => false, };} const CharacterClass = struct { range_start: usize, range_len: usize, negated: bool = false, ascii_digit: bool = false, ascii_word: bool = false, ecmascript_space: bool = false, not_ecmascript_space: bool = false, unicode_letter: bool = false, fn matches(self: CharacterClass, ranges: []const Range, codepoint: u21) bool { var matched = self.unicode_letter and unicode_letter.contains(codepoint); matched = matched or (self.ascii_digit and codepoint >= '0' and codepoint <= '9'); matched = matched or (self.ascii_word and ((codepoint >= 'a' and codepoint <= 'z') or (codepoint >= 'A' and codepoint <= 'Z') or (codepoint >= '0' and codepoint <= '9') or codepoint == '_')); const is_space = isEcmascriptWhitespace(codepoint); matched = matched or (self.ecmascript_space and is_space); matched = matched or (self.not_ecmascript_space and !is_space); for (ranges[self.range_start..][0..self.range_len]) |range| { if (codepoint >= range.first and codepoint <= range.last) { matched = true; break; } } return if (self.negated) !matched else matched; }}; const Parser = struct { alloc: Allocator, source: []const u8, limits: Limits, index: usize = 0, group_depth: usize = 0, nodes: std.ArrayList(Node) = .empty, classes: std.ArrayList(CharacterClass) = .empty, ranges: std.ArrayList(Range) = .empty, fn deinit(self: *Parser) void { self.nodes.deinit(self.alloc); self.classes.deinit(self.alloc); self.ranges.deinit(self.alloc); } fn parse(self: *Parser) Error!usize { const root = try self.parseAlternation(null); if (self.index != self.source.len) return error.InvalidPattern; return root; } fn parseAlternation(self: *Parser, terminator: ?u8) Error!usize { var left = try self.parseSequence(terminator); while (self.peekByte() == '|') { self.index += 1; const right = try self.parseSequence(terminator); left = try self.addNode(.{ .alternate = .{ .left = left, .right = right } }); } return left; } fn parseSequence(self: *Parser, terminator: ?u8) Error!usize { var result: ?usize = null; while (self.index < self.source.len) { const byte = self.source[self.index]; if (byte == '|' or (terminator != null and byte == terminator.?)) break; const item = try self.parseRepetition(); result = if (result) |left| try self.addNode(.{ .concat = .{ .left = left, .right = item } }) else item; } return result orelse try self.addNode(.empty); } fn parseRepetition(self: *Parser) Error!usize { const atom = try self.parseAtom(); if (self.index >= self.source.len) return atom.node; if (!atom.quantifiable) switch (self.source[self.index]) { '*', '+', '?', '{' => return error.InvalidPattern, else => {}, }; var min: usize = undefined; var max: ?usize = undefined; switch (self.source[self.index]) { '*' => { self.index += 1; min = 0; max = null; }, '+' => { self.index += 1; min = 1; max = null; }, '?' => { self.index += 1; min = 0; max = 1; }, '{' => { self.index += 1; min = try self.parseCount(); if (self.consumeByte('}')) { max = min; } else { if (!self.consumeByte(',')) return error.InvalidPattern; max = if (self.consumeByte('}')) null else blk: { const upper = try self.parseCount(); if (!self.consumeByte('}')) return error.InvalidPattern; break :blk upper; }; } }, else => return atom.node, } if (max) |upper| if (upper < min) return error.InvalidPattern; if (min > self.limits.max_repeat or (max orelse min) > self.limits.max_repeat) { return error.PatternLimitExceeded; } _ = self.consumeByte('?'); // Lazy quantifiers have identical acceptance semantics. if (self.index < self.source.len) switch (self.source[self.index]) { '*', '+', '?', '{' => return error.InvalidPattern, else => {}, }; return self.addNode(.{ .repeat = .{ .child = atom.node, .min = min, .max = max } }); } fn parseAtom(self: *Parser) Error!Atom { if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; switch (byte) { '^' => { self.index += 1; return .{ .node = try self.addNode(.assert_start), .quantifiable = false }; }, '$' => { self.index += 1; return .{ .node = try self.addNode(.assert_end), .quantifiable = false }; }, '.' => { self.index += 1; return .{ .node = try self.addNode(.any) }; }, '(' => { self.index += 1; if (self.peekByte() == '?') return error.InvalidPattern; if (self.group_depth >= self.limits.max_depth) { return error.PatternLimitExceeded; } self.group_depth += 1; defer self.group_depth -= 1; const nested = try self.parseAlternation(')'); if (!self.consumeByte(')')) return error.InvalidPattern; return .{ .node = nested }; }, '[' => return .{ .node = try self.parseCharacterClass() }, '\\' => return .{ .node = try self.parseEscapeNode() }, ')', ']', '}', '|', '*', '+', '?', '{' => return error.InvalidPattern, else => { const codepoint = try self.nextCodepoint(); return .{ .node = try self.addNode(.{ .literal = codepoint }) }; }, } } fn parseEscapeNode(self: *Parser) Error!usize { self.index += 1; if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; self.index += 1; switch (byte) { 'd', 'D', 'w', 'W', 's', 'S' => { var class = CharacterClass{ .range_start = self.ranges.items.len, .range_len = 0, .negated = std.ascii.isUpper(byte), }; switch (std.ascii.toLower(byte)) { 'd' => class.ascii_digit = true, 'w' => class.ascii_word = true, 's' => class.ecmascript_space = true, else => unreachable, } return self.addClassNode(class); }, 'p', 'P' => { if (!self.consumeByte('{')) return error.InvalidPattern; const start = self.index; while (self.index < self.source.len and self.source[self.index] != '}') : (self.index += 1) {} if (!self.consumeByte('}')) return error.InvalidPattern; const property = self.source[start .. self.index - 1]; if (!std.mem.eql(u8, property, "Letter") and !std.mem.eql(u8, property, "L")) { return error.InvalidPattern; } return self.addClassNode(.{ .range_start = self.ranges.items.len, .range_len = 0, .negated = byte == 'P', .unicode_letter = true, }); }, 'n' => return self.addNode(.{ .literal = '\n' }), 'r' => return self.addNode(.{ .literal = '\r' }), 't' => return self.addNode(.{ .literal = '\t' }), 'f' => return self.addNode(.{ .literal = 0x0C }), 'v' => return self.addNode(.{ .literal = 0x0B }), 'x' => return self.addNode(.{ .literal = try self.parseHexCodepoint(2) }), 'u' => { if (self.consumeByte('{')) { const codepoint = try self.parseVariableHexCodepoint(); if (!self.consumeByte('}')) return error.InvalidPattern; return self.addNode(.{ .literal = codepoint }); } return self.addNode(.{ .literal = try self.parseHexCodepoint(4) }); }, '0' => { if (self.peekByte()) |next| if (std.ascii.isDigit(next)) { return error.InvalidPattern; }; return self.addNode(.{ .literal = 0 }); }, '1'...'9', 'b', 'B', 'c', 'k' => return error.InvalidPattern, else => { if (!isIdentityEscape(byte, false)) return error.InvalidPattern; return self.addNode(.{ .literal = byte }); }, } } fn parseCharacterClass(self: *Parser) Error!usize { self.index += 1; var class = CharacterClass{ .range_start = self.ranges.items.len, .range_len = 0, .negated = self.consumeByte('^'), }; var first = true; while (self.index < self.source.len) { if (self.source[self.index] == ']' and !first) { self.index += 1; class.range_len = self.ranges.items.len - class.range_start; return self.addClassNode(class); } const left = try self.parseClassAtom(&class); first = false; if (left == null) { if (self.peekByte() == '-' and self.index + 1 < self.source.len and self.source[self.index + 1] != ']') { return error.InvalidPattern; } continue; } if (self.peekByte() == '-' and self.index + 1 < self.source.len and self.source[self.index + 1] != ']') { self.index += 1; const right = (try self.parseClassAtom(&class)) orelse return error.InvalidPattern; if (right < left.?) return error.InvalidPattern; try self.ranges.append(self.alloc, .{ .first = left.?, .last = right }); } else { try self.ranges.append(self.alloc, .{ .first = left.?, .last = left.? }); } if (self.ranges.items.len - class.range_start > self.limits.max_states) { return error.PatternLimitExceeded; } } return error.InvalidPattern; } fn parseClassAtom(self: *Parser, class: *CharacterClass) Error!?u21 { if (self.index >= self.source.len) return error.InvalidPattern; if (self.source[self.index] != '\\') return try self.nextCodepoint(); self.index += 1; if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; self.index += 1; switch (byte) { 'd' => { class.ascii_digit = true; return null; }, 'w' => { class.ascii_word = true; return null; }, 's' => { class.ecmascript_space = true; return null; }, 'S' => { class.not_ecmascript_space = true; return null; }, 'D', 'W', 'p', 'P', 'b', 'B', '1'...'9', 'c', 'k' => return error.InvalidPattern, '0' => { if (self.peekByte()) |next| if (std.ascii.isDigit(next)) { return error.InvalidPattern; }; return 0; }, 'n' => return '\n', 'r' => return '\r', 't' => return '\t', 'f' => return 0x0C, 'v' => return 0x0B, 'x' => return try self.parseHexCodepoint(2), 'u' => return try self.parseHexCodepoint(4), else => { if (!isIdentityEscape(byte, true)) return error.InvalidPattern; return @as(u21, byte); }, } } fn addClassNode(self: *Parser, class: CharacterClass) Error!usize { if (self.classes.items.len >= self.limits.max_states) return error.PatternLimitExceeded; const index = self.classes.items.len; try self.classes.append(self.alloc, class); return self.addNode(.{ .class = index }); } fn addNode(self: *Parser, node: Node) Error!usize { if (self.nodes.items.len >= self.limits.max_states) return error.PatternLimitExceeded; const index = self.nodes.items.len; try self.nodes.append(self.alloc, node); return index; } fn parseCount(self: *Parser) Error!usize { const start = self.index; while (self.index < self.source.len and std.ascii.isDigit(self.source[self.index])) : (self.index += 1) {} if (self.index == start) return error.InvalidPattern; return std.fmt.parseInt(usize, self.source[start..self.index], 10) catch return error.PatternLimitExceeded; } fn parseHexCodepoint(self: *Parser, digits: usize) Error!u21 { if (digits > self.source.len - self.index) return error.InvalidPattern; const value = std.fmt.parseInt(u21, self.source[self.index..][0..digits], 16) catch return error.InvalidPattern; self.index += digits; if (!std.unicode.utf8ValidCodepoint(value)) return error.InvalidPattern; return value; } fn parseVariableHexCodepoint(self: *Parser) Error!u21 { const start = self.index; while (self.index < self.source.len and self.source[self.index] != '}') : (self.index += 1) {} if (self.index == start or self.index - start > 6) return error.InvalidPattern; const value = std.fmt.parseInt(u21, self.source[start..self.index], 16) catch return error.InvalidPattern; if (!std.unicode.utf8ValidCodepoint(value)) return error.InvalidPattern; return value; } fn nextCodepoint(self: *Parser) Error!u21 { const width = std.unicode.utf8ByteSequenceLength(self.source[self.index]) catch return error.InvalidUtf8; if (width > self.source.len - self.index) return error.InvalidUtf8; const codepoint = std.unicode.utf8Decode(self.source[self.index..][0..width]) catch return error.InvalidUtf8; self.index += width; return codepoint; } fn peekByte(self: *const Parser) ?u8 { return if (self.index < self.source.len) self.source[self.index] else null; } fn consumeByte(self: *Parser, expected: u8) bool { if (self.peekByte() != expected) return false; self.index += 1; return true; }}; fn isIdentityEscape(byte: u8, in_class: bool) bool { return switch (byte) { '^', '$', '\\', '.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '/' => true, '-' => in_class, else => false, };} const Op = enum { epsilon, literal, any, class, split, assert_start, assert_end, accept };const Instruction = struct { op: Op, out: usize = invalid_index, out1: usize = invalid_index, value: usize = 0,};const Patch = struct { instruction: usize, second: bool = false };const Fragment = struct { start: usize, outs: std.ArrayList(Patch) }; const Compiler = struct { alloc: Allocator, nodes: []const Node, limits: Limits, instructions: std.ArrayList(Instruction) = .empty, fn deinit(self: *Compiler) void { self.instructions.deinit(self.alloc); } fn compile(self: *Compiler, node_index: usize) Error!usize { var fragment = try self.compileNode(node_index); defer fragment.outs.deinit(self.alloc); const accept = try self.addInstruction(.{ .op = .accept }); self.patch(fragment.outs.items, accept); return fragment.start; } fn compileNode(self: *Compiler, node_index: usize) Error!Fragment { return switch (self.nodes[node_index]) { .empty => self.single(.{ .op = .epsilon }, false), .literal => |value| self.single(.{ .op = .literal, .value = value }, false), .any => self.single(.{ .op = .any }, false), .class => |value| self.single(.{ .op = .class, .value = value }, false), .assert_start => self.single(.{ .op = .assert_start }, false), .assert_end => self.single(.{ .op = .assert_end }, false), .concat => |pair| self.compileConcat(pair), .alternate => |pair| self.compileAlternate(pair), .repeat => |repeat| self.compileRepeat(repeat), }; } fn compileConcat(self: *Compiler, pair: Pair) Error!Fragment { var left = try self.compileNode(pair.left); errdefer left.outs.deinit(self.alloc); var right = try self.compileNode(pair.right); errdefer right.outs.deinit(self.alloc); const left_owned = left; const right_owned = right; left.outs = .empty; right.outs = .empty; return self.concat(left_owned, right_owned); } fn compileAlternate(self: *Compiler, pair: Pair) Error!Fragment { var left = try self.compileNode(pair.left); errdefer left.outs.deinit(self.alloc);Lines 1–500 of 843. Load more
const std = @import("std"); const unicode_letter = @import("json_schema_unicode_letter.zig"); const Allocator = std.mem.Allocator; const invalid_index = std.math.maxInt(usize); pub const Limits = struct { max_depth: usize, max_states: usize, max_repeat: usize, max_steps: usize, }; pub const Error = error{ InvalidPattern, PatternLimitExceeded, InvalidUtf8, } || Allocator.Error; const Pair = struct { left: usize, right: usize }; const Repeat = struct { child: usize, min: usize, max: ?usize }; const Atom = struct { node: usize, quantifiable: bool = true }; const Node = union(enum) { empty, literal: u21, any, class: usize, concat: Pair, alternate: Pair, repeat: Repeat, assert_start, assert_end, }; const Range = struct { first: u21, last: u21 }; fn isEcmascriptWhitespace(codepoint: u21) bool { return switch (codepoint) { 0x0009...0x000D, 0x0020, 0x00A0, 0x1680, 0x2000...0x200A, 0x2028, 0x2029, 0x202F, 0x205F, 0x3000, 0xFEFF, => true, else => false, }; } const CharacterClass = struct { range_start: usize, range_len: usize, negated: bool = false, ascii_digit: bool = false, ascii_word: bool = false, ecmascript_space: bool = false, not_ecmascript_space: bool = false, unicode_letter: bool = false, fn matches(self: CharacterClass, ranges: []const Range, codepoint: u21) bool { var matched = self.unicode_letter and unicode_letter.contains(codepoint); matched = matched or (self.ascii_digit and codepoint >= '0' and codepoint <= '9'); matched = matched or (self.ascii_word and ((codepoint >= 'a' and codepoint <= 'z') or (codepoint >= 'A' and codepoint <= 'Z') or (codepoint >= '0' and codepoint <= '9') or codepoint == '_')); const is_space = isEcmascriptWhitespace(codepoint); matched = matched or (self.ecmascript_space and is_space); matched = matched or (self.not_ecmascript_space and !is_space); for (ranges[self.range_start..][0..self.range_len]) |range| { if (codepoint >= range.first and codepoint <= range.last) { matched = true; break; } } return if (self.negated) !matched else matched; } }; const Parser = struct { alloc: Allocator, source: []const u8, limits: Limits, index: usize = 0, group_depth: usize = 0, nodes: std.ArrayList(Node) = .empty, classes: std.ArrayList(CharacterClass) = .empty, ranges: std.ArrayList(Range) = .empty, fn deinit(self: *Parser) void { self.nodes.deinit(self.alloc); self.classes.deinit(self.alloc); self.ranges.deinit(self.alloc); } fn parse(self: *Parser) Error!usize { const root = try self.parseAlternation(null); if (self.index != self.source.len) return error.InvalidPattern; return root; } fn parseAlternation(self: *Parser, terminator: ?u8) Error!usize { var left = try self.parseSequence(terminator); while (self.peekByte() == '|') { self.index += 1; const right = try self.parseSequence(terminator); left = try self.addNode(.{ .alternate = .{ .left = left, .right = right } }); } return left; } fn parseSequence(self: *Parser, terminator: ?u8) Error!usize { var result: ?usize = null; while (self.index < self.source.len) { const byte = self.source[self.index]; if (byte == '|' or (terminator != null and byte == terminator.?)) break; const item = try self.parseRepetition(); result = if (result) |left| try self.addNode(.{ .concat = .{ .left = left, .right = item } }) else item; } return result orelse try self.addNode(.empty); } fn parseRepetition(self: *Parser) Error!usize { const atom = try self.parseAtom(); if (self.index >= self.source.len) return atom.node; if (!atom.quantifiable) switch (self.source[self.index]) { '*', '+', '?', '{' => return error.InvalidPattern, else => {}, }; var min: usize = undefined; var max: ?usize = undefined; switch (self.source[self.index]) { '*' => { self.index += 1; min = 0; max = null; }, '+' => { self.index += 1; min = 1; max = null; }, '?' => { self.index += 1; min = 0; max = 1; }, '{' => { self.index += 1; min = try self.parseCount(); if (self.consumeByte('}')) { max = min; } else { if (!self.consumeByte(',')) return error.InvalidPattern; max = if (self.consumeByte('}')) null else blk: { const upper = try self.parseCount(); if (!self.consumeByte('}')) return error.InvalidPattern; break :blk upper; }; } }, else => return atom.node, } if (max) |upper| if (upper < min) return error.InvalidPattern; if (min > self.limits.max_repeat or (max orelse min) > self.limits.max_repeat) { return error.PatternLimitExceeded; } _ = self.consumeByte('?'); // Lazy quantifiers have identical acceptance semantics. if (self.index < self.source.len) switch (self.source[self.index]) { '*', '+', '?', '{' => return error.InvalidPattern, else => {}, }; return self.addNode(.{ .repeat = .{ .child = atom.node, .min = min, .max = max } }); } fn parseAtom(self: *Parser) Error!Atom { if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; switch (byte) { '^' => { self.index += 1; return .{ .node = try self.addNode(.assert_start), .quantifiable = false }; }, '$' => { self.index += 1; return .{ .node = try self.addNode(.assert_end), .quantifiable = false }; }, '.' => { self.index += 1; return .{ .node = try self.addNode(.any) }; }, '(' => { self.index += 1; if (self.peekByte() == '?') return error.InvalidPattern; if (self.group_depth >= self.limits.max_depth) { return error.PatternLimitExceeded; } self.group_depth += 1; defer self.group_depth -= 1; const nested = try self.parseAlternation(')'); if (!self.consumeByte(')')) return error.InvalidPattern; return .{ .node = nested }; }, '[' => return .{ .node = try self.parseCharacterClass() }, '\\' => return .{ .node = try self.parseEscapeNode() }, ')', ']', '}', '|', '*', '+', '?', '{' => return error.InvalidPattern, else => { const codepoint = try self.nextCodepoint(); return .{ .node = try self.addNode(.{ .literal = codepoint }) }; }, } } fn parseEscapeNode(self: *Parser) Error!usize { self.index += 1; if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; self.index += 1; switch (byte) { 'd', 'D', 'w', 'W', 's', 'S' => { var class = CharacterClass{ .range_start = self.ranges.items.len, .range_len = 0, .negated = std.ascii.isUpper(byte), }; switch (std.ascii.toLower(byte)) { 'd' => class.ascii_digit = true, 'w' => class.ascii_word = true, 's' => class.ecmascript_space = true, else => unreachable, } return self.addClassNode(class); }, 'p', 'P' => { if (!self.consumeByte('{')) return error.InvalidPattern; const start = self.index; while (self.index < self.source.len and self.source[self.index] != '}') : (self.index += 1) {} if (!self.consumeByte('}')) return error.InvalidPattern; const property = self.source[start .. self.index - 1]; if (!std.mem.eql(u8, property, "Letter") and !std.mem.eql(u8, property, "L")) { return error.InvalidPattern; } return self.addClassNode(.{ .range_start = self.ranges.items.len, .range_len = 0, .negated = byte == 'P', .unicode_letter = true, }); }, 'n' => return self.addNode(.{ .literal = '\n' }), 'r' => return self.addNode(.{ .literal = '\r' }), 't' => return self.addNode(.{ .literal = '\t' }), 'f' => return self.addNode(.{ .literal = 0x0C }), 'v' => return self.addNode(.{ .literal = 0x0B }), 'x' => return self.addNode(.{ .literal = try self.parseHexCodepoint(2) }), 'u' => { if (self.consumeByte('{')) { const codepoint = try self.parseVariableHexCodepoint(); if (!self.consumeByte('}')) return error.InvalidPattern; return self.addNode(.{ .literal = codepoint }); } return self.addNode(.{ .literal = try self.parseHexCodepoint(4) }); }, '0' => { if (self.peekByte()) |next| if (std.ascii.isDigit(next)) { return error.InvalidPattern; }; return self.addNode(.{ .literal = 0 }); }, '1'...'9', 'b', 'B', 'c', 'k' => return error.InvalidPattern, else => { if (!isIdentityEscape(byte, false)) return error.InvalidPattern; return self.addNode(.{ .literal = byte }); }, } } fn parseCharacterClass(self: *Parser) Error!usize { self.index += 1; var class = CharacterClass{ .range_start = self.ranges.items.len, .range_len = 0, .negated = self.consumeByte('^'), }; var first = true; while (self.index < self.source.len) { if (self.source[self.index] == ']' and !first) { self.index += 1; class.range_len = self.ranges.items.len - class.range_start; return self.addClassNode(class); } const left = try self.parseClassAtom(&class); first = false; if (left == null) { if (self.peekByte() == '-' and self.index + 1 < self.source.len and self.source[self.index + 1] != ']') { return error.InvalidPattern; } continue; } if (self.peekByte() == '-' and self.index + 1 < self.source.len and self.source[self.index + 1] != ']') { self.index += 1; const right = (try self.parseClassAtom(&class)) orelse return error.InvalidPattern; if (right < left.?) return error.InvalidPattern; try self.ranges.append(self.alloc, .{ .first = left.?, .last = right }); } else { try self.ranges.append(self.alloc, .{ .first = left.?, .last = left.? }); } if (self.ranges.items.len - class.range_start > self.limits.max_states) { return error.PatternLimitExceeded; } } return error.InvalidPattern; } fn parseClassAtom(self: *Parser, class: *CharacterClass) Error!?u21 { if (self.index >= self.source.len) return error.InvalidPattern; if (self.source[self.index] != '\\') return try self.nextCodepoint(); self.index += 1; if (self.index >= self.source.len) return error.InvalidPattern; const byte = self.source[self.index]; self.index += 1; switch (byte) { 'd' => { class.ascii_digit = true; return null; }, 'w' => { class.ascii_word = true; return null; }, 's' => { class.ecmascript_space = true; return null; }, 'S' => { class.not_ecmascript_space = true; return null; }, 'D', 'W', 'p', 'P', 'b', 'B', '1'...'9', 'c', 'k' => return error.InvalidPattern, '0' => { if (self.peekByte()) |next| if (std.ascii.isDigit(next)) { return error.InvalidPattern; }; return 0; }, 'n' => return '\n', 'r' => return '\r', 't' => return '\t', 'f' => return 0x0C, 'v' => return 0x0B, 'x' => return try self.parseHexCodepoint(2), 'u' => return try self.parseHexCodepoint(4), else => { if (!isIdentityEscape(byte, true)) return error.InvalidPattern; return @as(u21, byte); }, } } fn addClassNode(self: *Parser, class: CharacterClass) Error!usize { if (self.classes.items.len >= self.limits.max_states) return error.PatternLimitExceeded; const index = self.classes.items.len; try self.classes.append(self.alloc, class); return self.addNode(.{ .class = index }); } fn addNode(self: *Parser, node: Node) Error!usize { if (self.nodes.items.len >= self.limits.max_states) return error.PatternLimitExceeded; const index = self.nodes.items.len; try self.nodes.append(self.alloc, node); return index; } fn parseCount(self: *Parser) Error!usize { const start = self.index; while (self.index < self.source.len and std.ascii.isDigit(self.source[self.index])) : (self.index += 1) {} if (self.index == start) return error.InvalidPattern; return std.fmt.parseInt(usize, self.source[start..self.index], 10) catch return error.PatternLimitExceeded; } fn parseHexCodepoint(self: *Parser, digits: usize) Error!u21 { if (digits > self.source.len - self.index) return error.InvalidPattern; const value = std.fmt.parseInt(u21, self.source[self.index..][0..digits], 16) catch return error.InvalidPattern; self.index += digits; if (!std.unicode.utf8ValidCodepoint(value)) return error.InvalidPattern; return value; } fn parseVariableHexCodepoint(self: *Parser) Error!u21 { const start = self.index; while (self.index < self.source.len and self.source[self.index] != '}') : (self.index += 1) {} if (self.index == start or self.index - start > 6) return error.InvalidPattern; const value = std.fmt.parseInt(u21, self.source[start..self.index], 16) catch return error.InvalidPattern; if (!std.unicode.utf8ValidCodepoint(value)) return error.InvalidPattern; return value; } fn nextCodepoint(self: *Parser) Error!u21 { const width = std.unicode.utf8ByteSequenceLength(self.source[self.index]) catch return error.InvalidUtf8; if (width > self.source.len - self.index) return error.InvalidUtf8; const codepoint = std.unicode.utf8Decode(self.source[self.index..][0..width]) catch return error.InvalidUtf8; self.index += width; return codepoint; } fn peekByte(self: *const Parser) ?u8 { return if (self.index < self.source.len) self.source[self.index] else null; } fn consumeByte(self: *Parser, expected: u8) bool { if (self.peekByte() != expected) return false; self.index += 1; return true; } }; fn isIdentityEscape(byte: u8, in_class: bool) bool { return switch (byte) { '^', '$', '\\', '.', '*', '+', '?', '(', ')', '[', ']', '{', '}', '|', '/' => true, '-' => in_class, else => false, }; } const Op = enum { epsilon, literal, any, class, split, assert_start, assert_end, accept }; const Instruction = struct { op: Op, out: usize = invalid_index, out1: usize = invalid_index, value: usize = 0, }; const Patch = struct { instruction: usize, second: bool = false }; const Fragment = struct { start: usize, outs: std.ArrayList(Patch) }; const Compiler = struct { alloc: Allocator, nodes: []const Node, limits: Limits, instructions: std.ArrayList(Instruction) = .empty, fn deinit(self: *Compiler) void { self.instructions.deinit(self.alloc); } fn compile(self: *Compiler, node_index: usize) Error!usize { var fragment = try self.compileNode(node_index); defer fragment.outs.deinit(self.alloc); const accept = try self.addInstruction(.{ .op = .accept }); self.patch(fragment.outs.items, accept); return fragment.start; } fn compileNode(self: *Compiler, node_index: usize) Error!Fragment { return switch (self.nodes[node_index]) { .empty => self.single(.{ .op = .epsilon }, false), .literal => |value| self.single(.{ .op = .literal, .value = value }, false), .any => self.single(.{ .op = .any }, false), .class => |value| self.single(.{ .op = .class, .value = value }, false), .assert_start => self.single(.{ .op = .assert_start }, false), .assert_end => self.single(.{ .op = .assert_end }, false), .concat => |pair| self.compileConcat(pair), .alternate => |pair| self.compileAlternate(pair), .repeat => |repeat| self.compileRepeat(repeat), }; } fn compileConcat(self: *Compiler, pair: Pair) Error!Fragment { var left = try self.compileNode(pair.left); errdefer left.outs.deinit(self.alloc); var right = try self.compileNode(pair.right); errdefer right.outs.deinit(self.alloc); const left_owned = left; const right_owned = right; left.outs = .empty; right.outs = .empty; return self.concat(left_owned, right_owned); } fn compileAlternate(self: *Compiler, pair: Pair) Error!Fragment { var left = try self.compileNode(pair.left); errdefer left.outs.deinit(self.alloc);