Repository: carbon-language/carbon-lang
File: toolchain/base/kind_switch.h (C/C++)

Code before:
concept TypeFoundInVariant = false;

template <class T>
  requires TypeFoundInVariant<T>
struct ValidCaseType;

template <size_t I, typename T, typename TypePack>
struct IndexOfTypeValue {
  // Error case when `T` is not found in the std::variant<...> types.
  ValidCaseType<T> Error;
};

template <size_t I, typename T, typename... Ts>
struct IndexOfTypeValue<I, T, TypePack<T, Ts...>> {
  static constexpr size_t Index = I;
};

template <size_t I, typename T, typename U, typename... Ts>
struct IndexOfTypeValue<I, T, TypePack<U, Ts...>> {
  static constexpr size_t Index =
      IndexOfTypeValue<I + 1, T, TypePack<Ts...>>::Index;
};

template <typename T, typename TypePack>
[[maybe_unused]] static constexpr size_t IndexOfType =
    IndexOfTypeValue<0, T, TypePack>::Index;

// Given `CARBON_KIND(CaseT name)` this generates `CaseT::Kind`. It explicitly
// returns `KindT` because that may differ from `CaseT::Kind`, and may not be
// copyable.
template <typename SwitchT, typename CaseFnT>
consteval auto ForCase() -> auto {
  using CaseT = llvm::function_traits<CaseFnT>::template arg_t<0>;
  if constexpr (IsStdVariant<SwitchT>) {
    return IndexOfType<CaseT, StdVariantTypePack<SwitchT>>;
  } else {
    using KindT = llvm::function_traits<
        decltype(&std::remove_cvref_t<SwitchT>::kind)>::result_t;
    return static_cast<KindT::RawEnumType>(KindT::template For<CaseT>);
  }
}

// Given `CARBON_KIND_SWITCH(value)` and `CARBON_KIND(CaseT name)` this
// generates `value.As<CaseT>()`.
template <typename CaseFnT, typename SwitchT>
auto Cast(SwitchT&& kind_switch_value) -> decltype(auto) {
  using CaseT = llvm::function_traits<CaseFnT>::template arg_t<0>;
  if constexpr (IsStdVariant<SwitchT>) {
    return std::get<CaseT>(kind_switch_value);
  } else {
    return kind_switch_value.template As<CaseT>();

Review comment (performance):
This will result in compile time that is cubic in the number of variant elements: for each I, we'll instantiate IndexOfTypeValue I times, and each of those instantiations has O(N) elements in its `TypePack<U, Ts...>` argument.

[libcxx does a linear scan](https://github.com/llvm/llvm-project/blob/main/libcxx/include/__tuple/find_index.h) rather than a recursive one, which would make it be quadratic to build a switch over all the elements of a variant -- better, though that's still not great. (Best I've seen recently was code that used `__PRETTY_FUNCTION__` to get a string for the type name, and built a hash table at compile time, but ... that's too much complexity and I bet the constant factor outweighs the benefit in most cases, plus hashing the type name is linear in the length of the type name, which could be large itself.)

Aha! Given we're already macro-expanding for each different arity, there *is* a way to do this in linear time! [Here is an example of the kind of thing we'd want the macros to generate](https://godbolt.org/z/15z1b6Yjo).

Code after:
  static_assert(sizeof...(Ts) <= 12,
                "CARBON_KIND_SWITCH supports std::variant with up to 12 types. "
                "Add more if needed.");
};

// Generate StdVariantTypeMap specializations for each number of types in the
// std::variant<...> type list.
CARBON_INTERNAL_KIND_TYPE_MAP(0);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6, 7);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6, 7, 8);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6, 7, 8, 9);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
CARBON_INTERNAL_KIND_TYPE_MAP(0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11);

#undef CARBON_INTERNAL_KIND_IDENTIFIER
#undef CARBON_INTERNAL_KIND_IDENTIFIERS
#undef CARBON_INTERNAL_KIND_TYPENAME
#undef CARBON_INTERNAL_KIND_TYPENAMES
#undef CARBON_INTERNAL_KIND_ENUM_NAME
#undef CARBON_INTERNAL_KIND_TYPES_TO_ENUM_NAMES
#undef CARBON_INTERNAL_KIND_TYPE_TO_ENUM_NAME
#undef CARBON_INTERNAL_KIND_TYPE_MAP

// Uses the above `CARBON_INTERNAL_KIND_TYPE_MAP` expansions to make an enum
// with a value for each type in a std::variant<...> type list.
template <typename StdVariant>
using StdVariantEnum = StdVariantTypeMap<std::decay_t<StdVariant>>::EnumType;

// Uses the `CARBON_INTERNAL_KIND_TYPE_MAP` expanstions to find the enum value
// in `StdVariantEnum` for a given type `T` in the type list of a
// std::variant<...>.
template <typename T, typename StdVariant>
constexpr auto CaseValueOfTypeInStdVariant =
    StdVariantTypeMap<std::decay_t<StdVariant>>::template EnumValue<T>;

// Given `CARBON_KIND_SWITCH(value)` this returns the actual value to switch on.
//
// For types with a `kind()` accessor, this is the just the value of `kind()`.
// The type returned from `kind()` is expected to be a `SemIR::TypeEnum`, as it
// is required to have its API, including a nested `RawEnumType`.
//
// For std::variant<...> this is an enum synthesized from the types in the
// variant's type list.
template <typename SwitchT>
constexpr auto SwitchOn(SwitchT&& switch_value) -> auto {