5.6 Visitors and tree traversal

Suppose that you need a function that returns a list of all indices appearing in an arbitrary expression. The indices can have any dimension, and for indices with variance you always want the covariant version returned.

You can't use get_free_indices() because you also want to include dummy indices in the list, and you can't use find() as it needs specific index dimensions (and it would require two passes: one for indices with variance, one for plain ones).

The obvious solution to this problem is a tree traversal with a type switch, such as the following:

void gather_indices_helper(const ex & e, lst & l)
{
    if (is_a<varidx>(e)) {
        const varidx & vi = ex_to<varidx>(e);
        l.append(vi.is_covariant() ? vi : vi.toggle_variance());
    } else if (is_a<idx>(e)) {
        l.append(e);
    } else {
        size_t n = e.nops();
        for (size_t i = 0; i < n; ++i)
            gather_indices_helper(e.op(i), l);
    }
}

lst gather_indices(const ex & e)
{
    lst l;
    gather_indices_helper(e, l);
    l.sort();
    l.unique();
    return l;
}

This works fine but fans of object-oriented programming will feel uncomfortable with the type switch. One reason is that there is a possibility for subtle bugs regarding derived classes. If we had, for example, written

    if (is_a<idx>(e)) {
      ...
    } else if (is_a<varidx>(e)) {
      ...

in gather_indices_helper, the code wouldn't have worked because the first line "absorbs" all classes derived from idx, including varidx, so the special case for varidx would never have been executed.

Also, for a large number of classes, a type switch like the above can get unwieldy and inefficient (it's a linear search, after all). gather_indices_helper only checks for two classes, but if you had to write a function that required a different implementation for nearly every GiNaC class, the result would be very hard to maintain and extend.

The cleanest approach to the problem would be to add a new virtual function to GiNaC's class hierarchy. In our example, there would be specializations for idx and varidx while the default implementation in basic performed the tree traversal. Unfortunately, in C++ it's impossible to add virtual member functions to existing classes without changing their source and recompiling everything. GiNaC comes with source, so you could actually do this, but for a small algorithm like the one presented this would be impractical.

One solution to this dilemma is the Visitor design pattern, which is implemented in GiNaC (actually, Robert Martin's Acyclic Visitor variation, described in detail in http://objectmentor.com/publications/acv.pdf). Instead of adding virtual functions to the class hierarchy to implement operations, GiNaC provides a single "bouncing" method accept() that takes an instance of a special visitor class and redirects execution to the one visit() virtual function of the visitor that matches the type of object that accept() was being invoked on.

Visitors in GiNaC must derive from the global visitor class as well as from the class T::visitor of each class T they want to visit, and implement the member functions void visit(const T &) for each class.

A call of

void ex::accept(visitor & v) const;

will then dispatch to the correct visit() member function of the specified visitor v for the type of GiNaC object at the root of the expression tree (e.g. a symbol, an idx or a mul).

Here is an example of a visitor:

class my_visitor
 : public visitor,          // this is required
   public add::visitor,     // visit add objects
   public numeric::visitor, // visit numeric objects
   public basic::visitor    // visit basic objects
{
    void visit(const add & x)
    { cout << "called with an add object" << endl; }

    void visit(const numeric & x)
    { cout << "called with a numeric object" << endl; }

    void visit(const basic & x)
    { cout << "called with a basic object" << endl; }
};

which can be used as follows:

...
    symbol x("x");
    ex e1 = 42;
    ex e2 = 4*x-3;
    ex e3 = 8*x;

    my_visitor v;
    e1.accept(v);
     // prints "called with a numeric object"
    e2.accept(v);
     // prints "called with an add object"
    e3.accept(v);
     // prints "called with a basic object"
...

The visit(const basic &) method gets called for all objects that are not numeric or add and acts as an (optional) default.

From a conceptual point of view, the visit() methods of the visitor behave like a newly added virtual function of the visited hierarchy. In addition, visitors can store state in member variables, and they can be extended by deriving a new visitor from an existing one, thus building hierarchies of visitors.

We can now rewrite our index example from above with a visitor:

class gather_indices_visitor
 : public visitor, public idx::visitor, public varidx::visitor
{
    lst l;

    void visit(const idx & i)
    {
        l.append(i);
    }

    void visit(const varidx & vi)
    {
        l.append(vi.is_covariant() ? vi : vi.toggle_variance());
    }

public:
    const lst & get_result() // utility function
    {
        l.sort();
        l.unique();
        return l;
    }
};

What's missing is the tree traversal. We could implement it in visit(const basic &), but GiNaC has predefined methods for this:

void ex::traverse_preorder(visitor & v) const;
void ex::traverse_postorder(visitor & v) const;
void ex::traverse(visitor & v) const;

traverse_preorder() visits a node before visiting its subexpressions, while traverse_postorder() visits a node after visiting its subexpressions. traverse() is a synonym for traverse_preorder().

Here is a new implementation of gather_indices() that uses the visitor and traverse():

lst gather_indices(const ex & e)
{
    gather_indices_visitor v;
    e.traverse(v);
    return v.get_result();
}

Alternatively, you could use pre- or postorder iterators for the tree traversal:

lst gather_indices(const ex & e)
{
    gather_indices_visitor v;
    for (const_preorder_iterator i = e.preorder_begin();
         i != e.preorder_end(); ++i) {
        i->accept(v);
    }
    return v.get_result();
}