Skip to main content

qualia_core_db/topology/
delta_ring.rs

1//! Fixed-size zero-heap `TopologicalDeltaRing` and `MergedGraphView`.
2//!
3//! Tier-1 Zero-Heap (`AGENTS.md` §0 & §0-A): live topological mutations (`Insert`, `Tombstone`,
4//! `Reify`, `AnchorBind`) are recorded in a fixed-capacity `[TopologicalDeltaEntry; CAP]` array
5//! and merged with `HarbouredCsrView` on the fly in caller-supplied slices.
6
7use bytemuck::{Pod, Zeroable};
8use serde::{Deserialize, Serialize};
9
10use crate::topology::csr_view::HarbouredCsrView;
11use crate::topology::header::{AnchorDomain, CellAnchor, TopologyError};
12
13/// Operation discriminant encoded in bits `[0..3]` of `TopologicalDeltaEntry::op_domain_and_slot`.
14#[repr(u8)]
15#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Hash, Serialize, Deserialize)]
16pub enum DeltaOpKind {
17    #[default]
18    Tombstone = 0,
19    Insert = 1,
20    Reify = 2,
21    AnchorBind = 3,
22}
23
24impl DeltaOpKind {
25    #[inline]
26    pub const fn from_u8(v: u8) -> Option<Self> {
27        match v & 0x0F {
28            0 => Some(Self::Tombstone),
29            1 => Some(Self::Insert),
30            2 => Some(Self::Reify),
31            3 => Some(Self::AnchorBind),
32            _ => None,
33        }
34    }
35}
36
37/// 16-byte cache-aligned delta entry scoped to a specific `graph_slot` ($0 \dots M$)
38/// inside the host `PoetGeometry`.
39#[repr(C, align(16))]
40#[derive(Copy, Clone, Debug, Default, PartialEq, Eq, Pod, Zeroable, Serialize, Deserialize)]
41pub struct TopologicalDeltaEntry {
42    pub source_vertex: u32,
43    pub target_vertex: u32,
44    /// Backing `NQuin` slot index or host Geometry $k$-cell index.
45    pub edge_anchor_idx: u32,
46    /// `[0..3]`: `DeltaOpKind` (`Tombstone=0`, `Insert=1`, `Reify=2`, `AnchorBind=3`)
47    /// `[4..7]`: `AnchorDomain` nibble (`0..=4` or `0xF` for `SemanticQuin`)
48    /// `[8..15]`: Harboured graph slot index `m` in `0..harboured_graph_count`
49    pub op_domain_and_slot: u16,
50    /// Monotonic sequence number within the open edit session.
51    pub seq_no: u16,
52}
53
54const _: () = assert!(core::mem::size_of::<TopologicalDeltaEntry>() == 16);
55const _: () = assert!(core::mem::align_of::<TopologicalDeltaEntry>() == 16);
56
57impl TopologicalDeltaEntry {
58    #[inline]
59    pub const fn pack_op_domain_slot(
60        op: DeltaOpKind,
61        domain: AnchorDomain,
62        graph_slot: u8,
63    ) -> u16 {
64        let op_nib = (op as u16) & 0x0F;
65        let dom_nib = ((domain as u8) & 0x0F) as u16;
66        op_nib | (dom_nib << 4) | ((graph_slot as u16) << 8)
67    }
68
69    #[inline]
70    pub const fn new_insert(
71        graph_slot: u8,
72        source_vertex: u32,
73        target_vertex: u32,
74        edge_anchor_idx: u32,
75        seq_no: u16,
76    ) -> Self {
77        Self {
78            source_vertex,
79            target_vertex,
80            edge_anchor_idx,
81            op_domain_and_slot: Self::pack_op_domain_slot(
82                DeltaOpKind::Insert,
83                AnchorDomain::SemanticQuin,
84                graph_slot,
85            ),
86            seq_no,
87        }
88    }
89
90    #[inline]
91    pub const fn new_tombstone(
92        graph_slot: u8,
93        source_vertex: u32,
94        target_vertex: u32,
95        seq_no: u16,
96    ) -> Self {
97        Self {
98            source_vertex,
99            target_vertex,
100            edge_anchor_idx: 0,
101            op_domain_and_slot: Self::pack_op_domain_slot(
102                DeltaOpKind::Tombstone,
103                AnchorDomain::SemanticQuin,
104                graph_slot,
105            ),
106            seq_no,
107        }
108    }
109
110    #[inline]
111    pub const fn new_reify(
112        graph_slot: u8,
113        source_vertex: u32,
114        target_vertex: u32,
115        edge_anchor_idx: u32,
116        seq_no: u16,
117    ) -> Self {
118        Self {
119            source_vertex,
120            target_vertex,
121            edge_anchor_idx,
122            op_domain_and_slot: Self::pack_op_domain_slot(
123                DeltaOpKind::Reify,
124                AnchorDomain::SemanticQuin,
125                graph_slot,
126            ),
127            seq_no,
128        }
129    }
130
131    #[inline]
132    pub const fn new_anchor_bind(
133        graph_slot: u8,
134        vertex: u32,
135        cell_index: u32,
136        domain: AnchorDomain,
137        seq_no: u16,
138    ) -> Self {
139        Self {
140            source_vertex: vertex,
141            target_vertex: cell_index,
142            edge_anchor_idx: cell_index,
143            op_domain_and_slot: Self::pack_op_domain_slot(
144                DeltaOpKind::AnchorBind,
145                domain,
146                graph_slot,
147            ),
148            seq_no,
149        }
150    }
151
152    #[inline]
153    pub const fn op_kind(&self) -> DeltaOpKind {
154        match self.op_domain_and_slot & 0x0F {
155            0 => DeltaOpKind::Tombstone,
156            1 => DeltaOpKind::Insert,
157            2 => DeltaOpKind::Reify,
158            _ => DeltaOpKind::AnchorBind,
159        }
160    }
161
162    #[inline]
163    pub const fn graph_slot(&self) -> u8 {
164        ((self.op_domain_and_slot >> 8) & 0xFF) as u8
165    }
166
167    #[inline]
168    pub const fn anchor_domain(&self) -> AnchorDomain {
169        match ((self.op_domain_and_slot >> 4) & 0x0F) as u8 {
170            0 => AnchorDomain::Cell0Vertex,
171            1 => AnchorDomain::Cell1Edge,
172            2 => AnchorDomain::Cell2Face,
173            3 => AnchorDomain::Cell3Volume,
174            4 => AnchorDomain::CellKSimplex,
175            _ => AnchorDomain::SemanticQuin,
176        }
177    }
178}
179
180/// Fixed-capacity, zero-heap delta ring buffer for live topological mutations across harboured graphs.
181#[derive(Copy, Clone, Debug)]
182pub struct TopologicalDeltaRing<const CAP: usize = 256> {
183    entries: [TopologicalDeltaEntry; CAP],
184    len: usize,
185    next_seq: u16,
186}
187
188impl<const CAP: usize> Default for TopologicalDeltaRing<CAP> {
189    fn default() -> Self {
190        Self::new()
191    }
192}
193
194impl<const CAP: usize> TopologicalDeltaRing<CAP> {
195    #[inline]
196    pub const fn new() -> Self {
197        Self {
198            entries: [TopologicalDeltaEntry {
199                source_vertex: 0,
200                target_vertex: 0,
201                edge_anchor_idx: 0,
202                op_domain_and_slot: 0,
203                seq_no: 0,
204            }; CAP],
205            len: 0,
206            next_seq: 0,
207        }
208    }
209
210    #[inline]
211    pub const fn len(&self) -> usize {
212        self.len
213    }
214
215    #[inline]
216    pub const fn is_empty(&self) -> bool {
217        self.len == 0
218    }
219
220    #[inline]
221    pub const fn capacity(&self) -> usize {
222        CAP
223    }
224
225    #[inline]
226    pub fn clear(&mut self) {
227        self.len = 0;
228        self.next_seq = 0;
229    }
230
231    #[inline]
232    pub fn entries(&self) -> &[TopologicalDeltaEntry] {
233        &self.entries[..self.len]
234    }
235
236    /// Append a delta entry, assigning the next monotonic `seq_no`.
237    pub fn push_entry(&mut self, mut entry: TopologicalDeltaEntry) -> Result<u16, TopologyError> {
238        if self.len >= CAP {
239            return Err(TopologyError::DeltaRingFull { capacity: CAP });
240        }
241        let seq = self.next_seq;
242        entry.seq_no = seq;
243        self.entries[self.len] = entry;
244        self.len += 1;
245        self.next_seq = self.next_seq.wrapping_add(1);
246        Ok(seq)
247    }
248
249    /// Record an edge insertion (`source_vertex -> target_vertex`) in `graph_slot`.
250    #[inline]
251    pub fn insert_edge(
252        &mut self,
253        graph_slot: u8,
254        source_vertex: u32,
255        target_vertex: u32,
256        edge_anchor_idx: u32,
257    ) -> Result<u16, TopologyError> {
258        self.push_entry(TopologicalDeltaEntry::new_insert(
259            graph_slot,
260            source_vertex,
261            target_vertex,
262            edge_anchor_idx,
263            0,
264        ))
265    }
266
267    /// Record an edge deletion (`source_vertex -> target_vertex`) in `graph_slot`.
268    #[inline]
269    pub fn tombstone_edge(
270        &mut self,
271        graph_slot: u8,
272        source_vertex: u32,
273        target_vertex: u32,
274    ) -> Result<u16, TopologyError> {
275        self.push_entry(TopologicalDeltaEntry::new_tombstone(
276            graph_slot,
277            source_vertex,
278            target_vertex,
279            0,
280        ))
281    }
282
283    /// Record a reified hyperedge insertion (`source_vertex -> target_vertex`) in `graph_slot`.
284    #[inline]
285    pub fn reify_edge(
286        &mut self,
287        graph_slot: u8,
288        source_vertex: u32,
289        target_vertex: u32,
290        edge_anchor_idx: u32,
291    ) -> Result<u16, TopologyError> {
292        self.push_entry(TopologicalDeltaEntry::new_reify(
293            graph_slot,
294            source_vertex,
295            target_vertex,
296            edge_anchor_idx,
297            0,
298        ))
299    }
300
301    /// Bind `vertex` in `graph_slot` to `(domain, cell_index)` in the host Geometry.
302    #[inline]
303    pub fn bind_anchor(
304        &mut self,
305        graph_slot: u8,
306        vertex: u32,
307        cell_index: u32,
308        domain: AnchorDomain,
309    ) -> Result<u16, TopologyError> {
310        self.push_entry(TopologicalDeltaEntry::new_anchor_bind(
311            graph_slot,
312            vertex,
313            cell_index,
314            domain,
315            0,
316        ))
317    }
318
319    /// 64-bit bitmask of harboured graph slots (`0..64`) modified in this ring.
320    pub fn dirty_slot_mask(&self) -> u64 {
321        let mut mask = 0u64;
322        let mut i = 0usize;
323        while i < self.len {
324            let slot = self.entries[i].graph_slot();
325            if slot < 64 {
326                mask |= 1u64 << slot;
327            }
328            i += 1;
329        }
330        mask
331    }
332}
333
334/// Zero-heap merged view combining an immutable `HarbouredCsrView` with live `TopologicalDeltaRing` edits.
335#[derive(Copy, Clone, Debug)]
336pub struct MergedGraphView<'a, const CAP: usize = 256> {
337    base: HarbouredCsrView<'a>,
338    ring: &'a TopologicalDeltaRing<CAP>,
339    graph_slot: u16,
340}
341
342impl<'a, const CAP: usize> MergedGraphView<'a, CAP> {
343    #[inline]
344    pub const fn new(
345        base: HarbouredCsrView<'a>,
346        ring: &'a TopologicalDeltaRing<CAP>,
347        graph_slot: u16,
348    ) -> Self {
349        Self {
350            base,
351            ring,
352            graph_slot,
353        }
354    }
355
356    #[inline]
357    pub const fn base(&self) -> &HarbouredCsrView<'a> {
358        &self.base
359    }
360
361    #[inline]
362    pub const fn ring(&self) -> &'a TopologicalDeltaRing<CAP> {
363        self.ring
364    }
365
366    #[inline]
367    pub const fn graph_slot(&self) -> u16 {
368        self.graph_slot
369    }
370
371    #[inline]
372    pub const fn vertex_count(&self) -> u32 {
373        self.base.vertex_count()
374    }
375
376    /// Materialize the effective outgoing neighbours and edge anchors of vertex `u`
377    /// after applying all `TopologicalDeltaRing` mutations for `self.graph_slot` in `seq_no` order.
378    pub fn effective_out_neighbors(
379        &self,
380        u: u32,
381        out_targets: &mut [u32],
382        out_edge_anchors: &mut [u32],
383    ) -> Result<usize, TopologyError> {
384        let base_targets = self.base.out_neighbors(u)?;
385        let base_anchors = self.base.out_edge_anchors(u)?;
386        let track_anchors = !out_edge_anchors.is_empty();
387
388        if base_targets.len() > out_targets.len()
389            || (track_anchors && base_anchors.len() > out_edge_anchors.len())
390        {
391            return Err(TopologyError::BufferTooSmall);
392        }
393
394        let mut count = base_targets.len();
395        out_targets[..count].copy_from_slice(base_targets);
396        if track_anchors {
397            out_edge_anchors[..count].copy_from_slice(base_anchors);
398        }
399
400        let v_count = self.base.vertex_count();
401        let entries = self.ring.entries();
402        let mut i = 0usize;
403        while i < entries.len() {
404            let entry = &entries[i];
405            i += 1;
406            if entry.graph_slot() as u16 != self.graph_slot || entry.source_vertex != u {
407                continue;
408            }
409            match entry.op_kind() {
410                DeltaOpKind::Tombstone => {
411                    let mut k = 0usize;
412                    while k < count {
413                        if out_targets[k] == entry.target_vertex {
414                            let mut shift = k;
415                            while shift + 1 < count {
416                                out_targets[shift] = out_targets[shift + 1];
417                                if track_anchors {
418                                    out_edge_anchors[shift] = out_edge_anchors[shift + 1];
419                                }
420                                shift += 1;
421                            }
422                            count -= 1;
423                        } else {
424                            k += 1;
425                        }
426                    }
427                }
428                DeltaOpKind::Insert | DeltaOpKind::Reify => {
429                    if entry.target_vertex >= v_count {
430                        return Err(TopologyError::VertexOutOfRange {
431                            vertex: entry.target_vertex,
432                            count: v_count,
433                        });
434                    }
435                    let mut existing = None;
436                    let mut k = 0usize;
437                    while k < count {
438                        if out_targets[k] == entry.target_vertex {
439                            existing = Some(k);
440                            break;
441                        }
442                        k += 1;
443                    }
444                    if let Some(pos) = existing {
445                        if track_anchors {
446                            out_edge_anchors[pos] = entry.edge_anchor_idx;
447                        }
448                    } else {
449                        if count >= out_targets.len()
450                            || (track_anchors && count >= out_edge_anchors.len())
451                        {
452                            return Err(TopologyError::BufferTooSmall);
453                        }
454                        out_targets[count] = entry.target_vertex;
455                        if track_anchors {
456                            out_edge_anchors[count] = entry.edge_anchor_idx;
457                        }
458                        count += 1;
459                    }
460                }
461                DeltaOpKind::AnchorBind => {}
462            }
463        }
464
465        Ok(count)
466    }
467
468    /// Resolve the effective `CellAnchor` of vertex `v` after applying `AnchorBind` delta entries.
469    pub fn effective_cell_anchor(&self, v: u32) -> Result<CellAnchor, TopologyError> {
470        let mut anchor = *self.base.cell_anchor(v)?;
471        let entries = self.ring.entries();
472        let mut i = 0usize;
473        while i < entries.len() {
474            let e = &entries[i];
475            if e.graph_slot() as u16 == self.graph_slot
476                && e.op_kind() == DeltaOpKind::AnchorBind
477                && e.source_vertex == v
478            {
479                anchor.cell_index = e.target_vertex;
480                anchor.anchor_domain = e.anchor_domain() as u8;
481            }
482            i += 1;
483        }
484        Ok(anchor)
485    }
486}
487