Using TreeWalker

Getting started

To use the TreeWalker in your code, you don't need to do much! That's the whole point. Yes, there are imports to deal with, as usual, but apart from that, you need only to define an Operator, and you are in business!

First let's look at the simplest thing you can do, and work from there. We'll simply walk a tree and perform no operation. For our own testing we defined a NullOperator that does exactly nothing, except satisfy the IOperator interface. We can use this class to get started.

Incidentally, the snippets I'm going to use for the examples are taken from a "doctest" file called treeWalker.txt in the docs folder of the ATContentTypes Product. That's why you'll see the >>> at the left of each line (if you aren't familiar with doctests you shouldn't worry about this syntax - just imagine the >>> is a prompt for an interactive python session that you could use in your favorite python shell or you can go back to the previous section and get the whole story). If you want to run this doctest you should use the photoimagemerge branch with Archetypes 1.4 branch and CMFDynamicFTI trunk You are also welcome to look at treeWalker.txt itself for reference. The source of this Plone.org tutorial document is available as a single Structured Text file called treeOperations.txt in the docs folder, and is also tested in our test suite.

OK, so on with the tutorial...

First let's import TreeWalker and NullOperator:

      >>> from Products.ATContentTypes.adapters.treeWalker import TreeWalker
      >>> from Products.ATContentTypes.adapters.operator import NullOperator

Then let's instantiate the NullOperator:

      >>> nulloperator = NullOperator()

Now we instantiate a TreeWalker using the nulloperator - we always need to tell the TreeWalker what we want it to do at each node it visits. In this case, nothing:

      >>> walker = TreeWalker(nulloperator)

Let it walk the tree starting at some folder:

      >>> walker.walk(folder)

That's it. The nodes are visited. The operate method on the NullOperator class is called, and we expect nothing to happen.

Doing something real

Imagine you want to make a text outline or tree (like the unix tree command) showing the path of each object in a folder hierarchy. And assume you don't want to deal with the iteration details.

We can do that quite quickly. All we need to do is define an operator conforming to the IOperator interface, and pass it to a new tree walker. Here's the code from our doctest:

        >>> from zope.interface import implements
        >>> from Products.ATContentTypes.interface.operator import IOperator
        >>> class TracingOperator (object):
        ...     implements(IOperator)
        ...     def __init__(self):
        ...        self.trace = []
        ...     def getTrace(self):
        ...        return self.trace
        ...     def operate(self, context, path='', **kwargs):
        ...        self.trace.append(path)

We called it TracingOperator, because it returns a trace of the traversal of the hierarchy. We needed to add two new imports: implements which gives us the new interface rigor mentioned in the introduction, and IOperator, which is the interface we need to implement.

The constructor initializes a list that will hold the places we visit. getTrace() returns that list, and operate() is the method, defined in the IOperator interface, that is called for every node in the tree. In this case, operate() simply appends to the trace the path from the node on which the walk started.

Quoting directly from the doctest:

     Add some folders::

        >>> folder = self.folder
        >>> folder.invokeFactory('Folder', 'f1')
        'f1'
        >>> folder.f1.invokeFactory('Folder', 'subf1_1')
        'subf1_1'
        >>> folder.f1.invokeFactory('Folder', 'subf1_2')
        'subf1_2'
        >>> folder.f1.subf1_2.invokeFactory('Folder', 'subsubf1_2_1')
        'subsubf1_2_1'

Add a selection of documents:

        >>> folder.f1.invokeFactory('Document', 'd1')
        'd1'
        >>> folder.f1.d1.setText("A nice text")
        >>> folder.f1.subf1_1.invokeFactory('Document', 'd2')
        'd2'
        >>> folder.f1.subf1_1.d2.setText("A nice text")
        >>> folder.f1.subf1_1.invokeFactory('Document', 'd3')
        'd3'
        >>> folder.f1.subf1_1.d3.setText("A nice text")
        >>> folder.f1.subf1_2.subsubf1_2_1.invokeFactory('Document', 'd4')
        'd4'

      And perform the operation::

        >>> tracingoperator = TracingOperator()
        >>> tracingwalker = TreeWalker(tracingoperator)
        >>> tracingwalker.walk(folder.f1) 
        >>> trace = tracingoperator.getTrace()

We instantiate the TracingOperator, and pass it to the instantiation of TreeWalker. Then we walk, starting from the example folder we created above. By the way, folder is the root folder that we are provided by the test infrastructure.

Finally we see the list of items on the path that we visited:

        >>> print trace
          ['f1', 'f1/subf1_1', 'f1/subf1_1/d2', 'f1/subf1_1/d3', 'f1/subf1_2', 
          'f1/subf1_2/subsubf1_2_1', 'f1/subf1_2/subsubf1_2_1/d4', 'f1/d1']

This is a trace of the original folder structure. There are a couple of things to note:

• the origin of the walk, folder.f1 in this case, is seen in the result. Meaning that operate was called on it.
• intermediate folders were also visited. For example, f1/subf1_2 is a folder that contains another folder.
• folders are visited before their contents. This is a type of recursion called "pre-order" meaning that folders are visited before their contents. This seems like the most common use-case.

More on Filtering

Filtering is an important part of tree walking. It improves performance and can simplify the code in your operator. We wanted power and flexibility without complexity. Initially, filtering was simple and homogenous - the filter provided by default, or the filter optionally passed on creation, was applied across all folders in the tree. We improved this by offering a third option that we might call Heterogenous filtering, or perhaps adaptive filtering - automagically applying different filters at different nodes of a tree.

The filtering options are:

1. If a filterClass is passed as a parameter to TreeWalker(), that class is applied to filter the start node, and all sub nodes, and it is responsible for security of access to content of the tree (see later).
2. Otherwise, if a folder implements IFilterFolder, it will be adapted during recursion through that interface, and the filter configured for that type will be applied. A level of security is provided by the Filter superclass.
3. Otherwise, the default filter - FolderFilter - will be applied. FolderFilter returns all items in a folder for operation, in accordance with the security comments below.

This gives us the option, by configuration of special adapters to a type, to control the number and type of items returned on filtering. A simple example would be a PhotoAlbum, where if a custom adapter were defined, only photos and sub-albums would be returned. Any other documents in a PhotoAlbum hierarchy would be ignored during traversal of the tree. This is developed in more detail in the Implementation section, below.

Using filterClass=FolderFilter as parameter to TreeWalker(), we also have the option to easily force the operation on all allowed content (see Security, below), by forcing application of the broadest filter to all permitted folderish nodes, without exception.

Security

There is a security issue that's important to address in tree walking. In Zope a method may be invoked on a node if the user has the necessary permission for that node. But that permission does not prevent us accessing or manipulating content during the walk that the user should not normally be able to access. In the case of our Archive method, we don't want the zip archive to contain items that the user would normally not be able to see.

And from the programmer's perspective, we don't want the creator of a filter to wrestle with security concerns that we can take care of on his behalf.

To deal with both of these issues, we've created a Filter hierarchy that breaks apart the security and selection aspects of filtering into two methods. The user will normally implement the selection aspect in a new subclass of Filter, leaving our wrapper method, listPermittedObjects(), provided in the superclass, to deal with security aspect. We do not go into this in great detail here, just suffice it to say that implementing a filter adapter is as easy as this:

         class PhotoAlbumFilter(Filter):
             """
             """
             implements(IFilterFolder)

             def filter(self):
                 return self.context.ObjectValues(['Image','PhotoAlbum','Folder'])

And if you want to bypass our security completely, you always have the option to provide your own filterClass that will give you all the control and all the responsibility that goes with it.