formualizer_eval/engine/
vertex_store.rs

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

formualizer_eval/engine/
vertex_store.rs
