无法在安全Rust中创建循环链接列表；不安全的版本当机 [英] Unable to create a circular linked list in safe Rust; unsafe version crashes

问题描述

我正在编写一个小型战略游戏，但是在实现循环链​​表时遇到问题。

该游戏涉及几个人一个接一个地采取行动直到游戏结束为止。我可以通过使用循环链接列表来完成此操作，其中每个元素都是一个播放器，并引用下一个播放器。结构是这样的：

 ＃[derive（Debug，Clone）] 
 struct Player {
名称：字符串，
被杀死：bool，
接下来：Option< Box< Player>> ;, 
} 
  

我还想要一个指向当前活动播放器的指针并能够修改其状态，但是我认为Rust不允许我对同一个对象进行两个可变引用，因为每个玩家已经具有对下一个玩家的可变引用。

我想到的是，我可以使用对 Box ，由先前的播放器拥有并指向当前播放器。我写了一个简单的main函数来解决问题：

  fn main（）{
 let mut p3：Player =玩家{
名称： C .to_string（），
被杀：false，
 next：无，
}; 
 let mut p2：玩家=玩家{
名称： B .to_string（），
被杀死：false，
接下来：Some（不安全{Box :: from_raw（& ; mut p3）}），
}; 
 let mut p1：玩家=玩家{
名称： A .to_string（），
被杀死：false，
接下来：Some（不安全{Box :: from_raw（& ; mut p2）}），
}; 
 p3.next = Some（不安全{Box :: from_raw（& mut p1）}）; 
 println！（ GAME STARTED！）; 
 let mut current_player = p3.next.as_mut（）。unwrap（）; 
让mut count = 0; 
而计数< 10 {
 println！（杀死/保存{}的玩家，current_player.name）; 
（* current_player）.killed =！（* current_player）.killed; 
 println！（
玩家{}被杀死：{}，
（* current_player）.name，
（* current_player）.killed 
）; 
 current_player =（* current_player）.next.as_mut（）。unwrap（）; 
计数=计数+ 1 
} 
 println！（ End！）; 
} 
  

错误也与可变性有关，但我不知道如何解决。我想知道是否有更好的方法在Rust中实现这个想法，而不是使用循环链接列表和指向当前播放器的指针。也许我应该切换到另一个结构吗？

错误消息很长，下面是前几行：

< error [E0502]：无法借用current_player（通过current_player.name）是不可变的，因为current_player也是借来的可变（通过` current_player.next`）
-> src / main.rs：29：44
|
29 | println！（杀死/保存{}的玩家，current_player.name）；
| ^^^^^^^^^^^^^^^^^^^^^不变的借书current_player.name-与current_player.next重叠-在这里出现
...
36 | current_player =（* current_player）.next.as_mut（）。unwrap（）;
| ----------------------这里发生可变借用（通过current_player.next`）
...
40 | }
| -可变借款在这里结束


如果我更改 as_mut（） as_ref（）的c $ c>方法，该方法返回 Box 的不变引用，并注释行

  //（* current_player）.killed =！（* current_player）.killed; 
  

程序可以成功构建，但完成时会出现未知的运行时错误。也不知道为什么会这样。

 游戏已开始！ 
玩家杀死/保存A 
玩家A被杀死：false 
玩家杀死/保存B 
玩家B被杀死：false 
 ...... 
玩家杀死/保存C 
玩家C被杀死：false 
玩家杀死/保存A 
玩家A被杀死：false 
结束！ 
错误：发生未知错误
  

解决方案

第一个，您应该阅读 也要完全学习Rust许多链接列表 。单链列表不简单，与多少种编程语言对待它们不同。当涉及到所有权（Rust的核心概念）时，循环链表（或双向链表）非常复杂。

循环链接列表，谁拥有每个商品？，这很重要，因为期望值的所有者放弃该值。

类似地，出于某种原因不允许使用多个可变引用。如果需要它们，可以使用 RefCell之类的类型。 允许您具有与代码结构不直接对应的可变性。

崩溃的原因就在这里：不安全。您已经告诉编译器这很酷，我知道我在做什么，然后您继续违反所有期望得到的保证。如果要使用不安全，则应阅读 The Rustonomicon：高级和不安全Rust编程的黑暗艺术 。

在这种情况下， Box :: from_raw 特别警告您正在做什么：

调用此函数后，原始指针归于所得的框。具体来说， Box 析构函数将调用 T 的析构函数，并释放分配的内存。由于未指定 Box 分配和释放内存的方式，因此传递给此函数的唯一有效指针是从另一个 Box 通过 Box :: into_raw 函数。

---

虽然您不需要创建链接列表；只需使用 Vec ：

 ＃[derive（Debug，Clone） ] 
结构播放器{
名称：字符串，
被杀死：bool，
} 
 
 fn main（）{
让mut玩家= vec！[
 Player {
 name： C .to_string（），
 kill：false，
}，
 Player {
 name： B .to_string（），
被杀死：false，
}，
玩家{
名称： A .to_string（），
被杀死：false，
}，
]; 
 
 println！（游戏开始！）； 
 
让mut current_player_idx = 0; 
 let player_count = players.len（）; $。$ 10中$的
 
 {
 let current_player =& mut玩家[current_player_idx]; 
 
 println！（杀死/保存{}的玩家，current_player.name）； 
 current_player.killed =！current_player.killed; 
 println！（
玩家{}被杀死：{}，
 current_player.name，current_player.killed 
）; 
 
 current_player_idx + = 1; 
 current_player_idx％= player_count; 
} 
 println！（ End！）; 
} 
  

请注意，您不需要任何显式取消引用。

I am writing a small strategic game, but I have a problem with implementing a circular linked list.

The game involves several people taking actions one by one and round by round until the game ends. I though that this could be done by using a circular linked list where each element is a player with a reference to the next player. The structure is like this:

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

I also want a pointer to the current active player and be able to modify the status of it, but I think Rust does not allow me to have two mutable references to the same object because each player already has a mutable reference to the next player.

What I came up with is that I can use a simple mutable reference to the Box which is owned by its previous player and pointing to the current player. I wrote a simple main function where the problem occurs:

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

The error is also about the mutability but I have no idea how to fix it. I wonder if there is a better way to implement the idea in Rust rather than using a circular linked list and a pointer to the current player. Maybe should I switch to another structure?

The error message is quite long, here are the first few lines:

error[E0502]: cannot borrow `current_player` (via `current_player.name`) as immutable because `current_player` is also borrowed as mutable (via `current_player.next`)
  --> src/main.rs:29:44
   |
29 |         println!("Player to kill/save {}", current_player.name);
   |                                            ^^^^^^^^^^^^^^^^^^^ immutable borrow of `current_player.name` -- which overlaps with `current_player.next` -- occurs here
...
36 |         current_player = (*current_player).next.as_mut().unwrap();
   |                          ---------------------- mutable borrow occurs here (via `current_player.next`)
...
40 | }
   | - mutable borrow ends here

If I change the as_mut() method to as_ref() which returns the immutable reference of the Box, and comment the line

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

The program can build successfully but there will be an unknown runtime error when it finishes. Don't know why that happens either.

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

解决方案

First, you should go read Learning Rust With Entirely Too Many Linked Lists. Singly-linked lists are not simple, unlike how many programming languages treat them. Circular linked lists (or doubly-linked lists) are quite complicated when it comes to ownership, a core Rust concept.

If you have a circular linked list, who owns each item? This is important to know because the owner of a value is expected to drop the value.

Similarly, multiple mutable references are disallowed for a reason. If you want them, there are types like RefCell that allow you to have mutability that doesn't directly correspond to the structure of the code.

The reason of the crash is right here: unsafe. You've told the compiler "this is cool, I know what I'm doing" and then you proceed to break all the guarantees that you are expected to uphold. If you want to use unsafe, you should read The Rustonomicon: The Dark Arts of Advanced and Unsafe Rust Programming.

In this case, Box::from_raw specifically warns against what you are doing:

After calling this function, the raw pointer is owned by the resulting Box. Specifically, the Box destructor will call the destructor of T and free the allocated memory. Since the way Box allocates and releases memory is unspecified, the only valid pointer to pass to this function is the one taken from another Box via the Box::into_raw function.

---

You don't need to create a linked list though; just use a 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!");
}

Note that you don't need any explicit dereferencing.

这篇关于无法在安全Rust中创建循环链接列表；不安全的版本当机的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！