Skip to main content

dive_core/
store.rs

1//! The persistent, hash-consed, sharded store.
2//!
3//! - 256 shards, selected by the top eight bits of the interning hash. For
4//!   retained construction views this includes their exact representation;
5//!   canonical nodes use their value hash unchanged.
6//! - Node storage is append-only. Each shard has one column per size class;
7//!   a column is a chunked vector of `OnceLock` slots that hold a node's
8//!   header and its handles inline (the largest class boxes its handles). A
9//!   slot is written once, under the shard's lock, and read without a lock,
10//!   so reading a node is one chunk load and one slot load.
11//! - The deduplication index is an open-addressing table of atomic `u64`
12//!   entries. An intern that finds its node (a hit, by far the common case)
13//!   probes it without a lock, through the interning heap's
14//!   [`InternCache`] of the shard's current table; a miss takes the shard's
15//!   `Mutex`, probes again, and inserts. Growing replaces the table and
16//!   bumps the shard's generation, so a cached table is refreshed (under
17//!   the lock) when the generation moves; an old table stays valid for the
18//!   readers that still hold it, because nodes never move.
19//!   Each shard's lock and generation live on their own cache lines, apart
20//!   from the columns that readers touch.
21//!
22//! All of this is safe Rust. A handle the store did not issue is an internal
23//! error: reads return an empty poison view and set [`Store::poisoned`], which
24//! the engine reports as a bug, never as a verdict.
25
26use std::sync::atomic::{AtomicBool, AtomicU64, Ordering};
27use std::sync::{Arc, Mutex, OnceLock, PoisonError, Weak};
28
29use crate::handle::{CLASSES, Handle, LAZY_CLASS, MAX_CLASS_INDEX, mix2};
30use crate::node::{Kind, View, flags};
31use crate::strings::{StringOrder, Strings};
32
33pub mod compact;
34mod memory;
35pub mod snapshot;
36pub use memory::StoreMemory;
37
38const SHARDS: usize = 256;
39/// Chunks per column: chunk `k` holds `2^(base + k)` slots, which covers
40/// [`MAX_CLASS_INDEX`] for any base.
41const CHUNKS: usize = 31;
42/// The inline capacities of classes `0..CLASSES - 1`; the last class boxes.
43const CAPS: [usize; 2] = [4, 8];
44
45static EMPTY_DATA: [Handle; 0] = [];
46
47const POISON_VIEW: View<'static> = View {
48    kind: Kind::Set,
49    lo: 0,
50    hash: 0,
51    sum: 0,
52    flags: 0,
53    data: &EMPTY_DATA,
54};
55
56/// The size class of a node with `len` handles. Lazy nodes (constants
57/// only) have a class of their own, so that a handle tells it.
58fn class_of(len: usize, fl: u8) -> u8 {
59    if fl & (crate::node::flags::LAZY | crate::node::flags::VIEW) != 0 {
60        return LAZY_CLASS;
61    }
62    match len {
63        0..=4 => 0,
64        5..=8 => 1,
65        _ => 2,
66    }
67}
68
69/// A view parent has an extensional value hash, but exact interning must
70/// distinguish its retained child handles. Using only the value hash puts all
71/// equal independent representations in one probe cluster, making ordinary
72/// state handoff quadratic. Keep that representation key private to the
73/// index: value hashes and canonical interning stay intact.
74fn interning_hash(kind: Kind, fl: u8, lo: i64, hash: u64, data: &[Handle]) -> u64 {
75    if fl & flags::NESTED_VIEW == 0 {
76        return hash;
77    }
78    let header = u64::from(kind as u8) | (u64::from(fl & !flags::CONCRETE) << 8);
79    let hash = mix2(mix2(hash, header), lo.cast_unsigned());
80    data.iter().fold(hash, |key, h| mix2(key, h.bits()))
81}
82
83/// Whether a stored node is the one being interned. [`flags::CONCRETE`] is a
84/// cached proof, not identity, so it is ignored.
85fn same_identity(n: &View<'_>, kind: Kind, fl: u8, lo: i64, hash: u64, data: &[Handle]) -> bool {
86    n.kind == kind
87        && (n.flags & !flags::CONCRETE) == (fl & !flags::CONCRETE)
88        && n.lo == lo
89        && n.hash == hash
90        && n.data == data
91}
92
93/// A node's header fields.
94#[derive(Clone, Copy)]
95struct Head {
96    kind: Kind,
97    flags: u8,
98    lo: i64,
99    hash: u64,
100    sum: u64,
101}
102
103/// A stored node.
104trait Slot: Sized {
105    fn make(h: Head, data: &[Handle]) -> Self;
106    fn view(&self) -> View<'_>;
107}
108
109/// A node whose handles are inline (at most `K`).
110#[derive(Debug)]
111struct Inline<const K: usize> {
112    kind: Kind,
113    flags: u8,
114    len: u8,
115    lo: i64,
116    hash: u64,
117    sum: u64,
118    data: [Handle; K],
119}
120
121impl<const K: usize> Slot for Inline<K> {
122    fn make(
123        Head {
124            kind,
125            flags,
126            lo,
127            hash,
128            sum,
129        }: Head,
130        data: &[Handle],
131    ) -> Self {
132        let mut a = [Handle::EMPTY; K];
133        let n = data.len().min(K);
134        a[..n].copy_from_slice(&data[..n]);
135        #[allow(clippy::cast_possible_truncation, reason = "K is at most 8")]
136        let len = n as u8;
137        Self {
138            kind,
139            flags,
140            len,
141            lo,
142            hash,
143            sum,
144            data: a,
145        }
146    }
147
148    #[inline]
149    fn view(&self) -> View<'_> {
150        View {
151            kind: self.kind,
152            lo: self.lo,
153            hash: self.hash,
154            sum: self.sum,
155            flags: self.flags,
156            data: self
157                .data
158                .get(..usize::from(self.len))
159                .unwrap_or(&EMPTY_DATA),
160        }
161    }
162}
163
164/// A node of the largest class: its handles in their own allocation.
165#[derive(Debug)]
166struct Boxed {
167    kind: Kind,
168    flags: u8,
169    lo: i64,
170    hash: u64,
171    sum: u64,
172    data: Box<[Handle]>,
173}
174
175impl Slot for Boxed {
176    fn make(
177        Head {
178            kind,
179            flags,
180            lo,
181            hash,
182            sum,
183        }: Head,
184        data: &[Handle],
185    ) -> Self {
186        Self {
187            kind,
188            flags,
189            lo,
190            hash,
191            sum,
192            data: data.into(),
193        }
194    }
195
196    #[inline]
197    fn view(&self) -> View<'_> {
198        View {
199            kind: self.kind,
200            lo: self.lo,
201            hash: self.hash,
202            sum: self.sum,
203            flags: self.flags,
204            data: &self.data,
205        }
206    }
207}
208
209/// The log2 of every column's first chunk (16 slots). One base for all
210/// classes lets a read locate its slot before it dispatches on the class.
211const BASE: u32 = 4;
212
213/// One column: an append-only chunked vector of write-once slots.
214struct Column<T> {
215    chunks: [OnceLock<Box<[OnceLock<T>]>>; CHUNKS],
216}
217
218impl<T: Slot> Column<T> {
219    fn new() -> Self {
220        Self {
221            chunks: std::array::from_fn(|_| OnceLock::new()),
222        }
223    }
224
225    #[inline]
226    fn get(&self, (c, off): (usize, usize)) -> Option<&T> {
227        self.chunks.get(c)?.get()?.get(off)?.get()
228    }
229
230    fn allocated_bytes(&self) -> usize {
231        self.chunks
232            .iter()
233            .filter_map(OnceLock::get)
234            .map(|chunk| std::mem::size_of_val(chunk.as_ref()))
235            .sum()
236    }
237
238    /// Writes slot `index`. Called under the shard's lock, in index order.
239    fn put(&self, index: u64, node: T) -> bool {
240        let (c, off) = locate(index, BASE);
241        let Some(chunk) = self.chunks.get(c) else {
242            return false;
243        };
244        let chunk = chunk.get_or_init(|| {
245            (0..(1usize << (BASE as usize + c)))
246                .map(|_| OnceLock::new())
247                .collect()
248        });
249        chunk.get(off).is_some_and(|s| s.set(node).is_ok())
250    }
251}
252
253/// The class and index a table entry names.
254fn unpack(e: u64) -> (u8, u64) {
255    #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
256    let local = (e as u32).wrapping_sub(1);
257    #[allow(clippy::cast_possible_truncation, reason = "three class bits")]
258    let class = (local >> LOCAL_CLASS_SHIFT) as u8;
259    (class, u64::from(local & ((1 << LOCAL_CLASS_SHIFT) - 1)))
260}
261
262/// Probes `table` for a node with the low hash bits `h32` that `same`
263/// accepts, without a lock. `None` is a miss in this table only: an entry
264/// written meanwhile, or into a newer table, is found under the lock.
265#[inline]
266fn probe(table: &[AtomicU64], h32: u32, same: impl Fn(u8, u64) -> bool) -> Option<(u8, u64)> {
267    if table.is_empty() {
268        return None;
269    }
270    let mask = table.len() - 1;
271    let mut p = h32 as usize & mask;
272    loop {
273        let e = table[p].load(Ordering::Acquire);
274        if e == 0 {
275            return None;
276        }
277        #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
278        if (e >> 32) as u32 == h32 {
279            let (class, i) = unpack(e);
280            if same(class, i) {
281                return Some((class, i));
282            }
283        }
284        p = (p + 1) & mask;
285    }
286}
287
288/// The chunk and offset of slot `index` in a column with first chunk
289/// `2^base`.
290#[inline]
291fn locate(index: u64, base: u32) -> (usize, usize) {
292    let i = index + (1 << base);
293    let b = i.ilog2();
294    #[allow(
295        clippy::cast_possible_truncation,
296        reason = "bounded by CHUNKS and the chunk size"
297    )]
298    ((b - base) as usize, (i - (1 << b)) as usize)
299}
300
301/// A shard's node storage: one column per size class.
302struct Columns {
303    c4: Column<Inline<{ CAPS[0] }>>,
304    c8: Column<Inline<{ CAPS[1] }>>,
305    boxed: Column<Boxed>,
306    lazy: Column<Boxed>,
307}
308
309impl Columns {
310    fn new() -> Self {
311        Self {
312            c4: Column::new(),
313            c8: Column::new(),
314            boxed: Column::new(),
315            lazy: Column::new(),
316        }
317    }
318
319    #[allow(
320        clippy::inline_always,
321        reason = "the hottest read of the core; measured: a call here costs ~5% instructions on MCLamportMutex"
322    )]
323    #[inline(always)]
324    fn view(&self, class: u8, index: u64) -> Option<View<'_>> {
325        let at = locate(index, BASE);
326        if class == 0 {
327            self.c4.get(at).map(Slot::view)
328        } else if class == 1 {
329            self.c8.get(at).map(Slot::view)
330        } else if class == 2 {
331            self.boxed.get(at).map(Slot::view)
332        } else {
333            self.lazy.get(at).map(Slot::view)
334        }
335    }
336
337    fn put(&self, class: u8, index: u64, h: Head, d: &[Handle]) -> bool {
338        match class {
339            0 => self.c4.put(index, Slot::make(h, d)),
340            1 => self.c8.put(index, Slot::make(h, d)),
341            2 => self.boxed.put(index, Slot::make(h, d)),
342            3 => self.lazy.put(index, Slot::make(h, d)),
343            _ => false,
344        }
345    }
346}
347
348/// The deduplication index of one shard.
349///
350/// `table` is open addressing with linear probing. An entry is
351/// `(low 32 bits of the interning hash) << 32 | (local + 1)`, where `local` is
352/// `class << 29 | index`; zero is empty. The probe position is the low bits
353/// of the hash, so growing needs no node reads.
354struct Index {
355    lens: [u64; CLASSES],
356    table: Table,
357    used: usize,
358    hits: u64,
359    misses: u64,
360    handles: u64,
361    boxed_payload_bytes: usize,
362    retired: Vec<RetiredTable>,
363    rehash_scratch_bytes: usize,
364    largest_rehash_scratch_bytes: usize,
365}
366
367/// A shard's deduplication table. Entries are written once, under the
368/// shard's lock, after the node they name; readers load them without it.
369type Table = Arc<[AtomicU64]>;
370
371/// Weak records do not keep old table payload alive. They let accounting see
372/// tables held by `InternCache` readers after the index replaces its own Arc.
373struct RetiredTable {
374    table: Weak<[AtomicU64]>,
375}
376
377fn empty_table(cap: usize) -> Table {
378    (0..cap).map(|_| AtomicU64::new(0)).collect()
379}
380
381const LOCAL_CLASS_SHIFT: u32 = 29;
382
383impl Default for Index {
384    fn default() -> Self {
385        Self {
386            lens: [0; CLASSES],
387            table: empty_table(0),
388            used: 0,
389            hits: 0,
390            misses: 0,
391            handles: 0,
392            boxed_payload_bytes: 0,
393            retired: Vec::new(),
394            rehash_scratch_bytes: 0,
395            largest_rehash_scratch_bytes: 0,
396        }
397    }
398}
399
400impl Index {
401    /// Doubles the table into a new one; the old one stays valid for the
402    /// readers that hold it.
403    fn grow(&mut self) {
404        let cap = (self.table.len() * 2).max(64);
405        let t: Vec<u64> = {
406            let mut t = vec![0u64; cap];
407            let mask = cap - 1;
408            for e in self.table.iter() {
409                let e = e.load(Ordering::Relaxed);
410                if e != 0 {
411                    let mut p = (e >> 32) as usize & mask;
412                    while t[p] != 0 {
413                        p = (p + 1) & mask;
414                    }
415                    t[p] = e;
416                }
417            }
418            t
419        };
420        let scratch = t.capacity() * std::mem::size_of::<u64>();
421        self.rehash_scratch_bytes += scratch;
422        self.largest_rehash_scratch_bytes = self.largest_rehash_scratch_bytes.max(scratch);
423        if !self.table.is_empty() && Arc::strong_count(&self.table) > 1 {
424            self.retired.push(RetiredTable {
425                table: Arc::downgrade(&self.table),
426            });
427        }
428        self.table = t.into_iter().map(AtomicU64::new).collect();
429    }
430
431    fn memory_usage(&mut self, out: &mut StoreMemory) {
432        out.boxed_payload_bytes += self.boxed_payload_bytes;
433        out.current_table_bytes += std::mem::size_of_val(self.table.as_ref());
434        // Upgrading pins the payload while it is measured; a second reader does
435        // not multiply its allocation. Dead records release their Weak metadata.
436        self.retired.retain(|retired| {
437            if let Some(table) = retired.table.upgrade() {
438                out.retired_table_bytes += std::mem::size_of_val(table.as_ref());
439                out.retired_tables += 1;
440                true
441            } else {
442                false
443            }
444        });
445        out.retirement_tracking_bytes +=
446            self.retired.capacity() * std::mem::size_of::<RetiredTable>();
447        out.rehash_scratch_bytes += self.rehash_scratch_bytes;
448        out.largest_rehash_scratch_bytes = out
449            .largest_rehash_scratch_bytes
450            .max(self.largest_rehash_scratch_bytes);
451    }
452}
453
454/// One shard's lock, on its own cache line.
455#[repr(align(128))]
456struct Shard {
457    index: Mutex<Index>,
458}
459
460/// One shard's table generation, on its own cache line: bumped, under the
461/// lock, each time the table is replaced.
462#[repr(align(128))]
463#[derive(Default)]
464struct Generation(AtomicU64);
465
466/// A counter on its own cache line.
467#[repr(align(128))]
468#[derive(Default)]
469struct Padded(AtomicU64);
470
471/// Stripes of the lock-free hit counter.
472const HIT_STRIPES: usize = 16;
473
474/// A heap's view of the store's deduplication tables, for interning
475/// without the shard locks: the table of each shard it has
476/// interned into, with the generation it was read at, and the hits it has
477/// not yet added to the store's statistics.
478pub struct InternCache {
479    tables: Vec<Option<(u64, Table)>>,
480    hits: u64,
481    stripe: usize,
482    /// About the bytes of the nodes this heap has added to the store (a
483    /// node header and its handles each): what a caller that must bound
484    /// its persistent copies, such as a primed-definition memo site,
485    /// charges (`Machine::memo_eval`).
486    pub(crate) added: u64,
487}
488
489impl Default for InternCache {
490    fn default() -> Self {
491        static NEXT: AtomicU64 = AtomicU64::new(0);
492        #[allow(
493            clippy::cast_possible_truncation,
494            reason = "reduced modulo the stripes"
495        )]
496        let stripe = (NEXT.fetch_add(1, Ordering::Relaxed) as usize) % HIT_STRIPES;
497        Self {
498            tables: vec![None; SHARDS],
499            hits: 0,
500            stripe,
501            added: 0,
502        }
503    }
504}
505
506impl std::fmt::Debug for InternCache {
507    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
508        f.debug_struct("InternCache")
509            .field("hits", &self.hits)
510            .finish_non_exhaustive()
511    }
512}
513
514/// Intern statistics.
515#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
516pub struct StoreStats {
517    /// Interns that found an existing node.
518    pub hits: u64,
519    /// Interns that inserted a node.
520    pub misses: u64,
521    /// Nodes held.
522    pub nodes: u64,
523    /// Handles held by nodes.
524    pub handles: u64,
525    /// Nodes per size class (inline capacity 4, 8, then boxed, then lazy
526    /// constants).
527    pub classes: [u64; CLASSES],
528}
529
530/// The persistent store.
531pub struct Store {
532    cols: Box<[Columns]>,
533    shards: Box<[Shard]>,
534    generations: Box<[Generation]>,
535    hits: Box<[Padded]>,
536    strings: Strings,
537    hashcons: bool,
538    semantics: Semantics,
539    poisoned: AtomicBool,
540    /// The model's names, for printing ([`Store::set_printer`]).
541    printer: OnceLock<crate::print::Printer>,
542    /// Whether the plan may build an interval or a lazy set
543    /// ([`Store::lazy_sets`]).
544    lazy_sets: AtomicBool,
545    /// The run's random streams ([`Store::set_draws`]).
546    draws: OnceLock<std::sync::Arc<dyn crate::random::Draws>>,
547    /// The run's registers ([`Store::set_registers`]).
548    registers: OnceLock<std::sync::Arc<dyn crate::random::Registers>>,
549}
550
551/// The value semantics of a run, fixed for the store's life: the default
552/// profile's, or `--compat=tlc`'s ([`Semantics::tlc`]).
553#[derive(Clone, Copy, Debug, Default, PartialEq, Eq)]
554pub struct Semantics {
555    /// How strings compare.
556    pub string_order: StringOrder,
557    /// The integer semantics every heap on the store starts with.
558    pub int_mode: crate::int::IntMode,
559    /// TLC's comparisons (`--comparisons=tlc`) rather than TLA+'s: where
560    /// TLC's `equals`, `compareTo` or `member` may fail or answer otherwise
561    /// than TLA+, the core refuses (`compare.rs`).
562    pub tlc_comparisons: bool,
563    /// TLC's exploration order (`--explore-order=tlc`, A6): `x' \in S`
564    /// binds in the order of TLC's `elements()`, which the core follows
565    /// where it is the normalized order and refuses elsewhere.
566    pub tlc_exploration: bool,
567}
568
569impl Semantics {
570    /// `--compat=tlc`: token string order, 32-bit integers, TLC's
571    /// comparisons.
572    #[must_use]
573    pub const fn tlc() -> Self {
574        Self {
575            string_order: StringOrder::Token,
576            int_mode: crate::int::IntMode::Tlc,
577            tlc_comparisons: true,
578            tlc_exploration: true,
579        }
580    }
581}
582
583impl std::fmt::Debug for Store {
584    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
585        f.debug_struct("Store")
586            .field("stats", &self.stats())
587            .finish()
588    }
589}
590
591impl Default for Store {
592    fn default() -> Self {
593        Self::new(true)
594    }
595}
596
597impl Store {
598    /// A new store. `hashcons: false` is the `-hashcons` ablation: every
599    /// intern inserts a fresh node, and equality must be structural.
600    #[must_use]
601    pub fn new(hashcons: bool) -> Self {
602        Self::with_string_order(hashcons, StringOrder::Text)
603    }
604
605    /// A new store whose strings compare in `order` (`--compat=tlc` uses
606    /// [`StringOrder::Token`]). The order is fixed for the store's life,
607    /// because sets are kept sorted in it.
608    #[must_use]
609    pub fn with_string_order(hashcons: bool, order: StringOrder) -> Self {
610        Self::with_semantics(
611            hashcons,
612            Semantics {
613                string_order: order,
614                ..Semantics::default()
615            },
616        )
617    }
618
619    /// A new store with the run's value semantics, so that constant
620    /// folding, the search and trace replay all compute alike.
621    #[must_use]
622    pub fn with_semantics(hashcons: bool, semantics: Semantics) -> Self {
623        Self {
624            cols: (0..SHARDS).map(|_| Columns::new()).collect(),
625            shards: (0..SHARDS)
626                .map(|_| Shard {
627                    index: Mutex::new(Index::default()),
628                })
629                .collect(),
630            generations: (0..SHARDS).map(|_| Generation::default()).collect(),
631            hits: (0..HIT_STRIPES).map(|_| Padded::default()).collect(),
632            strings: Strings::new(semantics.string_order),
633            hashcons,
634            semantics,
635            poisoned: AtomicBool::new(false),
636            printer: OnceLock::new(),
637            lazy_sets: AtomicBool::new(false),
638            draws: OnceLock::new(),
639            registers: OnceLock::new(),
640        }
641    }
642
643    /// Sets the model's name table and value semantics, which printing
644    /// (`ToString`, `Print`) converts values with (`print.rs`). The first
645    /// call wins.
646    pub fn set_printer(&self, printer: crate::print::Printer) {
647        let _ = self.printer.set(printer);
648    }
649
650    /// Records that the plan may build a value TLC keeps as an interval or
651    /// a lazy set (`a..b`, `DOMAIN`, `SUBSET`, `[S -> T]`, `[a : S]`,
652    /// `S \X T`), which the core may enumerate: printing then refuses the
653    /// enumerated sets TLC could print otherwise (`print.rs`). Set while
654    /// compiling, before any search.
655    pub fn note_lazy_sets(&self) {
656        self.lazy_sets.store(true, Ordering::Relaxed);
657    }
658
659    /// Whether [`Store::note_lazy_sets`] was called.
660    #[must_use]
661    pub fn lazy_sets(&self) -> bool {
662        self.lazy_sets.load(Ordering::Relaxed)
663    }
664
665    /// Sets the run's random streams (`RandomElement`). The first call
666    /// wins.
667    pub fn set_draws(&self, draws: std::sync::Arc<dyn crate::random::Draws>) {
668        let _ = self.draws.set(draws);
669    }
670
671    /// The run's random streams, once set.
672    #[must_use]
673    pub fn draws(&self) -> Option<&std::sync::Arc<dyn crate::random::Draws>> {
674        self.draws.get()
675    }
676
677    /// Sets the run's `TLCSet`/`TLCGet` registers. The first call wins.
678    pub fn set_registers(&self, registers: std::sync::Arc<dyn crate::random::Registers>) {
679        let _ = self.registers.set(registers);
680    }
681
682    /// The run's registers, once set.
683    #[must_use]
684    pub fn registers(&self) -> Option<&std::sync::Arc<dyn crate::random::Registers>> {
685        self.registers.get()
686    }
687
688    /// The printer, once set.
689    #[must_use]
690    pub fn printer(&self) -> Option<&crate::print::Printer> {
691        self.printer.get()
692    }
693
694    /// Whether values are hash-consed.
695    #[must_use]
696    pub fn hashcons(&self) -> bool {
697        self.hashcons
698    }
699
700    /// The run's value semantics.
701    #[must_use]
702    pub fn semantics(&self) -> Semantics {
703        self.semantics
704    }
705
706    /// The integer semantics heaps on this store start with.
707    #[must_use]
708    pub fn int_mode(&self) -> crate::int::IntMode {
709        self.semantics.int_mode
710    }
711
712    /// The string table.
713    #[must_use]
714    pub fn strings(&self) -> &Strings {
715        &self.strings
716    }
717
718    /// Whether a read used a handle the store never issued (a bug).
719    #[must_use]
720    pub fn poisoned(&self) -> bool {
721        self.poisoned.load(Ordering::Relaxed)
722    }
723
724    /// The node behind a persistent handle. A handle the store did not issue
725    /// gives an empty set view and poisons the store.
726    #[inline]
727    pub(crate) fn view(&self, h: Handle) -> View<'_> {
728        let (s, class, i) = h.persistent_parts();
729        if let Some(v) = self.cols.get(usize::from(s)).and_then(|c| c.view(class, i)) {
730            v
731        } else {
732            self.poisoned.store(true, Ordering::Relaxed);
733            POISON_VIEW
734        }
735    }
736
737    /// Validates an opaque coordinate for the live-Store frontier codec without
738    /// turning corrupt file bytes into a poison read or a fabricated value.
739    pub(crate) fn retained_view(&self, handle: Handle) -> Option<View<'_>> {
740        if !handle.is_persistent() {
741            return None;
742        }
743        let (shard, class, index) = handle.persistent_parts();
744        if index > MAX_CLASS_INDEX {
745            return None;
746        }
747        self.cols
748            .get(usize::from(shard))
749            .and_then(|c| c.view(class, index))
750    }
751
752    /// Interns a node whose children are all persistent or scalar. Returns
753    /// the existing handle when an equal node is present. `cache` is the
754    /// interning heap's: a hit is found without the shard's lock.
755    #[allow(clippy::too_many_arguments, reason = "the node header, flat")]
756    pub(crate) fn intern(
757        &self,
758        cache: &mut InternCache,
759        kind: Kind,
760        flags: u8,
761        lo: i64,
762        hash: u64,
763        sum: u64,
764        data: &[Handle],
765    ) -> Handle {
766        let index_hash = interning_hash(kind, flags, lo, hash, data);
767        #[allow(clippy::cast_possible_truncation, reason = "the top eight bits")]
768        let s = (index_hash >> 56) as u8;
769        let (Some(shard), Some(cols), Some(generation)) = (
770            self.shards.get(usize::from(s)),
771            self.cols.get(usize::from(s)),
772            self.generations.get(usize::from(s)),
773        ) else {
774            self.poisoned.store(true, Ordering::Relaxed);
775            return Handle::EMPTY;
776        };
777        #[allow(clippy::cast_possible_truncation, reason = "the low 32 bits")]
778        let h32 = index_hash as u32;
779        let same = |class: u8, i: u64| {
780            cols.view(class, i)
781                .is_some_and(|n| same_identity(&n, kind, flags, lo, hash, data))
782        };
783        if self.hashcons {
784            // The lock-free probe of the cached table.
785            let g = generation.0.load(Ordering::Acquire);
786            let entry = cache.tables.get_mut(usize::from(s));
787            if let Some(entry) = entry {
788                if entry.as_ref().is_none_or(|(cg, _)| *cg != g) {
789                    let index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
790                    *entry = Some((
791                        generation.0.load(Ordering::Relaxed),
792                        Arc::clone(&index.table),
793                    ));
794                }
795                if let Some((_, table)) = entry.as_ref()
796                    && let Some(found) = probe(table, h32, same)
797                {
798                    cache.hits += 1;
799                    let (class, i) = found;
800                    return Handle::persistent(s, class, i);
801                }
802            }
803        }
804        let mut index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
805        let mut slot = None;
806        if self.hashcons {
807            if (index.used + 1) * 4 > index.table.len() * 3 {
808                index.grow();
809                generation.0.fetch_add(1, Ordering::Release);
810            }
811            let mask = index.table.len() - 1;
812            let mut p = h32 as usize & mask;
813            loop {
814                let e = index.table[p].load(Ordering::Relaxed);
815                if e == 0 {
816                    slot = Some(p);
817                    break;
818                }
819                #[allow(clippy::cast_possible_truncation, reason = "packed entry")]
820                if (e >> 32) as u32 == h32 {
821                    let (class, i) = unpack(e);
822                    if same(class, i) {
823                        index.hits += 1;
824                        return Handle::persistent(s, class, i);
825                    }
826                }
827                p = (p + 1) & mask;
828            }
829        }
830        let class = class_of(data.len(), flags);
831        let i = index.lens[usize::from(class)];
832        if i >= MAX_CLASS_INDEX
833            || !cols.put(
834                class,
835                i,
836                Head {
837                    kind,
838                    flags,
839                    lo,
840                    hash,
841                    sum,
842                },
843                data,
844            )
845        {
846            self.poisoned.store(true, Ordering::Relaxed);
847            return Handle::EMPTY;
848        }
849        index.lens[usize::from(class)] += 1;
850        index.misses += 1;
851        cache.added += (std::mem::size_of::<Head>() + std::mem::size_of_val(data)) as u64;
852        index.handles += data.len() as u64;
853        index.boxed_payload_bytes += usize::from(class >= 2) * std::mem::size_of_val(data);
854        if let Some(p) = slot {
855            #[allow(
856                clippy::cast_possible_truncation,
857                reason = "bounded by MAX_CLASS_INDEX"
858            )]
859            let local = (u32::from(class) << LOCAL_CLASS_SHIFT) | i as u32;
860            // After the node: a reader that sees the entry sees the node.
861            index.table[p].store(
862                (u64::from(h32) << 32) | u64::from(local + 1),
863                Ordering::Release,
864            );
865            index.used += 1;
866        }
867        Handle::persistent(s, class, i)
868    }
869
870    /// Adds a heap's lock-free hits to the statistics.
871    pub(crate) fn flush_hits(&self, cache: &mut InternCache) {
872        if cache.hits != 0 {
873            if let Some(c) = self.hits.get(cache.stripe) {
874                c.0.fetch_add(cache.hits, Ordering::Relaxed);
875            }
876            cache.hits = 0;
877        }
878    }
879
880    /// Intern statistics, summed over the shards.
881    #[must_use]
882    pub fn stats(&self) -> StoreStats {
883        let mut st = StoreStats::default();
884        for c in &self.hits {
885            st.hits += c.0.load(Ordering::Relaxed);
886        }
887        for shard in &self.shards {
888            let index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
889            st.hits += index.hits;
890            st.misses += index.misses;
891            st.handles += index.handles;
892            for (c, &n) in index.lens.iter().enumerate() {
893                st.nodes += n;
894                st.classes[c] += n;
895            }
896        }
897        st
898    }
899
900    /// Measures known requested retained bytes and capacities, including tables
901    /// still held by readers after index growth. Dead retirement records are
902    /// collected before reporting; their vector's spare capacity still counts.
903    ///
904    /// This read takes shard locks, without changing interning identities or
905    /// hit/miss counters. It is intended for phase boundaries, not the hot path.
906    /// See [`StoreMemory`] for opaque allocations and snapshot limitations.
907    ///
908    /// ```
909    /// let store = dive_core::Store::default();
910    /// let memory = store.memory_usage();
911    /// assert!(memory.fixed_bytes > 0);
912    /// assert_eq!(memory.slab_bytes, 0);
913    /// assert!(memory.known_retained_bytes().is_some());
914    /// ```
915    #[must_use]
916    pub fn memory_usage(&self) -> StoreMemory {
917        let mut out = StoreMemory {
918            fixed_bytes: std::mem::size_of::<Self>()
919                + std::mem::size_of_val(self.cols.as_ref())
920                + std::mem::size_of_val(self.shards.as_ref())
921                + std::mem::size_of_val(self.generations.as_ref())
922                + std::mem::size_of_val(self.hits.as_ref()),
923            strings: self.strings.memory_usage(),
924            has_printer: self.printer.get().is_some(),
925            has_draws: self.draws.get().is_some(),
926            has_registers: self.registers.get().is_some(),
927            ..StoreMemory::default()
928        };
929        for (cols, shard) in self.cols.iter().zip(&self.shards) {
930            let mut index = shard.index.lock().unwrap_or_else(PoisonError::into_inner);
931            out.slab_bytes += cols.c4.allocated_bytes()
932                + cols.c8.allocated_bytes()
933                + cols.boxed.allocated_bytes()
934                + cols.lazy.allocated_bytes();
935            index.memory_usage(&mut out);
936        }
937        out
938    }
939}
940
941#[cfg(test)]
942mod tests {
943    use super::*;
944
945    #[test]
946    fn locate_covers_indices_contiguously() {
947        for base in [4u32, 6, 8] {
948            let mut prev = (0usize, 0usize);
949            assert_eq!(locate(0, base), (0, 0));
950            for i in 1..5000u64 {
951                let (c, off) = locate(i, base);
952                if c == prev.0 {
953                    assert_eq!(off, prev.1 + 1);
954                } else {
955                    assert_eq!((c, off), (prev.0 + 1, 0));
956                    assert_eq!(prev.1 + 1, 1 << (base as usize + prev.0));
957                }
958                prev = (c, off);
959            }
960            let (c, _) = locate(MAX_CLASS_INDEX - 1, base);
961            assert!(c < CHUNKS, "the last index fits for base {base}");
962        }
963    }
964
965    fn int(v: i64) -> Handle {
966        Handle::int(v).unwrap_or(Handle::EMPTY)
967    }
968
969    #[test]
970    fn memory_counts_allocated_slabs_and_actual_boxed_payload() {
971        let store = Store::new(false);
972        let mut cache = InternCache::default();
973        let empty = store.memory_usage();
974        assert!(empty.fixed_bytes > 0);
975        assert_eq!(empty.slab_bytes, 0);
976        for i in 0..17 {
977            let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &[int(i)]);
978        }
979        let inline = store.memory_usage();
980        // Seventeen occupied slots retain both whole chunks: 16 + 32 slots.
981        assert_eq!(
982            inline.slab_bytes,
983            48 * std::mem::size_of::<OnceLock<Inline<4>>>()
984        );
985        assert_eq!(inline.boxed_payload_bytes, 0);
986        let five = [int(0); 5];
987        let nine = [int(0); 9];
988        let two = [int(0); 2];
989        let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &five);
990        let _ = store.intern(&mut cache, Kind::Set, 0, 0, 0, 0, &nine);
991        let _ = store.intern(
992            &mut cache,
993            Kind::Fcn,
994            crate::node::flags::RECORD,
995            0,
996            0,
997            0,
998            &two,
999        );
1000        let all = store.memory_usage();
1001        assert_eq!(all.fixed_bytes, empty.fixed_bytes);
1002        assert_eq!(
1003            all.slab_bytes,
1004            inline.slab_bytes
1005                + 16 * std::mem::size_of::<OnceLock<Inline<8>>>()
1006                + 32 * std::mem::size_of::<OnceLock<Boxed>>()
1007        );
1008        assert_eq!(all.boxed_payload_bytes, 11 * std::mem::size_of::<Handle>());
1009        assert_eq!(
1010            all.current_table_bytes, 0,
1011            "hashcons-off has no index tables"
1012        );
1013        assert_eq!(all.retired_tables, 0);
1014        assert_eq!(all.rehash_scratch_bytes, 0);
1015        assert!(all.known_retained_bytes() > inline.known_retained_bytes());
1016    }
1017
1018    #[test]
1019    fn memory_counts_shared_retired_tables_until_the_last_reader_drops() {
1020        let store = Store::default();
1021        let hash = 0xabcd_0000_0000_1234;
1022        let mut first = InternCache::default();
1023        let mut second = InternCache::default();
1024        let mut writer = InternCache::default();
1025        let initial = store.intern(&mut first, Kind::Set, 0, 0, hash, 0, &[int(0)]);
1026        assert_eq!(
1027            store.intern(&mut first, Kind::Set, 0, 0, hash, 0, &[int(0)]),
1028            initial
1029        );
1030        assert_eq!(
1031            store.intern(&mut second, Kind::Set, 0, 0, hash, 0, &[int(0)]),
1032            initial
1033        );
1034        for i in 1..49 {
1035            let _ = store.intern(&mut writer, Kind::Set, 0, 0, hash, 0, &[int(i)]);
1036        }
1037        let memory = store.memory_usage();
1038        assert_eq!(memory.current_table_bytes, 128 * std::mem::size_of::<u64>());
1039        assert_eq!(memory.retired_table_bytes, 64 * std::mem::size_of::<u64>());
1040        assert_eq!(
1041            memory.retired_tables, 1,
1042            "three readers share one allocation"
1043        );
1044        assert!(memory.retirement_tracking_bytes >= std::mem::size_of::<RetiredTable>());
1045        assert_eq!(
1046            memory.rehash_scratch_bytes,
1047            192 * std::mem::size_of::<u64>()
1048        );
1049        assert_eq!(
1050            memory.largest_rehash_scratch_bytes,
1051            memory.current_table_bytes
1052        );
1053        // Measuring is observational: counters and identities do not change.
1054        let stats = store.stats();
1055        assert_eq!(store.memory_usage(), memory);
1056        assert_eq!(store.stats(), stats);
1057        drop(writer);
1058        drop(first);
1059        assert_eq!(
1060            store.memory_usage().retired_table_bytes,
1061            memory.retired_table_bytes
1062        );
1063        drop(second);
1064        let released = store.memory_usage();
1065        assert_eq!(released.retired_table_bytes, 0);
1066        assert_eq!(released.retired_tables, 0);
1067        assert_eq!(released.current_table_bytes, memory.current_table_bytes);
1068        assert_eq!(
1069            released.retirement_tracking_bytes,
1070            memory.retirement_tracking_bytes
1071        );
1072        let shard = &store.shards[0xab];
1073        assert!(
1074            shard
1075                .index
1076                .lock()
1077                .unwrap_or_else(PoisonError::into_inner)
1078                .retired
1079                .is_empty(),
1080            "dead Weak records are removed, without hiding spare Vec capacity"
1081        );
1082    }
1083
1084    #[test]
1085    fn memory_does_not_charge_hashcons_hits_as_new_payload() {
1086        let store = Store::default();
1087        let mut cache = InternCache::default();
1088        let data = [int(1); 12];
1089        let original = store.intern(&mut cache, Kind::Set, 0, 0, 19, 0, &data);
1090        let before = store.memory_usage();
1091        for _ in 0..20 {
1092            assert_eq!(
1093                store.intern(&mut cache, Kind::Set, 0, 0, 19, 0, &data),
1094                original
1095            );
1096        }
1097        assert_eq!(store.memory_usage(), before);
1098        assert_eq!(before.boxed_payload_bytes, std::mem::size_of_val(&data));
1099        assert_eq!(store.stats().nodes, 1);
1100    }
1101
1102    #[test]
1103    fn every_size_class_round_trips_and_dedupes() {
1104        let store = Store::default();
1105        let mut c = InternCache::default();
1106        let mut got = Vec::new();
1107        for len in [0i64, 1, 4, 5, 8, 9, 16, 17, 32, 33, 100] {
1108            let data: Vec<Handle> = (0..len).map(int).collect();
1109            let hash = crate::handle::mix64(len.unsigned_abs() + 1);
1110            let h = store.intern(&mut c, Kind::Set, 0, 7, hash, 3, &data);
1111            let v = store.view(h);
1112            assert_eq!(v.data, data.as_slice(), "len {len}");
1113            assert_eq!((v.kind, v.lo, v.hash, v.sum), (Kind::Set, 7, hash, 3));
1114            assert_eq!(
1115                store.intern(&mut c, Kind::Set, 0, 7, hash, 3, &data),
1116                h,
1117                "len {len}"
1118            );
1119            got.push(h);
1120        }
1121        store.flush_hits(&mut c);
1122        let st = store.stats();
1123        assert_eq!(st.nodes, got.len() as u64);
1124        assert_eq!(st.hits, got.len() as u64);
1125        assert_eq!(st.classes, [3, 2, 6, 0]);
1126        assert!(!store.poisoned());
1127    }
1128
1129    #[test]
1130    fn colliding_hashes_are_told_apart_and_the_table_grows() {
1131        let store = Store::default();
1132        let mut c = InternCache::default();
1133        // Every node has the same hash: probing must compare contents.
1134        let hash = 0xabcd_0000_0000_1234;
1135        let hs: Vec<Handle> = (0..500)
1136            .map(|i| store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(i)]))
1137            .collect();
1138        for (i, &h) in (0..).zip(&hs) {
1139            assert_eq!(store.view(h).data, &[int(i)]);
1140            assert_eq!(store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(i)]), h);
1141        }
1142        // Distinct hashes in one shard, enough to grow the table repeatedly.
1143        for i in 0..5000u64 {
1144            let hash = (0x11u64 << 56) | crate::handle::mix64(i) >> 8;
1145            let a = store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(1)]);
1146            assert_eq!(store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(1)]), a);
1147        }
1148        assert_eq!(store.stats().nodes, 5500);
1149        assert!(!store.poisoned());
1150    }
1151
1152    #[test]
1153    fn concurrent_interns_dedupe_while_tables_grow() {
1154        // Every thread interns the same values, in different orders, so
1155        // that hits race inserts and growth, and every lock-free probe
1156        // either finds the node or falls back to the lock.
1157        let store = std::sync::Arc::new(Store::default());
1158        let threads: Vec<_> = (0..8u64)
1159            .map(|t| {
1160                let store = std::sync::Arc::clone(&store);
1161                std::thread::spawn(move || {
1162                    let mut c = InternCache::default();
1163                    let mut out = vec![Handle::EMPTY; 20_011];
1164                    for k in 0..20_011u64 {
1165                        let i = (k * (2 * t + 1)) % 20_011; // prime, so a permutation
1166                        let hash = crate::handle::mix64(i);
1167                        let v = i64::try_from(i).unwrap_or(0);
1168                        out[usize::try_from(i).unwrap_or(0)] =
1169                            store.intern(&mut c, Kind::Set, 0, 0, hash, 0, &[int(v)]);
1170                    }
1171                    store.flush_hits(&mut c);
1172                    out
1173                })
1174            })
1175            .collect();
1176        let all: Vec<Vec<Handle>> = threads.into_iter().filter_map(|t| t.join().ok()).collect();
1177        assert_eq!(all.len(), 8);
1178        for (i, h) in (0..).zip(&all[0]) {
1179            assert_eq!(store.view(*h).data, &[int(i)]);
1180        }
1181        assert!(all.iter().all(|o| *o == all[0]));
1182        let st = store.stats();
1183        assert_eq!(st.nodes, 20_011);
1184        assert_eq!(st.hits + st.misses, 8 * 20_011);
1185        let memory = store.memory_usage();
1186        assert!(memory.current_table_bytes > 0);
1187        assert_eq!(
1188            memory.retired_tables, 0,
1189            "all worker caches have been dropped"
1190        );
1191        assert_eq!(memory.retired_table_bytes, 0);
1192        assert!(!store.poisoned());
1193    }
1194
1195    #[test]
1196    fn without_hashconsing_every_intern_inserts() {
1197        let store = Store::new(false);
1198        let mut c = InternCache::default();
1199        let a = store.intern(&mut c, Kind::Set, 0, 0, 9, 9, &[int(1)]);
1200        let b = store.intern(&mut c, Kind::Set, 0, 0, 9, 9, &[int(1)]);
1201        assert_ne!(a, b);
1202        assert_eq!(store.view(a).data, store.view(b).data);
1203        assert_eq!(store.stats().nodes, 2);
1204    }
1205
1206    #[test]
1207    fn foreign_handles_poison_the_store() {
1208        let store = Store::default();
1209        let v = store.view(Handle::persistent(3, 0, 99));
1210        assert_eq!(v.data.len(), 0);
1211        assert!(store.poisoned());
1212    }
1213}