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