This is an archive of the discontinued LLVM Phabricator instance.

[libc++][ranges] Implement `std::mergeable`.
ClosedPublic

Authored by var-const on Feb 10 2022, 2:30 PM.

Diff Detail

Event Timeline

var-const created this revision.Feb 10 2022, 2:30 PM
var-const requested review of this revision.Feb 10 2022, 2:30 PM
Herald added a project: Restricted Project. · View Herald TranscriptFeb 10 2022, 2:30 PM
Herald added a reviewer: Restricted Project. · View Herald Transcript
var-const updated this revision to Diff 407688.Feb 10 2022, 2:33 PM

Rebase, use the correct link to the patch on the status page.

Looks pretty reasonable to me, mod comments.

libcxx/include/__iterator/mergeable.h
17

Here you need __iterator/projected.h and maybe some others; but the Modular CI build should tell you about it.

27–28

Please put the linebreak before class _Comp. (At least not between Proj1 and Proj2.)

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp
19

Why is <compare> needed?

50

int& operator*() const; ?

59

Grammar nit: AssignableOnlyFromInt

74

Because invocable<BadComp, int&, int&> is false, right? I think it would be cleaner to replace lines 73–79 with just

static_assert( std::mergeable<InputIterator, InputIterator, OutputIterator, bool(*)(int, int)>);
static_assert(!std::mergeable<InputIterator, InputIterator, OutputIterator, bool(*)(int*, int*)>);
90

I might not be parsing this correctly, but isn't decltype(BadProjection()(InputIterator(std::declval<int*>()))) simply Empty?

Here I think it would be cleaner to replace lines 81–92 with something like

static_assert( std::mergeable<const int*, const int*, int*, bool(*)(int, int), std::identity, std::identity>);
static_assert( std::mergeable<const int*, const int*, int*, bool(*)(int, int), int(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int), int*(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int), int(*)(int), int*(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int*, int), int*(*)(int), int(*)(int)>);
static_assert(!std::mergeable<const int*, const int*, int*, bool(*)(int, int*), int(*)(int), int*(*)(int)>);

This doesn't cover anything about value categories / ref-qualification, though, so maybe think about whether we expect something like

struct Projection {
    bool operator(int&, int&) const;
    bool operator(int&&, int&&) const = delete;
};

to work, not-work, or be IFNDR; and whether removing the const from operator() would break anything.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp
21–28

Please add blank lines between these definitions to keep them from all running together visually (since they don't fit on a single line each).

I see clang-format thinks line 25 is a "continuation line" rather than a "separate line"? :P

var-const updated this revision to Diff 407729.Feb 10 2022, 5:25 PM
var-const marked 7 inline comments as done.

Address feedback and rebase.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp
59

Done.

(I'm not a native speaker, but I thought both are fine? At least, I've definitely seen "only" used at the end of a sentence quite a bit, e.g. https://en.wikipedia.org/wiki/For_Your_Eyes_Only)

74

Done. I still think it's good to check whether the comparator defines a strict weak order because it makes the intention of the test clearer (and I created aliases for the function types).

90

Replaced with the tests you provided, thanks (also added some type aliases).

struct Projection is intended to be used as a comparator, right? It does work in practice (also when operator() is not const). It's a good question whether it should work, though. From a glance, I feel like we shouldn't demand the invocation operator to be const (we take it by value and don't have to make our copy const, after all). I think the pre-ranges algorithms allow functors to take their arguments by a non-const reference, but if the functor modifies the values, it's undefined behavior, and I suppose an argument could be made that ranges algorithms should also support this for ease of conversion. As for rvalue arguments, I'm not sure. I don't think we need to solve this in this patch, though.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.subsumption.compile.pass.cpp
21–28

Done. This was formatted manually, clang-format actually merges these into a single line.

LGTM mod comments, but I think someone else should also take a look.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp
32

Huh, I didn't notice until now that mergeable does not actually require that O be an output_iterator — i.e. mergeable<A,B,O> doesn't subsume output_iterator<O, iter_value_t<I>>.
Perhaps you should define your own struct Output here that satisfies only the very minimal requirements and is not actually an output iterator; is that physically possible?

82–83

How about naming these ToInt and ToPtr?
(Or of course eliminating all the typedefs. Implicit in my suggestions here is that I find simple types like int* much easier to parse at a glance, than typedefs like Input and Output where it's not even clear that they're iterators, let alone that their value type is int. So anywhere that the iterator type is "uninteresting," I'd much prefer to see a boring type like int* instead of a typedef. This even extends to the function types: I find bool(*)(int, int) easier to parse than GoodComp.)

90

struct Projection is intended to be used as a comparator, right?

Oops, yeah. I think I started my thought thinking "projection," but then muscle memory turned it into a comparator halfway through. I think the interesting case I was trying to get at was

struct Projection {
    int operator(int&) const;
    int operator(int&&) const = delete;
};

i.e. making sure that the projection was called as proj(*first) with *first as a mutable lvalue.

var-const updated this revision to Diff 408030.Feb 11 2022, 1:18 PM
var-const marked 3 inline comments as done.

Address feedback (in particular, add a test case for WeaklyIncrementable
that's not an output iterator).

var-const updated this revision to Diff 408031.Feb 11 2022, 1:19 PM

Add a comment to WeaklyIncrementable, rebase.

var-const updated this revision to Diff 408034.Feb 11 2022, 1:22 PM
var-const marked an inline comment as done.

Fix and expand comment.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp
32

Yes, it's possible (the way I found is this: weakly_incrementable only requires it++ to be defined, while output_iterator requires it to return something dereferenceable, thus making it return void does the trick). Added a test case for that.

82–83

Thanks, I like these names more.

(I think this depends a lot on personal preference. I'm the other way round -- I find a wall of pointer types with small variations throughout to be quite unreadable, and I think "parsing" natural language is easier than special symbols. Also, using typedefs makes it easier to change the types throughout the file)

90

Projection also works with the current implementation (also with libstdc++ and MSVC implementations).

I think this should work -- mergeable requires the underlying type to be copyable, not just movable between the iterators. If the implementation deals with a copy of the value, restricting the projection to e.g. only const references seems to go against that contract.

Do you want to add Projection as a test case (i.e., do we want to explicitly commit to supporting this)?

Continues to LGTM; continue to want one other person to rubber-stamp it at least.

libcxx/test/std/iterators/iterator.requirements/alg.req.mergeable/mergeable.compile.pass.cpp
90

Do you want to add Projection as a test case (i.e., do we want to explicitly commit to supporting this)?

Yes, my reading of the standard is that we have to support this. (In fact, we have to support Projection even when its operator() is not const-qualified!) Now, probably when we get to the actual ranges::merge algorithm we'll find it's not so clear-cut, at least in theory; but for concept mergeable, the chain of logic/code seems pretty unassailable.

97–98

Drive-by grammar nit ;) but also, mainly, adjusted the line-break point.

var-const updated this revision to Diff 408149.Feb 11 2022, 9:49 PM
var-const marked 2 inline comments as done.

Address feedback

ldionne accepted this revision.Feb 14 2022, 8:37 AM

LGTM with ultra nit.

libcxx/include/iterator
159–162

This is a nit, but can we match the order of the synopsis in the Standard: indirectly_swappable, indirectly_comparable, permutable, mergeable?

This revision is now accepted and ready to land.Feb 14 2022, 8:37 AM
var-const marked an inline comment as done.Feb 14 2022, 10:40 PM

Address feedback, fix the CI, rebase on main.

var-const updated this revision to Diff 408768.Feb 15 2022, 1:48 AM

Rebase on main.

Quuxplusone accepted this revision.Feb 15 2022, 8:49 AM
Quuxplusone added inline comments.
libcxx/include/iterator
529

Nit: This blank line looks unnecessary.

var-const updated this revision to Diff 408912.Feb 15 2022, 9:14 AM

Remove an accidental empty line, rebase on main.

var-const updated this revision to Diff 409537.Feb 17 2022, 1:34 AM

Guard mergeable with _LIBCPP_HAS_NO_INCOMPLETE_RANGES (because it depends on
ranges::less which is guarded by it).

var-const updated this revision to Diff 409554.Feb 17 2022, 2:17 AM

Rebase, mark the subsumption test as not supporting incomplete ranges.

var-const updated this revision to Diff 409825.Feb 17 2022, 5:23 PM

Add a test case for non-default projections.

The CI error looks unrelated (in AIX 32-bit):

Failed Tests (1):
  ibm-libc++-shared.cfg.in ::
std/thread/thread.mutex/thread.mutex.requirements/thread.sharedtimedmutex.requirements/thread.sharedtimedmutex.class/try_lock_shared.pass.cpp
This revision was landed with ongoing or failed builds.Feb 17 2022, 8:12 PM
This revision was automatically updated to reflect the committed changes.