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

[bkramer]

Summary

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.

[djasper]

Just some high-level comments for now.

clang-tidy/llvm/IncludeOrderCheck.cpp

31 ↗

(On Diff #12064)

If we only look at includes in the main file, will we ever get any warnings about the include order in headers?

44 ↗

(On Diff #12064)

Maybe use translationUnitDecl() so that the empty callback isn't called so often? Probably doesn't matter, though.

Also, couldn't you do that based on PPCallbacks::FileChanged() (when it leaves the main file)?

150 ↗

(On Diff #12064)

The "but" seems wrong.

[alexfh]

clang-tidy/llvm/IncludeOrderCheck.cpp

30 ↗

(On Diff #12064)

It would be useful to check the include order in headers too (except for system headers). The results from unwanted headers are filtered afterwards.

54 ↗

(On Diff #12064)

"Category" is too vague, a more specific name would be better. Maybe "sorting priority", or "precedence"?

76 ↗

(On Diff #12064)

The CR newline style seems to be old enough to be useless. And without supporting it std::strchr would do the job.

101 ↗

(On Diff #12064)

So, this won't work for files consisting only of #includes? That's sub-optimal.

104 ↗

(On Diff #12064)

How about a pure-lexer approach to finding the end of includes block? Just lex everything in between #include directives until you find a non-comment token that is not a part of a preprocessor directive?

BTW, is this needed at all if you only sort includes within each block?

clang-tidy/llvm/IncludeOrderCheck.h

29 ↗

(On Diff #12064)

Please move the function definition to the .cpp file.

47 ↗

(On Diff #12064)

It's a bit confusing. What if the first include in a file was just an arbitrary header, which happened to be included first? What if the first include isn't special (e.g. we're analyzing a header file)?

Should we try to do filename matching?

[bkramer]

clang-tidy/llvm/IncludeOrderCheck.cpp

31 ↗

(On Diff #12064)

I'm not entirely sure if the strategy is to run clang-tidy on the header file to get results or if we want to also have them when running it just on the .cpp file.

But since header results are filtered by default it should be fine to remove this check.

44 ↗

(On Diff #12064)

There is no tranlationUnitDecl() matcher (yet). Reusing PPCallbacks is a good idea, I'll try that.

104 ↗

(On Diff #12064)

It should be fine to even sort clusters of #includes in the middle of the code in LLVM, but I have to double check that.

clang-tidy/llvm/IncludeOrderCheck.h

47 ↗

(On Diff #12064)

I tried to do filename matching (even with some fuzzyness) and it just doesn't work for LLVM. e.g. in lib/Analysis many passes have "Passes.h" at the top which is totally unrelated to the filename :(

[alexfh]

test/clang-tidy/llvm-include-order.cpp

1 ↗

(On Diff #12064)

Why can't we use check_clang_tidy_fix.sh here?

[bkramer]

test/clang-tidy/llvm-include-order.cpp

1 ↗

(On Diff #12064)

There is currently no way to add additional flags (include path in this case) with the shell script. The other reason is that this test case produces an error (the includes don't exist) which the script would catch.

[alexfh]

test/clang-tidy/llvm-include-order.cpp

1 ↗

(On Diff #12064)

I see. How about adding the headers to the Inputs/ directory and adding --isystem=%S/Inputs for "system" headers? Relying on the error recovery doesn't seem correct here.
We could also forward all arguments of the script that we don't use to clang_tidy.

[bkramer]

• Moved everything into the PPCallback. Required adding some accessors to ClangTidyCheck.
• Removed check for "first decl", don't report errors from the main file.
• Made test use check_clang_tidy_fix.sh. Add dummy headers and make the script forward arguments.

[alexfh]

clang-tidy/llvm/IncludeOrderCheck.cpp

51 ↗

(On Diff #12100)

It's wrong to do something here after the check dies. We either need to fix the order of the EndOfMainFile call (it seems to be better to call it before EndSourceFileAction in FrontendAction::EndSourceFile()) or perform the analysis in a different callback.

78 ↗

(On Diff #12100)

So why do we care about CR line endings? ClangFormat doesn't support them, for example, and we didn't get any requests to add support for them, afaik.

112 ↗

(On Diff #12100)

Does "block include sorting" correctly describe what really happens? Don't #define/#if just delimit blocks of includes?

[bkramer]

• Updated for the change that reorders the calls to EndOfMainFile in clang.
• Limited new line checking to \n, which should be sufficient.
• Clarified comments a bit.

[alexfh]

Looks good provided the comments are addressed.

clang-tidy/llvm/IncludeOrderCheck.cpp

71 ↗

(On Diff #12198)

Now that it is just one call, it's not particularly useful to have a separate function. Maybe inline it?

103 ↗

(On Diff #12198)

It probably doesn't matter much, but I don't think we need presumed locations here. Considering #line directives doesn't make much sense in this context.

142 ↗

(On Diff #12198)

Maybe "#includes are not sorted properly"?

[bkramer]

Closed by commit rL215152 (authored by d0k).

clang-tools-extra/trunk/clang-tidy/llvm/IncludeOrderCheck.cpp

 #include "clang/Lex/Preprocessor.h"
 
 namespace clang {
 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
 } // namespace clang

clang-tools-extra/trunk/test/clang-tidy/check_clang_tidy_fix.sh

 # Feed the rest arguments to clang-tidy after --.
 shift 3
 
 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
 
 FileCheck -input-file=${TEMPORARY_FILE} ${INPUT_FILE} \
   -check-prefix=CHECK-FIXES -strict-whitespace
 
 if grep -q CHECK-MESSAGES ${INPUT_FILE}; then
   FileCheck -input-file=${TEMPORARY_FILE}.msg ${INPUT_FILE} \
     -check-prefix=CHECK-MESSAGES -implicit-check-not="{{warning|error}}:"
 fi

clang-tools-extra/trunk/test/clang-tidy/llvm-include-order.cpp

+// 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"