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