[llvm] lldb abi_tag support 1/3 - Add equality comparison API to itanium_demangle::Node

[Michael137]

Summary

In LLDB we currently rely on hand-parsing demangled function
prototypes when selecting a candidate symbol for expression evaluation.
We now plan to use the Itanium mangle tree API to compare function
encodings instead.

This patch adds the ability to compare nodes of the Itanium mangle tree.

Testing

• Added unit-tests for each Node's new operator==

[Michael137]

• Fixed PointerToMemberType::operator==

[Michael137]

• Add necessary null-checks

[Michael137]

Planning to add unit-tests once we are fine with the approach in https://reviews.llvm.org/D131335

[Michael137]

• Rebase

[Michael137]

• Fix NodeArray::operator==()
• Fix FunctionEncoding::operator==()
• Start adding operator!=()

[Michael137]

• Start adding unit-tests

[Michael137]

• Remove debug logging

[Michael137]

Still WIP, but general approach is there. Before I add more unit-tests (i.e., around 75 test-cases, one for each Node type), are people ok with the general implementation/testing strategy?

[Michael137]

• Remove mistakenly added header

[Michael137]

• Reword commit message

[Michael137]

• Add more tests

[Michael137]

• Start adding asserts to operator==

[Michael137]

• Add more tests

[ldionne]

Once you use the libcxxabi sources as a base, the libcxxabi review group should kick in and our CI should get triggered.

llvm/include/llvm/Demangle/ItaniumDemangle.h

233 ↗

(On Diff #451086)

I think I don't understand why there is both operator== and equals. Do we really need both?

Instead, you could consider defining a virtual bool equals(Node const* Root) const = 0; and override it in subclasses, which seems to be a bit more in-line with what's done elsewhere in this file (e.g. printRight). Thoughts? It does mean that all overrides are going to have to check that Root->Kind == this->Kind, but that may be acceptable.

372 ↗

(On Diff #451086)

If you keep defining operator== after my comment above, I feel like all classes that get an operator== should also get an operator!= defined with the usual !(a == b).

435–440 ↗

(On Diff #451086)

Just a suggestion, non-blocking. I find that clearer but it may just be preference.

llvm/unittests/Demangle/ItaniumDemangleTestUtils.h

2

I suspect cp_to_llvm.sh will have to be updated to know about this new file.

[Michael137]

llvm/include/llvm/Demangle/ItaniumDemangle.h

233 ↗

(On Diff #451086)

That's a reasonable alternative. It does give us some more flexibility in comparing concrete vs. abstract nodes. With my implementation we'd have to cast a concrete node back to Node* to compare for equality which isn't very ergonomic.

372 ↗

(On Diff #451086)

Will do

435–440 ↗

(On Diff #451086)

I find your approach more readable :)
will do that instead, thanks

[Michael137]

llvm/unittests/Demangle/ItaniumDemangleTestUtils.h

2

It looks like the unit tests are exclusively in llvm/? I'll keep the tests in this directory for now

[Michael137]

• Move changes to libcxxabi/
• Add operator!=()

[Michael137]

• Remove redundant accessors

[Michael137]

• Sync

libcxxabi/src/cxa_demangle.cpp

if (*first == '_') {
         ;
       if (t1 == last)
         first = last;
     }
   }
   return first;
 }
 
+bool itanium_demangle::Node::equals(Node const* Other) const {
+  assert(Other != nullptr);
+
+  if (K != Other->getKind())
+    return false;
+
+  switch (K) {
+#define NODE(X)                                                                                                        \
+  case K##X:                                                                                                           \
+    return *static_cast<const X*>(this) == *static_cast<const X*>(Other);
+#include "demangle/ItaniumNodes.def"
+  }
+  assert(0 && "unknown mangling node kind");
+}
+
 #ifndef NDEBUG
 namespace {
 struct DumpVisitor {
   unsigned Depth = 0;
   bool PendingNewline = false;
 
   template<typename NodeT> static constexpr bool wantsNewline(const NodeT *) {
     return true;

libcxxabi/src/demangle/ItaniumDemangle.h

public:
   Node(Kind K_, Cache RHSComponentCache_, Cache ArrayCache_ = Cache::No,
        Cache FunctionCache_ = Cache::No)
       : Node(K_, Prec::Primary, RHSComponentCache_, ArrayCache_,
              FunctionCache_) {}
 
   /// Visit the most-derived object corresponding to this object.
   template<typename Fn> void visit(Fn F) const;
 
+  /// Returns true if the tree rooted at this node is equivalent to
+  /// the tree rooted at the specified 'Root' node.
+  ///
+  /// Equivalence of two nodes N1 and N2 is defined as:
+  /// 1. N1.getKind() == N2.getKind()
+  /// 2. N1 == N2 where '==' is defined by the
+  ///    kind of N1 and N2.
+  ///
+  /// Behaviour is undefined if 'Root == nullptr'.
+  bool equals(Node const *Root) const;
+
   // The following function is provided by all derived classes:
   //
   // Call F with arguments that, when passed to the constructor of this node,
   // would construct an equivalent node.
   //template<typename Fn> void match(Fn F) const;
 
   bool hasRHSComponent(OutputBuffer &OB) const {
     if (RHSComponentCache != Cache::Unknown)
for (size_t Idx = 0; Idx != NumElements; ++Idx) {
       if (AfterComma == OB.getCurrentPosition()) {
         OB.setCurrentPosition(BeforeComma);
         continue;
       }
 
       FirstElement = false;
     }
   }
+
+  friend bool operator==(NodeArray const &LHS, NodeArray const &RHS) {
+    if (LHS.size() != RHS.size())
+      return false;
+
+    auto **IT1 = LHS.begin();
+    auto **IT2 = RHS.begin();
+    for (; IT1 != LHS.end(); ++IT1, ++IT2)
+      if (!(*IT1)->equals(*IT2))
+        return false;
+
+    return true;
+  }
+
+  friend bool operator!=(NodeArray const &LHS, NodeArray const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct NodeArrayNode : Node {
   NodeArray Array;
   NodeArrayNode(NodeArray Array_) : Node(KNodeArrayNode), Array(Array_) {}
 
   template<typename Fn> void match(Fn F) const { F(Array); }
 
   void printLeft(OutputBuffer &OB) const override { Array.printWithComma(OB); }
+
+  friend bool operator==(NodeArrayNode const &LHS, NodeArrayNode const &RHS) {
+    return LHS.Array == RHS.Array;
+  }
+
+  friend bool operator!=(NodeArrayNode const &LHS, NodeArrayNode const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class DotSuffix final : public Node {
   const Node *Prefix;
   const StringView Suffix;
 
 public:
   DotSuffix(const Node *Prefix_, StringView Suffix_)
       : Node(KDotSuffix), Prefix(Prefix_), Suffix(Suffix_) {}
 
   template<typename Fn> void match(Fn F) const { F(Prefix, Suffix); }
 
   void printLeft(OutputBuffer &OB) const override {
     Prefix->print(OB);
     OB += " (";
     OB += Suffix;
     OB += ")";
   }
+
+  friend bool operator==(DotSuffix const &LHS, DotSuffix const &RHS) {
+    assert(LHS.Prefix != nullptr);
+    assert(RHS.Prefix != nullptr);
+
+    return LHS.Suffix == RHS.Suffix && LHS.Prefix->equals(RHS.Prefix);
+  }
+
+  friend bool operator!=(DotSuffix const &LHS, DotSuffix const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class VendorExtQualType final : public Node {
   const Node *Ty;
   StringView Ext;
   const Node *TA;
 
 public:
   VendorExtQualType(const Node *Ty_, StringView Ext_, const Node *TA_)
       : Node(KVendorExtQualType), Ty(Ty_), Ext(Ext_), TA(TA_) {}
 
   template <typename Fn> void match(Fn F) const { F(Ty, Ext, TA); }
 
   void printLeft(OutputBuffer &OB) const override {
     Ty->print(OB);
     OB += " ";
     OB += Ext;
     if (TA != nullptr)
       TA->print(OB);
   }
+
+  friend bool operator==(VendorExtQualType const &LHS,
+                         VendorExtQualType const &RHS) {
+    assert(LHS.Ty != nullptr);
+    assert(RHS.Ty != nullptr);
+
+    if (!(LHS.Ext == RHS.Ext))
+      return false;
+
+    if (!LHS.Ty->equals(RHS.Ty))
+      return false;
+
+    if (LHS.TA != nullptr && RHS.TA != nullptr)
+      return LHS.TA->equals(RHS.TA);
+
+    return LHS.TA == nullptr && RHS.TA == nullptr;
+  }
+
+  friend bool operator!=(VendorExtQualType const &LHS,
+                         VendorExtQualType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 enum FunctionRefQual : unsigned char {
   FrefQualNone,
   FrefQualLValue,
   FrefQualRValue,
 };
 
public:
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Child->printLeft(OB);
     printQuals(OB);
   }
 
   void printRight(OutputBuffer &OB) const override { Child->printRight(OB); }
+
+  friend bool operator==(QualType const &LHS, QualType const &RHS) {
+    assert(LHS.Child != nullptr);
+    assert(RHS.Child != nullptr);
+
+    return LHS.Quals == RHS.Quals && LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(QualType const &LHS, QualType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ConversionOperatorType final : public Node {
   const Node *Ty;
 
 public:
   ConversionOperatorType(const Node *Ty_)
       : Node(KConversionOperatorType), Ty(Ty_) {}
 
   template<typename Fn> void match(Fn F) const { F(Ty); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "operator ";
     Ty->print(OB);
   }
+
+  friend bool operator==(ConversionOperatorType const &LHS,
+                         ConversionOperatorType const &RHS) {
+    return LHS.Ty->equals(RHS.Ty);
+  }
+
+  friend bool operator!=(ConversionOperatorType const &LHS,
+                         ConversionOperatorType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PostfixQualifiedType final : public Node {
   const Node *Ty;
   const StringView Postfix;
 
 public:
   PostfixQualifiedType(const Node *Ty_, StringView Postfix_)
       : Node(KPostfixQualifiedType), Ty(Ty_), Postfix(Postfix_) {}
 
   template<typename Fn> void match(Fn F) const { F(Ty, Postfix); }
 
   void printLeft(OutputBuffer &OB) const override {
     Ty->printLeft(OB);
     OB += Postfix;
   }
+
+  friend bool operator==(PostfixQualifiedType const &LHS,
+                         PostfixQualifiedType const &RHS) {
+    return LHS.Postfix == RHS.Postfix && LHS.Ty->equals(RHS.Ty);
+  }
+
+  friend bool operator!=(PostfixQualifiedType const &LHS,
+                         PostfixQualifiedType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class NameType final : public Node {
   const StringView Name;
 
 public:
   NameType(StringView Name_) : Node(KNameType), Name(Name_) {}
 
   template<typename Fn> void match(Fn F) const { F(Name); }
 
   StringView getName() const { return Name; }
   StringView getBaseName() const override { return Name; }
 
   void printLeft(OutputBuffer &OB) const override { OB += Name; }
+
+  friend bool operator==(NameType const &LHS, NameType const &RHS) {
+    return LHS.Name == RHS.Name;
+  }
+
+  friend bool operator!=(NameType const &LHS, NameType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class BitIntType final : public Node {
   const Node *Size;
   bool Signed;
 
 public:
   BitIntType(const Node *Size_, bool Signed_)
       : Node(KBitIntType), Size(Size_), Signed(Signed_) {}
 
   template <typename Fn> void match(Fn F) const { F(Size, Signed); }
 
   void printLeft(OutputBuffer &OB) const override {
     if (!Signed)
       OB += "unsigned ";
     OB += "_BitInt";
     OB.printOpen();
     Size->printAsOperand(OB);
     OB.printClose();
   }
+
+  friend bool operator==(BitIntType const &LHS, BitIntType const &RHS) {
+    return LHS.Signed == RHS.Signed && LHS.Size->equals(RHS.Size);
+  }
+
+  friend bool operator!=(BitIntType const &LHS, BitIntType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ElaboratedTypeSpefType : public Node {
   StringView Kind;
   Node *Child;
 public:
   ElaboratedTypeSpefType(StringView Kind_, Node *Child_)
       : Node(KElaboratedTypeSpefType), Kind(Kind_), Child(Child_) {}
 
   template<typename Fn> void match(Fn F) const { F(Kind, Child); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += Kind;
     OB += ' ';
     Child->print(OB);
   }
+
+  friend bool operator==(ElaboratedTypeSpefType const &LHS,
+                         ElaboratedTypeSpefType const &RHS) {
+    return LHS.Kind == RHS.Kind && LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(ElaboratedTypeSpefType const &LHS,
+                         ElaboratedTypeSpefType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct AbiTagAttr : Node {
   Node *Base;
   StringView Tag;
 
   AbiTagAttr(Node* Base_, StringView Tag_)
       : Node(KAbiTagAttr, Base_->RHSComponentCache,
              Base_->ArrayCache, Base_->FunctionCache),
         Base(Base_), Tag(Tag_) {}
 
   template<typename Fn> void match(Fn F) const { F(Base, Tag); }
 
   void printLeft(OutputBuffer &OB) const override {
     Base->printLeft(OB);
     OB += "[abi:";
     OB += Tag;
     OB += "]";
   }
+
+  friend bool operator==(AbiTagAttr const &LHS, AbiTagAttr const &RHS) {
+    return LHS.Tag == RHS.Tag && LHS.Base->equals(RHS.Base);
+  }
+
+  friend bool operator!=(AbiTagAttr const &LHS, AbiTagAttr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class EnableIfAttr : public Node {
   NodeArray Conditions;
 public:
   EnableIfAttr(NodeArray Conditions_)
       : Node(KEnableIfAttr), Conditions(Conditions_) {}
 
   template<typename Fn> void match(Fn F) const { F(Conditions); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += " [enable_if:";
     Conditions.printWithComma(OB);
     OB += ']';
   }
+
+  friend bool operator==(EnableIfAttr const &LHS, EnableIfAttr const &RHS) {
+    return LHS.Conditions == RHS.Conditions;
+  }
+
+  friend bool operator!=(EnableIfAttr const &LHS, EnableIfAttr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ObjCProtoName : public Node {
   const Node *Ty;
   StringView Protocol;
 
   friend class PointerType;
 
public:
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Ty->print(OB);
     OB += "<";
     OB += Protocol;
     OB += ">";
   }
+
+  friend bool operator==(ObjCProtoName const &LHS, ObjCProtoName const &RHS) {
+    return LHS.Protocol == RHS.Protocol && LHS.Ty->equals(RHS.Ty);
+  }
+
+  friend bool operator!=(ObjCProtoName const &LHS, ObjCProtoName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PointerType final : public Node {
   const Node *Pointee;
 
 public:
   PointerType(const Node *Pointee_)
       : Node(KPointerType, Pointee_->RHSComponentCache),
public:
   void printRight(OutputBuffer &OB) const override {
     if (Pointee->getKind() != KObjCProtoName ||
         !static_cast<const ObjCProtoName *>(Pointee)->isObjCObject()) {
       if (Pointee->hasArray(OB) || Pointee->hasFunction(OB))
         OB += ")";
       Pointee->printRight(OB);
     }
   }
+
+  friend bool operator==(PointerType const &LHS, PointerType const &RHS) {
+    return LHS.Pointee->equals(RHS.Pointee);
+  }
+
+  friend bool operator!=(PointerType const &LHS, PointerType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 enum class ReferenceKind {
   LValue,
   RValue,
 };
 
 // Represents either a LValue or an RValue reference type.
void printRight(OutputBuffer &OB) const override {
     ScopedOverride<bool> SavePrinting(Printing, true);
     std::pair<ReferenceKind, const Node *> Collapsed = collapse(OB);
     if (!Collapsed.second)
       return;
     if (Collapsed.second->hasArray(OB) || Collapsed.second->hasFunction(OB))
       OB += ")";
     Collapsed.second->printRight(OB);
   }
+
+  friend bool operator==(ReferenceType const &LHS, ReferenceType const &RHS) {
+    return LHS.RK == RHS.RK && LHS.Pointee->equals(RHS.Pointee);
+  }
+
+  friend bool operator!=(ReferenceType const &LHS, ReferenceType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PointerToMemberType final : public Node {
   const Node *ClassType;
   const Node *MemberType;
 
 public:
   PointerToMemberType(const Node *ClassType_, const Node *MemberType_)
void printLeft(OutputBuffer &OB) const override {
     OB += "::*";
   }
 
   void printRight(OutputBuffer &OB) const override {
     if (MemberType->hasArray(OB) || MemberType->hasFunction(OB))
       OB += ")";
     MemberType->printRight(OB);
   }
+
+  friend bool operator==(PointerToMemberType const &LHS,
+                         PointerToMemberType const &RHS) {
+    return LHS.ClassType->equals(RHS.ClassType) &&
+           LHS.MemberType->equals(RHS.MemberType);
+  }
+
+  friend bool operator!=(PointerToMemberType const &LHS,
+                         PointerToMemberType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ArrayType final : public Node {
   const Node *Base;
   Node *Dimension;
 
 public:
   ArrayType(const Node *Base_, Node *Dimension_)
void printRight(OutputBuffer &OB) const override {
     if (OB.back() != ']')
       OB += " ";
     OB += "[";
     if (Dimension)
       Dimension->print(OB);
     OB += "]";
     Base->printRight(OB);
   }
+
+  friend bool operator==(ArrayType const &LHS, ArrayType const &RHS) {
+    return LHS.Base->equals(RHS.Base) && LHS.Dimension->equals(RHS.Dimension);
+  }
+
+  friend bool operator!=(ArrayType const &LHS, ArrayType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class FunctionType final : public Node {
   const Node *Ret;
   NodeArray Params;
   Qualifiers CVQuals;
   FunctionRefQual RefQual;
   const Node *ExceptionSpec;
void printRight(OutputBuffer &OB) const override {
     else if (RefQual == FrefQualRValue)
       OB += " &&";
 
     if (ExceptionSpec != nullptr) {
       OB += ' ';
       ExceptionSpec->print(OB);
     }
   }
+
+  friend bool operator==(FunctionType const &LHS, FunctionType const &RHS) {
+    return LHS.CVQuals == RHS.CVQuals && LHS.RefQual == RHS.RefQual &&
+           LHS.Params == RHS.Params && LHS.Ret->equals(RHS.Ret) &&
+           LHS.ExceptionSpec->equals(RHS.ExceptionSpec);
+  }
+
+  friend bool operator!=(FunctionType const &LHS, FunctionType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class NoexceptSpec : public Node {
   const Node *E;
 public:
   NoexceptSpec(const Node *E_) : Node(KNoexceptSpec), E(E_) {}
 
   template<typename Fn> void match(Fn F) const { F(E); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "noexcept";
     OB.printOpen();
     E->printAsOperand(OB);
     OB.printClose();
   }
+
+  friend bool operator==(NoexceptSpec const &LHS, NoexceptSpec const &RHS) {
+    return LHS.E->equals(RHS.E);
+  }
+
+  friend bool operator!=(NoexceptSpec const &LHS, NoexceptSpec const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class DynamicExceptionSpec : public Node {
   NodeArray Types;
 public:
   DynamicExceptionSpec(NodeArray Types_)
       : Node(KDynamicExceptionSpec), Types(Types_) {}
 
   template<typename Fn> void match(Fn F) const { F(Types); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "throw";
     OB.printOpen();
     Types.printWithComma(OB);
     OB.printClose();
   }
+
+  friend bool operator==(DynamicExceptionSpec const &LHS,
+                         DynamicExceptionSpec const &RHS) {
+    return LHS.Types == RHS.Types;
+  }
+
+  friend bool operator!=(DynamicExceptionSpec const &LHS,
+                         DynamicExceptionSpec const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class FunctionEncoding final : public Node {
   const Node *Ret;
   const Node *Name;
   NodeArray Params;
   const Node *Attrs;
   Qualifiers CVQuals;
void printRight(OutputBuffer &OB) const override {
     if (RefQual == FrefQualLValue)
       OB += " &";
     else if (RefQual == FrefQualRValue)
       OB += " &&";
 
     if (Attrs != nullptr)
       Attrs->print(OB);
   }
+
+  friend bool operator==(FunctionEncoding const &LHS,
+                         FunctionEncoding const &RHS) {
+    assert(LHS.Name != nullptr);
+    assert(RHS.Name != nullptr);
+
+    if (LHS.CVQuals != RHS.CVQuals)
+      return false;
+
+    if (LHS.RefQual != RHS.RefQual)
+      return false;
+
+    if (!LHS.Name->equals(RHS.Name))
+      return false;
+
+    if (!!LHS.Ret != !!RHS.Ret)
+      return false;
+
+    if (LHS.Ret)
+      if (!LHS.Ret->equals(RHS.Ret))
+        return false;
+
+    if (!!LHS.Attrs != !!RHS.Attrs)
+      return false;
+
+    if (LHS.Attrs)
+      if (!LHS.Attrs->equals(RHS.Attrs))
+        return false;
+
+    return LHS.Params == RHS.Params;
+  }
+
+  friend bool operator!=(FunctionEncoding const &LHS,
+                         FunctionEncoding const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class LiteralOperator : public Node {
   const Node *OpName;
 
 public:
   LiteralOperator(const Node *OpName_)
       : Node(KLiteralOperator), OpName(OpName_) {}
 
   template<typename Fn> void match(Fn F) const { F(OpName); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "operator\"\" ";
     OpName->print(OB);
   }
+
+  friend bool operator==(LiteralOperator const &LHS,
+                         LiteralOperator const &RHS) {
+    assert(LHS.OpName != nullptr);
+    assert(RHS.OpName != nullptr);
+
+    return LHS.OpName->equals(RHS.OpName);
+  }
+
+  friend bool operator!=(LiteralOperator const &LHS,
+                         LiteralOperator const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class SpecialName final : public Node {
   const StringView Special;
   const Node *Child;
 
 public:
   SpecialName(StringView Special_, const Node *Child_)
       : Node(KSpecialName), Special(Special_), Child(Child_) {}
 
   template<typename Fn> void match(Fn F) const { F(Special, Child); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += Special;
     Child->print(OB);
   }
+
+  friend bool operator==(SpecialName const &LHS, SpecialName const &RHS) {
+    assert(LHS.Child != nullptr);
+    assert(RHS.Child != nullptr);
+
+    return LHS.Special == RHS.Special && LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(SpecialName const &LHS, SpecialName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class CtorVtableSpecialName final : public Node {
   const Node *FirstType;
   const Node *SecondType;
 
 public:
   CtorVtableSpecialName(const Node *FirstType_, const Node *SecondType_)
       : Node(KCtorVtableSpecialName),
         FirstType(FirstType_), SecondType(SecondType_) {}
 
   template<typename Fn> void match(Fn F) const { F(FirstType, SecondType); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "construction vtable for ";
     FirstType->print(OB);
     OB += "-in-";
     SecondType->print(OB);
   }
+
+  friend bool operator==(CtorVtableSpecialName const &LHS,
+                         CtorVtableSpecialName const &RHS) {
+    assert(LHS.FirstType != nullptr);
+    assert(RHS.FirstType != nullptr);
+
+    assert(LHS.SecondType != nullptr);
+    assert(RHS.SecondType != nullptr);
+
+    return LHS.FirstType->equals(RHS.FirstType) &&
+           LHS.SecondType->equals(RHS.SecondType);
+  }
+
+  friend bool operator!=(CtorVtableSpecialName const &LHS,
+                         CtorVtableSpecialName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct NestedName : Node {
   Node *Qual;
   Node *Name;
 
   NestedName(Node *Qual_, Node *Name_)
       : Node(KNestedName), Qual(Qual_), Name(Name_) {}
 
   template<typename Fn> void match(Fn F) const { F(Qual, Name); }
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputBuffer &OB) const override {
     Qual->print(OB);
     OB += "::";
     Name->print(OB);
   }
+
+  friend bool operator==(NestedName const &LHS, NestedName const &RHS) {
+    assert(LHS.Qual != nullptr);
+    assert(RHS.Qual != nullptr);
+
+    assert(LHS.Name != nullptr);
+    assert(RHS.Name != nullptr);
+
+    return LHS.Qual->equals(RHS.Qual) && LHS.Name->equals(RHS.Name);
+  }
+
+  friend bool operator!=(NestedName const &LHS, NestedName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct ModuleName : Node {
   ModuleName *Parent;
   Node *Name;
   bool IsPartition;
 
   ModuleName(ModuleName *Parent_, Node *Name_, bool IsPartition_ = false)
       : Node(KModuleName), Parent(Parent_), Name(Name_),
         IsPartition(IsPartition_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Parent, Name, IsPartition);
   }
 
   void printLeft(OutputBuffer &OB) const override {
     if (Parent)
       Parent->print(OB);
     if (Parent || IsPartition)
       OB += IsPartition ? ':' : '.';
     Name->print(OB);
   }
+
+  friend bool operator==(ModuleName const &LHS, ModuleName const &RHS) {
+    assert(LHS.Name != nullptr);
+    assert(RHS.Name != nullptr);
+
+    if (LHS.IsPartition != RHS.IsPartition)
+      return false;
+
+    if (!!LHS.Parent != !!RHS.Parent)
+      return false;
+
+    if (LHS.Parent)
+      if (!LHS.Parent->equals(RHS.Parent))
+        return false;
+
+    return LHS.Name->equals(RHS.Name);
+  }
+
+  friend bool operator!=(ModuleName const &LHS, ModuleName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct ModuleEntity : Node {
   ModuleName *Module;
   Node *Name;
 
   ModuleEntity(ModuleName *Module_, Node *Name_)
       : Node(KModuleEntity), Module(Module_), Name(Name_) {}
 
   template <typename Fn> void match(Fn F) const { F(Module, Name); }
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputBuffer &OB) const override {
     Name->print(OB);
     OB += '@';
     Module->print(OB);
   }
+
+  friend bool operator==(ModuleEntity const &LHS, ModuleEntity const &RHS) {
+    return LHS.Module->equals(RHS.Module) && LHS.Name->equals(RHS.Name);
+  }
+
+  friend bool operator!=(ModuleEntity const &LHS, ModuleEntity const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct LocalName : Node {
   Node *Encoding;
   Node *Entity;
 
   LocalName(Node *Encoding_, Node *Entity_)
       : Node(KLocalName), Encoding(Encoding_), Entity(Entity_) {}
 
   template<typename Fn> void match(Fn F) const { F(Encoding, Entity); }
 
   void printLeft(OutputBuffer &OB) const override {
     Encoding->print(OB);
     OB += "::";
     Entity->print(OB);
   }
+
+  friend bool operator==(LocalName const &LHS, LocalName const &RHS) {
+    assert(LHS.Encoding != nullptr);
+    assert(RHS.Encoding != nullptr);
+
+    assert(LHS.Entity != nullptr);
+    assert(RHS.Entity != nullptr);
+
+    return LHS.Encoding->equals(RHS.Encoding) && LHS.Entity->equals(RHS.Entity);
+  }
+
+  friend bool operator!=(LocalName const &LHS, LocalName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class QualifiedName final : public Node {
   // qualifier::name
   const Node *Qualifier;
   const Node *Name;
 
 public:
   QualifiedName(const Node *Qualifier_, const Node *Name_)
       : Node(KQualifiedName), Qualifier(Qualifier_), Name(Name_) {}
 
   template<typename Fn> void match(Fn F) const { F(Qualifier, Name); }
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputBuffer &OB) const override {
     Qualifier->print(OB);
     OB += "::";
     Name->print(OB);
   }
+
+  friend bool operator==(QualifiedName const &LHS, QualifiedName const &RHS) {
+    assert(LHS.Qualifier != nullptr);
+    assert(RHS.Qualifier != nullptr);
+
+    assert(LHS.Name != nullptr);
+    assert(RHS.Name != nullptr);
+
+    return LHS.Qualifier->equals(RHS.Qualifier) && LHS.Name->equals(RHS.Name);
+  }
+
+  friend bool operator!=(QualifiedName const &LHS, QualifiedName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class VectorType final : public Node {
   const Node *BaseType;
   const Node *Dimension;
 
 public:
   VectorType(const Node *BaseType_, const Node *Dimension_)
       : Node(KVectorType), BaseType(BaseType_), Dimension(Dimension_) {}
 
   template<typename Fn> void match(Fn F) const { F(BaseType, Dimension); }
 
   void printLeft(OutputBuffer &OB) const override {
     BaseType->print(OB);
     OB += " vector[";
     if (Dimension)
       Dimension->print(OB);
     OB += "]";
   }
+
+  friend bool operator==(VectorType const &LHS, VectorType const &RHS) {
+    return LHS.BaseType->equals(RHS.BaseType) &&
+           LHS.Dimension->equals(RHS.Dimension);
+  }
+
+  friend bool operator!=(VectorType const &LHS, VectorType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PixelVectorType final : public Node {
   const Node *Dimension;
 
 public:
   PixelVectorType(const Node *Dimension_)
       : Node(KPixelVectorType), Dimension(Dimension_) {}
 
   template<typename Fn> void match(Fn F) const { F(Dimension); }
 
   void printLeft(OutputBuffer &OB) const override {
     // FIXME: This should demangle as "vector pixel".
     OB += "pixel vector[";
     Dimension->print(OB);
     OB += "]";
   }
+
+  friend bool operator==(PixelVectorType const &LHS,
+                         PixelVectorType const &RHS) {
+    return LHS.Dimension->equals(RHS.Dimension);
+  }
+
+  friend bool operator!=(PixelVectorType const &LHS,
+                         PixelVectorType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class BinaryFPType final : public Node {
   const Node *Dimension;
 
 public:
   BinaryFPType(const Node *Dimension_)
       : Node(KBinaryFPType), Dimension(Dimension_) {}
 
   template<typename Fn> void match(Fn F) const { F(Dimension); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "_Float";
     Dimension->print(OB);
   }
+
+  friend bool operator==(BinaryFPType const &LHS, BinaryFPType const &RHS) {
+    return LHS.Dimension->equals(RHS.Dimension);
+  }
+
+  friend bool operator!=(BinaryFPType const &LHS, BinaryFPType const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 enum class TemplateParamKind { Type, NonType, Template };
 
 /// An invented name for a template parameter for which we don't have a
 /// corresponding template argument.
 ///
 /// This node is created when parsing the <lambda-sig> for a lambda with
case TemplateParamKind::NonType:
       break;
     case TemplateParamKind::Template:
       OB += "$TT";
       break;
     }
     if (Index > 0)
       OB << Index - 1;
   }
+
+  friend bool operator==(SyntheticTemplateParamName const &LHS,
+                         SyntheticTemplateParamName const &RHS) {
+    return LHS.Kind == RHS.Kind && LHS.Index == RHS.Index;
+  }
+
+  friend bool operator!=(SyntheticTemplateParamName const &LHS,
+                         SyntheticTemplateParamName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A template type parameter declaration, 'typename T'.
 class TypeTemplateParamDecl final : public Node {
   Node *Name;
 
 public:
   TypeTemplateParamDecl(Node *Name_)
       : Node(KTypeTemplateParamDecl, Cache::Yes), Name(Name_) {}
 
   template<typename Fn> void match(Fn F) const { F(Name); }
 
   void printLeft(OutputBuffer &OB) const override { OB += "typename "; }
 
   void printRight(OutputBuffer &OB) const override { Name->print(OB); }
+
+  friend bool operator==(TypeTemplateParamDecl const &LHS,
+                         TypeTemplateParamDecl const &RHS) {
+    return LHS.Name->equals(RHS.Name);
+  }
+
+  friend bool operator!=(TypeTemplateParamDecl const &LHS,
+                         TypeTemplateParamDecl const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A non-type template parameter declaration, 'int N'.
 class NonTypeTemplateParamDecl final : public Node {
   Node *Name;
   Node *Type;
 
 public:
   NonTypeTemplateParamDecl(Node *Name_, Node *Type_)
       : Node(KNonTypeTemplateParamDecl, Cache::Yes), Name(Name_), Type(Type_) {}
 
   template<typename Fn> void match(Fn F) const { F(Name, Type); }
 
   void printLeft(OutputBuffer &OB) const override {
     Type->printLeft(OB);
     if (!Type->hasRHSComponent(OB))
       OB += " ";
   }
 
   void printRight(OutputBuffer &OB) const override {
     Name->print(OB);
     Type->printRight(OB);
   }
+
+  friend bool operator==(NonTypeTemplateParamDecl const &LHS,
+                         NonTypeTemplateParamDecl const &RHS) {
+    return LHS.Name->equals(RHS.Name) && LHS.Type->equals(RHS.Type);
+  }
+
+  friend bool operator!=(NonTypeTemplateParamDecl const &LHS,
+                         NonTypeTemplateParamDecl const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A template template parameter declaration,
 /// 'template<typename T> typename N'.
 class TemplateTemplateParamDecl final : public Node {
   Node *Name;
   NodeArray Params;
 
 public:
   TemplateTemplateParamDecl(Node *Name_, NodeArray Params_)
       : Node(KTemplateTemplateParamDecl, Cache::Yes), Name(Name_),
         Params(Params_) {}
 
   template<typename Fn> void match(Fn F) const { F(Name, Params); }
 
   void printLeft(OutputBuffer &OB) const override {
     ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
     OB += "template<";
     Params.printWithComma(OB);
     OB += "> typename ";
   }
 
   void printRight(OutputBuffer &OB) const override { Name->print(OB); }
+
+  friend bool operator==(TemplateTemplateParamDecl const &LHS,
+                         TemplateTemplateParamDecl const &RHS) {
+    return LHS.Name->equals(RHS.Name) && LHS.Params == RHS.Params;
+  }
+
+  friend bool operator!=(TemplateTemplateParamDecl const &LHS,
+                         TemplateTemplateParamDecl const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A template parameter pack declaration, 'typename ...T'.
 class TemplateParamPackDecl final : public Node {
   Node *Param;
 
 public:
   TemplateParamPackDecl(Node *Param_)
       : Node(KTemplateParamPackDecl, Cache::Yes), Param(Param_) {}
 
   template<typename Fn> void match(Fn F) const { F(Param); }
 
   void printLeft(OutputBuffer &OB) const override {
     Param->printLeft(OB);
     OB += "...";
   }
 
   void printRight(OutputBuffer &OB) const override { Param->printRight(OB); }
+
+  friend bool operator==(TemplateParamPackDecl const &LHS,
+                         TemplateParamPackDecl const &RHS) {
+    return LHS.Param->equals(RHS.Param);
+  }
+
+  friend bool operator!=(TemplateParamPackDecl const &LHS,
+                         TemplateParamPackDecl const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// An unexpanded parameter pack (either in the expression or type context). If
 /// this AST is correct, this node will have a ParameterPackExpansion node above
 /// it.
 ///
 /// This node is created when some <template-args> are found that apply to an
 /// <encoding>, and is stored in the TemplateParams table. In order for this to
if (Idx < Data.size())
       Data[Idx]->printLeft(OB);
   }
   void printRight(OutputBuffer &OB) const override {
     initializePackExpansion(OB);
     size_t Idx = OB.CurrentPackIndex;
     if (Idx < Data.size())
       Data[Idx]->printRight(OB);
   }
+
+  friend bool operator==(ParameterPack const &LHS, ParameterPack const &RHS) {
+    return LHS.Data == RHS.Data;
+  }
+
+  friend bool operator!=(ParameterPack const &LHS, ParameterPack const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A variadic template argument. This node represents an occurrence of
 /// J<something>E in some <template-args>. It isn't itself unexpanded, unless
 /// one of it's Elements is. The parser inserts a ParameterPack into the
 /// TemplateParams table if the <template-args> this pack belongs to apply to an
 /// <encoding>.
 class TemplateArgumentPack final : public Node {
   NodeArray Elements;
 public:
   TemplateArgumentPack(NodeArray Elements_)
       : Node(KTemplateArgumentPack), Elements(Elements_) {}
 
   template<typename Fn> void match(Fn F) const { F(Elements); }
 
   NodeArray getElements() const { return Elements; }
 
   void printLeft(OutputBuffer &OB) const override {
     Elements.printWithComma(OB);
   }
+
+  friend bool operator==(TemplateArgumentPack const &LHS,
+                         TemplateArgumentPack const &RHS) {
+    return LHS.Elements == RHS.Elements;
+  }
+
+  friend bool operator!=(TemplateArgumentPack const &LHS,
+                         TemplateArgumentPack const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A pack expansion. Below this node, there are some unexpanded ParameterPacks
 /// which each have Child->ParameterPackSize elements.
 class ParameterPackExpansion final : public Node {
   const Node *Child;
 
 public:
void printLeft(OutputBuffer &OB) const override {
 
     // Else, iterate through the rest of the elements in the pack.
     for (unsigned I = 1, E = OB.CurrentPackMax; I < E; ++I) {
       OB += ", ";
       OB.CurrentPackIndex = I;
       Child->print(OB);
     }
   }
+
+  friend bool operator==(ParameterPackExpansion const &LHS,
+                         ParameterPackExpansion const &RHS) {
+    return LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(ParameterPackExpansion const &LHS,
+                         ParameterPackExpansion const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class TemplateArgs final : public Node {
   NodeArray Params;
 
 public:
   TemplateArgs(NodeArray Params_) : Node(KTemplateArgs), Params(Params_) {}
 
   template<typename Fn> void match(Fn F) const { F(Params); }
 
   NodeArray getParams() { return Params; }
 
   void printLeft(OutputBuffer &OB) const override {
     ScopedOverride<unsigned> LT(OB.GtIsGt, 0);
     OB += "<";
     Params.printWithComma(OB);
     OB += ">";
   }
+
+  friend bool operator==(TemplateArgs const &LHS, TemplateArgs const &RHS) {
+    return LHS.Params == RHS.Params;
+  }
+
+  friend bool operator!=(TemplateArgs const &LHS, TemplateArgs const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 /// A forward-reference to a template argument that was not known at the point
 /// where the template parameter name was parsed in a mangling.
 ///
 /// This is created when demangling the name of a specialization of a
 /// conversion function template:
 ///
void printLeft(OutputBuffer &OB) const override {
     Ref->printLeft(OB);
   }
   void printRight(OutputBuffer &OB) const override {
     if (Printing)
       return;
     ScopedOverride<bool> SavePrinting(Printing, true);
     Ref->printRight(OB);
   }
+
+  friend bool operator==(ForwardTemplateReference const &LHS,
+                         ForwardTemplateReference const &RHS) {
+    if (LHS.Index != RHS.Index)
+      return false;
+
+    // Ignore 'Printing' member
+    if (LHS.Ref != nullptr && RHS.Ref != nullptr)
+      return LHS.Ref->equals(RHS.Ref);
+
+    return LHS.Ref == nullptr && RHS.Ref == nullptr;
+  }
+
+  friend bool operator!=(ForwardTemplateReference const &LHS,
+                         ForwardTemplateReference const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 struct NameWithTemplateArgs : Node {
   // name<template_args>
   Node *Name;
   Node *TemplateArgs;
 
   NameWithTemplateArgs(Node *Name_, Node *TemplateArgs_)
       : Node(KNameWithTemplateArgs), Name(Name_), TemplateArgs(TemplateArgs_) {}
 
   template<typename Fn> void match(Fn F) const { F(Name, TemplateArgs); }
 
   StringView getBaseName() const override { return Name->getBaseName(); }
 
   void printLeft(OutputBuffer &OB) const override {
     Name->print(OB);
     TemplateArgs->print(OB);
   }
+
+  friend bool operator==(NameWithTemplateArgs const &LHS,
+                         NameWithTemplateArgs const &RHS) {
+    return LHS.Name->equals(RHS.Name) &&
+           LHS.TemplateArgs->equals(RHS.TemplateArgs);
+  }
+
+  friend bool operator!=(NameWithTemplateArgs const &LHS,
+                         NameWithTemplateArgs const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class GlobalQualifiedName final : public Node {
   Node *Child;
 
 public:
   GlobalQualifiedName(Node* Child_)
       : Node(KGlobalQualifiedName), Child(Child_) {}
 
   template<typename Fn> void match(Fn F) const { F(Child); }
 
   StringView getBaseName() const override { return Child->getBaseName(); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "::";
     Child->print(OB);
   }
+
+  friend bool operator==(GlobalQualifiedName const &LHS,
+                         GlobalQualifiedName const &RHS) {
+    return LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(GlobalQualifiedName const &LHS,
+                         GlobalQualifiedName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 enum class SpecialSubKind {
   allocator,
   basic_string,
   string,
   istream,
   ostream,
void printLeft(OutputBuffer &OB) const override {
     OB << "std::" << getBaseName();
     if (isInstantiation()) {
       OB << "<char, std::char_traits<char>";
       if (SSK == SpecialSubKind::string)
         OB << ", std::allocator<char>";
       OB << ">";
     }
   }
+
+  friend bool operator==(ExpandedSpecialSubstitution const &LHS,
+                         ExpandedSpecialSubstitution const &RHS) {
+    return LHS.SSK == RHS.SSK;
+  }
+
+  friend bool operator!=(ExpandedSpecialSubstitution const &LHS,
+                         ExpandedSpecialSubstitution const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class SpecialSubstitution final : public ExpandedSpecialSubstitution {
 public:
   SpecialSubstitution(SpecialSubKind SSK_)
       : ExpandedSpecialSubstitution(SSK_, KSpecialSubstitution) {}
 
   template<typename Fn> void match(Fn F) const { F(SSK); }
public:
 
   template<typename Fn> void match(Fn F) const { F(Basename, IsDtor, Variant); }
 
   void printLeft(OutputBuffer &OB) const override {
     if (IsDtor)
       OB += "~";
     OB += Basename->getBaseName();
   }
+
+  friend bool operator==(CtorDtorName const &LHS, CtorDtorName const &RHS) {
+    assert(LHS.Basename != nullptr);
+    assert(RHS.Basename != nullptr);
+
+    return LHS.IsDtor == RHS.IsDtor && LHS.Variant == RHS.Variant &&
+           LHS.Basename->equals(RHS.Basename);
+  }
+
+  friend bool operator!=(CtorDtorName const &LHS, CtorDtorName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class DtorName : public Node {
   const Node *Base;
 
 public:
   DtorName(const Node *Base_) : Node(KDtorName), Base(Base_) {}
 
   template<typename Fn> void match(Fn F) const { F(Base); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "~";
     Base->printLeft(OB);
   }
+
+  friend bool operator==(DtorName const &LHS, DtorName const &RHS) {
+    assert(LHS.Base != nullptr);
+    assert(RHS.Base != nullptr);
+
+    return LHS.Base->equals(RHS.Base);
+  }
+
+  friend bool operator!=(DtorName const &LHS, DtorName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class UnnamedTypeName : public Node {
   const StringView Count;
 
 public:
   UnnamedTypeName(StringView Count_) : Node(KUnnamedTypeName), Count(Count_) {}
 
   template<typename Fn> void match(Fn F) const { F(Count); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "'unnamed";
     OB += Count;
     OB += "\'";
   }
+
+  friend bool operator==(UnnamedTypeName const &LHS,
+                         UnnamedTypeName const &RHS) {
+    return LHS.Count == RHS.Count;
+  }
+
+  friend bool operator!=(UnnamedTypeName const &LHS,
+                         UnnamedTypeName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ClosureTypeName : public Node {
   NodeArray TemplateParams;
   NodeArray Params;
   StringView Count;
 
 public:
public:
   }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "\'lambda";
     OB += Count;
     OB += "\'";
     printDeclarator(OB);
   }
+
+  friend bool operator==(ClosureTypeName const &LHS,
+                         ClosureTypeName const &RHS) {
+    return LHS.TemplateParams == RHS.TemplateParams &&
+           LHS.Params == RHS.Params && LHS.Count == RHS.Count;
+  }
+
+  friend bool operator!=(ClosureTypeName const &LHS,
+                         ClosureTypeName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class StructuredBindingName : public Node {
   NodeArray Bindings;
 public:
   StructuredBindingName(NodeArray Bindings_)
       : Node(KStructuredBindingName), Bindings(Bindings_) {}
 
   template<typename Fn> void match(Fn F) const { F(Bindings); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB.printOpen('[');
     Bindings.printWithComma(OB);
     OB.printClose(']');
   }
+
+  friend bool operator==(StructuredBindingName const &LHS,
+                         StructuredBindingName const &RHS) {
+    return LHS.Bindings == RHS.Bindings;
+  }
+
+  friend bool operator!=(StructuredBindingName const &LHS,
+                         StructuredBindingName const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 // -- Expression Nodes --
 
 class BinaryExpr : public Node {
   const Node *LHS;
   const StringView InfixOperator;
   const Node *RHS;
void printLeft(OutputBuffer &OB) const override {
     if (!(InfixOperator == ","))
       OB += " ";
     OB += InfixOperator;
     OB += " ";
     RHS->printAsOperand(OB, getPrecedence(), IsAssign);
     if (ParenAll)
       OB.printClose();
   }
+
+  friend bool operator==(BinaryExpr const &Left, BinaryExpr const &Right) {
+    return Left.InfixOperator == Right.InfixOperator &&
+           Left.LHS->equals(Right.LHS) && Left.RHS->equals(Right.RHS);
+  }
+
+  friend bool operator!=(BinaryExpr const &Left, BinaryExpr const &Right) {
+    return !(Left == Right);
+  }
 };
 
 class ArraySubscriptExpr : public Node {
   const Node *Op1;
   const Node *Op2;
 
 public:
   ArraySubscriptExpr(const Node *Op1_, const Node *Op2_, Prec Prec_)
       : Node(KArraySubscriptExpr, Prec_), Op1(Op1_), Op2(Op2_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Op1, Op2, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Op1->printAsOperand(OB, getPrecedence());
     OB.printOpen('[');
     Op2->printAsOperand(OB);
     OB.printClose(']');
   }
+
+  friend bool operator==(ArraySubscriptExpr const &LHS,
+                         ArraySubscriptExpr const &RHS) {
+    return LHS.Op1->equals(RHS.Op1) && LHS.Op2->equals(RHS.Op2);
+  }
+
+  friend bool operator!=(ArraySubscriptExpr const &LHS,
+                         ArraySubscriptExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PostfixExpr : public Node {
   const Node *Child;
   const StringView Operator;
 
 public:
   PostfixExpr(const Node *Child_, StringView Operator_, Prec Prec_)
       : Node(KPostfixExpr, Prec_), Child(Child_), Operator(Operator_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Child, Operator, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Child->printAsOperand(OB, getPrecedence(), true);
     OB += Operator;
   }
+
+  friend bool operator==(PostfixExpr const &LHS, PostfixExpr const &RHS) {
+    return LHS.Operator == RHS.Operator && LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(PostfixExpr const &LHS, PostfixExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ConditionalExpr : public Node {
   const Node *Cond;
   const Node *Then;
   const Node *Else;
 
 public:
   ConditionalExpr(const Node *Cond_, const Node *Then_, const Node *Else_,
                   Prec Prec_)
       : Node(KConditionalExpr, Prec_), Cond(Cond_), Then(Then_), Else(Else_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Cond, Then, Else, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Cond->printAsOperand(OB, getPrecedence());
     OB += " ? ";
     Then->printAsOperand(OB);
     OB += " : ";
     Else->printAsOperand(OB, Prec::Assign, true);
   }
+
+  friend bool operator==(ConditionalExpr const &LHS,
+                         ConditionalExpr const &RHS) {
+    return LHS.Cond->equals(RHS.Cond) && LHS.Then->equals(RHS.Then) &&
+           LHS.Else->equals(RHS.Else);
+  }
+
+  friend bool operator!=(ConditionalExpr const &LHS,
+                         ConditionalExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class MemberExpr : public Node {
   const Node *LHS;
   const StringView Kind;
   const Node *RHS;
 
 public:
   MemberExpr(const Node *LHS_, StringView Kind_, const Node *RHS_, Prec Prec_)
       : Node(KMemberExpr, Prec_), LHS(LHS_), Kind(Kind_), RHS(RHS_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(LHS, Kind, RHS, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     LHS->printAsOperand(OB, getPrecedence(), true);
     OB += Kind;
     RHS->printAsOperand(OB, getPrecedence(), false);
   }
+
+  friend bool operator==(MemberExpr const &Left, MemberExpr const &Right) {
+    return Left.Kind == Right.Kind && Left.LHS->equals(Right.LHS) &&
+           Left.RHS->equals(Right.RHS);
+  }
+
+  friend bool operator!=(MemberExpr const &Left, MemberExpr const &Right) {
+    return !(Left == Right);
+  }
 };
 
 class SubobjectExpr : public Node {
   const Node *Type;
   const Node *SubExpr;
   StringView Offset;
   NodeArray UnionSelectors;
   bool OnePastTheEnd;
void printLeft(OutputBuffer &OB) const override {
     } else if (Offset[0] == 'n') {
       OB += "-";
       OB += Offset.dropFront();
     } else {
       OB += Offset;
     }
     OB += ">";
   }
+
+  friend bool operator==(SubobjectExpr const &LHS, SubobjectExpr const &RHS) {
+    return LHS.Offset == RHS.Offset && LHS.OnePastTheEnd == RHS.OnePastTheEnd &&
+           LHS.Type->equals(RHS.Type) && LHS.SubExpr->equals(RHS.SubExpr) &&
+           LHS.UnionSelectors == RHS.UnionSelectors;
+  }
+
+  friend bool operator!=(SubobjectExpr const &LHS, SubobjectExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class EnclosingExpr : public Node {
   const StringView Prefix;
   const Node *Infix;
   const StringView Postfix;
 
 public:
   EnclosingExpr(StringView Prefix_, const Node *Infix_,
                 Prec Prec_ = Prec::Primary)
       : Node(KEnclosingExpr, Prec_), Prefix(Prefix_), Infix(Infix_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Prefix, Infix, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += Prefix;
     OB.printOpen();
     Infix->print(OB);
     OB.printClose();
     OB += Postfix;
   }
+
+  friend bool operator==(EnclosingExpr const &LHS, EnclosingExpr const &RHS) {
+    return LHS.Prefix == RHS.Prefix && LHS.Postfix == RHS.Postfix &&
+           LHS.Infix->equals(RHS.Infix);
+  }
+
+  friend bool operator!=(EnclosingExpr const &LHS, EnclosingExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class CastExpr : public Node {
   // cast_kind<to>(from)
   const StringView CastKind;
   const Node *To;
   const Node *From;
 
OB += CastKind;
       OB += "<";
       To->printLeft(OB);
       OB += ">";
     }
     OB.printOpen();
     From->printAsOperand(OB);
     OB.printClose();
   }
+
+  friend bool operator==(CastExpr const &LHS, CastExpr const &RHS) {
+    return LHS.CastKind == RHS.CastKind && LHS.To->equals(RHS.To) &&
+           LHS.From->equals(RHS.From);
+  }
+
+  friend bool operator!=(CastExpr const &LHS, CastExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class SizeofParamPackExpr : public Node {
   const Node *Pack;
 
 public:
   SizeofParamPackExpr(const Node *Pack_)
       : Node(KSizeofParamPackExpr), Pack(Pack_) {}
 
   template<typename Fn> void match(Fn F) const { F(Pack); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "sizeof...";
     OB.printOpen();
     ParameterPackExpansion PPE(Pack);
     PPE.printLeft(OB);
     OB.printClose();
   }
+
+  friend bool operator==(SizeofParamPackExpr const &LHS,
+                         SizeofParamPackExpr const &RHS) {
+    return LHS.Pack->equals(RHS.Pack);
+  }
+
+  friend bool operator!=(SizeofParamPackExpr const &LHS,
+                         SizeofParamPackExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class CallExpr : public Node {
   const Node *Callee;
   NodeArray Args;
 
 public:
   CallExpr(const Node *Callee_, NodeArray Args_, Prec Prec_)
       : Node(KCallExpr, Prec_), Callee(Callee_), Args(Args_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Callee, Args, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     Callee->print(OB);
     OB.printOpen();
     Args.printWithComma(OB);
     OB.printClose();
   }
+
+  friend bool operator==(CallExpr const &LHS, CallExpr const &RHS) {
+    return LHS.Callee->equals(RHS.Callee) && LHS.Args == RHS.Args;
+  }
+
+  friend bool operator!=(CallExpr const &LHS, CallExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class NewExpr : public Node {
   // new (expr_list) type(init_list)
   NodeArray ExprList;
   Node *Type;
   NodeArray InitList;
   bool IsGlobal; // ::operator new ?
void printLeft(OutputBuffer &OB) const override {
     OB += " ";
     Type->print(OB);
     if (!InitList.empty()) {
       OB.printOpen();
       InitList.printWithComma(OB);
       OB.printClose();
     }
   }
+
+  friend bool operator==(NewExpr const &LHS, NewExpr const &RHS) {
+    return LHS.IsGlobal == RHS.IsGlobal && LHS.IsArray == RHS.IsArray &&
+           LHS.Type->equals(RHS.Type) && LHS.ExprList == RHS.ExprList &&
+           LHS.InitList == RHS.InitList;
+  }
+
+  friend bool operator!=(NewExpr const &LHS, NewExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class DeleteExpr : public Node {
   Node *Op;
   bool IsGlobal;
   bool IsArray;
 
 public:
void printLeft(OutputBuffer &OB) const override {
     if (IsGlobal)
       OB += "::";
     OB += "delete";
     if (IsArray)
       OB += "[]";
     OB += ' ';
     Op->print(OB);
   }
+
+  friend bool operator==(DeleteExpr const &LHS, DeleteExpr const &RHS) {
+    return LHS.IsGlobal == RHS.IsGlobal && LHS.IsArray == RHS.IsArray &&
+           LHS.Op->equals(RHS.Op);
+  }
+
+  friend bool operator!=(DeleteExpr const &LHS, DeleteExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PrefixExpr : public Node {
   StringView Prefix;
   Node *Child;
 
 public:
   PrefixExpr(StringView Prefix_, Node *Child_, Prec Prec_)
       : Node(KPrefixExpr, Prec_), Prefix(Prefix_), Child(Child_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Prefix, Child, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += Prefix;
     Child->printAsOperand(OB, getPrecedence());
   }
+
+  friend bool operator==(PrefixExpr const &LHS, PrefixExpr const &RHS) {
+    return LHS.Prefix == RHS.Prefix && LHS.Child->equals(RHS.Child);
+  }
+
+  friend bool operator!=(PrefixExpr const &LHS, PrefixExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class FunctionParam : public Node {
   StringView Number;
 
 public:
   FunctionParam(StringView Number_) : Node(KFunctionParam), Number(Number_) {}
 
   template<typename Fn> void match(Fn F) const { F(Number); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "fp";
     OB += Number;
   }
+
+  friend bool operator==(FunctionParam const &LHS, FunctionParam const &RHS) {
+    return LHS.Number == RHS.Number;
+  }
+
+  friend bool operator!=(FunctionParam const &LHS, FunctionParam const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ConversionExpr : public Node {
   const Node *Type;
   NodeArray Expressions;
 
 public:
   ConversionExpr(const Node *Type_, NodeArray Expressions_, Prec Prec_)
       : Node(KConversionExpr, Prec_), Type(Type_), Expressions(Expressions_) {}
 
   template <typename Fn> void match(Fn F) const {
     F(Type, Expressions, getPrecedence());
   }
 
   void printLeft(OutputBuffer &OB) const override {
     OB.printOpen();
     Type->print(OB);
     OB.printClose();
     OB.printOpen();
     Expressions.printWithComma(OB);
     OB.printClose();
   }
+
+  friend bool operator==(ConversionExpr const &LHS, ConversionExpr const &RHS) {
+    return LHS.Type->equals(RHS.Type) && LHS.Expressions == RHS.Expressions;
+  }
+
+  friend bool operator!=(ConversionExpr const &LHS, ConversionExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class PointerToMemberConversionExpr : public Node {
   const Node *Type;
   const Node *SubExpr;
   StringView Offset;
 
 public:
public:
   void printLeft(OutputBuffer &OB) const override {
     OB.printOpen();
     Type->print(OB);
     OB.printClose();
     OB.printOpen();
     SubExpr->print(OB);
     OB.printClose();
   }
+
+  friend bool operator==(PointerToMemberConversionExpr const &LHS,
+                         PointerToMemberConversionExpr const &RHS) {
+    return LHS.Offset == RHS.Offset && LHS.Type->equals(RHS.Type) &&
+           LHS.SubExpr->equals(RHS.SubExpr);
+  }
+
+  friend bool operator!=(PointerToMemberConversionExpr const &LHS,
+                         PointerToMemberConversionExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class InitListExpr : public Node {
   const Node *Ty;
   NodeArray Inits;
 public:
   InitListExpr(const Node *Ty_, NodeArray Inits_)
       : Node(KInitListExpr), Ty(Ty_), Inits(Inits_) {}
 
   template<typename Fn> void match(Fn F) const { F(Ty, Inits); }
 
   void printLeft(OutputBuffer &OB) const override {
     if (Ty)
       Ty->print(OB);
     OB += '{';
     Inits.printWithComma(OB);
     OB += '}';
   }
+
+  friend bool operator==(InitListExpr const &LHS, InitListExpr const &RHS) {
+    if (!!LHS.Ty != !!RHS.Ty)
+      return false;
+
+    if (LHS.Ty)
+      if (!LHS.Ty->equals(RHS.Ty))
+        return false;
+
+    return LHS.Inits == RHS.Inits;
+  }
+
+  friend bool operator!=(InitListExpr const &LHS, InitListExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class BracedExpr : public Node {
   const Node *Elem;
   const Node *Init;
   bool IsArray;
 public:
   BracedExpr(const Node *Elem_, const Node *Init_, bool IsArray_)
void printLeft(OutputBuffer &OB) const override {
     } else {
       OB += '.';
       Elem->print(OB);
     }
     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
       OB += " = ";
     Init->print(OB);
   }
+
+  friend bool operator==(BracedExpr const &LHS, BracedExpr const &RHS) {
+    return LHS.IsArray == RHS.IsArray && LHS.Elem->equals(RHS.Elem) &&
+           LHS.Init->equals(RHS.Init);
+  }
+
+  friend bool operator!=(BracedExpr const &LHS, BracedExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class BracedRangeExpr : public Node {
   const Node *First;
   const Node *Last;
   const Node *Init;
 public:
   BracedRangeExpr(const Node *First_, const Node *Last_, const Node *Init_)
       : Node(KBracedRangeExpr), First(First_), Last(Last_), Init(Init_) {}
 
   template<typename Fn> void match(Fn F) const { F(First, Last, Init); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += '[';
     First->print(OB);
     OB += " ... ";
     Last->print(OB);
     OB += ']';
     if (Init->getKind() != KBracedExpr && Init->getKind() != KBracedRangeExpr)
       OB += " = ";
     Init->print(OB);
   }
+
+  friend bool operator==(BracedRangeExpr const &LHS,
+                         BracedRangeExpr const &RHS) {
+    return LHS.First->equals(RHS.First) && LHS.Last->equals(RHS.Last) &&
+           LHS.Init->equals(RHS.Init);
+  }
+
+  friend bool operator!=(BracedRangeExpr const &LHS,
+                         BracedRangeExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class FoldExpr : public Node {
   const Node *Pack, *Init;
   StringView OperatorName;
   bool IsLeftFold;
 
 public:
if (IsLeftFold || Init != nullptr) {
       OB << " " << OperatorName << " ";
       if (IsLeftFold)
         PrintPack();
       else
         Init->printAsOperand(OB, Prec::Cast, true);
     }
     OB.printClose();
   }
+
+  friend bool operator==(FoldExpr const &LHS, FoldExpr const &RHS) {
+    if (LHS.IsLeftFold != RHS.IsLeftFold ||
+        LHS.OperatorName == RHS.OperatorName)
+      return false;
+
+    if (!!LHS.Pack != !!RHS.Pack)
+      return false;
+
+    if (LHS.Pack)
+      if (!LHS.Pack->equals(RHS.Pack))
+        return false;
+
+    if (LHS.Init != nullptr && RHS.Init != nullptr)
+      return LHS.Init->equals(RHS.Init);
+
+    return LHS.Init == nullptr && RHS.Init == nullptr;
+  }
+
+  friend bool operator!=(FoldExpr const &LHS, FoldExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class ThrowExpr : public Node {
   const Node *Op;
 
 public:
   ThrowExpr(const Node *Op_) : Node(KThrowExpr), Op(Op_) {}
 
   template<typename Fn> void match(Fn F) const { F(Op); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "throw ";
     Op->print(OB);
   }
+
+  friend bool operator==(ThrowExpr const &LHS, ThrowExpr const &RHS) {
+    return LHS.Op->equals(RHS.Op);
+  }
+
+  friend bool operator!=(ThrowExpr const &LHS, ThrowExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class BoolExpr : public Node {
   bool Value;
 
 public:
   BoolExpr(bool Value_) : Node(KBoolExpr), Value(Value_) {}
 
   template<typename Fn> void match(Fn F) const { F(Value); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += Value ? StringView("true") : StringView("false");
   }
+
+  friend bool operator==(BoolExpr const &LHS, BoolExpr const &RHS) {
+    return LHS.Value == RHS.Value;
+  }
+
+  friend bool operator!=(BoolExpr const &LHS, BoolExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class StringLiteral : public Node {
   const Node *Type;
 
 public:
   StringLiteral(const Node *Type_) : Node(KStringLiteral), Type(Type_) {}
 
   template<typename Fn> void match(Fn F) const { F(Type); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "\"<";
     Type->print(OB);
     OB += ">\"";
   }
+
+  friend bool operator==(StringLiteral const &LHS, StringLiteral const &RHS) {
+    assert(LHS.Type != nullptr);
+    assert(RHS.Type != nullptr);
+
+    return LHS.Type->equals(RHS.Type);
+  }
+
+  friend bool operator!=(StringLiteral const &LHS, StringLiteral const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class LambdaExpr : public Node {
   const Node *Type;
 
 public:
   LambdaExpr(const Node *Type_) : Node(KLambdaExpr), Type(Type_) {}
 
   template<typename Fn> void match(Fn F) const { F(Type); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB += "[]";
     if (Type->getKind() == KClosureTypeName)
       static_cast<const ClosureTypeName *>(Type)->printDeclarator(OB);
     OB += "{...}";
   }
+
+  friend bool operator==(LambdaExpr const &LHS, LambdaExpr const &RHS) {
+    return LHS.Type->equals(RHS.Type);
+  }
+
+  friend bool operator!=(LambdaExpr const &LHS, LambdaExpr const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class EnumLiteral : public Node {
   // ty(integer)
   const Node *Ty;
   StringView Integer;
 
 public:
   EnumLiteral(const Node *Ty_, StringView Integer_)
       : Node(KEnumLiteral), Ty(Ty_), Integer(Integer_) {}
 
   template<typename Fn> void match(Fn F) const { F(Ty, Integer); }
 
   void printLeft(OutputBuffer &OB) const override {
     OB.printOpen();
     Ty->print(OB);
     OB.printClose();
 
     if (Integer[0] == 'n')
       OB << "-" << Integer.dropFront(1);
     else
       OB << Integer;
   }
+
+  friend bool operator==(EnumLiteral const &LHS, EnumLiteral const &RHS) {
+    assert(LHS.Ty != nullptr);
+    assert(RHS.Ty != nullptr);
+
+    return LHS.Integer == RHS.Integer && LHS.Ty->equals(RHS.Ty);
+  }
+
+  friend bool operator!=(EnumLiteral const &LHS, EnumLiteral const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 class IntegerLiteral : public Node {
   StringView Type;
   StringView Value;
 
 public:
   IntegerLiteral(StringView Type_, StringView Value_)
if (Value[0] == 'n') {
       OB += '-';
       OB += Value.dropFront(1);
     } else
       OB += Value;
 
     if (Type.size() <= 3)
       OB += Type;
   }
+
+  friend bool operator==(IntegerLiteral const &LHS, IntegerLiteral const &RHS) {
+    return LHS.Type == RHS.Type && LHS.Value == RHS.Value;
+  }
+
+  friend bool operator!=(IntegerLiteral const &LHS, IntegerLiteral const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 template <class Float> struct FloatData;
 
 namespace float_literal_impl {
 constexpr Node::Kind getFloatLiteralKind(float *) {
   return Node::KFloatLiteral;
 }

 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
       std::reverse(buf, e);
 #endif
       char num[FloatData<Float>::max_demangled_size] = {0};
       int n = snprintf(num, sizeof(num), FloatData<Float>::spec, value);
       OB += StringView(num, num + n);
     }
   }
+
+  friend bool operator==(FloatLiteralImpl<Float> const &LHS,
+                         FloatLiteralImpl<Float> const &RHS) {
+    return LHS.Contents == RHS.Contents;
+  }
+
+  friend bool operator!=(FloatLiteralImpl<Float> const &LHS,
+                         FloatLiteralImpl<Float> const &RHS) {
+    return !(LHS == RHS);
+  }
 };
 
 using FloatLiteral = FloatLiteralImpl<float>;
 using DoubleLiteral = FloatLiteralImpl<double>;
 using LongDoubleLiteral = FloatLiteralImpl<long double>;
 
 /// Visit the node. Calls \c F(P), where \c P is the node cast to the
 /// appropriate derived class.

llvm/unittests/Demangle/ItaniumDemangleTest.cpp

 //===------------------ ItaniumDemangleTest.cpp ---------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Demangle/ItaniumDemangle.h"
+#include "ItaniumDemangleTestUtils.h"
+#include "llvm/IR/Argument.h"
 #include "llvm/Support/Allocator.h"
 #include "gmock/gmock.h"
 #include "gtest/gtest.h"
+#include <algorithm>
 #include <cstdlib>
+#include <iterator>
 #include <vector>
 
 using namespace llvm;
 using namespace llvm::itanium_demangle;
-
-namespace {
-class TestAllocator {
-  BumpPtrAllocator Alloc;
-
-public:
-  void reset() { Alloc.Reset(); }
-
-  template <typename T, typename... Args> T *makeNode(Args &&... args) {
-    return new (Alloc.Allocate(sizeof(T), alignof(T)))
-        T(std::forward<Args>(args)...);
-  }
-
-  void *allocateNodeArray(size_t sz) {
-    return Alloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
-  }
-};
-} // namespace
+using namespace llvm::itanium_demangle::test_utils;
 
 namespace NodeMatcher {
 // Make sure the node matchers provide constructor parameters. This is a
 // compilation test.
 template <typename NT> struct Ctor {
   template <typename... Args> void operator()(Args &&...args) {
     auto _ = NT(std::forward<Args>(args)...);
   }
struct TestParser : AbstractManglingParser<TestParser, TestAllocator> {
     }
   };
 
   // void f(A<_Float16>, _Float16);
   TestParser Parser("_Z1f1AIDF16_EDF16_");
   ASSERT_NE(nullptr, Parser.parse());
   EXPECT_THAT(Parser.Types, testing::ElementsAre("_Float16", "A", "_Float16"));
 }
+
+TEST(ItaniumDemangle, Equality_NodeArray) {
+  ManglingNodeCreator Creator;
+
+  // Test empty NodeArray equality
+  std::vector<Node *> LHS;
+  std::vector<Node *> RHS;
+
+  // Empty == Empty
+  ASSERT_EQ(Creator.makeNodeArray(LHS.cbegin(), LHS.cend()),
+            Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+
+  RHS.push_back(Creator.makeReferenceType(Qualifiers::QualNone, "test",
+                                          ReferenceKind::RValue));
+
+  // Empty vs. non-empty
+  ASSERT_NE(Creator.makeNodeArray(LHS.cbegin(), LHS.cend()),
+            Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+
+  LHS.push_back(Creator.makeReferenceType(Qualifiers::QualNone, "test",
+                                          ReferenceKind::RValue));
+
+  // Equal single nodes
+  ASSERT_EQ(Creator.makeNodeArray(LHS.cbegin(), LHS.cend()),
+            Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+
+  LHS.push_back(Creator.makeReferenceType(Qualifiers::QualNone, "test",
+                                          ReferenceKind::LValue));
+  RHS.push_back(Creator.makeReferenceType(Qualifiers::QualRestrict, "test",
+                                          ReferenceKind::RValue));
+
+  // Non-equal second node
+  ASSERT_NE(Creator.makeNodeArray(LHS.cbegin(), LHS.cend()),
+            Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+}
+
+TEST(ItaniumDemangle, Equality_Node) {
+  ManglingNodeCreator Creator;
+
+  // Comparison of nodes with mismatching kinds should fail
+  ASSERT_FALSE(test_utils::compareNodes(Creator.make<NameType>("Foo"),
+                                        Creator.make<FloatLiteral>("1.0")));
+}
+
+TEST(ItaniumDemangle, Equality_QualType) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Same qualifiers and name
+    Node const *Q1 = Creator.makeQualType("Test", Qualifiers::QualVolatile);
+    Node const *Q2 = Creator.makeQualType("Test", Qualifiers::QualVolatile);
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different qualifiers
+    Node const *Q1 = Creator.makeQualType("Test", Qualifiers::QualNone);
+    Node const *Q2 = Creator.makeQualType("Test", Qualifiers::QualRestrict);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different name
+    Node const *Q1 = Creator.makeQualType("Test", Qualifiers::QualNone);
+    Node const *Q2 = Creator.makeQualType("", Qualifiers::QualNone);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_NameType) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Both empty
+    Node const *Q1 = Creator.make<NameType>("");
+    Node const *Q2 = Creator.make<NameType>("");
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Both non-empty
+    Node const *Q1 = Creator.make<NameType>("test");
+    Node const *Q2 = Creator.make<NameType>("test");
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Not equal
+    Node const *Q1 = Creator.make<NameType>("test");
+    Node const *Q2 = Creator.make<NameType>("tes");
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_ReferenceType) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Same type
+    Node const *Q1 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::LValue);
+    Node const *Q2 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::LValue);
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different name
+    Node const *Q1 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::LValue);
+    Node const *Q2 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Tes",
+                                               ReferenceKind::LValue);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different CV-qualifiers
+    Node const *Q1 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::LValue);
+    Node const *Q2 = Creator.makeReferenceType(Qualifiers::QualRestrict, "Test",
+                                               ReferenceKind::LValue);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different ref-qualifiers
+    Node const *Q1 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::LValue);
+    Node const *Q2 = Creator.makeReferenceType(Qualifiers::QualVolatile, "Test",
+                                               ReferenceKind::RValue);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_TemplateArgs) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> LHS;
+  std::vector<Node *> RHS;
+
+  {
+    // Both empty
+    Node const *Q1 = Creator.makeTemplateArgs(LHS);
+    Node const *Q2 = Creator.makeTemplateArgs(RHS);
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  LHS.push_back(Creator.make<NameType>("test"));
+  RHS.push_back(Creator.make<NameType>("test"));
+
+  {
+    // Both equal
+    Node const *Q1 = Creator.makeTemplateArgs(LHS);
+    Node const *Q2 = Creator.makeTemplateArgs(RHS);
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  LHS.push_back(Creator.make<NameType>("foo"));
+  RHS.push_back(Creator.make<NameType>("bar"));
+
+  {
+    // Not equal anymore
+    Node const *Q1 = Creator.makeTemplateArgs(LHS);
+    Node const *Q2 = Creator.makeTemplateArgs(RHS);
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_NameWithTemplateArgs) {
+  ManglingNodeCreator Creator;
+
+  {
+    // No args
+    Node const *Q1 = Creator.makeNameWithTemplateArgs("Foo", {});
+    Node const *Q2 = Creator.makeNameWithTemplateArgs("Foo", {});
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Equal
+    Node const *Q1 = Creator.makeNameWithTemplateArgs(
+        "Foo", {Creator.make<NameType>("foo")});
+    Node const *Q2 = Creator.makeNameWithTemplateArgs(
+        "Foo", {Creator.make<NameType>("foo")});
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different name
+    Node const *Q1 = Creator.makeNameWithTemplateArgs(
+        "Foo", {Creator.make<NameType>("foo")});
+    Node const *Q2 = Creator.makeNameWithTemplateArgs(
+        "Bar", {Creator.make<NameType>("foo")});
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  {
+    // Different args
+    Node const *Q1 = Creator.makeNameWithTemplateArgs(
+        "Foo", {Creator.make<NameType>("foo"), Creator.make<NameType>("bar")});
+
+    Node const *Q2 = Creator.makeNameWithTemplateArgs(
+        "Foo", {Creator.make<NameType>("bar"), Creator.make<NameType>("foo")});
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_NodeArrayNode) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> LHS;
+  std::vector<Node *> RHS;
+
+  {
+    Node const *Q1 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(LHS.cbegin(), LHS.cend()));
+    Node const *Q2 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  LHS.push_back(Creator.make<NameType>("Foo"));
+  RHS.push_back(Creator.make<NameType>("Foo"));
+
+  {
+    // Equal
+    Node const *Q1 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(LHS.cbegin(), LHS.cend()));
+    Node const *Q2 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+    ASSERT_TRUE(test_utils::compareNodes(Q1, Q2));
+  }
+
+  LHS.push_back(Creator.make<NameType>("Bar"));
+  RHS.push_back(Creator.make<NameType>("Qux"));
+
+  {
+    // Not equal
+    Node const *Q1 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(LHS.cbegin(), LHS.cend()));
+    Node const *Q2 = Creator.make<NodeArrayNode>(
+        Creator.makeNodeArray(RHS.cbegin(), RHS.cend()));
+    ASSERT_FALSE(test_utils::compareNodes(Q1, Q2));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_DotSuffix) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> ParamNodes{
+      Creator.makeReferenceType(Qualifiers::QualVolatile, "Foo",
+                                ReferenceKind::LValue),
+      Creator.makeReferenceType(Qualifiers::QualRestrict, "Bar",
+                                ReferenceKind::RValue)};
+
+  Node const *Func1 = Creator.makeFunctionEncoding("Baz", ParamNodes, {}, {});
+  Node const *Func2 = Creator.makeFunctionEncoding("Qux", ParamNodes, {}, {});
+  ASSERT_FALSE(test_utils::compareNodes(Func1, Func2));
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<DotSuffix>(Func1, "foo");
+    Node const *RHS = Creator.make<DotSuffix>(Func1, "foo");
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different suffix
+    Node const *LHS = Creator.make<DotSuffix>(Func1, "foo");
+    Node const *RHS = Creator.make<DotSuffix>(Func1, "bar");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different prefix
+    Node const *LHS = Creator.make<DotSuffix>(Func1, "foo");
+    Node const *RHS = Creator.make<DotSuffix>(Func2, "foo");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_NestedName) {
+  ManglingNodeCreator Creator;
+
+  auto *Scope1 = Creator.make<NameType>("S1");
+  auto *Scope2 = Creator.make<NameType>("S2");
+
+  auto *Name1 = Creator.make<NameType>("Foo");
+  auto *Name2 = Creator.make<NameType>("Bar");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<NestedName>(Scope1, Name1);
+    Node const *RHS = Creator.make<NestedName>(Scope1, Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different scope
+    Node const *LHS = Creator.make<NestedName>(Scope1, Name1);
+    Node const *RHS = Creator.make<NestedName>(Scope2, Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<NestedName>(Scope1, Name1);
+    Node const *RHS = Creator.make<NestedName>(Scope1, Name2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_ModuleName) {
+  ManglingNodeCreator Creator;
+
+  auto *Name1 = Creator.make<NameType>("Foo");
+  auto *Name2 = Creator.make<NameType>("Bar");
+
+  ModuleName *Parent1 =
+      static_cast<ModuleName *>(Creator.make<ModuleName>(nullptr, Name1, true));
+
+  ModuleName *Parent2 = static_cast<ModuleName *>(
+      Creator.make<ModuleName>(Parent1, Name2, false));
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<ModuleName>(Parent1, Name1, true);
+    Node const *RHS = Creator.make<ModuleName>(Parent1, Name1, true);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different parents
+    Node const *LHS = Creator.make<ModuleName>(Parent1, Name1, true);
+    Node const *RHS = Creator.make<ModuleName>(Parent2, Name1, true);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<ModuleName>(Parent2, Name1, true);
+    Node const *RHS = Creator.make<ModuleName>(Parent2, Name2, true);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different partition type
+    Node const *LHS = Creator.make<ModuleName>(Parent2, Name1, true);
+    Node const *RHS = Creator.make<ModuleName>(Parent2, Name1, false);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_LocalName) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> ParamNodes{
+      Creator.makeReferenceType(Qualifiers::QualVolatile, "Foo",
+                                ReferenceKind::LValue),
+      Creator.makeReferenceType(Qualifiers::QualRestrict, "Bar",
+                                ReferenceKind::RValue)};
+
+  Node *Func1 = Creator.makeFunctionEncoding("Baz", ParamNodes, {}, {});
+  Node *Func2 = Creator.makeFunctionEncoding("Qux", ParamNodes, {}, {});
+  ASSERT_FALSE(test_utils::compareNodes(Func1, Func2));
+
+  Node *Name1 = Creator.make<NestedName>(Creator.make<NameType>("Scope1"),
+                                         Creator.make<NameType>("Name1"));
+
+  Node *Name2 = Creator.make<NestedName>(Creator.make<NameType>("Scope2"),
+                                         Creator.make<NameType>("Name2"));
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<LocalName>(Func1, Name1);
+    Node const *RHS = Creator.make<LocalName>(Func1, Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different encoding
+    Node const *LHS = Creator.make<LocalName>(Func1, Name1);
+    Node const *RHS = Creator.make<LocalName>(Func2, Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<LocalName>(Func1, Name2);
+    Node const *RHS = Creator.make<LocalName>(Func1, Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_QualifiedName) {
+  ManglingNodeCreator Creator;
+
+  auto *Scope1 = Creator.make<NameType>("Foo");
+  auto *Scope2 = Creator.make<NameType>("Bar");
+
+  auto *Name1 = Creator.make<NameType>("foo");
+  auto *Name2 = Creator.make<NameType>("bar");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<QualifiedName>(Scope1, Name1);
+    Node const *RHS = Creator.make<QualifiedName>(Scope1, Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different scope
+    Node const *LHS = Creator.make<QualifiedName>(Scope1, Name1);
+    Node const *RHS = Creator.make<QualifiedName>(Scope2, Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<QualifiedName>(Scope1, Name2);
+    Node const *RHS = Creator.make<QualifiedName>(Scope1, Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_CtorDtorName) {
+  ManglingNodeCreator Creator;
+
+  auto *Name1 = Creator.make<NameType>("Foo");
+  auto *Name2 = Creator.make<NameType>("Bar");
+
+  int Variant1 = '5' - '0';
+  int Variant2 = '4' - '0';
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<CtorDtorName>(Name1, true, Variant1);
+    Node const *RHS = Creator.make<CtorDtorName>(Name1, true, Variant1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<CtorDtorName>(Name1, true, Variant1);
+    Node const *RHS = Creator.make<CtorDtorName>(Name2, true, Variant1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Constructor vs. Destructor
+    Node const *LHS = Creator.make<CtorDtorName>(Name1, true, Variant1);
+    Node const *RHS = Creator.make<CtorDtorName>(Name1, false, Variant1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different variant
+    Node const *LHS = Creator.make<CtorDtorName>(Name1, false, Variant2);
+    Node const *RHS = Creator.make<CtorDtorName>(Name1, false, Variant1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_DtorName) {
+  ManglingNodeCreator Creator;
+
+  auto *Name1 = Creator.make<NameType>("Foo");
+  auto *Name2 = Creator.make<NameType>("Bar");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<DtorName>(Name1);
+    Node const *RHS = Creator.make<DtorName>(Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<DtorName>(Name1);
+    Node const *RHS = Creator.make<DtorName>(Name2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_UnnamedTypename) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<UnnamedTypeName>("Foo");
+    Node const *RHS = Creator.make<UnnamedTypeName>("Foo");
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<UnnamedTypeName>("Foo");
+    Node const *RHS = Creator.make<UnnamedTypeName>("Bar");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_ClosureTypeName) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> Params1{Creator.make<NameType>("double"),
+                              Creator.make<NameType>("int")};
+
+  std::vector<Node *> Params2{Creator.make<NameType>("double"),
+                              Creator.make<NameType>("std::string")};
+
+  std::vector<Node *> TemplateParams1{Creator.make<NameType>("Foo"),
+                                      Creator.make<NameType>("Bar")};
+
+  std::vector<Node *> TemplateParams2{Creator.make<NameType>("Bar"),
+                                      Creator.make<NameType>("Foo")};
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    Node const *RHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    Node const *RHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Bar");
+
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different params
+    Node const *LHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    Node const *RHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params2.cbegin(), Params2.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different template params
+    Node const *LHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams1.cbegin(), TemplateParams1.cend()),
+        "Foo");
+
+    Node const *RHS = Creator.make<ClosureTypeName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()),
+        Creator.makeNodeArray(TemplateParams2.cbegin(), TemplateParams2.cend()),
+        "Foo");
+
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_StructuredBindingName) {
+  ManglingNodeCreator Creator;
+
+  std::vector<Node *> Params1{Creator.make<NameType>("Foo"),
+                              Creator.make<NameType>("Bar")};
+
+  std::vector<Node *> Params2{Creator.make<NameType>("Bar"),
+                              Creator.make<NameType>("Foo")};
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<StructuredBindingName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()));
+    Node const *RHS = Creator.make<StructuredBindingName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()));
+
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different bindings
+    Node const *LHS = Creator.make<StructuredBindingName>(
+        Creator.makeNodeArray(Params1.cbegin(), Params1.cend()));
+    Node const *RHS = Creator.make<StructuredBindingName>(
+        Creator.makeNodeArray(Params2.cbegin(), Params2.cend()));
+
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_LiteralOperator) {
+  ManglingNodeCreator Creator;
+
+  auto *Name1 = Creator.make<NameType>("==");
+  auto *Name2 = Creator.make<NameType>("+");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<LiteralOperator>(Name1);
+    Node const *RHS = Creator.make<LiteralOperator>(Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different name
+    Node const *LHS = Creator.make<LiteralOperator>(Name1);
+    Node const *RHS = Creator.make<LiteralOperator>(Name2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_SpecialName) {
+  ManglingNodeCreator Creator;
+
+  auto *Name1 = Creator.make<NameType>("Foo");
+  auto *Name2 = Creator.make<NameType>("Bar");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<SpecialName>("vtable for ", Name1);
+    Node const *RHS = Creator.make<SpecialName>("vtable for ", Name1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different prefix
+    Node const *LHS = Creator.make<SpecialName>("VTT for ", Name1);
+    Node const *RHS = Creator.make<SpecialName>("vtable for ", Name1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different child
+    Node const *LHS = Creator.make<SpecialName>("vtable for ", Name1);
+    Node const *RHS = Creator.make<SpecialName>("vtable for ", Name2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_CtorVtableSpecialName) {
+  ManglingNodeCreator Creator;
+
+  auto *FstType1 = Creator.make<NameType>("Foo");
+  auto *FstType2 = Creator.make<NameType>("Bar");
+
+  auto *SndType1 = Creator.make<NameType>("Baz");
+  auto *SndType2 = Creator.make<NameType>("Quz");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<CtorVtableSpecialName>(FstType1, SndType1);
+    Node const *RHS = Creator.make<CtorVtableSpecialName>(FstType1, SndType1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different first type
+    Node const *LHS = Creator.make<CtorVtableSpecialName>(FstType1, SndType1);
+    Node const *RHS = Creator.make<CtorVtableSpecialName>(FstType2, SndType1);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different second type
+    Node const *LHS = Creator.make<CtorVtableSpecialName>(FstType1, SndType1);
+    Node const *RHS = Creator.make<CtorVtableSpecialName>(FstType1, SndType2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_StringLiteral) {
+  ManglingNodeCreator Creator;
+
+  auto *Type1 = Creator.make<NameType>("std::string");
+  auto *Type2 = Creator.make<NameType>("char const*");
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<itanium_demangle::StringLiteral>(Type1);
+    Node const *RHS = Creator.make<itanium_demangle::StringLiteral>(Type1);
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different type
+    Node const *LHS = Creator.make<itanium_demangle::StringLiteral>(Type1);
+    Node const *RHS = Creator.make<itanium_demangle::StringLiteral>(Type2);
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_EnumLiteral) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<IntegerLiteral>("Enum1", "100");
+    Node const *RHS = Creator.make<IntegerLiteral>("Enum1", "100");
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different type
+    Node const *LHS = Creator.make<IntegerLiteral>("Enum1", "100");
+    Node const *RHS = Creator.make<IntegerLiteral>("Enum2", "100");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different value
+    Node const *LHS = Creator.make<IntegerLiteral>("Enum1", "100");
+    Node const *RHS = Creator.make<IntegerLiteral>("Enum1", "50");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}
+
+TEST(ItaniumDemangle, Equality_FloatLiteral) {
+  ManglingNodeCreator Creator;
+
+  {
+    // Equal
+    Node const *LHS = Creator.make<FloatLiteral>("1.0");
+    Node const *RHS = Creator.make<FloatLiteral>("1.0");
+    ASSERT_TRUE(test_utils::compareNodes(LHS, RHS));
+  }
+
+  {
+    // Different value
+    Node const *LHS = Creator.make<FloatLiteral>("1.0");
+    Node const *RHS = Creator.make<FloatLiteral>("2.0");
+    ASSERT_FALSE(test_utils::compareNodes(LHS, RHS));
+  }
+}

llvm/unittests/Demangle/ItaniumDemangleTestUtils.h

+//===------------------ ItaniumDemangleTestUtils.h ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_DEMANGLE_ITANIUMDEMANGLE_TEST_UTILS_H
+#define LLVM_DEMANGLE_ITANIUMDEMANGLE_TEST_UTILS_H
+
+#include "llvm/Demangle/Demangle.h"
+#include "llvm/Demangle/ItaniumDemangle.h"
+#include "llvm/Demangle/StringView.h"
+#include "llvm/Support/Allocator.h"
+
+#include <vector>
+
+namespace llvm::itanium_demangle::test_utils {
+
+class TestAllocator {
+  BumpPtrAllocator Alloc;
+
+public:
+  void reset() { Alloc.Reset(); }
+
+  template <typename T, typename... Args> T *makeNode(Args &&...args) {
+    return new (Alloc.Allocate(sizeof(T), alignof(T)))
+        T(std::forward<Args>(args)...);
+  }
+
+  void *allocateNodeArray(size_t sz) {
+    return Alloc.Allocate(sizeof(Node *) * sz, alignof(Node *));
+  }
+};
+
+struct ManglingNodeCreator
+    : AbstractManglingParser<ManglingNodeCreator, TestAllocator> {
+
+  ManglingNodeCreator() : AbstractManglingParser(nullptr, nullptr) {}
+
+  auto *makeTemplateArgs(std::vector<Node *> const &Args) {
+    return make<TemplateArgs>(makeNodeArray(Args.cbegin(), Args.cend()));
+  }
+
+  auto *makeQualType(StringView VarName, Qualifiers Quals) {
+    return make<QualType>(make<NameType>(VarName), Quals);
+  }
+
+  auto *makeReferenceType(Qualifiers Quals, StringView ArgName,
+                          ReferenceKind RefKind) {
+    return make<ReferenceType>(makeQualType(ArgName, Quals), RefKind);
+  }
+
+  auto *makeNameWithTemplateArgs(StringView FnName,
+                                 std::vector<Node *> const &Args) {
+    auto *TArgs = makeTemplateArgs(Args);
+    return make<NameWithTemplateArgs>(make<NameType>(FnName), TArgs);
+  }
+
+  auto *makeFunctionEncoding(StringView FnName, std::vector<Node *> const &Args,
+                             Qualifiers CVQuals, FunctionRefQual RefQual) {
+    auto const *NameNode = make<NameType>(FnName);
+    NodeArray Params = makeNodeArray(Args.cbegin(), Args.cend());
+    return make<FunctionEncoding>(nullptr, NameNode, Params, nullptr, CVQuals,
+                                  RefQual);
+  }
+};
+
+inline bool compareNodes(Node const *LHS, Node const *RHS) {
+  return LHS && RHS && LHS->equals(RHS);
+}
+
+} // namespace llvm::itanium_demangle::test_utils
+
+#endif // LLVM_DEMANGLE_ITANIUMDEMANGLE_TEST_UTILS_H