Another lifetime problem: in HashMap, one type is more general than the other

help
1

I'm struggling with another lifetime-related issue, particularly with HashMap keys. It's difficult to fully explain in words, but I've tried my best to reduce the problem to 150 lines of code. If anyone has suggestions on how to simplify it further, I'd appreciate that too.

It gives

error[E0308]: mismatched types
    |               ^^^^^^^^^^ one type is more general than the other
    = note: expected reference `&'k &_`
               found reference `&&_`
note: the lifetime requirement is introduced here
   --> src\bin\problem.rs:90:5

This question based on question regarding Transitive Lifetimes if that matter.

2

I didn't read the other post and haven't tried to figure out what you're trying to do enough to suggest a solution, but I can explain the error.

Here is the Fields trait and the GAT parts of the implementations. I simplified the bounds of the implementations, but with no change in meaning.[1]

pub trait Fields<K, V> {
    type Key<'k> where Self: 'k;
    type Val<'v> where Self: 'v;
    fn fields(&self) -> impl IteratorTrait<Item = (Self::Key<'_>, Self::Val<'_>)>;
}

impl<V> Fields<usize, &'_ V> for Vec<V> where V: std::borrow::ToOwned {
    type Key<'k> = usize where Self: 'k;
    type Val<'v> = &'v V where Self: 'v;
}

impl<K, V> Fields<&'_ K, &'_ V> for HashMap<K, V>
where
    K: core::hash::Hash + core::cmp::Eq,
    V: std::borrow::ToOwned,
{
    type Key<'k> = &'k K where Self: 'k;
    type Val<'v> = &'v V where Self: 'v;
}

And here's the bound that's involved in the error.

impl<T, RowKey, Row> TableRows for AsTable<'_, T, RowKey, Row>
where
    for<'k, 'v> T: Fields<
        RowKey, 
        &'k Row, 
        Key<'k> = RowKey, 
        Val<'v> = &'v Row
     > + 'k + 'v,
    RowKey: crate::RowKey,

Type parameters like RowKey resolve to a single type, which means that to meet this part of the bound:

T: for<'k> Fields<_, _, Key<'k> = RowKey>

the actual type of Key<'k> can't involve 'k -- because that would be a different type for every lifetime 'k.

// This bound can be met: let RowKey = usize
Vec<V>: for<'k> Fields<_, _, Key<'k> = RowKey>

// This bound *cannot* be met, because for every distinct
// lifetime `'k`, `&'k K` is a distinct type
HashMap<K, V>: for<'k> Fields<_, _, Key<'k> = RowKey>

Or perhaps another way to think about it: RowKey can't resolve to &'k K because RowKey exists outside of the for<'k> ... bound, where 'k isn't defined.

  1. Implementations can't be less general than the trait declaration, so those extra bounds weren't actually doing anything. For example usize: 'k is trivially true for any 'k, and V: 'v is implied by Self = HashMap<K, V>: 'v ↩ī¸Ž

1 Like
3

There's probably not enough information in the OP to do so. You're not using the RowKey associated type so I don't know what it's for. If you remove it, you can get rid of the bound that HashMap can't meet.

 pub trait TableRows {
-    type RowKey;
     type Row;
     fn rows(&self) -> impl IteratorTrait<Item = &Self::Row>;
 }

 impl<T, RowKey, Row> TableRows for AsTable<'_, T, RowKey, Row>
 where
-    for<'k, 'v> T: Fields<RowKey, &'k Row, Key<'k> = RowKey, Val<'v> = &'v Row> + 'k + 'v,
+    for<'k, 'v> T: Fields<RowKey, &'k Row, Val<'v> = &'v Row> + 'k + 'v,
     RowKey: crate::RowKey,
 {
-    type RowKey = RowKey;
     type Row = Row;
     fn rows(&self) -> impl IteratorTrait<Item = &Self::Row> {
-        self.as_ref().fields().map(move |(_k, e): (RowKey, &Row)| e)
+        self.as_ref().fields().map(move |(_k, e): (_, &Row)| e)
     }
 }
2 Likes
4

I see. Thank you for the answer. If I understand correctly you basically dropped definition of key, because the type is not important as long as key is not passed further. But that solution feels like workaround. What if key is passed

-     fn rows(&self) -> impl IteratorTrait<Item = &Self::Row> {
+     fn rows(&self) -> impl IteratorTrait<Item = (Self::RowKey, &Self::Row)> {

What then is proper solution?

5

Then a non-generic parameter/associated type RowKey in TableRows can't support an implementation of Fields where the definition of the GAT Key<'k> incorporates 'k.

HashMap simply doesn't implement IteratorTrait in such a way that the item is a tuple whose 0-indexed field is the same type given any input lifetime on &self, which is what this says is required.

// Same type for every input lifetime        vvvvvvvvvvvv
fn rows(&self) -> impl IteratorTrait<Item = (Self::RowKey, &Self::Row)> {

You could change the TableRows trait to work with one specific lifetime.

pub trait TableRows<'k> {
    type RowKey;
    type Row;

    fn rows(&'k self) -> impl IteratorTrait<Item = (Self::RowKey, &'k Self::Row)>;
}

impl<'k, T, RowKey, Row: 'k> TableRows<'k> for AsTable<'k, T, RowKey, Row>
where
    T: Fields<RowKey, &'k Row, Key<'k> = RowKey, Val<'k> = &'k Row> + 'k,
{
    type RowKey = RowKey;
    type Row = Row;

    fn rows(&'k self) -> impl IteratorTrait<Item = (Self::RowKey, &'k Self::Row)> {
        self.as_ref().fields()
    }
}

But I don't know if this will actually satisfy your end goal or if it's just kicking a deeper problem down the road.

1 Like
6

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.