Bug or arcane orphan rules?

[bascule]

Apologies if this falls under "help" more than an IRLO discussion, but this is weird enough people have suggested filing a bug and I wanted to see if anyone could explain what's happening before I do that.

The following example doesn't work:

https://play.rust-lang.org/?version=stable&mode=debug&edition=2021&gist=cb42d7bc4035e94dd9ff394c4ff79c36

use core::ops::Mul;

// Don't touch this

pub trait Group:
    Sized
    + Mul<Self::Scalar, Output = Self>
    + for<'a> Mul<&'a Self::Scalar, Output = Self>
{
    type Scalar;
}

// Make changes to anything below

pub trait Curve {
    type Scalar;
    type Field;
}

pub struct Point<C: Curve> {
    x: C::Field,
    y: C::Field
}

impl<C: Curve> Group for Point<C> {
    type Scalar = C::Scalar;
}

impl<C: Curve> Mul<C::Scalar> for Point<C> {
    type Output = Self;

    fn mul(self, other: C::Scalar) -> Self {
        unimplemented!()
    }
}

impl<C: Curve> Mul<&C::Scalar> for Point<C> {
    type Output = Self;

    fn mul(self, other: &C::Scalar) -> Self {
        unimplemented!()
    }
}

It fails to typecheck with the following error:

error[E0119]: conflicting implementations of trait `std::ops::Mul<&_>` for type `Point<_>`
  --> src/lib.rs:37:1
   |
29 | impl<C: Curve> Mul<C::Scalar> for Point<C> {
   | ------------------------------------------ first implementation here
...
37 | impl<C: Curve> Mul<&C::Scalar> for Point<C> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `Point<_>`

...but if instead of C::Scalar I use a concrete type like a struct, the Mul impls do not conflict.

The error seems to suggest that an associated type could be its own reference type? I'm quite confused by it. I know that generic parameters of traits are a weird corner case in the orphan rules, but I can't figure out what's happening here.

If I remove the second Mul impl, it quickly becomes clear these two types are distinct:

error[E0271]: type mismatch resolving `for<'a> <C as Curve>::Scalar == &'a <C as Curve>::Scalar`
  --> src/lib.rs:25:16
   |
25 | impl<C: Curve> Group for Point<C> {
   |                ^^^^^ expected associated type, found reference
   |
   = note: expected associated type `<C as Curve>::Scalar`
                    found reference `&'a <C as Curve>::Scalar`
   = help: consider constraining the associated type `<C as Curve>::Scalar` to `&'a <C as Curve>::Scalar`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

Is the original error about overlapping Mul definitions a bug, or expected behavior for some reason?

[steffahn]

I think this is less about the orphan rules themself and more about in which cases the compiler can (or cannot) detect that types cannot be the same. Maybe less of a bug and more of a limitation, arguably?

[CAD97]

The limitation is in fact that the compiler is unable/unwilling to prove that T::Proj != &T::Proj.

Instead, the compiler just looks at two unknown types A and &B, and says that A = &B is valid, thus there's an overlap.

Polonius may resolve this; even if not, resolving this is probably blocked on polonius.

An interesting edge case that could be related:

trait Lie: Group {
}

impl<T> Group for T
where
    T: Lie,
{
    type Scalar = <Self as Group>::Scalar;
}

This passes tyck and only fails when you try to actually use the projection (which is possible by implementing Lie for a type). (I reported an issue for this IIRC but can't grab it atm.)

Trying to use this to generate Scalar = &Scalar

impl<T> Group for T
where
    T: Lie,
    <T as Group>::Scalar: 'static,
{
    type Scalar = &'static <Self as Group>::Scalar;
}

runs into a requirement evaluation overflow.

It's also worth noting that recursive type aliases are explicitly forbidden, so reasoning based on recursive types not existing is probably sound.

[quinedot]

Here's a workaround.

[bascule]

Wow awesome, thanks!