nx_regex.nx source

1// nx_regex.nx -- SOVEREIGN linear-time regex GATE, now on the GENERAL nx_regex_lib (rule 15). Linear NFA state-set, 2// NO backtracking => ReDoS-IMMUNE (the RE2/Go design). Subset: literal/./*/+/?/[..]/^/$. (|/() = follow-on.) 3// T1-T6 correctness. T7 EXCEED: ReDoS-pathological match runs in LINEAR steps (measured). T8 teeth: non-match=0. 4// expect_exit: 0 Sovereign: nx_regex_lib (+ nx_syscalls). 5import "nx_regex_lib.nx" 6import "nx_itoa_lib.nx" // shared MSB-first emitter (zero-alloc) 7import "nx_syscalls.nx" 8const K_MAGIC_2000: i64 = 2000 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 } 17 18func main() -> i64 { 19 g_puts("nx_regex (SOVEREIGN linear-time NFA regex on nx_regex_lib -- no backtracking => ReDoS-immune; s-class exceed)\n" as *u8) 20 var pass: i64=0; var total: i64=0 21 let sd: *i64 = sys_mmap(8) 22 sd[0]=0; var t1: i64=0; if re_run("abc" as *u8,"xxabcyy" as *u8,sd)==1 { if re_run("abc" as *u8,"abx" as *u8,sd)==0 { t1=1 } } 23 pass=pass+ck("T1: literals -- 'abc' matches 'xxabcyy', not 'abx'" as *u8, t1); total=total+1 24 var t2: i64=0; if re_run("a*b" as *u8,"aaab" as *u8,sd)==1 { if re_run("a*b" as *u8,"b" as *u8,sd)==1 { if re_run("a*b" as *u8,"aaa" as *u8,sd)==0 { t2=1 } } } 25 pass=pass+ck("T2: star -- 'a*b' matches 'aaab' and 'b' (zero a), not 'aaa'" as *u8, t2); total=total+1 26 var t3: i64=0; if re_run("a.c" as *u8,"axc" as *u8,sd)==1 { if re_run("a.c" as *u8,"ac" as *u8,sd)==0 { t3=1 } } 27 pass=pass+ck("T3: dot -- 'a.c' matches 'axc', not 'ac'" as *u8, t3); total=total+1 28 var t4: i64=0; if re_run("[0-9]+" as *u8,"x42y" as *u8,sd)==1 { if re_run("[0-9]+" as *u8,"xy" as *u8,sd)==0 { t4=1 } } 29 pass=pass+ck("T4: class -- '[0-9]+' matches 'x42y', not 'xy'" as *u8, t4); total=total+1 30 var t5: i64=0; if re_run("^ab" as *u8,"abc" as *u8,sd)==1 { if re_run("^ab" as *u8,"xab" as *u8,sd)==0 { t5=1 } } 31 pass=pass+ck("T5: anchor ^ -- '^ab' matches 'abc', not 'xab'" as *u8, t5); total=total+1 32 var t6: i64=0; if re_run("ab$" as *u8,"xab" as *u8,sd)==1 { if re_run("ab$" as *u8,"abx" as *u8,sd)==0 { t6=1 } } 33 pass=pass+ck("T6: anchor $ -- 'ab$' matches 'xab', not 'abx'" as *u8, t6); total=total+1 34 sd[0]=0 35 let m: i64 = re_run("a*a*a*a*a*a*a*a*c" as *u8, "aaaaaaaaaaaaaaaaaaaaaaaa" as *u8, sd) 36 g_puts(" T7 ReDoS pattern on 24 a's: match="); g_pn(m); g_puts(" steps="); g_pn(sd[0]); g_puts(" (LINEAR; a backtracker is EXPONENTIAL)\n" as *u8) 37 var t7: i64=0; if m==0 { if sd[0]<K_MAGIC_2000 { t7=1 } } 38 pass=pass+ck("T7 (EXCEED): ReDoS-pathological match ran in LINEAR steps (no catastrophic backtracking)" as *u8, t7); total=total+1 39 sd[0]=0; var t8: i64=0; if re_run("hello" as *u8,"world" as *u8,sd)==0 { t8=1 } 40 pass=pass+ck("T8 (teeth): a non-matching pattern returns 0" as *u8, t8); total=total+1 41 42 var okall: i64=0; if pass==total { okall=1 } 43 g_puts("---- nx_regex: passed "); g_pn(pass); g_puts(" / "); g_pn(total); g_puts(" ----\n" as *u8) 44 if okall==1 { 45 let logf: i64=sys_openat_append("knowledge/status/regex.log" as *u8, 420) 46 if logf>=0 { let z: i64=sys_write(logf,"NXREGEX on nx_regex_lib GREEN: literals/star/dot/class/anchors + ReDoS-pathological LINEAR (no backtracking)\n" as *u8,103); sys_close(logf) } 47 g_puts("verdict=GREEN (sovereign linear-time NFA regex on nx_regex_lib: correct + ReDoS-IMMUNE = s-class exceed)\n" as *u8); sys_exit(0); return 0 48 } 49 g_puts("verdict=RED\n" as *u8); sys_exit(1); return 1 50}