773 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8 9#ifndef SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H10#define SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H11 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 33template <class Container, class Range>34concept HasInsertRange = requires(Container& c, Range&& range) { c.insert_range(c.end(), range); };35 36template <template <class...> class Container, class T, class U>37constexpr bool test_constraints_insert_range() {38 // Input range with the same value type.39 static_assert(HasInsertRange<Container<T>, InputRange<T>>);40 // Input range with a convertible value type.41 static_assert(HasInsertRange<Container<T>, InputRange<U>>);42 // Input range with a non-convertible value type.43 static_assert(!HasInsertRange<Container<T>, InputRange<Empty>>);44 // Not an input range.45 static_assert(!HasInsertRange<Container<T>, InputRangeNotDerivedFrom>);46 static_assert(!HasInsertRange<Container<T>, InputRangeNotIndirectlyReadable>);47 static_assert(!HasInsertRange<Container<T>, InputRangeNotInputOrOutputIterator>);48 49 return true;50}51 52template <class Container, class Range>53concept HasAppendRange = requires(Container& c, Range&& range) { c.append_range(range); };54 55template <template <class...> class Container, class T, class U>56constexpr bool test_constraints_append_range() {57 // Input range with the same value type.58 static_assert(HasAppendRange<Container<T>, InputRange<T>>);59 // Input range with a convertible value type.60 static_assert(HasAppendRange<Container<T>, InputRange<U>>);61 // Input range with a non-convertible value type.62 static_assert(!HasAppendRange<Container<T>, InputRange<Empty>>);63 // Not an input range.64 static_assert(!HasAppendRange<Container<T>, InputRangeNotDerivedFrom>);65 static_assert(!HasAppendRange<Container<T>, InputRangeNotIndirectlyReadable>);66 static_assert(!HasAppendRange<Container<T>, InputRangeNotInputOrOutputIterator>);67 68 return true;69}70 71template <class Container, class Range>72concept HasPrependRange = requires(Container& c, Range&& range) { c.prepend_range(range); };73 74template <template <class...> class Container, class T, class U>75constexpr bool test_constraints_prepend_range() {76 // Input range with the same value type.77 static_assert(HasPrependRange<Container<T>, InputRange<T>>);78 // Input range with a convertible value type.79 static_assert(HasPrependRange<Container<T>, InputRange<U>>);80 // Input range with a non-convertible value type.81 static_assert(!HasPrependRange<Container<T>, InputRange<Empty>>);82 // Not an input range.83 static_assert(!HasPrependRange<Container<T>, InputRangeNotDerivedFrom>);84 static_assert(!HasPrependRange<Container<T>, InputRangeNotIndirectlyReadable>);85 static_assert(!HasPrependRange<Container<T>, InputRangeNotInputOrOutputIterator>);86 87 return true;88}89 90template <class Container, class Range>91concept HasAssignRange = requires(Container& c, Range&& range) { c.assign_range(range); };92 93template <template <class...> class Container, class T, class U>94constexpr bool test_constraints_assign_range() {95 // Input range with the same value type.96 static_assert(HasAssignRange<Container<T>, InputRange<T>>);97 // Input range with a convertible value type.98 static_assert(HasAssignRange<Container<T>, InputRange<U>>);99 // Input range with a non-convertible value type.100 static_assert(!HasAssignRange<Container<T>, InputRange<Empty>>);101 // Not an input range.102 static_assert(!HasAssignRange<Container<T>, InputRangeNotDerivedFrom>);103 static_assert(!HasAssignRange<Container<T>, InputRangeNotIndirectlyReadable>);104 static_assert(!HasAssignRange<Container<T>, InputRangeNotInputOrOutputIterator>);105 106 return true;107}108 109// Empty container.110 111template <class T>112TestCase<T> constexpr EmptyContainer_EmptyRange{.initial = {}, .index = 0, .input = {}, .expected = {}};113// Note: specializations for `bool` still use `vector<int>` for inputs. This is to avoid dealing with `vector<bool>` and114// its iterators over proxy types.115template <>116constexpr TestCase<int> EmptyContainer_EmptyRange<bool>{.initial = {}, .index = 0, .input = {}, .expected = {}};117 118template <class T>119constexpr TestCase<T> EmptyContainer_OneElementRange;120template <>121constexpr TestCase<int> EmptyContainer_OneElementRange<int>{.initial = {}, .index = 0, .input = {5}, .expected = {5}};122template <>123constexpr TestCase<char> EmptyContainer_OneElementRange<char>{.initial = {}, .index = 0, .input = "a", .expected = "a"};124template <>125constexpr TestCase<int> EmptyContainer_OneElementRange<bool>{126 .initial = {}, .index = 0, .input = {true}, .expected = {true}};127 128template <class T>129constexpr TestCase<T> EmptyContainer_MidRange;130template <>131constexpr TestCase<int> EmptyContainer_MidRange<int>{132 .initial = {}, .index = 0, .input = {5, 3, 1, 7, 9}, .expected = {5, 3, 1, 7, 9}};133template <>134constexpr TestCase<char> EmptyContainer_MidRange<char>{135 .initial = {}, .index = 0, .input = "aeiou", .expected = "aeiou"};136template <>137constexpr TestCase<int> EmptyContainer_MidRange<bool>{138 .initial = {}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1}};139 140// One-element container.141 142template <class T>143constexpr TestCase<T> OneElementContainer_Begin_EmptyRange;144template <>145constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<int>{146 .initial = {3}, .index = 0, .input = {}, .expected = {3}};147template <>148constexpr TestCase<char> OneElementContainer_Begin_EmptyRange<char>{149 .initial = "B", .index = 0, .input = {}, .expected = "B"};150template <>151constexpr TestCase<int> OneElementContainer_Begin_EmptyRange<bool>{152 .initial = {0}, .index = 0, .input = {}, .expected = {0}};153 154template <class T>155constexpr TestCase<T> OneElementContainer_End_EmptyRange;156template <>157constexpr TestCase<int> OneElementContainer_End_EmptyRange<int>{158 .initial = {3}, .index = 1, .input = {}, .expected = {3}};159template <>160constexpr TestCase<char> OneElementContainer_End_EmptyRange<char>{161 .initial = "B", .index = 1, .input = {}, .expected = "B"};162template <>163constexpr TestCase<int> OneElementContainer_End_EmptyRange<bool>{164 .initial = {0}, .index = 1, .input = {}, .expected = {0}};165 166template <class T>167constexpr TestCase<T> OneElementContainer_Begin_OneElementRange;168template <>169constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<int>{170 .initial = {3}, .index = 0, .input = {-5}, .expected = {-5, 3}};171template <>172constexpr TestCase<char> OneElementContainer_Begin_OneElementRange<char>{173 .initial = "B", .index = 0, .input = "a", .expected = "aB"};174template <>175constexpr TestCase<int> OneElementContainer_Begin_OneElementRange<bool>{176 .initial = {0}, .index = 0, .input = {1}, .expected = {1, 0}};177 178template <class T>179constexpr TestCase<T> OneElementContainer_End_OneElementRange;180template <>181constexpr TestCase<int> OneElementContainer_End_OneElementRange<int>{182 .initial = {3}, .index = 1, .input = {-5}, .expected = {3, -5}};183template <>184constexpr TestCase<char> OneElementContainer_End_OneElementRange<char>{185 .initial = "B", .index = 1, .input = "a", .expected = "Ba"};186template <>187constexpr TestCase<int> OneElementContainer_End_OneElementRange<bool>{188 .initial = {0}, .index = 1, .input = {1}, .expected = {0, 1}};189 190template <class T>191constexpr TestCase<T> OneElementContainer_Begin_MidRange;192template <>193constexpr TestCase<int> OneElementContainer_Begin_MidRange<int>{194 .initial = {3}, .index = 0, .input = {-5, -3, -1, -7, -9}, .expected = {-5, -3, -1, -7, -9, 3}};195template <>196constexpr TestCase<char> OneElementContainer_Begin_MidRange<char>{197 .initial = "B", .index = 0, .input = "aeiou", .expected = "aeiouB"};198template <>199constexpr TestCase<int> OneElementContainer_Begin_MidRange<bool>{200 .initial = {0}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1, 0}};201 202template <class T>203constexpr TestCase<T> OneElementContainer_End_MidRange;204template <>205constexpr TestCase<int> OneElementContainer_End_MidRange<int>{206 .initial = {3}, .index = 1, .input = {-5, -3, -1, -7, -9}, .expected = {3, -5, -3, -1, -7, -9}};207template <>208constexpr TestCase<char> OneElementContainer_End_MidRange<char>{209 .initial = "B", .index = 1, .input = "aeiou", .expected = "Baeiou"};210template <>211constexpr TestCase<int> OneElementContainer_End_MidRange<bool>{212 .initial = {0}, .index = 1, .input = {1, 1, 0, 1, 1}, .expected = {0, 1, 1, 0, 1, 1}};213 214// Full container / empty range.215 216template <class T>217constexpr TestCase<T> FullContainer_Begin_EmptyRange;218template <>219constexpr TestCase<int> FullContainer_Begin_EmptyRange<int>{220 .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {}, .expected = {11, 29, 35, 14, 84}};221template <>222constexpr TestCase<char> FullContainer_Begin_EmptyRange<char>{223 .initial = "_BCD_", .index = 0, .input = {}, .expected = "_BCD_"};224template <>225constexpr TestCase<int> FullContainer_Begin_EmptyRange<bool>{226 .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {}, .expected = {0, 0, 1, 0, 0}};227 228template <class T>229constexpr TestCase<T> FullContainer_Mid_EmptyRange;230template <>231constexpr TestCase<int> FullContainer_Mid_EmptyRange<int>{232 .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {}, .expected = {11, 29, 35, 14, 84}};233template <>234constexpr TestCase<char> FullContainer_Mid_EmptyRange<char>{235 .initial = "_BCD_", .index = 2, .input = {}, .expected = "_BCD_"};236template <>237constexpr TestCase<int> FullContainer_Mid_EmptyRange<bool>{238 .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {}, .expected = {0, 0, 1, 0, 0}};239 240template <class T>241constexpr TestCase<T> FullContainer_End_EmptyRange;242template <>243constexpr TestCase<int> FullContainer_End_EmptyRange<int>{244 .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {}, .expected = {11, 29, 35, 14, 84}};245template <>246constexpr TestCase<char> FullContainer_End_EmptyRange<char>{247 .initial = "_BCD_", .index = 5, .input = {}, .expected = "_BCD_"};248template <>249constexpr TestCase<int> FullContainer_End_EmptyRange<bool>{250 .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {}, .expected = {0, 0, 1, 0, 0}};251 252// Full container / one-element range.253 254template <class T>255constexpr TestCase<T> FullContainer_Begin_OneElementRange;256template <>257constexpr TestCase<int> FullContainer_Begin_OneElementRange<int>{258 .initial = {11, 29, 35, 14, 84}, .index = 0, .input = {-5}, .expected = {-5, 11, 29, 35, 14, 84}};259template <>260constexpr TestCase<char> FullContainer_Begin_OneElementRange<char>{261 .initial = "_BCD_", .index = 0, .input = "a", .expected = "a_BCD_"};262template <>263constexpr TestCase<int> FullContainer_Begin_OneElementRange<bool>{264 .initial = {0, 0, 1, 0, 0}, .index = 0, .input = {1}, .expected = {1, 0, 0, 1, 0, 0}};265 266template <class T>267constexpr TestCase<T> FullContainer_Mid_OneElementRange;268template <>269constexpr TestCase<int> FullContainer_Mid_OneElementRange<int>{270 .initial = {11, 29, 35, 14, 84}, .index = 2, .input = {-5}, .expected = {11, 29, -5, 35, 14, 84}};271template <>272constexpr TestCase<char> FullContainer_Mid_OneElementRange<char>{273 .initial = "_BCD_", .index = 2, .input = "a", .expected = "_BaCD_"};274template <>275constexpr TestCase<int> FullContainer_Mid_OneElementRange<bool>{276 .initial = {0, 0, 1, 0, 0}, .index = 2, .input = {1}, .expected = {0, 0, 1, 1, 0, 0}};277 278template <class T>279constexpr TestCase<T> FullContainer_End_OneElementRange;280template <>281constexpr TestCase<int> FullContainer_End_OneElementRange<int>{282 .initial = {11, 29, 35, 14, 84}, .index = 5, .input = {-5}, .expected = {11, 29, 35, 14, 84, -5}};283template <>284constexpr TestCase<char> FullContainer_End_OneElementRange<char>{285 .initial = "_BCD_", .index = 5, .input = "a", .expected = "_BCD_a"};286template <>287constexpr TestCase<int> FullContainer_End_OneElementRange<bool>{288 .initial = {0, 0, 1, 0, 0}, .index = 5, .input = {1}, .expected = {0, 0, 1, 0, 0, 1}};289 290// Full container / mid-sized range.291 292template <class T>293constexpr TestCase<T> FullContainer_Begin_MidRange;294template <>295constexpr TestCase<int> FullContainer_Begin_MidRange<int>{296 .initial = {11, 29, 35, 14, 84},297 .index = 0,298 .input = {-5, -3, -1, -7, -9},299 .expected = {-5, -3, -1, -7, -9, 11, 29, 35, 14, 84}};300template <>301constexpr TestCase<char> FullContainer_Begin_MidRange<char>{302 .initial = "_BCD_", .index = 0, .input = "aeiou", .expected = "aeiou_BCD_"};303template <>304constexpr TestCase<int> FullContainer_Begin_MidRange<bool>{305 .initial = {0, 0, 1, 0, 1}, .index = 0, .input = {1, 1, 0, 1, 1}, .expected = {1, 1, 0, 1, 1, 0, 0, 1, 0, 1}};306 307template <class T>308constexpr TestCase<T> FullContainer_Mid_MidRange;309template <>310constexpr TestCase<int> FullContainer_Mid_MidRange<int>{311 .initial = {11, 29, 35, 14, 84},312 .index = 2,313 .input = {-5, -3, -1, -7, -9},314 .expected = {11, 29, -5, -3, -1, -7, -9, 35, 14, 84}};315template <>316constexpr TestCase<char> FullContainer_Mid_MidRange<char>{317 .initial = "_BCD_", .index = 2, .input = "aeiou", .expected = "_BaeiouCD_"};318template <>319constexpr TestCase<int> FullContainer_Mid_MidRange<bool>{320 .initial = {0, 0, 1, 0, 1}, .index = 2, .input = {1, 1, 0, 1, 1}, .expected = {0, 0, 1, 1, 0, 1, 1, 1, 0, 1}};321 322template <class T>323constexpr TestCase<T> FullContainer_End_MidRange;324template <>325constexpr TestCase<int> FullContainer_End_MidRange<int>{326 .initial = {11, 29, 35, 14, 84},327 .index = 5,328 .input = {-5, -3, -1, -7, -9},329 .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9}};330template <>331constexpr TestCase<char> FullContainer_End_MidRange<char>{332 .initial = "_BCD_", .index = 5, .input = "aeiou", .expected = "_BCD_aeiou"};333template <>334constexpr TestCase<int> FullContainer_End_MidRange<bool>{335 .initial = {0, 0, 1, 0, 1}, .index = 5, .input = {1, 1, 0, 1, 1}, .expected = {0, 0, 1, 0, 1, 1, 1, 0, 1, 1}};336 337// Full container / long range.338 339template <class T>340constexpr TestCase<T> FullContainer_Begin_LongRange;341template <>342constexpr TestCase<int> FullContainer_Begin_LongRange<int>{343 .initial = {11, 29, 35, 14, 84},344 .index = 0,345 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},346 .expected = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17,347 -1, -5, -11, -89, -21, -33, -48, 11, 29, 35, 14, 84}};348template <>349constexpr TestCase<char> FullContainer_Begin_LongRange<char>{350 .initial = "_BCD_", .index = 0, .input = "aeiouqwxyz5781964203", .expected = "aeiouqwxyz5781964203_BCD_"};351template <>352constexpr TestCase<int> FullContainer_Begin_LongRange<bool>{353 .initial = {0, 0, 1, 0, 0},354 .index = 0,355 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},356 .expected = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0}};357 358template <class T>359constexpr TestCase<T> FullContainer_Mid_LongRange;360template <>361constexpr TestCase<int> FullContainer_Mid_LongRange<int>{362 .initial = {11, 29, 35, 14, 84},363 .index = 2,364 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},365 .expected = {11, 29, -5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29,366 -88, -17, -1, -5, -11, -89, -21, -33, -48, 35, 14, 84}};367template <>368constexpr TestCase<char> FullContainer_Mid_LongRange<char>{369 .initial = "_BCD_", .index = 2, .input = "aeiouqwxyz5781964203", .expected = "_Baeiouqwxyz5781964203CD_"};370template <>371constexpr TestCase<int> FullContainer_Mid_LongRange<bool>{372 .initial = {0, 0, 1, 0, 0},373 .index = 2,374 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},375 .expected = {0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0}};376 377template <class T>378constexpr TestCase<T> FullContainer_End_LongRange;379template <>380constexpr TestCase<int> FullContainer_End_LongRange<int>{381 .initial = {11, 29, 35, 14, 84},382 .index = 5,383 .input = {-5, -3, -1, -7, -9, -19, -48, -56, -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48},384 .expected = {11, 29, 35, 14, 84, -5, -3, -1, -7, -9, -19, -48, -56,385 -13, -14, -29, -88, -17, -1, -5, -11, -89, -21, -33, -48}};386template <>387constexpr TestCase<char> FullContainer_End_LongRange<char>{388 .initial = "_BCD_", .index = 5, .input = "aeiouqwxyz5781964203", .expected = "_BCD_aeiouqwxyz5781964203"};389template <>390constexpr TestCase<int> FullContainer_End_LongRange<bool>{391 .initial = {0, 0, 1, 0, 1},392 .index = 5,393 .input = {1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0},394 .expected = {0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0}};395 396// Sequence containers tests.397 398template <class Container, class Iter, class Sent, class Validate>399constexpr void test_sequence_insert_range(Validate validate) {400 using T = typename Container::value_type;401 using D = typename Container::difference_type;402 auto get_pos = [](auto& c, auto& test_case) { return std::ranges::next(c.begin(), static_cast<D>(test_case.index)); };403 404 auto test = [&](auto& test_case) {405 Container c(test_case.initial.begin(), test_case.initial.end());406 auto in = wrap_input<Iter, Sent>(test_case.input);407 auto pos = get_pos(c, test_case);408 409 auto result = c.insert_range(pos, in);410 assert(result == get_pos(c, test_case));411 validate(c);412 return std::ranges::equal(c, test_case.expected);413 };414 415 { // Empty container.416 // empty_c.insert_range(end, empty_range)417 assert(test(EmptyContainer_EmptyRange<T>));418 // empty_c.insert_range(end, one_element_range)419 assert(test(EmptyContainer_OneElementRange<T>));420 // empty_c.insert_range(end, mid_range)421 assert(test(EmptyContainer_MidRange<T>));422 }423 424 { // One-element container.425 // one_element_c.insert_range(begin, empty_range)426 assert(test(OneElementContainer_Begin_EmptyRange<T>));427 // one_element_c.insert_range(end, empty_range)428 assert(test(OneElementContainer_End_EmptyRange<T>));429 // one_element_c.insert_range(begin, one_element_range)430 assert(test(OneElementContainer_Begin_OneElementRange<T>));431 // one_element_c.insert_range(end, one_element_range)432 assert(test(OneElementContainer_End_OneElementRange<T>));433 // one_element_c.insert_range(begin, mid_range)434 assert(test(OneElementContainer_Begin_MidRange<T>));435 // one_element_c.insert_range(end, mid_range)436 assert(test(OneElementContainer_End_MidRange<T>));437 }438 439 { // Full container.440 // full_container.insert_range(begin, empty_range)441 assert(test(FullContainer_Begin_EmptyRange<T>));442 // full_container.insert_range(mid, empty_range)443 assert(test(FullContainer_Mid_EmptyRange<T>));444 // full_container.insert_range(end, empty_range)445 assert(test(FullContainer_End_EmptyRange<T>));446 // full_container.insert_range(begin, one_element_range)447 assert(test(FullContainer_Begin_OneElementRange<T>));448 // full_container.insert_range(end, one_element_range)449 assert(test(FullContainer_Mid_OneElementRange<T>));450 // full_container.insert_range(end, one_element_range)451 assert(test(FullContainer_End_OneElementRange<T>));452 // full_container.insert_range(begin, mid_range)453 assert(test(FullContainer_Begin_MidRange<T>));454 // full_container.insert_range(mid, mid_range)455 assert(test(FullContainer_Mid_MidRange<T>));456 // full_container.insert_range(end, mid_range)457 assert(test(FullContainer_End_MidRange<T>));458 // full_container.insert_range(begin, long_range)459 assert(test(FullContainer_Begin_LongRange<T>));460 // full_container.insert_range(mid, long_range)461 assert(test(FullContainer_Mid_LongRange<T>));462 // full_container.insert_range(end, long_range)463 assert(test(FullContainer_End_LongRange<T>));464 }465}466 467template <class Container, class Iter, class Sent, class Validate>468constexpr void test_sequence_prepend_range(Validate validate) {469 using T = typename Container::value_type;470 471 auto test = [&](auto& test_case) {472 Container c(test_case.initial.begin(), test_case.initial.end());473 auto in = wrap_input<Iter, Sent>(test_case.input);474 475 c.prepend_range(in);476 validate(c);477 return std::ranges::equal(c, test_case.expected);478 };479 480 { // Empty container.481 // empty_c.prepend_range(empty_range)482 assert(test(EmptyContainer_EmptyRange<T>));483 // empty_c.prepend_range(one_element_range)484 assert(test(EmptyContainer_OneElementRange<T>));485 // empty_c.prepend_range(mid_range)486 assert(test(EmptyContainer_MidRange<T>));487 }488 489 { // One-element container.490 // one_element_c.prepend_range(empty_range)491 assert(test(OneElementContainer_Begin_EmptyRange<T>));492 // one_element_c.prepend_range(one_element_range)493 assert(test(OneElementContainer_Begin_OneElementRange<T>));494 // one_element_c.prepend_range(mid_range)495 assert(test(OneElementContainer_Begin_MidRange<T>));496 }497 498 { // Full container.499 // full_container.prepend_range(empty_range)500 assert(test(FullContainer_Begin_EmptyRange<T>));501 // full_container.prepend_range(one_element_range)502 assert(test(FullContainer_Begin_OneElementRange<T>));503 // full_container.prepend_range(mid_range)504 assert(test(FullContainer_Begin_MidRange<T>));505 // full_container.prepend_range(long_range)506 assert(test(FullContainer_Begin_LongRange<T>));507 }508}509 510template <class Container, class Iter, class Sent, class Validate>511constexpr void test_sequence_append_range(Validate validate) {512 using T = typename Container::value_type;513 514 auto test = [&](auto& test_case) {515 Container c(test_case.initial.begin(), test_case.initial.end());516 auto in = wrap_input<Iter, Sent>(test_case.input);517 518 c.append_range(in);519 validate(c);520 return std::ranges::equal(c, test_case.expected);521 };522 523 { // Empty container.524 // empty_c.append_range(empty_range)525 assert(test(EmptyContainer_EmptyRange<T>));526 // empty_c.append_range(one_element_range)527 assert(test(EmptyContainer_OneElementRange<T>));528 // empty_c.append_range(mid_range)529 assert(test(EmptyContainer_MidRange<T>));530 }531 532 { // One-element container.533 // one_element_c.append_range(empty_range)534 assert(test(OneElementContainer_End_EmptyRange<T>));535 // one_element_c.append_range(one_element_range)536 assert(test(OneElementContainer_End_OneElementRange<T>));537 // one_element_c.append_range(mid_range)538 assert(test(OneElementContainer_End_MidRange<T>));539 }540 541 { // Full container.542 // full_container.append_range(empty_range)543 assert(test(FullContainer_End_EmptyRange<T>));544 // full_container.append_range(one_element_range)545 assert(test(FullContainer_End_OneElementRange<T>));546 // full_container.append_range(mid_range)547 assert(test(FullContainer_End_MidRange<T>));548 // full_container.append_range(long_range)549 assert(test(FullContainer_End_LongRange<T>));550 }551}552 553template <class Container, class Iter, class Sent, class Validate>554constexpr void test_sequence_assign_range(Validate validate) {555 using T = typename Container::value_type;556 557 auto& initial_empty = EmptyContainer_EmptyRange<T>.initial;558 auto& initial_one_element = OneElementContainer_Begin_EmptyRange<T>.initial;559 auto& initial_full = FullContainer_Begin_EmptyRange<T>.initial;560 auto& input_empty = FullContainer_Begin_EmptyRange<T>.input;561 auto& input_one_element = FullContainer_Begin_OneElementRange<T>.input;562 auto& input_mid_range = FullContainer_Begin_MidRange<T>.input;563 auto& input_long_range = FullContainer_Begin_LongRange<T>.input;564 565 auto test = [&](auto& initial, auto& input) {566 Container c(initial.begin(), initial.end());567 auto in = wrap_input<Iter, Sent>(input);568 569 c.assign_range(in);570 validate(c);571 return std::ranges::equal(c, input);572 };573 574 { // Empty container.575 // empty_container.assign_range(empty_range)576 assert(test(initial_empty, input_empty));577 // empty_container.assign_range(one_element_range)578 assert(test(initial_empty, input_one_element));579 // empty_container.assign_range(mid_range)580 assert(test(initial_empty, input_mid_range));581 // empty_container.assign_range(long_range)582 assert(test(initial_empty, input_long_range));583 }584 585 { // One-element container.586 // one_element_container.assign_range(empty_range)587 assert(test(initial_one_element, input_empty));588 // one_element_container.assign_range(one_element_range)589 assert(test(initial_one_element, input_one_element));590 // one_element_container.assign_range(mid_range)591 assert(test(initial_one_element, input_mid_range));592 // one_element_container.assign_range(long_range)593 assert(test(initial_one_element, input_long_range));594 }595 596 { // Full container.597 // full_container.assign_range(empty_range)598 assert(test(initial_full, input_empty));599 // full_container.assign_range(one_element_range)600 assert(test(initial_full, input_one_element));601 // full_container.assign_range(mid_range)602 assert(test(initial_full, input_mid_range));603 // full_container.assign_range(long_range)604 assert(test(initial_full, input_long_range));605 }606}607 608// Move-only types.609 610template <template <class...> class Container>611constexpr void test_sequence_insert_range_move_only() {612 MoveOnly input[5];613 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});614 615 Container<MoveOnly> c;616 c.insert_range(c.end(), in);617}618 619template <template <class...> class Container>620constexpr void test_sequence_prepend_range_move_only() {621 MoveOnly input[5];622 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});623 624 Container<MoveOnly> c;625 c.prepend_range(in);626}627 628template <template <class...> class Container>629constexpr void test_sequence_append_range_move_only() {630 MoveOnly input[5];631 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});632 633 Container<MoveOnly> c;634 c.append_range(in);635}636 637template <template <class...> class Container>638constexpr void test_sequence_assign_range_move_only() {639 MoveOnly input[5];640 std::ranges::subrange in(std::move_iterator{input}, std::move_iterator{input + 5});641 642 Container<MoveOnly> c;643 c.assign_range(in);644}645 646// Exception safety.647 648template <template <class...> class Container>649void test_insert_range_exception_safety_throwing_copy() {650#if !defined(TEST_HAS_NO_EXCEPTIONS)651 constexpr int ThrowOn = 3;652 using T = ThrowingCopy<ThrowOn>;653 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {654 Container<T> c;655 c.insert_range(c.end(), std::ranges::subrange(from, to));656 });657#endif658}659 660template <template <class...> class Container, class T>661void test_insert_range_exception_safety_throwing_allocator() {662#if !defined(TEST_HAS_NO_EXCEPTIONS)663 T in[] = {0, 1};664 665 try {666 ThrowingAllocator<T> alloc;667 668 globalMemCounter.reset();669 Container<T, ThrowingAllocator<T>> c(alloc);670 c.insert_range(c.end(), in);671 assert(false); // The function call above should throw.672 673 } catch (int) {674 assert(globalMemCounter.new_called == globalMemCounter.delete_called);675 }676#endif677}678 679template <template <class...> class Container>680void test_prepend_range_exception_safety_throwing_copy() {681#if !defined(TEST_HAS_NO_EXCEPTIONS)682 constexpr int ThrowOn = 3;683 using T = ThrowingCopy<ThrowOn>;684 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {685 Container<T> c;686 c.prepend_range(std::ranges::subrange(from, to));687 });688#endif689}690 691template <template <class...> class Container, class T>692void test_prepend_range_exception_safety_throwing_allocator() {693#if !defined(TEST_HAS_NO_EXCEPTIONS)694 T in[] = {0, 1};695 696 try {697 ThrowingAllocator<T> alloc;698 699 globalMemCounter.reset();700 Container<T, ThrowingAllocator<T>> c(alloc);701 c.prepend_range(in);702 assert(false); // The function call above should throw.703 704 } catch (int) {705 assert(globalMemCounter.new_called == globalMemCounter.delete_called);706 }707#endif708}709 710template <template <class...> class Container>711void test_append_range_exception_safety_throwing_copy() {712#if !defined(TEST_HAS_NO_EXCEPTIONS)713 constexpr int ThrowOn = 3;714 using T = ThrowingCopy<ThrowOn>;715 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {716 Container<T> c;717 c.append_range(std::ranges::subrange(from, to));718 });719#endif720}721 722template <template <class...> class Container, class T>723void test_append_range_exception_safety_throwing_allocator() {724#if !defined(TEST_HAS_NO_EXCEPTIONS)725 T in[] = {0, 1};726 727 try {728 ThrowingAllocator<T> alloc;729 730 globalMemCounter.reset();731 Container<T, ThrowingAllocator<T>> c(alloc);732 c.append_range(in);733 assert(false); // The function call above should throw.734 735 } catch (int) {736 assert(globalMemCounter.new_called == globalMemCounter.delete_called);737 }738#endif739}740 741template <template <class...> class Container>742void test_assign_range_exception_safety_throwing_copy() {743#if !defined(TEST_HAS_NO_EXCEPTIONS)744 constexpr int ThrowOn = 3;745 using T = ThrowingCopy<ThrowOn>;746 test_exception_safety_throwing_copy<ThrowOn, /*Size=*/5>([](T* from, T* to) {747 Container<T> c;748 c.assign_range(std::ranges::subrange(from, to));749 });750#endif751}752 753template <template <class...> class Container, class T>754void test_assign_range_exception_safety_throwing_allocator() {755#if !defined(TEST_HAS_NO_EXCEPTIONS)756 T in[] = {0, 1};757 758 try {759 ThrowingAllocator<T> alloc;760 761 globalMemCounter.reset();762 Container<T, ThrowingAllocator<T>> c(alloc);763 c.assign_range(in);764 assert(false); // The function call above should throw.765 766 } catch (int) {767 assert(globalMemCounter.new_called == globalMemCounter.delete_called);768 }769#endif770}771 772#endif // SUPPORT_INSERT_RANGE_SEQUENCE_CONTAINERS_H773