358 lines
13 KiB
Plaintext
358 lines
13 KiB
Plaintext
|
#!/usr/bin/env python3
|
||
|
|
|
||
|
|
# Usage (the graphviz package must be installed in your distribution)
|
||
|
|
# ./support/scripts/graph-depends [-p package-name] > test.dot
|
||
|
|
# dot -Tpdf test.dot -o test.pdf
|
||
|
|
#
|
||
|
|
# With no arguments, graph-depends will draw a complete graph of
|
||
|
|
# dependencies for the current configuration.
|
||
|
|
# If '-p <package-name>' is specified, graph-depends will draw a graph
|
||
|
|
# of dependencies for the given package name.
|
||
|
|
# If '-d <depth>' is specified, graph-depends will limit the depth of
|
||
|
|
# the dependency graph to 'depth' levels.
|
||
|
|
#
|
||
|
|
# Limitations
|
||
|
|
#
|
||
|
|
# * Some packages have dependencies that depend on the Buildroot
|
||
|
|
# configuration. For example, many packages have a dependency on
|
||
|
|
# openssl if openssl has been enabled. This tool will graph the
|
||
|
|
# dependencies as they are with the current Buildroot
|
||
|
|
# configuration.
|
||
|
|
#
|
||
|
|
# Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
|
||
|
|
# Copyright (C) 2019 Yann E. MORIN <yann.morin.1998@free.fr>
|
||
|
|
|
||
|
|
import logging
|
||
|
|
import sys
|
||
|
|
import argparse
|
||
|
|
from fnmatch import fnmatch
|
||
|
|
|
||
|
|
import brpkgutil
|
||
|
|
|
||
|
|
# Modes of operation:
|
||
|
|
MODE_FULL = 1 # draw full dependency graph for all selected packages
|
||
|
|
MODE_PKG = 2 # draw dependency graph for a given package
|
||
|
|
|
||
|
|
allpkgs = []
|
||
|
|
|
||
|
|
|
||
|
|
# The Graphviz "dot" utility doesn't like dashes in node names. So for
|
||
|
|
# node names, we strip all dashes. Also, nodes can't start with a number,
|
||
|
|
# so we prepend an underscore.
|
||
|
|
def pkg_node_name(pkg):
|
||
|
|
return "_" + pkg.replace("-", "")
|
||
|
|
|
||
|
|
|
||
|
|
# Basic cache for the results of the is_dep() function, in order to
|
||
|
|
# optimize the execution time. The cache is a dict of dict of boolean
|
||
|
|
# values. The key to the primary dict is "pkg", and the key of the
|
||
|
|
# sub-dicts is "pkg2".
|
||
|
|
is_dep_cache = {}
|
||
|
|
|
||
|
|
|
||
|
|
def is_dep_cache_insert(pkg, pkg2, val):
|
||
|
|
try:
|
||
|
|
is_dep_cache[pkg].update({pkg2: val})
|
||
|
|
except KeyError:
|
||
|
|
is_dep_cache[pkg] = {pkg2: val}
|
||
|
|
|
||
|
|
|
||
|
|
# Retrieves from the cache whether pkg2 is a transitive dependency
|
||
|
|
# of pkg.
|
||
|
|
# Note: raises a KeyError exception if the dependency is not known.
|
||
|
|
def is_dep_cache_lookup(pkg, pkg2):
|
||
|
|
return is_dep_cache[pkg][pkg2]
|
||
|
|
|
||
|
|
|
||
|
|
# This function return True if pkg is a dependency (direct or
|
||
|
|
# transitive) of pkg2, dependencies being listed in the deps
|
||
|
|
# dictionary. Returns False otherwise.
|
||
|
|
# This is the un-cached version.
|
||
|
|
def is_dep_uncached(pkg, pkg2, deps):
|
||
|
|
try:
|
||
|
|
for p in deps[pkg2]:
|
||
|
|
if pkg == p:
|
||
|
|
return True
|
||
|
|
if is_dep(pkg, p, deps):
|
||
|
|
return True
|
||
|
|
except KeyError:
|
||
|
|
pass
|
||
|
|
return False
|
||
|
|
|
||
|
|
|
||
|
|
# See is_dep_uncached() above; this is the cached version.
|
||
|
|
def is_dep(pkg, pkg2, deps):
|
||
|
|
try:
|
||
|
|
return is_dep_cache_lookup(pkg, pkg2)
|
||
|
|
except KeyError:
|
||
|
|
val = is_dep_uncached(pkg, pkg2, deps)
|
||
|
|
is_dep_cache_insert(pkg, pkg2, val)
|
||
|
|
return val
|
||
|
|
|
||
|
|
|
||
|
|
# This function eliminates transitive dependencies; for example, given
|
||
|
|
# these dependency chain: A->{B,C} and B->{C}, the A->{C} dependency is
|
||
|
|
# already covered by B->{C}, so C is a transitive dependency of A, via B.
|
||
|
|
# The functions does:
|
||
|
|
# - for each dependency d[i] of the package pkg
|
||
|
|
# - if d[i] is a dependency of any of the other dependencies d[j]
|
||
|
|
# - do not keep d[i]
|
||
|
|
# - otherwise keep d[i]
|
||
|
|
def remove_transitive_deps(pkg, deps):
|
||
|
|
d = deps[pkg]
|
||
|
|
new_d = []
|
||
|
|
for i in range(len(d)):
|
||
|
|
keep_me = True
|
||
|
|
for j in range(len(d)):
|
||
|
|
if j == i:
|
||
|
|
continue
|
||
|
|
if is_dep(d[i], d[j], deps):
|
||
|
|
keep_me = False
|
||
|
|
if keep_me:
|
||
|
|
new_d.append(d[i])
|
||
|
|
return new_d
|
||
|
|
|
||
|
|
|
||
|
|
# List of dependencies that all/many packages have, and that we want
|
||
|
|
# to trim when generating the dependency graph.
|
||
|
|
MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton', 'host-tar', 'host-gzip', 'host-ccache']
|
||
|
|
|
||
|
|
|
||
|
|
# This function removes the dependency on some 'mandatory' package, like the
|
||
|
|
# 'toolchain' package, or the 'skeleton' package
|
||
|
|
def remove_mandatory_deps(pkg, deps):
|
||
|
|
return [p for p in deps[pkg] if p not in MANDATORY_DEPS]
|
||
|
|
|
||
|
|
|
||
|
|
# This function returns all dependencies of pkg that are part of the
|
||
|
|
# mandatory dependencies:
|
||
|
|
def get_mandatory_deps(pkg, deps):
|
||
|
|
return [p for p in deps[pkg] if p in MANDATORY_DEPS]
|
||
|
|
|
||
|
|
|
||
|
|
# This function will check that there is no loop in the dependency chain
|
||
|
|
# As a side effect, it builds up the dependency cache.
|
||
|
|
def check_circular_deps(deps):
|
||
|
|
def recurse(pkg):
|
||
|
|
if pkg not in list(deps.keys()):
|
||
|
|
return
|
||
|
|
if pkg in not_loop:
|
||
|
|
return
|
||
|
|
not_loop.append(pkg)
|
||
|
|
chain.append(pkg)
|
||
|
|
for p in deps[pkg]:
|
||
|
|
if p in chain:
|
||
|
|
logging.warning("\nRecursion detected for : %s" % (p))
|
||
|
|
while True:
|
||
|
|
_p = chain.pop()
|
||
|
|
logging.warning("which is a dependency of: %s" % (_p))
|
||
|
|
if p == _p:
|
||
|
|
sys.exit(1)
|
||
|
|
recurse(p)
|
||
|
|
chain.pop()
|
||
|
|
|
||
|
|
not_loop = []
|
||
|
|
chain = []
|
||
|
|
for pkg in list(deps.keys()):
|
||
|
|
recurse(pkg)
|
||
|
|
|
||
|
|
|
||
|
|
# This functions trims down the dependency list of all packages.
|
||
|
|
# It applies in sequence all the dependency-elimination methods.
|
||
|
|
def remove_extra_deps(deps, rootpkg, transitive, arrow_dir):
|
||
|
|
# For the direct dependencies, find and eliminate mandatory
|
||
|
|
# deps, and add them to the root package. Don't do it for a
|
||
|
|
# reverse graph, because mandatory deps are only direct deps.
|
||
|
|
if arrow_dir == "forward":
|
||
|
|
for pkg in list(deps.keys()):
|
||
|
|
if not pkg == rootpkg:
|
||
|
|
for d in get_mandatory_deps(pkg, deps):
|
||
|
|
if d not in deps[rootpkg]:
|
||
|
|
deps[rootpkg].append(d)
|
||
|
|
deps[pkg] = remove_mandatory_deps(pkg, deps)
|
||
|
|
for pkg in list(deps.keys()):
|
||
|
|
if not transitive or pkg == rootpkg:
|
||
|
|
deps[pkg] = remove_transitive_deps(pkg, deps)
|
||
|
|
return deps
|
||
|
|
|
||
|
|
|
||
|
|
# Print the attributes of a node: label and fill-color
|
||
|
|
def print_attrs(outfile, pkg, pkg_type, pkg_version, depth, colors):
|
||
|
|
name = pkg_node_name(pkg)
|
||
|
|
if pkg == 'all':
|
||
|
|
label = 'ALL'
|
||
|
|
else:
|
||
|
|
label = pkg
|
||
|
|
if depth == 0:
|
||
|
|
color = colors[0]
|
||
|
|
else:
|
||
|
|
if pkg_type == "host":
|
||
|
|
color = colors[2]
|
||
|
|
else:
|
||
|
|
color = colors[1]
|
||
|
|
if pkg_version == "virtual":
|
||
|
|
outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
|
||
|
|
else:
|
||
|
|
outfile.write("%s [label = \"%s\"]\n" % (name, label))
|
||
|
|
outfile.write("%s [color=%s,style=filled]\n" % (name, color))
|
||
|
|
|
||
|
|
|
||
|
|
done_deps = []
|
||
|
|
|
||
|
|
|
||
|
|
# Print the dependency graph of a package
|
||
|
|
def print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
|
||
|
|
arrow_dir, draw_graph, depth, max_depth, pkg, colors):
|
||
|
|
if pkg in done_deps:
|
||
|
|
return
|
||
|
|
done_deps.append(pkg)
|
||
|
|
if draw_graph:
|
||
|
|
print_attrs(outfile, pkg, dict_types[pkg], dict_versions[pkg], depth, colors)
|
||
|
|
elif depth != 0:
|
||
|
|
outfile.write("%s " % pkg)
|
||
|
|
if pkg not in dict_deps:
|
||
|
|
return
|
||
|
|
for p in stop_list:
|
||
|
|
if fnmatch(pkg, p):
|
||
|
|
return
|
||
|
|
if dict_versions[pkg] == "virtual" and "virtual" in stop_list:
|
||
|
|
return
|
||
|
|
if dict_types[pkg] == "host" and "host" in stop_list:
|
||
|
|
return
|
||
|
|
if max_depth == 0 or depth < max_depth:
|
||
|
|
for d in dict_deps[pkg]:
|
||
|
|
if dict_versions[d] == "virtual" and "virtual" in exclude_list:
|
||
|
|
continue
|
||
|
|
if dict_types[d] == "host" and "host" in exclude_list:
|
||
|
|
continue
|
||
|
|
add = True
|
||
|
|
for p in exclude_list:
|
||
|
|
if fnmatch(d, p):
|
||
|
|
add = False
|
||
|
|
break
|
||
|
|
if add:
|
||
|
|
if draw_graph:
|
||
|
|
outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir))
|
||
|
|
print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
|
||
|
|
arrow_dir, draw_graph, depth + 1, max_depth, d, colors)
|
||
|
|
|
||
|
|
|
||
|
|
def parse_args():
|
||
|
|
parser = argparse.ArgumentParser(description="Graph packages dependencies")
|
||
|
|
parser.add_argument("--check-only", "-C", dest="check_only", action="store_true", default=False,
|
||
|
|
help="Only do the dependency checks (circular deps...)")
|
||
|
|
parser.add_argument("--outfile", "-o", metavar="OUT_FILE", dest="outfile",
|
||
|
|
help="File in which to generate the dot representation")
|
||
|
|
parser.add_argument("--package", '-p', metavar="PACKAGE",
|
||
|
|
help="Graph the dependencies of PACKAGE")
|
||
|
|
parser.add_argument("--depth", '-d', metavar="DEPTH", dest="depth", type=int, default=0,
|
||
|
|
help="Limit the dependency graph to DEPTH levels; 0 means no limit.")
|
||
|
|
parser.add_argument("--stop-on", "-s", metavar="PACKAGE", dest="stop_list", action="append",
|
||
|
|
help="Do not graph past this package (can be given multiple times)." +
|
||
|
|
" Can be a package name or a glob, " +
|
||
|
|
" 'virtual' to stop on virtual packages, or " +
|
||
|
|
"'host' to stop on host packages.")
|
||
|
|
parser.add_argument("--exclude", "-x", metavar="PACKAGE", dest="exclude_list", action="append",
|
||
|
|
help="Like --stop-on, but do not add PACKAGE to the graph.")
|
||
|
|
parser.add_argument("--exclude-mandatory", "-X", action="store_true",
|
||
|
|
help="Like if -x was passed for all mandatory dependencies.")
|
||
|
|
parser.add_argument("--colors", "-c", metavar="COLOR_LIST", dest="colors",
|
||
|
|
default="lightblue,grey,gainsboro",
|
||
|
|
help="Comma-separated list of the three colors to use" +
|
||
|
|
" to draw the top-level package, the target" +
|
||
|
|
" packages, and the host packages, in this order." +
|
||
|
|
" Defaults to: 'lightblue,grey,gainsboro'")
|
||
|
|
parser.add_argument("--transitive", dest="transitive", action='store_true',
|
||
|
|
default=False)
|
||
|
|
parser.add_argument("--no-transitive", dest="transitive", action='store_false',
|
||
|
|
help="Draw (do not draw) transitive dependencies")
|
||
|
|
parser.add_argument("--direct", dest="direct", action='store_true', default=True,
|
||
|
|
help="Draw direct dependencies (the default)")
|
||
|
|
parser.add_argument("--reverse", dest="direct", action='store_false',
|
||
|
|
help="Draw reverse dependencies")
|
||
|
|
parser.add_argument("--quiet", '-q', dest="quiet", action='store_true',
|
||
|
|
help="Quiet")
|
||
|
|
parser.add_argument("--flat-list", '-f', dest="flat_list", action='store_true', default=False,
|
||
|
|
help="Do not draw graph, just print a flat list")
|
||
|
|
return parser.parse_args()
|
||
|
|
|
||
|
|
|
||
|
|
def main():
|
||
|
|
args = parse_args()
|
||
|
|
|
||
|
|
check_only = args.check_only
|
||
|
|
|
||
|
|
logging.basicConfig(stream=sys.stderr, format='%(message)s',
|
||
|
|
level=logging.WARNING if args.quiet else logging.INFO)
|
||
|
|
|
||
|
|
if args.outfile is None:
|
||
|
|
outfile = sys.stdout
|
||
|
|
else:
|
||
|
|
if check_only:
|
||
|
|
logging.error("don't specify outfile and check-only at the same time")
|
||
|
|
sys.exit(1)
|
||
|
|
outfile = open(args.outfile, "w")
|
||
|
|
|
||
|
|
if args.package is None:
|
||
|
|
mode = MODE_FULL
|
||
|
|
rootpkg = 'all'
|
||
|
|
else:
|
||
|
|
mode = MODE_PKG
|
||
|
|
rootpkg = args.package
|
||
|
|
|
||
|
|
if args.stop_list is None:
|
||
|
|
stop_list = []
|
||
|
|
else:
|
||
|
|
stop_list = args.stop_list
|
||
|
|
|
||
|
|
if args.exclude_list is None:
|
||
|
|
exclude_list = []
|
||
|
|
else:
|
||
|
|
exclude_list = args.exclude_list
|
||
|
|
|
||
|
|
if args.exclude_mandatory:
|
||
|
|
exclude_list += MANDATORY_DEPS
|
||
|
|
|
||
|
|
if args.direct:
|
||
|
|
arrow_dir = "forward"
|
||
|
|
else:
|
||
|
|
if mode == MODE_FULL:
|
||
|
|
logging.error("--reverse needs a package")
|
||
|
|
sys.exit(1)
|
||
|
|
arrow_dir = "back"
|
||
|
|
|
||
|
|
draw_graph = not args.flat_list
|
||
|
|
|
||
|
|
# Get the colors: we need exactly three colors,
|
||
|
|
# so no need not split more than 4
|
||
|
|
# We'll let 'dot' validate the colors...
|
||
|
|
colors = args.colors.split(',', 4)
|
||
|
|
if len(colors) != 3:
|
||
|
|
logging.error("Error: incorrect color list '%s'" % args.colors)
|
||
|
|
sys.exit(1)
|
||
|
|
|
||
|
|
deps, rdeps, dict_types, dict_versions = brpkgutil.get_dependency_tree()
|
||
|
|
dict_deps = deps if args.direct else rdeps
|
||
|
|
|
||
|
|
check_circular_deps(dict_deps)
|
||
|
|
if check_only:
|
||
|
|
sys.exit(0)
|
||
|
|
|
||
|
|
dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive, arrow_dir)
|
||
|
|
|
||
|
|
# Start printing the graph data
|
||
|
|
if draw_graph:
|
||
|
|
outfile.write("digraph G {\n")
|
||
|
|
|
||
|
|
print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list,
|
||
|
|
arrow_dir, draw_graph, 0, args.depth, rootpkg, colors)
|
||
|
|
|
||
|
|
if draw_graph:
|
||
|
|
outfile.write("}\n")
|
||
|
|
else:
|
||
|
|
outfile.write("\n")
|
||
|
|
|
||
|
|
|
||
|
|
if __name__ == "__main__":
|
||
|
|
sys.exit(main())
|