This is an archive of the discontinued LLVM Phabricator instance.

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

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

Details

Diff Detail

Event Timeline

zoecarver created this revision.May 19 2021, 2:03 PM
zoecarver requested review of this revision.May 19 2021, 2:03 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2021, 2:03 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone requested changes to this revision.May 19 2021, 3:19 PM
Quuxplusone added a subscriber: tcanens.
Quuxplusone added inline comments.
libcxx/include/__iterator/iter_swap.h
10–11

s/SWAP/ITER_SWAP/g

14–15

alphabetize plz

45–53

Do we have any sense of whether the Standard intends this unqualified iter_move to refer to std::ranges::iter_move (which is what it currently refers to in this PR, IIUC) or to an ADL iter_move (which is what would make more sense IMHO IIUC)?
If it is intended to refer to std::ranges::iter_move, then please (for the love of god) replace iter_move with ranges::iter_move throughout.
If it is intended to be an ADL iter_move, then... yuck, but let's figure something out.

61

Here and line 80, I suggest removing the cast to (void). IIUC, the reason it's there in https://eel.is/c++draft/iterator.cust.swap#4.1 is to make the "expression-equivalent-to" part work out to the correct type.
However, it does occur to me that a cast to (void) is technically not a no-op, because it affects the well-formedness of the expression when iter_swap has been marked [[nodiscard]] (and a user's ADL iter_swap might be marked [[nodiscard]] for all we know).
I'd be interested in @tcanens' take on whether the (void) cast is indispensable.

76–77

This should say indirectly_movable_storable<_T1&&, _T2&&>, right? because the type of E1 is not _T1 but rather _T1&&?
Can you find a test case that demonstrates the difference, and add it as a regression test?
This comment probably applies equally to all your uses of exposition-only helpers such as __readable_swappable, but I'm even less confident that that difference will be detectable by a test.

81

Here, __iter_exchange_move needs to be ADL-proofed — but actually, I strongly suggest that you just inline its body right here (and inline its noexcept-specification on line 78). Yes I know the Standard factors it out; but it's used only once and the factoring-out doesn't seem to do anything but make the code longer (both in the Standard and in libc++).

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

Has this been done in other tests already? If I'd seen it, I'd say why are you adding the &.
I would make IterSwapT an alias for decltype(std::ranges::iter_swap), and then I would check both std::invocable_v<IterSwapT, blah> and a few std::invocable_v<IterSwapT&, blah> and std::invocable_v<IterSwapT&&, blah>. (Remember reference-collapsing means that with your current definition, all three of IterSwapT{,&,&&} are equivalent to IterSwapT&, and that strikes me as less-useful-than-it-could-be.)

31

nit: explicit plz

33
38–42

Here and line 54: I'm worried that your implementation of this function is unnecessary and/or indistinguishable from the default ranges::swap, which means you're not actually testing that it's called. How about replacing these implementations with

friend constexpr void iter_swap(HasIterSwap& a, HasIterSwap& b) {
    called1 = true;
}
friend constexpr void iter_swap(HasIterSwap& a, bool& b) {
    called2 = true;
}

and then writing tests that assert(called1 && !called2) (or whatever you expect to happen).
For constexpr-friendliness, you'll probably need to make your constructor explicit HasIterSwap(bool& c1, bool& c2) : called1(c1), called2(c2) {}. Slack me if this doesn't make sense.

85

Yes — ranges::iter_swap(++i, ++j) is supposed to increment i only once, not twice.
But this is physically obvious. The Standard needs to mention it because the Standard is pretending that these are expressions-not-function-calls. We don't have to test it; you can remove this TODO.

156

It seems like this is testing the order in which std::swap performs its moves — is that right? If so, I don't think it belongs in libcxx/test/std/ at all. Ditto throughout.

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

int moves() const { return moves_; } :)

This revision now requires changes to proceed.May 19 2021, 3:19 PM
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,

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.

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
74

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
142

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
142

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.