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}