Is the implementation of IntoIterator for &BTreeMap too restricted?

I was trying to write some kind of Map trait and while trying to implementing I couldn't get it to work with BTreeMap (but no problems with HashMap).

I managed to reduce the problematic code to the following: https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=4f04df28ec1557299a1e6f33dfeb93a3

The error message is still very cryptic (E0311 isn't even present in the error index!):

error[E0311]: the parameter type `K` may not live long enough
  --> src/lib.rs:16:12
   |
16 | impl<K, V> Map for BTreeMap<K, V> {
   |            ^^^
   |
   = help: consider adding an explicit lifetime bound for `K`
   = note: the parameter type `K` must be valid for any other region...
note: ...so that the type `K` will meet its required lifetime bounds
  --> src/lib.rs:16:12
   |
16 | impl<K, V> Map for BTreeMap<K, V> {
   |            ^^^

error[E0311]: the parameter type `V` may not live long enough
  --> src/lib.rs:16:12
   |
16 | impl<K, V> Map for BTreeMap<K, V> {
   |            ^^^
   |
   = help: consider adding an explicit lifetime bound for `V`
   = note: the parameter type `V` must be valid for any other region...
note: ...so that the type `V` will meet its required lifetime bounds
  --> src/lib.rs:16:12
   |
16 | impl<K, V> Map for BTreeMap<K, V> {
   |            ^^^

Anyway, turns out the implementation of IntoIterator for &'a HashMap and &'a BTreeMap are a little different:

impl<'a, K, V, S> IntoIterator for &'a HashMap<K, V, S>
impl<'a, K: 'a, V: 'a> IntoIterator for &'a BTreeMap<K, V>

Can you spot that little difference? It's that K: 'a and V: 'a. That's what causes the error. I don't think they're even needed since the implementation delegates to self.iter() and it doesn't need those bounds.

So here come the question: how can I make the original code work? Obviously I can't modify the stdlib implementation...

How about modifying the trait to include the lifetime? You could do something like this:

use std::collections::{BTreeMap, HashMap};

trait Map<'a>
where
    Self: 'a,
    &'a Self: IntoIterator<Item = (&'a Self::Key, &'a Self::Value)>,
{
    type Key;
    type Value;
}

impl<'a, K: 'a, V: 'a> Map<'a> for HashMap<K, V> {
    type Key = K;
    type Value = V;
}

impl<'a, K: 'a, V: 'a> Map<'a> for BTreeMap<K, V> {
    type Key = K;
    type Value = V;
}

It'd mean when you require the trait you'd have to require T: for<'a> Map<'a>, but it should otherwise work?

Regarding the difference between the two impls, that's... interesting. I would have thought both would require the K: 'a, V: 'a bounds, and I don't really understand how HashMap gets away with it. Both hash_map::Iter<'a, K, V> and btree_map::Iter<'a, K, V> require K: 'a, V: 'a, so I don't think either IntoIterator implementation is actually usable without those bounds. But it's weird how having it explicitly stated in the BTreeMap IntoIterator implementation prevents your initial post's impl from working, when it otherwise would have.

With everything else said, are you sure about this?

If we really could remove the K: 'a, V: 'a bounds from the BTreeMap IntoIterator implementation, it seems like a pure win - something that could definitely be accepted as a PR into rust-lang/rust.

Thanks for the reply!

Yeah I was trying to avoid that. Well, whatever, I just discovered the existance of issue #20671 which just makes it require a lot more boilerplate than that.

My guess is that when you write &'a T it's implied T: 'a, meaning the existance of &'a HashMap<K, V> implies HashMap<K, V>: 'a and so K: 'a and V: 'a.

Yeah, that's really weird. The compiler should be able to infer that those bounds are always satisfied.

I mean, I could, but I don't even know where to start. Well, that's probably also an excuse. I'm just lazy.

I ran into a similar odd problem with that error code the other day.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.