From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from lists.gentoo.org (pigeon.gentoo.org [208.92.234.80]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits)) (No client certificate requested) by finch.gentoo.org (Postfix) with ESMTPS id ACC3E158020 for ; Thu, 22 Dec 2022 07:12:00 +0000 (UTC) Received: from pigeon.gentoo.org (localhost [127.0.0.1]) by pigeon.gentoo.org (Postfix) with SMTP id 92681E0843; Thu, 22 Dec 2022 07:11:59 +0000 (UTC) Received: from smtp.gentoo.org (woodpecker.gentoo.org [IPv6:2001:470:ea4a:1:5054:ff:fec7:86e4]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits)) (No client certificate requested) by pigeon.gentoo.org (Postfix) with ESMTPS id 78C14E0825 for ; Thu, 22 Dec 2022 07:11:59 +0000 (UTC) Received: from oystercatcher.gentoo.org (oystercatcher.gentoo.org [148.251.78.52]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (4096 bits)) (No client certificate requested) by smtp.gentoo.org (Postfix) with ESMTPS id 7981B3412C7 for ; Thu, 22 Dec 2022 07:11:58 +0000 (UTC) Received: from localhost.localdomain (localhost [IPv6:::1]) by oystercatcher.gentoo.org (Postfix) with ESMTP id 9CF1E7F0 for ; Thu, 22 Dec 2022 07:11:55 +0000 (UTC) From: "Arthur Zamarin" To: gentoo-commits@lists.gentoo.org Content-Transfer-Encoding: 8bit Content-type: text/plain; charset=UTF-8 Reply-To: gentoo-dev@lists.gentoo.org, "Arthur Zamarin" Message-ID: <1671678633.322a5f0b4f92731d36bb1922697a59472e20eace.arthurzam@gentoo> Subject: [gentoo-commits] proj/pkgcore/pkgcore:master commit in: src/pkgcore/scripts/ X-VCS-Repository: proj/pkgcore/pkgcore X-VCS-Files: src/pkgcore/scripts/pmerge.py X-VCS-Directories: src/pkgcore/scripts/ X-VCS-Committer: arthurzam X-VCS-Committer-Name: Arthur Zamarin X-VCS-Revision: 322a5f0b4f92731d36bb1922697a59472e20eace X-VCS-Branch: master Date: Thu, 22 Dec 2022 07:11:55 +0000 (UTC) Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: List-Id: Gentoo Linux mail X-BeenThere: gentoo-commits@lists.gentoo.org X-Auto-Response-Suppress: DR, RN, NRN, OOF, AutoReply X-Archives-Salt: 680134bc-0698-4093-be42-2e9007008ff7 X-Archives-Hash: d13e21e75266e09aa4f4df7633c89d98 commit: 322a5f0b4f92731d36bb1922697a59472e20eace Author: Brian Harring gmail com> AuthorDate: Wed Dec 21 23:26:15 2022 +0000 Commit: Arthur Zamarin gentoo 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 --disable-resolver-target-sorting` * `pmerge Signed-off-by: Brian Harring 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: