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