commit: 322a5f0b4f92731d36bb1922697a59472e20eace Author: Brian Harring <ferringb <AT> gmail <DOT> com> AuthorDate: Wed Dec 21 23:26:15 2022 +0000 Commit: Arthur Zamarin <arthurzam <AT> gentoo <DOT> org> CommitDate: Thu Dec 22 03:10:33 2022 +0000 URL: https://gitweb.gentoo.org/proj/pkgcore/pkgcore.git/commit/?id=322a5f0b
pmerge: sort target processing to stabilize the graph. The current resolver is effectively brute force graph exploration, iteratively adding results to the graph changing previously decisions based on new requests. This means that the resolver *can* produce different solutions if the order of constraints added to it differ. It's desirable the resolver behaviour be reproducible, thus change the default behaviour to sort the target list given to the resolver. As to why we don't force sorting within the resolver itself; for processing of package dependencies, those are already stably ordered. A future enhancement would be to modify the resolver to be explicit, but that's for when the resolver is rewritten. Currently the source of instability is the atoms fed to the resolver from pmerge, thus why I'm adding the sorting in pmerge. Finally: the resolver must always produce a solution, or must always not, irregardless of the argument ordering it's given. Thus '--disable-resolver-target-sorting' is added to allow disabling the sorting and doing something of a random entry/walk into the depgraph. This can produce differing solutions than what a sorted entry would produce; that is working as intended (there is no global optimizer of solutions, thus 'first solution' is what pmerge uses). Basically, these two invocations should agree that a solution exists, or doesn't. If they disagree this directly shows that the resolver is failing to explore solution space fully: * `pmerge <targets> --disable-resolver-target-sorting` * `pmerge <targets> Signed-off-by: Brian Harring <ferringb <AT> gmail.com> src/pkgcore/scripts/pmerge.py | 20 ++++++++++++++++++++ 1 file changed, 20 insertions(+) diff --git a/src/pkgcore/scripts/pmerge.py b/src/pkgcore/scripts/pmerge.py index 77046feb1..8ea24c8c6 100644 --- a/src/pkgcore/scripts/pmerge.py +++ b/src/pkgcore/scripts/pmerge.py @@ -286,6 +286,23 @@ debug_options.add_argument( what it has decided and why. """ ) +debug_options.add_argument( + '--disable-resolver-target-sorting', dest='force_stable_ordering_of_targets', + action='store_false', default=True, + help='disable stabilization of resolver graph processing', + docs=""" + Resolution of package dependencies can grossly vary depending on which nodes you start from. + + Pmerge by default sorts the targets it's asked to resolve; this in turn stabilizes the resolvers + output. This option allows disabling that sort. + + This should be only used if you're debugging the resolver and wish to effectively fuzz the resolvers + ability to find solutions; for a properly working resolver if a solution can be found, it *must* + be found. If a solution can't be found, then this flag should also result in no solution found. + + Any deviation from this is a bug in the resolver and should be reported. + """ +) class AmbiguousQuery(parserestrict.ParseError): @@ -640,6 +657,7 @@ def main(options, out, err): # This mode does not care about sets and packages so bypass all that. if options.unmerge: + # TODO: this logic should be updated to honor self.force_stable_ordering_of_targets if not options.oneshot: if world_set is None: argparser.error("disable world updating via --oneshot, " @@ -702,6 +720,8 @@ def main(options, out, err): return 1 atoms = stable_unique(atoms) + if options.force_stable_ordering_of_targets: + atoms = sorted(atoms) if options.clean and not options.oneshot: if world_set is None: