This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by philnik on Feb 11 2022, 1:24 PM.

Details

Diff Detail

Event Timeline

philnik created this revision.Feb 11 2022, 1:24 PM
philnik requested review of this revision.Feb 11 2022, 1:24 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 11 2022, 1:24 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone requested changes to this revision.Feb 11 2022, 2:29 PM
Quuxplusone added a subscriber: ldionne.

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
17

Granularize?

35

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.

42

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
44–45

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
53

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

76

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.

85

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.

103

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

107

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.

This revision now requires changes to proceed.Feb 11 2022, 2:29 PM
philnik updated this revision to Diff 408378.Feb 14 2022, 4:50 AM
philnik marked 8 inline comments as done.
  • Address comments

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 updated this revision to Diff 408505.Feb 14 2022, 10:45 AM
  • Address comments
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp
44–45

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?

76

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

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

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.

76

At least clang is happy with concept decltype(auto)

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

philnik updated this revision to Diff 410388.Feb 21 2022, 2:26 PM
philnik marked 2 inline comments as done.
  • Rebased
  • Fix CI
  • Address comment
philnik updated this revision to Diff 410391.Feb 21 2022, 2:38 PM

Actually rebase

philnik updated this revision to Diff 410406.Feb 21 2022, 3:27 PM
  • Fix GCC
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.min.pass.cpp
80
__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 added inline comments.Feb 23 2022, 8:30 AM
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.

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 updated this revision to Diff 411703.Feb 27 2022, 2:47 PM

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

philnik updated this revision to Diff 413293.Mar 6 2022, 4:14 AM
  • Add input range test
Herald added a project: Restricted Project. · View Herald TranscriptMar 6 2022, 4:14 AM
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 updated this revision to Diff 413770.Mar 8 2022, 5:12 AM
  • Rebased
  • Add synopsis
philnik updated this revision to Diff 413771.Mar 8 2022, 5:13 AM
  • Remove XFAIL
philnik marked 4 inline comments as done.Mar 8 2022, 3:59 PM

@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.

var-const requested changes to this revision.Mar 8 2022, 5:00 PM
This revision now requires changes to proceed.Mar 8 2022, 5:00 PM
philnik updated this revision to Diff 414050.Mar 9 2022, 2:47 AM
philnik marked 10 inline comments as done.
  • 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 added inline comments.Mar 9 2022, 8:11 AM
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 updated this revision to Diff 414122.Mar 9 2022, 9:14 AM
philnik marked 3 inline comments as done.
  • Address comments
libcxx/include/__algorithm/ranges_min.h
67

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

philnik updated this revision to Diff 414128.Mar 9 2022, 9:27 AM
  • Add else branch
var-const added inline comments.Mar 9 2022, 11:34 AM
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 added inline comments.Mar 9 2022, 3:31 PM
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 updated this revision to Diff 414439.Mar 10 2022, 11:11 AM
philnik marked 3 inline comments as done.
  • Rebased
  • Address comments
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 updated this revision to Diff 414774.Mar 11 2022, 5:01 PM
philnik marked 2 inline comments as done.
  • Rebased
  • Address comments

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 updated this revision to Diff 415816.Mar 16 2022, 7:07 AM
philnik marked 4 inline comments as done.
  • Address comments
Mordante accepted this revision as: Mordante.Mar 16 2022, 10:16 AM

LGTM after the CI passes.

var-const accepted this revision.Mar 17 2022, 6:16 PM

LGTM once the CI is green.

philnik updated this revision to Diff 416370.Mar 17 2022, 6:22 PM

Rebased to poke CI

philnik updated this revision to Diff 416373.Mar 17 2022, 6:57 PM
  • Fix guard
This revision was not accepted when it landed; it landed in state Needs Review.Mar 18 2022, 4:52 AM
This revision was automatically updated to reflect the committed changes.