1mod 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#[derive(Clone, Debug)]
32pub struct Declaration {
33 pub name: String,
35 pub predicate: Pred,
37 pub functions: Arc<[Value]>,
39}
40
41impl Model {
42 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 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
171fn 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#[derive(Clone, Copy, Debug, PartialEq, Eq)]
185pub enum Mode {
186 Checked,
188 Tlc,
190}
191
192#[derive(Clone, Copy, Debug)]
194pub struct Limits {
195 pub model_values: usize,
197 pub maps: usize,
199 pub cells: usize,
201 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#[derive(Clone, Debug, PartialEq, Eq)]
218pub enum Error {
219 TooFewGenerators,
221 UnknownModelValue,
223 DuplicateDomain,
225 NonBijective,
227 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#[derive(Clone, Debug, PartialEq, Eq)]
249pub struct Permutation {
250 images: Arc<Vec<usize>>,
251}
252
253impl Permutation {
254 #[must_use]
256 pub fn image(&self, index: usize) -> Option<usize> {
257 self.images.get(index).copied()
258 }
259
260 #[must_use]
262 pub fn images(&self) -> &[usize] {
263 self.images.as_slice()
264 }
265}
266
267#[derive(Clone, Debug)]
272pub struct Group {
273 maps: Vec<Permutation>,
274}
275
276impl Group {
277 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 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 #[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 let images = Arc::new(row);
417 self.seen.insert(images.clone());
418 self.maps.push(Permutation { images });
419 Ok(())
420 }
421}