diff --git a/libcxx/docs/FeatureTestMacroTable.rst b/libcxx/docs/FeatureTestMacroTable.rst --- a/libcxx/docs/FeatureTestMacroTable.rst +++ b/libcxx/docs/FeatureTestMacroTable.rst @@ -344,7 +344,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/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|","16.0","|ranges|" "`P1413R3 `__","LWG","Deprecate ``std::aligned_storage`` and ``std::aligned_union``","February 2022","","" "`P2255R2 `__","LWG","A type trait to detect reference binding to temporary","February 2022","","" "`P2273R3 `__","LWG","Making ``std::unique_ptr`` constexpr","February 2022","|Partial| [#note-P2273]_","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,TODO,Complete C++23,`Pipe support for user-defined range adaptors `_,Unassigned,No patch yet,Not started C++23,`Formatting Ranges `_,Mark de Wever,Various,In progress diff --git a/libcxx/include/CMakeLists.txt b/libcxx/include/CMakeLists.txt --- a/libcxx/include/CMakeLists.txt +++ b/libcxx/include/CMakeLists.txt @@ -421,6 +421,7 @@ __memory/builtin_new_allocator.h __memory/compressed_pair.h __memory/concepts.h + __memory/container_compatible_range.h __memory/construct_at.h __memory/destruct_n.h __memory/pointer_traits.h @@ -510,6 +511,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 @@ -526,6 +528,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/__memory/container_compatible_range.h b/libcxx/include/__memory/container_compatible_range.h new file mode 100644 --- /dev/null +++ b/libcxx/include/__memory/container_compatible_range.h @@ -0,0 +1,35 @@ +// -*- 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,250 @@ +// -*- 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 <__config> +#include <__algorithm/ranges_copy.h> +#include <__concepts/constructible.h> +#include <__concepts/convertible_to.h> +#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/transform_view.h> +#include <__ranges/size.h> +#include <__ranges/range_adaptor.h> +#include <__utility/declval.h> +#include <__utility/forward.h> + +#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) +# pragma GCC system_header +#endif + +_LIBCPP_BEGIN_NAMESPACE_STD + +#if _LIBCPP_STD_VER >= 23 + +namespace ranges { + +// Note: in the current Standard draft, `reservable-container` is a `constexpr bool` variable. However, that doesn't +// short-circuit which is necessary to avoid trying to evaluate `range_size_t` in case `sized_range` is not satisfied. +template +concept __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)); } || + // Insufficient constraint: also need to check that inserter(...) is well-formed (the type e.g. must have + // begin() defined, have value_type typedef, etc.). + 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 back_inserter(__c); + } else { + return inserter(__c, __c.end()); + } +} + +template +concept __can_try_convert_without_recursion = !input_range<_Container> || + convertible_to, range_value_t<_Container>>; + +template +concept __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) { + // 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 (__can_try_convert_without_recursion<_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 ( + common_range<_Range> && + __iterator_traits_detail::__cpp17_input_iterator> && + constructible_from<_Container, iterator_t<_Range>, sentinel_t<_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(__false<_Container>, "ranges::to: unable to convert to the given container type."); + } + + // Try the recursive case. + } else if constexpr (input_range>) { + return to<_Container>(__range | views::transform([](auto&& __elem) { + return to>(std::forward(__elem)); + }), std::forward<_Args>(__args)...); + + } else { + static_assert(__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