nx_dep_graph.nx source
↩ module page · 392 lines · 16262 B
1// nx_dep_graph.nx -- V2.0 P-8: directed dependency graph + Tarjan SCC.
2//
3// Sovereign port of Tarjan's 1972 strongly-connected-components algorithm
4// (Robert Tarjan, "Depth-first search and linear graph algorithms",
5// SIAM J. Computing, 1972). Linear-time O(V+E) cycle detection across
6// the substrate artifact graph.
7//
8// COMPOSES (per "avoid duplicate primitives" cardinal):
9// nx_syscalls.sys_mmap (per-instance buffer allocation)
10//
11// COMPOSED BY:
12// wiki/nx_pipeline_walker (V2.0 P-8.5; queued -- populates graph from
13// extractor_nx import lists)
14// wiki/nx_pipeline_route (V3+ /wiki/pipeline/graph view)
15// wiki/nx_artifact_store (V3+ MEANINGFUL refinement: artifact with
16// resolved imports + reverse-deps is more MEANINGFUL than orphans)
17//
18// V2.0 P-8 SCOPE:
19// - NxDepGraph: parallel-pool adjacency list (from_rowid -> list of to_rowid)
20// - nx_dep_graph_add_edge: caller-driven population
21// - nx_dep_graph_tarjan_scc: iterative Tarjan SCC (NO recursion; substrate-
22// friendly; bounded stack budget per NX_DEPG_MAX_STACK)
23// - Per-rowid SCC ID assignment (scc_id[rowid] = scc index 0..N-1)
24// - Accessors: deps / reverse-deps / scc-of / scc-size / cycle-detection
25//
26// V3+ SCOPE (TODO):
27// - Topological sort within DAG (sccs treated as supernodes)
28// - Critical-path computation (longest dep chain)
29// - Pretty-printed graphviz / mermaid emit
30// - Per-SCC quarantine recommendation (cycle = MEANINGFUL refinement
31// blocker per V2_0_PIPELINE_BOOTSTRAP §2.2)
32//
33// REFERENCE: Tarjan 1972 -- the original DFS-based algorithm. Substrate
34// implementation uses explicit work-stack + index/lowlink arrays (no
35// recursive function calls).
36//
37// Status: V2.0 P-8. 2026-05-27.
38
39import "nx_syscalls.nx"
40
41// ===== Sealed verdict surface (codes 3040-3049) =================================================
42const NX_DEPG_OK: i64 = 0
43const NX_DEPG_BAD_INPUT: i64 = 3040
44const NX_DEPG_GRAPH_FULL: i64 = 3041
45const NX_DEPG_EDGE_FULL: i64 = 3042
46const NX_DEPG_STACK_OVERFLOW: i64 = 3043
47const NX_DEPG_NOT_BUILT: i64 = 3044
48const NX_DEPG_LOOP_BUDGET: i64 = 3045
49const NX_DEPG_OUT_OF_RANGE: i64 = 3046
50
51// ===== Named constants (M7) =================================================
52const NX_DEPG_HARD_MAX_NODES: i64 = 10000
53const NX_DEPG_HARD_MAX_EDGES: i64 = 100000
54const NX_DEPG_MAX_STACK: i64 = 10000 // Tarjan work-stack cap
55const NX_DEPG_LOOP_BUDGET_CAP: i64 = 100000000
56
57// Tarjan unvisited sentinel
58const NX_DEPG_UNVISITED: i64 = 0 - 1
59
60// ===== NxDepGraph: CSR-like adjacency =================================================
61//
62// Edges stored as compressed sparse row (CSR):
63// edges_to[]: flat list of destination rowids (length = total edge count)
64// edges_from_start[from_rowid] -> first index into edges_to[]
65// edges_from_count[from_rowid] -> # of edges from from_rowid
66//
67// SCC fields filled by nx_dep_graph_tarjan_scc:
68// scc_id[rowid] = SCC index (0..scc_count-1); rowids in same SCC share id
69// scc_count = number of SCCs (== # of nodes if DAG; less if cycles exist)
70
71struct NxDepGraph {
72 // Adjacency (caller populates via add_edge during BUILD phase)
73 edges_to: *i64 // size: edges_cap
74 edges_to_used: i64 // index of next available slot
75 edges_from_start: *i64 // size: nodes_cap; -1 if no edges yet
76 edges_from_count: *i64 // size: nodes_cap
77
78 // For 2-phase build: phase 1 = count edges per from; phase 2 = fill edges_to
79 // V2.0 simpler: just append; edges_from_count tracks per-node count;
80 // edges_from_start tracks first-index; require add_edge calls grouped by from_rowid.
81 // (Caller-discipline; V3+ swaps for sort-and-finalize.)
82
83 // SCC results (filled by tarjan_scc)
84 scc_id: *i64 // size: nodes_cap; NX_DEPG_UNVISITED before tarjan
85 scc_count: i64
86 scc_built: i64 // 0 before tarjan; 1 after
87
88 // Internal Tarjan scratch (allocated by tarjan_scc)
89 tarjan_index: *i64
90 tarjan_lowlink: *i64
91 tarjan_onstack: *i64
92 tarjan_stack: *i64
93 tarjan_stack_top: i64
94
95 nodes_cap: i64
96 edges_cap: i64
97 valid: i64
98}
99
100// ===== Sealed init =================================================
101
102func nx_dep_graph_init(g: *NxDepGraph, nodes_cap: i64, edges_cap: i64) -> i64 {
103 if (g as i64) == 0 { return 0 - NX_DEPG_BAD_INPUT }
104 if nodes_cap < 1 { return 0 - NX_DEPG_BAD_INPUT }
105 if nodes_cap > NX_DEPG_HARD_MAX_NODES { return 0 - NX_DEPG_GRAPH_FULL }
106 if edges_cap < 1 { return 0 - NX_DEPG_BAD_INPUT }
107 if edges_cap > NX_DEPG_HARD_MAX_EDGES { return 0 - NX_DEPG_EDGE_FULL }
108
109 g.edges_to = (sys_mmap(edges_cap * 8)) as *i64
110 g.edges_to_used = 0
111 g.edges_from_start = (sys_mmap(nodes_cap * 8)) as *i64
112 g.edges_from_count = (sys_mmap(nodes_cap * 8)) as *i64
113 g.scc_id = (sys_mmap(nodes_cap * 8)) as *i64
114 g.scc_count = 0
115 g.scc_built = 0
116 g.tarjan_index = 0 as *i64
117 g.tarjan_lowlink = 0 as *i64
118 g.tarjan_onstack = 0 as *i64
119 g.tarjan_stack = 0 as *i64
120 g.tarjan_stack_top = 0
121
122 // Init scc_id + edges_from_start to UNVISITED / -1
123 var i: i64 = 0
124 while i < nodes_cap {
125 g.scc_id[i] = NX_DEPG_UNVISITED
126 g.edges_from_start[i] = 0 - 1
127 g.edges_from_count[i] = 0
128 i = i + 1
129 }
130
131 g.nodes_cap = nodes_cap
132 g.edges_cap = edges_cap
133 g.valid = 1
134 return NX_DEPG_OK
135}
136
137// ===== Add an edge from_rowid -> to_rowid =================================================
138//
139// CONTRACT: caller MUST group all add_edge calls per from_rowid before
140// moving on to the next from_rowid (CSR-build discipline). V3+ swaps
141// for unordered insert + sort-finalize.
142
143func nx_dep_graph_add_edge(g: *NxDepGraph, from_rowid: i64, to_rowid: i64) -> i64 {
144 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
145 if from_rowid < 0 { return 0 - NX_DEPG_BAD_INPUT }
146 if from_rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
147 if to_rowid < 0 { return 0 - NX_DEPG_BAD_INPUT }
148 if to_rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
149 if g.edges_to_used >= g.edges_cap { return 0 - NX_DEPG_EDGE_FULL }
150 if g.scc_built == 1 { return 0 - NX_DEPG_BAD_INPUT } // immutable after Tarjan
151
152 // First edge from this from_rowid? Stamp start.
153 if g.edges_from_count[from_rowid] == 0 {
154 g.edges_from_start[from_rowid] = g.edges_to_used
155 }
156 g.edges_to[g.edges_to_used] = to_rowid
157 g.edges_to_used = g.edges_to_used + 1
158 g.edges_from_count[from_rowid] = g.edges_from_count[from_rowid] + 1
159 return NX_DEPG_OK
160}
161
162// ===== Tarjan SCC (iterative; no recursion) =================================================
163//
164// Standard iterative Tarjan via explicit work-stack. Each node visited
165// once; each edge traversed once. O(V+E) time, O(V) space.
166//
167// Reference: Tarjan 1972 §3 algorithm STRONGCOMPONENTS.
168
169func nx_dep_graph_tarjan_scc(g: *NxDepGraph) -> i64 {
170 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
171 if g.scc_built == 1 { return NX_DEPG_OK } // idempotent
172
173 // Allocate scratch
174 g.tarjan_index = (sys_mmap(g.nodes_cap * 8)) as *i64
175 g.tarjan_lowlink = (sys_mmap(g.nodes_cap * 8)) as *i64
176 g.tarjan_onstack = (sys_mmap(g.nodes_cap * 8)) as *i64
177 g.tarjan_stack = (sys_mmap(NX_DEPG_MAX_STACK * 8)) as *i64
178
179 // Init: index = lowlink = -1; onstack = 0
180 var i: i64 = 0
181 while i < g.nodes_cap {
182 g.tarjan_index[i] = NX_DEPG_UNVISITED
183 g.tarjan_lowlink[i] = NX_DEPG_UNVISITED
184 g.tarjan_onstack[i] = 0
185 i = i + 1
186 }
187 g.tarjan_stack_top = 0
188
189 var next_index: i64 = 0
190 var scc_counter: i64 = 0
191
192 // Work stack for iterative DFS: pairs (node, edge_iter_idx)
193 // Use 2 i64s per frame; size = NX_DEPG_MAX_STACK
194 let work_stack_node: *i64 = (sys_mmap(NX_DEPG_MAX_STACK * 8)) as *i64
195 let work_stack_edge_idx: *i64 = (sys_mmap(NX_DEPG_MAX_STACK * 8)) as *i64
196 var work_top: i64 = 0
197
198 // Outer: for each unvisited node, start a DFS
199 var root: i64 = 0
200 var outer_iter: i64 = 0
201 while root < g.nodes_cap {
202 if outer_iter >= NX_DEPG_LOOP_BUDGET_CAP { return 0 - NX_DEPG_LOOP_BUDGET }
203 outer_iter = outer_iter + 1
204 if g.tarjan_index[root] == NX_DEPG_UNVISITED {
205 // Push root onto work stack
206 if work_top >= NX_DEPG_MAX_STACK { return 0 - NX_DEPG_STACK_OVERFLOW }
207 work_stack_node[work_top] = root
208 work_stack_edge_idx[work_top] = 0
209 work_top = work_top + 1
210 g.tarjan_index[root] = next_index
211 g.tarjan_lowlink[root] = next_index
212 next_index = next_index + 1
213 // Push root onto Tarjan stack
214 if g.tarjan_stack_top >= NX_DEPG_MAX_STACK { return 0 - NX_DEPG_STACK_OVERFLOW }
215 g.tarjan_stack[g.tarjan_stack_top] = root
216 g.tarjan_stack_top = g.tarjan_stack_top + 1
217 g.tarjan_onstack[root] = 1
218
219 // Inner loop: iterative DFS via work stack
220 var inner_iter: i64 = 0
221 while work_top > 0 {
222 if inner_iter >= NX_DEPG_LOOP_BUDGET_CAP { return 0 - NX_DEPG_LOOP_BUDGET }
223 inner_iter = inner_iter + 1
224
225 let cur: i64 = work_stack_node[work_top - 1]
226 let edge_i: i64 = work_stack_edge_idx[work_top - 1]
227 let n_edges: i64 = g.edges_from_count[cur]
228 let edge_start: i64 = g.edges_from_start[cur]
229
230 if edge_i < n_edges {
231 // Visit next neighbor
232 let neighbor: i64 = g.edges_to[edge_start + edge_i]
233 work_stack_edge_idx[work_top - 1] = edge_i + 1
234 if g.tarjan_index[neighbor] == NX_DEPG_UNVISITED {
235 // Push neighbor; assign index
236 if work_top >= NX_DEPG_MAX_STACK { return 0 - NX_DEPG_STACK_OVERFLOW }
237 work_stack_node[work_top] = neighbor
238 work_stack_edge_idx[work_top] = 0
239 work_top = work_top + 1
240 g.tarjan_index[neighbor] = next_index
241 g.tarjan_lowlink[neighbor] = next_index
242 next_index = next_index + 1
243 if g.tarjan_stack_top >= NX_DEPG_MAX_STACK { return 0 - NX_DEPG_STACK_OVERFLOW }
244 g.tarjan_stack[g.tarjan_stack_top] = neighbor
245 g.tarjan_stack_top = g.tarjan_stack_top + 1
246 g.tarjan_onstack[neighbor] = 1
247 }
248 if g.tarjan_index[neighbor] != NX_DEPG_UNVISITED {
249 if g.tarjan_onstack[neighbor] == 1 {
250 // Back-edge: update lowlink
251 if g.tarjan_lowlink[neighbor] < g.tarjan_lowlink[cur] {
252 g.tarjan_lowlink[cur] = g.tarjan_lowlink[neighbor]
253 }
254 }
255 }
256 }
257 if edge_i >= n_edges {
258 // All neighbors visited; check SCC root
259 if g.tarjan_lowlink[cur] == g.tarjan_index[cur] {
260 // Pop SCC off Tarjan stack
261 var done: i64 = 0
262 var pop_iter: i64 = 0
263 while done == 0 {
264 if pop_iter >= NX_DEPG_MAX_STACK { return 0 - NX_DEPG_LOOP_BUDGET }
265 pop_iter = pop_iter + 1
266 if g.tarjan_stack_top < 1 { done = 1 }
267 if g.tarjan_stack_top >= 1 {
268 g.tarjan_stack_top = g.tarjan_stack_top - 1
269 let popped: i64 = g.tarjan_stack[g.tarjan_stack_top]
270 g.tarjan_onstack[popped] = 0
271 g.scc_id[popped] = scc_counter
272 if popped == cur { done = 1 }
273 }
274 }
275 scc_counter = scc_counter + 1
276 }
277 // Pop work stack
278 work_top = work_top - 1
279 // Propagate lowlink up to parent if exists
280 if work_top > 0 {
281 let parent: i64 = work_stack_node[work_top - 1]
282 if g.tarjan_lowlink[cur] < g.tarjan_lowlink[parent] {
283 g.tarjan_lowlink[parent] = g.tarjan_lowlink[cur]
284 }
285 }
286 }
287 }
288 }
289 root = root + 1
290 }
291
292 g.scc_count = scc_counter
293 g.scc_built = 1
294 return NX_DEPG_OK
295}
296
297// ===== Accessors =================================================
298
299func nx_dep_graph_scc_of(g: *NxDepGraph, rowid: i64) -> i64 {
300 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
301 if g.scc_built == 0 { return 0 - NX_DEPG_NOT_BUILT }
302 if rowid < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
303 if rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
304 return g.scc_id[rowid]
305}
306
307// Returns size of the SCC containing rowid (>= 1; ==1 if no cycle).
308func nx_dep_graph_scc_size(g: *NxDepGraph, rowid: i64) -> i64 {
309 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
310 if g.scc_built == 0 { return 0 - NX_DEPG_NOT_BUILT }
311 if rowid < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
312 if rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
313 let my_scc: i64 = g.scc_id[rowid]
314 if my_scc < 0 { return 0 }
315 var count: i64 = 0
316 var i: i64 = 0
317 while i < g.nodes_cap {
318 if g.scc_id[i] == my_scc { count = count + 1 }
319 i = i + 1
320 }
321 return count
322}
323
324// Returns 1 if rowid is in a cycle (SCC size > 1), 0 otherwise.
325func nx_dep_graph_is_in_cycle(g: *NxDepGraph, rowid: i64) -> i64 {
326 let sz: i64 = nx_dep_graph_scc_size(g, rowid)
327 if sz > 1 { return 1 }
328 return 0
329}
330
331// Returns number of outgoing edges (deps) for rowid.
332func nx_dep_graph_deps_count(g: *NxDepGraph, rowid: i64) -> i64 {
333 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
334 if rowid < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
335 if rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
336 return g.edges_from_count[rowid]
337}
338
339// Returns the i-th dep rowid for from_rowid, or -1 if out of range.
340func nx_dep_graph_dep_at(g: *NxDepGraph, from_rowid: i64, i: i64) -> i64 {
341 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
342 if from_rowid < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
343 if from_rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
344 if i < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
345 let n: i64 = g.edges_from_count[from_rowid]
346 if i >= n { return 0 - NX_DEPG_OUT_OF_RANGE }
347 let start: i64 = g.edges_from_start[from_rowid]
348 return g.edges_to[start + i]
349}
350
351// Returns # of incoming edges (reverse-deps) for rowid (O(V+E) scan).
352func nx_dep_graph_rev_deps_count(g: *NxDepGraph, rowid: i64) -> i64 {
353 if g.valid != 1 { return 0 - NX_DEPG_BAD_INPUT }
354 if rowid < 0 { return 0 - NX_DEPG_OUT_OF_RANGE }
355 if rowid >= g.nodes_cap { return 0 - NX_DEPG_OUT_OF_RANGE }
356 var count: i64 = 0
357 var i: i64 = 0
358 while i < g.edges_to_used {
359 if g.edges_to[i] == rowid { count = count + 1 }
360 i = i + 1
361 }
362 return count
363}
364
365// Returns total SCC count (= node count if pure DAG; less if cycles exist).
366func nx_dep_graph_scc_count(g: *NxDepGraph) -> i64 {
367 if g.valid != 1 { return 0 }
368 if g.scc_built == 0 { return 0 }
369 return g.scc_count
370}
371
372// Returns total edge count.
373func nx_dep_graph_edge_count(g: *NxDepGraph) -> i64 {
374 if g.valid != 1 { return 0 }
375 return g.edges_to_used
376}
377
378// Returns number of nodes with at least one cycle (SCC size > 1).
379// O(V+E) full scan.
380func nx_dep_graph_count_nodes_in_cycles(g: *NxDepGraph) -> i64 {
381 if g.valid != 1 { return 0 }
382 if g.scc_built == 0 { return 0 }
383 var count: i64 = 0
384 var i: i64 = 0
385 while i < g.nodes_cap {
386 if g.scc_id[i] >= 0 {
387 if nx_dep_graph_scc_size(g, i) > 1 { count = count + 1 }
388 }
389 i = i + 1
390 }
391 return count
392}