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
24using namespace llvm;
25using namespace llvm::itanium_demangle;
26
27constexpr const char *itanium_demangle::FloatData<float>::spec;
28constexpr const char *itanium_demangle::FloatData<double>::spec;
29constexpr 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
34const 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
62namespace {
63struct 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
280void itanium_demangle::Node::dump() const {
281  DumpVisitor V;
282  visit(std::ref(V));
283  V.newLine();
284}
285#endif
286
287namespace {
288class 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
316public:
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
345class DefaultAllocator {
346  BumpPointerAllocator Alloc;
347
348public:
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
366using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
367
368char *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  Node *AST = Parser.parse();
379
380  if (AST == nullptr)
381    InternalStatus = demangle_invalid_mangled_name;
382  else {
383    OutputBuffer OB(Buf, N);
384    assert(Parser.ForwardTemplateRefs.empty());
385    AST->print(OB);
386    OB += '\0';
387    if (N != nullptr)
388      *N = OB.getCurrentPosition();
389    Buf = OB.getBuffer();
390  }
391
392  if (Status)
393    *Status = InternalStatus;
394  return InternalStatus == demangle_success ? Buf : nullptr;
395}
396
397ItaniumPartialDemangler::ItaniumPartialDemangler()
398    : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
399
400ItaniumPartialDemangler::~ItaniumPartialDemangler() {
401  delete static_cast<Demangler *>(Context);
402}
403
404ItaniumPartialDemangler::ItaniumPartialDemangler(
405    ItaniumPartialDemangler &&Other)
406    : RootNode(Other.RootNode), Context(Other.Context) {
407  Other.Context = Other.RootNode = nullptr;
408}
409
410ItaniumPartialDemangler &ItaniumPartialDemangler::
411operator=(ItaniumPartialDemangler &&Other) {
412  std::swap(RootNode, Other.RootNode);
413  std::swap(Context, Other.Context);
414  return *this;
415}
416
417// Demangle MangledName into an AST, storing it into this->RootNode.
418bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
419  Demangler *Parser = static_cast<Demangler *>(Context);
420  size_t Len = std::strlen(MangledName);
421  Parser->reset(MangledName, MangledName + Len);
422  RootNode = Parser->parse();
423  return RootNode == nullptr;
424}
425
426static char *printNode(const Node *RootNode, char *Buf, size_t *N) {
427  OutputBuffer OB(Buf, N);
428  RootNode->print(OB);
429  OB += '\0';
430  if (N != nullptr)
431    *N = OB.getCurrentPosition();
432  return OB.getBuffer();
433}
434
435char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
436  if (!isFunction())
437    return nullptr;
438
439  const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
440
441  while (true) {
442    switch (Name->getKind()) {
443    case Node::KAbiTagAttr:
444      Name = static_cast<const AbiTagAttr *>(Name)->Base;
445      continue;
446    case Node::KModuleEntity:
447      Name = static_cast<const ModuleEntity *>(Name)->Name;
448      continue;
449    case Node::KNestedName:
450      Name = static_cast<const NestedName *>(Name)->Name;
451      continue;
452    case Node::KLocalName:
453      Name = static_cast<const LocalName *>(Name)->Entity;
454      continue;
455    case Node::KNameWithTemplateArgs:
456      Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
457      continue;
458    default:
459      return printNode(Name, Buf, N);
460    }
461  }
462}
463
464char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
465                                                          size_t *N) const {
466  if (!isFunction())
467    return nullptr;
468  const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
469
470  OutputBuffer OB(Buf, N);
471
472 KeepGoingLocalFunction:
473  while (true) {
474    if (Name->getKind() == Node::KAbiTagAttr) {
475      Name = static_cast<const AbiTagAttr *>(Name)->Base;
476      continue;
477    }
478    if (Name->getKind() == Node::KNameWithTemplateArgs) {
479      Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
480      continue;
481    }
482    break;
483  }
484
485  if (Name->getKind() == Node::KModuleEntity)
486    Name = static_cast<const ModuleEntity *>(Name)->Name;
487
488  switch (Name->getKind()) {
489  case Node::KNestedName:
490    static_cast<const NestedName *>(Name)->Qual->print(OB);
491    break;
492  case Node::KLocalName: {
493    auto *LN = static_cast<const LocalName *>(Name);
494    LN->Encoding->print(OB);
495    OB += "::";
496    Name = LN->Entity;
497    goto KeepGoingLocalFunction;
498  }
499  default:
500    break;
501  }
502  OB += '\0';
503  if (N != nullptr)
504    *N = OB.getCurrentPosition();
505  return OB.getBuffer();
506}
507
508char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
509  if (!isFunction())
510    return nullptr;
511  auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
512  return printNode(Name, Buf, N);
513}
514
515char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
516                                                     size_t *N) const {
517  if (!isFunction())
518    return nullptr;
519  NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
520
521  OutputBuffer OB(Buf, N);
522
523  OB += '(';
524  Params.printWithComma(OB);
525  OB += ')';
526  OB += '\0';
527  if (N != nullptr)
528    *N = OB.getCurrentPosition();
529  return OB.getBuffer();
530}
531
532char *ItaniumPartialDemangler::getFunctionReturnType(
533    char *Buf, size_t *N) const {
534  if (!isFunction())
535    return nullptr;
536
537  OutputBuffer OB(Buf, N);
538
539  if (const Node *Ret =
540          static_cast<const FunctionEncoding *>(RootNode)->getReturnType())
541    Ret->print(OB);
542
543  OB += '\0';
544  if (N != nullptr)
545    *N = OB.getCurrentPosition();
546  return OB.getBuffer();
547}
548
549char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
550  assert(RootNode != nullptr && "must call partialDemangle()");
551  return printNode(static_cast<Node *>(RootNode), Buf, N);
552}
553
554bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
555  assert(RootNode != nullptr && "must call partialDemangle()");
556  if (!isFunction())
557    return false;
558  auto *E = static_cast<const FunctionEncoding *>(RootNode);
559  return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
560}
561
562bool ItaniumPartialDemangler::isCtorOrDtor() const {
563  const Node *N = static_cast<const Node *>(RootNode);
564  while (N) {
565    switch (N->getKind()) {
566    default:
567      return false;
568    case Node::KCtorDtorName:
569      return true;
570
571    case Node::KAbiTagAttr:
572      N = static_cast<const AbiTagAttr *>(N)->Base;
573      break;
574    case Node::KFunctionEncoding:
575      N = static_cast<const FunctionEncoding *>(N)->getName();
576      break;
577    case Node::KLocalName:
578      N = static_cast<const LocalName *>(N)->Entity;
579      break;
580    case Node::KNameWithTemplateArgs:
581      N = static_cast<const NameWithTemplateArgs *>(N)->Name;
582      break;
583    case Node::KNestedName:
584      N = static_cast<const NestedName *>(N)->Name;
585      break;
586    case Node::KModuleEntity:
587      N = static_cast<const ModuleEntity *>(N)->Name;
588      break;
589    }
590  }
591  return false;
592}
593
594bool ItaniumPartialDemangler::isFunction() const {
595  assert(RootNode != nullptr && "must call partialDemangle()");
596  return static_cast<const Node *>(RootNode)->getKind() ==
597         Node::KFunctionEncoding;
598}
599
600bool ItaniumPartialDemangler::isSpecialName() const {
601  assert(RootNode != nullptr && "must call partialDemangle()");
602  auto K = static_cast<const Node *>(RootNode)->getKind();
603  return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
604}
605
606bool ItaniumPartialDemangler::isData() const {
607  return !isFunction() && !isSpecialName();
608}
609