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