Skip to main content

dive_core/
heap.rs

1//! Value operations over both regions: views, hashing, equality, the
2//! canonical order, builders, materialization of symbolic sets, and interning
3//! by deep close.
4
5use std::cmp::Ordering;
6use std::sync::Arc;
7
8use crate::Error;
9use crate::arena::{Arena, Mark};
10use crate::handle::{Handle, K_FCN, K_SET, K_SYM, Tag, fin, int_hash, mix2, mix64, scalar_hash};
11use crate::node::{Kind, View, flags};
12use crate::store::Store;
13
14/// The largest set the core materializes.
15pub const MAX_MATERIALIZE: usize = 1 << 24;
16
17/// The most elements of a constant quantifier domain whose enumeration a
18/// heap keeps ([`Heap::enumerate_constant`]).
19pub const MAX_CONSTANT_DOMAIN: usize = 1 << 16;
20
21/// The most transient handle words (node headers plus data) the kept
22/// enumeration of one constant quantifier domain may add to a heap's store
23/// ([`Heap::enumerate_constant`]): elements that are large compounds are
24/// enumerated afresh instead of being retained.
25pub const MAX_CONSTANT_DOMAIN_WORDS: usize = 1 << 20;
26
27/// Maximum successful source nodes remembered by one local identity closure.
28pub const MAX_LOCAL_CLOSE_ENTRIES: usize = 65_536;
29/// Maximum aggregate live child-copy workspace in one local identity closure.
30pub const MAX_LOCAL_CLOSE_SCRATCH_BYTES: usize = 64 * 1024 * 1024;
31
32#[derive(Default)]
33struct LocalClose {
34    visited: std::collections::HashMap<Handle, Handle>,
35    scratch: usize,
36}
37
38impl LocalClose {
39    fn remember(&mut self, source: Handle, closed: Handle) -> Result<(), Error> {
40        if !self.visited.contains_key(&source) {
41            if self.visited.len() >= MAX_LOCAL_CLOSE_ENTRIES {
42                return Err(Error::unsupported(
43                    "candidate identity closure visited-node bound",
44                ));
45            }
46            self.visited
47                .try_reserve(1)
48                .map_err(|_| Error::unsupported("candidate identity closure map allocation"))?;
49        }
50        self.visited.insert(source, closed);
51        Ok(())
52    }
53}
54
55static EMPTY_DATA: [Handle; 0] = [];
56
57/// A worker's view of the value regions: the shared persistent store and its
58/// own arena.
59#[derive(Debug)]
60pub struct Heap {
61    pub(crate) store: Arc<Store>,
62    pub(crate) arena: Arena,
63    pub(crate) defer_reclamation: bool,
64    /// Candidate expansion must not promote speculative results through caches.
65    pub(crate) speculative: bool,
66    /// Whether [`Heap::string`] refuses a text the shared table lacks
67    /// ([`Heap::set_existing_strings_only`]).
68    strings: StringMode,
69    poisoned: std::cell::Cell<bool>,
70    /// `-delta-hash`: recompute hashes in full instead of incrementally.
71    pub(crate) full_hash: bool,
72    /// The integer semantics (`int.rs`).
73    pub(crate) int_mode: crate::int::IntMode,
74    /// Interned enumerations of persistent finite symbolic sets, for
75    /// [`Heap::materialize_cached`].
76    materialized: std::collections::HashMap<Handle, Handle>,
77    /// Persistent enumerations of constant quantifier domains, for
78    /// [`Heap::enumerate_constant`]; `None` for one that is not kept.
79    constant_domains: std::collections::HashMap<Handle, Option<Handle>>,
80    /// Interned images of persistent values under one reduction's maps
81    /// (`symmetry.rs`), keyed by map index and value, with the reduction
82    /// they belong to.
83    pub(crate) sym_images: crate::symmetry::ImageCache,
84    work_control: Option<Arc<dyn crate::eval::WorkControl>>,
85    work_steps: std::cell::Cell<u32>,
86    work_interrupted: std::cell::Cell<bool>,
87    /// This heap's copy of the string table's texts and ranks, by id,
88    /// extended on a miss: string comparisons read it without the table's
89    /// lock, which every worker would otherwise share.
90    names: std::cell::RefCell<Names>,
91    /// This heap's view of the store's deduplication tables, for interning
92    /// a value already present without the shard lock.
93    pub(crate) cache: crate::store::InternCache,
94}
95
96impl Drop for Heap {
97    fn drop(&mut self) {
98        self.store.flush_hits(&mut self.cache);
99    }
100}
101
102/// A heap's lock-free copy of the shared string table
103/// ([`crate::strings::Strings`]).
104///
105/// Ids never change their text, so the text copy never goes stale. Ranks
106/// shift as strings are interned, but never reorder two ids the table had
107/// already ranked together, so a rank copy that covers both ids of a
108/// comparison orders them as the table does now.
109#[derive(Debug, Default)]
110struct Names {
111    texts: Vec<Arc<str>>,
112    ranks: Arc<[u32]>,
113}
114
115impl Names {
116    /// Extends the copy when `id` is past it, taking the table's current
117    /// ranks with the new texts.
118    fn sync(&mut self, strings: &crate::strings::Strings, id: u32) {
119        if (id as usize) < self.texts.len() {
120            return;
121        }
122        let more = strings.texts_from(self.texts.len());
123        if more.is_empty() {
124            return;
125        }
126        self.texts.extend(more);
127        self.ranks = strings.ranks();
128    }
129}
130
131/// The closure of a lazy node ([`Heap::closure`]).
132#[derive(Clone, Copy, Debug)]
133pub struct Closure<'a> {
134    /// `Lambda` or `SetPred`.
135    pub kind: Kind,
136    /// The evaluator's closure id.
137    pub id: u32,
138    /// The function's domain, or the predicate's base set.
139    pub domain: Handle,
140    /// The captured values, in the evaluator's order.
141    pub captures: &'a [Handle],
142}
143
144/// The hash of a set with the given element-hash sum.
145#[must_use]
146pub fn set_hash(len: usize, sum: u64) -> u64 {
147    fin(K_SET, len as u64, sum)
148}
149
150/// The hash of a function with the given entry sum.
151#[must_use]
152pub fn fcn_hash(len: usize, sum: u64) -> u64 {
153    fin(K_FCN, len as u64, sum)
154}
155
156impl Heap {
157    /// A heap over `store` with a fresh arena.
158    #[must_use]
159    pub fn new(store: Arc<Store>, heap_arena: bool, full_hash: bool) -> Self {
160        let int_mode = store.int_mode();
161        Self {
162            store,
163            arena: Arena::new(heap_arena),
164            defer_reclamation: false,
165            speculative: false,
166            strings: StringMode::Intern,
167            poisoned: std::cell::Cell::new(false),
168            full_hash,
169            int_mode,
170            materialized: std::collections::HashMap::new(),
171            constant_domains: std::collections::HashMap::new(),
172            sym_images: crate::symmetry::ImageCache::default(),
173            work_control: None,
174            work_steps: std::cell::Cell::new(0),
175            work_interrupted: std::cell::Cell::new(false),
176            names: std::cell::RefCell::new(Names::default()),
177            cache: crate::store::InternCache::default(),
178        }
179    }
180
181    /// Compares two string or model-value ids in the table's order, as
182    /// [`crate::strings::Strings::cmp`] does: by the ranks in this heap's
183    /// copy when it ranks both ids, else from its copy of the texts.
184    #[inline]
185    pub(crate) fn str_cmp(&self, a: u32, b: u32) -> Ordering {
186        if a == b {
187            return Ordering::Equal;
188        }
189        {
190            let names = self.names.borrow();
191            if let (Some(x), Some(y)) = (names.ranks.get(a as usize), names.ranks.get(b as usize)) {
192                return x.cmp(y);
193            }
194        }
195        self.str_cmp_unranked(a, b)
196    }
197
198    /// [`Heap::str_cmp`] for an id outside this heap's rank copy: refreshes
199    /// the copy, then compares by rank, by token or by text.
200    #[inline(never)]
201    fn str_cmp_unranked(&self, a: u32, b: u32) -> Ordering {
202        let strings = self.store.strings();
203        let mut names = self.names.borrow_mut();
204        names.sync(strings, a.max(b));
205        if let (Some(x), Some(y)) = (names.ranks.get(a as usize), names.ranks.get(b as usize)) {
206            return x.cmp(y);
207        }
208        if strings.order() == crate::strings::StringOrder::Token {
209            return a.cmp(&b);
210        }
211        match (names.texts.get(a as usize), names.texts.get(b as usize)) {
212            (Some(x), Some(y)) => x.cmp(y),
213            _ => a.cmp(&b),
214        }
215    }
216
217    /// Whether the shared table has issued `id`.
218    #[inline]
219    pub(crate) fn known_name(&self, id: u32) -> bool {
220        if (id as usize) < self.names.borrow().texts.len() {
221            return true;
222        }
223        let mut names = self.names.borrow_mut();
224        names.sync(self.store.strings(), id);
225        (id as usize) < names.texts.len()
226    }
227
228    /// TLC's model-value type for a name, using this heap's append-only
229    /// text copy. The rule counts UTF-16 units, as `ModelValue` does.
230    pub(crate) fn model_type(&self, id: u32) -> Option<u16> {
231        let mut names = self.names.borrow_mut();
232        names.sync(self.store.strings(), id);
233        let mut units = names.texts.get(id as usize)?.encode_utf16();
234        let (first, second) = (units.next()?, units.next()?);
235        (second == u16::from(b'_') && units.next().is_some()).then_some(first)
236    }
237
238    /// The store.
239    #[must_use]
240    pub fn store(&self) -> &Arc<Store> {
241        &self.store
242    }
243
244    /// The arena.
245    #[must_use]
246    pub fn arena(&self) -> &Arena {
247        &self.arena
248    }
249
250    /// Frees the transients of the current expansion.
251    pub fn reset(&mut self) {
252        self.arena.reset();
253        self.store.flush_hits(&mut self.cache);
254    }
255
256    /// The current transient allocation point.
257    #[must_use]
258    pub fn mark(&self) -> Mark {
259        self.arena.mark()
260    }
261
262    /// Frees every transient allocated after `mark`. No handle allocated
263    /// after the mark may be used afterwards, including one held in a frame
264    /// slot or a thunk cache; such a use is detected as stale.
265    pub fn rollback(&mut self, mark: Mark) {
266        if !self.defer_reclamation {
267            self.arena.rollback(mark);
268        }
269    }
270
271    /// Whether an invalid handle read was detected: an internal error.
272    ///
273    /// Persistent handles are coordinates within one [`Store`]. Callers must
274    /// keep them with their issuing `Store`; equal coordinates from another `Store` cannot
275    /// be distinguished from a locally issued handle by this check.
276    #[must_use]
277    pub fn poisoned(&self) -> bool {
278        self.poisoned.get() || self.arena.stale() || self.store.poisoned()
279    }
280
281    /// The view of a compound handle. A stale or scalar handle gives an empty
282    /// set view and poisons the heap.
283    #[must_use]
284    #[inline]
285    pub fn view(&self, h: Handle) -> View<'_> {
286        if h.is_persistent() {
287            return self.store.view(h);
288        }
289        if h.is_transient()
290            && let Some(v) = self.arena.lookup(h)
291        {
292            return v;
293        }
294        self.poison_view()
295    }
296
297    #[cold]
298    fn poison_view(&self) -> View<'_> {
299        self.poisoned.set(true);
300        View {
301            kind: Kind::Set,
302            lo: 0,
303            hash: 0,
304            sum: 0,
305            flags: 0,
306            data: &EMPTY_DATA,
307        }
308    }
309
310    /// Records an internal error: a lazy value reached an operation that
311    /// needs a closed one.
312    #[cold]
313    fn lazy_misuse(&self) {
314        self.poisoned.set(true);
315    }
316
317    /// The hash and flags of a child, for builders: no closedness check.
318    #[inline]
319    fn child(&self, h: Handle) -> (u64, u8) {
320        if let Some(s) = scalar_hash(h) {
321            return (s, 0);
322        }
323        let v = self.view(h);
324        let hash = if self.full_hash {
325            self.deep_hash(h)
326        } else {
327            v.hash
328        };
329        (
330            hash,
331            (v.flags & flags::LAZY) | (v.flags & flags::NESTED_VIEW),
332        )
333    }
334
335    /// Whether a child is proved materialized without walking it: a known
336    /// scalar, an eager big integer, or a node carrying [`flags::CONCRETE`].
337    /// `false` proves nothing (`compare::materialized` decides).
338    #[inline]
339    fn concrete_child(&self, h: Handle) -> bool {
340        if !h.is_compound() {
341            return h
342                .as_str_id()
343                .or_else(|| h.as_model_id())
344                .is_none_or(|id| self.known_name(id));
345        }
346        let v = self.view(h);
347        v.flags & flags::CONCRETE != 0 || (v.kind == Kind::BigInt && !v.is_lazy())
348    }
349
350    /// [`flags::CONCRETE`] when every child is [`Heap::concrete_child`].
351    fn concrete_bit(&self, children: &[Handle]) -> u8 {
352        if children.iter().all(|&c| self.concrete_child(c)) {
353            flags::CONCRETE
354        } else {
355            0
356        }
357    }
358
359    /// Whether a value is proved materialized by a cached fact, without a
360    /// walk: a boolean, an inline integer, a string or model value whose name
361    /// this heap's [`Store`] issued, an eager big integer, or a persistent
362    /// eager node carrying [`flags::CONCRETE`] (an eager `Set`, `IntFcn` or
363    /// `Fcn` whose every descendant is materialized, as
364    /// `compare::materialized` defines it). `false` proves nothing: snapshot
365    /// restore, owned exchange and candidate decoding clear the bit, and
366    /// [`Heap::materialized_within`] then decides.
367    #[must_use]
368    pub fn proved_concrete(&self, h: Handle) -> bool {
369        if h.is_empty() || h.is_transient() {
370            return false;
371        }
372        if !h.is_compound() {
373            return h
374                .as_str_id()
375                .or_else(|| h.as_model_id())
376                .is_none_or(|id| self.known_name(id));
377        }
378        let v = self.view(h);
379        !v.is_lazy()
380            && v.flags & flags::UNNORM == 0
381            && (v.flags & flags::CONCRETE != 0 || v.kind == Kind::BigInt)
382    }
383
384    /// Whether every root is materialized as `compare::materialized`
385    /// defines it (no lazy, symbolic or unnormalized node and no unknown name
386    /// at any depth), decided by an iterative walk over at most `nodes`
387    /// handles. Transient and empty handles decline. `false` proves nothing:
388    /// an exhausted allowance or a failed scratch allocation also declines,
389    /// and so does a heap that is poisoned when the walk ends.
390    ///
391    /// Without `name_bytes`, a node carrying [`flags::CONCRETE`] is trusted
392    /// and not entered. With `name_bytes: Some(n)` every node is entered,
393    /// and the text bytes of every string and model-value occurrence count
394    /// against `n`.
395    #[must_use]
396    pub fn materialized_within(
397        &self,
398        roots: &[Handle],
399        nodes: usize,
400        name_bytes: Option<usize>,
401    ) -> bool {
402        let mut pending = Vec::new();
403        if pending.try_reserve(roots.len()).is_err() {
404            return false;
405        }
406        pending.extend_from_slice(roots);
407        let (mut work, mut bytes) = (0usize, 0usize);
408        while let Some(h) = pending.pop() {
409            work += 1;
410            if work > nodes || h.is_empty() || h.is_transient() {
411                return false;
412            }
413            if !h.is_compound() {
414                let Some(id) = h.as_str_id().or_else(|| h.as_model_id()) else {
415                    continue;
416                };
417                if !self.known_name(id) {
418                    return false;
419                }
420                if let Some(limit) = name_bytes {
421                    let Some(len) = self.names.borrow().texts.get(id as usize).map(|t| t.len())
422                    else {
423                        return false;
424                    };
425                    bytes = bytes.saturating_add(len);
426                    if bytes > limit {
427                        return false;
428                    }
429                }
430                continue;
431            }
432            let v = self.view(h);
433            if v.is_lazy() || v.flags & flags::UNNORM != 0 {
434                return false;
435            }
436            if name_bytes.is_none() && v.flags & flags::CONCRETE != 0 {
437                continue;
438            }
439            match v.kind {
440                Kind::BigInt => continue,
441                Kind::Set | Kind::IntFcn | Kind::Fcn => {}
442                _ => return false,
443            }
444            if v.data.len() > nodes.saturating_sub(work).saturating_sub(pending.len())
445                || pending.try_reserve(v.data.len()).is_err()
446            {
447                return false;
448            }
449            pending.extend_from_slice(v.data);
450        }
451        !self.poisoned()
452    }
453
454    /// Whether a value must be closed by the evaluator before it is hashed,
455    /// compared or interned (ยง11.3).
456    #[must_use]
457    pub fn is_lazy(&self, h: Handle) -> bool {
458        h.is_compound() && self.view(h).is_lazy()
459    }
460
461    /// The kind of a compound, `None` for a scalar.
462    #[must_use]
463    pub fn kind(&self, h: Handle) -> Option<Kind> {
464        h.is_compound().then(|| self.view(h).kind)
465    }
466
467    /// The value hash of a closed value. Finite symbolic sets must be
468    /// normalized first. A lazy value poisons the heap.
469    #[must_use]
470    pub fn hash(&self, h: Handle) -> u64 {
471        if let Some(s) = scalar_hash(h) {
472            return s;
473        }
474        let v = self.view(h);
475        if v.is_lazy() {
476            self.lazy_misuse();
477        }
478        if self.full_hash {
479            return self.deep_hash(h);
480        }
481        v.hash
482    }
483
484    /// The hash recomputed from the leaves, ignoring cached child hashes
485    /// (the `-delta-hash` ablation).
486    #[must_use]
487    pub fn deep_hash(&self, h: Handle) -> u64 {
488        if let Some(s) = scalar_hash(h) {
489            return s;
490        }
491        let v = self.view(h);
492        match v.kind {
493            Kind::Set => {
494                let sum = v
495                    .data
496                    .iter()
497                    .fold(0u64, |a, &e| a.wrapping_add(self.deep_hash(e)));
498                set_hash(v.data.len(), sum)
499            }
500            Kind::IntFcn => {
501                let mut sum = 0u64;
502                for (i, &x) in v.data.iter().enumerate() {
503                    #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
504                    let k = v.lo + i as i64;
505                    sum = sum.wrapping_add(mix2(int_hash(k), self.deep_hash(x)));
506                }
507                fcn_hash(v.data.len(), sum)
508            }
509            Kind::Fcn => {
510                let mut sum = 0u64;
511                for (&k, &x) in v.keys().iter().zip(v.values()) {
512                    sum = sum.wrapping_add(mix2(self.deep_hash(k), self.deep_hash(x)));
513                }
514                fcn_hash(v.len(), sum)
515            }
516            _ => v.hash,
517        }
518    }
519
520    // ------------------------------------------------------------------
521    // Equality and order
522    // ------------------------------------------------------------------
523
524    /// Value equality of two normalized handles.
525    #[must_use]
526    pub fn eq(&self, a: Handle, b: Handle) -> bool {
527        if a == b {
528            return true;
529        }
530        if !a.is_compound() || !b.is_compound() {
531            return false;
532        }
533        if a.is_persistent()
534            && b.is_persistent()
535            && self.store.hashcons()
536            && !a.is_lazy_persistent()
537            && !b.is_lazy_persistent()
538        {
539            return false;
540        }
541        let (va, vb) = (self.view(a), self.view(b));
542        if va.is_lazy() || vb.is_lazy() {
543            self.lazy_misuse();
544            return false;
545        }
546        if va.hash != vb.hash
547            || va.kind != vb.kind
548            || (va.kind != Kind::Set && va.lo != vb.lo)
549            || va.data.len() != vb.data.len()
550        {
551            return false;
552        }
553        va.data.iter().zip(vb.data).all(|(&x, &y)| self.eq(x, y))
554    }
555
556    /// The rank of a handle's class in the canonical order: model
557    /// values, booleans, integers, strings, then compounds.
558    fn scalar_rank(h: Handle) -> u8 {
559        match h.tag() {
560            Tag::Empty => 0,
561            Tag::Model => 1,
562            Tag::Bool => 2,
563            Tag::Int => 3,
564            Tag::Str => 4,
565            Tag::Persistent | Tag::Transient => 5,
566        }
567    }
568
569    fn kind_rank(k: Kind) -> u8 {
570        match k {
571            Kind::Set => 4,
572            Kind::IntFcn | Kind::Fcn => 5,
573            _ => 6,
574        }
575    }
576
577    /// The canonical total order (the default profile's value order): model values by name, booleans,
578    /// integers, strings by text, finite sets by size then elements,
579    /// functions by size, domain then values, then symbolic sets
580    /// structurally. Consistent with
581    /// [`Heap::eq`] on normalized handles.
582    #[must_use]
583    pub fn cmp(&self, a: Handle, b: Handle) -> Ordering {
584        if a == b {
585            return Ordering::Equal;
586        }
587        let (mut ra, mut rb) = (Self::scalar_rank(a), Self::scalar_rank(b));
588        if ra != rb {
589            // A big integer is a compound that ranks among the integers.
590            if a.is_compound() && self.view(a).kind == Kind::BigInt {
591                ra = 3;
592            }
593            if b.is_compound() && self.view(b).kind == Kind::BigInt {
594                rb = 3;
595            }
596            if ra != rb {
597                return ra.cmp(&rb);
598            }
599            return self.int_cmp(a, b).unwrap_or(Ordering::Equal);
600        }
601        match a.tag() {
602            Tag::Bool => a.as_bool().cmp(&b.as_bool()),
603            Tag::Int => a.as_int().cmp(&b.as_int()),
604            Tag::Str => match (a.as_str_id(), b.as_str_id()) {
605                (Some(x), Some(y)) => self.str_cmp(x, y),
606                _ => Ordering::Equal,
607            },
608            // By name, as strings.
609            Tag::Model => match (a.as_model_id(), b.as_model_id()) {
610                (Some(x), Some(y)) => self.str_cmp(x, y),
611                _ => Ordering::Equal,
612            },
613            Tag::Persistent | Tag::Transient => self.cmp_compound(a, b),
614            Tag::Empty => Ordering::Equal,
615        }
616    }
617
618    fn cmp_compound(&self, a: Handle, b: Handle) -> Ordering {
619        let (va, vb) = (self.view(a), self.view(b));
620        if va.is_lazy() || vb.is_lazy() {
621            self.lazy_misuse();
622            return Ordering::Equal;
623        }
624        if va.kind == Kind::BigInt || vb.kind == Kind::BigInt {
625            return match (va.kind == Kind::BigInt, vb.kind == Kind::BigInt) {
626                (true, true) => self.int_cmp(a, b).unwrap_or(Ordering::Equal),
627                (true, false) => Ordering::Less,
628                _ => Ordering::Greater,
629            };
630        }
631        let (ra, rb) = (Self::kind_rank(va.kind), Self::kind_rank(vb.kind));
632        if ra != rb {
633            return ra.cmp(&rb);
634        }
635        match (va.kind, vb.kind) {
636            (Kind::Set, Kind::Set) => va.data.len().cmp(&vb.data.len()).then_with(|| {
637                for (&x, &y) in va.data.iter().zip(vb.data) {
638                    let c = self.cmp(x, y);
639                    if c != Ordering::Equal {
640                        return c;
641                    }
642                }
643                Ordering::Equal
644            }),
645            // Two tuples, or integer-domain functions with the same domain:
646            // the domains are equal, so only the values decide.
647            (Kind::IntFcn, Kind::IntFcn) if va.lo == vb.lo && va.data.len() == vb.data.len() => {
648                for (&x, &y) in va.data.iter().zip(vb.data) {
649                    let c = self.cmp(x, y);
650                    if c != Ordering::Equal {
651                        return c;
652                    }
653                }
654                Ordering::Equal
655            }
656            (ka, kb) if ka.is_fcn() && kb.is_fcn() => {
657                let n = va.len();
658                n.cmp(&vb.len()).then_with(|| {
659                    for i in 0..n {
660                        let c = self.cmp(fcn_key(&va, i), fcn_key(&vb, i));
661                        if c != Ordering::Equal {
662                            return c;
663                        }
664                    }
665                    for (&x, &y) in va.values().iter().zip(vb.values()) {
666                        let c = self.cmp(x, y);
667                        if c != Ordering::Equal {
668                            return c;
669                        }
670                    }
671                    Ordering::Equal
672                })
673            }
674            (ka, kb) => (ka as u8)
675                .cmp(&(kb as u8))
676                .then(va.lo.cmp(&vb.lo))
677                .then(va.data.len().cmp(&vb.data.len()))
678                .then_with(|| {
679                    for (&x, &y) in va.data.iter().zip(vb.data) {
680                        let c = self.cmp(x, y);
681                        if c != Ordering::Equal {
682                            return c;
683                        }
684                    }
685                    Ordering::Equal
686                }),
687        }
688    }
689
690    // ------------------------------------------------------------------
691    // Builders
692    // ------------------------------------------------------------------
693
694    /// A set from normalized elements in any order, with duplicates.
695    pub fn set_from(&mut self, elems: &mut Vec<Handle>) -> Handle {
696        if elems.len() > 1 {
697            elems.sort_unstable_by(|&a, &b| self.cmp(a, b));
698            elems.dedup_by(|a, b| self.eq(*a, *b));
699        }
700        self.set_sorted(elems)
701    }
702
703    /// A set from sorted, distinct, closed elements. A lazy element poisons
704    /// the heap (ยง11.3).
705    pub fn set_sorted(&mut self, elems: &[Handle]) -> Handle {
706        let mut sum = 0u64;
707        let mut lazy = 0;
708        for &e in elems {
709            let (h, f) = self.child(e);
710            sum = sum.wrapping_add(h);
711            lazy |= f;
712        }
713        if lazy & flags::LAZY != 0 {
714            self.lazy_misuse();
715        }
716        let concrete = self.concrete_bit(elems);
717        self.arena.alloc(
718            Kind::Set,
719            concrete,
720            0,
721            set_hash(elems.len(), sum),
722            sum,
723            elems,
724        )
725    }
726
727    /// The empty set.
728    pub fn empty_set(&mut self) -> Handle {
729        self.set_sorted(&[])
730    }
731
732    /// A function over `lo..lo+n-1` from normalized values.
733    pub fn int_fcn(&mut self, lo: i64, vals: &[Handle]) -> Handle {
734        self.int_fcn_as(lo, vals, 0)
735    }
736
737    pub(crate) fn int_fcn_as(&mut self, lo: i64, vals: &[Handle], view: u8) -> Handle {
738        let lo = if vals.is_empty() { 1 } else { lo };
739        let mut sum = 0u64;
740        let mut fl = 0;
741        for (i, &v) in vals.iter().enumerate() {
742            #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
743            let k = lo + i as i64;
744            let (h, f) = self.child(v);
745            sum = sum.wrapping_add(mix2(int_hash(k), h));
746            fl |= f;
747        }
748        if fl & flags::LAZY == 0 {
749            fl |= self.concrete_bit(vals);
750        }
751        self.arena.alloc(
752            Kind::IntFcn,
753            fl | view,
754            lo,
755            fcn_hash(vals.len(), sum),
756            sum,
757            vals,
758        )
759    }
760
761    /// A tuple (a function over `1..n`).
762    pub fn tuple(&mut self, vals: &[Handle]) -> Handle {
763        self.int_fcn(1, vals)
764    }
765
766    /// A tuple literal `<<v1, ...>>`: the tuple [`Heap::tuple`] builds, with
767    /// the view bit [`flags::TUPLE`] (as [`Heap::record`]).
768    pub fn tuple_literal(&mut self, vals: &[Handle]) -> Handle {
769        self.int_fcn_as(1, vals, flags::TUPLE)
770    }
771
772    /// A function from sorted, distinct, closed keys and their values (which
773    /// may be lazy), in canonical form.
774    pub fn fcn_sorted(&mut self, keys: &[Handle], vals: &[Handle]) -> Handle {
775        self.fcn_sorted_as(keys, vals, 0)
776    }
777
778    pub(crate) fn fcn_sorted_as(&mut self, keys: &[Handle], vals: &[Handle], view: u8) -> Handle {
779        if let Some(lo) = contiguous_ints(keys) {
780            return self.int_fcn(lo, vals);
781        }
782        let mut sum = 0u64;
783        let mut fl = 0;
784        for (&k, &v) in keys.iter().zip(vals) {
785            let (kh, kf) = self.child(k);
786            let (vh, vf) = self.child(v);
787            // Only a lazy key is a misuse. A key may be a closed view (a
788            // tuple of records an exact intern marked `NESTED_VIEW`), which
789            // is then retained like a value's view.
790            if kf & flags::LAZY != 0 {
791                self.lazy_misuse();
792            }
793            sum = sum.wrapping_add(mix2(kh, vh));
794            fl |= kf | vf;
795        }
796        let mut data = Vec::with_capacity(keys.len() * 2);
797        data.extend_from_slice(keys);
798        data.extend_from_slice(vals);
799        if fl & flags::LAZY == 0 {
800            fl |= self.concrete_bit(&data);
801        }
802        self.arena.alloc(
803            Kind::Fcn,
804            fl | view,
805            0,
806            fcn_hash(keys.len(), sum),
807            sum,
808            &data,
809        )
810    }
811
812    /// A function from `(key, value)` pairs with distinct keys, any order.
813    pub fn fcn_from_pairs(&mut self, pairs: &mut [(Handle, Handle)]) -> Handle {
814        pairs.sort_unstable_by(|a, b| self.cmp(a.0, b.0));
815        let keys: Vec<Handle> = pairs.iter().map(|p| p.0).collect();
816        let vals: Vec<Handle> = pairs.iter().map(|p| p.1).collect();
817        self.fcn_sorted(&keys, &vals)
818    }
819
820    /// A record literal `[f1 |-> v1, ...]` from sorted, distinct string keys:
821    /// the function [`Heap::fcn_sorted`] builds, with [`flags::RECORD`]. The
822    /// bit is a view bit: equality, hashing, order and [`Heap::intern`]
823    /// ignore it, and [`Heap::intern_view`] keeps it.
824    pub fn record(&mut self, keys: &[Handle], vals: &[Handle]) -> Handle {
825        self.fcn_sorted_as(keys, vals, flags::RECORD)
826    }
827
828    #[cfg(test)]
829    pub(crate) fn canonical_test_set(&mut self, elems: &[Handle]) -> Result<Handle, Error> {
830        crate::compare::require_materialized(self, elems)?;
831        Ok(self.set_from(&mut elems.to_vec()))
832    }
833
834    /// A set enumeration `{e1, ...}` as TLC builds it before normalizing:
835    /// the normalized, closed elements in construction order, duplicates kept, as a
836    /// [`Kind::SetEnum`] view with [`flags::UNNORM`]. It is normalized,
837    /// hashed and interned as the set of its elements; only membership and
838    /// error paths that the contract names read its order.
839    pub fn set_enum(&mut self, elems: &[Handle]) -> Handle {
840        self.symbolic(Kind::SetEnum, 0, elems)
841    }
842
843    /// The same function with the entry at index `i` replaced, hashing in
844    /// O(1) from the stored sum.
845    #[allow(
846        clippy::many_single_char_names,
847        reason = "short names for the hash algebra"
848    )]
849    pub fn fcn_with(&mut self, f: Handle, i: usize, new: Handle) -> Handle {
850        let v = self.view(f);
851        let (kind, lo, sum, n, was_lazy) = (v.kind, v.lo, v.sum, v.len(), v.is_lazy());
852        let was_concrete = v.flags & flags::CONCRETE != 0;
853        // TLC's `RecordValue` and `TupleValue` EXCEPT keep their class.
854        let record = v.flags & (flags::RECORD | flags::TUPLE);
855        let mut data = v.data.to_vec();
856        let (key_hash, slot) = match kind {
857            Kind::IntFcn => {
858                #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
859                let k = lo + i as i64;
860                (int_hash(k), i)
861            }
862            _ => (self.child(data[i]).0, n + i),
863        };
864        let old = data[slot];
865        data[slot] = new;
866        // Recount laziness only when it may have changed; O(1) otherwise.
867        let fl = if was_lazy {
868            let vals = if kind == Kind::IntFcn {
869                &data[..]
870            } else {
871                &data[n..]
872            };
873            vals.iter().fold(0, |a, &x| a | self.child(x).1)
874        } else {
875            (v.flags & flags::NESTED_VIEW) | self.child(new).1
876        };
877        let sum = if self.full_hash {
878            // `-delta-hash`: recompute the sum from every entry.
879            let mut s = 0u64;
880            for j in 0..n {
881                let (kh, x) = match kind {
882                    Kind::IntFcn => {
883                        #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
884                        let k = lo + j as i64;
885                        (int_hash(k), data[j])
886                    }
887                    _ => (self.child(data[j]).0, data[n + j]),
888                };
889                s = s.wrapping_add(mix2(kh, self.child(x).0));
890            }
891            s
892        } else {
893            sum.wrapping_sub(mix2(key_hash, self.child(old).0))
894                .wrapping_add(mix2(key_hash, self.child(new).0))
895        };
896        let concrete = if was_concrete && fl & flags::LAZY == 0 && self.concrete_child(new) {
897            flags::CONCRETE
898        } else {
899            0
900        };
901        self.arena.alloc(
902            kind,
903            fl | record | concrete,
904            lo,
905            fcn_hash(n, sum),
906            sum,
907            &data,
908        )
909    }
910
911    /// A symbolic set node. Its hash is structural, not extensional: a
912    /// finite symbolic set is normalized before it is hashed as a value.
913    pub fn symbolic(&mut self, kind: Kind, lo: i64, data: &[Handle]) -> Handle {
914        let mut h = mix64(K_SYM ^ (kind as u64) ^ lo.cast_unsigned().rotate_left(17));
915        let mut fl = if kind.is_lazy() { flags::LAZY } else { 0 };
916        for &d in data {
917            let (dh, df) = self.child(d);
918            h = mix2(h, dh);
919            fl |= df;
920        }
921        if kind == Kind::SetEnum {
922            if fl & flags::LAZY != 0 {
923                self.lazy_misuse();
924            }
925            fl |= flags::UNNORM;
926        }
927        self.arena.alloc(kind, fl, lo, h, 0, data)
928    }
929
930    /// `[x \in domain |-> e]`, unmaterialized: the evaluator's closure
931    /// `closure` over `captures` (ยง11.2). Lazy.
932    pub fn lambda(&mut self, closure: u32, domain: Handle, captures: &[Handle]) -> Handle {
933        self.closure_node(Kind::Lambda, closure, domain, captures)
934    }
935
936    /// `{x \in base : P}`, unenumerated: the evaluator's closure `closure`
937    /// over `captures` (ยง11.2). Lazy.
938    pub fn set_pred(&mut self, closure: u32, base: Handle, captures: &[Handle]) -> Handle {
939        self.closure_node(Kind::SetPred, closure, base, captures)
940    }
941
942    fn closure_node(&mut self, kind: Kind, id: u32, first: Handle, captures: &[Handle]) -> Handle {
943        let mut data = Vec::with_capacity(captures.len() + 1);
944        data.push(first);
945        data.extend_from_slice(captures);
946        self.symbolic(kind, i64::from(id), &data)
947    }
948
949    /// `a \cup b`, kept symbolic (TLC's `SetCupValue`): membership is
950    /// either side's, and it is enumerated only when normalized.
951    pub fn union(&mut self, a: Handle, b: Handle) -> Handle {
952        self.symbolic(Kind::Union, 0, &[a, b])
953    }
954
955    /// The closure of a `Lambda` or `SetPred` node.
956    #[must_use]
957    pub fn closure(&self, h: Handle) -> Option<Closure<'_>> {
958        if !h.is_compound() {
959            return None;
960        }
961        let v = self.view(h);
962        if !v.kind.is_lazy() {
963            return None;
964        }
965        let (&first, captures) = v.data.split_first()?;
966        Some(Closure {
967            kind: v.kind,
968            id: u32::try_from(v.lo).ok()?,
969            domain: first,
970            captures,
971        })
972    }
973
974    /// The same kind as `h` with new contents, in canonical form and
975    /// rehashed: a set is re-sorted, a function keeps its keys and takes new
976    /// values. The evaluator closes a lazy value bottom-up with it
977    /// (ยง11.5 rule 4). For a `Fcn`, `data` is the keys then the values, as
978    /// in its view.
979    pub fn rebuild(&mut self, h: Handle, data: &[Handle]) -> Handle {
980        if !h.is_compound() {
981            return h;
982        }
983        let v = self.view(h);
984        let (kind, lo, n) = (v.kind, v.lo, v.data.len());
985        if data.len() != n {
986            self.lazy_misuse();
987            return h;
988        }
989        match kind {
990            Kind::Set => self.set_from(&mut data.to_vec()),
991            Kind::IntFcn => self.int_fcn(lo, data),
992            Kind::Fcn => {
993                let (keys, vals) = data.split_at(n / 2);
994                self.fcn_sorted(keys, vals)
995            }
996            _ => self.symbolic(kind, lo, data),
997        }
998    }
999
1000    /// `lo..hi`.
1001    pub fn interval(&mut self, lo: i64, hi: i64) -> Handle {
1002        let hi_h = Handle::int(hi).unwrap_or(Handle::EMPTY);
1003        self.symbolic(Kind::Interval, lo, &[hi_h])
1004    }
1005
1006    // ------------------------------------------------------------------
1007    // Normalization and materialization
1008    // ------------------------------------------------------------------
1009
1010    /// Whether a set is finite (symbolic sets over finite components).
1011    #[must_use]
1012    pub fn is_finite(&self, h: Handle) -> bool {
1013        if !h.is_compound() {
1014            return true;
1015        }
1016        let v = self.view(h);
1017        match v.kind {
1018            Kind::Set
1019            | Kind::IntFcn
1020            | Kind::Fcn
1021            | Kind::Lambda
1022            | Kind::BigInt
1023            | Kind::Interval
1024            | Kind::SetEnum => true,
1025            Kind::Nat | Kind::Int => false,
1026            Kind::SeqSet => self.view_is_empty_set(v.data[0]),
1027            Kind::Subset | Kind::FcnSet | Kind::Product => {
1028                v.data.iter().all(|&d| self.is_finite(d))
1029            }
1030            Kind::RecSet => v.data[v.data.len() / 2..]
1031                .iter()
1032                .all(|&d| self.is_finite(d)),
1033            Kind::Union => v.data.iter().all(|&d| self.is_finite(d)),
1034            Kind::SetPred => self.is_finite(v.data[0]),
1035        }
1036    }
1037
1038    fn view_is_empty_set(&self, h: Handle) -> bool {
1039        h.is_compound() && {
1040            let v = self.view(h);
1041            v.kind == Kind::Set && v.data.is_empty()
1042        }
1043    }
1044
1045    /// Normalizes a value: a finite symbolic set becomes an enumerated set.
1046    /// Other values are returned unchanged.
1047    ///
1048    /// # Errors
1049    /// The set is too large to materialize.
1050    pub fn norm(&mut self, h: Handle) -> Result<Handle, Error> {
1051        if !h.is_compound() {
1052            return Ok(h);
1053        }
1054        let v = self.view(h);
1055        if !v.kind.is_symbolic() || v.is_lazy() || !self.is_finite(h) {
1056            return Ok(h);
1057        }
1058        self.materialize(h)
1059    }
1060
1061    /// The elements of a finite set in canonical order, as a new enumerated
1062    /// set.
1063    ///
1064    /// # Errors
1065    /// An infinite or too-large set.
1066    pub fn materialize(&mut self, h: Handle) -> Result<Handle, Error> {
1067        self.materialize_fresh(h)
1068    }
1069
1070    /// As [`Heap::materialize`], but a persistent set's enumeration is
1071    /// interned and kept, so that it is built once per worker. Used only by
1072    /// membership under `-symbolic-member`: interning every enumeration
1073    /// would fill the store with values no state holds.
1074    ///
1075    /// # Errors
1076    /// As [`Heap::materialize`].
1077    pub fn materialize_cached(&mut self, h: Handle) -> Result<Handle, Error> {
1078        if h.is_persistent() && !self.speculative {
1079            if let Some(&m) = self.materialized.get(&h) {
1080                return Ok(m);
1081            }
1082            let m = self.materialize_fresh(h)?;
1083            let m = self.intern(m)?;
1084            self.materialized.insert(h, m);
1085            return Ok(m);
1086        }
1087        self.materialize_fresh(h)
1088    }
1089
1090    /// [`Heap::norm`] of a constant quantifier domain (a plan constant)
1091    /// that is enumerated once per evaluation of its quantifier. A
1092    /// persistent finite symbolic set of at most [`MAX_CONSTANT_DOMAIN`]
1093    /// elements (and [`MAX_CONSTANT_DOMAIN_WORDS`] new store words) is
1094    /// materialized once per heap and kept, when its
1095    /// enumeration is already in canonical persistent form (interning it
1096    /// exactly and canonically give the same handle; a read-only canonical
1097    /// form check runs first, so most rejected domains intern nothing). Its
1098    /// elements are then
1099    /// persistent, equal and identical to the ones a fresh enumeration
1100    /// builds. Any other set is normalized as [`Heap::norm`] does.
1101    ///
1102    /// # Errors
1103    /// As [`Heap::norm`].
1104    pub fn enumerate_constant(&mut self, h: Handle) -> Result<Handle, Error> {
1105        if !h.is_compound() || !h.is_persistent() || self.speculative {
1106            return self.norm(h);
1107        }
1108        let kept = self.constant_domains.get(&h).copied();
1109        if let Some(Some(m)) = kept {
1110            return Ok(m);
1111        }
1112        let v = self.view(h);
1113        if !v.kind.is_symbolic() || v.is_lazy() || !self.is_finite(h) {
1114            return Ok(h);
1115        }
1116        let m = self.materialize_fresh(h)?;
1117        if kept.is_some() {
1118            return Ok(m);
1119        }
1120        // Check, without interning, that the enumeration is small and
1121        // already in canonical form, so that a domain that will not be kept
1122        // leaves no interned copies behind in the store.
1123        let exact = if self.view(m).data.len() > MAX_CONSTANT_DOMAIN
1124            || !self.within_transient_words(m, MAX_CONSTANT_DOMAIN_WORDS)
1125            || !crate::compare::materialized(self, m, 0)?
1126        {
1127            None
1128        } else {
1129            match (self.intern_exact(m), self.intern(m)) {
1130                (Ok(exact), Ok(canonical)) if exact == canonical => Some(exact),
1131                _ => None,
1132            }
1133        };
1134        self.constant_domains.insert(h, exact);
1135        Ok(exact.unwrap_or(m))
1136    }
1137
1138    /// Whether the transient nodes reachable from `h` (counted once per
1139    /// path, so shared nodes count more than once) hold at most `budget`
1140    /// handle words, headers included. Persistent children are not counted:
1141    /// interning reuses them.
1142    fn within_transient_words(&self, h: Handle, budget: usize) -> bool {
1143        let mut left = budget;
1144        let mut stack = vec![h];
1145        while let Some(n) = stack.pop() {
1146            if !n.is_compound() || !n.is_transient() {
1147                continue;
1148            }
1149            let data = self.view(n).data;
1150            let Some(rest) = left.checked_sub(1 + data.len()) else {
1151                return false;
1152            };
1153            left = rest;
1154            stack.extend(data.iter().copied().filter(|d| d.is_transient()));
1155        }
1156        true
1157    }
1158
1159    fn materialize_fresh(&mut self, h: Handle) -> Result<Handle, Error> {
1160        let mut cur = self.cursor(h)?;
1161        let mut out = Vec::new();
1162        while let Some(e) = cur.next(self)? {
1163            if out.len() >= MAX_MATERIALIZE {
1164                return Err(Error::unsupported(
1165                    "materializing a set of more than 2^24 elements",
1166                ));
1167            }
1168            out.push(e);
1169        }
1170        Ok(self.set_sorted(&out))
1171    }
1172
1173    /// The elements of a finite set (normalized) as a vector.
1174    ///
1175    /// # Errors
1176    /// As [`Heap::materialize`].
1177    pub fn elements(&mut self, h: Handle) -> Result<Vec<Handle>, Error> {
1178        if h.is_compound() {
1179            let v = self.view(h);
1180            if v.kind == Kind::Set {
1181                return Ok(v.data.to_vec());
1182            }
1183        }
1184        let mut cur = self.cursor(h)?;
1185        let mut out = Vec::new();
1186        while let Some(e) = cur.next(self)? {
1187            if out.len() >= MAX_MATERIALIZE {
1188                return Err(Error::unsupported(
1189                    "enumerating a set of more than 2^24 elements",
1190                ));
1191            }
1192            out.push(e);
1193        }
1194        Ok(out)
1195    }
1196
1197    /// Read-only `Value.isEmpty` on concrete explicit/interval/product axes.
1198    /// Unknown axes decline in source order; later emptiness cannot waive them.
1199    /// Returns visited work for callers that also own a finite fuel budget.
1200    pub(crate) fn product_empty(&self, h: Handle) -> Result<(Option<bool>, usize), Error> {
1201        let mut work = 0;
1202        let result = self.concrete_product_empty(h, 0, &mut work)?;
1203        Ok((result, work))
1204    }
1205
1206    fn concrete_product_empty(
1207        &self,
1208        h: Handle,
1209        depth: u8,
1210        work: &mut usize,
1211    ) -> Result<Option<bool>, Error> {
1212        self.work_poll()?;
1213        *work = work.saturating_add(1);
1214        if depth >= 64 || !h.is_compound() {
1215            return Ok(None);
1216        }
1217        let view = self.view(h);
1218        match view.kind {
1219            Kind::Set | Kind::SetEnum => Ok(Some(view.data.is_empty())),
1220            Kind::Interval => Ok(view.data.first().and_then(|h| h.as_int()).and_then(|hi| {
1221                if hi < view.lo {
1222                    Some(true)
1223                } else {
1224                    hi.checked_sub(view.lo)
1225                        .and_then(|n| n.checked_add(1))
1226                        .filter(|&n| n <= i64::from(i32::MAX))
1227                        .map(|_| false)
1228                }
1229            })),
1230            Kind::Product => {
1231                for &axis in view.data {
1232                    match self.concrete_product_empty(axis, depth + 1, work)? {
1233                        Some(false) => {}
1234                        empty => return Ok(empty),
1235                    }
1236                }
1237                Ok(Some(false))
1238            }
1239            _ => Ok(None),
1240        }
1241    }
1242
1243    /// A cursor over a set's elements in canonical order.
1244    ///
1245    /// # Errors
1246    /// The value is not an enumerable set.
1247    pub fn cursor(&mut self, h: Handle) -> Result<Cursor, Error> {
1248        if !h.is_compound() {
1249            return Err(Error::eval(
1250                "attempted to enumerate a value that is not a set",
1251            ));
1252        }
1253        let v = self.view(h);
1254        let (kind, lo, data) = (v.kind, v.lo, v.data.to_vec());
1255        Ok(match kind {
1256            Kind::Set => Cursor::Array { set: h, i: 0 },
1257            Kind::Interval => Cursor::Range {
1258                cur: lo,
1259                hi: data[0].as_int().unwrap_or(lo - 1),
1260            },
1261            Kind::Product => {
1262                // SetOfTuplesValue.elements first checks source-order emptiness.
1263                // Do this at materialization, including compound components,
1264                // before normalizing any axis or requiring later axes be sets.
1265                if self.product_empty(h)?.0 == Some(true) {
1266                    return Ok(Cursor::Array {
1267                        set: self.empty_set(),
1268                        i: 0,
1269                    });
1270                }
1271                let comps = data
1272                    .iter()
1273                    .map(|&s| {
1274                        let s = self.norm(s)?;
1275                        self.elements(s)
1276                    })
1277                    .collect::<Result<Vec<_>, Error>>()?;
1278                Cursor::odometer(Shape::Tuple, comps)
1279            }
1280            Kind::FcnSet => {
1281                let dom = self.norm(data[0])?;
1282                let keys = self.elements(dom)?;
1283                let rng = self.norm(data[1])?;
1284                let r = self.elements(rng)?;
1285                let comps = vec![r; keys.len()];
1286                Cursor::odometer(Shape::Fcn(keys), comps)
1287            }
1288            Kind::RecSet => {
1289                let n = data.len() / 2;
1290                let names = data[..n].to_vec();
1291                let comps = data[n..]
1292                    .iter()
1293                    .map(|&s| {
1294                        let s = self.norm(s)?;
1295                        self.elements(s)
1296                    })
1297                    .collect::<Result<Vec<_>, Error>>()?;
1298                Cursor::odometer(Shape::Fcn(names), comps)
1299            }
1300            Kind::Subset => {
1301                let base = self.norm(data[0])?;
1302                let elems = self.elements(base)?;
1303                if elems.len() > 24 {
1304                    return Err(Error::unsupported(
1305                        "enumerating SUBSET of a set of more than 24 elements",
1306                    ));
1307                }
1308                Cursor::Subset {
1309                    elems,
1310                    k: 0,
1311                    combo: Vec::new(),
1312                    started: false,
1313                }
1314            }
1315            Kind::SetEnum => {
1316                let mut v = data;
1317                let set = self.set_from(&mut v);
1318                Cursor::Array { set, i: 0 }
1319            }
1320            Kind::Union => {
1321                let (a, b) = (self.norm(data[0])?, self.norm(data[1])?);
1322                let mut v = self.elements(a)?;
1323                v.extend(self.elements(b)?);
1324                let set = self.set_from(&mut v);
1325                Cursor::Array { set, i: 0 }
1326            }
1327            Kind::Nat | Kind::Int | Kind::SeqSet => {
1328                return Err(Error::eval("attempted to enumerate an infinite set"));
1329            }
1330            Kind::IntFcn | Kind::Fcn | Kind::Lambda => {
1331                return Err(Error::eval("attempted to enumerate a function as a set"));
1332            }
1333            Kind::BigInt => {
1334                return Err(Error::eval(
1335                    "attempted to enumerate a value that is not a set",
1336                ));
1337            }
1338            Kind::SetPred => {
1339                return Err(Error::internal(
1340                    "a set predicate reached the heap's enumeration; the evaluator closes it",
1341                ));
1342            }
1343        })
1344    }
1345
1346    /// The number of elements of a finite set.
1347    ///
1348    /// # Errors
1349    /// Not a finite set.
1350    pub fn cardinality(&mut self, h: Handle) -> Result<u64, Error> {
1351        if !h.is_compound() {
1352            return Err(Error::eval("Cardinality of a value that is not a set"));
1353        }
1354        let v = self.view(h);
1355        if v.is_lazy() {
1356            return Err(Error::internal(
1357                "Cardinality of an unclosed lazy value; the evaluator closes it",
1358            ));
1359        }
1360        match v.kind {
1361            Kind::Set => Ok(v.data.len() as u64),
1362            #[allow(clippy::cast_sign_loss, reason = "checked non-negative")]
1363            Kind::Interval => {
1364                let hi = v.data[0].as_int().unwrap_or(v.lo - 1);
1365                Ok(if hi < v.lo { 0 } else { (hi - v.lo + 1) as u64 })
1366            }
1367            _ => {
1368                let m = self.norm(h)?;
1369                if m == h {
1370                    return Err(Error::eval("Cardinality of an infinite set"));
1371                }
1372                self.cardinality(m)
1373            }
1374        }
1375    }
1376
1377    // ------------------------------------------------------------------
1378    // Interning
1379    // ------------------------------------------------------------------
1380
1381    /// Selects speculative candidate evaluation, returning the previous mode.
1382    ///
1383    /// In this mode evaluator memo sites and materialization caches do not
1384    /// promote results. Explicit `intern` calls retain their persistent contract.
1385    pub fn set_speculative(&mut self, enabled: bool) -> bool {
1386        std::mem::replace(&mut self.speculative, enabled)
1387    }
1388
1389    /// Whether candidate evaluation is keeping identities local to this Arena.
1390    #[must_use]
1391    pub const fn is_speculative(&self) -> bool {
1392        self.speculative
1393    }
1394
1395    /// Interns for an ordinary run, or closes locally during candidate expansion.
1396    ///
1397    /// # Errors
1398    /// As [`Self::intern`] or [`Self::close_identity_local`].
1399    pub fn state_identity(&mut self, h: Handle) -> Result<Handle, Error> {
1400        if self.speculative {
1401            self.close_identity_local(h)
1402        } else {
1403            self.intern(h)
1404        }
1405    }
1406
1407    /// Closes a mathematical identity in the local Arena without Store promotion.
1408    ///
1409    /// This performs the same demanded normalization as [`Self::intern`], but
1410    /// returns values valid only until the owning Arena is rolled back or reset.
1411    /// No persistent-handle certificate or interning cache is populated.
1412    ///
1413    /// # Errors
1414    /// An unclosed lazy value, failed normalization, or a too-deep candidate.
1415    pub fn close_identity_local(&mut self, h: Handle) -> Result<Handle, Error> {
1416        let h = self.close_local(h, 0, &mut LocalClose::default())?;
1417        crate::compare::require_materialized(self, &[h])?;
1418        Ok(h)
1419    }
1420
1421    /// Closes related roots with one bounded, operation-local sharing map.
1422    ///
1423    /// No result or source mapping survives this call. Original values retain
1424    /// their symbolic representations; returned roots are Arena-local.
1425    ///
1426    /// # Errors
1427    /// As [`Self::close_identity_local`], or root-row workspace exhaustion.
1428    pub fn close_identity_row_local(&mut self, roots: &[Handle]) -> Result<Vec<Handle>, Error> {
1429        if std::mem::size_of_val(roots) > MAX_LOCAL_CLOSE_SCRATCH_BYTES {
1430            return Err(Error::unsupported(
1431                "candidate identity root-row workspace bound",
1432            ));
1433        }
1434        let mut out = Vec::new();
1435        out.try_reserve_exact(roots.len())
1436            .map_err(|_| Error::unsupported("candidate identity root-row allocation"))?;
1437        let mut close = LocalClose::default();
1438        for &root in roots {
1439            let root = self.close_local(root, 0, &mut close)?;
1440            crate::compare::require_materialized(self, &[root])?;
1441            out.push(root);
1442        }
1443        Ok(out)
1444    }
1445
1446    fn close_local(
1447        &mut self,
1448        source: Handle,
1449        depth: usize,
1450        close: &mut LocalClose,
1451    ) -> Result<Handle, Error> {
1452        let h = source;
1453        if !h.is_compound() {
1454            return Ok(h);
1455        }
1456        if let Some(&closed) = close.visited.get(&h) {
1457            return Ok(closed);
1458        }
1459        if depth >= 128 {
1460            return Err(Error::unsupported("candidate identity nesting exceeds 128"));
1461        }
1462        self.work_poll()?;
1463        if let Some(&closed) = close.visited.get(&h) {
1464            close.remember(source, closed)?;
1465            return Ok(closed);
1466        }
1467        let view = self.view(h);
1468        if view.is_lazy() {
1469            return Err(Error::internal("closing an unclosed lazy candidate value"));
1470        }
1471        if view.kind.is_symbolic() && self.is_finite(h) {
1472            let materialized = self.materialize(h)?;
1473            let closed = self.close_local(materialized, depth + 1, close)?;
1474            close.remember(source, closed)?;
1475            close.remember(h, closed)?;
1476            return Ok(closed);
1477        }
1478        if view.kind.is_symbolic() {
1479            return Err(Error::unsupported(
1480                "mathematical identity of a symbolic state value",
1481            ));
1482        }
1483        if view.kind == Kind::Fcn {
1484            // Closing a symbolic key could change its order or collapse two
1485            // keys. A sorted function cannot silently inherit either change.
1486            crate::compare::require_materialized(self, &view.data[..view.data.len() / 2])?;
1487        }
1488        // Constants can retain symbolic descendants even without view flags.
1489        if h.is_persistent()
1490            && view.flags & flags::VIEW == 0
1491            && crate::compare::materialized(self, h, 0)?
1492        {
1493            return Ok(h);
1494        }
1495        let lo = if view.kind == Kind::Set { 0 } else { view.lo };
1496        let bytes = std::mem::size_of_val(view.data);
1497        if bytes > MAX_LOCAL_CLOSE_SCRATCH_BYTES.saturating_sub(close.scratch) {
1498            return Err(Error::unsupported(
1499                "candidate identity closure child workspace bound",
1500            ));
1501        }
1502        let mut children = Vec::new();
1503        children
1504            .try_reserve_exact(view.data.len())
1505            .map_err(|_| Error::unsupported("candidate identity closure child allocation"))?;
1506        let bytes = children.capacity() * size_of::<Handle>();
1507        if bytes > MAX_LOCAL_CLOSE_SCRATCH_BYTES.saturating_sub(close.scratch) {
1508            return Err(Error::unsupported(
1509                "candidate identity closure child workspace bound",
1510            ));
1511        }
1512        close.scratch += bytes;
1513        for chunk in view.data.chunks(64) {
1514            self.work_poll()?;
1515            children.extend_from_slice(chunk);
1516        }
1517        for child in &mut children {
1518            *child = self.close_local(*child, depth + 1, close)?;
1519        }
1520        let unchanged = self.view(h).data == children;
1521        let closed =
1522            if unchanged && self.view(h).flags & !flags::CONCRETE == 0 && self.view(h).lo == lo {
1523                h
1524            } else if unchanged && h.is_transient() {
1525                self.arena
1526                    .project(h, 0, lo)
1527                    .ok_or_else(|| Error::internal("candidate identity projection owner"))?
1528            } else {
1529                // Materializing a child changes its value hash and can coalesce
1530                // equal set members. Recompute the parent's structure and hash.
1531                self.rebuild(h, &children)
1532            };
1533        close.scratch -= bytes;
1534        close.remember(source, closed)?;
1535        close.remember(h, closed)?;
1536        Ok(closed)
1537    }
1538
1539    /// Interns a value into the persistent store, deep-closing it: children
1540    /// first, finite symbolic sets materialized.
1541    ///
1542    /// # Errors
1543    /// A set too large to materialize.
1544    pub fn intern(&mut self, h: Handle) -> Result<Handle, Error> {
1545        if crate::compare::materialized(self, h, 0)? {
1546            self.intern_materialized(h)
1547        } else {
1548            let h = self.close_identity_local(h)?;
1549            self.intern_materialized(h)
1550        }
1551    }
1552
1553    fn intern_materialized(&mut self, h: Handle) -> Result<Handle, Error> {
1554        match h.tag() {
1555            Tag::Transient => {}
1556            Tag::Persistent => {
1557                if h.is_lazy_persistent() {
1558                    let v = self.view(h);
1559                    if v.is_lazy() {
1560                        return Err(Error::internal("interning an unclosed lazy value"));
1561                    }
1562                    if !v.kind.is_symbolic() {
1563                        // A record literal's view (`intern_view`): its identity
1564                        // has no view bit.
1565                        let (kind, lo, hash, sum) = (
1566                            v.kind,
1567                            if v.kind == Kind::Set { 0 } else { v.lo },
1568                            v.hash,
1569                            v.sum,
1570                        );
1571                        let mut data = v.data.to_vec();
1572                        for d in &mut data {
1573                            *d = self.intern_materialized(*d)?;
1574                        }
1575                        let concrete = self.concrete_identity(kind, &data);
1576                        return Ok(self.store.intern(
1577                            &mut self.cache,
1578                            kind,
1579                            concrete,
1580                            lo,
1581                            hash,
1582                            sum,
1583                            &data,
1584                        ));
1585                    }
1586                }
1587                let k = self.view(h).kind;
1588                if k.is_symbolic() && self.is_finite(h) {
1589                    let m = self.materialize(h)?;
1590                    return self.intern_materialized(m);
1591                }
1592                return Ok(h);
1593            }
1594            _ => return Ok(h),
1595        }
1596        let Some(idx) = self.arena.index(h) else {
1597            self.arena.mark_stale();
1598            return Ok(Handle::EMPTY);
1599        };
1600        let done = self.arena.interned[idx];
1601        if !done.is_empty() {
1602            return Ok(done);
1603        }
1604        let v = self.view(h);
1605        if v.is_lazy() {
1606            return Err(Error::internal(
1607                "interning an unclosed lazy value; the evaluator closes it first",
1608            ));
1609        }
1610        if v.kind.is_symbolic() && self.is_finite(h) {
1611            let m = self.materialize(h)?;
1612            let p = self.intern_materialized(m)?;
1613            self.arena.interned[idx] = p;
1614            return Ok(p);
1615        }
1616        let (kind, lo, hash, sum) = (
1617            v.kind,
1618            if v.kind == Kind::Set { 0 } else { v.lo },
1619            v.hash,
1620            v.sum,
1621        );
1622        let mut data = v.data.to_vec();
1623        for d in &mut data {
1624            if d.is_compound() {
1625                *d = self.intern_materialized(*d)?;
1626            }
1627        }
1628        let concrete = self.concrete_identity(kind, &data);
1629        let p = self
1630            .store
1631            .intern(&mut self.cache, kind, concrete, lo, hash, sum, &data);
1632        self.arena.interned[idx] = p;
1633        Ok(p)
1634    }
1635
1636    /// [`flags::CONCRETE`] for an eager canonical identity node.
1637    fn concrete_identity(&self, kind: Kind, data: &[Handle]) -> u8 {
1638        if matches!(kind, Kind::Set | Kind::IntFcn | Kind::Fcn) {
1639            self.concrete_bit(data)
1640        } else {
1641            0
1642        }
1643    }
1644
1645    /// Interns a constant, preserving available function literal classes
1646    /// recursively and keeping symbolic sets symbolic. This is a value used
1647    /// for evaluation, not its canonical identity (`0121` in the ADRs).
1648    /// A lazy constant (for example `[x \in Nat |-> x + 1]`) stays lazy: it
1649    /// is interned structurally, never compared by handle (ยง11.1).
1650    ///
1651    /// # Errors
1652    /// As [`Heap::intern`].
1653    pub fn intern_const(&mut self, h: Handle) -> Result<Handle, Error> {
1654        if !h.is_transient() {
1655            return Ok(h);
1656        }
1657        self.intern_structural(h)
1658    }
1659
1660    /// Interns a node as it is, view bits included, with its components
1661    /// interned as constants: apart from identities (class 3) when it is
1662    /// lazy or a view.
1663    fn intern_structural(&mut self, h: Handle) -> Result<Handle, Error> {
1664        let v = self.view(h);
1665        let (kind, mut fl, lo, hash, sum) = (v.kind, v.flags, v.lo, v.hash, v.sum);
1666        let mut data = v.data.to_vec();
1667        for d in &mut data {
1668            *d = self.intern_const(*d)?;
1669            if d.is_compound() && self.view(*d).flags & flags::VIEW != 0 {
1670                fl |= flags::NESTED_VIEW;
1671            }
1672        }
1673        Ok(self
1674            .store
1675            .intern(&mut self.cache, kind, fl, lo, hash, sum, &data))
1676    }
1677
1678    /// Interns a closed value exactly as it is: every node keeps its kind
1679    /// and view bits (a symbolic set stays symbolic, a record literal stays
1680    /// one), so the persistent handle reads like `h` everywhere, and two
1681    /// handles it returns are equal exactly when the representations are.
1682    /// Step-predicate memo sites use it for their keys and results;
1683    /// graph capture uses it to retain original
1684    /// target representations independently of canonical state identities.
1685    ///
1686    /// # Errors
1687    /// `h` is lazy (holds a closure only the evaluator can force).
1688    pub fn intern_exact(&mut self, h: Handle) -> Result<Handle, Error> {
1689        if !h.is_transient() {
1690            return Ok(h);
1691        }
1692        let v = self.view(h);
1693        if v.is_lazy() {
1694            return Err(Error::internal("interning an unclosed lazy value"));
1695        }
1696        let (kind, mut fl, lo, hash, sum) = (v.kind, v.flags, v.lo, v.hash, v.sum);
1697        let mut data = v.data.to_vec();
1698        for d in &mut data {
1699            if d.is_transient() {
1700                *d = self.intern_exact(*d)?;
1701            }
1702            if d.is_compound() && self.view(*d).flags & flags::VIEW != 0 {
1703                fl |= flags::NESTED_VIEW;
1704            }
1705        }
1706        Ok(self
1707            .store
1708            .intern(&mut self.cache, kind, fl, lo, hash, sum, &data))
1709    }
1710
1711    /// Interns a state value with its lazy view (ยง8): the identity handle
1712    /// (as [`Heap::intern`]) and, when the value is a symbolic set or carries
1713    /// a view bit ([`flags::VIEW`]) at the top level, that representation
1714    /// interned apart from identities; otherwise [`Handle::EMPTY`]. Nested
1715    /// view bits are not kept. The engine keeps the view in a side table
1716    /// only where the plan asks for it; hashing and equality use the identity.
1717    ///
1718    /// # Errors
1719    /// As [`Heap::intern`].
1720    pub fn intern_view(&mut self, h: Handle) -> Result<(Handle, Handle), Error> {
1721        let view = if !h.is_compound() {
1722            Handle::EMPTY
1723        } else if self.view(h).kind.is_symbolic() {
1724            self.intern_const(h)?
1725        } else if self.view(h).flags & flags::VIEW != 0 {
1726            if h.is_transient() {
1727                self.intern_structural(h)?
1728            } else {
1729                h
1730            }
1731        } else {
1732            Handle::EMPTY
1733        };
1734        Ok((self.intern(h)?, view))
1735    }
1736
1737    pub(crate) fn set_work_control(&mut self, control: Option<Arc<dyn crate::eval::WorkControl>>) {
1738        self.work_control = control;
1739    }
1740
1741    pub(crate) fn mark_work_interrupted(&self) {
1742        self.work_interrupted.set(true);
1743    }
1744
1745    /// Whether this machine reached its caller-owned cooperative stop.
1746    #[must_use]
1747    pub fn work_interrupted(&self) -> bool {
1748        self.work_interrupted.get()
1749    }
1750
1751    pub(crate) fn work_poll(&self) -> Result<(), Error> {
1752        let steps = self.work_steps.get();
1753        self.work_steps.set(steps.wrapping_add(1));
1754        if steps.trailing_zeros() >= 6 && self.work_control.as_ref().is_some_and(|c| !c.proceed()) {
1755            self.mark_work_interrupted();
1756            return Err(Error::stop());
1757        }
1758        Ok(())
1759    }
1760
1761    /// The string id of `text`.
1762    ///
1763    /// # Errors
1764    /// The string table is full, or the text is new while
1765    /// [`Heap::set_existing_strings_only`] holds (unsupported).
1766    pub fn string(&self, text: &str) -> Result<Handle, Error> {
1767        if self.strings == StringMode::ExistingOnly {
1768            return self
1769                .store
1770                .strings()
1771                .lookup(text)
1772                .map(Handle::string)
1773                .ok_or_else(|| {
1774                    Error::unsupported(
1775                        "a string this optional evaluation would add to the shared string table",
1776                    )
1777                });
1778        }
1779        Ok(Handle::string(self.store.strings().intern(text)?))
1780    }
1781
1782    /// Makes [`Heap::string`] refuse any text the shared table does not
1783    /// already hold, returning the previous mode. An isolated optional
1784    /// machine uses it so that skipping its work elsewhere cannot change
1785    /// later string tokens (string order under `--compat=tlc`).
1786    ///
1787    /// ```
1788    /// # fn example(heap: &mut dive_core::Heap) {
1789    /// let previous = heap.set_existing_strings_only(true);
1790    /// heap.set_existing_strings_only(previous);
1791    /// # }
1792    /// ```
1793    pub fn set_existing_strings_only(&mut self, enabled: bool) -> bool {
1794        let mode = if enabled {
1795            StringMode::ExistingOnly
1796        } else {
1797            StringMode::Intern
1798        };
1799        std::mem::replace(&mut self.strings, mode) == StringMode::ExistingOnly
1800    }
1801}
1802
1803/// Whether [`Heap::string`] may add a text to the shared string table.
1804#[derive(Clone, Copy, Debug, PartialEq, Eq)]
1805enum StringMode {
1806    /// Assign an id to a new text.
1807    Intern,
1808    /// Refuse a text the table lacks.
1809    ExistingOnly,
1810}
1811
1812/// The key of entry `i` of a function view.
1813pub(crate) fn fcn_key(v: &View<'_>, i: usize) -> Handle {
1814    match v.kind {
1815        #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
1816        Kind::IntFcn => Handle::int(v.lo + i as i64).unwrap_or(Handle::EMPTY),
1817        _ => v.data[i],
1818    }
1819}
1820
1821/// The lower bound if `keys` are the consecutive integers `lo, lo+1, ...`.
1822fn contiguous_ints(keys: &[Handle]) -> Option<i64> {
1823    // The empty function is the empty tuple: one canonical form.
1824    let Some(first) = keys.first() else {
1825        return Some(1);
1826    };
1827    let lo = first.as_int()?;
1828    for (i, k) in keys.iter().enumerate() {
1829        #[allow(clippy::cast_possible_wrap, reason = "domains fit in i64")]
1830        if k.as_int()? != lo + i as i64 {
1831            return None;
1832        }
1833    }
1834    Some(lo)
1835}
1836
1837/// The kind of value an odometer builds.
1838#[derive(Clone, Debug)]
1839pub enum Shape {
1840    /// A tuple of the components.
1841    Tuple,
1842    /// A function from these sorted keys to the components.
1843    Fcn(Vec<Handle>),
1844}
1845
1846/// A cursor over a set's elements in canonical order.
1847#[derive(Clone, Debug)]
1848pub enum Cursor {
1849    /// An enumerated set.
1850    Array {
1851        /// The set.
1852        set: Handle,
1853        /// The next index.
1854        i: usize,
1855    },
1856    /// An interval.
1857    Range {
1858        /// The next element.
1859        cur: i64,
1860        /// The last element.
1861        hi: i64,
1862    },
1863    /// Functions, records or tuples over component sets, the last component
1864    /// fastest (canonical order).
1865    Odometer {
1866        /// What each step builds.
1867        shape: Shape,
1868        /// The component element lists.
1869        comps: Vec<Vec<Handle>>,
1870        /// The current indices.
1871        idx: Vec<usize>,
1872        /// Exhausted.
1873        done: bool,
1874    },
1875    /// `SUBSET S`: by size, then lexicographically.
1876    Subset {
1877        /// The base elements.
1878        elems: Vec<Handle>,
1879        /// The current size.
1880        k: usize,
1881        /// The current combination.
1882        combo: Vec<usize>,
1883        /// Whether the first combination of size `k` was produced.
1884        started: bool,
1885    },
1886}
1887
1888impl Cursor {
1889    fn odometer(shape: Shape, comps: Vec<Vec<Handle>>) -> Self {
1890        let done = comps.iter().any(Vec::is_empty);
1891        let n = comps.len();
1892        Self::Odometer {
1893            shape,
1894            comps,
1895            idx: vec![0; n],
1896            done,
1897        }
1898    }
1899
1900    /// The next element.
1901    ///
1902    /// # Errors
1903    /// A stale set handle.
1904    pub fn next(&mut self, heap: &mut Heap) -> Result<Option<Handle>, Error> {
1905        match self {
1906            Self::Array { set, i } => {
1907                let v = heap.view(*set);
1908                let r = v.data.get(*i).copied();
1909                *i += 1;
1910                Ok(r)
1911            }
1912            Self::Range { cur, hi } => {
1913                if *cur > *hi {
1914                    return Ok(None);
1915                }
1916                let r = Handle::int(*cur);
1917                *cur += 1;
1918                r.map(Some)
1919                    .ok_or_else(|| Error::unsupported("integer outside the 61-bit range"))
1920            }
1921            Self::Odometer {
1922                shape,
1923                comps,
1924                idx,
1925                done,
1926            } => {
1927                if *done {
1928                    return Ok(None);
1929                }
1930                let vals: Vec<Handle> = idx.iter().zip(comps.iter()).map(|(&i, c)| c[i]).collect();
1931                let out = match shape {
1932                    Shape::Tuple => heap.tuple(&vals),
1933                    Shape::Fcn(keys) => heap.fcn_sorted(keys, &vals),
1934                };
1935                // Advance, last position fastest.
1936                let mut p = idx.len();
1937                loop {
1938                    if p == 0 {
1939                        *done = true;
1940                        break;
1941                    }
1942                    p -= 1;
1943                    idx[p] += 1;
1944                    if idx[p] < comps[p].len() {
1945                        break;
1946                    }
1947                    idx[p] = 0;
1948                }
1949                Ok(Some(out))
1950            }
1951            Self::Subset {
1952                elems,
1953                k,
1954                combo,
1955                started,
1956            } => {
1957                let n = elems.len();
1958                if *started {
1959                    // Next combination of size k, lexicographically.
1960                    let mut i = *k;
1961                    let mut advanced = false;
1962                    while i > 0 {
1963                        i -= 1;
1964                        if combo[i] < n - *k + i {
1965                            combo[i] += 1;
1966                            for j in i + 1..*k {
1967                                combo[j] = combo[j - 1] + 1;
1968                            }
1969                            advanced = true;
1970                            break;
1971                        }
1972                    }
1973                    if !advanced {
1974                        *k += 1;
1975                        if *k > n {
1976                            return Ok(None);
1977                        }
1978                        *combo = (0..*k).collect();
1979                    }
1980                } else {
1981                    *started = true;
1982                    *combo = Vec::new();
1983                }
1984                let mut sub: Vec<Handle> = combo.iter().map(|&i| elems[i]).collect();
1985                Ok(Some(heap.set_from(&mut sub)))
1986            }
1987        }
1988    }
1989}
1990
1991#[cfg(test)]
1992impl Heap {
1993    /// A persistent copy of a transient node without [`flags::CONCRETE`], as
1994    /// snapshot restore and owned exchange produce it.
1995    pub(crate) fn unmarked_copy(&mut self, t: Handle) -> Handle {
1996        let v = self.view(t);
1997        let (kind, fl, lo, hash, sum) = (v.kind, v.flags & !flags::CONCRETE, v.lo, v.hash, v.sum);
1998        let data = v.data.to_vec();
1999        self.store
2000            .intern(&mut self.cache, kind, fl, lo, hash, sum, &data)
2001    }
2002}
2003
2004#[cfg(test)]
2005#[allow(clippy::many_single_char_names, reason = "short value names in tests")]
2006mod tests {
2007    use super::*;
2008
2009    fn int(v: i64) -> Handle {
2010        Handle::int(v).unwrap_or(Handle::EMPTY)
2011    }
2012
2013    fn heap(full: bool) -> Heap {
2014        Heap::new(Arc::new(Store::default()), false, full)
2015    }
2016
2017    #[test]
2018    fn mathematical_state_identity_refuses_nested_symbolic_values() {
2019        let mut h = heap(false);
2020        let empty = h.empty_set();
2021        let naturals = h.symbolic(Kind::Nat, 0, &[]);
2022        let product = h.symbolic(Kind::Product, 0, &[empty, naturals]);
2023        let range = h.interval(1, 1);
2024        let sequence = h.symbolic(Kind::SeqSet, 0, &[range]);
2025        for symbolic in [sequence, product] {
2026            let tuple = h.tuple(&[symbolic]);
2027            let function_key = h.fcn_sorted(&[symbolic], &[int(1)]);
2028            let function_value = h.fcn_sorted(&[int(0)], &[symbolic]);
2029            let singleton = h.set_sorted(&[tuple]);
2030            for value in [symbolic, tuple, function_key, function_value, singleton] {
2031                let before = h.store().stats().nodes;
2032                assert!(
2033                    matches!(h.intern(value), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2034                );
2035                assert!(
2036                    matches!(h.close_identity_local(value), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2037                );
2038                assert!(
2039                    matches!(h.close_identity_row_local(&[value]), Err(error) if error.kind() == crate::ErrorKind::Unsupported)
2040                );
2041                assert_eq!(h.store().stats().nodes, before);
2042            }
2043        }
2044    }
2045
2046    #[test]
2047    fn product_materialization_checks_empty_axes_before_normalization() -> Result<(), Error> {
2048        for semantics in [crate::Semantics::default(), crate::Semantics::tlc()] {
2049            let mut h = Heap::new(
2050                Arc::new(Store::with_semantics(true, semantics)),
2051                false,
2052                false,
2053            );
2054            let empty_interval = h.interval(3, 2);
2055            let mixed = h.set_from(&mut vec![int(0), Handle::TRUE]);
2056            let product = h.symbolic(Kind::Product, 0, &[empty_interval, mixed, int(0)]);
2057            let nested = h.symbolic(Kind::Product, 0, &[product, mixed]);
2058            for value in [product, nested] {
2059                let materialized = h.materialize(value)?;
2060                assert_eq!(h.view(materialized).kind, Kind::Set);
2061                assert_eq!(h.view(materialized).data, []);
2062            }
2063            // An invalid scalar axis still refuses when it precedes emptiness.
2064            let earlier_scalar = h.symbolic(Kind::Product, 0, &[int(0), empty_interval]);
2065            assert!(h.materialize(earlier_scalar).is_err());
2066            let one = h.set_from(&mut vec![int(0)]);
2067            let demanded = h.symbolic(Kind::Product, 0, &[one, mixed]);
2068            let materialized = h.materialize(demanded)?;
2069            assert_eq!(h.view(materialized).data.len(), 2);
2070            assert!(!h.poisoned());
2071        }
2072        Ok(())
2073    }
2074
2075    /// The heap's copy of the string texts orders strings as the table
2076    /// does, also for strings interned after the copy was first made.
2077    #[test]
2078    fn string_comparison_follows_the_table_as_it_grows() {
2079        let h = heap(false);
2080        let t = h.store().strings();
2081        let id = |s: &str| t.intern(s).unwrap_or(u32::MAX);
2082        let (b, a) = (id("b"), id("a"));
2083        assert_eq!(h.str_cmp(b, a), Ordering::Greater);
2084        let (c, aa) = (id("c"), id("aa"));
2085        for (x, y) in [(a, b), (b, c), (aa, a), (aa, b), (c, aa), (c, c)] {
2086            assert_eq!(h.str_cmp(x, y), t.cmp(x, y), "{x} {y}");
2087        }
2088    }
2089
2090    /// Strings the table has not ranked yet compare by text, against ranked
2091    /// and unranked strings alike, as the table orders them.
2092    #[test]
2093    fn string_comparison_covers_strings_past_the_ranks() {
2094        let h = heap(false);
2095        let t = h.store().strings();
2096        let id = |s: &str| t.intern(s).unwrap_or(u32::MAX);
2097        let ranked: Vec<u32> = (0..1500).map(|n| id(&format!("k{n:04}"))).collect();
2098        assert_eq!(h.str_cmp(ranked[1], ranked[0]), Ordering::Greater);
2099        let late = [id("k0500x"), id("a"), id("zz")];
2100        assert!(t.ranks().len() < t.len(), "the late strings stay unranked");
2101        for &x in late.iter().chain(&ranked[495..505]) {
2102            for &y in late.iter().chain(&ranked[495..505]) {
2103                assert_eq!(h.str_cmp(x, y), t.cmp(x, y), "{x} {y}");
2104            }
2105        }
2106    }
2107
2108    #[test]
2109    fn model_types_follow_utf16_names_across_append_and_reset() {
2110        use crate::strings::StringOrder;
2111
2112        for order in [StringOrder::Text, StringOrder::Token] {
2113            let mut h = Heap::new(
2114                Arc::new(Store::with_string_order(true, order)),
2115                false,
2116                false,
2117            );
2118            for names in [
2119                ["", "a", "A_", "A_x", "_x", "n1", "รฉ_x", "๐Ÿ˜€_x"],
2120                ["รฉ_๐Ÿ˜€", "๐€€_x", "A_รฉ", "A_๐Ÿ˜€", "__x", "_", "๐Ÿ˜€", "x_y"],
2121            ] {
2122                for name in names {
2123                    let id = h.store.strings().intern(name).unwrap_or(u32::MAX);
2124                    let units: Vec<_> = name.encode_utf16().collect();
2125                    let expected = if units.len() > 2 && units[1] == u16::from(b'_') {
2126                        Some(units[0])
2127                    } else {
2128                        None
2129                    };
2130                    for _ in 0..2 {
2131                        assert_eq!(h.model_type(id), expected, "{order:?} {name:?}");
2132                        assert_eq!(crate::compare::mv_type(&h, Handle::model(id)), expected);
2133                        h.reset();
2134                    }
2135                }
2136            }
2137            assert_eq!(h.model_type(u32::MAX), None);
2138            assert_eq!(crate::compare::mv_type(&h, Handle::TRUE), None);
2139            h.store.strings().seal();
2140            assert_eq!(h.model_type(3), Some(u16::from(b'A')));
2141        }
2142    }
2143
2144    #[test]
2145    fn incremental_except_hash_equals_the_full_hash() {
2146        for full in [false, true] {
2147            let mut h = heap(full);
2148            let f = h.int_fcn(1, &[int(1), int(2), int(3)]);
2149            let inner = h.set_from(&mut vec![int(7), int(5)]);
2150            let g = h.fcn_with(f, 1, inner);
2151            let direct = h.int_fcn(1, &[int(1), inner, int(3)]);
2152            assert!(h.eq(g, direct));
2153            assert_eq!(h.hash(g), h.hash(direct));
2154            assert_eq!(h.hash(g), h.deep_hash(direct));
2155            // Records: string keys, through `fcn_with` twice.
2156            let (a, b) = (
2157                h.string("a").unwrap_or(Handle::EMPTY),
2158                h.string("b").unwrap_or(Handle::EMPTY),
2159            );
2160            let r = h.fcn_from_pairs(&mut [(b, int(1)), (a, int(2))]);
2161            let r2 = h.fcn_with(r, 0, int(9));
2162            let r3 = h.fcn_with(r2, 0, int(2));
2163            assert_eq!(h.hash(r3), h.deep_hash(r));
2164            assert!(h.eq(r3, r));
2165        }
2166    }
2167
2168    #[test]
2169    fn interning_is_hash_consed_and_preserves_hashes() {
2170        let mut h = heap(false);
2171        let a = h.set_from(&mut vec![int(3), int(1), int(2)]);
2172        let b = h.interval(1, 3);
2173        let b = h.norm(b).unwrap_or(Handle::EMPTY);
2174        assert!(h.eq(a, b));
2175        let pa = h.intern(a).unwrap_or(Handle::EMPTY);
2176        let pb = h.intern(b).unwrap_or(Handle::EMPTY);
2177        assert_eq!(pa, pb);
2178        assert_eq!(h.hash(pa), h.hash(a));
2179        let t = h.tuple(&[a, int(4)]);
2180        let pt = h.intern(t).unwrap_or(Handle::EMPTY);
2181        h.reset();
2182        // After the epoch ends the persistent copy still resolves.
2183        let v = h.view(pt);
2184        assert_eq!(v.data.first().copied(), Some(pa));
2185        assert!(!h.poisoned());
2186        let st = h.store().stats();
2187        assert!(st.hits >= 1, "{st:?}");
2188    }
2189
2190    #[test]
2191    fn stale_transient_handles_poison_the_heap() {
2192        let mut h = heap(false);
2193        let a = h.set_from(&mut vec![int(1)]);
2194        h.reset();
2195        let _ = h.view(a);
2196        assert!(h.poisoned());
2197    }
2198
2199    #[test]
2200    fn rollback_frees_candidates_and_stale_reads_poison() {
2201        let mut h = heap(false);
2202        let kept = h.set_from(&mut vec![int(1)]);
2203        for i in 0..1000 {
2204            let m = h.mark();
2205            let c = h.tuple(&[int(i), kept]);
2206            if i % 10 == 0 {
2207                continue;
2208            }
2209            assert!(h.eq(h.view(c).data[1], kept));
2210            h.rollback(m);
2211        }
2212        // The 100 kept candidates and the set remain; the rest were freed.
2213        assert_eq!(h.arena().len(), 101);
2214        assert!(!h.poisoned());
2215        let m = h.mark();
2216        let gone = h.tuple(&[int(7)]);
2217        h.rollback(m);
2218        let _ = h.tuple(&[int(8)]);
2219        let _ = h.view(gone);
2220        assert!(h.poisoned(), "a handle freed by rollback must not resolve");
2221    }
2222
2223    #[test]
2224    fn lazy_values_carry_their_closure_and_propagate() {
2225        let mut h = heap(false);
2226        let dom = h.interval(1, 3);
2227        let f = h.lambda(7, dom, &[int(5)]);
2228        assert!(h.is_lazy(f));
2229        let c = h
2230            .closure(f)
2231            .map(|c| (c.kind, c.id, c.domain, c.captures.to_vec()));
2232        assert_eq!(c, Some((Kind::Lambda, 7, dom, vec![int(5)])));
2233        // A record holding it is lazy; a closed one is not.
2234        let a = h.string("a").unwrap_or(Handle::EMPTY);
2235        let r = h.fcn_sorted(&[a], &[f]);
2236        assert!(h.is_lazy(r));
2237        let closed = h.fcn_sorted(&[a], &[int(1)]);
2238        assert!(!h.is_lazy(closed));
2239        assert!(!h.poisoned());
2240        // Interning an unclosed value is refused.
2241        assert!(h.intern(r).is_err());
2242        assert!(!h.poisoned());
2243        // EXCEPT replacing the only lazy entry recounts laziness.
2244        let r2 = h.fcn_with(r, 0, int(1));
2245        assert!(!h.is_lazy(r2));
2246        assert!(h.eq(r2, closed));
2247        let p = h.set_pred(2, dom, &[]);
2248        assert!(h.is_lazy(p));
2249        assert_eq!(h.norm(p).ok(), Some(p), "only the evaluator enumerates it");
2250        assert!(h.cursor(p).is_err());
2251        assert!(!h.poisoned());
2252    }
2253
2254    #[test]
2255    fn lazy_values_in_closed_positions_poison() {
2256        for op in 0..3 {
2257            let mut h = heap(false);
2258            let dom = h.interval(1, 3);
2259            let f = h.lambda(0, dom, &[]);
2260            match op {
2261                0 => {
2262                    let _ = h.hash(f);
2263                }
2264                1 => {
2265                    let _ = h.set_sorted(&[f]);
2266                }
2267                _ => {
2268                    let g = h.lambda(1, dom, &[]);
2269                    let _ = h.eq(f, g);
2270                }
2271            }
2272            assert!(h.poisoned(), "op {op}");
2273        }
2274    }
2275
2276    #[test]
2277    fn rebuild_closes_a_value_bottom_up() {
2278        let mut h = heap(false);
2279        let dom = h.interval(1, 2);
2280        let f = h.lambda(0, dom, &[]);
2281        let t = h.tuple(&[int(9), f]);
2282        // The evaluator materializes `f` and rebuilds the parent.
2283        let m = h.int_fcn(1, &[int(10), int(20)]);
2284        let data = h.view(t).data.to_vec();
2285        let closed = h.rebuild(t, &[data[0], m]);
2286        assert!(!h.is_lazy(closed));
2287        let direct = h.tuple(&[int(9), m]);
2288        assert!(h.eq(closed, direct));
2289        assert_eq!(h.hash(closed), h.hash(direct));
2290        assert!(h.intern(closed).is_ok());
2291        // A rebuilt set is re-sorted.
2292        let s = h.set_from(&mut vec![int(1), int(2)]);
2293        let s2 = h.rebuild(s, &[int(5), int(3)]);
2294        assert_eq!(h.view(s2).data, &[int(3), int(5)]);
2295        assert!(!h.poisoned());
2296    }
2297
2298    #[test]
2299    fn lazy_constants_stay_lazy_and_are_never_compared_by_handle() {
2300        let mut h = heap(false);
2301        let nat = h.symbolic(Kind::Nat, 0, &[]);
2302        let f = h.lambda(3, nat, &[]);
2303        let p = h.intern_const(f).unwrap_or(Handle::EMPTY);
2304        assert!(p.is_lazy_persistent());
2305        h.reset();
2306        assert_eq!(h.closure(p).map(|c| c.id), Some(3));
2307        assert!(h.intern(p).is_err());
2308        let nat = h.symbolic(Kind::Nat, 0, &[]);
2309        let g = h.lambda(4, nat, &[]);
2310        let q = h.intern_const(g).unwrap_or(Handle::EMPTY);
2311        assert!(!h.poisoned());
2312        let _ = h.eq(p, q);
2313        assert!(h.poisoned(), "two lazy constants cannot be compared");
2314    }
2315
2316    #[test]
2317    fn nested_function_views_never_claim_canonical_identity() -> Result<(), Error> {
2318        for hashcons in [true, false] {
2319            for exact in [false, true] {
2320                let store = Arc::new(Store::new(hashcons));
2321                let mut h = Heap::new(store, false, false);
2322                let a = h.string("a")?;
2323                let record = h.record(&[a], &[int(0)]);
2324                let general = h.fcn_sorted(&[a], &[int(0)]);
2325                let left = h.fcn_sorted(&[int(1)], &[record]);
2326                let right = h.fcn_sorted(&[int(1)], &[general]);
2327                let left = h.fcn_sorted(&[int(1)], &[left]);
2328                let right = h.fcn_sorted(&[int(1)], &[right]);
2329                let (left, right) = if exact {
2330                    (h.intern_exact(left)?, h.intern_exact(right)?)
2331                } else {
2332                    (h.intern_const(left)?, h.intern_const(right)?)
2333                };
2334                h.reset();
2335                assert!(
2336                    h.eq(left, right),
2337                    "equal values cannot be rejected by the persistent identity fast path"
2338                );
2339                assert!(
2340                    left.is_lazy_persistent(),
2341                    "nested representation is structural"
2342                );
2343                assert_eq!(
2344                    h.view(left).flags & flags::TUPLE,
2345                    0,
2346                    "the parent is still a general function"
2347                );
2348                assert_ne!(left, right, "representations remain distinct");
2349                assert_eq!(h.hash(left), h.hash(right));
2350                let a = h.intern(left)?;
2351                let b = h.intern(right)?;
2352                assert!(!a.is_lazy_persistent());
2353                assert!(h.eq(a, b));
2354                if hashcons {
2355                    assert_eq!(a, b, "canonical identity is unchanged");
2356                }
2357            }
2358        }
2359        Ok(())
2360    }
2361
2362    #[test]
2363    fn unions_stay_symbolic_until_normalized() {
2364        let mut h = heap(false);
2365        let a = h.interval(1, 3);
2366        let b = h.set_from(&mut vec![int(0), int(2), int(7)]);
2367        let u = h.union(a, b);
2368        assert_eq!(h.kind(u), Some(Kind::Union));
2369        assert!(h.is_finite(u));
2370        assert_eq!(h.cardinality(u).ok(), Some(5));
2371        let n = h.norm(u).unwrap_or(Handle::EMPTY);
2372        assert_eq!(h.view(n).data, &[int(0), int(1), int(2), int(3), int(7)]);
2373        let nat = h.symbolic(Kind::Nat, 0, &[]);
2374        let inf = h.union(nat, b);
2375        assert!(!h.is_finite(inf));
2376        assert_eq!(h.norm(inf).ok(), Some(inf));
2377        assert!(!h.poisoned());
2378    }
2379
2380    #[test]
2381    fn intern_view_keeps_the_representation_beside_the_identity() {
2382        let mut h = heap(false);
2383        let iv = h.interval(1, 3);
2384        let (id, view) = h.intern_view(iv).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2385        assert_eq!(h.kind(id), Some(Kind::Set));
2386        assert_eq!(h.kind(view), Some(Kind::Interval));
2387        let e = h.set_from(&mut vec![int(3), int(2), int(1)]);
2388        let (id2, none) = h.intern_view(e).unwrap_or((Handle::EMPTY, Handle::TRUE));
2389        assert_eq!(id, id2, "identity is extensional");
2390        assert!(none.is_empty());
2391        assert!(!h.poisoned());
2392    }
2393
2394    #[test]
2395    fn sets_of_strings_follow_the_store_order() {
2396        use crate::strings::StringOrder;
2397        for (order, want) in [
2398            (StringOrder::Text, ["a", "b"]),
2399            (StringOrder::Token, ["b", "a"]),
2400        ] {
2401            let store = Arc::new(Store::with_string_order(true, order));
2402            assert!(store.strings().preload(["b", "a"]).is_ok());
2403            let mut h = Heap::new(store, false, false);
2404            let (a, b) = (
2405                h.string("a").unwrap_or(Handle::EMPTY),
2406                h.string("b").unwrap_or(Handle::EMPTY),
2407            );
2408            let set = h.set_from(&mut vec![a, b]);
2409            let got: Vec<String> = h
2410                .view(set)
2411                .data
2412                .iter()
2413                .filter_map(|e| e.as_str_id())
2414                .filter_map(|id| h.store().strings().text(id))
2415                .map(|t| t.to_string())
2416                .collect();
2417            assert_eq!(got, want, "{order:?}");
2418        }
2419    }
2420
2421    #[test]
2422    fn an_exact_copy_keeps_every_view_bit_and_symbolic_set() {
2423        let mut h = heap(false);
2424        let (a, b) = (
2425            h.string("a").unwrap_or(Handle::EMPTY),
2426            h.string("b").unwrap_or(Handle::EMPTY),
2427        );
2428        let span = h.interval(1, 3);
2429        let inner = h.record(&[a], &[int(1)]);
2430        let lit = h.record(&[a, b], &[inner, span]);
2431        let exact = h.intern_exact(lit).unwrap_or(Handle::EMPTY);
2432        assert!(exact.is_persistent());
2433        let v = h.view(exact);
2434        assert!(v.is_record_literal());
2435        let (first, second) = (v.values()[0], v.values()[1]);
2436        assert!(h.view(first).is_record_literal(), "nested bits are kept");
2437        assert_eq!(h.view(second).kind, Kind::Interval, "symbolic sets stay");
2438        assert!(h.eq(exact, lit));
2439        // Equal representations share one handle; the identity is apart.
2440        let inner2 = h.record(&[a], &[int(1)]);
2441        let span2 = h.interval(1, 3);
2442        let lit2 = h.record(&[a, b], &[inner2, span2]);
2443        assert_eq!(h.intern_exact(lit2).ok(), Some(exact));
2444        let fcn = h.fcn_sorted(&[a, b], &[inner2, span2]);
2445        assert_ne!(h.intern_exact(fcn).ok(), Some(exact));
2446    }
2447
2448    /// A function key may be a closed view: a tuple of records that an
2449    /// exact intern (graph capture for liveness) marked `NESTED_VIEW`, as
2450    /// `KeyValueStore`'s `PermSeqs` over its logged operations builds.
2451    /// Only a lazy key is a misuse.
2452    #[test]
2453    fn a_closed_view_is_a_function_key() {
2454        let mut h = heap(false);
2455        let a = h.string("a").unwrap_or(Handle::EMPTY);
2456        let rec = h.record(&[a], &[int(1)]);
2457        let seq = h.tuple_literal(&[rec]);
2458        let key = h.intern_exact(seq).unwrap_or(Handle::EMPTY);
2459        assert_ne!(h.view(key).flags & flags::NESTED_VIEW, 0);
2460        let f = h.fcn_sorted(&[key, a], &[int(1), int(2)]);
2461        assert!(!h.poisoned());
2462        assert_ne!(h.view(f).flags & flags::NESTED_VIEW, 0, "the view is kept");
2463        let plain = h.tuple(&[rec]);
2464        let g = h.fcn_sorted(&[plain, a], &[int(1), int(2)]);
2465        assert!(h.eq(f, g));
2466        let dom = h.interval(1, 2);
2467        let lazy = h.set_pred(0, dom, &[]);
2468        let _ = h.fcn_sorted(&[lazy], &[int(1)]);
2469        assert!(h.poisoned(), "a lazy key is still a misuse");
2470    }
2471
2472    #[test]
2473    fn a_record_literal_bit_is_a_view_bit() {
2474        let mut h = heap(false);
2475        let (a, b) = (
2476            h.string("a").unwrap_or(Handle::EMPTY),
2477            h.string("b").unwrap_or(Handle::EMPTY),
2478        );
2479        let (keys, vals) = ([a, b], [int(1), int(2)]);
2480        let lit = h.record(&keys, &vals);
2481        let fcn = h.fcn_sorted(&keys, &vals);
2482        assert!(h.view(lit).is_record_literal());
2483        assert!(!h.view(fcn).is_record_literal());
2484        assert!(h.eq(lit, fcn), "equality ignores the bit");
2485        assert_eq!(h.hash(lit), h.hash(fcn));
2486        assert_eq!(h.cmp(lit, fcn), Ordering::Equal);
2487        let changed = h.fcn_with(lit, 0, int(9));
2488        assert!(h.view(changed).is_record_literal(), "EXCEPT keeps it");
2489
2490        // The identity never carries the bit, whichever is interned first.
2491        let id_lit = h.intern(lit).unwrap_or(Handle::EMPTY);
2492        let id_fcn = h.intern(fcn).unwrap_or(Handle::TRUE);
2493        assert_eq!(id_lit, id_fcn);
2494        assert!(!h.view(id_lit).is_record_literal());
2495        let lit2 = h.record(&keys, &vals);
2496        let (id, view) = h
2497            .intern_view(lit2)
2498            .unwrap_or((Handle::EMPTY, Handle::EMPTY));
2499        assert_eq!(id, id_fcn);
2500        assert!(h.view(view).is_record_literal());
2501        assert_ne!(view, id, "the view is interned apart from the identity");
2502        assert!(h.eq(view, id));
2503        assert_eq!(h.intern(view).ok(), Some(id));
2504        let again = h.record(&keys, &vals);
2505        let (_, view2) = h
2506            .intern_view(again)
2507            .unwrap_or((Handle::EMPTY, Handle::EMPTY));
2508        assert_eq!(view2, view, "views are hash-consed among themselves");
2509        let k = h.record(&keys, &vals);
2510        let constant = h.intern_const(k).unwrap_or(Handle::EMPTY);
2511        assert!(h.view(constant).is_record_literal());
2512        assert_eq!(
2513            h.intern(constant).ok(),
2514            Some(id),
2515            "identity remains canonical"
2516        );
2517        // A set holding the view and the identity has one element.
2518        let set = h.set_from(&mut vec![view, id]);
2519        assert_eq!(h.view(set).data.len(), 1);
2520        // Tuple literals likewise.
2521        let t = h.tuple_literal(&[int(1), int(2)]);
2522        let plain = h.tuple(&[int(1), int(2)]);
2523        assert!(h.view(t).is_tuple_literal() && !h.view(plain).is_tuple_literal());
2524        assert!(h.eq(t, plain));
2525        let t2 = h.fcn_with(t, 1, int(5));
2526        assert!(h.view(t2).is_tuple_literal());
2527        let (tid, tview) = h.intern_view(t).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2528        assert_eq!(h.intern(plain).ok(), Some(tid));
2529        assert!(h.view(tview).is_tuple_literal() && !h.view(tid).is_tuple_literal());
2530        assert!(!h.poisoned());
2531    }
2532
2533    #[test]
2534    fn a_set_enumeration_keeps_tlc_construction_order_as_a_view() {
2535        let mut h = heap(false);
2536        let e = h.set_enum(&[int(3), int(1), int(3), int(2)]);
2537        let v = h.view(e);
2538        assert_eq!(v.kind, Kind::SetEnum);
2539        assert!(!v.is_norm());
2540        assert_eq!(v.data, &[int(3), int(1), int(3), int(2)]);
2541        assert!(h.is_finite(e));
2542        assert_eq!(h.cardinality(e).ok(), Some(3));
2543        let n = h.norm(e).unwrap_or(Handle::EMPTY);
2544        assert!(h.view(n).is_norm());
2545        assert_eq!(h.view(n).data, &[int(1), int(2), int(3)]);
2546        let plain = h.set_from(&mut vec![int(1), int(2), int(3)]);
2547        let id_plain = h.intern(plain).unwrap_or(Handle::EMPTY);
2548        let (id, view) = h.intern_view(e).unwrap_or((Handle::EMPTY, Handle::EMPTY));
2549        assert_eq!(id, id_plain);
2550        assert_eq!(h.kind(view), Some(Kind::SetEnum));
2551        assert!(!h.view(view).is_norm());
2552        assert_eq!(h.intern(view).ok(), Some(id));
2553        assert!(!h.poisoned());
2554    }
2555
2556    #[test]
2557    fn subset_cursor_is_in_canonical_order() {
2558        let mut h = heap(false);
2559        let base = h.set_from(&mut vec![int(1), int(2)]);
2560        let s = h.symbolic(Kind::Subset, 0, &[base]);
2561        let elems = h.elements(s).unwrap_or_default();
2562        assert_eq!(elems.len(), 4);
2563        for w in elems.windows(2) {
2564            assert_eq!(h.cmp(w[0], w[1]), Ordering::Less);
2565        }
2566    }
2567
2568    #[test]
2569    fn constant_domains_are_enumerated_once_into_equal_persistent_elements() {
2570        let mut h = heap(false);
2571        let ints = h.interval(1, 2);
2572        let names = h.set_from(&mut vec![int(7), int(8)]);
2573        let product = h.symbolic(Kind::Product, 0, &[ints, names]);
2574        let subset = h.symbolic(Kind::Subset, 0, &[product]);
2575        let domain = h.intern_exact(subset).unwrap_or(Handle::EMPTY);
2576        assert!(domain.is_persistent());
2577        let fresh = h.norm(domain).unwrap_or(Handle::EMPTY);
2578        let kept = h.enumerate_constant(domain).unwrap_or(Handle::EMPTY);
2579        assert!(kept.is_persistent());
2580        assert_eq!(h.enumerate_constant(domain).ok(), Some(kept));
2581        let fresh_elems = h.elements(fresh).unwrap_or_default();
2582        let kept_elems = h.elements(kept).unwrap_or_default();
2583        assert_eq!(kept_elems.len(), 16);
2584        assert_eq!(fresh_elems.len(), kept_elems.len());
2585        for (&a, &b) in fresh_elems.iter().zip(&kept_elems) {
2586            assert!(b.is_persistent());
2587            assert_eq!(h.cmp(a, b), Ordering::Equal);
2588            assert_eq!(h.intern(a).ok(), Some(b));
2589        }
2590        // An enumeration above the bound is built afresh every time.
2591        let big = h.interval(1, 17);
2592        let big = h.symbolic(Kind::Subset, 0, &[big]);
2593        let big = h.intern_exact(big).unwrap_or(Handle::EMPTY);
2594        for _ in 0..2 {
2595            let m = h.enumerate_constant(big).unwrap_or(Handle::EMPTY);
2596            assert!(m.is_transient());
2597            assert_eq!(h.view(m).data.len(), 1 << 17);
2598        }
2599        // The word budget counts transient headers and data, not
2600        // persistent children.
2601        let fresh = h.norm(domain).unwrap_or(Handle::EMPTY);
2602        assert!(h.within_transient_words(fresh, 1 << 12));
2603        // The top node alone holds 1 + 16 words.
2604        assert!(!h.within_transient_words(fresh, 16));
2605        assert!(h.within_transient_words(kept, 0));
2606        // Non-symbolic and transient sets are normalized as `norm` does.
2607        let set = h.set_from(&mut vec![int(1)]);
2608        assert_eq!(h.enumerate_constant(set).ok(), Some(set));
2609        assert!(!h.poisoned());
2610    }
2611
2612    fn unmarked(h: &mut Heap, t: Handle) -> Handle {
2613        h.unmarked_copy(t)
2614    }
2615
2616    #[test]
2617    fn concrete_proofs_trust_the_bit_and_the_bounded_walk_decides_without_it() {
2618        let mut h = heap(false);
2619        let name = h.string("abcd").unwrap_or(Handle::EMPTY);
2620        let model = Handle::model(h.store().strings().intern("m").unwrap_or(0));
2621        for scalar in [Handle::TRUE, int(-3), name, model] {
2622            assert!(h.proved_concrete(scalar));
2623            assert!(h.materialized_within(&[scalar], 1, None));
2624        }
2625        let unknown = Handle::string(1 << 20);
2626        for refused in [Handle::EMPTY, unknown, Handle::model(1 << 20)] {
2627            assert!(!h.proved_concrete(refused));
2628            assert!(!h.materialized_within(&[refused], 8, None));
2629        }
2630        // Eager builders and exact interning keep the cached proof.
2631        let tuple = h.tuple_literal(&[name, model]);
2632        let set = h.set_from(&mut vec![tuple, int(1), model]);
2633        assert!(!h.proved_concrete(set), "a transient is never proved");
2634        assert!(!h.materialized_within(&[set], 64, None));
2635        let marked = h.intern_exact(set).unwrap_or(Handle::EMPTY);
2636        assert!(h.proved_concrete(marked));
2637        assert!(h.materialized_within(&[marked], 1, None));
2638        // With a name allowance every node is entered and every occurrence counts.
2639        assert!(h.materialized_within(&[marked], 64, Some(6)));
2640        assert!(!h.materialized_within(&[marked], 64, Some(5)));
2641        assert!(!h.materialized_within(&[marked], 3, Some(64)));
2642        // Without the bit the walk decides, within its node allowance.
2643        let inner = h.tuple_literal(&[int(7), name]);
2644        let inner = unmarked(&mut h, inner);
2645        let outer = h.set_from(&mut vec![inner, Handle::FALSE]);
2646        let outer = unmarked(&mut h, outer);
2647        assert_eq!(h.view(outer).flags & flags::CONCRETE, 0);
2648        assert!(!h.proved_concrete(outer));
2649        assert!(h.materialized_within(&[outer], 5, None));
2650        assert!(!h.materialized_within(&[outer], 4, None));
2651        // Symbolic, unnormalized and lazy nodes decline at any depth.
2652        let interval = h.interval(1, 3);
2653        let raw = h.set_enum(&[int(2), int(1)]);
2654        let raw = h.intern_exact(raw).unwrap_or(Handle::EMPTY);
2655        for symbolic in [interval, raw] {
2656            let symbolic = h.intern_exact(symbolic).unwrap_or(Handle::EMPTY);
2657            let nested = h.tuple(&[symbolic]);
2658            let nested = unmarked(&mut h, nested);
2659            for value in [symbolic, nested] {
2660                assert!(!h.proved_concrete(value));
2661                assert!(!h.materialized_within(&[value], 64, None));
2662            }
2663        }
2664        let big = h.int_from_big(&(num_bigint::BigInt::from(1) << 80u32));
2665        if big.is_compound() {
2666            let big = h.intern_exact(big).unwrap_or(Handle::EMPTY);
2667            assert!(h.proved_concrete(big));
2668            assert!(h.materialized_within(&[big], 1, None));
2669        }
2670        assert!(!h.poisoned());
2671        let _ = h.view(Handle::EMPTY);
2672        assert!(
2673            !h.materialized_within(&[int(1)], 1, None),
2674            "current poison declines"
2675        );
2676    }
2677}