Jump to content

Hierarchical visitor pattern: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
credit
See the talk page
 
(12 intermediate revisions by 12 users not shown)
Line 1: Line 1:
#REDIRECT [[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 hierarchical [[data structure]] such as [[Tree data structure|tree]].

'''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

== Credit ==
The first draft is based on an excerpt from [[WikiWikiWeb]].

Latest revision as of 21:12, 30 June 2015

Redirect to:

Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Hierarchical_visitor_pattern&oldid=669390707"