support/scripts/graph-depends

   1 #!/usr/bin/env python
   2
   3 # Usage (the graphviz package must be installed in your distribution)
   4 #  ./support/scripts/graph-depends [-p package-name] > test.dot
   5 #  dot -Tpdf test.dot -o test.pdf
   6 #
   7 # With no arguments, graph-depends will draw a complete graph of
   8 # dependencies for the current configuration.
   9 # If '-p <package-name>' is specified, graph-depends will draw a graph
  10 # of dependencies for the given package name.
  11 # If '-d <depth>' is specified, graph-depends will limit the depth of
  12 # the dependency graph to 'depth' levels.
  13 #
  14 # Limitations
  15 #
  16 #  * Some packages have dependencies that depend on the Buildroot
  17 #    configuration. For example, many packages have a dependency on
  18 #    openssl if openssl has been enabled. This tool will graph the
  19 #    dependencies as they are with the current Buildroot
  20 #    configuration.
  21 #
  22 # Copyright (C) 2010-2013 Thomas Petazzoni <thomas.petazzoni@free-electrons.com>
  23
  24 import sys
  25 import subprocess
  26 import argparse
  27 from fnmatch import fnmatch
  28
  29 import brpkgutil
  30
  31 # Modes of operation:
  32 MODE_FULL = 1   # draw full dependency graph for all selected packages
  33 MODE_PKG = 2    # draw dependency graph for a given package
  34
  35 allpkgs = []
  36
  37
  38 # Execute the "make show-targets" command to get the list of the main
  39 # Buildroot PACKAGES and return it formatted as a Python list. This
  40 # list is used as the starting point for full dependency graphs
  41 def get_targets():
  42     sys.stderr.write("Getting targets\n")
  43     cmd = ["make", "-s", "--no-print-directory", "show-targets"]
  44     p = subprocess.Popen(cmd, stdout=subprocess.PIPE, universal_newlines=True)
  45     output = p.communicate()[0].strip()
  46     if p.returncode != 0:
  47         return None
  48     if output == '':
  49         return []
  50     return output.split(' ')
  51
  52
  53 # Recursive function that builds the tree of dependencies for a given
  54 # list of packages. The dependencies are built in a list called
  55 # 'dependencies', which contains tuples of the form (pkg1 ->
  56 # pkg2_on_which_pkg1_depends, pkg3 -> pkg4_on_which_pkg3_depends) and
  57 # the function finally returns this list.
  58 def get_all_depends(pkgs, get_depends_func):
  59     dependencies = []
  60
  61     # Filter the packages for which we already have the dependencies
  62     filtered_pkgs = []
  63     for pkg in pkgs:
  64         if pkg in allpkgs:
  65             continue
  66         filtered_pkgs.append(pkg)
  67         allpkgs.append(pkg)
  68
  69     if len(filtered_pkgs) == 0:
  70         return []
  71
  72     depends = get_depends_func(filtered_pkgs)
  73
  74     deps = set()
  75     for pkg in filtered_pkgs:
  76         pkg_deps = depends[pkg]
  77
  78         # This package has no dependency.
  79         if pkg_deps == []:
  80             continue
  81
  82         # Add dependencies to the list of dependencies
  83         for dep in pkg_deps:
  84             dependencies.append((pkg, dep))
  85             deps.add(dep)
  86
  87     if len(deps) != 0:
  88         newdeps = get_all_depends(deps, get_depends_func)
  89         if newdeps is not None:
  90             dependencies += newdeps
  91
  92     return dependencies
  93
  94
  95 # The Graphviz "dot" utility doesn't like dashes in node names. So for
  96 # node names, we strip all dashes.
  97 def pkg_node_name(pkg):
  98     return pkg.replace("-", "")
  99
 100
 101 TARGET_EXCEPTIONS = [
 102     "target-finalize",
 103     "target-post-image",
 104 ]
 105
 106
 107 # Basic cache for the results of the is_dep() function, in order to
 108 # optimize the execution time. The cache is a dict of dict of boolean
 109 # values. The key to the primary dict is "pkg", and the key of the
 110 # sub-dicts is "pkg2".
 111 is_dep_cache = {}
 112
 113
 114 def is_dep_cache_insert(pkg, pkg2, val):
 115     try:
 116         is_dep_cache[pkg].update({pkg2: val})
 117     except KeyError:
 118         is_dep_cache[pkg] = {pkg2: val}
 119
 120
 121 # Retrieves from the cache whether pkg2 is a transitive dependency
 122 # of pkg.
 123 # Note: raises a KeyError exception if the dependency is not known.
 124 def is_dep_cache_lookup(pkg, pkg2):
 125     return is_dep_cache[pkg][pkg2]
 126
 127
 128 # This function return True if pkg is a dependency (direct or
 129 # transitive) of pkg2, dependencies being listed in the deps
 130 # dictionary. Returns False otherwise.
 131 # This is the un-cached version.
 132 def is_dep_uncached(pkg, pkg2, deps):
 133     try:
 134         for p in deps[pkg2]:
 135             if pkg == p:
 136                 return True
 137             if is_dep(pkg, p, deps):
 138                 return True
 139     except KeyError:
 140         pass
 141     return False
 142
 143
 144 # See is_dep_uncached() above; this is the cached version.
 145 def is_dep(pkg, pkg2, deps):
 146     try:
 147         return is_dep_cache_lookup(pkg, pkg2)
 148     except KeyError:
 149         val = is_dep_uncached(pkg, pkg2, deps)
 150         is_dep_cache_insert(pkg, pkg2, val)
 151         return val
 152
 153
 154 # This function eliminates transitive dependencies; for example, given
 155 # these dependency chain: A->{B,C} and B->{C}, the A->{C} dependency is
 156 # already covered by B->{C}, so C is a transitive dependency of A, via B.
 157 # The functions does:
 158 #   - for each dependency d[i] of the package pkg
 159 #     - if d[i] is a dependency of any of the other dependencies d[j]
 160 #       - do not keep d[i]
 161 #     - otherwise keep d[i]
 162 def remove_transitive_deps(pkg, deps):
 163     d = deps[pkg]
 164     new_d = []
 165     for i in range(len(d)):
 166         keep_me = True
 167         for j in range(len(d)):
 168             if j == i:
 169                 continue
 170             if is_dep(d[i], d[j], deps):
 171                 keep_me = False
 172         if keep_me:
 173             new_d.append(d[i])
 174     return new_d
 175
 176
 177 # This function removes the dependency on some 'mandatory' package, like the
 178 # 'toolchain' package, or the 'skeleton' package
 179 def remove_mandatory_deps(pkg, deps):
 180     return [p for p in deps[pkg] if p not in ['toolchain', 'skeleton']]
 181
 182
 183 # This function will check that there is no loop in the dependency chain
 184 # As a side effect, it builds up the dependency cache.
 185 def check_circular_deps(deps):
 186     def recurse(pkg):
 187         if pkg not in list(deps.keys()):
 188             return
 189         if pkg in not_loop:
 190             return
 191         not_loop.append(pkg)
 192         chain.append(pkg)
 193         for p in deps[pkg]:
 194             if p in chain:
 195                 sys.stderr.write("\nRecursion detected for  : %s\n" % (p))
 196                 while True:
 197                     _p = chain.pop()
 198                     sys.stderr.write("which is a dependency of: %s\n" % (_p))
 199                     if p == _p:
 200                         sys.exit(1)
 201             recurse(p)
 202         chain.pop()
 203
 204     not_loop = []
 205     chain = []
 206     for pkg in list(deps.keys()):
 207         recurse(pkg)
 208
 209
 210 # This functions trims down the dependency list of all packages.
 211 # It applies in sequence all the dependency-elimination methods.
 212 def remove_extra_deps(deps, transitive):
 213     for pkg in list(deps.keys()):
 214         if not pkg == 'all':
 215             deps[pkg] = remove_mandatory_deps(pkg, deps)
 216     for pkg in list(deps.keys()):
 217         if not transitive or pkg == 'all':
 218             deps[pkg] = remove_transitive_deps(pkg, deps)
 219     return deps
 220
 221
 222 # Print the attributes of a node: label and fill-color
 223 def print_attrs(outfile, pkg, version, depth, colors):
 224     name = pkg_node_name(pkg)
 225     if pkg == 'all':
 226         label = 'ALL'
 227     else:
 228         label = pkg
 229     if depth == 0:
 230         color = colors[0]
 231     else:
 232         if pkg.startswith('host') \
 233                 or pkg.startswith('toolchain') \
 234                 or pkg.startswith('rootfs'):
 235             color = colors[2]
 236         else:
 237             color = colors[1]
 238     if version == "virtual":
 239         outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label))
 240     else:
 241         outfile.write("%s [label = \"%s\"]\n" % (name, label))
 242     outfile.write("%s [color=%s,style=filled]\n" % (name, color))
 243
 244
 245 done_deps = []
 246
 247
 248 # Print the dependency graph of a package
 249 def print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
 250                    arrow_dir, depth, max_depth, pkg, colors):
 251     if pkg in done_deps:
 252         return
 253     done_deps.append(pkg)
 254     print_attrs(outfile, pkg, dict_version.get(pkg), depth, colors)
 255     if pkg not in dict_deps:
 256         return
 257     for p in stop_list:
 258         if fnmatch(pkg, p):
 259             return
 260     if dict_version.get(pkg) == "virtual" and "virtual" in stop_list:
 261         return
 262     if pkg.startswith("host-") and "host" in stop_list:
 263         return
 264     if max_depth == 0 or depth < max_depth:
 265         for d in dict_deps[pkg]:
 266             if dict_version.get(d) == "virtual" \
 267                and "virtual" in exclude_list:
 268                 continue
 269             if d.startswith("host-") \
 270                and "host" in exclude_list:
 271                 continue
 272             add = True
 273             for p in exclude_list:
 274                 if fnmatch(d, p):
 275                     add = False
 276                     break
 277             if add:
 278                 outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir))
 279                 print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
 280                                arrow_dir, depth + 1, max_depth, d, colors)
 281
 282
 283 def parse_args():
 284     parser = argparse.ArgumentParser(description="Graph packages dependencies")
 285     parser.add_argument("--check-only", "-C", dest="check_only", action="store_true", default=False,
 286                         help="Only do the dependency checks (circular deps...)")
 287     parser.add_argument("--outfile", "-o", metavar="OUT_FILE", dest="outfile",
 288                         help="File in which to generate the dot representation")
 289     parser.add_argument("--package", '-p', metavar="PACKAGE",
 290                         help="Graph the dependencies of PACKAGE")
 291     parser.add_argument("--depth", '-d', metavar="DEPTH", dest="depth", type=int, default=0,
 292                         help="Limit the dependency graph to DEPTH levels; 0 means no limit.")
 293     parser.add_argument("--stop-on", "-s", metavar="PACKAGE", dest="stop_list", action="append",
 294                         help="Do not graph past this package (can be given multiple times)." +
 295                         " Can be a package name or a glob, " +
 296                         " 'virtual' to stop on virtual packages, or " +
 297                         "'host' to stop on host packages.")
 298     parser.add_argument("--exclude", "-x", metavar="PACKAGE", dest="exclude_list", action="append",
 299                         help="Like --stop-on, but do not add PACKAGE to the graph.")
 300     parser.add_argument("--colours", "-c", metavar="COLOR_LIST", dest="colours",
 301                         default="lightblue,grey,gainsboro",
 302                         help="Comma-separated list of the three colours to use" +
 303                         " to draw the top-level package, the target" +
 304                         " packages, and the host packages, in this order." +
 305                         " Defaults to: 'lightblue,grey,gainsboro'")
 306     parser.add_argument("--transitive", dest="transitive", action='store_true',
 307                         default=False)
 308     parser.add_argument("--no-transitive", dest="transitive", action='store_false',
 309                         help="Draw (do not draw) transitive dependencies")
 310     parser.add_argument("--direct", dest="direct", action='store_true', default=True,
 311                         help="Draw direct dependencies (the default)")
 312     parser.add_argument("--reverse", dest="direct", action='store_false',
 313                         help="Draw reverse dependencies")
 314     return parser.parse_args()
 315
 316
 317 def main():
 318     args = parse_args()
 319
 320     check_only = args.check_only
 321
 322     if args.outfile is None:
 323         outfile = sys.stdout
 324     else:
 325         if check_only:
 326             sys.stderr.write("don't specify outfile and check-only at the same time\n")
 327             sys.exit(1)
 328         outfile = open(args.outfile, "w")
 329
 330     if args.package is None:
 331         mode = MODE_FULL
 332     else:
 333         mode = MODE_PKG
 334         rootpkg = args.package
 335
 336     if args.stop_list is None:
 337         stop_list = []
 338     else:
 339         stop_list = args.stop_list
 340
 341     if args.exclude_list is None:
 342         exclude_list = []
 343     else:
 344         exclude_list = args.exclude_list
 345
 346     if args.direct:
 347         get_depends_func = brpkgutil.get_depends
 348         arrow_dir = "forward"
 349     else:
 350         if mode == MODE_FULL:
 351             sys.stderr.write("--reverse needs a package\n")
 352             sys.exit(1)
 353         get_depends_func = brpkgutil.get_rdepends
 354         arrow_dir = "back"
 355
 356     # Get the colours: we need exactly three colours,
 357     # so no need not split more than 4
 358     # We'll let 'dot' validate the colours...
 359     colours = args.colours.split(',', 4)
 360     if len(colours) != 3:
 361         sys.stderr.write("Error: incorrect colour list '%s'\n" % args.colours)
 362         sys.exit(1)
 363
 364     # In full mode, start with the result of get_targets() to get the main
 365     # targets and then use get_all_depends() for all targets
 366     if mode == MODE_FULL:
 367         targets = get_targets()
 368         dependencies = []
 369         allpkgs.append('all')
 370         filtered_targets = []
 371         for tg in targets:
 372             # Skip uninteresting targets
 373             if tg in TARGET_EXCEPTIONS:
 374                 continue
 375             dependencies.append(('all', tg))
 376             filtered_targets.append(tg)
 377         deps = get_all_depends(filtered_targets, get_depends_func)
 378         if deps is not None:
 379             dependencies += deps
 380         rootpkg = 'all'
 381
 382     # In pkg mode, start directly with get_all_depends() on the requested
 383     # package
 384     elif mode == MODE_PKG:
 385         dependencies = get_all_depends([rootpkg], get_depends_func)
 386
 387     # Make the dependencies a dictionnary { 'pkg':[dep1, dep2, ...] }
 388     dict_deps = {}
 389     for dep in dependencies:
 390         if dep[0] not in dict_deps:
 391             dict_deps[dep[0]] = []
 392         dict_deps[dep[0]].append(dep[1])
 393
 394     check_circular_deps(dict_deps)
 395     if check_only:
 396         sys.exit(0)
 397
 398     dict_deps = remove_extra_deps(dict_deps, args.transitive)
 399     dict_version = brpkgutil.get_version([pkg for pkg in allpkgs
 400                                           if pkg != "all" and not pkg.startswith("root")])
 401
 402     # Start printing the graph data
 403     outfile.write("digraph G {\n")
 404
 405     print_pkg_deps(outfile, dict_deps, dict_version, stop_list, exclude_list,
 406                    arrow_dir, 0, args.depth, rootpkg, colours)
 407
 408     outfile.write("}\n")
 409
 410
 411 if __name__ == "__main__":
 412     sys.exit(main())