nx_treehash.nx source
↩ module page · 311 lines · 15034 B
1// nx_treehash.nx -- CROSS-TREE CONTENT-IDENTITY MANIFEST. The hash half of nx_treediff.
2//
3// THE GAP IT CLOSES (measured 2026-08-06, tree-canon-single-writer lane):
4// nx_treediff emits `<bytes> <relpath>` and nx_treediverge compares those SIZES. Both organs say
5// so honestly in their own output -- treediff prints "size is a SCREEN, not proof of identity" and
6// treediverge's usage line says "(by BYTES, a FLOOR)". They were right, and they were built that
7// way for a stated reason: "it needs no hash primitive on either side."
8// THAT REASON EXPIRED. nx_sha256.nx has shipped the whole time and nx_filehash wired it to a PATH.
9// Meanwhile the hourly treediverge beat reported divergent=5943 for days while a content-level
10// census of the same two trees reported 17,164 of 17,579. Both numbers were honest measurements of
11// DIFFERENT THINGS: 5,943 files differ in LENGTH; the rest differ in BYTES AT EQUAL LENGTH, which a
12// size screen cannot see by construction.
13// => A SCREEN THAT DOCUMENTS ITS OWN FLOOR STILL GETS READ AS A TOTAL ONCE IT IS WIRED TO A BEAT.
14// The trend log made a floor look like a burn-down. This organ removes the excuse: content identity
15// is now as cheap to measure as length, so nothing has to infer identity from size again.
16//
17// DESIGN: same walker, same caps, same in-band envelope as nx_treediff -- deliberately, so the two
18// manifests are directly comparable and this organ inherits a proven traversal rather than a new one.
19// The row is a STRICT SUPERSET of treediff's: `<sha256-64hex> <bytes> <relpath>`, so a consumer can
20// still do the cheap size compare AND the exact content compare from one file.
21//
22// *UNREADABLE IS NEVER A HASH. nx_filehash banked the law: a hasher that digests an empty buffer for
23// a missing file emits a real-looking 64-hex answer for a file that does not exist. Here an unreadable
24// file emits 64 '-' (fixed width, cannot collide with hex, never equal to itself) and is COUNTED in
25// the envelope, so a permission error can never masquerade as convergence.
26//
27// *MEMORY IS THE REAL RISK AND IT IS FREED EXPLICITLY. Hashing means READING EVERY FILE'S BYTES --
28// the exact shape of the leak class this estate has been bitten by repeatedly (the unfreed per-call
29// mmap that took 28.5GB of a 36GB host, and nx_treediff's own per-entry path buffers). Every mmap
30// here is matched by a munmap. THE SUBTLE ONE: sys_read_file reserves `filesize+16`, but for a file
31// whose lseek(END) is 0 it falls back to a 4 GiB reservation -- so a zero-byte .nx freed as "0+16"
32// would leak 4 GiB of address space per occurrence and hit RLIMIT_AS. That case is freed at its true
33// reserved size.
34//
35// DIALECT: plain-if, no empty literals, <=6 params, consts above use.
36// license_tier: ORIGINAL expect_exit: 0 No hw writes (Rule 26).
37import "nx_syscalls.nx"
38import "nx_sha256.nx"
39
40const TH_MAX_FILES: i64 = 40000 // upper bound on emitted rows; declared, never silent
41const TH_MAX_DEPTH: i64 = 8 // recursion depth cap
42const TH_PATH_CAP: i64 = 1024
43const TH_DIRENT_BUF: i64 = 65536
44const TH_OUTBUF: i64 = 8388608 // 8 MiB (~20k rows x ~130B, with headroom)
45const TH_DIGEST_BYTES: i64 = 32
46const TH_HEX_CHARS: i64 = 64
47const TH_NUMBUF: i64 = 64
48// sys_read_file's fallback reservation when lseek(END) reports 0 (empty/special files).
49const TH_EMPTY_RESERVE: i64 = 4294967296
50
51static th_count: *i64 // [0]=rows [1]=dirs [2]=cap_hit [3]=outbuf_full [4]=unreadable
52static th_out: *u8
53static th_out_n: *i64
54static th_num: *u8 // reusable digit scratch (allocated ONCE, never per row)
55static th_rev: *u8
56static th_dig: *u8 // reusable 32-byte digest sink
57static th_hex: *u8 // reusable 64-char hex sink
58
59func th_puts(s: *u8) -> i64 {
60 var n: i64 = 0
61 while s[n] != (0 as u8) { n = n + 1 }
62 sys_write(1, s, n)
63 return 0
64}
65func th_putn(v: i64) -> i64 {
66 var m: i64 = v
67 if m == 0 { th_num[0] = 48 as u8; sys_write(1, th_num, 1); return 0 }
68 if m < 0 { th_puts("-" as *u8); m = 0 - m }
69 var k: i64 = 0
70 while m > 0 { th_rev[k] = (48 + (m % 10)) as u8; m = m / 10; k = k + 1 }
71 var i: i64 = 0
72 while i < k { th_num[i] = th_rev[k - 1 - i]; i = i + 1 }
73 sys_write(1, th_num, k)
74 return 0
75}
76func th_cat(d: *u8, o: i64, s: *u8) -> i64 {
77 var a: i64 = o
78 var i: i64 = 0
79 while s[i] != (0 as u8) { d[a] = s[i]; a = a + 1; i = i + 1 }
80 d[a] = 0 as u8
81 return a
82}
83// SCOPE IS AN ARGUMENT, NOT A CONSTANT. The extension was hardcoded to "nx", which silently made the
84// estate's only CONTENT-IDENTITY instrument unable to answer any question about the knowledge/ data
85// plane -- and it answered files=0 rather than refusing, which reads as "that tree is empty".
86// A HARDCODED FILTER IS A CAPABILITY CEILING WEARING THE COSTUME OF A DEFAULT: the caller cannot see
87// it, cannot change it, and gets a confident zero. Measured 2026-08-16: asking whether
88// knowledge/compare and buildroot/knowledge/compare had diverged was unanswerable by this organ, and
89// the two empty manifests it produced made nx_hashdiverge certify CONVERGED.
90// The default stays "nx" so every existing caller's contract is unchanged (rule 19).
91static th_ext: *u8
92static th_extn: i64
93func th_ends_ext(nm: *u8) -> i64 {
94 var n: i64 = 0
95 while nm[n] != (0 as u8) { n = n + 1 }
96 if n < th_extn + 1 { return 0 }
97 if nm[n - th_extn - 1] != (46 as u8) { return 0 }
98 var i: i64 = 0
99 while i < th_extn {
100 if nm[n - th_extn + i] != th_ext[i] { return 0 }
101 i = i + 1
102 }
103 return 1
104}
105
106// digest -> lowercase hex in th_hex. No allocation.
107func th_digest_hex(d: *u8) -> i64 {
108 var i: i64 = 0
109 while i < TH_DIGEST_BYTES {
110 let v: i64 = d[i] as i64
111 let hi: i64 = (v >> 4) & 15
112 let lo: i64 = v & 15
113 if hi < 10 { th_hex[i*2] = (48+hi) as u8 } else { th_hex[i*2] = (87+hi) as u8 }
114 if lo < 10 { th_hex[i*2+1] = (48+lo) as u8 } else { th_hex[i*2+1] = (87+lo) as u8 }
115 i = i + 1
116 }
117 return 0
118}
119// *A SENTINEL THAT CANNOT BE MISTAKEN FOR A DIGEST: 64 dashes are not hex, so no comparer can ever
120// read an unreadable file as matching anything -- including another unreadable file.
121func th_hex_unreadable() -> i64 {
122 var i: i64 = 0
123 while i < TH_HEX_CHARS { th_hex[i] = 45 as u8; i = i + 1 }
124 return 0
125}
126
127// *RETURNS THE LENGTH, -1 when unreadable, and FREES EVERY BYTE IT MAPPED.
128func th_hash_file(path: *u8, out: *u8) -> i64 {
129 let ln: *i64 = sys_mmap(16) as *i64
130 ln[0] = 0
131 let buf: *u8 = sys_read_file(path, ln)
132 if (buf as i64) == 0 { sys_munmap(ln as *u8, 16); return 0 - 1 }
133 let n: i64 = ln[0]
134 sha256_digest(buf, n, out)
135 // Free EXACTLY what sys_read_file reserved -- see the header note on the empty-file 4 GiB case.
136 if n > 0 { sys_munmap(buf, n + 16) } else { sys_munmap(buf, TH_EMPTY_RESERVE + 16) }
137 sys_munmap(ln as *u8, 16)
138 return n
139}
140
141// append "<64hex> <bytes> <relpath>\n". FAIL-CLOSED ON OVERFLOW: a full buffer sets th_count[3] so
142// the envelope reports PARTIAL rather than presenting a truncated census as a total.
143func th_row(hx: *u8, sz: i64, rel: *u8) -> i64 {
144 var k: i64 = 0
145 var m: i64 = sz
146 if m < 0 { th_num[0] = 45 as u8; k = 1; m = 0 - m }
147 if m == 0 { th_num[k] = 48 as u8; k = k + 1 }
148 var j: i64 = 0
149 while m > 0 { th_rev[j] = (48 + (m % 10)) as u8; m = m / 10; j = j + 1 }
150 while j > 0 { th_num[k] = th_rev[j - 1]; k = k + 1; j = j - 1 }
151 var rl: i64 = 0
152 while rel[rl] != (0 as u8) { rl = rl + 1 }
153 let need: i64 = TH_HEX_CHARS + 1 + k + 1 + rl + 1
154 var o: i64 = th_out_n[0]
155 if o + need >= TH_OUTBUF { th_count[3] = 1; return 0 }
156 var i: i64 = 0
157 while i < TH_HEX_CHARS { th_out[o] = hx[i]; o = o + 1; i = i + 1 }
158 th_out[o] = 32 as u8; o = o + 1
159 i = 0
160 while i < k { th_out[o] = th_num[i]; o = o + 1; i = i + 1 }
161 th_out[o] = 32 as u8; o = o + 1
162 i = 0
163 while i < rl { th_out[o] = rel[i]; o = o + 1; i = i + 1 }
164 th_out[o] = 10 as u8; o = o + 1
165 th_out_n[0] = o
166 return 0
167}
168
169func th_walk(dir: *u8, rel: *u8, depth: i64) -> i64 {
170 if depth > TH_MAX_DEPTH { th_count[2] = 1; return 0 }
171 let fd: i64 = sys_openat_rd(dir)
172 if fd < 0 { return 0 }
173 th_count[1] = th_count[1] + 1
174 let buf: *u8 = sys_mmap(TH_DIRENT_BUF)
175 var go: i64 = 1
176 while go == 1 {
177 let n: i64 = sys_getdents64(fd, buf, TH_DIRENT_BUF)
178 if n <= 0 { go = 0 }
179 if n > 0 {
180 var off: i64 = 0
181 while off < n {
182 // the dirent_* helpers take the RECORD POINTER, not (buf, offset).
183 let rec: *u8 = ((buf as i64) + off) as *u8
184 let rl: i64 = dirent_reclen(rec)
185 let ty: i64 = dirent_type(rec)
186 let nm: *u8 = dirent_name(rec)
187 var skip: i64 = 0
188 if nm[0] == (46 as u8) { skip = 1 } // . .. and dotfiles
189 if skip == 0 {
190 let sub: *u8 = sys_mmap(TH_PATH_CAP)
191 var o: i64 = th_cat(sub, 0, dir)
192 o = th_cat(sub, o, "/" as *u8)
193 o = th_cat(sub, o, nm)
194 let srel: *u8 = sys_mmap(TH_PATH_CAP)
195 var r: i64 = th_cat(srel, 0, rel)
196 if rel[0] != (0 as u8) { r = th_cat(srel, r, "/" as *u8) }
197 r = th_cat(srel, r, nm)
198 if ty == 4 { th_walk(sub, srel, depth + 1) }
199 if ty != 4 {
200 if th_ends_ext(nm) == 1 {
201 if th_count[0] >= TH_MAX_FILES { th_count[2] = 1 } else {
202 let sz: i64 = th_hash_file(sub, th_dig)
203 if sz < 0 {
204 th_hex_unreadable()
205 th_count[4] = th_count[4] + 1
206 th_row(th_hex, 0 - 1, srel)
207 }
208 if sz >= 0 {
209 th_digest_hex(th_dig)
210 th_row(th_hex, sz, srel)
211 }
212 th_count[0] = th_count[0] + 1
213 }
214 }
215 }
216 // per-entry buffers are freed HERE -- 18k files x 2 x 4KiB is not a rounding error.
217 sys_munmap(sub, TH_PATH_CAP)
218 sys_munmap(srel, TH_PATH_CAP)
219 }
220 off = off + rl
221 }
222 }
223 }
224 sys_close(fd)
225 sys_munmap(buf, TH_DIRENT_BUF)
226 return 0
227}
228
229func main(argc: i64, argv: *i64) -> i64 {
230 th_num = sys_mmap(TH_NUMBUF)
231 th_rev = sys_mmap(TH_NUMBUF)
232 if argc < 2 {
233 th_puts("usage: nx_treehash <dir> [outfile] -- '<sha256-64hex> <bytes> <relpath>' per .nx file.\n" as *u8)
234 th_puts(" CONTENT identity, not the size SCREEN that nx_treediff emits. With [outfile] the\n" as *u8)
235 th_puts(" manifest is WRITTEN THERE (read it back with nx_fs) and stdout carries only the\n" as *u8)
236 th_puts(" envelope, so a transport payload cap can never bound coverage.\n" as *u8)
237 th_puts(" An UNREADABLE file emits 64 '-' and is counted -- never a plausible-looking hash.\n" as *u8)
238 sys_exit(2)
239 return 2
240 }
241 th_count = sys_mmap(64) as *i64
242 th_count[0] = 0
243 th_count[1] = 0
244 th_count[2] = 0
245 th_count[3] = 0
246 th_count[4] = 0
247 th_out_n = sys_mmap(16) as *i64
248 th_out_n[0] = 0
249 th_dig = sys_mmap(TH_DIGEST_BYTES + 8)
250 th_hex = sys_mmap(TH_HEX_CHARS + 8)
251 var outp: *u8 = 0 as *u8
252 if argc > 2 { outp = argv[2] as *u8; th_out = sys_mmap(TH_OUTBUF) }
253 if (th_out as i64) == 0 {
254 th_puts("# TREEHASH RED -- an outfile is required (a 20k-row hash manifest must never ride stdout)\n" as *u8)
255 sys_exit(2)
256 return 2
257 }
258 // Optional 3rd arg = the extension to hash, WITHOUT the dot ("matrix", "conf", "verdict").
259 // Absent -> "nx", which is what every existing caller passes today, so their behaviour is byte-identical.
260 th_ext = "nx" as *u8
261 th_extn = 2
262 if argc > 3 {
263 th_ext = argv[3] as *u8
264 var e: i64 = 0
265 while th_ext[e] != (0 as u8) { e = e + 1 }
266 th_extn = e
267 }
268 if th_extn <= 0 {
269 th_puts("# TREEHASH RED -- empty extension: a scope that matches nothing would report files=0 as if the tree were empty\n" as *u8)
270 sys_exit(2)
271 return 2
272 }
273 let root: *u8 = argv[1] as *u8
274 th_walk(root, "" as *u8, 0)
275 let fd: i64 = sys_openat_wr(outp, 0x1a4)
276 if fd < 0 {
277 th_puts("# TREEHASH RED -- cannot open outfile: " as *u8); th_puts(outp); th_puts("\n" as *u8)
278 sys_exit(3); return 3
279 }
280 sys_write(fd, th_out, th_out_n[0])
281 sys_close(fd)
282 th_puts("# manifest written: " as *u8); th_puts(outp)
283 th_puts(" bytes=" as *u8); th_putn(th_out_n[0]); th_puts("\n" as *u8)
284 // ENVELOPE IN-BAND: a scanner that hides its coverage presents a floor as a total (law L011).
285 // THE SCOPE IS PART OF THE ANSWER. This walker hashes *.nx ONLY (th_ends_nx), so a tree of
286 // .matrix / .conf / .verdict files yields files=0 -- which is CORRECT, and which read as "that
287 // tree is empty" to me on 2026-08-16 because the envelope never said what it was looking for.
288 // A count printed without its filter is an invitation to misread it as a population.
289 // Measured cost: two zero-row manifests fed to nx_hashdiverge produced a confident
290 // "verdict=CONVERGED (every path present in both trees is byte-identical)" about two trees from
291 // which no file had been read. Naming the scope here is the cheap half of that fix; the third
292 // verdict state in nx_hashdiverge is the half that refuses.
293 th_puts("# TREEHASH-MANIFEST scope=*." as *u8); th_puts(th_ext); th_puts(" files=" as *u8); th_putn(th_count[0])
294 if th_count[0] == 0 { th_puts(" (ZERO FILES MATCHED THAT SCOPE -- this is not an empty tree, it is an empty FILTER RESULT)" as *u8) }
295 th_puts(" dirs=" as *u8); th_putn(th_count[1])
296 th_puts(" unreadable=" as *u8); th_putn(th_count[4])
297 th_puts(" file_cap=" as *u8); th_putn(TH_MAX_FILES)
298 th_puts(" depth_cap=" as *u8); th_putn(TH_MAX_DEPTH)
299 th_puts(" cap_hit=" as *u8); th_putn(th_count[2])
300 th_puts(" outbuf_full=" as *u8); th_putn(th_count[3])
301 var partial: i64 = 0
302 if th_count[2] == 1 { partial = 1 }
303 if th_count[3] == 1 { partial = 1 }
304 if partial == 1 { th_puts(" verdict=PARTIAL (coverage truncated -- raise a cap deliberately, never read this as a total)" as *u8) }
305 if partial == 0 { th_puts(" verdict=COMPLETE" as *u8) }
306 th_puts("\n# NOTE: sha256 is PROOF of identity, not a screen. Equal hash = equal bytes. This retires\n" as *u8)
307 th_puts("# the 'equal sizes can still differ' blind spot that let a size-screen beat report a floor\n" as *u8)
308 th_puts("# as a burn-down for days.\n" as *u8)
309 sys_exit(0)
310 return 0
311}