problems with trait objects with a trait projection value that contains Self

[ExpHP]

Title Edited. Original title was: ICE: Encountered a freshend type with id 0 but our counter is only at 0

Only on nightly. Minimized for your pleasure:

// NOTE: uncommenting Input changes the error message
// pub struct Input {}

pub trait BuildAlgorithmStateFn{
    fn build(&self) -> Box<dyn AlgorithmStateFn<Output=()>>;
}

pub trait AlgorithmStateFn
    : FnMut() -> <Self as AlgorithmStateFn>::Output
{
    type Output;
}

Error/Backtrace if Input is commented out

error: internal compiler error: src/librustc/infer/freshen.rs:165: Encountered a freshend type with id 0 but our counter is only at 0

thread 'main' panicked at 'Box<Any>', src/librustc_errors/lib.rs:600:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:211
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:227
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:480
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::bug
   8: rustc::util::bug::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::util::bug::opt_span_bug_fmt
  13: rustc::util::bug::bug_fmt
  14: <rustc::infer::freshen::TypeFreshener<'a, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
  15: <smallvec::SmallVec<A> as core::iter::traits::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  16: rustc::ty::fold::TypeFoldable::fold_with
  17: rustc::traits::select::SelectionContext::select
  18: rustc::infer::InferCtxt::commit_if_ok
  19: rustc::traits::project::opt_normalize_projection_type
  20: rustc::traits::project::normalize_projection_type
  21: <rustc::traits::project::AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
  22: <smallvec::SmallVec<A> as core::iter::traits::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  23: rustc::ty::fold::TypeFoldable::fold_with
  24: rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable<'tcx> for &'tcx rustc::ty::TyS<'tcx>>::super_fold_with
  25: <rustc::traits::project::AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
  26: <smallvec::SmallVec<A> as core::iter::traits::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  27: rustc::ty::fold::TypeFoldable::fold_with
  28: rustc::ty::structural_impls::<impl rustc::ty::fold::TypeFoldable<'tcx> for &'tcx rustc::ty::TyS<'tcx>>::super_fold_with
  29: <rustc::traits::project::AssociatedTypeNormalizer<'a, 'b, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
  30: <smallvec::SmallVec<A> as core::iter::traits::FromIterator<<A as smallvec::Array>::Item>>::from_iter
  31: rustc::ty::fold::TypeFoldable::fold_with
  32: rustc::traits::project::normalize
  33: rustc::infer::InferCtxt::partially_normalize_associated_types_in
  34: rustc::ty::context::tls::with_related_context
  35: rustc::infer::InferCtxtBuilder::enter
  36: rustc_typeck::check::wfcheck::check_associated_item
  37: rustc_typeck::check::wfcheck::check_trait_item
  38: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::check_trait_item_well_formed<'tcx>>::compute
  39: rustc::ty::context::tls::with_context
  40: rustc::dep_graph::graph::DepGraph::with_task_impl
  41: rustc::ty::context::tls::with_related_context
  42: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  43: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  44: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::ensure_query
  45: rustc::session::Session::track_errors
  46: rustc_typeck::check_crate
  47: rustc::ty::context::tls::enter_context
  48: <std::thread::local::LocalKey<T>>::with
  49: rustc::ty::context::TyCtxt::create_and_enter
  50: rustc_driver::driver::compile_input
  51: rustc_driver::run_compiler_with_pool
  52: <scoped_tls::ScopedKey<T>>::set
  53: rustc_driver::run_compiler
  54: syntax::with_globals
  55: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:102
  56: rustc_driver::run
  57: rustc_driver::main
  58: std::rt::lang_start::{{closure}}
  59: std::panicking::try::do_call
             at src/libstd/rt.rs:59
             at src/libstd/panicking.rs:310
  60: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:102
  61: std::rt::lang_start_internal
             at src/libstd/panicking.rs:289
             at src/libstd/panic.rs:398
             at src/libstd/rt.rs:58
  62: main
  63: __libc_start_main
  64: <unknown>
query stack during panic:
#0 [check_trait_item_well_formed] processing `BuildAlgorithmStateFn::build`
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.32.0-nightly (6bfb46e4a 2018-11-26) running on x86_64-unknown-linux-gnu

note: compiler flags: -C debuginfo=2 -C incremental --crate-type lib

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

error: Could not compile `rsp2-minimize`.

To learn more, run the command again with --verbose.

Error/Backtrace if Input is present

error: internal compiler error: src/librustc_typeck/variance/constraints.rs:344: unexpected type encountered in variance inference: FreshTy(0)

thread 'main' panicked at 'Box<Any>', src/librustc_errors/lib.rs:600:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:59
             at src/libstd/panicking.rs:211
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:227
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:480
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::bug
   8: rustc::util::bug::opt_span_bug_fmt::{{closure}}
   9: rustc::ty::context::tls::with_opt::{{closure}}
  10: rustc::ty::context::tls::with_context_opt
  11: rustc::ty::context::tls::with_opt
  12: rustc::util::bug::opt_span_bug_fmt
  13: rustc::util::bug::bug_fmt
  14: rustc_typeck::variance::constraints::ConstraintContext::add_constraints_from_ty
  15: rustc_typeck::variance::constraints::ConstraintContext::add_constraints_from_invariant_substs
  16: rustc_typeck::variance::constraints::ConstraintContext::add_constraints_from_ty
  17: rustc_typeck::variance::constraints::ConstraintContext::add_constraints_from_ty
  18: rustc_typeck::variance::constraints::ConstraintContext::add_constraints_from_ty
  19: rustc_typeck::variance::constraints::ConstraintContext::visit_node_helper
  20: rustc::hir::Crate::visit_all_item_likes
  21: rustc_typeck::variance::constraints::add_constraints_from_crate
  22: rustc_typeck::variance::crate_variances
  23: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::crate_variances<'tcx>>::compute
  24: rustc::ty::context::tls::with_context
  25: rustc::dep_graph::graph::DepGraph::with_task_impl
  26: rustc::ty::context::tls::with_related_context
  27: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  28: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  29: rustc_typeck::variance::variances_of
  30: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::variances_of<'tcx>>::compute
  31: rustc::ty::context::tls::with_context
  32: rustc::dep_graph::graph::DepGraph::with_task_impl
  33: rustc::ty::context::tls::with_related_context
  34: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  35: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  36: rustc_typeck::check::wfcheck::check_variances_for_type_defn
  37: rustc_typeck::check::wfcheck::check_item_well_formed
  38: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::check_item_well_formed<'tcx>>::compute
  39: rustc::ty::context::tls::with_context
  40: rustc::dep_graph::graph::DepGraph::with_task_impl
  41: rustc::ty::context::tls::with_related_context
  42: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  43: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  44: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::ensure_query
  45: rustc::session::Session::track_errors
  46: rustc_typeck::check_crate
  47: rustc::ty::context::tls::enter_context
  48: <std::thread::local::LocalKey<T>>::with
  49: rustc::ty::context::TyCtxt::create_and_enter
  50: rustc_driver::driver::compile_input
  51: rustc_driver::run_compiler_with_pool
  52: <scoped_tls::ScopedKey<T>>::set
  53: rustc_driver::run_compiler
  54: syntax::with_globals
  55: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:102
  56: rustc_driver::run
  57: rustc_driver::main
  58: std::rt::lang_start::{{closure}}
  59: std::panicking::try::do_call
             at src/libstd/rt.rs:59
             at src/libstd/panicking.rs:310
  60: __rust_maybe_catch_panic
             at src/libpanic_unwind/lib.rs:102
  61: std::rt::lang_start_internal
             at src/libstd/panicking.rs:289
             at src/libstd/panic.rs:398
             at src/libstd/rt.rs:58
  62: main
  63: __libc_start_main
  64: <unknown>
query stack during panic:
#0 [crate_variances] computing the variances for items in this crate
#1 [variances_of] processing `Input`
#2 [check_item_well_formed] processing `Input`
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.32.0-nightly (6bfb46e4a 2018-11-26) running on x86_64-unknown-linux-gnu

note: compiler flags: -C debuginfo=2 -C incremental --crate-type lib

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

error: Could not compile `rsp2-minimize`.

To learn more, run the command again with --verbose.

"Correct" output on beta

At least, "correct" as in "not an ICE"...

$ RUST_BACKTRACE=1 cargo +beta build
   Compiling objekt v0.1.1                                                                                                                                   
   Compiling rsp2-minimize v0.1.0 (/home/lampam/rsp2.3)                                                                                                      
error[E0191]: the value of the associated type `Output` (from the trait `std::ops::FnOnce`) must be specified                                                
  --> src/lib.rs:11:28                                                                                                                                       
   |                                                                                                                                                         
11 |     fn build(&self) -> Box<dyn AlgorithmStateFn<Output=()>>;                                                                                            
   |                            ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ missing associated type `Output` value                                                       
                                                                                                                                                             
error: aborting due to previous error 

Additional notes:

It is not related to the name clash of the associated types, because the following modified snippet:

pub struct Input {}

pub trait BuildAlgorithmStateFn{
    fn build(&self) -> Box<dyn AlgorithmStateFn<Output2=(),Output=()>>;
}

pub trait AlgorithmStateFn
    : FnMut() -> <Self as AlgorithmStateFn>::Output2
{
    type Output2;
}

...also produces the same ICE on nightly (but compiles on beta).

[pnkfelix]

triage: P-high. assigning to self.

[pnkfelix]

oop @arielb1 volunteered to take it in parallel.

[arielb1]

The problem is that AlgorithmStateFn has a supertrait that contains Self. We forbid non-projection supertraitsthe input parameters of supertraits from containing Self, but we don't forbid the output of projections from containing Self.

The problem with these supertraits is that of course, T: dyn AlgorithmicStateFn does not imply that it can be wrapped into a dyn T, because the associated type might be different (note, because there is a projection there, the type might also be the same - as long as Output2 normalizes to the same thing as Output, all is OK).

The regression was caused by #55687 - "Take supertraits into account when calculating associated types".

I'm not sure what's the best way to solve this while keeping #55687. We could regard trait-objects with a projection that contains Self as non-object-safe, but that would be a backwards-compatibility break - and these types are indeed useful.

The other option would be to have the Self = THE-TRAIT-OBJECT-TYPE interpretation, and make sure we check the projections when upcasting, rather than regarding these as implicit. Nah that results in a cyclic type of infinite size fix τ = dyn AlgorithmicStateFn<Output2=X, Output=<τ as AlgorithmicStateFn>::Output2

[arielb1]

We could require the user to explicitly specify the value of the type in these cases - if they'll specify it wrongly, they'll get an error anyway (that's it, it would always give an error if WF on trait object types actually worked. Right now, it doesn't, but the object type will still be uninhabited because all the "good" implementors of the trait will have consistent associated types). That would be the backwards compatible fix.

[arielb1]

A post-Chalk option might be to have dyn AlgorithmStateFn<Output2=()> and dyn AlgorithmStateFn<Output=(), Output2=()> be two names for the same type (i.e., define object types if their trait components are in the same order and if all of their "expanded" associated types are equal). Of course, we should not go there before we both have a better model of trait object types and are comfortable with a type having wildly-different names.

[Centril]

Reduced version (@arielb1 has more):

trait Alpha {
    fn build() -> &'static dyn Beta<Delta = ()>;
}

trait Beta: Gamma<Delta = Self> {}

trait Gamma {
    type Delta;
}