6
\$\begingroup\$

The goal is to minimize boilerplate code for creating visitors while allowing users to easily define custom visitors without having to add new accept methods for each visitor type. For example, a standard visitor pattern with five visitable classes A, B, C, D and E and two visitor types could be

  struct A;
  struct B;
  struct C;
  struct D;
  struct E;

  struct AEVisitor{
    virtual void visit(A &a) = 0;
    virtual void visit(E &a) = 0;
  };

  struct ABCDVisitor{
    virtual void visit(A &a) = 0;
    virtual void visit(B &b) = 0;
    virtual void visit(C &c) = 0;
    virtual void visit(D &d) = 0;
  };

  struct A{
    virtual void accept(AEVisitor &v){ v.visit(*this); }
    virtual void accept(ABCDVisitor &v){ v.visit(*this); }
  };

  struct B:public virtual A{
    void accept(ABCDVisitor &v)override{ v.visit(*this); }
  };

  struct C:public virtual A{
    void accept(ABCDVisitor &v)override{ v.visit(*this); }
  };

  struct D:public B,public C{
    void accept(ABCDVisitor &v)override{ v.visit(*this); }
  };

  struct E:public A{
    void accept(AEVisitor &v)override{ v.visit(*this); }
  };

  struct PrintAEVisitor:public AEVisitor{
    void visit(A &a){ LOG("visit A"); }
    void visit(E &a){ LOG("visit E"); }
  };

  struct PrintABCDVisitor:public ABCDVisitor{
    void visit(A &a){ LOG("visit A"); }
    void visit(B &b){ LOG("visit B"); }
    void visit(C &c){ LOG("visit C"); }
    void visit(D &d){ LOG("visit D"); }
  };

where, for additional complexity, the inheritance between A, B, C and D forms a diamond. Both visitors are able to visit all five types and will fallback to visiting the A base class. With the acyclic visitor pattern the code is reduced to

  struct A:public Visitable<A>{ };
  struct B:public Visitable<B,A>{ };
  struct C:public Visitable<C,A>{ };
  struct D:public Visitable<D,B,C>{ };
  struct E:public Visitable<E,A>{ };

  struct PrintAEVisitor:public Visitor<A,E>{
    void visit(A &a){ LOG("visit A"); }
    void visit(E &a){ LOG("visit E"); }
  };

  struct PrintABCDVisitor:public Visitor<A,B,C,D>{
    void visit(A &a){ LOG("visit A"); }
    void visit(B &b){ LOG("visit B"); }
    void visit(C &c){ LOG("visit C"); }
    void visit(D &d){ LOG("visit D"); }
  };

and is effectively identical to before. Internally this can be implemented by letting the accept method of the visitable objects check if the visitor is supported e.g. by using dynamic_cast. However dynamic_cast introduces in a significant overhead. Alternatively we use a dictionary std::unordered_map<std::typeindex,void*> to lookup and cast the visitor to the required type.

The Visitor and Visitable templates are implemented as

#define VISITOR_NO_DYNAMIC_CAST

#ifdef VISITOR_NO_DYNAMIC_CAST
#include <unordered_map>
#include <typeinfo>
#include <typeindex>
#endif

#ifndef VISITOR_NO_EXCEPTIONS
#include <exception>
#endif

class VisitableBase;
template <typename ... Args> class Visitor;
template <typename ... Args> class ConstVisitor;
template <typename ... Args> class Visitable;

template <template <typename ... Args> class Visitor> class VisitorBasePrototype{
#ifdef VISITOR_NO_DYNAMIC_CAST
protected:
  std::unordered_map<std::type_index,void *> derived_types;
public:
  template <class T> Visitor<T> * as_visitor_for(){
    auto it = derived_types.find(typeid(Visitor<T>));
    if(it == derived_types.end()) return nullptr;
    return reinterpret_cast<Visitor<T>*>(it->second);
  }
#else
public:
  template <class T> Visitor<T> * as_visitor_for(){
    return dynamic_cast<Visitor<T> *>(this);
  }
#endif
  virtual ~VisitorBasePrototype(){}
};

using VisitorBase = VisitorBasePrototype<Visitor>;
using ConstVisitorBase = VisitorBasePrototype<ConstVisitor>;;

class VisitableBase{
public:
  virtual void accept(VisitorBase &visitor) = 0;
  virtual void accept(ConstVisitorBase &visitor)const = 0;
  virtual ~VisitableBase(){}
};

template <typename First,typename Second,typename ... Rest> class Visitor<First,Second,Rest...>:public Visitor<First>,public Visitor<Second,Rest...>{
public:
  using ConstVisitor = ::ConstVisitor<First,Second,Rest...>;
};

template <typename T> class Visitor<T>:public virtual VisitorBase{
public:
  using ConstVisitor = ::ConstVisitor<T>;

#ifdef VISITOR_NO_DYNAMIC_CAST
  Visitor(){
    VisitorBase::derived_types.emplace(typeid(Visitor<T>),reinterpret_cast<void*>(this));
  }
#endif
  virtual void visit(T &) = 0;
};

template <typename First,typename Second,typename ... Rest> class ConstVisitor<First,Second,Rest...>:public ConstVisitor<First>,public ConstVisitor<Second,Rest...>{
public:
};

template <typename T> class ConstVisitor<T>:public virtual ConstVisitorBase{
public:
#ifdef VISITOR_NO_DYNAMIC_CAST
  ConstVisitor(){
    ConstVisitorBase::derived_types.emplace(typeid(ConstVisitor<T>),reinterpret_cast<void*>(this));
  }
#endif
  virtual void visit(const T &) = 0;
};

#ifndef VISITOR_NO_EXCEPTIONS
struct IncompatibleVisitorException:public std::exception{};
#endif

template <class T> class Visitable<T>:public virtual VisitableBase{
public:

#ifndef VISITOR_NO_EXCEPTIONS
  struct IncompatibleVisitorException:public ::IncompatibleVisitorException{};
#endif

  void accept(VisitorBase &visitor)override{
    if(auto casted = visitor.as_visitor_for<T>()){
      casted->visit(static_cast<T &>(*this));
    }
    else{
#ifndef VISITOR_NO_EXCEPTIONS
      throw IncompatibleVisitorException();
#endif
    }
  }

  void accept(ConstVisitorBase &visitor)const override{
    if(auto casted = visitor.as_visitor_for<T>()){
      casted->visit(static_cast<const T &>(*this));
    }
    else{
#ifndef VISITOR_NO_EXCEPTIONS
      throw IncompatibleVisitorException();
#endif
    }
  }

};

template <class T,class ... Bases> class Visitable<T,Bases...>:public virtual Bases ...{
private:

  template <class Current> void try_to_accept(VisitorBase &visitor){
    Current::accept(visitor);
  }

  template <class Current,class Second,typename ... Rest> void try_to_accept(VisitorBase &visitor){
    if(auto casted = visitor.as_visitor_for<Current>()){
      casted->visit(static_cast<Current &>(*this));
      return;
    }
    try_to_accept<Second,Rest ...>(visitor);
  }

  template <class Current> void try_to_accept(ConstVisitorBase &visitor)const{
    Current::accept(visitor);
  }

  template <class Current,class Second,typename ... Rest> void try_to_accept(ConstVisitorBase &visitor)const{
    if(auto casted = visitor.as_visitor_for<Current>()){
      casted->visit(static_cast<const Current &>(*this));
      return;
    }
    try_to_accept<Second,Rest ...>(visitor);
  }

public:

  void accept(VisitorBase &visitor)override{
    try_to_accept<T, Bases...>(visitor);
  }

  void accept(ConstVisitorBase &visitor)const override{
    try_to_accept<T, Bases...>(visitor);
  }

};

A Benchmark shows approximately 77 times slower execution time using dynamic_cast and 25 times slower execution time using the dictionary compared to the standard approach.

Is this implementation safe and optimal? Can performance be further improved?

The full source code including the benchmark is available at cpp.sh/32bc.

\$\endgroup\$
  • \$\begingroup\$ I forgot to mention that the template arguments of the Visitable class are the derived class itself and virtual base classes (which are also derived from Visitable). When accepting a visitor it will search the Derived class, all virtual base classes and, if none are applicable, it will recursively call the accept method of the last template argument. \$\endgroup\$ – Lars Jul 17 '17 at 19:31
0
\$\begingroup\$

Using some template metaprogramming magic I managed to dramatically speed up the acyclic visitor implementation to be only about 2-3x slower than the standard visitor approach.

Instead of storing pointers to different visitors in an unordered set, the visitors now override a virtual function which receives a runtime generated type-index of the visitable class V (simply a static unsigned) and returns a Visitor<V> of that class if possible and nullptr otherwise.

void * Visitor<First,Rest...>::cast_to_visitor_for(unsigned requested_type_id){
  auto result = Visitor<First>::cast_to_visitor_for(requested_type_id);
  if(result) return result;
  return Visitor<Rest...>::cast_to_visitor_for(requested_type_id);
}

and the implementation of Visitor<First>::cast_to_visitor_for is

void * Visitor<V>::cast_to_visitor_for(unsigned requested_type_id){
  if(get_type_index<V>() == requested_type_id){ return reinterpret_cast<void*>(this); }
  return nullptr;
}

Another problem that arose was that the visitable class derived from more than one type needed to explicitly mention all visitable base classes found in the base types. This was avoided by having all visitable base types store a compile-time list of their derived visitable classes, sorted according to their depth in the virtual inheritance graph. When accepting a visitor the visitable class then simply iterates through all visitable base types and iteratively calls VisitorBase::cast_to_visitor_for(get_type_index<Visitable>()) for all Visitable base classes.

Only drawbacks are the increased compile time and the more verbose type name, where Visitable<D,B,C> is now indirectly referred to by DerivedVisitable<D,WithVisitableBaseClass<B,C>>::Type. The type-list creation and sorting logic is handled by the DerivedVisitable type and passed to the actual Visitor class as a template parameter.

Using the new visitor code I implemented visitor_cast, a drop-in alternative for dynamic_cast for visitable types which is about 4x faster for the class hierarchy in the example above.

The full code is now around 500 lines long can be found at my Github repository.

\$\endgroup\$

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.