Что и главное зачем мы собираемся делать?

Начнём с примера, допустим у нас есть интерфейс 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) { ??? }

В стандартной библиотеке С++ нет возможности сделать это никак кроме вереницы '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 вызова, что задача нетривиальная, но необходимая

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

Так, с ключами в 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

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