Skip to main content

dive_model/
symmetry.rs

1//! Pure symmetry declaration preparation, bounded closure and safety keys.
2//!
3//! This matches `MVPerms.permutationSubgroup` and `MVPerm.compose` at the
4//! pinned TLC revision. Preparation handles supported tool-level warnings;
5//! activation and concrete trace retention belong to the checker. Liveness and
6//! random symmetry interactions still require separate implementations.
7//! Indices refer to one caller-supplied table of model values, not intern tokens.
8
9mod liveness;
10mod prepare;
11pub use liveness::{SymmetryLiveness, SymmetryLivenessResolution};
12
13pub use prepare::{Prepared, Reduction};
14
15use std::collections::HashSet;
16use std::fmt;
17use std::sync::Arc;
18
19use dive_eval::{ErrorClass, St};
20use dive_ir::{Effects, Level};
21use dive_value::{SetKind, Value};
22
23use crate::tables::Look;
24use crate::{BindError, Ec, Model, Pred};
25
26/// A pure symmetry declaration before warning, model-value and closure checks.
27///
28/// This is an intermediate startup stage, not permission to reduce states.
29/// `Tool.getSymmetryPerms` validates all function representations before its
30/// too-small heuristic; domain/range and closure checks follow that heuristic.
31#[derive(Clone, Debug)]
32pub struct Declaration {
33    /// The configuration's name.
34    pub name: String,
35    /// The original definition body, evaluated rather than its cached value.
36    pub predicate: Pred,
37    /// Function records in normalized run order, including identities.
38    pub functions: Arc<[Value]>,
39}
40
41impl Model {
42    /// Reads the configured pure symmetry definition from TLC's pre-constant
43    /// name-table snapshot and validates its set/function representations.
44    /// Call once during startup, before checking. This does not build the
45    /// group, issue too-small warnings or lift any checking refusal.
46    ///
47    /// # Example
48    /// ```
49    /// # use std::sync::Arc;
50    /// # use dive_model::{BindOptions, bind};
51    /// let source = "---- MODULE M ----\nEXTENDS TLC\nCONSTANT S\nVARIABLE x\n\
52    ///               Init == x = TRUE\nNext == UNCHANGED x\n\
53    ///               Sym == Permutations(S)\n====\n";
54    /// let analysis = dive_sema::analyze_source("M.tla", source, &dive_sema::Options::default());
55    /// let ir = Arc::new(dive_ir::lower(&analysis).unwrap());
56    /// let cfg = dive_config::parse("CONSTANT S={a,b}\nINIT Init\nNEXT Next\nSYMMETRY Sym\n")
57    ///     .into_config().unwrap();
58    /// let model = bind(ir, &cfg, &BindOptions::tlc()).unwrap();
59    /// let declaration = model.symmetry_declaration().unwrap().unwrap();
60    /// assert_eq!(declaration.functions.len(), 2);
61    /// assert!(!model.unsupported.is_empty()); // reduction remains unsupported
62    /// ```
63    ///
64    /// # Errors
65    /// TLC's proved name/type, division-by-zero and set-comparison diagnostics;
66    /// explicit refusals for unverified
67    /// evaluation/normalization startup errors, or effectful, nonconstant and
68    /// parameterized declarations. Domain/range
69    /// validation, warning construction and kernel exceptions are later stages.
70    pub fn symmetry_declaration(&self) -> Result<Option<Declaration>, BindError> {
71        let Some(name) = self.symmetry.as_ref() else {
72            return Ok(None);
73        };
74        let definition = match &self.symmetry_definition {
75            None => {
76                return Err(BindError::tlc(
77                    Ec::TlcConfigSpecifiedNotDefined,
78                    &["symmetry function", name],
79                ));
80            }
81            Some(Look::Def(definition)) => *definition,
82            Some(_) => {
83                return Err(symmetry_runtime_error(&format!(
84                    "The symmetry function {name} must specify a set of permutations."
85                )));
86            }
87        };
88        let def = self.ir.def(definition);
89        let node = self.ir.node(def.body);
90        if !def.params.is_empty()
91            || node.level != Level::Constant
92            || node.effects.intersects(Effects::IMPURE)
93        {
94            return Err(BindError::unsupported(format!(
95                "effectful, nonconstant or parameterized SYMMETRY {name} at {}",
96                self.ir.location(&node.origin)
97            )));
98        }
99        let predicate = Pred::new(
100            def.body,
101            self.evaluator
102                .scope(definition)
103                .map_err(|e| BindError::unsupported(e.to_string()))?,
104        );
105        let value =
106            self.eval(&predicate, &St::constant())
107                .map_err(|error| match error.class() {
108                    ErrorClass::Unsupported | ErrorClass::ResourceLimit => {
109                        BindError::unsupported(format!("SYMMETRY {name}: {}", error.message()))
110                    }
111                    ErrorClass::Bug | ErrorClass::Interrupted => {
112                        BindError::bug(format!("SYMMETRY {name}: {}", error.message()))
113                    }
114                    ErrorClass::Eval
115                        if error.ec() == dive_eval::Ec::DivisionByZero
116                            && error.is_eval_exception() =>
117                    {
118                        // Tool.getSymmetryPerms evaluates before assumptions;
119                        // TLC's outer catch reports this EvalException as GENERAL.
120                        symmetry_exception("tlc2.tool.EvalException", &error.tool_text())
121                    }
122                    ErrorClass::Eval => BindError::unsupported(format!(
123                        "SYMMETRY {name} declaration evaluation error ({}): {}",
124                        error.ec().code(),
125                        error.message()
126                    )),
127                })?;
128        let Value::Set(set) = value else {
129            return Err(symmetry_runtime_error(
130                "The symmetry operator must specify a set of functions.",
131            ));
132        };
133        if !matches!(set.kind(), SetKind::Enum | SetKind::Raw) {
134            return Err(symmetry_runtime_error(
135                "The symmetry operator must specify a set of functions.",
136            ));
137        }
138        let functions = set
139            .elements(self.evaluator.options().ctx)
140            .map_err(|error| match error.kind() {
141                dive_value::ErrorKind::Codec => BindError::bug(format!(
142                    "SYMMETRY {name} set normalization: {}",
143                    error.message()
144                )),
145                dive_value::ErrorKind::Incomparable => symmetry_runtime_error(error.message()),
146                _ => BindError::unsupported(format!(
147                    "SYMMETRY {name} set normalization: {}",
148                    error.message()
149                )),
150            })?;
151        if functions.iter().any(|value| match value {
152            Value::Fcn(function) => function.is_tuple_literal() || function.is_record_literal(),
153            _ => true,
154        }) {
155            return Err(symmetry_runtime_error(
156                "The symmetry values must be function records.",
157            ));
158        }
159        Ok(Some(Declaration {
160            name: name.clone(),
161            predicate,
162            functions,
163        }))
164    }
165}
166
167fn symmetry_runtime_error(message: &str) -> BindError {
168    symmetry_exception("java.lang.RuntimeException", message)
169}
170
171// MP.ECGeneralMsg disguises Assert.TLCRuntimeException as RuntimeException,
172// while an EvalException retains its real class. Other exception families
173// remain unsupported until their startup classification has been measured.
174fn symmetry_exception(class: &str, message: &str) -> BindError {
175    BindError::tlc(
176        Ec::General,
177        &[&format!(
178            "TLC threw an unexpected exception.\nThis was probably caused by an error in the spec or model.\nSee the User Output or TLC Console for clues to what happened.\nThe exception was a {class}\n: {message}"
179        )],
180    )
181}
182
183/// Validation of a declared symmetry function.
184#[derive(Clone, Copy, Debug, PartialEq, Eq)]
185pub enum Mode {
186    /// Require a bijection after extending omitted model values by identity.
187    Checked,
188    /// Preserve TLC's acceptance of non-bijective functions.
189    Tlc,
190}
191
192/// Hard resource bounds. A refusal never returns a partial closure.
193#[derive(Clone, Copy, Debug)]
194pub struct Limits {
195    /// Maximum model-value universe size.
196    pub model_values: usize,
197    /// Maximum retained nonidentity maps.
198    pub maps: usize,
199    /// Maximum retained dense cells plus one working row.
200    pub cells: usize,
201    /// Maximum input-pair, dense-row and composition work units.
202    pub work: usize,
203}
204
205impl Default for Limits {
206    fn default() -> Self {
207        Self {
208            model_values: 4096,
209            maps: 4096,
210            cells: 1_000_000,
211            work: 32_000_000,
212        }
213    }
214}
215
216/// An invalid declaration or an exhausted resource bound.
217#[derive(Clone, Debug, PartialEq, Eq)]
218pub enum Error {
219    /// TLC's closure kernel requires at least two supplied functions.
220    TooFewGenerators,
221    /// A domain or range index is outside the supplied universe.
222    UnknownModelValue,
223    /// The supplied function has two entries for one domain element.
224    DuplicateDomain,
225    /// The total map, including omitted identities, is not bijective.
226    NonBijective,
227    /// The named resource bound was exceeded.
228    Limit(&'static str),
229}
230
231impl fmt::Display for Error {
232    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
233        match self {
234            Self::TooFewGenerators => {
235                f.write_str("symmetry generator set has fewer than two functions")
236            }
237            Self::UnknownModelValue => f.write_str("symmetry index outside model-value universe"),
238            Self::DuplicateDomain => f.write_str("duplicate symmetry function domain"),
239            Self::NonBijective => f.write_str("symmetry function is not bijective"),
240            Self::Limit(name) => write!(f, "symmetry resource limit: {name}"),
241        }
242    }
243}
244
245impl std::error::Error for Error {}
246
247/// A total map of the model-value universe, with implicit identities made explicit.
248#[derive(Clone, Debug, PartialEq, Eq)]
249pub struct Permutation {
250    images: Arc<Vec<usize>>,
251}
252
253impl Permutation {
254    /// The image of a model-value index, including identity images.
255    #[must_use]
256    pub fn image(&self, index: usize) -> Option<usize> {
257        self.images.get(index).copied()
258    }
259
260    /// Images in the caller's model-value order.
261    #[must_use]
262    pub fn images(&self) -> &[usize] {
263        self.images.as_slice()
264    }
265}
266
267/// Nonidentity maps in TLC's insertion order.
268///
269/// In [`Mode::Tlc`], malformed generators can produce a finite semigroup
270/// rather than a group.
271#[derive(Clone, Debug)]
272pub struct Group {
273    maps: Vec<Permutation>,
274}
275
276impl Group {
277    /// Closes normalized generator functions under TLC's composition order.
278    /// Generators are consumed in the supplied order; identities and duplicates
279    /// are dropped. Composing `a` with `b` applies `a` first, then `b`.
280    ///
281    /// Omitted domain indices map to themselves. Each supplied function must
282    /// have unique domain entries even in TLC mode: the input represents an
283    /// already normalized function. The caller must enumerate the source set
284    /// in the run's value order before calling this kernel.
285    ///
286    /// # Example
287    ///
288    /// ```
289    /// use dive_model::symmetry::{Group, Limits, Mode};
290    /// let generators = vec![vec![(0, 1), (1, 0)], vec![(2, 3), (3, 2)]];
291    /// let group = Group::from_generators(4, &generators, Mode::Checked, Limits::default())?;
292    /// // Two independent swaps generate three nonidentity maps.
293    /// assert_eq!(group.maps().len(), 3);
294    /// assert_eq!(group.maps()[2].images(), [1, 0, 3, 2]);
295    /// # Ok::<(), dive_model::symmetry::Error>(())
296    /// ```
297    ///
298    /// # Errors
299    /// Fewer than two supplied functions, invalid indices, duplicate domains,
300    /// non-bijections in checked mode, or
301    /// a named resource refusal. No partial group is exposed on failure.
302    pub fn from_generators(
303        universe: usize,
304        generators: &[Vec<(usize, usize)>],
305        mode: Mode,
306        limits: Limits,
307    ) -> Result<Self, Error> {
308        if generators.len() < 2 {
309            return Err(Error::TooFewGenerators);
310        }
311        if universe > limits.model_values {
312            return Err(Error::Limit("model values"));
313        }
314        let mut builder = Builder {
315            universe,
316            limits,
317            work: 0,
318            maps: Vec::new(),
319            seen: HashSet::new(),
320        };
321        for generator in generators {
322            builder.charge(1)?;
323            builder.scratch()?;
324            builder.charge(universe)?;
325            let mut row: Vec<usize> = (0..universe).collect();
326            // Input-domain validation is temporary O(universe) metadata.
327            let mut assigned = HashSet::new();
328            for &(domain, range) in generator {
329                builder.charge(1)?;
330                if domain >= universe || range >= universe {
331                    return Err(Error::UnknownModelValue);
332                }
333                if !assigned.insert(domain) {
334                    return Err(Error::DuplicateDomain);
335                }
336                row[domain] = range;
337            }
338            if mode == Mode::Checked {
339                builder.charge(universe)?;
340                let images: HashSet<usize> = row.iter().copied().collect();
341                if images.len() != universe {
342                    return Err(Error::NonBijective);
343                }
344            }
345            builder.insert(row)?;
346        }
347        let generators = builder.maps.len();
348        let mut begin = 0;
349        loop {
350            let end = builder.maps.len();
351            for i in 0..generators {
352                for j in begin..end {
353                    builder.charge(1)?;
354                    builder.scratch()?;
355                    builder.charge(universe)?;
356                    let first = &builder.maps[i].images;
357                    let second = &builder.maps[j].images;
358                    let row = first.iter().map(|&image| second[image]).collect();
359                    builder.insert(row)?;
360                }
361            }
362            if end == builder.maps.len() {
363                break;
364            }
365            begin = end;
366        }
367        Ok(Self { maps: builder.maps })
368    }
369
370    /// Nonidentity maps. Identity remains the canonicalization's initial candidate.
371    #[must_use]
372    pub fn maps(&self) -> &[Permutation] {
373        &self.maps
374    }
375}
376
377struct Builder {
378    universe: usize,
379    limits: Limits,
380    work: usize,
381    maps: Vec<Permutation>,
382    seen: HashSet<Arc<Vec<usize>>>,
383}
384
385impl Builder {
386    fn charge(&mut self, amount: usize) -> Result<(), Error> {
387        self.work = self.work.checked_add(amount).ok_or(Error::Limit("work"))?;
388        if self.work > self.limits.work {
389            return Err(Error::Limit("work"));
390        }
391        Ok(())
392    }
393
394    fn scratch(&self) -> Result<(), Error> {
395        let cells = self
396            .maps
397            .len()
398            .checked_add(1)
399            .and_then(|n| n.checked_mul(self.universe))
400            .ok_or(Error::Limit("cells"))?;
401        if cells > self.limits.cells {
402            return Err(Error::Limit("cells"));
403        }
404        Ok(())
405    }
406
407    fn insert(&mut self, row: Vec<usize>) -> Result<(), Error> {
408        self.charge(self.universe)?;
409        if row.iter().enumerate().all(|(i, &value)| i == value) || self.seen.contains(&row) {
410            return Ok(());
411        }
412        if self.maps.len() >= self.limits.maps {
413            return Err(Error::Limit("maps"));
414        }
415        // Move the vector into an Arc without copying its dense row.
416        let images = Arc::new(row);
417        self.seen.insert(images.clone());
418        self.maps.push(Permutation { images });
419        Ok(())
420    }
421}