[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

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.

368

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).

424–429

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

llvm/unittests/Demangle/ItaniumDemangleTestUtils.h

1 ↗

(On Diff #451086)

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

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.

368

Will do

424–429

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

[Michael137]

llvm/unittests/Demangle/ItaniumDemangleTestUtils.h

1 ↗

(On Diff #451086)

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

llvm/include/llvm/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)
+      if (!(*IT1)->equals(*IT2))
+        return false;
+
+    return true;
+  }
 };
 
 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;
+  }
 };
 
 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) {
+    return lhs.Suffix == rhs.Suffix && lhs.Prefix->equals(rhs.Prefix);
+  }
 };
 
 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) {
+    return lhs.Ext == rhs.Ext
+           && lhs.Ty->equals(rhs.Ty)
+           && lhs.TA->equals(rhs.TA);
+  }
 };
 
 enum FunctionRefQual : unsigned char {
   FrefQualNone,
   FrefQualLValue,
   FrefQualRValue,
 };
 
 enum Qualifiers {
   QualNone = 0,
   QualConst = 0x1,
   QualVolatile = 0x2,
   QualRestrict = 0x4,
 };
 
 inline Qualifiers operator|=(Qualifiers &Q1, Qualifiers Q2) {
   return Q1 = static_cast<Qualifiers>(Q1 | Q2);
 }
 
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) {
+    return lhs.Quals == rhs.Quals
+           && lhs.Child->equals(rhs.Child);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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) {
+    return lhs.CVQuals == rhs.CVQuals
+           && lhs.RefQual == rhs.RefQual
+           && lhs.Ret->equals(rhs.Ret)
+           && lhs.Name->equals(rhs.Name)
+           && lhs.Params == rhs.Params
+           && lhs.Attrs->equals(rhs.Attrs);
+  }
 };
 
 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) {
+    return lhs.OpName == rhs.OpName;
+  }
 };
 
 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) {
+    return lhs.Special == rhs.Special
+           && lhs.Child->equals(rhs.Child);
+  }
 };
 
 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) {
+    return lhs.FirstType->equals(rhs.FirstType)
+           && lhs.SecondType->equals(rhs.SecondType);
+  }
 };
 
 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) {
+    return lhs.Qual->equals(rhs.Qual)
+           && lhs.Name->equals(rhs.Name);
+  }
 };
 
 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) {
+    if (lhs.IsPartition != rhs.IsPartition)
+      return false;
+
+    if (!!lhs.Parent != !!rhs.Parent)
+      return false;
+
+    if (lhs.Parent)
+      if (!(*lhs.Parent == *rhs.Parent))
+        return false;
+     
+    return lhs.Name->equals(rhs.Name);
+  }
 };
 
 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);
+  }
 };
 
 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) {
+    return lhs.Encoding->equals(rhs.Encoding)
+           && lhs.Entity->equals(rhs.Entity);
+  }
 };
 
 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) {
+    return lhs.Qualifier->equals(rhs.Qualifier)
+           && lhs.Name->equals(rhs.Name);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 /// 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);
+  }
 };
 
 /// 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);
+  }
 };
 
 /// 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;
+  }
 };
 
 /// 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);
+  }
 };
 
 /// 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;
+  }
 };
 
 /// 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;
+  }
 };
 
 /// 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);
+  }
 };
 
 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;
+  }
 };
 
 /// 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:
 ///
struct ForwardTemplateReference : Node {
   Node *Ref = nullptr;
 
   // If we're currently printing this node. It is possible (though invalid) for
   // a forward template reference to refer to itself via a substitution. This
   // creates a cyclic AST, which will stack overflow printing. To fix this, bail
   // out if more than one print* function is active.
   mutable bool Printing = false;
 
+  friend bool operator==(ForwardTemplateReference const& lhs,
+                         ForwardTemplateReference const& rhs) {
+    if (lhs.Index != rhs.Index)
+      return false;
+
+    if (!!lhs.Ref != !!rhs.Ref)
+      return false;
+
+    if (lhs.Ref)
+      if (!lhs.Ref->equals(rhs.Ref))
+        return false;
+
+    // Ignore 'Printing' member
+    return true;
+  }
+
   ForwardTemplateReference(size_t Index_)
       : Node(KForwardTemplateReference, Cache::Unknown, Cache::Unknown,
              Cache::Unknown),
         Index(Index_) {}
 
   // We don't provide a matcher for these, because the value of the node is
   // not determined by its construction parameters, and it generally needs
   // special handling.
struct NameWithTemplateArgs : Node {
   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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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) {
+    return lhs.IsDtor == rhs.IsDtor
+           && lhs.Variant == rhs.Variant
+           && lhs.Basename->equals(rhs.Basename);
+  }
 };
 
 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) {
+    return lhs.Base->equals(rhs.Base);
+  }
 };
 
 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;
+  }
 };
 
 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;
+  }
 };
 
 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;
+  }
 };
 
 // -- 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& lhs,
+                         BinaryExpr const& rhs) {
+    return lhs.InfixOperator == rhs.InfixOperator
+           && lhs.LHS->equals(rhs.LHS)
+           && lhs.RHS->equals(rhs.RHS);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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& lhs,
+                         MemberExpr const& rhs) {
+    return lhs.Kind == rhs.Kind
+           && lhs.LHS->equals(rhs.LHS)
+           && lhs.RHS->equals(rhs.RHS);
+  }
 };
 
 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;
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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;
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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;
+  }
 };
 
 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);
+  }
 };
 
 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) {
+    return lhs.Ty->equals(rhs.Ty)
+           && lhs.Inits == rhs.Inits;
+  }
 };
 
 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);
+  }
 };
 
 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);
+  }
 };
 
 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) {
+    return lhs.IsLeftFold == rhs.IsLeftFold
+           && lhs.OperatorName == rhs.OperatorName
+           && lhs.Pack->equals(rhs.Pack)
+           && lhs.Init->equals(rhs.Init);
+  }
 };
 
 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);
+  }
 };
 
 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;
+  }
 };
 
 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) {
+    return lhs.Type->equals(rhs.Type);
+  }
 };
 
 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);
+  }
 };
 
 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) {
+    return lhs.Integer == rhs.Integer
+           && lhs.Ty->equals(rhs.Ty);
+  }
 };
 
 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;
+  }
 };
 
 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;
+  }
 };
 
 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/lib/Demangle/ItaniumDemangle.cpp

if (*first == '_') {
         ;
       if (t1 == last)
         first = last;
     }
   }
   return first;
 }
 
+bool 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 "llvm/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;