[libcxx][type_traits] Implement C++20 common_ref

[miscco]

Summary

This implements the new type trait common_ref that is needed for library concepts support

[cjdb]

libcxx/include/type_traits

2306–2307

Perhaps we should hold off on merging this so we can use std::convertible_to instead.

[miscco]

@cjdb I have to disagree. That would create a ciruclar dependency between concepts and type_traits, which is in my opinion not worth it.

Also note that std::convertible_to essentially falls back to is_convertible_v

[miscco]

libcxx/include/type_traits

2292–2318

I think I should add the respective wording here so that one understands what it is actually testing.

[miscco]

Simplified code and improved comments

[miscco]

libcxx/include/type_traits

2306–2307

I would add that std::convertible_to has slightly different semantics too as it has some addtional requires clauses

[cjdb]

libcxx/include/type_traits

2306–2307

Fair. I'd at least encourage the use of a _requires-clause_, since it's demonstrably faster to compile than SFINAE and is being commit for the first time to a concepts-aware compiler.

[miscco]

libcxx/include/type_traits

2306–2307

That sounds reasonable. However, someone could theoretically use a C++20 compiler (aka clang 9) without concept support and that would lead to <type_traits> not compiling.

On the other hand I think that is a very bad use case that should not be suported. Maintainers thoughts?

[cjdb]

libcxx/include/type_traits

2306–2307

Since common_reference is really only useful with ranges in mind, we could section this code off with feature-test macros?

[miscco]

ping

[miscco]

ping

[miscco]

ping

[cjdb]

@miscco What is the status of this commit? I will review it on Wednesday if it's still in good shape.

[miscco]

Ping

In D74351#2547689, @cjdb wrote:

@miscco What is the status of this commit? I will review it on Wednesday if it's still in good shape.

Hey,

as far as I can tell it should be still up to date. I have only limited time right now to look at it in depth though

[ldionne]

libcxx/include/type_traits

2306–2307

On the other hand I think that is a very bad use case that should not be suported. Maintainers thoughts?

I think it's entirely fine to use requires clauses if it simplifies the implementation. I have little sympathy for someone trying to use this with a compiler that doesn't support concepts, or with a compiler that does but with concepts disabled.

[cjdb]

@miscco I took this patch and reworked it slightly in D96657 so that it's a bit closer to the standard wording (it's a separate patch because I didn't want to overwrite your implementation with such a drastic change).

Are you okay with this, or have I overlooked an advantage to you moving some of COMMON-REF into common_reference?

[miscco]

@cjdb I am totally fine with dropping this revision. Thanks a lot for working on this!

libcxx/include/type_traits

: __common_type_impl<
           __common_types<_Tp, _Up, _Vp _LIBCPP_OPTIONAL_PACK(_Rest...)> > {};
 
 #undef _LIBCPP_OPTIONAL_PACK
 
 #if _LIBCPP_STD_VER > 11
 template <class ..._Tp> using common_type_t = typename common_type<_Tp...>::type;
 #endif
 
+// common_ref
+#if _LIBCPP_STD_VER > 17
+// Let COND_RES(X, Y) be:
+template <class _Tp, class _Up>
+using __cond_res =
+    decltype(false ? _VSTD::declval<_Tp(&)()>()() : _VSTD::declval<_Up(&)()>()());
+
+// Let COPYCV(FROM, TO) be an alias for type TO with the addition of FROM’s
+// top-level cv-qualifiers.
+template <class _From>
+struct __copy_cv_
+{
+    template <class _To>
+    using __res_type = _To;
+};
+template <class _From>
+struct __copy_cv_<const _From>
+{
+    template <class _To>
+    using __res_type = add_const_t<_To>;
+};
+template <class _From>
+struct __copy_cv_<volatile _From>
+{
+    template <class _To>
+    using __res_type = add_volatile_t<_To>;
+};
+template <class _From>
+struct __copy_cv_<const volatile _From>
+{
+    template <class _To>
+    using __res_type = add_cv_t<_To>;
+};
+template <class _From, class _To>
+using __copy_cv = typename __copy_cv_<_From>::template __res_type<_To>;
+
+// Let XREF(A) denote a unary class [sic] template T such [...]
+// [Note: XREF(A) is __xref<A>::template __res_type]
+template <class _Tp>
+struct __xref
+{
+    template <class _Up>
+    using __res_type = __copy_cv<_Tp, _Up>;
+};
+template <class _Tp>
+struct __xref<_Tp&>
+{
+    template <class _Up>
+    using __res_type = add_lvalue_reference_t<__copy_cv<_Tp, _Up>>;
+};
+template <class _Tp>
+struct __xref<_Tp&&>
+{
+    template <class _Up>
+    using __res_type = add_rvalue_reference_t<__copy_cv<_Tp, _Up>>;
+};
+
+//            COMMON-REF(A, B) is COND-RES(COPYCV(X, Y) &, COPYCV(!Y, X) &)
+//            if that type exists and is a reference type.
+template <class _Tp, class _Up,
+    class _Result = __cond_res<__copy_cv<_Tp, _Up>&, __copy_cv<_Up, _Tp>&>,
+    class = enable_if_t<is_lvalue_reference_v<_Result>>>
+using __common_ref = _Result;
+
+//            Otherwise, let C be remove_­reference_­t<COMMON-REF(X&, Y&)>&&.
+template <class _Tp, class _Up>
+using __common_ref_C = remove_reference_t<__common_ref<_Tp, _Up>>&&;
+
+//            Otherwise, let D be COMMON-REF(const X&, Y&).
+template <class _Tp, class _Up>
+using __common_ref_D = __common_ref<const _Tp, _Up>;
+
+// Note C: For the common_reference trait applied to a parameter pack [...]
+
+// bullet 1 - sizeof...(T) == 0
+template <class...>
+struct _LIBCPP_TEMPLATE_VIS common_reference {};
+
+template <class... _Types>
+using common_reference_t = typename common_reference<_Types...>::type;
+
+// bullet 2 - sizeof...(T) == 1
+template <class _Tp>
+struct _LIBCPP_TEMPLATE_VIS common_reference<_Tp>
+{
+    using type = _Tp;
+};
+
+// bullet 3 - sizeof...(T) == 2
+
+// sub-bullet 4 & 5 - [...] if common_type_t<T1, T2> is well-formed [...]
+//                  - Otherwise, there shall be no member type.
+template <class _Tp, class _Up, class = void>
+struct __common_reference4 : common_type<_Tp, _Up>
+{};
+
+// sub-bullet 3 - [...] if COND_RES(T1, T2) is well-formed [...]
+template <class _Tp, class _Up>
+struct __common_reference4<_Tp, _Up, void_t<__cond_res<_Tp, _Up>>>
+{
+    using type = __cond_res<_Tp, _Up>;
+};
+
+// sub-bullet 2 - [...] if basic_common_reference<[...]>::type is well-formed [...]
+template <class, class, template <class> class, template <class> class>
+struct _LIBCPP_TEMPLATE_VIS basic_common_reference
+{};
+
+template <class _Tp, class _Up>
+using __basic_common_ref = typename basic_common_reference<
+    remove_cvref_t<_Tp>, remove_cvref_t<_Up>,
+    __xref<_Tp>::template __res_type, __xref<_Up>::template __res_type>::type;
+
+template <class _Tp, class _Up, class = void>
+struct __common_reference3 : __common_reference4<_Tp, _Up>
+{};
+
+template <class _Tp, class _Up>
+struct __common_reference3<_Tp, _Up, void_t<__basic_common_ref<_Tp, _Up>>>
+{
+    using type = __basic_common_ref<_Tp, _Up>;
+};
+
+// sub-bullet 1 - If T1 and T2 are reference types and COMMON_REF(T1, T2) is well-formed [...]
+template <class _Tp, class _Up, class = void>
+struct __common_reference2 : __common_reference3<_Tp, _Up>
+{};
+
+template <class _Tp, class _Up>
+struct __common_reference2<_Tp&, _Up&, void_t<__common_ref<_Tp, _Up>>>
+{
+    using type = __common_ref<_Tp, _Up>;
+};
+
+template <class _Tp, class _Up>
+struct __common_reference2<_Tp&&, _Up&&, enable_if_t<
+    is_convertible_v<_Tp&&, __common_ref_C<_Tp, _Up>> &&
+    is_convertible_v<_Up&&, __common_ref_C<_Tp, _Up>>>>
+{
+    using type = __common_ref_C<_Tp, _Up>;
+};
+
+template <class _Tp, class _Up>
+struct __common_reference2<_Tp&&, _Up&, enable_if_t<
+    is_convertible_v<_Tp&&, __common_ref<const _Tp, _Up>>>>
+{
+    using type = __common_ref_D<_Tp, _Up>;
+};
+
+template <class _Tp, class _Up>
+struct __common_reference2<_Tp&, _Up&&, enable_if_t<
+    is_convertible_v<_Up&&, __common_ref<const _Up, _Tp>>>>
+{
+    using type = __common_ref_D<Up, _Tp>;
+};
+
+template <class _Tp, class _Up>
+struct _LIBCPP_TEMPLATE_VIS common_reference<_Tp, _Up>
+    : __common_reference2<_Tp, _Up>
+{};
+
+// bullet 4 - sizeof...(T) > 2
+template <class _Void, class _Tp, class _Up, class... _Types>
+struct __fold_common_reference
+{};
+template <class _Tp, class _Up, class... _Types>
+struct __fold_common_reference<void_t<common_reference_t<_Tp, _Up>>, _Tp, _Up, _Types...>
+    : common_reference<common_reference_t<_Tp, _Up>, _Types...>
+{};
+
+template <class _Tp, class _Up, class _Vp, class... _Rest>
+struct _LIBCPP_TEMPLATE_VIS common_reference<_Tp, _Up, _Vp, _Rest...>
+    : __fold_common_reference<void, _Tp, _Up, _Vp, _Rest...>
+{};
+
+#endif // _LIBCPP_STD_VER > 17
+
 // is_assignable
 
 template<typename, typename _Tp> struct __select_2nd { typedef _LIBCPP_NODEBUG_TYPE _Tp type; };
 
 template <class _Tp, class _Arg>
 typename __select_2nd<decltype((_VSTD::declval<_Tp>() = _VSTD::declval<_Arg>())), true_type>::type
 __is_assignable_test(int);
 

libcxx/test/std/utilities/meta/meta.trans/meta.trans.other/common_reference.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.
+//
+//===----------------------------------------------------------------------===//
+
+// UNSUPPORTED: c++98, c++03, c++11, c++14, c++17
+
+// type_traits
+// common_reference
+
+#include <type_traits>
+
+using std::common_reference;
+using std::common_reference_t;
+using std::is_same_v;
+using std::void_t;
+
+template <class, class = void>
+constexpr bool is_trait = false;
+template <class T>
+constexpr bool is_trait<T, void_t<typename T::type>> = true;
+
+// A slightly simplified variation of std::tuple
+template <class...> struct Tuple {};
+
+template <class, class, class> struct Tuple_helper {};
+template <class... Ts, class... Us>
+struct Tuple_helper<void_t<common_reference_t<Ts, Us>...>, Tuple<Ts...>, Tuple<Us...>>
+{
+    using type = Tuple<common_reference_t<Ts, Us>...>;
+};
+
+namespace std
+{
+    template <class... Ts, class... Us,
+        template <class> class TQual, template <class> class UQual>
+    struct basic_common_reference<::Tuple<Ts...>, ::Tuple<Us...>, TQual, UQual>
+        : ::Tuple_helper<void, Tuple<TQual<Ts>...>, Tuple<UQual<Us>...>>
+    {};
+}
+
+struct X2 {};
+struct Y2 {};
+struct Z2 {};
+
+namespace std
+{
+    template <>
+    struct common_type<X2, Y2>
+    {
+        using type = Z2;
+    };
+    template <>
+    struct common_type<Y2, X2>
+    {
+        using type = Z2;
+    };
+}
+
+// (6.1)
+//  -- If sizeof...(T) is zero, there shall be no member type.
+void test_bullet_one() {
+    static_assert(!is_trait<common_reference<>>);
+}
+
+// (6.2)
+//  -- Otherwise, if sizeof...(T) is one, let T0 denote the sole type in the
+//     pack T. The member typedef type shall denote the same type as T0.
+void test_bullet_two() {
+    static_assert(is_same_v<common_reference_t<void>, void>);
+    static_assert(is_same_v<common_reference_t<int>, int>);
+    static_assert(is_same_v<common_reference_t<int&>, int&>);
+    static_assert(is_same_v<common_reference_t<int&&>, int&&>);
+    static_assert(is_same_v<common_reference_t<int const>, int const>);
+    static_assert(is_same_v<common_reference_t<int const&>, int const&>);
+    static_assert(is_same_v<common_reference_t<int const&&>, int const&&>);
+    static_assert(is_same_v<common_reference_t<int volatile[]>, int volatile[]>);
+    static_assert(is_same_v<common_reference_t<int volatile (&)[]>, int volatile (&)[]>);
+    static_assert(is_same_v<common_reference_t<int volatile (&&)[]>, int volatile (&&)[]>);
+    static_assert(is_same_v<common_reference_t<void(&)()>, void(&)()>);
+    static_assert(is_same_v<common_reference_t<void(&&)()>, void(&&)()>);
+}
+
+// (6.3)
+//  -- Otherwise, if sizeof...(T) is two, let T1 and T2 denote the two types in
+//     the pack T. Then
+// (6.3.1)
+//    -- If T1 and T2 are reference types and COMMON_REF(T1, T2) is well-formed,
+//       then the member typedef type denotes that type.
+void test_bullet_three_one() {
+    {
+        struct B {};
+        struct D : B {};
+        static_assert(is_same_v<common_reference_t<B&, D&>, B&>);
+        static_assert(is_same_v<common_reference_t<B const&, D&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B&, D const&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B&, D const&, D&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B&, D&, B&, D&>, B&>);
+
+        static_assert(is_same_v<common_reference_t<B&&, D&&>, B&&>);
+        static_assert(is_same_v<common_reference_t<B const&&, D&&>, B const&&>);
+        static_assert(is_same_v<common_reference_t<B&&, D const&&>, B const&&>);
+        static_assert(is_same_v<common_reference_t<B&, D&&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B&, D const&&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B const&, D&&>, B const&>);
+
+        static_assert(is_same_v<common_reference_t<B&&, D&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B&&, D const&>, B const&>);
+        static_assert(is_same_v<common_reference_t<B const&&, D&>, B const&>);
+    }
+
+    static_assert(is_same_v<common_reference_t<int const volatile&&,
+                                               int volatile&&>,
+                            int const volatile&&>);
+
+    static_assert(is_same_v<common_reference_t<int const&,
+                                               int volatile&>,
+                            int const volatile&>);
+
+    static_assert(is_same_v<common_reference_t<int (&)[10],
+                                               int (&&)[10]>,
+                            int const (&)[10]>);
+
+    static_assert(is_same_v<common_reference_t<int const (&)[10],
+                                               int volatile (&)[10]>,
+                            int const volatile (&)[10]>);
+}
+
+// (6.3.2)
+//    -- Otherwise, if basic_common_reference<remove_cvref_t<T1>,
+//       remove_cvref_t<T2>, XREF(T1), XREF(T2)>::type is well-formed, then the
+//       member typedef type denotes that type.
+void test_bullet_three_two() {
+    static_assert(is_same_v<common_reference_t<const Tuple<int, short>&,
+                                               Tuple<int&, short volatile&>>,
+                            Tuple<const int&, const volatile short&>>);
+
+    static_assert(is_same_v<common_reference_t<volatile Tuple<int, short>&,
+                                               const Tuple<int, short>&>,
+                            const volatile Tuple<int, short>&>);
+}
+
+// (6.3.3)
+//    -- Otherwise, if COND_RES(T1, T2) is well-formed, then the member typedef
+//       type denotes that type.
+void test_bullet_three_three() {
+    static_assert(is_same_v<common_reference_t<void, void>, void>);
+    static_assert(is_same_v<common_reference_t<int, short>, int>);
+    static_assert(is_same_v<common_reference_t<int, short&>, int>);
+    static_assert(is_same_v<common_reference_t<int&, short&>, int>);
+    static_assert(is_same_v<common_reference_t<int&, short>, int>);
+
+    // tricky volatile reference case
+    static_assert(is_same_v<common_reference_t<int&&, int volatile&>, int>);
+    static_assert(is_same_v<common_reference_t<int volatile&, int&&>, int>);
+
+    static_assert(is_same_v<common_reference_t<int (&)[10], int (&)[11]>, int*>);
+
+    {
+        // https://github.com/ericniebler/stl2/issues/338
+        struct MyIntRef { MyIntRef(int&); };
+        static_assert(is_same_v<common_reference_t<int&, MyIntRef>, MyIntRef>);
+    }
+}
+
+// (6.3.4)
+//    -- Otherwise, if common_type_t<T1, T2> is well-formed, then the member
+//       typedef type denotes that type.
+void test_bullet_three_four() {
+    {
+        struct moveonly {
+            moveonly() = default;
+            moveonly(moveonly&&) = default;
+            moveonly& operator=(moveonly&&) = default;
+        };
+        struct moveonly2 : moveonly {};
+
+        static_assert(is_same_v<common_reference_t<moveonly  const&, moveonly >, moveonly>);
+        static_assert(is_same_v<common_reference_t<moveonly2 const&, moveonly >, moveonly>);
+        static_assert(is_same_v<common_reference_t<moveonly  const&, moveonly2>, moveonly>);
+    }
+
+    static_assert(is_same_v<common_reference_t<X2&, Y2 const&>, Z2>);
+}
+
+// (6.3.5)
+//    -- Otherwise, there shall be no member type.
+void test_bullet_three_five() {
+    static_assert(!is_trait<
+        common_reference<volatile Tuple<short>&, const Tuple<int, short>&>>);
+}
+
+// (6.4)
+//  -- Otherwise, if sizeof...(T) is greater than two, let T1, T2, and Rest,
+//     respectively, denote the first, second, and (pack of) remaining types
+//     comprising T. Let C be the type common_reference_t<T1, T2>. Then:
+// (6.4.1)
+//    -- If there is such a type C, the member typedef type shall denote the
+//       same type, if any, as common_reference_t<C, Rest...>.
+void test_bullet_four_one() {
+    static_assert(is_same_v<common_reference_t<int, int, int>, int>);
+    static_assert(is_same_v<common_reference_t<int&&, int const&, int volatile&>,
+                            int const volatile&>);
+    static_assert(is_same_v<common_reference_t<int&&, int const&, float&>, float>);
+}
+
+// (6.4.2)
+//    -- Otherwise, there shall be no member type.
+void test_bullet_four_two() {
+    static_assert(!is_trait<common_reference<int, short, int, char*>>);
+}
+
+int main(int, char**)
+{
+    test_bullet_one();
+    test_bullet_two();
+    test_bullet_three_one();
+    test_bullet_three_two();
+    test_bullet_three_three();
+    test_bullet_three_four();
+    test_bullet_three_five();
+    test_bullet_four_one();
+    test_bullet_four_two();
+
+    return 0;
+}