<variant>: visit() combinatoric catastrophe

[StephanTLavavej]

Reported by @xiangfan-ms:

C:\Temp>type meow.cpp

#include <cassert>
#include <variant>
using namespace std;

struct S {
    int operator()(auto, auto, auto, auto, auto) const {
        return 1729;
    }
};

int main() {
    using V = variant<char, int, long, long long>;
    assert(visit<int>(S{}, V{'a'}, V{'b'}, V{10}, V{20L}, V{30LL}) == 1729);
}

MSVC accepts this due to the compiler's type trait optimizations, but it still takes a significant amount of time to compile:

C:\Temp>cl /EHsc /nologo /W4 /MTd /Od /std:c++20 /Bt meow.cpp
meow.cpp
time(C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\bin\HostX64\x64\c1xx.dll)=5.114s
time(C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\bin\HostX64\x64\c2.dll)=0.135s
  OptRef: Total time = 0.000s
  OptIcf: Total time = 0.015s
Pass 1: Interval #1, time = 0.062s
Pass 2: Interval #2, time = 0.016s
Final: Total time = 0.078s
time(C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\bin\HostX64\x64\link.exe)=0.082s

C:\Temp>meow

Clang rejects this, because <variant> massively exceeds the compiler's template limits:

C:\Temp>clang-cl /EHsc /nologo /W4 /MTd /Od /std:c++20 meow.cpp
In file included from meow.cpp:2:
In file included from C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\include\variant:15:
In file included from C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\include\exception:12:
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\include\type_traits(52,27): fatal error:
      recursive template instantiation exceeded maximum depth of 1024
    using type = typename _Conjunction<_Next::value, _Next, _Rest...>::type;
                          ^
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\include\type_traits(52,27): note: in
      instantiation of template class 'std::_Conjunction<true, std::is_convertible<int, int>, std::is_convertible<int,
      int>, std::is_convertible<int, int>, std::is_convertible<int, int>, std::is_convertible<int, int>,
      std::is_convertible<int, int>, std::is_convertible<int, int>, std::is_convertible<int, int>,
[...]
C:\Program Files\Microsoft Visual Studio\2022\Preview\VC\Tools\MSVC\14.33.31424\include\variant(1671,23): note: in
      instantiation of template class 'std::_Variant_all_visit_results_implicitly_convertible<int, S,
      std::_Meta_list<std::integer_sequence<unsigned long long, 0, 0, 0, 0, 0>, std::integer_sequence<unsigned long
      long, 0, 0, 0, 0, 1>, std::integer_sequence<unsigned long long, 0, 0, 0, 0, 2>, std::integer_sequence<unsigned
      long long, 0, 0, 0, 0, 3>, std::integer_sequence<unsigned long long, 0, 0, 0, 0, 4>,
[...]
      long long, 4, 4, 4, 4, 3>, std::integer_sequence<unsigned long long, 4, 4, 4, 4, 4>>, std::variant<char, int,
      long, long long> &&, std::variant<char, int, long, long long> &&, std::variant<char, int, long, long long> &&,
      std::variant<char, int, long, long long> &&, std::variant<char, int, long, long long> &&>' requested here
        static_assert(_Variant_all_visit_results_implicitly_convertible<_Ret, _Callable, _ListOfIndexVectors,
                      ^
meow.cpp(13,12): note: in instantiation of function template specialization 'std::visit<int, S, std::variant<char, int,
      long, long long>, std::variant<char, int, long, long long>, std::variant<char, int, long, long long>,
      std::variant<char, int, long, long long>, std::variant<char, int, long, long long>, void>' requested here
    assert(visit<int>(S{}, V{'a'}, V{'b'}, V{10}, V{20L}, V{30LL}) == 1729);
           ^
1 error generated.

This is the code that's responsible:

STL/stl/inc/variant

Lines 1662 to 1675 in 17fde2c

	#if _HAS_CXX20
	template <class _Ret, class _Callable, class... _Variants, class = void_t<_As_variant<_Variants>...>>
	constexpr _Ret visit(_Callable&& _Obj, _Variants&&... _Args) {
	constexpr auto _Size = _Variant_total_states<_Remove_cvref_t<_As_variant<_Variants>>...>;
	using _ListOfIndexLists =
	_Meta_list<_Meta_as_list<make_index_sequence<1 + variant_size_v<_Remove_cvref_t<_As_variant<_Variants>>>>>...>;
	using _ListOfIndexVectors =
	_Meta_transform<_Meta_quote<_Meta_as_integer_sequence>, _Meta_cartesian_product<_ListOfIndexLists>>;
	if constexpr (!is_void_v<_Ret>) {
	static_assert(_Variant_all_visit_results_implicitly_convertible<_Ret, _Callable, _ListOfIndexVectors,
	_As_variant<_Variants>...>::value,
	"visit<R>() requires the result of all potential invocations to be implicitly convertible to R "
	"(N4835 [variant.visit]/2).");
	}

STL/stl/inc/variant

Lines 1502 to 1532 in 17fde2c

	template <class _Callable, class _IndexSequence, class... _Variants>
	struct _Variant_single_visit_result; // undefined
	template <class _Callable, size_t... _Idxs, class... _Variants>
	struct _Variant_single_visit_result<_Callable, index_sequence<_Idxs...>,
	_Variants...> { // result type/category from invoking _Callable with the elements of
	// _Variants... at (_Idxs - 1)...
	using type = decltype(_STD invoke(_STD declval<_Callable>(),
	_Variant_raw_get<_Idxs == 0 ? 0 : _Idxs - 1>(_STD declval<_Variants>()._Storage())...));
	};
	template <class _Callable, class _ListOfIndexVectors, class... _Variants>
	struct _Variant_all_visit_results_same; // undefined
	template <class _Callable, class... _IndexVectors, class... _Variants>
	struct _Variant_all_visit_results_same<_Callable, _Meta_list<_IndexVectors...>, _Variants...>
	: _All_same<typename _Variant_single_visit_result<_Callable, _IndexVectors,
	_Variants...>::type...>::type { // true_type iff invocation of _Callable on the elements of _Variants with all
	// sequences of indices in _IndexVectors has the same type and value category.
	};
	template <class _To, class _Callable, class _ListOfIndexVectors, class... _Variants>
	struct _Variant_all_visit_results_implicitly_convertible; // undefined
	template <class _To, class _Callable, class... _IndexVectors, class... _Variants>
	struct _Variant_all_visit_results_implicitly_convertible<_To, _Callable, _Meta_list<_IndexVectors...>, _Variants...>
	: _Convertible_from_all<_To,
	typename _Variant_single_visit_result<_Callable, _IndexVectors, _Variants...>::type...>::type {
	// true_type if invocation of _Callable on the elements of _Variants with all sequences of indices in _IndexVectors
	// is implicitly convertible to _To.
	};

As @CaseyCarter explained, variant<char, int, long, long long> has 5 possible states (including valueless_by_exception), so visiting 5 variants will examine 5^5 = 3,125 combinations of argument types.

I (@StephanTLavavej 🐱) wonder whether we could use tree-like expansion instead of linear pack expansion to avoid the length limits here. (We'd still be doing the same amount of work, just not with huge type lists.) However, I am uncertain whether the actual visitation would also need to be changed:

STL/stl/inc/variant

Lines 1677 to 1678 in 17fde2c

	return _Visit_impl<_Size, _Ret, _ListOfIndexVectors>(
	static_cast<_Callable&&>(_Obj), static_cast<_Variants&&>(_Args)...);

[CaseyCarter]

I am uncertain whether the actual visitation would also need to be changed

_ListOfIndexVectors has the same number of argument types on line 1677 as it did on line 1506, so yes the actual visitation will also need to be changed.

[CaseyCarter]

_ListOfIndexVectors has the same number of argument types on line 1677 as it did on line 1506, so yes the actual visitation will also need to be changed.

While this argument still seems perfectly reasonable, we have empiric evidence that disagrees. 🤷‍♂️