support/scripts/graph-depends

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