Something went wrong. Try again.
A Zig library that reads git repositories without running git, with log, show and diff output byte-identical to git's.
Something went wrong. Try again.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! POSIX regular expressions, basic and extended, as glibc's `regcomp`//! and `regexec` read and match them for git: `git config --get-regexp`//! and its value patterns, `:/<text>` and `^{/<text>}`, `git log`'s//! `--grep`, `--author` and `--committer`, and the function lines of diff//! drivers. Most of them ask only whether a pattern matches somewhere in//! a string (`Regex.matches`); a diff driver's `xfuncname` also asks//! where, and where its first group matched (`Regex.exec`). It is small//! enough to write here rather than bring in a regex library whose//! dialect is not POSIX's.//!//! It takes alternation, grouping, the repetitions `*`, `+`, `?` and//! `{m,n}`, `.`, `^`, `$`, and bracket expressions with ranges, negation//! and the POSIX classes. Bytes are bytes, as in the C locale git runs in//! when nothing says otherwise. glibc's corners were found by asking `git//! config --get-regexp` and `git log --grep`://!//! - **Extended** (`Syntax.extended`): a `)` with no `(` is itself; a `{`//! that does not make a whole bound is an error, as is a repetition with//! nothing before it to repeat, or after `(`, `|`, `^` or `$`; a//! repetition may follow another (`a**`, `a+*`, `x{1}{2}`).//! - **Basic** (`Syntax.basic`): `\(`, `\)`, `\{`, `\}` and `\|` are the//! operators, with glibc's `\+` and `\?`; `*` is itself at the start of//! the pattern, after `\(` or `\|`, or after an anchoring `^`; `^` anchors//! only at the start of the pattern or after `\(` or `\|`, and `$` only//! at the end or before `\)` or `\|`; and a `*` or `\{` after another//! repetition is an error, where a `\+` or `\?` is not.//! - **GNU's escapes** (`Options.gnu`), which glibc gives `--grep` its//! meaning for: `\w` and `\W` (a word character, alphanumeric or `_`,//! and anything else), `\s` and `\S`, `\b` and `\B` (a word boundary and//! anywhere else), `\<` and `\>` (the start and end of a word), and//! `\`` and `\'` (the start and end of the whole text). Without it they//! are refused by name, as `git config` once needed.//! - **Back references** are refused by name; one to a group that does not//! exist is an error, as glibc makes it.//! - **Case** is ignored for ASCII letters alone with//! `Options.ignore_case`.//! - **Lines**: without `Options.newline` a `.` matches a line feed and `^`//! and `$` match only at the ends of the whole text, which is how git//! compiles the patterns `config` and `:/<text>` use; with it, as//! `REG_NEWLINE`, `.` and a negated bracket expression do not match a//! line feed and `^` and `$` match at every line's ends.//!//! What is wrong with a malformed pattern is named in glibc's words//! (`Problem.message`), as git repeats them.//!//! The pattern is compiled to a nondeterministic automaton and run over//! the text with every live state at once, so no pattern can make it take//! longer than the pattern's size times the text's to say whether, and//! where, it matches. A match's groups are then found by trying the ways//! through it in glibc's order of preference, each state at most once,//! which costs at most the pattern's size times the match's length (times//! that length again for each repetition whose iterations could be//! empty).
const std = @import("std");const Allocator = std.mem.Allocator;
/// Why a pattern was not compiled.pub const Error = error{ /// Malformed: what `regcomp` refuses. InvalidPattern, /// Valid, but uses something this does not implement. Unsupported,} || Allocator.Error;
/// Which of POSIX's two syntaxes a pattern is read in.pub const Syntax = enum { basic, extended };
/// How a pattern is read and matched.pub const Options = struct { syntax: Syntax = .extended, /// Match ASCII letters without regard to case, as `REG_ICASE`. ignore_case: bool = false, /// `REG_NEWLINE`: lines are matched apart. newline: bool = false, /// GNU's escapes, `\w`, `\b` and the rest. gnu: bool = false, /// `.` does not match a NUL, as glibc's `.` was seen not to where git /// matches a pickaxe's pattern against contents that may hold one (a /// negated bracket expression and `\W` still match it). dot_excludes_nul: bool = false,};
/// What is wrong with a malformed pattern, as glibc's `regerror` names/// it.pub const Problem = enum { bad_pattern, collation, class_name, trailing_backslash, back_reference, bracket, parenthesis, brace, bad_bound, range_end, bad_repetition, too_big,
/// glibc's words for it. pub fn message(p: Problem) []const u8 { return switch (p) { .bad_pattern => "Invalid regular expression", .collation => "Invalid collation character", .class_name => "Invalid character class name", .trailing_backslash => "Trailing backslash", .back_reference => "Invalid back reference", .bracket => "Unmatched [, [^, [:, [., or [=", .parenthesis => "Unmatched ( or \\(", .brace => "Unmatched \\{", .bad_bound => "Invalid content of \\{\\}", .range_end => "Invalid range end", .bad_repetition => "Invalid preceding regular expression", .too_big => "Regular expression too big", }; }};
/// What went wrong compiling a pattern: what was malformed, or what was/// not supported.pub const Failure = struct { problem: Problem = .bad_pattern, /// The construct refused, when compiling fails with `Unsupported`. unsupported: []const u8 = "",};
const Assertion = enum { begin, end, text_begin, text_end, word_boundary, not_word_boundary, word_start, word_end,};
const Inst = union(enum) { /// One byte in the set. set: *const [256]bool, /// Either of two places, the first preferred. split: [2]u32, jump: u32, assert: Assertion, /// Records the position in a group's slot: `2n` where group `n` /// begins, `2n + 1` where it ends. save: u32, /// Records the position in a register, where an iteration that must /// not be empty begins. mark: u32, /// Fails unless the position has moved on since the register's mark. check: u32, match,};
/// A compiled pattern.pub const Regex = struct { arena: std.heap.ArenaAllocator, program: []const Inst, newline: bool = false, /// How many parenthesized subexpressions the pattern has. groups: u32 = 0, /// How many registers its repetitions mark. marks: u32 = 0, /// Whether the first group lies inside a repetition that may iterate /// more than once, where glibc's choice of iteration was not matched. first_group_repeated: bool = false, /// `REG_NOTBOL`: the start of the text is not the start of a line, /// so `^` does not match there; set only by `search`. not_bol: bool = false,
/// Compiles `pattern` as an extended regular expression without GNU's /// escapes, as `git config` and message searches do. On /// `Unsupported`, `what` is set to the construct refused. pub fn compile(gpa: Allocator, pattern: []const u8, what: ?*[]const u8) Error!Regex { var failure: Failure = .{}; return compileWith(gpa, pattern, .{}, &failure) catch |err| { if (err == error.Unsupported) if (what) |w| { w.* = failure.unsupported; }; return err; }; }
/// Compiles `pattern` as `options` say; `failure`, when given, says /// what was wrong with one that does not compile. pub fn compileWith(gpa: Allocator, pattern: []const u8, options: Options, failure: ?*Failure) Error!Regex { var arena: std.heap.ArenaAllocator = .init(gpa); errdefer arena.deinit(); var c: Compiler = .{ .a = arena.allocator(), .pattern = pattern, .options = options }; const node = c.whole() catch |err| { if (failure) |f| f.* = .{ .problem = c.problem, .unsupported = c.unsupported }; return err; }; if (size(node) > max_program) { if (failure) |f| f.* = .{ .problem = .too_big, .unsupported = "repetitions that large" }; return error.Unsupported; } var e: Emitter = .{ .a = c.a }; try e.emit(node); try e.append(.match); return .{ .arena = arena, .program = e.program.items, .newline = options.newline, .groups = c.groups, .marks = e.marks, .first_group_repeated = groupRepeated(node, 1, false) orelse false, }; }
/// Frees the pattern. pub fn deinit(r: *Regex) void { r.arena.deinit(); }
/// Whether the pattern matches anywhere in `text`. pub fn matches(r: *const Regex, gpa: Allocator, text: []const u8) Allocator.Error!bool { const n = r.program.len; var current = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n); defer current.deinit(gpa); var next = try std.DynamicBitSetUnmanaged.initEmpty(gpa, n); defer next.deinit(gpa); var stack: std.ArrayList(u32) = .empty; defer stack.deinit(gpa); var i: usize = 0; while (true) : (i += 1) { // A match may start anywhere. if (try r.addState(gpa, ¤t, &stack, 0, text, i)) return true; if (i == text.len) return false; next.unsetAll(); var it = current.iterator(.{}); while (it.next()) |pc| switch (r.program[pc]) { .set => |s| if (s[text[i]]) { if (try r.addState(gpa, &next, &stack, @intCast(pc + 1), text, i + 1)) return true; }, else => {}, }; std.mem.swap(std.DynamicBitSetUnmanaged, ¤t, &next); } }
fn holds(r: *const Regex, a: Assertion, text: []const u8, pos: usize) bool { const before = pos > 0 and isWord(text[pos - 1]); const after = pos < text.len and isWord(text[pos]); return switch (a) { .begin => (pos == 0 and !r.not_bol) or (pos != 0 and r.newline and text[pos - 1] == '\n'), .end => pos == text.len or (r.newline and text[pos] == '\n'), .text_begin => pos == 0, .text_end => pos == text.len, .word_boundary => before != after, .not_word_boundary => before == after, .word_start => !before and after, .word_end => before and !after, }; }
/// Adds the state `pc` and everything reachable from it without /// reading a byte; true if that reaches a match. fn addState(r: *const Regex, gpa: Allocator, set: *std.DynamicBitSetUnmanaged, stack: *std.ArrayList(u32), start: u32, text: []const u8, pos: usize) Allocator.Error!bool { stack.clearRetainingCapacity(); try stack.append(gpa, start); while (stack.pop()) |pc| { if (set.isSet(pc)) continue; set.set(pc); switch (r.program[pc]) { .set => {}, .split => |targets| { try stack.append(gpa, targets[1]); try stack.append(gpa, targets[0]); }, .jump => |t| try stack.append(gpa, t), .assert => |a| if (r.holds(a, text, pos)) try stack.append(gpa, pc + 1), // Iterations that are empty add nothing to what matches. .save, .mark, .check => try stack.append(gpa, pc + 1), .match => return true, } } return false; }
/// Where the pattern matches in `text`: the match that begins /// earliest and, of those, the longest, as POSIX chooses. With /// `groups`, `groups[i]` is where group `i + 1` matched within it, or /// null if it took no part; groups past the pattern's are null. /// /// POSIX says each group should then match the longest it can, but /// glibc, and so git, does not: it takes the groups of the first way /// through the pattern that ends where the match ends, trying /// alternatives in the order written and repetitions greedily, one /// more iteration before one fewer; an unbounded repetition (`*`, /// `+`, `{m,}`) takes an empty iteration only where one is required /// or none came before it, a bounded one wherever it can. That was /// found by comparing the two over thousands of random patterns and /// texts. pub fn exec(r: *const Regex, gpa: Allocator, text: []const u8, groups: []?Span) Allocator.Error!?Span { for (groups) |*g| g.* = null; const whole = try r.find(gpa, text) orelse return null; if (groups.len == 0 or r.groups == 0) return whole; var b: Backtracker = try .init(gpa, r, text, whole); defer b.deinit(); const found = try b.run(); std.debug.assert(found); for (groups, 0..) |*g, i| { if (i >= r.groups) break; const start = b.slots[2 * (i + 1)]; const end = b.slots[2 * (i + 1) + 1]; if (start != no_position and end != no_position) g.* = .{ .start = start, .end = end }; } return whole; }
/// The leftmost-longest match in `text`, as `exec` finds it without /// groups; with `not_bol`, as `REG_NOTBOL` asks, `^` does not match at /// the start of `text` (though `\``, and the word assertions, which /// see nothing before it, still do). pub fn search(r: *const Regex, gpa: Allocator, text: []const u8, not_bol: bool) Allocator.Error!?Span { var copy = r.*; copy.not_bol = not_bol; return copy.find(gpa, text); }
/// The leftmost-longest match: every live state followed at once, /// each with the position its match began, keeping the earliest /// beginning for each state. fn find(r: *const Regex, gpa: Allocator, text: []const u8) Allocator.Error!?Span { const n = r.program.len; var current: Threads = try .init(gpa, n); defer current.deinit(gpa); var next: Threads = try .init(gpa, n); defer next.deinit(gpa); var stack: std.ArrayList(u32) = .empty; defer stack.deinit(gpa); var best: ?Span = null; var i: usize = 0; while (true) : (i += 1) { // A match may begin anywhere until one has been found; the // threads are kept in the order their matches began. if (best == null) try r.addThread(gpa, ¤t, &stack, 0, i, text, i, &best); if (i == text.len or (best != null and current.list.items.len == 0)) break; next.clear(); for (current.list.items) |t| switch (r.program[t.pc]) { .set => |s| if (s[text[i]]) { if (best) |bst| if (t.start > bst.start) continue; try r.addThread(gpa, &next, &stack, t.pc + 1, t.start, text, i + 1, &best); }, else => {}, }; std.mem.swap(Threads, ¤t, &next); } return best; }
fn addThread(r: *const Regex, gpa: Allocator, threads: *Threads, stack: *std.ArrayList(u32), pc0: u32, start: usize, text: []const u8, pos: usize, best: *?Span) Allocator.Error!void { stack.clearRetainingCapacity(); try stack.append(gpa, pc0); while (stack.pop()) |pc| { if (threads.member.isSet(pc)) continue; threads.member.set(pc); switch (r.program[pc]) { .set => try threads.list.append(gpa, .{ .pc = pc, .start = start }), .split => |targets| { try stack.append(gpa, targets[1]); try stack.append(gpa, targets[0]); }, .jump => |t| try stack.append(gpa, t), .assert => |a| if (r.holds(a, text, pos)) try stack.append(gpa, pc + 1), .save, .mark, .check => try stack.append(gpa, pc + 1), .match => { if (best.*) |b| { if (start < b.start or (start == b.start and pos > b.end)) best.* = .{ .start = start, .end = pos }; } else best.* = .{ .start = start, .end = pos }; }, } } }};
/// Where a match, or a group within one, lies in the text: bytes/// `start..end`.pub const Span = struct { start: usize, end: usize,};
const no_position = std.math.maxInt(usize);
/// States waiting to read the next byte, in the order their matches/// began.const Threads = struct { list: std.ArrayList(Thread) = .empty, member: std.DynamicBitSetUnmanaged,
const Thread = struct { pc: u32, start: usize };
fn init(gpa: Allocator, n: usize) Allocator.Error!Threads { return .{ .member = try .initEmpty(gpa, n) }; }
fn deinit(t: *Threads, gpa: Allocator) void { t.list.deinit(gpa); t.member.deinit(gpa); }
fn clear(t: *Threads) void { t.list.clearRetainingCapacity(); t.member.unsetAll(); }};
/// Finds the groups of a match already known to lie at `whole`: the first/// way through the program, in order of preference, that reaches the end/// at `whole.end`. A state that once failed to get there fails again, so/// each is tried once and no pattern makes this take exponential time;/// the registers of repetitions that must not be empty are part of the/// state.const Backtracker = struct { gpa: Allocator, r: *const Regex, text: []const u8, end: usize, start: usize, slots: []usize, marks: []usize, stack: std.ArrayList(Frame) = .empty, /// States tried, without marks: `pc * (len + 1) + offset`. seen: std.AutoHashMapUnmanaged(u64, void) = .empty, /// States tried, with marks. seen_marked: std.StringHashMapUnmanaged(void) = .empty, keys: std.heap.ArenaAllocator,
const Frame = union(enum) { try_state: struct { pc: u32, pos: usize }, restore_slot: struct { slot: u32, value: usize }, restore_mark: struct { mark: u32, value: usize }, };
fn init(gpa: Allocator, r: *const Regex, text: []const u8, whole: Span) Allocator.Error!Backtracker { const slots = try gpa.alloc(usize, 2 * (@as(usize, r.groups) + 1)); errdefer gpa.free(slots); @memset(slots, no_position); const marks = try gpa.alloc(usize, r.marks); @memset(marks, no_position); return .{ .gpa = gpa, .r = r, .text = text, .start = whole.start, .end = whole.end, .slots = slots, .marks = marks, .keys = .init(gpa) }; }
fn deinit(b: *Backtracker) void { b.gpa.free(b.slots); b.gpa.free(b.marks); b.stack.deinit(b.gpa); b.seen.deinit(b.gpa); b.seen_marked.deinit(b.gpa); b.keys.deinit(); }
/// Whether the state was tried before; marks it tried. fn tried(b: *Backtracker, pc: u32, pos: usize) Allocator.Error!bool { const width: u64 = b.end - b.start + 1; const flat: u64 = @as(u64, pc) * width + (pos - b.start); if (b.marks.len == 0) return (try b.seen.getOrPut(b.gpa, flat)).found_existing; const ka = b.keys.allocator(); const key = try ka.alloc(u8, 8 * (1 + b.marks.len)); std.mem.writeInt(u64, key[0..8], flat, .little); for (b.marks, 0..) |m, k| std.mem.writeInt(u64, key[8 * (k + 1) ..][0..8], m, .little); const gop = try b.seen_marked.getOrPut(b.gpa, key); if (gop.found_existing) ka.free(key); return gop.found_existing; }
fn run(b: *Backtracker) Allocator.Error!bool { const program = b.r.program; try b.stack.append(b.gpa, .{ .try_state = .{ .pc = 0, .pos = b.start } }); while (b.stack.pop()) |frame| switch (frame) { .restore_slot => |x| b.slots[x.slot] = x.value, .restore_mark => |x| b.marks[x.mark] = x.value, .try_state => |st| { var pc = st.pc; var pos = st.pos; while (true) { if (pos > b.end) break; if (try b.tried(pc, pos)) break; switch (program[pc]) { .set => |s| { if (pos < b.end and s[b.text[pos]]) { pc += 1; pos += 1; } else break; }, .split => |targets| { try b.stack.append(b.gpa, .{ .try_state = .{ .pc = targets[1], .pos = pos } }); pc = targets[0]; }, .jump => |t| pc = t, .assert => |a| { if (b.r.holds(a, b.text, pos)) pc += 1 else break; }, .save => |slot| { try b.stack.append(b.gpa, .{ .restore_slot = .{ .slot = slot, .value = b.slots[slot] } }); b.slots[slot] = pos; pc += 1; }, .mark => |m| { try b.stack.append(b.gpa, .{ .restore_mark = .{ .mark = m, .value = b.marks[m] } }); b.marks[m] = pos; pc += 1; }, .check => |m| { if (b.marks[m] == pos) break; pc += 1; }, .match => { if (pos == b.end) return true; break; }, } } }, }; return false; }};
fn isWord(c: u8) bool { return std.ascii.isAlphanumeric(c) or c == '_';}
const Node = union(enum) { empty, set: *const [256]bool, assert: Assertion, concat: []const Node, alternate: []const Node, repeat: struct { node: *const Node, min: u32, max: ?u32 }, /// A parenthesized subexpression, numbered from 1 as POSIX counts /// them. group: struct { index: u32, node: *const Node },};
/// The most copies a bounded repetition may make, as glibc's `RE_DUP_MAX`.const max_repeat = 0x7fff;
/// The most instructions a compiled pattern may have, past which one is/// refused rather than allowed to take unbounded memory.const max_program = 1 << 20;
/// One piece of a pattern, with what the syntax makes of it.const Token = union(enum) { literal: u8, any, bracket, open, close, bar, star, plus, question, /// `{` or `\{`, its bound read. bound: Bound, begin, end, /// One of GNU's escapes. escape: u8, back_reference: u8,};
const Bound = struct { min: u32, max: ?u32 };
const Compiler = struct { a: Allocator, pattern: []const u8, options: Options, pos: usize = 0, unsupported: []const u8 = "", problem: Problem = .bad_pattern, depth: u32 = 0, groups: u32 = 0, /// Groups opened and not yet closed. open_groups: u32 = 0,
fn fail(c: *Compiler, p: Problem) error{InvalidPattern} { c.problem = p; return error.InvalidPattern; }
fn basic(c: *const Compiler) bool { return c.options.syntax == .basic; }
fn whole(c: *Compiler) Error!Node { // glibc says a lone `[` at the very end is no pattern at all // rather than an unmatched bracket. if (std.mem.eql(u8, c.pattern, "[")) return c.fail(.bad_pattern); const node = try c.alternation(); if (c.pos != c.pattern.len) { // Only an unmatched `\)` stops a basic pattern early. return c.fail(.parenthesis); } return node; }
/// Whether the pattern, at `at`, begins a closing group or an /// alternative, or ends: where a basic `$` anchors. fn endsHere(c: *const Compiler, at: usize) bool { if (at == c.pattern.len) return true; if (c.basic()) { if (at + 1 < c.pattern.len and c.pattern[at] == '\\' and (c.pattern[at + 1] == ')' or c.pattern[at + 1] == '|')) return true; } return false; }
/// Reads the next token; `start` says whether it begins the pattern, /// a group or an alternative, where a basic `*` and `^` mean /// something else. fn token(c: *Compiler, start: bool, after_anchor: bool) Error!?Token { if (c.pos >= c.pattern.len) return null; const ch = c.pattern[c.pos]; if (ch == '\\') { if (c.pos + 1 >= c.pattern.len) return c.fail(.trailing_backslash); const e = c.pattern[c.pos + 1]; c.pos += 2; if (c.basic()) switch (e) { '(' => return .open, ')' => return .close, '|' => return .bar, '{' => return .{ .bound = try c.bound(true) }, '}' => return .{ .literal = '}' }, '+' => return if (start) .{ .literal = '+' } else .plus, '?' => return if (start) .{ .literal = '?' } else .question, else => {}, }; if (e >= '1' and e <= '9') return .{ .back_reference = e }; if (std.mem.findScalar(u8, "wWsSbB<>`'", e) != null) { if (!c.options.gnu) { c.unsupported = c.pattern[c.pos - 2 .. c.pos]; return error.Unsupported; } return .{ .escape = e }; } return .{ .literal = e }; } c.pos += 1; switch (ch) { '.' => return .any, '[' => return .bracket, '*' => return if (c.basic() and (start or after_anchor)) .{ .literal = '*' } else .star, '^' => return if (!c.basic() or start) .begin else .{ .literal = '^' }, '$' => return if (!c.basic() or c.endsHere(c.pos)) .end else .{ .literal = '$' }, else => {}, } if (!c.basic()) switch (ch) { '(' => return .open, ')' => return if (c.open_groups > 0) .close else .{ .literal = ')' }, '|' => return .bar, '+' => return .plus, '?' => return .question, '{' => { // A bound with nothing before it to repeat is wrong // whatever follows. if (start or after_anchor) return c.fail(.bad_repetition); return .{ .bound = try c.bound(false) }; }, else => {}, }; return .{ .literal = ch }; }
/// Looks at the next token without taking it. fn peekToken(c: *Compiler, start: bool, after_anchor: bool) Error!?Token { const saved = c.pos; defer c.pos = saved; return c.token(start, after_anchor); }
fn alternation(c: *Compiler) Error!Node { c.depth += 1; defer c.depth -= 1; if (c.depth > 200) return c.fail(.too_big); var branches: std.ArrayList(Node) = .empty; try branches.append(c.a, try c.concatenation()); while (true) { const t = try c.peekToken(false, false) orelse break; if (t != .bar) break; _ = try c.token(false, false); try branches.append(c.a, try c.concatenation()); } if (branches.items.len == 1) return branches.items[0]; return .{ .alternate = branches.items }; }
fn concatenation(c: *Compiler) Error!Node { var items: std.ArrayList(Node) = .empty; var start = true; var after_anchor = false; while (true) { const t = try c.peekToken(start, after_anchor) orelse break; if (t == .bar or t == .close) break; _ = try c.token(start, after_anchor); const one = try c.atom(t); const is_anchor = t == .begin or t == .end; try items.append(c.a, try c.repetitions(one, is_anchor)); start = false; after_anchor = t == .begin; } if (items.items.len == 0) return .empty; if (items.items.len == 1) return items.items[0]; return .{ .concat = items.items }; }
fn repetitions(c: *Compiler, node: Node, anchor: bool) Error!Node { var n = node; var repeated = false; while (true) { const t = try c.peekToken(false, false) orelse break; var min: u32 = 0; var max: ?u32 = null; switch (t) { .star => {}, .plus => min = 1, .question => max = 1, .bound => |b| { min = b.min; max = b.max; }, else => break, } if (anchor and !c.basic()) return c.fail(.bad_repetition); // A basic `*` or bound may not follow another repetition. if (c.basic() and repeated and (t == .star or t == .bound)) return c.fail(.bad_repetition); _ = try c.token(false, false); const inner = try c.a.create(Node); inner.* = n; n = .{ .repeat = .{ .node = inner, .min = min, .max = max } }; repeated = true; } return n; }
/// The bound after a `{` (or a basic `\{`): `m`, `m,`, `,n` or `m,n`, /// then `}` (or `\}`). fn bound(c: *Compiler, escaped: bool) Error!Bound { var i = c.pos; const given_min = c.number(&i); var max: ?u32 = given_min; if (i < c.pattern.len and c.pattern[i] == ',') { i += 1; max = c.number(&i); } else if (given_min == null) { if (i >= c.pattern.len) return c.fail(.brace); return c.fail(.bad_bound); } const min = given_min orelse 0; if (escaped) { if (i >= c.pattern.len or (i + 1 >= c.pattern.len and c.pattern[i] == '\\')) return c.fail(.brace); if (c.pattern[i] != '\\' or c.pattern[i + 1] != '}') return c.fail(.bad_bound); i += 2; } else { if (i >= c.pattern.len) return c.fail(.brace); if (c.pattern[i] != '}') return c.fail(.bad_bound); i += 1; } if (max) |m| if (m < min) return c.fail(.bad_bound); if (min > max_repeat or (max orelse 0) > max_repeat) return c.fail(.too_big); c.pos = i; return .{ .min = min, .max = max }; }
fn number(c: *const Compiler, i: *usize) ?u32 { const start = i.*; var n: u32 = 0; while (i.* < c.pattern.len and std.ascii.isDigit(c.pattern[i.*])) : (i.* += 1) { n = @min(n * 10 + (c.pattern[i.*] - '0'), 100_000); } return if (i.* == start) null else n; }
fn newSet(c: *Compiler) Allocator.Error!*[256]bool { const set = try c.a.create([256]bool); set.* = @splat(false); return set; }
/// Makes `set` match either case of each ASCII letter it matches, when /// case is ignored. fn fold(c: *const Compiler, set: *[256]bool) void { if (!c.options.ignore_case) return; for ('a'..'z' + 1) |l| { const u = l - 'a' + 'A'; if (set[l] or set[u]) { set[l] = true; set[u] = true; } } }
fn single(c: *Compiler, byte: u8) Allocator.Error!Node { const set = try c.newSet(); set[byte] = true; c.fold(set); return .{ .set = set }; }
fn atom(c: *Compiler, t: Token) Error!Node { switch (t) { .literal => |b| return c.single(b), .open => { c.groups += 1; const index = c.groups; c.open_groups += 1; const inner = try c.a.create(Node); inner.* = try c.alternation(); const close = try c.token(false, false); c.open_groups -= 1; if (close == null or close.? != .close) return c.fail(.parenthesis); return .{ .group = .{ .index = index, .node = inner } }; }, .close => return c.fail(.parenthesis), .any => { const set = try c.newSet(); set.* = @splat(true); if (c.options.newline) set['\n'] = false; if (c.options.dot_excludes_nul) set[0] = false; return .{ .set = set }; }, .begin => return .{ .assert = .begin }, .end => return .{ .assert = .end }, .bracket => return c.bracket(), // A repetition with nothing before it to repeat; a basic `*` // there is itself, and never comes here. .star, .plus, .question, .bound => return c.fail(.bad_repetition), .bar => unreachable, .escape => |e| switch (e) { 'w', 'W', 's', 'S' => { const set = try c.newSet(); for (0..256) |b| { const byte: u8 = @intCast(b); set[b] = switch (e) { 'w' => isWord(byte), 'W' => !isWord(byte), 's' => Class.space.matches(byte), else => !Class.space.matches(byte), }; } return .{ .set = set }; }, 'b' => return .{ .assert = .word_boundary }, 'B' => return .{ .assert = .not_word_boundary }, '<' => return .{ .assert = .word_start }, '>' => return .{ .assert = .word_end }, '`' => return .{ .assert = .text_begin }, else => return .{ .assert = .text_end }, }, .back_reference => |d| { if (d - '0' > c.groups) return c.fail(.back_reference); c.unsupported = "back references"; return error.Unsupported; }, } }
fn bracket(c: *Compiler) Error!Node { const set = try c.newSet(); var negated = false; if (c.pos < c.pattern.len and c.pattern[c.pos] == '^') { negated = true; c.pos += 1; } var first = true; while (true) : (first = false) { if (c.pos >= c.pattern.len) return c.fail(.bracket); const ch = c.pattern[c.pos]; if (ch == ']' and !first) { c.pos += 1; break; } var lo: u8 = ch; if (ch == '[' and c.pos + 1 < c.pattern.len and (c.pattern[c.pos + 1] == ':' or c.pattern[c.pos + 1] == '=' or c.pattern[c.pos + 1] == '.')) { const kind = c.pattern[c.pos + 1]; const close = std.mem.find(u8, c.pattern[c.pos + 2 ..], &.{ kind, ']' }) orelse return c.fail(.bracket); const name = c.pattern[c.pos + 2 ..][0..close]; c.pos += 2 + close + 2; if (kind == ':') { const class = std.meta.stringToEnum(Class, name) orelse return c.fail(.class_name); for (0..256) |b| if (class.matches(@intCast(b))) { set[b] = true; }; continue; } // `[=a=]` and `[.a.]` name one byte in the C locale. if (name.len != 1) return c.fail(.collation); lo = name[0]; } else c.pos += 1; if (c.pos + 1 < c.pattern.len and c.pattern[c.pos] == '-' and c.pattern[c.pos + 1] != ']') { var hi = c.pattern[c.pos + 1]; c.pos += 2; if (hi == '[' and c.pos < c.pattern.len and (c.pattern[c.pos] == '.' or c.pattern[c.pos] == '=')) { const kind = c.pattern[c.pos]; const close = std.mem.find(u8, c.pattern[c.pos + 1 ..], &.{ kind, ']' }) orelse return c.fail(.bracket); const name = c.pattern[c.pos + 1 ..][0..close]; if (name.len != 1) return c.fail(.collation); hi = name[0]; c.pos += 1 + close + 2; } if (hi < lo) return c.fail(.range_end); for (lo..@as(usize, hi) + 1) |b| set[b] = true; } else set[lo] = true; } c.fold(set); if (negated) { for (set) |*b| b.* = !b.*; if (c.options.newline) set['\n'] = false; } return .{ .set = set }; }};
const Class = enum { alnum, alpha, blank, cntrl, digit, graph, lower, print, punct, space, upper, xdigit,
fn matches(class: Class, c: u8) bool { return switch (class) { .alnum => std.ascii.isAlphanumeric(c), .alpha => std.ascii.isAlphabetic(c), .blank => c == ' ' or c == '\t', .cntrl => std.ascii.isControl(c), .digit => std.ascii.isDigit(c), .graph => c > ' ' and c < 0x7f, .lower => std.ascii.isLower(c), .print => c >= ' ' and c < 0x7f, .punct => c > ' ' and c < 0x7f and !std.ascii.isAlphanumeric(c), .space => c == ' ' or (c >= '\t' and c <= '\r'), .upper => std.ascii.isUpper(c), .xdigit => std.ascii.isHex(c), }; }};
/// How many instructions `node` compiles to, saturating.fn size(node: Node) u64 { return switch (node) { .empty => 0, .set, .assert => 1, .group => |g| @min(size(g.node.*) + 2, max_program + 1), .concat => |items| sum: { var n: u64 = 0; for (items) |i| n = @min(n + size(i), max_program + 1); break :sum n; }, .alternate => |branches| sum: { var n: u64 = 0; for (branches) |b| n = @min(n + size(b) + 2, max_program + 1); break :sum n; }, .repeat => |r| @min((size(r.node.*) + 4) * @max(r.max orelse r.min + 1, 1), max_program + 1), };}
/// Whether group `index` lies, in `node`, inside a repetition that may/// iterate more than once; null if the group is not in it.fn groupRepeated(node: Node, index: u32, inside: bool) ?bool { return switch (node) { .empty, .set, .assert => null, .group => |g| if (g.index == index) inside else groupRepeated(g.node.*, index, inside), .concat, .alternate => |items| for (items) |i| { if (groupRepeated(i, index, inside)) |r| break r; } else null, .repeat => |r| groupRepeated(r.node.*, index, inside or r.max == null or r.max.? > 1), };}
/// Whether `node` can match the empty string.fn nullable(node: Node) bool { return switch (node) { .empty, .assert => true, .set => false, .group => |g| nullable(g.node.*), .concat => |items| for (items) |i| { if (!nullable(i)) break false; } else true, .alternate => |branches| for (branches) |b| { if (nullable(b)) break true; } else false, .repeat => |r| r.min == 0 or nullable(r.node.*), };}
/// Compiles nodes to a program.const Emitter = struct { a: Allocator, program: std.ArrayList(Inst) = .empty, /// Registers given out to repetitions whose iterations may match the /// empty string. marks: u32 = 0,
fn append(e: *Emitter, inst: Inst) Allocator.Error!void { try e.program.append(e.a, inst); }
fn here(e: *const Emitter) u32 { return @intCast(e.program.items.len); }
/// One optional iteration of a repetition, its split's second target /// left for the caller to fill. Unless it is the very first iteration /// (`first`), a guarded one that could match the empty string must /// not, which is how glibc was seen to count the iterations of an /// unbounded repetition for its groups. fn optional(e: *Emitter, body: Node, first: bool, guarded: bool) Allocator.Error!usize { const split_at = e.program.items.len; try e.append(.{ .split = .{ e.here() + 1, 0 } }); if (guarded and !first) { const m = e.marks; e.marks += 1; try e.append(.{ .mark = m }); try e.emit(body); try e.append(.{ .check = m }); } else try e.emit(body); return split_at; }
fn emit(e: *Emitter, node: Node) Allocator.Error!void { switch (node) { .empty => {}, .set => |s| try e.append(.{ .set = s }), .assert => |x| try e.append(.{ .assert = x }), .group => |g| { try e.append(.{ .save = 2 * g.index }); try e.emit(g.node.*); try e.append(.{ .save = 2 * g.index + 1 }); }, .concat => |items| for (items) |n| try e.emit(n), .alternate => |branches| { // split L1, next; L1: branch; jump end; ... var jumps: std.ArrayList(usize) = .empty; for (branches, 0..) |b, i| { if (i + 1 < branches.len) { const split_at = e.program.items.len; try e.append(.{ .split = .{ e.here() + 1, 0 } }); try e.emit(b); try jumps.append(e.a, e.program.items.len); try e.append(.{ .jump = 0 }); e.program.items[split_at].split[1] = e.here(); } else try e.emit(b); } for (jumps.items) |j| e.program.items[j] = .{ .jump = e.here() }; }, .repeat => |r| { const guarded = nullable(r.node.*); for (0..r.min) |_| try e.emit(r.node.*); if (r.max) |max| { // Each optional copy may be skipped to the end. var splits: std.ArrayList(usize) = .empty; // Any of them may be empty, as glibc was seen to // allow where the repetition is bounded. for (r.min..max) |_| try splits.append(e.a, try e.optional(r.node.*, true, false)); for (splits.items) |s| e.program.items[s].split[1] = e.here(); } else { // A first iteration that may be empty, then // L: split body, out; body; jump L var first_split: ?usize = null; if (r.min == 0 and guarded) first_split = try e.optional(r.node.*, true, guarded); const loop = e.here(); const split_at = try e.optional(r.node.*, false, guarded); try e.append(.{ .jump = loop }); e.program.items[split_at].split[1] = e.here(); if (first_split) |f| e.program.items[f].split[1] = e.here(); } }, } }};
const testing = std.testing;
fn expectMatchWith(want: bool, options: Options, pattern: []const u8, text: []const u8) !void { var r = try Regex.compileWith(testing.allocator, pattern, options, null); defer r.deinit(); errdefer std.debug.print("/{s}/ ({t}) against \"{s}\"\n", .{ pattern, options.syntax, text }); try testing.expectEqual(want, try r.matches(testing.allocator, text));}
fn expectMatch(want: bool, pattern: []const u8, text: []const u8) !void { return expectMatchWith(want, .{}, pattern, text);}
const fuzz_input = @import("testing/fuzz.zig");
test "extended regular expressions match as POSIX says" { try expectMatch(true, "s\\.a", "s.a"); try expectMatch(false, "s\\.a", "sxa"); try expectMatch(true, "^s\\.[ab]", "s.b"); try expectMatch(false, "^x", "ax"); try expectMatch(true, "x$", "ax"); try expectMatch(true, "a|b", "xb"); try expectMatch(true, "^(ab)+$", "ababab"); try expectMatch(false, "^(ab)+$", "aba"); try expectMatch(true, "^a{2,3}$", "aaa"); try expectMatch(false, "^a{2,3}$", "aaaa"); try expectMatch(true, "[[:upper:]]", "t.Sub"); try expectMatch(false, "[^a-z.]", "abc.d"); try expectMatch(true, "", "anything"); try expectMatch(true, "a)", "a)"); try expectMatch(true, "^x\\{", "x{y"); try expectMatch(true, "\\d", "d"); try expectMatch(true, "^a{,2}$", "aa"); try expectMatch(true, "|", "x"); try expectMatch(true, "a**", "b"); try expectMatch(true, "()", "x"); try expectMatch(true, "(a*)*b", "aaab"); try expectMatch(true, "x{1}{2}", "xx"); try expectMatch(true, "a.b", "a\nb");}
test "basic regular expressions match as glibc reads them" { const b: Options = .{ .syntax = .basic, .gnu = true }; try expectMatchWith(true, b, "a|b", "a|b"); try expectMatchWith(false, b, "a|b", "a"); try expectMatchWith(true, b, "a\\|b", "b"); try expectMatchWith(true, b, "\\(ab\\)*c", "ababc"); try expectMatchWith(true, b, "^a\\{2\\}$", "aa"); try expectMatchWith(true, b, "a{2}", "a{2}"); try expectMatchWith(true, b, "*a", "*a"); try expectMatchWith(true, b, "**", "x"); try expectMatchWith(true, b, "^*", "*"); try expectMatchWith(true, b, "\\(*\\)", "*"); try expectMatchWith(true, b, "a^b", "a^b"); try expectMatchWith(true, b, "a$b", "a$b"); try expectMatchWith(true, b, "x\\+\\+", "xx"); try expectMatchWith(true, b, "fix+", "fix+"); try expectMatchWith(true, b, "\\<alpha\\>", "an alpha beta"); try expectMatchWith(false, b, "\\<alph\\>", "an alpha beta"); try expectMatchWith(true, b, "\\bbeta", "alpha beta"); try expectMatchWith(false, b, "\\Sbeta", "alpha beta"); try expectMatchWith(true, b, "\\w", "x"); try expectMatchWith(true, b, "\\`alpha", "alpha"); try expectMatchWith(false, b, "\\`lpha", "alpha"); try expectMatchWith(true, .{ .syntax = .basic, .ignore_case = true }, "MERGE", "merge"); try expectMatchWith(true, .{ .syntax = .basic, .ignore_case = true }, "[A-C]x", "bx"); try expectMatchWith(false, .{ .newline = true }, "a.b", "a\nb"); try expectMatchWith(true, .{ .newline = true }, "^b", "a\nb"); try expectMatchWith(true, .{ .newline = true }, "a$", "a\nb");}
test "malformed and unsupported patterns are refused, in glibc's words" { const cases = [_]struct { Syntax, []const u8, Problem }{ .{ .extended, "[", .bad_pattern }, .{ .extended, "[a", .bracket }, .{ .extended, "(", .parenthesis }, .{ .extended, "a{", .brace }, .{ .extended, "{", .bad_repetition }, .{ .extended, "{1}", .bad_repetition }, .{ .extended, "a{1", .brace }, .{ .extended, "a{1,2", .brace }, .{ .extended, "a{x}", .bad_bound }, .{ .extended, "^*", .bad_repetition }, .{ .extended, "b|*", .bad_repetition }, .{ .extended, "*a", .bad_repetition }, .{ .extended, "(*a)", .bad_repetition }, .{ .extended, "a{2,1}", .bad_bound }, .{ .extended, "[[:foo:]]", .class_name }, .{ .extended, "[z-a]", .range_end }, .{ .extended, "\\", .trailing_backslash }, .{ .extended, "a\\", .trailing_backslash }, .{ .extended, "[[.ab.]]", .collation }, .{ .extended, "\\1", .back_reference }, .{ .basic, "\\(", .parenthesis }, .{ .basic, "\\)", .parenthesis }, .{ .basic, "a\\{", .brace }, .{ .basic, "a\\{1,", .brace }, .{ .basic, "a\\{x\\}", .bad_bound }, .{ .basic, "a\\{99999\\}", .too_big }, .{ .basic, "a**", .bad_repetition }, .{ .basic, "\\{1\\}", .bad_repetition }, .{ .basic, "x*\\{2\\}", .bad_repetition }, .{ .basic, "a\\?*", .bad_repetition }, .{ .basic, "[]", .bracket }, .{ .basic, "[^]", .bracket }, }; for (cases) |case| { var failure: Failure = .{}; errdefer std.debug.print("/{s}/ ({t})\n", .{ case[1], case[0] }); try testing.expectError(error.InvalidPattern, Regex.compileWith(testing.allocator, case[1], .{ .syntax = case[0], .gnu = true }, &failure)); try testing.expectEqual(case[2], failure.problem); } var what: []const u8 = ""; try testing.expectError(error.Unsupported, Regex.compile(testing.allocator, "a\\w", &what)); try testing.expectEqualStrings("\\w", what); try testing.expectError(error.Unsupported, Regex.compileWith(testing.allocator, "(a)\\1", .{ .gnu = true }, null));}
/// What `exec` makes of `pattern` against `text`: the first group's/// text if it took part, the whole match otherwise, or null if there is/// no match, which is the text git shows after `@@`.fn firstGroupOrMatch(options: Options, pattern: []const u8, text: []const u8) !?[]const u8 { var r = try Regex.compileWith(testing.allocator, pattern, options, null); defer r.deinit(); var groups: [1]?Span = undefined; const whole = try r.exec(testing.allocator, text, &groups) orelse return null; const span = groups[0] orelse whole; return text[span.start..span.end];}
test "groups are those glibc chooses, not POSIX's longest" { // Each answer is what git 2.56 showed after `@@` with the pattern as // `diff.<driver>.xfuncname` and the text as the function line. const cases = [_]struct { []const u8, []const u8, ?[]const u8 }{ .{ "a|ab", "xab", "ab" }, .{ "(a*)(a*)", "aaa", "aaa" }, .{ "(a|ab)(bc|c)", "abc", "a" }, .{ "(ab|a)(bc|c)", "abc", "ab" }, .{ "(a|ab)c", "abc", "ab" }, .{ "(a|ab)*c", "abababc", "ab" }, .{ "(a|b)*", "ab", "b" }, .{ "(a*)*", "aa", "aa" }, .{ "x(a*)*y", "xy", "" }, .{ "x(a*)+y", "xy", "" }, .{ "x(a)*y", "xy", "xy" }, .{ "x(a|ab)*(b*)y", "xababby", "a" }, .{ "(a|ab)(c|bcd)(d*)", "abcd", "a" }, .{ "(a|ab|abc)(d*)", "abcd", "abc" }, .{ "(a?)(ab)?b?", "ab", "a" }, .{ "(.*)(b)", "abab", "aba" }, .{ "x(.)*y", "xabcy", "c" }, .{ "(a+|b+)*", "aabba", "a" }, .{ "(a+|ab)*c", "aabc", "ab" }, .{ "(ab|a)*(b*)", "abab", "ab" }, .{ "(a|ab)(b*)", "abb", "a" }, .{ "x(y?)*z", "xz", "" }, .{ "x(y*){2}z", "xyz", "" }, .{ "x(y|z|yz)?(z*)w", "xyzw", "y" }, .{ "(a{0,2}){2}", "aaa", "a" }, .{ "(a|aa){2}", "aaa", "aa" }, .{ "(a*){0,3}", "aa", "" }, .{ "x(a*){0,3}y", "xaay", "" }, .{ "(a{0,2}|a?(b{1,2}|a?)b{2}){0,2}(.a|((a{1,2}|b.a{2})))", "aaa", "" }, .{ "(x)?y", "y", "y" }, .{ "(x)?y", "xy", "x" }, .{ "x[^a]", "x", null }, }; for (cases) |case| { errdefer std.debug.print("/{s}/ against \"{s}\"\n", .{ case[0], case[1] }); const got = try firstGroupOrMatch(.{ .gnu = true }, case[0], case[1]); if (case[2]) |want| try testing.expectEqualStrings(want, got orelse return error.TestExpectedEqual) else try testing.expectEqual(null, got); } try testing.expectEqualStrings("el", (try firstGroupOrMatch(.{ .syntax = .basic, .gnu = true }, "h\\(el\\)lo", "hello")).?);}
test "a first group inside a repetition is told apart" { for ([_]struct { []const u8, bool }{ .{ "(a)", false }, .{ "(a)?", false }, .{ "x(a(b)*)", false }, .{ "(a)*", true }, .{ "((a))+", true }, .{ "(b)(a)*", false }, .{ "(x|(a){2})", false }, .{ "((a){2})", false }, .{ "(?:a)", false }, .{ "(a){1,2}", true }, .{ "(a){1}", false }, }) |case| { var r = Regex.compileWith(testing.allocator, case[0], .{}, null) catch continue; defer r.deinit(); errdefer std.debug.print("/{s}/\n", .{case[0]}); try testing.expectEqual(case[1], r.first_group_repeated); }}
test "a match begins as early as it can and is as long as it can be" { var r = try Regex.compileWith(testing.allocator, "a.*b|c", .{}, null); defer r.deinit(); try testing.expectEqual(Span{ .start = 0, .end = 3 }, (try r.exec(testing.allocator, "acb", &.{})).?); try testing.expectEqual(Span{ .start = 1, .end = 2 }, (try r.exec(testing.allocator, "xcx", &.{})).?); try testing.expectEqual(null, try r.exec(testing.allocator, "xyz", &.{}));}
/// A slow reference for groups, written from the rule `exec` documents/// and nothing else: every way through the pattern, in order of/// preference, by recursion over the parsed pattern.const Reference = struct { text: []const u8, slots: []usize, /// When set, a way through must end here; when not, every end is /// recorded in `ends`. end: ?usize = null, ends: []bool, newline: bool = false, steps: usize = 0,
const Cont = union(enum) { node: struct { node: *const Node, next: ?*const Cont }, close: struct { slot: u32, next: ?*const Cont }, iterate: struct { min: u32, max: ?u32, body: *const Node, count: u32, next: ?*const Cont }, after: struct { min: u32, max: ?u32, body: *const Node, count: u32, start: usize, next: ?*const Cont }, };
const TooLong = error{TooLong};
fn go(f: *Reference, k: ?*const Cont, pos: usize) TooLong!bool { f.steps += 1; if (f.steps > 2_000_000) return error.TooLong; const c = k orelse { if (f.end) |e| return pos == e; f.ends[pos] = true; return false; }; switch (c.*) { .node => |n| return f.node(n.node, n.next, pos), .close => |x| { const old = f.slots[x.slot]; f.slots[x.slot] = pos; if (try f.go(x.next, pos)) return true; f.slots[x.slot] = old; return false; }, .iterate => |it| { if (it.max == null or it.count < it.max.?) { const a: Cont = .{ .after = .{ .min = it.min, .max = it.max, .body = it.body, .count = it.count, .start = pos, .next = it.next } }; if (try f.node(it.body, &a, pos)) return true; } if (it.count >= it.min) return f.go(it.next, pos); return false; }, .after => |a| { if (pos == a.start and a.count >= a.min and a.count > 0 and a.max == null) return false; const it: Cont = .{ .iterate = .{ .min = a.min, .max = a.max, .body = a.body, .count = a.count + 1, .next = a.next } }; return f.go(&it, pos); }, } }
fn node(f: *Reference, n: *const Node, next: ?*const Cont, pos: usize) TooLong!bool { switch (n.*) { .empty => return f.go(next, pos), .set => |s| return pos < f.text.len and s[f.text[pos]] and try f.go(next, pos + 1), .assert => |a| { const r: Regex = .{ .arena = undefined, .program = &.{}, .newline = f.newline }; return r.holds(a, f.text, pos) and try f.go(next, pos); }, .concat => |items| { if (items.len == 0) return f.go(next, pos); const rest: Node = .{ .concat = items[1..] }; const c: Cont = .{ .node = .{ .node = &rest, .next = next } }; return f.node(&items[0], &c, pos); }, .alternate => |branches| { for (branches) |*b| if (try f.node(b, next, pos)) return true; return false; }, .group => |g| { const old = f.slots[2 * g.index]; f.slots[2 * g.index] = pos; const c: Cont = .{ .close = .{ .slot = 2 * g.index + 1, .next = next } }; if (try f.node(g.node, &c, pos)) return true; f.slots[2 * g.index] = old; return false; }, .repeat => |r| { const it: Cont = .{ .iterate = .{ .min = r.min, .max = r.max, .body = r.node, .count = 0, .next = next } }; return f.go(&it, pos); }, } }};
fn fuzzGroups(_: void, smith: *testing.Smith) anyerror!void { const gpa = testing.allocator; var pattern_buf: [24]u8 = undefined; var text_buf: [10]u8 = undefined; const pattern = pattern_buf[0..smith.slice(&pattern_buf)]; const text = text_buf[0..smith.slice(&text_buf)]; const options: Options = .{ .syntax = if (smith.value(bool)) .basic else .extended, .gnu = true };
var arena: std.heap.ArenaAllocator = .init(gpa); defer arena.deinit(); var c: Compiler = .{ .a = arena.allocator(), .pattern = pattern, .options = options }; const tree = c.whole() catch |err| switch (err) { error.OutOfMemory => return err, else => return, }; if (size(tree) > 4096) return; var r = Regex.compileWith(gpa, pattern, options, null) catch return; defer r.deinit();
var groups: [10]?Span = undefined; const got = try r.exec(gpa, text, &groups);
const slots = try arena.allocator().alloc(usize, 2 * (@as(usize, c.groups) + 1)); const ends = try arena.allocator().alloc(bool, text.len + 1); var f: Reference = .{ .text = text, .slots = slots, .ends = ends }; var want: ?Span = null; for (0..text.len + 1) |start| { @memset(ends, false); const top: Reference.Cont = .{ .node = .{ .node = &tree, .next = null } }; _ = f.go(&top, start) catch return; const last = std.mem.findScalarLast(bool, ends, true) orelse continue; want = .{ .start = start, .end = last }; @memset(slots, no_position); f.end = last; try testing.expect(f.go(&top, start) catch return); break; } try testing.expectEqual(want, got); if (want == null) return; for (groups, 0..) |g, i| { const want_group: ?Span = if (i < c.groups and slots[2 * (i + 1)] != no_position and slots[2 * (i + 1) + 1] != no_position) .{ .start = slots[2 * (i + 1)], .end = slots[2 * (i + 1) + 1] } else null; try testing.expectEqual(want_group, g); }}
test "fuzz: groups agree with a slow reference" { try fuzz_input.fuzz({}, fuzzGroups, .{ .corpus = &.{ @embedFile("fuzz/regex-groups"), "\x0c\x00\x00\x00x(a|ab)*(b*)\x07\x00\x00\x00xababby\x00\x00\x00\x00\x00\x00\x00\x00", "\x06\x00\x00\x00(a*)*b\x03\x00\x00\x00aab\x00\x00\x00\x00\x00\x00\x00\x00", "\x09\x00\x00\x00\\(a*\\)*b\x02\x00\x00\x00ab\x01\x00\x00\x00\x00\x00\x00\x00", "\x0b\x00\x00\x00(a{0,2}){2}\x03\x00\x00\x00aaa\x00\x00\x00\x00\x00\x00\x00\x00", } });}