nx_depcycle.nx source

1// nx_depcycle.nx -- ACYCLIC DEPENDENCIES PRINCIPLE checker (industry SOTA, grounded in nishi research: 2// corpus confirms Coupling / Cohesion / Dependency-inversion / Clean-architecture as the canon). Reads 3// the ecosystem IMPORT GRAPH (the atlas edges) and finds circular dependencies: A imports B imports ... 4// imports A. Cycles are the top structural smell -- organs in a cycle can't be built / understood / tested 5// / reused independently, blocking modular OO design (Robert Martin, "Clean Architecture", ADP). Uses 6// KAHN topological reduction (iterative, no recursion): repeatedly remove zero-in-degree nodes; whatever 7// remains with in-degree>0 is trapped in a cycle = the ADP-violation set. Deterministic. 8// argv: <dir> [dir2...] 9// Report: CYCLENODE <basename> (each node still trapped after reduction), then 10// NX-DEPCYCLE nodes=N edges=E cyclic=C verdict=ACYCLIC|CYCLIC-C 11// exit 0 = ran. license_tier: ORIGINAL No hw writes (Rule 26). 12import "nx_seat_drive_lib.nx" 13import "nx_deploy_lib.nx" 14import "nx_syscalls.nx" 15const DC_MAGIC_262144: i64 = 262144 16const DC_MAGIC_1024: i64 = 1024 17 18const DC_MAXN: i64 = 30000 19const DC_MAXE: i64 = 200000 20const DC_NB: i64 = 65536 21const DC_NAMEBUF: i64 = 3145728 22const DC_FILECAP: i64 = 2097152 23const DC_FNV_OFF: i64 = 1469598103934665603 24const DC_FNV_PRIME: i64 = 1099511628211 25 26func dc_isid(c: i64) -> i64 { 27 if c >= 97 { if c <= 122 { return 1 } } 28 if c >= 65 { if c <= 90 { return 1 } } 29 if c >= 48 { if c <= 57 { return 1 } } 30 if c == 95 { return 1 } 31 if c == 46 { return 1 } 32 return 0 33} 34func dc_ends_nx(nm: *u8) -> i64 { 35 var n: i64 = 0 36 while nm[n] != (0 as u8) { n = n + 1 } 37 if n < 3 { return 0 } 38 if nm[n-3] == (46 as u8) { if nm[n-2] == (110 as u8) { if nm[n-1] == (120 as u8) { return 1 } } } 39 return 0 40} 41func dc_fnv(buf: *u8, s: i64, e: i64) -> i64 { 42 var h: i64 = DC_FNV_OFF 43 var i: i64 = s 44 while i < e { h = h ^ (buf[i] as i64); h = h * DC_FNV_PRIME; i = i + 1 } 45 return h 46} 47 48// globals for the node map (module statics defined ABOVE use per fwd-const law) 49static g_nbuf: *u8 50static g_noff: *i64 51static g_nlen: *i64 52static g_bhead: *i64 53static g_bnext: *i64 54static g_nb: *i64 55static g_nn: *i64 56 57func dc_streq(buf: *u8, s: i64, l: i64, name: *u8, no: i64, nl: i64) -> i64 { 58 if l != nl { return 0 } 59 var i: i64 = 0 60 while i < l { if buf[s+i] != name[no+i] { return 0 } i = i + 1 } 61 return 1 62} 63// find-or-insert basename[s..e) from src into the node map; returns node index 64func dc_intern(src: *u8, s: i64, e: i64) -> i64 { 65 let l: i64 = e - s 66 let h: i64 = dc_fnv(src, s, e) 67 let b: i64 = h & (DC_NB - 1) 68 var p: i64 = g_bhead[b] 69 while p >= 0 { 70 if dc_streq(g_nbuf, g_noff[p], g_nlen[p], src, s, l) == 1 { return p } 71 p = g_bnext[p] 72 } 73 // insert 74 let idx: i64 = g_nn[0] 75 if idx >= DC_MAXN { return 0 - 1 } 76 let no: i64 = g_nb[0] 77 if no + l + 1 >= DC_NAMEBUF { return 0 - 1 } 78 g_noff[idx] = no 79 g_nlen[idx] = l 80 var w: i64 = 0 81 while w < l { g_nbuf[no + w] = src[s + w]; w = w + 1 } 82 g_nb[0] = no + l 83 g_bnext[idx] = g_bhead[b] 84 g_bhead[b] = idx 85 g_nn[0] = idx + 1 86 return idx 87} 88// find only (no insert); -1 if absent 89func dc_find(src: *u8, s: i64, e: i64) -> i64 { 90 let l: i64 = e - s 91 let h: i64 = dc_fnv(src, s, e) 92 let b: i64 = h & (DC_NB - 1) 93 var p: i64 = g_bhead[b] 94 while p >= 0 { 95 if dc_streq(g_nbuf, g_noff[p], g_nlen[p], src, s, l) == 1 { return p } 96 p = g_bnext[p] 97 } 98 return 0 - 1 99} 100 101func main(argc: i64, argv: *i64) -> i64 { 102 if argc < 2 { sd_w("usage: nx_depcycle <dir> [dir2...]\n" as *u8); sys_exit(2); return 2 } 103 g_nbuf = sys_mmap(DC_NAMEBUF) 104 g_noff = sys_mmap(8 * DC_MAXN) as *i64 105 g_nlen = sys_mmap(8 * DC_MAXN) as *i64 106 g_bhead = sys_mmap(8 * DC_NB) as *i64 107 g_bnext = sys_mmap(8 * DC_MAXN) as *i64 108 g_nb = sys_mmap(16) as *i64 109 g_nn = sys_mmap(16) as *i64 110 g_nb[0] = 0 111 g_nn[0] = 0 112 var bi: i64 = 0 113 while bi < DC_NB { g_bhead[bi] = 0 - 1; bi = bi + 1 } 114 115 // edges: src->dst arrays + per-node out-adjacency linked list + in-degree 116 let esrc: *i64 = sys_mmap(8 * DC_MAXE) as *i64 117 let edst: *i64 = sys_mmap(8 * DC_MAXE) as *i64 118 var ne: i64 = 0 119 let src: *u8 = sys_mmap(DC_FILECAP) 120 let dbuf: *u8 = sys_mmap(DC_MAGIC_262144) 121 122 // PASS 1: register all .nx basenames as nodes 123 var d: i64 = 1 124 while d < argc { 125 let dir: *u8 = argv[d] as *u8 126 let dfd: i64 = sys_openat_rd(dir) 127 if dfd >= 0 { 128 var go: i64 = 1 129 while go == 1 { 130 let dn: i64 = sys_getdents64(dfd, dbuf, DC_MAGIC_262144) 131 if dn <= 0 { go = 0 } else { 132 var off: i64 = 0 133 while off < dn { 134 let rec: *u8 = ((dbuf as i64) + off) as *u8 135 let ty: i64 = dirent_type(rec) 136 let nm: *u8 = dirent_name(rec) 137 if ty != 4 { if dc_ends_nx(nm) == 1 { 138 var l: i64 = 0 139 while nm[l] != (0 as u8) { l = l + 1 } 140 dc_intern(nm, 0, l) 141 } } 142 off = off + dirent_reclen(rec) 143 } 144 } 145 } 146 sys_close(dfd) 147 } 148 d = d + 1 149 } 150 151 // PASS 2: for each file, parse import "Y.nx" -> edge (thisnode -> Ynode) 152 d = 1 153 while d < argc { 154 let dir: *u8 = argv[d] as *u8 155 let dfd: i64 = sys_openat_rd(dir) 156 if dfd >= 0 { 157 var go: i64 = 1 158 while go == 1 { 159 let dn: i64 = sys_getdents64(dfd, dbuf, DC_MAGIC_262144) 160 if dn <= 0 { go = 0 } else { 161 var off: i64 = 0 162 while off < dn { 163 let rec: *u8 = ((dbuf as i64) + off) as *u8 164 let ty: i64 = dirent_type(rec) 165 let nm: *u8 = dirent_name(rec) 166 if ty != 4 { if dc_ends_nx(nm) == 1 { 167 var nl: i64 = 0 168 while nm[nl] != (0 as u8) { nl = nl + 1 } 169 let selfnode: i64 = dc_find(nm, 0, nl) 170 // read file, scan for import "..." 171 let p: *u8 = sys_mmap(DC_MAGIC_1024) 172 var po: i64 = 0 173 var dj: i64 = 0 174 while dir[dj] != (0 as u8) { p[po] = dir[dj]; po = po + 1; dj = dj + 1 } 175 p[po] = 47 as u8; po = po + 1 176 var mj: i64 = 0 177 while nm[mj] != (0 as u8) { p[po] = nm[mj]; po = po + 1; mj = mj + 1 } 178 p[po] = 0 as u8 179 let fd: i64 = sys_openat_rd(p) 180 if fd >= 0 { 181 var slen: i64 = 0 182 var r: i64 = sys_read(fd, src, DC_FILECAP - 1) 183 while r > 0 { slen = slen + r; if slen >= DC_FILECAP - 1 { r = 0 } else { r = sys_read(fd, src + slen, DC_FILECAP - 1 - slen) } } 184 sys_close(fd) 185 // scan for import "NAME" at line starts -> edge selfnode -> Ynode 186 var k: i64 = 0 187 while k + 8 < slen { 188 var atbol: i64 = 0 189 if k == 0 { atbol = 1 } 190 if k > 0 { if src[k-1] == (10 as u8) { atbol = 1 } } 191 if atbol == 1 { 192 var mm: i64 = 1 193 if src[k] != (105 as u8) { mm = 0 } 194 if mm == 1 { if src[k+1] != (109 as u8) { mm = 0 } } 195 if mm == 1 { if src[k+2] != (112 as u8) { mm = 0 } } 196 if mm == 1 { if src[k+3] != (111 as u8) { mm = 0 } } 197 if mm == 1 { if src[k+4] != (114 as u8) { mm = 0 } } 198 if mm == 1 { if src[k+5] != (116 as u8) { mm = 0 } } 199 if mm == 1 { if src[k+6] != (32 as u8) { mm = 0 } } 200 if mm == 1 { if src[k+7] != (34 as u8) { mm = 0 } } 201 if mm == 1 { 202 let ys: i64 = k + 8 203 var ye: i64 = ys 204 var s3: i64 = 1 205 while s3 == 1 { if ye >= slen { s3 = 0 } else { if src[ye] == (34 as u8) { s3 = 0 } else { ye = ye + 1 } } } 206 if ye > ys { 207 let dstnode: i64 = dc_find(src, ys, ye) 208 if dstnode >= 0 { if selfnode >= 0 { if selfnode != dstnode { if ne < DC_MAXE { 209 esrc[ne] = selfnode 210 edst[ne] = dstnode 211 ne = ne + 1 212 } } } } 213 } 214 } 215 } 216 k = k + 1 217 } 218 } 219 } } 220 off = off + dirent_reclen(rec) 221 } 222 } 223 } 224 sys_close(dfd) 225 } 226 d = d + 1 227 } 228 229 let nn: i64 = g_nn[0] 230 // in-degree 231 let indeg: *i64 = sys_mmap(8 * DC_MAXN) as *i64 232 var z: i64 = 0 233 while z < nn { indeg[z] = 0; z = z + 1 } 234 var ei: i64 = 0 235 while ei < ne { indeg[edst[ei]] = indeg[edst[ei]] + 1; ei = ei + 1 } 236 // out-adjacency linked list 237 let ohead: *i64 = sys_mmap(8 * DC_MAXN) as *i64 238 let onext: *i64 = sys_mmap(8 * DC_MAXE) as *i64 239 z = 0 240 while z < nn { ohead[z] = 0 - 1; z = z + 1 } 241 ei = 0 242 while ei < ne { onext[ei] = ohead[esrc[ei]]; ohead[esrc[ei]] = ei; ei = ei + 1 } 243 // KAHN: queue zero-indeg, process, decrement dst indeg 244 let queue: *i64 = sys_mmap(8 * DC_MAXN) as *i64 245 var qh: i64 = 0 246 var qt: i64 = 0 247 z = 0 248 while z < nn { if indeg[z] == 0 { queue[qt] = z; qt = qt + 1 } z = z + 1 } 249 var processed: i64 = 0 250 while qh < qt { 251 let u: i64 = queue[qh] 252 qh = qh + 1 253 processed = processed + 1 254 var e2: i64 = ohead[u] 255 while e2 >= 0 { 256 let v: i64 = edst[e2] 257 indeg[v] = indeg[v] - 1 258 if indeg[v] == 0 { queue[qt] = v; qt = qt + 1 } 259 e2 = onext[e2] 260 } 261 } 262 let cyclic: i64 = nn - processed 263 264 // report cyclic nodes (indeg>0 still) 265 z = 0 266 var shown: i64 = 0 267 while z < nn { 268 if indeg[z] > 0 { 269 if shown < 200 { 270 sd_w("CYCLENODE " as *u8) 271 sys_write(1, ((g_nbuf as i64) + g_noff[z]) as *u8, g_nlen[z]) 272 sd_w("\n" as *u8) 273 } 274 shown = shown + 1 275 } 276 z = z + 1 277 } 278 279 sd_w("NX-DEPCYCLE nodes=" as *u8) 280 let ob: *u8 = sys_mmap(64) 281 sd_num(ob, 0, nn) 282 sd_w(ob) 283 sd_w(" edges=" as *u8) 284 sd_num(ob, 0, ne) 285 sd_w(ob) 286 sd_w(" cyclic=" as *u8) 287 sd_num(ob, 0, cyclic) 288 sd_w(ob) 289 sd_w(" verdict=" as *u8) 290 if cyclic == 0 { sd_w("ACYCLIC\n" as *u8) } else { 291 sd_w("CYCLIC-" as *u8) 292 sd_num(ob, 0, cyclic) 293 sd_w(ob) 294 sd_w("\n" as *u8) 295 } 296 sys_exit(0) 297 return 0 298}