code wiki / _hdl_build / nx_regex_vm_lib.nx
nx_regex_vm_lib.nx source
↩ module page · 128 lines · 9222 B
1// nx_regex_vm_lib.nx -- the UNIFIED sovereign regex engine (linear-time Thompson NFA, ReDoS-immune) as a pure LIBRARY.
2// STRICT SUPERSET of the old atom-NFA (nx_regex_lib): literal / '.' / '*' '+' '?' / '[..]' classes+ranges / '\' escape
3// + ALTERNATION '|' + GROUPS '()' + '^' '$' ANCHORS (line-anchor semantics, as grep uses). No backtracking => ReDoS-
4// IMMUNE (the RE2/Go design). This is the ONE regex engine for the OS; grep (re_vm_grep_count) runs on it. No main.
5import "nx_syscalls.nx"
6const K_MAGIC_1024: i64 = 1024
7
8func rv_slen(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} return n }
9func cs_set(csbm: *i64, base: i64, ch: i64) -> i64 { csbm[base+(ch>>6)]=csbm[base+(ch>>6)]|(1<<(ch&63)); return 0 }
10func cs_match(csbm: *i64, cls: i64, ch: i64) -> i64 { return (csbm[cls*4+(ch>>6)]>>(ch&63))&1 }
11
12// re2post: infix -> postfix (pop[]=1 CHAR/2 CONCAT/3 ALT/4 STAR/5 PLUS/6 QUES; parg=charset id). *pcsn=#charsets.
13func re2post(re: *u8, pop: *i64, parg: *i64, csbm: *i64, pcsn: *i64) -> i64 {
14 var i: i64=0; var np: i64=0; var csn: i64=0; var nalt: i64=0; var natom: i64=0
15 let pna: *i64=sys_mmap(64*8) as *i64; let pnt: *i64=sys_mmap(64*8) as *i64; var sp: i64=0
16 while re[i]!=(0 as u8) {
17 let c: i64=re[i] as i64
18 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 }
19 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 }
20 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 }
21 else { if c==42 { pop[np]=4; parg[np]=0; np=np+1; i=i+1 }
22 else { if c==43 { pop[np]=5; parg[np]=0; np=np+1; i=i+1 }
23 else { if c==63 { pop[np]=6; parg[np]=0; np=np+1; i=i+1 }
24 else {
25 if natom>1 { natom=natom-1; pop[np]=2; parg[np]=0; np=np+1 }
26 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
27 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 }
28 else { if c==91 { i=i+1; var inc: i64=1
29 while inc==1 { if re[i]==(0 as u8) { inc=0 } else { if re[i]==(93 as u8) { i=i+1; inc=0 } else {
30 let lo: i64=re[i] as i64; var rg: i64=0
31 if re[i+1]==(45 as u8) { if re[i+2]!=(0 as u8) { if re[i+2]!=(93 as u8) { rg=1 } } }
32 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 } } } }
33 } 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 } } }
34 pop[np]=1; parg[np]=cs; np=np+1; natom=natom+1
35 } } } } } }
36 }
37 natom=natom-1; while natom>0 { pop[np]=2; parg[np]=0; np=np+1; natom=natom-1 }
38 while nalt>0 { pop[np]=3; parg[np]=0; np=np+1; nalt=nalt-1 }
39 if sp!=0 { return 0-1 } // unclosed '(' -> malformed (fail-loud, don't feed post2nfa a bad stack)
40 pcsn[0]=csn
41 return np
42}
43// post2nfa: build the explicit NFA state graph. returns start; *pmatch=accept state; *pns=state count.
44func post2nfa(pop: *i64, parg: *i64, np: i64, scls: *i64, sto: *i64, se1: *i64, se2: *i64, pns: *i64, pmatch: *i64) -> i64 {
45 var ns: i64=0
46 let fst: *i64=sys_mmap(128*8) as *i64; let fac: *i64=sys_mmap(128*8) as *i64; var sp: i64=0
47 var k: i64=0
48 while k<np {
49 let o: i64=pop[k]
50 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
51 let s0: i64=ns; scls[s0]=parg[k]; sto[s0]=s1; se1[s0]=0-1; se2[s0]=0-1; ns=ns+1
52 fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
53 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
54 se1[aA]=bS; fst[sp]=aS; fac[sp]=bA; sp=sp+1 }
55 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
56 let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=bS; ns=ns+1
57 let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
58 se1[aA]=s1; se1[bA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
59 if o==4 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
60 let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
61 let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=s1; ns=ns+1
62 se1[aA]=aS; se2[aA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
63 if o==5 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
64 let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
65 se1[aA]=aS; se2[aA]=s1; fst[sp]=aS; fac[sp]=s1; sp=sp+1 }
66 if o==6 { let aS: i64=fst[sp-1]; let aA: i64=fac[sp-1]; sp=sp-1
67 let s1: i64=ns; scls[s1]=0-1; sto[s1]=0-1; se1[s1]=0-1; se2[s1]=0-1; ns=ns+1
68 let s0: i64=ns; scls[s0]=0-1; sto[s0]=0-1; se1[s0]=aS; se2[s0]=s1; ns=ns+1
69 se1[aA]=s1; fst[sp]=s0; fac[sp]=s1; sp=sp+1 }
70 k=k+1
71 }
72 pns[0]=ns; pmatch[0]=fac[sp-1]; return fst[sp-1]
73}
74func addstate(scls: *i64, sto: *i64, se1: *i64, se2: *i64, s: i64, clist: *i64, cnp: *i64, seen: *i64, gen: i64, mst: i64, mf: *i64) -> i64 {
75 if seen[s]==gen { return 0 }
76 seen[s]=gen
77 if s==mst { mf[0]=1; return 0 }
78 if scls[s]>=0 { clist[cnp[0]]=s; cnp[0]=cnp[0]+1; return 0 }
79 if se1[s]>=0 { addstate(scls,sto,se1,se2,se1[s],clist,cnp,seen,gen,mst,mf) }
80 if se2[s]>=0 { addstate(scls,sto,se1,se2,se2[s],clist,cnp,seen,gen,mst,mf) }
81 return 0
82}
83
84// UNIFIED match: strips leading '^' (anchored start) + trailing '$' (anchored end), runs the linear-time state-set
85// sim with anchor semantics. returns 1/0, or -1 on a malformed pattern.
86func re_vm_run(re: *u8, text: *u8, tn: i64) -> i64 {
87 let rlen: i64 = rv_slen(re)
88 var astart: i64=0; var aend: i64=0; var ri: i64=0; var rend: i64=rlen
89 if rlen>0 { if re[0]==(94 as u8) { astart=1; ri=1 } } // ^
90 if rend>ri { if re[rend-1]==(36 as u8) { aend=1; rend=rend-1 } } // trailing $
91 let clean: *u8=sys_mmap(rlen+2); var ci: i64=0
92 while ri<rend { clean[ci]=re[ri]; ci=ci+1; ri=ri+1 } clean[ci]=0 as u8
93 if ci==0 { // pattern was only anchors / empty
94 if astart==1 { if aend==1 { if tn==0 { return 1 } return 0 } } // ^$ = empty line only
95 return 1 // ^, $, or "" = matches (empty match exists)
96 }
97 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
98 let np: i64=re2post(clean, pop, parg, csbm, pcsn); if np<0 { return 0-1 }
99 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
100 let pns: *i64=sys_mmap(8) as *i64; let pmatch: *i64=sys_mmap(8) as *i64
101 let start: i64=post2nfa(pop,parg,np,scls,sto,se1,se2,pns,pmatch); let mst: i64=pmatch[0]
102 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 }
103 let cl: *i64=sys_mmap((pns[0]+2)*8) as *i64; let nl: *i64=sys_mmap((pns[0]+2)*8) as *i64
104 var gen: i64=1; let cnp: *i64=sys_mmap(8) as *i64; let mf: *i64=sys_mmap(8) as *i64; let nnp: *i64=sys_mmap(8) as *i64
105 cnp[0]=0; mf[0]=0; addstate(scls,sto,se1,se2,start,cl,cnp,seen,gen,mst,mf)
106 if mf[0]==1 { if aend==0 { return 1 } if tn==0 { return 1 } } // empty match (respect $)
107 var matched: i64=0; var p: i64=0
108 while p<tn {
109 let ch: i64=text[p] as i64; gen=gen+1; nnp[0]=0; mf[0]=0
110 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 }
111 if astart==0 { addstate(scls,sto,se1,se2,start,nl,nnp,seen,gen,mst,mf) } // unanchored: re-seed each pos
112 var j: i64=0; while j<nnp[0] { cl[j]=nl[j]; j=j+1 } cnp[0]=nnp[0]
113 if mf[0]==1 { if aend==0 { matched=1 } else { if p==tn-1 { matched=1 } } } // $ => must reach match at the end
114 p=p+1
115 }
116 return matched
117}
118
119// SOVEREIGN grep: count lines in buf[0..nbuf) that match the regex `pat` (ReDoS-immune, full-regex). the OS grep matcher.
120func re_vm_grep_count(buf: *u8, nbuf: i64, pat: *u8) -> i64 {
121 var count: i64=0; var start: i64=0; var i: i64=0
122 while i<=nbuf {
123 if i==nbuf { if i>start { if re_vm_run(pat, buf+start, i-start)==1 { count=count+1 } } i=i+1 }
124 else { if buf[i]==(10 as u8) { if re_vm_run(pat, buf+start, i-start)==1 { count=count+1 } start=i+1 } i=i+1 }
125 }
126 return count
127}
128func regex_vm_lib_main() -> i64 { return 0 }