HashMap holding Vec buffer and slice to buffer

Question

I am trying to store into a HashMap the result of a parsing operation on a text file (parsed with nom). The result is comprised of a Vec buffer and some slices over that buffer. The goal is to store those together in a tuple or struct as a value in the hash map (with String key). But I can't work around the lifetime issues.

Context

The parsing itself takes an &[u8] and returns some data structure containing slices over that same input, e.g.:

struct Cmd<'a> {
  pub name: &'a str
}

fn parse<'a>(input: &'a [u8]) -> Vec<Cmd<'a>> {
  [...]
}

Now, because the parsing operates on slices without storage, I need to first store the input text in a Vec so that the output slices remain valid, so something like:

struct Entry<'a> {
  pub input_data: Vec<u8>,
  pub parsed_result: Vec<Cmd<'a>>
}

Then I would ideally store this Entry into a HashMap. This is were troubles arise. I tried two different approaches:

Attempt A: Store then parse

Create the HashMap entry first with the input, parse referencing the HashMap entry directly, and then update it.

pub fn store_and_parse(filename: &str, map: &mut HashMap<String, Entry>) {
  let buffer: Vec<u8> = load_from_file(filename);
  let mut entry = Entry{ input_data: buffer, parsed_result: vec![] };
  let cmds = parse(&entry.input_data[..]);
  entry.parsed_result = cmds;
  map.insert(filename.to_string(), entry);
}

This doesn't work because the borrow checker complains that &entry.input_data[..] borrows with the same lifetime as entry, and therefore cannot be moved into map as there's an active borrow.

error[E0597]: `entry.input_data` does not live long enough
  --> src\main.rs:26:23
   |
23 | pub fn store_and_parse(filename: &str, map: &mut HashMap<String, Entry>) {
   |                                        --- has type `&mut std::collections::HashMap<std::string::String, Entry<'1>>`
...
26 |     let cmds = parse(&entry.input_data[..]);
   |                       ^^^^^^^^^^^^^^^^ borrowed value does not live long enough
27 |     entry.parsed_result = cmds;
28 |     map.insert(filename.to_string(), entry);
   |     --------------------------------------- argument requires that `entry.input_data` is borrowed for `'1`
29 | }
   | - `entry.input_data` dropped here while still borrowed

error[E0505]: cannot move out of `entry` because it is borrowed
  --> src\main.rs:28:38
   |
26 |     let cmds = parse(&entry.input_data[..]);
   |                       ---------------- borrow of `entry.input_data` occurs here
27 |     entry.parsed_result = cmds;
28 |     map.insert(filename.to_string(), entry);
   |         ------                       ^^^^^ move out of `entry` occurs here
   |         |
   |         borrow later used by call

Attempt B: Parse then store

Parse first, then try to store both the Vec buffer and the data slices into it all together into the HashMap.

pub fn parse_and_store(filename: &str, map: &mut HashMap<String, Entry>) {
  let buffer: Vec<u8> = load_from_file(filename);
  let cmds = parse(&buffer[..]);
  let entry = Entry{ input_data: buffer, parsed_result: cmds };
  map.insert(filename.to_string(), entry);
}

This doesn't work because the borrow checker complains that cmds has same lifetime as &buffer[..] but buffer will be dropped by the end of the function. It ignores the fact that cmds and buffer have the same lifetime, and are both (I wish) moved into entry, which is itself moved into map, so there should be no lifetime issue here.

error[E0597]: `buffer` does not live long enough
  --> src\main.rs:33:21
   |
31 | pub fn parse_and_store(filename: &str, map: &mut HashMap<String, Entry>) {
   |                                        --- has type `&mut std::collections::HashMap<std::string::String, Entry<'1>>`
32 |   let buffer: Vec<u8> = load_from_file(filename);
33 |   let cmds = parse(&buffer[..]);
   |                     ^^^^^^ borrowed value does not live long enough
34 |   let entry = Entry{ input_data: buffer, parsed_result: cmds };
35 |   map.insert(filename.to_string(), entry);
   |   --------------------------------------- argument requires that `buffer` is borrowed for `'1`
36 | }
   | - `buffer` dropped here while still borrowed

error[E0505]: cannot move out of `buffer` because it is borrowed
  --> src\main.rs:34:34
   |
31 | pub fn parse_and_store(filename: &str, map: &mut HashMap<String, Entry>) {
   |                                        --- has type `&mut std::collections::HashMap<std::string::String, Entry<'1>>`
32 |   let buffer: Vec<u8> = load_from_file(filename);
33 |   let cmds = parse(&buffer[..]);
   |                     ------ borrow of `buffer` occurs here
34 |   let entry = Entry{ input_data: buffer, parsed_result: cmds };
   |                                  ^^^^^^ move out of `buffer` occurs here
35 |   map.insert(filename.to_string(), entry);
   |   --------------------------------------- argument requires that `buffer` is borrowed for `'1`

Minimal (non-)working example

use std::collections::HashMap;

#[derive(Debug, PartialEq)]
struct Cmd<'a> {
    name: &'a str
}

fn parse<'a>(input: &'a [u8]) -> Vec<Cmd<'a>> {
    Vec::new()
}

fn load_from_file(filename: &str) -> Vec<u8> {
    Vec::new()
}

#[derive(Debug, PartialEq)]
struct Entry<'a> {
    pub input_data: Vec<u8>,
    pub parsed_result: Vec<Cmd<'a>>
}

// pub fn store_and_parse(filename: &str, map: &mut HashMap<String, Entry>) {
//     let buffer: Vec<u8> = load_from_file(filename);
//     let mut entry = Entry{ input_data: buffer, parsed_result: vec![] };
//     let cmds = parse(&entry.input_data[..]);
//     entry.parsed_result = cmds;
//     map.insert(filename.to_string(), entry);
// }

pub fn parse_and_store(filename: &str, map: &mut HashMap<String, Entry>) {
  let buffer: Vec<u8> = load_from_file(filename);
  let cmds = parse(&buffer[..]);
  let entry = Entry{ input_data: buffer, parsed_result: cmds };
  map.insert(filename.to_string(), entry);
}

fn main() {
    println!("Hello, world!");
}

Edit: Attempt with 2 maps

As Kevin pointed, and this is what threw me off the first time (above attempts), the borrow checker doesn't understand that moving a Vec doesn't invalidate the slices because the heap buffer of the Vec is not touched. Fair enough.

Side note: I am ignoring the parts of Kevin's answer related to using indexes (the Rust documentation explicitly states slices are a better replacement for indices, so I feel this is working against the language) and the use of external crates (which also are explicitly working against the language). I am trying to learn and understand how to do this "the Rust way", not at all costs.

So my immediate reaction to that was to change the data structure: first insert the storage Vec into a first HashMap, and once it's there call the parse() function to create the slices directly pointing into the HashMap value. Then store those into a second HashMap, which would naturally dissociate the two. However that also doesn't work as soon as I put all of that in a loop, which is the broader goal of this code:

fn two_maps<'a>(
    filename: &str,
    input_map: &'a mut HashMap<String, Vec<u8>>,
    cmds_map: &mut HashMap<String, Vec<Cmd<'a>>>,
    queue: &mut Vec<String>) {
    {
        let buffer: Vec<u8> = load_from_file(filename);
        input_map.insert(filename.to_string(), buffer);
    }
    {
        let buffer = input_map.get(filename).unwrap();
        let cmds = parse(&buffer[..]);
        for cmd in &cmds {
            // [...] Find further dependencies to load and parse
            queue.push("...".to_string());
        }
        cmds_map.insert(filename.to_string(), cmds);
    }
}

fn main() {
    let mut input_map = HashMap::new();
    let mut cmds_map = HashMap::new();
    let mut queue = Vec::new();
    queue.push("file1.txt".to_string());
    while let Some(path) = queue.pop() {
        println!("Loading file: {}", path);
        two_maps(&path[..], &mut input_map, &mut cmds_map, &mut queue);
    }
}

The problem here is that once the input buffer is in the first map input_map, referencing it binds the lifetime of each new parsed result to the entry of that HashMap, and therefore the &'a mut reference (the 'a lifetime added). Without this, the compiler complains that data flows from input_map into cmds_map with unrelated lifetimes, which is fair enough. But with this, the &'a mut reference to input_map becomes locked on the first loop iteration and never released, and the borrow checker chokes on the second iteration, quite rightfully so.

So I am stuck again. Is what I am trying to do completely unreasonable and impossible in Rust? How can I approach the problem (algorithms, data structures) to make things work lifetime-wise? I really don't see what's the "Rust way" here to store a collection of buffers and slices over those buffers. Is the only solution (that I want to avoid) to first load all files, and then parse them? This is very impractical in my case because most files contain references to other files, and I want to load the minimum chain of dependencies (likely < 10 files), not the entire collection (which is something like 3000+ files), and I can only access dependencies by parsing each file.

It seems the core of the issue is that storing the input buffers into any kind of data structure requires a mutable reference to said data structure for the duration of the insert operation, which is incompatible with having long-lived immutable references to each single buffer (for the slices) because those references need to have the same lifetime as per the HashMap definition. Is there any other data structure (maybe immutable ones) that lifts this? Or am I completely on the wrong track?

Answer 1

Now, because the parsing operates on slices without storage, I need to first store the input text in a Vec so that the output slices remain valid, so something like:

struct Entry<'a> {
  pub input_data: Vec<u8>,
  pub parsed_result: Vec<Cmd<'a>>
}

What you are attempting here is a “self-referential structure”, where parsed_result refers to input_data. There is an incidental and a fundamental reason why this cannot work as written.

The incidental reason is that this struct declaration contains the lifetime parameter 'a, but actually the lifetime you're attempting to give parsed_result is the lifetime of the struct itself, and there is no Rust syntax to specify that lifetime.

The fundamental reason is that Rust allows structs (and other values) to be moved to other locations in memory, and references are just statically checked pointers. So, when you write

map.insert(filename.to_string(), entry);

you're causing the value of entry to be moved from the stack frame to the HashMap's storage. That move invalidates any references into entry, whether or not entry contains those references itself. That's what the error "cannot move out of entry because it is borrowed" means; the borrow checker is not allowing the move to happen.

In your Attempt B,

  let buffer: Vec<u8> = load_from_file(filename);
  let cmds = parse(&buffer[..]);
  let entry = Entry{ input_data: buffer, parsed_result: cmds };

the problem is that you're moving buffer (into the Entry) while cmds borrows it. Again, that means the references (just fancy pointers!) into buffer would become invalid, so it's not allowed.

(Now, since Vec stores its actual data in a heap-allocated vector that will stay put while the Vec is moved, this might actually be safe, but the Rust borrow checker doesn't care about that.)

Solutions

The simplest solution (from a language perspective) is to have each Cmd store indices into input_data instead of references. Indices don't become invalid when the object is moved since they're relative. The disadvantage of this is of course that you have to slice the input data every time — code has to carry around the Entry as well as the Cmd.

However, there are tools available to make self-referential structures, without even needing to write any unsafe code. The crates ouroboros and rental both allow you to define self-referential structs, at the price of having to use special functions to access the struct fields.

For example, your code might look something like this using ouroboros (I haven't tested this):

use ouroboros::self_referencing;

#[self_referencing]
struct Entry {
    input_data: Vec<u8>,
    #[borrows(input_data)]
    parsed_result: Vec<Cmd<'this>> // 'this is a special lifetime name provided by ouroboros
}

fn parse_and_store(filename: &str, map: &mut HashMap<String, Entry>) {
    let entry = EntryBuilder {  // EntryBuilder is defined by ouroboros to help construct Entry
        input_data: load_from_file(filename),
        // Note that instead of giving a value for parsed_result, we give
        // a function to compute it.
        parsed_result_builder: |input_data: &[u8]| parse(input_data),
    }.build();
    map.insert(filename.to_string(), entry);
}

fn do_something_with_entry(entry: &Entry) {
    entry.with_parsed_result(|cmds| {
        // cmds is a reference to `self.parsed_result` which only lives as
        // long as this lambda and therefore can't be invalidated by a move.
    });
}

ouroboros (and rental) provide a fairly odd interface for accessing fields. If, like me, you don't want to expose that interface to your users (or the rest of your code), you can write a wrapper struct around the self-referential struct whose impl contains methods designed for how you want the structure to be used, so all of the odd field access methods can remain private.