1use 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#[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 pub edges: Vec<(u32, u32, u32)>,
25 pub edge_weights: Option<Vec<f32>>,
26}
27
28#[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 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
49pub 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
84pub 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 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 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
306pub 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 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 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}