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 
314 bool initializeOutputStream(char *Buf, size_t *N, OutputStream &S,
315                             size_t InitSize) {
316   size_t BufferSize;
317   if (Buf == nullptr) {
318     Buf = static_cast<char *>(std::malloc(InitSize));
319     if (Buf == nullptr)
320       return true;
321     BufferSize = InitSize;
322   } else
323     BufferSize = *N;
324 
325   S.reset(Buf, BufferSize);
326   return false;
327 }
328 }  // unnamed namespace
329 
330 //===----------------------------------------------------------------------===//
331 // Code beyond this point should not be synchronized with libc++abi.
332 //===----------------------------------------------------------------------===//
333 
334 using Demangler = itanium_demangle::Db<DefaultAllocator>;
335 
336 char *llvm::itaniumDemangle(const char *MangledName, char *Buf,
337                             size_t *N, int *Status) {
338   if (MangledName == nullptr || (Buf != nullptr && N == nullptr)) {
339     if (Status)
340       *Status = demangle_invalid_args;
341     return nullptr;
342   }
343 
344   int InternalStatus = demangle_success;
345   Demangler Parser(MangledName, MangledName + std::strlen(MangledName));
346   OutputStream S;
347 
348   Node *AST = Parser.parse();
349 
350   if (AST == nullptr)
351     InternalStatus = demangle_invalid_mangled_name;
352   else if (initializeOutputStream(Buf, N, S, 1024))
353     InternalStatus = demangle_memory_alloc_failure;
354   else {
355     assert(Parser.ForwardTemplateRefs.empty());
356     AST->print(S);
357     S += '\0';
358     if (N != nullptr)
359       *N = S.getCurrentPosition();
360     Buf = S.getBuffer();
361   }
362 
363   if (Status)
364     *Status = InternalStatus;
365   return InternalStatus == demangle_success ? Buf : nullptr;
366 }
367 
368 bool llvm::itaniumFindTypesInMangledName(const char *MangledName, void *Ctx,
369                                          void (*Callback)(void *,
370                                                           const char *)) {
371   Demangler Parser(MangledName, MangledName + std::strlen(MangledName));
372   Parser.TypeCallback = Callback;
373   Parser.TypeCallbackContext = Ctx;
374   return Parser.parse() == nullptr;
375 }
376 
377 ItaniumPartialDemangler::ItaniumPartialDemangler()
378     : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
379 
380 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
381   delete static_cast<Demangler *>(Context);
382 }
383 
384 ItaniumPartialDemangler::ItaniumPartialDemangler(
385     ItaniumPartialDemangler &&Other)
386     : RootNode(Other.RootNode), Context(Other.Context) {
387   Other.Context = Other.RootNode = nullptr;
388 }
389 
390 ItaniumPartialDemangler &ItaniumPartialDemangler::
391 operator=(ItaniumPartialDemangler &&Other) {
392   std::swap(RootNode, Other.RootNode);
393   std::swap(Context, Other.Context);
394   return *this;
395 }
396 
397 // Demangle MangledName into an AST, storing it into this->RootNode.
398 bool ItaniumPartialDemangler::partialDemangle(const char *MangledName) {
399   Demangler *Parser = static_cast<Demangler *>(Context);
400   size_t Len = std::strlen(MangledName);
401   Parser->reset(MangledName, MangledName + Len);
402   RootNode = Parser->parse();
403   return RootNode == nullptr;
404 }
405 
406 static char *printNode(const Node *RootNode, char *Buf, size_t *N) {
407   OutputStream S;
408   if (initializeOutputStream(Buf, N, S, 128))
409     return nullptr;
410   RootNode->print(S);
411   S += '\0';
412   if (N != nullptr)
413     *N = S.getCurrentPosition();
414   return S.getBuffer();
415 }
416 
417 char *ItaniumPartialDemangler::getFunctionBaseName(char *Buf, size_t *N) const {
418   if (!isFunction())
419     return nullptr;
420 
421   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
422 
423   while (true) {
424     switch (Name->getKind()) {
425     case Node::KAbiTagAttr:
426       Name = static_cast<const AbiTagAttr *>(Name)->Base;
427       continue;
428     case Node::KStdQualifiedName:
429       Name = static_cast<const StdQualifiedName *>(Name)->Child;
430       continue;
431     case Node::KNestedName:
432       Name = static_cast<const NestedName *>(Name)->Name;
433       continue;
434     case Node::KLocalName:
435       Name = static_cast<const LocalName *>(Name)->Entity;
436       continue;
437     case Node::KNameWithTemplateArgs:
438       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
439       continue;
440     default:
441       return printNode(Name, Buf, N);
442     }
443   }
444 }
445 
446 char *ItaniumPartialDemangler::getFunctionDeclContextName(char *Buf,
447                                                           size_t *N) const {
448   if (!isFunction())
449     return nullptr;
450   const Node *Name = static_cast<const FunctionEncoding *>(RootNode)->getName();
451 
452   OutputStream S;
453   if (initializeOutputStream(Buf, N, S, 128))
454     return nullptr;
455 
456  KeepGoingLocalFunction:
457   while (true) {
458     if (Name->getKind() == Node::KAbiTagAttr) {
459       Name = static_cast<const AbiTagAttr *>(Name)->Base;
460       continue;
461     }
462     if (Name->getKind() == Node::KNameWithTemplateArgs) {
463       Name = static_cast<const NameWithTemplateArgs *>(Name)->Name;
464       continue;
465     }
466     break;
467   }
468 
469   switch (Name->getKind()) {
470   case Node::KStdQualifiedName:
471     S += "std";
472     break;
473   case Node::KNestedName:
474     static_cast<const NestedName *>(Name)->Qual->print(S);
475     break;
476   case Node::KLocalName: {
477     auto *LN = static_cast<const LocalName *>(Name);
478     LN->Encoding->print(S);
479     S += "::";
480     Name = LN->Entity;
481     goto KeepGoingLocalFunction;
482   }
483   default:
484     break;
485   }
486   S += '\0';
487   if (N != nullptr)
488     *N = S.getCurrentPosition();
489   return S.getBuffer();
490 }
491 
492 char *ItaniumPartialDemangler::getFunctionName(char *Buf, size_t *N) const {
493   if (!isFunction())
494     return nullptr;
495   auto *Name = static_cast<FunctionEncoding *>(RootNode)->getName();
496   return printNode(Name, Buf, N);
497 }
498 
499 char *ItaniumPartialDemangler::getFunctionParameters(char *Buf,
500                                                      size_t *N) const {
501   if (!isFunction())
502     return nullptr;
503   NodeArray Params = static_cast<FunctionEncoding *>(RootNode)->getParams();
504 
505   OutputStream S;
506   if (initializeOutputStream(Buf, N, S, 128))
507     return nullptr;
508 
509   S += '(';
510   Params.printWithComma(S);
511   S += ')';
512   S += '\0';
513   if (N != nullptr)
514     *N = S.getCurrentPosition();
515   return S.getBuffer();
516 }
517 
518 char *ItaniumPartialDemangler::getFunctionReturnType(
519     char *Buf, size_t *N) const {
520   if (!isFunction())
521     return nullptr;
522 
523   OutputStream S;
524   if (initializeOutputStream(Buf, N, S, 128))
525     return nullptr;
526 
527   if (const Node *Ret =
528           static_cast<const FunctionEncoding *>(RootNode)->getReturnType())
529     Ret->print(S);
530 
531   S += '\0';
532   if (N != nullptr)
533     *N = S.getCurrentPosition();
534   return S.getBuffer();
535 }
536 
537 char *ItaniumPartialDemangler::finishDemangle(char *Buf, size_t *N) const {
538   assert(RootNode != nullptr && "must call partialDemangle()");
539   return printNode(static_cast<Node *>(RootNode), Buf, N);
540 }
541 
542 bool ItaniumPartialDemangler::hasFunctionQualifiers() const {
543   assert(RootNode != nullptr && "must call partialDemangle()");
544   if (!isFunction())
545     return false;
546   auto *E = static_cast<const FunctionEncoding *>(RootNode);
547   return E->getCVQuals() != QualNone || E->getRefQual() != FrefQualNone;
548 }
549 
550 bool ItaniumPartialDemangler::isCtorOrDtor() const {
551   const Node *N = static_cast<const Node *>(RootNode);
552   while (N) {
553     switch (N->getKind()) {
554     default:
555       return false;
556     case Node::KCtorDtorName:
557       return true;
558 
559     case Node::KAbiTagAttr:
560       N = static_cast<const AbiTagAttr *>(N)->Base;
561       break;
562     case Node::KFunctionEncoding:
563       N = static_cast<const FunctionEncoding *>(N)->getName();
564       break;
565     case Node::KLocalName:
566       N = static_cast<const LocalName *>(N)->Entity;
567       break;
568     case Node::KNameWithTemplateArgs:
569       N = static_cast<const NameWithTemplateArgs *>(N)->Name;
570       break;
571     case Node::KNestedName:
572       N = static_cast<const NestedName *>(N)->Name;
573       break;
574     case Node::KStdQualifiedName:
575       N = static_cast<const StdQualifiedName *>(N)->Child;
576       break;
577     }
578   }
579   return false;
580 }
581 
582 bool ItaniumPartialDemangler::isFunction() const {
583   assert(RootNode != nullptr && "must call partialDemangle()");
584   return static_cast<const Node *>(RootNode)->getKind() ==
585          Node::KFunctionEncoding;
586 }
587 
588 bool ItaniumPartialDemangler::isSpecialName() const {
589   assert(RootNode != nullptr && "must call partialDemangle()");
590   auto K = static_cast<const Node *>(RootNode)->getKind();
591   return K == Node::KSpecialName || K == Node::KCtorVtableSpecialName;
592 }
593 
594 bool ItaniumPartialDemangler::isData() const {
595   return !isFunction() && !isSpecialName();
596 }
597