Acyclic Visitor

в 16:02, , рубрики: c++, design patterns, just for fun, visitor pattern, Программирование

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

Acyclic Visitor - 1

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

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

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

Типичная реализация Cyclic Visitor
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
    }
};

Типичная реализация Acyclic Visitor с RTTI
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
    }
};

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

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

Pattern Time(ms)
Cyclic visitor 11.3
Acyclic visitor(RTTI) 220.4

Видно что посетитель 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);
}

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

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

Pattern Time(ms)
Cyclic visitor 11.3
Acyclic visitor(RTTI) 220.4
Acyclic visitor with map 23.2
Acyclic visitor with unordered_map 44.5
Acyclic visitor with sort vector 31.1


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

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

Автор: PkXwmpgN

Источник

Поделиться новостью

* - обязательные к заполнению поля