Skip to main content

qualia_core_db/topology/
invariants.rs

1//! Non-recursive, zero-heap topological, modal, and homological invariant verifiers.
2//!
3//! Tier-1 Zero-Heap (`AGENTS.md` §0 & §0-A): all graph traversals, reachability checks,
4//! cycle detectors, and Betti/Euler calculators operate strictly on caller-supplied
5//! `visited_bits: &mut [u64]` and `work_queue: &mut [u32]` slices without recursion or heap allocation.
6
7use 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
17/// Belnap 4-valued paraconsistent `Both` (`⊤` contradiction) opcode byte in `NQuin::predicate[0..7]`.
18pub const OP_BELNAP_BOTH: u8 = 0x32;
19
20/// Summary of 1-skeleton homological invariants for a `HarbouredCsrView`.
21#[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
30/// Non-recursive zero-heap reachability gate verifying that inserting `u -> v` into `view`
31/// does not introduce a directed cycle (`v -*-> u`).
32pub 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        // 1. Base CSR outgoing neighbours not tombstoned in the delta ring.
76        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        // 2. Delta-ring inserted/reified outgoing neighbours from `curr`.
98        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
135/// Verify all active `TopologyInvariants` on `csr` and compute its `HomologySummary`
136/// ($\chi, \beta_0, \beta_1$, root count, sink count) with zero heap allocation.
137pub 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
251/// Verify that the host Geometry Complex's stamped `euler_characteristic` equals
252/// its cellular alternating sum $\chi = N_0 - N_1 + N_2 - N_3$.
253pub 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