249 lines · c
1// -*- C++ -*-2//===----------------------------------------------------------------------===//3//4// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5// See https://llvm.org/LICENSE.txt for license information.6// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7//8//===----------------------------------------------------------------------===//9 10#ifndef _LIBCPP___RANGES_TO_H11#define _LIBCPP___RANGES_TO_H12 13#include <__concepts/constructible.h>14#include <__concepts/convertible_to.h>15#include <__concepts/derived_from.h>16#include <__concepts/same_as.h>17#include <__config>18#include <__cstddef/ptrdiff_t.h>19#include <__functional/bind_back.h>20#include <__iterator/iterator_traits.h>21#include <__ranges/access.h>22#include <__ranges/concepts.h>23#include <__ranges/from_range.h>24#include <__ranges/range_adaptor.h>25#include <__ranges/ref_view.h>26#include <__ranges/size.h>27#include <__ranges/transform_view.h>28#include <__type_traits/add_pointer.h>29#include <__type_traits/is_class.h>30#include <__type_traits/is_const.h>31#include <__type_traits/is_union.h>32#include <__type_traits/is_volatile.h>33#include <__type_traits/type_identity.h>34#include <__utility/declval.h>35#include <__utility/forward.h>36 37#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)38# pragma GCC system_header39#endif40 41_LIBCPP_BEGIN_NAMESPACE_STD42 43#if _LIBCPP_STD_VER >= 2344 45namespace ranges {46 47template <class _Container>48constexpr bool __reservable_container =49 sized_range<_Container> && requires(_Container& __c, range_size_t<_Container> __n) {50 __c.reserve(__n);51 { __c.capacity() } -> same_as<decltype(__n)>;52 { __c.max_size() } -> same_as<decltype(__n)>;53 };54 55template <class _Container, class _Ref>56constexpr bool __container_appendable = requires(_Container& __c, _Ref&& __ref) {57 requires(58 requires { __c.emplace_back(std::forward<_Ref>(__ref)); } ||59 requires { __c.push_back(std::forward<_Ref>(__ref)); } ||60 requires { __c.emplace(__c.end(), std::forward<_Ref>(__ref)); } ||61 requires { __c.insert(__c.end(), std::forward<_Ref>(__ref)); });62};63 64// Note: making this a concept allows short-circuiting the second condition.65template <class _Container, class _Range>66concept __try_non_recursive_conversion =67 !input_range<_Container> || convertible_to<range_reference_t<_Range>, range_value_t<_Container>>;68 69template <class _Container, class _Range, class... _Args>70concept __constructible_from_iter_pair =71 common_range<_Range> && requires { typename iterator_traits<iterator_t<_Range>>::iterator_category; } &&72 derived_from<typename iterator_traits<iterator_t<_Range>>::iterator_category, input_iterator_tag> &&73 constructible_from<_Container, iterator_t<_Range>, sentinel_t<_Range>, _Args...>;74 75template <class>76concept __always_false = false;77 78// `ranges::to` base template -- the `_Container` type is a simple type template parameter.79template <class _Container, input_range _Range, class... _Args>80 requires(!view<_Container>)81[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr _Container to(_Range&& __range, _Args&&... __args) {82 // Mandates: C is a cv-unqualified class type.83 static_assert(!is_const_v<_Container>, "The target container cannot be const-qualified, please remove the const");84 static_assert(85 !is_volatile_v<_Container>, "The target container cannot be volatile-qualified, please remove the volatile");86 static_assert(is_class_v<_Container> || is_union_v<_Container>, "The target must be a class type or union type");87 // First see if the non-recursive case applies -- the conversion target is either:88 // - a range with a convertible value type;89 // - a non-range type which might support being created from the input argument(s) (e.g. an `optional`).90 if constexpr (__try_non_recursive_conversion<_Container, _Range>) {91 // Case 1 -- construct directly from the given range.92 if constexpr (constructible_from<_Container, _Range, _Args...>) {93 return _Container(std::forward<_Range>(__range), std::forward<_Args>(__args)...);94 }95 96 // Case 2 -- construct using the `from_range_t` tagged constructor.97 else if constexpr (constructible_from<_Container, from_range_t, _Range, _Args...>) {98 return _Container(from_range, std::forward<_Range>(__range), std::forward<_Args>(__args)...);99 }100 101 // Case 3 -- construct from a begin-end iterator pair.102 else if constexpr (__constructible_from_iter_pair<_Container, _Range, _Args...>) {103 return _Container(ranges::begin(__range), ranges::end(__range), std::forward<_Args>(__args)...);104 }105 106 // Case 4 -- default-construct (or construct from the extra arguments) and insert, reserving the size if possible.107 else if constexpr (constructible_from<_Container, _Args...> &&108 __container_appendable<_Container, range_reference_t<_Range>>) {109 _Container __result(std::forward<_Args>(__args)...);110 if constexpr (sized_range<_Range> && __reservable_container<_Container>) {111 __result.reserve(static_cast<range_size_t<_Container>>(ranges::size(__range)));112 }113 114 for (auto&& __ref : __range) {115 using _Ref = decltype(__ref);116 if constexpr (requires { __result.emplace_back(std::declval<_Ref>()); }) {117 __result.emplace_back(std::forward<_Ref>(__ref));118 } else if constexpr (requires { __result.push_back(std::declval<_Ref>()); }) {119 __result.push_back(std::forward<_Ref>(__ref));120 } else if constexpr (requires { __result.emplace(__result.end(), std::declval<_Ref>()); }) {121 __result.emplace(__result.end(), std::forward<_Ref>(__ref));122 } else {123 static_assert(requires { __result.insert(__result.end(), std::declval<_Ref>()); });124 __result.insert(__result.end(), std::forward<_Ref>(__ref));125 }126 }127 return __result;128 129 } else {130 static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type.");131 }132 133 // Try the recursive case.134 } else if constexpr (input_range<range_reference_t<_Range>>) {135 return ranges::to<_Container>(136 ref_view(__range) | views::transform([](auto&& __elem) {137 return ranges::to<range_value_t<_Container>>(std::forward<decltype(__elem)>(__elem));138 }),139 std::forward<_Args>(__args)...);140 141 } else {142 static_assert(__always_false<_Container>, "ranges::to: unable to convert to the given container type.");143 }144}145 146template <class _Range>147struct __minimal_input_iterator {148 using iterator_category = input_iterator_tag;149 using value_type = range_value_t<_Range>;150 using difference_type = ptrdiff_t;151 using pointer = add_pointer_t<range_reference_t<_Range>>;152 using reference = range_reference_t<_Range>;153 154 reference operator*() const;155 pointer operator->() const;156 __minimal_input_iterator& operator++();157 __minimal_input_iterator operator++(int);158 bool operator==(const __minimal_input_iterator&) const;159};160 161// Deduces the full type of the container from the given template template parameter.162template <template <class...> class _Container, input_range _Range, class... _Args>163struct _Deducer {164 _LIBCPP_HIDE_FROM_ABI static constexpr auto __deduce_func() {165 using _InputIter = __minimal_input_iterator<_Range>;166 167 // Case 1 -- can construct directly from the given range.168 if constexpr (requires { _Container(std::declval<_Range>(), std::declval<_Args>()...); }) {169 using _Result = decltype( //170 _Container(std::declval<_Range>(), std::declval<_Args>()...));171 return type_identity<_Result>{};172 173 // Case 2 -- can construct from the given range using the `from_range_t` tagged constructor.174 } else if constexpr ( //175 requires { _Container(from_range, std::declval<_Range>(), std::declval<_Args>()...); }) {176 using _Result = //177 decltype(_Container(from_range, std::declval<_Range>(), std::declval<_Args>()...));178 return type_identity<_Result>{};179 180 // Case 3 -- can construct from a begin-end iterator pair.181 } else if constexpr ( //182 requires { _Container(std::declval<_InputIter>(), std::declval<_InputIter>(), std::declval<_Args>()...); }) {183 using _Result =184 decltype(_Container(std::declval<_InputIter>(), std::declval<_InputIter>(), std::declval<_Args>()...));185 return type_identity<_Result>{};186 187 } else {188 static_assert(__always_false<_Range>,189 "ranges::to: unable to deduce the container type from the template template argument.");190 }191 }192 193 using type = typename decltype(__deduce_func())::type;194};195 196// `ranges::to` specialization -- `_Container` is a template template parameter requiring deduction to figure out the197// container element type.198template <template <class...> class _Container, input_range _Range, class... _Args>199[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Range&& __range, _Args&&... __args) {200 using _DeduceExpr = typename _Deducer<_Container, _Range, _Args...>::type;201 return ranges::to<_DeduceExpr>(std::forward<_Range>(__range), std::forward<_Args>(__args)...);202}203 204// Range adaptor closure object 1 -- wrapping the `ranges::to` version where `_Container` is a simple type template205// parameter.206template <class _Container, class... _Args>207 requires(!view<_Container>)208[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Args&&... __args) {209 // Mandates: C is a cv-unqualified class type.210 static_assert(!is_const_v<_Container>, "The target container cannot be const-qualified, please remove the const");211 static_assert(212 !is_volatile_v<_Container>, "The target container cannot be volatile-qualified, please remove the volatile");213 static_assert(is_class_v<_Container> || is_union_v<_Container>, "The target must be a class type or union type");214 auto __to_func = []<input_range _Range, class... _Tail>(_Range&& __range, _Tail&&... __tail) static215 requires requires { //216 /**/ ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...);217 }218 { return ranges::to<_Container>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...); };219 220 return __pipeable(std::__bind_back(__to_func, std::forward<_Args>(__args)...));221}222 223// Range adaptor closure object 2 -- wrapping the `ranges::to` version where `_Container` is a template template224// parameter.225template <template <class...> class _Container, class... _Args>226[[nodiscard]] _LIBCPP_HIDE_FROM_ABI constexpr auto to(_Args&&... __args) {227 // clang-format off228 auto __to_func = []<input_range _Range, class... _Tail,229 class _DeducedExpr = typename _Deducer<_Container, _Range, _Tail...>::type>230 (_Range&& __range, _Tail&& ... __tail) static231 requires requires { //232 /**/ ranges::to<_DeducedExpr>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...);233 }234 {235 return ranges::to<_DeducedExpr>(std::forward<_Range>(__range), std::forward<_Tail>(__tail)...);236 };237 // clang-format on238 239 return __pipeable(std::__bind_back(__to_func, std::forward<_Args>(__args)...));240}241 242} // namespace ranges243 244#endif // _LIBCPP_STD_VER >= 23245 246_LIBCPP_END_NAMESPACE_STD247 248#endif // _LIBCPP___RANGES_TO_H249