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