formualizer_eval/engine/
lookup_index_cache.rs

1use std::hash::{Hash, Hasher};
2use std::sync::atomic::{AtomicUsize, Ordering};
3use std::sync::{Arc, RwLock};
4
5use formualizer_common::{ExcelError, LiteralValue, SheetId};
6use rustc_hash::FxHashMap;
7use smallvec::SmallVec;
8
9use crate::builtins::lookup::lookup_utils::cmp_for_lookup;
10use crate::engine::{DateSystem, range_view::RangeView};
11
12#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
13pub struct LookupIndexKey {
14    pub(crate) sheet_id: SheetId,
15    pub(crate) start_row: u32,
16    pub(crate) start_col: u32,
17    pub(crate) end_row: u32,
18    pub(crate) end_col: u32,
19    pub(crate) axis: LookupAxis,
20    pub(crate) snapshot_id: u64,
21}
22
23#[derive(Clone, Copy, Debug, Eq, PartialEq, Hash)]
24pub enum LookupAxis {
25    ColumnInView(usize),
26    RowInView(usize),
27}
28
29#[derive(Debug, Eq, PartialEq)]
30pub enum LookupHashKey {
31    Number(u64),
32    Text(Box<str>),
33    Boolean(bool),
34    Empty,
35}
36
37impl Hash for LookupHashKey {
38    fn hash<H: Hasher>(&self, state: &mut H) {
39        match self {
40            Self::Number(bits) => {
41                0u8.hash(state);
42                bits.hash(state);
43            }
44            Self::Text(text) => {
45                1u8.hash(state);
46                text.hash(state);
47            }
48            Self::Boolean(value) => {
49                2u8.hash(state);
50                value.hash(state);
51            }
52            Self::Empty => {
53                3u8.hash(state);
54            }
55        }
56    }
57}
58
59impl LookupHashKey {
60    pub(crate) fn from_literal(value: &LiteralValue, date_system: DateSystem) -> Option<Self> {
61        match value {
62            LiteralValue::Number(n) => Some(Self::Number(normalize_f64_bits(*n))),
63            LiteralValue::Int(i) => Some(Self::Number(normalize_f64_bits(*i as f64))),
64            LiteralValue::Text(s) => Some(Self::Text(s.to_lowercase().into_boxed_str())),
65            LiteralValue::Boolean(b) => Some(Self::Boolean(*b)),
66            LiteralValue::Empty => Some(Self::Empty),
67            // Temporal values are numbers in Excel: key them by their serial so
68            // an exact lookup finds them whether the needle or the cell (or
69            // both) carry a temporal type rather than a plain numeric.
70            LiteralValue::Date(_) | LiteralValue::DateTime(_) | LiteralValue::Time(_) => value
71                .as_serial_number_for(date_system)
72                .map(|serial| Self::Number(normalize_f64_bits(serial))),
73            LiteralValue::Error(_)
74            | LiteralValue::Array(_)
75            | LiteralValue::Duration(_)
76            | LiteralValue::Pending => None,
77        }
78    }
79}
80
81fn normalize_f64_bits(n: f64) -> u64 {
82    if n.is_nan() {
83        return f64::NAN.to_bits();
84    }
85    let rounded = n.round();
86    if (n - rounded).abs() < 1e-12 {
87        rounded.to_bits()
88    } else {
89        n.to_bits()
90    }
91}
92
93#[derive(Debug, Clone, Default)]
94pub struct DuplicateIndices {
95    pub(crate) first: usize,
96    pub(crate) last: usize,
97    pub(crate) all: SmallVec<[usize; 1]>,
98}
99
100pub struct LookupIndex {
101    pub(crate) len: usize,
102    date_system: DateSystem,
103    pub(crate) bytes: usize,
104    pub(crate) entries: FxHashMap<LookupHashKey, DuplicateIndices>,
105    pub(crate) cell_values: Box<[LiteralValue]>,
106    pub(crate) first_empty: Option<usize>,
107}
108
109impl LookupIndex {
110    pub(crate) fn build(
111        view: &RangeView<'_>,
112        axis: LookupAxis,
113        date_system: DateSystem,
114    ) -> Result<BuildOutcome, ExcelError> {
115        let (rows, cols) = view.dims();
116        let len = match axis {
117            LookupAxis::ColumnInView(col) => {
118                if col >= cols {
119                    return Ok(BuildOutcome::Degenerate);
120                }
121                rows
122            }
123            LookupAxis::RowInView(row) => {
124                if row >= rows {
125                    return Ok(BuildOutcome::Degenerate);
126                }
127                cols
128            }
129        };
130        if len == 0 {
131            return Ok(BuildOutcome::Degenerate);
132        }
133
134        let mut entries: FxHashMap<LookupHashKey, DuplicateIndices> = FxHashMap::default();
135        let mut cell_values = Vec::with_capacity(len);
136        let mut first_empty = None;
137        let mut error_count = 0usize;
138
139        for idx in 0..len {
140            let value = match axis {
141                LookupAxis::ColumnInView(col) => view.get_cell(idx, col),
142                LookupAxis::RowInView(row) => view.get_cell(row, idx),
143            };
144            if matches!(value, LiteralValue::Error(_)) {
145                error_count += 1;
146            }
147            if matches!(value, LiteralValue::Empty) && first_empty.is_none() {
148                first_empty = Some(idx);
149            }
150            if let Some(key) = LookupHashKey::from_literal(&value, date_system) {
151                let dups = entries.entry(key).or_insert_with(|| DuplicateIndices {
152                    first: idx,
153                    last: idx,
154                    all: SmallVec::new(),
155                });
156                if dups.all.is_empty() {
157                    dups.first = idx;
158                }
159                dups.last = idx;
160                dups.all.push(idx);
161            }
162            cell_values.push(value);
163        }
164
165        if error_count > 0 {
166            return Ok(BuildOutcome::ErrorInLookupAxis);
167        }
168
169        let bytes = estimate_bytes(len, entries.len());
170        Ok(BuildOutcome::Built(Self {
171            len,
172            date_system,
173            bytes,
174            entries,
175            cell_values: cell_values.into_boxed_slice(),
176            first_empty,
177        }))
178    }
179
180    pub(crate) fn find_first_exact(&self, needle: &LiteralValue) -> Option<usize> {
181        let hash_key = LookupHashKey::from_literal(needle, self.date_system)?;
182        if let Some(dups) = self.entries.get(&hash_key) {
183            for &idx in &dups.all {
184                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
185                    return Some(idx);
186                }
187            }
188        }
189        if let Some(n) = numeric_zero_candidate(needle)
190            && n.abs() < 1e-12
191        {
192            return self.first_empty;
193        }
194        None
195    }
196
197    pub(crate) fn find_last_exact(&self, needle: &LiteralValue) -> Option<usize> {
198        let hash_key = LookupHashKey::from_literal(needle, self.date_system)?;
199        if let Some(dups) = self.entries.get(&hash_key) {
200            for &idx in dups.all.iter().rev() {
201                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
202                    return Some(idx);
203                }
204            }
205        }
206        if let Some(n) = numeric_zero_candidate(needle)
207            && n.abs() < 1e-12
208        {
209            return self.first_empty;
210        }
211        None
212    }
213}
214
215fn numeric_zero_candidate(needle: &LiteralValue) -> Option<f64> {
216    match needle {
217        LiteralValue::Number(n) => Some(*n),
218        LiteralValue::Int(i) => Some(*i as f64),
219        _ => None,
220    }
221}
222
223pub(crate) fn estimate_bytes(len: usize, entries: usize) -> usize {
224    len.saturating_mul(std::mem::size_of::<LiteralValue>().saturating_add(8))
225        .saturating_add(entries.saturating_mul(96))
226        .saturating_add(256)
227}
228
229pub(crate) enum BuildOutcome {
230    Built(LookupIndex),
231    ErrorInLookupAxis,
232    Degenerate,
233}
234
235const LOOKUP_INDEX_BUILD_THRESHOLD: u32 = 3;
236const CALL_COUNT_PRUNE_LIMIT: usize = 4096;
237
238#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
239pub struct LookupIndexCacheReport {
240    pub(crate) builds: usize,
241    pub(crate) hits: usize,
242    pub(crate) misses: usize,
243    pub(crate) skipped_volatile: usize,
244    pub(crate) skipped_error: usize,
245    pub(crate) skipped_tiny: usize,
246    pub(crate) skipped_cap: usize,
247    pub(crate) skipped_below_threshold: usize,
248    pub(crate) bytes_in_cache: usize,
249    pub(crate) entries_count: usize,
250}
251
252pub struct LookupIndexCache {
253    inner: RwLock<FxHashMap<LookupIndexKey, Arc<LookupIndex>>>,
254    call_counts: RwLock<FxHashMap<LookupIndexKey, u32>>,
255    volatile_keys: RwLock<FxHashMap<LookupIndexKey, ()>>,
256    build_threshold: u32,
257    bytes_in_use: AtomicUsize,
258    max_bytes: usize,
259    builds: AtomicUsize,
260    hits: AtomicUsize,
261    misses: AtomicUsize,
262    skipped_volatile: AtomicUsize,
263    skipped_error: AtomicUsize,
264    skipped_tiny: AtomicUsize,
265    skipped_cap: AtomicUsize,
266    skipped_below_threshold: AtomicUsize,
267}
268
269fn volatile_key(mut key: LookupIndexKey) -> LookupIndexKey {
270    key.snapshot_id = 0;
271    key
272}
273
274impl LookupIndexCache {
275    pub(crate) fn new(max_bytes: usize) -> Self {
276        Self {
277            inner: RwLock::new(FxHashMap::default()),
278            call_counts: RwLock::new(FxHashMap::default()),
279            volatile_keys: RwLock::new(FxHashMap::default()),
280            build_threshold: LOOKUP_INDEX_BUILD_THRESHOLD,
281            bytes_in_use: AtomicUsize::new(0),
282            max_bytes,
283            builds: AtomicUsize::new(0),
284            hits: AtomicUsize::new(0),
285            misses: AtomicUsize::new(0),
286            skipped_volatile: AtomicUsize::new(0),
287            skipped_error: AtomicUsize::new(0),
288            skipped_tiny: AtomicUsize::new(0),
289            skipped_cap: AtomicUsize::new(0),
290            skipped_below_threshold: AtomicUsize::new(0),
291        }
292    }
293
294    pub(crate) fn get(&self, key: &LookupIndexKey) -> Option<Arc<LookupIndex>> {
295        let found = self
296            .inner
297            .read()
298            .ok()
299            .and_then(|guard| guard.get(key).cloned());
300        if found.is_some() {
301            self.hits.fetch_add(1, Ordering::Relaxed);
302        } else {
303            self.misses.fetch_add(1, Ordering::Relaxed);
304        }
305        found
306    }
307
308    pub(crate) fn should_build(&self, key: LookupIndexKey) -> bool {
309        let Ok(mut guard) = self.call_counts.write() else {
310            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
311            return false;
312        };
313        if guard.len() > CALL_COUNT_PRUNE_LIMIT {
314            guard.retain(|existing_key, _| existing_key.snapshot_id == key.snapshot_id);
315        }
316        let count = guard.entry(key).or_insert(0);
317        *count = count.saturating_add(1);
318        if *count <= self.build_threshold {
319            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
320            return false;
321        }
322        true
323    }
324
325    pub(crate) fn would_exceed_cap(&self, bytes: usize) -> bool {
326        self.bytes_in_use
327            .load(Ordering::Relaxed)
328            .saturating_add(bytes)
329            > self.max_bytes
330    }
331
332    pub(crate) fn is_known_volatile(&self, key: &LookupIndexKey) -> bool {
333        let volatile_key = volatile_key(*key);
334        self.volatile_keys
335            .read()
336            .map(|guard| guard.contains_key(&volatile_key))
337            .unwrap_or(false)
338    }
339
340    pub(crate) fn note_volatile_key(&self, key: LookupIndexKey) {
341        if let Ok(mut guard) = self.volatile_keys.write() {
342            if guard.len() > CALL_COUNT_PRUNE_LIMIT {
343                guard.clear();
344            }
345            guard.insert(volatile_key(key), ());
346        }
347    }
348
349    pub(crate) fn insert_if_room(
350        &self,
351        key: LookupIndexKey,
352        index: LookupIndex,
353    ) -> Option<Arc<LookupIndex>> {
354        let bytes = index.bytes;
355        let current = self.bytes_in_use.load(Ordering::Relaxed);
356        if current.saturating_add(bytes) > self.max_bytes {
357            self.skipped_cap.fetch_add(1, Ordering::Relaxed);
358            return None;
359        }
360        let index = Arc::new(index);
361        if let Ok(mut guard) = self.inner.write() {
362            if let Some(existing) = guard.get(&key) {
363                self.hits.fetch_add(1, Ordering::Relaxed);
364                return Some(existing.clone());
365            }
366            guard.insert(key, index.clone());
367            self.bytes_in_use.fetch_add(bytes, Ordering::Relaxed);
368            self.builds.fetch_add(1, Ordering::Relaxed);
369            Some(index)
370        } else {
371            None
372        }
373    }
374
375    pub(crate) fn note_skipped_volatile(&self) {
376        self.skipped_volatile.fetch_add(1, Ordering::Relaxed);
377    }
378
379    pub(crate) fn note_skipped_error(&self) {
380        self.skipped_error.fetch_add(1, Ordering::Relaxed);
381    }
382
383    pub(crate) fn note_skipped_tiny(&self) {
384        self.skipped_tiny.fetch_add(1, Ordering::Relaxed);
385    }
386
387    pub(crate) fn note_skipped_cap(&self) {
388        self.skipped_cap.fetch_add(1, Ordering::Relaxed);
389    }
390
391    pub(crate) fn reset_counters(&self) {
392        self.builds.store(0, Ordering::Relaxed);
393        self.hits.store(0, Ordering::Relaxed);
394        self.misses.store(0, Ordering::Relaxed);
395        self.skipped_volatile.store(0, Ordering::Relaxed);
396        self.skipped_error.store(0, Ordering::Relaxed);
397        self.skipped_tiny.store(0, Ordering::Relaxed);
398        self.skipped_cap.store(0, Ordering::Relaxed);
399        self.skipped_below_threshold.store(0, Ordering::Relaxed);
400    }
401
402    pub(crate) fn report(&self) -> LookupIndexCacheReport {
403        let entries_count = self
404            .inner
405            .read()
406            .map(|guard| guard.len())
407            .unwrap_or_default();
408        LookupIndexCacheReport {
409            builds: self.builds.load(Ordering::Relaxed),
410            hits: self.hits.load(Ordering::Relaxed),
411            misses: self.misses.load(Ordering::Relaxed),
412            skipped_volatile: self.skipped_volatile.load(Ordering::Relaxed),
413            skipped_error: self.skipped_error.load(Ordering::Relaxed),
414            skipped_tiny: self.skipped_tiny.load(Ordering::Relaxed),
415            skipped_cap: self.skipped_cap.load(Ordering::Relaxed),
416            skipped_below_threshold: self.skipped_below_threshold.load(Ordering::Relaxed),
417            bytes_in_cache: self.bytes_in_use.load(Ordering::Relaxed),
418            entries_count,
419        }
420    }
421}
formualizer_eval/engine/lookup_index_cache.rs

formualizer_eval/engine/
lookup_index_cache.rs
