Page MenuHomePhabricator

[libc++][ranges] Implement std::ranges::swap_ranges()
ClosedPublic

Authored by philnik on Dec 27 2021, 4:08 AM.

Details

Summary

Implement std::ranges::swap_ranges()

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Quuxplusone added inline comments.Jan 3 2022, 8:58 AM
libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp
46 ↗(On Diff #396976)
48 ↗(On Diff #396976)

Utter nit, but let's make this a + 10 in both cases, since this signifies an "end" iterator. :)

philnik updated this revision to Diff 398118.Jan 7 2022, 6:01 AM
philnik marked 5 inline comments as done.
  • rebased
  • Addressed comments and renamed some stuff
philnik updated this revision to Diff 398119.Jan 7 2022, 6:06 AM
  • Added module tests
philnik updated this revision to Diff 398121.Jan 7 2022, 6:11 AM
  • Removed 0-length whitespaces
philnik updated this revision to Diff 398125.Jan 7 2022, 6:16 AM
  • Removed another whitespace
philnik updated this revision to Diff 398157.Jan 7 2022, 8:18 AM
  • rebased
  • Added UNSUPPORTED comments
philnik updated this revision to Diff 399236.Jan 12 2022, 12:28 AM
  • Rebased
  • Add include
Quuxplusone added a subscriber: ldionne.

LGTM % nits!

libcxx/include/__algorithm/ranges_swap_ranges.h
26
35–36

Nit: Consider the following alternatives, either of which feels preferable to me (and the first feels the most "libc++ style":

_LIBCPP_HIDE_FROM_ABI constexpr ranges::swap_ranges_result<_I1, _I2>
operator()(_I1 __first1, _S1 __last1, _I2 __first2, _S2 __last2) const
_LIBCPP_HIDE_FROM_ABI constexpr
ranges::swap_ranges_result<_I1, _I2> operator()(_I1 __first1, _S1 __last1,
                                                _I2 __first2, _S2 __last2) const
libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
39

(ditto throughout, just to keep line lengths manageable)

53

Can we get tests here for swap_ranges(j, i) and swap_ranges(j, j+1, i, i+3) as well?

157

Here and line 158-159, please don't line-break between auto and a! Line-break after = would be a good place. Maybe using Expected = std::ranges::swap_ranges_result<...> would be useful.
Also, please std::vector<int> rather than just std::vector. (I'm unusually anti-CTAD by nature, but) let's not introduce additional complexity if we don't have to.

168

Nit: struct S {};
Or just use int on line 168 and then you don't need S.

libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp
48 ↗(On Diff #396976)

This is relevant to @ldionne's interests re that LWG (write-a-paper-not-an-)issue. @ldionne, should we start testing our niebloids in here? start a new test file? none of the above?
This might be a blocking/controversial point.

philnik updated this revision to Diff 400167.Jan 14 2022, 3:34 PM
philnik marked 6 inline comments as done.
  • Rebased
  • Addredd comments
Quuxplusone requested changes to this revision.Jan 22 2022, 8:41 AM
Quuxplusone added inline comments.
libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
85

IIUC, the special thing about borrowed input ranges is that their iterators don't dangle. So this test should be testing with std::move(b1), not just b1. And that means that it should simply be merged into test_rval_range(), something like

std::vector<int> x = {1, 2, 3};
using It = std::vector<int>::iterator;
std::same_as<std::ranges::swap_ranges_result<It, It>> auto c =
  std::ranges::swap_ranges(std::views::all(x), r);
assert(c.in1 == x.end());
assert(c.in2 == r.end());
assert((r == std::vector<int>{1, 2, 3}));
assert((x == std::vector<int>{4, 5, 6}));

where std::views::all(x) is our rvalue, borrowed, range.

Going further down this rabbit hole... Notice that both subrange and all_t (i.e. ref_view in this case) are both not only borrowed ranges, but also views. We don't have test coverage for a borrowed non-view. However, such things seem vanishingly rare? I think the trick is to make it immobile:

struct BorrowedNonView : std::view_base {
    BorrowedNonView(BorrowedNonView&&) = delete;
    int *begin() const;
    int *end() const;
};

I would say that this is not worth it (especially since swap_ranges doesn't do anything surprising w.r.t. dangling).

173

Instead of [[maybe_unused]], let's assert(a.in1 == r.end()). Likewise throughout.

179–184

The only reason this is split out is because vector isn't constexpr yet, right?
Could you see whether it's easy to use the constexpr deque from libcxx/test/support/test_constexpr_container.h instead?

libcxx/test/std/library/description/conventions/customization.point.object/cpo.compile.pass.cpp
48 ↗(On Diff #396976)

This has changed thanks to D116570; please move this diff into libcxx/test/std/library/description/conventions/customization.point.object/niebloid.compile.pass.cpp, where it will be a one-line diff.

Actually, now I feel a little guilty for not adding all the iterator-sentinel signatures into niebloid.compile.pass.cpp. I think my original logic was that basically all we were catching with that test was if you did something bizarre with the implementation of the object itself, or if you forgot the const on operator() — but the former doesn't require testing more than one signature, and the latter should be caught immediately by ordinary testing because the object itself is constexpr.

This revision now requires changes to proceed.Jan 22 2022, 8:41 AM
philnik updated this revision to Diff 402830.Jan 25 2022, 3:30 AM
philnik marked 4 inline comments as done.
  • Rebased
  • Address comments
libcxx/include/__algorithm/ranges_swap_ranges.h
33–36

Ditto below.

42

I believe you're missing _VSTD::move on both operands, which means there's some test coverage missing. Please investigate and add regression tests involving cpp20_input_iterator.

libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
85

On the ranges::mismatch review you pointed out that views::all(x) i.e. ref_view is not a borrowed range, and it looks like you're right w.r.t. libc++, but that seems to be a libc++ bug.
https://en.cppreference.com/w/cpp/ranges/borrowed_range
I'll fix it, and then views::all(x) should be acceptable as a borrowed range in these tests.

I think std::ranges::subrange(x) is also acceptable, but it's slightly longer and less idiomatic than views::all.
Actually perhaps we should make a new dedicated test type, in support/test_range.h:

template<class R>
struct BorrowedRange {
    explicit BorrowedRange(const R& r) : r_(&r) {}
    BorrowedRange(BorrowedRange&&) = delete; // immobile
    auto begin() const { return std::ranges::begin(*r_); }
    auto end() const { return std::ranges::end(*r_); }
    const R *r_;
};
static_assert( std::ranges::borrowed_range<BorrowedRange<int[10]>>);
static_assert(!std::ranges::view<BorrowedRange<int[10]>>);

template<class R>
BorrowedRange<R> make_borrowed_range(const R& r) {
    static_assert(std::ranges::range<const R>);
    return BorrowedRange<R>(r);
}

Then line 87 becomes

std::ranges::swap_ranges(make_borrowed_range(r1), r2);

and it's more self-documenting.
However, the existing support/test_range.h [sic] looks a little messy, so maybe I'll tackle that at some point this week myself, unless you really want to tackle it.

123–127

Consider s/Iter/It/g, s/Sentinel/Sent/g, to shorten these lines.

155–163

Awesome constexprification! But please put each of the two tests in its own { } scope as usual, so Expected2 is defined closer to its point of use. (This requires re-defining r in each scope; I have no problem with that.)

philnik updated this revision to Diff 404273.Jan 29 2022, 8:12 AM
philnik marked 5 inline comments as done.
  • Rebased
  • Address comments

Please git grep swap_ranges ../libcxx/; I believe there's a TODO in iter_swap related to swap_ranges.
Or if you're planning a followup PR for that, that's also OK.

libcxx/include/__algorithm/ranges_swap_ranges.h
36

Here and line 48, we could remove ranges:: from the return type. Should we?
Let's be consistent with whatever you're doing in ranges::mismatch and any other open (or closed) PRs.

libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
28

I think the dependency on std::list is gone? Please check whether any other headers can be removed now.

143

Consider linebreaking.

212

s/int, int/int, char/g so we see we're not accidentally swapping the arguments' order or anything crazy like that. Obviously that bug isn't likely, but it's also trivial to test for.

philnik updated this revision to Diff 404280.Jan 29 2022, 8:55 AM
philnik marked 4 inline comments as done.
  • Address nits
philnik updated this revision to Diff 405466.Feb 2 2022, 3:00 PM
  • Fix CI
ldionne accepted this revision.Feb 9 2022, 6:47 AM

I looked at the implementation, which LGTM. Deferring to @Quuxplusone for the tests.

This revision is now accepted and ready to land.Feb 9 2022, 6:47 AM
Quuxplusone accepted this revision.Feb 9 2022, 8:07 AM

LGTM modulo a few last test nits.

It might also be nice to

static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), cpp17_output_iterator<int*>, int*>);
static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), int*, cpp17_output_iterator<int*>>);

But that's technically non-portable, in that it depends on the ability to take decltype(std::ranges::swap_ranges), which is guaranteed-in-practice-but-not-in-theory because niebloids. So I'm neutral on whether to include those lines somewhere.

libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
97

Nit, throughout: I'd prefer to see std::views::all(rx) instead of std::ranges::subrange(rx). Advantages: shorter, more idiomatic, no CTAD.

171

Above, I'd suggested something involving test_ranges<NonCommon, std::array<int, 3>>(). I no longer particularly care about testing multiple kinds of ranges, because we get some additional coverage in the named tests (e.g. test_borrowed_input_range()). So, let's leave test_range() as testing only std::array alone — but then, please remove its template parameters Range1 and Range2.
Also consider using C arrays instead of std::array, just to keep things simple.

216

It might also be nice to

static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), cpp17_output_iterator<int*>, int*>);
static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), int*, cpp17_output_iterator<int*>>);

Bah, naturally I meant

static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), std::ranges::subrange<cpp17_output_iterator<int*>>, std::ranges::subrange<int*>>);
static_assert(!std::is_invocable_v<decltype(std::ranges::swap_ranges), std::ranges::subrange<int*>, std::ranges::subrange<cpp17_output_iterator<int*>>>);
philnik updated this revision to Diff 407256.Feb 9 2022, 12:52 PM
philnik marked 3 inline comments as done.
  • Rebased
  • Address comments
philnik updated this revision to Diff 407301.Feb 9 2022, 2:29 PM
  • Add pragma system_header
This revision was landed with ongoing or failed builds.Feb 10 2022, 7:02 AM
This revision was automatically updated to reflect the committed changes.