code wiki / _hdl_build / nx_ui_tdist.nx
nx_ui_tdist.nx source
↩ module page · 197 lines · 11957 B
1// nx_ui_tdist.nx -- ui-validation V1 (sovereign DETERMINISTIC engine). Real structural TREE-EDIT-DISTANCE:
2// upgrades nx_ui_struct's flat-fingerprint to an ORDER + DEPTH sensitive tree metric. Parses HTML into a
3// POSTORDER (tag,depth) token sequence (a DOM-tree serialization: each element emitted after its children,
4// carrying its nesting depth) and computes edit distance between two pages' sequences. Catches subtree
5// add/remove, reordering, and nesting changes that a flat count misses. DETERMINISTIC, LLM-free, air-gap.
6// ★KAT-GATED: `selftest` proves the edit-distance core correct (identical=0, insert=1, substitute=1,
7// delete=1) BEFORE any page is judged -- correctness proven, not asserted (the anti-navel-gaze discipline).
8// HONEST ENVELOPE: postorder-serialization edit distance = a TRACTABLE tree-structure metric; full
9// Zhang-Shasha ZSS tree-edit-distance over the RENDERED AXTree = the exact-optimal follow-on (needs the
10// sovereign browser's live accessibility tree, browser lane). Assumes well-formed server-emitted markup.
11// nx_ui_tdist selftest | dist <urlA> <urlB> [connect]
12// exit: 0 (selftest GREEN / dist computed) | 1 selftest RED | 4 fetch-fail | 2 usage.
13// license_tier: ORIGINAL expect_exit: 0
14import "nx_tool_run.nx"
15const K_MAGIC_30000: i64 = 30000
16const K_MAGIC_2166136261: i64 = 2166136261
17const K_MAGIC_16777619: i64 = 16777619
18const K_MAGIC_2147483647: i64 = 2147483647
19const K_MAGIC_5000: i64 = 5000
20const K_MAGIC_4096: i64 = 4096
21const K_MAGIC_524288: i64 = 524288
22const K_MAGIC_2048: i64 = 2048
23
24func td_w(fd: i64, s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(fd, s, n); return 0 }
25func td_b(rep: *u8, pos: i64, s: *u8) -> i64 { var p: i64 = pos; var i: i64 = 0; while s[i] != (0 as u8) { if p < K_MAGIC_30000 { rep[p] = s[i]; p = p + 1 } i = i + 1 } return p }
26func td_bn(rep: *u8, pos: i64, v: i64) -> i64 { var p: i64 = pos; var m: i64 = v; if m < 0 { if p < K_MAGIC_30000 { rep[p] = 45 as u8; p = p + 1 } m = 0 - m } let t: *u8 = sys_mmap(28); var k: i64 = 0; if m == 0 { t[0] = 48 as u8; k = 1 } while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } var i: i64 = 0; while i < k { if p < K_MAGIC_30000 { rep[p] = t[k - 1 - i]; p = p + 1 } i = i + 1 } return p }
27func td_min3(a: i64, b: i64, c: i64) -> i64 { var m: i64 = a; if b < m { m = b } if c < m { m = c } return m }
28// FNV-ish hash of a byte span [s,e) -> stable 31-bit tag id
29func td_hash(buf: *u8, s: i64, e: i64) -> i64 {
30 var h: i64 = K_MAGIC_2166136261
31 var i: i64 = s
32 while i < e { let c: i64 = buf[i]; var lc: i64 = c; if c >= 65 { if c <= 90 { lc = c + 32 } } h = (h ^ lc) * K_MAGIC_16777619; h = h & K_MAGIC_2147483647; i = i + 1 }
33 if h == 0 { h = 1 }
34 return h
35}
36// is the lowercased name span [s,e) a void element (no close tag)?
37func td_void(buf: *u8, s: i64, e: i64) -> i64 {
38 let ln: i64 = e - s
39 // check img input br hr meta link area col wbr
40 if ln == 3 { if buf[s]==(105 as u8) { if buf[s+1]==(109 as u8) { if buf[s+2]==(103 as u8) { return 1 } } } }
41 if ln == 5 { if buf[s]==(105 as u8) { if buf[s+1]==(110 as u8) { return 1 } } }
42 if ln == 2 { if buf[s]==(98 as u8) { if buf[s+1]==(114 as u8) { return 1 } } if buf[s]==(104 as u8) { if buf[s+1]==(114 as u8) { return 1 } } }
43 if ln == 4 { if buf[s]==(109 as u8) { if buf[s+1]==(101 as u8) { return 1 } } if buf[s]==(108 as u8) { if buf[s+1]==(105 as u8) { return 1 } } }
44 return 0
45}
46func td_isletter(c: i64) -> i64 { if c >= 65 { if c <= 90 { return 1 } } if c >= 97 { if c <= 122 { return 1 } } return 0 }
47// parse HTML [0,n) -> postorder (tag*64+depth) tokens into toks; return count
48func td_tokens(buf: *u8, n: i64, toks: *i64, cap: i64) -> i64 {
49 var cnt: i64 = 0
50 var depth: i64 = 0
51 var i: i64 = 0
52 while i < n {
53 if buf[i] != (60 as u8) { i = i + 1 } else {
54 let c1: i64 = buf[i+1]
55 if c1 == 33 {
56 var j: i64 = i + 1; var done: i64 = 0
57 while done == 0 { if j >= n { done = 1; i = n } else { if buf[j] == (62 as u8) { done = 1; i = j + 1 } else { j = j + 1 } } }
58 } else { if c1 == 47 {
59 // close tag </name>
60 var s: i64 = i + 2; var e: i64 = s
61 while e < n { let c: i64 = buf[e]; if c == 62 { let z: i64 = e; e = n + K_MAGIC_5000 + z } else { if c == 32 { let z2: i64 = e; e = n + K_MAGIC_5000 + z2 } else { e = e + 1 } } }
62 var namee: i64 = e
63 if namee > n { namee = namee - n - K_MAGIC_5000 }
64 if cnt < cap { if depth > 0 { toks[cnt] = td_hash(buf, s, namee) * 64 + depth; cnt = cnt + 1 } }
65 if depth > 0 { depth = depth - 1 }
66 // advance past '>'
67 var g: i64 = namee; var gd: i64 = 0
68 while gd == 0 { if g >= n { gd = 1; i = n } else { if buf[g] == (62 as u8) { gd = 1; i = g + 1 } else { g = g + 1 } } }
69 } else { if td_isletter(c1) == 1 {
70 // open tag <name ...>
71 var s2: i64 = i + 1; var e2: i64 = s2
72 while e2 < n { let c: i64 = buf[e2]; if c == 32 { let z: i64 = e2; e2 = n + K_MAGIC_5000 + z } else { if c == 62 { let z2: i64 = e2; e2 = n + K_MAGIC_5000 + z2 } else { if c == 47 { let z3: i64 = e2; e2 = n + K_MAGIC_5000 + z3 } else { e2 = e2 + 1 } } } }
73 var namee2: i64 = e2
74 if namee2 > n { namee2 = namee2 - n - K_MAGIC_5000 }
75 let isv: i64 = td_void(buf, s2, namee2)
76 // find tag end '>' and detect self-close '/>'
77 var te: i64 = namee2; var selfc: i64 = 0; var fd2: i64 = 0
78 while fd2 == 0 { if te >= n { fd2 = 1 } else { if buf[te] == (62 as u8) { if te > 0 { if buf[te-1] == (47 as u8) { selfc = 1 } } fd2 = 1 } else { te = te + 1 } } }
79 if isv == 1 { if cnt < cap { toks[cnt] = td_hash(buf, s2, namee2) * 64 + (depth + 1); cnt = cnt + 1 } } else { if selfc == 1 { if cnt < cap { toks[cnt] = td_hash(buf, s2, namee2) * 64 + (depth + 1); cnt = cnt + 1 } } else { depth = depth + 1 } }
80 i = te + 1
81 } else { i = i + 1 } } }
82 }
83 }
84 return cnt
85}
86// Levenshtein edit distance between int arrays a[0,na) and b[0,nb) (unit costs)
87func td_lev(a: *i64, na: i64, b: *i64, nb: i64) -> i64 {
88 let prev: *i64 = sys_mmap((nb + 2) * 8) as *i64
89 let cur: *i64 = sys_mmap((nb + 2) * 8) as *i64
90 var j: i64 = 0
91 while j <= nb { prev[j] = j; j = j + 1 }
92 var i: i64 = 1
93 while i <= na {
94 cur[0] = i
95 var k: i64 = 1
96 while k <= nb {
97 var sub: i64 = 1
98 if a[i-1] == b[k-1] { sub = 0 }
99 cur[k] = td_min3(prev[k] + 1, cur[k-1] + 1, prev[k-1] + sub)
100 k = k + 1
101 }
102 var m: i64 = 0
103 while m <= nb { prev[m] = cur[m]; m = m + 1 }
104 i = i + 1
105 }
106 return prev[nb]
107}
108func td_kat(rep: *u8, pos: i64, name: *u8, got: i64, want: i64, fails: *i64) -> i64 {
109 var p: i64 = pos
110 p = td_b(rep, p, " " as *u8); p = td_b(rep, p, name); p = td_b(rep, p, " got=" as *u8); p = td_bn(rep, p, got); p = td_b(rep, p, " want=" as *u8); p = td_bn(rep, p, want)
111 if got == want { p = td_b(rep, p, " PASS\n" as *u8) } else { p = td_b(rep, p, " FAIL\n" as *u8); fails[0] = fails[0] + 1 }
112 return p
113}
114func td_reads(path: *u8, buf: *u8, cap: i64) -> i64 {
115 let fd: i64 = sys_openat_rd(path)
116 if fd < 0 { return 0 - 1 }
117 var n: i64 = 0
118 var go: i64 = 1
119 while go == 1 { let r: i64 = sys_read(fd, (buf as i64 + n) as *u8, cap - n); if r <= 0 { go = 0 } else { n = n + r } if n >= cap { go = 0 } }
120 sys_close(fd)
121 return n
122}
123func td_fetch(url: *i64, connect: i64, buf: *u8, cap: i64, olen: *i64) -> i64 {
124 let HG: *u8 = "/volume1/homes/elderwesto/nishihost/nx_https_get.elf" as *u8
125 let av: *i64 = sys_mmap(16 * 8) as *i64
126 av[0] = HG as i64; av[1] = url as i64
127 if connect != 0 { av[2] = connect; av[3] = 0 } else { av[2] = 0 }
128 return tr_run_capture(HG, av, buf, cap, olen)
129}
130func main(argc: i64, argv: *i64) -> i64 {
131 if argc < 2 { td_w(2, "usage: nx_ui_tdist selftest | dist <urlA> <urlB> [connect]\n" as *u8); sys_exit(2); return 2 }
132 let verb: *u8 = argv[1] as *u8
133 if verb[0] == 115 {
134 // selftest: KAT the edit-distance core
135 let rep: *u8 = sys_mmap(K_MAGIC_4096)
136 var p: i64 = 0
137 let fails: *i64 = sys_mmap(16) as *i64
138 fails[0] = 0
139 p = td_b(rep, p, "NX-UI-TDIST selftest (edit-distance core)\n" as *u8)
140 let a: *i64 = sys_mmap(64) as *i64
141 let b: *i64 = sys_mmap(64) as *i64
142 a[0]=1; a[1]=2; a[2]=3
143 b[0]=1; b[1]=2; b[2]=3
144 p = td_kat(rep, p, "identical" as *u8, td_lev(a, 3, b, 3), 0, fails)
145 b[3]=4
146 p = td_kat(rep, p, "insert" as *u8, td_lev(a, 3, b, 4), 1, fails)
147 b[0]=1; b[1]=9; b[2]=3
148 p = td_kat(rep, p, "substitute" as *u8, td_lev(a, 3, b, 3), 1, fails)
149 b[0]=1; b[1]=3
150 p = td_kat(rep, p, "delete" as *u8, td_lev(a, 3, b, 2), 1, fails)
151 a[0]=5;a[1]=6;a[2]=7;a[3]=8; b[0]=5;b[1]=8
152 p = td_kat(rep, p, "delete2" as *u8, td_lev(a, 4, b, 2), 2, fails)
153 if fails[0] == 0 { p = td_b(rep, p, "VERDICT=GREEN (edit-distance core proven; safe to judge pages)\n" as *u8) } else { p = td_b(rep, p, "VERDICT=RED\n" as *u8) }
154 sys_write(1, rep, p)
155 if fails[0] == 0 { sys_exit(0); return 0 }
156 sys_exit(1); return 1
157 }
158 if argc < 4 { td_w(2, "usage: nx_ui_tdist dist <urlA> <urlB> [connect]\n" as *u8); sys_exit(2); return 2 }
159 var connect: i64 = 0
160 if argc >= 5 { connect = argv[4] }
161 let cap: i64 = K_MAGIC_524288
162 let bufA: *u8 = sys_mmap(cap + 16)
163 let bufB: *u8 = sys_mmap(cap + 16)
164 let olen: *i64 = sys_mmap(16) as *i64
165 let ra: i64 = td_fetch((argv[2]) as *i64, connect, bufA, cap, olen)
166 let na: i64 = olen[0]
167 if ra == 127 { td_w(1, "UI-TDIST verdict=FETCH-FAIL A\n" as *u8); sys_exit(4); return 4 }
168 if na <= 0 { td_w(1, "UI-TDIST verdict=FETCH-FAIL A-empty\n" as *u8); sys_exit(4); return 4 }
169 let rb: i64 = td_fetch((argv[3]) as *i64, connect, bufB, cap, olen)
170 let nb: i64 = olen[0]
171 if rb == 127 { td_w(1, "UI-TDIST verdict=FETCH-FAIL B\n" as *u8); sys_exit(4); return 4 }
172 if nb <= 0 { td_w(1, "UI-TDIST verdict=FETCH-FAIL B-empty\n" as *u8); sys_exit(4); return 4 }
173 let tcap: i64 = K_MAGIC_4096
174 let tA: *i64 = sys_mmap(tcap * 8) as *i64
175 let tB: *i64 = sys_mmap(tcap * 8) as *i64
176 let cA: i64 = td_tokens(bufA, na, tA, tcap)
177 let cB: i64 = td_tokens(bufB, nb, tB, tcap)
178 let dist: i64 = td_lev(tA, cA, tB, cB)
179 var bigger: i64 = cA
180 if cB > bigger { bigger = cB }
181 var pct: i64 = 0
182 if bigger > 0 { pct = (dist * 1000) / bigger }
183 let rep: *u8 = sys_mmap(K_MAGIC_2048)
184 var p: i64 = 0
185 p = td_b(rep, p, "{\"kind\":\"tree_edit_distance\",\"nodesA\":" as *u8); p = td_bn(rep, p, cA)
186 p = td_b(rep, p, ",\"nodesB\":" as *u8); p = td_bn(rep, p, cB)
187 p = td_b(rep, p, ",\"tree_edit_distance\":" as *u8); p = td_bn(rep, p, dist)
188 p = td_b(rep, p, ",\"drift_permille\":" as *u8); p = td_bn(rep, p, pct)
189 p = td_b(rep, p, ",\"verdict\":\"" as *u8)
190 if dist == 0 { p = td_b(rep, p, "IDENTICAL-STRUCTURE" as *u8) } else { if pct < 50 { p = td_b(rep, p, "MINOR-DRIFT" as *u8) } else { if pct < 250 { p = td_b(rep, p, "MODERATE-RESTRUCTURE" as *u8) } else { p = td_b(rep, p, "MAJOR-RESTRUCTURE" as *u8) } } }
191 p = td_b(rep, p, "\",\"metric\":\"postorder (tag,depth) serialization edit distance -- deterministic LLM-free tree-structure metric; full Zhang-Shasha ZSS over the rendered AXTree = exact-optimal follow-on\"}" as *u8)
192 sys_write(1, rep, p)
193 let ofd: i64 = sys_openat_wr("knowledge/status/ui_tdist.out.tmp" as *u8, 420)
194 if ofd >= 0 { sys_write(ofd, rep, p); sys_close(ofd); sys_renameat("knowledge/status/ui_tdist.out.tmp" as *u8, "knowledge/status/ui_tdist.out" as *u8) }
195 sys_exit(0)
196 return 0
197}