Skip to main content

dive_value/
value.rs

1//! The value representation.
2//!
3//! [`Value`] is 16 bytes, immutable, `Send + Sync`, and cheap to clone: scalars are
4//! inline and compound values are shared behind an [`Arc`]. Compound values carry a
5//! precomputed (or lazily cached) hash, so hashing is O(1) and unequal values usually
6//! differ at the first hash comparison. Dropping a value is iterative, so any nesting
7//! depth is safe.
8
9use std::fmt;
10use std::hash::{Hash, Hasher};
11use std::sync::atomic::{AtomicBool, Ordering as AtomicOrdering};
12use std::sync::{Arc, OnceLock};
13
14use num_bigint::BigInt;
15
16use crate::atom::{Atom, mix64};
17use crate::ctx::{Ctx, ValueOrder};
18use crate::error::{ErrorKind, Result, ValueError};
19use crate::function_domain::{DomainInner, GeneralFcn};
20use crate::int::Int;
21
22/// A TLA+ value.
23///
24/// Integers built through [`Value::int`] are canonical: [`Value::Int`] for every value
25/// in `i64` range and [`Value::BigInt`] only outside it. Equality, ordering, hashing
26/// and fingerprints are numeric even for a hand-built `BigInt` that fits in an `i64`.
27/// Functions are canonical by domain (see [`Fcn`]). Sets may be enumerated or lazy
28/// (see [`Set`]); equality and hashing look through the representation.
29#[derive(Clone)]
30pub enum Value {
31    /// `TRUE` or `FALSE`.
32    Bool(bool),
33    /// An integer in `i64` range.
34    Int(i64),
35    /// An integer outside `i64` range (big-integer mode only).
36    BigInt(Arc<BigInt>),
37    /// A string.
38    Str(Atom),
39    /// A model value: untyped, or typed when named `x_name` (TLC's rule).
40    Model(Atom),
41    /// A set.
42    Set(Set),
43    /// A function, including tuples, sequences and records.
44    Fcn(Fcn),
45}
46
47/// Per-kind constants for [`Value`]'s hash.
48const K_BOOL: u64 = 0x1f83_d9ab_fb41_bd6b;
49const K_INT: u64 = 0x5be0_cd19_137e_2179;
50pub(crate) const K_STR: u64 = 0x6a09_e667_f3bc_c908;
51const K_MV: u64 = 0xbb67_ae85_84ca_a73b;
52pub(crate) const K_SET: u64 = 0x3c6e_f372_fe94_f82b;
53const K_FCN: u64 = 0xa54f_f53a_5f1d_36f1;
54
55pub(crate) fn mix2(a: u64, b: u64) -> u64 {
56    mix64(a ^ b.rotate_left(29).wrapping_mul(0x9e37_79b9_7f4a_7c15))
57}
58
59/// Hash of the integer `v`, shared by inline and big integers and by tuple domains.
60pub(crate) fn int_hash(v: i64) -> u64 {
61    #[allow(clippy::cast_sign_loss, reason = "bit reinterpretation for hashing")]
62    mix64((v as u64) ^ K_INT)
63}
64
65impl Value {
66    /// `TRUE`.
67    pub const TRUE: Self = Self::Bool(true);
68    /// `FALSE`.
69    pub const FALSE: Self = Self::Bool(false);
70
71    /// An integer value from an [`Int`], in canonical form.
72    #[must_use]
73    pub fn int(i: Int) -> Self {
74        match i {
75            Int::Small(v) => Self::Int(v),
76            Int::Big(b) => match Int::from_big((*b).clone()) {
77                Int::Small(v) => Self::Int(v),
78                Int::Big(_) => Self::BigInt(b),
79            },
80        }
81    }
82
83    /// The integer, if this is one, in canonical form.
84    #[must_use]
85    pub fn as_int(&self) -> Option<Int> {
86        match self {
87            Self::Int(v) => Some(Int::Small(*v)),
88            Self::BigInt(b) => Some(Int::from_big((**b).clone())),
89            _ => None,
90        }
91    }
92
93    /// The boolean, if this is one.
94    #[must_use]
95    pub const fn as_bool(&self) -> Option<bool> {
96        match self {
97            Self::Bool(b) => Some(*b),
98            _ => None,
99        }
100    }
101
102    /// The set, if this is one.
103    #[must_use]
104    pub const fn as_set(&self) -> Option<&Set> {
105        match self {
106            Self::Set(s) => Some(s),
107            _ => None,
108        }
109    }
110
111    /// The function, if this is one.
112    #[must_use]
113    pub const fn as_fcn(&self) -> Option<&Fcn> {
114        match self {
115            Self::Fcn(f) => Some(f),
116            _ => None,
117        }
118    }
119
120    /// The hash used by [`Hash`]: order-independent for sets and functions, so equal
121    /// values hash equally whatever their representation (an interval and the
122    /// enumerated set it equals, for example). Never changes how TLC's operations
123    /// behave: hashing an unnormalized set does not normalize it.
124    #[must_use]
125    pub fn hash64(&self) -> u64 {
126        match self {
127            Self::Bool(b) => mix64(K_BOOL ^ u64::from(*b)),
128            Self::Int(v) => int_hash(*v),
129            Self::BigInt(b) => match self.as_int().and_then(|i| i.to_i64()) {
130                Some(v) => int_hash(v),
131                None => b
132                    .to_signed_bytes_le()
133                    .iter()
134                    .fold(K_INT, |h, d| mix2(h, u64::from(*d))),
135            },
136            Self::Str(a) => mix2(K_STR, a.text_hash()),
137            Self::Model(a) => mix2(K_MV, a.text_hash()),
138            Self::Set(s) => s.hash64(),
139            Self::Fcn(f) => f.0.hash,
140        }
141    }
142
143    /// A short name of the value's kind, for diagnostics.
144    #[must_use]
145    pub fn kind_name(&self) -> &'static str {
146        match self {
147            Self::Bool(_) => "boolean",
148            Self::Int(_) | Self::BigInt(_) => "integer",
149            Self::Str(_) => "string",
150            Self::Model(_) => "model value",
151            Self::Set(_) => "set",
152            Self::Fcn(_) => "function",
153        }
154    }
155}
156
157impl From<bool> for Value {
158    fn from(b: bool) -> Self {
159        Self::Bool(b)
160    }
161}
162
163impl From<i64> for Value {
164    fn from(v: i64) -> Self {
165        Self::Int(v)
166    }
167}
168
169impl From<Int> for Value {
170    fn from(v: Int) -> Self {
171        Self::int(v)
172    }
173}
174
175impl Hash for Value {
176    fn hash<H: Hasher>(&self, state: &mut H) {
177        state.write_u64(self.hash64());
178    }
179}
180
181impl PartialEq for Value {
182    fn eq(&self, other: &Self) -> bool {
183        crate::order::semantic_eq(self, other)
184    }
185}
186
187impl Eq for Value {}
188
189/// The TLC printing of the value. Formatting never changes how TLC's operations
190/// behave: it does not normalize unnormalized sets.
191impl fmt::Debug for Value {
192    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
193        match crate::print::to_debug_string(self) {
194            Some(s) => f.write_str(&s),
195            None => write!(f, "<{}>", self.kind_name()),
196        }
197    }
198}
199
200// ---------------------------------------------------------------------------------
201// Sets
202// ---------------------------------------------------------------------------------
203
204/// A set, enumerated or lazy. Cloning is a reference-count increment.
205///
206/// Enumerated sets are kept normalized: sorted in the run's [`ValueOrder`] without
207/// duplicates. Lazy sets (`a..b`, `SUBSET S`, `[S -> T]`, `S \X T`, `[a : S]`, `Nat`,
208/// `Int`, `STRING`, `Seq(S)`, and evaluator-driven filters and maps) keep their
209/// definition; membership is decided without enumerating, as in TLC. Equality,
210/// ordering, hashing and fingerprints stream lazy sets in normalized order rather
211/// than materializing them. Infinite sets refuse enumeration with
212/// [`ErrorKind::NotEnumerable`].
213#[derive(Clone)]
214pub struct Set(pub(crate) Arc<SetInner>);
215
216pub(crate) struct SetInner {
217    pub(crate) order: ValueOrder,
218    pub(crate) hash: OnceLock<u64>,
219    /// The normalized elements, once computed. Only successes are cached, so an error
220    /// is always computed under the caller's context.
221    pub(crate) elems: OnceLock<Arc<[Value]>>,
222    /// For `Raw` sets: whether TLC would consider the set normalized (`isNorm`). Set
223    /// only by the operations that normalize in TLC, never by hashing, `==` or
224    /// formatting.
225    pub(crate) tlc_norm: AtomicBool,
226    /// The cached FP64 fingerprint of this set alone (see [`crate::fp64::FpCache`]).
227    pub(crate) fp: crate::fp64::FpCache,
228    pub(crate) repr: SetRepr,
229}
230
231/// The source of an evaluator-driven lazy set (`{x \in S : P}` or `{e : x \in S}`).
232///
233/// `dive-value` stores and prints such sets but cannot evaluate them: `dive-eval`
234/// implements this trait.
235pub trait DeferredSet: Send + Sync + fmt::Debug + std::any::Any {
236    /// Which construct the set is.
237    fn kind(&self) -> DeferredKind;
238    /// Computes the set's elements in any order; `dive-value` normalizes them.
239    ///
240    /// # Errors
241    /// Any evaluation error.
242    fn elements(&self, ctx: Ctx) -> Result<Vec<Value>>;
243    /// Decides membership without enumerating, if the source can.
244    ///
245    /// # Errors
246    /// Any evaluation error.
247    fn member(&self, elem: &Value, ctx: Ctx) -> Option<Result<bool>>;
248    /// A stable description of the definition (for example the bound set and the
249    /// values the predicate closes over). Two unenumerable deferred sets of the same
250    /// kind are equal, and ordered, by their keys; enumerable ones by their elements.
251    /// The default, an empty key, makes all unenumerable sets of one kind equal.
252    fn key(&self) -> Vec<Value> {
253        Vec::new()
254    }
255    /// The source as [`std::any::Any`], so that its owner can recover its
256    /// own type (the evaluator reproduces TLC's unnormalized enumeration of
257    /// its lazy sets). The default, `None`, hides it.
258    fn as_any(&self) -> Option<&dyn std::any::Any> {
259        None
260    }
261}
262
263/// See [`DeferredSet::kind`].
264#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
265pub enum DeferredKind {
266    /// `{x \in S : P}`.
267    Filter,
268    /// `{e : x \in S}`.
269    Map,
270    /// `S \cup T` of sets TLC keeps lazy (`SetCupValue`).
271    Cup,
272    /// `S \cap T` of sets TLC keeps lazy (`SetCapValue`).
273    Cap,
274    /// `S \ T` of sets TLC keeps lazy (`SetDiffValue`).
275    Diff,
276    /// `UNION S` that TLC keeps lazy (`UnionValue`).
277    Union,
278}
279
280pub(crate) enum SetRepr {
281    /// Normalized elements (the elements live in `SetInner::elems`).
282    Enum,
283    /// Elements as constructed, normalized on demand (TLC's unnormalized
284    /// `SetEnumValue`). Until TLC would normalize it, membership scans the elements
285    /// linearly with TLC's equality.
286    Raw(Box<[Value]>),
287    Interval(Int, Int),
288    Subset(Value),
289    FcnSet(Value, Value),
290    /// Fields sorted in the set's order, without duplicates.
291    RcdSet(Box<[(Atom, Value)]>),
292    Product(Box<[Value]>),
293    Nat,
294    Int,
295    Strings,
296    Seq(Value),
297    Deferred(Arc<dyn DeferredSet>),
298}
299
300/// The kind of a set, as a plain enum for matching.
301#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
302pub enum SetKind {
303    /// An enumerated, normalized set.
304    Enum,
305    /// An enumerated set as written, normalized on demand.
306    Raw,
307    /// `a..b`.
308    Interval,
309    /// `SUBSET S`.
310    Subset,
311    /// `[S -> T]`.
312    FcnSet,
313    /// `[a : S, ...]`.
314    RcdSet,
315    /// `S1 \X ... \X Sn`.
316    Product,
317    /// `Nat`.
318    Nat,
319    /// `Int`.
320    Int,
321    /// `STRING`.
322    Strings,
323    /// `Seq(S)`.
324    Seq,
325    /// An evaluator-driven filter or map.
326    Deferred,
327}
328
329impl Set {
330    pub(crate) fn new(order: ValueOrder, repr: SetRepr) -> Self {
331        Self(Arc::new(SetInner {
332            order,
333            hash: OnceLock::new(),
334            elems: OnceLock::new(),
335            tlc_norm: AtomicBool::new(false),
336            fp: crate::fp64::FpCache::new(),
337            repr,
338        }))
339    }
340
341    /// Builds a set from elements already sorted and deduplicated in `order`.
342    pub(crate) fn from_sorted(order: ValueOrder, elems: Vec<Value>) -> Self {
343        let set = Self::new(order, SetRepr::Enum);
344        let elems: Arc<[Value]> = elems.into();
345        let _ = set.0.hash.set(set_hash(
346            elems.iter().map(Value::hash64),
347            elems.len() as u128,
348        ));
349        let _ = set.0.elems.set(elems);
350        set
351    }
352
353    /// Stored explicit elements, without normalization, enumeration or callbacks.
354    #[must_use]
355    pub fn stored_elements(&self) -> Option<&[Value]> {
356        match &self.0.repr {
357            SetRepr::Enum => self.0.elems.get().map(AsRef::as_ref),
358            SetRepr::Raw(e) => Some(e),
359            _ => None,
360        }
361    }
362
363    /// Whether normalized element storage has already been cached.
364    /// This reads storage only; it invokes no provider and grants no authority
365    /// to reproduce a deferred provider's conversion or callback history.
366    #[must_use]
367    pub fn has_cached_elements(&self) -> bool {
368        self.0.elems.get().is_some()
369    }
370
371    /// The set's kind.
372    #[must_use]
373    pub fn kind(&self) -> SetKind {
374        match &self.0.repr {
375            SetRepr::Enum => SetKind::Enum,
376            SetRepr::Raw(_) => SetKind::Raw,
377            SetRepr::Interval(..) => SetKind::Interval,
378            SetRepr::Subset(_) => SetKind::Subset,
379            SetRepr::FcnSet(..) => SetKind::FcnSet,
380            SetRepr::RcdSet(_) => SetKind::RcdSet,
381            SetRepr::Product(_) => SetKind::Product,
382            SetRepr::Nat => SetKind::Nat,
383            SetRepr::Int => SetKind::Int,
384            SetRepr::Strings => SetKind::Strings,
385            SetRepr::Seq(_) => SetKind::Seq,
386            SetRepr::Deferred(_) => SetKind::Deferred,
387        }
388    }
389
390    /// The order the set is sorted in.
391    #[must_use]
392    pub fn order(&self) -> ValueOrder {
393        self.0.order
394    }
395
396    /// Whether the set is infinite (`Nat`, `Int`, `STRING`, `Seq(S)` for non-empty `S`,
397    /// and lazy sets built from those).
398    #[must_use]
399    pub fn is_infinite(&self) -> bool {
400        crate::enumerate::is_infinite(self)
401    }
402
403    /// The elements in normalized order, enumerating if the set is lazy: TLC's
404    /// `elements()`/`toSetEnum()`. An unnormalized (`Raw`) set counts as normalized
405    /// afterwards, as in TLC.
406    ///
407    /// # Errors
408    /// [`ErrorKind::NotEnumerable`] for an infinite or symbolic set,
409    /// [`ErrorKind::TooLarge`] when the set is too large, and comparison errors from
410    /// normalization.
411    pub fn elements(&self, ctx: Ctx) -> Result<Arc<[Value]>> {
412        if !matches!(
413            self.0.repr,
414            SetRepr::Enum | SetRepr::Raw(_) | SetRepr::Deferred(_)
415        ) {
416            // TLC's `toSetEnum` sizes the set first: its size errors come first.
417            crate::enumerate::size(self, ctx)?;
418        }
419        let e = self.cached_elements(ctx)?;
420        self.mark_normalized();
421        Ok(e)
422    }
423
424    /// Streams a concrete set's raw TLC enumeration over concrete components,
425    /// without sizing or materializing the complete compound result.
426    ///
427    /// Returns `None`, without normalization or callbacks, unless this is a
428    /// finite explicit collection, interval, powerset, product, function set
429    /// or record set whose complete component storage is concrete and in the
430    /// same value order. Deferred or symbolic storage keeps its old route. All capability
431    /// checks precede effects; this selects output storage, never admission.
432    ///
433    /// Constructor emptiness checks precede component normalization, in TLC's
434    /// order. Nonempty components are materialized before the first output, so
435    /// this does not make a huge individual component incremental. Output order
436    /// follows this set's construction order; callers must establish that it is
437    /// their required exploration order. The full result is not cached.
438    ///
439    /// ```
440    /// use dive_value::{Ctx, Value};
441    /// let ctx = Ctx::dive();
442    /// let base = Value::interval(1.into(), 31.into(), ctx);
443    /// let Value::Set(powerset) = Value::subset(base, ctx) else {
444    ///     return Err("SUBSET must produce a set".into());
445    /// };
446    /// let mut elements = powerset.concrete_element_stream(ctx)?
447    ///     .ok_or("components need another enumeration route")?;
448    /// assert_eq!(elements.next(), Some(Value::set(vec![], ctx)?));
449    /// # Ok::<(), Box<dyn std::error::Error>>(())
450    /// ```
451    ///
452    /// # Errors
453    /// Required component size/normalization errors. A failed capability check
454    /// returns `None` rather than evaluating or refusing an unsupported provider.
455    pub fn concrete_element_stream(&self, ctx: Ctx) -> Result<Option<crate::SetElementStream>> {
456        crate::stream::concrete_raw(self, ctx)
457    }
458
459    /// Prepare a concrete powerset with typed, transactional integer positions.
460    /// Non-powersets or unknown component storage decline before consumption.
461    /// The required component size/normalization precedes its first empty value.
462    ///
463    /// # Errors
464    /// The same required component errors as [`Self::concrete_element_stream`].
465    pub fn concrete_subset_stream(&self, ctx: Ctx) -> Result<Option<crate::ConcreteSubsetStream>> {
466        crate::stream::concrete_subset(self, ctx)
467    }
468
469    /// The elements in normalized order, without changing TLC's view of the set
470    /// or of any set nested in it: [`Set::elements`] without its side effects.
471    ///
472    /// # Errors
473    /// As [`Set::elements`].
474    pub fn peek_elements(&self, ctx: Ctx) -> Result<Arc<[Value]>> {
475        self.quiet_elements(ctx)
476    }
477
478    /// The elements in normalized order, without changing TLC's view of the set or
479    /// of any set nested in it (issue #32): the operations TLC would perform to
480    /// normalize run with [`quiet::Quiet`] active, so they mark nothing.
481    pub(crate) fn quiet_elements(&self, ctx: Ctx) -> Result<Arc<[Value]>> {
482        if let Some(e) = self.0.elems.get() {
483            return Ok(e.clone());
484        }
485        let _quiet = quiet::Quiet::enter();
486        self.cached_elements(ctx)
487    }
488
489    /// Enumerates and normalizes the set, caching the result unless a mark was
490    /// suppressed while computing it. A suppressed mark means TLC's normalization
491    /// would have normalized a nested set; the cache must not skip that side effect
492    /// when a TLC operation later asks for the elements, so the result is
493    /// recomputed then.
494    fn cached_elements(&self, ctx: Ctx) -> Result<Arc<[Value]>> {
495        if let Some(e) = self.0.elems.get() {
496            return Ok(e.clone());
497        }
498        let before = quiet::suppressed();
499        let e: Arc<[Value]> = crate::enumerate::enumerate(self, ctx)?.into();
500        if quiet::suppressed() == before {
501            Ok(self.0.elems.get_or_init(|| e).clone())
502        } else {
503            Ok(e)
504        }
505    }
506
507    /// Whether TLC would treat the set as normalized (always, except for a `Raw` set
508    /// that no normalizing operation has touched). This reads representation only;
509    /// it neither enumerates nor changes the set. It is not a validation certificate.
510    #[must_use]
511    pub fn is_tlc_normalized(&self) -> bool {
512        match self.0.repr {
513            SetRepr::Raw(_) => self.0.tlc_norm.load(AtomicOrdering::Acquire),
514            _ => true,
515        }
516    }
517
518    /// Records that TLC would now treat the set as normalized.
519    pub(crate) fn mark_normalized(&self) {
520        if matches!(self.0.repr, SetRepr::Raw(_)) && !self.is_tlc_normalized() {
521            if quiet::active() {
522                quiet::note_suppressed();
523            } else {
524                self.0.tlc_norm.store(true, AtomicOrdering::Release);
525            }
526        }
527    }
528
529    /// The number of elements (TLC's `size()`, which normalizes).
530    ///
531    /// # Errors
532    /// As [`Set::elements`], plus TLC's size limits in [`IntMode::Tlc`](crate::IntMode).
533    pub fn size(&self, ctx: Ctx) -> Result<u64> {
534        crate::enumerate::size(self, ctx)
535    }
536
537    /// The order-independent hash (see [`Value::hash64`]).
538    #[must_use]
539    pub fn hash64(&self) -> u64 {
540        *self
541            .0
542            .hash
543            .get_or_init(|| crate::order::compute_set_hash(self))
544    }
545
546    pub(crate) fn repr(&self) -> &SetRepr {
547        &self.0.repr
548    }
549
550    /// The interval bounds, if this is `a..b`.
551    #[must_use]
552    pub fn as_interval(&self) -> Option<(&Int, &Int)> {
553        match &self.0.repr {
554            SetRepr::Interval(a, b) => Some((a, b)),
555            _ => None,
556        }
557    }
558
559    /// The domain and range, if this is `[S -> T]`.
560    #[must_use]
561    pub fn as_fcn_set(&self) -> Option<(&Value, &Value)> {
562        match &self.0.repr {
563            SetRepr::FcnSet(d, r) => Some((d, r)),
564            _ => None,
565        }
566    }
567
568    /// The fields and their sets, if this is `[a : S, ...]`, sorted in the set's
569    /// order (TLC's `SetOfRcdsValue.sortByNames` under [`ValueOrder::Tlc`]).
570    #[must_use]
571    pub fn as_rcd_set(&self) -> Option<&[(Atom, Value)]> {
572        match &self.0.repr {
573            SetRepr::RcdSet(f) => Some(f),
574            _ => None,
575        }
576    }
577
578    /// The factors, if this is `S1 \X ... \X Sn`.
579    #[must_use]
580    pub fn as_product(&self) -> Option<&[Value]> {
581        match &self.0.repr {
582            SetRepr::Product(f) => Some(f),
583            _ => None,
584        }
585    }
586
587    /// Whether two handles share the same allocation.
588    #[must_use]
589    pub fn ptr_eq(&self, other: &Self) -> bool {
590        Arc::ptr_eq(&self.0, &other.0)
591    }
592
593    /// The address of the shared allocation: while both handles are alive,
594    /// two handles have the same address exactly when they are
595    /// [`ptr_eq`](Self::ptr_eq).
596    #[must_use]
597    pub fn addr(&self) -> usize {
598        Arc::as_ptr(&self.0).addr()
599    }
600
601    /// The evaluator-driven source, if this is a deferred set.
602    #[must_use]
603    pub fn as_deferred(&self) -> Option<&Arc<dyn DeferredSet>> {
604        match &self.0.repr {
605            SetRepr::Deferred(d) => Some(d),
606            _ => None,
607        }
608    }
609
610    /// The components of a lazy set: the base of `SUBSET S` or `Seq(S)`, the domain
611    /// and range of `[S -> T]`, the factors of `S1 \X ... \X Sn`, or the field sets of
612    /// `[a : S, ...]` (with their names); empty for other kinds.
613    #[must_use]
614    pub fn components(&self) -> Vec<(Option<Atom>, Value)> {
615        match &self.0.repr {
616            SetRepr::Subset(b) | SetRepr::Seq(b) => vec![(None, b.clone())],
617            SetRepr::FcnSet(d, r) => vec![(None, d.clone()), (None, r.clone())],
618            SetRepr::Product(fs) => fs.iter().map(|f| (None, f.clone())).collect(),
619            SetRepr::RcdSet(fs) => fs
620                .iter()
621                .map(|(a, f)| (Some(a.clone()), f.clone()))
622                .collect(),
623            _ => Vec::new(),
624        }
625    }
626
627    /// The elements of an enumerated set as constructed, without normalizing it (TLC's
628    /// `SetEnumValue.elems` before `normalize()`), or `None` for other kinds or a set
629    /// TLC would already treat as normalized.
630    #[must_use]
631    pub fn raw_elements(&self) -> Option<&[Value]> {
632        match &self.0.repr {
633            SetRepr::Raw(e) if !self.is_tlc_normalized() => Some(e),
634            _ => None,
635        }
636    }
637}
638
639/// Quiet mode: while a [`quiet::Quiet`] guard is alive on this thread, operations
640/// that TLC performs with side effects (normalizing an unnormalized set) compute the
641/// same results without recording the side effect. `==`, [`Hash`] and `Debug` run
642/// quietly.
643pub(crate) mod quiet {
644    use std::cell::Cell;
645
646    thread_local! {
647        static DEPTH: Cell<u32> = const { Cell::new(0) };
648        static SUPPRESSED: Cell<u64> = const { Cell::new(0) };
649    }
650
651    /// Keeps quiet mode active on this thread until dropped.
652    pub(crate) struct Quiet(());
653
654    impl Quiet {
655        pub(crate) fn enter() -> Self {
656            DEPTH.with(|d| d.set(d.get().saturating_add(1)));
657            Self(())
658        }
659    }
660
661    impl Drop for Quiet {
662        fn drop(&mut self) {
663            DEPTH.with(|d| d.set(d.get().saturating_sub(1)));
664        }
665    }
666
667    pub(crate) fn active() -> bool {
668        DEPTH.with(Cell::get) > 0
669    }
670
671    /// The number of marks suppressed on this thread so far.
672    pub(crate) fn suppressed() -> u64 {
673        SUPPRESSED.with(Cell::get)
674    }
675
676    pub(crate) fn note_suppressed() {
677        SUPPRESSED.with(|s| s.set(s.get().wrapping_add(1)));
678    }
679}
680
681/// Whether this thread is normalizing a value without observable side effects.
682///
683/// Infallible equality, ordering and hashing can force deferred providers in
684/// this mode. A cooperative evaluator must defer host interruption until this
685/// unit returns: a transient interruption cannot stand in for a value or become
686/// a cached structural hash. Quiet mode records normalization observability,
687/// rather than whether an operation is infallible. Ordinary error propagation
688/// is unchanged; cooperative interruption is deferred for the entire quiet
689/// unit, including fallible peek work nested inside it.
690#[must_use]
691pub fn quiet_operation_active() -> bool {
692    quiet::active()
693}
694
695/// Sets with more elements than this hash by cardinality alone, so that hashing a
696/// huge lazy set (`0..2147483646`) is O(1). Equality still compares the elements.
697pub(crate) const HASH_ELEMENT_LIMIT: u128 = 1 << 16;
698
699/// The order-independent hash of a set with the given element hashes (consumed only
700/// when `len` is at most [`HASH_ELEMENT_LIMIT`]).
701pub(crate) fn set_hash(hashes: impl Iterator<Item = u64>, len: u128) -> u64 {
702    let sum = if len <= HASH_ELEMENT_LIMIT {
703        hashes.fold(0u64, |acc, h| acc.wrapping_add(mix64(h)))
704    } else {
705        0x9e37_79b9_7f4a_7c15
706    };
707    #[allow(clippy::cast_possible_truncation, reason = "hash mixing")]
708    mix2(K_SET ^ (len as u64), sum)
709}
710
711// ---------------------------------------------------------------------------------
712// Functions
713// ---------------------------------------------------------------------------------
714
715/// A finite function. Cloning is a reference-count increment.
716///
717/// The representation is canonical by domain, so equal functions have equal
718/// representations:
719/// - domain `1..n` (including the empty domain): a **tuple** (TLC `TupleValue`);
720/// - a non-empty domain of strings: a **record**, fields sorted;
721/// - any other domain: a **general** function (TLC `FcnRcdValue`), pairs sorted by
722///   domain element.
723///
724/// A record also remembers whether it is a record *literal* (TLC `RecordValue`: built
725/// by `[f |-> e]` or enumerated from `[f : S]`) or a function that happens to have a
726/// string domain (TLC `FcnRcdValue`: built by `:>`, `@@`, `[x \in S |-> e]` or
727/// enumerated from `[S -> T]`). TLC compares and prints the two differently; equality,
728/// hashing and fingerprints ignore the distinction.
729///
730/// Likewise a tuple remembers whether it is a tuple *literal* (TLC `TupleValue`: built
731/// by `<<...>>`, `Append`, `\o` and the other sequence operators, or enumerated from
732/// `S1 \X S2`) or a function with domain `1..n` built any other way (TLC
733/// `FcnRcdValue`: `[i \in 1..n |-> e]`, `:>`, `@@`, or an element of `[S -> T]`). TLC
734/// reports function-application errors and value kinds differently for the two
735/// ([`Fcn::is_tuple_literal`]); equality, hashing and fingerprints ignore it.
736#[derive(Clone)]
737pub struct Fcn(pub(crate) Arc<FcnInner>);
738
739pub(crate) struct FcnInner {
740    pub(crate) hash: u64,
741    /// Order, literal receiver class and sealed constructor/source-hook facts.
742    /// Replaces the old two bytes plus padding without growing the header.
743    pub(crate) metadata: crate::receiver::FunctionMetadata,
744    pub(crate) fp: crate::fp64::FpCache,
745    pub(crate) repr: FcnRepr,
746}
747
748pub(crate) enum FcnRepr {
749    Tuple(Box<[Value]>),
750    Record(Box<[(Atom, Value)]>),
751    General(GeneralFcn),
752}
753
754/// A conservative exact-domain lookup, without evaluating unknown keys.
755#[derive(Clone, Copy, Debug, PartialEq, Eq)]
756pub enum DomainLookup {
757    /// The original checked lookup is required.
758    Unknown,
759    /// Every possible comparison is error-free and the key is absent.
760    Missing,
761    /// The key is at this index in the function's stored range order.
762    Found(usize),
763}
764
765/// The shape of a function's domain.
766#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
767pub enum FcnKind {
768    /// Domain `1..n`, including the empty function.
769    Tuple,
770    /// A non-empty domain of strings.
771    Record,
772    /// Any other domain.
773    General,
774}
775
776fn fcn_hash<'a>(pairs: impl Iterator<Item = (u64, &'a Value)>, len: usize) -> u64 {
777    let sum = pairs.fold(0u64, |acc, (dh, v)| acc.wrapping_add(mix2(dh, v.hash64())));
778    mix2(K_FCN ^ (len as u64), sum)
779}
780
781impl Fcn {
782    pub(crate) fn tuple(elems: Vec<Value>) -> Self {
783        Self::tuple_as(elems, true)
784    }
785
786    /// A function with domain `1..n` that TLC keeps as a `FcnRcdValue`.
787    pub(crate) fn tuple_fcn(elems: Vec<Value>) -> Self {
788        Self::tuple_as(elems, false)
789    }
790
791    fn tuple_as(elems: Vec<Value>, literal: bool) -> Self {
792        Self::tuple_metadata(
793            elems,
794            crate::receiver::FunctionMetadata::new(ValueOrder::default(), literal),
795        )
796    }
797
798    pub(crate) fn tuple_metadata(
799        elems: Vec<Value>,
800        metadata: crate::receiver::FunctionMetadata,
801    ) -> Self {
802        let hash = fcn_hash(
803            elems
804                .iter()
805                .enumerate()
806                .map(|(i, v)| (int_hash(i64::try_from(i).unwrap_or(i64::MAX) + 1), v)),
807            elems.len(),
808        );
809        Self(Arc::new(FcnInner {
810            hash,
811            metadata,
812            fp: crate::fp64::FpCache::new(),
813            repr: FcnRepr::Tuple(elems.into_boxed_slice()),
814        }))
815    }
816
817    pub(crate) fn record(fields: Vec<(Atom, Value)>, order: ValueOrder, literal: bool) -> Self {
818        Self::record_metadata(
819            fields,
820            crate::receiver::FunctionMetadata::new(order, literal),
821        )
822    }
823
824    pub(crate) fn record_metadata(
825        fields: Vec<(Atom, Value)>,
826        metadata: crate::receiver::FunctionMetadata,
827    ) -> Self {
828        let hash = fcn_hash(
829            fields.iter().map(|(a, v)| (mix2(K_STR, a.text_hash()), v)),
830            fields.len(),
831        );
832        Self(Arc::new(FcnInner {
833            hash,
834            metadata,
835            fp: crate::fp64::FpCache::new(),
836            repr: FcnRepr::Record(fields.into_boxed_slice()),
837        }))
838    }
839
840    pub(crate) fn general(pairs: Vec<(Value, Value)>, order: ValueOrder) -> Self {
841        let hash = fcn_hash(pairs.iter().map(|(d, v)| (d.hash64(), v)), pairs.len());
842        Self(Arc::new(FcnInner {
843            hash,
844            metadata: crate::receiver::FunctionMetadata::new(order, false),
845            fp: crate::fp64::FpCache::new(),
846            repr: FcnRepr::General(GeneralFcn::new(pairs, order)),
847        }))
848    }
849
850    /// The domain's shape.
851    #[must_use]
852    pub fn kind(&self) -> FcnKind {
853        match &self.0.repr {
854            FcnRepr::Tuple(_) => FcnKind::Tuple,
855            FcnRepr::Record(_) => FcnKind::Record,
856            FcnRepr::General(_) => FcnKind::General,
857        }
858    }
859
860    /// Whether this is a record literal (TLC `RecordValue`), as opposed to a function
861    /// that has a string domain (see [`Fcn`]).
862    #[must_use]
863    pub fn is_record_literal(&self) -> bool {
864        self.0.metadata.literal() && matches!(self.0.repr, FcnRepr::Record(_))
865    }
866
867    /// Whether this is a tuple literal (TLC `TupleValue`), as opposed to a function
868    /// with domain `1..n` that TLC keeps as a `FcnRcdValue` (see [`Fcn`]).
869    #[must_use]
870    pub fn is_tuple_literal(&self) -> bool {
871        self.0.metadata.literal() && matches!(self.0.repr, FcnRepr::Tuple(_))
872    }
873
874    /// The order the fields or domain are sorted in.
875    #[must_use]
876    pub fn order(&self) -> ValueOrder {
877        self.0.metadata.order()
878    }
879
880    /// The number of domain elements.
881    #[must_use]
882    pub fn len(&self) -> usize {
883        match &self.0.repr {
884            FcnRepr::Tuple(e) => e.len(),
885            FcnRepr::Record(f) => f.len(),
886            FcnRepr::General(p) => p.len(),
887        }
888    }
889
890    /// Whether the domain is empty (the function `<<>>`).
891    #[must_use]
892    pub fn is_empty(&self) -> bool {
893        self.len() == 0
894    }
895
896    /// The elements, if the function is a tuple (domain `1..n`).
897    #[must_use]
898    pub fn as_tuple(&self) -> Option<&[Value]> {
899        match &self.0.repr {
900            FcnRepr::Tuple(e) => Some(e),
901            _ => None,
902        }
903    }
904
905    /// The fields in order, if the function is a record.
906    #[must_use]
907    pub fn as_record(&self) -> Option<&[(Atom, Value)]> {
908        match &self.0.repr {
909            FcnRepr::Record(f) => Some(f),
910            _ => None,
911        }
912    }
913
914    /// The `i`-th domain element and its value, in normalized domain order.
915    #[must_use]
916    pub fn entry(&self, i: usize) -> Option<(Value, &Value)> {
917        match &self.0.repr {
918            FcnRepr::Tuple(e) => e
919                .get(i)
920                .map(|v| (Value::Int(i64::try_from(i).unwrap_or(i64::MAX) + 1), v)),
921            FcnRepr::Record(f) => f.get(i).map(|(a, v)| (Value::Str(a.clone()), v)),
922            FcnRepr::General(p) => p.get(i).map(|(d, v)| (d.clone(), v)),
923        }
924    }
925
926    /// The `i`-th entry, borrowing stored keys where possible.
927    #[must_use]
928    pub fn entry_cow(&self, i: usize) -> Option<(std::borrow::Cow<'_, Value>, &Value)> {
929        match &self.0.repr {
930            FcnRepr::General(p) => p.get(i).map(|(d, v)| (std::borrow::Cow::Borrowed(d), v)),
931            _ => self.entry(i).map(|(d, v)| (std::borrow::Cow::Owned(d), v)),
932        }
933    }
934
935    /// An exact index or miss for eager integer/Cartesian domains. `Unknown` means
936    /// the argument requires the caller's original checked comparison path.
937    ///
938    /// ```
939    /// use dive_value::{Ctx, DomainLookup, Value};
940    /// let Value::Fcn(f) = Value::fcn(
941    ///     vec![(Value::Int(0), Value::TRUE), (Value::Int(1), Value::FALSE)],
942    ///     Ctx::dive(),
943    /// )? else { unreachable!() };
944    /// assert_eq!(f.checked_domain_index(&Value::Int(1)), DomainLookup::Found(1));
945    /// assert_eq!(f.checked_domain_index(&Value::Int(4)), DomainLookup::Missing);
946    /// assert_eq!(f.checked_domain_index(&Value::TRUE), DomainLookup::Unknown);
947    /// # Ok::<(), dive_value::ValueError>(())
948    /// ```
949    #[must_use]
950    pub fn checked_domain_index(&self, argument: &Value) -> DomainLookup {
951        match &self.0.repr {
952            FcnRepr::General(p) => p.domain.checked_index(argument),
953            _ => DomainLookup::Unknown,
954        }
955    }
956
957    /// Cached TLC key positions for a proven provider-free general domain.
958    /// This implementation view does not mark the function TLC-normalized.
959    #[must_use]
960    pub fn tlc_domain_indices(&self) -> Option<&[usize]> {
961        match &self.0.repr {
962            FcnRepr::General(p) => p.domain.tlc_order(),
963            _ => None,
964        }
965    }
966
967    /// Iterates over `(domain element, value)` in normalized domain order.
968    pub fn iter(&self) -> impl Iterator<Item = (Value, &Value)> + '_ {
969        (0..self.len()).filter_map(move |i| self.entry(i))
970    }
971
972    /// Iterates over the values in normalized domain order, without building
973    /// the domain elements.
974    pub fn values(&self) -> impl Iterator<Item = &Value> + '_ {
975        let (tuple, record, general) = match &self.0.repr {
976            FcnRepr::Tuple(e) => (Some(e.iter()), None, None),
977            FcnRepr::Record(f) => (None, Some(f.iter().map(|(_, v)| v)), None),
978            FcnRepr::General(p) => (None, None, Some(p.iter().map(|(_, v)| v))),
979        };
980        tuple
981            .into_iter()
982            .flatten()
983            .chain(record.into_iter().flatten())
984            .chain(general.into_iter().flatten())
985    }
986
987    /// Applies the function to `arg`, returning `None` when `arg` is not in the domain.
988    #[must_use]
989    pub fn apply(&self, arg: &Value) -> Option<&Value> {
990        match (&self.0.repr, arg) {
991            (FcnRepr::Tuple(e), Value::Int(i)) => i
992                .checked_sub(1)
993                .and_then(|i| usize::try_from(i).ok())
994                .and_then(|i| e.get(i)),
995            (FcnRepr::Record(f), Value::Str(a)) => f.iter().find(|(n, _)| n == a).map(|(_, v)| v),
996            (FcnRepr::General(p), _) => match p.domain.checked_index(arg) {
997                DomainLookup::Found(index) => p.values.get(index),
998                DomainLookup::Missing => None,
999                DomainLookup::Unknown => p.iter().find(|(d, _)| *d == arg).map(|(_, v)| v),
1000            },
1001            _ => None,
1002        }
1003    }
1004
1005    /// Replaces one range value while preserving an already canonical domain.
1006    /// Returns `new` unchanged when rebuilding in `ctx` might normalize keys or
1007    /// change the function's representation; callers then use their original path.
1008    ///
1009    /// # Errors
1010    /// Returns the proposed value for an invalid index or an unproved domain.
1011    pub fn with_value_at(
1012        &self,
1013        i: usize,
1014        new: Value,
1015        ctx: Ctx,
1016    ) -> std::result::Result<Self, Value> {
1017        if i >= self.len() {
1018            return Err(new);
1019        }
1020        match &self.0.repr {
1021            FcnRepr::Tuple(values) => {
1022                let mut values = values.to_vec();
1023                values[i] = new;
1024                Ok(Self::tuple_as(values, self.0.metadata.literal()))
1025            }
1026            FcnRepr::Record(fields) => {
1027                if self.order() != ctx.order {
1028                    return Err(new);
1029                }
1030                let mut fields = fields.to_vec();
1031                fields[i].1 = new;
1032                Ok(Self::record(
1033                    fields,
1034                    self.order(),
1035                    self.0.metadata.literal(),
1036                ))
1037            }
1038            FcnRepr::General(general) => {
1039                if self.order() != ctx.order || !general.domain.canonical() {
1040                    return Err(new);
1041                }
1042                let mut values = general.values.to_vec();
1043                values[i] = new;
1044                let hash = fcn_hash(
1045                    general
1046                        .domain
1047                        .keys
1048                        .iter()
1049                        .zip(&values)
1050                        .map(|(d, v)| (d.hash64(), v)),
1051                    values.len(),
1052                );
1053                Ok(Self(Arc::new(FcnInner {
1054                    hash,
1055                    metadata: crate::receiver::FunctionMetadata::new(
1056                        self.order(),
1057                        self.0.metadata.literal(),
1058                    ),
1059                    fp: crate::fp64::FpCache::new(),
1060                    repr: FcnRepr::General(GeneralFcn {
1061                        domain: Arc::clone(&general.domain),
1062                        values: values.into_boxed_slice(),
1063                    }),
1064                })))
1065            }
1066        }
1067    }
1068
1069    pub(crate) fn exact_domain_equals(&self, set: &Set) -> Option<bool> {
1070        match &self.0.repr {
1071            FcnRepr::General(general) => general.domain.matches_set(set),
1072            _ => None,
1073        }
1074    }
1075
1076    /// Whether two handles share the same allocation.
1077    #[must_use]
1078    pub fn ptr_eq(&self, other: &Self) -> bool {
1079        Arc::ptr_eq(&self.0, &other.0)
1080    }
1081
1082    /// The address of the shared allocation: while both handles are alive,
1083    /// two handles have the same address exactly when they are
1084    /// [`ptr_eq`](Self::ptr_eq).
1085    #[must_use]
1086    pub fn addr(&self) -> usize {
1087        Arc::as_ptr(&self.0).addr()
1088    }
1089}
1090
1091// ---------------------------------------------------------------------------------
1092// Iterative drop
1093// ---------------------------------------------------------------------------------
1094
1095/// Queues a child that would be freed with its parent; drops any other child
1096/// (a scalar, or a compound value shared elsewhere) in place, in O(1).
1097fn queue(out: &mut Vec<Value>, v: Value) {
1098    if frees_compound(&v) {
1099        out.push(v);
1100    }
1101}
1102
1103impl SetInner {
1104    fn take_children(&mut self, out: &mut Vec<Value>) {
1105        match std::mem::replace(&mut self.repr, SetRepr::Enum) {
1106            SetRepr::Raw(e) | SetRepr::Product(e) => {
1107                for v in e {
1108                    queue(out, v);
1109                }
1110            }
1111            SetRepr::Subset(v) | SetRepr::Seq(v) => queue(out, v),
1112            SetRepr::FcnSet(d, r) => {
1113                queue(out, d);
1114                queue(out, r);
1115            }
1116            SetRepr::RcdSet(fs) => {
1117                for (_, v) in fs {
1118                    queue(out, v);
1119                }
1120            }
1121            other => self.repr = other,
1122        }
1123        if let Some(mut e) = self.elems.take()
1124            && let Some(slice) = Arc::get_mut(&mut e)
1125        {
1126            for v in slice.iter_mut() {
1127                queue(out, std::mem::replace(v, Value::FALSE));
1128            }
1129        }
1130    }
1131}
1132
1133impl FcnInner {
1134    fn take_children(&mut self, out: &mut Vec<Value>) {
1135        match std::mem::replace(&mut self.repr, FcnRepr::Tuple(Box::default())) {
1136            FcnRepr::Tuple(e) => {
1137                for v in e {
1138                    queue(out, v);
1139                }
1140            }
1141            FcnRepr::Record(fs) => {
1142                for (_, v) in fs {
1143                    queue(out, v);
1144                }
1145            }
1146            FcnRepr::General(mut ps) => {
1147                for v in std::mem::take(&mut ps.values) {
1148                    queue(out, v);
1149                }
1150                if let Some(domain) = Arc::get_mut(&mut ps.domain) {
1151                    domain.take_children(out);
1152                }
1153            }
1154        }
1155    }
1156}
1157
1158/// Drops values without recursion: each uniquely owned compound value is emptied
1159/// into a work list before it is freed.
1160fn drain(mut stack: Vec<Value>) {
1161    while let Some(v) = stack.pop() {
1162        match v {
1163            Value::Set(mut s) => {
1164                if let Some(inner) = Arc::get_mut(&mut s.0) {
1165                    inner.take_children(&mut stack);
1166                }
1167            }
1168            Value::Fcn(mut f) => {
1169                if let Some(inner) = Arc::get_mut(&mut f.0) {
1170                    inner.take_children(&mut stack);
1171                }
1172            }
1173            _ => {}
1174        }
1175    }
1176}
1177
1178/// Whether dropping this handle would free a compound value, which the iterative
1179/// drop must then take apart. Scalars and shared compound values drop in O(1)
1180/// without recursion.
1181fn frees_compound(v: &Value) -> bool {
1182    match v {
1183        Value::Set(s) => Arc::strong_count(&s.0) == 1,
1184        Value::Fcn(f) => Arc::strong_count(&f.0) == 1,
1185        _ => false,
1186    }
1187}
1188
1189impl SetInner {
1190    /// Whether any child this set owns would be freed with it (see
1191    /// [`frees_compound`]).
1192    fn frees_compound_child(&self) -> bool {
1193        let in_repr = match &self.repr {
1194            SetRepr::Raw(e) | SetRepr::Product(e) => e.iter().any(frees_compound),
1195            SetRepr::Subset(v) | SetRepr::Seq(v) => frees_compound(v),
1196            SetRepr::FcnSet(d, r) => frees_compound(d) || frees_compound(r),
1197            SetRepr::RcdSet(fs) => fs.iter().any(|(_, v)| frees_compound(v)),
1198            _ => false,
1199        };
1200        in_repr
1201            || self
1202                .elems
1203                .get()
1204                .is_some_and(|e| Arc::strong_count(e) == 1 && e.iter().any(frees_compound))
1205    }
1206}
1207
1208impl FcnInner {
1209    /// Whether any child this function owns would be freed with it (see
1210    /// [`frees_compound`]).
1211    fn frees_compound_child(&self) -> bool {
1212        match &self.repr {
1213            FcnRepr::Tuple(e) => e.iter().any(frees_compound),
1214            FcnRepr::Record(fs) => fs.iter().any(|(_, v)| frees_compound(v)),
1215            FcnRepr::General(ps) => {
1216                ps.values.iter().any(frees_compound)
1217                    || (Arc::strong_count(&ps.domain) == 1
1218                        && ps.domain.keys.iter().any(frees_compound))
1219            }
1220        }
1221    }
1222}
1223
1224// Dropping is iterative only where it must be. A value whose children would
1225// all survive it (scalars, or compound values shared elsewhere) drops its
1226// children in place. Otherwise the first `NATIVE_DROP_DEPTH` nested levels
1227// are freed by native recursion, and deeper ones through a work list, so
1228// nesting depth never becomes unbounded recursion depth. A child whose last
1229// other owner drops it concurrently is freed by that child's own `Drop`,
1230// which applies the same rules.
1231/// How many compound values one thread frees by native recursion before it
1232/// switches to the work list. Small enough that the recursion is cheap on any
1233/// worker stack; deep enough that ordinary values never need the work list.
1234const NATIVE_DROP_DEPTH: u32 = 32;
1235
1236std::thread_local! {
1237    static DROP_DEPTH: std::cell::Cell<u32> = const { std::cell::Cell::new(0) };
1238}
1239
1240/// A level of bounded native recursion while dropping (see
1241/// [`NATIVE_DROP_DEPTH`]); none is available beyond the bound.
1242struct NativeDrop;
1243
1244impl NativeDrop {
1245    fn enter() -> Option<Self> {
1246        let depth = DROP_DEPTH.get();
1247        (depth < NATIVE_DROP_DEPTH).then(|| {
1248            DROP_DEPTH.set(depth + 1);
1249            Self
1250        })
1251    }
1252}
1253
1254impl Drop for NativeDrop {
1255    fn drop(&mut self) {
1256        DROP_DEPTH.set(DROP_DEPTH.get().saturating_sub(1));
1257    }
1258}
1259
1260impl Drop for SetInner {
1261    fn drop(&mut self) {
1262        if !self.frees_compound_child() {
1263            return;
1264        }
1265        if let Some(_level) = NativeDrop::enter() {
1266            drop(std::mem::replace(&mut self.repr, SetRepr::Enum));
1267            drop(self.elems.take());
1268            return;
1269        }
1270        let mut stack = Vec::new();
1271        self.take_children(&mut stack);
1272        drain(stack);
1273    }
1274}
1275
1276impl DomainInner {
1277    fn take_children(&mut self, out: &mut Vec<Value>) {
1278        for key in std::mem::take(&mut self.keys) {
1279            queue(out, key);
1280        }
1281    }
1282}
1283
1284impl Drop for DomainInner {
1285    fn drop(&mut self) {
1286        if !self.keys.iter().any(frees_compound) {
1287            return;
1288        }
1289        if let Some(_level) = NativeDrop::enter() {
1290            drop(std::mem::take(&mut self.keys));
1291            return;
1292        }
1293        let mut stack = Vec::new();
1294        self.take_children(&mut stack);
1295        drain(stack);
1296    }
1297}
1298
1299impl Drop for FcnInner {
1300    fn drop(&mut self) {
1301        if !self.frees_compound_child() {
1302            return;
1303        }
1304        if let Some(_level) = NativeDrop::enter() {
1305            drop(std::mem::replace(
1306                &mut self.repr,
1307                FcnRepr::Tuple(Box::default()),
1308            ));
1309            return;
1310        }
1311        let mut stack = Vec::new();
1312        self.take_children(&mut stack);
1313        drain(stack);
1314    }
1315}
1316
1317// ---------------------------------------------------------------------------------
1318// Constructors
1319// ---------------------------------------------------------------------------------
1320
1321impl Value {
1322    /// A string, interned in `names`.
1323    #[must_use]
1324    pub fn string(names: &crate::Interner, text: &str) -> Self {
1325        Self::Str(names.intern(text))
1326    }
1327
1328    /// A model value, interned in `names`.
1329    #[must_use]
1330    pub fn model(names: &crate::Interner, name: &str) -> Self {
1331        Self::Model(names.intern(name))
1332    }
1333
1334    /// A normalized set of `elems`.
1335    ///
1336    /// Normalization applies TLC's comparability rules: `{1, "a"}` is an error, with
1337    /// the message TLC gives (`Attempted to compare string "a" with non-string:\n1`).
1338    /// Whether an error occurs is decided exactly as TLC decides it, by TLC's
1339    /// insertion sort in TLC's name order, in both [`ValueOrder`]s (with names interned
1340    /// in TLC's order); the result is then sorted in `ctx.order`.
1341    ///
1342    /// When elements are equal but differently represented (`1..3` and `{1, 2, 3}`),
1343    /// the first one is kept, as in TLC.
1344    ///
1345    /// # Errors
1346    /// [`ErrorKind::Incomparable`] and friends, as in TLC.
1347    pub fn set(elems: Vec<Self>, ctx: Ctx) -> Result<Self> {
1348        crate::order::normalize_set(elems, ctx).map(|s| Self::Set(Set::from_sorted(ctx.order, s)))
1349    }
1350
1351    /// Constructs a mathematical finite set in canonical value order.
1352    ///
1353    /// Unlike [`Self::set`], construction accepts mixed value shapes without
1354    /// reproducing TLC's partial sorting comparisons. This does not
1355    /// change the semantics of direct scalar comparisons.
1356    ///
1357    /// ```
1358    /// use dive_value::{Ctx, Value};
1359    /// let ctx = Ctx::dive();
1360    /// let a = Value::set_canonical(vec![Value::Int(1), Value::TRUE], ctx)?;
1361    /// let b = Value::set_canonical(vec![Value::TRUE, Value::Int(1), Value::TRUE], ctx)?;
1362    /// assert_eq!(a, b);
1363    /// # Ok::<(), dive_value::ValueError>(())
1364    /// ```
1365    ///
1366    /// # Errors
1367    /// A symbolic child whose mathematical identity is not established, including
1368    /// inside a singleton, nested set, function key or function value, or allocation failure.
1369    pub fn set_canonical(elems: Vec<Self>, ctx: Ctx) -> Result<Self> {
1370        crate::construction::canonical_set(elems, ctx, &mut || true).map_err(|error| match error {
1371            crate::ConstructionError::Value(error) => error,
1372            other => ValueError::new(ErrorKind::DiveLimit, other.to_string()),
1373        })
1374    }
1375
1376    /// Requires a complete explicit finite value tree, including raw set storage.
1377    ///
1378    /// Stored name order need not match `ctx`; this inspection does not sort or
1379    /// normalize values and never invokes a symbolic provider.
1380    ///
1381    /// Symbolic definitions are not mathematical inequality certificates.
1382    /// This checks singleton/nested sets and all function keys and values without
1383    /// enumerating a symbolic domain.
1384    ///
1385    /// ```
1386    /// use dive_value::{Ctx, Value};
1387    /// Value::Int(1).require_materialized(Ctx::dive())?;
1388    /// # Ok::<(), dive_value::ValueError>(())
1389    /// ```
1390    ///
1391    /// # Errors
1392    /// An unsupported symbolic child, or temporary allocation failure.
1393    pub fn require_materialized(&self, ctx: Ctx) -> Result<()> {
1394        crate::construction::require_closed(self, ctx, &mut || true).map_err(|error| match error {
1395            crate::ConstructionError::Value(error) => error,
1396            other => ValueError::new(ErrorKind::DiveLimit, other.to_string()),
1397        })
1398    }
1399
1400    /// Produces a materialized operand for quiet extensional equality.
1401    ///
1402    /// Explicit and deferred results are checked recursively. Symbolic operator
1403    /// definitions are refused rather than compared structurally. As with value
1404    /// equality and hashing, provider evaluation here does not invoke host control.
1405    ///
1406    /// # Errors
1407    /// Provider evaluation errors, unsupported identity, or allocation failure.
1408    pub fn materialized_for_equality(&self, ctx: Ctx) -> Result<Self> {
1409        let _quiet = quiet::Quiet::enter();
1410        self.materialized_identity(ctx)
1411    }
1412
1413    /// Materializes explicit/deferred children for an identity-demanding operation.
1414    ///
1415    /// Provider evaluation retains its normal controls. Symbolic operator
1416    /// definitions whose identity is unproved remain unsupported.
1417    ///
1418    /// # Errors
1419    /// Provider evaluation errors, unsupported identity, or allocation failure.
1420    pub fn materialized_identity(&self, ctx: Ctx) -> Result<Self> {
1421        crate::construction::materialized_identity(self, ctx, &mut || true, 0).map_err(|error| {
1422            match error {
1423                crate::ConstructionError::Value(error) => error,
1424                other => ValueError::new(ErrorKind::DiveLimit, other.to_string()),
1425            }
1426        })
1427    }
1428
1429    /// Constructs an explicit set with cooperative normalization checkpoints.
1430    ///
1431    /// `proceed` returns false to interrupt. Closed materialized values use
1432    /// checked comparison, sorting and fallible temporary storage. Symbolic
1433    /// children keep the uncontrolled constructor, whose enumeration is not yet
1434    /// cooperative. Final shared-value allocations retain Rust's allocation
1435    /// behavior; this is not an allocation-time memory ceiling.
1436    ///
1437    /// # Errors
1438    /// The original value error, interruption, or temporary allocation failure.
1439    ///
1440    /// ```
1441    /// use dive_value::{ConstructionError, Ctx, Value};
1442    /// let result = Value::set_controlled(vec![Value::Int(1)], Ctx::tlc(), &mut || false);
1443    /// assert!(matches!(result, Err(ConstructionError::Interrupted)));
1444    /// ```
1445    pub fn set_controlled(
1446        elems: Vec<Self>,
1447        ctx: Ctx,
1448        proceed: &mut dyn FnMut() -> bool,
1449    ) -> Result<Self, crate::ConstructionError> {
1450        for value in &elems {
1451            if !crate::construction::closed(value, ctx, proceed)? {
1452                return Self::set(elems, ctx).map_err(Into::into);
1453            }
1454        }
1455        crate::construction::set(elems, ctx, proceed)
1456    }
1457
1458    /// A set exactly as TLC builds a set enumeration `{e1, ..., en}`: unnormalized
1459    /// until TLC would normalize it. Membership tests scan the elements with TLC's
1460    /// equality, so `1 \in {1, "a"}` is `TRUE` while `{1, "a"} = {}` is an error, as in
1461    /// TLC.
1462    #[must_use]
1463    pub fn set_raw(elems: Vec<Self>, ctx: Ctx) -> Self {
1464        if elems.is_empty() {
1465            return Self::Set(Set::from_sorted(ctx.order, elems));
1466        }
1467        Self::Set(Set::new(ctx.order, SetRepr::Raw(elems.into_boxed_slice())))
1468    }
1469
1470    /// The empty set.
1471    #[must_use]
1472    pub fn empty_set(ctx: Ctx) -> Self {
1473        Self::Set(Set::from_sorted(ctx.order, Vec::new()))
1474    }
1475
1476    /// The interval `lo..hi` (empty when `hi < lo`).
1477    #[must_use]
1478    pub fn interval(lo: Int, hi: Int, ctx: Ctx) -> Self {
1479        Self::Set(Set::new(ctx.order, SetRepr::Interval(lo, hi)))
1480    }
1481
1482    /// `SUBSET base`.
1483    #[must_use]
1484    pub fn subset(base: Self, ctx: Ctx) -> Self {
1485        Self::Set(Set::new(ctx.order, SetRepr::Subset(base)))
1486    }
1487
1488    /// `[domain -> range]`.
1489    #[must_use]
1490    pub fn fcn_set(domain: Self, range: Self, ctx: Ctx) -> Self {
1491        Self::Set(Set::new(ctx.order, SetRepr::FcnSet(domain, range)))
1492    }
1493
1494    /// `[f1 : S1, ..., fn : Sn]`.
1495    ///
1496    /// # Errors
1497    /// [`ErrorKind::Duplicate`] when a field repeats.
1498    pub fn record_set(fields: Vec<(Atom, Self)>, ctx: Ctx) -> Result<Self> {
1499        let fields = sort_fields(fields, ctx.order)?;
1500        Ok(Self::Set(Set::new(
1501            ctx.order,
1502            SetRepr::RcdSet(fields.into_boxed_slice()),
1503        )))
1504    }
1505
1506    /// `S1 \X ... \X Sn` (`n >= 2` in TLA+ syntax; any `n` is accepted).
1507    #[must_use]
1508    pub fn product(factors: Vec<Self>, ctx: Ctx) -> Self {
1509        Self::Set(Set::new(
1510            ctx.order,
1511            SetRepr::Product(factors.into_boxed_slice()),
1512        ))
1513    }
1514
1515    /// `Nat`.
1516    #[must_use]
1517    pub fn nat(ctx: Ctx) -> Self {
1518        Self::Set(Set::new(ctx.order, SetRepr::Nat))
1519    }
1520
1521    /// `Int`.
1522    #[must_use]
1523    pub fn int_set(ctx: Ctx) -> Self {
1524        Self::Set(Set::new(ctx.order, SetRepr::Int))
1525    }
1526
1527    /// `STRING`.
1528    #[must_use]
1529    pub fn string_set(ctx: Ctx) -> Self {
1530        Self::Set(Set::new(ctx.order, SetRepr::Strings))
1531    }
1532
1533    /// `Seq(range)`.
1534    #[must_use]
1535    pub fn seq_set(range: Self, ctx: Ctx) -> Self {
1536        Self::Set(Set::new(ctx.order, SetRepr::Seq(range)))
1537    }
1538
1539    /// `BOOLEAN`, which TLC represents as the enumerated set `{FALSE, TRUE}`.
1540    #[must_use]
1541    pub fn boolean_set(ctx: Ctx) -> Self {
1542        Self::Set(Set::from_sorted(ctx.order, vec![Self::FALSE, Self::TRUE]))
1543    }
1544
1545    /// An evaluator-driven lazy set (`{x \in S : P}` or `{e : x \in S}`).
1546    #[must_use]
1547    pub fn deferred(source: Arc<dyn DeferredSet>, ctx: Ctx) -> Self {
1548        Self::Set(Set::new(ctx.order, SetRepr::Deferred(source)))
1549    }
1550
1551    /// The tuple (sequence) `<<e1, ..., en>>` (TLC `TupleValue`).
1552    #[must_use]
1553    pub fn tuple(elems: Vec<Self>) -> Self {
1554        Self::Fcn(Fcn::tuple(elems))
1555    }
1556
1557    /// The function with domain `1..n` mapping `i` to `elems[i - 1]`, as TLC builds it
1558    /// from `[i \in 1..n |-> e]` (a `FcnRcdValue`, not a `TupleValue`; see [`Fcn`]).
1559    /// Equal to [`Value::tuple`] of the same elements.
1560    #[must_use]
1561    pub fn tuple_fcn(elems: Vec<Self>) -> Self {
1562        Self::Fcn(Fcn::tuple_fcn(elems))
1563    }
1564
1565    /// The record literal `[f1 |-> v1, ..., fn |-> vn]` (TLC `RecordValue`). With no
1566    /// fields this is the empty function `<<>>`.
1567    ///
1568    /// # Errors
1569    /// [`ErrorKind::Duplicate`] when a field repeats (TLC: `Field name f occurs
1570    /// multiple times in record.`).
1571    pub fn record(fields: Vec<(Atom, Self)>, ctx: Ctx) -> Result<Self> {
1572        if fields.is_empty() {
1573            return Ok(Self::tuple(Vec::new()));
1574        }
1575        Ok(Self::Fcn(Fcn::record(
1576            sort_fields(fields, ctx.order)?,
1577            ctx.order,
1578            true,
1579        )))
1580    }
1581
1582    /// The function with the given `(argument, value)` pairs (TLC `FcnRcdValue`, as
1583    /// built by `:>`, `@@` or `[x \in S |-> e]`), in canonical form (see [`Fcn`]). The
1584    /// domain is normalized with TLC's comparability rules.
1585    ///
1586    /// # Errors
1587    /// Comparison errors from normalizing the domain, and [`ErrorKind::Duplicate`]
1588    /// when an argument repeats (TLC: `The value\nd\noccurs multiple times in the
1589    /// function domain.`).
1590    pub fn fcn(pairs: Vec<(Self, Self)>, ctx: Ctx) -> Result<Self> {
1591        crate::order::make_fcn(pairs, ctx)
1592    }
1593
1594    /// Constructs a function with the controls and symbolic fallback
1595    /// described by [`Self::set_controlled`].
1596    ///
1597    /// # Errors
1598    /// The original domain error, interruption, or temporary allocation failure.
1599    pub fn fcn_controlled(
1600        pairs: Vec<(Self, Self)>,
1601        ctx: Ctx,
1602        proceed: &mut dyn FnMut() -> bool,
1603    ) -> Result<Self, crate::ConstructionError> {
1604        for (key, value) in &pairs {
1605            if !crate::construction::closed(key, ctx, proceed)?
1606                || !crate::construction::closed(value, ctx, proceed)?
1607            {
1608                return Self::fcn(pairs, ctx).map_err(Into::into);
1609            }
1610        }
1611        crate::construction::fcn(pairs, ctx, proceed)
1612    }
1613
1614    /// Constructs a record with cooperative field sorting and fallible scratch
1615    /// storage. Final shared storage retains Rust's allocation behavior.
1616    ///
1617    /// # Errors
1618    /// The original duplicate-field error, interruption, or scratch allocation
1619    /// failure.
1620    pub fn record_controlled(
1621        fields: Vec<(Atom, Self)>,
1622        ctx: Ctx,
1623        proceed: &mut dyn FnMut() -> bool,
1624    ) -> Result<Self, crate::ConstructionError> {
1625        crate::construction::record(fields, ctx, proceed)
1626    }
1627}
1628
1629pub(crate) fn sort_fields(
1630    mut fields: Vec<(Atom, Value)>,
1631    order: ValueOrder,
1632) -> Result<Vec<(Atom, Value)>> {
1633    fields.sort_by(|a, b| a.0.cmp_with(&b.0, order));
1634    for w in fields.windows(2) {
1635        if w[0].0 == w[1].0 {
1636            return Err(ValueError::new(
1637                ErrorKind::Duplicate,
1638                format!("Field name {} occurs multiple times in record.", w[1].0),
1639            ));
1640        }
1641    }
1642    Ok(fields)
1643}