Variable vs Constraint-based solver

[perdasilva]

Hey everyone,

I wanted to ask you what you think about the work I've put together in this PR.

Currently, the solver takes as input a slice of variables. Variable is an interface that connects an Identifier with a set of Constraints for the purposes of generating gini literals when the constraint is applied (e.g. see the dependency constraint).

I've refactored the Solver to take as input a slice of Constraints, which were themselves refactored to contain the subject of the constraint (i.e.). I did this because I think it will make it easier to express arbitrary constraints (inc. conjunctions and disjunctions of arbitrary constraints).

For instance, if we have two variables:

A:

• mandatory
• dependency(X, Y, Z)
  B:
• mandatory
• dependency(C, D, E)

It would be hard to express something like (A OR B), especially given that each Variable must only appear once in the input .

With a constraint based approach, you could simply add a new constraint, e.g. Or(Mandatory("a"), Mandatory("b")).

[akihikokuroda]

Is this a OR b (c depends on)?

[perdasilva]

That's right. The dependency constraint is an implication: A -> B, which gets translated to (B or ~A).
Because a package dependency can be fulfilled by multiple bundles, you'd have A -> B1 or A-> B2 or A -> B3, etc.
This simplifies to (B1 or B2 or B3 or .. Bn or ~A). If we want to install A, for the clause to the true, one (or more) of B1..Bn must be true.
This is why we also need another constraint over the B1..Bn to say that AtMost 1 can be true.

[perdasilva]

After an interesting conversation on slack. It seems going the Variable way, might be the right way.