Mover árvores de expressão

Neste artigo, você aprenderá a visitar cada nó em uma árvore de expressão enquanto estiver criando uma cópia modificada dessa árvore de expressão. Você converterá árvores de expressão para entender os algoritmos de modo que eles possam ser convertidos em outro ambiente. Você alterará o algoritmo criado. Você poderá adicionar registro em log, interceptar chamadas de método e monitorá-las ou realizar outras ações.

O código que você compila para mover uma árvore de expressão é uma extensão do que você já viu para visitar todos os nós em uma árvore. Quando você move uma árvore de expressão, visita todos os nós e ao visitá-los, cria a nova árvore. A nova árvore pode conter referências aos nós originais ou aos novos nós que você inseriu na árvore.

Vamos acessar uma árvore de expressão e criar uma árvore com alguns nós de substituição. Neste exemplo, substituiremos qualquer constante por uma constante dez vezes maior. Caso contrário, deixe a árvore de expressão intacta. Em vez de ler o valor da constante e substituí-la por uma nova constante, você fará essa substituição trocando o nó de constante por um novo nó que executa a multiplicação.

Aqui, quando encontrar um nó de constante, você criará um nó de multiplicação cujos filhos serão a constante original e a constante 10:

private static Expression ReplaceNodes(Expression original)
{
    if (original.NodeType == ExpressionType.Constant)
    {
        return Expression.Multiply(original, Expression.Constant(10));
    }
    else if (original.NodeType == ExpressionType.Add)
    {
        var binaryExpression = (BinaryExpression)original;
        return Expression.Add(
            ReplaceNodes(binaryExpression.Left),
            ReplaceNodes(binaryExpression.Right));
    }
    return original;
}

Crie uma árvore substituindo o nó original pelo substituto. Você verificará as alterações compilando e executando a árvore substituída.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var addition = Expression.Add(one, two);
var sum = ReplaceNodes(addition);
var executableFunc = Expression.Lambda(sum);

var func = (Func<int>)executableFunc.Compile();
var answer = func();
Console.WriteLine(answer);

A criação de uma nova árvore é uma combinação da visita aos nós da árvore existentes e a criação de novos nós, inserindo-os na árvore. O anterior exemplo mostra a importância de as árvores de expressão serem imutáveis. Observe que a árvore criada no código anterior contém uma mistura de nós recém-criados e nós da árvore existente. Os nós podem ser usados em ambas as árvores porque os nós na árvore existente não podem ser modificados. Reutilizar nós resulta em eficiências significativas de memória. Os mesmos nós podem ser usados em toda a árvore ou em várias árvores de expressão. Como os nós não podem ser modificados, o mesmo nó pode ser reutilizado sempre que necessário.

Percorrer e executar uma adição

Vamos verificar a nova árvore criando um segundo visitante que percorre a árvore de nós de adição e calcula o resultado. Faça algumas modificações no visitante que você viu até agora. Nessa nova versão, o visitante retorna a soma parcial da operação de adição até este ponto. Para uma expressão de constante, esse é simplesmente o valor da expressão de constante. Para uma expressão de adição, o resultado será a soma dos operandos esquerdos e direitos, uma vez que essas árvores forem percorridas.

var one = Expression.Constant(1, typeof(int));
var two = Expression.Constant(2, typeof(int));
var three = Expression.Constant(3, typeof(int));
var four = Expression.Constant(4, typeof(int));
var addition = Expression.Add(one, two);
var add2 = Expression.Add(three, four);
var sum = Expression.Add(addition, add2);

// Declare the delegate, so you can call it
// from itself recursively:
Func<Expression, int> aggregate = null!;
// Aggregate, return constants, or the sum of the left and right operand.
// Major simplification: Assume every binary expression is an addition.
aggregate = (exp) =>
    exp.NodeType == ExpressionType.Constant ?
    (int)((ConstantExpression)exp).Value :
    aggregate(((BinaryExpression)exp).Left) + aggregate(((BinaryExpression)exp).Right);

var theSum = aggregate(sum);
Console.WriteLine(theSum);

Tem bastante código nisso, mas os conceitos são acessíveis. Esse código visita filhos em uma pesquisa de profundidade inicial. Ao encontrar um nó constante, o visitante retorna o valor da constante. Depois de visitar ambos os filhos, o visitante terá a soma calculada para essa subárvore. Agora o nó de adição poderá computar sua soma. Uma vez que todos os nós da árvore de expressão forem visitados, a soma é calculada. Você pode executar o exemplo no depurador e rastrear a execução.

Vamos facilitar o rastreamento de como os nós são analisados e como a soma é calculada, percorrendo a árvore. Esta é uma versão atualizada do método de agregação que inclui bastante informação de rastreamento:

private static int Aggregate(Expression exp)
{
    if (exp.NodeType == ExpressionType.Constant)
    {
        var constantExp = (ConstantExpression)exp;
        Console.Error.WriteLine($"Found Constant: {constantExp.Value}");
        if (constantExp.Value is int value)
        {
            return value;
        }
        else
        {
            return 0;
        }
    }
    else if (exp.NodeType == ExpressionType.Add)
    {
        var addExp = (BinaryExpression)exp;
        Console.Error.WriteLine("Found Addition Expression");
        Console.Error.WriteLine("Computing Left node");
        var leftOperand = Aggregate(addExp.Left);
        Console.Error.WriteLine($"Left is: {leftOperand}");
        Console.Error.WriteLine("Computing Right node");
        var rightOperand = Aggregate(addExp.Right);
        Console.Error.WriteLine($"Right is: {rightOperand}");
        var sum = leftOperand + rightOperand;
        Console.Error.WriteLine($"Computed sum: {sum}");
        return sum;
    }
    else throw new NotSupportedException("Haven't written this yet");
}

Executá-lo na expressão sum produz o seguinte resultado:

10
Found Addition Expression
Computing Left node
Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Constant: 2
Right is: 2
Computed sum: 3
Left is: 3
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 10
10

Rastreie a saída e acompanhe no código anterior. Você será capaz de entender como o código visita cada nó e calcula a soma, à medida que percorre a árvore e localiza a soma.

Agora, vejamos uma execução diferente, com a expressão fornecida por sum1:

Expression<Func<int>> sum1 = () => 1 + (2 + (3 + 4));

Aqui está a saída ao examinar essa expressão:

Found Addition Expression
Computing Left node
Found Constant: 1
Left is: 1
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 2
Left is: 2
Computing Right node
Found Addition Expression
Computing Left node
Found Constant: 3
Left is: 3
Computing Right node
Found Constant: 4
Right is: 4
Computed sum: 7
Right is: 7
Computed sum: 9
Right is: 9
Computed sum: 10
10

Embora a resposta final seja a mesma, a forma de percorrer a árvore é diferente. Os nós são percorridos em uma ordem diferente, porque a árvore foi construída com operações diferentes que ocorrem primeiro.

Criar uma cópia modificada

Crie um novo projeto de Aplicativo de Console. Adicione uma diretiva using ao arquivo para o namespace System.Linq.Expressions. Adicione a classe AndAlsoModifier ao seu projeto.

public class AndAlsoModifier : ExpressionVisitor
{
    public Expression Modify(Expression expression)
    {
        return Visit(expression);
    }

    protected override Expression VisitBinary(BinaryExpression b)
    {
        if (b.NodeType == ExpressionType.AndAlso)
        {
            Expression left = this.Visit(b.Left);
            Expression right = this.Visit(b.Right);

            // Make this binary expression an OrElse operation instead of an AndAlso operation.
            return Expression.MakeBinary(ExpressionType.OrElse, left, right, b.IsLiftedToNull, b.Method);
        }

        return base.VisitBinary(b);
    }
}

Essa classe herda a classe ExpressionVisitor e é especializada para modificar expressões que representam operações AND condicionais. Ela muda essas operações de uma AND condicional para uma OR condicional. A classe substitui o método VisitBinary do tipo base, pois as expressões condicionais AND são representadas como expressões binárias. No método VisitBinary, se a expressão que é passada a ele representa uma operação AND condicional, o código cria uma nova expressão que contém o operador OR condicional em vez do operador AND condicional. Se a expressão passada para o VisitBinary não representa uma operação AND condicional, o método adia para a implementação da classe base. Os métodos da classe base constroem nós semelhantes às árvores de expressão passadas, mas as subárvores dos nós são substituídas pelas árvores de expressão produzidas de maneira recorrente pelo visitante.

Adicione uma diretiva using ao arquivo para o namespace System.Linq.Expressions. Adicione código ao método Main no arquivo Program.cs para criar uma árvore de expressão e passá-la ao método que a modifica.

Expression<Func<string, bool>> expr = name => name.Length > 10 && name.StartsWith("G");
Console.WriteLine(expr);

AndAlsoModifier treeModifier = new AndAlsoModifier();
Expression modifiedExpr = treeModifier.Modify((Expression)expr);

Console.WriteLine(modifiedExpr);

/*  This code produces the following output:

    name => ((name.Length > 10) && name.StartsWith("G"))
    name => ((name.Length > 10) || name.StartsWith("G"))
*/

O código cria uma expressão que contém uma operação AND condicional. Em seguida, ele cria uma instância da classe AndAlsoModifier e passa a expressão ao método Modify dessa classe. A árvore de expressão original e a modificada são geradas para mostrar a alteração. Compile e execute o aplicativo.

Saiba mais

Este exemplo mostra um pequeno subconjunto do código que você compilaria para percorrer e interpretar os algoritmos representados por uma árvore de expressão. Para obter informações sobre como criar uma biblioteca de uso geral que converte árvores de expressão em outra linguagem, leia esta série de Matt Warren. Ele entra em detalhes de como mover qualquer código que você pode encontrar em uma árvore de expressão.

Espero que você tenha visto o verdadeiro potencial das árvores de expressão. Você examina um conjunto de códigos, faz as alterações que deseja nesse código e executa a versão modificada. Como as árvores de expressão são imutáveis, você cria árvores usando os componentes de árvores existentes. A reutilização de nós minimiza a quantidade de memória necessária para criar árvores de expressão modificadas.