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