C#: An item with the same key has already been added, when compiling expression

Question

Ok, here's a tricky one. Hopefully there is an expression guru here who can spot what I am doing wrong here, cause I am just not getting it.

I am building up expressions that I use to filter queries. To ease that process I have a couple of Expression<Func<T, bool>> extension methods that makes my code cleaner and so far they have been working nicely. I have written tests for all of them except one, which I wrote one for today. And that test fails completely with an ArgumentException with a long stack trace. And I just don't get it. Especially since I have been using that method for a while successfully in my queries!

Anyways, here is the stack trace I get when running the test:

failed: System.ArgumentException : An item with the same key has already been added.
    at System.ThrowHelper.ThrowArgumentException(ExceptionResource resource)
    at System.Collections.Generic.Dictionary`2.Insert(TKey key, TValue value, Boolean add)
    at System.Linq.Expressions.ExpressionCompiler.PrepareInitLocal(ILGenerator gen, ParameterExpression p)
    at System.Linq.Expressions.ExpressionCompiler.GenerateInvoke(ILGenerator gen, InvocationExpression invoke, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateBinary(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateUnliftedAndAlso(ILGenerator gen, BinaryExpression b)
    at System.Linq.Expressions.ExpressionCompiler.GenerateAndAlso(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateBinary(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateUnliftedOrElse(ILGenerator gen, BinaryExpression b)
    at System.Linq.Expressions.ExpressionCompiler.GenerateOrElse(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateBinary(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateInvoke(ILGenerator gen, InvocationExpression invoke, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateUnliftedAndAlso(ILGenerator gen, BinaryExpression b)
    at System.Linq.Expressions.ExpressionCompiler.GenerateAndAlso(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateBinary(ILGenerator gen, BinaryExpression b, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.Generate(ILGenerator gen, Expression node, StackType ask)
    at System.Linq.Expressions.ExpressionCompiler.GenerateLambda(LambdaExpression lambda)
    at System.Linq.Expressions.ExpressionCompiler.CompileDynamicLambda(LambdaExpression lambda)
    at System.Linq.Expressions.Expression`1.Compile()
    PredicateTests.cs(257,0): at Namespace.ExpressionExtensionsTests.WhereWithin_CollectionIsFilteredAsExpected()

The test itself looks like the following, an it fails at the Compile statement:

[Test]
public void WhereWithin_CollectionIsFilteredAsExpected()
{
    var range = new[] { Range.Create(2, 7), Range.Create(15, 18) };

    var predicate = Predicate
        .Create<int>(x => x % 2 == 0)
        .AndWithin(range, x => x)
        .Compile();

    var actual = Enumerable.Range(0, 20)
        .Where(predicate)
        .ToArray();

    Assert.That(actual, Is.EqualTo(new[] { 2, 4, 6, 16, 18 }));
}

I just don't understand the error message. I thought it might have to do with the fact that I always use x as the parameter name, but didn't seem to help when I tried to swap them around. What makes it even weirder to me is that I have been using this exact method for a while already in bigger Linq2Sql queries and they have always worked nicely. So in my test I tried to not compile the expression and use AsQueryable so I could use it on that instead. But that just made the exception occur on the ToArray instead. What is going on here? How can I fix this?

You can find the offending and annoying code in the zip file below the line:

---

Note: I had posted some of the related code here, but after some comments I decided to extract the code into it's own project which shows the exception more clearly. And more importantly, that can be run, compiled and debugged.

• ExpressionCuriosity.zip

---

Update: Simplified the example project even further with some of the suggestions from @Mark. Like removing the range class and instead just hard coding single constant range. Also added another example where using the exact same method actually works fine. So, using the AndWithin method makes the app crash, while using the WhereWithin method actually works fine. I feel pretty much clueless!

• ExpressionCuriosity.zip (Updated)

Entry

Is Range<TValue> a class you have written yourself? – Velocity

@Mark: Yes, it's mostly just a class with a start and an end. Although i have a range of extension methods for it and it has equals overridden and so on. But in this case that shouldn't really matter. It's a very simple class :) – Entry

As a comment, System.Predicate already exists, so the naming is somewhat confusing. msdn.microsoft.com/en-us/library/bfcke1bz.aspx – Taut

@recursive: I know, but couldn't come up with a better one. And since I never really use that Predicate delegate anyways... yeah... :p – Entry

@Svish: it would be useful if you could post some compiling code that can be run to reproduce the error. Can you rewrite the code to not need the Range class but still produce the error, thereby producing a self-contained example that reproduces the error? Alternatively if you can't do this, can you include the code for all classes needed to reproduce this error? – Velocity

Could maybe rename it to Filter or something... but we'll see :) – Entry

@Mark: Hmm... a very good point. It is almost midnight here now though, but if no-one has spotted anything when I get back tomorrow I will sure see what I can do cause this thing is bugging me big time, hehe. (Pun half intended :p) – Entry

@Mark: Ok, I couldn't go to sleep without doing it. Made a tiny project with the minimum code to make the error. Well, probably could be even less, but yeah. Editing question – Entry

(What is it with software development and the time around midnight... sigh :p ) – Entry

@Svish: I can reproduce the error. You can further simplify it by having only one range, and the error still occurs. – Velocity

@Mark: Oh yeah, that's right. – Entry

@Svish: it seems to me to be a bug. I tried my simplified version in .NET 4 and it worked, but your simplified version still doesn't work. – Velocity

@Mark: Hm... a bug in the .Net framework you mean? – Entry

It does look that way to me, although I am not that familiar with expression trees so there may be a bug in your code that I'm not aware of, but there isn't any obvious error that I can see. It is odd that it would work or not work depending on .NET framework version. I think the way forward is to further simplify to a single method that reproduces the bug absolutely as simple as possible, and if still no-one can see any error in your code, then perhaps contact Microsoft. – Velocity

@Svish: Check out my even simpler version: just one method, 6 lines of code, same error. – Velocity

@Svish: Have you made any more progress on this? – Velocity

@Mark: No, unfortunately not. Have changed work and my home computer is dead. Would still love to figure it out though... but yeah. – Entry

Answer 1

I refactored your methods a bit to make the compiler a bit happier:

public static Expression<Func<TSubject, bool>> AndWithin<TSubject, TField>(
    this Expression<Func<TSubject, bool>> original,
    IEnumerable<Range<TField>> range, Expression<Func<TSubject, TField>> field) where TField : IComparable<TField>
{
  return original.And(range.GetPredicateFor(field));
}


static Expression<Func<TSource, bool>> GetPredicateFor<TSource, TValue>
    (this IEnumerable<Range<TValue>> range, Expression<Func<TSource, TValue>> selector) where TValue : IComparable<TValue>
{
  var param = Expression.Parameter(typeof(TSource), "x");

  if (range == null || !range.Any())
    return Expression.Lambda<Func<TSource, bool>>(Expression.Constant(false), param);

  Expression body = null;
  foreach (var r in range)
  {
    Expression<Func<TValue, TValue, TValue, bool>> BT = (val, min, max) => val.CompareTo(min) >= 0 && val.CompareTo(max) <= 0;
    var newPart = Expression.Invoke(BT, param,
                                      Expression.Constant(r.Start, typeof(TValue)),
                                      Expression.Constant(r.End, typeof(TValue)));

    body = body == null ? newPart : (Expression)Expression.OrElse(body, newPart);
  }

  return Expression.Lambda<Func<TSource, bool>>(body, param);
}

Both have the added restriction of IComparable<TValue> (the only change to the first method).

In the second, I'm doing the comparison via a Func Expression implementation, notice that the func is created inside the loop...it's the second addition of this (what it thinks is the same...) expression in the old method that's blowing up.

Disclaimer: I still don't fully understand why your previous method didn't work, but this alternative approach bypasses the problem. Let me know if this isn't what you're after and we'll try something else.

Also, kudos on ASKING a question well, a sample project is exemplary.

Frizz

Hm... wasn't it compiling for you? Compiles here... Anyways, what made it pass for you? The IComparable, or doing the comparison in the expression? Will doing that work in a Linq2Sql query? – Entry

You are right in that this makes my example problem not crash anymore. However, it is not usable since I can't use the Compare method since it is not supported by the LinqToSql provider =/ (Thanks for the kudos btw :p) – Entry

@Svish: It's supported on our provider, you just can't supply your own Comparer, what error do you get when you try this? – Frizz

Oh, so I can't use the default comparer and such? – Entry

@Svish: You can, it's the only one you can. It's a similar situation with strings, look at this: msdn.microsoft.com/en-us/library/bb882672.aspx You can use String.Compare(string1, string2), but no other overload works, because in SQL it's just translated as COLUMN_A > COLUMN_B, same with any other .Compare unless there's an exception someone's familiar with. – Frizz

@Svish: It does on our provider, null is < 0 in oracle, I assume the same comparison would be true for SQL Server. As long as you're comparing nullables to nullables you won't get any trouble. In your case just change your Range so be Nullable<T> instead of T for the Start and End properties. – Frizz

Answer 2

This is not an answer, but I hope it will help someone find the answer. I've simplified the code further so that it is just one single file and still fails in the same way. I have renamed the variables so that "x" is not used twice. I have removed the Range class and replaced it with hardcoded constants 0 and 1.

using System;
using System.Linq;
using System.Linq.Expressions;

class Program
{
    static Expression<Func<int, bool>> And(Expression<Func<int, bool>> first,
                                           Expression<Func<int, bool>> second)
    {
        var x = Expression.Parameter(typeof(int), "x");
        var body = Expression.AndAlso(Expression.Invoke(first, x), Expression.Invoke(second, x));
        return Expression.Lambda<Func<int, bool>>(body, x);
    }

    static Expression<Func<int, bool>> GetPredicateFor(Expression<Func<int, int>> selector)
    {
        var param = Expression.Parameter(typeof(int), "y");
        var member = Expression.Invoke(selector, param);

        Expression body =
            Expression.AndAlso(
                Expression.GreaterThanOrEqual(member, Expression.Constant(0, typeof(int))),
                Expression.LessThanOrEqual(member, Expression.Constant(1, typeof(int))));

        return Expression.Lambda<Func<int, bool>>(body, param);
    }

    static void Main()
    {
        Expression<Func<int, bool>> predicate = a => true;
        predicate = And(predicate, GetPredicateFor(b => b)); // Comment out this line and it will run without error
        var z = predicate.Compile();
    }
}

The expression looks like this in the debugger:

x => (Invoke(a => True,x) && Invoke(y => ((Invoke(b => b,y) >= 0) && (Invoke(b => b,y) <= 1)),x))

Update: I've simplified it down to about the most simple it can be while still throwing the same exception:

using System;
using System.Linq;
using System.Linq.Expressions;

class Program
{
    static void Main()
    {
        Expression<Func<int, bool>> selector = b => true;
        ParameterExpression param = Expression.Parameter(typeof(int), "y");
        InvocationExpression member = Expression.Invoke(selector, param);
        Expression body = Expression.AndAlso(member, member);
        Expression<Func<int, bool>> predicate = Expression.Lambda<Func<int, bool>>(body, param);
        var z = predicate.Compile();
    }
}

Velocity

Created an updated project with some of your simplifications. Please check it out :) – Entry

Notice that the simplified code (the version with just 6 lines) works in .NET 4.0, but not in .NET 3.5, which suggests to me that there was a bug in .NET 3.5 that has been fixed in 4.0. Furthermore, the original code doesn't work in .NET 4.0, which could mean that there still is a bug in .NET 4.0 and you should perhaps report this to Microsoft as a possible bug. – Velocity

Hm... how would you report this as a bug to Microsoft? Never really understood that... I suppose it has something to do with the connect website, but never figured out that jungle =/ – Entry

And if you do choose this route, please do come back occasionally with status updates (or a bug track ticket) as I'm very interested in how this turns out, and judging by the number of upvotes/stars your question got, a few others are too. – Velocity