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