# leaves.py
# DNF plugin for listing installed packages not required by any other
# installed package.
#
# Copyright (C) 2015 Emil Renner Berthing
#
# This copyrighted material is made available to anyone wishing to use,
# modify, copy, or redistribute it subject to the terms and conditions of
# the GNU General Public License v.2, or (at your option) any later version.
# This program is distributed in the hope that it will be useful, but WITHOUT
# ANY WARRANTY expressed or implied, including the implied warranties of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
# Public License for more details.
#
import dnf
import dnf.sack
import dnf.cli
from dnfpluginscore import _
class Leaves(dnf.Plugin):
name = 'leaves'
def __init__(self, base, cli):
super(Leaves, self).__init__(base, cli)
if cli:
cli.register_command(LeavesCommand)
class LeavesCommand(dnf.cli.Command):
aliases = ('leaves',)
summary = _('List installed packages not required by any other package')
def buildgraph(self):
"""
Load the list of installed packages and their dependencies using
hawkey, and build the dependency graph and the graph of reverse
dependencies.
"""
query = dnf.sack._rpmdb_sack(self.base).query().apply()
pkgmap = dict()
packages = []
depends = []
rdepends = []
deps = set()
providers = set()
for i, pkg in enumerate(query):
pkgmap[pkg] = i
packages.append(pkg)
rdepends.append([])
for i, pkg in enumerate(packages):
for req in pkg.requires:
sreq = str(req)
if sreq.startswith('rpmlib(') or sreq == 'solvable:prereqmarker':
continue
for dpkg in query.filter(provides=req):
providers.add(pkgmap[dpkg])
if len(providers) == 1 and i not in providers:
deps.update(providers)
providers.clear()
deplist = list(deps)
deps.clear()
depends.append(deplist)
for j in deplist:
rdepends[j].append(i)
return (packages, depends, rdepends)
def kosaraju(self, graph, rgraph):
"""
Run Kosaraju's algorithm to find strongly connected components
in the graph, and return the list of nodes in the components
without any incoming edges.
"""
N = len(graph)
rstack = []
stack = []
idx = []
tag = [False] * N
# do depth-first searches in the graph
# and push nodes to rstack "on the way up"
# until all nodes have been pushed.
# tag nodes so we don't visit them more than once
for u in range(N):
if tag[u]:
continue
stack.append(u)
idx.append(len(graph[u]))
tag[u] = True
while stack:
u = stack[-1]
i = idx[-1]
if i:
i -= 1
idx[-1] = i
v = graph[u][i]
if not tag[v]:
stack.append(v)
idx.append(len(graph[v]))
tag[v] = True
else:
stack.pop()
idx.pop()
rstack.append(u)
# now searches beginning at nodes popped from
# rstack in the graph with all edges reversed
# will give us the strongly connected components.
# the incoming edges to each component is the
# union of incoming edges to each node in the
# component minus the incoming edges from
# component nodes themselves.
# now all nodes are tagged, so this time let's
# remove the tags as we visit each node.
leaves = []
scc = []
sccredges = set()
while rstack:
v = rstack.pop()
if not tag[v]:
continue
stack.append(v)
tag[v] = False
while stack:
v = stack.pop()
redges = rgraph[v]
scc.append(v)
sccredges.update(redges)
for u in redges:
if tag[u]:
stack.append(u)
tag[u] = False
sccredges.difference_update(scc)
if not sccredges:
leaves.extend(scc)
del scc[:]
sccredges.clear()
return leaves
def findleaves(self):
(packages, depends, rdepends) = self.buildgraph()
return [packages[i] for i in self.kosaraju(depends, rdepends)]
def run(self):
for pkg in sorted(map(str, self.findleaves())):
print(pkg)