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