TAIT coherence checks don't ensure composability of crates

[steffahn]

The coherence checks for trait implementations where the receiver type is an opaque type (defined with TAIT) are designed and/or implemented in a way that doesn’t uphold the principle of seamless composability of crates. It also doesn’t uphold current principles of what kind of trait implementation constitutes a breaking change.

---

Here’s a reproducing example (consisting of 3 crates):

crate A

[package]
name = "a"
edition = "2021"

pub trait MyFrom<T> {
    fn from(value: T) -> Self;
}

pub trait AsFoo {}

pub struct Foo;

impl AsFoo for Foo {}

---

crate B

[package]
name = "b"
edition = "2021"

[dependencies]
a = { path = "../a" }

use a::{AsFoo, MyFrom};

pub struct Wrapper<T>(pub T);

impl<T> MyFrom<T> for Wrapper<T> {
    fn from(value: T) -> Self {
        Wrapper(value)
    }
}

impl<T> AsFoo for Wrapper<T> {}

---

crate C

[package]
name = "c"
edition = "2021"

[dependencies]
a = { path = "../a" }
b = { path = "../b" }

#![feature(type_alias_impl_trait)]

use a::{AsFoo, Foo, MyFrom};
// use b; // <- uncomment for error

type Alias = impl AsFoo;

struct Local;

impl MyFrom<Local> for Alias {
    fn from(_: Local) -> Alias {
        Foo
    }
}

---

The above example involving 3 crates A, B, C; A is a dependency of B and C.

C compiles successfully with just A as a dependency. If B is added as a dependency of C (and actually used, by uncommenting the use b;) then the following error appears:

error[E0119]: conflicting implementations of trait `MyFrom<Local>` for type `Wrapper<Local>`
  --> src/lib.rs:10:1
   |
10 | impl MyFrom<Local> for Alias {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: conflicting implementation in crate `b`:
           - impl<T> MyFrom<T> for Wrapper<T>;

The error also does make sense: If we further change crate C, so that the defining use of Alias produces not a Foo but a b::Wrapper<Local>, then the impls of MyFrom will become actually overlapping, even when the opaque type is treated transparently. As far as I can tell, it seems that the goal of the error was to be conservative and ensure that changing the actual concrete choice of type behind the opaque TAIT-type should not introduce any new overlap errors later.

As a consequence, in my opinion this means that without the crate B, there should probably also be some kind of error here.

Some more thoughts and observations:

• the problematic impl<T> MyFrom<T> for Wrapper<T> is a blanket impl. Addition of such an impl is actually considered a breaking change in other kinds of situations
  • when such an impl is added for a type Wrapper<T> that already exists in previous versions, that’s considered technically breaking
  • however, if it’s introduced together with the type Wrapper<T>, that it okay; and it’s exactly this combination that “add trait B as dependency” achieves
• the problematic impl<T> MyFrom<T> for Wrapper<T> produces the same error if crates A and B are combined into one. I split them up, because it makes an even stronger argument; nonetheless, common “what’s considered breaking” standards imply that crate A should of course also be allowed to simply add such a pair of struct Wrapper<T> + this impl of MyFrom, and this issue violates that principle, too.
• I first noticed this issue in this code example, where some trait impls involving local traits and types, as well as From and AsRef<str> results in an error mention that surprisingly mentions random stuff such as gimli::common::DebugFrameOffset [presumably because it’s the first type the compiler finds that has some kind of From<T> for Self<T>-style implementation]. If nothing else that’s a surprising diagnostic, but unsurprisingly is just highlighted this more abstract&general issue with coherence-checks.
• I have not tried reasoning more deeply about what kind of “orphan rules” a TAIT needs to fulfill to avoid this issue completely, but I wouldn’t be surprised if there are some straightforward ways of giving TAITs a more restrictive version of the orphan rules, which solve this issue.

@rustbot label +F-type_alias_impl_trait +A-coherence +A-traits +T-types

[lcnr]

may be fixed by new solver, cc https://github.com/rust-lang/rust/issues/99554

[lcnr]

So this can actually not be unsound, it's only an issue of composability.

• as long as C doesnt import B, the opaque type cannot refer to Wrapper
• once C refers to B, we get an error

I believe this is a general issue with ambiguous aliases. Should affect specialization as well. We should always treat aliases which cannot be normalized as potentially uncovered ty params.

[lcnr]

I believe that the fix for this is 8244d7ae1996f0cf848ea507ed818d400250fa1c. However, this means that the coherence failure for the following now wants to talk about an "uncovered type parameter" even though there isn't any inference variable involved.

// crate a
trait Trait {}

// crate b
#![feature(type_alias_impl_trait)]
type Alias = impl Sized;
fn define() -> Alias { SomeForeignType }
impl a::Trait for Alias {}

This then ICEs here https://github.com/rust-lang/rust/blob/de19f2b73d4fd456be06f299a5d9d8fd622ca298/compiler/rustc_hir_analysis/src/coherence/orphan.rs#L350 and the diagnostics code generally doesn't handle this yet.

I would love for someone else to pick this up and handle the necessary diagnostics changes, though I may look into this myself in a few months once I've got the time