Confused about apparently escaping reference

help
1

I'm confused why this doesn't compile:

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

struct Cache(Mutex<HashMap<Cow<'static, str>, Vec<u8>>>);

impl Cache {
    fn pop(&self, key: &Cow<'_, str>) {
        self.0
            .lock()
            .unwrap()
            .get_mut(key)
            .and_then(|vec| vec.pop());
    }
}

Error:

error[E0521]: borrowed data escapes outside of method
  --> src/lib.rs:9:9
   |
8  |       fn pop(&self, key: &Cow<'_, str>) {
   |                     ---
   |                     |
   |                     `key` is a reference that is only valid in the method body
   |                     has type `&Cow<'1, str>`
9  | /         self.0
10 | |             .lock()
11 | |             .unwrap()
12 | |             .get_mut(key)
   | |                         ^
   | |                         |
   | |_________________________`key` escapes the method body here
   |                           argument requires that `'1` must outlive `'static`

For more information about this error, try `rustc --explain E0521`.
error: could not compile `playground` (lib) due to previous error

(Playground.)

The diagnostics here seem obviously incorrect -- pop() yields () so no lifetimes can actually escape the method body. Any suggestions for how to fix this?

2

your key is of type Cow<'static, str>, which implements Borrow<str>, so get_mut() need a &str as argument.

impl Cache {
    fn pop(&self, key: &Cow<'_, str>) {
        self.0
            .lock()
            .unwrap()
            .get_mut(key.as_ref())
            .and_then(|vec| vec.pop());
    }
}

or even simpler, you don't need Cow as parameter type, just use &str

impl Cache {
    fn pop(&self, key: &str) {
        self.0
            .lock()
            .unwrap()
            .get_mut(key)
            .and_then(|vec| vec.pop());
    }
}
3

Note that the compiler doesn't mark the .and_then(...) part of your code as an error, which matches that the pop method call doesn't affect the correctness. You may remove the .and_then(...) part entirely, and the error stays.

The method which the compiler complains about isn't Cache::pop, it's get_mut. The signature requires that Cow<'static, str> (the type of the HashMap key) can be borrowed as &Cow<'_, str>. This is only true if '_: 'static, which the compiler complains about. You need to explicitly convert key to &str in order to use it here:

impl Cache {
    fn pop(&self, key: &Cow<'_, str>) {
        self.0
            .lock()
            .unwrap()
            .get_mut(&key[..])
            .and_then(|vec| vec.pop());
    }
}
1 Like
4

the diagnostic is a little bit off the point. because Borrow is reflexive, i.e. all types implements Borrow<Self>. in your particular case, the key type Cow<'static, str> both implements Borrow<str> and Borrow<Cow<'static, str>>, but you are giving an Cow<'_, str> as argument, so the type checker complain about the lifetime, but it really should complain about not satisfy the Borrow<Key> bound.

5

Okay, I guess the example code is overly simplified. The original case is more like this:

use std::collections::HashMap;
use std::sync::Mutex;

struct Cache(Mutex<HashMap<Key<'static>, Vec<u8>>>);

impl Cache {
    fn pop(&self, key: &Key<'_>) {
        self.0
            .lock()
            .unwrap()
            .get_mut(key)
            .and_then(|vec| vec.pop());
    }
}

#[derive(Eq, Hash, PartialEq)]
enum Key<'a> {
    Borrowed(&'a str),
    Owned(String),
}

(Playground.)

Is there a way I can implement Borrow to make this work?

6

it's the same deal, you don't need a Key type to lookup an entry in a HashMap, you just need a borrowed form of the Key. if your Key mimics the std::borrow::Borrow semantics, it surely should implement Borrow (could also implement AsRef and Deref for convenience).

#[derive(Eq, Hash, PartialEq)]
enum Key<'a> {
    Borrowed(&'a str),
    Owned(String),
}
impl<'a> Borrow<str> for Key<'a> {
    fn borrow(&self) -> &str {
        match self {
            //...
        }
    }
}
impl Cache {
    fn pop(&self, key: &str) {
        self.0
            .lock()
            .unwrap()
            .get_mut(key)
            .and_then(|vec| vec.pop());
    }
}
7

Okay, another round of desimplification:

use std::collections::HashMap;
use std::sync::Mutex;

struct Cache(Mutex<HashMap<Type<'static>, Vec<u8>>>);

impl Cache {
    fn pop(&self, ty: &Type<'_>) {
        self.0
            .lock()
            .unwrap()
            .get_mut(ty)
            .and_then(|vec| vec.pop());
    }
}

#[derive(Eq, Hash, PartialEq)]
enum Type<'a> {
    Key(Key<'a>),
    Number(usize),
}

#[derive(Eq, Hash, PartialEq)]
enum Key<'a> {
    Borrowed(&'a str),
    Owned(String),
}

(Playground.)

8

forget to mention, don't use auto derived Hash, Ord, and Eq if your type implements Borrow. see the document for the Borrow trait. to quote:

when providing implementations for additional traits, it needs to be considered whether they should behave identically to those of the underlying type as a consequence of acting as a representation of that underlying type. Generic code typically uses Borrow<T> when it relies on the identical behavior of these additional trait implementations. These traits will likely appear as additional trait bounds.

In particular Eq, Ord and Hash must be equivalent for borrowed and owned values: x.borrow() == y.borrow() should give the same result as x == y.

1 Like
9

please clarify what's the expected semantics and behavior. if you want to lookup a HashMap with a key that is different from the actual Key type stored in the hash table, the lookup key must have "obvious" relation with the stored key, most often you see String is stored, but you can lookup with a &str, and this relationship is expressed in the form of the Borrow bound of the lookup methods (e.g. HashMap::get_mut() and others)

in your example, I don't see an "obvious" correspondence between the stored key and the lookup key types. depending on what the intended behavior should be, you might implement Borrow differently.

if you find yourself cannot implement Borrow in a sensible way, your key type probably is ill formed.

10

pop needs an explicit static lifetime here. The compiler does not infer function parameter types from the function body.

    fn pop(&self, ty: &Type<'static>) {
11

In my case the lookup type is actually (a reference to) the same type as what is stored in the HashMap -- that seems like a pretty obvious relation to me. The problem seems to me to be that it's impossible to have the Borrow trait abstract over lifetimes. Like, I can't write this:

impl Borrow<ServerName<'_>> for ServerName<'static> {
    fn borrow(&self) -> &ServerName<'_> {
        todo!()
    }
}

because it conflicts with one of the blanket impls:

error[E0119]: conflicting implementations of trait `Borrow<ServerName<'static>>` for type `ServerName<'static>`
  --> src/server_name.rs:82:1
   |
82 | impl Borrow<ServerName<'_>> for ServerName<'static> {
   | ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |
   = note: conflicting implementation in crate `core`:
           - impl<T> Borrow<T> for T
             where T: ?Sized;

This seems conceptually quite silly. If I have a reference to a key, the compiler should not care about how long the data inside the key lives.

12

(Yup, I have that in my actual implemenation.)

13

if your type itself has a lifetime parameter, your type might already be a reference to some other type. the whole point of using Borrow to lookup a HashMap is you need the least information (just enough to calculate the hash value). if you can't implement the Borrow trait, your usage of the HashMap is probably incorrect.

you shall not implement Borrow<ServerName<'a>> for ServerName<'b>>, you should instead borrow the actual data that ServerName wraps.

14

then stop posting code that doesn't represent your real code and pretending it causes your problem. in your previous example, the stored key has a Number variant, how on earth is that "obvious" related to the lookup type which lacks that information?

15

I understand what you're saying, this makes sense. But you may be assuming the compiler somehow knows what the get_mut method is doing. The compiler only looks at the interface of get_mut and doesn't know what it is doing with the data inside the key.

16

There is no Type<'static>: Borrow<Type<'anylifetime>>.

A better trait bound on map/set is Equivalent in equivalent - Rust which indexmap - Rust uses.

  • The Equivalent trait, which offers more flexible equality definitions between borrowed and owned versions of keys.

Rust Playground

2 Likes
17

I guess I'll implement a separate borrowed type, but that definitely seems like a large amount of boilerplate for what I'm trying to do here (simply abstracting over a lifetime). The Equivalent trait as used by indexmap seems like a much better and more powerful solution (thanks to @vague for pointing it out), but for this I'm kinda tied to the std HashMap.

The Key type might be confusingly named since the Type type (in that example) is actually being used as the hash map's K. Anyway, it seems reasonable to me that a key type might contain some string-like value and also some number-like value. Honestly, the whole setup with the Borrow trait seems quite limiting, although it fits the String/str case well it doesn't seem to generalize well to other scenarios that seems conceptually reasonable.

18

It's true that the Borrow trait is limiting. But abstracting over lifetimes is rarely simple. For example the lifetime-ignoring implementation for Equivalent conflicts just as much as one for Borrow would.[1]

Anyway, here's a walkthrough of one way to work around Borrow's limitations. Short on boilerplate, it is not.

  1. Equivalent's blanket implementation happens to rely on Borrow, so this isn't surprising. But the same would be true for any reflective blanket implementation. ↩ī¸Ž

2 Likes