Formula constraints

Initial work required for #168.

I revived this work recently, which was first started some time ago.

Generally speaking, this changes how the dependency formula is constructed so that all special variables introduced for the purpose of constructing the more complex expressions in dependencies have a value that exactly matches the expression.

Currently, CNF clauses in the dependency formula are wrapped in "conditionals".

E.g. A package cat/foo with dependency cat/bar-dep and cat/baz-dep might have clauses like

• !cat/foo | cat/bar-dep
• !cat/foo | cat/baz-dep I.e. either cat/baz-dep is required, or cat/foo must not be installed as the dependency isn't necessary if the package requiring it is not installed.

What this changes it to is that it introduces variables to represent whether or not a part of the formula is satisfied, and then uses the initial conditions to create something like a tree of requirements.

E.g. We create a variable A to express the dependencies of package cat/foo

Then for the above example, we constrain A such that it is true if and only if cat/bar-dep and cat/baz-dep are enabled. Then if we want cat/foo to be installed (and it gets its own dependency token), we also require that A must be true, or if another package depends on cat/foo, it would require that A must be true if (but not only if) that other package is installed.

TODO: This description should probably be adapted as comments in the code.

Status

Constraints on REQUIRED_USE conditions are functional. Constraints on the DEPEND strings are implemented, but not working at the moment.

Weights for flags now apply whether or not the package is installed (but won't affect the outcome since we discard flags for packages which aren't enabled after dependency calculation). Flags are now always forced to disabled for packages which are not installed.

Future Work

Enumerating over solutions to the dependency formula using the RC2.enumerate function should always produce meaningfully different results once this is complete, making it possible to look at equivalent dependency configurations, or even dependency configurations that differ from the optimal by a small amount. Then we'll need to compare the differences and provide an interface to choose between the options.