HashMap 持有 Vec 缓冲区和切片到缓冲区

HashMap holding Vec buffer and slice to buffer

我正在尝试将对文本文件(用 nom 解析)的解析操作结果存储到 HashMap 中。结果由 Vec 缓冲区和该缓冲区上的一些切片组成。目标是将它们一起存储在元组或结构中作为散列映射中的值(使用 String 键)。但我无法解决生命周期问题。

上下文

解析本身采用 &[u8] 和 returns 一些数据结构,其中包含相同输入的切片,例如:

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

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

现在,因为解析是在没有存储的切片上进行的,所以我需要先将输入文本存储在 Vec 中,以便输出切片保持有效,例如:

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

那么我最好将这个 Entry 存储到一个 HashMap 中。这是麻烦出现了。我尝试了两种不同的方法:

尝试 A:存储然后解析

先用输入创建HashMap条目,直接解析引用HashMap条目,然后更新它。

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);
}

这不起作用,因为借用检查器抱怨 &entry.input_data[..] 借用与 entry 相同的生命周期,因此不能移动到 map,因为存在活动借用。

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

尝试 B:解析然后存储

首先解析,然后尝试将 Vec 缓冲区和其中的数据切片一起存储到 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);
}

这不起作用,因为借用检查器抱怨 cmds&buffer[..] 具有相同的生命周期,但 buffer 将在函数结束时被删除。它忽略了 cmdsbuffer 具有相同生命周期的事实,并且都(我希望)移入 entry,后者本身移入 map,因此应该在这里不是终身问题。

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`

最小(非)工作示例

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!");
}

编辑:尝试使用 2 张地图

正如 Kevin 指出的那样,这是第一次让我失望的原因(以上尝试),借用检查器不明白移动 Vec 不会使切片无效,因为堆缓冲区Vec 未被触及。很公平。

旁注:我忽略了 Kevin 的回答中与使用索引相关的部分(Rust 文档 explicitly states slices are a better replacement for indices,所以我觉得这不利于语言)和外部索引的使用板条箱(它们也明确反对该语言)。我正在努力学习和理解如何以“Rust 方式”做到这一点,而不是不惜一切代价。

所以我的直接反应是改变数据结构:首先将存储 Vec 插入第一个 HashMap,一旦它在那里调用 parse() 函数来创建切片直接指向 HashMap 值。然后将它们存储到第二个 HashMap 中,这会自然地将两者分离。但是,一旦我将所有这些放入循环中,这也不起作用,这是此代码的更广泛目标:

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);
    }
}

这里的问题是,一旦输入缓冲区位于第一个映射 input_map 中,引用它会将每个新解析结果的生命周期绑定到 HashMap 的条目,因此 &'a mut 引用(添加了 'a 生命周期)。如果没有这个,编译器会抱怨数据从 input_map 流入 cmds_map 具有不相关的生命周期,这很公平。但是有了这个,&'a mutinput_map 的引用在第一次循环迭代中被锁定并且永远不会释放,并且借用检查器在第二次迭代中阻塞,这是理所当然的。

所以我又卡住了。我想做的事情在 Rust 中是完全不合理和不可能的吗?我怎样才能解决问题(算法、数据结构)以使事情在整个生命周期内正常工作?我真的不明白这里存储缓冲区集合和这些缓冲区上的切片的“Rust 方式”是什么。唯一的解决方案(我想避免)首先加载所有文件,然后解析它们吗?这在我的情况下 非常 不切实际,因为大多数文件都包含对其他文件的引用,我想加载最小的依赖链(可能 < 10 个文件),而不是整个集合(这是大约 3000 多个文件),我只能通过解析每个文件来访问依赖项。

问题的核心似乎是将输入缓冲区存储到任何类型的数据结构中都需要在插入操作期间对所述数据结构进行可变引用,这与长期不可变引用不兼容到每个单独的缓冲区(对于切片),因为这些引用需要具有与 HashMap 定义相同的生命周期。是否有任何其他数据结构(可能是不可变的)可以解决这个问题?还是我完全走错了路?

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>>
}

你在这里尝试的是“self-referential结构”,其中parsed_result指的是input_data。这不能像写的那样工作有一个偶然的和一个根本的原因。

附带的原因是此结构声明包含生命周期 参数 'a,但实际上您试图提供的生命周期 parsed_result 是结构本身的生命周期,并且没有 Rust 语法来指定该生命周期。

根本原因是 Rust 允许结构(和其他值)移动到内存中的其他位置,而引用只是静态检查的指针。所以,当你写

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

您导致 entry 的值从堆栈帧移动 到 HashMap 的存储。该移动使对 entry 的任何引用无效,无论 entry 是否包含这些引用本身。这就是错误“无法移出 entry 因为它是借来的”的意思;借用检查器不允许移动发生。

在你的尝试 B 中,

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

问题是您正在移动 buffer(进入 Entry)而 cmds 借用它。同样,这意味着对 buffer 的引用(只是花哨的指针!)将变得无效,因此不允许。

(现在,由于 Vec 将其实际数据存储在 heap-allocated 向量中,当 Vec 移动时该向量将保持不变,这实际上可能是安全的,但是 Rust 借用检查员不关心那个。)

解决方案

最简单的解决方案(从语言的角度来看)是让每个 Cmd 将索引存储到 input_data 而不是引用。当对象移动时,索引不会变得无效,因为它们是相对的。这样做的缺点当然是每次都必须对输入数据进行切片——代码必须携带 Entry 以及 Cmd.

但是,有 工具可用于制作 self-referential 结构,甚至不需要编写任何不安全的代码。板条箱 ouroboros and rental 都允许您定义 self-referential 结构,代价是必须使用特殊函数来访问结构字段。

例如,您的代码可能看起来像这样使用 ouroboros(我还没有测试过):

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(和rental)为访问字段提供了一个相当奇怪的接口。如果像我一样,您不想将该接口暴露给您的用户(或您的其余代码),您可以围绕 self-referential 结构编写一个包装器结构,其 impl 包含设计用于您希望如何使用该结构,因此所有奇数字段访问方法都可以保持私有。