[clang-tidy] Implement the include order checker for LLVM.

There are still a couple of rough edges in here but it is working fine
on LLVM and generates the same results as sort_includes.py if there are
no blank lines involved.

Differential Revision: http://reviews.llvm.org/D4741

llvm-svn: 215152

13 files changed, 169 insertions, 10 deletions

diff --git a/clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp b/clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp
index de4f650a33c..2060a4d0613 100644
--- a/clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp
+++ b/clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp
@@ -18,26 +18,147 @@ namespace tidy {
 namespace {
 class IncludeOrderPPCallbacks : public PPCallbacks {
 public:
-  explicit IncludeOrderPPCallbacks(IncludeOrderCheck &Check) : Check(Check) {}
+  explicit IncludeOrderPPCallbacks(ClangTidyCheck &Check, SourceManager &SM)
+      : LookForMainModule(true), Check(Check), SM(SM) {}
 
   void InclusionDirective(SourceLocation HashLoc, const Token &IncludeTok,
                           StringRef FileName, bool IsAngled,
                           CharSourceRange FilenameRange, const FileEntry *File,
                           StringRef SearchPath, StringRef RelativePath,
-                          const Module *Imported) override {
-    // FIXME: This is a dummy implementation to show how to get at preprocessor
-    // information. Implement a real include order check.
-    Check.diag(HashLoc, "This is an include");
-  }
+                          const Module *Imported) override;
+  void EndOfMainFile() override;
 
 private:
-  IncludeOrderCheck &Check;
+  struct IncludeDirective {
+    SourceLocation Loc;    ///< '#' location in the include directive
+    CharSourceRange Range; ///< SourceRange for the file name
+    StringRef Filename;    ///< Filename as a string
+    bool IsAngled;         ///< true if this was an include with angle brackets
+    bool IsMainModule;     ///< true if this was the first include in a file
+  };
+  std::vector<IncludeDirective> IncludeDirectives;
+  bool LookForMainModule;
+
+  ClangTidyCheck &Check;
+  SourceManager &SM;
 };
 } // namespace
 
 void IncludeOrderCheck::registerPPCallbacks(CompilerInstance &Compiler) {
-  Compiler.getPreprocessor()
-      .addPPCallbacks(new IncludeOrderPPCallbacks(*this));
+  Compiler.getPreprocessor().addPPCallbacks(
+      new IncludeOrderPPCallbacks(*this, Compiler.getSourceManager()));
+}
+
+static int getPriority(StringRef Filename, bool IsAngled, bool IsMainModule) {
+  // We leave the main module header at the top.
+  if (IsMainModule)
+    return 0;
+
+  // LLVM and clang headers are in the penultimate position.
+  if (Filename.startswith("llvm/") || Filename.startswith("llvm-c/") ||
+      Filename.startswith("clang/") || Filename.startswith("clang-c/"))
+    return 2;
+
+  // System headers are sorted to the end.
+  if (IsAngled || Filename.startswith("gtest/"))
+    return 3;
+
+  // Other headers are inserted between the main module header and LLVM headers.
+  return 1;
+}
+
+void IncludeOrderPPCallbacks::InclusionDirective(
+    SourceLocation HashLoc, const Token &IncludeTok, StringRef FileName,
+    bool IsAngled, CharSourceRange FilenameRange, const FileEntry *File,
+    StringRef SearchPath, StringRef RelativePath, const Module *Imported) {
+  // We recognize the first include as a special main module header and want
+  // to leave it in the top position.
+  IncludeDirective ID = {HashLoc, FilenameRange, FileName, IsAngled, false};
+  if (LookForMainModule && !IsAngled) {
+    ID.IsMainModule = true;
+    LookForMainModule = false;
+  }
+  IncludeDirectives.push_back(std::move(ID));
+}
+
+void IncludeOrderPPCallbacks::EndOfMainFile() {
+  LookForMainModule = true;
+  if (IncludeDirectives.empty())
+    return;
+
+  // TODO: find duplicated includes.
+
+  // Form blocks of includes. We don't want to sort across blocks. This also
+  // implicitly makes us never reorder over #defines or #if directives.
+  // FIXME: We should be more careful about sorting below comments as we don't
+  // know if the comment refers to the next include or the whole block that
+  // follows.
+  std::vector<unsigned> Blocks(1, 0);
+  for (unsigned I = 1, E = IncludeDirectives.size(); I != E; ++I)
+    if (SM.getExpansionLineNumber(IncludeDirectives[I].Loc) !=
+        SM.getExpansionLineNumber(IncludeDirectives[I - 1].Loc) + 1)
+      Blocks.push_back(I);
+  Blocks.push_back(IncludeDirectives.size()); // Sentinel value.
+
+  // Get a vector of indices.
+  std::vector<unsigned> IncludeIndices;
+  for (unsigned I = 0, E = IncludeDirectives.size(); I != E; ++I)
+    IncludeIndices.push_back(I);
+
+  // Sort the includes. We first sort by priority, then lexicographically.
+  for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI)
+    std::sort(&IncludeIndices[Blocks[BI]], &IncludeIndices[Blocks[BI + 1]],
+              [this](unsigned LHSI, unsigned RHSI) {
+      IncludeDirective &LHS = IncludeDirectives[LHSI];
+      IncludeDirective &RHS = IncludeDirectives[RHSI];
+
+      int PriorityLHS =
+          getPriority(LHS.Filename, LHS.IsAngled, LHS.IsMainModule);
+      int PriorityRHS =
+          getPriority(RHS.Filename, RHS.IsAngled, RHS.IsMainModule);
+
+      return std::tie(PriorityLHS, LHS.Filename) <
+             std::tie(PriorityRHS, RHS.Filename);
+    });
+
+  // Emit a warning for each block and fixits for all changes within that block.
+  for (unsigned BI = 0, BE = Blocks.size() - 1; BI != BE; ++BI) {
+    // Find the first include that's not in the right position.
+    unsigned I, E;
+    for (I = Blocks[BI], E = Blocks[BI + 1]; I != E; ++I)
+      if (IncludeIndices[I] != I)
+        break;
+
+    if (I == E)
+      continue;
+
+    // Emit a warning.
+    auto D = Check.diag(IncludeDirectives[I].Loc,
+                        "#includes are not sorted properly");
+
+    // Emit fix-its for all following includes in this block.
+    for (; I != E; ++I) {
+      if (IncludeIndices[I] == I)
+        continue;
+      const IncludeDirective &CopyFrom = IncludeDirectives[IncludeIndices[I]];
+
+      SourceLocation FromLoc = CopyFrom.Range.getBegin();
+      const char *FromData = SM.getCharacterData(FromLoc);
+      unsigned FromLen = std::strcspn(FromData, "\n");
+
+      StringRef FixedName(FromData, FromLen);
+
+      SourceLocation ToLoc = IncludeDirectives[I].Range.getBegin();
+      const char *ToData = SM.getCharacterData(ToLoc);
+      unsigned ToLen = std::strcspn(ToData, "\n");
+      auto ToRange =
+          CharSourceRange::getCharRange(ToLoc, ToLoc.getLocWithOffset(ToLen));
+
+      D << FixItHint::CreateReplacement(ToRange, FixedName);
+    }
+  }
+
+  IncludeDirectives.clear();
 }
 
 } // namespace tidy
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/a.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/a.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/a.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/b.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/b.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/b.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang-c/c.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang-c/c.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang-c/c.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang/b.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang/b.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/clang/b.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/gtest/foo.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/gtest/foo.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/gtest/foo.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/i.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/i.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/i.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/j.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/j.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/j.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm-c/d.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm-c/d.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm-c/d.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm/a.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm/a.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/llvm/a.h
diff --git a/clang-tools-extra/test/clang-tidy/Inputs/Headers/s.h b/clang-tools-extra/test/clang-tidy/Inputs/Headers/s.h
new file mode 100644
index 00000000000..e69de29bb2d
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/Inputs/Headers/s.h
diff --git a/clang-tools-extra/test/clang-tidy/check_clang_tidy_fix.sh b/clang-tools-extra/test/clang-tidy/check_clang_tidy_fix.sh
index 851307aa031..955696950de 100755
--- a/clang-tools-extra/test/clang-tidy/check_clang_tidy_fix.sh
+++ b/clang-tools-extra/test/clang-tidy/check_clang_tidy_fix.sh
@@ -20,7 +20,7 @@ set -o errexit
 # Remove the contents of the CHECK lines to avoid CHECKs matching on themselves.
 # We need to keep the comments to preserve line numbers while avoiding empty
 # lines which could potentially trigger formatting-related checks.
-sed 's#// *[A-Z-]\+:.*#//#' ${INPUT_FILE} > ${TEMPORARY_FILE}
+sed -E 's#// *[A-Z-]+:.*#//#' ${INPUT_FILE} > ${TEMPORARY_FILE}
 
 clang-tidy ${TEMPORARY_FILE} -fix --checks="-*,${CHECK_TO_RUN}" \
   -- --std=c++11 $* > ${TEMPORARY_FILE}.msg 2>&1
diff --git a/clang-tools-extra/test/clang-tidy/llvm-include-order.cpp b/clang-tools-extra/test/clang-tidy/llvm-include-order.cpp
new file mode 100644
index 00000000000..8311e3a3532
--- /dev/null
+++ b/clang-tools-extra/test/clang-tidy/llvm-include-order.cpp
@@ -0,0 +1,38 @@
+// RUN: $(dirname %s)/check_clang_tidy_fix.sh %s llvm-include-order %t -isystem %S/Inputs/Headers
+// REQUIRES: shell
+
+// CHECK-MESSAGES: [[@LINE+2]]:1: warning: #includes are not sorted properly
+#include "j.h"
+#include "gtest/foo.h"
+#include "i.h"
+#include <s.h>
+#include "llvm/a.h"
+#include "clang/b.h"
+#include "clang-c/c.h" // hi
+#include "llvm-c/d.h" // -c
+
+// CHECK-FIXES: #include "j.h"
+// CHECK-FIXES-NEXT: #include "i.h"
+// CHECK-FIXES-NEXT: #include "clang-c/c.h" // hi
+// CHECK-FIXES-NEXT: #include "clang/b.h"
+// CHECK-FIXES-NEXT: #include "llvm-c/d.h" // -c
+// CHECK-FIXES-NEXT: #include "llvm/a.h"
+// CHECK-FIXES-NEXT: #include "gtest/foo.h"
+// CHECK-FIXES-NEXT: #include <s.h>
+
+#include "b.h"
+#ifdef FOO
+#include "a.h"
+#endif
+
+// CHECK-FIXES: #include "b.h"
+// CHECK-FIXES-NEXT: #ifdef FOO
+// CHECK-FIXES-NEXT: #include "a.h"
+// CHECK-FIXES-NEXT: #endif
+
+// CHECK-MESSAGES: [[@LINE+1]]:1: warning: #includes are not sorted properly
+#include "b.h"
+#include "a.h"
+
+// CHECK-FIXES: #include "a.h"
+// CHECK-FIXES-NEXT: #include "b.h"