异常安全(Exception Safety)

虽然程序应该谨慎使用展开(unwinding),但是有很多代码 可能会(can) 恐慌.如果你打开(unwrap)一个None,索引越界,或除以0,你的程序将会恐慌.在调试版本中,如果溢出,每个算术运算都会发生混乱.除非你非常小心并严格控制运行的代码,否则几乎所有东西都可以展开,你需要做好准备.

在更广泛的编程世界中,随时准备展开通常被称为 异常安全(exception safety) .在Rust中,有两个级别的异常安全性,人们可能会关注它们:

  • 在不安全代码中,我们 必须(must) 异常安全,以免违反内存安全.我们称之为 最小的(minimal) 异常安全性.

  • 在安全的代码中,对于程序做正确的事情来说, 最好(good) 是异常安全.我们称之为 最大(maximal) 异常安全性.

与Rust中许多地方的情况一样,不安全代码必须准备好在展开时处理不好的安全代码.暂时创建不健全状态的代码必须小心,恐慌不会导致使用该状态.通常,这意味着确保在这些状态存在时仅运行非恐慌代码,或者在恐慌的情况下使守卫清理状态.这并不一定意味着,恐慌作证的状态是一个完全连贯的状态.我们只需保证它是一个 安全的(safe) 状态.

大多数不安全代码都是叶状的(leaf-like),因此很容易使之异常安全.它控制所有运行的代码,大多数代码都不会出现恐慌.但是,在重复调用调用者提供的(caller-provided)代码时,不安全代码使用临时未初始化数据的数组并不罕见.这样的代码需要小心并考虑异常安全性.

Vec::push_all(Vec::push_all)

Vec::push_all是一个临时的技术(hack),可以通过切片可靠地高效扩展Vec而无需特化.这是一个简单的实现:

  1. impl<T: Clone> Vec<T> {
  2.     fn push_all(&mut self, to_push: &[T]) {
  3.         self.reserve(to_push.len());
  4.         unsafe {
  5.             // can't overflow because we just reserved this
  6.             self.set_len(self.len() + to_push.len());
  8.             for (i, x) in to_push.iter().enumerate() {
  9.                 self.ptr().add(i).write(x.clone());
  10.             }
  11.         }
  12.     }
  13. }

我们绕过push以避免冗余容量和对Vec的len检查,我们肯定知道它有容量.逻辑是完全正确的,只是我们的代码有一个微妙的问题:它不是异常安全的!set_len,add和write都很好;clone是我们忽视的(over-looked)恐慌炸弹.

克隆完全不受我们控制,完全可以自由恐慌.如果是这样,我们的函数将提前退出,Vec的长度设置得太大.如果查看或删除Vec,将读取未初始化的内存!

这种情况下的修复非常简单.如果我们想保证 确实是 我们克隆的值被删除,我们可以设置len每次循环迭代.如果我们只想保证无法观察到未初始化的内存,我们可以在循环后设置len.

BinaryHeap::sift_up(BinaryHeap::sift_up)

将元素冒泡到堆中比扩展Vec要复杂一些.伪代码如下:

```Rust (pseudocode) bubble_up(heap, index): while index != 0 && heap[index] < heap[parent(index)]: heap.swap(index, parent(index)) index = parent(index)

  2. 这段代码逐字转录到Rust完全没问题,但是有一个恼人的性能特征:`self`元素一遍又一遍地无用地交换.我们宁愿拥有以下内容:
  4. ```Rust (pseudocode)
  5. bubble_up(heap, index):
  6.     let elem = heap[index]
  7.     while index != 0 && elem < heap[parent(index)]:
  8.         heap[index] = heap[parent(index)]
  9.         index = parent(index)
  10.     heap[index] = elem

此代码确保尽可能少地复制每个元素(实际上有必要将elem一般复制两次).但它现在暴露了一些异常安全问题!在任何时候,都存在一个值的两个副本.如果我们在这个函数中发生恐慌,那么将会出现双重删除(double-dropped)问题.不幸的是,我们也没有完全控制代码:比较是用户定义的!

与Vec不同,这里的修复并不容易.一种选择是将用户定义的代码和不安全的代码分成两个独立的阶段:

```Rust (pseudocode) bubble_up(heap, index): let end_index = index; while end_index != 0 && heap[end_index] < heap[parent(end_index)]: end_index = parent(end_index)

  1. let elem = heap[index]
  2. while index != end_index:
  3.     heap[index] = heap[parent(index)]
  4.     index = parent(index)
  5. heap[index] = elem
  2. 如果用户定义的代码爆炸,那就不再是问题,因为我们还没有真正触及堆的状态.一旦我们开始搞乱堆，我们只处理我们信任的数据和函数,所以不用担心恐慌.
  4. 也许你对这个设计不满意.肯定是作弊!我们必须做 *两次(twice)* 复杂的堆遍历!好吧,让我们咬紧牙关.让我们 *真的(for reals)* 混合不可信和不安全的代码。
  6. 如果Rust有像Java中一样的`try`和`finally`,我们可以执行以下操作:
  8. ```Rust (pseudocode)
  9. bubble_up(heap, index):
  10.     let elem = heap[index]
  11.     try:
  12.         while index != 0 && elem < heap[parent(index)]:
  13.             heap[index] = heap[parent(index)]
  14.             index = parent(index)
  15.     finally:
  16.         heap[index] = elem

基本思路很简单:如果比较恐慌,我们就将松散的元素扔在逻辑上未初始化的索引中并挽救.任何观察堆的人都会看到一个可能 不一致的(inconsistent) 堆,但至少它不会导致任何双重删除!如果算法正常终止,则此操作恰好与我们如何完成的方式完全一致.

可悲的是,Rust没有这样的构造函数,所以我们需要自己动手!这样做的方法是将算法的状态存储在一个单独的结构中,其中包含”finally”逻辑的析构函数.无论我们是否恐慌,析构函数都会在我们之后运行和清理.

  1. struct Hole<'a, T: 'a> {
  2.     data: &'a mut [T],
  3.     /// `elt` is always `Some` from new until drop.
  4.     elt: Option<T>,
  5.     pos: usize,
  6. }
  8. impl<'a, T> Hole<'a, T> {
  9.     fn new(data: &'a mut [T], pos: usize) -> Self {
  10.         unsafe {
  11.             let elt = ptr::read(&data[pos]);
  12.             Hole {
  13.                 data: data,
  14.                 elt: Some(elt),
  15.                 pos: pos,
  16.             }
  17.         }
  18.     }
  20.     fn pos(&self) -> usize { self.pos }
  22.     fn removed(&self) -> &T { self.elt.as_ref().unwrap() }
  24.     unsafe fn get(&self, index: usize) -> &T { &self.data[index] }
  26.     unsafe fn move_to(&mut self, index: usize) {
  27.         let index_ptr: *const _ = &self.data[index];
  28.         let hole_ptr = &mut self.data[self.pos];
  29.         ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
  30.         self.pos = index;
  31.     }
  32. }
  34. impl<'a, T> Drop for Hole<'a, T> {
  35.     fn drop(&mut self) {
  36.         // fill the hole again
  37.         unsafe {
  38.             let pos = self.pos;
  39.             ptr::write(&mut self.data[pos], self.elt.take().unwrap());
  40.         }
  41.     }
  42. }
  44. impl<T: Ord> BinaryHeap<T> {
  45.     fn sift_up(&mut self, pos: usize) {
  46.         unsafe {
  47.             // Take out the value at `pos` and create a hole.
  48.             let mut hole = Hole::new(&mut self.data, pos);
  50.             while hole.pos() != 0 {
  51.                 let parent = parent(hole.pos());
  52.                 if hole.removed() <= hole.get(parent) { break }
  53.                 hole.move_to(parent);
  54.             }
  55.             // Hole will be unconditionally filled here; panic or not!
  56.         }
  57.     }
  58. }