Page MenuHomePhabricator

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

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


Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes

Actually rebase

philnik updated this revision to Diff 410406.Feb 21 2022, 3:27 PM
  • Fix GCC
Quuxplusone added inline comments.
__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. Can anyone else reproduce it?
(also attn @jwakely in case he has any ideas)

jwakely added inline comments.Feb 23 2022, 8:30 AM

Looks like a similar problem to (and its dup) which we decided was a problem with using a deduced return type in the library code, not a compiler bug.


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

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?


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?


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?


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?


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


The initializer_list overload also seems to be missing from here.


Nit: <random> seems unused?


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


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


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


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

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


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

Quuxplusone added inline comments.Mar 9 2022, 8:11 AM

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


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.


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


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


  // 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

According to 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

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)?


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


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

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

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


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


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.


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


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.