libcxx/test/std/containers/container.adaptors/push_range_container_adaptors.h

   1 //===----------------------------------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #ifndef SUPPORT_PUSH_RANGE_CONTAINER_ADAPTORS_H
  10 #define SUPPORT_PUSH_RANGE_CONTAINER_ADAPTORS_H
  11
  12 #include <algorithm>
  13 #include <cassert>
  14 #include <concepts>
  15 #include <cstddef>
  16 #include <initializer_list>
  17 #include <ranges>
  18 #include <type_traits>
  19 #include <vector>
  20
  21 #include "../exception_safety_helpers.h"
  22 #include "../from_range_helpers.h"
  23 #include "../insert_range_helpers.h"
  24 #include "MoveOnly.h"
  25 #include "almost_satisfies_types.h"
  26 #include "count_new.h"
  27 #include "min_allocator.h"
  28 #include "test_allocator.h"
  29 #include "test_iterators.h"
  30 #include "test_macros.h"
  31 #include "type_algorithms.h"
  32 #include "unwrap_container_adaptor.h"
  33
  34 template <class Container, class Range>
  35 concept HasPushRange = requires (Container& c, Range&& range) {
  36   c.push_range(range);
  37 };
  38
  39 template <template <class...> class Container, class T, class U>
  40 constexpr bool test_constraints_push_range() {
  41   // Input range with the same value type.
  42   static_assert(HasPushRange<Container<T>, InputRange<T>>);
  43   // Input range with a convertible value type.
  44   static_assert(HasPushRange<Container<T>, InputRange<U>>);
  45   // Input range with a non-convertible value type.
  46   static_assert(!HasPushRange<Container<T>, InputRange<Empty>>);
  47   // Not an input range.
  48   static_assert(!HasPushRange<Container<T>, InputRangeNotDerivedFrom>);
  49   static_assert(!HasPushRange<Container<T>, InputRangeNotIndirectlyReadable>);
  50   static_assert(!HasPushRange<Container<T>, InputRangeNotInputOrOutputIterator>);
  51
  52   return true;
  53 }
  54
  55 // Empty container.
  56
  57 template <class T>
  58 TestCase<T> constexpr EmptyContainer_EmptyRange {
  59   .initial = {}, .input = {}, .expected = {}
  60 };
  61
  62 template <class T> constexpr TestCase<T> EmptyContainer_OneElementRange {
  63   .initial = {}, .input = {5}, .expected = {5}
  64 };
  65
  66 template <class T> constexpr TestCase<T> EmptyContainer_MidRange {
  67   .initial = {}, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9}
  68 };
  69
  70 // One-element container.
  71
  72 template <class T> constexpr TestCase<T> OneElementContainer_EmptyRange {
  73   .initial = {3}, .input = {}, .expected = {3}
  74 };
  75
  76 template <class T> constexpr TestCase<T> OneElementContainer_OneElementRange {
  77   .initial = {3}, .input = {-5}, .expected = {3, -5}
  78 };
  79
  80 template <class T> constexpr TestCase<T> OneElementContainer_MidRange {
  81   .initial = {3}, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9}
  82 };
  83
  84 // Full container.
  85
  86 template <class T> constexpr TestCase<T> FullContainer_EmptyRange {
  87   .initial = {11, 29, 35, 14, 84}, .input = {}, .expected = {11, 29, 35, 14, 84}
  88 };
  89
  90 template <class T> constexpr TestCase<T> FullContainer_OneElementRange {
  91   .initial = {11, 29, 35, 14, 84}, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5}
  92 };
  93
  94 template <class T> constexpr TestCase<T> FullContainer_MidRange {
  95   .initial = {11, 29, 35, 14, 84},
  96   .input = {-5, -3, -1, -7, -9},
  97   .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9}
  98 };
  99
 100 template <class T> constexpr TestCase<T> FullContainer_LongRange {
 101   .initial = {11, 29, 35, 14, 84},
 102   .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},
 103   .expected = {
 104       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
 105   }
 106 };
 107
 108 // Container adaptors tests.
 109
 110 template <class Adaptor, class Iter, class Sent>
 111 constexpr void test_push_range(bool is_result_heapified = false) {
 112   using T = typename Adaptor::value_type;
 113
 114   auto test = [&](auto& test_case) {
 115     Adaptor adaptor(test_case.initial.begin(), test_case.initial.end());
 116     auto in = wrap_input<Iter, Sent>(test_case.input);
 117
 118     adaptor.push_range(in);
 119     UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
 120     auto& c = unwrap_adaptor.get_container();
 121
 122     if (is_result_heapified) {
 123       assert(std::ranges::is_heap(c));
 124       return std::ranges::is_permutation(c, test_case.expected);
 125     } else {
 126       return std::ranges::equal(c, test_case.expected);
 127     }
 128   };
 129
 130   { // Empty container.
 131     // empty_c.push_range(empty_range)
 132     assert(test(EmptyContainer_EmptyRange<T>));
 133     // empty_c.push_range(one_element_range)
 134     assert(test(EmptyContainer_OneElementRange<T>));
 135     // empty_c.push_range(mid_range)
 136     assert(test(EmptyContainer_MidRange<T>));
 137   }
 138
 139   { // One-element container.
 140     // one_element_c.push_range(empty_range)
 141     assert(test(OneElementContainer_EmptyRange<T>));
 142     // one_element_c.push_range(one_element_range)
 143     assert(test(OneElementContainer_OneElementRange<T>));
 144     // one_element_c.push_range(mid_range)
 145     assert(test(OneElementContainer_MidRange<T>));
 146   }
 147
 148   { // Full container.
 149     // full_container.push_range(empty_range)
 150     assert(test(FullContainer_EmptyRange<T>));
 151     // full_container.push_range(one_element_range)
 152     assert(test(FullContainer_OneElementRange<T>));
 153     // full_container.push_range(mid_range)
 154     assert(test(FullContainer_MidRange<T>));
 155     // full_container.push_range(long_range)
 156     assert(test(FullContainer_LongRange<T>));
 157   }
 158 }
 159
 160 // Move-only types.
 161
 162 template <template <class ...> class Container>
 163 constexpr void test_push_range_move_only() {
 164   MoveOnly input[5];
 165   std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});
 166
 167   Container<MoveOnly> c;
 168   c.push_range(in);
 169 }
 170
 171 // Check that `append_range` is preferred if available and `push_back` is used as a fallback.
 172
 173 enum class InserterChoice {
 174   Invalid,
 175   PushBack,
 176   AppendRange
 177 };
 178
 179 template <class T, InserterChoice Inserter>
 180 struct Container {
 181   InserterChoice inserter_choice = InserterChoice::Invalid;
 182
 183   using value_type = T;
 184   using iterator = T*;
 185   using reference = T&;
 186   using const_reference = const T&;
 187   using size_type = std::size_t;
 188
 189   static constexpr int Capacity = 8;
 190   int size_ = 0;
 191   value_type buffer_[Capacity] = {};
 192
 193   iterator begin() { return buffer_; }
 194   iterator end() { return buffer_ + size_; }
 195   size_type size() const { return size_; }
 196
 197   template <class U>
 198   void push_back(U val)
 199   requires (Inserter >= InserterChoice::PushBack) {
 200     inserter_choice = InserterChoice::PushBack;
 201     buffer_[size_] = val;
 202     ++size_;
 203   }
 204
 205   template <std::ranges::input_range Range>
 206   void append_range(Range&& range)
 207   requires (Inserter >= InserterChoice::AppendRange) {
 208     assert(size() + std::ranges::distance(range) <= Capacity);
 209
 210     inserter_choice = InserterChoice::AppendRange;
 211
 212     for (auto&& e : range) {
 213       buffer_[size_] = e;
 214       ++size_;
 215     }
 216   }
 217
 218   friend bool operator==(const Container&, const Container&) = default;
 219 };
 220
 221 template <template <class ...> class AdaptorT, class T>
 222 void test_push_range_inserter_choice(bool is_result_heapified = false) {
 223   { // `append_range` is preferred if available.
 224     using BaseContainer = Container<T, InserterChoice::AppendRange>;
 225     using Adaptor = AdaptorT<T, BaseContainer>;
 226     T in[] = {1, 2, 3, 4, 5};
 227
 228     Adaptor adaptor;
 229     adaptor.push_range(in);
 230
 231     UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
 232     auto& c = unwrap_adaptor.get_container();
 233     assert(c.inserter_choice == InserterChoice::AppendRange);
 234     if (is_result_heapified) {
 235       assert(std::ranges::is_heap(c));
 236       assert(std::ranges::is_permutation(c, in));
 237     } else {
 238       assert(std::ranges::equal(c, in));
 239     }
 240   }
 241
 242   { // `push_back` is used as a fallback (via `back_inserter`).
 243     using BaseContainer = Container<T, InserterChoice::PushBack>;
 244     using Adaptor = AdaptorT<T, BaseContainer>;
 245     T in[] = {1, 2, 3, 4, 5};
 246
 247     Adaptor adaptor;
 248     adaptor.push_range(in);
 249
 250     UnwrapAdaptor<Adaptor> unwrap_adaptor(std::move(adaptor));
 251     auto& c = unwrap_adaptor.get_container();
 252     assert(c.inserter_choice == InserterChoice::PushBack);
 253     if (is_result_heapified) {
 254       assert(std::ranges::is_heap(c));
 255       assert(std::ranges::is_permutation(c, in));
 256     } else {
 257       assert(std::ranges::equal(c, in));
 258     }
 259   }
 260 }
 261
 262 // Exception safety.
 263
 264 template <template <class ...> class Container>
 265 void test_push_range_exception_safety_throwing_copy() {
 266 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 267   constexpr int ThrowOn = 3;
 268   using T = ThrowingCopy<ThrowOn>;
 269   test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](auto* from, auto* to) {
 270     Container<T> c;
 271     c.push_range(std::ranges::subrange(from, to));
 272   });
 273 #endif
 274 }
 275
 276 template <template <class ...> class Adaptor, template <class ...> class BaseContainer, class T>
 277 void test_push_range_exception_safety_throwing_allocator() {
 278 #if !defined(TEST_HAS_NO_EXCEPTIONS)
 279   T in[] = {0, 1};
 280
 281   try {
 282     globalMemCounter.reset();
 283     Adaptor<T, BaseContainer<T, ThrowingAllocator<T>>> c;
 284     c.push_range(in);
 285     assert(false); // The function call above should throw.
 286
 287   } catch (int) {
 288     assert(globalMemCounter.new_called == globalMemCounter.delete_called);
 289   }
 290 #endif
 291 }
 292
 293 #endif // SUPPORT_PUSH_RANGE_CONTAINER_ADAPTORS_H