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 "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 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 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 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 } 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 } 204 llvm::StringRef Header::name() const { 205 return getMappingPerLang(Language)->HeaderNames[ID]; 206 } 207 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 } 217 llvm::StringRef Symbol::scope() const { 218 return getMappingPerLang(Language)->SymbolNames[ID].scope(); 219 } 220 llvm::StringRef Symbol::name() const { 221 return getMappingPerLang(Language)->SymbolNames[ID].name(); 222 } 223 llvm::StringRef Symbol::qualifiedName() const { 224 return getMappingPerLang(Language)->SymbolNames[ID].qualifiedName(); 225 } 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 } 238 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 } 244 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 251 Recognizer::Recognizer() { ensureInitialized(); } 252 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 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