2010 04 18 linq a good visitor use case but bad implementation

Published on April 18th, 2010 at 15:50

LINQ: A good Visitor use case (but bad implementation)

Last week, I wrote about the Visitor design pattern as a means of executing different code depending on the runtime type of an object. For example, if you want to deal with Apples and Oranges in different ways, Visitor is the way to go.

Another, and maybe a little more realistic area of application of the pattern is the analysis and transformation of tree data structures. In fact, Gamma, Helm, Johnson, and Vlissides used exactly this – the processing of an abstract syntax tree – as the motivating example in their explanation of Visitor in the Design Patterns book. Recently, I’ve been doing a lot of abstract syntax tree processing because I’m working on a new SQL backend for re-linq.

In LINQ, everything is built around the concept of expression trees, abstract syntax trees that represent queries. The re-linq front-end parses those trees and constructs query models from them in order to enable easier interpretation of those queries. The expressions used inside the query, such as select projections, where conditions, and so on, are kept as (simplified) expression trees, however. Therefore, anybody building a LINQ provider based on re-linq will have to write some code to analyze these expression trees.

The analyzing code might be very simple, such as “for constant expressions, emit the constant value to the SQL statement being built”, or more complex, such as, “for member expressions, determine whether the member denotes an entity and, if so, emit a join”. But no matter how complex or simple it is, it will always be code that depends on the actual type of the expression nodes in the tree. And how is type dependent code handled most elegantly? Here comes the Visitor pattern: re-linq provides an ExpressionTreeVisitor base class with methods such as VisitConstantExpression and VisitMemberExpression that are automatically called depending on the type of expression being processed by the visitor. Just derive from that class and override the Visit… methods to execute your type-dependent code.

However, re-linq has to cheat for bringing the Visitor pattern to .NET 3.5 expression tree data structures. Due to some oversight (or, more likely, time constraints), .NET 3.5’s expression nodes do not provide Accept methods, so the visitor base class cannot use double dispatch to execute the right Visit... method for an expression. Instead, it has to resort to dynamic type comparisons and discriminator (= NodeType property) checks. This dirty workaround is hidden in re-linq’s ExpressionTreeVisitor.VisitExpression method:

public virtual Expression VisitExpression (Expression expression)
{
  // ...

  switch (expression.NodeType)
  {
  case ExpressionType.ArrayLength:
  case ExpressionType.Convert:
  case ExpressionType.ConvertChecked:
  case ExpressionType.Negate:
  case ExpressionType.NegateChecked:
  case ExpressionType.Not:
  case ExpressionType.Quote:
  case ExpressionType.TypeAs:
  case ExpressionType.UnaryPlus:
    return VisitUnaryExpression ((UnaryExpression) expression);
  case ExpressionType.Add:
  case ExpressionType.AddChecked:
  case ExpressionType.Divide:
  case ExpressionType.Modulo:
  case ExpressionType.Multiply:
  case ExpressionType.MultiplyChecked:
  case ExpressionType.Power:
  case ExpressionType.Subtract:
  case ExpressionType.SubtractChecked:
  case ExpressionType.And:
  case ExpressionType.Or:
  case ExpressionType.ExclusiveOr:
  case ExpressionType.LeftShift:
  case ExpressionType.RightShift:
  case ExpressionType.AndAlso:
  case ExpressionType.OrElse:
  case ExpressionType.Equal:
  case ExpressionType.NotEqual:
  case ExpressionType.GreaterThanOrEqual:
  case ExpressionType.GreaterThan:
  case ExpressionType.LessThan:
  case ExpressionType.LessThanOrEqual:
  case ExpressionType.Coalesce:
  case ExpressionType.ArrayIndex:
  return VisitBinaryExpression ((BinaryExpression) expression);
  case ExpressionType.Conditional:
    return VisitConditionalExpression ((ConditionalExpression) expression);
  case ExpressionType.Constant:
    return VisitConstantExpression ((ConstantExpression) expression);
  case ExpressionType.Invoke:
    return VisitInvocationExpression ((InvocationExpression) expression);
  case ExpressionType.Lambda:
    return VisitLambdaExpression ((LambdaExpression) expression);
  case ExpressionType.MemberAccess:
    return VisitMemberExpression ((MemberExpression) expression);
  case ExpressionType.Call:
    return VisitMethodCallExpression ((MethodCallExpression) expression);
   case ExpressionType.New:
    return VisitNewExpression ((NewExpression) expression);
  case ExpressionType.NewArrayBounds:
  case ExpressionType.NewArrayInit:
    return VisitNewArrayExpression ((NewArrayExpression) expression);
  case ExpressionType.MemberInit:
    return VisitMemberInitExpression ((MemberInitExpression) expression);
  case ExpressionType.ListInit:
    return VisitListInitExpression ((ListInitExpression) expression);
  case ExpressionType.Parameter:
    return VisitParameterExpression ((ParameterExpression) expression);
  case ExpressionType.TypeIs:
    return VisitTypeBinaryExpression ((TypeBinaryExpression) expression);

  default:
    if (expression is SubQueryExpression)
      return VisitSubQueryExpression ((SubQueryExpression) expression);
    else if (expression is QuerySourceReferenceExpression)
      return VisitQuerySourceReferenceExpression (
          (QuerySourceReferenceExpression) expression);
    else
      return VisitUnknownExpression (expression);
  }
}

In .NET 4.0, this has finally been addressed, and the Expression base class provides an Accept method that can be used to implement double dispatch. However, .NET 3.5 expressions show one of the two big weaknesses of the Visitor pattern: The visited class hierarchy must support the pattern for it to be used. If the authors of the class hierarchy didn’t anticipate the need for double dispatch, or if they didn’t knew the pattern, it’s out of reach.

Next time: the second big problem of the Visitor pattern. Can you guess what it is?

- Fabian