commit: 31832c7faf5bffde25a596ce62ecf84c478fac45
Author: Zac Medico <zmedico <AT> gentoo <DOT> org>
AuthorDate: Wed Nov 29 16:14:27 2023 +0000
Commit: Zac Medico <zmedico <AT> gentoo <DOT> org>
CommitDate: Wed Nov 29 16:33:18 2023 +0000
URL: https://gitweb.gentoo.org/proj/portage.git/commit/?id=31832c7f
Optimize runtime cycle ignore_priority leaf selection loop for topological sort
Since increasing ignore_priority can only lead to a larger
selection of leaf nodes, there is no need to increase ignore_priority
to search for smaller groups of leaf nodes.
It was the "only harvest one node at a time" part of commit
3487594cd8f4 that caused the test case to succeed.
Fixes: 3487594cd8f4 ("Increase ignore_priority during topological sort for
runtime cycle")
Bug: https://bugs.gentoo.org/917259
Signed-off-by: Zac Medico <zmedico <AT> gentoo.org>
lib/_emerge/depgraph.py | 31 ++++++++++----------------
lib/portage/tests/resolver/test_merge_order.py | 8 +++----
2 files changed, 16 insertions(+), 23 deletions(-)
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 9f041f83a9..15c3e3ca7b 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -9478,36 +9478,29 @@ 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
+ leaves = None
for ignore_priority in ignore_priorities:
leaves = cycle_digraph.leaf_nodes(
ignore_priority=ignore_priority
)
- if leaves and (
- smallest_leaves is None
- or len(leaves) < len(smallest_leaves)
- ):
- smallest_leaves = leaves
- if len(smallest_leaves) == 1:
- break
+ if leaves:
+ # Select leaves with minimum ignore_priority,
+ # in order to ingore as few deps as possible.
+ break
- if smallest_leaves is None:
- smallest_leaves = [cycle_digraph.order[-1]]
+ if leaves is None:
+ leaves = [cycle_digraph.order[-1]]
# Prefer installed leaves, in order to avoid
- # merging something too early.
- installed_leaves = [pkg for pkg in smallest_leaves if
pkg.installed]
+ # merging something too early as in bug 917259.
+ installed_leaves = [pkg for pkg in leaves if pkg.installed]
if installed_leaves:
- smallest_leaves = installed_leaves
+ leaves = installed_leaves
# 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])
+ cycle_digraph.remove(leaves[0])
+ selected_nodes.append(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_merge_order.py
b/lib/portage/tests/resolver/test_merge_order.py
index e6d45c847b..a6c236a207 100644
--- a/lib/portage/tests/resolver/test_merge_order.py
+++ b/lib/portage/tests/resolver/test_merge_order.py
@@ -385,9 +385,9 @@ class MergeOrderTestCase(TestCase):
# 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"),
- # ),
+ merge_order_assertions=(
+ ("app-misc/circ-buildtime-a-1",
"app-misc/circ-buildtime-c-1"),
+ ),
mergelist=[
(
"app-misc/circ-buildtime-b-1",
@@ -703,9 +703,9 @@ 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-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-c-1",
