2010 05 24 how a visitor implementation can handle unknown nodes

Published on April 10th, 2010 at 17:45

How a Visitor implementation can handle unknown nodes

Two weeks ago, I explained how we use interfaces and dynamic type casts to overcome the Visitor pattern’s problems with extensible class hierarchies in re-linq. In a nutshell, we have a visitor base class, ExpressionTreeVisitor, with Visit... methods for all standard expression node types. For extension nodes, we define specific visitor interfaces, and we test whether a specific visitor instance supports the interface using a runtime type check. This pattern is known as the Acyclic Visitor pattern (to some, at least…).

Here’s an example; the Accept method of SqlCaseExpression (an extension node type):

public override Expression Accept (ExpressionTreeVisitor visitor)
{
  ArgumentUtility.CheckNotNull ("visitor", visitor);

  var specificVisitor = visitor as ISqlSpecificExpressionVisitor;
  if (specificVisitor != null)
    return specificVisitor.VisitSqlCaseExpression (this);
  else
    return base.Accept (visitor);
}

The base class’ Accept method, which is called if the visitor instance does not support the extension node, is implemented as follows:

public virtual Expression Accept (ExpressionTreeVisitor visitor)
{
  ArgumentUtility.CheckNotNull ("visitor", visitor);

  return visitor.VisitUnknownExpression (this);
}

Last time I said that there were three possibilities of how the VisitUnknownExpression method could be implemented in a specific visitor: it could ignore the unknown expression, it could throw an exception, or do … something else. But what could that third option be?

The answer sounds simple: Handle the unknown node in a generic way.

Sometimes, that’s easy. For example, re-linq has a visitor called FormattingExpressionVisitor, which is used to generate a string representation of expression trees. (We need that because the implementation of Expression.ToString() acts just plain stupid when confronted with a non-standard expression being a child of a standard one.) That visitor  handles unknown nodes in a generic way – it just calls ToString() on them.

Sometimes, it’s harder. While some expression visitors, such as a SQL-generating visitor or the FormattingExpressionTreeVisitor, are used to transform expression trees into a completely different representation, the much more common scenario is that specialized visitors search for certain node patterns. They then either return what they’ve found or transform the nodes, replacing them with other structures.

For example, consider a visitor that looks for ConditionalExpressions (the equivalent of C#’s conditional operator ?: in expression trees) and transforms those into SqlCaseExpressions:

protected override Expression VisitConditionalExpression (  
    ConditionalExpression expression)
{
  ArgumentUtility.CheckNotNull ("expression", expression);

  return new SqlCaseExpression (  
 VisitExpression (expression.Test),  
      VisitExpression (expression.IfTrue),  
      VisitExpression (expression.IfFalse));
}

How should such a pattern matching visitor handle unknown expressions in a generic way? After all, a ConditionalExpression might be located beneath any unknown expression!

Ideally, a pattern matching visitor should be able to ignore all unknown expressions and at the same time analyze the expressions’ child nodes. And, voilà, this is exactly what the default implementation of ExpressionTreeVisitor.VisitUnknownExpression does:

protected internal virtual Expression VisitUnknownExpression (  
    Expression expression)
{

  var extensionExpression = expression as ExtensionExpression;
  if (extensionExpression != null)
    return extensionExpression.VisitChildren (this);
  else
  {
    var message = string.Format (  
        "Expression type {0} is not supported by this {1}.",  
        expression.NodeType,  
        GetType().Name);

    throw new NotSupportedException (message);
  }
}

Every extension expression has a VisitChildren method used by visitors that need to visit a specific node’s children even when they don’t know the node’s type. Here’s SqlCaseExpression’s implementation of VisitChildren:

protected override Expression VisitChildren (ExpressionTreeVisitor visitor)
{
  ArgumentUtility.CheckNotNull ("visitor", visitor);

  var testPredicate = visitor.VisitExpression (TestPredicate);
  var thenValue = visitor.VisitExpression (ThenValue);
  var elseValue = visitor.VisitExpression (ElseValue);

  if (testPredicate != TestPredicate  
      || thenValue != ThenValue  
      || elseValue != ElseValue)
    return new SqlCaseExpression (testPredicate, thenValue, elseValue);
  else
    return this;
}

This clever design was not my own idea, it originates from the Dynamic Language Runtime’s abstract syntax tree implementation, and it has later been included in .NET 4.0’s Expression class. The method is called VisitExtension there; you can read my short summary of that feature in my post about .NET 4.0’s extension expressions. As I promised in that post, we copied the design for re-linq and .NET 3.5.

So, this post concludes my little series about the visitor pattern. To summarize,

• the Visitor pattern allows you to define virtual method-like behavior without modifying the classes on whose type the behavior depends;
• re-linq implements the Visitor pattern in an un-pure form because the Expression class doesn’t define an Accept method,
• interfaces and runtime type checks can be used to create visitors for extensible class hierarchies; and
• VisitChildren methods can be used to allow a Visitor implementation on an extensible class hierarchy to ignore unknown instances while still analyzing the instances’ children.

"And yet, in this instance, a function by any other name is still as virtual," she smiled, and glided away. Her words drifted off with her as she passed out of sight: "And a Visitor pattern by any other name is still as useful, and is more aptly described. But that is the way of things...."

Conversations: By Any Other Name, Jim Hyslop and Herb Sutter, Dr. Dobb’s

- Fabian