Представление и основы 2: добавляем сырости
Краткое содержание трёх предыдущих частей: перемешивание ссылок
&,& mutиBoxс небезопасными указателями*mutи*const— верный способ получить Неопределённое Поведение, поскольку безопасные указатели вводят дополнительные ограничения, которым сырые указатели не обязаны подчиняться.
Господи, мне опять придётся писать связные списки. Прекрасно. ПРЕКРАСНО. Всё прекрасно. У нас всё прекрасно.
Мы быстро разберём большую часть этого раздела, поскольку мы уже обсудили дизайн в первой части. Всё, что бы делали, было в основном правильно, за исключением того, что мы смешивали безопасные и небезопасные указатели.
Представление
Итак, в новом представлении мы собираемся использовать только сырые указатели. Всё будет нормально и мы никогда больше не ошибёмся.
Вот наше старое проблемное представление:
#![allow(unused)] fn main() { 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>, } }
А вот наше новое представление.
#![allow(unused)] fn main() { pub struct List<T> { head: Link<T>, tail: *mut Node<T>, } type Link<T> = *mut Node<T>; // ГОРАЗДО ЛУЧШЕ struct Node<T> { elem: T, next: Link<T>, } }
Запомните: Option не удобен и не полезен, если мы используем сырые указатели, так что мы можем от него отказаться.
Чуть позже мы познакомимся с типом NotNull, но пока будем пользоваться чистыми указателями.
Основы
List::new по сути остаётся тем же самым.
use ptr;
impl<T> List<T> {
pub fn new() -> Self {
List { head: ptr::null_mut(), tail: ptr::null_mut() }
}
}push в основе так...
pub fn push(&mut self, elem: T) {
let mut new_tail = Box::new(Подождите, мы же больше не используем Box. Как нам выделить память без Box?
Мы могли бы вызывать std::alloc::alloc, но в данном случае это как брать катану на кухню.
Свою работу мы сделаем, но это будет и неудобно, и слишком наворочено.
Мы хотим использовать боксы, но, в то же время, нет. Один совершенно безумный вариант, но возможно жизнеспособный — сделать что-то такое:
#![allow(unused)] fn main() { struct Node<T> { elem: T, real_next: Option<Box<Node<T>>>, next: *mut Node<T>, } }
Идея в том, что мы создаём бокс и храним его в своём узле.
Затем получаем сырой указатель на содержимое бокса, и используем его, пока мы не закончим с узлом и не захотим его удалить.
Тогда мы можем забрать (take) и освободить Box из переменной real_next.
Кажется, это решение совместимо с нашей упрощённой моделью стековых заимствований?
Если вы хотите поэкспериментировать с этой идеей, пожалуйста, развлекайтесь, но выглядит она уродливо, не так ли? Это не глава про Rc или RefCell и мы больше не будем играть в эту игру. Будем делать простые и ясные вещи.
Используем милейшую функцию Box::into_raw.
pub fn into_raw(b: Box<T>) -> *mut TВозвращает сырой указатель на содержимое Box.
Указатель будет правильно выровнен и не равен null.
После вызова этой функции вызывающая сторона отвечает за память, которой прежде владел Box. В частности, вызывающая сторона должна правильно уничтожить T и освободить память с учётом внутреннего устройства Box. Простейший способ это сделать — преобразовать сырой указатель обратно в Box с помощью функции
Box::from_raw, позволив деструктору Box выполнить очистку.Обратите внимание, что это ассоциированная функция, то есть вы должны вызывать её как
Box::into_raw(b)вместоb.into_raw(). Это нужно, чтобы избежать возможного конфликта с методом внутреннего типа.Примеры
Конвертируем сырой указатель обратно в Box с помощью Box::from_raw для автоматической очистки:
#![allow(unused)] fn main() { let x = Box::new(String::from("Hello")); let ptr = Box::into_raw(x); let x = unsafe { Box::from_raw(ptr) }; }
Прекрасно, эти методы как будто разработаны буквально для нашего случая.
Они также следует нашим правилам: начинают с безопасного Box, превращают его в сырой указатель, и затем преобразуют его обратно в Box (когда мы хотим вызывать drop).
По сути, всё выглядит точно также, как и ужасный способ с real_next, но без необходимости возиться с сохранением Box, поскольку это тот же самый указатель.
Теперь, когда мы везде используем сырые указатели, давайте не беспокоиться о том, чтобы блоки unsafe были небольшими: весь наш код небезопасен.
(Так всегда и было, но иногда обманывать самих себя так приятно.)
pub fn push(&mut self, elem: T) {
unsafe {
// Сразу преобразуем Box в сырой указатель
let new_tail = Box::into_raw(Box::new(Node {
elem: elem,
next: ptr::null_mut(),
}));
if !self.tail.is_null() {
(*self.tail).next = new_tail;
} else {
self.head = new_tail;
}
self.tail = new_tail;
}
}Смотрите, сейчас, когда мы используем только сырые указатели, код выглядит гораздо чище!
Перейдём к методу pop, который тоже достаточно похож на старую реализацию, хотя мы помним, что надо вызывать Box::from_raw перед очисткой:
pub fn pop(&mut self) -> Option<T> {
unsafe {
if self.head.is_null() {
None
} else {
// ВОССТАНЬ ИЗ МОГИЛЫ
let head = Box::from_raw(self.head);
self.head = head.next;
if self.head.is_null() {
self.tail = ptr::null_mut();
}
Some(head.elem)
}
}
}Наши прекрасные маленькие take и map больше не нужны, теперь мы проверяем и устанавливаем null вручную.
И, раз уже мы заговорили об этом, давайте добавим деструктор.
Пока реализуем через повторяющийся вызов pop, потому что это легко и просто:
impl<T> Drop for List<T> {
fn drop(&mut self) {
while let Some(_) = self.pop() { }
}
}А теперь настал момент истины:
#[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);
// Проверяем push после pop из пустого списка
list.push(6);
list.push(7);
// Проверяем обычное удаление
assert_eq!(list.pop(), Some(6));
assert_eq!(list.pop(), Some(7));
assert_eq!(list.pop(), None);
}
}cargo test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... 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. 12 passed; 0 failed; 0 ignored; 0 measured
Хорошо, но согласен ли miri?
MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test
running 12 tests
test fifth::test::basics ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fourth::test::into_iter ... 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. 12 passed; 0 failed; 0 ignored; 0 measured
ЙЕЕЕЕ!!!!!
ЭТА ХРЕНЬ СРАБОТАЛА!
ВОЗМОЖНО!
НЕВОЗМОЖНО ДОКАЗАТЬ ОТСУТСТВИЕ НЕОПРЕДЕЛЁННОГО ПОВЕДЕНИЯ. ЕСТЬ ШАНС, ЧТО ОНО ВСЁ ЕЩЁ СУЩЕСТВУЕТ ГДЕ-ТО ТАМ, НО ЕСТЬ ПРЕДЕЛ ТОМУ, НАСКОЛЬКО Я ГОТОВА БЫТЬ СТРОГОЙ В ШУТОЧНОЙ КНИГЕ О СВЯЗНЫХ СПИСКАХ. В ОБЩЕМ, МЫ БУДЕМ СЧИТАТЬ ЭТО ДОКАЗАТЕЛЬСТВО 100% ПРОВЕРЕННЫМ МАШИНОЙ И ЛЮБОЙ, КТО СКАЖЕТ ОБРАТНОЕ, МОЖЕТ ОБЛИЗАТЬ МОЕГО ПЕТУШКА!
(Прим. перев.: в оригинальном тексте именно так — довольно грубо — и написано. Речь, конечно, идёт об языке программирования Coq, который используется для доказательства корректности программ. В то же время Coq созвучен английскому cock — петух. Кроме того, в разговорном английском слово cock означает мужской половой орган.)
Что и требовалось доказать.