Page MenuHomePhabricator

[libc++][ranges] Add indirectly_comparable concept
ClosedPublic

Authored by philnik on Dec 24 2021, 5:55 AM.

Details

Summary

Add indirectly_comparable concept

Diff Detail

Event Timeline

philnik requested review of this revision.Dec 24 2021, 5:55 AM
philnik created this revision.
Herald added a project: Restricted Project. · View Herald TranscriptDec 24 2021, 5:55 AM
Herald added a reviewer: Restricted Project. · View Herald Transcript
philnik updated this revision to Diff 396156.Dec 24 2021, 6:00 AM
  • Updated synopsis
Quuxplusone requested changes to this revision.Dec 25 2021, 9:09 PM

🎄😄

libcxx/include/__iterator/iter_swap.h
102–103 ↗(On Diff #396156)

This code looks fine, but why on earth is it in iter_swap.h?
It should be in __iterator/concepts.h, or (because I think that would create a cycle) just put it in __iterator/indirectly_comparable.h.

Somewhat tangential query: Is this the last of the <iterator> concepts? or are we still missing some?

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
19–20

Direct inclusion of <__iterator/readable_traits.h> will fail the modules build.
I've never seen libcxx/test/support/indirectly_readable.h before but it looks crazy complicated; can we avoid using it here? I think all you actually need for this test would be something like

struct Deref {
    int operator()(int*) const;
};

static_assert(!std::indirectly_comparable<int, int, std::less<int>>);  // not dereferenceable
static_assert(!std::indirectly_comparable<int*, int*, int>);  // not a predicate
static_assert( std::indirectly_comparable<int*, int*, std::less<int>>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>>);
static_assert( std::indirectly_comparable<int**, int*, std::less<int>, Deref>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, Deref, Deref>);
static_assert(!std::indirectly_comparable<int**, int*, std::less<int>, std::identity, Deref>);
static_assert( std::indirectly_comparable<int*, int**, std::less<int>, std::identity, Deref>);

And then a subsumption test in each direction:

template<class F> requires std::indirectly_comparable<int*, char*, F> && true
constexpr bool subsumes(F f) { return true; }

template<class F> requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>>
void subsumes(F f);

template<class F> requires std::indirect_binary_predicate<F, std::projected<int*, std::identity>, std::projected<char*, std::identity>> && true
constexpr bool is_subsumed(F f) { return true; }

template<class F> requires std::indirectly_comparable<int*, char*, F>
void is_subsumed(F f);

static_assert(subsumes(std::less<int>()));
static_assert(is_subsumed(std::less<int>()));

https://godbolt.org/z/c9rEh8e8c

This revision now requires changes to proceed.Dec 25 2021, 9:09 PM
philnik updated this revision to Diff 396212.Dec 26 2021, 1:36 AM
philnik marked 2 inline comments as done.
  • Updated test
  • Moved indirectly_comparable into its own header
philnik added inline comments.Dec 26 2021, 1:36 AM
libcxx/include/__iterator/iter_swap.h
102–103 ↗(On Diff #396156)

There are at least permutable, mergable and sortable missing, probably more.

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
19–20

Why does it make a difference if there is the && true at the end? Is there some "this has more requirements, so it must be stricter"?

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
19–20

Yep. See circa 20m–35m in my "Concepts As She Is Spoke" (CppCon 2018). The idea here is that subsumes #2 is constrained by a bunch of stuff, and then subsumes #1 is constrained by all that same stuff plus one additional atomic constraint of "true (line 1, column 73)." So subsumes #1 is strictly more constrained.

Note that Concepts does not treat the keywords true and false as magic.

FWIW, I find the linebreak positions on lines 30–31 and 39–40 to be weird. Doesn't really matter, though.

LGTM % comments

libcxx/include/__iterator/indirectly_comparable.h
23
libcxx/include/__iterator/iter_swap.h
17 ↗(On Diff #396212)

These two includes can vanish again.

Mordante accepted this revision.Dec 28 2021, 9:33 AM

LGTM modulo some nits. Make sure it passes the CI before committing. (I know the CI isn't working at the moment.)

libcxx/docs/Status/RangesPaper.csv
66

Maybe update the name ;-)

libcxx/include/module.modulemap
597

I don't see the generated test for this header.

libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
22

Is there a reason not to include static_assert(!std::indirectly_comparable<int, int, std::less<int>>); // not dereferenceable?
I would like to see the suggested comment copied.

32

I think this can use comment, it looks like magic. (And yes I read the reason for it above.)

This revision is now accepted and ready to land.Dec 28 2021, 9:33 AM
libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
22

+1, also the one before it:

static_assert(!std::indirectly_comparable<int, int, std::less<int>>);  // not dereferenceable
static_assert(!std::indirectly_comparable<int*, int*, int>);  // not a predicate

FYI I'm not married to those specific code comments. I put them because I thought otherwise it was a little subtle (particularly because these are the first couple of lines, where the reader is still getting a handle on what we're doing here). After the first two lines, the "not a..." explanations get really complicated to explain, plus the reader should have gained a little experience decoding the earlier lines, so I figured comments were more pain than gain at that point.

philnik updated this revision to Diff 396433.Dec 28 2021, 2:22 PM
philnik marked 8 inline comments as done.
  • Updated name
  • Added line-break
  • Removed headers
  • Added header test
  • Added missing assertions
  • Added comment
libcxx/test/std/iterators/iterator.requirements/indirectcallable/indirectinvocable/indirectly_comparable.compile.pass.cpp
22

The reason is that they are not in the godbolt link and I copied the code from there :).

Mordante accepted this revision.Dec 29 2021, 9:34 AM

Thanks for the update.

Quuxplusone accepted this revision.Dec 29 2021, 9:38 AM
philnik updated this revision to Diff 397133.Jan 3 2022, 2:03 PM

Rebased to trigger CI

Why is the CI failing? I ran all the generator scripts, but it didn't change anything.

Why is the CI failing? I ran all the generator scripts, but it didn't change anything.

https://buildkite.com/llvm-project/libcxx-ci/builds/7566#fbd04c3f-dcc1-45dd-993c-a9fd09735bdf says:

+ grep -rn '[^ -~]' libcxx/include/
libcxx/include/iterator:145:  concept indirectly_­comparable =
libcxx/include/iterator:146:    indirect_­binary_­predicate<R, projected<I1, P1>, projected<I2, P2>>; // since C++20

This means there's some non-ASCII character in there (on each of those lines). If you copied from eel.is, it's probably a zero-width space character in the vicinity of one of the underscores. A sufficiently dumb text editor will be able to show you exactly where.

philnik updated this revision to Diff 397228.Jan 4 2022, 2:05 AM
  • Removed whitespaces
philnik updated this revision to Diff 397263.Jan 4 2022, 4:24 AM
  • Include <__iterator/concepts.h>
philnik updated this revision to Diff 397355.Jan 4 2022, 11:32 AM
  • Include <functional> in test
This revision was automatically updated to reflect the committed changes.