graph-depends 13 KB

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