1#!/usr/bin/env python3 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# Copyright (C) 2019 Yann E. MORIN <yann.morin.1998@free.fr> 24 25import logging 26import sys 27import argparse 28from fnmatch import fnmatch 29 30import brpkgutil 31 32# Modes of operation: 33MODE_FULL = 1 # draw full dependency graph for all selected packages 34MODE_PKG = 2 # draw dependency graph for a given package 35 36allpkgs = [] 37 38 39# The Graphviz "dot" utility doesn't like dashes in node names. So for 40# node names, we strip all dashes. Also, nodes can't start with a number, 41# so we prepend an underscore. 42def pkg_node_name(pkg): 43 return "_" + pkg.replace("-", "") 44 45 46# Basic cache for the results of the is_dep() function, in order to 47# optimize the execution time. The cache is a dict of dict of boolean 48# values. The key to the primary dict is "pkg", and the key of the 49# sub-dicts is "pkg2". 50is_dep_cache = {} 51 52 53def is_dep_cache_insert(pkg, pkg2, val): 54 try: 55 is_dep_cache[pkg].update({pkg2: val}) 56 except KeyError: 57 is_dep_cache[pkg] = {pkg2: val} 58 59 60# Retrieves from the cache whether pkg2 is a transitive dependency 61# of pkg. 62# Note: raises a KeyError exception if the dependency is not known. 63def is_dep_cache_lookup(pkg, pkg2): 64 return is_dep_cache[pkg][pkg2] 65 66 67# This function return True if pkg is a dependency (direct or 68# transitive) of pkg2, dependencies being listed in the deps 69# dictionary. Returns False otherwise. 70# This is the un-cached version. 71def is_dep_uncached(pkg, pkg2, deps): 72 try: 73 for p in deps[pkg2]: 74 if pkg == p: 75 return True 76 if is_dep(pkg, p, deps): 77 return True 78 except KeyError: 79 pass 80 return False 81 82 83# See is_dep_uncached() above; this is the cached version. 84def is_dep(pkg, pkg2, deps): 85 try: 86 return is_dep_cache_lookup(pkg, pkg2) 87 except KeyError: 88 val = is_dep_uncached(pkg, pkg2, deps) 89 is_dep_cache_insert(pkg, pkg2, val) 90 return val 91 92 93# This function eliminates transitive dependencies; for example, given 94# these dependency chain: A->{B,C} and B->{C}, the A->{C} dependency is 95# already covered by B->{C}, so C is a transitive dependency of A, via B. 96# The functions does: 97# - for each dependency d[i] of the package pkg 98# - if d[i] is a dependency of any of the other dependencies d[j] 99# - do not keep d[i] 100# - otherwise keep d[i] 101def remove_transitive_deps(pkg, deps): 102 d = deps[pkg] 103 new_d = [] 104 for i in range(len(d)): 105 keep_me = True 106 for j in range(len(d)): 107 if j == i: 108 continue 109 if is_dep(d[i], d[j], deps): 110 keep_me = False 111 if keep_me: 112 new_d.append(d[i]) 113 return new_d 114 115 116# List of dependencies that all/many packages have, and that we want 117# to trim when generating the dependency graph. 118MANDATORY_DEPS = ['toolchain', 'skeleton', 'host-skeleton', 'host-tar', 'host-gzip', 'host-ccache'] 119 120 121# This function removes the dependency on some 'mandatory' package, like the 122# 'toolchain' package, or the 'skeleton' package 123def remove_mandatory_deps(pkg, deps): 124 return [p for p in deps[pkg] if p not in MANDATORY_DEPS] 125 126 127# This function returns all dependencies of pkg that are part of the 128# mandatory dependencies: 129def get_mandatory_deps(pkg, deps): 130 return [p for p in deps[pkg] if p in MANDATORY_DEPS] 131 132 133# This function will check that there is no loop in the dependency chain 134# As a side effect, it builds up the dependency cache. 135def check_circular_deps(deps): 136 def recurse(pkg): 137 if pkg not in list(deps.keys()): 138 return 139 if pkg in not_loop: 140 return 141 not_loop.append(pkg) 142 chain.append(pkg) 143 for p in deps[pkg]: 144 if p in chain: 145 logging.warning("\nRecursion detected for : %s" % (p)) 146 while True: 147 _p = chain.pop() 148 logging.warning("which is a dependency of: %s" % (_p)) 149 if p == _p: 150 sys.exit(1) 151 recurse(p) 152 chain.pop() 153 154 not_loop = [] 155 chain = [] 156 for pkg in list(deps.keys()): 157 recurse(pkg) 158 159 160# This functions trims down the dependency list of all packages. 161# It applies in sequence all the dependency-elimination methods. 162def remove_extra_deps(deps, rootpkg, transitive, arrow_dir): 163 # For the direct dependencies, find and eliminate mandatory 164 # deps, and add them to the root package. Don't do it for a 165 # reverse graph, because mandatory deps are only direct deps. 166 if arrow_dir == "forward": 167 for pkg in list(deps.keys()): 168 if not pkg == rootpkg: 169 for d in get_mandatory_deps(pkg, deps): 170 if d not in deps[rootpkg]: 171 deps[rootpkg].append(d) 172 deps[pkg] = remove_mandatory_deps(pkg, deps) 173 for pkg in list(deps.keys()): 174 if not transitive or pkg == rootpkg: 175 deps[pkg] = remove_transitive_deps(pkg, deps) 176 return deps 177 178 179# Print the attributes of a node: label and fill-color 180def print_attrs(outfile, pkg, pkg_type, pkg_version, depth, colors): 181 name = pkg_node_name(pkg) 182 if pkg == 'all': 183 label = 'ALL' 184 else: 185 label = pkg 186 if depth == 0: 187 color = colors[0] 188 else: 189 if pkg_type == "host": 190 color = colors[2] 191 else: 192 color = colors[1] 193 if pkg_version == "virtual": 194 outfile.write("%s [label = <<I>%s</I>>]\n" % (name, label)) 195 else: 196 outfile.write("%s [label = \"%s\"]\n" % (name, label)) 197 outfile.write("%s [color=%s,style=filled]\n" % (name, color)) 198 199 200done_deps = [] 201 202 203# Print the dependency graph of a package 204def print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, 205 arrow_dir, draw_graph, depth, max_depth, pkg, colors): 206 if pkg in done_deps: 207 return 208 done_deps.append(pkg) 209 if draw_graph: 210 print_attrs(outfile, pkg, dict_types[pkg], dict_versions[pkg], depth, colors) 211 elif depth != 0: 212 outfile.write("%s " % pkg) 213 if pkg not in dict_deps: 214 return 215 for p in stop_list: 216 if fnmatch(pkg, p): 217 return 218 if dict_versions[pkg] == "virtual" and "virtual" in stop_list: 219 return 220 if dict_types[pkg] == "host" and "host" in stop_list: 221 return 222 if max_depth == 0 or depth < max_depth: 223 for d in dict_deps[pkg]: 224 if dict_versions[d] == "virtual" and "virtual" in exclude_list: 225 continue 226 if dict_types[d] == "host" and "host" in exclude_list: 227 continue 228 add = True 229 for p in exclude_list: 230 if fnmatch(d, p): 231 add = False 232 break 233 if add: 234 if draw_graph: 235 outfile.write("%s -> %s [dir=%s]\n" % (pkg_node_name(pkg), pkg_node_name(d), arrow_dir)) 236 print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, 237 arrow_dir, draw_graph, depth + 1, max_depth, d, colors) 238 239 240def parse_args(): 241 parser = argparse.ArgumentParser(description="Graph packages dependencies") 242 parser.add_argument("--check-only", "-C", dest="check_only", action="store_true", default=False, 243 help="Only do the dependency checks (circular deps...)") 244 parser.add_argument("--outfile", "-o", metavar="OUT_FILE", dest="outfile", 245 help="File in which to generate the dot representation") 246 parser.add_argument("--package", '-p', metavar="PACKAGE", 247 help="Graph the dependencies of PACKAGE") 248 parser.add_argument("--depth", '-d', metavar="DEPTH", dest="depth", type=int, default=0, 249 help="Limit the dependency graph to DEPTH levels; 0 means no limit.") 250 parser.add_argument("--stop-on", "-s", metavar="PACKAGE", dest="stop_list", action="append", 251 help="Do not graph past this package (can be given multiple times)." + 252 " Can be a package name or a glob, " + 253 " 'virtual' to stop on virtual packages, or " + 254 "'host' to stop on host packages.") 255 parser.add_argument("--exclude", "-x", metavar="PACKAGE", dest="exclude_list", action="append", 256 help="Like --stop-on, but do not add PACKAGE to the graph.") 257 parser.add_argument("--exclude-mandatory", "-X", action="store_true", 258 help="Like if -x was passed for all mandatory dependencies.") 259 parser.add_argument("--colors", "-c", metavar="COLOR_LIST", dest="colors", 260 default="lightblue,grey,gainsboro", 261 help="Comma-separated list of the three colors to use" + 262 " to draw the top-level package, the target" + 263 " packages, and the host packages, in this order." + 264 " Defaults to: 'lightblue,grey,gainsboro'") 265 parser.add_argument("--transitive", dest="transitive", action='store_true', 266 default=False) 267 parser.add_argument("--no-transitive", dest="transitive", action='store_false', 268 help="Draw (do not draw) transitive dependencies") 269 parser.add_argument("--direct", dest="direct", action='store_true', default=True, 270 help="Draw direct dependencies (the default)") 271 parser.add_argument("--reverse", dest="direct", action='store_false', 272 help="Draw reverse dependencies") 273 parser.add_argument("--quiet", '-q', dest="quiet", action='store_true', 274 help="Quiet") 275 parser.add_argument("--flat-list", '-f', dest="flat_list", action='store_true', default=False, 276 help="Do not draw graph, just print a flat list") 277 return parser.parse_args() 278 279 280def main(): 281 args = parse_args() 282 283 check_only = args.check_only 284 285 logging.basicConfig(stream=sys.stderr, format='%(message)s', 286 level=logging.WARNING if args.quiet else logging.INFO) 287 288 if args.outfile is None: 289 outfile = sys.stdout 290 else: 291 if check_only: 292 logging.error("don't specify outfile and check-only at the same time") 293 sys.exit(1) 294 outfile = open(args.outfile, "w") 295 296 if args.package is None: 297 mode = MODE_FULL 298 rootpkg = 'all' 299 else: 300 mode = MODE_PKG 301 rootpkg = args.package 302 303 if args.stop_list is None: 304 stop_list = [] 305 else: 306 stop_list = args.stop_list 307 308 if args.exclude_list is None: 309 exclude_list = [] 310 else: 311 exclude_list = args.exclude_list 312 313 if args.exclude_mandatory: 314 exclude_list += MANDATORY_DEPS 315 316 if args.direct: 317 arrow_dir = "forward" 318 else: 319 if mode == MODE_FULL: 320 logging.error("--reverse needs a package") 321 sys.exit(1) 322 arrow_dir = "back" 323 324 draw_graph = not args.flat_list 325 326 # Get the colors: we need exactly three colors, 327 # so no need not split more than 4 328 # We'll let 'dot' validate the colors... 329 colors = args.colors.split(',', 4) 330 if len(colors) != 3: 331 logging.error("Error: incorrect color list '%s'" % args.colors) 332 sys.exit(1) 333 334 deps, rdeps, dict_types, dict_versions = brpkgutil.get_dependency_tree() 335 dict_deps = deps if args.direct else rdeps 336 337 check_circular_deps(dict_deps) 338 if check_only: 339 sys.exit(0) 340 341 dict_deps = remove_extra_deps(dict_deps, rootpkg, args.transitive, arrow_dir) 342 343 # Start printing the graph data 344 if draw_graph: 345 outfile.write("digraph G {\n") 346 347 print_pkg_deps(outfile, dict_deps, dict_types, dict_versions, stop_list, exclude_list, 348 arrow_dir, draw_graph, 0, args.depth, rootpkg, colors) 349 350 if draw_graph: 351 outfile.write("}\n") 352 else: 353 outfile.write("\n") 354 355 356if __name__ == "__main__": 357 sys.exit(main()) 358