保存可变引用,以备日后使用别名

Question

我正在尝试实现像拉链这样的东西,但是利用可变引用来避免在我移动时不得不解构和重构数据结构.我有一个链接列表尝试的示例代码,尽管我最好将其应用于其他结构,如树.

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前focus超出范围,我们将永远无法"看到"易变走样.这似乎类似于正常的可变借用:在借用超出范围之前,您不能使用借来的变量.

有没有办法向借阅检查员解释这个？如果你想向借用检查器"解释"从数组中借用两个非重叠切片是可以的,你可以使用split_at:是否有一些相应的函数将强制执行,trail在focus超出范围之前从未使用过,并且这样做,满足借阅检查员？

Answer 1

为了实现您的目标，我们需要摆脱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是一种特殊类型，旨在告诉编译器“假装我正在存储/拥有 a T，即使我没有”。如果没有此字段，编译器会抱怨生命周期参数'a未使用。

请注意，Zipper::new仍然需要 a&'a mut List<T>作为参数：这允许Zipper通过要求调用者具有对 的唯一可变引用来提供安全接口List<T>，我们可以使用这一事实来声明结构中的其他不安全操作确实是安全的，因为我们有充分了解可用的可变引用。就编译器而言， a可变地Zipper 借用了List; 如果你尝试在is 范围内改变Listwhile a ，你会得到一个错误，指出 the已经被可变地借用了。ZipperListList

您还没有显示任何可以让用户获得对 的Zipper焦点的引用的代码。我一直在考虑一种可能不安全的实现，并且很想走这条路，但编译器不会告诉你这是错误的。我来给你展示：

impl<'a, T: 'a> Zipper<'a, T> {
    pub fn focus(&mut self) -> &'a mut List<T> {
        unsafe { &mut *self.focus }
    }
}

返回 a 是很诱人的，&'a mut List<T>因为这就是我们得到的。然而，这是错误的，因为返回值的生命周期没有以任何方式绑定self，这意味着我们可以调用focus两次来获取对同一个List<T>. 如果我们仍然有&'a mut List<T>in Zipper，编译器会告诉我们是否尝试返回 a &'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>超出范围为止。