How to reference sub-results when using visitor pattern?

Question

Suppose I have a composite hierarchy to represent regular expresions, like this:

public abstract class Expression {
  public abstract void accept(Visitor visitor);
}

public class Identifier extends Expression {
  public final String token;

  public Identifier(String token) {
    this.token = token;
  }

  @Override
  public void accept(Visitor visitor) {
    visitor.visit(this);
  }

  public String getToken() {
    return token;
  }
}

public class Sequence extends Expression {
  private final List<Expression> subExprs;

  public Sequence(List<Expression> subExprs) {
    this.subExprs = new ArrayList<Expression>(subExprs);
  }

  @Override
  public void accept(Visitor visitor) {
    visitor.visit(this);
  }

  public List<Expression> getSubExprs() {
    return subExprs;
  }
}

...

public abstract class Visitor  {
  public abstract void visit(Identifier identifier);
  public abstract void visit(Sequence sequence);
}

The question is, how do I implement operations that need to crawl the tree and calculate the results recursively, such as:

• serialize a regexp to string,
• evaluate a regexp to a set of sequences,
• ...

Suppose for example the following Visitor implementation:

public class Serialize extends Visitor {

  public void visit(Sequence sequence) {
    for (Expression subExpr : sequence.getSubExprs()) {
      // here, I don't have any means to access the sub-results
      subExpr.accept(visitor);
    }
  }

  ...
}

To calculate the result at any given level of the tree, I need to know the sub-results at the levels below. Ideally I would need the accept method to return the calculated result. This does not seem to be possible, though, as individual operations might return results of different type.

The only solution that comes to my mind is to cache the sub-results manually in a map on the visitor class. This seems very cumbersome, though.

Is Visitor a suitable pattern in this case? What would be a suitable implementation?

Answer 1

First of all, extend visitor to return results. I often do something like:

public interface JSStatementVisitor<V, E extends Exception> {

    public V visitBlock(JSBlock value) throws E;

    public V visitVariable(JSVariableStatement value) throws E;

    public V visitEmpty(JSEmptyStatement value) throws E;

    ...

}

This gives you much more flexibility with visitors. If you don't need results or exceptions just use Void and RuntimeException.

The counterpart is like:

public interface JSStatement extends JSSourceElement {
    public <V, E extends Exception> V acceptStatementVisitor(
            JSStatementVisitor<V, E> visitor) throws E;
}

(By the way I prefer having qualified visit methods (like visitBlock instead of visit or acceptStatementVisitor instead of accept) to avoid possible naming collisions in case some class will have to implement several interfaces.

Alternatively you could make your visitors stateful and have a method like V getResult(), but I'm not a big fan of stateful things.

This is the first part. Your visitors now return values.

Next, when working with composites, you'll need to aggregate their results (as your visitor have to return one result only). Add a method like:

public V aggregate(Iterable<V> values) throws E;

And you're there.

---

(I never did the thing below, but it will most probably work equally well.)

Yet another option would be to pass some Callback<V> callback function to the visit method:

public interface JSStatementVisitor<V, E extends Exception> {
    public void visitBlock(JSBlock value, Callback<V> result) throws E;
}

The counterpart is, accordingly:

public interface JSStatement extends JSSourceElement {
    public <V, E extends Exception> void acceptStatementVisitor(
            JSStatementVisitor<V, E> visitor, Callback<V> result) throws E;
}

With this "yet another option" in the first part you won't even need an additional method for aggregation. You could implement and pass the MyAggregatingCallback<V> implements Callback<V>. It would aggregate the results and then allow to flush the aggregated result V to the original callback.