1use 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#[derive(Clone, Debug)]
17pub struct Prepared {
18 pub reduction: Option<Arc<Reduction>>,
20 pub warnings: Vec<Message>,
22}
23
24#[derive(Clone, Debug)]
28pub struct Reduction {
29 universe: Vec<Atom>,
30 indices: HashMap<Atom, usize>,
31 group: Group,
32 typed: Vec<bool>,
35 id: u64,
37}
38
39#[derive(Default)]
50struct ImageCache {
51 owner: Option<(u64, Ctx)>,
52 images: HashMap<Exact, Arc<Entry>>,
53 held: usize,
54 generation: u64,
56 sorted: Vec<(Value, u32)>,
58 rank: Vec<u64>,
60}
61
62struct Entry {
64 key: u32,
65 images: Box<[Option<(Value, u32)>]>,
66}
67
68const RANK_GAP: u64 = 1 << 24;
70
71impl ImageCache {
72 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
101struct 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
120fn 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
138const 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 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 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 ¶meters
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 #[must_use]
449 pub fn universe(&self) -> &[Atom] {
450 &self.universe
451 }
452
453 #[must_use]
456 pub fn maps(&self) -> &[crate::symmetry::Permutation] {
457 self.group.maps()
458 }
459
460 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 let mut candidate = values.to_vec();
488 let mut distinct: Vec<Option<Option<Distinct>>> = vec![None; values.len()];
491 let mut unbuilt: Vec<usize> = Vec::new();
493 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 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 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 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 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 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 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 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 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 #[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 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 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 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 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
1079fn 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#[derive(Clone)]
1094struct Distinct {
1095 elements: Arc<[Value]>,
1096 entries: Vec<Arc<Entry>>,
1097 generation: u64,
1098 atoms: Vec<usize>,
1100}
1101
1102fn 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
1117fn 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
1140fn 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 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 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 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}