Trait argument from associated type has conflicting impl

[conradludgate]

I tried this code:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=5a6bc60775d41ce5ef3ff9656d489c51

#![feature(try_trait_v2)]
struct Flip<T>(T);
impl<T> std::ops::FromResidual<Flip<T>> for Option<T>
{
    fn from_residual(residual: Flip<T>) -> Self {
        Some(residual.0)
    }
}

I expected to see this happen: Code compiles successfully

Instead, this happened:

error[[E0119]](https://doc.rust-lang.org/nightly/error-index.html#E0119): conflicting implementations of trait `std::ops::FromResidual<Flip<_>>` for type `std::option::Option<_>`
 --> src/lib.rs:3:1
  |
3 | impl<T> std::ops::FromResidual<Flip<T>> for Option<T>
  | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: conflicting implementation in crate `core`:
          - impl<T> FromResidual for Option<T>;

As you you see, the stdlib has

impl<T> FromResidual for Option<T> {}

Which makes use of a default type arg on FromResidual - <Self as Try>::Residual. For Option<T>, that is Option<Infallible>.

So apparently, FromResidual<Option<Infallible>> conflicts with FromResidual<Flip<T>>.

Playing devil's advocate, we could assume that FromResidual is being conservative with its conflicts because Try::Residual could change, but it could never change to a type I own.

Meta

rustc --version --verbose:

rustc 1.64.0-nightly (3924dac7b 2022-07-29)
binary: rustc
commit-hash: 3924dac7bb29bc8eb348059c901e8f912399c857
commit-date: 2022-07-29
host: aarch64-apple-darwin
release: 1.64.0-nightly
LLVM version: 14.0.6

[conradludgate]

I want this to focus away from FromResidual and more towards the type conflicts. FromResidual is just the first trait I found with this behaviour. I believe this would affect other traits too.

Also note, this requires a crate boundary. core already implements both

impl<T> ops::FromResidual for Option<T> {}
impl<T> ops::FromResidual<ops::Yeet<()>> for Option<T> {}

which is exactly what I'm trying to accomplish - just that it's conflicting in my crate

[conradludgate]

It was suggested that this might be due to the generic Flip<T>, but I get the same error when non-generic:

#![feature(try_trait_v2)]
struct Flip;
impl<T> std::ops::FromResidual<Flip> for Option<T>
{
    fn from_residual(residual: Flip) -> Self {
        None
    }
}

[lcnr]

minimization

// crate `dep`
pub trait Assoc {
    type Ty;
}
impl Assoc for () {
    type Ty = ();
}

pub trait Trait {}
impl Trait for <() as Assoc>::Ty {} // err
// impl Trait for () {} // ok

// local crate
struct LocalTy;
impl dep::Trait for LocalTy {}

results in

error[E0119]: conflicting implementations of trait `Trait<()>` for type `()`
  --> dep/src/lib.rs:10:1
   |
9  | impl Trait<<() as Assoc>::Ty> for () {} // err
   | ------------------------------------ first implementation here
10 | impl Trait<()> for () {}
   | ^^^^^^^^^^^^^^^^^^^^^ conflicting implementation for `()`

this is a language/compiler bug. we're missing a normalization during coherence¹, cc @rust-lang/types

Footnotes

1. ofc it's more complicated than this, see the next comment ↩

[lcnr]

normalizing the trait refs during coherence we end up with the obligation <() as Assoc>::Ty == LocalTy which should result in an error, proving that these two impls cannot overlap. To check that this obligation holds, we have to normalize <() as Assoc>::Ty.

For this we try to get the impl candidate for (): Assoc.

rust/compiler/rustc_trait_selection/src/traits/project.rs

Line 1402 in c9e134e

let impl_source = match selcx.select(&trait_obligation) {

This should succeed, but instead gets converted to ambiguity as the is_knowable check fails:

rust/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs

Line 78 in c9e134e

if let Some(conflict) = self.is_knowable(stack) {

We currently always convert trait obligations to ambiguity if either an upstream or downstream crate may implement that trait ref in the future. Most of the time, that is fine as coherence only checks whether some obligation definitely does not hold. So if some obligations get downgraded from success to ambiguity, this doesn't matter.

The only time where that matters is if this obligation succeeding may cause another obligation to fail. This is the case when checking projection predicates.

I think the correct fix here is to move the intercrate field into the InferCtxt. While that isn't perfect, as ideally the inference context shouldn't need to know about trait solving, there isn't any place which only sometimes wants to use intercrate mode, so it being part of the InferCtxt is a lot safer than trying to thread it into every fulfillment context. This is the same reasoning as in #99501

[lcnr]

going to look into this at some point after rustconf

@rustbot claim

[lcnr]

another case where normalization being ambiguous prevents a later error is

// dep
pub trait Assoc {
    type Ty;
}
impl Assoc for () {
    type Ty = ();
}

// local crate
trait Trait {}

impl Trait for <() as dep::Assoc>::Ty {} // err

trait Bar {}
impl<T: Bar> Trait for T {} // this errors, but we know that `(): Bar` does not hold.

unlike the first case, this one is order dependent as T: Bar remains ambiguous until we've normalized () as dep::Assoc>::Ty. Afaik to correctly fix this we have to stop using predicate_may_hold but instead have to use a proper fulfillment context

rust/compiler/rustc_trait_selection/src/traits/coherence.rs

Line 279 in c9e134e

.find(|o| !selcx.predicate_may_hold_fatal(o));

[b-naber]

normalizing the trait refs during coherence we end up with the obligation <() as Assoc>::Ty == LocalTy which should result in an error, proving that these two impls cannot overlap. To check that this obligation holds, we have to normalize <() as Assoc>::Ty.

For this we try to get the impl candidate for (): Assoc.

rust/compiler/rustc_trait_selection/src/traits/project.rs

Line 1402 in c9e134e

let impl_source = match selcx.select(&trait_obligation) {

This should succeed, but instead gets converted to ambiguity as the is_knowable check fails:

rust/compiler/rustc_trait_selection/src/traits/select/candidate_assembly.rs

Line 78 in c9e134e

if let Some(conflict) = self.is_knowable(stack) {

We currently always convert trait obligations to ambiguity if either an upstream or downstream crate may implement that trait ref in the future. Most of the time, that is fine as coherence only checks whether some obligation definitely does not hold. So if some obligations get downgraded from success to ambiguity, this doesn't matter.

The only time where that matters is if this obligation succeeding may cause another obligation to fail. This is the case when checking projection predicates.

I think the correct fix here is to move the intercrate field into the InferCtxt. While that isn't perfect, as ideally the inference context shouldn't need to know about trait solving, there isn't any place which only sometimes wants to use intercrate mode, so it being part of the InferCtxt is a lot safer than trying to thread it into every fulfillment context. This is the same reasoning as in #99501

Not sure how similar this is to your approach, but I previously tried to fix this by changing the intercrate flag and got errors during a bors run, which I wasn't able to solve: #86360