Debian Codegraph @

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

raw
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/Decl.h"
14 #include "clang/AST/DeclBase.h"
15 #include "clang/Basic/FileEntry.h"
16 #include "clang/Basic/SourceLocation.h"
17 #include "clang/Basic/SourceManager.h"
18 #include "clang/Tooling/Inclusions/StandardLibrary.h"
19 #include "llvm/ADT/STLExtras.h"
20 #include "llvm/ADT/SmallVector.h"
21 #include "llvm/ADT/StringRef.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/ErrorHandling.h"
24 #include <string>
25 #include <utility>
26
27 namespace clang::include_cleaner {
28 namespace {
29 llvm::SmallVector<Hinted<Header>>
30 applyHints(llvm::SmallVector<Hinted<Header>> Headers, Hints H) {
31 for (auto &Header : Headers)
32 Header.Hint |= H;
33 return Headers;
34 }
35
36 llvm::SmallVector<Header> ranked(llvm::SmallVector<Hinted<Header>> Headers) {
37 llvm::stable_sort(llvm::reverse(Headers),
38 [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
39 return LHS < RHS;
40 });
41 return llvm::SmallVector<Header>(Headers.begin(), Headers.end());
42 }
43
44 // Return the basename from a verbatim header spelling, leaves only the file
45 // name.
46 llvm::StringRef basename(llvm::StringRef Header) {
47 Header = Header.trim("<>\"");
48 if (auto LastSlash = Header.rfind('/'); LastSlash != Header.npos)
49 Header = Header.drop_front(LastSlash + 1);
50 // Drop everything after first `.` (dot).
51 // foo.h -> foo
52 // foo.cu.h -> foo
53 Header = Header.substr(0, Header.find('.'));
54 return Header;
55 }
56
57 // Check if spelling of \p H matches \p DeclName.
58 bool nameMatch(llvm::StringRef DeclName, Header H) {
59 switch (H.kind()) {
60 case Header::Physical:
61 return basename(H.physical()->getName()).equals_insensitive(DeclName);
62 case Header::Standard:
63 return basename(H.standard().name()).equals_insensitive(DeclName);
64 case Header::Verbatim:
65 return basename(H.verbatim()).equals_insensitive(DeclName);
66 }
67 llvm_unreachable("unhandled Header kind!");
68 }
69
70 llvm::StringRef symbolName(const Symbol &S) {
71 switch (S.kind()) {
72 case Symbol::Declaration:
73 // Unnamed decls like operators and anonymous structs won't get any name
74 // match.
75 if (const auto *ND = llvm::dyn_cast<NamedDecl>(&S.declaration()))
76 if (auto *II = ND->getIdentifier())
77 return II->getName();
78 return "";
79 case Symbol::Macro:
80 return S.macro().Name->getName();
81 }
82 llvm_unreachable("unhandled Symbol kind!");
83 }
84
85 } // namespace
86
87 llvm::SmallVector<Hinted<Header>> findHeaders(const SymbolLocation &Loc,
88 const SourceManager &SM,
89 const PragmaIncludes *PI) {
90 auto IsPublicHeader = [&PI](const FileEntry *FE) {
91 return (PI->isPrivate(FE) || !PI->isSelfContained(FE))
92 ? Hints::None
93 : Hints::PublicHeader;
94 };
95 llvm::SmallVector<Hinted<Header>> Results;
96 switch (Loc.kind()) {
97 case SymbolLocation::Physical: {
98 FileID FID = SM.getFileID(SM.getExpansionLoc(Loc.physical()));
99 const FileEntry *FE = SM.getFileEntryForID(FID);
100 if (!FE)
101 return {};
102 if (!PI)
103 return {{FE, Hints::PublicHeader}};
104 while (FE) {
105 Hints CurrentHints = IsPublicHeader(FE);
106 Results.emplace_back(FE, CurrentHints);
107 // FIXME: compute transitive exporter headers.
108 for (const auto *Export : PI->getExporters(FE, SM.getFileManager()))
109 Results.emplace_back(Export, IsPublicHeader(Export));
110
111 if (auto Verbatim = PI->getPublic(FE); !Verbatim.empty()) {
112 Results.emplace_back(Verbatim,
113 Hints::PublicHeader | Hints::PreferredHeader);
114 break;
115 }
116 if (PI->isSelfContained(FE) || FID == SM.getMainFileID())
117 break;
118
119 // Walkup the include stack for non self-contained headers.
120 FID = SM.getDecomposedIncludedLoc(FID).first;
121 FE = SM.getFileEntryForID(FID);
122 }
123 return Results;
124 }
125 case SymbolLocation::Standard: {
126 for (const auto &H : Loc.standard().headers()) {
127 Results.emplace_back(H, Hints::PublicHeader);
128 for (const auto *Export : PI->getExporters(H, SM.getFileManager()))
129 Results.emplace_back(Header(Export), IsPublicHeader(Export));
130 }
131 // StandardLibrary returns headers in preference order, so only mark the
132 // first.
133 if (!Results.empty())
134 Results.front().Hint |= Hints::PreferredHeader;
135 return Results;
136 }
137 }
138 llvm_unreachable("unhandled SymbolLocation kind!");
139 }
140
141 llvm::SmallVector<Header> headersForSymbol(const Symbol &S,
142 const SourceManager &SM,
143 const PragmaIncludes *PI) {
144 // Get headers for all the locations providing Symbol. Same header can be
145 // reached through different traversals, deduplicate those into a single
146 // Header by merging their hints.
147 llvm::SmallVector<Hinted<Header>> Headers;
148 for (auto &Loc : locateSymbol(S))
149 Headers.append(applyHints(findHeaders(Loc, SM, PI), Loc.Hint));
150 // If two Headers probably refer to the same file (e.g. Verbatim(foo.h) and
151 // Physical(/path/to/foo.h), we won't deduplicate them or merge their hints
152 llvm::stable_sort(
153 Headers, [](const Hinted<Header> &LHS, const Hinted<Header> &RHS) {
154 return static_cast<Header>(LHS) < static_cast<Header>(RHS);
155 });
156 auto *Write = Headers.begin();
157 for (auto *Read = Headers.begin(); Read != Headers.end(); ++Write) {
158 *Write = *Read++;
159 while (Read != Headers.end() &&
160 static_cast<Header>(*Write) == static_cast<Header>(*Read)) {
161 Write->Hint |= Read->Hint;
162 ++Read;
163 }
164 }
165 Headers.erase(Write, Headers.end());
166
167 // Add name match hints to deduplicated providers.
168 llvm::StringRef SymbolName = symbolName(S);
169 for (auto &H : Headers) {
170 if (nameMatch(SymbolName, H))
171 H.Hint |= Hints::PreferredHeader;
172 }
173
174 // FIXME: Introduce a MainFile header kind or signal and boost it.
175 return ranked(std::move(Headers));
176 }
177 } // namespace clang::include_cleaner