Introduction

In a previous article I introduced the Composite pattern - as neat a way of organizing components at runtime as you could want. To recap, a composite structure is a tree of components, all of which implement the same core type. This feature enables you to treat the whole tree, a sub-tree or an individual component interchangeably. Think about a shape in a drawing program: you can select, drag and/or transform it. Select and group multiple shapes, and you can perform the same operations on the collection as you did on the individual component.

Components in a composite relationship are good at working with one another. Called by a client, an object performs the required operation and then invokes the same method upon each of its children. Each child then repeats the process, until the whole tree has responded to the client's message.

This is neat, but it carries with it a certain danger. Because it is so easy to build composite functions into a type, it's tempting to extend the remit of your classes beyond their strict responsibilities. This kind of feature bloat makes for unwieldy and error-prone code. You start by building in core functions, such as transform() and move(). Then you find yourself straying into the gray area of object persistence with save(). Before you know it, you're adding more and more increasingly tangential operations to the type - not because the type needs each operation integrally, but because each operation needs easy access to every component in the structure.

The Visitor Pattern

Composites are good at traversing themselves, and for that reason they attract new methods. We can address this problem by extracting these methods into their own type, and by generalizing traversal so that such objects can be transported to every node in the tree. This is known as the Visitor pattern.

Overview

The Visitor pattern collects tasks into a type. These tasks are designed to be applied to every component in a structure. Since the task objects are distinct from the components upon which they operate, it's easy to add new functionality without changing the component interface. It's simply a matter of defining a new concrete instance of the task type.

Implementation

So how does this simple matter pan out in practice? Earlier in this series, I used the Composite pattern to create a simple system for organizing notes and resources. The same code will serve us here, too. We are already able to traverse this particular tree of components for several built-in operations, in particular for cloning the tree and for printing out summary information.

Now we need to add more operations, and there are more on the horizon, we know. Several species of search are mooted, as is saving in multiple formats. It may be convenient to build these new functions into the composite type itself, but you know it smells wrong. There is probably a metric for the number and nature of countervailing responsibilities a type can bear. Personally I rely on a sense of sin, and let guilt rein me in.

The Visitor pattern bears some similarity to the Observer pattern, in that the target component calls back into a provided object. Here, though, the relationship is more transient.

Figure 1 shows the participants in this example:

The MyListComponent type reappears, of course, along with its concrete classes. I highlight a new method, though: accept(). accept() requires a MyListVisitor object, and an integer. It is responsible for calling a method in the provided MyListVisitor, and, depending upon your implementation, passing the object on to its children via their own accept() methods.

So you can pass a MyListVisitor object to a MyListComposite object and it will be passed along to every node on the tree - just visiting.

There is a further refinement here, though. A visitor may need to perform variations on its core functionality according to the MyListComponent it is currently visiting. Each implementation of MyListComponent::accept() must therefore call the relevant method for its type. So WebText needs to call MyListVisitor::visitWebText, Note will call MyListVisitor::visitNote(), and so on. The callback relationship is more sophisticated in this instance than in the Observer pattern, where a single update() method is invoked.

Let's get to some code. Here is the Binary implementation of accept():

Because Binary is a node and so doesn't maintain children, the accept() method is very simple here. It calls the relevant method on the provided MyListVisitor class, passing along the current instance of itself and a provided $level variable. $level should be the depth of the component in the tree. Although $level isn't a true part of the classic Visitor pattern, I have found it useful enough to include in almost every implementation.

As you might expect, MyListComposite objects have to do a little more work in implementing access(), though not much. Here's WebText:

In addition to calling MyListVisitor::visitWebText(), this implementation loops through any children, calling accept() on each. If you detect the fishy tang of code duplication here, you're right. We need to implement accept() for every node, and this traversal code in every MyListComposite object. This is because each object in the structure must call its own counterpart in the visitor interface. That's not the last word on this issue, however, and I will return to the problem in the next section.

Now that we have our tree primed to accept visitors, we should create some classes to work with them. Here is the MyListVisitor class:

As you can see, this class presently has no concrete code at all. We could promote flexibility by making it an interface rather than an abstract class. In this case though, I have some ideas up my sleeve that will require that code is added in future.

Here is a child class, SimpleSearchVisitor:

A casual glance may suggest that there's a lot going on here, but most of it in fact boils down to simple method calls. The real functionality lies in the testText() method, which accepts a string and searches it for a property, $term. $term is set according to a constructor argument. The visit* methods acquire data from their MyListComponent argument, and pass their returned strings along to testText(). If a match is found, the component is added to an array property called $matches. Each visit* method must query different fields, according to the particular subclass it works with.

Finally, the matches() function returns the array of MyListComponent objects collated during the traversal.

This code fragment creates a tree, and then traverses it in search of the word 'artichoke':

Most of this example is taken up with the process of creating the tree of MyListComponent objects. This code is included for the sake of completeness, and is covered in full in PHP 5 and Design Patterns: Composite. Once the tree is constructed, we create a SimpleSearchVisitor object, initializing it with the search term. We pass this new object to MyListComponent::accept(). Behind the scenes the component calls back to the SimpleSearchVisitor object, and then passes it on to its children. Finally we use print_r() to check for any matches. Here is the output (snipped for brevity):

Array
(
    [0] => Address Object
        (
            [street:protected] => 56 Artichoke Road
            [postcode:protected] => XY4 Y33
            [children:protected] => Array
                (
                    [0] => Note Object
                )
        )
)

[ continued in part 2 of PHP Patterns: The Visitor Pattern ]

Digg This!