Add script to mass add a new #include.

tools/clang/pass_to_move/add_header.py

Index: tools/clang/pass_to_move/add_header.py
diff --git a/tools/clang/pass_to_move/add_header.py b/tools/clang/pass_to_move/add_header.py
new file mode 100755
index 0000000000000000000000000000000000000000..08f75c5ebb4508570e951f9669452e25c99ee17e
--- /dev/null
+++ b/tools/clang/pass_to_move/add_header.py
@@ -0,0 +1,318 @@
+#!/usr/bin/env python
+# Copyright 2015 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.
+
+import argparse
+import collections
+import difflib
+import os.path
+import re
+import sys
+
+_HEADER_TYPE_C_SYSTEM = 0
+_HEADER_TYPE_CXX_SYSTEM = 1
+_HEADER_TYPE_USER = 2
+_HEADER_TYPE_INVALID = -1
+
+
+def ClassifyHeader(decorated_name):
+  if IsCSystemHeader(decorated_name):
+    return _HEADER_TYPE_C_SYSTEM
+  elif IsCXXSystemHeader(decorated_name):
+    return _HEADER_TYPE_CXX_SYSTEM
+  elif IsUserHeader(decorated_name):
+    return _HEADER_TYPE_USER
+  else:
+    return _HEADER_TYPE_INVALID
+
+
+def UndecoratedName(decorated_name):
+  return decorated_name[1:-1]
+
+
+def IsSystemHeader(decorated_name):
+  return decorated_name[0] == '<' and decorated_name[-1] == '>'
+
+
+def IsCSystemHeader(decorated_name):
+  return IsSystemHeader(decorated_name) and UndecoratedName(
+      decorated_name).endswith('.h')
+
+
+def IsCXXSystemHeader(decorated_name):
+  return IsSystemHeader(decorated_name) and not UndecoratedName(
+      decorated_name).endswith('.h')
+
+
+def IsUserHeader(decorated_name):
+  return decorated_name[0] == '"' and decorated_name[-1] == '"'
+
+
+_EMPTY_LINE_RE = re.compile(r'\s*$')
+_COMMENT_RE = re.compile(r'\s*//(.*)$')
+_INCLUDE_RE = re.compile(
+    r'\s*#(import|include)\s+([<"].+?[">])\s*?(?://(.*))?$')
+
+
+def FindIncludes(lines):
+  """Finds the block of #includes, assuming Google+Chrome C++ style source.
+
+  Returns:
+    begin, end: The begin and end indices of the #include block, respectively.
+        If no #include block is found, the returned indices will be negative.
+  """
+  begin = end = -1
+  for idx, line in enumerate(lines):
+    # TODO(dcheng): #define and #undef should probably also be allowed.
+    if _EMPTY_LINE_RE.match(line) or _COMMENT_RE.match(line):
+      continue
+    m = _INCLUDE_RE.match(line)
+    if not m:
+      if begin < 0:
+        # No match, but no #includes have been seen yet. Keep scanning for the
+        # first #include.
+        continue
+      break
+
+    if begin < 0:
+      begin = idx
+    end = idx + 1
+  return begin, end
+
+
+class Include(object):
+  """Represents an #include and any interesting things associated with it."""
+
+  def __init__(self, decorated_name, directive, preamble, inline_comment):
+    self.decorated_name = decorated_name
+    self.directive = directive
+    self.preamble = preamble
+    self.inline_comment = inline_comment
+    self.header_type = ClassifyHeader(decorated_name)
+    assert self.header_type != _HEADER_TYPE_INVALID
+    self.is_primary_header = False
+
+  def __repr__(self):
+    return str((self.decorated_name, self.directive, self.preamble,
+                self.inline_comment, self.header_type, self.is_primary_header))
+
+  def ShouldInsertNewline(self, previous_include):
+    return (self.is_primary_header != previous_include.is_primary_header or
+            self.header_type != previous_include.header_type)
+
+  def ToSource(self):
+    source = []
+    source.extend(self.preamble)
+    include_line = '#%s %s' % (self.directive, self.decorated_name)
+    if self.inline_comment:
+      include_line = include_line + '  //' + self.inline_comment
+    source.append(include_line)
+    return [line.rstrip() for line in source]
+
+
+def ParseIncludes(lines):
+  """Parses lines into a list of Include objects. Returns None on failure.
+
+  Args:
+    lines: A list of strings representing C++ source code.
+  """
+  includes = []
+  preamble = []
+  for line in lines:
+    if _EMPTY_LINE_RE.match(line):
+      if preamble:
+        # preamble contents are flushed when an #include directive is matched.
+        # If preamble is non-empty, that means there is a preamble separated
+        # from its #include directive by at least one newline. Just give up,
+        # since the sorter has no idea how to preserve structure in this case.
+        return
+      continue
+    m = _INCLUDE_RE.match(line)
+    if not m:
+      preamble.append(line)
+      continue
+    includes.append(Include(m.group(2), m.group(1), preamble, m.group(3)))
+    preamble = []
+  if preamble:
+    return
+  return includes
+
+
+def _DecomposePath(filename):
+  """Decomposes a filename into a list of directories and the basename."""
+  dirs = []
+  dirname, basename = os.path.split(filename)
+  while dirname:
+    dirname, last = os.path.split(dirname)
+    dirs.append(last)
+  dirs.reverse()
+  # Remove the extension from the basename.
+  basename = os.path.splitext(basename)[0]
+  return dirs, basename
+
+
+def MarkPrimaryInclude(includes, filename):
+  """Finds the primary header in includes and marks it as such.
+
+  Per the style guide, if moo.cc's main purpose is to implement or test the
+  functionality in moo.h, moo.h should be ordered first in the includes.
+
+  Args:
+    includes: A list of Include objects.
+    filename: The filename to use as the basis for finding the primary header.
+  """
+  # Header files never have a primary include.
+  if filename.endswith('.h'):
+    return
+
+  basis = _DecomposePath(filename)
+  PLATFORM_SUFFIX = \
+      r'(?:_(?:android|aura|chromeos|ios|linux|mac|ozone|posix|win|x11))?'
+  TEST_SUFFIX = \
+      r'(?:_(?:browser|interactive_ui|ui|unit)?test)?'
+
+  # The list of includes is searched in reverse order of length. Even though
+  # matching is fuzzy, moo_posix.h should take precedence over moo.h when
+  # considering moo_posix.cc.
+  includes.sort(key=lambda i: -len(i.decorated_name))
+  for include in includes:
+    if include.header_type != _HEADER_TYPE_USER:
+      continue
+    to_test = _DecomposePath(UndecoratedName(include.decorated_name))
+
+    # If the basename to test is longer than the basis, just skip it and
+    # continue. moo.c should never match against moo_posix.h.
+    if len(to_test[1]) > len(basis[1]):
+      continue
+
+    # The basename in the two paths being compared need to fuzzily match.
+    # This allows for situations where moo_posix.cc implements the interfaces
+    # defined in moo.h.
+    escaped_basename = re.escape(to_test[1])
+    if not (re.match(escaped_basename + PLATFORM_SUFFIX + TEST_SUFFIX + '$',
+                     basis[1]) or
+            re.match(escaped_basename + TEST_SUFFIX + PLATFORM_SUFFIX + '$',
+                     basis[1])):
+      continue
+
+    # The topmost directory name must match, and the rest of the directory path
+    # should be 'substantially similar'.
+    s = difflib.SequenceMatcher(None, to_test[0], basis[0])
+    first_matched = False
+    total_matched = 0
+    for match in s.get_matching_blocks():
+      if total_matched == 0 and match.a == 0 and match.b == 0:
+        first_matched = True
+      total_matched += match.size
+
+    if not first_matched:
+      continue
+
+    # 'Substantially similar' is defined to be:
+    # - no more than two differences
+    # - at least one match besides the topmost directory
+    total_differences = abs(total_matched - len(to_test[0])) + abs(
+        total_matched - len(basis[0]))
+    # Note: total_differences != 0 is mainly intended to allow more succint
+    # tests (otherwise tests with just a basename would always trip the
+    # total_matched < 2 check).
+    if total_differences != 0 and (total_differences > 2 or total_matched < 2):
+      continue
+
+    include.is_primary_header = True
+    return
+
+
+def SerializeIncludes(includes):
+  """Turns includes back into the corresponding C++ source code.
+
+  This function assumes that the list of input Include objects is already sorted
+  according to Google style.
+
+  Args:
+    includes: a list of Include objects.
+
+  Returns:
+    A list of strings representing C++ source code.
+  """
+  source = []
+
+  # Assume there's always at least one include.
+  previous_include = None
+  for include in includes:
+    if previous_include and include.ShouldInsertNewline(previous_include):
+      source.append('')
+    source.extend(include.ToSource())
+    previous_include = include
+  return source
+
+
+def InsertHeaderIntoSource(filename, source, decorated_name):
+  """Inserts the specified header into some source text, if needed.
+
+  Args:
+    filename: The name of the source file.
+    source: A string containing the contents of the source file.
+    decorated_name: The decorated name of the header to insert.
+
+  Returns:
+    None on failure or the modified source text on success.
+  """
+  lines = source.splitlines()
+  begin, end = FindIncludes(lines)
+
+  # No #includes in this file. Just give up.
+  # TODO(dcheng): Be more clever and insert it after the file-level comment or
+  # include guard as appropriate.
+  if begin < 0:
+    return
+
+  includes = ParseIncludes(lines[begin:end])
+  if not includes:
+    return
+  if decorated_name in [i.decorated_name for i in includes]:
+    # Nothing to do.
+    return source
+  MarkPrimaryInclude(includes, filename)
+  includes.append(Include(decorated_name, 'include', [], None))
+
+  def SortKey(include):
+    return (not include.is_primary_header, include.header_type,
+            include.decorated_name)
+
+  includes.sort(key=SortKey)
+  lines[begin:end] = SerializeIncludes(includes)
+  lines.append('')  # To avoid eating the newline at the end of the file.
+  return '\n'.join(lines)
+
+
+def main():
+  parser = argparse.ArgumentParser(
+      description='Mass insert a new header into a bunch of files.')
+  parser.add_argument(
+      '--header',
+      help='The decorated filename of the header to insert (e.g. "a" or <a>)',
+      required=True)
+  parser.add_argument('files', nargs='+')
+  args = parser.parse_args()
+  if ClassifyHeader(args.header) == _HEADER_TYPE_INVALID:
+    print '--header argument must be a decorated filename, e.g.'
+    print '  --header "<utility>"'
+    print 'or'
+    print '  --header \'"moo.h"\''
+    return 1
+  print 'Inserting #include %s...' % args.header
+  for filename in args.files:
+    with file(filename, 'r') as f:
+      new_source = InsertHeaderIntoSource(
+          os.path.normpath(filename), f.read(), args.header)
+    if not new_source:
+      print 'Failed to process file: %s' % filename
+      continue
+    with file(filename, 'w') as f:
+      f.write(new_source)
+
+
+if __name__ == '__main__':
+  sys.exit(main())