#![deny(missing_docs)]
#![warn(clippy::missing_docs_in_private_items)]
pub mod all_different;
pub mod among;
pub mod at_least;
mod builders;
pub mod gcc;
pub mod not_equals;
pub mod regular;
pub mod sum;
use std::any::Any;
use crate::modelling::*;
pub use all_different::AllDifferent;
pub use among::Among;
pub use at_least::AtLeast;
pub use gcc::Gcc;
pub use not_equals::NotEquals;
pub use regular::Regular;
pub use sum::Sum;
#[doc(inline)]
pub use crate::modelling::{Constraint, ConstraintProperty, ConstraintShapeKey};
pub use builders::*;
#[cfg(test)]
mod test_contract {
use super::*;
use deepsize::DeepSizeOf;
use rustc_hash::{FxHashSet, FxHasher};
use std::any::TypeId;
use std::hash::Hasher;
struct Instance {
name: &'static str,
domains: Vec<Vec<isize>>,
constraint: Box<dyn Constraint>,
type_id: TypeId,
scope_len: usize,
complete: bool,
}
impl Instance {
fn new<C: Constraint + 'static>(
name: &'static str,
domains: Vec<Vec<isize>>,
scope: &[usize],
make: impl FnOnce(Vec<VariableIndex>, &Problem) -> C,
complete: bool,
) -> Self {
let mut problem = Problem::default();
let vars: Vec<VariableIndex> = domains
.iter()
.map(|d| problem.add_variable(d.clone()))
.collect();
let mut constraint = make(scope.iter().map(|&i| vars[i]).collect(), &problem);
constraint.update_variable_ordering(&vars);
Self {
name,
domains,
constraint: Box::new(constraint),
type_id: TypeId::of::<C>(),
scope_len: scope.len(),
complete,
}
}
fn layers(&self) -> usize {
self.domains.len()
}
}
fn doms(n: usize, d: isize) -> Vec<Vec<isize>> {
vec![(0..d).collect(); n]
}
fn set(values: &[isize]) -> FxHashSet<isize> {
values.iter().copied().collect()
}
fn no_one_then_zero() -> Vec<Vec<Option<usize>>> {
vec![
vec![Some(1), Some(2), Some(3)],
vec![Some(1), Some(2), Some(3)],
vec![None, Some(2), Some(3)],
vec![Some(1), Some(2), Some(3)],
]
}
fn instances() -> Vec<Instance> {
vec![
Instance::new(
"AllDifferent",
doms(4, 4),
&[0, 1, 2, 3],
AllDifferent::new,
true,
),
Instance::new(
"AllDifferent, partial scope",
doms(5, 3),
&[0, 1, 3],
AllDifferent::new,
true,
),
Instance::new(
"NotEquals",
doms(4, 3),
&[1, 3],
|v, p| NotEquals::new(v[0], v[1], p),
true,
),
Instance::new(
"Among",
doms(4, 3),
&[0, 1, 2, 3],
|v, _| Among::new(v, set(&[1, 2]), 1, 2),
true,
),
Instance::new(
"Among, partial scope",
doms(5, 3),
&[0, 2, 3, 4],
|v, _| Among::new(v, set(&[1, 2]), 1, 2),
true,
),
Instance::new(
"AtLeast",
doms(4, 3),
&[0, 1, 2, 3],
|v, _| AtLeast::new(v, set(&[1]), 2),
true,
),
Instance::new(
"AtLeast, partial scope",
doms(5, 3),
&[1, 2, 4],
|v, _| AtLeast::new(v, set(&[0, 2]), 2),
true,
),
Instance::new(
"Gcc",
doms(4, 3),
&[0, 1, 2, 3],
|v, _| Gcc::new(v, vec![(0, 1, 2), (1, 0, 1), (2, 1, 3)]),
true,
),
Instance::new(
"Gcc, saturating bounds",
doms(4, 3),
&[0, 1, 2, 3],
|v, _| Gcc::new(v, vec![(0, 1, 4), (1, 0, 4)]),
true,
),
Instance::new(
"Gcc, partial scope",
doms(5, 3),
&[0, 1, 3, 4],
|v, _| Gcc::new(v, vec![(0, 1, 2), (1, 1, 1)]),
true,
),
Instance::new(
"Sum",
doms(4, 3),
&[0, 1, 2, 3],
|v, p| Sum::new(v, 4, p),
true,
),
Instance::new(
"Sum, partial scope",
doms(5, 3),
&[0, 1, 3],
|v, p| Sum::new(v, 3, p),
true,
),
Instance::new(
"Regular",
doms(4, 3),
&[0, 1, 2, 3],
|v, p| Regular::new(v, no_one_then_zero(), 0, FxHashSet::from_iter([0, 1, 2]), p),
true,
),
Instance::new(
"Regular, partial scope",
doms(5, 3),
&[0, 2, 3],
|v, p| Regular::new(v, no_one_then_zero(), 0, FxHashSet::from_iter([1, 2, 3]), p),
true,
),
]
}
fn assignments(instance: &Instance) -> Vec<Vec<isize>> {
let mut all: Vec<Vec<isize>> = vec![vec![]];
for domain in &instance.domains {
all = all
.into_iter()
.flat_map(|prefix| {
domain.iter().map(move |&v| {
let mut t = prefix.clone();
t.push(v);
t
})
})
.collect();
}
all
}
fn top_down(constraint: &dyn Constraint, prefix: &[isize]) -> Box<dyn ConstraintProperty> {
let mut property = constraint.empty_property();
for (layer, &value) in prefix.iter().enumerate() {
let mut next = constraint.identity_property();
next.update(&*property, value, constraint.is_layer_in_scope(layer));
property = next;
}
property
}
fn bottom_up(
constraint: &dyn Constraint,
from: usize,
t: &[isize],
) -> Box<dyn ConstraintProperty> {
let mut property = constraint.empty_property_backward();
for layer in (from..t.len()).rev() {
let mut next = constraint.identity_property();
next.update_backward(&*property, t[layer], constraint.is_layer_in_scope(layer));
property = next;
}
property
}
fn removed_at(constraint: &dyn Constraint, t: &[isize], layer: usize) -> bool {
let parent = top_down(constraint, &t[..layer]);
let child = bottom_up(constraint, layer + 1, t);
constraint.is_assignment_invalid(&*parent, &*child, layer, t[layer])
}
struct Lcg(u64);
impl Lcg {
fn below(&mut self, bound: usize) -> usize {
self.0 = self
.0
.wrapping_mul(6364136223846793005)
.wrapping_add(1442695040888963407);
((self.0 >> 33) as usize) % bound
}
}
fn top_down_pool(instance: &Instance, rng: &mut Lcg) -> Vec<Vec<Box<dyn ConstraintProperty>>> {
let c = instance.constraint.as_ref();
let all = assignments(instance);
(0..instance.layers())
.map(|l| {
let mut pool: Vec<Box<dyn ConstraintProperty>> =
all.iter().map(|t| top_down(c, &t[..l])).collect();
for _ in 0..20 {
let mut merged = pool[rng.below(pool.len())].clone();
merged.merge(&*pool[rng.below(pool.len())]);
pool.push(merged);
}
pool
})
.collect()
}
fn bottom_up_pool(instance: &Instance, rng: &mut Lcg) -> Vec<Vec<Box<dyn ConstraintProperty>>> {
let c = instance.constraint.as_ref();
let all = assignments(instance);
(0..=instance.layers())
.map(|l| {
let mut pool: Vec<Box<dyn ConstraintProperty>> =
all.iter().map(|t| bottom_up(c, l, t)).collect();
for _ in 0..20 {
let mut merged = pool[rng.below(pool.len())].clone();
merged.merge(&*pool[rng.below(pool.len())]);
pool.push(merged);
}
pool
})
.collect()
}
fn same(a: &dyn ConstraintProperty, b: &dyn ConstraintProperty) -> bool {
ConstraintProperty::eq(a, b)
}
fn hash_of(property: &dyn ConstraintProperty) -> u64 {
use std::hash::Hasher;
let mut hasher = FxHasher::default();
property.hash(&mut hasher);
hasher.finish()
}
fn merged(
a: &(dyn ConstraintProperty + 'static),
b: &dyn ConstraintProperty,
) -> Box<dyn ConstraintProperty> {
let mut m = dyn_clone::clone_box(a);
m.merge(b);
m
}
#[test]
fn an_assignment_that_satisfies_the_constraint_is_never_removed() {
for instance in instances() {
let c = instance.constraint.as_ref();
for t in assignments(&instance) {
if !c.is_satisfied(&t) {
continue;
}
for layer in (0..instance.layers()).filter(|&l| c.is_layer_in_scope(l)) {
assert!(
!removed_at(c, &t, layer),
"{}: {t:?} satisfies the constraint but its edge at layer {layer} is removed",
instance.name
);
}
}
}
}
#[test]
fn an_assignment_that_violates_the_constraint_is_removed_somewhere() {
for instance in instances().into_iter().filter(|i| i.complete) {
let c = instance.constraint.as_ref();
let mut violating = 0;
for t in assignments(&instance) {
if c.is_satisfied(&t) {
continue;
}
violating += 1;
let removed = (0..instance.layers())
.filter(|&l| c.is_layer_in_scope(l))
.any(|l| removed_at(c, &t, l));
assert!(
removed,
"{}: {t:?} violates the constraint and no edge of its path is removed",
instance.name
);
}
assert!(violating > 0, "{}: nothing is violated", instance.name);
}
}
#[test]
fn the_instances_have_both_solutions_and_violations() {
for instance in instances() {
let c = instance.constraint.as_ref();
let all = assignments(&instance);
let sat = all.iter().filter(|t| c.is_satisfied(t)).count();
assert!(
sat > 0 && sat < all.len(),
"{}: {sat}/{}",
instance.name,
all.len()
);
}
}
#[test]
fn merge_is_a_join() {
let mut rng = Lcg(1);
for instance in instances() {
let c = instance.constraint.as_ref();
let identity = c.identity_property();
for pool in top_down_pool(&instance, &mut rng)
.into_iter()
.chain(bottom_up_pool(&instance, &mut rng))
{
for _ in 0..200 {
let a = &pool[rng.below(pool.len())];
let b = &pool[rng.below(pool.len())];
let d = &pool[rng.below(pool.len())];
let name = instance.name;
assert!(same(&*merged(&**a, &**a), &**a), "{name}: not idempotent");
assert!(
same(&*merged(&**a, &**b), &*merged(&**b, &**a)),
"{name}: not commutative"
);
assert!(
same(
&*merged(&*merged(&**a, &**b), &**d),
&*merged(&**a, &*merged(&**b, &**d))
),
"{name}: not associative"
);
assert!(
same(&*merged(&**a, &*identity), &**a),
"{name}: the identity is not neutral on the right"
);
assert!(
same(&*merged(&*identity, &**a), &**a),
"{name}: the identity is not neutral on the left"
);
}
}
}
}
#[test]
fn folding_two_parents_is_merging_the_two_folds() {
let mut rng = Lcg(2);
for instance in instances() {
let c = instance.constraint.as_ref();
let td = top_down_pool(&instance, &mut rng);
let bu = bottom_up_pool(&instance, &mut rng);
for layer in 0..instance.layers() {
for &value in &instance.domains[layer] {
for in_scope in [true, false] {
for (pool, backward) in [(&td[layer], false), (&bu[layer + 1], true)] {
for _ in 0..100 {
let a = &pool[rng.below(pool.len())];
let b = &pool[rng.below(pool.len())];
let fold = |others: &[&dyn ConstraintProperty]| {
let mut p = c.identity_property();
for other in others {
if backward {
p.update_backward(*other, value, in_scope);
} else {
p.update(*other, value, in_scope);
}
}
p
};
let both = fold(&[&**a, &**b]);
let reversed = fold(&[&**b, &**a]);
let apart = merged(&*fold(&[&**a]), &*fold(&[&**b]));
let name = instance.name;
assert!(
same(&*both, &*apart),
"{name}: folding two parents differs from merging the folds (layer {layer}, value {value}, in scope {in_scope}, backward {backward})"
);
assert!(
same(&*both, &*reversed),
"{name}: the fold depends on the order of the parents"
);
}
}
}
}
}
}
}
#[test]
fn a_merged_node_never_removes_an_edge_of_a_satisfying_assignment() {
let mut rng = Lcg(3);
let mut checked = 0;
let mut removed = 0;
for instance in instances() {
let c = instance.constraint.as_ref();
let all = assignments(&instance);
for layer in (0..instance.layers()).filter(|&l| c.is_layer_in_scope(l)) {
for _ in 0..400 {
let prefixes: Vec<&Vec<isize>> = (0..1 + rng.below(4))
.map(|_| &all[rng.below(all.len())])
.collect();
let suffixes: Vec<&Vec<isize>> = (0..1 + rng.below(4))
.map(|_| &all[rng.below(all.len())])
.collect();
let mut parent = top_down(c, &prefixes[0][..layer]);
for p in &prefixes[1..] {
parent.merge(&*top_down(c, &p[..layer]));
}
let mut child = bottom_up(c, layer + 1, suffixes[0]);
for s in &suffixes[1..] {
child.merge(&*bottom_up(c, layer + 1, s));
}
for &value in &instance.domains[layer] {
let invalid = c.is_assignment_invalid(&*parent, &*child, layer, value);
removed += usize::from(invalid);
for p in &prefixes {
for s in &suffixes {
let mut t = p[..layer].to_vec();
t.push(value);
t.extend_from_slice(&s[layer + 1..]);
if c.is_satisfied(&t) {
checked += 1;
assert!(
!invalid,
"{}: merging {} prefixes and {} suffixes removes the edge {value} of {t:?} at layer {layer}",
instance.name,
prefixes.len(),
suffixes.len()
);
}
}
}
}
}
}
}
assert!(checked > 0 && removed > 0, "the law was never exercised");
}
#[test]
fn equality_is_an_equivalence_and_agrees_with_the_hash() {
let mut rng = Lcg(4);
for instance in instances() {
let pools = top_down_pool(&instance, &mut rng);
for pool in pools {
for a in &pool {
assert!(same(&**a, &**a), "{}: eq is not reflexive", instance.name);
let copy = a.clone();
assert!(same(&*copy, &**a) && hash_of(&*copy) == hash_of(&**a));
}
for _ in 0..300 {
let a = &pool[rng.below(pool.len())];
let b = &pool[rng.below(pool.len())];
assert_eq!(
same(&**a, &**b),
same(&**b, &**a),
"{}: eq is not symmetric",
instance.name
);
if same(&**a, &**b) {
assert_eq!(
hash_of(&**a),
hash_of(&**b),
"{}: equal properties hash differently",
instance.name
);
}
}
}
}
}
#[test]
fn dyn_properties_can_be_deduplicated_in_a_hash_set() {
let mut rng = Lcg(5);
for instance in instances() {
let pool = &top_down_pool(&instance, &mut rng)[instance.layers() - 1];
let mut classes: Vec<&Box<dyn ConstraintProperty>> = vec![];
for p in pool {
if !classes.iter().any(|q| same(&***q, &**p)) {
classes.push(p);
}
}
let hashed: std::collections::HashSet<Box<dyn ConstraintProperty>> =
pool.iter().cloned().collect();
assert_eq!(hashed.len(), classes.len(), "{}", instance.name);
}
}
#[test]
fn equal_properties_filter_alike() {
let mut rng = Lcg(6);
let mut pairs = 0;
for instance in instances() {
let c = instance.constraint.as_ref();
let td = top_down_pool(&instance, &mut rng);
let bu = bottom_up_pool(&instance, &mut rng);
for layer in (0..instance.layers()).filter(|&l| c.is_layer_in_scope(l)) {
for (side, pool, other) in [
("parent", &td[layer], &bu[layer + 1]),
("child", &bu[layer + 1], &td[layer]),
] {
for (i, a) in pool.iter().enumerate() {
let Some(b) = pool[..i].iter().find(|b| same(&***b, &**a)) else {
continue;
};
pairs += 1;
for o in other.iter() {
for &value in &instance.domains[layer] {
let (ra, rb) = if side == "parent" {
(
c.is_assignment_invalid(&**a, &**o, layer, value),
c.is_assignment_invalid(&**b, &**o, layer, value),
)
} else {
(
c.is_assignment_invalid(&**o, &**a, layer, value),
c.is_assignment_invalid(&**o, &**b, layer, value),
)
};
assert_eq!(
ra, rb,
"{}: equal {side} properties filter differently (layer {layer}, value {value})",
instance.name
);
}
}
}
}
}
}
assert!(pairs > 0);
}
#[test]
fn a_clone_is_independent_of_the_original() {
let mut rng = Lcg(7);
for instance in instances() {
let pool = &top_down_pool(&instance, &mut rng)[instance.layers() / 2];
for _ in 0..100 {
let a = &pool[rng.below(pool.len())];
let b = &pool[rng.below(pool.len())];
let snapshot = a.clone();
let mut copy = a.clone();
copy.merge(&**b);
copy.update(&**b, instance.domains[0][0], true);
assert!(
same(&**a, &*snapshot),
"{}: changing a clone changed the original",
instance.name
);
}
}
}
#[test]
fn order_keys_are_finite_and_have_a_fixed_length() {
let mut rng = Lcg(8);
for instance in instances() {
let c = instance.constraint.as_ref();
let length = c.empty_property().order_key().len();
for pool in top_down_pool(&instance, &mut rng)
.into_iter()
.chain(bottom_up_pool(&instance, &mut rng))
{
for p in pool {
let key = p.order_key();
assert_eq!(key.len(), length, "{}", instance.name);
assert!(
key.iter().all(|x| x.is_finite()),
"{}: {key:?}",
instance.name
);
}
}
assert_eq!(
c.identity_property().order_key().len(),
length,
"{}",
instance.name
);
}
}
#[test]
fn the_key_has_the_arity_of_the_scope() {
let mut problem = Problem::default();
for instance in instances() {
let c = instance.constraint.as_ref();
let key = c.structural_key(&problem);
assert_eq!(key.arity(), instance.scope_len, "{}", instance.name);
assert_eq!(key.arity(), c.iter_scope().count(), "{}", instance.name);
assert_eq!(dyn_clone::clone_box(c).structural_key(&problem), key);
}
problem.add_variable(vec![0]);
}
#[test]
fn as_any_gives_back_the_concrete_constraint() {
for instance in instances() {
assert_eq!(
instance.constraint.as_any().type_id(),
instance.type_id,
"{}",
instance.name
);
}
}
#[test]
fn every_kind_of_constraint_has_its_own_name() {
let mut names: Vec<&'static str> =
instances().iter().map(|i| i.constraint.name()).collect();
names.sort_unstable();
names.dedup();
assert_eq!(
names,
vec![
"AllDifferent",
"Among",
"AtLeast",
"GCC",
"Not Equals",
"Regular",
"Sum"
]
);
}
#[test]
fn the_scope_is_what_is_satisfied_reads() {
for instance in instances() {
let c = instance.constraint.as_ref();
let scope: Vec<usize> = c.iter_scope().map(|v| v.0).collect();
for t in assignments(&instance) {
for outside in (0..instance.layers()).filter(|i| !scope.contains(i)) {
for &other in &instance.domains[outside] {
let mut u = t.clone();
u[outside] = other;
assert_eq!(c.is_satisfied(&t), c.is_satisfied(&u), "{}", instance.name);
}
}
}
}
}
#[test]
fn layers_in_scope_are_the_layers_of_the_scope_variables() {
for instance in instances() {
let c = instance.constraint.as_ref();
let scope: Vec<usize> = c.iter_scope().map(|v| v.0).collect();
for layer in 0..instance.layers() {
assert_eq!(
c.is_layer_in_scope(layer),
scope.contains(&layer),
"{}",
instance.name
);
}
}
}
#[test]
fn the_size_of_a_property_is_reported() {
for instance in instances() {
assert!(
instance.constraint.identity_property().deep_size_of() > 0,
"{}",
instance.name
);
}
}
#[derive(Clone, deepsize::DeepSizeOf)]
struct Counter(usize);
impl ConstraintProperty for Counter {
fn update(&mut self, _: &dyn ConstraintProperty, _: isize, _: bool) {
self.0 += 1;
}
fn merge(&mut self, _: &dyn ConstraintProperty) {}
fn hash(&self, hasher: &mut dyn Hasher) {
hasher.write_usize(self.0);
}
fn eq(&self, other: &dyn ConstraintProperty) -> bool {
other
.as_any()
.downcast_ref::<Counter>()
.is_some_and(|o| o.0 == self.0)
}
fn order_key(&self) -> Vec<f64> {
vec![self.0 as f64]
}
fn is_single_state(&self) -> bool {
true
}
fn as_any(&self) -> &dyn Any {
self
}
fn name(&self) -> &'static str {
"Counter"
}
}
macro_rules! constraint_with_defaults {
($name:ident, { $($extra:item)* }) => {
#[derive(Clone, deepsize::DeepSizeOf)]
struct $name;
impl Constraint for $name {
fn update_variable_ordering(&mut self, _: &[VariableIndex]) {}
fn structural_key(&self, _: &Problem) -> ConstraintShapeKey {
ConstraintShapeKey::NotEquals
}
fn is_layer_in_scope(&self, _: usize) -> bool {
true
}
fn iter_scope(&self) -> Box<dyn Iterator<Item = VariableIndex> + '_> {
Box::new(std::iter::empty())
}
fn is_satisfied(&self, _: &[isize]) -> bool {
true
}
fn name(&self) -> &'static str {
stringify!($name)
}
fn as_any(&self) -> &dyn Any {
self
}
fn identity_property(&self) -> Box<dyn ConstraintProperty> {
Box::new(Counter(7))
}
fn is_assignment_invalid(&self, _: &dyn ConstraintProperty, _: &dyn ConstraintProperty, _: usize, _: isize) -> bool {
false
}
$($extra)*
}
};
}
constraint_with_defaults!(OnlyRequired, {});
constraint_with_defaults!(WithEmpty, {
fn empty_property(&self) -> Box<dyn ConstraintProperty> {
Box::new(Counter(9))
}
});
fn counter_of(property: &dyn ConstraintProperty) -> usize {
property.as_any().downcast_ref::<Counter>().unwrap().0
}
#[test]
fn by_default_there_is_no_precedence_requirement() {
assert!(OnlyRequired.precedence_edges().is_empty());
}
#[test]
fn by_default_the_root_and_the_sink_hold_the_identity() {
assert_eq!(counter_of(&*OnlyRequired.empty_property()), 7);
assert_eq!(counter_of(&*OnlyRequired.empty_property_backward()), 7);
}
#[test]
fn by_default_the_sink_holds_the_property_of_the_root() {
assert_eq!(counter_of(&*WithEmpty.empty_property()), 9);
assert_eq!(counter_of(&*WithEmpty.empty_property_backward()), 9);
}
#[test]
fn by_default_the_backward_update_is_the_update() {
let mut property = Counter(0);
property.update_backward(&Counter(0), 3, true);
assert_eq!(property.0, 1);
}
#[test]
fn the_arity_of_every_kind_of_key() {
let keys = [
(ConstraintShapeKey::AllDifferent { arity: 5 }, 5),
(ConstraintShapeKey::NotEquals, 2),
(
ConstraintShapeKey::Among {
arity: 4,
values: vec![1],
lb: 0,
ub: 2,
},
4,
),
(
ConstraintShapeKey::AtLeast {
arity: 3,
values: vec![1],
lb: 1,
},
3,
),
(
ConstraintShapeKey::Gcc {
arity: 6,
bounds: vec![(1, 0, 2)],
},
6,
),
(
ConstraintShapeKey::Regular {
arity: 7,
transitions: vec![vec![Some(0)]],
initial_state: 0,
accepting_states: vec![0],
},
7,
),
(
ConstraintShapeKey::Sum {
arity: 8,
target: 3,
},
8,
),
];
for (key, arity) in keys {
assert_eq!(key.arity(), arity, "{key:?}");
}
}
#[test]
fn keys_of_different_kinds_are_never_equal() {
let a = ConstraintShapeKey::AllDifferent { arity: 2 };
let b = ConstraintShapeKey::Sum {
arity: 2,
target: 0,
};
assert_ne!(a, b);
assert_ne!(a, ConstraintShapeKey::NotEquals);
}
#[test]
fn the_property_of_a_single_path_is_a_single_state() {
for instance in instances() {
let c = instance.constraint.as_ref();
assert!(c.empty_property().is_single_state(), "{}", instance.name);
for tuple in assignments(&instance) {
for layer in 0..=instance.layers() {
assert!(
top_down(c, &tuple[..layer]).is_single_state(),
"{}: prefix {:?}",
instance.name,
&tuple[..layer]
);
}
}
}
}
}