Lifetime error when inserting a value into a HashMap

[guillegalor]

Hello!

First of all, sorry about my English. I've reach to a compilation problem when trying to add a value to a HashMap using a &str parameter as the key. This is a simplification of my real code to show the problem.

pub fn calculate_paths_to_earth(
    planet: &str,
    known_paths: &mut HashMap<&str, usize>,
    roads: HashMap<&str, HashSet<&str>>,
) {
    // Already known
    if known_paths.contains_key(planet) {
        return;
    }
    let mut num_paths = 0;
    let planets_to_go = roads
        .get(planet)
        .expect("Desde un planeta no se puede ir a ningun planeta");

    if planets_to_go.contains("New Earth") {
        num_paths += 1;
    }

    known_paths.insert(planet, num_paths);
}

With that, the compilation error cargo returns it's:

:! cargo build                                                                                                                                                                                             
   Compiling Ej2-Galactica v0.1.0 (/home/guille/Documentos/TuentiChallenge2019/Ej2-Galactica)
error[E0623]: lifetime mismatch
  --> src/main.rs:27:24
   |
10 |     planet: &str,
   |             ---- these two types are declared with different lifetimes...
11 |     known_paths: &mut HashMap<&str, usize>,
   |                               ----
...
27 |     known_paths.insert(planet, num_paths);
   |                        ^^^^^^ ...but data from `planet` flows into `known_paths` here

error: aborting due to previous error

I've done some research about lifetimes but I still don't know how to solve this. Any idea of what I'm missing? Thank you all in advance!

[droundy]

You can't use &str as the key to a HashMap because there is no way for the map to know that the key will still exist when it goes to look it up later. You have two options: you could either let the map own the keys by making them of type String or you could limit your code to compile time strings and make them & static str. Actually in the latter case you could use runtime strings if you leak the strings by promising that you'll never free them. One way to achieve this would be via string interning via internment.

[leudz]

You can solve it by adding some lifetimes, like this.

[RustyYato]

You could just use a single lifetime for both &str, no need to over complicate it.

[kornel]

In your case you only need to declare that the temporary substrings are all borrowed from the same source, by giving them the same lifetime annotation:

pub fn calculate_paths_to_earth<'a>(
    planet: &'a str,
    known_paths: &mut HashMap<&'a str, usize>,
    roads: HashMap<&str, HashSet<&str>>,
) 

In larger code you may still run into problems with lifetimes, e.g. if you try to create a new name and insert it. In that case:

• consider using owned strings (String) instead of temporary borrowed substrings (&str).

• If one string may be shared in multiple hashmaps/sets, and cloning becomes a performance problem, use a shared type: Arc<str>.

• if the string is shared in hundreds of places, consider string interning.

[Yandros]

Although valid solutions to the OP have been suggested, I think this is a good opportunity to talk about lifetime elision in functions, in order to allow people to solve similar issues:

Click here for an explanation in Spanish

@guillegalor

pub fn calculate_paths_to_earth (
    planet: &str,
    known_paths: &mut HashMap<&str, usize>,
    roads: HashMap<&str, HashSet<&str>>,
)

Aquí tienes muchas lifetimes implícitas y por tanto elididas. Las lifetimes se pueden elidir explícitamente con '_ (funcionalidad de la edición 2018):

pub fn calculate_paths_to_earth (
    planet: &'_ str,
    known_paths: &'_ mut HashMap<&'_ str, usize>,
    roads: HashMap<&'_ str, HashSet<&'_ str>>,
) -> ()

(esencialmente se esconde una lifetime detrás de cada símbolo &, y de vez en cuando en algunas estructuras. Este último caso es bastante traicionero, ya que es más difícil de ver: para ello recomiendo activar el lint #![deny(elided_lifetimes_in_paths)])

¿Qué hace Rust cuando hay lifetimes elididas?

• c.f., la documentación oficial:

@Traducción de https://doc.rust-lang.org/reference/lifetime-elision.html#lifetime-elision-in-functions

1. Parámetros:
   Se aplica un parámetro de lifetime distinto por cada lifetime elidida en los argumentos de una función.

2. Valor de retorno:
   Cuando aparece exactamente una única lifetime en todos los argumentos de una función (potencialmente elidida), esta lifetime es la que se aplica a la(s) lifetime(s) elidida(s) del valor de retorno.

   • En el caso de una función cuyo primer argumento es &self ó &mut self, entonces la lifetime de este borrow de Self es la que se aplica a la(s) lifetime(s) elidida(s) del valor de retorno.

Como tu ejemplo no elide ninguna lifetime en el valor de retorno (), sólo se aplica la primera regla:

pub fn calculate_paths_to_earth<'_1, '_2, '_3, '_4, '_5> (
    planet: &'_1 str,
    known_paths: &'_2 mut HashMap<&'_3 str, usize>,
    roads: HashMap<&'_4 str, HashSet<&'_5 str>>,
) -> ()
where
    // detalle: el préstamo de `known_paths` (duración '_2)
    // no puede durar más que el de la cosa prestada (`HashMap<&'_3 str, usize>`)
    '_3 : '_2, // '_3 >= '_2

Aparte de la restricción entre el segundo y tercer parámetro de lifetime ('_3 : '_2, i.e., '_3 dura al menos tanto como '_2), todos los parámetros son distintos e independientes. Ello los hace incompatibles (no hay bivariancia en Rust que yo sepa).
Ergo el tipo de planet, &'_1 str, es incompatible con el tipo de las claves, &'_3 str.

Solución

Lo que han sugerido los demás: explicitar la igualdad entre la lifetime de planet y la de las claves del HashMap (y ya que estamos, las demás lifetimes de str, ya que se van a usar todas en el mismo contexto. La que no hace falta explicitar es la del préstamo mut de la HashMap):

pub fn calculate_paths_to_earth<'planet> (
    planet: &'planet str,
    known_paths: &'_ mut HashMap<&'planet str, usize>,
    roads: HashMap<&'planet str, HashSet<&'planet str>>,
)

Click here for an explanation in English

@guillegalor

pub fn calculate_paths_to_earth (
    planet: &str,
    known_paths: &mut HashMap<&str, usize>,
    roads: HashMap<&str, HashSet<&str>>,
)

Here you have many implicit and thus elided lifetimes. These lifetimes can be explicitely elided with '_ (edition 2018 feature):

pub fn calculate_paths_to_earth (
    planet: &'_ str,
    known_paths: &'_ mut HashMap<&'_ str, usize>,
    roads: HashMap<&'_ str, HashSet<&'_ str>>,
) -> ()

(long story short, there is a lifetime parameter behind each symbol &, and sometimes in some structures as well. Since the latter are more tricky to spot, I suggest you enable the following lint: #![deny(elided_lifetimes_in_paths)])

What does Rust do with elided lifetimes?

• c.f., the official documentation:

@Slight modification of https://doc.rust-lang.org/reference/lifetime-elision.html#lifetime-elision-in-functions

1. Function parameters:
   Each elided lifetime in the parameters becomes a distinct lifetime parameter.

2. Return type:
   If there is exactly one lifetime used in the parameters (elided or not), that lifetime is assigned to all elided output lifetimes.

   • When the function's first parameter receiver is &self or &mut self, then the lifetime of that reference to Self is assigned to all elided output lifetime parameters.

Since your example has no elided lifetimes in the return type (), only the first rule applies:

pub fn calculate_paths_to_earth<'_1, '_2, '_3, '_4, '_5> (
    planet: &'_1 str,
    known_paths: &'_2 mut HashMap<&'_3 str, usize>,
    roads: HashMap<&'_4 str, HashSet<&'_5 str>>,
) -> ()
where
    // detail: the lifetime of the borrow of `known_paths` ('_2)
    // cannot outlast the borrowee's (`HashMap<&'_3 str, usize>`)
    '_3 : '_2, // '_3 >= '_2

Besides the bound on the second and third lifetime parameters ('_3 : '_2, i.e., '_3 lives at least as long as '_2), all these parameters are distinct and independent of each other. This makes them incompatible with each other (AFAIK, there is no bivariance in Rust).

Therefore, the type of planet, &'_1 str, is not "compatible" with the type of the keys, &'_3 str.

Solution

What the others have suggested: that the equality between planet's lifetime and the keys' be made explicit (and now that we are at it, let's make it equal to the other &str lifetimes, since it seems likely that they will be used in the same context anyways. The one lifetime that does not need to be made explicit is the one in the mut borrow of the HashMap):

pub fn calculate_paths_to_earth<'planet> (
    planet: &'planet str,
    known_paths: &'_ mut HashMap<&'planet str, usize>,
    roads: HashMap<&'planet str, HashSet<&'planet str>>,
)