我可以证明 Rust Borrow Checker 分配的单调性吗

Question

我有以下代码无法编译：

// TODO: Return Result, remove `.expect`s
fn to_blender_subfile<'a>(
    filepath: &str,
    transform: Transform,
    visited_file_cache: &'a mut HashMap<&'a str, Vec<Command>>,
    blender: &mut Blender,
) {
    // TODO: Support colors and backface culling

    let commands = visited_file_cache.get(filepath).unwrap();
    // "unwrap" is enforced by the wrapper function

    for command in commands.iter() {
        if let Command::Subfile { filepath, .. } = command {
            if !visited_file_cache.contains_key(filepath.as_str()) {
                let mut file = std::fs::File::open(filepath).expect("Failed to open file");

                let mut file_contents = String::new();

                let contents_len = file
                   .read_to_string(&mut file_contents)
                   .expect("Failed to read file into buffer");

                assert_eq!(contents_len, file_contents.len()); // TODO: Check this


                // "parse_file" is defined elsewhere
                let commands = parse_file(&file_contents);

                if let Some(_) = visited_file_cache.insert(filepath.as_str(), commands) {
                    std::unreachable!();
                }
            }
        }
    }

    // ... rest of function
}

我从

rustc

得到的错误是：

cannot borrow `*visited_file_cache` as mutable because it is also borrowed as immutable 

指的是我在声称

visited_file_cache.insert(filepath.as_str(), commands)

时同时做

let commands = visited_file_cache.get(filepath).unwrap();

和

visited_file_cache: &'a mut HashMap<&'a str, Vec<Command>>

。

我对正在发生的事情的理解，至少在高层次上，是借用检查器正在保护我免于变异

visited_file_cache

，同时也引用其键的值，因为一般来说，它的键可能会在其值中幸存下来，这可能会导致到悬空指针。

这一切都很好，但是根据代码的性质，如果键值对已插入到

visited_file_cache

中，则无法将其删除（即它的寿命至少与哈希图本身一样长）。我知道编译器无法使用这些信息，因此它会抱怨，但是有没有办法向编译器表达一个区域单调增长？然后我可以告诉编译器

visited_file_cache

由单调分配器支持，并且其

insert

方法是非破坏性的，从而消除上述错误。

编译器能否理解此类结构，或者标准库中是否存在预定义的结构，可以在使用

unsafe

时强制执行上述行为？

我知道我可以通过复制字符串并使

visited_file_cache

的键拥有所有权来轻松规避此问题，并且我很确定我也可以使用引用计数。但是，我认为这两种解决方案的基础设施对于我的用例来说都不是必需的。

注意我是 Rust 新手（虽然我看过 Rustonomicon，但还没看过 Rust Book），但我有 C 和 Haskell 背景。

Answer 1

首先，如果您只想编译代码，那么实际上您可以相对轻松地通过一些克隆和拥有的密钥来实现：参见操场。

虽然有点无聊，不是吗？

那么，我们需要什么才能在修改地图时迭代并引用地图的键和值？

漏了，漏了，漏了！

（不要误认为“舔它，舔它，舔它！”，没有地质学家在做出这个答案时受到伤害）

在 Rust 中，泄漏是安全的。事实上，有一个明确的函数可以做到这一点。所以我们要泄露所有的东西：

• 按键将是

  &'static str

  。
• 命令将是

  &'static [Command]

  。

泄漏

String

可以通过以下方式实现：

let filename: Box<str> = _string_;
let filename = Box::leak(filename);

泄漏切片可以通过以下方式实现：

let commands: Box<[Command]> = _vec_;
let commands = Box::leak(commands);

就是这样。我们现在可以有一个

HashMap<&'static str, &'static [Command]>

，其中

filepath: &'static str

位于

Command::Subfile

，我们就可以开始了。

调整一下。

泄漏是安全的，所以很酷，但是......它并不适合重复。所以我们需要另一个选择。

地图的另一个选择是保证插入的键和值（1）不会被移动并且（2）不会被改变（共享时）。

Rust 非常酷的一点是，事实上，您可以在类型级别表达此类不变量（共享与非共享），因此我们得到：

impl<K, V> PushMap<K, V> {
    //  Only reads & `insert_if_new` are possible for the duration of the borrow.
    fn get(&self, key: &K) -> Option<&V>;

    //  Returns `value` if the key is already present in the map.
    //
    //  This is unlike `insert` (which returns the previous value), hence the
    //  the different name.
    fn insert_if_new(&self, key: K, value: V) -> Option<(K, V)>;

    //  Mirror API of standard HashMap.
    fn get_mut(&mut self, key: &K) -> Option<&mut V>;
    fn insert(&mut self, key: K, value: V) -> Option<V>;
    fn remove(&mut self, key: &K) -> Option<V>;
}

使用

insert_new

确实需要内部可变性。在底部，这意味着

UnsafeCell

，而

Cell

和

RefCell

包装纸不会在这里切割它，所以我们需要自己制作。

这 also 意味着不可能在多个线程之间共享

&PushMap

（虽然可以使用

&HashMap

），除非我们 also 将其设为并发映射。这是一个权衡。

确切的实现留给读者作为练习。从文献来看，使用链表作为存储桶的典型哈希表实现将符合要求，尽管使用链表会产生开销。否则，也可以在交错数组概念之上实现，请参阅

jagged

存储库了解示例。