1use bytemuck::{Pod, Zeroable};
8use serde::{Deserialize, Serialize};
9
10use crate::topology::csr_view::HarbouredCsrView;
11use crate::topology::header::{AnchorDomain, CellAnchor, TopologyError};
12
13#[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#[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 pub edge_anchor_idx: u32,
46 pub op_domain_and_slot: u16,
50 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#[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 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 #[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 #[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 #[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 #[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 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#[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 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 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