ravenrs_sheet/model/
store.rs

1//! Copy-on-write sparse cell storage.
2//!
3//! Cells live in bands of 64 rows, each band behind an `Arc`. Cloning a store (an undo snapshot)
4//! copies only the band pointers; editing a cell copies just its band.
5
6use std::collections::BTreeMap;
7use std::sync::Arc;
8
9use crate::base::{CellRef, RangeRef};
10use serde::{Deserialize, Serialize};
11
12use crate::model::cell::Cell;
13
14const BAND: u32 = 64;
15
16fn has_value(cell: &Cell) -> bool {
17    cell.has_content()
18}
19
20#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
21struct Band {
22    /// row → (col → cell)
23    rows: BTreeMap<u32, BTreeMap<u32, Cell>>,
24}
25
26#[derive(Clone, Debug, Default, PartialEq, Serialize, Deserialize)]
27pub struct CellStore {
28    bands: BTreeMap<u32, Arc<Band>>,
29    len: usize,
30}
31
32impl CellStore {
33    pub fn new() -> Self {
34        Self::default()
35    }
36    pub fn len(&self) -> usize {
37        self.len
38    }
39    pub fn is_empty(&self) -> bool {
40        self.len == 0
41    }
42    pub fn get(&self, c: CellRef) -> Option<&Cell> {
43        self.bands.get(&(c.row / BAND))?.rows.get(&c.row)?.get(&c.col)
44    }
45    /// Mutable access (copies the band if shared).
46    pub fn get_mut(&mut self, c: CellRef) -> Option<&mut Cell> {
47        let band = self.bands.get_mut(&(c.row / BAND))?;
48        if !band.rows.get(&c.row).is_some_and(|r| r.contains_key(&c.col)) {
49            return None;
50        }
51        Arc::make_mut(band).rows.get_mut(&c.row)?.get_mut(&c.col)
52    }
53    /// Stores a cell; a default (empty, unstyled) cell is removed instead.
54    pub fn set(&mut self, c: CellRef, cell: Cell) {
55        if cell.is_blank() {
56            self.remove(c);
57            return;
58        }
59        let band = Arc::make_mut(self.bands.entry(c.row / BAND).or_default());
60        if band.rows.entry(c.row).or_default().insert(c.col, cell).is_none() {
61            self.len += 1;
62        }
63    }
64    /// Puts every cell in the band its row says and recounts the length — serialized band keys
65    /// and the cached count are derived state, and the ones a file carries are not trusted. Cells
66    /// outside the sheet grid are dropped; returns how many (#1008).
67    pub fn rebuild(&mut self) -> usize {
68        let mut out = CellStore::new();
69        let mut dropped = 0;
70        for (_, band) in std::mem::take(&mut self.bands) {
71            for (row, cols) in band.rows.iter() {
72                for (col, cell) in cols.iter() {
73                    let at = CellRef::new(*row, *col);
74                    if at.is_valid() {
75                        out.set(at, cell.clone());
76                    } else {
77                        dropped += 1;
78                    }
79                }
80            }
81        }
82        *self = out;
83        dropped
84    }
85
86    pub fn remove(&mut self, c: CellRef) -> Option<Cell> {
87        let key = c.row / BAND;
88        let band = self.bands.get_mut(&key)?;
89        if !band.rows.get(&c.row).is_some_and(|r| r.contains_key(&c.col)) {
90            return None;
91        }
92        let b = Arc::make_mut(band);
93        let row = b.rows.get_mut(&c.row)?;
94        let old = row.remove(&c.col);
95        if row.is_empty() {
96            b.rows.remove(&c.row);
97        }
98        if b.rows.is_empty() {
99            self.bands.remove(&key);
100        }
101        if old.is_some() {
102            self.len -= 1;
103        }
104        old
105    }
106    /// Cells in `r`, row-major. Efficient for sparse data: skips empty bands and rows.
107    pub fn iter_range(&self, r: RangeRef) -> impl Iterator<Item = (CellRef, &Cell)> + '_ {
108        let (b0, b1) = (r.start.row / BAND, r.end.row / BAND);
109        self.bands.range(b0..=b1).flat_map(move |(_, band)| {
110            band.rows
111                .range(r.start.row..=r.end.row)
112                .flat_map(move |(row, cols)| cols.range(r.start.col..=r.end.col).map(move |(col, cell)| (CellRef::new(*row, *col), cell)))
113        })
114    }
115    pub fn iter(&self) -> impl Iterator<Item = (CellRef, &Cell)> + '_ {
116        self.bands
117            .values()
118            .flat_map(|band| band.rows.iter().flat_map(|(row, cols)| cols.iter().map(move |(col, cell)| (CellRef::new(*row, *col), cell))))
119    }
120    /// Cells of one row in `c0..=c1`.
121    pub fn row(&self, row: u32, c0: u32, c1: u32) -> impl Iterator<Item = (u32, &Cell)> + '_ {
122        self.bands.get(&(row / BAND)).and_then(|b| b.rows.get(&row)).into_iter().flat_map(move |cols| cols.range(c0..=c1).map(|(c, cell)| (*c, cell)))
123    }
124    /// Smallest range containing every stored cell, `None` when empty.
125    pub fn used_range(&self) -> Option<RangeRef> {
126        let first_band = self.bands.values().next()?;
127        let last_band = self.bands.values().next_back()?;
128        let r0 = *first_band.rows.keys().next()?;
129        let r1 = *last_band.rows.keys().next_back()?;
130        let mut c0 = u32::MAX;
131        let mut c1 = 0;
132        for band in self.bands.values() {
133            for cols in band.rows.values() {
134                if let (Some(a), Some(b)) = (cols.keys().next(), cols.keys().next_back()) {
135                    c0 = c0.min(*a);
136                    c1 = c1.max(*b);
137                }
138            }
139        }
140        if c0 == u32::MAX {
141            return None;
142        }
143        Some(RangeRef::new(CellRef::new(r0, c0), CellRef::new(r1, c1)))
144    }
145    /// Last stored row in column `col` at or above `below_or_at` (for Ctrl+arrow navigation).
146    pub fn has(&self, c: CellRef) -> bool {
147        self.get(c).is_some_and(has_value)
148    }
149    /// Last row (inclusive, capped at `cap`) of the maximal run of contiguous rows at or after
150    /// `from.row` that store a cell in `from.col` with a non-empty *value* in `from.col`. `None`
151    /// when `from` itself doesn't qualify.
152    ///
153    /// Deliberately narrower than `has`/`get` (which also count a formula with no cached value
154    /// yet, for Ctrl+arrow navigation): this matches `Sheet::value_ref`, whose callers test the
155    /// `Value` it returns with `!v.is_empty()` regardless of whether a formula produced it — a
156    /// formula cell with an empty cached value (`=""`, or not yet recalculated) is "empty" to
157    /// them. A stored cell with no value and no formula (for example a formatted spill child) does
158    /// fall through to `spill` in `value_ref`, so `last_contiguous_nonempty` asks `value_ref`
159    /// about the row where this run stops.
160    ///
161    /// Walks each band's row map with `BTreeMap::range` (one in-order pass per band) instead of
162    /// one `get` per row, so a long, densely-populated run costs roughly one tree-traversal step
163    /// per row rather than one binary search per row.
164    pub fn contiguous_value_run(&self, from: CellRef, cap: u32) -> Option<u32> {
165        let mut last = None;
166        let mut expect = from.row;
167        while expect <= cap {
168            let band_key = expect / BAND;
169            let Some(band) = self.bands.get(&band_key) else { break };
170            let band_hi = ((band_key + 1) * BAND - 1).min(cap);
171            let mut advanced = false;
172            for (r, cols) in band.rows.range(expect..=band_hi) {
173                if *r != expect || cols.get(&from.col).is_none_or(|c| c.value.is_empty()) {
174                    return last;
175                }
176                last = Some(expect);
177                expect += 1;
178                advanced = true;
179            }
180            if !advanced {
181                break;
182            }
183        }
184        last
185    }
186    /// Positions whose cells differ between `self` and `other` (stored on one side only, or not
187    /// equal). Bands both stores share are skipped, so comparing an edited copy with the store
188    /// it was cloned from only visits the bands the edit touched.
189    pub fn diff(&self, other: &CellStore) -> Vec<CellRef> {
190        let empty = Band::default();
191        let mut keys: Vec<u32> = self.bands.keys().chain(other.bands.keys()).copied().collect();
192        keys.sort_unstable();
193        keys.dedup();
194        let mut out = Vec::new();
195        for k in keys {
196            let (a, b) = (self.bands.get(&k), other.bands.get(&k));
197            if let (Some(a), Some(b)) = (a, b)
198                && Arc::ptr_eq(a, b)
199            {
200                continue;
201            }
202            let (a, b) = (a.map_or(&empty, |x| x), b.map_or(&empty, |x| x));
203            for (row, cols) in &a.rows {
204                for (col, cell) in cols {
205                    if b.rows.get(row).and_then(|r| r.get(col)) != Some(cell) {
206                        out.push(CellRef::new(*row, *col));
207                    }
208                }
209            }
210            for (row, cols) in &b.rows {
211                for col in cols.keys() {
212                    if !a.rows.get(row).is_some_and(|r| r.contains_key(col)) {
213                        out.push(CellRef::new(*row, *col));
214                    }
215                }
216            }
217        }
218        out
219    }
220    /// Approximate heap storage kept alive by this snapshot's bands that `newer` no longer
221    /// shares. This is for bounding Undo history, not for reporting process memory: BTreeMap
222    /// nodes and allocator overhead vary by platform. Shared formulas and values are counted
223    /// only when the newer band no longer holds the same Arc.
224    pub fn retained_bytes_against(&self, newer: &CellStore) -> usize {
225        use std::mem::size_of;
226
227        let mut bytes = 0usize;
228        for (key, band) in &self.bands {
229            let next = newer.bands.get(key);
230            if next.is_some_and(|b| Arc::ptr_eq(b, band)) {
231                continue;
232            }
233            bytes = bytes.saturating_add(size_of::<Band>());
234            for (row, cols) in &band.rows {
235                bytes = bytes.saturating_add(size_of::<u32>() + 3 * size_of::<usize>());
236                for (col, cell) in cols {
237                    // Cells and BTreeMap nodes are duplicated with a cloned band even when
238                    // their formula/value Arcs are still shared with the next snapshot.
239                    bytes = bytes.saturating_add(size_of::<u32>() + size_of::<Cell>() + 3 * size_of::<usize>());
240                    let next_cell = next.and_then(|b| b.rows.get(row)).and_then(|r| r.get(col));
241                    if let Some(formula) = &cell.formula
242                        && !next_cell.and_then(|c| c.formula.as_ref()).is_some_and(|f| Arc::ptr_eq(f, formula))
243                    {
244                        bytes = bytes.saturating_add(size_of::<crate::model::cell::Formula>() + formula.text.len());
245                        if let Some(expr) = &formula.expr {
246                            expr.walk(&mut |_| bytes = bytes.saturating_add(size_of::<crate::formula::Expr>()));
247                        }
248                    }
249                    match &cell.value {
250                        crate::base::Value::Text(text)
251                            if !next_cell.and_then(|c| c.value.as_text()).is_some_and(|t| std::ptr::eq(t, text.as_ref())) =>
252                        {
253                            bytes = bytes.saturating_add(text.len());
254                        }
255                        crate::base::Value::Array(array)
256                            if !next_cell.is_some_and(|c| matches!(&c.value, crate::base::Value::Array(a) if Arc::ptr_eq(a, array))) =>
257                        {
258                            bytes = bytes
259                                .saturating_add(size_of::<crate::base::Array>() + array.data.len().saturating_mul(size_of::<crate::base::Value>()));
260                        }
261                        _ => {}
262                    }
263                }
264            }
265        }
266        bytes
267    }
268    /// Removes every cell in `r` and returns them.
269    pub fn take_range(&mut self, r: RangeRef) -> Vec<(CellRef, Cell)> {
270        let keys: Vec<CellRef> = self.iter_range(r).map(|(c, _)| c).collect();
271        keys.into_iter().filter_map(|c| self.remove(c).map(|cell| (c, cell))).collect()
272    }
273    /// Rows strictly greater than or equal to `from` moved by `delta` (positive = down). Rows that
274    /// would land before `from`... callers delete the vacated block first.
275    pub fn shift_rows(&mut self, from: u32, delta: i64) {
276        let moved: Vec<(CellRef, Cell)> = {
277            let keys: Vec<CellRef> = self.iter().filter(|(c, _)| c.row >= from).map(|(c, _)| c).collect();
278            keys.into_iter().filter_map(|c| self.remove(c).map(|cell| (c, cell))).collect()
279        };
280        for (c, cell) in moved {
281            let nr = c.row as i64 + delta;
282            if (0..crate::base::MAX_ROWS as i64).contains(&nr) {
283                self.set(CellRef::new(nr as u32, c.col), cell);
284            }
285        }
286    }
287    pub fn shift_cols(&mut self, from: u32, delta: i64) {
288        let keys: Vec<CellRef> = self.iter().filter(|(c, _)| c.col >= from).map(|(c, _)| c).collect();
289        let moved: Vec<(CellRef, Cell)> = keys.into_iter().filter_map(|c| self.remove(c).map(|cell| (c, cell))).collect();
290        for (c, cell) in moved {
291            let nc = c.col as i64 + delta;
292            if (0..crate::base::MAX_COLS as i64).contains(&nc) {
293                self.set(CellRef::new(c.row, nc as u32), cell);
294            }
295        }
296    }
297    /// Shifts cells within rows `r0..=r1` and columns `>= from` horizontally (Insert/Delete Cells
298    /// with shift right/left).
299    pub fn shift_cols_in_rows(&mut self, r0: u32, r1: u32, from: u32, delta: i64) {
300        let range = RangeRef::new(CellRef::new(r0, from), CellRef::new(r1, crate::base::MAX_COLS - 1));
301        let moved = self.take_range(range);
302        for (c, cell) in moved {
303            let nc = c.col as i64 + delta;
304            if (0..crate::base::MAX_COLS as i64).contains(&nc) {
305                self.set(CellRef::new(c.row, nc as u32), cell);
306            }
307        }
308    }
309    /// Shifts cells within columns `c0..=c1` and rows `>= from` vertically.
310    pub fn shift_rows_in_cols(&mut self, c0: u32, c1: u32, from: u32, delta: i64) {
311        let range = RangeRef::new(CellRef::new(from, c0), CellRef::new(crate::base::MAX_ROWS - 1, c1));
312        let moved = self.take_range(range);
313        for (c, cell) in moved {
314            let nr = c.row as i64 + delta;
315            if (0..crate::base::MAX_ROWS as i64).contains(&nr) {
316                self.set(CellRef::new(nr as u32, c.col), cell);
317            }
318        }
319    }
320}
321
322#[cfg(test)]
323mod tests {
324    use super::*;
325    use crate::base::Value;
326
327    fn c(r: u32, col: u32) -> CellRef {
328        CellRef::new(r, col)
329    }
330
331    #[test]
332    fn set_get_remove() -> Result<(), Box<dyn std::error::Error>> {
333        let mut s = CellStore::new();
334        s.set(c(0, 0), Cell::value(1.0.into()));
335        s.set(c(100, 5), Cell::value("x".into()));
336        assert_eq!(s.len(), 2);
337        assert_eq!(s.get(c(100, 5)).map(|x| x.value.clone()), Some(Value::from("x")));
338        assert_eq!(s.used_range().ok_or("none")?.a1(), "A1:F101");
339        s.set(c(0, 0), Cell::default());
340        assert_eq!(s.len(), 1);
341        assert!(s.remove(c(100, 5)).is_some());
342        assert!(s.is_empty());
343        assert!(s.used_range().is_none());
344        Ok(())
345    }
346
347    #[test]
348    fn cow_snapshots() -> Result<(), Box<dyn std::error::Error>> {
349        let mut s = CellStore::new();
350        for r in 0..1000 {
351            s.set(c(r, 0), Cell::value((r as f64).into()));
352        }
353        let snap = s.clone();
354        s.set(c(5, 0), Cell::value(99.0.into()));
355        assert_eq!(snap.get(c(5, 0)).ok_or("none")?.value, Value::Number(5.0));
356        assert_eq!(s.get(c(5, 0)).ok_or("none")?.value, Value::Number(99.0));
357        Ok(())
358    }
359
360    #[test]
361    fn diff_visits_changed_bands() {
362        let mut s = CellStore::new();
363        for r in 0..1000 {
364            s.set(c(r, 0), Cell::value((r as f64).into()));
365        }
366        let snap = s.clone();
367        assert!(s.diff(&snap).is_empty());
368        s.set(c(5, 0), Cell::value(99.0.into()));
369        s.set(c(700, 3), Cell::value("new".into()));
370        s.remove(c(900, 0));
371        assert_eq!(snap.diff(&s), [c(5, 0), c(700, 3), c(900, 0)]);
372    }
373
374    #[test]
375    fn range_iteration_order() -> Result<(), Box<dyn std::error::Error>> {
376        let mut s = CellStore::new();
377        s.set(c(70, 2), Cell::value(3.0.into()));
378        s.set(c(1, 1), Cell::value(1.0.into()));
379        s.set(c(1, 3), Cell::value(2.0.into()));
380        s.set(c(500, 0), Cell::value(4.0.into()));
381        let v: Vec<f64> =
382            s.iter_range(RangeRef::parse("A1:D100").ok_or("none")?).map(|(_, x)| x.value.as_f64()).collect::<Option<_>>().ok_or("none")?;
383        assert_eq!(v, [1.0, 2.0, 3.0]);
384        Ok(())
385    }
386
387    #[test]
388    fn shifting() {
389        let mut s = CellStore::new();
390        s.set(c(2, 0), Cell::value(1.0.into()));
391        s.set(c(5, 0), Cell::value(2.0.into()));
392        s.shift_rows(3, 2);
393        assert!(s.get(c(7, 0)).is_some());
394        assert!(s.get(c(2, 0)).is_some());
395        s.shift_cols(0, 1);
396        assert!(s.get(c(7, 1)).is_some());
397    }
398}
ravenrs_sheet/model/store.rs

ravenrs_sheet/model/
store.rs
