Invalid closure lifetime inference

[phaylon]

I'm experimenting with a parser combinator and ran into an issue with closure lifetime inference.

This might be a duplicate of #39943, since it uses a similar (but simpler) mechanism to produce the same error message. However, in the code below the error is potentially a lot further away, and since I need to return values from the closure I'm having trouble finding any way to make it work by explicitly specifying a signature. Since it involves more moving parts, I'm also not sure how to confirm if the underlying issue is the same.

I removed all parts that aren't involved in triggering the error message (the original use case has trait methods with related return types).

It comes down to the following error message:

rustc 1.16.0 (30cf806ef 2017-03-10)
error: `content` does not live long enough
  --> <anon>:64:1
   |
62 |         let _ = apply(&content, parser);
   |                        ------- borrow occurs here
63 |     };
64 | }
   | ^ `content` dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created

error: aborting due to previous error

And here is the triggering code:

trait Parse<'input> {

    type Output;
}

// needs one parser which has its Output depending on the input
struct AnyParser;

impl<'input> Parse<'input>
for AnyParser {

    type Output = &'input str;
}

// also needs another parser taking a closure that takes a subparsers
// result
fn fold<P, I, F>(parser: P, init: I, fold: F) -> Fold<P, I, F>
{
    Fold {
        parser: parser,
        init: init,
        fold: fold,
    }
}

struct Fold<P, I, F> {
    parser: P,
    init: I,
    fold: F,
}

impl<'input, P, I, F, T> Parse<'input>
for Fold<P, I, F>
where
    P: Parse<'input>,
    I: Fn() -> T,
    F: Fn(T, P::Output) -> T,
{
    type Output = T;
}

// taking the content and the parser together
fn apply<'input, P>(input: &'input str, parser: P)
where
    P: Parse<'input>,
{
    unimplemented!();
}

fn main() {
    let parser = fold(
        AnyParser,
        // these closures seems to make it think the parser holds on to
        // the AnyParser result (which is part of the input)
        || None,
        |_, v| Some(v),
    );
    // rustc says this must outlive the parser, which is unfortunate
    let content: String = "foo".into();
    {
        let _ = apply(&content, parser);
    };
}

[phaylon]

After some experimentation, I tried a possible fix, which lead to an ICE.

I changed

impl<'input, P, I, F, T> Parse<'input>
for Fold<P, I, F>
where
    P: Parse<'input>,
    I: Fn() -> T,
    F: Fn(T, P::Output) -> T,
{
    type Output = T;
}

to

impl<'input, P, I, F, T> Parse<'input>
for Fold<P, I, F>
where
    P: Parse<'input>,
    I: Fn() -> T,
    // changed to give the ::Output its own lifetime
    F: for<'x> Fn(T, <P as Parse<'x>>::Output) -> T,
{
    type Output = T;
}

which gives me:

error: internal compiler error: /checkout/src/librustc/traits/project.rs:1256: Failed to unify obligation `Obligation(predicate=ProjectionTy { trait_ref: <[closure@src/lib.rs:66:9: 66:23] as std::ops::FnOnce<(std::option::Option<_>, <AnyParser<'_> as Parse<'x>>::Output)>>, item_name: Output(87) },depth=1)` with poly_projection `Binder(ProjectionPredicate(ProjectionTy { trait_ref: <[closure@src/lib.rs:66:9: 66:23] as std::ops::FnOnce<(std::option::Option<_>, &str)>>, item_name: Output(87) }, std::option::Option<_>))`: Sorts(ExpectedFound { expected: &str, found: <AnyParser<'_> as Parse<'x>>::Output })
  --> src/lib.rs:70:17
   |
70 |         let _ = apply(&content, parser);
   |                 ^^^^^

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: run with `RUST_BACKTRACE=1` for a backtrace

My rustc --version --verbose is:

rustc 1.18.0-nightly (1785bca51 2017-04-21)
binary: rustc
commit-hash: 1785bca5137fad1f26e4d3c347cbb68408a28fa9
commit-date: 2017-04-21
host: x86_64-unknown-linux-gnu
release: 1.18.0-nightly
LLVM version: 3.9

And here is the RUST_BACKTRACE:

thread 'rustc' panicked at 'Box<Any>', /checkout/src/librustc_errors/lib.rs:375
stack backtrace:
   0: std::sys::imp::backtrace::tracing::imp::unwind_backtrace
             at /checkout/src/libstd/sys/unix/backtrace/tracing/gcc_s.rs:49
   1: std::sys_common::backtrace::_print
             at /checkout/src/libstd/sys_common/backtrace.rs:71
   2: std::panicking::default_hook::{{closure}}
             at /checkout/src/libstd/sys_common/backtrace.rs:60
             at /checkout/src/libstd/panicking.rs:355
   3: std::panicking::default_hook
             at /checkout/src/libstd/panicking.rs:365
   4: std::panicking::rust_panic_with_hook
             at /checkout/src/libstd/panicking.rs:549
   5: std::panicking::begin_panic
   6: rustc::session::opt_span_bug_fmt::{{closure}}
   7: rustc::session::opt_span_bug_fmt
   8: rustc::session::span_bug_fmt
   9: rustc::traits::project::confirm_param_env_candidate
  10: rustc::traits::project::confirm_callable_candidate
  11: rustc::traits::project::confirm_closure_candidate
  12: rustc::traits::project::confirm_candidate
  13: rustc::traits::project::opt_normalize_projection_type
  14: rustc::traits::project::poly_project_and_unify_type::{{closure}}
  15: rustc::traits::project::poly_project_and_unify_type
  16: <rustc::traits::fulfill::FulfillProcessor<'a, 'b, 'gcx, 'tcx> as rustc_data_structures::obligation_forest::ObligationProcessor>::process_obligation
  17: <rustc_data_structures::obligation_forest::ObligationForest<O>>::process_obligations
  18: rustc::traits::fulfill::FulfillmentContext::select_where_possible
  19: rustc_typeck::check::FnCtxt::select_obligations_where_possible
  20: rustc_typeck::check::FnCtxt::check_argument_types
  21: rustc_typeck::check::callee::<impl rustc_typeck::check::FnCtxt<'a, 'gcx, 'tcx>>::confirm_builtin_call
  22: rustc_typeck::check::callee::<impl rustc_typeck::check::FnCtxt<'a, 'gcx, 'tcx>>::check_call
  23: rustc_typeck::check::FnCtxt::check_expr_kind
  24: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref
  25: rustc_typeck::check::FnCtxt::check_decl_initializer
  26: rustc_typeck::check::FnCtxt::check_decl_local
  27: rustc_typeck::check::FnCtxt::check_stmt
  28: rustc_typeck::check::FnCtxt::check_block_with_expected::{{closure}}
  29: rustc_typeck::check::FnCtxt::check_block_with_expected
  30: rustc_typeck::check::FnCtxt::check_expr_kind
  31: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref
  32: rustc_typeck::check::FnCtxt::check_stmt
  33: rustc_typeck::check::FnCtxt::check_block_with_expected::{{closure}}
  34: rustc_typeck::check::FnCtxt::check_block_with_expected
  35: rustc_typeck::check::FnCtxt::check_expr_kind
  36: rustc_typeck::check::FnCtxt::check_expr_with_expectation_and_lvalue_pref
  37: rustc_typeck::check::FnCtxt::check_return_expr
  38: rustc_typeck::check::check_fn
  39: rustc_typeck::check::typeck_tables
  40: rustc::ty::maps::<impl rustc::ty::maps::queries::typeck_tables<'tcx>>::try_get
  41: rustc::ty::maps::<impl rustc::ty::maps::queries::typeck_tables<'tcx>>::get
  42: rustc::ty::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::item_tables
  43: rustc_typeck::check::typeck_item_bodies
  44: rustc::ty::maps::<impl rustc::ty::maps::queries::typeck_item_bodies<'tcx>>::try_get
  45: rustc::ty::maps::<impl rustc::ty::maps::queries::typeck_item_bodies<'tcx>>::get
  46: rustc_typeck::check_crate
  47: rustc_driver::driver::phase_3_run_analysis_passes::{{closure}}
  48: rustc::ty::context::TyCtxt::create_and_enter
  49: rustc_driver::driver::phase_3_run_analysis_passes
  50: rustc_driver::driver::compile_input
  51: rustc_driver::run_compiler
  52: std::panicking::try::do_call
  53: __rust_maybe_catch_panic
             at /checkout/src/libpanic_unwind/lib.rs:98
  54: <F as alloc::boxed::FnBox<A>>::call_box
  55: std::sys::imp::thread::Thread::new::thread_start
             at /checkout/src/liballoc/boxed.rs:650
             at /checkout/src/libstd/sys_common/thread.rs:21
             at /checkout/src/libstd/sys/unix/thread.rs:84
  56: start_thread
  57: clone

[kennytm]

The ICE reduced:

trait T<'x> {
    type V;
}
impl<'g> T<'g> for u32 {
    type V = u16;
}
fn main() {
    (&|_|()) as &for<'x> Fn(<u32 as T<'x>>::V);
}

[steveklabnik]

Triage: still ICEs

[estebank]

Still ICEs:

error[E0631]: type mismatch in closure arguments
 --> src/main.rs:8:5
  |
8 |     (&|_|()) as &for<'x> Fn(<u32 as T<'x>>::V);
  |     ^^-----^
  |     | |
  |     | found signature of `fn(u16) -> _`
  |     expected signature of `fn(<u32 as T<'x>>::V) -> _`
  |
  = note: required for the cast to the object type `dyn for<'x> std::ops::Fn(<u32 as T<'x>>::V)`

thread 'rustc' panicked at 'assertion failed: !ty.needs_infer() && !ty.has_placeholders()', src/librustc_typeck/check/writeback.rs:119:9
note: Some details are omitted, run with `RUST_BACKTRACE=full` for a verbose backtrace.
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::begin_panic
   7: rustc_typeck::check::writeback::WritebackCx::visit_node_id
   8: <rustc_typeck::check::writeback::WritebackCx<'cx, 'gcx, 'tcx> as rustc::hir::intravisit::Visitor<'gcx>>::visit_expr
   9: rustc::hir::intravisit::walk_expr
  10: <rustc_typeck::check::writeback::WritebackCx<'cx, 'gcx, 'tcx> as rustc::hir::intravisit::Visitor<'gcx>>::visit_expr
  11: rustc::hir::intravisit::walk_expr
  12: <rustc_typeck::check::writeback::WritebackCx<'cx, 'gcx, 'tcx> as rustc::hir::intravisit::Visitor<'gcx>>::visit_expr
  13: rustc_typeck::check::writeback::<impl rustc_typeck::check::FnCtxt<'a, 'gcx, 'tcx>>::resolve_type_vars_in_body
  14: rustc::ty::context::GlobalCtxt::enter_local
  15: rustc_typeck::check::typeck_tables_of
  16: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::typeck_tables_of<'tcx>>::compute
  17: rustc::dep_graph::graph::DepGraph::with_task_impl
  18: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_get_with
  19: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::ensure_query
  20: rustc::session::Session::track_errors
  21: rustc_typeck::check::typeck_item_bodies
  22: rustc::ty::query::__query_compute::typeck_item_bodies
  23: rustc::ty::query::<impl rustc::ty::query::config::QueryAccessors<'tcx> for rustc::ty::query::queries::typeck_item_bodies<'tcx>>::compute
  24: rustc::dep_graph::graph::DepGraph::with_task_impl
  25: rustc::ty::query::plumbing::<impl rustc::ty::context::TyCtxt<'a, 'gcx, 'tcx>>::try_get_with
  26: rustc::util::common::time
  27: rustc_typeck::check_crate
  28: <std::thread::local::LocalKey<T>>::with
  29: rustc::ty::context::TyCtxt::create_and_enter
  30: rustc_driver::driver::compile_input
  31: rustc_driver::run_compiler_with_pool
  32: <scoped_tls::ScopedKey<T>>::set
  33: rustc_driver::run_compiler
  34: <scoped_tls::ScopedKey<T>>::set
query stack during panic:
#0 [typeck_tables_of] processing `main`
#1 [typeck_item_bodies] type-checking all item bodies
end of query stack
error: aborting due to previous error

[JohnTitor]

The reduced example doesn't show the ICE, from 1.35.0 (tested on godbolt). Marked as E-needstest

[estebank]

And the original code is now accepted, so adding tests is enough to close this ticket.