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

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

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

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

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.

1228

Fix indent while here.

1294–1300

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.

include/clang/Format/Format.h

struct FormatStyle {
   PointerAlignmentStyle PointerAlignment;
 
   /// \brief If ``true``, clang-format will attempt to re-flow comments.
   bool ReflowComments;
 
   /// \brief If ``true``, clang-format will sort ``#includes``.
   bool SortIncludes;
 
+  /// \brief If ``true``, clang-format will remove duplicate ``#includes`` when
+  /// sorting ``#includes``.
+  bool DeduplicateIncludes;
+
   /// \brief If ``true``, a space may be inserted after C style casts.
   bool SpaceAfterCStyleCast;
 
   /// \brief If ``false``, spaces will be removed before assignment operators.
   bool SpaceBeforeAssignmentOperators;
 
   /// \brief Different ways to put a space before opening parentheses.
   enum SpaceBeforeParensOptions {

lib/Format/Format.cpp

IO.mapOptional("PenaltyBreakFirstLessLess",
                    Style.PenaltyBreakFirstLessLess);
     IO.mapOptional("PenaltyBreakString", Style.PenaltyBreakString);
     IO.mapOptional("PenaltyExcessCharacter", Style.PenaltyExcessCharacter);
     IO.mapOptional("PenaltyReturnTypeOnItsOwnLine",
                    Style.PenaltyReturnTypeOnItsOwnLine);
     IO.mapOptional("PointerAlignment", Style.PointerAlignment);
     IO.mapOptional("ReflowComments", Style.ReflowComments);
     IO.mapOptional("SortIncludes", Style.SortIncludes);
+    IO.mapOptional("DeduplicateIncludes", Style.DeduplicateIncludes);
     IO.mapOptional("SpaceAfterCStyleCast", Style.SpaceAfterCStyleCast);
     IO.mapOptional("SpaceBeforeAssignmentOperators",
                    Style.SpaceBeforeAssignmentOperators);
     IO.mapOptional("SpaceBeforeParens", Style.SpaceBeforeParens);
     IO.mapOptional("SpaceInEmptyParentheses", Style.SpaceInEmptyParentheses);
     IO.mapOptional("SpacesBeforeTrailingComments",
                    Style.SpacesBeforeTrailingComments);
     IO.mapOptional("SpacesInAngles", Style.SpacesInAngles);
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.
 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()))
     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 is currently put.
+  unsigned CurrentCursorIndex = UINT_MAX;
+  // The index of the include on which the cursor will be put after
+  // deduplicating.
+  unsigned CursorIndex = UINT_MAX;
+  if (Cursor)
+    // Find `CurrentCursorIndex` and `CursorIndex`.
+    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) {
+        CurrentCursorIndex = Indices[i];
+        CursorIndex = CurrentCursorIndex;
+        if (Style.DeduplicateIncludes) {
+          // 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;
+      }
+    }
+
+  if (Style.DeduplicateIncludes)
+    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;
-      }
+    if (Cursor && CursorIndex == Index) {
+      unsigned CursorToEOLOffset = Includes[CurrentCursorIndex].Offset +
+                                   Includes[CurrentCursorIndex].Text.size() -
+                                   *Cursor;
+      *Cursor = Includes.front().Offset + result.size() - CursorToEOLOffset;
     }
   }
 
-  // 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 duplicate #includes are not deleted, sorting #includes shouldn't change
+  // their total number of characters.
+  unsigned num_chars_replaced = Includes.back().Offset +
+                                Includes.back().Text.size() -
+                                Includes.front().Offset;
+  assert(Style.DeduplicateIncludes || result.size() == num_chars_replaced);
   auto Err = Replaces.add(tooling::Replacement(
-      FileName, Includes.front().Offset, result.size(), result));
+      FileName, Includes.front().Offset, num_chars_replaced, 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 {

test/Format/remove-duplicate-includes.cpp

+// RUN: grep -Ev "// *[A-Z-]+:" %s \
+// RUN:   | clang-format -style="{BasedOnStyle: LLVM, SortIncludes: true, DeduplicateIncludes: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>
+{
+  int x  ;
+}

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";

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) {
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) {
+  Style.DeduplicateIncludes = true;
+  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) {
+  Style.DeduplicateIncludes = true;
+  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) {
+  Style.DeduplicateIncludes = true;
+  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) {
+  Style.DeduplicateIncludes = true;
+  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) {
+  Style.DeduplicateIncludes = true;
+  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