Page MenuHomePhabricator

[libc++][ranges] Add range.cmp: equal_to, not_equal_to, less, etc.
ClosedPublic

Authored by zoecarver on Apr 13 2021, 5:28 PM.

Details

Summary

Adds the six new concept constrained comparisons.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Quuxplusone added inline comments.Fri, Apr 16, 8:34 AM
libcxx/test/std/utilities/function.objects/range.cmp/equal_to.pass.cpp
27–32

Nit: Please remove these two instances of constexpr, and also remove all other constexpr that aren't necessary to the point of the test. Remember, in general, concepts care only whether some expression e.g. x == y is well-formed; they don't actually try to evaluate the expression at compile-time. (And so we should save the 10 characters. But also, weakly-arguably, removing constexpr makes the test stronger because now we're kinda "verifying" that nothing in libc++ is trying to evaluate x == y at compile time.)

37–38

Drive-by FYI: the test class explicit_operators provides seven comparison operators (both the usual six and a redundant operator<=>). I'm not sure that was intentional.

libcxx/test/support/compare_types.h
7–9

Probably a good idea to fix the include guard's name.

516–518

Nit: please fix the whitespace to match lines 574-577, i.e., { return false; } all on the same line. Ditto below.

libcxx/test/support/pointer_comparison_test_helper.h
23–24

This loop now runs 100x100 times, and doesn't actually test anything after the first two iterations.
I see you are now testing 3 of the 4 cases here:

  • valid pointer versus itself
  • valid pointer versus another valid pointer
  • null pointer versus null pointer

but you aren't testing

  • valid pointer versus null pointer

Is that because you think it's undefined behavior? I don't know whether it is or not. But anyway, I think the structure of this function ought to reflect the fact that there are 4 cases to test — not, like, 100x100 cases.

zoecarver updated this revision to Diff 338249.Fri, Apr 16, 3:00 PM
  • Apply most of Arthur's comments.
zoecarver added inline comments.Fri, Apr 16, 3:02 PM
libcxx/include/functional
3244

I don't really care which thing we do. As for this comment and the one below, I'd be interested to hear other's opinions as well. I'm happy to implement whatever the consensus is.

libcxx/test/std/utilities/function.objects/range.cmp/equal_to.pass.cpp
37–38

I'm pretty sure it wasn't. I removed the spaceship operator. Not that it matters too much which are removed, but I think explicit_operators sort of indicates that the individual operators are declared.

cc @cjdb

zoecarver added inline comments.Fri, Apr 16, 3:03 PM
libcxx/test/support/compare_types.h
26

If all these changes are distracting, I can move and format this file in a separate nfc patch.

cjdb requested changes to this revision.Fri, Apr 16, 11:22 PM
cjdb added inline comments.
libcxx/include/functional
3243

noexcept specifiers would be appreciated.

3244

Per range.cmp, not_equal_to::operator() has effects equivalent to return !ranges::equal_to{}(std::forward<T>(t), std::forward<U>(u)).

I'd actually prefer to see all of the implementations return the expressions in the standard wording, verbatim.

libcxx/test/std/utilities/function.objects/range.cmp/equal_to.pass.cpp
37–38

but I think explicit_operators sort of indicates that the individual operators are declared.

Yes, this was intentional.

This revision now requires changes to proceed.Fri, Apr 16, 11:22 PM
Quuxplusone added inline comments.Sat, Apr 17, 4:48 PM
libcxx/test/std/utilities/function.objects/range.cmp/greater_equal.pass.cpp
34

Btw, if this test still compiles after making is_transparent equal to void, something is a little screwy somewhere. I recommend

static_assert(requires { typename std::ranges::greater_equal::transparent; });

as you've got elsewhere. (And apply consistently throughout.)

41

This comment is more confusing than other comments. (I recommend deleting it.)
Also, consider checking heterogeneous comparisons: fn(2, 1L) and maybe even fn(2, MoveOnly(1)) if the latter compiles (I'm not sure off the top of my head whether we expect it to or not, nor whether that's interesting).

libcxx/test/std/utilities/function.objects/range.cmp/not_equal_to.pass.cpp
28

remove constexpr here

libcxx/test/support/compare_types.h
26

FYI, no objection from me if you want to push a whitespace-only cleanup. (But I don't find these changes particularly distracting, either.)
Or, give me the go-ahead and I'll do it.

47–48

I do wonder, in passing, (A) what ec1 stands for, and (B) why we provide an operator!= here when we already have a suitable operator==.
Also, in passing, none of these should be noexcept. (Removing that keyword in the first place would have shortened the line enough to escape the ravages of clang-format, and then we wouldn't even be looking at this code anymore.)

cjdb added inline comments.Sat, Apr 17, 5:22 PM
libcxx/test/support/compare_types.h
47–48

(A) what ec1 stands for

equality_comparable1. I didn't expect people would like equality_comparable_with_equality_comparable1. Perhaps control would be a more descriptive name.

(B) why we provide an operator!= here when we already have a suitable operator==.

Many types that predate C++20 have operator!=.

Also, in passing, none of these should be noexcept.

noexcept is fine, unless you can provide a technical reason why it "shouldn't" be there.

tcanens added inline comments.
libcxx/include/functional
3244

I've removed the claim on cppreference that this can be implemented with !=; the convertible-to-pointer corner case means that it can't - consider a case where == results in a built-in comparing pointers but != doesn't; we attach no semantic requirements to the != in such a case.

Quuxplusone added inline comments.Sat, Apr 17, 10:13 PM
libcxx/include/functional
3244

@tcanens: Uh-oh. And the resolution of https://cplusplus.github.io/LWG/issue3530 doesn't affect your statement?
Could you post an example test case where the difference between !ranges::equal_to{}(FWD(t), FWD(u)) and FWD(t) != FWD(u) is observable?
And I would bet that the difference between !ranges::equal_to{}(FWD(t), FWD(u)) and !(FWD(t) == FWD(u)) is also observable, because the latter might be applying ! to a type other than bool?

cjdb added inline comments.Sat, Apr 17, 10:53 PM
libcxx/include/functional
3244

And the resolution of https://cplusplus.github.io/LWG/issue3530 doesn't affect your statement?

No, because that's exclusively to do with pointers.

Could you post an example test case where the difference between !ranges::equal_to{}(FWD(t), FWD(u)) and FWD(t) != FWD(u) is observable?

enum class X { a, b };

[[nodiscard]] bool operator!=(X const x, X const y) noexcept
{
  auto const result = static_cast<int>(x) != static_cast<int>(y);
  std::cout << result << '\n';
  return result;
}

Same for t > u below.

And I would bet that the difference between !ranges::equal_to{}(FWD(t), FWD(u)) and !(FWD(t) == FWD(u)) is also observable, because the latter might be applying ! to a type other than bool?

Sadly. I think !bool(FWD(t) == FWD(u)) is okay because FWD(t) == FWD(u) needs to be converted to bool in ranges::equal_to{}(FWD(t), FWD(u)) anyway.

tcanens added inline comments.Sat, Apr 17, 10:55 PM
libcxx/include/functional
3244
struct T {
    operator void*() const { return nullptr; }
    friend bool operator!=(T, T) { return true; }
};

LWG3530 means that implementations don't have to use heroic efforts to detect and support types for which the other comparisons are ill-formed, but here the comparison is well-formed and "just" gives nonsensical results. It doesn't seem to be worth the extra specification effort to make this pathological case undefined, since the comparison function objects are the only ones affected, and they still produces meaningful results.

And I would bet that the difference between !ranges::equal_to{}(FWD(t), FWD(u)) and !(FWD(t) == FWD(u)) is also observable, because the latter might be applying ! to a type other than bool?

boolean-testable has enough semantic requirements for the latter to work (and for the carve-out case the result type is definitely bool). I would consider the difference unobservable.

tcanens added inline comments.Sat, Apr 17, 11:07 PM
libcxx/include/functional
3244

I think the enum example goes a bit too far. For types required to model equality_comparable (or even the weaker form), I'm pretty sure the intent is that implementations can use x != y and !(x ==y) mostly interchangeably.

  • Apply feedback
  • Add noexcept
  • Add tests for heterogeneous types
zoecarver added inline comments.Tue, Apr 20, 11:26 AM
libcxx/include/functional
3244

Okay so @cjdb wants the wording from the standard verbatim and @Quuxplusone wants !=. Again, I don't feel strongly, so unless there's a consensus (or a majority who strongly prefers one) I'm going to leave this as-is.

cjdb accepted this revision.Tue, Apr 20, 11:34 AM

LGTM pending feedback resolution.

libcxx/include/functional
3228–3229

Perhaps we should put this in __detail/noexcept_helpers.h?

3244

We can't use != (similarly for <=, >=, and >). I don't mind using == and < directly since you're using _LIBCPP_NOEXCEPT_RETURN, but if you'd prefer to make a helper variable (e.g. __is_less_nothrow<T, U>), then going with the standard wording is probably better.

Quuxplusone added inline comments.Tue, Apr 20, 12:11 PM
libcxx/include/functional
3228–3229

If it ends up being used in more than one place, we might want to pull it out (or else stop using it). For now, it's good to follow the general principle of "declare as close as possible to the point of use."

3232

I like [[nodiscard]] here. But shouldn't we be expressing it via _LIBCPP_NODISCARD_EXT?
@ldionne, thoughts?

If [[nodiscard]] (or the spelling thereof) is not immediately a no-brainer for @ldionne, then I suggest leaving it off for now, and applying _LIBCPP_NODISCARD_EXT consistently across the entire <functional> library in a separate PR. For example, right now std::less<int>::operator() is not-nodiscard; I think we probably all agree that it should be nodiscard; but that'd be an extension and we'd want to use the right macro and we'd want tests for it.

3244

Leaving as-is is good with me. The fewer constrained function templates we instantiate, and the fewer dependencies-on-other-functions we introduce, the better. :)
However, before landing, please do change it to use != locally and verify that at least one of your test cases "successfully fails." (IOW, I believe Tim when he says we can't use !=; but if it's true we can't use !=, then we should have a regression test for that. We shouldn't land this without some such "successfully failing" test.)

zoecarver added inline comments.Tue, Apr 20, 1:58 PM
libcxx/include/functional
3228–3229

@Quuxplusone it's also used in D100255 and <tuple>. __detail/noexcept_helpers.h sounds good to me. But maybe there's a more general place we could start putting stuff like this. (A place we could also move some stuff to, mainly from type_traits.)

3244

So, I'm adding a test for

struct OddType {
    constexpr operator void*() const { return nullptr; }
    friend constexpr bool operator!=(OddType, OddType) { return true; }
};

IIUC the pointer exception gives us the ability to have this type (where != isn't the same as !(==)). However, this is where it gets fun... because if this type is supported (and if I'm writing a test for it) then the Standard says std::ranges::not_equal_to()(OddType(), OddType()) should be false, even though the != operator unconditionally returns true. I'm happy to add that test, but I don't see a lot of benefit in it, and it seems very confusing. I think "ignoring" this case, or filing an LWG issue would be a better course of action.

zoecarver updated this revision to Diff 338993.Tue, Apr 20, 2:01 PM
  • Apply review feedback.
  • Rebase.
zoecarver added inline comments.Tue, Apr 20, 2:02 PM
libcxx/include/__detail/noexcept_helpers.h
25 ↗(On Diff #338993)

We never get a chance to #undef this now but I think that's OK.

zoecarver added inline comments.Tue, Apr 20, 2:56 PM
libcxx/include/functional
3244

LWG3530 means that implementations don't have to use heroic efforts to detect and support types for which the other comparisons are ill-formed, but here the comparison is well-formed and "just" gives nonsensical results. It doesn't seem to be worth the extra specification effort to make this pathological case undefined, since the comparison function objects are the only ones affected, and they still produces meaningful results.

@tcanens LWG3530 unconditionally constrains not_equal_to with equality_comparable_with which semantically requires that (!(x == y)) == (x!=y). Doesn't that mean T isn't a valid argument in your example?

tcanens added inline comments.Tue, Apr 20, 3:37 PM
libcxx/include/functional
3244

"satisfies" is purely syntactic, and that's intentional. The semantic requirements are imposed through "models".

LWG3530 is careful to not impose the equality_comparable_with (and similar) semantic requirements on things that reduce to built-in pointer comparisons because the whole point of the special case is to produce a consistent total order even when the built-in comparison doesn't.

In some cases with raw pointers, the core language permits x == y and x != y to both produce true (or both false); the example isn't really behaviorally distinguishable from such a case, and I don't think it's worth spending LWG's time crafting wording trying to ban it.

zoecarver added inline comments.Tue, Apr 20, 3:46 PM
libcxx/include/functional
3244

OK. I get it. I was confused because of the Constraints: T and U satisfy equality_comparable_with. But I understand now, T and U do satisfy equality_comparable_with, it's just the built-in pointer that the operator reduces them to which doesn't.

So, you don't think it's worth LWG's time to "fix" this so that in your example the != operator is selected? I was going to write up an email to the reflector, but if you don't think it makes sense to spend time on it, then I won't.

tcanens added inline comments.Tue, Apr 20, 4:13 PM
libcxx/include/functional
3244

OK. I get it. I was confused because of the Constraints: T and U satisfy equality_comparable_with. But I understand now, T and U do satisfy equality_comparable_with, it's just the built-in pointer that the operator reduces them to which doesn't.

The built-in pointers satisfy equality_comparable_with (but do not model it unless restricted to the domain on which the comparisons have well-defined results by core language rules).

So, you don't think it's worth LWG's time to "fix" this so that in your example the != operator is selected? I was going to write up an email to the reflector, but if you don't think it makes sense to spend time on it, then I won't.

I definitely don't want != to be selected in that example. That breaks the guarantee that ranges::equal_to(x, y) == !ranges::not_equal_to(x, y) which is far more critical.

zoecarver added inline comments.Tue, Apr 20, 4:20 PM
libcxx/include/functional
3244

OK. Thanks for explaining. In that case, I guess this is just a weird type, and the behavior is as correct as it can/should be.

zoecarver updated this revision to Diff 339040.Tue, Apr 20, 4:29 PM
  • Add test for PtrAndNotEqOperator.
tcanens added inline comments.Wed, Apr 21, 6:52 AM
libcxx/include/functional
3235

The implicit conversion to bool is not captured in the noexcept, ditto elsewhere.

libcxx/test/support/pointer_comparison_test_helper.h
13

If you want to test this sort of thing, I'd suggest something like the example from https://gcc.gnu.org/bugzilla/show_bug.cgi?id=78420#c0. "Comparison produces a total order when the built-in is required to" (which describes 3/4 of the test cases below) is not a particularly interesting property compared to "comparison produces a total order even when the built-in is not required to".

Quuxplusone added inline comments.Wed, Apr 21, 7:32 AM
libcxx/include/__detail/noexcept_helpers.h
25 ↗(On Diff #338993)

Yes, that part is okay.
Based on @tcanens' repeated observations that this macro is being misused to create the wrong noexcept-specifiers, though, I think we ought to put a moratorium on this kind of macro. It's not really saving us any work, in the sense that it's actually slowing down reviews by making us have to skip back and forth to compare the function body with the definition of the macro, and then find out that the macro is doing the wrong thing in this case, and so on. I think noexcept-clauses should just be written out in the usual way, and this macro should be retired.

Bonus: no more __detail/ dumping-ground directory. Bonus: no more noexcept_helpers.h (plural name, only one "helper", helper doesn't help).

libcxx/test/support/pointer_comparison_test_helper.h
13

How about

struct {
  int a, b;
} local;
int *a = &local.a;
int *b = &local.b;
int *c = nullptr;
int *d = &local.a + 1;
std::uintptr_t ua = reinterpret_cast<std::uintptr_t>(a);
std::uintptr_t ub = reinterpret_cast<std::uintptr_t>(b);
std::uintptr_t uc = reinterpret_cast<std::uintptr_t>(c);
std::uintptr_t ud = reinterpret_cast<std::uintptr_t>(d);
assert(comp(a, a) == ucomp(ua, ua));
assert(comp(a, b) == ucomp(ua, ub));
assert(comp(a, c) == ucomp(ua, uc));
assert(comp(a, d) == ucomp(ua, ud));
assert(comp(b, a) == ucomp(ub, ua));
assert(comp(b, b) == ucomp(ub, ub));
assert(comp(b, c) == ucomp(ub, uc));
assert(comp(b, d) == ucomp(ub, ud));
assert(comp(c, a) == ucomp(uc, ua));
assert(comp(c, b) == ucomp(uc, ub));
assert(comp(c, c) == ucomp(uc, uc));
assert(comp(c, d) == ucomp(uc, ud));
assert(comp(d, a) == ucomp(ud, ua));
assert(comp(d, b) == ucomp(ud, ub));
assert(comp(d, c) == ucomp(ud, uc));
assert(comp(d, d) == ucomp(ud, ud));

I haven't thought hard about how to factor out the testing of std::less<int*> and std::less<> so that you can just call the function template twice with different args instead of repeating that entire 16-line array of tests for vcomp.

Quuxplusone added inline comments.Wed, Apr 21, 8:01 AM
libcxx/include/functional
510–511

(Now moot, but just for your future information) libc++ sorts _ asciibetically prior to a:
__config __detail concepts type_traits typeinfo is correct,
concepts __config __detail typeinfo type_traits would be wrong.

  • Fix noxecpt (remove header)
  • Re-write pointer_comparison_test_helper.h again.
libcxx/test/support/pointer_comparison_test_helper.h
13

The loop is back. But in this case, think it both increases coverage and readability. Let me know what you think.

zoecarver added inline comments.Wed, Apr 21, 10:02 AM
libcxx/test/support/pointer_comparison_test_helper.h
5

No need for std::vector or memory to be included here.

  • Remove unused includes.
Quuxplusone added inline comments.Wed, Apr 21, 10:10 AM
libcxx/test/support/pointer_comparison_test_helper.h
26–29

I don't mind the loop now; but please use the values I gave:

struct {
  int a, b;
} local;
int *pointers[] = { &local.a, &local.b, nullptr, &local.a + 1 };

The reason for these four values in particular is:

  • &a < &b is true in practice but unspecified in theory (AFAIK) (because a and b are not members of the same array).
  • &a < &a+1 is true in both practice and theory
  • &b == &a+1 is UB in practice but unspecified in theory

(&b and &a+1 are the same memory address in practice; but compilers including GCC and perhaps Clang will do front-end optimizations under the assumption that a pointer derived from a cannot possibly alias a pointer derived from b. So in practice you get inconsistent results; see my blog post linked earlier. But, for our purposes here, as @tcanens said, this is the sole really interesting case. Certainly it is uninteresting to compare &buff[0] with &buff[1].)

  • Use Arthur's values.

Okay, the builds passed (after only 11 hours). @Quuxplusone how's this looking to you?

Quuxplusone requested changes to this revision.Thu, Apr 22, 11:09 AM
Quuxplusone added inline comments.
libcxx/test/std/utilities/function.objects/range.cmp/less.pass.cpp
61

BLOCKER: Did you mean /std::less/std::ranges::less/? But then that won't compile, right? because std::ranges::less is not a class template anymore?

The good news is that literally everything else in this patch is good; I downloaded the raw diff and went through it in git diff, so it wasn't until the very end that I got to the newly added files and found the lack of tests for std::ranges::less. :)

I recommend splitting out the trivial whitespace diffs and just landing them for now.
(This will also help in case you end up having to revert the functional change later.)

libcxx/test/support/compare_types.h
7–9

Throughout: s/TEST_SUPPORT_COMPARISON_TYPES_H/TEST_SUPPORT_COMPARE_TYPES_H/

This revision now requires changes to proceed.Thu, Apr 22, 11:09 AM
  • Fix final (?) two nits.
Quuxplusone accepted this revision as: Quuxplusone.Thu, Apr 22, 12:49 PM

Seems OK to me at this point. Might want to have @ldionne take a look at it, though.
(I'm particularly wondering if there's a good way to de-duplicate the two copies of do_pointer_comparison_test.)

This revision was not accepted when it landed; it landed in state Needs Review.Thu, Apr 22, 6:06 PM
This revision was landed with ongoing or failed builds.
This revision was automatically updated to reflect the committed changes.