在迭代递归结构时无法获取可变引用：同一时间无法作为可变借用多次。

Question

在迭代递归结构时无法获取可变引用：同一时间无法作为可变借用多次。

27

我试图迭代地导航递归数据结构，以便在特定位置插入元素。据我所知，这意味着获取对该结构根部的可变引用，并将其逐步替换为对其后继者的引用:

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(ref mut node) = *anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

（Rust playground 链接）

然而，这个失败了：

error[E0499]: cannot borrow `anchor.0` as mutable more than once at a time
  --> src/main.rs:14:24
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ^^^^^^^^^^^^
   |                        |
   |                        second mutable borrow occurs here
   |                        first mutable borrow occurs here
...
18 |     }
   |     - first borrow ends here

error[E0506]: cannot assign to `anchor` because it is borrowed
  --> src/main.rs:15:13
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ borrow of `anchor` occurs here
15 |             anchor = &mut node.next;
   |             ^^^^^^^^^^^^^^^^^^^^^^^ assignment to borrowed `anchor` occurs here

error[E0499]: cannot borrow `*anchor` as mutable more than once at a time
  --> src/main.rs:17:9
   |
14 |         while let Some(ref mut node) = *anchor {
   |                        ------------ first mutable borrow occurs here
...
17 |         anchor
   |         ^^^^^^ second mutable borrow occurs here
18 |     }
   |     - first borrow ends here

这是有道理的，因为anchor和node都指向相同的结构，但在解构后，我实际上不再关心anchor。

如何使用安全的Rust正确实现back()？

- Fabian Knorr

4个回答

13

启用非词法生命周期（non-lexical lifetimes）后，原始代码可以正常工作：

type Link = Option<Box<Node>>;

struct Node {
    next: Link,
}

struct Recursive {
    root: Link,
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(node) = anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

非词法生命周期提高了编译器借用检查器的精度，使其能够看到anchor的可变借用不再使用。由于最近语言的更改，我们还可以简化if let中的关键字。

- Shepmaster

7

你可以使用递归来满足借用检查器。这种方法的缺点是对于列表中的每个项目都会创建一个堆栈帧。如果你的列表很长，这肯定会导致堆栈溢出。LLVM会将Node::back方法优化为一个循环（请参见在playground上生成的LLVM IR）。

impl Node {
    fn back(&mut self) -> &mut Link {
        match self.next {
            Some(ref mut node) => node.back(),
            None => &mut self.next,
        }
    }
}

impl Recursive {
    fn back(&mut self) -> Option<&mut Link> {
        self.root.as_mut().map(|node| node.back())
    }
}

- oli_obk

2

它可以正常工作：

fn back(&mut self) -> &mut Link {
    let mut anchor = &mut self.root;
    while anchor.is_some(){
        anchor = &mut {anchor}.as_mut().unwrap().next;
    }
    anchor
}

- aSpex

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Matthieu M. · Accepted Answer

虽然我希望能有更加优雅的解决方案，但实际上这是可能实现的。

关键在于不要从anchor中借用，因此需要在两个累加器之间进行切换：

一个保存对当前节点的引用
另一个被赋予下一个节点的引用

这让我想到：

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

虽然不太好看，但这是借用检查器可以支持的东西，所以¯\_(ツ)_/¯。

@ker通过创建一个未命名的临时变量进行了改进：

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

这里的技巧在于使用{anchor}将anchor的内容移动到一个未命名的临时变量中，该匹配会在其上执行。因此，在match块中，我们不是从anchor中借用，而是从临时变量中借用，使我们可以自由修改anchor。请参见相关博客文章 Stuff the Identity Function Does (in Rust)。