5
\$\begingroup\$

Here is my attempt at implementing the Acyclic visitor pattern from here in C++11.

The aim is to obtain an implementation which is easy to use and avoids all the boilerplate as much as possible. I would also like to keep the use of macros to a minimum, to keep the code readable.

To use it, one makes the visitable base class (say N) inheriting from the class AbstractVisitable, which defines the pure virtual method void accept(Visitor<>&) = 0 (and its const counterpart: void accept(Visitor<>&) const = 0).

The actual visitable classes A1, ..., An (which are subclasses of N), need to use the macro CONCRETE_VISITABLE which implements the accept method. Finally, an actual visitor is implemented by deriving from Visitor<A1, ..., An>, and implementing the method void visit(Ai&) override {...} for each class A1, ..., An.

There is also the VisitorFunction class, which is used to simplify the common tasks of passing a parameter to the visitor and getting a result from its application.

Visitor.h

#ifndef VISITOR_H_
#define VISITOR_H_

#include <stdexcept>
#include <string>
#include <sstream>
#include <type_traits>
#include <typeinfo>
#include <utility>


template<typename... Ts>
struct Visitor {
    virtual ~Visitor() = default;
};

template<typename T>
struct Visitor<T>: public virtual Visitor<> {
    virtual void visit(T&) = 0;
};

template<typename T, typename... Us>
struct Visitor<T, Us...>: public Visitor<T>, public Visitor<Us>... { };

template<typename... Ts>
using ConstVisitor = Visitor<const Ts...>;


struct AbstractVisitable {
    virtual ~AbstractVisitable() = default;
    virtual void accept(Visitor<>&) = 0;
    virtual void accept(Visitor<>&) const = 0;

protected:
    template<typename T>
    static inline void acceptImpl(Visitor<>& v, T& p) {
        if (auto* av = dynamic_cast<Visitor<T>*>(&v))
            av->visit(p);
        else if (auto* av = dynamic_cast<Visitor<const T>*>(&v))
            av->visit(p);
        else
            throw std::domain_error(std::string() + typeid(v).name() +
                    " does not implement Visitor< " +
                    typeid(T).name() + " >");
    }
};


#define CONCRETE_VISITABLE \
    void accept(Visitor<>& v) override { \
        using TypeOfThis = std::remove_pointer<decltype(this)>::type; \
        AbstractVisitable::acceptImpl<TypeOfThis>(v, *this); } \
    \
    void accept(Visitor<>& v) const override { \
        using TypeOfThis = std::remove_pointer<decltype(this)>::type; \
        AbstractVisitable::acceptImpl<TypeOfThis>(v, *this); }



template<typename Ret, typename... Ts>
struct VisitorFunction;

template<typename Ret, typename Arg, typename... VisitableTypes>
struct VisitorFunction<Ret(Arg), VisitableTypes...>:
        Visitor<VisitableTypes...> {
    VisitorFunction(Arg parameter, Ret initialResult = Ret()):
        parameter(parameter), result(initialResult) {}
    Arg parameter;
    Ret result;

    template<typename T>
    Ret accept(T& v) {
        v.accept(*this);
        return result;
    }
};

template<typename Arg, typename... VisitableTypes>
struct VisitorFunction<void(Arg), VisitableTypes...>:
        Visitor<VisitableTypes...> {
    VisitorFunction(Arg parameter): parameter(parameter) {}
    Arg parameter;

    template<typename T>
    void accept(T& v) {
        v.accept(*this);
    }
};

template<typename Ret, typename... VisitableTypes>
struct VisitorFunction<Ret(), VisitableTypes...>:
        Visitor<VisitableTypes...> {
    VisitorFunction(Ret initialResult = Ret()):
        result(initialResult) {}
    Ret result;

    template<typename T>
    Ret accept(T& v) {
        v.accept(*this);
        return result;
    }
};


#endif /* VISITOR_H_ */

test.cpp

#include "Visitor.h"

#include <functional>
#include <iostream>


struct Node: public AbstractVisitable { };

struct A: public Node {
    CONCRETE_VISITABLE
};

struct B: public Node {
    CONCRETE_VISITABLE
};

struct C: public Node {
    CONCRETE_VISITABLE
};

struct ZC: public C {
    CONCRETE_VISITABLE
};


struct BasicVisitor: Visitor<A, B, C, ZC> {
    void visit(A&) override {
        std::cout << "A" << std::endl;
    }
    void visit(B&) override {
        std::cout << "B" << std::endl;
    }
    void visit(C&) override {
        std::cout << "C" << std::endl;
    }
    void visit(ZC&) override {
        std::cout << "ZC" << std::endl;
    }
};


struct BasicConstVisitor: ConstVisitor<A, B> {
    void visit(const A&) override {
        std::cout << "A" << std::endl;
    }
    void visit(const B&) override {
        std::cout << "B" << std::endl;
    }
};


struct FuncVisitor: VisitorFunction<int(std::string), A, B, C> {
    using VisitorFunction::VisitorFunction;

    void visit(A&) override {
        std::cout << "A " << parameter << std::endl;
        result += 1;
    }
    void visit(B&) override {
        std::cout << "B" << std::endl;
        result += 10;
    }
    void visit(C&) override {
        std::cout << "C" << std::endl;
        result += 100;
    }
};


struct VoidFuncVisitor: VisitorFunction<void(std::string), A, B, C> {
    using VisitorFunction::VisitorFunction;

    void visit(A&) override {
        std::cout << "A" << parameter << std::endl;
    }
    void visit(B&) override {
        std::cout << "B" << std::endl;
    }
    void visit(C&) override {
        std::cout << "C" << std::endl;
    }
};

int main() {
    A a; Node& n1 = a;
    B b; Node& n2 = b;
    C c; Node& n3 = c;

    BasicVisitor basic;
    Visitor<>& vis1 = basic;
    n1.accept(vis1);
    n2.accept(vis1);
    n3.accept(vis1);

    BasicConstVisitor basicConst;
    Visitor<>& visConst1 = basicConst;
    n1.accept(visConst1);
    n2.accept(visConst1);

    ZC zc;
    zc.accept(vis1);

    int result = FuncVisitor("PARAM", 50000).accept(n1);
    std::cout << "Result: " << result << std::endl;

    return 0;
}
\$\endgroup\$
1
\$\begingroup\$
  1. You can simplify your Visitor-template:

    template<class... T>
    struct Visitor : Visitor<T>... {
        virtual ~Visitor() = default;
    };
    
    template<class T>
    struct Visitor<T> : virtual Visitor<> {
        virtual void visit(T&) = 0;
    };
    

    It's a shame C++ doesn't have real mixin's, or we would mark Visitor with at least two template-arguments as a pure compile-time fiction.

  2. You are adding expensive logic to accept a Visitor<const T> wherever you accept a Visitor<T>. Making all Visitor<const T> derive from the corresponding Visitor<T> is far cheaper. Just add a specialization:

    template <class T>
    struct Visitor<const T> : Visitor<T> {
        void visit(T& t) override { visit((const T&)t); }
        virtual void visit(const T&) = 0;
    };
    

    Unfortunately, adding explicit specializations allowing a Visitor<Base> to visit a Derived, where both kinds of visitors might exist, would contravene the pattern's aims. There extra-logic is needed despite the runtime-cost.

  3. Visitable bases should have something more in common than that they are visitable, which sharply diminishes the usefulness of a baseclass of all visitable types (meaning it should be a mixin for performance, if we had such).
    And a mixin instead of templates or macros for adding the implementations for the accept-functions would also be nice.
    Well, let's do the best we can with what we have, the CRTP, to at least diminish the need for even more multiple inheritance:

    namespace detail {
        struct dummy {};
        template <class T>
        inline void accept(Visitor<>& v, T&) {
            throw std::domain_error(std::string(typeid(v).name()) +
                " does not implement any visitor for " + typeid(T).name());
        }
        template <class T, class X, class... Z>
        inline void accept(Visitor<>& v, T& p) {
            if(auto* av = dynamic_cast<Visitor<X>*>(&v))
                av->visit(dynamic_cast<X&>(p));
            else
                accept<T, Z...>(v, p);
        }
    }
    
    template <class B = void, class... T>
    struct Visitable : std::conditional<std::is_class<B>::value, B, Visitable<>>::type {
        virtual ~Visitable() = default;
        virtual void accept(Visitor<>& v) { detail::accept<Visitable, T...>(v, *this); };
        virtual void accept(Visitor<>& v) const {
            detail::accept<const Visitable, const T...>(v, *this); };
    };
    
    template <class B>
    struct Visitable<B> : std::conditional<std::is_class<B>::value, B, detail::dummy>::type {
        virtual ~Visitable() = default;
        virtual void accept(Visitor<>&) = 0;
        virtual void accept(Visitor<>&) const = 0;
    };
    
  4. A visitor visits, it doesn't accept. If you want to ask a visitor to visit somewhere, a good name is tryVisit.

See http://coliru.stacked-crooked.com/a/603efde5268ff999 for the fully-modified version.

\$\endgroup\$
  • \$\begingroup\$ Thanks. Some doubts. (1) The class hierarchy is changed, since A,B,C,ZC do not directly derive from Node anymore. The derivation from Node is hidden in the definition of Visitable. What if the derivation from Node is declared virtual? (2) The base class Node, and the subclasses A,B,C,ZC, all derive from Visitable<...>. According to the Visitor pattern, they are conceptually different, since Node defines the pure virtual method visit(...), which is implemented by the visitable subclasses. I think leaving Node implementing a different class AbstractVisitable is better. \$\endgroup\$ – Ghx Oct 24 '15 at 15:25
  • \$\begingroup\$ Well, you shouldn't see the use of Visitor<2+ types> as anything but an implementation-detaill which should be ignored. Dito for any of the Visitable<T,...>, where T already has the two virtual member-functions (Or it's just used for implementing the real root-class). So yes, there are new classes in the inheritance-hierarchy, but those should be ignored. \$\endgroup\$ – Deduplicator Oct 24 '15 at 15:56

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.