Construyendo expresiones 'planas' en lugar de 'árbol' LINQ

Question

Estoy usando algún código (disponible here en MSDN) para construir dinámicamente expresiones LINQ que contengan múltiples 'cláusulas' OR.

El código en cuestión es

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)); 

Esto genera una expresión LINQ que se ve algo como esto:

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

Estoy golpeando el límite de recursión (100) cuando se utiliza esta expresión, por lo que Me gustaría generar una expresión que se ve así:

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

¿Cómo puedo modificar el ex código de construcción de presión para hacer esto?

Answer 1

Es necesario modificar la generación de modo que construye un árbol equilibrado en lugar de una secuencia de OR s donde el subárbol izquierdo es una expresión única y el subárbol derecho contiene todos los elementos restantes. Gráficamente:

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

Como se puede ver, incluso en este caso sencillo, el mejor enfoque no es tan profunda (de forma recursiva anidada). El código para generar el mejor árbol de expresión se puede escribir como un método recursivo en 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); 

no probé el código, lo que puede haber algunos errores de menor importancia, pero debería mostrar la idea.

Answer 2

Si esto es realmente LINQ to Objects según sus etiquetas, ¿por qué está construyendo árboles de expresión? Puede usar delegados muy fácilmente, y no tendrán un límite de recursión.

Sin embargo, más al punto: si lo que desea es ver si es un ID de alguna colección particular, por qué no estás usando algo como:

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