1 //===--- StandardLibrary.cpp ------------------------------------*- C++ -*-===//
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 "clang/Tooling/Inclusions/StandardLibrary.h"
10 #include "clang/AST/Decl.h"
11 #include "clang/Basic/LangOptions.h"
12 #include "llvm/ADT/ArrayRef.h"
13 #include "llvm/ADT/DenseSet.h"
14 #include "llvm/ADT/STLExtras.h"
15 #include "llvm/ADT/StringRef.h"
16 #include "llvm/Support/Casting.h"
17 #include <optional>
18
19 namespace clang {
20 namespace tooling {
21 namespace stdlib {
22
23 namespace {
24 // Symbol name -> Symbol::ID, within a namespace.
25 using NSSymbolMap = llvm::DenseMap<llvm::StringRef, unsigned>;
26
27 // A Mapping per language.
28 struct SymbolHeaderMapping {
29 llvm::StringRef *HeaderNames = nullptr;
30 // Header name => Header::ID
31 llvm::DenseMap<llvm::StringRef, unsigned> *HeaderIDs;
32
33 unsigned SymbolCount = 0;
34 // Symbol::ID => symbol qualified_name/name/scope
35 struct SymbolName {
36 const char *Data; // std::vector
37 unsigned ScopeLen; // ~~~~~
38 unsigned NameLen; // ~~~~~~
scopeclang::tooling::stdlib::__anon324b17e80111::SymbolHeaderMapping::SymbolName39 StringRef scope() const { return StringRef(Data, ScopeLen); }
nameclang::tooling::stdlib::__anon324b17e80111::SymbolHeaderMapping::SymbolName40 StringRef name() const { return StringRef(Data + ScopeLen, NameLen); }
qualifiedNameclang::tooling::stdlib::__anon324b17e80111::SymbolHeaderMapping::SymbolName41 StringRef qualifiedName() const {
42 return StringRef(Data, ScopeLen + NameLen);
43 }
44 } *SymbolNames = nullptr;
45 // Symbol name -> Symbol::ID, within a namespace.
46 llvm::DenseMap<llvm::StringRef, NSSymbolMap *> *NamespaceSymbols = nullptr;
47 // Symbol::ID => Header::ID
48 llvm::SmallVector<unsigned> *SymbolHeaderIDs = nullptr;
49 };
50 } // namespace
51 static SymbolHeaderMapping
52 *LanguageMappings[static_cast<unsigned>(Lang::LastValue) + 1];
getMappingPerLang(Lang L)53 static const SymbolHeaderMapping *getMappingPerLang(Lang L) {
54 return LanguageMappings[static_cast<unsigned>(L)];
55 }
56
countSymbols(Lang Language)57 static int countSymbols(Lang Language) {
58 ArrayRef<const char*> Symbols;
59 #define SYMBOL(Name, NS, Header) #NS #Name,
60 switch (Language) {
61 case Lang::C: {
62 static constexpr const char *CSymbols[] = {
63 #include "CSymbolMap.inc"
64 };
65 Symbols = CSymbols;
66 break;
67 }
68 case Lang::CXX: {
69 static constexpr const char *CXXSymbols[] = {
70 #include "StdSpecialSymbolMap.inc"
71 #include "StdSymbolMap.inc"
72 #include "StdTsSymbolMap.inc"
73 };
74 Symbols = CXXSymbols;
75 break;
76 }
77 }
78 #undef SYMBOL
79 return llvm::DenseSet<StringRef>(Symbols.begin(), Symbols.end()).size();
80 }
81
initialize(Lang Language)82 static int initialize(Lang Language) {
83 SymbolHeaderMapping *Mapping = new SymbolHeaderMapping();
84 LanguageMappings[static_cast<unsigned>(Language)] = Mapping;
85
86 unsigned SymCount = countSymbols(Language);
87 Mapping->SymbolCount = SymCount;
88 Mapping->SymbolNames =
89 new std::remove_reference_t<decltype(*Mapping->SymbolNames)>[SymCount];
90 Mapping->SymbolHeaderIDs = new std::remove_reference_t<
91 decltype(*Mapping->SymbolHeaderIDs)>[SymCount];
92 Mapping->NamespaceSymbols =
93 new std::remove_reference_t<decltype(*Mapping->NamespaceSymbols)>;
94 Mapping->HeaderIDs =
95 new std::remove_reference_t<decltype(*Mapping->HeaderIDs)>;
96 auto AddNS = [&](llvm::StringRef NS) -> NSSymbolMap & {
97 auto R = Mapping->NamespaceSymbols->try_emplace(NS, nullptr);
98 if (R.second)
99 R.first->second = new NSSymbolMap();
100 return *R.first->second;
101 };
102
103 auto AddHeader = [&](llvm::StringRef Header) -> unsigned {
104 return Mapping->HeaderIDs->try_emplace(Header, Mapping->HeaderIDs->size())
105 .first->second;
106 };
107
108 auto Add = [&, SymIndex(-1)](llvm::StringRef QName, unsigned NSLen,
109 llvm::StringRef HeaderName) mutable {
110 // Correct "Nonefoo" => foo.
111 // FIXME: get rid of "None" from the generated mapping files.
112 if (QName.take_front(NSLen) == "None") {
113 QName = QName.drop_front(NSLen);
114 NSLen = 0;
115 }
116
117 if (SymIndex >= 0 &&
118 Mapping->SymbolNames[SymIndex].qualifiedName() == QName) {
119 // Not a new symbol, use the same index.
120 assert(llvm::none_of(llvm::ArrayRef(Mapping->SymbolNames, SymIndex),
121 [&QName](const SymbolHeaderMapping::SymbolName &S) {
122 return S.qualifiedName() == QName;
123 }) &&
124 "The symbol has been added before, make sure entries in the .inc "
125 "file are grouped by symbol name!");
126 } else {
127 // First symbol or new symbol, increment next available index.
128 ++SymIndex;
129 }
130 Mapping->SymbolNames[SymIndex] = {
131 QName.data(), NSLen, static_cast<unsigned int>(QName.size() - NSLen)};
132 if (!HeaderName.empty())
133 Mapping->SymbolHeaderIDs[SymIndex].push_back(AddHeader(HeaderName));
134
135 NSSymbolMap &NSSymbols = AddNS(QName.take_front(NSLen));
136 NSSymbols.try_emplace(QName.drop_front(NSLen), SymIndex);
137 };
138
139 struct Symbol {
140 const char *QName;
141 unsigned NSLen;
142 const char *HeaderName;
143 };
144 #define SYMBOL(Name, NS, Header) \
145 {#NS #Name, static_cast<decltype(Symbol::NSLen)>(StringRef(#NS).size()), \
146 #Header},
147 switch (Language) {
148 case Lang::C: {
149 static constexpr Symbol CSymbols[] = {
150 #include "CSymbolMap.inc"
151 };
152 for (const Symbol &S : CSymbols)
153 Add(S.QName, S.NSLen, S.HeaderName);
154 break;
155 }
156 case Lang::CXX: {
157 static constexpr Symbol CXXSymbols[] = {
158 #include "StdSpecialSymbolMap.inc"
159 #include "StdSymbolMap.inc"
160 #include "StdTsSymbolMap.inc"
161 };
162 for (const Symbol &S : CXXSymbols)
163 Add(S.QName, S.NSLen, S.HeaderName);
164 break;
165 }
166 }
167 #undef SYMBOL
168
169 Mapping->HeaderNames = new llvm::StringRef[Mapping->HeaderIDs->size()];
170 for (const auto &E : *Mapping->HeaderIDs)
171 Mapping->HeaderNames[E.second] = E.first;
172
173 return 0;
174 }
175
ensureInitialized()176 static void ensureInitialized() {
177 static int Dummy = []() {
178 for (unsigned L = 0; L <= static_cast<unsigned>(Lang::LastValue); ++L)
179 initialize(static_cast<Lang>(L));
180 return 0;
181 }();
182 (void)Dummy;
183 }
184
all(Lang L)185 std::vector<Header> Header::all(Lang L) {
186 ensureInitialized();
187 std::vector<Header> Result;
188 const auto *Mapping = getMappingPerLang(L);
189 Result.reserve(Mapping->HeaderIDs->size());
190 for (unsigned I = 0, E = Mapping->HeaderIDs->size(); I < E; ++I)
191 Result.push_back(Header(I, L));
192 return Result;
193 }
named(llvm::StringRef Name,Lang L)194 std::optional<Header> Header::named(llvm::StringRef Name, Lang L) {
195 ensureInitialized();
196 const auto *Mapping = getMappingPerLang(L);
197 auto It = Mapping->HeaderIDs->find(Name);
198 if (It == Mapping->HeaderIDs->end())
199 return std::nullopt;
200 return Header(It->second, L);
201 }
name() const202 llvm::StringRef Header::name() const {
203 return getMappingPerLang(Language)->HeaderNames[ID];
204 }
205
all(Lang L)206 std::vector<Symbol> Symbol::all(Lang L) {
207 ensureInitialized();
208 std::vector<Symbol> Result;
209 const auto *Mapping = getMappingPerLang(L);
210 Result.reserve(Mapping->SymbolCount);
211 for (unsigned I = 0, E = Mapping->SymbolCount; I < E; ++I)
212 Result.push_back(Symbol(I, L));
213 return Result;
214 }
scope() const215 llvm::StringRef Symbol::scope() const {
216 return getMappingPerLang(Language)->SymbolNames[ID].scope();
217 }
name() const218 llvm::StringRef Symbol::name() const {
219 return getMappingPerLang(Language)->SymbolNames[ID].name();
220 }
qualifiedName() const221 llvm::StringRef Symbol::qualifiedName() const {
222 return getMappingPerLang(Language)->SymbolNames[ID].qualifiedName();
223 }
named(llvm::StringRef Scope,llvm::StringRef Name,Lang L)224 std::optional<Symbol> Symbol::named(llvm::StringRef Scope, llvm::StringRef Name,
225 Lang L) {
226 ensureInitialized();
227
228 if (NSSymbolMap *NSSymbols =
229 getMappingPerLang(L)->NamespaceSymbols->lookup(Scope)) {
230 auto It = NSSymbols->find(Name);
231 if (It != NSSymbols->end())
232 return Symbol(It->second, L);
233 }
234 return std::nullopt;
235 }
header() const236 std::optional<Header> Symbol::header() const {
237 const auto& Headers = getMappingPerLang(Language)->SymbolHeaderIDs[ID];
238 if (Headers.empty())
239 return std::nullopt;
240 return Header(Headers.front(), Language);
241 }
headers() const242 llvm::SmallVector<Header> Symbol::headers() const {
243 llvm::SmallVector<Header> Results;
244 for (auto HeaderID : getMappingPerLang(Language)->SymbolHeaderIDs[ID])
245 Results.emplace_back(Header(HeaderID, Language));
246 return Results;
247 }
248
Recognizer()249 Recognizer::Recognizer() { ensureInitialized(); }
250
namespaceSymbols(const DeclContext * DC,Lang L)251 NSSymbolMap *Recognizer::namespaceSymbols(const DeclContext *DC, Lang L) {
252 if (DC->isTranslationUnit()) // global scope.
253 return getMappingPerLang(L)->NamespaceSymbols->lookup("");
254
255 auto It = NamespaceCache.find(DC);
256 if (It != NamespaceCache.end())
257 return It->second;
258 const NamespaceDecl *D = llvm::cast<NamespaceDecl>(DC);
259 NSSymbolMap *Result = [&]() -> NSSymbolMap * {
260 if (D->isAnonymousNamespace())
261 return nullptr;
262 // Print the namespace and its parents ommitting inline scopes.
263 std::string Scope;
264 for (const auto *ND = D; ND;
265 ND = llvm::dyn_cast_or_null<NamespaceDecl>(ND->getParent()))
266 if (!ND->isInlineNamespace() && !ND->isAnonymousNamespace())
267 Scope = ND->getName().str() + "::" + Scope;
268 return getMappingPerLang(L)->NamespaceSymbols->lookup(Scope);
269 }();
270 NamespaceCache.try_emplace(D, Result);
271 return Result;
272 }
273
operator ()(const Decl * D)274 std::optional<Symbol> Recognizer::operator()(const Decl *D) {
275 Lang L;
276 if (D->getLangOpts().CPlusPlus)
277 L = Lang::CXX;
278 else if (D->getLangOpts().C99)
279 L = Lang::C;
280 else
281 return std::nullopt; // not a supported language.
282
283 // If D is std::vector::iterator, `vector` is the outer symbol to look up.
284 // We keep all the candidate DCs as some may turn out to be anon enums.
285 // Do this resolution lazily as we may turn out not to have a std namespace.
286 llvm::SmallVector<const DeclContext *> IntermediateDecl;
287 const DeclContext *DC = D->getDeclContext();
288 if (!DC) // The passed D is a TranslationUnitDecl!
289 return std::nullopt;
290 while (!DC->isNamespace() && !DC->isTranslationUnit()) {
291 if (NamedDecl::classofKind(DC->getDeclKind()))
292 IntermediateDecl.push_back(DC);
293 DC = DC->getParent();
294 }
295 NSSymbolMap *Symbols = namespaceSymbols(DC, L);
296 if (!Symbols)
297 return std::nullopt;
298
299 llvm::StringRef Name = [&]() -> llvm::StringRef {
300 for (const auto *SymDC : llvm::reverse(IntermediateDecl)) {
301 DeclarationName N = cast<NamedDecl>(SymDC)->getDeclName();
302 if (const auto *II = N.getAsIdentifierInfo())
303 return II->getName();
304 if (!N.isEmpty())
305 return ""; // e.g. operator<: give up
306 }
307 if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
308 if (const auto *II = ND->getIdentifier())
309 return II->getName();
310 return "";
311 }();
312 if (Name.empty())
313 return std::nullopt;
314
315 auto It = Symbols->find(Name);
316 if (It == Symbols->end())
317 return std::nullopt;
318 return Symbol(It->second, L);
319 }
320
321 } // namespace stdlib
322 } // namespace tooling
323 } // namespace clang
324