diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -352,7 +352,7 @@ ------------------------------------------------- ----------------- ``__cpp_lib_ranges_starts_ends_with`` *unimplemented* ------------------------------------------------- ----------------- - ``__cpp_lib_ranges_to_container`` *unimplemented* + ``__cpp_lib_ranges_to_container`` ``202202L`` ------------------------------------------------- ----------------- ``__cpp_lib_ranges_zip`` *unimplemented* ------------------------------------------------- ----------------- diff --git a/libcxx/docs/ReleaseNotes.rst b/libcxx/docs/ReleaseNotes.rst --- a/libcxx/docs/ReleaseNotes.rst +++ b/libcxx/docs/ReleaseNotes.rst @@ -37,6 +37,7 @@ Implemented Papers ------------------ +- P1206R7 - ``ranges::to``: A function to convert any range to a container - P2520R0 - ``move_iterator`` should be a random access iterator - P1328R1 - ``constexpr type_info::operator==()`` - P1413R3 - Formatting ``thread::id`` (the ``stacktrace`` is not done yet) diff --git a/libcxx/docs/Status/Cxx2bIssues.csv b/libcxx/docs/Status/Cxx2bIssues.csv --- a/libcxx/docs/Status/Cxx2bIssues.csv +++ b/libcxx/docs/Status/Cxx2bIssues.csv @@ -258,7 +258,7 @@ "`3820 `__","``cartesian_product_view::iterator::prev`` is not quite right","February 2023","","","|ranges|" "`3825 `__","Missing compile-time argument ``id`` check in ``basic_format_parse_context::next_arg_id``","February 2023","|Complete|","17.0","|format|" "`3204 `__","``sub_match::swap`` only swaps the base class","February 2023","|Complete|","17.0","" -"`3733 `__","``ranges::to`` misuses ``cpp17-input-iterator``","February 2023","","","|ranges|" +"`3733 `__","``ranges::to`` misuses ``cpp17-input-iterator``","February 2023","|Complete|","17.0","|ranges|" "`3742 `__","``deque::prepend_range`` needs to permute","February 2023","","","|ranges|" "`3790 `__","`P1467 `__ accidentally changed ``nexttoward``'s signature","February 2023","","","" "`3819 `__","``reference_meows_from_temporary`` should not use ``is_meowible``","February 2023","","","" @@ -292,7 +292,7 @@ "`3833 `__","Remove specialization ``template struct formatter``","February 2023","|Complete|","17.0","|format|" "`3836 `__","``std::expected`` conversion constructor ``expected(const expected&)`` should take precedence over ``expected(U&&)`` with operator ``bool``","February 2023","","","" "`3843 `__","``std::expected::value() &`` assumes ``E`` is copy constructible","February 2023","","","" -"`3847 `__","``ranges::to`` can still return views","February 2023","","","|ranges|" +"`3847 `__","``ranges::to`` can still return views","February 2023","|Complete|","17.0","|ranges|" "`3862 `__","``basic_const_iterator``'s ``common_type`` specialization is underconstrained","February 2023","","","" "`3865 `__","Sorting a range of ``pairs``","February 2023","|Complete|","17.0","|ranges|" "`3869 `__","Deprecate ``std::errc`` constants related to UNIX STREAMS","February 2023","","","" 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 `__","LWG","``std::expected``","February 2022","|Complete|","16.0" "`P0533R9 `__","LWG","``constexpr`` for ```` and ````","February 2022","|In progress| [#note-P0533R9]_","" "`P0627R6 `__","LWG","Function to mark unreachable code","February 2022","|Complete|","15.0" -"`P1206R7 `__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","","","|ranges|" +"`P1206R7 `__","LWG","``ranges::to``: A function to convert any range to a container","February 2022","|Complete|","17.0","|ranges|" "`P1413R3 `__","LWG","Deprecate ``std::aligned_storage`` and ``std::aligned_union``","February 2022","|Complete| [#note-P1413R3]_","" "`P2255R2 `__","LWG","A type trait to detect reference binding to temporary","February 2022","","" "`P2273R3 `__","LWG","Making ``std::unique_ptr`` constexpr","February 2022","|Complete|","16.0" diff --git a/libcxx/docs/Status/RangesMajorFeatures.csv b/libcxx/docs/Status/RangesMajorFeatures.csv --- a/libcxx/docs/Status/RangesMajorFeatures.csv +++ b/libcxx/docs/Status/RangesMajorFeatures.csv @@ -1,4 +1,4 @@ Standard,Name,Assignee,CL,Status -C++23,`ranges::to `_,Unassigned,No patch yet,Not started +C++23,`ranges::to `_,Konstantin Varlamov,`D142335 `_,Complete C++23,`Pipe support for user-defined range adaptors `_,Unassigned,No patch yet,Not started C++23,`Formatting Ranges `_,Mark de Wever,Various,Complete diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -438,6 +438,7 @@ __iterator/permutable.h __iterator/prev.h __iterator/projected.h + __iterator/ranges_iterator_traits.h __iterator/readable_traits.h __iterator/reverse_access.h __iterator/reverse_iterator.h @@ -581,6 +582,7 @@ __ranges/as_rvalue_view.h __ranges/common_view.h __ranges/concepts.h + __ranges/container_compatible_range.h __ranges/copyable_box.h __ranges/counted.h __ranges/dangling.h @@ -593,6 +595,7 @@ __ranges/enable_borrowed_range.h __ranges/enable_view.h __ranges/filter_view.h + __ranges/from_range.h __ranges/iota_view.h __ranges/istream_view.h __ranges/join_view.h @@ -610,6 +613,7 @@ __ranges/subrange.h __ranges/take_view.h __ranges/take_while_view.h + __ranges/to.h __ranges/transform_view.h __ranges/view_interface.h __ranges/views.h diff --git a/libcxx/include/__algorithm/copy_n.h b/libcxx/include/__algorithm/copy_n.h --- a/libcxx/include/__algorithm/copy_n.h +++ b/libcxx/include/__algorithm/copy_n.h @@ -10,10 +10,13 @@ #define _LIBCPP___ALGORITHM_COPY_N_H #include <__algorithm/copy.h> +#include <__algorithm/iterator_operations.h> #include <__config> #include <__iterator/iterator_traits.h> #include <__type_traits/enable_if.h> #include <__utility/convert_to_integral.h> +#include <__utility/move.h> +#include <__utility/pair.h> #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) # pragma GCC system_header @@ -21,45 +24,53 @@ _LIBCPP_BEGIN_NAMESPACE_STD -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 typename enable_if < __is_cpp17_input_iterator<_InputIterator>::value && !__is_cpp17_random_access_iterator<_InputIterator>::value, - _OutputIterator + pair<_InputIterator, _OutputIterator> >::type -copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) +__copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) { typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; if (__n > 0) { *__result = *__first; + ++__first; ++__result; for (--__n; __n > 0; --__n) { - ++__first; *__result = *__first; + ++__first; ++__result; } } - return __result; + return std::make_pair(std::move(__first), std::move(__result)); } -template +template inline _LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_SINCE_CXX20 typename enable_if < __is_cpp17_random_access_iterator<_InputIterator>::value, - _OutputIterator + pair<_InputIterator, _OutputIterator> >::type -copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) +__copy_n(_InputIterator __first, _Size __orig_n, _OutputIterator __result) { - typedef typename iterator_traits<_InputIterator>::difference_type difference_type; + using difference_type = typename _IterOps<_AlgPolicy>:: template __difference_type<_InputIterator>; typedef decltype(_VSTD::__convert_to_integral(__orig_n)) _IntegralSize; _IntegralSize __n = __orig_n; - return _VSTD::copy(__first, __first + difference_type(__n), __result); + return std::__copy<_AlgPolicy>(__first, __first + difference_type(__n), __result); +} + +template +inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_SINCE_CXX20 +_OutputIterator copy_n(_InputIterator __first, _Size __n, _OutputIterator __result) +{ + return std::__copy_n<_ClassicAlgPolicy>(std::move(__first), __n, std::move(__result)).second; } _LIBCPP_END_NAMESPACE_STD diff --git a/libcxx/include/__iterator/ranges_iterator_traits.h b/libcxx/include/__iterator/ranges_iterator_traits.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__iterator/ranges_iterator_traits.h @@ -0,0 +1,42 @@ +// -*- 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___ITERATOR_RANGES_ITERATOR_TRAITS_H +#define _LIBCPP___ITERATOR_RANGES_ITERATOR_TRAITS_H + +#include <__config> +#include <__fwd/pair.h> +#include <__ranges/concepts.h> +#include <__type_traits/add_const.h> +#include <__type_traits/remove_const.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +template +using __range_key_type = remove_const_t::first_type>; + +template +using __range_mapped_type = typename ranges::range_value_t<_Range>::second_type; + +template +using __range_to_alloc_type = + pair::first_type>, + typename ranges::range_value_t<_Range>::second_type>; + +#endif + +_LIBCPP_END_NAMESPACE_STD + +#endif // _LIBCPP___ITERATOR_RANGES_ITERATOR_TRAITS_H 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 +concept _ContainerCompatibleRange = + ranges::input_range<_Range> && convertible_to, _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/__ranges/to.h b/libcxx/include/__ranges/to.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__ranges/to.h @@ -0,0 +1,246 @@ +// -*- 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_TO_H +#define _LIBCPP___RANGES_TO_H + +#include <__algorithm/ranges_copy.h> +#include <__concepts/constructible.h> +#include <__concepts/convertible_to.h> +#include <__concepts/derived_from.h> +#include <__concepts/same_as.h> +#include <__config> +#include <__functional/bind_back.h> +#include <__iterator/back_insert_iterator.h> +#include <__iterator/insert_iterator.h> +#include <__iterator/iterator_traits.h> +#include <__ranges/access.h> +#include <__ranges/concepts.h> +#include <__ranges/from_range.h> +#include <__ranges/range_adaptor.h> +#include <__ranges/size.h> +#include <__ranges/transform_view.h> +#include <__type_traits/add_pointer.h> +#include <__type_traits/is_const.h> +#include <__type_traits/is_volatile.h> +#include <__type_traits/type_identity.h> +#include <__utility/declval.h> +#include <__utility/forward.h> +#include + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +namespace ranges { + +template +constexpr bool __reservable_container = sized_range<_Container> && + requires(_Container& __c, range_size_t<_Container> __n) { + __c.reserve(__n); + { __c.capacity() } -> same_as; + { __c.max_size() } -> same_as; +}; + +template +constexpr bool __container_insertable = requires(_Container& __c, _Ref&& __ref) { + requires( + requires { __c.push_back(std::forward<_Ref>(__ref)); } || + requires { __c.insert(__c.end(), std::forward<_Ref>(__ref)); }); +}; + +template +_LIBCPP_HIDE_FROM_ABI constexpr auto __container_inserter(_Container& __c) { + if constexpr (requires { __c.push_back(std::declval<_Ref>()); }) { + return std::back_inserter(__c); + } else { + return std::inserter(__c, __c.end()); + } +} + +template +concept __try_non_recursive_conversion = + !input_range<_Container> || convertible_to, range_value_t<_Container>>; + +template +concept __constructible_from_iter_pair = common_range<_Range> && requires { + typename iterator_traits>::iterator_category; +} && derived_from>::iterator_category, input_iterator_tag> && + constructible_from<_Container, iterator_t<_Range>, sentinel_t<_Range>, _Args...>; + +template +concept __always_false = false; + +// `ranges::to` base template -- the `_Container` type is a simple type template parameter. +template + requires(!view<_Container>) +_LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr _Container to(_Range&& __range, _Args&&... __args) { + // Mandates: C is a cv-unqualified class type. + static_assert(!is_const_v<_Container>, "The target container cannot be const-qualified, please remove the const"); + static_assert(!is_volatile_v<_Container>, + "The target container cannot be volatile-qualified, please remove the volatile"); + + // First see if the non-recursive case applies -- the conversion target is either: + // - a range with a convertible value type; + // - a non-range type which might support being created from the input argument(s) (e.g. an `optional`). + if constexpr (__try_non_recursive_conversion<_Container, _Range>) { + // Case 1 -- construct directly from the given range. + if constexpr (constructible_from<_Container, _Range, _Args...>) { + return _Container(std::forward<_Range>(__range), std::forward<_Args>(__args)...); + } + + // Case 2 -- construct using the `from_range_t` tagged constructor. + else if constexpr (constructible_from<_Container, from_range_t, _Range, _Args...>) { + return _Container(from_range, std::forward<_Range>(__range), std::forward<_Args>(__args)...); + } + + // Case 3 -- construct from a begin-end iterator pair. + else if constexpr (__constructible_from_iter_pair<_Container, _Range, _Args...>) { + return _Container(ranges::begin(__range), ranges::end(__range), std::forward<_Args>(__args)...); + } + + // Case 4 -- default-construct (or construct from the extra arguments) and insert, reserving the size if possible. + else if constexpr (constructible_from<_Container, _Args...> && + __container_insertable<_Container, range_reference_t<_Range>>) { + _Container __result(std::forward<_Args>(__args)...); + if constexpr (sized_range<_Range> && __reservable_container<_Container>) { + __result.reserve(static_cast>(ranges::size(__range))); + } + + ranges::copy(__range, __container_inserter>(__result)); + + return __result; + + } else { + static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type."); + } + + // Try the recursive case. + } else if constexpr (input_range>) { + return ranges::to<_Container>( + __range | views::transform([](auto&& __elem) { + return ranges::to>(std::forward(__elem)); + }), + std::forward<_Args>(__args)...); + + } else { + static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type."); + } +} + +template +struct __minimal_input_iterator { + using iterator_category = input_iterator_tag; + using value_type = range_value_t<_Range>; + using difference_type = ptrdiff_t; + using pointer = add_pointer_t>; + using reference = range_reference_t<_Range>; + + reference operator*() const; + pointer operator->() const; + __minimal_input_iterator& operator++(); + __minimal_input_iterator operator++(int); + bool operator==(const __minimal_input_iterator&) const; +}; + +// Deduces the full type of the container from the given template template parameter. +template