Что и главное зачем мы собираемся делать?
Начнём с примера, допустим у нас есть интерфейс 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
