Skip to main content

qualia_core_db/topology/
compactor.rs

1//! Tier-2 cold `GTOP` segment compiler and delta-ring compaction engine.
2//!
3//! Tier-2 Cold Bounded (`AGENTS.md` ยง0-A): [`compile_geometry_segment`] checks the caller's
4//! `budget_bytes` before allocating scratch buffers and emits a 64-byte-aligned `GTOP` binary
5//! segment directly into the caller's `out_buf` with Castagnoli CRC-32C receipts.
6
7use crate::container_10d::crc32c::{crc32c_update, crc32c};
8use crate::topology::delta_ring::{DeltaOpKind, TopologicalDeltaEntry};
9use crate::topology::header::{
10    CellAnchor, GeometryComplexKind, GeometryMetricKind, GraphEmbedRole, GraphMorphology,
11    HarbouredGraphHeader, PoetGeometryHeader, TopologyError, TopologyInvariants,
12};
13
14/// Unsealed specification of one harboured graph prior to CSR/CSC compaction.
15#[derive(Clone, Debug, PartialEq)]
16pub struct UnsealedGraphSpec {
17    pub graph_id: u64,
18    pub embed_role: GraphEmbedRole,
19    pub morphology: GraphMorphology,
20    pub invariants: TopologyInvariants,
21    pub context_and_state_mask: u32,
22    pub anchors: Vec<CellAnchor>,
23    /// Directed edges `(source_v, target_v, edge_anchor_idx)`.
24    pub edges: Vec<(u32, u32, u32)>,
25    pub edge_weights: Option<Vec<f32>>,
26}
27
28/// Unsealed specification of a host Geometry Complex and its $M$ harboured graphs.
29#[derive(Clone, Debug, PartialEq)]
30pub struct UnsealedGeometrySpec {
31    pub geometry_id: u64,
32    pub construct_schema_hash: u64,
33    pub manifold_id: u32,
34    pub complex_kind: GeometryComplexKind,
35    pub metric_kind: GeometryMetricKind,
36    pub ambient_dim: u8,
37    pub intrinsic_dim: u8,
38    /// Cellular counts `[N_0, N_1, N_2, N_3]`.
39    pub cell_counts: [u32; 4],
40    pub active_graph_slot: u16,
41    pub graphs: Vec<UnsealedGraphSpec>,
42}
43
44#[inline]
45const fn align64(offset: usize) -> usize {
46    (offset + 63) & !63
47}
48
49/// Compute the exact 64-byte-aligned byte length required to encode `spec` into a `GTOP` segment.
50pub fn required_geometry_segment_bytes(spec: &UnsealedGeometrySpec) -> Result<usize, TopologyError> {
51    let m = spec.graphs.len();
52    let mut cursor = 64usize
53        .checked_add(m.checked_mul(64).ok_or(TopologyError::BufferTooSmall)?)
54        .ok_or(TopologyError::BufferTooSmall)?;
55
56    for g in &spec.graphs {
57        let v = g.anchors.len();
58        let e = g.edges.len();
59        let anchors_bytes = v.checked_mul(16).ok_or(TopologyError::BufferTooSmall)?;
60        let ptr_bytes = (v + 1).checked_mul(4).ok_or(TopologyError::BufferTooSmall)?;
61        let edge_u32_bytes = e.checked_mul(4).ok_or(TopologyError::BufferTooSmall)?;
62
63        for section_len in [
64            anchors_bytes,
65            ptr_bytes,
66            edge_u32_bytes,
67            edge_u32_bytes,
68            ptr_bytes,
69            edge_u32_bytes,
70        ] {
71            cursor = align64(cursor)
72                .checked_add(align64(section_len))
73                .ok_or(TopologyError::BufferTooSmall)?;
74        }
75        if g.edge_weights.is_some() {
76            cursor = align64(cursor)
77                .checked_add(align64(edge_u32_bytes))
78                .ok_or(TopologyError::BufferTooSmall)?;
79        }
80    }
81    Ok(align64(cursor))
82}
83
84/// Compile `spec` into a 64-byte-aligned `GTOP` binary segment inside `out_buf`.
85///
86/// Fails closed with [`TopologyError::BudgetExhausted`] if the segment + scratch bytes exceed
87/// `budget_bytes`, and with [`TopologyError::BufferTooSmall`] if `out_buf` cannot hold the segment.
88pub fn compile_geometry_segment(
89    spec: &UnsealedGeometrySpec,
90    budget_bytes: usize,
91    out_buf: &mut [u8],
92) -> Result<usize, TopologyError> {
93    if !spec.graphs.is_empty() && (spec.active_graph_slot as usize) >= spec.graphs.len() {
94        return Err(TopologyError::GraphSlotOutOfRange {
95            slot: spec.active_graph_slot,
96            count: spec.graphs.len() as u16,
97        });
98    }
99
100    let total_bytes = required_geometry_segment_bytes(spec)?;
101    let max_scratch = spec
102        .graphs
103        .iter()
104        .map(|g| (g.anchors.len() + 1) * 8 + g.edges.len() * 32)
105        .max()
106        .unwrap_or(0);
107    let requested = total_bytes.saturating_add(max_scratch);
108    if requested > budget_bytes {
109        return Err(TopologyError::BudgetExhausted {
110            requested,
111            budget: budget_bytes,
112        });
113    }
114    if out_buf.len() < total_bytes {
115        return Err(TopologyError::BufferTooSmall);
116    }
117
118    for g in &spec.graphs {
119        let v_count = g.anchors.len() as u32;
120        if let Some(ref w) = g.edge_weights {
121            if w.len() != g.edges.len() {
122                return Err(TopologyError::BufferTooSmall);
123            }
124        }
125        for &(u, v, _) in &g.edges {
126            if u >= v_count {
127                return Err(TopologyError::VertexOutOfRange {
128                    vertex: u,
129                    count: v_count,
130                });
131            }
132            if v >= v_count {
133                return Err(TopologyError::VertexOutOfRange {
134                    vertex: v,
135                    count: v_count,
136                });
137            }
138        }
139    }
140
141    out_buf[..total_bytes].fill(0);
142
143    let m = spec.graphs.len();
144    let graph_dir_offset = 64usize;
145    let mut cursor = align64(graph_dir_offset + m * 64);
146
147    for (slot, g) in spec.graphs.iter().enumerate() {
148        let v_count = g.anchors.len();
149        let e_count = g.edges.len();
150
151        // Sort CSR edges by (u, v, edge_anchor) carrying optional weight.
152        let mut csr_tuples: Vec<(u32, u32, u32, f32)> = Vec::with_capacity(e_count);
153        for (idx, &(u, v, anc)) in g.edges.iter().enumerate() {
154            let w = g.edge_weights.as_ref().map_or(0.0, |ws| ws[idx]);
155            csr_tuples.push((u, v, anc, w));
156        }
157        csr_tuples.sort_unstable_by(|a, b| (a.0, a.1, a.2).cmp(&(b.0, b.1, b.2)));
158
159        let mut csr_row_ptr = vec![0u32; v_count + 1];
160        let mut csr_col_idx = Vec::with_capacity(e_count);
161        let mut edge_anchor = Vec::with_capacity(e_count);
162        let mut sorted_weights = Vec::with_capacity(if g.edge_weights.is_some() { e_count } else { 0 });
163
164        for &(u, v, anc, w) in &csr_tuples {
165            csr_row_ptr[u as usize + 1] += 1;
166            csr_col_idx.push(v);
167            edge_anchor.push(anc);
168            if g.edge_weights.is_some() {
169                sorted_weights.push(w);
170            }
171        }
172        for u in 0..v_count {
173            csr_row_ptr[u + 1] += csr_row_ptr[u];
174        }
175
176        // Sort CSC edges by (v, u) for backward incoming lookups.
177        let mut csc_tuples: Vec<(u32, u32)> = csr_tuples.iter().map(|&(u, v, _, _)| (v, u)).collect();
178        csc_tuples.sort_unstable();
179
180        let mut csc_col_ptr = vec![0u32; v_count + 1];
181        let mut csc_row_idx = Vec::with_capacity(e_count);
182        for &(v, u) in &csc_tuples {
183            csc_col_ptr[v as usize + 1] += 1;
184            csc_row_idx.push(u);
185        }
186        for v in 0..v_count {
187            csc_col_ptr[v + 1] += csc_col_ptr[v];
188        }
189
190        let anchor_table_offset = align64(cursor);
191        let anchor_bytes: &[u8] = bytemuck::cast_slice(&g.anchors);
192        out_buf[anchor_table_offset..anchor_table_offset + anchor_bytes.len()]
193            .copy_from_slice(anchor_bytes);
194        cursor = align64(anchor_table_offset + align64(anchor_bytes.len()));
195
196        let csr_row_ptr_offset = align64(cursor);
197        let row_ptr_bytes: &[u8] = bytemuck::cast_slice(&csr_row_ptr);
198        out_buf[csr_row_ptr_offset..csr_row_ptr_offset + row_ptr_bytes.len()]
199            .copy_from_slice(row_ptr_bytes);
200        cursor = align64(csr_row_ptr_offset + align64(row_ptr_bytes.len()));
201
202        let csr_col_idx_offset = align64(cursor);
203        let col_idx_bytes: &[u8] = bytemuck::cast_slice(&csr_col_idx);
204        out_buf[csr_col_idx_offset..csr_col_idx_offset + col_idx_bytes.len()]
205            .copy_from_slice(col_idx_bytes);
206        cursor = align64(csr_col_idx_offset + align64(col_idx_bytes.len()));
207
208        let edge_anchor_offset = align64(cursor);
209        let edge_anc_bytes: &[u8] = bytemuck::cast_slice(&edge_anchor);
210        out_buf[edge_anchor_offset..edge_anchor_offset + edge_anc_bytes.len()]
211            .copy_from_slice(edge_anc_bytes);
212        cursor = align64(edge_anchor_offset + align64(edge_anc_bytes.len()));
213
214        let csc_col_ptr_offset = align64(cursor);
215        let csc_ptr_bytes: &[u8] = bytemuck::cast_slice(&csc_col_ptr);
216        out_buf[csc_col_ptr_offset..csc_col_ptr_offset + csc_ptr_bytes.len()]
217            .copy_from_slice(csc_ptr_bytes);
218        cursor = align64(csc_col_ptr_offset + align64(csc_ptr_bytes.len()));
219
220        let csc_row_idx_offset = align64(cursor);
221        let csc_row_bytes: &[u8] = bytemuck::cast_slice(&csc_row_idx);
222        out_buf[csc_row_idx_offset..csc_row_idx_offset + csc_row_bytes.len()]
223            .copy_from_slice(csc_row_bytes);
224        cursor = align64(csc_row_idx_offset + align64(csc_row_bytes.len()));
225
226        let edge_weight_offset = if g.edge_weights.is_some() {
227            let off = align64(cursor);
228            let w_bytes: &[u8] = bytemuck::cast_slice(&sorted_weights);
229            out_buf[off..off + w_bytes.len()].copy_from_slice(w_bytes);
230            cursor = align64(off + align64(w_bytes.len()));
231            off as u32
232        } else {
233            0
234        };
235
236        let mut gh = HarbouredGraphHeader {
237            graph_id: g.graph_id,
238            parent_geometry_id: spec.geometry_id,
239            anchor_table_offset: anchor_table_offset as u32,
240            csr_row_ptr_offset: csr_row_ptr_offset as u32,
241            csr_col_idx_offset: csr_col_idx_offset as u32,
242            edge_anchor_offset: edge_anchor_offset as u32,
243            csc_col_ptr_offset: csc_col_ptr_offset as u32,
244            csc_row_idx_offset: csc_row_idx_offset as u32,
245            edge_weight_offset,
246            vertex_count: v_count as u32,
247            edge_count: e_count as u32,
248            context_and_state_mask: g.context_and_state_mask,
249            embed_role: g.embed_role as u8,
250            morphology: g.morphology as u8,
251            invariants: g.invariants,
252            crc32c: 0,
253        };
254        let gh_bytes = bytemuck::bytes_of(&gh);
255        let mut crc_state = crc32c_update(0xFFFF_FFFF, &gh_bytes[..60]);
256        crc_state = crc32c_update(crc_state, anchor_bytes);
257        crc_state = crc32c_update(crc_state, row_ptr_bytes);
258        crc_state = crc32c_update(crc_state, col_idx_bytes);
259        crc_state = crc32c_update(crc_state, edge_anc_bytes);
260        crc_state = crc32c_update(crc_state, csc_ptr_bytes);
261        crc_state = crc32c_update(crc_state, csc_row_bytes);
262        if g.edge_weights.is_some() {
263            crc_state = crc32c_update(crc_state, bytemuck::cast_slice(&sorted_weights));
264        }
265        gh.crc32c = !crc_state;
266
267        let hdr_off = graph_dir_offset + slot * 64;
268        out_buf[hdr_off..hdr_off + 64].copy_from_slice(bytemuck::bytes_of(&gh));
269    }
270
271    let euler = (spec.cell_counts[0] as i32)
272        .wrapping_sub(spec.cell_counts[1] as i32)
273        .wrapping_add(spec.cell_counts[2] as i32)
274        .wrapping_sub(spec.cell_counts[3] as i32);
275
276    let mut geom_hdr = PoetGeometryHeader {
277        geometry_id: spec.geometry_id,
278        construct_schema_hash: spec.construct_schema_hash,
279        manifold_id: spec.manifold_id,
280        cell_0_count: spec.cell_counts[0],
281        cell_1_count: spec.cell_counts[1],
282        cell_2_count: spec.cell_counts[2],
283        cell_3_count: spec.cell_counts[3],
284        geometry_payload_offset: 0,
285        ddg_operators_offset: 0,
286        graph_dir_offset: graph_dir_offset as u32,
287        harboured_graph_count: m as u16,
288        active_graph_slot: spec.active_graph_slot,
289        euler_characteristic: euler,
290        complex_kind: spec.complex_kind as u8,
291        metric_kind: spec.metric_kind as u8,
292        ambient_dim: spec.ambient_dim,
293        intrinsic_dim: spec.intrinsic_dim,
294        crc32c: 0,
295    };
296    let geom_bytes = bytemuck::bytes_of(&geom_hdr);
297    let mut state = crc32c_update(0xFFFF_FFFF, &geom_bytes[..60]);
298    state = crc32c_update(state, &out_buf[64..total_bytes]);
299    geom_hdr.crc32c = !state;
300    out_buf[0..64].copy_from_slice(bytemuck::bytes_of(&geom_hdr));
301
302    let _ = crc32c;
303    Ok(total_bytes)
304}
305
306/// Apply live `TopologicalDeltaEntry` mutations targeting `slot` onto `base_spec` and deduplicate.
307pub fn seal_harboured_graph_deltas(
308    base_spec: &mut UnsealedGraphSpec,
309    deltas: &[TopologicalDeltaEntry],
310    slot: u16,
311) {
312    let mut slot_deltas: Vec<TopologicalDeltaEntry> = deltas
313        .iter()
314        .copied()
315        .filter(|d| d.graph_slot() as u16 == slot)
316        .collect();
317    slot_deltas.sort_unstable_by_key(|d| d.seq_no);
318
319    for d in slot_deltas {
320        match d.op_kind() {
321            DeltaOpKind::Tombstone => {
322                let mut i = 0usize;
323                while i < base_spec.edges.len() {
324                    if base_spec.edges[i].0 == d.source_vertex
325                        && base_spec.edges[i].1 == d.target_vertex
326                    {
327                        base_spec.edges.remove(i);
328                        if let Some(ref mut ws) = base_spec.edge_weights {
329                            if i < ws.len() {
330                                ws.remove(i);
331                            }
332                        }
333                    } else {
334                        i += 1;
335                    }
336                }
337            }
338            DeltaOpKind::Insert | DeltaOpKind::Reify => {
339                if d.op_kind() == DeltaOpKind::Reify {
340                    base_spec.invariants |= TopologyInvariants::REIFIED_EDGES;
341                }
342                if let Some(pos) = base_spec
343                    .edges
344                    .iter()
345                    .position(|&(u, v, _)| u == d.source_vertex && v == d.target_vertex)
346                {
347                    base_spec.edges[pos].2 = d.edge_anchor_idx;
348                } else {
349                    base_spec
350                        .edges
351                        .push((d.source_vertex, d.target_vertex, d.edge_anchor_idx));
352                    if let Some(ref mut ws) = base_spec.edge_weights {
353                        ws.push(1.0);
354                    }
355                }
356            }
357            DeltaOpKind::AnchorBind => {
358                if let Some(anchor) = base_spec.anchors.get_mut(d.source_vertex as usize) {
359                    anchor.cell_index = d.target_vertex;
360                    anchor.anchor_domain = d.anchor_domain() as u8;
361                }
362            }
363        }
364    }
365
366    if let Some(ref mut ws) = base_spec.edge_weights {
367        let mut combined: Vec<((u32, u32, u32), f32)> = base_spec
368            .edges
369            .iter()
370            .copied()
371            .zip(ws.iter().copied())
372            .collect();
373        combined.sort_unstable_by(|a, b| a.0.cmp(&b.0));
374        combined.dedup_by(|a, b| a.0 .0 == b.0 .0 && a.0 .1 == b.0 .1);
375        base_spec.edges = combined.iter().map(|&(e, _)| e).collect();
376        *ws = combined.iter().map(|&(_, w)| w).collect();
377    } else {
378        base_spec.edges.sort_unstable();
379        base_spec.edges.dedup_by(|a, b| a.0 == b.0 && a.1 == b.1);
380    }
381}
382
383#[cfg(test)]
384mod tests {
385    use super::*;
386    use crate::specialized_libs::computational_geometry::{
387        build_triangle_half_edges, required_edge_slots, EdgeSlot, HalfEdge,
388    };
389    use crate::topology::delta_ring::TopologicalDeltaRing;
390    use crate::topology::geometry_view::PoetGeometryView;
391    use crate::topology::header::AnchorDomain;
392    use crate::topology::induce_intrinsic::{
393        induce_combinatorial_dart_graph, induce_primal_and_dual_from_half_edges,
394        induce_simplicial_boundary_incidence,
395    };
396    use crate::topology::invariants::verify_geometry_complex_homology;
397
398    #[repr(C, align(64))]
399    struct AlignedBuf([u8; 8192]);
400
401    #[test]
402    fn induce_and_compile_multi_graph_geometry_segment_roundtrip() {
403        let triangles = [[0u32, 1, 2], [2, 1, 3]];
404        let mut half_edges = [HalfEdge::default(); 6];
405        let mut slots = vec![EdgeSlot::default(); required_edge_slots(triangles.len())];
406        build_triangle_half_edges(4, &triangles, &mut half_edges, &mut slots).unwrap();
407
408        let budget = 64 * 1024;
409        let (mut primal, dual) =
410            induce_primal_and_dual_from_half_edges(0x9001, &half_edges, 4, 2, budget).unwrap();
411        let incidence =
412            induce_simplicial_boundary_incidence(0x9001, &triangles, 4, budget).unwrap();
413        let darts = induce_combinatorial_dart_graph(0x9001, &half_edges, budget).unwrap();
414
415        // Seal a delta on primal graph (slot 0)
416        let mut ring: TopologicalDeltaRing<8> = TopologicalDeltaRing::new();
417        ring.insert_edge(0, 0, 3, 99).unwrap();
418        ring.bind_anchor(0, 3, 3, AnchorDomain::Cell0Vertex)
419            .unwrap();
420        seal_harboured_graph_deltas(&mut primal, ring.entries(), 0);
421
422        let geom_spec = UnsealedGeometrySpec {
423            geometry_id: 0x9001,
424            construct_schema_hash: 0xABCD,
425            manifold_id: 3,
426            complex_kind: GeometryComplexKind::SurfaceManifold2D,
427            metric_kind: GeometryMetricKind::Euclidean,
428            ambient_dim: 3,
429            intrinsic_dim: 2,
430            cell_counts: [4, 5, 2, 0],
431            active_graph_slot: 0,
432            graphs: vec![primal, dual, incidence, darts],
433        };
434
435        // Tight budget fails closed with BudgetExhausted
436        let mut out = AlignedBuf([0u8; 8192]);
437        assert!(matches!(
438            compile_geometry_segment(&geom_spec, 128, &mut out.0),
439            Err(TopologyError::BudgetExhausted { .. })
440        ));
441
442        let written = compile_geometry_segment(&geom_spec, budget, &mut out.0).unwrap();
443        let view = PoetGeometryView::from_segment_bytes(&out.0[..written]).unwrap();
444        assert_eq!(view.harboured_graph_count(), 4);
445        assert_eq!(verify_geometry_complex_homology(&view).unwrap(), 1);
446
447        let g0 = view.graph_at_slot(0).unwrap();
448        assert!(g0.out_neighbors(0).unwrap().contains(&3));
449        assert_ne!(g0.header().crc32c, 0);
450        assert_ne!(view.header().crc32c, 0);
451    }
452}