Transitive Borrow trait?

help
1

A little background: I'm the owner of the bimap crate, which is a two-directional bijective map implementation. A BiHashMap<L, R> is internally composed of two hashmaps left2right: HashMap<Rc<L>, Rc<R>> and right2left: HashMap<Rc<R>, Rc<L>>. Both hashmaps share the left and right values through the Rcs.

I'd like to be able to implement an API similar to HashMap's get() method, which in my case would look like

fn get_by_left<Q>(&self, left: &Q) -> Option<&R>
where
    Rc<L>: Borrow<Q>,
    Q: Eq + Hash {
    // ...
}

Unfortunately, this doesn't work. When I try using a &str to get() with a BiHashMap<String, usize>, I get the error

the trait `std::borrow::Borrow<&str>` is not implemented for `std::rc::Rc<std::string::String>`

As I see it, Borrow<T> is implemented for Rc<T>, and Borrow<str> is implemented for String, so transitively Borrow<str> could be implemented for Rc<String>. Is there any way to accomplish that? Or, is there another way to get an API similar to HashMap's?

2

I can't see a way to make what you want work. HashMap's API is great most of the time, but with any advanced usage, you quickly run into a wall.

Something you can try is writing a private wrapper struct BiMapRc<T>(Rc<T>) and implement the correct Borrow behavior on that. Something like:

impl<T, U> Borrow<U> for BiMapRc<T> where T: Borrow<U> {
    fn borrow(&self) -> &U {
        self.0.borrow()
    }
}

This fails to compile because if T: Borrow<BiMapRc<T>>, this conflicts with the blanket impl Borrow<T> for T, but maybe you find a way to make it work anyway.

If all else fails, there's also the unstable, nightly-only raw entry API.

1 Like
3

Thanks for the response. I hadn't heard of the raw entry API, but it's probably the best way to go since one of the uses listed in the documentation is

Using a search key that doesn't work with the Borrow trait

However I'd like to keep my crate usable on stable Rust. Perhaps I can put it behind a feature flag, or (more likely) just wait until it lands on stable.

4

This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.