[libc++] Fix template instantiation depth issues with std::tuple

[ldionne]

Summary

This fixes the issue by implementing _And using the short-circuiting
SFINAE trick that we previously used only in std::tuple. One thing we
could look into is use the naive recursive implementation for disjunctions
with a small number of arguments, and use that trick with larger numbers
of arguments. It might be the case that the constant overhead for setting
up the SFINAE trick makes it only worth doing for larger packs, but that's
left for further work.

This problem was raised in https://reviews.llvm.org/D96523.

[ldionne]

Greatly simplify the implementation of _And, and hopefully fix C++03

libcxx/include/type_traits

struct _MetaBase<true> {
   template <class _First, class...>
   using _FirstImpl _LIBCPP_NODEBUG_TYPE = _First;
   template <class, class _Second, class...>
   using _SecondImpl _LIBCPP_NODEBUG_TYPE = _Second;
   template <class _Tp = void>
   using _EnableIfImpl _LIBCPP_NODEBUG_TYPE = _Tp;
   template <class _Result, class _First, class ..._Rest>
   using _OrImpl _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_First::value != true && sizeof...(_Rest) != 0>::template _OrImpl<_First, _Rest...>;
-  template <class _Result, class _First, class ..._Rest>
-  using _AndImpl _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_First::value == true && sizeof...(_Rest) != 0>::template _AndImpl<_First, _Rest...>;
 };
 
 template <>
 struct _MetaBase<false> {
   template <class _Tp, class _Up>
   using _SelectImpl _LIBCPP_NODEBUG_TYPE = _Up;
   template <template <class...> class, template <class...> class _SecondFn, class ..._Args>
   using _SelectApplyImpl _LIBCPP_NODEBUG_TYPE = _SecondFn<_Args...>;
   template <class _Result, class ...>
   using _OrImpl _LIBCPP_NODEBUG_TYPE = _Result;
-  template <class _Result, class ...>
-  using _AndImpl _LIBCPP_NODEBUG_TYPE = _Result;
 };
 template <bool _Cond, class _Ret = void>
 using _EnableIf _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_Cond>::template _EnableIfImpl<_Ret>;
 template <bool _Cond, class _IfRes, class _ElseRes>
 using _If _LIBCPP_NODEBUG_TYPE = typename _MetaBase<_Cond>::template _SelectImpl<_IfRes, _ElseRes>;
 template <class ..._Rest>
 using _Or _LIBCPP_NODEBUG_TYPE = typename _MetaBase< sizeof...(_Rest) != 0 >::template _OrImpl<false_type, _Rest...>;
-template <class ..._Rest>
-using _And _LIBCPP_NODEBUG_TYPE = typename _MetaBase< sizeof...(_Rest) != 0 >::template _AndImpl<true_type, _Rest...>;
 template <class _Pred>
 struct _Not : _BoolConstant<!_Pred::value> {};
 template <class ..._Args>
 using _FirstType _LIBCPP_NODEBUG_TYPE = typename _MetaBase<(sizeof...(_Args) >= 1)>::template _FirstImpl<_Args...>;
 template <class ..._Args>
 using _SecondType _LIBCPP_NODEBUG_TYPE = typename _MetaBase<(sizeof...(_Args) >= 2)>::template _SecondImpl<_Args...>;
 
+template <class ...> using __expand_to_true = true_type;
+template <class ..._Pred>
+__expand_to_true<_EnableIf<_Pred::value>...> __and_helper(int);
+template <class ...>
+false_type __and_helper(...);
+template <class ..._Pred>
+using _And _LIBCPP_NODEBUG_TYPE = decltype(__and_helper<_Pred...>(0));
+
 template <template <class...> class _Func, class ..._Args>
 struct _Lazy : _Func<_Args...> {};
 
 // Member detector base
 
 template <template <class...> class _Templ, class ..._Args, class = _Templ<_Args...> >
 true_type __sfinae_test_impl(int);
 template <template <class...> class, class ...>

libcxx/test/std/utilities/tuple/tuple.tuple/tuple.cnstr/recursion_depth.pass.cpp

+// -*- C++ -*-
+//===----------------------------------------------------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++03, c++11
+
+// Make sure that we don't blow up the template instantiation recursion depth
+// for tuples of size <= 1024.
+
+#include <tuple>
+#include <cassert>
+#include <utility>
+
+template <size_t... I>
+constexpr void CreateTuple(std::index_sequence<I...>) {
+  std::tuple<decltype(I)...> tuple(I...);
+  assert(std::get<0>(tuple) == 0);
+  assert(std::get<sizeof...(I)-1>(tuple) == sizeof...(I)-1);
+}
+
+constexpr bool test() {
+  CreateTuple(std::make_index_sequence<1024>{});
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test(), "");
+  return 0;
+}