Open jsdw opened 5 months ago
I simplified the example a bit, nethier Foo
nor Key
are needed.
use std::collections::HashMap;
fn resolve<'this, 'a, T>(types: &'this HashMap<&'static str, T>, key: &'a str) -> Option<&'this T> {
types.get(&key)
}
Duplicate of: https://github.com/rust-lang/rust/issues/80389#issuecomment-752067798 however the practical example here is amenable to a concrete possible fix, hence I'm expanding on the explanation of how to arrive there.
get(&Q)
relies on the bound Borrow<Q> for K
. You can use a reference to any query type Q
provided that the stored keys can be borrowed as that query type. In Rust 'borrowed as' is integrated with the type system, using the Borrow
trait, to say: these types have the same equality, hashing, comparison.
The standard library provides:
Borrow<Q> for &'_ Q
, this is what makes &'static str
work since there you'll find that the argument Q = str
matches.Borrow<T> for T
which in your case is relevant since it leads to the type error. The compiler infers that the only substitution to satisfy Borrow<Q> for Key<'this>
is for it to hold Q = Key<'this>
but you have Q = Key<'a>
. And then to tries to coerce the reference to &Key<'a>
into &Key<'this>
to satisfy that function argument type. This is possible for the covariant type Key
but only to shorten lifetimes, which notably is the inverse relationship of what is possible to solve via borrowed reference. This directly leads to the error message.Fixing this is possible by ensuring the Borrow
exists for different lifetimes, the way an indirect reference can. One layer of struct wrapper is required. It's not possible to write Borrow<Key<'b>> for Key<'a>
directly since this overlaps with the reflexive impl given in the standard library.
#[derive(Hash, PartialEq, Eq)]
struct Key<'lt> {
inner: &'lt str,
}
/// Wraps key so it can be `Borrow`'d under any short lifetime.
///
/// Avoid the conflicting implementation problem of using the same type.
#[derive(Hash, PartialEq, Eq)]
#[repr(transparent)]
struct KeyCapsule<'lt> {
inner: Key<'lt>,
}
// Hash, PartialEq, Eq, are compatible due to the way single-attribute structs are derived.
// It just calls the methods on each field.
impl<'a, 'b: 'a> core::borrow::Borrow<Key<'a>> for KeyCapsule<'b> {
fn borrow(&self) -> &Key<'a> {
&self.inner
}
}
fn with<'this, 'a>(map: &std::collections::HashSet<KeyCapsule<'this>>, key: &'a str) -> bool {
map.contains(&Key {
inner: key,
})
}
fn main() {
let mut map: std::collections::HashSet::<KeyCapsule<'static>>
= Default::default();
map.insert(KeyCapsule { inner: Key { inner: "Hello" }});
assert!(with(&map, "Hello"));
}
Thank you for the very insightful response @HeroicKatora!
As I switched to using hashbrown::HashMap
for no-std support, I ended up finding the raw_entry
API really useful for working around the issue and did something like this, which I'll leave here just in case it helps anybody:
// Define a key type to insert into a hashbrown::HashMap
#[derive(Clone, Debug, PartialEq, Eq)]
struct Key {
a: String,
b: String,
}
impl core::hash::Hash for Key {
fn hash<H: core::hash::Hasher>(&self, state: &mut H) {
hash_key(self.a, &self.b, state);
}
}
fn hash_key<H: core::hash::Hasher>(a: &str, b: &str, state: &mut H) {
a.hash(state);
b.hash(state);
}
// And then, we can lookup using the raw_entry API like:
fn lookup<'map>(
a: &str,
b: &str,
map: &'map HashMap<Key, Info>,
) -> Option<(&'map Key, &'map Info)> {
// Manually construct the key hash
let hash = {
use core::hash::{BuildHasher, Hasher};
let mut state = map.hasher().build_hasher();
hash_key(a, b, &mut state);
state.finish()
};
// Look up the entry by hash, and then compare keys we get back to find the matching key.
map.raw_entry().from_hash(hash, |k| k.a == a && k.b == b)
}
Though at some point I might go back to using struct Key { a: Cow<'static,str>, b: Cow<'static,str> }
plus your wrapper approach instead, which would avoid any hashing shenanigans (and the chance for something to go wrong there if fields are added or whatever).
Happy to see this closed anyways now. Thanks!
I'm not sure what words to use to actually describe (or search for a dupe) this issue, so I'll just post it here and hope that it makes more sense to you guys (and sorry if it is a dupe; I'm almost sure it would be)!
So basically, if I write this code:
I get back this error:
Despite the fact that
HashMap::get()
returns the values with a lifetime of self, and nothing to do with the key provided.However, this does work:
Removing the
struct
indirection when defining the key type seems to make things happy!Background
The above is a minimal reproduction of the issue I ran into, but the reason I ran into it is because I want to have something like:
In other words, I want to be able to borrow more than 1 value to lookup some owned key in the hashmap. I went down the route of trying
struct Key<'a> { a: Cow<'a,str>, b: Cow<'a,str>
and thenHashMap<Key<'static>, String>
, but this led me to bumping up against this odd lifetime issue :)Any pointers would be amazingly welcome!