Something went wrong. Try again.
A regular expression library for Zig with PCRE semantics, four engines behind one API, and a JIT for x86-64 and aarch64.
Something went wrong. Try again.
1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301311321331341351361371381391401411421431441451461471481491501511521531541551561571581591601611621631641651661671681691701711721731741751761771781791801811821831841851861871881891901911921931941951961971981992002012022032042052062072082092102112122132142152162172182192202212222232242252262272282292302312322332342352362372382392402412422432442452462472482492502512522532542552562572582592602612622632642652662672682692702712722732742752762772782792802812822832842852862872882892902912922932942952962972982993003013023033043053063073083093103113123133143153163173183193203213223233243253263273283293303313323333343353363373383393403413423433443453463473483493503513523533543553563573583593603613623633643653663673683693703713723733743753763773783793803813823833843853863873883893903913923933943953963973983994004014024034044054064074084094104114124134144154164174184194204214224234244254264274284294304314324334344354364374384394404414424434444454464474484494504514524534544554564574584594604614624634644654664674684694704714724734744754764774784794804814824834844854864874884894904914924934944954964974984995005015025035045055065075085095105115125135145155165175185195205215225235245255265275285295305315325335345355365375385395405415425435445455465475485495505515525535545555565575585595605615625635645655665675685695705715725735745755765775785795805815825835845855865875885895905915925935945955965975985996006016026036046056066076086096106116126136146156166176186196206216226236246256266276286296306316326336346356366376386396406416426436446456466476486496506516526536546556566576586596606616626636646656666676686696706716726736746756766776786796806816826836846856866876886896906916926936946956966976986997007017027037047057067077087097107117127137147157167177187197207217227237247257267277287297307317327337347357367377387397407417427437447457467477487497507517527537547557567577587597607617627637647657667677687697707717727737747757767777787797807817827837847857867877887897907917927937947957967977987998008018028038048058068078088098108118128138148158168178188198208218228238248258268278288298308318328338348358368378388398408418428438448458468478488498508518528538548558568578588598608618628638648658668678688698708718728738748758768778788798808818828838848858868878888898908918928938948958968978988999009019029039049059069079089099109119129139149159169179189199209219229239249259269279289299309319329339349359369379389399409419429439449459469479489499509519529539549559569579589599609619629639649659669679689699709719729739749759769779789799809819829839849859869879889899909919929939949959969979989991000100110021003100410051006100710081009101010111012101310141015101610171018101910201021102210231024102510261027102810291030103110321033103410351036103710381039104010411042104310441045104610471048104910501051105210531054105510561057105810591060106110621063106410651066106710681069107010711072107310741075107610771078107910801081108210831084108510861087108810891090109110921093109410951096109710981099110011011102110311041105110611071108110911101111111211131114111511161117111811191120112111221123112411251126112711281129113011311132113311341135113611371138113911401141114211431144114511461147114811491150115111521153115411551156115711581159116011611162116311641165116611671168116911701171117211731174117511761177117811791180118111821183118411851186118711881189119011911192119311941195119611971198119912001201120212031204120512061207120812091210121112121213121412151216121712181219122012211222122312241225122612271228122912301231123212331234123512361237123812391240124112421243124412451246124712481249125012511252125312541255125612571258125912601261126212631264126512661267126812691270127112721273127412751276127712781279128012811282128312841285128612871288128912901291129212931294129512961297129812991300130113021303130413051306130713081309131013111312131313141315131613171318131913201321132213231324132513261327132813291330133113321333133413351336133713381339134013411342134313441345134613471348134913501351135213531354135513561357135813591360136113621363136413651366136713681369137013711372137313741375137613771378137913801381138213831384138513861387138813891390139113921393139413951396139713981399140014011402140314041405140614071408140914101411141214131414141514161417141814191420142114221423142414251426142714281429143014311432143314341435143614371438143914401441144214431444144514461447144814491450145114521453145414551456145714581459146014611462146314641465146614671468146914701471147214731474147514761477147814791480148114821483148414851486148714881489149014911492149314941495149614971498149915001501150215031504150515061507150815091510151115121513151415151516151715181519152015211522152315241525152615271528152915301531153215331534153515361537153815391540154115421543154415451546154715481549155015511552155315541555155615571558155915601561156215631564156515661567156815691570157115721573157415751576157715781579158015811582158315841585158615871588158915901591159215931594159515961597159815991600160116021603160416051606160716081609161016111612161316141615161616171618161916201621162216231624162516261627162816291630163116321633163416351636163716381639164016411642164316441645164616471648164916501651165216531654165516561657165816591660166116621663166416651666166716681669167016711672167316741675167616771678167916801681168216831684168516861687168816891690169116921693169416951696169716981699170017011702170317041705170617071708170917101711// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Behavior tests exercising the full pipeline through all four engines.const std = @import("std");const zregex = @import("root.zig");const Regex = zregex.Regex;
const gpa = std.testing.allocator;
/// Compile, find, and check the text of the whole match (null = no match).fn expectFind(pattern: []const u8, haystack: []const u8, expected: ?[]const u8) !void { var re = try Regex.compile(gpa, pattern); defer re.deinit(); var m = (try re.find(gpa, haystack)) orelse { try std.testing.expectEqual(@as(?[]const u8, null), expected); return; }; defer m.deinit(gpa); try std.testing.expect(expected != null); try std.testing.expectEqualStrings(expected.?, m.span().slice(haystack));}
/// Compile, find, and check each capture group's text (index 0 first).fn expectGroups(pattern: []const u8, haystack: []const u8, expected: []const ?[]const u8) !void { var re = try Regex.compile(gpa, pattern); defer re.deinit(); var m = (try re.find(gpa, haystack)).?; defer m.deinit(gpa); try std.testing.expectEqual(expected.len, m.groups.len); for (expected, 0..) |e, i| { if (e) |text| { try std.testing.expect(m.groups[i] != null); try std.testing.expectEqualStrings(text, m.groups[i].?.slice(haystack)); } else { try std.testing.expectEqual(@as(?zregex.Span, null), m.groups[i]); } }}
test "literals and alternation" { try expectFind("abc", "xxabcxx", "abc"); try expectFind("abc", "xxabxx", null); try expectFind("cat|dog", "hotdog", "dog"); try expectFind("cat|dog", "catalog", "cat"); try expectFind("", "anything", "");}
test "leftmost-greedy semantics" { try expectFind("a+", "caaat", "aaa"); try expectFind("a|ab", "ab", "a"); // alternation prefers the left branch try expectFind("<.+>", "<a><b>", "<a><b>"); try expectFind("<.+?>", "<a><b>", "<a>");}
test "quantifiers" { try expectFind("ab*c", "ac", "ac"); try expectFind("ab*c", "abbbc", "abbbc"); try expectFind("ab+c", "ac", null); try expectFind("ab?c", "abc", "abc"); try expectFind("a{3}", "aaaa", "aaa"); try expectFind("a{2,3}", "aaaa", "aaa"); try expectFind("a{2,3}?", "aaaa", "aa"); try expectFind("a{2,}", "aaaa", "aaaa"); try expectFind("a{4,}", "aaa", null);}
test "character classes" { try expectFind("[abc]+", "xcabz", "cab"); try expectFind("[^abc]+", "abxyzca", "xyz"); try expectFind("[a-fA-F0-9]+", "xDEADbeef9!", "DEADbeef9"); try expectFind("[]x]+", "ax]x", "x]x"); // leading ] is literal try expectFind("[a-]+", "b-a-", "-a-"); try expectFind("\\d+", "abc123def", "123"); try expectFind("\\D+", "12abc34", "abc"); try expectFind("\\w+", "!hi_there2!", "hi_there2"); try expectFind("\\s+", "a \t\nb", " \t\n"); try expectFind("[\\d\\s]+", "a1 2b", "1 2"); try expectFind("[^\\S]+", "ab cd", " ");}
test "anchors and boundaries" { try expectFind("^abc", "abcdef", "abc"); try expectFind("^bcd", "abcdef", null); try expectFind("def$", "abcdef", "def"); try expectFind("cde$", "abcdef", null); try expectFind("^$", "", ""); try expectFind("\\bcat\\b", "a cat sat", "cat"); try expectFind("\\bcat\\b", "concatenate", null); try expectFind("\\Bcat\\B", "concatenate", "cat"); try expectFind("\\Aab", "abc", "ab"); try expectFind("bc\\z", "abc", "bc"); // `$` also matches before a newline ending the text; `\z` never does, // and `\Z` always does. One trailing newline only. try expectFind("bc$", "abc\n", "bc"); try expectFind("bc$", "abc\n\n", null); try expectFind("bc\\z", "abc\n", null); try expectFind("bc\\Z", "abc\n", "bc"); try expectFind("bc\\Z", "abc", "bc"); try expectFind("^$", "\n", ""); try expectFind("c$", "abc", "c");}
test "captures" { try expectGroups("(\\w+)@(\\w+)", "mail me: jeff@example now", &.{ "jeff@example", "jeff", "example" }); try expectGroups("(a(b)c)d", "abcd", &.{ "abcd", "abc", "b" }); try expectGroups("(a)|(b)", "b", &.{ "b", null, "b" }); try expectGroups("(a)?b", "b", &.{ "b", null }); try expectGroups("(?:ab)+(c)", "ababc", &.{ "ababc", "c" }); // Captures persist across repeat iterations (PCRE semantics, not JS): // group 1 keeps "a" from the first iteration. try expectGroups("(?:(a)|(b))+", "ab", &.{ "ab", "a", "b" });}
test "named groups" { var re = try Regex.compile(gpa, "(?<year>\\d{4})-(?<month>\\d{2})"); defer re.deinit(); try std.testing.expectEqual(@as(?u8, 1), re.groupIndex("year")); try std.testing.expectEqual(@as(?u8, 2), re.groupIndex("month")); try std.testing.expectEqual(@as(?u8, null), re.groupIndex("day")); var m = (try re.find(gpa, "on 2026-08-30 we")).?; defer m.deinit(gpa); try std.testing.expectEqualStrings("2026", m.group(re.groupIndex("year").?).?.slice("on 2026-08-30 we"));}
test "utf-8 semantics" { try expectFind("h.llo", "xhéllo", "héllo"); // . is one codepoint try expectFind("é+", "aééb", "éé"); try expectFind("[à-ö]+", "xàéöy", "àéö"); try expectFind("héllo", "say héllo!", "héllo"); try expectFind("\\x{1F600}+", "hi😀😀!", "😀😀"); try expectGroups("(.)(.)", "é€x", &.{ "é€", "é", "€" });}
test "flags" { var re = try Regex.compileWithFlags(gpa, "hello", .{ .case_insensitive = true }); defer re.deinit(); try std.testing.expect(try re.isMatch(gpa, "say HeLLo"));
var re2 = try Regex.compileWithFlags(gpa, "^b$", .{ .multiline = true }); defer re2.deinit(); try std.testing.expect(try re2.isMatch(gpa, "a\nb\nc")); var re3 = try Regex.compile(gpa, "^b$"); defer re3.deinit(); try std.testing.expect(!try re3.isMatch(gpa, "a\nb\nc"));
var re4 = try Regex.compileWithFlags(gpa, "a.b", .{ .dot_all = true }); defer re4.deinit(); try std.testing.expect(try re4.isMatch(gpa, "a\nb")); var re5 = try Regex.compile(gpa, "a.b"); defer re5.deinit(); try std.testing.expect(!try re5.isMatch(gpa, "a\nb"));
var re6 = try Regex.compileWithFlags(gpa, "[a-z]+", .{ .case_insensitive = true }); defer re6.deinit(); try std.testing.expect(try re6.isMatch(gpa, "ABC"));}
test "inline flags" { try expectFind("(?i)hello", "say HeLLo", "HeLLo"); try expectFind("(?i)[a-z]+", "ABC", "ABC"); // Takes effect mid-pattern... try expectFind("a(?i)b", "aB", "aB"); try expectFind("a(?i)b", "Ab", null); // ...and is scoped to the enclosing group. try expectFind("(a(?i)b)c", "aBc", "aBc"); try expectFind("(a(?i)b)c", "aBC", null); try expectFind("(?i:ab)c", "ABc", "ABc"); try expectFind("(?i:a(?-i:b))", "Ab", "Ab"); try expectFind("(?i:a(?-i:b))", "AB", null); // Persists across | until the group ends (PCRE semantics). try expectFind("(?:x(?i)a|b)", "B", "B"); // m and s. try expectFind("(?m)^b$", "a\nb\nc", "b"); try expectFind("(?s)a.b", "a\nb", "a\nb"); try expectFind("(?s:a.)b", "a\nb", "a\nb"); try expectFind("a.(?s)b", "a\nb", null); // too late for the earlier dot
// Clearing a flag set via compileWithFlags. var re = try Regex.compileWithFlags(gpa, "a(?-i)b", .{ .case_insensitive = true }); defer re.deinit(); try std.testing.expect(try re.isMatch(gpa, "Ab")); try std.testing.expect(!try re.isMatch(gpa, "aB"));
// Case-insensitive backreference comparison. try expectFind("(?i)(abc)-\\1", "xABc-abCx", "ABc-abC"); var re2 = try Regex.compile(gpa, "(abc)-(?i)\\1"); defer re2.deinit(); try std.testing.expect(try re2.isMatch(gpa, "abc-ABC"));}
test "inline flags at comptime" { const re = comptime Regex.compileComptime("(?i)h(?-i:ell)o"); try std.testing.expect(try re.isMatch(gpa, "HellO")); try std.testing.expect(!try re.isMatch(gpa, "hELLo"));}
test "engine selection" { var re = try Regex.compile(gpa, "a+b"); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.pike, re.fallback_engine); var re2 = try Regex.compile(gpa, "(a)\\1"); defer re2.deinit(); try std.testing.expectEqual(zregex.Engine.backtrack, re2.fallback_engine); var re3 = try Regex.compile(gpa, "(?=a)b"); defer re3.deinit(); try std.testing.expectEqual(zregex.Engine.backtrack, re3.fallback_engine);}
test "backreferences" { try expectFind("(a+)\\1", "aaaa", "aaaa"); try expectFind("(a+)\\1", "aba", null); try expectGroups("(\\w+) \\1", "say ho ho!", &.{ "ho ho", "ho" }); try expectFind("(?<q>['\"]).*?\\k<q>", "say \"hi' there\" ok", "\"hi' there\""); // A backreference to a group that never participated fails, as in PCRE. try expectFind("(?:(a)|b)\\1c", "bc", null); try expectFind("(a)?\\1b", "b", null); try expectFind("(a)\\1b", "aab", "aab"); // it does participate here}
test "lookaround" { try expectFind("\\w+(?=!)", "hey you! there", "you"); try expectFind("\\w+(?=!)", "hey you there", null); try expectFind("a(?!b)", "ab ac", "a"); try expectGroups("(?<=\\$)(\\d+)", "cost: $42 now", &.{ "42", "42" }); try expectFind("(?<!\\$)\\b\\d+", "$42 43", "43"); // Variable-length lookbehind. try expectFind("(?<=ab+)c", "abbbc", "c"); try expectFind("(?<=ab+)c", "ac", null);}
test "no catastrophic backtracking without backrefs" { // Classic blowup pattern; on the Pike VM this is linear and just fails. var re = try Regex.compile(gpa, "(a+)+$"); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.pike, re.fallback_engine); const haystack = @as([60]u8, @splat('a')) ++ "b"; try std.testing.expect(!try re.isMatch(gpa, haystack));}
test "empty-body loops terminate" { try expectFind("(?:a*)*b", "aaab", "aaab"); try expectFind("(?:a*)*b", "ccc", null); try expectFind("(a*)*b", "aab", "aab"); try expectFind("(|a)*b", "aab", "aab"); // Same shapes through the backtracker (lookahead forces it). try expectFind("(?=a)(?:a*)*b", "aaab", "aaab"); try expectFind("(?=x)(x*)*y", "xxy", "xxy");}
test "step limit" { var re = try Regex.compile(gpa, "(a+)+\\1$"); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.backtrack, re.fallback_engine); re.max_steps = 1000; const haystack = @as([40]u8, @splat('a')) ++ "b"; try std.testing.expectError(error.StepLimitExceeded, re.isMatch(gpa, haystack));}
test "iterator" { var re = try Regex.compile(gpa, "\\d+"); defer re.deinit(); const haystack = "a1b22c333"; var it = re.iterator(gpa, haystack); defer it.deinit(); const expected = [_][]const u8{ "1", "22", "333" }; for (expected) |e| { var m = (try it.next()).?; defer m.deinit(gpa); try std.testing.expectEqualStrings(e, m.span().slice(haystack)); } try std.testing.expectEqual(@as(?zregex.Match, null), try it.next()); try std.testing.expectEqual(@as(?zregex.Match, null), try it.next());}
test "iterator with empty matches" { var re = try Regex.compile(gpa, "a*"); defer re.deinit(); const haystack = "baa"; var it = re.iterator(gpa, haystack); defer it.deinit(); var spans: std.ArrayList(zregex.Span) = .empty; defer spans.deinit(gpa); while (try it.next()) |m| { var mm = m; defer mm.deinit(gpa); try spans.append(gpa, mm.span()); } // Empty at 0, "aa" at 1, empty at end. try std.testing.expectEqualSlices(zregex.Span, &.{ .{ .start = 0, .end = 0 }, .{ .start = 1, .end = 3 }, .{ .start = 3, .end = 3 }, }, spans.items);}
test "comptime compilation" { const re = comptime Regex.compileComptime("(\\d{3})-(\\d{4})"); try std.testing.expectEqual(zregex.Engine.pike, re.fallback_engine); var m = (try re.find(gpa, "call 555-0199 now")).?; defer m.deinit(gpa); try std.testing.expectEqualStrings("555-0199", m.span().slice("call 555-0199 now")); try std.testing.expectEqualStrings("555", m.groups[1].?.slice("call 555-0199 now")); // deinit on a comptime-compiled regex is a safe no-op. var copy = re; copy.deinit();}
test "comptime compilation with flags, names, and backtracking features" { const re = comptime Regex.compileComptimeWithFlags( "(?<word>\\w+) \\k<word>", .{ .case_insensitive = true }, ); try std.testing.expectEqual(zregex.Engine.backtrack, re.fallback_engine); try std.testing.expectEqual(@as(?u8, 1), re.groupIndex("word")); try std.testing.expect(try re.isMatch(gpa, "Hey HEY!")); try std.testing.expect(!try re.isMatch(gpa, "hey ho"));}
test "findAt and spans" { var re = try Regex.compile(gpa, "ab"); defer re.deinit(); var m = (try re.findAt(gpa, "abab", 1)).?; defer m.deinit(gpa); try std.testing.expectEqual(zregex.Span{ .start = 2, .end = 4 }, m.span());}
test "compile errors surface" { try std.testing.expectError(error.UnbalancedParen, Regex.compile(gpa, "(a")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "+")); try std.testing.expectError(error.ProgramTooLarge, Regex.compile(gpa, "(?:(?:a{1000}){1000}){1000}"));}
test "prefilter analysis" { const cases = [_]struct { pattern: []const u8, flags: zregex.Flags = .{}, usable: bool, single: ?u8 = null, }{ .{ .pattern = "abc", .usable = true, .single = 'a' }, .{ .pattern = "^abc$", .usable = true, .single = 'a' }, .{ .pattern = "(?i)q", .usable = true }, // {q, Q} .{ .pattern = "cat|dog", .usable = true }, .{ .pattern = "a*bc", .usable = true }, // {a, b} .{ .pattern = "(?=x)yz", .usable = true, .single = 'y' }, .{ .pattern = "(a)\\1", .usable = true, .single = 'a' }, .{ .pattern = ".x", .usable = false }, .{ .pattern = "[^a]x", .usable = false }, .{ .pattern = "a?b?", .usable = false }, // can match empty }; inline for (cases) |c| { var re = try Regex.compileWithFlags(gpa, c.pattern, c.flags); defer re.deinit(); try std.testing.expectEqual(c.usable, re.prefilter.usable); if (c.single) |b| try std.testing.expectEqual(@as(?u8, b), re.prefilter.single); } // Set contents: a*bc can start with 'a' or 'b' but not 'c'. var re = try Regex.compile(gpa, "a*bc"); defer re.deinit(); try std.testing.expect(re.prefilter.bytes['a']); try std.testing.expect(re.prefilter.bytes['b']); try std.testing.expect(!re.prefilter.bytes['c']); // (?i) folds. var re2 = try Regex.compile(gpa, "(?i)q"); defer re2.deinit(); try std.testing.expect(re2.prefilter.bytes['q']); try std.testing.expect(re2.prefilter.bytes['Q']);}
test "prefilter never stops mid-codepoint" { // U+00A9 (©) is 0xC2 0xA9 in UTF-8; 'é' is 0xC3 0xA9. A lone invalid // 0xA9 byte decodes to U+00A9 via the fallback, but the 0xA9 inside a // valid 'é' must not: matches may only start at decode boundaries. // // 0xA9 is therefore a candidate byte *and* a continuation byte, which is // exactly the shape that stops the scan from stepping a byte at a time. var re = try Regex.compile(gpa, "\u{A9}"); defer re.deinit(); try std.testing.expect(!re.prefilter.byte_steppable); try std.testing.expect(!try re.isMatch(gpa, "é")); // C3 A9: no boundary at the A9 try std.testing.expect(try re.isMatch(gpa, "x\xA9y")); // lone invalid byte: matches try std.testing.expect(try re.isMatch(gpa, "x\u{A9}y")); // real ©}
test "prefilter honors utf-8 lead bytes and raw fallback" { var re = try Regex.compile(gpa, "é+"); defer re.deinit(); try std.testing.expect(re.prefilter.usable); try std.testing.expect(re.prefilter.bytes[0xC3]); // é lead byte try std.testing.expect(re.prefilter.bytes[0xE9]); // raw fallback for U+E9 try std.testing.expect(!re.prefilter.bytes['e']); try std.testing.expect(try re.isMatch(gpa, "abcé")); try std.testing.expect(try re.isMatch(gpa, "ab\xE9cd")); // invalid byte fallback}
test "dfa and pike agree on every match and capture" { const patterns = [_][]const u8{ "abc", "a+", "a+?", "a*b", "(a|ab)(c|bcd)", "<.+>", "<.+?>", "(\\w+)@([\\w.]+)", "^\\w+", "\\w+$", "\\bcat\\b", "\\Babc", "x{2,4}", "(a*)*b", "(|a)*b", "[^x]y", ".at", "a$", "^", "a?", "é+", "(.)(.)", "\\d{2,}", "colou?r", "(?:ab|cd)+", "(a)(b)?c?", "^$", "\\x{1F600}+", }; const haystacks = [_][]const u8{ "", "a", "abc abc", "aaabbb", "the cat sat on a mat", "x@y.z mail alice@example.org!", "line one\nline two\ncat\n", "xxxxx", "abcbcd", "aébé\xFFcé", "color colour", "ababcdab", "hi 😀😀 there", "wordcat catword cat", "12 345 6789", }; for (patterns) |pat| { var re = try Regex.compile(gpa, pat); defer re.deinit(); if (re.engine != .pike) continue; for (haystacks) |hay| { re.dfa_mode = .on; var it_dfa = re.iterator(gpa, hay); defer it_dfa.deinit(); re.dfa_mode = .off; var it_pike = re.iterator(gpa, hay); defer it_pike.deinit(); while (true) { re.dfa_mode = .on; const a = try it_dfa.next(); re.dfa_mode = .off; const b = try it_pike.next(); if (a == null or b == null) { try std.testing.expectEqual(a == null, b == null); break; } var ma = a.?; defer ma.deinit(gpa); var mb = b.?; defer mb.deinit(gpa); std.testing.expectEqualSlices(?zregex.Span, mb.groups, ma.groups) catch |err| { std.debug.print("pattern={s} haystack={f}\n", .{ pat, std.zig.fmtString(hay) }); return err; }; } } }}
test "dfa handles findAt context correctly" { // \b at a findAt start must see the previous character. var re = try Regex.compile(gpa, "\\bcat"); defer re.deinit(); var m = try re.findAt(gpa, "concat cat", 3); try std.testing.expect(m != null); // finds " cat", not "cat" inside concat try std.testing.expectEqual(@as(usize, 7), m.?.span().start); m.?.deinit(gpa); // ^ must not hold at a mid-string start position. var re2 = try Regex.compile(gpa, "^x"); defer re2.deinit(); try std.testing.expectEqual(@as(?zregex.Match, null), try re2.findAt(gpa, "yx", 1));}
test "fused repeats in the backtracker" { // Greedy gives back one codepoint at a time down to min: a{2,} must // shrink from 4 to 2 so the backref can match the rest. try expectGroups("(a{2,})\\1", "aaaa", &.{ "aaaa", "aa" }); // Bounded {n,m}. try expectFind("(?=\\d)\\d{2,4}", "12345 1", "1234"); try expectFind("(?=\\d)\\d{2,4}x", "12345x", "2345x"); try expectFind("(?=\\d)\\d{2,4}", "9!", null); // Lazy fused repeat grows one at a time. try expectGroups("(a+?)a\\1", "aaaa", &.{ "aaa", "a" }); try expectFind("(?<=x).*?y", "xaay", "aay"); // UTF-8 child codepoints step correctly in both directions. try expectFind("(?=é)é+x", "ééx", "ééx"); try expectFind("(é{2,})\\1", "éééé", "éééé"); // A capturing group inside a repeat must not fuse (captures per iteration). try expectGroups("(?=a)(a)+b", "aab", &.{ "aab", "a" }); // Non-capturing wrapper does fuse and stays correct. try expectFind("(?=a)(?:a)+b", "aab", "aab"); // Fused rep at the start feeds the prefilter. var re = try Regex.compile(gpa, "\\d+(?=%)"); defer re.deinit(); try std.testing.expect(re.prefilter.usable); try std.testing.expect(re.prefilter.bytes['5']); try std.testing.expect(!re.prefilter.bytes['x']); var m = (try re.find(gpa, "at 15% now")).?; defer m.deinit(gpa); try std.testing.expectEqualStrings("15", m.span().slice("at 15% now"));}
test "memoization tames exponential backtracking" { // 2^30-ish unmemoized; the memo makes it polynomial and it just fails. var re = try Regex.compile(gpa, "(a+)+\\1$"); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.backtrack, re.fallback_engine); const haystack = @as([30]u8, @splat('a')) ++ "b"; try std.testing.expect(!try re.isMatch(gpa, haystack)); // Without the memo the same search must blow the step budget. re.memo = false; re.max_steps = 100_000; try std.testing.expectError(error.StepLimitExceeded, re.isMatch(gpa, haystack));
// Alternation-driven blowup, forced onto the backtracker by a lookahead. var re2 = try Regex.compile(gpa, "(?=a)(a|a)*c$"); defer re2.deinit(); const haystack2 = @as([26]u8, @splat('a')) ++ "b"; try std.testing.expect(!try re2.isMatch(gpa, haystack2)); re2.memo = false; re2.max_steps = 100_000; try std.testing.expectError(error.StepLimitExceeded, re2.isMatch(gpa, haystack2));}
test "memoization preserves semantics" { const cases = [_]struct { p: []const u8, h: []const u8 }{ .{ .p = "(a+)+\\1", .h = "aaaaaa" }, .{ .p = "(a|ab)+(c|bc)\\1", .h = "ababcab" }, .{ .p = "(\\w+) \\1", .h = "hey hey ho ho" }, .{ .p = "(?=(a+))(a|aa)+b", .h = "aaaab" }, .{ .p = "(?:(x)|(y))*\\1\\2", .h = "xyxy" }, .{ .p = "((a*)b\\2)+", .h = "aabaab ab" }, .{ .p = "(a{2,})\\1", .h = "aaaaa" }, .{ .p = "(?<=(b))a\\1", .h = "bab" }, }; for (cases) |c| { var re = try Regex.compile(gpa, c.p); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.backtrack, re.fallback_engine); re.memo = true; const with = try re.find(gpa, c.h); re.memo = false; const without = try re.find(gpa, c.h); if (with == null or without == null) { try std.testing.expectEqual(with == null, without == null); continue; } var a = with.?; defer a.deinit(gpa); var b = without.?; defer b.deinit(gpa); try std.testing.expectEqualSlices(?zregex.Span, b.groups, a.groups); }}
test "lookahead sub-runs are re-evaluated correctly under memoization" { // The lookahead runs at several positions across attempts; sub-run // states must not be poisoned by earlier (successful) runs. try expectGroups("(?=(a+))\\1b", "aaab", &.{ "aaab", "aaa" }); try expectGroups("(?=(\\w+))(\\w)x", "ab cx", &.{ "cx", "cx", "c" }); // Atomic lookaround: the captured \\w+ cannot be retried shorter, so the // backref can never fit (PCRE agrees: no match). try expectFind("(?=(\\w+))x\\1", "axaa", null);}
test "literal retry scanning preserves greedy semantics" { // The scan jumps between '-' occurrences largest-first: same result as // stepping back one position at a time. try expectGroups("(?=.)(\\S+)-(\\S+)", "a-b-c", &.{ "a-b-c", "a-b", "c" }); try expectFind("(\\w+)-\\1", "aaa-bbb ab-ab x", "ab-ab"); // Case-insensitive continuation char uses the folded reverse scan. try expectFind("(?i)(\\d+)A\\1", "x12a12y", "12a12"); // Lookahead continuation: scan for the looked-at char. try expectGroups("(\\w+)(?=@)", "mail jeff@x", &.{ "jeff", "jeff" }); // No occurrence in range: the frame dies without a match. try expectFind("(\\w{2,})=\\1", "aaaa bbbb", null);}
test "dynamic lead-run skipping with backrefs" { // Failing words never execute the backref, so whole runs are skipped; // the word that does match must still be found with correct captures. try expectGroups("(\\w{3,})-\\1", "aaaa bbbb ccc-ccc dd", &.{ "ccc-ccc", "ccc" }); try expectFind("(\\w+) \\1", "aaaa bbbb cc cc", "cc cc"); // Backref executed but failed: no skip, later start in same run matches. try expectFind("(\\w+)\\1", "xabab", "abab");}
test "jit agrees with the interpreters on every match and capture" { if (!zregex.jit_available) return error.SkipZigTest; // On x86-64 the two vector widths generate different code for the same // repeats, so each is checked against the interpreters in turn. if (@import("builtin").cpu.arch == .x86_64) { defer zregex.overrideAvx2(null); for ([_]bool{ false, true }) |avx2| { zregex.overrideAvx2(avx2); try jitDifferential(); } } else { try jitDifferential(); }}
fn jitDifferential() !void { // Deliberately mixes the constructs the generator inlines (fused repeats, // classes, assertions, single-codepoint lookaround) with the ones it hands // to helpers (non-ASCII literals and classes, backreferences). const patterns = [_][]const u8{ "abc", "a+", "a+?", "a*b", "(a|ab)(c|bcd)", "<.+>", "<.+?>", "(\\w+)@([\\w.]+)", "^\\w+", "\\w+$", "\\bcat\\b", "\\Babc", "x{2,4}", "(a*)*b", "(|a)*b", "[^x]y", ".at", "a$", "^", "a?", "é+", "(.)(.)", "\\d{2,}", "colou?r", "(?:ab|cd)+", "(a)(b)?c?", "^$", "\\x{1F600}+", "(\\w+) \\1", "(a+)\\1", "(\\w{2,})-\\1", "(?i)(abc)\\1", "\\w+(?=@)", "a(?!b)", "(?<=\\$)\\d+", "(?<!x)y", "(?i)HeLLo", "(?m)^b$", "(?s)a.b", "[à-ö]+", "(a{2,})\\1", "(?=\\d)\\d{2,4}", "(\\S+)-(\\S+)", "\\d{3,5}x", }; const haystacks = [_][]const u8{ "", "a", "abc abc", "aaabbb", "the cat sat on a mat", "x@y.z mail alice@example.org!", "line one\nline two\ncat\n", "xxxxx", "abcbcd", "aébé\xFFcé", "color colour", "ababcdab", "hi 😀😀 there", "wordcat catword cat", "12 345 6789", "say ho ho and hey hey!", "cost: $42, was $7", "aa-aa bb-bb cc-dd", "ABC abc AbC abcabc", "aaaaaaaaaaaaaaaaaaaab", }; for (patterns) |pat| { var re = try Regex.compile(gpa, pat); defer re.deinit(); if (re.jit_code == null) continue; for (haystacks) |hay| { re.jit_mode = .on; var it_jit = re.iterator(gpa, hay); defer it_jit.deinit(); re.jit_mode = .off; var it_ref = re.iterator(gpa, hay); defer it_ref.deinit(); while (true) { re.jit_mode = .on; const a = try it_jit.next(); re.jit_mode = .off; const b = try it_ref.next(); if (a == null or b == null) { std.testing.expectEqual(b == null, a == null) catch |err| { std.debug.print("pattern={s} haystack={f}\n", .{ pat, std.zig.fmtString(hay) }); return err; }; break; } var ma = a.?; defer ma.deinit(gpa); var mb = b.?; defer mb.deinit(gpa); std.testing.expectEqualSlices(?zregex.Span, mb.groups, ma.groups) catch |err| { std.debug.print("pattern={s} haystack={f}\n", .{ pat, std.zig.fmtString(hay) }); return err; }; } } }}
test "jit bails instead of blowing up, and the answer still comes back" { if (!zregex.jit_available) return error.SkipZigTest; // The generated code has no memoization, so this exhausts its budget; the // memoizing interpreter behind it still produces the right answer. var re = try Regex.compile(gpa, "(a+)+\\1$"); defer re.deinit(); try std.testing.expectEqual(zregex.Engine.jit, re.engine); try std.testing.expect(!try re.isMatch(gpa, @as([30]u8, @splat('a')) ++ "b"));}
test "greedy give-back happens exactly where a shorter run could help" { // '-' is not a word character, so no shorter \w+ run can be followed by // one: both engines skip the retry entirely. Matches must be unaffected. try expectGroups("(\\w+)-(\\w+)", "ab-cd", &.{ "ab-cd", "ab", "cd" }); try expectFind("\\w+-\\w+", "xx yy-zz", "yy-zz"); try expectGroups("(\\w{3,})-\\1", "aaaa bbbb ccc-ccc dd", &.{ "ccc-ccc", "ccc" }); // Here the continuation *is* a member of the repeated class, so the // give-back is real and the shorter run is what matches. try expectGroups("(\\S+)-(\\S+)", "a-b-c", &.{ "a-b-c", "a-b", "c" }); try expectFind("[a-z]+ing", "singing", "singing"); try expectFind("[a-z]+ab", "xabab", "xabab"); try expectFind("\\w+_\\w+", "a_b", "a_b"); // '_' is a word char // Case-insensitive: the fold partner counts as a member too. try expectFind("(?i)[a-z]+X", "fooxbar", "foox");}
test "regressions found by differential fuzzing" { // A deferred low-priority branch used to be marked visited as soon as it // was queued, so a higher-priority path reaching the same instruction // later was dropped along with its captures. Group 1 must be the empty // match the `\b` branch makes, not unset. try expectGroups("(?:(\\b)|\\d){0,1}[ab1]", " ba1", &.{ "b", "" });
// Re-entering a group overwrites its start before its end, so a // backreference reached while the group is open saw start > end and // sliced backwards. It must behave as an unset group and match empty. var re = try Regex.compile(gpa, "((a)|b)+\\2"); defer re.deinit(); // Group 2 never participates on the path that reaches the // backreference, so this cannot match — what matters is that it does // not slice backwards while deciding so. try std.testing.expect(!try re.isMatch(gpa, "ab"));
// A loop iteration that consumes nothing ends the loop; it does not fail // and force the body to consume. `(a*?)*` must therefore match empty, // which is what PCRE and Python do. try expectGroups("(a*?)*", "aa", &.{ "", "" }); try expectFind("(a*)*", "aa", "aa"); try expectFind("(?:a*?)*b", "aab", "aab"); try expectFind("(?:a*)*b", "aab", "aab");}
test "prefilter skipping does not strand the Pike VM" { // Skipping to the next candidate byte leaves visited marks behind from // the position just abandoned. Reusing that generation blocked the // assertion here, so no match was found at all. try expectFind("@?\\Bb", "@ab", "b"); try expectFind("(?:@)?\\Bb", "@ab", "b"); try expectFind("a?\\Bb", "@ab", "ab"); // leftmost: the optional 'a' is taken try expectGroups("(@)?\\Bb", "@ab", &.{ "b", null });}
test "POSIX bracket classes" { // `[[:name:]]` is only meaningful inside a class, and ASCII-only, which // is what `\d`, `\w` and `\s` already are here and what PCRE gives these // without PCRE2_UCP. Every span below was checked against PCRE2. // // Before these were implemented the inner brackets were read as ordinary // members, so `[[:digit:]]` quietly meant "one of `[:digt]`" and matched // the wrong thing rather than failing. const hay = "ab12:] _-A~ "; try expectFind("[[:digit:]]+", hay, "12"); try expectFind("[[:alpha:]]+", hay, "ab"); try expectFind("[[:alnum:]]+", hay, "ab12"); try expectFind("[[:upper:]]+", hay, "A"); try expectFind("[[:lower:]]+", hay, "ab"); try expectFind("[[:space:]]+", hay, " "); try expectFind("[[:blank:]]+", hay, " "); try expectFind("[[:punct:]]+", hay, ":]"); try expectFind("[[:xdigit:]]+", hay, "ab12"); try expectFind("[[:word:]]+", hay, "ab12"); try expectFind("[[:graph:]]+", hay, "ab12:]"); try expectFind("[[:print:]]+", hay, hay); try expectFind("[[:ascii:]]+", hay, hay); try expectFind("[[:cntrl:]]+", hay, null); // Mixed with ordinary members, and both ways of negating. try expectFind("[[:alpha:]0-9]+", hay, "ab12"); try expectFind("[[:^digit:]]+", hay, "ab"); try expectFind("[^[:digit:]]+", hay, "ab"); // A `[` that does not open one stays the literal PCRE makes it, so a // class missing the `:]` terminator still reads as ordinary members. try expectFind("[[]", "x[y", "["); try expectFind("[[:a]+", "ab12", "a"); // Anything terminated by `:]` is meant as one of these, so a name nobody // defines is an error -- as in PCRE, and rather than falling back to // reading the characters one at a time. The names are case-sensitive. try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:bogus:]]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:^bogus:]]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:DIGIT:]]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:a-z:]]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[::]]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:^:]]"));}
test "a caseless POSIX complement closes over case before complementing" { // Found by tools/oracle.zig. `[:^lower:]` is complemented while the // pattern is parsed, but `(?i)` is not applied until match time, so // without closing the set over case first the two happen in the wrong // order: `a` folded to `A`, found it in the complement of `a-z`, and // matched. PCRE reads the class as "not a letter of either case". // // `lower` and `upper` are the only names this can be seen through -- // every other set, and `\D`, `\W` and `\S` too, already holds both cases // of everything in it or neither. try expectFind("(?i:[[:^lower:]])", "a", null); try expectFind("(?i:[[:^lower:]])", "A", null); try expectFind("(?i:[[:^upper:]])", "A", null); try expectFind("(?i:[[:^upper:]])", "z", null); // Characters with no case are unaffected, and so is the whole thing // without the flag. try expectFind("(?i:[[:^lower:]])", "0", "0"); try expectFind("(?i:[[:^lower:]])", "_", "_"); try expectFind("[[:^lower:]]", "A", "A"); try expectFind("[[:^lower:]]", "a", null); try expectFind("(?i:[[:^alpha:]])", "Q", null); try expectFind("(?i:[[:^xdigit:]])", "F", null); try expectFind("(?i:[[:^digit:]])", "a", "a"); try expectFind("(?i:[[:^word:]])", "-", "-");}
test "case folding is Unicode, not ASCII" { // Found by running PCRE2's own test corpus through tools/oracle.zig, // where caseless matching of non-ASCII was by far the largest source of // difference. The tables come from CaseFolding.txt, via the uucode // package, and hold simple case folding only -- the `C` and `S` entries. try expectFind("(?i)\u{c1}", "\u{e1}", "\u{e1}"); // Á ~ á try expectFind("(?i)\u{391}+", "\u{3b1}", "\u{3b1}"); // Α ~ α try expectFind("(?i)\u{23a}", "\u{2c65}", "\u{2c65}"); // Ⱥ ~ ⱥ try expectFind("(?i)\u{1e9e}", "\u{df}", "\u{df}"); // ẞ ~ ß
// Three-member classes: `s` also matches the long s, `k` the Kelvin sign. try expectFind("(?i)s", "\u{17f}", "\u{17f}"); try expectFind("(?i)\u{17f}", "S", "S"); try expectFind("(?i)k", "\u{212a}", "\u{212a}"); try expectFind("(?i)\u{212a}", "k", "k");
// Classes are closed over case where they are built, so nothing folds // while matching and every engine sees an ordinary class. try expectFind("(?i)[z\u{df}]+", "\u{1e9e}", "\u{1e9e}"); try expectFind("(?i)[\u{105}-\u{109}]", "\u{104}", "\u{104}");
// A complement is taken of the closed set, never closed afterwards. The // Kelvin sign is a non-word character, so closing `\W` after the fact // would drag `k` and `K` into it. try expectFind("(?i)\\W", "k", null); try expectFind("(?i)[\\W]", "k", null); try expectFind("(?i)[^k]", "k", null); try expectFind("(?i)[^k]", "\u{212a}", null); try expectFind("(?i)[[:^lower:]]", "a", null); try expectFind("(?i)[[:^lower:]]", "0", "0");
// Simple case folding is the `C` and `S` entries of CaseFolding.txt and // nothing else. `İ` (U+0130) has only a full mapping and a Turkic one, so // it folds to itself; PCRE matches it against neither `i` nor `I`. try expectFind("(?i)i", "\u{130}", null); try expectFind("(?i)\u{130}", "i", null); try expectFind("(?i)\u{130}", "I", null); try expectFind("(?i)[i]", "\u{130}", null);}
test "a caseless backreference may match a different number of bytes" { // `Ⱥ` (U+023A) is two bytes and the `ⱥ` (U+2C65) it folds together with // is three, so the text a backreference matches can be longer or shorter // than the text it captured. Comparing byte by byte -- which is what this // did while folding was ASCII-only, where the two cases of a character // always have the same length -- got both the comparison and how far to // advance wrong. try expectFind( "(?i)(\u{23a}\u{23a}\u{23a})\\1", "\u{23a}\u{23a}\u{23a}\u{2c65}\u{2c65}\u{2c65}", "\u{23a}\u{23a}\u{23a}\u{2c65}\u{2c65}\u{2c65}", ); try expectFind( "(?i)(\u{2c65}\u{2c65})\\1", "\u{2c65}\u{2c65}\u{23a}\u{23a}", "\u{2c65}\u{2c65}\u{23a}\u{23a}", ); try expectFind("(?i)(\u{de})\\1", "\u{de}\u{fe}", "\u{de}\u{fe}"); try expectFind("(?i)(.) \\1", "A a", "A a");}
test "relaxed brace quantifiers" { // PCRE ignores space and horizontal tab after `{`, before `}`, and on // either side of the comma, and reads a missing minimum as zero. A brace // pair holding no number at all is not a quantifier and stays literal. // Found by running PCRE2's own test corpus. try expectFind("a{,3}B", "aaaB", "aaaB"); try expectFind("x{,2}(x|b)", "xxb", "xxb"); try expectFind("a{ 1,2 }", "aa", "aa"); try expectFind("a{ 1 , 2 }", "aa", "aa"); try expectFind("A{ ,3}", "AAAAAA", "AAA"); try expectFind("A{ 3, }", "AAAA", "AAAA"); // Not quantifiers: no number between the braces. try expectFind("A{,}B", "A{,}B", "A{,}B"); try expectFind("A{ , }B", "A{ , }B", "A{ , }B"); try expectFind("X{}", "ZZX{}YZ", "X{}"); // Still not a quantifier: holding something that is not a bound. try expectFind("X{12ABC}", "ZZX{12ABC}Y", "X{12ABC}");}
test "horizontal and vertical whitespace classes" { // In PCRE `\v` is the vertical whitespace class, not the vertical tab -- // Python and JavaScript are the ones that read it as a character, and // zregex used to follow them. Both lists reach past ASCII even without // PCRE2_UCP, because both are fixed sets rather than Unicode properties. try expectFind("\\v", "a\nb", "\n"); try expectFind("\\v", "a\tb", null); try expectFind("a\\vb", "a\nb", "a\nb"); try expectFind("\\v", "a\u{2028}", "\u{2028}"); try expectFind("\\h", "a\tb", "\t"); try expectFind("\\h", "a b", " "); try expectFind("\\h", "\u{3000}x", "\u{3000}"); try expectFind("\\H", "\tab", "a"); try expectFind("\\V", "\nab", "a"); try expectFind("[\\v]", "a\nb", "\n"); try expectFind("[^\\v]+", "\nab", "ab");}
test "a variable-length lookbehind takes the longest match" { // PCRE tries the longest lookbehind text first, so the group captures all // four digits rather than the last one. zregex searched from the shortest // and reported the other end of the range. try expectGroups("(?<=(\\d{1,4}))X", "1234X", &.{ "X", "1234" }); try expectGroups("(?<=(a{1,3}))X", "aaaX", &.{ "X", "aaa" }); try expectGroups("(?<=(ab|b))X", "abX", &.{ "X", "ab" }); // Unbounded lookbehind has no maximum to start from, so it begins at the // start of the haystack; the answer is still the longest. try expectGroups("(?<=(a+))X", "aaaX", &.{ "X", "aaa" });}
test "iteration retries for a longer match where it found an empty one" { // After an empty match, the next thing to try is a longer match in the // same place -- not the next position. `.*?` reports empty at 0 and then // `a` and `b` in turn; advancing straight away reported empty at 0, 1 and 2 // and never the text between them. PCRE does this (it is the loop pcre2demo.c // documents) and so does Python; zregex was the odd one out, which only // showed once the oracle started comparing every match rather than the // leftmost one. const cases = [_]struct { pat: []const u8, hay: []const u8, want: []const zregex.Span, }{ .{ .pat = ".*?", .hay = "ab", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 0, .end = 1 }, .{ .start = 1, .end = 1 }, .{ .start = 1, .end = 2 }, .{ .start = 2, .end = 2 }, } }, // The retry fails here -- nothing longer starts at 0 -- so the search // carries on from the next codepoint, as it always did. .{ .pat = "a*", .hay = "bab", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 1, .end = 2 }, .{ .start = 2, .end = 2 }, .{ .start = 3, .end = 3 }, } }, .{ .pat = "(?:)", .hay = "ab", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 1, .end = 1 }, .{ .start = 2, .end = 2 }, } }, // Stepping past an empty match moves a whole codepoint, not a byte. .{ .pat = "b*", .hay = "\u{20ac}b", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 3, .end = 4 }, .{ .start = 4, .end = 4 }, } }, }; for (cases) |c| { var re = try Regex.compile(gpa, c.pat); defer re.deinit(); var got: std.ArrayList(zregex.Span) = .empty; defer got.deinit(gpa); var it = re.iterator(gpa, c.hay); defer it.deinit(); while (try it.next()) |m| { var mm = m; defer mm.deinit(gpa); try got.append(gpa, mm.span()); } std.testing.expectEqualSlices(zregex.Span, c.want, got.items) catch |err| { std.debug.print("pattern={s} haystack={s}\n", .{ c.pat, c.hay }); return err; }; }}
test "NUL is an ordinary character" { // Nothing here takes a subject as a C string, so a NUL byte is a // character like any other and must not end anything early. It is in both // of the fuzzer's alphabets for that reason; this pins down the answers // it is checked against, all of which PCRE2 agrees with. try expectFind("\\x00", "a\x00b", "\x00"); try expectFind("a\\x00b", "a\x00b", "a\x00b"); try expectFind("\\x00+", "a\x00\x00b", "\x00\x00"); try expectFind("[\\x00-\\x08]", "a\x00b", "\x00"); try expectFind("[^\\x00]+", "a\x00b", "a"); try expectFind(".", "\x00", "\x00"); try expectFind("\\w\\x00", "a\x00", "a\x00"); // A NUL in the middle of a haystack does not stop the search reaching // what is after it. try expectFind("b", "a\x00b", "b"); try expectFind("$", "a\x00", ""); // Group 0 spans the NUL, and a capture may hold one. try expectGroups("(a\\x00)(b)", "a\x00b", &.{ "a\x00b", "a\x00", "b" });}
test "adversarial patterns cannot demand absurd memory" { // Two memory bombs, measured with a byte-counting allocator before the // limits below existed. // // Six nested nullable loops wrapped around a program near the // instruction ceiling made the Pike VM's visited table four million // keys -- instructions times two per guard level -- and one 381-byte // pattern allocated half a gigabyte. The compiler now refuses a program // whose table would pass a million keys; every pattern up to sixteen // thousand instructions keeps all six guard levels, so nothing short of // a deliberately built monster notices. var pat: std.ArrayList(u8) = .empty; defer pat.deinit(gpa); try pat.appendSlice(gpa, "((((((a?)*)*)*)*)*)*"); for (0..60) |_| try pat.appendSlice(gpa, "b{900}"); try std.testing.expectError(error.ProgramTooLarge, Regex.compile(gpa, pat.items));
// The nesting alone is fine: it is the combination with a huge program // that is refused. var re = try Regex.compile(gpa, "((((((a?)*)*)*)*)*)*b"); defer re.deinit(); try expectFind("((((((a?)*)*)*)*)*)*b", "aab", "aab");
// The parse buffers are sized for the worst case at dozens of bytes per // pattern byte, and a pattern of no-ops compiles to almost nothing while // costing all of it: eight megabytes of `(?:)` allocated six hundred. // Patterns are refused past a megabyte, before anything is allocated; // real content runs into the program ceiling two orders of magnitude // sooner, so only no-op spam can ever reach this. pat.clearRetainingCapacity(); for (0..(1 << 18) + 1) |_| try pat.appendSlice(gpa, "(?:)"); try std.testing.expectError(error.PatternTooLong, Regex.compile(gpa, pat.items));}
test "adversarial patterns fail cleanly instead of crashing" { // Compile-time hardening. A pattern is attacker-sized input too: each of // these once either crashed or would have run away, and each must now // come back as an ordinary error in time proportional to its size. // // A long flat pattern used to build a left-leaning concat spine one node // per character, and the compiler's recursive walk overran the stack on // it -- a segfault from a pattern of plain letters -- before the // program-size limit could reject it. The parser now builds balanced // trees, so the walk is log-deep and the limit gets its say. Emission // order is leaf order either way, so the program is unchanged. var big: std.ArrayList(u8) = .empty; defer big.deinit(gpa); for (0..300_000) |_| try big.append(gpa, 'a'); try std.testing.expectError(error.ProgramTooLarge, Regex.compile(gpa, big.items));
// The same spine, made of alternation branches. big.clearRetainingCapacity(); for (0..60_000) |_| try big.appendSlice(gpa, "a|"); try std.testing.expectError(error.ProgramTooLarge, Regex.compile(gpa, big.items));
// Multiplicative counted repeats: a billion-instruction expansion must // be cut off by the counting pass, not walked. try std.testing.expectError(error.ProgramTooLarge, Regex.compile(gpa, "((a{1000}){1000}){1000}"));
// Group nesting past the depth limit. big.clearRetainingCapacity(); for (0..5000) |_| try big.appendSlice(gpa, "(?:"); try big.append(gpa, 'a'); for (0..5000) |_| try big.appendSlice(gpa, ")"); try std.testing.expectError(error.NestingTooDeep, Regex.compile(gpa, big.items));}
test "the step budget bounds a whole scan, not each start position" { // `(a+)\1$` against a run of `a` is quadratic per attempt and runs at // every start position. With the budget granted anew at each start -- // which is what PCRE does with its match limit, and what this library // used to do -- no single attempt ever tripped it, and the scan took // seconds at 24K of input and grew cubically from there; the same input // hangs `grep -P` outright. The budget now covers the whole call, plus // an allowance per input byte so that honest scans of large haystacks // still get work proportional to their size. var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); for (0..2000) |_| try hay.append(gpa, 'a'); try hay.append(gpa, 'b');
var re = try Regex.compile(gpa, "(a+)\\1$"); defer re.deinit(); re.max_steps = 10_000; re.jit_mode = .off; // the JIT bails on its own budget; hold the interpreter to it try std.testing.expectError(error.StepLimitExceeded, re.find(gpa, hay.items));
// The per-byte allowance is what keeps an honest scan alive: the same // pattern over the same haystack with the match present finds it, and a // benign pattern crosses a large haystack without touching the limit. try expectFind("(a+)\\1", "xxaaaax", "aaaa"); var big: std.ArrayList(u8) = .empty; defer big.deinit(gpa); for (0..100_000) |_| try big.append(gpa, 'a'); try big.append(gpa, 'b'); var re2 = try Regex.compile(gpa, "(a?)b\\1"); defer re2.deinit(); const m = (try re2.find(gpa, big.items)) orelse return error.TestUnexpectedResult; var mm = m; defer mm.deinit(gpa); // `a?` must match empty here: taking the `a` at 99,999 leaves the // backreference wanting another one past the end of the input. try std.testing.expectEqual(@as(usize, 100_000), mm.span().start);}
test "a leading class bracket may open a range" { // `]` first in a class is a literal, and an ordinary member in every // other way, so it may be the low end of a range: `[]-b]` runs from `]` // to `b` and takes in the letter `a`. It used to be added as a finished // member, which quietly read that class as the three characters `]`, // `-`, `b`. Found by mutating PCRE2's own test patterns -- the seed was // `a[]-b]e` from testinput1, one deletion away. try expectFind("a[]-b]", "aab", "aa"); try expectFind("[]-b]+", "]^_`ab.", "]^_`ab"); try expectFind("[^]-b]", "a", null); try expectFind("[^]-b]", "x", "x"); try expectFind("(?i)[]-b]", "A", "A"); // Still a literal when no range follows: alone, or with `-` last. try expectFind("[]]", "x]y", "]"); try expectFind("[]-]", "-", "-"); try expectFind("[]-]", "a", null); // A backwards range is an error here as anywhere in a class. try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[]-\x20]"));}
test "a bare assertion cannot be quantified" { // `^*`, `\b+` and the rest are errors in PCRE -- a quantifier must // follow a repeatable item -- and repeating something zero-width never // meant more than writing it once. zregex used to compile them, which // was most of what the oracle generated and threw away before the // generator stopped emitting them; now both libraries turn them down. try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "^*")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "$+")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "\\b?")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "\\B*")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "\\A+")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "\\z?")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "\\Z{1,2}")); try std.testing.expectError(error.NothingToRepeat, Regex.compile(gpa, "a^{2}")); // Wrapped in a group it is a repeatable item again, as in PCRE, and so // are lookarounds. try expectFind("(?m:^)*a", "a", "a"); try expectFind("(?:\\b)+a", "a", "a"); try expectFind("(?=a)+a", "aa", "a");}
test "a shorthand set cannot open a class range" { // `[\d-z]` is an error in PCRE, not a class holding a literal dash; the // dash is literal only where no range could start -- last, or first. try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[\\d-z]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[[:digit:]-z]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[\\s-x]")); try std.testing.expectError(error.InvalidClass, Regex.compile(gpa, "[\\w-\\d]")); try expectFind("[\\d-]", "-", "-"); try expectFind("[[:digit:]-]", "-", "-"); try expectFind("[-\\d]", "-", "-"); try expectFind("[\\h-]", "\t", "\t");}
test "an iteration spends one budget, not one per match" { // Each `next` scans a region disjoint from the last, so the per-byte // allowance is naturally spent once across an iteration -- but the // `max_steps` headroom used to be granted anew at every call, and a // haystack alternating cheap matches with expensive stretches could // claim it once per match. The iterator now holds every `next` to one // pool. Interleave sixty `x` matches with runs of `a` that `(a+)\1$` // grinds against: under the old accounting each run fit its own fresh // budget and the iteration completed; under one pool it must run dry // partway, after real matches have been returned. var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); for (0..60) |_| { try hay.append(gpa, 'x'); for (0..200) |_| try hay.append(gpa, 'a'); } var re = try Regex.compile(gpa, "x|(a+)\\1$"); defer re.deinit(); re.max_steps = 5000; re.jit_mode = .off;
var it = re.iterator(gpa, hay.items); defer it.deinit(); var matches: usize = 0; var ran_dry = false; while (true) { const step = it.next() catch |e| { try std.testing.expectEqual(error.StepLimitExceeded, e); ran_dry = true; break; }; var m = step orelse break; m.deinit(gpa); matches += 1; } try std.testing.expect(ran_dry); try std.testing.expect(matches > 0); try std.testing.expect(matches < 60);
// A haystack dense with matches and nothing expensive between them // iterates to the end on the same pool. var re2 = try Regex.compile(gpa, "(a)\\1?"); defer re2.deinit(); re2.jit_mode = .off; hay.clearRetainingCapacity(); for (0..10_000) |_| try hay.append(gpa, 'a'); var it2 = re2.iterator(gpa, hay.items); defer it2.deinit(); var n: usize = 0; while (try it2.next()) |m| { var mm = m; mm.deinit(gpa); n += 1; } try std.testing.expectEqual(@as(usize, 5000), n);}
test "findAt past the end of the haystack finds nothing" { // Every engine takes the start as a position to read context around: // `\b` and multiline `^` look at the byte before it. Without the bounds // check in `findAt`, a start beyond the end was an out-of-bounds read -- // in a release build `\b` at 105 of a 5-byte haystack read garbage, // called it a word character, and returned the span 105..105, outside // the haystack; in a debug build this test would have panicked. Found by // probing the public API with arguments no fuzzer generates. const hay = "aab\u{e9}"; const patterns = [_][]const u8{ "a+", "\\b", "\\B", "(?m)^a", "(?m)a$", "(?<=a)b", "(a)\\1" }; for (patterns) |p| { var re = try Regex.compile(gpa, p); defer re.deinit(); for ([_]usize{ hay.len + 1, hay.len + 100, std.math.maxInt(usize) }) |start| { try std.testing.expectEqual(@as(?zregex.Span, null), blk: { const m = try re.findAt(gpa, hay, start); if (m) |found| { var mm = found; defer mm.deinit(gpa); break :blk mm.span(); } break :blk null; }); } } // The end itself is a real position: an empty match and a trailing // assertion still hold there. var re = try Regex.compile(gpa, "\\b"); defer re.deinit(); const m = (try re.findAt(gpa, "ab", 2)) orelse return error.TestUnexpectedResult; var mm = m; defer mm.deinit(gpa); try std.testing.expectEqual(@as(usize, 2), mm.span().start);}
test "pike capture chains are compacted, and compaction changes nothing" { // A run of `(a?)` groups against a long haystack once grew five // kilobytes of dead capture chain per input byte -- three hundred // megabytes for sixty kilobytes of `a` -- because chain nodes lived in // one arena for the whole scan and nearly all of them belonged to // threads that died a step later. The Pike VM now compacts: chains still // reachable from live threads are copied to a fresh arena and the rest // freed. This input is long enough to force the compactor to run about // a hundred and fifty times; the captures must come out exactly as the // backtracker computes them without any of that machinery. var pat: std.ArrayList(u8) = .empty; defer pat.deinit(gpa); for (0..90) |_| try pat.appendSlice(gpa, "(a?)"); try pat.appendSlice(gpa, "b"); var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); for (0..60_000) |_| try hay.append(gpa, 'a'); try hay.append(gpa, 'b');
var re = try Regex.compile(gpa, pat.items); defer re.deinit(); re.jit_mode = .off; re.dfa_mode = .off;
// The equality check runs at a size the backtracker can afford; five // hundred positions of ninety optional groups still put ~90,000 nodes // through the arena, past the compaction threshold. var probe_bt = re; probe_bt.fallback_engine = .backtrack; var short_hay: std.ArrayList(u8) = .empty; defer short_hay.deinit(gpa); for (0..500) |_| try short_hay.append(gpa, 'a'); try short_hay.append(gpa, 'b'); const short = short_hay.items; const mp = (try re.find(gpa, short)) orelse return error.TestUnexpectedResult; var pike_m = mp; defer pike_m.deinit(gpa); const mb = (try probe_bt.find(gpa, short)) orelse return error.TestUnexpectedResult; var bt_m = mb; defer bt_m.deinit(gpa); try std.testing.expectEqualSlices(?zregex.Span, bt_m.groups, pike_m.groups);
// The full sixty kilobytes -- some hundred and fifty compactions -- on // the Pike VM alone: must complete, must find the match at the end. const ml = (try re.find(gpa, hay.items)) orelse return error.TestUnexpectedResult; var long_m = ml; defer long_m.deinit(gpa); try std.testing.expectEqual(@as(usize, 60_001), long_m.span().end);}
test "the backtracker's scratch is bounded like its time" { // Slot writes nearly every step of a long budget-legal scan once built // fifty megabytes of undo log; the frame stack and undo log are now held // to a cap in PCRE2-heap-limit territory, and exceeding it is the same // error as exceeding the step budget -- it is the same thing, a bound on // what one search may spend. Memoization has carried its own entry cap // all along, so it is turned off here to expose the logs themselves. var hay: std.ArrayList(u8) = .empty; defer hay.deinit(gpa); for (0..400_000) |_| try hay.append(gpa, 'a'); var re = try Regex.compile(gpa, "(?:(a)(a)(a)(a))+\\1z"); defer re.deinit(); re.jit_mode = .off; re.memo = false; try std.testing.expectError(error.StepLimitExceeded, re.find(gpa, hay.items));
// With memoization on -- the default -- the same scan completes: the // memo prunes the re-visits, its table has carried its own entry cap all // along, and the logs stay far under the new one. var re2 = try Regex.compile(gpa, "(?:(a)(a)(a)(a))+\\1z"); defer re2.deinit(); re2.jit_mode = .off; const m = try re2.find(gpa, hay.items); try std.testing.expect(m == null);}
test "deep lookaround nesting is bounded, not a stack overflow" { // Matching recurses on the native stack once per lookaround: the // backtracker's lookaround handling calls back into `matchFrom`, and a // lookaround body can hold another. Nesting is capped at compile time // (the same `max_depth` that bounds the parser and the compiler's own // recursion), so that recursion is bounded too -- this is the same crash // class as the concat spine that once segfaulted, checked at the cap // rather than left to luck. Two hundred deep compiles and matches; one // past it is a clean error, never a crash. inline for (.{ "(?=", "(?<=", "(?:" }) |open| { const close = ")"; var at_cap: std.ArrayList(u8) = .empty; defer at_cap.deinit(gpa); for (0..200) |_| try at_cap.appendSlice(gpa, open); try at_cap.append(gpa, 'a'); for (0..200) |_| try at_cap.appendSlice(gpa, close); var re = try Regex.compile(gpa, at_cap.items); defer re.deinit(); const m = try re.find(gpa, "aaaa"); if (m) |found| { var mm = found; mm.deinit(gpa); }
var past: std.ArrayList(u8) = .empty; defer past.deinit(gpa); for (0..201) |_| try past.appendSlice(gpa, open); try past.append(gpa, 'a'); for (0..201) |_| try past.appendSlice(gpa, close); try std.testing.expectError(error.NestingTooDeep, Regex.compile(gpa, past.items)); }}
test "cases where PCRE2 is the one that is wrong" { // Found by tools/oracle.zig. All were checked against Python, which // agrees with zregex; the reference is pinned in build.zig.zon, and the // generator steers around what that version still gets wrong so the // tool reports real differences.
// Adding `(?i)` can only ever add matches. PCRE2 10.47 lost the match // when a caseless class held a wide non-ASCII range; 10.48 fixed it and // agrees with these, which stay as plain behavior tests. try expectFind("(?i)[\u{a0}-\u{2fff}]+", "Aa\u{20ac}-x", "\u{20ac}"); try expectFind("[\u{a0}-\u{2fff}]+", "Aa\u{20ac}-x", "\u{20ac}");
// `X{0}` matches empty, so what follows decides the match. PCRE2 fails // the whole pattern for some nullable bodies -- still, as of 10.48, for // the last two below; 10.48 fixed the lookaround-bodied ones. try expectFind("(?:(?= ){8}){0}A", "A", "A"); try expectFind("(?:a){0,0}A", "A", "A"); try expectFind("(?:(?=x)+){0}A", "A", "A"); // A body that is itself nullable reaches the same PCRE2 failure, and a // group wrapped round the repeat still captures the empty span where it // stood. Python reports exactly these spans. try expectGroups("((|(.*)){0})b", "ab", &.{ "b", "", null, null }); try expectGroups("((.*){0})b", "ab", &.{ "b", "", null });}
test "lookbehind at a position inside a multi-byte sequence" { // Found by differential fuzzing. The JIT used to step back by the length // `decodeBefore` reports and then decode *forward* from there, which is a // different operation: starting inside a multi-byte sequence, // `decodeBefore` falls back to the single byte before the position, while // decoding forward finds the whole sequence, which ends elsewhere. var re = try Regex.compile(gpa, "(?<=\u{20ac})"); defer re.deinit(); const hay = "ab\u{20ac}"; // '€' occupies bytes 2, 3 and 4 // Only the position just past the euro qualifies. for ([_]usize{ 0, 1, 2, 3, 4 }) |start| { var m = (try re.findAt(gpa, hay, start)).?; defer m.deinit(gpa); try std.testing.expectEqual(@as(usize, 5), m.span().start); } // And the position itself still qualifies when searched from directly. var last = (try re.findAt(gpa, hay, 5)).?; defer last.deinit(gpa); try std.testing.expectEqual(@as(usize, 5), last.span().start); // A negative lookbehind must agree with it position for position. var neg = try Regex.compile(gpa, "(?<!\u{20ac})b"); defer neg.deinit(); try std.testing.expect(try neg.isMatch(gpa, "ab")); try std.testing.expect(!try neg.isMatch(gpa, "\u{20ac}b"));}
test "searching from inside a multi-byte codepoint" { // `findAt` takes any byte offset, including one inside a codepoint. A // greedy repeat retrying from there used to step back over the whole // codepoint and land before the position the search started at, which // reported a match ending before its own start. const hay = "ab@aab A\u{20ac}"; // 'A' at 7, euro at 8, 9 and 10 for ([_][]const u8{ "[\u{a0}-\u{2fff}]*(?<=A)", ".*(?<=A)", "[\u{a0}-\u{2fff}]*(?<=\u{20ac})" }) |pat| { var re = try Regex.compile(gpa, pat); defer re.deinit(); for (0..hay.len + 1) |start| { const m = try re.findAt(gpa, hay, start); if (m) |found| { var mm = found; defer mm.deinit(gpa); const sp = mm.span(); try std.testing.expect(sp.start >= start); try std.testing.expect(sp.start <= sp.end); try std.testing.expect(sp.end <= hay.len); } } }}
test "an empty loop iteration keeps its captures, on every engine" { // PCRE and Python run a final iteration that consumes nothing, so the // group ends up holding the empty span where the loop stopped rather than // the last one that consumed something. The Pike VM used to report the // latter: two threads sharing an instruction can disagree about whether // the current iteration began at this position, and deduplicating on the // instruction alone dropped the higher-priority path that ran the empty // iteration. `\s(b|.??)*` also had the wrong *span* for the same reason. const cases = [_]struct { pat: []const u8, hay: []const u8, want: []const ?zregex.Span, }{ .{ .pat = "(a*)*", .hay = "aa", .want = &.{ .{ .start = 0, .end = 2 }, .{ .start = 2, .end = 2 } } }, .{ .pat = "(a|)*", .hay = "aa", .want = &.{ .{ .start = 0, .end = 2 }, .{ .start = 2, .end = 2 } } }, .{ .pat = "(a*)*b", .hay = "aab", .want = &.{ .{ .start = 0, .end = 3 }, .{ .start = 2, .end = 2 } } }, .{ .pat = "(a*)+", .hay = "aa", .want = &.{ .{ .start = 0, .end = 2 }, .{ .start = 2, .end = 2 } } }, .{ .pat = "(a*)*(b*)*", .hay = "aab", .want = &.{ .{ .start = 0, .end = 3 }, .{ .start = 2, .end = 2 }, .{ .start = 3, .end = 3 } }, }, .{ .pat = "\\s(b|.??)*", .hay = " ba", .want = &.{ .{ .start = 0, .end = 2 }, .{ .start = 2, .end = 2 } } }, .{ .pat = "(|a)*", .hay = "aa", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 0, .end = 0 } } }, .{ .pat = "(a?)*", .hay = "b", .want = &.{ .{ .start = 0, .end = 0 }, .{ .start = 0, .end = 0 } } }, }; for (cases) |c| { for ([_]enum { pike, backtrack, jit }{ .pike, .backtrack, .jit }) |which| { var re = try Regex.compile(gpa, c.pat); defer re.deinit(); re.dfa_mode = .off; switch (which) { .jit => { re.jit_mode = .on; if (re.jit_code == null) continue; }, .pike => { re.jit_mode = .off; re.fallback_engine = .pike; }, .backtrack => { re.jit_mode = .off; re.fallback_engine = .backtrack; }, } const m = (try re.find(gpa, c.hay)) orelse { std.debug.print("pattern={s} on {s}: no match\n", .{ c.pat, c.hay }); return error.TestUnexpectedResult; }; var mm = m; defer mm.deinit(gpa); std.testing.expectEqualSlices(?zregex.Span, c.want, mm.groups) catch |err| { std.debug.print("pattern={s} haystack={s} engine={t}\n", .{ c.pat, c.hay, which }); return err; }; } }}
test "many nullable loops still tell empty iterations apart" { // The Pike VM keeps threads that disagree about whether the current loop // iteration began here from being merged, by putting a bit per empty-loop // guard in the visited key. Those bits used to be handed out in the order // the guards appeared, and only four of them existed. // // `x{n}` over a nullable body emits n copies of the loop and so n guards, // which ran the four out at n = 5. The guards past the ceiling shared a // coarser key, the thread that had run the empty final iteration was // merged away, and group 2 came back as 0..1 -- the last iteration that // consumed something -- instead of the empty 1..1 that PCRE and Python // both report. Bits are handed out per nesting level now, so the copies, // which sit side by side rather than inside one another, share one. const want = [_]?zregex.Span{ .{ .start = 0, .end = 2 }, .{ .start = 0, .end = 1 }, .{ .start = 1, .end = 1 }, }; for ([_]usize{ 1, 2, 4, 5, 6, 9, 17, 40 }) |n| { var buf: [32]u8 = undefined; const pat = try std.fmt.bufPrint(&buf, "((a{{0,}}?){{0,}}){{{d}}}b", .{n}); for ([_]enum { pike, dfa, backtrack, jit }{ .pike, .dfa, .backtrack, .jit }) |which| { var re = try Regex.compile(gpa, pat); defer re.deinit(); re.dfa_mode = .off; re.jit_mode = .off; switch (which) { .jit => { re.jit_mode = .on; if (re.jit_code == null) continue; }, .dfa => re.dfa_mode = .on, .pike => re.fallback_engine = .pike, .backtrack => re.fallback_engine = .backtrack, } const m = (try re.find(gpa, "ab")) orelse { std.debug.print("pattern={s} engine={t}: no match\n", .{ pat, which }); return error.TestUnexpectedResult; }; var mm = m; defer mm.deinit(gpa); std.testing.expectEqualSlices(?zregex.Span, &want, mm.groups) catch |err| { std.debug.print("pattern={s} engine={t}\n", .{ pat, which }); return err; }; } }}
test "an empty iteration ends the loop only once the minimum is met" { // PCRE stops repeating as soon as an iteration consumes nothing, so the // mandatory iteration of `e+` ends the loop just as a later one does, and // no further iteration can read what it captured. Below the minimum the // repeat has to keep going regardless, which is why `{2,}` still reaches // a second iteration and matches from 0. Python allows the `+` case; // zregex follows PCRE. try expectFind("(?:()|[a]\\1)+1", "a1", "1"); try expectFind("(?:()|[a]\\1)*1", "a1", "1"); try expectFind("(?:()|[a]\\1){1,}1", "a1", "1"); try expectFind("(?:()|[a]\\1){2,}1", "a1", "a1"); // Repeats whose body can match empty but that do consume are unaffected. try expectFind("(a*)+", "aa", "aa"); try expectFind("(a?)+b", "ab", "ab");}
test "a backreference to the group enclosing it" { // PCRE treats a group as unavailable while it is open, so `\1` inside // group 1 fails there; zregex reads the value that group captured on its // last completed iteration. All but one of these agree with PCRE anyway. // The exception is `1(2|\1*)`, left as zregex answers it because PCRE // has no single answer to follow: it matches `1(\1*)` but fails // `1(2|\1*)`, which differ only in which alternative comes first, and // Python rejects the construct outright as a reference to an open group. try expectFind("(a\\1)", "a", null); try expectFind("1(\\1*)", "1", "1"); try expectFind("1(2|\\1*)", "1", "1"); try expectFind("(|[a]\\1)+1", "a1", "1");}
test "octal escapes, and telling them from backreferences" { // PCRE reads `\ddd` as a backreference when the number is under ten or // names a group that exists, and as an octal character otherwise. Under // ten it is always a backreference, so `\8` is an error rather than a // character; inside a class there are no backreferences at all. try expectFind("\\101", "A", "A"); try expectFind("\\11", "\t", "\t"); try expectFind("\\012a", "\na", "\na"); try expectFind("[\\1]", "\x01", "\x01"); // Three digits at most: the fourth is a literal of its own. try expectFind("\\1011", "A1", "A1"); // `\18` is octal 1 followed by a literal 8, since 8 is not an octal digit. try expectFind("\\18", "\x018", "\x018"); // A group that exists still wins. try expectFind("(a)\\1", "aa", "aa"); try std.testing.expectError(error.InvalidBackref, Regex.compile(gpa, "\\1")); try std.testing.expectError(error.InvalidBackref, Regex.compile(gpa, "\\8"));}
test "comptime and runtime compilation agree" { // The comptime path builds its program with a separate code path that // bakes the result into the binary, so it can drift from the runtime one // without any single pattern's test noticing. Run both over a spread of // constructs and require identical matches. const patterns = .{ "(\\d{3})-(\\d{4})", "(?i)h(?-i:ell)o", "(a*)*", "\\s(b|.??)*", "(?:()|[a]\\1)+1", "\\101\\x41", "(\\w+)@([\\w.]+)", "(?<year>\\d{4})-(?<mon>\\d{2})", "a{2,4}?b", "(?<=x)y+", "(a)(b)?\\1", "[^\\d\\s]+", "\\bfoo\\b", "(?:ab|a)*c", }; const haystacks = [_][]const u8{ "", "555-1234", "hello HELLO", "aaa", " ba", "a1", "AA", "mail jeff@x.org", "2026-08-31", "aaab", "xyyy", "abab", "foo bar foo", "ababac", "\t\n z", }; inline for (patterns) |pat| { const ct = comptime Regex.compileComptime(pat); var rt = try Regex.compile(gpa, pat); defer rt.deinit(); for (haystacks) |hay| { const a = try ct.find(gpa, hay); defer if (a) |m| { var mm = m; mm.deinit(gpa); }; const b = try rt.find(gpa, hay); defer if (b) |m| { var mm = m; mm.deinit(gpa); }; if ((a == null) != (b == null)) { std.debug.print("pattern={s} haystack={f}: comptime {} runtime {}\n", .{ pat, std.zig.fmtString(hay), a != null, b != null, }); return error.TestUnexpectedResult; } if (a) |ma| { std.testing.expectEqualSlices(?zregex.Span, b.?.groups, ma.groups) catch |err| { std.debug.print("pattern={s} haystack={f}\n", .{ pat, std.zig.fmtString(hay) }); return err; }; } } }}
test "multiline ^ does not start a line after a trailing newline" { // PCRE starts a line after an *internal* newline only. A newline that // ends the subject leaves no line after it, so `(?m:^)` has no match at // the very end of "a\n" and `(?m:^(?!\n))` does not match "\n" at all. try expectFind("(?m:^(?!\\n))", "\n", null); try expectFind("(?m:^)x", "\nx", "x"); try expectFind("(?m:^b)", "a\nb", "b"); // Line starts in "a\nb" are 0 and 2; in "a\n" and "\n" only 0, since the // newline ends the subject. try expectStarts("(?m:^)", "a\nb", &.{ 0, 2 }); try expectStarts("(?m:^)", "a\n", &.{0}); try expectStarts("(?m:^)", "\n", &.{0}); // `$` is unaffected: before a final newline and at the end both count. try expectStarts("(?m:$)", "a\n", &.{ 1, 2 });}
/// Every match's start offset, for assertions about zero-width assertions/// where the matched text says nothing.fn expectStarts(pattern: []const u8, haystack: []const u8, expected: []const usize) !void { var re = try Regex.compile(gpa, pattern); defer re.deinit(); var starts: std.ArrayList(usize) = .empty; defer starts.deinit(gpa); var it = re.iterator(gpa, haystack); defer it.deinit(); while (try it.next()) |m| { var mm = m; defer mm.deinit(gpa); try starts.append(gpa, mm.span().start); } try std.testing.expectEqualSlices(usize, expected, starts.items);}
test "retrying a repeat that started inside a codepoint" { // Decoding forward from inside a multi-byte sequence degrades to a single // byte, so a run built from such a position advances a byte at a time. // Decoding *backwards* from its end finds the whole sequence instead, so // a retry that stepped back by that much would land before the position // the search started from. The JIT used to give up there and report no // match where every interpreter found one. const emoji = "\u{1F600}"; // four bytes, so offsets 1..3 are inside it for ([_][]const u8{ ".?.", ".?([^b])", ".?(?:-|[^ab]1)", ".{0,2}." }) |pat| { var re = try Regex.compile(gpa, pat); defer re.deinit(); for ([_]bool{ false, true }) |use_jit| { re.jit_mode = if (use_jit) .on else .off; if (use_jit and re.jit_code == null) continue; for (0..emoji.len + 1) |start| { const m = try re.findAt(gpa, emoji, start); if (m) |found| { var mm = found; defer mm.deinit(gpa); const sp = mm.span(); try std.testing.expect(sp.start >= start); try std.testing.expect(sp.start <= sp.end); } } } } // The last byte of the sequence still matches on its own, as a degraded // one-byte codepoint, whichever engine runs it. var re = try Regex.compile(gpa, ".?."); defer re.deinit(); re.jit_mode = .on; const m = try re.findAt(gpa, emoji, 3); try std.testing.expect(m != null); var mm = m.?; defer mm.deinit(gpa); try std.testing.expectEqual(@as(usize, 3), mm.span().start); try std.testing.expectEqual(@as(usize, 4), mm.span().end);}