lib/Demangle/ItaniumDemangle.cpp

   1 //===------------------------- ItaniumDemangle.cpp ------------------------===//
   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 "llvm/Demangle/Demangle.h"
  14 #include "llvm/Demangle/ItaniumDemangle.h"
  15
  16 #include <cassert>
  17 #include <cctype>
  18 #include <cstdio>
  19 #include <cstdlib>
  20 #include <cstring>
  21 #include <functional>
  22 #include <numeric>
  23 #include <utility>
  24 #include <vector>
  25
  26 using namespace llvm;
  27 using namespace llvm::itanium_demangle;
  28
  29 constexpr const char *itanium_demangle::FloatData<float>::spec;
  30 constexpr const char *itanium_demangle::FloatData<double>::spec;
  31 constexpr const char *itanium_demangle::FloatData<long double>::spec;
  32
  33 // <discriminator> := _ <non-negative number>      # when number < 10
  34 //                 := __ <non-negative number> _   # when number >= 10
  35 //  extension      := decimal-digit+               # at the end of string
  36 const char *itanium_demangle::parse_discriminator(const char *first,
  37                                                   const char *last) {
  38   // parse but ignore discriminator
  39   if (first != last) {
  40     if (*first == '_') {
  41       const char *t1 = first + 1;
  42       if (t1 != last) {
  43         if (std::isdigit(*t1))
  44           first = t1 + 1;
  45         else if (*t1 == '_') {
  46           for (++t1; t1 != last && std::isdigit(*t1); ++t1)
  47             ;
  48           if (t1 != last && *t1 == '_')
  49             first = t1 + 1;
  50         }
  51       }
  52     } else if (std::isdigit(*first)) {
  53       const char *t1 = first + 1;
  54       for (; t1 != last && std::isdigit(*t1); ++t1)
  55         ;
  56       if (t1 == last)
  57         first = last;
  58     }
  59   }
  60   return first;
  61 }
  62
  63 #ifndef NDEBUG
  64 namespace {
  65 struct DumpVisitor {
  66   unsigned Depth = 0;
  67   bool PendingNewline = false;
  68
  69   template<typename NodeT> static constexpr bool wantsNewline(const NodeT *) {
  70     return true;
  71   }
  72   static bool wantsNewline(NodeArray A) { return !A.empty(); }
  73   static constexpr bool wantsNewline(...) { return false; }
  74
  75   template<typename ...Ts> static bool anyWantNewline(Ts ...Vs) {
  76     for (bool B : {wantsNewline(Vs)...})
  77       if (B)
  78         return true;
  79     return false;
  80   }
  81
  82   void printStr(const char *S) { fprintf(stderr, "%s", S); }
  83   void print(StringView SV) {
  84     fprintf(stderr, "\"%.*s\"", (int)SV.size(), SV.begin());
  85   }
  86   void print(const Node *N) {
  87     if (N)
  88       N->visit(std::ref(*this));
  89     else
  90       printStr("<null>");
  91   }
  92   void print(NodeOrString NS) {
  93     if (NS.isNode())
  94       print(NS.asNode());
  95     else if (NS.isString())
  96       print(NS.asString());
  97     else
  98       printStr("NodeOrString()");
  99   }
 100   void print(NodeArray A) {
 101     ++Depth;
 102     printStr("{");
 103     bool First = true;
 104     for (const Node *N : A) {
 105       if (First)
 106         print(N);
 107       else
 108         printWithComma(N);
 109       First = false;
 110     }
 111     printStr("}");
 112     --Depth;
 113   }
 114
 115   // Overload used when T is exactly 'bool', not merely convertible to 'bool'.
 116   void print(bool B) { printStr(B ? "true" : "false"); }
 117
 118   template <class T>
 119   typename std::enable_if<std::is_unsigned<T>::value>::type print(T N) {
 120     fprintf(stderr, "%llu", (unsigned long long)N);
 121   }
 122
 123   template <class T>
 124   typename std::enable_if<std::is_signed<T>::value>::type print(T N) {
 125     fprintf(stderr, "%lld", (long long)N);
 126   }
 127
 128   void print(ReferenceKind RK) {
 129     switch (RK) {
 130     case ReferenceKind::LValue:
 131       return printStr("ReferenceKind::LValue");
 132     case ReferenceKind::RValue:
 133       return printStr("ReferenceKind::RValue");
 134     }
 135   }
 136   void print(FunctionRefQual RQ) {
 137     switch (RQ) {
 138     case FunctionRefQual::FrefQualNone:
 139       return printStr("FunctionRefQual::FrefQualNone");
 140     case FunctionRefQual::FrefQualLValue:
 141       return printStr("FunctionRefQual::FrefQualLValue");
 142     case FunctionRefQual::FrefQualRValue:
 143       return printStr("FunctionRefQual::FrefQualRValue");
 144     }
 145   }
 146   void print(Qualifiers Qs) {
 147     if (!Qs) return printStr("QualNone");
 148     struct QualName { Qualifiers Q; const char *Name; } Names[] = {
 149       {QualConst, "QualConst"},
 150       {QualVolatile, "QualVolatile"},
 151       {QualRestrict, "QualRestrict"},
 152     };
 153     for (QualName Name : Names) {
 154       if (Qs & Name.Q) {
 155         printStr(Name.Name);
 156         Qs = Qualifiers(Qs & ~Name.Q);
 157         if (Qs) printStr(" | ");
 158       }
 159     }
 160   }
 161   void print(SpecialSubKind SSK) {
 162     switch (SSK) {
 163     case SpecialSubKind::allocator:
 164       return printStr("SpecialSubKind::allocator");
 165     case SpecialSubKind::basic_string:
 166       return printStr("SpecialSubKind::basic_string");
 167     case SpecialSubKind::string:
 168       return printStr("SpecialSubKind::string");
 169     case SpecialSubKind::istream:
 170       return printStr("SpecialSubKind::istream");
 171     case SpecialSubKind::ostream:
 172       return printStr("SpecialSubKind::ostream");
 173     case SpecialSubKind::iostream:
 174       return printStr("SpecialSubKind::iostream");
 175     }
 176   }
 177   void print(TemplateParamKind TPK) {
 178     switch (TPK) {
 179     case TemplateParamKind::Type:
 180       return printStr("TemplateParamKind::Type");
 181     case TemplateParamKind::NonType:
 182       return printStr("TemplateParamKind::NonType");
 183     case TemplateParamKind::Template:
 184       return printStr("TemplateParamKind::Template");
 185     }
 186   }
 187
 188   void newLine() {
 189     printStr("\n");
 190     for (unsigned I = 0; I != Depth; ++I)
 191       printStr(" ");
 192     PendingNewline = false;
 193   }
 194
 195   template<typename T> void printWithPendingNewline(T V) {
 196     print(V);
 197     if (wantsNewline(V))
 198       PendingNewline = true;
 199   }
 200
 201   template<typename T> void printWithComma(T V) {
 202     if (PendingNewline || wantsNewline(V)) {
 203       printStr(",");
 204       newLine();
 205     } else {
 206       printStr(", ");
 207     }
 208
 209     printWithPendingNewline(V);
 210   }
 211
 212   struct CtorArgPrinter {
 213     DumpVisitor &Visitor;
 214
 215     template<typename T, typename ...Rest> void operator()(T V, Rest ...Vs) {
 216       if (Visitor.anyWantNewline(V, Vs...))
 217         Visitor.newLine();
 218       Visitor.printWithPendingNewline(V);
 219       int PrintInOrder[] = { (Visitor.printWithComma(Vs), 0)..., 0 };
 220       (void)PrintInOrder;
 221     }
 222   };
 223
 224   template<typename NodeT> void operator()(const NodeT *Node) {
 225     Depth += 2;
 226     fprintf(stderr, "%s(", itanium_demangle::NodeKind<NodeT>::name());
 227     Node->match(CtorArgPrinter{*this});
 228     fprintf(stderr, ")");
 229     Depth -= 2;
 230   }
 231
 232   void operator()(const ForwardTemplateReference *Node) {
 233     Depth += 2;
 234     fprintf(stderr, "ForwardTemplateReference(");
 235     if (Node->Ref && !Node->Printing) {
 236       Node->Printing = true;
 237       CtorArgPrinter{*this}(Node->Ref);
 238       Node->Printing = false;
 239     } else {
 240       CtorArgPrinter{*this}(Node->Index);
 241     }
 242     fprintf(stderr, ")");
 243     Depth -= 2;
 244   }
 245 };
 246 }
 247
 248 void itanium_demangle::Node::dump() const {
 249   DumpVisitor V;
 250   visit(std::ref(V));
 251   V.newLine();
 252 }
 253 #endif
 254
 255 namespace {
 256 class BumpPointerAllocator {
 257   struct BlockMeta {
 258     BlockMeta* Next;
 259     size_t Current;
 260   };
 261
 262   static constexpr size_t AllocSize = 4096;
 263   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
 264
 265   alignas(long double) char InitialBuffer[AllocSize];
 266   BlockMeta* BlockList = nullptr;
 267
 268   void grow() {
 269     char* NewMeta = static_cast<char *>(std::malloc(AllocSize));
 270     if (NewMeta == nullptr)
 271       std::terminate();
 272     BlockList = new (NewMeta) BlockMeta{BlockList, 0};
 273   }
 274
 275   void* allocateMassive(size_t NBytes) {
 276     NBytes += sizeof(BlockMeta);
 277     BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(std::malloc(NBytes));
 278     if (NewMeta == nullptr)
 279       std::terminate();
 280     BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0};
 281     return static_cast<void*>(NewMeta + 1);
 282   }
 283
 284 public:
 285   BumpPointerAllocator()
 286       : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {}
 287
 288   void* allocate(size_t N) {
 289     N = (N + 15u) & ~15u;
 290     if (N + BlockList->Current >= UsableAllocSize) {
 291       if (N > UsableAllocSize)
 292         return allocateMassive(N);
 293       grow();
 294     }
 295     BlockList->Current += N;
 296     return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) +
 297                               BlockList->Current - N);
 298   }
 299
 300   void reset() {
 301     while (BlockList) {
 302       BlockMeta* Tmp = BlockList;
 303       BlockList = BlockList->Next;
 304       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
 305         std::free(Tmp);
 306     }
 307     BlockList = new (InitialBuffer) BlockMeta{nullptr, 0};
 308   }
 309
 310   ~BumpPointerAllocator() { reset(); }
 311 };
 312
 313 class DefaultAllocator {
 314   BumpPointerAllocator Alloc;
 315
 316 public:
 317   void reset() { Alloc.reset(); }
 318
 319   template<typename T, typename ...Args> T *makeNode(Args &&...args) {
 320     return new (Alloc.allocate(sizeof(T)))
 321         T(std::forward<Args>(args)...);
 322   }
 323
 324   void *allocateNodeArray(size_t sz) {
 325     return Alloc.allocate(sizeof(Node *) * sz);
 326   }
 327 };
 328 }  // unnamed namespace
 329
 330 //===----------------------------------------------------------------------===//
 331 // Code beyond this point should not be synchronized with libc++abi.
 332 //===----------------------------------------------------------------------===//
 333
 334 using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
 335
 336 char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
 337                             size_t *N, int *Status) {
 338   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
 339     if (Status)
 340       *Status = demangle_invalid_args;
 341     return nullptr;
 342   }
 343
 344   int InternalStatus = demangle_success;
 345   Demangler Parser(MangledName, MangledName + std::strlen(MangledName));
 346   OutputStream S;
 347
 348   Node *AST = Parser.parse();
 349
 350   if (AST == nullptr)
 351     InternalStatus = demangle_invalid_mangled_name;
 352   else if (!initializeOutputStream(Buf, N, S, 1024))
 353     InternalStatus = demangle_memory_alloc_failure;
 354   else {
 355     assert(Parser.ForwardTemplateRefs.empty());
 356     AST->print(S);
 357     S += '\0';
 358     if (N != nullptr)
 359       *N = S.getCurrentPosition();
 360     Buf = S.getBuffer();
 361   }
 362
 363   if (Status)
 364     *Status = InternalStatus;
 365   return InternalStatus == demangle_success ? Buf : nullptr;
 366 }
 367
 368 ItaniumPartialDemangler::ItaniumPartialDemangler()
 369     : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
 370
 371 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
 372   delete static_cast<Demangler *>(Context);
 373 }
 374
 375 ItaniumPartialDemangler::ItaniumPartialDemangler(
 376     ItaniumPartialDemangler &&Other)
 377     : RootNode(Other.RootNode), Context(Other.Context) {
 378   Other.Context = Other.RootNode = nullptr;
 379 }
 380
 381 ItaniumPartialDemangler &ItaniumPartialDemangler::
 382 operator=(ItaniumPartialDemangler &&Other) {
 383   std::swap(RootNode, Other.RootNode);
 384   std::swap(Context, Other.Context);
 385   return *this;
 386 }
 387
 388 // Demangle MangledName into an AST, storing it into this->RootNode.
 389 bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
 390   Demangler *Parser = static_cast<Demangler *>(Context);
 391   size_t Len = std::strlen(MangledName);
 392   Parser->reset(MangledName, MangledName + Len);
 393   RootNode = Parser->parse();
 394   return RootNode == nullptr;
 395 }
 396
 397 static char *printNode(const Node *RootNode, char *Buf, size_t *N) {
 398   OutputStream S;
 399   if (!initializeOutputStream(Buf, N, S, 128))
 400     return nullptr;
 401   RootNode->print(S);
 402   S += '\0';
 403   if (N != nullptr)
 404     *N = S.getCurrentPosition();
 405   return S.getBuffer();
 406 }
 407
 408 char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
 409   if (!isFunction())
 410     return nullptr;
 411
 412   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 413
 414   while (true) {
 415     switch (Name->getKind()) {
 416     case Node::KAbiTagAttr:
 417       Name = static_cast<const AbiTagAttr *>(Name)->Base;
 418       continue;
 419     case Node::KStdQualifiedName:
 420       Name = static_cast<const StdQualifiedName *>(Name)->Child;
 421       continue;
 422     case Node::KNestedName:
 423       Name = static_cast<const NestedName *>(Name)->Name;
 424       continue;
 425     case Node::KLocalName:
 426       Name = static_cast<const LocalName *>(Name)->Entity;
 427       continue;
 428     case Node::KNameWithTemplateArgs:
 429       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
 430       continue;
 431     default:
 432       return printNode(Name, Buf, N);
 433     }
 434   }
 435 }
 436
 437 char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
 438                                                           size_t *N) const {
 439   if (!isFunction())
 440     return nullptr;
 441   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 442
 443   OutputStream S;
 444   if (!initializeOutputStream(Buf, N, S, 128))
 445     return nullptr;
 446
 447  KeepGoingLocalFunction:
 448   while (true) {
 449     if (Name->getKind() == Node::KAbiTagAttr) {
 450       Name = static_cast<const AbiTagAttr *>(Name)->Base;
 451       continue;
 452     }
 453     if (Name->getKind() == Node::KNameWithTemplateArgs) {
 454       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
 455       continue;
 456     }
 457     break;
 458   }
 459
 460   switch (Name->getKind()) {
 461   case Node::KStdQualifiedName:
 462     S += "std";
 463     break;
 464   case Node::KNestedName:
 465     static_cast<const NestedName *>(Name)->Qual->print(S);
 466     break;
 467   case Node::KLocalName: {
 468     auto *LN = static_cast<const LocalName *>(Name);
 469     LN->Encoding->print(S);
 470     S += "::";
 471     Name = LN->Entity;
 472     goto KeepGoingLocalFunction;
 473   }
 474   default:
 475     break;
 476   }
 477   S += '\0';
 478   if (N != nullptr)
 479     *N = S.getCurrentPosition();
 480   return S.getBuffer();
 481 }
 482
 483 char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
 484   if (!isFunction())
 485     return nullptr;
 486   auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
 487   return printNode(Name, Buf, N);
 488 }
 489
 490 char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
 491                                                      size_t *N) const {
 492   if (!isFunction())
 493     return nullptr;
 494   NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
 495
 496   OutputStream S;
 497   if (!initializeOutputStream(Buf, N, S, 128))
 498     return nullptr;
 499
 500   S += '(';
 501   Params.printWithComma(S);
 502   S += ')';
 503   S += '\0';
 504   if (N != nullptr)
 505     *N = S.getCurrentPosition();
 506   return S.getBuffer();
 507 }
 508
 509 char *ItaniumPartialDemangler::getFunctionReturnType(
 510     char *Buf, size_t *N) const {
 511   if (!isFunction())
 512     return nullptr;
 513
 514   OutputStream S;
 515   if (!initializeOutputStream(Buf, N, S, 128))
 516     return nullptr;
 517
 518   if (const Node *Ret =
 519           static_cast<const FunctionEncoding *>(RootNode)->getReturnType())
 520     Ret->print(S);
 521
 522   S += '\0';
 523   if (N != nullptr)
 524     *N = S.getCurrentPosition();
 525   return S.getBuffer();
 526 }
 527
 528 char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
 529   assert(RootNode != nullptr && "must call partialDemangle()");
 530   return printNode(static_cast<Node *>(RootNode), Buf, N);
 531 }
 532
 533 bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
 534   assert(RootNode != nullptr && "must call partialDemangle()");
 535   if (!isFunction())
 536     return false;
 537   auto *E = static_cast<const FunctionEncoding *>(RootNode);
 538   return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
 539 }
 540
 541 bool ItaniumPartialDemangler::isCtorOrDtor() const {
 542   const Node *N = static_cast<const Node *>(RootNode);
 543   while (N) {
 544     switch (N->getKind()) {
 545     default:
 546       return false;
 547     case Node::KCtorDtorName:
 548       return true;
 549
 550     case Node::KAbiTagAttr:
 551       N = static_cast<const AbiTagAttr *>(N)->Base;
 552       break;
 553     case Node::KFunctionEncoding:
 554       N = static_cast<const FunctionEncoding *>(N)->getName();
 555       break;
 556     case Node::KLocalName:
 557       N = static_cast<const LocalName *>(N)->Entity;
 558       break;
 559     case Node::KNameWithTemplateArgs:
 560       N = static_cast<const NameWithTemplateArgs *>(N)->Name;
 561       break;
 562     case Node::KNestedName:
 563       N = static_cast<const NestedName *>(N)->Name;
 564       break;
 565     case Node::KStdQualifiedName:
 566       N = static_cast<const StdQualifiedName *>(N)->Child;
 567       break;
 568     }
 569   }
 570   return false;
 571 }
 572
 573 bool ItaniumPartialDemangler::isFunction() const {
 574   assert(RootNode != nullptr && "must call partialDemangle()");
 575   return static_cast<const Node *>(RootNode)->getKind() ==
 576          Node::KFunctionEncoding;
 577 }
 578
 579 bool ItaniumPartialDemangler::isSpecialName() const {
 580   assert(RootNode != nullptr && "must call partialDemangle()");
 581   auto K = static_cast<const Node *>(RootNode)->getKind();
 582   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
 583 }
 584
 585 bool ItaniumPartialDemangler::isData() const {
 586   return !isFunction() && !isSpecialName();
 587 }