buildroot/support/scripts/graph-depends

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