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