A problem about lifetime, pls help

I encountered a very confusing problem, code as followings

use std::str;
struct Finder<'a> {
    find_fn: Box<dyn Fn(&'a str, &'a str)-> Option<usize>>,
    find_str: &'a str,
}
impl <'a> Finder <'a> {
    fn new(find_fn: Box<dyn Fn(&'a str, &'a str)->Option<usize>>, find_str: &'a str)-> Self{
        Self{find_fn, find_str}
    }
}

fn foo<'b>(_: &'b str, _: &'b str)-> Option<usize> {
    None
}

fn find_str<'a>(f_str: &'a str)-> usize {
    let f = Finder::new(Box::new(str::find::<&str>), f_str);  //error?
    // let f = Finder::new(Box::new(foo), f_str);    //compile ok
    todo!()
}

Here is playground

It will compile error:

error[E0759]: `f_str` has lifetime `'a` but it needs to satisfy a `'static` lifetime requirement

but the prototype of str::find is

pub fn find<'a, P>(&'a self, pat: P) -> Option<usize>
where
    P: Pattern<'a>

I can not know why is the static lifetime?

Any help will be appreciated, thanks.

First, remove some lifetimes:

struct Finder<'a> {
    find_fn: Box<dyn Fn(&str, &str) -> Option<usize>>,
    find_str: &'a str,
}
impl<'a> Finder<'a> {
    fn new(find_fn: Box<dyn Fn(&str, &str) -> Option<usize>>, find_str: &'a str) -> Self {
        Self { find_fn, find_str }
    }
}

Now call it with a closure:

fn find_str(f_str: &str) -> usize {
    let f = Finder::new(Box::new(|a, b| a.find(b)), f_str);
    let f = Finder::new(Box::new(|a, b| foo(a, b)), f_str);
    todo!()
}

I didn't remove every lifetime here, but the easiest way to get something like this to work is to remove every single lifetime using e.g. String.

1 Like

Cool, It does work!
But why does the closure work but the fn does not ?

These are not the same signature:

fn foo<'a>(&'a str, &'a str) -> usize;
fn foo<'a, 'b>(&'a str, &'b str) -> usize;

The closure lets you translate to the right signature.

but which signature is fn foo<'a, 'b>(&'a str, &'b str)-> usize;
the prototype of str::find is

pub fn find<'a, P>(&'a self, pat: P) -> Option<usize>
where
    P: Pattern<'a>

I thought the signature was also fn foo<&'a str, &'a str>-> usize ?

dyn Trait types like dyn Fn also have a lifetime, which can be omitted and usually defaults to 'static. That's where the 'static was coming from. If you allow the dyn Fn to be more limited:

 struct Finder<'a> {
-    find_fn: Box<dyn Fn(&'a str, &'a str)-> Option<usize>>,
+    find_fn: Box<dyn Fn(&'a str, &'a str)-> Option<usize> + 'a>,
     find_str: &'a str,
 }
 impl <'a> Finder <'a> {
-    fn new(find_fn: Box<dyn Fn(&'a str, &'a str)->Option<usize>>, find_str: &'a str)-> Self{
+    fn new(find_fn: Box<dyn Fn(&'a str, &'a str)->Option<usize> + 'a>, find_str: &'a str)-> Self{
         Self{find_fn, find_str}
     }
 }

Then the compiler can find its way. Alternatively you can put the trait objects behind shorter lived references:

 struct Finder<'a> {
-    find_fn: Box<dyn Fn(&'a str, &'a str)-> Option<usize> + 'a>,
+    find_fn: &'a dyn Fn(&'a str, &'a str)-> Option<usize>,
     find_str: &'a str,
 }
 impl <'a> Finder <'a> {
-    fn new(find_fn: Box<dyn Fn(&'a str, &'a str)->Option<usize> + 'a>, find_str: &'a str)-> Self{
+    fn new(find_fn: &'a dyn Fn(&'a str, &'a str)->Option<usize>, find_str: &'a str)-> Self{
         Self{find_fn, find_str}
     }
 }
 // ...
-    let f = Finder::new(Box::new(str::find::<&str>), f_str);
+    let f = Finder::new(&str::find::<&str>, f_str); 

And that also works as the dyn Fn lifetime is inferred to be 'a in this case as well. See lifetime misconceptions #6 or try adding back the 'static bound to see the error return.


Why does Alice's solution work then, if it doesn't change the bounds on dyn Fn? The closures being passed in don't capture anything, so they are in fact 'static. You can see this by trying to pass in a closure that captures a local reference (i.e. cannot be 'static).

The indirection of the closures hid the lifetimes that are part of std::find::<'_, _> that the compiler was struggling with. So in your original example, if you just replace

-    let f = Finder::new(str::find::<&str>), f_str);
+    let f = Finder::new(Box::new(|a, b| a.find(b)), f_str);

It is also good enough to compile.

(But Alice's solution, or perhaps a variant using &dyn Fn, is the much cleaner one.)


I think the compiler is entangling the lifetimes of std::find::<'_, _> with that of f_str, as if it could store a copy of f_str indefinitely (for 'static), but I don't have a citation nor a good explanation of why.

1 Like

Thank you very much! Very clear and detailed!
I have one last confusing problem. If I replace str::find with a following custom fn foo, why does it compile successfully?

use std::str;

struct Finder<'a> {
    find_fn: Box<dyn Fn(&'a str, &'a str)-> Option<usize>>,
    find_str: &'a str,
}
impl <'a> Finder <'a> {
    fn new(find_fn: Box<dyn Fn(&'a str, &'a str)->Option<usize>>, find_str: &'a str)-> Self{
        Self{find_fn, find_str}
    }
}

fn foo<'b>(_: &'b str, _: &'b str)-> Option<usize> {
    None
}

fn find_str<'a>(f_str: &'a str)-> usize {
    // let f = Finder::new(Box::new(str::find::<&str>), f_str);  //error?
    let f = Finder::new(Box::new(foo), f_str);    //compile ok
    todo!()
}

looking forward to your further explanation, thanks again.

Your find_fn requires it to take a single lifetime argument and reuse it for both arguments, and that is indeed the signature of foo. The signature of str::find allows the two arguments to have two different lifetimes.

1 Like

According to post of @quinedot, dyn Fn has 'static lifetime. Then Box::new(foo) also has 'static lifetime?

Minimal repro:

fn main<'a> ()
{
    //              allow it to be turbofishable (early-bound lifetime)
    //              vvvv
    fn is_static<'a : 'a> (_: impl 'static + Fn(&'a ()))
    {}

    //      infer that the param is `&'a ()`
    //           +----+
    //           |    |
    //          --  vvvv
    is_static::<'a>(drop);
}
  • we end up feeding a drop::<Inferred> function, with Inferred = &'a (), and such function item is thus infected, a the type-level, with the Inferred type, and thus, bounded by the lifetime of Inferred = &'a (), i.e., bounded by 'a, even though the function, in and of itself, does not dangle after 'a.

It's a type-level limitation, one which is easily circumvented by not performing that eta reduction, and using closures at call-sites instead, as @alice suggested.

Thanks @alice @quinedot @Yandros for your enthusiastic reply. But I am still confused why fn foo does work but str::find does not?
Maybe str::find is a method of struct and its prototype including (&'a self)?

It's a limitation / bug in the type system and how generics and inference gets resolved: foo, contrary to find, always takes a reference type, so it's automatically 'static. But when you take a fully (over types) generic function and try to substitute a type parameter with a reference type, the resulting function (item) becomes lifetime-infected / non-'static for some reason1.

Repro:

fn main ()
{
    fn check<'local> (
        _: impl 'static + Fn(&'local ()),
        _: &'local (),
    )
    {}
    
    fn generic_over_lifetime_only<'lt> (_: &'lt ())
    {}
    
    fn generic_over_ty<T> (_: T)
    {}
    
    let local = ();
    check(generic_over_lifetime_only, &local); // OK
    check(generic_over_ty, &local); // Fails
}

1 This is not the early-bound / non-higher-order vs. late-bound / higher-order distinction…

Thank you very much for patient explanation.
but when I add lifetime parameter like str::find, it is compiled again.

fn main ()
{
    fn check<'local> (
        _: impl 'static + Fn(&'local ()),
        _: &'local (),
    )
    {}
    
    fn generic_over_lifetime_only<'lt> (_: &'lt ())
    {}
    
    fn generic_over_ty<'lt, T> (_: &'lt T)
    {}
    
    let local = ();
    check(generic_over_lifetime_only, &local); // OK
    check(generic_over_ty, &local); // Fails
}

Maybe str::find is the method of str, and str has lifetime of 'a, so the lifetime of dyn str::find is not 'static?

I spent awhile poking at this and following rabbit holes in an effort to understand it. The rabbit holes were quite interesting but I'm not 100% they're related, so I'll skip most of them in this post.

Eventually I ended up playing with this arguably simpler analog:

    fn check<'local> (
        _: &'static fn(&'local ()),
        _: &'local (),
    )

It also doesn't work with generic_over_ty, and I eventually decided that this is due to two barriers.

One is that RFC 1214 made it so that

if all type/lifetime parameters appearing in the type T must outlive 'a , then T: 'a (though there can also be other ways for us to decide that T: 'a is valid, such as in-scope where clauses). So for example fn(&'x X): 'a if 'x: 'a and X: 'a (presuming that X is a type parameter).

This means you can't get a static function pointer to a fn(&()) (the lifetime-infection). Issue 80317 proposed to relax this for function pointers at least, but no RFC has materialized that I'm aware of. (IRLO thread.) The case for Fn-implementors that are not coercible to function pointers is even less clear.

The second barrier is that generic_over_ty<&()> is a fn(&()) while generic_over_lifetime_only is a for<'a> fn(&'a ()) -- i.e. the compiler doesn't "hoist" the former into a higher-ranked type. (This higher-ranked type avoids the infection.) I tried to get a grasp on whether or not it could or should be hoisted or not. It seemed this could well be unsound but I didn't come up with an example.

Then, while looking at something unrelated, I stumbled across this comment by Niko which says that

the first type fn(T) cannot ever be equal to the second type for<'a> fn(&'a U) because there is no value of T that can name 'a .

I wish I had a more thorough explanation than that, but I don't. The context is that this could someday be accepted as valid and non-overlapping:

impl<T> Trait for fn(&T) { }
impl<T> Trait for fn(T) { }

And the implication is that the generic-over-type-but-not-lifetime version cannot be hoisted.


In summary, the current situation seems to be intentional. It may someday work directly for function pointers (or may not). The case for other types is less clear.