Background
Hierarchical Visitor -- found to recur while working with the Composite Pattern and other hierarchical data-structures. Occurrences of Hierarchical Visitor Pattern included a logical and hierarchical grouping of network hosts, rules, Security Permissions and Roles, and the Test Case and Test Suite classes described in Cpp Utx Overview. I, along with some others have used the hierarchical visitor in favor of the traditional Visitor Pattern for the last three years. I recently attempted to simplify or decompose this pattern further in Hierarchical Visitor Discussion. While some great ideas were contributed, I still found this to be (for me) the most straight forward representation. -- Robert Di Falco
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 Visitor Pattern 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 Composite Pattern. 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 qualify 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 Visitor Pattern as it only tells us when we are entering a composite node.
To search a file system optimally, we need to take advantage 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 Visitor Pattern 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 Hierarchical Visitor Pattern. 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 Visitor Pattern 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 Visitor Pattern 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 Once And Only Once when using the traditional Visitor Pattern with Hierarchical Structures. At some point the limitations are exceeded and another, more powerful mode of traversal -- usually External Iteration -- 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 Pattern Hatching. Some behavior is implemented with the Visitor Pattern while other more complex behaviors (such as indented tree-listings) require other iteration mechanisms. This is why we say that, eventually, Once And Only Once will be violated when using the traditional Visitor Pattern.
Applicability
Like the traditional Visitor Pattern, the Hierarchical Visitor Pattern combines a Functor Object (the Visitor object itself) with Internal Iterators (the accept members of the Composite Pattern). Together, these form a generalized mechanism for tree traversal. These allow the Hierarchical Visitor Pattern to be useful anywhere the traditional Visitor Pattern 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 Visitor Pattern, 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 we have left the previous node before we entered the current node.
The Hierarchical Visitor Pattern 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 possibility 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 Visitor Pattern 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 ancestor 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 abandon the traditional visitor and use another means of traversal. Most programmers violate the encapsulation provided by the traditional visitor when performing tree searches.
Hierarchical Visitor Pattern 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, traversal immediately 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 composite's 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
HierarchicalVisitor (FilenameQualifier):
defines the visitEnter and visitLeave operations for Composite nodes and visit operation for Leaf nodes
Component (FileSystemItem):
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 visited. The composite's accept implementation uses the answer from visitEnter to determine whether 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 implementation 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 Functor Object 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 Null Object (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; } } }
Now we just need to create the Composite structure. For details on this see Composite Pattern. 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 Hierarchical Visitor Pattern, it is quite difficult to achieve with the traditional Visitor Pattern. 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 FileListingVisitor 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
Cpp Utx Overview:
A version of Cpp Unit for large systems development
Eclipse Ide:
The Java Development Tooling uses hierarchical vistors for traversing its AST. It makes use of both, entering and leaving visit methods (called beginVisit()/endVisit()) and controlled traversal via a boolean return.
SPACE:
The Security Platform Architecture for Composition and Extension is a Product Line Architecture for create Surveillance and Response systems (such as Intrusion Detection Systems or File Integrity Checkers) from a set of Core Assets. The Hierarchical Visitor Pattern is used throughout the system to provide system integrated from SPACE greater flexibility. 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 distributed system can be logically grouped together to ease the complexity of summarizing or administering a network of 10,000+ nodes/computers. You may have a group named "all-nodes" that contains the group called "saled-department". This group might contain all the computers in the sales department. The Hierarchical Visitor Pattern is used to allow systems that are based on the SPACE Product Line Architecture to operate on nodes in unpredictable ways.
Related Patterns
See also: Hierarchical Visitor Discussion
See original on c2.com 