llvm/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 <utility>
  23
  24 using namespace llvm;
  25 using namespace llvm::itanium_demangle;
  26
  27 constexpr const char *itanium_demangle::FloatData<float>::spec;
  28 constexpr const char *itanium_demangle::FloatData<double>::spec;
  29 constexpr const char *itanium_demangle::FloatData<long double>::spec;
  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(StringView 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> std::enable_if_t<std::is_unsigned<T>::value> print(T N) {
 109     fprintf(stderr, "%llu", (unsigned long long)N);
 110   }
 111
 112   template <class T> std::enable_if_t<std::is_signed<T>::value> print(T N) {
 113     fprintf(stderr, "%lld", (long long)N);
 114   }
 115
 116   void print(ReferenceKind RK) {
 117     switch (RK) {
 118     case ReferenceKind::LValue:
 119       return printStr("ReferenceKind::LValue");
 120     case ReferenceKind::RValue:
 121       return printStr("ReferenceKind::RValue");
 122     }
 123   }
 124   void print(FunctionRefQual RQ) {
 125     switch (RQ) {
 126     case FunctionRefQual::FrefQualNone:
 127       return printStr("FunctionRefQual::FrefQualNone");
 128     case FunctionRefQual::FrefQualLValue:
 129       return printStr("FunctionRefQual::FrefQualLValue");
 130     case FunctionRefQual::FrefQualRValue:
 131       return printStr("FunctionRefQual::FrefQualRValue");
 132     }
 133   }
 134   void print(Qualifiers Qs) {
 135     if (!Qs) return printStr("QualNone");
 136     struct QualName { Qualifiers Q; const char *Name; } Names[] = {
 137       {QualConst, "QualConst"},
 138       {QualVolatile, "QualVolatile"},
 139       {QualRestrict, "QualRestrict"},
 140     };
 141     for (QualName Name : Names) {
 142       if (Qs & Name.Q) {
 143         printStr(Name.Name);
 144         Qs = Qualifiers(Qs & ~Name.Q);
 145         if (Qs) printStr(" | ");
 146       }
 147     }
 148   }
 149   void print(SpecialSubKind SSK) {
 150     switch (SSK) {
 151     case SpecialSubKind::allocator:
 152       return printStr("SpecialSubKind::allocator");
 153     case SpecialSubKind::basic_string:
 154       return printStr("SpecialSubKind::basic_string");
 155     case SpecialSubKind::string:
 156       return printStr("SpecialSubKind::string");
 157     case SpecialSubKind::istream:
 158       return printStr("SpecialSubKind::istream");
 159     case SpecialSubKind::ostream:
 160       return printStr("SpecialSubKind::ostream");
 161     case SpecialSubKind::iostream:
 162       return printStr("SpecialSubKind::iostream");
 163     }
 164   }
 165   void print(TemplateParamKind TPK) {
 166     switch (TPK) {
 167     case TemplateParamKind::Type:
 168       return printStr("TemplateParamKind::Type");
 169     case TemplateParamKind::NonType:
 170       return printStr("TemplateParamKind::NonType");
 171     case TemplateParamKind::Template:
 172       return printStr("TemplateParamKind::Template");
 173     }
 174   }
 175   void print(Node::Prec P) {
 176     switch (P) {
 177     case Node::Prec::Primary:
 178       return printStr("Node::Prec::Primary");
 179     case Node::Prec::Postfix:
 180       return printStr("Node::Prec::Postfix");
 181     case Node::Prec::Unary:
 182       return printStr("Node::Prec::Unary");
 183     case Node::Prec::Cast:
 184       return printStr("Node::Prec::Cast");
 185     case Node::Prec::PtrMem:
 186       return printStr("Node::Prec::PtrMem");
 187     case Node::Prec::Multiplicative:
 188       return printStr("Node::Prec::Multiplicative");
 189     case Node::Prec::Additive:
 190       return printStr("Node::Prec::Additive");
 191     case Node::Prec::Shift:
 192       return printStr("Node::Prec::Shift");
 193     case Node::Prec::Spaceship:
 194       return printStr("Node::Prec::Spaceship");
 195     case Node::Prec::Relational:
 196       return printStr("Node::Prec::Relational");
 197     case Node::Prec::Equality:
 198       return printStr("Node::Prec::Equality");
 199     case Node::Prec::And:
 200       return printStr("Node::Prec::And");
 201     case Node::Prec::Xor:
 202       return printStr("Node::Prec::Xor");
 203     case Node::Prec::Ior:
 204       return printStr("Node::Prec::Ior");
 205     case Node::Prec::AndIf:
 206       return printStr("Node::Prec::AndIf");
 207     case Node::Prec::OrIf:
 208       return printStr("Node::Prec::OrIf");
 209     case Node::Prec::Conditional:
 210       return printStr("Node::Prec::Conditional");
 211     case Node::Prec::Assign:
 212       return printStr("Node::Prec::Assign");
 213     case Node::Prec::Comma:
 214       return printStr("Node::Prec::Comma");
 215     case Node::Prec::Default:
 216       return printStr("Node::Prec::Default");
 217     }
 218   }
 219
 220   void newLine() {
 221     printStr("\n");
 222     for (unsigned I = 0; I != Depth; ++I)
 223       printStr(" ");
 224     PendingNewline = false;
 225   }
 226
 227   template<typename T> void printWithPendingNewline(T V) {
 228     print(V);
 229     if (wantsNewline(V))
 230       PendingNewline = true;
 231   }
 232
 233   template<typename T> void printWithComma(T V) {
 234     if (PendingNewline || wantsNewline(V)) {
 235       printStr(",");
 236       newLine();
 237     } else {
 238       printStr(", ");
 239     }
 240
 241     printWithPendingNewline(V);
 242   }
 243
 244   struct CtorArgPrinter {
 245     DumpVisitor &Visitor;
 246
 247     template<typename T, typename ...Rest> void operator()(T V, Rest ...Vs) {
 248       if (Visitor.anyWantNewline(V, Vs...))
 249         Visitor.newLine();
 250       Visitor.printWithPendingNewline(V);
 251       int PrintInOrder[] = { (Visitor.printWithComma(Vs), 0)..., 0 };
 252       (void)PrintInOrder;
 253     }
 254   };
 255
 256   template<typename NodeT> void operator()(const NodeT *Node) {
 257     Depth += 2;
 258     fprintf(stderr, "%s(", itanium_demangle::NodeKind<NodeT>::name());
 259     Node->match(CtorArgPrinter{*this});
 260     fprintf(stderr, ")");
 261     Depth -= 2;
 262   }
 263
 264   void operator()(const ForwardTemplateReference *Node) {
 265     Depth += 2;
 266     fprintf(stderr, "ForwardTemplateReference(");
 267     if (Node->Ref && !Node->Printing) {
 268       Node->Printing = true;
 269       CtorArgPrinter{*this}(Node->Ref);
 270       Node->Printing = false;
 271     } else {
 272       CtorArgPrinter{*this}(Node->Index);
 273     }
 274     fprintf(stderr, ")");
 275     Depth -= 2;
 276   }
 277 };
 278 }
 279
 280 void itanium_demangle::Node::dump() const {
 281   DumpVisitor V;
 282   visit(std::ref(V));
 283   V.newLine();
 284 }
 285 #endif
 286
 287 namespace {
 288 class BumpPointerAllocator {
 289   struct BlockMeta {
 290     BlockMeta* Next;
 291     size_t Current;
 292   };
 293
 294   static constexpr size_t AllocSize = 4096;
 295   static constexpr size_t UsableAllocSize = AllocSize - sizeof(BlockMeta);
 296
 297   alignas(long double) char InitialBuffer[AllocSize];
 298   BlockMeta* BlockList = nullptr;
 299
 300   void grow() {
 301     char* NewMeta = static_cast<char *>(std::malloc(AllocSize));
 302     if (NewMeta == nullptr)
 303       std::terminate();
 304     BlockList = new (NewMeta) BlockMeta{BlockList, 0};
 305   }
 306
 307   void* allocateMassive(size_t NBytes) {
 308     NBytes += sizeof(BlockMeta);
 309     BlockMeta* NewMeta = reinterpret_cast<BlockMeta*>(std::malloc(NBytes));
 310     if (NewMeta == nullptr)
 311       std::terminate();
 312     BlockList->Next = new (NewMeta) BlockMeta{BlockList->Next, 0};
 313     return static_cast<void*>(NewMeta + 1);
 314   }
 315
 316 public:
 317   BumpPointerAllocator()
 318       : BlockList(new (InitialBuffer) BlockMeta{nullptr, 0}) {}
 319
 320   void* allocate(size_t N) {
 321     N = (N + 15u) & ~15u;
 322     if (N + BlockList->Current >= UsableAllocSize) {
 323       if (N > UsableAllocSize)
 324         return allocateMassive(N);
 325       grow();
 326     }
 327     BlockList->Current += N;
 328     return static_cast<void*>(reinterpret_cast<char*>(BlockList + 1) +
 329                               BlockList->Current - N);
 330   }
 331
 332   void reset() {
 333     while (BlockList) {
 334       BlockMeta* Tmp = BlockList;
 335       BlockList = BlockList->Next;
 336       if (reinterpret_cast<char*>(Tmp) != InitialBuffer)
 337         std::free(Tmp);
 338     }
 339     BlockList = new (InitialBuffer) BlockMeta{nullptr, 0};
 340   }
 341
 342   ~BumpPointerAllocator() { reset(); }
 343 };
 344
 345 class DefaultAllocator {
 346   BumpPointerAllocator Alloc;
 347
 348 public:
 349   void reset() { Alloc.reset(); }
 350
 351   template<typename T, typename ...Args> T *makeNode(Args &&...args) {
 352     return new (Alloc.allocate(sizeof(T)))
 353         T(std::forward<Args>(args)...);
 354   }
 355
 356   void *allocateNodeArray(size_t sz) {
 357     return Alloc.allocate(sizeof(Node *) * sz);
 358   }
 359 };
 360 }  // unnamed namespace
 361
 362 //===----------------------------------------------------------------------===//
 363 // Code beyond this point should not be synchronized with libc++abi.
 364 //===----------------------------------------------------------------------===//
 365
 366 using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
 367
 368 char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
 369                             size_t *N, int *Status) {
 370   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
 371     if (Status)
 372       *Status = demangle_invalid_args;
 373     return nullptr;
 374   }
 375
 376   int InternalStatus = demangle_success;
 377   Demangler Parser(MangledName, MangledName + std::strlen(MangledName));
 378   OutputBuffer OB;
 379
 380   Node *AST = Parser.parse();
 381
 382   if (AST == nullptr)
 383     InternalStatus = demangle_invalid_mangled_name;
 384   else if (!initializeOutputBuffer(Buf, N, OB, 1024))
 385     InternalStatus = demangle_memory_alloc_failure;
 386   else {
 387     assert(Parser.ForwardTemplateRefs.empty());
 388     AST->print(OB);
 389     OB += '\0';
 390     if (N != nullptr)
 391       *N = OB.getCurrentPosition();
 392     Buf = OB.getBuffer();
 393   }
 394
 395   if (Status)
 396     *Status = InternalStatus;
 397   return InternalStatus == demangle_success ? Buf : nullptr;
 398 }
 399
 400 ItaniumPartialDemangler::ItaniumPartialDemangler()
 401     : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
 402
 403 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
 404   delete static_cast<Demangler *>(Context);
 405 }
 406
 407 ItaniumPartialDemangler::ItaniumPartialDemangler(
 408     ItaniumPartialDemangler &&Other)
 409     : RootNode(Other.RootNode), Context(Other.Context) {
 410   Other.Context = Other.RootNode = nullptr;
 411 }
 412
 413 ItaniumPartialDemangler &ItaniumPartialDemangler::
 414 operator=(ItaniumPartialDemangler &&Other) {
 415   std::swap(RootNode, Other.RootNode);
 416   std::swap(Context, Other.Context);
 417   return *this;
 418 }
 419
 420 // Demangle MangledName into an AST, storing it into this->RootNode.
 421 bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
 422   Demangler *Parser = static_cast<Demangler *>(Context);
 423   size_t Len = std::strlen(MangledName);
 424   Parser->reset(MangledName, MangledName + Len);
 425   RootNode = Parser->parse();
 426   return RootNode == nullptr;
 427 }
 428
 429 static char *printNode(const Node *RootNode, char *Buf, size_t *N) {
 430   OutputBuffer OB;
 431   if (!initializeOutputBuffer(Buf, N, OB, 128))
 432     return nullptr;
 433   RootNode->print(OB);
 434   OB += '\0';
 435   if (N != nullptr)
 436     *N = OB.getCurrentPosition();
 437   return OB.getBuffer();
 438 }
 439
 440 char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
 441   if (!isFunction())
 442     return nullptr;
 443
 444   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 445
 446   while (true) {
 447     switch (Name->getKind()) {
 448     case Node::KAbiTagAttr:
 449       Name = static_cast<const AbiTagAttr *>(Name)->Base;
 450       continue;
 451     case Node::KModuleEntity:
 452       Name = static_cast<const ModuleEntity *>(Name)->Name;
 453       continue;
 454     case Node::KNestedName:
 455       Name = static_cast<const NestedName *>(Name)->Name;
 456       continue;
 457     case Node::KLocalName:
 458       Name = static_cast<const LocalName *>(Name)->Entity;
 459       continue;
 460     case Node::KNameWithTemplateArgs:
 461       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
 462       continue;
 463     default:
 464       return printNode(Name, Buf, N);
 465     }
 466   }
 467 }
 468
 469 char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
 470                                                           size_t *N) const {
 471   if (!isFunction())
 472     return nullptr;
 473   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
 474
 475   OutputBuffer OB;
 476   if (!initializeOutputBuffer(Buf, N, OB, 128))
 477     return nullptr;
 478
 479  KeepGoingLocalFunction:
 480   while (true) {
 481     if (Name->getKind() == Node::KAbiTagAttr) {
 482       Name = static_cast<const AbiTagAttr *>(Name)->Base;
 483       continue;
 484     }
 485     if (Name->getKind() == Node::KNameWithTemplateArgs) {
 486       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
 487       continue;
 488     }
 489     break;
 490   }
 491
 492   if (Name->getKind() == Node::KModuleEntity)
 493     Name = static_cast<const ModuleEntity *>(Name)->Name;
 494
 495   switch (Name->getKind()) {
 496   case Node::KNestedName:
 497     static_cast<const NestedName *>(Name)->Qual->print(OB);
 498     break;
 499   case Node::KLocalName: {
 500     auto *LN = static_cast<const LocalName *>(Name);
 501     LN->Encoding->print(OB);
 502     OB += "::";
 503     Name = LN->Entity;
 504     goto KeepGoingLocalFunction;
 505   }
 506   default:
 507     break;
 508   }
 509   OB += '\0';
 510   if (N != nullptr)
 511     *N = OB.getCurrentPosition();
 512   return OB.getBuffer();
 513 }
 514
 515 char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
 516   if (!isFunction())
 517     return nullptr;
 518   auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
 519   return printNode(Name, Buf, N);
 520 }
 521
 522 char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
 523                                                      size_t *N) const {
 524   if (!isFunction())
 525     return nullptr;
 526   NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
 527
 528   OutputBuffer OB;
 529   if (!initializeOutputBuffer(Buf, N, OB, 128))
 530     return nullptr;
 531
 532   OB += '(';
 533   Params.printWithComma(OB);
 534   OB += ')';
 535   OB += '\0';
 536   if (N != nullptr)
 537     *N = OB.getCurrentPosition();
 538   return OB.getBuffer();
 539 }
 540
 541 char *ItaniumPartialDemangler::getFunctionReturnType(
 542     char *Buf, size_t *N) const {
 543   if (!isFunction())
 544     return nullptr;
 545
 546   OutputBuffer OB;
 547   if (!initializeOutputBuffer(Buf, N, OB, 128))
 548     return nullptr;
 549
 550   if (const Node *Ret =
 551           static_cast<const FunctionEncoding *>(RootNode)->getReturnType())
 552     Ret->print(OB);
 553
 554   OB += '\0';
 555   if (N != nullptr)
 556     *N = OB.getCurrentPosition();
 557   return OB.getBuffer();
 558 }
 559
 560 char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
 561   assert(RootNode != nullptr && "must call partialDemangle()");
 562   return printNode(static_cast<Node *>(RootNode), Buf, N);
 563 }
 564
 565 bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
 566   assert(RootNode != nullptr && "must call partialDemangle()");
 567   if (!isFunction())
 568     return false;
 569   auto *E = static_cast<const FunctionEncoding *>(RootNode);
 570   return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
 571 }
 572
 573 bool ItaniumPartialDemangler::isCtorOrDtor() const {
 574   const Node *N = static_cast<const Node *>(RootNode);
 575   while (N) {
 576     switch (N->getKind()) {
 577     default:
 578       return false;
 579     case Node::KCtorDtorName:
 580       return true;
 581
 582     case Node::KAbiTagAttr:
 583       N = static_cast<const AbiTagAttr *>(N)->Base;
 584       break;
 585     case Node::KFunctionEncoding:
 586       N = static_cast<const FunctionEncoding *>(N)->getName();
 587       break;
 588     case Node::KLocalName:
 589       N = static_cast<const LocalName *>(N)->Entity;
 590       break;
 591     case Node::KNameWithTemplateArgs:
 592       N = static_cast<const NameWithTemplateArgs *>(N)->Name;
 593       break;
 594     case Node::KNestedName:
 595       N = static_cast<const NestedName *>(N)->Name;
 596       break;
 597     case Node::KModuleEntity:
 598       N = static_cast<const ModuleEntity *>(N)->Name;
 599       break;
 600     }
 601   }
 602   return false;
 603 }
 604
 605 bool ItaniumPartialDemangler::isFunction() const {
 606   assert(RootNode != nullptr && "must call partialDemangle()");
 607   return static_cast<const Node *>(RootNode)->getKind() ==
 608          Node::KFunctionEncoding;
 609 }
 610
 611 bool ItaniumPartialDemangler::isSpecialName() const {
 612   assert(RootNode != nullptr && "must call partialDemangle()");
 613   auto K = static_cast<const Node *>(RootNode)->getKind();
 614   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
 615 }
 616
 617 bool ItaniumPartialDemangler::isData() const {
 618   return !isFunction() && !isSpecialName();
 619 }