Confusing lifetime issues when returning `impl Fn`

Question

I have been trying to understand some lifetime conflicts relating to a function I've written that returns impl Fn. Let's start at the beginning. I have the following code file that won't compile:

use nom::bytes::complete::is_not;
use nom::character::complete::multispace0;
use nom::combinator::verify;
use nom::error::{
    ParseError,
    VerboseError,
};
use nom::sequence::terminated;
use nom::IResult;

fn one_token<'a, E>(input: &'a str) -> IResult<&str, &str, E>
where
    E: ParseError<&'a str>,
{
    terminated(is_not(" \t\r\n"), multispace0)(input)
}

fn str_token<'a, E>(expected_string: String) -> impl Fn(&'a str) -> IResult<&str, &str, E>
where
    E: ParseError<&'a str>,
{
    verify(one_token, move |actual_string| {
        actual_string == expected_string
    })
}

fn main() {
    let parser_1 = str_token::<VerboseError<_>>("foo".into());
    let string = "foo bar".to_string();
    let input = &string[..];
    let parser_2 = str_token::<VerboseError<_>>("foo".into());

    println!("{:?} {:?}", parser_1(input), parser_2(input),);
}

I get this error message:

error[E0597]: `string` does not live long enough
  --> src/main.rs:30:18
   |
30 |     let input = &string[..];
   |                  ^^^^^^ borrowed value does not live long enough
...
34 | }
   | -
   | |
   | `string` dropped here while still borrowed
   | borrow might be used here, when `parser_1` is dropped and runs the destructor for type `impl std::ops::Fn<(&str,)>`
   |
   = note: values in a scope are dropped in the opposite order they are defined

It appears that the returned impl Fn assigned to parser_1 only works for values whose lifetimes are at least as long as the parser_1 variable. This violates my expectation that parser_1 would work with a variable of any lifetime. I initially suspected that this might have been due to some interaction between the lifetime parameter 'a on str_token and the error type parameter E. So I just made the error type explicit:

fn one_token(input: &str) -> IResult<&str, &str, VerboseError<&str>> {
    terminated(is_not(" \t\r\n"), multispace0)(input)
}

fn str_token<'a>(
    expected_string: String,
) -> impl Fn(&'a str) -> IResult<&str, &str, VerboseError<&str>> {
    verify(one_token, move |actual_string| {
        actual_string == expected_string
    })
}

This didn't fix the problem. It causes the exact same compilation error. So then I tried modifying str_token to use higher-rank trait bounds:

fn str_token(
    expected_string: String,
) -> impl for<'a> Fn(&'a str) -> IResult<&str, &str, VerboseError<&str>> {
    verify(one_token, move |actual_string| {
        actual_string == expected_string
    })
}

But then I get this error:

error[E0277]: expected a `std::ops::Fn<(&'a str,)>` closure, found `impl std::ops::Fn<(&str,)>`
  --> src/main.rs:14:6
   |
14 | ) -> impl for<'a> Fn(&'a str) -> IResult<&str, &str, VerboseError<&str>> {
   |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected an `Fn<(&'a str,)>` closure, found `impl std::ops::Fn<(&str,)>`
   |
   = help: the trait `for<'a> std::ops::Fn<(&'a str,)>` is not implemented for `impl std::ops::Fn<(&str,)>`
   = note: the return type of a function must have a statically known size

error[E0271]: type mismatch resolving `for<'a> <impl std::ops::Fn<(&str,)> as std::ops::FnOnce<(&'a str,)>>::Output == std::result::Result<(&'a str, &'a str), nom::internal::Err<nom::error::VerboseError<&'a s
tr>>>`
  --> src/main.rs:14:6
   |
14 | ) -> impl for<'a> Fn(&'a str) -> IResult<&str, &str, VerboseError<&str>> {
   |      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected bound lifetime parameter 'a, found concrete lifetime
   |
   = note: the return type of a function must have a statically known size

And, frankly, I have basically no idea how to interpret that. Can anyone comment on what's going on here? Why would the lifetime of a returned impl Fn be bound to the lifetime of the factory function that produced it even when its behavior doesn't actually depend on that lifetime? How can I fix this problem and still use an impl Fn return value? Why aren't HRTBs working when it seems like the perfect application of them? I'm pretty lost here.

By the way, I'm using the nom parsing library found here: https://github.com/Geal/nom/

Also, the code for the verify function is here: https://github.com/Geal/nom/blob/851706460a9311f7bbae8e9b7ee497c7188df0a3/src/combinator/mod.rs#L459

And if anyone wants to play around with a cargo project containing all these examples, there's one here: https://github.com/davesque/nom-test/

You can clone it, checkout the first-version, no-error-parameter, or higher-rank-trait-bounds tags, and invoke cargo run.

Note:

I asked a similar question recently here: How to use higher-rank trait bounds to make a returned impl Fn more generic?

However, I eventually decided this question wasn't specific enough to what I was actually trying to do. Someone had already answered it, so I didn't want to make a big edit and cause the answer to become confusing and apparently unrelated to my question.

Answer 1

When you have a function/struct/trait with a lifetime like <'a>, it implies that any reference marked as 'a must outlive the function/struct/trait. Outliving means (among other things) that the thing that has been referenced must have already existed before the function was called/struct was created/item implementing the trait has been created. The reference can't be created later, because it'd mean its lifetime started later than required.

In your case, str_token<'a> means the string marked by &'a str must have been created and already exist before str_token function was called.

Your code violates the requirement that you have:

 let parser_1 = str_token::<VerboseError<_>>("foo".into());
 let input = &string[..];

because parser_1 has been created before the input, but the lifetime annotation on it allows it to be used only with strings crated before the parser.

If you swap order of these lines, it should work.

for<'b> impl Fn(&'b str) would be more flexible, because it means a lifetime is defined "on the fly" for whatever you use this function with, so any lifetime would work. But the library you're working with apparently requires the less flexible method, perhaps for a good reason that isn't directly related to your usage.

Here's a minimal test case:

fn parser<'a>() -> impl Fn(&'a str) -> &str {
    |a| a
}

fn main() {
    let s1 = String::new();
    let p = parser();
    let s2 = String::new();
    p(&s1);
    //p(&s2);
}