formualizer_eval/engine/
addr.rs

1//! Vertex address space.
2//!
3//! The graph holds two disjoint kinds of vertex.
4//!
5//! * **Grid vertices** — cells, formulas, empty placeholders. Their address *is* their
6//!   identity: a `(SheetId, row, col)` position that users can see, reference, and shift
7//!   with structural edits.
8//! * **Symbol vertices** — defined names, tables, and external sources. They are identified
9//!   by name and have no position at all.
10//!
11//! Before this module existed, both kinds shared one address space: symbols were handed
12//! fabricated `(row, col)` coordinates on a real user-visible sheet, and the only thing that
13//! kept them from behaving like cells was their deliberate absence from `cell_to_vertex` —
14//! a convention any code path could break. Issues #302 and #304 are two paths that broke it.
15//!
16//! [`GridAddr`] and [`SymbolAddr`] make the distinction a type. [`VertexAddr`] is the tagged
17//! union actually stored in the vertex store and the edge coordinate arrays. Structures that
18//! are keyed by grid position take a `GridAddr`, which a symbol cannot produce, so inserting
19//! a symbol into a grid structure is a compile error rather than a runtime guard.
20//!
21//! # Representation
22//!
23//! [`VertexAddr`] is exactly 8 bytes — the same width as the [`AbsCoord`] it replaces. The
24//! coordinate encoding saturates rows (20 bits) and columns (14 bits) at Excel's limits but
25//! leaves the top 20 bits (`0xFFFFF000_00000000`) reserved and always zero for a real
26//! position, with `u64::MAX` already reserved as the invalid sentinel. Symbols live in that
27//! niche: bit 63 set with the rest of the reserved field clear. The edge coordinate arrays
28//! are `Vec` parallel to adjacency, so widening them to `Option<AbsCoord>` (16 bytes) would
29//! double hot memory; using the existing niche keeps the address free.
30
31use formualizer_common::Coord as AbsCoord;
32use std::fmt;
33
34/// The reserved high field of a packed coordinate. Zero for every real `(row, col)`.
35const RESERVED_HIGH_MASK: u64 = 0xFFFFF000_00000000;
36
37/// Tag written into the reserved high field to mark a symbol address.
38const SYMBOL_TAG: u64 = 1 << 63;
39
40/// Payload area available to a symbol address (44 bits; `u32` indices fit trivially).
41const SYMBOL_PAYLOAD_MASK: u64 = !RESERVED_HIGH_MASK;
42
43/// A real grid position.
44///
45/// Only vertices that live on a sheet's grid have one. Grid-keyed structures take this
46/// type so a symbol cannot be inserted into them.
47#[repr(transparent)]
48#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash)]
49pub struct GridAddr(AbsCoord);
50
51impl Default for GridAddr {
52    #[inline]
53    fn default() -> Self {
54        Self::new(0, 0)
55    }
56}
57
58impl Ord for GridAddr {
59    #[inline]
60    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
61        (self.row(), self.col()).cmp(&(other.row(), other.col()))
62    }
63}
64
65impl PartialOrd for GridAddr {
66    #[inline]
67    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
68        Some(self.cmp(other))
69    }
70}
71
72impl GridAddr {
73    /// Construct from zero-based row/column, panicking beyond Excel's limits.
74    #[inline]
75    pub fn new(row: u32, col: u32) -> Self {
76        Self(AbsCoord::new(row, col))
77    }
78
79    /// Wrap an already-packed coordinate.
80    #[inline]
81    pub const fn from_coord(coord: AbsCoord) -> Self {
82        Self(coord)
83    }
84
85    /// The packed coordinate.
86    #[inline]
87    pub const fn coord(self) -> AbsCoord {
88        self.0
89    }
90
91    #[inline]
92    pub fn row(self) -> u32 {
93        self.0.row()
94    }
95
96    #[inline]
97    pub fn col(self) -> u32 {
98        self.0.col()
99    }
100}
101
102impl From<AbsCoord> for GridAddr {
103    #[inline]
104    fn from(coord: AbsCoord) -> Self {
105        Self(coord)
106    }
107}
108
109impl From<GridAddr> for AbsCoord {
110    #[inline]
111    fn from(addr: GridAddr) -> Self {
112        addr.0
113    }
114}
115
116/// A dense symbol identity.
117///
118/// Symbols have no position. The index is an allocation counter and carries no meaning
119/// beyond distinguishing one symbol vertex from another; nothing may derive a row, a
120/// column, or a sheet from it.
121#[repr(transparent)]
122#[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
123pub struct SymbolAddr(u32);
124
125impl SymbolAddr {
126    #[inline]
127    pub const fn new(index: u32) -> Self {
128        Self(index)
129    }
130
131    #[inline]
132    pub const fn index(self) -> u32 {
133        self.0
134    }
135}
136
137/// The address of a vertex: a grid position or a symbol identity, in 8 bytes.
138#[repr(transparent)]
139#[derive(Copy, Clone, PartialEq, Eq, Hash)]
140pub struct VertexAddr(u64);
141
142impl VertexAddr {
143    /// The invalid sentinel. Neither a grid position nor a symbol.
144    pub const INVALID: Self = Self(u64::MAX);
145
146    /// Address of a vertex that occupies a grid position.
147    #[inline]
148    pub fn grid(addr: GridAddr) -> Self {
149        Self(addr.0.as_u64())
150    }
151
152    /// Address of a vertex identified by name rather than position.
153    #[inline]
154    pub const fn symbol(addr: SymbolAddr) -> Self {
155        Self(SYMBOL_TAG | (addr.0 as u64))
156    }
157
158    /// The grid position, or `None` for a symbol (or the invalid sentinel).
159    ///
160    /// This is the only route from a stored vertex address to a `(row, col)`, which is what
161    /// keeps symbols out of grid-keyed structures.
162    #[inline]
163    pub fn as_grid(self) -> Option<GridAddr> {
164        (self.0 & RESERVED_HIGH_MASK == 0).then(|| GridAddr(unsafe_coord_from_raw(self.0)))
165    }
166
167    /// The symbol identity, or `None` for a grid position.
168    #[inline]
169    pub fn as_symbol(self) -> Option<SymbolAddr> {
170        (self.0 & RESERVED_HIGH_MASK == SYMBOL_TAG)
171            .then_some(SymbolAddr((self.0 & SYMBOL_PAYLOAD_MASK) as u32))
172    }
173
174    #[inline]
175    pub fn is_symbol(self) -> bool {
176        self.0 & RESERVED_HIGH_MASK == SYMBOL_TAG
177    }
178
179    #[inline]
180    pub fn is_grid(self) -> bool {
181        self.0 & RESERVED_HIGH_MASK == 0
182    }
183
184    #[inline]
185    pub const fn as_u64(self) -> u64 {
186        self.0
187    }
188
189    /// Total order used to keep edge lists deterministic.
190    ///
191    /// Grid vertices order by `(row, col)` exactly as they did when the arrays held bare
192    /// coordinates. Symbols have no position, so they sort after every grid vertex, by
193    /// allocation index.
194    #[inline]
195    pub fn order_key(self) -> (u32, u32) {
196        match (self.as_grid(), self.as_symbol()) {
197            (Some(grid), _) => (grid.row(), grid.col()),
198            (_, Some(symbol)) => (u32::MAX, symbol.index()),
199            _ => (u32::MAX, u32::MAX),
200        }
201    }
202}
203
204/// Rebuild a `Coord` from raw bits already known to have a clear reserved field.
205#[inline]
206fn unsafe_coord_from_raw(raw: u64) -> AbsCoord {
207    debug_assert!(raw & RESERVED_HIGH_MASK == 0);
208    // `Coord::from_raw` rejects reserved low bits too; a stored grid address never has them,
209    // and falling back to the packed row/col keeps this total rather than panicking.
210    AbsCoord::from_raw(raw).unwrap_or_else(|_| AbsCoord::new(0, 0))
211}
212
213impl From<GridAddr> for VertexAddr {
214    #[inline]
215    fn from(addr: GridAddr) -> Self {
216        Self::grid(addr)
217    }
218}
219
220impl From<SymbolAddr> for VertexAddr {
221    #[inline]
222    fn from(addr: SymbolAddr) -> Self {
223        Self::symbol(addr)
224    }
225}
226
227impl From<AbsCoord> for VertexAddr {
228    #[inline]
229    fn from(coord: AbsCoord) -> Self {
230        Self::grid(GridAddr(coord))
231    }
232}
233
234impl Default for VertexAddr {
235    #[inline]
236    fn default() -> Self {
237        Self::grid(GridAddr::default())
238    }
239}
240
241impl fmt::Debug for VertexAddr {
242    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
243        if let Some(grid) = self.as_grid() {
244            write!(f, "Grid(r{}, c{})", grid.row(), grid.col())
245        } else if let Some(symbol) = self.as_symbol() {
246            write!(f, "Symbol({})", symbol.index())
247        } else {
248            write!(f, "VertexAddr::INVALID")
249        }
250    }
251}
252
253#[cfg(test)]
254mod tests {
255    use super::*;
256
257    #[test]
258    fn vertex_addr_is_eight_bytes() {
259        assert_eq!(std::mem::size_of::<VertexAddr>(), 8);
260        assert_eq!(std::mem::size_of::<VertexAddr>(), size_of::<AbsCoord>());
261        assert_eq!(std::mem::align_of::<VertexAddr>(), align_of::<AbsCoord>());
262        assert_eq!(size_of::<GridAddr>(), 8);
263    }
264
265    #[test]
266    fn grid_addresses_round_trip_and_are_never_symbols() {
267        for (row, col) in [(0, 0), (1, 1), (1_048_575, 16_383), (7, 0), (0, 16_383)] {
268            let addr = VertexAddr::grid(GridAddr::new(row, col));
269            assert!(addr.is_grid());
270            assert!(!addr.is_symbol());
271            assert_eq!(addr.as_symbol(), None);
272            let grid = addr.as_grid().expect("grid address must decode");
273            assert_eq!((grid.row(), grid.col()), (row, col));
274            assert_eq!(addr.order_key(), (row, col));
275        }
276    }
277
278    #[test]
279    fn symbol_addresses_round_trip_and_are_never_grid() {
280        for index in [0u32, 1, 16_384, u32::MAX] {
281            let addr = VertexAddr::symbol(SymbolAddr::new(index));
282            assert!(addr.is_symbol());
283            assert!(!addr.is_grid());
284            assert_eq!(addr.as_grid(), None);
285            assert_eq!(addr.as_symbol(), Some(SymbolAddr::new(index)));
286            assert_eq!(addr.order_key(), (u32::MAX, index));
287        }
288    }
289
290    #[test]
291    fn invalid_sentinel_is_neither_grid_nor_symbol() {
292        assert!(!VertexAddr::INVALID.is_grid());
293        assert!(!VertexAddr::INVALID.is_symbol());
294        assert_eq!(VertexAddr::INVALID.as_grid(), None);
295        assert_eq!(VertexAddr::INVALID.as_symbol(), None);
296    }
297
298    #[test]
299    fn symbols_order_after_every_grid_position() {
300        let last_cell = VertexAddr::grid(GridAddr::new(1_048_575, 16_383));
301        let first_symbol = VertexAddr::symbol(SymbolAddr::new(0));
302        assert!(last_cell.order_key() < first_symbol.order_key());
303    }
304}
formualizer_eval/engine/addr.rs

formualizer_eval/engine/
addr.rs
