A sample of visitor pattern used in pull mode
Java
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Failed to load latest commit information.
.settings
src
.classpath
.gitignore
.project
README.md
pom.xml

README.md

Pull Visitor Pattern

Visitor pattern is often used to separate operation from object graph it operates with. Here we assume that the reader is familiar with the subject.

The idea is like this:

  • The operation over object graph is implemented as type called Visitor.
  • Visitor defines methods for each type of object in the graph, which a called during traversing of the graph.
  • Traversing over the graph is implemented by a type called Traverser, or by the Visitor or by each object type in the graph.

Implementation should collect, aggregate or perform other actions during visit of objects in the graph, so that at the end of the visit the purpose of operation will be complete.

Such implementation is push-like: you create operation object and call a method that gets object graph on input and returns operation result on output.

In the past we often dealt with big graphs (usually these are virtual graphs backended at database or at a file system).

Also having a strong experience in the XSLT we see that the visitor pattern in OOP is directly mapped into xsl:template and xsl:apply-templates technique.

Another thought was that in XML processing there are two camps:

  • SAX (push-like) - those who process xml in callbacks, which is very similar to visitor pattern; and
  • XML Reader (pull-like) - those who pull xml components from a source, and then iterate and process them.

As with SAX vs XML Reader or, more generally, push vs pull processing models, there is no the best one. One or the other is preferable in particular circumstances. E.g. Pull like component fits into a transformation pipeline where one pull component has another as its source; another example is when one needs to process two sources at once, which is untrivial with push like model. On the other hand push processing fits better into Reduce part of MapReduce pattern where you need to accumulate results from source.

So, our idea was to complete classic push-like visitor pattern with an example of pull-like implementation.

For the demostration we have selected Java language, and a simplest boolean expression calculator. Please note that we start from object graph, so we put expression parsing aside.

So, this is the object graph:

public interface Expression
{
  public <R> R accept(Visitor<R> visitor);
}

public abstract class UnaryExpression implements Expression { public Expression argument; }

public abstract class BinaryExpression implements Expression { public Expression first; public Expression second; }

public class AndExpression extends BinaryExpression { public <R> R accept(Visitor<R> visitor) { return visitor.visit(this); } }

public class OrExpression extends BinaryExpression { public <R> R accept(Visitor<R> visitor) { return visitor.visit(this); } }

public class NotExpression extends UnaryExpression { public <R> R accept(Visitor<R> visitor) { return visitor.visit(this); } }

public class RefExpression implements Expression { public String name;

public <R> R accept(Visitor<R> visitor) { return visitor.visit(this); } }

and a Visitor interface:

public interface Visitor<R>
{
  R visit(AndExpression expression);
  R visit(NotExpression expression);
  R visit(OrExpression expression);
  R visit(RefExpression expression);
}

Now, let's define an Evaluator - a visitor to calculate expression value:

public abstract class Evaluator implements Visitor<Void>
{
  public boolean result()
  {
    return stack.pop(); 
  }

public Void visit(AndExpression expression) { boolean second = stack.pop(); boolean first = stack.pop();

stack.push(first && second);

return null;

}

public Void visit(NotExpression expression) { stack.push(!stack.pop());

return null;

}

public Void visit(OrExpression expression) { boolean second = stack.pop(); boolean first = stack.pop();

stack.push(first || second);

return null;

}

public Void visit(RefExpression expression) { stack.push(resolve(expression.name));

return null;

}

public abstract boolean resolve(String name); public ArrayDeque<Boolean> stack = new ArrayDeque<>();
}

These are the common parts between push and pull implementations.

At this point we should deal with traversing logic, which in case of push-like implementation recursively calls visitors in the graph; and in case of pull-like implementation builds an iterator over graph.

So, this is push-like TraversingVisitor:

public class TraversingVisitor<R> implements Visitor<R>
{
  public TraversingVisitor(Visitor<R> visitor)
  {
    this.visitor = visitor;
  }

public TraversingVisitor(Visitor<R> visitor, boolean traverseFirst) { this.visitor = visitor; this.traverseFirst = traverseFirst;
}

public void traverse(BinaryExpression expression) { expression.first.accept(this); expression.second.accept(this); }

public void traverse(UnaryExpression expression) { expression.argument.accept(this); }

public void traverse(AndExpression expression) { traverse((BinaryExpression)expression); }

public void traverse(NotExpression expression) { traverse((UnaryExpression)expression); }

public void traverse(OrExpression expression) { traverse((BinaryExpression)expression); }

public void traverse(RefExpression expression) { }

public R visit(AndExpression expression) { if (traverseFirst) { traverse(expression); }

R result = visitor == null ? null : visitor.visit(expression);

if (!traverseFirst)
{
  traverse(expression);
}

return result;

}

public R visit(NotExpression expression) { if (traverseFirst) { traverse(expression); }

R result = visitor == null ? null : visitor.visit(expression);

if (!traverseFirst)
{
  traverse(expression);
}

return result;

}

public R visit(OrExpression expression) { if (traverseFirst) { traverse(expression); }

R result = visitor == null ? null : visitor.visit(expression);

if (!traverseFirst)
{
  traverse(expression);
}

return result;

}

public R visit(RefExpression expression) { if (traverseFirst) { traverse(expression); }

R result = visitor == null ? null : visitor.visit(expression);

if (!traverseFirst)
{
  traverse(expression);
}

return result;

}

protected Visitor<R> visitor; protected boolean traverseFirst; }

And this is pull-like Traverser that provides Stream over the graph.

public class Traverser implements Visitor<Stream<Expression>>
{
  public Stream<Expression> stream(Expression expression)
  {
    return Stream.concat(
      Stream.of(expression), 
      expression.accept(this).flatMap(this::stream));
  }

public Stream<Expression> traverseFirstStream(Expression expression) { return Stream.concat( expression.accept(this).flatMap(this::traverseFirstStream), Stream.of(expression)); }

public Stream<Expression> visit(BinaryExpression expression) { return Stream.of(expression.first, expression.second); }

public Stream<Expression> visit(UnaryExpression expression) { return Stream.of(expression.argument); }

public Stream<Expression> visit(AndExpression expression) { return visit((BinaryExpression)expression); }

public Stream<Expression> visit(NotExpression expression) { return visit((UnaryExpression)expression); }

public Stream<Expression> visit(OrExpression expression) { return visit((BinaryExpression)expression); }

public Stream<Expression> visit(RefExpression expression) { return Stream.empty(); } }

Now we have all components needed to evaluate the expression:

  public static boolean evaluatePull(Expression expression, Evaluator evaluator)
  {
    Traverser traverser = new Traverser();
    Iterable<Expression> iterable = traverser.traverseFirstStream(expression)::iterator;
for(Expression e: iterable)
{
  e.accept(evaluator);
}

return evaluator.result();

}

public static boolean evaluatePush(Expression expression, Evaluator evaluator) { TraversingVisitor<Void> traverser = new TraversingVisitor<>(evaluator, true);

expression.accept(traverser);

return evaluator.result();

}