Pull to refresh

Мультиметоды в C++. Библиотечная реализация. Введение в MML

Reading time 23 min
Views 20K
Наверное, многие C++-программисты слышали про мультиметоды и знают о том, что по сей день нет для этого языка приемлемой реализации: ни языковой поддержки, ни внешних библиотек. Есть кодогенераторы, выкрутасы через виртуальные методы, частный случай двойной диспетчеризации aka паттерн Посетитель (Visitor). Но ведь хочется просто реализовать несколько функций и указать: этот набор функций — есть мультиметод и точка.

О мультиметодах и некоторых подходах к их библиотечной реализации давно писали Мейерс и Александреску. Почти 20 лет эти идеи обсуждаются в различной литературе по C++, но до сих пор так и не были развиты до законченного решения, которое можно было бы удобно использовать в реальных проектах…

Я решил попытать счастья, дерзнуть, предложить свое видение этой проблемы и способ ее решения. Получилась шаблонная библиотека на одних только заголовочниках.
Это реализация под стандарт C++03, на чистом C++: без каких-либо кодогенераторов и дополнений. Цель — библиотека с простым и понятным интерфейсом для реализации возможности перегружать функций по типу (и даже по значению) во время выполнения (это была программа минимум, в конечном итоге получилось еще много вкусностей).

Для тест-драйва необходимо скачать исходники, и сделать парочку #include.

Я выбрал вариант изложения от простого к сложному. Поэтому в этой статье я расскажу о наиболее простом способе использования библиотеки и пока не рассказываю о приемах реализации.

Что такое мультиметод?

У него есть несколько синонимов: множественная диспетчеризация, множественное переключение по типу, перегрузка функций во время выполнения. На эту тему есть много информации в интернете и литературе, поэтому, не буду кросспостить одно и то же, а предоставлю пару ссылок:
английская и русская Википедия.

Зачем мультиметоды в C++?

Этот вопрос также раскрывать не буду.
Сразу сообщу, что целью была попытка реализации мультиметодов, а не абстрактные рассуждения с обоснованием, нужны ли они в C++. Кому-то нужны, а кому-то нет. Если есть идиома, значит реализация имеет право на существование, нравится кому-то это или нет. Раз другие языки имеют такие реализации, со стороны языка или библиотеки, чем C++ хуже?
Кстати, C++, возможно, когда-нибудь будет поддерживать мультиметоды со стороны языка. Вот предложение Бьерна Страуструпа. Раньше все ожидали их появления в редакции С++0x, но до сих пор предложение должным образом не проработано.

От себя я могу добавить. Страуструп рекомендует по возможности отдавать предпочтение свободным функциям, вместо внутренних методов-членов, если такой функции достаточно публичного интерфейса класса. Но что делать, если функция должна обрабатывать полиморфный аргумент? Каждый раз приходится добавлять новый виртуальный метод, пронизывающий всю иерархию (или ее часть). Это особенность жесткой связи данных и методов. Мультиметоды позволяют избежать этой зависимости, позволяют расширять функционал не вмешиваясь в иерархию классов. То есть без использования внутренних виртуальных методов можно создать внешний виртуальный метод, причем не от одного, а от нескольких полиморфных аргументов. В общем, прикладная часть довольно широка.

Немного истории

Впервые о мультиметоде я узнал в 2009-м году в процессе изучения C++ и приемов проектирования из книги «Банды четырех» «Приемы объектно-ориентированного проектирования. Паттерны проектирования.» в разделе «Посетитель» (Visitor). На то время мне показалось странным, что нет вменяемой и простой с точки зрения пользования реализации мультиметода для C++. Я набросал прототип, и развивал его (несколько раз переписывая почти полностью) в свободное время в качестве хобби, по мере изучения и углубления в язык. Когда я дорос до чтения Александреску, узнал, что он реализовал мультиметод несколькими способами. Но они оказались сильно ограничены, сложны в использовании, а в некоторых случаях вообще не работают, это всего лишь пример метапрограммирования к его книге. Да и приставка «мульти» тут ни к чему: его реализация работает только для функций 2-х аргументов. Я нашел еще несколько видов реализаций, но для них нужен был либо кодогенератор, либо написание ручного кода и внесение в свою иерархию существенных изменений для поддержки диспетчеризации. Все это так сложно, что нет желания использовать мультиметоды в C++. Мне удалось найти способ избавиться от этих сложностей, представив интерфейс в очень простом виде и приемлемую по производительности реализацию. Забегая вперед, один из самых простых способов создать мультиметод (а способов библиотека предоставляет много, от простых до тонкой ручной настройки готовыми или собственными политиками поведения алгоритма):

mml::make_multimethod(f1, f2,..., fn)

f1, f2,..., fn — имена функций или callable-объектов, которые нужно динамически перегрузить (то есть собрать из них мультиметод). Никаких дополнительных требований к аргументам нет, make_multimethod возвращает функциональный объект, представляющий мультиметод (динамически перегруженную функцию), настроенный параметрами по-умолчанию. Это низкий порог вхождения пользователя библиотеки, не требует дополнительных знаний.
В итоге, сформировалась библиотечка, наверное, даже приличная, назвал я ее банально: MML — MultiMethod Library. Пора ей увидеть свет, скорее всего, она станет кому-то полезной. Учитывая, что за эти почти 3 года ситуация с мультиметодами в C++ никуда не сдвинулась (ИМХО, может я просто чего-то не знаю).

Постановка задачи

Что должен делать мультиметод — понятно. Но как он должен это делать, и, что немаловажно, как это будет выглядеть? Буду отталкиваться от основного назначения — перегрузка во время выполнения. А что такое перегрузка в объектно ориентированном стиле? Вообще, как выглядит перегрузка функций во время компиляции в C++? Давайте проанализируем.
Не вдаваясь во все тонкости правил перегрузки (включая наследование, using-объявления, поиск Кёнига и пр.), рассмотрим простой пример:

void f(int){}
void f(double){}
void f(char, void*){}

Из него видно, что имя функции f перегружено 3 раза по типам аргументов и их количеству. Несмотря на то, что перегрузка функций появилась в C++ как преимущество ООП (в C перегрузки нет), ее форма и не пахнет объектной ориентированностью. Связаны эти 3 функции неявно: по совпадении имен, мало того термин «перегруженная функция» как нечто целое неприменим к этому примеру. Попробуйте, например, целиком сохранить этот набор в переменную или передать его в некоторую функцию и где-то впоследствии выполнить вызов с перегрузкой:

auto of = f; // ошибка неоднозначности взятия адреса функции f

Язык не имеет средств объединения набора перегруженных функций в цельный объект. Такая форма перегрузки отказывается инкапсулироваться.
Рассмотрим объектно-ориентированную альтернативу:

struct f
{
    void operator()(int) const {}
    void operator()(double) const {}
    void operator()(char, void*) const {}
};

auto of = f(); // прекрасно работает, of можно сохранять, передавать в качестве аргумента другой функции

Можно подумать, что все функции теперь лучше оформлять в виде функтора (функционального объекта). В этом есть здравый смысл, если это обосновано, например, для получения преимуществ встраивания (inlining) при передаче предикатов в стандартные алгоритмы и пр., но не для всех задач. Необоснованное написание функтора вместо обычной старой доброй функции окажется неудобным, затратным по времени, а также для некоторых задач неприемлемым решением.

Итак, в объектно-ориентированном стиле перегруженная функция — это функтор (он же функциональный объект) с перегруженным operator(). В библиотеке MML есть готовый полезный шаблон, который оборачивает множество отдельных callable-сущностей (это функторы, лямбды и указатели на обычные функции) и представляет для каждой из них перегруженный operator(). Это объект overloaded_function<F1,… Fn> и функция make_overloaded_function(f1, ..., fn), которая создает объект, выводя параметры его шаблона через типы своих аргументов.

overloaded_function — это сущность, представляющая собой перегруженную функцию во время компиляции, которую можно вызывать используя operator(). Из тех же соображений нужно исходить при проектировании интерфейса мультиметода. Т.е. он должен являться некоторой callable-сущностью, выглядеть внешне также как перегруженный функтор, но выполнять перегрузку во время выполнения в зависимости от реального динамического типа параметров, который во время компиляции неизвестен. Мультиметод должен представлять собой объект-значение, содержать все необходимые данные внутри себя, т.е. поддерживать концепцию Assignable. Такой интерфейс и поведение позволит мультиметоду выглядеть как обычная вызываемая сущность и взаимодействовать с STL, boost, а также с многими STL like-библиотеками и пользовательским кодом без специального адаптирования.

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

Предлагаемое решение

Удалось получить набор классов, стратегий, классов характеристик, фасадов, адаптеров и пр. утилит для наиболее общего решения задачи помимо самого мультиметода. Но, т.к. статья вводная, я пока расскажу о самом простом варианте использования мультиметода, так называемый низкий порог. Для этого я подготовил фасад multimethod и функцию для его создания на базе набора целевых callable-сущностей make_multimethod. Ядром библиотеки является шаблонный класс dispatcher, о котором я расскажу в следующих статьях по мере углубления, он максимально обобщен и не ограничивается лишь реализацией мультиметода, multimethod — это фасад для упрощения использования диспетчера.

Пожалуй, достаточно рассуждений, лучше воспользоваться примерами с комментариями, чтобы понять, как все на самом деле просто.

Для примера нам необходима простая иерархия. Воспользуюсь классическим примером: игра, в которой будем сталкивать космические корабли, астероиды и космические станции:

Иерархия
struct game_object
{
    virtual ~game_object()
    {
    }
};


struct space_ship
    : game_object
{
};

struct space_station
    : game_object
{
};

struct asteroid
    : game_object
{
};

Для удобства, функция, которая возвращает массив полиморфных указателей на игровые объекты:

get_obj_pointers()
vector<game_object*>& get_obj_pointers()
{
    static space_ship ship;
    static asteroid ast;
    static space_station station;

    static vector<game_object*> objs;

    if (objs.empty())
    {
        objs.push_back(&ship);
        objs.push_back(&ast);
        objs.push_back(&station);
    }

    return objs;
}

Набор целевых статически перегруженных функций:

const char* collide_go_go(game_object*, game_object*)
{
    return "Unsupported colliding!";
}

const char* collide_sh_sh(space_ship*, space_ship*)
{
    return "Space ship collides with space ship";
}

const char* collide_sh_as(space_ship*, asteroid*)
{
    return "Space ship collides with asteroid";
}

const char* collide_as_sh(asteroid*, space_ship*)
{
    return "Asteroid collides with space ship";
}

const char* collide_as_as(asteroid*, asteroid*)
{
    return "Asteroid collides with asteroid";
}

Какие же они перегруженные, спросите вы, у них разные имена. Да, разные, для удобства взятия адреса. Если кому-то сильно нужно, можно дать одинаковые имена, только придется разрешить неоднозначность, когда будете брать адрес функций.

Первый важный момент. Создаем мультиметод (нужно подключить заголовочник <mml/generation/make_multimethod.hpp>):

#include <mml/generation/make_multimethod.hpp>

auto collide = make_multimethod(
      collide_go_go
    , collide_sh_sh
    , collide_sh_as
    , collide_as_sh
    , collide_as_as
    );

Готово! collide — есть мультиметод. Можно обойтись без auto, сразу передать результат в шаблонную функцию, присвоить boost::function<const char*(game_object*, game_object*)> collide =… или явно указать тип multimethod<...>. Явно указывать тип довольно сложно, лучше всего пользоваться автоматическим выведением. Инкапсулируя в (boost|std|std::tr1)::function, вы потеряете часть функциональности и производительности в некоторых конкретный случаях (ниже будет поясняющий пример), но, в целом, в большинстве случаев поведение будет тем же.

Второй важный момент. Используем мультиметод. Сталкиваем попарно все игровые объекты:

auto& objs =  get_obj_pointers();
for (size_t i = 0; i < objs.size(); ++i)
    for (size_t j = 0; j < objs.size(); ++j)
        cout << '\t' << collide(objs[i], objs[j]) << endl;

Вывод
        Space ship collides with space ship
        Space ship collides with asteroid
        Asteroid collides with space ship
        Asteroid collides with asteroid

Вывод в консоль показывает, кто на самом деле с кем столкнулся. Как видите, от иерархии не требуется какая-то особая поддержка диспетчеризации. В multimethod по-умолчанию используется dynamic_cast для выяснения реального динамического типа объекта. Следовательно, компилировать код нужно с включенной поддержкой RTTI.
Для оценки эффективности я привожу псевдокод, который при компиляции даст тот же машинный код, что и вызов collide(objs[i], objs[j]):

Псевдокод
inline const char* collide(game_object* obj1, game_object* obj2)
{
    if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_sh_sh(sh1, sh2);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_sh_as(sh1, as2);
        else
            return collide_go_go(sh1, obj2);
    else if (asteroid* as1 = dynamic_cast<asteroid*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_as_sh(as1, sh2);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_as_as(as1, as2);
        else
            return collide_go_go(as1, obj2);
    else
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_go_go(obj1, sh2);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_go_go(obj1, as2);
        else
            return collide_go_go(obj1, obj2);
}

Как видно, накладные расходы во время выполнения представлены в лучшем случае 2-мя dynamic_cast, в худшем — 4-мя.

Библиотека работает с указателями на полиморфные объекты: как со встроенными, так и с умными и даже определенными пользователем. Для работы со ссылками я написал фасад ref_multimethod (реализован в <mml/generation/make_ref_multimethod.hpp>):

Утилитная функция для удобства создания массива ссылок на полиморфные объекты:

get_objs_refs()
boost::ptr_vector<game_object>& get_objs_refs()
{
    static boost::ptr_vector<game_object> objs;

    if (objs.empty())
    {
        objs.push_back(new space_ship);
        objs.push_back(new asteroid);
        objs.push_back(new space_station);
    }

    return objs;
}

Целевые функции, принимающие ссылки:

Тот же набор, как с указателями, только принимают ссылки
const char* collide_ref_go_go(game_object&, game_object&)
{
    return "Unsupported colliding!";
}

const char* collide_ref_sh_sh(space_ship&, space_ship&)
{
    return "Space ship collides with space ship";
}

const char* collide_ref_sh_as(space_ship&, asteroid&)
{
    return "Space ship collides with asteroid";
}

const char* collide_ref_as_sh(asteroid&, space_ship&)
{
    return "Asteroid collides with space ship";
}

const char* collide_ref_as_as(asteroid&, asteroid&)
{
    return "Asteroid collides with asteroid";
}

Чтобы не повторять один и тот же цикл сталкивания объектов, я обернул его в шаблонную функцию:

template <typename F, typename Objs>
void collide_tester(F collide, Objs& objs)
{
    for (size_t i = 0; i < 2; ++i)
        for (size_t j = 0; j < 2; ++j)
            cout << '\t' << collide(objs[i], objs[j]) << endl;
}

Создаем и используем ссылочный мультиметод:

#include <mml/generation/make_ref_multimethod.hpp>

collide_tester(
      make_ref_multimethod(
          collide_ref_go_go
        , collide_ref_sh_sh
        , collide_ref_sh_as
        , collide_ref_as_sh
        , collide_ref_as_as
        )
    , get_objs_refs()
    );

Вывод
        Space ship collides with space ship
        Space ship collides with asteroid
        Asteroid collides with space ship
        Asteroid collides with asteroid

Рантайм эквивалент в псевдокоде будет такой же, как в предыдущем примере с указателями.

Я уже говорил, что функциональные объекты выгодно отличаются от указателей на встроенную функцию тем, что легко поддаются встраиванию. Мало того, большинство таких объектов не имеет членов-данных, поэтому позволяют вообще не хранить их в памяти контейнера при помощи хитрой техники «Empty Base Optimization», которая применена в недрах библиотеки. Вот пример взаимодействия мультиметода с функтором:

struct collider_sh_as
{
    const char* operator()(space_ship*, asteroid*) const
    {
        return "Space ship collides with asteroid";
    }
};

collide_tester(
    make_multimethod(
          collide_go_go
        , collide_sh_sh
        , collider_sh_as()
        , collide_as_sh
        , collide_as_as
        )
    , get_obj_pointers()
    );

Как видно, использовать функторы также просто, как и встроенные функции. Но при этом, размер мультиметода будет на ширину одного указателя меньше, и любой компилятор сможет без труда встроить тело collider_sh_as::operator() в место вызова.

Типы параметров и возвращаемое значение call-оператора библиотека определяет через BOOST_TYPEOF(&collider_sh_as::operator()). Не стоит расстраиваться, если ваш компилятор не поддерживает BOOST_TYPEOF, или вы не хотите регистрировать пользовательские типы для поддержки BOOST_TYPEOF, или вообще не хотите знать, что это. Можно явно указать типы параметров, для этого есть несколько удобных способов. Библиотека реализует следующий протокол определения типов параметров и возвращаемого значения функтора (F):
  1. Пытается получить функциональный тип из типа функтора через F::signature. Необходимо определить его следующим образом:

    struct collider_sh_as
    {
        typedef const char* signature(space_ship*, asteroid*);
    ...
    }
    

  2. Если предыдущий typedef отсутствует, пытается найти типы внутри функтора через F::result_type, F::arg1_type, F::arg2_type, ..., F::argn_type:

    struct collider_sh_as
    {
        typedef const char* result_type;
        typedef space_ship* arg1_type;
        typedef asteroid* arg2_type;
    ...
    }
    

    Таким образом, автоматически поддерживается boost::function, которая экспортирует такие typedef.

  3. Если они отсутствуют, пытается найти типы через F::result_type, F::argument_type (для унарной функции), F::first_argument_type, F::second_argument_type (для бинарной функции).

    struct collider_sh_as
    {
        typedef const char* result_type;
        typedef space_ship* first_argument_type;
        typedef asteroid* second_argument_type;
    ...
    }
    

    или, что гораздо удобнее:

    struct collider_sh_as
        : std::binary_function<space_ship*,  asteroid*,  result_type>
    {
    ...
    }
    

    Таким образом, автоматически поддерживается std::unary_function, std::binary_function.

  4. Если предыдущие 3 шага не дали результата, то используется BOOST_TYPEOF. Поддерживаются любые функторы с одним нешаблонным operator(). Таким образом, поддерживается std::function и лямбды C++11. На некоторых компиляторах придется регистрировать пользовательские типы. Я до сих пор не понял, как работает BOOST_TYPEOF, я не регистрировал пользовательские типы, а он прекрасно выводит типы параметров на MSVC 7.1 и выше.

В предыдущих примерах мультиметод собирался из функций одинаковой арности. Это не есть ограничение библиотеки.
Вообще, библиотека поддерживает арность от 0 до MML_MAX_ARITY. MML_MAX_ARITY по умолчанию равна 5. Значение по-умолчанию можно изменить. Для этого перед подключением заголовочников нужно определить макрос:

#define MML_MAX_ARITY n
n — максимальная арность.

Добавим для примера нульарные, унарные и тернарные функции:

// ничего не сталкивается, глупость, но для примера сойдет
const char* collide_void() 
{
    return "Nothing collides?!";
}

// объект сталкивается ни с чем, тоже глупость
const char* collide_go(game_object*)
{
    return "Unsupported colliding!";
}

const char* collide_sh(space_ship*)
{
    return "Space ship collides with what?!";
}

const char* collide_as(asteroid*)
{
    return "Asteroid collides with what?!";
}

const char* collide_go_go_go(game_object*, game_object*, game_object*)
{
    return "Unsupported colliding!";
}

const char* collide_sh_as_as(space_ship*, asteroid*, asteroid*)
{
    return "Space ship collides with two asteroids";
}

const char* collide_sh_as_st(space_ship*, asteroid*, space_station*)
{
    return "Space ship collides with asteroid and space_station";
}

Нужен новый тестер, который будет сталкивать разное количество объектов:

template <typename F, typename Objs>
void collide_tester_var_arg(F collide, Objs& objs)
{
    // без аргументов
    cout << '\t' << collide() << endl;

    // 1 аргумент
    cout << '\t' << collide(objs[0]) << endl;
    cout << '\t' << collide(objs[1]) << endl;

    // 2 аргумента
    cout << '\t' << collide(objs[0], objs[0]) << endl;
    cout << '\t' << collide(objs[0], objs[1]) << endl;

    // 3 аргумента
    cout << '\t' << collide(objs[0], objs[1], objs[1]) << endl;
    cout << '\t' << collide(objs[0], objs[1], objs[2]) << endl;

}

Создаем и используем мультиметод:

collide_tester_var_arg(
      make_multimethod(
          collide_go_go
        , collide_sh_sh
        , collide_sh_as
        , collide_void
        , collide_go
        , collide_sh
        , collide_as
        , collide_go_go_go
        , collide_sh_as_as
        , collide_sh_as_st
        )
    , get_obj_pointers()
    );

Вывод
        Nothing collides
        Space ship collides with what?!
        Asteroid collides with what?!
        Space ship collides with space ship
        Space ship collides with asteroid
        Space ship collides with two asteroids
        Space ship collides with asteroid and space_station

Таким образом, мультиметод ведет себя подобно статически перегруженной функции по количеству аргументов.
Рантайм эквивалент в псевдокоде здесь будет поинтереснее, он сильно зависит от количества аргументов:

Псевдокод
// collide()
inline const char* collide()
{
    return collide_void();
}
// никаких накладных расходов в рантайм!


// collide(objs[0])
// collide(objs[1])
inline const char* collide(game_object* obj)
{
    if (space_ship* sh = dynamic_cast<space_ship*>(obj))
        return collide_sh(sh);
    else if (asteroid* as = dynamic_cast<asteroid*>(obj))
        return collide_as(as);
    else
        return collide_go(obj);
}
// накладные расходы в рантайм:
// min 1 cast
// max 2 casts

// collide(objs[0], objs[0])
// collide(objs[0], objs[1])
// такие же, как в примере выше в функции: inline const char* collide(game_object* obj1, game_object* obj2) {...}

// collide(objs[0], objs[1], objs[1])
// collide(objs[0], objs[1], objs[2])
inline const char* collide(game_object* obj1, game_object* obj2, game_object* obj3)
{
    if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(sh1, sh2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(sh1, sh2, st3);
            else
                return collide_go_go_go(sh1, sh2, obj3);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_sh_as_as(sh1, as2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_sh_as_st(sh1, as2, st3);
            else
                return collide_go_go_go(sh1, as2, obj3);
        else
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(sh1, obj2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(sh1, obj2, st3);
            else
                return collide_go_go_go(sh1, obj2, obj3);
    else if (asteroid* as1 = dynamic_cast<asteroid*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(as1, sh2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(as1, sh2, st3);
            else
                return collide_go_go_go(as1, sh2, obj3);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(as1, as2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(as1, as2, st3);
            else
                return collide_go_go_go(as1, as2, obj3);
        else
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(as1, obj2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(as1, obj2, st3);
            else
                return collide_go_go_go(as1, obj2, obj3);
    else
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(obj1, sh2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(obj1, sh2, st3);
            else
                return collide_go_go_go(obj1, sh2, obj3);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(obj1, as2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(obj1, as2, st3);
            else
                return collide_go_go_go(obj1, as2, obj3);
        else
            if (asteroid* as3 = dynamic_cast<asteroid*>(obj3))
                return collide_go_go_go(obj1, obj2, as3);
            else if (space_station* st3 = dynamic_cast<space_station*>(obj3))
                return collide_go_go_go(obj1, obj2, st3);
            else
                return collide_go_go_go(obj1, obj2, obj3);
}
// накладные расходы в рантайм:
// min 3 casts
// max 6 casts

Можно смешивать полиморфные типы и типы-значения. Типы-значения будут просто передаваться как есть.
Введем пару дополнительных целевых функций, которые могут принимать 3-й параметр типа int:

const char* collide_go_go_int(game_object*, game_object*, int)
{
    return "Unsupported colliding with extra int parameter!";
}

const char* collide_sh_as_int(space_ship*, asteroid*, int)
{
    return "Space ship collides with asteroid with extra int parameter";
}

Тестер для наглядности будет передавать в мультиметод:
2 полиморфных типа;
3 полиморфных типа;
2 полиморфных с одним неполиморфным типом:

template <typename F, typename Objs>
void collide_tester_non_polymorphic_arg(F collide, Objs& objs)
{
    cout << '\t' << collide(objs[0], objs[1]) << endl;
    cout << '\t' << collide(objs[0], objs[1], objs[2]) << endl;
    cout << '\t' << collide(objs[0], objs[1], 1) << endl;
}

Создаем мультиметод на базе предыдущих и новых целевых функций и используем:

collide_tester_non_polymorphic_arg(
        make_multimethod(
          collide_go_go
        , collide_sh_sh
        , collide_sh_as
        , collide_as_sh
        , collide_as_as
        , collide_go_go_go
        , collide_sh_as_st
        , collide_sh_as_as
        , collide_go_go_int
        , collide_sh_as_int
        )
    , get_obj_pointers()
    );

Вывод
        Space ship collides with asteroid
        Space ship collides with asteroid and space_station
        Space ship collides with asteroid with extra int parameter

Рантайм-эквивалент для первого и второго вызовов я приводил, рассмотрим третий:

Псевдокод
// collide(objs[0], objs[1], 1)
inline const char* collide(game_object* obj1, game_object* obj2, int n)
{
    if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_go_go_int(sh1, sh2, n);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_sh_as_int(sh1, as2, n);
        else
            return collide_go_go_int(sh1, obj2, n);
    else if (asteroid* as1 = dynamic_cast<asteroid*>(obj1))
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_go_go_int(as1, sh2, n);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_go_go_int(as1, as2, n);
        else
            return collide_go_go_int(as1, obj2, n);
    else
        if (space_ship* sh2 = dynamic_cast<space_ship*>(obj2))
            return collide_go_go_int(obj1, sh2, n);
        else if (asteroid* as2 = dynamic_cast<asteroid*>(obj2))
            return collide_go_go_int(obj1, as2, n);
        else
            return collide_go_go_int(obj1, obj2, n);
}
// накладные расходы в рантайм:
// min 2 casts
// max 4 casts

Как видно неполиморфные аргументы не приводят к дополнительным накладным расходам.

Также поддерживается перегрузка по квалификаторам const и volatile:

const char* collide_go_cvgo(game_object*, const volatile game_object*)
{
    return "Unsupported colliding!";
}

const char* collide_sh_cas(space_ship*, const asteroid*)
{
    return "Space ship collides with const asteroid";
}

const char* collide_sh_vas(space_ship*, volatile asteroid*)
{
    return "Space ship collides with volatile asteroid";
}

const char* collide_sh_cvas(space_ship*, const volatile asteroid*)
{
    return "Space ship collides with const volatile asteroid";
}

template <typename F, typename Objs>
void collide_tester_cv(F collide, Objs& objs)
{
    game_object* object = objs[1];
    const game_object* c_object = objs[1];
    const volatile game_object* cv_object = objs[1];

    cout << '\t' << collide(objs[0], object) << endl;
    cout << '\t' << collide(objs[0], c_object) << endl;
    cout << '\t' << collide(objs[0], cv_object) << endl;
}

collide_tester_cv(
        make_multimethod(
          collide_sh_as
        , collide_go_cvgo
        , collide_sh_cas
        , collide_sh_vas
        , collide_sh_cvas
        )
    , get_obj_pointers()
    );
}

Вывод
        Space ship collides with asteroid
        Space ship collides with const asteroid
        Space ship collides with const volatile asteroid

Важной особенностью мультиметода является способность оптимизировать диспетчеризацию, если точный тип полиморфного аргумента известен уже на этапе компиляции. Другими словами, поиск реального типа аргумента начинается с того узла иерархии, которым является фактический тип передаваемого аргумента. Как бы проще объяснить… Вот лучше рассмотрим пример:

template <typename F, typename Objs>
void collide_tester_compile_time_optim(F collide, Objs& objs)
{
    space_ship ship;
    asteroid ast;

    cout << '\t' << collide(objs[0], &ast) << endl;
    cout << '\t' << collide(&ship, &ast) << endl;
}

collide_tester_compile_time_optim(
        make_multimethod(
          collide_go_go
        , collide_sh_sh
        , collide_sh_as
        , collide_as_sh
        , collide_as_as
        )
    , get_obj_pointers()
    );

Вывод
        Space ship collides with asteroid
        Space ship collides with asteroid

Теперь внимательно рассмотрим рантайм-эквивалент:

// collide(objs[0], &ast)
inline const char* collide(game_object* obj1, asteroid* as2)
{
    if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
        return collide_sh_as(sh1, as2);
    else if (asteroid* as1 = dynamic_cast<asteroid*>(obj1))
        return collide_as_as(as1, as2);
    else
        return collide_go_go(obj1, as2);
}
// накладные расходы в рантайм:
// min 1 cast
// max 2 casts

// collide(&ship, &ast)
inline const char* collide(space_ship* sh1, asteroid* as2)
{
    return collide_sh_as(sh1, as2);
}
// никаких накладных расходов!

Первый вызов диспетчеризуется только по первому аргументу, второй аргумент передается как есть, т.к. его тип и так точно известен еще во время компиляции.
Второй вызов вообще просто форвардится, типы обоих аргументов известны во время компиляции.
Вот почему для поддержки такой оптимизации мультиметод, по возможности, необходимо хранить и передавать в чистом виде, а не прятать за boost::function /*std::function*/. Вызов с апкастингом — collide((game_object*)&ship, (game_object*)&ast) — лишит библиотеку возможности оптимизации.

Мультиметод поддерживает не только голые указатели, но и boost::shared_ptr, а также пользовательские типы указателей при правильной специализации пары шаблонов (о них в следующих статьях). Для поддержки boost::shared_ptr нужно подключить заголовочный файл <mml/casting/sp_dynamic_caster.hpp>.
Пример:

#include <mml/casting/sp_dynamic_caster.hpp>

const char* sp_collide_go_go(game_object*, boost::shared_ptr<game_object>)
{
    return "Unsupported colliding!";
}

const char* sp_collide_sh_sh(space_ship*, boost::shared_ptr<space_ship>)
{
    return "Space ship collides with smart_ptr space ship";
}

struct sp_collider_sh_as
{
    const char* operator()(space_ship*, boost::shared_ptr<asteroid>) const
    {
        return "Space ship collides with smart_ptr asteroid";
    }
};

template <typename F, typename Objs>
void sp_collide_tester(F collide, Objs& objs)
{
    boost::shared_ptr<game_object> obj1(new space_ship);
    boost::shared_ptr<game_object> obj2(new asteroid);

    cout << '\t' << collide(objs[0], obj1) << endl;
    cout << '\t' << collide(objs[0], obj2) << endl;
}

sp_collide_tester(
        make_multimethod(
          sp_collide_go_go
        , sp_collide_sh_sh
        , sp_collider_sh_as()
        )
    , get_obj_pointers()
    );

Вывод
        Space ship collides with smart_ptr space ship
        Space ship collides with smart_ptr asteroid

Рантайм эквивалент:

Псевдокод
// collide(objs[0], obj1)
// collide(objs[0], obj2)
inline const char* collide(game_object* obj1, const boost::shared_ptr<game_object>& sp_obj2)
{
    if (space_ship* sh1 = dynamic_cast<space_ship*>(obj1))
        if (boost::shared_ptr<space_ship> sp_sh2 = boost::shared_dynamic_cast<space_ship>(sp_obj2))
            return sp_collide_sh_sh(sh1, sp_sh2);
        else if (boost::shared_ptr<asteroid> sp_as2 = boost::shared_dynamic_cast<asteroid>(sp_obj2))
            return sp_collider_sh_as()(sh1, sp_as2);
        else
            return sp_collide_go_go(obj1, sp_obj2);
    else
        if (boost::shared_ptr<space_ship> sp_sh2 = boost::shared_dynamic_cast<space_ship>(sp_obj2))
            return sp_collide_go_go(obj1, sp_sh2);
        else if (boost::shared_ptr<asteroid> sp_as2 = boost::shared_dynamic_cast<asteroid>(sp_obj2))
            return sp_collide_go_go(obj1, sp_as2);
        else
            return sp_collide_go_go(obj1, sp_obj2);
}
// накладные расходы в рантайм:
// min 2 casts
// max 3 casts

Исходники примеров лежат здесь.

Преимущества

Простота использования. Каноничность выражения. Не нужно ничего инициализировать, описывать свою иерархию класов, не нужно вмешиваться в иерархию. Для обычного использования не требуется метаинформация. Всю необходимую метаинформацию мультиметод получит из вашего кода самостоятельно. С первого взгляда может показаться невероятным, но это так.
Нет ограничений на количество аргументов (может быть даже 0).
Основная часть кода — compile time, поэтому бОльшая часть ошибок неправильного использования мультиметода обнаружится компилятором.

Недостатки

Высокая нагрузка на компилятор может проявиться в случае инстанцирования множества мультиметодов разного типа (как в примере для статьи). Именно разного, т.к. компилятор инстанцирует каждый шаблон с определенным набором параметров только один раз. Количество однотипных объектов-мультиметодов при этом не важно. Полагаю, в реальном проекте такое разнообразие встретится редко. Кстати, при использовании механизма прекомпилированных заголовочников время компиляции примера падает почти вдвое.
При неправильном использовании, невнятные сообщения компилятора об ошибках с простынями шаблонного кода.

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

Производительность — это слабое место в приведенных примерах по причине использования dynamic_cast. Но dynamic_cast не является частью ядра библиотеки. Это способ, заданный стратегией по-умолчанию для выделения реального типа объекта. В следующей статье я покажу, как задать собственную стратегию приведения типа на примере «fast_cast», которая рвет по эффективности dynamic_cast на порядки. С другой стороны, даже такая эффективность будет приемлема для большинства прикладных задач. Вы ведь не собираетесь реализовывать обработку потокового видео, вызывая мультиметод для каждого байта?
Для прикладных или GUI задач такой вариант очень даже приемлем. После встраивания (inlining) для релизной сборки других накладных расходов в рантайм нет.
Пришлось помучиться с оптимизацией шаблонного кода так, чтобы минимизировать побочные эффекты на рантайм. Кстати по производительности мультиметод сравним с реализацией паттерна Acyclyc Visitor, предложенного Робертом Мартином. Он также реализован посредством dynamic_cast.
Мультиметод не использует кучу, состояние хранит внутри, если оно есть. В идеальном варианте (при использовании функторов, а не указателей на функции) состояние вообще не хранится — объект пустой и все вызовы легко встраиваются.

Зависимости

Для работы требуется компилятор C++ с поддержкой стандарта 03 или выше и BOOST (headers only) версии 1.45.0 или выше.

Важно! Обязательно наличие директории «boost» и «mml» внутри include-директории компилятора. Не сами каталоги «boost» и «mml» указать как include directories, а каталог, их содержащий.

Библиотека с примерами протестирована на компиляторах (пока что только под Windows):
GCC 3.4.2;
Visual C++ 7.1, 8.0, 9.0, 10.0.

UPD: О реализации я пока не написал ни слова, хотя есть, чем интересным поделиться. Статья вводная, а уже и так раздута. Поясню, что подавляющая часть кода библиотеки является кодом времени компиляции (в библиотеке на сегодня 57 заголовочных файлов объемом ~190 КБ). Повсеместно применяются приемы интроспекции и шаблонного метапрограммирования, то есть программирования компилятора на генерацию рантайм кода. Копмилятор, опираясь на типы, как бы строит бинарное дерево if-else, которое сильно зависит от входных типов.

UPD 2: Я забыл указать важную особенность: перегрузка не эмулируется, а выполняется по правилам языка C++ самим компилятором. После того как диспетчер приведет каждый аргумент к реальному типу, он передаст вызов в соответствующую перегруженную целевую функцию. Поэтому ошибки, связанные непосредственно с перегрузкой будут обнаружены компилятором. Спасибо mejedi за внимательность.

Виктор Щерба. Россия, Дубна.
Tags:
Hubs:
+42
Comments 19
Comments Comments 19

Articles