Acyclic Visitor

In this article, we will look at one of the options for implementing the Acyclic Visitor behavioral design pattern without using RTTI.

The main purpose of Visitor's behavioral design pattern is the introduction of abstract functionality for the hierarchical structure of objects.

The implementation of the template can be divided into two categories.

• Cyclic Visitor . It is based on the function overloading mechanism. Due to the cyclical dependency (the visited hierarchy requires clarification of the type of visitor, the visitor needs to refine all classes in the hierarchy), the scope is limited only to stable hierarchies (to which new classes are rarely added).
• Acyclic Visitor . Based on a dynamic data type identification ( RTTI ) mechanism. There are no restrictions on visited hierarchies, but performance decreases due to the use of dynamic identification.

struct entity; struct geometry; struct model; struct visitor { virtual bool visit(entity &) = 0; virtual bool visit(geometry &) = 0; virtual bool visit(model &) = 0; }; struct entity { public: virtual ~entity() {} virtual void accept(visitor & obj) { obj.visit(*this); } }; struct geometry : entity { public: void accept(visitor & obj) { obj.visit(*this); } }; struct model : geometry { public: void accept(visitor & obj) { obj.visit(*this); } }; struct test_visitor : visitor { public: void visit(entity & obj) { // something } void visit(geometry & obj) { // something } void visit(model & obj) { // something } }; 

 template<typename _Visitable> struct visitor { virtual void visit(_Visitable &) = 0; }; struct visitor_base { virtual ~visitor_base(){} }; struct entity { public: virtual ~entity() {} virtual void accept(visitor_base & obj) { using entity_visitor = visitor<entity>; if(entity_visitor * ev = dynamic_cast<entity_visitor*>(&obj)) ev->visit(*this); } }; struct geometry : entity { public: virtual void accept(visitor_base & obj) { using geometry_visitor = visitor<geometry>; if(geometry_visitor * gv = dynamic_cast<geometry_visitor*>(&obj)) gv->visit(*this); } }; struct model : geometry { public: virtual void accept(visitor_base & obj) { using model_visitor = visitor<model>; if(model_visitor * mv = dynamic_cast<model_visitor*>(&obj)) mv->visit(*this); } }; struct test_visitor : visitor_base, visitor<entity>, visitor<geometry>, visitor<model> { public: void visit(entity & obj) { // something } void visit(geometry & obj) { // something } void visit(model & obj) { // something } }; 

Performance

Perform a simple operation on an array of three million items

It can be seen that the visitor with dynamic identification is much inferior in performance to the usual pattern. Our main task will be to preserve the acyclicity of the template, but to bring its performance closer to the version without RTTI.

Implementation

The basic idea is that for a set of visited classes from the hierarchy, the visitor generates a special late-binding table ( vtbl ) containing conversion methods that call the corresponding methods on the visitor, based on a unique identifier of the type of class being visited.

So, we have two subtasks

• Get a unique type identifier
• Generate late binding table

Unique type identifier

To solve this problem, we will use the small header-only CTTI library. As a unique identifier we will use a hash calculated on the basis of a unique string type name.

 namespace detail { using hash_type = std::uint64_t; template<typename _Base, typename _Specific> struct tag {}; template<typename _Base, typename _Specific> inline constexpr hash_type get_hash() { using tag_type = tag<typename std::remove_cv<_Base>::type, typename std::remove_cv<_Specific>::type>; return ctti::unnamed_type_id<tag_type>().hash(); } } /* detail */ 

Considering that we will process our objects polymorphically and the exact type of object will not be known to us, each class in the hierarchy should take care of the mechanism for obtaining its unique identifier. We will add a virtual method that returns an identifier.

 template <typename _Base> struct visitable { using base_type = _Base; }; //    //       #define VISITABLE(Specific) \ static constexpr detail::hash_type hash__ = detail::get_hash<base_type, Specific>(); \ virtual detail::hash_type get_hash() const \ {\ return hash__; \ } 

 struct entity : visitable<entity> { public: VISITABLE(entity); public: virtual ~entity() {} }; struct geometry : entity { public: VISITABLE(geometry); }; struct model : geometry { public: VISITABLE(model); }; 

Generating a late link table

As a container for the converter methods, we will use the standard associative container map with a unique identifier of the visited type as the key.

 namespace detail { template<typename _Visitor, typename _Base> struct vtbl_traits { //    . //        using base_type = _Base; //   using visitor_type = _Visitor; //    -  using function_type = void(visitor_type::*)(base_type &); }; template<typename _Traits> struct vtbl { using base_type = typename _Traits::base_type; using function_type = typename _Traits::function_type; using visitor_type = typename _Traits::visitor_type; //        template<typename _Specific> void put(function_type function) { vtbl_[get_hash<base_type, _Specific>()] = function; } //         function_type get(const hash_type & hash) const { auto it = vtbl_.find(hash); return it != vtbl_.end() ? it->second : nullptr; } private: std::map<hash_type, function_type> vtbl_; }; } /* detail */ 

Dale we need to generate a table for the list of classes that we will attend

 namespace detail { // _Traits   // _Specifics     template<typename _Traits, typename... _Specifics> struct vtbl_builder { //   using vtbl_type = vtbl<_Traits>; //   using visitor_type = typename _Traits::visitor_type; //    using base_type = typename _Traits::base_type; template<typename... _Targets> struct targets {}; vtbl_builder() { //    put_thunk(targets<_Specifics...>()); } const auto * get_vtbl() const { return &vtbl_; } private: template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>) { //        //      . //         using specific_type = constancy_t<base_type, _Specific>; using is_put = typename has_visit_method<visitor_type, specific_type>::type; put_thunk(targets<_Specific, _Tail...>(), is_put()); } //          //   thunk      template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>, std::true_type) { vtbl_.template put<_Specific>(&visitor_type::template thunk<base_type, _Specific>); put_thunk(targets<_Tail...>()); } //          //   ,     template<typename _Specific, typename... _Tail> void put_thunk(targets<_Specific, _Tail...>, std::false_type) { put_thunk(targets<_Tail...>()); } void put_thunk(targets<>) {} private: vtbl_type vtbl_; }; //         template<typename _Traits, typename... _Specifics> inline const auto * get_vtbl() { static vtbl_builder<_Traits, typename std::remove_cv<_Specifics>::type...> builder; return builder.get_vtbl(); } } /* detail */ 

 template<typename _From, typename _To> using constancy_t = typename std::conditional<std::is_const<_From>::value, const _To, _To>::type; 

 template<typename _Visitor, typename _Specific> struct has_visit_method { template<typename _Class, typename _Param> static auto test(_Param * p) -> decltype(std::declval<_Class>().visit(*p), std::true_type()); template<typename, typename> static std::false_type test(...); using type = decltype(test<_Visitor, _Specific>(nullptr)); static constexpr const bool value = std::is_same<std::true_type, type>::value; }; 

It remains for us to define the converter methods and describe the object's processing mechanism.

 template<typename _Base> struct visitor_traits { //      using base_type = _Base; }; //     template<typename _Visitor, typename _Traits> struct visitor { using visitor_type = _Visitor; using traits_type = _Traits; // -,       template<typename _Base, typename _Specific> void thunk(_Base & base) { using specific_type = detail::constancy_t<_Base, _Specific>; static_cast<visitor_type*>(this)->visit(static_cast<specific_type&>(base)); } //    template<typename _Base> void operator()(_Base & base) { // ,      //    . static_assert(std::is_base_of<typename traits_type::base_type, _Base>::value, ""); //   . //  _Base     //     using base_type = detail::constancy_t<_Base, typename traits_type::base_type>; using traits_type = detail::vtbl_traits<visitor_type, base_type>; //      . //   get_vtbl     const auto * vtbl = static_cast<visitor_type*>(this)->template get_vtbl<traits_type>(); //       , //      ,  if(auto thunk = vtbl->get(base.get_hash())) (static_cast<visitor_type*>(this)->*thunk)(base); } }; //          //    - #define VISIT(...) \ template<typename _Traits> \ const auto * get_vtbl() const \ { \ return detail::get_vtbl<_Traits, __VA_ARGS__>(); \ } 

 struct entity : visitable<entity> { public: VISITABLE(entity); public: virtual ~entity() {} }; struct geometry : entity { public: VISITABLE(geometry); }; struct model : geometry { public: VISITABLE(model); }; template<typename _Visitor> using visitor_entities = visitor<_Visitor, visitor_traits<entity>>; struct test_visitor : visitor_entities<test_visitor> { public: VISIT(entity, geometry, model); public: void visit(const entity & obj) { // something } void visit(const geometry & obj) { // something } void visit(const model & obj) { // something } }; int main() { const entity & ref_entity = entity(); const entity & ref_model = model(); const entity & ref_geometry = geometry(); test_visitor test; test(ref_entity); test(ref_model); test(ref_geometry); } 

Performance

Performance on the same dough with different standard containers for late binding table

The project code can be found on github .

I would be happy for comments and suggestions (you can mail yegorov.alex@gmail.com)
Thank!