Hi Lénárd,

equality_comparable_with<T, U> has to strike a line somewhere between leaving out types with an operator==(T, U) that is an actual equality and including types with an operator==(T, U) which is not equality. Stripping the CR requirements in favor of semantic-only requirements is skipping drawing the line down the middle, instead including all types with an operator==(T, U) or else leaving out all types which don't explicitly opt-in. The issue is that we use operator== as something other than equality all the time. Iterator-sentinels throughout the standard library are a prime example. We use operator== in places that very much feel like equality all the time, yet they aren't actually equality. When writing a heterogeneous operator==, we aren't thinking, "I'm writing an operator==(T, U). I'd better first stop to prove that this is actually mathematically an equality," especially because the proof involves at least all three of operator==(T, U), operator==(T, T), and operator==(U, U).

Take the iterator-sentinel example: this truly feels like an equality. Conceptually, the sentinel either is the last iterator in the range for a finite range, or else it is the limit of the iterators. So we naturally feel like operator==(iterator, sentinel) is an equality, and it probably is if all instances of the iterator type were in the same singular range. The issue is that we are forgetting about operator==(iterator, iterator), allowing us to end up with it1 == sentinel and it2 == sentinel, but it1 != it2. We could say, "Oh, but those are just equivalence classes with it1 and it2 belonging to the same equivalence class called 'end of range'." But if they are to belong to the same equivalence class, then we'd need to make it1 == it2 true, that is make operator==(iterator, iterator) actually just "are these iterators both at the end or both not at the end?" That's problematic.

It's very easy to think of the operator==(T, U) as always comparing one object from T and one object from U, as that's what the operator says it's doing. However, when considering an equality, it's just as important to consider operator==(T, T) and operator==(U, U); all three of these operator==s must be part of the same "equality" operation for this set of operator==s to actually be equality. The CR requirements capture this.

Thanks,
Justin

On Sun, Jun 13, 2021 at 2:39 AM Lénárd Szolnoki via Std-Proposals <std-proposals@lists.isocpp.org> wrote:
Hi,

I don't think we even need a common reference either. Is the common
type commonly used by function templates requiring
equality_comparable_with?

I still think that there is a strong motivation for specifying "strong
equality" between different types, but I don't think it requires any
kind of common type. I think the following semantic requirements would
do the trick:

For t1. t2 of type T and u1, u2 of type U:
* If `t1 == u1` and `t2 == u1` then t1 and t2 are substitutable.
* If `u1 == t1` and `u2 == t1` then u1 and u2 are substitutable.

Substitutable: http://eel.is/c++draft/cmp.categories#pre-4

Maybe it makes sense to give a name to only one side of the requirement
here too.

Some previous discussion here:
https://groups.google.com/a/isocpp.org/g/std-proposals/c/_dBzUrC7FDc/m/_Wj8tbpSBgAJ

Cheers,
Lénárd

On Sat, 12 Jun 2021 14:37:00 -0500
Barry Revzin via Std-Proposals <std-proposals@lists.isocpp.org> wrote:

> Hey Justin,
>
> I find this pretty compelling. So in short,
> equality_comparable_with<T, U> (among other things) both requires
> that a common reference exists (I'll call this type CR) but also that
> T and U are both convertible to CR, and what you're proposing here is
> to keep all the requirements the same, still require that CR exists
> as a type, but instead only require that T and U are both convertible
> to CR const&?
>
> To me, that seems like it still completely satisfies the design
> intent of the model (we still have semantic meaning for the quality
> between T and U) while simply allowing non-copyable types to work.
> And unique_ptr<T> == nullptr_t does very much seem semantically sound
> to me. But I am not somebody that has ever really understood common
> reference, so I'm CCing the three people that do.
>
> Barry
>
> On Fri, Jun 11, 2021 at 12:58 AM Justin Bassett via Std-Proposals <
> std-proposals@lists.isocpp.org> wrote:
>
> > Hello,
> >
> > *Summary:* std::equality_comparable_with should be extended to
> > support more types that have a heterogeneous equality, specifically
> > types which are move-only or are otherwise burned by one particular
> > aspect of the common reference requirements.
> >
> > *Background: *std::equality_comparable_with<T, U> checks that const
> > T& and const U& are both convertible to their
> > std::equality_comparable common reference. This requirement is
> > because we want std::equality_comparable_with to specify equality
> > rather than any number of things that are not equality (e.g.
> > iterator/sentinel "equality", DSLs). However, this requirement is
> > too strict, and I believe we can do better.
> >
> > https://stackoverflow.com/q/66937947/1896169 is relevant and why
> > I've been thinking about this; it shows that
> > std::equality_comparable_with<std::unique_ptr<T>, std::nullptr_t>
> > is false, even though the heterogenous operator== is in fact an
> > actual equality.
> >
> > Why we have the common-reference requirement: cross-type equality
> > isn't mathematically rigorously defined (see
> > https://wg21.link/n3351 pages 15-16). When we write operator==(T,
> > U) as an equality operator, what we are actually saying is that
> > there is some common super-type of T and U under which this
> > operator== is an equality. This is what
> > std::equality_comparable_with attempts to encode. We don't actually
> > need to convert to this common supertype to do t == u; we just need
> > the heterogeneous operator== to be equivalent to the supertype's
> > operator==.
> >
> > *Proposal: *I believe the common *reference *requirement is too
> > strict. Mathematically, a "reference" is meaningless. All we
> > actually need is a common "supertype." This is important, because
> > sometimes std::common_reference<const T&, const U&> is a
> > non-reference V, such as with the unique_ptr<T>-nullptr_t case,
> > where it is unique_ptr<T>. By specifying equality_comparable_with
> > to require a common *reference*, we end up requiring that
> > unique_ptr<T> is copyable (const unique_ptr<T>& must be convertible
> > to unique_ptr<T>). In this case and many other similar cases with a
> > heterogeneous operator== that means equality, we can capture this
> > equality with equality_comparable_with if change the
> > convertible_to<const T&, common_reference_t<const T&, const U&>> to
> > allow const T& to be the same type as common_reference_t<const T&,
> > const U&> after stripping cvref.
> >
> > This does mean that it will become very difficult to express an
> > equals() function in terms of the supertype operator==, but the
> > point of the supertype operator== requirement is that it exists,
> > not that it will be used.
> >
> > In the code form that I believe captures this (quoting my answer to
> > that stackoverflow question):
> > 
> >> template <class T, class U>concept equality_comparable_with =
> >>   __WeaklyEqualityComparableWith<T, U> &&
> >>   std::equality_comparable<T> &&
> >>   std::equality_comparable<U> &&
> >>   std::equality_comparable<
> >>     std::common_reference_t<
> >>       const std::remove_reference_t<T>&,
> >>       const std::remove_reference_t<U>&>> &&
> >>   __CommonSupertypeWith< // not necessarily a reference anymore
> >>     const std::remove_reference_t<T>&,
> >>     const std::remove_reference_t<U>&>;
> >> template <class T, class U>concept __CommonSupertypeWith =
> >>   std::same_as<std::common_reference_t<T, U>,
> >> std::common_reference_t<U, T>> && std::convertible_to<T, const
> >> std::common_reference_t<T, U>&> && std::convertible_to<U, const
> >> std::common_reference_t<T, U>&>;
> >>
> >> *"Diff":* 
> >
> > Changes this: std::common_reference_with<const
> > remove_reference_t<T>&, const remove_reference_t<U>&>
> > To this: __CommonSupertypeWith<const remove_reference_t<T>&, const
> > remove_reference_t<U>&>
> >
> > Which __CommonSupertypeWith is the same as common_reference_with,
> > except we specify the convertibility to the common_reference_t as
> > convertibility to const (common-reference)& instead of
> > (common-reference).
> >
> >
> > *Other thoughts:*
> > I have other thoughts regarding equality_comparable_with, namely
> > that I think it should be possible to opt-in to
> > equality_comparable_with without hijacking common_reference_t for
> > your type, which is problematic because common_reference_t is not
> > exclusive to equality_comparable_with. That is, I think there
> > should be an explicit customization point to declare "MyType's
> > heterogeneous operator== is actually equality and isn't just using
> > the '==' syntax." However, I don't feel as strongly about this.
> >
> > Thanks,
> > Justin Bassett
> > --
> > Std-Proposals mailing list
> > Std-Proposals@lists.isocpp.org
> > https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals
> > 

--
Std-Proposals mailing list
Std-Proposals@lists.isocpp.org
https://lists.isocpp.org/mailman/listinfo.cgi/std-proposals