xref: /freebsd/contrib/llvm-project/llvm/lib/Demangle/ItaniumDemangle.cpp (revision dd41de95a84d979615a2ef11df6850622bf6184e) 
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> std::enable_if_t<std::is_unsigned<T>::value> print(T N) {
111     fprintf(stderr, "%llu", (unsigned long long)N);
112   }
113 
114   template <class T> std::enable_if_t<std::is_signed<T>::value> print(T N) {
115     fprintf(stderr, "%lld", (long long)N);
116   }
117 
118   void print(ReferenceKind RK) {
119     switch (RK) {
120     case ReferenceKind::LValue:
121       return printStr("ReferenceKind::LValue");
122     case ReferenceKind::RValue:
123       return printStr("ReferenceKind::RValue");
124     }
125   }
126   void print(FunctionRefQual RQ) {
127     switch (RQ) {
128     case FunctionRefQual::FrefQualNone:
129       return printStr("FunctionRefQual::FrefQualNone");
130     case FunctionRefQual::FrefQualLValue:
131       return printStr("FunctionRefQual::FrefQualLValue");
132     case FunctionRefQual::FrefQualRValue:
133       return printStr("FunctionRefQual::FrefQualRValue");
134     }
135   }
136   void print(Qualifiers Qs) {
137     if (!Qs) return printStr("QualNone");
138     struct QualName { Qualifiers Q; const char *Name; } Names[] = {
139       {QualConst, "QualConst"},
140       {QualVolatile, "QualVolatile"},
141       {QualRestrict, "QualRestrict"},
142     };
143     for (QualName Name : Names) {
144       if (Qs & Name.Q) {
145         printStr(Name.Name);
146         Qs = Qualifiers(Qs & ~Name.Q);
147         if (Qs) printStr(" | ");
148       }
149     }
150   }
151   void print(SpecialSubKind SSK) {
152     switch (SSK) {
153     case SpecialSubKind::allocator:
154       return printStr("SpecialSubKind::allocator");
155     case SpecialSubKind::basic_string:
156       return printStr("SpecialSubKind::basic_string");
157     case SpecialSubKind::string:
158       return printStr("SpecialSubKind::string");
159     case SpecialSubKind::istream:
160       return printStr("SpecialSubKind::istream");
161     case SpecialSubKind::ostream:
162       return printStr("SpecialSubKind::ostream");
163     case SpecialSubKind::iostream:
164       return printStr("SpecialSubKind::iostream");
165     }
166   }
167   void print(TemplateParamKind TPK) {
168     switch (TPK) {
169     case TemplateParamKind::Type:
170       return printStr("TemplateParamKind::Type");
171     case TemplateParamKind::NonType:
172       return printStr("TemplateParamKind::NonType");
173     case TemplateParamKind::Template:
174       return printStr("TemplateParamKind::Template");
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 
238 void itanium_demangle::Node::dump() const {
239   DumpVisitor V;
240   visit(std::ref(V));
241   V.newLine();
242 }
243 #endif
244 
245 namespace {
246 class 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 
274 public:
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 
303 class DefaultAllocator {
304   BumpPointerAllocator Alloc;
305 
306 public:
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 
324 using Demangler = itanium_demangle::ManglingParser<DefaultAllocator>;
325 
326 char *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 
358 ItaniumPartialDemangler::ItaniumPartialDemangler()
359     : RootNode(nullptr), Context(new Demangler{nullptr, nullptr}) {}
360 
361 ItaniumPartialDemangler::~ItaniumPartialDemangler() {
362   delete static_cast<Demangler *>(Context);
363 }
364 
365 ItaniumPartialDemangler::ItaniumPartialDemangler(
366     ItaniumPartialDemangler &&Other)
367     : RootNode(Other.RootNode), Context(Other.Context) {
368   Other.Context = Other.RootNode = nullptr;
369 }
370 
371 ItaniumPartialDemangler &ItaniumPartialDemangler::
372 operator=(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.
379 bool 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 
387 static 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 
398 char *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 
427 char *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 
473 char *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 
480 char *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 
499 char *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 
518 char *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 
523 bool 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 
531 bool 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 
563 bool ItaniumPartialDemangler::isFunction() const {
564   assert(RootNode != nullptr && "must call partialDemangle()");
565   return static_cast<const Node *>(RootNode)->getKind() ==
566          Node::KFunctionEncoding;
567 }
568 
569 bool 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 
575 bool ItaniumPartialDemangler::isData() const {
576   return !isFunction() && !isSpecialName();
577 }
578