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 
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(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 
240 void itanium_demangle::Node::dump() const {
241   DumpVisitor V;
242   visit(std::ref(V));
243   V.newLine();
244 }
245 #endif
246 
247 namespace {
248 class 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 
276 public:
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 
305 class DefaultAllocator {
306   BumpPointerAllocator Alloc;
307 
308 public:
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 
326 using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
327 
328 char *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 
360 ItaniumPartialDemangler::ItaniumPartialDemangler()
361     : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
362 
363 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
364   delete static_cast<Demangler *>(Context);
365 }
366 
367 ItaniumPartialDemangler::ItaniumPartialDemangler(
368     ItaniumPartialDemangler &&Other)
369     : RootNode(Other.RootNode), Context(Other.Context) {
370   Other.Context = Other.RootNode = nullptr;
371 }
372 
373 ItaniumPartialDemangler &ItaniumPartialDemangler::
374 operator=(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.
381 bool 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 
389 static 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 
400 char *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 
429 char *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 
475 char *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 
482 char *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 
501 char *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 
520 char *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 
525 bool 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 
533 bool 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 
565 bool ItaniumPartialDemangler::isFunction() const {
566   assert(RootNode != nullptr && "must call partialDemangle()");
567   return static_cast<const Node *>(RootNode)->getKind() ==
568          Node::KFunctionEncoding;
569 }
570 
571 bool 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 
577 bool ItaniumPartialDemangler::isData() const {
578   return !isFunction() && !isSpecialName();
579 }
580