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                // Integer-valued f64s have zero low bits. FxHasher preserves
43                // those bits, sending whole numeric columns to one bucket.
44                // Use the SplitMix64 finalizer to avalanche the bits without
45                // changing key equality or numeric normalization.
46                let mut mixed = *bits;
47                mixed = (mixed ^ (mixed >> 30)).wrapping_mul(0xbf58_476d_1ce4_e5b9);
48                mixed = (mixed ^ (mixed >> 27)).wrapping_mul(0x94d0_49bb_1331_11eb);
49                (mixed ^ (mixed >> 31)).hash(state);
50            }
51            Self::Text(text) => {
52                1u8.hash(state);
53                text.hash(state);
54            }
55            Self::Boolean(value) => {
56                2u8.hash(state);
57                value.hash(state);
58            }
59            Self::Empty => {
60                3u8.hash(state);
61            }
62        }
63    }
64}
65
66impl LookupHashKey {
67    fn from_needle(value: &LiteralValue, date_system: DateSystem) -> Option<Self> {
68        // Blank needles retain numeric-zero coercion; blank candidates do not.
69        if matches!(value, LiteralValue::Empty) {
70            Some(Self::Number(0.0f64.to_bits()))
71        } else {
72            Self::from_literal(value, date_system)
73        }
74    }
75
76    pub(crate) fn from_literal(value: &LiteralValue, date_system: DateSystem) -> Option<Self> {
77        match value {
78            LiteralValue::Number(n) => Some(Self::Number(normalize_f64_bits(*n))),
79            LiteralValue::Int(i) => Some(Self::Number(normalize_f64_bits(*i as f64))),
80            LiteralValue::Text(s) => Some(Self::Text(s.to_lowercase().into_boxed_str())),
81            LiteralValue::Boolean(b) => Some(Self::Boolean(*b)),
82            LiteralValue::Empty => None,
83            // Temporal values are numbers in Excel: key them by their serial so
84            // an exact lookup finds them whether the needle or the cell (or
85            // both) carry a temporal type rather than a plain numeric.
86            LiteralValue::Date(_) | LiteralValue::DateTime(_) | LiteralValue::Time(_) => value
87                .as_serial_number_for(date_system)
88                .map(|serial| Self::Number(normalize_f64_bits(serial))),
89            LiteralValue::Error(_)
90            | LiteralValue::Array(_)
91            | LiteralValue::Duration(_)
92            | LiteralValue::Pending => None,
93        }
94    }
95}
96
97fn normalize_f64_bits(n: f64) -> u64 {
98    if n.is_nan() {
99        return f64::NAN.to_bits();
100    }
101    let rounded = n.round();
102    if (n - rounded).abs() < 1e-12 {
103        // Exact comparisons identify signed zero; the index must do so too.
104        if rounded == 0.0 {
105            0.0f64.to_bits()
106        } else {
107            rounded.to_bits()
108        }
109    } else {
110        n.to_bits()
111    }
112}
113
114#[derive(Debug, Clone, Default)]
115pub struct DuplicateIndices {
116    pub(crate) first: usize,
117    pub(crate) last: usize,
118    pub(crate) all: SmallVec<[usize; 1]>,
119}
120
121pub struct LookupIndex {
122    pub(crate) len: usize,
123    date_system: DateSystem,
124    pub(crate) bytes: usize,
125    pub(crate) entries: FxHashMap<LookupHashKey, DuplicateIndices>,
126    pub(crate) cell_values: Box<[LiteralValue]>,
127}
128
129#[cfg(test)]
130thread_local! {
131    static BUILD_ATTEMPTS: std::cell::Cell<usize> = const { std::cell::Cell::new(0) };
132}
133
134#[cfg(test)]
135pub(crate) fn take_build_attempts() -> usize {
136    BUILD_ATTEMPTS.with(|c| c.replace(0))
137}
138
139impl LookupIndex {
140    pub(crate) fn build(
141        view: &RangeView<'_>,
142        axis: LookupAxis,
143        date_system: DateSystem,
144    ) -> Result<BuildOutcome, ExcelError> {
145        #[cfg(test)]
146        BUILD_ATTEMPTS.with(|c| c.set(c.get() + 1));
147        let (rows, cols) = view.dims();
148        let len = match axis {
149            LookupAxis::ColumnInView(col) => {
150                if col >= cols {
151                    return Ok(BuildOutcome::Degenerate);
152                }
153                rows
154            }
155            LookupAxis::RowInView(row) => {
156                if row >= rows {
157                    return Ok(BuildOutcome::Degenerate);
158                }
159                cols
160            }
161        };
162        if len == 0 {
163            return Ok(BuildOutcome::Degenerate);
164        }
165
166        let mut entries: FxHashMap<LookupHashKey, DuplicateIndices> =
167            FxHashMap::with_capacity_and_hasher(len, Default::default());
168        let mut cell_values = Vec::with_capacity(len);
169        let mut error_count = 0usize;
170
171        for idx in 0..len {
172            let value = match axis {
173                LookupAxis::ColumnInView(col) => view.get_cell(idx, col),
174                LookupAxis::RowInView(row) => view.get_cell(row, idx),
175            };
176            if matches!(value, LiteralValue::Error(_)) {
177                error_count += 1;
178            }
179            if let Some(key) = LookupHashKey::from_literal(&value, date_system) {
180                let dups = entries.entry(key).or_insert_with(|| DuplicateIndices {
181                    first: idx,
182                    last: idx,
183                    all: SmallVec::new(),
184                });
185                if dups.all.is_empty() {
186                    dups.first = idx;
187                }
188                dups.last = idx;
189                dups.all.push(idx);
190            }
191            cell_values.push(value);
192        }
193
194        if error_count > 0 {
195            return Ok(BuildOutcome::ErrorInLookupAxis);
196        }
197
198        // Sized for distinct keys up front; a column of repeated keys
199        // gives the unused buckets back.
200        if entries.len().saturating_mul(2) < entries.capacity() {
201            entries.shrink_to_fit();
202        }
203        let bytes = retained_bytes(&cell_values, &entries);
204        Ok(BuildOutcome::Built(Self {
205            len,
206            date_system,
207            bytes,
208            entries,
209            cell_values: cell_values.into_boxed_slice(),
210        }))
211    }
212
213    pub(crate) fn find_first_exact(&self, needle: &LiteralValue) -> Option<usize> {
214        let hash_key = LookupHashKey::from_needle(needle, self.date_system)?;
215        if let Some(dups) = self.entries.get(&hash_key) {
216            for &idx in &dups.all {
217                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
218                    return Some(idx);
219                }
220            }
221        }
222        None
223    }
224
225    pub(crate) fn find_last_exact(&self, needle: &LiteralValue) -> Option<usize> {
226        let hash_key = LookupHashKey::from_needle(needle, self.date_system)?;
227        if let Some(dups) = self.entries.get(&hash_key) {
228            for &idx in dups.all.iter().rev() {
229                if cmp_for_lookup(needle, &self.cell_values[idx], self.date_system) == Some(0) {
230                    return Some(idx);
231                }
232            }
233        }
234        None
235    }
236}
237
238fn retained_bytes(
239    values: &[LiteralValue],
240    entries: &FxHashMap<LookupHashKey, DuplicateIndices>,
241) -> usize {
242    // HashMap capacity excludes control bytes and vacant buckets. Round up to
243    // the backing power-of-two bucket count; allocator bookkeeping is estimated.
244    let buckets = if entries.capacity() == 0 {
245        0
246    } else {
247        entries.capacity().saturating_add(1).next_power_of_two()
248    };
249    let mut bytes = values
250        .len()
251        .saturating_mul(std::mem::size_of::<LiteralValue>())
252        .saturating_add(
253            buckets.saturating_mul(std::mem::size_of::<(LookupHashKey, DuplicateIndices)>() + 1),
254        )
255        .saturating_add(256);
256    for value in values {
257        bytes = bytes.saturating_add(literal_payload_bytes(value));
258    }
259    for (key, indices) in entries {
260        if let LookupHashKey::Text(text) = key {
261            bytes = bytes.saturating_add(text.len());
262        }
263        if indices.all.spilled() {
264            bytes = bytes.saturating_add(
265                indices
266                    .all
267                    .capacity()
268                    .saturating_mul(std::mem::size_of::<usize>()),
269            );
270        }
271    }
272    bytes
273}
274
275fn literal_payload_bytes(value: &LiteralValue) -> usize {
276    match value {
277        LiteralValue::Text(text) => text.capacity(),
278        LiteralValue::Array(rows) => rows.iter().fold(
279            rows.capacity()
280                .saturating_mul(std::mem::size_of::<Vec<LiteralValue>>()),
281            |bytes, row| {
282                row.iter().fold(
283                    bytes.saturating_add(
284                        row.capacity()
285                            .saturating_mul(std::mem::size_of::<LiteralValue>()),
286                    ),
287                    |bytes, value| bytes.saturating_add(literal_payload_bytes(value)),
288                )
289            },
290        ),
291        _ => 0,
292    }
293}
294
295pub(crate) fn estimate_bytes(len: usize, entries: usize) -> usize {
296    len.saturating_mul(std::mem::size_of::<LiteralValue>().saturating_add(8))
297        .saturating_add(entries.saturating_mul(96))
298        .saturating_add(256)
299}
300
301pub(crate) enum BuildOutcome {
302    Built(LookupIndex),
303    ErrorInLookupAxis,
304    Degenerate,
305}
306
307const LOOKUP_INDEX_BUILD_THRESHOLD: u32 = 3;
308const CAP_REJECTED: u32 = u32::MAX;
309const CALL_COUNT_PRUNE_LIMIT: usize = 4096;
310
311#[derive(Debug, Clone, Copy, Default, PartialEq, Eq)]
312pub struct LookupIndexCacheReport {
313    pub(crate) builds: usize,
314    pub(crate) hits: usize,
315    pub(crate) misses: usize,
316    pub(crate) skipped_volatile: usize,
317    pub(crate) skipped_error: usize,
318    pub(crate) skipped_tiny: usize,
319    pub(crate) skipped_cap: usize,
320    pub(crate) skipped_below_threshold: usize,
321    pub(crate) bytes_in_cache: usize,
322    pub(crate) entries_count: usize,
323}
324
325pub struct LookupIndexCache {
326    inner: RwLock<FxHashMap<LookupIndexKey, Arc<LookupIndex>>>,
327    call_counts: RwLock<FxHashMap<LookupIndexKey, u32>>,
328    volatile_keys: RwLock<FxHashMap<LookupIndexKey, ()>>,
329    build_threshold: u32,
330    bytes_in_use: AtomicUsize,
331    max_bytes: usize,
332    builds: AtomicUsize,
333    hits: AtomicUsize,
334    misses: AtomicUsize,
335    skipped_volatile: AtomicUsize,
336    skipped_error: AtomicUsize,
337    skipped_tiny: AtomicUsize,
338    skipped_cap: AtomicUsize,
339    skipped_below_threshold: AtomicUsize,
340    /// Program 3: builds in progress. Parallel members of a lookup family
341    /// miss the cache together; one builds the index and the others wait
342    /// for it instead of each building (and allocating) a copy.
343    in_flight: std::sync::Mutex<FxHashMap<LookupIndexKey, Arc<BuildFlight>>>,
344    /// Index builds started from `single_flight` (tests).
345    #[cfg(test)]
346    pub(crate) flights_built: AtomicUsize,
347}
348
349/// The outcome of one in-progress build, shared by the callers waiting on it.
350pub(crate) type BuildFlight = std::sync::OnceLock<Option<Arc<LookupIndex>>>;
351
352fn volatile_key(mut key: LookupIndexKey) -> LookupIndexKey {
353    key.snapshot_id = 0;
354    key
355}
356
357impl LookupIndexCache {
358    pub(crate) fn new(max_bytes: usize) -> Self {
359        Self {
360            inner: RwLock::new(FxHashMap::default()),
361            call_counts: RwLock::new(FxHashMap::default()),
362            volatile_keys: RwLock::new(FxHashMap::default()),
363            build_threshold: LOOKUP_INDEX_BUILD_THRESHOLD,
364            bytes_in_use: AtomicUsize::new(0),
365            max_bytes,
366            builds: AtomicUsize::new(0),
367            hits: AtomicUsize::new(0),
368            misses: AtomicUsize::new(0),
369            skipped_volatile: AtomicUsize::new(0),
370            skipped_error: AtomicUsize::new(0),
371            skipped_tiny: AtomicUsize::new(0),
372            skipped_cap: AtomicUsize::new(0),
373            skipped_below_threshold: AtomicUsize::new(0),
374            in_flight: std::sync::Mutex::new(FxHashMap::default()),
375            #[cfg(test)]
376            flights_built: AtomicUsize::new(0),
377        }
378    }
379
380    /// Run `build` once for `key` among concurrent callers: the first
381    /// caller builds, the others block until it has finished and share its
382    /// outcome.
383    pub(crate) fn single_flight(
384        &self,
385        key: LookupIndexKey,
386        build: impl FnOnce() -> Option<Arc<LookupIndex>>,
387    ) -> Option<Arc<LookupIndex>> {
388        let flight = {
389            let Ok(mut guard) = self.in_flight.lock() else {
390                return build();
391            };
392            Arc::clone(guard.entry(key).or_default())
393        };
394        let mut built = false;
395        let outcome = flight
396            .get_or_init(|| {
397                built = true;
398                build()
399            })
400            .clone();
401        // A waiter's shared outcome is a cache hit (as a duplicate build
402        // finding the entry in `insert_if_room` was).
403        if !built && outcome.is_some() {
404            self.hits.fetch_add(1, Ordering::Relaxed);
405        }
406        if let Ok(mut guard) = self.in_flight.lock()
407            && guard.get(&key).is_some_and(|f| Arc::ptr_eq(f, &flight))
408        {
409            guard.remove(&key);
410        }
411        outcome
412    }
413
414    // Called only at an exclusive Engine mutation boundary, after all evaluation
415    // workers have joined. No old-generation builder can race this reclamation.
416    pub(crate) fn clear(&mut self) {
417        self.inner
418            .get_mut()
419            .unwrap_or_else(|p| p.into_inner())
420            .clear();
421        self.call_counts
422            .get_mut()
423            .unwrap_or_else(|p| p.into_inner())
424            .clear();
425        self.volatile_keys
426            .get_mut()
427            .unwrap_or_else(|p| p.into_inner())
428            .clear();
429        self.bytes_in_use.store(0, Ordering::Relaxed);
430        self.in_flight
431            .get_mut()
432            .unwrap_or_else(|p| p.into_inner())
433            .clear();
434    }
435
436    pub(crate) fn get(&self, key: &LookupIndexKey) -> Option<Arc<LookupIndex>> {
437        let found = self
438            .inner
439            .read()
440            .ok()
441            .and_then(|guard| guard.get(key).cloned());
442        if found.is_some() {
443            self.hits.fetch_add(1, Ordering::Relaxed);
444        } else {
445            self.misses.fetch_add(1, Ordering::Relaxed);
446        }
447        found
448    }
449
450    /// A builder's re-check after its `get` missed: an entry published in
451    /// between is a hit (no second miss is counted).
452    pub(crate) fn recheck(&self, key: &LookupIndexKey) -> Option<Arc<LookupIndex>> {
453        let found = self
454            .inner
455            .read()
456            .ok()
457            .and_then(|guard| guard.get(key).cloned());
458        if found.is_some() {
459            self.hits.fetch_add(1, Ordering::Relaxed);
460        }
461        found
462    }
463
464    pub(crate) fn should_build(&self, key: LookupIndexKey) -> bool {
465        let Ok(mut guard) = self.call_counts.write() else {
466            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
467            return false;
468        };
469        if guard.len() > CALL_COUNT_PRUNE_LIMIT {
470            guard.retain(|existing_key, _| existing_key.snapshot_id == key.snapshot_id);
471        }
472        let count = guard.entry(key).or_insert(0);
473        if *count == CAP_REJECTED {
474            self.skipped_cap.fetch_add(1, Ordering::Relaxed);
475            return false;
476        }
477        *count = count.saturating_add(1).min(CAP_REJECTED - 1);
478        if *count <= self.build_threshold {
479            self.skipped_below_threshold.fetch_add(1, Ordering::Relaxed);
480            return false;
481        }
482        true
483    }
484
485    pub(crate) fn would_exceed_cap(&self, bytes: usize) -> bool {
486        self.bytes_in_use
487            .load(Ordering::Relaxed)
488            .saturating_add(bytes)
489            > self.max_bytes
490    }
491
492    pub(crate) fn is_known_volatile(&self, key: &LookupIndexKey) -> bool {
493        let volatile_key = volatile_key(*key);
494        self.volatile_keys
495            .read()
496            .map(|guard| guard.contains_key(&volatile_key))
497            .unwrap_or(false)
498    }
499
500    pub(crate) fn note_volatile_key(&self, key: LookupIndexKey) {
501        if let Ok(mut guard) = self.volatile_keys.write() {
502            if guard.len() > CALL_COUNT_PRUNE_LIMIT {
503                guard.clear();
504            }
505            guard.insert(volatile_key(key), ());
506        }
507    }
508
509    pub(crate) fn insert_if_room(
510        &self,
511        key: LookupIndexKey,
512        index: LookupIndex,
513    ) -> Option<Arc<LookupIndex>> {
514        let bytes = index.bytes;
515        if let Ok(mut guard) = self.inner.write() {
516            if let Some(existing) = guard.get(&key) {
517                self.hits.fetch_add(1, Ordering::Relaxed);
518                return Some(existing.clone());
519            }
520            // Serialize duplicate detection, admission and accounting. The earlier
521            // preflight estimate is only a hint and cannot reserve concurrent space.
522            let current = self.bytes_in_use.load(Ordering::Relaxed);
523            if bytes > self.max_bytes.saturating_sub(current) {
524                self.skipped_cap.fetch_add(1, Ordering::Relaxed);
525                // Actual payloads (especially text) can exceed the preflight
526                // estimate. Do not rebuild and discard them on every later call.
527                if let Ok(mut counts) = self.call_counts.write() {
528                    counts.insert(key, CAP_REJECTED);
529                }
530                return None;
531            }
532            let index = Arc::new(index);
533            guard.insert(key, index.clone());
534            self.bytes_in_use.fetch_add(bytes, Ordering::Relaxed);
535            self.builds.fetch_add(1, Ordering::Relaxed);
536            Some(index)
537        } else {
538            None
539        }
540    }
541
542    pub(crate) fn note_skipped_volatile(&self) {
543        self.skipped_volatile.fetch_add(1, Ordering::Relaxed);
544    }
545
546    pub(crate) fn note_skipped_error(&self) {
547        self.skipped_error.fetch_add(1, Ordering::Relaxed);
548    }
549
550    pub(crate) fn note_skipped_tiny(&self) {
551        self.skipped_tiny.fetch_add(1, Ordering::Relaxed);
552    }
553
554    pub(crate) fn note_skipped_cap(&self) {
555        self.skipped_cap.fetch_add(1, Ordering::Relaxed);
556    }
557
558    pub(crate) fn reset_counters(&self) {
559        self.builds.store(0, Ordering::Relaxed);
560        self.hits.store(0, Ordering::Relaxed);
561        self.misses.store(0, Ordering::Relaxed);
562        self.skipped_volatile.store(0, Ordering::Relaxed);
563        self.skipped_error.store(0, Ordering::Relaxed);
564        self.skipped_tiny.store(0, Ordering::Relaxed);
565        self.skipped_cap.store(0, Ordering::Relaxed);
566        self.skipped_below_threshold.store(0, Ordering::Relaxed);
567    }
568
569    pub(crate) fn report(&self) -> LookupIndexCacheReport {
570        let guard = self.inner.read().ok();
571        let entries_count = guard.as_ref().map_or(0, |guard| guard.len());
572        LookupIndexCacheReport {
573            builds: self.builds.load(Ordering::Relaxed),
574            hits: self.hits.load(Ordering::Relaxed),
575            misses: self.misses.load(Ordering::Relaxed),
576            skipped_volatile: self.skipped_volatile.load(Ordering::Relaxed),
577            skipped_error: self.skipped_error.load(Ordering::Relaxed),
578            skipped_tiny: self.skipped_tiny.load(Ordering::Relaxed),
579            skipped_cap: self.skipped_cap.load(Ordering::Relaxed),
580            skipped_below_threshold: self.skipped_below_threshold.load(Ordering::Relaxed),
581            bytes_in_cache: self.bytes_in_use.load(Ordering::Relaxed),
582            entries_count,
583        }
584    }
585}
586
587#[cfg(test)]
588mod tests {
589    use super::*;
590    use chrono::NaiveTime;
591
592    fn key(col: u32) -> LookupIndexKey {
593        LookupIndexKey {
594            sheet_id: 0,
595            start_row: 0,
596            start_col: col,
597            end_row: 128,
598            end_col: col,
599            axis: LookupAxis::ColumnInView(0),
600            snapshot_id: 1,
601        }
602    }
603    fn index(bytes: usize) -> LookupIndex {
604        LookupIndex {
605            len: 0,
606            date_system: DateSystem::Excel1900,
607            bytes,
608            entries: FxHashMap::default(),
609            cell_values: Box::new([]),
610        }
611    }
612
613    #[test]
614    fn numeric_keys_distribute_across_initial_buckets() {
615        let buckets: std::collections::HashSet<_> = (1..=4096)
616            .map(|i| {
617                let mut hasher = rustc_hash::FxHasher::default();
618                LookupHashKey::Number((i as f64).to_bits()).hash(&mut hasher);
619                hasher.finish() & 8191
620            })
621            .collect();
622        assert!(
623            buckets.len() > 2048,
624            "only {} initial buckets",
625            buckets.len()
626        );
627    }
628
629    #[test]
630    fn exact_index_selects_signed_zero_and_temporal_zero_duplicates() {
631        assert_eq!(
632            LookupHashKey::from_literal(&LiteralValue::Empty, DateSystem::Excel1900),
633            None
634        );
635        assert_eq!(
636            LookupHashKey::from_needle(&LiteralValue::Empty, DateSystem::Excel1900),
637            Some(LookupHashKey::Number(0.0f64.to_bits()))
638        );
639        let midnight = LiteralValue::Time(NaiveTime::from_hms_opt(0, 0, 0).unwrap());
640        let values = vec![
641            LiteralValue::Empty,
642            LiteralValue::Boolean(false),
643            LiteralValue::Text("0".into()),
644            LiteralValue::Number(-0.0),
645            midnight.clone(),
646            LiteralValue::Number(0.0),
647            LiteralValue::Boolean(false),
648            LiteralValue::Text("0".into()),
649        ];
650        let view = RangeView::from_owned_rows(
651            values.into_iter().map(|value| vec![value]).collect(),
652            DateSystem::Excel1900,
653        );
654        let BuildOutcome::Built(index) =
655            LookupIndex::build(&view, LookupAxis::ColumnInView(0), DateSystem::Excel1900).unwrap()
656        else {
657            panic!("expected a lookup index");
658        };
659
660        assert_eq!(index.find_first_exact(&LiteralValue::Number(0.0)), Some(3));
661        assert_eq!(index.find_last_exact(&LiteralValue::Number(-0.0)), Some(5));
662        assert_eq!(index.find_first_exact(&midnight), Some(3));
663        assert_eq!(index.find_last_exact(&midnight), Some(5));
664        assert_eq!(index.find_first_exact(&LiteralValue::Empty), Some(3));
665        assert_eq!(index.find_last_exact(&LiteralValue::Empty), Some(5));
666
667        let temporal_only_view = RangeView::from_owned_rows(
668            vec![
669                vec![LiteralValue::Empty],
670                vec![LiteralValue::Boolean(false)],
671                vec![LiteralValue::Text("0".into())],
672                vec![midnight],
673            ],
674            DateSystem::Excel1900,
675        );
676        let BuildOutcome::Built(temporal_only) = LookupIndex::build(
677            &temporal_only_view,
678            LookupAxis::ColumnInView(0),
679            DateSystem::Excel1900,
680        )
681        .unwrap() else {
682            panic!("expected a temporal lookup index");
683        };
684        assert_eq!(
685            temporal_only.find_first_exact(&LiteralValue::Number(0.0)),
686            Some(3)
687        );
688    }
689
690    #[test]
691    fn concurrent_admission_and_duplicate_races_obey_cap() {
692        for duplicate in [false, true] {
693            let mut cache = LookupIndexCache::new(if duplicate { 1024 } else { 4096 });
694            let barrier = std::sync::Barrier::new(16);
695            std::thread::scope(|scope| {
696                let handles: Vec<_> = (0..16)
697                    .map(|i| {
698                        let cache = &cache;
699                        let barrier = &barrier;
700                        scope.spawn(move || {
701                            barrier.wait();
702                            cache.insert_if_room(key(if duplicate { 0 } else { i }), index(1024))
703                        })
704                    })
705                    .collect();
706                let admitted: Vec<_> = handles
707                    .into_iter()
708                    .filter_map(|h| h.join().unwrap())
709                    .collect();
710                assert_eq!(admitted.len(), if duplicate { 16 } else { 4 });
711                if duplicate {
712                    assert!(admitted.iter().all(|item| Arc::ptr_eq(item, &admitted[0])));
713                }
714            });
715            let report = cache.report();
716            assert_eq!(report.bytes_in_cache, cache.max_bytes);
717            assert_eq!(report.builds, if duplicate { 1 } else { 4 });
718            assert_eq!(report.entries_count, report.builds);
719            assert_eq!(report.skipped_cap, if duplicate { 0 } else { 12 });
720            cache.clear();
721            assert_eq!(cache.report().bytes_in_cache, 0);
722            assert_eq!(cache.report().entries_count, 0);
723            assert!(cache.insert_if_room(key(0), index(1024)).is_some());
724        }
725    }
726
727    #[test]
728    fn retained_text_and_duplicate_heap_payloads_are_charged() {
729        let mut entries = FxHashMap::default();
730        let mut text = String::with_capacity(4096);
731        text.push_str("LONG KEY");
732        let values = [LiteralValue::Text(text)];
733        let empty_bytes = retained_bytes(&[], &entries);
734        assert_eq!(
735            retained_bytes(&values, &entries) - empty_bytes,
736            std::mem::size_of::<LiteralValue>() + 4096
737        );
738        let mut dups = DuplicateIndices::default();
739        dups.all.extend(0..100);
740        let heap_bytes = dups.all.capacity() * std::mem::size_of::<usize>();
741        entries.insert(LookupHashKey::Text("long key".into()), dups);
742        let charged = retained_bytes(&values, &entries);
743        assert!(charged >= empty_bytes + 4096 + 8 + heap_bytes);
744        entries
745            .get_mut(&LookupHashKey::Text("long key".into()))
746            .unwrap()
747            .all = SmallVec::new();
748        assert_eq!(charged - retained_bytes(&values, &entries), heap_bytes);
749        let cache = LookupIndexCache::new(charged - 1);
750        assert!(cache.insert_if_room(key(0), index(charged)).is_none());
751    }
752}
formualizer_eval/engine/lookup_index_cache.rs

formualizer_eval/engine/
lookup_index_cache.rs
