# Equality Function Generator

I have a small open source library called Equ that I've been using already on several projects. After a rework of the internals I thought I'd ask here for opinions on improvement possibilities.

At the core of my library is a class that generates equality functions, i.e. bool Equals<T>(T a, T b) and int GetHashCode<T>(T obj).

It takes a type and a set of MemberInfo objects that define which members (properties or fields) should be included in the equality functions. The class generates a Func as output for each of Equals() and GetHashCode() using expression trees. The idea behind this approach is that the slow reflection code needs to be run only once per type, using the resulting lambdas as sort of a cache for the code.

Here's the code of the central class of the library, EqualityFunctionGenerator. This is a copy of this.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using System.Linq.Expressions;
using System.Reflection;

public class EqualityFunctionGenerator
{
private static readonly MethodInfo _objectEqualsMethod = typeof(object).GetMethod("Equals", BindingFlags.Static | BindingFlags.Public);

public EqualityFunctionGenerator(Type type, Func<Type, IEnumerable<FieldInfo>> fieldSelector, Func<Type, IEnumerable<PropertyInfo>> propertySelector)
{
_type = type;
_fieldSelector = fieldSelector;
_propertySelector = propertySelector;
}

public Func<object, int> MakeGetHashCodeMethod()
{
var objRaw = Expression.Parameter(typeof(object), "obj");

// cast to the concrete type
var objParam = Expression.Convert(objRaw, _type);

// compound XOR expression
var getHashCodeExprs = GetIncludedMembers(_type).Select(p => MakeGetHashCodeExpression(p.Item1, p.Item2, objParam));

return Expression.Lambda<Func<object, int>>(xorChainExpr, objRaw).Compile();
}

public Func<object, object, bool> MakeEqualsMethod()
{
var leftRaw = Expression.Parameter(typeof(object), "left");
var rightRaw = Expression.Parameter(typeof(object), "right");

// cast to the concrete type
var leftParam = Expression.Convert(leftRaw, _type);
var rightParam = Expression.Convert(rightRaw, _type);

// compound AND expression using short-circuit evaluation
var equalsExprs = GetIncludedMembers(_type).Select(p => MakeEqualsExpression(p.Item1, p.Item2, leftParam, rightParam));
var andChainExpr = equalsExprs.Aggregate((Expression)Expression.Constant(true), Expression.AndAlso);

// call Object.Equals if second parameter doesn't match type
var objectEqualsExpr = Expression.Equal(leftRaw, rightRaw);
var useTypedEqualsExpression = Expression.Condition(
Expression.TypeIs(rightRaw, _type),
andChainExpr,
objectEqualsExpr);

return Expression.Lambda<Func<object, object, bool>>(useTypedEqualsExpression, leftRaw, rightRaw).Compile();
}

private IEnumerable<Tuple<MemberInfo, Type>> GetIncludedMembers(Type type)
{
var selectedFields = _fieldSelector(type).Select(f => Tuple.Create((MemberInfo)f, f.FieldType));
var selectedProperties = _propertySelector(type).Select(f => Tuple.Create((MemberInfo)f, f.PropertyType));

return selectedFields.Concat(selectedProperties);
}

private static Expression LinkHashCodeExpression(Expression left, Expression right)
{
var leftMultiplied = Expression.Multiply(left, Expression.Constant(486187739));
return Expression.ExclusiveOr(leftMultiplied, right);
}

private static Expression MakeEqualsExpression(MemberInfo member, Type memberType, Expression left, Expression right)
{
var leftMemberExpr = Expression.MakeMemberAccess(left, member);
var rightMemberExpr = Expression.MakeMemberAccess(right, member);

if (memberType.IsValueType)
{
return MakeValueTypeEqualExpression(leftMemberExpr, rightMemberExpr);
}
if (IsSequenceType(memberType))
{
return MakeSequenceTypeEqualExpression(leftMemberExpr, rightMemberExpr, memberType);
}
return MakeReferenceTypeEqualExpression(leftMemberExpr, rightMemberExpr);
}

private static Expression MakeValueTypeEqualExpression(Expression left, Expression right)
{
return Expression.Equal(left, right);
}

private static Expression MakeSequenceTypeEqualExpression(Expression left, Expression right, Type enumerableType)
{
return MakeCallOnSequenceEqualityComparerExpression("Equals", enumerableType, left, right);
}

private static Expression MakeReferenceTypeEqualExpression(Expression left, Expression right)
{
return Expression.Call(_objectEqualsMethod, left, right);
}

private static Expression MakeGetHashCodeExpression(MemberInfo member, Type memberType, UnaryExpression obj)
{
var memberAccessExpr = Expression.MakeMemberAccess(obj, member);
var memberAccessAsObjExpr = Expression.Convert(memberAccessExpr, typeof(object));

var getHashCodeExpr = IsSequenceType(memberType)
? MakeCallOnSequenceEqualityComparerExpression("GetHashCode", memberType, memberAccessExpr)
: Expression.Call(memberAccessAsObjExpr, "GetHashCode", Type.EmptyTypes);

return Expression.Condition(
Expression.ReferenceEqual(Expression.Constant(null), memberAccessAsObjExpr), // If member is null
Expression.Constant(0), // Return 0
getHashCodeExpr); // Return the actual getHashCode call
}

private static Expression MakeCallOnSequenceEqualityComparerExpression(string methodName, Type enumerableType, params Expression[] parameterExpressions)
{
var comparerType = typeof(ElementwiseSequenceEqualityComparer<>).MakeGenericType(enumerableType);
var comparerInstance = comparerType.GetProperty("Default", BindingFlags.Static | BindingFlags.Public).GetValue(null);
var comparerExpr = Expression.Constant(comparerInstance);

return Expression.Call(comparerExpr, methodName, Type.EmptyTypes, parameterExpressions);
}

private static bool IsSequenceType(Type type)
{
return typeof(IEnumerable).IsAssignableFrom(type) && type != typeof(string);
}
}


The referenced ElementwiseSequenceEqualityComparer is basically just a wrapper around Enumerable.SequenceEqual(). It can be found here.

I'm especially interested in opportunities to further improve performance and simplicity. And, of course, if you see any problem with my approach or implementation, that would be great to know as well.

## Edit: Usage Details

The primary use case of Equ is with value objects, where usually all members participate in the equality comparison. This use case is covered by MemberwiseEquatable and makes it very simple for clients, because all fields are captured, even when the value object class is changed later.

Under the hood, MemberwiseEquatable uses the EqualityFunctionGenerator shown above. Clients can also use the EqualityFunctionGenerator directly when they need more control over the exact members that participate in equality comparison.

-
Have you considered supporting IComparable<T> too? –  svick Jul 15 '14 at 13:14
@svick I thought about that as well, but I think that's conceptually not as easy as it might seem at first sight. With equality, it is simple - two value objects are equal when all their parts are equal. But what should a a.CompareTo(b) method return, when a.Part1 > b.Part1 and a.Part2 < b.Part2? –  theDmi Jul 15 '14 at 13:21
With IComparable, order matters: you compare the objects by Part1 first and only if they're equal, you look at Part2 (in other words, you're basically doing .OrderBy(x => x.Part1).ThenBy(x => x.Part2)). Because of this, I think it makes sense to support only explicit member lists for this (no “compare by all fields”). –  svick Jul 15 '14 at 13:25
@svick Exactly, and as a result, the main "selling point" of my library (i.e. not having to explicitly list members, see github.com/thedmi/Equ#simple-scenarios) would be defeated. But I agree that this would be a useful addition! Pull requests welcome, btw :-) –  theDmi Jul 15 '14 at 13:37
If my understanding is correct (and it really could not be :P) you compare each member and properties of your object to test the equality? –  TopinFrassi Jul 15 '14 at 14:24

You should add XML comments, especially for important items (like EqualityFunctionGenerator) and potentially confusing items (like fieldSelector).

typeof(object).GetMethod("Equals", BindingFlags.Static | BindingFlags.Public)


Safer way to do this would be to create a delegate for object.Equals() and then take its Method:

new Func<object, object, bool>(object.Equals).Method


equalsExprs.Aggregate((Expression)Expression.Constant(true), Expression.AndAlso)


You don't need to use seed here, this will work too:

equalsExprs.Aggregate(Expression.AndAlso)


var objectEqualsExpr = Expression.Equal(leftRaw, rightRaw);


This won't work if the type also overloads == by delegating to Equals() (which is the most reasonable implementation). Instead, I think you should just return false when the types don't match.

Expression.TypeIs(rightRaw, _type)


This doesn't actually check whether the type of rightRaw is _type, it checks whether it's _type or a type derived from _type (just like is does in C#). Here, I think you want to know whether the type is exactly _type. You can do this by calling GetType() (and don't forget to add a null check before doing that).

private static Expression MakeEqualsExpression(MemberInfo member, Type memberType, Expression left, Expression right)


You don't need the memberType parameter here, you can use leftMemberExpr.Type instead.

This means you can get rid of the Tuple in GetIncludedMembers() and return just the MemberInfo.

private static Expression MakeGetHashCodeExpression(MemberInfo member, Type memberType, UnaryExpression obj)


I don't see any reason why obj should be a UnaryExpression, you should use Expression here.

-
Wow, thank you very much for your inputs! I didn't know the Method member of Func and that Expression has a Type property. –  theDmi Jul 16 '14 at 6:37

I believe you shouldn't compare all members and properties. Lets say your object has an ID property that defines the identity of your object, you might not want to compare all your fields/properties knowing that comparing only one is enough. Or if you are using an ORM and that not all your navigation properties are loaded, your objects wouldn't be equal even though they "are".

As a solution, I think you could put attributes to the properties/fields that define the equality of your object, something like this

public class MyClass
{
[EqualityMember]
public int PropertyThatWillBeCompared{get;set;}

public int PropertyThatWontBeCompared{get;set;}

[EqualityMember]
public int PropertyThatWillAlsoBeCompared{get;set;}
}


Then you could scan your PropertyInfo and MemberInfo for those who have this attribute and compare them. (Obviously, this solution will only work with your objects, since you have the source)

-
I think that's what the fieldSelector and propertySelector parameters are for. –  svick Jul 15 '14 at 16:45
Maybe indeed, it isn't very clear. Though I asked the OP if he was comparing all the properties/fields in the question's comment and he said yes... If your point appears to be true I'll just remove my answer! –  TopinFrassi Jul 15 '14 at 17:28
Maybe I should have explained the intended usage scenarios better. I did so now, see the updated question. Svick is right, fieldSelector and propertySelector serve the purpose of specifying which members participate in the equality comparison. However, your suggestion with attributes would be a clearer way for the clients. That way, I would be able to hide the complexity of the EqualityFunctionGenerator even for the more advanced cases. –  theDmi Jul 16 '14 at 6:30
I use this approach for my equality class and it works like a charm ;) –  TopinFrassi Jul 16 '14 at 12:10