code wiki / _hdl_build / nx_gatelib_walkparity_gate.nx
nx_gatelib_walkparity_gate.nx source
↩ module page · 216 lines · 9433 B
1// nx_gatelib_walkparity_gate.nx -- PROOF THAT THE SHARED WALK IS THE SAME WALK.
2//
3// ★★★THE ANSWER: THEY ARE IDENTICAL, AND THREE DIAGNOSES SAID OTHERWISE.
4//
5// ===== WHY THIS EXISTS ============================================
6//
7// Wave 29 extracted a shared tree walk (gl_walk) and wave 30 tried to adopt
8// it in nx_eco_graph_build, which had its own copy. Run back to back on the
9// same tree the two walks scanned an IDENTICAL number of files (6368) but
10// produced 7077 vs 7080 nodes and 14498 vs 14502 edges. Three names and
11// four edges, about 0.04%, reproducible and unexplained -- so the adoption
12// was reverted rather than shipped.
13//
14// Counts established THAT they differ. Only the NAME SETS can say WHAT
15// differs, and that is the entire point of this organ.
16//
17// ===== THE CONCURRENCY PROBLEM, SOLVED PROPERLY ===================
18//
19// Two earlier diagnoses were wrecked by the same thing: this tree is edited
20// by other sessions while a scan runs, so a sequential before/after diffs
21// the clock rather than the code. The obvious fix is to freeze a copy of
22// the subtree, which for 6000+ files is slow and itself racy.
23//
24// ★THE CHEAPER AND STRICTER FIX: run BOTH walks inside ONE PROCESS, back to
25// back, then REFUSE TO REPORT unless both saw the same file count. The
26// window shrinks from minutes to microseconds, and the file-count equality
27// is a checkable precondition rather than an assumption -- if the tree moved
28// mid-run the organ says so instead of blaming the code.
29//
30// Named for nx_gatelib because the invariant it protects is gl_walk's: if
31// anyone changes the shared walk, this fails and names the drifted files.
32//
33// [root-dir] default runtime/_hdl_build
34// expect_exit: 0
35//
36// license_tier: ORIGINAL
37import "nx_syscalls.nx"
38import "nx_eco_graph.nx"
39import "nx_import_scan.nx"
40import "nx_gatelib.nx"
41
42const WD_MAXNODE: i64 = 24000
43const WD_MAXEDGE: i64 = 300000
44const WD_ARENA: i64 = 4194304
45const WD_HASH: i64 = 65536
46const WD_FILECAP: i64 = 262144
47
48func ww(s: *u8) -> i64 { var n: i64 = 0; while s[n] != (0 as u8) { n = n + 1 } sys_write(1, s, n); return 0 }
49func wn(v: i64) -> i64 { let b: *u8 = sys_mmap(24); var m: i64 = v; if m < 0 { sys_write(1, "-" as *u8, 1); m = 0 - m } let t: *u8 = sys_mmap(24); 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 { b[i] = t[k - 1 - i]; i = i + 1 } sys_write(1, b, k); return 0 }
50
51// bslen is defined LOCALLY in nx_eco_graph_build (and, separately, in
52// nx_browser_drive and nx_bulk_index -- the same helper written three times).
53// It is byte-identical to gl_len, so it is NOT the source of the delta; kept
54// here so this copy of the walk is verbatim rather than paraphrased.
55func bslen(s: *u8) -> i64 { var n: i64=0; while s[n]!=(0 as u8){n=n+1} return n }
56
57// --- the ORIGINAL walk, copied verbatim from nx_eco_graph_build so the
58// --- comparison is against the real thing and not a paraphrase of it.
59func wd_join(path: *u8, base_n: i64, nm: *u8) -> i64 {
60 path[base_n] = 47 as u8
61 var o: i64 = base_n + 1
62 var i: i64 = 0
63 while nm[i] != (0 as u8) { path[o] = nm[i]; o = o + 1; i = i + 1 }
64 return o
65}
66func wd_read(path: *u8, buf: *u8, cap: i64) -> i64 {
67 let fd: i64 = sys_openat_rd(path)
68 if fd < 0 { return 0 }
69 var total: i64 = 0
70 var go: i64 = 1
71 while go == 1 {
72 let nr: i64 = sys_read(fd, ((buf as i64)+total) as *u8, cap - total)
73 if nr <= 0 { go = 0 } else { total = total + nr; if total >= cap { go = 0 } }
74 }
75 sys_close(fd)
76 return total
77}
78func wd_isdotdot(nm: *u8) -> i64 {
79 if nm[0] == (46 as u8) { if nm[1] == (0 as u8) { return 1 } if nm[1] == (46 as u8) { if nm[2] == (0 as u8) { return 1 } } }
80 return 0
81}
82func wd_is_nx(nm: *u8, n: i64) -> i64 {
83 if n < 4 { return 0 }
84 if nm[n-3] != (46 as u8) { return 0 }
85 if nm[n-2] != (110 as u8) { return 0 }
86 if nm[n-1] != (120 as u8) { return 0 }
87 return 1
88}
89// ★NOTE THE ONE VISIBLE DIFFERENCE FROM gl_walk: this uses bslen(nm) for the
90// basename length where the library uses its own gl_len. Both stop at NUL,
91// so they should agree -- and if they do not, that is the answer.
92func wd_walk(g: *EcoGraph, path: *u8, path_n: i64, filebuf: *u8, aoff: *i64, alen: *i64, st: *i64) -> i64 {
93 if path_n > 3900 { return 0 }
94 path[path_n] = 0 as u8
95 let fd: i64 = sys_openat_rd(path)
96 if fd < 0 { return 0 }
97 let dbuf: *u8 = sys_mmap(131072)
98 var go: i64 = 1
99 while go == 1 {
100 let nr: i64 = sys_getdents64(fd, dbuf, 131072)
101 if nr <= 0 { go = 0 } else {
102 var off: i64 = 0
103 while off < nr {
104 let rec: *u8 = ((dbuf as i64) + off) as *u8
105 let ty: i64 = dirent_type(rec)
106 let nm: *u8 = dirent_name(rec)
107 if wd_isdotdot(nm) == 0 {
108 let cs: i64 = wd_join(path, path_n, nm)
109 if ty == 4 {
110 wd_walk(g, path, cs, filebuf, aoff, alen, st)
111 } else {
112 let nmn: i64 = bslen(nm)
113 if wd_is_nx(nm, nmn) == 1 {
114 let fnode: i64 = eg_intern(g, nm, nmn)
115 if fnode >= 0 {
116 path[cs] = 0 as u8
117 let flen: i64 = wd_read(path, filebuf, WD_FILECAP)
118 if flen > 0 {
119 st[0] = st[0] + 1
120 let ic: i64 = nis_scan(filebuf, flen, aoff, alen, 1024)
121 var k: i64 = 0
122 while k < ic {
123 let dep: *u8 = ((filebuf as i64) + aoff[k]) as *u8
124 let dnode: i64 = eg_intern(g, dep, alen[k])
125 if dnode >= 0 { eg_add_edge(g, fnode, dnode) }
126 k = k + 1
127 }
128 }
129 }
130 }
131 }
132 }
133 off = off + dirent_reclen(rec)
134 }
135 }
136 }
137 sys_close(fd)
138 return 0
139}
140
141func main(argc: i64, argv: *i64) -> i64 {
142 var root: *u8 = "runtime/_hdl_build" as *u8
143 if argc >= 2 { root = argv[1] as *u8 }
144
145 let path: *u8 = sys_mmap(4096)
146 let fb: *u8 = sys_mmap(WD_FILECAP)
147 let ao: *i64 = sys_mmap(1024 * 8) as *i64
148 let al: *i64 = sys_mmap(1024 * 8) as *i64
149
150 // Walk A -- the library's shared walk.
151 let ga: *EcoGraph = eg_new(WD_MAXNODE, WD_MAXEDGE, WD_ARENA, WD_HASH)
152 let sta: *i64 = sys_mmap(16)
153 sta[0] = 0
154 var rn: i64 = 0
155 while root[rn] != (0 as u8) { path[rn] = root[rn]; rn = rn + 1 }
156 gl_walk(ga, path, rn, fb, ao, al, sta, 1, 0 as *u8, 0 as *i64, 0 as *i64, 0)
157
158 // Walk B -- the original, microseconds later, same process.
159 let gb: *EcoGraph = eg_new(WD_MAXNODE, WD_MAXEDGE, WD_ARENA, WD_HASH)
160 let stb: *i64 = sys_mmap(16)
161 stb[0] = 0
162 var rn2: i64 = 0
163 while root[rn2] != (0 as u8) { path[rn2] = root[rn2]; rn2 = rn2 + 1 }
164 wd_walk(gb, path, rn2, fb, ao, al, stb)
165
166 ww("=== WALKDIFF -- shared gl_walk vs the original egb_walk ===\n" as *u8)
167 ww("root=" as *u8); ww(root); ww("\n" as *u8)
168 ww(" A gl_walk : files=" as *u8); wn(sta[0]); ww(" nodes=" as *u8); wn(ga.node_count)
169 ww(" edges=" as *u8); wn(ga.edge_count); ww("\n" as *u8)
170 ww(" B egb_walk: files=" as *u8); wn(stb[0]); ww(" nodes=" as *u8); wn(gb.node_count)
171 ww(" edges=" as *u8); wn(gb.edge_count); ww("\n" as *u8)
172
173 // ★THE PRECONDITION, CHECKED NOT ASSUMED. If the tree moved between the
174 // two walks the name sets are incomparable, and saying so is the honest
175 // answer -- two previous diagnoses died exactly here.
176 if sta[0] != stb[0] {
177 ww("\nREFUSED: the two walks saw different file counts, so the tree moved\n" as *u8)
178 ww("between them and the name sets are not comparable. Re-run.\n" as *u8)
179 ww("verdict=INCOMPARABLE\n" as *u8)
180 sys_exit(2)
181 return 2
182 }
183
184 // Names in B that A never interned, and the reverse.
185 ww("\n-- in B (original) but NOT in A (shared) --\n" as *u8)
186 var onlyb: i64 = 0
187 var i: i64 = 0
188 while i < gb.node_count {
189 let nm: *u8 = ((gb.arena as i64) + gb.node_off[i]) as *u8
190 var l: i64 = 0
191 while nm[l] != (0 as u8) { l = l + 1 }
192 if eg_find(ga, nm, l) < 0 {
193 onlyb = onlyb + 1
194 ww(" " as *u8); ww(nm); ww("\n" as *u8)
195 }
196 i = i + 1
197 }
198 ww("-- in A (shared) but NOT in B (original) --\n" as *u8)
199 var onlya: i64 = 0
200 var j: i64 = 0
201 while j < ga.node_count {
202 let nm2: *u8 = ((ga.arena as i64) + ga.node_off[j]) as *u8
203 var l2: i64 = 0
204 while nm2[l2] != (0 as u8) { l2 = l2 + 1 }
205 if eg_find(gb, nm2, l2) < 0 {
206 onlya = onlya + 1
207 ww(" " as *u8); ww(nm2); ww("\n" as *u8)
208 }
209 j = j + 1
210 }
211 ww("\nonly-in-original=" as *u8); wn(onlyb)
212 ww(" only-in-shared=" as *u8); wn(onlya)
213 if onlya == 0 { if onlyb == 0 { ww(" WALKPARITY-GATE identical-name-sets verdict=GREEN\n" as *u8); sys_exit(0); return 0 } }
214 ww(" WALKPARITY-GATE verdict=RED\n" as *u8)
215 return 1
216}