异常安全性

尽管程序应该谨慎地使用展开（unwinding），但仍有很多代码可能会发生 panic。 如果你解包一个 None，索引越界或除以 0，你的程序将会 panic。在 debug 构建中，如果发生溢出，每个算术运算都可能 panic。除非你非常小心并严格控制运行的代码，否则几乎所有事情都可能展开，你需要为此做好准备。

为展开做好准备在更广泛的编程世界中通常被称为异常安全性。 在 Rust 中，人们可能会关注两个级别的异常安全性

• 在 unsafe 代码中，我们必须保证异常安全，以免违反内存安全。 我们称之为最低限度的异常安全。

• 在 safe 代码中，保证异常安全以使你的程序正常工作是好的。 我们称之为最大限度的异常安全。

就像 Rust 中的许多情况一样，在发生展开时，Unsafe 代码必须准备好处理错误的 Safe 代码。 临时创建不健全状态的代码必须小心，以防 panic 导致该状态被使用。通常，这意味着在这些状态存在时，仅运行不会 panic 的代码，或者创建一个在发生 panic 时清理状态的保护措施。这并不一定意味着 panic 见证的状态是一个完全一致的状态。 我们只需要保证它是一个安全的状态。

大多数 Unsafe 代码都是叶子式的，因此很容易实现异常安全。 它控制所有运行的代码，并且大多数代码都不会 panic。 但是，Unsafe 代码在重复调用调用者提供的代码时，使用临时未初始化数据数组的情况并不少见。 这样的代码需要小心并考虑异常安全性。

Vec::push_all

Vec::push_all 是一个临时 hack，用于在没有特殊化的情况下，可靠地高效地通过切片扩展 Vec。 这是一个简单的实现

impl<T: Clone> Vec<T> {
    fn push_all(&mut self, to_push: &[T]) {
        self.reserve(to_push.len());
        unsafe {
            // can't overflow because we just reserved this
            self.set_len(self.len() + to_push.len());

            for (i, x) in to_push.iter().enumerate() {
                self.ptr().add(i).write(x.clone());
            }
        }
    }
}

我们绕过 push 是为了避免对 Vec 进行冗余的容量和 len 检查，因为我们明确知道 Vec 具有容量。 该逻辑完全正确，但是我们的代码存在一个微妙的问题：它不是异常安全的！ set_len、add 和 write 都很好； clone 是我们忽略的 panic 炸弹。

Clone 完全不受我们的控制，并且可以完全自由地 panic。 如果发生 panic，我们的函数将提前退出，并且 Vec 的长度设置得过大。 如果查看或丢弃 Vec，将会读取未初始化的内存！

在这种情况下，修复方法很简单。 如果我们想保证我们确实克隆的值被丢弃，我们可以每次循环迭代都设置 len。 如果我们只是想保证无法观察到未初始化的内存，我们可以在循环之后设置 len。

BinaryHeap::sift_up

将元素向上冒泡到堆中比扩展 Vec 稍微复杂一些。 伪代码如下

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

将此代码逐字转换为 Rust 完全没问题，但是有一个令人讨厌的性能特征：self 元素一遍又一遍地被无用地交换。 我们宁愿拥有以下代码

bubble_up(heap, index):
    let elem = heap[index]
    while index != 0 && elem < heap[parent(index)]:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

此代码确保每个元素被尽可能少地复制（事实上，通常需要将 elem 复制两次）。 但是，它现在暴露了一些异常安全问题！ 在任何时候，都存在一个值的两个副本。 如果我们在这个函数中发生 panic，某些东西会被双重丢弃。 不幸的是，我们也不能完全控制代码：该比较是用户定义的！

与 Vec 不同，此处的修复并不容易。 一种选择是将用户定义的代码和 unsafe 代码分成两个单独的阶段

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

    let elem = heap[index]
    while index != end_index:
        heap[index] = heap[parent(index)]
        index = parent(index)
    heap[index] = elem

如果用户定义的代码崩溃，那没问题了，因为我们还没有真正触及堆的状态。 一旦我们开始处理堆，我们只使用我们信任的数据和函数，因此不必担心 panic。

也许您对这种设计不满意。 肯定是在作弊！ 而且我们必须两次执行复杂的堆遍历！ 好吧，让我们咬紧牙关。 让我们真正地混合不可信代码和 unsafe 代码。

如果 Rust 像 Java 那样有 try 和 finally，我们可以执行以下操作

bubble_up(heap, index):
    let elem = heap[index]
    try:
        while index != 0 && elem < heap[parent(index)]:
            heap[index] = heap[parent(index)]
            index = parent(index)
    finally:
        heap[index] = elem

基本思想很简单：如果比较发生 panic，我们只需将松散的元素扔到逻辑上未初始化的索引中，然后退出。 任何观察堆的人都会看到一个可能不一致的堆，但至少它不会导致任何双重丢弃！ 如果算法正常终止，则此操作恰好与我们无论如何都要完成的操作一致。

遗憾的是，Rust 没有这样的构造，因此我们需要自己实现！ 做到这一点的方法是将算法的状态存储在具有“finally”逻辑的析构函数的单独结构中。 无论我们是否 panic，该析构函数都会运行并清理我们的操作。

struct Hole<'a, T: 'a> {
    data: &'a mut [T],
    /// `elt` is always `Some` from new until drop.
    elt: Option<T>,
    pos: usize,
}

impl<'a, T> Hole<'a, T> {
    fn new(data: &'a mut [T], pos: usize) -> Self {
        unsafe {
            let elt = ptr::read(&data[pos]);
            Hole {
                data,
                elt: Some(elt),
                pos,
            }
        }
    }

    fn pos(&self) -> usize { self.pos }

    fn removed(&self) -> &T { self.elt.as_ref().unwrap() }

    fn get(&self, index: usize) -> &T { &self.data[index] }

    unsafe fn move_to(&mut self, index: usize) {
        let index_ptr: *const _ = &self.data[index];
        let hole_ptr = &mut self.data[self.pos];
        ptr::copy_nonoverlapping(index_ptr, hole_ptr, 1);
        self.pos = index;
    }
}

impl<'a, T> Drop for Hole<'a, T> {
    fn drop(&mut self) {
        // fill the hole again
        unsafe {
            let pos = self.pos;
            ptr::write(&mut self.data[pos], self.elt.take().unwrap());
        }
    }
}

impl<T: Ord> BinaryHeap<T> {
    fn sift_up(&mut self, pos: usize) {
        unsafe {
            // Take out the value at `pos` and create a hole.
            let mut hole = Hole::new(&mut self.data, pos);

            while hole.pos() != 0 {
                let parent = parent(hole.pos());
                if hole.removed() <= hole.get(parent) { break }
                hole.move_to(parent);
            }
            // Hole will be unconditionally filled here; panic or not!
        }
    }
}