{"name":"ext/regex.nu","source":"// stdlib/ext/regex.nu — NFA-based regular expression engine (pure NURL)\n//\n// Tier 2 #13. Determinismi tärkeämpi kuin ominaisuusrunsaus —\n// matching is O(n*m) (text length × NFA size) via Thompson construction\n// + set-based simulation; no backtracking, no catastrophic blow-up.\n//\n// ── Pattern grammar ─────────────────────────────────────────────────\n//\n//   re        ::= alt\n//   alt       ::= seq ('|' seq)*\n//   seq       ::= atom*\n//   atom      ::= base quant?\n//   base      ::= '.' | char | escape | class | '(' alt ')' | '^' | '$'\n//   quant     ::= '*' | '+' | '?'\n//   class     ::= '[' '^'? class_item+ ']'\n//   class_item::= char | char '-' char | escape\n//   escape    ::= '\\.' | '\\*' | '\\+' | '\\?' | '\\(' | '\\)' | '\\[' | '\\]'\n//               | '\\|' | '\\^' | '\\$' | '\\\\' | '\\/' | '\\n' | '\\t' | '\\r'\n//               | '\\d' (digits 0-9) | '\\D' (non-digits)\n//               | '\\w' (word: [A-Za-z0-9_]) | '\\W' (non-word)\n//               | '\\s' (whitespace: space/tab/cr/lf) | '\\S' (non-ws)\n//\n// `.` matches any byte except `\\n`. Anchors `^` and `$` are zero-width\n// and match only at text start / end (no multiline mode). All\n// quantifiers are greedy. Capture groups ARE supported: `(` … `)` both\n// groups for precedence and records the span, readable through\n// `regex_find_caps` and substitutable through `regex_expand`.\n//\n// ── API ─────────────────────────────────────────────────────────────\n//\n//   ( regex_compile pattern )       → ! Regex ParseErr\n//   ( regex_test    r text )        → b              any match anywhere\n//   ( regex_match   r text )        → b              entire text matches\n//   ( regex_find    r text )        → ? Match        leftmost match\n//   ( regex_find_caps r text slots ) → ? Match       …with capture groups\n//   ( regex_ngroups r )             → i              capture groups in it\n//   ( regex_expand  text slots tmpl ) → String       expand `&` / `\\1`\n//   ( regex_find_all r text )       → ( Vec Match )  non-overlapping\n//   ( regex_replace  r text repl )  → String         non-overlapping replace\n//   ( regex_split    r text )       → ( Vec String ) split on matches\n//   ( regex_free     r )            → v   early release (optional: the last\n//                                        owner of a Regex releases it)\n//\n// `Match { i start, i len }` is a half-open span over the original text\n// (text bytes [start, start+len)). Use `string_substr` on the text to\n// project it to a String. Empty matches are skipped in find_all/split/\n// replace to avoid infinite loops.\n//\n// ── Errors ──────────────────────────────────────────────────────────\n//\n//   ParseErr::Empty           → empty pattern\n//   ParseErr::BadFormat       → malformed pattern\n//   ParseErr::TrailingGarbage → unmatched `)` or `]`\n\n$ `stdlib/core/errors.nu`\n$ `stdlib/core/string.nu`\n$ `stdlib/core/vec.nu`\n$ `stdlib/core/rcbox.nu`\n\n// ── State kinds ─────────────────────────────────────────────────────\n// 0 = Match  (accept; out1/out2 unused)\n// 1 = Char   (a = byte 0..255; out1 = next on consume)\n// 2 = Any    (matches any byte except '\\n'; out1 = next)\n// 3 = Class  (a = class index; out1 = next on consume)\n// 4 = Anchor (a = 0 for '^', 1 for '$'; out1 = next, zero-width)\n// 5 = Split  (out1, out2 are both ε-successors)\n// 6 = Eps    (out1 = next, zero-width)\n// 7 = Save   (a = capture slot; out1 = next, zero-width) — records the\n//            current position into the thread's slot array, which is how\n//            a group's span survives to the end of the match\n\n// ── Public types ────────────────────────────────────────────────────\n\n: Match { i start i len }\n\n// Regex is an opaque handle to a RegexImpl in an rcbox: every copy is the\n// same compiled pattern, and the last owner releases it (Regex_drop) —\n// nothing to free by hand. Single-field struct fits in i64, which is\n// required for `! Regex ParseErr` to take the narrow-enum tag-fold path.\n: RegexImpl {\n    ( Vec i ) states  // 4 ints/state: kind, a, out1, out2\n    ( Vec i ) classes  // class store, packed\n    ( Vec i ) class_starts  // class_idx → offset in classes\n    i start\n    i ngroups  // capture groups, numbered by opening paren\n}\n\n: Regex { ( Shared RegexImpl ) ctl }\n\n// Parser state — a local of regex_compile the parser advances in place\n// (`inout`); its tables move into the compiled pattern.\n: RxParser {\n    s pat\n    i len\n    i pos\n    ( Vec i ) states\n    ( Vec i ) classes\n    ( Vec i ) class_starts\n    i ngroups\n}\n\n// ── State table helpers ─────────────────────────────────────────────\n\n@ __rx_add_state inout RxParser p i kind i a i out1 i out2 → i {\n    : ( Vec i ) st . p states\n    : i n / ( vec_len [i] st ) 4\n    ( vec_push [i] st kind )\n    ( vec_push [i] st a )\n    ( vec_push [i] st out1 )\n    ( vec_push [i] st out2 )\n    ^ n\n}\n\n@ __rx_state_kind ( Vec i ) st i idx → i {\n    : *i d ( vec_data [i] st )\n    ^ . d * idx 4\n}\n\n@ __rx_state_a ( Vec i ) st i idx → i {\n    : *i d ( vec_data [i] st )\n    ^ . d + * idx 4 1\n}\n\n@ __rx_state_out1 ( Vec i ) st i idx → i {\n    : *i d ( vec_data [i] st )\n    ^ . d + * idx 4 2\n}\n\n@ __rx_state_out2 ( Vec i ) st i idx → i {\n    : *i d ( vec_data [i] st )\n    ^ . d + * idx 4 3\n}\n\n@ __rx_set_out1 ( Vec i ) st i idx i v → v {\n    : *i d ( vec_data [i] st )\n    = . d + * idx 4 2 v\n}\n\n@ __rx_set_out2 ( Vec i ) st i idx i v → v {\n    : *i d ( vec_data [i] st )\n    = . d + * idx 4 3 v\n}\n\n// Patch the exit state's out1 (uniform fragment-exit convention).\n@ __rx_patch_exit inout RxParser p i exit_idx i target → v {\n    ( __rx_set_out1 . p states exit_idx target )\n}\n\n// ── Class helpers ───────────────────────────────────────────────────\n// A class is stored as a header word followed by 2 * n_pairs range\n// words. Header layout: (n_pairs << 1) | neg_flag.\n\n@ __rx_class_begin inout RxParser p i neg → i {\n    : ( Vec i ) cs . p classes\n    : ( Vec i ) ofs . p class_starts\n    : i idx ( vec_len [i] ofs )\n    : i off ( vec_len [i] cs )\n    ( vec_push [i] ofs off )\n    // Reserve header slot — count filled in by __rx_class_finish.\n    ( vec_push [i] cs ? != 0 neg 1 0 )\n    ^ idx\n}\n\n@ __rx_class_add_range inout RxParser p i lo i hi → v {\n    : ( Vec i ) cs . p classes\n    ( vec_push [i] cs lo )\n    ( vec_push [i] cs hi )\n}\n\n@ __rx_class_finish inout RxParser p i class_idx → v {\n    : ( Vec i ) cs . p classes\n    : ( Vec i ) ofs . p class_starts\n    : i off ( __vi_get ofs class_idx )\n    : i header ( __vi_get cs off )\n    : i n_pairs / - ( vec_len [i] cs ) + off 1 2\n    : i new_header | * n_pairs 2 & header 1\n    : *i d ( vec_data [i] cs )\n    = . d off new_header\n}\n\n@ __rx_class_test ( Vec i ) classes ( Vec i ) class_starts i class_idx i ch → b {\n    : i off ( __vi_get class_starts class_idx )\n    : i header ( __vi_get classes off )\n    : b neg != 0 & header 1\n    : i n_pairs / header 2\n    : ~ i k 0\n    : ~ b found F\n    ~ < k n_pairs {\n        : i lo ( __vi_get classes + off + 1 * k 2 )\n        : i hi ( __vi_get classes + off + 2 * k 2 )\n        ? & >= ch lo <= ch hi { = found T } {}\n        = k + k 1\n    }\n    ^ ? neg ! found found\n}\n\n// ── Vec[i] direct access (skip Option wrapping for hot paths) ───────\n\n@ __vi_get ( Vec i ) v i idx → i {\n    : *i d ( vec_data [i] v )\n    ^ . d idx\n}\n\n@ __vi_set ( Vec i ) v i idx i x → v {\n    : *i d ( vec_data [i] v )\n    = . d idx x\n}\n\n// ── Character-class helpers (for escapes) ───────────────────────────\n\n@ __is_digit_byte i c → b { ^ & >= c 48 <= c 57 }\n\n@ __is_word_byte i c → b {\n    ^ | | | & >= c 65 <= c 90 & >= c 97 <= c 122 & >= c 48 <= c 57 == c 95\n}\n\n@ __is_space_byte i c → b {\n    ^ | | | == c 32 == c 9 == c 10 == c 13\n}\n\n// Build a built-in class for \\d, \\D, \\w, \\W, \\s, \\S. Returns class_idx.\n@ __rx_builtin_class inout RxParser p i which → i {\n    // which: 0=\\d 1=\\D 2=\\w 3=\\W 4=\\s 5=\\S\n    : i neg ? | == which 1 | == which 3 == which 5 1 0\n    : i idx ( __rx_class_begin p neg )\n    ? | == which 0 == which 1 {\n        ( __rx_class_add_range p 48 57 )\n    } {}\n    ? | == which 2 == which 3 {\n        ( __rx_class_add_range p 48 57 )\n        ( __rx_class_add_range p 65 90 )\n        ( __rx_class_add_range p 97 122 )\n        ( __rx_class_add_range p 95 95 )\n    } {}\n    ? | == which 4 == which 5 {\n        ( __rx_class_add_range p 9 10 )\n        ( __rx_class_add_range p 13 13 )\n        ( __rx_class_add_range p 32 32 )\n    } {}\n    ( __rx_class_finish p idx )\n    ^ idx\n}\n\n// ── Parser cursor helpers ───────────────────────────────────────────\n\n@ __rx_eof inout RxParser p → b { ^ >= . p pos . p len }\n\n@ __rx_peek inout RxParser p → i {\n    ? ( __rx_eof p ) { ^ -1 } {}\n    ^ ( nurl_str_at . p pat . p len . p pos )\n}\n\n@ __rx_bump inout RxParser p → i {\n    : i c ( __rx_peek p )\n    = . p pos + . p pos 1\n    ^ c\n}\n\n// ── Escape decode ───────────────────────────────────────────────────\n// Returns: kind in slot 0 (0=literal 1=class), value in slot 1.\n//   For literal: slot1 = byte value.\n//   For class:  slot1 = class index.\n// Encoded into a single i: (kind << 16) | (value & 0xFFFF).\n// The class indices stay well under 65535 in any sane pattern.\n\n@ __rx_decode_escape inout RxParser p → i {\n    : i c ( __rx_peek p )\n    = . p pos + . p pos 1\n    // Plain meta-literals: . * + ? ( ) [ ] | ^ $ \\ /\n    ? | | | | | | | | | | | | == c 46 == c 42 == c 43 == c 63 == c 40 == c 41 == c 91 == c 93 == c 124 == c 94 == c 36 == c 92 == c 47\n    { ^ & c 65535 } {}\n    // Whitespace literals\n    ? == c 110 { ^ 10 } {}  // \\n\n    ? == c 116 { ^ 9 } {}  // \\t\n    ? == c 114 { ^ 13 } {}  // \\r\n    ? == c 102 { ^ 12 } {}  // \\f\n    ? == c 118 { ^ 11 } {}  // \\v\n    ? == c 48 { ^ 0 } {}  // \\0\n    // Built-in classes\n    : ~ i which -1\n    ? == c 100 { = which 0 } {}  // \\d\n    ? == c 68 { = which 1 } {}  // \\D\n    ? == c 119 { = which 2 } {}  // \\w\n    ? == c 87 { = which 3 } {}  // \\W\n    ? == c 115 { = which 4 } {}  // \\s\n    ? == c 83 { = which 5 } {}  // \\S\n    ? >= which 0 {\n        : i ci ( __rx_builtin_class p which )\n        ^ | * 1 65536 ci\n    } {}\n    // Unknown escape: treat as literal of the escaped byte (forgiving).\n    ^ & c 65535\n}\n\n// ── NFA fragment ─────────────────────────────────────────────────────\n// A fragment encodes (entry_state_idx, exit_state_idx) as one i64:\n// (entry << 32) | (exit & 0xFFFFFFFF). Both fit in 32 bits — patterns\n// with 4-billion states are not a concern.\n\n@ __frag i en i ex → i { ^ | * en 4294967296 & ex 4294967295 }\n\n@ __frag_entry i f → i { ^ / f 4294967296 }\n\n@ __frag_exit i f → i { ^ & f 4294967295 }\n\n// ── Emit primitives ─────────────────────────────────────────────────\n// Convention: every fragment's \"exit\" is a state whose out1 is unset\n// and gets patched by the next concat.\n\n@ __emit_char inout RxParser p i c → i {\n    : i s1 ( __rx_add_state p 1 c -1 -1 )\n    : i s2 ( __rx_add_state p 6 0 -1 -1 )\n    ( __rx_set_out1 . p states s1 s2 )\n    ^ ( __frag s1 s2 )\n}\n\n@ __emit_any inout RxParser p → i {\n    : i s1 ( __rx_add_state p 2 0 -1 -1 )\n    : i s2 ( __rx_add_state p 6 0 -1 -1 )\n    ( __rx_set_out1 . p states s1 s2 )\n    ^ ( __frag s1 s2 )\n}\n\n@ __emit_class inout RxParser p i ci → i {\n    : i s1 ( __rx_add_state p 3 ci -1 -1 )\n    : i s2 ( __rx_add_state p 6 0 -1 -1 )\n    ( __rx_set_out1 . p states s1 s2 )\n    ^ ( __frag s1 s2 )\n}\n\n@ __emit_anchor inout RxParser p i which → i {\n    : i s1 ( __rx_add_state p 4 which -1 -1 )\n    : i s2 ( __rx_add_state p 6 0 -1 -1 )\n    ( __rx_set_out1 . p states s1 s2 )\n    ^ ( __frag s1 s2 )\n}\n\n@ __emit_concat inout RxParser p i fa i fb → i {\n    ( __rx_patch_exit p ( __frag_exit fa ) ( __frag_entry fb ) )\n    ^ ( __frag ( __frag_entry fa ) ( __frag_exit fb ) )\n}\n\n@ __emit_alt inout RxParser p i fa i fb → i {\n    : i merge ( __rx_add_state p 6 0 -1 -1 )\n    ( __rx_patch_exit p ( __frag_exit fa ) merge )\n    ( __rx_patch_exit p ( __frag_exit fb ) merge )\n    : i split ( __rx_add_state p 5 0 ( __frag_entry fa ) ( __frag_entry fb ) )\n    ^ ( __frag split merge )\n}\n\n@ __emit_star inout RxParser p i fa → i {\n    : i merge ( __rx_add_state p 6 0 -1 -1 )\n    : i split ( __rx_add_state p 5 0 ( __frag_entry fa ) merge )\n    ( __rx_patch_exit p ( __frag_exit fa ) split )\n    ^ ( __frag split merge )\n}\n\n@ __emit_plus inout RxParser p i fa → i {\n    : i merge ( __rx_add_state p 6 0 -1 -1 )\n    : i split ( __rx_add_state p 5 0 ( __frag_entry fa ) merge )\n    ( __rx_patch_exit p ( __frag_exit fa ) split )\n    ^ ( __frag ( __frag_entry fa ) merge )\n}\n\n@ __emit_optional inout RxParser p i fa → i {\n    : i merge ( __rx_add_state p 6 0 -1 -1 )\n    : i split ( __rx_add_state p 5 0 ( __frag_entry fa ) merge )\n    ( __rx_patch_exit p ( __frag_exit fa ) merge )\n    ^ ( __frag split merge )\n}\n\n// ── Pattern parser (recursive descent) ──────────────────────────────\n// Returns a fragment encoded as i, or -1 on parse error. The caller\n// translates -1 into ParseErr::BadFormat.\n\n@ __parse_class inout RxParser p → i {\n    // ASSUMES position past '['. Builds a class and emits a class state\n    // fragment. Returns fragment, or -1 on error.\n    : ~ i neg 0\n    ? == ( __rx_peek p ) 94 {\n        = . p pos + . p pos 1\n        = neg 1\n    } {}\n    : i ci ( __rx_class_begin p neg )\n    : ~ b done F\n    : ~ b error F\n    : ~ i n_added 0\n    ~ & ! done ! error {\n        ? ( __rx_eof p ) { = error T } {\n            : i c ( __rx_peek p )\n            ? == c 93 {  // ']'\n                = . p pos + . p pos 1\n                = done T\n            } {\n                : ~ i lo 0\n                : ~ b is_class_member F\n                : ~ i member_class_idx -1\n                ? == c 92 {  // '\\'\n                    = . p pos + . p pos 1\n                    : i enc ( __rx_decode_escape p )\n                    : i kind / enc 65536\n                    : i val & enc 65535\n                    ? == kind 1 {\n                        = is_class_member T\n                        = member_class_idx val\n                    } {\n                        = lo val\n                    }\n                } {\n                    = . p pos + . p pos 1\n                    = lo c\n                }\n                ? is_class_member {\n                    // Inline a class's ranges into the current class.\n                    : ( Vec i ) cs . p classes\n                    : ( Vec i ) ofs . p class_starts\n                    : i moff ( __vi_get ofs member_class_idx )\n                    : i mhdr ( __vi_get cs moff )\n                    : i mn / mhdr 2\n                    : ~ i k 0\n                    ~ < k mn {\n                        : i mlo ( __vi_get cs + moff + 1 * k 2 )\n                        : i mhi ( __vi_get cs + moff + 2 * k 2 )\n                        ( __rx_class_add_range p mlo mhi )\n                        = n_added + n_added 1\n                        = k + k 1\n                    }\n                } {\n                    // Possibly a range like 'a-z'.\n                    : ~ i hi lo\n                    ? & ! ( __rx_eof p ) == ( __rx_peek p ) 45 {\n                        // Look ahead: '-' must not be ']' otherwise treat as literal '-'.\n                        : i p2 + . p pos 1\n                        ? & < p2 . p len != ( nurl_str_at . p pat . p len p2 ) 93 {\n                            = . p pos + . p pos 1  // consume '-'\n                            : i nx ( __rx_peek p )\n                            ? == nx 92 {\n                                = . p pos + . p pos 1\n                                : i enc2 ( __rx_decode_escape p )\n                                : i kind2 / enc2 65536\n                                ? == kind2 1 { = error T } { = hi & enc2 65535 }\n                            } {\n                                = . p pos + . p pos 1\n                                = hi nx\n                            }\n                        } {}\n                    } {}\n                    ? ! error {\n                        ( __rx_class_add_range p lo hi )\n                        = n_added + n_added 1\n                    } {}\n                }\n            }\n        }\n    }\n    ? error { ^ -1 } {}\n    ? == n_added 0 { ^ -1 } {}\n    ( __rx_class_finish p ci )\n    ^ ( __emit_class p ci )\n}\n\n// Forward declaration via mutual recursion: __parse_alt and __parse_atom\n// reference each other through __parse_seq.\n\n@ __parse_atom inout RxParser p → i {\n    ? ( __rx_eof p ) { ^ -1 } {}\n    : i c ( __rx_peek p )\n    : ~ i frag -1\n    ? == c 46 {  // '.'\n        = . p pos + . p pos 1\n        = frag ( __emit_any p )\n    } {\n        ? == c 94 {  // '^'\n            = . p pos + . p pos 1\n            = frag ( __emit_anchor p 0 )\n        } {\n            ? == c 36 {  // '$'\n                = . p pos + . p pos 1\n                = frag ( __emit_anchor p 1 )\n            } {\n                ? == c 40 {  // '('\n                    = . p pos + . p pos 1\n                    // Number the group at its OPENING paren, before the\n                    // body is parsed, so nested groups number the way\n                    // every regex dialect promises: `((a)(b))` is 1, 2, 3.\n                    = . p ngroups + . p ngroups 1\n                    : i g . p ngroups\n                    : i inner ( __parse_alt p )\n                    ? < inner 0 { ^ -1 } {}\n                    ? != ( __rx_peek p ) 41 { ^ -1 } {}\n                    = . p pos + . p pos 1\n                    : i s_open ( __rx_add_state p 7 * 2 g -1 -1 )\n                    : i s_close ( __rx_add_state p 7 + * 2 g 1 -1 -1 )\n                    : i f_open ( __frag s_open s_open )\n                    : i f_close ( __frag s_close s_close )\n                    = frag ( __emit_concat p ( __emit_concat p f_open inner ) f_close )\n                } {\n                    ? == c 91 {  // '['\n                        = . p pos + . p pos 1\n                        : i fc ( __parse_class p )\n                        ? < fc 0 { ^ -1 } {}\n                        = frag fc\n                    } {\n                        ? == c 92 {  // '\\\\'\n                            = . p pos + . p pos 1\n                            : i enc ( __rx_decode_escape p )\n                            : i kind / enc 65536\n                            : i val & enc 65535\n                            ? == kind 1 { = frag ( __emit_class p val ) }\n                            { = frag ( __emit_char p val ) }\n                        } {\n                            // Reject metachars that should not appear at atom start.\n                            ? | | | | | == c 42 == c 43 == c 63 == c 41 == c 124 == c 93 { ^ -1 } {}\n                            = . p pos + . p pos 1\n                            = frag ( __emit_char p c )\n                        }\n                    }\n                }\n            }\n        }\n    }\n    // Quantifier\n    ? < frag 0 { ^ -1 } {}\n    ? ! ( __rx_eof p ) {\n        : i q ( __rx_peek p )\n        ? == q 42 { = . p pos + . p pos 1 = frag ( __emit_star p frag ) } {\n            ? == q 43 { = . p pos + . p pos 1 = frag ( __emit_plus p frag ) } {\n                ? == q 63 { = . p pos + . p pos 1 = frag ( __emit_optional p frag ) } {}\n            }\n        }\n    } {}\n    ^ frag\n}\n\n@ __parse_seq inout RxParser p → i {\n    // Empty seq → epsilon fragment (one Eps state pointing nowhere; will\n    // be patched).\n    : ~ i acc -1\n    : ~ b done F\n    ~ ! done {\n        ? ( __rx_eof p ) { = done T } {\n            : i c ( __rx_peek p )\n            ? | == c 124 == c 41 { = done T } {\n                : i atom ( __parse_atom p )\n                ? < atom 0 { ^ -1 } {}\n                ? < acc 0 { = acc atom } { = acc ( __emit_concat p acc atom ) }\n            }\n        }\n    }\n    ? < acc 0 {\n        // Empty seq → single Eps state.\n        : i s1 ( __rx_add_state p 6 0 -1 -1 )\n        = acc ( __frag s1 s1 )\n    } {}\n    ^ acc\n}\n\n@ __parse_alt inout RxParser p → i {\n    : i first ( __parse_seq p )\n    ? < first 0 { ^ -1 } {}\n    : ~ i acc first\n    : ~ b done F\n    ~ ! done {\n        ? ( __rx_eof p ) { = done T } {\n            ? != ( __rx_peek p ) 124 { = done T } {\n                = . p pos + . p pos 1\n                : i rhs ( __parse_seq p )\n                ? < rhs 0 { ^ -1 } {}\n                = acc ( __emit_alt p acc rhs )\n            }\n        }\n    }\n    ^ acc\n}\n\n// ── Compile entry ───────────────────────────────────────────────────\n\n@ regex_compile s pattern → !Regex ParseErr {\n    : i n ( nurl_str_len pattern )\n    ? == n 0 {\n        ^ @ !Regex ParseErr { F @ ParseErr { Empty } }\n    } {}\n    : ~ RxParser p @ RxParser { pattern n 0 ( vec_new [i] ) ( vec_new [i] ) ( vec_new [i] ) 0 }\n    : i frag ( __parse_alt p )\n    ? < frag 0 {\n        ^ @ !Regex ParseErr { F @ ParseErr { BadFormat } }\n    } {}\n    ? < . p pos . p len {\n        // Trailing `)` or `]` is not consumed by parser → reject.\n        ^ @ !Regex ParseErr { F @ ParseErr { TrailingGarbage } }\n    } {}\n    // Patch the fragment exit to a fresh Match state.\n    : i match_state ( __rx_add_state p 0 0 -1 -1 )\n    ( __rx_patch_exit p ( __frag_exit frag ) match_state )\n    : i start_idx ( __frag_entry frag )\n    // The parser's tables move into the pattern.\n    ^ @ !Regex ParseErr { T @ Regex { ( shared_new [RegexImpl] @ RegexImpl { . p states . p classes . p class_starts start_idx . p ngroups } ) } }\n}\n\n@ Regex_share Regex r → Regex { ^ @ Regex { ( shared_clone [RegexImpl] . r ctl ) } }\n\n@ Regex_drop sink Regex r → v {}\n\n// Let go of `r` now rather than at the end of its owner's scope.\n@ regex_free sink Regex r → v {}\n\n// ── Match engine ────────────────────────────────────────────────────\n// Two-set NFA simulation. We store active states as a Vec[i] of state\n// indices, plus a parallel \"marked\" buffer (raw bytes via nurl_zalloc)\n// to dedupe. Each step advances current → next on consuming one byte,\n// then we swap.\n\n// Vec[i]-based active-set machinery — recursive ε-closure walk that\n// dedupes via a parallel `marked` vector. Char/Any/Class/Match states\n// land on the active list; Eps/Split/Anchor are zero-width and walked\n// transitively.\n\n@ __vi_fill ( Vec i ) v i n i val → v {\n    : ~ i k 0\n    ~ < k n { ( __vi_set v k val ) = k + k 1 }\n}\n\n// Copy one thread's slot array out of the flat list, and back in.\n@ __rx_caps_load ( Vec i ) caps ( Vec i ) work i base i nslots → v {\n    : ~ i k 0\n    ~ < k nslots { ( __vi_set work k ( __vi_get caps + base k ) ) = k + k 1 }\n}\n\n// ε-closure with capture slots — a Pike VM's `addthread`.\n//\n// `work` is the caller's slot array for the thread being added; a Save\n// state writes into it, recurses, and writes the old value back, so one\n// array serves the whole depth-first walk instead of a copy per branch.\n// The copy happens once, at the leaf, when the thread is appended.\n//\n// Dedup is still by state, and the FIRST thread to reach a state keeps\n// it. Since Split's out1 is walked before out2 and out1 is the greedy\n// branch, that ordering is what makes `(a*)(a*)` put everything in the\n// first group rather than splitting arbitrarily.\n@ __rx_add_thread ( Vec i ) states ( Vec i ) active ( Vec i ) marked ( Vec i ) caps ( Vec i ) work i nslots i s_idx i text_pos i text_len → v {\n    ? < s_idx 0 { ^ } {}\n    ? != 0 ( __vi_get marked s_idx ) { ^ } {}\n    ( __vi_set marked s_idx 1 )\n    : i kind ( __rx_state_kind states s_idx )\n    ? == kind 6 {\n        ( __rx_add_thread states active marked caps work nslots ( __rx_state_out1 states s_idx ) text_pos text_len )\n        ^\n    } {}\n    ? == kind 5 {\n        ( __rx_add_thread states active marked caps work nslots ( __rx_state_out1 states s_idx ) text_pos text_len )\n        ( __rx_add_thread states active marked caps work nslots ( __rx_state_out2 states s_idx ) text_pos text_len )\n        ^\n    } {}\n    ? == kind 4 {\n        : i a ( __rx_state_a states s_idx )\n        : b matches ? == a 0 == text_pos 0 == text_pos text_len\n        ? matches {\n            ( __rx_add_thread states active marked caps work nslots ( __rx_state_out1 states s_idx ) text_pos text_len )\n        } {}\n        ^\n    } {}\n    ? == kind 7 {\n        : i slot ( __rx_state_a states s_idx )\n        ? < slot nslots {\n            : i old ( __vi_get work slot )\n            ( __vi_set work slot text_pos )\n            ( __rx_add_thread states active marked caps work nslots ( __rx_state_out1 states s_idx ) text_pos text_len )\n            ( __vi_set work slot old )\n        } {\n            ( __rx_add_thread states active marked caps work nslots ( __rx_state_out1 states s_idx ) text_pos text_len )\n        }\n        ^\n    } {}\n    ( vec_push [i] active s_idx )\n    : ~ i k 0\n    ~ < k nslots { ( vec_push [i] caps ( __vi_get work k ) ) = k + k 1 }\n}\n\n@ __rx_clear_marked ( Vec i ) marked i n → v {\n    : ~ i k 0\n    ~ < k n {\n        ( __vi_set marked k 0 )\n        = k + k 1\n    }\n}\n\n// Per-search scratch: the Vec[i] the NFA simulation needs. These used to\n// be allocated (and freed) inside __rx_run_at, i.e. once per START\n// POSITION — 8005 allocations for a 2 KB subject in `regex_replace`.\n// They carry no state between runs, so every public entry point builds\n// one scratch up front and reuses it across the whole scan. Passing it\n// explicitly (rather than caching it in the Regex) keeps a compiled\n// Regex reentrant: two searches can run over the same Regex at once,\n// each with its own scratch.\n: RxScratch {\n    ( Vec i ) cur\n    ( Vec i ) nxt\n    ( Vec i ) marked_cur\n    ( Vec i ) marked_nxt\n    ( Vec i ) caps_cur  // flat: thread k owns [k*nslots, (k+1)*nslots)\n    ( Vec i ) caps_nxt\n    ( Vec i ) work  // one thread's slots, during the ε-closure\n    ( Vec i ) best  // the winning thread's slots\n    i nstates\n    i nslots\n}\n\n@ __rx_nstates Regex r → i {\n    : *RegexImpl impl ( shared_ptr [RegexImpl] . r ctl )\n    ^ / ( vec_len [i] . impl states ) 4\n}\n\n// Capture groups in the pattern. Group `k` occupies slots 2k and 2k+1;\n// slots 0 and 1 are the whole match, filled in by the caller.\n@ regex_ngroups Regex r → i {\n    : *RegexImpl impl ( shared_ptr [RegexImpl] . r ctl )\n    ^ . impl ngroups\n}\n\n@ __rx_nslots Regex r → i { ^ * 2 + ( regex_ngroups r ) 1 }\n\n// A Vec[i] of `n` zeros — the marked-set shape __vi_set writes into.\n@ __rx_zeros i n → ( Vec i ) {\n    : ( Vec i ) v ( vec_with_cap [i] n )\n    : ~ i k 0\n    ~ < k n { ( vec_push [i] v 0 ) = k + k 1 }\n    ^ v\n}\n\n@ __rx_scratch_new Regex r → RxScratch {\n    : i ns ( __rx_nstates r )\n    : i nsl ( __rx_nslots r )\n    ^ @ RxScratch {\n        ( vec_with_cap [i] ns )\n        ( vec_with_cap [i] ns )\n        ( __rx_zeros ns )\n        ( __rx_zeros ns )\n        ( vec_with_cap [i] * ns nsl )\n        ( vec_with_cap [i] * ns nsl )\n        ( __rx_zeros nsl )\n        ( __rx_zeros nsl )\n        ns\n        nsl\n    }\n}\n\n// Try to match starting at text_pos. Returns the longest match length\n// found at this start (≥0), or -1 if no match. `sc` is scratch owned by\n// the caller; its contents are reset here, so the same scratch can be\n// handed to every start position of a scan. On success `sc.best` holds\n// the winning thread's capture slots (absolute offsets, -1 for a group\n// that did not take part).\n@ __rx_run_at Regex r s text i text_len i text_pos RxScratch sc → i {\n    : *RegexImpl impl ( shared_ptr [RegexImpl] . r ctl )\n    : ( Vec i ) states . impl states\n    : ( Vec i ) classes . impl classes\n    : ( Vec i ) class_starts . impl class_starts\n    : i start . impl start\n    : i nstates . sc nstates\n    : i nslots . sc nslots\n    : ~ ( Vec i ) cur . sc cur\n    : ~ ( Vec i ) nxt . sc nxt\n    : ~ ( Vec i ) marked_cur . sc marked_cur\n    : ~ ( Vec i ) marked_nxt . sc marked_nxt\n    : ~ ( Vec i ) caps_cur . sc caps_cur\n    : ~ ( Vec i ) caps_nxt . sc caps_nxt\n    : ( Vec i ) work . sc work\n    : ( Vec i ) best_caps . sc best\n    ( vec_clear [i] cur )\n    ( vec_clear [i] nxt )\n    ( vec_clear [i] caps_cur )\n    ( vec_clear [i] caps_nxt )\n    ( __rx_clear_marked marked_cur nstates )\n    ( __rx_clear_marked marked_nxt nstates )\n    ( __vi_fill work nslots -1 )\n    ( __vi_fill best_caps nslots -1 )\n    ( __rx_add_thread states cur marked_cur caps_cur work nslots start text_pos text_len )\n\n    : ~ i best -1\n    // The start state may itself be the match (a zero-length match).\n    : ~ i k2 0\n    ~ < k2 ( vec_len [i] cur ) {\n        : i sx ( __vi_get cur k2 )\n        ? & == ( __rx_state_kind states sx ) 0 < best 0 {\n            = best 0\n            ( __rx_caps_load caps_cur best_caps * k2 nslots nslots )\n        } {}\n        = k2 + k2 1\n    }\n\n    : ~ i pos text_pos\n    : ~ b done F\n    ~ ! done {\n        ? >= pos text_len { = done T } {\n            : i ch ( nurl_str_at text text_len pos )\n            ( __rx_clear_marked marked_nxt nstates )\n            ( vec_clear [i] nxt )\n            ( vec_clear [i] caps_nxt )\n            : ~ i ki 0\n            ~ < ki ( vec_len [i] cur ) {\n                : i si ( __vi_get cur ki )\n                : i kind ( __rx_state_kind states si )\n                : ~ b consumes F\n                ? == kind 1 {  // Char\n                    ? == ( __rx_state_a states si ) ch { = consumes T } {}\n                } {\n                    ? == kind 2 {  // Any (not '\\n')\n                        ? != ch 10 { = consumes T } {}\n                    } {\n                        ? == kind 3 {  // Class\n                            : i ci ( __rx_state_a states si )\n                            ? ( __rx_class_test classes class_starts ci ch ) { = consumes T } {}\n                        } {}\n                    }\n                }\n                ? consumes {\n                    : i nxt_state ( __rx_state_out1 states si )\n                    ( __rx_caps_load caps_cur work * ki nslots nslots )\n                    ( __rx_add_thread states nxt marked_nxt caps_nxt work nslots nxt_state + pos 1 text_len )\n                } {}\n                = ki + ki 1\n            }\n            = pos + pos 1\n            // Swap cur/nxt, their marked sets and their capture stores.\n            : ( Vec i ) tmp cur\n            = cur nxt\n            = nxt tmp\n            : ( Vec i ) tmpm marked_cur\n            = marked_cur marked_nxt\n            = marked_nxt tmpm\n            : ( Vec i ) tmpc caps_cur\n            = caps_cur caps_nxt\n            = caps_nxt tmpc\n            // After consuming a byte, check whether any state in the new\n            // cur is a Match — record the longest.\n            : ~ i kj 0\n            ~ < kj ( vec_len [i] cur ) {\n                : i sk ( __vi_get cur kj )\n                ? & == ( __rx_state_kind states sk ) 0 > - pos text_pos best {\n                    = best - pos text_pos\n                    ( __rx_caps_load caps_cur best_caps * kj nslots nslots )\n                } {}\n                = kj + kj 1\n            }\n            ? == ( vec_len [i] cur ) 0 { = done T } {}\n        }\n    }\n\n    ^ best\n}\n\n// ── Public match API ────────────────────────────────────────────────\n\n@ regex_test Regex r s text → b {\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : ~ i pos 0\n    : ~ b hit F\n    ~ & ! hit <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? >= m 0 { = hit T } { = pos + pos 1 }\n    }\n    ^ hit\n}\n\n@ regex_match Regex r s text → b {\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : i m ( __rx_run_at r text n 0 sc )\n    ^ == m n\n}\n\n@ regex_find Regex r s text → ?Match {\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : ~ i pos 0\n    : ~ i hit_at -1\n    : ~ i hit_len 0\n    ~ & < hit_at 0 <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? >= m 0 { = hit_at pos = hit_len m } { = pos + pos 1 }\n    }\n    ? >= hit_at 0 { ^ @ ?Match { T @ Match { hit_at hit_len } } } {}\n    ^ @ ?Match { F @ Match { 0 0 } }\n}\n\n// The leftmost match, WITH its capture groups.\n//\n// `slots` is cleared and refilled with `2 * (ngroups + 1)` entries of\n// absolute byte offsets into `text`: slots 0 and 1 are the whole match's\n// start and end, and group k occupies 2k and 2k+1. A group that did not\n// take part in the match (the untaken side of an alternation, a `?` that\n// matched nothing) reads -1 in BOTH of its slots — the caller must test\n// for it rather than assume a span.\n//\n//     : ( Vec i ) slots ( vec_new [i] )\n//     ?? ( regex_find_caps r line slots ) {\n//       T m → { : i g1s ( __vi_get slots 2 ) … }\n//       F _ → { }\n//     }\n@ regex_find_caps Regex r s text ( Vec i ) slots → ?Match {\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : i nslots . sc nslots\n    ( vec_clear [i] slots )\n    : ~ i k 0\n    ~ < k nslots { ( vec_push [i] slots -1 ) = k + k 1 }\n    : ~ i pos 0\n    : ~ i hit_at -1\n    : ~ i hit_len 0\n    ~ & < hit_at 0 <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? >= m 0 {\n            = hit_at pos\n            = hit_len m\n            : ~ i j 0\n            ~ < j nslots { ( __vi_set slots j ( __vi_get . sc best j ) ) = j + j 1 }\n            ( __vi_set slots 0 pos )\n            ( __vi_set slots 1 + pos m )\n        } { = pos + pos 1 }\n    }\n    ? >= hit_at 0 { ^ @ ?Match { T @ Match { hit_at hit_len } } } {}\n    ^ @ ?Match { F @ Match { 0 0 } }\n}\n\n// Expand a replacement template against a match's capture slots — the\n// `s///` right-hand side every editor and every sed writes:\n//\n//   &        the whole match          \\1 … \\9   capture group 1 … 9\n//   \\&       a literal ampersand      \\\\        a literal backslash\n//   \\n \\t \\r the usual escapes        \\0        the whole match\n//\n// A reference to a group that did not participate expands to nothing,\n// which is what makes `s/(a)|(b)/[\\1\\2]/` produce `[a]` and `[b]`\n// rather than one of them failing.\n//\n// `regex_replace` deliberately does NOT do this — it inserts its\n// replacement verbatim, which is what a caller substituting arbitrary\n// user text needs. Use this when the template is a pattern language.\n@ regex_expand s text ( Vec i ) slots s tmpl → String {\n    : String out ( string_new )\n    : i tn ( nurl_str_len tmpl )\n    : i nslots ( vec_len [i] slots )\n    : ~ i i 0\n    ~ < i tn {\n        : i c ( nurl_str_at tmpl tn i )\n        ? == c 38 {\n            ( __rx_push_slot out text slots 0 nslots )\n            = i + i 1\n        } {\n            ? & == c 92 < + i 1 tn {\n                : i e ( nurl_str_at tmpl tn + i 1 )\n                = i + i 2\n                ? & >= e 48 <= e 57 {\n                    ( __rx_push_slot out text slots - e 48 nslots )\n                } {\n                    ? == e 110 { ( string_push_char out 10 ) } {\n                        ? == e 116 { ( string_push_char out 9 ) } {\n                            ? == e 114 { ( string_push_char out 13 ) } {\n                                ( string_push_char out e )\n                            } } }\n                }\n            } {\n                ( string_push_char out c )\n                = i + i 1\n            }\n        }\n    }\n    ^ out\n}\n\n@ __rx_push_slot String out s text ( Vec i ) slots i group i nslots → v {\n    : i a * 2 group\n    : i b + a 1\n    ? >= b nslots { ^ } {}\n    : i from ( __vi_get slots a )\n    : i to ( __vi_get slots b )\n    ? | < from 0 < to from { ^ } {}\n    : i n ( nurl_str_len text )\n    : ~ i k from\n    ~ & < k to < k n {\n        ( string_push_char out ( nurl_str_at text n k ) )\n        = k + k 1\n    }\n}\n\n@ regex_find_all Regex r s text → ( Vec Match ) {\n    : ( Vec Match ) out ( vec_new [Match] )\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : ~ i pos 0\n    ~ <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? >= m 0 {\n            ( vec_push [Match] out @ Match { pos m } )\n            ? == m 0 { = pos + pos 1 } { = pos + pos m }\n        } {\n            = pos + pos 1\n        }\n    }\n    ^ out\n}\n\n@ regex_replace Regex r s text s repl → String {\n    : String out ( string_with_cap ( nurl_str_len text ) )\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : ~ i pos 0\n    ~ <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? >= m 0 {\n            ( string_push_str out repl )\n            ? == m 0 {\n                ? < pos n {\n                    ( string_push_char out ( nurl_str_at text n pos ) )\n                    = pos + pos 1\n                } { = pos + pos 1 }\n            } { = pos + pos m }\n        } {\n            ? < pos n {\n                ( string_push_char out ( nurl_str_at text n pos ) )\n            } {}\n            = pos + pos 1\n        }\n    }\n    ^ out\n}\n\n@ regex_split Regex r s text → ( Vec String ) {\n    : ( Vec String ) out ( vec_new [String] )\n    : i n ( nurl_str_len text )\n    : RxScratch sc ( __rx_scratch_new r )\n    : ~ i seg_start 0\n    : ~ i pos 0\n    ~ <= pos n {\n        : i m ( __rx_run_at r text n pos sc )\n        ? & >= m 0 > m 0 {\n            // Emit segment [seg_start..pos)\n            : i seg_len - pos seg_start\n            : String s1 ( string_with_cap seg_len )\n            : ~ i k seg_start\n            ~ < k pos {\n                ( string_push_char s1 ( nurl_str_at text n k ) )\n                = k + k 1\n            }\n            ( vec_push [String] out s1 )\n            = pos + pos m\n            = seg_start pos\n        } { = pos + pos 1 }\n    }\n    // Emit final segment [seg_start..n)\n    : i tail_len - n seg_start\n    : String tail ( string_with_cap tail_len )\n    : ~ i k seg_start\n    ~ < k n {\n        ( string_push_char tail ( nurl_str_at text n k ) )\n        = k + k 1\n    }\n    ( vec_push [String] out tail )\n    ^ out\n}\n","bytes":39056}