rust - 在逻辑上拆分借用以解决启用 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 {
    // 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
            }
        }
    }
}

安全的要点围绕着指向 found 中的值的指针。 .它最初是一个可变引用，因此我们知道它在迭代时是有效的。我们知道 find_map在第一个 Some 上停止迭代，我们知道使用 iter_mut() 进行迭代无论如何都不应该改变我们的值(value)观。由于 this无法在 found 的绑定(bind)之间更改以及它在 match 中的用法，我相信这段代码是安全的。
通过 Miri 练习代码总是很有值(value)的。您必须实际运行代码，因为 Miri 只会标记导致未定义行为的代码，而忽略任何休眠代码路径。此代码是 Miri-clean:

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

2 (0x2829c)
2 (0x2829c)
6 (0x41054)
6 (0x41054)

Is [the original implementation] actually safe?

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

Is this the recommended way to express the unsafe operations performed? Should I use pointers instead?

什么时候可以避免 mem::transmute , 一般应避免。 transmute是大锤子，可以做很多你可能不想要的事情(改变类型是关键)。在这种情况下，使用指针感觉要简单得多。
我同意使用注释来说明为什么不安全的代码是安全的。即便是错的，也能体现出原作者的心态。 future 的审阅者可能会说“啊，他们没有考虑 list 项目＃42，让我测试一下!”。
特别是对于您评论中的推理，它对我来说过于密集/学术。我不明白为什么要谈论多个生命周期或双重借用。

Will the new Polonius borrow checker be able to reason about patterns like this?

是的:

% cargo +nightly rustc --
   Compiling example v0.1.0 (/private/tmp/example)
error[E0499]: cannot borrow `*this` as mutable more than once at a time
 --> src/main.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

% cargo +nightly rustc -- -Zpolonius
   Compiling example v0.1.0 (/private/tmp/example)
    Finished dev [unoptimized + debuginfo] target(s) in 0.86s

% ./target/debug/example
2 (0x7f97ea405b24)
2 (0x7f97ea405b24)
6 (0x7f97ea405ba4)
6 (0x7f97ea405ba4)

也可以看看:

How to update-or-insert on a Vec?

Double mutable borrow error in a loop happens even with NLL on

Returning a reference from a HashMap or Vec causes a borrow to last beyond the scope it's in?

When is it necessary to circumvent Rust's borrow checker?