Linq to SQL throwing a StackOverflowException

Question

I'm executing a pretty simple query using Linq to SQL. I'm creating the expression and then passing it to the Where() extension method. The Linq internals are throwing a StackOverflowException when I attempt to actually execute the query. Here is the code:

int expectedCount = 4;
Expression<Func<Thing, bool>> expression = ...;

//Expression looks like (LocaleID = 1 && GenderID ==1 && (TimeFrameID == 2007 || TimeFrameID == 2008))

using (XYZDataContext context = new XYZDataContext())
{
    int count = context.Things.Where(expression).Count();
    //...
}

And here is the DebugView of the expression:

.Lambda #Lambda1<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    .Invoke (.Lambda #Lambda2<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o) & .Invoke (.Lambda #Lambda3<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o)
}

.Lambda #Lambda2<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    .Invoke (.Lambda #Lambda4<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o) & .Invoke (.Lambda #Lambda5<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o)
}

.Lambda #Lambda3<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    .Invoke (.Lambda #Lambda6<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o) | .Invoke (.Lambda #Lambda7<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>)($o)
}

.Lambda #Lambda4<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    $o.LocaleID == .Constant<System.Nullable`1[System.Int32]>(1)
}

.Lambda #Lambda5<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    $o.GenderID == .Constant<System.Nullable`1[System.Int32]>(1)
}

.Lambda #Lambda6<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    $o.TimeframeID == .Constant<System.Nullable`1[System.Int32]>(2007)
}

.Lambda #Lambda7<System.Func`2[XYZ.DataAccess.Thing,System.Boolean]>(XYZ.DataAccess.Thing $o)
{
    $o.TimeframeID == .Constant<System.Nullable`1[System.Int32]>(2008)
}

The expression appears correct to me and it is fairly trivial. When I read the debug view I see:

((LocaleID == 1 && GenderID == 1) && (TimeFrameID == 2007 || TimeFrameID == 2008))

...which is correct.

Update 1

Removing one of the inner or'd clauses, it works fine. So having both inner or'd clauses is breaking the translation from LINQ to SQL, somehow.

Update 2

I'm having trouble getting the debugger to step into .NET Framework code - I've tried using Reflector to do it as well as just Visual Studio. I got in once but in general stepping in is not working. The one time I did get in the StackOverflowException was occurring in:

ExecutionContext.Run(ExecutionContext executionContext, ContextCallback callback, object state, bool ignoreSyncCtx)

Update 3

Here is the code that is used to create the Expression. There is way too much code to post but the heart of it is below. I have classes which allow me to build a complex multi-level query and serialize it to JSON and XML. At the core, each piece of the query is built using the following methods and then is Or'd and And'd together:

public class LinqSearchField<T, V> : ISearchField
{
    public string Name { get; private set; }
    public Expression<Func<T, V>> Selector { get; private set; }

    public Expression<Func<T, bool>> LessThan(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.LessThan(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> LessThanOrEqual(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.LessThanOrEqual(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> Equal(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.Equal(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> NotEqual(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.NotEqual(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> GreaterThan(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.GreaterThan(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> GreaterThanOrEqual(V value)
    {
        return Expression.Lambda<Func<T, bool>>(Expression.GreaterThanOrEqual(this.Selector.Body, GetConstant(value)), this.Selector.Parameters);
    }

    private ConstantExpression GetConstant(V value)
    {
        return Expression.Constant(value, typeof(V));
    }

    public Expression<Func<T, bool>> Null()
    {
        return Expression.Lambda<Func<T, bool>>(Expression.Equal(this.Selector.Body, Expression.Constant(null)), this.Selector.Parameters);
    }

    public Expression<Func<T, bool>> NotNull()
    {
        return Expression.Lambda<Func<T, bool>>(Expression.NotEqual(this.Selector.Body, Expression.Constant(null)), this.Selector.Parameters);
    }
}

Here is the And code (the OR code is the same but with Expression.And instead):

public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> expression1, Expression<Func<T, bool>> expression2)
{
    ParameterExpression[] parameters = expression1.Parameters.Union(expression2.Parameters).Distinct(new ParameterExpressionComparer()).ToArray();
    InvocationExpression invocationExpression1 = Expression.Invoke(expression1, parameters);
    InvocationExpression invocationExpression2 = Expression.Invoke(expression2, parameters);
    Expression binaryExpression = null;

    //And the current expression to the previous one.
    binaryExpression = Expression.AndAlso(invocationExpression1, invocationExpression2); //Or OrElse.

    //Wrap the expression in a lambda.
    return Expression.Lambda<Func<T, bool>>(binaryExpression, parameters);
}

Update 4

It will probably be frowned upon but here is a sample which reproduces this issue. I really need to figure out what's going on here.

Answer 1

I had my suspicions initially but can now confirm it.

You're combining two lambdas that have two completely different instances of their parameters. The parameter instances are not swappable, even if they have the same names and same types. They are effectively parameters in different scopes. When you attempted to invoke one of the expressions with the wrong parameter object, chaos ensues, in this case, a stack overflow.

What you should be doing is create a new parameter instance (or reuse one) and rebind the bodies of your lambdas to use that new parameter. I suspect that will fix this. And to go a step further, you should properly combine these expressions by rebuilding them, rather than patching them together as method calls. I doubt the query providers will like these as invocations any way.

Try this implementation of your And() and Or() methods along with this helper method to do the rebinding:

public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> expression1, Expression<Func<T, bool>> expression2)
{
    // reuse the first expression's parameter
    var param = expression1.Parameters.Single();
    var left = expression1.Body;
    var right = RebindParameter(expression2.Body, expression2.Parameters.Single(), param);
    var body = Expression.AndAlso(left, right);
    return Expression.Lambda<Func<T, bool>>(body, param);
}

public static Expression<Func<T, bool>> Or<T>(this Expression<Func<T, bool>> expression1, Expression<Func<T, bool>> expression2)
{
    var param = expression1.Parameters.Single();
    var left = expression1.Body;
    var right = RebindParameter(expression2.Body, expression2.Parameters.Single(), param);
    var body = Expression.OrElse(left, right);
    return Expression.Lambda<Func<T, bool>>(body, param);
}

private static Expression RebindParameter(Expression expr, ParameterExpression oldParam, ParameterExpression newParam)
{
    switch (expr.NodeType)
    {
    case ExpressionType.Parameter:
        var asParameterExpression = expr as ParameterExpression;
        return (asParameterExpression.Name == oldParam.Name)
            ? newParam
            : asParameterExpression;
    case ExpressionType.MemberAccess:
        var asMemberExpression = expr as MemberExpression;
        return asMemberExpression.Update(
            RebindParameter(asMemberExpression.Expression, oldParam, newParam));
    case ExpressionType.AndAlso:
    case ExpressionType.OrElse:
    case ExpressionType.Equal:
    case ExpressionType.NotEqual:
    case ExpressionType.LessThan:
    case ExpressionType.LessThanOrEqual:
    case ExpressionType.GreaterThan:
    case ExpressionType.GreaterThanOrEqual:
        var asBinaryExpression = expr as BinaryExpression;
        return asBinaryExpression.Update(
            RebindParameter(asBinaryExpression.Left, oldParam, newParam),
            asBinaryExpression.Conversion,
            RebindParameter(asBinaryExpression.Right, oldParam, newParam));
    case ExpressionType.Call:
        var asMethodCallExpression = expr as MethodCallExpression;
        return asMethodCallExpression.Update(
            RebindParameter(asMethodCallExpression.Object, oldParam, newParam),
            asMethodCallExpression.Arguments.Select(arg =>
                RebindParameter(arg, oldParam, newParam)));
    case ExpressionType.Invoke:
        var asInvocationExpression = expr as InvocationExpression;
        return asInvocationExpression.Update(
            RebindParameter(asInvocationExpression.Expression, oldParam, newParam),
            asInvocationExpression.Arguments.Select(arg =>
                RebindParameter(arg, oldParam, newParam)));
    case ExpressionType.Lambda:
        var asLambdaExpression = expr as LambdaExpression;
        return Expression.Lambda(
            RebindParameter(asLambdaExpression.Body, oldParam, newParam),
            asLambdaExpression.Parameters.Select(param =>
                (ParameterExpression)RebindParameter(param, oldParam, newParam)));
    default:
        // you should add cases for any expression types that have subexpressions
        return expr;
    }
}

What the rebinding method does is searches for (by name) and returns an expression where all ParameterExpression within an expression tree are replaced with an instance of another ParameterExpression. This does not modify the existing expressions but rebuilds the expression creating newly updated expressions when needed. In other words, it returns a new expression that should be used as a replacement of the one that you are rebinding.

The idea is to examine the Expression and determine what type it is. If it is a ParameterExpression, check if it has the same name as the parameter we're looking for. If it is, return our new parameter, otherwise return it as we shouldn't change it. If the expression is not a parameter, it will probably be an expression that contains subexpressions and would have to be replaced.

A BinaryExpression will have a Left operand and a Right operand, both expressions. They both need to be rebound since somewhere down their expression trees might be a parameter that needs replacing. The Update() method will replace the current expression with a similar one with the new subexpressions. In this case, we only wanted to (potentially) update the Left and Right subexpressions.

The MethodCallExpression and InvocationExpression has the same idea but it's tree is slightly different. It has the Object expression (or Expression in the case of an invocation) which represents the instance (or delegate/lambda) that you want to be calling on. (The MethodCallExpression also has a MethodInfo which represents the instance method to call) They also have Arguments (all expressions) which are used as the arguments to the call. These expressions potentially would need to be rebound.

You can think of the RebindParameter() method as a "super"-Update() method which updates parameters within an entire expression tree.

To further illustrate, an illustration to help visualize what the tree looks like and what changes. Note that since there are replacements occurring here, most of the subtrees will be new instances.

[

---

Now here's something I didn't realize was available, the ExpressionVisitor. Wish I noticed it sooner. This will make the rebinder better to work with. Rather than posting the full code here, here it is on pastebin. Then to use it:

public static Expression<Func<T, bool>> And<T>(this Expression<Func<T, bool>> expression1, Expression<Func<T, bool>> expression2)
{
    // reuse the first expression's parameter
    var param = expression1.Parameters.Single();
    var left = expression1.Body;
    var right = ParameterRebinder.Rebind(expression2.Body, expression2.Parameters.Single(), param);
    var body = Expression.AndAlso(left, right);
    return Expression.Lambda<Func<T, bool>>(body, param);
}

public static Expression<Func<T, bool>> Or<T>(this Expression<Func<T, bool>> expression1, Expression<Func<T, bool>> expression2)
{
    var param = expression1.Parameters.Single();
    var left = expression1.Body;
    var right = ParameterRebinder.Rebind(expression2.Body, expression2.Parameters.Single(), param);
    var body = Expression.OrElse(left, right);
    return Expression.Lambda<Func<T, bool>>(body, param);
}