Borrowing / Copying from a more restrictive generic to a less restrictive generic

help
1

Hi. I have a need to create objects of a generic type, and that generic type sometimes has an embedded lifetime. Along these lines:

use core::hash::Hash;
use std::collections::HashSet;

trait Key<'a> : Hash + Eq {
    fn from_owned_key<O : OwnedKey>(owned_key : &'a O) -> Self;
}
impl <'a>Key<'a> for &'a str {
    fn from_owned_key<O : OwnedKey>(owned_key : &'a O) -> Self {
        owned_key.borrow_str().unwrap()
    }
}
impl Key<'static> for String {
    fn from_owned_key<O : OwnedKey>(owned_key : &O) -> Self {
        owned_key.to_string().unwrap()
    }
}

trait OwnedKey : Key<'static> {
    fn borrow_str(&self) -> Option<&str>;
    fn to_string(&self) -> Option<String>;
}
impl OwnedKey for String {
    fn borrow_str(&self) -> Option<&str> {
        Some(&self)
    }
    fn to_string(&self) -> Option<String> {
        Some(self.clone())
    }
}

fn check_container<'a, R : Key<'a>>(container : &HashSet<R>) -> bool
{
    let owned_string = "test_key".to_string();

    let query_key = R::from_owned_key(&owned_string); //This is the problem.
    // query_key is created with the lifetime of 'a, which outlives this
    // function.  I need a way to make something that is the *Type* of
    // R, but with another lifetime.
    
    container.contains(&query_key)
}

fn main() {
    let container : HashSet<&str> = HashSet::new();
    let _ = check_container(&container);
}

Is there another way to create a new Key but with a more limited lifetime, or an alternative way to structure these traits so that it is possible to borrow from a more restrictive generic (OwnedKey) to a less restrictive generic (Key)?

Thank you.

2

What happens here is that the borrow checker can't know that .contains() doesn't take advantage of the potentially-longer lifetime of Key that HashMap has, and only uses it temporarily. Borrow checker treats this call the same as if you called insert. Lifetimes of Key are the same for both, and you can probably see it would be an error to call insert, because the HashMap of longer-lived strings would end up with a short-lived one that was temporarily borrowed for a single function call.

This problem is why HashSet by itself already uses the Borrow trait to allow more flexible keys. You're re-inventing the Borrow trait on top of it, but that won't work. R::from_owned_key is supposed to create a key with R's lifetime, and HashSet doesn't support flexibility of your Key trait, it has its own Borrow trait.

  • You can just force it through with mem::transmute to give contains the lifetime it wants. It will be safe in practice, because you know contains won't keep the value longer than the function call.

  • Or use the Borrow trait instead. Copy the function signature from contains, and it will give you the flexibility to query by either owned or borrowed keys.

1 Like
3

Thank you for the reply!

You can comment out the contains (or change it to a println! so it doesn't disappear during optimization) and you'll get the same error, 'owned_string' does not live long enough. The die is cast (probably because of the Drop trait) when the from_owned_key method creates type with a built-in lifetime exceeding the function scope, that is borrowing the temporary within the function.

You're 100% right that I'm trying to conceptually get a Borrow<> trait, but I need a Borrow<> trait that sometimes makes a clone and sometimes does a format conversion depending on what's needed. I definitely tried make things work with Borrow<> but eventually gave up. :frowning: Maybe I'll give that approach another go - I just got discouraged.

The transmute appears safe in this case, but I was trying to avoid it because I felt like this problem must not be unique to me in this case so perhaps there was a better solution.

Thanks again.

4

<--Edited-->

I wasn't thinking clearly before. I have a solution with transmute that keeps all the unsafe nicely wrapped up in one spot. The key was to transmute inside the trait's impl when I know the concrete types. (so technically one spot per impl) Still not ideal to need unsafe in this situation.

Thanks for all the help and advice.

5

To do this without unsafe, you can use borrowed trait objects for the comparison:

trait KeyData {
    fn get_str(&self)->&str;
}

impl PartialEq for dyn KeyData + '_ {
    fn eq(&self, rhs:&Self)-> bool { self.get_str() == rhs.get_str() }
}

impl Eq for dyn KeyData + '_ {}

impl Hash for dyn KeyData + '_ {
    fn hash<H:Hasher>(&self, state: &mut H) {
        self.get_str().hash(state)
    }
}

// Newtypes so that we can implement Borrow, Eq, & Hash manually
struct BorrowedKey<'a>(&'a str);
struct OwnedKey(String);

// ... See playground for impls ... //

fn check_container<'a, R : Hash+Eq+Borrow<dyn KeyData+'a>>(container : &HashSet<R>) -> bool
{
    let owned = OwnedKey("test_key".to_string());
    let query_key: &dyn KeyData = &owned;
    container.contains(query_key)
}

fn main() {
    let key_str = String::from("test_key");
    let mut container : HashSet<BorrowedKey> = HashSet::new();
    container.insert(BorrowedKey(key_str.as_str()));
    let _ = check_container(&container);
}
1 Like
6

I love this answer. In fact you perfectly answered a question I had earlier about creating a HashMap with heterogeneous type keys. Workaround for Hash trait not being object-safe

This time, however, I want to make something that will compile without any dynamic dispatch. So I think I still need the unsafe.

Thank you for taking the time to explain this pattern. I especially love the macro for all the tedious impls.

7

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.