Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Find top-level packages of the dependency graph for debian packages
#!/usr/bin/python3
import argparse, sys
import apt
import networkx as nx
parser = argparse.ArgumentParser(
description = "Find top-level packages of the dependency graph"
)
parser.add_argument(
"names", metavar = "package", nargs = "*",
help = "package names to use (default: all installed packages)"
)
parser.add_argument(
"--root-dir", metavar = "dir",
help = "act as if chrooted in the specified directory"
)
parser.add_argument(
"--follow-unspecified-packages", action = "store_true",
help = "follow dependencies of packages not part of the initial input"
)
parser.add_argument(
"--no-use-recommends", action = "store_true",
help = "don't use recommended packages for the dependency graph"
)
parser.add_argument(
"--show-missing-recommends", action = "store_true",
help = "list missing recommended packages suffixed with a dash"
)
args = parser.parse_args()
inputPackages = set()
cache = apt.Cache(rootdir = args.root_dir)
providedPackages = dict()
def nameToPackage(name):
if name not in cache:
if name in providedPackages:
return providedPackages[name]
else:
return None
package = cache[name]
if package.installed:
return package.installed
else:
return max(package.versions)
def resolveDependencyBranch(dependency, arch):
# Pick every possible or branch for simplicity if the dependency isn't one
# of the input packages, which means we might not find all the root nodes,
# but in practice usually isn't a problem since a branched dependency is
# usually of libraries
baseDependencies = set()
for baseDependency in dependency.or_dependencies:
package = nameToPackage(baseDependency.name + ":" + arch)
if not package:
continue
if package in inputPackages:
return {(package, type)}
baseDependencies.add((package, baseDependency.rawtype))
return baseDependencies
def outputPackageList(packages):
if len(packages) > 1:
return "(" + " ".join(packages) + ")"
return packages[0]
# Find the packages
fail = False
for name in args.names:
package = nameToPackage(name)
if not package:
print("Could not find in package cache:", name, file = sys.stderr)
fail = True
continue
inputPackages.add(package)
for name in package.provides:
providedPackages[name + ":" + package.package.architecture()] = package
if fail:
sys.exit(1)
# Use all installed packages if no packages were specified
if len(inputPackages) == 0:
for package in cache:
package = package.installed
if not package:
continue
inputPackages.add(package)
for name in package.provides:
providedPackages[name + ":" + package.package.architecture()] = package
# Build our dependency graph
packagesDG = nx.MultiDiGraph()
visitStack = list(inputPackages)
visitedPackages = set()
while len(visitStack) > 0:
package = visitStack.pop()
fullname = package.package.fullname
packagesDG.add_node(fullname)
visitedPackages.add(fullname)
dependencies = package.dependencies
if not args.no_use_recommends:
dependencies.extend(package.recommends)
arch = package.package.architecture()
for dependency in dependencies:
for dependencyPackage, type in resolveDependencyBranch(dependency, arch):
dependencyFullname = dependencyPackage.package.fullname
packagesDG.add_edge(fullname, dependencyFullname, type = type)
if args.follow_unspecified_packages and dependencyFullname not in visitedPackages:
visitStack.append(dependencyPackage)
# Remove any cycles
nodes = list(nx.strongly_connected_components(packagesDG))
packagesDAG = nx.condensation(packagesDG, scc = nodes)
# Find the nodes that have no in-edges - these are the top-level nodes
topLevelNodes = set()
for node in packagesDAG:
if len(list(packagesDAG.predecessors(node))) == 0:
topLevelNodes.add(node)
# Convert the nodes back into package names
topLevelPackages = set()
for node in topLevelNodes:
packages = inputPackages & set(map(nameToPackage, nodes[node]))
packages = sorted(packages, key = lambda p: p.package.name)
packageNames = [package.package.name for package in packages]
# The results should always be one of the input packages
assert(len(packages) > 0)
topLevelPackages.add(packages[0])
if packages[0].priority not in {"required", "important"}:
print(packageNames[0])
if len(packages) > 1:
print("{} consists of {}".format(packageNames[0], outputPackageList(packageNames)), file = sys.stderr)
# Find missing recommend packages if requested
if args.show_missing_recommends:
recommendedVias = dict()
for edge in packagesDG.edges(data = True):
if edge[2]["type"] != "Recommends":
continue
package = nameToPackage(edge[1])
if package and package not in inputPackages:
recommendedVias.setdefault(edge[1], set()).add(edge[0])
for edge in packagesDG.edges(data = True):
if edge[2]["type"] != "Recommends":
recommendedVias.pop(edge[1], None)
for name, via in recommendedVias.items():
by = topLevelPackages & set(map(nameToPackage, nx.ancestors(packagesDG, name)))
via = set(map(nameToPackage, via)) - set(by)
name = nameToPackage(name).package.name
via = sorted(package.package.name for package in via)
by = sorted(package.package.name for package in by)
print("{}-".format(name))
print(
"{}- is recommended by {}{}".format(
name,
outputPackageList(by),
" via {}".format(outputPackageList(sorted(via))) if len(via) > 0 else ""
),
file = sys.stderr
)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.