Mover árvores de expressão

Neste artigo, você aprenderá a visitar cada nó em uma árvore de expressão ao criar uma cópia modificada dessa árvore de expressão. Você traduz árvores de expressão para entender os algoritmos e para que possam ser adaptados a outro ambiente. Você altera o algoritmo que foi 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 novos nós que você colocou na árvore.

Vamos acessar uma árvore de expressão e criar uma árvore com alguns nós de substituição. Neste exemplo, vamos substituir qualquer constante por uma constante 10 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ê faz essa substituição substituindo o nó constante por um novo nó que executa a multiplicação.

Aqui, depois de encontrar um nó constante, você cria um novo nó de multiplicação cujos filhos sã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. Verifique 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 de visitar os nós na árvore existente e criar novos nós e inseri-los na árvore. O exemplo anterior mostra a importância das árvores de expressão serem imutáveis. Observe que a nova á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. Reutilização de nós resulta em eficiências significativas de memória. Os mesmos nós podem ser usados ao longo de uma á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. Nesta nova versão, o visitante retorna a soma parcial da operação de adição até este ponto. Para uma expressão constante, é simplesmente o valor da expressão 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);

Há um pouco de código aqui, 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. Depois de todos os nós na árvore de expressão terem sido visitados, a soma foi computada. Você pode monitorar a execução rodando o exemplo no depurador e acompanhando o processo.

Vamos facilitar o rastreamento de como os nós são analisados e como a soma é computada atravessando a árvore. Aqui está uma versão atualizada do método Aggregate que inclui um pouco de informações 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");
}

Executar isto na expressão sum resulta na seguinte saída:

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, vamos examinar uma execução diferente, com a expressão fornecida por sum1:

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

Aqui está a saída da análise desta 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, o percurso da árvore é diferente. Os nós são percorridos em uma ordem diferente, porque a árvore foi construída com operações diferentes ocorrendo primeiro.

Criar uma cópia modificada

Crie um novo projeto de Aplicativo de Console . Adicione uma using diretiva ao arquivo para o System.Linq.Expressions namespace. Adicione a AndAlsoModifier classe 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 ExpressionVisitor classe e é especializada para modificar expressões que representam operações condicionais AND . Altera essas operações de uma condicional AND para uma condicional OR. A classe substitui o VisitBinary método do tipo base, pois expressões condicionais AND são representadas como expressões binárias. VisitBinary No método, se a expressão passada para ela representar uma operação condicionalAND, o código construirá uma nova expressão que contenha o operador condicional OR em vez do operador condicionalAND. Se a expressão passada para VisitBinary não representar uma operação condicional AND, o método reverterá 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 using diretiva ao arquivo para o System.Linq.Expressions namespace. Adicione código ao Main método no arquivo Program.cs para criar uma árvore de expressão e passá-la para o método que o 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 condicional AND . Em seguida, ele cria uma instância da AndAlsoModifier classe e passa a expressão para o Modify método dessa classe. As árvores de expressão original e 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 finalidade geral que traduz árvores de expressão em outra linguagem, leia esta série por Matt Warren. Ele entra em detalhes sobre como traduzir qualquer um dos códigos 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 todas as alterações desejadas nesse código e executa a versão alterada. Como as árvores de expressão são imutáveis, você cria novas árvores usando os componentes das árvores existentes. Reutilizar nós minimiza a quantidade de memória necessária para criar árvores de expressão modificadas.