c# - Comparing two objects by iterating recursively through all the properties' properties?

Question

I've written a test method for comparison between two instances of a class (the assumption of type compatibility is given). Proudly I checked all the public properties making sure to return a list of discrepancies.

The problem is that some of the properties are objects containing their own properties (sub-properties, if you will). Those are not being compared, as far I can see by stepping through the process flow.

How can I design a call that goes in on-depth and compares all sub-properties? Extra bonus if the approach is relatively simple. :)

public static class Extensions
{
  public static IEnumerable<string> DiffersOn<Generic>(
    this Generic self, Generic another) where Generic : class
  {
    if (self == null || another == null)
      yield return null;

    Type type = typeof(Generic);
    IEnumerable<PropertyInfo> properties = type.GetProperties(
      BindingFlags.Public | BindingFlags.Instance);

    foreach (PropertyInfo property in properties)
    {
      var selfie = type.GetProperty(property.Name).GetValue(self);
      var othie = type.GetProperty(property.Name).GetValue(another);
      if (selfie != othie && (selfie == null || !selfie.Equals(othie)))
        yield return property.Name;
    }
  }
}

Answer 1

As I said in comment easiest way is to use BinaryFormatter to serialize both objects and compare raw byte[] streams. With that you'll compare fields (and not properties) so things may be different (two objects may be compared as logically equal even if their private fields are different). Biggest advantage is that serialization will handle a very tricky case: when objects have circular references.

Roughly something like this:

static bool CheckForEquality(object a, object b)
{
    BinaryFormatter formatter = new BinaryFormatter();

    using (MemoryStream streamA = new MemoryStream())
    using (MemoryStream streamB = new MemoryStream())
    {
        formatter.Serialize(streamA, a);
        formatter.Serialize(streamB, b);

        if (streamA.Length != streamB.Length)
            return false;

        streamA.Seek(0, SeekOrigin.Begin);
        streamB.Seek(0, SeekOrigin.Begin);

        for (int value = 0; (value = streamA.ReadByte()) >= 0; )
        {
            if (value != streamB.ReadByte())
                return false;
        }

        return true;
    }
}

As pointed out by Ben Voigt in a comment this algorithm to compare streams is pretty slow, for a fast buffer comparison (MemoryStream keeps data in a byte[] buffer) see this post he suggested.

If you need more "control" and actually handle custom comparison then you have to make things more complicated. Next sample is first raw (and untested!) version of this comparison. It doesn't handle a very important thing: circular references.

static bool CheckForEquality(object a, object b)
{
    if (Object.ReferenceEquals(a, b))
        return true;

    // This is little bit arbitrary, if b has a custom comparison
    // that may equal to null then this will bypass that. However
    // it's pretty uncommon for a non-null object to be equal
    // to null (unless a is null and b is Nullable<T>
    // without value). Mind this...
    if (Object.ReferenceEquals(a, null)
        return false; 

    // Here we handle default and custom comparison assuming
    // types are "well-formed" and with good habits. Hashcode
    // checking is a micro optimization, it may speed-up checking
    // for inequality (if hashes are different then we may safely
    // assume objects aren't equal...in "well-formed" objects).
    if (!Object.ReferenceEquals(b, null) && a.GetHashCode() != b.GetHashCode())
        return false;

    if (a.Equals(b))
        return true;

    var comparableA = a as IComparable;
    if (comparableA != null)
        return comparableA.CompareTo(b) == 0;

    // Different instances and one of them is null, they're different unless
    // it's a special case handled by "a" object (with IComparable).
    if (Object.ReferenceEquals(b, null))
        return false;

    // In case "b" has a custom comparison for objects of type "a"
    // but not vice-versa.
    if (b.Equals(a))
        return true; 

    // We assume we can compare only the same type. It's not true
    // because of custom comparison operators but it should also be
    // handled in Object.Equals().
    var type = a.GetType();
    if (type != b.GetType())
        return false;

    // Special case for lists, they won't match but we may consider
    // them equal if they have same elements and each element match
    // corresponding one in the other object.
    // This comparison is order sensitive so A,B,C != C,B,A.
    // Items must be first ordered if this isn't what you want.
    // Also note that a better implementation should check for
    // ICollection as a special case and IEnumerable should be used.
    // An even better implementation should also check for
    // IStructuralComparable and IStructuralEquatable implementations.
    var listA = a as System.Collections.ICollection;
    if (listA != null)
    {
        var listB = b as System.Collections.ICollection;

        if (listA.Count != listB.Count)
            return false;

        var aEnumerator = listA.GetEnumerator();
        var bEnumerator = listB.GetEnumerator();

        while (aEnumerator.MoveNext() && bEnumerator.MoveNext())
        {
            if (!CheckForEquality(aEnumerator.Current, bEnumerator.Current))
                return false;
        }

        // We don't return true here, a class may implement IList and also have
        // many other properties, go on with our comparison
    }

    // If we arrived here we have to perform a property by
    // property comparison recursively calling this function.
    // Note that here we check for "public interface" equality.
    var properties = type.GetProperties().Where(x => x.GetMethod != null);
    foreach (var property in properties)
    {
        if (!CheckForEquality(property.GetValue(a), property.GetValue(b)))
            return false;
    }

    // If we arrived here then objects can be considered equal
    return true;
}

If you strip out comments you'll have pretty short code. To handle circular references you have to avoid to compare again and again same tuple, to do that you have to split function like in this example (very very naive implementation, I know):

static bool CheckForEquality(object a, object b)
{
    return CheckForEquality(new List<Tuple<object, object>>(), a, b);
}

With core implementation like this (I rewrite only important part):

static bool CheckForEquality(List<Tuple<object, object>> visitedObjects, 
                             object a, object b)
{
    // If we compared this tuple before and we're still comparing
    // then we can consider them as equal (or irrelevant).
    if (visitedObjects.Contains(Tuple.Create(a, b)))
        return true;

    visitedObjects.Add(Tuple.Create(a, b));

    // Go on and pass visitedObjects to recursive calls
}

Next step is little bit more complicate (get the list of different properties) because it may not be such simple (for example if two properties are lists and they have different number of items). I'll just sketch a possible solution (removing code for circular references for clarity). Note that when equality breaks then subsequent checks may also produce unexpected exceptions so it should be implemented much better than this.

New prototype will be:

static void CheckForEquality(object a, object b, List<string> differences)
{
     CheckForEquality("", a, b, differences);
}

And implementation method will also need to keep track of "current path":

static void CheckForEquality(string path,
                             object a, object b, 
                             List<string> differences)
{
    if (a.Equals(b))
        return;

    var comparableA = a as IComparable;
    if (comparableA != null && comparableA.CompareTo(b) != 0)
        differences.Add(path);

    if (Object.ReferenceEquals(b, null))
    {
        differences.Add(path);
        return; // This is mandatory: nothing else to compare
    }

    if (b.Equals(a))
        return true;

    var type = a.GetType();
    if (type != b.GetType())
    {
        differences.Add(path);
        return; // This is mandatory: we can't go on comparing different types
    }

    var listA = a as System.Collections.ICollection;
    if (listA != null)
    {
        var listB = b as System.Collections.ICollection;

        if (listA.Count == listB.Count)
        {
            var aEnumerator = listA.GetEnumerator();
            var bEnumerator = listB.GetEnumerator();

            int i = 0;
            while (aEnumerator.MoveNext() && bEnumerator.MoveNext())
            {
                CheckForEquality(
                    String.Format("{0}[{1}]", path, i++),
                    aEnumerator.Current, bEnumerator.Current, differences);
            }
        }
        else
        {
            differences.Add(path);
        }
    }

    var properties = type.GetProperties().Where(x => x.GetMethod != null);
    foreach (var property in properties)
    {
        CheckForEquality(
            String.Format("{0}.{1}", path, property.Name),
            property.GetValue(a), property.GetValue(b), differences);
    }
}