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

   1 //===--- FindHeaders.cpp --------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "AnalysisInternal.h"
  10 #include "TypesInternal.h"
  11 #include "clang-include-cleaner/Record.h"
  12 #include "clang-include-cleaner/Types.h"
  13 #include "clang/AST/ASTContext.h"
  14 #include "clang/AST/Decl.h"
  15 #include "clang/AST/DeclBase.h"
  16 #include "clang/AST/DeclCXX.h"
  17 #include "clang/Basic/Builtins.h"
  18 #include "clang/Basic/FileEntry.h"
  19 #include "clang/Basic/SourceLocation.h"
  20 #include "clang/Basic/SourceManager.h"
  21 #include "clang/Tooling/Inclusions/StandardLibrary.h"
  22 #include "llvm/ADT/ArrayRef.h"
  23 #include "llvm/ADT/STLExtras.h"
  24 #include "llvm/ADT/SmallVector.h"
  25 #include "llvm/ADT/StringRef.h"
  26 #include "llvm/Support/Casting.h"
  27 #include "llvm/Support/ErrorHandling.h"
  28 #include <optional>
  29 #include <queue>
  30 #include <set>
  31 #include <utility>
  32
  33 namespace clang::include_cleaner {
  34 namespace {
  35 llvm::SmallVector<Hinted<Header>>
  36 applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
  37   for (auto &Header : Headers)
  38     Header.Hint |= H;
  39   return Headers;
  40 }
  41
  42 llvm::SmallVector<Header> ranked(llvm::SmallVector<Hinted<Header>> Headers) {
  43   llvm::stable_sort(llvm::reverse(Headers),
  44                     [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
  45                       return LHS < RHS;
  46                     });
  47   return llvm::SmallVector<Header>(Headers.begin(), Headers.end());
  48 }
  49
  50 // Return the basename from a verbatim header spelling, leaves only the file
  51 // name.
  52 llvm::StringRef basename(llvm::StringRef Header) {
  53   Header = Header.trim("<>\"");
  54   Header = llvm::sys::path::filename(Header);
  55   // Drop everything after first `.` (dot).
  56   // foo.h -> foo
  57   // foo.cu.h -> foo
  58   Header = Header.substr(0, Header.find('.'));
  59   return Header;
  60 }
  61
  62 // Check if spelling of \p H matches \p DeclName.
  63 bool nameMatch(llvm::StringRef DeclName, Header H) {
  64   switch (H.kind()) {
  65   case Header::Physical:
  66     return basename(H.physical().getName()).equals_insensitive(DeclName);
  67   case Header::Standard:
  68     return basename(H.standard().name()).equals_insensitive(DeclName);
  69   case Header::Verbatim:
  70     return basename(H.verbatim()).equals_insensitive(DeclName);
  71   }
  72   llvm_unreachable("unhandled Header kind!");
  73 }
  74
  75 llvm::StringRef symbolName(const Symbol &S) {
  76   switch (S.kind()) {
  77   case Symbol::Declaration:
  78     // Unnamed decls like operators and anonymous structs won't get any name
  79     // match.
  80     if (const auto *ND = llvm::dyn_cast<NamedDecl>(&S.declaration()))
  81       if (auto *II = ND->getIdentifier())
  82         return II->getName();
  83     return "";
  84   case Symbol::Macro:
  85     return S.macro().Name->getName();
  86   }
  87   llvm_unreachable("unhandled Symbol kind!");
  88 }
  89
  90 Hints isPublicHeader(const FileEntry *FE, const PragmaIncludes &PI) {
  91   if (PI.isPrivate(FE) || !PI.isSelfContained(FE))
  92     return Hints::None;
  93   return Hints::PublicHeader;
  94 }
  95
  96 llvm::SmallVector<Hinted<Header>>
  97 hintedHeadersForStdHeaders(llvm::ArrayRef<tooling::stdlib::Header> Headers,
  98                            const SourceManager &SM, const PragmaIncludes *PI) {
  99   llvm::SmallVector<Hinted<Header>> Results;
 100   for (const auto &H : Headers) {
 101     Results.emplace_back(H, Hints::PublicHeader | Hints::OriginHeader);
 102     if (!PI)
 103       continue;
 104     for (FileEntryRef Export : PI->getExporters(H, SM.getFileManager()))
 105       Results.emplace_back(Header(Export), isPublicHeader(Export, *PI));
 106   }
 107   // StandardLibrary returns headers in preference order, so only mark the
 108   // first.
 109   if (!Results.empty())
 110     Results.front().Hint |= Hints::PreferredHeader;
 111   return Results;
 112 }
 113
 114 // Symbol to header mapping for std::move and std::remove, based on number of
 115 // parameters.
 116 std::optional<tooling::stdlib::Header>
 117 headerForAmbiguousStdSymbol(const NamedDecl *ND) {
 118   if (!ND->isInStdNamespace())
 119     return {};
 120   if (auto* USD = llvm::dyn_cast<UsingShadowDecl>(ND))
 121     ND = USD->getTargetDecl();
 122   const auto *FD = ND->getAsFunction();
 123   if (!FD)
 124     return std::nullopt;
 125   llvm::StringRef FName = symbolName(*ND);
 126   if (FName == "move") {
 127     if (FD->getNumParams() == 1)
 128       // move(T&& t)
 129       return tooling::stdlib::Header::named("<utility>");
 130     if (FD->getNumParams() == 3 || FD->getNumParams() == 4)
 131       // move(InputIt first, InputIt last, OutputIt dest);
 132       // move(ExecutionPolicy&& policy, ForwardIt1 first,
 133       // ForwardIt1 last, ForwardIt2 d_first);
 134       return tooling::stdlib::Header::named("<algorithm>");
 135   } else if (FName == "remove") {
 136     if (FD->getNumParams() == 1)
 137       // remove(const char*);
 138       return tooling::stdlib::Header::named("<cstdio>");
 139     if (FD->getNumParams() == 3)
 140       // remove(ForwardIt first, ForwardIt last, const T& value);
 141       return tooling::stdlib::Header::named("<algorithm>");
 142   }
 143   return std::nullopt;
 144 }
 145
 146 // Special-case symbols without proper locations, like the ambiguous standard
 147 // library symbols (e.g. std::move) or builtin declarations.
 148 std::optional<llvm::SmallVector<Hinted<Header>>>
 149 headersForSpecialSymbol(const Symbol &S, const SourceManager &SM,
 150                         const PragmaIncludes *PI) {
 151   // Our special casing logic only deals with decls, so bail out early for
 152   // macros.
 153   if (S.kind() != Symbol::Declaration)
 154     return std::nullopt;
 155   const auto *ND = llvm::cast<NamedDecl>(&S.declaration());
 156   // We map based on names, so again bail out early if there are no names.
 157   if (!ND)
 158     return std::nullopt;
 159   auto *II = ND->getIdentifier();
 160   if (!II)
 161     return std::nullopt;
 162
 163   // Check first for symbols that are part of our stdlib mapping. As we have
 164   // header names for those.
 165   if (auto Header = headerForAmbiguousStdSymbol(ND)) {
 166     return applyHints(hintedHeadersForStdHeaders({*Header}, SM, PI),
 167                       Hints::CompleteSymbol);
 168   }
 169
 170   // Now check for builtin symbols, we shouldn't suggest any headers for ones
 171   // without any headers.
 172   if (auto ID = II->getBuiltinID()) {
 173     const char *BuiltinHeader =
 174         ND->getASTContext().BuiltinInfo.getHeaderName(ID);
 175     if (!BuiltinHeader)
 176       return llvm::SmallVector<Hinted<Header>>{};
 177     // FIXME: Use the header mapping for builtins with a known header.
 178   }
 179   return std::nullopt;
 180 }
 181
 182 } // namespace
 183
 184 llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
 185                                               const SourceManager &SM,
 186                                               const PragmaIncludes *PI) {
 187   llvm::SmallVector<Hinted<Header>> Results;
 188   switch (Loc.kind()) {
 189   case SymbolLocation::Physical: {
 190     FileID FID = SM.getFileID(SM.getExpansionLoc(Loc.physical()));
 191     OptionalFileEntryRef FE = SM.getFileEntryRefForID(FID);
 192     if (!FE)
 193       return {};
 194     if (!PI)
 195       return {{*FE, Hints::PublicHeader | Hints::OriginHeader}};
 196     bool IsOrigin = true;
 197     std::queue<FileEntryRef> Exporters;
 198     while (FE) {
 199       Results.emplace_back(*FE,
 200                            isPublicHeader(*FE, *PI) |
 201                                (IsOrigin ? Hints::OriginHeader : Hints::None));
 202       for (FileEntryRef Export : PI->getExporters(*FE, SM.getFileManager()))
 203         Exporters.push(Export);
 204
 205       if (auto Verbatim = PI->getPublic(*FE); !Verbatim.empty()) {
 206         Results.emplace_back(Verbatim,
 207                              Hints::PublicHeader | Hints::PreferredHeader);
 208         break;
 209       }
 210       if (PI->isSelfContained(*FE) || FID == SM.getMainFileID())
 211         break;
 212
 213       // Walkup the include stack for non self-contained headers.
 214       FID = SM.getDecomposedIncludedLoc(FID).first;
 215       FE = SM.getFileEntryRefForID(FID);
 216       IsOrigin = false;
 217     }
 218     // Now traverse provider trees rooted at exporters.
 219     // Note that we only traverse export edges, and ignore private -> public
 220     // mappings, as those pragmas apply to exporter, and not the main provider
 221     // being exported in this header.
 222     std::set<const FileEntry *> SeenExports;
 223     while (!Exporters.empty()) {
 224       FileEntryRef Export = Exporters.front();
 225       Exporters.pop();
 226       if (!SeenExports.insert(Export).second) // In case of cyclic exports
 227         continue;
 228       Results.emplace_back(Export, isPublicHeader(Export, *PI));
 229       for (FileEntryRef Export : PI->getExporters(Export, SM.getFileManager()))
 230         Exporters.push(Export);
 231     }
 232     return Results;
 233   }
 234   case SymbolLocation::Standard: {
 235     return hintedHeadersForStdHeaders(Loc.standard().headers(), SM, PI);
 236   }
 237   }
 238   llvm_unreachable("unhandled SymbolLocation kind!");
 239 }
 240
 241 llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
 242                                            const SourceManager &SM,
 243                                            const PragmaIncludes *PI) {
 244   // Get headers for all the locations providing Symbol. Same header can be
 245   // reached through different traversals, deduplicate those into a single
 246   // Header by merging their hints.
 247   llvm::SmallVector<Hinted<Header>> Headers;
 248   if (auto SpecialHeaders = headersForSpecialSymbol(S, SM, PI)) {
 249     Headers = std::move(*SpecialHeaders);
 250   } else {
 251     for (auto &Loc : locateSymbol(S))
 252       Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hint));
 253   }
 254   // If two Headers probably refer to the same file (e.g. Verbatim(foo.h) and
 255   // Physical(/path/to/foo.h), we won't deduplicate them or merge their hints
 256   llvm::stable_sort(
 257       Headers, [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
 258         return static_cast<Header>(LHS) < static_cast<Header>(RHS);
 259       });
 260   auto *Write = Headers.begin();
 261   for (auto *Read = Headers.begin(); Read != Headers.end(); ++Write) {
 262     *Write = *Read++;
 263     while (Read != Headers.end() &&
 264            static_cast<Header>(*Write) == static_cast<Header>(*Read)) {
 265       Write->Hint |= Read->Hint;
 266       ++Read;
 267     }
 268   }
 269   Headers.erase(Write, Headers.end());
 270
 271   // Add name match hints to deduplicated providers.
 272   llvm::StringRef SymbolName = symbolName(S);
 273   for (auto &H : Headers) {
 274     // Don't apply name match hints to standard headers as the standard headers
 275     // are already ranked in the stdlib mapping.
 276     if (H.kind() == Header::Standard)
 277       continue;
 278     // Don't apply name match hints to exporting headers. As they usually have
 279     // names similar to the original header, e.g. foo_wrapper/foo.h vs
 280     // foo/foo.h, but shouldn't be preferred (unless marked as the public
 281     // interface).
 282     if ((H.Hint & Hints::OriginHeader) == Hints::None)
 283       continue;
 284     if (nameMatch(SymbolName, H))
 285       H.Hint |= Hints::PreferredHeader;
 286   }
 287
 288   // FIXME: Introduce a MainFile header kind or signal and boost it.
 289   return ranked(std::move(Headers));
 290 }
 291 } // namespace clang::include_cleaner