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