nx_regex_unified_gate.nx source

1// nx_regex_unified_gate.nx -- GATE: the UNIFIED linear-time regex engine (nx_regex_vm_lib) is a STRICT SUPERSET of 2// BOTH old engines and drives grep. Proves: (T1) every atom-NFA feature works (literal/./*+?/[]ranges/^/$ anchors); 3// (T2) PLUS alternation | and groups () that the atom-NFA could NOT do; (T3) the UNIFICATION payoff -- anchors COMBINED 4// with alternation/groups (^(cat|dog)$), which NEITHER old engine could express; (T4) ReDoS-immune (linear on the 5// classic blowup); (T5) grep runs on it -- ReDoS-immune, full-regex line grep (beats backtracking grep/PCRE); (T6) 6// malformed pattern fails-loud. This consolidates two engines into one SOTA engine. expect_exit: 0 7import "nx_syscalls.nx" 8import "nx_regex_vm_lib.nx" 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 } 11func g_pn(v: i64) -> i64 { let b: *u8=sys_mmap(28); var x: i64=v; if x<0{b[0]=45;sys_write(1,b,1);x=0-x} if x==0{b[0]=48;sys_write(1,b,1);return 0} var d: i64=0; var y: i64=x; while y>0{d=d+1;y=y/10} var i: i64=d-1; y=x; while i>=0{b[i]=(48+(y%10)) as u8;y=y/10;i=i-1} sys_write(1,b,d); return 0 } 12func 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 } 13func m(pat: *u8, text: *u8, n: i64) -> i64 { return re_vm_run(pat, text, n) } 14 15func main() -> i64 { 16 g_puts("nx_regex_unified_gate (ONE linear-time regex engine: superset of both + anchors + alternation + grep, ReDoS-immune)\n" as *u8) 17 var pass: i64=0; var total: i64=0 18 19 // T1: every ATOM-NFA feature (literal, ., *, +, ?, [a-z] class+range, ^ and $ anchors). 20 var t1: i64=0 21 if m("abc" as *u8,"abc" as *u8,3)==1 { if m("abc" as *u8,"abx" as *u8,3)==0 { 22 if m("a.c" as *u8,"axc" as *u8,3)==1 { if m("ab*c" as *u8,"ac" as *u8,2)==1 { if m("ab+c" as *u8,"ac" as *u8,2)==0 { 23 if m("ab?c" as *u8,"abc" as *u8,3)==1 { if m("[a-z]+" as *u8,"hello" as *u8,5)==1 { if m("[0-9]" as *u8,"a" as *u8,1)==0 { 24 if m("^abc" as *u8,"abc" as *u8,3)==1 { if m("^abc" as *u8,"xabc" as *u8,4)==0 { if m("abc$" as *u8,"abc" as *u8,3)==1 { if m("abc$" as *u8,"abcd" as *u8,4)==0 { t1=1 } } } } } } } } } } } } 25 pass=pass+ck("T1: all atom-NFA features -- literal . * + ? [a-z] ranges + ^ $ anchors -- work on the unified engine" as *u8, t1); total=total+1 26 27 // T2: alternation | and groups () -- which the atom-NFA CANNOT do. 28 var t2: i64=0 29 if m("cat|dog" as *u8,"cat" as *u8,3)==1 { if m("cat|dog" as *u8,"dog" as *u8,3)==1 { if m("cat|dog" as *u8,"cow" as *u8,3)==0 { 30 if m("(ab)+" as *u8,"abab" as *u8,4)==1 { if m("a(b|c)d" as *u8,"abd" as *u8,3)==1 { if m("a(b|c)d" as *u8,"aed" as *u8,3)==0 { t2=1 } } } } } } 31 pass=pass+ck("T2: PLUS alternation | and groups () -- capabilities the atom-NFA engine never had" as *u8, t2); total=total+1 32 33 // T3: THE UNIFICATION PAYOFF -- anchors COMBINED with alternation/groups. Neither old engine could express this. 34 var t3: i64=0 35 if m("^(cat|dog)$" as *u8,"cat" as *u8,3)==1 { if m("^(cat|dog)$" as *u8,"dog" as *u8,3)==1 { 36 if m("^(cat|dog)$" as *u8,"cats" as *u8,4)==0 { if m("^(cat|dog)$" as *u8,"scat" as *u8,4)==0 { t3=1 } } } } 37 g_puts(" T3 '^(cat|dog)$': cat="); g_pn(m("^(cat|dog)$" as *u8,"cat" as *u8,3)); g_puts(" cats="); g_pn(m("^(cat|dog)$" as *u8,"cats" as *u8,4)); g_puts(" (anchors+alternation, neither old engine could do this)\n" as *u8) 38 pass=pass+ck("T3 (unification payoff): ^(cat|dog)$ -- anchors + alternation together, expressible by NEITHER old engine" as *u8, t3); total=total+1 39 40 // T4: ReDoS-immune -- the classic '(a|a)*b$' on many a's (no b) stays LINEAR (a backtracker explodes). 41 let r4: i64 = m("(a|a)*b$" as *u8,"aaaaaaaaaaaaaaaaaaaaaaaaaa" as *u8,26) 42 var t4: i64=0; if r4==0 { t4=1 } 43 pass=pass+ck("T4 (ReDoS): '(a|a)*b$' on 26 a's = linear-time no-match (backtracking regex would blow up exponentially)" as *u8, t4); total=total+1 44 45 // T5: GREP runs on the unified engine -- ReDoS-immune, full-regex line grep. A 4-line log: 46 let log: *u8 = "ERROR disk fail\nwarn mem low\nERROR net down\ninfo all ok\n" as *u8 47 let nlog: i64 = 55 48 let nStart: i64 = re_vm_grep_count(log, nlog, "^ERROR" as *u8) // lines STARTING with ERROR -> 2 49 let nAlt: i64 = re_vm_grep_count(log, nlog, "warn|ERROR" as *u8) // lines with warn OR ERROR -> 3 50 let nNone: i64 = re_vm_grep_count(log, nlog, "^debug" as *u8) // none 51 g_puts(" T5 grep: '^ERROR'="); g_pn(nStart); g_puts(" 'warn|ERROR'="); g_pn(nAlt); g_puts(" '^debug'="); g_pn(nNone); g_puts(" (expect 2, 3, 0)\n" as *u8) 52 var t5: i64=0; if nStart==2 { if nAlt==3 { if nNone==0 { t5=1 } } } 53 pass=pass+ck("T5: sovereign grep on the unified engine -- anchored + alternation regex over lines (ReDoS-immune)" as *u8, t5); total=total+1 54 55 // T6 (teeth): a malformed pattern (unbalanced paren) fails-loud (-1), never crashes/miscompiles. 56 let r6: i64 = m("(ab" as *u8,"ab" as *u8,2) 57 var t6: i64=0; if r6==(0-1) { t6=1 } 58 g_puts(" T6 malformed '(ab' rc="); g_pn(r6); g_puts(" (-1 = fail-loud)\n" as *u8) 59 pass=pass+ck("T6 (teeth): a malformed pattern (unbalanced paren) fails-loud (-1), never a crash or miscompile" as *u8, t6); total=total+1 60 61 var okall: i64=0; if pass==total { okall=1 } 62 g_puts("---- nx_regex_unified_gate: passed "); g_pn(pass); g_puts(" / "); g_pn(total); g_puts(" ----\n" as *u8) 63 if okall==1 { 64 let logf: i64=sys_openat_append("knowledge/status/regex_unified.log" as *u8, 420) 65 if logf>=0 { let z: i64=sys_write(logf,"NXREGEXUNIFIED GREEN: ONE linear-time regex engine (nx_regex_vm_lib) -- strict superset of both old engines (literals/./*+?/[]/ranges + | + () + ^ $ anchors), ReDoS-immune, drives sovereign grep; ^(cat|dog)$ expressible by neither old engine\n" as *u8,240); sys_close(logf) } 66 g_puts("verdict=GREEN (two regex engines UNIFIED into one linear-time ReDoS-immune superset -- anchors + alternation + groups + classes, driving grep; the REGEX consolidation gap closed)\n" as *u8); sys_exit(0); return 0 67 } 68 g_puts("verdict=RED\n" as *u8); sys_exit(1); return 1 69}