Hierarchical visitor pattern

In software development, hierarchical visitor pattern is one of design patterns that intend to provide a way to visit every node in the data structure

Background * Hierarchical Visitor -- found to recur while working with the CompositePattern and other hierarchical data-structures. Occurances of HierarchicalVisitorPattern included a logical and hierarchical grouping of network hosts, Security Permissions and Roles, and the TestCase and TestSuite classes described in CppUtxOverview. I, along with some others have used the hierarchical visitor in favor of the traditional VisitorPattern for the last three years. I recently attempted to simplify or decompose this pattern further in HierarchicalVisitorDiscussion. While some great ideas were contributed, I still found this to be (for me) the most straight forward representation.

---

Intent

Represent an operation to be performed on the nodes of a hierarchical object structure. Hierarchical Visitor lets one define new operations without changing the classes of the nodes on which it operates. Hierarchical Visitor overcomes the limitations of the traditional VisitorPattern by allowing a programmer to track traversal depth and short-circuit branch traversal.

---

Motivation

Consider a file system represented using a hierarchical structure, such as that provided by the CompositePattern. The file objects are leaf nodes and the directories are the composite nodes. Now consider two operations on a file system: (a) fully qualifying a file name and (b) searching for a specific file.

To fully qualified a file name, we must traverse each of its parent composites. To do this, we start with a string representing the root composite, and concatenate each child composite until we reach the actual file object. We need to determine what composites (directories) are children of the root and which are its siblings. This requires we track when we are entering a composite and leaving a composite. If we enter the composite bar before we have left the composite foo, we know we have "foo/bar". However, if we leave foo before entering bar then foo and bar are siblings. This is quite impossible if equipped only with the traditional VisitorPattern as it only tells us when we are entering a composite node.

To search a file system optimally, we need to take adavantage of fully qualified names. If we are searching for "root/foo2/bar3/file.dat", we don't need to search through the branches "root/foo1/*", "root/foo2/bar1/*", or even "root/foo2/bar2/*". Unfortunately, because the traditional VisitorPattern does not have the ability to conditionally traverse a hierarchical structure, we are left with only two choices -- (a) use an alternative means of traversal or (b) search even those branches that have no possibility of a match.

These two examples summarize the advantages of the HierarchicalVisitorPattern. One no longer needs to rely on multiple traversal techniques when the limitations of the traditional visitor pattern must be exceeded. We can generalize these limitations as:

* hierarchical navigation -- the traditional VisitorPattern has no concept of depth. As a result, visitor cannot determine if one composite is within another composite or beside it. * conditional navigation -- the traditional VisitorPattern does not allow branches to be skipped. As a result, visitor cannot stop, filter, or optimize traversal based on some condition.

The primary consequence of these limitations is a eventual violation of OnceAndOnlyOnce when using the traditional VisitorPattern with Hierarchical Structures. At some point the limitations are exceeded and another, more powerful mode of traversal -- usually ExternalIteration -- is required. The first two File System examples are typical of those operations that challenge these limitations. Further consider the File System sample discussed in PatternHatching. Some behavior is implemented with the VisitorPattern while other more complex behaviors (such as indented tree-listings) require other iteration mechanisms. This is why we say that, eventually, OnceAndOnlyOnce will be violated when using the traditional VisitorPattern.

---

Applicability

Like the traditional VisitorPattern, the HierarchicalVisitorPattern combines a FunctorObject (the Visitor object itself) with InternalIterator's (the accept' members of the CompositePattern). Together, these form a generalized mechanism for tree traversal. These allow the HierarchicalVisitorPattern to be useful anywhere the traditional VisitorPattern would. The hierarchical visitor is then made more useful by allowing hierarchical navigation and conditional navigation.

Hierarchical navigation

Hierarchical navigation is important for any traversal that needs to know whether one node is the child of another or its sibling. The simplest example of this is tree listings where an indentation level needs to be maintained. With the traditional VisitorPattern, one can only determine when we are entering a node. This tells us that we may want to indent but gives us no clues about outdenting. We don't know if the we have left the previous node before we entered the current node.

The HierarchicalVisitorPattern removes this limitation by defining a two method protocol when visiting nodes -- visitEnter and visitLeave. If we are entering the composite node bar before leaving the composite node foo, we can safely assume that bar is a child (and not a sibling) of the composite foo.

Conditional Navigation

Conditional navigation is required to skip unnecessary branches and all of their children. Consider the second operation of the File System example. The search for a specific file in a particular path can only be performed optimally if we can dispose of branches that have no possiblity of providing a match. Consider the following graph:

* 1. * 1.1 * 1.2 * 1.2.1 * 1.2.2 * 1.3 * 1.3.1 * 1.3.1.1 * 1.3.2 * 2. * 2.1 * 2.2

The traditional VisitorPattern would have to visit each leaf of the entire structure in order to find the leaf labeled "2.2"! Even though we can see that "1" does not match the root ancenstor of "2.2", we would still have no choice but to perform a match for the leaf "1.3.1.1". The only way to avoid this is to abandoned the traditional visitor and use another means of traversal. Most programmers violate the encapsulation provided by the traditional visitor when performing tree searches.

HierarchicalVisitorPattern allows us to solve this problem within a single visiting paradigm. It does so by having each invocation of accept answer a boolean traversal state for its depth of the tree. For example, if accept on a composite or leaf answers false, then traversal immeadiately stops at that tree depth. In other words, no more of its siblings will be traversed, even if some of those siblings are composites with children of their own. Reconsider the example graph. As we visit the node labeled "1", we can cause its accept message to answer false like so:

boolean visitEnter( Composite node )
{
    String sLabel = node.getLabel();
    return sLabel.equals( "2.2", sLabel.length() );
}

If the compsites label does not match the first N characters of "2.2", we do not enter the node and we do not traverse its children. We then proceed directly to the node labeled "2". For this composite node, the expression will return true, causing us to continue searching its children. This strategy allows us to find the optimal path to "2.2". Furthermore, we cannot construct this strategy using the traditional visitor alone.

---

Participants

* H'ierarchicalVisitor (F'ilenameQualifier) * defines the visitEnter and visitLeave operations for Composite nodes and visit operation for Leaf nodes

* Component (File'System'Item) * defines the base class common to Leaf and Composite nodes. This interface/class establishes the basic accept protocol. * Composite (Directory) * a Component that can contain children Components and implements accept to process itself and its children * Leaf (File) * a concrete Component that implements the accept protocol to process only itself

---

Collaborations

Hierarchical Visitor collaborates directly with Leaf and Composite objects. The members of the visitor interface are called indirectly by the implementation of accept in the Composite and Leaf classes.

When Composite accepts a visitor (e.g. composite.accept(Visitor)), it notifies the visitor that it is entering a new branch by sending the visitor the message:

   boolean visitEnter( this )

The this argument is the Composite object itself. We can use visitEnter to process the composite or wait for visitLeave -- after its children have been visitted. The composite's accept implementation uses the answer from visitEnter to determine whether if its children should accept this visitor. So, if visitEnter answers true, accept is invoked on each of its children or until one of the accept invocations answers false. This essentially works like a do...while loop. The first child accept that answers false causes traversal at that level to stop. We then give accept method of this composite to answer true or false. This result comes from the answer to visitLeave. The whole Composite accept implemetnation looks like the following:

   public boolean accept( Visitor v )
   {
       if ( v.visitEnter( this ) )  // enter this node?
           m_children.doWhile( <each>.accept( v ) );

       return visitLeave( this );
   }

Remember that each Composite may itself be the child of another Composite. So, if visitLeave returns false, this would short-circuit visiting its sibling nodes. The Leaf implementation of accept is very simple. It just invokes visit on the passed Visitor with itself as the argument and uses the result for its return value:

 boolean Leaf.accept( Visitor v )
 {
     return v.visit( this );
 }

Any time a call to accept answers false, it signals the parent's accept member to stop processing children at that level in the tree.

Once a parent node has called accept for each of its children, it will call visitor.visitLeave. This lets the visitor FunctorObject know it is done with this branch and proceeding to either a sibling or parent Component node at the same tree-depth as this node.

---

Implementation

Consider the following interface for the Hierarchical Visitor:

  public interface Visitor
  {
      boolean visitEnter( Composite node ); // going into a branch
      boolean visitLeave( Composite node ); // coming out
      boolean visit( Leaf node );
  }

That's pretty much it. To make life a little easier I provide a NullObject (Default Implementation) visitor.

  public interface Visitor
  {
      .
      .
      .
      public static class Default implements Visitor
      {
          public boolean visitEnter( Composite node ) {
              return true;
          }
          public boolean visitLeave( Composite node ) {
              return true;
          }
          public boolean visit( Leaf node ) {
              return true;
          }
      }
  }

No we just need to create the Composite structure. For details on this see CompositePattern. The only variation is the accept methods which both need to return a boolean. These members should be implemented as follows:

   boolean Composite.accept( Visitor v )
   {
       if ( v.visitEnter( this ) )  // enter this node?
       {
           Iterator at = m_children.iterator();
           while ( at.hasNext() )
               if ( ((Component)at.next()).accept( v ) )
                   break;
       }
       
       return v.visitLeave( this );
   }

And the leaf implementation:

  boolean accept( Visitor visitor )
  {
      return visitor.visit( this );
  }

---

Sample Code and Usage

In this example, the Composite node is a Directory and the Leaf node is a File object. We implement a Visitor that can construct the qualified path name for each File component. While this can be simply done using the HierarchicalVisitorPattern, it is quite difficult to achieve with the traditional VisitorPattern. Note that this example only shows the 'hierarchical navigation features of the hierarchical visitor and does not use any of its conditional features.

/**
 * Maintains a string that when accessed in the "visit"
 * member will return the current qualified file name.
 */
public abstract 
    class      F'ilenameQualifier'
    implements F'ileVisitor

{
    static final String SEPCHAR = "\\";  // path separator

    private m_sPath = "";

    // Entering a composite: Push its name on the Path
    public boolean visitEnter( Directory node )
    {
        m_sPath += node.getName();
        m_sPath += SEPCHAR;  // NOTE: Don't forget the separator!
        return true;         // process leafs (i.e. files or subdirs)
    }

    // Leaving a composite: Pop its name from the Path
    public boolean visitLeave( Directory node )
    {
        m_sPath.resize( m_sPath.size() - node.getName().size() );
        return true;         // go to next sibling
    }

    // Provide read-only access to the current qualifier
    String currentPath()
    {
       return m_sPath;
    }
}

We only added a protected member to access the current path for each call to visit. Because we are creating classes, we can extend them to add or refine behavior. For example, we can extend the qualifier to create a hierarchical listing of qualified file names:

public 
    class   F'ileListingVisitor

    extends F'ilenameQualifier

{
    private int m_nLevel;   // Indent Level

    public boolean visitEnter( Directory node )
    {
        super.visitEnter( node );

        println( node.getName() );
        m_nLevel++;         // increase indent level
        return true;
    }

    public boolean visitLeave( Directory node )
    {
        super.visitLeave( node );

        m_nLevel--;         // decrease indent level
        return true;
    }
     
    public boolean visit( File leaf )
    {
        println( currentPath() + leaf.getName() );
        return true;
    }

    private void println( String s )
    {
        int N = m_nLevel * TABSIZE;
        while ( N-- ) System.print( ' ' );
        System.println( s );;
    }
 }

To use, you simply pass an instance of the F'ileListingVisitor to the accept member of any composite in the file system.

  Directory dir = directoryAt( path );
  dir.accept( new F'ileListingVisitor()' );

Here's an example of a composite hierarchy for this sample:

 interface F'ileSystemObject

 {
     String  getName();
     boolean accept( Visitor v );
 }

 class Directory implements F'ileSystemObject

 {
     private String    m_name;
     private I'temArray m_contents = new I'temArray();

     public Directory( String name )
     {
         m_name = name;
     }

     public String getName()
     {
         return m_name;
     }

     public void add( F'ileSystemObject child )

     {
         m_contents.add( child );
     }
     .
     .
     .
     public boolean accept( Visitor v )
     {
         if ( v.visitEnter( this ) )
             m_contents.detect( new Block() {
                 public boolean is( Object each ) {
                     return !((F'ileSystemObject)each).accept( v ); } } );

         return v.visitLeave( this );
     }
 }

 class File implements F'ileSystemObject

 {
     private String m_name;

     public File( String name )
     {
         m_name = name;
     }

     public String getName()
     {
         return m_name;
     }

     public boolean accept( Visitor v )
     {
         return v.visit( this );
     }
 }

That's pretty much it. You add files to directories like so:

 Directory root = new Directory( "root" );
 Directory temp  = new Directory( "temp" );

 temp.add( new File( "foo.txt" ) );
 root.add( temp )
 root.add( new File( "bar.txt" ) );

This creates the following file structure:

 root
   |
   +--temp
   |   |
   |   +--foo.txt
   |
   +--bar.txt

---

Sample Code for Filtered Processing

This example shows the extensibility of the Hierarchical Visitor. The following shows us building on the basic Hierarchical Visitor to create a new abstraction that allows us to add filter objects and processing objects to selectively process a composite.

First we define the interface for creating classes that filter nodes or operate on filtered nodes:

   interface Filter
   {
       boolean canVisit( Composite node );
       boolean canVisit( Leaf leaf );
   }

   interface Operator extends C'lassicVisitor

   {
       void visit( Composite node );
       void visit( Leaf leaf );
   }

   class F'ilteredVisitor extends H'ierarchicalVisitor
   {
       Items m_filters;     // one or more filter conditions
       Items m_operators;   // one or more operators

       ...

       // Add a filter
       public void add( Filter filter ) {
           m_filters.add( filter );
       }

       // Add an operator
       public void add( Operator process ) {
           m_operators.add( process );
       }
  
       ...

       // Filter this entire Branch?
       public boolean visitEnter( Composite node )
       {            
           // Return first that rejects this node
           Object rejected =
               m_filters.detect( new Block() {
                   public boolean is( Filter each ) {
                       return !each.canVisit( node ); } } );

           return ( rejected == null );
       }
       
       // Visit non-rejected nodes
       public boolean visitLeave( Composite node )
       {
           m_operators.enum( new Block() {
               public void run( Operator each ) {
                   each.visit( node ); } } );

           return true;
       }

       // Check reject state for each condition, process if not rejected
       public boolean visit( Leaf node )
       {
           // Return first that rejects this leaf
           Object rejected =
               m_filters.detect( new Block() {
                   public boolean is( Filter each ) {
                       return !each.canVisit( node ); } } );

           if ( rejected == null )  // no one rejected
               m_operators.enum( new Block() {
                   public void run( Operator each ) {
                       each.visit( node ); } } );

           return true;                
       }
   }

This allows you to aggregate various filters and operators into the Hierarchical Visitor.

---

Existing Uses * CppUtxOverview -- A version of CppUnit for large systems development * SPACE -- The Security Platform Architecture for Composition and Extension is a ProductLineArchitecture for create Surveillance and Response systems (such as Intrusion Detection Systems or File Integrity Checkers) from a set of CoreAssets. The HierarchicalVisitorPattern is used throughout the system to provide system integrated from SPACE greater flexability. Some example uses include: * Permissions -- in SPACE a Permission can be a single permission or a logically named group of permissions. The hierarchical visitor allows implies methods to be written efficiently. * Node Grouping -- nodes in the distrib