A problem about lifetime, pls help

[leafinsky]

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.

[alice]

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.

[leafinsky]

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

[alice]

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.

[leafinsky]

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 ?

[quinedot]

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.

[leafinsky]

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.

[alice]

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.

[leafinsky]

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

[Yandros]

@leafinsky

    // let f = Finder::new(Box::new(str::find::<&str>), f_str);  //error?
    let f = Finder::new(Box::new(foo), f_str);    //compile ok

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.

[leafinsky]

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)?

[Yandros]

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 reason¹.

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
}

• Playground

---

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

[leafinsky]

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?

[quinedot]

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.

[Yandros]

I've made more tests, and as I suspected,

@Yandros

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

• (Or, at least, not in my examples)

The key things to observe here are:

• a function item / ZST which is only generic over lifetimes, does not seem to have its type "visibly" infected with the (potentially non-higher-order) lifetime of its parameter, thus avoiding the case of:

  @quinedot

  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

  I mean, it necessarily has to be infected with that lifetime for soundness, but it is as if this very case was special-cased by the compiler to escape the above "outlives rule".

• Any other case:

  • be it a function item which was generic over types and which gets turbofish-fed an actual lifetime-infected type,
  • be it a non-higher-order function pointer,
  • be it a trait object,
  • be it an existential type,

  they all get infected with the lifetime at the type level, thus ceasing to be 'static as per @quinedot's quoted rule above.

---

This leads to potentially one of the most surprising / confusing Rust snippets I've ever seen :

fn _with_non_static<'non_static> ()
{   
    fn funnel<'lt : 'lt> (f: impl 'static + FnOnce(&'lt ()))
      -> impl 'static + FnOnce(&'lt ()) // <- Actually not `'static` in practice
                                        //    because `'lt`-infected existential!
    {
        f
    }

    let f = funnel::<'non_static>(|_| ()); // OK
    let f = funnel::<'non_static>(f); // Fails!?
}

• Playground

[quinedot]

@Yandros

it is as if this very case was special-cased by the compiler to escape the above "outlives rule".

Is this the following, do you think?

For higher-ranked lifetimes, we simply ignore the relation, since the lifetime is not yet known. This means for example that for<'a> fn(&'a i32): 'x holds, even though we do not yet know what region 'a is (and in fact it may be instantiated many times with different values on each call to the fn).

(Higher-order function pointers do seem to act the same as function items.)

@Yandros

This leads to potentially one of the most surprising / confusing Rust snippets I've ever seen :

I am surprised and don't understand why the infected return is allowed, an apparent contradiction. (I admit I haven't taken the time to fully dive in on the RFC either, though.)

---

Edit: I skimmed my notes on the rabbit holes I decided not to post about earlier, and now think they're relevant to this case. impl Trait has "hidden" (captured) lifetimes that cannot be expressed (in contrast with dyn Trait). I haven't had time to more than skim though. Message me if you want my incomplete breadcrumbs; hopefully I'll find time to explore more later.

[Yandros]

Since we are kind of delving into compiler internals, and clearly getting ouf of depth w.r.t. the OP here, I'm continuing the discussion on Zulip (I haven't been able to ping you there, @quinedot)