# 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)