Leverage softfail information

There are 4 propagators that use a notion of "softfailing". Constraint propagation softfails if no deduction can be made at this point. In other words, the constraint can still be satisfied or violated and the propagator is unable to enforce constraint satisfaction. The critical holes involved in a softfail are stored and could be used to reduce the number of re-propagations.

As of 06/05/2024, softfailing happens in these 4 constraints:

LocalForbidden
LocalOrdered
LocalContains
LocalUnique

"Forbidden" Example

Forbidden constraint: 4{2, 1} Current tree: 4{HOLE[1, 2], HOLE[1, 2], 1}.

In this case, the pattern_match function will return a PatternMatchSoftFail that holds a reference to the two holes involved in the softfail.

These references are currently ignored, but could be used to reduce the number of propagations by implementing a 2-watcher scheme. We only need to re-propagate this constraint if at least one of the domains of the holes involved in the soft fail is updated.

"Ordered" Example

Ordered constraint: 4{:a, :b}, :a <= :b Current tree: 4{5{1, HOLE[1, 2]}, 5{1, HOLE[1, 2]}}.

The make_less_than_or_equal! tree manipulation will return a LessThanOrEqualSoftFail, since the assignment of the 2 holes involved is ambiguous. This result holds references to the holes involved, but they are currently ignored. The number of re-propagations can be reduced by only re-propagating on manipulations on these holes.

"Contains" Example ("Unique" is similar)

Contains constraint: Contains(2) Current tree: 4{4{HOLE[1, 3], HOLE[1, 2]}, 4{HOLE[2, 3], HOLE[1, 3]}}.

For simplicity, assume all holes hold terminal rules. This propagator will soft fail with a list of n rules that can potentially hold a 2. The constraint should only be repropagated if n-1 of these domains are updated (in this example, n=3).

Herb-AI / HerbConstraints.jl