Skip to content

More complex dependency solver

Benjamin Winger requested to merge bmwinger/portmod:sat_depsolver into master

Closes #59 (closed), #41 (closed), #82 (closed).

This is probably the biggest change prior to 2.0. Basically, we use a MAX-SAT solver from pysat to determine a set of mods that do not cause any conflicts, and use soft constraints (i.e. Weighted MAX-SAT) to try and find the best configuration in terms of using the newest versions of mods that are available, avoiding installing/uninstalling mods unnecessarily, and preserving the user's use flag configuration if possible.

The one main thing that remains to be implemented before this can be merged is conflict tracing. That is, when an unresolvable conflict is found, we should display the mod that includes the blocker causing the conflict, and the trace of the dependency tree from the user's selected mods to the mod in question, in addition to the same trace for whichever mod requires the blocked mod to be installed (there may be multiple, in which case it should be sufficient to display this for just one, and note that n other mods also require the blocked mod).

REQUIRED_USE strings also need to be enforced. Edit: Done

I'm somewhat worried that the code is a little obtuse at the moment, so I will also attempt to clean it up as much as possible and include helpful comments as necessary.

An interesting caveat is that the way we solve this problem is different from Portage, and, as such, replicating portage's behaviour is not always desirable, as it would require extra work for very little gain. The main example of this I can think of is that currently, dependencies that aren't satisfied (e.g. from uninstalling with --delete or installing with --nodeps) will be pulled in by almost any command. The only way to avoid this would be to prune mods from the transactions that aren't in the selected mods dependency trees. I haven't dived too deeply into portage's dependency resolution, but I believe this trait is due to not attempting to ensure installed mod dependencies are resolved when installing mods. I think portage just tracks blockers for installed mods that aren't passed on the command line. This actually wouldn't be a bad idea if we ever have performance problems though, but for the moment the performance is quite good. I haven't tested this on a particularly large number of mods yet though; it remains to see how large the equations need to be before performance starts to become really poor (MAX-SAT is NP-hard after all). I'll have to start compiling a meta-momw/expanded-vanilla metamod, as ~123 or so mods would be a reasonably good test, compared to the 41 I currently have installed.

Update: No noticeable slowdown with the WIP expanded-vanilla metamod and 138 mods installed

Edited by Benjamin Winger

Merge request reports