Sort include entries.

PRESUBMIT.py

Index: PRESUBMIT.py
diff --git a/PRESUBMIT.py b/PRESUBMIT.py
index 111abb03b0dfdaa9500b66a287ec997a6da0d16c..0f936979877702f33bce811d091149f03586f88f 100644
--- a/PRESUBMIT.py
+++ b/PRESUBMIT.py
@@ -34,6 +34,12 @@ LINT_FILTERS = [
 ]
 
 
+_INCLUDE_ORDER_WARNING = (
+    'Your #include order seems to be broken. Remember to use the right '
+    'collation (LC_COLLATE=C) and check\nhttps://google.github.io/styleguide/'
+    'cppguide.html#Names_and_Order_of_Includes')
+
+
 def _CheckUnwantedDependencies(input_api, output_api):
   """Runs checkdeps on #include statements added in this
   change. Breaking - rules is an error, breaking ! rules is a
@@ -91,11 +97,171 @@ def _CheckUnwantedDependencies(input_api, output_api):
   return results
 
 
+def _CheckIncludeOrderForScope(scope, input_api, file_path, changed_linenums):
+  """Checks that the lines in scope occur in the right order.
+
+  1. C system files in alphabetical order
+  2. C++ system files in alphabetical order
+  3. Project's .h files
+  """
+
+  c_system_include_pattern = input_api.re.compile(r'\s*#include <.*\.h>')
+  cpp_system_include_pattern = input_api.re.compile(r'\s*#include <.*>')
+  custom_include_pattern = input_api.re.compile(r'\s*#include ".*')
+
+  C_SYSTEM_INCLUDES, CPP_SYSTEM_INCLUDES, CUSTOM_INCLUDES = range(3)
+
+  state = C_SYSTEM_INCLUDES
+
+  previous_line = ''
+  previous_line_num = 0
+  problem_linenums = []
+  out_of_order = " - line belongs before previous line"
+  for line_num, line in scope:
+    if c_system_include_pattern.match(line):
+      if state != C_SYSTEM_INCLUDES:
+        problem_linenums.append((line_num, previous_line_num,
+            " - C system include file in wrong block"))
+      elif previous_line and previous_line > line:
+        problem_linenums.append((line_num, previous_line_num,
+            out_of_order))
+    elif cpp_system_include_pattern.match(line):
+      if state == C_SYSTEM_INCLUDES:
+        state = CPP_SYSTEM_INCLUDES
+      elif state == CUSTOM_INCLUDES:
+        problem_linenums.append((line_num, previous_line_num,
+            " - c++ system include file in wrong block"))
+      elif previous_line and previous_line > line:
+        problem_linenums.append((line_num, previous_line_num, out_of_order))
+    elif custom_include_pattern.match(line):
+      if state != CUSTOM_INCLUDES:
+        state = CUSTOM_INCLUDES
+      elif previous_line and previous_line > line:
+        problem_linenums.append((line_num, previous_line_num, out_of_order))
+    else:
+      problem_linenums.append((line_num, previous_line_num,
+          "Unknown include type"))
+    previous_line = line
+    previous_line_num = line_num
+
+  warnings = []
+  for (line_num, previous_line_num, failure_type) in problem_linenums:
+    if line_num in changed_linenums or previous_line_num in changed_linenums:
+      warnings.append('    %s:%d:%s' % (file_path, line_num, failure_type))
+  return warnings
+
+
+def _CheckIncludeOrderInFile(input_api, f, changed_linenums):
+  """Checks the #include order for the given file f."""
+
+  system_include_pattern = input_api.re.compile(r'\s*#include \<.*')
+  # Exclude the following includes from the check:
+  # 1) #include <.../...>, e.g., <sys/...> includes often need to appear in a
+  # specific order.
+  # 2) <atlbase.h>, "build/build_config.h"
+  excluded_include_pattern = input_api.re.compile(
+      r'\s*#include (\<.*/.*|\<atlbase\.h\>|"build/build_config.h")')
+  custom_include_pattern = input_api.re.compile(r'\s*#include "(?P<FILE>.*)"')
+  # Match the final or penultimate token if it is xxxtest so we can ignore it
+  # when considering the special first include.
+  test_file_tag_pattern = input_api.re.compile(
+    r'_[a-z]+test(?=(_[a-zA-Z0-9]+)?\.)')
+  if_pattern = input_api.re.compile(
+      r'\s*#\s*(if|elif|else|endif|define|undef).*')
+  # Some files need specialized order of includes; exclude such files from this
+  # check.
+  uncheckable_includes_pattern = input_api.re.compile(
+      r'\s*#include '
+      '("ipc/.*macros\.h"|<windows\.h>|".*gl.*autogen.h")\s*')
+
+  contents = f.NewContents()
+  warnings = []
+  line_num = 0
+
+  # Handle the special first include. If the first include file is
+  # some/path/file.h, the corresponding including file can be some/path/file.cc,
+  # some/other/path/file.cc, some/path/file_platform.cc, some/path/file-suffix.h
+  # etc. It's also possible that no special first include exists.
+  # If the included file is some/path/file_platform.h the including file could
+  # also be some/path/file_xxxtest_platform.h.
+  including_file_base_name = test_file_tag_pattern.sub(
+    '', input_api.os_path.basename(f.LocalPath()))
+
+  for line in contents:
+    line_num += 1
+    if system_include_pattern.match(line):
+      # No special first include -> process the line again along with normal
+      # includes.
+      line_num -= 1
+      break
+    match = custom_include_pattern.match(line)
+    if match:
+      match_dict = match.groupdict()
+      header_basename = test_file_tag_pattern.sub(
+        '', input_api.os_path.basename(match_dict['FILE'])).replace('.h', '')
+
+      if header_basename not in including_file_base_name:
+        # No special first include -> process the line again along with normal
+        # includes.
+        line_num -= 1
+      break
+
+  # Split into scopes: Each region between #if and #endif is its own scope.
+  scopes = []
+  current_scope = []
+  for line in contents[line_num:]:
+    line_num += 1
+    if uncheckable_includes_pattern.match(line):
+      continue
+    if if_pattern.match(line):
+      scopes.append(current_scope)
+      current_scope = []
+    elif ((system_include_pattern.match(line) or
+           custom_include_pattern.match(line)) and
+          not excluded_include_pattern.match(line)):
+      current_scope.append((line_num, line))
+  scopes.append(current_scope)
+
+  for scope in scopes:
+    warnings.extend(_CheckIncludeOrderForScope(scope, input_api, f.LocalPath(),
+                                               changed_linenums))
+  return warnings
+
+
+def _CheckIncludeOrder(input_api, output_api):
+  """Checks that the #include order is correct.
+
+  1. The corresponding header for source files.
+  2. C system files in alphabetical order
+  3. C++ system files in alphabetical order
+  4. Project's .h files in alphabetical order
+
+  Each region separated by #if, #elif, #else, #endif, #define and #undef follows
+  these rules separately.
+  """
+  def FileFilterIncludeOrder(affected_file):
+    black_list = (input_api.DEFAULT_BLACK_LIST)
+    return input_api.FilterSourceFile(affected_file, black_list=black_list)
+
+  warnings = []
+  for f in input_api.AffectedFiles(file_filter=FileFilterIncludeOrder):
+    if f.LocalPath().endswith(('.cc', '.h', '.mm')):
+      changed_linenums = set(line_num for line_num, _ in f.ChangedContents())
+      warnings.extend(_CheckIncludeOrderInFile(input_api, f, changed_linenums))
+
+  results = []
+  if warnings:
+    results.append(output_api.PresubmitPromptOrNotify(_INCLUDE_ORDER_WARNING,
+                                                      warnings))
+  return results
+
+
 def CheckChangeOnUpload(input_api, output_api):
   results = []
   results += _CheckUnwantedDependencies(input_api, output_api)
   results += input_api.canned_checks.CheckPatchFormatted(input_api, output_api)
   results += input_api.canned_checks.CheckChangeLintsClean(
       input_api, output_api, None, LINT_FILTERS)
+  results += _CheckIncludeOrder(input_api, output_api)
 
   return results