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