Метод drop и устойчивость к панике
А вы заметили этот комментарий:
#![allow(unused)] fn main() { // Обратите внимание, что мы больше не должны беспокоиться // о `take`, потому что копирование сырых указателей не приводит к // вызову деструкторов, если мы что-то напутаем... правда? :) // Праааавда? :))) }
Это правда?
Простите, вы забыли, какую книгу читаете? Конечно, нет! (В каком-то смысле.)
Снова заглянем внутрь pop_front:
// Возвращаем к жизни Box, так что можно извлечь и уничтожить его
// значение (Box магически делает это за нас).
let boxed_node = Box::from_raw(node.as_ptr());
let result = boxed_node.elem;
// Делаем следующий узел новым передним узлом.
self.front = boxed_node.back;
if let Some(new) = self.front {
// Убираем ссылку переднего узла на удалённый узел.
(*new.as_ptr()).front = None;
} else {
// Если передний узел равен null, значит, список пустой!
debug_assert!(self.len == 1);
self.back = None;
}
self.len -= 1;
result
// Здесь Box неявным образом освобождается, потому что больше нет T.Видите ошибку? Ужасно, но она в этой строчке:
debug_assert!(self.len == 1);Серьёзно? Проклятая проверка целостности, сделанная для тестов — ошибка? Да!!! Впрочем, если коллекция реализована корректно, ошибка не должна возникнуть. Но может получиться так, что вполне безобидная штука вроде «некорректного обновления len» превратится в Уязвимость, вызванную ошибкой безопасности памяти! Почему? Потому что может возникнуть паника! Большую часть времени вам не стоит беспокоиться о панике, но однажды вы начинаете писать поистине небезопасный код и вольно обращаетесь с «инвариантностью», и вам приходится проявлять повышенную бдительность!
Нам нужно поговорить об устойчивости к исключениям (ИЛИ устойчивости к панике, ИЛИ устойчивости к раскрутке стека...).
Итак, паника по умолчанию приводит к раскрутке стека (unwinding). Раскрутка — это красивый способ сказать «немедленно завершить каждую функцию». Вы можете подумать «Ладно, если всё завершается, значит, программа тоже завершается, так что не о чем беспокоиться?», но вы не правы!
Мы должны беспокоиться по двум причинам: из-за запуска деструкторов, и возможного перехвата раскрутки. В обоих случаях, код будет выполняться после паники, так что нам надо быть очень осторожными и убедиться, что наши небезопасные коллекции находятся в каком-то когерентном состоянии независимо от паники, потому что паника неявно означает ранний возврат (early return)!
Подумайте, в каком состоянии находится коллекция, когда мы доходим до строки с ошибкой.
У нас есть boxed_node на стеке, и мы извлекли из него элемент. Если бы мы завершили функцию в этой точке, Box должен был быть уничтожен, и узел должен был быть освобождён. Теперь вы видите?.. self.back всё ещё указывает на освобождённый узел! Как только мы реализуем оставшиеся функции и начнём использовать self.back для разных вещей, это приведёт к ошибке использование-после-освобождения (use-after-free)! Кошмар!
Интересно, что в этой строке встречается похожая проблема, но гораздо более безопасная:
self.len -= 1;По умолчанию в отладочных сборках Rust проверяет выход за нижнюю и верхнюю границы, и паникует, когда они случаются. Да, любая арифметическая операция представляет собой угрозу для устойчивости к панике! Этот случай лучше, потому что он происходит после того, как мы восстановили все наши инварианты, так что он не может привести к проблемам с безопасностью памяти... Если мы вышли за нижнюю границу, ошибка уже случилась, так что программа упала бы в любом случае! В каком смысле debug_assert хуже, потому что превращает неважную проблему в критическую!
Я уже несколько раз употребляла термин «инвариант», а всё потому, что это действительно полезная концепция для разговора про устойчивость к панике! В каком-то смысле, для стороннего наблюдателя у нашей коллекции есть определённые свойства, которые всегда соблюдаются. Для связного списка одним из таких свойств является следующее: для любого достижимого узла в нашем списке выделена и проинициализирована память.
Внутри реализации нам доступно чуть больше гибкости, чтобы временно нарушать инварианты, пока мы уверены, что восстановим их до того, как кто-нибудь заметит.
По сути, это одно из «главных преимуществ» системы владения и заимствования в Rust для коллекций: если операции нужен параметр &mut Self, мы гарантированно получаем эксклюзивный доступ к нашей коллекции и свободно можем временно нарушить инварианты, зная, что никто не сможет незаметно нам помешать.
Возможно, наилучшим воплощением этой идеи является Vec::drain, который, фактически, позволяет вам полностью нарушить основной инвариант Vec и начать извлекать значения не только из начала Vec, но и из середины.
Причина, по которой это правильно заключается в том, что итератор Drain, который мы возвращаем, хранит &mut на Vec, поэтому любой доступ к нему ограничен!
Никто не сможет пользоваться Vec до тех пор, пока итератор Drain не завершится, и тогда деструктор «восстановит» Vec до того, как кто-либо это заметит, что идеа—
Нет, это не идеально. К сожалению вы не можете полагаться на выполнение деструкторов в коде, который вы не контролируете, так что даже с Drain нам нужно делать небольшую дополнительную работу, чтобы инварианты нашего типа всегда сохранялись, но в несколько нелепой манере: в начале мы просто сбрасываем длину Vec в 0, так что если у кого-то утечёт Drain, он получит безопасный Vec... потеряв при этом все данные. Ты устроил утечку мне? Я устрою утечку тебе! Око за око! Истинная справедливость!
Чтобы разобраться, когда для устойчивости при панике действительно можно использовать деструкторы, познакомьтесь с учебным примером использования BinaryHeap::sift_up.
Нам в любом случае не нужны все эти навороченные штуки для наших связных списков. Нам всего лишь надо быть внимательнее по отношению к тому, где мы нарушаем инварианты, чтобы обеспечить корректность и избегать ненужной раскрутки стека в середине сложных задач.
В этом случае у нас есть две возможности сделать код надёжнее:
- Чаще использовать такие операции, как Option::take, потому что они более «транзакционные» и имеют тенденцию сохранять инварианты.
- Удалить все debug_assert и доверять себе в написании лучших тестов со специальными функциями «проверки целостности», которые никогда не будут выполняться в пользовательском коде.
В принципе мне нравится первый вариант, но на самом деле он не сработает для двусвязного списка, потому что нам одновременно требуются два значения, а не одно. Option::take не решит нашей проблемы, а вот перенос debug_assert на строку ниже — решит. Но, правда, зачем усложнять себе жизнь? Давайте просто удалим все debug_assert и убедимся, что любая паника может возникнуть только в начале или конце наших методов, где, как известно, выполняются все инварианты.
(Возможно про них следует думать, как о предусловиях и постусловиях, но на самом деле к ним правильнее относиться, как к инвариантам!)
Вот наша полная текущая реализация:
#![allow(unused)] fn main() { use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. Кроме того, мы добавили // несколько проверок, на случай, если что-то напутали. self.back = Some(new); } // Этот код выполняется всегда! self.front = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn len(&self) -> usize { self.len } } }
Что здесь может привести к панике? Чтобы ответить на этот вопрос, надо быть экспертом по Rust, но, к счастью, я им являюсь!
Единственные места, которые я вижу, где код может вызвать панику (за исключением совершенно безумной идеи перекомпилировать стандартную библиотеку с включенными debug_assert, чего никогда не следует делать) — это Box::new (в случае нехватки памяти) и арифметические операции с len.
Всё это находится или в самом конце или в самом начале наших методов, так что да, наш код красивый и безопасный!
...удивились, что Bos::new может вызывать панику?
Паника может достать вас самым непредсказуемым образом!
Держите свои инварианты в целости, чтобы вас это не беспокоило!