[libc++][ranges] implement `std::ranges::includes`

[huixie90]

Summary

[libc++][ranges] implement std::ranges::includes

[var-const]

Almost LGTM -- the only important comment is about sentinel types in tests.

libcxx/docs/Status/RangesAlgorithms.csv

32

Nit: please include the patch link.

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp

49

Nit: include <utility>.

109

I'm a bit concerned that we never check the pretty common case where In1 and Sent1 are the same type. Consider making Sent1 and Sent2 template parameters. If the test takes too long, I'd rather omit some less interesting iterator types (for partition_copy, I only use iterator types with the weakest and the strongest constraints, with the idea that if both cpp20_input_iterator and random_access_iterator work, then it's very unlikely that forward_iterator or bidirectional_iterator won't work).

400

Optional: there's some prior art to reduce boilerplate here in test_support/counting_predicates.h. I used it in https://reviews.llvm.org/D130070 (with some additions) and it seemed to reduce verbosity a little. This can easily be done in a follow-up.

[jloser]

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp

239–240

Nit: we can remove these TODOs since you have tests below with a custom comparator and custom projection, right?

[var-const]

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp

239–240

+1 -- sorry I somehow missed that.

[huixie90]

address review issues

[var-const]

Thanks for addressing the feedback!

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp

240

This is pretty neat. You could also do something like if constexpr (std::sentinel_for<Iter2, Iter2>) to decide whether the iterator can be used as its own sentinel type (just throwing it out there, this LGTM).

[huixie90]

rebase

libcxx/docs/Status/RangesAlgorithms.csv

 Search,count,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,count_if,Nikolas Klauser,`D121523 <https://llvm.org/D121523>`_,✅
 Search,search,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,search_n,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Search,find_end,Nikolas Klauser,`D124079 <https://llvm.org/D124079>`_,✅
 Read-only,is_partitioned,Nikolas Klauser,`D124440 <https://llvm.org/D124440>`_,✅
 Read-only,is_sorted,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
 Read-only,is_sorted_until,Nikolas Klauser,`D125608 <https://llvm.org/D125608>`_,✅
-Read-only,includes,Nikolas Klauser,n/a,Not started
+Read-only,includes,Hui Xie,`D130116 <https://llvm.org/D130116>`,✅
 Read-only,is_heap,Nikolas Klauser,n/a,Not started
 Read-only,is_heap_until,Nikolas Klauser,n/a,Not started
 Read-only,clamp,Nikolas Klauser,`D126193 <https://llvm.org/D126193>`_,Under review
 Read-only,is_permutation,Nikolas Klauser,`D127194 <https://llvm.org/D127194>`_,Under review
 Read-only,for_each,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Read-only,for_each_n,Nikolas Klauser,`D124332 <https://llvm.org/D124332>`_,✅
 Write,copy,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅
 Write,copy_if,Nikolas Klauser,`D122982 <https://llvm.org/D122982>`_,✅

libcxx/include/__algorithm/includes.h

 //===----------------------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef _LIBCPP___ALGORITHM_INCLUDES_H
 #define _LIBCPP___ALGORITHM_INCLUDES_H
 
 #include <__algorithm/comp.h>
 #include <__algorithm/comp_ref_type.h>
 #include <__config>
 #include <__iterator/iterator_traits.h>
+#include <__utility/move.h>
 
 #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
 #  pragma GCC system_header
 #endif
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
-template <class _Compare, class _InputIterator1, class _InputIterator2>
-_LIBCPP_CONSTEXPR_AFTER_CXX17 bool
-__includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
-           _Compare __comp)
-{
-    for (; __first2 != __last2; ++__first1)
-    {
-        if (__first1 == __last1 || __comp(*__first2, *__first1))
-            return false;
-        if (!__comp(*__first1, *__first2))
-            ++__first2;
-    }
-    return true;
+template <class _Iter1, class _Sent1, class _Iter2, class _Sent2, class _Comp>
+_LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+__includes(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp&& __comp) {
+  for (; __first2 != __last2; ++__first1) {
 }
 
 template <class _InputIterator1, class _InputIterator2, class _Compare>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-bool
-includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2,
-         _Compare __comp)
-{
-    typedef typename __comp_ref_type<_Compare>::type _Comp_ref;
-    return _VSTD::__includes<_Comp_ref>(__first1, __last1, __first2, __last2, __comp);
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool includes(
+    _InputIterator1 __first1,
+    _InputIterator1 __last1,
+    _InputIterator2 __first2,
+    _InputIterator2 __last2,
+    _Compare __comp) {
+  return std::__includes(
+      std::move(__first1), std::move(__last1), std::move(__first2), std::move(__last2), static_cast<_Comp_ref>(__comp));
 }
 
 template <class _InputIterator1, class _InputIterator2>
-_LIBCPP_NODISCARD_EXT inline
-_LIBCPP_INLINE_VISIBILITY _LIBCPP_CONSTEXPR_AFTER_CXX17
-bool
-includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2)
-{
-    return _VSTD::includes(__first1, __last1, __first2, __last2,
-                          __less<typename iterator_traits<_InputIterator1>::value_type,
-                                 typename iterator_traits<_InputIterator2>::value_type>());
+_LIBCPP_NODISCARD_EXT inline _LIBCPP_HIDE_FROM_ABI _LIBCPP_CONSTEXPR_AFTER_CXX17 bool
+includes(_InputIterator1 __first1, _InputIterator1 __last1, _InputIterator2 __first2, _InputIterator2 __last2) {
+  return std::includes(
+      std::move(__first1),
+      std::move(__last1),
+      std::move(__first2),
+      std::move(__last2),
 }
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP___ALGORITHM_INCLUDES_H

libcxx/include/__algorithm/ranges_includes.h

 #if _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 _LIBCPP_BEGIN_NAMESPACE_STD
 
 namespace ranges {
 namespace __includes {
 
 struct __fn {
-
-  template <input_iterator _Iter1, sentinel_for<_Iter1> _Sent1, input_iterator _Iter2, sentinel_for<_Iter2> _Sent2,
-            class _Proj1 = identity, class _Proj2 = identity,
-            indirect_strict_weak_order<projected<_Iter1, _Proj1>, projected<_Iter2, _Proj2>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  bool operator()(_Iter1 __first1, _Sent1 __last1, _Iter2 __first2, _Sent2 __last2, _Comp __comp = {},
-                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__first1; (void)__last1; (void)__first2; (void)__last2; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+  template <
+      input_iterator _Iter1,
+      sentinel_for<_Iter1> _Sent1,
+      input_iterator _Iter2,
+      sentinel_for<_Iter2> _Sent2,
+      class _Proj1                                                                           = identity,
+      class _Proj2                                                                           = identity,
+  _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
+      _Iter1 __first1,
+      _Sent1 __last1,
+      _Iter2 __first2,
+      _Sent2 __last2,
+      _Comp __comp   = {},
+      _Proj1 __proj1 = {},
+      _Proj2 __proj2 = {}) const {
+    return std::__includes(
+        std::move(__first1),
+        std::move(__last1),
+        std::move(__first2),
+        std::move(__last2),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
   }
 
-  template <input_range _Range1, input_range _Range2, class _Proj1 = identity, class _Proj2 = identity,
-            indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>,
-                                       projected<iterator_t<_Range2>, _Proj2>> _Comp = ranges::less>
-  _LIBCPP_HIDE_FROM_ABI constexpr
-  bool operator()(_Range1&& __range1, _Range2&& __range2, _Comp __comp = {},
-                  _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
-    // TODO: implement
-    (void)__range1; (void)__range2; (void)__comp; (void)__proj1; (void)__proj2;
-    return {};
+  template <
+      input_range _Range1,
+      input_range _Range2,
+      class _Proj1 = identity,
+      class _Proj2 = identity,
+      indirect_strict_weak_order<projected<iterator_t<_Range1>, _Proj1>, projected<iterator_t<_Range2>, _Proj2>>
+          _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr bool operator()(
+      _Range1&& __range1, _Range2&& __range2, _Comp __comp = {}, _Proj1 __proj1 = {}, _Proj2 __proj2 = {}) const {
+    return std::__includes(
+        ranges::begin(__range1),
+        ranges::end(__range1),
+        ranges::begin(__range2),
+        ranges::end(__range2),
+        ranges::__make_projected_comp(__comp, __proj1, __proj2));
   }
-
 };
 
 } // namespace __includes
 
 inline namespace __cpo {
   inline constexpr auto includes = __includes::__fn{};
 } // namespace __cpo
 } // namespace ranges
 
 _LIBCPP_END_NAMESPACE_STD
 
 #endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
 
 #endif // _LIBCPP___ALGORITHM_RANGES_INCLUDES_H

libcxx/include/algorithm

constexpr set_union_result<I1, I2, O>
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
 
   template<input_range R1, input_range R2, weakly_incrementable O,
            class Comp = ranges::less, class Proj1 = identity, class Proj2 = identity>
     requires mergeable<iterator_t<R1>, iterator_t<R2>, O, Comp, Proj1, Proj2>
     constexpr set_union_result<borrowed_iterator_t<R1>, borrowed_iterator_t<R2>, O>
       set_union(R1&& r1, R2&& r2, O result, Comp comp = {},
                 Proj1 proj1 = {}, Proj2 proj2 = {});                                                // since C++20
+
+  template<input_iterator I1, sentinel_for<I1> S1, input_iterator I2, sentinel_for<I2> S2,
+           class Proj1 = identity, class Proj2 = identity,
+           indirect_strict_weak_order<projected<I1, Proj1>, projected<I2, Proj2>> Comp =
+             ranges::less>
+    constexpr bool includes(I1 first1, S1 last1, I2 first2, S2 last2, Comp comp = {},
+                            Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
+  
+  template<input_range R1, input_range R2, class Proj1 = identity,
+           class Proj2 = identity,
+           indirect_strict_weak_order<projected<iterator_t<R1>, Proj1>,
+                                      projected<iterator_t<R2>, Proj2>> Comp = ranges::less>
+    constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
+                            Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
 }
 
     constexpr bool     // constexpr in C++20
     all_of(InputIterator first, InputIterator last, Predicate pred);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     any_of(InputIterator first, InputIterator last, Predicate pred);

 #include <__algorithm/ranges_fill_n.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_end.h>
 #include <__algorithm/ranges_find_first_of.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_for_each.h>
 #include <__algorithm/ranges_for_each_n.h>
+#include <__algorithm/ranges_includes.h>
 #include <__algorithm/ranges_is_partitioned.h>
 #include <__algorithm/ranges_is_sorted.h>
 #include <__algorithm/ranges_is_sorted_until.h>
 #include <__algorithm/ranges_lexicographical_compare.h>
 #include <__algorithm/ranges_lower_bound.h>
 #include <__algorithm/ranges_make_heap.h>
 #include <__algorithm/ranges_max.h>
 #include <__algorithm/ranges_max_element.h>

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_comparators.pass.cpp

#endif
     (void)std::ranges::find_if_not(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(first, last, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     (void)std::ranges::for_each(a, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     (void)std::ranges::for_each_n(first, count, UnaryVoid(&copies)); assert(copies == 1); copies = 0;
     //(void)std::ranges::generate(first, last, NullaryValue(&copies)); assert(copies == 0);
     //(void)std::ranges::generate(a, NullaryValue(&copies)); assert(copies == 0);
     //(void)std::ranges::generate_n(first, count, NullaryValue(&copies)); assert(copies == 0);
-    //(void)std::ranges::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0);
-    //(void)std::ranges::includes(a, b, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::includes(first, last, first2, last2, Less(&copies)); assert(copies == 0);
+    (void)std::ranges::includes(a, b, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap(a, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap_until(first, last, Less(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap_until(a, Less(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(first, last, UnaryTrue(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(a, UnaryTrue(&copies)); assert(copies == 0);
     //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(&copies)); assert(copies == 0);
     //(void)std::ranges::is_permutation(a, b, Equal(&copies)); assert(copies == 0);

libcxx/test/libcxx/algorithms/ranges_robust_against_copying_projections.pass.cpp

#endif
     (void)std::ranges::find_first_of(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::find_if_not(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(first, last, UnaryVoid(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each(a, UnaryVoid(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::for_each_n(first, count, UnaryVoid(), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
-    //(void)std::ranges::includes(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::includes(first, last, first2, last2, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::includes(a, b, Less(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap(a, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap_until(first, last, Less(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_heap_until(a, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::is_partitioned(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_permutation(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);
     //(void)std::ranges::is_permutation(a, b, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/std/algorithms/alg.sorting/alg.set.operations/includes/ranges_includes.pass.cpp

 //   constexpr bool includes(R1&& r1, R2&& r2, Comp comp = {},
 //                           Proj1 proj1 = {}, Proj2 proj2 = {});                                   // Since C++20
 
 #include <algorithm>
 #include <array>
 #include <concepts>
 #include <functional>
 #include <ranges>
+#include <utility>
 
 #include "almost_satisfies_types.h"
 #include "test_iterators.h"
 
-// TODO: SFINAE tests.
+template <
+    class Iter1 = int*,
+    class Sent1 = int*,
+    class Iter2 = int*,
+    class Sent2 = int*,
+    class Comp  = std::ranges::less,
+    class Proj1 = std::identity,
+    class Proj2 = std::identity>
+concept HasIncludesIter =
+    requires(Iter1&& iter1, Sent1&& sent1, Iter2&& iter2, Sent2&& sent2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) {
+      std::ranges::includes(
+          std::forward<Iter1>(iter1),
+          std::forward<Sent1>(sent1),
+          std::forward<Iter2>(iter2),
+          std::forward<Sent2>(sent2),
+          std::forward<Comp>(comp),
+          std::forward<Proj1>(proj1),
+          std::forward<Proj2>(proj2));
+    };
+
+static_assert(HasIncludesIter<int*, int*, int*, int*>);
+
+// !std::input_iterator<I1>
+static_assert(!HasIncludesIter<InputIteratorNotDerivedFrom>);
+
+// !std::sentinel_for<S1, I1>
+static_assert(!HasIncludesIter<int*, SentinelForNotSemiregular>);
+
+// !std::input_iterator<I2>
+static_assert(!HasIncludesIter<int*, int*, InputIteratorNotDerivedFrom>);
+
+// !std::sentinel_for<S2, I2>
+static_assert(!HasIncludesIter<int*, int*, int*, SentinelForNotSemiregular>);
+
+// !indirect_strict_weak_order<Comp, projected<I1, Proj1>, projected<I2, Proj2>>
+struct NotAComparator {};
+static_assert(!HasIncludesIter<int*, int*, int*, int*, NotAComparator>);
+
+template <
+    class Range1,
+    class Range2,
+    class Comp  = std::ranges::less,
+    class Proj1 = std::identity,
+    class Proj2 = std::identity>
+concept HasIncludesRange =
+    requires(Range1&& range1, Range2&& range2, Comp&& comp, Proj1&& proj1, Proj2&& proj2) {
+      std::ranges::includes(
+          std::forward<Range1>(range1),
+          std::forward<Range2>(range2),
+          std::forward<Comp>(comp),
+          std::forward<Proj1>(proj1),
+          std::forward<Proj2>(proj2));
+    };
+
+template <class T>
+using R = UncheckedRange<T>;
+
+static_assert(HasIncludesRange<R<int*>, R<int*>>);
+
+// !std::input_range<R2>
+static_assert(!HasIncludesRange<R<InputIteratorNotDerivedFrom>, R<int*>>);
+
+// !std::input_range<R2>
+static_assert(!HasIncludesRange<R<int*>, R<InputIteratorNotDerivedFrom>>);
+
+// !indirect_strict_weak_order<Comp, projected<iterator_t<R1>, Proj1>,
+//                                   projected<iterator_t<R2>, Proj2>>
+static_assert(!HasIncludesRange<R<int*>, R<int*>, NotAComparator>);
+
+template <class In1, class In2, template <class> class SentWrapper, std::size_t N1, std::size_t N2>
+constexpr void testIncludesImpl(std::array<int, N1> in1, std::array<int, N2> in2, bool expected) {
+  using Sent1 = SentWrapper<In1>;
+  using Sent2 = SentWrapper<In2>;
+
+  // iterator overload
+  {
+    std::same_as<bool> decltype(auto) result = std::ranges::includes(
+        In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}, In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}});
+    assert(result == expected);
+  }
+
+  // range overload
+  {
+    std::ranges::subrange r1{In1{in1.data()}, Sent1{In1{in1.data() + in1.size()}}};
+    std::ranges::subrange r2{In2{in2.data()}, Sent2{In2{in2.data() + in2.size()}}};
+    std::same_as<bool> decltype(auto) result = std::ranges::includes(r1, r2);
+    assert(result == expected);
+  }
+}
+
+template <class In1, class In2, template <class> class SentWrapper>
+constexpr void testImpl() {
+  // range 1 shorter than range2
+  {
+    std::array in1{0, 1, 5, 6, 9, 10};
+    std::array in2{3, 6, 7, 9, 13, 15, 100};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+  // range 2 shorter than range 1 but not subsequence
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 1 and range 2 has the same length but different elements
+  {
+    std::array in1{2, 6, 8, 12, 15, 16};
+    std::array in2{0, 2, 8, 15, 17, 19};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 1 == range 2
+  {
+    std::array in1{0, 1, 2};
+    std::array in2{0, 1, 2};
+    bool expected = true;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 2 is subsequence of range 1
+  {
+    std::array in1{8, 9, 10, 12, 13};
+    std::array in2{8, 10};
+    bool expected = true;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 1 is subsequence of range 2
+  {
+    std::array in1{0, 1, 1};
+    std::array in2{0, 1, 1, 2, 5};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 2 is subsequence of range 1 with duplicated elements
+  {
+    std::array in1{8, 9, 10, 12, 12, 12};
+    std::array in2{8, 12, 12};
+    bool expected = true;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 2 is not a subsequence of range 1 because of duplicated elements
+  {
+    std::array in1{8, 9, 10, 12, 13};
+    std::array in2{8, 10, 10};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 1 is empty
+  {
+    std::array<int, 0> in1{};
+    std::array in2{3, 4, 5};
+    bool expected = false;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // range 2 is empty
+  {
+    std::array in1{3, 4, 5};
+    std::array<int, 0> in2{};
+    bool expected = true;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+
+  // both ranges are empty
+  {
+    std::array<int, 0> in1{};
+    std::array<int, 0> in2{};
+    bool expected = true;
+    testIncludesImpl<In1, In2, SentWrapper>(in1, in2, expected);
+  }
+}
+
+template <class Iter2, template <class> class SentWrapper>
+constexpr void withAllPermutationsOfIter1() {
+  // C++17 InputIterator may or may not satisfy std::input_iterator
+  testImpl<cpp20_input_iterator<int*>, Iter2, sentinel_wrapper>();
+  testImpl<forward_iterator<int*>, Iter2, SentWrapper>();
+  testImpl<bidirectional_iterator<int*>, Iter2, SentWrapper>();
+  testImpl<random_access_iterator<int*>, Iter2, SentWrapper>();
+  testImpl<contiguous_iterator<int*>, Iter2, SentWrapper>();
+  testImpl<int*, Iter2, SentWrapper>();
+}
+
+template <template <class> class SentWrapper>
+constexpr void withAllPermutationsOfIter1AndIter2() {
+  withAllPermutationsOfIter1<cpp20_input_iterator<int*>, sentinel_wrapper>();
+  withAllPermutationsOfIter1<forward_iterator<int*>, SentWrapper>();
+  withAllPermutationsOfIter1<bidirectional_iterator<int*>, SentWrapper>();
+  withAllPermutationsOfIter1<random_access_iterator<int*>, SentWrapper>();
+  withAllPermutationsOfIter1<contiguous_iterator<int*>, SentWrapper>();
+  withAllPermutationsOfIter1<int*, SentWrapper>();
+}
 
 constexpr bool test() {
-  // TODO: main tests.
-  // TODO: A custom comparator works.
-  // TODO: A custom projection works.
+  withAllPermutationsOfIter1AndIter2<std::type_identity_t>();
+  withAllPermutationsOfIter1AndIter2<sentinel_wrapper>();
+
+  struct Data {
+    int data;
+  };
+
+  // Test custom comparator
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{4}, Data{12}};
+
+    const auto comp = [](const Data& x, const Data& y) { return x.data < y.data; };
+    bool expected   = true;
+
+    // iterator overload
+    {
+      auto result = std::ranges::includes(r1.begin(), r1.end(), r2.begin(), r2.end(), comp);
+      assert(result == expected);
+    }
+
+    // range overload
+    {
+      auto result = std::ranges::includes(r1, r2, comp);
+      assert(result == expected);
+    }
+  }
+
+  // Test custom projection
+  {
+    std::array r1{Data{4}, Data{8}, Data{12}};
+    std::array r2{Data{4}, Data{9}};
+
+    const auto proj = &Data::data;
+    bool expected   = false;
+
+    // iterator overload
+    {
+      auto result = std::ranges::includes(r1.begin(), r1.end(), r2.begin(), r2.end(), {}, proj, proj);
+      assert(result == expected);
+    }
+
+    // range overload
+    {
+      auto result = std::ranges::includes(r1, r2, {}, proj, proj);
+      assert(result == expected);
+    }
+  }
+
+  // Complexity: At most 2 * ((last1 - first1) + (last2 - first2)) - 1
+  // comparisons and applications of each projection.
+  {
+    struct CompProjs {
+      std::size_t numberOfComp  = 0;
+      std::size_t numberOfProj1 = 0;
+      std::size_t numberOfProj2 = 0;
+
+      constexpr auto comp() {
+        return [this](int x, int y) {
+          ++numberOfComp;
+          return x < y;
+        };
+      }
+
+      constexpr auto proj1() {
+        return [this](const Data& d) {
+          ++numberOfProj1;
+          return d.data;
+        };
+      }
+
+      constexpr auto proj2() {
+        return [this](const Data& d) {
+          ++numberOfProj2;
+          return d.data;
+        };
+      }
+    };
+    std::array<Data, 4> r1{{{0}, {1}, {2}, {3}}};
+    std::array<Data, 2> r2{{{4}, {5}}};
+    const std::size_t maxOperation = 2 * (r1.size() + r2.size()) - 1;
+
+    // iterator overload
+    {
+      CompProjs compProjs{};
+
+      auto result = std::ranges::includes(
+          r1.begin(), r1.end(), r2.begin(), r2.end(), compProjs.comp(), compProjs.proj1(), compProjs.proj2());
+      assert(!result);
+      assert(compProjs.numberOfComp < maxOperation);
+      assert(compProjs.numberOfProj1 < maxOperation);
+      assert(compProjs.numberOfProj2 < maxOperation);
+    }
+
+    // range overload
+    {
+      CompProjs compProjs{};
+
+      auto result = std::ranges::includes(r1, r2, compProjs.comp(), compProjs.proj1(), compProjs.proj2());
+      assert(!result);
+      assert(compProjs.numberOfComp < maxOperation);
+      assert(compProjs.numberOfProj1 < maxOperation);
+      assert(compProjs.numberOfProj2 < maxOperation);
+    }
+  }
 
   return true;
 }
 
 int main(int, char**) {
   test();
   static_assert(test());
 
   return 0;
 }

libcxx/test/std/algorithms/ranges_robust_against_nonbool_predicates.pass.cpp

constexpr bool test_all() {
   test(std::ranges::minmax_element, in, binary_pred);
   test(std::ranges::count_if, in, unary_pred);
   test(std::ranges::search, in, in2, binary_pred);
   test(std::ranges::search_n, in, count, x, binary_pred);
   test(std::ranges::find_end, in, in2, binary_pred);
   test(std::ranges::is_partitioned, in, unary_pred);
   test(std::ranges::is_sorted, in, binary_pred);
   test(std::ranges::is_sorted_until, in, binary_pred);
-  //test(std::ranges::includes, in, in2, binary_pred);
+  test(std::ranges::includes, in, in2, binary_pred);
   //test(std::ranges::is_heap, in, binary_pred);
   //test(std::ranges::is_heap_until, in, binary_pred);
   //std::ranges::clamp(2, 1, 3, binary_pred);
   //test(std::ranges::is_permutation, in, in2, binary_pred);
   test(std::ranges::copy_if, in, out, unary_pred);
   //test(std::ranges::remove_copy_if, in, out, unary_pred);
   test(std::ranges::replace_if, in, unary_pred, x);
   //test(std::ranges::replace_copy_if, in, out, unary_pred, x);

libcxx/test/std/algorithms/ranges_robust_against_omitting_invoke.pass.cpp

constexpr bool test_all() {
   test(std::ranges::count, in, x, &Bar::val);
   test(std::ranges::count_if, in, &Foo::unary_pred, &Bar::val);
   test(std::ranges::search, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::search_n, in, count, x, &Foo::binary_pred, &Bar::val);
   test(std::ranges::find_end, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::is_partitioned, in, &Foo::unary_pred, &Bar::val);
   test(std::ranges::is_sorted, in, &Foo::binary_pred, &Bar::val);
   test(std::ranges::is_sorted_until, in, &Foo::binary_pred, &Bar::val);
-  //test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
+  test(std::ranges::includes, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   //test(std::ranges::is_heap, in, &Foo::binary_pred, &Bar::val);
   //test(std::ranges::is_heap_until, in, &Foo::binary_pred, &Bar::val);
   //std::ranges::clamp(b, a, c, &Foo::binary_pred);
   //test(std::ranges::is_permutation, in, in2, &Foo::binary_pred, &Bar::val, &Bar::val);
   test(std::ranges::for_each, in, &Foo::unary_pred, &Bar::val);
   std::ranges::for_each_n(in.begin(), count, &Foo::unary_pred, &Bar::val);
   // `copy`, `copy_n` and `copy_backward` have neither a projection nor a predicate.
   test(std::ranges::copy_if, in, out, &Foo::unary_pred, &Bar::val);

libcxx/test/std/algorithms/ranges_robust_against_proxy_iterators.pass.cpp

constexpr void run_tests() {
   test(std::ranges::count, in, x);
   test(std::ranges::count_if, in, unary_pred);
   test(std::ranges::search, in, in2);
   test(std::ranges::search_n, in, count, x);
   test(std::ranges::find_end, in, in2);
   test(std::ranges::is_partitioned, in, unary_pred);
   test(std::ranges::is_sorted, in);
   test(std::ranges::is_sorted_until, in);
-  //test(std::ranges::includes, in, in2);
+  test(std::ranges::includes, in, in2);
   //test(std::ranges::is_heap, in);
   //test(std::ranges::is_heap_until, in);
   //test(std::ranges::is_permutation, in, in2);
   test(std::ranges::for_each, in, std::identity{});
   std::ranges::for_each_n(in.begin(), count, std::identity{});
   if constexpr (std::copyable<T>) {
     test(std::ranges::copy, in, out);
     std::ranges::copy_n(in.begin(), count, out);

libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp

 static_assert(test(std::ranges::find_end, a, a));
 //static_assert(test(std::ranges::find_first_of, a, a));
 static_assert(test(std::ranges::find_if, a, odd));
 static_assert(test(std::ranges::find_if_not, a, odd));
 static_assert(test(std::ranges::for_each, a, odd));
 static_assert(test(std::ranges::for_each_n, a, 10, odd));
 //static_assert(test(std::ranges::generate, a, gen));
 //static_assert(test(std::ranges::generate_n, a, 10, gen));
-//static_assert(test(std::ranges::includes, a, a));
+static_assert(test(std::ranges::includes, a, a));
 //static_assert(test(std::ranges::inplace_merge, a, a+5));
 //static_assert(test(std::ranges::is_heap, a));
 //static_assert(test(std::ranges::is_heap_until, a));
 static_assert(test(std::ranges::is_partitioned, a, odd));
 //static_assert(test(std::ranges::is_permutation, a, a));
 static_assert(test(std::ranges::is_sorted, a));
 static_assert(test(std::ranges::is_sorted_until, a));
 static_assert(test(std::ranges::lexicographical_compare, a, a));