106c3fb27SDimitry Andric // -*- C++ -*- 206c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 306c3fb27SDimitry Andric // 406c3fb27SDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 506c3fb27SDimitry Andric // See https://llvm.org/LICENSE.txt for license information. 606c3fb27SDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 706c3fb27SDimitry Andric // 806c3fb27SDimitry Andric //===----------------------------------------------------------------------===// 906c3fb27SDimitry Andric 1006c3fb27SDimitry Andric #ifndef _LIBCPP___RANGES_TO_H 1106c3fb27SDimitry Andric #define _LIBCPP___RANGES_TO_H 1206c3fb27SDimitry Andric 1306c3fb27SDimitry Andric #include <__algorithm/ranges_copy.h> 1406c3fb27SDimitry Andric #include <__concepts/constructible.h> 1506c3fb27SDimitry Andric #include <__concepts/convertible_to.h> 1606c3fb27SDimitry Andric #include <__concepts/derived_from.h> 1706c3fb27SDimitry Andric #include <__concepts/same_as.h> 1806c3fb27SDimitry Andric #include <__config> 1906c3fb27SDimitry Andric #include <__functional/bind_back.h> 2006c3fb27SDimitry Andric #include <__iterator/back_insert_iterator.h> 2106c3fb27SDimitry Andric #include <__iterator/insert_iterator.h> 2206c3fb27SDimitry Andric #include <__iterator/iterator_traits.h> 2306c3fb27SDimitry Andric #include <__ranges/access.h> 2406c3fb27SDimitry Andric #include <__ranges/concepts.h> 2506c3fb27SDimitry Andric #include <__ranges/from_range.h> 2606c3fb27SDimitry Andric #include <__ranges/range_adaptor.h> 27*0fca6ea1SDimitry Andric #include <__ranges/ref_view.h> 2806c3fb27SDimitry Andric #include <__ranges/size.h> 2906c3fb27SDimitry Andric #include <__ranges/transform_view.h> 3006c3fb27SDimitry Andric #include <__type_traits/add_pointer.h> 3106c3fb27SDimitry Andric #include <__type_traits/is_const.h> 3206c3fb27SDimitry Andric #include <__type_traits/is_volatile.h> 3306c3fb27SDimitry Andric #include <__type_traits/type_identity.h> 3406c3fb27SDimitry Andric #include <__utility/declval.h> 3506c3fb27SDimitry Andric #include <__utility/forward.h> 3606c3fb27SDimitry Andric #include <cstddef> 3706c3fb27SDimitry Andric 3806c3fb27SDimitry Andric #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER) 3906c3fb27SDimitry Andric # pragma GCC system_header 4006c3fb27SDimitry Andric #endif 4106c3fb27SDimitry Andric 4206c3fb27SDimitry Andric _LIBCPP_BEGIN_NAMESPACE_STD 4306c3fb27SDimitry Andric 4406c3fb27SDimitry Andric #if _LIBCPP_STD_VER >= 23 4506c3fb27SDimitry Andric 4606c3fb27SDimitry Andric namespace ranges { 4706c3fb27SDimitry Andric 4806c3fb27SDimitry Andric template <class _Container> 495f757f3fSDimitry Andric constexpr bool __reservable_container = 505f757f3fSDimitry Andric sized_range<_Container> && requires(_Container& __c, range_size_t<_Container> __n) { 5106c3fb27SDimitry Andric __c.reserve(__n); 5206c3fb27SDimitry Andric { __c.capacity() } -> same_as<decltype(__n)>; 5306c3fb27SDimitry Andric { __c.max_size() } -> same_as<decltype(__n)>; 5406c3fb27SDimitry Andric }; 5506c3fb27SDimitry Andric 5606c3fb27SDimitry Andric template <class _Container, class _Ref> 5706c3fb27SDimitry Andric constexpr bool __container_insertable = requires(_Container& __c, _Ref&& __ref) { 5806c3fb27SDimitry Andric requires( 5906c3fb27SDimitry Andric requires { __c.push_back(std::forward<_Ref>(__ref)); } || 6006c3fb27SDimitry Andric requires { __c.insert(__c.end(), std::forward<_Ref>(__ref)); }); 6106c3fb27SDimitry Andric }; 6206c3fb27SDimitry Andric 6306c3fb27SDimitry Andric template <class _Ref, class _Container> 6406c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI constexpr auto __container_inserter(_Container& __c) { 6506c3fb27SDimitry Andric if constexpr (requires { __c.push_back(std::declval<_Ref>()); }) { 6606c3fb27SDimitry Andric return std::back_inserter(__c); 6706c3fb27SDimitry Andric } else { 6806c3fb27SDimitry Andric return std::inserter(__c, __c.end()); 6906c3fb27SDimitry Andric } 7006c3fb27SDimitry Andric } 7106c3fb27SDimitry Andric 7206c3fb27SDimitry Andric // Note: making this a concept allows short-circuiting the second condition. 7306c3fb27SDimitry Andric template <class _Container, class _Range> 7406c3fb27SDimitry Andric concept __try_non_recursive_conversion = 7506c3fb27SDimitry Andric !input_range<_Container> || convertible_to<range_reference_t<_Range>, range_value_t<_Container>>; 7606c3fb27SDimitry Andric 7706c3fb27SDimitry Andric template <class _Container, class _Range, class... _Args> 7806c3fb27SDimitry Andric concept __constructible_from_iter_pair = 7906c3fb27SDimitry Andric common_range<_Range> && requires { typename iterator_traits<iterator_t<_Range>>::iterator_category; } && 8006c3fb27SDimitry Andric derived_from<typename iterator_traits<iterator_t<_Range>>::iterator_category, input_iterator_tag> && 8106c3fb27SDimitry Andric constructible_from<_Container, iterator_t<_Range>, sentinel_t<_Range>, _Args...>; 8206c3fb27SDimitry Andric 8306c3fb27SDimitry Andric template <class> 8406c3fb27SDimitry Andric concept __always_false = false; 8506c3fb27SDimitry Andric 8606c3fb27SDimitry Andric // `ranges::to` base template -- the `_Container` type is a simple type template parameter. 8706c3fb27SDimitry Andric template <class _Container, input_range _Range, class... _Args> 8806c3fb27SDimitry Andric requires(!view<_Container>) 89*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Container to(_Range&& __range, _Args&&... __args) { 9006c3fb27SDimitry Andric // Mandates: C is a cv-unqualified class type. 9106c3fb27SDimitry Andric static_assert(!is_const_v<_Container>, "The target container cannot be const-qualified, please remove the const"); 9206c3fb27SDimitry Andric static_assert( 9306c3fb27SDimitry Andric !is_volatile_v<_Container>, "The target container cannot be volatile-qualified, please remove the volatile"); 9406c3fb27SDimitry Andric 9506c3fb27SDimitry Andric // First see if the non-recursive case applies -- the conversion target is either: 9606c3fb27SDimitry Andric // - a range with a convertible value type; 9706c3fb27SDimitry Andric // - a non-range type which might support being created from the input argument(s) (e.g. an `optional`). 9806c3fb27SDimitry Andric if constexpr (__try_non_recursive_conversion<_Container, _Range>) { 9906c3fb27SDimitry Andric // Case 1 -- construct directly from the given range. 10006c3fb27SDimitry Andric if constexpr (constructible_from<_Container, _Range, _Args...>) { 10106c3fb27SDimitry Andric return _Container(std::forward<_Range>(__range), std::forward<_Args>(__args)...); 10206c3fb27SDimitry Andric } 10306c3fb27SDimitry Andric 10406c3fb27SDimitry Andric // Case 2 -- construct using the `from_range_t` tagged constructor. 10506c3fb27SDimitry Andric else if constexpr (constructible_from<_Container, from_range_t, _Range, _Args...>) { 10606c3fb27SDimitry Andric return _Container(from_range, std::forward<_Range>(__range), std::forward<_Args>(__args)...); 10706c3fb27SDimitry Andric } 10806c3fb27SDimitry Andric 10906c3fb27SDimitry Andric // Case 3 -- construct from a begin-end iterator pair. 11006c3fb27SDimitry Andric else if constexpr (__constructible_from_iter_pair<_Container, _Range, _Args...>) { 11106c3fb27SDimitry Andric return _Container(ranges::begin(__range), ranges::end(__range), std::forward<_Args>(__args)...); 11206c3fb27SDimitry Andric } 11306c3fb27SDimitry Andric 11406c3fb27SDimitry Andric // Case 4 -- default-construct (or construct from the extra arguments) and insert, reserving the size if possible. 11506c3fb27SDimitry Andric else if constexpr (constructible_from<_Container, _Args...> && 11606c3fb27SDimitry Andric __container_insertable<_Container, range_reference_t<_Range>>) { 11706c3fb27SDimitry Andric _Container __result(std::forward<_Args>(__args)...); 11806c3fb27SDimitry Andric if constexpr (sized_range<_Range> && __reservable_container<_Container>) { 11906c3fb27SDimitry Andric __result.reserve(static_cast<range_size_t<_Container>>(ranges::size(__range))); 12006c3fb27SDimitry Andric } 12106c3fb27SDimitry Andric 12206c3fb27SDimitry Andric ranges::copy(__range, ranges::__container_inserter<range_reference_t<_Range>>(__result)); 12306c3fb27SDimitry Andric 12406c3fb27SDimitry Andric return __result; 12506c3fb27SDimitry Andric 12606c3fb27SDimitry Andric } else { 12706c3fb27SDimitry Andric static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type."); 12806c3fb27SDimitry Andric } 12906c3fb27SDimitry Andric 13006c3fb27SDimitry Andric // Try the recursive case. 13106c3fb27SDimitry Andric } else if constexpr (input_range<range_reference_t<_Range>>) { 13206c3fb27SDimitry Andric return ranges::to<_Container>( 133*0fca6ea1SDimitry Andric ref_view(__range) | views::transform([](auto&& __elem) { 13406c3fb27SDimitry Andric return ranges::to<range_value_t<_Container>>(std::forward<decltype(__elem)>(__elem)); 13506c3fb27SDimitry Andric }), 13606c3fb27SDimitry Andric std::forward<_Args>(__args)...); 13706c3fb27SDimitry Andric 13806c3fb27SDimitry Andric } else { 13906c3fb27SDimitry Andric static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type."); 14006c3fb27SDimitry Andric } 14106c3fb27SDimitry Andric } 14206c3fb27SDimitry Andric 14306c3fb27SDimitry Andric template <class _Range> 14406c3fb27SDimitry Andric struct __minimal_input_iterator { 14506c3fb27SDimitry Andric using iterator_category = input_iterator_tag; 14606c3fb27SDimitry Andric using value_type = range_value_t<_Range>; 14706c3fb27SDimitry Andric using difference_type = ptrdiff_t; 14806c3fb27SDimitry Andric using pointer = add_pointer_t<range_reference_t<_Range>>; 14906c3fb27SDimitry Andric using reference = range_reference_t<_Range>; 15006c3fb27SDimitry Andric 15106c3fb27SDimitry Andric reference operator*() const; 15206c3fb27SDimitry Andric pointer operator->() const; 15306c3fb27SDimitry Andric __minimal_input_iterator& operator++(); 15406c3fb27SDimitry Andric __minimal_input_iterator operator++(int); 15506c3fb27SDimitry Andric bool operator==(const __minimal_input_iterator&) const; 15606c3fb27SDimitry Andric }; 15706c3fb27SDimitry Andric 15806c3fb27SDimitry Andric // Deduces the full type of the container from the given template template parameter. 15906c3fb27SDimitry Andric template <template <class...> class _Container, input_range _Range, class... _Args> 16006c3fb27SDimitry Andric struct _Deducer { 16106c3fb27SDimitry Andric _LIBCPP_HIDE_FROM_ABI static constexpr auto __deduce_func() { 16206c3fb27SDimitry Andric using _InputIter = __minimal_input_iterator<_Range>; 16306c3fb27SDimitry Andric 16406c3fb27SDimitry Andric // Case 1 -- can construct directly from the given range. 16506c3fb27SDimitry Andric if constexpr (requires { _Container(std::declval<_Range>(), std::declval<_Args>()...); }) { 16606c3fb27SDimitry Andric using _Result = decltype( // 16706c3fb27SDimitry Andric _Container(std::declval<_Range>(), std::declval<_Args>()...)); 16806c3fb27SDimitry Andric return type_identity<_Result>{}; 16906c3fb27SDimitry Andric 17006c3fb27SDimitry Andric // Case 2 -- can construct from the given range using the `from_range_t` tagged constructor. 17106c3fb27SDimitry Andric } else if constexpr ( // 17206c3fb27SDimitry Andric requires { _Container(from_range, std::declval<_Range>(), std::declval<_Args>()...); }) { 17306c3fb27SDimitry Andric using _Result = // 17406c3fb27SDimitry Andric decltype(_Container(from_range, std::declval<_Range>(), std::declval<_Args>()...)); 17506c3fb27SDimitry Andric return type_identity<_Result>{}; 17606c3fb27SDimitry Andric 17706c3fb27SDimitry Andric // Case 3 -- can construct from a begin-end iterator pair. 17806c3fb27SDimitry Andric } else if constexpr ( // 17906c3fb27SDimitry Andric requires { _Container(std::declval<_InputIter>(), std::declval<_InputIter>(), std::declval<_Args>()...); }) { 18006c3fb27SDimitry Andric using _Result = 18106c3fb27SDimitry Andric decltype(_Container(std::declval<_InputIter>(), std::declval<_InputIter>(), std::declval<_Args>()...)); 18206c3fb27SDimitry Andric return type_identity<_Result>{}; 18306c3fb27SDimitry Andric 18406c3fb27SDimitry Andric } else { 18506c3fb27SDimitry Andric static_assert(__always_false<_Range>, 18606c3fb27SDimitry Andric "ranges::to: unable to deduce the container type from the template template argument."); 18706c3fb27SDimitry Andric } 18806c3fb27SDimitry Andric } 18906c3fb27SDimitry Andric 19006c3fb27SDimitry Andric using type = typename decltype(__deduce_func())::type; 19106c3fb27SDimitry Andric }; 19206c3fb27SDimitry Andric 19306c3fb27SDimitry Andric // `ranges::to` specialization -- `_Container` is a template template parameter requiring deduction to figure out the 19406c3fb27SDimitry Andric // container element type. 19506c3fb27SDimitry Andric template <template <class...> class _Container, input_range _Range, class... _Args> 196*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Range&& __range, _Args&&... __args) { 19706c3fb27SDimitry Andric using _DeduceExpr = typename _Deducer<_Container, _Range, _Args...>::type; 19806c3fb27SDimitry Andric return ranges::to<_DeduceExpr>(std::forward<_Range>(__range), std::forward<_Args>(__args)...); 19906c3fb27SDimitry Andric } 20006c3fb27SDimitry Andric 20106c3fb27SDimitry Andric // Range adaptor closure object 1 -- wrapping the `ranges::to` version where `_Container` is a simple type template 20206c3fb27SDimitry Andric // parameter. 20306c3fb27SDimitry Andric template <class _Container, class... _Args> 20406c3fb27SDimitry Andric requires(!view<_Container>) 205*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Args&&... __args) { 20606c3fb27SDimitry Andric // Mandates: C is a cv-unqualified class type. 20706c3fb27SDimitry Andric static_assert(!is_const_v<_Container>, "The target container cannot be const-qualified, please remove the const"); 20806c3fb27SDimitry Andric static_assert( 20906c3fb27SDimitry Andric !is_volatile_v<_Container>, "The target container cannot be volatile-qualified, please remove the volatile"); 21006c3fb27SDimitry Andric 211*0fca6ea1SDimitry Andric auto __to_func = []<input_range _Range, class... _Tail>(_Range&& __range, _Tail&&... __tail) static 21206c3fb27SDimitry Andric requires requires { // 21306c3fb27SDimitry Andric /**/ ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...); 21406c3fb27SDimitry Andric } 2155f757f3fSDimitry Andric { return ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...); }; 21606c3fb27SDimitry Andric 21706c3fb27SDimitry Andric return __range_adaptor_closure_t(std::__bind_back(__to_func, std::forward<_Args>(__args)...)); 21806c3fb27SDimitry Andric } 21906c3fb27SDimitry Andric 22006c3fb27SDimitry Andric // Range adaptor closure object 2 -- wrapping the `ranges::to` version where `_Container` is a template template 22106c3fb27SDimitry Andric // parameter. 22206c3fb27SDimitry Andric template <template <class...> class _Container, class... _Args> 223*0fca6ea1SDimitry Andric [[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Args&&... __args) { 22406c3fb27SDimitry Andric // clang-format off 22506c3fb27SDimitry Andric auto __to_func = []<input_range _Range, class... _Tail, 22606c3fb27SDimitry Andric class _DeducedExpr = typename _Deducer<_Container, _Range, _Tail...>::type> 227*0fca6ea1SDimitry Andric (_Range&& __range, _Tail&& ... __tail) static 22806c3fb27SDimitry Andric requires requires { // 22906c3fb27SDimitry Andric /**/ ranges::to<_DeducedExpr>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...); 23006c3fb27SDimitry Andric } 23106c3fb27SDimitry Andric { 23206c3fb27SDimitry Andric return ranges::to<_DeducedExpr>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...); 23306c3fb27SDimitry Andric }; 23406c3fb27SDimitry Andric // clang-format on 23506c3fb27SDimitry Andric 23606c3fb27SDimitry Andric return __range_adaptor_closure_t(std::__bind_back(__to_func, std::forward<_Args>(__args)...)); 23706c3fb27SDimitry Andric } 23806c3fb27SDimitry Andric 23906c3fb27SDimitry Andric } // namespace ranges 24006c3fb27SDimitry Andric 24106c3fb27SDimitry Andric #endif // _LIBCPP_STD_VER >= 23 24206c3fb27SDimitry Andric 24306c3fb27SDimitry Andric _LIBCPP_END_NAMESPACE_STD 24406c3fb27SDimitry Andric 24506c3fb27SDimitry Andric #endif // _LIBCPP___RANGES_TO_H 246