use std::cmp::Ordering;
use std::collections::{HashMap, HashSet};
use std::sync::Arc;
use dive_config::{ConstantEntry, ModelConfig};
use dive_eval::{ConstBinding, St};
use dive_ir::{Arg, Expr, ExprId, OpRef, StdOp};
use dive_value::{Atom, Ctx, SetKind, Value, ValueOrder};
use super::{Declaration, Group, Limits, Mode, Permutation, symmetry_runtime_error};
use crate::{BindError, Ec, Message, Model, Pred};
#[derive(Clone, Debug)]
pub struct Prepared {
pub reduction: Option<Arc<Reduction>>,
pub warnings: Vec<Message>,
}
#[derive(Clone, Debug)]
pub struct Reduction {
universe: Vec<Atom>,
indices: HashMap<Atom, usize>,
group: Group,
typed: Vec<bool>,
id: u64,
}
#[derive(Default)]
struct ImageCache {
owner: Option<(u64, Ctx)>,
images: HashMap<Exact, Arc<Entry>>,
held: usize,
generation: u64,
sorted: Vec<(Value, u32)>,
rank: Vec<u64>,
}
struct Entry {
key: u32,
images: Box<[Option<(Value, u32)>]>,
}
const RANK_GAP: u64 = 1 << 24;
impl ImageCache {
fn rank_id(&mut self, value: &Value, order: ValueOrder) -> u32 {
match self
.sorted
.binary_search_by(|(probe, _)| probe.cmp_with(value, order))
{
Ok(at) => self.sorted[at].1,
Err(at) => {
let id = u32::try_from(self.rank.len()).unwrap_or(u32::MAX);
let below = at
.checked_sub(1)
.map_or(0, |i| self.rank[self.sorted[i].1 as usize]);
let above = self
.sorted
.get(at)
.map_or(u64::MAX, |(_, above)| self.rank[*above as usize]);
self.rank.push(below + (above - below) / 2);
self.sorted.insert(at, (value.clone(), id));
if above - below < 2 {
for (i, (_, id)) in self.sorted.iter().enumerate() {
self.rank[*id as usize] = (i as u64 + 1) * RANK_GAP;
}
}
id
}
}
}
}
struct Exact(Value);
impl PartialEq for Exact {
fn eq(&self, other: &Self) -> bool {
self.0 == other.0 && same_classes(&self.0, &other.0)
}
}
impl Eq for Exact {}
impl std::hash::Hash for Exact {
fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
state.write_u64(self.0.hash64());
}
}
fn same_classes(a: &Value, b: &Value) -> bool {
match (a, b) {
(Value::Fcn(f), Value::Fcn(g)) => {
f.ptr_eq(g)
|| (f.kind() == g.kind()
&& f.is_record_literal() == g.is_record_literal()
&& f.is_tuple_literal() == g.is_tuple_literal()
&& f.len() == g.len()
&& f.iter()
.zip(g.iter())
.all(|((d, v), (e, w))| same_classes(&d, &e) && same_classes(v, w)))
}
(Value::Int(_) | Value::BigInt(_), Value::Int(_) | Value::BigInt(_)) => true,
_ => std::mem::discriminant(a) == std::mem::discriminant(b),
}
}
const IMAGE_CACHE_LIMIT: usize = 1 << 18;
thread_local! {
static IMAGES: std::cell::RefCell<ImageCache> = std::cell::RefCell::default();
}
static NEXT_REDUCTION: std::sync::atomic::AtomicU64 = std::sync::atomic::AtomicU64::new(0);
impl Model {
pub fn prepare_symmetry(
&self,
cfg: &ModelConfig,
mode: Mode,
limits: Limits,
) -> Result<Option<Prepared>, BindError> {
let Some(declaration) = self.symmetry_declaration()? else {
return Ok(None);
};
let args = argument_nodes(self.ir.expr(declaration.predicate.expr))?;
if !args.is_empty() && args.len() >= declaration.functions.len() {
if mode == Mode::Checked
&& !declaration.functions.is_empty()
&& declaration.functions.iter().all(|value| match value {
Value::Fcn(function) => function.iter().all(|(domain, range)| {
matches!(domain, Value::Model(_)) && matches!(range, Value::Model(_))
}),
_ => false,
})
{
let mut checked = declaration.clone();
if checked.functions.len() == 1 {
checked.functions =
vec![checked.functions[0].clone(), checked.functions[0].clone()].into();
}
prepare_group(&checked, mode, limits)?;
}
return Ok(Some(Prepared {
reduction: None,
warnings: vec![warning(self, cfg, &args)?],
}));
}
let reduction = prepare_group(&declaration, mode, limits)?;
let members: HashSet<Atom> = reduction
.group
.maps()
.iter()
.flat_map(|map| {
map.images()
.iter()
.enumerate()
.filter(|(index, image)| index != *image)
.map(|(_, image)| reduction.universe[*image].clone())
})
.collect();
let mut unused = Vec::new();
for arg in args {
if let Some(values) = permutation_argument(self, &declaration, arg)?
&& !values
.iter()
.any(|value| matches!(value, Value::Model(m) if members.contains(m)))
{
unused.push(arg);
}
}
Ok(Some(Prepared {
reduction: Some(Arc::new(reduction)),
warnings: if unused.is_empty() {
Vec::new()
} else {
vec![warning(self, cfg, &unused)?]
},
}))
}
}
fn argument_nodes(expr: &Expr) -> Result<Vec<ExprId>, BindError> {
match expr {
Expr::Def(_) | Expr::Const(_) | Expr::Bool(_) | Expr::Num(_) | Expr::Str(_) => {
Ok(Vec::new())
}
Expr::Builtin { args, .. }
| Expr::SetEnum(args)
| Expr::Tuple(args)
| Expr::Cartesian(args) => Ok(args.to_vec()),
Expr::Apply { args, .. } => args
.iter()
.map(|arg| match arg {
Arg::Expr { expr: id, .. } => Ok(*id),
Arg::Op { .. } => Err(BindError::unsupported(
"SYMMETRY warning arguments containing an operator argument",
)),
})
.collect(),
Expr::If { cond, then, other } => Ok(vec![*cond, *then, *other]),
Expr::Junction { items, .. } => Ok(items.to_vec()),
_ => Err(BindError::unsupported(
"SYMMETRY declaration syntax whose TLC argument/warning shape is not implemented",
)),
}
}
fn warning(model: &Model, cfg: &ModelConfig, args: &[ExprId]) -> Result<Message, BindError> {
let mut names = Vec::new();
for arg in args {
let image = model
.ir
.human_readable_image(*arg)
.filter(|s| !s.is_empty())
.ok_or_else(|| {
BindError::unsupported("SYMMETRY warning lacks original source tokens")
})?;
let alias = if image.starts_with("Permutations") {
image
.get("Permutations".len() + 1..image.len().saturating_sub(1))
.ok_or_else(|| BindError::unsupported("SYMMETRY warning permutation image"))?
} else {
&image
};
let original = cfg
.constants
.iter()
.rev()
.find_map(|entry| match entry {
ConstantEntry::Substitution {
name,
target,
module: None,
} if target.text == alias => Some(name.text.as_str()),
_ => None,
})
.unwrap_or(alias);
names.push(original.to_owned());
}
let many = args.len() > 1;
let parameters = [
if many { "s" } else { "" },
&names.join(", and "),
if many { "have" } else { "has" },
if many { "" } else { "s" },
];
Ok(Message::Warning {
code: Ec::TlcSymmetrySetTooSmall,
message: Ec::TlcSymmetrySetTooSmall.render(
¶meters
.iter()
.map(|s| (*s).to_owned())
.collect::<Vec<_>>(),
),
})
}
fn permutation_argument(
model: &Model,
declaration: &Declaration,
arg: ExprId,
) -> Result<Option<Arc<[Value]>>, BindError> {
let Expr::Apply { callee, args } = model.ir.expr(arg) else {
return Ok(None);
};
let op = match callee {
OpRef::Def(def) => model.ir.def(*def).std,
OpRef::Std(op) => Some(*op),
_ => None,
};
if op != Some(StdOp::TlcPermutations) {
return Ok(None);
}
let [Arg::Expr { expr: domain, .. }] = args.as_ref() else {
return Ok(None);
};
let value = match model.ir.expr(*domain) {
Expr::Const(constant) => match model.evaluator.constant_binding(*constant) {
Some(ConstBinding::Value(value)) => value,
_ => return Ok(None),
},
Expr::Def(_) => model
.eval(
&Pred::new(*domain, declaration.predicate.scope.clone()),
&St::constant(),
)
.map_err(|error| {
BindError::unsupported(format!("SYMMETRY unused argument: {}", error.message()))
})?,
Expr::SubstRef { .. } => {
return Err(BindError::unsupported(
"SYMMETRY unused-set warning under instance substitutions",
));
}
_ => return Ok(None),
};
if let Value::Set(set) = value
&& matches!(set.kind(), SetKind::Enum | SetKind::Raw)
{
return set
.elements(model.evaluator.options().ctx)
.map(Some)
.map_err(|error| {
BindError::unsupported(format!(
"SYMMETRY unused-set normalization: {}",
error.message()
))
});
}
Ok(None)
}
fn prepare_group(
declaration: &Declaration,
mode: Mode,
limits: Limits,
) -> Result<Reduction, BindError> {
let mut universe = Vec::new();
let mut indices = HashMap::new();
let mut generators = Vec::new();
let mut work = 0usize;
for value in declaration.functions.iter() {
let Value::Fcn(fcn) = value else {
return Err(BindError::bug(
"validated symmetry function ceased to be a function",
));
};
let mut pairs = Vec::new();
for (domain, range) in fcn.iter() {
work = work
.checked_add(1)
.ok_or_else(|| BindError::unsupported("SYMMETRY generator work limit"))?;
if work > limits.work {
return Err(BindError::unsupported("SYMMETRY generator work limit"));
}
let (Value::Model(domain), Value::Model(range)) = (&domain, range) else {
return Err(symmetry_runtime_error(
"Symmetry function must have model values as domain and range.",
));
};
let mut ids = [0usize; 2];
for (at, atom) in [domain, range].into_iter().enumerate() {
ids[at] = if let Some(index) = indices.get(atom) {
*index
} else {
if universe.len() >= limits.model_values {
return Err(BindError::unsupported("SYMMETRY model-value limit"));
}
let index = universe.len();
universe.push(atom.clone());
indices.insert(atom.clone(), index);
index
};
}
pairs.push((ids[0], ids[1]));
}
generators.push(pairs);
}
let group =
Group::from_generators(universe.len(), &generators, mode, limits).map_err(|error| {
BindError::unsupported(format!("SYMMETRY {}: {error}", declaration.name))
})?;
let typed = group
.maps()
.iter()
.map(|map| {
map.images()
.iter()
.enumerate()
.all(|(from, &to)| universe[from].mv_type() == universe[to].mv_type())
})
.collect();
Ok(Reduction {
universe,
indices,
group,
typed,
id: NEXT_REDUCTION.fetch_add(1, std::sync::atomic::Ordering::Relaxed),
})
}
impl Reduction {
#[must_use]
pub fn universe(&self) -> &[Atom] {
&self.universe
}
#[must_use]
pub fn maps(&self) -> &[crate::symmetry::Permutation] {
self.group.maps()
}
pub fn canonical_values(
&self,
values: &[Value],
variable_order: &[usize],
ctx: Ctx,
) -> Result<Vec<Value>, BindError> {
if variable_order.len() != values.len()
|| variable_order
.iter()
.enumerate()
.any(|(at, index)| *index >= values.len() || variable_order[..at].contains(index))
{
return Err(BindError::bug(
"symmetry variable order is not a permutation of the state slots",
));
}
let mut best = values.to_vec();
let mut work = 0usize;
let mut candidate = values.to_vec();
let mut distinct: Vec<Option<Option<Distinct>>> = vec![None; values.len()];
let mut unbuilt: Vec<usize> = Vec::new();
let mut best_from: Option<usize> = None;
let mut best_ranked = true;
let mut best_ids: Vec<Option<Option<Vec<u32>>>> = vec![None; values.len()];
for (at, map) in self.group.maps().iter().enumerate() {
let typed = self.typed.get(at).copied().unwrap_or(false);
let mut smaller = false;
unbuilt.clear();
for &index in variable_order {
let value = values
.get(index)
.ok_or_else(|| BindError::bug("symmetry variable order outside state"))?;
if !smaller && typed {
if distinct[index].is_none() {
distinct[index] = Some(self.distinct(value, ctx));
}
if let Some(Some(elements)) = &distinct[index]
&& !(elements.atoms.iter().all(|&i| map.image(i) == Some(i))
&& matches!(value, Value::Set(set) if !set.is_tlc_normalized()))
&& let Some(ordering) = self.compare_slot(
elements,
(at, map),
&best[index],
best_ranked
.then(|| {
best_ids[index]
.get_or_insert_with(|| Self::rank_ids(elements, best_from))
.as_deref()
})
.flatten(),
ctx,
&mut work,
)?
{
match ordering {
Ordering::Greater => break,
Ordering::Equal => {
unbuilt.push(index);
continue;
}
Ordering::Less => {
unbuilt.push(index);
self.build_unbuilt(
&unbuilt,
true,
values,
map,
(&mut candidate, &best),
ctx,
&mut work,
)?;
smaller = true;
continue;
}
}
}
}
candidate[index] = self.permute(value, map, ctx, 0, &mut work)?;
if !smaller {
let ordering = compare_values(&candidate[index], &best[index], ctx)?;
match ordering {
Ordering::Greater => break,
Ordering::Less => {
self.build_unbuilt(
&unbuilt,
false,
values,
map,
(&mut candidate, &best),
ctx,
&mut work,
)?;
smaller = true;
}
Ordering::Equal => {}
}
}
}
if smaller {
std::mem::swap(&mut best, &mut candidate);
best_from = Some(at);
best_ranked = typed;
best_ids.fill(None);
}
}
Ok(best)
}
fn compare_slot(
&self,
elements: &Distinct,
(at, map): (usize, &Permutation),
best: &Value,
best_ids: Option<&[u32]>,
ctx: Ctx,
work: &mut usize,
) -> Result<Option<Ordering>, BindError> {
*work = work.saturating_add(elements.elements.len());
if *work > 32_000_000 {
return Err(BindError::unsupported(
"SYMMETRY per-state permutation work/depth limit",
));
}
if let Some(ids) = best_ids
&& let Some(ordering) = Self::compare_ranks(elements, at, ids)
{
if ctx.order == ValueOrder::Tlc
&& let Value::Set(set) = best
{
set.elements(ctx).map_err(|error| {
BindError::unsupported(format!(
"SYMMETRY candidate comparison: {}",
error.message()
))
})?;
}
return Ok(Some(ordering));
}
self.compare_image(elements, at, map, best, ctx, work)
}
fn compare_image(
&self,
elements: &Distinct,
at: usize,
map: &Permutation,
best: &Value,
ctx: Ctx,
work: &mut usize,
) -> Result<Option<Ordering>, BindError> {
let mut fresh = Vec::new();
for (element, entry) in elements.elements.iter().zip(&elements.entries) {
if entry.images.get(at).and_then(Option::as_ref).is_none() {
fresh.push(self.permute(element, map, ctx, 1, work)?);
}
}
let mut fresh = fresh.iter();
let images = elements
.entries
.iter()
.map(|entry| {
entry
.images
.get(at)
.and_then(Option::as_ref)
.map(|(image, _)| image)
.or_else(|| fresh.next())
.ok_or_else(|| BindError::bug("SYMMETRY image cache lost an image"))
})
.collect::<Result<Vec<&Value>, _>>()?;
if ctx.order == ValueOrder::Tlc {
dive_value::tlc::compare_distinct_set(&images, best, ctx).map_err(|error| {
BindError::unsupported(format!(
"SYMMETRY candidate comparison: {}",
error.message()
))
})
} else {
Ok(Value::cmp_distinct_set(&images, best, ctx.order))
}
}
fn distinct(&self, value: &Value, ctx: Ctx) -> Option<Distinct> {
let elements = distinct_elements(value, ctx)?;
let mut atoms = HashSet::new();
for element in elements.iter() {
self.collect_atoms(element, &mut atoms);
}
let mut atoms: Vec<usize> = atoms.into_iter().collect();
atoms.sort_unstable();
let (entries, generation) = self.cached_images(&elements, ctx);
Some(Distinct {
elements,
entries,
generation,
atoms,
})
}
fn collect_atoms(&self, value: &Value, atoms: &mut HashSet<usize>) {
match value {
Value::Model(atom) => {
if let Some(&index) = self.indices.get(atom) {
atoms.insert(index);
}
}
Value::Fcn(function) => {
if let Some(tuple) = function.as_tuple() {
for v in tuple {
self.collect_atoms(v, atoms);
}
} else if let Some(fields) = function.as_record() {
for (_, v) in fields {
self.collect_atoms(v, atoms);
}
} else {
for (domain, range) in function.iter() {
self.collect_atoms(&domain, atoms);
self.collect_atoms(range, atoms);
}
}
}
_ => {}
}
}
fn cached_images(&self, elements: &[Value], ctx: Ctx) -> (Vec<Arc<Entry>>, u64) {
IMAGES.with(|cache| {
let mut cache = cache.borrow_mut();
if cache.owner != Some((self.id, ctx)) {
let generation = cache.generation + 1;
*cache = ImageCache {
owner: Some((self.id, ctx)),
generation,
..ImageCache::default()
};
}
if cache
.held
.saturating_add(elements.len() * (self.group.maps().len() + 1))
> IMAGE_CACHE_LIMIT
{
let generation = cache.generation + 1;
*cache = ImageCache {
owner: cache.owner,
generation,
..ImageCache::default()
};
}
let entries = elements
.iter()
.map(|element| {
let key = Exact(element.clone());
if let Some(entry) = cache.images.get(&key) {
return entry.clone();
}
let images = self
.group
.maps()
.iter()
.map(|map| {
let image = self.permute(element, map, ctx, 1, &mut 0).ok()?;
let id = cache.rank_id(&image, ctx.order);
Some((image, id))
})
.collect();
let entry = Arc::new(Entry {
key: cache.rank_id(element, ctx.order),
images,
});
cache.held += self.group.maps().len() + 1;
cache.images.insert(key, entry.clone());
entry
})
.collect();
(entries, cache.generation)
})
}
fn compare_ranks(elements: &Distinct, at: usize, best: &[u32]) -> Option<Ordering> {
thread_local! {
static MINE: std::cell::RefCell<Vec<u64>> = const { std::cell::RefCell::new(Vec::new()) };
}
if elements.entries.len() != best.len() {
return None;
}
IMAGES.with(|cache| {
let cache = cache.borrow();
if cache.generation != elements.generation {
return None;
}
let rank = |id: u32| cache.rank.get(id as usize).copied();
MINE.with(|mine| {
let mut mine = mine.borrow_mut();
mine.clear();
for entry in &elements.entries {
mine.push(rank(entry.images.get(at)?.as_ref()?.1)?);
}
mine.sort_unstable();
for (m, b) in mine.iter().zip(best) {
let c = m.cmp(&rank(*b)?);
if c != Ordering::Equal {
return Some(c);
}
}
Some(Ordering::Equal)
})
})
}
fn rank_ids(elements: &Distinct, at: Option<usize>) -> Option<Vec<u32>> {
let mut ids = elements
.entries
.iter()
.map(|entry| match at {
None => Some(entry.key),
Some(at) => Some(entry.images.get(at)?.as_ref()?.1),
})
.collect::<Option<Vec<u32>>>()?;
IMAGES.with(|cache| {
let cache = cache.borrow();
if cache.generation != elements.generation {
return None;
}
let rank = |id: u32| cache.rank.get(id as usize).copied().unwrap_or(u64::MAX);
ids.sort_unstable_by_key(|id| rank(*id));
Some(ids)
})
}
#[allow(
clippy::too_many_arguments,
reason = "the two state rows travel together with the map and work counter"
)]
fn build_unbuilt(
&self,
unbuilt: &[usize],
last_less: bool,
values: &[Value],
map: &Permutation,
(candidate, best): (&mut [Value], &[Value]),
ctx: Ctx,
work: &mut usize,
) -> Result<(), BindError> {
for &index in unbuilt {
let value = values
.get(index)
.ok_or_else(|| BindError::bug("symmetry variable order outside state"))?;
candidate[index] = self.permute(value, map, ctx, 0, work)?;
let ordering = compare_values(&candidate[index], &best[index], ctx)?;
let expected = if last_less && Some(&index) == unbuilt.last() {
Ordering::Less
} else {
Ordering::Equal
};
if ordering != expected {
return Err(BindError::bug(
"SYMMETRY image comparison disagrees with the built image",
));
}
}
Ok(())
}
pub fn normalize_concrete(values: &[Value], ctx: Ctx) -> Result<(), BindError> {
let mut work = 0usize;
for value in values {
deep_normalize(value, ctx, 0, &mut work)?;
}
Ok(())
}
fn permute(
&self,
value: &Value,
map: &Permutation,
ctx: Ctx,
depth: usize,
work: &mut usize,
) -> Result<Value, BindError> {
*work = work
.checked_add(1)
.ok_or_else(|| BindError::unsupported("SYMMETRY permutation work limit"))?;
if *work > 32_000_000 || depth > 256 {
return Err(BindError::unsupported(
"SYMMETRY per-state permutation work/depth limit",
));
}
let recur =
|value: &Value, work: &mut usize| self.permute(value, map, ctx, depth + 1, work);
let map_error = |error: dive_value::ValueError| {
BindError::unsupported(format!("SYMMETRY value permutation: {}", error.message()))
};
match value {
Value::Model(atom) => Ok(self
.indices
.get(atom)
.and_then(|&i| map.image(i))
.and_then(|i| self.universe.get(i))
.map_or_else(|| value.clone(), |atom| Value::Model(atom.clone()))),
Value::Fcn(function) => permute_function(function, ctx, |value| recur(value, work)),
Value::Set(set) => match set.kind() {
SetKind::Enum | SetKind::Raw => {
let elements = match set.raw_elements() {
Some(elements) => Arc::from(elements),
None => set.elements(ctx).map_err(map_error)?,
};
if elements.len() > 32_000_000usize.saturating_sub(*work) {
return Err(BindError::unsupported(
"SYMMETRY set permutation work limit",
));
}
let permuted = elements
.iter()
.map(|value| recur(value, work))
.collect::<Result<Vec<_>, _>>()?;
if elements
.iter()
.zip(&permuted)
.all(|(before, after)| same_value(before, after))
{
Ok(value.clone())
} else {
Ok(Value::set_raw(permuted, ctx))
}
}
SetKind::Interval => Ok(value.clone()),
_ => Err(BindError::unsupported(format!(
"SYMMETRY permutation of lazy {:?} values",
set.kind()
))),
},
_ => Ok(value.clone()),
}
}
}
fn permute_function(
function: &dive_value::Fcn,
ctx: Ctx,
mut recur: impl FnMut(&Value) -> Result<Value, BindError>,
) -> Result<Value, BindError> {
let map_error = |error: dive_value::ValueError| {
BindError::unsupported(format!("SYMMETRY value permutation: {}", error.message()))
};
if let Some(tuple) = function.as_tuple() {
let values = tuple
.iter()
.map(&mut recur)
.collect::<Result<Vec<_>, _>>()?;
if tuple
.iter()
.zip(&values)
.all(|(before, after)| same_value(before, after))
{
return Ok(Value::Fcn(function.clone()));
}
return Ok(if function.is_tuple_literal() {
Value::tuple(values)
} else {
Value::tuple_fcn(values)
});
}
if function.is_record_literal() {
let fields = function
.as_record()
.ok_or_else(|| BindError::bug("record has no fields"))?
.iter()
.map(|(name, value)| Ok((name.clone(), recur(value)?)))
.collect::<Result<Vec<_>, BindError>>()?;
if function.as_record().is_some_and(|original| {
original
.iter()
.zip(&fields)
.all(|((_, before), (_, after))| same_value(before, after))
}) {
return Ok(Value::Fcn(function.clone()));
}
return Value::record(fields, ctx).map_err(map_error);
}
let ranges = function
.iter()
.map(|(_, range)| recur(range))
.collect::<Result<Vec<_>, BindError>>()?;
let pairs = function
.iter()
.zip(ranges)
.map(|((domain, _), range)| Ok((recur(&domain)?, range)))
.collect::<Result<Vec<_>, BindError>>()?;
if function
.iter()
.zip(&pairs)
.all(|((domain, before), (image, after))| {
same_value(&domain, image) && same_value(before, after)
})
{
return Ok(Value::Fcn(function.clone()));
}
Value::fcn(pairs, ctx).map_err(map_error)
}
fn deep_normalize(
value: &Value,
ctx: Ctx,
depth: usize,
work: &mut usize,
) -> Result<(), BindError> {
*work = work
.checked_add(1)
.ok_or_else(|| BindError::unsupported("SYMMETRY normalization work limit"))?;
if *work > 32_000_000 || depth > 256 {
return Err(BindError::unsupported(
"SYMMETRY normalization work/depth limit",
));
}
match value {
Value::Set(set) if matches!(set.kind(), SetKind::Enum | SetKind::Raw) => {
if let Some(raw) = set.raw_elements() {
for child in raw {
deep_normalize(child, ctx, depth + 1, work)?;
}
} else {
for child in set
.elements(ctx)
.map_err(|e| {
BindError::unsupported(format!(
"SYMMETRY deep normalization: {}",
e.message()
))
})?
.iter()
{
deep_normalize(child, ctx, depth + 1, work)?;
}
}
set.elements(ctx).map_err(|e| {
BindError::unsupported(format!("SYMMETRY deep normalization: {}", e.message()))
})?;
}
Value::Fcn(fcn) => {
for (_, child) in fcn.iter() {
deep_normalize(child, ctx, depth + 1, work)?;
}
}
Value::Set(set) if set.as_deferred().is_some() => {
let operand = set
.as_deferred()
.and_then(|provider| {
dive_eval::deferred_filter_normalization_operand(provider.as_ref())
})
.ok_or_else(|| {
BindError::unsupported(
"SYMMETRY deep normalization of unproved deferred values",
)
})?;
deep_normalize(operand, ctx, depth + 1, work)?;
}
Value::Set(set) => {
for (_, child) in set.components() {
deep_normalize(&child, ctx, depth + 1, work)?;
}
}
_ => {}
}
Ok(())
}
fn same_value(before: &Value, after: &Value) -> bool {
match (before, after) {
(Value::Set(a), Value::Set(b)) => a.ptr_eq(b),
(Value::Fcn(a), Value::Fcn(b)) => a.ptr_eq(b),
_ => before == after,
}
}
#[derive(Clone)]
struct Distinct {
elements: Arc<[Value]>,
entries: Vec<Arc<Entry>>,
generation: u64,
atoms: Vec<usize>,
}
fn compare_values(candidate: &Value, best: &Value, ctx: Ctx) -> Result<Ordering, BindError> {
if ctx.order == ValueOrder::Tlc {
dive_value::tlc::compare(candidate, best, ctx).map_err(|error| {
BindError::unsupported(format!(
"SYMMETRY candidate comparison: {}",
error.message()
))
})
} else {
Ok(candidate.cmp_with(best, ctx.order))
}
}
fn distinct_elements(value: &Value, ctx: Ctx) -> Option<Arc<[Value]>> {
let Value::Set(set) = value else {
return None;
};
if !matches!(set.kind(), SetKind::Enum | SetKind::Raw) {
return None;
}
let elements = set.peek_elements(ctx).ok()?;
let mut budget = 1_000_000usize;
(elements
.iter()
.all(|element| set_free(element, 1, &mut budget))
&& Value::elements_comparable(&elements))
.then_some(elements)
}
fn set_free(value: &Value, depth: usize, budget: &mut usize) -> bool {
if *budget == 0 || depth > 256 {
return false;
}
*budget -= 1;
match value {
Value::Set(_) => false,
Value::Fcn(function) => {
if let Some(tuple) = function.as_tuple() {
tuple.iter().all(|v| set_free(v, depth + 1, budget))
} else if let Some(fields) = function.as_record() {
fields.iter().all(|(_, v)| set_free(v, depth + 1, budget))
} else {
function.iter().all(|(domain, range)| {
set_free(&domain, depth + 1, budget) && set_free(range, depth + 1, budget)
})
}
}
_ => true,
}
}
#[cfg(test)]
mod tests {
#![allow(clippy::unwrap_used, reason = "test fixtures")]
use super::*;
use dive_value::Interner;
fn reference(
reduction: &Reduction,
values: &[Value],
order: &[usize],
ctx: Ctx,
) -> Result<Vec<Value>, BindError> {
let mut best = values.to_vec();
let mut work = 0usize;
let mut candidate = values.to_vec();
for map in reduction.group.maps() {
let mut smaller = false;
for &index in order {
candidate[index] = reduction.permute(&values[index], map, ctx, 0, &mut work)?;
if !smaller {
match compare_values(&candidate[index], &best[index], ctx)? {
Ordering::Greater => break,
Ordering::Less => smaller = true,
Ordering::Equal => {}
}
}
}
if smaller {
std::mem::swap(&mut best, &mut candidate);
}
}
Ok(best)
}
struct Rng(u64);
impl Rng {
fn below(&mut self, n: u64) -> u64 {
self.0 ^= self.0 << 13;
self.0 ^= self.0 >> 7;
self.0 ^= self.0 << 17;
self.0 % n
}
}
fn reduction(names: &Interner, atoms: &[&str]) -> Reduction {
let universe: Vec<Atom> = atoms.iter().map(|a| names.intern(a)).collect();
let indices = universe
.iter()
.enumerate()
.map(|(i, a)| (a.clone(), i))
.collect();
let generators: Vec<Vec<(usize, usize)>> = (0..universe.len() - 1)
.map(|i| vec![(i, i + 1), (i + 1, i)])
.collect();
let group =
Group::from_generators(universe.len(), &generators, Mode::Tlc, Limits::default())
.unwrap();
let typed = vec![true; group.maps().len()];
Reduction {
universe,
indices,
group,
typed,
id: NEXT_REDUCTION.fetch_add(1, std::sync::atomic::Ordering::Relaxed),
}
}
fn state(names: &Interner, rng: &mut Rng, ctx: Ctx) -> Vec<Value> {
let mv = |rng: &mut Rng| Value::model(names, &format!("m{}", rng.below(4)));
let mut records = Vec::new();
for _ in 0..rng.below(9) {
let mut fields = vec![
(names.intern("type"), Value::string(names, "a")),
(
names.intern("b"),
Value::Int(i64::try_from(rng.below(3)).unwrap()),
),
(names.intern("v"), mv(rng)),
];
if rng.below(2) == 0 {
fields[0].1 = Value::string(names, "b");
fields.push((names.intern("acc"), mv(rng)));
}
records.push(Value::record(fields, ctx).unwrap());
}
let tuples = (0..rng.below(6))
.map(|_| {
Value::tuple(vec![
mv(rng),
Value::Int(i64::try_from(rng.below(2)).unwrap()),
])
})
.collect();
let function = Value::fcn(
(0..4)
.map(|i| {
(
Value::model(names, &format!("m{i}")),
Value::Int(i64::try_from(rng.below(2)).unwrap()),
)
})
.collect(),
ctx,
)
.unwrap();
let nested = (0..rng.below(3))
.map(|_| Value::set_raw(vec![mv(rng), mv(rng)], ctx))
.collect();
let functions = (0..rng.below(4))
.map(|_| {
let mut pairs = vec![(mv(rng), Value::Int(1))];
let other = mv(rng);
if pairs[0].0 != other {
pairs.push((other, Value::Int(2)));
}
Value::fcn(pairs, ctx).unwrap()
})
.collect();
vec![
Value::set_raw(records, ctx),
Value::set_raw(functions, ctx),
mv(rng),
Value::set_raw(tuples, ctx),
function,
Value::set_raw(nested, ctx),
]
}
fn normalized(values: &[Value]) -> Vec<bool> {
values
.iter()
.map(|v| matches!(v, Value::Set(s) if s.is_tlc_normalized()))
.collect()
}
#[test]
fn unbuilt_images_choose_the_reference_representative() {
for ctx in [Ctx::tlc(), Ctx::default()] {
let names = Interner::new();
for a in ["m0", "m1", "m2", "m3", "type", "b", "v", "acc", "a"] {
names.intern(a);
}
let reduction = reduction(&names, &["m0", "m1", "m2", "m3"]);
for order in [
[0usize, 1, 2, 3, 4, 5],
[2, 4, 0, 5, 3, 1],
[5, 3, 1, 0, 2, 4],
] {
let mut rng = Rng(0x9e37_79b9_7f4a_7c15);
for _ in 0..300 {
let seed = rng.0;
let mine = state(&names, &mut Rng(seed), ctx);
let theirs = state(&names, &mut Rng(seed), ctx);
rng.below(2);
let got = reduction.canonical_values(&mine, &order, ctx).unwrap();
let want = reference(&reduction, &theirs, &order, ctx).unwrap();
assert_eq!(got, want, "order {order:?}, seed {seed}");
assert_eq!(
normalized(&mine),
normalized(&theirs),
"ctx {ctx:?} order {order:?} seed {seed} state {theirs:?} best {want:?}"
);
assert_eq!(
normalized(&got),
normalized(&want),
"ctx {ctx:?} order {order:?} seed {seed} got {got:?}"
);
}
}
}
}
}