nx_treediverge.nx source

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 40func tv_puts(s: *u8) -> i64 { 41 var n: i64 = 0 42 while s[n] != (0 as u8) { n = n + 1 } 43 sys_write(1, s, n) 44 return 0 45} 46func tv_putn(v: i64) -> i64 { 47 let b: *u8 = sys_mmap(32) 48 var m: i64 = v 49 if m == 0 { b[0] = 48 as u8; sys_write(1, b, 1); return 0 } 50 if m < 0 { tv_puts("-" as *u8); m = 0 - m } 51 let t: *u8 = sys_mmap(32) 52 var k: i64 = 0 53 while m > 0 { t[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 } 54 var i: i64 = 0 55 while i < k { b[i] = t[k - 1 - i]; i = i + 1 } 56 sys_write(1, b, k) 57 return 0 58} 59 60// whole-file read; outn[0] = bytes, or -1 when the path is unreadable (REPORTED, never silently 0) 61func tv_readall(path: *u8, outn: *i64) -> *u8 { 62 let fd: i64 = sys_openat_rd(path) 63 if fd < 0 { outn[0] = 0 - 1; return 0 as *u8 } 64 let buf: *u8 = sys_mmap(TV_BUFCAP) 65 var tot: i64 = 0 66 var go: i64 = 1 67 while go == 1 { 68 let r: i64 = sys_read(fd, ((buf as i64) + tot) as *u8, TV_BUFCAP - tot - 1) 69 if r <= 0 { go = 0 } else { tot = tot + r } 70 if tot >= TV_BUFCAP - 1 { go = 0 } 71 } 72 sys_close(fd) 73 buf[tot] = 0 as u8 74 outn[0] = tot 75 return buf 76} 77 78func tv_hash(s: *u8) -> i64 { 79 var h: i64 = TV_MAGIC_5381 80 var i: i64 = 0 81 while s[i] != (0 as u8) { h = ((h * 33) + (s[i] as i64)) & 0x7fffffff; i = i + 1 } 82 return h & (TV_HBUCKETS - 1) 83} 84func tv_streq(a: *u8, b: *u8) -> i64 { 85 var i: i64 = 0 86 while a[i] != (0 as u8) { if a[i] != b[i] { return 0 } i = i + 1 } 87 if b[i] != (0 as u8) { return 0 } 88 return 1 89} 90 91// Parse one manifest line "<bytes> <relpath>" IN PLACE: NUL-terminate the relpath, return its pointer; 92// size lands in szout[0]. Returns 0 for a blank/garbled line so the caller can skip without aborting. 93// NOTE: written WITHOUT `break` on purpose -- this dialect's loop-exit idiom is a go-flag, and a 94// hand-rolled pseudo-break is exactly what span forever in the seq95ad autofix intake gate. 95func tv_parse(buf: *u8, start: i64, end: i64, szout: *i64) -> *u8 { 96 var i: i64 = start 97 var v: i64 = 0 98 var any: i64 = 0 99 var go: i64 = 1 100 while go == 1 { 101 if i >= end { go = 0 } else { 102 let c: i64 = buf[i] as i64 103 if c >= 48 { if c <= 57 { v = v * 10 + (c - 48); any = 1; i = i + 1 } else { go = 0 } } else { go = 0 } 104 } 105 } 106 if any == 0 { return 0 as *u8 } 107 if i >= end { return 0 as *u8 } 108 if buf[i] != (32 as u8) { return 0 as *u8 } 109 let p: i64 = i + 1 110 if p >= end { return 0 as *u8 } 111 buf[end] = 0 as u8 112 szout[0] = v 113 return ((buf as i64) + p) as *u8 114} 115 116// index the B manifest into the hash table; returns row count 117func tv_index(buf: *u8, n: i64) -> i64 { 118 var i: i64 = 0 119 var ls: i64 = 0 120 var cnt: i64 = 0 121 let szp: *i64 = sys_mmap(16) as *i64 122 while i < n { 123 if buf[i] == (10 as u8) { 124 if cnt < TV_MAXENT { 125 let rel: *u8 = tv_parse(buf, ls, i, szp) 126 if (rel as i64) != 0 { 127 let h: i64 = tv_hash(rel) 128 tv_keyp[cnt] = rel as i64 129 tv_size[cnt] = szp[0] 130 tv_next[cnt] = tv_head[h] 131 tv_seen[cnt] = 0 132 tv_head[h] = cnt 133 cnt = cnt + 1 134 } 135 } 136 ls = i + 1 137 } 138 i = i + 1 139 } 140 return cnt 141} 142 143// find a relpath in the B index; returns entry index or -1 144func tv_find(rel: *u8) -> i64 { 145 let h: i64 = tv_hash(rel) 146 var e: i64 = tv_head[h] 147 while e >= 0 { 148 if tv_streq(rel, tv_keyp[e] as *u8) == 1 { return e } 149 e = tv_next[e] 150 } 151 return 0 - 1 152} 153 154func tv_emit(tag: *u8, rel: *u8, a: i64, b: i64) -> i64 { 155 tv_puts(tag); tv_puts(" " as *u8); tv_puts(rel) 156 tv_puts(" a=" as *u8); tv_putn(a) 157 tv_puts(" b=" as *u8); tv_putn(b) 158 tv_puts(" delta=" as *u8); tv_putn(a - b) 159 tv_puts("\n" as *u8) 160 return 0 161} 162 163func main(argc: i64, argv: *i64) -> i64 { 164 if argc < 3 { 165 tv_puts("usage: nx_treediverge <manifestA> <manifestB> [labelA] [labelB]\n" as *u8) 166 tv_puts(" manifests come from: nx_treediff <dir> <outfile> (one per tree)\n" as *u8) 167 tv_puts(" verdicts per file: A-ONLY / B-ONLY / A-AHEAD / B-AHEAD (by BYTES, a FLOOR)\n" as *u8) 168 sys_exit(2) 169 return 2 170 } 171 let pa: *u8 = argv[1] as *u8 172 let pb: *u8 = argv[2] as *u8 173 var la: *u8 = "A" as *u8 174 var lb: *u8 = "B" as *u8 175 if argc >= 4 { la = argv[3] as *u8 } 176 if argc >= 5 { lb = argv[4] as *u8 } 177 178 let na: *i64 = sys_mmap(16) as *i64 179 let nb: *i64 = sys_mmap(16) as *i64 180 let ba: *u8 = tv_readall(pa, na) 181 let bb: *u8 = tv_readall(pb, nb) 182 // NON-VACUITY: refuse rather than report a comforting zero off an empty read. 183 if (ba as i64) == 0 { tv_puts("TREEDIVERGE REFUSED: cannot read manifest A\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 } 184 if (bb as i64) == 0 { tv_puts("TREEDIVERGE REFUSED: cannot read manifest B\nverdict=REFUSED\n" as *u8); sys_exit(3); return 3 } 185 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 } 186 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 } 187 188 tv_head = sys_mmap(8 * TV_HBUCKETS) as *i64 189 tv_keyp = sys_mmap(8 * TV_MAXENT) as *i64 190 tv_size = sys_mmap(8 * TV_MAXENT) as *i64 191 tv_next = sys_mmap(8 * TV_MAXENT) as *i64 192 tv_seen = sys_mmap(8 * TV_MAXENT) as *i64 193 var h: i64 = 0 194 while h < TV_HBUCKETS { tv_head[h] = 0 - 1; h = h + 1 } 195 196 let bn: i64 = tv_index(bb, nb[0]) 197 198 tv_puts("=== nx_treediverge " as *u8); tv_puts(la); tv_puts(" vs " as *u8); tv_puts(lb); tv_puts(" ===\n" as *u8) 199 200 var same: i64 = 0 201 var aahead: i64 = 0 202 var bahead: i64 = 0 203 var aonly: i64 = 0 204 var an: i64 = 0 205 let szp: *i64 = sys_mmap(16) as *i64 206 var i: i64 = 0 207 var ls: i64 = 0 208 let nn: i64 = na[0] 209 while i < nn { 210 if ba[i] == (10 as u8) { 211 let rel: *u8 = tv_parse(ba, ls, i, szp) 212 if (rel as i64) != 0 { 213 an = an + 1 214 let e: i64 = tv_find(rel) 215 if e < 0 { aonly = aonly + 1; tv_emit("A-ONLY " as *u8, rel, szp[0], 0 - 1) } 216 else { 217 tv_seen[e] = 1 218 let bs: i64 = tv_size[e] 219 if szp[0] == bs { same = same + 1 } 220 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) } } 221 } 222 } 223 ls = i + 1 224 } 225 i = i + 1 226 } 227 var bonly: i64 = 0 228 var e2: i64 = 0 229 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 } 230 231 tv_puts("\n--- ENVELOPE ---\n" as *u8) 232 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) 233 tv_puts("same=" as *u8); tv_putn(same) 234 tv_puts(" " as *u8); tv_puts(la); tv_puts("_ahead=" as *u8); tv_putn(aahead) 235 tv_puts(" " as *u8); tv_puts(lb); tv_puts("_ahead=" as *u8); tv_putn(bahead) 236 tv_puts(" " as *u8); tv_puts(la); tv_puts("_only=" as *u8); tv_putn(aonly) 237 tv_puts(" " as *u8); tv_puts(lb); tv_puts("_only=" as *u8); tv_putn(bonly) 238 tv_puts("\n" as *u8) 239 let div: i64 = aahead + bahead + aonly + bonly 240 tv_puts("divergent=" as *u8); tv_putn(div); tv_puts("\n" as *u8) 241 // ★THE VERDICT THAT MATTERS: BIDIRECTIONAL means a one-way sync in EITHER direction destroys work. 242 if aahead > 0 { if bahead > 0 { 243 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) 244 sys_exit(1); return 1 245 } } 246 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 } 247 if bahead == 0 { if bonly == 0 { tv_puts("verdict=A-SUPERSET -- safe to sync A->B\n" as *u8); sys_exit(0); return 0 } } 248 if aahead == 0 { if aonly == 0 { tv_puts("verdict=B-SUPERSET -- safe to sync B->A\n" as *u8); sys_exit(0); return 0 } } 249 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) 250 sys_exit(1) 251 return 1 252}