[include-cleaner] Better support ambiguous std symbols

[hokein]

Summary

By special-casing them at the moment. The tooling stdlib lib doesn't
support these symbols (most important one is std::move).

[kadircet]

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

104

nit: else if

110

we also need to account for exporters, similar to findHeaders. might be worth lifting that branch to a free-function.

182

rather than doing this here and bailing out early, i think we should just augment the Headers below, after locateSymbol and findHeaders is run.

that way we'll make sure rest of the logic applies in the future without special casing (e.g. we've some fixmes for treating implementation locations for stdlib symbols as providers, in such a scenario this early exits would create non-uniformity).
it also implies we'll need to think about hints to attach here, which seems consistent with rest of the logic again (as we still assign hints to headers derived from stdlib recognizer).

so what about an alternative with a signature like: llvm::SmallVector<Hinted<Header>> headersForSpecialSymbols(S, SM, PI); then we can just initialize Headers with a call to it?

[hokein]

address comments

[hokein]

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

182

i think we should just augment the Headers below, after locateSymbol and findHeaders is run.

I'm not sure about it. Looks like this is subtle, it creates discrepancies for standard symbols, these special std symbols will have the underlying header as alternative while other normal std-recognizer symbols not. I think it would be better to be consistent for all std symbols.

[kadircet]

thanks!

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

85

we actually need to nullcheck for PI here, defaulting to PublicHeader when it isn't present.

86

nit: maybe unwrap this? e.g:

if (PI->isPrivate(..) ... ) return Hints::None;
return Hints::PublicHeader;

95

we need to nullcheck for PI here

134

can you also wrap this in applyHints(..., Hints::CompleteSymbol), similar to what locateSymbol does for rest of the stdlib symbols

[hokein]

handle the case where PI is null.

[hokein]

Thanks for the review!

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

85

ah, I think we can make it a reference, all callsites can guarantee the PI is nonnull.

clang-tools-extra/include-cleaner/lib/FindHeaders.cpp

if (const auto *ND = llvm::dyn_cast<NamedDecl>(&S.declaration()))
         return II->getName();
     return "";
   case Symbol::Macro:
     return S.macro().Name->getName();
   }
   llvm_unreachable("unhandled Symbol kind!");
 }
 
+Hints isPublicHeader(const FileEntry *FE, const PragmaIncludes *PI) {
+  return (PI->isPrivate(FE) || !PI->isSelfContained(FE)) ? Hints::None
+                                                         : Hints::PublicHeader;
+}
+llvm::SmallVector<Hinted<Header>>
+hintedHeadersForStdHeaders(llvm::ArrayRef<tooling::stdlib::Header> Headers,
+                           const SourceManager &SM, const PragmaIncludes *PI) {
+  llvm::SmallVector<Hinted<Header>> Results;
+  for (const auto &H : Headers) {
+    Results.emplace_back(H, Hints::PublicHeader);
+    for (const auto *Export : PI->getExporters(H, SM.getFileManager()))
+      Results.emplace_back(Header(Export), isPublicHeader(Export, PI));
+  }
+  // StandardLibrary returns headers in preference order, so only mark the
+  // first.
+  if (!Results.empty())
+    Results.front().Hint |= Hints::PreferredHeader;
+  return Results;
+}
+
+// Special-case the ambiguous standard library symbols (e.g. std::move) which
+// are not supported by the tooling stdlib lib.
+llvm::SmallVector<Hinted<Header>>
+headersForSpecialSymbol(const Symbol &S, const SourceManager &SM,
+                        const PragmaIncludes *PI) {
+  if (S.kind() != Symbol::Declaration || !S.declaration().isInStdNamespace())
+    return {};
+
+  const auto *FD = S.declaration().getAsFunction();
+  if (!FD)
+    return {};
+
+  llvm::StringRef FName = FD->getName();
+  llvm::SmallVector<tooling::stdlib::Header> Headers;
+  if (FName == "move") {
+    if (FD->getNumParams() == 1)
+      // move(T&& t)
+      Headers.push_back(*tooling::stdlib::Header::named("<utility>"));
+    if (FD->getNumParams() == 3)
+      // move(InputIt first, InputIt last, OutputIt dest);
+      Headers.push_back(*tooling::stdlib::Header::named("<algorithm>"));
+  } else if (FName == "remove") {
+    if (FD->getNumParams() == 1)
+      // remove(const char*);
+      Headers.push_back(*tooling::stdlib::Header::named("<cstdio>"));
+    if (FD->getNumParams() == 3)
+      // remove(ForwardIt first, ForwardIt last, const T& value);
+      Headers.push_back(*tooling::stdlib::Header::named("<algorithm>"));
+  }
+  return hintedHeadersForStdHeaders(Headers, SM, PI);
+}
+
 } // namespace
 
 llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
                                               const SourceManager &SM,
                                               const PragmaIncludes *PI) {
-  auto IsPublicHeader = [&PI](const FileEntry *FE) {
-    return (PI->isPrivate(FE) || !PI->isSelfContained(FE))
-               ? Hints::None
-               : Hints::PublicHeader;
-  };
   llvm::SmallVector<Hinted<Header>> Results;
   switch (Loc.kind()) {
   case SymbolLocation::Physical: {
     FileID FID = SM.getFileID(SM.getExpansionLoc(Loc.physical()));
     const FileEntry *FE = SM.getFileEntryForID(FID);
     if (!FE)
       return {};
     if (!PI)
       return {{FE, Hints::PublicHeader}};
     while (FE) {
-      Hints CurrentHints = IsPublicHeader(FE);
+      Hints CurrentHints = isPublicHeader(FE, PI);
       Results.emplace_back(FE, CurrentHints);
       // FIXME: compute transitive exporter headers.
       for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
-        Results.emplace_back(Export, IsPublicHeader(Export));
+        Results.emplace_back(Export, isPublicHeader(Export, PI));
 
       if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) {
         Results.emplace_back(Verbatim,
                              Hints::PublicHeader | Hints::PreferredHeader);
         break;
       }
       if (PI->isSelfContained(FE) || FID == SM.getMainFileID())
         break;
 
       // Walkup the include stack for non self-contained headers.
       FID = SM.getDecomposedIncludedLoc(FID).first;
       FE = SM.getFileEntryForID(FID);
     }
     return Results;
   }
   case SymbolLocation::Standard: {
-    for (const auto &H : Loc.standard().headers()) {
-      Results.emplace_back(H, Hints::PublicHeader);
-      for (const auto *Export : PI->getExporters(H, SM.getFileManager()))
-        Results.emplace_back(Header(Export), IsPublicHeader(Export));
-    }
-    // StandardLibrary returns headers in preference order, so only mark the
-    // first.
-    if (!Results.empty())
-      Results.front().Hint |= Hints::PreferredHeader;
-    return Results;
+    return hintedHeadersForStdHeaders(Loc.standard().headers(), SM, PI);
   }
   }
   llvm_unreachable("unhandled SymbolLocation kind!");
 }
 
 llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
                                            const SourceManager &SM,
                                            const PragmaIncludes *PI) {
   // Get headers for all the locations providing Symbol. Same header can be
   // reached through different traversals, deduplicate those into a single
   // Header by merging their hints.
-  llvm::SmallVector<Hinted<Header>> Headers;
+  llvm::SmallVector<Hinted<Header>> Headers =
+      headersForSpecialSymbol(S, SM, PI);
+  if (Headers.empty())
     for (auto &Loc : locateSymbol(S))
       Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hint));
   // If two Headers probably refer to the same file (e.g. Verbatim(foo.h) and
   // Physical(/path/to/foo.h), we won't deduplicate them or merge their hints
   llvm::stable_sort(
       Headers, [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
         return static_cast<Header>(LHS) < static_cast<Header>(RHS);
       });
   auto *Write = Headers.begin();
   for (auto *Read = Headers.begin(); Read != Headers.end(); ++Write) {

clang-tools-extra/include-cleaner/unittests/FindHeadersTest.cpp

EXPECT_THAT(findHeaders("private.h"),
               UnorderedElementsAre(
                   HintedHeader(physicalHeader("private.h"), Hints::None),
                   HintedHeader(Header("\"public.h\""),
                                Hints::PreferredHeader | Hints::PublicHeader)));
 }
 
 class HeadersForSymbolTest : public FindHeadersTest {
 protected:
-  llvm::SmallVector<Header> headersForFoo() {
+  llvm::SmallVector<Header> headersFor(llvm::StringRef Name) {
     struct Visitor : public RecursiveASTVisitor<Visitor> {
       const NamedDecl *Out = nullptr;
+      llvm::StringRef Name;
+      Visitor(llvm::StringRef Name) : Name(Name) {}
       bool VisitNamedDecl(const NamedDecl *ND) {
-        if (ND->getName() == "foo") {
+        if (auto *TD = ND->getDescribedTemplate())
+          ND = TD;
+
+        if (ND->getName() == Name) {
           EXPECT_TRUE(Out == nullptr || Out == ND->getCanonicalDecl())
-              << "Found multiple matches for foo.";
+              << "Found multiple matches for " << Name << ".";
           Out = cast<NamedDecl>(ND->getCanonicalDecl());
         }
         return true;
       }
     };
-    Visitor V;
+    Visitor V(Name);
     V.TraverseDecl(AST->context().getTranslationUnitDecl());
     if (!V.Out)
-      ADD_FAILURE() << "Couldn't find any decls named foo.";
+      ADD_FAILURE() << "Couldn't find any decls named " << Name << ".";
     assert(V.Out);
     return headersForSymbol(*V.Out, AST->sourceManager(), &PI);
   }
+  llvm::SmallVector<Header> headersForFoo() { return headersFor("foo"); }
 };
 
 TEST_F(HeadersForSymbolTest, Deduplicates) {
   Inputs.Code = R"cpp(
     #include "foo.h"
   )cpp";
   Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
     // IWYU pragma: private, include "foo.h"
TEST_F(HeadersForSymbolTest, PreferPublicOverNameMatchOnPrivate) {
   Inputs.ExtraFiles["foo.h"] = guard(R"cpp(
     // IWYU pragma: private, include "public.h"
     struct foo {};
   )cpp");
   buildAST();
   EXPECT_THAT(headersForFoo(), ElementsAre(Header(StringRef("\"public.h\"")),
                                            physicalHeader("foo.h")));
 }
+
+TEST_F(HeadersForSymbolTest, AmbiguousStdSymbols) {
+  struct {
+    llvm::StringRef Code;
+    llvm::StringRef Name;
+
+    llvm::StringRef ExpectedHeader;
+  } TestCases[] = {
+      {
+          R"cpp(
+            namespace std {
+             template <typename InputIt, typename OutputIt>
+             constexpr OutputIt move(InputIt first, InputIt last, OutputIt dest);
+            })cpp",
+          "move",
+          "<algorithm>",
+      },
+      {
+          R"cpp(
+            namespace std {
+              template<typename T> constexpr T move(T&& t) noexcept;
+            })cpp",
+          "move",
+          "<utility>",
+      },
+      {
+          R"cpp(
+            namespace std {
+              template<class ForwardIt, class T>
+              ForwardIt remove(ForwardIt first, ForwardIt last, const T& value);
+            })cpp",
+          "remove",
+          "<algorithm>",
+      },
+      {
+          "namespace std { int remove(const char*); }",
+          "remove",
+          "<cstdio>",
+      },
+  };
+
+  for (const auto &T : TestCases) {
+    Inputs.Code = T.Code;
+    buildAST();
+    EXPECT_THAT(headersFor(T.Name),
+                UnorderedElementsAre(
+                    Header(*tooling::stdlib::Header::named(T.ExpectedHeader))));
+  }
+}
+
 } // namespace
 } // namespace clang::include_cleaner