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 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 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 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 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 } 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 } 202 llvm::StringRef Header::name() const { 203 return getMappingPerLang(Language)->HeaderNames[ID]; 204 } 205 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 } 215 llvm::StringRef Symbol::scope() const { 216 return getMappingPerLang(Language)->SymbolNames[ID].scope(); 217 } 218 llvm::StringRef Symbol::name() const { 219 return getMappingPerLang(Language)->SymbolNames[ID].name(); 220 } 221 llvm::StringRef Symbol::qualifiedName() const { 222 return getMappingPerLang(Language)->SymbolNames[ID].qualifiedName(); 223 } 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 } 236 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 } 242 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 249 Recognizer::Recognizer() { ensureInitialized(); } 250 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 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