Revert "find_smallest_cycle: Optimize to traverse fewer nodes"

This reverts commit 49e01d041c74680a81860b819daff812d83df02f
in order to fix bug 922629. Later we can try to optimize it
again but without breaking testTarMergeOrder.

Bug: https://bugs.gentoo.org/922629
Signed-off-by: Zac Medico <zmedico@gentoo.org>

4 files changed, 9 insertions, 40 deletions

diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index 6b91d5c42..3adc04bcf 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -9313,14 +9313,7 @@ class depgraph:
 
                 asap_nodes.extend(libc_pkgs)
 
-        def gather_deps(
-            ignore_priority,
-            mergeable_nodes,
-            selected_nodes,
-            node,
-            smallest_cycle=None,
-            traversed_nodes=None,
-        ):
+        def gather_deps(ignore_priority, mergeable_nodes, selected_nodes, node):
             """
             Recursively gather a group of nodes that RDEPEND on
             eachother. This ensures that they are merged as a group
@@ -9340,24 +9333,10 @@ class depgraph:
                 # RDEPENDs installed first, but ignore uninstalls
                 # (these occur when new portage blocks an older package version).
                 return False
-            if traversed_nodes is not None:
-                if node in traversed_nodes:
-                    # Identical to a previously traversed cycle.
-                    return False
-                traversed_nodes.add(node)
             selected_nodes.add(node)
-            if smallest_cycle is not None and len(selected_nodes) >= len(
-                smallest_cycle
-            ):
-                return False
             for child in mygraph.child_nodes(node, ignore_priority=ignore_priority):
                 if not gather_deps(
-                    ignore_priority,
-                    mergeable_nodes,
-                    selected_nodes,
-                    child,
-                    smallest_cycle=smallest_cycle,
-                    traversed_nodes=traversed_nodes,
+                    ignore_priority, mergeable_nodes, selected_nodes, child
                 ):
                     return False
             return True
@@ -9515,21 +9494,12 @@ class depgraph:
                             local_priority_range.MEDIUM_SOFT + 1,
                         )
                     ):
-                        # Traversed nodes for current priority
-                        traversed_nodes = set()
                         for node in nodes:
                             if not mygraph.parent_nodes(node):
                                 continue
-                            if node in traversed_nodes:
-                                continue
                             selected_nodes = set()
                             if gather_deps(
-                                priority,
-                                mergeable_nodes,
-                                selected_nodes,
-                                node,
-                                smallest_cycle=smallest_cycle,
-                                traversed_nodes=traversed_nodes,
+                                priority, mergeable_nodes, selected_nodes, node
                             ):
                                 if smallest_cycle is None or len(selected_nodes) < len(
                                     smallest_cycle
diff --git a/lib/portage/tests/resolver/test_rebuild_ghostscript.py b/lib/portage/tests/resolver/test_rebuild_ghostscript.py
index 8ee3349d6..dad6a2132 100644
--- a/lib/portage/tests/resolver/test_rebuild_ghostscript.py
+++ b/lib/portage/tests/resolver/test_rebuild_ghostscript.py
@@ -137,9 +137,9 @@ class RebuildGhostscriptTestCase(TestCase):
                 mergelist=[
                     "sys-apps/dbus-1.15.6",
                     "x11-libs/gtk+-3.24.38",
-                    "app-text/ghostscript-gpl-10.01.2",
                     "net-dns/avahi-0.8-r7",
                     "net-print/cups-2.4.6",
+                    "app-text/ghostscript-gpl-10.01.2",
                     "app-text/libspectre-0.2.12",
                     "x11-libs/goffice-0.10.55",
                 ],
diff --git a/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py b/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
index ed329aa09..a695b2519 100644
--- a/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
+++ b/lib/portage/tests/resolver/test_runtime_cycle_merge_order.py
@@ -56,11 +56,8 @@ class RuntimeCycleMergeOrderTestCase(TestCase):
                     ("app-misc/leaf-b-1", "app-misc/leaf-d-1", "app-misc/leaf-e-1"),
                     ("app-misc/branch-d-1", "app-misc/branch-e-1"),
                     "app-misc/runtime-c-1",
-                    (
-                        "app-misc/branch-b-1",
-                        "app-misc/runtime-cycle-c-1",
-                        "app-misc/branch-c-1",
-                    ),
+                    ("app-misc/runtime-cycle-c-1", "app-misc/branch-c-1"),
+                    "app-misc/branch-b-1",
                     ("app-misc/runtime-cycle-b-1", "app-misc/plugin-b-1"),
                     "app-misc/plugins-consumer-1",
                 ],
diff --git a/lib/portage/tests/resolver/test_tar_merge_order.py b/lib/portage/tests/resolver/test_tar_merge_order.py
index 7e1a18bc2..4bd9b4df4 100644
--- a/lib/portage/tests/resolver/test_tar_merge_order.py
+++ b/lib/portage/tests/resolver/test_tar_merge_order.py
@@ -12,7 +12,6 @@ from portage.tests.resolver.ResolverPlayground import (
 
 
 class TarMergeOrderTestCase(TestCase):
-    @pytest.mark.xfail(reason="bug #922629 isn't yet fixed")
     def testTarMergeOrder(self):
         """
         Test for bug #922629 where binary app-arch/tar[acl] was merged
@@ -21,6 +20,9 @@ class TarMergeOrderTestCase(TestCase):
 
         It poorly interacted with @system containing app-alternatives/tar
         as a circular dependency on app-arch/tar.
+
+        Bisect found that commit 49e01d041c74680a81860b819daff812d83df02f
+        triggered the issue.
         """
 
         ebuilds = {