[clang-format] Remove all include duplicates not only those in the same block

[Febbe]

Summary

This change aims to remove all duplicate include directives,
instead of only those, which are in the same block.

This change might be a bit controversial, since it will also remove includes, which are in custom splitted blocks like:

#include "a.h"
/* some code */

// following include must stay!:
#include "a.h"

This is a follow up patch for D143691, but can be freestanding.

[HazardyKnusperkeks]

I can see that this is maybe useful, but that have to be behind a new option, which is turned off by default. And a big no to changing the existing tests, you may add new stuff.

[Febbe]

@HazardyKnusperkeks thank you for the review, I would add another option, but I don't know a good name. I would propose a

boolean IncludeDeduplicateInAllBlocks which defaults to zero.

First an Include, to keep include-sorting related options together in the documentation (sorted by name not by category)
DeduplicateInAllBlocks self explaining name.

But IncludeDeduplication with the enum states IDD_SameBlock(default) and IDD_ALL would also an option.
The latter has the advantage, that an expansion of this option would not require the adjustment of tests.

What's your preference?

[HazardyKnusperkeks]

In D143870#4124057, @Febbe wrote:

@HazardyKnusperkeks thank you for the review, I would add another option, but I don't know a good name. I would propose a

boolean IncludeDeduplicateInAllBlocks which defaults to zero.

First an Include, to keep include-sorting related options together in the documentation (sorted by name not by category)
DeduplicateInAllBlocks self explaining name.

But IncludeDeduplication with the enum states IDD_SameBlock(default) and IDD_ALL would also an option.
The latter has the advantage, that an expansion of this option would not require the adjustment of tests.

What's your preference?

The enum is the better variant, I'd add the Off/None variant in the same breath. But the name has to be better, you don't need to start it with Include, since D138446 we can link to other options and that should happen. So a more natural name would be DeduplicateIncludeDirectives.

[MyDeveloperDay]

I know it might not seem an obvious use case but there really isn't a requirement to not include header files more than once.. imagine if I have

#define ARCH "win32"
#include "MyDataStructThatContainsPlaformSpecificNamesUsingARCH.h"
#define ARCH "win64"
#include "MyDataStructThatContainsPlaformSpecificNamesUsingARCH.h"

Its not nice, but just because I include it twice doesn't mean its wrong? This change would break code written that way, No?

clang/unittests/Format/SortIncludesTest.cpp

927

Please don't change existing tests

[Febbe]

In D143870#4273075, @MyDeveloperDay wrote:

I know it might not seem an obvious use case but there really isn't a requirement to not include header files more than once.. imagine if I have

#define ARCH "win32"
#include "MyDataStructThatContainsPlaformSpecificNamesUsingARCH.h"
#define ARCH "win64"
#include "MyDataStructThatContainsPlaformSpecificNamesUsingARCH.h"

Its not nice, but just because I include it twice doesn't mean its wrong? This change would break code written that way, No?

Mhh, I need to test that. But you are right, if it removes the header in one of the conditional preprocessor blocks, it would be very bad.
Regarding normal blocks, the behavior was already inconsistent, as soon to reorder blocks was activated:
Blocks are merged if possible, then de-duplicated and split again. So I just made the behavior more consistent here.

Regarding the comment that I must not change existing tests: I think this rule is too strict, because those tests are mostly regression tests.
But a regression tests does not test for correctness. So if a test had already a wrong assumption, it must be changeable.
Also, when a behavior is now undesirable, it should be possible to adapt them.
I would say in this case I should replace the test with your case, to reflect that includes must not be removed, when they are in different conditional preprocessor blocks.
That the different "modi" should be more consistent is in my opinion desirable.

Last but not least, I currently have nearly zero free time, so I would like to pause this and my other phab until my thesis is done.

[MyDeveloperDay]

Regarding the comment that I must not change existing tests: I think this rule is too strict, because those tests are mostly regression tests.
But a regression tests does not test for correctness. So if a test had already a wrong assumption, it must be changeable.

I don't agree, you are making the assumption that the default behaviour should now be different from what is was before, we have 100,000+ of users did you canvas them to ask if we wanted your suggested correct behaviour? (especially when someone has split their includes into a separate include group? I assume for a reason)

What would be their recourse if they didn't want the duplicate removed across groups, I don't see one? are you expecting them to // clang-format on/off

Ultimately we try not to change the default behaviour, if we think the behaviour is useful (and this could be), we ask that its put behind a new "Option" and that by default its off.

SortIncludes was latterly considered a contentious addition and has been proved to alter code in a well publicized example, in hindsight most people think it should have been off by default. I don't like making assumptions that we should turn something on, that others might not want/need or desire. This feels like one of those and something that could break code.

I personally follow a Beyoncé rule when it comes to unit tests... "If I like it I should have put a test on it", if the test is there, I need to be persuaded the test is very wrong before I'm happy to let it be changed to a new behaviour.

FWIW, these are not just regression tests, they assert that the behaviour is as the author desired and that is considered correctness until proven otherwise, any new author needs to respect that, or prove its a genuine bug and not just a matter of style/opinion.

[Febbe]

Actually, I already wanted to add an enum, controlling this behavior.
But even with an enum, this check should only remove includes in consecutive blocks, which could be relocated (are not split by #defines or a comment)
Or I should add the options to DeduplicateIncludeDirectives: {DID_InSameBlock (default), DID_Never, DID_Allways, DID_OnlyConsecutiveBlocks}

Note, that I use DID_InSameBlock as default, because that's the current behavior, even many people would like to have it off by default.

Regarding the breaking of current features: What would you do, if a break is necessary, to implement a way more useful feature or to fix a huge issue/bug?
Would you just infer a new version number? (I personally don't like the idea of having version numbers for specific tests, but that would be the easiest way to keep compatibility with old configurations and codebases).
Of course, the assumptions must be proven, as you said.

clang/lib/Format/Format.cpp

 #include "clang/Basic/Diagnostic.h"
 #include "clang/Basic/DiagnosticOptions.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Lex/Lexer.h"
 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/Sequence.h"
 #include "llvm/ADT/StringRef.h"
+#include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Allocator.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/Path.h"
 #include "llvm/Support/Regex.h"
 #include "llvm/Support/VirtualFileSystem.h"
 #include "llvm/Support/YAMLTraits.h"
 #include <algorithm>
 #include <memory>

 // 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,
+                            llvm::StringSet<> &AllIncludes,
                             ArrayRef<tooling::Range> Ranges, StringRef FileName,
                             StringRef Code, tooling::Replacements &Replaces,
                             unsigned *Cursor) {
   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
   const unsigned IncludesBeginOffset = Includes.front().Offset;
   const unsigned IncludesEndOffset =
       Includes.back().Offset + Includes.back().Text.size();
   const unsigned IncludesBlockSize = IncludesEndOffset - IncludesBeginOffset;
static void sortCppIncludes(const FormatStyle &Style,
   // 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.trim() ==
-                                     Includes[RHSI].Text.trim();
-                            }),
-                Indices.end());
+
+  Indices.erase(
+      std::remove_if(
+          Indices.begin(), Indices.end(),
+          [&](unsigned val) {
+            return !AllIncludes.try_emplace(Includes[val].Text.trim()).second;
 
   int CurrentCategory = Includes.front().Category;
 
   // If the #includes are out of order, we generate a single replacement fixing
   // the entire block. Otherwise, no replacement is generated.
   // In case Style.IncldueStyle.IncludeBlocks != IBS_Preserve, this check is not
   // enough as additional newlines might be added or removed across #include
   // blocks. This we handle below by generating the updated #include blocks and
tooling::Replacements sortCppIncludes(const FormatStyle &Style, StringRef Code,
                                       StringRef FileName,
                                       tooling::Replacements &Replaces,
                                       unsigned *Cursor) {
   unsigned Prev = llvm::StringSwitch<size_t>(Code)
                       .StartsWith("\xEF\xBB\xBF", 3) // UTF-8 BOM
                       .Default(0);
   unsigned SearchFrom = 0;
   SmallVector<StringRef, 4> Matches;
+  llvm::StringSet<> AllIncludes{};
   SmallVector<IncludeDirective, 16> IncludesInBlock;
 
   // FIXME: Do some validation, e.g. edit distance of the base name, to fix
   // cases where the first #include is unlikely to be the main header.
   tooling::IncludeCategoryManager Categories(Style.IncludeStyle, FileName);
   bool FirstIncludeBlock = true;
   // Todo(remove before merge): removed: multiple files can be main includes
   // This option caused random sorting, depending which was detected first.
if (!FormattingOff && !MergeWithNextLine) {
         }
         int Category = Categories.getIncludePriority(
             IncludeName,
             /*CheckMainHeader=*/FirstIncludeBlock);
         int Priority =
             Categories.getSortIncludePriority(IncludeName, FirstIncludeBlock);
         // Todo(remove before merge): reason for removal: every header can have
         // 0,0 priority
+
         IncludesInBlock.push_back(
             {IncludeName, Line, Prev, Category, Priority});
+
       } else if (!IncludesInBlock.empty() && !EmptyLineSkipped) {
-        sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code,
-                        Replaces, Cursor);
+        sortCppIncludes(Style, IncludesInBlock, AllIncludes, Ranges, FileName,
+                        Code, Replaces, Cursor);
         IncludesInBlock.clear();
-        if (Trimmed.startswith("#pragma hdrstop")) // Precompiled headers.
+        if (Trimmed.startswith("#pragma hdrstop")) { // Precompiled headers.
           FirstIncludeBlock = true;
-        else
+          AllIncludes.clear();
+        } else {
           FirstIncludeBlock = false;
         }
       }
+    }
     if (Pos == StringRef::npos || Pos + 1 == Code.size())
       break;
 
     if (!MergeWithNextLine)
       Prev = Pos + 1;
     SearchFrom = Pos + 1;
   }
   if (!IncludesInBlock.empty()) {
-    sortCppIncludes(Style, IncludesInBlock, Ranges, FileName, Code, Replaces,
-                    Cursor);
+    sortCppIncludes(Style, IncludesInBlock, AllIncludes, Ranges, FileName, Code,
+                    Replaces, Cursor);
   }
   return Replaces;
 }
 
 // Returns group number to use as a first order sort on imports. Gives UINT_MAX
 // if the import does not match any given groups.
 static unsigned findJavaImportGroup(const FormatStyle &Style,
                                     StringRef ImportIdentifier) {

clang/unittests/Format/SortIncludesTest.cpp

EXPECT_EQ("#include <a>\n"
                  "#include <c>\n"
                  "/* clang-format on */\n"));
 
   // Not really turning it off
   EXPECT_EQ("#include <a>\n"
             "#include <b>\n"
             "#include <c>\n"
             "/* clang-format offically */\n"
-            "#include <a>\n"
-            "#include <b>\n"
-            "#include <c>\n"
+            "\n"
             "/* clang-format onwards */\n",
             sort("#include <b>\n"
                  "#include <a>\n"
                  "#include <c>\n"
                  "/* clang-format offically */\n"
                  "#include <b>\n"
                  "#include <a>\n"
                  "#include <c>\n"
EXPECT_EQ("#include <a>\n"
             "#include <c>\n",
             sort("#include <b>\n"
                  "#include <a>\n"
                  "\n"
                  "#include <b>\n"
                  "\n"
                  "#include <c>\n"
                  "#include <b>\n"));
+
+  Style.IncludeBlocks = tooling::IncludeStyle::IBS_Regroup;
+  EXPECT_EQ("#include \"MyProject/MyLibrary/c_main.h\"\n"
+            "\n"
+            "#include <MyProject/MySubLibrary/MySubClass.h>\n"
+            "//\n",
+            sort("#include \"MyProject/MyLibrary/c_main.h\"\n"
+                 "#include \"MyProject/MyLibrary/c_main.h\"\n"
+                 "#include <MyProject/MySubLibrary/MySubClass.h>\n"
+                 "#include <MyProject/MySubLibrary/MySubClass.h>\n"
+                 "//\n"
+                 "#include <MyProject/MySubLibrary/MySubClass.h>\n",
+                 "c_main.cpp", 2U));
 }
 
 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
TEST_F(SortIncludesTest, CalculatesCorrectCursorPositionAfterDeduplicate) {
   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) {
+TEST_F(SortIncludesTest, DeduplicateInAllBlocks) {
   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"));
 }