Building unusual IComparer<T> from expressions

Question

I've needed a couple of very special comparers recenty and didn't want to implement each one of them every time so I created a builder and a couple of supporting classes that do that for me.

Example

I'll start with an example. Given a collection of Products:

var products = new[]
{
    new Product {Name = "Car", Price = 7 },
    new Product {Name = "Table", Price = 3 },
    new Product {Name = "Orange", Price = 1 },
};

private class Product
{
    public int Id { get; set; }

    public string Name { get; set; }

    public int Price { get; set; }
}

I'd like to sort them either by the length of their name or price. Instead of implementig this type of unusual sorting with a new comparer I can use my new builder that allows me to create a comparer for that on the fly:

var comparer = ComparerFactory<Product>.Create(
    x => new { x.Name.Length, x.Price },
    (builder, x, y) =>
    {
        builder
            .LessThen(() => x.Length < y.Length || x.Price < y.Price)
            .Equal(() => x.Length == y.Length || x.Price == y.Price)
            .GreaterThan(() => x.Length > y.Length || x.Price > y.Price);
    });

var sorted = products.OrderByDescending(p => p, comparer).ToList();

Implementation

On top of everything else I use the ComparerFactory<T> that implements the tedious null checks and comparisons. No magic here.

internal static class ComparerFactory<T>
{
    private class Comparer : IComparer<T>
    {
        private readonly IDictionary<CompareOperator, Func<T, T, bool>> _comparers;

        internal Comparer([NotNull] IDictionary<CompareOperator, Func<T, T, bool>> comparers)
        {
            _comparers = comparers;
        }

        public int Compare(T x, T y)
        {
            if (ReferenceEquals(x, y)) return 0;
            if (ReferenceEquals(x, null)) return -1;
            if (ReferenceEquals(y, null)) return 1;

            if (_comparers[CompareOperator.LessThan](x, y)) return -1;
            if (_comparers[CompareOperator.Equal](x, y)) return 0;
            if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

            // Makes the compiler very happy.
            return 0;
        }
    }

    public static IComparer<T> Create<TComparable>(Expression<Func<T, TComparable>> selectComparable, Action<ComparerBuilder<T, TComparable>, TComparable, TComparable> create)
    {
        var builder = new ComparerBuilder<T, TComparable>(selectComparable);
        create(builder, default, default);
        var funcs = builder.Build();
        return new Comparer(funcs);
    }
}

The interesing part begins with the ComparerBuilder<T, TComparable>. An instance of this class passed to the Create call just after the expression that selects the relevant value or properties as an anonymous object:

var comparer = ComparerFactory<Product>.Create(
    x => new { x.Name.Length, x.Price },
    (builder, x, y) => { ... });

The user also receives the two arguments that should be compared x and y. I'm doing this to not have to repeat myself when defining each comparison like I did before.

This was the first version but I didn't like it. Too much redundancy so I moved the two repeating variables to the top.

(
    isLessThan: (x, y) => x.Ordinal < y.Ordinal,
    areEqual: (x, y) => x.Ordinal == y.Ordinal,
    isGreaterThan: (x, y) => x.Ordinal > y.Ordinal
);

The builder collects a couple of expressions. One for selecting the value or the properties that should be compared and one expression for each operation.

Finally the Build method turns each three operation expressions into three Func<T, T, bool>:

internal class ComparerBuilder<T, TComparable>
{
    private readonly Expression<Func<T, TComparable>> _getComparable;
    private readonly IDictionary<CompareOperator, Expression<Func<bool>>> _expressions = new Dictionary<CompareOperator, Expression<Func<bool>>>();

    public ComparerBuilder(Expression<Func<T, TComparable>> getComparable)
    {
        _getComparable = getComparable;
    }

    public ComparerBuilder<T, TComparable> LessThen(Expression<Func<bool>> expression)
    {
        _expressions[CompareOperator.LessThan] = expression;
        return this;
    }

    public ComparerBuilder<T, TComparable> Equal(Expression<Func<bool>> expression)
    {
        _expressions[CompareOperator.Equal] = expression;
        return this;
    }

    public ComparerBuilder<T, TComparable> GreaterThan(Expression<Func<bool>> expression)
    {
        _expressions[CompareOperator.GreaterThan] = expression;
        return this;
    }

    internal IDictionary<CompareOperator, Func<T, T, bool>> Build()
    {
        var left = Expression.Parameter(typeof(T), "left");
        var right = Expression.Parameter(typeof(T), "right");

        return _expressions.ToDictionary(x => x.Key, x => CompileComparer(x.Value, new[] { left, right }));
    }

    private Func<T, T, bool> CompileComparer(Expression compare, ParameterExpression[] parameters)
    {
        var rewritten = CompareRewriter.Rewrite(_getComparable, parameters, compare);
        var lambda = Expression.Lambda<Func<T, T, bool>>(Expression.Invoke(rewritten), parameters);
        return lambda.Compile();
    }
}

But since the original operation expressions are incompatible with the Func<T, T, bool> signature:

() => x < y

I cannot call them from the comparer yet. I need something else that wold accept parameters:

(x, y) => x < y

In order to achieve this I created the CompareRewriter that is a ExpressionVisitor and replaces closures with calls to the selector for the comparable type or value. In case it's an anonymous type an additional conversion is necessary. Here a property access needs to be done to get the result of the type selector and not the closure which is useless later.

This means that on the left and right side of each <, > and == operator I inject the selector specified as the first argument:

x => new { x.Name.Length, x.Price }

Rewriting the expressions was the trickiest part but I managed to create the correct expressions and it behaves just as I expect it to.

internal class CompareRewriter : ExpressionVisitor
{
    private readonly Expression _getComparable;
    private readonly ParameterExpression[] _parameters;
    private int _param;

    public CompareRewriter(Expression getComparable, ParameterExpression[] parameters)
    {
        _getComparable = getComparable;
        _parameters = parameters;
    }

    public static Expression Rewrite(Expression getComparable, ParameterExpression[] parameters, Expression compare)
    {
        var visitor = new CompareRewriter(getComparable, parameters);
        return visitor.Visit(compare);
    }

    protected override Expression VisitLambda<T>(Expression<T> node)
    {
        var binary = Visit((BinaryExpression)node.Body);
        return Expression.Lambda<Func<bool>>(binary);
    }

    protected override Expression VisitBinary(BinaryExpression node)
    {
        if (node.NodeType == ExpressionType.Equal) return base.VisitBinary(node);

        // Rewrite
        // () => ClosureT1.x < ClosureT2.y
        // to
        // () => getComparable(T2).x < getComparable(T2).y

        var getLeft = Expression.Invoke(_getComparable, _parameters[0]);
        var getRight = Expression.Invoke(_getComparable, _parameters[1]);

        _param = 0;
        var left = Visit(node.Left);
        _param++;
        var right = Visit(node.Right);

        // Determine whether a member-access is necessary or are we using pure values?
        left = left == node.Left ? getLeft : left;
        right = right == node.Right ? getRight : right;

        switch (node.NodeType)
        {
            case ExpressionType.LessThan: return Expression.LessThan(left, right);
            case ExpressionType.Equal: return Expression.Equal(left, right);
            case ExpressionType.GreaterThan: return Expression.GreaterThan(left, right);
        }
        return base.VisitBinary(node);
    }

    protected override Expression VisitMember(MemberExpression node)
    {
        return
            node.Member.MemberType == MemberTypes.Property
            ? Expression.MakeMemberAccess(Expression.Invoke(_getComparable, _parameters[_param]), node.Member)
            : base.VisitMember(node);
    }
}

internal enum CompareOperator
{
    LessThan,
    Equal,
    GreaterThan
}

---

What do you think of this kind of a builder where you need to rewrite the expressions afterwards? What do you say about the expression-visitor?

---

The same code but as a single file can be found here and my two tests here.

Answer 1

        builder
            .LessThen(() => x.Length < y.Length || x.Price < y.Price)
            .Equal(() => x.Length == y.Length || x.Price == y.Price)
            .GreaterThan(() => x.Length > y.Length || x.Price > y.Price);

gives me a very bad feeling, which turned out to be justified when I saw

        public int Compare(T x, T y)
        {
            ...

            if (_comparers[CompareOperator.LessThan](x, y)) return -1;
            if (_comparers[CompareOperator.Equal](x, y)) return 0;
            if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

            // Makes the compiler very happy.
            return 0;
        }

Fundamentally, what you have here may implement the IComparer<T> interface but it is not a comparer, as shown by the following test:

    [TestMethod]
    public void ComparerIsComparer()
    {
        var comparer = ComparerFactory<Product>.Create(
            x => new { x.Name.Length, x.Price },
            (builder, x, y) =>
            {
                builder
                    .LessThen(() => x.Length < y.Length || x.Price < y.Price)
                    .Equal(() => x.Length == y.Length || x.Price == y.Price)
                    .GreaterThan(() => x.Length > y.Length || x.Price > y.Price);
            });

        var products = new[]
        {
            new Product {Name = "Car", Price = 7 },
            new Product {Name = "Table", Price = 3 },
            new Product {Name = "Orange", Price = 1 },
        };

        foreach (var a in products)
        {
            foreach (var b in products)
            {
                var cmp1 = comparer.Compare(a, b);
                var cmp2 = comparer.Compare(b, a);
                Assert.IsTrue((cmp1 < 0 && cmp2 > 0) || (cmp1 == 0 && cmp2 == 0) || (cmp1 > 0 && cmp2 < 0));
            }
        }
    }

From the mention of "special comparers" in the question and "crazy comparers" in a comment on the question I assume that this is the intended behaviour, but it's still a violation of the principle of least surprise and should be very clearly commented in the code.

Note that a further consequence is that the test CanCreateCanonicalComparer is unreliable. Microsoft could (they probably won't, but they could) change the implementation of OrderByDescending in such a way that it still respects its documented behaviour and continues working for code which uses reasonable comparers, but breaks your test. Perhaps more likely, a third party implementation of .Net might write OrderByDescending differently to Microsoft.

---

            // Makes the compiler very happy.
            return 0;

The compiler would be equally happy if you threw an exception, and in my opinion that would be a more honest fix. If execution reaches this line, there's a programming error either in this code or in the code which uses it.

---

        internal Comparer([NotNull] IDictionary<CompareOperator, Func<T, T, bool>> comparers)
        {
            _comparers = comparers;
        }

        public int Compare(T x, T y)
        {
            ...

            if (_comparers[CompareOperator.LessThan](x, y)) return -1;
            if (_comparers[CompareOperator.Equal](x, y)) return 0;
            if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

            ...
        }

I'm not entirely convinced that a dictionary is appropriate but, given the decision to use it, in my opinion the constructor should check that it contains all of the necessary keys.

---

Postscript: my suggestion for a ComparerBuilder API would be the following:

public class ComparerBuilder<T>
{
    private ComparerBuilder() { }

    public static ComparerBuilder<T> CompareBy<TProjection>(Func<T, TProjection> projection) =>
        new ComparerBuilder<T>().ThenBy(projection);

    public static ComparerBuilder<T> CompareByDesc<TProjection>(Func<T, TProjection> projection) =>
        new ComparerBuilder<T>().ThenByDesc(projection);

    public ComparerBuilder<T> ThenBy<TProjection>(Func<T, TProjection> projection);

    public ComparerBuilder<T> ThenByDesc<TProjection>(Func<T, TProjection> projection);

    public Comparer<T> Build();
}

with a test to show usage:

    [TestMethod]
    public void TestComparerChain()
    {
        var data = new ValueTuple<string, int>[]
        {
            ("A", 10),
            ("B", 5),
            ("C", 2),
            ("C", 10),
            ("B", 5),
            ("A", 2),
        };
        var cmp = ComparerBuilder<ValueTuple<string, int>>.
            CompareByDesc(tuple => tuple.Item2).
            ThenBy(tuple => tuple.Item1).
            Build();

        data = data.OrderBy(x => x, cmp).ToArray();
        Assert.IsTrue(data.SequenceEqual(new ValueTuple<string, int>[]
        {
            ("A", 2),
            ("C", 2),
            ("B", 5),
            ("B", 5),
            ("A", 10),
            ("C", 10),
        }));
    }

This gives plenty of scope to use expression parsing and code generation...

Answer 2

I really admire your efforts and I read the question as more about Expressions than comparison.

Anyway: as for the comparison, you should be aware that the result is different if the initial order of the Products is changed:

this:

  var products = new[]
  {
    new Product {Name = "Car", Price = 7 },
    new Product {Name = "Table", Price = 3 },
    new Product {Name = "Orange", Price = 1 },
  };
  var sorted = products.OrderByDescending(p => p, comparer).ToList();

gives:

Orange, Car, Table

where

  var products = new[]
  {
    new Product {Name = "Orange", Price = 1 },
    new Product {Name = "Car", Price = 7 },
    new Product {Name = "Table", Price = 3 },
  };
  var sorted = products.OrderByDescending(p => p, comparer).ToList();

gives

Table, Orange, Car

I would call that an undesired side effect

---

In the same way you'll get different results if you change the order of the operators:

if (_comparers[CompareOperator.LessThan](x, y)) return -1;
if (_comparers[CompareOperator.Equal](x, y)) return 0;
if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

will potentially give another result than:

    if (_comparers[CompareOperator.Equal](x, y)) return 0;
    if (_comparers[CompareOperator.LessThan](x, y)) return -1;
    if (_comparers[CompareOperator.GreaterThan](x, y)) return 1;

but which one is right?

---

If you extent the Product class to:

  public class Product
  {
    public int Id { get; set; }
    public string Name { get; set; }
    public int Price { get; set; }
    public string Category { get; set; }

    public override string ToString()
    {
      return $"{Name} -> {Id} -> {Price} -> {Category}";
    }
  }

  var products = new[]
  {
    new Product {Name = "Car", Price = 7, Category = "Vehicle" },
    new Product {Name = "Table", Price = 3, Category = "Furniture" },
    new Product {Name = "Orange", Price = 1, Category = "Fruit" },
  };

and define the comparer as:

  var comparer = ComparerFactory<Product>.Create(
    x => new { x.Name.Length, x.Price, CategoryLitra = x.Category[0] },
    (builder, x, y) =>
    {
      builder
      .LessThen(() => x.Length < y.Length)
      .Equal(() => x.CategoryLitra == y.CategoryLitra)
      .GreaterThan(() => x.Price > y.Price);
    });

then the comparer should fall through to

    ...
    // Makes the compiler very happy.
    return 0;
  }

for "Table" (x) and "Car" (y) because none of the operators return true - but it doesn't. It evaluates them as Equal

The problems relates to this:

protected override Expression VisitBinary(BinaryExpression node)
{
    if (node.NodeType == ExpressionType.Equal) return base.VisitBinary(node);
    ...

But I'm not the one to explain why (or why you make this exception), but if you remove that if-statement it works.

---

I can only agree with Peter Taylor in his comment and strongly recommend only to compare in one "dimension" - otherwise I only see trouble as shown above.

---

If you insist on this design a more straight forward and naive solution could be:

  public class StrangeComparer<T> : IComparer<T>
  {
    Func<T, T, bool> m_lessThan;
    Func<T, T, bool> m_equals;
    Func<T, T, bool> m_greaterThan;

    public StrangeComparer(Func<T, T, bool> lessThan, Func<T, T, bool> equals, Func<T, T, bool> greaterThan)
    {
      m_lessThan = lessThan;
      m_equals = equals;
      m_greaterThan = greaterThan;
    }

    public int Compare(T x, T y)
    {
      if (ReferenceEquals(x, y)) return 0;
      if (x == null) return -1;
      if (y == null) return 1;

      if (m_lessThan(x, y)) return -1;
      if (m_equals(x, y)) return 0;
      if (m_greaterThan(x, y)) return 1;

      throw new InvalidOperationException($"Compare of {x} and {y}");
    }
  }

but IMO you're better off with something like:

  public class StrangeComparer<T> : IComparer<T>
  {
    Func<T, T, int> m_comparer;

    public StrangeComparer(Func<T, T, int> comparer)
    {
      m_comparer = comparer;
    }

    public int Compare(T x, T y)
    {
      if (ReferenceEquals(x, y)) return 0;
      if (x == null) return -1;
      if (y == null) return 1;

      return m_comparer(x, y);
    }
  }

Answer 3

I'd say this is far too complicated. It took me some time to figure out what those expressions are getting rewritten to, and the results do not look very efficient:

(x => new { x.Name.Length, x.Price }).Invoke(left).Length < (x => new { x.Name.Length, x.Price }).Invoke(right).Length || ...

---

What are the benefits here compared to a simple Comparer<T> class that wraps a Func<T, T, int>? Not only would that require less boilerplate code, it also simplifies the calling code and should be several times faster:

var comparer = new Comparer<Product>((x, y) =>
{
    if (x.Name.Length < y.Name.Length || x.Price < y.Price) return -1;
    if (x.Name.Length == y.Name.Length || x.Price == y.Price) return 0;
    return 1;
});
products.OrderByDescending(p => p, comparer).ToList();

Automatically taking care of the standard reference checks in the Comparer class is a good idea - I'd definitely keep that. However, what if Name is null? With the above approach, you can use Elvis operators, but they're apparently not (yet?) supported in expression trees.