Why does HashSet::take require explicit lifetime but HashSet::get does not?

This code doesn't compile if the get operation is replaced with take in the do_something method. Why?

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

#[derive(Debug)]
struct OwnedKey {
    a: String,
}

#[derive(Debug)]
enum Key<'a> {
    OwnedKey(OwnedKey),
    RefKey(&'a str),
}

impl Hash for Key<'_> {
    fn hash<H>(&self, state: &mut H)
    where
        H: std::hash::Hasher,
    {
        match self {
            Key::OwnedKey(r) => r.a.hash(state),
            Key::RefKey(s) => s.hash(state),
        }
    }
}

impl PartialEq for Key<'_> {
    fn eq(&self, other: &Self) -> bool {
        match self {
            Self::OwnedKey(self_r) => match other {
                Self::OwnedKey(other_r) => return self_r.a == other_r.a,
                Self::RefKey(other_s) => return self_r.a == *other_s,
            },
            Self::RefKey(self_s) => match other {
                Self::OwnedKey(other_r) => return other_r.a == *self_s,
                Self::RefKey(other_s) => return *self_s == *other_s,
            },
        }
    }
}

impl Eq for Key<'_> {}

struct Test<'a> {
    map: HashSet<Key<'a>>,
}

impl<'a> Test<'a> {
    fn new() -> Self {
        Test {
            map: HashSet::new(),
        }
    }

    fn insert(&mut self, key: Key<'a>) {
        self.map.insert(key);
    }

    fn do_something(&mut self, some_string: &String) {
        let lookup_key = Key::RefKey(some_string.as_str());
        match self.map.get(&lookup_key) {
            Some(val) => {
                println!("{:?}", val);
            }
            None => {
                println!("Found nothihng!");
            }
        }
    }
}

fn main() {
    let mut test = Test::new();

    test.insert(Key::OwnedKey(OwnedKey {
        a: "sdfsdf".to_string(),
    }));

    let some_string = "sdfsdf".to_string();
    test.do_something(&some_string);
}

(Playground)

That Key type looks a lot like the Cow type ? Would this work for you ?

2 Likes

Because HashSet::take take &mut self, it is invariant over lifetimes in its Self type.

That is, the compiler won't let you pass a short-lived reference to HashSet::take where the set stores longer-lived references, because it is concerned that take could write that short-lived reference into the long-lived set. (It wouldn't actually do this, but the compiler has no way to know that.)

If you want to define a custom type that works similarly to Cow, you could implement the Borrow trait:

impl Borrow<str> for Key<'_> {
    fn borrow(&self) -> &str {
        match self {
            Key::OwnedKey(OwnedKey { a }) => a,
            Key::RefKey(s) => s,
        }
    }
}

(Playground)

4 Likes

Hmm, I'm not sure to be honest. What I would like to do is insert a "heavy" owned type that contains a lot of data (a key + a bunch of other fields), and then be able to do lookups + mutable retrieval/removal using just a lightweight reference (just the key portion) at zero copy. Wouldn't Cow in this case copy the reference key?

That is, the compiler won't let you pass a short-lived reference to HashSet::take where the set stores longer-lived references, because it is concerned that take could write that short-lived reference into the long-lived set. (It wouldn't actually do this, but the compiler has no way to know that.)

Is there a way to allow that here? Or would that mean having to reimplement the hashset?

Unfortunately, the way the Borrow trait is defined makes it impossible in the general case to efficiently use "borrowed" versions of keys that contain multiple owned fields, while using a standard library HashSet. There are a couple of ways to solve this with external crates:

  • Create a set using hashbrown::HashMap and use its raw_entry_mut method to do lookups using a "borrowed" key.
  • Or use an indexmap::IndexSet and implement the indexmap::Equivalent trait for your "owned" and "borrowed" key types.
2 Likes

I almost forgot, there's also this workaround with trait objects that works with the standard HashSet.

Thanks. I stumbled on this solution on Stackoverflow, but it seems like this wouldn't work if one of the key types were a Rc<RefCell<T>>? Because the borrow trait wouldn't be possible to implement? Also, would this have worse performance because of the vtable lookup? I decided to go with the raw_entry_mut solution you suggested for the first reason.

The optimizer is pretty good at devirtualizing this sort of dynamic dispatch, where all of the concrete types appear in the same function. You’d have to check the generated assembly to be sure, though.

1 Like

It's a bit trickier, but here's a sketch of how to use the trait object trick when the owned key contains a RefCell: Rust Playground

2 Likes