Internal Compiler Error caused by Generic Associated Types

[Sawchord]

Code

#![feature(generic_associated_types)]

trait Monad /* : Applicative (for pure/return, doesn't matter for this example) */ {
    // Self is like the "f a" in haskell

    /// extract the "a" from "f a"
    type Unplug;

    /// exchange the "a" in "f a" in the type of Self with B
    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)
    }
}

// This function causes the compiler error, specifically, when i added the Plug = P constraint.
fn stringify<T, M1, P>(m: M1) -> M1::Plug<P>
where
    T: core::fmt::Display,
    M1: Monad<Unplug = T, Plug = P>,
{
    m.bind(|x| format!("{}", x))
}

fn main() {
    let x = Some(1).bind(|x| Some(x * 2));
    println!("{:?}", x);
}

Meta

rustc --version --verbose:

rustc 1.50.0-nightly (1c389ffef 2020-11-24)
binary: rustc
commit-hash: 1c389ffeff814726dec325f0f2b0c99107df2673
commit-date: 2020-11-24
host: x86_64-unknown-linux-gnu
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
 --> crash.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=[M1]

Backtrace

thread 'rustc' panicked at 'Box<Any>', /rustc/1c389ffeff814726dec325f0f2b0c99107df2673/compiler/rustc_errors/src/lib.rs:904:9
stack backtrace:
   0: std::panicking::begin_panic
   1: rustc_errors::HandlerInner::span_bug
   2: rustc_errors::Handler::span_bug
   3: rustc_middle::util::bug::opt_span_bug_fmt::{{closure}}
   4: rustc_middle::ty::context::tls::with_opt::{{closure}}
   5: rustc_middle::ty::context::tls::with_opt
   6: rustc_middle::util::bug::opt_span_bug_fmt
   7: rustc_middle::util::bug::span_bug_fmt
   8: <rustc_middle::ty::subst::SubstFolder as rustc_middle::ty::fold::TypeFolder>::fold_ty
   9: rustc_middle::ty::fold::TypeFoldable::fold_with
  10: rustc_middle::ty::fold::TypeFoldable::fold_with
  11: rustc_middle::ty::subst::Subst::subst
  12: rustc_middle::ty::GenericPredicates::instantiate_into
  13: rustc_middle::ty::GenericPredicates::instantiate
  14: rustc_trait_selection::traits::wf::WfPredicates::nominal_obligations
  15: rustc_trait_selection::traits::wf::WfPredicates::compute_projection
  16: rustc_trait_selection::traits::wf::predicate_obligations
  17: rustc_typeck::check::wfcheck::check_where_clauses
  18: rustc_typeck::check::wfcheck::check_fn_or_method
  19: rustc_infer::infer::InferCtxtBuilder::enter
  20: rustc_typeck::check::wfcheck::check_item_well_formed
  21: rustc_middle::ty::query::<impl rustc_query_system::query::config::QueryAccessors<rustc_middle::ty::context::TyCtxt> for rustc_middle::ty::query::queries::check_item_well_formed>::compute
  22: rustc_query_system::dep_graph::graph::DepGraph<K>::with_task
  23: rustc_data_structures::stack::ensure_sufficient_stack
  24: rustc_query_system::query::plumbing::get_query_impl
  25: rustc_query_system::query::plumbing::ensure_query_impl
  26: <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once
  27: rustc_hir::hir::Crate::par_visit_all_item_likes
  28: rustc_typeck::check_crate
  29: rustc_interface::passes::analysis
  30: rustc_middle::ty::query::<impl rustc_query_system::query::config::QueryAccessors<rustc_middle::ty::context::TyCtxt> for rustc_middle::ty::query::queries::analysis>::compute
  31: rustc_query_system::dep_graph::graph::DepGraph<K>::with_eval_always_task
  32: rustc_data_structures::stack::ensure_sufficient_stack
  33: rustc_query_system::query::plumbing::get_query_impl
  34: rustc_interface::passes::QueryContext::enter
  35: rustc_interface::queries::<impl rustc_interface::interface::Compiler>::enter
  36: rustc_span::with_source_map
  37: scoped_tls::ScopedKey<T>::set

[camelid]

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

[cynecx]

#79554 might be related.

[camelid]

If #79554 fixes it, then we'll find out in rust-lang/glacier!

[cynecx]

I expected this to work (tested on top of #79554):

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)))
}

But it errors with:

error[E0308]: mismatched types
  --> a.rs:32:16
   |
32 |     m.bind(|x| Some(format!("{}", x)))
   |                ^^^^^^^^^^^^^^^^^^^^^^ expected associated type, found enum `Option`
   |
   = note: expected associated type `<M1 as Monad>::Plug<_>`
                         found enum `Option<String>`
   = help: consider constraining the associated type `<M1 as Monad>::Plug<_>` to `Option<String>`
   = note: for more information, visit https://doc.rust-lang.org/book/ch19-03-advanced-traits.html

Am I missing something? (Or is this a bug?) @jackh726

EDIT: I think the issue here is that we can't constraint the generic argument for Plug to the concrete type String. But I also kinda expected <M1 as Monad>::Plug<String> would get normalized to Option<String>

[jackh726]

@cynecx looks like the same bug as #76407 (working on it now)

[Alexendoo]

Fixed by #79554

[cynecx]

Huh? This isn't fully fixed by #79554. This original code also requires normalization which doesn't happen right now.

[memoryruins]

@cynecx this issue was only tracking the ICE, which is fixed on nightly and now has a regression test. #76407 is tracking the issue you're referring to, right? Worth re-posting the examples on the other issue.