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