Lifetimes with Vec::dedup_by_key

[jkugelman]

pub fn main() {
    let mut names = vec![
        String::from("John Brown"),
        String::from("John Smith"),
        String::from("Joe Brown"),
    ];
    names.dedup_by_key(|name: &mut String| &name[..4]);
}

Why doesn't this compile?

error: lifetime may not live long enough
 --> src/main.rs:7:44
  |
7 |     names.dedup_by_key(|name: &mut String| &name[..4]);
  |                               -          - ^^^^^^^^^^ returning this value requires that `'1` must outlive `'2`
  |                               |          |
  |                               |          return type of closure is &'2 str
  |                               let's call the lifetime of this reference `'1`

Playground

I thought both references would have the same lifetime. Doesn't the slice live exactly as long as the String? I don't understand why they're not both '1.

And how do I get it to work? I hope I don't have to clone the strings. (In my real program they're huge objects, but I'm hoping Strings are a suitable stand-in.)

[cole-miller]

The signature here is

impl<T> Vec<T> {
    pub fn dedup_by_key<F, K>(&mut self, key: F)
    where
        F: FnMut(&mut T) -> K,
        K: PartialEq<K>,
}

The bound F: FnMut(&mut T) -> K is short for F: for<'a> FnMut(&'a mut T) -> K, that is, the output type K is not allowed to depend on the lifetime 'a of the borrowed input. The closure you provide has the signature^† for<'a> &'a mut String -> &'a str, with the output type &'a str depending on 'a, so it is not allowed. It's an unfortunate limitation of the Fn traits, but you should be able to work around it in this case, without cloning, by using Vec::dedup_by instead.

^† strictly speaking I'm not sure this is true, because—as Yandros pointed out to me in a previous thread—closures are rarely higher-order: any implicit lifetimes in the signature are likely to be fixed or "early bound", not allowed to vary between different calls as the HRTB for<'a> ... would imply. But the upshot is the same, the compiler can't deduce what K should be because FnMut(&mut T) -> K doesn't allow it to incorporate the lifetime of the borrowed item.

[jkugelman]

Oh, I see. I wish the compiler would say something more like that. "Output lifetime '2 can't depend on '1", say. Or, "Closure doesn't match trait bound." The way it reads now I thought my closure was broken on its own. I didn't make the connection that it doesn't satisfy the FnMut(&mut T) -> K signature.

You say this is a limitation of the Fn traits. Can you expand on that? Is it a limitation of this signature, or is it impossible to express the necessary constraint, like, at all?

[quinedot]

You're actually getting hit by an unfortunate lack of lifetime elision on closures. That's why the error is on your closure, and not the method call.

You can work around it by doing:

// This signature will obey the elision rules
fn annotate<T: ?Sized, U: ?Sized, F: FnMut(&mut T) -> &U>(f: F) -> F { f }

let mut closure = annotate(|name: &mut String| &name[..4]);

...but then if you try to call dedup_by_key with this closure, you'll get a different error, which is about the borrowing signature that @cole-miller explained. (It's still not a great error, but at least lets you know there's some sort of signature mismatch.) However, as they also said, dedup_by can still work, and in fact dedup_by_key just calls dedup_by under the hood, like so:

names.dedup_by(|a, b| closure(a) == closure(b));

However if your use case supports it, it's going to be more clear to just implement this with a single closure, ala

names.dedup_by(|a, b| &a[..4] == &b[..4]);

Playground.