Visitor pattern: To cast or not to cast

[kainev]

Hi all,

I've just started using C++ (from Python/Java), I'm trying to implement a basic visitor design pattern to be recursively used on a tree data structure.

I've got two methods in my mind but am unsure about what would be better.

The first is to define a degenerate Visitor class, containing only a virtual destructor:

class Visitor
{
public:
    virtual ~Visitor() = 0;
}

Then, define a Visitable interface:

class Visitable
{
public:
    virtual void accept(Visitor& visitor) = 0;
}

Now, any node in my data structure that I want to be visitable will inherit from the Visitable interface, and I will create an implementation of Visitor for that specific node, and use a dynamic_cast to cast the Visitor to the derived Visitor.

class MyNode : public Visitable
{
public:
    void accept(Visitor& visitor)
    {
        if (MyNodeVisitor* myNodeVisitor = dynamic_cast<MyNodeVisitor*>(&visitor))
        {
            myNodeVisitor->visit(this);
        }
    }
}

class MyNodeVisitor : public Visitor
{
public:
    void visit(MyNode& node)
    {
        // do stuff on node
    }
}

So with this method I would need to create a visitor for each type of visitable node, however I could use generics to eliminate that, but keeping things simple for now. A concern of mine is the overhead of using a dynamic_cast. Especially as for my little project performance is really important.

The next thing I could do is change the Visitable class to have a method for every node type that returns itself as that type, OR returns 0 if its not that type, such as:

class Visitable
{
public:
    virtual void accept(Visitor& visitor) = 0;

    virtual MyNode* getMyNode() { return 0; }
    virtual MyOtherNode* getMyOtherNode() { return 0; }
}

Then the MyNode class would override the 'getMyNode' function and return itself, but would NOT override the MyOtherNode method, thus it would return 0 if called on MyNode. Then we would update the classes to the following:

class Visitor
{
public:
    virtual void visit(Visitable& node) = 0;
}

class MyNode : public Visitable
{
public:
    void accept(Visitor& visitor)
    {
        visitor->visit(this)
    }

    MyNode* getMyNode() override
    {
        return this;
    }
}

class MyNodeVisitor : public Visitor
{
public:
    void visit(Visitable& node) override
    {
        if(MyNode* myNode = node.getMyNode())
        {
            // do stuff
        }
    }
}

I'd like to know peoples thoughts on both methods, I'm concerned about the overhead of dynamic_cast but it seems to be a cleaner solution, however for the sake of writing a few extra functions in the Visitable class I feel it may be worth it. Also there are probably a million typos in my code, I wrote it in here and I can't preview for some reason.

Thanks!

[dhayden]

I don't think the dynamic cast is expensive, but if you're going to use it then shouldn't you check to see if it returns nullptr? That will happen if MyNode::accept() is passed something that isn't a MyNodeVisitor (or a class derived from it).

I understand that this is just an exercise, but keep in mind that the simplest code is usually the best. Unless you really need this level of complexity, I'd stick with something simpler.

[keskiverto]

Random example by websearch shows no cast: https://sourcemaking.com/design_patterns/visitor/cpp/2

[icy1]

I think dynamic_cast is worth it for maintainability. You need the run-time checking, or you'll have uninvited visitors with static_cast or reinterpret cast.

Edit: added in code for both ways.

#include <iostream>
#include <string>

using namespace std;

class Visitor;
class Visitable
{
public:
    virtual string Name() { return "Visitable"; };
    virtual void Accept(Visitor& visitor) = 0;
};

class Visitor
{
public:
    virtual string Name() = 0;
    virtual void Visit(Visitable* node) = 0;
    virtual bool IsMyNode() = 0;
    virtual bool IsAnother() = 0;
    virtual bool IsUninvited() = 0;
protected:
    virtual ~Visitor() = default;
};

class MyNode;
class MyNodeVisitor : public Visitor
{
public:
    string Name() override { return "MyNodeVisitor"; }
    void Visit(Visitable* node)
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
    bool IsMyNode() override { return true; }
    bool IsAnother() override { return false; }
    bool IsUninvited() override { return false; }
};

struct AnotherVisitor : public Visitor 
{
    string Name() override { return "AnotherVisitor"; }
    void Visit(Visitable* node) override
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
    
    void Specific(Visitable* node)
    {
        cout << Name() << " was specifically visited  by "<<node->Name() <<".\n";
    }
    
    bool IsMyNode() override { return false; }
    bool IsAnother() override { return true; }
    bool IsUninvited() override { return false; }
};

struct UninvitedVisitor : public Visitor 
{
    string Name() override { return "UninvitedVisitor"; }
    void Visit(Visitable* node) override
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
    bool IsMyNode() override { return false; }
    bool IsAnother() override { return false; }
    bool IsUninvited() override { return true; }
};

class MyNode : public Visitable
{
public:
    string Name() override { return "MyNode"; }
    void Accept(Visitor& visitor) override
    {
        // Alternately:
        //if (dynamic_cast<MyNodeVisitor*>(&visitor))
        if (visitor.IsMyNode())
        {
            visitor.Visit(this);
        }
        // Alternately:
        //else if (auto a = dynamic_cast<AnotherVisitor*>(&visitor))
        else if (visitor.IsAnother())
        {
            auto a = static_cast<AnotherVisitor*>(&visitor);
            a->Specific(this);
        }
        else 
        {
            cout << visitor.Name() << " doesn't get any dinner.\n";
        }
    }
};


int main()
{
    MyNode my;
    MyNodeVisitor my_node_visitor;
    AnotherVisitor another_visitor;
    UninvitedVisitor uninvited_visitor;
    
    my.Accept(my_node_visitor);
    my.Accept(another_visitor);
    my.Accept(uninvited_visitor);
    
    return 0;
}

can test at https://repl.it/repls/StableDismalMatrix

MyNodeVisitor was visited by MyNode.
AnotherVisitor was specifically visited  by MyNode.
UninvitedVisitor doesn't get any dinner.

The core question you're trying to ask here, "Is Visitor 'v' a BarVisitor?" , would alternately be solved by having pure virtual methods in Visitor. But these will add up the more derived classes you make.

class Visitor
{
public:
// ...
    virtual bool IsMyNode() = 0;
    virtual bool IsAnother() = 0;
    virtual bool IsUninvited() = 0;
// ...
};

And each of the children will have to respond accordingly with true or false. If just checking against the parent, you'll still need to cast in order to use children-specific methods, but once you've determined the type for sure, you can get away with a static_cast.

[icy1]

@keskiverto -- yes that example is not being visited by Base but decided to make separate methods for each child, so could do that, too.

[keskiverto]

Gang of Four's version of Visitor https://en.wikipedia.org/wiki/Visitor_pattern
"adds new functions to a family of classes, without modifying the classes"

If the family of classes cares about the actual type of the visitors, then you need to modify the classes when you add new visitor types. Are there more than one visitor pattern?

[JLBorges]

This is (the most common implementation of) the acyclic vistor pattern/
https://condor.depaul.edu/dmumaugh/OOT/Design-Principles/acv.pdf
http://www.cplusplus.com/forum/general/136902/

[kainev]

Thanks for the replies everyone!

@icy1 Thanks for the great example. One thing though, regarding if we chose the casting method, is instead of having an if statement in the Accept function, I think maybe you would create the MyNodeVisitor as an abstract class, and then inherit from that and override the the visit method, such as:

class MyNodeVisitor : public Visitor
{
public:
    string Name() override { return "MyNodeVisitor"; }
    virtual void Visit(Visitable* node) = 0;
};

class MyNodeVisitorFoo : public MyNodeVisitor 
{
public:
    string Name() override { return "MyNodeVisitorFoo"; }
    void Visit(Visitable* node) override
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
};

class MyNodeVisitorBar : public MyNodeVisitor 
{
public:
    string Name() override { return "MyNodeVisitorBar"; }
    void Visit(Visitable* node) override
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
};

That way you wouldn't have to chain if statements to define new visitors. Otherwise as @keskiverto mentioned, you'd be modifying the classes when adding new visitor types, which goes against the pattern.
Also, for the other method, instead of doing:

class Visitor
{
public:
// ...
    virtual bool IsMyNode() = 0;
    virtual bool IsAnother() = 0;
    virtual bool IsUninvited() = 0;
// ...
};

couldn't we instead do:

class Visitor
{
public:
// ...
    virtual bool IsMyNode() { return 0; };
    virtual bool IsAnother() { return 0; };
    virtual bool IsUninvited() { return 0; };
// ...
};

That way we only have to add these methods to the base Visitor class, and in what ever derived class, we only need to override the specific function:

class MyNodeVisitor : public Visitor
{
public:
    string Name() override { return "MyNodeVisitor"; }
    void Visit(Visitable* node)
    {
        cout << Name() << " was visited by " << node->Name() << ".\n";
    }
    bool IsMyNode() override { return true; }
};

What do you think?

@JLBorges
Thanks for the links, seems like dynamic_cast is probably the way to go.

[icy1]

One thing though, regarding if we chose the casting method, is instead of having an if statement in the Accept function, I think maybe you would create the MyNodeVisitor as an abstract class, and then inherit from that and override the the visit method, such as:

Going with the casting method, it seems one if statement is unavoidable, since the cast could return a nullptr. With dynamic_cast, everything should work without needing a second set of derivations (that is, everyone derives from Visitor).
As for chaining, I had chained "if" statements to also show a sort of error handling, as well as potentially call a method specific to a child (though I guess this is outside the pattern).

As keskiverto said, if following the true visitor pattern, try to avoid any sort of casting altogether and delegate to a Dispatcher, who knows about everyone and hopefully is one of the only ones to recompile.

Yeah, your tweak to the query methods to reduce clutter looks reasonable (but write out 'false' instead of 0 ;D).

[kainev]

Alright, things are starting to make sense in my head.. except this article that @JLBorges linked:
https://condor.depaul.edu/dmumaugh/OOT/Design-Principles/acv.pdf

Is almost exactly the same as the above implementations, HOWEVER, the accept functions are marked as const. Taken straight from the article:

void ZoomModem::Accept(Visitor& v) const
{
 if (ZoomModemVisitor* zv = dynamic_cast<ZoomModemVisitor*>(&v))
 zv->Visit(*this);
 else
 // AcceptError
}

My issue with this is that since 'Accept' is const, the `this` keyword returns a const. Then their Visit function is:

virtual void Visit(ZoomModem&); // configure Zoom for Unix 

(They don't provide an implementation of the method)

This would surely return an error no? From my quick checks in Visual studio, I can't get this to work. Surely if the Accept method is marked const, you would have to change the visit method to:

virtual void Visit(const ZoomModem&); // configure Zoom for Unix 

which defeats the purpose as then you can't really add additional functionality to a class, only read data from it.

Am I missing something?

[JLBorges]

> Surely if the Accept method is marked const, you would have to change the visit method to:
> virtual void Visit(const ZoomModem&); // configure Zoom for Unix
> which defeats the purpose as then you can't really add additional functionality to a class,
> only read data from it.

Yes.

Of course it is possible to provide two overloads (const and non-const) for both Visit and Accept, if we want to maintain the distinction between visitors which are observers and visitors which are modifiers.