Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Closed
ExpHP opened this issue Nov 27, 2018 · 13 comments
Closed
Assignees
Labels
I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority regression-from-stable-to-beta Performance or correctness regression from stable to beta. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-lang Relevant to the language team, which will review and decide on the PR/issue.

Comments

@ExpHP
Copy link
Contributor

ExpHP commented Nov 27, 2018

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

@Centril Centril added the I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ label Nov 27, 2018
@oli-obk oli-obk added the regression-from-stable-to-nightly Performance or correctness regression from stable to nightly. label Nov 29, 2018
@pnkfelix
Copy link
Member

triage: P-high. assigning to self.

@pnkfelix pnkfelix assigned pnkfelix and arielb1 and unassigned pnkfelix Nov 29, 2018
@pnkfelix
Copy link
Member

oop @arielb1 volunteered to take it in parallel.

@pnkfelix pnkfelix added the P-high High priority label Nov 29, 2018
@arielb1
Copy link
Contributor

arielb1 commented Dec 2, 2018

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
Copy link
Contributor

arielb1 commented Dec 2, 2018

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
Copy link
Contributor

arielb1 commented Dec 2, 2018

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.

@arielb1 arielb1 changed the title ICE: Encountered a freshend type with id 0 but our counter is only at 0 problems with trait objects with a trait projection value that contains Self Dec 3, 2018
@arielb1 arielb1 added I-nominated T-lang Relevant to the language team, which will review and decide on the PR/issue. labels Dec 3, 2018
@Centril
Copy link
Contributor

Centril commented Dec 3, 2018

Reduced version (@arielb1 has more):

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

trait Beta: Gamma<Delta = Self> {}

trait Gamma {
    type Delta;
}

@arielb1
Copy link
Contributor

arielb1 commented Dec 3, 2018

Nominating for T-lang discussion. That's not a call I should make unilaterally.

The question is about trait objects of these traits:

trait MyTrait: Supertrait<Output=SOMETHING<Self>> {
    // ...
}

With the "classical useful" case being:

trait MyTrait: FnMut() -> <Self as MyTrait>::MyOutput {
    type MyOutput;
}

A few observations:

  1. If Self was present in an input type parameter of the supertrait (e.g. MyTrait: FnMut(<Self as MyTrait>::MyAssocType)), we would already regard MyTrait as non-object-safe.
  2. But this case is apparently useful, and it would be a shame and an annoyance to ban it.
  3. WF for trait object types doesn't work very well (object-safe traits can have associated types with unchecked bounds #27675), which might complicate discussions/solutions until we get it sorted out.
  4. If the value is injective (e.g., doesn't contain a projection), then the type dyn MyTrait<Output=X> is uninhabited for every X: it is impossible to have a value of type T that can be put into the trait object, because <T as MyTrait>::Output != <dyn MyTrait<Output=X> as MyTrait>::Output (unless T is already a trait object!).
  5. ALT0: Until Take supertraits into account when calculating associated types #55687, you would have to use the type as MyTrait<MyOutput=X, Output=X>, and your type would by uninhabited (and possibly non-WF) unless the Xs you wrote were the same. We can maintain that situation if we revert Take supertraits into account when calculating associated types #55687.
  6. With Take supertraits into account when calculating associated types #55687, the intent was that you'll be able to write MyTrait<MyOutput=X> without writing an assignment for Output. However, with the current implementation, that does not work very well - it would have to expand to the infinite type fix $ τ → dyn MyTrait<MyOutput=X, Output=<τ as MyTrait>::MyOutput.
    6.a. We can't just "pick out the associated type". We could have trait MyTrait: FnMut() -> <Something<Based<On<Self>>> as SomeTrait>::SomeOutput
  7. ALT1: One possible solution would be to have the type always be MyTrait<MyOutput=X> and the compiler will "infer" Output by itself. We'll need to do some handling for the case where you do write Output explicitly. We need to see how complicated this would be to implement, but I don't feel this sort of thing should get into a beta - that would mean reverting Take supertraits into account when calculating associated types #55687 for this nightly.
  8. ALT2: The other solution would be to disable the defaulting when the projection output type contains Self, so that you'll have to write MyTrait<MyOutput=X, Output=X> (same as before) if the projection output contains Self, but you can still use Take supertraits into account when calculating associated types #55687 in other cases, such as trait MyTrait: FnMut() -> u32.

There could also be some other alternative I haven't noticed.

@arielb1 arielb1 added the T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. label Dec 3, 2018
@arielb1
Copy link
Contributor

arielb1 commented Dec 3, 2018

Another option would be to have trait-object types be some sort of recursive types themselves, e.g. dyn (Self → MyTrait<MyOutput=X, Output=<Self as MyTrait>::MyOutput>), and expand the Self when we project types out of the trait object. That's however the sort of thing that will make WF-checking and type equality so much more fun.

@alexcrichton alexcrichton added regression-from-stable-to-beta Performance or correctness regression from stable to beta. and removed regression-from-stable-to-nightly Performance or correctness regression from stable to nightly. labels Dec 8, 2018
@pnkfelix
Copy link
Member

T-compiler triage: This is still waiting for the lang team. (Its understandable that they didn't see it yet, as the meeting last week was cancelled.)

@nikomatsakis
Copy link
Contributor

ALT2: The other solution would be to disable the defaulting when the projection output type contains Self, so that you'll have to write MyTrait<MyOutput=X, Output=X> (same as before) if the projection output contains Self, but you can still use #55687 in other cases, such as trait MyTrait: FnMut() -> u32.

This seems like the obvious "short-term" solution. It's certainly the one I thought of. Basically we would permit you to elide associated types that are specified, so long as those specifications don't involve Self. (That's the proposal, right?)

Longer term, we definitely have to wrestle a bit with trait objects. Between the WF problems, #51443, etc, it feels like something should be adjusted.

One question we've been wondering about is just how to extend Chalk to cover object types.

@nikomatsakis
Copy link
Contributor

Discussed in the @rust-lang/lang meeting.

In short, we think the best fix is to take the ALT2 approach for now -- sidestep the ICE, but retain the benefits of #55687.

(That said, for backporting purposes, it might be fine to revert #55687, that's more of an engineering question.)

In principle it would be nice if Foo<Out = X> (given the trait definitions below) would "work", but that is something we can work out "at our liesure".

trait Foo: Bar<Out = Self> {
}

trait Bar { type Out; }

@nikomatsakis
Copy link
Contributor

@arielb1 are you interested in doing that fix?

@arielb1
Copy link
Contributor

arielb1 commented Dec 14, 2018

Sure.

bors added a commit that referenced this issue Dec 18, 2018
fix trait objects with a Self-containing projection values

Fixes #56288.

This follows ALT2 in the issue.

beta-nominating since this is a regression.

r? @nikomatsakis
pietroalbini pushed a commit to pietroalbini/rust that referenced this issue Dec 31, 2018
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
I-ICE Issue: The compiler panicked, giving an Internal Compilation Error (ICE) ❄️ P-high High priority regression-from-stable-to-beta Performance or correctness regression from stable to beta. T-compiler Relevant to the compiler team, which will review and decide on the PR/issue. T-lang Relevant to the language team, which will review and decide on the PR/issue.
Projects
None yet
Development

No branches or pull requests

7 participants