[clangd] Deduplicate missing-include findings

[VitaNuo]

Thank you!

clang-tools-extra/clangd/IncludeCleaner.cpp

419

Could you move the below to a separate function with a descriptive name? IMO taking care of the special cases inline makes functions very long and distracts the reader from their main purpose.

432

Nit: maybe add a comment explaining that llvm::unique returns a past-the-end iterator after deduplicating elements? I've spent a bit of time deciphering this line.

clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp

417

Nit: move )cpp"); to the next line please.

421

Nit: use the same style for multiline strings, i.e., R"cpp(.

423

Nit: move closing tokens of the multiline string to next line.

[kadircet]

clang-tools-extra/clangd/IncludeCleaner.cpp

419

but this is not a special case, this is still part of "missing include information gathering", and is being applied to all of the findings (just like how all the used headers get accumulated in a set, the only problem is members of MissingIncludeDiagInfo is hard to order, hence we can't directly use a set)

432

yeah the language isn't really helpful in that regard but unfortunately unique & erase pattern is pretty much the idiomatic way of deduplicating a sorted container. I can add it here but we have some more mentions of it across the code that doesn't have any explanations. so I am not sure what kind of weight it would carry.

[kadircet]

• Reorganize string literals in tests

[ArturGainullin]

Hello! After this change IncludeCleaner.GenerateMissingHeaderDiags unit test from ClangdTests.exe is failing on Windows for Debug build. Could you please take a look.
It looks like error appears because comparator doesn't satisfy strict weak ordering.
I.e. it fails on verification of the comparator (with "invalid comparator" message) at the following line:

MissingIncludes.erase(llvm::unique(MissingIncludes), MissingIncludes.end());

[----------] 1 test from IncludeCleaner
[ RUN      ] IncludeCleaner.GenerateMissingHeaderDiags
Built preamble of size 193724 for file C:\clangd-test\foo.cpp version null in 0.07 seconds
Exception Code: 0x80000003
0x00007FF66CA142FE, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D342FE byte(s), std::_Debug_lt_pred<`clang::clangd::computeIncludeCleanerFindings'::`2'::<lambda_2> &,clang::clangd::MissingIncludeDiagInfo &,clang::clangd::MissingIncludeDiagInfo &,0>() + 0x8E byte(s), C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Tools\MSVC\14.33.31629\include\xutility, line 1532 + 0x55 byte(s)
0x00007FF66CA1645F, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D3645F byte(s), std::_Insertion_sort_unchecked<clang::clangd::MissingIncludeDiagInfo *,`clang::clangd::computeIncludeCleanerFindings'::`2'::<lambda_2> >() + 0xAF byte(s), C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Tools\MSVC\14.33.31629\include\algorithm, line 7154 + 0x1A byte(s)
0x00007FF66CA19D05, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D39D05 byte(s), std::stable_sort<std::_Vector_iterator<std::_Vector_val<std::_Simple_types<clang::clangd::MissingIncludeDiagInfo> > >,`clang::clangd::computeIncludeCleanerFindings'::`2'::<lambda_2> >() + 0xC5 byte(s), C:\Program Files\Microsoft Visual Studio\2022\Professional\VC\Tools\MSVC\14.33.31629\include\algorithm, line 7714 + 0x0 byte(s)
0x00007FF66CA19C18, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D39C18 byte(s), llvm::stable_sort<std::vector<clang::clangd::MissingIncludeDiagInfo,std::allocator<clang::clangd::MissingIncludeDiagInfo> > &,`clang::clangd::computeIncludeCleanerFindings'::`2'::<lambda_2> >() + 0x68 byte(s), C:\iusers\againull\llvm-project\llvm\include\llvm\ADT\STLExtras.h, line 2070 + 0x0 byte(s)
0x00007FF66CA0CC3A, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D2CC3A byte(s), clang::clangd::computeIncludeCleanerFindings() + 0x3FA byte(s), C:\iusers\againull\llvm-project\clang-tools-extra\clangd\IncludeCleaner.cpp, line 433 + 0x0 byte(s)
0x00007FF66CA0CF74, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5D2CF74 byte(s), clang::clangd::issueIncludeCleanerDiagnostics() + 0xF4 byte(s), C:\iusers\againull\llvm-project\clang-tools-extra\clangd\IncludeCleaner.cpp, line 561 + 0x15 byte(s)
0x00007FF66C1E2385, C:\iusers\againull\llvm-project\build\tools\clang\tools\extra\clangd\unittests\ClangdTests.exe(0x00007FF666CE0000) + 0x5502385 byte(s), clang::clangd::ParsedAST::build() + 0x2C15 byte(s),
C:\iusers\againull\llvm-project\clang-tools-extra\clangd\ParsedAST.cpp, line 691 + 0x88 byte(s)
...

[kadircet]

Thanks @ArturGainullin ! you're right, i've sent out 5e74a3dc2da879d98204f2360e2e33571b93b91b.

[ArturGainullin]

In D149165#4309463, @kadircet wrote:

Thanks @ArturGainullin ! you're right, i've sent out 5e74a3dc2da879d98204f2360e2e33571b93b91b.

@kadircet Thanks a lot!

clang-tools-extra/clangd/IncludeCleaner.cpp

 #include "clang/Lex/HeaderSearch.h"
 #include "clang/Lex/Preprocessor.h"
 #include "clang/Tooling/Core/Replacement.h"
 #include "clang/Tooling/Inclusions/HeaderIncludes.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
 #include "clang/Tooling/Syntax/Tokens.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/GenericUniformityImpl.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/STLFunctionalExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/Error.h"
include_cleaner::walkUsed(
         assert(!TouchingTokens.empty());
         // Loc points to the start offset of the ref token, here we use the last
         // element of the TouchingTokens, e.g. avoid getting the "::" for
         // "ns::^abc".
         MissingIncludeDiagInfo DiagInfo{
             Ref.Target, TouchingTokens.back().range(SM), Providers};
         MissingIncludes.push_back(std::move(DiagInfo));
       });
+  // Put possibly equal diagnostics together for deduplication.
+  // The duplicates might be from macro arguments that get expanded multiple
+  // times.
+  llvm::stable_sort(MissingIncludes, [](const MissingIncludeDiagInfo &LHS,
+                                        const MissingIncludeDiagInfo &RHS) {
+    if (LHS.Symbol == RHS.Symbol) {
+      // We can get away just by comparing the offsets as all the ranges are in
+      // main file.
+      return LHS.SymRefRange.beginOffset() < RHS.SymRefRange.beginOffset();
+    }
+    // If symbols are different we don't care about the ordering.
+    return true;
+  });
+  MissingIncludes.erase(llvm::unique(MissingIncludes), MissingIncludes.end());
   std::vector<const Inclusion *> UnusedIncludes =
       getUnused(AST, Used, /*ReferencedPublicHeaders*/ {});
   return {std::move(UnusedIncludes), std::move(MissingIncludes)};
 }
 
 std::vector<Diag> issueIncludeCleanerDiagnostics(ParsedAST &AST,
                                                  llvm::StringRef Code) {
   // Interaction is only polished for C/CPP.

clang-tools-extra/clangd/unittests/IncludeCleanerTests.cpp

)cpp");
   TU.AdditionalFiles["expander.inc"] = guard("FOO(f1);FOO(f2);");
   TU.AdditionalFiles["foo.h"] = guard("struct Foo {};");
   TU.AdditionalFiles["all.h"] = guard("#include \"foo.h\"");
 
   TU.Code = MainFile.code();
   ParsedAST AST = TU.build();
 
   auto Findings = computeIncludeCleanerFindings(AST).MissingIncludes;
-  // FIXME: Deduplicate references resulting from expansion of the same macro in
-  // multiple places.
-  EXPECT_THAT(Findings, testing::SizeIs(2));
+  EXPECT_THAT(Findings, testing::SizeIs(1));
   auto RefRange = Findings.front().SymRefRange;
   auto &SM = AST.getSourceManager();
   EXPECT_EQ(RefRange.file(), SM.getMainFileID());
   // FIXME: Point at the spelling location, rather than the include.
   EXPECT_EQ(halfOpenToRange(SM, RefRange.toCharRange(SM)), MainFile.range());
-  EXPECT_EQ(RefRange, Findings[1].SymRefRange);
+}
+
+TEST(IncludeCleaner, MissingIncludesAreUnique) {
+  Annotations MainFile(R"cpp(
+    #include "all.h"
+    FOO([[Foo]]);
+  )cpp");
+
+  TestTU TU;
+  TU.AdditionalFiles["foo.h"] = guard("struct Foo {};");
+  TU.AdditionalFiles["all.h"] = guard(R"cpp(
+    #include "foo.h"
+    #define FOO(X) X y; X z
+  )cpp");
+
+  TU.Code = MainFile.code();
+  ParsedAST AST = TU.build();
+
+  auto Findings = computeIncludeCleanerFindings(AST).MissingIncludes;
+  EXPECT_THAT(Findings, testing::SizeIs(1));
+  auto RefRange = Findings.front().SymRefRange;
+  auto &SM = AST.getSourceManager();
+  EXPECT_EQ(RefRange.file(), SM.getMainFileID());
+  EXPECT_EQ(halfOpenToRange(SM, RefRange.toCharRange(SM)), MainFile.range());
 }
 
 TEST(IncludeCleaner, NoCrash) {
   TestTU TU;
   Annotations MainCode(R"cpp(
     #include "all.h"
     void test() {
       [[1s]];