`nx_rxfull.nx` source

↩ module page · 768 lines · 35338 B
1// nx_regex.nx -- SOVEREIGN regex engine (operator 2026-07-08/09: push the JS engine to run modern bundles;
2// regex is the last bundle-blocker + a PARSE-level one). Standalone + self-gated so it is proven before wiring
3// into the JS lexer/RegExp. Architecture = Cox's "regex VM" (compile the pattern to a flat INSTRUCTION PROGRAM,
4// then a backtracking matcher over it) -- flat dispatch dodges nx_cc's deep-else-nest miscompile, and it makes
5// captures + step-bounding clean. STEP + DEPTH bounded => a hostile bundle regex can NEVER hang/crash the crawler
6// (fails safe to no-match). Covers: literals, ., char classes [..] (ranges/negation/predef), \d\w\s\D\W\S,
7// anchors ^ $, quantifiers * + ? and {n} {n,} {n,m} (greedy + lazy ?), groups (capturing + (?:..)), alternation
8// |, escapes, \b \B word-boundary, flags i (icase) m (multiline) s (dotall). Leftmost match + capture groups.
9// license_tier: ORIGINAL
10import "nx_syscalls.nx"
11
12// ---- instruction opcodes (program stride 3: [op, a, b]) ----
13const RE_CHAR:   i64 = 1    // a = charcode (lowered if icase)
14const RE_ANY:    i64 = 2    // any char (not newline unless dotall)
15const RE_CLASS:  i64 = 3    // a = class-table base
16const RE_SPLIT:  i64 = 4    // a,b = two pcs to try (a first)
17const RE_JMP:    i64 = 5    // a = pc
18const RE_SAVE:   i64 = 6    // a = capture slot
19const RE_MATCH:  i64 = 7
20const RE_BOL:    i64 = 8    // ^
21const RE_EOL:    i64 = 9    // $
22const RE_WORDB:  i64 = 10   // \b
23const RE_NWORDB: i64 = 11   // \B
24const RE_AHEAD:  i64 = 12   // a=negate(0 pos/1 neg) b=after-pc; ZERO-WIDTH sub-match of [p+1 .. RE_AEND)
25const RE_AEND:   i64 = 13   // terminates a lookahead sub-match program (acts like MATCH for the sub-run)
26const RE_BREF:   i64 = 14   // a=groupnum; re-match the text a prior capture group matched (JS \1..\9)
27const RE_MARK:   i64 = 15   // a=slot; record current input pos into marks[slot] (loop-entry stamp)
28const RE_BACK:   i64 = 16   // a=slot b=target; take the loop back-edge to `target` ONLY if pos advanced since
                          //   marks[slot] -- a ZERO-WIDTH iteration FAILS (ES RepeatMatcher), killing `(a*)*`
                          //   catastrophic-empty-loop recursion (was a native-stack SEGV before the depth cap).
31const RE_LOOPA:  i64 = 17   // a=min(0 star/1 plus) b=greedy; the SINGLE consuming atom insn sits at p+1 and the
                          //   continuation at p+2. Matches the atom ITERATIVELY (count run, then try counts
                          //   longest-first/shortest-first) -> O(1) recursion depth per loop instead of one
                          //   SPLIT frame PER CHARACTER -- \s+ \S* [^x]* .* on KB-scale strings stay flat.
35
36// ---- AST node kinds (node stride 6: [kind, a, b, c, d, e]) ----
37const RX_CHAR:   i64 = 1    // a=code
38const RX_ANY:    i64 = 2
39const RX_CLASS:  i64 = 3    // a=class base
40const RX_CONCAT: i64 = 4    // a=left b=right
41const RX_ALT:    i64 = 5    // a=left b=right
42const RX_STAR:   i64 = 6    // a=child b=greedy
43const RX_PLUS:   i64 = 7    // a=child b=greedy
44const RX_QUEST:  i64 = 8    // a=child b=greedy
45const RX_REPEAT: i64 = 9    // a=child b=min c=max(-1=inf) d=greedy
46const RX_GROUP:  i64 = 10   // a=child b=capturing c=groupnum
47const RX_BOL:    i64 = 11
48const RX_EOL:    i64 = 12
49const RX_WORDB:  i64 = 13
50const RX_NWORDB: i64 = 14
51const RX_EMPTY:  i64 = 15
52const RX_LOOKAHEAD: i64 = 16   // a=child b=negate(0 pos/1 neg)  -- (?=..) / (?!..)
53const RX_BACKREF:   i64 = 17   // a=groupnum  -- \1..\9
54
55// ---- flags ----
56const RXF_I: i64 = 1
57const RXF_M: i64 = 2
58const RXF_S: i64 = 4
59const RXF_G: i64 = 8
60
61// ---- caps (fail-safe, never silent-corrupt) ----
62const RX_MAXNODE:  i64 = 8192
63const RX_MAXPROG:  i64 = 16384
64const RX_MAXCLASS: i64 = 8192
65const RX_MAXREP:   i64 = 1000     // {n,m} expansion clamp
66const RX_MAXDEPTH: i64 = 6000     // backtracking recursion cap (stack-overflow guard)
67const RX_FUEL:     i64 = 5000000  // total backtracking steps (catastrophic-backtrack guard)
68
69struct Regex { prog: *i64, nprog: i64, classes: *i64, ngroup: i64, flags: i64, nsave: i64, ok: i64, nmark: i64 }
70const REGEX_BYTES: i64 = 64
71
72struct RxP { pat: *u8, plen: i64, pos: i64, nodes: *i64, nn: i64, classes: *i64, nc: i64, ngroup: i64, flags: i64, err: i64 }
73const RXP_BYTES: i64 = 80
74
75struct Rx { s: *u8, slen: i64, prog: *i64, classes: *i64, flags: i64, saves: *i64, fuel: *i64, marks: *i64 }
76const RX_BYTES: i64 = 64
77
78// ---------- small char helpers ----------
79func rx_lc(c: i64) -> i64 { if c >= 65 { if c <= 90 { return c + 32 } } return c }
80func rx_swapcase(c: i64) -> i64 { if c >= 65 { if c <= 90 { return c + 32 } } if c >= 97 { if c <= 122 { return c - 32 } } return c }
81func rx_isword(c: i64) -> i64 { if c >= 48 { if c <= 57 { return 1 } } if c >= 65 { if c <= 90 { return 1 } } if c >= 97 { if c <= 122 { return 1 } } if c == 95 { return 1 } return 0 }
82
83// ---------- parser cursor ----------
84func rp_peek(p: *RxP) -> i64 { if p.pos < p.plen { return (p.pat[p.pos]) as i64 } return 0 - 1 }
85func rp_at(p: *RxP, off: i64) -> i64 { let q: i64 = p.pos + off; if q < p.plen { return (p.pat[q]) as i64 } return 0 - 1 }
86func rp_adv(p: *RxP) -> i64 { p.pos = p.pos + 1; return 0 }
87// create a node (kind,a,b,c); d/e default 0. returns node index.
88func rp_node(p: *RxP, kind: i64, a: i64, b: i64, c: i64) -> i64 {
  let i: i64 = p.nn
  if i >= RX_MAXNODE { p.err = 1; return 0 }
  let base: i64 = i * 6
  let nd: *i64 = p.nodes
  nd[base] = kind; nd[base + 1] = a; nd[base + 2] = b; nd[base + 3] = c; nd[base + 4] = 0; nd[base + 5] = 0
  p.nn = i + 1
  return i
96}
97
98// append a [lo,hi] range to the class arena (used while building a class)
99func rp_add_range(p: *RxP, lo: i64, hi: i64) -> i64 { let cl: *i64 = p.classes; if p.nc + 2 > RX_MAXCLASS { p.err = 1; return 0 } cl[p.nc] = lo; cl[p.nc + 1] = hi; p.nc = p.nc + 2; return 0 }
100// add the ranges for a predefined class into the current build (which: 0 digit / 1 word / 2 space)
101func rp_add_predef(p: *RxP, which: i64) -> i64 {
  if which == 0 { rp_add_range(p, 48, 57); return 0 }
  if which == 1 { rp_add_range(p, 48, 57); rp_add_range(p, 65, 90); rp_add_range(p, 97, 122); rp_add_range(p, 95, 95); return 0 }
  rp_add_range(p, 9, 13); rp_add_range(p, 32, 32); return 0
105}
106// build a standalone one-class from a predefined set (neg=1 for \D\W\S) -> RX_CLASS node
107func rp_predef_node(p: *RxP, which: i64, neg: i64) -> i64 {
  let cl: *i64 = p.classes
  let base: i64 = p.nc
  if base + 2 > RX_MAXCLASS { p.err = 1; return 0 }
  cl[base] = neg; cl[base + 1] = 0; p.nc = base + 2
  rp_add_predef(p, which)
  cl[base + 1] = (p.nc - base - 2) / 2
  return rp_node(p, RX_CLASS, base, 0, 0)
115}
116
117// read ONE class-escape LITERAL value (the '\' is consumed by the caller; \d\w\s predefs handled separately).
118// Handles \xHH (byte) and \uHHHH (FULL code point -- values >0xFF land in a range that matches NO byte, which
119// is exactly right for a byte-string engine: `Ĩ-￿` matches nothing in ASCII, per V8). \n\t\r etc via
120// rx_esc_char. Consumes the escape char + any hex digits.
121func rp_class_esc_val(p: *RxP) -> i64 {
  let e: i64 = rp_peek(p); rp_adv(p)
  if e == 120 {                                  // \xHH
      let h1: i64 = rx_hexval(rp_peek(p))
      let h2: i64 = rx_hexval(rp_at(p, 1))
      if h1 >= 0 { if h2 >= 0 { rp_adv(p); rp_adv(p); return h1 * 16 + h2 } }
      return 120
  }
  if e == 117 {                                  // \uHHHH -> full code point (may exceed byte range)
      let u1: i64 = rx_hexval(rp_peek(p))
      let u2: i64 = rx_hexval(rp_at(p, 1))
      let u3: i64 = rx_hexval(rp_at(p, 2))
      let u4: i64 = rx_hexval(rp_at(p, 3))
      if u1 >= 0 { if u2 >= 0 { if u3 >= 0 { if u4 >= 0 {
          rp_adv(p); rp_adv(p); rp_adv(p); rp_adv(p)
          return ((u1 * 16 + u2) * 16 + u3) * 16 + u4
      } } } }
      return 117
  }
  return rx_esc_char(e)
141}
142// parse a [...] class -> RX_CLASS node
143func rp_class(p: *RxP) -> i64 {
  rp_adv(p)                                  // consume '['
  let cl: *i64 = p.classes
  let base: i64 = p.nc
  if base + 2 > RX_MAXCLASS { p.err = 1; return 0 }
  var neg: i64 = 0
  if rp_peek(p) == 94 { neg = 1; rp_adv(p) }  // ^
  cl[base] = neg; cl[base + 1] = 0; p.nc = base + 2
  var go: i64 = 1
  while go == 1 {
      let c: i64 = rp_peek(p)
      if c < 0 { p.err = 1; go = 0 }
      else {
          if c == 93 { rp_adv(p); go = 0 }    // ']'
          else {
              if c == 92 {                    // '\' escape inside class
                  rp_adv(p)                   // consume backslash
                  let e: i64 = rp_peek(p)
                  if e == 100 { rp_adv(p); rp_add_predef(p, 0) }
                  else { if e == 119 { rp_adv(p); rp_add_predef(p, 1) }
                  else { if e == 115 { rp_adv(p); rp_add_predef(p, 2) }
                  else { let lit: i64 = rp_class_esc_val(p); rp_class_lit(p, lit) } } }   // \x \u \n .. + range
              } else {
                  rp_adv(p)
                  rp_class_lit(p, c)
              }
          }
      }
  }
  if p.err == 1 { return 0 }
  cl[base + 1] = (p.nc - base - 2) / 2
  return rp_node(p, RX_CLASS, base, 0, 0)
175}
176// a literal class member `lo` -- maybe a range `lo-hi` (peek at p.pos which is AFTER lo was consumed).
177func rp_class_lit(p: *RxP, lo: i64) -> i64 {
  if rp_peek(p) == 45 { if rp_at(p, 1) != 93 { if rp_at(p, 1) >= 0 {   // '-' and next isn't ']'
      rp_adv(p)                               // consume '-'
      var hi: i64 = rp_peek(p)
      if hi == 92 { rp_adv(p); hi = rp_class_esc_val(p) }   // \x/\u/\n.. hi bound (consumes esc + hex)
      else { rp_adv(p) }                      // literal hi char
      rp_add_range(p, lo, hi)
      return 0
  } } }
  rp_add_range(p, lo, lo)
  return 0
188}
189
190// hex digit -> value (0-15) or -1.
191func rx_hexval(c: i64) -> i64 {
  if c >= 48 { if c <= 57 { return c - 48 } }
  if c >= 97 { if c <= 102 { return c - 87 } }
  if c >= 65 { if c <= 70 { return c - 55 } }
  return 0 - 1
196}
197// decode a backslash-escape char (the byte AFTER '\') to its literal code.
198func rx_esc_char(e: i64) -> i64 {
  if e == 110 { return 10 }   // \n
  if e == 116 { return 9 }    // \t
  if e == 114 { return 13 }   // \r
  if e == 102 { return 12 }   // \f
  if e == 118 { return 11 }   // \v
  if e == 48  { return 0 }    // \0
  return e                    // \\ \. \/ \[ ... -> the literal char
206}
207
208// parse an escape in ATOM context -> a node (class / boundary / char)
209func rp_escape(p: *RxP) -> i64 {
  rp_adv(p)                                  // consume '\'
  let e: i64 = rp_peek(p); rp_adv(p)
  if e == 100 { return rp_predef_node(p, 0, 0) }  // \d
  if e == 68  { return rp_predef_node(p, 0, 1) }  // \D
  if e == 119 { return rp_predef_node(p, 1, 0) }  // \w
  if e == 87  { return rp_predef_node(p, 1, 1) }  // \W
  if e == 115 { return rp_predef_node(p, 2, 0) }  // \s
  if e == 83  { return rp_predef_node(p, 2, 1) }  // \S
  if e == 98  { return rp_node(p, RX_WORDB, 0, 0, 0) }   // \b
  if e == 66  { return rp_node(p, RX_NWORDB, 0, 0, 0) }  // \B
  if e == 49  { return rp_backref_node(p, 1) }           // \1 .. \9 backreference
  if e == 50  { return rp_backref_node(p, 2) }
  if e == 51  { return rp_backref_node(p, 3) }
  if e == 52  { return rp_backref_node(p, 4) }
  if e == 53  { return rp_backref_node(p, 5) }
  if e == 54  { return rp_backref_node(p, 6) }
  if e == 55  { return rp_backref_node(p, 7) }
  if e == 56  { return rp_backref_node(p, 8) }
  if e == 57  { return rp_backref_node(p, 9) }
  if e == 120 {                                          // \xHH -> literal byte
      let h1: i64 = rx_hexval(rp_peek(p))
      let h2: i64 = rx_hexval(rp_at(p, 1))
      if h1 >= 0 { if h2 >= 0 {
          rp_adv(p); rp_adv(p)
          var xc: i64 = h1 * 16 + h2
          if (p.flags & RXF_I) != 0 { xc = rx_lc(xc) }
          return rp_node(p, RX_CHAR, xc, 0, 0)
      } }
  }
  if e == 117 {                                          // \uHHHH -> FULL code point (NOT low-byte: a value
      let u1: i64 = rx_hexval(rp_peek(p))                //  >0xFF then matches NO byte, which is correct for
      let u2: i64 = rx_hexval(rp_at(p, 1))               //  a byte-string engine -- ` ` must NOT alias '('.
      let u3: i64 = rx_hexval(rp_at(p, 2))
      let u4: i64 = rx_hexval(rp_at(p, 3))
      if u1 >= 0 { if u2 >= 0 { if u3 >= 0 { if u4 >= 0 {
          rp_adv(p); rp_adv(p); rp_adv(p); rp_adv(p)
          var uc: i64 = ((u1 * 16 + u2) * 16 + u3) * 16 + u4
          if (p.flags & RXF_I) != 0 { uc = rx_lc(uc) }
          return rp_node(p, RX_CHAR, uc, 0, 0)
      } } } }
  }
  var lit: i64 = rx_esc_char(e)
  if (p.flags & RXF_I) != 0 { lit = rx_lc(lit) }
  return rp_node(p, RX_CHAR, lit, 0, 0)
254}
255// backref node; a group number that hasn't been opened YET (forward ref) is a JS octal/empty edge -> if the
256// referenced group index exceeds the total this parse will see, the matcher treats an unset span as empty.
257func rp_backref_node(p: *RxP, g: i64) -> i64 { return rp_node(p, RX_BACKREF, g, 0, 0) }
258
259// atom := group | class | . | ^ | $ | \esc | literal
260func rp_atom(p: *RxP) -> i64 {
  let c: i64 = rp_peek(p)
  if c == 40 {                                // '('
      rp_adv(p)
      var capturing: i64 = 1
      var gnum: i64 = 0
      if rp_peek(p) == 63 {                   // (?
          let c2: i64 = rp_at(p, 1)
          if c2 == 58 { capturing = 0; rp_adv(p); rp_adv(p) }            // (?:
          else { if c2 == 61 {                                          // (?= positive lookahead
              rp_adv(p); rp_adv(p)
              let la: i64 = rp_alt(p)
              if rp_peek(p) != 41 { p.err = 1; return 0 }
              rp_adv(p)
              return rp_node(p, RX_LOOKAHEAD, la, 0, 0)
          }
          else { if c2 == 33 {                                          // (?! negative lookahead
              rp_adv(p); rp_adv(p)
              let ln: i64 = rp_alt(p)
              if rp_peek(p) != 41 { p.err = 1; return 0 }
              rp_adv(p)
              return rp_node(p, RX_LOOKAHEAD, ln, 1, 0)
          }
          else { p.err = 1; return 0 } } }    // (?<  lookbehind still unsupported -> decline
      }
      if capturing == 1 { p.ngroup = p.ngroup + 1; gnum = p.ngroup }
      let child: i64 = rp_alt(p)
      if rp_peek(p) != 41 { p.err = 1; return 0 }
      rp_adv(p)
      return rp_node(p, RX_GROUP, child, capturing, gnum)
  }
  if c == 91 { return rp_class(p) }           // '['
  if c == 46 { rp_adv(p); return rp_node(p, RX_ANY, 0, 0, 0) }   // '.'
  if c == 94 { rp_adv(p); return rp_node(p, RX_BOL, 0, 0, 0) }   // '^'
  if c == 36 { rp_adv(p); return rp_node(p, RX_EOL, 0, 0, 0) }   // '$'
  if c == 92 { return rp_escape(p) }          // '\'
  if c < 0 { return rp_node(p, RX_EMPTY, 0, 0, 0) }
  rp_adv(p)
  var lit: i64 = c
  if (p.flags & RXF_I) != 0 { lit = rx_lc(lit) }
  return rp_node(p, RX_CHAR, lit, 0, 0)
301}
302
303// parse an optional {n} {n,} {n,m}. On success returns 1 and fills box[0]=min box[1]=max(-1 inf).
304// On not-a-quantifier restores pos and returns 0. (a bare '{' is then a literal.)
305func rp_brace(p: *RxP, box: *i64) -> i64 {
  let save: i64 = p.pos
  rp_adv(p)                                   // consume '{'
  var haven: i64 = 0
  var n: i64 = 0
  var d: i64 = rp_peek(p)
  while d >= 48 { if d <= 57 { n = n * 10 + (d - 48); haven = 1; rp_adv(p); d = rp_peek(p) } else { d = 0 - 1 } }
  if haven == 0 { p.pos = save; return 0 }
  var mx: i64 = n
  if rp_peek(p) == 44 {                        // ','
      rp_adv(p)
      if rp_peek(p) == 125 { mx = 0 - 1 }      // {n,}
      else {
          var m: i64 = 0; var havem: i64 = 0
          var d2: i64 = rp_peek(p)
          while d2 >= 48 { if d2 <= 57 { m = m * 10 + (d2 - 48); havem = 1; rp_adv(p); d2 = rp_peek(p) } else { d2 = 0 - 1 } }
          if havem == 0 { p.pos = save; return 0 }
          mx = m
      }
  }
  if rp_peek(p) != 125 { p.pos = save; return 0 }
  rp_adv(p)                                   // consume '}'
  box[0] = n; box[1] = mx
  return 1
329}
330
331// repeat := atom quantifier?    (quantifier: * + ? {n,m}, each with optional lazy '?')
332func rp_repeat(p: *RxP) -> i64 {
  let atom: i64 = rp_atom(p)
  if p.err == 1 { return atom }
  let c: i64 = rp_peek(p)
  if c == 42 { rp_adv(p); let g: i64 = rp_lazy(p); return rp_wrap(p, RX_STAR, atom, g, 0, 0) }   // *
  if c == 43 { rp_adv(p); let g: i64 = rp_lazy(p); return rp_wrap(p, RX_PLUS, atom, g, 0, 0) }   // +
  if c == 63 { rp_adv(p); let g: i64 = rp_lazy(p); return rp_wrap(p, RX_QUEST, atom, g, 0, 0) }  // ?
  if c == 123 {                               // '{'
      let box: *i64 = sys_mmap(16) as *i64
      if rp_brace(p, box) == 1 {
          let g: i64 = rp_lazy(p)
          return rp_wrap(p, RX_REPEAT, atom, box[0], box[1], g)
      }
  }
  return atom
347}
348// consume an optional lazy '?' after a quantifier -> greedy(1) / lazy(0)
349func rp_lazy(p: *RxP) -> i64 { if rp_peek(p) == 63 { rp_adv(p); return 0 } return 1 }
350// build a quantifier wrapper node; RX_REPEAT stores greedy in slot d (nd[idx*6+4]).
351func rp_wrap(p: *RxP, kind: i64, child: i64, x: i64, y: i64, g: i64) -> i64 {
  if kind == RX_REPEAT {
      let idx: i64 = rp_node(p, RX_REPEAT, child, x, y)
      p.nodes[idx * 6 + 4] = g
      return idx
  }
  return rp_node(p, kind, child, x, 0)         // STAR/PLUS/QUEST: b=greedy
358}
359
360// concat := repeat*   (until '|' ')' or end)
361func rp_concat(p: *RxP) -> i64 {
  var acc: i64 = 0 - 1
  var go: i64 = 1
  while go == 1 {
      let c: i64 = rp_peek(p)
      if c < 0 { go = 0 }
      else { if c == 124 { go = 0 } else { if c == 41 { go = 0 } else {
          let r: i64 = rp_repeat(p)
          if p.err == 1 { go = 0 } else {
              if acc < 0 { acc = r } else { acc = rp_node(p, RX_CONCAT, acc, r, 0) }
          }
      } } }
  }
  if acc < 0 { acc = rp_node(p, RX_EMPTY, 0, 0, 0) }
  return acc
376}
377
378// alt := concat ('|' concat)*
379func rp_alt(p: *RxP) -> i64 {
  var left: i64 = rp_concat(p)
  var go: i64 = 1
  while go == 1 {
      if rp_peek(p) == 124 {                  // '|'
          rp_adv(p)
          let right: i64 = rp_concat(p)
          left = rp_node(p, RX_ALT, left, right, 0)
          if p.err == 1 { go = 0 }
      } else { go = 0 }
  }
  return left
391}
392
393// ---------- compile AST -> program ----------
394func rc_emit(prog: *i64, npp: *i64, op: i64, a: i64, b: i64) -> i64 {
  let i: i64 = npp[0]
  if i >= RX_MAXPROG { return i }
  prog[i * 3] = op; prog[i * 3 + 1] = a; prog[i * 3 + 2] = b
  npp[0] = i + 1
  return i
400}
401// is the node ONE consuming atom (compiles to exactly one CHAR/CLASS/ANY insn)? -> RE_LOOPA flattenable.
402func rx_single_atom(nodes: *i64, node: i64) -> i64 {
  let k: i64 = nodes[node * 6]
  if k == RX_CHAR { return 1 }
  if k == RX_CLASS { return 1 }
  if k == RX_ANY { return 1 }
  return 0
408}
409// emit a greedy/lazy star loop over child-node `child`. Single-atom bodies flatten to RE_LOOPA (iterative,
410// O(1) depth). Composite bodies: npp[1] = the running MARK-slot counter (empty-loop guard): the back-edge is
411// RE_BACK (progress-checked) not an unconditional RE_JMP, so a zero-width iteration fails per the ES spec.
412func rc_star(nodes: *i64, child: i64, prog: *i64, npp: *i64, greedy: i64) -> i64 {
  if rx_single_atom(nodes, child) == 1 {
      rc_emit(prog, npp, RE_LOOPA, 0, greedy)
      rc(nodes, child, prog, npp)             // exactly one atom insn
      return 0
  }
  let slot: i64 = npp[1]; npp[1] = slot + 1
  let l1: i64 = npp[0]
  let s: i64 = rc_emit(prog, npp, RE_SPLIT, 0, 0)
  let cs: i64 = npp[0]
  rc_emit(prog, npp, RE_MARK, slot, 0)
  rc(nodes, child, prog, npp)
  rc_emit(prog, npp, RE_BACK, slot, l1)   // progress -> back to l1 (re-SPLIT); empty -> iteration fails
  let af: i64 = npp[0]
  if greedy == 1 { prog[s * 3 + 1] = cs; prog[s * 3 + 2] = af } else { prog[s * 3 + 1] = af; prog[s * 3 + 2] = cs }
  return 0
428}
429func rc(nodes: *i64, node: i64, prog: *i64, npp: *i64) -> i64 {
  let base: i64 = node * 6
  let k: i64 = nodes[base]
  let a: i64 = nodes[base + 1]
  let b: i64 = nodes[base + 2]
  let c: i64 = nodes[base + 3]
  let d: i64 = nodes[base + 4]
  if k == RX_CHAR { rc_emit(prog, npp, RE_CHAR, a, 0); return 0 }
  if k == RX_ANY { rc_emit(prog, npp, RE_ANY, 0, 0); return 0 }
  if k == RX_CLASS { rc_emit(prog, npp, RE_CLASS, a, 0); return 0 }
  if k == RX_BOL { rc_emit(prog, npp, RE_BOL, 0, 0); return 0 }
  if k == RX_EOL { rc_emit(prog, npp, RE_EOL, 0, 0); return 0 }
  if k == RX_WORDB { rc_emit(prog, npp, RE_WORDB, 0, 0); return 0 }
  if k == RX_NWORDB { rc_emit(prog, npp, RE_NWORDB, 0, 0); return 0 }
  if k == RX_EMPTY { return 0 }
  if k == RX_CONCAT { rc(nodes, a, prog, npp); rc(nodes, b, prog, npp); return 0 }
  if k == RX_ALT {
      let s: i64 = rc_emit(prog, npp, RE_SPLIT, 0, 0)
      prog[s * 3 + 1] = npp[0]
      rc(nodes, a, prog, npp)
      let j: i64 = rc_emit(prog, npp, RE_JMP, 0, 0)
      prog[s * 3 + 2] = npp[0]
      rc(nodes, b, prog, npp)
      prog[j * 3 + 1] = npp[0]
      return 0
  }
  if k == RX_STAR { rc_star(nodes, a, prog, npp, b); return 0 }
  if k == RX_PLUS {
      if rx_single_atom(nodes, a) == 1 {      // flatten: one mandatory + iterative tail
          rc_emit(prog, npp, RE_LOOPA, 1, b)
          rc(nodes, a, prog, npp)
          return 0
      }
      let slot: i64 = npp[1]; npp[1] = slot + 1
      let l1: i64 = npp[0]
      rc_emit(prog, npp, RE_MARK, slot, 0)
      rc(nodes, a, prog, npp)
      let s: i64 = rc_emit(prog, npp, RE_SPLIT, 0, 0)
      let bk: i64 = npp[0]
      rc_emit(prog, npp, RE_BACK, slot, l1)   // greedy loop arm: re-enter only if the body advanced
      let af: i64 = npp[0]
      if b == 1 { prog[s * 3 + 1] = bk; prog[s * 3 + 2] = af } else { prog[s * 3 + 1] = af; prog[s * 3 + 2] = bk }
      return 0
  }
  if k == RX_QUEST {
      let s: i64 = rc_emit(prog, npp, RE_SPLIT, 0, 0)
      let cs: i64 = npp[0]
      rc(nodes, a, prog, npp)
      let af: i64 = npp[0]
      if b == 1 { prog[s * 3 + 1] = cs; prog[s * 3 + 2] = af } else { prog[s * 3 + 1] = af; prog[s * 3 + 2] = cs }
      return 0
  }
  if k == RX_GROUP {
      if b == 1 {
          rc_emit(prog, npp, RE_SAVE, 2 * c, 0)
          rc(nodes, a, prog, npp)
          rc_emit(prog, npp, RE_SAVE, 2 * c + 1, 0)
      } else { rc(nodes, a, prog, npp) }
      return 0
  }
  if k == RX_BACKREF { rc_emit(prog, npp, RE_BREF, a, 0); return 0 }
  if k == RX_LOOKAHEAD {
      // RE_AHEAD(neg, after) ; <body> ; RE_AEND   -- the matcher runs the body as an isolated ZERO-WIDTH
      // sub-match (RE_AEND ends it), then continues at `after` with the input position UNCHANGED.
      let sh: i64 = rc_emit(prog, npp, RE_AHEAD, b, 0)
      rc(nodes, a, prog, npp)
      rc_emit(prog, npp, RE_AEND, 0, 0)
      prog[sh * 3 + 2] = npp[0]                 // after = pc past RE_AEND
      return 0
  }
  if k == RX_REPEAT {
      var i: i64 = 0
      while i < b { rc(nodes, a, prog, npp); i = i + 1 }   // min mandatory copies
      if c < 0 { rc_star(nodes, a, prog, npp, d); return 0 }   // {n,} -> star tail
      var opt: i64 = c - b
      if opt > RX_MAXREP { opt = RX_MAXREP }
      let sidx: *i64 = sys_mmap(8 * (opt + 1)) as *i64
      var oi: i64 = 0
      while oi < opt {                                    // (max-min) optional copies
          let s: i64 = rc_emit(prog, npp, RE_SPLIT, 0, 0)
          sidx[oi] = s
          prog[s * 3 + 1] = npp[0]                         // greedy default: try child (fall-through)
          rc(nodes, a, prog, npp)
          oi = oi + 1
      }
      let endpc: i64 = npp[0]
      oi = 0
      while oi < opt {
          let s: i64 = sidx[oi]
          if d == 1 { prog[s * 3 + 2] = endpc } else { let cs: i64 = prog[s * 3 + 1]; prog[s * 3 + 1] = endpc; prog[s * 3 + 2] = cs }
          oi = oi + 1
      }
      return 0
  }
  return 0
524}
525
526// ---------- matcher ----------
527func rx_class_match(rx: *Rx, cbase: i64, ch: i64) -> i64 {
  let cl: *i64 = rx.classes
  let neg: i64 = cl[cbase]
  let nr: i64 = cl[cbase + 1]
  var m: i64 = 0
  var k: i64 = 0
  while k < nr { let lo: i64 = cl[cbase + 2 + k * 2]; let hi: i64 = cl[cbase + 2 + k * 2 + 1]; if ch >= lo { if ch <= hi { m = 1 } } k = k + 1 }
  if m == 0 { if (rx.flags & RXF_I) != 0 {
      let c2: i64 = rx_swapcase(ch)
      var k2: i64 = 0
      while k2 < nr { let lo: i64 = cl[cbase + 2 + k2 * 2]; let hi: i64 = cl[cbase + 2 + k2 * 2 + 1]; if c2 >= lo { if c2 <= hi { m = 1 } } k2 = k2 + 1 }
  } }
  if neg == 1 { return 1 - m }
  return m
541}
542func rx_wordb(rx: *Rx, i: i64) -> i64 {
  var before: i64 = 0
  if i > 0 { if rx_isword((rx.s[i - 1]) as i64) == 1 { before = 1 } }
  var after: i64 = 0
  if i < rx.slen { if rx_isword((rx.s[i]) as i64) == 1 { after = 1 } }
  if before != after { return 1 }
  return 0
549}
550// backtracking matcher: return end position (>=0) on success (saves filled), -1 on fail/abort.
551// FLAT dispatch (each branch returns or updates p/i and re-loops) -- dodges nx_cc deep-else miscompile.
552func re_bt(rx: *Rx, pc: i64, sp: i64, depth: i64) -> i64 {
  if depth > RX_MAXDEPTH { return 0 - 1 }
  let prog: *i64 = rx.prog
  let s: *u8 = rx.s
  let slen: i64 = rx.slen
  let fuel: *i64 = rx.fuel
  var p: i64 = pc
  var i: i64 = sp
  var run: i64 = 1
  while run == 1 {
      if fuel[0] <= 0 { return 0 - 1 }
      fuel[0] = fuel[0] - 1
      let base: i64 = p * 3
      let op: i64 = prog[base]
      let a: i64 = prog[base + 1]
      let b: i64 = prog[base + 2]
      if op == RE_MATCH { return i }
      if op == RE_CHAR {
          if i >= slen { return 0 - 1 }
          var ch: i64 = (s[i]) as i64
          if (rx.flags & RXF_I) != 0 { ch = rx_lc(ch) }
          if ch != a { return 0 - 1 }
          p = p + 1; i = i + 1
      }
      if op == RE_ANY {
          if i >= slen { return 0 - 1 }
          if (rx.flags & RXF_S) == 0 { let dc: i64 = (s[i]) as i64; if dc == 10 { return 0 - 1 } if dc == 13 { return 0 - 1 } }   // `.` excludes LF+CR (V8)
          p = p + 1; i = i + 1
      }
      if op == RE_CLASS {
          if i >= slen { return 0 - 1 }
          if rx_class_match(rx, a, (s[i]) as i64) == 0 { return 0 - 1 }
          p = p + 1; i = i + 1
      }
      if op == RE_JMP { p = a }
      if op == RE_SPLIT {
          let r: i64 = re_bt(rx, a, i, depth + 1)
          if r >= 0 { return r }
          p = b
      }
      if op == RE_SAVE {
          let sv: *i64 = rx.saves
          let old: i64 = sv[a]
          sv[a] = i
          let r2: i64 = re_bt(rx, p + 1, i, depth + 1)
          if r2 >= 0 { return r2 }
          sv[a] = old
          return 0 - 1
      }
      if op == RE_BOL {
          var okb: i64 = 0
          if i == 0 { okb = 1 }
          if okb == 0 { if (rx.flags & RXF_M) != 0 { if ((s[i - 1]) as i64) == 10 { okb = 1 } } }
          if okb == 0 { return 0 - 1 }
          p = p + 1
      }
      if op == RE_EOL {
          var oke: i64 = 0
          if i == slen { oke = 1 }
          if oke == 0 { if (rx.flags & RXF_M) != 0 { if ((s[i]) as i64) == 10 { oke = 1 } } }
          if oke == 0 { return 0 - 1 }
          p = p + 1
      }
      if op == RE_WORDB { if rx_wordb(rx, i) == 0 { return 0 - 1 } p = p + 1 }
      if op == RE_NWORDB { if rx_wordb(rx, i) == 1 { return 0 - 1 } p = p + 1 }
      if op == RE_AEND { return i }             // lookahead sub-match terminator: success at current pos
      if op == RE_AHEAD {                       // a=neg b=after; run [p+1..RE_AEND) zero-width
          let sub: i64 = re_bt(rx, p + 1, i, depth + 1)
          var matched: i64 = 0
          if sub >= 0 { matched = 1 }
          if a == 0 { if matched == 0 { return 0 - 1 } }   // positive: body MUST match here
          if a == 1 { if matched == 1 { return 0 - 1 } }   // negative: body must NOT match here
          p = b                                 // continue after the assertion; i UNCHANGED (zero-width)
      }
      if op == RE_LOOPA {                       // a=min b=greedy; atom insn at p+1, continuation at p+2.
          let ap: i64 = (p + 1) * 3             // count the atom's maximal run ITERATIVELY (no recursion),
          let akind: i64 = prog[ap]             // then try lengths longest-first (greedy) / shortest-first
          let aa: i64 = prog[ap + 1]            // (lazy); each candidate recurses the continuation ONCE.
          var cnt: i64 = 0
          var j: i64 = i
          var scan: i64 = 1
          while scan == 1 {
              if j >= slen { scan = 0 } else {
                  let ch0: i64 = (s[j]) as i64
                  var okc: i64 = 0
                  if akind == RE_CHAR { var c2: i64 = ch0; if (rx.flags & RXF_I) != 0 { c2 = rx_lc(c2) } if c2 == aa { okc = 1 } }
                  if akind == RE_CLASS { okc = rx_class_match(rx, aa, ch0) }
                  if akind == RE_ANY { okc = 1; if (rx.flags & RXF_S) == 0 { if ch0 == 10 { okc = 0 } if ch0 == 13 { okc = 0 } } }
                  if okc == 1 { j = j + 1; cnt = cnt + 1 } else { scan = 0 }
              }
          }
          if cnt < a { return 0 - 1 }           // fewer than min -> no match here
          if b == 1 {
              var c3: i64 = cnt
              while c3 >= a {
                  if fuel[0] <= 0 { return 0 - 1 }
                  fuel[0] = fuel[0] - 1
                  let r3: i64 = re_bt(rx, p + 2, i + c3, depth + 1)
                  if r3 >= 0 { return r3 }
                  c3 = c3 - 1
              }
              return 0 - 1
          }
          var c4: i64 = a
          while c4 <= cnt {
              if fuel[0] <= 0 { return 0 - 1 }
              fuel[0] = fuel[0] - 1
              let r4: i64 = re_bt(rx, p + 2, i + c4, depth + 1)
              if r4 >= 0 { return r4 }
              c4 = c4 + 1
          }
          return 0 - 1
      }
      if op == RE_MARK {                        // stamp loop-entry pos; save-restore discipline (like RE_SAVE)
          let mk: *i64 = rx.marks               // so backtracking into an EARLIER iteration sees ITS stamp.
          let mold: i64 = mk[a]
          mk[a] = i
          let mr: i64 = re_bt(rx, p + 1, i, depth + 1)
          if mr >= 0 { return mr }
          mk[a] = mold
          return 0 - 1
      }
      if op == RE_BACK {                        // ES RepeatMatcher: an EMPTY iteration FAILS (captures restored
          if i > rx.marks[a] { p = b } else { return 0 - 1 }   // via the SAVE/MARK unwind); progress -> loop.
      }
      if op == RE_BREF {                        // a=groupnum; re-match the captured span
          let sv: *i64 = rx.saves
          let gs: i64 = sv[2 * a]
          let ge: i64 = sv[2 * a + 1]
          if gs >= 0 { if ge >= gs {            // group matched -> require the same bytes here
              let glen: i64 = ge - gs
              if i + glen > slen { return 0 - 1 }
              var bi: i64 = 0
              while bi < glen {
                  var c1: i64 = (s[gs + bi]) as i64
                  var c2: i64 = (s[i + bi]) as i64
                  if (rx.flags & RXF_I) != 0 { c1 = rx_lc(c1); c2 = rx_lc(c2) }
                  if c1 != c2 { return 0 - 1 }
                  bi = bi + 1
              }
              i = i + glen
          } }
          p = p + 1                             // unset group (gs<0) -> matches empty (JS semantics)
      }
  }
  return 0 - 1
698}
699
700// ---------- public API ----------
701// compile a pattern (bytes+len) with flag bits -> *Regex (re.ok==0 on parse error/decline).
702func nx_regex_compile(pat: *u8, plen: i64, flags: i64) -> *Regex {
  let p: *RxP = sys_mmap(RXP_BYTES) as *RxP
  p.pat = pat; p.plen = plen; p.pos = 0
  p.nodes = sys_mmap(RX_MAXNODE * 6 * 8) as *i64; p.nn = 0
  p.classes = sys_mmap(RX_MAXCLASS * 8) as *i64; p.nc = 0
  p.ngroup = 0; p.flags = flags; p.err = 0
  let root: i64 = rp_alt(p)
  let re: *Regex = sys_mmap(REGEX_BYTES) as *Regex
  re.classes = p.classes; re.ngroup = p.ngroup; re.flags = flags
  re.nsave = 2 * (p.ngroup + 1)
  if p.err == 1 { re.ok = 0; re.prog = 0 as *i64; re.nprog = 0; return re }
  if p.pos < p.plen { re.ok = 0; re.prog = 0 as *i64; re.nprog = 0; return re }   // trailing junk (e.g. stray ')')
  let prog: *i64 = sys_mmap(RX_MAXPROG * 3 * 8) as *i64
  let npp: *i64 = sys_mmap(16) as *i64; npp[0] = 0; npp[1] = 0   // [1] = MARK-slot counter (one per loop)
  rc_emit(prog, npp, RE_SAVE, 0, 0)          // save[0] = match start
  rc(p.nodes, root, prog, npp)
  rc_emit(prog, npp, RE_SAVE, 1, 0)          // save[1] = match end
  rc_emit(prog, npp, RE_MATCH, 0, 0)
  re.prog = prog; re.nprog = npp[0]; re.ok = 1; re.nmark = npp[1]
  return re
722}
723// leftmost search from `start`. saves (caller-sized re.nsave) filled with [start,end, g1s,g1e, ...]; -1 = unset.
724// returns match-start position (>=0) or -1 (no match). Total work is fuel-bounded => never hangs.
725func nx_regex_exec(re: *Regex, s: *u8, slen: i64, start: i64, saves: *i64) -> i64 {
  if re.ok == 0 { return 0 - 1 }
  let rx: *Rx = sys_mmap(RX_BYTES) as *Rx
  rx.s = s; rx.slen = slen; rx.prog = re.prog; rx.classes = re.classes; rx.flags = re.flags; rx.saves = saves
  let fuel: *i64 = sys_mmap(8) as *i64; fuel[0] = RX_FUEL
  rx.fuel = fuel
  var nmk: i64 = re.nmark
  if nmk < 1 { nmk = 1 }
  let mks: *i64 = sys_mmap(nmk * 8) as *i64   // loop-entry stamps (zero-init; MARK stamps before any BACK reads)
  var mi: i64 = 0
  while mi < nmk { mks[mi] = 0 - 1; mi = mi + 1 }
  rx.marks = mks
  let nsave: i64 = re.nsave
  var i: i64 = start
  while i <= slen {
      var k: i64 = 0
      while k < nsave { saves[k] = 0 - 1; k = k + 1 }
      let r: i64 = re_bt(rx, 0, i, 0)
      if r >= 0 { return saves[0] }
      if fuel[0] <= 0 { return 0 - 1 }
      i = i + 1
  }
  return 0 - 1
748}
749// convenience: 1 if the pattern matches anywhere in s, else 0.
750func nx_regex_test(re: *Regex, s: *u8, slen: i64) -> i64 {
  let saves: *i64 = sys_mmap(re.nsave * 8) as *i64
  if nx_regex_exec(re, s, slen, 0, saves) >= 0 { return 1 }
  return 0
754}
755// parse a JS flags string ("gimsuy") into bits (unknown flags ignored).
756func nx_regex_flags(fs: *u8, flen: i64) -> i64 {
  var f: i64 = 0
  var i: i64 = 0
  while i < flen {
      let c: i64 = (fs[i]) as i64
      if c == 105 { f = f | RXF_I }   // i
      if c == 109 { f = f | RXF_M }   // m
      if c == 115 { f = f | RXF_S }   // s
      if c == 103 { f = f | RXF_G }   // g
      i = i + 1
  }
  return f
768}
nx_rxfull.nx source

`nx_rxfull.nx` source
