Skip to main content

dive_model/symmetry/
prepare.rs

1//! Tool-level symmetry preparation and concrete-state canonical keys.
2
3use std::cmp::Ordering;
4use std::collections::{HashMap, HashSet};
5use std::sync::Arc;
6
7use dive_config::{ConstantEntry, ModelConfig};
8use dive_eval::{ConstBinding, St};
9use dive_ir::{Arg, Expr, ExprId, OpRef, StdOp};
10use dive_value::{Atom, Ctx, SetKind, Value, ValueOrder};
11
12use super::{Declaration, Group, Limits, Mode, Permutation, symmetry_runtime_error};
13use crate::{BindError, Ec, Message, Model, Pred};
14
15/// Complete pure tool-level preparation, before attachment to a safety checker.
16#[derive(Clone, Debug)]
17pub struct Prepared {
18    /// The bounded closure; `None` means TLC's too-small heuristic disabled it.
19    pub reduction: Option<Arc<Reduction>>,
20    /// Startup warnings, in TLC's order.
21    pub warnings: Vec<Message>,
22}
23
24/// A bounded symmetry closure over the model values it mentions.
25/// State canonicalization changes keys only: the checker explores and retains
26/// the original concrete state and predecessor.
27#[derive(Clone, Debug)]
28pub struct Reduction {
29    universe: Vec<Atom>,
30    indices: HashMap<Atom, usize>,
31    group: Group,
32    /// Per map: whether it maps every model value to one of the same TLC type,
33    /// so that the image of any value has that value's comparability shape.
34    typed: Vec<bool>,
35    /// Identifies this closure's entries in the per-thread image cache.
36    id: u64,
37}
38
39/// Set elements' images under every map of one reduction, per thread. The
40/// images of the elements of a state's sets are compared, never kept or
41/// evaluated, and only for elements in which no set occurs, so a shared image
42/// is indistinguishable from a freshly built one. `None` marks a map whose
43/// image fails to build: that element is permuted afresh, which raises the
44/// error where the uncached search would.
45///
46/// Every cached element and image also has a rank: ranks are ordered as
47/// their values are by the total order, and equal values share one, so that
48/// comparing two sets of them is comparing integers.
49#[derive(Default)]
50struct ImageCache {
51    owner: Option<(u64, Ctx)>,
52    images: HashMap<Exact, Arc<Entry>>,
53    held: usize,
54    /// Bumped whenever the cache starts over, invalidating every rank id.
55    generation: u64,
56    /// The distinct ranked values in ascending order, with their rank ids.
57    sorted: Vec<(Value, u32)>,
58    /// Rank by rank id. Renumbering keeps the order of existing ranks.
59    rank: Vec<u64>,
60}
61
62/// One element's rank id, and its images (with rank ids) under every map.
63struct Entry {
64    key: u32,
65    images: Box<[Option<(Value, u32)>]>,
66}
67
68/// The space left between consecutive ranks when they are renumbered.
69const RANK_GAP: u64 = 1 << 24;
70
71impl ImageCache {
72    /// The rank id of `value`, ranking it if it is new.
73    fn rank_id(&mut self, value: &Value, order: ValueOrder) -> u32 {
74        match self
75            .sorted
76            .binary_search_by(|(probe, _)| probe.cmp_with(value, order))
77        {
78            Ok(at) => self.sorted[at].1,
79            Err(at) => {
80                let id = u32::try_from(self.rank.len()).unwrap_or(u32::MAX);
81                let below = at
82                    .checked_sub(1)
83                    .map_or(0, |i| self.rank[self.sorted[i].1 as usize]);
84                let above = self
85                    .sorted
86                    .get(at)
87                    .map_or(u64::MAX, |(_, above)| self.rank[*above as usize]);
88                self.rank.push(below + (above - below) / 2);
89                self.sorted.insert(at, (value.clone(), id));
90                if above - below < 2 {
91                    for (i, (_, id)) in self.sorted.iter().enumerate() {
92                        self.rank[*id as usize] = (i as u64 + 1) * RANK_GAP;
93                    }
94                }
95                id
96            }
97        }
98    }
99}
100
101/// A cache key: equal values that TLC also represents alike. Equal values of
102/// different TLC classes (a record and a string-domain function) compare
103/// alike only where neither comparison fails, so they never share images.
104struct Exact(Value);
105
106impl PartialEq for Exact {
107    fn eq(&self, other: &Self) -> bool {
108        self.0 == other.0 && same_classes(&self.0, &other.0)
109    }
110}
111
112impl Eq for Exact {}
113
114impl std::hash::Hash for Exact {
115    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
116        state.write_u64(self.0.hash64());
117    }
118}
119
120/// Whether two equal set-free values have the same TLC classes throughout.
121fn same_classes(a: &Value, b: &Value) -> bool {
122    match (a, b) {
123        (Value::Fcn(f), Value::Fcn(g)) => {
124            f.ptr_eq(g)
125                || (f.kind() == g.kind()
126                    && f.is_record_literal() == g.is_record_literal()
127                    && f.is_tuple_literal() == g.is_tuple_literal()
128                    && f.len() == g.len()
129                    && f.iter()
130                        .zip(g.iter())
131                        .all(|((d, v), (e, w))| same_classes(&d, &e) && same_classes(v, w)))
132        }
133        (Value::Int(_) | Value::BigInt(_), Value::Int(_) | Value::BigInt(_)) => true,
134        _ => std::mem::discriminant(a) == std::mem::discriminant(b),
135    }
136}
137
138/// The most images a thread's cache holds before it starts over.
139const IMAGE_CACHE_LIMIT: usize = 1 << 18;
140
141thread_local! {
142    static IMAGES: std::cell::RefCell<ImageCache> = std::cell::RefCell::default();
143}
144
145static NEXT_REDUCTION: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
146
147impl Model {
148    /// Prepares a pure declaration using `Tool.getSymmetryPerms`'s ordering:
149    /// representations, too-small warnings, domain/range checks, closure,
150    /// then unused argument warnings. `cfg` must be the bound configuration.
151    /// This API does not itself activate reduction or remove checker refusals.
152    ///
153    /// # Example
154    /// ```
155    /// # use std::sync::Arc;
156    /// # use dive_model::{BindOptions, bind};
157    /// # use dive_model::symmetry::{Mode, Limits};
158    /// let source = "---- MODULE M ----\nEXTENDS TLC\nCONSTANT S\nVARIABLE x\n\
159    ///               Init == x = TRUE\nNext == UNCHANGED x\n\
160    ///               Sym == Permutations(S)\n====\n";
161    /// let analysis = dive_sema::analyze_source("M.tla", source, &dive_sema::Options::default());
162    /// let ir = Arc::new(dive_ir::lower(&analysis).unwrap());
163    /// let cfg = dive_config::parse("CONSTANT S={a,b}\nINIT Init\nNEXT Next\nSYMMETRY Sym\n")
164    ///     .into_config().unwrap();
165    /// let model = bind(ir, &cfg, &BindOptions::tlc()).unwrap();
166    /// let prepared = model.prepare_symmetry(&cfg, Mode::Tlc, Limits::default()).unwrap().unwrap();
167    /// assert!(prepared.reduction.is_some());
168    /// assert!(prepared.warnings.is_empty());
169    /// ```
170    ///
171    /// # Errors
172    /// Invalid declarations, unavailable warning source evidence, unverified
173    /// startup exceptions, or a bounded-closure refusal.
174    pub fn prepare_symmetry(
175        &self,
176        cfg: &ModelConfig,
177        mode: Mode,
178        limits: Limits,
179    ) -> Result<Option<Prepared>, BindError> {
180        let Some(declaration) = self.symmetry_declaration()? else {
181            return Ok(None);
182        };
183        let args = argument_nodes(self.ir.expr(declaration.predicate.expr))?;
184        if !args.is_empty() && args.len() >= declaration.functions.len() {
185            // The default profile rejects non-bijective model-value maps even
186            // when TLC disables them. Non-model identities retain TLC's warning
187            // shortcut, deliberately: rejecting them too would be a further
188            // result-changing default.
189            // A duplicate generator supplies the kernel's capacity precondition
190            // without altering its closure; no reduction is attached here.
191            if mode == Mode::Checked
192                && !declaration.functions.is_empty()
193                && declaration.functions.iter().all(|value| match value {
194                    Value::Fcn(function) => function.iter().all(|(domain, range)| {
195                        matches!(domain, Value::Model(_)) && matches!(range, Value::Model(_))
196                    }),
197                    _ => false,
198                })
199            {
200                let mut checked = declaration.clone();
201                if checked.functions.len() == 1 {
202                    checked.functions =
203                        vec![checked.functions[0].clone(), checked.functions[0].clone()].into();
204                }
205                prepare_group(&checked, mode, limits)?;
206            }
207            return Ok(Some(Prepared {
208                reduction: None,
209                warnings: vec![warning(self, cfg, &args)?],
210            }));
211        }
212        let reduction = prepare_group(&declaration, mode, limits)?;
213        let members: HashSet<Atom> = reduction
214            .group
215            .maps()
216            .iter()
217            .flat_map(|map| {
218                map.images()
219                    .iter()
220                    .enumerate()
221                    .filter(|(index, image)| index != *image)
222                    .map(|(_, image)| reduction.universe[*image].clone())
223            })
224            .collect();
225        let mut unused = Vec::new();
226        for arg in args {
227            if let Some(values) = permutation_argument(self, &declaration, arg)?
228                && !values
229                    .iter()
230                    .any(|value| matches!(value, Value::Model(m) if members.contains(m)))
231            {
232                unused.push(arg);
233            }
234        }
235        Ok(Some(Prepared {
236            reduction: Some(Arc::new(reduction)),
237            warnings: if unused.is_empty() {
238                Vec::new()
239            } else {
240                vec![warning(self, cfg, &unused)?]
241            },
242        }))
243    }
244}
245
246fn argument_nodes(expr: &Expr) -> Result<Vec<ExprId>, BindError> {
247    match expr {
248        Expr::Def(_) | Expr::Const(_) | Expr::Bool(_) | Expr::Num(_) | Expr::Str(_) => {
249            Ok(Vec::new())
250        }
251        Expr::Builtin { args, .. }
252        | Expr::SetEnum(args)
253        | Expr::Tuple(args)
254        | Expr::Cartesian(args) => Ok(args.to_vec()),
255        Expr::Apply { args, .. } => args
256            .iter()
257            .map(|arg| match arg {
258                Arg::Expr { expr: id, .. } => Ok(*id),
259                Arg::Op { .. } => Err(BindError::unsupported(
260                    "SYMMETRY warning arguments containing an operator argument",
261                )),
262            })
263            .collect(),
264        Expr::If { cond, then, other } => Ok(vec![*cond, *then, *other]),
265        Expr::Junction { items, .. } => Ok(items.to_vec()),
266        _ => Err(BindError::unsupported(
267            "SYMMETRY declaration syntax whose TLC argument/warning shape is not implemented",
268        )),
269    }
270}
271
272fn warning(model: &Model, cfg: &ModelConfig, args: &[ExprId]) -> Result<Message, BindError> {
273    let mut names = Vec::new();
274    for arg in args {
275        let image = model
276            .ir
277            .human_readable_image(*arg)
278            .filter(|s| !s.is_empty())
279            .ok_or_else(|| {
280                BindError::unsupported("SYMMETRY warning lacks original source tokens")
281            })?;
282        let alias = if image.starts_with("Permutations") {
283            image
284                .get("Permutations".len() + 1..image.len().saturating_sub(1))
285                .ok_or_else(|| BindError::unsupported("SYMMETRY warning permutation image"))?
286        } else {
287            &image
288        };
289        let original = cfg
290            .constants
291            .iter()
292            .rev()
293            .find_map(|entry| match entry {
294                ConstantEntry::Substitution {
295                    name,
296                    target,
297                    module: None,
298                } if target.text == alias => Some(name.text.as_str()),
299                _ => None,
300            })
301            .unwrap_or(alias);
302        names.push(original.to_owned());
303    }
304    let many = args.len() > 1;
305    let parameters = [
306        if many { "s" } else { "" },
307        &names.join(", and "),
308        if many { "have" } else { "has" },
309        if many { "" } else { "s" },
310    ];
311    Ok(Message::Warning {
312        code: Ec::TlcSymmetrySetTooSmall,
313        message: Ec::TlcSymmetrySetTooSmall.render(
314            &parameters
315                .iter()
316                .map(|s| (*s).to_owned())
317                .collect::<Vec<_>>(),
318        ),
319    })
320}
321
322fn permutation_argument(
323    model: &Model,
324    declaration: &Declaration,
325    arg: ExprId,
326) -> Result<Option<Arc<[Value]>>, BindError> {
327    let Expr::Apply { callee, args } = model.ir.expr(arg) else {
328        return Ok(None);
329    };
330    let op = match callee {
331        OpRef::Def(def) => model.ir.def(*def).std,
332        OpRef::Std(op) => Some(*op),
333        _ => None,
334    };
335    if op != Some(StdOp::TlcPermutations) {
336        return Ok(None);
337    }
338    let [Arg::Expr { expr: domain, .. }] = args.as_ref() else {
339        return Ok(None);
340    };
341    let value = match model.ir.expr(*domain) {
342        Expr::Const(constant) => match model.evaluator.constant_binding(*constant) {
343            Some(ConstBinding::Value(value)) => value,
344            _ => return Ok(None),
345        },
346        Expr::Def(_) => model
347            .eval(
348                &Pred::new(*domain, declaration.predicate.scope.clone()),
349                &St::constant(),
350            )
351            .map_err(|error| {
352                BindError::unsupported(format!("SYMMETRY unused argument: {}", error.message()))
353            })?,
354        Expr::SubstRef { .. } => {
355            return Err(BindError::unsupported(
356                "SYMMETRY unused-set warning under instance substitutions",
357            ));
358        }
359        _ => return Ok(None),
360    };
361    if let Value::Set(set) = value
362        && matches!(set.kind(), SetKind::Enum | SetKind::Raw)
363    {
364        return set
365            .elements(model.evaluator.options().ctx)
366            .map(Some)
367            .map_err(|error| {
368                BindError::unsupported(format!(
369                    "SYMMETRY unused-set normalization: {}",
370                    error.message()
371                ))
372            });
373    }
374    Ok(None)
375}
376
377fn prepare_group(
378    declaration: &Declaration,
379    mode: Mode,
380    limits: Limits,
381) -> Result<Reduction, BindError> {
382    let mut universe = Vec::new();
383    let mut indices = HashMap::new();
384    let mut generators = Vec::new();
385    let mut work = 0usize;
386    for value in declaration.functions.iter() {
387        let Value::Fcn(fcn) = value else {
388            return Err(BindError::bug(
389                "validated symmetry function ceased to be a function",
390            ));
391        };
392        let mut pairs = Vec::new();
393        for (domain, range) in fcn.iter() {
394            work = work
395                .checked_add(1)
396                .ok_or_else(|| BindError::unsupported("SYMMETRY generator work limit"))?;
397            if work > limits.work {
398                return Err(BindError::unsupported("SYMMETRY generator work limit"));
399            }
400            let (Value::Model(domain), Value::Model(range)) = (&domain, range) else {
401                return Err(symmetry_runtime_error(
402                    "Symmetry function must have model values as domain and range.",
403                ));
404            };
405            let mut ids = [0usize; 2];
406            for (at, atom) in [domain, range].into_iter().enumerate() {
407                ids[at] = if let Some(index) = indices.get(atom) {
408                    *index
409                } else {
410                    if universe.len() >= limits.model_values {
411                        return Err(BindError::unsupported("SYMMETRY model-value limit"));
412                    }
413                    let index = universe.len();
414                    universe.push(atom.clone());
415                    indices.insert(atom.clone(), index);
416                    index
417                };
418            }
419            pairs.push((ids[0], ids[1]));
420        }
421        generators.push(pairs);
422    }
423    let group =
424        Group::from_generators(universe.len(), &generators, mode, limits).map_err(|error| {
425            BindError::unsupported(format!("SYMMETRY {}: {error}", declaration.name))
426        })?;
427    let typed = group
428        .maps()
429        .iter()
430        .map(|map| {
431            map.images()
432                .iter()
433                .enumerate()
434                .all(|(from, &to)| universe[from].mv_type() == universe[to].mv_type())
435        })
436        .collect();
437    Ok(Reduction {
438        universe,
439        indices,
440        group,
441        typed,
442        id: NEXT_REDUCTION.fetch_add(1, std::sync::atomic::Ordering::Relaxed),
443    })
444}
445
446impl Reduction {
447    /// The model values the closure permutes; a map's images index into it.
448    #[must_use]
449    pub fn universe(&self) -> &[Atom] {
450        &self.universe
451    }
452
453    /// The closure's nonidentity maps, in the order canonicalization tries
454    /// them (the state itself is the initial candidate).
455    #[must_use]
456    pub fn maps(&self) -> &[crate::symmetry::Permutation] {
457        self.group.maps()
458    }
459
460    /// Canonical values in the supplied variable order. The original values
461    /// remain the explored state. TLC mode compares each candidate in TLC's
462    /// argument order; canonical mode uses its approved total value order.
463    ///
464    /// # Errors
465    /// Values outside the implemented pure permutation representations, value
466    /// comparison errors, or the per-state permutation work/depth limit.
467    pub fn canonical_values(
468        &self,
469        values: &[Value],
470        variable_order: &[usize],
471        ctx: Ctx,
472    ) -> Result<Vec<Value>, BindError> {
473        if variable_order.len() != values.len()
474            || variable_order
475                .iter()
476                .enumerate()
477                .any(|(at, index)| *index >= values.len() || variable_order[..at].contains(index))
478        {
479            return Err(BindError::bug(
480                "symmetry variable order is not a permutation of the state slots",
481            ));
482        }
483        let mut best = values.to_vec();
484        let mut work = 0usize;
485        // Reuse the two complete state rows, as TLC does. An early-abandoned
486        // row is overwritten before it can become the new minimum.
487        let mut candidate = values.to_vec();
488        // Per slot: the elements of a set that may be compared without
489        // building its image (see `distinct_elements`), computed once.
490        let mut distinct: Vec<Option<Option<Distinct>>> = vec![None; values.len()];
491        // Slots compared equal without building their image, in order.
492        let mut unbuilt: Vec<usize> = Vec::new();
493        // The map whose image is the best row (`None`: the state itself),
494        // whether its images may be compared by rank, and per slot the rank
495        // ids of the best row's set, computed when first needed.
496        let mut best_from: Option<usize> = None;
497        let mut best_ranked = true;
498        let mut best_ids: Vec<Option<Option<Vec<u32>>>> = vec![None; values.len()];
499        for (at, map) in self.group.maps().iter().enumerate() {
500            let typed = self.typed.get(at).copied().unwrap_or(false);
501            let mut smaller = false;
502            unbuilt.clear();
503            for &index in variable_order {
504                let value = values
505                    .get(index)
506                    .ok_or_else(|| BindError::bug("symmetry variable order outside state"))?;
507                if !smaller && typed {
508                    if distinct[index].is_none() {
509                        distinct[index] = Some(self.distinct(value, ctx));
510                    }
511                    // A map that fixes an unnormalized set yields the set
512                    // itself, which the full comparison then normalizes.
513                    if let Some(Some(elements)) = &distinct[index]
514                        && !(elements.atoms.iter().all(|&i| map.image(i) == Some(i))
515                            && matches!(value, Value::Set(set) if !set.is_tlc_normalized()))
516                        && let Some(ordering) = self.compare_slot(
517                            elements,
518                            (at, map),
519                            &best[index],
520                            best_ranked
521                                .then(|| {
522                                    best_ids[index]
523                                        .get_or_insert_with(|| Self::rank_ids(elements, best_from))
524                                        .as_deref()
525                                })
526                                .flatten(),
527                            ctx,
528                            &mut work,
529                        )?
530                    {
531                        match ordering {
532                            Ordering::Greater => break,
533                            Ordering::Equal => {
534                                unbuilt.push(index);
535                                continue;
536                            }
537                            Ordering::Less => {
538                                unbuilt.push(index);
539                                self.build_unbuilt(
540                                    &unbuilt,
541                                    true,
542                                    values,
543                                    map,
544                                    (&mut candidate, &best),
545                                    ctx,
546                                    &mut work,
547                                )?;
548                                smaller = true;
549                                continue;
550                            }
551                        }
552                    }
553                }
554                candidate[index] = self.permute(value, map, ctx, 0, &mut work)?;
555                if !smaller {
556                    let ordering = compare_values(&candidate[index], &best[index], ctx)?;
557                    match ordering {
558                        Ordering::Greater => break,
559                        Ordering::Less => {
560                            self.build_unbuilt(
561                                &unbuilt,
562                                false,
563                                values,
564                                map,
565                                (&mut candidate, &best),
566                                ctx,
567                                &mut work,
568                            )?;
569                            smaller = true;
570                        }
571                        Ordering::Equal => {}
572                    }
573                }
574            }
575            if smaller {
576                std::mem::swap(&mut best, &mut candidate);
577                best_from = Some(at);
578                best_ranked = typed;
579                best_ids.fill(None);
580            }
581        }
582        Ok(best)
583    }
584
585    /// Compares a set slot's image under a map against the best row's slot
586    /// without building the image: by rank when the best slot's rank ids
587    /// are known, otherwise by value. `None` when `best` needs the full
588    /// comparison. Under TLC's order, comparing normalizes `best`'s set,
589    /// as `compareTo` does.
590    fn compare_slot(
591        &self,
592        elements: &Distinct,
593        (at, map): (usize, &Permutation),
594        best: &Value,
595        best_ids: Option<&[u32]>,
596        ctx: Ctx,
597        work: &mut usize,
598    ) -> Result<Option<Ordering>, BindError> {
599        *work = work.saturating_add(elements.elements.len());
600        if *work > 32_000_000 {
601            return Err(BindError::unsupported(
602                "SYMMETRY per-state permutation work/depth limit",
603            ));
604        }
605        if let Some(ids) = best_ids
606            && let Some(ordering) = Self::compare_ranks(elements, at, ids)
607        {
608            if ctx.order == ValueOrder::Tlc
609                && let Value::Set(set) = best
610            {
611                set.elements(ctx).map_err(|error| {
612                    BindError::unsupported(format!(
613                        "SYMMETRY candidate comparison: {}",
614                        error.message()
615                    ))
616                })?;
617            }
618            return Ok(Some(ordering));
619        }
620        self.compare_image(elements, at, map, best, ctx, work)
621    }
622
623    /// Compares the image of a set with `elements` under the map at `at`
624    /// against `best` without building it, or `None` when `best` needs the
625    /// full comparison.
626    fn compare_image(
627        &self,
628        elements: &Distinct,
629        at: usize,
630        map: &Permutation,
631        best: &Value,
632        ctx: Ctx,
633        work: &mut usize,
634    ) -> Result<Option<Ordering>, BindError> {
635        let mut fresh = Vec::new();
636        for (element, entry) in elements.elements.iter().zip(&elements.entries) {
637            if entry.images.get(at).and_then(Option::as_ref).is_none() {
638                fresh.push(self.permute(element, map, ctx, 1, work)?);
639            }
640        }
641        let mut fresh = fresh.iter();
642        let images = elements
643            .entries
644            .iter()
645            .map(|entry| {
646                entry
647                    .images
648                    .get(at)
649                    .and_then(Option::as_ref)
650                    .map(|(image, _)| image)
651                    .or_else(|| fresh.next())
652                    .ok_or_else(|| BindError::bug("SYMMETRY image cache lost an image"))
653            })
654            .collect::<Result<Vec<&Value>, _>>()?;
655        if ctx.order == ValueOrder::Tlc {
656            dive_value::tlc::compare_distinct_set(&images, best, ctx).map_err(|error| {
657                BindError::unsupported(format!(
658                    "SYMMETRY candidate comparison: {}",
659                    error.message()
660                ))
661            })
662        } else {
663            Ok(Value::cmp_distinct_set(&images, best, ctx.order))
664        }
665    }
666
667    /// The set slot's [`Distinct`] data, when its image may be compared
668    /// without building it.
669    fn distinct(&self, value: &Value, ctx: Ctx) -> Option<Distinct> {
670        let elements = distinct_elements(value, ctx)?;
671        let mut atoms = HashSet::new();
672        for element in elements.iter() {
673            self.collect_atoms(element, &mut atoms);
674        }
675        let mut atoms: Vec<usize> = atoms.into_iter().collect();
676        atoms.sort_unstable();
677        let (entries, generation) = self.cached_images(&elements, ctx);
678        Some(Distinct {
679            elements,
680            entries,
681            generation,
682            atoms,
683        })
684    }
685
686    /// The symmetric model values occurring in a set-free value.
687    fn collect_atoms(&self, value: &Value, atoms: &mut HashSet<usize>) {
688        match value {
689            Value::Model(atom) => {
690                if let Some(&index) = self.indices.get(atom) {
691                    atoms.insert(index);
692                }
693            }
694            Value::Fcn(function) => {
695                if let Some(tuple) = function.as_tuple() {
696                    for v in tuple {
697                        self.collect_atoms(v, atoms);
698                    }
699                } else if let Some(fields) = function.as_record() {
700                    for (_, v) in fields {
701                        self.collect_atoms(v, atoms);
702                    }
703                } else {
704                    for (domain, range) in function.iter() {
705                        self.collect_atoms(&domain, atoms);
706                        self.collect_atoms(range, atoms);
707                    }
708                }
709            }
710            _ => {}
711        }
712    }
713
714    /// The cache entries of `elements`, from this thread's cache, and the
715    /// generation that issued their rank ids.
716    fn cached_images(&self, elements: &[Value], ctx: Ctx) -> (Vec<Arc<Entry>>, u64) {
717        IMAGES.with(|cache| {
718            let mut cache = cache.borrow_mut();
719            if cache.owner != Some((self.id, ctx)) {
720                let generation = cache.generation + 1;
721                *cache = ImageCache {
722                    owner: Some((self.id, ctx)),
723                    generation,
724                    ..ImageCache::default()
725                };
726            }
727            if cache
728                .held
729                .saturating_add(elements.len() * (self.group.maps().len() + 1))
730                > IMAGE_CACHE_LIMIT
731            {
732                let generation = cache.generation + 1;
733                *cache = ImageCache {
734                    owner: cache.owner,
735                    generation,
736                    ..ImageCache::default()
737                };
738            }
739            let entries = elements
740                .iter()
741                .map(|element| {
742                    let key = Exact(element.clone());
743                    if let Some(entry) = cache.images.get(&key) {
744                        return entry.clone();
745                    }
746                    let images = self
747                        .group
748                        .maps()
749                        .iter()
750                        .map(|map| {
751                            let image = self.permute(element, map, ctx, 1, &mut 0).ok()?;
752                            let id = cache.rank_id(&image, ctx.order);
753                            Some((image, id))
754                        })
755                        .collect();
756                    let entry = Arc::new(Entry {
757                        key: cache.rank_id(element, ctx.order),
758                        images,
759                    });
760                    cache.held += self.group.maps().len() + 1;
761                    cache.images.insert(key, entry.clone());
762                    entry
763                })
764                .collect();
765            (entries, cache.generation)
766        })
767    }
768
769    /// The image of a set slot under the map at `at` against the best
770    /// representative's slot, both given by rank ids, or `None` when either
771    /// lacks them. `best` holds the best slot's rank ids in ascending order.
772    fn compare_ranks(elements: &Distinct, at: usize, best: &[u32]) -> Option<Ordering> {
773        thread_local! {
774            static MINE: std::cell::RefCell<Vec<u64>> = const { std::cell::RefCell::new(Vec::new()) };
775        }
776        if elements.entries.len() != best.len() {
777            return None;
778        }
779        IMAGES.with(|cache| {
780            let cache = cache.borrow();
781            if cache.generation != elements.generation {
782                return None;
783            }
784            let rank = |id: u32| cache.rank.get(id as usize).copied();
785            MINE.with(|mine| {
786                let mut mine = mine.borrow_mut();
787                mine.clear();
788                for entry in &elements.entries {
789                    mine.push(rank(entry.images.get(at)?.as_ref()?.1)?);
790                }
791                mine.sort_unstable();
792                for (m, b) in mine.iter().zip(best) {
793                    let c = m.cmp(&rank(*b)?);
794                    if c != Ordering::Equal {
795                        return Some(c);
796                    }
797                }
798                Some(Ordering::Equal)
799            })
800        })
801    }
802
803    /// The rank ids of a set slot's image under the map at `at` (the
804    /// elements themselves for `None`), in ascending rank order.
805    fn rank_ids(elements: &Distinct, at: Option<usize>) -> Option<Vec<u32>> {
806        let mut ids = elements
807            .entries
808            .iter()
809            .map(|entry| match at {
810                None => Some(entry.key),
811                Some(at) => Some(entry.images.get(at)?.as_ref()?.1),
812            })
813            .collect::<Option<Vec<u32>>>()?;
814        IMAGES.with(|cache| {
815            let cache = cache.borrow();
816            if cache.generation != elements.generation {
817                return None;
818            }
819            let rank = |id: u32| cache.rank.get(id as usize).copied().unwrap_or(u64::MAX);
820            ids.sort_unstable_by_key(|id| rank(*id));
821            Some(ids)
822        })
823    }
824
825    /// Builds the images of the slots that were compared without them, once
826    /// the candidate is known to be smaller, and repeats their comparisons on
827    /// the built values: the same comparisons, with the same normalizations,
828    /// as if they had been built in the first place. When `last_less`, the
829    /// last slot decided `Less`; every other slot compared equal.
830    #[allow(
831        clippy::too_many_arguments,
832        reason = "the two state rows travel together with the map and work counter"
833    )]
834    fn build_unbuilt(
835        &self,
836        unbuilt: &[usize],
837        last_less: bool,
838        values: &[Value],
839        map: &Permutation,
840        (candidate, best): (&mut [Value], &[Value]),
841        ctx: Ctx,
842        work: &mut usize,
843    ) -> Result<(), BindError> {
844        for &index in unbuilt {
845            let value = values
846                .get(index)
847                .ok_or_else(|| BindError::bug("symmetry variable order outside state"))?;
848            candidate[index] = self.permute(value, map, ctx, 0, work)?;
849            let ordering = compare_values(&candidate[index], &best[index], ctx)?;
850            let expected = if last_less && Some(&index) == unbuilt.last() {
851                Ordering::Less
852            } else {
853                Ordering::Equal
854            };
855            if ordering != expected {
856                return Err(BindError::bug(
857                    "SYMMETRY image comparison disagrees with the built image",
858                ));
859            }
860        }
861        Ok(())
862    }
863
864    /// TLC deep-normalizes the concrete source after selecting another
865    /// representative, and before evaluating a VIEW even when identity wins.
866    /// This preserves normalization observed by subsequent enumeration.
867    ///
868    /// # Errors
869    /// A value normalization error or the same bounded work/depth refusal.
870    pub fn normalize_concrete(values: &[Value], ctx: Ctx) -> Result<(), BindError> {
871        let mut work = 0usize;
872        for value in values {
873            deep_normalize(value, ctx, 0, &mut work)?;
874        }
875        Ok(())
876    }
877
878    fn permute(
879        &self,
880        value: &Value,
881        map: &Permutation,
882        ctx: Ctx,
883        depth: usize,
884        work: &mut usize,
885    ) -> Result<Value, BindError> {
886        *work = work
887            .checked_add(1)
888            .ok_or_else(|| BindError::unsupported("SYMMETRY permutation work limit"))?;
889        if *work > 32_000_000 || depth > 256 {
890            return Err(BindError::unsupported(
891                "SYMMETRY per-state permutation work/depth limit",
892            ));
893        }
894        let recur =
895            |value: &Value, work: &mut usize| self.permute(value, map, ctx, depth + 1, work);
896        let map_error = |error: dive_value::ValueError| {
897            BindError::unsupported(format!("SYMMETRY value permutation: {}", error.message()))
898        };
899        match value {
900            Value::Model(atom) => Ok(self
901                .indices
902                .get(atom)
903                .and_then(|&i| map.image(i))
904                .and_then(|i| self.universe.get(i))
905                .map_or_else(|| value.clone(), |atom| Value::Model(atom.clone()))),
906            Value::Fcn(function) => permute_function(function, ctx, |value| recur(value, work)),
907            Value::Set(set) => match set.kind() {
908                SetKind::Enum | SetKind::Raw => {
909                    let elements = match set.raw_elements() {
910                        Some(elements) => Arc::from(elements),
911                        None => set.elements(ctx).map_err(map_error)?,
912                    };
913                    if elements.len() > 32_000_000usize.saturating_sub(*work) {
914                        return Err(BindError::unsupported(
915                            "SYMMETRY set permutation work limit",
916                        ));
917                    }
918                    let permuted = elements
919                        .iter()
920                        .map(|value| recur(value, work))
921                        .collect::<Result<Vec<_>, _>>()?;
922                    if elements
923                        .iter()
924                        .zip(&permuted)
925                        .all(|(before, after)| same_value(before, after))
926                    {
927                        Ok(value.clone())
928                    } else {
929                        Ok(Value::set_raw(permuted, ctx))
930                    }
931                }
932                SetKind::Interval => Ok(value.clone()),
933                _ => Err(BindError::unsupported(format!(
934                    "SYMMETRY permutation of lazy {:?} values",
935                    set.kind()
936                ))),
937            },
938            _ => Ok(value.clone()),
939        }
940    }
941}
942
943fn permute_function(
944    function: &dive_value::Fcn,
945    ctx: Ctx,
946    mut recur: impl FnMut(&Value) -> Result<Value, BindError>,
947) -> Result<Value, BindError> {
948    let map_error = |error: dive_value::ValueError| {
949        BindError::unsupported(format!("SYMMETRY value permutation: {}", error.message()))
950    };
951    if let Some(tuple) = function.as_tuple() {
952        let values = tuple
953            .iter()
954            .map(&mut recur)
955            .collect::<Result<Vec<_>, _>>()?;
956        if tuple
957            .iter()
958            .zip(&values)
959            .all(|(before, after)| same_value(before, after))
960        {
961            return Ok(Value::Fcn(function.clone()));
962        }
963        return Ok(if function.is_tuple_literal() {
964            Value::tuple(values)
965        } else {
966            Value::tuple_fcn(values)
967        });
968    }
969    if function.is_record_literal() {
970        let fields = function
971            .as_record()
972            .ok_or_else(|| BindError::bug("record has no fields"))?
973            .iter()
974            .map(|(name, value)| Ok((name.clone(), recur(value)?)))
975            .collect::<Result<Vec<_>, BindError>>()?;
976        if function.as_record().is_some_and(|original| {
977            original
978                .iter()
979                .zip(&fields)
980                .all(|((_, before), (_, after))| same_value(before, after))
981        }) {
982            return Ok(Value::Fcn(function.clone()));
983        }
984        return Value::record(fields, ctx).map_err(map_error);
985    }
986    // FcnRcdValue.permute visits every range before any domain.
987    let ranges = function
988        .iter()
989        .map(|(_, range)| recur(range))
990        .collect::<Result<Vec<_>, BindError>>()?;
991    let pairs = function
992        .iter()
993        .zip(ranges)
994        .map(|((domain, _), range)| Ok((recur(&domain)?, range)))
995        .collect::<Result<Vec<_>, BindError>>()?;
996    if function
997        .iter()
998        .zip(&pairs)
999        .all(|((domain, before), (image, after))| {
1000            same_value(&domain, image) && same_value(before, after)
1001        })
1002    {
1003        return Ok(Value::Fcn(function.clone()));
1004    }
1005    Value::fcn(pairs, ctx).map_err(map_error)
1006}
1007
1008fn deep_normalize(
1009    value: &Value,
1010    ctx: Ctx,
1011    depth: usize,
1012    work: &mut usize,
1013) -> Result<(), BindError> {
1014    *work = work
1015        .checked_add(1)
1016        .ok_or_else(|| BindError::unsupported("SYMMETRY normalization work limit"))?;
1017    if *work > 32_000_000 || depth > 256 {
1018        return Err(BindError::unsupported(
1019            "SYMMETRY normalization work/depth limit",
1020        ));
1021    }
1022    match value {
1023        Value::Set(set) if matches!(set.kind(), SetKind::Enum | SetKind::Raw) => {
1024            // Children first, as SetEnumValue.deepNormalize. Reading raw values
1025            // here must not sort the parent before its children are normalized.
1026            if let Some(raw) = set.raw_elements() {
1027                for child in raw {
1028                    deep_normalize(child, ctx, depth + 1, work)?;
1029                }
1030            } else {
1031                for child in set
1032                    .elements(ctx)
1033                    .map_err(|e| {
1034                        BindError::unsupported(format!(
1035                            "SYMMETRY deep normalization: {}",
1036                            e.message()
1037                        ))
1038                    })?
1039                    .iter()
1040                {
1041                    deep_normalize(child, ctx, depth + 1, work)?;
1042                }
1043            }
1044            set.elements(ctx).map_err(|e| {
1045                BindError::unsupported(format!("SYMMETRY deep normalization: {}", e.message()))
1046            })?;
1047        }
1048        Value::Fcn(fcn) => {
1049            for (_, child) in fcn.iter() {
1050                deep_normalize(child, ctx, depth + 1, work)?;
1051            }
1052        }
1053        Value::Set(set) if set.as_deferred().is_some() => {
1054            let operand = set
1055                .as_deferred()
1056                .and_then(|provider| {
1057                    dive_eval::deferred_filter_normalization_operand(provider.as_ref())
1058                })
1059                .ok_or_else(|| {
1060                    BindError::unsupported(
1061                        "SYMMETRY deep normalization of unproved deferred values",
1062                    )
1063                })?;
1064            // SetPredValue visits only inVal, never its predicate. Unknown
1065            // providers and unproved lazy-operation caches remain refused
1066            // without invoking any provider method.
1067            deep_normalize(operand, ctx, depth + 1, work)?;
1068        }
1069        Value::Set(set) => {
1070            for (_, child) in set.components() {
1071                deep_normalize(&child, ctx, depth + 1, work)?;
1072            }
1073        }
1074        _ => {}
1075    }
1076    Ok(())
1077}
1078
1079// TLC's permute methods retain the original object only when every child keeps
1080// identity. Extensional equality is insufficient: an invariant set may still
1081// have changed its raw element order, observable until normalization.
1082fn same_value(before: &Value, after: &Value) -> bool {
1083    match (before, after) {
1084        (Value::Set(a), Value::Set(b)) => a.ptr_eq(b),
1085        (Value::Fcn(a), Value::Fcn(b)) => a.ptr_eq(b),
1086        _ => before == after,
1087    }
1088}
1089
1090/// A set slot whose image is compared without building it: its normalized
1091/// elements, each element's cache entry, and the cache generation that
1092/// issued their rank ids.
1093#[derive(Clone)]
1094struct Distinct {
1095    elements: Arc<[Value]>,
1096    entries: Vec<Arc<Entry>>,
1097    generation: u64,
1098    /// The symmetric model values occurring in the elements.
1099    atoms: Vec<usize>,
1100}
1101
1102/// The candidate-against-best comparison: TLC's `compareTo` in TLC mode, the
1103/// approved total value order otherwise.
1104fn compare_values(candidate: &Value, best: &Value, ctx: Ctx) -> Result<Ordering, BindError> {
1105    if ctx.order == ValueOrder::Tlc {
1106        dive_value::tlc::compare(candidate, best, ctx).map_err(|error| {
1107            BindError::unsupported(format!(
1108                "SYMMETRY candidate comparison: {}",
1109                error.message()
1110            ))
1111        })
1112    } else {
1113        Ok(candidate.cmp_with(best, ctx.order))
1114    }
1115}
1116
1117/// The normalized elements of `value` when it is an enumerated set whose
1118/// image can be compared without building it: no set occurs inside its
1119/// elements, so comparing them normalizes nothing, and the elements are
1120/// mutually comparable, so normalizing the image only sorts it. A map that
1121/// preserves model-value types keeps both properties and, being injective,
1122/// keeps the elements distinct. Reading the elements changes nothing TLC can
1123/// observe; the full comparison normalizes the same sets.
1124fn distinct_elements(value: &Value, ctx: Ctx) -> Option<Arc<[Value]>> {
1125    let Value::Set(set) = value else {
1126        return None;
1127    };
1128    if !matches!(set.kind(), SetKind::Enum | SetKind::Raw) {
1129        return None;
1130    }
1131    let elements = set.peek_elements(ctx).ok()?;
1132    let mut budget = 1_000_000usize;
1133    (elements
1134        .iter()
1135        .all(|element| set_free(element, 1, &mut budget))
1136        && Value::elements_comparable(&elements))
1137    .then_some(elements)
1138}
1139
1140/// Whether no set occurs in `value`, within a work budget and the depth
1141/// limit of [`Reduction::permute`].
1142fn set_free(value: &Value, depth: usize, budget: &mut usize) -> bool {
1143    if *budget == 0 || depth > 256 {
1144        return false;
1145    }
1146    *budget -= 1;
1147    match value {
1148        Value::Set(_) => false,
1149        Value::Fcn(function) => {
1150            if let Some(tuple) = function.as_tuple() {
1151                tuple.iter().all(|v| set_free(v, depth + 1, budget))
1152            } else if let Some(fields) = function.as_record() {
1153                fields.iter().all(|(_, v)| set_free(v, depth + 1, budget))
1154            } else {
1155                function.iter().all(|(domain, range)| {
1156                    set_free(&domain, depth + 1, budget) && set_free(range, depth + 1, budget)
1157                })
1158            }
1159        }
1160        _ => true,
1161    }
1162}
1163
1164#[cfg(test)]
1165mod tests {
1166    #![allow(clippy::unwrap_used, reason = "test fixtures")]
1167
1168    use super::*;
1169    use dive_value::Interner;
1170
1171    /// The search before images were compared without building them: every
1172    /// candidate slot is permuted and compared in full.
1173    fn reference(
1174        reduction: &Reduction,
1175        values: &[Value],
1176        order: &[usize],
1177        ctx: Ctx,
1178    ) -> Result<Vec<Value>, BindError> {
1179        let mut best = values.to_vec();
1180        let mut work = 0usize;
1181        let mut candidate = values.to_vec();
1182        for map in reduction.group.maps() {
1183            let mut smaller = false;
1184            for &index in order {
1185                candidate[index] = reduction.permute(&values[index], map, ctx, 0, &mut work)?;
1186                if !smaller {
1187                    match compare_values(&candidate[index], &best[index], ctx)? {
1188                        Ordering::Greater => break,
1189                        Ordering::Less => smaller = true,
1190                        Ordering::Equal => {}
1191                    }
1192                }
1193            }
1194            if smaller {
1195                std::mem::swap(&mut best, &mut candidate);
1196            }
1197        }
1198        Ok(best)
1199    }
1200
1201    struct Rng(u64);
1202
1203    impl Rng {
1204        fn below(&mut self, n: u64) -> u64 {
1205            self.0 ^= self.0 << 13;
1206            self.0 ^= self.0 >> 7;
1207            self.0 ^= self.0 << 17;
1208            self.0 % n
1209        }
1210    }
1211
1212    fn reduction(names: &Interner, atoms: &[&str]) -> Reduction {
1213        let universe: Vec<Atom> = atoms.iter().map(|a| names.intern(a)).collect();
1214        let indices = universe
1215            .iter()
1216            .enumerate()
1217            .map(|(i, a)| (a.clone(), i))
1218            .collect();
1219        // Transpositions of neighbours generate every permutation.
1220        let generators: Vec<Vec<(usize, usize)>> = (0..universe.len() - 1)
1221            .map(|i| vec![(i, i + 1), (i + 1, i)])
1222            .collect();
1223        let group =
1224            Group::from_generators(universe.len(), &generators, Mode::Tlc, Limits::default())
1225                .unwrap();
1226        let typed = vec![true; group.maps().len()];
1227        Reduction {
1228            universe,
1229            indices,
1230            group,
1231            typed,
1232            id: NEXT_REDUCTION.fetch_add(1, std::sync::atomic::Ordering::Relaxed),
1233        }
1234    }
1235
1236    /// A state with flat record sets of two shapes, tuple sets, a function
1237    /// keyed by model values, a scalar and a set of sets (the full path).
1238    fn state(names: &Interner, rng: &mut Rng, ctx: Ctx) -> Vec<Value> {
1239        let mv = |rng: &mut Rng| Value::model(names, &format!("m{}", rng.below(4)));
1240        let mut records = Vec::new();
1241        for _ in 0..rng.below(9) {
1242            let mut fields = vec![
1243                (names.intern("type"), Value::string(names, "a")),
1244                (
1245                    names.intern("b"),
1246                    Value::Int(i64::try_from(rng.below(3)).unwrap()),
1247                ),
1248                (names.intern("v"), mv(rng)),
1249            ];
1250            if rng.below(2) == 0 {
1251                fields[0].1 = Value::string(names, "b");
1252                fields.push((names.intern("acc"), mv(rng)));
1253            }
1254            records.push(Value::record(fields, ctx).unwrap());
1255        }
1256        let tuples = (0..rng.below(6))
1257            .map(|_| {
1258                Value::tuple(vec![
1259                    mv(rng),
1260                    Value::Int(i64::try_from(rng.below(2)).unwrap()),
1261                ])
1262            })
1263            .collect();
1264        let function = Value::fcn(
1265            (0..4)
1266                .map(|i| {
1267                    (
1268                        Value::model(names, &format!("m{i}")),
1269                        Value::Int(i64::try_from(rng.below(2)).unwrap()),
1270                    )
1271                })
1272                .collect(),
1273            ctx,
1274        )
1275        .unwrap();
1276        let nested = (0..rng.below(3))
1277            .map(|_| Value::set_raw(vec![mv(rng), mv(rng)], ctx))
1278            .collect();
1279        let functions = (0..rng.below(4))
1280            .map(|_| {
1281                let mut pairs = vec![(mv(rng), Value::Int(1))];
1282                let other = mv(rng);
1283                if pairs[0].0 != other {
1284                    pairs.push((other, Value::Int(2)));
1285                }
1286                Value::fcn(pairs, ctx).unwrap()
1287            })
1288            .collect();
1289        vec![
1290            Value::set_raw(records, ctx),
1291            Value::set_raw(functions, ctx),
1292            mv(rng),
1293            Value::set_raw(tuples, ctx),
1294            function,
1295            Value::set_raw(nested, ctx),
1296        ]
1297    }
1298
1299    fn normalized(values: &[Value]) -> Vec<bool> {
1300        values
1301            .iter()
1302            .map(|v| matches!(v, Value::Set(s) if s.is_tlc_normalized()))
1303            .collect()
1304    }
1305
1306    #[test]
1307    fn unbuilt_images_choose_the_reference_representative() {
1308        for ctx in [Ctx::tlc(), Ctx::default()] {
1309            let names = Interner::new();
1310            for a in ["m0", "m1", "m2", "m3", "type", "b", "v", "acc", "a"] {
1311                names.intern(a);
1312            }
1313            let reduction = reduction(&names, &["m0", "m1", "m2", "m3"]);
1314            for order in [
1315                [0usize, 1, 2, 3, 4, 5],
1316                [2, 4, 0, 5, 3, 1],
1317                [5, 3, 1, 0, 2, 4],
1318            ] {
1319                let mut rng = Rng(0x9e37_79b9_7f4a_7c15);
1320                for _ in 0..300 {
1321                    let seed = rng.0;
1322                    let mine = state(&names, &mut Rng(seed), ctx);
1323                    let theirs = state(&names, &mut Rng(seed), ctx);
1324                    rng.below(2);
1325                    let got = reduction.canonical_values(&mine, &order, ctx).unwrap();
1326                    let want = reference(&reduction, &theirs, &order, ctx).unwrap();
1327                    assert_eq!(got, want, "order {order:?}, seed {seed}");
1328                    assert_eq!(
1329                        normalized(&mine),
1330                        normalized(&theirs),
1331                        "ctx {ctx:?} order {order:?} seed {seed} state {theirs:?} best {want:?}"
1332                    );
1333                    assert_eq!(
1334                        normalized(&got),
1335                        normalized(&want),
1336                        "ctx {ctx:?} order {order:?} seed {seed} got {got:?}"
1337                    );
1338                }
1339            }
1340        }
1341    }
1342}