diff options
| author | Gabriel Schneider <[email protected]> | 2026-10-30 17:35:06 -0300 |
|---|---|---|
| committer | Gabriel Schneider <[email protected]> | 2026-10-30 17:35:06 -0300 |
| commit | 6d8da8721141284cf33bb901168b26135893eb86 (patch) | |
| tree | 791d63401d4e85fbca1d597a8ce0326e70efd545 /src/regexp.zig | |
| parent | efd43a3a2cf03bb741366331158b368abf9ac583 (diff) | |
| parent | bf6810a8f9d6cc82050e7d9c0cfb06358301b574 (diff) | |
| download | pardes-6d8da8721141284cf33bb901168b26135893eb86.tar.gz pardes-6d8da8721141284cf33bb901168b26135893eb86.zip | |
Merge latest upstream into the macOS branch for Zig 0.17
Retain the macOS branch history and local Acme selection color while adopting upstream's current core and platform changes. Pin Zig and ZLS to 0.17.0, and fetch the existing zstbi compatibility commit through upstream after its original fork was removed.
Diffstat (limited to 'src/regexp.zig')
| -rw-r--r-- | src/regexp.zig | 617 |
1 files changed, 617 insertions, 0 deletions
diff --git a/src/regexp.zig b/src/regexp.zig new file mode 100644 index 00000000..6d281859 --- /dev/null +++ b/src/regexp.zig @@ -0,0 +1,617 @@ +//! How pardes runs a regular expression over text: mvzr's, searched the way +//! sam searches (editors/acme/regx.c). `addr` (src/ninep/addr.zig) and +//! normal mode's `s` and `S` (src/normal.zig) both call it. +const std = @import("std"); +const builtin = @import("builtin"); +const mvzr = @import("mvzr"); + +/// A compiled pattern and how to run it. +/// +/// sam searches the text as lines: `^` and `$` at any line's start and end, +/// and `.` never a newline. mvzr has no such mode (its `^` and `$` are the +/// haystack's ends, its `.` any byte), so each line is its own haystack, and +/// a pattern that names a newline (`\n`) runs over the whole text with its +/// `.`s made `[^\n]`. +/// +/// mvzr backtracks, and has no bound on its work of its own: `a?` twenty +/// times then twenty `a`s is 2^20 steps from each start, `a*a*a*a*x` over a line of a +/// hundred `a`s a second. The search runs with the editor's turn, so it must +/// come back: build.zig patches a step budget into mvzr's matcher, and a +/// search that spends `budget` steps (about 300 ms here) stops with +/// `TooSlow`, found nothing rather than something wrong. +/// +/// ponytail: mvzr takes the first alternative that matches, not sam's +/// longest (`gam|gamma` finds `gam`); a search from the middle of a line lets +/// `^` match there unless the pattern starts with it; across lines, `^`, `$` +/// and `[^...]` keep mvzr's meaning; and a quadratic pattern over a long +/// enough line (`\s*(\w+)\s*=` over 20 KB of letters) runs out of budget. A +/// regex engine of sam's own would lift these; the user chose not to have +/// one. +/// mvzr's own `Regex` holds 64 operations, some 64 pattern characters; a +/// search pattern is often longer. Past these a pattern is refused naming +/// the limit (`e_long`). +pub const max_ops = 512; +const Compiled = mvzr.SizedRegex(max_ops, 64); + +pub const Regex = struct { + re: Compiled, + /// The literal every match starts with, when the pattern opens with one + /// (`line 049`, `foo` in `foo.*bar`): a search goes straight to where it + /// occurs rather than trying mvzr at every line. + lit: [32]u8 = undefined, + lit_len: u8 = 0, + /// The pattern names a newline: it runs over the whole text. + spans: bool, + /// The pattern starts with `^`: a search begun mid-line skips the line. + bol: bool, + /// mvzr steps left to every search with this compiled pattern together, + /// so that addr's backward scan and s/S's many calls share one bound. + steps: u64 = budget, + /// Where `find` last learned a line's start in a text (by its address + /// and length): the line holding `at` starts at `start`. A backward + /// search asks again at each match along a line, and looking back to + /// the line's start from the top each time was quadratic on a long one. + line_hint: struct { ptr: usize = 0, len: usize = 0, at: usize = 0, start: usize = 0 } = .{}, + /// ...and where a line learned to end: the line from `start` ends at + /// `end` (its newline, or `hi`), asked again at each match along it. + end_hint: struct { ptr: usize = 0, len: usize = 0, start: usize = 0, hi: usize = 0, end: usize = 0 } = .{}, + + /// Timed on this machine's ReleaseSafe build: 10M steps of the worst + /// patterns take 45-80 ms, and a Debug build is ten times slower. + pub const budget: u64 = if (builtin.mode == .debug) 4_000_000 else 32_000_000; + + pub const e_long = std.fmt.comptimePrint("bad regular expression: longer than mvzr's {d} operations (about {d} pattern characters)", .{ max_ops, max_ops }); + pub const e_anchor = "bad regular expression: in a pattern with \\n, ^ can only come first and $ only just before a \\n"; + pub const e_wide = std.fmt.comptimePrint("bad regular expression: a range of runes wider than {d} in [...] is not supported", .{max_range}); + pub const e_negated = "bad regular expression: a [^...] with non-ASCII runes is not supported (mvzr's classes hold bytes)"; + pub const e_mixed = "bad regular expression: an alternation anchors every branch with ^ or none (^a|^b, not ^a|b)"; + + /// The most runes a non-ASCII range in a class is spelled out as. + pub const max_range = 256; + + /// `Anchor`: a pattern that names a newline has `^` other than first, + /// or `$` other than just before a `\n`, which mvzr would read as the + /// ends of the whole text and so never match where sam would. + /// The plain characters a pattern opens with, each of which every match + /// must start with: up to the first metacharacter, less the last one + /// when a quantifier makes it optional or repeated. + fn literalPrefix(pat: []const u8, out: *[32]u8) u8 { + // ponytail: any `|` and there is none (a match may start with + // another branch); a top-level-only check would keep `a(b|c)`'s. + if (std.mem.indexOfScalar(u8, pat, '|') != null) return 0; + var n: usize = 0; + while (n < pat.len and n < out.len) : (n += 1) { + if (std.mem.indexOfScalar(u8, "\\^$.[]()|*+?{}", pat[n]) != null) break; + out[n] = pat[n]; + } + if (n < pat.len and std.mem.indexOfScalar(u8, "*?{", pat[n]) != null) n -|= 1; + return @intCast(n); + } + + pub const Error = error{ Bad, Anchor, TooLong, WideRange, NegatedRunes, Mixed }; + + pub fn compile(pat: []const u8) Error!Regex { + if (pat.len == 0) return error.Bad; + // mvzr's classes hold bytes: `[éa-z]` is written `(é|[a-z])` for it. + // The limits apply to the pattern as rewritten. + var runes: [5 * max_ops + 2]u8 = undefined; + if (try runeClasses(pat, &runes)) |whole| return compile(whole); + // mvzr takes `^` only at its pattern's start, so `^def|^ ` (a `^` + // after a `|`) is written `^(def| )` for it: the same lines. A mix, + // `^a|b`, has no such spelling and is refused rather than wrong. + var joined: [5 * max_ops + 2]u8 = undefined; + if (try anchoredAlternation(pat, &joined)) |whole| return compile(whole); + // `.` may become `[^\n]`: five bytes for one. + var buf: [5 * max_ops]u8 = undefined; + var len: usize = 0; + var spans = false; + // Twice over the pattern: the first pass learns whether it names a + // newline, which the second needs to rewrite its `.`s. + for ([2]bool{ false, true }) |emit| { + var i: usize = 0; + // mvzr ends a class at its first unescaped `]`, even one that + // comes first (`[]a]` is an empty class, then `a]`); a `]` member + // is written `\]`. + var in_class = false; + while (i < pat.len) : (i += 1) { + const c = pat[i]; + var piece: []const u8 = pat[i .. i + 1]; + if (c == '\\') { + if (i + 1 >= pat.len) return error.Bad; + i += 1; + piece = pat[i - 1 .. i + 1]; + if (pat[i] == 'n') spans = true; + // mvzr slices two hex digits after `\x` without looking, + // so a short one panics it: refuse it here. + if (pat[i] == 'x' and (i + 2 >= pat.len or + !std.ascii.isHex(pat[i + 1]) or !std.ascii.isHex(pat[i + 2]))) return error.Bad; + } else if (in_class) { + in_class = c != ']'; + } else if (c == '[') { + in_class = true; + } else if (c == '.' and spans) { + piece = "[^\\n]"; + } else if (spans and c == '^' and i != 0) { + return error.Anchor; + } else if (spans and c == '$') { + // `x$\n` is `x\n`; any other `$` would be the text's end. + if (std.mem.startsWith(u8, pat[i + 1 ..], "\\n")) continue; + return error.Anchor; + } + if (!emit) continue; + if (len + piece.len > buf.len) return error.TooLong; + @memcpy(buf[len..][0..piece.len], piece); + len += piece.len; + } + } + var lit: [32]u8 = undefined; + const lit_len = if (spans) 0 else literalPrefix(pat, &lit); + return .{ + .lit = lit, + .lit_len = lit_len, + .re = Compiled.compile(buf[0..len]) orelse { + // Too long, or malformed: told apart by trying it with room. + if (mvzr.SizedRegex(4 * max_ops, 256).compile(buf[0..len]) != null) return error.TooLong; + return error.Bad; + }, + .spans = spans, + .bol = pat[0] == '^', + }; + } + + /// `pat` with each class that holds a non-ASCII rune written as an + /// alternation of its runes and a class of the rest (`[éa-z]` is + /// `(é|[a-z])`), a range spelled out rune by rune; null when no class + /// holds one. + fn runeClasses(pat: []const u8, out: *[5 * max_ops + 2]u8) Error!?[]const u8 { + var w = std.Io.Writer.fixed(out); + var any = false; + var i: usize = 0; + while (i < pat.len) : (i += 1) { + const c = pat[i]; + if (c == '\\') { + w.writeAll(pat[i..@min(i + 2, pat.len)]) catch return error.TooLong; + i += 1; + continue; + } + if (c != '[') { + w.writeByte(c) catch return error.TooLong; + continue; + } + // The class's end, as mvzr finds it: the first unescaped `]`. + var end = i + 1; + while (end < pat.len and pat[end] != ']') : (end += 1) { + if (pat[end] == '\\') end += 1; + } + if (end >= pat.len) return error.Bad; + const body = pat[i + 1 .. end]; + if (for (body) |b| { + if (b >= 0x80) break false; + } else true) { + w.writeAll(pat[i .. end + 1]) catch return error.TooLong; + i = end; + continue; + } + if (body[0] == '^') return error.NegatedRunes; + any = true; + try runeClass(body, &w); + i = end; + } + return if (any) w.buffered() else null; + } + + fn runeClass(body: []const u8, w: *std.Io.Writer) Error!void { + var ascii: [5 * max_ops]u8 = undefined; + var n: usize = 0; + w.writeByte('(') catch return error.TooLong; + var alts: usize = 0; + var j: usize = 0; + while (j < body.len) { + if (body[j] == '\\') { + const len: usize = if (j + 1 < body.len and body[j + 1] == 'x') 4 else 2; + if (j + len > body.len) return error.Bad; + // An escape at one end of a range whose other end is a rune. + if (j + len + 1 < body.len and body[j + len] == '-' and body[j + len + 1] >= 0x80) return error.Bad; + if (n + len > ascii.len) return error.TooLong; + @memcpy(ascii[n..][0..len], body[j..][0..len]); + n += len; + j += len; + continue; + } + const lo, const lo_len = try rune(body[j..]); + j += lo_len; + var hi = lo; + if (j + 1 < body.len and body[j] == '-') { + if (body[j + 1] == '\\' and lo >= 0x80) return error.Bad; + if (body[j + 1] != '\\') { + hi, const hi_len = try rune(body[j + 1 ..]); + j += 1 + hi_len; + } + } + if (hi < lo) return error.Bad; + if (hi - lo + 1 > max_range) return error.WideRange; + // Runes that differ only in their last byte go as one + // alternative, `\xc3[\xa0-\xbf]` for `[à-ÿ]`: 256 runes one a + // time would pass `max_ops`. + var run: [4]u8 = undefined; + var run_len: usize = 0; + var run_hi: u8 = 0; + var cp = lo; + while (cp <= hi + 1) : (cp += 1) { + var enc: [4]u8 = undefined; + const len = if (cp > hi) 0 else std.unicode.utf8Encode(cp, &enc) catch continue; // a surrogate + if (run_len > 0 and (len != run_len or enc[len - 1] != run_hi + 1 or + !std.mem.eql(u8, enc[0 .. len - 1], run[0 .. len - 1]))) + { + if (alts > 0) w.writeByte('|') catch return error.TooLong; + w.writeAll(run[0 .. run_len - 1]) catch return error.TooLong; + if (run_hi == run[run_len - 1]) + w.writeByte(run_hi) catch return error.TooLong + else + w.print("[\\x{x:0>2}-\\x{x:0>2}]", .{ run[run_len - 1], run_hi }) catch return error.TooLong; + alts += 1; + run_len = 0; + } + if (cp > hi) break; + if (cp < 0x80) { + // `\xHH` rather than the byte: `]`, `^`, `-` and `\` + // would otherwise mean something in the class. + if (n + 4 > ascii.len) return error.TooLong; + _ = std.fmt.bufPrint(ascii[n..][0..4], "\\x{x:0>2}", .{cp}) catch unreachable; + n += 4; + continue; + } + if (run_len == 0) { + run = enc; + run_len = len; + } + run_hi = enc[len - 1]; + } + } + if (n > 0) w.print("|[{s}]", .{ascii[0..n]}) catch return error.TooLong; + w.writeByte(')') catch return error.TooLong; + } + + /// The rune `s` opens with and its length in bytes. + fn rune(s: []const u8) error{Bad}!struct { u21, usize } { + const len = std.unicode.utf8ByteSequenceLength(s[0]) catch return error.Bad; + if (len > s.len) return error.Bad; + return .{ std.unicode.utf8Decode(s[0..len]) catch return error.Bad, len }; + } + + /// `^a|^b` as `^(a|b)` in `out`, when the pattern is an alternation at + /// its top level and every branch starts with `^`; null when it is not + /// one, or no branch does. + fn anchoredAlternation(pat: []const u8, out: *[5 * max_ops + 2]u8) error{ Bad, Mixed }!?[]const u8 { + // No rewrite is longer than `out`, so neither is any pattern it + // takes, nor its count of bars. + if (pat.len > out.len) return error.Bad; + var bars: [5 * max_ops + 2]u16 = undefined; + var n: usize = 0; + var depth: usize = 0; + var in_class = false; + var i: usize = 0; + while (i < pat.len) : (i += 1) { + const c = pat[i]; + if (c == '\\') { + i += 1; + } else if (in_class) { + in_class = c != ']'; + } else if (c == '[') { + in_class = true; + } else if (c == '(') { + depth += 1; + } else if (c == ')') { + depth -|= 1; + } else if (c == '|' and depth == 0) { + bars[n] = @intCast(i); + n += 1; + } + } + if (n == 0) return null; + var anchored: usize = 0; + var from: usize = 0; + for (0..n + 1) |k| { + const to = if (k < n) bars[k] else pat.len; + anchored += @intFromBool(to > from and pat[from] == '^'); + from = to + 1; + } + if (anchored == 0) return null; + // Only `^` counts: `$` is mvzr's own at a branch's end (`a$|b`). + if (anchored != n + 1) return error.Mixed; + var w = std.Io.Writer.fixed(out); + w.writeAll("^(") catch return error.Bad; + from = 0; + for (0..n + 1) |k| { + const to = if (k < n) bars[k] else pat.len; + if (k > 0) w.writeByte('|') catch return error.Bad; + w.writeAll(pat[from + 1 .. to]) catch return error.Bad; + from = to + 1; + } + w.writeByte(')') catch return error.Bad; + return w.buffered(); + } + + pub const Match = struct { start: usize, end: usize }; + + /// Where the line from `start` ends (its newline, else `hi`), `at` on + /// it: known when asked before of this line of this text. + fn lineEnd(rx: *Regex, text: []const u8, start: usize, at: usize, hi: usize) usize { + const h = rx.end_hint; + if (h.ptr == @intFromPtr(text.ptr) and h.len == text.len and h.start == start and h.hi == hi and at <= h.end) return h.end; + // No newline between the line's start and `at`: the look starts there. + const end = std.mem.indexOfScalarPos(u8, text[0..hi], at, '\n') orelse hi; + rx.end_hint = .{ .ptr = @intFromPtr(text.ptr), .len = text.len, .start = start, .hi = hi, .end = end }; + return end; + } + + /// Where the line holding `from` starts, looking back only to where + /// the last call learned one in this text. + fn lineStart(rx: *Regex, text: []const u8, from: usize) usize { + const h = rx.line_hint; + const known = h.ptr == @intFromPtr(text.ptr) and h.len == text.len and h.at <= from; + const lo = if (known) h.at else 0; + const s = if (std.mem.lastIndexOfScalar(u8, text[lo..from], '\n')) |nl| lo + nl + 1 else if (known) h.start else 0; + rx.line_hint = .{ .ptr = @intFromPtr(text.ptr), .len = text.len, .at = from, .start = s }; + return s; + } + + /// The first match that starts in `from..=last` and ends by `hi`, as + /// offsets into `text`. The text before `from` still says where lines + /// begin. + pub fn find(rx: *Regex, text: []const u8, from: usize, last: usize, hi: usize) error{TooSlow}!?Match { + mvzr.steps_left = rx.steps; + mvzr.exhausted = false; + defer rx.steps = mvzr.steps_left; + // A `^` pattern that spans lines: mvzr's `^` is its haystack's start, + // so each line start from `from` on is tried as one. + // ponytail: a search per line start, each to `hi`; the step budget + // bounds it. + if (rx.spans and rx.bol) { + var s = if (from == 0 or text[from - 1] == '\n') from else (std.mem.indexOfScalarPos(u8, text[0..hi], from, '\n') orelse return null) + 1; + while (s <= last and s <= hi) { + const hit = rx.re.match(text[s..hi]); + if (mvzr.exhausted) return error.TooSlow; + if (hit) |m| if (m.start == 0) return .{ .start = s, .end = s + m.end }; + s = (std.mem.indexOfScalarPos(u8, text[0..hi], s, '\n') orelse return null) + 1; + } + return null; + } + var start: usize = if (rx.spans) 0 else rx.lineStart(text, from); + var at = from - start; + // `^` cannot match in the middle of a line. + if (!rx.spans and rx.bol and at > 0) { + start = (std.mem.indexOfScalarPos(u8, text[0..hi], from, '\n') orelse return null) + 1; + at = 0; + } + while (start <= hi and start <= last) { + // A pattern that opens with a literal matches only where it + // occurs: on to the line where it next does. + if (rx.lit_len > 0 and !rx.spans) { + const q = std.mem.indexOfPos(u8, text[0..hi], start + at, rx.lit[0..rx.lit_len]) orelse return null; + if (q > last) return null; + if (q > start + at) { + // `start` begins a line and `start + at` is on it: the + // look back ends there. + const line_start = if (std.mem.lastIndexOfScalar(u8, text[start + at .. q], '\n')) |nl| start + at + nl + 1 else start; + if (line_start > start) { + start = line_start; + at = q - line_start; + } else at = q - start; + if (rx.bol and at > 0) { + start = (std.mem.indexOfScalarPos(u8, text[0..hi], q, '\n') orelse return null) + 1; + at = 0; + continue; + } + } + } + const end = if (rx.spans) hi else rx.lineEnd(text, start, start + at, hi); + const line = text[start..end]; + // matchPos finds nothing at a haystack's very end, where `$` or + // an empty match still can. + const hit: ?[2]usize = if (at < line.len) + (if (rx.re.matchPos(at, line)) |m| .{ m.start, m.end } else null) + else if (at == line.len and rx.re.isMatch(line[at..])) .{ at, at } else null; + if (mvzr.exhausted) return error.TooSlow; + if (hit) |h| { + if (start + h[0] > last) return null; + return .{ .start = start + h[0], .end = start + h[1] }; + } + if (end == hi) return null; + start = end + 1; + at = 0; + } + return null; + } +}; + +test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans lines" { + const text = "alpha beta\nbeta gamma\ngamma\n"; + const Case = struct { pat: []const u8, from: usize, start: usize, end: usize }; + for ([_]Case{ + .{ .pat = "^beta", .from = 0, .start = 11, .end = 15 }, + .{ .pat = "beta$", .from = 0, .start = 6, .end = 10 }, + .{ .pat = "a.*", .from = 0, .start = 0, .end = 10 }, + .{ .pat = "a\\nbeta", .from = 0, .start = 9, .end = 15 }, + .{ .pat = "t.\\nbeta", .from = 0, .start = 8, .end = 15 }, + .{ .pat = "^", .from = 1, .start = 11, .end = 11 }, + }) |c| { + var rx = try Regex.compile(c.pat); + const m = (try rx.find(text, c.from, text.len, text.len)).?; + try std.testing.expectEqual(c.start, m.start); + try std.testing.expectEqual(c.end, m.end); + } + _ = try Regex.compile("a.*a\\nq"); + // `^` at every line start and `$` before a newline, when a pattern + // spans lines; anywhere else they are refused, never silently wrong. + const defs = "x = 1\ndef a\n\ndef b\n"; + var def = try Regex.compile("^def .*\\n"); + const d = (try def.find(defs, 0, defs.len, defs.len)).?; + try std.testing.expectEqual(@as(usize, 6), d.start); + try std.testing.expectEqual(@as(usize, 12), d.end); + try std.testing.expectEqual(@as(usize, 13), (try def.find(defs, 7, defs.len, defs.len)).?.start); + var blank = try Regex.compile("^\\n"); + try std.testing.expectEqual(@as(usize, 12), (try blank.find(defs, 0, defs.len, defs.len)).?.start); + var dollar = try Regex.compile("1$\\n"); + try std.testing.expectEqual(@as(usize, 4), (try dollar.find(defs, 0, defs.len, defs.len)).?.start); + try std.testing.expectError(error.Anchor, Regex.compile("(^|\\n)def")); + try std.testing.expectError(error.Anchor, Regex.compile("a$\\nb$")); + var none = try Regex.compile("zzz"); + try std.testing.expect(try none.find(text, 0, text.len, text.len) == null); + try std.testing.expectError(error.Bad, Regex.compile("")); + try std.testing.expectError(error.Bad, Regex.compile("a\\")); +} + +test "a pattern opening with a literal finds what a search from each line finds" { + const text = "alpha beta\nbeta gamma\ngamma alpha\nfoo line 049999 x\n"; + for ([_][]const u8{ "beta", "gam+a", "line 049999", "alph?a", "a.*a", "^gamma", "o+", "h$|zz", "beta|x" }) |pat| { + var fast = try Regex.compile(pat); + var slow = try Regex.compile(pat); + slow.lit_len = 0; + var from: usize = 0; + while (from < text.len) : (from += 1) { + const a = try fast.find(text, from, text.len, text.len); + const b = try slow.find(text, from, text.len, text.len); + try std.testing.expectEqual(b == null, a == null); + if (a) |m| try std.testing.expectEqual(b.?.start, m.start); + } + } +} + +test "a class with non-ASCII runes matches those runes: [éa-z], a range of them, and refuses a wide range or [^é]" { + const text = "1 é 2 b 3 ü 4 ñ\n"; + var mixed = try Regex.compile("[éa-z]+"); + try std.testing.expectEqual(@as(usize, 2), (try mixed.find(text, 0, text.len, text.len)).?.start); + const m = (try mixed.find(text, 5, text.len, text.len)).?; + try std.testing.expectEqualStrings("b", text[m.start..m.end]); + var range = try Regex.compile("3 [à-ÿ]"); + const r = (try range.find(text, 0, text.len, text.len)).?; + try std.testing.expectEqualStrings("3 ü", text[r.start..r.end]); + // An ASCII member that means something in a class stays a member. + var odd = try Regex.compile("[ñ\\]^-]"); + try std.testing.expectEqual(@as(usize, 16), (try odd.find(text, 0, text.len, text.len)).?.start); + var none = try Regex.compile("[ö]"); + try std.testing.expect(try none.find(text, 0, text.len, text.len) == null); + try std.testing.expectError(error.WideRange, Regex.compile("[ā-ӿ]")); + try std.testing.expectError(error.NegatedRunes, Regex.compile("[^é]")); + try std.testing.expectError(error.Bad, Regex.compile("[é")); + try std.testing.expectError(error.Bad, Regex.compile("[ÿ-à]")); + // A full 256-rune range fits the limit as rewritten. + var wide = try Regex.compile("x[Ā-ǿ]"); + try std.testing.expectEqual(@as(usize, 2), (try wide.find("ǿxǿ", 0, 5, 5)).?.start); + var kana = try Regex.compile("[ぁ-ゟ]"); // 3 bytes, across a last-byte wrap + try std.testing.expectEqual(@as(usize, 1), (try kana.find("aゞ", 0, 4, 4)).?.start); + try std.testing.expectError(error.WideRange, Regex.compile("[Ā-Ȁ]")); +} + +test "a pattern past 64 characters compiles, and one past the limit says so" { + var long = try Regex.compile(&@as([200]u8, @splat('a'))); + const text = "x" ++ &@as([200]u8, @splat('a')) ++ "\n"; + try std.testing.expectEqual(@as(usize, 1), (try long.find(text, 0, text.len, text.len)).?.start); + try std.testing.expectError(error.TooLong, Regex.compile(&@as([max_ops + 8]u8, @splat('a')))); + try std.testing.expectError(error.Bad, Regex.compile("a[b")); +} + +test "a ^ after | anchors that branch: ^def|^ finds a line that starts either way, and a mix is refused" { + const text = "x def\n a\ndef b\n"; + var both = try Regex.compile("^def|^ "); + try std.testing.expectEqual(@as(usize, 6), (try both.find(text, 0, text.len, text.len)).?.start); + try std.testing.expectEqual(@as(usize, 9), (try both.find(text, 7, text.len, text.len)).?.start); + try std.testing.expectError(error.Mixed, Regex.compile("^def|x")); + var plain = try Regex.compile("a|b"); + try std.testing.expectEqual(@as(usize, 7), (try plain.find(text, 0, text.len, text.len)).?.start); + // Seventeen branches and more are a pattern like any other. + var many = try Regex.compile("q|r|s|t|u|v|w|x|y|z|k|l|m|n|o|p|j|b"); + try std.testing.expectEqual(@as(usize, 0), (try many.find(text, 0, text.len, text.len)).?.start); +} + +test "a quoted backslash before n is no newline, and a class ends where mvzr ends it" { + // `\\n` is a backslash then an n: the pattern stays on one line, so its + // `.` is not made [^\n] and does match within the line. + var slash = try Regex.compile("a\\\\n."); + try std.testing.expect(!slash.spans); + try std.testing.expectEqual(@as(usize, 0), (try slash.find("a\\nX", 0, 4, 4)).?.start); + // `[\]x]` is a class of `]` and `x`: the escaped `]` does not end it, + // so the `*` after it is a repeat and the `.` a newline's rewrite. + var class = try Regex.compile("[\\]x]*y.\\n"); + try std.testing.expect(class.spans); + try std.testing.expectEqual(@as(usize, 1), (try class.find("-]x]y!\nz", 0, 8, 8)).?.start); + try std.testing.expect(try class.find("-]x]y\n\n", 0, 7, 7) == null); + // mvzr reads `[]x]` as an empty class then `x]`, which nothing matches. + var empty = try Regex.compile("[]x]"); + try std.testing.expect(try empty.find("x]", 0, 2, 2) == null); +} + +test "a search that would backtrack without end runs out of budget, promptly" { + var line: [20000]u8 = @splat('a'); + for ([_][]const u8{ "(a|ab)*c", "a*a*a*a*a*x", ".*.*.*x" }) |pat| { + var rx = try Regex.compile(pat); + try std.testing.expectError(error.TooSlow, rx.find(&line, 0, line.len, line.len)); + } + // As long a chain as mvzr compiles, over runs one `a` short of it: 2^20 + // steps from every start. + for (0..line.len / 20) |i| line[i * 20 + 19] = 'b'; + var chain = try Regex.compile(std.mem.asBytes(&@as([20][2]u8, @splat("a?".*))) ++ &@as([20]u8, @splat('a'))); + try std.testing.expectError(error.TooSlow, chain.find(&line, 0, line.len, line.len)); +} + +test "the match is the leftmost, however long the line" { + // A window cut into the identifier would find `x... =` from its middle. + const text = "let " ++ &@as([100]u8, @splat('x')) ++ " = 1"; + var assign = try Regex.compile("\\s*(\\w+)\\s*="); + const m = (try assign.find(text, 0, text.len, text.len)).?; + try std.testing.expectEqual(@as(usize, 3), m.start); + try std.testing.expectEqual(@as(usize, 106), m.end); + // Repeats are not counted or capped. + var five = try Regex.compile("a*b*c*d*e*f"); + const f = (try five.find("xxaabbf", 0, 7, 7)).?; + try std.testing.expectEqual(@as(usize, 2), f.start); + try std.testing.expectEqual(@as(usize, 7), f.end); +} + +test "a \\x without two hex digits is refused, not handed to mvzr to panic on" { + for ([_][]const u8{ "\\x", "a\\x1", "\\x1b[\\x", "[\\x]", "\\xg1" }) |pat| + try std.testing.expectError(error.Bad, Regex.compile(pat)); + var rx = try Regex.compile("\\x41"); + try std.testing.expectEqual(@as(usize, 1), (try rx.find("xA", 0, 1, 2)).?.start); +} + +test "a repeat inside a group gives back to what follows the group" { + const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize }; + for ([_]Case{ + .{ .pat = "a+ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(a+)ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(a*)ab", .text = "aab", .start = 0, .end = 3 }, + .{ .pat = "(.+)_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "([a-z_]+)_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "\\w+_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "(\\w)+_area", .text = "the_total_area x", .start = 0, .end = 14 }, + .{ .pat = "([a-z]+)_area", .text = "the_total_area x", .start = 4, .end = 14 }, + .{ .pat = "x(ab|a)bc", .text = "xabc", .start = 0, .end = 4 }, + }) |c| { + var rx = try Regex.compile(c.pat); + const m = (try rx.find(c.text, 0, c.text.len, c.text.len)) orelse { + std.debug.print("no match for {s}\n", .{c.pat}); + return error.NoMatch; + }; + try std.testing.expectEqual(c.start, m.start); + try std.testing.expectEqual(c.end, m.end); + } +} + +test "`$` may end any alternative, not only the last" { + const Case = struct { pat: []const u8, text: []const u8, start: usize, end: usize }; + for ([_]Case{ + .{ .pat = "h$|zz", .text = "xh", .start = 1, .end = 2 }, + .{ .pat = "zz|h$", .text = "xh", .start = 1, .end = 2 }, + .{ .pat = "h$|zz", .text = "hx zz", .start = 3, .end = 5 }, + .{ .pat = "(h$|zz)", .text = "xh", .start = 1, .end = 2 }, + }) |c| { + var rx = try Regex.compile(c.pat); + const m = (try rx.find(c.text, 0, c.text.len, c.text.len)).?; + try std.testing.expectEqual(c.start, m.start); + try std.testing.expectEqual(c.end, m.end); + } + var only = try Regex.compile("h$|zz"); + try std.testing.expectEqual(null, try only.find("hx", 0, 2, 2)); +} |
