式ツリーを変換する

[アーティクル]
03/14/2023

この記事では、式ツリーを変更してコピーを作成する間に、その式ツリーの各ノードにアクセスする方法について説明します。別の環境に変換できるように、式ツリーを変換してアルゴリズムを理解します。作成されたアルゴリズムを変更します。ログの追加、メソッド呼び出しの取得と追跡、その他の目的で行うことがあります。

式ツリーを変換するために構築するコードは、既に説明した、ツリーのすべてのノードにアクセスする式です。式ツリーを変換するときに、すべてのノードにアクセスします。また、アクセスしながら新しいツリーを構築します。新しいツリーには、元のノードの参照や、ツリーに配置した新しいノードが含まれる場合があります。

式ツリーにアクセスし、置換ノードをいくつか含む新しいツリーを作成してみましょう。この例では、定数を 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);

新しいツリーの構築は、既存のツリー内のノードへのアクセスと、新しいノードの作成とツリーへの挿入を組み合わせた操作です。前の例は、式ツリーが不変であることの重要性を示しています。前のコードで作成される新しいツリーには、新しく作成されたノードと、既存のツリーのノードが混在していることに注意してください。既存のツリーのノードは変更できないため、両方のツリーでノードを使用できます。ノードを再利用すると、メモリ効率が大幅に向上します。同じノードを 1 つのツリー全体、または複数の式ツリーで使用できます。ノードは変更できないので、必要に応じていつでも同じノードを再利用できます。

加算を走査して実行する

加算ノードのツリーをたどって結果を計算する 2 つ目のビジターを作成することで、新しいツリーを検証してみましょう。これまでに見てきたビジターに対していくつか変更を行います。この新しいバージョンのビジターは、加算演算のこのポイントまでの部分的な合計を返します。定数式の場合、これは単に定数式の値です。加算式の場合、ツリーの走査が完了すると、結果は左右のオペランドの合計になります。

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

長いコードですが、概念はわかりやすいものです。このコードでは、深さ優先検索で子にアクセスします。定数ノードが検出されると、ビジターから定数値が返されます。ビジターが両方の子にアクセスした後では、それらの子によりそのサブツリーの合計が計算されています。加算ノードで、合計を計算できるようになります。式ツリー内のすべてのノードがアクセスされると、合計が計算されます。実行をトレースするには、デバッガーでサンプルを実行して実行をトレースします。

ツリーを走査して、ノードを分析し、合計を計算する方法を簡単にしてみましょう。大量のトレース情報を含む更新版の Aggregate メソッドを次に示します。

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

最終的な答えは同じですが、ツリーの走査は異なります。ノードは別の順序で走査されます。これは、優先する演算が異なるツリーが構成されていたためです。

変更されたツリーを作成する

新しいコンソールアプリケーション プロジェクトを作成します。ファイルに System.Linq.Expressions 名前空間の using ディレクティブを追加します。 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);
    }
}

このクラスは、AND 条件演算を表す式を変更するための特別なクラスで、ExpressionVisitor クラスを継承します。このクラスによって条件 AND が条件 OR に変更されます。 AND 条件式は二項式で表されるため、クラスは基本データ型の VisitBinary メソッドをオーバーライドします。 VisitBinary メソッドでは、渡される式が AND 条件演算を表す場合、AND 条件演算子ではなく OR 条件演算子を含む新しい式がコードによって作成されます。 VisitBinary に渡される式が AND 条件演算を表さない場合、メソッドは基底クラスの実装に従います。基底クラスのメソッドによって、渡された式ツリーに似たノードが作成されますが、そのノードのサブツリーは、ビジターによって再帰的に作成される式ツリーに置き換えられます。

ファイルに System.Linq.Expressions 名前空間の using ディレクティブを追加します。式ツリーを作成して、それを変更するメソッドに渡すには、Program.cs ファイルの Main メソッドにコードを追加します。

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 メソッドにその式を渡します。元の式ツリーと変更された式ツリーの両方が出力され、変更内容が表示されます。アプリケーションをコンパイルして実行します。

詳細情報

このサンプルは、式ツリーで表されるアルゴリズムを走査し、解釈するために構築するコードのごく一部です。式ツリーを別の言語に変換する汎用ライブラリの作成については、Matt Warren によるこちらのシリーズをご覧ください。式ツリーに含まれる任意のコードを変換する方法について、詳しく説明されています。

式ツリーの真の力を見てきました。コードのセットを調べて、そのコードに必要な変更を行い、変更したバージョンを実行します。式ツリーは不変なので、既存のツリーのコンポーネントを使って新しいツリーを作成します。ノードを再利用すると、変更された式ツリーを作成するために必要なメモリの量が最小限に抑えられます。

式ツリーを変換する

加算を走査して実行する

変更されたツリーを作成する

詳細情報

フィードバック

その他のリソース