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