diff options
Diffstat (limited to 'src/regexp.zig')
| -rw-r--r-- | src/regexp.zig | 250 |
1 files changed, 243 insertions, 7 deletions
diff --git a/src/regexp.zig b/src/regexp.zig index ca396ff1..ddb5eb28 100644 --- a/src/regexp.zig +++ b/src/regexp.zig @@ -27,8 +27,19 @@ const mvzr = @import("mvzr"); /// 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: mvzr.Regex, + 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. @@ -41,19 +52,48 @@ pub const Regex = struct { /// 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)"; + + /// 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. - pub fn compile(pat: []const u8) error{ Bad, Anchor }!Regex { + /// 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 }; + + 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: [258]u8 = undefined; + var joined: [5 * max_ops + 2]u8 = undefined; if (try anchoredAlternation(pat, &joined)) |whole| return compile(whole); - var buf: [256]u8 = undefined; + // `.` 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 @@ -90,22 +130,150 @@ pub const Regex = struct { return error.Anchor; } if (!emit) continue; - if (len + piece.len > buf.len) return error.Bad; + 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 .{ - .re = mvzr.compile(buf[0..len]) orelse return error.Bad, + .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: *[258]u8) error{Bad}!?[]const u8 { + fn anchoredAlternation(pat: []const u8, out: *[5 * max_ops + 2]u8) error{Bad}!?[]const u8 { var bars: [16]usize = undefined; var n: usize = 0; var depth: usize = 0; @@ -183,6 +351,24 @@ pub const Regex = struct { 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) { + const line_start = if (std.mem.lastIndexOfScalar(u8, text[0..q], '\n')) |nl| nl + 1 else 0; + 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 std.mem.indexOfScalarPos(u8, text[0..hi], start, '\n') orelse hi; const line = text[start..end]; // matchPos finds nothing at a haystack's very end, where `$` or @@ -240,6 +426,56 @@ test "lines are haystacks: ^ and $ at each line, . never a newline, \\n spans li 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("a" ** 200); + const text = "x" ++ "a" ** 200 ++ "\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("a" ** (max_ops + 8))); + 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|^ "); |