Implementing Borrow trait for a type with a lifetime

Question

I'm trying to use. strongly typed wrapper for a "keys" in my program, so that I don't mistake arbitrary strings for a Key. I have:

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Key(String);

I have a HashMap<Key, _>, and I want to lookup values with a reference to a key type (i.e. not having to own the string). It seems like what I need to do is:

create a "ref" type for my Key:

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct KeyRef<'a>(&'a String);

(in reality I'd want KeyRef<'a>(&'a str), but using String makes for a clearer example)

implement Borrow<KeyRef<'_>> for Key

I've tried my best, here's a playground link

My most explicit attempt (annotating all lifetimes) is:

impl<'a> Borrow<KeyRef<'a>> for Key {
    fn borrow<'b>(&'b self) -> &'b KeyRef<'a> where 'b: 'a {
        let string_ref : &'a String = &self.0;
        let key_ref : &'a KeyRef<'a> = &KeyRef(string_ref);
        key_ref
    }
}

Which gives me the error: "lifetime parameters or bounds on method borrow do not match the trait declaration".

Intuitively it feels like this should be possible:

KeyRef holds a reference of lifetime 'a, so any value of KeyRef cannot outlive 'a.
In fn borrow<'b>(&'b self), 'b can't be greater than 'a due to the above

But the compiler doesn't seem to like my explicit attempt to demonstrate that (with where 'b: 'a), and leaving it off I get "cannot infer an appropriate lifetime for borrow expression due to conflicting requirements"

Could you elaborate on I want to lookup values without passing a full string? — Alexey Larionov
Implementing Borrow<A> for B does not read as "Borrowing B can yield an A", but "Any borrow of a B can be used to yield any borrow of an A, subject to lifetime validation", that's where your mistake is. — L. Riemer
@AlexeyLarionov clarified in the question that I want to be able to lookup by a reference, i.e. something I can get from a &Key without additional allocations. — gfxmonk
@L.Riemer can you expand on that? I wrote down my intuition at the end of the question, which seems like what you mean by "subject to lifetime validation". I assume I'm wrong about something in there, does that mean it's impossible? — gfxmonk
To expand a little: In this case, you can of course not use any &self to yield any &KeyRef<' _> - the generic lifetime needs to be constrained, by the lifetime of the self-borrow. You can't do that though, it's not in the trait functions signature, for good reason. As said by others, you are overcomplicating things here. You don't need "additional allocations" when doing this the rusty way. — L. Riemer

user2722968 user2722968 · Accepted Answer · 2021-01-23T11:26:55

As far as I understand your situation, you are needlessly overcomplicating things. A straightforward implementation:

use std::collections::HashMap;
use std::borrow::Borrow;

#[derive(Debug, Clone, PartialEq, Eq, Hash)]
struct Key(String);

impl Borrow<str> for Key {
    fn borrow(&self) -> &str {
        &self.0
    }
}

impl Borrow<String> for Key {
    fn borrow(&self) -> &String {
        &self.0
    }
}

fn main() {
    let mut map = HashMap::new();
    map.insert(Key("one".to_owned()), 1);

    // Because Key is Borrow<String>
    println!("{:?}", map.get("one".to_owned()));
    
    // Because Key is Borrow<str>
    println!("{:?}", map.get("one"));
}

Implementing Borrow trait for a type with a lifetime

1 Answers