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