Lifetime issue with generic trait bound

Question

I'm writing a trait as an interface over map-type data structures (e.g. std::collections::BTreeMap and std::collections::HashMap). This is a follow-up to a question I asked yesterday, though it stands on its own.

I'm having a lifetime issue I can't seem to understand. I've searched for answers in all my textbooks, The Rust Reference, StackOverflow, and more, and I haven't been able to figure out what's going on. I've written almost a dozen variants on the following code based on the suggestions from the previous question, and I wind up with the same situation. I'm hoping someone can help me understand either why gc3() is impossible or what I'm doing wrong. I know it's entirely possible I've had my nose in the problem for so long I'm missing something simple that should be obvious. (playground)

use std::collections::hash_map::{HashMap, Iter};

fn main() {
    gc1(&HashMap::new());
    gc2(&HashMap::new());
    gc3(HashMap::new());
}

// Works
fn gc1<'a>(map: &'a dyn GroupedCollection<'a, usize, usize, Iter<'a, usize, Vec<usize>>>) {
    let _ = map.iter().collect::<Vec<_>>();
}

// Works
fn gc2<'a, M>(map: &'a M)
where
    M: 'a + GroupedCollection<'a, usize, usize, Iter<'a, usize, Vec<usize>>>,
{
    let _ = map.iter().collect::<Vec<_>>();
}

// Compiler error: `map` does not live long enough
fn gc3<'a, M>(map: M)
where
    M: 'a + GroupedCollection<'a, usize, usize, Iter<'a, usize, Vec<usize>>>,
{
    let _ = map.iter().collect::<Vec<_>>();
}

pub trait GroupedCollection<'a, K, V, I: 'a> {
    fn iter(&'a self) -> I;
}

impl<'a, K, V> GroupedCollection<'a, K, V, Iter<'a, K, Vec<V>>> for HashMap<K, Vec<V>>
{
    fn iter(&'a self) -> Iter<'a, K, Vec<V>> {
        HashMap::iter(&self)
    }
}

error[E0597]: `map` does not live long enough
  --> src/main.rs:27:13
   |
23 | fn gc3<'a, M>(map: M)
   |        -- lifetime `'a` defined here
...
27 |     let _ = map.iter().collect::<Vec<_>>();
   |             ^^^^^^^^^^
   |             |
   |             borrowed value does not live long enough
   |             argument requires that `map` is borrowed for `'a`
28 | }
   | - `map` dropped here while still borrowed

Is the compiler complaining because the references produced by map.iter() are dropped at the end of collect() because collect(self) consumes the iterator? (I've tried addressing this by assigning 'a: 'b to GroupedCollection and 'b to iterator references, but it doesn't seem to fix the issue: playground)

Chayim Friedman · Accepted Answer · 2022-05-05T21:52:31.547

TL;DR: Don't use a lifetime parameter, use HRTB: where M: for<'a> GroupedCollection<'a, usize, usize, Iter<'a, usize, Vec<usize>>>.

'a is a caller-chosen lifetime. Suppose the caller choose 'static (in general, it is good to validate lifetimes against 'static). map.iter() is desugared to <M as GroupedCollection<'static, ...>>::iter(&map). <M as GroupedCollection<'static, ...>>::iter() requires &'a self, i.e. &'static self. But map is a local variable, and thus &map is definitely not 'static. Boom.

It works with references because the caller not only choose 'a, it also needs to provide a reference that matches it. If it'll choose 'static, it will have to provide &'static M and so everything is fine.

The solution? You want a callee-chosen lifetime. That is, M implements GroupedCollection for some lifetime 'a I choose, not my caller. There is no way to express that in Rust, but you can say "M implements GroupedCollection for any lifetime", and obviously that includes the lifetime I will choose. This is Higher-Ranked Trait Bounds: M: for<'a> GroupedCollection<'a, ...>. So:

fn gc3<M>(map: M)
where
    M: for<'a> GroupedCollection<'a, usize, usize, Iter<'a, usize, Vec<usize>>>,
{
    // ...
}

Playground.

Is it perfect? No. There may be cases where M doesn't implement GroupedCollection for any lifetime, but it does for the lifetime we choose. But you cannot do better without GAT.

Lifetime issue with generic trait bound

1 Answers1