In the previous posts in this series I looked at the basic Visitor design pattern and a couple of variations, like eliminating recursion to make the visitor interruptable. As promised, this time I will make our visitor re-entrant.

Here’s what we have so far:

public class BaseFileSystemVisitor 
    implements FileSystemVisitor {

  public FileSystemNode visit(final FileSystemNode node) {
    int numNodesVisited = 0;
    FileSystemNode current = node;

   while (current != null && numNodesVisited < maxNodes) {
      numNodesVisited++;
      stack.push(current);
      if (current.start(this)) {
        current = current.getNext();
      } else {
        current = current.getNextNoChild();
      }
      while (!stack.isEmpty() 
          && !stack.peek().isAncestorOf(current)) {
        stack.pop().stop(this);
      }
    }
    return current;
  }

First of all, note there is a bug in here: when start returns false, the stop method is called anyway! This is because the folder is still on the stack and therefore will be stopped when it is popped from the stack. Given this analysis, the fix is easy:

  public FileSystemNode visit(final FileSystemNode node) {
    int numNodesVisited = 0;
    FileSystemNode current = node;

    while (current != null && numNodesVisited < maxNodes) {
      numNodesVisited++;
      stack.push(current);
      if (current.start(this)) {
        current = current.getNext();
      } else {
        current = current.getNextNoChild();
        stack.pop();
      }
      while (!stack.isEmpty()
          && !stack.peek().isAncestorOf(current)) {
        stack.pop().stop(this);
      }
    }
    return current;
  }

Now suppose we want to change the order in which children are displayed, e.g. first show all sub-folders, than the others. We could write that as follows:

public class XmlVisitor 
    extends BaseFileSystemVisitor {

  public boolean start(Folder folder) {
    out.println("<folder name='" + folder.getName() 
        + "'>");
  
    Iterator children = folder.getChildren();
    while (children.hasNext()) {
      FileSystemNode child = children.next();
      if (child instanceof Folder) {
        while ((child = visit(child)) != null) { 
          // Repeat, since the visitor may be interrupted
        }
      }
    }
    
    children = folder.getChildren();
    while (children.hasNext()) {
      FileSystemNode child = children.next();
      if (!(child instanceof Folder)) {
        while ((child = visit(child)) != null) { 
          // Repeat, since the visitor may be interrupted
        }
      }
    }

    stop(folder);
    return false;
  }

But this produces the wrong output, and an EmptyStackException on top of that. The problem is that the visit method just iterates until there are no more nodes left. This is wrong for the re-entrant case: it should iterate until the nodes are no longer descendants of the root that is passed into the method:

  public FileSystemNode visit(final FileSystemNode node) {
    final FileSystemNode root;
    FileSystemNode current;
    if (stack.isEmpty() || stack.peek() != node) {
      current = node;
      root = node;
    } else {
      current = (FileSystemNode) stack.pop();
      root = (FileSystemNode) stack.firstElement();
    }
    while (root.isAncestorOf(current) 
        && numNodesVisited < maxNodes) {
      numNodesVisited++;
      stack.push(current);
      if (current.start(this)) {
        current = current.getNext();
      } else {
        current = current.getNextNoChild();
        stack.pop();
      }
      if (root.isAncestorOf(current)) {
        while (!stack.isEmpty() 
            && !stack.peek().isAncestorOf(current)) {
          stack.pop().stop(this);
        }
      }
    }
    
    if (numNodesVisited >= maxNodes) {
      numNodesVisited = 0;
    }

    final FileSystemNode result;
    if (root.isAncestorOf(current)) {
      stack.push(current);
      result = current;
    } else {
      result = null;
    }    
    return result;
  }

Note that numNodesVisited is now a field instead of local variable.

The code has become much more complex, but we are now successfully supporting both interruptability and re-entrancy. Next time, we will make things even more complex by adding support for modification of the data structure being visited.