Acyclic Visitor

В этой статье мы рассмотрим один из вариантов реализации поведенческого шаблона проектирования Acyclic Visitor без ипользования RTTI.

Основным назначением поведенческого шаблона проектирования Visitor является введение абстрактной функциональности для иерархической структуры объектов.

Реализации шаблона можно условно разделить на две категории.

• Cyclic Visitor. Основан на механизме перегрузки функций (Function overloading). Из-за циклической зависимости (посещаемой иерархии необходимо уточнение типа посетителя, посетителю необходимо уточнение всех классов в иерархии), область применения ограничевается только устойчивыми иерархиями (в которые редко добавляются новые классы).
• Acyclic Visitor. Основан на механизме динамической идентификации типа данных (RTTI). Нет ограничений на посещаемые иерархии, но за счет использования динамической идентификации снижается производительность.

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
    }
};

Производительность

Выполнение простой операции на массиве из трех миллионов элементов

Видно что посетитель c динамической идентификацией сильно уступает в производительности обычному шаблону. Нашей основной задачей будет сохранить ацикличность шаблона, но приблизить его производительность к варианту без RTTI.

Реализация

Основная идея заключается в том, что для набора посещаемых классов из иерархии, посетитель генерирует специальную таблицу позднего связывания (vtbl), содержащую методы-преобразователи, вызывающие соответствующие методы у посетителя, основываясь на уникальном идентификаторе типа посещаемого класса.

Итак, у нас есть две подзадачи

• Получить уникальный идентификатор типа
• Сгенерировать таблицу позднего связывания

Уникальный идентификатор типа

Для решения этой задачи мы воспользуемся маленькой header-only библиотекой CTTI. В качестве уникального идентификатора будем использовать хеш, посчитанный на основе уникального строкового имени типа.

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 */

Исходя из того, что мы будем обрабатывать наши объекты полиморфно и точный тип объекта нам будет неизвестен, кажный класс в иерархии должен позаботиться о механизме получения своего уникального идентификатора. Мы добавим виртуальный метод возвращающий идентификатор.

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);
};

Генерация таблицы позднего связывания

В качестве контейнера для методов-преобразователей мы будем использовать стандартный ассоциативный контейнер map с уникальным идентификатором посещаемого типа в качестве ключа.

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 */

Далле нам нужно сгенерировать таблицу для списка классов, которые мы будем посещать

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;
};

Нам осталось определить методы-преобразователи и описать механизм обработки объекта

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);
}

Производительность

Производительность на том же тесте с разными стандартными контейнерами для таблицы позднего связывания

Код проекта можно найти на GitHub.

Буду рад комментариям и предложениям (можно по почте yegorov.alex@gmail.com)
Спасибо!

Автор: PkXwmpgN

Источник