[libc++][ranges] Implement ranges::min

[• Quuxplusone]

The headline here is that we need to remember to std::invoke our predicates and projections. Sorry I'm just catching this now.

libcxx/include/__algorithm/ranges_min.h

16

Granularize?

34

Argh! Peeking at range-v3's code has just reminded me that we need to be using std::invoke for projections and comparators. Please fix here and probably in some earlier reviews too (sadly).
The test case for this would be, like,

struct S { int i; };
S a[3] = { S{2}, S{1}, S{3} };
decltype(auto) ret = std::ranges::min(a[0], a[1], {}, &S::i);
ASSERT_SAME_TYPE(decltype(ret), const S&);
assert(&ret == &a[1]);
assert(ret.i == 1);

and likewise for the initializer_list and range overloads.

41

This works, but why not just return *ranges::min_element(ranges::begin(__r), ranges::end(__r)...... oh, because you don't want to copy the comparator or the projection, right!
Very clever; I guess I have no problem with this. But attn @ldionne, do you think this is OK and/or can you think of a better pattern? Because I imagine we'll be doing this a lot.

AFAICT, range-v3 takes the middle path: it doesn't unnecessarily copy callables (much?), but it also takes no special precautions to avoid move-constructing them. We could go that route, but I think avoiding unnecessary moves is a QoI thing and we might as well do it right the first time.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

43–44

You probably intended

static_assert( HasMin<int(&)[10]>);
static_assert(!HasMin<NoLessThanOp(&)[10]>);
static_assert(!HasMin<NotTotallyOrdered(&)[10]>);

and/or

static_assert(!HasMin<std::initializer_list<NoLessThanOp>>);
static_assert(!HasMin<std::initializer_list<NotTotallyOrdered>>);

FYI, I'm getting more and more uncomfortable with this HasXxx pattern, because it makes it impossible to test rvalue types. I think you should switch, at least in new code, to

static_assert(std::invocable<decltype(std::ranges::min), std::initializer_list<int>>);
static_assert(std::invocable<decltype(std::ranges::min), int(&)[10]>);
static_assert(std::invocable<decltype(std::ranges::min), int(&&)[10]>); // impossible to express right now

52

I'd like a test for decltype(ranges::min(1,2)), etc. — it should return a const int&.

75

This should be std::same_as<int> decltype(auto) if that's allowed (I think it probably isn't), or else write it out longhand with decltype(auto) ret = ~~~ ASSERT_SAME_TYPE(decltype(ret), ~~~). What we're worried about here is that this overload of ranges::min should return exactly int, not a const int& that might dangle.

84

Nit: consider auto projection = []... to shorten this line.
Coverage: As recently discussed with @var-const in the std::mergeable PR, I'd like to see a little coverage for a projection like [](int& i) { ... }. In other words, std::ranges::min(a) should be forwarding along the constness of its range's elements. Notice that the elements of an initializer_list<T> are already const T; that's why the made-up iterator type in those overloads' constraints is const T* instead of T*. But when the range is a plain old non-const array, we should be able successfully to treat its elements as non-const lvalues.

102

Remember that [[maybe_unused]] is a code smell!
You should be asserting that ret == 1 here.

106

views::all isn't just borrowed, but also a view; and I don't think either of those properties are "interesting" to ranges::min, are they? This test case might be redundant.

[philnik]

• Address comments

[• Quuxplusone]

Please git grep ranges::min and fix what you find. std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp needs updating, at least.

[philnik]

• Address comments

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

43–44

I copy/pasted that part, so it's probably also not tested properly in the other test.

I'm getting more and more uncomfortable with this HasXxx pattern

concept HasMin = requires(T&& t) { std::ranges::min(std::forward<T>(t)); } should work for these cases, right?

75

At least clang is happy with concept decltype(auto). It also works as expected.

[• Quuxplusone]

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

43–44

Yes, it should; or even concept HasMin = requires { std::ranges::min(std::declval<T>()); }. I'm ambivalent as to the readability of that versus a straight std::invocable<RangeMinT, ...>, so, either is fine AFAIC.

75

At least clang is happy with concept decltype(auto)

Yep, Godbolt says everyone's happy with it, so, OK.

[philnik]

• Rebased
• Fix CI
• Address comment

[philnik]

Actually rebase

[philnik]

• Fix GCC

[philnik]

Does someone see why https://reviews.llvm.org/harbormaster/unit/view/2761914/ fails?

[• Quuxplusone]

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

80

In D119589#3339433, @philnik wrote:

Does someone see why https://reviews.llvm.org/harbormaster/unit/view/2761914/ fails?

__iterator/projected.h:28:34: error: 'std::__1::indirect_result_t<_Proj&, _It> std::__1::projected<_It, _Proj>::operator*() const [with _It = const test_initializer_list()::<lambda(int, int)>*; _Proj = std::__1::identity; std::__1::indirect_result_t<_Proj&, _It> = const test_initializer_list()::<lambda(int, int)>&]', declared using local type 'const test_initializer_list()::<lambda(int, int)>', is used but never defined [-fpermissive]
   28 |   indirect_result_t<_Proj&, _It> operator*() const; // not defined
      |                                  ^~~~~~~~

Kind of, but I think it's a GCC bug. GCC is complaining about the use of the "local type" decltype(comparator). We're instantiating projected<int*, decltype(comparator)> and declaring its operator*, but there's no way that operator* can ever be defined outside of this TU, and it's also not defined inside this TU, so that's a problem... at least for GCC, for some reason. (That is, I think GCC is mistakenly considering operator* to have been ODR-used, even though we're only using it in non-evaluated contexts AFAICT.)
I have not been able to reproduce the problem on Godbolt's version(s) of GCC. https://godbolt.org/z/hs8fTodM9 Can anyone else reproduce it?
(also attn @jwakely in case he has any ideas)

[jwakely]

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

80

Looks like a similar problem to https://gcc.gnu.org/PR92894 (and its https://gcc.gnu.org/PR94241 dup) which we decided was a problem with using a deduced return type in the library code, not a compiler bug.

[• Quuxplusone]

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

80

Ah, I (think I) get it. I've posted D120417 to check my guess.

[philnik]

Mark the test as XFAIL: gcc. Arthur is working on the problem in D120417.

[philnik]

• Add input range test

[• Quuxplusone]

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

16

I just landed D120417; rebase on main and try removing this XFAIL!

[philnik]

• Rebased
• Add synopsis

[philnik]

• Remove XFAIL

[var-const]

@philnik Can you also update RangesAlgorithms.csv?

libcxx/include/__algorithm/ranges_min.h

62

Question: the Standard has the requirement that the range is not empty for both this overload and the initializer_list overload, but it is only checked here. AFAICT, __min_element::__fn::__go doesn't do this check. Is there a reason to only apply this check here?

67

Some thoughts: this could lead to a lot of copying in the worst case. min_element doesn't have this problem because it stores the iterator instead; however, it's fine for min_element operating on forward_iterators but cannot be used here since we're iterating an input_range. It probably doesn't matter in most scenarios, but in the worst case, I could imagine that calling min on std::vector<ExpensiveToCopy> could result in copying every single element if the vector happens to be in descending order.

I wonder if it would be worthwhile to have an if constexpr to only copy iterators if the range is a forward range, and fall back to this implementation otherwise?

libcxx/include/__ranges/take_view.h

121 ↗

(On Diff #413771)

Thanks for going back to fix this! Sorry about the annoying comment -- do you know if this change affects the visible behavior of take_view (e.g., some code compiles now that wouldn't compile previously, or vice versa)? If yes, could you please add a test(s) for this?

libcxx/include/algorithm

48

Does the overload taking an initializer_list also need to be added?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

22

The initializer_list overload also seems to be missing from here.

27

Nit: <random> seems unused?

44

Should this be TotallyOrderedRval? Also, wouldn't this class need at least an equality operator to be totally ordered?

70

Nit: it seems like this test uses both static_assert and ASSERT_SAME_TYPE for comparing types, can it be consistent?

123

Nit: consider adding newlines between braced scopes. I just think it makes it easier to separate different test cases visually.

161

It seems like more SFINAE tests are needed -- I don't think constraints such as input_range, copyable, indirectly_copyable_storable, etc. are currently being checked.

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_min.h

67

I thought about that too, let's see what @Quuxplusone thinks.

libcxx/include/__ranges/take_view.h

121 ↗

(On Diff #413771)

I don't think so, but I could be wrong.

[• Quuxplusone]

libcxx/include/__algorithm/ranges_min.h

62

Nice catch!

Wording nit: s/has to/must/

It is difficult, but possible, to create an empty initializer_list:

std::initializer_list<int> il = {};
std::ranges::min(il);  // UB

I agree let's be consistent: either both should _LIBCPP_ASSERT or neither should. I have no particular preference which.

@var-const, both ranges::min_element and std::min_element are totally fine with a zero-element range; in that case there is no min element found, so they return last (which points to no element of the range).

67

Good point! I'm slightly worried there might be a subtlety we're all missing, but let's run with it for now.
However, @philnik, please put an } else { around lines 67–72: we don't want to instantiate that part of the template when forward_range<_Rp> is true.

libcxx/include/__ranges/take_view.h

121 ↗

(On Diff #413771)

This is just taking the min of two integers both of type range_size_t<_View>. I don't think there's any possible way for the behavior to be different.
In fact, if I ran the zoo, we'd just do

using _SizeT = range_size_t<_View>;
_SizeT __n = ranges::size(__base_);
return __n < static_cast<_SizeT>(__count_) ? __n : static_cast<_SizeT>(__count_);

and not pay for the instantiation (or inclusion) of ranges::min at all. (But generally libc++ style is to follow the reference implementation to the letter, so as to avoid bugs due to exactly the kind of over-cleverness I'm displaying here. So I recommend keeping this as ranges::min.)

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

123

Ultranit: I have a slight preference for not newlines between braced scopes — two almost-empty lines is enough separation for me. However, I also would change line 88 from

{ // test comparator

to

{
  // test comparator

(and likewise line 82, 129, and anywhere else I missed). Please make the line 82/88/etc change; and I recommend re-removing the blank lines, but won't die on that hill. :)

[philnik]

• Address comments

libcxx/include/__algorithm/ranges_min.h

67

According to https://godbolt.org/z/fjaxc9rT5 it doesn't get instantiated.

[philnik]

• Add else branch

[var-const]

libcxx/include/algorithm

42

Hmm, looking at the Standard, I see

template<class T, class Proj = identity,
         indirect_­strict_­weak_­order<projected<const T*, Proj>> Comp = ranges::less>
  constexpr const T& ranges::min(const T& a, const T& b, Comp comp = {}, Proj proj = {});

// initializer_list overload looks the same

template<input_­range R, class Proj = identity,
         indirect_­strict_­weak_­order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
  requires indirectly_­copyable_­storable<iterator_t<R>, range_value_t<R>*>
  constexpr range_value_t<R>
    ranges::min(R&& r, Comp comp = {}, Proj proj = {});

Should this be fixed (here and in the test file)?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

22

Nit: for consistency, please either add a newline between these two overloads, or remove the newline above (I'd prefer the former).

161

Hmm, I still don't see a check for input_range and indirectly_copyable_storable.

[• Quuxplusone]

libcxx/include/algorithm

42

Yikes, good catch! (The current PR has constexpr I min(I first, S last, ... presumably copy-pasted from min_element.) It'll also be a very good idea to make sure we have at least one test for, like, std::ranges::min(p, p+1) (takes the min of the pointer values, not the min element of the range), and also a SFINAE test for std::ranges::min(It, Sent) where the It and Sent are of different types. If these tests already exist, awesome.

[philnik]

• Rebased
• Address comments

[• Quuxplusone]

libcxx/include/__algorithm/ranges_min.h

51–52

(1) I was going to comment "Is it safe to call ranges::begin twice on an arbitrary range?" (I think not). But then noticed that this is just an initializer_list. Please s/__r/__il/g as a matter of naming.
Then, I also strongly recommend replacing ranges::begin/end with __il.begin/end(); but if this is because we're following the Standard's wording exactly, then it's OK to disregard me here.

(2) Depending on how https://reviews.llvm.org/D121248#inline-1160030 is resolved, this may need to become ranges::__min_element_impl(...). @ldionne, PTAL at my argument over there; WDYT?

[philnik]

• Rebased
• Address comments

[Mordante]

The code looks good, but it seems we lack a bit of test coverage.

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp

93

I miss tests to compare the Complexity Complexity: Exactly one comparison and two applications of the projection, if any.

94

I miss a test for two equivalent values. Returns: The smaller value. Returns the first argument when the arguments are equivalent.
We need to test the first argument is returned.

148

Please add a test with multiple equivalent values:

• The first element has multiple equivalent values
• Another element has multiple equivalent values

That way we make sure we validate Returns: The smallest value in the input range. Returns a copy of the leftmost element when several elements are equivalent to the smallest.

The same for test_range

151

I like a separate test like this one, but using an input_iterator. It seems that code path is completely untested.

[philnik]

• Address comments

[Mordante]

LGTM after the CI passes.

[philnik]

• Fix CI

[var-const]

LGTM once the CI is green.

[philnik]

Rebased to poke CI

[philnik]

• Fix guard

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_min.h
   __algorithm/ranges_min_element.h
   __algorithm/ranges_swap_ranges.h
   __algorithm/remove.h
   __algorithm/remove_copy.h
   __algorithm/remove_copy_if.h
   __algorithm/remove_if.h
   __algorithm/replace.h
   __algorithm/replace_copy.h

libcxx/include/__algorithm/ranges_min.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_MIN_H
+#define _LIBCPP___ALGORITHM_RANGES_MIN_H
+
+#include <__algorithm/ranges_min_element.h>
+#include <__config>
+#include <__functional/identity.h>
+#include <__functional/ranges_operations.h>
+#include <iterator>
+
+#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
+#  pragma GCC system_header
+#endif
+
+_LIBCPP_PUSH_MACROS
+#include <__undef_macros>
+
+_LIBCPP_BEGIN_NAMESPACE_STD
+
+namespace ranges {
+namespace __min {
+struct __fn {
+  template <class _Tp, class _Proj = identity,
+            indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  const _Tp& operator()(const _Tp& __a, const _Tp& __b, _Comp __comp = {}, _Proj __proj = {}) const {
+    return __comp(__proj(__a), __proj(__b)) ? __a : __b;
+  }
+
+  template <copyable _Tp, class _Proj = identity,
+            indirect_strict_weak_order<projected<const _Tp*, _Proj>> _Comp = ranges::less>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  _Tp operator()(initializer_list<_Tp> __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return *ranges::__min_element::__fn::__go(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+
+  template <input_range _Rp, class _Proj = identity,
+            indirect_strict_weak_order<projected<iterator_t<_Rp>, _Proj>> _Comp = ranges::less>
+    requires indirectly_copyable_storable<iterator_t<_Rp>, range_value_t<_Rp>*>
+  _LIBCPP_HIDE_FROM_ABI constexpr
+  range_value_t<_Rp> operator()(_Rp&& __r, _Comp __comp = {}, _Proj __proj = {}) const {
+    return *ranges::__min_element::__fn::__go(ranges::begin(__r), ranges::end(__r), __comp, __proj);
+  }
+};
+} // namespace __min
+
+inline namespace __cpo {
+  inline constexpr auto min = __min::__fn{};
+} // namespace __cpo
+} // namespace ranges
+
+_LIBCPP_END_NAMESPACE_STD
+
+_LIBCPP_POP_MACROS
+
+#endif // _LIBCPP___ALGORITHM_RANGES_MIN_H

libcxx/include/algorithm

namespace ranges {
   template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
     indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>             // since C++20
   constexpr I min_element(I first, S last, Comp comp = {}, Proj proj = {});
 
   template<forward_range R, class Proj = identity,
     indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less> // since C++20
   constexpr borrowed_iterator_t<R> min_element(R&& r, Comp comp = {}, Proj proj = {});
 }
 
 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);
 
 template <class InputIterator, class Function>
     constexpr Function          // constexpr in C++20

 #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_min.h>
 #include <__algorithm/ranges_min_element.h>
 #include <__algorithm/ranges_swap_ranges.h>
 #include <__algorithm/remove.h>
 #include <__algorithm/remove_copy.h>
 #include <__algorithm/remove_copy_if.h>
 #include <__algorithm/remove_if.h>
 #include <__algorithm/replace.h>
 #include <__algorithm/replace_copy.h>

libcxx/test/libcxx/diagnostics/detail.headers/algorithm/ranges_min.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_min.h'}}
+#include <__algorithm/ranges_min.h>

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.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-no-concepts
+// UNSUPPORTED: libcpp-has-no-incomplete-ranges
+
+//  template<forward_iterator I, sentinel_for<I> S, class Proj = identity,
+//    indirect_strict_weak_order<projected<I, Proj>> Comp = ranges::less>
+//  constexpr I ranges::min(I first, S last, Comp comp = {}, Proj proj = {});
+//
+//  template<forward_range R, class Proj = identity,
+//    indirect_strict_weak_order<projected<iterator_t<R>, Proj>> Comp = ranges::less>
+//  constexpr borrowed_iterator_t<R> ranges::min(R&& r, Comp comp = {}, Proj proj = {});
+
+#include <algorithm>
+#include <array>
+#include <cassert>
+#include <random>
+#include <ranges>
+
+#include "test_macros.h"
+#include "test_iterators.h"
+
+template <class T>
+concept HasMin = requires (T t) { std::ranges::min(t); };
+
+struct NoLessThanOp {};
+struct NotTotallyOrdered {
+  int i;
+  bool operator<(const NotTotallyOrdered& o) const { return i < o.i; }
+};
+
+static_assert(HasMin<std::initializer_list<int>>);
+static_assert(!HasMin<int>);
+static_assert(!HasMin<NoLessThanOp>);
+static_assert(!HasMin<NotTotallyOrdered>);
+
+constexpr void test_2_arguments() {
+  assert(std::ranges::min(1, 2) == 1);
+  assert(std::ranges::min(2, 1) == 1);
+  // test comparator
+  assert(std::ranges::min(1, 2, std::ranges::greater{}) == 2);
+  // test projection
+  assert(std::ranges::min(1, 2, std::ranges::less{}, [](int i){ return i == 1 ? 10 : i; }) == 2);
+}
+
+constexpr void test_initializer_list() {
+  { // test projection
+    int ret = std::ranges::min({7, 6, 9, 3, 5, 1, 2, 4}, std::ranges::less{}, [](int i) { return i == 5 ? -100 : i; });
+    assert(ret == 5);
+  }
+  { // test comparator
+    int ret = std::ranges::min({7, 6, 9, 3, 5, 1, 2, 4}, std::ranges::greater{});
+    assert(ret == 9);
+  }
+  {
+    int compares = 0;
+    int projections = 0;
+    auto comparator = [&](int a, int b) {
+      ++compares;
+      return a < b;
+    };
+    auto projection = [&](int a) {
+      ++projections;
+      return a;
+    };
+    [[maybe_unused]] std::same_as<int> auto ret = std::ranges::min({1, 2, 3}, comparator, projection);
+    assert(compares == 2);
+    assert(projections == 4);
+  }
+}
+
+constexpr void test_range() {
+  int a[] = {7, 6, 9, 3, 5, 1, 2, 4};
+  { // test projection
+    int ret = std::ranges::min(a, std::ranges::less{}, [](int i) { return i == 5 ? -100 : i; });
+    assert(ret == 5);
+  }
+  { // test comparator
+    int ret = std::ranges::min(a, std::ranges::greater{});
+    assert(ret == 9);
+  }
+  {
+    int compares = 0;
+    int projections = 0;
+    auto comparator = [&](int a, int b) {
+      ++compares;
+      return a < b;
+    };
+    auto projection = [&](int a) {
+      ++projections;
+      return a;
+    };
+    [[maybe_unused]] std::same_as<int> auto ret = std::ranges::min(std::array{1, 2, 3}, comparator, projection);
+    assert(compares == 2);
+    assert(projections == 4);
+  }
+  { // test borrowed range
+    int ret = std::ranges::min(std::views::all(a));
+    assert(ret == 1);
+  }
+}
+
+constexpr bool test() {
+  test_2_arguments();
+  test_initializer_list();
+  test_range();
+
+  return true;
+}
+
+int main(int, char**) {
+  test();
+  static_assert(test());
+
+  return 0;
+}