mod liveness;
mod prepare;
pub use liveness::{SymmetryLiveness, SymmetryLivenessResolution};
pub use prepare::{Prepared, Reduction};
use std::collections::HashSet;
use std::fmt;
use std::sync::Arc;
use dive_eval::{ErrorClass, St};
use dive_ir::{Effects, Level};
use dive_value::{SetKind, Value};
use crate::tables::Look;
use crate::{BindError, Ec, Model, Pred};
#[derive(Clone, Debug)]
pub struct Declaration {
pub name: String,
pub predicate: Pred,
pub functions: Arc<[Value]>,
}
impl Model {
pub fn symmetry_declaration(&self) -> Result<Option<Declaration>, BindError> {
let Some(name) = self.symmetry.as_ref() else {
return Ok(None);
};
let definition = match &self.symmetry_definition {
None => {
return Err(BindError::tlc(
Ec::TlcConfigSpecifiedNotDefined,
&["symmetry function", name],
));
}
Some(Look::Def(definition)) => *definition,
Some(_) => {
return Err(symmetry_runtime_error(&format!(
"The symmetry function {name} must specify a set of permutations."
)));
}
};
let def = self.ir.def(definition);
let node = self.ir.node(def.body);
if !def.params.is_empty()
|| node.level != Level::Constant
|| node.effects.intersects(Effects::IMPURE)
{
return Err(BindError::unsupported(format!(
"effectful, nonconstant or parameterized SYMMETRY {name} at {}",
self.ir.location(&node.origin)
)));
}
let predicate = Pred::new(
def.body,
self.evaluator
.scope(definition)
.map_err(|e| BindError::unsupported(e.to_string()))?,
);
let value =
self.eval(&predicate, &St::constant())
.map_err(|error| match error.class() {
ErrorClass::Unsupported | ErrorClass::ResourceLimit => {
BindError::unsupported(format!("SYMMETRY {name}: {}", error.message()))
}
ErrorClass::Bug | ErrorClass::Interrupted => {
BindError::bug(format!("SYMMETRY {name}: {}", error.message()))
}
ErrorClass::Eval
if error.ec() == dive_eval::Ec::DivisionByZero
&& error.is_eval_exception() =>
{
symmetry_exception("tlc2.tool.EvalException", &error.tool_text())
}
ErrorClass::Eval => BindError::unsupported(format!(
"SYMMETRY {name} declaration evaluation error ({}): {}",
error.ec().code(),
error.message()
)),
})?;
let Value::Set(set) = value else {
return Err(symmetry_runtime_error(
"The symmetry operator must specify a set of functions.",
));
};
if !matches!(set.kind(), SetKind::Enum | SetKind::Raw) {
return Err(symmetry_runtime_error(
"The symmetry operator must specify a set of functions.",
));
}
let functions = set
.elements(self.evaluator.options().ctx)
.map_err(|error| match error.kind() {
dive_value::ErrorKind::Codec => BindError::bug(format!(
"SYMMETRY {name} set normalization: {}",
error.message()
)),
dive_value::ErrorKind::Incomparable => symmetry_runtime_error(error.message()),
_ => BindError::unsupported(format!(
"SYMMETRY {name} set normalization: {}",
error.message()
)),
})?;
if functions.iter().any(|value| match value {
Value::Fcn(function) => function.is_tuple_literal() || function.is_record_literal(),
_ => true,
}) {
return Err(symmetry_runtime_error(
"The symmetry values must be function records.",
));
}
Ok(Some(Declaration {
name: name.clone(),
predicate,
functions,
}))
}
}
fn symmetry_runtime_error(message: &str) -> BindError {
symmetry_exception("java.lang.RuntimeException", message)
}
fn symmetry_exception(class: &str, message: &str) -> BindError {
BindError::tlc(
Ec::General,
&[&format!(
"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}"
)],
)
}
#[derive(Clone, Copy, Debug, PartialEq, Eq)]
pub enum Mode {
Checked,
Tlc,
}
#[derive(Clone, Copy, Debug)]
pub struct Limits {
pub model_values: usize,
pub maps: usize,
pub cells: usize,
pub work: usize,
}
impl Default for Limits {
fn default() -> Self {
Self {
model_values: 4096,
maps: 4096,
cells: 1_000_000,
work: 32_000_000,
}
}
}
#[derive(Clone, Debug, PartialEq, Eq)]
pub enum Error {
TooFewGenerators,
UnknownModelValue,
DuplicateDomain,
NonBijective,
Limit(&'static str),
}
impl fmt::Display for Error {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
match self {
Self::TooFewGenerators => {
f.write_str("symmetry generator set has fewer than two functions")
}
Self::UnknownModelValue => f.write_str("symmetry index outside model-value universe"),
Self::DuplicateDomain => f.write_str("duplicate symmetry function domain"),
Self::NonBijective => f.write_str("symmetry function is not bijective"),
Self::Limit(name) => write!(f, "symmetry resource limit: {name}"),
}
}
}
impl std::error::Error for Error {}
#[derive(Clone, Debug, PartialEq, Eq)]
pub struct Permutation {
images: Arc<Vec<usize>>,
}
impl Permutation {
#[must_use]
pub fn image(&self, index: usize) -> Option<usize> {
self.images.get(index).copied()
}
#[must_use]
pub fn images(&self) -> &[usize] {
self.images.as_slice()
}
}
#[derive(Clone, Debug)]
pub struct Group {
maps: Vec<Permutation>,
}
impl Group {
pub fn from_generators(
universe: usize,
generators: &[Vec<(usize, usize)>],
mode: Mode,
limits: Limits,
) -> Result<Self, Error> {
if generators.len() < 2 {
return Err(Error::TooFewGenerators);
}
if universe > limits.model_values {
return Err(Error::Limit("model values"));
}
let mut builder = Builder {
universe,
limits,
work: 0,
maps: Vec::new(),
seen: HashSet::new(),
};
for generator in generators {
builder.charge(1)?;
builder.scratch()?;
builder.charge(universe)?;
let mut row: Vec<usize> = (0..universe).collect();
let mut assigned = HashSet::new();
for &(domain, range) in generator {
builder.charge(1)?;
if domain >= universe || range >= universe {
return Err(Error::UnknownModelValue);
}
if !assigned.insert(domain) {
return Err(Error::DuplicateDomain);
}
row[domain] = range;
}
if mode == Mode::Checked {
builder.charge(universe)?;
let images: HashSet<usize> = row.iter().copied().collect();
if images.len() != universe {
return Err(Error::NonBijective);
}
}
builder.insert(row)?;
}
let generators = builder.maps.len();
let mut begin = 0;
loop {
let end = builder.maps.len();
for i in 0..generators {
for j in begin..end {
builder.charge(1)?;
builder.scratch()?;
builder.charge(universe)?;
let first = &builder.maps[i].images;
let second = &builder.maps[j].images;
let row = first.iter().map(|&image| second[image]).collect();
builder.insert(row)?;
}
}
if end == builder.maps.len() {
break;
}
begin = end;
}
Ok(Self { maps: builder.maps })
}
#[must_use]
pub fn maps(&self) -> &[Permutation] {
&self.maps
}
}
struct Builder {
universe: usize,
limits: Limits,
work: usize,
maps: Vec<Permutation>,
seen: HashSet<Arc<Vec<usize>>>,
}
impl Builder {
fn charge(&mut self, amount: usize) -> Result<(), Error> {
self.work = self.work.checked_add(amount).ok_or(Error::Limit("work"))?;
if self.work > self.limits.work {
return Err(Error::Limit("work"));
}
Ok(())
}
fn scratch(&self) -> Result<(), Error> {
let cells = self
.maps
.len()
.checked_add(1)
.and_then(|n| n.checked_mul(self.universe))
.ok_or(Error::Limit("cells"))?;
if cells > self.limits.cells {
return Err(Error::Limit("cells"));
}
Ok(())
}
fn insert(&mut self, row: Vec<usize>) -> Result<(), Error> {
self.charge(self.universe)?;
if row.iter().enumerate().all(|(i, &value)| i == value) || self.seen.contains(&row) {
return Ok(());
}
if self.maps.len() >= self.limits.maps {
return Err(Error::Limit("maps"));
}
let images = Arc::new(row);
self.seen.insert(images.clone());
self.maps.push(Permutation { images });
Ok(())
}
}