graphdeps.py 16 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379380381382383384385386387388389390391392393394395396397398399400401402403404405406
  1. #!/usr/bin/env python
  2. # Copyright 2013 The Chromium Authors. All rights reserved.
  3. # Use of this source code is governed by a BSD-style license that can be
  4. # found in the LICENSE file.
  5. """Dumps a graph of allowed and disallowed inter-module dependencies described
  6. by the DEPS files in the source tree. Supports DOT and PNG as the output format.
  7. Enables filtering and differential highlighting of parts of the graph based on
  8. the specified criteria. This allows for a much easier visual analysis of the
  9. dependencies, including answering questions such as "if a new source must
  10. depend on modules A, B, and C, what valid options among the existing modules
  11. are there to put it in."
  12. See README.md for a detailed description of the DEPS format.
  13. """
  14. import os
  15. import optparse
  16. import pipes
  17. import re
  18. import sys
  19. from builddeps import DepsBuilder
  20. from rules import Rule
  21. class DepsGrapher(DepsBuilder):
  22. """Parses include_rules from DEPS files and outputs a DOT graph of the
  23. allowed and disallowed dependencies between directories and specific file
  24. regexps. Can generate only a subgraph of the whole dependency graph
  25. corresponding to the provided inclusion and exclusion regexp filters.
  26. Also can highlight fanins and/or fanouts of certain nodes matching the
  27. provided regexp patterns.
  28. """
  29. def __init__(self,
  30. base_directory,
  31. extra_repos,
  32. verbose,
  33. being_tested,
  34. ignore_temp_rules,
  35. ignore_specific_rules,
  36. hide_disallowed_deps,
  37. out_file,
  38. out_format,
  39. layout_engine,
  40. unflatten_graph,
  41. incl,
  42. excl,
  43. hilite_fanins,
  44. hilite_fanouts):
  45. """Creates a new DepsGrapher.
  46. Args:
  47. base_directory: OS-compatible path to root of checkout, e.g. C:\chr\src.
  48. verbose: Set to true for debug output.
  49. being_tested: Set to true to ignore the DEPS file at tools/graphdeps/DEPS.
  50. ignore_temp_rules: Ignore rules that start with Rule.TEMP_ALLOW ("!").
  51. ignore_specific_rules: Ignore rules from specific_include_rules sections.
  52. hide_disallowed_deps: Hide disallowed dependencies from the output graph.
  53. out_file: Output file name.
  54. out_format: Output format (anything GraphViz dot's -T option supports).
  55. layout_engine: Layout engine for formats other than 'dot'
  56. (anything that GraphViz dot's -K option supports).
  57. unflatten_graph: Try to reformat the output graph so it is narrower and
  58. taller. Helps fight overly flat and wide graphs, but
  59. sometimes produces a worse result.
  60. incl: Include only nodes matching this regexp; such nodes' fanin/fanout
  61. is also included.
  62. excl: Exclude nodes matching this regexp; such nodes' fanin/fanout is
  63. processed independently.
  64. hilite_fanins: Highlight fanins of nodes matching this regexp with a
  65. different edge and node color.
  66. hilite_fanouts: Highlight fanouts of nodes matching this regexp with a
  67. different edge and node color.
  68. """
  69. DepsBuilder.__init__(
  70. self,
  71. base_directory,
  72. extra_repos,
  73. verbose,
  74. being_tested,
  75. ignore_temp_rules,
  76. ignore_specific_rules)
  77. self.ignore_temp_rules = ignore_temp_rules
  78. self.ignore_specific_rules = ignore_specific_rules
  79. self.hide_disallowed_deps = hide_disallowed_deps
  80. self.out_file = out_file
  81. self.out_format = out_format
  82. self.layout_engine = layout_engine
  83. self.unflatten_graph = unflatten_graph
  84. self.incl = incl
  85. self.excl = excl
  86. self.hilite_fanins = hilite_fanins
  87. self.hilite_fanouts = hilite_fanouts
  88. self.deps = set()
  89. def DumpDependencies(self):
  90. """ Builds a dependency rule table and dumps the corresponding dependency
  91. graph to all requested formats."""
  92. self._BuildDepsGraph()
  93. self._DumpDependencies()
  94. def _BuildDepsGraph(self):
  95. """Recursively traverses the source tree starting at the specified directory
  96. and builds a dependency graph representation in self.deps."""
  97. for (rules, _) in self.GetAllRulesAndFiles():
  98. deps = rules.AsDependencyTuples(
  99. include_general_rules=True,
  100. include_specific_rules=not self.ignore_specific_rules)
  101. self.deps.update(deps)
  102. def _DumpDependencies(self):
  103. """Dumps the built dependency graph to the specified file with specified
  104. format."""
  105. if self.out_format == 'dot' and not self.layout_engine:
  106. if self.unflatten_graph:
  107. pipe = pipes.Template()
  108. pipe.append('unflatten -l 2 -c 3', '--')
  109. out = pipe.open(self.out_file, 'w')
  110. else:
  111. out = open(self.out_file, 'w')
  112. else:
  113. pipe = pipes.Template()
  114. if self.unflatten_graph:
  115. pipe.append('unflatten -l 2 -c 3', '--')
  116. dot_cmd = 'dot -T' + self.out_format
  117. if self.layout_engine:
  118. dot_cmd += ' -K' + self.layout_engine
  119. pipe.append(dot_cmd, '--')
  120. out = pipe.open(self.out_file, 'w')
  121. self._DumpDependenciesImpl(self.deps, out)
  122. out.close()
  123. def _DumpDependenciesImpl(self, deps, out):
  124. """Computes nodes' and edges' properties for the dependency graph |deps| and
  125. carries out the actual dumping to a file/pipe |out|."""
  126. deps_graph = dict()
  127. deps_srcs = set()
  128. # Pre-initialize the graph with src->(dst, allow) pairs.
  129. for (allow, src, dst) in deps:
  130. if allow == Rule.TEMP_ALLOW and self.ignore_temp_rules:
  131. continue
  132. deps_srcs.add(src)
  133. if src not in deps_graph:
  134. deps_graph[src] = []
  135. deps_graph[src].append((dst, allow))
  136. # Add all hierarchical parents too, in case some of them don't have their
  137. # own DEPS, and therefore are missing from the list of rules. Those will
  138. # be recursively populated with their parents' rules in the next block.
  139. parent_src = os.path.dirname(src)
  140. while parent_src:
  141. if parent_src not in deps_graph:
  142. deps_graph[parent_src] = []
  143. parent_src = os.path.dirname(parent_src)
  144. # For every node, propagate its rules down to all its children.
  145. deps_srcs = list(deps_srcs)
  146. deps_srcs.sort()
  147. for src in deps_srcs:
  148. parent_src = os.path.dirname(src)
  149. if parent_src:
  150. # We presort the list, so parents are guaranteed to precede children.
  151. assert parent_src in deps_graph,\
  152. "src: %s, parent_src: %s" % (src, parent_src)
  153. for (dst, allow) in deps_graph[parent_src]:
  154. # Check that this node does not explicitly override a rule from the
  155. # parent that we're about to add.
  156. if ((dst, Rule.ALLOW) not in deps_graph[src]) and \
  157. ((dst, Rule.TEMP_ALLOW) not in deps_graph[src]) and \
  158. ((dst, Rule.DISALLOW) not in deps_graph[src]):
  159. deps_graph[src].append((dst, allow))
  160. node_props = {}
  161. edges = []
  162. # 1) Populate a list of edge specifications in DOT format;
  163. # 2) Populate a list of computed raw node attributes to be output as node
  164. # specifications in DOT format later on.
  165. # Edges and nodes are emphasized with color and line/border weight depending
  166. # on how many of incl/excl/hilite_fanins/hilite_fanouts filters they hit,
  167. # and in what way.
  168. for src in deps_graph.keys():
  169. for (dst, allow) in deps_graph[src]:
  170. if allow == Rule.DISALLOW and self.hide_disallowed_deps:
  171. continue
  172. if allow == Rule.ALLOW and src == dst:
  173. continue
  174. edge_spec = "%s->%s" % (src, dst)
  175. if not re.search(self.incl, edge_spec) or \
  176. re.search(self.excl, edge_spec):
  177. continue
  178. if src not in node_props:
  179. node_props[src] = {'hilite': None, 'degree': 0}
  180. if dst not in node_props:
  181. node_props[dst] = {'hilite': None, 'degree': 0}
  182. edge_weight = 1
  183. if self.hilite_fanouts and re.search(self.hilite_fanouts, src):
  184. node_props[src]['hilite'] = 'lightgreen'
  185. node_props[dst]['hilite'] = 'lightblue'
  186. node_props[dst]['degree'] += 1
  187. edge_weight += 1
  188. if self.hilite_fanins and re.search(self.hilite_fanins, dst):
  189. node_props[src]['hilite'] = 'lightblue'
  190. node_props[dst]['hilite'] = 'lightgreen'
  191. node_props[src]['degree'] += 1
  192. edge_weight += 1
  193. if allow == Rule.ALLOW:
  194. edge_color = (edge_weight > 1) and 'blue' or 'green'
  195. edge_style = 'solid'
  196. elif allow == Rule.TEMP_ALLOW:
  197. edge_color = (edge_weight > 1) and 'blue' or 'green'
  198. edge_style = 'dashed'
  199. else:
  200. edge_color = 'red'
  201. edge_style = 'dashed'
  202. edges.append(' "%s" -> "%s" [style=%s,color=%s,penwidth=%d];' % \
  203. (src, dst, edge_style, edge_color, edge_weight))
  204. # Reformat the computed raw node attributes into a final DOT representation.
  205. nodes = []
  206. for (node, attrs) in node_props.items():
  207. attr_strs = []
  208. if attrs['hilite']:
  209. attr_strs.append('style=filled,fillcolor=%s' % attrs['hilite'])
  210. attr_strs.append('penwidth=%d' % (attrs['degree'] or 1))
  211. nodes.append(' "%s" [%s];' % (node, ','.join(attr_strs)))
  212. # Output nodes and edges to |out| (can be a file or a pipe).
  213. edges.sort()
  214. nodes.sort()
  215. out.write('digraph DEPS {\n'
  216. ' fontsize=8;\n')
  217. out.write('\n'.join(nodes))
  218. out.write('\n\n')
  219. out.write('\n'.join(edges))
  220. out.write('\n}\n')
  221. out.close()
  222. def PrintUsage():
  223. print("""Usage: python graphdeps.py [--root <root>]
  224. --root ROOT Specifies the repository root. This defaults to "../../.."
  225. relative to the script file. This will be correct given the
  226. normal location of the script in "<root>/tools/graphdeps".
  227. --(others) There are a few lesser-used options; run with --help to show them.
  228. Examples:
  229. Dump the whole dependency graph:
  230. graphdeps.py
  231. Find a suitable place for a new source that must depend on /apps and
  232. /content/browser/renderer_host. Limit potential candidates to /apps,
  233. /chrome/browser and content/browser, and descendants of those three.
  234. Generate both DOT and PNG output. The output will highlight the fanins
  235. of /apps and /content/browser/renderer_host. Overlapping nodes in both fanins
  236. will be emphasized by a thicker border. Those nodes are the ones that are
  237. allowed to depend on both targets, therefore they are all legal candidates
  238. to place the new source in:
  239. graphdeps.py \
  240. --root=./src \
  241. --out=./DEPS.svg \
  242. --format=svg \
  243. --incl='^(apps|chrome/browser|content/browser)->.*' \
  244. --excl='.*->third_party' \
  245. --fanin='^(apps|content/browser/renderer_host)$' \
  246. --ignore-specific-rules \
  247. --ignore-temp-rules""")
  248. def main():
  249. option_parser = optparse.OptionParser()
  250. option_parser.add_option(
  251. "", "--root",
  252. default="", dest="base_directory",
  253. help="Specifies the repository root. This defaults "
  254. "to '../../..' relative to the script file, which "
  255. "will normally be the repository root.")
  256. option_parser.add_option(
  257. '', '--extra-repos',
  258. action='append', dest='extra_repos', default=[],
  259. help='Specifies extra repositories relative to root repository.')
  260. option_parser.add_option(
  261. "-f", "--format",
  262. dest="out_format", default="dot",
  263. help="Output file format. "
  264. "Can be anything that GraphViz dot's -T option supports. "
  265. "The most useful ones are: dot (text), svg (image), pdf (image)."
  266. "NOTES: dotty has a known problem with fonts when displaying DOT "
  267. "files on Ubuntu - if labels are unreadable, try other formats.")
  268. option_parser.add_option(
  269. "-o", "--out",
  270. dest="out_file", default="DEPS",
  271. help="Output file name. If the name does not end in an extension "
  272. "matching the output format, that extension is automatically "
  273. "appended.")
  274. option_parser.add_option(
  275. "-l", "--layout-engine",
  276. dest="layout_engine", default="",
  277. help="Layout rendering engine. "
  278. "Can be anything that GraphViz dot's -K option supports. "
  279. "The most useful are in decreasing order: dot, fdp, circo, osage. "
  280. "NOTE: '-f dot' and '-f dot -l dot' are different: the former "
  281. "will dump a raw DOT graph and stop; the latter will further "
  282. "filter it through 'dot -Tdot -Kdot' layout engine.")
  283. option_parser.add_option(
  284. "-i", "--incl",
  285. default="^.*$", dest="incl",
  286. help="Include only edges of the graph that match the specified regexp. "
  287. "The regexp is applied to edges of the graph formatted as "
  288. "'source_node->target_node', where the '->' part is vebatim. "
  289. "Therefore, a reliable regexp should look like "
  290. "'^(chrome|chrome/browser|chrome/common)->content/public/browser$' "
  291. "or similar, with both source and target node regexps present, "
  292. "explicit ^ and $, and otherwise being as specific as possible.")
  293. option_parser.add_option(
  294. "-e", "--excl",
  295. default="^$", dest="excl",
  296. help="Exclude dependent nodes that match the specified regexp. "
  297. "See --incl for details on the format.")
  298. option_parser.add_option(
  299. "", "--fanin",
  300. default="", dest="hilite_fanins",
  301. help="Highlight fanins of nodes matching the specified regexp.")
  302. option_parser.add_option(
  303. "", "--fanout",
  304. default="", dest="hilite_fanouts",
  305. help="Highlight fanouts of nodes matching the specified regexp.")
  306. option_parser.add_option(
  307. "", "--ignore-temp-rules",
  308. action="store_true", dest="ignore_temp_rules", default=False,
  309. help="Ignore !-prefixed (temporary) rules in DEPS files.")
  310. option_parser.add_option(
  311. "", "--ignore-specific-rules",
  312. action="store_true", dest="ignore_specific_rules", default=False,
  313. help="Ignore specific_include_rules section of DEPS files.")
  314. option_parser.add_option(
  315. "", "--hide-disallowed-deps",
  316. action="store_true", dest="hide_disallowed_deps", default=False,
  317. help="Hide disallowed dependencies in the output graph.")
  318. option_parser.add_option(
  319. "", "--unflatten",
  320. action="store_true", dest="unflatten_graph", default=False,
  321. help="Try to reformat the output graph so it is narrower and taller. "
  322. "Helps fight overly flat and wide graphs, but sometimes produces "
  323. "inferior results.")
  324. option_parser.add_option(
  325. "-v", "--verbose",
  326. action="store_true", default=False,
  327. help="Print debug logging")
  328. options, args = option_parser.parse_args()
  329. if not options.out_file.endswith(options.out_format):
  330. options.out_file += '.' + options.out_format
  331. deps_grapher = DepsGrapher(
  332. base_directory=options.base_directory,
  333. extra_repos=options.extra_repos,
  334. verbose=options.verbose,
  335. being_tested=False,
  336. ignore_temp_rules=options.ignore_temp_rules,
  337. ignore_specific_rules=options.ignore_specific_rules,
  338. hide_disallowed_deps=options.hide_disallowed_deps,
  339. out_file=options.out_file,
  340. out_format=options.out_format,
  341. layout_engine=options.layout_engine,
  342. unflatten_graph=options.unflatten_graph,
  343. incl=options.incl,
  344. excl=options.excl,
  345. hilite_fanins=options.hilite_fanins,
  346. hilite_fanouts=options.hilite_fanouts)
  347. if len(args) > 0:
  348. PrintUsage()
  349. return 1
  350. print('Using base directory: ', deps_grapher.base_directory)
  351. print('include nodes : ', options.incl)
  352. print('exclude nodes : ', options.excl)
  353. print('highlight fanins of : ', options.hilite_fanins)
  354. print('highlight fanouts of: ', options.hilite_fanouts)
  355. deps_grapher.DumpDependencies()
  356. return 0
  357. if '__main__' == __name__:
  358. sys.exit(main())