1 //===------------------------- MicrosoftDemangle.h --------------*- C++ -*-===//
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 #ifndef LLVM_DEMANGLE_MICROSOFT_DEMANGLE_H
10 #define LLVM_DEMANGLE_MICROSOFT_DEMANGLE_H
11 
12 #include "llvm/Demangle/DemangleConfig.h"
13 #include "llvm/Demangle/MicrosoftDemangleNodes.h"
14 #include "llvm/Demangle/StringView.h"
15 #include "llvm/Demangle/Utility.h"
16 
17 #include <utility>
18 
19 namespace llvm {
20 namespace ms_demangle {
21 // This memory allocator is extremely fast, but it doesn't call dtors
22 // for allocated objects. That means you can't use STL containers
23 // (such as std::vector) with this allocator. But it pays off --
24 // the demangler is 3x faster with this allocator compared to one with
25 // STL containers.
26 constexpr size_t AllocUnit = 4096;
27 
28 class ArenaAllocator {
29   struct AllocatorNode {
30     uint8_t *Buf = nullptr;
31     size_t Used = 0;
32     size_t Capacity = 0;
33     AllocatorNode *Next = nullptr;
34   };
35 
addNode(size_t Capacity)36   void addNode(size_t Capacity) {
37     AllocatorNode *NewHead = new AllocatorNode;
38     NewHead->Buf = new uint8_t[Capacity];
39     NewHead->Next = Head;
40     NewHead->Capacity = Capacity;
41     Head = NewHead;
42     NewHead->Used = 0;
43   }
44 
45 public:
ArenaAllocator()46   ArenaAllocator() { addNode(AllocUnit); }
47 
~ArenaAllocator()48   ~ArenaAllocator() {
49     while (Head) {
50       assert(Head->Buf);
51       delete[] Head->Buf;
52       AllocatorNode *Next = Head->Next;
53       delete Head;
54       Head = Next;
55     }
56   }
57 
allocUnalignedBuffer(size_t Size)58   char *allocUnalignedBuffer(size_t Size) {
59     assert(Head && Head->Buf);
60 
61     uint8_t *P = Head->Buf + Head->Used;
62 
63     Head->Used += Size;
64     if (Head->Used <= Head->Capacity)
65       return reinterpret_cast<char *>(P);
66 
67     addNode(std::max(AllocUnit, Size));
68     Head->Used = Size;
69     return reinterpret_cast<char *>(Head->Buf);
70   }
71 
allocArray(size_t Count)72   template <typename T, typename... Args> T *allocArray(size_t Count) {
73     size_t Size = Count * sizeof(T);
74     assert(Head && Head->Buf);
75 
76     size_t P = (size_t)Head->Buf + Head->Used;
77     uintptr_t AlignedP =
78         (((size_t)P + alignof(T) - 1) & ~(size_t)(alignof(T) - 1));
79     uint8_t *PP = (uint8_t *)AlignedP;
80     size_t Adjustment = AlignedP - P;
81 
82     Head->Used += Size + Adjustment;
83     if (Head->Used <= Head->Capacity)
84       return new (PP) T[Count]();
85 
86     addNode(std::max(AllocUnit, Size));
87     Head->Used = Size;
88     return new (Head->Buf) T[Count]();
89   }
90 
alloc(Args &&...ConstructorArgs)91   template <typename T, typename... Args> T *alloc(Args &&... ConstructorArgs) {
92     constexpr size_t Size = sizeof(T);
93     assert(Head && Head->Buf);
94 
95     size_t P = (size_t)Head->Buf + Head->Used;
96     uintptr_t AlignedP =
97         (((size_t)P + alignof(T) - 1) & ~(size_t)(alignof(T) - 1));
98     uint8_t *PP = (uint8_t *)AlignedP;
99     size_t Adjustment = AlignedP - P;
100 
101     Head->Used += Size + Adjustment;
102     if (Head->Used <= Head->Capacity)
103       return new (PP) T(std::forward<Args>(ConstructorArgs)...);
104 
105     static_assert(Size < AllocUnit, "");
106     addNode(AllocUnit);
107     Head->Used = Size;
108     return new (Head->Buf) T(std::forward<Args>(ConstructorArgs)...);
109   }
110 
111 private:
112   AllocatorNode *Head = nullptr;
113 };
114 
115 struct BackrefContext {
116   static constexpr size_t Max = 10;
117 
118   TypeNode *FunctionParams[Max];
119   size_t FunctionParamCount = 0;
120 
121   // The first 10 BackReferences in a mangled name can be back-referenced by
122   // special name @[0-9]. This is a storage for the first 10 BackReferences.
123   NamedIdentifierNode *Names[Max];
124   size_t NamesCount = 0;
125 };
126 
127 enum class QualifierMangleMode { Drop, Mangle, Result };
128 
129 enum NameBackrefBehavior : uint8_t {
130   NBB_None = 0,          // don't save any names as backrefs.
131   NBB_Template = 1 << 0, // save template instanations.
132   NBB_Simple = 1 << 1,   // save simple names.
133 };
134 
135 enum class FunctionIdentifierCodeGroup { Basic, Under, DoubleUnder };
136 
137 // Demangler class takes the main role in demangling symbols.
138 // It has a set of functions to parse mangled symbols into Type instances.
139 // It also has a set of functions to convert Type instances to strings.
140 class Demangler {
141 public:
142   Demangler() = default;
143   virtual ~Demangler() = default;
144 
145   // You are supposed to call parse() first and then check if error is true.  If
146   // it is false, call output() to write the formatted name to the given stream.
147   SymbolNode *parse(StringView &MangledName);
148 
149   TagTypeNode *parseTagUniqueName(StringView &MangledName);
150 
151   // True if an error occurred.
152   bool Error = false;
153 
154   void dumpBackReferences();
155 
156 private:
157   SymbolNode *demangleEncodedSymbol(StringView &MangledName,
158                                     QualifiedNameNode *QN);
159   SymbolNode *demangleDeclarator(StringView &MangledName);
160   SymbolNode *demangleMD5Name(StringView &MangledName);
161   SymbolNode *demangleTypeinfoName(StringView &MangledName);
162 
163   VariableSymbolNode *demangleVariableEncoding(StringView &MangledName,
164                                                StorageClass SC);
165   FunctionSymbolNode *demangleFunctionEncoding(StringView &MangledName);
166 
167   Qualifiers demanglePointerExtQualifiers(StringView &MangledName);
168 
169   // Parser functions. This is a recursive-descent parser.
170   TypeNode *demangleType(StringView &MangledName, QualifierMangleMode QMM);
171   PrimitiveTypeNode *demanglePrimitiveType(StringView &MangledName);
172   CustomTypeNode *demangleCustomType(StringView &MangledName);
173   TagTypeNode *demangleClassType(StringView &MangledName);
174   PointerTypeNode *demanglePointerType(StringView &MangledName);
175   PointerTypeNode *demangleMemberPointerType(StringView &MangledName);
176   FunctionSignatureNode *demangleFunctionType(StringView &MangledName,
177                                               bool HasThisQuals);
178 
179   ArrayTypeNode *demangleArrayType(StringView &MangledName);
180 
181   NodeArrayNode *demangleFunctionParameterList(StringView &MangledName,
182                                                bool &IsVariadic);
183   NodeArrayNode *demangleTemplateParameterList(StringView &MangledName);
184 
185   std::pair<uint64_t, bool> demangleNumber(StringView &MangledName);
186   uint64_t demangleUnsigned(StringView &MangledName);
187   int64_t demangleSigned(StringView &MangledName);
188 
189   void memorizeString(StringView s);
190   void memorizeIdentifier(IdentifierNode *Identifier);
191 
192   /// Allocate a copy of \p Borrowed into memory that we own.
193   StringView copyString(StringView Borrowed);
194 
195   QualifiedNameNode *demangleFullyQualifiedTypeName(StringView &MangledName);
196   QualifiedNameNode *demangleFullyQualifiedSymbolName(StringView &MangledName);
197 
198   IdentifierNode *demangleUnqualifiedTypeName(StringView &MangledName,
199                                               bool Memorize);
200   IdentifierNode *demangleUnqualifiedSymbolName(StringView &MangledName,
201                                                 NameBackrefBehavior NBB);
202 
203   QualifiedNameNode *demangleNameScopeChain(StringView &MangledName,
204                                             IdentifierNode *UnqualifiedName);
205   IdentifierNode *demangleNameScopePiece(StringView &MangledName);
206 
207   NamedIdentifierNode *demangleBackRefName(StringView &MangledName);
208   IdentifierNode *demangleTemplateInstantiationName(StringView &MangledName,
209                                                     NameBackrefBehavior NBB);
210   IntrinsicFunctionKind
211   translateIntrinsicFunctionCode(char CH, FunctionIdentifierCodeGroup Group);
212   IdentifierNode *demangleFunctionIdentifierCode(StringView &MangledName);
213   IdentifierNode *
214   demangleFunctionIdentifierCode(StringView &MangledName,
215                                  FunctionIdentifierCodeGroup Group);
216   StructorIdentifierNode *demangleStructorIdentifier(StringView &MangledName,
217                                                      bool IsDestructor);
218   ConversionOperatorIdentifierNode *
219   demangleConversionOperatorIdentifier(StringView &MangledName);
220   LiteralOperatorIdentifierNode *
221   demangleLiteralOperatorIdentifier(StringView &MangledName);
222 
223   SymbolNode *demangleSpecialIntrinsic(StringView &MangledName);
224   SpecialTableSymbolNode *
225   demangleSpecialTableSymbolNode(StringView &MangledName,
226                                  SpecialIntrinsicKind SIK);
227   LocalStaticGuardVariableNode *
228   demangleLocalStaticGuard(StringView &MangledName, bool IsThread);
229   VariableSymbolNode *demangleUntypedVariable(ArenaAllocator &Arena,
230                                               StringView &MangledName,
231                                               StringView VariableName);
232   VariableSymbolNode *
233   demangleRttiBaseClassDescriptorNode(ArenaAllocator &Arena,
234                                       StringView &MangledName);
235   FunctionSymbolNode *demangleInitFiniStub(StringView &MangledName,
236                                            bool IsDestructor);
237 
238   NamedIdentifierNode *demangleSimpleName(StringView &MangledName,
239                                           bool Memorize);
240   NamedIdentifierNode *demangleAnonymousNamespaceName(StringView &MangledName);
241   NamedIdentifierNode *demangleLocallyScopedNamePiece(StringView &MangledName);
242   EncodedStringLiteralNode *demangleStringLiteral(StringView &MangledName);
243   FunctionSymbolNode *demangleVcallThunkNode(StringView &MangledName);
244 
245   StringView demangleSimpleString(StringView &MangledName, bool Memorize);
246 
247   FuncClass demangleFunctionClass(StringView &MangledName);
248   CallingConv demangleCallingConvention(StringView &MangledName);
249   StorageClass demangleVariableStorageClass(StringView &MangledName);
250   bool demangleThrowSpecification(StringView &MangledName);
251   wchar_t demangleWcharLiteral(StringView &MangledName);
252   uint8_t demangleCharLiteral(StringView &MangledName);
253 
254   std::pair<Qualifiers, bool> demangleQualifiers(StringView &MangledName);
255 
256   // Memory allocator.
257   ArenaAllocator Arena;
258 
259   // A single type uses one global back-ref table for all function params.
260   // This means back-refs can even go "into" other types.  Examples:
261   //
262   //  // Second int* is a back-ref to first.
263   //  void foo(int *, int*);
264   //
265   //  // Second int* is not a back-ref to first (first is not a function param).
266   //  int* foo(int*);
267   //
268   //  // Second int* is a back-ref to first (ALL function types share the same
269   //  // back-ref map.
270   //  using F = void(*)(int*);
271   //  F G(int *);
272   BackrefContext Backrefs;
273 };
274 
275 } // namespace ms_demangle
276 } // namespace llvm
277 
278 #endif // LLVM_DEMANGLE_MICROSOFT_DEMANGLE_H
279