HashMap::get and borrow::Cow result in too strict a lifetime

help
1

I'm trying to create a HashMap that has tuple keys, where some of the tuple entries can be looked up by reference. I've seen mentioned before that borrow::Cow could be used to solve this problem. However, it seems to cause some issue I'm having difficulty understanding.

Here's a (very) reduced form of my problem:

use std::collections::HashMap;
use std::borrow::Cow;

struct Table {
    map: HashMap<(Cow<'static, str>, Cow<'static, str>), String>,
}

impl Table {
    fn get_chars<'a, 'b>(&'a self, first: &'b str, second: &'b str) -> &'a str {
        let key: (Cow<'b, str>, Cow<'b, str>) = (Cow::Borrowed(first), Cow::Borrowed(second));
        let m: &'a HashMap<(Cow<'static, str>, Cow<'static, str>), String> = &self.map;
        let s: &'a String = HashMap::get(m, &key).unwrap();
        return &s;
    }
}

The issue I have is that borrowck is convinced that s cannot have lifetime 'a, since the key has lifetime 'b. I don't know why this is the case, since m clearly has lifetime 'a. I might expect some error due to the Cow lifetimes not matching, but the error messages on nightly and stable don't mention it at all.

Is there a way of working around this problem? Am I missing something?
Alternatively, is it possible to create a type like Cow that doesn't have this problem?

Playground here

2

The signature of HashMap::get is:

fn get<Q: ?Sized>(&self, k: &Q) -> Option<&V>
where
    K: Borrow<Q>,
    Q: Hash + Eq,

In your case K=(Cow<'static, str>, Cow<'static, str>) and Q=(Cow<'b, str>, Cow<'b, str>). Let's check whether K: Borrow<Q>.

fn with_b_lifetime<'b>() {
    check_borrow::<
        (Cow<'static, str>, Cow<'static, str>),
        (Cow<'b, str>, Cow<'b, str>)
    >();
}

fn check_borrow<K, Q>() where K: Borrow<Q> {}

error[E0308]: mismatched types
  |
  | /     check_borrow::<
  | |         (Cow<'static, str>, Cow<'static, str>),
  | |         (Cow<'b, str>, Cow<'b, str>)
  | |     >();
  | |_____^ lifetime mismatch
  |
  = note: expected type `std::borrow::Borrow<(std::borrow::Cow<'b, str>, std::borrow::Cow<'b, str>)>`
             found type `std::borrow::Borrow<(std::borrow::Cow<'static, str>, std::borrow::Cow<'static, str>)>`

So I guess not! This is causing the lifetime error in your code. It seems like a standard library / type system / type checker limitation to me because Borrow is actually fine to use on those types.

fn call_borrow<'a, 'b>(
    k: &'a (Cow<'static, str>, Cow<'static, str>),
) -> &'a (Cow<'b, str>, Cow<'b, str>) {
    Borrow::borrow(k)
}

Here is a workaround using a bit of unsafe code that lets you use HashMap<(String, String), String>. This is based on How to implement HashMap with two keys?.

use std::collections::HashMap;
use std::mem::ManuallyDrop;

pub struct Table {
    map: HashMap<(String, String), String>,
}

impl Table {
    pub fn get_chars(&self, first: &str, second: &str) -> Option<&str> {
        unsafe {
            // Construct two temporary Strings in a tuple that think they own
            // the data in `first` and `second`.
            let k = (String::from_raw_parts(first.as_ptr() as *mut u8,
                                            first.len(), first.len()),
                     String::from_raw_parts(second.as_ptr() as *mut u8,
                                            second.len(), second.len()));

            // Make sure not to drop our `(String, String)` even if `get`
            // panics. The caller or whoever owns the data behind `first` and
            // `second` will drop them.
            let k = ManuallyDrop::new(k);

            // Deref `k` to get `&(String, String)` and perform lookup.
            let v = self.map.get(&k);

            // Convert `Option<&String>` to `Option<&str>`.
            v.map(String::as_str)
        }
    }
}
1 Like
3

hmm you have to find somebody else who can explain it but if you use

fn get_chars<'a, 'b: 'a> ... it compiles.

1 Like
4

This is probably because Cow<'b, str> cannot be a subtype of Cow<'a, str> unless 'b outlives 'a. I don’t think Borrow comes into play at all here, really - it’s a subtyping relationship issue. Cow<'static, str> is a subtype of any other Cow<'l, str>, so at issue is whether 'b is even valid with respect to 'a, for which the map is borrowed.

5

Playground here

6

Thanks for the detailed explanations. I wish there were some way of wrapping that unsafe code in general, but it looks like that's probably not possible. Maybe at some point a Borrow impl on tuples that allow the elements of the tuple to be borrowed could be added.

I guess the main point of confusion is that the beta and nightly compiler seem to give the wrong error message for this:

error[E0623]: lifetime mismatch
  --> src/main.rs:12:29
   |
9  |     fn get_chars<'a, 'b>(&'a self, first: &'b str, second: &'b str) -> &'a str {
   |                                           -------                      -------
   |                                           |
   |                                           this parameter and the return type are declared with different lifetimes...
...
12 |         let s: &'a String = HashMap::get(m, &key).unwrap();
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...but data from `first` is returned here

I think the real problem is what vitalyd indicated, that Cow<'b, str> is not a subtype of Cow<'static, str>, but the compiler error doesn't reflect that. The error on stable does mention it, so maybe this is a regression in the quality of the error message?

Specifically, stable mentions that:

note: ...so that expression is assignable (expected &(std::borrow::Cow<'_, str>, std::borrow::Cow<'_, str>), found &(std::borrow::Cow<'b, str>, std::borrow::Cow<'b, str>))
7

ordermap has Equivalent which does allow for more such solutions than the default Borrow mechanism. It could work here.

8

The subtyping relationship is the other way: Cow<'static, str> is a subtype of Cow<'some_lifetime, str>.

I also think the error message on nightly is worse than stable. Neither one makes the issue super obvious, but the nightly version makes it worse by muddying the water a bit with its "... but data from first is returned here" part.

error[E0623]: lifetime mismatch
  --> src/main.rs:12:29
   |
9  |     fn get_chars<'a, 'b>(&'a self, first: &'b str, second: &'b str) -> &'a str {
   |                                           -------                      -------
   |                                           |
   |                                           this parameter and the return type are declared with different lifetimes...
...
12 |         let s: &'a String = HashMap::get(m, &key).unwrap();
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...but data from `first` is returned here