Rust lang lifetime mismatch for HashMap with str key

Question

I'm trying to implement an existing C++ algorithm, that works, in Rust to understand how lifetimes work.. What is the pattern that we should use for the following... to give a background, this algorithm tries to find the length of the longest palindromic subsequence.

use std::cmp::{max, min};
use std::collections::HashMap;
use std::str;

fn main() {
    let mut m = HashMap::new();
    println!(
        "Longest palin size: {}",
        longest_palin_substring("abdbca".as_bytes(), &mut m)
    );
}
    
    
    pub fn longest_palin_substring(is_palin: &[u8], map: &mut HashMap<&str, usize>) -> usize {
    println!("current string : {}", str::from_utf8(is_palin).unwrap());
    if is_palin.len() == 0 || is_palin.len() == 1 {
        return is_palin.len();
    }

    if let Some(len) = map.get(str::from_utf8(is_palin).unwrap()) {
        *len
    } else {
        let c1 = if is_palin[0] == is_palin[is_palin.len() - 1] {
            let r = longest_palin_substring(&is_palin[1..is_palin.len() - 1], map);
            if r == is_palin.len() - 2 {
                2 + r
            } else {
                0
            }
        } else {
            0
        };

        let c2 = longest_palin_substring(&is_palin[1..], map);
        let c3 = longest_palin_substring(&is_palin[..is_palin.len() - 1], map);

        let c = max(c1, max(c2, c3));
        map.insert(str::from_utf8(is_palin).unwrap(), c);
        c
    }
}

error[E0623]: lifetime mismatch
  --> src/main.rs:38:20
   |
14 |     pub fn longest_palin_substring(is_palin: &[u8], map: &mut HashMap<&str, usize>) -> usize {
   |                                              -----                    ----
   |                                              |
   |                                              these two types are declared with different lifetimes...
...
38 |         map.insert(str::from_utf8(is_palin).unwrap(), c);
   |                    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ ...but data from `is_palin` flows into `map` here

error: aborting due to previous error; 1 warning emitted

For more information about this error, try `rustc --explain E0623`.
error: could not compile `playground`

To learn more, run the command again with --verbose.

I tried adding &'a lifetime to all the references, but then it complains of mutable borrow happening multiple times.

 pub fn longest_palin_substring<'a>(                                                                                                                 
     is_palin: &'a [u8],                                                                                                                             
     map: &'a mut HashMap<&'a str, usize>,                                                                                                           
 ) -> usize {                                                                                                                                        

Error:

error[E0499]: cannot borrow `*map` as mutable more than once at a time

My questions are as follows:

• first, obviously, is how I should proceed to fix this compile error
• what is the pattern to follow for some state that will be used to memoize results in a recursive implementation of, say, dynamic programming.

Any pointers where I can learn more about patterns in rust would be greatly appreciated.

Thanks.

Answer 1

You're close. First, the lifetime of the hashmap is going to be different than the lifetime of its key type.

The compile errors can be fixed as such:

pub fn longest_palin_substring<'a>(is_palin: &'a [u8], map: &mut HashMap<&'a str, usize>) -> usize {

As a general rule, if you aren't storing a reference passed to a function, you don't want any lifetime annotations on the type, the compiler uses the function signature to determine how references are used without inspecting the function's contents.

Second, for memoizing things, I would use some interior mutability primitives. If the algorithm is single threaded then Cell or RefCell will do, if not a Mutex will allow you to mutate internal state.

If things are going to be memoized only once, you may be interested in once_cell (it's still nightly-only, but there is a crate usabe in stable).