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