Value equalities and circular references: how to allow infinite recursion?

Question

I have several classes that contain multiple fields. I need to compare them by value, i.e. Two instances of a class are equal if their fields contain the same data. I overridden the GetHashCode and Equals methods for this.

Perhaps these classes contain circular references.

Example: We want to model institutions (e.g. government, sports clubs, whatever). The institution has a name. A Club is an institution that has a name and a list of members. Each member of Person who has a name and a favorite institution. If a member of a certain club has this club as their favorite institution, we have a round link.

But circular links combined with equality of value lead to infinite recursion. Here is a sample code:

 interface IInstitution { string Name { get; } } class Club : IInstitution { public string Name { get; set; } public HashSet<Person> Members { get; set; } public override int GetHashCode() { return Name.GetHashCode() + Members.Count; } public override bool Equals(object obj) { Club other = obj as Club; if (other == null) return false; return Name.Equals(other.Name) && Members.SetEquals(other.Members); } } class Person { public string Name { get; set; } public IInstitution FavouriteInstitution { get; set; } public override int GetHashCode() { return Name.GetHashCode(); } public override bool Equals(object obj) { Person other = obj as Person; if (other == null) return false; return Name.Equals(other.Name) && FavouriteInstitution.Equals(other.FavouriteInstitution); } } class Program { public static void Main() { Club c1 = new Club { Name = "myClub", Members = new HashSet<Person>() }; Person p1 = new Person { Name = "Johnny", FavouriteInstitution = c1 } c1.Members.Add(p1); Club c2 = new Club { Name = "myClub", Members = new HashSet<Person>() }; Person p2 = new Person { Name = "Johnny", FavouriteInstitution = c2 } c2.Members.Add(p2); bool c1_and_c2_equal = c1.Equals(c2); // StackOverflowException! // c1.Equals(c2) calls Members.SetEquals(other.Members) // Members.SetEquals(other.Members) calls p1.Equals(p2) // p1.Equals(p2) calls c1.Equals(c2) } } 

c1_and_c2_equal should return true , and in fact we (people) can see that they are equal in value with a small amount of thinking, without starting into infinite recursion. However, I cannot say how we understand this. But since it is possible, I hope there is a way to solve this problem in the code too!

So the question is: How do I check if values ​​are equal without using infinite recursions?

Please note that I need to allow circular references in general, and not just the case above. I will call it 2-circle, since c1 links p1 and p1 links c1 . There may be other n-circles, for example. if club A has a member M whose favorite club B has member N whose favorite club is A That would be 4 laps. Other object models may also allow n-circles with odd numbers n. I am looking for a way to solve all these problems at once, since I will not know in advance what value n can have.

Answer 1

In the general case that interests me

- where we have the classes C1 , ..., Cn , where each of these classes can have any number of VALUES (for example, int , string , ...), as well as any number of REFERENCES to any other classes C1 , .. ., Cn (for example, if for each type of Ci field ICollection<Ci> ) is

the question "Are two objects A and B equal?" in the sense of the equality described here

seems to be EQUIVALENT for

the question "For two finite, directed, connected, colored graphs G and H there an isomorphism from G to H ?" .

Here is the equivalence:

• vertices of the graph correspond to object (class instances) Graphs
• match object s links Color
• corresponds to a conglomeration of values ​​and the type itself (i.e., the colors of two vertices are the same if their corresponding object have the same type and the same values)

This is an NP-hard question, so I think I will abandon my plan to implement this and move on using the method without a link.

Answer 2

A simple workaround (used in the DBMS) is to use a unique Id to identify Person (of any type). Then you do not need to compare every other property, and you never come across such reference links.

Another way is to compare differently in Equals , so give in-depth validation only for the Equals type and not for reference types. You can use a custom resolver:

 public class PersonNameComparer : IEqualityComparer<Person> { public bool Equals(Person x, Person y) { if (x == null && y == null) return true; if (x == null || y == null) return false; if(object.ReferenceEquals(x, y)) return true; return x.Name == y.Name; } public int GetHashCode(Person obj) { return obj?.Name?.GetHashCode() ?? int.MinValue; } } 

Now you can change the implementation of Equals Club to avoid Members using their in-depth verification, which includes the institution, but only their Name :

 public override bool Equals(object obj) { if (Object.ReferenceEquals(this, obj)) return true; Club other = obj as Club; if (other == null) return false; var personNameComparer = new PersonNameComparer(); return Name.Equals(other.Name) && Members.Count == other.Members.Count && !Members.Except(other.Members, personNameComparer).Any(); } 

You noticed that I cannot use SetEquals because there is no overload for my custom comparator.

Answer 3

Following Dryadwoods suggestion, I have modified the Equals methods so that I can track elements that have already been mapped.

First, we need an equality mapper that checks reference equality for the corresponding elements of pairs:

 public class ValuePairRefEqualityComparer<T> : IEqualityComparer<(T,T)> where T : class { public static ValuePairRefEqualityComparer<T> Instance = new ValuePairRefEqualityComparer<T>(); private ValuePairRefEqualityComparer() { } public bool Equals((T,T) x, (T,T) y) { return ReferenceEquals(x.Item1, y.Item1) && ReferenceEquals(x.Item2, y.Item2); } public int GetHashCode((T,T) obj) { return RuntimeHelpers.GetHashCode(obj.Item1) + 2 * RuntimeHelpers.GetHashCode(obj.Item2); } } 

And here is the modified Equals Club method:

 static HashSet<(Club,Club)> checkedPairs = new HashSet<(Club,Club)>(ValuePairRefEqualityComparer<Club>.Instance); public override bool Equals(object obj) { Club other = obj as Club; if (other == null) return false; if (!Name.Equals(other.Name)) return; if (checkedPairs.Contains((this,other)) || checkedPairs.Contains((other,this))) return true; checkedPairs.Add((this,other)); bool membersEqual = Members.SetEquals(other.Members); checkedPairs.Clear(); return membersEqual; } 

The version for Person similar. Note that I add (this,other) to checkedPairs and check if (this,other) or (other,this) contained, because it may happen that after the first call to c1.Equals(c2) we get a call to c2.Equals(c1) instead of c1.Equals(c2) . I'm not sure if this is really happening, but since I don't see the implementation of SetEquals , I believe that this is possible.

Since I am not happy with using a static field for already verified pairs (it will not work if the program is parallel!), I asked one more question: make the variable last for the call stack .