[clangd] Disambiguate overloads of std::move for header insertion.

[sammccall]

Summary

Up until now, we relied on matching the filename.
This depends on unstable details of libstdc++ and doesn't work well on other
stdlibs. Also we'd like to remove it (see D88204).

[kadircet]

clang-tools-extra/clangd/index/SymbolCollector.cpp

563

i think this should live inside CanonicalIncludes. What about changing mapHeader to take in an llvm::Optional<size_t> NumParams or llvm::Optional<llvm::StringRef> Signature ?

That way we can actually get rid of the ambiguity caused by all of the overloads. I am not sure if number of parameters is always going to be enough tho so Signature might be a safer bet with some canonicalization so that we can match the version in cppreference.

(I would prefer the solution above, but I am also fine with moving this into SymbolCollector::getIncludeHeader with a FIXME.)

[sammccall]

clang-tools-extra/clangd/index/SymbolCollector.cpp

563

That's kind of the point of this patch, I think this one special case isn't worth making that library more complicated.

Would also be happy with just always suggesting <utility>, or never suggesting anything, though.

[kadircet]

Thanks, LGTM! As you mentioned I believe std::move is common enough to deserve the special casing.

clang-tools-extra/clangd/index/SymbolCollector.cpp

563

Makes sense, I was suggesting SymbolCollector::getIncludeHeader rather than SymbolCollector::finish to keep the logic in here less complicated. But I am fine if you don't want to make changes to the singature. (It is unfortunate that getIncludeHeader is a private member instead of a free helper in here anyways.)

[sammccall]

In D88885#2314596, @kadircet wrote:

Thanks, LGTM! As you mentioned I believe std::move is common enough to deserve the special casing.

Common enough and also literally the only case AFAIK (hopefully the committee is friendly enough not to add more in future).
That combination pushes me towards preferring this hack at least for now...

clang-tools-extra/clangd/index/SymbolCollector.cpp

563

Oh right, of course. Done.

Yeah it's unfortunate, it's because isSelfContainedHeader is an expensive check that we have to cache, so there's a bunch of state it needs access to.

[sammccall]

Refactor the hack into a more appropriate place.

[kadircet]

clang-tools-extra/clangd/index/SymbolCollector.cpp

557

this one is no longer needed.

[sammccall]

clang-tools-extra/clangd/index/SymbolCollector.cpp

557

whoops, fixed in 6ee47f552ba7654a0997c8deb71f65d0d91f4a28

clang-tools-extra/clangd/index/CanonicalIncludes.cpp

collectIWYUHeaderMaps(CanonicalIncludes *Includes) {
   return std::make_unique<PragmaCommentHandler>(Includes);
 }
 
 void CanonicalIncludes::addSystemHeadersMapping(const LangOptions &Language) {
   if (Language.CPlusPlus) {
     static const auto *Symbols = new llvm::StringMap<llvm::StringRef>({
 #define SYMBOL(Name, NameSpace, Header) {#NameSpace #Name, #Header},
 #include "StdSymbolMap.inc"
+        // There are two std::move()s, this is by far the most common.
+        SYMBOL(move, std::, <utility>)
 #undef SYMBOL
     });
     StdSymbolMapping = Symbols;
   } else if (Language.C11) {
     static const auto *CSymbols = new llvm::StringMap<llvm::StringRef>({
 #define SYMBOL(Name, NameSpace, Header) {#Name, #Header},
 #include "CSymbolMap.inc"
 #undef SYMBOL

clang-tools-extra/clangd/index/SymbolCollector.cpp

for (const IdentifierInfo *II : ReferencedMacros) {
         if (auto ID = getSymbolID(II->getName(), MI, PP->getSourceManager()))
           IncRef(*ID);
     }
   }
   // Fill in IncludeHeaders.
   // We delay this until end of TU so header guards are all resolved.
   // Symbols in slabs aren' mutable, so insert() has to walk all the strings
   // :-(
   llvm::SmallString<256> QName;
   for (const auto &Entry : IncludeFiles)
     if (const Symbol *S = Symbols.find(Entry.first)) {
       QName = S->Scope;
       QName.append(S->Name);
       if (auto Header = getIncludeHeader(QName, Entry.second)) {
+        // Hack: there are two std::move() overloads from different headers.
+        // CanonicalIncludes returns the common one-arg one from <utility>.
+        if (S->Name == "move" && S->Scope == "std::" &&
+            S->Signature.contains(','))
+          *Header = "<algorithm>";
         Symbol NewSym = *S;
         NewSym.IncludeHeaders.push_back({*Header, 1});
         Symbols.insert(NewSym);
       }
     }
 
   const auto &SM = ASTCtx->getSourceManager();
   llvm::DenseMap<FileID, std::string> URICache;

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

TEST(CanonicalIncludesTest, CXXStandardLibrary) {
   CanonicalIncludes CI;
   auto Language = LangOptions();
   Language.CPlusPlus = true;
   CI.addSystemHeadersMapping(Language);
 
   // Usual standard library symbols are mapped correctly.
   EXPECT_EQ("<vector>", CI.mapHeader("path/vector.h", "std::vector"));
   EXPECT_EQ("<cstdio>", CI.mapHeader("path/stdio.h", "std::printf"));
-  // std::move is ambiguous, currently mapped only based on path
-  EXPECT_EQ("<utility>", CI.mapHeader("libstdc++/bits/move.h", "std::move"));
-  EXPECT_EQ("path/utility.h", CI.mapHeader("path/utility.h", "std::move"));
+  // std::move is ambiguous, currently always mapped to <utility>
+  EXPECT_EQ("<utility>",
+            CI.mapHeader("libstdc++/bits/stl_algo.h", "std::move"));
   // Unknown std symbols aren't mapped.
   EXPECT_EQ("foo/bar.h", CI.mapHeader("foo/bar.h", "std::notathing"));
   // iosfwd declares some symbols it doesn't own.
   EXPECT_EQ("<ostream>", CI.mapHeader("iosfwd", "std::ostream"));
   // And (for now) we assume it owns the others.
   EXPECT_EQ("<iosfwd>", CI.mapHeader("iosfwd", "std::notwathing"));
 }
 

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

 
 TEST_F(SymbolCollectorTest, CanonicalSTLHeader) {
   CollectorOpts.CollectIncludePath = true;
   CanonicalIncludes Includes;
   auto Language = LangOptions();
   Language.CPlusPlus = true;
   Includes.addSystemHeadersMapping(Language);
   CollectorOpts.Includes = &Includes;
-  runSymbolCollector("namespace std { class string {}; }", /*Main=*/"");
-  EXPECT_THAT(Symbols,
-              Contains(AllOf(QName("std::string"), DeclURI(TestHeaderURI),
-                             IncludeHeader("<string>"))));
+  runSymbolCollector(
+      R"cpp(
+      namespace std {
+        class string {};
+        // Move overloads have special handling.
+        template <typename T> T&& move(T&&);
+        template <typename I, typename O> O move(I, I, O);
+      }
+      )cpp",
+      /*Main=*/"");
+  for (const auto &S : Symbols)
+    llvm::errs() << S.Scope << S.Name << " in " << S.IncludeHeaders.size()
+                 << "\n";
+  EXPECT_THAT(
+      Symbols,
+      UnorderedElementsAre(
+          QName("std"),
+          AllOf(QName("std::string"), DeclURI(TestHeaderURI),
+                IncludeHeader("<string>")),
+          AllOf(Labeled("move(T &&)"), IncludeHeader("<utility>")),
+          AllOf(Labeled("move(I, I, O)"), IncludeHeader("<algorithm>"))));
 }
 
 TEST_F(SymbolCollectorTest, IWYUPragma) {
   CollectorOpts.CollectIncludePath = true;
   CanonicalIncludes Includes;
   PragmaHandler = collectIWYUHeaderMaps(&Includes);
   CollectorOpts.Includes = &Includes;
   const std::string Header = R"(