Lifetime mismatch in generic trait with iterator bound

Question

I'm trying to abstract an interface to a map-type backing data structure (currently std::collections::HashMap and std::collections::BTreeMap) so that I can swap out the data structure without affecting the calling code. I'm running into a lifetime error with one particular method: (playground)

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

pub trait GroupedCollection<K, V, KeyIterator>
where
    KeyIterator: Iterator
{
    fn keys(&self) -> KeyIterator;
}

impl<K, V> GroupedCollection<K, V, Keys<'_, K, Vec<V>>> for HashMap<K, Vec<V>>
{
    fn keys(&self) -> Keys<'_, K, Vec<V>> {
        HashMap::keys(&self)
    }
}

fn main() {}

The compiler's telling me I have a lifetime mismatch:

error: `impl` item signature doesn't match `trait` item signature
  --> src/main.rs:12:5
   |
7  |     fn keys(&self) -> KeyIterator;
   |     ------------------------------ expected `fn(&'1 HashMap<K, Vec<V>>) -> std::collections::hash_map::Keys<'2, K, Vec<V>>`
...
12 |     fn keys(&self) -> Keys<'_, K, Vec<V>> {
   |     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ found `fn(&'1 HashMap<K, Vec<V>>) -> std::collections::hash_map::Keys<'1, K, Vec<V>>`
   |
   = note: expected `fn(&'1 HashMap<K, Vec<V>>) -> std::collections::hash_map::Keys<'2, K, Vec<V>>`
              found `fn(&'1 HashMap<K, Vec<V>>) -> std::collections::hash_map::Keys<'1, K, Vec<V>>`
help: the lifetime requirements from the `impl` do not correspond to the requirements in the `trait`
  --> src/main.rs:7:23
   |
7  |     fn keys(&self) -> KeyIterator;
   |                       ^^^^^^^^^^^ consider borrowing this type parameter in the trait

I haven't worked much with the reserved lifetime '_. From reading The Rust Reference: Lifetime Elision, if I understand correctly (and I'm not sure that I do), the following applies:

Default Trait Object Lifetimes

...

If the trait object is used as a type argument of a generic type then the containing type is first used to try to infer a bound.

• If there is a unique bound from the containing type then that is the default

...

My understanding is that this is where the compiler is deriving '1 for both lifetime parameters on the impl signature.

Since I haven't given the compiler any information about lifetimes in my trait definition, my understanding is that the compiler assumes that the &self in fn keys() and type Item = &'a K in the monomorphized hash_map::Keys will have different lifetimes.

After reading this question, I think I might have arrived at the right solution, but it's melting my brain a bit: (playground)

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

pub trait GroupedCollection<'a, K: 'a, V, KeyIterator>
where
    KeyIterator: Iterator<Item = &'a K>,
{
    fn keys(&'a self) -> KeyIterator;
}

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

Am I understanding the problem correctly? And is adding the explicit lifetime 'a the right solution here, or have I done something silly that happened to compile?

Answer 1

When you write a lifetime of '_ it means: "here I should write a lifetime, but I don't particularly care about it, so... whatever".

In particular, when you write it in a trait impl such as:

impl<K, V> GroupedCollection<K, V, Keys<'_, K, Vec<V>>> for ...

it is as if you wrote:

impl<'x, K, V> GroupedCollection<K, V, Keys<'x, K, Vec<V>>> for ...

That is, the users of this impl can instantiate it with any lifetime they want.

But when you write it in the return type of a function such as:

fn keys(&self) -> Keys<'_, K, Vec<V>>

is is as if you wrote:

fn keys<'s>(&'s self) -> Keys<'s, K, Vec<V>>

That is, the lifetime is deduced by the default lifetime rules.

Now, your first compiler error happens because your Keys<'x, _, _> from the trait argument and your Keys<'s, _, _> are not the same, so the type of the function keys() does not match the trait definition.

How to fix it? Well, your implementation of keys must return a value with its lifetime limited to that of self, so if you are willing to change the trait to reflect that:

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

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

Which is almost what you wrote in your second version (I think that you added a few unneeded constraints).

---

Following the comment by @cdhowie above, what you really want is a Generic Associated Type (GAT). This means that it is the implementation of the trait that decides the lifetime, not the user. Unfortunately they are still unstable:

#![feature(generic_associated_types)]

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

pub trait GroupedCollection<K, V>
{
    type KeyIterator<'s> where Self: 's;
    fn keys<'s>(&'s self) -> Self::KeyIterator<'s>;
}

impl<K, V> GroupedCollection<K, V> for HashMap<K, Vec<V>>
{
    type KeyIterator<'s> = Keys<'s, K, Vec<V>>
        where Self: 's;
    fn keys<'s>(&'s self) -> Keys<'s, K, Vec<V>> {
        HashMap::keys(&self)
    }
}

Which I think it is much easier to understand and easier to use.