ExpressionTree Compile () method throws stackoverflow exception

Question

I have a gridview in which we can filter by different criteria. Each criterion is an expression. I have a scenario where I can have more than a thousand criteria that make my expression throw StackOverflow when calling the compilation method.

I'm still new to using btw expression trees.

Here is an example I made to reproduce stackoverflow.

var param = Expression.Parameter(typeof(SomeEntity), "SomeEntity"); Expression finalExpression = Expression.Default(typeof(bool)); for (int i = 0; i < 20000; i++) // Create 20000 expressions { var left = Expression.Property(param, "OrderID"); var right = Expression.Constant(42.ToString()); var expression = BinaryExpression.Equal(left, right); finalExpression = Expression.OrElse(finalExpression, expression); } var hello = Expression.Lambda(finalExpression, param); hello.Compile(); 

My question is: is there a way to “reduce” this expression or any other solutions that prevent the use of stackoverflow?

thanks

NOTE: this is what the expression looks like in the debugger:

 (SomeEntity.OrderID == "42")) OrElse (SomeEntity.OrderID == "42")) OrElse (SomeEntity.OrderID == "42")) OrElse (SomeEntity.OrderID == "42")) OrElse (SomeEntity.OrderID == "42")) x20000 

Answer 1

I have just successfully tested this code with up to 1,000,000 conditions without - I suspect that it can handle as many conditions as you want.

When you call Compile in a lambda expression, the expression tree descends recursively to compile it; extremely deep trees (like this) require many, many stack frames to accomplish this - hence, a StackOverflowException .

What I did below is only to fulfill a fixed number of conditions (set by MaxPredicateConditionCount ) before compiling the expression and clicking on it into a set of conditions that have already been generated. If this collection of pre-generated expressions reaches this maximum, they are combined into a new expression and so on. In this way, we can limit the depth of recursion needed to compile the expression (by doing this in pieces).

 public class PredicateBuilder<TParameter> { private const int MaxPredicateConditionCount = 500; private readonly List<Expression<Func<TParameter, bool>>> _existingPredicates = new List<Expression<Func<TParameter, bool>>>(MaxPredicateConditionCount); private readonly ParameterExpression _parameter = Expression.Parameter(typeof(TParameter)); private Expression<Func<TParameter, bool>> _expression; private Expression _workingPredicate; private int _workingPredicateConditionCount; public bool Built { get; private set; } public Expression<Func<TParameter, bool>> LambdaExpression { get { if (!Built) { return null; } return _expression; } } public void AddCondition<TValue>(string propertyName, TValue value) { if (Built) { throw new InvalidOperationException("Predicate has already been built"); } var property = Expression.Property(_parameter, propertyName); var constant = Expression.Constant(value, typeof(TValue)); var equality = Expression.Equal(property, constant); if (_workingPredicate == null) { _workingPredicate = equality; } else { if (MaxPredicateConditionCount < ++_workingPredicateConditionCount) { var compiledWorking = Expression.Lambda<Func<TParameter, bool>>(_workingPredicate, _parameter).Compile(); _existingPredicates.Add(p => compiledWorking(p)); if (_existingPredicates.Count + 1 > MaxPredicateConditionCount) { var compiled = BuildExistingPredicates().Compile(); _existingPredicates.Clear(); _existingPredicates.Add(p => compiled(p)); } _workingPredicate = equality; _workingPredicateConditionCount = 0; } else { _workingPredicate = Expression.OrElse(_workingPredicate, equality); } } } private Expression<Func<TParameter, bool>> BuildExistingPredicates() { Expression compileTemp = Expression.Invoke(_existingPredicates[0], _parameter); for (var i = 1; i < _existingPredicates.Count; ++i) { var nextCall = Expression.Invoke(_existingPredicates[i], _parameter); compileTemp = Expression.OrElse(compileTemp, nextCall); } return Expression.Lambda<Func<TParameter, bool>>(compileTemp, _parameter); } public void Build() { Built = true; //There were no conditions, assume true if (_workingPredicate == null) { _expression = x => true; return; } _existingPredicates.Add(Expression.Lambda<Func<TParameter, bool>>(_workingPredicate, _parameter)); _expression = BuildExistingPredicates(); _existingPredicates.Clear(); _workingPredicate = null; _workingPredicateConditionCount = 0; } public Func<TParameter, bool> Compile() { if (!Built) { Build(); } return _expression.Compile(); } } 

Object Example

 public class SomeEntity { public string OrderID { get; set; } } 

Using

 class Program { static void Main() { var builder = new PredicateBuilder<SomeEntity>(); for (int i = 0; i < 1000000; i++) // Create 1,000,000 expressions { builder.AddCondition("OrderID", "42"); Console.Title = i.ToString(); } builder.Compile(); } }