formualizer_eval/engine/
spill.rs

1//! Spill interfaces (shim) for reserve/write/commit/rollback lifecycle.
2//! Phase 2: Introduce types only; implementation can delegate to current graph methods.
3
4use crate::engine::graph::DependencyGraph;
5use crate::engine::interval_tree::IntervalTree;
6use crate::engine::vertex::VertexId;
7use crate::engine::{SpillBufferMode, SpillCancellationPolicy, SpillConfig, SpillVisibility};
8use crate::reference::CellRef;
9use formualizer_common::{ExcelError, ExcelErrorKind, LiteralValue};
10use rustc_hash::{FxHashMap, FxHashSet};
11
12#[derive(Debug, Clone, Copy)]
13pub struct SpillShape {
14    pub rows: u32,
15    pub cols: u32,
16}
17
18#[derive(Debug)]
19pub struct SpillMeta {
20    pub epoch: u64,
21    pub config: SpillConfig,
22}
23
24#[derive(Debug)]
25pub struct SpillReservation {
26    pub anchor: CellRef,
27    pub shape: SpillShape,
28    pub writer_mode: SpillBufferMode,
29    pub visibility: SpillVisibility,
30    pub cancellation: SpillCancellationPolicy,
31}
32
33pub trait SpillWriter {
34    fn write_row(&mut self, r: u32, values: &[LiteralValue]) -> Result<(), ExcelError>;
35}
36
37pub trait SpillManager {
38    fn reserve(
39        &mut self,
40        graph: &DependencyGraph,
41        anchor: CellRef,
42        shape: SpillShape,
43        meta: SpillMeta,
44    ) -> Result<(SpillReservation, Box<dyn SpillWriter>), ExcelError>;
45
46    fn commit(&mut self, reservation: SpillReservation) -> Result<(), ExcelError>;
47
48    fn rollback(&mut self, reservation: SpillReservation);
49}
50
51/// Generic, reusable region lock manager per sheet.
52#[derive(Default, Debug)]
53pub struct RegionLockManager {
54    next_id: u64,
55    // Per-sheet interval indexes for rows and cols
56    row_trees: FxHashMap<u32, IntervalTree<u64>>, // sheet_id -> row intervals → lock ids
57    col_trees: FxHashMap<u32, IntervalTree<u64>>, // sheet_id -> col intervals → lock ids
58    locks: FxHashMap<u64, RegionLock>,            // id -> lock
59}
60
61#[derive(Debug, Clone, Copy)]
62pub struct Region {
63    pub sheet_id: u32,
64    pub row_start: u32,
65    pub row_end: u32,
66    pub col_start: u32,
67    pub col_end: u32,
68}
69
70#[derive(Debug)]
71struct RegionLock {
72    id: u64,
73    owner: VertexId,
74    region: Region,
75}
76
77impl RegionLockManager {
78    pub fn reserve(&mut self, region: Region, owner: VertexId) -> Result<u64, ExcelError> {
79        // Fast path: zero-size or invalid region is treated as no-op
80        if region.row_end < region.row_start || region.col_end < region.col_start {
81            return Ok(0);
82        }
83        let row_tree = self.row_trees.entry(region.sheet_id).or_default();
84        let col_tree = self.col_trees.entry(region.sheet_id).or_default();
85
86        // Gather overlapping row locks
87        let mut row_ids: FxHashSet<u64> = FxHashSet::default();
88        for (_low, _high, set) in row_tree.query(region.row_start, region.row_end) {
89            for id in set {
90                row_ids.insert(id);
91            }
92        }
93        if !row_ids.is_empty() {
94            let mut col_ids: FxHashSet<u64> = FxHashSet::default();
95            for (_low, _high, set) in col_tree.query(region.col_start, region.col_end) {
96                for id in set {
97                    col_ids.insert(id);
98                }
99            }
100            // Intersect
101            let conflict = row_ids.iter().any(|id| col_ids.contains(id));
102            if conflict {
103                return Err(ExcelError::new(ExcelErrorKind::Spill)
104                    .with_message("Region reserved by another spill"));
105            }
106        }
107
108        // Allocate lock id and insert
109        self.next_id = self.next_id.wrapping_add(1).max(1);
110        let id = self.next_id;
111        row_tree.insert(region.row_start, region.row_end, id);
112        col_tree.insert(region.col_start, region.col_end, id);
113        self.locks.insert(id, RegionLock { id, owner, region });
114        Ok(id)
115    }
116
117    pub fn release(&mut self, id: u64) {
118        if id == 0 {
119            return;
120        }
121        if let Some(lock) = self.locks.remove(&id) {
122            if let Some(tree) = self.row_trees.get_mut(&lock.region.sheet_id) {
123                tree.remove(lock.region.row_start, lock.region.row_end, &lock.id);
124            }
125            if let Some(tree) = self.col_trees.get_mut(&lock.region.sheet_id) {
126                tree.remove(lock.region.col_start, lock.region.col_end, &lock.id);
127            }
128        }
129    }
130
131    #[cfg(test)]
132    pub fn active_count(&self, sheet_id: u32) -> usize {
133        let r = self.row_trees.get(&sheet_id).map(|t| t.len()).unwrap_or(0);
134        let c = self.col_trees.get(&sheet_id).map(|t| t.len()).unwrap_or(0);
135        r.max(c)
136    }
137}
formualizer_eval/engine/spill.rs

formualizer_eval/engine/
spill.rs
