clang-format: Extend #include sorting functionality

[djasper]

Summary

Recognize main module header as well as different #include categories. This should now mimic the behavior of llvm/utils/sort_includes.py as well as clang-tools-extra/clang-tidy/llvm/IncludeOrderCheck.cpp very closely.

[klimek]

lib/Format/Format.cpp

1665

pre-compiled

1677

Run clang-format.

Also, shouldn't we try to figure out whether the name matches, instead of simply assuming the first one is the main header?

[djasper]

lib/Format/Format.cpp

1677

Ran clang-format and added a comment.

[klimek]

lg

[djasper]

Submitted as r248782.

include/clang/Format/Format.h

struct FormatStyle {
   /// \code
   /// FOREACH(<variable-declaration>, ...)
   ///   <loop-body>
   /// \endcode
   ///
   /// For example: BOOST_FOREACH.
   std::vector<std::string> ForEachMacros;
 
+  /// \brief Regular expressions denoting the different #include categories used
+  /// for ordering #includes.
+  ///
+  /// These regular expressions are matched against the filename of an include
+  /// (including the <> or "") in order. The value belonging to the first
+  /// matching regular expression is assigned and #includes are sorted first
+  /// according to increasing category number and then alphabetically within
+  /// each category.
+  ///
+  /// If none of the regular expressions match, UINT_MAX is assigned as
+  /// category. The main header for a source file automatically gets category 0,
+  /// so that it is kept at the beginning of the #includes
+  /// (http://llvm.org/docs/CodingStandards.html#include-style).
+  std::vector<std::pair<std::string, unsigned>> IncludeCategories;
+
   /// \brief Indent case labels one level from the switch statement.
   ///
   /// When \c false, use the same indentation level as for the switch statement.
   /// Switch statement body is always indented one level more than case labels.
   bool IndentCaseLabels;
 
   /// \brief The number of columns to use for indentation.
   unsigned IndentWidth;

lib/Format/Format.cpp

 //===--- Format.cpp - Format C++ code -------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 ///
 /// \file
 /// \brief This file implements functions declared in Format.h. This will be
 /// split into separate files as we go.
 ///
 //===----------------------------------------------------------------------===//
 
+#include "clang/Format/Format.h"
 #include "ContinuationIndenter.h"
 #include "TokenAnnotator.h"
 #include "UnwrappedLineFormatter.h"
 #include "UnwrappedLineParser.h"
 #include "WhitespaceManager.h"
 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/SourceManager.h"
-#include "clang/Format/Format.h"
 #include "clang/Lex/Lexer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/YAMLTraits.h"
 #include <queue>
FormatStyle getLLVMStyle() {
   LLVMStyle.ConstructorInitializerIndentWidth = 4;
   LLVMStyle.ContinuationIndentWidth = 4;
   LLVMStyle.Cpp11BracedListStyle = true;
   LLVMStyle.DerivePointerAlignment = false;
   LLVMStyle.ExperimentalAutoDetectBinPacking = false;
   LLVMStyle.ForEachMacros.push_back("foreach");
   LLVMStyle.ForEachMacros.push_back("Q_FOREACH");
   LLVMStyle.ForEachMacros.push_back("BOOST_FOREACH");
+  LLVMStyle.IncludeCategories = {{"^\"(llvm|llvm-c|clang|clang-c)/", 2},
+                                 {"^(<|\"(gtest|isl|json)/)", 3},
+                                 {".*", 1}};
   LLVMStyle.IndentCaseLabels = false;
   LLVMStyle.IndentWrappedFunctionNames = false;
   LLVMStyle.IndentWidth = 2;
   LLVMStyle.TabWidth = 8;
   LLVMStyle.MaxEmptyLinesToKeep = 1;
   LLVMStyle.KeepEmptyLinesAtTheStartOfBlocks = true;
   LLVMStyle.NamespaceIndentation = FormatStyle::NI_None;
   LLVMStyle.ObjCBlockIndentWidth = 2;
FormatStyle getGoogleStyle(FormatStyle::LanguageKind Language) {
   GoogleStyle.AccessModifierOffset = -1;
   GoogleStyle.AlignEscapedNewlinesLeft = true;
   GoogleStyle.AllowShortIfStatementsOnASingleLine = true;
   GoogleStyle.AllowShortLoopsOnASingleLine = true;
   GoogleStyle.AlwaysBreakBeforeMultilineStrings = true;
   GoogleStyle.AlwaysBreakTemplateDeclarations = true;
   GoogleStyle.ConstructorInitializerAllOnOneLineOrOnePerLine = true;
   GoogleStyle.DerivePointerAlignment = true;
+  GoogleStyle.IncludeCategories = {{"^<.*\\.h>", 1}, {"^<.*", 2}, {".*", 3}};
   GoogleStyle.IndentCaseLabels = true;
   GoogleStyle.KeepEmptyLinesAtTheStartOfBlocks = false;
   GoogleStyle.ObjCSpaceAfterProperty = false;
   GoogleStyle.ObjCSpaceBeforeProtocolList = false;
   GoogleStyle.PointerAlignment = FormatStyle::PAS_Left;
   GoogleStyle.SpacesBeforeTrailingComments = 2;
   GoogleStyle.Standard = FormatStyle::LS_Auto;
 
private:
   encoding::Encoding Encoding;
   bool BinPackInconclusiveFunctions;
 };
 
 struct IncludeDirective {
   StringRef Filename;
   StringRef Text;
   unsigned Offset;
-  bool IsAngled;
+  unsigned Category;
 };
 
 } // end anonymous namespace
 
 // Determines whether 'Ranges' intersects with ('Start', 'End').
 static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
                          unsigned End) {
   for (auto Range : Ranges) {
static void sortIncludes(const FormatStyle &Style,
                          tooling::Replacements &Replaces) {
   if (!affectsRange(Ranges, Includes.front().Offset,
                     Includes.back().Offset + Includes.back().Text.size()))
     return;
   SmallVector<unsigned, 16> Indices;
   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
     Indices.push_back(i);
   std::sort(Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
-    return Includes[LHSI].Filename < Includes[RHSI].Filename;
+    return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
+           std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
   });
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
   bool OutOfOrder = false;
   for (unsigned i = 1, e = Indices.size(); i != e; ++i) {
     if (Indices[i] != i) {
       OutOfOrder = true;

 }
 
 tooling::Replacements sortIncludes(const FormatStyle &Style, StringRef Code,
                                    ArrayRef<tooling::Range> Ranges,
                                    StringRef FileName) {
   tooling::Replacements Replaces;
   unsigned Prev = 0;
   unsigned SearchFrom = 0;
-  llvm::Regex IncludeRegex(R"(^[\t\ ]*#[\t\ ]*include[^"<]*["<]([^">]*)([">]))");
+  llvm::Regex IncludeRegex(
+      R"(^[\t\ ]*#[\t\ ]*include[^"<]*(["<][^">]*[">]))");
   SmallVector<StringRef, 4> Matches;
   SmallVector<IncludeDirective, 16> IncludesInBlock;
+
+  // In compiled files, consider the first #include to be the main #include of
+  // the file if it is not a system #include. This ensures that the header
+  // doesn't have hidden dependencies
+  // (http://llvm.org/docs/CodingStandards.html#include-style).
+  bool LookForMainHeader = FileName.endswith(".c") ||
+                           FileName.endswith(".cc") ||
+                           FileName.endswith(".cpp")||
+                           FileName.endswith(".c++")||
+                           FileName.endswith(".cxx");
+
+  // Create pre-compile regular expressions for the #include categories.
+  SmallVector<llvm::Regex, 4> CategoryRegexs;
+  for (const auto &IncludeBlock : Style.IncludeCategories)
+    CategoryRegexs.emplace_back(IncludeBlock.first);
+
   for (;;) {
     auto Pos = Code.find('\n', SearchFrom);
     StringRef Line =
         Code.substr(Prev, (Pos != StringRef::npos ? Pos : Code.size()) - Prev);
     if (!Line.endswith("\\")) {
       if (IncludeRegex.match(Line, &Matches)) {
-        bool IsAngled = Matches[2] == ">";
-        if (!IncludesInBlock.empty() &&
-            IsAngled != IncludesInBlock.back().IsAngled) {
-          sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
-          IncludesInBlock.clear();
+        unsigned Category;
+        if (LookForMainHeader &&! Matches[1].startswith("<")) {
+          Category = 0;
+        } else {
+          Category = UINT_MAX;
+          for (unsigned i = 0, e = CategoryRegexs.size(); i != e; ++i) {
+            if (CategoryRegexs[i].match(Matches[1])) {
+              Category = Style.IncludeCategories[i].second;
+              break;
+            }
+          }
         }
-        IncludesInBlock.push_back({Matches[1], Line, Prev, Matches[2] == ">"});
+        LookForMainHeader = false;
+        IncludesInBlock.push_back({Matches[1], Line, Prev, Category});
       } else if (!IncludesInBlock.empty()) {
         sortIncludes(Style, IncludesInBlock, Ranges, FileName, Replaces);
         IncludesInBlock.clear();
       }
       Prev = Pos + 1;
     }
     if (Pos == StringRef::npos || Pos + 1 == Code.size())
       break;

tools/clang-format/ClangFormat.cpp

FallbackStyle("fallback-style",
               cl::desc("The name of the predefined style used as a\n"
                        "fallback in case clang-format is invoked with\n"
                        "-style=file, but can not find the .clang-format\n"
                        "file to use.\n"
                        "Use -fallback-style=none to skip formatting."),
               cl::init("LLVM"), cl::cat(ClangFormatCategory));
 
 static cl::opt<std::string>
-AssumeFilename("assume-filename",
+AssumeFileName("assume-filename",
                cl::desc("When reading from stdin, clang-format assumes this\n"
                         "filename to look for a style config file (with\n"
                         "-style=file) and to determine the language."),
                cl::cat(ClangFormatCategory));
 
 static cl::opt<bool> Inplace("i",
                              cl::desc("Inplace edit <file>s, if specified."),
                              cl::cat(ClangFormatCategory));
if (std::error_code EC = CodeOrErr.getError()) {
     return true;
   }
   std::unique_ptr<llvm::MemoryBuffer> Code = std::move(CodeOrErr.get());
   if (Code->getBufferSize() == 0)
     return false; // Empty files are formatted correctly.
   std::vector<tooling::Range> Ranges;
   if (fillRanges(Code.get(), Ranges))
     return true;
-  FormatStyle FormatStyle = getStyle(
-      Style, (FileName == "-") ? AssumeFilename : FileName, FallbackStyle);
+  StringRef AssumedFileName = (FileName == "-") ? AssumeFileName : FileName;
+  FormatStyle FormatStyle = getStyle(Style, AssumedFileName, FallbackStyle);
   Replacements Replaces;
   std::string ChangedCode;
   if (SortIncludes) {
     Replaces =
-        sortIncludes(FormatStyle, Code->getBuffer(), Ranges, FileName);
+        sortIncludes(FormatStyle, Code->getBuffer(), Ranges, AssumedFileName);
     ChangedCode = tooling::applyAllReplacements(Code->getBuffer(), Replaces);
     for (const auto &R : Replaces)
       Ranges.push_back({R.getOffset(), R.getLength()});
   } else {
     ChangedCode = Code->getBuffer().str();
   }
 
   bool IncompleteFormat = false;
cl::ParseCommandLineOptions(
       "result is written to the standard output.\n");
 
   if (Help)
     cl::PrintHelpMessage();
 
   if (DumpConfig) {
     std::string Config =
         clang::format::configurationAsText(clang::format::getStyle(
-            Style, FileNames.empty() ? AssumeFilename : FileNames[0],
+            Style, FileNames.empty() ? AssumeFileName : FileNames[0],
             FallbackStyle));
     llvm::outs() << Config << "\n";
     return 0;
   }
 
   bool Error = false;
   switch (FileNames.size()) {
   case 0:

unittests/Format/SortIncludesTest.cpp

 #define DEBUG_TYPE "format-test"
 
 namespace clang {
 namespace format {
 namespace {
 
 class SortIncludesTest : public ::testing::Test {
 protected:
-  std::string sort(llvm::StringRef Code) {
+  std::string sort(llvm::StringRef Code, StringRef FileName = "input.cpp") {
     std::vector<tooling::Range> Ranges(1, tooling::Range(0, Code.size()));
-    std::string Sorted = applyAllReplacements(
-        Code, sortIncludes(getLLVMStyle(), Code, Ranges, "input.cpp"));
-    return applyAllReplacements(
-        Sorted, reformat(getLLVMStyle(), Sorted, Ranges, "input.cpp"));
+    std::string Sorted =
+        applyAllReplacements(Code, sortIncludes(Style, Code, Ranges, FileName));
+    return applyAllReplacements(Sorted,
+                                reformat(Style, Sorted, Ranges, FileName));
   }
+
+  FormatStyle Style = getLLVMStyle();
 };
 
 TEST_F(SortIncludesTest, BasicSorting) {
   EXPECT_EQ("#include \"a.h\"\n"
             "#include \"b.h\"\n"
             "#include \"c.h\"\n",
             sort("#include \"a.h\"\n"
                  "#include \"c.h\"\n"
EXPECT_EQ("#include \"a.h\"\n"
                  "#include \"b.h\" // >\n"));
 }
 
 TEST_F(SortIncludesTest, SortsLocallyInEachBlock) {
   EXPECT_EQ("#include \"a.h\"\n"
             "#include \"c.h\"\n"
             "\n"
             "#include \"b.h\"\n",
-            sort("#include \"c.h\"\n"
-                 "#include \"a.h\"\n"
+            sort("#include \"a.h\"\n"
+                 "#include \"c.h\"\n"
                  "\n"
                  "#include \"b.h\"\n"));
 }
 
 TEST_F(SortIncludesTest, HandlesAngledIncludesAsSeparateBlocks) {
+  EXPECT_EQ("#include \"a.h\"\n"
+            "#include \"c.h\"\n"
+            "#include <b.h>\n"
+            "#include <d.h>\n",
+            sort("#include <d.h>\n"
+                 "#include <b.h>\n"
+                 "#include \"c.h\"\n"
+                 "#include \"a.h\"\n"));
+
+  Style = getGoogleStyle(FormatStyle::LK_Cpp);
   EXPECT_EQ("#include <b.h>\n"
             "#include <d.h>\n"
             "#include \"a.h\"\n"
             "#include \"c.h\"\n",
             sort("#include <d.h>\n"
                  "#include <b.h>\n"
                  "#include \"c.h\"\n"
                  "#include \"a.h\"\n"));
 }
 
 TEST_F(SortIncludesTest, HandlesMultilineIncludes) {
   EXPECT_EQ("#include \"a.h\"\n"
             "#include \"b.h\"\n"
             "#include \"c.h\"\n",
             sort("#include \"a.h\"\n"
                  "#include \\\n"
                  "\"c.h\"\n"
                  "#include \"b.h\"\n"));
 }
 
+TEST_F(SortIncludesTest, LeavesMainHeaderFirst) {
+  EXPECT_EQ("#include \"llvm/a.h\"\n"
+            "#include \"b.h\"\n"
+            "#include \"c.h\"\n",
+            sort("#include \"llvm/a.h\"\n"
+                 "#include \"c.h\"\n"
+                 "#include \"b.h\"\n"));
+
+  // Don't do this in headers.
+  EXPECT_EQ("#include \"b.h\"\n"
+            "#include \"c.h\"\n"
+            "#include \"llvm/a.h\"\n",
+            sort("#include \"llvm/a.h\"\n"
+                 "#include \"c.h\"\n"
+                 "#include \"b.h\"\n",
+                 "some_header.h"));
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang