lib/Demangle/ItaniumDemangle.cpp

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