`nx_regex_vm.nx` source

↩ module page · 143 lines · 10785 B
1// nx_regex_vm.nx -- FULL regex with ALTERNATION | and GROUPS () via a Thompson NFA, still LINEAR-TIME (epsilon-
2// closure state-set, NO backtracking => ReDoS-immune). Closes the regex gap beyond the atom-NFA (nx_regex_lib).
3// Pipeline: re2post (iterative, paren-stack) -> post2nfa (explicit state graph) -> sim (state-set).
4//   T1 'a|b'  T2 '(ab)+'  T3 'a(b|c)d'  T4 '(a|b)*c'  T5 EXCEED '(a|a)*b' on 24 a's = LINEAR  T6 teeth non-match.
5// expect_exit: 0   Sovereign: nx_syscalls.
6import "nx_syscalls.nx"
7import "nx_itoa_lib.nx"   // shared MSB-first emitter (zero-alloc)
8const K_MAGIC_1024: i64 = 1024
9
10func g_puts(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} sys_write(1,s,n); return 0 }
11// MIGRATED to the shared emitter (debt 1785563586). The old body mmapped a scratch buffer
12// per call and never freed it. At PAGE granularity that is 4096B leaked PER CALL -- the
13// defect that took 28.5GB of a 36GB host in nx_ts_lumadiff (2MB input, ~3.66M calls).
14// nxi_* is MSB-first, allocates NOTHING, and emits identical bytes including the sign.
15func g_pn(v: i64) -> i64 { nxi_out(v); return 0 }
16func ck(name: *u8, c: i64) -> i64 { if c==1 { g_puts("  PASS " as *u8) } else { g_puts("  FAIL " as *u8) } g_puts(name); g_puts("\n" as *u8); return c }
17func cs_set(csbm: *i64, base: i64, ch: i64) -> i64 { csbm[base+(ch>>6)]=csbm[base+(ch>>6)]|(1<<(ch&63)); return 0 }
18func cs_match(csbm: *i64, cls: i64, ch: i64) -> i64 { return (csbm[cls*4+(ch>>6)]>>(ch&63))&1 }
19
20// re2post: infix -> postfix tokens (pop[]=1 CHAR/2 CONCAT/3 ALT/4 STAR/5 PLUS/6 QUES; parg=charset id for CHAR).
21// builds charsets in csbm; *pcsn=#charsets. returns np or -1.
22func re2post(re: *u8, pop: *i64, parg: *i64, csbm: *i64, pcsn: *i64) -> i64 {
  var i: i64=0; var np: i64=0; var csn: i64=0; var nalt: i64=0; var natom: i64=0
  let pna: *i64=sys_mmap(64*8) as *i64; let pnt: *i64=sys_mmap(64*8) as *i64; var sp: i64=0
  while re[i]!=(0 as u8) {
      let c: i64=re[i] as i64
      if c==40 { if natom>1 { natom=natom-1; pop[np]=2; parg[np]=0; np=np+1 } pna[sp]=nalt; pnt[sp]=natom; sp=sp+1; nalt=0; natom=0; i=i+1 }
      else { if c==124 { if natom==0 { return 0-1 } natom=natom-1; while natom>0 { pop[np]=2; parg[np]=0; np=np+1; natom=natom-1 } nalt=nalt+1; i=i+1 }
      else { if c==41 { if sp==0 { return 0-1 } natom=natom-1; while natom>0 { pop[np]=2; parg[np]=0; np=np+1; natom=natom-1 } while nalt>0 { pop[np]=3; parg[np]=0; np=np+1; nalt=nalt-1 } sp=sp-1; nalt=pna[sp]; natom=pnt[sp]; natom=natom+1; i=i+1 }
      else { if c==42 { pop[np]=4; parg[np]=0; np=np+1; i=i+1 }
      else { if c==43 { pop[np]=5; parg[np]=0; np=np+1; i=i+1 }
      else { if c==63 { pop[np]=6; parg[np]=0; np=np+1; i=i+1 }
      else {
          if natom>1 { natom=natom-1; pop[np]=2; parg[np]=0; np=np+1 }
          let cs: i64=csn; csn=csn+1; let base: i64=cs*4; csbm[base]=0; csbm[base+1]=0; csbm[base+2]=0; csbm[base+3]=0
          if c==46 { csbm[base]=0-1; csbm[base+1]=0-1; csbm[base+2]=0-1; csbm[base+3]=0-1; i=i+1 }
          else { if c==91 { i=i+1; var inc: i64=1
              while inc==1 { if re[i]==(0 as u8) { inc=0 } else { if re[i]==(93 as u8) { i=i+1; inc=0 } else {
                  let lo: i64=re[i] as i64; var rg: i64=0
                  if re[i+1]==(45 as u8) { if re[i+2]!=(0 as u8) { if re[i+2]!=(93 as u8) { rg=1 } } }
                  if rg==1 { let hi: i64=re[i+2] as i64; var ch: i64=lo; while ch<=hi { cs_set(csbm,base,ch); ch=ch+1 } i=i+3 } else { cs_set(csbm,base,lo); i=i+1 } } } }
          } else { if c==92 { cs_set(csbm,base,re[i+1] as i64); i=i+2 } else { cs_set(csbm,base,c); i=i+1 } } }
          pop[np]=1; parg[np]=cs; np=np+1; natom=natom+1
      } } } } } }
  }
  natom=natom-1; while natom>0 { pop[np]=2; parg[np]=0; np=np+1; natom=natom-1 }
  while nalt>0 { pop[np]=3; parg[np]=0; np=np+1; nalt=nalt-1 }
  pcsn[0]=csn
  return np
50}
51
52// post2nfa: build explicit state graph. state s: scls[s] (charset or -1), sto[s] (char target), se1[s]/se2[s] (eps, or -1).
53// returns start state; *pmatch = the accept(match) state; *pns = state count.
54func post2nfa(pop: *i64, parg: *i64, np: i64, scls: *i64, sto: *i64, se1: *i64, se2: *i64, pns: *i64, pmatch: *i64) -> i64 {
  var ns: i64=0
  let fst: *i64=sys_mmap(128*8) as *i64; let fac: *i64=sys_mmap(128*8) as *i64; var sp: i64=0
  var k: i64=0
  while k<np {
      let o: i64=pop[k]
      if o==1 { let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
                let s0: i64=ns; scls[s0]=parg[k]; sto[s0]=s1; se1[s0]=0-1; se2[s0]=0-1; ns=ns+1
                fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
      if o==2 { let bS: i64=fst[sp-1]; let bA: i64=fac[sp-1]; let aS: i64=fst[sp-2]; let aA: i64=fac[sp-2]; sp=sp-2
                se1[aA]=bS; fst[sp]=aS; fac[sp]=bA; sp=sp+1 }
      if o==3 { let bS: i64=fst[sp-1]; let bA: i64=fac[sp-1]; let aS: i64=fst[sp-2]; let aA: i64=fac[sp-2]; sp=sp-2
                let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=bS; ns=ns+1
                let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
                se1[aA]=s1; se1[bA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
      if o==4 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
                let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
                let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=s1; ns=ns+1
                se1[aA]=aS; se2[aA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
      if o==5 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
                let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
                se1[aA]=aS; se2[aA]=s1; fst[sp]=aS; fac[sp]=s1; sp=sp+1 }
      if o==6 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
                let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
                let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=s1; ns=ns+1
                se1[aA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
      k=k+1
  }
  pns[0]=ns; pmatch[0]=fac[sp-1]; return fst[sp-1]
83}
84
85// epsilon-closure add (recursive). marks mf[0]=1 if the match state is reachable; adds char-states to clist.
86func addstate(scls: *i64, sto: *i64, se1: *i64, se2: *i64, s: i64, clist: *i64, cnp: *i64, seen: *i64, gen: i64, mst: i64, mf: *i64) -> i64 {
  if seen[s]==gen { return 0 }
  seen[s]=gen
  if s==mst { mf[0]=1; return 0 }
  if scls[s]>=0 { clist[cnp[0]]=s; cnp[0]=cnp[0]+1; return 0 }
  if se1[s]>=0 { addstate(scls,sto,se1,se2,se1[s],clist,cnp,seen,gen,mst,mf) }
  if se2[s]>=0 { addstate(scls,sto,se1,se2,se2[s],clist,cnp,seen,gen,mst,mf) }
  return 0
94}
95func re_vm_match(re: *u8, text: *u8, tn: i64) -> i64 {
  let pop: *i64=sys_mmap(256*8) as *i64; let parg: *i64=sys_mmap(256*8) as *i64; let csbm: *i64=sys_mmap(256*4*8) as *i64; let pcsn: *i64=sys_mmap(8) as *i64
  let np: i64=re2post(re, pop, parg, csbm, pcsn); if np<0 { return 0-1 }
  let scls: *i64=sys_mmap(K_MAGIC_1024*8) as *i64; let sto: *i64=sys_mmap(K_MAGIC_1024*8) as *i64; let se1: *i64=sys_mmap(K_MAGIC_1024*8) as *i64; let se2: *i64=sys_mmap(K_MAGIC_1024*8) as *i64
  let pns: *i64=sys_mmap(8) as *i64; let pmatch: *i64=sys_mmap(8) as *i64
  let start: i64=post2nfa(pop,parg,np,scls,sto,se1,se2,pns,pmatch); let mst: i64=pmatch[0]
  let seen: *i64=sys_mmap((pns[0]+2)*8) as *i64; var z: i64=0; while z<pns[0] { seen[z]=0-1; z=z+1 }
  let cl: *i64=sys_mmap((pns[0]+2)*8) as *i64; let nl: *i64=sys_mmap((pns[0]+2)*8) as *i64
  var gen: i64=1; let cnp: *i64=sys_mmap(8) as *i64; let mf: *i64=sys_mmap(8) as *i64
  cnp[0]=0; mf[0]=0; addstate(scls,sto,se1,se2,start,cl,cnp,seen,gen,mst,mf)
  if mf[0]==1 { return 1 }
  var matched: i64=0; var p: i64=0
  while p<tn {
      let ch: i64=text[p] as i64; gen=gen+1; let nnp: i64=sys_mmap(8) as *i64; nnp[0]=0; mf[0]=0
      var i: i64=0; while i<cnp[0] { let s: i64=cl[i]; if cs_match(csbm,scls[s],ch)==1 { addstate(scls,sto,se1,se2,sto[s],nl,nnp,seen,gen,mst,mf) } i=i+1 }
      addstate(scls,sto,se1,se2,start,nl,nnp,seen,gen,mst,mf)   // unanchored: a match may start here
      var j: i64=0; while j<nnp[0] { cl[j]=nl[j]; j=j+1 } cnp[0]=nnp[0]
      if mf[0]==1 { matched=1 }
      p=p+1
  }
  return matched
116}
117
118func main() -> i64 {
  g_puts("nx_regex_vm (FULL regex |/() via Thompson NFA -- linear-time, ReDoS-immune)\n" as *u8)
  var pass: i64=0; var total: i64=0
  var t1: i64=0; if re_vm_match("a|b" as *u8,"a" as *u8,1)==1 { if re_vm_match("a|b" as *u8,"b" as *u8,1)==1 { if re_vm_match("a|b" as *u8,"c" as *u8,1)==0 { t1=1 } } }
  pass=pass+ck("T1: alternation 'a|b' matches 'a','b', not 'c'" as *u8, t1); total=total+1
  var t2: i64=0; if re_vm_match("(ab)+" as *u8,"ab" as *u8,2)==1 { if re_vm_match("(ab)+" as *u8,"abab" as *u8,4)==1 { if re_vm_match("(ab)+" as *u8,"ba" as *u8,2)==0 { t2=1 } } }
  pass=pass+ck("T2: group+rep '(ab)+' matches 'ab','abab', not 'ba'" as *u8, t2); total=total+1
  var t3: i64=0; if re_vm_match("a(b|c)d" as *u8,"abd" as *u8,3)==1 { if re_vm_match("a(b|c)d" as *u8,"acd" as *u8,3)==1 { if re_vm_match("a(b|c)d" as *u8,"aed" as *u8,3)==0 { t3=1 } } }
  pass=pass+ck("T3: group-alt 'a(b|c)d' matches 'abd','acd', not 'aed'" as *u8, t3); total=total+1
  var t4: i64=0; if re_vm_match("(a|b)*c" as *u8,"ababc" as *u8,5)==1 { if re_vm_match("(a|b)*c" as *u8,"c" as *u8,1)==1 { if re_vm_match("(a|b)*c" as *u8,"abx" as *u8,3)==0 { t4=1 } } }
  pass=pass+ck("T4: '(a|b)*c' matches 'ababc','c'(zero), not 'abx'" as *u8, t4); total=total+1
  let r5: i64=re_vm_match("(a|a)*b" as *u8,"aaaaaaaaaaaaaaaaaaaaaaaa" as *u8,24)
  var t5: i64=0; if r5==0 { t5=1 }
  pass=pass+ck("T5 (EXCEED): ReDoS-classic '(a|a)*b' on 24 a's = no-match in LINEAR time (a backtracker EXPLODES)" as *u8, t5); total=total+1
  var t6: i64=0; if re_vm_match("hello" as *u8,"world" as *u8,5)==0 { t6=1 }
  pass=pass+ck("T6 (teeth): a non-matching pattern returns 0" as *u8, t6); total=total+1
134
  var okall: i64=0; if pass==total { okall=1 }
  g_puts("---- nx_regex_vm: passed "); g_pn(pass); g_puts(" / "); g_pn(total); g_puts(" ----\n" as *u8)
  if okall==1 {
      let logf: i64=sys_openat_append("knowledge/status/regex_vm.log" as *u8, 420)
      if logf>=0 { let z: i64=sys_write(logf,"NXREGEXVM GREEN: full regex |/() via Thompson NFA, linear-time; (a|a)*b ReDoS-classic stays LINEAR\n" as *u8,93); sys_close(logf) }
      g_puts("verdict=GREEN (full regex with alternation |/groups () via Thompson NFA, still linear-time/ReDoS-immune; regex gap CLOSED)\n" as *u8); sys_exit(0); return 0
  }
  g_puts("verdict=RED\n" as *u8); sys_exit(1); return 1
143}
nx_regex_vm.nx source

`nx_regex_vm.nx` source
