Преобразование деревьев выражений

Из этой статьи вы узнаете, как посетить каждый узел в дереве выражений при создании измененной копии этого дерева выражений. Вы преобразуете деревья выражений, чтобы понять алгоритмы, чтобы их можно было преобразовать в другую среду. Вы изменяете созданный алгоритм. Вы можете добавлять журналы, перехватывать вызовы методов и отслеживать их или другие цели.

Код, создаваемый для преобразования дерева выражения, является расширением кода, который используется для обхода всех узлов в дереве. Во время преобразования дерева выражения вы выполняете обход всех узлов и, таким образом, построение нового дерева. Новое дерево может содержать ссылки на исходные узлы или новые узлы, которые вы разместили в дереве.

Давайте перейдем к дереву выражений и создадим новое дерево с некоторыми узлами замены. В этом примере давайте заменим любую константу константой, которая в 10 раз больше. В противном случае дерево выражений остается нетронутым. Вместо того, чтобы считывать значение константы и заменять его новой константой, необходимо заменить узел константы новым узлом, выполняющим умножение.

Здесь, после того как вы найдете узел константы, вы создаете новый узел умножения, дочерними элементами которого являются исходная константа и константа 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;
}

Создайте новое дерево, заменив исходный узел заменой. Чтобы проверить изменения, выполните компиляцию и выполнение замененного дерева.

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

Создание нового дерева представляет собой сочетание обхода узлов в существующем дереве и создания новых узлов и вставки их в дерево. В предыдущем примере показано, как важно, чтобы деревья выражений были неизменяемыми. Обратите внимание, что новое дерево, созданное в предыдущем коде, содержит смесь только что созданных узлов и узлов из существующего дерева. Узлы можно использовать в обоих деревьях, так как узлы в существующем дереве нельзя изменить. Повторное использование узлов приводит к значительной эффективности памяти. Одни и те же узлы можно использовать в одном дереве или в нескольких деревьях выражений. Поскольку узлы нельзя изменить, один узел можно при необходимости использовать повторно.

Обход и выполнение сложения

Давайте проверим новое дерево, создав второго посетителя, который проходит дерево узлов сложения и вычисляет результат. Внесите несколько изменений в посетителей, которые вы видели до сих пор. В этой новой версии посетитель возвращает частичную сумму операции сложения до этой точки. Для константного выражения это просто значение константного выражения. Для выражения добавления результатом будет сумма левого и правого операндов, поскольку выполняется обход этих деревьев.

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

Здесь есть довольно много кода, но концепции доступны. Этот код обходит дочерние элементы при поиске в глубину. При обнаружении узла константы посетитель возвращает значение этой константы. После посещения обоих детей посетитель вычислил сумму, вычисленную для этого поддеревья. Теперь добавленный узел может вычислить свою сумму. После посещения всех узлов в дереве выражений вычисляется сумма. Вы можете отслеживать выполнение, запустив пример в отладчике с трассировкой выполнения.

Мы можем упростить трассировку анализа узлов и вычисления суммы путем обхода дерева. Вот обновленная версия метода агрегирования, который включает совсем немного данных трассировки:

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

При его выполнении в sum выражении выводятся следующие выходные данные:

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

Выполните трассировку выходных данных и выполните инструкции в приведенном выше коде. Вы наверняка поймете, каким образом код обходит каждый узел и вычисляет сумму по мере обхода дерева и нахождения суммы.

Теперь рассмотрим другое выполнение, где выражение задается объектом sum1:

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

Ниже вы видите выходные данные проверки этого выражения:

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

Хотя окончательный ответ совпадает, обход дерева отличается. Узлы обходятся в другом порядке, так как дерево было создано с помощью других начальных операций.

Создание измененной копии

Создайте новый проект консольного приложения. Добавьте в файл директиву using для пространства имен System.Linq.Expressions. Добавьте в проект класс AndAlsoModifier.

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

Этот класс наследует класс ExpressionVisitor и специально предназначен для изменения выражений, которые представляют условные операции AND. Он изменяет эти операции с условного AND на условное OR. Класс переопределяет VisitBinary метод базового типа, так как условные AND выражения представлены в виде двоичных выражений. Если выражение, переданное в метод VisitBinary, представляет условную операцию AND, код создает новое выражение, которое содержит условный оператор OR вместо условного оператора AND. Если выражение, передаваемое в VisitBinary , не представляет условную AND операцию, метод откладывается на реализацию базового класса. Методы базового класса создают узлы, которые похожи на передаваемые деревья выражений, но их вложенные деревья заменяются деревьями выражений, созданными посетителем рекурсивно.

Добавьте в файл директиву using для пространства имен System.Linq.Expressions. Добавьте код в Main метод в файле Program.cs, чтобы создать дерево выражений и передать его методу, который изменяет его.

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"))
*/

В приведенном ниже коде создается выражение, которое содержит условную операцию AND. Затем в нем создается экземпляр класса AndAlsoModifier, и в метод Modify этого класса передается выражение. Как исходные, так и измененные деревья выражений выводятся для отображения изменения. Скомпилируйте и запустите приложение.

Подробнее

В этом примере показана малая часть кода, который необходимо создать для обхода и интерпретации алгоритмов, представляемых деревом выражения. Сведения о создании библиотеки общего назначения, которая переводит деревья выражений на другой язык, см. в этой серии работ Мэтта Уоррена. Здесь преобразование кода, который можно найти в дереве выражения, рассматривается гораздо подробнее.

Теперь вы увидели истинную силу деревьев выражений. Вы изучаете набор кода, вносите необходимые изменения в этот код и выполняете измененную версию. Так как деревья выражений являются неизменяемыми, новые деревья создаются с помощью компонентов существующих деревьев. Повторное использование узлов сводит к минимуму объем памяти, необходимый для создания измененных деревьев выражений.