Adding a constraint¶
A constraint is a Rust type that tells the MDD compiler what it forbids. The contract, the
protocol the compiler follows and the laws an implementation must obey are written once, in the
module documentation of aicad::constraints (the Rust documentation). This page lists the places
a constraint touches, in order, including the Python side. Start from src/constraints/among.rs,
the shortest constraint.
The set of constraints is closed: the compiler shares compiled structures between constraints of
the same shape through an enum (ConstraintShapeKey) that rebuilds each constraint. A constraint
therefore has to be added to this crate; it cannot be plugged in from another one.
Steps¶
Write the module
src/constraints/<name>.rs, with the//!header sections of the existing ones: meaning, how it compiles (property update, node merging, edge filtering), design notes, example. Say what an empty scope, a repeated variable and a changed domain do.Implement
Constraintand a private property type implementingConstraintProperty. The constructor should panic, with a clear message, on input that cannot mean anything.is_satisfiedis the specification: everything else is an implementation of it that can be wrong.Declare it in
src/constraints/mod.rsand add a builder inbuilders.rsthat creates the constraint and adds it to aProblem.Add a variant to
ConstraintShapeKey(insrc/modelling/constraint.rs) and toarity, and return it fromstructural_key. The key must hold everything the compiled structure depends on and nothing else, in a canonical form: sort sets, so that two declarations in a different order share a structure.Rebuild it in the arena: add the case to
instantiate_constraintinsrc/mdd/arena.rs. The match is exhaustive, so the compiler points at it.Expose it to Python:
a method on
PyProbleminsrc/pyaicad/problem.rsthat checks its arguments and calls the builder (errors arePyValueErrors with a message that names the argument);a constraint class and a function in
python/pyaicad/model.py, validating the arguments with the helpers there and calling the native method in_apply;an export in
python/pyaicad/__init__.py, an entry inpython/pyaicad/_core.pyi, and a line indocs/api.md.
Document it where users look: the docstring of the Python function (with a small doctest) and, if it opens a new kind of model, a sentence in the modelling chapter of the Python and Rust guides.
Worked example: Sum¶
Sum ($\sum_i x_i = t$) is the smallest constraint that needs a real summary, so every step above can be
read on it. All the Rust below is pulled from the source, not retyped.
The idea. A node of the diagram has to remember, for the paths that reach it, what the rest of
the diagram needs to know about the sum so far. Remembering every possible partial sum would give as
many nodes as sums. Sum keeps only the smallest and the largest, an interval, which is cheap and
lets the compiler discard an edge whose paths cannot reach the target.
The property (step 2) holds that interval. isize::MAX and isize::MIN are the sentinels of
“no path yet”, which is the identity of the fold:
struct SumProperty {
/// The smallest sum of the paths summarised.
min: isize,
/// The largest sum of the paths summarised.
max: isize,
}
Folding and merging are the two operations the compiler uses to build and shrink properties. An
edge of value v shifts the interval of its parent by v (only in the scope; other layers copy it),
and several parents are combined by widening; merging two nodes does the same.
fn update(&mut self, other: &dyn ConstraintProperty, assignment: isize, in_scope: bool) {
let other = other
.as_any()
.downcast_ref::<SumProperty>()
.unwrap_or_else(|| {
panic!(
"Calling update on property {} with other property of type {}",
self.name(),
other.name()
);
});
let delta = if in_scope { assignment } else { 0 };
// The sentinels (no path yet) must stay sentinels: adding to them would overflow.
let other_min = if other.min == isize::MAX {
isize::MAX
} else {
other.min + delta
};
let other_max = if other.max == isize::MIN {
isize::MIN
} else {
other.max + delta
};
self.min = self.min.min(other_min);
self.max = self.max.max(other_max);
}
fn merge(&mut self, other: &dyn ConstraintProperty) {
let other = other
.as_any()
.downcast_ref::<SumProperty>()
.unwrap_or_else(|| {
panic!(
"Calling merge on property {} with other property of type {}",
self.name(),
other.name()
);
});
self.min = self.min.min(other.min);
self.max = self.max.max(other.max);
}
(The downcast_ref and its panic! only check that the compiler did not hand a property of another
kind of constraint to this one; every property type repeats it.)
Filtering is what makes the diagram smaller. An edge between a parent whose sums lie in $[m_p, M_p]$ and a child in $[m_c, M_c]$ lies on paths whose total is somewhere in $[m_p + v + m_c,\ M_p + v + M_c]$; if the target is outside, the edge goes:
// A node without any path (the sentinels) cannot be crossed by an edge. This also keeps
// the additions below away from the sentinels, which would overflow.
if parent.min > parent.max || child.min > child.max {
return true;
}
let local_min = parent.min + child.min + assignment;
let local_max = parent.max + child.max + assignment;
local_min > self.target || local_max < self.target
This is bounds reasoning: a total inside the interval that no path reaches is not detected, so a
compiled diagram may keep paths that do not sum to the target until nodes are split enough for the
intervals to become points. That is why the tests compare with is_satisfied and a brute-force
count, and why the module header says it.
The key (step 4) holds the arity and the target, and nothing else:
fn structural_key(&self, _problem: &Problem) -> ConstraintShapeKey {
ConstraintShapeKey::Sum {
arity: self.variables.len(),
target: self.target,
}
}
and the arena rebuilds a Sum from it on a synthetic problem (step 5):
ConstraintShapeKey::Sum { arity: _, target } => {
Box::new(Sum::new(synthetic_variables, *target, synthetic_problem))
}
The constructor refuses a repeated variable, because the property cannot tell how many times a layer counts:
let distinct: FxHashSet<VariableIndex> = variables.iter().copied().collect();
if distinct.len() != variables.len() {
panic!("Sum does not support a variable repeated in its scope");
}
The builder and the Python side (steps 3 and 6) are a few lines each:
// src/constraints/builders.rs
pub fn sum(problem: &mut Problem, variables: Vec<VariableIndex>, target: isize) -> ConstraintIndex {
problem.add_constraint(Sum::new(variables, target, problem))
}
// src/pyaicad/problem.rs, a method of PyProblem
fn add_sum(&mut self, scope: Vec<usize>, target: isize) -> PyResult<()> {
let vars = scope.into_iter().map(VariableIndex).collect();
sum(self.mutate()?, vars, target);
Ok(())
}
# python/pyaicad/model.py
@dataclass(frozen=True)
class _SumEquals(Constraint):
scope: Tuple[Var, ...]
target: int
def _apply(self, native: Any) -> None:
native.add_sum(_idx(self.scope), self.target)
def sum_equals(variables: Iterable[Var], target: int) -> Constraint:
"""The variables add up to ``target``. Values may be negative."""
scope = _variables(variables, "sum_equals", distinct=True)
return _SumEquals(scope, operator.index(target))
Python validates the shape of the input (distinct=True rejects a repeated variable with a
ModelError that names the function); Rust owns what the constraint means.
Tests¶
The compiled MDD must contain every solution at every width and be exact once fully refined, compared with
is_satisfiedand a brute-force enumeration on small instances.Add an instance of the constraint to
test_contractat the end ofsrc/constraints/mod.rs, which checks the laws of the contract (identity, merge, update direction).Add it to the oracle in
tests/oracle.py, so that the Python tests compare compiled solution counts with a brute-force count, and add a Python test for the argument validation.