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