《通过链表学习Rust》学习笔记

 

《通过链表学习rust》笔记

《通过链表学习rust》笔记

1. 创建项目

$ cargo new --lib lists
     Created library `lists` package
$ cd lists

2. 差的栈实现

第一种链表实现方式会在 src/first.rs 中编写,在 Cargo 自动生成的 src/lib.rs 开头写上一行:

pub mod first;

2.1. 内存布局

什么是链表呢?定义如下:

List a = Empty | Elem a (List a)

和类型(sum type)链表 List 要么是空表 Empty,要么持有一个元素 Elem,同时后面跟着下一个链表 List

和类型:可以具有不同类型的值的类型

用 Rust 写出这个函数式版的定义:

enum List {
  Empty,
  Elem(i32, List),
}

但是这里出现了递归定义

$ cargo build
   Compiling lists v0.1.0
error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:2:1
  |
2 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
3 |     Empty,
4 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

rust无法计算出List类型的大小,所以要用指针来代替

enum List {
  Empty,
  Elem(i32, Box<List>),
}

但是这种定义涉及到内存在栈和堆上的分配问题,比如:

let a: List = List::Elem(100, Box::new(List::Empty));
println!("{:?}", a);
let b: List = List::Elem(10, Box::new(a));
println!("{:?}", b);

运行得到

Elem(100, Empty)
Elem(10, Elem(100, Empty))

内存布局:

[] =() =[Elem A, 指针] -> (Elem B, 指针) -> (Empty 垃圾数据)
  • rust的枚举体的内存分配:
    • 枚举类型的变量需要用一些整数tag来指示它是该枚举类型中的哪一种变体(variant)
    • 同时它需要足够的空间来存储 T1、T2、… Tn 中最大的类型(可能需要额外的空间来满足内存对齐的要求)
  • 有两个关键问题: 1.我们给一个没有存储数据信息的结点分配了空间
    • Empty 变体只含有一位的信息
    • 却占用了一个元素加一个指针的空间,因为它随时可能转变为 Elem 变体
    • 为了减少多分配的空间,我们可以用一个新的类型来避免
      enum List {
        Empty,
        ElemThenEmpty(i32),
        ElemThenNotEmpty(i32, Box<List>),
      }
      

      这样无需为Empty分配空间了,但它没有解决第2个问题,内存分配不一致的问题

      1. 其中一个结点却没有被分配堆空间
    • 第1个结点分配在了栈上

空指针优化 每个枚举变量都会有标志来标明它是哪种变体。但如果是这样的枚举类型:

enum Foo {
    A,
    B(NonNullPtr),
}

空指针优化就能起作用了。它可以节省标签占用的空间 如果是变体 A,就将储存内容全部置零 反之,非零内容则代表变体 B

  • 为了应用空指针优化,又解决内存分配不一致的问题:
    • 思想
      • 对于我们声明的类型而言,如果说枚举体能让它持有若干值中的一种,那么结构体就能使它同时拥有多个值
      • 据此,我们可以将原来的 List 类型拆成两部分:List 与 Node 类型
      • 我们最好把存放元素的空间,与为下一链表所分配的空间分开考虑
      • 这样一个链表要么是空表,要么“持有一个元素,同时后面跟着下一个链表”
    • 应用空指针优化,需要把枚举体写成如下形式
      enum List {
        Empty,
        Elem(Box<_>),
      }
      
    • 我们通过用一个完全独立的类型来实现「持有一个元素,同时后面跟着下一个链表」
    • 解决内存分配不一致问题
      • 所以有链表结点都存在堆上
      • 要保存的元素用结构体来表达
        struct Node {
          elem: i32,
          next: List,
        }
        
    • 另一种可能的布局:
      [指针] -> (Elem A, 指针) -> (Elem B, 空指针) -> (Empty)
      

      ```

得到新的链表:

#[derive(Debug)]
struct Node {
  elem: i32, 
  next: List,
}

#[derive(Debug)]
enum List {
  Empty,
  Elem(Box<Node>),
}

使用链表:

fn main() {
  let a = List::Elem(Box::new(Node {elem: 100, next: List::Empty}));
  println!("a: {:?}", a);
  match a {
    List::Elem(ref node) => {
      println!("a.elem: {:?}", node.elem);
      println!("a.next: {:?}", node.next);
    }    
    List::Empty => println!("a.elem: Empty"),
  }

  let b = List::Elem(Box::new(Node {elem: 10, next: a}));
  println!("b: {:?}", b);
  match b {
    List::Elem(ref node) => {
      println!("b.elem: {:?}", node.elem);
      println!("b.next: {:?}", node.next);
    }
    List::Empty => println!("b.elem: Empty"),
  }
}

得到结果:

a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty
b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty })
 })
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })

为了让别人能使用 List,我们将List访问权限设置为公有 pub:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

但编译出错了:

 cargo build
   Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists) error[E0446]: private type `Node` in public interface
  --> src/main.rs:10:8
   |
2  | struct Node {
   | ----------- `Node` declared as private
...
10 |   Elem(Box<Node>),
   |        ^^^^^^^^^ can't leak private type

error: aborting due to previous error

For more information about this error, try `rustc --explain E0446`.
error: could not compile `lists`

To learn more, run the command again with --verbose.

问题在于公有枚举体的所有内部变体也都是公有的,而私有类型不能出现在公有的地方。理论上我们可以也把 Node 设为公有类型,但这不符合 Rust 编程风格,我们应该将实现细节隐藏起来。为达成这一点,我们可以将 List 设成结构体:

#[derive(Debug)]
struct Node {
  elem: i32, 
  next: Link,
}

#[derive(Debug)]
enum Link {
  Empty,
  Elem(Box<Node>),
}

#[derive(Debug)]
pub struct List {
  head: Link,
}

fn main() {
  let a = Link::Elem(Box::new(Node {elem: 100, next: Link::Empty}));
  println!("a: {:?}", a);
  match a {
    Link::Elem(ref node) => {
      println!("a.elem: {:?}", node.elem);
      println!("a.next: {:?}", node.next);
    }    
    Link::Empty => println!("a.elem: Empty"),
  }

  let b = Link::Elem(Box::new(Node {elem: 10, next: a}));
  println!("b: {:?}", b);
  match b {
    Link::Elem(ref node) => {
      println!("b.elem: {:?}", node.elem);
      println!("b.next: {:?}", node.next);
    }
    Link::Empty => println!("b.elem: Empty"),
  }
  let list = List {head: b};
  println!("list: {:?}", list);
  println!("list.head: {:?}", list.head);
}

运行后得到:

❯ cargo run
   Compiling lists v0.1.0 (/home/wilson/experiments/rust/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 0.24s
     Running `target/debug/lists`

a: Elem(Node { elem: 100, next: Empty })
a.elem: 100
a.next: Empty

b: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next: Empty }) })
b.elem: 10
b.next: Elem(Node { elem: 100, next: Empty })

list: List { head: Elem(Node { elem: 10, next: Elem(Node { elem: 100
, next: Empty }) }) }

list.head: Elem(Node { elem: 10, next: Elem(Node { elem: 100, next:
Empty }) })

2.2. New 方法

我们创建好了链表的数据结构,现在要加入的是它的方法。首先是 new 方法

impl List {
  fn new() -> Self {
    List {head: Link::Empty}
  }
}

可以用 Self 指代 impl 块所实现的类型

2.3. 所有权初探

在 Rust 中,方法就是一类特殊的函数。它们拥有无须指明类型的 self 参数,self 参数主要有三种形式:self&mut self&self。它们分别代表了 Rust 中主要的三种所有权:

  • self代表值(value)
    • 值意味着真正的所有权
      • 你可以移动它、销毁它、改变它
      • 或者以引用的方式借出它
    • 当你按值传递对象时,它会被移动到新的变量
  • &mut self:可变引用
    • 可变引用意味着对你不拥有的对象暂时有独占的访问权利
    • 只要有了可变引用,那你就可以为所欲为了
  • &self:共享引用
    • 共享引用意味着对你不拥有的对象暂时有共享的访问权利

2.4. Push 方法

因为push会改变链表,所以我们用&mut self

impl List {
  pub fn push(&mut self, elem: i32) {
      let node = Node {
        elem,
        next: mem::replace(&mut self.head, Link::Empty),
      }
      self.head = Link::More(Box::new(node));
  }
}

2.5. Pop 方法

pop方法也会改写list,所以仍用&mut self。但pop会遇到链表为空和链表非空的情况,所以:

impl List {
  pub fn pop(&mut self) {
    match mem::replace(&mut self.head, Link::Empty) {
      Link::Empty => None,
      Link::More(pnode) => {
          self.head = pnode.next;
          Some(pnode.elem)
      }
    }
  }
}

2.6. 单元测试

  • 一般来说,我们会尽量将我们的测试放在代码旁边
  • 我们通常为测试创建一个新的名称空间,以避免与“真正的”代码发生冲突
  • 我们可以使用mod来创建一个全新的内联文件
  • 我们所要做的就是编写一个函数,并用#[test]标注它
// in first.rs

#[cfg(test)] // 只在测试时才编译这个模块,否则模块内的List导入但未使用
mod test {
  use super::List; //因为我们创建了一个新模块,所以需要显式地导入`List`来使用它

  #[test]
  fn basics() {
  // Check empty list behaves right
  assert_eq!(list.pop(), None);}
}
  • 因为我们创建了一个新模块,所以需要显式地导入List来使用它
  • 因为我们只有在测试时使用了List,所以我们应该指出,只有在运行测试时才应该编译整个测试模块

2.7. Drop 方法

如果一个类型实现了一个称为Drop的特征,那么它就有一个析构函数,Drop的声明如下:

pub trait Drop {
    fn drop(&mut self);
}

List实现Drop

impl Drop for List {
  fn drop(&mut self) {
    let mut cur_link = mem::replace(&mut self.head, Link::Empty);

    while let Link::More(pnode) = cur_link {
      cur_link = mem::replace(&mut pnode.next, Link::Empty);
    }
  }
}

3 一个好的单链接堆栈

让我们添加一个名为second.rs的新文件

// in lib.rs 
pub mod first
pub mod second

3.1. 使用 Option

实际上可以改进的地方如下:

  1. enumOption表达
     enum Link {
         Empty,
         More(Box<Node>),
     }
    

    相当于 Option<Box<Node>>,再用type Link = Option<Box<Node>>,于是我们得到新的List数据结构写法:

     struct List {
       head: Link,
     }
    
     type Link = Option<Box<Node>>;
    
     struct Node {
       elem: i32,
       next: Link,
     }
    
  2. mem::replace可以用take表示 实际上 mem::replace(&mut option, none) 是非常常见的用法,rust用take方法来实现
     pub fn take(&mut self) -> Option<T>
    

    所以 mem::replce(&mut self.head, Link::Empty); 就相当于 self.head.take()

  3. match option { None => None, Some(x) => Some(y)} 是一个非常常见的习惯用法,它被称为map
    1. map接受一个函数,在Some(x)中的x上执行,生成Some(y)中的y
    2. 我们可以编写一个合适的fn并将其传递给map,但我们更愿意编写内联操作
      pub fn pop(&mut self) -> Option<i32> {
        self.head.take().map(|node| {
       self.head = node.next;
        Some(node.elem)
        })
      }
      

3.2. Generic

把具体类型转变为泛型<T>

  1. List数据结构
     struct List<T> {
       head: Link<T>,
     }
     type Link<T> = Option<Box<Node<T>>>;
     struct Node<T> {
       elem: T,
       next: Link,
     }
    
  2. List的方法

     impl<T> List<T> {
         pub fn new() -> Self {
           List {head: None}
         }
    
         pub fn push(&mut self, elem: T) {
           let node = Node {
             elem,
             next: self.head.take(),
           }
           self.head = Some(node);
         }
    
         pub fn pop(&mut self) -> Option<T> {
           self.head.take().map(|node| {
             self.head = node.next;
             Some(node.elem)
           })
         }
     }
    
     impl<T> Drop for List<T> {
       let cur_link = self.head.take();
       while let Some(cur_node) = cur_link {
           cur_link = cur_node.next.take();
       }
     }
    

3.3. Peek

我们所需要做的就是返回对列表头元素的引用(如果它存在的话)

impl List {
  pub fn peek(&mut self) -> Option<&T> {
    self.head.as_ref().map(|node| {
      &node.elem
    })
  }
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| {
      &mut node.elem
    })
  }
}

加入测试

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);

    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
  }
}

但是当我们要修改值时要注意:

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);
    list.peek_mut().map(|&mut elem| {
      elem = 100;
    });
  }
}

事实证明,这样写闭包的参数并不能说明value是一个可变引用。相反,它创建了一个模式,将与闭包的参数进行匹配;|&mut value|的意思是 “参数是一个可突变的引用,但请将它指向的值复制到value中即可”。如果我们只是使用|value|,那么value的类型将是&mut i32

mod test {
  #[test]
  fn peek() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(3);
    list.peek_mut().map(|elem| {
      *elem = 100;
    });
  }
}

3.4. IntoIter

rust中迭代器的声明如下:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

迭代器产生Option<Self::Item>的原因是接口合并了has_nextget_next概念。每个类型需要实现三种类型的迭代器:

  • Into迭代:T
  • Mut迭代:&mut T
  • 迭代:&T
  1. 创建一个IntoIter类型
     pub struct IntoIter<T>(List<T>);
    
  2. List<T>实现into_iter方法,将List<T>类型转换为IntoIter<T>类型
     impl<T> List<T> {
       pub fn into_iter(self) -> IntoIter<T> {
           IntoIter(self)
       }
     }
    
  3. IntoIter<T>类型实现Iterator特性
     impl<T> Iterator for IntoIter<T> {
       type Item = T;
       pub fn next(&mut self) -> Option<Self::Item> {
         self.0.pop()
       }
     }
    
  4. 写测试代码
     mod test {
       #[test]
       fn into_iter() {
         let mut list = List::new();
         list.push(1); list.push(2); list.push(3);
    
         let mut iter = list.into_iter();
         assert_eq!(iter.next(), Some(3));
         assert_eq!(iter.next(), Some(2));
         assert_eq!(iter.next(), Some(1));
         assert_eq!(iter.next(), None);
       }
     }
    

3.5. Iter

pub struct List<T> {
    head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem,
            next: self.head.take(),
        });
        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|pnode| {
            self.head = pnode.next;
            pnode.elem
        })
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|node| &node.elem)
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|node| &mut node.elem)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();

        while let Some(mut cur_node) = cur_link {
            cur_link = cur_node.next.take();
        }
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.head.take().map(|node| {
            self.0.head = node.next;
            node.elem
        })
    }
}

pub struct IterRef<'a, T>(Option<&'a Node<T>>);

impl<T> List<T> {
    pub fn iter_ref<'a>(&'a self) -> IterRef<'a, T> {
        IterRef(self.head.as_deref())
    }
}

impl<'a, T> Iterator for IterRef<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.map(|node| {
            self.0 = node.next.as_deref();
            &node.elem
        })
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn sec_list() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        if let Some(elem) = list.peek_mut() {
            *elem = 100;
        }
        assert_eq!(list.peek(), Some(&100));
        list.peek_mut().map(|elem| *elem = 3);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), None);

        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), None);

        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter_ref = list.iter_ref();
        assert_eq!(iter_ref.next(), Some(&3));
        assert_eq!(iter_ref.next(), Some(&2));
        assert_eq!(iter_ref.next(), Some(&1));
    }
}

3.6. IterMut

根据IterRef的实现:

impl<'a, T> Iterator for IterRef<'a, T> {
  type Item = &'a T;

  fn next(&mut self) -> Option<Self::Item> {...}
}

去糖后的真实代码是

impl<'a, T> Iterator for IterRef<'a, T> {
  type Item = &'a T;
  fn next<'b>(&'b mut self) -> Option<&'a T> {...}
}

next的签名在输入和输出的生命期之间没有建立任何约束! 为什么我们要关心这个问题?这意味着我们可以无条件地重复调用 next!

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();

对于共享引用来说,这绝对是好的,因为整个要点就是你可以同时拥有大量的引用。然而可变引用不能共存。关键就是它们是排他性的。

最终的结果是,使用安全代码编写IterMut明显更难了(我们还没有讨论到这意味着什么……)。令人惊奇的是,IterMut实际上可以完全安全地实现许多结构!我们将从以下几个方面入手。

我们先把Iter代码改成可变的:

pub struct IterMut<'a, T> {
  next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
  pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut {next: self.head.as_deref_mut()}
  }
}

impl<'a, T> Iterator for IterMut<'a, T> {
  type Item = &'a mut T;

  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref_mut();
      &mut node.elem
    })
  }
}
> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
  --> src/second.rs:95:25
   |
94 |     pub fn iter_mut(&self) -> IterMut<'_, T> {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
95 |         IterMut { next: self.head.as_deref_mut() }
   |                         ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error[E0507]: cannot move out of borrowed content
   --> src/second.rs:103:9
    |
103 |         self.next.map(|node| {
    |         ^^^^^^^^^ cannot move out of borrowed content

好吧,看起来我们这里有两个不同的错误。第一条看起来非常清楚,甚至告诉我们如何修复它!你不能将共享引用升级到可变引用,所以iter_mut需要采用&mut self

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
}

那另一个呢?

哎呀! 其实我在上一节写iter impl的时候不小心出了一个错误,我们只是运气好,才成功的!

我们刚刚第一次接触到Copy的魔力。当我们介绍所有权时,我们说当你转移资源后,你将不能再使用它。对于某些类型,这是很有道理的。我们的好朋友Box为我们管理着堆上的分配,我们当然不希望两段代码都认为他们需要释放它的内存。

然而对于其他类型来说,这就是垃圾。整数没有所有权语义,它们只是无意义的数字!这就是为什么整数被标记为Copy的原因。众所周知,Copy类型是可以通过比特复制来完美拷贝的。因此,它们有一个超级能力:当移动时,旧的值仍然可以使用。因此,你甚至可以将Copy类型从一个引用中移出而不需要replace替换!

rust 中的所有数字基元 (i32, u64, bool, f32, char, 等等…) 都是 Copy。你也可以声明任何用户定义的类型也是Copy,只要它的所有组件都是Copy

关键是为什么这段代码能用,共享引用也是Copy! 因为&CopyOption<&>也是Copy。所以当我们做self.next.map的时候,因为Option只是被Copy了,所以很正常。现在我们不能这样做,因为&mut不是Copy(如果你复制了一个&mut,你就会有两个&mut到内存的同一个位置,这是禁止的)。相反,我们应该正确地对Option应用take来获取它。

fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
        self.next = node.next.as_deref_mut();
        &mut node.elem
    })
}
cargo build

卧槽,IterMut编译通过了! 我们来测试一下:

#[test]
fn iter_mut() {
  let mut list = List::new();
  list.push(1); list.push(2); list.push(3);

  let mut iter = list.iter_mut();
  assert_eq!(iter.next(), Some(&mut 3));
  assert_eq!(iter.next(), Some(&mut 2));
  assert_eq!(iter.next(), Some(&mut 1));
}
> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

test result: ok. 7 passed; 0 failed; 0 ignored; 0 measured

它正常工作了,卧槽,为什么?

我们刚刚实现了一段代码,它接收了一个单链的列表,并返回一个列表中的每一个元素的可变的引用(最多一次)。而且它是经过静态验证的,所以是完全安全的。

如果你问我的话,这是个大问题。这有几个原因:

  • 我们对Option<&mut>使用了take,所以我们有专属的访问权来获取可变的引用。不需要担心有人再看它
  • Rust明白,把一个可变引用共享到指向结构的子字段中是可以的,因为没有办法 “往上走”,而且它们肯定是不相干的

事实证明,你也可以应用这个基本逻辑来为一个数组或一棵树获得一个安全的IterMut! 你甚至可以把迭代器做成DoubleEnded,这样你就可以从前面和后面同时消耗迭代器了! 哇!

pub struct IterMut<'a, T>(Option<&'a mut Node<T>>);

impl<'a, T> List<T> {
    pub fn iter_mut(&'a mut self) -> IterMut<'a, T> {
        IterMut(self.head.as_deref_mut().map(|node| node))
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node| {
            self.0 = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}

4 一个持久的单链栈

好了,我们已经掌握了可变单链栈的技巧。

让我们通过编写一个持久不变的单链列表,从单一所有权转向共享所有权。这将是函数式程序员所熟悉和喜爱的列表。你可以得到头或者尾巴,把一个链表的头放在另一个链表的尾巴上……基本上就是这样。

在这个过程中,我们大体上只会熟悉RcArc,但这将为下一个改变游戏的列表做准备。

让我们添加一个新的文件,叫做third.rs

pub mod frist;
pub mod second;
pub mod third;

4.1 Layout

好了,回到布局的画板上。

关于持久化列表最重要的一点是,你基本上可以无代价的操作列表的尾部。

比如说,在持久化列表中,这是一个常见的工作量:

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

但在最后,我们希望内存是这样的:

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

Boxes不能达到这个效果,因为B的所有权是共享的。谁应该释放它?如果我删除list2,会释放B吗?如果使用了Boxes的话,意味着我们希望如此。

函数式语言–实际上几乎所有其他语言–都可以通过使用垃圾回收来解决这个问题。有了垃圾收集的魔力,B只有在每个人都停止查询它之后才会被释放。万岁!

Rust没有任何类似于这些语言的垃圾收集器。他们有跟踪GC,它会在运行时挖出所有的内存,并自动找出哪些是垃圾。相反,Rust今天所拥有的是引用计数。引用计数可以被认为是一个非常简单的GC。对于许多工作应用来说,它的消耗明显低于跟踪收集器,如果你设法建立周期,消耗量可以忽略不计。但是,嘿,这就是我们的全部了! 值得庆幸的是,对于我们的案例来说,我们永远不会遇到周期问题(你可以试着自己证明这一点–我肯定不会)。

那么我们如何进行引用计数的垃圾收集呢?Rc! Rc就像Box一样,但我们可以复制它,只有当所有由它派生的Rc被析构时,它的内存才会被释放。不幸的是,这种灵活性付出了严重的代价:我们只能对它的内部进行共享引用。这意味着我们无法真正从其中任一个列表中取出数据,也无法对它们进行修改。

那么我们的布局会是什么样子呢?嗯,之前我们有:

pub struct List<T> {
  head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
} 

我们能只把Box改为Rc吗?

// in thrid.rs 
use std::rc::Rc;

pub struct List<T> {
  head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
  elem: T,
  next: Link<T>,
}
cargo build

warning: field is never used: `head`
 --> src/third.rs:4:5
  |
4 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

似乎是合法的。Rust继续是完全琐碎的写作。我敢打赌,我们可以用Rc找到并替换Box,然后就可以了。

4.2. Basics

我们现在已经知道了很多Rust的基础知识,所以我们可以再做很多简单的事情。

对于构造函数,我们又可以直接复制粘贴。

impl<T> List<T> {
  pub fn new() -> Self {
    List {head: None}
  }
}

pushpop已经没有意义了。相反,我们可以提供appendtail,它们提供的东西大致相同。

让我们从append开始。它接收一个list和一个元素,然后返回一个List。就像可变 list 的情况一样,我们要做一个新的节点,它的下一个值是旧的 list。唯一新奇的是如何获得下一个值,因为我们不允许改变任何东西。

我们祈祷的答案就是Clone特性。Clone 几乎被每个类型都实现了,它提供了一种通用的方法来获取 “另一个像这个一样的”,它只给定一个共享引用,在逻辑上是不相干的。它就像C++中的复制构造函数,但它从来没有被隐式调用。

特别是Rc使用Clone作为增量引用数的方式。所以,我们不是把一个Box移到子列表中,而是直接克隆旧列表的头部。我们甚至不需要在头部进行匹配,因为Option暴露了一个Clone实现,它完全可以完成我们想要的事情。

好吧,让我们试试看:

pub fn append(&self, elem: T) -> List<T> {
  List {head: Some(Rc::new(Node {
    elem,
    next: self.head.clone(),
  }))}
}
> cargo build
warning: field is never used: `elem`
  --> src/third.rs:10:5
   |
10 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

哇,Rust对实际使用字段的态度真的很精明。它告诉我们,没有消费者能够真正观察到这些字段的使用情况! 不过,我们目前看来还是不错的。

tail是这个操作的逻辑反转。它接收一个列表,然后返回整个列表,并删除第一个元素。所有这些都是克隆列表中的第二个元素(如果它存在的话)。让我们试试这个。

pub fn tail(&self) -> List<T> {
  List { head: self.head.as_ref().map(|node| node.next.clone()) }
}
> cargo build
error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

Hrm, 我们搞砸了。map期望我们返回一个Y,但这里我们返回的是Option<Y>。幸运的是,这是另一种常见的Option模式,我们可以使用and_then让我们返回一个Option

pub fn tail(&self) -> List<T> {
  List {head: self.head.as_ref().and_then(|node| node.next.clone()) }
}
> cargo build

好极了!

现在我们有了tail,我们应该提供head,它返回对第一个元素的引用。这只是从可变列表中peek查看到的:

pub fn head(&self) -> Option<&T> {
  self.head.as_ref().map(|node| &node.elem)
}

漂亮!

这样的功能已经足够我们测试了:

#[cfg(test)]
mod test {
  use super::List;
  #[test]
  fn baiscs() {
    let list = List::new();
    assert_eq!(list.head(), None);
    
    let list = list.append(1).append(2).append(3);
    assert_eq!(list.head(), Some(&3));
    
    let list = list.tail();
    assert_eq!(list.head(), Some(&2));
    
    let list = list.tail();
    assert_eq!(list.head(), Some(&1));
    
    let list = list.tail();
    assert_eq!(list.head(), None);
    
    // 确认空链表tail也工作
    let list = list.tail();
    assert_eq!(list.head(), None);
  }
}
> cargo test
     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured

完美!

Iter也与我们的可变列表相同:

pub struct Iter<'a, T> {
  next: Option<&'a Node<T>>,
}

impl<T> List<T> {
  pub fn iter(&self) -> Iter<'_, T> {
    Iter { next: self.head.as_deref() }
  }
}

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = &'a T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref();
      &node.elem
    })
  }
}
#[test]
fn iter() {
	let list = List::new().append(1).append(2).append(3);
	
	let mut iter = list.iter();
	assert_eq!(iter.next(), Some(&3));
	assert_eq!(iter.next(), Some(&2));
	assert_eq!(iter.next(), Some(&1));
}
cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured

谁说过动态类型更容易?

注意,我们不能为这种类型实现IntoIterIterMut。我们只能对元素进行共享访问。

4.3. Drop

和可变列表一样,我们也有一个递归的析构器问题。诚然,对于不可变列表来说,这并不是一个很糟糕的问题:如果我们曾经在某个地方碰到过另一个列表的头的节点,我们不会递归地放弃它。然而这仍然是一个我们应该关心的事情,如何处理并不是那么清楚。我们之前是这样解决的。

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_node.next.take();
    }
  }
}

问题是loop

cur_link = boxed_node.next.take();

这是在Box里面修改Node,但是我们不能用Rc来做,它只给我们共享的访问权,因为任意数量的其他Rc都可能指向它。

但是如果我们知道我们是最后一个知道这个节点的列表,其实把Node移出Rc就可以了。然后我们也可以知道什么时候停止:每当我们不能把Node提取出来的时候。

而你看,Rc有一个方法正是这样做的:try_unwrap

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut head = self.head.take();
    while let Some(node) = head {
      if let Ok(mut node) = Rc::try_unwrap(node) {
        head = node.next.take();
      } else {
        break;
      }
    }
  }
}
> cargo test
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/too-many-lists/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 1.10s
     Running /Users/ABeingessner/dev/too-many-lists/lists/target/debug/deps/lists-86544f1d97438f1f

running 8 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

好极了,干得漂亮!

4.4. Arc

使用不可变链表的一个原因是为了跨线程共享数据。毕竟共享的可变状态是万恶之源,解决这个问题的一个方法就是永远杀死可变部分。

只是我们的列表根本不是线程安全的。为了做到线程安全,我们需要原子地摆弄引用计数。否则,两个线程可能会尝试递增引用计数,而只有一个会发生。那么列表可能会过早地被释放!

为了获得线程安全,我们必须使用ArcArcRc完全相同,只是引用计数是原子化修改的。如果你不需要的话,这有一点开销,所以Rust暴露了这两个功能。我们需要做的就是把每一个对 Rc的引用替换为 std::sync::Arc。就是这样。我们的线程安全了。

但这提出了一个有趣的问题:我们如何知道一个类型是否是线程安全的?我们会不会不小心搞砸了?

不!在 Rust 中,你不能搞砸线程安全。

之所以如此,是因为Rust用两个特性以一流的方式来模拟线程安全。SendSync.

如果一个类型可以安全地移动到另一个线程,那么它就是Send。如果一个类型在多个线程之间共享是安全的,那么它就是Sync。也就是说,如果TSync&T就是Send。在这种情况下,安全意味着不可能引起数据竞争,(不要误解为更一般的竞争条件问题)。

这些都是标记性特征,这是一种花哨的说法,它们是完全不提供接口的特征。你要么是发送,要么不是。这只是一个其他API可以要求的属性。如果你不是适当的Send,那么静态上就不可能被发送到不同的线程! 很好!

SendSync也是根据你是否完全由SendSync类型组成而自动派生的特征。这类似于只有由Copy类型构成时才能实现Copy,但如果你是Copy类型,我们就会自动去实现它。

几乎每个类型都是SendSync。大多数类型都是Send,因为它们完全拥有自己的数据。大多数类型是Sync,因为跨线程共享数据的唯一方法是把它们放在一个共享引用的后面,这使得它们是不可改变的。

然而,有一些特殊的类型违反了这些属性:那些具有内部可变性的类型。到目前为止,我们只真正地与继承的可变性(也就是外部可变性)进行了交互:一个值的可变性是由它的容器的可变性继承而来的。也就是说,你不能因为你觉得喜欢而随机突变一个不可变值的某个字段。

内部可变性类型违反了这一点:它们让你通过共享引用进行改变。内部可变性有两大类:单元格cells,它只在单线程上下文中工作;以及在多线程上下文中工作的锁locks。由于显而易见的原因,当你能使用单元格cells时,单元格cell开销更小的。还有原子atomics,它是类似锁的原语。

那么这些和RcArc有什么关系呢?好吧,它们都使用内部可变性作为它们的引用计数。更糟糕的是,这个引用计数是在每个实例之间共享的!Rc只是使用一个单元格cell,这意味着它不是线程安全的。Arc使用原子atomic,这意味着它是线程安全的。当然,你不能通过把一个类型放在Arc中就神奇地使它成为线程安全的。Arc只能像其他类型一样派生出线程安全。

我真的真的不想深入讨论原子内存模型或非派生的Send实现的细节。不用说,随着您深入了解Rust的线程安全故事,事情会变得更加复杂。作为一个高级使用者,你真的不需要去思考它。

4.5. Final Code

use std::rc::Rc;

type Link<T> = Option<Rc<Node<T>>>;

pub struct List<T> {
    head: Link<T>,
}

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None }
    }

    pub fn append(&self, elem: T) -> Self {
        List {
            head: Some(Rc::new(Node {
                elem,
                next: self.head.clone(),
            })),
        }
    }

    pub fn tail(&self) -> Self {
        List {
            head: self.head.as_ref().and_then(|node| node.next.clone()),
        }
    }

    pub fn head(&self) -> Option<&T> {
        self.head.as_deref().map(|node| &node.elem)
    }
}

pub struct IterRef<'a, T>(Option<&'a Node<T>>);

impl<T> List<T> {
    pub fn iter_ref(&self) -> IterRef<'_, T> {
        IterRef(self.head.as_deref())
    }
}

impl<'a, T> Iterator for IterRef<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        self.0.map(|node| {
            self.0 = node.next.as_deref();
            &node.elem
        })
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.append(1).append(2).append(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);
        let list = list.tail();
        assert_eq!(list.head(), None);
    }

    #[test]
    fn iter_ref() {
        let list = List::new().append(1).append(2).append(3);
        let mut iter_ref = list.iter_ref();
        assert_eq!(iter_ref.next(), Some(&3));
        assert_eq!(iter_ref.next(), Some(&2));
        assert_eq!(iter_ref.next(), Some(&1));
    }
}

5. A Bad Safe Deque

现在,我们已经看到了Rc,听说了内部可变,这给了一个有趣的想法…也许我们可以通过Rc实现可变。如果是这样的话,也许我们可以完全安全地实现一个双链表!

在这个过程中,我们将会熟悉内部的可变性,并且可能会艰难地认识到安全并不意味着正确。双链表很难,而且我总是在某个地方犯错误。

让我们添加一个名为fourth.rs的新文件

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;

免责声明:这一章基本上证明了这是一个非常糟糕的想法。

5.1. Layout

我们设计的关键是RefCell类型。RefCell的核心是一对方法:

fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;

borrowborrow_mut的规则与&&mut的规则完全相同:你可以随意调用borrow,但borrow_mut要求排他性。

RefCell并不是静态地强制它们,而是在运行时强制它们。如果你违反了规则,RefCell就会panic,让程序崩溃。为什么它返回这些RefRefMut的东西?它们的行为和Rc很像,只是引用而已。他们还会保持RefCell的借用,直到它们超出了范围。我们稍后会讲到。

现在,有了RcRefCell,我们可以成为… 一个难以置信的冗长的、可普遍突变的、不能收集周期的垃圾收集语言。Y-yaaaaay……

好了,我们要做双链路。这意味着每个节点都有一个指向上一个节点和下一个节点的指针。同时,List本身也有一个指向第一个节点和最后一个节点的指针。这样我们就可以在列表的两端快速插入和删除。

所以,我们可能想要这样的东西:

use std::rc::Rc;
use std::cell::RefCell;

pub struct List<T> {
  head: Link<T>,
  tail: Link<T>,
}
  
type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
  prev: Link<T>,
}

5.2. Building

好了,我们先从建立列表开始。这个新系统很直接,new还是很琐碎的,只要把所有字段都None掉就可以了。另外,由于它变得有点笨拙,让我们再使用一个Node构造函数

impl<T> Node<T> {
  fn new(elem: T) -> Rc<RefCell<Self>> {
    Rc::new(RefCell::new(Node {
      elem,
      prev: None,
      next: None,
    }))
  }
}

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
}
> cargo build
**一堆死代码警告但已建立成功**

耶!

现在,让我们尝试写push到列表的前面。因为双链表要复杂得多,所以我们需要做更多的工作。单链表操作可以简化为简单的一行操作,而双链表操作则相当复杂。

特别地,我们现在需要特别处理空列表周围的一些边界情况。大多数操作将只触及头部或尾部指针。然而,当切换到空列表或从空列表切换时,我们需要同时编辑这两个列表。

对我们来说,验证我们的方法是否合理的一个简单方法是,我们保持以下不变性:

  • 每个节点都应该有两个指向它的指针
  • 列表中间的每个节点由其前任和后继指向,而两端的节点则由列表本身指向。

让我们试一试吧:

pub fn push_front(&mut self, elem: T) {
  // 新节点需要+2个链接,其他节点都应该是+0
  let new_node = Node::new(elem);
  match self.head.take() {
  	Some(old_head) => {
      //非空列表,需要连接old_head
      old_head.prev = Some(new_head.clone()); // +1 new_head
      new_head.next = Some(old_head);	// +1 old_head
      self.head = Some(new_head);	// +1 new_head, -1 old_head
      // 总计:+2 new_head, +0 old_head -- OK!  
    }
    None => {
      // 空列表,需要设置尾部
      self.tail = Some(new_head.clone());	// +1 new_head
      self.head = Some(new_head);	// +1 new_head
      // 总计:+2 new_head -- OK!
    }
  }
}
> cargo build
error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

好吧。编译器错误。良好的开端。

为什么我们不能访问节点上的prevnext字段?之前我们只有Rc<Node>时,它可以工作。看来RefCell有点碍事了。我们应该查阅一下文档。

具有动态检查借位规则的可变内存位置

有关更多信息,请参阅模块级文档

共享可变容器。Cell<T>RefCell<T>类型的值可以通过共享引用(即共同的&T类型)发生突变,而大多数Rust类型只能通过唯一引用(&mut T)发生突变。我们说Cell<T>RefCell<T>提供了“内部突变性”,与典型的Rust类型表现出“继承突变性”相反。

Cell类型有两种:Cell<T>RefCell<T>Cell<T>提供了getset方法,这些方法可以通过一个方法调用来更改内部值。Cell<T>只与实现复制的类型兼容。对于其他类型,必须使用RefCell<T>类型,在突变之前获取写锁。

RefCell<T>使用Rust的生命周期来实现“动态借用”,在这个过程中,人们可以声明对内部值的临时、独占、可变访问。RefCell<T>的借用是在“运行时”被跟踪的,不像Rust的原生引用类型是在编译时完全静态跟踪的。因为RefCell<T>的借用是动态的,所以可以尝试去借用一个已经被可变地借用的值;当这种情况发生时,会导致线程panic

何时选择内部可变性

比较常见的继承可变性,必须有唯一的访问权限才能改变一个值,是使Rust能够有力地推理指针别名的关键语言元素之一,从而静态地防止崩溃bug。因此,继承的可变性是首选,而内部可变性是最后的手段。由于单元格类型在不允许突变的地方可以实现突变,所以在某些情况下,内部突变可能是合适的,甚至是必须使用的,如:

  • 将继承的可变性根引入共享类型
  • 逻辑不可变方法的实现细节
  • Clone的可变实现

在共享类型中引入继承变异性根部

共享的智能指针类型,包括Rc<T>Arc<T>,提供了可以在多方之间克隆和共享的容器。因为包含的值可能是多重别名的,所以它们只能作为共享引用而不是可变引用借来。如果没有单元格,就根本不可能改变共享框中的数据。

在共享指针类型中放置RefCell<T>来重新引入可变性是很常见的

use std::collections::HashMap;
use std::cell::RefCell;
use std::rc::Rc;

fn main() {
    let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new()));
    shared_map.borrow_mut().insert("africa", 92388);
    shared_map.borrow_mut().insert("kyoto", 11837);
    shared_map.borrow_mut().insert("piccadilly", 11826);
    shared_map.borrow_mut().insert("marbles", 38);
}

注意,这个例子使用的是Rc<T>,而不是Arc<T>RefCell<T>用于单线程场景。如果在多线程环境中需要共享的可变性,可以考虑使用Mutex<T>

嘿,Rust的文档仍然很棒。

我们关心的是以下这一行:

shared_map.borrow_mut().insert("africa", 92388);

尤其是borrow_mut的东西。 似乎我们需要显式借用RefCell.运算符不会为我们这样做。 奇怪, 咱们试试吧:

pub fn push_front(&mut self, elem: T) {
  let new_head = Node::new(elem);
  match self.head.take() {
    Some(old_head) => {
      old_head.borrow_mut().prev = Some(new_head.clone());
      new_head.borrow_mut().next = Some(old_head);
      self.head = Some(new_head);
    }
    None => {
      self.tail = Some(new_head.clone());
      self.head = Some(new_head);
    }
  }
}
> cargo build

warning: field is never used: `elem`
  --> src/fourth.rs:12:5
   |
12 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

嘿,它构建通过了! Docs又赢了。

list           new_head          Node             Node             Node
+-------+   +--+--------+--+ +-----------+--+ +-----------+--+ +-----------+-----+
| head <----+  |  prev  |  +----->prev   |  +----> prev   |  +----> prev   |     |
+-------|      +--------+    |  +--------+    |  +--------+    |  +--------+     |
| tail <----+  |  next <-----+  | next <------+  | next <------+  | next   |     |
+-------+   |  +--------+       +--------+       +--------+       +--------+     |
            |  |  elem  |       | elem   |       | elem   |       | elem   |     |
            |  +--------+       +--------+       +--------+       +--------+     |
            |                                                                    |
            |                                                                    |
            +--------------------------------------------------------------------+

list
+-------+      new_head
| head <----+--+--------+     +-------+
+-------|   |  |  prev <----+-+  None |
| tail <----+  +--------|   | +-------+
+-------+      |  next <----+
               +--------+
               |  elem  |
               +--------+
list            new_head            old_head
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            |                   |
            +-------------------+

5.3. Breaking

pop_front应该与push_front具有相同的基本逻辑,但必须是向后的。 咱们试试吧:

pub fn pop_front(&mut self) -> Option<T> {
	// 需要取出old_head,确保它是 -2
  self.head.take().map(|old_head| {	// -1 old_head
    match old_head.borrow_mut().next.take() {
      Some(new_head) => {	// -1 new_head
        // 非空list
        new_head.borrow_mut().prev.take();	// -1 old
        self.head = Some(new_head);	// +1 new
        // 总计:-2 old, +0 new
      }
      None => {
        // 空list
        self.tail.take();		// -1 old
        // 总计:-2 old, (no new)
      }
    }
    old_head.elem
  })
}
> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

确认 RefCells。 我猜要再来一次borrow_mut

pub fn pop_front(&mut self) -> Option<T> {
	self.head.take().map(|old_head|{
    match old_head.borrow_mut().next.take() {
      Some(new_head) => {
        new_head.borrow_mut().prev.take();
        self.head = Some(new_head);
      }
      None => {
        self.tail.take();
      }
    }
    old_head.borrow_mut().elem
  })
}
cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |   

Hrm… 借用mut只能得到一个&mut Node<T>,但我们不能提出这个节点!

我们需要一些能把RefCell<T>转换成T的东西。让我们看看文档中有没有类似的东西。

fn into_inner(self) -> T

Consumes the RefCell, returning the wrapped value.

这看起来很有希望!

old_head.into_inner().elem
> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

啊,见鬼。into_inner想要将RefCell移出,但我们不能,因为它在Rc中。正如我们在前一章中看到的,Rc<T>只允许我们获得对其内部的共享引用。这是有道理的,因为这就是引用计数指针的全部意义:它们是共享的!

当我们想要为引用计数列表实现Drop时,这是一个问题,解决方案是相同的:Rc::try_unwrap,它将一个Rc的内容移出,如果它的refcount是1。

Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::unwrap返回一个Result<T, Rc<T>>Result基本上是一个通用Option,其中None情况下有相关的数据。在本例中,您试图展开的Rc。因为我们不关心它失败的情况(如果我们正确地编写了程序,它必须成功),所以我们只对它调用unwrap

无论如何,让我们看看接下来我们会遇到什么编译错误(让我们面对它,肯定会有一个)。

> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

啊。为Result进行unwrap解包要求可以调试打印错误情况。RefCell<T>仅在T实现Debug时才实现。Node没有实现调试。

我们不这样做,而是通过okResult转换为Option来解决这个问题:

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
cargo build

是的。我们成功了。

我们实现了pushpop

  1. list.head = None, list.tail = None

    list
    +-------+      
    | head <----+--+-------+
    +-------|   |  +  None |
    | tail <----+| +-------+
    +-------+      
    
  2. list有一个链表

    list
    +-------+      new_head
    | head <----+--+--------+     +-------+
    +-------|   |  |  prev <----+-+  None |
    | tail <----+  +--------|   | +-------+
    +-------+      |  next <----+
                   +--------+
                   |  elem  |
                   +--------+
    
  3. list有多个链表

            +-------------------+
list        |   old_head        |   new_head
+-------+   |   +--------+      +---+--------+   +--+-------+
| &head<----+   |  prev  |      |   |  prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next  |      |   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

让我们通过旧的stack basic来进行测试(因为这是我们到目前为止所实现的所有内容)

#[cfg(test)]
mod test {
	use super::List;
  
  #[test]
  fn baiscs() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);
  }
}

现在我们可以正确地从列表中删除东西,我们可以实现Drop。这一次Drop在概念上更有趣一些。以前我们费心为栈实现Drop只是为了避免无限递归,现在我们需要实现Drop来让任何事情发生。

Rc不能处理循环。如果有一个循环,所有的东西都会让其他的东西保活。事实证明,一个双链表只是一个由小循环组成的大链!因此,当我们删除我们的列表,两个末端节点的refcounts会被减为1.…然后什么也不会发生。好吧,如果我们的列表只包含一个节点,我们就可以了。但理想情况下,如果一个列表包含多个元素,它也应该正常工作。也许这只是我的想法。

正如我们所看到的,删除元素有点痛苦。所以最简单的方法就是一直弹出直到没有:

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    while self.pop_front().is_some() {}
  }
}

(我们其实可以使用可变堆栈来实现这一点,但捷径是为那些理解事物的人准备的!)

我们可以看看pushpop的反向版本的实现,但它们只是复制-粘贴作业,我们将在本章后面讨论。现在让我们看看更有趣的东西

5.4. Peek

好了,我们通过了pushpop。不瞒你说,我当时有点激动。编译时的正确性是一种致命的毒药。

让我们做一些简单的事情来冷静一下:让我们先实现peek_front

list            new_head            old_head
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

这在以前总是很容易的。还是很简单,对吧

事实上,我想我可以直接复制粘贴

pub fn peek_front(&self) -> Option<&T> {
  self.head.as_ref().map(|node| &node.elem)
}

等一下。 这次不是

pub fn peek_front(&self) -> Option<&T> {
  self.head.as_ref().map(|node| {
    // borrow!!!
    &node.borrow().elem
  })
}
> cargo build

error[E0515]: 不能返回引用临时值的值
  --> src/fourth.rs:66:13
   |
66 |             &node.borrow().elem
   |             ^   ----------^^^^^
   |             |   |
   |             |   这里创建的临时值
   |             |
   |             返回一个引用当前函数所拥有的数据的值

这与我们的单链表完全相同。为什么事情会不同。为什么。

答案就是这一章的全部寓意:RefCell让一切都悲伤。到目前为止,RefCell一直是个讨厌的东西。现在他们将成为一场噩梦。

那么到底发生了什么呢?要理解这一点,我们需要回到borrow的定义

fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>

layout节我们说:

RefCell并不是静态地强制它们,而是在运行时强制它们。如果你违反了规则,RefCell就会panic,让程序崩溃。为什么它返回这些RefRefMut的东西?它们的行为和Rc很像,只是借用而已。而且他们会一直借用RefCell直到他们超出了范围。

我们稍后会讲到

现在就是稍后

RefRefMut分别实现了DerefDerefMut,所以对于大多数意图和目的来说,它们的行为与&T&mut T完全相同。然而,由于这些特性的工作方式,返回的引用与Ref的生命期有关,而不是实际的RefCell。这就意味着,只要我们把引用留在身边,Ref就必须一直存在。

事实上,这对于正确性来说是必要的。当一个Ref被丢弃时,它会告诉RefCell它不再被借用了。因此,如果我们确实设法保持我们的引用比 Ref 存在的时间更长,我们可以在引用还在运行的时候得到一个 RefMut,并完全将Rust的类型系统破坏了一半。

那么我们现在的情况是什么呢?我们只想返回一个引用,但我们需要把Ref这个东西留在身边。但只要我们从peek中返回引用,函数就结束了,而Ref就超出了作用域。

😖

据我所知,我们在这里完全是死水一潭。您不能像那样完全封装RefCells的使用。但是…如果我们放弃完全隐藏实现细节呢?如果我们返回Ref

pub fn peek_front(&self) -> Option<Ref<T>> {
  self.head.as_ref().map(|node| node.borrow())
}
> cargo build

error[E0412]: cannot find type `Ref` in this scope
  --> src/fourth.rs:63:40
   |
63 |     pub fn peek_front(&self) -> Option<Ref<T>> {
   |                                        ^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
   |
1  | use core::cell::Ref;
   |
1  | use std::cell::Ref;
   |

必须导入一些东西

use std::cell::{Ref, RefCell};
> cargo build

error[E0308]: mismatched types
  --> src/fourth.rs:64:9
   |
64 | /         self.head.as_ref().map(|node| {
65 | |             node.borrow()
66 | |         })
   | |__________^ expected type parameter, found struct `fourth::Node`
   |
   = note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
              found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`

嗯…这是正确的。我们有一个Ref<Node<T>>,但是我们想要一个Ref<T>。我们可以放弃所有封装的希望,直接返回这个。我们还可以让事情变得更加复杂,将Ref<Node<T>>包装为新的类型,只公开对&T的访问。

这两种选择都有点蹩脚。

相反,我们要深入下去。让我们找点乐子。我们的乐趣来源就是这个野兽

map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
	where F: FnOnce(&T) -> &U,
				U: ?Sized

为借来的数据的一个组件创建一个新的Ref

是的:就像你可以在一个Option上进行map映射一样,你可以也映射一个Ref

我肯定有人在某处真的很兴奋,因为单子或任何东西,但我不关心任何这些。我也不认为这是一个适当的单子,因为没有类似的情况,但我离题了。

这很酷,这对我来说才是最重要的。我需要这个:

pub fn peek_front(&self) -> Option<Ref<T>> {
  self.head.as_ref().map(|node|{
    Ref::map(node.borrow(), |node| &node.elem)
  })
}
> cargo build

让我们通过从堆栈中添加测试来确保这是有效的。我们需要做些调整来处理Ref并未实现比较这一事实。

#[test]
fn peek() {
	let mut list = List::new();
  assert!(list.peek_front().is_none());
  list.push_front(1);
  list.push_front(2);
  list.push_front(3);
  
  assert_eq!(&*list.peek_front().unwrap(), &3);
}

5.5. Symmetric Cases

好了,让我们把组合对称现实

list
+-------+          +-------+
| &head<-----+------| None |
+-------|    |     +-------+
| &tail<-----+
+-------+

list
+-------+   +---+--------+--+   +------------+   +--+-------+
| &head<----+   |  prev  |  +--------> prev  |   |  |  None |
+-------|       +--------+      |   +--------+   |  +-------+
| &tail<----+   |  next <-------+   |  next <----+
+-------+   |   +--------+      |   +--------+
            |   |  elem  |      |   |  elem  |
            |   +--------+      |   +--------+
            +-------------------+

我们只需要做一些基本的文本替换

tail <-> head
next <-> prev
front -> back

哦,我们还需要添加_mut变体以进行peek查询

pub fn push_back(&mut self, elem: T) {
  let new_tail = Node::new(elem);
  match self.tail.take() {
    Some(old_tail) => {
      old_tail.borrow_mut().next = Some(new_tail.clone());
      new_tail.borrow_mut().prev = Some(old_tail);
      self.tail = Some(new_tail);
    }
    None => {
      self.head = Some(new_tail.clone());
      self.tail = Some(new_tail);
    }
  }
}

pub fn pop_back(&mut self) -> Option<T> {
  self.tail.take().map(|old_tail| {
    match old_tail.borrow_mut().prev.take() {
      Some(new_tail) => {
        new_tail.borrow_mut().next.take();
        self.tail = Some(new_tail);
      }
    	None => {
        self.head.take();
      }      
    }
    Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
  })
}

pub fn peek_back(&self) -> Option<Ref<T>> {
  self.tail.as_ref().map(|node| {
    Ref::map(node.borrow(), |node| &node.elem)
  })
}

pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
  self.tail.as_ref().map(|node|{
    RefMut::map(node.borrow_mut(), |node| &mut node.elem)
  })
}

pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
  self.head.as_ref().map(|node|{
    RefMut::map(node.borrow_mut(), |node| &mut node.elem)
  })
}

大量充实我们的测试

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();
        assert_eq!(list.pop_front(), None);

        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        list.push_front(4);
        list.push_front(5);

        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        // ----- back ------
        assert_eq!(list.pop_back(), None);

        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));

        list.push_back(4);
        list.push_back(5);

        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(4));
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }
}

还有没有一些情况下我们没有测试? 大概有。

组合空间确实在这里爆炸了。

我们的代码至少没有明显的错误。

> cargo test

好了。复制粘贴是最好的编程方式。

5.6. Iteration

像往常一样,IntoIter将是最简单的。只需要包装栈并调用pop

pub struct IntoIter<T>(List<T>);

impl<T> List<T> {
  pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
  }
}

impl<T> Iterator for IntoIter<T> {
  type Item = T;
  fn next(&mut self) -> Option<T> {
    self.0.pop_front()
  }
}

但我们有了一个有趣的新发展。在此之前,我们的列表只有一个“自然”迭代顺序,而Deque本质上是双向的。从前到后有什么特别之处?如果有人想要在另一个方向迭代该怎么办?

对于这个问题,Rust实际上有一个答案:DoubleEndedIterator DoubleEndedIterator 继承自Iterator(意味着所有DoubleEndedIterator 都是迭代器),并且需要一个新方法:next_back。它与next具有完全相同的签名,但它应该从另一端产生元素。DoubleEndedIterator的语义对我们来说非常方便:迭代器变成了deque容器。您可以从前面和后面使用元素,直到两端收敛,此时迭代器为空。

就像Iteratornext一样,事实证明next_back并不是DoubleEndedIterator的用户真正关心的东西。相反,这个接口最好的地方在于它公开了rev方法,它将迭代器包装起来,生成一个新迭代器,以相反的顺序生成元素。它的语义相当直接:在反向迭代器上调用next就是调用next_back

因为我们已经是deque了,提供这个API很容易:

impl<T> DoubleEndedIterator for IntoIter<T> {
  fn next_back(&mut self) -> Option<T> {
    self.0.pop_back()
  }
}

我们来测试一下:

#[test]
fn into_iter() {
  let mut list = List::new();
  list.push_front(1); list.push_front(2); list.push_front(3);
  
  let mut iter = list.into_iter();
  assert_eq!(iter.next(), Some(3));
  assert_eq!(iter.next_back(), Some(1));
  assert_eq!(iter.next(), Some(2));
  assert_eq!(iter.next_back(), None);
  assert_eq!(iter.next(), None);
}
> cargo test

好极了!

Iter

Iter就不那么宽容了。我们又得应付那些可怕的Ref了!由于引用Refs,我们不能像以前那样存储&Node。相反,让我们尝试存储Ref<Node>s

pub struct Iter<'a T>(Option<Ref<'a, Node<T>>>);

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter(self.head.as_deref().map(|node| node.borrow()))
  }
}

到目前为止,一切都好。实现next会有点麻烦,但我认为它与旧堆栈IterMut的基本逻辑相同,但有额外的RefCell疯狂:

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = Ref<'a, T>;
  fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref: Ref<Node<T>> |{
      self.0 = node_ref.next: Option<Rc<RefCell<Node<T>>>>
               .as_ref(): Option<&Rc<RefCell<Node<T>>>>
               .map(|head: &Rc<RefCell<Node<T>>>| head: &Rc<RefCell<Node<T>>>
                    .borrow(): Ref<Node<T>>);
      Ref::map(node_ref, |node| &node.elem)
    })
  }
}
cargo build

error[E0521]: 借用的数据逃逸到闭包之外
   --> src/fourth.rs:155:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` 是在这里声明的,在闭包体之外
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   -------- 借用仅在闭包体中有效
    |             |
    |             对' node ref '的引用在这里逃逸出了闭包体

error[E0505]: 无法移出' node_ref ',因为它是借来的
   --> src/fourth.rs:156:22
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- 生命期参数 “'1 出现在 self 的类型中
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ------   -------- 这里出现`node_ref`的借用
    |             |
    |             赋值要求 "node_ref ""’1"借用
156 |             Ref::map(node_ref, |node| &node.elem)
    |                      ^^^^^^^^ 移出`node_ref`发生在这里

该死

node_ref的寿命不够长。不像一般的引用,Rust不允许我们像那样把引用Refs分开。我们从head.borrow()中得到的Ref只允许存在与node_ref相同的时间,但是我们最终在Ref::map调用中丢弃了它。

巧合的是,在我写这个的时候,我们想要的函数实际上两天前就稳定下来了。这意味着它还需要几个月的时间才能发布稳定版。因此,让我们继续使用最新的夜间构建:

pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
	F: FnOnce(&T) -> (&U, &V),
	U: ?Sized,
	V: ?Sized,

Woof,让我们试一试……

fn next(&mut self) -> Option<Self::Item> {
  self.0.take().map(|node_ref: Ref<Node<T>>| {
    let (next: Ref<Option<Rc<Ref<Node<T>>>>>, elem: Ref<T>) 
        = Ref::map_split(node_ref, |node: &Node<T>| {
      (&node.next, &node.elem)
    });
    self.0 = next.as_ref(): Option<&Rc<Ref<Node<T>>>>
             .map(|head: &Rc<Ref<Node<T>>>| head.borrow());
    elem
  })
}
cargo build
   Compiling lists v0.1.0 (/Users/ABeingessner/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:159:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
...
159 |             self.0 = next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   ---- borrow is only valid in the closure body
    |             |
    |             reference to `next` escapes the closure body here

恩。我们需要再次使用Ref::Map才能使生命期正确。 但是 Ref::Map 返回一个Ref,我们需要一个Option<Ref>,但是我们需要遍历Ref才能映射到我们的Option上…

长时间凝视远方

??????

fn next(&mut self) -> Option<Self::Item> {
  self.0.take().map(|node_ref: Ref<Node<T>>| {
    let (next, elem) = Ref::map_split(node_ref, |node| {
      (&node.next, &node.elem)
    });
    self.0 = if next.is_some() {
      Some(Ref::map(next: Ref<Option<Rc<RefCell<Node<T>>>>>, 
                   |next: &Option<Rc<RefCell<Node<T>>>>| 
            &**next
            .as_ref(): Option<&Rc<RefCell<Node<T>>>>
            .unwrap(): &Rc<RefCell<Node<T>>>
        		// &RefCell<Node<T>>
    ))} else {
      None
    };
    elem
  })
}
error[E0308]: mismatched types
   --> src/fourth.rs:162:22
    |
162 |                 Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
    |
    = note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
               found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`

哦。对的。有多个重叠的RefCells。我们在列表中走得越深,每个RefCell下的嵌套就越深。例如,我们需要维护一个Refs栈来代表我们所持有的所有未偿还的借用,因为如果我们停止查看某个元素,则需要减少它之前的每个RefCell上的借位计数……

我认为我们在这里无能为力。 这是一个死胡同。 让我们尝试摆脱RefCell

那我们的Rcs呢? 谁说我们需要存储引用? 为什么我们不能仅仅克隆整个Rc来在list中间找到一个很好的拥有者句柄?

pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
  pub fn iter(&self) -> Iter<T> {
    Iter(self.head.as_ref().map(|head| head.clone()))
  }
}

impl<T> Iterator for Iter<T> {
  type Item =

嗯…等等,我们现在返回什么? &TRef<T>

不,这些都没用……我们的Iter再也没有生命周期了!&TRef<T>都要求我们在进入next之前预先声明一些生命周期。但是我们从Rc中得到的任何东西都会借用Iterator……头……痛……aaaaaahhhhhh

也许我们可以…map……Rc……得到一个Rc<T>?这是答案吗?Rc的文档中似乎没有这样的内容。实际上有人做了个crate让你可以这么做。

但是,等等,即使我们这样做,也遇到了一个更大的问题:迭代器失效的可怕幽灵。 以前,我们完全不受迭代器失效的影响,因为Iter借用了列表list,使其完全不可变。 但是,如果我们的Iter产生的是Rcs,那么他们根本不会借用该列表! 这意味着人们可以在持有列表中的指针的同时在列表上调用pushpop

哦,上帝,那会有什么后果?

好吧,pushing其实是可以的。 我们的视野已经进入了该列表的某些子范围,并且该列表将增长到超出我们的视线。 没什么大不了的。

然而pop是另一回事。 如果他们在我们的范围外弹出元素,那应该还是可以的。 我们看不到那些节点,所以什么也不会发生。 但是,但是如果他们试图弹出我们指向的节点……一切都会崩溃! 特别是当他们去unwrap解包try_unwrap的结果时,它实际上将失败,并且整个程序将崩溃。

这其实是非常酷的。我们可以将大量内部自有指针添加到列表中,同时对其进行修改,直到他们试图删除我们指向的节点为止。即使我们没有得到悬空指针或其他东西,程序也肯定会崩溃。

但是在映射Rcs的基础上还要处理迭代器无效的问题,这似乎……很糟糕。 Rc<RefCell>真的让我们失望了。 有趣的是,我们经历了持久栈情况的反转。 在持久性堆栈努力获取数据所有权但每天都可以获取引用的地方,我们的列表在获得所有权方面没有问题,但却很难借出我们的引用。

虽然公平地说,但我们的大多数努力都围绕着希望隐藏实现细节并拥有一个优雅的API来进行。 如果我们只是想到处传递Nodes,我们可以做到一切都很好。

哎呀,我们可以创建多个并发的IterMuts,这些IterMuts在运行时进行了检查,以确保不可变地访问同一元素!

实际上,这种设计更适合于内部数据结构,因为这些数据结构永远不会被API的用户看到。内部可变性对于编写安全的应用程序非常有用。没有比这安全的库了。

总之,我放弃了IterIterMut。我们可以做,但是……唉…….

5.7. Final Code

好了,这就是在Rust中实现一个100%安全的双链表。它的实现是个噩梦,泄露了实现细节,而且不支持几个基本操作。

但是,它是存在的。

哦,我猜它也被RcRefCell之间大量的“不必要的”运行时检查所困扰。我把不必要的放在引号里,因为它们实际上是必要的,以确保整个是安全的。我们遇到了一些地方,这些检查实际上是必要的。双向链表有一个可怕的混乱的别名和所有权故事。

尽管如此,这也是我们可以做的事情。尤其是当我们不在乎将内部数据结构暴露给用户的时候。

从现在开始,我们将专注于硬币的另一面:通过让我们的实现变得不安全来夺回所有的控制权


#![allow(unused_variables)]
fn main() {
use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
    prev: Link<T>,
}


impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_head.clone());
                new_head.borrow_mut().next = Some(old_head);
                self.head = Some(new_head);
            }
            None => {
                self.tail = Some(new_head.clone());
                self.head = Some(new_head);
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_tail.clone());
                new_tail.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_tail);
            }
            None => {
                self.head = Some(new_tail.clone());
                self.tail = Some(new_tail);
            }
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev.take();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

    pub fn peek_front(&self) -> Option<Ref<T>> {
        self.head.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop_front(), None);

        // Populate list
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(3));
        assert_eq!(list.pop_front(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_front(4);
        list.push_front(5);

        // Check normal removal
        assert_eq!(list.pop_front(), Some(5));
        assert_eq!(list.pop_front(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_front(), Some(1));
        assert_eq!(list.pop_front(), None);

        // ---- back -----

        // Check empty list behaves right
        assert_eq!(list.pop_back(), None);

        // Populate list
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(3));
        assert_eq!(list.pop_back(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push_back(4);
        list.push_back(5);

        // Check normal removal
        assert_eq!(list.pop_back(), Some(5));
        assert_eq!(list.pop_back(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop_back(), Some(1));
        assert_eq!(list.pop_back(), None);
    }

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

        list.push_front(1); list.push_front(2); list.push_front(3);

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push_front(1); list.push_front(2); list.push_front(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next_back(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next_back(), None);
        assert_eq!(iter.next(), None);
    }
}
}

6. 不安全的单链队列

好吧,引用计数的内部可变性有点失控了。Rust当然不会真的希望你做这种事吧?嗯,是也不是。RcRefcell可以很好地处理简单的情况,但它们可能会变得很笨重。特别是当你想隐藏它的发生时。 一定有更好的方法!

在这一章中,我们将回到单链表,并实现一个单链路队列,以了解原始指针和Unsafe Rust

让我们添加一个名为 fifth.rs 的新文件

// in lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;

我们的代码主要是由second派生的。因为在链表的世界里,队列基本上是堆栈的扩充。不过,我们还是要从头开始,因为我们还需要解决一些关于布局之类的基本问题。

##6.1. Layout

那么,单链路的队列是什么样的呢?好吧,当我们有一个单链栈时,我们推到列表的一端,然后从同一端弹出。栈和队列的唯一区别是,队列会从另一端弹出。所以从我们的栈实现来看,我们有:

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

stack push X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

stack pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

为了创建一个队列,我们只需要决定将哪个操作移动到列表的末尾:push,还是pop?由于我们的列表是单链的,我们实际上可以用相同的努力将任意一个操作移动到最后。

要将push移动到末尾,只需一直走到None,并使用新元素将其设置为Some

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

flipped push X:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

要将pop移至末尾,我们只需要一直走到None之前的节点,然后将其取走:

input list:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
  
flipped pop:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

我们可以在今天做完这一切,然后收手,但那会很糟糕! 这两种操作都会走过整个列表。有些人会认为,这样的队列实现确实是一个队列,因为它公开了正确的接口。然而我认为,性能保证也是接口的一部分。我并不关心精确的渐变边界,但在乎“快”与“慢”的区别。队列保证了pushpop是快速的,而遍历整个列表肯定不是快速的。

一个关键的观察是,我们浪费了大量的工作,重复做同样的事情。我们能记住这些工作吗? 为什么,是的!我们可以存储一个指向列表末尾的指针,然后直接跳到那里就可以了!

事实证明,只有pushpop的一种反转才能使用此功能。 要反转pop,我们必须将“tail”指针向后移动,但是由于我们的列表是单链链接,因此我们无法有效地做到这一点。 如果我们反转push,我们只需要向前移动“head”指针,这很容易。

list
+------+     +------+
| head <---+-+ None |
+------+   | +------+
| tail <---+
+------+
list
+------+   +--+------+   +--+------+
| head <---+  | elem |   |  | elem |
+------+      +------+   |  +------+
| tail <---+  | next <---+  | next |
+------+   |  +------+   |  +------+
           +-------------+

让我们试一试:

use std::mem;

pub struct List<T> {
  head: Link<T>,
  tail: Link<T>, // NEW!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
  
  pub fn push(&mut self, elem: T) {
    let new_tail = Box::new(Node {
      elem,
      // 当您push到tail时,next永远是None
      next: None,
    });
    // 换 old_tail 指向 new_tail
    let old_tail = mem::replace(&mut self.tail, Some(new_tail));
    
    match old_tail {
      Some(mut old_tail) => {
        // 如果 old_tail 存在,更新old_tail指向new_tail
        old_tail.next = Some(new_tail);
      }
      None => {
        // 否则,更新head指向new_tail
        self.head = Some(new_tail);
      }
    }
  }
}

我现在对 impl 的细节讲得比较快,因为我们对这种事情应该很熟悉。并不是说你一定要期望第一次就能产生这样的代码,我只是跳过了一些我们以前要处理的试错。其实我在写这段代码的时候犯了一大堆错误,我就不展示了。你只能看到我漏掉一个mut;这么多次才会停止指导。别担心,我们会看到很多其他的错误信息!

> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move

该死!

使用了转移后的值:new_tail

Box并没有实现Copy,所以我们不能随便把它分配到两个位置。更重要的是,Box拥有它所指向的东西,当它被丢弃时,会尝试释放它。如果我们的push实现编译后,就会把列表的尾部双倍释放! 实际上,就像我们写的那样,我们的代码会在每次push时释放 old_tail。呀!🙀

我们知道如何创建一个非所有者指针。这只是一个参考!

pub struct List<T> {
  head: Link<T>,
  tail: Option<&mut Node<T>>,
}
type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // When you push onto the tail, your next is always None
            next: None,
        });

        // Put the box in the right place, and then grab a reference to its Node
        // 将box放在正确的位置,然后获取对其Node的引用
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // If the old tail existed, update it to point to the new tail
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // Otherwise, update the head to point to it
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        self.tail = new_tail;
    }
}

这没什么难的。和前面的代码基本思路一样,只是我们使用了一些隐式返回的好处,从我们塞入实际Box的地方提取尾部引用。

> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter

对了,我们需要在类型生命周期中提供引用。嗯…这个引用的生命周期是多少?这看起来像IterMut,对吧?让我们尝试一下我们对IterMut所做的,只是添加一个泛型的'a'

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // NEW!
}

impl<'a, T> List<'a, T> {
  ...
}
cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting 
error[E0495]: 由于需求冲突,无法推断出自动引用的适当生命周期
requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_deref_mut()
   |                           ^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
注意:首先,生命周期不能超过18:5在方法体上定义的匿名生命周期#1…
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // When you push onto the tail, your next is always None
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
注意:……所以引用不会比借来的内容更长久
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_deref_mut()
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
注意:但是,生命周期必须在13:6 impl上定义的生命周期 'a 内有效。
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
   = 注意:……这样表达式就可以赋值了
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>

哇,那是一条非常详细的错误消息。 这有点令人担忧,因为这表明我们正在做的事情确实搞砸了。 这是一个有趣的部分:

生命周期必须在impl上定义的生命周期a内有效

我们是从self借来的,但是编译器希望我们的生命期和'a一样长,如果我们告诉它self可以持续那么长时间呢?

pub fn push(&'a mut self, elem: T) {
  ...
}
cargo build

warning: field is never used: `elem`
 --> src/fifth.rs:9:5
  |
9 |     elem: T,
  |     ^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

哦,嘿,成功了!太棒了!

我们也来完成 pop

pub fn pop(&'a mut self) -> Option<T> {
  // 获取list的当前head
  self.head.take().map(|head| {
    let head = *head;
    self.head = head.next;
    // 如果我们的“head”没有,请确保将“tail”设置为“None”
    if self.head.is_none() {
      self.tail = None;
    }
    head.elem
  })
}

并为此编写一个快速测试:

mod test {
  use super::List;
  #[test]
  fn basics() {
    let mut list = List::new();
    
    assert_eq!(list.pop(), None);
    
    list.push(1); list.push(2); list.push(3);
    
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), Some(2));
    
    list.push(4); list.push(5);
    
    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(4));
    
    // check exhaustion
    assert_eq!(list.pop(), Some(5));
    assert_eq!(list.pop(), None);
  }
}
cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** WAY MORE LINES OF ERRORS **

....

error: aborting due to 11 previous errors

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

哦~ 我的天哪。

编译者对我们的吐槽并没有错。我们只是犯了一个Rust的大罪:我们在自己的内部存储了一个对自己的引用。不知何故,我们设法说服Rust,这在我们的pushpop实现中完全是有意义的(我对此感到非常震惊)。我相信原因是Rust还不能从单纯的pushpop中判断出引用是属于我们自己的——或者更确切地说,Rust根本就没有这个概念。引用到自己身上失效只是一种紧急的行为。

当我们尝试使用我们的列表时,一切很快就崩溃了。当我们调用pushpop时,我们会立即将对自己的引用存储在我们自己中并陷入困境。我们实际上是在借用自己。

我们的pop实现暗示了为什么这可能真的很危险

// ...
if self.head.is_none() {
    self.tail = None;
}

如果我们忘了这样做呢?那我们的tail就会指向某个被从列表中删除的节点。这样的节点会被立即释放,我们会有一个悬空的指针,而Rust本来应该保护我们的。

而事实上,Rust正在保护我们免受这种危险。只是以一种非常… 迂回的方式。

所以,我们能做些什么? 回到Rc <RefCell>>地狱?

行行好,不行

不,相反,我们将偏离常规,使用原始指针。我们的布局是这样的:

pub struct List<T> {
  head: Link<T>,
  tail: *mut Node<T>, // 危险 Danger
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>,
}

就是这样。真的别跟我说这些没用的引用计数、动态借用检查的废话

硬核、没有检查的指针才是王道~

让我们成为C语言的人吧,让我们回到C语言一整天。

我准备好了。

你好,unsafe

6.2. Unsafe

这是一个严肃,重大,复杂和危险的话题。 这是如此严重,以至于我写了另一本书

简而言之,只要你允许调用其他语言,每一种语言实际上都是不安全的,因为你可以让C做任意错误的事情。是的:Java, Python, Ruby, Haskell…在外部函数接口(FFI)面前,每个人都非常不安全。

Rust通过将自己分成两种语言来接受这个事实。安全Rust和不安全Rust。到目前为止,我们只使用了安全Rust。它是完全100%安全的……除了它可以FFI成不安全的Rust

不安全Rust是安全Rust的超级集。它的语义和规则与安全Rust完全相同,只是允许你做一些额外的事情,这些事情非常不安全,可能会导致可怕的未定义行为,困扰着C。

这是一个非常大的话题有很多有趣的特例。我真的不想太深入(好吧,我是想的。我读过那本书)。这没关系,因为使用链表,我们实际上可以忽略几乎所有这些。

我们将使用的主要不安全工具是原始指针。原始指针基本上是C的指针。它们没有固有的别名规则。他们没有生命期。它们可以是null。它们可以悬挂着。它们可以指向未初始化的内存。它们可以转换为整数,也可以从整数转换为指针。它们可以被强制转换指向另一种类型。可变性吗?转换它。几乎所有的东西都可以,这意味着几乎所有的东西都可以出错。

这是一些不好的东西,说实话,你永远不用去碰这些东西,你会活得更开心。不幸的是,我们想写链表,而链表是可怕的。这意味着我们将不得不使用不安全的指针。

原始指针有两种:*const T*mut T。它们的意思是来自C的const T *T *,但我们实际上并不关心C认为它们的含义是什么。 您只能将* const T解引用到&T,但是就像变量的可变性一样,这只是防止不正确使用的纱布。 最多只是意味着您必须先将* const强制转换为* mut。但是如果你没有修改指针的引用的权限,你就会有麻烦了。

无论如何,当我们编写一些代码时,我们会对此有更好的感觉。 目前,

*mut T = &unchecked mut T

6.3. Basics

好了,回到最基本的bascis。我们如何构造我们的列表

之前,我们是这样写的:

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: None }
  }
}

但我们不再对尾部使用Option了

> cargo build

error[E0308]: mismatched types
  --> src/fifth.rs:15:34
   |
15 |         List { head: None, tail: None }
   |                                  ^^^^ expected *-ptr, found enum `std::option::Option`
   |
   = note: expected type `*mut fifth::Node<T>`
              found type `std::option::Option<_>`

我们可以使用Option,但是与Box不同,* mut是可为空的。 这意味着它不能从空指针优化中受益。 相反,我们将使用null来表示None

那么我们如何获得一个空指针呢? 有几种方法,但是我更喜欢使用std::ptr::nul_mut()。 如果需要,您也可以使用 0 as *mut _,但这似乎太混乱了。

use std::ptr;

// 定义 ...

impl<T> List<T> {
  pub fn new() -> Self {
    List { head: None, tail: ptr::null_mut() }
  }
}
> cargo build
** 一堆字段未使用的警告 **

嘘~ ,编译器,我们很快就会使用它们。

好了,我们继续写push。这一次,我们不是在插入后抓取一个Option<&mut Node<T>>,而是马上抓取一个*mut Node<T>Box的内部。我们知道我们可以这样做,因为Box的内容有一个稳定的地址,即使我们移动Box。当然,这样做是不安全的,因为如果我们直接丢掉这个Box,就会有一个指向已释放内存的指针。

我们如何从普通指针制作原始指针? 威逼! 如果将变量声明为原始指针,则普通引用将强制进入该变量:

let raw_tail: *mut _ = &mut *new_tail;

我们需要的信息都有了。我们可以将我们的代码近似地翻译成以前的参考版本

pub fn push(&mut self, elem: T) {
  let mut new_tail = Box::new(Node {
    elem,
    next: None,
  });
  let raw_tail: *mut _ = &mut *new_tail;
  
  // .is_null 检查null,等同于检查None
  if !self.tail.is_null() {
    self.tail.next = Some(new_tail);
  } else {
    self.head = Some(new_tail);
  }
  self.tail = raw_tail;
}
> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             self.tail.next = Some(new_tail);
   |             ----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

嗯?我们有一个指向Node的指针,为什么我们不能得到next字段?

当你用原始指针的时候,Rust有点混蛋。为了访问原始指针的内容,它坚持要手动对其进行解引用,因为这是一个非常不安全的操作。我们来做一下:

*self.tail.next = Some(new_tail);
> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             *self.tail.next = Some(new_tail);
   |             -----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; try dereferencing it: `(*self.tail).next`

呃~~ 运算优先级~~

(*self.tail).next = Some(new_tail);
> cargo build

error[E0133]: dereference of raw pointer is unsafe and requires unsafe function or block
  --> src/fifth.rs:31:13
   |
31 |             (*self.tail).next = Some(new_tail);
   |             ^^^^^^^^^^^^^^^^^ dereference of raw pointer
   |
   = note: raw pointers may be NULL, dangling or unaligned; they can violate aliasing rules and cause data races: all of these are undefined behavior

就不应该这么难!!!

还记得我说不安全的Rust就像一个FFI语言的安全Rust吗?编译器想让我们显式地界定我们在哪放置这个FFI。我们有两个选择。首先,我们可以将整个函数标记为不安全的,在这种情况下,它成为不安全的Rust函数,只能在不安全的上下文中调用。这并不好,因为我们希望我们的列表是安全使用的。其次,我们可以在函数内部编写一个不安全的块,来划定FFI边界。这声明了整个函数是安全的。我们来做这个:

pub fn push(&mut self, elem: T) {
  let mut new_tail = Box::new(Node {
    elem,
    next: None,
  });
  let raw_tail: *mut _ = &mut *new_tail;
  
  if !self.tail.is_null() {
    unsafe{
      (*self.tail).next = Some(new_tail);
    }
  } else {
    self.head = Some(new_tail);
  }
}
> cargo build
编译通过

耶!

有趣的是,到目前为止,这是我们唯一写不安全块的地方。但我们到处都是原始指针,这是怎么回事?

事实证明,在不安全的问题上,Rust是一个庞大的规则学究。我们很合理地想要最大化安全Rust程序集,因为这些程序我们可以更有信心。为了达到这个目的,Rust小心翼翼地为不安全划出了最小的表面积。请注意,我们使用原始指针的所有其他地方都是对它们进行赋值,或者只是观察它们是否为空。

如果你从来没有解引用过原始指针那是完全安全的事情。您只是读写一个整数!使用原始指针唯一可能遇到麻烦的情况是对它进行解引用。所以Rust说只有这个操作是不安全的,其他一切都是完全安全的。

超级学究。但技术上正确的。

然而,这引发了一个有趣的问题:尽管我们应该用不安全块来界定不安全块的范围,但它实际上取决于在块之外建立的状态。甚至是在函数之外!这就是我所说的不安全污染。

一旦你在一个模块中使用了unsafe,整个模块就会被unsafe污染。为了确保不安全代码的不变性得到维护,必须正确地编写所有内容。

由于隐私的关系,这种污染是可以处理的。在我们的模块之外,所有的struct字段都是完全私有的,所以其他人不能以任意的方式干扰我们的状态。只要我们公开的api组合没有导致糟糕的事情发生,就外部观察者而言,我们所有的代码都是安全的!实际上,这和FFI的情况没有什么不同。只要暴露出一个安全的接口,没有人需要关心某个python数学库是否会外壳到C语言。

不管怎样,我们来看看pop,它和参考版本几乎一字不差

pub fn pop(&mut self) -> Option<T> {
  self.head.take().map(|head| {
    let head = *head;
    self.head = head.next;
    
    if self.head.is_none() {
      self.tail = ptr::null_mut();
    }
    head.elem
  })
}

再一次,我们看到了另一种情况,即安全是有状态的。 如果我们无法在该函数中使尾指针为零,那么我们将看不到任何问题。 但是,随后的push调用将开始写入悬空的tail

让我们来测试一下

#[cfg(test)]
mod test {
  use super::List;
  #[test]
  fn basics() {
    let mut list = List::new();
    assert_eq!(list.pop(), None);
    list.push(1); list.push(2); list.push(3);
    
    assert_eq!(list.pop(), Some(1));
    assert_eq!(list.pop(), Some(2));
    
    list.push(4);
    list.push(5);
    
    assert_eq!(list.pop(), Some(3));
    assert_eq!(list.pop(), Some(4));
    
    assert_eq!(list.pop(), Some(5));
    assert_eq!(list.pop(), None);
    
    list.push(6);
    list.push(7);
    
    assert_eq!(list.pop(), Some(6));
    assert_eq!(list.pop(), Some(7));
    assert_eq!(list.pop(), None);
  }
}

这只是堆栈测试,但是把预期的pop结果翻转过来了。我还在最后增加了一些额外的步骤,以确保pop中的尾指针损坏情况不会发生。

> cargo test

God Star!

6.4. Extras

现在已经编写了pushpop,其他所有内容与堆栈情况完全相同。 只有更改列表长度的操作才需要真正担心尾指针。

因此,让我们从第二个列表中窃取所有内容(请确保反转预期的测试输出):

// ...

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
  next: Option<&'a Node<T>>,
}
pub struct IterMut<'a, T> {
  next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
  // ...
  
  pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }
  
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_ref().map(|node| &mut node.elem)
  }
  
  pub fn into_iter(self) -> IntoIter<T> {
    IntoIter(self)
  }
  
  pub fn iter(&self) -> Iter<'_, T> {
    Iter { next: self.head.as_deref() }
  }
  
  pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
  }
}

impl<T> Drop for List<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_node.next.take();
    }
  }
}

impl<T> Iterator for IntoIter<T> {
  type Item = T;
  fn next(&mut self) -> Option<Self::Item> {
    self.0.pop()
  }
}

impl<'a, T> Iterator for Iter<'a, T> {
  type Item = &'a T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.map(|node| {
      self.next = node.next.as_deref();
      &node.elem
    })
  }
}

impl<'a, T> Iterator for IterMut<'a, T> {
  type Item = &'a mut T;
  fn next(&mut self) -> Option<Self::Item> {
    self.next.take().map(|node| {
      self.next = node.next.as_deref_mut();
      &mut node.elem
    })
  }
}

#[cfg(test)]
mod test {
    // ...

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}
> cargo test

大声疾呼的复制粘贴编程。

起初我以为用IntoIter会弄乱,但我们还是很方便地按迭代顺序弹出结果了!

6.5. Final Code

好了,通过一点点的不安全性,我们成功地在简单的安全队列上得到了线性时间上的改进,并且我们成功地重用了来自安全堆栈的几乎所有逻辑!我们也不需要编写任何疯狂的RcRefCell内容。

pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> Node<T> {
    pub fn new(elem: T) -> Box<Node<T>> {
        Box::new(Node { elem, next: None })
    }
}

impl<T> List<T> {
    pub fn new() -> Self {
        List {
            head: None,
            tail: std::ptr::null_mut(),
        }
    }

    pub fn push(&mut self, elem: T) {
        let mut new_tail = Node::new(elem);
        let raw_tail: *mut _ = &mut *new_tail;

        if !self.tail.is_null() {
            unsafe {
                (*self.tail).next = Some(new_tail);
            }
        } else {
            self.head = Some(new_tail);
        }
        self.tail = raw_tail;
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            self.head = old_head.next;
            if self.head.is_none() {
                self.tail = std::ptr::null_mut();
            }
            old_head.elem
        })
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<T> {
        Iter {
            next: self.head.as_deref(),
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<T> {
        IterMut {
            next: self.head.as_deref_mut(),
        }
    }

    pub fn peek(&self) -> Option<&T> {
        self.head.as_ref().map(|old_head| &old_head.elem)
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        self.head.as_mut().map(|old_head| &mut old_head.elem)
    }
}

pub struct IntoIter<T>(List<T>);

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.head.take().map(|old_head| {
            self.0.head = old_head.next;
            old_head.elem
        })
    }
}
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|old_head| {
            self.next = old_head.next.as_deref();
            &old_head.elem
        })
    }
}
pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.take().map(|old_head| {
            self.next = old_head.next.as_deref_mut();
            &mut old_head.elem
        })
    }
}

#[cfg(test)]
mod test {
    use super::List;
    #[test]
    fn basics() {
        let mut list = List::new();

        // Check empty list behaves right
        assert_eq!(list.pop(), None);

        // Populate list
        list.push(1);
        list.push(2);
        list.push(3);

        // Check normal removal
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), Some(2));

        // Push some more just to make sure nothing's corrupted
        list.push(4);
        list.push(5);

        // Check normal removal
        assert_eq!(list.pop(), Some(3));
        assert_eq!(list.pop(), Some(4));

        // Check exhaustion
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), None);

        // Check the exhaustion case fixed the pointer right
        list.push(6);
        list.push(7);

        // Check normal removal
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1);
        list.push(2);
        list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }
}

7. 一个Ok但不安全的双链双端队列

不,我还没写完这本书!这并没有什么意义。 如果你真的想要更多的话,请阅读The Rustonomiconstd::collections::LinkedList的源代码

8. 一堆愚蠢的清单

好吧。就是这样。我们列了所有的清单。 哈哈, 不, 总是会有更多的清单 这一章是一个活生生的文档,讲述了更荒谬的链表,以及它们如何与Rust互动

  1. The Double Single
  2. TODO: BList?
  3. TODO: SkipList?
  4. TODO: std::channel? – That’s like another whole chapter. Or 3.

8.1. 双单链表

我们在处理双重链接列表时很费劲,因为它们的所有权语义很纠结:没有一个节点严格地拥有任何其他节点。然而我们之所以在这个问题上挣扎,是因为我们带来了我们对链接列表是什么的先入为主的概念。也就是说,我们假设所有的链接都是朝同一个方向走的。

相反,我们可以把列表分成两半:一个向左,一个向右:

// lib.rs
// ...
pub mod silly;
// silly1.rs
use second::List as Stack;

struct List<T> {
  left: Stack<T>,
  right: Stack<T>,
}

现在,我们有了一个通用列表,而不仅仅是一个安全堆栈。我们可以通过推入任意一个堆栈来向左或向右增长列表。我们还可以通过将值从一端弹出到另一端来“遍历”列表。为了避免不必要的分配,我们将复制安全堆栈的源码,以访问其私有详细信息

pub struct Stack<T> {
  head: Link<T>,
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
  elem: T,
  next: Link<T>
}

impl<T> Stack<T> {
  pub fn new() -> Self {
    Stack { head: None }
  }
  
  pub fn push(&mut self, elem: T) {
    let new_node = Box::new(Node {
      elem,
      next: self.head.take(),
    });
    self.head = Some(new_node);
  }
  
  pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|node| {
      let node = *node;
      self.head = node.next;
      node.elem
    })
  }
  
  pub fn peek(&self) -> Option<&T> {
    self.head.as_ref().map(|node| &node.elem)
  }
  
  pub fn peek_mut(&mut self) -> Option<&mut T> {
    self.head.as_mut().map(|node| &mut node.elem)
  }
}

impl<T> Drop for Stack<T> {
  fn drop(&mut self) {
    let mut cur_link = self.head.take();
    while let Some(mut boxed_node) = cur_link {
      cur_link = boxed_noded.next.take();
    }
  }
}

然后再重写pushpop

pub fn push(&mut self, elem: T) {
  let new_node = Box::new(Node{
    elem,
    next: None,
  });
  self.push_node(new_node);
}

fn push_node(&mut self, mut node: Box<Node<T>>) {
  node.next = self.head.take();
  self.head = Some(node);
}

pub fn pop(&mut self) -> Option<T> {
  self.pop_node().map(|node| node.elem)
}

fn pop_node(&mut self) -> Option<Box<Node<T>>> {
  self.head = node.next.take();
  node
}

现在我们可以做出我们的链表了:

pub struct List<T> {
  left: Stack<T>,
  right: Stack<T>,
}

impl<T> List<T> {
  fn new() -> Self {
    List { left: Stack::new(), right: Stack::new() }
  }
}

而且我们可以做一些常用的接口:

pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }

但最有趣的是,我们可以遍历:

pub fn go_left(&mut self) -> bool {
  self.left.pop_node().map(|node| {
    self.right.push_node(node);
  }).is_some()
}

pub fn go_right(&mut self) -> bool {
  self.right.pop_node().map(|node| {
    self.left.push_node(node);
  }).is_some()
}

我们在这里返回booleans只是为了方便表示我们是否真的成功移动。现在我们来测试一下这个宝贝:

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn walk_aboot() {
        let mut list = List::new();             // [_]

        list.push_left(0);                      // [0,_]
        list.push_right(1);                     // [0, _, 1]
        assert_eq!(list.peek_left(), Some(&0));
        assert_eq!(list.peek_right(), Some(&1));

        list.push_left(2);                      // [0, 2, _, 1]
        list.push_left(3);                      // [0, 2, 3, _, 1]
        list.push_right(4);                     // [0, 2, 3, _, 4, 1]

        while list.go_left() {}                 // [_, 0, 2, 3, 4, 1]

        assert_eq!(list.pop_left(), None);
        assert_eq!(list.pop_right(), Some(0));  // [_, 2, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(2));  // [_, 3, 4, 1]

        list.push_left(5);                      // [5, _, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
        assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]
        assert_eq!(list.pop_right(), Some(4));  // [_, 1]
        assert_eq!(list.pop_right(), Some(1));  // [_]

        assert_eq!(list.pop_right(), None);
        assert_eq!(list.pop_left(), None);

    }
}
> cargo test

这是手指数据结构的一个极端例子,我们在结构中保持了某种手指,因此可以支持在时间上对与手指距离成正比的位置进行操作。

我们可以对手指周围的列表进行非常快速的更改,但是如果我们要在离手指很远的地方进行更改,我们就必须一直走到那边去。我们可以通过将元素从一个堆栈转移到另一个堆栈来永久地走过去,或者我们可以用&mut暂时沿着链接走过去来进行更改。然而,&mut永远不能回到列表中去,而我们的手指可以。

附录

转换 函数
Option<T> -> Option<&T> Option::as_ref(&self) -> Option<&T>
Option<T> -> Option<&mut T> Option::as_mut(&self) -> Option<&mut T>
Option<T> -> Option<&<T as Deref>::Target> Option::as_deref(&self)
Option<T> -> Option<&mut <TasDeref>::Target> Option::as_deref_mut(&self)
Option<T> -> Option<U> Option::map(|node| node)
Option::and_then(|node| Some(node))
Option<T> -> None x = y.take()
x = mem::replace(&mut y, None)
Option<T> -> T Option::unwrap(self) -> T
Rc<T> -> Result<T, Rc<T>> / Ok<T> Rc::try_unwrap(x: Rc<T>)
Rc<RefCell<Node<T>>> -> &RefCell<Node<T>> x.as_deref()
RefCell<T> -> T RefCell::into_inner(self) -> T
Result<T> -> Option<T> Result::ok(self) -> Option<T>
Ref<T> -> Ref<U>/ Ref<Node<T>> -> Ref<U> Ref::map(Ref<T>, F) -> Ref<'_, U>
where F: FnOnce<&T> -> &U
Ref<T> -> &T Ref::map(Ref<T>, |x: &T| &x.elem) -> Ref<U>

match 表达式

match表达式在模式上产生分支。匹配的具体形式取决于模式。匹配表达式有一个检查表达式,它是要与模式进行比较的值。被审查者的表达和模式必须具有相同的类型。

匹配的行为不同,取决于检查对象表达式是位置表达式还是值表达式。如果检查对象表达式是一个值表达式,那么它首先会被计算,并放进一个临时位置,然后将结果值按顺序与arms中的模式进行比较,直到找到匹配的为止。带有匹配模式的第一个arm被选择为匹配的分支目标,模式所绑定的任何变量都被分配给arm块中的局部变量,控制流进入匹配块中。

当检审查达式是位置表达式时,匹配不分配临时位置;但是,按值绑定可以从内存位置复制或移动。如果可能的话,更可取的方法是匹配位置表达式,因为这些匹配的生存期继承place表达式的生存期,而不是被限制在匹配的内部。

let x = 1;
match x {
  1 => println!("one"),
  2 => println!("two"),
  _ => println!("something else"),
}

模式中变量绑定的作用域是匹配守护match guardarm表达式。绑定方式(移动、复制或引用)取决于模式。可以用|操作符连接多个匹配模式。每个模式将按照从左到右的顺序进行测试,直到找到一个成功的匹配。