depclean: Strengthen IDEPEND in unmerge order

Increase priority of IDEPEND so that it is stronger
than RDEPEND in unmerge order calculations. This
causes IDEPEND to be unmerged afterwards when
packages are involved in RDEPEND cycles.

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

5 files changed, 92 insertions, 18 deletions

diff --git a/lib/_emerge/AbstractDepPriority.py b/lib/_emerge/AbstractDepPriority.py
index a9616c109..3af262cd7 100644
--- a/lib/_emerge/AbstractDepPriority.py
+++ b/lib/_emerge/AbstractDepPriority.py
@@ -1,4 +1,4 @@
-# Copyright 1999-2013 Gentoo Foundation
+# Copyright 1999-2023 Gentoo Authors
 # Distributed under the terms of the GNU General Public License v2
 
 import copy
@@ -9,6 +9,7 @@ class AbstractDepPriority(SlotObject):
     __slots__ = (
         "buildtime",
         "buildtime_slot_op",
+        "installtime",
         "runtime",
         "runtime_post",
         "runtime_slot_op",
diff --git a/lib/_emerge/UnmergeDepPriority.py b/lib/_emerge/UnmergeDepPriority.py
index d818bad1b..b14f8b84e 100644
--- a/lib/_emerge/UnmergeDepPriority.py
+++ b/lib/_emerge/UnmergeDepPriority.py
@@ -12,18 +12,19 @@ class UnmergeDepPriority(AbstractDepPriority):
         "satisfied",
     )
     """
-	Combination of properties           Priority  Category
-
-	runtime_slot_op                        0       HARD
-	runtime                               -1       HARD
-	runtime_post                          -2       HARD
-	buildtime                             -3       SOFT
-	(none of the above)                   -3       SOFT
-	"""
+    Combination of properties           Priority  Category
+
+    installtime                            0       HARD
+    runtime_slot_op                       -1       HARD
+    runtime                               -2       HARD
+    runtime_post                          -3       HARD
+    buildtime                             -4       SOFT
+    (none of the above)                   -4       SOFT
+    """
 
     MAX = 0
-    SOFT = -3
-    MIN = -3
+    SOFT = -4
+    MIN = -4
 
     def __init__(self, **kwargs):
         AbstractDepPriority.__init__(self, **kwargs)
@@ -31,19 +32,23 @@ class UnmergeDepPriority(AbstractDepPriority):
             self.optional = True
 
     def __int__(self):
-        if self.runtime_slot_op:
+        if self.installtime:
             return 0
-        if self.runtime:
+        if self.runtime_slot_op:
             return -1
-        if self.runtime_post:
+        if self.runtime:
             return -2
-        if self.buildtime:
+        if self.runtime_post:
             return -3
-        return -3
+        if self.buildtime:
+            return -4
+        return -4
 
     def __str__(self):
         if self.ignored:
             return "ignored"
+        if self.installtime:
+            return "install time"
         if self.runtime_slot_op:
             return "hard slot op"
         myvalue = self.__int__()
diff --git a/lib/_emerge/actions.py b/lib/_emerge/actions.py
index 13bb75931..20f3978f7 100644
--- a/lib/_emerge/actions.py
+++ b/lib/_emerge/actions.py
@@ -1568,11 +1568,12 @@ def _calc_depclean(settings, trees, ldpath_mtimes, myopts, action, args_set, spi
         graph = digraph()
         del cleanlist[:]
 
+        installtime = UnmergeDepPriority(installtime=True, runtime=True)
         runtime = UnmergeDepPriority(runtime=True)
         runtime_post = UnmergeDepPriority(runtime_post=True)
         buildtime = UnmergeDepPriority(buildtime=True)
         priority_map = {
-            "IDEPEND": runtime,
+            "IDEPEND": installtime,
             "RDEPEND": runtime,
             "PDEPEND": runtime_post,
             "BDEPEND": buildtime,
@@ -1683,6 +1684,8 @@ def _calc_depclean(settings, trees, ldpath_mtimes, myopts, action, args_set, spi
                         break
                 if not nodes:
                     raise AssertionError("no root nodes")
+                # Sort nodes for deterministic results.
+                nodes.sort(reverse=True)
                 if ignore_priority is not None:
                     # Some deps have been dropped due to circular dependencies,
                     # so only pop one node in order to minimize the number that
diff --git a/lib/_emerge/depgraph.py b/lib/_emerge/depgraph.py
index e92c6962a..6ee4471bb 100644
--- a/lib/_emerge/depgraph.py
+++ b/lib/_emerge/depgraph.py
@@ -4007,7 +4007,9 @@ class depgraph:
             (
                 self._frozen_config._running_root.root,
                 edepend["IDEPEND"],
-                self._priority(cross=self._cross(pkg.root), runtime=True),
+                self._priority(
+                    cross=self._cross(pkg.root), installtime=True, runtime=True
+                ),
             ),
             (
                 myroot,
diff --git a/lib/portage/tests/resolver/test_depclean_order.py b/lib/portage/tests/resolver/test_depclean_order.py
index 23b5e755c..36d60d44e 100644
--- a/lib/portage/tests/resolver/test_depclean_order.py
+++ b/lib/portage/tests/resolver/test_depclean_order.py
@@ -109,3 +109,66 @@ class SimpleDepcleanTestCase(TestCase):
                 self.assertEqual(test_case.test_success, True, test_case.fail_msg)
         finally:
             playground.cleanup()
+
+    def testCircularDepclean(self):
+        """
+        Test for bug 916135, where an indirect circular dependency caused
+        the unmerge order to fail to account for IDEPEND.
+        """
+
+        ebuilds = {
+            "dev-util/A-1": {},
+            "dev-libs/B-1": {
+                "EAPI": "8",
+                "SLOT": "1",
+                "IDEPEND": "dev-util/A",
+                "RDEPEND": "dev-libs/B:=",
+            },
+            "dev-libs/B-2": {
+                "EAPI": "8",
+                "SLOT": "2",
+                "IDEPEND": "dev-util/A",
+                "RDEPEND": "dev-libs/B:=",
+            },
+            "dev-libs/C-1": {},
+        }
+
+        installed = {
+            "dev-util/A-1": {},
+            "dev-libs/B-1": {
+                "EAPI": "8",
+                "SLOT": "1",
+                "IDEPEND": "dev-util/A",
+                "RDEPEND": "dev-libs/B:2/2=",
+            },
+            "dev-libs/B-2": {
+                "EAPI": "8",
+                "SLOT": "2",
+                "IDEPEND": "dev-util/A",
+                "RDEPEND": "dev-libs/B:1/1=",
+            },
+            "dev-libs/C-1": {},
+        }
+
+        world = ("dev-libs/C",)
+
+        test_cases = (
+            # Remove dev-libs/B first because it IDEPENDs on dev-util/A
+            ResolverPlaygroundTestCase(
+                [],
+                options={"--depclean": True},
+                success=True,
+                ordered=True,
+                cleanlist=["dev-libs/B-2", "dev-libs/B-1", "dev-util/A-1"],
+            ),
+        )
+
+        playground = ResolverPlayground(
+            ebuilds=ebuilds, installed=installed, world=world
+        )
+        try:
+            for test_case in test_cases:
+                playground.run_TestCase(test_case)
+                self.assertEqual(test_case.test_success, True, test_case.fail_msg)
+        finally:
+            playground.cleanup()