[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

561

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

561

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

561

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

561

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.h

 
 private:
   const Symbol *addDeclaration(const NamedDecl &, SymbolID,
                                bool IsMainFileSymbol);
   void addDefinition(const NamedDecl &, const Symbol &DeclSymbol);
   void processRelations(const NamedDecl &ND, const SymbolID &ID,
                         ArrayRef<index::SymbolRelation> Relations);
 
-  llvm::Optional<std::string> getIncludeHeader(llvm::StringRef QName, FileID);
+  llvm::Optional<std::string> getIncludeHeader(const Symbol &S, FileID);
   bool isSelfContainedHeader(FileID);
   // Heuristically headers that only want to be included via an umbrella.
   static bool isDontIncludeMeHeader(llvm::StringRef);
 
   // All Symbols collected from the AST.
   SymbolSlab::Builder Symbols;
   // File IDs for Symbol.IncludeHeaders.
   // The final spelling is calculated in finish().

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)) {
+      if (auto Header = getIncludeHeader(*S, Entry.second)) {
         Symbol NewSym = *S;
-        NewSym.IncludeHeaders.push_back({*Header, 1});
+        NewSym.IncludeHeaders.push_back({std::move(*Header), 1});
         Symbols.insert(NewSym);
       }
     }
 
   const auto &SM = ASTCtx->getSourceManager();
   llvm::DenseMap<FileID, std::string> URICache;
   auto GetURI = [&](FileID FID) -> llvm::Optional<std::string> {
     auto Found = URICache.find(FID);
if (auto DefLoc =
           getTokenLocation(Loc, SM, Opts, ASTCtx->getLangOpts(), FileURI))
     S.Definition = *DefLoc;
   Symbols.insert(S);
 }
 
 /// Gets a canonical include (URI of the header or <header> or "header") for
 /// header of \p FID (which should usually be the *expansion* file).
 /// Returns None if includes should not be inserted for this file.
-llvm::Optional<std::string>
-SymbolCollector::getIncludeHeader(llvm::StringRef QName, FileID FID) {
+llvm::Optional<std::string> SymbolCollector::getIncludeHeader(const Symbol &S,
+                                                              FileID FID) {
   const SourceManager &SM = ASTCtx->getSourceManager();
   const FileEntry *FE = SM.getFileEntryForID(FID);
   if (!FE || FE->getName().empty())
     return llvm::None;
   llvm::StringRef Filename = FE->getName();
   // If a file is mapped by canonical headers, use that mapping, regardless
   // of whether it's an otherwise-good header (header guards etc).
   if (Opts.Includes) {
+    llvm::SmallString<256> QName = S.Scope;
+    QName.append(S.Name);
     llvm::StringRef Canonical = Opts.Includes->mapHeader(Filename, QName);
     // If we had a mapping, always use it.
-    if (Canonical.startswith("<") || Canonical.startswith("\""))
+    if (Canonical.startswith("<") || Canonical.startswith("\"")) {
+      // Hack: there are two std::move() overloads from different headers.
+      // CanonicalIncludes returns the common one-arg one from <utility>.
+      if (Canonical == "<utility>" && S.Name == "move" &&
+          S.Signature.contains(','))
+        Canonical = "<algorithm>";
       return Canonical.str();
+    }
     if (Canonical != Filename)
       return toURI(SM, Canonical, Opts);
   }
   if (!isSelfContainedHeader(FID)) {
     // A .inc or .def file is often included into a real header to define
     // symbols (e.g. LLVM tablegen files).
     if (Filename.endswith(".inc") || Filename.endswith(".def"))
-      return getIncludeHeader(QName, SM.getFileID(SM.getIncludeLoc(FID)));
+      return getIncludeHeader(S, SM.getFileID(SM.getIncludeLoc(FID)));
     // Conservatively refuse to insert #includes to files without guards.
     return llvm::None;
   }
   // Standard case: just insert the file itself.
   return toURI(SM, Filename, Opts);
 }
 
 bool SymbolCollector::isSelfContainedHeader(FileID FID) {

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