use crate::derived_artifact::replay_recipe;
use crate::equivalence_edge::{DerivedEquivalenceEdge, DerivedEquivalenceEdgeOutcome};
use super::*;
fn same(left: &Algebra, right: &Algebra) -> bool {
left.certificate() == right.certificate()
}
pub(super) fn partitions<'a>(size: usize, classes: impl IntoIterator<Item = &'a [usize]>) -> bool {
let mut seen = vec![false; size];
let mut last = None;
for members in classes {
let increasing = members.windows(2).all(|pair| pair[0] < pair[1]);
verify_guard!(increasing && members.first().copied() > last);
last = members.first().copied();
for &member in members {
verify_guard!(member < size && !std::mem::replace(&mut seen[member], true));
}
}
seen.iter().all(|&found| found)
}
pub(super) fn spanning_tree(
members: &[usize],
edges: impl ExactSizeIterator<Item = (usize, usize)>,
) -> bool {
verify_guard!(edges.len() + 1 == members.len());
let mut parent: Vec<usize> = (0..members.len()).collect();
for (left, right) in edges {
let (Ok(left), Ok(right)) = (members.binary_search(&left), members.binary_search(&right))
else {
return false;
};
let (left, right) = (root(&mut parent, left), root(&mut parent, right));
verify_guard!(left != right);
parent[left] = right;
}
true
}
fn root(parent: &mut [usize], mut node: usize) -> usize {
while parent[node] != node {
parent[node] = parent[parent[node]];
node = parent[node];
}
node
}
pub(super) fn covers_pairs(
count: usize,
separated: impl Iterator<Item = (usize, usize)>,
unresolved: &[UnresolvedPair],
) -> bool {
let mut pairs: Vec<_> = separated.collect();
let open: Vec<_> = unresolved.iter().map(|pair| pair.classes).collect();
let increasing = |pairs: &[(usize, usize)]| pairs.windows(2).all(|w| w[0] < w[1]);
verify_guard!(increasing(&pairs) && increasing(&open));
let all = count
.checked_mul(count.saturating_sub(1))
.map(|twice| twice / 2);
verify_guard!(all == Some(pairs.len() + open.len()));
pairs.extend(open);
pairs.sort_unstable();
let valid = |&(left, right): &(usize, usize)| left < right && right < count;
increasing(&pairs) && pairs.iter().all(valid)
}
pub(super) fn replay_edge(
source: &Arc<Algebra>,
recipe: &[ArtifactMutation],
limits: &ClassificationLimits,
) -> Option<Box<DerivedEquivalenceEdge>> {
let discovery = &limits.discovery;
let tilting = replay_recipe(source, recipe, discovery.tilting, discovery.goal()).ok()?;
match DerivedEquivalenceEdge::recover(tilting, &limits.target) {
Ok(DerivedEquivalenceEdgeOutcome::Certified(edge)) => Some(edge),
_ => None,
}
}
impl DerivedClassification {
pub fn verify(&self) -> bool {
let members = self.classes.iter().map(|class| &class.members[..]);
partitions(self.family.len(), members)
&& self.classes.iter().all(|class| self.class_holds(class))
&& covers_pairs(
self.classes.len(),
self.separations.iter().map(|separation| separation.classes),
&self.unresolved,
)
&& self
.separations
.iter()
.all(|separation| self.separation_holds(separation))
}
fn class_holds(&self, class: &DerivedClass) -> bool {
let edges = class
.merges
.iter()
.map(|merge| (merge.source, merge.member));
spanning_tree(&class.members, edges)
&& class.merges.iter().all(|merge| self.merge_holds(merge))
}
fn merge_holds(&self, merge: &DerivedMerge) -> bool {
let_or_false!(Some(source) = self.family.get(merge.source));
let_or_false!(Some(member) = self.family.get(merge.member));
let reached = match merge.path.steps() {
[] => merge.recipe.is_empty() && same(merge.path.source(), source),
[_] => same(merge.path.source(), source) && self.replays(merge, source),
_ => false,
};
reached
&& same(merge.isomorphism.source(), merge.path.target())
&& same(merge.isomorphism.target(), member)
&& merge.isomorphism.verify()
}
fn replays(&self, merge: &DerivedMerge, source: &Arc<Algebra>) -> bool {
let_or_false!(Some(edge) = replay_edge(source, &merge.recipe, &self.limits));
same(edge.target(), merge.path.target())
}
fn separation_holds(&self, separation: &ClassSeparation) -> bool {
let (left, right) = separation.members;
let (left_class, right_class) = separation.classes;
let witness = &separation.witness;
self.classes[left_class].members.contains(&left)
&& self.classes[right_class].members.contains(&right)
&& same(witness.left(), &self.family[left])
&& same(witness.right(), &self.family[right])
&& witness.limits() == self.limits.invariants
&& witness.verify()
}
}