lib/Support/ItaniumManglingCanonicalizer.cpp

   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::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 }