Rust Lifetimes in Higher Order Functions

Question

I have a map: HashMap<&str, Vec<&str>> and I'm trying to create a reverse lookup map HashMap<&str, &str> which refers from each of the element in the original vector to the original key.

E.g. map like below

{
  "k": vec!["a", "b"]
}

would be transformed into

{
  "a": "k",
  "b": "k",
}

It works perfectly fine when I do that with:

    let substitutes: HashMap<&str, Vec<&str>> = vec![("a", vec!["b", "c"])].into_iter().collect();
    
    // Below works fine
    let mut reversed: HashMap<&str, &str> = HashMap::new();
    for (&k, v) in substitutes.iter() {
        for vv in v.iter() {
            reversed.insert(vv, k);
        }
    }

However it doesn't work if I try to do that with a Higher Order Functions:

    // Below doesn't work
    let reversed_2: HashMap<&str, &str> = substitutes
        .iter()
        .flat_map(|(&k, v)| v.iter().map(|&vv| (vv, k)))
        .collect();

And gives the following errors:

error[E0373]: closure may outlive the current function, but it borrows `k`, which is owned by the current function
  --> src/main.rs:18:42
   |
18 |         .flat_map(|(&k, v)| v.iter().map(|&vv| (vv, k)))
   |                                          ^^^^^      - `k` is borrowed here
   |                                          |
   |                                          may outlive borrowed value `k`
   |
note: closure is returned here
  --> src/main.rs:18:29
   |
18 |         .flat_map(|(&k, v)| v.iter().map(|&vv| (vv, k)))
   |                             ^^^^^^^^^^^^^^^^^^^^^^^^^^^
help: to force the closure to take ownership of `k` (and any other referenced variables), use the `move` keyword
   |
18 |         .flat_map(|(&k, v)| v.iter().map(move |&vv| (vv, k)))
   |                                          ^^^^^^^^^^

error: aborting due to previous error; 1 warning emitted

I am trying to wrap my head around how vv might outlive k given that it's in the same scope under flat_map.

Would be really helpful to get more information why my HOF approach fails.

Playground

user_3404377 · Answer

In this case, the compiler help was exactly right: you need to add move on the inner closure.

let reversed_2: HashMap<&str, &str> = substitutes
    .iter()
    .flat_map(|(&k, v)| v.iter().map(move |&vv| (vv, k)))
    .collect();

Rust Playgroud

When you make an anonymous function that uses variables from the surrounding scope, the inline function (called a closure) needs access to those variables. By default, it takes a reference to them, leaving them available in the enclosing scope. However, in this case, the closure takes a reference to k and returns it, which means that it could escape the enclosing scope.

.flat_map(|(&k, v)| {
    // k is only valid in this anonymous function

    // a reference to k is returned out of map and also out of flat_map
    // (Note: no move)
    v.iter().map(|&vv| (vv, k))

    // the anonymous function ends, all references to k need to have ended
})

// A reference to k has been returned, even though k's lifetime has ended
// Compiler error!

When you switch to a move closure, rather than taking to references to things in the enclosing environment, you take ownership of the things themselves. This lets you return k rather than a reference to k, sidestepping the issue.

.flat_map(|(&k, v)| {
    // k is only valid in this anonymous function

    // k is moved out of the enclosing function and into the inner function
    // Because it owns k, it can return it
    // (Note: uses move)
    v.iter().map(move |&vv| (vv, k))

    // k has been moved out of this environment, so its lifetime does not end here
})

// k has been returned and is still alive

Rust Lifetimes in Higher Order Functions

1 Answers