This is an archive of the discontinued LLVM Phabricator instance.

[libc++] `<algorithm>`: `ranges::minmax` should dereference iterators only once
ClosedPublic

Authored by fsb4000 on Jan 29 2023, 9:15 PM.

Details

Summary

In https://reviews.llvm.org/D135248 libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp failed because move_iterator became random_access_iterator and ranges::minmax now chooses this branch.
We can't do *__result.first twice because move_iterator will move the value after the first dereference.

This is basically the same bug as I found in MS STL two days ago: https://github.com/microsoft/STL/pull/3366

Diff Detail

Event Timeline

fsb4000 created this revision.Jan 29 2023, 9:15 PM
Herald added a project: Restricted Project. · View Herald TranscriptJan 29 2023, 9:15 PM
fsb4000 requested review of this revision.Jan 29 2023, 9:15 PM
Herald added a reviewer: Restricted Project. · View Herald TranscriptJan 29 2023, 9:15 PM
fsb4000 edited the summary of this revision. (Show Details)Jan 29 2023, 9:20 PM
philnik requested changes to this revision.Jan 30 2023, 1:14 AM
philnik added a subscriber: philnik.
philnik added inline comments.
libcxx/include/__algorithm/ranges_minmax.h
93

IMO we should special-case the one element case here instead. In no other case will the first and second iterator point to the same element.

94

You have to add a regression test for this.

This revision now requires changes to proceed.Jan 30 2023, 1:14 AM
fsb4000 updated this revision to Diff 493778.Jan 31 2023, 4:49 PM

@philnik

You have to add a regression test for this.

We have a test for this.

{
    // check that the range_access iterator isn't moved from multiple times
    std::shared_ptr<int> a[] = { std::make_shared<int>(42) };
    auto range = std::ranges::subrange(std::move_iterator(a), std::move_iterator(a + 1));
    auto [min, max] = std::ranges::minmax(range);
    assert(a[0] == nullptr);
    assert(min != nullptr);
    assert(max == min);
  }

after std::move_iterator will become a range access iterator. But I've added a test for input_move_iterator not to lose testing the else branch in the algorithm range::minmax.

IMO we should special-case the one element case here instead.

Maybe I misunderstood but we not always can call ranges::size to find out that range size is one but we always can check equality iterators...

fsb4000 marked 2 inline comments as done.Jan 31 2023, 4:58 PM
fsb4000 updated this revision to Diff 493819.Jan 31 2023, 9:14 PM

Remove an unneeded move.

fsb4000 updated this revision to Diff 493820.Jan 31 2023, 9:20 PM

add std:::

fsb4000 edited the summary of this revision. (Show Details)Jan 31 2023, 10:16 PM
TIMEOUT: apple-libc++-backdeployment.cfg.in :: std/thread/thread.condition/notify_all_at_thread_exit_lwg3343.pass.cpp (8020 of 8020)
******************** TEST 'apple-libc++-backdeployment.cfg.in :: std/thread/thread.condition/notify_all_at_thread_exit_lwg3343.pass.cpp' FAILED

Try to rerun CI.

fsb4000 updated this revision to Diff 493884.Feb 1 2023, 2:50 AM

clang-format

fsb4000 updated this revision to Diff 494078.Feb 1 2023, 3:07 PM

rebase + change if constexpr condition

fsb4000 updated this revision to Diff 494087.Feb 1 2023, 3:26 PM

range_reference_t

fsb4000 updated this revision to Diff 494091.Feb 1 2023, 3:39 PM

clarify comment

@philnik

@CaseyCarter after review my MS PR suggested that you (@philnik) had suggested me before

How do folks feel about a different approach (https://github.com/fsb4000/STL/compare/fix2900...CaseyCarter:STL:minmax) that detects the problem case "for free" by unrolling the first loop iteration? (Bugfix aside, this feels like a cleaner implementation of minmax by avoiding codeshare with minmax_element.) (Note that the maximum and minimum element can only be the same when the range has a single element.)

I will update this patch later when we finish with the MS PR to the final version of that PR.

fsb4000 updated this revision to Diff 494820.Feb 4 2023, 6:35 AM

clang-format

fsb4000 edited the summary of this revision. (Show Details)Feb 4 2023, 6:37 AM
fsb4000 updated this revision to Diff 494824.Feb 4 2023, 7:22 AM

try to fix tests

fsb4000 updated this revision to Diff 494827.Feb 4 2023, 7:48 AM

try again

Because "The machines hosting the AIX libc++ pre-commit CI workers will be down for maintenance for a couple of hours over the weekend. We expect everything to be back online by Monday"
I think this patch is ready for review.

philnik added inline comments.Feb 7 2023, 2:27 AM
libcxx/include/__algorithm/ranges_minmax.h
142–144

These should either be static_asserts or simply not exist at all.

146

This has been asserted already, there is no need to check it twice.

148

I think this should use iter_value_t.

153

What are these static_casts for?

162

Why are you effectively re-implementing minmax_element here?

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

Couldn't you use a cpp20_input_iterator<std::move_iterator<std::string>>? That would make this test constexpr-compatible and avoid implementing another iterator.

fsb4000 updated this revision to Diff 495474.Feb 7 2023, 4:48 AM
fsb4000 marked 4 inline comments as done.

applying code review's suggestions.

fsb4000 marked an inline comment as done.Feb 7 2023, 4:52 AM
fsb4000 added inline comments.
libcxx/include/__algorithm/ranges_minmax.h
153

MS STL uses the static_casts. I used for consistency with MS STL. I asked them why the static_cast are needed and I added more static_casts here. After their answer and if the static_casts are optionally needed I could remove them.

162

To implement special-case the one element case without adding an addional if.

Ok, I try another approach.

fsb4000 updated this revision to Diff 495511.Feb 7 2023, 6:35 AM
fsb4000 marked an inline comment as done.

clang-format

fsb4000 updated this revision to Diff 495514.Feb 7 2023, 6:39 AM

fix tests

fsb4000 updated this revision to Diff 495519.Feb 7 2023, 6:49 AM

add constexpr test

fsb4000 updated this revision to Diff 495525.Feb 7 2023, 7:00 AM

I renamed the variable for consistency with other tests.

fsb4000 added inline comments.Feb 7 2023, 9:44 PM
libcxx/include/__algorithm/ranges_minmax.h
153

Casey answered me:
indirectly_copyable_storable<_It, _ValueT*> (https://eel.is/c++draft/alg.req.ind.copy#2) requires that _ValueT is copyable, but the reference type of the input range (and _It) isn't necessarily const _ValueT& so we don't have the same guarantee of implicit convertibility. In fact there's no requirement on that algorithm that lets us implicitly convert the result of an iterator dereference to _ValueT. There is a requirement that constructible_from<_ValueT, iter_reference_t<_It>> holds, however, so we can perform the conversion explicitly with static_cast.

https://github.com/microsoft/STL/pull/3384#discussion_r1099671173

fsb4000 marked an inline comment as done.Feb 9 2023, 9:33 PM
philnik added inline comments.Feb 10 2023, 8:57 AM
libcxx/include/__algorithm/ranges_minmax.h
85–86
102–103

I think this comment is more confusing than helpful TBH.

153

IMO we should add them in another patch then, since this should be checked for all algorithms (most return an iterator, so there shouldn't be many cases) and tested. Could you open an issue for this so we don't forget?

fsb4000 updated this revision to Diff 496720.Feb 11 2023, 3:31 PM
fsb4000 marked 3 inline comments as done.

I changed comments, removed static_casts, used ranges::next instead of ++

I created an issue https://github.com/llvm/llvm-project/issues/60680

libcxx/include/__algorithm/ranges_minmax.h
102–103

I changed these comments.

153

OK

fsb4000 updated this revision to Diff 496721.Feb 11 2023, 3:50 PM

added #include <__iterator/next.h>

fsb4000 updated this revision to Diff 496723.Feb 11 2023, 4:06 PM

reordered includes

fsb4000 updated this revision to Diff 496737.Feb 11 2023, 8:19 PM
philnik accepted this revision.Feb 13 2023, 8:27 AM

LGTM % test comment.

libcxx/include/__algorithm/ranges_minmax.h
102

WDYT?

libcxx/test/std/algorithms/alg.sorting/alg.min.max/ranges.minmax.pass.cpp
341–359

Could you remove this and instead use the constexpr test case with forward_iterators, so the we actually test for the bug now, instead of waiting for move_iterator to be random-access?

This revision is now accepted and ready to land.Feb 13 2023, 8:27 AM
fsb4000 updated this revision to Diff 497238.Feb 14 2023, 1:28 AM

rebased, changed the comments, changed the test

fsb4000 marked 2 inline comments as done.Feb 14 2023, 1:28 AM
fsb4000 updated this revision to Diff 497240.Feb 14 2023, 1:38 AM

clang-format

fsb4000 updated this revision to Diff 497247.Feb 14 2023, 2:12 AM
This comment was removed by fsb4000.
fsb4000 updated this revision to Diff 497252.Feb 14 2023, 2:21 AM
philnik accepted this revision.Feb 14 2023, 2:32 PM
This revision was landed with ongoing or failed builds.Feb 14 2023, 3:03 PM
This revision was automatically updated to reflect the committed changes.