halotukozak.regex

Regex.Alt's branch container - see its doc comment for why this exists instead of Alt simply storing a Vector[Regex]/Set[Regex] directly. Stores two genuinely immutable views built together, once, from the same order-preserving dedup pass: toVector (insertion-order, deduplicated - what iterator and every inherited Iterable operation like exists/map/ toList use) and asSet (the same elements, for equals/hashCode - Set semantics are order-independent, so ACI normalization and Subset.isEmpty's visited-state dedup are unaffected by which order two equivalent Alts happen to store their branches in). The mutable.LinkedHashSet doing the actual dedup work in AltBranches.apply below is a construction-time-only local builder, discarded once toVector/asSet are snapshotted from it - AltBranches itself holds no mutable state, matching every other node in this immutable tree (see Regex's own cached hashCode above, which relies on that immutability).

Whole-string capture-span extraction for patterns containing Regex.Group nodes - the "Phase B" this library's issue #18 tracks (Phase A, Regex.Group itself, only recognizes groups structurally; nothing extracted their matched spans until this).

Backed by Pike's VM: a Thompson-construction NFA compiled directly from a parsed Regex tree (unerased - unlike Subset.of, this needs every Regex.Group node, not none of them), executed as a priority-ordered set of "threads" (one per live NFA position) that all advance one input code point at a time, each carrying its own capture-register array - the technique RE2/Go's regexp/Rust's regex crate actually ship for general (non-"one-pass") captures. Guaranteed O(programSize × inputLength): at most one thread per program instruction survives each step (an equal-or-lower-priority duplicate reaching an already-live instruction is dropped), so there's no repeat of catastrophic-backtracking blowup - the same complexity discipline Subset.isEmpty's visited-state BFS already relies on.

This is a genuinely separate engine from Subset/TokenMatcher, not an extension of either - Subset.of erases every Group before deriving through a pattern specifically so its derivative algebra never has to reason about captures at all. Regex.scala's only changes for this feature are mechanical: Regex.Alt's parts became an order-preserving Vector instead of a Set (see its own doc comment for why - every no-backtracking submatch algorithm, Pike's VM included, needs leftmost-first alternation priority, which a Set can't record) with equals/hashCode overridden back to Set-like semantics so Subset's ACI-normalization/termination story is completely unaffected. Subset.scala/TokenMatcher.scala are untouched.

Whole-string match only (mirrors this library's only existing matching precedent, RegexConformanceTest's private matches helper) - no find/replace/split, and captures aren't wired into TokenMatcher's compiled DFA. Both are tracked separately (issue #53 for the former; a TokenMatcher follow-up for the latter).

Result of a successful CaptureMatcher.matchWhole call: the spans captured by every numbered/named group in the pattern (see Regex.Group). Group 0 is always present and always spans the whole input, exactly like java.util.regex.Matcher.group(0).

Single closed code-point range.

A symbolic regex algebra with exact language containment ("is this pattern a subset of that one?") in addition to the usual construction combinators — not just string matching. Pure Scala, no java.util.regex (or any other JVM-only API) anywhere in the implementation, so it compiles and runs identically on the JVM, Scala.js, and Scala Native.

Construct via smart factories on the companion (Regex.lit, Regex.literal, Regex.range, Regex.apply, Regex.alt, Regex.inter, Regex.all) and member combinators (a concat b, a | b, a & b, !a, r.star, r.repeat(n, m)). Raw case class constructors are inaccessible — only pattern matching via the generated unapply methods is allowed.

Supports literals, escapes (\d \D \s \S \w \W \t \n \r \f \a \e \v \cX \0[n[n]] \xhh \x{h...h} \uhhhh \Q...\E \R and meta-escapes), Unicode property escapes \p{...} \P{...} (general categories and ASCII-only POSIX classes; see UnicodeCategories), character classes (including ranges, negation, nested subclasses, and && intersection), ., alternation |, capturing groups (...), named groups (?...), non-capturing groups (?:...), lookahead (?=...) (?!...), the i inline flag (?i) (?-i) (?i:...) (?-i:...), anchors ^ $ \A \Z \z, quantifiers * + ? {n} {n,} {n,m} (bounds capped at Regex.maxRepeatBound).

Capturing groups are recognized structurally (numbered/named correctly, and fully transparent to every containment/matching operation - see Regex.Group and Subset's doc comment) but their captured spans aren't extractable yet - that's tracked separately.

Unsupported (parser returns RegexParseError.UnsupportedFeature): word-boundary anchors \b \B, \G, lookbehind (? \g{...}, Unicode script/block properties (\p{IsGreek}, \p{InGreek}), grapheme clusters \X.

For subset/emptiness/nullability queries and Brzozowski derivatives, see Subset.

Reason a RegexParser.parse call did not produce a Regex.

Java-regex-style parser producing a normalized Regex.

Supported subset (see Regex doc): literals, escapes (\d \D \s \S \w \W \t \n \r \f \a \e \v \cX \0[n[n]] \xhh \x{h...h} \uhhhh \Q...\E \R and meta-escapes . * + ? ( ) [ ] { } | ^ $ -), Unicode property escapes \p{...} \P{...} (general categories like L/Lu/Nd, and the ASCII-only POSIX classes like Alpha/Digit - see UnicodeCategories; script/block properties are unsupported), ., char classes [...] [^...] with ranges, nested shorthand escapes ([\da-f]), nested subclasses, and && intersection ([a-z&&[^aeiou]]) (\b inside a class means backspace, matching Java), alternation |, capturing groups (...), named groups (?...), non-capturing groups (?:...), lookahead (?=...) (?!...), the i inline flag (?i) (?-i) (?i:...) (?-i:...) (ASCII-only case folding, matching Java's CASE_INSENSITIVE without UNICODE_CASE), quantifiers * + ? {n} {n,} {n,m} (bounds capped at Regex.maxRepeatBound), anchors ^ $ \A \Z \z.

Capturing/named groups are recognized structurally (numbered/named correctly - see Regex.Group) but their captured spans aren't extractable yet - that's tracked separately, same as Regex's own doc comment notes.

Unsupported: word-boundary anchors \b \B, \G, lookbehind, backreferences \1..\9 \k \g{...}, Unicode script/block properties (\p{IsGreek}, \p{InGreek}, etc.), grapheme clusters \X, other inline flags ((?m), (?s), (?d), (?u), (?x), (?U)). Any other undefined letter escape (e.g. \m, \y, \q) is rejected as invalid syntax, matching java.util.regex.Pattern's own behavior.

Raised (as a Left, never thrown) by Subset.isEmptyBounded, Subset.subsetBounded, TokenMatcher.fromRegexesBounded, and TokenMatcher.fromSubsetsBounded when deciding the answer would require visiting more than limit distinct derivative states.

This engine has no classic backtracking, so it isn't exposed to catastrophic-backtracking ReDoS in the traditional sense - but the derivative state space these operations explore has no bound of its own: a pattern built to maximize distinct derivative states (many overlapping alternations/intersections/bounded repetitions near Regex.maxRepeatBound) can still make either slow or memory-heavy. That matters wherever pattern strings come from untrusted input, e.g. Subset's stated use case of validating one pattern against another at load/build time. The bounded methods this guards are opt-in: the plain isEmpty/subset/fromRegexes/ fromSubsets stay uncapped, unchanged, for every existing caller.

Lexer-style longest-match tokenizer over a priority-ordered list of patterns.

Backed by a DFA obtained via Brzozowski-derivative subset construction over all patterns in parallel (a single automaton, not one-per-pattern): building it walks the derivative state space once (fromRegexes/fromSubsets), so matchAt itself is just array lookups - a binary search to classify the current code point into an alphabet partition, then an Int transition-table read - with no Regex/Subset allocation or derivation on the hot path. Ties broken by lowest priority index (i.e., the first pattern in the input list wins).

boundaries(i) is the first code point of partition i (boundaries(0) == 0); the partition itself spans [boundaries(i), boundaries(i + 1)), with boundaries.length acting as the exclusive upper partition for the last one. All derivative states share this same partition: deriving only ever discards Chars leaves (via smart-constructor normalization), never introduces new ones, so the alphabet fixed at the initial patterns already bounds every reachable state.

transitions is numStates * boundaries.length entries, row-major by state; -1 marks the (unrepresented) dead state, i.e. every pattern's derivative going empty.

accept(state) is the lowest pattern index nullable in that state at a position followed by more input, or -1 if none is; acceptAtEnd(state) is the same at the end of the input. They differ only for $/\Z/\z (see Regex.nullableBeforeMoreInput): a token ends wherever the next one starts, so those hold only when it's the last one. Any other lookahead would have to see the input after the token, so the builders reject it - see UnsupportedTokenConstruct.

State 0 starts a match past the start of the input, inputStartState one at offset 0. They differ only when a pattern uses ^/\A, which holds only at offset 0 (state 0 starts from the patterns with every ^/\A already failed, like any derivative). fastAscii is built from state 0, so it's skipped for a match at offset 0 whenever the two differ.

A pattern containing Regex.Group nodes (capturing/named groups) compiles fine - they're erased the same way Subset.of erases them for containment checks (fromRegexes/ fromSubsets go through Subset.of too) - but matchAt/findFirst never return capture spans; this DFA only ever tracks priority/end position. Wiring captures into the compiled automaton is separate, not-yet-done work.

Constructor kept private - the only place that ever builds one directly is compile below, in the companion object; @publicInBinary exists solely so given ToExpr[TokenMatcher]'s quoted call to it still resolves once that quote is spliced into a different compilation unit's generated bytecode (by tokenMatcher(...) below, or a user's own macro), despite being private at the source level everywhere else.

Pattern patternIndex of a TokenMatcher uses construct, which depends on the input after the token and so can't be matched by it: a lookahead other than the $/\Z/\z anchors. Returned by TokenMatcher.fromRegexesChecked; the other builders throw it as an IllegalArgumentException. Whole-string matching (Subset, CaptureMatcher) supports every lookahead.

Sorted, non-overlapping, merged ranges over Int code points.

Opaque over ArraySeq[Range]: every instance is built through a normalizing smart constructor (CharSet.normalize, CharSet.single, CharSet.range, CharSet.empty, CharSet.all, CharSet.of) - complement/intersect rely on that invariant. ArraySeq's true O(1) array-backed indexed access (contains's binary search, intersect/complement's indexed loops) and structural equals/hashCode (which Regex's Set-based ACI normalization and cached hashCode rely on) come along for free from the underlying representation.

Opaque view over a Regex exposing Brzozowski-derivative based language emptiness and subset operations.

a.subset(b) decides whether L(a) ⊆ L(b) by checking emptiness of a ∩ ¬b. Termination relies on smart-constructor normalization in Regex keeping the derivative state set finite up to similarity.

Regex.Group nodes never survive lifting into this type: Subset.of erases every one of them before the result is ever derived through (see that method's doc comment for why). That means every other function in this file can - and does - assume no Group ever reaches it, which matters specifically for rawDerive's Concat(Look(...), _)/Concat(Alt(...), _) shape-matching special cases below: a Group wrapping a leading Look (e.g. ((?=a))a) would otherwise have to be specifically unwrapped in each of those, on top of the ordinary generic-recursion handling every other node already gets for free.

Compile-time counterpart to regex"..." (see Regex), but for a whole priority-ordered pattern list instead of a single pattern: parses every pattern and builds the DFA (TokenMatcher.compile's derivative-state BFS) at macro-expansion time, splicing the already-built matcher through the existing given ToExpr[TokenMatcher] as plain Array[Int] tables. Without this, TokenMatcher.fromRegexes/fromSubsets re-derive that whole automaton (BFS over derivative states, transition-table construction) from scratch on every process startup, even though a literal, fixed pattern list (e.g. a lexer's token table) is exactly as knowable at compile time as a single regex"..." pattern is.

Every pattern must itself reduce to a literal String constant - a Varargs element that doesn't is a macro-expansion error, not a runtime-parsing fallback: unlike regex"..." (which falls back to parsing at runtime when the pattern isn't a literal, since there's exactly one Regex either way), there's no equally sensible fallback for a whole vararg pattern list threaded through a macro parameter - TokenMatcher.fromRegexes/fromSubsets already exist as the explicit runtime-parsing entry point for patterns not known until runtime (e.g. loaded from a config file).

patterns must be declared inline too, for the same reason regex"..."'s sc receiver is (see that doc comment): without it, the compiler binds the vararg call-site arguments to a synthetic proxy val before splicing, so 'patterns inside tokenMatcherImpl sees only a reference to that val - never the literal argument list itself - and every call falls into the "not a literal" branch below regardless of what was actually written at the call site.