[libc++] Implement ranges::contains

[Mordante]

Thanks for the patch.

The LLVM project will move to GitHub PRs tomorrow. As outlined on discourse the libc++ team would like to focus on closing active reviews. It would be great if you can close this review and make a GitHub PR instead.

[philnik]

Could you abandon this, since there is a PR open on GitHub?

libcxx/include/CMakeLists.txt

set(files
   __algorithm/pstl_frontend_dispatch.h
   __algorithm/pstl_transform.h
   __algorithm/push_heap.h
   __algorithm/ranges_adjacent_find.h
   __algorithm/ranges_all_of.h
   __algorithm/ranges_any_of.h
   __algorithm/ranges_binary_search.h
   __algorithm/ranges_clamp.h
+  __algorithm/ranges_contains.h
   __algorithm/ranges_copy.h
   __algorithm/ranges_copy_backward.h
   __algorithm/ranges_copy_if.h
   __algorithm/ranges_copy_n.h
   __algorithm/ranges_count.h
   __algorithm/ranges_count_if.h
   __algorithm/ranges_equal.h
   __algorithm/ranges_equal_range.h

libcxx/include/__algorithm/ranges_contains.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_RANGES_CONTAINS_H
+#define _LIBCPP___ALGORITHM_RANGES_CONTAINS_H
+
+#include <__algorithm/in_in_result.h>
+#include <__algorithm/ranges_starts_with.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/indirectly_comparable.h>
+#include <__ranges/access.h>
+#include <__ranges/concepts.h>
+#include <__utility/move.h>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+#if _LIBCPP_STD_VER >= 23
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __contains {
+struct __fn {
+  template <class _Iter, class _Sent, class _Type, class _Proj>
+  _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool
+  __compare_single_element(_Iter __first, _Sent __last, const _Type& __value, _Proj& __proj = {}) const {
+    auto __pred = [&](auto&& __e) { return std::forward<decltype(__e)>(__e) == __value; };
+    for (; __first != __last; ++__first) {
+      if (std::invoke(std::move(__pred), std::invoke(std::move(__proj), *__first)))
+        return true;
+    }
+    return false;
+  }
+
+  template <input_iterator _Iter, sentinel_for<_Iter> _Sent, class _Type, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<_Iter, _Proj>, const _Type*>
+  _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool
+  operator()(_Iter __first, _Sent __last, const _Type& __value, _Proj __proj = {}) const {
+    return __compare_single_element(std::move(__first), std::move(__last), __value, __proj);
+  }
+
+  template <input_range _Range, class _Type, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Range>, _Proj>, const _Type*>
+  _LIBCPP_NODISCARD_EXT _LIBCPP_HIDE_FROM_ABI constexpr bool
+  operator()(_Range&& __range, const _Type& __value, _Proj __proj = {}) const {
+    return __compare_single_element(ranges::begin(__range), ranges::end(__range), __value, __proj);
+  }
+};
+} // namespace __contains
+inline namespace __cpo {
+inline constexpr auto contains = __contains::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER >= 23
+
+#endif // _LIBCPP___ALGORITHM_RANGES_CONTAINS_H

libcxx/include/algorithm

template<class I, class O>
     using copy_n_result = in_out_result<I, O>;                                              // since C++20
 
   template<class I, class O>
     using copy_if_result = in_out_result<I, O>;                                             // since C++20
 
   template<class I1, class I2>
     using copy_backward_result = in_out_result<I1, I2>;                                     // since C++20
 
+  template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+    constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});       // since C++23
+
+  template<input_range R, class T, class Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+    constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});                 // since C++23
+
   template<input_iterator I, sentinel_for<I> S, weakly_incrementable O>
     requires indirectly_copyable<I, O>
     constexpr ranges::copy_result<I, O> ranges::copy(I first, S last, O result);            // since C++20
 
   template<input_range R, weakly_incrementable O>
     requires indirectly_copyable<iterator_t<R>, O>
     constexpr ranges::copy_result<borrowed_iterator_t<R>, O> ranges::copy(R&& r, O result); // since C++20
 

 #include <__algorithm/pstl_for_each.h>
 #include <__algorithm/pstl_transform.h>
 #include <__algorithm/push_heap.h>
 #include <__algorithm/ranges_adjacent_find.h>
 #include <__algorithm/ranges_all_of.h>
 #include <__algorithm/ranges_any_of.h>
 #include <__algorithm/ranges_binary_search.h>
 #include <__algorithm/ranges_clamp.h>
+#include <__algorithm/ranges_contains.h>
 #include <__algorithm/ranges_copy.h>
 #include <__algorithm/ranges_copy_backward.h>
 #include <__algorithm/ranges_copy_if.h>
 #include <__algorithm/ranges_copy_n.h>
 #include <__algorithm/ranges_count.h>
 #include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_equal.h>
 #include <__algorithm/ranges_equal_range.h>

libcxx/include/module.modulemap.in

module __algorithm {
       module ranges_binary_search {
         private header "__algorithm/ranges_binary_search.h"
         export functional.__functional.ranges_operations
       }
       module ranges_clamp {
         private header "__algorithm/ranges_clamp.h"
         export functional.__functional.ranges_operations
       }
+      module ranges_contains                 { private header "__algorithm/ranges_contains.h" }
       module ranges_copy {
         private header "__algorithm/ranges_copy.h"
         export algorithm.__algorithm.in_out_result
       }
       module ranges_copy_backward {
         private header "__algorithm/ranges_copy_backward.h"
         export algorithm.__algorithm.in_out_result
       }

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

constexpr bool all_the_algorithms()
     (void)std::ranges::adjacent_find(a, Equal(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::all_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::all_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::any_of(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::any_of(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(first, last, value, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::binary_search(a, value, Less(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::clamp(T(), T(), T(), Less(), Proj(&copies)); assert(copies == 0);
+#if TEST_STD_VER > 20
+    (void)std::ranges::contains(first, last, value, Proj(&copies)); assert(copies == 0);
+    (void)std::ranges::contains(a, value, Proj(&copies)); assert(copies == 0);
+#endif
     (void)std::ranges::count(first, last, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count(a, value, Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(first, last, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::count_if(a, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(first, last, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
     (void)std::ranges::copy_if(a, first2, UnaryTrue(), Proj(&copies)); assert(copies == 0);
 #if TEST_STD_VER > 20
     //(void)std::ranges::ends_with(first, last, first2, last2, Equal(), Proj(&copies), Proj(&copies)); assert(copies == 0);

libcxx/test/libcxx/private_headers.verify.cpp

 #include <__algorithm/pstl_backends/cpu_backends/serial.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/serial.h'}}
 #include <__algorithm/pstl_backends/cpu_backends/transform.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/pstl_backends/cpu_backends/transform.h'}}
 #include <__algorithm/push_heap.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/push_heap.h'}}
 #include <__algorithm/ranges_adjacent_find.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_adjacent_find.h'}}
 #include <__algorithm/ranges_all_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_all_of.h'}}
 #include <__algorithm/ranges_any_of.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_any_of.h'}}
 #include <__algorithm/ranges_binary_search.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_binary_search.h'}}
 #include <__algorithm/ranges_clamp.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_clamp.h'}}
+#include <__algorithm/ranges_contains.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_contains.h'}}
 #include <__algorithm/ranges_copy.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy.h'}}
 #include <__algorithm/ranges_copy_backward.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_backward.h'}}
 #include <__algorithm/ranges_copy_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_if.h'}}
 #include <__algorithm/ranges_copy_n.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_copy_n.h'}}
 #include <__algorithm/ranges_count.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
 #include <__algorithm/ranges_count_if.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
 #include <__algorithm/ranges_equal.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal.h'}}
 #include <__algorithm/ranges_equal_range.h> // expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_equal_range.h'}}

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

+//===----------------------------------------------------------------------===//
+//
+// 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
+//
+//===----------------------------------------------------------------------===//
+
+// <algorithm>
+
+// UNSUPPORTED: c++03, c++11, c++14, c++17, c++20
+// template<input_iterator I, sentinel_for<I> S, class T, class Proj = identity>
+//     requires indirect_binary_predicate<ranges::equal_to, projected<I, Proj>, const T*>
+//     constexpr bool ranges::contains(I first, S last, const T& value, Proj proj = {});       // since C++23
+
+// template<input_range R, class T, class Proj = identity>
+//     requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+//     constexpr bool ranges::contains(R&& r, const T& value, Proj proj = {});                 // since C++23
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+#include <vector>
+
+#include "almost_satisfies_types.h"
+#include "boolean_testable.h"
+#include "test_iterators.h"
+
+struct NotEqualityComparable {};
+
+template <class Iter, class Sent = Iter>
+concept HasContainsIt = requires(Iter iter, Sent sent) { std::ranges::contains(iter, sent, *iter); };
+
+static_assert(HasContainsIt<int*>);
+static_assert(!HasContainsIt<NotEqualityComparable*>);
+static_assert(!HasContainsIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasContainsIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasContainsIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasContainsIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
+static_assert(!HasContainsIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
+
+static_assert(!HasContainsIt<int*, int>);
+static_assert(!HasContainsIt<int, int*>);
+
+template <class Range, class ValT>
+concept HasContainsR = requires(Range range) { std::ranges::contains(range, ValT{}); };
+
+static_assert(HasContainsR<std::array<int, 1>, int>);
+static_assert(!HasContainsR<int, int>);
+static_assert(!HasContainsR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
+static_assert(!HasContainsR<InputRangeNotDerivedFrom, int>);
+static_assert(!HasContainsR<InputRangeNotIndirectlyReadable, int>);
+static_assert(!HasContainsR<InputRangeNotInputOrOutputIterator, int>);
+static_assert(!HasContainsR<InputRangeNotSentinelSemiregular, int>);
+static_assert(!HasContainsR<InputRangeNotSentinelEqualityComparableWith, int>);
+
+static std::vector<int> comparable_data;
+
+// clang-format off
+template <class Iter, class Sent = Iter>
+constexpr void test_iterators() {
+  using ValueT = std::iter_value_t<Iter>;
+  {  // simple tests
+    {
+      ValueT a[] = {1, 2, 3, 4, 5, 6};
+      std::same_as<bool> auto ret =
+        std::ranges::contains(Iter(a), Sent(Iter(a + 6)), 3);
+      assert(ret);
+    }
+    {
+      ValueT a[] = {1, 2, 3, 4, 5, 6};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 6)));
+      std::same_as<bool> decltype(auto) ret =
+        std::ranges::contains(range, 3);
+      assert(ret);
+    }
+  }
+
+  { // check that an empty range works
+    {
+      ValueT a[] = {};
+      auto ret = std::ranges::contains(Iter(a), Sent(Iter(a)), 1);
+      assert(!ret);
+    }
+    {
+      ValueT a[] = {};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a)));
+      auto ret = std::ranges::contains(range, 1);
+      assert(!ret);
+    }
+  }
+
+  { // check that no match
+    {
+      ValueT a[] = {13, 1, 21, 4, 5};
+      auto ret = std::ranges::contains(Iter(a), Sent(Iter(a + 5)), 10);
+      assert(!ret);
+    }
+    {
+      ValueT a[] = {13, 1, 21, 4, 5};
+      auto range = std::ranges::subrange(Iter(a), Sent(Iter(a + 5)));
+      auto ret = std::ranges::contains(range, 10);
+      assert(!ret);
+    }
+  }
+
+  if (!std::is_constant_evaluated())
+    comparable_data.clear();
+}
+template <class ElementT>
+class TriviallyComparable {
+  ElementT el_;
+
+public:
+  TEST_CONSTEXPR TriviallyComparable(ElementT el) : el_(el) {}
+  bool operator==(const TriviallyComparable&) const = default;
+};
+
+template <class IndexT>
+class Comparable {
+  IndexT index_;
+
+public:
+  Comparable(IndexT i)
+      : index_([&]() {
+          IndexT size = static_cast<IndexT>(comparable_data.size());
+          comparable_data.push_back(i);
+          return size;
+        }()) {}
+
+  bool operator==(const Comparable& other) const {
+    return comparable_data[other.index_] == comparable_data[index_];
+  }
+
+  friend bool operator==(const Comparable& lhs, long long rhs) { return comparable_data[lhs.index_] == rhs; }
+};
+
+constexpr bool test() {
+  types::for_each(types::type_list<char, wchar_t, int, long, 
+                  TriviallyComparable<char>, TriviallyComparable<wchar_t>>{},
+                  []<class T> {
+                    types::for_each(types::cpp20_input_iterator_list<T*>{}, 
+                      []<class Iter> {
+                      if constexpr (std::forward_iterator<Iter>)
+                        test_iterators<Iter>();
+                      test_iterators<Iter, sentinel_wrapper<Iter>>();
+                      test_iterators<Iter, sized_sentinel<Iter>>();
+                    });
+                  });
+
+  {
+    // count invocations of the projection
+    {
+      int a[] = {1, 9, 0, 13, 25};
+      int projection_count = 0;
+      auto ret = std::ranges::contains(a, a + 5, 0,
+                                [&](int i) { ++projection_count; return i; });
+      assert(ret);
+      assert(projection_count == 3);
+    }
+    {
+      int a[] ={1, 9, 0, 13, 25};
+      int projection_count = 0;
+      auto range = std::ranges::subrange(a, a + 5);
+      auto ret = std::ranges::contains(range, 0, [&](int i) { ++projection_count; return i; });
+      assert(ret);
+      assert(projection_count == 3);
+    }
+  }
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  types::for_each(types::type_list<Comparable<char>, Comparable<wchar_t>>{},
+                []<class T> {
+                  types::for_each(types::cpp20_input_iterator_list<T*>{}, 
+                    []<class Iter> {
+                    if constexpr (std::forward_iterator<Iter>)
+                      test_iterators<Iter>();
+                    test_iterators<Iter, sentinel_wrapper<Iter>>();
+                    test_iterators<Iter, sized_sentinel<Iter>>();
+                  });
+                });
+
+  return 0;
+}

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

 
 // [algorithm.syn]
 
 static_assert(test(std::ranges::adjacent_find, a));
 static_assert(test(std::ranges::all_of, a, odd));
 static_assert(test(std::ranges::any_of, a, odd));
 static_assert(test(std::ranges::binary_search, a, 42));
 static_assert(test(std::ranges::clamp, 42, 42, 42));
+static_assert(test(std::ranges::contains, a, 42));
 static_assert(test(std::ranges::copy, a, a));
 static_assert(test(std::ranges::copy_backward, a, a));
 static_assert(test(std::ranges::copy_if, a, a, odd));
 static_assert(test(std::ranges::copy_n, a, 10, a));
 static_assert(test(std::ranges::count, a, 42));
 static_assert(test(std::ranges::count_if, a, odd));
 //static_assert(test(std::ranges::ends_with, a, a));
 static_assert(test(std::ranges::equal, a, a));