Lưu tham chiếu có thể thay đổi cho sau này ngay cả khi được đặt tên

Question

Tôi đang cố gắng triển khai một cái gì đó như dây kéo nhưng lợi dụng các tham chiếu có thể thay đổi để tránh phải cấu trúc lại và cấu trúc lại dữ liệu khi tôi di chuyển nó. Tôi đã có mã ví dụ cho một nỗ lực với một danh sách liên kết, mặc dù tôi lý tưởng muốn áp dụng nó cho các cấu trúc khác, như cây cối.

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

Trình kiểm tra mượn là không hài lòng với điều này:

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 

Đây không phải là đáng ngạc nhiên: nếu chúng ta có một dây kéo tập trung vào một danh sách và gọi down vào nó, chúng tôi nhận dây kéo với một mutable tham chiếu đến đuôi của danh sách đó, vì vậy chúng tôi có bí danh có thể thay đổi được.

Tuy nhiên, nếu chúng tôi không bao giờ sử dụng số trail của Zipper trước khi focus vượt quá phạm vi, chúng tôi sẽ không bao giờ có thể "xem" bí danh có thể thay đổi được. Điều này có vẻ tương tự như khoản vay có thể thay đổi thông thường: bạn không thể sử dụng biến số mà bạn đã vay từ khi khoản vay vượt quá phạm vi.

Có cách nào để giải thích điều này cho người kiểm tra vay không? Nếu bạn muốn "giải thích" cho người mượn mượn vay hai lát không chồng lên nhau từ một mảng thì không sao, bạn có thể sử dụng split_at: có một số chức năng tương ứng sẽ thực thi trail không bao giờ được sử dụng trước focus không nằm ngoài phạm vi và làm như vậy, thỏa mãn người mượn tiền?

Answer 1

Để đạt được mục tiêu của bạn, chúng tôi cần loại bỏ tham chiếu có thể thay đổi trong cấu trúc Zipper. Thay vào đó, chúng ta có thể sử dụng con trỏ nguyên liệu có thể thay đổi: chúng cho phép chúng ta thay đổi tham chiếu của chúng và chúng ta có thể có nhiều hơn một con trỏ trỏ đến một đối tượng cụ thể, nhưng việc dereferencing chúng không an toàn.

Dưới đây là các mã:

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

Các focus trường trong Zipper struct bây giờ là một *mut List<T>. Bởi vì đây là một con trỏ thô, chúng ta có thể sao chép nó một cách tự do. Điều này giải quyết lỗi trình biên dịch bạn có trong Zipper::down. Ngoài ra còn có một trường mới, _list, thuộc loại PhantomData<&'a mut List<T>>. PhantomData là một loại đặc biệt có nghĩa là để nói cho trình biên dịch "giả vờ tôi đang lưu trữ/sở hữu một T, mặc dù tôi không phải là". Nếu không có trường này, trình biên dịch sẽ phàn nàn rằng tham số trọn đời 'a không được sử dụng.

ý rằng Zipper::new vẫn hy vọng một &'a mut List<T> như một tham số: điều này cho phép Zipper để cung cấp một giao diện an toàn bằng cách yêu cầu người gọi để có một tài liệu tham khảo có thể thay đổi duy nhất cho các List<T>, một thực tế chúng ta có thể sử dụng để tuyên bố rằng các hoạt động không an toàn khác trong cấu trúc thực sự an toàn vì chúng tôi có kiến ​​thức đầy đủ về các tham chiếu có thể thay đổi có sẵn. Theo như trình biên dịch có liên quan, một số điện thoại Zipperlà có thể mượn List; nếu bạn cố gắng biến một số List trong khi một số Zipper trên số List là phạm vi, bạn sẽ gặp lỗi khi số List đã được vay mượn một cách tương đối.

---

Bạn chưa hiển thị bất kỳ mã nào cho phép người dùng tham chiếu đến tiêu điểm của Zipper. Tôi đã suy nghĩ về một triển khai có thể sẽ không an toàn, và nó là hấp dẫn để đi con đường đó, nhưng trình biên dịch sẽ không cho bạn biết nó sai.Hãy để tôi chỉ cho bạn:

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

Thật là hấp dẫn để trả lại &'a mut List<T> vì đó là những gì chúng tôi được cung cấp. Tuy nhiên, điều đó sai bởi vì giá trị của vòng đời trả về không bị ràng buộc với self theo bất kỳ cách nào, có nghĩa là chúng ta có thể gọi focus hai lần để nhận hai tham chiếu có thể thay đổi cho cùng một List<T>. Nếu chúng tôi vẫn có một số &'a mut List<T> trong Zipper, trình biên dịch sẽ cho chúng tôi biết nếu chúng tôi đã cố gắng trả lại &'a mut List<T> (trừ khi chúng tôi sử dụng mã unsafe để giải quyết nó). Một thực hiện đúng sẽ là:

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

Thực hiện điều này, các Zipper sẽ được mượn mutably chừng nào trở &mut List<T> là xung quanh, có nghĩa là chúng ta không thể gọi focus (hoặc down) cho đến khi &mut List<T> đi ra khỏi phạm vi.