Is the lifetime of a BTreeMap::get() result attached to the key as well as the map?

Hi all. I'm having trouble using trait objects to implement an s-expression-like structure with some map-like functionality. The boiled down essence of the problem follows. I can get it to work if I have method fn get<'v>(&'v self, _k: &'v dyn Value) -> Option<&'v dyn Value> but that's no good because it forces the key lifetime to be the same as the map lifetime! Could the underlying problem be that BTreeMap's get method isn't specific enough about the lifetimes involved, or am I just misunderstanding something important? Any help much appreciated.

pub trait Value {
    fn get(&self, _k: &dyn Value) -> Option<&dyn Value> {
        None
    }
}

impl<V: Value> Value for std::collections::BTreeMap<Box<dyn Value>, V> {
    fn get(&self, k: &dyn Value) -> Option<&dyn Value> {
        match std::collections::BTreeMap::get(self, k) {
            Some(v) => Some(v),
            None => None,
        }
    }
}

// The remaining code is not interesting for the problem at hand
impl<'a> PartialEq for dyn Value + 'a { fn eq(&self, _other: &Self) -> bool { todo!() }}
impl<'a> Eq for dyn Value + 'a {}
impl<'a> Ord for dyn Value + 'a { fn cmp(&self, _other: &Self) -> std::cmp::Ordering { todo!() }}
impl<'a> PartialOrd for dyn Value + 'a { fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> { Some(self.cmp(other)) }}

(Playground)

Errors:

   Compiling playground v0.0.1 (/playground)
error: lifetime may not live long enough
  --> src/lib.rs:10:24
   |
8  |     fn get(&self, k: &dyn Value) -> Option<&dyn Value> {
   |            -         - let's call the lifetime of this reference `'1`
   |            |
   |            let's call the lifetime of this reference `'2`
9  |         match std::collections::BTreeMap::get(self, k) {
10 |             Some(v) => Some(v),
   |                        ^^^^^^^ associated function was supposed to return data with lifetime `'2` but it is returning data with lifetime `'1`
   |
help: consider introducing a named lifetime parameter and update trait if needed
   |
8  |     fn get<'a>(&'a self, k: &'a dyn Value) -> Option<&dyn Value> {
   |           ++++  ++           ++

error: could not compile `playground` due to previous error

I think this solves your problem (playground):

pub trait Value {
    fn get<'a, 'b>(&'a self, _k: &'a dyn Value) -> Option<&'b dyn Value>
    where
        'a: 'b,
    {
        None
    }
}

impl<V: Value> Value for std::collections::BTreeMap<Box<dyn Value>, V> {
    fn get<'a, 'b>(&'a self, k: &'a dyn Value) -> Option<&'b dyn Value>
    where
        'a: 'b,
    {
        match std::collections::BTreeMap::get(self, k) {
            Some(v) => Some(v),
            None => None,
        }
    }
}

The problem seems to be that Box<T> only implements Borrow<T>.

What you need is that Box<T> implements Borrow<U> where T: U.

Looks like an omission in the standard library.

1 Like

The problem is with trait objects! The compiler doesn't know that it is okay to borrow Box<dyn (Value + 'a)> as &dyn (Value + 'b) when b is shorter than a. And this is indeed correct: your trait object might not be covariant (more about variance here).

Easiest solution is to make your trait object 'static like this playground. Tell us if you need it to be non-static; we'd need to do some manual Borrow impls.

That's not quite right. The lifetime of a trait object is covariant -- in fact, due to how unsizing coercion works, it's covariant even in otherwise invariant positions.

The Borrow, Eq and Ord constraints require that the lifetimes of the operands are the same, though.

If we supply the elided lifetimes in the OP signature, we get

fn get<'s, 'd>(&'s self, k: &'d (dyn Value + 'd) -> Option<&'s (dyn Value + 's)>

And we're effectively trying to call

// Lifetimes must coerce to the same thing for comparison
BTreeMap::<Box<dyn Value + 'd>, V>::get::<dyn Value + 'd>(self, k)

But we can't pass a &'s self if 's is longer than 'd, Because that would have to coerce to an invalid

&'s BTreeMap<Box<dyn Value + 'd>>

And the upshot is you have to constrain 'd: 's somehow; making them equal is one way to do so.

(You also have to tie 's to the object lifetime returned as the borrow of Self is the only thing constraining the validity of the V you're coercing to dyn Value + '_).

1 Like

You’re right. I mistakenly thought that dyn Value + 'v would behave similarly to dyn Value<'v>.

Hi all, thank you all for your responses. What I'm hearing is that it might very well not be possible to do what I need! (Please forgive my not @-mentioning some of your names here, as apparently there's a rule that new users are only able to mention two other users in a post :roll_eyes:)

Unfortunately @-RedDocMD, the solution you offer is essentially the fn get<'a>(&'a, &'a) -> &'a solution that the compiler suggests, which definitely compiles and runs (for simple use cases) but doesn't solve the problem (for nontrivial uses).

Relatedly unfortunately, @wishawa, I think I do need non-static, because I'd like to be able to write utilities like

fn getit<'a>(d: &'a dyn Value, k: &str) -> Option<&'a dyn Value> {                                                                                                          
  d.get(&k)
}

where &str: Value, and I can't see a path to making the lifetimes of the various dyn Values line up. (Maybe if I implemented for str rather than &str... but here I'm just throwing random things at the wall to see what sticks...) What Borrow impls will we need?

I wonder if @-tczajka's comment is close to the mark. Looking at the signature of BTreeMap::get it seems quite plausible (though I worry I haven't properly understood what @quinedot was saying). How might I go about testing the hypothesis?

I'm hesitant about @quinedot's suggestion: when I spell out the full BTreeMap::<...>::get::<...>(...) call in the code, the error message is different, and doesn't talk about the lifetimes of the v resulting from the get call anymore. My inexperience here may be leading me astray. Is there some way of getting Rust to print out fully-elaborated code so I can see the results of type and lifetime inference?

Here's the magic Borrow impl needed Rust Playground

The main idea consists in passing a different type ValueWrapper to get so that you can impl<'a, 'b: 'a> Borrow<ValueWrapper<'a>> for Box<dyn Value + 'b>. This however requires being able to convert a &(dyn Value + 'a) to a &ValueWrapper<'a>, and the trick here is to use bytemuck to safely implement this cast.

2 Likes

Thanks so much @SkiFire13! That works perfectly for me. The missing piece was bytemuck; I'll try to remember that for next time something like this comes up :-)

Non-'static might've been a bad description here. Do you need dyn Value to be non-owned? dyn Value + 'static means the value is owned. You can still have non-'static borrows of it; &'a (dyn Value + 'static) means a borrow lasting for 'a, where the borrowed value is owned.

Not that this matter :slight_smile: @SkiFire13 's solution works well even when dyn Value is not owned.

1 Like