Boxed trait objects & strings: cannot infer an appropriate lifetime for autoref due to conflicting requirements

Hey all, pretty new to Rust. I've been working through the book, and when I read the chapter on trait objects I was itching to go back and change the minigrep project to use a generic Iterator<Item=&'a str> type rather than the concrete Vec<&'a str> of the examples.

(Why? I like the C#/Clojure—and maybe Haskell?—style of passing lazy iterators around. It fits in better with my functional thinking, personally, and calling .collect() all the time nags me.)

At any rate, I've got the following code, and I can't quite identify why it won't compile—I know Rust thinks the lifetime should be 'static, but I can't see why, how to fix it, or why it's the .lines() line that is identified as the issue. I read a similar post, but adding + 'a only makes the error message longer.

I've not yet converted the run function to return a boxed iterator, so it still calls .collect(). I've omitted the tests. I've given some additional code at the top of the file that I don't think is representative of the issue, but may be nice if you want to drop this in a file and run rustc or cargo build on it.

I've included the error message afterwards.

Please let me know if additional details would help resolve the problem. I'm not looking for the solution to get things done :tm:, but rather an explanation so I can learn from this.

use std::error::*;
use std::fs;

#[derive(Debug)]
pub struct Config {
    pub query: String,
    pub filename: String,
    pub case_sensitive: bool,
}

impl Config {
    pub fn new(mut args: std::env::Args, case_sensitive: bool) -> Result<Config, String> {
        args.next(); // eat the program name
        args.next()
            .map_or(Err(String::from("missing query")), |query| {
                args.next()
                    .map_or(Err(String::from("missing filename")), |filename| {
                        Ok(Config {
                            query,
                            filename,
                            case_sensitive,
                        })
                    })
            })
    }
}

pub fn run(conf: Config) -> Result<Vec<String>, Box<dyn Error>> {
    let contents = fs::read_to_string(&conf.filename)?;
    let search_fn = if conf.case_sensitive {
        search
    } else {
        search_case_insensitive
    };
    Ok(search_fn(&conf.query, &contents)
        .enumerate()
        .map(|(num, line)| format!("{}:{}:{}", conf.filename, num, line))
        .collect())
}

pub fn search<'a>(query: &str, contents: &'a str) -> Box<dyn Iterator<Item = &'a str>> {
    search_backend(query, contents, |x| x.to_string())
}

pub fn search_case_insensitive<'a>(
    query: &str,
    contents: &'a str,
) -> Box<dyn Iterator<Item = &'a str>> {
    search_backend(&query.to_lowercase(), contents, |line| line.to_lowercase())
}

fn search_backend<'a, F>(
    query: &str,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str>>
where
    F: Fn(&&str) -> String,
{
    Box::new(
        contents
            .lines()
            .filter(|line| line_pp(line).contains(&query)),
    )
}

// tests omitted
   Compiling minigrep v0.1.0 (/Users/Knoble/code/rust/minigrep)
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/lib.rs:62:14
   |
62 |             .lines()
   |              ^^^^^
   |
note: first, the lifetime cannot outlive the lifetime `'a` as defined on the function body at 52:19...
  --> src/lib.rs:52:19
   |
52 | fn search_backend<'a, F>(
   |                   ^^
note: ...so that reference does not outlive borrowed content
  --> src/lib.rs:61:9
   |
61 |         contents
   |         ^^^^^^^^
   = note: but, the lifetime must be valid for the static lifetime...
note: ...so that the expression is assignable
  --> src/lib.rs:60:5
   |
60 | /     Box::new(
61 | |         contents
62 | |             .lines()
63 | |             .filter(|line| line_pp(line).contains(&query)),
64 | |     )
   | |_____^
   = note: expected  `std::boxed::Box<(dyn std::iter::Iterator<Item = &'a str> + 'static)>`
              found  `std::boxed::Box<dyn std::iter::Iterator<Item = &str>>`

error: aborting due to previous error

For more information about this error, try `rustc --explain E0495`.
error: could not compile `minigrep`.

To learn more, run the command again with --verbose.

This compiles: (Playground)

fn search_backend<'a, F: 'a>(
    query: &'a str,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str>+'a>
where
    F: Fn(&&str) -> String,
{
    Box::new(
        contents
            .lines()
            .filter(move |line| line_pp(line).contains(&query)),
    )
}

The changes I made to get this to work, mostly following the compiler’s advice at each stage:

  • I added + ‘a to the return type so that the closure could process ’a references
  • The compiler then said that query needed an explicit lifetime, so I changed its type to &’a str
  • It then said that F might not live long enough, so I declared F:’a in the type parameters
  • Finally, it complained that the closure was capturing a reference to a local variable, so I redefined it as a move closure.

At each step, the compiler suggested the correct fix, but it took several iterations before the final code was something it was happy with.


Edit: It looks like the error messages you’re getting don’t include the suggestions I’m used to seeing. Here’s the error message I get from the stable playground on your original code, for example:

   Compiling playground v0.0.1 (/playground)
error: cannot infer an appropriate lifetime
  --> src/lib.rs:11:14
   |
3  |       contents: &'a str,
   |                 ------- data with this lifetime...
...
9  | /     Box::new(
10 | |         contents
11 | |             .lines()
   | |              ^^^^^
12 | |             .filter(|line| line_pp(line).contains(&query)),
13 | |     )
   | |_____- ...is captured and required to be `'static` here
   |
help: to permit non-static references in a `dyn Trait` value, you can add an explicit bound for the lifetime `'a` as defined on the function body at 1:19
   |
5  | ) -> Box<dyn Iterator<Item = &'a str> + 'a>
   |                                       ^^^^
1 Like

Wow, thanks! That was so much easier to solve through with the right compiler messages. I understand why the closure needs to be move now, and I think I understand why that also means query and the type of F need the same lifetimes as everything else—I wonder if, now that everything has the same lifetime, we could omit them altogether?

Re: error messages, it looks like I'm on rust 1.44.1 and the Playground is on 1.45.0, which could explain a lot. Running rustup update made a huge difference!

1 Like

Not quite, because Box<dyn ...> defaults to ’static when there’s no explicit lifetime. You might be able to do something with ’_, though.

Interesting. I did need to finangle some more, since I was passing &query.to_lowercase() in one of the search implementations, which was a function-local temporary and so didn't live long enough to be returned as part of the Iterator object.

I ended up with

pub fn search<'a>(query: &'a str, contents: &'a str) -> Box<dyn Iterator<Item = &'a str> + 'a> {
    search_backend(query.to_string(), contents, |x| x.to_string())
}

pub fn search_case_insensitive<'a>(
    query: &'a str,
    contents: &'a str,
) -> Box<dyn Iterator<Item = &'a str> + 'a> {
    search_backend(query.to_lowercase(), contents, |line| line.to_lowercase())
}

fn search_backend<'a, F: 'a>(
    query: String,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str> + 'a>
where
    F: Fn(&&str) -> String,
{
    Box::new(
        contents
            .lines()
            .filter(move |line| line_pp(line).contains(&query)),
    )
}

Using an owned String seems like it causes some extra allocations (query.to_string() in search) and doesn't seem all that idiomatic (&str seems preferred), but I couldn't figure out a way to make query.to_lowercase() not be a function-local temporary—it simply has to be.

1 Like

The alternative is to call to_lowercase inside the closure, but then you’re regenerating the lowercase representation for every line in order to save the heap allocation— probably not a good tradeoff.

Agreed. Thanks for all your help... I wonder if you have any thoughts on converting run() to return Result<Box<dyn Iterator<Item = String>>, ...> (Item could also be &str)? I could not find a way to do it, even after taking &Config as a parameter and trying move on the closure, and even with 'a lifetimes on those pieces...

I guess the results have to materialize somewhere, and run is one choice for it, but I wondered if it was possible to defer that realization to the libraries consumer

You’ll need to either:

  • clone() the query so that the expression search_fn(&conf.query, &contents) doesn’t hold a reference to conf, which then allows it to be moved into the closure, or
  • Accept an &’a Config and make your return type Result<Box<dyn Iterator<Item = String> + ‘a>, ...>. That will force the caller to keep the Config alive until they’re done with the iterator.

:thinking:

Did it? Some of the fixes make the code locally correct, but over-constrain it globally. In particular, it would be nice to support this usage:

let haystack = "banana\napple\norange";
let matches: Vec<_> = {
    let needle = String::from("an");
    search_backend(&needle, haystack, |x| (*x).to_owned()).collect()
};
println!("matches: {:?}", matches);

In this case the needle has a shorter life than the haystack, but it ought not to really matter, because the &strs returned by the Iterator only reference haystack. Except the compiler will (correctly) reject it:

error[E0597]: `needle` does not live long enough
  --> src/main.rs:20:24
   |
18 |     let matches: Vec<_> = {
   |         ------- borrow later stored here
19 |         let needle = String::from("an");
20 |         search_backend(&needle, haystack, |x| (*x).to_owned()).collect()
   |                        ^^^^^^^ borrowed value does not live long enough
21 |     };
   |     - `needle` dropped here while still borrowed

Following the compiler suggestions without taking time to fully understand them led us down the garden path a bit. We want the Iterator to produce items that are &strs that only reference contents, so let's give everything except contents and Item = &'a str a different lifetime:

fn search_backend<'a, 'b, F: 'b>(
    query: &'b str,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str> + 'b>
where
    F: Fn(&&str) -> String,

This gives an error message that is a bit confusing, but if you think on it for a bit you might realize that 'b can't be allowed to outlive 'a, because the Iterator can't live longer than the Items it's handing out, so adding 'a: 'b gives us something that compiles:

fn search_backend<'a: 'b, 'b, F: 'b>(
    query: &'b str,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str> + 'b>
where
    F: Fn(&&str) -> String,

I can think of two more changes that make this function strictly more flexible:

  • Accept FnMut instead of Fn. Every closure that satisfies Fn also satisfies FnMut and it permits stateful closures without interior mutability.
  • FnMut(&&'a str) is slightly more general (easier to satisfy) than FnMut(&&str). The second one has to accept references of any lifetime whereas the first only needs to accept references of lifetime 'a (which is the lifetime of the only references that are actually passed to it).

Compiler suggestions are often useful hints, but bear in mind that the compiler doesn't have context. This is a great example of where it makes a minor suggestion that fixes the immediate problem, but lacks the understanding to come up with the (more complicated) fix the situation actually calls for. The responsibility for that falls on the programmer.

@benknoble: Here's how I'd apply the same principle to the functions you most recently posted:

pub fn search<'a>(query: &str, contents: &'a str) -> Box<dyn Iterator<Item = &'a str> + 'a> {
    search_backend(query.to_string(), contents, |x| x.to_string())
}

pub fn search_case_insensitive<'a>(
    query: &str,
    contents: &'a str,
) -> Box<dyn Iterator<Item = &'a str> + 'a> {
    search_backend(query.to_lowercase(), contents, |line| line.to_lowercase())
}

fn search_backend<'a: 'b, 'b, F: 'b>(
    query: String,
    contents: &'a str,
    line_pp: F,
) -> Box<dyn Iterator<Item = &'a str> + 'b>
where
    F: Fn(&&'a str) -> String,
{
    Box::new(
        contents
            .lines()
            .filter(move |line| line_pp(line).contains(&query)),
    )
}
3 Likes

@trentj fascinating... In the first example, you've given query and the returned iterator the same lifetimes, is that right? And contents and the items of the iterator have the same lifetime, which must be at least the lifetime of query and the iterator... and then same for the Fn.

In the second example, just to double-check my understanding, the move closure in search_backend takes ownership of both line_pp and query, right? Otherwise, it doesn't seem query would live long enough anyway... It doesn't look like there's a way to handle query as &str instead, except that it would also have to live as long as the returned iterator?

Yes, that's right. To be a little more precise, the iterator returned from search_backend, because of the + 'b, can't live any longer than the argument that was borrowed to query. It doesn't have to live for exactly as long as the because the compiler can shorten 'b to be whatever is just long enough to keep the returned iterator alive. Lifetime annotations don't actually tell the compiler how long things should or do live; they only describe how different borrows are related.

Right, so, it's not very intuitive why query and line_pp both have types with a 'b in them, since there's not a direct relationship between the two arguments. But the important thing is they both have the same relationship to the return type: the Iterator can't be allowed to outlive query, and it can't be allowed to outlive line_pp, either, so 'b is not actually the exact lifetime of either argument: it's some lifetime, in the calling function, during which the three arguments and return value are all valid. 'a is some lifetime during which contents is valid, and the items yielded by the returned iterator are also valid, even if the iterator itself no longer is.

Yep, move closures always take ownership of whatever they close over.

Not without making other changes. One option might be to make search_backend generic over the type of query:

fn search_backend<'a: 'b, 'b, F, Q>(
    query: Q,
    contents: &'a str,
    mut line_pp: F,
) -> Box<dyn Iterator<Item = &'a str> + 'b>
where
    F: 'b + FnMut(&'a str) -> String,
    Q: 'b + AsRef<str>,
{
    Box::new(
        contents
            .lines()
            .filter(move |line| line_pp(line).contains(query.as_ref())),
    )
}

// inside search:
    search_backend(query, contents, |x| x.to_owned())

// inside search_case_insensitive:
    search_backend(query.to_lowercase(), contents, str::to_lowercase)

But this might not be better. One other thing that comes to mind is to redesign search_backend so the "query" argument is itself a closure that returns true or false:

fn search_backend<'a: 'b, 'b, Q>(
    mut query: Q,
    contents: &'a str,
) -> Box<dyn Iterator<Item = &'a str> + 'b>
where
    Q: 'b + FnMut(&'a str) -> bool,
{
    Box::new(contents.lines().filter(move |line| query(line)))
}

// inside search:
    search_backend(move |l| l.contains(query), contents)

// inside search_case_insensitive:
    let query = query.to_lowercase();
    search_backend(move |l| l.to_lowercase().contains(&query), contents)

This cuts down on unnecessary copying because you don't have to call to_owned in search.

Fascinating! Thanks for all the explanations.