diff --git a/libcxx/docs/Status/Cxx2bPapers.csv b/libcxx/docs/Status/Cxx2bPapers.csv --- 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/__ranges/container_compatible_range.h b/libcxx/include/__ranges/container_compatible_range.h new file mode 100644 --- /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 <__config> +#include <__concepts/convertible_to.h> +#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 --- /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 { + _LIBCPP_HIDE_FROM_ABI 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 --- a/libcxx/include/__split_buffer +++ b/libcxx/include/__split_buffer @@ -170,6 +170,14 @@ __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 @@ _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 @@ ++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/vector b/libcxx/include/vector --- a/libcxx/include/vector +++ b/libcxx/include/vector @@ -41,6 +41,8 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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 @@ 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); @@ -282,6 +302,7 @@ #include <__algorithm/equal.h> #include <__algorithm/fill_n.h> #include <__algorithm/lexicographical_compare.h> +#include <__algorithm/iterator_operations.h> #include <__algorithm/remove.h> #include <__algorithm/remove_if.h> #include <__algorithm/rotate.h> @@ -296,6 +317,7 @@ #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> @@ -306,6 +328,11 @@ #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> @@ -435,6 +462,20 @@ _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: @@ -500,6 +541,20 @@ 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 @@ -602,6 +657,14 @@ 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(); @@ -621,6 +684,20 @@ _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 && @@ -700,9 +777,51 @@ _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); @@ -909,6 +1028,15 @@ -> 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 @@ -1023,10 +1151,9 @@ } 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_); } @@ -1123,11 +1250,7 @@ _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> @@ -1138,11 +1261,7 @@ 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> @@ -1152,15 +1271,8 @@ _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> @@ -1171,15 +1283,8 @@ 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> @@ -1187,15 +1292,7 @@ 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> @@ -1203,15 +1300,7 @@ 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> @@ -1355,6 +1444,13 @@ _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); @@ -1367,22 +1463,27 @@ _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 { @@ -1812,7 +1913,6 @@ } 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, @@ -1820,8 +1920,17 @@ _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(); @@ -1837,7 +1946,7 @@ 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())); @@ -1865,17 +1974,27 @@ _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) { @@ -1895,7 +2014,7 @@ { 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); } } @@ -2143,6 +2262,23 @@ _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); @@ -2182,6 +2318,20 @@ >::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 @@ -2271,6 +2421,14 @@ } #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 @@ -2294,6 +2452,20 @@ >::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) @@ -2331,6 +2503,53 @@ 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 @@ -2357,13 +2576,9 @@ {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 @@ -2493,17 +2708,11 @@ } 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) @@ -2511,7 +2720,7 @@ 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> @@ -2605,22 +2814,7 @@ __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> @@ -2632,22 +2826,7 @@ __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> @@ -2659,14 +2838,8 @@ __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> @@ -2678,14 +2851,8 @@ __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 @@ -2701,7 +2868,7 @@ if (__n > 0) { __vallocate(__n); - __construct_at_end(__il.begin(), __il.end()); + __construct_at_end(__il.begin(), __il.end(), __il.size()); } } @@ -2716,7 +2883,7 @@ if (__n > 0) { __vallocate(__n); - __construct_at_end(__il.begin(), __il.end()); + __construct_at_end(__il.begin(), __il.end(), __il.size()); } } @@ -2732,7 +2899,7 @@ if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2746,7 +2913,7 @@ if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2805,7 +2972,7 @@ else if (__v.size() > 0) { __vallocate(__v.size()); - __construct_at_end(__v.begin(), __v.end()); + __construct_at_end(__v.begin(), __v.end(), __v.size()); } } @@ -2873,6 +3040,13 @@ >::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); @@ -2888,9 +3062,17 @@ >::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) { @@ -2899,7 +3081,7 @@ __vdeallocate(); __vallocate(__n); } - __construct_at_end(__first, __last); + __construct_at_end(__first, __last, __n); } } @@ -2913,7 +3095,7 @@ 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); } @@ -3025,6 +3207,14 @@ >::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(); @@ -3040,7 +3230,7 @@ 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())); @@ -3070,7 +3260,15 @@ >::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; @@ -3091,7 +3289,7 @@ 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/std/containers/from_range_helpers.h b/libcxx/test/std/containers/from_range_helpers.h new file mode 100644 --- /dev/null +++ b/libcxx/test/std/containers/from_range_helpers.h @@ -0,0 +1,148 @@ +//===----------------------------------------------------------------------===// +// +// 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; + } + } + + 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 --- /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 --- /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 --- /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 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/append_range.pass.cpp @@ -0,0 +1,73 @@ +//===----------------------------------------------------------------------===// +// +// 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 "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); +// - 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()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + + { // 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 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/assign_range.pass.cpp @@ -0,0 +1,66 @@ +//===----------------------------------------------------------------------===// +// +// 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 "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); +// - 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()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + + { // 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 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/construct_from_range.pass.cpp @@ -0,0 +1,41 @@ +//===----------------------------------------------------------------------===// +// +// 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 "asan_testing.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()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + + 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 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector.bool/insert_range.pass.cpp @@ -0,0 +1,73 @@ +//===----------------------------------------------------------------------===// +// +// 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 "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}); +// - 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()); + LIBCPP_ASSERT(is_contiguous_container_asan_correct(c)); + }); + }); + + { // 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 --- /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 --- 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 @@ 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 --- 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 @@ 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 @@ 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 --- /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 --- /dev/null +++ b/libcxx/test/std/containers/sequences/vector/vector.modifiers/assign_range.pass.cpp @@ -0,0 +1,68 @@ +//===----------------------------------------------------------------------===// +// +// 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. + 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)); + } + } + + 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 --- /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/support/deduction_guides_sfinae_checks.h b/libcxx/test/support/deduction_guides_sfinae_checks.h --- 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 @@ 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 @@ // // 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