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