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