buildtools/checkdeps/graphdeps.py

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