This is an archive of the discontinued LLVM Phabricator instance.

[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

philnik requested review of this revision.Dec 27 2021, 4:08 AM
philnik created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptDec 27 2021, 4:08 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
Quuxplusone requested changes to this revision.Dec 28 2021, 4:16 PM
Quuxplusone added a subscriber: jloser.

The code looks pretty solid to me (although I am still requesting to reorganize it). The tests need more fleshing out.

Part of the reason for this PR is to experiment and see whether we want {__algorithm/in_in_result.h, etc} or {__algorithm/results.h}. I would say that AFAICT it provides no interesting evidence for either option, but it's definitely not evidence against my hypothesis that {__algorithm/in_in_result.h, etc} is the right choice. :) The use of in_in_result.h here feels pretty natural and self-documenting.

libcxx/include/__algorithm/swap_ranges.h
12–19

The includes needed by std::swap_ranges and std::ranges::swap_ranges practically don't overlap at all, nor are they ever used together, nor is there any circular dependency between them. Therefore (and for other pre-existing prejudices about code organization ;)) I think ranges::swap_ranges should be moved into a new file __algorithm/ranges_swap_ranges.h.

16

Please leave the spacing here consistent with every other header file. (I know, clang-format strikes again; but we have hundreds of header files that use the old spacing, and we shouldn't change them one at a time (or, IMHO, at all).)

40–41
43–44
48
libcxx/include/algorithm
675–682

These changes LGTM, and also IIUC you should remove the comment on line 673 as well. But please make these changes in a separate trivial PR (which I'll "LGTM" as soon as I see it).

libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
76–77

I suspect that in the process of adding all the below-requested tests, you'll realize that either the templated test2 should go away entirely, or it needs a few more template parameters. Whatever happens, I'd prefer to stay away from circular-looking assertions like this, where we depend on metaprogramming to tell us the answer to some other metaprogramming. Ideally, the tests would be as simple and self-evident as possible, e.g.

{
std::list<int> r1 = {1, 2, 3};
std::vector<int> r2 = {4, 5, 6};
using It1 = std::list<int>::iterator;
using It2 = std::vector<int>::iterator;
std::same_as<std::ranges::in_in_result<It1, It2>> auto r =
    std::ranges::swap_ranges(r1, r2);
// Or: auto r = std::ranges::swap_ranges(r1, r2);
//     ASSERT_SAME_TYPE(decltype(r), std::ranges::in_in_result<It1, It2>);
assert(r.in1 == r1.end());
assert(r.in2 == r2.end());
assert((r1 == std::list<int>{4, 5, 6}));
assert((r2 == std::vector<int>{1, 2, 3}));
}
96–102

(1) I'm not thrilled by the test1, test2, tests1, tests2 naming scheme. I'd prefer a very minor modification: keep test1 and test2, but combine tests[12] into a new constexpr bool test() that does all of the calls to test[12], and then main just does the usual test() / static_assert(test()). Alternatively, maybe the templated test[12] disappear, and then you just rename tests[12] to test_iterator_sentinel and test_range.

(2) I don't see any tests for

  • non-contiguous range types
  • non-iterator sentinel types
  • two inputs that aren't of the same length
  • non-forward iterators (e.g. cpp20_input_iterator and cpp17_input_iterator), and ranges thereof
  • borrowed range types e.g. subrange (right?)
  • non-borrowed range types as rvalues, which IIUC should return swap_ranges_result<dangling, Iter2> or swap_ranges_result<Iter1, dangling> so let's test that
  • SFINAE-friendliness (I believe you can-and-should just add a line to @jloser's cpo.compile.pass.cpp, or optionally start a new sibling file specifically for the ranges algorithms)
  • the non-constrainedness of swap_ranges_result, e.g. swap_ranges_result<int, int> p; is a perfectly fine declaration (Admittedly this is basically implied by the fact that swap_ranges_result<dangling, dangling> is OK — dangling is not an iterator either — but IMO let's test it anyway just for the record. It's the least important of these items by far, though)
This revision now requires changes to proceed.Dec 28 2021, 4:16 PM
philnik updated this revision to Diff 396976.Jan 2 2022, 6:37 PM
philnik marked 6 inline comments as done.
  • Moved ranges::swap_range into its own header and style changes
  • Updated test
philnik added inline comments.Jan 2 2022, 6:37 PM
libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
96–102

What non-iterator sentinel types are there? Is somewhere a list of them? I looked at https://en.cppreference.com/w/cpp/header/ranges but didn't see anything of interest there.

Quuxplusone added inline comments.Jan 3 2022, 8:58 AM
libcxx/test/std/algorithms/alg.modifying.operations/alg.swap/ranges.swap_ranges.pass.cpp
96–102

For our purposes, use sentinel_wrapper<T> from "test_iterators.h". So for example something like this:

struct NonCommon {
  int data_[3] = {};
  auto begin() { return forward_iterator<int*>(data_); }
  auto end() { return sentinel_wrapper<forward_iterator<int*>>(forward_iterator<int*>(data_ + 3)); }
};
test_ranges<std::array<int, 3>, NonCommon>();
test_ranges<NonCommon, std::array<int, 3>>();

Just FYI, there are some standard sentinel types: std::default_sentinel and std::unreachable_sentinel, and then there are harder-to-name ones such as std::ranges::sentinel_t<std::ranges::take_while_view<std::string_view, bool(*)(int)>> (actually there's nothing normative to stop that type from also being some kind of iterator, but in practice it never is).

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.