1use crate::frame_layout::DEFEATER_BIT;
8use crate::modalities::logic::deontic::OP_FORBID;
9use crate::tensor::Tensor10D;
10use crate::topology::csr_view::HarbouredCsrView;
11use crate::topology::delta_ring::{DeltaOpKind, MergedGraphView};
12use crate::topology::geometry_view::PoetGeometryView;
13use crate::topology::header::{
14 AnchorDomain, GraphMorphology, TopologyError, TopologyInvariants,
15};
16
17pub const OP_BELNAP_BOTH: u8 = 0x32;
19
20#[derive(Copy, Clone, Debug, Default, PartialEq, Eq)]
22pub struct HomologySummary {
23 pub euler_characteristic: i32,
24 pub betti_0: u32,
25 pub betti_1: u32,
26 pub root_count: u32,
27 pub sink_count: u32,
28}
29
30pub fn check_acyclic_insert<const CAP: usize>(
33 view: &MergedGraphView<'_, CAP>,
34 u: u32,
35 v: u32,
36 visited_bits: &mut [u64],
37 queue: &mut [u32],
38) -> Result<(), TopologyError> {
39 let v_count = view.vertex_count();
40 if u >= v_count {
41 return Err(TopologyError::VertexOutOfRange {
42 vertex: u,
43 count: v_count,
44 });
45 }
46 if v >= v_count {
47 return Err(TopologyError::VertexOutOfRange {
48 vertex: v,
49 count: v_count,
50 });
51 }
52 if u == v {
53 return Err(TopologyError::CycleDetected {
54 source: u,
55 target: v,
56 });
57 }
58
59 let n = v_count as usize;
60 let words = (n + 63) / 64;
61 if visited_bits.len() < words || queue.len() < n {
62 return Err(TopologyError::BufferTooSmall);
63 }
64
65 visited_bits[..words].fill(0);
66 set_bit(visited_bits, v as usize);
67 queue[0] = v;
68 let mut head = 0usize;
69 let mut tail = 1usize;
70
71 while head < tail {
72 let curr = queue[head];
73 head += 1;
74
75 let base_nbrs = view.base().out_neighbors(curr)?;
77 let mut i = 0usize;
78 while i < base_nbrs.len() {
79 let w = base_nbrs[i];
80 i += 1;
81 if !is_edge_live_in_ring(view, curr, w, true) {
82 continue;
83 }
84 if w == u {
85 return Err(TopologyError::CycleDetected {
86 source: u,
87 target: v,
88 });
89 }
90 if !test_bit(visited_bits, w as usize) {
91 set_bit(visited_bits, w as usize);
92 queue[tail] = w;
93 tail += 1;
94 }
95 }
96
97 let entries = view.ring().entries();
99 let mut j = 0usize;
100 while j < entries.len() {
101 let e = &entries[j];
102 j += 1;
103 if e.graph_slot() as u16 != view.graph_slot() || e.source_vertex != curr {
104 continue;
105 }
106 if matches!(e.op_kind(), DeltaOpKind::Insert | DeltaOpKind::Reify) {
107 let w = e.target_vertex;
108 if w >= v_count {
109 return Err(TopologyError::VertexOutOfRange {
110 vertex: w,
111 count: v_count,
112 });
113 }
114 if !is_edge_live_in_ring(view, curr, w, false) {
115 continue;
116 }
117 if w == u {
118 return Err(TopologyError::CycleDetected {
119 source: u,
120 target: v,
121 });
122 }
123 if !test_bit(visited_bits, w as usize) {
124 set_bit(visited_bits, w as usize);
125 queue[tail] = w;
126 tail += 1;
127 }
128 }
129 }
130 }
131
132 Ok(())
133}
134
135pub fn verify_graph_invariants(
138 csr: &HarbouredCsrView<'_>,
139 quins: &[crate::NQuin],
140 coords_10d: Option<&[Tensor10D]>,
141 visited_bits: &mut [u64],
142 work_queue: &mut [u32],
143) -> Result<HomologySummary, TopologyError> {
144 let v_count = csr.vertex_count() as usize;
145 let e_count = csr.edge_count() as usize;
146 let words = (v_count + 63) / 64;
147
148 if v_count > 0 && (visited_bits.len() < words || work_queue.len() < v_count) {
149 return Err(TopologyError::BufferTooSmall);
150 }
151
152 let invariants = csr.header().invariants;
153 let is_dag = invariants.contains(TopologyInvariants::ACYCLIC)
154 || csr.header().morphology == GraphMorphology::DeterministicDAG as u8;
155
156 if is_dag && v_count > 0 {
157 verify_acyclic_kahn(csr, visited_bits, work_queue)?;
158 }
159
160 let check_temporal = invariants.contains(TopologyInvariants::TEMPORAL_MONOTONIC);
161 let check_deontic = invariants.contains(TopologyInvariants::DEONTIC_GUARDED);
162 let check_paraconsistent = invariants.contains(TopologyInvariants::PARACONSISTENT_ISOLATED);
163 let check_sensitivity = invariants.contains(TopologyInvariants::SENSITIVITY_MONOTONIC);
164 let max_sens = csr.header().max_sensitivity_class();
165
166 if check_temporal || check_deontic || check_paraconsistent || check_sensitivity {
167 let mut u = 0u32;
168 while (u as usize) < v_count {
169 let nbrs = csr.out_neighbors(u)?;
170 let e_anchors = csr.out_edge_anchors(u)?;
171 let mut k = 0usize;
172 while k < nbrs.len() {
173 let v = nbrs[k];
174 let edge_anchor_idx = e_anchors[k];
175 k += 1;
176
177 if check_temporal {
178 if let Some(coords) = coords_10d {
179 if (u as usize) < coords.len()
180 && (v as usize) < coords.len()
181 && coords[u as usize].t > coords[v as usize].t
182 {
183 return Err(TopologyError::TemporalMonotonicityViolation {
184 source: u,
185 target: v,
186 });
187 }
188 }
189 if let ( Some(clock_u), Some(clock_v) ) = (
190 vertex_lamport_clock(csr, quins, u),
191 vertex_lamport_clock(csr, quins, v),
192 ) {
193 if clock_u > clock_v {
194 return Err(TopologyError::TemporalMonotonicityViolation {
195 source: u,
196 target: v,
197 });
198 }
199 }
200 }
201
202 if let Some(q) = quins.get(edge_anchor_idx as usize) {
203 let opcode = (q.predicate & 0xFF) as u8;
204 if check_deontic && opcode == OP_FORBID && (q.predicate & DEFEATER_BIT) == 0 {
205 return Err(TopologyError::DeonticForbidViolation { edge_anchor_idx });
206 }
207 if check_paraconsistent && opcode == OP_BELNAP_BOTH {
208 return Err(TopologyError::ParaconsistentContagion { edge_anchor_idx });
209 }
210 if check_sensitivity {
211 let edge_sens = (q.context >> 56) as u8;
212 if edge_sens > max_sens {
213 return Err(TopologyError::SensitivityEscalation {
214 source_class: max_sens,
215 target_class: edge_sens,
216 });
217 }
218 }
219 }
220 }
221 u += 1;
222 }
223 }
224
225 let mut root_count = 0u32;
226 let mut sink_count = 0u32;
227 let mut v = 0u32;
228 while (v as usize) < v_count {
229 if csr.in_degree(v)? == 0 {
230 root_count += 1;
231 }
232 if csr.out_degree(v)? == 0 {
233 sink_count += 1;
234 }
235 v += 1;
236 }
237
238 let betti_0 = compute_connected_components(csr, visited_bits, work_queue)?;
239 let euler_characteristic = (v_count as i32) - (e_count as i32);
240 let betti_1 = ((e_count as i32) - (v_count as i32) + (betti_0 as i32)).max(0) as u32;
241
242 Ok(HomologySummary {
243 euler_characteristic,
244 betti_0,
245 betti_1,
246 root_count,
247 sink_count,
248 })
249}
250
251pub fn verify_geometry_complex_homology(geom: &PoetGeometryView<'_>) -> Result<i32, TopologyError> {
254 let hdr = geom.header();
255 let computed = hdr.computed_euler_characteristic();
256 if hdr.euler_characteristic != computed {
257 return Err(TopologyError::ChecksumMismatch {
258 expected: computed as u32,
259 actual: hdr.euler_characteristic as u32,
260 });
261 }
262 Ok(computed)
263}
264
265fn verify_acyclic_kahn(
266 csr: &HarbouredCsrView<'_>,
267 visited_bits: &mut [u64],
268 in_deg_work: &mut [u32],
269) -> Result<(), TopologyError> {
270 let v_count = csr.vertex_count() as usize;
271 let words = (v_count + 63) / 64;
272 visited_bits[..words].fill(0);
273
274 let mut u = 0usize;
275 while u < v_count {
276 let nbrs = csr.out_neighbors(u as u32)?;
277 let mut k = 0usize;
278 while k < nbrs.len() {
279 if nbrs[k] == u as u32 {
280 return Err(TopologyError::CycleDetected {
281 source: u as u32,
282 target: u as u32,
283 });
284 }
285 k += 1;
286 }
287 in_deg_work[u] = csr.in_degree(u as u32)?;
288 u += 1;
289 }
290
291 let mut eliminated = 0usize;
292 while eliminated < v_count {
293 let mut progress = false;
294 let mut v = 0usize;
295 while v < v_count {
296 if !test_bit(visited_bits, v) && in_deg_work[v] == 0 {
297 set_bit(visited_bits, v);
298 eliminated += 1;
299 progress = true;
300 let nbrs = csr.out_neighbors(v as u32)?;
301 let mut k = 0usize;
302 while k < nbrs.len() {
303 let w = nbrs[k] as usize;
304 in_deg_work[w] = in_deg_work[w].saturating_sub(1);
305 k += 1;
306 }
307 }
308 v += 1;
309 }
310 if !progress {
311 let mut src = 0u32;
312 let mut dst = 0u32;
313 let mut s = 0usize;
314 'find_cycle: while s < v_count {
315 if !test_bit(visited_bits, s) {
316 let nbrs = csr.out_neighbors(s as u32)?;
317 let mut k = 0usize;
318 while k < nbrs.len() {
319 let w = nbrs[k] as usize;
320 if !test_bit(visited_bits, w) {
321 src = s as u32;
322 dst = w as u32;
323 break 'find_cycle;
324 }
325 k += 1;
326 }
327 }
328 s += 1;
329 }
330 return Err(TopologyError::CycleDetected {
331 source: src,
332 target: dst,
333 });
334 }
335 }
336 Ok(())
337}
338
339fn compute_connected_components(
340 csr: &HarbouredCsrView<'_>,
341 visited_bits: &mut [u64],
342 work_queue: &mut [u32],
343) -> Result<u32, TopologyError> {
344 let v_count = csr.vertex_count() as usize;
345 if v_count == 0 {
346 return Ok(0);
347 }
348 let words = (v_count + 63) / 64;
349 visited_bits[..words].fill(0);
350
351 let mut components = 0u32;
352 let mut start = 0usize;
353 while start < v_count {
354 if test_bit(visited_bits, start) {
355 start += 1;
356 continue;
357 }
358 components += 1;
359 set_bit(visited_bits, start);
360 work_queue[0] = start as u32;
361 let mut head = 0usize;
362 let mut tail = 1usize;
363
364 while head < tail {
365 let curr = work_queue[head];
366 head += 1;
367
368 let out_nbrs = csr.out_neighbors(curr)?;
369 let mut i = 0usize;
370 while i < out_nbrs.len() {
371 let w = out_nbrs[i] as usize;
372 if !test_bit(visited_bits, w) {
373 set_bit(visited_bits, w);
374 work_queue[tail] = w as u32;
375 tail += 1;
376 }
377 i += 1;
378 }
379
380 let in_nbrs = csr.in_neighbors(curr)?;
381 let mut j = 0usize;
382 while j < in_nbrs.len() {
383 let w = in_nbrs[j] as usize;
384 if !test_bit(visited_bits, w) {
385 set_bit(visited_bits, w);
386 work_queue[tail] = w as u32;
387 tail += 1;
388 }
389 j += 1;
390 }
391 }
392 start += 1;
393 }
394
395 Ok(components)
396}
397
398#[inline]
399fn vertex_lamport_clock(csr: &HarbouredCsrView<'_>, quins: &[crate::NQuin], v: u32) -> Option<u64> {
400 if quins.is_empty() {
401 return None;
402 }
403 let anchor = csr.cell_anchor(v).ok()?;
404 if anchor.anchor_domain == AnchorDomain::SemanticQuin as u8 {
405 if let Some(q) = quins.get(anchor.cell_index as usize) {
406 if anchor.entity_hash == 0 || q.subject == anchor.entity_hash {
407 return Some((q.metadata >> 32) & 0x1FFF_FFFF);
408 }
409 }
410 }
411 if anchor.entity_hash != 0 {
412 let mut i = 0usize;
413 while i < quins.len() {
414 if quins[i].subject == anchor.entity_hash {
415 return Some((quins[i].metadata >> 32) & 0x1FFF_FFFF);
416 }
417 i += 1;
418 }
419 }
420 None
421}
422
423#[inline]
424fn is_edge_live_in_ring<const CAP: usize>(
425 view: &MergedGraphView<'_, CAP>,
426 u: u32,
427 v: u32,
428 mut live: bool,
429) -> bool {
430 let entries = view.ring().entries();
431 let mut i = 0usize;
432 while i < entries.len() {
433 let e = &entries[i];
434 if e.graph_slot() as u16 == view.graph_slot()
435 && e.source_vertex == u
436 && e.target_vertex == v
437 {
438 match e.op_kind() {
439 DeltaOpKind::Tombstone => live = false,
440 DeltaOpKind::Insert | DeltaOpKind::Reify => live = true,
441 DeltaOpKind::AnchorBind => {}
442 }
443 }
444 i += 1;
445 }
446 live
447}
448
449#[inline]
450fn test_bit(bits: &[u64], idx: usize) -> bool {
451 (bits[idx >> 6] & (1u64 << (idx & 63))) != 0
452}
453
454#[inline]
455fn set_bit(bits: &mut [u64], idx: usize) {
456 bits[idx >> 6] |= 1u64 << (idx & 63);
457}
458