nx_regex_lib.nx source
↩ module page · 91 lines · 4507 B
1// nx_regex_lib.nx -- GENERAL SOVEREIGN REGEX CAPABILITY (shared library). Linear-time NFA matcher (state-set, no
2// backtracking => ReDoS-IMMUNE, the RE2/Go design). Pure library: no main, no UI. Imports only nx_syscalls.
3// Subset: literal, '.', '*' '+' '?', '[..]' classes (a-z ranges), '^' '$' anchors. (alternation |/groups () = TODO.)
4// re_parse(pat,bm,q,fl)->natom re_match(text,tn,bm,q,na,fl,steps)->0/1 re_search(pat,text,tn)->0/1 re_run(pat,text,steps)->0/1
5import "nx_syscalls.nx"
6
7func re_slen(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} return n }
8func re_setbit(bm: *i64, base: i64, ch: i64) -> i64 { let w: i64=base+(ch>>6); bm[w]=bm[w]|(1<<(ch&63)); return 0 }
9func re_getbit(bm: *i64, base: i64, ch: i64) -> i64 { return (bm[base+(ch>>6)]>>(ch&63))&1 }
10
11// parse `pat` into atoms: bm = 256-bit char-set per atom (atom*4 i64), q = quantifier (0 one,1 ?,2 *,3 +),
12// fl[0]=anchored-start(^), fl[1]=anchored-end($). returns natom.
13func re_parse(pat: *u8, bm: *i64, q: *i64, fl: *i64) -> i64 {
14 var i: i64=0; var na: i64=0; fl[0]=0; fl[1]=0
15 if pat[0]==(94 as u8) { fl[0]=1; i=1 }
16 while pat[i]!=(0 as u8) {
17 let c: i64 = pat[i] as i64
18 var isatom: i64=1
19 if c==36 { if pat[i+1]==(0 as u8) { fl[1]=1; i=i+1; isatom=0 } }
20 if isatom==1 {
21 let base: i64 = na*4
22 bm[base]=0; bm[base+1]=0; bm[base+2]=0; bm[base+3]=0
23 if c==46 { bm[base]=0-1; bm[base+1]=0-1; bm[base+2]=0-1; bm[base+3]=0-1; i=i+1 }
24 else { if c==91 {
25 i=i+1; var inclass: i64=1
26 while inclass==1 {
27 if pat[i]==(0 as u8) { inclass=0 }
28 else { if pat[i]==(93 as u8) { i=i+1; inclass=0 }
29 else {
30 let lo: i64=pat[i] as i64
31 var ranged: i64=0
32 if pat[i+1]==(45 as u8) { if pat[i+2]!=(0 as u8) { if pat[i+2]!=(93 as u8) { ranged=1 } } }
33 if ranged==1 { let hi: i64=pat[i+2] as i64; var ch: i64=lo; while ch<=hi { re_setbit(bm,base,ch); ch=ch+1 } i=i+3 }
34 else { re_setbit(bm,base,lo); i=i+1 }
35 } }
36 }
37 }
38 else { if c==92 { let nc: i64=pat[i+1] as i64; re_setbit(bm,base,nc); i=i+2 }
39 else { re_setbit(bm,base,c); i=i+1 } } }
40 var qq: i64=0
41 let nx: i64 = pat[i] as i64
42 if nx==42 { qq=2; i=i+1 }
43 if nx==43 { qq=3; i=i+1 }
44 if nx==63 { qq=1; i=i+1 }
45 q[na]=qq; na=na+1
46 }
47 }
48 return na
49}
50
51func re_close(set: *i64, q: *i64, na: i64) -> i64 {
52 var changed: i64=1
53 while changed==1 {
54 changed=0; var j: i64=0
55 while j<na { if set[j]==1 { var opt: i64=0; if q[j]==1 { opt=1 } if q[j]==2 { opt=1 } if opt==1 { if set[j+1]==0 { set[j+1]=1; changed=1 } } } j=j+1 }
56 }
57 return 0
58}
59
60func re_match(text: *u8, tn: i64, bm: *i64, q: *i64, na: i64, fl: *i64, steps: *i64) -> i64 {
61 let cur: *i64 = sys_mmap((na+2)*8) as *i64; let nxt: *i64 = sys_mmap((na+2)*8) as *i64
62 var z: i64=0; while z<=na { cur[z]=0; z=z+1 }
63 cur[0]=1; re_close(cur,q,na)
64 if cur[na]==1 { if fl[1]==0 { return 1 } if tn==0 { return 1 } }
65 var p: i64=0
66 while p<tn {
67 let ch: i64 = text[p] as i64
68 z=0; while z<=na { nxt[z]=0; z=z+1 }
69 var j: i64=0
70 while j<na { steps[0]=steps[0]+1; if cur[j]==1 { if re_getbit(bm,j*4,ch)==1 { nxt[j+1]=1; if q[j]>=2 { nxt[j]=1 } } } j=j+1 }
71 z=0; while z<=na { cur[z]=nxt[z]; z=z+1 }
72 if fl[0]==0 { cur[0]=1 }
73 re_close(cur,q,na)
74 if cur[na]==1 { if fl[1]==0 { return 1 } if p==tn-1 { return 1 } }
75 p=p+1
76 }
77 return 0
78}
79
80// search a buffer text[0..tn) for a match of `pat`. (parses pat each call -- fine for one-shot; for per-line loops
81// callers can re_parse once then re_match per line.)
82func re_search(pat: *u8, text: *u8, tn: i64) -> i64 {
83 let bm: *i64 = sys_mmap(256*4*8) as *i64; let q: *i64 = sys_mmap(256*8) as *i64; let fl: *i64 = sys_mmap(2*8) as *i64; let sd: *i64 = sys_mmap(8)
84 let na: i64 = re_parse(pat, bm, q, fl)
85 return re_match(text, tn, bm, q, na, fl, sd)
86}
87func re_run(pat: *u8, text: *u8, steps: *i64) -> i64 {
88 let bm: *i64 = sys_mmap(256*4*8) as *i64; let q: *i64 = sys_mmap(256*8) as *i64; let fl: *i64 = sys_mmap(2*8) as *i64
89 let na: i64 = re_parse(pat, bm, q, fl)
90 return re_match(text, re_slen(text), bm, q, na, fl, steps)
91}