Added graphdeps.py tool to dump inter-module dependency graph to DOT/PNG with regexp filtering/highlighting.

Joi: this commit consists of 2 logical parts. Part #1 is refactoring of checkdeps.py into a base class in builddeps.py and a subclass in the new trimmed down checkdeps.py. Part #2 is adding graphdeps.py, which derives from the same base class and does its own thing. There are also trivial accompanying changes to rules.py.

This tool was very useful to me during a recent development for understanding inter-module dependencies and finding good places for new sources.

BUG=292397

Review URL: https://codereview.chromium.org/24018004

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@226295 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 795 insertions, 323 deletions

diff --git a/tools/checkdeps/builddeps.py b/tools/checkdeps/builddeps.py
new file mode 100755
index 0000000..48ec64a
--- /dev/null
+++ b/tools/checkdeps/builddeps.py
@@ -0,0 +1,347 @@
+# Copyright 2013 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""Traverses the source tree, parses all found DEPS files, and constructs
+a dependency rule table to be used by subclasses.
+
+The format of the deps file:
+
+First you have the normal module-level deps. These are the ones used by
+gclient. An example would be:
+
+  deps = {
+    "base":"http://foo.bar/trunk/base"
+  }
+
+DEPS files not in the top-level of a module won't need this. Then you
+have any additional include rules. You can add (using "+") or subtract
+(using "-") from the previously specified rules (including
+module-level deps). You can also specify a path that is allowed for
+now but that we intend to remove, using "!"; this is treated the same
+as "+" when check_deps is run by our bots, but a presubmit step will
+show a warning if you add a new include of a file that is only allowed
+by "!".
+
+Note that for .java files, there is currently no difference between
+"+" and "!", even in the presubmit step.
+
+  include_rules = {
+    # Code should be able to use base (it's specified in the module-level
+    # deps above), but nothing in "base/evil" because it's evil.
+    "-base/evil",
+
+    # But this one subdirectory of evil is OK.
+    "+base/evil/not",
+
+    # And it can include files from this other directory even though there is
+    # no deps rule for it.
+    "+tools/crime_fighter",
+
+    # This dependency is allowed for now but work is ongoing to remove it,
+    # so you shouldn't add further dependencies on it.
+    "!base/evil/ok_for_now.h",
+  }
+
+If you have certain include rules that should only be applied for some
+files within this directory and subdirectories, you can write a
+section named specific_include_rules that is a hash map of regular
+expressions to the list of rules that should apply to files matching
+them.  Note that such rules will always be applied before the rules
+from 'include_rules' have been applied, but the order in which rules
+associated with different regular expressions is applied is arbitrary.
+
+  specific_include_rules = {
+    ".*_(unit|browser|api)test\.cc": [
+      "+libraries/testsupport",
+    ],
+  }
+
+DEPS files may be placed anywhere in the tree. Each one applies to all
+subdirectories, where there may be more DEPS files that provide additions or
+subtractions for their own sub-trees.
+
+There is an implicit rule for the current directory (where the DEPS file lives)
+and all of its subdirectories. This prevents you from having to explicitly
+allow the current directory everywhere.  This implicit rule is applied first,
+so you can modify or remove it using the normal include rules.
+
+The rules are processed in order. This means you can explicitly allow a higher
+directory and then take away permissions from sub-parts, or the reverse.
+
+Note that all directory separators must be slashes (Unix-style) and not
+backslashes. All directories should be relative to the source root and use
+only lowercase.
+"""
+
+import os
+import subprocess
+import copy
+
+from rules import Rule, Rules
+
+
+# Variable name used in the DEPS file to add or subtract include files from
+# the module-level deps.
+INCLUDE_RULES_VAR_NAME = 'include_rules'
+
+# Variable name used in the DEPS file to add or subtract include files
+# from module-level deps specific to files whose basename (last
+# component of path) matches a given regular expression.
+SPECIFIC_INCLUDE_RULES_VAR_NAME = 'specific_include_rules'
+
+# Optionally present in the DEPS file to list subdirectories which should not
+# be checked. This allows us to skip third party code, for example.
+SKIP_SUBDIRS_VAR_NAME = 'skip_child_includes'
+
+
+def NormalizePath(path):
+  """Returns a path normalized to how we write DEPS rules and compare paths.
+  """
+  return path.lower().replace('\\', '/')
+
+
+class DepsBuilder(object):
+  """Parses include_rules from DEPS files.
+  """
+
+  def __init__(self,
+               base_directory=None,
+               verbose=False,
+               being_tested=False,
+               ignore_temp_rules=False,
+               ignore_specific_rules=False):
+    """Creates a new DepsBuilder.
+
+    Args:
+      base_directory: OS-compatible path to root of checkout, e.g. C:\chr\src.
+      verbose: Set to true for debug output.
+      being_tested: Set to true to ignore the DEPS file at tools/checkdeps/DEPS.
+      ignore_temp_rules: Ignore rules that start with Rule.TEMP_ALLOW ("!").
+    """
+    self.base_directory = base_directory
+    self.verbose = verbose
+    self._under_test = being_tested
+    self._ignore_temp_rules = ignore_temp_rules
+    self._ignore_specific_rules = ignore_specific_rules
+
+    if not base_directory:
+      self.base_directory = os.path.abspath(
+        os.path.join(os.path.abspath(os.path.dirname(__file__)), '..', '..'))
+
+    self.git_source_directories = set()
+    self._AddGitSourceDirectories()
+
+    # Map of normalized directory paths to rules to use for those
+    # directories, or None for directories that should be skipped.
+    self.directory_rules = {}
+    self._ApplyDirectoryRulesAndSkipSubdirs(Rules(), self.base_directory)
+
+  def _ApplyRules(self, existing_rules, includes, specific_includes, cur_dir):
+    """Applies the given include rules, returning the new rules.
+
+    Args:
+      existing_rules: A set of existing rules that will be combined.
+      include: The list of rules from the "include_rules" section of DEPS.
+      specific_includes: E.g. {'.*_unittest\.cc': ['+foo', '-blat']} rules
+                         from the "specific_include_rules" section of DEPS.
+      cur_dir: The current directory, normalized path. We will create an
+               implicit rule that allows inclusion from this directory.
+
+    Returns: A new set of rules combining the existing_rules with the other
+             arguments.
+    """
+    rules = copy.deepcopy(existing_rules)
+
+    # First apply the implicit "allow" rule for the current directory.
+    if cur_dir.startswith(
+          NormalizePath(os.path.normpath(self.base_directory))):
+      relative_dir = cur_dir[len(self.base_directory) + 1:]
+
+      source = relative_dir
+      if len(source) == 0:
+        source = 'top level'  # Make the help string a little more meaningful.
+      rules.AddRule('+' + relative_dir,
+                    relative_dir,
+                    'Default rule for ' + source)
+    else:
+      raise Exception('Internal error: base directory is not at the beginning' +
+                      ' for\n  %s and base dir\n  %s' %
+                      (cur_dir, self.base_directory))
+
+    def ApplyOneRule(rule_str, cur_dir, dependee_regexp=None):
+      """Deduces a sensible description for the rule being added, and
+      adds the rule with its description to |rules|.
+
+      If we are ignoring temporary rules, this function does nothing
+      for rules beginning with the Rule.TEMP_ALLOW character.
+      """
+      if self._ignore_temp_rules and rule_str.startswith(Rule.TEMP_ALLOW):
+        return
+
+      rule_block_name = 'include_rules'
+      if dependee_regexp:
+        rule_block_name = 'specific_include_rules'
+      if not relative_dir:
+        rule_description = 'the top level %s' % rule_block_name
+      else:
+        rule_description = relative_dir + "'s %s" % rule_block_name
+      rules.AddRule(rule_str, relative_dir, rule_description, dependee_regexp)
+
+    # Apply the additional explicit rules.
+    for (_, rule_str) in enumerate(includes):
+      ApplyOneRule(rule_str, cur_dir)
+
+    # Finally, apply the specific rules.
+    if not self._ignore_specific_rules:
+      for regexp, specific_rules in specific_includes.iteritems():
+        for rule_str in specific_rules:
+          ApplyOneRule(rule_str, cur_dir, regexp)
+
+    return rules
+
+  def _ApplyDirectoryRules(self, existing_rules, dir_name):
+    """Combines rules from the existing rules and the new directory.
+
+    Any directory can contain a DEPS file. Toplevel DEPS files can contain
+    module dependencies which are used by gclient. We use these, along with
+    additional include rules and implicit rules for the given directory, to
+    come up with a combined set of rules to apply for the directory.
+
+    Args:
+      existing_rules: The rules for the parent directory. We'll add-on to these.
+      dir_name: The directory name that the deps file may live in (if
+                it exists).  This will also be used to generate the
+                implicit rules.  This is a non-normalized path.
+
+    Returns: A tuple containing: (1) the combined set of rules to apply to the
+             sub-tree, and (2) a list of all subdirectories that should NOT be
+             checked, as specified in the DEPS file (if any).
+    """
+    norm_dir_name = NormalizePath(dir_name)
+
+    # Check for a .svn directory in this directory or check this directory is
+    # contained in git source direcotries. This will tell us if it's a source
+    # directory and should be checked.
+    if not (os.path.exists(os.path.join(dir_name, ".svn")) or
+            (norm_dir_name in self.git_source_directories)):
+      return (None, [])
+
+    # Check the DEPS file in this directory.
+    if self.verbose:
+      print 'Applying rules from', dir_name
+    def FromImpl(_unused, _unused2):
+      pass  # NOP function so "From" doesn't fail.
+
+    def FileImpl(_unused):
+      pass  # NOP function so "File" doesn't fail.
+
+    class _VarImpl:
+      def __init__(self, local_scope):
+        self._local_scope = local_scope
+
+      def Lookup(self, var_name):
+        """Implements the Var syntax."""
+        if var_name in self._local_scope.get('vars', {}):
+          return self._local_scope['vars'][var_name]
+        raise Exception('Var is not defined: %s' % var_name)
+
+    local_scope = {}
+    global_scope = {
+        'File': FileImpl,
+        'From': FromImpl,
+        'Var': _VarImpl(local_scope).Lookup,
+        }
+    deps_file = os.path.join(dir_name, 'DEPS')
+
+    # The second conditional here is to disregard the
+    # tools/checkdeps/DEPS file while running tests.  This DEPS file
+    # has a skip_child_includes for 'testdata' which is necessary for
+    # running production tests, since there are intentional DEPS
+    # violations under the testdata directory.  On the other hand when
+    # running tests, we absolutely need to verify the contents of that
+    # directory to trigger those intended violations and see that they
+    # are handled correctly.
+    if os.path.isfile(deps_file) and (
+        not self._under_test or not os.path.split(dir_name)[1] == 'checkdeps'):
+      execfile(deps_file, global_scope, local_scope)
+    elif self.verbose:
+      print '  No deps file found in', dir_name
+
+    # Even if a DEPS file does not exist we still invoke ApplyRules
+    # to apply the implicit "allow" rule for the current directory
+    include_rules = local_scope.get(INCLUDE_RULES_VAR_NAME, [])
+    specific_include_rules = local_scope.get(SPECIFIC_INCLUDE_RULES_VAR_NAME,
+                                             {})
+    skip_subdirs = local_scope.get(SKIP_SUBDIRS_VAR_NAME, [])
+
+    return (self._ApplyRules(existing_rules, include_rules,
+                             specific_include_rules, norm_dir_name),
+            skip_subdirs)
+
+  def _ApplyDirectoryRulesAndSkipSubdirs(self, parent_rules, dir_path):
+    """Given |parent_rules| and a subdirectory |dir_path| from the
+    directory that owns the |parent_rules|, add |dir_path|'s rules to
+    |self.directory_rules|, and add None entries for any of its
+    subdirectories that should be skipped.
+    """
+    directory_rules, excluded_subdirs = self._ApplyDirectoryRules(parent_rules,
+                                                                  dir_path)
+    self.directory_rules[NormalizePath(dir_path)] = directory_rules
+    for subdir in excluded_subdirs:
+      self.directory_rules[NormalizePath(
+          os.path.normpath(os.path.join(dir_path, subdir)))] = None
+
+  def GetDirectoryRules(self, dir_path):
+    """Returns a Rules object to use for the given directory, or None
+    if the given directory should be skipped.  This takes care of
+    first building rules for parent directories (up to
+    self.base_directory) if needed.
+
+    Args:
+      dir_path: A real (non-normalized) path to the directory you want
+      rules for.
+    """
+    norm_dir_path = NormalizePath(dir_path)
+
+    if not norm_dir_path.startswith(
+        NormalizePath(os.path.normpath(self.base_directory))):
+      dir_path = os.path.join(self.base_directory, dir_path)
+      norm_dir_path = NormalizePath(dir_path)
+
+    parent_dir = os.path.dirname(dir_path)
+    parent_rules = None
+    if not norm_dir_path in self.directory_rules:
+      parent_rules = self.GetDirectoryRules(parent_dir)
+
+    # We need to check for an entry for our dir_path again, in case we
+    # are at a path e.g. A/B/C where A/B/DEPS specifies the C
+    # subdirectory to be skipped; in this case, the invocation to
+    # GetDirectoryRules(parent_dir) has already filled in an entry for
+    # A/B/C.
+    if not norm_dir_path in self.directory_rules:
+      if not parent_rules:
+        # If the parent directory should be skipped, then the current
+        # directory should also be skipped.
+        self.directory_rules[norm_dir_path] = None
+      else:
+        self._ApplyDirectoryRulesAndSkipSubdirs(parent_rules, dir_path)
+    return self.directory_rules[norm_dir_path]
+
+  def _AddGitSourceDirectories(self):
+    """Adds any directories containing sources managed by git to
+    self.git_source_directories.
+    """
+    if not os.path.exists(os.path.join(self.base_directory, '.git')):
+      return
+
+    popen_out = os.popen('cd %s && git ls-files --full-name .' %
+                         subprocess.list2cmdline([self.base_directory]))
+    for line in popen_out.readlines():
+      dir_name = os.path.join(self.base_directory, os.path.dirname(line))
+      # Add the directory as well as all the parent directories. Use
+      # forward slashes and lower case to normalize paths.
+      while dir_name != self.base_directory:
+        self.git_source_directories.add(NormalizePath(dir_name))
+        dir_name = os.path.dirname(dir_name)
+    self.git_source_directories.add(NormalizePath(self.base_directory))
diff --git a/tools/checkdeps/checkdeps.py b/tools/checkdeps/checkdeps.py
index 5bfde13..0dd0f49 100755
--- a/tools/checkdeps/checkdeps.py
+++ b/tools/checkdeps/checkdeps.py
@@ -1,114 +1,28 @@
 #!/usr/bin/env python
-# Copyright (c) 2012 The Chromium Authors. All rights reserved.
+# Copyright 2012 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
 """Makes sure that files include headers from allowed directories.
 
 Checks DEPS files in the source tree for rules, and applies those rules to
-"#include" commands in source files. Any source file including something not
-permitted by the DEPS files will fail.
-
-The format of the deps file:
-
-First you have the normal module-level deps. These are the ones used by
-gclient. An example would be:
-
-  deps = {
-    "base":"http://foo.bar/trunk/base"
-  }
-
-DEPS files not in the top-level of a module won't need this. Then you
-have any additional include rules. You can add (using "+") or subtract
-(using "-") from the previously specified rules (including
-module-level deps). You can also specify a path that is allowed for
-now but that we intend to remove, using "!"; this is treated the same
-as "+" when check_deps is run by our bots, but a presubmit step will
-show a warning if you add a new include of a file that is only allowed
-by "!".
-
-Note that for .java files, there is currently no difference between
-"+" and "!", even in the presubmit step.
-
-  include_rules = {
-    # Code should be able to use base (it's specified in the module-level
-    # deps above), but nothing in "base/evil" because it's evil.
-    "-base/evil",
-
-    # But this one subdirectory of evil is OK.
-    "+base/evil/not",
-
-    # And it can include files from this other directory even though there is
-    # no deps rule for it.
-    "+tools/crime_fighter",
-
-    # This dependency is allowed for now but work is ongoing to remove it,
-    # so you shouldn't add further dependencies on it.
-    "!base/evil/ok_for_now.h",
-  }
-
-If you have certain include rules that should only be applied for some
-files within this directory and subdirectories, you can write a
-section named specific_include_rules that is a hash map of regular
-expressions to the list of rules that should apply to files matching
-them.  Note that such rules will always be applied before the rules
-from 'include_rules' have been applied, but the order in which rules
-associated with different regular expressions is applied is arbitrary.
-
-  specific_include_rules = {
-    ".*_(unit|browser|api)test\.cc": [
-      "+libraries/testsupport",
-    ],
-  }
-
-DEPS files may be placed anywhere in the tree. Each one applies to all
-subdirectories, where there may be more DEPS files that provide additions or
-subtractions for their own sub-trees.
-
-There is an implicit rule for the current directory (where the DEPS file lives)
-and all of its subdirectories. This prevents you from having to explicitly
-allow the current directory everywhere.  This implicit rule is applied first,
-so you can modify or remove it using the normal include rules.
-
-The rules are processed in order. This means you can explicitly allow a higher
-directory and then take away permissions from sub-parts, or the reverse.
-
-Note that all directory separators must be slashes (Unix-style) and not
-backslashes. All directories should be relative to the source root and use
-only lowercase.
+"#include" and "import" directives in the .cpp and .java source files.
+Any source file including something not permitted by the DEPS files will fail.
+
+See builddeps.py for a detailed description of the DEPS format.
 """
 
 import os
 import optparse
 import re
-import subprocess
 import sys
-import copy
 
 import cpp_checker
 import java_checker
 import results
-from rules import Rule, Rules
-
-
-# Variable name used in the DEPS file to add or subtract include files from
-# the module-level deps.
-INCLUDE_RULES_VAR_NAME = 'include_rules'
 
-# Variable name used in the DEPS file to add or subtract include files
-# from module-level deps specific to files whose basename (last
-# component of path) matches a given regular expression.
-SPECIFIC_INCLUDE_RULES_VAR_NAME = 'specific_include_rules'
-
-# Optionally present in the DEPS file to list subdirectories which should not
-# be checked. This allows us to skip third party code, for example.
-SKIP_SUBDIRS_VAR_NAME = 'skip_child_includes'
-
-
-def NormalizePath(path):
-  """Returns a path normalized to how we write DEPS rules and compare paths.
-  """
-  return path.lower().replace('\\', '/')
+from builddeps import DepsBuilder
+from rules import Rule, Rules
 
 
 def _IsTestFile(filename):
@@ -118,8 +32,8 @@ def _IsTestFile(filename):
   return re.match('(test|mock|dummy)_.*|.*_[a-z]*test\.(cc|mm|java)', filename)
 
 
-class DepsChecker(object):
-  """Parses include_rules from DEPS files and can verify files in the
+class DepsChecker(DepsBuilder):
+  """Parses include_rules from DEPS files and erifies files in the
   source tree against them.
   """
 
@@ -135,27 +49,14 @@ class DepsChecker(object):
       base_directory: OS-compatible path to root of checkout, e.g. C:\chr\src.
       verbose: Set to true for debug output.
       being_tested: Set to true to ignore the DEPS file at tools/checkdeps/DEPS.
+      ignore_temp_rules: Ignore rules that start with Rule.TEMP_ALLOW ("!").
     """
-    self.base_directory = base_directory
-    self.verbose = verbose
-    self._under_test = being_tested
-    self._ignore_temp_rules = ignore_temp_rules
-    self._skip_tests = skip_tests
-
-    if not base_directory:
-      self.base_directory = os.path.abspath(
-        os.path.join(os.path.abspath(os.path.dirname(__file__)), '..', '..'))
+    DepsBuilder.__init__(
+        self, base_directory, verbose, being_tested, ignore_temp_rules)
 
+    self._skip_tests = skip_tests
     self.results_formatter = results.NormalResultsFormatter(verbose)
 
-    self.git_source_directories = set()
-    self._AddGitSourceDirectories()
-
-    # Map of normalized directory paths to rules to use for those
-    # directories, or None for directories that should be skipped.
-    self.directory_rules = {}
-    self._ApplyDirectoryRulesAndSkipSubdirs(Rules(), self.base_directory)
-
   def Report(self):
     """Prints a report of results, and returns an exit code for the process."""
     if self.results_formatter.GetResults():
@@ -164,194 +65,6 @@ class DepsChecker(object):
     print '\nSUCCESS\n'
     return 0
 
-  def _ApplyRules(self, existing_rules, includes, specific_includes, cur_dir):
-    """Applies the given include rules, returning the new rules.
-
-    Args:
-      existing_rules: A set of existing rules that will be combined.
-      include: The list of rules from the "include_rules" section of DEPS.
-      specific_includes: E.g. {'.*_unittest\.cc': ['+foo', '-blat']} rules
-                         from the "specific_include_rules" section of DEPS.
-      cur_dir: The current directory, normalized path. We will create an
-               implicit rule that allows inclusion from this directory.
-
-    Returns: A new set of rules combining the existing_rules with the other
-             arguments.
-    """
-    rules = copy.deepcopy(existing_rules)
-
-    # First apply the implicit "allow" rule for the current directory.
-    if cur_dir.startswith(
-          NormalizePath(os.path.normpath(self.base_directory))):
-      relative_dir = cur_dir[len(self.base_directory) + 1:]
-
-      source = relative_dir
-      if len(source) == 0:
-        source = 'top level'  # Make the help string a little more meaningful.
-      rules.AddRule('+' + relative_dir, 'Default rule for ' + source)
-    else:
-      raise Exception('Internal error: base directory is not at the beginning' +
-                      ' for\n  %s and base dir\n  %s' %
-                      (cur_dir, self.base_directory))
-
-    def ApplyOneRule(rule_str, dependee_regexp=None):
-      """Deduces a sensible description for the rule being added, and
-      adds the rule with its description to |rules|.
-
-      If we are ignoring temporary rules, this function does nothing
-      for rules beginning with the Rule.TEMP_ALLOW character.
-      """
-      if self._ignore_temp_rules and rule_str.startswith(Rule.TEMP_ALLOW):
-        return
-
-      rule_block_name = 'include_rules'
-      if dependee_regexp:
-        rule_block_name = 'specific_include_rules'
-      if not relative_dir:
-        rule_description = 'the top level %s' % rule_block_name
-      else:
-        rule_description = relative_dir + "'s %s" % rule_block_name
-      rules.AddRule(rule_str, rule_description, dependee_regexp)
-
-    # Apply the additional explicit rules.
-    for (_, rule_str) in enumerate(includes):
-      ApplyOneRule(rule_str)
-
-    # Finally, apply the specific rules.
-    for regexp, specific_rules in specific_includes.iteritems():
-      for rule_str in specific_rules:
-        ApplyOneRule(rule_str, regexp)
-
-    return rules
-
-  def _ApplyDirectoryRules(self, existing_rules, dir_name):
-    """Combines rules from the existing rules and the new directory.
-
-    Any directory can contain a DEPS file. Toplevel DEPS files can contain
-    module dependencies which are used by gclient. We use these, along with
-    additional include rules and implicit rules for the given directory, to
-    come up with a combined set of rules to apply for the directory.
-
-    Args:
-      existing_rules: The rules for the parent directory. We'll add-on to these.
-      dir_name: The directory name that the deps file may live in (if
-                it exists).  This will also be used to generate the
-                implicit rules.  This is a non-normalized path.
-
-    Returns: A tuple containing: (1) the combined set of rules to apply to the
-             sub-tree, and (2) a list of all subdirectories that should NOT be
-             checked, as specified in the DEPS file (if any).
-    """
-    norm_dir_name = NormalizePath(dir_name)
-
-    # Check for a .svn directory in this directory or check this directory is
-    # contained in git source direcotries. This will tell us if it's a source
-    # directory and should be checked.
-    if not (os.path.exists(os.path.join(dir_name, ".svn")) or
-            (norm_dir_name in self.git_source_directories)):
-      return (None, [])
-
-    # Check the DEPS file in this directory.
-    if self.verbose:
-      print 'Applying rules from', dir_name
-    def FromImpl(_unused, _unused2):
-      pass  # NOP function so "From" doesn't fail.
-
-    def FileImpl(_unused):
-      pass  # NOP function so "File" doesn't fail.
-
-    class _VarImpl:
-      def __init__(self, local_scope):
-        self._local_scope = local_scope
-
-      def Lookup(self, var_name):
-        """Implements the Var syntax."""
-        if var_name in self._local_scope.get('vars', {}):
-          return self._local_scope['vars'][var_name]
-        raise Exception('Var is not defined: %s' % var_name)
-
-    local_scope = {}
-    global_scope = {
-        'File': FileImpl,
-        'From': FromImpl,
-        'Var': _VarImpl(local_scope).Lookup,
-        }
-    deps_file = os.path.join(dir_name, 'DEPS')
-
-    # The second conditional here is to disregard the
-    # tools/checkdeps/DEPS file while running tests.  This DEPS file
-    # has a skip_child_includes for 'testdata' which is necessary for
-    # running production tests, since there are intentional DEPS
-    # violations under the testdata directory.  On the other hand when
-    # running tests, we absolutely need to verify the contents of that
-    # directory to trigger those intended violations and see that they
-    # are handled correctly.
-    if os.path.isfile(deps_file) and (
-        not self._under_test or not os.path.split(dir_name)[1] == 'checkdeps'):
-      execfile(deps_file, global_scope, local_scope)
-    elif self.verbose:
-      print '  No deps file found in', dir_name
-
-    # Even if a DEPS file does not exist we still invoke ApplyRules
-    # to apply the implicit "allow" rule for the current directory
-    include_rules = local_scope.get(INCLUDE_RULES_VAR_NAME, [])
-    specific_include_rules = local_scope.get(SPECIFIC_INCLUDE_RULES_VAR_NAME,
-                                             {})
-    skip_subdirs = local_scope.get(SKIP_SUBDIRS_VAR_NAME, [])
-
-    return (self._ApplyRules(existing_rules, include_rules,
-                             specific_include_rules, norm_dir_name),
-            skip_subdirs)
-
-  def _ApplyDirectoryRulesAndSkipSubdirs(self, parent_rules, dir_path):
-    """Given |parent_rules| and a subdirectory |dir_path| from the
-    directory that owns the |parent_rules|, add |dir_path|'s rules to
-    |self.directory_rules|, and add None entries for any of its
-    subdirectories that should be skipped.
-    """
-    directory_rules, excluded_subdirs = self._ApplyDirectoryRules(parent_rules,
-                                                                  dir_path)
-    self.directory_rules[NormalizePath(dir_path)] = directory_rules
-    for subdir in excluded_subdirs:
-      self.directory_rules[NormalizePath(
-          os.path.normpath(os.path.join(dir_path, subdir)))] = None
-
-  def GetDirectoryRules(self, dir_path):
-    """Returns a Rules object to use for the given directory, or None
-    if the given directory should be skipped.  This takes care of
-    first building rules for parent directories (up to
-    self.base_directory) if needed.
-
-    Args:
-      dir_path: A real (non-normalized) path to the directory you want
-      rules for.
-    """
-    norm_dir_path = NormalizePath(dir_path)
-
-    if not norm_dir_path.startswith(
-        NormalizePath(os.path.normpath(self.base_directory))):
-      dir_path = os.path.join(self.base_directory, dir_path)
-      norm_dir_path = NormalizePath(dir_path)
-
-    parent_dir = os.path.dirname(dir_path)
-    parent_rules = None
-    if not norm_dir_path in self.directory_rules:
-      parent_rules = self.GetDirectoryRules(parent_dir)
-
-    # We need to check for an entry for our dir_path again, in case we
-    # are at a path e.g. A/B/C where A/B/DEPS specifies the C
-    # subdirectory to be skipped; in this case, the invocation to
-    # GetDirectoryRules(parent_dir) has already filled in an entry for
-    # A/B/C.
-    if not norm_dir_path in self.directory_rules:
-      if not parent_rules:
-        # If the parent directory should be skipped, then the current
-        # directory should also be skipped.
-        self.directory_rules[norm_dir_path] = None
-      else:
-        self._ApplyDirectoryRulesAndSkipSubdirs(parent_rules, dir_path)
-    return self.directory_rules[norm_dir_path]
-
   def CheckDirectory(self, start_dir):
     """Checks all relevant source files in the specified directory and
     its subdirectories for compliance with DEPS rules throughout the
@@ -426,24 +139,6 @@ class DepsChecker(object):
               problems.append((file_path, rule_type, violation_text))
     return problems
 
-  def _AddGitSourceDirectories(self):
-    """Adds any directories containing sources managed by git to
-    self.git_source_directories.
-    """
-    if not os.path.exists(os.path.join(self.base_directory, '.git')):
-      return
-
-    popen_out = os.popen('cd %s && git ls-files --full-name .' %
-                         subprocess.list2cmdline([self.base_directory]))
-    for line in popen_out.readlines():
-      dir_name = os.path.join(self.base_directory, os.path.dirname(line))
-      # Add the directory as well as all the parent directories. Use
-      # forward slashes and lower case to normalize paths.
-      while dir_name != self.base_directory:
-        self.git_source_directories.add(NormalizePath(dir_name))
-        dir_name = os.path.dirname(dir_name)
-    self.git_source_directories.add(NormalizePath(self.base_directory))
-
 
 def PrintUsage():
   print """Usage: python checkdeps.py [--root <root>] [tocheck]
diff --git a/tools/checkdeps/graphdeps.py b/tools/checkdeps/graphdeps.py
new file mode 100755
index 0000000..6008f1c
--- /dev/null
+++ b/tools/checkdeps/graphdeps.py
@@ -0,0 +1,403 @@
+#!/usr/bin/env python
+# Copyright 2013 The Chromium Authors. All rights reserved.
+# Use of this source code is governed by a BSD-style license that can be
+# found in the LICENSE file.
+
+"""Dumps a graph of allowed and disallowed inter-module dependencies described
+by the DEPS files in the source tree. Supports DOT and PNG as the output format.
+
+Enables filtering and differential highlighting of parts of the graph based on
+the specified criteria. This allows for a much easier visual analysis of the
+dependencies, including answering questions such as "if a new source must
+depend on modules A, B, and C, what valid options among the existing modules
+are there to put it in."
+
+See builddeps.py for a detailed description of the DEPS format.
+"""
+
+import os
+import optparse
+import pipes
+import re
+import sys
+
+from builddeps import DepsBuilder
+from rules import Rule
+
+
+class DepsGrapher(DepsBuilder):
+  """Parses include_rules from DEPS files and outputs a DOT graph of the
+  allowed and disallowed dependencies between directories and specific file
+  regexps. Can generate only a subgraph of the whole dependency graph
+  corresponding to the provided inclusion and exclusion regexp filters.
+  Also can highlight fanins and/or fanouts of certain nodes matching the
+  provided regexp patterns.
+  """
+
+  def __init__(self,
+               base_directory,
+               verbose,
+               being_tested,
+               ignore_temp_rules,
+               ignore_specific_rules,
+               hide_disallowed_deps,
+               out_file,
+               out_format,
+               layout_engine,
+               unflatten_graph,
+               incl,
+               excl,
+               hilite_fanins,
+               hilite_fanouts):
+    """Creates a new DepsGrapher.
+
+    Args:
+      base_directory: OS-compatible path to root of checkout, e.g. C:\chr\src.
+      verbose: Set to true for debug output.
+      being_tested: Set to true to ignore the DEPS file at tools/graphdeps/DEPS.
+      ignore_temp_rules: Ignore rules that start with Rule.TEMP_ALLOW ("!").
+      ignore_specific_rules: Ignore rules from specific_include_rules sections.
+      hide_disallowed_deps: Hide disallowed dependencies from the output graph.
+      out_file: Output file name.
+      out_format: Output format (anything GraphViz dot's -T option supports).
+      layout_engine: Layout engine for formats other than 'dot'
+                     (anything that GraphViz dot's -K option supports).
+      unflatten_graph: Try to reformat the output graph so it is narrower and
+                       taller. Helps fight overly flat and wide graphs, but
+                       sometimes produces a worse result.
+      incl: Include only nodes matching this regexp; such nodes' fanin/fanout
+            is also included.
+      excl: Exclude nodes matching this regexp; such nodes' fanin/fanout is
+            processed independently.
+      hilite_fanins: Highlight fanins of nodes matching this regexp with a
+                     different edge and node color.
+      hilite_fanouts: Highlight fanouts of nodes matching this regexp with a
+                      different edge and node color.
+    """
+    DepsBuilder.__init__(
+        self,
+        base_directory,
+        verbose,
+        being_tested,
+        ignore_temp_rules,
+        ignore_specific_rules)
+
+    self.ignore_temp_rules = ignore_temp_rules
+    self.ignore_specific_rules = ignore_specific_rules
+    self.hide_disallowed_deps = hide_disallowed_deps
+    self.out_file = out_file
+    self.out_format = out_format
+    self.layout_engine = layout_engine
+    self.unflatten_graph = unflatten_graph
+    self.incl = incl
+    self.excl = excl
+    self.hilite_fanins = hilite_fanins
+    self.hilite_fanouts = hilite_fanouts
+
+    self.deps = set()
+
+  def DumpDependencies(self):
+    """ Builds a dependency rule table and dumps the corresponding dependency
+    graph to all requested formats."""
+    self._BuildDepsGraph(self.base_directory)
+    self._DumpDependencies()
+
+  def _BuildDepsGraph(self, full_path):
+    """Recursively traverses the source tree starting at the specified directory
+    and builds a dependency graph representation in self.deps."""
+    rel_path = os.path.relpath(full_path, self.base_directory)
+    #if re.search(self.incl, rel_path) and not re.search(self.excl, rel_path):
+    rules = self.GetDirectoryRules(full_path)
+    if rules:
+      deps = rules.AsDependencyTuples(
+          include_general_rules=True,
+          include_specific_rules=not self.ignore_specific_rules)
+      self.deps.update(deps)
+
+    for item in os.listdir(full_path):
+      next_full_path = os.path.join(full_path, item)
+      if os.path.isdir(next_full_path):
+        self._BuildDepsGraph(next_full_path)
+
+  def _DumpDependencies(self):
+    """Dumps the built dependency graph to the specified file with specified
+    format."""
+    if self.out_format == 'dot' and not self.layout_engine:
+      if self.unflatten_graph:
+        pipe = pipes.Template()
+        pipe.append('unflatten -l 2 -c 3', '--')
+        out = pipe.open(self.out_file, 'w')
+      else:
+        out = open(self.out_file, 'w')
+    else:
+      pipe = pipes.Template()
+      if self.unflatten_graph:
+        pipe.append('unflatten -l 2 -c 3', '--')
+      dot_cmd = 'dot -T' + self.out_format
+      if self.layout_engine:
+        dot_cmd += ' -K' + self.layout_engine
+      pipe.append(dot_cmd, '--')
+      out = pipe.open(self.out_file, 'w')
+
+    self._DumpDependenciesImpl(self.deps, out)
+    out.close()
+
+  def _DumpDependenciesImpl(self, deps, out):
+    """Computes nodes' and edges' properties for the dependency graph |deps| and
+    carries out the actual dumping to a file/pipe |out|."""
+    deps_graph = dict()
+    deps_srcs = set()
+
+    # Pre-initialize the graph with src->(dst, allow) pairs.
+    for (allow, src, dst) in deps:
+      if allow == Rule.TEMP_ALLOW and self.ignore_temp_rules:
+        continue
+
+      deps_srcs.add(src)
+      if src not in deps_graph:
+        deps_graph[src] = []
+      deps_graph[src].append((dst, allow))
+
+      # Add all hierarchical parents too, in case some of them don't have their
+      # own DEPS, and therefore are missing from the list of rules. Those will
+      # be recursively populated with their parents' rules in the next block.
+      parent_src = os.path.dirname(src)
+      while parent_src:
+        if parent_src not in deps_graph:
+          deps_graph[parent_src] = []
+        parent_src = os.path.dirname(parent_src)
+
+    # For every node, propagate its rules down to all its children.
+    deps_srcs = list(deps_srcs)
+    deps_srcs.sort()
+    for src in deps_srcs:
+      parent_src = os.path.dirname(src)
+      if parent_src:
+        # We presort the list, so parents are guaranteed to precede children.
+        assert parent_src in deps_graph,\
+               "src: %s, parent_src: %s" % (src, parent_src)
+        for (dst, allow) in deps_graph[parent_src]:
+          # Check that this node does not explicitly override a rule from the
+          # parent that we're about to add.
+          if ((dst, Rule.ALLOW) not in deps_graph[src]) and \
+             ((dst, Rule.TEMP_ALLOW) not in deps_graph[src]) and \
+             ((dst, Rule.DISALLOW) not in deps_graph[src]):
+            deps_graph[src].append((dst, allow))
+
+    node_props = {}
+    edges = []
+
+    # 1) Populate a list of edge specifications in DOT format;
+    # 2) Populate a list of computed raw node attributes to be output as node
+    #    specifications in DOT format later on.
+    # Edges and nodes are emphasized with color and line/border weight depending
+    # on how many of incl/excl/hilite_fanins/hilite_fanouts filters they hit,
+    # and in what way.
+    for src in deps_graph.keys():
+      for (dst, allow) in deps_graph[src]:
+        if allow == Rule.DISALLOW and self.hide_disallowed_deps:
+          continue
+
+        if allow == Rule.ALLOW and src == dst:
+          continue
+
+        edge_spec = "%s->%s" % (src, dst)
+        if not re.search(self.incl, edge_spec) or \
+               re.search(self.excl, edge_spec):
+          continue
+
+        if src not in node_props:
+          node_props[src] = {'hilite': None, 'degree': 0}
+        if dst not in node_props:
+          node_props[dst] = {'hilite': None, 'degree': 0}
+
+        edge_weight = 1
+
+        if self.hilite_fanouts and re.search(self.hilite_fanouts, src):
+          node_props[src]['hilite'] = 'lightgreen'
+          node_props[dst]['hilite'] = 'lightblue'
+          node_props[dst]['degree'] += 1
+          edge_weight += 1
+
+        if self.hilite_fanins and re.search(self.hilite_fanins, dst):
+          node_props[src]['hilite'] = 'lightblue'
+          node_props[dst]['hilite'] = 'lightgreen'
+          node_props[src]['degree'] += 1
+          edge_weight += 1
+
+        if allow == Rule.ALLOW:
+          edge_color = (edge_weight > 1) and 'blue' or 'green'
+          edge_style = 'solid'
+        elif allow == Rule.TEMP_ALLOW:
+          edge_color = (edge_weight > 1) and 'blue' or 'green'
+          edge_style = 'dashed'
+        else:
+          edge_color = 'red'
+          edge_style = 'dashed'
+        edges.append('    "%s" -> "%s" [style=%s,color=%s,penwidth=%d];' % \
+            (src, dst, edge_style, edge_color, edge_weight))
+
+    # Reformat the computed raw node attributes into a final DOT representation.
+    nodes = []
+    for (node, attrs) in node_props.iteritems():
+      attr_strs = []
+      if attrs['hilite']:
+        attr_strs.append('style=filled,fillcolor=%s' % attrs['hilite'])
+      attr_strs.append('penwidth=%d' % (attrs['degree'] or 1))
+      nodes.append('    "%s" [%s];' % (node, ','.join(attr_strs)))
+
+    # Output nodes and edges to |out| (can be a file or a pipe).
+    edges.sort()
+    nodes.sort()
+    out.write('digraph DEPS {\n'
+              '    fontsize=8;\n')
+    out.write('\n'.join(nodes))
+    out.write('\n\n')
+    out.write('\n'.join(edges))
+    out.write('\n}\n')
+    out.close()
+
+
+def PrintUsage():
+  print """Usage: python graphdeps.py [--root <root>]
+
+  --root ROOT Specifies the repository root. This defaults to "../../.."
+              relative to the script file. This will be correct given the
+              normal location of the script in "<root>/tools/graphdeps".
+
+  --(others)  There are a few lesser-used options; run with --help to show them.
+
+Examples:
+  Dump the whole dependency graph:
+    graphdeps.py
+  Find a suitable place for a new source that must depend on /apps and
+  /content/browser/renderer_host. Limit potential candidates to /apps,
+  /chrome/browser and content/browser, and descendants of those three.
+  Generate both DOT and PNG output. The output will highlight the fanins
+  of /apps and /content/browser/renderer_host. Nodes belonging to both fanins
+  will be emphasized by a thicker outline. Those nodes are the ones that are
+  allowed to depend on both targets, therefore they are all legal candidates
+  to place our new source in:
+    graphdeps.py \
+      --root=./src \
+      --dot=./DEPS.dot \
+      --png=./DEPS.png \
+      --incl='^(apps|chrome/browser|content/browser)' \
+      --fanin='^(apps|content/browser/renderer_host)$' \
+      --excl='third_party' \
+      --ignore-specific-rules \
+      --ignore-temp-rules"""
+
+
+def main():
+  option_parser = optparse.OptionParser()
+  option_parser.add_option(
+      "", "--root",
+      default="", dest="base_directory",
+      help="Specifies the repository root. This defaults "
+           "to '../../..' relative to the script file, which "
+           "will normally be the repository root.")
+  option_parser.add_option(
+      "-f", "--format",
+      dest="out_format", default="dot",
+      help="Output file format. "
+           "Can be anything that GraphViz dot's -T option supports. "
+           "The most useful ones are: dot (text), svg (image), pdf (image)."
+           "NOTES: dotty has a known problem with fonts when displaying DOT "
+           "files on Ubuntu - if labels are unreadable, try other formats.")
+  option_parser.add_option(
+      "-o", "--out",
+      dest="out_file", default="DEPS",
+      help="Output file name. If the name does not end in an extension "
+           "matching the output format, that extension is automatically "
+           "appended.")
+  option_parser.add_option(
+      "-l", "--layout-engine",
+      dest="layout_engine", default="",
+      help="Layout rendering engine. "
+           "Can be anything that GraphViz dot's -K option supports. "
+           "The most useful are in decreasing order: dot, fdp, circo, osage. "
+           "NOTE: '-f dot' and '-f dot -l dot' are different: the former "
+           "will dump a raw DOT graph and stop; the latter will further "
+           "filter it through 'dot -Tdot -Kdot' layout engine.")
+  option_parser.add_option(
+      "-i", "--incl",
+      default="^.*$", dest="incl",
+      help="Include only dependent nodes that match the specified regexp. "
+           "Such nodes\" fanins and fanouts are also included, "
+           "unless filtered out by --excl.")
+  option_parser.add_option(
+      "-e", "--excl",
+      default="^$", dest="excl",
+      help="Exclude dependent nodes that match the specified regexp. "
+           "Such nodes\" fanins and fanouts are not directly affected.")
+  option_parser.add_option(
+      "", "--fanin",
+      default="", dest="hilite_fanins",
+      help="Highlight fanins of nodes matching the specified regexp.")
+  option_parser.add_option(
+      "", "--fanout",
+      default="", dest="hilite_fanouts",
+      help="Highlight fanouts of nodes matching the specified regexp.")
+  option_parser.add_option(
+      "", "--ignore-temp-rules",
+      action="store_true", dest="ignore_temp_rules", default=False,
+      help="Ignore !-prefixed (temporary) rules in DEPS files.")
+  option_parser.add_option(
+      "", "--ignore-specific-rules",
+      action="store_true", dest="ignore_specific_rules", default=False,
+      help="Ignore specific_include_rules section of DEPS files.")
+  option_parser.add_option(
+      "", "--hide-disallowed-deps",
+      action="store_true", dest="hide_disallowed_deps", default=False,
+      help="Hide disallowed dependencies in the output graph.")
+  option_parser.add_option(
+      "", "--unflatten",
+      action="store_true", dest="unflatten_graph", default=False,
+      help="Try to reformat the output graph so it is narrower and taller. "
+           "Helps fight overly flat and wide graphs, but sometimes produces "
+           "inferior results.")
+  option_parser.add_option(
+      "-v", "--verbose",
+      action="store_true", default=False,
+      help="Print debug logging")
+  options, args = option_parser.parse_args()
+
+  if not options.out_file.endswith(options.out_format):
+    options.out_file += '.' + options.out_format
+
+  deps_grapher = DepsGrapher(
+      base_directory=options.base_directory,
+      verbose=options.verbose,
+      being_tested=False,
+
+      ignore_temp_rules=options.ignore_temp_rules,
+      ignore_specific_rules=options.ignore_specific_rules,
+      hide_disallowed_deps=options.hide_disallowed_deps,
+
+      out_file=options.out_file,
+      out_format=options.out_format,
+      layout_engine=options.layout_engine,
+      unflatten_graph=options.unflatten_graph,
+
+      incl=options.incl,
+      excl=options.excl,
+      hilite_fanins=options.hilite_fanins,
+      hilite_fanouts=options.hilite_fanouts)
+
+  if len(args) > 0:
+    PrintUsage()
+    return 1
+
+  print 'Using base directory: ', deps_grapher.base_directory
+  print 'include nodes       : ', options.incl
+  print 'exclude nodes       : ', options.excl
+  print 'highlight fanins of : ', options.hilite_fanins
+  print 'highlight fanouts of: ', options.hilite_fanouts
+
+  deps_grapher.DumpDependencies()
+  return 0
+
+
+if '__main__' == __name__:
+  sys.exit(main())
diff --git a/tools/checkdeps/rules.py b/tools/checkdeps/rules.py
index 09d718c..b8a07df 100644
--- a/tools/checkdeps/rules.py
+++ b/tools/checkdeps/rules.py
@@ -1,4 +1,4 @@
-# Copyright (c) 2012 The Chromium Authors. All rights reserved.
+# Copyright 2012 The Chromium Authors. All rights reserved.
 # Use of this source code is governed by a BSD-style license that can be
 # found in the LICENSE file.
 
@@ -21,14 +21,22 @@ class Rule(object):
   DISALLOW = '-'
   TEMP_ALLOW = '!'
 
-  def __init__(self, allow, directory, source):
+  def __init__(self, allow, directory, dependent_directory, source):
     self.allow = allow
     self._dir = directory
+    self._dependent_dir = dependent_directory
     self._source = source
 
   def __str__(self):
     return '"%s%s" from %s.' % (self.allow, self._dir, self._source)
 
+  def AsDependencyTuple(self):
+    """Returns a tuple (allow, dependent dir, dependee dir) for this rule,
+    which is fully self-sufficient to answer the question whether the dependent
+    is allowed to depend on the dependee, without knowing the external
+    context."""
+    return (self.allow, self._dependent_dir or '.', self._dir or '.')
+
   def ParentOrMatch(self, other):
     """Returns true if the input string is an exact match or is a parent
     of the current rule. For example, the input "foo" would match "foo/bar"."""
@@ -46,7 +54,7 @@ class MessageRule(Rule):
   """
 
   def __init__(self, reason):
-    super(MessageRule, self).__init__(Rule.DISALLOW, '', '')
+    super(MessageRule, self).__init__(Rule.DISALLOW, '', '', '')
     self._reason = reason
 
   def __str__(self):
@@ -102,13 +110,32 @@ class Rules(object):
     result.append('  }')
     return '\n'.join(result)
 
-  def AddRule(self, rule_string, source, dependee_regexp=None):
+  def AsDependencyTuples(self, include_general_rules, include_specific_rules):
+    """Returns a list of tuples (allow, dependent dir, dependee dir) for the
+    specified rules (general/specific). Currently only general rules are
+    supported."""
+    def AddDependencyTuplesImpl(deps, rules, extra_dependent_suffix=""):
+      for rule in rules:
+        (allow, dependent, dependee) = rule.AsDependencyTuple()
+        tup = (allow, dependent + extra_dependent_suffix, dependee)
+        deps.add(tup)
+
+    deps = set()
+    if include_general_rules:
+      AddDependencyTuplesImpl(deps, self._general_rules)
+    if include_specific_rules:
+      for regexp, rules in self._specific_rules.iteritems():
+        AddDependencyTuplesImpl(deps, rules, "/" + regexp)
+    return deps
+
+  def AddRule(self, rule_string, dependent_dir, source, dependee_regexp=None):
     """Adds a rule for the given rule string.
 
     Args:
       rule_string: The include_rule string read from the DEPS file to apply.
       source: A string representing the location of that string (filename, etc.)
               so that we can give meaningful errors.
+      dependent_dir: The directory to which this rule applies.
       dependee_regexp: The rule will only be applied to dependee files
                        whose filename (last component of their path)
                        matches the expression. None to match all
@@ -128,7 +155,7 @@ class Rules(object):
     # passed "foo", we should remove "foo", "foo/bar", but not "foobar".
     rules_to_update = [x for x in rules_to_update
                        if not x.ParentOrMatch(rule_dir)]
-    rules_to_update.insert(0, Rule(rule_type, rule_dir, source))
+    rules_to_update.insert(0, Rule(rule_type, rule_dir, dependent_dir, source))
 
     if not dependee_regexp:
       self._general_rules = rules_to_update