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
19namespace clang {
20namespace tooling {
21namespace stdlib {
22
23namespace {
24// Symbol name -> Symbol::ID, within a namespace.
25using NSSymbolMap = llvm::DenseMap<llvm::StringRef, unsigned>;
26
27// A Mapping per language.
28struct 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; // ~~~~~~
39 StringRef scope() const { return StringRef(Data, ScopeLen); }
40 StringRef name() const { return StringRef(Data + ScopeLen, NameLen); }
41 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
51static SymbolHeaderMapping
52 *LanguageMappings[static_cast<unsigned>(Lang::LastValue) + 1];
53static const SymbolHeaderMapping *getMappingPerLang(Lang L) {
54 return LanguageMappings[static_cast<unsigned>(L)];
55}
56
57static 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>(llvm::from_range, Symbols).size();
81}
82
83static 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(Key: NS, Args: 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(Key: Header, Args: 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(N: NSLen) == "None") {
114 QName = QName.drop_front(N: NSLen);
115 NSLen = 0;
116 }
117
118 if (SymIndex > 0) {
119 assert(llvm::none_of(llvm::ArrayRef(Mapping->SymbolNames, SymIndex),
120 [&QName](const SymbolHeaderMapping::SymbolName &S) {
121 return S.qualifiedName() == QName;
122 }) &&
123 "The symbol has been added before, make sure entries in the .inc "
124 "file are grouped by symbol name!");
125 }
126 if (SymIndex < 0 ||
127 Mapping->SymbolNames[SymIndex].qualifiedName() != QName) {
128 // First symbol or new symbol, increment next available index.
129 ++SymIndex;
130 } // Else use the same index.
131 Mapping->SymbolNames[SymIndex] = {
132 .Data: QName.data(), .ScopeLen: NSLen, .NameLen: static_cast<unsigned int>(QName.size() - NSLen)};
133 if (!HeaderName.empty())
134 Mapping->SymbolHeaderIDs[SymIndex].push_back(Elt: AddHeader(HeaderName));
135
136 NSSymbolMap &NSSymbols = AddNS(QName.take_front(N: NSLen));
137 NSSymbols.try_emplace(Key: QName.drop_front(N: NSLen), Args&: 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
178static void ensureInitialized() {
179 static int Dummy = []() {
180 for (unsigned L = 0; L <= static_cast<unsigned>(Lang::LastValue); ++L)
181 initialize(Language: static_cast<Lang>(L));
182 return 0;
183 }();
184 (void)Dummy;
185}
186
187std::vector<Header> Header::all(Lang L) {
188 ensureInitialized();
189 std::vector<Header> Result;
190 const auto *Mapping = getMappingPerLang(L);
191 Result.reserve(n: Mapping->HeaderIDs->size());
192 for (unsigned I = 0, E = Mapping->HeaderIDs->size(); I < E; ++I)
193 Result.push_back(x: Header(I, L));
194 return Result;
195}
196std::optional<Header> Header::named(llvm::StringRef Name, Lang L) {
197 ensureInitialized();
198 const auto *Mapping = getMappingPerLang(L);
199 auto It = Mapping->HeaderIDs->find(Val: Name);
200 if (It == Mapping->HeaderIDs->end())
201 return std::nullopt;
202 return Header(It->second, L);
203}
204llvm::StringRef Header::name() const {
205 return getMappingPerLang(L: Language)->HeaderNames[ID];
206}
207
208std::vector<Symbol> Symbol::all(Lang L) {
209 ensureInitialized();
210 std::vector<Symbol> Result;
211 const auto *Mapping = getMappingPerLang(L);
212 Result.reserve(n: Mapping->SymbolCount);
213 for (unsigned I = 0, E = Mapping->SymbolCount; I < E; ++I)
214 Result.push_back(x: Symbol(I, L));
215 return Result;
216}
217llvm::StringRef Symbol::scope() const {
218 return getMappingPerLang(L: Language)->SymbolNames[ID].scope();
219}
220llvm::StringRef Symbol::name() const {
221 return getMappingPerLang(L: Language)->SymbolNames[ID].name();
222}
223llvm::StringRef Symbol::qualifiedName() const {
224 return getMappingPerLang(L: Language)->SymbolNames[ID].qualifiedName();
225}
226std::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(Val: Scope)) {
232 auto It = NSSymbols->find(Val: Name);
233 if (It != NSSymbols->end())
234 return Symbol(It->second, L);
235 }
236 return std::nullopt;
237}
238std::optional<Header> Symbol::header() const {
239 const auto& Headers = getMappingPerLang(L: Language)->SymbolHeaderIDs[ID];
240 if (Headers.empty())
241 return std::nullopt;
242 return Header(Headers.front(), Language);
243}
244llvm::SmallVector<Header> Symbol::headers() const {
245 llvm::SmallVector<Header> Results;
246 for (auto HeaderID : getMappingPerLang(L: Language)->SymbolHeaderIDs[ID])
247 Results.emplace_back(Args: Header(HeaderID, Language));
248 return Results;
249}
250
251Recognizer::Recognizer() { ensureInitialized(); }
252
253NSSymbolMap *Recognizer::namespaceSymbols(const DeclContext *DC, Lang L) {
254 if (DC->isTranslationUnit()) // global scope.
255 return getMappingPerLang(L)->NamespaceSymbols->lookup(Val: "");
256
257 auto It = NamespaceCache.find(Val: DC);
258 if (It != NamespaceCache.end())
259 return It->second;
260 const NamespaceDecl *D = llvm::cast<NamespaceDecl>(Val: 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>(Val: ND->getParent()))
268 if (!ND->isInlineNamespace() && !ND->isAnonymousNamespace())
269 Scope = ND->getName().str() + "::" + Scope;
270 return getMappingPerLang(L)->NamespaceSymbols->lookup(Val: Scope);
271 }();
272 NamespaceCache.try_emplace(Key: D, Args&: Result);
273 return Result;
274}
275
276std::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(K: DC->getDeclKind()))
294 IntermediateDecl.push_back(Elt: 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(C&: IntermediateDecl)) {
303 DeclarationName N = cast<NamedDecl>(Val: 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>(Val: 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(Val: 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