formualizer_eval/engine/
vertex_store.rs

1use super::addr::{GridAddr, VertexAddr};
2use super::vertex::{VertexId, VertexKind};
3use crate::SheetId;
4use std::sync::atomic::{AtomicU8, Ordering};
5
6#[cfg(test)]
7mod tests {
8    use super::*;
9    use crate::engine::addr::SymbolAddr;
10
11    fn grid(row: u32, col: u32) -> VertexAddr {
12        VertexAddr::grid(GridAddr::new(row, col))
13    }
14
15    #[test]
16    fn test_vertex_store_allocation() {
17        let mut store = VertexStore::new();
18        let id = store.allocate(grid(10, 20), 1, 0x01);
19        assert_eq!(store.addr(id), grid(10, 20));
20        assert_eq!(store.sheet_id(id), 1);
21        assert_eq!(store.flags(id), 0x01);
22    }
23
24    #[test]
25    fn prepared_batch_vertex_overflow_is_checked_before_mutation() {
26        let mut store = VertexStore::new();
27        store.len = u32::MAX as usize - FIRST_NORMAL_VERTEX as usize + 1;
28        let before = (
29            store.coords.len(),
30            store.sheet_kind.len(),
31            store.flags.len(),
32        );
33        assert_eq!(
34            store.try_allocate_batch(&[(grid(0, 0), 0, 0)], &[VertexId(FIRST_NORMAL_VERTEX)],),
35            Err(VertexBatchAllocationError::IdExhausted)
36        );
37        assert_eq!(
38            before,
39            (
40                store.coords.len(),
41                store.sheet_kind.len(),
42                store.flags.len()
43            )
44        );
45    }
46
47    #[test]
48    fn prepared_batch_reserved_id_mismatch_is_checked_before_mutation() {
49        let mut store = VertexStore::new();
50        let before = (store.len(), store.coords.len(), store.flags.len());
51        assert_eq!(
52            store.try_allocate_batch(&[(grid(0, 0), 0, 0)], &[VertexId(FIRST_NORMAL_VERTEX + 1)],),
53            Err(VertexBatchAllocationError::ReservedIdsMismatch)
54        );
55        assert_eq!(before, (store.len(), store.coords.len(), store.flags.len()));
56    }
57
58    #[test]
59    fn test_vertex_store_grow() {
60        let mut store = VertexStore::with_capacity(1000);
61        for i in 0..10_000 {
62            store.allocate(grid(i, i), 0, 0);
63        }
64        assert_eq!(store.len(), 10_000);
65        // Note: While VertexStore itself is 64-byte aligned,
66        // the Vec allocations inside may not be. This is fine
67        // as the important thing is data locality, not alignment.
68    }
69
70    #[test]
71    fn test_vertex_store_capacity() {
72        let store = VertexStore::with_capacity(100);
73        assert!(store.coords.capacity() >= 100);
74        assert!(store.sheet_kind.capacity() >= 100);
75        assert!(store.flags.capacity() >= 100);
76        assert!(store.value_ref.capacity() >= 100);
77        assert!(store.edge_offset.capacity() >= 100);
78    }
79
80    #[test]
81    fn test_vertex_store_accessors() {
82        let mut store = VertexStore::new();
83        let id = store.allocate(grid(5, 10), 3, 0x03);
84
85        // Test coord access
86        let position = store
87            .grid_addr(id)
88            .expect("cell vertices carry a grid position");
89        assert_eq!(position.row(), 5);
90        assert_eq!(position.col(), 10);
91
92        // Test sheet_id access
93        assert_eq!(store.sheet_id(id), 3);
94
95        // Test flags access
96        assert_eq!(store.flags(id), 0x03);
97        assert!(store.is_dirty(id));
98        assert!(store.is_volatile(id));
99
100        // Test kind access/update
101        store.set_kind(id, VertexKind::Cell);
102        assert_eq!(store.kind(id), VertexKind::Cell);
103    }
104
105    #[test]
106    fn symbol_vertices_have_no_grid_position() {
107        let mut store = VertexStore::new();
108        let cell = store.allocate(grid(3, 4), 0, 0);
109        let symbol = store.allocate(VertexAddr::symbol(SymbolAddr::new(0)), 0, 0);
110
111        assert_eq!(store.grid_addr(cell), Some(GridAddr::new(3, 4)));
112        assert_eq!(store.grid_addr(symbol), None);
113        assert!(store.addr(symbol).is_symbol());
114        assert_eq!(store.addr(symbol).as_symbol(), Some(SymbolAddr::new(0)));
115    }
116
117    /// The edge coordinate arrays and the vertex store hold one address per vertex,
118    /// parallel to adjacency. Tagging the symbol space must not widen that slot.
119    #[test]
120    fn stored_address_element_size_is_unchanged() {
121        assert_eq!(std::mem::size_of::<VertexAddr>(), 8);
122        assert_eq!(
123            std::mem::size_of::<VertexAddr>(),
124            std::mem::size_of::<formualizer_common::Coord>(),
125        );
126    }
127
128    #[test]
129    fn test_reserved_vertex_range() {
130        let mut store = VertexStore::new();
131        // First allocation should be >= FIRST_NORMAL_VERTEX
132        let id = store.allocate(grid(0, 0), 0, 0);
133        assert!(id.0 >= FIRST_NORMAL_VERTEX);
134    }
135
136    #[test]
137    fn test_atomic_flag_operations() {
138        let mut store = VertexStore::new();
139        let id = store.allocate(grid(0, 0), 0, 0);
140
141        // Test atomic flag updates
142        store.set_dirty(id, true);
143        assert!(store.is_dirty(id));
144
145        store.set_dirty(id, false);
146        assert!(!store.is_dirty(id));
147
148        store.set_volatile(id, true);
149        assert!(store.is_volatile(id));
150    }
151
152    #[test]
153    fn test_vertex_store_set_addr() {
154        let mut store = VertexStore::new();
155        let id = store.allocate(grid(1, 1), 0, 0);
156
157        // Update coordinate
158        store.set_addr(id, grid(5, 10));
159        assert_eq!(store.addr(id), grid(5, 10));
160    }
161
162    #[test]
163    fn test_vertex_store_atomic_flags() {
164        let mut store = VertexStore::new();
165        let id = store.allocate(grid(0, 0), 0, 0);
166
167        // Test atomic flag operations
168        store.set_dirty(id, true);
169        assert!(store.is_dirty(id));
170
171        store.set_volatile(id, true);
172        assert!(store.is_volatile(id));
173
174        // Mark as deleted (tombstone)
175        store.mark_deleted(id, true);
176        assert!(store.is_deleted(id));
177    }
178
179    #[test]
180    fn test_reserved_id_range_preserved() {
181        let mut store = VertexStore::new();
182
183        // Verify first allocation is >= FIRST_NORMAL_VERTEX
184        let id = store.allocate(grid(0, 0), 0, 0);
185        assert!(id.0 >= FIRST_NORMAL_VERTEX);
186
187        // Verify deletion uses tombstone, not physical removal
188        store.mark_deleted(id, true);
189        assert!(store.vertex_exists(id));
190        assert!(store.is_deleted(id));
191    }
192}
193
194/// Reserved vertex ID range constants
195pub const FIRST_NORMAL_VERTEX: u32 = 1024;
196pub const RANGE_VERTEX_START: u32 = 0;
197pub const EXTERNAL_VERTEX_START: u32 = 256;
198
199#[derive(Clone, Copy, Debug, PartialEq, Eq)]
200pub(crate) enum VertexBatchAllocationError {
201    IdExhausted,
202    ReservedIdsMismatch,
203}
204
205/// Core columnar storage for vertices in Struct-of-Arrays layout
206///
207/// Memory layout optimized for cache efficiency:
208/// - 21B logical per vertex (no struct padding)
209/// - Dense columnar arrays for hot data
210/// - Atomic flags for lock-free operations
211#[repr(C, align(64))]
212#[derive(Debug)]
213pub struct VertexStore {
214    // Dense columnar arrays - 21B per vertex logical
215    coords: Vec<VertexAddr>, // 8B (packed grid position or symbol identity)
216    sheet_kind: Vec<u32>,    // 4B (16-bit sheet, 8-bit kind, 8-bit reserved)
217    flags: Vec<AtomicU8>,    // 1B (dirty|volatile|deleted|...)
218    value_ref: Vec<u32>,     // 4B (2-bit tag, 4-bit error, 26-bit index)
219    edge_offset: Vec<u32>,   // 4B (CSR offset)
220
221    // Length tracking
222    len: usize,
223}
224
225impl Default for VertexStore {
226    fn default() -> Self {
227        Self::new()
228    }
229}
230
231impl VertexStore {
232    pub fn new() -> Self {
233        Self {
234            coords: Vec::new(),
235            sheet_kind: Vec::new(),
236            flags: Vec::new(),
237            value_ref: Vec::new(),
238            edge_offset: Vec::new(),
239            len: 0,
240        }
241    }
242
243    pub fn with_capacity(capacity: usize) -> Self {
244        Self {
245            coords: Vec::with_capacity(capacity),
246            sheet_kind: Vec::with_capacity(capacity),
247            flags: Vec::with_capacity(capacity),
248            value_ref: Vec::with_capacity(capacity),
249            edge_offset: Vec::with_capacity(capacity),
250            len: 0,
251        }
252    }
253
254    /// Reserve additional capacity for upcoming vertex allocations.
255    pub fn reserve(&mut self, additional: usize) {
256        if additional == 0 {
257            return;
258        }
259        // Ensure each column has enough spare capacity
260        let target = self.len + additional;
261        if self.coords.capacity() < target {
262            self.coords.reserve(additional);
263        }
264        if self.sheet_kind.capacity() < target {
265            self.sheet_kind.reserve(additional);
266        }
267        if self.flags.capacity() < target {
268            self.flags.reserve(additional);
269        }
270        if self.value_ref.capacity() < target {
271            self.value_ref.reserve(additional);
272        }
273        if self.edge_offset.capacity() < target {
274            self.edge_offset.reserve(additional);
275        }
276    }
277
278    /// Allocate a new vertex, returning its ID
279    /// IDs start at FIRST_NORMAL_VERTEX to reserve 0-1023 for special vertices
280    pub fn allocate(&mut self, addr: VertexAddr, sheet: SheetId, flags: u8) -> VertexId {
281        let id = VertexId(self.len as u32 + FIRST_NORMAL_VERTEX);
282        debug_assert!(id.0 >= FIRST_NORMAL_VERTEX);
283
284        self.coords.push(addr);
285        self.sheet_kind.push((sheet as u32) << 16);
286        self.flags.push(AtomicU8::new(flags));
287        self.value_ref.push(0);
288        self.edge_offset.push(0);
289        self.len += 1;
290
291        id
292    }
293
294    pub(crate) fn try_allocate_batch(
295        &mut self,
296        vertices: &[(VertexAddr, SheetId, u8)],
297        expected_ids: &[VertexId],
298    ) -> Result<Vec<VertexId>, VertexBatchAllocationError> {
299        if vertices.len() != expected_ids.len() {
300            return Err(VertexBatchAllocationError::ReservedIdsMismatch);
301        }
302        let start = u32::try_from(self.len)
303            .map_err(|_| VertexBatchAllocationError::IdExhausted)?
304            .checked_add(FIRST_NORMAL_VERTEX)
305            .ok_or(VertexBatchAllocationError::IdExhausted)?;
306        let count =
307            u32::try_from(vertices.len()).map_err(|_| VertexBatchAllocationError::IdExhausted)?;
308        if count != 0 {
309            start
310                .checked_add(count - 1)
311                .ok_or(VertexBatchAllocationError::IdExhausted)?;
312        }
313        let ids: Vec<_> = (0..count).map(|offset| VertexId(start + offset)).collect();
314        if ids != expected_ids {
315            return Err(VertexBatchAllocationError::ReservedIdsMismatch);
316        }
317        self.reserve(vertices.len());
318        for &(addr, sheet, flags) in vertices {
319            self.coords.push(addr);
320            self.sheet_kind.push((u32::from(sheet)) << 16);
321            self.flags.push(AtomicU8::new(flags));
322            self.value_ref.push(0);
323            self.edge_offset.push(0);
324            self.len += 1;
325        }
326        Ok(ids)
327    }
328
329    /// Allocate a batch whose identifiers were checked against the current
330    /// store length by an exclusively-held prepared transaction.
331    pub(crate) fn allocate_prevalidated_batch(&mut self, vertices: &[(VertexAddr, SheetId, u8)]) {
332        self.reserve(vertices.len());
333        for &(addr, sheet, flags) in vertices {
334            self.allocate(addr, sheet, flags);
335        }
336    }
337
338    /// Allocate many vertices contiguously in the current store order.
339    /// Returns the assigned VertexIds in the same order as input coords.
340    pub fn allocate_contiguous(
341        &mut self,
342        sheet: SheetId,
343        addrs: &[VertexAddr],
344        flags: u8,
345    ) -> Vec<VertexId> {
346        if addrs.is_empty() {
347            return Vec::new();
348        }
349        self.reserve(addrs.len());
350        let mut ids = Vec::with_capacity(addrs.len());
351        for &addr in addrs {
352            ids.push(self.allocate(addr, sheet, flags));
353        }
354        ids
355    }
356
357    #[inline]
358    pub fn len(&self) -> usize {
359        self.len
360    }
361
362    /// Convert vertex ID to index, returning None if invalid
363    #[inline]
364    fn vertex_id_to_index(&self, id: VertexId) -> Option<usize> {
365        if id.0 < FIRST_NORMAL_VERTEX {
366            return None;
367        }
368        let idx = (id.0 - FIRST_NORMAL_VERTEX) as usize;
369        if idx >= self.len {
370            return None;
371        }
372        Some(idx)
373    }
374
375    #[inline]
376    pub fn is_empty(&self) -> bool {
377        self.len == 0
378    }
379
380    // Accessors
381    /// The vertex's address: a grid position for cells and formulas, a symbol identity
382    /// for names, tables and external sources.
383    #[inline]
384    pub fn addr(&self, id: VertexId) -> VertexAddr {
385        if let Some(idx) = self.vertex_id_to_index(id) {
386            self.coords[idx]
387        } else {
388            VertexAddr::INVALID // Invalid vertices have no address at all
389        }
390    }
391
392    /// The vertex's grid position, or `None` when it is a symbol.
393    ///
394    /// Grid-keyed structures go through this, so a symbol cannot reach them.
395    #[inline]
396    pub fn grid_addr(&self, id: VertexId) -> Option<GridAddr> {
397        self.addr(id).as_grid()
398    }
399
400    #[inline]
401    pub fn sheet_id(&self, id: VertexId) -> SheetId {
402        if let Some(idx) = self.vertex_id_to_index(id) {
403            (self.sheet_kind[idx] >> 16) as SheetId
404        } else {
405            0 // Default sheet ID for invalid vertices
406        }
407    }
408
409    #[inline]
410    pub fn kind(&self, id: VertexId) -> VertexKind {
411        if let Some(idx) = self.vertex_id_to_index(id) {
412            let tag = ((self.sheet_kind[idx] >> 8) & 0xFF) as u8;
413            VertexKind::from_tag(tag)
414        } else {
415            VertexKind::Empty // Default kind for invalid vertices
416        }
417    }
418
419    #[inline]
420    pub fn set_kind(&mut self, id: VertexId, kind: VertexKind) {
421        if let Some(idx) = self.vertex_id_to_index(id) {
422            let sheet_bits = self.sheet_kind[idx] & 0xFFFF0000;
423            self.sheet_kind[idx] = sheet_bits | ((kind.to_tag() as u32) << 8);
424        }
425    }
426
427    #[inline]
428    pub fn flags(&self, id: VertexId) -> u8 {
429        if let Some(idx) = self.vertex_id_to_index(id) {
430            self.flags[idx].load(Ordering::Acquire)
431        } else {
432            0 // Default flags for invalid vertices
433        }
434    }
435
436    #[inline]
437    pub fn is_dirty(&self, id: VertexId) -> bool {
438        self.flags(id) & 0x01 != 0
439    }
440
441    #[inline]
442    pub fn is_volatile(&self, id: VertexId) -> bool {
443        self.flags(id) & 0x02 != 0
444    }
445
446    #[inline]
447    pub fn is_deleted(&self, id: VertexId) -> bool {
448        self.flags(id) & 0x04 != 0
449    }
450
451    #[inline]
452    pub fn is_dynamic(&self, id: VertexId) -> bool {
453        self.flags(id) & 0x08 != 0
454    }
455
456    #[inline]
457    pub fn set_dirty(&self, id: VertexId, dirty: bool) {
458        if id.0 < FIRST_NORMAL_VERTEX {
459            return; // Skip invalid vertex IDs
460        }
461        let idx = (id.0 - FIRST_NORMAL_VERTEX) as usize;
462        if idx >= self.flags.len() {
463            return; // Out of bounds
464        }
465        if dirty {
466            self.flags[idx].fetch_or(0x01, Ordering::Release);
467        } else {
468            self.flags[idx].fetch_and(!0x01, Ordering::Release);
469        }
470    }
471
472    #[inline]
473    pub fn set_volatile(&self, id: VertexId, volatile: bool) {
474        if id.0 < FIRST_NORMAL_VERTEX {
475            return;
476        }
477        if let Some(idx) = self.vertex_id_to_index(id) {
478            if volatile {
479                self.flags[idx].fetch_or(0x02, std::sync::atomic::Ordering::Release);
480            } else {
481                self.flags[idx].fetch_and(!0x02, std::sync::atomic::Ordering::Release);
482            }
483        }
484    }
485
486    #[inline]
487    pub fn set_dynamic(&self, id: VertexId, dynamic: bool) {
488        if id.0 < FIRST_NORMAL_VERTEX {
489            return;
490        }
491        if let Some(idx) = self.vertex_id_to_index(id) {
492            if dynamic {
493                self.flags[idx].fetch_or(0x08, std::sync::atomic::Ordering::Release);
494            } else {
495                self.flags[idx].fetch_and(!0x08, std::sync::atomic::Ordering::Release);
496            }
497        }
498    }
499
500    #[inline]
501    pub fn value_ref(&self, id: VertexId) -> u32 {
502        if let Some(idx) = self.vertex_id_to_index(id) {
503            self.value_ref[idx]
504        } else {
505            0 // Default value ref for invalid vertices
506        }
507    }
508
509    #[inline]
510    pub fn set_value_ref(&mut self, id: VertexId, value_ref: u32) {
511        if let Some(idx) = self.vertex_id_to_index(id) {
512            self.value_ref[idx] = value_ref;
513        }
514    }
515
516    #[inline]
517    pub fn edge_offset(&self, id: VertexId) -> u32 {
518        if let Some(idx) = self.vertex_id_to_index(id) {
519            self.edge_offset[idx]
520        } else {
521            0 // Default edge offset for invalid vertices
522        }
523    }
524
525    #[inline]
526    pub fn set_edge_offset(&mut self, id: VertexId, offset: u32) {
527        if let Some(idx) = self.vertex_id_to_index(id) {
528            self.edge_offset[idx] = offset;
529        }
530    }
531
532    /// Update the address of a vertex
533    /// # Safety
534    /// Caller must ensure CSR edge cache is updated via CsrMutableEdges::update_addr
535    #[doc(hidden)]
536    pub fn set_addr(&mut self, id: VertexId, addr: VertexAddr) {
537        if let Some(idx) = self.vertex_id_to_index(id) {
538            self.coords[idx] = addr;
539        }
540    }
541
542    /// Mark vertex as deleted (tombstone strategy)
543    pub fn mark_deleted(&self, id: VertexId, deleted: bool) {
544        if let Some(idx) = self.vertex_id_to_index(id) {
545            if deleted {
546                self.flags[idx].fetch_or(0x04, Ordering::Release);
547            } else {
548                self.flags[idx].fetch_and(!0x04, Ordering::Release);
549            }
550        }
551    }
552
553    /// Check if vertex exists (may be deleted/tombstoned)
554    pub fn vertex_exists(&self, id: VertexId) -> bool {
555        self.vertex_id_to_index(id).is_some()
556    }
557
558    /// Check if vertex exists and is not deleted
559    pub fn vertex_exists_active(&self, id: VertexId) -> bool {
560        self.vertex_id_to_index(id)
561            .map(|_| !self.is_deleted(id))
562            .unwrap_or(false)
563    }
564
565    /// Get an iterator over all vertex IDs (including deleted ones)
566    pub fn all_vertices(&self) -> impl Iterator<Item = VertexId> + '_ {
567        (0..self.len).map(|i| VertexId((i as u32) + FIRST_NORMAL_VERTEX))
568    }
569}
formualizer_eval/engine/vertex_store.rs

formualizer_eval/engine/
vertex_store.rs
