异常安全

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

在更广泛的编程世界中，为展开做好准备通常被称为*异常安全*。在 Rust 中，有两个级别的异常安全需要注意

在不安全的代码中，我们*必须*保证异常安全，以防止违反内存安全。我们称之为*最小*异常安全。
在安全的代码中，保证异常安全以使你的程序做正确的事情是*好的*。我们称之为*最大*异常安全。

与 Rust 中的许多地方一样，当涉及到展开时，不安全的代码必须准备好处理糟糕的安全的代码。暂时创建不健全状态的代码必须小心，不要因为 panic 而导致该状态被使用。通常这意味着要确保在这些状态存在时只运行非 panic 代码，或者在发生 panic 时创建一个清理状态的守卫。这并不一定意味着 panic 遇到的状态是一个完全一致的状态。我们只需要保证它是一个*安全*的状态。

大多数不安全的代码都是叶状的，因此很容易实现异常安全。它控制着所有运行的代码，而这些代码中的大多数都不能 panic。然而，不安全的代码在重复调用调用者提供的代码时，使用临时未初始化数据的数组并不少见。这样的代码需要小心并考虑异常安全。

Vec::push_all

Vec::push_all 是一个临时技巧，可以在没有特化的情况下可靠地高效地扩展 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 检查。逻辑完全正确，但我们的代码有一个微妙的问题：它不是异常安全的！set_len、add 和 write 都很好；clone 是我们忽略的炸弹。

Clone 完全不受我们控制，并且完全可以自由地 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 不同，这里的修复方法并不容易。一种选择是将用户定义的代码和不安全的代码分成两个独立的阶段

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。

也许你对这个设计不满意。这肯定是作弊！而且我们必须*两次*进行复杂的堆遍历！好吧，让我们硬着头皮上吧。让我们*真正地*混合不可信和不安全的代码。

如果 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!
        }
    }
}

Rust 秘典

异常安全

Vec::push_all

BinaryHeap::sift_up