ICE on nightly when dereferencing boxed Iterator trait object

[foxbenjaminfox]

When dereferencing a boxed Iterator trait object I get an internal compiler error (only on nightly).

Here is a minimal example: (playground link)

fn ice(x: Box<dyn Iterator<Item=()>>) {
    *x
}
fn main() {}

This should result in a type error, as indeed it does if I swap out dyn Iterator<Item=()> with dyn std::fmt::Debug.

Instead, it results in the following error when compiled with nightly (rustc src/main.rs):

thread 'rustc' panicked at 'index out of bounds: the len is 527 but the index is 527', /rustc/e2f221c75932de7a29845c8d6f1f73536ad00c41/src/libcore/slice/mod.rs:2455:10
note: Run with `RUST_BACKTRACE=1` environment variable to display a backtrace.

error: internal compiler error: unexpected panic

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.33.0-nightly (e2f221c75 2019-01-15) running on x86_64-unknown-linux-gnu

Meta

Output from rustc --version --verbose:

rustc 1.33.0-nightly (e2f221c75 2019-01-15)
binary: rustc
commit-hash: e2f221c75932de7a29845c8d6f1f73536ad00c41
commit-date: 2019-01-15
host: x86_64-unknown-linux-gnu
release: 1.33.0-nightly
LLVM version: 8.0

[estebank]

stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:39
   1: std::sys_common::backtrace::_print
             at src/libstd/sys_common/backtrace.rs:70
   2: std::panicking::default_hook::{{closure}}
             at src/libstd/sys_common/backtrace.rs:58
             at src/libstd/panicking.rs:200
   3: std::panicking::default_hook
             at src/libstd/panicking.rs:215
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at src/libstd/panicking.rs:482
   6: std::panicking::continue_panic_fmt
             at src/libstd/panicking.rs:385
   7: rust_begin_unwind
             at src/libstd/panicking.rs:312
   8: core::panicking::panic_fmt
             at src/libcore/panicking.rs:85
   9: core::panicking::panic_bounds_check
             at src/libcore/panicking.rs:61
  10: <ena::unify::UnificationTable<S>>::get_root_key
  11: rustc::infer::InferCtxt::shallow_resolve
  12: <rustc::infer::resolve::OpportunisticTypeResolver<'a, 'gcx, 'tcx> as rustc::ty::fold::TypeFolder<'gcx, 'tcx>>::fold_ty
  13: rustc::infer::InferCtxt::probe
  14: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter
  15: rustc_typeck::check::method::probe::ProbeContext::pick_method
  16: rustc_typeck::check::method::probe::ProbeContext::pick_core
  17: <core::iter::FilterMap<I, F> as core::iter::iterator::Iterator>::next
  18: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter
  19: rustc::infer::InferCtxt::probe
  20: rustc_typeck::check::method::probe::ProbeContext::pick
  21: rustc::infer::InferCtxt::probe
  22: rustc_typeck::check::method::probe::<impl rustc_typeck::check::FnCtxt<'a, 'gcx, 'tcx>>::probe_op
  23: <alloc::vec::Vec<T> as alloc::vec::SpecExtend<T, I>>::from_iter
  24: rustc_typeck::check::method::probe::<impl rustc_typeck::check::FnCtxt<'a, 'gcx, 'tcx>>::probe_for_return_type
  25: rustc_typeck::check::FnCtxt::suggest_ref_or_into
  26: rustc_typeck::check::FnCtxt::suggest_mismatched_types_on_tail
  27: <rustc_typeck::check::coercion::CoerceMany<'gcx, 'tcx, 'exprs, E>>::coerce_inner
  28: rustc_typeck::check::FnCtxt::check_block_with_expected
  29: rustc_typeck::check::FnCtxt::check_expr_kind
  30: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_needs
  31: rustc_typeck::check::FnCtxt::check_return_expr
  32: rustc_typeck::check::check_fn
  33: rustc::ty::context::GlobalCtxt::enter_local
  34: rustc_typeck::check::typeck_tables_of
  35: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::typeck_tables_of<'tcx>>::compute
  36: rustc::dep_graph::graph::DepGraph::with_task_impl
  37: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_get_with
  38: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::ensure_query
  39: rustc::session::Session::track_errors
  40: rustc_typeck::check::typeck_item_bodies
  41: rustc::ty::query::__query_compute::typeck_item_bodies
  42: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::typeck_item_bodies<'tcx>>::compute
  43: rustc::dep_graph::graph::DepGraph::with_task_impl
  44: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_get_with
  45: rustc::util::common::time
  46: rustc_typeck::check_crate
  47: <std::thread::local::LocalKey<T>>::with
  48: rustc::ty::context::TyCtxt::create_and_enter
  49: rustc_driver::driver::compile_input
  50: rustc_driver::run_compiler_with_pool
  51: <scoped_tls::ScopedKey<T>>::set
  52: rustc_driver::run_compiler
  53: <scoped_tls::ScopedKey<T>>::set
query stack during panic:
#0 [typeck_tables_of] processing `ice`
#1 [typeck_item_bodies] type-checking all item bodies
end of query stack

[sapphire-arches]

I think I just ran into this bug as well. It's repros in the 2018-12-31 nightly.

[hellow554]

The bug was introduced in nightly-2018-12-21, so somewhere between 790f4c5...09d6ab9

[LukasKalbertodt]

This could possibly be the same bug as #57216. At least the stack trace and panic message is very similar.

[pnkfelix]

triage: P-high; assigning to self.

[pnkfelix]

This was injected by #54252

cc @arielb1

[pnkfelix]

(the ICE seems like it may have been injected by commit be2bb4f specifically.)

[pnkfelix]

I have been looking at this more. I am not 100% certain I understand the steps that are leading to the ICE, but here are some notes and hypotheses based on adding some debug! statements to various points in the compiler and reading the resulting logs:

• The ICE is due to creating an inference variable (or vid) named _#527t and eventually attempting a lookup based on that inference variable on an eq_relations table with only 527 entries.
  • This is all part of the snapshotting system where we extend tables when we create new type variables.
  • Such extensions must be either committed or rolled back. When you rollback, you are supposed to not keep around the type variables that we created during a particular extension.
  • So we must be leaking state (i.e. the _#527t) during one of the extensions and then attempting to do a lookup based on that leaked state.
• There are four spots in the log where we create the vid _#527t. I cannot be certain which of the four is leaky.
  • (It might be nice to create a debugging variant of the snapshot system that doesn't reuse indices, and instead just marks table entries as popped, to help deal with this problem. But maybe I'm just looking at this through the lens of a Garbage Collection problem.)
• The three of the spots that create _#527t falling latest in the control flow (i.e. appear later in the log) are underneath the execution of probe_for_lev_candidate when it is searching for a candidate similar to rfold.
  • I have not yet exactly pinned down a tidy way to identify where the remaining _#527t (that falls a little earlier in the control flow) comes from.
  • Update: It might be arising during a pick_method invocation for self_ty: &mut (dyn std::iter::Iterator<Item=()> + 'static)) method_name: Some(rfold#0) and return_type: Some(()). (There's that rfold again.)
  • Specifically while searching the extension candidates, since the variable is created and then discarded before we see the debug! statement for "searching unstable candidates".
    

    rust/src/librustc_typeck/check/method/probe.rs

    Lines 1046 to 1051 in 0974bdc

    	for (kind, candidates) in &[
    	("inherent", &self.inherent_candidates),
    	("extension", &self.extension_candidates),
    	] {
    	debug!("searching {} candidates", kind);
    	let res = self.consider_candidates(

    
    

    rust/src/librustc_typeck/check/method/probe.rs

    Lines 1069 to 1072 in 0974bdc

    	}
    	debug!("searching unstable candidates");
    	let res = self.consider_candidates(

[pnkfelix]

(also, am I wrong in feeling my eyebrows go up when I observe that the compiler is attempting to search for candidates similar to the method name rfold when it is trying to construct a diagnostic for this code? I guess I shouldn't worry too much yet, since diagnostic generation need not be considered a hot path. But it still struck me as odd.)

[pnkfelix]

Anyway, just to narrow the search space for the bug, I'm going to hack probe_for_lev_candidate so that it never attempts to search beyond an empty set. That should allow me to identify whether the problematic vid _#527t is arising from the initial probe, or if it is arising from a probe underneath probe_for_lev_candidate.

Update: No, this probably won't suffice: the ICE is itself arising, I think, during the execution of probe_for_lev_candidate. So I suspect changing that method to only search an empty vector (or otherwise failing to call it, etc) will just mask the bug here.

[pnkfelix]

Okay, i think I have a hint at the problem

More debug log inspection has led me to conclude that the problematic vid _#527t is part of the inherent candidates attached to the ProbeContext.

Look at this code:

rust/src/librustc_typeck/check/method/probe.rs

Lines 507 to 517 in 0974bdc

	ty::Dynamic(ref data, ..) => {
	if let Some(p) = data.principal() {
	self.fcx.probe(|_| {
	let InferOk { value: self_ty, obligations: _ } =
	self.fcx.probe_instantiate_query_response(
	self.span, &self.orig_steps_var_values, self_ty)
	.unwrap_or_else(|_| {
	span_bug!(self.span, "{:?} was applicable but now isn't?", self_ty)
	});
	self.assemble_inherent_candidates_from_object(self_ty);
	});

• git blame notes this was updated by PR Add support for trait-objects without a principal #56837; but it was injected by process nested obligations in autoderef #54252.

During the execution of:

rust/src/librustc_typeck/check/method/probe.rs

Line 516 in 0974bdc

self.assemble_inherent_candidates_from_object(self_ty);

is when the vid _#527t is created and then pushed (as part of a candidate) onto the inherent candidates list attached to self. But then the callback for self.fcx.probe(|_| { ... }) returns, and as part of exiting the probe call, it does a rollback, which pops off the entries for the newly created inference variables _#527t and _#528t.

Sometime well after this point, we attempt to look at the inherent candidates (during probe_for_lev_candidate) and that's when we try to do a look up based on #_527t, but its effectively a dangling pointer into the eq_relations table at that point.

So, I am pretty sure the code for the ty::Dynamic case in fn assemble_probe is in error here. Or at least, its behavior doesn't match my understanding of how the probes are meant to be used.

Now my question is: How to fix this?

[pnkfelix]

Okay well as an experiment, I have tried just removing the wrapping call to self.fcx.probe(|_| { ... }), and so far ... nothing breaks? (And it resolves this particular instance of the bug, at least....)

[pnkfelix]

(this bug wasn't fixed in time for the nightly-to-beta promotion and so its now affecting beta)

[pnkfelix]

PR #57835 fixes this problem and has been nominated for beta-backport.

However, @arielb1 thinks that it is an insufficient solution and says they hope to have a better approach up soonish.

Thus, we might not want to do an eager backport of PR #57835, since it would probably be nicer to make a single backport that includes both the effect of that PR as well as the hypothetical PR to be provided by @arielb1

[pnkfelix]

visiting for triage: PR #57885 is a related follow-up to #57835. We'll hopefully discuss the hypothetical backport of PR #57835 at the T-compiler meeting today.

[pnkfelix]

visiting for triage. PR #57885 was beta-nominated and beta-accepted. If I recall correctly PR #57835 is a prerequisite for landing PR #57885. So I'll make sure a backport gets posted for both of those in the near future.

[pnkfelix]

closing bug now that PRs #57835 and #57885 have landed in beta-channel.