diff options
author | varconst <varconsteq@gmail.com> | 2023-05-08 23:40:21 -0700 |
---|---|---|
committer | Konstantin Varlamov <varconst@apple.com> | 2023-05-08 23:40:55 -0700 |
commit | 17bbb224f99cf6fde83aa68e2e22e70fe9ed77be (patch) | |
tree | 1208519e55b83c22ce35be88a5b066977f3818c0 /libcxx | |
parent | c60461e3f8154ade8e542e64d1711f975adac8d0 (diff) | |
download | llvm-17bbb224f99cf6fde83aa68e2e22e70fe9ed77be.tar.gz |
[libc++][ranges] Implement the changes to vector from P1206 (`ranges::to`):
- add the `from_range_t` constructors and the related deduction guides;
- add the `insert_range`/`assign_range`/etc. member functions.
(Note: this patch is split from https://reviews.llvm.org/D142335)
Differential Revision: https://reviews.llvm.org/D149826
Diffstat (limited to 'libcxx')
25 files changed, 2347 insertions, 196 deletions
diff --git a/libcxx/docs/Status/Cxx2bPapers.csv b/libcxx/docs/Status/Cxx2bPapers.csv index c5b99c113d88..a310cfc5ff16 100644 --- a/libcxx/docs/Status/Cxx2bPapers.csv +++ b/libcxx/docs/Status/Cxx2bPapers.csv @@ -41,7 +41,7 @@ "`P0323R12 <https://wg21.link/P0323R12>`__","LWG","``std::expected``","February 2022","|Complete|","16.0" "`P0533R9 <https://wg21.link/P0533R9>`__","LWG","``constexpr`` for ``<cmath>`` and ``<cstdlib>``","February 2022","|In progress| [#note-P0533R9]_","" "`P0627R6 <https://wg21.link/P0627R6>`__","LWG","Function to mark unreachable code","February 2022","|Complete|","15.0" -"`P1206R7 <https://wg21.link/P1206R7>`__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","","","|ranges|" +"`P1206R7 <https://wg21.link/P1206R7>`__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","|In Progress|","","|ranges|" "`P1413R3 <https://wg21.link/P1413R3>`__","LWG","Deprecate ``std::aligned_storage`` and ``std::aligned_union``","February 2022","|Complete| [#note-P1413R3]_","" "`P2255R2 <https://wg21.link/P2255R2>`__","LWG","A type trait to detect reference binding to temporary","February 2022","","" "`P2273R3 <https://wg21.link/P2273R3>`__","LWG","Making ``std::unique_ptr`` constexpr","February 2022","|Complete|","16.0" diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt index f42c82c3ab14..4929501a700c 100644 --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -581,6 +581,7 @@ set(files __ranges/as_rvalue_view.h __ranges/common_view.h __ranges/concepts.h + __ranges/container_compatible_range.h __ranges/copyable_box.h __ranges/counted.h __ranges/dangling.h @@ -593,6 +594,7 @@ set(files __ranges/enable_borrowed_range.h __ranges/enable_view.h __ranges/filter_view.h + __ranges/from_range.h __ranges/iota_view.h __ranges/istream_view.h __ranges/join_view.h diff --git a/libcxx/include/__ranges/container_compatible_range.h b/libcxx/include/__ranges/container_compatible_range.h new file mode 100644 index 000000000000..a58f1119885e --- /dev/null +++ b/libcxx/include/__ranges/container_compatible_range.h @@ -0,0 +1,33 @@ +// -*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___RANGES_CONTAINER_COMPATIBLE_RANGE_H +#define _LIBCPP___RANGES_CONTAINER_COMPATIBLE_RANGE_H + +#include <__concepts/convertible_to.h> +#include <__config> +#include <__ranges/concepts.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +template <class _Range, class _Tp> +concept _ContainerCompatibleRange = + ranges::input_range<_Range> && convertible_to<ranges::range_reference_t<_Range>, _Tp>; + +#endif // _LIBCPP_STD_VER >= 23 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___RANGES_CONTAINER_COMPATIBLE_RANGE_H diff --git a/libcxx/include/__ranges/from_range.h b/libcxx/include/__ranges/from_range.h new file mode 100644 index 000000000000..a6cb9e3d439e --- /dev/null +++ b/libcxx/include/__ranges/from_range.h @@ -0,0 +1,33 @@ +// -*- 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 +// +//===----------------------------------------------------------------------===// + +#ifndef _LIBCPP___RANGES_FROM_RANGE_H +#define _LIBCPP___RANGES_FROM_RANGE_H + +#include <__config> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +struct from_range_t { + explicit from_range_t() = default; +}; + +inline constexpr from_range_t from_range{}; + +#endif // _LIBCPP_STD_VER >= 23 + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___RANGES_FROM_RANGE_H diff --git a/libcxx/include/__split_buffer b/libcxx/include/__split_buffer index c4f1315ee5bf..5efc443a4b34 100644 --- a/libcxx/include/__split_buffer +++ b/libcxx/include/__split_buffer @@ -170,6 +170,14 @@ public: __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value> __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); + template <class _Iterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last); + + template <class _Iterator> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __construct_at_end_with_size(_Iterator __first, size_type __n); + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __destruct_at_begin(pointer __new_begin) { __destruct_at_begin(__new_begin, is_trivially_destructible<value_type>()); } @@ -279,6 +287,13 @@ template <class _InputIter> _LIBCPP_CONSTEXPR_SINCE_CXX20 __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIter>::value> __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIter __last) { + __construct_at_end_with_sentinel(__first, __last); +} + +template <class _Tp, class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 +void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_sentinel(_Iterator __first, _Sentinel __last) { __alloc_rr& __a = this->__alloc(); for (; __first != __last; ++__first) { @@ -296,13 +311,19 @@ __split_buffer<_Tp, _Allocator>::__construct_at_end(_InputIter __first, _InputIt ++this->__end_; } } - template <class _Tp, class _Allocator> template <class _ForwardIterator> _LIBCPP_CONSTEXPR_SINCE_CXX20 __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value> __split_buffer<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) { - _ConstructTransaction __tx(&this->__end_, _VSTD::distance(__first, __last)); + __construct_at_end_with_size(__first, std::distance(__first, __last)); +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator> +_LIBCPP_CONSTEXPR_SINCE_CXX20 +void __split_buffer<_Tp, _Allocator>::__construct_at_end_with_size(_ForwardIterator __first, size_type __n) { + _ConstructTransaction __tx(&this->__end_, __n); for (; __tx.__pos_ != __tx.__end_; ++__tx.__pos_, (void) ++__first) { __alloc_traits::construct(this->__alloc(), _VSTD::__to_address(__tx.__pos_), *__first); diff --git a/libcxx/include/module.modulemap.in b/libcxx/include/module.modulemap.in index 3f96e685bdc9..6b7bba1d1d41 100644 --- a/libcxx/include/module.modulemap.in +++ b/libcxx/include/module.modulemap.in @@ -1309,62 +1309,64 @@ module std [system] { export * module __ranges { - module access { private header "__ranges/access.h" } - module all { + module access { private header "__ranges/access.h" } + module all { private header "__ranges/all.h" export functional.__functional.compose export functional.__functional.perfect_forward } - module as_rvalue_view { private header "__ranges/as_rvalue_view.h" } - module common_view { private header "__ranges/common_view.h" } - module concepts { private header "__ranges/concepts.h" } - module copyable_box { private header "__ranges/copyable_box.h" } - module counted { + module as_rvalue_view { private header "__ranges/as_rvalue_view.h" } + module common_view { private header "__ranges/common_view.h" } + module concepts { private header "__ranges/concepts.h" } + module container_compatible_range { private header "__ranges/container_compatible_range.h" } + module copyable_box { private header "__ranges/copyable_box.h" } + module counted { private header "__ranges/counted.h" export span } - module dangling { private header "__ranges/dangling.h" } - module data { private header "__ranges/data.h" } - module drop_view { private header "__ranges/drop_view.h" } - module drop_while_view { private header "__ranges/drop_while_view.h" } - module elements_view { private header "__ranges/elements_view.h" } - module empty { private header "__ranges/empty.h" } - module empty_view { private header "__ranges/empty_view.h" } - module enable_borrowed_range { private header "__ranges/enable_borrowed_range.h" } - module enable_view { private header "__ranges/enable_view.h" } - module filter_view { private header "__ranges/filter_view.h" } - module iota_view { private header "__ranges/iota_view.h" } - module istream_view { + module dangling { private header "__ranges/dangling.h" } + module data { private header "__ranges/data.h" } + module drop_view { private header "__ranges/drop_view.h" } + module drop_while_view { private header "__ranges/drop_while_view.h" } + module elements_view { private header "__ranges/elements_view.h" } + module empty { private header "__ranges/empty.h" } + module empty_view { private header "__ranges/empty_view.h" } + module enable_borrowed_range { private header "__ranges/enable_borrowed_range.h" } + module enable_view { private header "__ranges/enable_view.h" } + module filter_view { private header "__ranges/filter_view.h" } + module from_range { private header "__ranges/from_range.h" } + module iota_view { private header "__ranges/iota_view.h" } + module istream_view { @requires_LIBCXX_ENABLE_LOCALIZATION@ private header "__ranges/istream_view.h" } - module join_view { private header "__ranges/join_view.h" } - module lazy_split_view { private header "__ranges/lazy_split_view.h" } - module non_propagating_cache { private header "__ranges/non_propagating_cache.h" } - module owning_view { private header "__ranges/owning_view.h" } - module range_adaptor { private header "__ranges/range_adaptor.h" } - module rbegin { private header "__ranges/rbegin.h" } - module ref_view { private header "__ranges/ref_view.h" } - module rend { private header "__ranges/rend.h" } - module reverse_view { private header "__ranges/reverse_view.h" } - module single_view { private header "__ranges/single_view.h" } - module size { private header "__ranges/size.h" } - module split_view { private header "__ranges/split_view.h" } - module subrange { + module join_view { private header "__ranges/join_view.h" } + module lazy_split_view { private header "__ranges/lazy_split_view.h" } + module non_propagating_cache { private header "__ranges/non_propagating_cache.h" } + module owning_view { private header "__ranges/owning_view.h" } + module range_adaptor { private header "__ranges/range_adaptor.h" } + module rbegin { private header "__ranges/rbegin.h" } + module ref_view { private header "__ranges/ref_view.h" } + module rend { private header "__ranges/rend.h" } + module reverse_view { private header "__ranges/reverse_view.h" } + module single_view { private header "__ranges/single_view.h" } + module size { private header "__ranges/size.h" } + module split_view { private header "__ranges/split_view.h" } + module subrange { private header "__ranges/subrange.h" export subrange_fwd } - module subrange_fwd { private header "__fwd/subrange.h" } - module take_view { private header "__ranges/take_view.h" } - module take_while_view { private header "__ranges/take_while_view.h" } - module transform_view { + module subrange_fwd { private header "__fwd/subrange.h" } + module take_view { private header "__ranges/take_view.h" } + module take_while_view { private header "__ranges/take_while_view.h" } + module transform_view { private header "__ranges/transform_view.h" export functional.__functional.bind_back export functional.__functional.perfect_forward } - module view_interface { private header "__ranges/view_interface.h" } - module views { private header "__ranges/views.h" } - module zip_view { private header "__ranges/zip_view.h" } + module view_interface { private header "__ranges/view_interface.h" } + module views { private header "__ranges/views.h" } + module zip_view { private header "__ranges/zip_view.h" } } } module ratio { diff --git a/libcxx/include/ranges b/libcxx/include/ranges index 8f3b4b21f622..38da82dc7581 100644 --- a/libcxx/include/ranges +++ b/libcxx/include/ranges @@ -339,6 +339,9 @@ namespace std { struct tuple_element<1, const ranges::subrange<I, S, K>> { using type = S; }; + + struct from_range_t { explicit from_range_t() = default; }; // Since C++23 + inline constexpr from_range_t from_range{}; // Since C++23 } */ @@ -360,6 +363,7 @@ namespace std { #include <__ranges/enable_borrowed_range.h> #include <__ranges/enable_view.h> #include <__ranges/filter_view.h> +#include <__ranges/from_range.h> #include <__ranges/iota_view.h> #include <__ranges/join_view.h> #include <__ranges/lazy_split_view.h> diff --git a/libcxx/include/vector b/libcxx/include/vector index a1366d0a9c2d..374a47c7173c 100644 --- a/libcxx/include/vector +++ b/libcxx/include/vector @@ -41,6 +41,8 @@ public: vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); template <class InputIterator> vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); + template<container-compatible-range<T> R> + constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 vector(const vector& x); vector(vector&& x) noexcept(is_nothrow_move_constructible<allocator_type>::value); @@ -55,6 +57,8 @@ public: vector& operator=(initializer_list<value_type> il); template <class InputIterator> void assign(InputIterator first, InputIterator last); + template<container-compatible-range<T> R> + constexpr void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& u); void assign(initializer_list<value_type> il); @@ -99,6 +103,8 @@ public: void push_back(value_type&& x); template <class... Args> reference emplace_back(Args&&... args); // reference in C++17 + template<container-compatible-range<T> R> + constexpr void append_range(R&& rg); // C++23 void pop_back(); template <class... Args> iterator emplace(const_iterator position, Args&&... args); @@ -107,6 +113,8 @@ public: iterator insert(const_iterator position, size_type n, const value_type& x); template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last); + template<container-compatible-range<T> R> + constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator position, initializer_list<value_type> il); iterator erase(const_iterator position); @@ -165,6 +173,8 @@ public: vector(size_type n, const value_type& value, const allocator_type& = allocator_type()); template <class InputIterator> vector(InputIterator first, InputIterator last, const allocator_type& = allocator_type()); + template<container-compatible-range<bool> R> + constexpr vector(from_range_t, R&& rg, const Allocator& = Allocator()); vector(const vector& x); vector(vector&& x) noexcept(is_nothrow_move_constructible<allocator_type>::value); @@ -179,6 +189,8 @@ public: vector& operator=(initializer_list<value_type> il); template <class InputIterator> void assign(InputIterator first, InputIterator last); + template<container-compatible-range<T> R> + constexpr void assign_range(R&& rg); // C++23 void assign(size_type n, const value_type& u); void assign(initializer_list<value_type> il); @@ -218,6 +230,8 @@ public: void push_back(const value_type& x); template <class... Args> reference emplace_back(Args&&... args); // C++14; reference in C++17 + template<container-compatible-range<T> R> + constexpr void append_range(R&& rg); // C++23 void pop_back(); template <class... Args> iterator emplace(const_iterator position, Args&&... args); // C++14 @@ -225,6 +239,8 @@ public: iterator insert(const_iterator position, size_type n, const value_type& x); template <class InputIterator> iterator insert(const_iterator position, InputIterator first, InputIterator last); + template<container-compatible-range<T> R> + constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 iterator insert(const_iterator position, initializer_list<value_type> il); iterator erase(const_iterator position); @@ -247,6 +263,10 @@ template <class InputIterator, class Allocator = allocator<typename iterator_tra vector(InputIterator, InputIterator, Allocator = Allocator()) -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // C++17 +template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> + vector(from_range_t, R&&, Allocator = Allocator()) + -> vector<ranges::range_value_t<R>, Allocator>; // C++23 + template <class Allocator> struct hash<std::vector<bool, Allocator>>; template <class T, class Allocator> bool operator==(const vector<T,Allocator>& x, const vector<T,Allocator>& y); @@ -281,6 +301,7 @@ template<class T, class charT> requires is-vector-bool-reference<T> // Since C++ #include <__algorithm/copy.h> #include <__algorithm/equal.h> #include <__algorithm/fill_n.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/lexicographical_compare.h> #include <__algorithm/remove.h> #include <__algorithm/remove_if.h> @@ -297,6 +318,7 @@ template<class T, class charT> requires is-vector-bool-reference<T> // Since C++ #include <__functional/hash.h> #include <__functional/unary_function.h> #include <__iterator/advance.h> +#include <__iterator/distance.h> #include <__iterator/iterator_traits.h> #include <__iterator/reverse_iterator.h> #include <__iterator/wrap_iter.h> @@ -308,6 +330,11 @@ template<class T, class charT> requires is-vector-bool-reference<T> // Since C++ #include <__memory/temp_value.h> #include <__memory/uninitialized_algorithms.h> #include <__memory_resource/polymorphic_allocator.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/container_compatible_range.h> +#include <__ranges/from_range.h> +#include <__ranges/size.h> #include <__split_buffer> #include <__type_traits/is_allocator.h> #include <__type_traits/is_constructible.h> @@ -317,6 +344,7 @@ template<class T, class charT> requires is-vector-bool-reference<T> // Since C++ #include <__utility/exception_guard.h> #include <__utility/forward.h> #include <__utility/move.h> +#include <__utility/pair.h> #include <__utility/swap.h> #include <climits> #include <cstring> @@ -345,7 +373,6 @@ template<class T, class charT> requires is-vector-bool-reference<T> // Since C++ _LIBCPP_PUSH_MACROS #include <__undef_macros> - _LIBCPP_BEGIN_NAMESPACE_STD template <class _Tp, class _Allocator /* = allocator<_Tp> */> @@ -437,6 +464,20 @@ public: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI constexpr vector(from_range_t, _Range&& __range, + const allocator_type& __alloc = allocator_type()) : __end_cap_(nullptr, __alloc) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + __init_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __init_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + private: class __destroy_vector { public: @@ -502,6 +543,20 @@ public: int> = 0> _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void assign(size_type __n, const_reference __u); #ifndef _LIBCPP_CXX03_LANG @@ -604,6 +659,14 @@ public: void emplace_back(_Args&&... __args); #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void pop_back(); @@ -623,6 +686,20 @@ public: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI iterator insert(const_iterator __position, _InputIterator __first, _InputIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<_Tp> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +#endif + template < class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value && @@ -702,9 +779,51 @@ private: _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __construct_at_end(size_type __n, const_reference __x); - template <class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value, int> = 0> - _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void - __construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n); + template <class _InputIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) { + auto __guard = std::__make_exception_guard(__destroy_vector(*this)); + std::__debug_db_insert_c(this); + + if (__n > 0) { + __vallocate(__n); + __construct_at_end(__first, __last, __n); + } + + __guard.__complete(); + } + + template <class _InputIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __init_with_sentinel(_InputIterator __first, _Sentinel __last) { + auto __guard = std::__make_exception_guard(__destroy_vector(*this)); + std::__debug_db_insert_c(this); + + for (; __first != __last; ++__first) + emplace_back(*__first); + + __guard.__complete(); + } + + template <class _Iterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __first, _Sentinel __last); + + template <class _ForwardIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n); + + template <class _InputIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); + + template <class _Iterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); + + template <class _InputIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n); _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI void __append(size_type __n, const_reference __x); @@ -911,6 +1030,15 @@ vector(_InputIterator, _InputIterator, _Alloc) -> vector<__iter_value_type<_InputIterator>, _Alloc>; #endif +#if _LIBCPP_STD_VER >= 23 +template <ranges::input_range _Range, + class _Alloc = allocator<ranges::range_value_t<_Range>>, + class = enable_if_t<__is_allocator<_Alloc>::value> + > +vector(from_range_t, _Range&&, _Alloc = _Alloc()) + -> vector<ranges::range_value_t<_Range>, _Alloc>; +#endif + template <class _Tp, class _Allocator> _LIBCPP_CONSTEXPR_SINCE_CXX20 void @@ -1026,10 +1154,9 @@ vector<_Tp, _Allocator>::__construct_at_end(size_type __n, const_reference __x) } template <class _Tp, class _Allocator> -template <class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_ForwardIterator>::value, int> > +template <class _InputIterator, class _Sentinel> _LIBCPP_CONSTEXPR_SINCE_CXX20 void -vector<_Tp, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last, size_type __n) -{ +vector<_Tp, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) { _ConstructTransaction __tx(*this, __n); __tx.__pos_ = std::__uninitialized_allocator_copy(__alloc(), __first, __last, __tx.__pos_); } @@ -1126,11 +1253,7 @@ template <class _InputIterator, __enable_if_t<__is_exactly_cpp17_input_iterator< _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - for (; __first != __last; ++__first) - emplace_back(*__first); - __guard.__complete(); + __init_with_sentinel(__first, __last); } template <class _Tp, class _Allocator> @@ -1141,11 +1264,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_InputIterator __first, _InputIterator __last, const allocator_type& __a) : __end_cap_(nullptr, __a) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - for (; __first != __last; ++__first) - emplace_back(*__first); - __guard.__complete(); + __init_with_sentinel(__first, __last); } template <class _Tp, class _Allocator> @@ -1155,15 +1274,8 @@ template <class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_For _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - size_type __n = static_cast<size_type>(std::distance(__first, __last)); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__first, __last, __n); - } - __guard.__complete(); + size_type __n = static_cast<size_type>(std::distance(__first, __last)); + __init_with_size(__first, __last, __n); } template <class _Tp, class _Allocator> @@ -1174,15 +1286,8 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a) : __end_cap_(nullptr, __a) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - size_type __n = static_cast<size_type>(std::distance(__first, __last)); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__first, __last, __n); - } - __guard.__complete(); + size_type __n = static_cast<size_type>(std::distance(__first, __last)); + __init_with_size(__first, __last, __n); } template <class _Tp, class _Allocator> @@ -1190,15 +1295,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(const vector& __x) : __end_cap_(nullptr, __alloc_traits::select_on_container_copy_construction(__x.__alloc())) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - size_type __n = __x.size(); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__x.__begin_, __x.__end_, __n); - } - __guard.__complete(); + __init_with_size(__x.__begin_, __x.__end_, __x.size()); } template <class _Tp, class _Allocator> @@ -1206,15 +1303,7 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 vector<_Tp, _Allocator>::vector(const vector& __x, const __type_identity_t<allocator_type>& __a) : __end_cap_(nullptr, __a) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - std::__debug_db_insert_c(this); - size_type __n = __x.size(); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__x.__begin_, __x.__end_, __n); - } - __guard.__complete(); + __init_with_size(__x.__begin_, __x.__end_, __x.size()); } template <class _Tp, class _Allocator> @@ -1358,6 +1447,13 @@ template <class _InputIterator, __enable_if_t<__is_exactly_cpp17_input_iterator< _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { + __assign_with_sentinel(__first, __last); +} + +template <class _Tp, class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<_Tp, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { clear(); for (; __first != __last; ++__first) emplace_back(*__first); @@ -1370,22 +1466,27 @@ template <class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_For _LIBCPP_CONSTEXPR_SINCE_CXX20 void vector<_Tp, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { - size_type __new_size = static_cast<size_type>(std::distance(__first, __last)); + __assign_with_size(__first, __last, std::distance(__first, __last)); +} + +template <class _Tp, class _Allocator> +template <class _ForwardIterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<_Tp, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __n) { + size_type __new_size = static_cast<size_type>(__n); if (__new_size <= capacity()) { - _ForwardIterator __mid = __last; - bool __growing = false; if (__new_size > size()) { - __growing = true; - __mid = __first; - std::advance(__mid, size()); - } - pointer __m = std::copy(__first, __mid, this->__begin_); - if (__growing) + _ForwardIterator __mid = std::next(__first, size()); + std::copy(__first, __mid, this->__begin_); __construct_at_end(__mid, __last, __new_size - size()); + } else + { + pointer __m = std::__copy<_ClassicAlgPolicy>(__first, __last, this->__begin_).second; this->__destruct_at_end(__m); + } } else { @@ -1815,7 +1916,6 @@ vector<_Tp, _Allocator>::insert(const_iterator __position, size_type __n, const_ } return __make_iter(__p); } - template <class _Tp, class _Allocator> template <class _InputIterator, __enable_if_t<__is_exactly_cpp17_input_iterator<_InputIterator>::value && is_constructible<_Tp, typename iterator_traits<_InputIterator>::reference>::value, @@ -1823,8 +1923,17 @@ template <class _InputIterator, __enable_if_t<__is_exactly_cpp17_input_iterator< _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { - _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, - "vector::insert(iterator, range) called with an iterator not referring to this vector"); + return __insert_with_sentinel(__position, __first, __last); +} + +template <class _Tp, class _Allocator> +template <class _InputIterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<_Tp, _Allocator>::iterator +vector<_Tp, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { + _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, + "vector::insert called with an iterator not referring to this vector"); + difference_type __off = __position - begin(); pointer __p = this->__begin_ + __off; allocator_type& __a = this->__alloc(); @@ -1840,7 +1949,7 @@ vector<_Tp, _Allocator>::insert(const_iterator __position, _InputIterator __firs try { #endif // _LIBCPP_HAS_NO_EXCEPTIONS - __v.__construct_at_end(__first, __last); + __v.__construct_at_end_with_sentinel(std::move(__first), std::move(__last)); difference_type __old_size = __old_last - this->__begin_; difference_type __old_p = __p - this->__begin_; reserve(__recommend(size() + __v.size())); @@ -1868,17 +1977,27 @@ template <class _ForwardIterator, __enable_if_t<__is_cpp17_forward_iterator<_For _LIBCPP_CONSTEXPR_SINCE_CXX20 typename vector<_Tp, _Allocator>::iterator vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { + return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); +} + +template <class _Tp, class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<_Tp, _Allocator>::iterator +vector<_Tp, _Allocator>::__insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, + difference_type __n) { _LIBCPP_DEBUG_ASSERT(__get_const_db()->__find_c_from_i(std::addressof(__position)) == this, - "vector::insert(iterator, range) called with an iterator not referring to this vector"); + "vector::insert called with an iterator not referring to this vector"); + + auto __insertion_size = __n; pointer __p = this->__begin_ + (__position - begin()); - difference_type __n = std::distance(__first, __last); if (__n > 0) { if (__n <= this->__end_cap() - this->__end_) { size_type __old_n = __n; pointer __old_last = this->__end_; - _ForwardIterator __m = __last; + _Iterator __m = std::next(__first, __n); difference_type __dx = this->__end_ - __p; if (__n > __dx) { @@ -1898,7 +2017,7 @@ vector<_Tp, _Allocator>::insert(const_iterator __position, _ForwardIterator __fi { allocator_type& __a = this->__alloc(); __split_buffer<value_type, allocator_type&> __v(__recommend(size() + __n), __p - this->__begin_, __a); - __v.__construct_at_end(__first, __last); + __v.__construct_at_end_with_size(__first, __insertion_size); __p = __swap_out_circular_buffer(__v, __p); } } @@ -2146,6 +2265,23 @@ public: _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(_ForwardIterator __first, _ForwardIterator __last, const allocator_type& __a, typename enable_if<__is_cpp17_forward_iterator<_ForwardIterator>::value>::type* = 0); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<bool> _Range> + _LIBCPP_HIDE_FROM_ABI constexpr + vector(from_range_t, _Range&& __range, const allocator_type& __a = allocator_type()) + : __begin_(nullptr), + __size_(0), + __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + __init_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __init_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v); _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector(const vector& __v, const allocator_type& __a); _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 vector& operator=(const vector& __v); @@ -2185,6 +2321,20 @@ public: >::type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 assign(_ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<bool> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void assign_range(_Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + __assign_with_size(ranges::begin(__range), ranges::end(__range), __n); + + } else { + __assign_with_sentinel(ranges::begin(__range), ranges::end(__range)); + } + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void assign(size_type __n, const value_type& __x); #ifndef _LIBCPP_CXX03_LANG @@ -2274,6 +2424,14 @@ public: } #endif +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<bool> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr void append_range(_Range&& __range) { + insert_range(end(), std::forward<_Range>(__range)); + } +#endif + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void pop_back() {--__size_;} #if _LIBCPP_STD_VER >= 14 @@ -2297,6 +2455,20 @@ public: >::type _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last); +#if _LIBCPP_STD_VER >= 23 + template <_ContainerCompatibleRange<bool> _Range> + _LIBCPP_HIDE_FROM_ABI + constexpr iterator insert_range(const_iterator __position, _Range&& __range) { + if constexpr (ranges::forward_range<_Range> || ranges::sized_range<_Range>) { + auto __n = static_cast<size_type>(ranges::distance(__range)); + return __insert_with_size(__position, ranges::begin(__range), ranges::end(__range), __n); + + } else { + return __insert_with_sentinel(__position, ranges::begin(__range), ranges::end(__range)); + } + } +#endif + #ifndef _LIBCPP_CXX03_LANG _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 iterator insert(const_iterator __position, initializer_list<value_type> __il) @@ -2334,6 +2506,53 @@ private: std::__throw_out_of_range("vector"); } + template <class _InputIterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 + void __init_with_size(_InputIterator __first, _Sentinel __last, size_type __n) { + auto __guard = std::__make_exception_guard(__destroy_vector(*this)); + + if (__n > 0) { + __vallocate(__n); + __construct_at_end(std::move(__first), std::move(__last), __n); + } + + __guard.__complete(); + } + + template <class _InputIterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 + void __init_with_sentinel(_InputIterator __first, _Sentinel __last) { +#ifndef _LIBCPP_HAS_NO_EXCEPTIONS + try { +#endif // _LIBCPP_HAS_NO_EXCEPTIONS + for (; __first != __last; ++__first) + push_back(*__first); +#ifndef _LIBCPP_HAS_NO_EXCEPTIONS + } catch (...) { + if (__begin_ != nullptr) + __storage_traits::deallocate(__alloc(), __begin_, __cap()); + std::__debug_db_invalidate_all(this); + throw; + } +#endif // _LIBCPP_HAS_NO_EXCEPTIONS + } + + template <class _Iterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_sentinel(_Iterator __first, _Sentinel __last); + + template <class _ForwardIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + void __assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns); + + template <class _InputIterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last); + + template <class _Iterator, class _Sentinel> + _LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI + iterator __insert_with_size(const_iterator __position, _Iterator __first, _Sentinel __last, difference_type __n); + // Allocate space for __n objects // throws length_error if __n > max_size() // throws (probably bad_alloc) if memory run out @@ -2360,13 +2579,9 @@ private: {return (__new_size + (__bits_per_word-1)) & ~((size_type)__bits_per_word-1);} _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 size_type __recommend(size_type __new_size) const; _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __construct_at_end(size_type __n, bool __x); - template <class _ForwardIterator> - typename enable_if - < - __is_cpp17_forward_iterator<_ForwardIterator>::value, - void - >::type - _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 __construct_at_end(_ForwardIterator __first, _ForwardIterator __last); + template <class _InputIterator, class _Sentinel> + _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 + void __construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n); _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 void __append(size_type __n, const_reference __x); _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 reference __make_ref(size_type __pos) _NOEXCEPT @@ -2496,17 +2711,11 @@ vector<bool, _Allocator>::__construct_at_end(size_type __n, bool __x) } template <class _Allocator> -template <class _ForwardIterator> +template <class _InputIterator, class _Sentinel> _LIBCPP_CONSTEXPR_SINCE_CXX20 -typename enable_if -< - __is_cpp17_forward_iterator<_ForwardIterator>::value, - void ->::type -vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardIterator __last) -{ +void vector<bool, _Allocator>::__construct_at_end(_InputIterator __first, _Sentinel __last, size_type __n) { size_type __old_size = this->__size_; - this->__size_ += std::distance(__first, __last); + this->__size_ += __n; if (__old_size == 0 || ((__old_size - 1) / __bits_per_word) != ((this->__size_ - 1) / __bits_per_word)) { if (this->__size_ <= __bits_per_word) @@ -2514,7 +2723,7 @@ vector<bool, _Allocator>::__construct_at_end(_ForwardIterator __first, _ForwardI else this->__begin_[(this->__size_ - 1) / __bits_per_word] = __storage_type(0); } - std::copy(__first, __last, __make_iter(__old_size)); + std::__copy<_ClassicAlgPolicy>(__first, __last, __make_iter(__old_size)); } template <class _Allocator> @@ -2608,22 +2817,7 @@ vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, __size_(0), __cap_alloc_(0, __default_init_tag()) { -#ifndef _LIBCPP_HAS_NO_EXCEPTIONS - try - { -#endif // _LIBCPP_HAS_NO_EXCEPTIONS - for (; __first != __last; ++__first) - push_back(*__first); -#ifndef _LIBCPP_HAS_NO_EXCEPTIONS - } - catch (...) - { - if (__begin_ != nullptr) - __storage_traits::deallocate(__alloc(), __begin_, __cap()); - std::__debug_db_invalidate_all(this); - throw; - } -#endif // _LIBCPP_HAS_NO_EXCEPTIONS + __init_with_sentinel(__first, __last); } template <class _Allocator> @@ -2635,22 +2829,7 @@ vector<bool, _Allocator>::vector(_InputIterator __first, _InputIterator __last, __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { -#ifndef _LIBCPP_HAS_NO_EXCEPTIONS - try - { -#endif // _LIBCPP_HAS_NO_EXCEPTIONS - for (; __first != __last; ++__first) - push_back(*__first); -#ifndef _LIBCPP_HAS_NO_EXCEPTIONS - } - catch (...) - { - if (__begin_ != nullptr) - __storage_traits::deallocate(__alloc(), __begin_, __cap()); - std::__debug_db_invalidate_all(this); - throw; - } -#endif // _LIBCPP_HAS_NO_EXCEPTIONS + __init_with_sentinel(__first, __last); } template <class _Allocator> @@ -2662,14 +2841,8 @@ vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __la __size_(0), __cap_alloc_(0, __default_init_tag()) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - size_type __n = static_cast<size_type>(std::distance(__first, __last)); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__first, __last); - } - __guard.__complete(); + auto __n = static_cast<size_type>(std::distance(__first, __last)); + __init_with_size(__first, __last, __n); } template <class _Allocator> @@ -2681,14 +2854,8 @@ vector<bool, _Allocator>::vector(_ForwardIterator __first, _ForwardIterator __la __size_(0), __cap_alloc_(0, static_cast<__storage_allocator>(__a)) { - auto __guard = std::__make_exception_guard(__destroy_vector(*this)); - size_type __n = static_cast<size_type>(std::distance(__first, __last)); - if (__n > 0) - { - __vallocate(__n); - __construct_at_end(__first, __last); - } - __guard.__complete(); + auto __n = static_cast<size_type>(std::distance(__first, __last)); + __init_with_size(__first, __last, __n); } #ifndef _LIBCPP_CXX03_LANG @@ -2704,7 +2871,7 @@ vector<bool, _Allocator>::vector(initializer_list<value_type> __il) if (__n > 0) { __vallocate(__n); - __construct_at_end(__il.begin(), __il.end()); + __construct_at_end(__il.begin(), __il.end(), __n); } } @@ -2719,7 +2886,7 @@ vector<bool, _Allocator>::vector(initializer_list<value_type> __il, const alloca if (__n > 0) { __vallocate(__n); - __construct_at_end(__il.begin(), __il.end()); + __construct_at_end(__il.begin(), __il.end(), __n); } } @@ -2735,7 +2902,7 @@ vector<bool, _Allocator>::vector(const vector& __v) if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2749,7 +2916,7 @@ vector<bool, _Allocator>::vector(const vector& __v, const allocator_type& __a) if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2808,7 +2975,7 @@ vector<bool, _Allocator>::vector(vector&& __v, const __type_identity_t<allocator else if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2876,6 +3043,13 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 typename enable_if <__is_exactly_cpp17_input_itera >::type vector<bool, _Allocator>::assign(_InputIterator __first, _InputIterator __last) { + __assign_with_sentinel(__first, __last); +} + +template <class _Allocator> +template <class _Iterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<bool, _Allocator>::__assign_with_sentinel(_Iterator __first, _Sentinel __last) { clear(); for (; __first != __last; ++__first) push_back(*__first); @@ -2891,9 +3065,17 @@ typename enable_if >::type vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __last) { - clear(); - difference_type __ns = std::distance(__first, __last); + __assign_with_size(__first, __last, std::distance(__first, __last)); +} + +template <class _Allocator> +template <class _ForwardIterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +void vector<bool, _Allocator>::__assign_with_size(_ForwardIterator __first, _Sentinel __last, difference_type __ns) { _LIBCPP_ASSERT(__ns >= 0, "invalid range specified"); + + clear(); + const size_t __n = static_cast<size_type>(__ns); if (__n) { @@ -2902,7 +3084,7 @@ vector<bool, _Allocator>::assign(_ForwardIterator __first, _ForwardIterator __la __vdeallocate(); __vallocate(__n); } - __construct_at_end(__first, __last); + __construct_at_end(__first, __last, __n); } } @@ -2916,7 +3098,7 @@ vector<bool, _Allocator>::reserve(size_type __n) this->__throw_length_error(); vector __v(this->get_allocator()); __v.__vallocate(__n); - __v.__construct_at_end(this->begin(), this->end()); + __v.__construct_at_end(this->begin(), this->end(), this->size()); swap(__v); std::__debug_db_invalidate_all(this); } @@ -3028,6 +3210,14 @@ _LIBCPP_CONSTEXPR_SINCE_CXX20 typename enable_if <__is_exactly_cpp17_input_itera >::type vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __first, _InputIterator __last) { + return __insert_with_sentinel(__position, __first, __last); +} + +template <class _Allocator> +template <class _InputIterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<bool, _Allocator>::iterator +vector<bool, _Allocator>::__insert_with_sentinel(const_iterator __position, _InputIterator __first, _Sentinel __last) { difference_type __off = __position - begin(); iterator __p = __const_iterator_cast(__position); iterator __old_end = end(); @@ -3043,7 +3233,7 @@ vector<bool, _Allocator>::insert(const_iterator __position, _InputIterator __fir try { #endif // _LIBCPP_HAS_NO_EXCEPTIONS - __v.assign(__first, __last); + __v.__assign_with_sentinel(std::move(__first), std::move(__last)); difference_type __old_size = static_cast<difference_type>(__old_end - begin()); difference_type __old_p = __p - begin(); reserve(__recommend(size() + __v.size())); @@ -3073,7 +3263,15 @@ typename enable_if >::type vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __first, _ForwardIterator __last) { - const difference_type __n_signed = std::distance(__first, __last); + return __insert_with_size(__position, __first, __last, std::distance(__first, __last)); +} + +template <class _Allocator> +template <class _ForwardIterator, class _Sentinel> +_LIBCPP_CONSTEXPR_SINCE_CXX20 _LIBCPP_HIDE_FROM_ABI +typename vector<bool, _Allocator>::iterator +vector<bool, _Allocator>::__insert_with_size(const_iterator __position, _ForwardIterator __first, _Sentinel __last, + difference_type __n_signed) { _LIBCPP_ASSERT(__n_signed >= 0, "invalid range specified"); const size_type __n = static_cast<size_type>(__n_signed); iterator __r; @@ -3094,7 +3292,7 @@ vector<bool, _Allocator>::insert(const_iterator __position, _ForwardIterator __f std::copy_backward(__position, cend(), __v.end()); swap(__v); } - std::copy(__first, __last, __r); + std::__copy<_ClassicAlgPolicy>(__first, __last, __r); return __r; } diff --git a/libcxx/test/libcxx/private_headers.verify.cpp b/libcxx/test/libcxx/private_headers.verify.cpp index d8a821893943..c7d035274c56 100644 --- a/libcxx/test/libcxx/private_headers.verify.cpp +++ b/libcxx/test/libcxx/private_headers.verify.cpp @@ -580,6 +580,7 @@ END-SCRIPT #include <__ranges/as_rvalue_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/as_rvalue_view.h'}} #include <__ranges/common_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/common_view.h'}} #include <__ranges/concepts.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/concepts.h'}} +#include <__ranges/container_compatible_range.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/container_compatible_range.h'}} #include <__ranges/copyable_box.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/copyable_box.h'}} #include <__ranges/counted.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/counted.h'}} #include <__ranges/dangling.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/dangling.h'}} @@ -592,6 +593,7 @@ END-SCRIPT #include <__ranges/enable_borrowed_range.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/enable_borrowed_range.h'}} #include <__ranges/enable_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/enable_view.h'}} #include <__ranges/filter_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/filter_view.h'}} +#include <__ranges/from_range.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/from_range.h'}} #include <__ranges/iota_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/iota_view.h'}} #include <__ranges/istream_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/istream_view.h'}} #include <__ranges/join_view.h> // expected-error@*:* {{use of private header from outside its module: '__ranges/join_view.h'}} diff --git a/libcxx/test/std/containers/from_range_helpers.h b/libcxx/test/std/containers/from_range_helpers.h new file mode 100644 index 000000000000..9bd72acfad09 --- /dev/null +++ b/libcxx/test/std/containers/from_range_helpers.h @@ -0,0 +1,154 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_FROM_RANGE_HELPERS_H +#define SUPPORT_FROM_RANGE_HELPERS_H + +#include <cstddef> +#include <iterator> +#include <type_traits> + +#include "min_allocator.h" +#include "test_allocator.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +struct Empty {}; + +template <class T> +struct InputRange { + cpp20_input_iterator<T*> begin(); + sentinel_wrapper<cpp20_input_iterator<T*>> end(); +}; + +template <class Iter, class Sent, std::ranges::input_range Range> +constexpr auto wrap_input(Range&& input) { + auto b = Iter(std::ranges::begin(input)); + auto e = Sent(Iter(std::ranges::end(input))); + return std::ranges::subrange(std::move(b), std::move(e)); +} + +template <class Iter, class Sent, class T> +constexpr auto wrap_input(std::vector<T>& input) { + auto b = Iter(input.data()); + auto e = Sent(Iter(input.data() + input.size())); + return std::ranges::subrange(std::move(b), std::move(e)); +} + +struct KeyValue { + int key; // Only the key is considered for equality comparison. + char value; // Allows distinguishing equivalent instances. + + bool operator<(const KeyValue& other) const { return key < other.key; } + bool operator==(const KeyValue& other) const { return key == other.key; } +}; + +template <> +struct std::hash<KeyValue> { + std::size_t operator()(const KeyValue& kv) const { + return kv.key; + } +}; + +#if !defined(TEST_HAS_NO_EXCEPTIONS) +template <int N> +struct ThrowingCopy { + static bool throwing_enabled; + static int created_by_copying; + static int destroyed; + int x = 0; // Allows distinguishing between different instances. + + ThrowingCopy() = default; + ThrowingCopy(int value) : x(value) {} + ~ThrowingCopy() { + ++destroyed; + } + + ThrowingCopy(const ThrowingCopy& other) : x(other.x) { + ++created_by_copying; + if (throwing_enabled && created_by_copying == N) { + throw -1; + } + } + + // Defined to silence GCC warnings. For test purposes, only copy construction is considered `created_by_copying`. + ThrowingCopy& operator=(const ThrowingCopy& other) { + x = other.x; + return *this; + } + + friend auto operator<=>(const ThrowingCopy&, const ThrowingCopy&) = default; + + static void reset() { + created_by_copying = destroyed = 0; + } +}; + +template <int N> +struct std::hash<ThrowingCopy<N>> { + std::size_t operator()(const ThrowingCopy<N>& value) const { + return value.x; + } +}; + +template <int N> +bool ThrowingCopy<N>::throwing_enabled = true; +template <int N> +int ThrowingCopy<N>::created_by_copying = 0; +template <int N> +int ThrowingCopy<N>::destroyed = 0; + +template <class T> +struct ThrowingAllocator { + using value_type = T; + using char_type = T; + using is_always_equal = std::false_type; + + ThrowingAllocator() = default; + + template <class U> + ThrowingAllocator(const ThrowingAllocator<U>&) {} + + T* allocate(std::size_t) { throw 1; } + void deallocate(T*, std::size_t) {} + + template <class U> + friend bool operator==(const ThrowingAllocator&, const ThrowingAllocator<U>&) { + return true; + } +}; +#endif + +template <class T, class Func> +constexpr void for_all_iterators_and_allocators(Func f) { + using Iterators = types::type_list< + cpp20_input_iterator<T*>, + forward_iterator<T*>, + bidirectional_iterator<T*>, + random_access_iterator<T*>, + contiguous_iterator<T*>, + T* + >; + + types::for_each(Iterators{}, [=]<class Iter>() { + f.template operator()<Iter, sentinel_wrapper<Iter>, std::allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, test_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, min_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, safe_allocator<T>>(); + + if constexpr (std::sentinel_for<Iter, Iter>) { + f.template operator()<Iter, Iter, std::allocator<T>>(); + f.template operator()<Iter, Iter, test_allocator<T>>(); + f.template operator()<Iter, Iter, min_allocator<T>>(); + f.template operator()<Iter, Iter, safe_allocator<T>>(); + } + }); +} + +#endif // SUPPORT_FROM_RANGE_HELPERS_H diff --git a/libcxx/test/std/containers/insert_range_helpers.h b/libcxx/test/std/containers/insert_range_helpers.h new file mode 100644 index 000000000000..2c4e14ce8b73 --- /dev/null +++ b/libcxx/test/std/containers/insert_range_helpers.h @@ -0,0 +1,123 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_INSERT_RANGE_HELPERS_H +#define SUPPORT_INSERT_RANGE_HELPERS_H + +#include <algorithm> +#include <array> +#include <cassert> +#include <concepts> +#include <map> +#include <ranges> +#include <set> +#include <type_traits> +#include <unordered_map> +#include <unordered_set> +#include <vector> + +#include "from_range_helpers.h" +#include "min_allocator.h" +#include "test_allocator.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +// A simple literal-type container. It can be used as a `constexpr` global variable (which isn't supported by +// `std::vector`). +template <class T, std::size_t N = 32> +class Buffer { + public: + constexpr Buffer() = default; + + constexpr Buffer(std::initializer_list<T> input) { + assert(input.size() <= N); + std::ranges::copy(input, data_); + size_ = input.size(); + } + + // Makes initializing `Buffer<char>` nicer -- allows writing `buf = "abc"` instead of `buf = {'a', 'b', 'c'}`. + // To make the two forms equivalent, omits the terminating null. + template <std::size_t N2> + constexpr Buffer(const char (&input) [N2]) + requires std::same_as<T, char> { + static_assert(N2 <= N); + std::ranges::copy(input, data_); + // Omit the terminating null. + size_ = input[N2 - 1] == '\0' ? N2 - 1 : N2; + } + + constexpr const T* begin() const { return data_; } + constexpr const T* end() const { return data_ + size_; } + constexpr std::size_t size() const { return size_; } + + private: + std::size_t size_ = 0; + T data_[N] = {}; +}; + +template <class T> +struct TestCase { + Buffer<T> initial; + std::size_t index = 0; + Buffer<T> input; + Buffer<T> expected; +}; + +template <class T, class PtrT, class Func> +constexpr void for_all_iterators_and_allocators(Func f) { + using Iterators = types::type_list< + cpp20_input_iterator<PtrT>, + forward_iterator<PtrT>, + bidirectional_iterator<PtrT>, + random_access_iterator<PtrT>, + contiguous_iterator<PtrT>, + PtrT + >; + + types::for_each(Iterators{}, [=]<class Iter>() { + f.template operator()<Iter, sentinel_wrapper<Iter>, std::allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, test_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, min_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, safe_allocator<T>>(); + + if constexpr (std::sentinel_for<Iter, Iter>) { + f.template operator()<Iter, Iter, std::allocator<T>>(); + f.template operator()<Iter, Iter, test_allocator<T>>(); + f.template operator()<Iter, Iter, min_allocator<T>>(); + f.template operator()<Iter, Iter, safe_allocator<T>>(); + } + }); +} + +// Uses a shorter list of iterator types for use in `constexpr` mode for cases when running the full set in would take +// too long. +template <class T, class PtrT, class Func> +constexpr void for_all_iterators_and_allocators_constexpr(Func f) { + using Iterators = types::type_list< + cpp20_input_iterator<PtrT>, + forward_iterator<PtrT>, + PtrT + >; + + types::for_each(Iterators{}, [=]<class Iter>() { + f.template operator()<Iter, sentinel_wrapper<Iter>, std::allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, test_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, min_allocator<T>>(); + f.template operator()<Iter, sentinel_wrapper<Iter>, safe_allocator<T>>(); + + if constexpr (std::sentinel_for<Iter, Iter>) { + f.template operator()<Iter, Iter, std::allocator<T>>(); + f.template operator()<Iter, Iter, test_allocator<T>>(); + f.template operator()<Iter, Iter, min_allocator<T>>(); + f.template operator()<Iter, Iter, safe_allocator<T>>(); + } + }); +} + +#endif // SUPPORT_INSERT_RANGE_HELPERS_H diff --git a/libcxx/test/std/containers/sequences/from_range_sequence_containers.h b/libcxx/test/std/containers/sequences/from_range_sequence_containers.h new file mode 100644 index 000000000000..7106cb807733 --- /dev/null +++ b/libcxx/test/std/containers/sequences/from_range_sequence_containers.h @@ -0,0 +1,161 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_FROM_RANGE_SEQUENCE_CONTAINERS_H +#define SUPPORT_FROM_RANGE_SEQUENCE_CONTAINERS_H + +#include <algorithm> +#include <array> +#include <cassert> +#include <cstddef> +#include <iterator> +#include <ranges> +#include <utility> + +#include "../from_range_helpers.h" +#include "MoveOnly.h" +#include "almost_satisfies_types.h" +#include "count_new.h" +#include "test_iterators.h" +#include "test_macros.h" + +template <class T> +concept HasSize = requires (const T& value) { value.size(); }; + +template <class Container, class Range> +concept HasFromRangeCtr = requires (Range&& range) { + Container(std::from_range, std::forward<Range>(range)); + Container(std::from_range, std::forward<Range>(range), std::allocator<typename Container::value_type>()); +}; + +template <template <class...> class Container, class T, class U> +constexpr bool test_constraints() { + // Input range with the same value type. + static_assert(HasFromRangeCtr<Container<T>, InputRange<T>>); + // Input range with a convertible value type. + static_assert(HasFromRangeCtr<Container<T>, InputRange<U>>); + // Input range with a non-convertible value type. + static_assert(!HasFromRangeCtr<Container<T>, InputRange<Empty>>); + // Not an input range. + static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotDerivedFrom>); + static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotIndirectlyReadable>); + static_assert(!HasFromRangeCtr<Container<T>, InputRangeNotInputOrOutputIterator>); + + // Note: there are no constraints on the allocator (it's not a separate template type of the constructor)`. + + return true; +} + +// Note: `std::array` is used to avoid dealing with `vector<bool>`. +template <template <class ...> class Container, + class T, + class Iter, + class Sent, + class Alloc, + std::size_t N, + class ValidateFunc> +constexpr void test_sequence_container_with_input(std::array<T, N>&& input, ValidateFunc validate) { + auto in = wrap_input<Iter, Sent>(input); + + { // (range) + Container<T> c(std::from_range, in); + + if constexpr (HasSize<Container<T>>) { + assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); + } + assert(std::ranges::equal(in, c)); + validate(c); + } + + { // (range, allocator) + Alloc alloc; + Container<T, Alloc> c(std::from_range, in, alloc); + + assert(c.get_allocator() == alloc); + if constexpr (HasSize<Container<T, Alloc>>) { + assert(c.size() == static_cast<std::size_t>(std::distance(c.begin(), c.end()))); + } + assert(std::ranges::equal(in, c)); + validate(c); + } +} + +template <template <class ...> class Container, + class T, + class Iter, + class Sent, + class Alloc, + class ValidateFunc> +constexpr void test_sequence_container(ValidateFunc validate) { + // Normal input. + test_sequence_container_with_input<Container, T, Iter, Sent, Alloc>(std::array{0, 5, 12, 7, -1, 8, 26}, validate); + // Empty input. + test_sequence_container_with_input<Container, T, Iter, Sent, Alloc>(std::array<int, 0>{}, validate); + // Single-element input. + test_sequence_container_with_input<Container, T, Iter, Sent, Alloc>(std::array{5}, validate); +} + +template <template <class ...> class Container> +constexpr void test_sequence_container_move_only() { + MoveOnly input[5]; + std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); + + [[maybe_unused]] Container<MoveOnly> c(std::from_range, in); +} + +template <class Iter, + class Sent, + class Alloc, + class ValidateFunc> +constexpr void test_vector_bool(ValidateFunc validate) { + // Normal input. + test_sequence_container_with_input<std::vector, bool, Iter, Sent, Alloc>( + std::array{true, false, false, true, false, true, true, true, false, true}, validate); + // Empty input. + test_sequence_container_with_input<std::vector, bool, Iter, Sent, Alloc>(std::array<bool, 0>{}, validate); + // Single-element input. + test_sequence_container_with_input<std::vector, bool, Iter, Sent, Alloc>(std::array{true}, validate); +} + +template <template <class ...> class Container> +void test_exception_safety_throwing_copy() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + using T = ThrowingCopy<3>; + T::reset(); + T in[5]; + + try { + Container<T> c(std::from_range, in); + assert(false); // The constructor call above should throw. + + } catch (int) { + assert(T::created_by_copying == 3); + assert(T::destroyed == 2); // No destructor call for the partially-constructed element. + } +#endif +} + +template <template <class ...> class Container, class T> +void test_exception_safety_throwing_allocator() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + T in[] = {0, 1}; + + try { + ThrowingAllocator<T> alloc; + + globalMemCounter.reset(); + Container<T, ThrowingAllocator<T>> c(std::from_range, in, alloc); + assert(false); // The constructor call above should throw. + + } catch (int) { + assert(globalMemCounter.new_called == globalMemCounter.delete_called); + } +#endif +} + +#endif // SUPPORT_FROM_RANGE_SEQUENCE_CONTAINERS_H diff --git a/libcxx/test/std/containers/sequences/insert_range_sequence_containers.h b/libcxx/test/std/containers/sequences/insert_range_sequence_containers.h new file mode 100644 index 000000000000..10fadca10eb8 --- /dev/null +++ b/libcxx/test/std/containers/sequences/insert_range_sequence_containers.h @@ -0,0 +1,827 @@ +//===----------------------------------------------------------------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// + +#ifndef SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H +#define SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H + +#include <algorithm> +#include <cassert> +#include <concepts> +#include <cstddef> +#include <initializer_list> +#include <ranges> +#include <type_traits> +#include <vector> + +#include "../from_range_helpers.h" +#include "../insert_range_helpers.h" +#include "MoveOnly.h" +#include "almost_satisfies_types.h" +#include "count_new.h" +#include "min_allocator.h" +#include "test_allocator.h" +#include "test_iterators.h" +#include "test_macros.h" +#include "type_algorithms.h" + +template <class Container, class Range> +concept HasInsertRange = requires (Container& c, Range&& range) { + c.insert_range(c.end(), range); +}; + +template <template <class...> class Container, class T, class U> +constexpr bool test_constraints_insert_range() { + // Input range with the same value type. + static_assert(HasInsertRange<Container<T>, InputRange<T>>); + // Input range with a convertible value type. + static_assert(HasInsertRange<Container<T>, InputRange<U>>); + // Input range with a non-convertible value type. + static_assert(!HasInsertRange<Container<T>, InputRange<Empty>>); + // Not an input range. + static_assert(!HasInsertRange<Container<T>, InputRangeNotDerivedFrom>); + static_assert(!HasInsertRange<Container<T>, InputRangeNotIndirectlyReadable>); + static_assert(!HasInsertRange<Container<T>, InputRangeNotInputOrOutputIterator>); + + return true; +} + +template <class Container, class Range> +concept HasAppendRange = requires (Container& c, Range&& range) { + c.append_range(range); +}; + +template <template <class...> class Container, class T, class U> +constexpr bool test_constraints_append_range() { + // Input range with the same value type. + static_assert(HasAppendRange<Container<T>, InputRange<T>>); + // Input range with a convertible value type. + static_assert(HasAppendRange<Container<T>, InputRange<U>>); + // Input range with a non-convertible value type. + static_assert(!HasAppendRange<Container<T>, InputRange<Empty>>); + // Not an input range. + static_assert(!HasAppendRange<Container<T>, InputRangeNotDerivedFrom>); + static_assert(!HasAppendRange<Container<T>, InputRangeNotIndirectlyReadable>); + static_assert(!HasAppendRange<Container<T>, InputRangeNotInputOrOutputIterator>); + + return true; +} + +template <class Container, class Range> +concept HasPrependRange = requires (Container& c, Range&& range) { + c.prepend_range(range); +}; + +template <template <class...> class Container, class T, class U> +constexpr bool test_constraints_prepend_range() { + // Input range with the same value type. + static_assert(HasPrependRange<Container<T>, InputRange<T>>); + // Input range with a convertible value type. + static_assert(HasPrependRange<Container<T>, InputRange<U>>); + // Input range with a non-convertible value type. + static_assert(!HasPrependRange<Container<T>, InputRange<Empty>>); + // Not an input range. + static_assert(!HasPrependRange<Container<T>, InputRangeNotDerivedFrom>); + static_assert(!HasPrependRange<Container<T>, InputRangeNotIndirectlyReadable>); + static_assert(!HasPrependRange<Container<T>, InputRangeNotInputOrOutputIterator>); + + return true; +} + +template <class Container, class Range> +concept HasAssignRange = requires (Container& c, Range&& range) { + c.assign_range(range); +}; + +template <template <class...> class Container, class T, class U> +constexpr bool test_constraints_assign_range() { + // Input range with the same value type. + static_assert(HasAssignRange<Container<T>, InputRange<T>>); + // Input range with a convertible value type. + static_assert(HasAssignRange<Container<T>, InputRange<U>>); + // Input range with a non-convertible value type. + static_assert(!HasAssignRange<Container<T>, InputRange<Empty>>); + // Not an input range. + static_assert(!HasAssignRange<Container<T>, InputRangeNotDerivedFrom>); + static_assert(!HasAssignRange<Container<T>, InputRangeNotIndirectlyReadable>); + static_assert(!HasAssignRange<Container<T>, InputRangeNotInputOrOutputIterator>); + + return true; +} + +// Empty container. + +template <class T> +TestCase<T> constexpr EmptyContainer_EmptyRange { + .initial = {}, .index = 0, .input = {}, .expected = {} +}; +// Note: specializations for `bool` still use `vector<int>` for inputs. This is to avoid dealing with `vector<bool>` and +// its iterators over proxy types. +template <> constexpr TestCase<int> EmptyContainer_EmptyRange<bool> { + .initial = {}, .index = 0, .input = {}, .expected = {} +}; + +template <class T> constexpr TestCase<T> EmptyContainer_OneElementRange; +template <> constexpr TestCase<int> EmptyContainer_OneElementRange<int> { + .initial = {}, .index = 0, .input = {5}, .expected = {5} +}; +template <> constexpr TestCase<char> EmptyContainer_OneElementRange<char> { + .initial = {}, .index = 0, .input = "a", .expected = "a" +}; +template <> constexpr TestCase<int> EmptyContainer_OneElementRange<bool> { + .initial = {}, .index = 0, .input = {true}, .expected = {true} +}; + +template <class T> constexpr TestCase<T> EmptyContainer_MidRange; +template <> constexpr TestCase<int> EmptyContainer_MidRange<int> { + .initial = {}, .index = 0, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9} +}; +template <> constexpr TestCase<char> EmptyContainer_MidRange<char> { + .initial = {}, .index = 0, .input = "aeiou", .expected = "aeiou" +}; +template <> constexpr TestCase<int> EmptyContainer_MidRange<bool> { + .initial = {}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1} +}; + +// One-element container. + +template <class T> constexpr TestCase<T> OneElementContainer_Begin_EmptyRange; +template <> constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<int> { + .initial = {3}, .index = 0, .input = {}, .expected = {3} +}; +template <> constexpr TestCase<char> OneElementContainer_Begin_EmptyRange<char> { + .initial = "B", .index = 0, .input = {}, .expected = "B" +}; +template <> constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<bool> { + .initial = {0}, .index = 0, .input = {}, .expected = {0} +}; + +template <class T> constexpr TestCase<T> OneElementContainer_End_EmptyRange; +template <> constexpr TestCase<int> OneElementContainer_End_EmptyRange<int> { + .initial = {3}, .index = 1, .input = {}, .expected = {3} +}; +template <> constexpr TestCase<char> OneElementContainer_End_EmptyRange<char> { + .initial = "B", .index = 1, .input = {}, .expected = "B" +}; +template <> constexpr TestCase<int> OneElementContainer_End_EmptyRange<bool> { + .initial = {0}, .index = 1, .input = {}, .expected = {0} +}; + +template <class T> constexpr TestCase<T> OneElementContainer_Begin_OneElementRange; +template <> constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<int> { + .initial = {3}, .index = 0, .input = {-5}, .expected = {-5, 3} +}; +template <> constexpr TestCase<char> OneElementContainer_Begin_OneElementRange<char> { + .initial = "B", .index = 0, .input = "a", .expected = "aB" +}; +template <> constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<bool> { + .initial = {0}, .index = 0, .input = {1}, .expected = {1, 0} +}; + +template <class T> constexpr TestCase<T> OneElementContainer_End_OneElementRange; +template <> constexpr TestCase<int> OneElementContainer_End_OneElementRange<int> { + .initial = {3}, .index = 1, .input = {-5}, .expected = {3, -5} +}; +template <> constexpr TestCase<char> OneElementContainer_End_OneElementRange<char> { + .initial = "B", .index = 1, .input = "a", .expected = "Ba" +}; +template <> constexpr TestCase<int> OneElementContainer_End_OneElementRange<bool> { + .initial = {0}, .index = 1, .input = {1}, .expected = {0, 1} +}; + +template <class T> constexpr TestCase<T> OneElementContainer_Begin_MidRange; +template <> constexpr TestCase<int> OneElementContainer_Begin_MidRange<int> { + .initial = {3}, .index = 0, .input = {-5, -3, -1, -7, -9}, .expected = {-5, -3, -1, -7, -9, 3} +}; +template <> constexpr TestCase<char> OneElementContainer_Begin_MidRange<char> { + .initial = "B", .index = 0, .input = "aeiou", .expected = "aeiouB" +}; +template <> constexpr TestCase<int> OneElementContainer_Begin_MidRange<bool> { + .initial = {0}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1, 0} +}; + +template <class T> constexpr TestCase<T> OneElementContainer_End_MidRange; +template <> constexpr TestCase<int> OneElementContainer_End_MidRange<int> { + .initial = {3}, .index = 1, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9} +}; +template <> constexpr TestCase<char> OneElementContainer_End_MidRange<char> { + .initial = "B", .index = 1, .input = "aeiou", .expected = "Baeiou" +}; +template <> constexpr TestCase<int> OneElementContainer_End_MidRange<bool> { + .initial = {0}, .index = 1, .input = {1, 1, 0, 1, 1}, .expected = {0, 1, 1, 0, 1, 1} +}; + +// Full container / empty range. + +template <class T> constexpr TestCase<T> FullContainer_Begin_EmptyRange; +template <> constexpr TestCase<int> FullContainer_Begin_EmptyRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Begin_EmptyRange<char> { + .initial = "_BCD_", .index = 0, .input = {}, .expected = "_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_Begin_EmptyRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +template <class T> constexpr TestCase<T> FullContainer_Mid_EmptyRange; +template <> constexpr TestCase<int> FullContainer_Mid_EmptyRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Mid_EmptyRange<char> { + .initial = "_BCD_", .index = 2, .input = {}, .expected = "_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_Mid_EmptyRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +template <class T> constexpr TestCase<T> FullContainer_End_EmptyRange; +template <> constexpr TestCase<int> FullContainer_End_EmptyRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {}, .expected = {11, 29, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_End_EmptyRange<char> { + .initial = "_BCD_", .index = 5, .input = {}, .expected = "_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_End_EmptyRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {}, .expected = {0, 0, 1, 0, 0} +}; + +// Full container / one-element range. + +template <class T> constexpr TestCase<T> FullContainer_Begin_OneElementRange; +template <> constexpr TestCase<int> FullContainer_Begin_OneElementRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {-5}, .expected = {-5, 11, 29, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Begin_OneElementRange<char> { + .initial = "_BCD_", .index = 0, .input = "a", .expected = "a_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_Begin_OneElementRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {1}, .expected = {1, 0, 0, 1, 0, 0} +}; + +template <class T> constexpr TestCase<T> FullContainer_Mid_OneElementRange; +template <> constexpr TestCase<int> FullContainer_Mid_OneElementRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {-5}, .expected = {11, 29, -5, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Mid_OneElementRange<char> { + .initial = "_BCD_", .index = 2, .input = "a", .expected = "_BaCD_" +}; +template <> constexpr TestCase<int> FullContainer_Mid_OneElementRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {1}, .expected = {0, 0, 1, 1, 0, 0} +}; + +template <class T> constexpr TestCase<T> FullContainer_End_OneElementRange; +template <> constexpr TestCase<int> FullContainer_End_OneElementRange<int> { + .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5} +}; +template <> constexpr TestCase<char> FullContainer_End_OneElementRange<char> { + .initial = "_BCD_", .index = 5, .input = "a", .expected = "_BCD_a" +}; +template <> constexpr TestCase<int> FullContainer_End_OneElementRange<bool> { + .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {1}, .expected = {0, 0, 1, 0, 0, 1} +}; + +// Full container / mid-sized range. + +template <class T> constexpr TestCase<T> FullContainer_Begin_MidRange; +template <> constexpr TestCase<int> FullContainer_Begin_MidRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 0, + .input = {-5, -3, -1, -7, -9}, + .expected = {-5, -3, -1, -7, -9, 11, 29, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Begin_MidRange<char> { + .initial = "_BCD_", + .index = 0, + .input = "aeiou", + .expected = "aeiou_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_Begin_MidRange<bool> { + .initial = {0, 0, 1, 0, 1}, + .index = 0, + .input = {1, 1, 0, 1, 1}, + .expected = {1, 1, 0, 1, 1, 0, 0, 1, 0, 1} +}; + +template <class T> constexpr TestCase<T> FullContainer_Mid_MidRange; +template <> constexpr TestCase<int> FullContainer_Mid_MidRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 2, + .input = {-5, -3, -1, -7, -9}, + .expected = {11, 29, -5, -3, -1, -7, -9, 35, 14, 84} +}; +template <> constexpr TestCase<char> FullContainer_Mid_MidRange<char> { + .initial = "_BCD_", + .index = 2, + .input = "aeiou", + .expected = "_BaeiouCD_" +}; +template <> constexpr TestCase<int> FullContainer_Mid_MidRange<bool> { + .initial = {0, 0, 1, 0, 1}, + .index = 2, + .input = {1, 1, 0, 1, 1}, + .expected = {0, 0, 1, 1, 0, 1, 1, 1, 0, 1} +}; + +template <class T> constexpr TestCase<T> FullContainer_End_MidRange; +template <> constexpr TestCase<int> FullContainer_End_MidRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 5, + .input = {-5, -3, -1, -7, -9}, + .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9} +}; +template <> constexpr TestCase<char> FullContainer_End_MidRange<char> { + .initial = "_BCD_", + .index = 5, + .input = "aeiou", + .expected = "_BCD_aeiou" +}; +template <> constexpr TestCase<int> FullContainer_End_MidRange<bool> { + .initial = {0, 0, 1, 0, 1}, + .index = 5, + .input = {1, 1, 0, 1, 1}, + .expected = {0, 0, 1, 0, 1, 1, 1, 0, 1, 1} +}; + +// Full container / long range. + +template <class T> constexpr TestCase<T> FullContainer_Begin_LongRange; +template <> constexpr TestCase<int> FullContainer_Begin_LongRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 0, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 11, 29, 35, 14, 84 + } +}; +template <> constexpr TestCase<char> FullContainer_Begin_LongRange<char> { + .initial = "_BCD_", + .index = 0, + .input = "aeiouqwxyz5781964203", + .expected = "aeiouqwxyz5781964203_BCD_" +}; +template <> constexpr TestCase<int> FullContainer_Begin_LongRange<bool> { + .initial = {0, 0, 1, 0, 0}, + .index = 0, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0 + } +}; + +template <class T> constexpr TestCase<T> FullContainer_Mid_LongRange; +template <> constexpr TestCase<int> FullContainer_Mid_LongRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 2, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + 11, 29, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48, 35, 14, 84 + } +}; +template <> constexpr TestCase<char> FullContainer_Mid_LongRange<char> { + .initial = "_BCD_", + .index = 2, + .input = "aeiouqwxyz5781964203", + .expected = "_Baeiouqwxyz5781964203CD_" +}; +template <> constexpr TestCase<int> FullContainer_Mid_LongRange<bool> { + .initial = {0, 0, 1, 0, 0}, + .index = 2, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0 + } +}; + +template <class T> constexpr TestCase<T> FullContainer_End_LongRange; +template <> constexpr TestCase<int> FullContainer_End_LongRange<int> { + .initial = {11, 29, 35, 14, 84}, + .index = 5, + .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}, + .expected = { + 11, 29, 35, 14, 84, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48 + } +}; +template <> constexpr TestCase<char> FullContainer_End_LongRange<char> { + .initial = "_BCD_", + .index = 5, + .input = "aeiouqwxyz5781964203", + .expected = "_BCD_aeiouqwxyz5781964203" +}; +template <> constexpr TestCase<int> FullContainer_End_LongRange<bool> { + .initial = {0, 0, 1, 0, 1}, + .index = 5, + .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}, + .expected = { + 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0 + } +}; + +// Sequence containers tests. + +template <class Container, class Iter, class Sent, class Validate> +constexpr void test_sequence_insert_range(Validate validate) { + using T = typename Container::value_type; + auto get_pos = [](auto& c, auto& test_case) { return std::ranges::next(c.begin(), test_case.index); }; + + auto test = [&](auto& test_case) { + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input<Iter, Sent>(test_case.input); + auto pos = get_pos(c, test_case); + + auto result = c.insert_range(pos, in); + assert(result == get_pos(c, test_case)); + validate(c); + return std::ranges::equal(c, test_case.expected); + }; + + { // Empty container. + // empty_c.insert_range(end, empty_range) + assert(test(EmptyContainer_EmptyRange<T>)); + // empty_c.insert_range(end, one_element_range) + assert(test(EmptyContainer_OneElementRange<T>)); + // empty_c.insert_range(end, mid_range) + assert(test(EmptyContainer_MidRange<T>)); + } + + { // One-element container. + // one_element_c.insert_range(begin, empty_range) + assert(test(OneElementContainer_Begin_EmptyRange<T>)); + // one_element_c.insert_range(end, empty_range) + assert(test(OneElementContainer_End_EmptyRange<T>)); + // one_element_c.insert_range(begin, one_element_range) + assert(test(OneElementContainer_Begin_OneElementRange<T>)); + // one_element_c.insert_range(end, one_element_range) + assert(test(OneElementContainer_End_OneElementRange<T>)); + // one_element_c.insert_range(begin, mid_range) + assert(test(OneElementContainer_Begin_MidRange<T>)); + // one_element_c.insert_range(end, mid_range) + assert(test(OneElementContainer_End_MidRange<T>)); + } + + { // Full container. + // full_container.insert_range(begin, empty_range) + assert(test(FullContainer_Begin_EmptyRange<T>)); + // full_container.insert_range(mid, empty_range) + assert(test(FullContainer_Mid_EmptyRange<T>)); + // full_container.insert_range(end, empty_range) + assert(test(FullContainer_End_EmptyRange<T>)); + // full_container.insert_range(begin, one_element_range) + assert(test(FullContainer_Begin_OneElementRange<T>)); + // full_container.insert_range(end, one_element_range) + assert(test(FullContainer_Mid_OneElementRange<T>)); + // full_container.insert_range(end, one_element_range) + assert(test(FullContainer_End_OneElementRange<T>)); + // full_container.insert_range(begin, mid_range) + assert(test(FullContainer_Begin_MidRange<T>)); + // full_container.insert_range(mid, mid_range) + assert(test(FullContainer_Mid_MidRange<T>)); + // full_container.insert_range(end, mid_range) + assert(test(FullContainer_End_MidRange<T>)); + // full_container.insert_range(begin, long_range) + assert(test(FullContainer_Begin_LongRange<T>)); + // full_container.insert_range(mid, long_range) + assert(test(FullContainer_Mid_LongRange<T>)); + // full_container.insert_range(end, long_range) + assert(test(FullContainer_End_LongRange<T>)); + } +} + +template <class Container, class Iter, class Sent, class Validate> +constexpr void test_sequence_prepend_range(Validate validate) { + using T = typename Container::value_type; + + auto test = [&](auto& test_case) { + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input<Iter, Sent>(test_case.input); + + c.prepend_range(in); + validate(c); + return std::ranges::equal(c, test_case.expected); + }; + + { // Empty container. + // empty_c.prepend_range(empty_range) + assert(test(EmptyContainer_EmptyRange<T>)); + // empty_c.prepend_range(one_element_range) + assert(test(EmptyContainer_OneElementRange<T>)); + // empty_c.prepend_range(mid_range) + assert(test(EmptyContainer_MidRange<T>)); + } + + { // One-element container. + // one_element_c.prepend_range(empty_range) + assert(test(OneElementContainer_Begin_EmptyRange<T>)); + // one_element_c.prepend_range(one_element_range) + assert(test(OneElementContainer_Begin_OneElementRange<T>)); + // one_element_c.prepend_range(mid_range) + assert(test(OneElementContainer_Begin_MidRange<T>)); + } + + { // Full container. + // full_container.prepend_range(empty_range) + assert(test(FullContainer_Begin_EmptyRange<T>)); + // full_container.prepend_range(one_element_range) + assert(test(FullContainer_Begin_OneElementRange<T>)); + // full_container.prepend_range(mid_range) + assert(test(FullContainer_Begin_MidRange<T>)); + // full_container.prepend_range(long_range) + assert(test(FullContainer_Begin_LongRange<T>)); + } +} + +template <class Container, class Iter, class Sent, class Validate> +constexpr void test_sequence_append_range(Validate validate) { + using T = typename Container::value_type; + + auto test = [&](auto& test_case) { + Container c(test_case.initial.begin(), test_case.initial.end()); + auto in = wrap_input<Iter, Sent>(test_case.input); + + c.append_range(in); + validate(c); + return std::ranges::equal(c, test_case.expected); + }; + + { // Empty container. + // empty_c.append_range(empty_range) + assert(test(EmptyContainer_EmptyRange<T>)); + // empty_c.append_range(one_element_range) + assert(test(EmptyContainer_OneElementRange<T>)); + // empty_c.append_range(mid_range) + assert(test(EmptyContainer_MidRange<T>)); + } + + { // One-element container. + // one_element_c.append_range(empty_range) + assert(test(OneElementContainer_End_EmptyRange<T>)); + // one_element_c.append_range(one_element_range) + assert(test(OneElementContainer_End_OneElementRange<T>)); + // one_element_c.append_range(mid_range) + assert(test(OneElementContainer_End_MidRange<T>)); + } + + { // Full container. + // full_container.append_range(empty_range) + assert(test(FullContainer_End_EmptyRange<T>)); + // full_container.append_range(one_element_range) + assert(test(FullContainer_End_OneElementRange<T>)); + // full_container.append_range(mid_range) + assert(test(FullContainer_End_MidRange<T>)); + // full_container.append_range(long_range) + assert(test(FullContainer_End_LongRange<T>)); + } +} + +template <class Container, class Iter, class Sent, class Validate> +constexpr void test_sequence_assign_range(Validate validate) { + using T = typename Container::value_type; + + auto& initial_empty = EmptyContainer_EmptyRange<T>.initial; + auto& initial_one_element = OneElementContainer_Begin_EmptyRange<T>.initial; + auto& initial_full = FullContainer_Begin_EmptyRange<T>.initial; + auto& input_empty = FullContainer_Begin_EmptyRange<T>.input; + auto& input_one_element = FullContainer_Begin_OneElementRange<T>.input; + auto& input_mid_range = FullContainer_Begin_MidRange<T>.input; + auto& input_long_range = FullContainer_Begin_LongRange<T>.input; + + auto test = [&](auto& initial, auto& input) { + Container c(initial.begin(), initial.end()); + auto in = wrap_input<Iter, Sent>(input); + + c.assign_range(in); + validate(c); + return std::ranges::equal(c, input); + }; + + { // Empty container. + // empty_container.assign_range(empty_range) + assert(test(initial_empty, input_empty)); + // empty_container.assign_range(one_element_range) + assert(test(initial_empty, input_one_element)); + // empty_container.assign_range(mid_range) + assert(test(initial_empty, input_mid_range)); + // empty_container.assign_range(long_range) + assert(test(initial_empty, input_long_range)); + } + + { // One-element container. + // one_element_container.assign_range(empty_range) + assert(test(initial_one_element, input_empty)); + // one_element_container.assign_range(one_element_range) + assert(test(initial_one_element, input_one_element)); + // one_element_container.assign_range(mid_range) + assert(test(initial_one_element, input_mid_range)); + // one_element_container.assign_range(long_range) + assert(test(initial_one_element, input_long_range)); + } + + { // Full container. + // full_container.assign_range(empty_range) + assert(test(initial_full, input_empty)); + // full_container.assign_range(one_element_range) + assert(test(initial_full, input_one_element)); + // full_container.assign_range(mid_range) + assert(test(initial_full, input_mid_range)); + // full_container.assign_range(long_range) + assert(test(initial_full, input_long_range)); + } +} + +// Move-only types. + +template <template <class ...> class Container> +constexpr void test_sequence_insert_range_move_only() { + MoveOnly input[5]; + std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); + + Container<MoveOnly> c; + c.insert_range(c.end(), in); +} + +template <template <class ...> class Container> +constexpr void test_sequence_prepend_range_move_only() { + MoveOnly input[5]; + std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); + + Container<MoveOnly> c; + c.prepend_range(in); +} + +template <template <class ...> class Container> +constexpr void test_sequence_append_range_move_only() { + MoveOnly input[5]; + std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); + + Container<MoveOnly> c; + c.append_range(in); +} + +template <template <class ...> class Container> +constexpr void test_sequence_assign_range_move_only() { + MoveOnly input[5]; + std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5}); + + Container<MoveOnly> c; + c.assign_range(in); +} + +// Exception safety. + +template <template <class ...> class Container> +void test_insert_range_exception_safety_throwing_copy() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + using T = ThrowingCopy<3>; + T::reset(); + T in[5]; + + try { + Container<T> c; + c.insert_range(c.end(), in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(T::created_by_copying == 3); + assert(T::destroyed == 2); // No destructor call for the partially-constructed element. + } +#endif +} + +template <template <class ...> class Container, class T> +void test_insert_range_exception_safety_throwing_allocator() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + T in[] = {0, 1}; + + try { + ThrowingAllocator<T> alloc; + + globalMemCounter.reset(); + Container<T, ThrowingAllocator<T>> c(alloc); + c.insert_range(c.end(), in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(globalMemCounter.new_called == globalMemCounter.delete_called); + } +#endif +} + +template <template <class ...> class Container> +void test_prepend_range_exception_safety_throwing_copy() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + using T = ThrowingCopy<3>; + T::reset(); + T in[5]; + + try { + Container<T> c; + c.prepend_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(T::created_by_copying == 3); + assert(T::destroyed == 2); // No destructor call for the partially-constructed element. + } +#endif +} + +template <template <class ...> class Container, class T> +void test_prepend_range_exception_safety_throwing_allocator() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + T in[] = {0, 1}; + + try { + ThrowingAllocator<T> alloc; + + globalMemCounter.reset(); + Container<T, ThrowingAllocator<T>> c(alloc); + c.prepend_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(globalMemCounter.new_called == globalMemCounter.delete_called); + } +#endif +} + +template <template <class ...> class Container> +void test_append_range_exception_safety_throwing_copy() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + using T = ThrowingCopy<3>; + T::reset(); + T in[5]; + + try { + Container<T> c; + c.append_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(T::created_by_copying == 3); + assert(T::destroyed == 2); // No destructor call for the partially-constructed element. + } +#endif +} + +template <template <class ...> class Container, class T> +void test_append_range_exception_safety_throwing_allocator() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + T in[] = {0, 1}; + + try { + ThrowingAllocator<T> alloc; + + globalMemCounter.reset(); + Container<T, ThrowingAllocator<T>> c(alloc); + c.append_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(globalMemCounter.new_called == globalMemCounter.delete_called); + } +#endif +} + +template <template <class ...> class Container> +void test_assign_range_exception_safety_throwing_copy() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + using T = ThrowingCopy<3>; + T::reset(); + T in[5]; + + try { + Container<T> c; + c.assign_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(T::created_by_copying == 3); + assert(T::destroyed == 2); // No destructor call for the partially-constructed element. + } +#endif +} + +template <template <class ...> class Container, class T> +void test_assign_range_exception_safety_throwing_allocator() { +#if !defined(TEST_HAS_NO_EXCEPTIONS) + T in[] = {0, 1}; + + try { + ThrowingAllocator<T> alloc; + + globalMemCounter.reset(); + Container<T, ThrowingAllocator<T>> c(alloc); + c.assign_range(in); + assert(false); // The function call above should throw. + + } catch (int) { + assert(globalMemCounter.new_called == globalMemCounter.delete_called); + } +#endif +} + +#endif // SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H diff --git a/libcxx/test/std/containers/sequences/vector.bool/append_range.pass.cpp b/libcxx/test/std/containers/sequences/vector.bool/append_range.pass.cpp new file mode 100644 index 000000000000..e76f9bcd3110 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/append_range.pass.cpp @@ -0,0 +1,72 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<bool> R> +// constexpr void append_range(R&& rg); // C++23 + +#include <vector> + +#include "../insert_range_sequence_containers.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of insertions (appending an {empty/one-element/mid-sized/long range} into an +// {empty/one-element/full} container); +// - an exception is thrown when allocating new elements. +constexpr bool test() { + static_assert(test_constraints_append_range<std::vector, bool, char>()); + + for_all_iterators_and_allocators<bool, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_append_range<std::vector<bool, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + // `is_contiguous_container_asan_correct` doesn't work on `vector<bool>`. + }); + }); + + { // Vector may or may not need to reallocate because of the insertion -- make sure to test both cases. + { // Ensure reallocation happens. + constexpr int N = 255; + bool in[N] = {}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + auto initial = v; + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.append_range(in); + // Because `in` is very large (it has to be to exceed the large capacity that `vector<bool>` allocates), it is + // impractical to have the expected value as a literal. + assert(v.size() == initial.size() + N); + assert(std::ranges::equal(v.begin(), v.begin() + initial.size(), initial.begin(), initial.end())); + assert(std::ranges::equal(v.begin() + initial.size(), v.end(), std::ranges::begin(in), std::ranges::end(in))); + } + + { // Ensure no reallocation happens. + bool in[] = {1, 1, 1, 1, 0, 0, 1, 1, 1, 1}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + v.reserve(v.size() + std::ranges::size(in)); + assert(v.capacity() >= v.size() + std::ranges::size(in)); + + v.append_range(in); + assert(std::ranges::equal(v, std::vector<bool>{0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + // Note: `test_append_range_exception_safety_throwing_copy` doesn't apply because copying booleans cannot throw. + test_append_range_exception_safety_throwing_allocator<std::vector, bool>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector.bool/assign_range.pass.cpp b/libcxx/test/std/containers/sequences/vector.bool/assign_range.pass.cpp new file mode 100644 index 000000000000..6ae5aa46d6cc --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/assign_range.pass.cpp @@ -0,0 +1,65 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<bool> R> +// constexpr void assign_range(R&& rg); // C++23 + +#include <vector> + +#include "../insert_range_sequence_containers.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of assignments (assigning an {empty/one-element/mid-sized/long range} to an +// {empty/one-element/full} container); +// - an exception is thrown when allocating new elements. +constexpr bool test() { + static_assert(test_constraints_assign_range<std::vector, bool, char>()); + + for_all_iterators_and_allocators<bool, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_assign_range<std::vector<bool, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + // `is_contiguous_container_asan_correct` doesn't work on `vector<bool>`. + }); + }); + + { // Vector may or may not need to reallocate because of the assignment -- make sure to test both cases. + { // Ensure reallocation happens. Note that `vector<bool>` typically reserves a lot of capacity. + constexpr int N = 255; + bool in[N] = {}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.assign_range(in); + assert(std::ranges::equal(v, in)); + } + + { // Ensure no reallocation happens. + bool in[] = {1, 1, 0, 1, 1}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + + v.assign_range(in); + assert(std::ranges::equal(v, in)); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + // Note: `test_assign_range_exception_safety_throwing_copy` doesn't apply because copying booleans cannot throw. + test_assign_range_exception_safety_throwing_allocator<std::vector, bool>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector.bool/construct_from_range.pass.cpp b/libcxx/test/std/containers/sequences/vector.bool/construct_from_range.pass.cpp new file mode 100644 index 000000000000..d1f0bf06ed57 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/construct_from_range.pass.cpp @@ -0,0 +1,40 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 + +#include <vector> + +#include "../from_range_sequence_containers.h" +#include "test_macros.h" + +// template<container-compatible-range<T> R> +// vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 + +constexpr bool test() { + for_all_iterators_and_allocators<bool>([]<class Iter, class Sent, class Alloc>() { + test_vector_bool<Iter, Sent, Alloc>([](const auto& c) { + LIBCPP_ASSERT(c.__invariants()); + // `is_contiguous_container_asan_correct` doesn't work on `vector<bool>`. + }); + }); + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + static_assert(test_constraints<std::vector, bool, char>()); + + // Note: test_exception_safety_throwing_copy doesn't apply because copying a boolean cannot throw. + test_exception_safety_throwing_allocator<std::vector, bool>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector.bool/insert_range.pass.cpp b/libcxx/test/std/containers/sequences/vector.bool/insert_range.pass.cpp new file mode 100644 index 000000000000..260a1037173e --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/insert_range.pass.cpp @@ -0,0 +1,72 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<bool> R> +// constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 + +#include <vector> + +#include "../insert_range_sequence_containers.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of insertions (inserting an {empty/one-element/mid-sized/long range} into an +// {empty/one-element/full} container at the {beginning/middle/end}); +// - an exception is thrown when allocating new elements. +constexpr bool test() { + static_assert(test_constraints_insert_range<std::vector, bool, char>()); + + for_all_iterators_and_allocators<bool, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_insert_range<std::vector<bool, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + // `is_contiguous_container_asan_correct` doesn't work on `vector<bool>`. + }); + }); + + { // Vector may or may not need to reallocate because of the insertion -- make sure to test both cases. + { // Ensure reallocation happens. + constexpr int N = 255; + bool in[N] = {}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + auto initial = v; + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.insert_range(v.end(), in); + // Because `in` is very large (it has to be to exceed the large capacity that `vector<bool>` allocates), it is + // impractical to have the expected value as a literal. + assert(v.size() == initial.size() + N); + assert(std::ranges::equal(v.begin(), v.begin() + initial.size(), initial.begin(), initial.end())); + assert(std::ranges::equal(v.begin() + initial.size(), v.end(), std::ranges::begin(in), std::ranges::end(in))); + } + + { // Ensure no reallocation happens. + bool in[] = {1, 1, 1, 1, 0, 0, 1, 1, 1, 1}; + std::vector<bool> v = {0, 0, 0, 1, 1, 0, 0, 0}; + v.reserve(v.size() + std::ranges::size(in)); + assert(v.capacity() >= v.size() + std::ranges::size(in)); + + v.insert_range(v.end(), in); + assert(std::ranges::equal(v, std::vector<bool>{0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + // Note: `test_insert_range_exception_safety_throwing_copy` doesn't apply because copying booleans cannot throw. + test_insert_range_exception_safety_throwing_allocator<std::vector, bool>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector/vector.cons/construct_from_range.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.cons/construct_from_range.pass.cpp new file mode 100644 index 000000000000..2acdcc35da6f --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector/vector.cons/construct_from_range.pass.cpp @@ -0,0 +1,42 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 + +// template<container-compatible-range<T> R> +// vector(from_range_t, R&& rg, const Allocator& = Allocator()); // C++23 + +#include <vector> + +#include "../../from_range_sequence_containers.h" +#include "asan_testing.h" +#include "test_macros.h" + +constexpr bool test() { + for_all_iterators_and_allocators<int>([]<class Iter, class Sent, class Alloc>() { + test_sequence_container<std::vector, int, Iter, Sent, Alloc>([](const auto& c) { + LIBCPP_ASSERT(c.__invariants()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + test_sequence_container_move_only<std::vector>(); + + return true; +} + +int main(int, char**) { + static_assert(test_constraints<std::vector, int, double>()); + test(); + + static_assert(test()); + + test_exception_safety_throwing_copy<std::vector>(); + test_exception_safety_throwing_allocator<std::vector, int>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector/vector.cons/deduct.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.cons/deduct.pass.cpp index 7902ed7ca6b8..322161d51750 100644 --- a/libcxx/test/std/containers/sequences/vector/vector.cons/deduct.pass.cpp +++ b/libcxx/test/std/containers/sequences/vector/vector.cons/deduct.pass.cpp @@ -13,14 +13,18 @@ // vector(InputIterator, InputIterator, Allocator = Allocator()) // -> vector<typename iterator_traits<InputIterator>::value_type, Allocator>; // +// template<ranges::input_range R, class Allocator = allocator<ranges::range_value_t<R>>> +// vector(from_range_t, R&&, Allocator = Allocator()) +// -> vector<ranges::range_value_t<R>, Allocator>; // C++23 #include <algorithm> -#include <vector> +#include <array> #include <cassert> -#include <cstddef> #include <climits> // INT_MAX +#include <cstddef> #include <iterator> #include <type_traits> +#include <vector> #include "deduction_guides_sfinae_checks.h" #include "test_macros.h" @@ -94,6 +98,20 @@ TEST_CONSTEXPR_CXX20 bool tests() { assert(vec.size() == 0); } +#if TEST_STD_VER >= 23 + { + { + std::vector c(std::from_range, std::array<int, 0>()); + static_assert(std::is_same_v<decltype(c), std::vector<int>>); + } + + { + using Alloc = test_allocator<int>; + std::vector c(std::from_range, std::array<int, 0>(), Alloc()); + static_assert(std::is_same_v<decltype(c), std::vector<int, Alloc>>); + } + } +#endif // A couple of vector<bool> tests, too! { diff --git a/libcxx/test/std/containers/sequences/vector/vector.cons/exceptions.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.cons/exceptions.pass.cpp index aa743ad55152..3ef5aeecc1b0 100644 --- a/libcxx/test/std/containers/sequences/vector/vector.cons/exceptions.pass.cpp +++ b/libcxx/test/std/containers/sequences/vector/vector.cons/exceptions.pass.cpp @@ -177,6 +177,7 @@ int main(int, char**) { Allocator<int> alloc(false); AllocVec vec(cpp17_input_iterator<int*>(a), cpp17_input_iterator<int*>(a + 2), alloc); } catch (int) { + // FIXME: never called. } check_new_delete_called(); @@ -185,6 +186,7 @@ int main(int, char**) { Allocator<int> alloc(false); AllocVec vec(forward_iterator<int*>(a), forward_iterator<int*>(a + 2), alloc); } catch (int) { + // FIXME: never called. } check_new_delete_called(); diff --git a/libcxx/test/std/containers/sequences/vector/vector.modifiers/append_range.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.modifiers/append_range.pass.cpp new file mode 100644 index 000000000000..0a9453428753 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector/vector.modifiers/append_range.pass.cpp @@ -0,0 +1,70 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<T> R> +// constexpr void append_range(R&& rg); // C++23 + +#include <vector> + +#include "../../insert_range_sequence_containers.h" +#include "asan_testing.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of insertions (appending an {empty/one-element/mid-sized/long range} into an +// {empty/one-element/full} container); +// - appending move-only elements; +// - an exception is thrown when copying the elements or when allocating new elements. +constexpr bool test() { + static_assert(test_constraints_append_range<std::vector, int, double>()); + + for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_append_range<std::vector<int, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + test_sequence_append_range_move_only<std::vector>(); + + { // Vector may or may not need to reallocate because of the insertion -- make sure to test both cases. + { // Ensure reallocation happens. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + v.shrink_to_fit(); + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.append_range(in); + assert(std::ranges::equal(v, std::array{1, 2, 3, 4, 5, 6, 7, 8, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10})); + } + + { // Ensure no reallocation happens. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + v.reserve(v.size() + std::ranges::size(in)); + assert(v.capacity() >= v.size() + std::ranges::size(in)); + + v.append_range(in); + assert(std::ranges::equal(v, std::array{1, 2, 3, 4, 5, 6, 7, 8, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + test_append_range_exception_safety_throwing_copy<std::vector>(); + test_append_range_exception_safety_throwing_allocator<std::vector, int>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector/vector.modifiers/assign_range.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.modifiers/assign_range.pass.cpp new file mode 100644 index 000000000000..891c6df4474d --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector/vector.modifiers/assign_range.pass.cpp @@ -0,0 +1,78 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<T> R> +// constexpr void assign_range(R&& rg); // C++23 + +#include <vector> + +#include "../../insert_range_sequence_containers.h" +#include "asan_testing.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of assignments (assigning an {empty/one-element/mid-sized/long range} to an +// {empty/one-element/full} container); +// - assigning move-only elements; +// - an exception is thrown when copying the elements or when allocating new elements. +constexpr bool test() { + static_assert(test_constraints_assign_range<std::vector, int, double>()); + + for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_assign_range<std::vector<int, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + test_sequence_assign_range_move_only<std::vector>(); + + { // Vector may or may not need to reallocate because of the assignment -- make sure to test both cases. + { // Ensure reallocation happens. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + v.shrink_to_fit(); + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.assign_range(in); + assert(std::ranges::equal(v, in)); + } + + { // Ensure no reallocation happens -- the input range is shorter than the vector. + int in[] = {-1, -2, -3, -4, -5}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + + v.assign_range(in); + assert(std::ranges::equal(v, in)); + } + + { // Ensure no reallocation happens -- the input range is longer than the vector but within capacity. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8}; + std::vector<int> v = {1, 2, 3, 4, 5}; + v.reserve(std::ranges::size(in)); + assert(v.capacity() >= std::ranges::size(in)); + + v.assign_range(in); + assert(std::ranges::equal(v, in)); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + test_assign_range_exception_safety_throwing_copy<std::vector>(); + test_assign_range_exception_safety_throwing_allocator<std::vector, int>(); + + return 0; +} diff --git a/libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_range.pass.cpp b/libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_range.pass.cpp new file mode 100644 index 000000000000..3b900ce73e98 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector/vector.modifiers/insert_range.pass.cpp @@ -0,0 +1,71 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 +// ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000 + +// template<container-compatible-range<T> R> +// constexpr iterator insert_range(const_iterator position, R&& rg); // C++23 + +#include <vector> + +#include "../../insert_range_sequence_containers.h" +#include "asan_testing.h" +#include "test_macros.h" + +// Tested cases: +// - different kinds of insertions (inserting an {empty/one-element/mid-sized/long range} into an +// {empty/one-element/full} container at the {beginning/middle/end}); +// - inserting move-only elements; +// - an exception is thrown when copying the elements or when allocating new elements. + +constexpr bool test() { + for_all_iterators_and_allocators<int, const int*>([]<class Iter, class Sent, class Alloc>() { + test_sequence_insert_range<std::vector<int, Alloc>, Iter, Sent>([](auto&& c) { + LIBCPP_ASSERT(c.__invariants()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + test_sequence_insert_range_move_only<std::vector>(); + + { // Vector may or may not need to reallocate because of the insertion -- make sure to test both cases. + { // Ensure reallocation happens. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + v.shrink_to_fit(); + assert(v.capacity() < v.size() + std::ranges::size(in)); + + v.insert_range(v.end(), in); + assert(std::ranges::equal(v, std::array{1, 2, 3, 4, 5, 6, 7, 8, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10})); + } + + { // Ensure no reallocation happens. + int in[] = {-1, -2, -3, -4, -5, -6, -7, -8, -9, -10}; + std::vector<int> v = {1, 2, 3, 4, 5, 6, 7, 8}; + v.reserve(v.size() + std::ranges::size(in)); + assert(v.capacity() >= v.size() + std::ranges::size(in)); + + v.insert_range(v.end(), in); + assert(std::ranges::equal(v, std::array{1, 2, 3, 4, 5, 6, 7, 8, -1, -2, -3, -4, -5, -6, -7, -8, -9, -10})); + } + } + + return true; +} + +int main(int, char**) { + test(); + static_assert(test()); + + static_assert(test_constraints_insert_range<std::vector, int, double>()); + + test_insert_range_exception_safety_throwing_copy<std::vector>(); + test_insert_range_exception_safety_throwing_allocator<std::vector, int>(); + + return 0; +} diff --git a/libcxx/test/std/ranges/range.utility/range.utility.conv/from_range_t.compile.pass.cpp b/libcxx/test/std/ranges/range.utility/range.utility.conv/from_range_t.compile.pass.cpp new file mode 100644 index 000000000000..b64d28350791 --- /dev/null +++ b/libcxx/test/std/ranges/range.utility/range.utility.conv/from_range_t.compile.pass.cpp @@ -0,0 +1,25 @@ +//===----------------------------------------------------------------------===// +// +// 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, c++17, c++20 + +// struct from_range_t { explicit from_range_t() = default; }; // Since C++23 +// inline constexpr from_range_t from_range{}; // Since C++23 + +#include <ranges> + +template <class T> +void check(std::from_range_t); + +template <class T> +concept IsCtrNonexplicit = requires { + check<T>({}); +}; + +// Verify that the constructor is `explicit`. +static_assert(!IsCtrNonexplicit<std::from_range_t>); diff --git a/libcxx/test/support/deduction_guides_sfinae_checks.h b/libcxx/test/support/deduction_guides_sfinae_checks.h index 5ada5ac28e8c..a811322c1a5e 100644 --- a/libcxx/test/support/deduction_guides_sfinae_checks.h +++ b/libcxx/test/support/deduction_guides_sfinae_checks.h @@ -18,6 +18,25 @@ #include <utility> #include "test_macros.h" +#if TEST_STD_VER >= 23 +#include "almost_satisfies_types.h" +#endif + +#if TEST_STD_VER >= 23 + +template <class T> +struct RangeT { + T* begin(); + T* end(); +}; +static_assert(std::ranges::input_range<RangeT<int>>); + +template <class T> +using BadRangeT = InputRangeNotDerivedFromGeneric<T>; +static_assert(std::ranges::range<BadRangeT<int>>); +static_assert(!std::ranges::input_range<BadRangeT<int>>); + +#endif // `SFINAEs_away` template variable checks whether the template arguments for // a given template class `Instantiated` can be deduced from the given @@ -34,17 +53,20 @@ template<template<typename ...> class Instantiated, class ...CtrArgs> constexpr bool SFINAEs_away = decltype(SFINAEs_away_impl<Instantiated, CtrArgs...>(0))::value; +struct Empty {}; + // For sequence containers the deduction guides should be SFINAE'd away when // given: // - "bad" input iterators (that is, a type not qualifying as an input // iterator); -// - a bad allocator. -template<template<typename ...> class Container, typename InstantiatedContainer> +// - a bad allocator; +// - a range not satisfying the `input_range` concept. +template<template<typename ...> class Container, typename InstantiatedContainer, typename BadAlloc = Empty> constexpr void SequenceContainerDeductionGuidesSfinaeAway() { - using Alloc = std::allocator<int>; - using Iter = int*; + using T = typename InstantiatedContainer::value_type; + using Alloc = std::allocator<T>; + using Iter = T*; - struct BadAlloc {}; // Note: the only requirement in the Standard is that integral types cannot be // considered input iterators; however, this doesn't work for sequence // containers because they have constructors of the form `(size_type count, @@ -70,6 +92,20 @@ constexpr void SequenceContainerDeductionGuidesSfinaeAway() { // // Cannot deduce from (alloc) static_assert(SFINAEs_away<Container, Alloc>); + +#if TEST_STD_VER >= 23 + using BadRange = BadRangeT<T>; + + // (from_range, range) + // + // Cannot deduce from (BAD_range) + static_assert(SFINAEs_away<Container, std::from_range_t, BadRange>); + + // (from_range, range, alloc) + // + // Cannot deduce from (range, BAD_alloc) + static_assert(SFINAEs_away<Container, std::from_range_t, RangeT<int>, BadAlloc>); +#endif } // For associative containers the deduction guides should be SFINAE'd away when |