CODEWITHSUNDEEP
.netlinqwcf-data-services
Ian Gregory
Ian Gregory

Reputation: 5820

Building 'flat' rather than 'tree' LINQ expressions

I'm using some code (available here on MSDN) to dynamically build LINQ expressions containing multiple OR 'clauses'.

The relevant code is

var equals = values.Select(value => (Expression)Expression.Equal(valueSelector.Body, Expression.Constant(value, typeof(TValue))));

var body = equals.Aggregate<Expression>((accumulate, equal) => Expression.Or(accumulate, equal));

This generates a LINQ expression that looks something like this:

(((((ID = 5) OR (ID = 4)) OR (ID = 3)) OR (ID = 2)) OR (ID = 1))

I'm hitting the recursion limit (100) when using this expression, so I'd like to generate an expression that looks like this:

(ID = 5) OR (ID = 4) OR (ID = 3) OR (ID = 2) OR (ID = 1)

How would I modify the expression building code to do this?

Upvotes: 5

Views: 580

Answers (2)

Tomas Petricek
Tomas Petricek

Reputation: 243041

You need to modify the generation so that it builds a ballanced tree instead of a sequence of ORs where the left sub-tree is a single expression and the right sub-tree contains all remaining elements. Graphically:

 Your code               Better
 ---------              --------
    OR                     OR
 #1    OR              OR      OR
     #2  OR          #1  #2  #3  #4
       #3  #4

As you can see, even in this simple case, the better approach is not as deeply (recursively nested). The code to generate the better expression tree can be written as a recursive method in C#:

Expression GenerateTree(List<Expression> exprs, int start, int end) {
  // End of the recursive processing - return single element
  if (start == end) return exprs[start];

  // Split the list between two parts of (roughly the same size)
  var mid = start + (end - start)/2;
  // Process the two parts recursively and join them using OR
  var left = GenerateTree(exprs, start, mid);
  var right = GenerateTree(exprs, mid+1, end);
  return Expression.Or(left, right);
}

// Then call it like this:
var equalsList = equals.ToList();
var body = GenerateTree(equalsList, 0, equalsList.Length);

I didn't try the code, so there may be some minor mistakes, but it should show the idea.

Upvotes: 6

Jon Skeet
Jon Skeet

Reputation: 1499760

If this is truly LINQ to Objects as per your tags, why are you building expression trees at all? You can use delegates very easily, and they won't have a recursion limit.

However, more to the point: if you just want to see whether an ID is in some particular collection, why aren't you using something like:

var query = from item in source
            where idCollection.Contains(item.Id)
            ...

Upvotes: 1

Related Questions