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