Fully generalize cmp instances

[aturon]

With cmp/ops reform, all of the comparison traits allow the types of the two sides to differ. However, the traits provide a default type for the right-hand size that is the same as the left-hand side. Thus, an impl like:

impl<T: PartialEq> PartialEq for Rc<T> { ... }

is more limited than it needs to be; it could instead be

impl<U, T: PartialEq<U>> PartialEq<Rc<U>> for Rc<T> { ... }

(Of course, you could imagine being even more general than that, allowing Rc values to be compared to other values.)

The various impls in the standard library should probably be generalized along these lines; currently a few are but most aren't.

[aturon]

cc @japaric @alexcrichton

I don't think we need to do this prior to stabilization, since we can always safely generalize in the future. I'd also like to put some thought into how general we want to make things, but the example above seems like a good minimum.

[aturon]

A bit of follow up: I'm seeing some cases where e.g. the PartialEq implementation has been generalized like the above, but the Eq hasn't.

[steveklabnik]

What's the status of this with #20065 merged?

[steveklabnik]

I am guessing the status is that it's done, so I'm giving it a close. Let me know if there's anything specific still missing.

[aturon]

@steveklabnik No, this hasn't been done yet. Basically it would require a sweep through all existing impls to generalize them.

I'm not sure where you want to track tickets like this. It's generally backwards compatible to make these changes, and not exactly high priority, but something nice for expressiveness and consistency (and definitely does not require an RFC).

[steveklabnik]

Yeah, it's hard because it's not directly actionable, it's more like 'double check all these things.' It'd be nice if we had an actual list.

[japaric]

I think the following command gives you a "Good Enough" list of implementations of PartialEq<Rhs=Self> on types that have generic parameters:

rustc -Z unstable-options --pretty=expanded libcore/lib.rs | grep 'impl <.*PartialEq '

Example output on liballoc:

    impl <T: ?Sized + PartialEq> PartialEq for Box<T> {
    impl <T: PartialEq> PartialEq for Arc<T> {
    impl <T: PartialEq> PartialEq for Rc<T> {

After running that command on every crate, and filtering out types that only have lifetime parameters like CovariantLifetime<'a>, I ended up with the following list:

liballoc
  - Arc<T>
  - Box<T>
  - Rc<T>
libcollections
  - BTreeMap<K, V>
  - BTreeSet<T>
  - DList<A>
  - EnumSet<E>
  - RingBuf<A>
  - VecMap<V>
libcore
  - (A, B)
  - (A, B, C)
  - (A, B, C, D)
  - (A, B, C, D, E)
  - (A, B, C, D, E, F)
  - (A, B, C, D, E, F, G)
  - (A, B, C, D, E, F, G, H)
  - (A, B, C, D, E, F, G, H, I)
  - (A, B, C, D, E, F, G, H, I, J)
  - (A, B, C, D, E, F, G, H, I, J, K)
  - (A, B, C, D, E, F, G, H, I, J, K, L)
  - (A,)
  - *const T
  - *mut T
  - Cell<T>
  - ContravariantType<T>
  - CovariantType<T>
  - InvariantType<T>
  - MinMaxResult<T>
  - NonZero<T>
  - Option<T>
  - PhantomData<T>
  - Range<Idx>
  - RangeFrom<Idx>
  - RangeTo<Idx>
  - RefCell<T>
  - Result<T, E>
  - extern "C" fn() -> _R
  - extern "C" fn(A) -> _R
  - extern "C" fn(A, B) -> _R
  - extern "C" fn(A, B, C) -> _R
  - extern "C" fn(A, B, C, D) -> _R
  - extern "C" fn(A, B, C, D, E) -> _R
librustc
  - Binder<T>
  - Obligation<'tcx, T>
  - OutlivesPredicate<A, B>
  - TrackMatchMode<T>
  - VarValueKey<K>
  - VecPerParamSpace<K>
  - VtableImplData<'tcx, N>
libstd
  - HashMap<K, V, S>
  - HashSet<T, S>
  - SendError<T>
  - TrySendError<T>
libsyntax
  - OwnedSlice<T>
  - P<T>
  - Spanned<T>
libtest
  - Summary<T>

I'll let @aturon pick the subset that would be nice to have for 1.0 (Option, Result, the smart pointers, the tuples?). Also, I don't think generalizing all of them actually makes sense.

Disclaimer: This list is not exhaustive, because some lines got wrapped around by the pretty printer and the grep expression expects a single line match.

[aturon]

@japaric Sorry for the delay, this comment was buried in my inbox (and I was away on vacation).

Anyway:

Option, Result, the smart pointers, the tuples?

That makes good sense to me as a 1.0 starting point, and I certainly agree that not all of the listed types should get this treatment.

[shepmaster]

cc #20927

[shepmaster]

I took a shot at just implementing this manually for Option. Unfortunately, it immediately runs into ambiguous types:

src/libsyntax/attr.rs:455:12: 455:27 error: unable to infer enough type information about `_`; type annotations required [E0282]
src/libsyntax/attr.rs:455         if feature == None && tag != "deprecated" {
                                     ^~~~~~~~~~~~~~~

I feel like there should be a nicer solution here. I'm pretty sure that adding type annotations to every None in existence is not going to play out well 😸 .

[huonw]

Argh! Sounds like it may not be possible to generalise. :(

[huonw]

It seems type parameter defaults may help to solve the issue @shepmaster met:

#![feature(default_type_parameter_fallback)]

enum Maybe<T> { Nothing, Just(T) }
use Maybe::*;

impl<T, U = T> PartialEq<Maybe<U>> for Maybe<T>
    where T: PartialEq<U>
{
    fn eq(&self, other: &Maybe<U>) -> bool {
        match (self, other) {
            (&Nothing, &Nothing) => true,
            (&Just(ref a), &Just(ref b)) => a == b,
            _ => false,
        }
    }
}

fn main() {
    println!("{}", Nothing == Just("foo"));

    println!("{}", Just("foo") == Nothing);
}

Without the default, both println!s fail to compile, but with the U = T default Just("foo") == Nothing works, and with T = U as the default Nothing == Just("foo") works. It doesn't seem possible to get both to work (e.g. T = U, U = T doesn't work).

[withoutboats]

How frustrating (and interesting!). Is it possible to improve default type parameters to allow mutual identity defaults?

[jroesch]

You aren't currently allowed to forward declare defaults, we might be able to lift that requirement having both be equal should just give you this set of equalities:

$0 = U,
$1 = T,
$1 = $0

[jroesch]

I'm up late working on a paper and this thought came to mind, you can encode a cute little trait trick in order to apply a secondary default:

#![feature(default_type_parameter_fallback)]

enum Maybe<T> { Nothing, Just(T) }
use Maybe::*;

trait DefaultTo<Ty, Default> {}
impl<T, U=T> DefaultTo<U, T> for () {}

impl<U, T = U> PartialEq<Maybe<U>> for Maybe<T>
    where T: PartialEq<U>,
          (): DefaultTo<U, T>
{
    fn eq(&self, other: &Maybe<U>) -> bool {
        match (self, other) {
            (&Nothing, &Nothing) => true,
            (&Just(ref a), &Just(ref b)) => a == b,
            _ => false,
        }
    }
}

fn main() {
    println!("{}", PartialEq::eq(&Nothing, &Just("foo")));

    println!("{}", PartialEq::eq(&Just("foo"), &Nothing));
}