nx_stem_bound_gate.nx source

1// nx_stem_bound_gate.nx -- THE STEM RUN BOUND, PROVEN OVER EVERY TERM OF THE LIVE DICTIONARY (search prep cut, 2026-09-14). 2// 3// WHY. dss_stem_expand (nx_docportal_search_seg.nx) finds every dictionary term whose stem equals the query 4// term's stem by walking the sorted run of terms sharing the stem's first 3 bytes and stemming each one. The 5// phase timers in /api/search named that walk as 0.33-0.40 s of every cold query, CPU in nx_stem per run entry 6// (a prefetch pass over the same run measured no gain). Widening the run key from 3 bytes to qsn-1 bytes makes 7// the walk a SUBSET of the old run, and it is exact ONLY IF: for every dictionary term w, w and stem(w) share 8// at least len(stem(w))-1 leading bytes. Porter rewrites suffixes only, and the rewrites that can change a byte 9// inside the stem's span (y to i, biliti to ble) touch at most its LAST byte -- but that is an argument about 10// the textbook, and the estate's stemmer is nx_stem. So this gate does not argue: it walks EVERY term of EVERY 11// live segment (no sample), stems each with the same nx_stem the scorer calls, and counts the terms that violate 12// the bound. One violation is RED and the cut does not ship; the violators are printed as the worklist. 13// 14// The predicate is a pure function so KAT and neg-control teeth pin its arithmetic before the census runs. The 15// shard path probes the manifest to survive the buildroot cwd anchor (nx_livemap_fast_gate's lesson); argv[1] 16// overrides the prefix. license_tier: ORIGINAL No hw writes (Rule 26). 17import "nx_seg_store.nx" 18import "nx_stem.nx" 19import "nx_gate_verdict.nx" 20 21const SB_TOKBUF: i64 = 4096 22const SB_MAXTERM: i64 = 40 // the expansion walk stems only terms shorter than this (dss_stem_expand) 23const SB_NARROW: i64 = 5 // stems of this length or more get a wider key than the old 3 bytes 24const SB_SHOW: i64 = 12 // violators printed; the COUNT is always the whole population 25 26// 1 iff term[0..tl) and stem[0..sl) agree on their first sl-1 bytes and the term is long enough to hold them. 27func sb_shares(term: *u8, tl: i64, stem: *u8, sl: i64) -> i64 { 28 if sl <= 1 { return 1 } 29 let need: i64 = sl - 1 30 if tl < need { return 0 } 31 var k: i64 = 0 32 while k < need { 33 if (term[k] as i64) != (stem[k] as i64) { return 0 } 34 k = k + 1 35 } 36 return 1 37} 38 39func main(argc: i64, argv: *i64) -> i64 { 40 let ctr: *i64 = gv_ctr() 41 gv_head("nx_stem_bound_gate -- every live dictionary term shares its stem's first len(stem)-1 bytes, the run bound the prep cut stands on" as *u8) 42 43 // the predicate, pinned on known pairs before it judges millions 44 gv_check("T1 KAT happy shares 4 of stem happi (y to i differs only in the last byte)" as *u8, sb_shares("happy" as *u8, 5, "happi" as *u8, 5), ctr) 45 gv_check("T1b KAT sensibility shares 6 of stem sensibl (biliti to ble differs only in the last byte)" as *u8, sb_shares("sensibility" as *u8, 11, "sensibl" as *u8, 7), ctr) 46 gv_check("T1c KAT sky shares 2 of stem ski (the short class the old 3-byte key already treats this way)" as *u8, sb_shares("sky" as *u8, 3, "ski" as *u8, 3), ctr) 47 gv_check("T1d KAT hopping shares all of stem hop (a stem shorter than the term)" as *u8, sb_shares("hopping" as *u8, 7, "hop" as *u8, 3), ctr) 48 gv_check("T1e KAT a stem of one byte binds nothing" as *u8, sb_shares("a" as *u8, 1, "x" as *u8, 1), ctr) 49 gv_check("T1f neg-control-abc-against-xyz is a violation" as *u8, (sb_shares("abc" as *u8, 3, "xyz" as *u8, 3) == 0) as i64, ctr) 50 gv_check("T1g neg-control-term-shorter-than-the-bound is a violation (ab against abcd)" as *u8, (sb_shares("ab" as *u8, 2, "abcd" as *u8, 4) == 0) as i64, ctr) 51 gv_check("T1h neg-control-mismatch-inside-the-bound is a violation (photograph against phonograph)" as *u8, (sb_shares("photograph" as *u8, 10, "phonograph" as *u8, 10) == 0) as i64, ctr) 52 gv_check("T1i a difference exactly at the stem's last byte is tolerated (abcde against abcdX)" as *u8, sb_shares("abcde" as *u8, 5, "abcdX" as *u8, 5), ctr) 53 54 // the live shard, from either cwd 55 var prefix: *u8 = "knowledge/store/dp-web-pub-" as *u8 56 let anch: i64 = sys_openat_rd("../knowledge/store/dp-web-pub-manifest.txt" as *u8) 57 if anch >= 0 { sys_close(anch); prefix = "../knowledge/store/dp-web-pub-" as *u8 } 58 if argc >= 2 { prefix = argv[1] as *u8 } 59 gv_puts(" shard prefix=" as *u8); gv_puts(prefix); gv_puts("\n" as *u8) 60 let h: *i64 = ss_open2(prefix, 1) 61 var t2: i64 = 0 62 if (h as i64) != 0 { t2 = 1 } 63 gv_check("T2 the shard opens (nothing below means anything if it does not)" as *u8, t2, ctr) 64 if t2 == 0 { 65 let rcx: i64 = gv_verdict("STEMBOUND" as *u8, ctr, "the run bound over the live dictionary" as *u8) 66 sys_exit(rcx) 67 return rcx 68 } 69 let ns: i64 = h[0] 70 gv_check("T3 the shard has MULTIPLE segments so every dictionary generation is covered" as *u8, (ns > 1) as i64, ctr) 71 72 let stemc: *u8 = sys_mmap(SB_TOKBUF) 73 let cbuf: *u8 = sys_mmap(SB_TOKBUF) 74 let tpb: *i64 = sys_mmap(64) as *i64 75 let tlb: *i64 = sys_mmap(64) as *i64 76 let dcb: *i64 = sys_mmap(64) as *i64 77 var total: i64 = 0 78 var checked: i64 = 0 79 var skipped: i64 = 0 80 var viol: i64 = 0 81 var narrowed: i64 = 0 82 var maxtl: i64 = 0 83 var maxsl: i64 = 0 84 var longer: i64 = 0 85 var shown: i64 = 0 86 var s: i64 = 0 87 while s < ns { 88 let tc: i64 = ss_term_count(h, s) 89 total = total + tc 90 var e: i64 = 0 91 while e < tc { 92 if ss_term_at(h, s, e, tpb, tlb, dcb) == 1 { 93 let tl: i64 = tlb[0] 94 if tl > maxtl { maxtl = tl } 95 if tl < SB_MAXTERM { 96 let dtp: *u8 = tpb[0] as *u8 97 var ci: i64 = 0 98 while ci < tl { cbuf[ci] = dtp[ci]; ci = ci + 1 } 99 cbuf[tl] = 0 as u8 100 let csn: i64 = nx_stem(cbuf, tl, stemc) 101 checked = checked + 1 102 if csn > maxsl { maxsl = csn } 103 if csn > tl { longer = longer + 1 } 104 if csn >= SB_NARROW { narrowed = narrowed + 1 } 105 if sb_shares(cbuf, tl, stemc, csn) == 0 { 106 viol = viol + 1 107 if shown < SB_SHOW { 108 shown = shown + 1 109 gv_puts(" VIOLATION seg=" as *u8); gv_num(s); gv_puts(" term=" as *u8); sys_write(1, cbuf, tl) 110 gv_puts(" stem=" as *u8); sys_write(1, stemc, csn); gv_puts("\n" as *u8) 111 } 112 } 113 } else { skipped = skipped + 1 } 114 } 115 e = e + 1 116 } 117 s = s + 1 118 } 119 gv_kv("segments" as *u8, ns) 120 gv_kv("terms_total" as *u8, total) 121 gv_kv("terms_checked" as *u8, checked) 122 gv_kv("terms_skipped_long" as *u8, skipped) 123 gv_kv("terms_narrowed_class" as *u8, narrowed) 124 gv_kv("stem_longer_than_term" as *u8, longer) 125 gv_kv("violations" as *u8, viol) 126 gv_kv("max_term_len" as *u8, maxtl) 127 gv_kv("max_stem_len" as *u8, maxsl) 128 gv_check("T4 fixture-reached-condition: at least one dictionary term was stemmed" as *u8, (checked > 0) as i64, ctr) 129 gv_check("T5 partition: checked plus skipped-long equals the dictionary total" as *u8, (checked + skipped == total) as i64, ctr) 130 gv_check("T6 the narrowed class is populated (stems of 5 or more bytes exist, so the wider key is exercised)" as *u8, (narrowed > 0) as i64, ctr) 131 gv_check("T7 nx_stem never returns a stem longer than its term" as *u8, (longer == 0) as i64, ctr) 132 gv_check("T8 THE BOUND: zero live terms violate share-first-len(stem)-minus-1-bytes" as *u8, (viol == 0) as i64, ctr) 133 let rc: i64 = gv_verdict("STEMBOUND" as *u8, ctr, "the run bound holds over the whole live dictionary" as *u8) 134 sys_exit(rc) 135 return rc 136}