Trouble with lifetimes in `Borrow` implementation

[SamSamSamSamSamSam]

I have a HashSet (actually a DashSet from the DashMap crate) which holds Arc<Foo>, where Foo looks like this:

struct Foo {
    pub bar: usize,
    pub children: [Whiz],
}

Yes, I'm aware that unsized types like this are tricky - that's not the topic of this post.

I'm trying to implement a lookup function like this:

fn lookup(&mut set: DashSet<Arc<Foo>>, bar: usize, children: &[Whiz]) -> Option<Arc<Foo>> {
    todo!();
}

The trickiness here comes from the fact that the keys are stored inside Arcs, but I don't want to allocate a new Arc or Foo to compare against during the lookup.

DashSet lets us look things up by any type Q where the Key type is Borrow<Q>, so I thought that I could be clever and do something like this:

struct LookupKey<'a> {
    bar: usize,
    children: &'a [Whiz],
}

// impls to give it identical `Eq` and `Hash` behaviour to `Arc<Foo>` elided

// Borrow Arc<Foo> as LookupKey so we can call .get() by LookupKey
impl<'a> Borrow<LookupKey<'a>> for Arc<Foo> {
    return &LookupKey{ bar: self.bar, children: &self.children };
}

This "clever" solution isn't working out for me, because I can't get the lifetimes to work. In the above Borrow implementation it fails to infer a lifetime on self.children due to conflicting requirements, and all of my playing about with trying to make lifetimes explicit has failed.

I've only been playing around in Rust for a week or so, and this is my first time not managing to win a fight against the borrow checker on my own. Help would be appreciated, both with how to make this Borrow implementation work, and also any comments on whether I'm solving the lookup problem in a sensible way.

[steffahn]

It’s possible to work around the problem with a trait object

use std::{borrow::Borrow, hash::Hash, sync::Arc};

use dashmap::DashSet;

#[derive(PartialEq, Eq, Hash)]
struct Whiz;

#[derive(PartialEq, Eq, Hash)]
struct Foo {
    pub bar: usize,
    pub children: [Whiz],
}

fn lookup(set: &DashSet<Arc<Foo>>, bar: usize, children: &[Whiz]) -> Option<Arc<Foo>> {
    #[derive(PartialEq, Eq, Hash)]
    struct BorrowedFoo<'a> {
        bar: usize,
        children: &'a [Whiz],
    }
    trait FooTrait {
        fn borrowed(&self) -> BorrowedFoo<'_>;
    }
    impl FooTrait for Arc<Foo> {
        fn borrowed(&self) -> BorrowedFoo<'_> {
            BorrowedFoo {
                bar: self.bar,
                children: &self.children,
            }
        }
    }
    impl FooTrait for BorrowedFoo<'_> {
        fn borrowed(&self) -> BorrowedFoo<'_> {
            BorrowedFoo {
                bar: self.bar,
                children: self.children,
            }
        }
    }
    impl<'a> Borrow<dyn FooTrait + 'a> for Arc<Foo> {
        fn borrow(&self) -> &(dyn FooTrait + 'a) {
            self
        }
    }
    impl Hash for dyn FooTrait + '_ {
        fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
            self.borrowed().hash(state)
        }
    }
    impl PartialEq for dyn FooTrait + '_ {
        fn eq(&self, other: &Self) -> bool {
            self.borrowed().eq(&other.borrowed())
        }
    }
    impl Eq for dyn FooTrait + '_ {}

    let key = BorrowedFoo { bar, children };
    set.get(&key as &dyn FooTrait).as_deref().cloned()
}

[SamSamSamSamSamSam]

That's a bit more complicated than I was expecting it to be, but I'll grok that and give it a go, thanks!

Is the use of the dyn stuff going to create runtime overhead? I haven't needed to work with dyn yet. This is a very hot path, so I'd rather dip into unsafe or something than accept overhead. I would hope that if we've got virtual calls here, there's enough information for LLVM to devirtualize.

[steffahn]

I believe, a dyn-free alternative is only possible with the (AFAIK unstable) raw API of dashmap together with the unstable (nightly-only) raw API of the standard library's HashMap:

#![feature(build_hasher_simple_hash_one)]
#![feature(hash_raw_entry)]

// also use `raw-api` feature of `dashmap` 

use std::{
    hash::{BuildHasher, Hash},
    sync::Arc,
};

use dashmap::DashSet;

#[derive(PartialEq, Eq, Hash)]
struct Whiz;

#[derive(PartialEq, Eq, Hash)]
struct Foo {
    pub bar: usize,
    pub children: [Whiz],
}

fn lookup(set: &DashSet<Arc<Foo>>, bar: usize, children: &[Whiz]) -> Option<Arc<Foo>> {
    #[derive(PartialEq, Eq, Hash)]
    struct BorrowedFoo<'a> {
        bar: usize,
        children: &'a [Whiz],
    }
    let key = BorrowedFoo { bar, children };
    let hash_usize = set.hash_usize(&key);

    let n = set.determine_shard(hash_usize);
    let shard = set.shards()[n].read();
    let hash = shard.hasher().hash_one(&key);
    let entry = shard.raw_entry().from_hash(hash, |candidate_key| {
        BorrowedFoo {
            bar: candidate_key.bar,
            children: &candidate_key.children,
        } == key
    });

    Some(entry?.0.clone())
}

(while using unstable standard library API anyways, I’ve also used build_hasher_simple_hash_one for convenience)

If you don't want to be limited to nightly and dependent on unstable API, you could still use this e.g. to benchmark against the stable approach with the trait object. It seems feasible that the trait object approach gets optimized properly, too; and even some remaining virtual function call(s) shouldn't be all that slow.