[include-cleaner] Only ignore builtins without a header

[kadircet]

Summary

Certain standard library functions (e.g. std::move) are also implemented
as builtins. This patch moves filtering logic to the symbol->header
mapping phase to rather generate these references without any providers
only when we don't have a mapping.
That way we can also map them to header names mentioned in the builtin
mappings.

[hokein]

Thanks. I was surprised to see that some standard library symbols are treated as builtin symbols.

I think the current approach is better (e.g. clangd's hover on __builtin_popcount() will not give some arbitrary header providers).

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

169

I think it would be clearer if we move this FIXME after the following if branch.

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

 //===--- FindHeaders.cpp --------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "AnalysisInternal.h"
 #include "TypesInternal.h"
 #include "clang-include-cleaner/Record.h"
 #include "clang-include-cleaner/Types.h"
+#include "clang/AST/ASTContext.h"
 #include "clang/AST/Decl.h"
 #include "clang/AST/DeclBase.h"
+#include "clang/Basic/Builtins.h"
 #include "clang/Basic/FileEntry.h"
 #include "clang/Basic/SourceLocation.h"
 #include "clang/Basic/SourceManager.h"
 #include "clang/Tooling/Inclusions/StandardLibrary.h"
+#include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallVector.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ErrorHandling.h"
-#include <string>
+#include <optional>
 #include <utility>
 
 namespace clang::include_cleaner {
 namespace {
 llvm::SmallVector<Hinted<Header>>
 applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
   for (auto &Header : Headers)
     Header.Hint |= H;
hintedHeadersForStdHeaders(llvm::ArrayRef<tooling::stdlib::Header> Headers,
   }
   // 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())
+// Symbol to header mapping for std::move and std::remove, based on number of
+// parameters.
+std::optional<tooling::stdlib::Header>
+headerForAmbiguousStdSymbol(const NamedDecl *ND) {
+  if (!ND->isInStdNamespace())
     return {};
-
-  const auto *FD = S.declaration().getAsFunction();
+  const auto *FD = ND->getAsFunction();
   if (!FD)
-    return {};
-
-  llvm::StringRef FName = symbolName(S);
-  llvm::SmallVector<tooling::stdlib::Header> Headers;
+    return std::nullopt;
+  llvm::StringRef FName = symbolName(*ND);
   if (FName == "move") {
     if (FD->getNumParams() == 1)
       // move(T&& t)
-      Headers.push_back(*tooling::stdlib::Header::named("<utility>"));
+      return tooling::stdlib::Header::named("<utility>");
     if (FD->getNumParams() == 3)
       // move(InputIt first, InputIt last, OutputIt dest);
-      Headers.push_back(*tooling::stdlib::Header::named("<algorithm>"));
+      return tooling::stdlib::Header::named("<algorithm>");
   } else if (FName == "remove") {
     if (FD->getNumParams() == 1)
       // remove(const char*);
-      Headers.push_back(*tooling::stdlib::Header::named("<cstdio>"));
+      return 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 applyHints(hintedHeadersForStdHeaders(Headers, SM, PI),
+      return tooling::stdlib::Header::named("<algorithm>");
+  }
+  return std::nullopt;
+
+// Special-case symbols without proper locations, like the ambiguous standard
+// library symbols (e.g. std::move) or builtin declarations.
+std::optional<llvm::SmallVector<Hinted<Header>>>
+headersForSpecialSymbol(const Symbol &S, const SourceManager &SM,
+                        const PragmaIncludes *PI) {
+  // Our special casing logic only deals with decls, so bail out early for
+  // macros.
+  if (S.kind() != Symbol::Declaration)
+    return std::nullopt;
+  const auto *ND = llvm::cast<NamedDecl>(&S.declaration());
+  // We map based on names, so again bail out early if there are no names.
+  if (!ND)
+    return std::nullopt;
+  auto *II = ND->getIdentifier();
+  if (!II)
+    return std::nullopt;
+
+  // Check first for symbols that are part of our stdlib mapping. As we have
+  // header names for those.
+  if (auto Header = headerForAmbiguousStdSymbol(ND)) {
+    return applyHints(hintedHeadersForStdHeaders({*Header}, SM, PI),
                       Hints::CompleteSymbol);
   }
 
+  // Now check for builtin symbols, we shouldn't suggest any headers for ones
+  // without any headers.
+  if (auto ID = II->getBuiltinID()) {
+    const char *BuiltinHeader =
+        ND->getASTContext().BuiltinInfo.getHeaderName(ID);
+    if (!BuiltinHeader)
+      return llvm::SmallVector<Hinted<Header>>{};
+    // FIXME: Use the header mapping for builtins with a known header.
+  }
+  return std::nullopt;
+}
+
 } // namespace
 
 llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
                                               const SourceManager &SM,
                                               const PragmaIncludes *PI) {
   llvm::SmallVector<Hinted<Header>> Results;
   switch (Loc.kind()) {
   case SymbolLocation::Physical: {

 }
 
 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 =
-      headersForSpecialSymbol(S, SM, PI);
-  if (Headers.empty())
+  llvm::SmallVector<Hinted<Header>> Headers;
+  if (auto SpecialHeaders = headersForSpecialSymbol(S, SM, PI)) {
+    Headers = std::move(*SpecialHeaders);
+  } else {
     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/lib/WalkAST.cpp

 
 class ASTWalker : public RecursiveASTVisitor<ASTWalker> {
   DeclCallback Callback;
 
   void report(SourceLocation Loc, NamedDecl *ND,
               RefType RT = RefType::Explicit) {
     if (!ND || Loc.isInvalid())
       return;
-    // Don't report builtin symbols.
-    if (const auto *II = ND->getIdentifier(); II && II->getBuiltinID() > 0)
-      return;
     Callback(Loc, *cast<NamedDecl>(ND->getCanonicalDecl()), RT);
   }
 
   NamedDecl *resolveTemplateName(TemplateName TN) {
     // For using-templates, only mark the alias.
     if (auto *USD = TN.getAsUsingShadowDecl())
       return USD;
     return TN.getAsTemplateDecl();

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

 TEST_F(WalkUsedTest, Basic) {
   llvm::Annotations Code(R"cpp(
   #include "header.h"
   #include "private.h"
 
   void $bar^bar($private^Private $p^p) {
     $foo^foo();
     std::$vector^vector $vconstructor^$v^v;
+    $builtin^__builtin_popcount(1);
+    std::$move^move(3);
   }
   )cpp");
   Inputs.Code = Code.code();
   Inputs.ExtraFiles["header.h"] = guard(R"cpp(
   void foo();
-  namespace std { class vector {}; }
+  namespace std { class vector {}; int&& move(int&&); }
   )cpp");
   Inputs.ExtraFiles["private.h"] = guard(R"cpp(
     // IWYU pragma: private, include "path/public.h"
     class Private {};
   )cpp");
 
   TestAST AST(Inputs);
   auto &SM = AST.sourceManager();
   auto HeaderFile = Header(AST.fileManager().getFile("header.h").get());
   auto PrivateFile = Header(AST.fileManager().getFile("private.h").get());
   auto PublicFile = Header("\"path/public.h\"");
   auto MainFile = Header(SM.getFileEntryForID(SM.getMainFileID()));
   auto VectorSTL = Header(*tooling::stdlib::Header::named("<vector>"));
+  auto UtilitySTL = Header(*tooling::stdlib::Header::named("<utility>"));
   EXPECT_THAT(
       offsetToProviders(AST, SM),
       UnorderedElementsAre(
           Pair(Code.point("bar"), UnorderedElementsAre(MainFile)),
           Pair(Code.point("p"), UnorderedElementsAre(MainFile)),
           Pair(Code.point("private"),
                UnorderedElementsAre(PublicFile, PrivateFile)),
           Pair(Code.point("foo"), UnorderedElementsAre(HeaderFile)),
           Pair(Code.point("vector"), UnorderedElementsAre(VectorSTL)),
           Pair(Code.point("vconstructor"), UnorderedElementsAre(VectorSTL)),
-          Pair(Code.point("v"), UnorderedElementsAre(MainFile))
-          ));
+          Pair(Code.point("v"), UnorderedElementsAre(MainFile)),
+          Pair(Code.point("builtin"), testing::IsEmpty()),
+          Pair(Code.point("move"), UnorderedElementsAre(UtilitySTL))));
 }
 
 TEST_F(WalkUsedTest, MultipleProviders) {
   llvm::Annotations Code(R"cpp(
   #include "header1.h"
   #include "header2.h"
   void foo();
 

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

 }
 
 TEST(WalkAST, Enums) {
   testWalk("enum E { $explicit^A = 42, B = 43 };", "int e = ^A;");
   testWalk("enum class $explicit^E : int;", "enum class ^E : int {};");
   testWalk("enum class E : int {};", "enum class ^E : int ;");
 }
 
-TEST(WalkAST, BuiltinSymbols) {
-  testWalk(R"cpp(
-    extern "C" int __builtin_popcount(unsigned int) noexcept;
-  )cpp", "int x = ^__builtin_popcount(1);");
-}
-
 } // namespace
 } // namespace clang::include_cleaner