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.
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250// SPDX-FileCopyrightText: © 2026 Jeffrey C. Ollie <jeff@ocjtech.us>// SPDX-License-Identifier: MIT
//! Shared types and helpers used by the parser, the compiler, and all four//! engines.const std = @import("std");const expect = std.testing.expect;const casefold = @import("casefold");
/// Compile-time flags affecting pattern semantics.pub const Flags = struct { /// Case-insensitive matching, using Unicode simple case folding. case_insensitive: bool = false, /// `^`/`$` match at line boundaries in addition to text boundaries. multiline: bool = false, /// `.` also matches `\n`. dot_all: bool = false,};
/// An inclusive codepoint range, the building block of character classes.pub const ClassRange = struct { lo: u21, hi: u21,};
/// Zero-width assertions.pub const Assertion = enum { begin_text, end_text, /// End of text, or just before a newline that ends it: what `$` means /// outside multiline mode, and what `\Z` always means. end_text_or_final_newline, begin_line, end_line, word_boundary, not_word_boundary,};
pub const DecodeResult = struct { cp: u21, len: u3,};
/// Decode the codepoint starting at `pos`. Invalid UTF-8 degrades to a/// single-byte codepoint (latin-1 style) so matching never fails mid-haystack.pub fn decode(input: []const u8, pos: usize) DecodeResult { const b = input[pos]; if (b < 0x80) return .{ .cp = b, .len = 1 }; // ASCII fast path const len = std.unicode.utf8ByteSequenceLength(b) catch return .{ .cp = b, .len = 1 }; if (pos + len > input.len) return .{ .cp = b, .len = 1 }; const cp = std.unicode.utf8Decode(input[pos..][0..len]) catch return .{ .cp = b, .len = 1 }; return .{ .cp = cp, .len = @intCast(len) };}
/// Decode the codepoint that ends exactly at `pos` (i.e. the one before it)./// Uses the same single-byte fallback as `decode`.pub fn decodeBefore(input: []const u8, pos: usize) DecodeResult { std.debug.assert(pos > 0); const last = input[pos - 1]; if (last < 0x80) return .{ .cp = last, .len = 1 }; // ASCII fast path var n: usize = 1; while (n <= 4 and n <= pos) : (n += 1) { const start = pos - n; const b = input[start]; // Look for a lead byte whose sequence length is exactly n. const len = std.unicode.utf8ByteSequenceLength(b) catch continue; if (len != n) continue; const cp = std.unicode.utf8Decode(input[start..pos]) catch break; return .{ .cp = cp, .len = @intCast(n) }; } return .{ .cp = input[pos - 1], .len = 1 };}
/// `\w` semantics: ASCII word character.pub fn isWordChar(cp: u21) bool { return switch (cp) { 'a'...'z', 'A'...'Z', '0'...'9', '_' => true, else => false, };}
/// Simple case folding, over the whole of Unicode.////// Most matching never calls this: a caseless literal or class is rewritten/// into its case-equivalence classes while the pattern is compiled, so by the/// time an engine runs there is no folding left to do. What remains is the/// caseless backreference, whose text is only known while matching.pub fn foldLower(cp: u21) u21 { // ASCII is the overwhelming majority and needs no table. if (cp < 0x80) return if (cp >= 'A' and cp <= 'Z') cp + 32 else cp; var lo: usize = 0; var hi: usize = casefold.folds.len; while (lo < hi) { const mid = lo + (hi - lo) / 2; const at = casefold.folds[mid][0]; if (at == cp) return casefold.folds[mid][1]; if (at < cp) lo = mid + 1 else hi = mid; } return cp;}
/// The codepoints that match `cp` under `(?i)`, `cp` itself included. All but/// about fifteen hundred codepoints are equivalent only to themselves, which/// is why the single-element answer is written into the caller's buffer rather/// than found in a table.pub fn caseOrbit(cp: u21, single: *[1]u21) []const u21 { if (cp >= 0x80 or (cp >= 'A' and cp <= 'Z') or (cp >= 'a' and cp <= 'z')) { for (casefold.orbits) |orbit| { // Orbits are sorted by their first member, so a codepoint below // this one cannot appear in any later orbit either. if (orbit[0] > cp) break; for (orbit) |m| { if (m == cp) return orbit; } } } single[0] = cp; return single;}
/// How many bytes of `input` at `pos` a backreference to `text` consumes, or/// null if it does not match there.////// Caselessly, that length need not be `text.len`: `Ⱥ` (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 every pair of cases has the same length -- gets both the/// comparison and the length wrong.pub fn backrefLen(input: []const u8, pos: usize, text: []const u8, ci: bool) ?usize { if (!ci) { if (pos + text.len > input.len) return null; if (!std.mem.eql(u8, text, input[pos..][0..text.len])) return null; return text.len; } var ti: usize = 0; var hi: usize = pos; while (ti < text.len) { if (hi >= input.len) return null; const want = decode(text, ti); const got = decode(input, hi); if (foldLower(want.cp) != foldLower(got.cp)) return null; ti += want.len; hi += got.len; } return hi - pos;}
/// Codepoint equality, optionally case-insensitive.pub fn charEq(a: u21, b: u21, ci: bool) bool { if (a == b) return true; return ci and foldLower(a) == foldLower(b);}
fn inRanges(ranges: []const ClassRange, cp: u21) bool { for (ranges) |r| { if (cp >= r.lo and cp <= r.hi) return true; } return false;}
/// Class membership test, honoring negation.////// The `ci` branch folds ASCII pairs only, and no compiled program reaches/// it any more: the parser closes a caseless class over its case-equivalent/// codepoints -- the whole of Unicode's simple folding, not just ASCII --/// while the pattern is compiled, and emits it with `ci` false. The flag/// stays in the instruction layout and this branch stays sound for it, but/// a class that folds at match time would be a bug upstream of here.pub fn classMatches(ranges: []const ClassRange, negated: bool, ci: bool, cp: u21) bool { var hit = inRanges(ranges, cp); if (!hit and ci) { // Try the other ASCII case of `cp`. if (cp >= 'A' and cp <= 'Z') { hit = inRanges(ranges, cp + 32); } else if (cp >= 'a' and cp <= 'z') { hit = inRanges(ranges, cp - 32); } } return hit != negated;}
/// Evaluate a zero-width assertion at byte offset `pos` of `input`.pub fn assertHolds(a: Assertion, input: []const u8, pos: usize) bool { switch (a) { .begin_text => return pos == 0, .end_text => return pos == input.len, .end_text_or_final_newline => { if (pos == input.len) return true; return pos + 1 == input.len and input[pos] == '\n'; }, .begin_line => { if (pos == 0) return true; // After an internal newline only: PCRE does not start a line // after a newline that ends the subject, so `(?m:^)` has no match // at the very end of "a\n". return pos < input.len and input[pos - 1] == '\n'; }, .end_line => { if (pos == input.len) return true; return input[pos] == '\n'; }, .word_boundary, .not_word_boundary => { const before = pos > 0 and isWordChar(decodeBefore(input, pos).cp); const after = pos < input.len and isWordChar(decode(input, pos).cp); const boundary = before != after; return if (a == .word_boundary) boundary else !boundary; }, }}
test decode { const s = "aé€x"; try std.testing.expectEqual(DecodeResult{ .cp = 'a', .len = 1 }, decode(s, 0)); try std.testing.expectEqual(DecodeResult{ .cp = 'é', .len = 2 }, decode(s, 1)); try std.testing.expectEqual(DecodeResult{ .cp = '€', .len = 3 }, decode(s, 3)); // Invalid byte falls back to a 1-byte codepoint. try std.testing.expectEqual(DecodeResult{ .cp = 0xff, .len = 1 }, decode("\xff\xfe", 0));}
test decodeBefore { const s = "aé€x"; try std.testing.expectEqual(DecodeResult{ .cp = 'a', .len = 1 }, decodeBefore(s, 1)); try std.testing.expectEqual(DecodeResult{ .cp = 'é', .len = 2 }, decodeBefore(s, 3)); try std.testing.expectEqual(DecodeResult{ .cp = '€', .len = 3 }, decodeBefore(s, 6)); try std.testing.expectEqual(DecodeResult{ .cp = 'x', .len = 1 }, decodeBefore(s, 7));}
test "end of text, with and without a final newline" { try expect(assertHolds(.end_text, "ab", 2)); try expect(!assertHolds(.end_text, "ab\n", 2)); // `$` also matches before a newline that ends the text, but only there. try expect(assertHolds(.end_text_or_final_newline, "ab", 2)); try expect(assertHolds(.end_text_or_final_newline, "ab\n", 2)); try expect(assertHolds(.end_text_or_final_newline, "ab\n", 3)); try expect(!assertHolds(.end_text_or_final_newline, "a\nb", 1)); try expect(!assertHolds(.end_text_or_final_newline, "ab\n\n", 2));}
test assertHolds { try std.testing.expect(assertHolds(.begin_text, "ab", 0)); try std.testing.expect(!assertHolds(.begin_text, "ab", 1)); try std.testing.expect(assertHolds(.end_text, "ab", 2)); try std.testing.expect(assertHolds(.begin_line, "a\nb", 2)); try std.testing.expect(assertHolds(.end_line, "a\nb", 1)); try std.testing.expect(assertHolds(.word_boundary, "ab cd", 2)); try std.testing.expect(assertHolds(.word_boundary, "ab", 0)); try std.testing.expect(assertHolds(.not_word_boundary, "ab", 1));}