[libcxx] Delay evaluation of __make_tuple_types to prevent blowing the max template instantiation depth. Fixes Bug #18345

[EricWF]

Summary

http://llvm.org/bugs/show_bug.cgi?id=18345

Tuple's constructor and assignment operators for "tuple-like" types evaluates __make_tuple_types unnecessarily. In the case of a large array this can blow the template instantiation depth.

Ex:

#include <array>
#include <tuple>
#include <memory>
 
typedef std::array<int, 1256> array_t;
typedef std::tuple<array_t> tuple_t;

int main() {
  array_t a;
  tuple_t t(a); // broken
  t = a; // broken

  // make_shared uses tuple behind the scenes. This bug breaks this code.
  std::make_shared<array_t>(a);
}

To prevent this from happening we delay the instantiation of __make_tuple_types until after we perform the length check. Currently __make_tuple_types is instantiated at the same time that the length check .

[K-ballo]

Have you considered a non-recursive implementation of __tuple_constructible_imp? For instance, checking whether foo(declval<Up>()...) is well-formed given void foo(Tp...).

[EricWF]

I haven't actually considered that. I'm actually leaning towards making __tuple_constructible_imp (and similar) lazy to prevent compile errors where possible. Either way I think I'll prototype something similar to your suggestion to see if it helps compile times.

However I'm more interested in improving __make_tuple_types since it is evaluated multiple times before __tuple_constructible_imp.

[EricWF]

Ping. This is the most important fix I have waiting for review. This already breaks make_shared for arrays. Without this fix both experimental/any + experimental/memory_resource will also have bugs in them.

[EricWF]

Ping. This bug has the potential to break a lot of code.

[K-ballo]

Looks good to me. Some notes attached.

include/__tuple

222

No need to name these parameters

235

..or these

249

..or these

273

..or these

286

..or these

310

..or these

test/utilities/tuple/tuple.tuple/tuple.assign/tuple_array_template_depth.pass.cpp

19

This comment is true only for mismatched tuple-sizes

[EricWF]

Address K-ballo's comments.

[EricWF]

Accepting after @K-ballo did an informal review and after offline discussions with @mclow.lists.

include/__tuple

 
 // __tuple_convertible
 
-template <bool, class _Tp, class _Up>
+template <class, class>
 struct __tuple_convertible_imp : public false_type {};
 
 template <class _Tp0, class ..._Tp, class _Up0, class ..._Up>
-struct __tuple_convertible_imp<true, __tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
+struct __tuple_convertible_imp<__tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
     : public integral_constant<bool,
                                is_convertible<_Tp0, _Up0>::value &&
-                               __tuple_convertible_imp<true, __tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
+                               __tuple_convertible_imp<__tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
 
 template <>
-struct __tuple_convertible_imp<true, __tuple_types<>, __tuple_types<> >
+struct __tuple_convertible_imp<__tuple_types<>, __tuple_types<> >
     : public true_type {};
 
+template <bool, class, class>
+struct __tuple_convertible_apply : public false_type {};
+
+template <class _Tp, class _Up>
+struct __tuple_convertible_apply<true, _Tp, _Up>
+  : public __tuple_convertible_imp<
+      typename __make_tuple_types<_Tp>::type
+    , typename __make_tuple_types<_Up>::type
+    >
+{};
+
 template <class _Tp, class _Up, bool = __tuple_like<typename remove_reference<_Tp>::type>::value,
                                 bool = __tuple_like<_Up>::value>
 struct __tuple_convertible

 
 template <class _Tp, class _Up>
 struct __tuple_convertible<_Tp, _Up, true, true>
-    : public __tuple_convertible_imp<tuple_size<typename remove_reference<_Tp>::type>::value ==
-                                     tuple_size<_Up>::value,
-             typename __make_tuple_types<_Tp>::type, typename __make_tuple_types<_Up>::type>
+    : public __tuple_convertible_apply<tuple_size<typename remove_reference<_Tp>::type>::value ==
+                                     tuple_size<_Up>::value, _Tp, _Up>
 {};
 
 // __tuple_constructible
 
-template <bool, class _Tp, class _Up>
+template <class, class>
 struct __tuple_constructible_imp : public false_type {};
 
 template <class _Tp0, class ..._Tp, class _Up0, class ..._Up>
-struct __tuple_constructible_imp<true, __tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
+struct __tuple_constructible_imp<__tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
     : public integral_constant<bool,
                                is_constructible<_Up0, _Tp0>::value &&
-                               __tuple_constructible_imp<true, __tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
+                               __tuple_constructible_imp<__tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
 
 template <>
-struct __tuple_constructible_imp<true, __tuple_types<>, __tuple_types<> >
+struct __tuple_constructible_imp<__tuple_types<>, __tuple_types<> >
     : public true_type {};
 
+template <bool _SameSize, class, class>
+struct __tuple_constructible_apply : public false_type {};
+
+template <class _Tp, class _Up>
+struct __tuple_constructible_apply<true, _Tp, _Up>
+  : public __tuple_constructible_imp<
+      typename __make_tuple_types<_Tp>::type
+    , typename __make_tuple_types<_Up>::type
+    >
+{};
+
 template <class _Tp, class _Up, bool = __tuple_like<typename remove_reference<_Tp>::type>::value,
                                 bool = __tuple_like<_Up>::value>
 struct __tuple_constructible

 
 template <class _Tp, class _Up>
 struct __tuple_constructible<_Tp, _Up, true, true>
-    : public __tuple_constructible_imp<tuple_size<typename remove_reference<_Tp>::type>::value ==
-                                     tuple_size<_Up>::value,
-             typename __make_tuple_types<_Tp>::type, typename __make_tuple_types<_Up>::type>
+    : public __tuple_constructible_apply<tuple_size<typename remove_reference<_Tp>::type>::value ==
+                                     tuple_size<_Up>::value, _Tp, _Up>
 {};
 
 // __tuple_assignable
 
-template <bool, class _Tp, class _Up>
+template <class, class>
 struct __tuple_assignable_imp : public false_type {};
 
 template <class _Tp0, class ..._Tp, class _Up0, class ..._Up>
-struct __tuple_assignable_imp<true, __tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
+struct __tuple_assignable_imp<__tuple_types<_Tp0, _Tp...>, __tuple_types<_Up0, _Up...> >
     : public integral_constant<bool,
                                is_assignable<_Up0&, _Tp0>::value &&
-                               __tuple_assignable_imp<true, __tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
+                               __tuple_assignable_imp<__tuple_types<_Tp...>, __tuple_types<_Up...> >::value> {};
 
 template <>
-struct __tuple_assignable_imp<true, __tuple_types<>, __tuple_types<> >
+struct __tuple_assignable_imp<__tuple_types<>, __tuple_types<> >
     : public true_type {};
 
+template <bool, class, class>
+struct __tuple_assignable_apply : public false_type {};
+
+template <class _Tp, class _Up>
+struct __tuple_assignable_apply<true, _Tp, _Up>
+  : __tuple_assignable_imp<
+      typename __make_tuple_types<_Tp>::type
+    , typename __make_tuple_types<_Up>::type
+    >
+{};
+
 template <class _Tp, class _Up, bool = __tuple_like<typename remove_reference<_Tp>::type>::value,
                                 bool = __tuple_like<_Up>::value>
 struct __tuple_assignable

 
 template <class _Tp, class _Up>
 struct __tuple_assignable<_Tp, _Up, true, true>
-    : public __tuple_assignable_imp<tuple_size<typename remove_reference<_Tp>::type>::value ==
-                                    tuple_size<_Up>::value,
-             typename __make_tuple_types<_Tp>::type, typename __make_tuple_types<_Up>::type>
+    : public __tuple_assignable_apply<tuple_size<typename remove_reference<_Tp>::type>::value ==
+                                    tuple_size<_Up>::value, _Tp, _Up>
 {};
 
 _LIBCPP_END_NAMESPACE_STD

test/utilities/tuple/tuple.tuple/tuple.assign/tuple_array_template_depth.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <tuple>
+
+// template <class... Types> class tuple;
+
+// template <class Tuple, __tuple_assignable<Tuple, tuple> >
+//   tuple & operator=(Tuple &&);
+
+// This test checks that we do not evaluate __make_tuple_types
+// on the array when it doesn't match the size of the tuple.
+
+#include <array>
+#include <tuple>
+
+// Use 1256 to try and blow the template instantiation depth for all compilers.
+typedef std::array<char, 1256> array_t;
+typedef std::tuple<array_t> tuple_t;
+
+int main()
+{
+    array_t arr;
+    tuple_t tup;
+    tup = arr;
+}

test/utilities/tuple/tuple.tuple/tuple.cnstr/tuple_array_template_depth.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is dual licensed under the MIT and the University of Illinois Open
+// Source Licenses. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+// <tuple>
+
+// template <class... Types> class tuple;
+
+// template <class Tuple, __tuple_convertible<Tuple, tuple> >
+//   tuple(Tuple &&);
+//
+// template <class Tuple, __tuple_constructible<Tuple, tuple> >
+//   tuple(Tuple &&);
+
+// This test checks that we do not evaluate __make_tuple_types
+// on the array.
+
+#include <array>
+#include <tuple>
+
+// Use 1256 to try and blow the template instantiation depth for all compilers.
+typedef std::array<char, 1256> array_t;
+typedef std::tuple<array_t> tuple_t;
+
+int main()
+{
+    array_t arr;
+    tuple_t tup(arr);
+}