Lifetime issue with str in closure


#1

Hi! I have a function, with the following signature:

    pub fn sort_unstable_by<T, F>(vec: & mut [T], to_slice: F)
    where
        F: Fn(&T) -> &[u8],
    {
        sort_req(vec, &to_slice, 0);
    }

Within the sort function, I need to be able to call the to_slice function multiple times, but I only use the returned value within the sort function.

Now, this works for e.g. tuples of strings:

let mut tuples = vec![(String::from("b"), 2), (String::from("a"), 1)];
sort_unstable_by(&mut tuples, |t| t.0.as_bytes());

But when trying to sort a similar structure with &str, it does not seem to work out.

let mut tuples = vec![("b", 2), ("a", 1)];
super::sort_unstable_by(&mut tuples, |t| t.0.as_bytes());

…Gives me this error:

error[E0597]: `*t.0` does not live long enough
   --> src/lib.rs:264:50
    |
264 |         sort_unstable_by(&mut tuples, |t| t.0.as_bytes());
    |                                                  ^^^ does not live long enough
...
267 |     }
    |     - borrowed value only lives until here
    |
note: borrowed value must be valid for the anonymous lifetime #2 defined on the body at 264:46...
   --> src/lib.rs:264:46
    |
264 |         sort_unstable_by(&mut tuples, |t| t.0.as_bytes());
    |                                              ^^^^^^^^^^^^^^^^^^

error: aborting due to previous error

I don’t understand what is going on. I have a decent understanding of lifetimes, but this one got me stuck. What I really don’t get is why it works with Strings but not &str.

Any help would be much appreciated!


#2

Could you give a full example? This is missing sort_req, even its type signature would be helpful. I have some ideas, but I want to try them out before I say something incorrect.


#3

Of course!

The type signature of sort_req is:

fn sort_req<T, F>(vec: &mut [T], to_slice: &F, depth: usize)
where
    F: Fn(&T) -> &[u8],
{
    ...
} 

The full code is a bit long to paste here, but it is available on Github. Apologies in advance for a rather long function :slight_smile:


#4

I’m stumped at the moment, but I think sort_req shouldn’t matter (try replacing the definition of sort_unstable_by with unimplemented!(), it should still error)


#5

This must be some sort of inference bug, of which several exist with closures and reference args interacting together. If you specify the type in the closure as |t: &(&str, _)| then it compiles.


#6

This has been bugging me for the last couple of hours as I’ve been away from my computer, and now that I’ve finally had a chance to try compiling some things… I’m surprised!

Observe: (these experiments place various levels of type annotation inside the closure)

pub fn sort_unstable_by<T, F>(vec: &mut [T], to_slice: F)
where F: Fn(&T) -> &[u8],
{ unimplemented!() }

fn main() {
    let mut tuples = vec!["b", "a"];
    
    // error[E0597]: `**x` does not live long enough
    // sort_unstable_by(&mut tuples, |x| x.as_bytes());
    
    // error[E0619]: the type of this value must be known in this context
    // sort_unstable_by(&mut tuples, |x: &&_| x.as_bytes());
    
    // ok
    sort_unstable_by(&mut tuples, |x: &&str| x.as_bytes());
}

The fact that the third example works appears to suggest that it is related to this known issue, however, I’m not sure if I have ever seen this issue produce any error besides “expected bound lifetime parameter, found concrete lifetime.” The second example is interesting, because usually type inference helps paper over this issue; but in this case (comparing the first failure to the second) we see that type inference is working against us.

What is that bound vs concrete lifetime error? Basically it’s what happens when the compiler assumes that a closure implements Fn(&'a) (for some 'a) when it is actually required to implement for<'a> Fn(&'a). Playing on that angle, there’s two more experiments we can try: Consider the fact that when T=&str, T contains a lifetime. What if we make that lifetime explicitly bound vs concrete in the Fn signature?

(these experiments try the original unannotated closure, but change the signature of sort_unstable_by)

// Should be equivalent to sort_unstable_by;
//  't is the lifetime that was implicitly contained in T when T = &str
pub fn sort_unstable_by_explicitly_in_type<'t, T: ?Sized, F>(vec: & mut [&'t T], to_slice: F)
where F: for<'a> Fn(&'a &'t T) -> &'a [u8],
{ unimplemented!() }

// Version that frees the lifetime from the type
pub fn sort_unstable_by_explicitly_free<T: ?Sized, F>(vec: & mut [&T], to_slice: F)
where F: for<'a,'t> Fn(&'a &'t T) -> &'a [u8],
{ unimplemented!() }

fn main() {
    // error[E0597]: `**x` does not live long enough
    // sort_unstable_by_explicitly_in_type(&mut tuples, |x| x.as_bytes());
    
    // ok
    sort_unstable_by_explicitly_free(&mut tuples, |x| x.as_bytes());
}

This serves as yet more evidence that it is related to the issue I linked above; though I still can’t quite paint a full picture of what exactly is going on in my head.

playpen


(Note: ?Sized is (or, should be) incidental to these examples, and is only necessary because T = str. Had I been less lazy I could have changed the example to use &mut [&i32])


#7

Stepping through lifetime inferencing:

pub fn sort_unstable_by<T, F>(vec: &mut [T], to_slice: F)
where
        F: Fn(&T) -> &[u8]

is inferred as:

pub fn sort_unstable_by<'a, T, F>(vec: &'a mut [T], to_slice: F)
where
        F: for<'b> Fn(&'b T) -> &'b [u8]

and with T resolved is:

pub fn sort_unstable_by<'a, 'b, F>(vec: &'a mut [(&'b str, i32)], to_slice: F)
where
        F: for<'c> Fn(&'c (&'b str, i32)) -> &'c [u8]

The problem here is the closure is expecting to be able to take a reference of any lifetime ('c), but the closure is returning an unrelated lifetime defined earlier ('b).

A working signature would be:

pub fn sort_unstable_by<'a, T, F>(vec: &'a mut [T], to_slice: F)
where
        F: Fn(&'a T) -> &'a [u8]

#8

Thank you all for your answers, they helped me understand the issue better.

@ExpHP
I tried changing the method signature, but it seems like the downstream method calls become quite hairy, i.e. sort_req in the example. Simply making them both have the F: for<'a,'t> Fn(&'a &'t T) -> &'a [u8], produced an error like this:

error[E0277]: the trait bound `for<'r> F: std::ops::Fn<(&'r T,)>` is not satisfied
   --> src/lib.rs:171:5
    |
171 |     sort_req(vec, &to_slice, 0);
    |     ^^^^^^^^ the trait `for<'r> std::ops::Fn<(&'r T,)>` is not implemented for `F`
    |
    = help: consider adding a `where for<'r> F: std::ops::Fn<(&'r T,)>` bound
    = note: required by `sort_req`

@Jarcho

I tried changing the signature to your suggestion. Unfortunately, it seems like it messes up the lifetime of the vec argument. I’m not completely sure why. Here’s a sample error message:

error[E0502]: cannot borrow `*vec` as mutable because it is also borrowed as immutable
   --> src/lib.rs:250:22
    |
186 |         for elem in vec.iter() {
    |                     --- immutable borrow occurs here
...
250 |                 &mut vec[offsets[i as usize] as usize..offsets[i as usize + 1] as usize],
    |                      ^^^ mutable borrow occurs here
...
257 | }
    | - immutable borrow ends here

One interesting part here is that line 186 is in a block, which is ended before line 250 (which is in a separate block).

Since this seems to be a known issue, I’m leaning towards making the type arguments explicit in the examples for now, as suggested by @vitalyd.

Again, thank you all very much!


#9

Hm, one more thing to rule out: Because we have &mut [T], lifetimes in T can be particularly nasty due to mutable borrows being invariant in their value type.

Let’s see what happens if I change my experiments to all receive &tuples:

let mut tuples = vec!["b", "a"];
    
// error[E0597]: `**x` does not live long enough
sort_unstable_by(&tuples, |x| x.as_bytes());
    
// error[E0619]: the type of this value must be known in this context
sort_unstable_by(&tuples, |x: &&_| x.as_bytes());
    
// ok
sort_unstable_by(&tuples, |x: &&str| x.as_bytes());
    
// error[E0597]: `**x` does not live long enough
sort_unstable_by_explicitly_in_type(&tuples, |x| x.as_bytes());
    
// ok
sort_unstable_by_explicitly_free(&tuples, |x| x.as_bytes());

these are the exact same results as before, so we can at least rule out invariance as one of the factors at play.


#10

I’m not seeing this particular issue; the following compiles fine for me:

pub fn sort_unstable_by_explicitly_free<T: ?Sized, F>(vec: &mut [&T], to_slice: F)
where F: for<'a,'t> Fn(&'a &'t T) -> &'a [u8],
{ sort_req(vec, to_slice) }

pub fn sort_req<T: ?Sized, F>(vec: &mut [&T], to_slice: F)
where F: for<'a,'t> Fn(&'a &'t T) -> &'a [u8],
{ unimplemented!() }

Note that I changed the types in my example in an attempt to minimize it; in your case the signature would be more like:

pub fn sort_unstable_by<T: ?Sized, F>(vec: &mut [(&T, i32)], to_slice: F)
where F: for<'a,'t> Fn(&'a (&'t T, i32)) -> &'a [u8],
{ sort_req(vec, to_slice) }

pub fn sort_req<T: ?Sized, F>(vec: &mut [(&T, i32)], to_slice: F)
where F: for<'a,'t> Fn(&'a (&'t T, i32)) -> &'a [u8],
{ unimplemented!() }

which should make apparent the much bigger issue of this approach (and why I wouldn’t recommend doing it), which is that it requires you to cut through abstraction boundaries and pretty much entirely defeats the point of making the function generic in T.


#11

Hm, I think that it might be due to me declaring the recursive function as taking &F, instead of F directly. This seems to be needed, since the function calls itself several times, and thus can’t take the Fn by value.

I do agree with you that this seems to be a deep rabbit hole though. Thank you very much for your time and patience!


#12

I cheated a little bit with my previous answer. The following isn’t valid code but more accurately describes inferenceing (for<...> where ... is not valid code, and AFAIK, cannot be expressed):

pub fn sort_unstable_by<'a, T, F>(vec: &'a mut [T], to_slice: F)
where
        T: 'a,
        F: for<'b> where T: 'b Fn(&'b T) -> &'b [u8]

and with T expanded should be, and would compile just fine if it were:

pub fn sort_unstable_by<'outer, 'inner, F>(vec: &'outer mut [(&'inner str, i32)], to_slice: F)
where
        'inner: 'outer,
        F: for<'outer2> where 'inner: 'outer2 Fn(&'outer2 (&'inner str, i32)) -> &'outer2 [u8]

but the compiler doesn’t seem to infer that the outer reference has to outlive the inner reference for the function parameter.


TL;DR: The lifetimes should be inferred correctly, but they aren’t. And, AFAIK, they can’t be written.