clang/lib/Tooling/Inclusions/Stdlib/StandardLibrary.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-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) {#NS #Name, StringRef(#NS).size(), #Header},
 145   switch (Language) {
 146   case Lang::C: {
 147     static constexpr Symbol CSymbols[] = {
 148 #include "CSymbolMap.inc"
 149     };
 150     for (const Symbol &S : CSymbols)
 151       Add(S.QName, S.NSLen, S.HeaderName);
 152     break;
 153   }
 154   case Lang::CXX: {
 155     static constexpr Symbol CXXSymbols[] = {
 156 #include "StdSpecialSymbolMap.inc"
 157 #include "StdSymbolMap.inc"
 158 #include "StdTsSymbolMap.inc"
 159     };
 160     for (const Symbol &S : CXXSymbols)
 161       Add(S.QName, S.NSLen, S.HeaderName);
 162     break;
 163   }
 164   }
 165 #undef SYMBOL
 166
 167   Mapping->HeaderNames = new llvm::StringRef[Mapping->HeaderIDs->size()];
 168   for (const auto &E : *Mapping->HeaderIDs)
 169     Mapping->HeaderNames[E.second] = E.first;
 170
 171   return 0;
 172 }
 173
 174 static void ensureInitialized() {
 175   static int Dummy = []() {
 176     for (unsigned L = 0; L <= static_cast<unsigned>(Lang::LastValue); ++L)
 177       initialize(static_cast<Lang>(L));
 178     return 0;
 179   }();
 180   (void)Dummy;
 181 }
 182
 183 std::vector<Header> Header::all(Lang L) {
 184   ensureInitialized();
 185   std::vector<Header> Result;
 186   const auto *Mapping = getMappingPerLang(L);
 187   Result.reserve(Mapping->HeaderIDs->size());
 188   for (unsigned I = 0, E = Mapping->HeaderIDs->size(); I < E; ++I)
 189     Result.push_back(Header(I, L));
 190   return Result;
 191 }
 192 std::optional<Header> Header::named(llvm::StringRef Name, Lang L) {
 193   ensureInitialized();
 194   const auto *Mapping = getMappingPerLang(L);
 195   auto It = Mapping->HeaderIDs->find(Name);
 196   if (It == Mapping->HeaderIDs->end())
 197     return std::nullopt;
 198   return Header(It->second, L);
 199 }
 200 llvm::StringRef Header::name() const {
 201   return getMappingPerLang(Language)->HeaderNames[ID];
 202 }
 203
 204 std::vector<Symbol> Symbol::all(Lang L) {
 205   ensureInitialized();
 206   std::vector<Symbol> Result;
 207   const auto *Mapping = getMappingPerLang(L);
 208   Result.reserve(Mapping->SymbolCount);
 209   for (unsigned I = 0, E = Mapping->SymbolCount; I < E; ++I)
 210     Result.push_back(Symbol(I, L));
 211   return Result;
 212 }
 213 llvm::StringRef Symbol::scope() const {
 214   return getMappingPerLang(Language)->SymbolNames[ID].scope();
 215 }
 216 llvm::StringRef Symbol::name() const {
 217   return getMappingPerLang(Language)->SymbolNames[ID].name();
 218 }
 219 llvm::StringRef Symbol::qualifiedName() const {
 220   return getMappingPerLang(Language)->SymbolNames[ID].qualifiedName();
 221 }
 222 std::optional<Symbol> Symbol::named(llvm::StringRef Scope, llvm::StringRef Name,
 223                                     Lang L) {
 224   ensureInitialized();
 225
 226   if (NSSymbolMap *NSSymbols =
 227           getMappingPerLang(L)->NamespaceSymbols->lookup(Scope)) {
 228     auto It = NSSymbols->find(Name);
 229     if (It != NSSymbols->end())
 230       return Symbol(It->second, L);
 231   }
 232   return std::nullopt;
 233 }
 234 std::optional<Header> Symbol::header() const {
 235   const auto& Headers = getMappingPerLang(Language)->SymbolHeaderIDs[ID];
 236   if (Headers.empty())
 237     return std::nullopt;
 238   return Header(Headers.front(), Language);
 239 }
 240 llvm::SmallVector<Header> Symbol::headers() const {
 241   llvm::SmallVector<Header> Results;
 242   for (auto HeaderID : getMappingPerLang(Language)->SymbolHeaderIDs[ID])
 243     Results.emplace_back(Header(HeaderID, Language));
 244   return Results;
 245 }
 246
 247 Recognizer::Recognizer() { ensureInitialized(); }
 248
 249 NSSymbolMap *Recognizer::namespaceSymbols(const DeclContext *DC, Lang L) {
 250   if (DC->isTranslationUnit()) // global scope.
 251     return getMappingPerLang(L)->NamespaceSymbols->lookup("");
 252
 253   auto It = NamespaceCache.find(DC);
 254   if (It != NamespaceCache.end())
 255     return It->second;
 256   const NamespaceDecl *D = llvm::cast<NamespaceDecl>(DC);
 257   NSSymbolMap *Result = [&]() -> NSSymbolMap * {
 258     if (D->isAnonymousNamespace())
 259       return nullptr;
 260     // Print the namespace and its parents ommitting inline scopes.
 261     std::string Scope;
 262     for (const auto *ND = D; ND;
 263          ND = llvm::dyn_cast_or_null<NamespaceDecl>(ND->getParent()))
 264       if (!ND->isInlineNamespace() && !ND->isAnonymousNamespace())
 265         Scope = ND->getName().str() + "::" + Scope;
 266     return getMappingPerLang(L)->NamespaceSymbols->lookup(Scope);
 267   }();
 268   NamespaceCache.try_emplace(D, Result);
 269   return Result;
 270 }
 271
 272 std::optional<Symbol> Recognizer::operator()(const Decl *D) {
 273   Lang L;
 274   if (D->getLangOpts().CPlusPlus)
 275     L = Lang::CXX;
 276   else if (D->getLangOpts().C99)
 277     L = Lang::C;
 278   else
 279     return std::nullopt; // not a supported language.
 280
 281   // If D is std::vector::iterator, `vector` is the outer symbol to look up.
 282   // We keep all the candidate DCs as some may turn out to be anon enums.
 283   // Do this resolution lazily as we may turn out not to have a std namespace.
 284   llvm::SmallVector<const DeclContext *> IntermediateDecl;
 285   const DeclContext *DC = D->getDeclContext();
 286   if (!DC) // The passed D is a TranslationUnitDecl!
 287     return std::nullopt;
 288   while (!DC->isNamespace() && !DC->isTranslationUnit()) {
 289     if (NamedDecl::classofKind(DC->getDeclKind()))
 290       IntermediateDecl.push_back(DC);
 291     DC = DC->getParent();
 292   }
 293   NSSymbolMap *Symbols = namespaceSymbols(DC, L);
 294   if (!Symbols)
 295     return std::nullopt;
 296
 297   llvm::StringRef Name = [&]() -> llvm::StringRef {
 298     for (const auto *SymDC : llvm::reverse(IntermediateDecl)) {
 299       DeclarationName N = cast<NamedDecl>(SymDC)->getDeclName();
 300       if (const auto *II = N.getAsIdentifierInfo())
 301         return II->getName();
 302       if (!N.isEmpty())
 303         return ""; // e.g. operator<: give up
 304     }
 305     if (const auto *ND = llvm::dyn_cast<NamedDecl>(D))
 306       if (const auto *II = ND->getIdentifier())
 307         return II->getName();
 308     return "";
 309   }();
 310   if (Name.empty())
 311     return std::nullopt;
 312
 313   auto It = Symbols->find(Name);
 314   if (It == Symbols->end())
 315     return std::nullopt;
 316   return Symbol(It->second, L);
 317 }
 318
 319 } // namespace stdlib
 320 } // namespace tooling
 321 } // namespace clang