What should be the lifetime restrictions of a Trait parameter that is moved into a filter closure?

Question

I have two methods on a struct.

The first method is a search which expects a criteria, and will return an iterator that applies that criteria:

pub fn search<'s>(
    &'s self,
    criteria: impl Criteria + 's,
) -> impl Iterator<Item = &'s Record> + 's {
    self.records.iter().filter(move |&tr| criteria.apply(tr))
}

I will admit to being a little confused as to why criteria has to have an explicit lifetime, because I move ownership of criteria into the filter closure. I would imagine it becomes owned by the Iterator, and thus have the same lifetime.

But, it works. Then I add on this function:

pub fn search_sorted<C, CMP>(&self, criteria: C, compare: CMP) -> Vec<(&UniqueId, &T)>
where
    C: Criteria,
    CMP: FnMut(&(&UniqueId, &T), &(&UniqueId, &T)) -> Ordering,
{
    let search_iter = self.search(criteria);
    let mut records: Vec<(&UniqueId, &T)> = search_iter.collect();
    records.sort_by(compare);
    records
}

Here the compiler insists that I need a lifetime on criteria. This confuses me, because criteria is an owned parameter, and then I'm passing ownership on to self.search. When I try to take the advice of the compiler to add a lifetime annotation, the compiler then just asks for more.

Here's a complete example that I built in Rust Playground:

use std::cmp::Ordering;

struct Record {}

trait Criteria {
    fn apply(&self, r: &Record) -> bool;
}

struct List {
    records: Vec<Record>
}

impl List {    
    fn new(lst: Vec<Record>) -> List {
        List{ records: lst }
    }
    
    pub fn search<'s>(
        &'s self,
        criteria: impl Criteria + 's,
    ) -> impl Iterator<Item = &'s Record> + 's {
        self.records.iter().filter(move |&tr| criteria.apply(tr))
    }
    
    pub fn search_sorted<C, CMP>(&self, criteria: C, compare: CMP) -> Vec<&Record>
    where
        C: Criteria,
        CMP: FnMut(&&Record, &&Record) -> Ordering,
    {
        let search_iter = self.search(criteria);
        let mut records: Vec<&Record> = search_iter.collect();
        records.sort_by(compare);
        records
    }

}

And then the error that I get (much forshortened) is this:

error[E0311]: the parameter type `C` may not live long enough
  --> src/lib.rs:30:32
   |
25 |     pub fn search_sorted<C, CMP>(&self, criteria: C, compare: CMP) -> Vec<&Record>
   |                          - help: consider adding an explicit lifetime bound...: `C: 'a`
...
30 |         let search_iter = self.search(criteria);
   |                                ^^^^^^
   |
note: the parameter type `C` must be valid for the anonymous lifetime #1 defined on the method body at 25:5...
  --> src/lib.rs:25:5

Can you give any advice for resolving this? For me, the obvious solution would just be "callers are required to do their own sorting", and I won't rule that out, but I do like having this utility function.

Answer 1

I will admit to being a little confused as to why criteria has to have an explicit lifetime, because I move ownership of criteria into the filter closure.

From the function's perspective, Criteria is a trait, that could have any number of implementations and any of those implementations might contain references. This annotation makes sure that, if the implementation of Criteria does contain a reference, its lifetime must be longer than the call to search. Otherwise it can't guarantee that an arbitrary criteria is valid throughout the body of the function.

The same is also true for search_sorted. You just need to add the lifetime parameter, as the error message suggested:

pub fn search_sorted<'s, C, CMP>(&'s self, criteria: C, compare: CMP) -> Vec<&Record>
where
    C: Criteria + 's,
    CMP: FnMut(&&Record, &&Record) -> Ordering,
{
    let search_iter = self.search(criteria);
    let mut records: Vec<&Record> = search_iter.collect();
    records.sort_by(compare);
    records
}

Note that I've also constrained &self with the same lifetime. This is the connection that allows the compiler to guarantee that the criteria does not contain references with a lifetime shorter than the function body. This in turn allows the compiler to guarantee that it can guarantee the lifetime requirements of search when it is called by search_sorted.