Что и главное зачем мы собираемся делать?
Начнём с примера, допустим у нас есть интерфейс Animal, который поддерживают классы Cat, Dog, и Frog.
И мы хотим определить операцию interact(взаимодействие) между двумя Animal.
void interact(Cat, Dog) { std::cout << "fight" << std::endl; } void interact(Dog, Cat) { interact(Cat{}, Dog{}); } void interact(Cat, Frog) { std::cout << "Cat licks Frog" << std::endl; }
Но если мы попробуем это использовать, то возникнет громадная проблема:
void foo(Animal* a, Animal* b) { ??? }
когда-то в стандарт С++ предлагали языковую поддержку этого
Предложение в стандарт С++ от создателя языка - https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2007/n2216.pdf
Там же можно увидеть больше use cases
В стандартной библиотеке С++ нет возможности сделать это никак кроме вереницы 'if' с dynamic_cast, что просто ужасно и выглядит и работает, к тому же совершенно не масштабируемо, после добавления одной функции достаточно забыть изменить код в других местах и в коде логическая ошибка.
Вы можете сказать - С++17 же есть std::variant! Кажется он решает эту проблему!
И нет, он не решает эту проблему полностью.
использование std::variant предполагает, что вы типы храните в variant, что далеко не всегда так, у вас может быть иерархия на virtual функциях, своя собственная как llvm-type-id или использовано стирание типов
нужно знать определения всех типов в месте создания variant, что далеко не всегда возможно
если подать в visit больше одного варианта, то есть риск схлопнуть вселенную, т.к. сложность компиляции этой конструкции O(N*M*X*...) где N M X это количества типов в вариантах
Вот живой пример: https://godbolt.org/z/633eh11rc
Таким образом, мы хотим на основе динамических типов аргументов выбирать во время выполнения программы нужную функцию и вызывать её. То есть делать runtime overload resolution.
Это называется мультидиспетчеризацией - виртуальные функции из С++ это частный случай, одиночная диспетчеризация.
как это выглядит в Lisp
Теперь подумаем, как бы мы вообще могли такое сделать?
Мультиметод можно представить как таблицу, где ключ это набор типов аргументов, а значение - указатель на функцию.
Но что такое ключ из типов? Нужно как-то отобразить типы в значение, которое может быть ключом в map.
Тут есть несколько идей:
Вариант №1:
std::type_info - сразу нет. Причины:
эта вещь не гарантирует буквально ничего, .name() полученный из неё согласно стандарту С++ может изменяться от вызова к вызову (!)
нельзя использовать это в constexpr контексте, а мы бы хотели constexpr map<Types, Foo>
во многих проектах использование typeid запрещено
нет гарантий, что сравнений type_info будет правильно работать при подключении dll
Вариант №2:
template<typename T> constexpr void* type_desc == &type_desc<T>;
Подобное странное рекурсивное определение действительно работает и даёт уникальные указатели для каждого типа, известные на компиляции.
Но и тут есть проблемы:
операции сравнения < > на указателях на разные объекты во время компиляции unspecified, поэтому использовать её нельзя.
если мы подключили типы через .dll, то у них этот идентификатор будет другим и мы будем неверно искать функцию в таблице
Вариант №3:
Сравнение по именам, полученным из макроса __PRETTY_FUNCTION__ и его аналогов на других компиляторах.
это работает с dll
можно посмотреть имя типа прямо во время отладки
если это недоступно, то будем использовать вариант №2
Кстати, наиболее эффективно оказывается хранить имена как C-string, потому что для поиска в map нужна операция <, которая выполняется для таких строк даже быстрее, чем для string_view. Представим, что этот тип мы реализовали:
struct descriptor_t { constexpr descriptor_t(const char* name); constexpr auto operator<=>(const descriptor_t&); }; // уникальный дескриптор для каждого типа template<typename T> constexpr inline descriptor_t descriptor_v = ...;
Теперь нам остаётся всего ничего:
достать информацию из функций-перегрузок нашего мультиметода
сложить эту информацию в constexpr map<array<descriptor_t, CountArgs>, Foo>
потом при вызове генерировать ключ из нескольких descriptor_t, полученных из входных аргументов;
находить функцию в таблице и вызывать. Если такой функции нет, будем возвращать std::nullopt
дополнительное: можно проверять на компиляции и на рантайме const-correctness вызова, что задача нетривиальная, но необходимая
пишем constexpr flat map используя стандартные алгоритмы
template <typename Key, typename Value, std::size_t N, typename Compare = std::less<Key>> struct flat_map { private: std::array<Key, N> keys; std::array<Value, N> values; public: constexpr flat_map(std::array<std::pair<Key, Value>, N> arr) { // sort by keys std::ranges::sort(arr, [](auto& l, auto& r) { return l.first < r.first; }); std::ranges::copy(arr | keys, keys.begin()); std::ranges::copy(arr | value, values.begin()); } constexpr auto find(const Key& key) const noexcept { auto it = std::ranges::lower_bound(keys, key, Compare{}); // lower_bound returns such 'it' for which 'key' <= *it, so check if it true, that key < *it if (it == keys.end() || Compare{}(key, *it)) return values.end(); return std::next(values.begin(), std::distance(keys.begin(), it)); } constexpr auto end() const noexcept { return values.end(); } };
Ключом в этой map будет массив descriptor_t длиной в количество аргументов мультиметода.
Но как же получить информацию о функциях-перегрузках?
Для этого напишем специализации функций для разных сигнатур функций(задачу нам упрощает тот факт, что это могут быть только указатели на функции или лямбды без захвата):
достаём информацию из функций
template <typename> struct traits {}; template <typename R, typename... Args> struct traits<R (*)(Args...)> { static constexpr bool is_noexcept = false; using all_args = type_list<Args...>; using decay_args = type_list<std::decay_t<Args>...>; static constexpr std::size_t args_count = sizeof...(Args); };
Только не забудьте потом сделать специализации для const, noexcept, const noexcept, & , && callable объектов, volatile, указателей на функции и конечно же C-variadic функций(методов, callable объектов...)
Кстати, библиотека не поддерживает C-variadic функции, потому что это было бы безумием
Так, с ключами в map мы определились. Но что будет там значением? Ведь функции разные и типы у них соответственно разные. Мы бы хотели привести все функции к одной сигнатуре - они должны возвращать ResultType и принимать array<void*, N>, а потом кастовать этот массив к нужным типам и вызывать реальную функцию
стираем сигнатуру функции
// передаём тип функции и типы аргументов template <typename Foo, typename... Ts> result_type match_invoker(const std::array<void*, args_count>& args) { return std::apply( [](auto*... void_ptrs) { return Foo{}(static_cast<Ts&&>(*reinterpret_cast<Ts*>(void_ptrs))...); }, args); }
Тут опять же всё немного упрощённо
Теперь понятно - значением в таблице будет указатель на функцию match_invoker<F, Args...> для каждой из функций. Используя это напишем конструктор для мультиметода. А назовём это дело visit_invoke, т.к. в std:: уже есть и visit и invoke, а тут явно напрашиваются аналогии.
Отмечу, что мы считаем полиморфным тип такой, у которого динамический type descriptor может отличаться от descroptor_v известный для его типа на компиляции.
Поэтому заметим, что пользователь может захотеть использовать разные полиморфные ие��архии - виртуальные функции, свои type-id(такие как LLVM-type-id), стирание типов, даже std::variant он может интерпретировать как полиморфный тип. Поэтому добавим policy-тип PolyTraits, который будет говорить шаблону visit_invoke_fn:
как получить дескриптор типа для какого-то Value
как получить адрес объекта для какого-то Value
пример poly_traits для std::variant
struct std_variant_poly_traits { // для std::variant, тут мы считаем его полиморфным типом template <typename... Ts> static descriptor_t get_type_descriptor(const std::variant<Ts...>& v) { return std::visit([]<typename T>(T&& v) { return descriptor_v<T>; } , v); } // для остальных типов, которые мы считаем не полиморфными template <typename T> static descriptor_t get_type_descriptor(const T&) { return descriptor_v<T>; } // тоже самое для адресов(упрощённо) template <typename T> static const void* to_address(const T& v) { return std::addressof(v); } template <typename... Ts> static const void* to_address(const std::variant<Ts...>& v) { return std::visit([](const auto& v) -> const void* { return std::addressof(v); } , v); } };
Теперь используя все полученные знания пишем конструктор мультиметода
пишем конструктор для мультиметода
template <typename Result, poly_traits Traits, typename... Foos> struct visit_invoke_fn { private: template <typename F> static constexpr std::pair<key_type, value_type> make_key_value_pair_for() { return []<typename... Ts>(aa::type_list<Ts...>) { return std::pair{key_type{descriptor_v<Ts>...}, &match_invoker<F, Ts...>}; }(typename traits<F>::all_args{}); // INVOKED HERE } public: constexpr visit_invoke_fn(Traits t = Traits{}) : map({make_key_value_pair_for<Foos>()...}), poly_traits(std::move(t)) { }
Ну и наконец главный метод .resolve, выполняющий разрешение перегрузки на рантайме.
Обратите внимание, мы принимаем любые аргументы и с помощью Traits(policy-типа) определяем какой у type_descriptor, и с помощью них же получаем адрес реального объекта из полиморфного.
Это позволяет поддерживать любые возможные пользовательские полиморфные иерархии:
(в коде опущены все проверки для простоты) template <typename... Args> std::optional<result_type> resolve(Args&&... args) const { key_type key{poly_traits.get_type_descriptor(args)...}; auto it = map.find(key); if (it == map.end()) [[unlikely]] return std::nullopt; // заранее мы стёрли тип функции до состояния Ret(*)(array<void*, N>) return (*it)({poly_traits.to_address(args)...}); }
А теперь время использовать это!
struct spaceship; struct asteriod; struct star; std::string ship_asteroid(spaceship s, asteroid a); std::string ship_star(spaceship s, star); std::string star_star(star a, star b); std::string ship_ship(spaceship a, spaceship b); // Create multidispatcher constexpr inline auto collision = aa::make_visit_invoke< // с С++20 можно использовать здесь и лямбды, но так выглядит проще ship_asteroid, ship_star, star_star, ship_ship >(); ... // Perform runtime overload resolution std::optional<std::string> foo(any_with<A> a, any_with<B> b) { return collision.resolve(a, b); }
Итоги
Мы добились возможности писать мультиметоды так, что они эффективнее, удобнее и лучше масштабируются, чем куча if или std::visit, наша реализация разрешает перегрузку за O(1) от количества возможных типов(то есть не зависит от их количества, в отличие от std::visit), также этот способ может быть использован не только с variant, но и с любыми другими полиморфными типами - один из них кстати any_with<...>, используемый в примере.
Кроме того, благодаря poly_traits мы можем использовать это даже для std::variant и решить проблему с невероятной сложностью компиляции std::visit, то есть мы реализовали удобный инструмент паттерн-матчинга
Разумеется в статью не влезли все возможности и подробности(например можно поддерживать перегрузки по количеству аргументов)
Если вы заинтересованы, то всегда можете посмотреть исходный код здесь: https://github.com/kelbon/AnyAny
