commit: 3487594cd8f46a5c83caaab3a9425321443e5efc Author: Zac Medico <zmedico <AT> gentoo <DOT> org> AuthorDate: Tue Nov 28 04:58:07 2023 +0000 Commit: Zac Medico <zmedico <AT> gentoo <DOT> org> CommitDate: Tue Nov 28 22:41:45 2023 +0000 URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=3487594c
Increase ignore_priority during topological sort for runtime cycle Fix AlternativesGzipTestCase by increasing ignore_priority in order to find smaller groups of leaf nodes during topological sort for runtime cycles. This causes some changes in merge order for MergeOrderTestCase, but they appear to be acceptable since they prevent temporarily unsatisfied RDEPEND by relying on satisfied installed build-time dependencies. Bug: https://bugs.gentoo.org/917259 Signed-off-by: Zac Medico <zmedico <AT> gentoo.org> lib/_emerge/depgraph.py | 27 ++++++++++++++++------ .../tests/resolver/test_alternatives_gzip.py | 8 +++---- lib/portage/tests/resolver/test_merge_order.py | 20 ++++++++-------- .../tests/resolver/test_rebuild_ghostscript.py | 2 +- 4 files changed, 35 insertions(+), 22 deletions(-) diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py index 29eadba3d1..da37f980ad 100644 --- a/lib/_emerge/depgraph.py +++ b/lib/_emerge/depgraph.py @@ -9478,17 +9478,30 @@ class depgraph: ) selected_nodes = [] while cycle_digraph: + # Increase ignore_priority in order to find + # smaller groups of leaf nodes. This solves + # bug 917259 which happened because too many + # leaves were selected at once. + smallest_leaves = None for ignore_priority in ignore_priorities: leaves = cycle_digraph.leaf_nodes( ignore_priority=ignore_priority ) - if leaves: - cycle_digraph.difference_update(leaves) - selected_nodes.extend(leaves) - break - else: - selected_nodes.extend(cycle_digraph) - break + if leaves and ( + smallest_leaves is None + or len(leaves) < len(smallest_leaves) + ): + smallest_leaves = leaves + if len(smallest_leaves) == 1: + break + + if smallest_leaves is None: + smallest_leaves = [cycle_digraph.order[-1]] + + # Only harvest one node at a time, in order to + # minimize the number of ignored dependencies. + cycle_digraph.remove(smallest_leaves[0]) + selected_nodes.append(smallest_leaves[0]) if not selected_nodes and myblocker_uninstalls: # An Uninstall task needs to be executed in order to diff --git a/lib/portage/tests/resolver/test_alternatives_gzip.py b/lib/portage/tests/resolver/test_alternatives_gzip.py index 602ed1756f..e763e84640 100644 --- a/lib/portage/tests/resolver/test_alternatives_gzip.py +++ b/lib/portage/tests/resolver/test_alternatives_gzip.py @@ -1,8 +1,6 @@ # Copyright 2023 Gentoo Authors # Distributed under the terms of the GNU General Public License v2 -import pytest - from portage.tests import TestCase from portage.tests.resolver.ResolverPlayground import ( ResolverPlayground, @@ -10,7 +8,6 @@ from portage.tests.resolver.ResolverPlayground import ( ) [email protected]() class AlternativesGzipTestCase(TestCase): def testAlternativesGzip(self): """ @@ -19,8 +16,9 @@ class AlternativesGzipTestCase(TestCase): find_smallest_cycle selects a large cycle and the topological sort produces poor results when leaf_nodes returns app-alternatives/gzip as part of a large group of nodes. - This problem might be solved by implementing a finer-grained - ignore_priority for leaf_nodes calls. + This problem was solved by changing the topological sort to + increase ignore_priority in order to select a smaller number + of leaf nodes at a time. """ ebuilds = { "app-alternatives/gzip-1": { diff --git a/lib/portage/tests/resolver/test_merge_order.py b/lib/portage/tests/resolver/test_merge_order.py index 940eb3bbbe..e6d45c847b 100644 --- a/lib/portage/tests/resolver/test_merge_order.py +++ b/lib/portage/tests/resolver/test_merge_order.py @@ -1,4 +1,4 @@ -# Copyright 2011-2020 Gentoo Authors +# Copyright 2011-2023 Gentoo Authors # Distributed under the terms of the GNU General Public License v2 from portage.tests import TestCase @@ -382,10 +382,12 @@ class MergeOrderTestCase(TestCase): ambiguous_merge_order=True, # The following merge order assertion reflects optimal order for # a circular relationship which is DEPEND in one direction and - # RDEPEND in the other. - merge_order_assertions=( - ("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"), - ), + # RDEPEND in the other. However, it is not respected because + # it would result in a temporarily broken RDEPEND, so we instead + # rely on satisfied installed build-time dependencies. + # merge_order_assertions=( + # ("app-misc/circ-buildtime-a-1", "app-misc/circ-buildtime-c-1"), + # ), mergelist=[ ( "app-misc/circ-buildtime-b-1", @@ -691,8 +693,8 @@ class MergeOrderTestCase(TestCase): "app-misc/circ-post-runtime-b-1", "app-misc/some-app-b-1", "app-misc/circ-runtime-a-1", - "app-misc/circ-runtime-b-1", "app-misc/circ-runtime-c-1", + "app-misc/circ-runtime-b-1", "app-misc/some-app-a-1", "app-misc/blocker-buildtime-unbuilt-a-1", "[uninstall]app-misc/installed-blocker-a-1", @@ -701,13 +703,13 @@ class MergeOrderTestCase(TestCase): "app-misc/circ-direct-b-1", "x11-base/xorg-server-1.14.1", "media-libs/mesa-9.1.3", - "app-misc/circ-buildtime-a-1", - "app-misc/circ-buildtime-b-1", "app-misc/circ-buildtime-c-1", + "app-misc/circ-buildtime-b-1", + "app-misc/circ-buildtime-a-1", "app-misc/some-app-c-1", "app-misc/circ-satisfied-a-1", - "app-misc/circ-satisfied-b-1", "app-misc/circ-satisfied-c-1", + "app-misc/circ-satisfied-b-1", ], ), ) diff --git a/lib/portage/tests/resolver/test_rebuild_ghostscript.py b/lib/portage/tests/resolver/test_rebuild_ghostscript.py index 88dc2b5fc3..8ee3349d6f 100644 --- a/lib/portage/tests/resolver/test_rebuild_ghostscript.py +++ b/lib/portage/tests/resolver/test_rebuild_ghostscript.py @@ -138,8 +138,8 @@ class RebuildGhostscriptTestCase(TestCase): "sys-apps/dbus-1.15.6", "x11-libs/gtk+-3.24.38", "app-text/ghostscript-gpl-10.01.2", - "net-print/cups-2.4.6", "net-dns/avahi-0.8-r7", + "net-print/cups-2.4.6", "app-text/libspectre-0.2.12", "x11-libs/goffice-0.10.55", ],
