Proposal: compare `Rc<T>` and `Arc<T>` by &T

[wx-csy]

Summary

Change the behavior of Rc<T>::{partial_cmp, cmp, eq, hash} by calling respective methods on &T, instead of T.

Motivation

Currently, I am implementing a library that allows users to mark a type ByPtr. It overrides the default implementations of PartialOrd<&T>, Ord, PartialEq<&T>, Eq and Hash for &T (thanks to &T being fundamental) to compare and hash the references by address (rather than the default by-inner-value behavior), pretty much like objects in Java and Python.

(The rationale that I chose to override traits for &T, but not T, is that by-address impl of traits for T violates the contract of several commonly used collections, e.g. HashSet, which requires the hash value doesn't change as the object moves. Impl for &T doesn't have this issue.)

However, smart pointers to these types are incomparable, as the current implementation calls the respective methods on their inner values. I think that it can be relaxed to calling the respective methods on &T.

Note that the change is a true relaxation: old code that compiles still compiles with the identical semantics. This is because by definition of &T: PartialOrd where T: PartialOrd (in core::cmp), T: PartialOrd implies &T: PartialOrd, and comparing &T is effectively comparing the inner value in such case.

(please correct me if I made any mistakes)

Proposed Change

The current implementations of PartialOrd for Rc<T: ?Sized + PartialOrd> is:

    fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
        (**self).partial_cmp(&**other)
    }

we may change it as:

impl<T: ?Sized> PartialOrd for Rc<T> 
    where for<'a> &'a T: PartialOrd<&'a T>
{
    fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
        (&**self).partial_cmp(&&**other)
    }
}

(thanks to HRTB)

and likewise for Ord, PartialEq, Eq and Hash, and those of Arc.

Alternative methods

1. provide a separate version of smart pointers for ByPtr types.
2. use wrapper types like ByAddress.

[steffahn]

@wx-csy

Currently, I am implementing a library that allows users to mark a type ByPtr . It overrides the default implementations of PartialOrd<&T> , Ord<&T> , PartialEq<&T> , Eq<&T> and Hash<&T> (thanks to &T being fundamental) to compare and hash the references by address (rather than the default by-inner-value behavior), pretty much like objects in Java and Python.

Can you elaborate on this? As far as I understand you are defining some local type(s), say Foo, and then you are implementing PartialEq for &Foo by comparing addresses. So Foo: PartialEq is not satisfied, but &Foo: PartialEq is. But why don’t you just implement PartialEq for Foo? The methods take references anyways.

---

Also I haven’t thought it through 100% but I believe that your proposed implementation doesn’t even work:

@wx-csy

The current implementations of PartialOrd for Rc<T: ?Sized + PartialOrd> is:

    fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
        (**self).partial_cmp(&**other)
    }

we may change it as:

impl<T: ?Sized> PartialOrd for Rc<T> 
    where for<'a> &'a T: PartialOrd<&'a T>
{
    fn partial_cmp(&self, other: &Rc<T>) -> Option<Ordering> {
        (*self).partial_cmp(&*other)
    }
}

In the current implementation, you have other: &Rc<T>, so *other: Rc<T> and **other: T, and finally &**other: &T. This means that you would get &*other: &Rc<T>, not &&T, which is what you would have to pass to partial_cmp of a PartialOrd implementation for &T. Instead you would probably have to use &&**other: &&T, i.e. something like PartialOrd::partial_cmp(&&**self, &&**other) [or (&**self).partial_cmp(&&**other)].

[hyeonu]

@wx-csy

I am implementing a library that allows users to mark a type ByPtr . It overrides the default implementations of PartialOrd<&T> , Ord<&T> , PartialEq<&T> , Eq<&T> and Hash<&T> (thanks to &T being fundamental) to compare and hash the references by address (rather than the default by-inner-value behavior)

&'_ T impls Borrow<T>, which has some requirements how it should impl such traits.

Further, when providing implementations for additional traits, it needs to be considered whether they should behave identical to those of the underlying type as a consequence of acting as a representation of that underlying type. Generic code typically uses Borrow<T> when it relies on the identical behavior of these additional trait implementations. These traits will likely appear as additional trait bounds.

In particular Eq , Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y .

Borrow in std::borrow - Rust

[wx-csy]

@steffahn

Can you elaborate on this? As far as I understand you are defining some local type(s), say Foo , and then you are implementing PartialEq for &Foo by comparing addresses. So Foo: PartialEq is not satisfied, but &Foo: PartialEq is. But why don’t you just implement PartialEq for Foo ? The methods take references anyways.

The short answer is, implementing PartialEq for Foo violates the semantic requirements for some collections e.g. HashSet. Logically speaking, we are comparing the references rather than the objects per se.

---

@steffahn

Also I haven’t thought it through 100% but I believe that your proposed implementation doesn’t even work:

Thank you for pointing out that. It's fixed now.

[wx-csy]

@hyeonu

&'_ T impls Borrow<T> , which has some requirements how it should impl such traits.

Borrow<T> for &T is effectively a no-op: it takes &T and then returns &T. So these requirements are trivially satisfied, right?

[hyeonu]

Implementation doesn't matter. Since the impl<T> Borrow<T> for &'_ T exist impl Hash for &'_ T should behave identically with impl Hash for T and so on. Otherwise it's a breach of contract, totally not an UB though.

Anyway why do you want to overrides the implementation for the reference type? All those traits operate on &self, which is a reference.

[wx-csy]

@hyeonu

Implementation doesn't matter. Since the impl<T> Borrow<T> for &'_ T exist impl Hash for &'_ T should behave identically with impl Hash for T and so on. Otherwise it's a breach of contract, totally not an UB though.

A custom Hash trait impl for &T cannot coexist with Hash impl for T; otherwise, there is a conflict on Hash impl for &T. So I don't think this will ever happen.

---

@hyeonu

Anyway why do you want to overrides the implementation for the reference type? All those traits operate on &self , which is a reference.

See:

@wx-csy

(The rationale that I chose to override traits for &T , but not T , is that by-address impl of traits for T violates the contract of several commonly used collections, e.g. HashSet , which requires the hash value doesn't change as the object moves. Impl for &T doesn't have this issue.)

[hyeonu]

@wx-csy

A custom Hash trait impl for &T cannot coexist with Hash impl for T ;

Um, wasn't it what you said you've made?

[mbrubeck]

In @wx-csy's code, &T implements Hash but T does not.

The Borrow contract can only be violated if both types implemented Hash. It's actually impossible to create implementations for T and &T that violate the contract, because of the generic impl in std.

[steffahn]

@wx-csy

The short answer is, implementing PartialEq for Foo violates the semantic requirements for some collections e.g. HashSet .

Wouldn't this perhaps just be an argument against using such a type Foo directly (without indirection) in a HashMap? Similar to how it is probably a bad idea to put a RefCell into a BTreeMap. I think the Ord implementation alone should not be problematic. Admitted, it might still be too confusing to have a type implement Hash without supporting it in a HashMap.