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