proj/portage:master commit in: lib/portage/dbapi/, lib/portage/tests/dbapi/

commit:     a8e69fdd4cc3a2c739873a5df65711d6b2fdf554
Author:     Matt Turner <mattst88 <AT> gentoo <DOT> org>
AuthorDate: Sun Aug  2 22:30:22 2026 +0000
Commit:     Matt Turner <mattst88 <AT> gentoo <DOT> org>
CommitDate: Wed Aug  5 18:59:29 2026 +0000
URL:        https://gitweb.gentoo.org/proj/portage.git/commit/?id=a8e69fdd

vartree: remove preserved libs that only consume each other

_find_unneeded_preserved_nodes() peels the consumer graph from its
roots, removing preserved libraries that have no consumers left and
repeating until no root node is a preserved library. A group of
preserved libraries which consume each other in a cycle has no root
node, so the peel stops on the first iteration and nothing in the cycle
is ever removed, even though nothing outside of the cycle consumes it.
The libraries stay in the preserved libs registry forever, along with
any libraries consumed only by the cycle.

Replace the peel with a least fixed point over the same graph: a
preserved library is needed if it has a consumer which is not itself a
preserved library, or if it has a consumer which is a preserved library
that is needed. Everything else is unneeded. For an acyclic graph this
is equivalent to the peel, and a cycle which nothing outside of it
consumes is never seeded, so it is correctly reported as unneeded.

Bug: https://bugs.gentoo.org/652382
Signed-off-by: Matt Turner <mattst88 <AT> gentoo.org>

 lib/portage/dbapi/vartree.py                   | 40 +++++++++++------
 lib/portage/tests/dbapi/test_preserved_libs.py | 60 ++++++++++++++++++++++++++
 2 files changed, 86 insertions(+), 14 deletions(-)

diff --git a/lib/portage/dbapi/vartree.py b/lib/portage/dbapi/vartree.py
index e15a258aa..34f79e99a 100644
--- a/lib/portage/dbapi/vartree.py
+++ b/lib/portage/dbapi/vartree.py
@@ -1734,13 +1734,14 @@ def _find_unneeded_preserved_nodes(lib_graph, preserved_nodes):
     consumers, find the preserved libraries which are not needed by
     anything.
 
-    Repeatedly take the preserved libraries which have no consumers left
-    and drop them from the graph, which may in turn leave other preserved
-    libraries without consumers.
+    A preserved library is needed if it has a consumer which is not itself
+    a preserved library, or if it has a consumer which is a preserved
+    library that is needed. Anything else is unneeded, including a group of
+    preserved libraries which consume each other in a cycle but which
+    nothing outside of the group consumes (bug 652382).
 
     @param lib_graph: graph in which an edge from a consumer (parent) to a
-            library (child) means that the consumer links against the library.
-            It is modified in place.
+            library (child) means that the consumer links against the library
     @type lib_graph: digraph
     @param preserved_nodes: the subset of nodes in lib_graph which are
             preserved libraries
@@ -1748,16 +1749,27 @@ def _find_unneeded_preserved_nodes(lib_graph, preserved_nodes):
     @rtype: set
     @return: the subset of preserved_nodes which is not needed
     """
-    unneeded_nodes = set()
-
-    while lib_graph:
-        root_nodes = preserved_nodes.intersection(lib_graph.root_nodes())
-        if not root_nodes:
-            break
-        lib_graph.difference_update(root_nodes)
-        unneeded_nodes.update(root_nodes)
+    needed_nodes = set()
+    stack = []
+
+    for preserved_node in preserved_nodes:
+        for consumer_node in lib_graph.parent_nodes(preserved_node):
+            if consumer_node not in preserved_nodes:
+                needed_nodes.add(preserved_node)
+                stack.append(preserved_node)
+                break
 
-    return unneeded_nodes
+    # Anything consumed by a needed preserved library is needed as well.
+    # This is what keeps a cycle alive when something outside of it still
+    # consumes part of it.
+    while stack:
+        node = stack.pop()
+        for child_node in lib_graph.child_nodes(node):
+            if child_node in preserved_nodes and child_node not in needed_nodes:
+                needed_nodes.add(child_node)
+                stack.append(child_node)
+
+    return preserved_nodes.difference(needed_nodes)
 
 
 class dblink:

diff --git a/lib/portage/tests/dbapi/test_preserved_libs.py b/lib/portage/tests/dbapi/test_preserved_libs.py
index 6cd881e31..49165a716 100644
--- a/lib/portage/tests/dbapi/test_preserved_libs.py
+++ b/lib/portage/tests/dbapi/test_preserved_libs.py
@@ -46,3 +46,63 @@ class FindUnneededPreservedNodesTestCase(TestCase):
             [("baz", "libbar"), ("libbar", "libfoo")], ["libfoo", "libbar"]
         )
         self.assertEqual(_find_unneeded_preserved_nodes(graph, preserved), set())
+
+    def testCycle(self):
+        # bug 652382: preserved libs which only consume each other must
+        # not keep each other alive. Cycles are not limited to two libs.
+        graph, preserved = self._build(
+            [("libfoo", "libbar"), ("libbar", "libbaz"), ("libbaz", "libfoo")],
+            ["libfoo", "libbar", "libbaz"],
+        )
+        self.assertEqual(
+            _find_unneeded_preserved_nodes(graph, preserved),
+            {"libfoo", "libbar", "libbaz"},
+        )
+
+    def testCycleWithInstalledConsumer(self):
+        # A cycle is needed if anything outside of it still consumes part
+        # of it.
+        graph, preserved = self._build(
+            [
+                ("libfoo", "libbar"),
+                ("libbar", "libbaz"),
+                ("libbaz", "libfoo"),
+                ("app", "libbar"),
+            ],
+            ["libfoo", "libbar", "libbaz"],
+        )
+        self.assertEqual(_find_unneeded_preserved_nodes(graph, preserved), set())
+
+    def testCycleFromBugReport(self):
+        # The graphite2 / freetype / harfbuzz / libpng case, in which
+        # freetype and harfbuzz consume each other, and graphite2 and
+        # libpng are consumed by harfbuzz and freetype respectively.
+        graph, preserved = self._build(
+            [
+                ("libharfbuzz", "libgraphite2"),
+                ("libharfbuzz", "libfreetype"),
+                ("libfreetype", "libharfbuzz"),
+                ("libfreetype", "libpng16"),
+            ],
+            ["libgraphite2", "libfreetype", "libharfbuzz", "libpng16"],
+        )
+        self.assertEqual(
+            _find_unneeded_preserved_nodes(graph, preserved),
+            {"libgraphite2", "libfreetype", "libharfbuzz", "libpng16"},
+        )
+
+    def testUnneededCycleAndNeededLib(self):
+        # An unneeded cycle is removed even though an unrelated preserved
+        # lib is still needed.
+        graph, preserved = self._build(
+            [
+                ("libfoo", "libbar"),
+                ("libbar", "libfoo"),
+                ("baz", "libqux"),
+            ],
+            ["libfoo", "libbar", "libqux"],
+        )
+        self.assertEqual(
+            _find_unneeded_preserved_nodes(graph, preserved),
+            {"libfoo", "libbar"},
+        )