Instrumenting an expression tree -- How to get the computed result of each subtree?

Question

Instrumenting an expression tree -- How to get the computed result of each subtree?

c# expression-trees instrumentation logging

Question

I'm doing some work in Expression Trees, a rules engine of sorts.

When you call ToString() on an Expression Tree, you get a lovely bit of diagnostic text:

 ((Param_0.Customer.LastName == "Doe") 
     AndAlso ((Param_0.Customer.FirstName == "John") 
     Or (Param_0.Customer.FirstName == "Jane")))

I wrote this bit of code, in an attempt to wrap the Expression with some logging capability:

public Expression WithLog(Expression exp)
{
    return Expression.Block(Expression.Call(
        typeof (Debug).GetMethod("Print",
            new Type [] { typeof(string) }),
            new [] { Expression.Call(Expression.Constant(exp),
            exp.GetType().GetMethod("ToString")) } ), exp);
}

This should allow me to insert logging at various places within the expression tree and get intermediate ToString() results when the expression tree executes.

What I haven't quite figured out is how to get the computed result of each sub-expression and include it in the log output. Ideally, I would like to see output that looks something like this, for diagnostic and auditing purposes:

Executing Rule: (Param_0.Customer.LastName == "Doe") --> true
Executing Rule: (Param_0.Customer.FirstName == "John") --> true
Executing Rule: (Param_0.Customer.FirstName == "Jane") --> false
Executing Rule: (Param_0.Customer.FirstName == "John") Or (Param_0.Customer.FirstName == "Jane")) --> true
Executing Rule: (Param_0.Customer.LastName == "Doe") AndAlso ((Param_0.Customer.FirstName == "John") Or (Param_0.Customer.FirstName == "Jane")) --> true

I suspect that I either need to walk the tree using ExpressionVisitor and add some code to each node, or walk the tree and compile and execute each subtree individually, but I haven't quite figured out how to make this work yet.

Any suggestions?

Robert Harvey

When using an `Interpret()` method

You will want to introduce a new expression type LoggedExpression with the following semantics:

it contains one expression
when evaluated, it evaluates the child node and prints out the stringified child node and result:

class LoggedExpression : Expression {
  private Expression child;
  public LoggedExpression(Expression child) { ... }
  public string ToString() { return child.ToString(); }
  public bool Interpret() {
    bool result = child.Interpret();
    log("Executing rule: " + child + " --> " + result);
    return result;
  }
}

If your language is more complex that simple boolean expressions, you would want to log before evaluating, so that you can easily debug hangups etc.

You will then have to transform your expression tree to a logged expression tree. This can easily be done by a method AsLoggedExpression(), that copies each node but wraps it in a log expression:

class Or : Expression {
  private Expression left;
  private Expression right;
  ...
  public Expression AsLoggedExpression() {
    return new LoggedExpression(new Or(left.AsLoggedExpression(), right.AsLoggedExpression()));
  }
}

Some nodes may return themselves unchanged instead of adding logging, e.g. constants or logging expressions themselves (as such, adding logging to a tree would be an idempotent operation).

When using a visitor

Each visit() method in the visitor takes care of evaluating an expression tree node. Given your main ExpressionInterpreter visitor, we can derive a LoggingExpressionInterpreter that for each node type logs the expression and evaluates it:

class LoggingExpressionInterpreter : ExpressionInterpreter {
  ...
  public bool Visit(Expression.Or ast) {
    bool result = base.Visit(ast);
    log("Executing rule: " + child + " --> " + result);
    return result;
  }
}

Here, we cannot use composition instead of inheritance because that would break recursive logging. It is fundamental that when evaluating any node, the logging interpreter is also used for all child nodes. If we would do away with inheritance, the Visit() and AcceptVisitor() methods would need an explicit argument for the visitor that should be applied to the child nodes.

I would strongly prefer the visitor-based method since it doesn't have to modify the expression tree, and results in less total code (I guess).

amon

View more on Stack Overflow

Shlomo · Accepted Answer · 1/4/2016 10:22:49 PM

While amon's post is correct in theory, there isn't an interpreter (that I know of) for C# ExpressionTrees. However, there is a compiler, and there is a nice abstract visitor which would work well for this purpose.

public class Program
{
    static void Main(string[] args)
    {

        Expression<Func<int, bool>> x = (i => i > 3 && i % 4 == 0);
        var visitor = new GetSubExpressionVisitor();
        var visited = (Expression<Func<int, bool>>)visitor.Visit(x);
        var func = visited.Compile();
        var result = func(4);
    }
}

public class GetSubExpressionVisitor : ExpressionVisitor
{
    private readonly List<ParameterExpression> _parameters = new List<ParameterExpression>();

    protected override Expression VisitLambda<T>(Expression<T> node)
    {
        _parameters.AddRange(node.Parameters);
        return base.VisitLambda(node);
    }

    protected override Expression VisitBinary(BinaryExpression node)
    {
        switch (node.NodeType)
        {
            case ExpressionType.Modulo:
            case ExpressionType.Equal:
            case ExpressionType.GreaterThanOrEqual:
            case ExpressionType.LessThanOrEqual:
            case ExpressionType.NotEqual:
            case ExpressionType.GreaterThan:
            case ExpressionType.LessThan:
            case ExpressionType.And:
            case ExpressionType.AndAlso:
            case ExpressionType.Or:
            case ExpressionType.OrElse:
                return WithLog(node);
        }
        return base.VisitBinary(node);
    }

    public Expression WithLog(BinaryExpression exp)
    {
        return Expression.Block(
            Expression.Call(
                typeof(Debug).GetMethod("Print", new Type[] { typeof(string) }),
                new[] 
                { 
                    Expression.Call(
                        typeof(string).GetMethod("Format", new [] { typeof(string), typeof(object), typeof(object)}),
                        Expression.Constant("Executing Rule: {0} --> {1}"),
                        Expression.Call(Expression.Constant(exp), exp.GetType().GetMethod("ToString")),
                        Expression.Convert(
                            exp,
                            typeof(object)
                        )
                    )
                }
            ),
            base.VisitBinary(exp)
        );
    }
}

I'm not entirely sure how well this code will work if you have a nested lambda, but if you don't have such a thing, this should do it.

Incorporated WithLog code. The code outputs the following:

Executing Rule: ((i > 3) AndAlso ((i % 4) == 0)) --> True
Executing Rule: (i > 3) --> True
Executing Rule: ((i % 4) == 0) --> True
Executing Rule: (i % 4) --> 0

Instrumenting an expression tree -- How to get the computed result of each subtree?

Question

Fastest Entity Framework Extensions

Accepted Answer

Popular Answer

When using an `Interpret()` method

When using a visitor

Performance

Expression Evaluator

Instrumenting an expression tree -- How to get the computed result of each subtree?

Question

Fastest Entity Framework Extensions

Accepted Answer

Popular Answer

When using an Interpret() method

When using a visitor

Performance

Expression Evaluator

When using an `Interpret()` method