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