nx_editdist.nx source
↩ module page · 64 lines · 3537 B
1// nx_editdist.nx -- INTEGER bounded Levenshtein for the typo/did-you-mean rung. Classic two-row DP over
2// byte strings (our index terms are lowercased alnum runs <= 32 bytes, so bytes == characters here).
3// ed_bounded returns the edit distance, or bound+1 the moment it can prove distance > bound (early-out:
4// the length gap alone decides most rejects at O(1)). No floats, no allocation beyond two 40-cell rows.
5// license_tier: ORIGINAL
6import "nx_syscalls.nx"
7
8// TWO FIXED SCRATCH ROWS, HOISTED TO LAZY STATICS 2026-08-15 (was TWO sys_mmap PER CALL, neither freed).
9// WHY IT MATTERS HERE: the caller that dominates is dss_correct's did-you-mean walk, which invokes this
10// ONCE PER DICTIONARY ENTRY in the query term's first-byte run, across all 14 segments of the web shard.
11// MEASURED LIVE 2026-08-15 on a zero-result query: page-reported search time <1 ms (the result memo hit)
12// yet wall clock 10,417 ms -- so ~10.4 s sits in this path, invisible to every happy-path measurement
13// because only a query that finds NOTHING pays it.
14// SAFE AS STATICS -- the same argument that shipped dss_tf_all's identical hoist: the rows are FIXED SIZE
15// (never derived from input), every cell is WRITTEN BEFORE IT IS READ on each row, the scratch is dead on
16// return, the function is not recursive, and the daemon is fork-per-request so each child owns its copy.
17// ⚠The length-gap early-out stays FIRST and above these: a reject must remain O(1) and must not touch
18// the rows at all -- that early-out is what makes most candidates free, and it already existed.
19const ED_ROWCELLS: i64 = 512
20static ed_prev: *i64
21static ed_cur: *i64
22func ed_bounded(a: *u8, an: i64, b: *u8, bn: i64, bound: i64) -> i64 {
23 var gap: i64 = an - bn
24 if gap < 0 { gap = 0 - gap }
25 if gap > bound { return bound + 1 }
26 if an == 0 { return bn }
27 if bn == 0 { return an }
28 // ★LATENT ROW OVERFLOW CLOSED IN PASSING: the rows were 40 cells and the loops write prev[bn]/cur[bn],
29 // but `an` reaches this from dss_correct's 64-BYTE token slots, so a query word longer than 37 bytes
30 // overran both rows. sys_mmap rounds to a page either way, so 512 cells costs exactly what 40 did --
31 // the small number bought nothing and risked memory. The guard below is belt-and-braces for anything
32 // that ever exceeds even that, and it REFUSES rather than truncating.
33 if an >= ED_ROWCELLS { return bound + 1 }
34 if bn >= ED_ROWCELLS { return bound + 1 }
35 if (ed_prev as i64) == 0 { ed_prev = sys_mmap(ED_ROWCELLS * 8) as *i64 }
36 if (ed_cur as i64) == 0 { ed_cur = sys_mmap(ED_ROWCELLS * 8) as *i64 }
37 let prev: *i64 = ed_prev
38 let cur: *i64 = ed_cur
39 var j: i64 = 0
40 while j <= bn { prev[j] = j; j = j + 1 }
41 var i: i64 = 1
42 while i <= an {
43 cur[0] = i
44 var rowmin: i64 = i
45 j = 1
46 while j <= bn {
47 var cost: i64 = 1
48 if a[i - 1] == b[j - 1] { cost = 0 }
49 var v: i64 = prev[j - 1] + cost // substitute / match
50 let del: i64 = prev[j] + 1 // delete from a
51 if del < v { v = del }
52 let ins: i64 = cur[j - 1] + 1 // insert into a
53 if ins < v { v = ins }
54 cur[j] = v
55 if v < rowmin { rowmin = v }
56 j = j + 1
57 }
58 if rowmin > bound { return bound + 1 } // the whole row exceeded the bound -> can only grow
59 j = 0
60 while j <= bn { prev[j] = cur[j]; j = j + 1 }
61 i = i + 1
62 }
63 return prev[bn]
64}