//! Regex compilation (M1-RULE-017, M1-RULE-018). //! //! The lexer has already done the lexical half of M1-RULE-017: it reduced //! `\/` to a slash, left every other backslash alone, rejected literal line //! breaks and validated the flags. What remains here is the mapping onto the //! engine and the search semantics. //! //! M1-RULE-017 requires `~=` to search anywhere in the value, with `^` and `$` //! needed for a full-field match. That is what the engine's own isMatch does, //! so nothing anchors the pattern. //! //! M1-RULE-018 defers syntax and behaviour to the pinned zig-regex revision. //! The tests below therefore record what that revision does rather than assert //! what PCRE would; a dependency bump that changes one is meant to fail them. //! //! Risk R1: the engine advertises linear-time matching but also backreferences //! and lookaround, which no single engine provides. Patterns using those //! presumably fall back to backtracking and can go exponential. M1-SAFE-004's //! fail-safe requirement is checked in T26, not here. const std = @import("std"); const diag = @import("../diag.zig"); const lexer = @import("lexer.zig"); const parser = @import("parser.zig"); /// The pinned dependency (M1-PKG-005). const engine = @import("regex"); pub const Error = error{ InvalidRegex, OutOfMemory }; /// Matches through a `Matcher`, which keeps the engine's lazy DFA from one /// call to the next. `Regex.isMatch` builds a fresh one every call, which /// made matching some ten times slower and allocated on every row. The cache /// makes a `Compiled` mutable and for one thread, and each copy keeps its own. pub const Compiled = struct { matcher: engine.Regex.Matcher, /// M1-RULE-017: an unanchored search over the exact decoded bytes. pub fn matches(self: *Compiled, haystack: []const u8) Error!bool { return self.matcher.isMatch(haystack) catch error.InvalidRegex; } }; /// Compiles a regex literal. Allocations belong to `arena`, so the result /// needs no separate teardown. pub fn compile( arena: std.mem.Allocator, literal: lexer.RegexLiteral, context: parser.Context, diags: *diag.List, ) Error!Compiled { // Verified against the vendored source in T01 (assumption A3): // i -> case_insensitive, m -> multiline, s -> dot_all. The engine's // `extended` and `unicode` are left off; M1-RULE-003 admits no flag for // either. const flags: engine.common.CompileFlags = .{ .case_insensitive = literal.flags.case_insensitive, .multiline = literal.flags.multiline, .dot_all = literal.flags.dot_all, }; // M1-RULE-018: the pinned engine compiles an empty pattern, which then // matches everything. The requirement rejects it instead. if (literal.pattern.len == 0) return invalid(arena, literal, context, diags); // The matcher borrows the regex, so the regex lives in the arena rather // than in the `Compiled` that is copied about. const inner = try arena.create(engine.Regex); inner.* = engine.Regex.compileWithFlags(arena, literal.pattern, flags) catch return invalid(arena, literal, context, diags); return .{ .matcher = inner.matcher() }; } /// Reports `literal` as not a valid regular expression. fn invalid( arena: std.mem.Allocator, literal: lexer.RegexLiteral, context: parser.Context, diags: *diag.List, ) Error { const message = arena.print( "'/{s}/' is not a valid regular expression", .{literal.pattern}, ) catch return error.OutOfMemory; diags.addConfig( .{ .file = context.file, .key_path = context.key_path }, "{s}", .{message}, ) catch return error.OutOfMemory; return error.InvalidRegex; } // -- tests ------------------------------------------------------------------- const expect = std.testing.expect; const expectError = std.testing.expectError; /// Lexes `source` as a single regex literal and compiles it, so the tests /// exercise the same path a rule takes. fn compiled(arena: *std.heap.ArenaAllocator, source: []const u8) Error!Compiled { const alloc = arena.allocator(); const diags = diag.List.create(alloc) catch return error.OutOfMemory; var scanner = lexer.Lexer.init(alloc, source); const token = (scanner.next() catch return error.InvalidRegex) orelse return error.InvalidRegex; return compile(alloc, token.regex, .{ .file = "rules.yaml", .key_path = "rules.r.match", }, diags); } fn matches(arena: *std.heap.ArenaAllocator, source: []const u8, haystack: []const u8) !bool { var compiled_regex = try compiled(arena, source); return compiled_regex.matches(haystack); } test "M1-RULE-017: the operator searches anywhere in the value" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/food/", "fast food items")); try expect(try matches(&arena, "/food/", "food")); try expect(try matches(&arena, "/food/", "seafood")); try expect(!try matches(&arena, "/food/", "drink")); } test "M1-RULE-017: a full-field match needs explicit anchors" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/^food$/", "food")); try expect(!try matches(&arena, "/^food$/", "fast food")); try expect(!try matches(&arena, "/^food$/", "food items")); } test "M1-RULE-017: the i flag matches case-insensitively" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/refund/i", "REFUND")); try expect(try matches(&arena, "/refund/i", "card Refund")); try expect(!try matches(&arena, "/refund/", "REFUND")); } test "M1-RULE-017: the s flag lets dot match a newline" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/a.b/s", "a\nb")); try expect(!try matches(&arena, "/a.b/", "a\nb")); try expect(try matches(&arena, "/a.b/", "axb")); } test "M1-RULE-017: the m flag anchors at line boundaries" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/^second/m", "first\nsecond")); try expect(!try matches(&arena, "/^second/", "first\nsecond")); } test "M1-RULE-017: an escaped slash matches a literal slash" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/a\\/b/", "xa/bx")); try expect(!try matches(&arena, "/a\\/b/", "ab")); } test "M1-RULE-017: other backslashes reach the engine" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/\\d+/", "abc123")); try expect(!try matches(&arena, "/\\d+/", "abc")); try expect(try matches(&arena, "/a\\.b/", "a.b")); try expect(!try matches(&arena, "/a\\.b/", "axb")); } test "M1-RULE-017: matching is over exact bytes without normalization" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // Precomposed e-acute does not match the decomposed pair. try expect(try matches(&arena, "/\u{00E9}/", "caf\u{00E9}")); try expect(!try matches(&arena, "/\u{00E9}/", "cafe\u{0301}")); } test "M1-RULE-018: an invalid pattern is reported, not accepted" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); const alloc = arena.allocator(); const diags = try diag.List.create(alloc); const literal: lexer.RegexLiteral = .{ .pattern = "(unclosed", .flags = .{} }; try expectError(error.InvalidRegex, compile(alloc, literal, .{ .file = "rules.yaml", .key_path = "rules.groceries.match", }, diags)); try expect(!diags.isEmpty()); try std.testing.expectEqualStrings("rules.groceries.match", diags.items.items[0].key_path.?); } // M1-RULE-018 pins the pinned revision's own behaviour. These are observations, // not a specification: if a dependency bump changes one, that is the signal. test "M1-RULE-018: quantifiers behave as recorded" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/ab*c/", "ac")); try expect(try matches(&arena, "/ab+c/", "abbc")); try expect(!try matches(&arena, "/ab+c/", "ac")); try expect(try matches(&arena, "/ab?c/", "ac")); try expect(try matches(&arena, "/a{2,3}/", "aaa")); try expect(!try matches(&arena, "/a{2,3}/", "a")); } test "M1-RULE-018: classes and alternation behave as recorded" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/[abc]/", "b")); try expect(!try matches(&arena, "/[^abc]/", "a")); try expect(try matches(&arena, "/[a-z]+/", "xyz")); try expect(try matches(&arena, "/cat|dog/", "hotdog")); try expect(try matches(&arena, "/\\w+/", "a_1")); try expect(try matches(&arena, "/\\s/", "a b")); } test "M1-RULE-018: an empty pattern is rejected" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // The pinned engine compiles an empty pattern, as many engines do, and it // matches everything. M1-RULE-018 rejects it instead, so "//" -- which T08 // lexes happily as an empty regex literal -- is refused here, at // configuration time. try expectError(error.InvalidRegex, matches(&arena, "//", "anything")); } test "M1-RULE-018: the i flag folds single characters beyond ASCII" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/müller/i", "MÜLLER")); try expect(try matches(&arena, "/MÜLLER/i", "müller")); try expect(try matches(&arena, "/é/i", "É")); // But one character never folds to two: ß does not match SS. try expect(!try matches(&arena, "/straße/i", "STRASSE")); } test "M1-RULE-018: groups behave as recorded" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); try expect(try matches(&arena, "/(ab)+/", "abab")); try expect(try matches(&arena, "/(?:ab)+/", "abab")); } fn canCompile(arena: *std.heap.ArenaAllocator, source: []const u8) bool { return if (compiled(arena, source)) |_| true else |_| false; } test "M1-RULE-018: backreferences and lookaround compile; nested quantifiers do not" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // Bears on risk R1. The engine advertises linear-time matching while also // accepting constructs no linear-time engine can support, so those must // reach a backtracking path. try expect(canCompile(&arena, "/(a)\\1/")); try expect(canCompile(&arena, "/(?=a)b/")); try expect(canCompile(&arena, "/(?<=a)b/")); // It does refuse the textbook catastrophic shape outright, so the obvious // blow-up is unreachable from a rule. Whether other shapes reach it is // open; M1-SAFE-004 is checked in T26. try expect(!canCompile(&arena, "/(a+)+b/")); } test "a compiled regex allocates nothing to match once it has matched" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // Counts the arena's allocations, not the arena's own calls for more // memory, which it makes only now and then. var counting = std.testing.FailingAllocator.init(arena.allocator(), .{}); const diags = try diag.List.create(arena.allocator()); const literal: lexer.RegexLiteral = .{ .flags = .{}, .pattern = "Ref\\. R\\d{3}[A-Z]{4}" }; const context: parser.Context = .{ .file = "rules.yaml", .key_path = "rules.r.match" }; var compiled_regex = try compile(counting.allocator(), literal, context, diags); const cell = "SEPA-Lastschrift Mandat 1043587263418 Ref. R007ABCD VISA Debit"; try expect(try compiled_regex.matches(cell)); const warmed = counting.allocations; for (0..100) |_| try expect(try compiled_regex.matches(cell)); try std.testing.expectEqual(warmed, counting.allocations); } test "M1-SAFE-004: compile reports exhaustion rather than the invalid regex" { var arena = std.heap.ArenaAllocator.init(std.testing.allocator); defer arena.deinit(); // The message allocates from a working arena, so the only allocation that // runs out is the one recording the diagnostic. var failing = std.testing.FailingAllocator.init(std.testing.allocator, .{ .fail_index = 0 }); var diags = diag.List.init(failing.allocator()); defer diags.deinit(); const literal: lexer.RegexLiteral = .{ .flags = .{}, .pattern = "(" }; const context: parser.Context = .{ .file = "rules.yaml", .key_path = "rules.r.match" }; try expectError(error.OutOfMemory, compile(arena.allocator(), literal, context, &diags)); }