`nx_ui_zss.nx` source

↩ module page · 231 lines · 14299 B
1// nx_ui_zss.nx -- ui-validation V1b (sovereign DETERMINISTIC engine). The EXACT-OPTIMAL structural
2// tree-edit-distance: real ZHANG-SHASHA (ZSS) over the DOM tree. Closes the honest gap nx_ui_tdist left
3// (postorder-Levenshtein = a tractable approximation; ZSS = the true tree-edit-distance that respects tree
4// structure in its edit operations). Reconstructs the tree from the postorder (tag,depth) DOM serialization:
5// leftmost-leaf-descendant l[] and keyroots derive directly from depth; then the ZSS forestdist DP. NO model.
6// KAT-GATED: `selftest` proves ZSS on known small-tree distances BEFORE any page is judged (anti-navel-gaze:
7// a hard algorithm must earn a green self-test first). HONEST ENVELOPE: exact ZSS over the SOURCE DOM tree,
8// node-capped for tractability; ZSS over the RENDERED AXTree = the browser-lane follow-on.
9//   nx_ui_zss selftest  |  dist <urlA> <urlB> [connect]
10// exit: 0 (selftest GREEN / dist computed) | 1 selftest RED | 4 fetch-fail | 2 usage.
11// license_tier: ORIGINAL   expect_exit: 0
12import "nx_tool_run.nx"
13const K_MAGIC_30000: i64 = 30000
14const K_MAGIC_2166136261: i64 = 2166136261
15const K_MAGIC_16777619: i64 = 16777619
16const K_MAGIC_2147483647: i64 = 2147483647
17const K_MAGIC_5000: i64 = 5000
18const K_MAGIC_4096: i64 = 4096
19const K_MAGIC_524288: i64 = 524288
20const K_MAGIC_2048: i64 = 2048
21
22func z_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 }
23func z_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 }
24func z_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 }
25func z_min3(a: i64, b: i64, c: i64) -> i64 { var m: i64 = a; if b < m { m = b } if c < m { m = c } return m }
26func z_hash(buf: *u8, s: i64, e: i64) -> i64 { var h: i64 = K_MAGIC_2166136261; var i: i64 = s; 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 } if h == 0 { h = 1 } return h }
27func z_void(buf: *u8, s: i64, e: i64) -> i64 { let ln: i64 = e - s; 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 } } } } if ln == 5 { if buf[s]==(105 as u8) { if buf[s+1]==(110 as u8) { return 1 } } } 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 } } } 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 } } } return 0 }
28func z_isletter(c: i64) -> i64 { if c >= 65 { if c <= 90 { return 1 } } if c >= 97 { if c <= 122 { return 1 } } return 0 }
29// parse HTML -> postorder lab[1..cnt] + dep[1..cnt]; return cnt (capped)
30func z_parse(buf: *u8, n: i64, lab: *i64, dep: *i64, cap: i64) -> i64 {
  var cnt: i64 = 0
  var depth: i64 = 0
  var i: i64 = 0
  while i < n {
      if buf[i] != (60 as u8) { i = i + 1 } else {
          let c1: i64 = buf[i+1]
          if c1 == 33 {
              var j: i64 = i + 1; var done: i64 = 0
              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 } } }
          } else { if c1 == 47 {
              var s: i64 = i + 2; var e: i64 = s
              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 } } }
              var namee: i64 = e
              if namee > n { namee = namee - n - K_MAGIC_5000 }
              if depth > 0 { if cnt < cap { cnt = cnt + 1; lab[cnt] = z_hash(buf, s, namee); dep[cnt] = depth } depth = depth - 1 }
              var g: i64 = namee; var gd: i64 = 0
              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 } } }
          } else { if z_isletter(c1) == 1 {
              var s2: i64 = i + 1; var e2: i64 = s2
              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 } } } }
              var namee2: i64 = e2
              if namee2 > n { namee2 = namee2 - n - K_MAGIC_5000 }
              let isv: i64 = z_void(buf, s2, namee2)
              var te: i64 = namee2; var selfc: i64 = 0; var fd2: i64 = 0
              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 } } }
              if isv == 1 { if cnt < cap { cnt = cnt + 1; lab[cnt] = z_hash(buf, s2, namee2); dep[cnt] = depth + 1 } } else { if selfc == 1 { if cnt < cap { cnt = cnt + 1; lab[cnt] = z_hash(buf, s2, namee2); dep[cnt] = depth + 1 } } else { depth = depth + 1 } }
              i = te + 1
          } else { i = i + 1 } } }
      }
  }
  return cnt
62}
63// l[i] = leftmost-leaf-descendant postorder index, from postorder depth
64func z_lfd(dep: *i64, n: i64, l: *i64) -> i64 {
  var i: i64 = 1
  while i <= n {
      var j: i64 = i - 1
      var go: i64 = 1
      while go == 1 { if j < 1 { go = 0 } else { if dep[j] > dep[i] { j = j - 1 } else { go = 0 } } }
      if j == i - 1 { l[i] = i } else { l[i] = j + 1 }
      i = i + 1
  }
  return 0
74}
75// keyroots ascending; returns count
76func z_keyroots(l: *i64, n: i64, kr: *i64) -> i64 {
  let seen: *i64 = sys_mmap((n + 2) * 8) as *i64
  var cnt: i64 = 0
  var i: i64 = n
  while i >= 1 { if seen[l[i]] == 0 { seen[l[i]] = 1; kr[cnt] = i; cnt = cnt + 1 } i = i - 1 }
  var a: i64 = 0; var b: i64 = cnt - 1
  while a < b { let t: i64 = kr[a]; kr[a] = kr[b]; kr[b] = t; a = a + 1; b = b - 1 }
  return cnt
84}
85// Zhang-Shasha tree-edit-distance (unit costs). 1-indexed postorder lab/dep.
86func z_zss(lab1: *i64, dep1: *i64, n1: i64, lab2: *i64, dep2: *i64, n2: i64) -> i64 {
  let l1: *i64 = sys_mmap((n1 + 2) * 8) as *i64
  let l2: *i64 = sys_mmap((n2 + 2) * 8) as *i64
  z_lfd(dep1, n1, l1); z_lfd(dep2, n2, l2)
  let kr1: *i64 = sys_mmap((n1 + 2) * 8) as *i64
  let kr2: *i64 = sys_mmap((n2 + 2) * 8) as *i64
  let k1n: i64 = z_keyroots(l1, n1, kr1)
  let k2n: i64 = z_keyroots(l2, n2, kr2)
  let w: i64 = n2 + 1
  let td: *i64 = sys_mmap((n1 + 1) * (n2 + 1) * 8) as *i64
  let fd: *i64 = sys_mmap((n1 + 1) * (n2 + 1) * 8) as *i64
  var a: i64 = 0
  while a < k1n {
      let i1: i64 = kr1[a]
      var bb: i64 = 0
      while bb < k2n {
          let j1: i64 = kr2[bb]
          let li: i64 = l1[i1]
          let lj: i64 = l2[j1]
          fd[(li - 1) * w + (lj - 1)] = 0
          var di: i64 = li
          while di <= i1 { fd[di * w + (lj - 1)] = fd[(di - 1) * w + (lj - 1)] + 1; di = di + 1 }
          var dj: i64 = lj
          while dj <= j1 { fd[(li - 1) * w + dj] = fd[(li - 1) * w + (dj - 1)] + 1; dj = dj + 1 }
          di = li
          while di <= i1 {
              dj = lj
              while dj <= j1 {
                  var same: i64 = 0
                  if l1[di] == li { if l2[dj] == lj { same = 1 } }
                  if same == 1 {
                      var cost: i64 = 1
                      if lab1[di] == lab2[dj] { cost = 0 }
                      let v: i64 = z_min3(fd[(di - 1) * w + dj] + 1, fd[di * w + (dj - 1)] + 1, fd[(di - 1) * w + (dj - 1)] + cost)
                      fd[di * w + dj] = v
                      td[di * w + dj] = v
                  } else {
                      let v2: i64 = z_min3(fd[(di - 1) * w + dj] + 1, fd[di * w + (dj - 1)] + 1, fd[(l1[di] - 1) * w + (l2[dj] - 1)] + td[di * w + dj])
                      fd[di * w + dj] = v2
                  }
                  dj = dj + 1
              }
              di = di + 1
          }
          bb = bb + 1
      }
      a = a + 1
  }
  return td[n1 * w + n2]
135}
136func z_kat(rep: *u8, pos: i64, name: *u8, got: i64, want: i64, fails: *i64) -> i64 {
  var p: i64 = pos
  p = z_b(rep, p, "  " as *u8); p = z_b(rep, p, name); p = z_b(rep, p, " got=" as *u8); p = z_bn(rep, p, got); p = z_b(rep, p, " want=" as *u8); p = z_bn(rep, p, want)
  if got == want { p = z_b(rep, p, " PASS\n" as *u8) } else { p = z_b(rep, p, " FAIL\n" as *u8); fails[0] = fails[0] + 1 }
  return p
141}
142func z_fetch(url: i64, connect: i64, buf: *u8, cap: i64, olen: *i64) -> i64 {
  let HG: *u8 = "/volume1/homes/elderwesto/nishihost/nx_https_get.elf" as *u8
  let av: *i64 = sys_mmap(16 * 8) as *i64
  av[0] = HG as i64; av[1] = url
  if connect != 0 { av[2] = connect; av[3] = 0 } else { av[2] = 0 }
  return tr_run_capture(HG, av, buf, cap, olen)
148}
149func main(argc: i64, argv: *i64) -> i64 {
  if argc < 2 { z_w(2, "usage: nx_ui_zss selftest | dist <urlA> <urlB> [connect]\n" as *u8); sys_exit(2); return 2 }
  let verb: *u8 = argv[1] as *u8
  if verb[0] == 115 {
      let rep: *u8 = sys_mmap(K_MAGIC_4096)
      var p: i64 = 0
      let fails: *i64 = sys_mmap(16) as *i64
      fails[0] = 0
      p = z_b(rep, p, "NX-UI-ZSS selftest (Zhang-Shasha tree-edit-distance)\n" as *u8)
      let la: *i64 = sys_mmap(64) as *i64
      let da: *i64 = sys_mmap(64) as *i64
      let lb: *i64 = sys_mmap(64) as *i64
      let db: *i64 = sys_mmap(64) as *i64
      // single vs single same
      la[1]=10; da[1]=0; lb[1]=10; db[1]=0
      p = z_kat(rep, p, "single-identical" as *u8, z_zss(la,da,1, lb,db,1), 0, fails)
      // single relabel
      lb[1]=11
      p = z_kat(rep, p, "single-relabel" as *u8, z_zss(la,da,1, lb,db,1), 1, fails)
      // a(b) vs a : postorder T1 [b(1),a(0)], T2 [a(0)]
      la[1]=11; da[1]=1; la[2]=10; da[2]=0; lb[1]=10; db[1]=0
      p = z_kat(rep, p, "delete-leaf" as *u8, z_zss(la,da,2, lb,db,1), 1, fails)
      // a(b,c) vs a(b): T1 [b(1),c(1),a(0)], T2 [b(1),a(0)]
      la[1]=11; da[1]=1; la[2]=12; da[2]=1; la[3]=10; da[3]=0; lb[1]=11; db[1]=1; lb[2]=10; db[2]=0
      p = z_kat(rep, p, "delete-child" as *u8, z_zss(la,da,3, lb,db,2), 1, fails)
      // a(b,c) vs a(x,c): T2 [x(1),c(1),a(0)]
      lb[1]=14; db[1]=1; lb[2]=12; db[2]=1; lb[3]=10; db[3]=0
      p = z_kat(rep, p, "relabel-child" as *u8, z_zss(la,da,3, lb,db,3), 1, fails)
      // a(b,c) vs a(c,b): T2 [c(1),b(1),a(0)]
      lb[1]=12; db[1]=1; lb[2]=11; db[2]=1; lb[3]=10; db[3]=0
      p = z_kat(rep, p, "swap-children" as *u8, z_zss(la,da,3, lb,db,3), 2, fails)
      // a(b(d),c) vs a(b,c): T1 [d(2),b(1),c(1),a(0)], T2 [b(1),c(1),a(0)]
      la[1]=13; da[1]=2; la[2]=11; da[2]=1; la[3]=12; da[3]=1; la[4]=10; da[4]=0
      lb[1]=11; db[1]=1; lb[2]=12; db[2]=1; lb[3]=10; db[3]=0
      p = z_kat(rep, p, "delete-grandchild" as *u8, z_zss(la,da,4, lb,db,3), 1, fails)
      if fails[0] == 0 { p = z_b(rep, p, "VERDICT=GREEN (ZSS proven correct; safe to judge pages)\n" as *u8) } else { p = z_b(rep, p, "VERDICT=RED\n" as *u8) }
      sys_write(1, rep, p)
      if fails[0] == 0 { sys_exit(0); return 0 }
      sys_exit(1); return 1
  }
  if argc < 4 { z_w(2, "usage: nx_ui_zss dist <urlA> <urlB> [connect]\n" as *u8); sys_exit(2); return 2 }
  var connect: i64 = 0
  if argc >= 5 { connect = argv[4] }
  let cap: i64 = K_MAGIC_524288
  let bufA: *u8 = sys_mmap(cap + 16)
  let bufB: *u8 = sys_mmap(cap + 16)
  let olen: *i64 = sys_mmap(16) as *i64
  let ra: i64 = z_fetch(argv[2], connect, bufA, cap, olen)
  let na: i64 = olen[0]
  if ra == 127 { z_w(1, "UI-ZSS verdict=FETCH-FAIL A\n" as *u8); sys_exit(4); return 4 }
  if na <= 0 { z_w(1, "UI-ZSS verdict=FETCH-FAIL A-empty\n" as *u8); sys_exit(4); return 4 }
  let rb: i64 = z_fetch(argv[3], connect, bufB, cap, olen)
  let nb: i64 = olen[0]
  if rb == 127 { z_w(1, "UI-ZSS verdict=FETCH-FAIL B\n" as *u8); sys_exit(4); return 4 }
  if nb <= 0 { z_w(1, "UI-ZSS verdict=FETCH-FAIL B-empty\n" as *u8); sys_exit(4); return 4 }
  let ncap: i64 = 320
  let labA: *i64 = sys_mmap((ncap + 2) * 8) as *i64
  let depA: *i64 = sys_mmap((ncap + 2) * 8) as *i64
  let labB: *i64 = sys_mmap((ncap + 2) * 8) as *i64
  let depB: *i64 = sys_mmap((ncap + 2) * 8) as *i64
  let cA: i64 = z_parse(bufA, na, labA, depA, ncap)
  let cB: i64 = z_parse(bufB, nb, labB, depB, ncap)
  let dist: i64 = z_zss(labA, depA, cA, labB, depB, cB)
  var bigger: i64 = cA
  if cB > bigger { bigger = cB }
  var pct: i64 = 0
  if bigger > 0 { pct = (dist * 1000) / bigger }
  let rep: *u8 = sys_mmap(K_MAGIC_2048)
  var p: i64 = 0
  p = z_b(rep, p, "{\"kind\":\"zss_tree_edit_distance\",\"nodesA\":" as *u8); p = z_bn(rep, p, cA)
  p = z_b(rep, p, ",\"nodesB\":" as *u8); p = z_bn(rep, p, cB)
  p = z_b(rep, p, ",\"node_cap\":" as *u8); p = z_bn(rep, p, ncap)
  p = z_b(rep, p, ",\"zss_distance\":" as *u8); p = z_bn(rep, p, dist)
  p = z_b(rep, p, ",\"drift_permille\":" as *u8); p = z_bn(rep, p, pct)
  p = z_b(rep, p, ",\"verdict\":\"" as *u8)
  if dist == 0 { p = z_b(rep, p, "IDENTICAL-STRUCTURE" as *u8) } else { if pct < 50 { p = z_b(rep, p, "MINOR-DRIFT" as *u8) } else { if pct < 250 { p = z_b(rep, p, "MODERATE-RESTRUCTURE" as *u8) } else { p = z_b(rep, p, "MAJOR-RESTRUCTURE" as *u8) } } }
  p = z_b(rep, p, "\",\"metric\":\"EXACT Zhang-Shasha ZSS tree-edit-distance over the source DOM (node-capped); KAT-verified core; rendered-AXTree ZSS = browser-lane follow-on\"}" as *u8)
  sys_write(1, rep, p)
  let ofd: i64 = sys_openat_wr("knowledge/status/ui_zss.out.tmp" as *u8, 420)
  if ofd >= 0 { sys_write(ofd, rep, p); sys_close(ofd); sys_renameat("knowledge/status/ui_zss.out.tmp" as *u8, "knowledge/status/ui_zss.out" as *u8) }
  sys_exit(0)
  return 0
231}
nx_ui_zss.nx source

`nx_ui_zss.nx` source
