5
\$\begingroup\$

Motivation

I created this because the Visitor pattern felt like the most appropriate, but I also wanted to satisfy the Open/Closed principle with respect to the logic when visiting specific node types. I also needed the ability to "return" a specialized value type from visitation without wanting to tie that knowledge to the visitable hierarchy. Why should those objects have to care what I'm making out of them?

The Visitor/Visitable classes are defined mostly as by Alexandrescu.

[Note: The existing codebase uses Qt, so I left the Qt classes intact rather than switch them for std equivalents.]

Visitor/Visitable Classes:

// Strawman base class
class BaseVisitor
{
public:
    virtual ~BaseVisitor() {};
};

// Class template for visitor, template params are type visited and return type of visit
template <class T, class R>
class Visitor
{
public:
    virtual R visit(const T &) = 0;
};

// Class template for visitable, template param is the return type of accept

template <class R>
class BaseVisitable
{
public:
    virtual ~BaseVisitable() {};
    virtual R accept(BaseVisitor &)
    {
        return (R) 0;
    }

    typedef R ReturnType;
protected:
    template <class T>
    static ReturnType acceptVisitor(const T &visited, BaseVisitor &visitor)
    {
        if (typeid(visited) == typeid(T))
        {
            auto p = dynamic_cast<Visitor<T, ReturnType> *> (&visitor);
            // We want to ignore non-specified nodes
            if (p != nullptr)
                return p->visit(visited);
            else
                return (ReturnType) 0;
        }
        else
        {
            throw std::runtime_error("typeid(T) doesn't match typeid(visited)! Did your inherited class miss DEFINE_VISITABLE()?");
        }
    }

};

#define DEFINE_VISITABLE() \
            virtual ReturnType accept(BaseVisitor &v) const \
                { return acceptVisitor(*this, v); }

Visitable Hierarchy

class VisitableBase : public BaseVisitable<void>
{
public:
    DEFINE_VISITABLE();
};

class VisitableDerived : public VisitableBase
{
public:
    DEFINE_VISITABLE();
};

class VisitableDerived2 : public VisitableBase
{
public:
    DEFINE_VISITABLE();
};

Code Under Review

This is where I did things differently than implement the standard Visitor class. I basically added subclasses of Visitor<T,R> and moved some logic from the master Visitor (that inherits all the Visitor<T,R> classes) into a base class.

Base Builder Class

Simple class to collect the values I'm trying to return from visitation. Doesn't have to be a class template, just contain the appropriate logic to aggregate the returned values.

class Collector
{
protected:
    void addToStack(const std::string& s)
    {
        m_stack.push(s);
    }

    QStack<std::string> getStack()
    {
        return m_stack;
    }

private:
    QStack<std::string> m_stack;
};

Converter

Inherits from Visitor<T,void> and virtually from Collector. This let me decouple conversion from visitation, and retain common logic for aggregating the results since the traditional Visitor classes can't access their derived master Visitor to do so.

template <typename VisitedType>
class Converter
    : public Visitor<VisitedType, void>
    , public virtual Collector
{
public:
    Converter(){ }
    virtual QString convert(const VisitedType& visited) = 0;

    virtual void visit(const VisitedType& visited) override
    {
        addToStack(convert(visited));
    }
};

Example Converter Classes

These inherit from Converter<T> and are my modification points.

class VisitableDerivedConverter : public Converter<VisitableDerived>
{
public:
    virtual QString convert(const VisitableDerived&) override
    {
        return "Normally converted VisitableDerived";
    }
};

class FabulousVisitableDerivedConverter : public Converter<VisitableDerived>
{
public:
    virtual QString convert(const VisitableDerived&) override
    {
        return "Fabulously converted VisitableDerived";
    }
};

class VisitableDerived2Converter : public Converter<VisitableDerived2>
{
public:
    virtual QString convert(const VisitableDerived2&) override
    {
        return "Normally converted VisitableDerived2";
    }
};

The client-facing Visitor

This is largely the same as the traditional visitor, but using variadic templates because not all nodes need to be handled.

template<typename... T>
class ConverterVisitor : public BaseVisitor
    , public T...
{
public:
    void talkAboutIt()
    {
        for (auto each : Collector::getStack())
        {
            qDebug() << each;
        }
    }
};

Usage

Example usage:

{
    auto newBuilder1 = new ConverterVisitor<VisitableDerivedConverter>();

    auto newBuilder2 = new ConverterVisitor<VisitableDerivedConverter, VisitableDerived2Converter>();

    auto newBuilder3 = new ConverterVisitor<FabulousVisitableDerivedConverter, VisitableDerived2Converter>();

    VisitableBase* visitable = new VisitableDerived();
    VisitableBase* visitable2 = new VisitableDerived2();

    qDebug() << "Builder1...";

    visitable->accept(*newBuilder1);
    visitable2->accept(*newBuilder1);

    newBuilder1->talkAboutIt();

    qDebug() << "Builder2...";

    visitable->accept(*newBuilder2);
    visitable2->accept(*newBuilder2);

    newBuilder2->talkAboutIt();

    qDebug() << "Builder3...";

    visitable->accept(*newBuilder3);
    visitable2->accept(*newBuilder3);

    newBuilder3->talkAboutIt();

}

And corresponding output:

 Builder1...
 "Normally converted VisitableDerived"
 Builder2...
 "Normally converted VisitableDerived"
 "Normally converted VisitableDerived2"
 Builder3...
 "Fabulously converted VisitableDerived"
 "Normally converted VisitableDerived2"

My Thoughts

Pros:

  • Feels clean
  • Implementing new conversion logic for a given node is easy
  • Construction and conversion logic are fairly well decoupled

Cons:

  • ConverterBuilder and Collector are more strongly coupled than they first appear, and effectively need to be designed together (or at least ConverterBuilder must be designed with consideration of the Collector)
  • Relies on the "dreaded diamond," which people don't like (but multiple inheritance is not necessarily evil)

Hopes and Dreams:

  • I would really love a lot more static_asserts and compiler errors to make it harder to use incorrectly. For example, including both VisitableDerivedConverter and FabulousVisitableDerivedConverter would ideally fail to compile, but currently results in that node getting skipped entirely (the dynamic_cast fails.)
  • The pattern would be a lot more reusable if Collector logic was a policy of the ConverterVisitor and configurable at design time. I can see a way to do this by having the Converter implementations also be class templates, but they shouldn't require knowledge that aggregation policies even exist. It's also highly desirable that the Converter implementations remain unit-testable, and hence instantiable in isolation.
\$\endgroup\$
  • \$\begingroup\$ When I copy your code to a Qt-Creator console project I get two compiler error messages (will put them into the two next comments for better readability): \$\endgroup\$ – πάντα ῥεῖ Jan 27 '17 at 17:48
  • \$\begingroup\$ C:\Users\g-mak_000\Documents\ModularVisitor\main.cpp:145: Fehler: there are no arguments to 'getStack' that depend on a template parameter, so a declaration of 'getStack' must be available [-fpermissive] for (auto each : getStack()) ^ \$\endgroup\$ – πάντα ῥεῖ Jan 27 '17 at 17:48
  • \$\begingroup\$ C:\Users\g-mak_000\Documents\ModularVisitor\main.cpp:50: Fehler: no matching function for call to 'std::exception::exception(const char [91])' throw std::exception("typeid(T) doesn't match typeid(visited)! Did your inherited class miss DEFINE_VISITABLE()?"); ^ \$\endgroup\$ – πάντα ῥεῖ Jan 27 '17 at 17:49
  • \$\begingroup\$ Fix these 1st please before asking for a review. For easy access I'll share what I have at coliru (fails to compile and run of course there). \$\endgroup\$ – πάντα ῥεῖ Jan 27 '17 at 17:51
  • \$\begingroup\$ @πάνταῥεῖ I edited to fix the second error, MSVC allows that constructor for std::exception, but it's non-standard. Here's an edited version of your coliru that compiles and runs: coliru.stacked-crooked.com/a/fd7059231595baef \$\endgroup\$ – John Neuhaus Jan 27 '17 at 19:03
3
\$\begingroup\$

The visitor pattern and open closed principle. There is a mild conflict here.

The visitor pattern is very good when you have a static class hierarchy and just want different ways to traverse the nodes in some collection. In these situations the visitor pattern behaves very well.

BUT

If the class hierarchy is not stable and you are adding new types of nodes then it does not behave very well. This is because every new class that you add to the hierarchy will require a new method in the visitor object (unless you want to default them using some template method to handle the new nodes).

Design

Not sure I agree with your design at all.
This is what a standard visitor pattern looks like.

 class A;
 class B;
 class C;
 class D;
 class E;
 class AlphaVisitor
 {
      public:
          virtual void visit(A& a) = 0;
          virtual void visit(B& b) = 0;
          virtual void visit(C& c) = 0;
          virtual void visit(D& d) = 0;
          virtual void visit(E& e) = 0;
 };
 class A {public: accept(AlphaVisitor& v) {/* STUFF*/ v.visit(*this);}};
 class B {public: accept(AlphaVisitor& v) {/* STUFF*/ v.visit(*this);}};
 class D {public: accept(AlphaVisitor& v) {/* STUFF*/ v.visit(*this);}};
 class E {public: accept(AlphaVisitor& v) {/* STUFF*/ v.visit(*this);}};

In your code both accept() and visit() return an R. This is not normal. It may be very big object that is returned. You don't want to copy that around. It is more common for the AlphaVisitor to accumulate state as it visits objects. Then when it has finished visiting then you can access the state from the visitor object itself.

 A                a(/* construct some large graph of A/B/C/D/E */);


 MyDerivedVisitor visitor;
 a.accept(visitor);

 ResultType value = visitor.getResult();

Code Review

R had better be constructible with an integer. Otherwise this will fail to even compile.

virtual R accept(BaseVisitor &)
{
    return (R) 0;
}

Runtime type checking is not a good idea. That is why we have the visitor pattern to prevent this.

static ReturnType acceptVisitor(const T &visited, BaseVisitor &visitor)
{
    if (typeid(visited) == typeid(T))
    {
    }
    else
    {
        throw std::runtime_error("typeid(T) doesn't match typeid(visited)! Did your inherited class miss DEFINE_VISITABLE()?");
    }
}

Please don't do this:

auto newBuilder1 = new ConverterVisitor<VisitableDerivedConverter>();

auto newBuilder2 = new ConverterVisitor<VisitableDerivedConverter, VisitableDerived2Converter>();

auto newBuilder3 = new ConverterVisitor<FabulousVisitableDerivedConverter, VisitableDerived2Converter>();

Just declare your variables locally.

ConverterVisitor<VisitableDerivedConverter>   newBuilder1;
ConverterVisitor<VisitableDerivedConverter, VisitableDerived2Converter>  newBuilder2;

ConverterVisitor<FabulousVisitableDerivedConverter, VisitableDerived2Converter>   newBuilder3;

The same as above

VisitableDerived  visitable;
VisitableDerived2 visitable2;

visitable.accept(newBuilder1);
visitable2.accept(newBuilder1);
\$\endgroup\$
  • \$\begingroup\$ Woops, my mistake on those autos, wasn't thinking hard enough when I wrote the usage part. The BaseVisitable and Visitor are Alexandrescu's Acyclic Visitor from Modern C++ Design almost verbatim, although I usually end up using void as the return type, so it's fair to question even bothering with it. I added the typeid check and exception to catch when DEFINE_VISITABLE has been missed in the visited hierarchy, rather than let it silently upcast. \$\endgroup\$ – John Neuhaus Jan 28 '17 at 0:06
  • \$\begingroup\$ The visited hierarchy in my case is stable and large, so that's not a concern. One question: is that the limit of your critique, or did you stop at the most egregious things? It was the classes built on top of the Acyclic Visitor pattern that I was most hoping for feedback on. \$\endgroup\$ – John Neuhaus Jan 28 '17 at 0:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.