"failed to normalize" ICE in NLL borrow checker

[jonas-schievink]

Happens on stable 1.34.2, 1.35.0 and current nightly (2019-05-28). Playground.

pub trait IntoFuture {
    type Item;
    type Error;
    type Future: Future<Item=Self::Item, Error=Self::Error>;
}

impl<T, E> IntoFuture for Result<T, E> {
    type Item = T;
    type Error = E;
    type Future = Fut<T, E>;
}

pub trait Future {
    type Item;
    type Error;
}

struct Fut<T, E>(T, E);
impl<T, E> Future for Fut<T, E> {
    type Item = T;
    type Error = E;
}

type BoxedError = Box<dyn std::error::Error + Send + Sync>;

trait FromRequest {
    type Context;
    fn from_request(context: Self::Context);
}

trait Guard {
    type Result;
}

struct Authenticated<R> {
    inner: R,
}

impl<R> FromRequest for Authenticated<R>
where
    <User as Guard>::Result:
        IntoFuture<Item = User, Error = BoxedError>,
    <<User as Guard>::Result as IntoFuture>::Future:
        Send,
{
    type Context = ();
    fn from_request(_: Self::Context) {}
}

struct User;
impl Guard for User {
    type Result = Result<Self, BoxedError>;
}

Results in:

error: internal compiler error: src/librustc_mir/borrow_check/nll/type_check/free_region_relations.rs:260: failed to normalize <Authenticated<R> as FromRequest>::Context

thread 'rustc' panicked at 'Box<Any>', src/librustc_errors/lib.rs:637:9
stack backtrace:
   0: backtrace::backtrace::libunwind::trace
             at /cargo/registry/src/jackfan.us.kg-1ecc6299db9ec823/backtrace-0.3.25/src/backtrace/libunwind.rs:97
   1: backtrace::backtrace::trace_unsynchronized
             at /cargo/registry/src/jackfan.us.kg-1ecc6299db9ec823/backtrace-0.3.25/src/backtrace/mod.rs:66
   2: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:47
   3: std::sys_common::backtrace::print
             at src/libstd/sys_common/backtrace.rs:36
   4: std::panicking::default_hook::{{closure}}
             at src/libstd/panicking.rs:197
   5: std::panicking::default_hook
             at src/libstd/panicking.rs:211
   6: rustc::util::common::panic_hook
   7: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:478
   8: std::panicking::begin_panic
   9: rustc_errors::Handler::bug
  10: rustc::util::bug::opt_span_bug_fmt::{{closure}}
  11: rustc::ty::context::tls::with_opt::{{closure}}
  12: rustc::ty::context::tls::with_context_opt
  13: rustc::ty::context::tls::with_opt
  14: rustc::util::bug::opt_span_bug_fmt
  15: rustc::util::bug::bug_fmt
  16: core::ops::function::impls::<impl core::ops::function::FnOnce<A> for &mut F>::call_once
  17: <core::iter::adapters::flatten::FlatMap<I,U,F> as core::iter::traits::iterator::Iterator>::next
  18: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T,I>>::from_iter
  19: rustc_mir::borrow_check::nll::type_check::free_region_relations::create
  20: rustc_mir::borrow_check::nll::type_check::type_check
  21: rustc_mir::borrow_check::nll::compute_regions
  22: rustc_mir::borrow_check::do_mir_borrowck
  23: rustc::ty::context::GlobalCtxt::enter_local
  24: rustc_mir::borrow_check::mir_borrowck
  25: rustc::ty::query::__query_compute::mir_borrowck
  26: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors for rustc::ty::query::queries::mir_borrowck>::compute
  27: rustc::dep_graph::graph::DepGraph::with_task_impl
  28: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  29: rustc::ty::<impl rustc::ty::context::TyCtxt>::par_body_owners
  30: rustc::util::common::time
  31: rustc_interface::passes::analysis
  32: rustc::ty::query::__query_compute::analysis
  33: rustc::dep_graph::graph::DepGraph::with_task_impl
  34: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt>::get_query
  35: rustc::ty::context::tls::enter_global
  36: rustc_interface::passes::BoxedGlobalCtxt::access::{{closure}}
  37: rustc_interface::passes::create_global_ctxt::{{closure}}
  38: rustc_interface::interface::run_compiler_in_existing_thread_pool
  39: std::thread::local::LocalKey<T>::with
  40: scoped_tls::ScopedKey<T>::set
  41: syntax::with_globals
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
query stack during panic:
#0 [mir_borrowck] processing `<Authenticated<R> as FromRequest>::from_request`
#1 [analysis] running analysis passes on this crate
end of query stack
error: aborting due to previous error


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

note: we would appreciate a bug report: https://github.com/rust-lang/rust/blob/master/CONTRIBUTING.md#bug-reports

note: rustc 1.37.0-nightly (721268583 2019-05-28) running on x86_64-unknown-linux-gnu

note: compiler flags: -C codegen-units=1 -C debuginfo=2 --crate-type lib

note: some of the compiler flags provided by cargo are hidden

[Centril]

Reduced:

pub struct Unit;
trait Obj {}

trait Bound {}
impl Bound for Unit {}

pub trait HasProj {
    type Proj;
}

impl<T> HasProj for T {
    type Proj = Unit;
}

trait HasProjFn {
    type Proj;
    fn the_fn(_: Self::Proj);
}

impl HasProjFn for Unit
where
    Box<dyn Obj>: HasProj,
    <Box<dyn Obj> as HasProj>::Proj: Bound,
{
    type Proj = Unit;
    fn the_fn(_: Self::Proj) {}
}

[Centril]

Compiles fine on 1.34.0; haven't tested 1.34.1.

[jonas-schievink]

@Centril both my repro and your reduced one do ICE on rustc 1.34.0 (91856ed52 2019-04-10) (and rustc 1.34.1 (fc50f328b 2019-04-24)) for me, can you verify that again?

[jonas-schievink]

Happens all the way back to 1.30.0 (with RUSTC_BOOTSTRAP=1) for me, as long as --edition=2018 is passed to rustc.

[Centril]

@jonas-schievink Ah of course! --edition=2018 is needed for NLL on older versions... :) I forgot that godbolt doesn't have that by default.