Associated type constraint fails, even if it implements requested trait

[Mr-Andersen]

Associated type constraint fails, even if it implements requested trait. In the example below, requested trait is Marker, u32 implements it, <MyStruct as MyTrait>::Item<'a> == u32, but <MyStruct as MyTrait>::Item<'a>: Marker does not pass. (Everything is ok with <'a> removed)

The code:

#![allow(incomplete_features)]
#![feature(generic_associated_types)]

trait Marker {}

impl Marker for u32 {}

trait MyTrait {
    type Item<'a>;
}

struct MyStruct;

impl MyTrait for MyStruct {
    type Item<'a> = u32;
}

fn ty_check<T>()
where
    T: MyTrait,
    for<'a> T::Item<'a>: Marker
{}

fn main() {
    ty_check::<MyStruct>();
}

Meta

rustc --version --verbose:

rustc 1.48.0-nightly (cdc8f0606 2020-09-05)
binary: rustc
commit-hash: cdc8f0606d0f3c4f3866643382c8a5776d1bdaed
commit-date: 2020-09-05
host: x86_64-unknown-linux-gnu
release: 1.48.0-nightly
LLVM version: 11.0

[Mr-Andersen]

Also, if type Item<'a>: Marker; in MyTrait, the code compiles.

[nikomatsakis]

This variant also fails to compile, but doesn't use GATs:

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2018&gist=1ea06f6d50ae8a612feb5a22279e2889

My guess is that this is the same bug. We are missing a normalization somewhere.

[jackh726]

Projections aren't getting normalized because:

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

Line 368 in cfba499

ty::Projection(data) if !data.has_escaping_bound_vars() => {

[NathanIceSea]

I could confirm with TryFrom trait associated type Error's Debug constraint, used as generic return type

[cynecx]

Another test-case copied from #79768 (@jackh726 mentioned that this might be related to this one):

#![feature(generic_associated_types)]

trait Monad {
    type Unplug;
    type Plug<B>: Monad;

    fn bind<B, F>(self, f: F) -> Self::Plug<B>
    where
        F: Fn(Self::Unplug) -> Self::Plug<B>;
}

impl<A> Monad for Option<A> {
    type Unplug = A;
    type Plug<B> = Option<B>;
    
    fn bind<B, F>(self, f: F) -> Option<B>
    where
        F: Fn(A) -> Option<B>,
    {
        self.and_then(f)
    }
}

fn stringify<T, M1>(m: M1) -> <M1 as Monad>::Plug<String>
where
    T: core::fmt::Display,
    M1: Monad<Unplug = T>,
{
    m.bind(|x| Some(format!("{}", x)))
}

[SkiFire13]

@cynecx I don't think your example should compile. M1 is not guaranteed to be Option<T>, there could be other types that impement Monad<Unplug=T> whose Plug<B> associated type is not Option<B>. For example if I add another impl for Result<A, ()> like the following then stringify will not be valid anymore when M1 = Result<T, ()>:

#![feature(generic_associated_types)]

trait Monad {
    type Unplug;
    type Plug<B>: Monad;

    fn bind<B, F>(self, f: F) -> Self::Plug<B>
    where
        F: Fn(Self::Unplug) -> Self::Plug<B>;
}

impl<A> Monad for Option<A> {
    type Unplug = A;
    type Plug<B> = Option<B>;
    
    fn bind<B, F>(self, f: F) -> Option<B>
    where
        F: Fn(A) -> Option<B>,
    {
        self.and_then(f)
    }
}

impl<A> Monad for Result<A, ()> {
    type Unplug = A;
    type Plug<B> = Result<B, ()>;
    
    fn bind<B, F>(self, f: F) -> Result<B, ()>
    where
        F: Fn(A) -> Result<B, ()>
    {
        self.and_then(f)
    }
}

fn stringify<T, M1>(m: M1) -> <M1 as Monad>::Plug<String>
where
    T: core::fmt::Display,
    M1: Monad<Unplug = T>,
{
    m.bind(|x| Some(format!("{}", x)))
}

fn main() {
    let a: Result<i32, ()> = Ok(0);
    stringify(a); // In this case <M1 as Monad>::Plug<String> = Result<String, ()>`, not `Option<String>`!
}

Edit: the following compiles, this may be what you want:

#![feature(generic_associated_types)]

trait Monad {
    type Unplug;
    type Plug<B>: Monad<Unplug = B>;

    fn plug(t: Self::Unplug) -> Self;

    fn bind<B, F>(self, f: F) -> Self::Plug<B>
    where
        F: Fn(Self::Unplug) -> Self::Plug<B>;
}

impl<A> Monad for Option<A> {
    type Unplug = A;
    type Plug<B> = Option<B>;
    
    fn plug(t: Self::Unplug) -> Self {
        Some(t)
    }
    
    fn bind<B, F>(self, f: F) -> Option<B>
    where
        F: Fn(A) -> Option<B>,
    {
        self.and_then(f)
    }
}

fn stringify<T, M1>(m: M1) -> <M1 as Monad>::Plug<String>
where
    T: core::fmt::Display,
    M1: Monad<Unplug = T>,
{
    m.bind(|x| M1::Plug::plug(format!("{}", x)))
}

[cynecx]

@SkiFire13 Oh wow. (...I feel stupid). Thanks for pointing that out :D