formualizer_eval/engine/
delta_edges.rs

1use super::csr_edges::CsrEdges;
2use super::packed_coord::PackedCoord;
3use super::vertex::VertexId;
4use rustc_hash::{FxHashMap, FxHashSet};
5
6#[cfg(test)]
7mod tests {
8    use super::*;
9    use crate::engine::packed_coord::PackedCoord;
10
11    #[test]
12    fn test_delta_slab_add_edge() {
13        let csr = CsrEdges::from_adjacency(
14            vec![(0u32, vec![1u32])],
15            &[
16                PackedCoord::new(0, 0),
17                PackedCoord::new(0, 1),
18                PackedCoord::new(0, 2),
19            ],
20        );
21        let mut delta = DeltaEdgeSlab::new();
22
23        delta.add_edge(VertexId(0), VertexId(2));
24
25        let merged = delta.merged_view(&csr, VertexId(0));
26        assert_eq!(merged, vec![VertexId(1), VertexId(2)]);
27    }
28
29    #[test]
30    fn test_delta_slab_remove_edge() {
31        let csr = CsrEdges::from_adjacency(
32            vec![(0u32, vec![1u32, 2u32, 3u32])],
33            &[
34                PackedCoord::new(0, 0),
35                PackedCoord::new(0, 1),
36                PackedCoord::new(0, 2),
37                PackedCoord::new(0, 3),
38            ],
39        );
40        let mut delta = DeltaEdgeSlab::new();
41
42        delta.remove_edge(VertexId(0), VertexId(2));
43
44        let merged = delta.merged_view(&csr, VertexId(0));
45        assert_eq!(merged, vec![VertexId(1), VertexId(3)]);
46    }
47
48    #[test]
49    fn test_delta_slab_rebuild_threshold() {
50        let mut edges = CsrMutableEdges::new();
51
52        // Add 1000 edges through delta slab
53        for i in 0..1000 {
54            edges.add_edge(VertexId(i), VertexId(i + 1));
55        }
56
57        // Should trigger rebuild at threshold
58        assert!(edges.delta_size() < 100); // Delta cleared after rebuild
59    }
60
61    #[test]
62    fn test_delta_slab_multiple_operations() {
63        let csr = CsrEdges::from_adjacency(
64            vec![(0u32, vec![1u32, 2u32]), (1u32, vec![3u32])],
65            &[
66                PackedCoord::new(0, 0),
67                PackedCoord::new(0, 1),
68                PackedCoord::new(0, 2),
69                PackedCoord::new(1, 0),
70            ],
71        );
72        let mut delta = DeltaEdgeSlab::new();
73
74        // Multiple operations on same vertex
75        delta.add_edge(VertexId(0), VertexId(3));
76        delta.remove_edge(VertexId(0), VertexId(1));
77        delta.add_edge(VertexId(0), VertexId(4));
78
79        let merged = delta.merged_view(&csr, VertexId(0));
80        assert_eq!(merged, vec![VertexId(2), VertexId(3), VertexId(4)]);
81    }
82
83    #[test]
84    fn test_delta_slab_empty_base() {
85        let csr = CsrEdges::empty();
86        let mut delta = DeltaEdgeSlab::new();
87
88        delta.add_edge(VertexId(0), VertexId(1));
89        delta.add_edge(VertexId(0), VertexId(2));
90
91        let merged = delta.merged_view(&csr, VertexId(0));
92        assert_eq!(merged, vec![VertexId(1), VertexId(2)]);
93    }
94
95    #[test]
96    fn test_delta_slab_remove_nonexistent() {
97        let csr = CsrEdges::from_adjacency(
98            vec![(0u32, vec![1u32])],
99            &[PackedCoord::new(0, 0), PackedCoord::new(0, 1)],
100        );
101        let mut delta = DeltaEdgeSlab::new();
102
103        // Remove edge that doesn't exist
104        delta.remove_edge(VertexId(0), VertexId(2));
105
106        let merged = delta.merged_view(&csr, VertexId(0));
107        assert_eq!(merged, vec![VertexId(1)]); // No change
108    }
109
110    #[test]
111    fn test_delta_slab_apply_to_csr() {
112        let csr = CsrEdges::from_adjacency(
113            vec![(0u32, vec![1u32]), (1u32, vec![2u32]), (2u32, vec![])],
114            &[
115                PackedCoord::new(0, 0),
116                PackedCoord::new(0, 1),
117                PackedCoord::new(1, 0),
118            ],
119        );
120
121        let mut delta = DeltaEdgeSlab::new();
122        delta.add_edge(VertexId(0), VertexId(2));
123        delta.remove_edge(VertexId(1), VertexId(2));
124        delta.add_edge(VertexId(2), VertexId(0));
125
126        // Apply delta and get new CSR
127        let coords = vec![
128            PackedCoord::new(0, 0),
129            PackedCoord::new(0, 1),
130            PackedCoord::new(1, 0),
131        ];
132        let vertex_ids = vec![0u32, 1u32, 2u32];
133        let new_csr = delta.apply_to_csr(&csr, &coords, &vertex_ids);
134
135        assert_eq!(new_csr.out_edges(VertexId(0)), &[VertexId(1), VertexId(2)]);
136        assert_eq!(new_csr.out_edges(VertexId(1)), &[]);
137        assert_eq!(new_csr.out_edges(VertexId(2)), &[VertexId(0)]);
138    }
139
140    #[test]
141    fn test_mutable_edges_auto_rebuild() {
142        let mut edges = CsrMutableEdges::with_coords(vec![
143            PackedCoord::new(0, 0),
144            PackedCoord::new(0, 1),
145            PackedCoord::new(1, 0),
146        ]);
147
148        // Add initial edges
149        edges.add_edge(VertexId(0), VertexId(1));
150        edges.add_edge(VertexId(1), VertexId(2));
151
152        // Perform many operations to trigger rebuild
153        for _ in 0..500 {
154            edges.add_edge(VertexId(2), VertexId(0));
155            edges.remove_edge(VertexId(2), VertexId(0));
156        }
157
158        // Check that rebuild happened (delta is small)
159        assert!(edges.delta_size() < 50);
160
161        // Verify edges are still correct
162        assert_eq!(edges.out_edges(VertexId(0)), vec![VertexId(1)]);
163        assert_eq!(edges.out_edges(VertexId(1)), vec![VertexId(2)]);
164    }
165
166    #[test]
167    fn test_mutable_edges_with_offset_vertex_ids() {
168        use crate::engine::vertex_store::FIRST_NORMAL_VERTEX;
169
170        let mut edges = CsrMutableEdges::new();
171
172        // Add vertices with IDs starting at FIRST_NORMAL_VERTEX (1024)
173        let base_id = FIRST_NORMAL_VERTEX;
174        edges.add_vertex(PackedCoord::new(0, 0), base_id);
175        edges.add_vertex(PackedCoord::new(0, 1), base_id + 1);
176        edges.add_vertex(PackedCoord::new(1, 0), base_id + 2);
177
178        // Add edges using offset IDs
179        edges.add_edge(VertexId(base_id), VertexId(base_id + 1));
180        edges.add_edge(VertexId(base_id + 1), VertexId(base_id + 2));
181        edges.add_edge(VertexId(base_id + 2), VertexId(base_id));
182
183        // Verify edges work correctly
184        assert_eq!(
185            edges.out_edges(VertexId(base_id)),
186            vec![VertexId(base_id + 1)]
187        );
188        assert_eq!(
189            edges.out_edges(VertexId(base_id + 1)),
190            vec![VertexId(base_id + 2)]
191        );
192        assert_eq!(
193            edges.out_edges(VertexId(base_id + 2)),
194            vec![VertexId(base_id)]
195        );
196
197        // Force rebuild and verify again
198        edges.rebuild();
199        assert_eq!(
200            edges.out_edges(VertexId(base_id)),
201            vec![VertexId(base_id + 1)]
202        );
203        assert_eq!(
204            edges.out_edges(VertexId(base_id + 1)),
205            vec![VertexId(base_id + 2)]
206        );
207        assert_eq!(
208            edges.out_edges(VertexId(base_id + 2)),
209            vec![VertexId(base_id)]
210        );
211    }
212
213    #[test]
214    fn test_csr_coord_update() {
215        let mut edges = CsrMutableEdges::new();
216
217        edges.add_vertex(PackedCoord::new(1, 1), 1024);
218        edges.add_vertex(PackedCoord::new(2, 2), 1025);
219        edges.add_edge(VertexId(1024), VertexId(1025));
220
221        // Update coordinate
222        edges.update_coord(VertexId(1024), PackedCoord::new(5, 5));
223
224        // Verify sorting remains correct after rebuild
225        edges.rebuild();
226        let out = edges.out_edges(VertexId(1024));
227        assert_eq!(out, vec![VertexId(1025)]);
228    }
229
230    #[test]
231    fn test_last_op_wins_add_then_remove() {
232        let csr = CsrEdges::from_adjacency(vec![(0u32, vec![])], &[PackedCoord::new(0, 0)]);
233        let mut delta = DeltaEdgeSlab::new();
234        delta.add_edge(VertexId(0), VertexId(1));
235        delta.remove_edge(VertexId(0), VertexId(1));
236        let merged = delta.merged_view(&csr, VertexId(0));
237        assert_eq!(merged, vec![]);
238    }
239
240    #[test]
241    fn test_last_op_wins_remove_then_add() {
242        let csr = CsrEdges::from_adjacency(vec![(0u32, vec![])], &[PackedCoord::new(0, 0)]);
243        let mut delta = DeltaEdgeSlab::new();
244        delta.remove_edge(VertexId(0), VertexId(1));
245        delta.add_edge(VertexId(0), VertexId(1));
246        let merged = delta.merged_view(&csr, VertexId(0));
247        assert_eq!(merged, vec![VertexId(1)]);
248    }
249
250    #[test]
251    fn test_dedup_additions_and_sorted() {
252        let csr = CsrEdges::from_adjacency(
253            vec![(0u32, vec![2u32])],
254            &[
255                PackedCoord::new(0, 0),
256                PackedCoord::new(0, 1),
257                PackedCoord::new(0, 2),
258            ],
259        );
260        let mut delta = DeltaEdgeSlab::new();
261        // Add duplicates and out-of-order ids
262        delta.add_edge(VertexId(0), VertexId(1));
263        delta.add_edge(VertexId(0), VertexId(3));
264        delta.add_edge(VertexId(0), VertexId(1)); // duplicate
265        let merged = delta.merged_view(&csr, VertexId(0));
266        // Should be deduped and sorted by VertexId
267        assert_eq!(merged, vec![VertexId(1), VertexId(2), VertexId(3)]);
268    }
269
270    #[test]
271    fn test_end_batch_rebuilds_on_coord_change_only() {
272        let mut edges =
273            CsrMutableEdges::with_coords(vec![PackedCoord::new(0, 0), PackedCoord::new(0, 1)]);
274        edges.begin_batch();
275        edges.update_coord(VertexId(0), PackedCoord::new(0, 2));
276        // No ops, only coord changed; end_batch should rebuild due to coord_dirty
277        edges.end_batch();
278        // Smoke: out_edges call should not panic and reflect empty edges
279        assert_eq!(edges.out_edges(VertexId(0)), Vec::<VertexId>::new());
280    }
281}
282
283/// Delta slab for accumulating edge mutations between CSR rebuilds
284///
285/// Provides O(1) edge mutations by tracking additions and removals
286/// separately, merging them with the base CSR on read.
287#[derive(Debug)]
288pub struct DeltaEdgeSlab {
289    /// New edges to add, grouped by source vertex (set semantics to avoid duplicates)
290    additions: FxHashMap<VertexId, FxHashSet<VertexId>>,
291
292    /// Edges to remove, stored as sets for O(1) lookup
293    removals: FxHashMap<VertexId, FxHashSet<VertexId>>,
294
295    /// Total operation count for rebuild threshold
296    op_count: usize,
297
298    /// Flag indicating coordinates have changed and rebuild is needed
299    coord_changed: bool,
300}
301
302impl DeltaEdgeSlab {
303    /// Create a new empty delta slab
304    pub fn new() -> Self {
305        Self {
306            additions: FxHashMap::default(),
307            removals: FxHashMap::default(),
308            op_count: 0,
309            coord_changed: false,
310        }
311    }
312
313    /// Add an edge from source to target
314    pub fn add_edge(&mut self, from: VertexId, to: VertexId) {
315        // Last-op-wins: if previously removed, cancel the removal
316        if let Some(rem) = self.removals.get_mut(&from) {
317            rem.remove(&to);
318        }
319        // Insert into additions set
320        self.additions.entry(from).or_default().insert(to);
321        self.op_count += 1;
322    }
323
324    /// Remove an edge from source to target
325    pub fn remove_edge(&mut self, from: VertexId, to: VertexId) {
326        // Last-op-wins: if previously added in this slab, cancel the addition
327        if let Some(adds) = self.additions.get_mut(&from) {
328            adds.remove(&to);
329        }
330        // Record removal
331        self.removals.entry(from).or_default().insert(to);
332        self.op_count += 1;
333    }
334
335    /// Get a merged view of edges for a vertex, combining CSR and delta
336    pub fn merged_view(&self, csr: &CsrEdges, v: VertexId) -> Vec<VertexId> {
337        // Start from base CSR out-edges
338        let mut result: Vec<_> = csr.out_edges(v).to_vec();
339        // Remove edges marked for deletion
340        if let Some(removes) = self.removals.get(&v) {
341            result.retain(|e| !removes.contains(e));
342        }
343        // Add new edges (set semantics)
344        if let Some(adds) = self.additions.get(&v) {
345            result.extend(adds.iter().copied());
346        }
347        // Dedup deterministically and sort by VertexId for stable order
348        let mut seen: FxHashSet<VertexId> = FxHashSet::default();
349        result.retain(|e| seen.insert(*e));
350        result.sort_by_key(|e| e.0);
351        result
352    }
353
354    /// Check if the delta needs to be applied (rebuild threshold reached)
355    pub fn needs_rebuild(&self) -> bool {
356        self.op_count >= 1000 || self.coord_changed
357    }
358
359    /// Mark that coordinates have changed and rebuild is needed
360    pub fn mark_dirty(&mut self) {
361        self.coord_changed = true;
362    }
363
364    /// Get the current operation count
365    pub fn op_count(&self) -> usize {
366        self.op_count
367    }
368
369    /// Clear the delta slab
370    pub fn clear(&mut self) {
371        self.additions.clear();
372        self.removals.clear();
373        self.op_count = 0;
374        self.coord_changed = false;
375    }
376
377    /// Apply delta to CSR, creating a new CSR structure
378    pub fn apply_to_csr(
379        &self,
380        base: &CsrEdges,
381        coords: &[PackedCoord],
382        vertex_ids: &[u32],
383    ) -> CsrEdges {
384        let mut adjacency = Vec::with_capacity(vertex_ids.len());
385
386        // Build new adjacency list by merging base and delta
387        for &vid in vertex_ids {
388            let v = VertexId(vid);
389            let merged = self.merged_view(base, v);
390
391            // Convert to u32 for adjacency format
392            let targets: Vec<u32> = merged.into_iter().map(|id| id.0).collect();
393
394            adjacency.push((vid, targets));
395        }
396
397        CsrEdges::from_adjacency(adjacency, coords)
398    }
399}
400
401impl Default for DeltaEdgeSlab {
402    fn default() -> Self {
403        Self::new()
404    }
405}
406
407/// Mutable edge storage combining CSR base with delta slab
408///
409/// Provides efficient edge mutations with automatic rebuild when
410/// delta grows too large.
411#[derive(Debug)]
412pub struct CsrMutableEdges {
413    /// Base CSR structure (immutable between rebuilds)
414    base: CsrEdges,
415
416    /// Delta slab for mutations
417    delta: DeltaEdgeSlab,
418
419    /// Vertex coordinates for deterministic ordering
420    coords: Vec<PackedCoord>,
421
422    /// Vertex IDs corresponding to coords array
423    vertex_ids: Vec<u32>,
424
425    /// Batch mode flag - when true, skip automatic rebuilds
426    batch_mode: bool,
427}
428
429impl CsrMutableEdges {
430    /// Create new mutable edges with empty base
431    pub fn new() -> Self {
432        Self {
433            base: CsrEdges::empty(),
434            delta: DeltaEdgeSlab::new(),
435            coords: Vec::new(),
436            vertex_ids: Vec::new(),
437            batch_mode: false,
438        }
439    }
440
441    /// Create with initial vertex coordinates
442    pub fn with_coords(coords: Vec<PackedCoord>) -> Self {
443        let num_vertices = coords.len();
444        let vertex_ids: Vec<u32> = (0..num_vertices as u32).collect();
445        let adjacency: Vec<_> = vertex_ids.iter().map(|&id| (id, Vec::new())).collect();
446
447        Self {
448            base: CsrEdges::from_adjacency(adjacency, &coords),
449            delta: DeltaEdgeSlab::new(),
450            coords,
451            vertex_ids,
452            batch_mode: false,
453        }
454    }
455
456    /// Add an edge, rebuilding if threshold reached
457    pub fn add_edge(&mut self, from: VertexId, to: VertexId) {
458        self.delta.add_edge(from, to);
459        self.maybe_rebuild();
460    }
461
462    /// Remove an edge, rebuilding if threshold reached
463    pub fn remove_edge(&mut self, from: VertexId, to: VertexId) {
464        self.delta.remove_edge(from, to);
465        self.maybe_rebuild();
466    }
467
468    /// Get outgoing edges for a vertex (merged view)
469    pub fn out_edges(&self, v: VertexId) -> Vec<VertexId> {
470        self.delta.merged_view(&self.base, v)
471    }
472
473    /// Get incoming edges from base CSR (delta not applied for performance)
474    /// After rebuild, this will include all changes
475    pub fn in_edges(&self, v: VertexId) -> &[VertexId] {
476        self.base.in_edges(v)
477    }
478
479    /// Get the current delta size
480    pub fn delta_size(&self) -> usize {
481        self.delta.op_count()
482    }
483
484    /// Force a rebuild of the CSR structure
485    pub fn rebuild(&mut self) {
486        if self.delta.op_count() > 0 || self.delta.needs_rebuild() {
487            self.base = self
488                .delta
489                .apply_to_csr(&self.base, &self.coords, &self.vertex_ids);
490            self.delta.clear();
491        }
492    }
493
494    /// Check and perform rebuild if threshold reached
495    fn maybe_rebuild(&mut self) {
496        if !self.batch_mode && self.delta.needs_rebuild() {
497            self.rebuild();
498        }
499    }
500
501    /// Enter batch mode - defer rebuilds until end_batch() is called
502    pub fn begin_batch(&mut self) {
503        self.batch_mode = true;
504    }
505
506    /// Exit batch mode and rebuild if needed
507    pub fn end_batch(&mut self) {
508        self.batch_mode = false;
509        if self.delta.op_count() > 0 || self.delta.needs_rebuild() {
510            self.rebuild();
511        }
512    }
513
514    /// Add a new vertex with its coordinate and ID
515    pub fn add_vertex(&mut self, coord: PackedCoord, vertex_id: u32) -> usize {
516        let idx = self.coords.len();
517        self.coords.push(coord);
518        self.vertex_ids.push(vertex_id);
519
520        // Rebuild base to include new vertex
521        // This is necessary to maintain CSR structure consistency
522        self.rebuild();
523
524        idx
525    }
526
527    /// Add many vertices at once; single rebuild at end.
528    pub fn add_vertices_batch(&mut self, items: &[(PackedCoord, u32)]) {
529        if items.is_empty() {
530            return;
531        }
532        let start_len = self.coords.len();
533        self.coords.reserve(items.len());
534        self.vertex_ids.reserve(items.len());
535        for (coord, vid) in items {
536            self.coords.push(*coord);
537            self.vertex_ids.push(*vid);
538        }
539        // Single rebuild to incorporate all new vertices.
540        self.rebuild();
541        debug_assert_eq!(self.coords.len(), start_len + items.len());
542    }
543
544    /// Update coordinate for a vertex in the cache
545    /// Marks for rebuild to maintain sort order
546    pub fn update_coord(&mut self, vertex_id: VertexId, new_coord: PackedCoord) {
547        // Find vertex in vertex_ids array
548        if let Some(pos) = self.vertex_ids.iter().position(|&id| id == vertex_id.0) {
549            self.coords[pos] = new_coord;
550            // Force rebuild on next access to maintain sort invariants
551            self.delta.mark_dirty();
552        }
553    }
554
555    /// Build underlying CSR directly from adjacency and provided coords/ids.
556    /// This replaces the current base and clears the delta slab.
557    pub fn build_from_adjacency(
558        &mut self,
559        adjacency: Vec<(u32, Vec<u32>)>,
560        coords: Vec<PackedCoord>,
561        vertex_ids: Vec<u32>,
562    ) {
563        self.base = CsrEdges::from_adjacency(adjacency, &coords);
564        self.coords = coords;
565        self.vertex_ids = vertex_ids;
566        self.delta.clear();
567    }
568}
569
570impl Default for CsrMutableEdges {
571    fn default() -> Self {
572        Self::new()
573    }
574}
formualizer_eval/engine/delta_edges.rs

formualizer_eval/engine/
delta_edges.rs
