Compiler panic during GAT type bound usage

[snoyberg]

Code

#![feature(generic_associated_types)]

trait Monad {
    type Unwrapped;
    type Wrapped<B>;

    fn bind<B, F>(self, f: F) -> Self::Wrapped<B> {
        todo!()
    }
}

fn join<MOuter, MInner, A>(outer: MOuter) -> MOuter::Wrapped<A>
where
    MOuter: Monad<Unwrapped = MInner>,
    MInner: Monad<Unwrapped = A, Wrapped = MOuter::Wrapped<A>>,
{
    outer.bind(|inner| inner)
}

fn main() {
    assert_eq!(join(Some(Some(true))), Some(true));
}

Meta

rustc --version --verbose:

rustc 1.50.0-nightly (b7ebc6b0c 2020-11-30)
binary: rustc
commit-hash: b7ebc6b0c1ba3c27ebb17c0b496ece778ef11e18
commit-date: 2020-11-30
host: x86_64-pc-windows-msvc
release: 1.50.0-nightly

Error output

warning: the feature `generic_associated_types` is incomplete and may not be safe to use and/or cause compiler crashes
 --> join.rs:1:12
  |
1 | #![feature(generic_associated_types)]
  |            ^^^^^^^^^^^^^^^^^^^^^^^^
  |
  = note: `#[warn(incomplete_features)]` on by default
  = note: see issue #44265 <https://github.com/rust-lang/rust/issues/44265> for more information

error: internal compiler error: compiler\rustc_middle\src\ty\subst.rs:529:17: type parameter `B/#1` (B/1) out of range when substituting, substs=[MInner]

thread 'rustc' panicked at 'Box<Any>', /rustc/b7ebc6b0c1ba3c27ebb17c0b496ece778ef11e18\compiler\rustc_errors\src\lib.rs:904:9
stack backtrace:
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.

note: the compiler unexpectedly panicked. this is a bug.

note: we would appreciate a bug report: https://github.com/rust-lang/rust/issues/new?labels=C-bug%2C+I-ICE%2C+T-compiler&template=ice.md

note: rustc 1.50.0-nightly (b7ebc6b0c 2020-11-30) running on x86_64-pc-windows-msvc

query stack during panic:
#0 [check_item_well_formed] checking that `join` is well-formed
#1 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to previous error; 1 warning emitted

Notes

I recognize this is an unstable compiler feature, and have no problem if it would be better to just close this. Also, if it would be better to include this report elsewhere, please let me know.

[camelid]

I recognize this is an unstable compiler feature, and have no problem if it would be better to just close this. Also, if it would be better to include this report elsewhere, please let me know.

Don't feel like this should be closed! It's important and helpful that you filed this so that we can smooth this feature out – even though it's unstable, this is still a bug that should be addressed :)

[camelid]

@rustbot glacier "https://gist.github.com/rust-play/43200608c0a841165c57ab660029b4f1"

[steffahn]

@snoyberg Only tangantially related to this issue, but you might be interested in this post of mine on how to do monads in Rust. It does e.g. support writing "join":

Example code of "join" that compiles with my approach:

fn join<A, M: Monad>(mmx: a!(M:<a!(M:<A>)>)) -> M::Of<A> {
    do_!{
        mx <- mmx;
        x <- mx;
        M::pure(x)
    }
}

// alternative version, using trivial conversion 
// between MT: HasTyCon<Param = T, GetTyCon = M>
//     and M::Of<T>
fn join_alternative<A, M: Monad>(mmx: a!(M:<a!(M:<A>)>)) -> M::Of<A> {
    do_!{
        mx <- mmx;
        mx.as_con_ty()
    }
}

fn main() {
    let xss = vec![vec![1,2,3],vec![],vec![4,5],vec![6]];
    // join can be used on concrete monadic types
    let xs = join(xss);
    print!("{:?}", xs); // [1,2,3,4,5,6]
    
}

// join can be used in a generic context
fn join_twice<A, M: Monad>(mmmx:  a!(M:<a!(M:<a!(M:<A>)>)>)) -> M::Of<A> {
    join(join(mmmx))
}

(playground including this example)

[amosonn]

It is worth noting, that technically this is the wrong syntax. Wrapped is not a type, rather a type constructor, and therefore cannot be bounded; the correct constraint should be:

MInner: Monad<Unwrapped = A, Wrapped<A> = MOuter::Wrapped<A>>`

which returns correctly (and sadly)

error: generic associated types in trait paths are currently not implemented
  --> src/main.rs:15:41
   |
15 |     MInner: Monad<Unwrapped = A, Wrapped<A> = MOuter::Wrapped<A>>,
   |                                         ^^^

Edit: this means that the crash should of course still be fixed, but to return a syntax error.

[jsjolen]

Here's a smaller test-case (I found this bug independently):

#![feature(generic_associated_types)]

pub trait SomeTrait {
    type Wrapped<A>: SomeTrait;

    fn f() -> ();
}

fn program<W>() -> ()
where
    W: SomeTrait<Wrapped = W>,
{
    return W::f();
}

fn main() {}

[Alexendoo]

Fixed by #79554

[marmeladema]

Adding a test for this is blocked on #82272

[jackh726]

No, test can be added as-is. Diagnostics issue is orthogonal.