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
33namespace clang::include_cleaner {
34namespace {
35llvm::SmallVector<Hinted<Header>>
36applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
37 for (auto &Header : Headers)
38 Header.Hint |= H;
39 return Headers;
40}
41
42llvm::SmallVector<Header> ranked(llvm::SmallVector<Hinted<Header>> Headers) {
43 llvm::stable_sort(Range: llvm::reverse(C&: Headers),
44 C: [](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.
52llvm::StringRef basename(llvm::StringRef Header) {
53 Header = Header.trim(Chars: "<>\"");
54 Header = llvm::sys::path::filename(path: Header);
55 // Drop everything after first `.` (dot).
56 // foo.h -> foo
57 // foo.cu.h -> foo
58 Header = Header.substr(Start: 0, N: Header.find(C: '.'));
59 return Header;
60}
61
62// Check if spelling of \p H matches \p DeclName.
63bool nameMatch(llvm::StringRef DeclName, Header H) {
64 switch (H.kind()) {
65 case Header::Physical:
66 return basename(Header: H.physical().getName()).equals_insensitive(RHS: DeclName);
67 case Header::Standard:
68 return basename(Header: H.standard().name()).equals_insensitive(RHS: DeclName);
69 case Header::Verbatim:
70 return basename(Header: H.verbatim()).equals_insensitive(RHS: DeclName);
71 }
72 llvm_unreachable("unhandled Header kind!");
73}
74
75llvm::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>(Val: &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
90Hints isPublicHeader(const FileEntry *FE, const PragmaIncludes &PI) {
91 if (PI.isPrivate(File: FE) || !PI.isSelfContained(File: FE))
92 return Hints::None;
93 return Hints::PublicHeader;
94}
95
96llvm::SmallVector<Hinted<Header>>
97hintedHeadersForStdHeaders(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(Args: H, Args: Hints::PublicHeader | Hints::OriginHeader);
102 if (!PI)
103 continue;
104 for (FileEntryRef Export : PI->getExporters(H, FM&: SM.getFileManager()))
105 Results.emplace_back(Args: Header(Export), Args: isPublicHeader(FE: Export, PI: *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.
116std::optional<tooling::stdlib::Header>
117headerForAmbiguousStdSymbol(const NamedDecl *ND) {
118 if (!ND->isInStdNamespace())
119 return {};
120 if (auto* USD = llvm::dyn_cast<UsingShadowDecl>(Val: 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(Name: "<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(Name: "<algorithm>");
135 } else if (FName == "remove") {
136 if (FD->getNumParams() == 1)
137 // remove(const char*);
138 return tooling::stdlib::Header::named(Name: "<cstdio>");
139 if (FD->getNumParams() == 3)
140 // remove(ForwardIt first, ForwardIt last, const T& value);
141 return tooling::stdlib::Header::named(Name: "<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.
148std::optional<llvm::SmallVector<Hinted<Header>>>
149headersForSpecialSymbol(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>(Val: &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(Headers: hintedHeadersForStdHeaders(Headers: {*Header}, SM, PI),
167 H: 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
184llvm::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(SpellingLoc: SM.getExpansionLoc(Loc: 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(Args&: *FE,
200 Args: isPublicHeader(FE: *FE, PI: *PI) |
201 (IsOrigin ? Hints::OriginHeader : Hints::None));
202 for (FileEntryRef Export : PI->getExporters(File: *FE, FM&: SM.getFileManager()))
203 Exporters.push(x: Export);
204
205 if (auto Verbatim = PI->getPublic(File: *FE); !Verbatim.empty()) {
206 Results.emplace_back(Args&: Verbatim,
207 Args: Hints::PublicHeader | Hints::PreferredHeader);
208 break;
209 }
210 if (PI->isSelfContained(File: *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(x: Export).second) // In case of cyclic exports
227 continue;
228 Results.emplace_back(Args&: Export, Args: isPublicHeader(FE: Export, PI: *PI));
229 for (FileEntryRef Export : PI->getExporters(File: Export, FM&: SM.getFileManager()))
230 Exporters.push(x: Export);
231 }
232 return Results;
233 }
234 case SymbolLocation::Standard: {
235 return hintedHeadersForStdHeaders(Headers: Loc.standard().headers(), SM, PI);
236 }
237 }
238 llvm_unreachable("unhandled SymbolLocation kind!");
239}
240
241llvm::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(RHS: applyHints(Headers: findHeaders(Loc, SM, PI), H: 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 Range&: Headers, C: [](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(CS: Write, CE: 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(DeclName: SymbolName, H))
285 H.Hint |= Hints::PreferredHeader;
286 }
287
288 // FIXME: Introduce a MainFile header kind or signal and boost it.
289 return ranked(Headers: std::move(Headers));
290}
291} // namespace clang::include_cleaner
292

source code of clang-tools-extra/include-cleaner/lib/FindHeaders.cpp