Skip to main content

dive_value/
order.rs

1//! Equality, the total order, hashing of sets, and normalization.
2//!
3//! # Equality and the order
4//!
5//! `impl PartialEq for Value` and [`Value::cmp_with`] are total and consistent:
6//! `a.cmp_with(b, o) == Equal` iff `a == b`, and equal values hash equally. Both are
7//! iterative, so any nesting depth is safe, and neither changes anything TLC can
8//! observe (unnormalized sets stay unnormalized).
9//!
10//! Sets fall in three classes:
11//! - **intervals**, compared by their bounds where possible;
12//! - **finite** sets of at most [`MAX_ENUMERATION`] elements (enumerated sets, lazy
13//!   sets of known size, normalizable set literals), compared by cardinality and then
14//!   element by element in normalized order, streaming lazy sets rather than
15//!   materializing them;
16//! - **structural** sets (infinite, too large, or unenumerable, such as a literal
17//!   `{1, "a"}` that TLC cannot normalize), compared by their definition.
18//!
19//! # Normalization and TLC's errors
20//!
21//! TLC sorts a set with a binary insertion sort (`ValueVec.sort`) and raises an error
22//! when it compares two incomparable values. Whether it raises one depends on which
23//! pairs the sort happens to compare. dive reproduces this exactly: when every pair of
24//! elements is provably comparable (a cheap structural "shape" join), dive uses a fast
25//! stable sort, which gives TLC's result; otherwise it runs TLC's insertion sort with
26//! TLC's strict comparison, in TLC's name order, which gives TLC's result or TLC's
27//! error, and then sorts the result in the run's order.
28
29#![allow(
30    clippy::many_single_char_names,
31    reason = "ports keep short operand names (a, b, s, t, x, y)"
32)]
33
34use std::cmp::Ordering;
35
36use crate::atom::Atom;
37use crate::ctx::{Ctx, IntMode, ValueOrder};
38use crate::enumerate::{MAX_ENUMERATION, quiet_size};
39use crate::error::{ErrorKind, Result, ValueError};
40use crate::stream::{Elems, slice_stream, stream};
41use crate::value::{Fcn, FcnRepr, HASH_ELEMENT_LIMIT, K_SET, Set, SetRepr, Value, mix2, set_hash};
42
43fn quiet_ctx(order: ValueOrder) -> Ctx {
44    Ctx {
45        int_mode: IntMode::Big,
46        order,
47    }
48}
49
50// ---------------------------------------------------------------------------------
51// Set classes
52// ---------------------------------------------------------------------------------
53
54#[derive(Clone, Copy, PartialEq, Eq)]
55enum Class {
56    Interval,
57    Finite,
58    Structural,
59}
60
61fn class(s: &Set) -> Class {
62    match s.repr() {
63        SetRepr::Interval(..) => Class::Interval,
64        SetRepr::Enum => Class::Finite,
65        SetRepr::Nat | SetRepr::Int | SetRepr::Strings => Class::Structural,
66        _ => match quiet_size(s) {
67            Some(n) if n <= u128::from(MAX_ENUMERATION) => Class::Finite,
68            _ => Class::Structural,
69        },
70    }
71}
72
73/// The elements of a finite set in `order`, streamed (or materialized and re-sorted
74/// if the set was built in another order). Changes nothing observable.
75fn quiet_stream(s: &Set, order: ValueOrder) -> Option<Elems> {
76    if s.order() == order {
77        return stream(s, quiet_ctx(order), false).ok();
78    }
79    let mut v: Vec<Value> = stream(s, quiet_ctx(s.order()), false).ok()?.collect();
80    v.sort_by(|a, b| total_cmp(a, b, order));
81    Some(slice_stream(v.into()))
82}
83
84fn interval_empty(s: &Set) -> bool {
85    s.as_interval().is_some_and(|(lo, hi)| hi < lo)
86}
87
88/// The set's hash (see [`Value::hash64`]).
89pub(crate) fn compute_set_hash(s: &Set) -> u64 {
90    match class(s) {
91        Class::Interval | Class::Finite => match quiet_size(s) {
92            Some(n) if n > HASH_ELEMENT_LIMIT => set_hash(std::iter::empty(), n),
93            Some(n) => match stream(s, quiet_ctx(s.order()), false) {
94                Ok(e) => set_hash(e.map(|v| v.hash64()), n),
95                Err(_) => structural_hash(s),
96            },
97            None => structural_hash(s),
98        },
99        Class::Structural => structural_hash(s),
100    }
101}
102
103fn structural_hash(s: &Set) -> u64 {
104    let seq = |init: u64, vals: &mut dyn Iterator<Item = &Value>| {
105        vals.fold(init, |h, v| mix2(h, v.hash64()))
106    };
107    let h = match s.repr() {
108        SetRepr::Nat => 1,
109        SetRepr::Int => 2,
110        SetRepr::Strings => 3,
111        SetRepr::Seq(r) => mix2(4, r.hash64()),
112        SetRepr::Subset(b) => mix2(5, b.hash64()),
113        SetRepr::FcnSet(d, r) => mix2(mix2(6, d.hash64()), r.hash64()),
114        SetRepr::RcdSet(fs) => fs
115            .iter()
116            .fold(7, |h, (a, v)| mix2(mix2(h, a.text_hash()), v.hash64())),
117        SetRepr::Product(fs) => seq(8, &mut fs.iter()),
118        SetRepr::Raw(e) => seq(9, &mut e.iter()),
119        SetRepr::Deferred(d) => seq(mix2(10, d.kind() as u64), &mut d.key().iter()),
120        SetRepr::Interval(lo, hi) => mix2(
121            mix2(11, Value::int(lo.clone()).hash64()),
122            Value::int(hi.clone()).hash64(),
123        ),
124        SetRepr::Enum => 12,
125    };
126    mix2(K_SET ^ 0xdead_beef, h)
127}
128
129/// Equality of the definitions of two structural sets.
130fn structural_eq(a: &Set, b: &Set) -> bool {
131    match (a.repr(), b.repr()) {
132        (SetRepr::Nat, SetRepr::Nat)
133        | (SetRepr::Int, SetRepr::Int)
134        | (SetRepr::Strings, SetRepr::Strings) => true,
135        (SetRepr::Seq(x), SetRepr::Seq(y)) | (SetRepr::Subset(x), SetRepr::Subset(y)) => x == y,
136        (SetRepr::FcnSet(d1, r1), SetRepr::FcnSet(d2, r2)) => d1 == d2 && r1 == r2,
137        (SetRepr::RcdSet(f1), SetRepr::RcdSet(f2)) => {
138            f1.len() == f2.len() && f1.iter().zip(f2.iter()).all(|(p, q)| p == q)
139        }
140        (SetRepr::Product(f1), SetRepr::Product(f2)) | (SetRepr::Raw(f1), SetRepr::Raw(f2)) => {
141            f1 == f2
142        }
143        (SetRepr::Interval(l1, h1), SetRepr::Interval(l2, h2)) => l1 == l2 && h1 == h2,
144        (SetRepr::Deferred(p), SetRepr::Deferred(q)) => p.kind() == q.kind() && p.key() == q.key(),
145        _ => false,
146    }
147}
148
149fn structural_rank(r: &SetRepr) -> u8 {
150    match r {
151        SetRepr::Nat => 0,
152        SetRepr::Int => 1,
153        SetRepr::Strings => 2,
154        SetRepr::Seq(_) => 3,
155        SetRepr::Subset(_) => 4,
156        SetRepr::FcnSet(..) => 5,
157        SetRepr::RcdSet(_) => 6,
158        SetRepr::Product(_) => 7,
159        SetRepr::Interval(..) => 8,
160        SetRepr::Enum => 9,
161        SetRepr::Raw(_) => 10,
162        SetRepr::Deferred(_) => 11,
163    }
164}
165
166fn seq_cmp(a: &[Value], b: &[Value], order: ValueOrder) -> Ordering {
167    a.len().cmp(&b.len()).then_with(|| {
168        for (x, y) in a.iter().zip(b) {
169            let c = total_cmp(x, y, order);
170            if c != Ordering::Equal {
171                return c;
172            }
173        }
174        Ordering::Equal
175    })
176}
177
178/// The order of two structural sets, by definition.
179fn structural_cmp(a: &Set, b: &Set, order: ValueOrder) -> Ordering {
180    let (ra, rb) = (structural_rank(a.repr()), structural_rank(b.repr()));
181    if ra != rb {
182        return ra.cmp(&rb);
183    }
184    match (a.repr(), b.repr()) {
185        (SetRepr::Seq(x), SetRepr::Seq(y)) | (SetRepr::Subset(x), SetRepr::Subset(y)) => {
186            total_cmp(x, y, order)
187        }
188        (SetRepr::FcnSet(d1, r1), SetRepr::FcnSet(d2, r2)) => {
189            total_cmp(d1, d2, order).then_with(|| total_cmp(r1, r2, order))
190        }
191        (SetRepr::RcdSet(f1), SetRepr::RcdSet(f2)) => f1.len().cmp(&f2.len()).then_with(|| {
192            for ((n1, s1), (n2, s2)) in f1.iter().zip(f2.iter()) {
193                let c = n1
194                    .cmp_with(n2, order)
195                    .then_with(|| total_cmp(s1, s2, order));
196                if c != Ordering::Equal {
197                    return c;
198                }
199            }
200            Ordering::Equal
201        }),
202        (SetRepr::Product(f1), SetRepr::Product(f2)) | (SetRepr::Raw(f1), SetRepr::Raw(f2)) => {
203            seq_cmp(f1, f2, order)
204        }
205        (SetRepr::Interval(l1, h1), SetRepr::Interval(l2, h2)) => {
206            l1.cmp(l2).then_with(|| h1.cmp(h2))
207        }
208        (SetRepr::Deferred(p), SetRepr::Deferred(q)) => (p.kind() as u8)
209            .cmp(&(q.kind() as u8))
210            .then_with(|| seq_cmp(&p.key(), &q.key(), order)),
211        _ => Ordering::Equal,
212    }
213}
214
215// ---------------------------------------------------------------------------------
216// ---------------------------------------------------------------------------------
217// Equality
218// ---------------------------------------------------------------------------------
219
220/// The normalized elements of a set that is (or can cheaply be) materialized, borrowed
221/// from the set's cache. Changes nothing observable.
222fn materialized_ref(s: &Set) -> Option<&[Value]> {
223    match s.repr() {
224        SetRepr::Enum | SetRepr::Raw(_) | SetRepr::Deferred(_) => {
225            s.quiet_elements(quiet_ctx(s.order())).ok()?;
226            s.0.elems.get().map(|e| &**e)
227        }
228        _ => None,
229    }
230}
231
232/// Equality of scalars, or `None` when both are compound.
233fn scalar_eq(a: &Value, b: &Value) -> Option<bool> {
234    Some(match (a, b) {
235        (Value::Bool(p), Value::Bool(q)) => p == q,
236        (Value::Int(p), Value::Int(q)) => p == q,
237        (Value::Int(_) | Value::BigInt(_), Value::Int(_) | Value::BigInt(_)) => {
238            a.as_int() == b.as_int()
239        }
240        (Value::Str(p), Value::Str(q)) | (Value::Model(p), Value::Model(q)) => p == q,
241        (Value::Fcn(f), Value::Fcn(g)) => {
242            if f.ptr_eq(g) {
243                return Some(true);
244            }
245            if f.0.hash != g.0.hash {
246                return Some(false);
247            }
248            return None;
249        }
250        (Value::Set(_), Value::Set(_)) => return None,
251        _ => false,
252    })
253}
254
255/// The semantic equality behind `impl PartialEq for Value`. Total: values TLC refuses
256/// to compare are simply unequal. Use [`crate::tlc::equals`] for TLC's checked
257/// equality. Iterative over enumerated sets and functions.
258pub(crate) fn semantic_eq(a: &Value, b: &Value) -> bool {
259    if let Some(r) = scalar_eq(a, b) {
260        return r;
261    }
262    let mut work: Vec<(&Value, &Value)> = vec![(a, b)];
263    while let Some((x, y)) = work.pop() {
264        let equal = match scalar_eq(x, y) {
265            Some(r) => r,
266            None => match (x, y) {
267                (Value::Fcn(f), Value::Fcn(g)) => fcn_eq_step(f, g, &mut work),
268                (Value::Set(s), Value::Set(t)) => set_eq_step(s, t, &mut work),
269                _ => false,
270            },
271        };
272        if !equal {
273            return false;
274        }
275    }
276    true
277}
278
279fn fcn_eq_step<'a>(f: &'a Fcn, g: &'a Fcn, work: &mut Vec<(&'a Value, &'a Value)>) -> bool {
280    if f.len() != g.len() || f.kind() != g.kind() {
281        return false;
282    }
283    match (&f.0.repr, &g.0.repr) {
284        (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => work.extend(a.iter().zip(b.iter())),
285        (FcnRepr::Record(a), FcnRepr::Record(b)) => {
286            if f.order() == g.order() {
287                for ((n, v), (m, w)) in a.iter().zip(b.iter()) {
288                    if n != m {
289                        return false;
290                    }
291                    work.push((v, w));
292                }
293            } else {
294                for (n, v) in a {
295                    match b.iter().find(|(m, _)| m == n) {
296                        Some((_, w)) => work.push((v, w)),
297                        None => return false,
298                    }
299                }
300            }
301        }
302        (FcnRepr::General(a), FcnRepr::General(b)) => {
303            if f.order() == g.order() {
304                for ((d1, v1), (d2, v2)) in a.iter().zip(b.iter()) {
305                    work.push((d1, d2));
306                    work.push((v1, v2));
307                }
308            } else {
309                for (d, v) in a {
310                    match b.iter().find(|(e, _)| *e == d) {
311                        Some((_, w)) => work.push((v, w)),
312                        None => return false,
313                    }
314                }
315            }
316        }
317        _ => return false,
318    }
319    true
320}
321
322fn set_eq_step<'a>(s: &'a Set, t: &'a Set, work: &mut Vec<(&'a Value, &'a Value)>) -> bool {
323    if s.ptr_eq(t) {
324        return true;
325    }
326    if let (Some((l1, h1)), Some((l2, h2))) = (s.as_interval(), t.as_interval()) {
327        return (h1 < l1 && h2 < l2) || (l1 == l2 && h1 == h2);
328    }
329    let (cs, ct) = (class(s), class(t));
330    match (cs == Class::Structural, ct == Class::Structural) {
331        (true, true) => return structural_eq(s, t),
332        (true, false) | (false, true) => return false,
333        (false, false) => {}
334    }
335    if quiet_size(s) != quiet_size(t) || s.hash64() != t.hash64() {
336        return false;
337    }
338    if s.order() == t.order()
339        && let (Some(a), Some(b)) = (materialized_ref(s), materialized_ref(t))
340    {
341        work.extend(a.iter().zip(b.iter()));
342        return true;
343    }
344    let order = s.order();
345    match (quiet_stream(s, order), quiet_stream(t, order)) {
346        (Some(a), Some(b)) => a.zip(b).all(|(x, y)| semantic_eq(&x, &y)),
347        _ => false,
348    }
349}
350
351// ---------------------------------------------------------------------------------
352// The total order
353// ---------------------------------------------------------------------------------
354
355pub(crate) fn rank(v: &Value) -> u8 {
356    match v {
357        Value::Model(_) => 0,
358        Value::Bool(_) => 1,
359        Value::Int(_) | Value::BigInt(_) => 2,
360        Value::Str(_) => 3,
361        Value::Set(s) => {
362            if class(s) == Class::Structural {
363                6
364            } else {
365                4
366            }
367        }
368        Value::Fcn(_) => 5,
369    }
370}
371
372impl Value {
373    /// A total order on all values, under the name order `order`.
374    ///
375    /// It extends TLC's partial order (`Value.compareTo` in `tlc2.value.impl`):
376    /// wherever TLC compares two values without error the two agree, and where TLC
377    /// raises an error this order falls back to a fixed ranking of kinds:
378    ///
379    /// 1. model values (by name),
380    /// 2. booleans (`FALSE < TRUE`),
381    /// 3. integers (numerically),
382    /// 4. strings (by name),
383    /// 5. finite sets (by cardinality, then element by element in normalized order),
384    /// 6. functions, including tuples and records (by domain size, then domain
385    ///    element by element, then values element by element),
386    /// 7. infinite, unenumerable or very large sets (`Nat < Int < STRING < Seq(S)`,
387    ///    then by definition).
388    ///
389    /// Names (rules 1 and 4, and record fields) are ordered by [`ValueOrder`].
390    /// Consistent with `==`: `a.cmp_with(b, o) == Equal` iff `a == b`.
391    #[must_use]
392    pub fn cmp_with(&self, other: &Self, order: ValueOrder) -> Ordering {
393        total_cmp(self, other, order)
394    }
395}
396
397/// After this many selections, [`for_each_sorted`] sorts what remains instead.
398const SELECT_BEFORE_SORT: usize = 4;
399
400/// Visits `elems` in ascending [`total_cmp`] order until `visit` decides,
401/// without sorting when the decision comes early: a candidate set usually
402/// differs from the set it is compared with in its first few elements.
403/// `elems` must be pairwise distinct, so that the order is unique.
404pub(crate) fn for_each_sorted<'a, T>(
405    elems: &[&'a Value],
406    order: ValueOrder,
407    mut visit: impl FnMut(&'a Value) -> Result<Option<T>>,
408) -> Result<Option<T>> {
409    let mut rest: Vec<&'a Value> = elems.to_vec();
410    let mut selected = 0usize;
411    while !rest.is_empty() {
412        if selected == SELECT_BEFORE_SORT {
413            rest.sort_unstable_by(|a, b| total_cmp(a, b, order));
414            for x in rest {
415                if let Some(t) = visit(x)? {
416                    return Ok(Some(t));
417                }
418            }
419            return Ok(None);
420        }
421        let mut min = 0;
422        for i in 1..rest.len() {
423            if total_cmp(rest[i], rest[min], order) == Ordering::Less {
424                min = i;
425            }
426        }
427        if let Some(t) = visit(rest.swap_remove(min))? {
428            return Ok(Some(t));
429        }
430        selected += 1;
431    }
432    Ok(None)
433}
434
435/// `Value::set_raw(elems).cmp_with(other, order)` for pairwise-distinct,
436/// mutually comparable `elems` (see [`Value::cmp_distinct_set`]).
437fn cmp_distinct_set(elems: &[&Value], other: &Value, order: ValueOrder) -> Option<Ordering> {
438    let Value::Set(t) = other else {
439        return None;
440    };
441    // The candidate is a small finite set (rank 4); only an enumerated `other`
442    // of the same rank compares element by element.
443    if !matches!(t.repr(), SetRepr::Enum | SetRepr::Raw(_)) || class(t) != Class::Finite {
444        return None;
445    }
446    let n = u128::try_from(elems.len()).ok()?;
447    if n > u128::from(MAX_ENUMERATION) {
448        return None;
449    }
450    let c = n.cmp(&quiet_size(t)?);
451    if c != Ordering::Equal {
452        return Some(c);
453    }
454    let mut theirs = quiet_stream(t, order)?;
455    let mut exhausted = false;
456    let decided = for_each_sorted(elems, order, |x| {
457        let Some(y) = theirs.next() else {
458            exhausted = true;
459            return Ok(Some(Ordering::Equal));
460        };
461        let c = total_cmp(x, &y, order);
462        Ok((c != Ordering::Equal).then_some(c))
463    })
464    .ok()?;
465    if exhausted {
466        return None;
467    }
468    Some(decided.unwrap_or(Ordering::Equal))
469}
470
471impl Value {
472    /// The order [`Value::cmp_with`] gives the set of `elems`, built raw,
473    /// against `other`, computed without building or sorting that set: its
474    /// elements are selected in order only up to the first difference.
475    /// `None` when `other` is not a finite enumerated set, so that the caller
476    /// must build the set and compare it in full.
477    ///
478    /// The caller must guarantee that `elems` are pairwise distinct and
479    /// mutually comparable ([`Value::elements_comparable`]), as the image of a
480    /// normalized set under an injective map that preserves comparability is.
481    ///
482    /// ```
483    /// use dive_value::{Ctx, Value};
484    /// let ctx = Ctx::default();
485    /// let (one, two, three) = (Value::Int(1), Value::Int(2), Value::Int(3));
486    /// let other = Value::set_raw(vec![one.clone(), three.clone()], ctx);
487    /// let full = Value::set_raw(vec![two.clone(), one.clone()], ctx).cmp_with(&other, ctx.order);
488    /// assert_eq!(Value::cmp_distinct_set(&[&two, &one], &other, ctx.order), Some(full));
489    /// ```
490    #[must_use]
491    pub fn cmp_distinct_set(
492        elems: &[&Value],
493        other: &Value,
494        order: ValueOrder,
495    ) -> Option<Ordering> {
496        cmp_distinct_set(elems, other, order)
497    }
498
499    /// Whether every pair of `elems` compares in TLC without error, so that a
500    /// set of them normalizes by the total order alone.
501    ///
502    /// ```
503    /// use dive_value::Value;
504    /// assert!(Value::elements_comparable(&[Value::Int(1), Value::Int(2)]));
505    /// assert!(!Value::elements_comparable(&[Value::Int(1), Value::Bool(true)]));
506    /// ```
507    #[must_use]
508    pub fn elements_comparable(elems: &[Value]) -> bool {
509        all_comparable(elems)
510    }
511}
512
513/// A function's `(domain, value)` pairs sorted in `order`.
514fn pairs_in(f: &Fcn, order: ValueOrder) -> crate::function_domain::OrderedFcn<'_> {
515    crate::function_domain::OrderedFcn::new(f, order)
516}
517
518/// The order of scalars (and of values of different scalar kinds), or `None` when a
519/// compound value is involved.
520pub(crate) fn scalar_cmp(a: &Value, b: &Value, order: ValueOrder) -> Option<Ordering> {
521    match (a, b) {
522        (Value::Bool(p), Value::Bool(q)) => Some(p.cmp(q)),
523        (Value::Int(p), Value::Int(q)) => Some(p.cmp(q)),
524        (Value::Str(p), Value::Str(q)) | (Value::Model(p), Value::Model(q)) => {
525            Some(p.cmp_with(q, order))
526        }
527        (Value::Set(_) | Value::Fcn(_), _) | (_, Value::Set(_) | Value::Fcn(_)) => None,
528        _ => {
529            let (ra, rb) = (rank(a), rank(b));
530            if ra == rb {
531                Some(a.as_int().cmp(&b.as_int()))
532            } else {
533                Some(ra.cmp(&rb))
534            }
535        }
536    }
537}
538
539pub(crate) fn total_cmp(a: &Value, b: &Value, order: ValueOrder) -> Ordering {
540    if let Some(c) = scalar_cmp(a, b, order) {
541        return c;
542    }
543    if let (Value::Fcn(f), Value::Fcn(g)) = (a, b)
544        && let Some(c) = flat_fcn_cmp(f, g, order)
545    {
546        return c;
547    }
548    let mut work: Vec<(&Value, &Value)> = vec![(a, b)];
549    while let Some((x, y)) = work.pop() {
550        let c = cmp_step(x, y, order, &mut work);
551        if c != Ordering::Equal {
552            return c;
553        }
554    }
555    Ordering::Equal
556}
557
558/// [`fcn_cmp_step`] for tuples, or records in `order`, whose deciding values
559/// are scalars, without a work list; `None` when a compound value would have
560/// to be compared.
561fn flat_fcn_cmp(f: &Fcn, g: &Fcn, order: ValueOrder) -> Option<Ordering> {
562    if f.ptr_eq(g) {
563        return Some(Ordering::Equal);
564    }
565    let c = f.len().cmp(&g.len());
566    if c != Ordering::Equal {
567        return Some(c);
568    }
569    let values = |pairs: &mut dyn Iterator<Item = (&Value, &Value)>| {
570        for (v, w) in pairs {
571            let c = scalar_cmp(v, w, order)?;
572            if c != Ordering::Equal {
573                return Some(c);
574            }
575        }
576        Some(Ordering::Equal)
577    };
578    match (&f.0.repr, &g.0.repr) {
579        (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => values(&mut a.iter().zip(b.iter())),
580        (FcnRepr::Record(a), FcnRepr::Record(b)) if f.order() == order && g.order() == order => {
581            for ((n, _), (m, _)) in a.iter().zip(b.iter()) {
582                let c = n.cmp_with(m, order);
583                if c != Ordering::Equal {
584                    return Some(c);
585                }
586            }
587            values(&mut a.iter().zip(b.iter()).map(|((_, v), (_, w))| (v, w)))
588        }
589        _ => None,
590    }
591}
592
593/// Compares the top level of `x` and `y`; pushes the pairs that decide a tie, so that
594/// the first of them is popped next.
595fn cmp_step<'a>(
596    x: &'a Value,
597    y: &'a Value,
598    order: ValueOrder,
599    work: &mut Vec<(&'a Value, &'a Value)>,
600) -> Ordering {
601    if let Some(c) = scalar_cmp(x, y, order) {
602        return c;
603    }
604    let (ra, rb) = (rank(x), rank(y));
605    if ra != rb {
606        return ra.cmp(&rb);
607    }
608    match (x, y) {
609        (Value::Fcn(f), Value::Fcn(g)) => fcn_cmp_step(f, g, order, work),
610        (Value::Set(s), Value::Set(t)) => set_cmp_step(s, t, ra, order, work),
611        _ => Ordering::Equal,
612    }
613}
614
615fn fcn_cmp_step<'a>(
616    f: &'a Fcn,
617    g: &'a Fcn,
618    order: ValueOrder,
619    work: &mut Vec<(&'a Value, &'a Value)>,
620) -> Ordering {
621    if f.ptr_eq(g) {
622        return Ordering::Equal;
623    }
624    let c = f.len().cmp(&g.len());
625    if c != Ordering::Equal {
626        return c;
627    }
628    let same_order = f.order() == order && g.order() == order;
629    match (&f.0.repr, &g.0.repr) {
630        // Same domain 1..n: only the values decide.
631        (FcnRepr::Tuple(a), FcnRepr::Tuple(b)) => {
632            work.extend(a.iter().zip(b.iter()).rev());
633            Ordering::Equal
634        }
635        (FcnRepr::Record(a), FcnRepr::Record(b)) if same_order => {
636            for ((n, _), (m, _)) in a.iter().zip(b.iter()) {
637                let c = n.cmp_with(m, order);
638                if c != Ordering::Equal {
639                    return c;
640                }
641            }
642            work.extend(a.iter().zip(b.iter()).rev().map(|((_, v), (_, w))| (v, w)));
643            Ordering::Equal
644        }
645        (FcnRepr::General(a), FcnRepr::General(b)) if same_order => {
646            work.extend(a.iter().zip(b.iter()).rev().map(|((_, v), (_, w))| (v, w)));
647            work.extend(a.iter().zip(b.iter()).rev().map(|((d, _), (e, _))| (d, e)));
648            Ordering::Equal
649        }
650        // Different domain shapes or orders: compare owned copies.
651        _ => {
652            let (p, q) = (pairs_in(f, order), pairs_in(g, order));
653            for ((d1, _), (d2, _)) in p.iter().zip(q.iter()) {
654                let c = total_cmp(&d1, &d2, order);
655                if c != Ordering::Equal {
656                    return c;
657                }
658            }
659            for ((_, v1), (_, v2)) in p.iter().zip(q.iter()) {
660                let c = total_cmp(v1, v2, order);
661                if c != Ordering::Equal {
662                    return c;
663                }
664            }
665            Ordering::Equal
666        }
667    }
668}
669
670fn set_cmp_step<'a>(
671    s: &'a Set,
672    t: &'a Set,
673    rank: u8,
674    order: ValueOrder,
675    work: &mut Vec<(&'a Value, &'a Value)>,
676) -> Ordering {
677    if s.ptr_eq(t) {
678        return Ordering::Equal;
679    }
680    if rank == 6 {
681        return structural_cmp(s, t, order);
682    }
683    let c = quiet_size(s).cmp(&quiet_size(t));
684    if c != Ordering::Equal {
685        return c;
686    }
687    if let (Some((l1, _)), Some((l2, _))) = (s.as_interval(), t.as_interval()) {
688        if interval_empty(s) {
689            return Ordering::Equal;
690        }
691        return l1.cmp(l2);
692    }
693    if s.order() == order
694        && t.order() == order
695        && let (Some(a), Some(b)) = (materialized_ref(s), materialized_ref(t))
696    {
697        work.extend(a.iter().zip(b.iter()).rev());
698        return Ordering::Equal;
699    }
700    match (quiet_stream(s, order), quiet_stream(t, order)) {
701        (Some(a), Some(b)) => {
702            for (x, y) in a.zip(b) {
703                let c = total_cmp(&x, &y, order);
704                if c != Ordering::Equal {
705                    return c;
706                }
707            }
708            Ordering::Equal
709        }
710        _ => structural_cmp(s, t, order),
711    }
712}
713
714// ---------------------------------------------------------------------------------
715// Comparability shapes
716// ---------------------------------------------------------------------------------
717
718/// A conservative description of which TLC comparisons can fail. If the join of two
719/// values' shapes is not `Conflict`, TLC compares them without error.
720#[derive(Clone, PartialEq, Eq, Debug)]
721enum Shape {
722    Bottom,
723    AnyMv,
724    TypedMv(u16),
725    Bool,
726    Int,
727    Str,
728    Set(Box<Shape>),
729    Fcn(Box<Shape>, Box<Shape>),
730    /// Functions with string domains (records, literal or not), by field-name
731    /// list: two of them with different names are told apart by their names
732    /// alone, and two with the same names compare field by field. The names
733    /// are in stored order (see [`join_fields`]).
734    Rcd(Vec<(Vec<Atom>, Vec<Shape>)>),
735    Conflict,
736}
737
738/// Joins record shapes: per name list, field by field.
739fn join_rcd(mut acc: Vec<(Vec<Atom>, Vec<Shape>)>, other: Vec<(Vec<Atom>, Vec<Shape>)>) -> Shape {
740    for (names, fields) in other {
741        if !join_fields(&mut acc, &names, |n| n, fields.into_iter()) {
742            return Shape::Conflict;
743        }
744    }
745    Shape::Rcd(acc)
746}
747
748/// Joins one record's field shapes into `acc`, keyed by its field names in
749/// stored order; `false` on a conflict. The same names stored in another
750/// order (records built under different name orders) are a conflict, so the
751/// key never pairs fields by position wrongly.
752fn join_fields<'a, N>(
753    acc: &mut Vec<(Vec<Atom>, Vec<Shape>)>,
754    names: &'a [N],
755    name: impl Fn(&'a N) -> &'a Atom,
756    fields: impl Iterator<Item = Shape>,
757) -> bool {
758    let same =
759        |n: &[Atom]| n.len() == names.len() && n.iter().zip(names).all(|(a, b)| a == name(b));
760    if let Some((_, mine)) = acc.iter_mut().find(|(n, _)| same(n)) {
761        for (field, theirs) in mine.iter_mut().zip(fields) {
762            let joined = join(std::mem::replace(field, Shape::Bottom), theirs);
763            if joined == Shape::Conflict {
764                return false;
765            }
766            *field = joined;
767        }
768        return true;
769    }
770    if acc
771        .iter()
772        .any(|(n, _)| n.len() == names.len() && names.iter().all(|other| n.contains(name(other))))
773    {
774        return false;
775    }
776    let fields: Vec<Shape> = fields.collect();
777    if fields.contains(&Shape::Conflict) {
778        return false;
779    }
780    acc.push((names.iter().map(|n| name(n).clone()).collect(), fields));
781    true
782}
783
784fn join(a: Shape, b: Shape) -> Shape {
785    use Shape::{AnyMv, Bottom, Conflict, Fcn, Set, TypedMv};
786    match (a, b) {
787        (Conflict, _) | (_, Conflict) => Conflict,
788        (Bottom | AnyMv, x) | (x, Bottom | AnyMv) => x,
789        (TypedMv(s), TypedMv(t)) => {
790            if s == t {
791                TypedMv(s)
792            } else {
793                Conflict
794            }
795        }
796        (Set(x), Set(y)) => match join(*x, *y) {
797            Conflict => Conflict,
798            j => Set(Box::new(j)),
799        },
800        (Fcn(d1, v1), Fcn(d2, v2)) => match (join(*d1, *d2), join(*v1, *v2)) {
801            (Conflict, _) | (_, Conflict) => Conflict,
802            (d, v) => Fcn(Box::new(d), Box::new(v)),
803        },
804        (Shape::Rcd(a), Shape::Rcd(b)) => join_rcd(a, b),
805        // Only the empty tuple compares with a record without error (TLC's
806        // `toRcd` of `<<>>`, and `FcnRcdValue.compareTo` by size); any other
807        // tuple or function fails in one of the two directions.
808        (Shape::Rcd(r), Fcn(d, v)) | (Fcn(d, v), Shape::Rcd(r)) if *d == Bottom && *v == Bottom => {
809            Shape::Rcd(r)
810        }
811        (x, y) => {
812            if x == y && matches!(x, Shape::Bool | Shape::Int | Shape::Str) {
813                x
814            } else {
815                Conflict
816            }
817        }
818    }
819}
820
821fn join_all<'a>(vals: impl Iterator<Item = &'a Value>) -> Shape {
822    let mut acc = Shape::Bottom;
823    for v in vals {
824        // Records join into the accumulated record shape in place, without
825        // building a shape of their own.
826        if let (Shape::Rcd(entries), Value::Fcn(f)) = (&mut acc, v)
827            && let FcnRepr::Record(fs) = &f.0.repr
828        {
829            let Ok(_guard) = crate::depth::Guard::enter() else {
830                return Shape::Conflict;
831            };
832            let joined = join_fields(entries, fs, |(n, _)| n, fs.iter().map(|(_, v)| shape(v)));
833            if !joined {
834                return Shape::Conflict;
835            }
836            continue;
837        }
838        acc = join(acc, shape(v));
839        if acc == Shape::Conflict {
840            break;
841        }
842    }
843    acc
844}
845
846fn shape(v: &Value) -> Shape {
847    // Very deep values simply take the exact (slow) path.
848    let Ok(_guard) = crate::depth::Guard::enter() else {
849        return Shape::Conflict;
850    };
851    match v {
852        Value::Bool(_) => Shape::Bool,
853        Value::Int(_) | Value::BigInt(_) => Shape::Int,
854        Value::Str(_) => Shape::Str,
855        Value::Model(a) => a.mv_type().map_or(Shape::AnyMv, Shape::TypedMv),
856        Value::Set(s) => match s.repr() {
857            SetRepr::Enum => match s.0.elems.get() {
858                Some(e) => match join_all(e.iter()) {
859                    Shape::Conflict => Shape::Conflict,
860                    j => Shape::Set(Box::new(j)),
861                },
862                None => Shape::Conflict,
863            },
864            SetRepr::Interval(..) => Shape::Set(Box::new(Shape::Int)),
865            _ => Shape::Conflict,
866        },
867        Value::Fcn(f) => match &f.0.repr {
868            FcnRepr::Tuple(e) => {
869                let d = if e.is_empty() {
870                    Shape::Bottom
871                } else {
872                    Shape::Int
873                };
874                match join_all(e.iter()) {
875                    Shape::Conflict => Shape::Conflict,
876                    j => Shape::Fcn(Box::new(d), Box::new(j)),
877                }
878            }
879            FcnRepr::Record(fs) => {
880                let mut acc = Vec::new();
881                if join_fields(&mut acc, fs, |(n, _)| n, fs.iter().map(|(_, v)| shape(v))) {
882                    Shape::Rcd(acc)
883                } else {
884                    Shape::Conflict
885                }
886            }
887            // An empty explicit domain would pass for the empty tuple.
888            FcnRepr::General(ps) if ps.is_empty() => Shape::Conflict,
889            FcnRepr::General(ps) => {
890                match (
891                    join_all(ps.iter().map(|(d, _)| d)),
892                    join_all(ps.iter().map(|(_, v)| v)),
893                ) {
894                    (Shape::Conflict, _) | (_, Shape::Conflict) => Shape::Conflict,
895                    (d, v) => Shape::Fcn(Box::new(d), Box::new(v)),
896                }
897            }
898        },
899    }
900}
901
902/// Whether every pair of `elems` is comparable in TLC without error.
903fn all_comparable(elems: &[Value]) -> bool {
904    // Fast scalar pass first: the common sets of integers or strings need no shapes.
905    let Some(first) = elems.first() else {
906        return true;
907    };
908    let scalar_same = match first {
909        Value::Int(_) => elems
910            .iter()
911            .all(|v| matches!(v, Value::Int(_) | Value::BigInt(_))),
912        Value::Str(_) => elems.iter().all(|v| matches!(v, Value::Str(_))),
913        Value::Bool(_) => elems.iter().all(|v| matches!(v, Value::Bool(_))),
914        _ => false,
915    };
916    scalar_same || join_all(elems.iter()) != Shape::Conflict
917}
918
919/// Joins record shapes: per name list, field by field.
920fn join_rcd_controlled(
921    mut acc: Vec<(Vec<Atom>, Vec<Shape>)>,
922    other: Vec<(Vec<Atom>, Vec<Shape>)>,
923    poll: &mut dyn FnMut() -> bool,
924) -> std::result::Result<Shape, crate::ConstructionError> {
925    for (names, fields) in other {
926        if !join_fields_controlled(&mut acc, &names, |n| n, fields.into_iter().map(Ok), poll)? {
927            return Ok(Shape::Conflict);
928        }
929    }
930    Ok(Shape::Rcd(acc))
931}
932
933fn join_fields_controlled<'a, N>(
934    acc: &mut Vec<(Vec<Atom>, Vec<Shape>)>,
935    names: &'a [N],
936    name: impl Fn(&'a N) -> &'a Atom,
937    fields: impl Iterator<Item = std::result::Result<Shape, crate::ConstructionError>>,
938    poll: &mut dyn FnMut() -> bool,
939) -> std::result::Result<bool, crate::ConstructionError> {
940    let mut found = None;
941    for (at, (stored, _)) in acc.iter().enumerate() {
942        crate::construction::checkpoint(poll)?;
943        if stored.len() != names.len() {
944            continue;
945        }
946        let mut same = true;
947        for (a, b) in stored.iter().zip(names) {
948            crate::construction::checkpoint(poll)?;
949            same &= a == name(b);
950        }
951        if same {
952            found = Some(at);
953            break;
954        }
955    }
956    if let Some(at) = found {
957        for (field, theirs) in acc[at].1.iter_mut().zip(fields) {
958            let joined = join_controlled(std::mem::replace(field, Shape::Bottom), theirs?, poll)?;
959            if joined == Shape::Conflict {
960                return Ok(false);
961            }
962            *field = joined;
963        }
964        return Ok(true);
965    }
966    for (stored, _) in acc.iter() {
967        if stored.len() == names.len() {
968            let mut same_names = true;
969            for other in names {
970                let mut contains = false;
971                for key in stored {
972                    crate::construction::checkpoint(poll)?;
973                    contains |= key == name(other);
974                }
975                same_names &= contains;
976            }
977            if same_names {
978                return Ok(false);
979            }
980        }
981    }
982    let mut collected = Vec::new();
983    for field in fields {
984        crate::construction::reserve(&mut collected, 1, poll)?;
985        collected.push(field?);
986    }
987    if collected.contains(&Shape::Conflict) {
988        return Ok(false);
989    }
990    let mut keys = Vec::new();
991    crate::construction::reserve(&mut keys, names.len(), poll)?;
992    for field in names {
993        crate::construction::checkpoint(poll)?;
994        keys.push(name(field).clone());
995    }
996    crate::construction::reserve(acc, 1, poll)?;
997    acc.push((keys, collected));
998    Ok(true)
999}
1000
1001fn join_controlled(
1002    a: Shape,
1003    b: Shape,
1004    poll: &mut dyn FnMut() -> bool,
1005) -> std::result::Result<Shape, crate::ConstructionError> {
1006    use Shape::{AnyMv, Bottom, Conflict, Fcn, Set, TypedMv};
1007    crate::construction::checkpoint(poll)?;
1008    Ok(match (a, b) {
1009        (Conflict, _) | (_, Conflict) => Conflict,
1010        (Bottom | AnyMv, x) | (x, Bottom | AnyMv) => x,
1011        (TypedMv(s), TypedMv(t)) => {
1012            if s == t {
1013                TypedMv(s)
1014            } else {
1015                Conflict
1016            }
1017        }
1018        (Set(x), Set(y)) => match join_controlled(*x, *y, poll)? {
1019            Conflict => Conflict,
1020            j => Set(Box::new(j)),
1021        },
1022        (Fcn(d1, v1), Fcn(d2, v2)) => match (
1023            join_controlled(*d1, *d2, poll)?,
1024            join_controlled(*v1, *v2, poll)?,
1025        ) {
1026            (Conflict, _) | (_, Conflict) => Conflict,
1027            (d, v) => Fcn(Box::new(d), Box::new(v)),
1028        },
1029        (Shape::Rcd(a), Shape::Rcd(b)) => join_rcd_controlled(a, b, poll)?,
1030        (Shape::Rcd(r), Fcn(d, v)) | (Fcn(d, v), Shape::Rcd(r)) if *d == Bottom && *v == Bottom => {
1031            Shape::Rcd(r)
1032        }
1033        (x, y) => {
1034            if x == y && matches!(x, Shape::Bool | Shape::Int | Shape::Str) {
1035                x
1036            } else {
1037                Conflict
1038            }
1039        }
1040    })
1041}
1042
1043fn join_all_controlled<'a>(
1044    vals: impl Iterator<Item = &'a Value>,
1045    poll: &mut dyn FnMut() -> bool,
1046) -> std::result::Result<Shape, crate::ConstructionError> {
1047    let mut acc = Shape::Bottom;
1048    for value in vals {
1049        crate::construction::checkpoint(poll)?;
1050        // Build this one field list before borrowing poll for the join_controlled.
1051        // It retains the existing record grouping and field order.
1052        if let (Shape::Rcd(entries), Value::Fcn(f)) = (&mut acc, value)
1053            && let FcnRepr::Record(fields) = &f.0.repr
1054        {
1055            let Ok(_guard) = crate::depth::Guard::enter() else {
1056                return Ok(Shape::Conflict);
1057            };
1058            let mut shapes = Vec::new();
1059            crate::construction::reserve(&mut shapes, fields.len(), poll)?;
1060            for (_, value) in fields {
1061                shapes.push(shape_controlled(value, poll)?);
1062            }
1063            if !join_fields_controlled(
1064                entries,
1065                fields,
1066                |(name, _)| name,
1067                shapes.into_iter().map(Ok),
1068                poll,
1069            )? {
1070                return Ok(Shape::Conflict);
1071            }
1072            continue;
1073        }
1074        acc = join_controlled(acc, shape_controlled(value, poll)?, poll)?;
1075        if acc == Shape::Conflict {
1076            break;
1077        }
1078    }
1079    Ok(acc)
1080}
1081
1082fn shape_controlled(
1083    value: &Value,
1084    poll: &mut dyn FnMut() -> bool,
1085) -> std::result::Result<Shape, crate::ConstructionError> {
1086    crate::construction::checkpoint(poll)?;
1087    let Ok(_guard) = crate::depth::Guard::enter() else {
1088        return Ok(Shape::Conflict);
1089    };
1090    Ok(match value {
1091        Value::Bool(_) => Shape::Bool,
1092        Value::Int(_) | Value::BigInt(_) => Shape::Int,
1093        Value::Str(_) => Shape::Str,
1094        Value::Model(atom) => atom.mv_type().map_or(Shape::AnyMv, Shape::TypedMv),
1095        Value::Set(set) => match set.repr() {
1096            SetRepr::Enum => match set.0.elems.get() {
1097                Some(elements) => match join_all_controlled(elements.iter(), poll)? {
1098                    Shape::Conflict => Shape::Conflict,
1099                    joined => Shape::Set(Box::new(joined)),
1100                },
1101                None => Shape::Conflict,
1102            },
1103            SetRepr::Interval(..) => Shape::Set(Box::new(Shape::Int)),
1104            _ => Shape::Conflict,
1105        },
1106        Value::Fcn(f) => match &f.0.repr {
1107            FcnRepr::Tuple(elements) => {
1108                let domain = if elements.is_empty() {
1109                    Shape::Bottom
1110                } else {
1111                    Shape::Int
1112                };
1113                match join_all_controlled(elements.iter(), poll)? {
1114                    Shape::Conflict => Shape::Conflict,
1115                    joined => Shape::Fcn(Box::new(domain), Box::new(joined)),
1116                }
1117            }
1118            FcnRepr::Record(fields) => {
1119                let mut shapes = Vec::new();
1120                crate::construction::reserve(&mut shapes, fields.len(), poll)?;
1121                for (_, value) in fields {
1122                    shapes.push(shape_controlled(value, poll)?);
1123                }
1124                let mut acc = Vec::new();
1125                if join_fields_controlled(
1126                    &mut acc,
1127                    fields,
1128                    |(name, _)| name,
1129                    shapes.into_iter().map(Ok),
1130                    poll,
1131                )? {
1132                    Shape::Rcd(acc)
1133                } else {
1134                    Shape::Conflict
1135                }
1136            }
1137            FcnRepr::General(pairs) if pairs.is_empty() => Shape::Conflict,
1138            FcnRepr::General(pairs) => match (
1139                join_all_controlled(pairs.iter().map(|(key, _)| key), poll)?,
1140                join_all_controlled(pairs.iter().map(|(_, value)| value), poll)?,
1141            ) {
1142                (Shape::Conflict, _) | (_, Shape::Conflict) => Shape::Conflict,
1143                (domain, value) => Shape::Fcn(Box::new(domain), Box::new(value)),
1144            },
1145        },
1146    })
1147}
1148
1149/// The original comparability proof, with checkpoints in its structural walk.
1150pub(crate) fn all_comparable_controlled(
1151    elems: &[Value],
1152    poll: &mut dyn FnMut() -> bool,
1153) -> std::result::Result<bool, crate::ConstructionError> {
1154    let Some(first) = elems.first() else {
1155        crate::construction::checkpoint(poll)?;
1156        return Ok(true);
1157    };
1158    let mut scalar_same = matches!(first, Value::Int(_) | Value::Str(_) | Value::Bool(_));
1159    for value in elems {
1160        crate::construction::checkpoint(poll)?;
1161        scalar_same &= match first {
1162            Value::Int(_) => matches!(value, Value::Int(_) | Value::BigInt(_)),
1163            Value::Str(_) => matches!(value, Value::Str(_)),
1164            Value::Bool(_) => matches!(value, Value::Bool(_)),
1165            _ => false,
1166        };
1167    }
1168    Ok(scalar_same || join_all_controlled(elems.iter(), poll)? != Shape::Conflict)
1169}
1170// ---------------------------------------------------------------------------------
1171// Normalization
1172// ---------------------------------------------------------------------------------
1173
1174/// Sorts and deduplicates set elements as TLC's `SetEnumValue.normalize` does.
1175pub(crate) fn normalize_set(mut elems: Vec<Value>, ctx: Ctx) -> Result<Vec<Value>> {
1176    if elems.len() <= 1 {
1177        return Ok(elems);
1178    }
1179    if all_comparable(&elems) {
1180        elems.sort_by(|a, b| total_cmp(a, b, ctx.order));
1181        elems.dedup_by(|later, earlier| total_cmp(later, earlier, ctx.order) == Ordering::Equal);
1182        return Ok(elems);
1183    }
1184    // Decide errors exactly as TLC does, in TLC's order; keep TLC's survivors.
1185    let mut out = tlc_insertion_sort(
1186        elems,
1187        Ctx {
1188            order: ValueOrder::Tlc,
1189            ..ctx
1190        },
1191    )?;
1192    if ctx.order != ValueOrder::Tlc {
1193        out.sort_by(|a, b| total_cmp(a, b, ctx.order));
1194    }
1195    Ok(out)
1196}
1197
1198/// `ValueVec.sort(true)`: binary insertion with `elem.compareTo(sorted[mid])`, keeping
1199/// the first of equal elements.
1200fn tlc_insertion_sort(elems: Vec<Value>, ctx: Ctx) -> Result<Vec<Value>> {
1201    let mut iter = elems.into_iter();
1202    let mut out: Vec<Value> = Vec::new();
1203    if let Some(first) = iter.next() {
1204        out.push(first);
1205    }
1206    for elem in iter {
1207        let (mut low, mut high) = (0usize, out.len());
1208        let mut cmp = Ordering::Equal;
1209        let mut idx = 0usize;
1210        while low < high {
1211            idx = low + ((high - low) >> 1);
1212            cmp = crate::tlc::compare(&elem, &out[idx], ctx)?;
1213            match cmp {
1214                Ordering::Equal => break,
1215                Ordering::Less => high = idx,
1216                Ordering::Greater => low = idx + 1,
1217            }
1218        }
1219        if cmp != Ordering::Equal {
1220            let at = if cmp == Ordering::Less { idx } else { idx + 1 };
1221            out.insert(at, elem);
1222        }
1223    }
1224    Ok(out)
1225}
1226
1227fn dup_domain(v: &Value, ctx: Ctx) -> ValueError {
1228    ValueError::new(
1229        ErrorKind::Duplicate,
1230        format!(
1231            "The value\n{}\noccurs multiple times in the function domain.",
1232            crate::print::to_tlc_string_lenient(v, ctx)
1233        ),
1234    )
1235}
1236
1237/// Builds a function in canonical form (see [`Fcn`]), normalizing the domain as
1238/// `FcnRcdValue.normalize` does. A string domain gives a record that is not a record
1239/// literal (TLC keeps such functions as `FcnRcdValue`).
1240pub(crate) fn make_fcn(mut pairs: Vec<(Value, Value)>, ctx: Ctx) -> Result<Value> {
1241    if pairs.is_empty() {
1242        return Ok(Value::tuple_fcn(Vec::new()));
1243    }
1244    if pairs.len() > 1 {
1245        let doms: Vec<Value> = pairs.iter().map(|(d, _)| d.clone()).collect();
1246        if all_comparable(&doms) {
1247            pairs.sort_by(|a, b| total_cmp(&a.0, &b.0, ctx.order));
1248            for w in pairs.windows(2) {
1249                if total_cmp(&w[0].0, &w[1].0, ctx.order) == Ordering::Equal {
1250                    return Err(dup_domain(&w[1].0, ctx));
1251                }
1252            }
1253        } else {
1254            tlc_fcn_normalize(
1255                &mut pairs,
1256                Ctx {
1257                    order: ValueOrder::Tlc,
1258                    ..ctx
1259                },
1260            )?;
1261            if ctx.order != ValueOrder::Tlc {
1262                pairs.sort_by(|a, b| total_cmp(&a.0, &b.0, ctx.order));
1263            }
1264        }
1265    }
1266    // Canonical representation by domain.
1267    let n = pairs.len();
1268    let is_tuple = pairs.iter().enumerate().all(
1269        |(i, (d, _))| matches!(d, Value::Int(k) if i64::try_from(i).is_ok_and(|i| *k == i + 1)),
1270    );
1271    if is_tuple {
1272        return Ok(Value::tuple_fcn(
1273            pairs.into_iter().map(|(_, v)| v).collect(),
1274        ));
1275    }
1276    if pairs.iter().all(|(d, _)| matches!(d, Value::Str(_))) {
1277        let mut fields: Vec<(Atom, Value)> = Vec::with_capacity(n);
1278        for (d, v) in pairs {
1279            if let Value::Str(a) = d {
1280                fields.push((a, v));
1281            }
1282        }
1283        return Ok(Value::Fcn(Fcn::record(fields, ctx.order, false)));
1284    }
1285    Ok(Value::Fcn(Fcn::general(pairs, ctx.order)))
1286}
1287
1288/// `FcnRcdValue.normalize`: bring the minimum to the front by swaps, then insertion
1289/// sort from index 2, comparing with TLC's strict `compareTo`.
1290fn tlc_fcn_normalize(pairs: &mut [(Value, Value)], ctx: Ctx) -> Result<()> {
1291    let n = pairs.len();
1292    for i in 1..n {
1293        let c = crate::tlc::compare(&pairs[0].0, &pairs[i].0, ctx)?;
1294        if c == Ordering::Equal {
1295            return Err(dup_domain(&pairs[i].0, ctx));
1296        }
1297        if c == Ordering::Greater {
1298            pairs.swap(0, i);
1299        }
1300    }
1301    for i in 2..n {
1302        let item = pairs[i].clone();
1303        let mut j = i;
1304        let mut c = Ordering::Less;
1305        while j > 0 {
1306            c = crate::tlc::compare(&item.0, &pairs[j - 1].0, ctx)?;
1307            if c != Ordering::Less {
1308                break;
1309            }
1310            pairs[j] = pairs[j - 1].clone();
1311            j -= 1;
1312        }
1313        if c == Ordering::Equal {
1314            // TLC prints `this.domain[i]` after the shifts, which may be a neighbour.
1315            return Err(dup_domain(&pairs[i].0, ctx));
1316        }
1317        pairs[j] = item;
1318    }
1319    Ok(())
1320}
1321
1322// ---------------------------------------------------------------------------------
1323// Function domains
1324// ---------------------------------------------------------------------------------
1325
1326impl Fcn {
1327    /// Whether the function's domain, as a set, equals `dom` (`DOMAIN f = dom`
1328    /// under `==`), decided without building the domain set: by the bounds of
1329    /// an interval, by lookup in an enumerated set, or factor by factor for a
1330    /// product of those. `None` when no such shortcut applies, or when
1331    /// building the domain set could fail (domain elements TLC cannot
1332    /// compare); the caller then builds the set.
1333    ///
1334    /// ```
1335    /// use dive_value::{Ctx, Int, Value};
1336    /// let ctx = Ctx::default();
1337    /// let (Value::Fcn(f), Value::Set(d)) = (
1338    ///     Value::tuple(vec![Value::TRUE, Value::FALSE]),
1339    ///     Value::interval(Int::Small(1), Int::Small(2), ctx),
1340    /// ) else {
1341    ///     unreachable!()
1342    /// };
1343    /// assert_eq!(f.domain_equals(&d), Some(true));
1344    /// ```
1345    #[must_use]
1346    pub fn domain_equals(&self, dom: &Set) -> Option<bool> {
1347        if let Some(same) = self.exact_domain_equals(dom) {
1348            return Some(same);
1349        }
1350        if !self.domain_comparable() {
1351            return None;
1352        }
1353        let n = self.len() as u128;
1354        match dom.repr() {
1355            SetRepr::Interval(..) | SetRepr::Enum => {
1356                if quiet_size(dom)? != n {
1357                    return Some(false);
1358                }
1359                let mut verdict = Some(true);
1360                self.for_each_key(&mut |k| {
1361                    if verdict == Some(true) {
1362                        verdict = contains_settled(dom, k);
1363                    }
1364                });
1365                verdict
1366            }
1367            SetRepr::Product(factors) => {
1368                // A product too large to enumerate compares by structure.
1369                if class(dom) == Class::Structural {
1370                    return None;
1371                }
1372                let mut size: u128 = 1;
1373                for f in factors {
1374                    let Value::Set(f) = f else { return None };
1375                    if !matches!(f.repr(), SetRepr::Interval(..) | SetRepr::Enum) {
1376                        return None;
1377                    }
1378                    size = size.checked_mul(quiet_size(f)?)?;
1379                }
1380                if size != n {
1381                    return Some(false);
1382                }
1383                let mut verdict = Some(true);
1384                self.for_each_key(&mut |k| {
1385                    if verdict == Some(true) {
1386                        verdict = in_product(factors, k);
1387                    }
1388                });
1389                verdict
1390            }
1391            _ => None,
1392        }
1393    }
1394
1395    /// Whether building the set of the domain elements cannot fail: as in
1396    /// `normalize_set`, every pair is comparable in TLC.
1397    fn domain_comparable(&self) -> bool {
1398        match &self.0.repr {
1399            // The integers `1..n`, or strings.
1400            FcnRepr::Tuple(_) | FcnRepr::Record(_) => true,
1401            FcnRepr::General(p) => p.domain.comparable(),
1402        }
1403    }
1404
1405    /// Visits the domain elements, without cloning stored ones.
1406    fn for_each_key(&self, visit: &mut dyn FnMut(&Value)) {
1407        match &self.0.repr {
1408            FcnRepr::Tuple(e) => {
1409                for i in 1..=e.len() {
1410                    visit(&Value::Int(i64::try_from(i).unwrap_or(i64::MAX)));
1411                }
1412            }
1413            FcnRepr::Record(f) => {
1414                for (a, _) in f {
1415                    visit(&Value::Str(a.clone()));
1416                }
1417            }
1418            FcnRepr::General(p) => {
1419                for (d, _) in p {
1420                    visit(d);
1421                }
1422            }
1423        }
1424    }
1425}
1426
1427/// Whether `k` is a tuple whose components are members of `factors` in turn,
1428/// or `None` when a factor cannot decide without enumeration.
1429fn in_product(factors: &[Value], k: &Value) -> Option<bool> {
1430    let Some(t) = k.as_fcn().and_then(Fcn::as_tuple) else {
1431        return Some(false);
1432    };
1433    if t.len() != factors.len() {
1434        return Some(false);
1435    }
1436    for (x, f) in t.iter().zip(factors) {
1437        if !contains_settled(f.as_set()?, x)? {
1438            return Some(false);
1439        }
1440    }
1441    Some(true)
1442}
1443
1444/// `x \in s` under `==` for an interval or an enumerated set whose elements
1445/// are stored, or `None` for other sets and big integers.
1446fn contains_settled(s: &Set, x: &Value) -> Option<bool> {
1447    match s.repr() {
1448        SetRepr::Interval(lo, hi) => {
1449            let (lo, hi) = (lo.to_i64()?, hi.to_i64()?);
1450            match x {
1451                Value::Int(v) => Some(lo <= *v && *v <= hi),
1452                Value::BigInt(_) => None,
1453                _ => Some(false),
1454            }
1455        }
1456        SetRepr::Enum => {
1457            let elems = s.stored_elements()?;
1458            let order = s.order();
1459            Some(elems.binary_search_by(|e| total_cmp(e, x, order)).is_ok())
1460        }
1461        _ => None,
1462    }
1463}
1464
1465/// Whether reading/comparing this already materialized key can avoid providers.
1466pub(crate) fn stable_key(value: &Value) -> bool {
1467    let Ok(_guard) = crate::depth::Guard::enter() else {
1468        return false;
1469    };
1470    match value {
1471        Value::Bool(_) | Value::Int(_) | Value::BigInt(_) | Value::Str(_) | Value::Model(_) => true,
1472        Value::Set(set) => match set.repr() {
1473            SetRepr::Interval(..) => true,
1474            SetRepr::Enum => set
1475                .stored_elements()
1476                .is_some_and(|e| e.iter().all(stable_key)),
1477            _ => false,
1478        },
1479        Value::Fcn(f) => match &f.0.repr {
1480            FcnRepr::Tuple(values) => values.iter().all(stable_key),
1481            FcnRepr::Record(fields) => fields.iter().all(|(_, v)| stable_key(v)),
1482            FcnRepr::General(pairs) => pairs.iter().all(|(d, v)| stable_key(d) && stable_key(v)),
1483        },
1484    }
1485}