libcxx/test/std/algorithms/alg.nonmodifying/alg.contains/ranges.contains_subrange.pass.cpp

   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 // <algorithm>
  10
  11 // UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
  12 // ADDITIONAL_COMPILE_FLAGS(has-fconstexpr-steps): -fconstexpr-steps=2000000
  13
  14 // template<forward_iterator I1, sentinel_for<I1> S1,
  15 //          forward_iterator I2, sentinel_for<I2> S2, class Proj = identity>
  16 //     requires indirectly_comparable<I1, I2, Pred, Proj1, Proj2>
  17 //     constexpr bool ranges::contains_subrange(I1 first1, S1 last1, I2 first2, S2 last2,
  18 //                                     Pred pred = {}, Proj1 proj1 = {}, Proj2 proj2 = {});       // since C++23
  19
  20 // template<forward_range R1, forward_range R2,
  21 //          class Pred = ranges::equal_to, class Proj1 = identity, class Proj2 = identity>
  22 //     requires indirectly_comparable<iterator_t<R1>, iterator_t<R2>, Pred, Proj1, Proj2>
  23 //     constexpr bool ranges::contains_subrange(R1&& r1, R2&& r2, Pred pred = {},
  24 //                                              Proj1 proj1 = {}, Proj2 proj2 = {});                 // since C++23
  25
  26 #include <algorithm>
  27 #include <array>
  28 #include <cassert>
  29 #include <concepts>
  30 #include <ranges>
  31 #include <utility>
  32
  33 #include "almost_satisfies_types.h"
  34 #include "test_iterators.h"
  35
  36 struct NotEqualityComparable {};
  37
  38 template <class Iter1, class Sent1 = Iter1, class Iter2 = int*, class Sent2 = Iter2>
  39 concept HasContainsSubrangeIt = requires(Iter1 first1, Sent1 last1, Iter2 first2, Sent2 last2) {
  40   std::ranges::contains_subrange(first1, last1, first2, last2);
  41 };
  42
  43 static_assert(HasContainsSubrangeIt<int*>);
  44 static_assert(!HasContainsSubrangeIt<ForwardIteratorNotDerivedFrom>);
  45 static_assert(!HasContainsSubrangeIt<ForwardIteratorNotIncrementable>);
  46 static_assert(!HasContainsSubrangeIt<int*, SentinelForNotSemiregular>);
  47 static_assert(!HasContainsSubrangeIt<int*, int*, int**>); // not indirectly comparable
  48 static_assert(!HasContainsSubrangeIt<int*, SentinelForNotWeaklyEqualityComparableWith>);
  49 static_assert(!HasContainsSubrangeIt<int*, int*, ForwardIteratorNotDerivedFrom>);
  50 static_assert(!HasContainsSubrangeIt<int*, int*, ForwardIteratorNotIncrementable>);
  51 static_assert(!HasContainsSubrangeIt<int*, int*, int*, SentinelForNotSemiregular>);
  52 static_assert(!HasContainsSubrangeIt<int*, int*, int*, SentinelForNotWeaklyEqualityComparableWith>);
  53
  54 template <class Range1, class Range2 = UncheckedRange<int*>>
  55 concept HasContainsSubrangeR = requires(Range1&& range1, Range2&& range2) {
  56   std::ranges::contains_subrange(std::forward<Range1>(range1), std::forward<Range2>(range2));
  57 };
  58
  59 static_assert(HasContainsSubrangeR<UncheckedRange<int*>>);
  60 static_assert(!HasContainsSubrangeR<ForwardRangeNotDerivedFrom>);
  61 static_assert(!HasContainsSubrangeR<ForwardIteratorNotIncrementable>);
  62 static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelSemiregular>);
  63 static_assert(!HasContainsSubrangeR<ForwardRangeNotSentinelEqualityComparableWith>);
  64 static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, UncheckedRange<int**>>); // not indirectly comparable
  65 static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotDerivedFrom>);
  66 static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotIncrementable>);
  67 static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelSemiregular>);
  68 static_assert(!HasContainsSubrangeR<UncheckedRange<int*>, ForwardRangeNotSentinelEqualityComparableWith>);
  69
  70 template <class Iter1, class Sent1 = Iter1, class Iter2, class Sent2 = Iter2>
  71 constexpr void test_iterators() {
  72   { // simple tests
  73     int a[]       = {1, 2, 3, 4, 5, 6};
  74     int p[]       = {3, 4, 5};
  75     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
  76     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
  77     {
  78       std::same_as<bool> decltype(auto) ret =
  79           std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
  80       assert(ret);
  81     }
  82     {
  83       std::same_as<bool> decltype(auto) ret = std::ranges::contains_subrange(whole, subrange);
  84       assert(ret);
  85     }
  86   }
  87
  88   { // no match
  89     int a[]       = {1, 2, 3, 4, 5, 6};
  90     int p[]       = {3, 4, 2};
  91     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
  92     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
  93     {
  94       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
  95       assert(!ret);
  96     }
  97     {
  98       bool ret = std::ranges::contains_subrange(whole, subrange);
  99       assert(!ret);
 100     }
 101   }
 102
 103   { // range consists of just one element
 104     int a[]       = {3};
 105     int p[]       = {3, 4, 2};
 106     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 107     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 108     {
 109       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 110       assert(!ret);
 111     }
 112     {
 113       bool ret = std::ranges::contains_subrange(whole, subrange);
 114       assert(!ret);
 115     }
 116   }
 117
 118   { // subrange consists of just one element
 119     int a[]       = {23, 1, 20, 3, 54, 2};
 120     int p[]       = {3};
 121     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 122     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 123     {
 124       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 125       assert(ret);
 126     }
 127     {
 128       bool ret = std::ranges::contains_subrange(whole, subrange);
 129       assert(ret);
 130     }
 131   }
 132
 133   { // range has zero length
 134     std::array<int, 0> a = {};
 135     int p[]              = {3, 4, 2};
 136     auto whole           = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
 137     auto subrange        = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 138     {
 139       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 140       assert(!ret);
 141     }
 142     {
 143       bool ret = std::ranges::contains_subrange(whole, subrange);
 144       assert(!ret);
 145     }
 146   }
 147
 148   { // subrange has zero length
 149     int a[]              = {3, 4, 2};
 150     std::array<int, 0> p = {};
 151     auto whole           = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 152     auto subrange        = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));
 153     {
 154       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 155       assert(ret);
 156     }
 157     {
 158       bool ret = std::ranges::contains_subrange(whole, subrange);
 159       assert(ret);
 160     }
 161   }
 162
 163   { // range and subrange both have zero length
 164     std::array<int, 0> a = {};
 165     std::array<int, 0> p = {};
 166     auto whole           = std::ranges::subrange(Iter1(a.data()), Sent1(Iter1(a.data())));
 167     auto subrange        = std::ranges::subrange(Iter2(p.data()), Sent2(Iter2(p.data())));
 168     {
 169       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 170       assert(ret);
 171     }
 172     {
 173       bool ret = std::ranges::contains_subrange(whole, subrange);
 174       assert(ret);
 175     }
 176   }
 177
 178   { // range and subrange are identical
 179     int a[]       = {3, 4, 11, 32, 54, 2};
 180     int p[]       = {3, 4, 11, 32, 54, 2};
 181     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 182     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 183     {
 184       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 185       assert(ret);
 186     }
 187     {
 188       bool ret = std::ranges::contains_subrange(whole, subrange);
 189       assert(ret);
 190     }
 191   }
 192
 193   { // subrange is longer than range
 194     int a[]       = {3, 4, 2};
 195     int p[]       = {23, 3, 4, 2, 11, 32, 54, 2};
 196     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 197     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 198     {
 199       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 200       assert(!ret);
 201     }
 202     {
 203       bool ret = std::ranges::contains_subrange(whole, subrange);
 204       assert(!ret);
 205     }
 206   }
 207
 208   { // subrange is the prefix
 209     int a[]       = {3, 43, 5, 100, 433, 278, 6457, 900};
 210     int p[]       = {3, 43, 5};
 211     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 212     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 213     {
 214       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 215       assert(ret);
 216     }
 217     {
 218       bool ret = std::ranges::contains_subrange(whole, subrange);
 219       assert(ret);
 220     }
 221   }
 222
 223   { // subrange is the suffix
 224     int a[]       = {3, 43, 5, 7, 68, 100, 433, 900};
 225     int p[]       = {100, 433, 900};
 226     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 227     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 228     {
 229       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 230       assert(ret);
 231     }
 232     {
 233       bool ret = std::ranges::contains_subrange(whole, subrange);
 234       assert(ret);
 235     }
 236   }
 237
 238   { // subrange is a subsequence
 239     int a[]       = {23, 1, 0, 54, 2};
 240     int p[]       = {1, 0, 2};
 241     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 242     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 243     {
 244       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 245       assert(!ret);
 246     }
 247     {
 248       bool ret = std::ranges::contains_subrange(whole, subrange);
 249       assert(!ret);
 250     }
 251   }
 252
 253   { // repeated subrange
 254     int a[]       = {23, 1, 0, 2, 54, 1, 0, 2, 23, 33};
 255     int p[]       = {1, 0, 2};
 256     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 257     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 258     {
 259       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end());
 260       assert(ret);
 261     }
 262     {
 263       bool ret = std::ranges::contains_subrange(whole, subrange);
 264       assert(ret);
 265     }
 266   }
 267
 268   { // check that the predicate is used
 269     int a[]       = {23, 81, 61, 0, 42, 25, 1, 2, 1, 29, 2};
 270     int p[]       = {-1, -2, -1};
 271     auto pred     = [](int l, int r) { return l * -1 == r; };
 272     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 273     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 274     {
 275       bool ret = std::ranges::contains_subrange(whole.begin(), whole.end(), subrange.begin(), subrange.end(), pred);
 276       assert(ret);
 277     }
 278     {
 279       bool ret = std::ranges::contains_subrange(whole, subrange, pred);
 280       assert(ret);
 281     }
 282   }
 283
 284   { // check that the projections are used
 285     int a[]       = {1, 3, 15, 1, 2, 1, 8};
 286     int p[]       = {2, 1, 2};
 287     auto whole    = std::ranges::subrange(Iter1(a), Sent1(Iter1(std::end(a))));
 288     auto subrange = std::ranges::subrange(Iter2(p), Sent2(Iter2(std::end(p))));
 289     auto proj1    = [](int i) { return i - 3; };
 290     auto proj2    = [](int i) { return i * -1; };
 291     {
 292       bool ret = std::ranges::contains_subrange(
 293           whole.begin(), whole.end(), subrange.begin(), subrange.end(), {}, proj1, proj2);
 294       assert(ret);
 295     }
 296     {
 297       bool ret = std::ranges::contains_subrange(whole, subrange, {}, proj1, proj2);
 298       assert(ret);
 299     }
 300   }
 301 }
 302
 303 constexpr bool test() {
 304   types::for_each(types::forward_iterator_list<int*>{}, []<class Iter1> {
 305     types::for_each(types::forward_iterator_list<int*>{}, []<class Iter2> {
 306       test_iterators<Iter1, Iter1, Iter2, Iter2>();
 307       test_iterators<Iter1, Iter1, Iter2, sized_sentinel<Iter2>>();
 308       test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, Iter2>();
 309       test_iterators<Iter1, sized_sentinel<Iter1>, Iter2, sized_sentinel<Iter2>>();
 310     });
 311   });
 312
 313   assert(std::ranges::contains_subrange(
 314       std::views::iota(0, 5), std::views::iota(0, 5) | std::views::filter([](int) { return true; })));
 315   assert(!std::ranges::contains_subrange(std::views::iota(0ULL, 42ULL), std::views::iota(0ULL, 1ULL << 32)));
 316
 317   return true;
 318 }
 319
 320 int main(int, char**) {
 321   test();
 322   static_assert(test());
 323
 324   return 0;
 325 }