code wiki / _hdl_build / nx_treediverge.nx
`nx_treediverge.nx` source

↩ module page · 317 lines · 15978 B
1// nx_treediverge.nx -- THE MISSING CROSS-TREE DIVERGENCE DETECTOR (debt 1785438829, sev-8).
2//
3// THE GAP IT CLOSES, in that debt's own words: "nx_dup_source_check finds dups WITHIN buildroot but
4// there is NO laptop-vs-NAS divergence detector -- I did it BY HAND four times today. BUILD THAT: a
5// cross-tree census emitting per-file laptop_bytes / nas_bytes / delta / direction, so divergence is a
6// REPORT rather than an archaeology exercise; size alone would have caught all four of today's instances."
7//
8// WHY IT MATTERS (not tidiness): /api/build compiles from buildroot, so a fix living only in the laptop
9// SSOT NEVER REACHES A RUNNING BINARY, and a fix living only in buildroot is DESTROYED by the next sync
10// from the SSOT. The divergence is BIDIRECTIONAL -- neither tree is a superset -- so a one-way sync in
11// EITHER direction silently loses work. You cannot merge safely without first knowing the direction
12// per file. That is exactly what this emits.
13//
14// COMPOSES, DOES NOT DUPLICATE: nx_treediff already emits one tree's manifest as "<bytes> <relpath>"
15// per .nx file and says in its own usage that it is "for cross-tree comparison" -- it just never
16// performed the comparison. This is the missing half. Run nx_treediff on each tree, then:
17//     nx_treediverge <manifestA> <manifestB> [labelA] [labelB]
18//
19// VERDICTS, per file: A-ONLY / B-ONLY / A-AHEAD / B-AHEAD / SAME. "AHEAD" is BY BYTES, which is the
20// signal that caught all four historical instances; it is a FLOOR, not proof of content (equal size can
21// still differ -- see the same-size-rewrite caveat on expect=<size> CAS). Declared, never implied.
22//
23// NON-VACUITY: an empty or unreadable manifest REFUSES (exit 3) instead of reporting "0 divergent",
24// because a comparator that reads nothing and prints GREEN is the self-ceiling defect this ecosystem
25// has banned repeatedly. A zero-divergence verdict is only emitted when BOTH sides actually had rows.
26import "nx_syscalls.nx"
27const TV_MAGIC_5381: i64 = 5381
28
29const TV_HBUCKETS: i64 = 65536        // hash buckets; power of two so the mask is an AND
30const TV_MAXENT: i64 = 200000         // per-tree entry ceiling (corpus is ~17.7k .nx today, 11x headroom)
31const TV_BUFCAP: i64 = 16777216       // 16 MiB per manifest (17.7k rows x ~80B ~= 1.4 MiB, 11x headroom)
32
33static tv_keyp: *i64                  // B-side: pointer to each relpath (NUL-terminated in place)
34static tv_size: *i64                  // B-side: bytes for that relpath
35static tv_next: *i64                  // B-side: hash chain
36static tv_head: *i64                  // B-side: bucket heads (-1 = empty)
37static tv_seen: *i64                  // B-side: 1 once matched by an A row (to find B-ONLY)
38static tv_nent: *i64
39// COUNTS-ONLY MODE. Set by the `counts` verb; tv_emit becomes a no-op so the ENVELOPE survives.
40// MEASURED 2026-08-16: the laptop-vs-nas comparison emits 191,459 bytes, the transport caps a captured
41// read at 163,840, and this organ prints thousands of DETAIL rows BEFORE its counts -- so the summary is
42// the first casualty of its own verbosity, on exactly the comparison big enough to need one.
43// ★AN ORGAN THAT PRINTS ITS EVIDENCE BEFORE ITS VERDICT LOSES THE VERDICT FIRST WHEN TRUNCATED.
44static tv_quiet: i64
45
46func tv_puts(s: *u8) -> i64 {
  var n: i64 = 0
  while s[n] != (0 as u8) { n = n + 1 }
  sys_write(1, s, n)
  return 0
51}
52func tv_putn(v: i64) -> i64 {
  let b: *u8 = sys_mmap(32)
  var m: i64 = v
  if m == 0 { b[0] = 48 as u8; sys_write(1, b, 1); return 0 }
  if m < 0 { tv_puts("-" as *u8); m = 0 - m }
  let t: *u8 = sys_mmap(32)
  var k: i64 = 0
  while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
  var i: i64 = 0
  while i < k { b[i] = t[k - 1 - i]; i = i + 1 }
  sys_write(1, b, k)
  return 0
64}
65
66// whole-file read; outn[0] = bytes, or -1 when the path is unreadable (REPORTED, never silently 0)
67func tv_readall(path: *u8, outn: *i64) -> *u8 {
  let fd: i64 = sys_openat_rd(path)
  if fd < 0 { outn[0] = 0 - 1; return 0 as *u8 }
  let buf: *u8 = sys_mmap(TV_BUFCAP)
  var tot: i64 = 0
  var go: i64 = 1
  while go == 1 {
      let r: i64 = sys_read(fd, ((buf as i64) + tot) as *u8, TV_BUFCAP - tot - 1)
      if r <= 0 { go = 0 } else { tot = tot + r }
      if tot >= TV_BUFCAP - 1 { go = 0 }
  }
  sys_close(fd)
  buf[tot] = 0 as u8
  outn[0] = tot
  return buf
82}
83
84func tv_hash(s: *u8) -> i64 {
  var h: i64 = TV_MAGIC_5381
  var i: i64 = 0
  while s[i] != (0 as u8) { h = ((h * 33) + (s[i] as i64)) & 0x7fffffff; i = i + 1 }
  return h & (TV_HBUCKETS - 1)
89}
90func tv_streq(a: *u8, b: *u8) -> i64 {
  var i: i64 = 0
  while a[i] != (0 as u8) { if a[i] != b[i] { return 0 } i = i + 1 }
  if b[i] != (0 as u8) { return 0 }
  return 1
95}
96
97// Parse one manifest line "<bytes> <relpath>" IN PLACE: NUL-terminate the relpath, return its pointer;
98// size lands in szout[0]. Returns 0 for a blank/garbled line so the caller can skip without aborting.
99// NOTE: written WITHOUT `break` on purpose -- this dialect's loop-exit idiom is a go-flag, and a
100// hand-rolled pseudo-break is exactly what span forever in the seq95ad autofix intake gate.
101func tv_parse(buf: *u8, start: i64, end: i64, szout: *i64) -> *u8 {
  var i: i64 = start
  var v: i64 = 0
  var any: i64 = 0
  var go: i64 = 1
  while go == 1 {
      if i >= end { go = 0 } else {
          let c: i64 = buf[i] as i64
          if c >= 48 { if c <= 57 { v = v * 10 + (c - 48); any = 1; i = i + 1 } else { go = 0 } } else { go = 0 }
      }
  }
  if any == 0 { return 0 as *u8 }
  if i >= end { return 0 as *u8 }
  if buf[i] != (32 as u8) { return 0 as *u8 }
  let p: i64 = i + 1
  if p >= end { return 0 as *u8 }
  buf[end] = 0 as u8
  szout[0] = v
  return ((buf as i64) + p) as *u8
120}
121
122// index the B manifest into the hash table; returns row count
123func tv_index(buf: *u8, n: i64) -> i64 {
  var i: i64 = 0
  var ls: i64 = 0
  var cnt: i64 = 0
  let szp: *i64 = sys_mmap(16) as *i64
  while i < n {
      if buf[i] == (10 as u8) {
          if cnt < TV_MAXENT {
              let rel: *u8 = tv_parse(buf, ls, i, szp)
              if (rel as i64) != 0 {
                  let h: i64 = tv_hash(rel)
                  tv_keyp[cnt] = rel as i64
                  tv_size[cnt] = szp[0]
                  tv_next[cnt] = tv_head[h]
                  tv_seen[cnt] = 0
                  tv_head[h] = cnt
                  cnt = cnt + 1
              }
          }
          ls = i + 1
      }
      i = i + 1
  }
  return cnt
147}
148
149// find a relpath in the B index; returns entry index or -1
150func tv_find(rel: *u8) -> i64 {
  let h: i64 = tv_hash(rel)
  var e: i64 = tv_head[h]
  while e >= 0 {
      if tv_streq(rel, tv_keyp[e] as *u8) == 1 { return e }
      e = tv_next[e]
  }
  return 0 - 1
158}
159
160func tv_emit(tag: *u8, rel: *u8, a: i64, b: i64) -> i64 {
  if tv_quiet == 1 { return 0 }
  tv_puts(tag); tv_puts(" " as *u8); tv_puts(rel)
  tv_puts(" a=" as *u8); tv_putn(a)
  tv_puts(" b=" as *u8); tv_putn(b)
  tv_puts(" delta=" as *u8); tv_putn(a - b)
  tv_puts("\n" as *u8)
  return 0
168}
169
170func main(argc: i64, argv: *i64) -> i64 {
  if argc < 3 {
      tv_puts("usage: nx_treediverge <manifestA> <manifestB> [labelA] [labelB]\n" as *u8)
      tv_puts("  manifests come from: nx_treediff <dir> <outfile>   (one per tree)\n" as *u8)
      tv_puts("  verdicts per file: A-ONLY / B-ONLY / A-AHEAD / B-AHEAD (by BYTES, a FLOOR)\n" as *u8)
      sys_exit(2)
      return 2
  }
  // `counts` as argv[1] shifts everything by one and suppresses the per-file rows. The whole token is
  // compared, not its first byte: a flag that accepts any spelling cannot report a typo, and silently
  // treating a MANIFEST PATH as the verb would compare the wrong two files and answer confidently.
  var base: i64 = 0
  tv_quiet = 0
  let a1: *u8 = argv[1] as *u8
  if a1[0] == (99 as u8) { if a1[1] == (111 as u8) { if a1[2] == (117 as u8) { if a1[3] == (110 as u8) { if a1[4] == (116 as u8) { if a1[5] == (115 as u8) { if a1[6] == (0 as u8) {
      tv_quiet = 1
      base = 1
  } } } } } } }
  if tv_quiet == 1 { if argc < 4 {
      tv_puts("usage: nx_treediverge counts <manifestA> <manifestB> [labelA] [labelB]\n" as *u8)
      sys_exit(2)
      return 2
  } }
  let pa: *u8 = argv[1 + base] as *u8
  let pb: *u8 = argv[2 + base] as *u8
  var la: *u8 = "A" as *u8
  var lb: *u8 = "B" as *u8
  if argc >= 4 + base { la = argv[3 + base] as *u8 }
  if argc >= 5 + base { lb = argv[4 + base] as *u8 }
199
  let na: *i64 = sys_mmap(16) as *i64
  let nb: *i64 = sys_mmap(16) as *i64
  let ba: *u8 = tv_readall(pa, na)
  let bb: *u8 = tv_readall(pb, nb)
  // NON-VACUITY: refuse rather than report a comforting zero off an empty read.
  if (ba as i64) == 0 { tv_puts("TREEDIVERGE REFUSED: cannot read manifest A\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 }
  if (bb as i64) == 0 { tv_puts("TREEDIVERGE REFUSED: cannot read manifest B\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 }
  if na[0] <= 0 { tv_puts("TREEDIVERGE REFUSED: manifest A is EMPTY -- a comparator that read nothing must not print zero divergence\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 }
  if nb[0] <= 0 { tv_puts("TREEDIVERGE REFUSED: manifest B is EMPTY -- a comparator that read nothing must not print zero divergence\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 }
209
  tv_head = sys_mmap(8 * TV_HBUCKETS) as *i64
  tv_keyp = sys_mmap(8 * TV_MAXENT) as *i64
  tv_size = sys_mmap(8 * TV_MAXENT) as *i64
  tv_next = sys_mmap(8 * TV_MAXENT) as *i64
  tv_seen = sys_mmap(8 * TV_MAXENT) as *i64
  var h: i64 = 0
  while h < TV_HBUCKETS { tv_head[h] = 0 - 1; h = h + 1 }
217
  let bn: i64 = tv_index(bb, nb[0])
219
  tv_puts("=== nx_treediverge  " as *u8); tv_puts(la); tv_puts(" vs " as *u8); tv_puts(lb); tv_puts(" ===\n" as *u8)
221
  var same: i64 = 0
  var aahead: i64 = 0
  var bahead: i64 = 0
  var aonly: i64 = 0
  var an: i64 = 0
  let szp: *i64 = sys_mmap(16) as *i64
  var i: i64 = 0
  var ls: i64 = 0
  let nn: i64 = na[0]
  while i < nn {
      if ba[i] == (10 as u8) {
          let rel: *u8 = tv_parse(ba, ls, i, szp)
          if (rel as i64) != 0 {
              an = an + 1
              let e: i64 = tv_find(rel)
              if e < 0 { aonly = aonly + 1; tv_emit("A-ONLY " as *u8, rel, szp[0], 0 - 1) }
              else {
                  tv_seen[e] = 1
                  let bs: i64 = tv_size[e]
                  if szp[0] == bs { same = same + 1 }
                  else { if szp[0] > bs { aahead = aahead + 1; tv_emit("A-AHEAD" as *u8, rel, szp[0], bs) } else { bahead = bahead + 1; tv_emit("B-AHEAD" as *u8, rel, szp[0], bs) } }
              }
          }
          ls = i + 1
      }
      i = i + 1
  }
  var bonly: i64 = 0
  var e2: i64 = 0
  while e2 < bn { if tv_seen[e2] == 0 { bonly = bonly + 1; tv_emit("B-ONLY " as *u8, tv_keyp[e2] as *u8, 0 - 1, tv_size[e2]) } e2 = e2 + 1 }
252
  tv_puts("\n--- ENVELOPE ---\n" as *u8)
  tv_puts("rows_" as *u8); tv_puts(la); tv_puts("="  as *u8); tv_putn(an); tv_puts("  rows_" as *u8); tv_puts(lb); tv_puts("=" as *u8); tv_putn(bn); tv_puts("\n" as *u8)
  tv_puts("same=" as *u8); tv_putn(same)
  tv_puts("  " as *u8); tv_puts(la); tv_puts("_ahead=" as *u8); tv_putn(aahead)
  tv_puts("  " as *u8); tv_puts(lb); tv_puts("_ahead=" as *u8); tv_putn(bahead)
  tv_puts("  " as *u8); tv_puts(la); tv_puts("_only=" as *u8); tv_putn(aonly)
  tv_puts("  " as *u8); tv_puts(lb); tv_puts("_only=" as *u8); tv_putn(bonly)
  tv_puts("\n" as *u8)
  let div: i64 = aahead + bahead + aonly + bonly
  tv_puts("divergent=" as *u8); tv_putn(div); tv_puts("\n" as *u8)
263
  // A PARTITION IS A CLAIM: CHECK THAT THE PARTS SUM, AND PRINT THE CHECK RATHER THAN LEAVING THE
  // READER TO DO THE ARITHMETIC. MEASURED 2026-08-16 on the live laptop-vs-nas run: the A side
  // reconciled exactly (15816+1178+1679+136 = 18809 = rows_laptop) while the B side came up TWO short
  // of rows_nas. Nobody had noticed, because nothing printed the sum -- and an unexplained residual is
  // a leak, not a rounding. Every shared bucket is counted on BOTH sides; only the *_only buckets differ.
  let suma: i64 = same + aahead + bahead + aonly
  let sumb: i64 = same + aahead + bahead + bonly
  tv_puts("partition_" as *u8); tv_puts(la); tv_puts("=" as *u8); tv_putn(suma)
  tv_puts("/" as *u8); tv_putn(an)
  tv_puts("  partition_" as *u8); tv_puts(lb); tv_puts("=" as *u8); tv_putn(sumb)
  tv_puts("/" as *u8); tv_putn(bn)
  var recon: i64 = 0
  if suma == an { if sumb == bn { recon = 1 } }
  if recon == 1 { tv_puts("  partition=RECONCILES\n" as *u8) }
  else { tv_puts("  partition=RESIDUAL -- the parts do NOT sum to the rows scanned; duplicate relpaths in a manifest are the usual cause, and a registry with two rows for one path has no single answer\n" as *u8) }
279
  // ROWS, NOT BYTES. The non-vacuity guard at the top of main asks "did I READ anything?"; this asks
  // the question that actually decides the verdict: "did I PARSE anything?".
  // MEASURED 2026-08-16: handed treecanon_laptop_hash.mf (1,767,988 bytes, 16k+ rows) instead of
  // treecanon_laptop.mf, this organ read every byte, parsed ZERO rows -- that family is
  // `<sha> <bytes> <relpath>` while tv_parse expects `<bytes> <relpath>` -- and printed
  // verdict=CONVERGED. A caller asking "do the trees agree?" got a confident YES from a comparison
  // that examined nothing. The two manifests differ by one word in the filename, so it is a one-word
  // mistake to make, and I made it on the first attempt.
  // ★A NON-VACUITY GUARD THAT MEASURES BYTES CANNOT SEE AN UNPARSEABLE FILE -- a file full of bytes it
  // cannot read sails straight through the check written to catch exactly this.
  // ★A COMPARATOR THAT PARSED NOTHING MUST NOT PRINT A VERDICT ABOUT ANYTHING, and CONVERGED is the
  // most dangerous thing it could say: it is the answer that ends the investigation.
  if an <= 0 {
      tv_puts("TREEDIVERGE REFUSED: parsed ZERO rows from manifest " as *u8); tv_puts(la)
      tv_puts(" -- it was readable and NON-EMPTY, so this is a FORMAT mismatch, not an empty tree.\n" as *u8)
      tv_puts("  This organ reads `<bytes> <relpath>` (nx_treediff output). The *_hash.mf family is\n" as *u8)
      tv_puts("  `<sha> <bytes> <relpath>` and belongs to a different reader.\nverdict=REFUSED\n" as *u8)
      sys_exit(3); return 3
  }
  if bn <= 0 {
      tv_puts("TREEDIVERGE REFUSED: parsed ZERO rows from manifest " as *u8); tv_puts(lb)
      tv_puts(" -- it was readable and NON-EMPTY, so this is a FORMAT mismatch, not an empty tree.\n" as *u8)
      tv_puts("  Expected `<bytes> <relpath>` (nx_treediff output).\nverdict=REFUSED\n" as *u8)
      sys_exit(3); return 3
  }
305
  // ★THE VERDICT THAT MATTERS: BIDIRECTIONAL means a one-way sync in EITHER direction destroys work.
  if aahead > 0 { if bahead > 0 {
      tv_puts("verdict=BIDIRECTIONAL -- NEITHER TREE IS A SUPERSET. A one-way sync in EITHER direction DESTROYS WORK; merge per-file, never push wholesale.\n" as *u8)
      sys_exit(1); return 1
  } }
  if div == 0 { tv_puts("verdict=CONVERGED -- byte-identical on every shared path (a FLOOR: equal size is not proof of equal content)\n" as *u8); sys_exit(0); return 0 }
  if bahead == 0 { if bonly == 0 { tv_puts("verdict=A-SUPERSET -- safe to sync A->B\n" as *u8); sys_exit(0); return 0 } }
  if aahead == 0 { if aonly == 0 { tv_puts("verdict=B-SUPERSET -- safe to sync B->A\n" as *u8); sys_exit(0); return 0 } }
  tv_puts("verdict=DIVERGENT-ONE-WAY -- one side leads on content but the other has unique paths; reconcile the *_only lists before syncing.\n" as *u8)
  sys_exit(1)
  return 1
317}
nx_treediverge.nx source

`nx_treediverge.nx` source
