我正在尝试实现类似拉链的东西,但利用可变引用来避免在浏览数据结构时必须解构和重建数据结构。我有尝试使用链表的示例代码,尽管我理想地希望将其应用于其他结构,例如树。
pub enum List<T> {
Empty,
Cons { head: T, tail: Box<List<T>> },
}
pub struct Zipper<'a, T: 'a> {
trail: Option<Box<Zipper<'a, T>>>,
focus: &'a mut List<T>,
}
impl<'a, T: 'a> Zipper<'a, T> {
pub fn down(&'a mut self) {
match self.focus {
&mut List::Empty => (),
&mut List::Cons {
tail: ref mut xs, ..
} => {
//We need a way to convince rust that we won't use oldZipper
//until xs goes out of scope
let oldZipper = std::mem::replace(
self,
Zipper {
trail: None,
focus: xs,
},
);
self.trail = Some(Box::new(oldZipper));
}
}
}
}
借阅检查员对此不满意:
error[E0499]: cannot borrow `*self` as mutable more than once at a time
--> src/main.rs:21:21
|
16 | tail: ref mut xs, ..
| ---------- first mutable borrow occurs here
...
21 | self,
| ^^^^ second mutable borrow occurs here
...
30 | }
| - first borrow ends here
这并不奇怪:如果我们有一个专注于列表的拉链并对其调用
down
,我们会得到带有对该列表尾部的可变引用的拉链,因此我们有可变的别名。
但是,如果我们在
trail
超出范围之前从未使用过 Zipper 的 focus
,我们将永远无法“看到”可变别名。这似乎类似于普通的可变借用:在借用超出范围之前,您不能使用借用的变量。
有什么办法可以向借阅检查员解释这一点吗?如果你想向借用检查器“解释”从数组中借用两个不重叠的切片是可以的,你可以使用
split_at
:是否有一些相应的函数可以强制 trail
之前从未使用过 focus
超出范围,这样做可以满足借用检查器的要求吗?
为了实现您的目标,我们需要摆脱
Zipper
结构中的可变引用。我们可以使用可变的原始指针来代替:它们让我们改变它们的所指对象,并且我们可以有多个这样的指针指向特定对象,但取消引用它们是不安全的。
这是代码:
use std::mem;
use std::marker::PhantomData;
pub enum List<T> {
Empty,
Cons { head: T, tail: Box<List<T>> },
}
pub struct Zipper<'a, T: 'a> {
trail: Option<Box<Zipper<'a, T>>>,
focus: *mut List<T>,
_list: PhantomData<&'a mut List<T>>,
}
impl<'a, T: 'a> Zipper<'a, T> {
pub fn new(list: &'a mut List<T>) -> Zipper<'a, T> {
Zipper {
trail: None,
focus: list as *mut List<T>,
_list: PhantomData,
}
}
pub fn down(&mut self) {
unsafe {
match *self.focus {
List::Empty => (),
List::Cons {
tail: ref mut xs, ..
} => {
let old_zipper = mem::replace(
self,
Zipper::new(xs),
);
self.trail = Some(Box::new(old_zipper));
}
}
}
}
}
fn main() {
let mut list = List::Cons { head: 1, tail: Box::new(List::Empty) };
let mut zipper = Zipper::new(&mut list);
zipper.down();
zipper.down();
}
focus
结构中的Zipper
字段现在是*mut List<T>
。因为这是一个原始指针,所以我们可以自由地复制它。这解决了您在 Zipper::down
中遇到的编译器错误。还有一个新字段 _list
,类型为 PhantomData<&'a mut List<T>>
。 PhantomData
是一种特殊类型,旨在告诉编译器“假装我正在存储/拥有 T
,即使我没有”。如果没有这个字段,编译器会抱怨生命周期参数 'a
未使用。
请注意,
Zipper::new
仍然需要 &'a mut List<T>
作为参数:这允许 Zipper
通过要求调用者拥有对 List<T>
的唯一可变引用来提供安全接口,我们可以使用这一事实来声明结构中的其他不安全操作确实是安全的,因为我们完全了解可用的可变引用。就编译器而言, Zipper
is 可变地借用 List
;如果您尝试在 List
上的 Zipper
在范围内时改变 List
,您将收到一条错误消息,表明 List
已被可变借用。
您尚未显示任何可以让用户获得对
Zipper
焦点的引用的代码。我一直在考虑一种可能不安全的实现,并且很想走这条路,但编译器不会告诉你这是错误的。让我告诉你:
impl<'a, T: 'a> Zipper<'a, T> {
pub fn focus(&mut self) -> &'a mut List<T> {
unsafe { &mut *self.focus }
}
}
返回
&'a mut List<T>
很诱人,因为这就是我们得到的。然而,这是错误的,因为返回值的生命周期没有以任何方式绑定到 self
,这意味着我们可以调用 focus
两次来获取对同一个 List<T>
的两个可变引用。如果 &'a mut List<T>
中仍然有 Zipper
,编译器会告诉我们是否尝试返回 &'a mut List<T>
(除非我们使用 unsafe
代码来解决它)。正确的实现是:
impl<'a, T: 'a> Zipper<'a, T> {
pub fn focus(&mut self) -> &mut List<T> {
unsafe { &mut *self.focus }
}
}
在此实现中,只要返回的
Zipper
存在,&mut List<T>
就会可变地借用,这意味着我们无法调用 focus
(或 down
),直到 &mut List<T>
超出范围。