How to determine the depth of a C# Expression Tree Iterativly?

c#, expression, lambda

Solution

The `ExpressionVisitor` that is included in .Net is recursive, but using a trick, you can turn it into an iterative one.

Basically, you're processing a queue of nodes. For each node in the queue, use `base.Visit()` to visit all of its children, but then add those children into the queue instead of recursively processing them right away.

This way, you don't have to write code specific to each `Expression` subtype, but you also work around the recursive nature of `ExpressionVisitor`.

class DepthVisitor : ExpressionVisitor
{
    private readonly Queue<Tuple<Expression, int>> m_queue =
        new Queue<Tuple<Expression, int>>();
    private bool m_canRecurse;
    private int m_depth;

    public int MeasureDepth(Expression expression)
    {
        m_queue.Enqueue(Tuple.Create(expression, 1));

        int maxDepth = 0;

        while (m_queue.Count > 0)
        {
            var tuple = m_queue.Dequeue();
            m_depth = tuple.Item2;

            if (m_depth > maxDepth)
                maxDepth = m_depth;

            m_canRecurse = true;

            Visit(tuple.Item1);
        }

        return maxDepth;
    }

    public override Expression Visit(Expression node)
    {
        if (m_canRecurse)
        {
            m_canRecurse = false;
            base.Visit(node);
        }
        else
            m_queue.Enqueue(Tuple.Create(node, m_depth + 1));

        return node;
    }
}

Problem

I am trying to figure out if there is a good way to figure out the depth of a particular C# Expression Tree using an iterative approach. We use expressions for some dynamic evaluation and under rare (error) conditions, the system can try to process an Expression Tree that is so large that it blows out the stack. I'm trying to figure out a way to check the depth of the tree prior to allowing the tree to be evaluated.

Original source

Related problems