無法在安全Rust中創建循環鏈表;不安全的版本崩潰

Question

我正在寫一個小型的戰略遊戲，但我在實現一個循環鏈表時遇到了問題。

這款遊戲涉及到幾個人一個接一個地採取行動，並一輪一輪地遊戲結束。我認爲這可以通過使用一個循環鏈表完成，其中每個元素都是一個參考下一個玩家的玩家。該結構是這樣的：

#[derive(Debug, Clone)] 
struct Player { 
    name: String, 
    killed: bool, 
    next: Option<Box<Player>>, 
} 

我也希望有一個指向當前活躍的球員，可以修改它的狀態，但我認爲鏽不允許我有相同的物體的兩個可變引用因爲每個玩家對下一個玩家都有一個可變的參考。

我想到的是，我可以使用一個簡單的可變參照Box，它由其前一個玩家擁有並指向當前玩家。我寫了一個簡單的主要功能，發生問題：

fn main() { 
    let mut p3: Player = Player { 
     name: "C".to_string(), 
     killed: false, 
     next: None, 
    }; 
    let mut p2: Player = Player { 
     name: "B".to_string(), 
     killed: false, 
     next: Some(unsafe { Box::from_raw(&mut p3) }), 
    }; 
    let mut p1: Player = Player { 
     name: "A".to_string(), 
     killed: false, 
     next: Some(unsafe { Box::from_raw(&mut p2) }), 
    }; 
    p3.next = Some(unsafe { Box::from_raw(&mut p1) }); 
    println!("GAME STARTED!"); 
    let mut current_player = p3.next.as_mut().unwrap(); 
    let mut count = 0; 
    while count < 10 { 
     println!("Player to kill/save {}", current_player.name); 
     (*current_player).killed = !(*current_player).killed; 
     println!("Player {} is killed: {}", 
       (*current_player).name, 
       (*current_player).killed); 
     current_player = (*current_player).next.as_mut().unwrap(); 
     count = count + 1 
    } 
    println!("End!"); 
} 

錯誤也是關於可變性，但我不知道如何解決它。我想知道是否有更好的方法在Rust中實現這個想法，而不是使用循環鏈表和指向當前播放器的指針。也許我應該切換到另一個結構？

錯誤消息是相當長的，這裏是第幾行：

error: cannot borrow `current_player` (via `current_player.name`) as immutable because `current_player` is also borrowed as mutable (via `current_player.next`) [E0502] 
     println!("Player to kill/save {}", current_player.name); 
             ^~~~~~~~~~~~~~~~~~~ 
note: mutable borrow occurs here (via `current_player.next`) 
     current_player = (*current_player).next.as_mut().unwrap(); 
        ^~~~~~~~~~~~~~~~~~~~~~ 
note: mutable borrow ends here 
} 

如果我改變as_mut()方法as_ref()它返回Box的不可變的參考和註釋行

// (*current_player).killed = !(*current_player).killed; 

該程序可以成功構建，但完成後會出現未知的運行時錯誤。不知道爲什麼會發生這種情況。

GAME STARTED! 
Player to kill/save A 
Player A is killed: false 
Player to kill/save B 
Player B is killed: false 
...... 
Player to kill/save C 
Player C is killed: false 
Player to kill/save A 
Player A is killed: false 
End! 
error: An unknown error occurred 

Answer 1

生鏽&mut不僅意味着可變的，但唯一的（與相同Box<T> - T假設由Box唯一擁有）。試圖用unsafe解決它將違反不變量，並會導致未定義的行爲。你得到的錯誤是因爲（我的猜測是你會導致雙重自由（遞歸？））。如果你想留在unsafe（不推薦），堅持在每個地方使用*mut指針。

內部可變性是你想要做的。你應該熟悉cell模塊。 This blogpost about interior mutability也值得一讀。

所以，我想重新定義你的結構類似：

use std::cell::{Cell,RefCell}; 
use std::rc::Weak; 

#[derive(Debug, Clone)] 
struct Player { 
    name: String, 
    killed: Cell<bool>, 
    next: RefCell<Option<Weak<Player>>>, 
} 

，並保持所有的球員背後Rc（引用計數指針）。如果您計劃讓所有玩家只活在主功能的堆疊上，那麼

next: Cell<Option<&Player>>, 

應該足夠了。

另一種選擇是把整個球員Rc<RefCell<Player>>，但它被認爲是很好的做法，只放可變部分的細胞。

Answer 2

首先，你應該去閱讀Learning Rust With Entirely Too Many Linked Lists。單向鏈接列表不是簡單的，這與多少種編程語言對待它們不同。當涉及所有權時，循環鏈表（或雙向鏈表）非常複雜，這是Rust的一個核心概念。

如果你有一個循環鏈表，誰擁有每一個項目？這很重要，因爲值的所有者預計會降低該值。

同樣，多個可變的引用是不允許的有原因。如果你想要它們，有一些像RefCell這樣的類型，可以讓你具有不直接對應於代碼結構的可變性。

崩潰的原因就在這裏：unsafe。你已經告訴編譯器「這很酷，我知道我在做什麼」，然後你繼續打破你所期待的所有保證。如果你想使用unsafe，你應該閱讀The Rustonomicon: The Dark Arts of Advanced and Unsafe Rust Programming。

儘管如此，只需使用一個Vec：

#[derive(Debug, Clone)] 
struct Player { 
    name: String, 
    killed: bool, 
} 

fn main() { 
    let mut players = vec![ 
     Player { 
      name: "C".to_string(), 
      killed: false, 
     }, 
     Player { 
      name: "B".to_string(), 
      killed: false, 
     }, 
     Player { 
      name: "A".to_string(), 
      killed: false, 
     }, 
    ]; 

    println!("GAME STARTED!"); 

    let mut current_player_idx = 0; 
    let player_count = players.len(); 

    for _ in 0..10 { 
     let current_player = &mut players[current_player_idx]; 

     println!("Player to kill/save {}", current_player.name); 
     current_player.killed = !current_player.killed; 
     println!(
      "Player {} is killed: {}", 
      current_player.name, current_player.killed 
     ); 

     current_player_idx += 1; 
     current_player_idx %= player_count; 
    } 
    println!("End!"); 
} 

請注意，您不需要任何顯式的解引用。