Big Ball of Mud

Testing Equality

with one comment

Equality in .NET is one of the most basic and usually harder to grasp concepts. While much has been written about implementing Equals and GetHashCode contracts, it is usually quite difficult to test all cases which can be broken when providing your own implementation.

First let’s see what can MSDN says about requirements for implementing Equals:

The following statements must be true for all implementations of the Equals method. In the list, x, y, and z represent object references that are not null.

• x.Equals(x) returns true (…)
• x.Equals(y) returns the same value as y.Equals(x). (…)
• (x.Equals(y) && y.Equals(z)) returns true if and only if x.Equals(z) returns true.
• Successive calls to x.Equals(y) return the same value as long as the objects referenced by x and y are not modified.
• x.Equals(a null reference) returns false.

http://msdn.microsoft.com/en-us/library/bsc2ak47.aspx

While it has been a while since I was in school, this sounds somewhat familiar:

Let A be a set and ~ be a binary relation on A. ~ is called an equivalence relation if and only if for all a,b,c in A, all the following holds true:

• Reflexivity: a ~ a
• Symmetry: if a ~ b then b ~ a
• Transitivity: if a ~ b and b ~ c then a ~ c.

http://en.wikipedia.org/wiki/Equivalence_relation

Right! The infamous Equals contract is just a definition of equivalence relation with some additional conditions: consistency and right-side null behaviour. Let’s try to put this ideas into code (and yes, I know consistency implementation is very naive):

`    4 public class EqualityConditions`
`    5 {`
`    6     private const int MaxConsistencyChecks = 5;`
`    7`
`    8     public static bool RelationIsReflexive<T>(T x)`
`    9         where T : class`
`   10     {`
`   11         return Equals(x, x);`
`   12     }`
`   13`
`   14     public static bool RelationIsSymmetric<T>(T x, T y)`
`   15         where T : class`
`   16     {`
`   17         return Equals(x, y) == Equals(y, x);`
`   18     }`
`   19`
`   20     public static bool RelationIsTransitive<T>(T x, T y, T z)`
`   21         where T : class`
`   22     {`
`   23         if (Equals(x, y) && Equals(y, z))`
`   24             return Equals(x, z);`
`   25`
`   26         return true;`
`   27     }`
`   28`
`   29     public static bool RelationIsConsistent<T>(T x, T y)`
`   30         where T : class`
`   31     {`
`   32         bool result = Equals(x, y);`
`   33         for (int i = 1; i < MaxConsistencyChecks; i++)`
`   34         {`
`   35             if (Equals(x, y) != result) return false;`
`   36         }`
`   37         return true;`
`   38     }`
`   39`
`   40     public static bool RelationIsFalseForRightSideNull<T>(T x)`
`   41         where T : class`
`   42     {`
`   43         if (x == null) return true;`
`   44         return !x.Equals(null);`
`   45     }`
`   46 }`

While this can be useful, there is one more interesting thing about the equivalence relation – it defines how the set of values can be divided into something called equivalence classes: groups of elements which are in relation with each other. What is more important, the if we divide any set into disjoint subsets, in such way that each element belongs to exactly one subset, this division generates the equivalence relation for us (see this for more accurate description). If by implementing Equals we define the relation in one way, the second way by defining it with subsets can be useful to test if our implementation is correct. Now with previous conditions defined, we can try to write some little framework to help us. Give it an interesting API, add some generics magic and voila! Let me give you an example.

Let’s assume we have defined a simple Name class which is a value object in our domain, encapsulating all name strings. This class has an Equals method implemented in standard way:

`    1 public class Name`
`    2 {`
`    3     public string Value { get; private set; }`
`    4`
`    5     public Name(string name)`
`    6     {`
`    7         if (string.IsNullOrEmpty(name)) throw new ArgumentException();`
`    8         Value = name;`
`    9     }`
`   10`
`   11     public override bool Equals(object obj)`
`   12     {`
`   13         if (ReferenceEquals(this, obj)) return true;`
`   14         if (obj == null || GetType() != obj.GetType())`
`   15         {`
`   16             return false;`
`   17         }`
`   18         var otherName = (Name)obj;`
`   19         return Value == otherName.Value;`
`   20     }`
`   21 }`

Now let’s test its Equals method by providing some examples (I used NUnit):

`    1 [TestFixture]`
`    2 public class NameTests`
`    3 {`
`    4     [Test]`
`    5     public void Verify_Equals_implementation()`
`    6     {`
`    7         Name nullReference = null;`
`    8         Name name1 = new Name("Name");`
`    9         Name name1_copy = new Name("Name");`
`   10         Name name2 = new Name("other Name");`
`   11         Name name1_Derrived = new NameDerrived("Name");`
`   12         Name name1_Derrived_copy = new NameDerrived("Name");`
`   13         Name name2_Derrived = new NameDerrived("other Name");`
`   14`
`   15         new EqualityTestRunner<Name>(`
`   16             Eq.Class(nullReference),`
`   17             Eq.Class(name1, name1_copy),`
`   18             Eq.Class(name2),`
`   19             Eq.Class(name1_Derrived, name1_Derrived_copy),`
`   20             Eq.Class(name2_Derrived)`
`   21             ).Run();`
`   22     }`
`   23`
`   24     class NameDerrived : Name {`
`   25         public NameDerrived(string name) : base(name)`
`   26         {`
`   27         }`
`   28     }`
`   29 }`

How are the classes defined? These are example of values, which if belong to the same group, should equal each other (in terms of Equals method). Any pair of elements from different groups should not equal each other.

So what should be tested here. First of all we should check if our relation is really an equivalence using conditions from EqualityConditions class. Then we can check if the relation defined by Equals matches the examples, by comparing each pair and checking if pair equality correspond to defined sets. Enough said, let’s see some code:

`    6 public class EqualityTestRunner<T> where T : class`
`    7 {`
`    8     private readonly EqualityClass<T>[] _equalityClasses;`
`    9`
`   10     public EqualityTestRunner(params EqualityClass<T>[] equalityClasses)`
`   11     {`
`   12         _equalityClasses = equalityClasses;`
`   13     }`
`   14`
`   15     public void Run()`
`   16     {`
`   17         foreach (var equalityClass in _equalityClasses)`
`   18         {`
`   19             equalityClass.AreEqualWithinClass();`
`   20             equalityClass.AreNotEqualWithOtherClassesMembers(_equalityClasses);`
`   21         }`
`   22         TestEqualityContractConditions(_equalityClasses);`
`   23     }`
`   24`
`   25     private static void TestEqualityContractConditions(IEnumerable<EqualityClass<T>> equalityClasses)`
`   26     {`
`   27         var allExamples = from equalityClass in equalityClasses`
`   28                           from example in equalityClass`
`   29                           select example;`
`   30         TestEqualityContractConditions(allExamples);`
`   31     }`
`   32`
`   33`
`   34     private static void TestEqualityContractConditions(IEnumerable<T> examples)`
`   35     {`
`   36         foreach (var first in examples)`
`   37         {`
`   38             EqualityTests<T>.IsReflective(first);`
`   39             EqualityTests<T>.IsFalseForRightSideNull(first);`
`   40`
`   41             foreach (var second in examples)`
`   42             {`
`   43                 EqualityTests<T>.IsSymmetric(first, second);`
`   44                 EqualityTests<T>.IsConsistent(first, second);`
`   45`
`   46                 foreach (var third in examples)`
`   47                 {`
`   48                     EqualityTests<T>.IsTransitive(first, second, third);`
`   49                 }`
`   50             }`
`   51         }`
`   52     }`
`   53 }`

Now the EqualityClass:

`    7 public class EqualityClass<T> : IEnumerable<T> where T : class`
`    8 {`
`    9     private readonly T[] _examples;`
`   10`
`   11     public EqualityClass(T[] examples)`
`   12     {`
`   13         _examples = examples;`
`   14     }`
`   15`
`   16     public void AreEqualWithinClass()`
`   17     {`
`   18         foreach (var first in _examples)`
`   19             foreach (var second in _examples)`
`   20             {`
`   21                 EqualityTests<T>.AreEqual(first, second);`
`   22             }`
`   23     }`
`   24`
`   25     public void AreNotEqualWithOtherClassesMembers(EqualityClass<T>[] equalityClasses)`
`   26     {`
`   27         foreach (var otherClass in equalityClasses)`
`   28         {`
`   29             if (otherClass == this) continue;`
`   30`
`   31             foreach (var exampleFromEqualityClass in _examples)`
`   32             {`
`   33                 foreach (var exampleFromOtherClass in otherClass._examples)`
`   34                 {`
`   35                     EqualityTests<T>.AreNotEqual(exampleFromEqualityClass, exampleFromOtherClass);`
`   36                 }`
`   37             }`
`   38         }`
`   39     }`
`   40`
`   41     public IEnumerator<T> GetEnumerator()`
`   42     {`
`   43         foreach (var example in _examples)`
`   44         {`
`   45             yield return example;`
`   46         }`
`   47     }`
`   48`
`   49     IEnumerator IEnumerable.GetEnumerator()`
`   50     {`
`   51         return GetEnumerator();`
`   52     }`
`   53 }`
`   54`
`   55 public static class Eq`
`   56 {`
`   57     public static EqualityClass<T> Class<T>(params T[] examples) where T : class`
`   58     {`
`   59         return new EqualityClass<T>(examples);`
`   60     }`
`   61 }`

And tests which are performed by Runner:

`    5 public static class EqualityTests<T>`
`    6     where T : class`
`    7 {`
`    8     public static void IsReflective(T x)`
`    9     {`
`   10         Assert.IsTrue(EqualityConditions.RelationIsReflexive(x),`
`   11                       string.Format("Relation is not reflective. x: {0}",`
`   12                                     x == null ? "null" : x.ToString())`
`   13             );`
`   14     }`
`   15`
`   16     public static void IsSymmetric(T x, T y)`
`   17     {`
`   18         Assert.IsTrue(EqualityConditions.RelationIsSymmetric(x, y),`
`   19                       string.Format("Relation is not symmetric. x: {0} y: {1}",`
`   20                                     x == null ? "null" : x.ToString(),`
`   21                                     y == null ? "null" : y.ToString())`
`   22             );`
`   23     }`
`   24`
`   25     public static void IsTransitive(T x, T y, T z)`
`   26     {`
`   27         Assert.IsTrue(EqualityConditions.RelationIsTransitive(x, y, z),`
`   28                       string.Format(`
`   29                           "Relation is not transitive. x: {0} y: {1}, z: {2}",`
`   30                           x == null ? "null" : x.ToString(),`
`   31                           y == null ? "null" : y.ToString(),`
`   32                           z == null ? "null" : z.ToString())`
`   33             );`
`   34     }`
`   35`
`   36     public static void IsConsistent(T x, T y)`
`   37     {`
`   38         Assert.IsTrue(EqualityConditions.RelationIsConsistent(x, y),`
`   39                       string.Format(`
`   40                           "Relation is not consistent. x: {0} y: {1}",`
`   41                           x == null ? "null" : x.ToString(),`
`   42                           y == null ? "null" : y.ToString())`
`   43             );`
`   44`
`   45     }`
`   46`
`   47     public static void IsFalseForRightSideNull(T x)`
`   48     {`
`   49         Assert.IsTrue(EqualityConditions.RelationIsFalseForRightSideNull(x),`
`   50                       string.Format(`
`   51                           "Relation is not false for null as right side parameter. x: {0}",`
`   52                           x == null ? "null" : x.ToString())`
`   53             );`
`   54     }`
`   55`
`   56     public static void AreEqual(T x, T y)`
`   57     {`
`   58         if (x != null)`
`   59         {`
`   60             Assert.IsTrue(x.Equals(y),`
`   61                           string.Format("Parameters should be equal, while: x != y    x: {0} y: {1}", x, y));`
`   62         }`
`   63`
`   64         if (y != null)`
`   65         {`
`   66             Assert.IsTrue(y.Equals(x),`
`   67                           string.Format("Parameters should be equal, while: y != x    x: {0} y: {1}", x, y));`
`   68         }`
`   69     }`
`   70`
`   71     public static void AreNotEqual(T x, T y)`
`   72     {`
`   73         if (x != null)`
`   74         {`
`   75             Assert.IsFalse(x.Equals(y),`
`   76                            string.Format("Parameters should not be equal, while: x == y    x: {0} y: {1}", x, y));`
`   77         }`
`   78`
`   79         if (y != null)`
`   80         {`
`   81             Assert.IsFalse(y.Equals(x),`
`   82                            string.Format("Parameters should not be equal, while: y == x    x: {0} y: {1}", x, y));`
`   83         }`
`   84     }`
`   85 }`

Of course this is just a concept, it does not test GetHashCode implementation at all, and if the Equals method is broken, it is somewhat difficult to find the cause.

Written by bigballofmud

2009/03/18 at 10:47 pm

Posted in C#