Page MenuHomePhabricator

[libcxx][ranges] Add `ranges::iter_swap`.
ClosedPublic

Authored by zoecarver on May 19 2021, 2:03 PM.

Details

Reviewers
cjdb
ldionne
Quuxplusone
Group Reviewers
Restricted Project
Commits
rG40d6d2c49dd1: [libcxx][ranges] Add `ranges::iter_swap`.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
zoecarver added inline comments.May 19 2021, 4:55 PM
libcxx/include/__iterator/iter_swap.h
61

I'm slightly against removing the void cast, basically to make sure a case like ensureVoidCast works below.

76–77

This is my bad for naming these _T1 and _T2 so when I read the standard wording, my brain thought it meant to just use the template params (which don't exist in the wording). I think you're right.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
156

Hmm, I see what you're saying with L155 specifically. And we probably don't really need this test (or maybe a better test would be arr[0].moves() + arr[1].moves() == 3.

Ditto throughout.

Where else do you see this?

tcanens added inline comments.May 19 2021, 5:04 PM
libcxx/include/__iterator/iter_swap.h
45–53

This is definitely ranges::iter_move.

61

nodiscard has zero normative effect, so it can't affect the well-formedness of anything.

76–77

The type of an expression is never a reference type.

79

This is missing the assignment,

Quuxplusone added inline comments.May 19 2021, 5:25 PM
libcxx/include/__iterator/iter_swap.h
76–77

The type of an expression is never a reference type.

So all of these trait checks should be using e.g. indirectly_movable_storable<remove_reference_t<_T1>, remove_reference_t<_T2>>? Blech. OK.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
156

At least lines 159, 162, 165, 168, 171, 174, 177.

cjdb requested changes to this revision.May 19 2021, 5:49 PM

Some initial feedback, will give the tests a more in-depth review in a day or so.

libcxx/include/__iterator/iter_swap.h
40–43
56–57
61

I would prefer it if ranges::iter_swap didn't randomly cause people to want to enable -Wno-unused-result. Let's keep the cast to void.

64–66

I'll leave the last overload as an exercise.

zoecarver added inline comments.May 20 2021, 9:15 AM
libcxx/include/__iterator/iter_swap.h
61

I would prefer it if ranges::iter_swap didn't randomly cause people to want to enable -Wno-unused-result. Let's keep the cast to void.

+1 I'm going to leave it. (I don't see any way it hurts to have it, but I can see ways it helps.)

64–66

When I've done this in other places, I've been asked to change it to use requires, and in this case (and especially below) I think it might be clearer than trying to fit it into the template.

76–77

So all of these trait checks should be using e.g. indirectly_movable_storable<remove_reference_t<_T1>, remove_reference_t<_T2>>? Blech. OK.

I think they can actually just be _T1 and _T2 (no remove_reference_t), right?

79

You're right. I thought __iter_exchange_move would take care of this, but it only checks one of the assignment operators, not the other.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
156

At least lines 159, 162, 165, 168, 171, 174, 177.

These are just checking that the values of the array buff are swapped. I think this is exactly what we want to be checking.

Quuxplusone added inline comments.May 20 2021, 11:41 AM
libcxx/include/__iterator/iter_swap.h
76–77

@tcanens said "the type of an expression is never a reference type," so no, you'd have to remove the reference first (e.g. if _T1 is int&, then we should apply the trait to int, not to int&).

zoecarver added inline comments.May 20 2021, 12:02 PM
libcxx/include/__iterator/iter_swap.h
76–77

I'm not sure I have the correct words to describe what I'm thinking here but won't the && in _T1&& "eat" the reference part of the reference type?

zoecarver marked 15 inline comments as done.Jun 4 2021, 3:26 PM
zoecarver added inline comments.
libcxx/include/__iterator/iter_swap.h
40–43

In other PRs I've been asked to put the !__unqualified_iter_swap part in the requires clause. I also like this better because then the concept is more composable (rather than only being useful in one place).

56–57

This is a bit more confusing imho. If you feel strongly I'll change it, though.

64–66

I'm going to leave this and mark it as resolved.

76–77

I'm not sure I have the correct words to describe what I'm thinking here but won't the && in _T1&& "eat" the reference part of the reference type?

@Quuxplusone ping, does this make any sense?

81

That's not a bad idea, I have to add a move for __old, but I think that's alright.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
38–42

Updated to have something similar to this. Let me know what you think.

For the record: this isn't really meant to test that we use the correct overload, though. I was just testing that it calls "the overload" it didn't really cross my mind that there would be any way for us to even call the bool& overload with an argument of type HasIterSwap. Anyway, I think it is a good idea to not have this just behave like an assignment operator or default swap impl.

85

Interesting, OK, thanks for explaining.

zoecarver marked 5 inline comments as done.Jun 4 2021, 3:27 PM
zoecarver updated this revision to Diff 349980.Jun 4 2021, 3:27 PM

Update based on review.

Quuxplusone resigned from this revision.Jun 4 2021, 7:01 PM

I'm unlikely to have any further comments on this, but also don't think I should count as "accepting" it, since I've mainly done superficial stuff and @tcanens had some pretty significant standardese issues (which have probably been dealt with now but I'm not claiming I'm sure of that). I'll let someone-else be the final approver.

libcxx/include/__iterator/iter_swap.h
75

Just *_VSTD::forward<_T1>(__x) = _VSTD::move(__old); — no need to cast to void here.

76–77

No; reference collapsing means that when T is int&, T&& is int& (not int&&).
However, at least for iter_value_t, the concept itself will strip cvref-qualifiers:
https://godbolt.org/z/aEEoen53P
and then for indirectly_movable_storable, I think it'd be difficult (and presumably library-UB, even if it were possible) to come up with a type where indirectly_movable_storable<T> was true and indirectly_movable_storable<T&> was false, or vice versa.
So I suppose no immediate action is needed here; let's just see if anyone files a bug.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
143

This is the only place you test std::ranges::iter_swap(lvalue, lvalue). Please expand the tests below to test them also with lvalues of type HasRangesSwapWrapper, A*, etc., at least enough to hit each different overload of iter_swap once with at least one lvalue.

You never test std::ranges::iter_swap(lvalue, rvalue) or std::ranges::iter_swap(rvalue, lvalue), but I don't think those need testing, as long as you hit the (lvalue, lvalue) cases.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/unqualified_lookup_wrapper.h
70–71
move_tracker(const move_tracker&) = delete;
move_tracker& operator=(const move_tracker&) = delete;

(Deleted functions don't need constexpr.)

75

moves() still doesn't need noexcept.

zoecarver marked 11 inline comments as done.Jun 14 2021, 8:00 AM

@ldionne this is ready for review.

@cjdb this is ready for re-review.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
143

OK. Added a few more lvalue tests to cover the remaining two overloads.

libcxx/test/std/iterators/iterator.requirements/iterator.cust/unqualified_lookup_wrapper.h
75

I think it makes sense to leave the constexpr in this case. This is a sort of general utility.

zoecarver updated this revision to Diff 351877.Jun 14 2021, 8:01 AM
zoecarver marked 2 inline comments as done.

Apply Arthur's suggested changes.

Rebase.

ldionne requested changes to this revision.Jun 14 2021, 2:35 PM
ldionne added inline comments.
libcxx/include/__iterator/iter_swap.h
43

I think it would be more in-line with what we usually do to say swappable_with<iter_reference_t<_T1>, iter_reference_t<_T2>> instead. WDYT?

As written, I think this is slightly incorrect (but I'm not sure it's possible to notice the difference). The Standard talks about the "reference type of E1 and E2", which is *declval<_T1&&>(), not *declval<_T1>(). But regardless, I think we can just switch to iter_reference_t<_T1> unless there's a problem with that I'm not seeing.

56–57

Agreed, I would definitely keep as-is.

69–71

I don't see how to do better, but it's awful to have to duplicate the body like that.

This revision now requires changes to proceed.Jun 14 2021, 2:35 PM
zoecarver added inline comments.Jun 15 2021, 6:19 AM
libcxx/include/__iterator/iter_swap.h
43

Hmm, trying to come up with an example where this doesn't work. I think it's actually 100% valid because indirectly_readable enforces that *in == iter_reference_t:

{ *in } -> std::same_as<std::iter_reference_t<In>>;

So, I'll do that.

69–71

I agree. We should really have a noexcept(auto). This wouldn't be too hard to add to clang, and then we could just let GCC users have worse codegen...

zoecarver updated this revision to Diff 352119.Jun 15 2021, 6:27 AM

Rebase. Apply Louis' comments.

zoecarver marked an inline comment as done.Jun 15 2021, 6:27 AM
ldionne accepted this revision.Jun 16 2021, 1:24 PM

LGTM with my comments applied.

libcxx/include/__iterator/iter_swap.h
69–71

If only that's how things worked 😅

libcxx/test/std/iterators/iterator.requirements/iterator.cust/iterator.cust.swap.pass.cpp
27

Based on http://eel.is/c++draft/customization.point.object#2, I would just do std::semiregular<std::remove_cv_t<IterSwapT>>.

139

Minor thing: I like to split test different test cases by enclosing them in a different scope. It makes it easier to see that they are different test cases and that they don't share anything between themselves. So I'd do:

{
    int value1 = 0;
    int value2 = 0;
    HasIterSwap a(value1), b(value2);
    std::ranges::iter_swap(a, b);
    assert(value1 == 1 && value2 == 1);
}
{
    int value1 = 0;
    int value2 = 0;
    HasRangesSwap c(value1), d(value2);
    HasRangesSwapWrapper cWrapper(c), dWrapper(d);
    std::ranges::iter_swap(cWrapper, dWrapper);
    assert(value1 == 1 && value2 == 1);
}

// etc...

(and CI passing once you rebase)

cjdb added a comment.Jun 17 2021, 10:22 AM

I'll properly review this tonight, but I don't suspect I'll have much more to add now.

libcxx/include/__iterator/iter_swap.h
56–57

FYI: we're going to be doing this in a lot of algorithms, and it's definitely part of the design of concepts.

zoecarver updated this revision to Diff 353404.Jun 21 2021, 9:56 AM
zoecarver marked 3 inline comments as done.

Fix based on Louis' review comments.

Rebase off main.

This now includes two commits. That's intentional so the CI passes (for some reaosn it was failing to apply the patch before).

zoecarver updated this revision to Diff 353514.Jun 21 2021, 4:31 PM

Add a modulemap entry.

cjdb accepted this revision.Jun 21 2021, 4:41 PM
This revision is now accepted and ready to land.Jun 21 2021, 4:41 PM
zoecarver updated this revision to Diff 353662.Jun 22 2021, 8:43 AM

Remove shadowing for GCC.

This revision was landed with ongoing or failed builds.Jun 22 2021, 9:53 AM
This revision was automatically updated to reflect the committed changes.