Make clang-format remove duplicate headers when sorting #includes.

[ioeric]

Summary

When sorting #includes, #include directives that have the same text will be deduplicated when sorting #includes, and only the first #include in the duplicate #includes remains. If the Cursor is provided and put on a deleted #include, it will be put on the remaining #include in the duplicate #includes.

[ioeric]

• Check code that is not in affected range is not reformatted in lit test.

[djasper]

lib/Format/Format.cpp

1242 ↗

(On Diff #67191)

This needs a comment on what it is actually doing (including what the intended behavior is). And that comment should also go into the patch description.

Also, it might be a good idea to pull this out into a function.

[djasper]

include/clang/Format/Format.h

551 ↗

(On Diff #67191)

Actually, how about we just do this unconditionally? I think people will always want it.

[ioeric]

• Addressed review comments.

[ioeric]

include/clang/Format/Format.h

551 ↗

(On Diff #67483)

Sounds good to me. I'll get rid of the option then.

[ioeric]

• Always deduplicate when sorting includes. Get rid of the option.

[djasper]

lib/Format/Format.cpp

1224 ↗

(On Diff #67483)

First off, make this return a pair<unsigned, unsigned> with the two values.

And then the comment needs to be more precise:

// Returns a pair (Index, OffsetToEOL) describing the position of the cursor
// before sorting/deduplicating. Index is the index of the include under the cursor
// in the original set of includes. If this include has duplicates, it is the index of
// the first of the duplicates as the others are going to be removed. OffsetToEOL
// Describes the cursor's position relative to the end of its current line.

1260 ↗

(On Diff #67483)

Fix indent while here.

1306 ↗

(On Diff #67483)

This can also be calculated upfront with:

Includes.back().Offset + Includes.back().Text.size() - Includes.front().Offset

And maybe you can pull some of those out into variables as they are also used in the very first line of this function.

[ioeric]

• Addressed review comments.

[djasper]

Looks good.

cfe/trunk/lib/Format/Format.cpp

static bool affectsRange(ArrayRef<tooling::Range> Ranges, unsigned Start,
   for (auto Range : Ranges) {
     if (Range.getOffset() < End &&
         Range.getOffset() + Range.getLength() > Start)
       return true;
   }
   return false;
 }
 
-// Sorts a block of includes given by 'Includes' alphabetically adding the
-// necessary replacement to 'Replaces'. 'Includes' must be in strict source
-// order.
+// Returns a pair (Index, OffsetToEOL) describing the position of the cursor
+// before sorting/deduplicating. Index is the index of the include under the
+// cursor in the original set of includes. If this include has duplicates, it is
+// the index of the first of the duplicates as the others are going to be
+// removed. OffsetToEOL describes the cursor's position relative to the end of
+// its current line.
+// If `Cursor` is not on any #include, `Index` will be UINT_MAX.
+static std::pair<unsigned, unsigned>
+FindCursorIndex(const SmallVectorImpl<IncludeDirective> &Includes,
+                const SmallVectorImpl<unsigned> &Indices, unsigned Cursor) {
+  unsigned CursorIndex = UINT_MAX;
+  unsigned OffsetToEOL = 0;
+  for (int i = 0, e = Includes.size(); i != e; ++i) {
+    unsigned Start = Includes[Indices[i]].Offset;
+    unsigned End = Start + Includes[Indices[i]].Text.size();
+    if (!(Cursor >= Start && Cursor < End))
+      continue;
+    CursorIndex = Indices[i];
+    OffsetToEOL = End - Cursor;
+    // Put the cursor on the only remaining #include among the duplicate
+    // #includes.
+    while (--i >= 0 && Includes[CursorIndex].Text == Includes[Indices[i]].Text)
+      CursorIndex = i;
+    break;
+  }
+  return std::make_pair(CursorIndex, OffsetToEOL);
+}
+
+// Sorts and deduplicate a block of includes given by 'Includes' alphabetically
+// adding the necessary replacement to 'Replaces'. 'Includes' must be in strict
+// source order.
+// #include directives with the same text will be deduplicated, and only the
+// first #include in the duplicate #includes remains. If the `Cursor` is
+// provided and put on a deleted #include, it will be moved to the remaining
+// #include in the duplicate #includes.
 static void sortCppIncludes(const FormatStyle &Style,
                             const SmallVectorImpl<IncludeDirective> &Includes,
                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
                             tooling::Replacements &Replaces, unsigned *Cursor) {
-  if (!affectsRange(Ranges, Includes.front().Offset,
-                    Includes.back().Offset + Includes.back().Text.size()))
+  unsigned IncludesBeginOffset = Includes.front().Offset;
+  unsigned IncludesBlockSize = Includes.back().Offset +
+                               Includes.back().Text.size() -
+                               IncludesBeginOffset;
+  if (!affectsRange(Ranges, IncludesBeginOffset, IncludesBlockSize))
     return;
   SmallVector<unsigned, 16> Indices;
   for (unsigned i = 0, e = Includes.size(); i != e; ++i)
     Indices.push_back(i);
   std::stable_sort(
       Indices.begin(), Indices.end(), [&](unsigned LHSI, unsigned RHSI) {
         return std::tie(Includes[LHSI].Category, Includes[LHSI].Filename) <
                std::tie(Includes[RHSI].Category, Includes[RHSI].Filename);
       });
+  // The index of the include on which the cursor will be put after
+  // sorting/deduplicating.
+  unsigned CursorIndex;
+  // The offset from cursor to the end of line.
+  unsigned CursorToEOLOffset;
+  if (Cursor)
+    std::tie(CursorIndex, CursorToEOLOffset) =
+        FindCursorIndex(Includes, Indices, *Cursor);
+
+  // Deduplicate #includes.
+  Indices.erase(std::unique(Indices.begin(), Indices.end(),
+                            [&](unsigned LHSI, unsigned RHSI) {
+                              return Includes[LHSI].Text == Includes[RHSI].Text;
+                            }),
+                Indices.end());
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
-  if (std::is_sorted(Indices.begin(), Indices.end()))
+  if (Indices.size() == Includes.size() &&
+      std::is_sorted(Indices.begin(), Indices.end()))
     return;
 
   std::string result;
-  bool CursorMoved = false;
   for (unsigned Index : Indices) {
     if (!result.empty())
       result += "\n";
     result += Includes[Index].Text;
-
-    if (Cursor && !CursorMoved) {
-      unsigned Start = Includes[Index].Offset;
-      unsigned End = Start + Includes[Index].Text.size();
-      if (*Cursor >= Start && *Cursor < End) {
-        *Cursor = Includes.front().Offset + result.size() + *Cursor - End;
-        CursorMoved = true;
-      }
-    }
-  }
-
-  // Sorting #includes shouldn't change their total number of characters.
-  // This would otherwise mess up 'Ranges'.
-  assert(result.size() ==
-         Includes.back().Offset + Includes.back().Text.size() -
-             Includes.front().Offset);
+    if (Cursor && CursorIndex == Index)
+      *Cursor = IncludesBeginOffset + result.size() - CursorToEOLOffset;
 
   auto Err = Replaces.add(tooling::Replacement(
-      FileName, Includes.front().Offset, result.size(), result));
+      FileName, Includes.front().Offset, IncludesBlockSize, result));
   // FIXME: better error handling. For now, just skip the replacement for the
   // release version.
   if (Err)
     llvm::errs() << llvm::toString(std::move(Err)) << "\n";
   assert(!Err);
 }
 
 namespace {

cfe/trunk/test/Format/remove-duplicate-includes.cpp

+// RUN: grep -Ev "// *[A-Z-]+:" %s \
+// RUN:   | clang-format -style="{BasedOnStyle: LLVM, SortIncludes: true}" -lines=1:5 \
+// RUN:   | FileCheck -strict-whitespace %s
+// CHECK: {{^#include\ <a>$}}
+#include  <a>
+// CHECK: {{^#include\ <b>$}}
+#include  <b>
+#include  <a>
+#include  <b>
+#include  <b>
+{
+// CHECK: {{^\ \ int x\ \ ;$}}
+  int x  ;
+}

cfe/trunk/tools/clang-format/ClangFormat.cpp

static bool format(StringRef FileName) {
   unsigned CursorPosition = Cursor;
   Replacements Replaces = sortIncludes(FormatStyle, Code->getBuffer(), Ranges,
                                        AssumedFileName, &CursorPosition);
   auto ChangedCode = tooling::applyAllReplacements(Code->getBuffer(), Replaces);
   if (!ChangedCode) {
     llvm::errs() << llvm::toString(ChangedCode.takeError()) << "\n";
     return true;
   }
-  for (const auto &R : Replaces)
-    Ranges.push_back({R.getOffset(), R.getLength()});
-
+  // Get new affected ranges after sorting `#includes`.
+  Ranges = tooling::calculateRangesAfterReplacements(Replaces, Ranges);
   bool IncompleteFormat = false;
   Replacements FormatChanges = reformat(FormatStyle, *ChangedCode, Ranges,
                                         AssumedFileName, &IncompleteFormat);
   Replaces = Replaces.merge(FormatChanges);
   if (OutputXML) {
     outs() << "<?xml version='1.0'?>\n<replacements "
               "xml:space='preserve' incomplete_format='"
            << (IncompleteFormat ? "true" : "false") << "'>\n";

cfe/trunk/unittests/Format/SortIncludesTest.cpp

 class SortIncludesTest : public ::testing::Test {
 protected:
   std::vector<tooling::Range> GetCodeRange(StringRef Code) {
     return std::vector<tooling::Range>(1, tooling::Range(0, Code.size()));
   }
 
   std::string sort(StringRef Code, StringRef FileName = "input.cpp") {
     auto Ranges = GetCodeRange(Code);
-    auto Sorted =
-        applyAllReplacements(Code, sortIncludes(Style, Code, Ranges, FileName));
+    auto Replaces = sortIncludes(Style, Code, Ranges, FileName);
+    Ranges = tooling::calculateRangesAfterReplacements(Replaces, Ranges);
+    auto Sorted = applyAllReplacements(Code, Replaces);
     EXPECT_TRUE(static_cast<bool>(Sorted));
     auto Result = applyAllReplacements(
         *Sorted, reformat(Style, *Sorted, Ranges, FileName));
     EXPECT_TRUE(static_cast<bool>(Result));
     return *Result;
   }
 
   unsigned newCursor(llvm::StringRef Code, unsigned Cursor) {
EXPECT_EQ("#include \"a.h\"\n"
                  "#include \"c.h\"\n"
                  "#include \"b.h\"\n"));
 }
 
 TEST_F(SortIncludesTest, NoReplacementsForValidIncludes) {
   // Identical #includes have led to a failure with an unstable sort.
   std::string Code = "#include <a>\n"
                      "#include <b>\n"
-                     "#include <b>\n"
-                     "#include <b>\n"
-                     "#include <b>\n"
-                     "#include <c>\n";
+                     "#include <c>\n"
+                     "#include <d>\n"
+                     "#include <e>\n"
+                     "#include <f>\n";
   EXPECT_TRUE(sortIncludes(Style, Code, GetCodeRange(Code), "a.cc").empty());
 }
 
 TEST_F(SortIncludesTest, SupportClangFormatOff) {
   EXPECT_EQ("#include <a>\n"
             "#include <b>\n"
             "#include <c>\n"
             "// clang-format off\n"
TEST_F(SortIncludesTest, CalculatesCorrectCursorPosition) {
   EXPECT_EQ(13u, newCursor(Code, 15));
   EXPECT_EQ(0u, newCursor(Code, 33));
 
   EXPECT_EQ(41u, newCursor(Code, 10));
   EXPECT_EQ(23u, newCursor(Code, 25));
   EXPECT_EQ(10u, newCursor(Code, 43));
 }
 
+TEST_F(SortIncludesTest, DeduplicateIncludes) {
+  EXPECT_EQ("#include <a>\n"
+            "#include <b>\n"
+            "#include <c>\n",
+            sort("#include <a>\n"
+                 "#include <b>\n"
+                 "#include <b>\n"
+                 "#include <b>\n"
+                 "#include <b>\n"
+                 "#include <c>\n"));
+}
+
+TEST_F(SortIncludesTest, SortAndDeduplicateIncludes) {
+  EXPECT_EQ("#include <a>\n"
+            "#include <b>\n"
+            "#include <c>\n",
+            sort("#include <b>\n"
+                 "#include <a>\n"
+                 "#include <b>\n"
+                 "#include <b>\n"
+                 "#include <c>\n"
+                 "#include <b>\n"));
+}
+
+TEST_F(SortIncludesTest, CalculatesCorrectCursorPositionAfterDeduplicate) {
+  std::string Code = "#include <b>\n"      // Start of line: 0
+                     "#include <a>\n"      // Start of line: 13
+                     "#include <b>\n"      // Start of line: 26
+                     "#include <b>\n"      // Start of line: 39
+                     "#include <c>\n"      // Start of line: 52
+                     "#include <b>\n";     // Start of line: 65
+  std::string Expected = "#include <a>\n"  // Start of line: 0
+                         "#include <b>\n"  // Start of line: 13
+                         "#include <c>\n"; // Start of line: 26
+  EXPECT_EQ(Expected, sort(Code));
+  // Cursor on 'i' in "#include <a>".
+  EXPECT_EQ(1u, newCursor(Code, 14));
+  // Cursor on 'b' in "#include <b>".
+  EXPECT_EQ(23u, newCursor(Code, 10));
+  EXPECT_EQ(23u, newCursor(Code, 36));
+  EXPECT_EQ(23u, newCursor(Code, 49));
+  EXPECT_EQ(23u, newCursor(Code, 36));
+  EXPECT_EQ(23u, newCursor(Code, 75));
+  // Cursor on '#' in "#include <c>".
+  EXPECT_EQ(26u, newCursor(Code, 52));
+}
+
+TEST_F(SortIncludesTest, DeduplicateLocallyInEachBlock) {
+  EXPECT_EQ("#include <a>\n"
+            "#include <b>\n"
+            "\n"
+            "#include <b>\n"
+            "#include <c>\n",
+            sort("#include <a>\n"
+                 "#include <b>\n"
+                 "\n"
+                 "#include <c>\n"
+                 "#include <b>\n"
+                 "#include <b>\n"));
+}
+
+TEST_F(SortIncludesTest, ValidAffactedRangesAfterDeduplicatingIncludes) {
+  std::string Code = "#include <a>\n"
+                     "#include <b>\n"
+                     "#include <a>\n"
+                     "#include <a>\n"
+                     "\n"
+                     "   int     x ;";
+  std::vector<tooling::Range> Ranges = {tooling::Range(0, 52)};
+  auto Replaces = sortIncludes(Style, Code, Ranges, "input.cpp");
+  Ranges = tooling::calculateRangesAfterReplacements(Replaces, Ranges);
+  EXPECT_EQ(1u, Ranges.size());
+  EXPECT_EQ(0u, Ranges[0].getOffset());
+  EXPECT_EQ(26u, Ranges[0].getLength());
+}
+
 } // end namespace
 } // end namespace format
 } // end namespace clang