| #!/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, direct): | |
| # 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 direct: | |
| 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)) | |
| # Print the dependency graph of a package | |
| def print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, | |
| direct, draw_graph, depth, max_depth, pkg, colors, done_deps=None): | |
| if done_deps is None: | |
| done_deps = [] | |
| 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: | |
| if direct: | |
| outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), "forward")) | |
| else: | |
| outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(d), pkg_node_name(pkg), "forward")) | |
| print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, | |
| direct, draw_graph, depth + 1, max_depth, d, colors, done_deps) | |
| 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=False, | |
| help="Draw direct dependencies (the default)") | |
| parser.add_argument("--reverse", dest="reverse", action='store_true', default=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 not args.direct and not args.reverse: | |
| args.direct = True | |
| 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.reverse and mode == MODE_FULL: | |
| logging.error("--reverse needs a package") | |
| sys.exit(1) | |
| 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) | |
| # Start printing the graph data | |
| if not check_only and draw_graph: | |
| outfile.write("digraph G {\n") | |
| deps, rdeps, dict_types, dict_versions = brpkgutil.get_dependency_tree() | |
| # forward | |
| if args.direct: | |
| dict_deps = deps | |
| direct = True | |
| check_circular_deps(dict_deps) | |
| if not check_only: | |
| dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive, direct) | |
| print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, | |
| direct, draw_graph, 0, args.depth, rootpkg, colors) | |
| # reverse | |
| if args.reverse: | |
| dict_deps = rdeps | |
| direct = False | |
| check_circular_deps(dict_deps) | |
| if not check_only: | |
| dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive, direct) | |
| print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, | |
| direct, draw_graph, 0, args.depth, rootpkg, colors) | |
| if not check_only and draw_graph: | |
| outfile.write("}\n") | |
| else: | |
| outfile.write("\n") | |
| if __name__ == "__main__": | |
| sys.exit(main()) |