326 lines · cpp
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-exception6//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::ID31 llvm::DenseMap<llvm::StringRef, unsigned> *HeaderIDs;32 33 unsigned SymbolCount = 0;34 // Symbol::ID => symbol qualified_name/name/scope35 struct SymbolName {36 const char *Data; // std::vector37 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::ID48 llvm::SmallVector<unsigned> *SymbolHeaderIDs = nullptr;49};50} // namespace51static SymbolHeaderMapping52 *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 SYMBOL80 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(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 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 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 SYMBOL170 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(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(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}196std::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}204llvm::StringRef Header::name() const {205 return getMappingPerLang(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(Mapping->SymbolCount);213 for (unsigned I = 0, E = Mapping->SymbolCount; I < E; ++I)214 Result.push_back(Symbol(I, L));215 return Result;216}217llvm::StringRef Symbol::scope() const {218 return getMappingPerLang(Language)->SymbolNames[ID].scope();219}220llvm::StringRef Symbol::name() const {221 return getMappingPerLang(Language)->SymbolNames[ID].name();222}223llvm::StringRef Symbol::qualifiedName() const {224 return getMappingPerLang(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(Scope)) {232 auto It = NSSymbols->find(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(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(Language)->SymbolHeaderIDs[ID])247 Results.emplace_back(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("");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 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 else283 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 up308 }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 stdlib324} // namespace tooling325} // namespace clang326