Explicit lifetimes in closures & one type is more general than the other

help
1

The line

data.sort_by_key(|d| &d.this);

in the code shown in this playground, gives the error

6 |     data.sort_by_key(|d| &d.this);
  |                       -- ^^^^^^^ returning this value requires that `'1` must outlive `'2`
  |                       ||
  |                       |return type of closure is &'2 String
  |                       has type `&'1 S`

At first blush, I'd expect lifetime elision rules to take care of this by making the two lifetimes the same.

So I want to try writing the lifetimes explicitly, at which point I realize that I don't recall ever having had the need to add lifetime annotations to closure definitions before. Is it possible?

So I try to replace the closure with the function

fn key(item: &S) -> &String {
    &item.this
}

which gives the error

7   |     data.sort_by_key(key);
    |     ^^^^^^^^^^^^^^^^^^^^^ one type is more general than the other
    |
    = note: expected reference `&String`
               found reference `&String`

which appears to be drawing my attention to two things which are both rendered as &String, being somehow different.

Huh?

2

The problem is that (I believe) sort_by_key temporarily stores the result of the key function, which means it can't reference the item (since the item is about to be moved during sorting). You'll notice the signature of the method doesn't allow for borrows coming from the input reference.

A reference from the surrounding scope would (I believe) satisfy it, hence why the borrow checker tells you yours doesn't live long enough. '2 is, essentially by definition, anything but '1.

(note: it's currently 1am where I live, and I'm running on four braincells and vague recollections of running into the same thing a while ago, so I apologize in advance for anything that's unclear or inaccurate)

1 Like
3

I'm on mobile and this will also be a terse answer as a result.

sort_by_key does not support closures that borrow, and the workaround is sort_by.

There is at least one recent thread about this if you don't want to wait for a more complete reply.

4

Ah yes, that's the crux of the matter.

Oh, I can work around it, no problem. But I was trying to understand the peripheral issues:

  • Is it possible to annotate the lifetimes of parameter and return types of closures?
  • How to make sense of an error message which states that two types which it represents identically, are different.
5

There's also this 8 year old bug report for further reference slice::sort_by_key has more restrictions than slice::sort_by · Issue #34162 · rust-lang/rust · GitHub

6

Can you post a minimal example that reproduces the error?

So far in my experience when the compiler says

expected reference `SomeType`
found reference `SomeType`

and you cannot see any difference between the types it has been because they were from two different versions of the same crate. But I don't know how that would happen in the standard librery. On that note, is the String here the std String or some type that just has the same name?
Also it is very well possible that this is the same problem as in the closure case but the error isn't aware of differences in lifetimes.

7

Can you explain how this method signature makes sure that K does not borrow from &T?

pub fn sort_by_key<K, F>(&mut self, mut f: F)
    where
        F: FnMut(&T) -> K,
        K: Ord,
    {
8

See playground link at the top of the thread. Repeated here for convenience.

I don't see how different crates might enter this trivial example that, on the face of it, only uses std.

9

As another data point, I believe this playground demonstrates what

was explaining. Not too shabby for 1am brain! :slight_smile:

It's obviously not practical. Just sheds some light on the borrow checker's view of the situation.

2 Likes
10

There are two solutions in this thread from three days ago:

  • Constrain the closure type by passing it to another function. The lifetime annotations you want would be possible by:

    fn same_lt_in_and_out<T: ?Sized, U: ?Sized, F>(f: F) -> F
where
    F: for<'a> Fn(&'a T) -> &'a U,
{
    f
}

data.sort_by_key(same_lt_in_and_out(|d| &d.this));

    except that that's not compatible with sort_by_key, so actually this gives an error.

  • Use the unstable feature closure_lifetime_binder.

5 Likes
11

Because there's no way to use the lifetime on the reference, therefore no way to annotate K with it. for<'a> Fn(&'a T) -> &'a K is a different, incompatible signature.

12

Sorry, I missed that.

13

So does that mean that because you cannot relate Ks lifetimes to &Ts the borrow checker has to assume that they are different?

14

Exactly. If that weren't true, what would happen? sort_by_key would be allowed to get the key, then move, drop, modify - do whatever it wanted to the item, likely invalidating the reference in doing so. Because it can't see that the two types are at all related.

1 Like
15

Type generics like K have to resolve to a single type. So when you have a trait bound like

F: FnMut(&T) -> K,
// aka
F: for<'any> FnMut(&'any T) -> K

that means that K has to be the same type, no matter what the input lifetime is -- and types that differ by lifetime are still distinct types. So there is no way to be a closure that returns a type which contains the input lifetime and meet this signature.

The Iterator trait has the same sort of restriction:

    type Item; // Must resolve to a single type
    fn next(&mut self) -> Option<Self::Item>;

If you've ever heard stuff like "iterators can't borrow from their fields" or "you would need a lending iterator (that does support borrowing on next)," this is the restriction they were talking about.

Here's the other thread I was thinking about before.

3 Likes