[libc++] P0433R2: add the remaining deduction guides.

[var-const]

Summary

Add deduction guides to valarray and scoped_allocator_adaptor. This largely
finishes implementation of the paper:

• deduction guides for other classes mentioned in the paper were implemented previously (see the list below);
• deduction guides for several classes contained in the proposal (reference_wrapper, lock_guard, scoped_lock, unique_lock, shared_lock) were removed by LWG2981.

Also add deduction guides to the synopsis for the few classes (e.g. pair)
where they were missing.

The only part of the paper that isn't fully implemented after this patch is
making sure certain deduction guides don't participate in overload resolution
when given incorrect template parameters.

List of significant commits implementing the other parts of P0433 (omitting some
minor fixes):

• pair
• basic_string
• array
• deque
• forward_list
• list
• vector
• queue/stack/priority_queue
• basic_regex
• optional
• map/multimap
• set/multiset
• unordered_set/unordered_multiset
• unordered_map/unordered_multimap
• function
• tuple
• shared_ptr/weak_ptr

Additional notes:

• It was revision 2 of the paper that was voted into the Standard. P0433R3 is a separate paper that is not part of the Standard.
• The paper also mandates removing several make_*_searcher functions (e.g. make_boyer_moore_searcher) which are currently not implemented (except in experimental/).
• The __cpp_lib_deduction_guides feature test macro from the paper was accidentally omitted from the Standard.

[• Quuxplusone]

Thanks for working on this!

libcxx/docs/Status/Cxx17.rst

43

I assume you've basically done the work already to figure out which guides you're talking about; could you specify that exact list right here? (Or even better, make a second PR that just fixes them ;))

libcxx/include/valarray

1086

Please line-break between > and valarray.

libcxx/test/std/numerics/numarray/template.valarray/valarray.cons/deduct.pass.cpp

22–29

Instead of these three tests, I'd rather see these seven tests (to hit all the expected CTAD codepaths):

{
    std::valarray v = {1, 2, 3, 4, 5};  // from initializer_list<T>
    ASSERT_SAME_TYPE(decltype(v), std::valarray<int>);
}
{
    long a[] = {1, 2, 3, 4, 5};
    std::valarray v(a, 5);  // from const T(&)[N], size_t
    ASSERT_SAME_TYPE(decltype(v), std::valarray<long>);
}
{
    long a[] = {1, 2, 3, 4, 5};
    std::valarray v(&a[0], 5);  // from const T&, size_t
    ASSERT_SAME_TYPE(decltype(v), std::valarray<long*>);  // surprising but true
}
{
    std::valarray<long> v {1,2,3,4,5};
    std::valarray v2 = v[std::slice(2,5,1)];  // from slice_array<T>
    static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
}
{
    std::valarray<long> v {1,2,3,4,5};
    std::valarray v2 = v[std::gslice(0, {5}, {1})];  // from gslice_array<T>
    static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
}
{
    std::valarray<long> v = {1, 2, 3, 4, 5};
    std::valarray<bool> m = {true, false, true, false, true};
    std::valarray v2 = v[m];  // from mask_array<T>
    static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
}
{
    std::valarray<long> v = {1, 2, 3, 4, 5};
    std::valarray<size_t> i = {1, 2, 3};
    std::valarray v2 = v[i];  // from indirect_array<T>
    static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
}

libcxx/test/std/utilities/allocator.adaptor/allocator.adaptor.cnstr/deduct.pass.cpp

30

Here and throughout, please check the actual type of a:

ASSERT_SAME_TYPE(decltype(a), std::scoped_allocator_adaptor<OuterAlloc>);

Checking the nested ::outer_allocator_type typedef isn't quite as good; and although checking both would be harmless, it also wouldn't be helpful. All we really care about in this specific test file is that CTAD produces the exactly correct scoped_allocator_adaptor<...> type; the existence/values of these nested typedefs can (and should already be) tested elsewhere.

libcxx/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp

40–65

FWIW, these three new tests strike me as redundant with line 35 (which itself — pre-existing — is already redundant with line 27).

[ldionne]

libcxx/docs/Status/Cxx17.rst

43

I think @var-const 's intent was to come back and fix them in a future PR. The guides he's talking about here are things like SFINAEing unordered_map guides away when the provided iterator is not an input iterator. We have a couple such guides that are not 100% correctly implemented.

libcxx/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp

40–65

IMO those are all relevant. The const T& one makes sure that we handle references correctly, the T* one that we handle pointers correctly, and the T[] one that arrays will cause the deduction guide to deduce an optional pointer.

Sure, when you know how it's implemented you realize that it's obvious it's going to work, but if you don't know how the deduction guide is implemented, IMO these test cases are useful.

[var-const]

• address feedback;
• don't define the deduction guides for language versions below C++17.

libcxx/docs/Status/Cxx17.rst

43

There is a requirement for all containers that deduction guides should not participate in overload resolution when the given types do not qualify as input iterators / allocators / comparators / hash functors. This requirement is largely untested and I think in some cases not fully implemented. There is also a requirement that a unique_ptr cannot be deduced from a plain pointer (to prevent a case where deducing from a built-in array would also deduce a pointer) -- it's implemented correctly but not tested.

I thought that listing all of this would be a little too much detail, and I'm indeed working on addressing those in a follow-up, so I thought it's okay to be a little more vague in the description. Please let me know if you'd still like to expand the description.

libcxx/test/std/numerics/numarray/template.valarray/valarray.cons/deduct.pass.cpp

22–29

Thanks a lot! Added.

libcxx/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp

40–65

@Quuxplusone Arthur, please let me know if you feel strongly about removing these. I'm slightly inclined to keep these tests (my intention was pretty much what Louis described), but I'm ok to remove them.

[• Quuxplusone]

LGTM!

libcxx/docs/Status/Cxx17.rst

43

If there's a chance someone else will have to do the work later, then it's important to have a really good and unambiguous TODO list here. But if you're just holding the list in your head while you actively do the work, then this is fine.
It sounds like the latter is the case; therefore I'm OK with this.

libcxx/test/std/numerics/numarray/template.valarray/valarray.cons/deduct.pass.cpp

46

ASAN rightly complains because I forgot that the second argument is "size", not "end". Make this std::slice(2,3,1) and I think it'll be quiet.

libcxx/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp

40–65

Personally I do still think they're unneeded; but Louis' preference overrules mine. Keep.

[var-const]

Fix the Asan issue.

[var-const]

libcxx/test/std/numerics/numarray/template.valarray/valarray.cons/deduct.pass.cpp

46

Done, thanks.

libcxx/docs/Status/Cxx17.rst

 
 .. csv-table::
    :file: Cxx17Papers.csv
    :header-rows: 1
    :widths: auto
 
 .. note::
 
-   .. [#note-P0433] P0433: So far, only the ``<string>``, sequence containers, container adaptors and ``<regex>`` portions of P0433 have been implemented.
+   .. [#note-P0433] P0433: The only part not fully implemented is the requirement that certain deduction guides should not participate in overload resolution when given incorrect template arguments.
    .. [#note-P0607] P0607: The parts of P0607 that are not done are the ``<regex>`` bits.
 
 
 .. _issues-status-cxx17:
 
 Library Working Group Issues Status
 ====================================
 
 .. csv-table::
    :file: Cxx17Issues.csv
    :header-rows: 1
    :widths: auto

libcxx/docs/Status/Cxx20Issues.csv

 "`2964 <https://wg21.link/LWG2964>`__","Apparently redundant requirement for dynamic_pointer_cast","Albuquerque","",""
 "`2965 <https://wg21.link/LWG2965>`__","Non-existing path::native_string() in filesystem_error::what() specification","Albuquerque","|Nothing To Do|",""
 "`2972 <https://wg21.link/LWG2972>`__","What is ``is_trivially_destructible_v<int>``\ ?","Albuquerque","|Complete|",""
 "`2976 <https://wg21.link/LWG2976>`__","Dangling uses_allocator specialization for packaged_task","Albuquerque","|Complete|",""
 "`2977 <https://wg21.link/LWG2977>`__","unordered_meow::merge() has incorrect Throws: clause","Albuquerque","|Nothing To Do|",""
 "`2978 <https://wg21.link/LWG2978>`__","Hash support for pmr::string and friends","Albuquerque","",""
 "`2979 <https://wg21.link/LWG2979>`__","aligned_union should require complete object types","Albuquerque","|Complete|",""
 "`2980 <https://wg21.link/LWG2980>`__","Cannot compare_exchange empty pointers","Albuquerque","",""
-"`2981 <https://wg21.link/LWG2981>`__","Remove redundant deduction guides from standard library","Albuquerque","",""
+"`2981 <https://wg21.link/LWG2981>`__","Remove redundant deduction guides from standard library","Albuquerque","|Nothing To Do|",""
 "`2982 <https://wg21.link/LWG2982>`__","Making size_type consistent in associative container deduction guides","Albuquerque","",""
 "`2988 <https://wg21.link/LWG2988>`__","Clause 32 cleanup missed one typename","Albuquerque","|Complete|","13.0"
 "`2993 <https://wg21.link/LWG2993>`__","reference_wrapper<T> conversion from T&&","Albuquerque","|Complete|","13.0"
 "`2998 <https://wg21.link/LWG2998>`__","Requirements on function objects passed to {``forward_``,}list-specific algorithms","Albuquerque","|Nothing To Do|",""
 "`3001 <https://wg21.link/LWG3001>`__","weak_ptr::element_type needs remove_extent_t","Albuquerque","|Complete|","14.0"
 "`3024 <https://wg21.link/LWG3024>`__","variant's copies must be deleted instead of disabled via SFINAE","Albuquerque","|Complete|",""
 "","","","",""
 "`2164 <https://wg21.link/LWG2164>`__","What are the semantics of ``vector.emplace(vector.begin(), vector.back())``\ ?","Jacksonville","|Complete|",""

libcxx/include/scoped_allocator

template <class T1, class T2, class U, class V>
         void construct(pair<T1, T2>* p, pair<U, V>&& x);
     template <class T> void destroy(T* p);
 
     template <class T> void destroy(T* p) noexcept;
 
     scoped_allocator_adaptor select_on_container_copy_construction() const noexcept;
 };
 
+template<class OuterAlloc, class... InnerAllocs>
+    scoped_allocator_adaptor(OuterAlloc, InnerAllocs...)
+        -> scoped_allocator_adaptor<OuterAlloc, InnerAllocs...>;
+
 template <class OuterA1, class OuterA2, class... InnerAllocs>
     bool
     operator==(const scoped_allocator_adaptor<OuterA1, InnerAllocs...>& a,
                const scoped_allocator_adaptor<OuterA2, InnerAllocs...>& b) noexcept;
 
 template <class OuterA1, class OuterA2, class... InnerAllocs>
     bool
     operator!=(const scoped_allocator_adaptor<OuterA1, InnerAllocs...>& a,
private:
     {
         using _Tup = tuple<_Args&&..., inner_allocator_type&>;
         return _Tup(_VSTD::get<_Idx>(_VSTD::move(__t))..., inner_allocator());
     }
 
     template <class...> friend class __scoped_allocator_storage;
 };
 
+#if _LIBCPP_STD_VER > 14
+template<class _OuterAlloc, class... _InnerAllocs>
+    scoped_allocator_adaptor(_OuterAlloc, _InnerAllocs...)
+        -> scoped_allocator_adaptor<_OuterAlloc, _InnerAllocs...>;
+#endif
+
 template <class _OuterA1, class _OuterA2>
 inline _LIBCPP_INLINE_VISIBILITY
 bool
 operator==(const scoped_allocator_adaptor<_OuterA1>& __a,
            const scoped_allocator_adaptor<_OuterA2>& __b) _NOEXCEPT
 {
     return __a.outer_allocator() == __b.outer_allocator();
 }

libcxx/include/utility

struct pair
     pair& operator=(pair&& p) noexcept(is_nothrow_move_assignable<T1>::value &&
                                        is_nothrow_move_assignable<T2>::value);   // constexpr in C++20
     template <class U, class V> pair& operator=(pair<U, V>&& p);                 // constexpr in C++20
 
     void swap(pair& p) noexcept(is_nothrow_swappable_v<T1> &&
                                 is_nothrow_swappable_v<T2>);                     // constexpr in C++20
 };
 
+template<class T1, class T2> pair(T1, T2) -> pair<T1, T2>;
+
 template <class T1, class T2> bool operator==(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14
 template <class T1, class T2> bool operator!=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14, removed in C++20
 template <class T1, class T2> bool operator< (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14, removed in C++20
 template <class T1, class T2> bool operator> (const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14, removed in C++20
 template <class T1, class T2> bool operator>=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14, removed in C++20
 template <class T1, class T2> bool operator<=(const pair<T1,T2>&, const pair<T1,T2>&); // constexpr in C++14, removed in C++20
 template <class T1, class T2>
   constexpr common_comparison_type_t<synth-three-way-result<T1>,

libcxx/include/valarray

public:
 
     valarray shift (int i) const;
     valarray cshift(int i) const;
     valarray apply(value_type f(value_type)) const;
     valarray apply(value_type f(const value_type&)) const;
     void resize(size_t n, value_type x = value_type());
 };
 
+template<class T, size_t cnt> valarray(const T(&)[cnt], size_t) -> valarray<T>;
+
 class slice
 {
 public:
     slice();
     slice(size_t start, size_t size, size_t stride);
 
     size_t start()  const;
     size_t size()   const;
private:
     const _Up*
     end(const valarray<_Up>& __v);
 
     _LIBCPP_INLINE_VISIBILITY
     void __clear(size_t __capacity);
     valarray& __assign_range(const value_type* __f, const value_type* __l);
 };
 
+#if _LIBCPP_STD_VER > 14
+template<class _Tp, size_t _Size>
+valarray(const _Tp(&)[_Size], size_t) -> valarray<_Tp>;
+#endif
+
 _LIBCPP_EXTERN_TEMPLATE(_LIBCPP_FUNC_VIS void valarray<size_t>::resize(size_t, size_t))
 
 template <class _Op, class _Tp>
 struct _UnaryOp<_Op, valarray<_Tp> >
 {
     typedef typename _Op::__result_type __result_type;
     typedef typename decay<__result_type>::type value_type;
 

libcxx/test/std/numerics/numarray/template.valarray/valarray.cons/deduct.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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, c++14
+
+// <valarray>
+
+// template<class T, size_t cnt> valarray(const T(&)[cnt], size_t) -> valarray<T>;
+
+#include <valarray>
+
+#include "test_macros.h"
+
+int main(int, char**)
+{
+    {
+        // From (initializer_list<T>)
+        std::valarray v = {1, 2, 3, 4, 5};
+        ASSERT_SAME_TYPE(decltype(v), std::valarray<int>);
+    }
+
+    {
+        // From (const T(&)[N], size_t)
+        long a[] = {1, 2, 3, 4, 5};
+        std::valarray v(a, 5);
+        ASSERT_SAME_TYPE(decltype(v), std::valarray<long>);
+    }
+
+    {
+        // From (const T&, size_t)
+        long a[] = {1, 2, 3, 4, 5};
+        std::valarray v(&a[0], 5);
+        // Surprising but true.
+        ASSERT_SAME_TYPE(decltype(v), std::valarray<long*>);
+    }
+
+    {
+        // From (slice_array<T>)
+        std::valarray<long> v{1,2,3,4,5};
+        std::valarray v2 = v[std::slice(2,3,1)];
+        static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
+    }
+
+    {
+        // From (gslice_array<T>)
+        std::valarray<long> v{1,2,3,4,5};
+        std::valarray v2 = v[std::gslice(0, {5}, {1})];
+        static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
+    }
+
+    {
+        // From (mask_array<T>)
+        std::valarray<long> v = {1, 2, 3, 4, 5};
+        std::valarray<bool> m = {true, false, true, false, true};
+        std::valarray v2 = v[m];
+        static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
+    }
+
+    {
+        // From (indirect_array<T>)
+        std::valarray<long> v = {1, 2, 3, 4, 5};
+        std::valarray<size_t> i = {1, 2, 3};
+        std::valarray v2 = v[i];
+        static_assert(std::is_same_v<decltype(v2), std::valarray<long>>);
+    }
+
+  return 0;
+}

libcxx/test/std/strings/basic.string/string.cons/iter_alloc_deduction.fail.cpp

 
 #include <string>
 #include <iterator>
 #include <cassert>
 #include <cstddef>
 
 #include "test_macros.h"
 
-class NotAnItertor {};
+class NotAnIterator {};
 
 template <typename T>
 struct NotAnAllocator { typedef T value_type; };
 
 int main(int, char**)
 {
     { // Not an iterator at all
-    std::basic_string s1{NotAnItertor{}, NotAnItertor{}, std::allocator<char>{}}; // expected-error {{no viable constructor or deduction guide for deduction of template arguments of 'basic_string'}}
+    std::basic_string s1{NotAnIterator{}, NotAnIterator{}, std::allocator<char>{}}; // expected-error {{no viable constructor or deduction guide for deduction of template arguments of 'basic_string'}}
     }
     { // Not an input iterator
     std::basic_string<char16_t> s0;
     std::basic_string s1{std::back_insert_iterator(s0), //  expected-error {{no viable constructor or deduction guide for deduction of template arguments of 'basic_string'}}
                          std::back_insert_iterator(s0),
                          std::allocator<char16_t>{}};
     }
     { // Not an allocator
     const wchar_t* s = L"12345678901234";
     (void)s;
     std::basic_string s1{s, s+10, NotAnAllocator<wchar_t>{}}; // expected-error {{no viable constructor or deduction guide for deduction of template arguments of 'basic_string'}}
     }
 
 
   return 0;
 }

libcxx/test/std/utilities/allocator.adaptor/allocator.adaptor.cnstr/allocs.pass.cpp

 //===----------------------------------------------------------------------===//
 //
 // 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
 
-// <memory>
+// <scoped_allocator>
 
 // template <class OuterAlloc, class... InnerAllocs>
 //   class scoped_allocator_adaptor
 
 // template <class OuterA2>
 //   scoped_allocator_adaptor(OuterA2&& outerAlloc,
 //                            const InnerAllocs& ...innerAllocs);
 

libcxx/test/std/utilities/allocator.adaptor/allocator.adaptor.cnstr/deduct.pass.cpp

+//===----------------------------------------------------------------------===//
+//
+// 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, c++14
+
+// <scoped_allocator>
+
+// template<class _OuterAlloc, class... _InnerAllocs>
+//     scoped_allocator_adaptor(_OuterAlloc, _InnerAllocs...)
+//         -> scoped_allocator_adaptor<_OuterAlloc, _InnerAllocs...>;
+
+#include <scoped_allocator>
+
+#include "test_macros.h"
+#include "allocators.h"
+
+int main(int, char**)
+{
+    // Deduct from (const OuterAlloc&).
+    {
+        typedef A1<int> OuterAlloc;
+        OuterAlloc outer(3);
+        std::scoped_allocator_adaptor a(outer);
+        ASSERT_SAME_TYPE(decltype(a), std::scoped_allocator_adaptor<OuterAlloc>);
+    }
+
+    // Deduct from (OuterAlloc&&).
+    {
+        typedef A1<int> OuterAlloc;
+        std::scoped_allocator_adaptor a(OuterAlloc(3));
+        ASSERT_SAME_TYPE(decltype(a), std::scoped_allocator_adaptor<OuterAlloc>);
+    }
+
+    // Deduct from (const OuterAlloc&, const InnerAlloc&).
+    {
+        typedef A1<int> OuterAlloc;
+        typedef A2<int> InnerAlloc;
+        OuterAlloc outer(3);
+        InnerAlloc inner(4);
+
+        std::scoped_allocator_adaptor a(outer, inner);
+        ASSERT_SAME_TYPE(decltype(a), std::scoped_allocator_adaptor<OuterAlloc, InnerAlloc>);
+    }
+
+    // Deduct from (const OuterAlloc&, const InnerAlloc1&, InnerAlloc2&&).
+    {
+        typedef A1<int> OuterAlloc;
+        typedef A2<int> InnerAlloc1;
+        typedef A2<float> InnerAlloc2;
+        OuterAlloc outer(3);
+        InnerAlloc1 inner(4);
+
+        std::scoped_allocator_adaptor a(outer, inner, InnerAlloc2(5));
+        ASSERT_SAME_TYPE(
+            decltype(a), std::scoped_allocator_adaptor<OuterAlloc, InnerAlloc1, InnerAlloc2>);
+    }
+
+  return 0;
+}

libcxx/test/std/utilities/optional/optional.object/optional.object.ctor/deduct.pass.cpp

 struct A {};
 
 int main(int, char**)
 {
 //  Test the explicit deduction guides
     {
 //  optional(T)
     std::optional opt(5);
-    static_assert(std::is_same_v<decltype(opt), std::optional<int>>, "");
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<int>);
     assert(static_cast<bool>(opt));
     assert(*opt == 5);
     }
 
     {
 //  optional(T)
     std::optional opt(A{});
-    static_assert(std::is_same_v<decltype(opt), std::optional<A>>, "");
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<A>);
     assert(static_cast<bool>(opt));
     }
 
+    {
+//  optional(const T&);
+    const int& source = 5;
+    std::optional opt(source);
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<int>);
+    assert(static_cast<bool>(opt));
+    assert(*opt == 5);
+    }
+
+    {
+//  optional(T*);
+    const int* source = nullptr;
+    std::optional opt(source);
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<const int*>);
+    assert(static_cast<bool>(opt));
+    assert(*opt == nullptr);
+    }
+
+    {
+//  optional(T[]);
+    int source[] = {1, 2, 3};
+    std::optional opt(source);
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<int*>);
+    assert(static_cast<bool>(opt));
+    assert((*opt)[0] == 1);
+    }
+
 //  Test the implicit deduction guides
     {
 //  optional(optional);
     std::optional<char> source('A');
     std::optional opt(source);
-    static_assert(std::is_same_v<decltype(opt), std::optional<char>>, "");
+    ASSERT_SAME_TYPE(decltype(opt), std::optional<char>);
     assert(static_cast<bool>(opt) == static_cast<bool>(source));
     assert(*opt == *source);
     }
 
   return 0;
 }