Page MenuHomePhabricator
Differential D102809 Diff 351877 libcxx/include/__iterator/iter_swap.h

Changeset View

Standalone View

View Options

libcxx/include/__iterator/iter_swap.h

  • This file was added.
// -*- C++ -*-
//===----------------------------------------------------------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
#ifndef _LIBCPP___ITERATOR_ITER_SWAP_H
#define _LIBCPP___ITERATOR_ITER_SWAP_H
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

s/SWAP/ITER_SWAP/g

Quuxplusone: `s/SWAP/ITER_SWAP/g`
#include <__config>
#include <__iterator/concepts.h>
#include <__iterator/iterator_traits.h>
#include <__ranges/access.h>
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

alphabetize plz

Quuxplusone: alphabetize plz
#include <type_traits>
#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
#pragma GCC system_header
#endif
_LIBCPP_PUSH_MACROS
#include <__undef_macros>
_LIBCPP_BEGIN_NAMESPACE_STD
#if !defined(_LIBCPP_HAS_NO_RANGES)
namespace ranges {
namespace __iter_swap {
template<class _I1, class _I2>
void iter_swap(_I1, _I2) = delete;
template<class _T1, class _T2>
concept __unqualified_iter_swap = requires(_T1&& __x, _T2&& __y) {
iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
};
template<class _T1, class _T2>
concept __readable_swappable =
indirectly_readable<_T1> && indirectly_readable<_T2> &&
swappable_with<decltype(*declval<_T1>()), decltype(*declval<_T2>())>;
ldionneUnsubmitted
Done
ReplyInline Actions

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.

ldionne: I think it would be more in-line with what we usually do to say…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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.

zoecarver: Hmm, trying to come up with an example where this doesn't work. I think it's actually 100%…
cjdbUnsubmitted
Done
ReplyInline Actions
iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
};
template<class _T1, class _T2>
- concept __readable_swappable =
- indirectly_readable<_T1> && indirectly_readable<_T2> &&
+ concept __iter_reference_swappable_with =
+ !__unqualified_iter_swap<_T1, _T2> &&
+ indirectly_readable<_T1> &&
+ indirectly_readable<_T2> &&
swappable_with<decltype(*declval<_T1>()), decltype(*declval<_T2>())>;
template<class _T1, class _T2>
cjdb:
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: In other PRs I've been asked to put the `!__unqualified_iter_swap` part in the requires clause.
struct __fn {
template <class _T1, class _T2>
requires __unqualified_iter_swap<_T1, _T2>
constexpr void operator()(_T1&& __x, _T2&& __y) const
noexcept(noexcept(iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y))))
{
(void)iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
}
template <class _T1, class _T2>
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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.

Quuxplusone: Do we have any sense of whether the Standard intends this unqualified `iter_move` to refer to…
tcanensUnsubmitted
Done
ReplyInline Actions

This is definitely ranges::iter_move.

tcanens: This is definitely `ranges::iter_move`.
requires (!__unqualified_iter_swap<_T1, _T2>) &&
__readable_swappable<_T1, _T2>
constexpr void operator()(_T1&& __x, _T2&& __y) const
noexcept(noexcept(ranges::swap(*_VSTD::forward<_T1>(__x), *_VSTD::forward<_T2>(__y))))
cjdbUnsubmitted
Done
ReplyInline Actions
struct __fn {
- template <class _T1, class _T2>
- requires __unqualified_iter_swap<_T1, _T2>
+ template <class _T1, __unqualified_iter_swap<_T1> _T2>
constexpr void operator()(_T1&& __x, _T2&& __y) const
cjdb:
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: This is a bit more confusing imho. If you feel strongly I'll change it, though.
ldionneUnsubmitted
Done
ReplyInline Actions

Agreed, I would definitely keep as-is.

ldionne: Agreed, I would definitely keep as-is.
cjdbUnsubmitted
Done
ReplyInline Actions

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

cjdb: FYI: we're going to be doing this in a lot of algorithms, and it's definitely part of the…
{
ranges::swap(*_VSTD::forward<_T1>(__x), *_VSTD::forward<_T2>(__y));
}
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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.

Quuxplusone: Here and line 80, I suggest removing the cast to `(void)`. IIUC, the reason it's there in https…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: I'm slightly against removing the void cast, basically to make sure a case like…
tcanensUnsubmitted
Done
ReplyInline Actions

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

tcanens: nodiscard has zero normative effect, so it can't affect the well-formedness of anything.
cjdbUnsubmitted
Done
ReplyInline Actions

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.

cjdb: I would prefer it if `ranges::iter_swap` didn't randomly cause people to want to enable `-Wno…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: > I would prefer it if ranges::iter_swap didn't randomly cause people to want to enable -Wno…
template <class _T1, class _T2>
requires (!__unqualified_iter_swap<_T1, _T2> &&
!__readable_swappable<_T1, _T2>) &&
indirectly_movable_storable<_T1, _T2> &&
indirectly_movable_storable<_T2, _T1>
cjdbUnsubmitted
Done
ReplyInline Actions
(void)iter_swap(_VSTD::forward<_T1>(__x), _VSTD::forward<_T2>(__y));
}
- template <class _T1, class _T2>
- requires (!__unqualified_iter_swap<_T1, _T2>) &&
- __readable_swappable<_T1, _T2>
+ template <class _T1, __iter_reference_swappable_with<_T1> _T2>
constexpr void operator()(_T1&& __x, _T2&& __y) const

I'll leave the last overload as an exercise.

cjdb: I'll leave the last overload as an exercise.
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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.

zoecarver: When I've done this in other places, I've been asked to change it to use `requires`, and in…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: I'm going to leave this and mark it as resolved.
constexpr void operator()(_T1&& __x, _T2&& __y) const
noexcept(noexcept(iter_value_t<_T2>(ranges::iter_move(__y))) &&
noexcept(*__y = ranges::iter_move(__x)) &&
noexcept(*_VSTD::forward<_T1>(__x) = declval<iter_value_t<_T2>>()))
ldionneUnsubmitted
Done
ReplyInline Actions

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

ldionne: I don't see how to do better, but it's awful to have to duplicate the body like that.
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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: I agree. We should really have a `noexcept(auto)`. This wouldn't be too hard to add to clang…
ldionneUnsubmitted
Done
ReplyInline Actions

If only that's how things worked 😅

ldionne: If only that's how things worked 😅
{
iter_value_t<_T2> __old(ranges::iter_move(__y));
*__y = ranges::iter_move(__x);
*_VSTD::forward<_T1>(__x) = _VSTD::move(__old);
}
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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

Quuxplusone: Just `*_VSTD::forward<_T1>(__x) = _VSTD::move(__old);` — no need to cast to `void` here.
};
} // end namespace __iter_swap
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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.

Quuxplusone: This should say `indirectly_movable_storable<_T1&&, _T2&&>`, right? because the type of `E1` is…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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.

zoecarver: This is my bad for naming these `_T1` and `_T2` so when I read the standard wording, my brain…
tcanensUnsubmitted
Done
ReplyInline Actions

The type of an expression is never a reference type.

tcanens: The type of an expression is never a reference type.
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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.

Quuxplusone: > The type of an expression is never a reference type. So all of these trait checks should be…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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?

zoecarver: > So all of these trait checks should be using e.g.
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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

Quuxplusone: @tcanens said "the type of an expression is never a reference type," so no, you'd have to…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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: I'm not sure I have the correct words to describe what I'm thinking here but won't the `&&` in…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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?

zoecarver: > I'm not sure I have the correct words to describe what I'm thinking here but won't the && in…
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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.

Quuxplusone: No; reference collapsing means that when `T` is `int&`, `T&&` is `int&` (not `int&&`). However…
inline namespace __cpo {
tcanensUnsubmitted
Done
ReplyInline Actions

This is missing the assignment,

tcanens: This is missing the assignment,
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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.

zoecarver: You're right. I thought `__iter_exchange_move` would take care of this, but it only checks one…
inline constexpr auto iter_swap = __iter_swap::__fn{};
} // namespace __cpo
QuuxplusoneUnsubmitted
Done
ReplyInline Actions

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

Quuxplusone: Here, `__iter_exchange_move` needs to be ADL-proofed — but actually, I strongly suggest that…
zoecarverAuthorUnsubmitted
Done
ReplyInline Actions

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

zoecarver: That's not a bad idea, I have to add a move for `__old`, but I think that's alright.
} // namespace ranges
#endif // !defined(_LIBCPP_HAS_NO_RANGES)
_LIBCPP_END_NAMESPACE_STD
_LIBCPP_POP_MACROS
#endif // _LIBCPP___ITERATOR_ITER_SWAP_H