nx_eco_graph.nx source
↩ module page · 267 lines · 11682 B
1// nx_eco_graph.nx -- R0 graph ENGINE (brick-2) of the living ecosystem graph
2// ([[project-nishi-living-ecosystem-graph-2026-07-15]]). A hash-interned basename node graph + import edges +
3// the queries the operator asked for: ANCESTORS = roots-to-god (transitive imports, down to leaves like
4// nx_syscalls → god), DESCENDANTS = children-to-newest (transitive importers), COUPLING (Ca fan-in / Ce
5// fan-out), ORPHAN (Ca==0). Composes nx_import_scan for edges; the live whole-tree walk that POPULATES it =
6// brick-3. Pure integer, sovereign, deterministic. license_tier: ORIGINAL
7import "nx_syscalls.nx"
8import "nx_sov_ledger.nx" // R1 persistence rides the SOVEREIGN info-mgmt plane (seg_store), NOT raw files
9const K_MAGIC_2166136261: i64 = 2166136261
10const K_MAGIC_16777619: i64 = 16777619
11
12struct EcoGraph {
13 arena: *u8, arena_used: i64, arena_cap: i64,
14 node_off: *i64, node_count: i64, node_cap: i64,
15 hash_head: *i64, node_next: *i64, hash_size: i64,
16 edge_src: *i64, edge_dst: *i64, edge_count: i64, edge_cap: i64,
17 // R0b CSR adjacency (built by eg_finalize -> O(E)-once, then queries are O(reachable))
18 out_head: *i64, out_list: *i64, in_head: *i64, in_list: *i64, ce_arr: *i64, ca_arr: *i64, finalized: i64,
19}
20
21func eg_new(node_cap: i64, edge_cap: i64, arena_cap: i64, hash_size: i64) -> *EcoGraph {
22 let g: *EcoGraph = sys_mmap(256) as *EcoGraph
23 g.arena = sys_mmap(arena_cap); g.arena_used = 0; g.arena_cap = arena_cap
24 g.node_off = sys_mmap(node_cap*8) as *i64; g.node_count = 0; g.node_cap = node_cap
25 g.hash_head = sys_mmap(hash_size*8) as *i64; g.node_next = sys_mmap(node_cap*8) as *i64; g.hash_size = hash_size
26 var i: i64 = 0
27 while i < hash_size { g.hash_head[i] = 0; i = i + 1 }
28 g.edge_src = sys_mmap(edge_cap*8) as *i64; g.edge_dst = sys_mmap(edge_cap*8) as *i64; g.edge_count = 0; g.edge_cap = edge_cap
29 g.finalized = 0
30 return g
31}
32
33// FNV-1a over the basename, folded to a non-negative bucket.
34func eg_hash(s: *u8, len: i64, mod: i64) -> i64 {
35 var h: i64 = K_MAGIC_2166136261
36 var i: i64 = 0
37 while i < len { h = (h ^ (s[i] as i64)) * K_MAGIC_16777619; h = h & 0x7fffffff; i = i + 1 }
38 return h % mod
39}
40func eg_name_eq(g: *EcoGraph, idx: i64, s: *u8, len: i64) -> i64 {
41 let off: i64 = g.node_off[idx]
42 var i: i64 = 0
43 while i < len { if g.arena[off+i] != s[i] { return 0 } i = i + 1 }
44 if g.arena[off+len] != (0 as u8) { return 0 }
45 return 1
46}
47// Intern a basename -> node idx (dedup via the hash chain). Adds if new. -1 on capacity.
48func eg_intern(g: *EcoGraph, s: *u8, len: i64) -> i64 {
49 let b: i64 = eg_hash(s, len, g.hash_size)
50 var cur: i64 = g.hash_head[b]
51 var go: i64 = 1
52 while go == 1 {
53 if cur == 0 { go = 0 } else {
54 let idx: i64 = cur - 1
55 if eg_name_eq(g, idx, s, len) == 1 { return idx }
56 cur = g.node_next[idx]
57 }
58 }
59 if g.node_count >= g.node_cap { return 0 - 1 }
60 if g.arena_used + len + 1 > g.arena_cap { return 0 - 1 }
61 let ni: i64 = g.node_count
62 g.node_off[ni] = g.arena_used
63 var i: i64 = 0
64 while i < len { g.arena[g.arena_used+i] = s[i]; i = i + 1 }
65 g.arena[g.arena_used+len] = 0 as u8
66 g.arena_used = g.arena_used + len + 1
67 g.node_next[ni] = g.hash_head[b]
68 g.hash_head[b] = ni + 1
69 g.node_count = ni + 1
70 return ni
71}
72func eg_add_edge(g: *EcoGraph, src: i64, dst: i64) -> i64 {
73 if g.edge_count >= g.edge_cap { return 0 - 1 }
74 g.edge_src[g.edge_count] = src; g.edge_dst[g.edge_count] = dst; g.edge_count = g.edge_count + 1
75 return 0
76}
77// R0b: build CSR adjacency + degree arrays ONCE (O(N+E)) so coupling is O(1) and traversals are O(reachable).
78func eg_finalize(g: *EcoGraph) -> i64 {
79 let n: i64 = g.node_count
80 let m: i64 = g.edge_count
81 g.ce_arr = sys_mmap((n+2)*8) as *i64
82 g.ca_arr = sys_mmap((n+2)*8) as *i64
83 g.out_head = sys_mmap((n+2)*8) as *i64
84 g.in_head = sys_mmap((n+2)*8) as *i64
85 g.out_list = sys_mmap((m+1)*8) as *i64
86 g.in_list = sys_mmap((m+1)*8) as *i64
87 var i: i64 = 0
88 while i <= n { g.ce_arr[i] = 0; g.ca_arr[i] = 0; i = i + 1 }
89 i = 0
90 while i < m {
91 let s: i64 = g.edge_src[i]; let d: i64 = g.edge_dst[i]
92 g.ce_arr[s] = g.ce_arr[s] + 1; g.ca_arr[d] = g.ca_arr[d] + 1
93 i = i + 1
94 }
95 g.out_head[0] = 0; g.in_head[0] = 0
96 i = 0
97 while i < n { g.out_head[i+1] = g.out_head[i] + g.ce_arr[i]; g.in_head[i+1] = g.in_head[i] + g.ca_arr[i]; i = i + 1 }
98 let cur_o: *i64 = sys_mmap((n+1)*8) as *i64
99 let cur_i: *i64 = sys_mmap((n+1)*8) as *i64
100 i = 0
101 while i < n { cur_o[i] = g.out_head[i]; cur_i[i] = g.in_head[i]; i = i + 1 }
102 i = 0
103 while i < m {
104 let s: i64 = g.edge_src[i]; let d: i64 = g.edge_dst[i]
105 g.out_list[cur_o[s]] = d; cur_o[s] = cur_o[s] + 1
106 g.in_list[cur_i[d]] = s; cur_i[d] = cur_i[d] + 1
107 i = i + 1
108 }
109 g.finalized = 1
110 return 0
111}
112func eg_ce(g: *EcoGraph, idx: i64) -> i64 { // fan-out = # imports
113 if g.finalized == 1 { return g.ce_arr[idx] }
114 var c: i64 = 0; var i: i64 = 0
115 while i < g.edge_count { if g.edge_src[i] == idx { c = c + 1 } i = i + 1 }
116 return c
117}
118func eg_ca(g: *EcoGraph, idx: i64) -> i64 { // fan-in = # importers
119 if g.finalized == 1 { return g.ca_arr[idx] }
120 var c: i64 = 0; var i: i64 = 0
121 while i < g.edge_count { if g.edge_dst[i] == idx { c = c + 1 } i = i + 1 }
122 return c
123}
124// ANCESTORS (roots-to-god): transitive OUT-closure (what idx imports, recursively). Caller zeroes `visited`
125// (node_count bytes) + marks visited[idx]=1, sets outn[0]=0. Collects reached node idxs into out[].
126func eg_ancestors(g: *EcoGraph, idx: i64, visited: *u8, out: *i64, outn: *i64, cap: i64) -> i64 {
127 if g.finalized == 1 {
128 var p: i64 = g.out_head[idx]
129 let e: i64 = g.out_head[idx+1]
130 while p < e {
131 let d: i64 = g.out_list[p]
132 if visited[d] == (0 as u8) { visited[d] = 1 as u8; if outn[0] < cap { out[outn[0]] = d; outn[0] = outn[0] + 1 } eg_ancestors(g, d, visited, out, outn, cap) }
133 p = p + 1
134 }
135 return 0
136 }
137 var i: i64 = 0
138 while i < g.edge_count {
139 if g.edge_src[i] == idx {
140 let d: i64 = g.edge_dst[i]
141 if visited[d] == (0 as u8) { visited[d] = 1 as u8; if outn[0] < cap { out[outn[0]] = d; outn[0] = outn[0] + 1 } eg_ancestors(g, d, visited, out, outn, cap) }
142 }
143 i = i + 1
144 }
145 return 0
146}
147// DESCENDANTS (children-to-newest): transitive IN-closure (who imports idx, recursively).
148func eg_descendants(g: *EcoGraph, idx: i64, visited: *u8, out: *i64, outn: *i64, cap: i64) -> i64 {
149 if g.finalized == 1 {
150 var p: i64 = g.in_head[idx]
151 let e: i64 = g.in_head[idx+1]
152 while p < e {
153 let s: i64 = g.in_list[p]
154 if visited[s] == (0 as u8) { visited[s] = 1 as u8; if outn[0] < cap { out[outn[0]] = s; outn[0] = outn[0] + 1 } eg_descendants(g, s, visited, out, outn, cap) }
155 p = p + 1
156 }
157 return 0
158 }
159 var i: i64 = 0
160 while i < g.edge_count {
161 if g.edge_dst[i] == idx {
162 let s: i64 = g.edge_src[i]
163 if visited[s] == (0 as u8) { visited[s] = 1 as u8; if outn[0] < cap { out[outn[0]] = s; outn[0] = outn[0] + 1 } eg_descendants(g, s, visited, out, outn, cap) }
164 }
165 i = i + 1
166 }
167 return 0
168}
169
170// ---- R1: persist the FINALIZED graph into the SOVEREIGN info-mgmt plane (nx_sov_ledger -> seg_store), NOT a
171// raw 3rd-party file. `prefix` = the seg_store store path; each component is a TYPED sovereign record (i64
172// arrays via sov_put_ints, the byte arena via sov_put). interop@boundary / sovereign@core: the graph store is
173// CORE, so it is sovereign. + name lookup (query-fast). The store is the SSOT the API/MCP/wiki read; R5 refreshes it.
174func eg_find(g: *EcoGraph, s: *u8, len: i64) -> i64 {
175 var i: i64 = 0
176 while i < g.node_count { if eg_name_eq(g, i, s, len) == 1 { return i } i = i + 1 }
177 return 0 - 1
178}
179func eg_save(g: *EcoGraph, prefix: *u8) -> i64 {
180 if g.finalized == 0 { return 0 - 1 }
181 let n: i64 = g.node_count
182 let m: i64 = g.edge_count
183 let hdr: *i64 = sys_mmap(32) as *i64
184 hdr[0] = n; hdr[1] = m; hdr[2] = g.arena_used
185 sov_put_ints(prefix, "eco:hdr" as *u8, hdr, 3)
186 sov_put(prefix, "eco:arena" as *u8, g.arena, g.arena_used)
187 sov_put_ints(prefix, "eco:node_off" as *u8, g.node_off, n)
188 sov_put_ints(prefix, "eco:ca" as *u8, g.ca_arr, n)
189 sov_put_ints(prefix, "eco:ce" as *u8, g.ce_arr, n)
190 sov_put_ints(prefix, "eco:out_head" as *u8, g.out_head, n+1)
191 sov_put_ints(prefix, "eco:in_head" as *u8, g.in_head, n+1)
192 sov_put_ints(prefix, "eco:out_list" as *u8, g.out_list, m)
193 sov_put_ints(prefix, "eco:in_list" as *u8, g.in_list, m)
194 return 0
195}
196func eg_load(prefix: *u8) -> *EcoGraph {
197 let hdr: *i64 = sys_mmap(32) as *i64
198 if sov_get_ints(prefix, "eco:hdr" as *u8, hdr, 3) != 3 { return 0 as *EcoGraph }
199 let n: i64 = hdr[0]
200 let m: i64 = hdr[1]
201 let au: i64 = hdr[2]
202 let g: *EcoGraph = sys_mmap(256) as *EcoGraph
203 g.node_count = n; g.edge_count = m; g.arena_used = au; g.finalized = 1
204 g.node_cap = n; g.edge_cap = m
205 g.arena = sys_mmap(au + 16)
206 sov_get_copy(prefix, "eco:arena" as *u8, g.arena, au)
207 g.node_off = sys_mmap((n+2)*8) as *i64
208 sov_get_ints(prefix, "eco:node_off" as *u8, g.node_off, n)
209 g.ca_arr = sys_mmap((n+2)*8) as *i64
210 sov_get_ints(prefix, "eco:ca" as *u8, g.ca_arr, n)
211 g.ce_arr = sys_mmap((n+2)*8) as *i64
212 sov_get_ints(prefix, "eco:ce" as *u8, g.ce_arr, n)
213 g.out_head = sys_mmap((n+2)*8) as *i64
214 sov_get_ints(prefix, "eco:out_head" as *u8, g.out_head, n+1)
215 g.in_head = sys_mmap((n+2)*8) as *i64
216 sov_get_ints(prefix, "eco:in_head" as *u8, g.in_head, n+1)
217 g.out_list = sys_mmap((m+1)*8) as *i64
218 sov_get_ints(prefix, "eco:out_list" as *u8, g.out_list, m)
219 g.in_list = sys_mmap((m+1)*8) as *i64
220 sov_get_ints(prefix, "eco:in_list" as *u8, g.in_list, m)
221 return g
222}
223
224// ---- R4-core: ORTHOGONALITY metric #1 = import-cycle (tangle) detection. A healthy layered ecosystem is a
225// DAG (imports flow toward god, never loop); a cycle = a non-orthogonal tangle. DFS 3-colour (0 white / 1 gray
226// on-stack / 2 black done): a back-edge to a gray node IS a cycle. Requires finalized (CSR). ----
227func eg_dfs_cycle(g: *EcoGraph, u: i64, color: *u8) -> i64 {
228 color[u] = 1 as u8
229 var p: i64 = g.out_head[u]
230 let e: i64 = g.out_head[u+1]
231 while p < e {
232 let v: i64 = g.out_list[p]
233 if color[v] == (1 as u8) { return 1 }
234 if color[v] == (0 as u8) { if eg_dfs_cycle(g, v, color) == 1 { return 1 } }
235 p = p + 1
236 }
237 color[u] = 2 as u8
238 return 0
239}
240// 1 if the import graph has ANY cycle (tangle), else 0.
241func eg_has_cycle(g: *EcoGraph) -> i64 {
242 let color: *u8 = sys_mmap(g.node_count + 2)
243 var i: i64 = 0
244 while i < g.node_count { color[i] = 0 as u8; i = i + 1 }
245 i = 0
246 while i < g.node_count {
247 if color[i] == (0 as u8) { if eg_dfs_cycle(g, i, color) == 1 { return 1 } }
248 i = i + 1
249 }
250 return 0
251}
252// coupling-distribution orthogonality signal: writes max_ca, n_hub (Ca>=hub_thr), n_leaf (Ca==0) into out[0..2].
253func eg_coupling_stats(g: *EcoGraph, hub_thr: i64, out: *i64) -> i64 {
254 var maxca: i64 = 0
255 var nhub: i64 = 0
256 var nleaf: i64 = 0
257 var i: i64 = 0
258 while i < g.node_count {
259 let ca: i64 = eg_ca(g, i)
260 if ca > maxca { maxca = ca }
261 if ca >= hub_thr { nhub = nhub + 1 }
262 if ca == 0 { nleaf = nleaf + 1 }
263 i = i + 1
264 }
265 out[0] = maxca; out[1] = nhub; out[2] = nleaf
266 return 0
267}