[libc++][ranges] Implement ranges::count{, _if}

[philnik]

• Update documentation

[Mordante]

In general looks good, but several minor issues.

libcxx/include/__algorithm/ranges_count.h

39

This differs from the wording invoke(proj, *i) == value for the overloads with a parameter proj but no parameter pred;
Does your code generate the same assembly as the wording in the Standard or does it generate extra overhead?

libcxx/include/algorithm

91

This is already in the namespace ranges and matches the other functions.
(The same for the other new functions.)

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

35

HasFindIt smells like a copy-paste, please update the name.

85

To avoid duplication this line could be placed in its parent block.

138

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp

49

Another copy-paste.

69

Why the mutable? I see it used at multiple places.

127

This comment is wrong.

169

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_count.h

39

What exactly do you think differs between my implementation and the standard? (https://godbolt.org/z/GvGvT7fxT) At least my ranges::count and std::count produce for this example the exact same assembly at -O1.

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

85

Arthur asked me to duplicate it in other tests to have the definition near the usage.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp

69

I think that's a leftover from some iteration of this test.

127

What's wrong with the comment? It checks that 0 is returned when there is no match?

[Mordante]

It looks like the CI failures aren't related to this change. LGTM, modulo one small issue.

libcxx/include/__algorithm/ranges_count.h

39

The indirection using the lambda is the difference. For -O0, the version with the lambda generates a lot more code for this version. Starting at -O1 both versions generate the same output.
But I don't feel too strongly about slightly worse codegen at -O0.

libcxx/include/__algorithm/ranges_count_if.h

28

Sorry I missed this in the previous review, but _LIBCPP_HAS_NO_CONCEPTS is no longer required.

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

85

For these small tests I would prefer to avoid duplication. However since Arthur asked you to do it this way, let's keep it as-is.

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp

127

Sorry I misread, please ignore my previous remark.

[philnik]

• Address comments

[ldionne]

Looks pretty good, with some comments especially about exhaustiveness in the tests.

libcxx/include/__algorithm/ranges_count.h

39

@tcanens 's comment on ranges::find probably applies here too -- this should be -> bool IIUC (please add test, too).

Also, we should use auto&& __e.

libcxx/include/__algorithm/ranges_count_if.h

33

FWIW, I'm not a huge fan of extremely terse names like this. I'd find _Iterator and _Sentinel clearer. This is non-blocking, but that would be easier to read, and it's not like we gain anything by using fewer characters. This applies throughout the patch.

35

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

60–70

Here, you should test with a 0-sized range and 1-sized range too. And for each range size (when that makes sense), you can vary the position of the element you're finding. Right now, you're always finding the last element in the range -- that's not exhaustive enough. You can also check for an element which is not in the range.

Then, you can remove a couple of tests below that are only run on int[], like the one that says // check that 0 is returned with no match.

This comment applies to the other algorithms patches I haven't looked at yet -- we need to be more exhaustive when checking algorithms, especially since it's so easy to do.

[philnik]

• Address comments

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

60–70

I'm not sure what you are asking for. Do you want that the result changes for every iterator type? Or just have more invocations for each of them?

[var-const]

libcxx/include/__algorithm/ranges_count_if.h

39

Question: in the Standard, there's an explicit cast to bool, but I presume it doesn't matter because the return type is implicitly converted to bool by virtue of being used in an if expression, right?

50

Question: hmm, there are no constraints on iter/range_difference_t (in the Standard), but the implementation has to make certain assumptions about the type. I wonder if it would be a good idea to have a constraint on that as well (unless this constraint comes from somewhere implicitly). What do you think?

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

45

I think there are a couple more SFINAE cases to test:

• projected<I, P> is invalid;
• iter/range_difference_t is invalid.

60

Nit: can you please add a comment to this test case as well, even something as simple as "Normal case" or similar? It just makes skimming through the file easier.

64

Can you add:

• a test case where ret > 1 to make sure the algorithm counts equivalent elements properly?
• a test case where all the elements are equal to the given element?

78

Question: why not use a.begin() and a.end()?

90

Nit: s/elment/element/.

121

Consider adding a test to ensure that a non-copyable (perhaps even non-movable) _Type works.

168

Can you also check that the return type is exactly iter/range_difference_t for a type that has some custom-defined difference type?

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp

2

(A few comments from the other test file apply here as well)

66

Hmm, quite a few test cases that are in ranges.count.pass.cpp seem to be missing here?

180

Can you also check that a predicate a) that takes its argument by lvalue; b) that has non-const operator() works?

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_count_if.h

39

Yes. ifs can use explicit conversions without the type being explicitly cast to bool. (https://godbolt.org/z/xr8nEb6xG)

50

There are constraints through input_iterator -> input_or_output_iterator -> weakly_incrementable. Specifically __signed_integer_like.

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

45

{iter, range}_difference_t is never invalid if input_{iterator, range} is valid. With projected i guess you meant indirect_binary_predicate? There I don't think I can do much more than NotEqualityComparable.

78

a.begin() and a.end() aren't portably int*, but they have to be int* for the casts to work.

[var-const]

libcxx/include/__algorithm/ranges_count_if.h

50

Ah, thanks for explaining.

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

246

Nit: s/auto/decltype(auto)/ (here and below).

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.pass.cpp

153

This should be count_if, not count.

[philnik]

• Address comments

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

246

I think we should stick with auto and only use decltype(auto) if we want to check that a reference is returned.

[var-const]

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

246

I think that

std::same_as<Foo> auto x = Bar();

and

static_assert(std::same_as<decltype(Bar()), Foo>);

should be exactly equivalent as far as checking the return type is concerned. If Bar() were to return const Foo&, the second check would catch that but not the first. Yes, it is highly unlikely that count could return a reference; however, I think it's easier to use an approach that is always guaranteed to work rather than deciding on a case-by-case basis.

[ldionne]

LGTM with my and Costa's comments. Thanks!

libcxx/include/__algorithm/ranges_count.h

39

My comment about -> bool can be ignored since this code is correct as-is. However, can we add tests like we did in D122011?

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.cpp

2

Please rebase onto main with the new way we generate those tests.

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

60–70

I think you can disregard this comment. I am not sure what I had in mind anymore, but I seem to have written it thinking that we were testing ranges::find, which is obviously not the case. I looked at the tests again and I don't think we are missing relevant coverage.

205–213

We usually say "NonMovable" instead of "Immobile". If you change it, it applies to the other test as well. Non-blocking, but it would be more idiomatic IMO.

[philnik]

• Address comments

libcxx/include/CMakeLists.txt

set(files
   __algorithm/partial_sort.h
   __algorithm/partial_sort_copy.h
   __algorithm/partition.h
   __algorithm/partition_copy.h
   __algorithm/partition_point.h
   __algorithm/pop_heap.h
   __algorithm/prev_permutation.h
   __algorithm/push_heap.h
+  __algorithm/ranges_count.h
+  __algorithm/ranges_count_if.h
   __algorithm/ranges_find.h
   __algorithm/ranges_find_if.h
   __algorithm/ranges_find_if_not.h
   __algorithm/ranges_max_element.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_mismatch.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/remove.h

libcxx/include/__algorithm/ranges_count.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_COUNT_H
+#define _LIBCPP___ALGORITHM_RANGES_COUNT_H
+
+#include <__algorithm/ranges_count_if.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/projected.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 > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __count {
+struct __fn {
+  template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Tp, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<_Ip, _Proj>, const _Tp*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last, const _Tp& __value, _Proj __proj = {}) const {
+    auto __pred = [&](const auto& __e) { return __e == __value; };
+    return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <input_range _Rp, class _Tp, class _Proj = identity>
+    requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<_Rp>, _Proj>, const _Tp*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_difference_t<_Rp> operator()(_Rp&& __r, const _Tp& __value, _Proj __proj = {}) const {
+    auto __pred = [&](const auto& __e) { return __e == __value; };
+    return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj);
+  }
+};
+} // namespace __count
+
+inline namespace __cpo {
+  inline constexpr auto count = __count::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // _LIBCPP_STD_VER > 17 && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_H

libcxx/include/__algorithm/ranges_count_if.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_COUNT_IF_H
+#define _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H
+
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/invoke.h>
+#include <__functional/ranges_operations.h>
+#include <__iterator/concepts.h>
+#include <__iterator/incrementable_traits.h>
+#include <__iterator/projected.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 !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+template <class _Ip, class _Sp, class _Proj, class _Pred>
+_LIBCPP_HIDE_FROM_ABI constexpr
+auto __count_if_impl(_Ip __first, _Sp __last, _Pred& __pred, _Proj& __proj) {
+  iter_difference_t<_Ip> __counter(0);
+  for (; __first != __last; ++__first) {
+    if (std::invoke(__pred, std::invoke(__proj, *__first)))
+      ++__counter;
+  }
+  return __counter;
+}
+
+namespace __count_if {
+struct __fn {
+  template <input_iterator _Ip, sentinel_for<_Ip> _Sp, class _Proj = identity,
+            indirect_unary_predicate<projected<_Ip, _Proj>> _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  iter_difference_t<_Ip> operator()(_Ip __first, _Sp __last, _Pred __pred, _Proj __proj = {}) const {
+    return ranges::__count_if_impl(std::move(__first), std::move(__last), __pred, __proj);
+  }
+
+  template <input_range _Rp, class _Proj = identity,
+            indirect_unary_predicate<projected<iterator_t<_Rp>, _Proj>> _Pred>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_difference_t<_Rp> operator()(_Rp&& __r, _Pred __pred, _Proj __proj = {}) const {
+    return ranges::__count_if_impl(ranges::begin(__r), ranges::end(__r), __pred, __proj);
+  }
+};
+} // namespace __count_if
+
+inline namespace __cpo {
+  inline constexpr auto count_if = __count_if::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+#endif // !defined(_LIBCPP_HAS_NO_CONCEPTS) && !defined(_LIBCPP_HAS_NO_INCOMPLETE_RANGES)
+
+#endif // _LIBCPP___ALGORITHM_RANGES_COUNT_IF_H

libcxx/include/algorithm

template<input_range R, class Proj = identity,
            indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
     constexpr borrowed_iterator_t<R>
       find_if_not(R&& r, Pred pred, Proj proj = {});                                // since C++20
 }
 
 template <class InputIterator, class Predicate>
     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);
 
 template <class InputIterator, class Predicate>
     constexpr bool     // constexpr in C++20
     none_of(InputIterator first, InputIterator last, Predicate pred);
 

 #include <__algorithm/partial_sort.h>
 #include <__algorithm/partial_sort_copy.h>
 #include <__algorithm/partition.h>
 #include <__algorithm/partition_copy.h>
 #include <__algorithm/partition_point.h>
 #include <__algorithm/pop_heap.h>
 #include <__algorithm/prev_permutation.h>
 #include <__algorithm/push_heap.h>
+#include <__algorithm/ranges_count.h>
+#include <__algorithm/ranges_count_if.h>
 #include <__algorithm/ranges_find.h>
 #include <__algorithm/ranges_find_if.h>
 #include <__algorithm/ranges_find_if_not.h>
 #include <__algorithm/ranges_max_element.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_mismatch.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/remove.h>

libcxx/include/module.modulemap

module __algorithm {
       module partial_sort             { private header "__algorithm/partial_sort.h" }
       module partial_sort_copy        { private header "__algorithm/partial_sort_copy.h" }
       module partition                { private header "__algorithm/partition.h" }
       module partition_copy           { private header "__algorithm/partition_copy.h" }
       module partition_point          { private header "__algorithm/partition_point.h" }
       module pop_heap                 { private header "__algorithm/pop_heap.h" }
       module prev_permutation         { private header "__algorithm/prev_permutation.h" }
       module push_heap                { private header "__algorithm/push_heap.h" }
+      module ranges_count             { private header "__algorithm/ranges_count.h" }
+      module ranges_count_if          { private header "__algorithm/ranges_count_if.h" }
       module ranges_find              { private header "__algorithm/ranges_find.h" }
       module ranges_find_if           { private header "__algorithm/ranges_find_if.h" }
       module ranges_find_if_not       { private header "__algorithm/ranges_find_if_not.h" }
       module ranges_max_element       { private header "__algorithm/ranges_max_element.h" }
       module ranges_min_element       { private header "__algorithm/ranges_min_element.h" }
       module ranges_mismatch          { private header "__algorithm/ranges_mismatch.h" }
       module ranges_swap_ranges       { private header "__algorithm/ranges_swap_ranges.h" }
       module remove                   { private header "__algorithm/remove.h" }

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count.module.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count.h'}}
+#include <__algorithm/ranges_count.h>

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_count_if.module.verify.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
+//
+//===----------------------------------------------------------------------===//
+
+// REQUIRES: modules-build
+
+// WARNING: This test was generated by 'generate_private_header_tests.py'
+// and should not be edited manually.
+
+// expected-error@*:* {{use of private header from outside its module: '__algorithm/ranges_count_if.h'}}
+#include <__algorithm/ranges_count_if.h>

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count.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
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// 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 iter_difference_t<I>
+//     ranges::count(I first, S last, const T& value, Proj proj = {});
+// template<input_range R, class T, class Proj = identity>
+//   requires indirect_binary_predicate<ranges::equal_to, projected<iterator_t<R>, Proj>, const T*>
+//   constexpr range_difference_t<R>
+//     ranges::count(R&& r, const T& value, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+struct NotEqualityComparable {};
+
+template <class It, class Sent = It>
+concept HasFindIt = requires(It it, Sent sent) { std::ranges::count(it, sent, *it); };
+static_assert(HasFindIt<int*>);
+static_assert(!HasFindIt<NotEqualityComparable*>);
+static_assert(!HasFindIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasFindIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasFindIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasFindIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
+static_assert(!HasFindIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
+
+static_assert(!HasFindIt<int*, int>);
+static_assert(!HasFindIt<int, int*>);
+
+template <class Range, class ValT>
+concept HasFindR = requires(Range r) { std::ranges::count(r, ValT{}); };
+static_assert(HasFindR<std::array<int, 1>, int>);
+static_assert(!HasFindR<int, int>);
+static_assert(!HasFindR<std::array<NotEqualityComparable, 1>, NotEqualityComparable>);
+static_assert(!HasFindR<InputRangeNotDerivedFrom, int>);
+static_assert(!HasFindR<InputRangeNotIndirectlyReadable, int>);
+static_assert(!HasFindR<InputRangeNotInputOrOutputIterator, int>);
+static_assert(!HasFindR<InputRangeNotSentinelSemiregular, int>);
+static_assert(!HasFindR<InputRangeNotSentinelEqualityComparableWith, int>);
+
+template <class It, class Sent = It>
+constexpr void test_iterators() {
+  {
+    int a[] = {1, 2, 3, 4};
+    std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(It(a), Sent(It(a + 4)), 4);
+    assert(ret == 1);
+  }
+  {
+    int a[] = {1, 2, 3, 4};
+    auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
+    std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(range, 4);
+    assert(ret == 1);
+  }
+}
+
+constexpr bool test() {
+  test_iterators<int*>();
+  test_iterators<const int*>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+
+  {
+    // check that projections are used properly and that they are called with the iterator directly
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::count(a, a + 4, a + 3, [](int& i) { return &i; });
+      assert(ret == 1);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::count(a, a + 3, [](int& i) { return &i; });
+      assert(ret == 1);
+    }
+  }
+
+  { // check that 0 is returned with no match
+    {
+      int a[] = {1, 1, 1};
+      auto ret = std::ranges::count(a, a + 3, 0);
+      assert(ret == 0);
+    }
+    {
+      int a[] = {1, 1, 1};
+      auto ret = std::ranges::count(a, 0);
+      assert(ret == 0);
+    }
+  }
+
+  {
+    // check that std::invoke is used
+    struct S { int i; };
+    S a[] = { S{1}, S{3}, S{2} };
+    std::same_as<std::ptrdiff_t> auto ret = std::ranges::count(a, 4, &S::i);
+    assert(ret == 0);
+  }
+
+  {
+    // count invocations of the projection
+    {
+      int a[] = {1, 2, 3, 4};
+      int projection_count = 0;
+      auto ret = std::ranges::count(a, a + 4, 2, [&](int i) { ++projection_count; return i; });
+      assert(ret == 1);
+      assert(projection_count == 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      int projection_count = 0;
+      auto ret = std::ranges::count(a, 2, [&](int i) { ++projection_count; return i; });
+      assert(ret == 1);
+      assert(projection_count == 4);
+    }
+  }
+
+  {
+    // check that an empty range works
+    {
+      std::array<int ,0> a = {};
+      auto ret = std::ranges::count(a.begin(), a.end(), 1);
+      assert(ret == 0);
+    }
+    {
+      std::array<int, 0> a = {};
+      auto ret = std::ranges::count(a, 1);
+      assert(ret == 0);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}

libcxx/test/std/algorithms/alg.nonmodifying/alg.count/ranges.count_if.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
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+// template<input_iterator I, sentinel_for<I> S, class Proj = identity,
+//          indirect_unary_predicate<projected<I, Proj>> Pred>
+//   constexpr iter_difference_t<I>
+//     ranges::count_if(I first, S last, Pred pred, Proj proj = {});
+// template<input_range R, class Proj = identity,
+//          indirect_unary_predicate<projected<iterator_t<R>, Proj>> Pred>
+//   constexpr range_difference_t<R>
+//     ranges::count_if(R&& r, Pred pred, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <ranges>
+
+#include "almost_satisfies_types.h"
+#include "test_iterators.h"
+
+struct Predicate {
+  bool operator()(int);
+};
+
+template <class It, class Sent = It>
+concept HasCountIfIt = requires(It it, Sent sent) { std::ranges::count_if(it, sent, Predicate{}); };
+static_assert(HasCountIfIt<int*>);
+static_assert(!HasCountIfIt<InputIteratorNotDerivedFrom>);
+static_assert(!HasCountIfIt<InputIteratorNotIndirectlyReadable>);
+static_assert(!HasCountIfIt<InputIteratorNotInputOrOutputIterator>);
+static_assert(!HasCountIfIt<cpp20_input_iterator<int*>, SentinelForNotSemiregular>);
+static_assert(!HasCountIfIt<cpp20_input_iterator<int*>, InputRangeNotSentinelEqualityComparableWith>);
+
+static_assert(!HasCountIfIt<int*, int>);
+static_assert(!HasCountIfIt<int, int*>);
+
+template <class Pred>
+concept HasFindIfPred = requires(int* it, Pred pred) {std::ranges::count_if(it, it, pred); };
+
+static_assert(!HasFindIfPred<IndirectUnaryPredicateNotCopyConstructible>);
+static_assert(!HasFindIfPred<IndirectUnaryPredicateNotPredicate>);
+
+template <class R>
+concept HasCountIfR = requires(R r) { std::ranges::count_if(r, Predicate{}); };
+static_assert(HasCountIfR<std::array<int, 0>>);
+static_assert(!HasCountIfR<int>);
+static_assert(!HasCountIfR<InputRangeNotDerivedFrom>);
+static_assert(!HasCountIfR<InputRangeNotIndirectlyReadable>);
+static_assert(!HasCountIfR<InputRangeNotInputOrOutputIterator>);
+static_assert(!HasCountIfR<InputRangeNotSentinelSemiregular>);
+static_assert(!HasCountIfR<InputRangeNotSentinelEqualityComparableWith>);
+
+template <class It, class Sent = It>
+constexpr void test_iterators() {
+  {
+    int a[] = {1, 2, 3, 4};
+    std::same_as<std::ptrdiff_t> auto ret =
+      std::ranges::count_if(It(a), Sent(It(a + 4)), [](int x) mutable { return x == 4; });
+    assert(ret == 1);
+  }
+  {
+    int a[] = {1, 2, 3, 4};
+    auto range = std::ranges::subrange(It(a), Sent(It(a + 4)));
+    std::same_as<std::ptrdiff_t> auto ret =
+      std::ranges::count_if(range, [](int x) mutable { return x == 4; });
+    assert(ret == 1);
+  }
+}
+
+constexpr bool test() {
+  test_iterators<int*>();
+  test_iterators<const int*>();
+  test_iterators<cpp20_input_iterator<int*>, sentinel_wrapper<cpp20_input_iterator<int*>>>();
+  test_iterators<bidirectional_iterator<int*>>();
+  test_iterators<forward_iterator<int*>>();
+  test_iterators<random_access_iterator<int*>>();
+  test_iterators<contiguous_iterator<int*>>();
+
+  {
+    // check that projections are used properly and that they are called with the iterator directly
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::count_if(a, a + 4, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; });
+      assert(ret == 1);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      auto ret = std::ranges::count_if(a, [&](int* i) { return i == a + 3; }, [](int& i) { return &i; });
+      assert(ret == 1);
+    }
+  }
+
+  {
+    // check that std::invoke is used
+    {
+      struct S {
+        int comp;
+        int other;
+      };
+      S a[] = { {0, 0}, {0, 2}, {0, 1} };
+      auto ret = std::ranges::count_if(a, [](int i){ return i == 0; }, &S::comp);
+      assert(ret == 3);
+    }
+    {
+      struct S {
+        int comp;
+        int other;
+      };
+      S a[] = { {0, 0}, {0, 2}, {0, 1} };
+      auto ret = std::ranges::count_if(a, a + 3, [](int i) { return i == 0; }, &S::comp);
+      assert(ret == 3);
+    }
+  }
+
+  {
+    // check that 0 is returned with no match
+    {
+      int a[] = {1, 1, 1};
+      auto ret = std::ranges::count_if(a, a + 3, [](int) { return false; });
+      assert(ret == 0);
+    }
+    {
+      int a[] = {1, 1, 1};
+      auto ret = std::ranges::count_if(a, [](int){ return false; });
+      assert(ret == 0);
+    }
+  }
+
+  {
+    // count projection and predicate invocation count
+    {
+      int a[] = {1, 2, 3, 4};
+      int predicate_count = 0;
+      int projection_count = 0;
+      auto ret = std::ranges::count_if(a, a + 4,
+                                       [&](int i) { ++predicate_count; return i == 2; },
+                                       [&](int i) { ++projection_count; return i; });
+      assert(ret == 1);
+      assert(predicate_count == 4);
+      assert(projection_count == 4);
+    }
+    {
+      int a[] = {1, 2, 3, 4};
+      int predicate_count = 0;
+      int projection_count = 0;
+      auto ret = std::ranges::count_if(a,
+                                       [&](int i) { ++predicate_count; return i == 2; },
+                                       [&](int i) { ++projection_count; return i; });
+      assert(ret == 1);
+      assert(predicate_count == 4);
+      assert(projection_count == 4);
+    }
+  }
+
+  {
+    // check that an empty range works
+    {
+      std::array<int ,0> a = {};
+      auto ret = std::ranges::count_if(a.begin(), a.end(), [](int) { return true; });
+      assert(ret == 0);
+    }
+    {
+      std::array<int, 0> a = {};
+      auto ret = std::ranges::count_if(a, [](int) { return true; });
+      assert(ret == 0);
+    }
+  }
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}