occurs check with aliases results in error, not ambiguity

[lcnr]

edit: this issue has been partially fixed in #117088, so any remaining incompleteness (and therefore incorrectly accepted overlap) is a lot harder to trigger. See rust-lang/trait-system-refactor-initiative#8 for a list of known issues with generalization. Keeping this issue open as is to track this, but we should try to write a test which relies on one of the other problems of that issue, now that the problem case 2 has been fixed.

---

// Using the higher ranked projection hack to prevent us from replacing the projection
// with an inference variable.
trait ToUnit<'a> {
    type Unit;
}

struct LocalTy;
impl<'a> ToUnit<'a> for *const LocalTy {
    type Unit = ();
}

impl<'a, T: Copy + ?Sized> ToUnit<'a> for *const T {
    type Unit = ();
}

trait Overlap<T> {
    type Assoc;
}

type Assoc<'a, T> = <*const T as ToUnit<'a>>::Unit;

impl<T> Overlap<T> for T {
    type Assoc = usize;
}

impl<T> Overlap<for<'a> fn(&'a (), Assoc<'a, T>)> for T
where
    for<'a> *const T: ToUnit<'a>,
{
    type Assoc = Box<usize>;
}

fn foo<T: Overlap<U>, U>(x: T::Assoc) -> T::Assoc {
    x
}

fn main() {
    foo::<for<'a> fn(&'a (), ()), for<'a> fn(&'a (), ())>(3usize);
}

for<'a> fn(&'a (), ())>: Overlap<for<'a> fn(&'a (), ())>> can be satisfied using both impls, ignoring a deficiency of the current normalization routine which means that right now the second impl pretty much never applies.

Currently inference constraints from equating the self type are not used to normalize the trait argument so we fail when equating () with Assoc<'a, for<'a> fn(&'a (), ())> even those these two are the same type. This will change once deferred projection equality is implemented.

why this currently passes coherence

Coherence does a pairwise check for all relevant impls. It starts by instantiating the impl parameters with inference vars and equating the impl headers. When we do that with Overlap<T> for T and Overlap<for<'a> fn(&'a (), Assoc<'a, T>)> for T we have:

• eq(?0: Overflap<?0>, ?1: Overlap<for<'a> fn(&'a (), <*const ?1 as ToUnit<'a>>::Unit)>)
  • eq(?0, ?1) constrains ?1 to be equal to ?0
  • eq(?0, for<'a> fn(&'a (), <*const ?0 as ToUnit<'a>>::Unit)>): this now fails the occurs check

The occurs check is necessary to prevent ourselves from creating infinitely large types, e.g. ?0 = Vec<?0>. But it does mean that coherence considers these two impls to be disjoint. Because the inference var only occurs inside of a projection, there's a way to equate these two types without resulting in an infinitely large type by normalizing the projection.

[compiler-errors]

Should we just consider CyclicTy type errors during impl header equation to be ambiguous? I can work on that if so.

Not sure if this needs more nuanced check, though.

[lcnr]

this can be changed to result in actual overlap on stable by splitting stuff over multiple crates:

// crate a;
pub trait ToUnit<'a, U> {
    type Unit;
}

pub trait Overlap<T> {
    type Assoc;
}

type Assoc<'a, T, U> = <&'static T as ToUnit<'a, U>>::Unit;

impl<T, U> Overlap<T> for (T, U) {
    type Assoc = usize;
}

// coherence does not detect overlap between these two impls as the occurs
// check fails during unification
impl<T, U> Overlap<for<'a> fn(&'a (), Assoc<'a, T, U>)> for (T, U)
where
    for<'a> &'static T: ToUnit<'a, U>,
{
    type Assoc = Box<usize>;
}

pub fn foo<T: Overlap<U>, U>(x: T::Assoc) -> T::Assoc {
    x
}

// crate b
use a::*;

struct LocalTy;
impl<'b> ToUnit<'b, LocalTy> for &'static for<'c> fn(&'c (), ())  {
    type Unit = ();
}

fn main() {
    foo::<(for<'a> fn(&'a (), ()), LocalTy), for<'a> fn(&'a (), ())>(1);
}

results in

error[E0283]: type annotations needed: cannot satisfy `(for<'a> fn(&'a (), ()), LocalTy): Overlap<for<'a> fn(&'a (), ())>`
  --> src\main.rs:9:5
   |
9  |     foo::<(for<'a> fn(&'a (), ()), LocalTy), for<'a> fn(&'a (), ())>(1);
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: multiple `impl`s satisfying `(for<'a> fn(&'a (), ()), LocalTy): Overlap<for<'a> fn(&'a (), ())>` found in the `dep` crate:
           - impl<T, U> Overlap<T> for (T, U);
           - impl<T, U> Overlap<for<'a> fn(&'a (), <&'static T as dep::ToUnit<'a, U>>::Unit)> for (T, U)
             where for<'a> &'static T: dep::ToUnit<'a, U>;
note: required by a bound in `dep::foo`
  --> C:\Users\Basti\Desktop\test1\dep\src\lib.rs:24:15
   |
24 | pub fn foo<T: Overlap<U>, U>(x: T::Assoc) -> T::Assoc {
   |               ^^^^^^^^^^ required by this bound in `foo`

going from this ambiguity to runtime UB would require also exploiting incompleteness outside of coherence to incorrectly reject one of the impls. I couldn't be bothered to implement that rn.

[lcnr]

the same issue exists for opaque types and is far easier to trigger, even in the old solver:

#![feature(type_alias_impl_trait)]
mod defining_scope {
    use super::*;
    pub type Alias<T> = impl Sized;
    
    pub fn cast<T>(x: Container<Alias<T>, T>) -> Container<T, T> {
        x
    }
}

struct Container<T: Trait<U>, U> {
    x: <T as Trait<U>>::Assoc,
}

trait Trait<T> {
    type Assoc;
}

impl<T> Trait<T> for T {
    type Assoc = Box<u32>;
}
impl<T> Trait<T> for defining_scope::Alias<T> {
    type Assoc = usize;
}

fn main() {
    let x: Box<u32> = defining_scope::cast::<()>(Container { x: 0 }).x;
    println!("{}", *x);
}

this currently results in an ICE:

error: internal compiler error: compiler/rustc_middle/src/ty/normalize_erasing_regions.rs:183:90: Failed to normalize Alias(Projection, AliasTy { args: [(), ()], def_id: DefId(0:15 ~ playground[ba98]::Trait::Assoc) }), maybe try to call `try_normalize_erasing_regions` instead

edit: fixed by #121848

[lcnr]

fixed by #130654