Lifetime of input (key) to HashMap::get() gets entanged w/ that of its output (value)

[zeenix]

The following code:

use std::{borrow::Cow, collections::HashMap};

#[derive(Debug)]
struct Message(String);

impl Message {
    fn interface(&self) -> &str {
        &self.0
    }
}

#[derive(Debug)]
struct Proxy<'p>(Cow<'p, str>);

impl<'p> Proxy<'p> {
    fn interface(&self) -> &str {
        &self.0
    }
}

#[derive(Hash, Eq, PartialEq)]
struct ProxyKey<'key>(Cow<'key, str>);

impl From<&Proxy<'_>> for ProxyKey<'_> {
    fn from(proxy: &Proxy<'_>) -> Self {
        ProxyKey(Cow::from(proxy.interface().to_owned()))
    }
}

impl<'key> From<&'key Message> for ProxyKey<'key> {
    fn from(msg: &'key Message) -> Self {
        ProxyKey(Cow::from(msg.interface()))
    }
}

struct ProxyGroup<'p> {
    proxies: HashMap<ProxyKey<'static>, Proxy<'p>>,
}

impl<'p> ProxyGroup<'p> {
    pub fn new() -> Self {
        Self {
            proxies: HashMap::new(),
        }
    }

    pub fn add<'a: 'p>(&mut self, proxy: Proxy<'a>) {
        let key = ProxyKey::from(&proxy);
        self.proxies.insert(key, proxy);
    }

    pub fn handle_next_signal(&self) {
        let msg = Message(String::from("some.interface"));

        match self.get_proxy_for_msg(&msg) {
            Some(_) => Self::consume_msg(msg),,
            None => (),
        }
    }

    fn get_proxy_for_msg<'a, 'b>(&'a self, msg: &'b Message) -> Option<&'a Proxy<'p>> 
    where
        'p: 'a,
    {
        let key = ProxyKey::from(msg);

        self.proxies.get(&key)
    }

    fn consume_msg(_msg: Message) {}
}

Which I (and devs I consulted on the Discord and IRC) think should compile. However, it doesn't and you get the following error:

error[E0623]: lifetime mismatch
  --> src/main.rs:67:9
   |
61 |     fn get_proxy_for_msg<'a, 'b>(&'a self, msg: &'b Message) -> Option<&'a Proxy<'p>> 
   |                                  --------       ----------- these two types are declared with different lifetimes...
...
67 |         self.proxies.get(&key)
   |         ^^^^^^^^^^^^^^^^^^^^^^ ...but data from `msg` flows into `self` here

error: aborting due to previous error

i-e for some reason the lifetime of the key get associated with lifetime of the Proxy value we get from the HashMap::get call. I think it's likely a compiler bug. Even it is not, it'd be great to get better diagnostics/error message from the compiler for this so I can tell what exactly is going wrong here.

Here is the playground link for trying this out conveniently.

NB: If I change the code to make use of iterator, it works:

    fn get_proxy_for_msg<'a, 'b>(&'a self, msg: &'b Message) -> Option<&'a Proxy<'p>>
    where
        'p: 'a,
    {
        let key = ProxyKey::from(msg);

        self.proxies
            .iter()
            .find(|&(k, _)| &key == k)
            .map(|(_, v)| v)
    }

Playground link.

Meta

rustc --version --verbose:

rustc 1.48.0 (7eac88abb 2020-11-16)
binary: rustc
commit-hash: 7eac88abb2e57e752f3302f02be5f3ce3d7adfb4
commit-date: 2020-11-16
host: x86_64-unknown-linux-gnu
release: 1.48.0
LLVM version: 11.0

Reproducible on nightly (bb17823 2020-12-25) as well.

[SkiFire13]

Minimal example:

use std::collections::HashMap;

pub fn test<'a, 'b>(map: &'a HashMap<&'static (), ()>, key: &'b ()) -> Option<&'a ()> {
    map.get(&key)
}

Doesn't compile with the following error:

error[E0623]: lifetime mismatch
 --> src/lib.rs:4:5
  |
3 | pub fn test<'a, 'b>(map: &'a HashMap<&'static (), ()>, key: &'b ()) -> Option<&'a ()> {
  |                                                             ------     --------------
  |                                                             |
  |                                                             this parameter and the return type are declared with different lifetimes...
4 |     map.get(&key)
  |     ^^^^^^^^^^^^^ ...but data from `key` is returned here

Playground link

[Aaron1011]

It looks like the signature of HashMap::get is too strict, as it requires that &self, &key, and &value all have the same lifetime (via lifetime elision). I think the signature can be relaxed to allow key to have an unrelated lifetime 'a, though this will require changes to hashbrown.

[SkiFire13]

@Aaron1011 I don't think that's the case, the lifetime elision tules tie the output lifetime only to the self borrow if no lifetime is specified, like in this case.

My guess is that this has to do with the Borrow trait. In particular K: Borrow<Q> leads to &'static (): Borrow<&'b ()>, or probably &'a (): Borrow<&'b ()> due to variance. This apparently is satisfied only for 'b = 'a thanks to impl<T> Borrow<T> for T.

Here's an example that IMO shows this problem with a different error:

fn assert_impl_borrow<A, B>(_: A, _: B) where A: std::borrow::Borrow<B> {}

fn test<'b>(a: &'static (), b: &'b ()) {
    assert_impl_borrow::<&'static (), &'b ()>(a, b);
}

A solution would be writing something like impl<T, U> Borrow<U> for T where U <: T where U <: T means U is a subtype of T, however I don't think there's a way to express that relation.

Edit:

fn assert_impl_borrow<A, B>(_: A, _: B) where A: std::borrow::Borrow<B> {}

fn test<'a, 'b>(a: &'a (), b: &'b ()) {
    assert_impl_borrow::<&'a (), &'b ()>(a, b);
}

This gives a more similar error

[Aaron1011]

You're right - I forgot how the lifetime elision rules work.

A more targeted impl would be impl<'a, 'b: 'a, T> Borrow<&'a T> for &'b T, which would not require a way of expressing a general 'subtype bound'. Unfortunately, I think this would require some type of 'intersection/lattice' specialization, since this new impl would (intentionally) apply in cases where impl<T> Borrow<T> for T does not.

[SkiFire13]

That impl might work with specialization, not sure if it already supports lifetimes. However even if it was included in the stdlib it still doesn't cover any struct that's covariant over a generic lifetime (for example any struct that wraps a shared reference)

[Dylan-DPC]

Current error:

error: impl method assumes more implied bounds than the corresponding trait method
 --> src/main.rs:9:22
  |
9 |     fn f<'b>(mut _x: &'static &'b Ty, y: &'b Ty) -> &'static Ty {
  |                      ^^^^^^^^^^^^^^^ help: replace this type to make the impl signature compatible: `&'static &'a Box<&'static u8>`
  |
  = warning: this was previously accepted by the compiler but is being phased out; it will become a hard error in a future release!
  = note: for more information, [see issue #105572 <https://github.com/rust-lang/rust/issues/105572>](https://github.com/rust-lang/rust/issues/105572)
  = note: `#[deny(implied_bounds_entailment)]` on by default