123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357 |
- #!/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())
|