librustc_mir/borrow_check/nll/universal_regions.rs:824: cannot convert ReFree ...

[Palmik]

NLL

I tried this code:

impl Struct {
    pub fn produce<'a>(&self, x: &'a mut X) -> impl Future<Item = (), Error = Y> + 'a
    {
        futures::future::loop_fn((), move |_| {
            // Adding the following line causes the crash.
            // Without the line the code does not compile, because:
            // free region `` does not outlive free region `'_#1r`
            let x: &'a mut X = x; 
            Self::produce_once(x).map(|_| futures::future::Loop::Continue(()))
        })
    }

    pub fn produce_once<'a>(x: &'a mut X) -> impl Future<Item = (), Error = Y> + 'a {
        unimpemented!()
    }
}

I expected to see this happen: To not cause panic in the compiler.

Instead, this happened: Panic.

error: internal compiler error: librustc_mir/borrow_check/nll/universal_regions.rs:824: cannot convert `ReFree(DefId(0/0:1083 ~ project[9bca]::some[0]::very[0]::deep[0]::module[0]::{{impl}}[0]::produce[0]), BrNamed(crate0:DefIndex(1:271), 'a))` to a region vid

thread 'main' panicked at 'Box<Any>', librustc_errors/lib.rs:554:9
note: Run with `RUST_BACKTRACE=1` for a backtrace.
error: aborting due to previous error

These are the enabled features:

#![feature(associated_type_defaults)]
#![feature(core_intrinsics)]
#![feature(entry_or_default)]
#![feature(nll)]
#![feature(optin_builtin_traits)]
#![feature(specialization)]
#![feature(transpose_result)]
#![feature(try_from)]

Meta

rustc --version --verbose:

rustc 1.27.0-nightly (e5f80f2a4 2018-05-09)
binary: rustc
commit-hash: e5f80f2a4f016bf724a1cfb580619d71c8fd39ec
commit-date: 2018-05-09
host: x86_64-unknown-linux-gnu
release: 1.27.0-nightly
LLVM version: 6.0

Backtrace:

thread 'main' panicked at 'Box<Any>', librustc_errors/lib.rs:554:9
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
             at libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::print
             at libstd/sys_common/backtrace.rs:71
             at libstd/sys_common/backtrace.rs:59
   2: std::panicking::default_hook::{{closure}}
             at libstd/panicking.rs:211
   3: std::panicking::default_hook
             at libstd/panicking.rs:227
   4: rustc::util::common::panic_hook
   5: std::panicking::rust_panic_with_hook
             at libstd/panicking.rs:467
   6: std::panicking::begin_panic
   7: rustc_errors::Handler::bug
   8: rustc::session::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::session::opt_span_bug_fmt
  13: rustc::session::bug_fmt
  14: rustc_mir::borrow_check::nll::universal_regions::UniversalRegionIndices::to_region_vid::{{closure}}
  15: rustc_mir::borrow_check::nll::universal_regions::UniversalRegionIndices::to_region_vid
  16: rustc_mir::borrow_check::nll::subtype_constraint_generation::generate
  17: rustc_mir::borrow_check::nll::compute_regions
  18: rustc_mir::borrow_check::do_mir_borrowck
  19: rustc::ty::context::tls::with_related_context
  20: rustc::infer::InferCtxtBuilder::enter
  21: rustc_mir::borrow_check::mir_borrowck
  22: rustc::ty::maps::<impl rustc::ty::maps::config::QueryConfig<'tcx> for rustc::ty::maps::queries::mir_borrowck<'tcx>>::compute
  23: rustc::ty::context::tls::with_context
  24: rustc::dep_graph::graph::DepGraph::with_task_impl
  25: rustc::ty::context::tls::with_related_context
  26: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  27: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  28: rustc::ty::maps::<impl rustc::ty::context::TyCtxt<'a, 'tcx, 'lcx>>::mir_borrowck
  29: rustc_mir::borrow_check::nll::type_check::type_check_internal
  30: rustc_mir::borrow_check::nll::type_check::type_check
  31: rustc_mir::borrow_check::nll::compute_regions
  32: rustc_mir::borrow_check::do_mir_borrowck
  33: rustc::ty::context::tls::with_related_context
  34: rustc::infer::InferCtxtBuilder::enter
  35: rustc_mir::borrow_check::mir_borrowck
  36: rustc::ty::maps::<impl rustc::ty::maps::config::QueryConfig<'tcx> for rustc::ty::maps::queries::mir_borrowck<'tcx>>::compute
  37: rustc::ty::context::tls::with_context
  38: rustc::dep_graph::graph::DepGraph::with_task_impl
  39: rustc::ty::context::tls::with_related_context
  40: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::force_query_with_job
  41: rustc::ty::maps::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::get_query
  42: rustc::ty::maps::<impl rustc::ty::context::TyCtxt<'a, 'tcx, 'lcx>>::mir_borrowck
  43: rustc_driver::driver::phase_3_run_analysis_passes::{{closure}}::{{closure}}
  44: rustc::ty::context::tls::enter_context
  45: <std::thread::local::LocalKey<T>>::with
  46: rustc::ty::context::TyCtxt::create_and_enter
  47: rustc_driver::driver::compile_input
  48: rustc_driver::run_compiler_impl
  49: <scoped_tls::ScopedKey<T>>::set
  50: syntax::with_globals
  51: <std::panic::AssertUnwindSafe<F> as core::ops::function::FnOnce<()>>::call_once
  52: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:105
  53: rustc_driver::run
  54: rustc_driver::main
  55: std::rt::lang_start::{{closure}}
  56: std::panicking::try::do_call
             at libstd/rt.rs:59
             at libstd/panicking.rs:310
  57: __rust_maybe_catch_panic
             at libpanic_unwind/lib.rs:105
  58: std::rt::lang_start_internal
             at libstd/panicking.rs:289
             at libstd/panic.rs:374
             at libstd/rt.rs:58
  59: main
  60: __libc_start_main
  61: <unknown>
query stack during panic:
#0 [mir_borrowck] processing `some::very::deep::module::Struct::produce::{{closure}}`
#1 [mir_borrowck] processing `some::very::deep::module::Struct::produce`
end of query stack
error: aborting due to previous error


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

[matthewjasper]

Self contained example

#![feature(nll)]

fn produce<'a>()
{
    move || {
        let x: &'a () = &();
    };
}


fn main() {}

[DutchGhost]

no need for a move, or closure, just the let expression already ICE's

#![feature(nll)]

fn crash<'a>() {
    let x: &'a () = &();
}

fn main() {}

[kennytm]

Alternative repro taken from #51676:

#![feature(nll)]

fn crash<'a>() {
    let x: &'a str = "?";
}

fn main() {}

[nikomatsakis]

High priority, blocks bootstrap too

[nikomatsakis]

OK, so, I remember this problem. It's a pain in the neck, but we gotta fix it. The problem is that we categorize 'a as a "late bound region" -- but it doesn't appear in any of the arguments. I'm actually a bit surprised about this, since the definition of when something is "late-bound" would seem to exclude 'a:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 2481 to 2483 in 860d169

	/// A region declared on a fn is **late-bound** if:
	/// - it is constrained by an argument type;
	/// - it does not appear in a where-clause.

However, the actual definition used in the code is a bit broader:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 2548 to 2558 in 860d169

	// appears in the where clauses? early-bound.
	if appears_in_where_clause.regions.contains(&lt_name) {
	continue;
	}
	// does not appear in the inputs, but appears in the return type? early-bound.
	if !constrained_by_input.regions.contains(&lt_name)
	&& appears_in_output.regions.contains(&lt_name)
	{
	continue;
	}

The reason that being late-bound makes a difference is because of how the universal regions code tries to instantiate and find all the lifetime parameters. It begins by looking the "generics" for the function: those include the early-bound regions. Then it instantiates all the remaining free regions that appear in the argument types -- that is supposed to capture the late-bound regions. But for a region like 'a, it gets overlooked.

The resolve_lifetime code actually does create a (sort of) complete list of late-bound regions, as part of the NamdRegionMap:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 195 to 215 in 860d169

	/// Maps the id of each lifetime reference to the lifetime decl
	/// that it corresponds to.
	///
	/// FIXME. This struct gets converted to a `ResolveLifetimes` for
	/// actual use. It has the same data, but indexed by `DefIndex`. This
	/// is silly.
	#[derive(Default)]
	struct NamedRegionMap {
	// maps from every use of a named (not anonymous) lifetime to a
	// `Region` describing how that region is bound
	pub defs: NodeMap<Region>,
	// the set of lifetime def ids that are late-bound; a region can
	// be late-bound if (a) it does NOT appear in a where-clause and
	// (b) it DOES appear in the arguments.
	pub late_bound: NodeSet,
	// For each type and trait definition, maps type parameters
	// to the trait object lifetime defaults computed from them.
	pub object_lifetime_defaults: NodeMap<Vec<ObjectLifetimeDefault>>,
	}

In particular, the late_bound field stores the def-id of each named lifetime parameter that will be late-bound:

rust/src/librustc/middle/resolve_lifetime.rs

Lines 207 to 210 in 860d169

	// the set of lifetime def ids that are late-bound; a region can
	// be late-bound if (a) it does NOT appear in a where-clause and
	// (b) it DOES appear in the arguments.
	pub late_bound: NodeSet,

This can be accessed via the named_region_map query.

(Annoyingly, that field doesn't contain all late-bound regions -- only the named ones. Anonymous ones are found later, during type conversion.)

What we would have to do is extend the UniversalRegions code. Currently, it replaces all late-bound regions in the input types with NLL region variables here:

rust/src/librustc_mir/borrow_check/nll/universal_regions.rs

Lines 458 to 463 in 860d169

	let inputs_and_output = self.infcx.replace_bound_regions_with_nll_infer_vars(
	FR,
	self.mir_def_id,
	&bound_inputs_and_output,
	&mut indices,
	);

After this step, we need to load the full set of named, late-bound regions and then check for each of them whether they were found amongst the types -- or maybe we should just add a new field to the NamedRegionMap containing those late-bound regions that do not appear in the types, since we're already doing the search? Actually, let's just do that.

[nikomatsakis]

OK, that was a first round of mentoring instructions, but there are maybe 50% notes to myself and not necessarily expected to be understood. Still, nominating for this week, and I can try to leave better notes.

[mikhail-m1]

look at it

[nikomatsakis]

So @mikhail-m1 I was looking over this issue again and it occurs to me that I think that the bug in the original issue may not be solved by my proposed fix (though some of the minimizations will be, I think). I'm going to look a bit into that and maybe split off a second issue with a different minimization.

[nikomatsakis]

Should be fixed now