Comparison concepts and reference types

[CaseyCarter]

We have quite a few concepts in the TS that are well-defined over value types - un-cv-qualified non-array object types - whose meaning is unclear for non-value types. We need to determine what their meaning should be. I'll examine EqualityComparable as a representative example in hopes that whatever conclusion I reach can be generalized to cover this entire class of concepts.

EqualityComparable

EqualityComparable<foo>() has a straight-forward meaning for a value type foo:

• bool(a == b) iff a equals b (== means "equals")
• bool(a != b) == !bool(a == b) (As relations, != is the complement of ==)
• a == b and a != b are valid non-modifying equality-preserving expressions if both a and b are expressions with type foo or const foo and any value category.

(Aside: The requirement "bool(a == a)" is not axiomatic; it's implied by "bool(a == b) iff a equals b". It also seems reasonable to me to require that the definition spaces of the two expressions be equal. Neither of these observations is in scope for this particular discussion.)

What meaning, if any, should EqualityComparable<const foo>() have? EqualityComparable<foo&>()? EqualityComparable<volatile foo&&>()?

Status Quo

What meaning does the current specification of EqualityComparable ascribe to non-value types?

• The very first sentence in the prose, "Let a and b be objects of type T," doesn't have a well-defined meaning when T is a non-object type.
• If T is a function or array type, the parameters of the requires clause are effectively of type const decay_t<T>; parameters are decayed just as function parameters are. As a result, EqualityComparable<int(double)>() == EqualityComparable<int(*)(double)>() and EqualityComparable<int[42]>() == EqualityComparable<int*>(), neither of which seems sensible to me since we cannot directly compare functions nor arrays for equality in C++. Even more bizarre is the cross-type case, where EqualityComparable<int[13],int[42]>() == EqualityComparable<int*,int*>().
• If T is a reference type, const T is the same type as T, so the required expressions must be valid for lvalues of type remove_reference_t<T>. If remove_reference_t<T> is not const, the expressions may modify the operands and they do not implicitly require expression variants.
• cv-qualified non-reference T actually seems meaningful. "a equals b" is defined for values, and object types that differ in their cv-qualifiers have the same value type.

  • const const T is the same type as const T so the required expressions are exactly equivalent to the expressions required by unqualified T when T is const-qualified. This would not be the case for a concept with expressions that are intended to allow modification. Given a hypothetical concept C<T> that requires an expression f(t) that may modify t, C<const T> requires f(ct) to be non-modifying and have implicit expression variants that also must be non-modifying. It's subtle that a template with associated constraints that include both C<foo> and C<const foo> actually forbids f to modify a mutable lvalue foo.

  • The case for volatile is similar: the explicitly required expressions operate on lvalues of type const volatile T, so implicit expression variants are required for all value categories of expressions with type const volatile T or volatile T, but notably not types T or const T. This could be addressed by extending the wording for implicit expression variants to generally cover all less-cv-qualified types.

    The same considerations apply for C<volatile foo> and C<const volatile foo> as noted above for C<foo> and C<const foo>.

    Note that the expression stability requirement in [concepts.lib.general.equality]/3 effectively disables the meaning of volatile in equality-preserving expressions: an external process or action may change the value of a volatile object, but it's forbidden to do so when the library may observe it. This distinction is subtle and may cause confusion if value-semantic concepts admit volatile types.

Functions & Arrays

The consequences of allowing function and array types are both bizarre and subtle, I believe the entire class of value-semantic concepts should categorically reject them.

References

The effects of allowing reference types are also quite subtle. The vast majority of non-language lawyers don't know how cv-qualifiers apply to reference types and won't have a chance of intuiting what EqualityComparable<Foo&&> means. Admitting reference types leads to a particular logic error I call "type/reference confusion": it's not clear to the reader or writer of code whether the intent is that the concept requirements apply to the type of the reference, or apply to the type of the referent. Proxy reference types exacerbate this problem in that they aren't easily distinguishable as references. If users become accustomed to C<Foo&> having the same meaning as C<Foo>, they will be caught unawares when e.g. C<reference_wrapper<Foo>> does not.

Until we have more widespread user experience with the TS I think it's best that the value-semantic class of concepts not admit reference types. What's not clear to me is whether the concepts should reject reference types syntactically, or if a program that applies such a concept to a reference type should be ill-formed. I've used both techniques for various concepts in the implementation of the TS at different times. My experience - which can hardly be considered statistically representative - is that hard errors usually occur closer to the source of the problem, and that silent rejections result in hard to find bugs buried beneath layers of templates and concepts.

cv-qualifiers

I'm least certain about how to approach cv-qualifiers. I can see a path that will give them meaning - much as we did with the object concepts - although there are still some subtleties. How we choose to handle cv-qualifiers has ramifications for the rest of the design. An Iterator cannot currently have a volatile-qualified reference type, for example, and allowing that would require changes throughout the algorithm specifications. Supporting volatile-qualified types in the concepts provides little value if the rest of the library doesn't support them, and changing the entire TS to support a freakish corner case is out of the question.

const-qualified types are easily supportable with reasonable semantics, and less marginal than volatile types. I'm fairly certain the existing wording of the library concepts works with const types and would require no changes. Forbidding reference types and volatile qualifiers while allowing const does seem like a special case to me, and therefore undesirable for consistency's sake.

Conclusions

If I had to choose an approach right now I would keep the meaning of the concepts as sharply defined as possible by rejecting non-object types, array types, and cv-qualified types syntactically, while making reference types ill-formed. Users must then learn that satisfaction of C<remove_const_t<T>>() implies that all of the required non-modifying expressions are valid for T, but the required maybe-modifying expressions are only valid if T is not const. Forcing users to deal with cv-qualifiers and reference types explicitly makes it harder to write generic code, but simultaneously makes it easier to write generic code with fewer errors.

Proposed Resolution

Change the definition of the Booolean concept ([concepts.lib.compare.boolean]/p1) as follows (includes the resolution for #330):

template <class B>
concept bool Boolean() {
-  return MoveConstructible<B>() && // (see 4.5.4)
-    requires(const B b1, const B b2, const bool a) {
-      bool(b1);
-      { b1 } -> bool;
-      bool(!b1);
-      { !b1 } -> bool;
-      { b1 && b2 } -> Same<bool>;
-      { b1 && a } -> Same<bool>;
-      { a && b1 } -> Same<bool>;
-      { b1 || b2 } -> Same<bool>;
-      { b1 || a } -> Same<bool>;
-      { a || b1 } -> Same<bool>;
-      { b1 == b2 } -> bool;
-      { b1 != b2 } -> bool;
-      { b1 == a } -> bool;
-      { a == b1 } -> bool;
-      { b1 != a } -> bool;
-      { a != b1 } -> bool;
+  return Movable<decay_t<B>>() && // (see \ref{concepts.lib.object.movable})
+    requires(const remove_reference_t<B>& b1,
+             const remove_reference_t<B>& b2, const bool a) {
+      { b1 } -> ConvertibleTo<bool>&&;
+      { !b1 } -> ConvertibleTo<bool>&&;
+      { b1 && a } ->  Same<bool>&&;
+      { b1 || a } ->  Same<bool>&&;
+      { b1 && b2 } -> Same<bool>&&;
+      { a && b2  } -> Same<bool>&&;
+      { b1 || b2 } -> Same<bool>&&;
+      { a || b2  } -> Same<bool>&&;
+      { b1 == b2 } -> ConvertibleTo<bool>&&;
+      { b1 == a  } -> ConvertibleTo<bool>&&;
+      { a == b2  } -> ConvertibleTo<bool>&&;
+      { b1 != b2 } -> ConvertibleTo<bool>&&;
+      { b1 != a  } -> ConvertibleTo<bool>&&;
+      { a != b2  } -> ConvertibleTo<bool>&&;
    };
 }

Change [concepts.lib.compare.boolean]/p2 as follows (depends on the resolution of #167):

-2 Given values b1 and b2 of type B, then Boolean<B>() is satisfied if and only if
+2 Given const lvalues b1 and b2 of type remove_reference_t<B>, then
+  Boolean<B>() is satisfied if and only if
-(2.1) — bool(b1) == [](bool x) { return x; }(b1).
 (2.2) — bool(b1) == !bool(!b1).
 (2.3) — (b1 && b2), (b1 && bool(b2)), and (bool(b1) && b2) are all equal to 
         (bool(b1) && bool(b2)), and have the same short-circuit evaluation.
 (2.4) — (b1 || b2), (b1 || bool(b2)), and (bool(b1) || b2) are all equal to
         (bool(b1) || bool(b2)), and have the same short-circuit evaluation.
 (2.5) — bool(b1 == b2), bool(b1 == bool(b2)), and bool(bool(b1) == b2) are
         all equal to (bool(b1) == bool(b2)).
 (2.6) — bool(b1 != b2), bool(b1 != bool(b2)), and bool(bool(b1) != b2) are
         all equal to (bool(b1) != bool(b2)).

Change concept WeaklyEqualityComparable ([concepts.lib.compare.equalitycomparable]) as follows (includes the resolution for #330):

 template <class T, class U>
 concept bool WeaklyEqualityComparable() {
-  return requires(const T& t, const U& u) {
-    { t == u } -> Boolean;
-    { u == t } -> Boolean;
-    { t != u } -> Boolean;
-    { u != t } -> Boolean;
+  return requires(const remove_reference_t<T>& t,
+                  const remove_reference_t<U>& u) {
+    { t == u } -> Boolean&&;
+    { t != u } -> Boolean&&;
+    { u == t } -> Boolean&&;
+    { u != t } -> Boolean&&;
   };
 }

Change [concepts.lib.compare.equalitycomparable]/p1 as follows:

-1 Let t and u be objects of types T and U.
+1 Let t and u be const lvalues of types remove_reference_t<T> and remove_reference_t<U>.
   WeaklyEqualityComparable<T, U>() is satisfied if and only if:
 (1.1) — t == u, u == t, t != u, and u != t have the same domain.
 (1.2) — bool(u == t) == bool(t == u).
 (1.3) — bool(t != u) == !bool(t == u).

Change cross-type concept EqualityComparable ([concepts.lib.compare.equalitycomparable]) as follows (includes the resolution for #330):

 template <class T, class U>
 concept bool EqualityComparable() {
-  return CommonReference<const T&, const U&>() &&
+  return
     EqualityComparable<T>() &&
     EqualityComparable<U>() &&
-    EqualityComparable<
-        remove_cv_t<remove_reference_t<common_reference_t<const T&, const U&>>>>() &&
+    CommonReference<
+      const remove_reference_t<T>&,
+      const remove_reference_t<U>&>() &&
+    EqualityComparable<
+      common_reference_t<
+        const remove_reference_t<T>&,
+        const remove_reference_t<U>&>>() &&
     WeaklyEqualityComparable<T, U>();
 }

Change [concepts.lib.compare.equalitycomparable]/p4 as follows:

-4 Let a be an object of type T, b be an object of type U, and C be
-  common_reference_t<const T&, const U&>.
+4 Let a be a const lvalue of type remove_reference_t<T>, b be a
+  const lvalue of type remove_reference_t<U>, and C be
+  common_reference_t<const remove_reference_t<T>&,
+  const remove_reference_t<U>&>.
   Then EqualityComparable<T, U>() is satisfied if and only if:
 (4.1) — bool(a == b) == bool(C(a) == C(b)).

Change concept StrictTotallyOrdered ([concepts.lib.compare.stricttotallyordered]) as follows (includes the resolution for #330):

 template <class T>
 concept bool StrictTotallyOrdered() {
   return EqualityComparable<T>() &&
-    requires(const T a, const T b) {
+    requires(const remove_reference_t<T>& t,
+             const remove_reference_t<U>& u) {
-      { a < b } -> Boolean;
-      { a > b } -> Boolean;
-      { a <= b } -> Boolean;
-      { a >= b } -> Boolean;
+      { a < b } -> Boolean&&;
+      { a > b } -> Boolean&&;
+      { a <= b } -> Boolean&&;
+      { a >= b } -> Boolean&&;
     };
 }

Change [concepts.lib.compare.stricttotallyordered]/p1 to be:

-1 Let a, b, and c be objects of type T.
+1 Let a, b, and c be const lvalues of type remove_reference_t<T>.
 Then StrictTotallyOrdered<T>() is satisfied if and only if
 (1.1) — Exactly one of bool(a < b), bool(b < a), or bool(a == b) is true.
 (1.2) — If bool(a < b) and bool(b < c), then bool(a < c).
 (1.3) — bool(a > b) == bool(b < a).
 (1.4) — bool(a <= b) == !bool(b < a).
 (1.5) — bool(a >= b) == !bool(a < b).

Change cross-type concept StrictTotallyOrdered ([concepts.lib.compare.stricttotallyordered]) as follows (includes the resolution for #330):

 template <class T, class U>
 concept bool StrictTotallyOrdered() {
-  return CommonReference<const T&, const U&>() &&
+  return
     StrictTotallyOrdered<T>() &&
     StrictTotallyOrdered<U>() &&
-    StrictTotallyOrdered<
-      remove_cv_t<remove_reference_t<common_reference_t<const T&, const U&>>>>() &&
+    CommonReference<
+      const remove_reference_t<T>&,
+      const remove_reference_t<U>&>() &&
+    StrictTotallyOrdered<
+      common_reference_t<
+        const remove_reference_t<T>&,
+        const remove_reference_t<U>&>>() &&
     EqualityComparable<T, U>() &&
-    requires(const T t, const U u) {
+    requires(const remove_reference_t<T>& t,
+             const remove_reference_t<U>& u) {
-      { t < u } -> Boolean;
-      { t > u } -> Boolean;
-      { t <= u } -> Boolean;
-      { t >= u } -> Boolean;
-      { u < t } -> Boolean;
-      { u > t } -> Boolean;
-      { u <= t } -> Boolean;
-      { u >= t } -> Boolean;
+      { t < u } -> Boolean&&;
+      { t > u } -> Boolean&&;
+      { t <= u } -> Boolean&&;
+      { t >= u } -> Boolean&&;
+      { u < t } -> Boolean&&;
+      { u > t } -> Boolean&&;
+      { u <= t } -> Boolean&&;
+      { u >= t } -> Boolean&&;
     };
 }

Change [concepts.lib.compare.stricttotallyordered]/p2 as follows:

-2 Let t be an object of type T, u be an object of type U,
+2 Let t be a const lvalue of type remove_reference_t<T>,
+  u be a const lvalue of type remove_reference_t<U>,
-  and C be common_reference_t<const T&, const U&>.
+  and C be common_reference_t<const remove_reference_t<T>&,
+  const remove_reference_t<U>&>.
   Then StrictTotallyOrdered<T, U>() is satisfied if and only if
 (2.1) — bool(t < u) == bool(C(t) < C(u)).
 (2.2) — bool(t > u) == bool(C(t) > C(u)).
 (2.3) — bool(t <= u) == bool(C(t) <= C(u)).
 (2.4) — bool(t >= u) == bool(C(t) >= C(u)).
 (2.5) — bool(u < t) == bool(C(u) < C(t)).
 (2.6) — bool(u > t) == bool(C(u) > C(t)).
 (2.7) — bool(u <= t) == bool(C(u) <= C(t)).
 (2.8) — bool(u >= t) == bool(C(u) >= C(t)).

Change section "Concept Relation" ([concepts.lib.callable.relation]) as follows:

template <class R, class T, class U>
concept bool Relation() {
  return Relation<R, T>() &&
    Relation<R, U>() &&
-    CommonReference<const T&, const U&>() &&
-    Relation<R,
-      common_reference_t<const T&, const U&>>() &&
+    CommonReference<
+      const remove_reference_t<T>&,
+      const remove_reference_t<U>&>() &&
+    Relation<R,
+      common_reference_t<
+        const remove_reference_t<T>&,
+        const remove_reference_t<U>&>>() &&
    Predicate<R, T, U>() &&
    Predicate<R, U, T>();
}

-1 Let r be any object of type R,
+1 Let r be an expression such that decltype((r)) is R,
-  a be any object of type T,
+  a be an expression such that decltype((a)) is T,
- b be any object of type U,
+  b be an expression such that decltype((b)) is U,
-  and C be common_reference_t<const T&, const U&>.
+  and C be common_reference_t<const remove_reference_t<T>&,
+  const remove_reference_t<U>&>.
  Then Relation<R, T, U>() is satisfied if and only if
(1.1) — bool(r(a, b)) == bool(r(C(a), C(b))).
(1.2) — bool(r(b, a)) == bool(r(C(b), C(a))).

Change "Concept Swappable" ([concepts.lib.corelang.swappable]) as follows:

template <class T>
concept bool Swappable() {
  return requires(T&& a, T&& b) {
    ranges::swap(std::forward<T>(a), std::forward<T>(b));
  };
}

template <class T, class U>
concept bool Swappable() {
  return Swappable<T>() &&
  Swappable<U>() &&
- CommonReference<const T&, const U&>() &&
+ CommonReference<
+   const remove_reference_t<T>&,
+   const remove_reference_t<U>&>() &&
  requires(T&& t, U&& u) {
    ranges::swap(std::forward<T>(t), std::forward<U>(u));
    ranges::swap(std::forward<U>(u), std::forward<T>(t));
  };
}

[ericniebler]

I'll notice that in some sense the issue is worse now in the current draft, which is now internally inconsistent. In WeaklyEqualityComparable, we have requires(const T& a, const T& b), but in StrictWeakOrder we have requires(const T a, const T b). What the wha?

[CaseyCarter]

We didn't understand when first formulating the concepts that the parameter types of requires expressions undergo decay:

template<class T>
concept bool C = requires(T t) {
  t = t;
};
static_assert(C<void(int)>); // Oops; function types are not assignable, but function *pointers* are
static_assert(C<int[42]>); // Oops: array vs pointer-to-element

I've been gradually armoring the concepts against array- and function-to-pointer decay, which I see now was a mistake. I should have made a single global fix.

[ericniebler]

@CaseyCarter I'd like to bump this one up the queue, especially since we're monkeying with the object concepts again.

[ericniebler]

I think we have a handle on this issue now (see P0547R0). @CaseyCarter? Nope, still a problem, looking at EqualityComparable.

[CaseyCarter]

I think we have a handle on this issue now

P0547 brings the 'structible and object concepts into line, absolutely. The Core concepts were already in good shape - Common was the only problem there, really, and it's locked down nicely now that we've revised it a hundred times.

That leaves only the Comparison concepts in question. Should Boolean, EqualityComparable, and StrictTotallyOrdered admit reference types and/or cv-qualified object types?

[ericniebler]

Let's look at a specific example:

template <> struct equal_to<void> {
  template <class T, class U>
    requires EqualityComparable<T, U>()
  constexpr auto operator()(T&& t, U&& u) const
    -> decltype(std::forward<T>(t) == std::forward<U>(u));
  typedef unspecified is_transparent;
};

If EqualityComparable doesn't work with reference types, then this code is wrong. Shall we require EqualityComparable<remove_reference_t<T>, remove_reference_t<U>>()? That's unfortunate.

I'm extremely uncomfortable with concept checks that introduce hard errors. A type should satisfy the concept or not. There is no third option.

I think I would be OK with saying that reference types do not satisfy these concepts. Although it's less convenient, it does avoid potential confusion.

[ericniebler]

P.S. Why does Boolean only require MoveConstructible and not Movable?

[CaseyCarter]

P.S. Why does Boolean only require MoveConstructible and not Movable?

We wanted Boolean to be returnable from a function, and didn't see a need to store them. I think we should either bite the bullet and make Boolean be an object type by requiring Movable, or constrain reference types to work correctly and not modify referents with requires(const remove_reference_t<T>& foo, /**/).

I'm extremely uncomfortable with concept checks that introduce hard errors. A type should satisfy the concept or not. There is no third option.

Hard errors exist to prevent us from doing something stupid when there is no "right" answer:

struct incomplete;
Destructible<incomplete>(); // Should be ill-formed
Assignable<incomplete&, int>(); // Ditto
struct complete { complete() = default; complete(complete const&) = delete; };
Swappable<complete&, complete&>(); // Ok (false)
void swap(complete&, complete&) {}
Swappable<complete&, complete&>(); // Should be Ill-formed NDR

[CaseyCarter]

I think we should either bite the bullet and make Boolean be an object type by requiring Movable, or constrain reference types to work correctly and not modify referents

...which I suppose applies equally well to EqualityComparable and StrictTotallyOrdered, except that we would require is_object directly instead of Movable.

[CaseyCarter]

 template <> struct equal_to<void> {
 template <class T, class U>
   requires EqualityComparable<T, U>()
 constexpr auto operator()(T&& t, U&& u) const
   -> decltype(std::forward<T>(t) == std::forward<U>(u));
 typedef unspecified is_transparent;
};

This is the essential "dangerous scenario" that concerns me: people applying concepts to forwarding references and thinking that means the referent type satisfies the concept. (I've called this "reference confusion" before.) This is what makes it tempting to declare e.g. EqualityComparable ill-formed for reference types, I'd like to catch this kind of programming error.

In the particular case of the comparison concepts, if we make them either require object types or properly strip references, it makes this error impossible: EqualityComparable<foo&, bar&&>() would have the same meaning as EqualityComparable<foo, bar>().

[CaseyCarter]

Right now, I'm convinced that EqualityComparable and StrictTotallyOrdered should "do the right thing" with reference types and not require object types, since they've never had any object-like semantics. I'm on the fence about whether we should require Movable for Boolean; do you see any reason to forbid e.g. int& operator<(T, U)?

[ericniebler]

I could imagine a future time when we want to separate "boolean-testability" from the stronger "behaves like a bool". Then Boolean<T>() == BooleanTestable<T>() && Movable<T>(). So I lean towards the stronger requirement. And to answer your question, I see no particular reason why int& operator<(T, U) should be allowed.

[ericniebler]

I'm making these edits to cmcstl2, and it turned up an issue. IndirectPredicate<bool T::*, T*>() is false because the result of applying the member pointer to the object pointer yields a reference. :-P

[CaseyCarter]

Perhaps instead of allowing reference types to satisfy Boolean, we should decay the result type of comparison functions and predicates?

[ericniebler]

I don't like the implications for the algorithms. Would they have to explicitly DECAY_COPY the result of predicates before testing them? Blech, no.

[CaseyCarter]

We could strip referenceness from the requires expression parameters, and require Movable<decay_t<T>>()?

[ericniebler]

I prefer Movable<remove_reference_t<T>>(). OK yeah, Movable<decay_t<T>>(). That seems best, and it appears to be working in cmcstl2.

[CaseyCarter]

Would they have to explicitly DECAY_COPY the result of predicates before testing them?

No. The comparison concepts require e.g. { t == u } -> Boolean; which requires the type of the expression t == u to satisfy Boolean per N4641 [temp.constr.deduct]/1:

An argument deduction constraint is a constraint that specifies a requirement that the type of an
expression E can be deduced from a type T, when T includes one or more placeholders (7.1.6.4).

The type of t == u has nothing to do with value category, so IIRC it's a bug that cmcstl2 is translating deduction constraints like that into t == u; requires Boolean<decltype(t == u)>(); instead of t == u; requires Boolean<remove_reference_t<decltype(t == u)>>();.

[CaseyCarter]

Still can't distinguish between rvalue-reference types and prvalues, but it's an improvement, no?

I don't think we care to distinguish xvalues from prvalues; it should not matter for our uses.

EDIT:

This is also much better than the replacement E; requires Same<decltype(E), T>(); than I was contemplating, which I think we'll need for GCC6.

EDIT AGAIN: requires Same<decltype(E)&&, T&&>() is closer.

[CaseyCarter]

The PR removes Boolean's requirement that the results of implicit and explicit conversion are equal, but does not state that it assumes that the PR for #167 has been applied. I'd like a (\ref{concepts.lib.object.movable}) for Movable here since that concept hasn't been seen yet, although it's less critical now that there's a synopsis for <experimental/ranges/concepts>.

[ericniebler]

Now Common's add_lvalue_reference_t<const T> in #311 looks odd to me. Should it be add_lvalue_reference<const std::remove_reference_t<T>>?