Поделиться через

Интерпретация выражений

  • Статья

В следующем примере кода показано, как дерево выражений, представляющее лямбда-выражение num => num < 5, может быть разложено на части.

// Add the following using directive to your code file:
// using System.Linq.Expressions;

// Create an expression tree.
Expression<Func<int, bool>> exprTree = num => num < 5;

// Decompose the expression tree.
ParameterExpression param = (ParameterExpression)exprTree.Parameters[0];
BinaryExpression operation = (BinaryExpression)exprTree.Body;
ParameterExpression left = (ParameterExpression)operation.Left;
ConstantExpression right = (ConstantExpression)operation.Right;

Console.WriteLine("Decomposed expression: {0} => {1} {2} {3}",
                  param.Name, left.Name, operation.NodeType, right.Value);

// This code produces the following output:

// Decomposed expression: num => num LessThan 5

Теперь напишем код для проверки структуры дерева выражения. Каждый узел в дереве выражений — это объект класса, производный от Expression.

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

Если тип узла имеет дочерние элементы, их нужно посетить в рекурсивном режиме. На каждом дочернем узле повторите процесс, используемый на корневом узле: определите тип и, если тип имеет дочерние элементы, пройдите по каждому из них.

Проверка выражения без дочерних элементов

Начнем с посещения каждого узла в простом дереве выражения. Ниже приведен код, который создает константное выражение, а затем проверяет его свойства:

var constant = Expression.Constant(24, typeof(int));

Console.WriteLine($"This is a/an {constant.NodeType} expression type");
Console.WriteLine($"The type of the constant value is {constant.Type}");
Console.WriteLine($"The value of the constant value is {constant.Value}");

Предыдущий код выводит следующие выходные данные:

This is a/an Constant expression type
The type of the constant value is System.Int32
The value of the constant value is 24

Теперь напишем код, который будет проверять это выражение и записывать некоторые важные свойства.

Выражение сложения

Начнем с примера сложения из вводной части к этому разделу.

Expression<Func<int>> sum = () => 1 + 2;

Примечание.

Не используйтеvar для объявления этого дерева выражений, так как естественный тип делегата Func<int>, а не Expression<Func<int>>.

LambdaExpression — это корневой узел. Для получения нужного кода в правой части оператора => следует найти один из дочерних элементов LambdaExpression. Это можно сделать со всеми выражениями в этом разделе. Благодаря родительскому узлу можно найти возвращаемый тип LambdaExpression.

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

Expression<Func<int, int, int>> addition = (a, b) => a + b;

Console.WriteLine($"This expression is a {addition.NodeType} expression type");
Console.WriteLine($"The name of the lambda is {((addition.Name == null) ? "<null>" : addition.Name)}");
Console.WriteLine($"The return type is {addition.ReturnType.ToString()}");
Console.WriteLine($"The expression has {addition.Parameters.Count} arguments. They are:");
foreach (var argumentExpression in addition.Parameters)
{
    Console.WriteLine($"\tParameter Type: {argumentExpression.Type.ToString()}, Name: {argumentExpression.Name}");
}

var additionBody = (BinaryExpression)addition.Body;
Console.WriteLine($"The body is a {additionBody.NodeType} expression");
Console.WriteLine($"The left side is a {additionBody.Left.NodeType} expression");
var left = (ParameterExpression)additionBody.Left;
Console.WriteLine($"\tParameter Type: {left.Type.ToString()}, Name: {left.Name}");
Console.WriteLine($"The right side is a {additionBody.Right.NodeType} expression");
var right = (ParameterExpression)additionBody.Right;
Console.WriteLine($"\tParameter Type: {right.Type.ToString()}, Name: {right.Name}");

Результатом является следующее:

This expression is a/an Lambda expression type
The name of the lambda is <null>
The return type is System.Int32
The expression has 2 arguments. They are:
        Parameter Type: System.Int32, Name: a
        Parameter Type: System.Int32, Name: b
The body is a/an Add expression
The left side is a Parameter expression
        Parameter Type: System.Int32, Name: a
The right side is a Parameter expression
        Parameter Type: System.Int32, Name: b

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

using System.Linq.Expressions;

namespace Visitors;
// Base Visitor class:
public abstract class Visitor
{
    private readonly Expression node;

    protected Visitor(Expression node) => this.node = node;

    public abstract void Visit(string prefix);

    public ExpressionType NodeType => node.NodeType;
    public static Visitor CreateFromExpression(Expression node) =>
        node.NodeType switch
        {
            ExpressionType.Constant => new ConstantVisitor((ConstantExpression)node),
            ExpressionType.Lambda => new LambdaVisitor((LambdaExpression)node),
            ExpressionType.Parameter => new ParameterVisitor((ParameterExpression)node),
            ExpressionType.Add => new BinaryVisitor((BinaryExpression)node),
            _ => throw new NotImplementedException($"Node not processed yet: {node.NodeType}"),
        };
}

// Lambda Visitor
public class LambdaVisitor : Visitor
{
    private readonly LambdaExpression node;
    public LambdaVisitor(LambdaExpression node) : base(node) => this.node = node;

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This expression is a {NodeType} expression type");
        Console.WriteLine($"{prefix}The name of the lambda is {((node.Name == null) ? "<null>" : node.Name)}");
        Console.WriteLine($"{prefix}The return type is {node.ReturnType}");
        Console.WriteLine($"{prefix}The expression has {node.Parameters.Count} argument(s). They are:");
        // Visit each parameter:
        foreach (var argumentExpression in node.Parameters)
        {
            var argumentVisitor = CreateFromExpression(argumentExpression);
            argumentVisitor.Visit(prefix + "\t");
        }
        Console.WriteLine($"{prefix}The expression body is:");
        // Visit the body:
        var bodyVisitor = CreateFromExpression(node.Body);
        bodyVisitor.Visit(prefix + "\t");
    }
}

// Binary Expression Visitor:
public class BinaryVisitor : Visitor
{
    private readonly BinaryExpression node;
    public BinaryVisitor(BinaryExpression node) : base(node) => this.node = node;

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This binary expression is a {NodeType} expression");
        var left = CreateFromExpression(node.Left);
        Console.WriteLine($"{prefix}The Left argument is:");
        left.Visit(prefix + "\t");
        var right = CreateFromExpression(node.Right);
        Console.WriteLine($"{prefix}The Right argument is:");
        right.Visit(prefix + "\t");
    }
}

// Parameter visitor:
public class ParameterVisitor : Visitor
{
    private readonly ParameterExpression node;
    public ParameterVisitor(ParameterExpression node) : base(node)
    {
        this.node = node;
    }

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This is an {NodeType} expression type");
        Console.WriteLine($"{prefix}Type: {node.Type}, Name: {node.Name}, ByRef: {node.IsByRef}");
    }
}

// Constant visitor:
public class ConstantVisitor : Visitor
{
    private readonly ConstantExpression node;
    public ConstantVisitor(ConstantExpression node) : base(node) => this.node = node;

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This is an {NodeType} expression type");
        Console.WriteLine($"{prefix}The type of the constant value is {node.Type}");
        Console.WriteLine($"{prefix}The value of the constant value is {node.Value}");
    }
}

Этот алгоритм является основой алгоритма, который посещает любой произвольный LambdaExpression. Созданный код ищет только небольшой пример возможных наборов узлов дерева выражений, с которыми он может столкнуться. Однако в результатах вы по-прежнему сможете находить полезные данные. (По умолчанию в Visitor.CreateFromExpression методе выводится сообщение в консоль ошибок при обнаружении нового типа узла. Таким образом, вы знаете, чтобы добавить новый тип выражения.)

При запуске этого посетителя в предыдущем выражении сложения вы получите следующие выходные данные:

This expression is a/an Lambda expression type
The name of the lambda is <null>
The return type is System.Int32
The expression has 2 argument(s). They are:
        This is an Parameter expression type
        Type: System.Int32, Name: a, ByRef: False
        This is an Parameter expression type
        Type: System.Int32, Name: b, ByRef: False
The expression body is:
        This binary expression is a Add expression
        The Left argument is:
                This is an Parameter expression type
                Type: System.Int32, Name: a, ByRef: False
        The Right argument is:
                This is an Parameter expression type
                Type: System.Int32, Name: b, ByRef: False

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

Добавление выражения с дополнительными операндами

Рассмотрим более сложный пример, но по-прежнему ограничим типы узлов только сложением:

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

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

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

Expression<Func<int>> sum3 = () => (1 + 2) + (3 + 4);
Expression<Func<int>> sum4 = () => 1 + ((2 + 3) + 4);
Expression<Func<int>> sum5 = () => (1 + (2 + 3)) + 4;

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

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

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

Expression<Func<int, int>> sum = (a) => 1 + a + 3 + 4;

Создайте посетителя для этой суммы и запустите посетителей, которые вы видите в этом выходных данных:

This expression is a/an Lambda expression type
The name of the lambda is <null>
The return type is System.Int32
The expression has 1 argument(s). They are:
        This is an Parameter expression type
        Type: System.Int32, Name: a, ByRef: False
The expression body is:
        This binary expression is a Add expression
        The Left argument is:
                This binary expression is a Add expression
                The Left argument is:
                        This binary expression is a Add expression
                        The Left argument is:
                                This is an Constant expression type
                                The type of the constant value is System.Int32
                                The value of the constant value is 1
                        The Right argument is:
                                This is an Parameter expression type
                                Type: System.Int32, Name: a, ByRef: False
                The Right argument is:
                        This is an Constant expression type
                        The type of the constant value is System.Int32
                        The value of the constant value is 3
        The Right argument is:
                This is an Constant expression type
                The type of the constant value is System.Int32
                The value of the constant value is 4

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

Expression<Func<int, int, int>> sum3 = (a, b) => (1 + a) + (3 + b);

Вот результат посетителя:

This expression is a/an Lambda expression type
The name of the lambda is <null>
The return type is System.Int32
The expression has 2 argument(s). They are:
        This is an Parameter expression type
        Type: System.Int32, Name: a, ByRef: False
        This is an Parameter expression type
        Type: System.Int32, Name: b, ByRef: False
The expression body is:
        This binary expression is a Add expression
        The Left argument is:
                This binary expression is a Add expression
                The Left argument is:
                        This is an Constant expression type
                        The type of the constant value is System.Int32
                        The value of the constant value is 1
                The Right argument is:
                        This is an Parameter expression type
                        Type: System.Int32, Name: a, ByRef: False
        The Right argument is:
                This binary expression is a Add expression
                The Left argument is:
                        This is an Constant expression type
                        The type of the constant value is System.Int32
                        The value of the constant value is 3
                The Right argument is:
                        This is an Parameter expression type
                        Type: System.Int32, Name: b, ByRef: False

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

Расширение этого примера

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

Expression<Func<int, int>> factorial = (n) =>
    n == 0 ?
    1 :
    Enumerable.Range(1, n).Aggregate((product, factor) => product * factor);

Этот код представляет одну из возможных реализаций для математической функции — факториала. Способ написания этого кода выделяет два ограничения для создания деревьев выражений путем назначения лямбда-выражений выражениям. Во-первых, лямбда-выражения инструкции не допускаются. Это означает, что вы не можете использовать циклы, блоки, операторы if / else и другие структуры управления, распространенные в C#. Вы ограничены использованием выражений. Во-вторых, вы не можете рекурсивно вызывать то же выражение. Можно было бы, если бы он уже был делегатом, но его нельзя назвать в виде дерева выражений. В разделе о создании деревьев выражений вы узнаете, как преодолеть эти ограничения.

В этом выражении возникают узлы всех этих типов:

  1. Equal (двоичное выражение)
  2. Multiply (двоичное выражение)
  3. Условный ? : (выражение)
  4. Выражение вызова метода (вызов Range() и Aggregate())

Одним из способов изменения алгоритма посетителя является поддержка его выполнения и запись типа узла при каждом достижении предложения default. После нескольких итераций вы увидите каждый из потенциальных узлов. Итак, у вас есть все, что нужно. Результат будет выглядеть примерно следующим образом:

public static Visitor CreateFromExpression(Expression node) =>
    node.NodeType switch
    {
        ExpressionType.Constant    => new ConstantVisitor((ConstantExpression)node),
        ExpressionType.Lambda      => new LambdaVisitor((LambdaExpression)node),
        ExpressionType.Parameter   => new ParameterVisitor((ParameterExpression)node),
        ExpressionType.Add         => new BinaryVisitor((BinaryExpression)node),
        ExpressionType.Equal       => new BinaryVisitor((BinaryExpression)node),
        ExpressionType.Multiply    => new BinaryVisitor((BinaryExpression) node),
        ExpressionType.Conditional => new ConditionalVisitor((ConditionalExpression) node),
        ExpressionType.Call        => new MethodCallVisitor((MethodCallExpression) node),
        _ => throw new NotImplementedException($"Node not processed yet: {node.NodeType}"),
    };

И MethodCallVisitor обработайте ConditionalVisitor эти два узла:

public class ConditionalVisitor : Visitor
{
    private readonly ConditionalExpression node;
    public ConditionalVisitor(ConditionalExpression node) : base(node)
    {
        this.node = node;
    }

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This expression is a {NodeType} expression");
        var testVisitor = Visitor.CreateFromExpression(node.Test);
        Console.WriteLine($"{prefix}The Test for this expression is:");
        testVisitor.Visit(prefix + "\t");
        var trueVisitor = Visitor.CreateFromExpression(node.IfTrue);
        Console.WriteLine($"{prefix}The True clause for this expression is:");
        trueVisitor.Visit(prefix + "\t");
        var falseVisitor = Visitor.CreateFromExpression(node.IfFalse);
        Console.WriteLine($"{prefix}The False clause for this expression is:");
        falseVisitor.Visit(prefix + "\t");
    }
}

public class MethodCallVisitor : Visitor
{
    private readonly MethodCallExpression node;
    public MethodCallVisitor(MethodCallExpression node) : base(node)
    {
        this.node = node;
    }

    public override void Visit(string prefix)
    {
        Console.WriteLine($"{prefix}This expression is a {NodeType} expression");
        if (node.Object == null)
            Console.WriteLine($"{prefix}This is a static method call");
        else
        {
            Console.WriteLine($"{prefix}The receiver (this) is:");
            var receiverVisitor = Visitor.CreateFromExpression(node.Object);
            receiverVisitor.Visit(prefix + "\t");
        }

        var methodInfo = node.Method;
        Console.WriteLine($"{prefix}The method name is {methodInfo.DeclaringType}.{methodInfo.Name}");
        // There is more here, like generic arguments, and so on.
        Console.WriteLine($"{prefix}The Arguments are:");
        foreach (var arg in node.Arguments)
        {
            var argVisitor = Visitor.CreateFromExpression(arg);
            argVisitor.Visit(prefix + "\t");
        }
    }
}

Будет получен следующий результат для дерева выражения:

This expression is a/an Lambda expression type
The name of the lambda is <null>
The return type is System.Int32
The expression has 1 argument(s). They are:
        This is an Parameter expression type
        Type: System.Int32, Name: n, ByRef: False
The expression body is:
        This expression is a Conditional expression
        The Test for this expression is:
                This binary expression is a Equal expression
                The Left argument is:
                        This is an Parameter expression type
                        Type: System.Int32, Name: n, ByRef: False
                The Right argument is:
                        This is an Constant expression type
                        The type of the constant value is System.Int32
                        The value of the constant value is 0
        The True clause for this expression is:
                This is an Constant expression type
                The type of the constant value is System.Int32
                The value of the constant value is 1
        The False clause for this expression is:
                This expression is a Call expression
                This is a static method call
                The method name is System.Linq.Enumerable.Aggregate
                The Arguments are:
                        This expression is a Call expression
                        This is a static method call
                        The method name is System.Linq.Enumerable.Range
                        The Arguments are:
                                This is an Constant expression type
                                The type of the constant value is System.Int32
                                The value of the constant value is 1
                                This is an Parameter expression type
                                Type: System.Int32, Name: n, ByRef: False
                        This expression is a Lambda expression type
                        The name of the lambda is <null>
                        The return type is System.Int32
                        The expression has 2 arguments. They are:
                                This is an Parameter expression type
                                Type: System.Int32, Name: product, ByRef: False
                                This is an Parameter expression type
                                Type: System.Int32, Name: factor, ByRef: False
                        The expression body is:
                                This binary expression is a Multiply expression
                                The Left argument is:
                                        This is an Parameter expression type
                                        Type: System.Int32, Name: product, ByRef: False
                                The Right argument is:
                                        This is an Parameter expression type
                                        Type: System.Int32, Name: factor, ByRef: False

Расширение библиотеки примеров

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

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

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

Наконец, библиотека, используемая в этой статье, была создана для демонстрации и обучения. Она не оптимизирована. Это делает структуры понятными, и чтобы выделить методы, используемые для посещения узлов и анализа того, что там.

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