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_MICROSOFTDEMANGLE_H
10 #define LLVM_DEMANGLE_MICROSOFTDEMANGLE_H
11 
12 #include "llvm/Demangle/MicrosoftDemangleNodes.h"
13 #include "llvm/Demangle/StringView.h"
14 
15 #include <utility>
16 
17 namespace llvm {
18 namespace ms_demangle {
19 // This memory allocator is extremely fast, but it doesn't call dtors
20 // for allocated objects. That means you can't use STL containers
21 // (such as std::vector) with this allocator. But it pays off --
22 // the demangler is 3x faster with this allocator compared to one with
23 // STL containers.
24 constexpr size_t AllocUnit = 4096;
25 
26 class ArenaAllocator {
27   struct AllocatorNode {
28     uint8_t *Buf = nullptr;
29     size_t Used = 0;
30     size_t Capacity = 0;
31     AllocatorNode *Next = nullptr;
32   };
33 
34   void addNode(size_t Capacity) {
35     AllocatorNode *NewHead = new AllocatorNode;
36     NewHead->Buf = new uint8_t[Capacity];
37     NewHead->Next = Head;
38     NewHead->Capacity = Capacity;
39     Head = NewHead;
40     NewHead->Used = 0;
41   }
42 
43 public:
44   ArenaAllocator() { addNode(AllocUnit); }
45 
46   ~ArenaAllocator() {
47     while (Head) {
48       assert(Head->Buf);
49       delete[] Head->Buf;
50       AllocatorNode *Next = Head->Next;
51       delete Head;
52       Head = Next;
53     }
54   }
55 
56   char *allocUnalignedBuffer(size_t Size) {
57     assert(Head && Head->Buf);
58 
59     uint8_t *P = Head->Buf + Head->Used;
60 
61     Head->Used += Size;
62     if (Head->Used <= Head->Capacity)
63       return reinterpret_cast<char *>(P);
64 
65     addNode(std::max(AllocUnit, Size));
66     Head->Used = Size;
67     return reinterpret_cast<char *>(Head->Buf);
68   }
69 
70   template <typename T, typename... Args> T *allocArray(size_t Count) {
71     size_t Size = Count * sizeof(T);
72     assert(Head && Head->Buf);
73 
74     size_t P = (size_t)Head->Buf + Head->Used;
75     uintptr_t AlignedP =
76         (((size_t)P + alignof(T) - 1) & ~(size_t)(alignof(T) - 1));
77     uint8_t *PP = (uint8_t *)AlignedP;
78     size_t Adjustment = AlignedP - P;
79 
80     Head->Used += Size + Adjustment;
81     if (Head->Used <= Head->Capacity)
82       return new (PP) T[Count]();
83 
84     addNode(std::max(AllocUnit, Size));
85     Head->Used = Size;
86     return new (Head->Buf) T[Count]();
87   }
88 
89   template <typename T, typename... Args> T *alloc(Args &&... ConstructorArgs) {
90     constexpr size_t Size = sizeof(T);
91     assert(Head && Head->Buf);
92 
93     size_t P = (size_t)Head->Buf + Head->Used;
94     uintptr_t AlignedP =
95         (((size_t)P + alignof(T) - 1) & ~(size_t)(alignof(T) - 1));
96     uint8_t *PP = (uint8_t *)AlignedP;
97     size_t Adjustment = AlignedP - P;
98 
99     Head->Used += Size + Adjustment;
100     if (Head->Used <= Head->Capacity)
101       return new (PP) T(std::forward<Args>(ConstructorArgs)...);
102 
103     static_assert(Size < AllocUnit);
104     addNode(AllocUnit);
105     Head->Used = Size;
106     return new (Head->Buf) T(std::forward<Args>(ConstructorArgs)...);
107   }
108 
109 private:
110   AllocatorNode *Head = nullptr;
111 };
112 
113 struct BackrefContext {
114   static constexpr size_t Max = 10;
115 
116   TypeNode *FunctionParams[Max];
117   size_t FunctionParamCount = 0;
118 
119   // The first 10 BackReferences in a mangled name can be back-referenced by
120   // special name @[0-9]. This is a storage for the first 10 BackReferences.
121   NamedIdentifierNode *Names[Max];
122   size_t NamesCount = 0;
123 };
124 
125 enum class QualifierMangleMode { Drop, Mangle, Result };
126 
127 enum NameBackrefBehavior : uint8_t {
128   NBB_None = 0,          // don't save any names as backrefs.
129   NBB_Template = 1 << 0, // save template instanations.
130   NBB_Simple = 1 << 1,   // save simple names.
131 };
132 
133 enum class FunctionIdentifierCodeGroup { Basic, Under, DoubleUnder };
134 
135 // Demangler class takes the main role in demangling symbols.
136 // It has a set of functions to parse mangled symbols into Type instances.
137 // It also has a set of functions to convert Type instances to strings.
138 class Demangler {
139 public:
140   Demangler() = default;
141   virtual ~Demangler() = default;
142 
143   // You are supposed to call parse() first and then check if error is true.  If
144   // it is false, call output() to write the formatted name to the given stream.
145   SymbolNode *parse(StringView &MangledName);
146 
147   TagTypeNode *parseTagUniqueName(StringView &MangledName);
148 
149   // True if an error occurred.
150   bool Error = false;
151 
152   void dumpBackReferences();
153 
154 private:
155   SymbolNode *demangleEncodedSymbol(StringView &MangledName,
156                                     QualifiedNameNode *QN);
157   SymbolNode *demangleDeclarator(StringView &MangledName);
158   SymbolNode *demangleMD5Name(StringView &MangledName);
159   SymbolNode *demangleTypeinfoName(StringView &MangledName);
160 
161   VariableSymbolNode *demangleVariableEncoding(StringView &MangledName,
162                                                StorageClass SC);
163   FunctionSymbolNode *demangleFunctionEncoding(StringView &MangledName);
164 
165   Qualifiers demanglePointerExtQualifiers(StringView &MangledName);
166 
167   // Parser functions. This is a recursive-descent parser.
168   TypeNode *demangleType(StringView &MangledName, QualifierMangleMode QMM);
169   PrimitiveTypeNode *demanglePrimitiveType(StringView &MangledName);
170   CustomTypeNode *demangleCustomType(StringView &MangledName);
171   TagTypeNode *demangleClassType(StringView &MangledName);
172   PointerTypeNode *demanglePointerType(StringView &MangledName);
173   PointerTypeNode *demangleMemberPointerType(StringView &MangledName);
174   FunctionSignatureNode *demangleFunctionType(StringView &MangledName,
175                                               bool HasThisQuals);
176 
177   ArrayTypeNode *demangleArrayType(StringView &MangledName);
178 
179   NodeArrayNode *demangleFunctionParameterList(StringView &MangledName,
180                                                bool &IsVariadic);
181   NodeArrayNode *demangleTemplateParameterList(StringView &MangledName);
182 
183   std::pair<uint64_t, bool> demangleNumber(StringView &MangledName);
184   uint64_t demangleUnsigned(StringView &MangledName);
185   int64_t demangleSigned(StringView &MangledName);
186 
187   void memorizeString(StringView s);
188   void memorizeIdentifier(IdentifierNode *Identifier);
189 
190   /// Allocate a copy of \p Borrowed into memory that we own.
191   StringView copyString(StringView Borrowed);
192 
193   QualifiedNameNode *demangleFullyQualifiedTypeName(StringView &MangledName);
194   QualifiedNameNode *demangleFullyQualifiedSymbolName(StringView &MangledName);
195 
196   IdentifierNode *demangleUnqualifiedTypeName(StringView &MangledName,
197                                               bool Memorize);
198   IdentifierNode *demangleUnqualifiedSymbolName(StringView &MangledName,
199                                                 NameBackrefBehavior NBB);
200 
201   QualifiedNameNode *demangleNameScopeChain(StringView &MangledName,
202                                             IdentifierNode *UnqualifiedName);
203   IdentifierNode *demangleNameScopePiece(StringView &MangledName);
204 
205   NamedIdentifierNode *demangleBackRefName(StringView &MangledName);
206   IdentifierNode *demangleTemplateInstantiationName(StringView &MangledName,
207                                                     NameBackrefBehavior NBB);
208   IntrinsicFunctionKind
209   translateIntrinsicFunctionCode(char CH, FunctionIdentifierCodeGroup Group);
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, bool IsThread);
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_MICROSOFTDEMANGLE_H
277