逻辑上拆分借用以解决启用 NLL 的借用检查器的限制是否安全？

Question

下面的代码涉及一个非常微妙的借用检查器闪避。代码本身描述了推理。问题：

• 这真的安全吗？
• 这是表示执行的不安全操作的推荐方式吗？我应该使用指针吗？
• 新的 Polonius 借用检查器能否推理出这样的模式？

/// Insert a new data element at a given key.
pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
    // Safety: As indicated below, we would like to return val1 directly in the loop,
    // but rust will reject this, claiming a double borrow, and we instead use some
    // unsafe hacks to circumvent the borrow checker. To show this is safe, consider
    // two cases.
    // - If the return is exercised (we found an element and early out):
    //   - let 'b be 'a (the borrow of self),
    //   - and let 'c be empty
    // - Otherwise (we did not find an element, exit the loop and terminate normally):
    //   - let 'b be the duration of the loop,
    //   - and let 'c be from the end of the loop until the end of 'a
    // In either case, 'b and 'c are disjoint, so the "double borrow" is safe.
    // The borrow checker reasons that 'b has to be at least 'a because it is returned,
    // and therefore it overlaps with 'c, but these happen in mutually exclusive
    // situations.
    for (key1, val1) in & /* 'b */ mut *this {
        if key == *key1 {
            // return val1; // we would like to write this
            return unsafe { // safety, see above. We know we are in the first case, so 'b = 'a
                std::mem::transmute::<&/* 'b */ mut V, &/* 'a */ mut V>(val1)
            }
        }
    }
    let this = & /* 'c */ mut *this;
    this.push((key, val));
    &mut this.last_mut().unwrap().1
}

这是我更愿意写的：

/// Insert a new data element at a given key.
pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
    for (key1, val1) in &mut *this {
        if key == *key1 {
            return val1;
        }
    }
    let this = &mut *this;
    this.push((key, val));
    &mut this.last_mut().unwrap().1
}

但它失败了：

error[E0499]: cannot borrow `*this` as mutable more than once at a time
 --> src/lib.rs:8:16
  |
2 | pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
  |               -- lifetime `'a` defined here
3 |     for (key1, val1) in &mut *this {
  |                         ---------- first mutable borrow occurs here
4 |         if key == *key1 {
5 |             return val1;
  |                    ---- returning this value requires that `*this` is borrowed for `'a`
...
8 |     let this = &mut *this;
  |                ^^^^^^^^^^ second mutable borrow occurs here

Answer 1

正如相关问题中所述，最简单的方法是使用索引，因为它不需要不安全的代码。我可能会这样写：

pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
    let idx = this
        .iter()
        .enumerate()
        .find_map(|(i, (k, _))| if key == *k { Some(i) } else { None });

    let idx = idx.unwrap_or_else(|| {
        this.push((key, val));
        this.len() - 1
    });

    &mut this[idx].1
}

您应该执行基准测试来了解这是否由于某种原因不够快。只有在这种情况下，您才应该选择unsafe编码以获得最后一点速度。然后，您应该再次进行基准测试，看看代码是否明显更快。

例如，您可以通过使用slice::get_unchecked_mut而不是 来获得加速&mut this[idx].1，这是一种更容易合理化的不安全代码。

在我们的安全代码中使用索引的好处是它们可以直接转换为指针偏移逻辑。我们可以采用这个安全的示例，并对其进行最小的修改，以获得使用unsafe代码的版本：

pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
    let idx = this
        .iter()
        .enumerate()
        .find_map(|(i, (k, _))| if key == *k { Some(i) } else { None });

    let idx = idx.unwrap_or_else(|| {
        this.push((key, val));
        this.len() - 1
    });

    &mut this[idx].1
}

安全要点围绕指向 中值的指针found。它最初是一个可变引用，所以我们知道它在迭代时是有效的。我们知道find_map在第一个上停止迭代Some，并且我们知道迭代 usingiter_mut()无论如何都不应该改变我们的值。由于this不能在 中更改它的绑定found和使用match，我相信这段代码是安全的。

通过 Miri 练习您的代码总是很有价值的。您必须实际执行代码，因为 Miri 仅标记导致未定义行为的代码，而忽略任何休眠代码路径。这段代码是 Miri 干净的：

fn main() {
    let mut things = vec![(1, 2), (3, 4)];

    let v = insert(&mut things, 1, 2);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 1, 2);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 5, 6);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 5, 6);
    println!("{} ({:p})", v, v);
}

pub fn insert<'a, K: Eq, V>(this: &'a mut Vec<(K, V)>, key: K, val: V) -> &'a mut V {
    // I copied this code from Stack Overflow without reading the surrounding
    // text which explained why this code is or is not safe.
    unsafe {
        let found = this
            .iter_mut()
            .find_map(|(k, v)| if key == *k { Some(v as *mut V) } else { None });

        match found {
            Some(v) => &mut *v,
            None => {
                this.push((key, val));
                &mut this.last_mut().unwrap().1
            }
        }
    }
}

[最初的实现]真的安全吗？

Miri 报告我上面使用的相同测试代码没有任何问题，而且我没有看到任何明显的错误。

这是表达所执行的不安全操作的推荐方式吗？我应该使用指针吗？

当可以避免时mem::transmute，通常应该避免。transmute是大锤子，可以做很多你可能不想要的事情（改变类型是关键之一）。在这种情况下，使用指针感觉更简单。

我同意使用注释来证明为什么不安全的代码是安全的。即使是错误的，也体现了原作者的想法。未来的审阅者可能会说“啊，他们没有考虑清单项目#42，让我测试一下！”。

特别是对于您评论中的推理，它对我来说过于密集/学术。我不明白为什么要谈论多重生命周期或双重借用。

新的 Polonius 借用检查器能够推理出这样的模式吗？

是的：

fn main() {
    let mut things = vec![(1, 2), (3, 4)];

    let v = insert(&mut things, 1, 2);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 1, 2);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 5, 6);
    println!("{} ({:p})", v, v);

    let v = insert(&mut things, 5, 6);
    println!("{} ({:p})", v, v);
}

也可以看看：

• 如何在 Vec 上更新或插入？
• 即使 NLL 打开，循环中的双重可变借用错误也会发生
• 从 HashMap 或 Vec 返回引用会导致借用超出其范围？
• 什么时候有必要规避 Rust 的借用检查器？