libcxxabi/src/cxa_demangle.cpp

   1 //===----------------------------------------------------------------------===//
   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 // FIXME: (possibly) incomplete list of features that clang mangles that this
  10 // file does not yet support:
  11 //   - C++ modules TS
  12
  13 #include "demangle/DemangleConfig.h"
  14 #include "demangle/ItaniumDemangle.h"
  15 #include "__cxxabi_config.h"
  16 #include <cassert>
  17 #include <cctype>
  18 #include <cstdio>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <functional>
  22 #include <numeric>
  23 #include <string_view>
  24 #include <utility>
  25
  26 using namespace itanium_demangle;
  27
  28 constexpr const char *itanium_demangle::FloatData<float>::spec;
  29 constexpr const char *itanium_demangle::FloatData<double>::spec;
  30 constexpr const char *itanium_demangle::FloatData<long double>::spec;
  31
  32 // <discriminator> := _ <non-negative number>      # when number < 10
  33 //                 := __ <non-negative number> _   # when number >= 10
  34 //  extension      := decimal-digit+               # at the end of string
  35 const char *itanium_demangle::parse_discriminator(const char *first,
  36                                                   const char *last) {
  37   // parse but ignore discriminator
  38   if (first != last) {
  39     if (*first == '_') {
  40       const char *t1 = first + 1;
  41       if (t1 != last) {
  42         if (std::isdigit(*t1))
  43           first = t1 + 1;
  44         else if (*t1 == '_') {
  45           for (++t1; t1 != last && std::isdigit(*t1); ++t1)
  46             ;
  47           if (t1 != last && *t1 == '_')
  48             first = t1 + 1;
  49         }
  50       }
  51     } else if (std::isdigit(*first)) {
  52       const char *t1 = first + 1;
  53       for (; t1 != last && std::isdigit(*t1); ++t1)
  54         ;
  55       if (t1 == last)
  56         first = last;
  57     }
  58   }
  59   return first;
  60 }
  61
  62 #ifndef NDEBUG
  63 namespace {
  64 struct DumpVisitor {
  65   unsigned Depth = 0;
  66   bool PendingNewline = false;
  67
  68   template<typename NodeT> static constexpr bool wantsNewline(const NodeT *) {
  69     return true;
  70   }
  71   static bool wantsNewline(NodeArray A) { return !A.empty(); }
  72   static constexpr bool wantsNewline(...) { return false; }
  73
  74   template<typename ...Ts> static bool anyWantNewline(Ts ...Vs) {
  75     for (bool B : {wantsNewline(Vs)...})
  76       if (B)
  77         return true;
  78     return false;
  79   }
  80
  81   void printStr(const char *S) { fprintf(stderr, "%s", S); }
  82   void print(std::string_view SV) {
  83     fprintf(stderr, "\"%.*s\"", (int)SV.size(), &*SV.begin());
  84   }
  85   void print(const Node *N) {
  86     if (N)
  87       N->visit(std::ref(*this));
  88     else
  89       printStr("<null>");
  90   }
  91   void print(NodeArray A) {
  92     ++Depth;
  93     printStr("{");
  94     bool First = true;
  95     for (const Node *N : A) {
  96       if (First)
  97         print(N);
  98       else
  99         printWithComma(N);
 100       First = false;
 101     }
 102     printStr("}");
 103     --Depth;
 104   }
 105
 106   // Overload used when T is exactly 'bool', not merely convertible to 'bool'.
 107   void print(bool B) { printStr(B ? "true" : "false"); }
 108
 109   template <class T>
 110   typename std::enable_if<std::is_unsigned<T>::value>::type print(T N) {
 111     fprintf(stderr, "%llu", (unsigned long long)N);
 112   }
 113
 114   template <class T>
 115   typename std::enable_if<std::is_signed<T>::value>::type print(T N) {
 116     fprintf(stderr, "%lld", (long long)N);
 117   }
 118
 119   void print(ReferenceKind RK) {
 120     switch (RK) {
 121     case ReferenceKind::LValue:
 122       return printStr("ReferenceKind::LValue");
 123     case ReferenceKind::RValue:
 124       return printStr("ReferenceKind::RValue");
 125     }
 126   }
 127   void print(FunctionRefQual RQ) {
 128     switch (RQ) {
 129     case FunctionRefQual::FrefQualNone:
 130       return printStr("FunctionRefQual::FrefQualNone");
 131     case FunctionRefQual::FrefQualLValue:
 132       return printStr("FunctionRefQual::FrefQualLValue");
 133     case FunctionRefQual::FrefQualRValue:
 134       return printStr("FunctionRefQual::FrefQualRValue");
 135     }
 136   }
 137   void print(Qualifiers Qs) {
 138     if (!Qs) return printStr("QualNone");
 139     struct QualName { Qualifiers Q; const char *Name; } Names[] = {
 140       {QualConst, "QualConst"},
 141       {QualVolatile, "QualVolatile"},
 142       {QualRestrict, "QualRestrict"},
 143     };
 144     for (QualName Name : Names) {
 145       if (Qs & Name.Q) {
 146         printStr(Name.Name);
 147         Qs = Qualifiers(Qs & ~Name.Q);
 148         if (Qs) printStr(" | ");
 149       }
 150     }
 151   }
 152   void print(SpecialSubKind SSK) {
 153     switch (SSK) {
 154     case SpecialSubKind::allocator:
 155       return printStr("SpecialSubKind::allocator");
 156     case SpecialSubKind::basic_string:
 157       return printStr("SpecialSubKind::basic_string");
 158     case SpecialSubKind::string:
 159       return printStr("SpecialSubKind::string");
 160     case SpecialSubKind::istream:
 161       return printStr("SpecialSubKind::istream");
 162     case SpecialSubKind::ostream:
 163       return printStr("SpecialSubKind::ostream");
 164     case SpecialSubKind::iostream:
 165       return printStr("SpecialSubKind::iostream");
 166     }
 167   }
 168   void print(TemplateParamKind TPK) {
 169     switch (TPK) {
 170     case TemplateParamKind::Type:
 171       return printStr("TemplateParamKind::Type");
 172     case TemplateParamKind::NonType:
 173       return printStr("TemplateParamKind::NonType");
 174     case TemplateParamKind::Template:
 175       return printStr("TemplateParamKind::Template");
 176     }
 177   }
 178   void print(Node::Prec P) {
 179     switch (P) {
 180     case Node::Prec::Primary:
 181       return printStr("Node::Prec::Primary");
 182     case Node::Prec::Postfix:
 183       return printStr("Node::Prec::Postfix");
 184     case Node::Prec::Unary:
 185       return printStr("Node::Prec::Unary");
 186     case Node::Prec::Cast:
 187       return printStr("Node::Prec::Cast");
 188     case Node::Prec::PtrMem:
 189       return printStr("Node::Prec::PtrMem");
 190     case Node::Prec::Multiplicative:
 191       return printStr("Node::Prec::Multiplicative");
 192     case Node::Prec::Additive:
 193       return printStr("Node::Prec::Additive");
 194     case Node::Prec::Shift:
 195       return printStr("Node::Prec::Shift");
 196     case Node::Prec::Spaceship:
 197       return printStr("Node::Prec::Spaceship");
 198     case Node::Prec::Relational:
 199       return printStr("Node::Prec::Relational");
 200     case Node::Prec::Equality:
 201       return printStr("Node::Prec::Equality");
 202     case Node::Prec::And:
 203       return printStr("Node::Prec::And");
 204     case Node::Prec::Xor:
 205       return printStr("Node::Prec::Xor");
 206     case Node::Prec::Ior:
 207       return printStr("Node::Prec::Ior");
 208     case Node::Prec::AndIf:
 209       return printStr("Node::Prec::AndIf");
 210     case Node::Prec::OrIf:
 211       return printStr("Node::Prec::OrIf");
 212     case Node::Prec::Conditional:
 213       return printStr("Node::Prec::Conditional");
 214     case Node::Prec::Assign:
 215       return printStr("Node::Prec::Assign");
 216     case Node::Prec::Comma:
 217       return printStr("Node::Prec::Comma");
 218     case Node::Prec::Default:
 219       return printStr("Node::Prec::Default");
 220     }
 221   }
 222
 223   void newLine() {
 224     printStr("\n");
 225     for (unsigned I = 0; I != Depth; ++I)
 226       printStr(" ");
 227     PendingNewline = false;
 228   }
 229
 230   template<typename T> void printWithPendingNewline(T V) {
 231     print(V);
 232     if (wantsNewline(V))
 233       PendingNewline = true;
 234   }
 235
 236   template<typename T> void printWithComma(T V) {
 237     if (PendingNewline || wantsNewline(V)) {
 238       printStr(",");
 239       newLine();
 240     } else {
 241       printStr(", ");
 242     }
 243
 244     printWithPendingNewline(V);
 245   }
 246
 247   struct CtorArgPrinter {
 248     DumpVisitor &Visitor;
 249
 250     template<typename T, typename ...Rest> void operator()(T V, Rest ...Vs) {
 251       if (Visitor.anyWantNewline(V, Vs...))
 252         Visitor.newLine();
 253       Visitor.printWithPendingNewline(V);
 254       int PrintInOrder[] = { (Visitor.printWithComma(Vs), 0)..., 0 };
 255       (void)PrintInOrder;
 256     }
 257   };
 258
 259   template<typename NodeT> void operator()(const NodeT *Node) {
 260     Depth += 2;
 261     fprintf(stderr, "%s(", itanium_demangle::NodeKind<NodeT>::name());
 262     Node->match(CtorArgPrinter{*this});
 263     fprintf(stderr, ")");
 264     Depth -= 2;
 265   }
 266
 267   void operator()(const ForwardTemplateReference *Node) {
 268     Depth += 2;
 269     fprintf(stderr, "ForwardTemplateReference(");
 270     if (Node->Ref && !Node->Printing) {
 271       Node->Printing = true;
 272       CtorArgPrinter{*this}(Node->Ref);
 273       Node->Printing = false;
 274     } else {
 275       CtorArgPrinter{*this}(Node->Index);
 276     }
 277     fprintf(stderr, ")");
 278     Depth -= 2;
 279   }
 280 };
 281 }
 282
 283 void itanium_demangle::Node::dump() const {
 284   DumpVisitor V;
 285   visit(std::ref(V));
 286   V.newLine();
 287 }
 288 #endif
 289
 290 namespace {
 291 class BumpPointerAllocator {
 292   struct BlockMeta {
 293     BlockMeta* Next;
 294     size_t Current;
 295   };
 296
 297   static constexpr size_t AllocSize = 4096;
 298   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
 299
 300   alignas(long double) char InitialBuffer[AllocSize];
 301   BlockMeta* BlockList = nullptr;
 302
 303   void grow() {
 304     char* NewMeta = static_cast<char *>(std::malloc(AllocSize));
 305     if (NewMeta == nullptr)
 306       std::terminate();
 307     BlockList = new (NewMeta) BlockMeta{BlockList, 0};
 308   }
 309
 310   void* allocateMassive(size_t NBytes) {
 311     NBytes += sizeof(BlockMeta);
 312     BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(std::malloc(NBytes));
 313     if (NewMeta == nullptr)
 314       std::terminate();
 315     BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0};
 316     return static_cast<void*>(NewMeta + 1);
 317   }
 318
 319 public:
 320   BumpPointerAllocator()
 321       : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {}
 322
 323   void* allocate(size_t N) {
 324     N = (N + 15u) & ~15u;
 325     if (N + BlockList->Current >= UsableAllocSize) {
 326       if (N > UsableAllocSize)
 327         return allocateMassive(N);
 328       grow();
 329     }
 330     BlockList->Current += N;
 331     return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) +
 332                               BlockList->Current - N);
 333   }
 334
 335   void reset() {
 336     while (BlockList) {
 337       BlockMeta* Tmp = BlockList;
 338       BlockList = BlockList->Next;
 339       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
 340         std::free(Tmp);
 341     }
 342     BlockList = new (InitialBuffer) BlockMeta{nullptr, 0};
 343   }
 344
 345   ~BumpPointerAllocator() { reset(); }
 346 };
 347
 348 class DefaultAllocator {
 349   BumpPointerAllocator Alloc;
 350
 351 public:
 352   void reset() { Alloc.reset(); }
 353
 354   template<typename T, typename ...Args> T *makeNode(Args &&...args) {
 355     return new (Alloc.allocate(sizeof(T)))
 356         T(std::forward<Args>(args)...);
 357   }
 358
 359   void *allocateNodeArray(size_t sz) {
 360     return Alloc.allocate(sizeof(Node *) * sz);
 361   }
 362 };
 363 }  // unnamed namespace
 364
 365 //===----------------------------------------------------------------------===//
 366 // Code beyond this point should not be synchronized with LLVM.
 367 //===----------------------------------------------------------------------===//
 368
 369 using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
 370
 371 namespace {
 372 enum : int {
 373   demangle_invalid_args = -3,
 374   demangle_invalid_mangled_name = -2,
 375   demangle_memory_alloc_failure = -1,
 376   demangle_success = 0,
 377 };
 378 }
 379
 380 namespace __cxxabiv1 {
 381 extern "C" _LIBCXXABI_FUNC_VIS char *
 382 __cxa_demangle(const char *MangledName, char *Buf, size_t *N, int *Status) {
 383   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
 384     if (Status)
 385       *Status = demangle_invalid_args;
 386     return nullptr;
 387   }
 388
 389   int InternalStatus = demangle_success;
 390   Demangler Parser(MangledName, MangledName + std::strlen(MangledName));
 391   Node *AST = Parser.parse();
 392
 393   if (AST == nullptr)
 394     InternalStatus = demangle_invalid_mangled_name;
 395   else {
 396     OutputBuffer O(Buf, N);
 397     assert(Parser.ForwardTemplateRefs.empty());
 398     AST->print(O);
 399     O += '\0';
 400     if (N != nullptr)
 401       *N = O.getCurrentPosition();
 402     Buf = O.getBuffer();
 403   }
 404
 405   if (Status)
 406     *Status = InternalStatus;
 407   return InternalStatus == demangle_success ? Buf : nullptr;
 408 }
 409 }  // __cxxabiv1