1 //===----------------- ItaniumManglingCanonicalizer.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 #include "llvm/Support/ItaniumManglingCanonicalizer.h"
10 
11 #include "llvm/ADT/FoldingSet.h"
12 #include "llvm/ADT/StringRef.h"
13 #include "llvm/Demangle/ItaniumDemangle.h"
14 #include "llvm/Support/Allocator.h"
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/FoldingSet.h"
18 #include "llvm/ADT/StringRef.h"
19 
20 using namespace llvm;
21 using llvm::itanium_demangle::ForwardTemplateReference;
22 using llvm::itanium_demangle::Node;
23 using llvm::itanium_demangle::NodeKind;
24 using llvm::itanium_demangle::StringView;
25 
26 namespace {
27 struct FoldingSetNodeIDBuilder {
28   llvm::FoldingSetNodeID &ID;
29   void operator()(const Node *P) { ID.AddPointer(P); }
30   void operator()(StringView Str) {
31     ID.AddString(llvm::StringRef(Str.begin(), Str.size()));
32   }
33   template<typename T>
34   typename std::enable_if<std::is_integral<T>::value ||
35                           std::is_enum<T>::value>::type
36   operator()(T V) {
37     ID.AddInteger((unsigned long long)V);
38   }
39   void operator()(itanium_demangle::NodeArray A) {
40     ID.AddInteger(A.size());
41     for (const Node *N : A)
42       (*this)(N);
43   }
44 };
45 
46 template<typename ...T>
47 void profileCtor(llvm::FoldingSetNodeID &ID, Node::Kind K, T ...V) {
48   FoldingSetNodeIDBuilder Builder = {ID};
49   Builder(K);
50   int VisitInOrder[] = {
51     (Builder(V), 0) ...,
52     0 // Avoid empty array if there are no arguments.
53   };
54   (void)VisitInOrder;
55 }
56 
57 // FIXME: Convert this to a generic lambda when possible.
58 template<typename NodeT> struct ProfileSpecificNode {
59   FoldingSetNodeID &ID;
60   template<typename ...T> void operator()(T ...V) {
61     profileCtor(ID, NodeKind<NodeT>::Kind, V...);
62   }
63 };
64 
65 struct ProfileNode {
66   FoldingSetNodeID &ID;
67   template<typename NodeT> void operator()(const NodeT *N) {
68     N->match(ProfileSpecificNode<NodeT>{ID});
69   }
70 };
71 
72 template<> void ProfileNode::operator()(const ForwardTemplateReference *N) {
73   llvm_unreachable("should never canonicalize a ForwardTemplateReference");
74 }
75 
76 void profileNode(llvm::FoldingSetNodeID &ID, const Node *N) {
77   N->visit(ProfileNode{ID});
78 }
79 
80 class FoldingNodeAllocator {
81   class alignas(alignof(Node *)) NodeHeader : public llvm::FoldingSetNode {
82   public:
83     // 'Node' in this context names the injected-class-name of the base class.
84     itanium_demangle::Node *getNode() {
85       return reinterpret_cast<itanium_demangle::Node *>(this + 1);
86     }
87     void Profile(llvm::FoldingSetNodeID &ID) { profileNode(ID, getNode()); }
88   };
89 
90   BumpPtrAllocator RawAlloc;
91   llvm::FoldingSet<NodeHeader> Nodes;
92 
93 public:
94   void reset() {}
95 
96   template <typename T, typename... Args>
97   std::pair<Node *, bool> getOrCreateNode(bool CreateNewNodes, Args &&... As) {
98     // FIXME: Don't canonicalize forward template references for now, because
99     // they contain state (the resolved template node) that's not known at their
100     // point of creation.
101     if (std::is_same<T, ForwardTemplateReference>::value) {
102       // Note that we don't use if-constexpr here and so we must still write
103       // this code in a generic form.
104       return {new (RawAlloc.Allocate(sizeof(T), alignof(T)))
105                   T(std::forward<Args>(As)...),
106               true};
107     }
108 
109     llvm::FoldingSetNodeID ID;
110     profileCtor(ID, NodeKind<T>::Kind, As...);
111 
112     void *InsertPos;
113     if (NodeHeader *Existing = Nodes.FindNodeOrInsertPos(ID, InsertPos))
114       return {static_cast<T*>(Existing->getNode()), false};
115 
116     if (!CreateNewNodes)
117       return {nullptr, true};
118 
119     static_assert(alignof(T) <= alignof(NodeHeader),
120                   "underaligned node header for specific node kind");
121     void *Storage =
122         RawAlloc.Allocate(sizeof(NodeHeader) + sizeof(T), alignof(NodeHeader));
123     NodeHeader *New = new (Storage) NodeHeader;
124     T *Result = new (New->getNode()) T(std::forward<Args>(As)...);
125     Nodes.InsertNode(New, InsertPos);
126     return {Result, true};
127   }
128 
129   template<typename T, typename... Args>
130   Node *makeNode(Args &&...As) {
131     return getOrCreateNode<T>(true, std::forward<Args>(As)...).first;
132   }
133 
134   void *allocateNodeArray(size_t sz) {
135     return RawAlloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
136   }
137 };
138 
139 class CanonicalizerAllocator : public FoldingNodeAllocator {
140   Node *MostRecentlyCreated = nullptr;
141   Node *TrackedNode = nullptr;
142   bool TrackedNodeIsUsed = false;
143   bool CreateNewNodes = true;
144   llvm::SmallDenseMap<Node*, Node*, 32> Remappings;
145 
146   template<typename T, typename ...Args> Node *makeNodeSimple(Args &&...As) {
147     std::pair<Node *, bool> Result =
148         getOrCreateNode<T>(CreateNewNodes, std::forward<Args>(As)...);
149     if (Result.second) {
150       // Node is new. Make a note of that.
151       MostRecentlyCreated = Result.first;
152     } else if (Result.first) {
153       // Node is pre-existing; check if it's in our remapping table.
154       if (auto *N = Remappings.lookup(Result.first)) {
155         Result.first = N;
156         assert(Remappings.find(Result.first) == Remappings.end() &&
157                "should never need multiple remap steps");
158       }
159       if (Result.first == TrackedNode)
160         TrackedNodeIsUsed = true;
161     }
162     return Result.first;
163   }
164 
165   /// Helper to allow makeNode to be partially-specialized on T.
166   template<typename T> struct MakeNodeImpl {
167     CanonicalizerAllocator &Self;
168     template<typename ...Args> Node *make(Args &&...As) {
169       return Self.makeNodeSimple<T>(std::forward<Args>(As)...);
170     }
171   };
172 
173 public:
174   template<typename T, typename ...Args> Node *makeNode(Args &&...As) {
175     return MakeNodeImpl<T>{*this}.make(std::forward<Args>(As)...);
176   }
177 
178   void reset() { MostRecentlyCreated = nullptr; }
179 
180   void setCreateNewNodes(bool CNN) { CreateNewNodes = CNN; }
181 
182   void addRemapping(Node *A, Node *B) {
183     // Note, we don't need to check whether B is also remapped, because if it
184     // was we would have already remapped it when building it.
185     Remappings.insert(std::make_pair(A, B));
186   }
187 
188   bool isMostRecentlyCreated(Node *N) const { return MostRecentlyCreated == N; }
189 
190   void trackUsesOf(Node *N) {
191     TrackedNode = N;
192     TrackedNodeIsUsed = false;
193   }
194   bool trackedNodeIsUsed() const { return TrackedNodeIsUsed; }
195 };
196 
197 /// Convert St3foo to NSt3fooE so that equivalences naming one also affect the
198 /// other.
199 template<>
200 struct CanonicalizerAllocator::MakeNodeImpl<
201            itanium_demangle::StdQualifiedName> {
202   CanonicalizerAllocator &Self;
203   Node *make(Node *Child) {
204     Node *StdNamespace = Self.makeNode<itanium_demangle::NameType>("std");
205     if (!StdNamespace)
206       return nullptr;
207     return Self.makeNode<itanium_demangle::NestedName>(StdNamespace, Child);
208   }
209 };
210 
211 // FIXME: Also expand built-in substitutions?
212 
213 using CanonicalizingDemangler =
214     itanium_demangle::ManglingParser<CanonicalizerAllocator>;
215 }
216 
217 struct ItaniumManglingCanonicalizer::Impl {
218   CanonicalizingDemangler Demangler = {nullptr, nullptr};
219 };
220 
221 ItaniumManglingCanonicalizer::ItaniumManglingCanonicalizer() : P(new Impl) {}
222 ItaniumManglingCanonicalizer::~ItaniumManglingCanonicalizer() { delete P; }
223 
224 ItaniumManglingCanonicalizer::EquivalenceError
225 ItaniumManglingCanonicalizer::addEquivalence(FragmentKind Kind, StringRef First,
226                                              StringRef Second) {
227   auto &Alloc = P->Demangler.ASTAllocator;
228   Alloc.setCreateNewNodes(true);
229 
230   auto Parse = [&](StringRef Str) {
231     P->Demangler.reset(Str.begin(), Str.end());
232     Node *N = nullptr;
233     switch (Kind) {
234       // A <name>, with minor extensions to allow arbitrary namespace and
235       // template names that can't easily be written as <name>s.
236     case FragmentKind::Name:
237       // Very special case: allow "St" as a shorthand for "3std". It's not
238       // valid as a <name> mangling, but is nonetheless the most natural
239       // way to name the 'std' namespace.
240       if (Str.size() == 2 && P->Demangler.consumeIf("St"))
241         N = P->Demangler.make<itanium_demangle::NameType>("std");
242       // We permit substitutions to name templates without their template
243       // arguments. This mostly just falls out, as almost all template names
244       // are valid as <name>s, but we also want to parse <substitution>s as
245       // <name>s, even though they're not.
246       else if (Str.startswith("S"))
247         // Parse the substitution and optional following template arguments.
248         N = P->Demangler.parseType();
249       else
250         N = P->Demangler.parseName();
251       break;
252 
253       // A <type>.
254     case FragmentKind::Type:
255       N = P->Demangler.parseType();
256       break;
257 
258       // An <encoding>.
259     case FragmentKind::Encoding:
260       N = P->Demangler.parseEncoding();
261       break;
262     }
263 
264     // If we have trailing junk, the mangling is invalid.
265     if (P->Demangler.numLeft() != 0)
266       N = nullptr;
267 
268     // If any node was created after N, then we cannot safely remap it because
269     // it might already be in use by another node.
270     return std::make_pair(N, Alloc.isMostRecentlyCreated(N));
271   };
272 
273   Node *FirstNode, *SecondNode;
274   bool FirstIsNew, SecondIsNew;
275 
276   std::tie(FirstNode, FirstIsNew) = Parse(First);
277   if (!FirstNode)
278     return EquivalenceError::InvalidFirstMangling;
279 
280   Alloc.trackUsesOf(FirstNode);
281   std::tie(SecondNode, SecondIsNew) = Parse(Second);
282   if (!SecondNode)
283     return EquivalenceError::InvalidSecondMangling;
284 
285   // If they're already equivalent, there's nothing to do.
286   if (FirstNode == SecondNode)
287     return EquivalenceError::Success;
288 
289   if (FirstIsNew && !Alloc.trackedNodeIsUsed())
290     Alloc.addRemapping(FirstNode, SecondNode);
291   else if (SecondIsNew)
292     Alloc.addRemapping(SecondNode, FirstNode);
293   else
294     return EquivalenceError::ManglingAlreadyUsed;
295 
296   return EquivalenceError::Success;
297 }
298 
299 static ItaniumManglingCanonicalizer::Key
300 parseMaybeMangledName(CanonicalizingDemangler &Demangler, StringRef Mangling,
301                       bool CreateNewNodes) {
302   Demangler.ASTAllocator.setCreateNewNodes(CreateNewNodes);
303   Demangler.reset(Mangling.begin(), Mangling.end());
304   // Attempt demangling only for names that look like C++ mangled names.
305   // Otherwise, treat them as extern "C" names. We permit the latter to
306   // be remapped by (eg)
307   //   encoding 6memcpy 7memmove
308   // consistent with how they are encoded as local-names inside a C++ mangling.
309   Node *N;
310   if (Mangling.startswith("_Z") || Mangling.startswith("__Z") ||
311       Mangling.startswith("___Z") || Mangling.startswith("____Z"))
312     N = Demangler.parse();
313   else
314     N = Demangler.make<itanium_demangle::NameType>(
315         StringView(Mangling.data(), Mangling.size()));
316   return reinterpret_cast<ItaniumManglingCanonicalizer::Key>(N);
317 }
318 
319 ItaniumManglingCanonicalizer::Key
320 ItaniumManglingCanonicalizer::canonicalize(StringRef Mangling) {
321   return parseMaybeMangledName(P->Demangler, Mangling, true);
322 }
323 
324 ItaniumManglingCanonicalizer::Key
325 ItaniumManglingCanonicalizer::lookup(StringRef Mangling) {
326   return parseMaybeMangledName(P->Demangler, Mangling, false);
327 }
328