Что же, история с внутренней изменчивостью счётчика ссылок вышла из под контроля. Возможно Rust не рассчитан на структуры подобного вида? И да, и нет. Rc и RefCell могут прекрасно подойти для обработки простых случаев, но в то же время, они могут быть очень неуклюжими. Особенно, если вы пытаетесь скрыть эту неуклюжесть. Должен быть лучший способ!

В этой главые мы вернёмся к односвязным спискам и реализуем односвязную очередь с помощью сырых указателей и небезопасного Rust.

ГОЛОС ЗА КАДРОМ: А я укажу на ошибки.

Мы не собираем делать любые ошибки.

Давайте добавим новый файл с именем fifth.rs:

// в lib.rs

pub mod first;
pub mod second;
pub mod third;
pub mod fourth;
pub mod fifth;

Мы будем писать код, «подглядывая» в second.rs, так как в мире связных списков очереди в каком-то смысле — это расширение стека. Кроме того, мы начнём с чистого листа, поскольку есть несколько фундаментальных вопросов, которые мы хотим обсудить. Они касаются в первую очередь представления.

Представление

Так на что похожа односвязная очередь? Когда речь шла об односвязном стеке, мы вставляли элементы с одного конца списка и затем удаляли их с того же конца. Единственное отличие между стеком и очередью в том, что элементы очереди удаляются с другого конца. Из нашей реализации стека мы получаем:

список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

вставка X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)

удаление:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

Чтобы превратить стек в очередь надо решить, какую операцию перенести на другой конец списка — вставку или удаление? Так как у нас односвязный список, мы с одинаковыми усилиями можем перенести на другой конец любую из операций.

Чтобы перенести в конец вставку, мы должны пробежаться по списку до None и заменить его на Some с новым элементом.

список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

вставка X в конец:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

Чтобы перенести в конец удаление, мы должны пробежаться по списку до узла перед None и изъять узел.

список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)

удаление с конца:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)

Мы могли бы закрыть задачу прямо сейчас, но, скажем прямо, это решение ужасно! Обе операции пробегаются по всему списку. Вы возразите, что такая реализация вполне нормальна, поскольку полностью соответствует интерфейсу. Однако, я уверена, что гарантии производительности тоже являются частью интерфейса. Меня не волнуют точные асимптотические границы, просто «быстро» или «медленно». Гарантии очереди в том, что вставка и удаление быстрые, а обход всего списка — определённо не быстрый.

Обратите внимание, что мы делаем тучу работы, повторяя одну и ту же вещь снова и снова. Можем ли мы «кешировать» всю эту работу и переиспользовать результат? Да, разумеется! Мы можем сохранить указатель на конец списка и просто перепрыгивать туда!

Оказывается, что с этой идеей работает только один из вариантов инверсии вставки/удаления. Чтобы инвертировать pop, мы должны передвинуть назад указатель на хвост, но, поскольку наш список односвязный, этого нельзя сделать эффективно. Однако, если инвертируем push, надо будет передвинуть вперёд указатель на голову, а легко.

Давайте попробуем:

use std::mem;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>, // НОВАЯ СТРОКА!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // Когда вставляете в конец списка, следующий узел всегда None
            next: None,
        });

        // теперь указатель на хвост указывает на новый хвост
        let old_tail = mem::replace(&mut self.tail, Some(new_tail));

        match old_tail {
            Some(mut old_tail) => {
                // Если старый хвост был, обновляем его, чтобы он указывал на новый
                old_tail.next = Some(new_tail);
            }
            None => {
                // В противном случае, обновляем голову, чтобы указывала на него
                self.head = Some(new_tail);
            }
        }
    }
}

Я собираюсь ускорить повествование, опуская некоторые детали, поскольку к настоящему моменту вы уже должны понимать, как работает Rust. Похоже, что этот код запустится с первого раза. Сейчас я не показываю ошибки, которые показывала раньше, вроде пропусков mut или ;, так как они перестали быть поучительными. Не переживайте, мы столкнёмся с множеством других ошибок!

> cargo build

error[E0382]: use of moved value: `new_tail`
  --> src/fifth.rs:38:38
   |
26 |         let new_tail = Box::new(Node {
   |             -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 |         let old_tail = mem::replace(&mut self.tail, Some(new_tail));
   |                                                          -------- value moved here
...
38 |                 old_tail.next = Some(new_tail);
   |                                      ^^^^^^^^ value used here after move

Да что ж такое!

use of moved value: new_tail

Использование перемещённого значения: new_tail.

Box не реализует Copy, так что мы просто не можем присвоить его двум разным переменным. Что важнее, Box владеет значением, на которое указывает, и постарается освободить его в своём деструкторе. Если бы наша реализация push компилировалась, мы бы дважды освобождали хвост нашего списка! На самом деле, наш текущий код будет освобождать old_tail при каждом вызове push. Кошмар!

Ладно, мы знаем, как создать указатель без владения. Это будет просто ссылка!

pub struct List<T> {
    head: Link<T>,
    tail: Option<&mut Node<T>>, // НОВАЯ СТРОКА!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // Когда вставляете в конец списка, следующий узел всегда None
            next: None,
        });

        // Помещаем бокс в правильное место получем ссылку на его узел
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // Если старый хвост был, обновляем его, чтобы он указывал на новый
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // В противном случае, обновляем голову, чтобы указывала на него
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        self.tail = new_tail;
    }
}

Никакого особого трюкачества. Та же базовая идея, что и в предыдущем коде, за исключением того, что мы используем преимущества неявного возврата и получем ссылку на хвост прямо оттуда, куда мы только что поместили Box.

> cargo build

error[E0106]: missing lifetime specifier
 --> src/fifth.rs:3:18
  |
3 |     tail: Option<&mut Node<T>>, // NEW!
  |                  ^ expected lifetime parameter

Да, правильно, мы ведь должны указывать время жизни ссылок в типах. Хмм… а какое время жизни у этой ссылки? Ну, код похож на IterMut, правда? Давайте попробуем, то же самое, что мы делали в IterMut и просто добавим обобщённый 'a:

pub struct List<'a, T> {
    head: Link<T>,
    tail: Option<&'a mut Node<T>>, // НОВЫЙ КОД!
}

type Link<T> = Option<Box<Node<T>>>;

struct Node<T> {
    elem: T,
    next: Link<T>,
}

impl<'a, T> List<'a, T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }

    pub fn push(&mut self, elem: T) {
        let new_tail = Box::new(Node {
            elem: elem,
            // Когда вставляете в конец списка, следующий узел всегда None
            next: None,
        });

        // Помещаем бокс в правильное место и получем ссылку на его узел
        let new_tail = match self.tail.take() {
            Some(old_tail) => {
                // Если старый хвост был, обновляем его, чтобы он указывал на новый
                old_tail.next = Some(new_tail);
                old_tail.next.as_deref_mut()
            }
            None => {
                // В противном случае, обновляем голову, чтобы указывала на него
                self.head = Some(new_tail);
                self.head.as_deref_mut()
            }
        };

        self.tail = new_tail;
    }
}

cargo build

error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
  --> src/fifth.rs:35:27
   |
35 |                 self.head.as_deref_mut()
   |                           ^^^^^^^^^^^^
   |
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
  --> src/fifth.rs:18:5
   |
18 | /     pub fn push(&mut self, elem: T) {
19 | |         let new_tail = Box::new(Node {
20 | |             elem: elem,
21 | |             // When you push onto the tail, your next is always None
...  |
39 | |         self.tail = new_tail;
40 | |     }
   | |_____^
note: ...so that reference does not outlive borrowed content
  --> src/fifth.rs:35:17
   |
35 |                 self.head.as_deref_mut()
   |                 ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
  --> src/fifth.rs:13:6
   |
13 | impl<'a, T> List<'a, T> {
   |      ^^
   = note: ...so that the expression is assignable:
           expected std::option::Option<&'a mut fifth::Node<T>>
              found std::option::Option<&mut fifth::Node<T>>

Ого, вот действительно подробное сообщение об ошибке. Оно настораживает, потому что утверждает, что мы делаем что-то по настоящему неправильное. Вот интересная часть:

the lifetime must be valid for the lifetime 'a as defined on the impl

Время жизни должно быть действительно в течение времени жизни 'a, заданного в блоке impl

Мы заимствуем self, но компилятор хочет, чтобы мы существовали столько же, сколько и 'a, а что, если мы скажем ему, что self действительно существует столько же?

    pub fn push(&'a mut self, elem: T) {

cargo build

warning: field is never used: `elem`
 --> src/fifth.rs:9:5
  |
9 |     elem: T,
  |     ^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

О, здорово, так работает! Отлично!

Теперь давайте реализуем pop:

pub fn pop(&'a mut self) -> Option<T> {
    // Извлекаем текущую голову списка
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        // Если новый список пуст, хвост должен быть установлен в `None`.
        if self.head.is_none() {
            self.tail = None;
        }

        head.elem
    })
}

И напишем небольшой тест для нашего кода.

#[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);
    }
}

cargo test

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:68:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
68 |         list.push(1);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:69:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
69 |         list.push(2);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here

error[E0499]: cannot borrow `list` as mutable more than once at a time
  --> src/fifth.rs:70:9
   |
65 |         assert_eq!(list.pop(), None);
   |                    ---- first mutable borrow occurs here
...
70 |         list.push(3);
   |         ^^^^
   |         |
   |         second mutable borrow occurs here
   |         first borrow later used here


....

** ЕЩЁ МНОГО СТРОК С ОШИБКАМИ **

....

error: aborting due to 11 previous errors

🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀

Да божечки мои.

Компилятор совершенно прав, ругаясь на наш код. Мы только что совершили смертный грех языка Rust: сохранили ссылку на себя внутри себя. Нам как-то удалось убедить компилятор, что это действительно имеет смысл в наших реализациях push и pop (я искренне удивляюсь, что мы смогли).

Причина, по которой это вроде бы работает в том, что в Rust вообще нет такого понятия, как указатель на себя. Каждая часть кода технически корректна сама по себе (мы можем вызывать push и pop один раз), но затем вступает в силу абсурдность нашего решения и всё просто ломается.

Я уверена, что у написанного нами может быть какое-то применение, но, насколько мне известно, это всего лишь синтаксически корректная тарабарщина. Мы говорим, что у нас есть что-то с временем жизни 'a, и что push и pop заимствуют self на это время. Это странно, но Rust смотрит на каждую часть нашего кода по отдельности и ни видит никаких нарушений.

Но как только мы пытаемся действительно использовать список, компилятор нам сообщает: «так, вы заимствовали self изменяемым образом на время 'a, так что вы не можете использовать self до конца 'a», но также: «поскольку вы содержите 'a, он должен быть действителен в течение всего времени существования списка».

Это почти противоречие, но есть одно решение: сразу после вызова push или pop список себя закрепляет и к нему больше нельзя получить доступ. Образно говоря, он проглатывает свой хвост и возносится в мир грёз.

ГОЛОС ЗА КАДРОМ: с тех пор, как была написана эта книга, Rust, фактически, формализовал закрепление и нашёл ему применение! Возможно, это было самое сложное расширение языка со времён появления анализатора заимствований (borrow checker). Но нам, в любом случае, не надо закреплять наш список!

Закрепления нужны и полезны для async/await, футур, сопрограмм, поскольку компилятору надо собирать локальные переменные в некоторое подобие структуры и хранить их, пока футура/сопрограмма не будет готова к возобновлению. Поскольку локальные переменные могут ссылаться на другие локальные переменные, и мы хотим, чтобы всё работало, эти структуры в конечном счёте могут содержать ссылки на самих себя!

Таким образом, для await или yield Rust нуждается в корректном способе описания и манипулирования закреплёнными значениями. К счастью, в основном всё это скрыто глубоко в недрах компилятора и при обычных обстоятельствах никому не приходится думать про Pin (или даже про футуры). Главное исключение из этого правила: разработчики и проектировщики асинхронных библиотек, таких как tokio.

Мы не станем реализовывать асинхронную библиотеку в этой книге. Мои друзья знают все виды «крутых» (и странных) трюков, которые можно провернуть с Pin, но я бы не хотела погружаться в эту тему. Продолжу убеждать себя, что закреплённых типов не существуют и они не могут мне навредить.

Наша реализация pop подсказывает, почему хранение ссылки на себя внутри себя может быть опасным:

// ...
if self.head.is_none() {
    self.tail = None;
}

Что, если мы забудем это сделать? Тогда наш хвост будет указывать на какой-то узел, который уже удалён из списка. Такой узел будет мгновенно освобождён и мы получили бы висящий указатель, от чего Rust должен был нас защитить!

И действительно Rust защищает нас от подобной опасности. Просто очень… окольным путём.

Так что же нам теперь делать? Возвращаться в ад Rc<RefCell>>?

Спасибо. Не надо.

Нет, вместо этого пустимся во все тяжкие и начнём использовать сырыми указателями. Теперь наша структура будет выглядеть так.

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>,
}

И это всё. Никакого детского лепета про подсчёт ссылок и динамическую проверку заимствований! Реальные. Сложные. Непроверяемые. Указатели.

ГОЛОС ЗА КАДРОМ: наша реализация фактически была не просто неправильной, а опасно неправильной. Но для этого урока время ещё не пришло. В следующей части усвоим его на собственном горьком опыте, как и всегда.

Да будет C ныне, присно и во веки веков!

Я возвращаюсь домой. Я готова.

Привет, unsafe.

ГОЛОС ЗА КАДРОМ: какая невероятная самонадеянность со стороны автора.

Небезопасный Rust

Это серьёзная, большая, сложная и опасная тема. Настолько серьёзная, что я написала про неё отдельную книгу. (Прим. перевод.: речь идёт о широко известной в среде Rust-программистов книге Растономикон).

На самом деле любой язык, из которого можно вызывать функции на другом языке, уже является небезопасным, потому что, например, в C можно делать любые плохие вещи. Java, Python, Ruby, Haskell… все они крайне небезопасны из-за присутствия в них интерфейса внешних функций (Foreign Function Interfaces, FFI).

Rust следует этой истине, разделяя себя на два языка — Безопасный и Небезопасный Rust. Пока что мы работали только с Безопасным. Это на 100% безопасно… пока мы не используем FFI.

Небезопасный Rust — это надмножество над Безопасным Rust. Он такой же, как и Безопасный Rust со всей семантикой и правилами, но вам доступны дополнительные возможности. Они дико небезопасны и могут привести к ужасному Неопределённому Поведению (Undefined Behaviour, UB), которым так славится C.

Ещё раз скажу, что мы имеем дело с действительно огромной темой, в которой много интересных частных случаев. Я на самом деле не хочу иметь в ними дела (ну, ладно, хочу; уже имела; читайте книгу). К счастью, в случае связных списков мы можем игнорировать большинство из них.

ГОЛОС ЗА КАДРОМ: Это была ложь, но в 2015 она казалась правдой.

Главный инструмент Небезопасного Rust, который мы будем использовать — это сырые указатели. Сырые указатели — это, по сути, указатели из C. У них нет собственных правил псевдонимизации (aliasing). У них нет времени жизни. Они могут быть нулевыми. Они могут быть невыровненными. Они могут быть висячими. Они могут указывать на неинициализированную память. Их можно приводить к целым числам и обратно. Их можно приводить к указателям на другой тип. Неизменяемый указатель? Приводим к изменяемому! Мы можем делать практически всё, что угодно, а это значит, что практически всё, что угодно, может пойти не так.

ГОЛОС ЗА КАДРОМ: нет собственных правил псевдонимизации, да? Эх, молодо-зелено.

Это довольно неприятная штука и, честно говоря, вы были бы гораздо счастливее, оставаясь в рамках Безопасного Rust. К сожалению, мы хотим писать связные списки, а связные списки действительно ужасны. И это значит, что нам придётся использовать небезопасные указатели.

Есть два вида сырых указателей: *const T и *mut T. Предполагается, что они соответствуют const T* и T* из языка C, но нам, по большому счёту, всё равно, что они означают в C. *const T можно разыменовать только в &T, но, как и в случае с изменяемостью переменной, это всего лишь способ защиты от некорректного использования. Его можно обойти, если сначала надо привести *const к *mut. Впрочем, если у вас нет права менять объект, на который ссылается указатель, у вас возникнут проблемы.

В любом случае, мы лучше разберёмся в теме, если напишем немного кода. А пока для нас *mut T будет значить &unchecked mut T!

Основы

ГОЛОС ЗА КАДРОМ: в этой главе есть фундаментальная ошибка, точнее, её неясные очертания. Собственно, про неё и написана эта книга. Как только мы стали использовать unsafe, у нас появилась возможность делать большие ошибки, при этом наши программы вполне компилироваться и на первый взгляд даже работают. Фундаментальная ошибка будет раскрыта в следующей главе. А пока — не используйте содержимое этой главы в продуктовом коде!

Самое время вернуться к основам. Как мы конструируем наш список?

Раньше мы просто делали:

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: None }
    }
}

Но теперь мы не можем использовать Option для tail:

> cargo build

error[E0308]: mismatched types
  --> src/fifth.rs:15:34
   |
15 |         List { head: None, tail: None }
   |                                  ^^^^ expected *-ptr, found 
   |                                       enum `std::option::Option`
   |
   = note: expected type `*mut fifth::Node<T>`
              found type `std::option::Option<_>`

Мы могли бы использовать Option, но, в отличие от Box, *mut может принимать значение null. Это значит, что мы не получаем преимуществ от оптимизации нулевого указателя. Вместо этого мы используем null, чтобы представить вариант None.

Так как же нам получить указатель на null? Есть несколько способов, но я предпочитаю вызывать std::ptr::null_mut(). Если хотите, можете писать 0 as *mut _, но на мой взгляд это выглядит неряшливо.

use std::ptr;

// определения...

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: None, tail: ptr::null_mut() }
    }
}

cargo build

warning: field is never used: `head`
 --> src/fifth.rs:4:5
  |
4 |     head: Link<T>,
  |     ^^^^^^^^^^^^^
  |
  = note: #[warn(dead_code)] on by default

warning: field is never used: `tail`
 --> src/fifth.rs:5:5
  |
5 |     tail: *mut Node<T>,
  |     ^^^^^^^^^^^^^^^^^^

warning: field is never used: `elem`
  --> src/fifth.rs:11:5
   |
11 |     elem: T,
   |     ^^^^^^^

warning: field is never used: `head`
  --> src/fifth.rs:12:5
   |
12 |     head: Link<T>,
   |     ^^^^^^^^^^^^^

Тише, компилятор, скоро мы используем все эти определения.

Ладно, давайте снова напишем push. Теперь, вместо того, чтобы после вставки получить Option<&mut Node<T>>, мы сразу же получим *mut Node<T> из Box. Мы без проблем можем это сделать, потому что содержимое Box имеет стабильный адрес, даже если мы перемещаем Box. Конечно, это не безопасно, потому что если мы удалим Box, у нас останется указатель на освобождённую память.

Как получить сырой указатель из обычного указателя? С помощью приведения типа! К переменной, объявленной как сырой указатель, можно привести обычную ссылку.

let raw_tail: *mut _ = &mut *new_tail;

Теперь у нас есть вся необходимая информация. Мы можем переписать наш код так, чтобы он был более-менее похож на предыдущую эталонную реализацию.

pub fn push(&mut self, elem: T) {
    let mut new_tail = Box::new(Node {
        elem: elem,
        next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    // .is_null проверяет на null, эквивалент проверки на None
    if !self.tail.is_null() {
        // Если старый хвост был, обновляем его, чтобы он указывал на новый
        self.tail.next = Some(new_tail);
    } else {
        // В противном случае, обновляем голову, чтобы указывала на него
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             self.tail.next = Some(new_tail);
   |             ----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; 
   |             try dereferencing it: `(*self.tail).next`

Что? У нас есть указатель на Node, почему нам недоступно поле next?

Когда вы используете сырые указатели, Rust становится довольно грубым. Для доступа к содержимому сырого указателя нужно ручное разыменование, поскольку это крайней небезопасная операция. Так давайте, наконец, разыменуем:

*self.tail.next = Some(new_tail);

> cargo build

error[E0609]: no field `next` on type `*mut fifth::Node<T>`
  --> src/fifth.rs:31:23
   |
31 |             *self.tail.next = Some(new_tail);
   |             -----------^^^^
   |             |
   |             help: `self.tail` is a raw pointer; 
   |             try dereferencing it: `(*self.tail).next`

У-у-у-у, приоритет операторов.

(*self.tail).next = Some(new_tail);

> cargo build

error[E0133]: dereference of raw pointer is unsafe and requires 
              unsafe function or block

  --> src/fifth.rs:31:13
   |
31 |             (*self.tail).next = Some(new_tail);
   |             ^^^^^^^^^^^^^^^^^ dereference of raw pointer
   |
   = note: raw pointers may be NULL, dangling or unaligned; 
     they can violate aliasing rules and cause data races: 
     all of these are undefined behavior

ЭТО. НЕ ДОЛЖНО. БЫТЬ. ТАКИМ. СЛОЖНЫМ.

Помните, я говорила, что Небезопасный Rust — это своего рода FFI для Безопасного Rust? Ну вот, компилятор требует, чтобы мы явно указывали, где именно применяем FFI. У нас есть два варианта. Во-первых, мы можем пометить всю нашу функцию ключевым словом unsafe, при этом она становится функцией Небезопасного Rust и может быть вызвана только в небезопасном контексте. Это не очень здорово, потому что мы хотим, чтобы нашим списком можно было пользоваться в безопасном коде. Во-вторых, мы можем написать блок unsafe внутри нашей функции, чтобы обозначить границы FFI. При этом сама функция будет считаться безопасной. Хорошо, давайте сделаем:

pub fn push(&mut self, elem: T) {
    let mut new_tail = Box::new(Node {
        elem: elem,
        next: None,
    });

    let raw_tail: *mut _ = &mut *new_tail;

    if !self.tail.is_null() {
        // Привет, компилятор. Я знаю, что рискую и обещаю
        // быть хорошим программистом, который никогда не ошибается.
        unsafe {
            (*self.tail).next = Some(new_tail);
        }
    } else {
        self.head = Some(new_tail);
    }

    self.tail = raw_tail;
}

> cargo build
warning: field is never used: `elem`
  --> src/fifth.rs:11:5
   |
11 |     elem: T,
   |     ^^^^^^^
   |
   = note: #[warn(dead_code)] on by default

Ага!

Довольно интересно, но это пока единственное место, где нам пришлось написать небезопасный код. Сырые указатели у нас повсюду, почему unsafe потребовался только здесь?

Дело в том, что, когда речь заходит об unsafe, Rust становится настоящим педантом, помешанным на правилах. Мы вполне обоснованно хотим максимизировать множество программ на Безопасном Rust, потому что в отношении них мы можем быть гораздо более уверены. Чтобы этого достигнуть, Rust старается выделять минимальную возможную небезопасную область. Обратите внимание, что в других местах, где мы работали с сырыми указателями, мы либо присваивали им значение, либо просто проверяли их на null.

Если вы никогда не разыменовываете сырой указатель все эти операции совершенно безопасны. Вы просто читаете и записываете целые числа! Неприятности с сырым указателем могут возникнуть только при разыменовании. Так что Rust считает небезопасной только эту операцию, а все остальные — нет.

Супер. Педантично. Но технически корректно.

ГОЛОС ЗА КАДРОМ: Где-то на другом конце света инженер-электронщица чувствует, как мурашки бегут по её коже — должно быть, кто-то опять утверждает, что указатели — это всего лишь целые числа. Она смотрит на своё предложение по новой схеме аутентификации аппаратных указателей и скупая слеза бежит по её щеке. Инженер-сборщик по соседству не чувствует ничего — он давно научился всегда надевать тёплый свитер.

Из-за того, что действительно небезопасными является только часть операций, возникает интересная проблема. Не смотря на то, что небезопасная область ограничена блоком unsafe, в действительности, она зависит от состояния, заложенного вне этого блока и даже вне функции!

Это то, что я называю небезопасным заражением. Как только вы используете unsafe в модуле, весь модуль заражается небезопасностью. Всё должно быть написано корректно, чтобы гарантировать соблюдение всех инвариантов в небезопасном коде.

Проблема заражения решается благодаря приватности. Вне нашего модуля поля нашей структуры абсолютно приватны, поэтому никто не другой не может произвольно менять наше состояние. До тех пор, пока никакая комбинация вызовов API не приводит к негативным последствиям, с точки зрения внешнего наблюдателя весь наш код безопасен! И, по сути, это ничем не отличается от FFI. Никого не волнует, что математическая библиотека Python вызывает код на C, если она предоставляет безопасный интерфейс.

Ладно, теперь давайте напишем pop, который практически дословно повторяет эталонную версию:

pub fn pop(&mut self) -> Option<T> {
    self.head.take().map(|head| {
        let head = *head;
        self.head = head.next;

        if self.head.is_none() {
            self.tail = ptr::null_mut();
        }

        head.elem
    })
}

Мы встретили ещё один сценарий, в котором безопасность зависит от состояния. Если мы не обнулим указатель на хвост в этой функции, у нас не будет никаких проблем. Однако последующие вызовы push начнут писать в висячий указатель!

Давайте протестируем:

#[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);

        // Check the exhaustion case fixed the pointer right
        list.push(6);
        list.push(7);

        // Check normal removal
        assert_eq!(list.pop(), Some(6));
        assert_eq!(list.pop(), Some(7));
        assert_eq!(list.pop(), None);
    }
}

Это всё тот же тест стека, но результаты pop здесь находятся в обратном порядке. Кроме того, я добавила пару дополнительных проверок в конец, чтобы убедиться, что при вызове pop указатель на хвост не повреждается.

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

нервно смеётся Все эти штуки с unsafe оказались такими простыми, я не понимаю, почему все утверждают обратное. Наша программа прекрасно работает.

ГОЛОС ЗА КАДРОМ: 🙂

…правда?

ГОЛОС ЗА КАДРОМ: 🙂

Хорошо, мы написали небезопасный код и компилятор не может нам помочь с поиском ошибок. Возможно, тесты сработали случайно, а на самом деле у нас там что-то недетерминированное. Какое-то Неопределённое Поведение.

Но что мы можем сделать? Мы выбрались из домика, в котором нас защищал rustc. Теперь нам никто не поможет.

…Подождите, а что это за подозрительный тип в переулке?

“Эй, парень, не хочешь поинтерпретировать немного Rust кода?”

Ннннет… Наверное.

“Чувак, это невероятно, интерпретация может проверить, действительно ли исполнение твоей программы в динамике соответствует семантике модели памяти Rust. Крышу сносит…”

Что?

“Она проверяет, есть ли у тебя Неопределённое Поведение.”

Думаю, один раз я могу попробовать интерпретацию.

“У тебя же установлен rustup, правда?”

Конечно да, это же та самая утилита для поддержания инструментария Rust в актуальном состоянии!

> rustup +nightly-2022-01-21 component add miri

info: syncing channel updates for 'nightly-2022-01-21-x86_64-pc-windows-msvc'
info: latest update on 2022-01-21, rust version 1.60.0-nightly (777bb86bc 2022-01-20)
info: downloading component 'cargo'
info: downloading component 'clippy'
info: downloading component 'rust-docs'
info: downloading component 'rust-std'
info: downloading component 'rustc'
info: downloading component 'rustfmt'
info: installing component 'cargo'
info: installing component 'clippy'
info: installing component 'rust-docs'
info: installing component 'rust-std'
info: installing component 'rustc'
info: installing component 'rustfmt'
info: downloading component 'miri'
info: installing component 'miri'

Что ты только что установил на мой компьютер!?

“Отличную Вещь”

ГОЛОС ЗА КАДРОМ: Есть кое-какие тонкости, касающиеся версии инструментария:

Инструмент, который мы установили — miri — тесно взаимодействует с внутренностями rustc, поэтому доступен только в ночных сборках.

+nightly-2022-01-21 указывает rustup, что мы хотим установить miri вместе с ночной сборкой инструментария за указанную дату. Я использовала конкретную дату, потому что иногда miri содержит ошибки и не компилируется несколько ночей подряд. rustup автоматически загрузит любой инструментарий, который мы укажем с помощью +, если он ещё не установлен.

2022-01-21 — это сборка, где, я точно знаю, miri работает, что можно проверить на этой странице. Если вы счастливчик, можете использовать просто +nightly.

Мы будем использовать синтаксис + при каждом вызове miri через cargo miri для указания версии совместимого инструментария. Если не хотите каждый раз писать версию, запустите rustup override set

> cargo +nightly-2022-01-21 miri test

I will run `"cargo.exe" "install" "xargo"` to install 
a recent enough xargo. Proceed? [Y/n]

Э-Э-Э, ЧТО ЭТО ЗА XARGO?

Не бери в голову, всё в порядке."

> y

    Updating crates.io index
  Installing xargo v0.3.24
...
    Finished release [optimized] target(s) in 10.65s
  Installing C:\Users\ninte\.cargo\bin\xargo-check.exe
  Installing C:\Users\ninte\.cargo\bin\xargo.exe
   Installed package `xargo v0.3.24` (executables `xargo-check.exe`, `xargo.exe`)

I will run `"rustup" "component" "add" "rust-src"` to install 
the `rust-src` component for the selected toolchain. Proceed? [Y/n]

Э-Э??

“Кто же не любит иметь копию исходного кода Rust?”

> y

info: downloading component 'rust-src'
info: installing component 'rust-src'

“Ну, вот, всё готово, а теперь самое интересное.”

   Compiling lists v0.1.0 (C:\Users\ninte\dev\tmp\lists)
    Finished test [unoptimized + debuginfo] target(s) in 0.25s
     Running unittests (lists-5cc11d9ee5c3e924.exe)

error: Undefined Behavior: trying to reborrow for Unique at alloc84055, 
       but parent tag <209678> does not have an appropriate item in 
       the borrow stack

   --> \lib\rustlib\src\rust\library\core\src\option.rs:846:18
    |
846 |             Some(x) => Some(f(x)),
    |                  ^ trying to reborrow for Unique at alloc84055, 
    |                    but parent tag <209678> does not have an 
    |                    appropriate item in the borrow stack
    |
    = help: this indicates a potential bug in the program: 
      it performed an invalid operation, but the rules it 
      violated are still experimental
    = help: see https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md 
      for further information

    = note: inside `std::option::Option::<std::boxed::Box<fifth::Node<i32>>>::map::<i32, [closure@src\fifth.rs:31:30: 40:10]>` at \lib\rustlib\src\rust\library\core\src\option.rs:846:18

note: inside `fifth::List::<i32>::pop` at src\fifth.rs:31:9
   --> src\fifth.rs:31:9
    |
31  | /         self.head.take().map(|head| {
32  | |             let head = *head;
33  | |             self.head = head.next;
34  | |
...   |
39  | |             head.elem
40  | |         })
    | |__________^
note: inside `fifth::test::basics` at src\fifth.rs:74:20
   --> src\fifth.rs:74:20
    |
74  |         assert_eq!(list.pop(), Some(1));
    |                    ^^^^^^^^^^
note: inside closure at src\fifth.rs:62:5
   --> src\fifth.rs:62:5
    |
61  |       #[test]
    |       ------- in this procedural macro expansion
62  | /     fn basics() {
63  | |         let mut list = List::new();
64  | |
65  | |         // Check empty list behaves right
...   |
96  | |         assert_eq!(list.pop(), None);
97  | |     }
    | |_____^
 ...
error: aborting due to previous error

Ого. Какая ужасная ошибка.

“Да, взгляни на это дерьмо. Тебе понравится на него натыкаться.”

Благодарю?

“Вот возьми и бутылочку эстрадиола, она тебе пригодится.”

Подожди, зачем?

“Поверь мне, скоро ты начнёшь думать о моделях памяти.”

ГОЛОС ЗА КАДРОМ: после этого таинственный незнакомец превратился в лису и ускользнул сквозь дыру в стене. Автор несколько минут смотрела в никуда, пытаясь осмыслить произошедшее.

Таинственная лиса оказалась права не только по поводу моего пола: miri — действительно Отличная Вещь.

Так что же такое miri?

Экспериментальный интерпретатор промежуточного представления среднего уровня (Mid-level Intermediate Representation, MIR). Он может запускать бинарники и тестовые наборы из проектов cargo и выявлять целые классы неопределённого поведения, например:

• Выход за границы допустимого диапазона памяти и использование памяти после освобождения

• Недопустимое использование неинициализированных данных

• Нарушение внутренних предусловий (достижение unreachable_unchecked, вызов copy_nonoverlapping с перекрывающимися диапазонами, …)

• Доступ к памяти и ссылкам с недостаточно строгим выравниванием

• Нарушение некоторых базовых инвариантов для типов (значение bool, отличное от 0 и 1 или неизвестная метка перечисления)

• Экспериментально: Нарушение правил многоуровневого заимствования, регулирующих псевдонимы для ссылочных типов

• Экспериментально: Состояние гонки данных (но без эффектов ослабленной модели памяти)

Кроме того, miri сообщит вам об утечках памяти. Если после завершения программы останется выделенная память, недоступная из глобальной статической переменной, miri выдаст ошибку.

…

Однако, имейте в виду, что miri не может обнаружить все случаи неопределённого поведения в вашей программе и не может выполнить любую программу.

В двух словах: он интерпретирует вашу программу и сообщает о всех нарушениях правил во время выполнения, приведших к Неопределённому Поведению. Это нужно, поскольку Неопределённое Поведение происходит именно во время выполнения. Если бы проблему можно было обнаружить на этапе компиляции, компилятор просто выдал бы ошибку!

Возможно, вы знакомы с такими инструментами, как ubsan и tsan. По сути, miri — такой же инструмент, но более полный и продвинутый.

Выглядит так, что за стенами нашего домика miri шастает с ножом в руках. Правда, нож учебный.

Чтобы miri проверил нашу работу, надо запустить его с такими параметрами:

> cargo +nightly-2022-01-21 miri test

Давайте посмотрим, что он вырезал на нашей парте:

error: Undefined Behavior: trying to reborrow for Unique at alloc84055, but parent tag <209678> does not have an appropriate item in the borrow stack

   --> \lib\rustlib\src\rust\library\core\src\option.rs:846:18
    |
846 |             Some(x) => Some(f(x)),
    |                  ^ trying to reborrow for Unique at alloc84055, 
    |                    but parent tag <209678> does not have an 
    |                    appropriate item in the borrow stack
    |

    = help: this indicates a potential bug in the program: it 
      performed an invalid operation, but the rules it 
      violated are still experimental
    
    = help: see 
      https://github.com/rust-lang/unsafe-code-guidelines/blob/master/wip/stacked-borrows.md 
      for further information

Ладно, я вижу, что мы допустили ошибку, но сообщение об ошибке сбивает меня с толку. Что такое «стек заимствований».

Постараемся разобраться с этим в следующей части.

Пытаемся разобраться в стековом заимствовании

В предыдущем разделе мы попытались запустить нашу небезопасную односвязную очередь в miri. Он сказал, что мы нарушили правила стековых заимствований и дал нам ссылку на документацию.

Обычно я разбираю доку, но не в этот раз. На самом деле мы не являемся целевой аудиторией этой документации. Она написана для разработчиков компилятора и академиков, которые работают над семантикой Rust.

Так что я собираюсь дать вам высокоуровневое представление о «стековых заимствований» и рассказать несколько простых правил.

ГОЛОС ЗА КАДРОМ: стековые заимствования остаются «экспериментальными» в качестве семантической модели Rust. Нарушение этих правил не означает, что у вас «неправильная» программа. Но если вы — не разработчик компилятора, лучше просто исправьте программу, если miri на неё ругается. Это намного безопаснее, чем жалеть, когда возникнет Неопределённое Поведение.

Причина: псевдономизация указателей

Перед тем, как узнать, какие правила мы нарушили, полезно разобраться, почему эти правила вообще существуют. Есть несколько различных причин, из-за которых возникают проблемы, но я думаю, что самой важной является псевдономизация указателей.

Мы называем два указателя псевдонимами, если они указывают на перекрывающиеся области памяти. Как кого-то «известного под псевдонимом» можно называть двумя различными именами, так и область памяти может быть доступна через два различных указателя. И это может приводить к проблемам.

Компилятор использует информацию о псевдономизации указателя, чтобы оптимизировать доступ к памяти, так что если информация, на которую он опирается ошибочная, программа скомпилируется неправильно и будет выдавать случайный мусор.

ГОЛОС ЗА КАДРОМ: на практике, псевдономизация больше связана с доступом к памяти, чем с самими указателями, и имеет значение только тогда, когда один из указателей является изменяющим. Внимание к указателям связано с тем, что к ним удобно прикреплять правила.

Чтобы понять, почему информация о псевдономизации указателей так важна, послушайте Притчу о сердитом человечке.

Однажды Михил осматривал свои книжные полки и увидел незнакомую книгу. Сняв её с полки, он посмотрел на обложку.

«Ах, да, мой старый экземпляр Войны и мира, книга, которую я наверняка прочитал. Люблю часть, посвящённую миру.»

Внезапно в дверь постучали. Михил вернул книгу на полку и открыл дверь — там стояла его непримиримая противница Хамслава.

«Привет, Хамслава, ты когда-нибудь читала Войну и мир?»

«Пффф, на самом деле никто не читал Войну и мир.»

«Ну, а я читал, смотри, она у меня прямо на полке, что очевидно означает, что я её прочёл.»

Хамслава не могла в это поверить. Её лицо сменило обычное самодовольное выражение на железную маску ярости и решимости. Оттолкнув Михила в сторону, Хамслава решительным шагом направилась к книжной полке, с яростью тысячи Валькирий вырвала том с его законного места. Она перевернула в руках древний текст и, увидев обложку, задрожала.

Михил уже был готов насладиться своим очевидным превосходством, но его прервал внезапный смех Хамславы.

«Это не Война и мир, это Война и тир!

Слёзы текли по лицу Хамславы. Несомненно, это был лучший момент в её жизни.

«Н-нет! Я же только что смотрел!»

Он вырвал книгу из рук Хамславы и посмотрел на обложку. Действительно, слово «мир» было зачёркнуто и исправлено на «тир». Михил в ужасе застыл. Несомненно, это был худший момент в его жизни.

Он упал на колени и беспомощно уставился на книжный шкаф. Как это могло произойти? Он же видел обложку мгновенье назад!

Тут он заметил какое-то движение в шкафу. Это был человечек. Человечек с самым сердитым выражением лица, которое Михил когда-либо видел. Он показал Михилу средний палец и, сказав «тебе никто не поверит», скрылся между книгами.

План Михила был идеальным, но не учитывал появления сердитого человечка с маркером в руках и жаждой разрушения в душе. Он думал, что знает, что написано на обложке и считал, что никто не может этого изменить. Но, увы, он ошибался.

А Хамслава в красках описала свою невероятную победу в стенгазете, так что репутация Михила в местном Интернет-кафе была разрушена навсегда.

Никто не хочет оказаться на месте Михила, но никто не хочет и жить в постоянном страхе перед сердитым человечком. Нам бы хотелось знать, когда этот сердитый человечек может над нами подшутить. В этот момент мы были бы очень осторожны, и параноидально проверяли бы всё перед использованием. Но в обычных условиях мы бы хотели доверять собственной памяти.

Именно в этом (упрощённо) и заключается ключевой момент псевдономизации: компилятор хотел бы знать, когда безопасно «запоминать» (кешировать) значения, вместо того, чтобы загружать их снова и снова. А для этого компилятору надо знать про все случаи, когда сердитый человечек мог бы изменить память за вашей спиной.

ГОЛОС ЗА КАДРОМ: компилятор также использует эту информацию для кеширования хранений, то есть он избегает отправки данные в память, если думает, это этого никто не заметит. Причина проблемы всё ещё в сердитых человечках, но им надо прочитать память, чтобы проблема проявилась.

Безопасные стековые заимствования

Ладно, значит мы хотим, чтобы у компилятора была полная информация о псевдономизации указателей. Можно ли её предоставить? Ну, выглядит так, что Rust для этого и спроектирован. Изменяемые ссылки по определению не могут иметь псевдонимов, а разделяемые ссылки, хотя и могут быть псевдонимами друг друга, не могут изменяться. Прекрасно. Отправляй в прод!

На самом деле всё гораздо сложнее. Мы можем «повторно заимствовать» изменяемые указатели. Например:

let mut data = 10;
let ref1 = &mut data;
let ref2 = &mut *ref1;

*ref2 += 2;
*ref1 += 1;

println!("{}", data);

Компилируется и запускается без проблем. Почему?

Мы поймём, что здесь происходит, если поменяем две строки местами:

let mut data = 10;
let ref1 = &mut data;
let ref2 = &mut *ref1;

// ПОРЯДОК ИЗМЕНИЛСЯ!
*ref1 += 1;
*ref2 += 2;

println!("{}", data);

error[E0503]: cannot use `*ref1` because it was mutably borrowed
 --> src/main.rs:6:5
  |
4 |     let ref2 = &mut *ref1;
  |                ---------- borrow of `*ref1` occurs here
5 |     
6 |     *ref1 += 1;
  |     ^^^^^^^^^^ use of borrowed `*ref1`
7 |     *ref2 += 2;
  |     ---------- borrow later used here

For more information about this error, try `rustc --explain E0503`.
error: could not compile `playground` due to previous error

Внезапно теперь мы получаем ошибку компилятора!

Когда мы повторно заимствуем изменяемый указатель, оригинальный указатель нельзя использовать, пока заимствование не закончится.

В коде, который работает присутствует удобная вложенность использований. Мы повторно заимствуем новый указатель, используем его, а затем перестаём использовать, прежде чем вернуться к старому указателю. В коде, который не работает, всё не так. Мы чередуем использования в произвольном порядке.

Именно так у нас могут одновременно быть и несколько заимствований и, и информация о псевдонимизации. Все наши заимствования явным образом упорядочены и в каждый момент времени только одно из них можно считать «живым».

Эй, а вы знаете, как лучше всего представить штуки, упорядоченные явным образом? В виде стека. Стека заимствований.

Ага, вот и стек заимствований!

Объект, находящийся на вершине стека, является «живым» и знает, что у него фактически нет псевдонимов. Когда вы заимствуете указатель повторно, новый указатель вставляется в начало стека, становясь новым живым указателем. Когда вы используете старый указатель, он возвращается к жизни путём удаления из стека всех указателей выше него. В этой точке указатель «знает», что был заимствован и что память могла быть изменена, но теперь он снова имеет эксклюзивный доступ — нет надобности беспокоиться о сердитом человечке.

В общем, нет ничего страшного в обращении к повторно заимствованному указателю, поскольку мы всегда можем удалить всё, что находится выше него. Реальная проблема возникает при доступе к указателю, который уже удалён из стека заимствований — тогда у вас всё ломается.

К счастью, конструкция анализатора заимствований гарантирует, что безопасные Rust-программы следуют этим правилам, что мы и видели в первом примере. Но компилятор, если сравнивать со стековыми заимствованиями, видит проблему «задом наперёд». С точки зрения стековых заимствований ref1 ломает ref2. Компилятор настаивает, что ref2 должен быть корректным в течение всего времени использования, и что ref1 нарушает порядок, действуя вне очереди.

Поэтому и «нельзя использовать *ref1, поскольку это изменяемое заимствование». Тот же самый результат, но, возможно, оформленный в более интуитивном виде (особенно,когда речь идёт о не-лексическом времени жизни).

Но анализатор заимствований не может помочь нам, если мы используем небезопасные указатели!

Небезопасные стековые заимствования

Итак, мы хотим заставить небезопасные указатели участвовать в системе стековых заимствований, даже если компилятор не может их корректно отслеживать. Также мы хотим, чтобы система была достаточно гибкой, чтобы её нельзя было сломать слишком легко и вызвать UB.

Это трудная проблема, и я не знаю, как её решить, но ребята, работавшие над стековыми заимствованиями, придумали что-то, что внушает доверие, и miri пытается воплотить эти идеи.

В самом общем смысле, когда вы преобразуете ссылку (или любой другой безопасный указатель) в сырой указатель, то по сути это выглядит, как повторное заимствование. Поэтому сырой указатель может делать с памятью, что захочет, а когда срок заимствования истечёт, всё будет так же, как и при обычном повторном заимствовании.

Весь вопрос в том, когда истекает срок повторного заимствования? Ну, кажется, что лучшее время для завершения заимствования, это когда вы начинаете использовать оригинальную ссылку. В противном случае всё это не выглядит как аккуратный вложенный стек.

Но подождите, вы можете превратить сырой указатель в ссылку! И вы можете копировать сырые указатели! Что будет, если вы сделаете &mut -> *mut -> &mut -> *mut, а затем обратитесь к первому *mut? Как, блин, стековые заимствования работают в этом случае?

Честно говоря, я не знаю! Вот почему всё так сложно. На самом, всё ещё сложнее, потому что стековые заимствования пытаются быть снисходительными и позволяют небезопасному коду работать способами, которых вы от него ожидаете. Вот поэтому я запускаю miri, чтобы попытаться найти ошибки.

Именно эта неразбериха является причиной появления экстра-экспериментального экстра-строгого режима miri: -Zmiri-tag-raw-pointers.

Чтобы включить этот режим, надо передать флаг через переменную окружения MIRIFLAGS:

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test

Или можно установить переменную глобально, как в Windows:

$env:MIRIFLAGS="-Zmiri-tag-raw-pointers"
cargo +nightly-2022-01-21 miri test

В целом, мы будем придерживаться этого экстра-строгого режима, просто чтобы быть экстра уверенными в нашей работе. Помимо прочего, он в некотором смысле «проще» и лучше подходит для экспериментов и формирования интуитивного понимания стековых заимствований.

Управление стековыми заимствованиями

При использовании сырых указателей мы будем придерживаться простой и понятной эвристики, которая, как я надеюсь, имеет большую толерантность к ошибкам:

Как только вы стали использовать сырые указатели, старайтесь использовать ТОЛЬКО сырые указатели.

Это сильно снижает возможность непредумышленной потери «права» сырого указателя на доступ к памяти.

ГОЛОС ЗА КАДРОМ: у этого упрощения есть два аспекта:

1. У безопасных указателей часто есть другие свойства, помимо псевдономизации: память выделена, выровнена, её достаточно для хранения объекта указывания, объект указывания инициализирован и т. д. Поэтому так опасно разбрасывать их везде, когда они находятся в нестабильном состоянии.

2. Даже если вы используете только сырые указатели, вы не можете использовать псевдонимы для доступа к любой памяти. Указатели концептуально привязаны к определённым «областям выделенной памяти» (которые могут быть такими же мелкими, как и локальная переменная на стеке). Нельзя просто взять указатель на одну область, прибавить к нему смещение и получить указатель на другую область. Если бы это было возможно, угроза сердитых человечков была бы всегда и везде. Именно по этой причине точка зрения «указатели — всего лишь целые числа» является проблематичной.

В то же время мы хотим, чтобы в нашем интерфейсе были только безопасные ссылки, чтобы строить красивые безопасные абстракции и чтобы пользователю нашего списка не нужно было ни о чём беспокоиться.

Вот что мы будем делать:

1. В начале метода используем входные ссылки, чтобы получить сырые указатели

2. Далее будем использовать только сырые указатели

3. В конце, если нужно, преобразуем сырые указатели в безопасные указатели

Поскольку поля наших типов приватны, мы будем хранить их в виде сырых указателей.

Фактически, часть большой ошибки, которую мы совершили, заключается в том, что мы продолжили использовать Box! Box имеет специальную аннотацию, которая говорит компилятору, что «эта штука очень похожа на &mut, потому что эксклюзивно владеет указателем». И это правда!

Но сырой указатель, в котором мы хранили конец списка, указывает на Box, поэтому всякий раз, когда мы обращаемся к Box, мы, возможно, ломаем повторное заимствование этого сырого указателя!

В следующем разделе мы вернёмся в нашему привычному формату и разберёмся с целым ворохом непростых примеров.

Тестирование стековых заимствований

Подытожим, что мы (упрощённо) знаем о подели памяти Rust, опираясь на предыдущие разделы:

• Концептуально, обработка повторных заимствований в Rust осуществляется через «стек заимствований»

• Единственный указатель на вершине стека считается «живым» (имеет эксклюзивный доступ)

• При доступе через указатель из глубины стека, «живым» становится он, а указатели выше него удаляются из стека

• Нельзя использовать указатели, которые были удалены из стека заимствований

• Анализатор зависимостей гарантирует, что безопасный код соответствуем этим требованиям

• Miri (в теории) проверяет, что сырые указатели соответствуют этим правилам во время выполнения

В прошлой части было много теории и идей. Теперь давайте перейдём к истинной сути этой книги — написанию плохого кода и тому, как заставить наши инструменты ругаться на этот код. Мы разберём груды примеров, чтобы понять, работает ли наша ментальная модель, а также попытаемся прочувствовать стековые заимствования на интуитивном уровне.

ГОЛОС ЗА КАДРОМ: обнаружение Неопределённого Поведения — это хлопотное дело. Помимо прочего, мы имеем дело с ситуациями, которые компилятор буквально полагает невозможными.

Если вы счастливчик, программа будет «казаться работающей», при этом она будет содержать бомбу замедленного действия для Более Умного Компилятора или небольшого изменения в коде. Если вы настоящий счастливчик, программа гарантированно не будет работать, так что вы сможете найти ошибку и исправить её. Но если вы не счастливчик, программа будет ломаться странным и непонятным образом.

Miri пытается работать обойти эту проблему, получая от rustc простейшее не оптимизированное представление программы и следя за её состоянием при интерпретации. «Средства динамического анализа» (sanitizers) — довольно детерминированный и надёжный подход, он он никогда не будет совершенным. Ваша тестовая программа должна дойти до точки с UB, однако во многих программах пышным цветом цветёт разного рода недетерминированное поведение (скажем, HashMap по умолчанию использует датчик случайных чисел).

Ни при каких обстоятельствах мы не должны считать, что отсутствие предупреждений miri означает полное отсутствие UB в нашей программе. В то же время, бывает, что miri думает, будто нашла UB, но на самом деле это не так. Если у нас есть ментальная модель работы указателей, и miri с нами согласна — это хороший знак, что мы на правильном пути.

Базовые заимствования

В предыдущих разделах мы видели, что анализатору заимствований не нравится такой код:

let mut data = 10;
let ref1 = &mut data;
let ref2 = &mut *ref1;

// ПОРЯДОК ИЗМЕНИЛСЯ!
*ref1 += 1;
*ref2 += 2;

println!("{}", data);

Давайте посмотрим, что случится, если мы заменим ref2 на *mut:

unsafe {
    let mut data = 10;
    let ref1 = &mut data;
    let ptr2 = ref1 as *mut _;

    // ПОРЯДОК ИЗМЕНИЛСЯ!
    *ref1 += 1;
    *ptr2 += 2;

    println!("{}", data);
}

cargo run
   Compiling miri-sandbox v0.1.0
    Finished dev [unoptimized + debuginfo] target(s) in 0.71s
     Running `target\debug\miri-sandbox.exe`
13

Кажется, rustc всё устраивает: никаких предупреждений и программа выдала ожидаемый результат! Теперь посмотрим, что об этом думает miri (в строгом режиме):

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

    Finished dev [unoptimized + debuginfo] target(s) in 0.00s
     Running cargo-miri.exe target\miri

error: Undefined Behavior: no item granting read access 
to tag <untagged> at alloc748 found in borrow stack.

 --> src\main.rs:9:9
  |
9 |         *ptr2 += 2;
  |         ^^^^^^^^^^ no item granting read access to tag <untagged> 
  |                    at alloc748 found in borrow stack.
  |
  = help: this indicates a potential bug in the program: 
    it performed an invalid operation, but the rules it 
    violated are still experimental
 

Отлично! Наша интуитивная модель подтвердилась: хотя компилятор не смог обнаружить проблему, miri смогла.

Давайте попробуем более сложное преобразование &mut -> *mut -> &mut -> *mut, о котором мы говорили ранее:

unsafe {
    let mut data = 10;
    let ref1 = &mut data;
    let ptr2 = ref1 as *mut _;
    let ref3 = &mut *ptr2;
    let ptr4 = ref3 as *mut _;

    // Сначала обращаемся к первому сырому указателю
    *ptr2 += 2;

    // Затем обращаемся к переменным в порядке «стека заимствований»
    *ptr4 += 4;
    *ref3 += 3;
    *ptr2 += 2;
    *ref1 += 1;

    println!("{}", data);
}

cargo run
22

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: no item granting read access 
to tag <1621> at alloc748 found in borrow stack.

  --> src\main.rs:13:5
   |
13 |     *ptr4 += 4;
   |     ^^^^^^^^^^ no item granting read access to tag <1621> 
   |                at alloc748 found in borrow stack.
   |

Да, да! В строгом режиме miri смогла «различить» два сырых указателя, обнаружив, что использование второго ведёт к порче первого. Давайте посмотрим, начнёт ли всё работать, когда мы удалим первое использование, которое всё сломало:

unsafe {
    let mut data = 10;
    let ref1 = &mut data;
    let ptr2 = ref1 as *mut _;
    let ref3 = &mut *ptr2;
    let ptr4 = ref3 as *mut _;

    // Обращаемся к переменным в порядке «стека заимствований»
    *ptr4 += 4;
    *ref3 += 3;
    *ptr2 += 2;
    *ref1 += 1;

    println!("{}", data);
}

cargo run
20

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
20

ОТЛИЧНО.

Я почти уверена, что к настоящему моменту мы можем получить докторскую степень по проектированию и реализации моделей памяти в языках программирования. Кому вообще нужны компиляторы, если это так просто?

ГОЛОС ЗА КАДРОМ: это не так, но я всё равно тобой горжусь.

Тестирование массивов

Поэкспериментируем с массивами и смещениями указателей (сложением и вычитанием). Будет ли работать этот код?

unsafe {
    let mut data = [0; 10];
    let ref1_at_0 = &mut data[0];           // Ссылка на 0-й элемент
    let ptr2_at_0 = ref1_at_0 as *mut i32;  // Указатель на 0-й элемент
    let ptr3_at_1 = ptr2_at_0.add(1);       // Указатель на 1-й элемент

    *ptr3_at_1 += 3;
    *ptr2_at_0 += 2;
    *ref1_at_0 += 1;

    // Должно быть [3, 3, 0, ...]
    println!("{:?}", &data[..]);
}

cargo run
[3, 3, 0, 0, 0, 0, 0, 0, 0, 0]

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: no item granting read access 
to tag <1619> at alloc748+0x4 found in borrow stack.
 --> src\main.rs:8:5
  |
8 |     *ptr3_at_1 += 3;
  |     ^^^^^^^^^^^^^^^ no item granting read access to tag <1619>
  |                     at alloc748+0x4 found in borrow stack.

Рвёт заявление в докторантуру

Что случилось? Мы же прекрасно используем стек заимствований! Можем быть, причина в том, что мы преобразуем ptr -> ptr? Попробуем просто скопировать указатель, чтобы оба указателя указывали на один и тот же элемент:

unsafe {
    let mut data = [0; 10];
    let ref1_at_0 = &mut data[0];           // Ссылка на 0-й элемент
    let ptr2_at_0 = ref1_at_0 as *mut i32;  // Указатель на 0-й элемент
    let ptr3_at_0 = ptr2_at_0;              // Указатель на 0-й элемент

    *ptr3_at_0 += 3;
    *ptr2_at_0 += 2;
    *ref1_at_0 += 1;

    // Должно быть [6, 0, 0, ...]
    println!("{:?}", &data[..]);
}

cargo run
[6, 0, 0, 0, 0, 0, 0, 0, 0, 0]

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
[6, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Нет, такой код прекрасно работает. Может быть, нам просто повезло. Давайте как следует перетасуем указатели:

unsafe {
    let mut data = [0; 10];
    let ref1_at_0 = &mut data[0];            // Ссылка на 0-й элемент
    let ptr2_at_0 = ref1_at_0 as *mut i32;   // Указатель на 0-й элемент
    let ptr3_at_0 = ptr2_at_0;               // Указатель на 0-й элемент
    let ptr4_at_0 = ptr2_at_0.add(0);        // Указатель на 0-й элемент
    let ptr5_at_0 = ptr3_at_0.add(1).sub(1); // Указатель на 0-й элемент

    // Абсолютно беспорядочная мешанина использования указателей
    *ptr3_at_0 += 3;
    *ptr2_at_0 += 2;
    *ptr4_at_0 += 4;
    *ptr5_at_0 += 5;
    *ptr3_at_0 += 3;
    *ptr2_at_0 += 2;
    *ref1_at_0 += 1;

    // Должно быть [20, 0, 0, ...]
    println!("{:?}", &data[..]);
}

cargo run
[20, 0, 0, 0, 0, 0, 0, 0, 0, 0]

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
[20, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Нет! На самом деле, miri гораздо снисходительнее, если речь идёт о сырых указателях, производных от других сырых указателей. Все они разделяют одно и то же «заимствование» (или, как miri его называет, маркер).

Как только вы начинаете использовать сырые указатели, они провоцируют появление сердитых человечков, которые начинают мешать. Но это нормально, и поэтому компилятор не будет оптимизировать чтение и запись также, как в случае ссылок.

ГОЛОС ЗА КАДРОМ: Если код достаточно простой, компилятор отслеживает производные указатели и продолжает оптимизацию, если это возможно. Однако эта часть компилятора достаточно капризная.

Так в чём же реальная проблема?

Несмотря на то, что data — это один «кусок памяти» (одна локальная переменная), ref1_at_0 заимствует только первый элемент. Rust позволяет разбивать заимствования на части, чтобы они применялись к разным частям выделенной памяти! Давайте попробуем:

unsafe {
    let mut data = [0; 10];
    let ref1_at_0 = &mut data[0];           // Ссылка на 0-й элемент
    let ref2_at_1 = &mut data[1];           // Ссылка на 1-й элемент
    let ptr3_at_0 = ref1_at_0 as *mut i32;  // Указатель на 0-й элемент
    let ptr4_at_1 = ref2_at_1 as *mut i32;  // Указатель на 1-й элемент

    *ptr4_at_1 += 4;
    *ptr3_at_0 += 3;
    *ref2_at_1 += 2;
    *ref1_at_0 += 1;

    // Должно быть [4, 6, 0, ...]
    println!("{:?}", &data[..]);
}

error[E0499]: cannot borrow `data[_]` as mutable more than once at a time
 --> src\main.rs:5:21
  |
4 |     let ref1_at_0 = &mut data[0];           // Reference to 0th element
  |                     ------------ first mutable borrow occurs here
5 |     let ref2_at_1 = &mut data[1];           // Reference to 1th element
  |                     ^^^^^^^^^^^^ second mutable borrow occurs here
6 |     let ptr3_at_0 = ref1_at_0 as *mut i32;  // Ptr to 0th element
  |                     --------- first borrow later used here
  |
  = help: consider using `.split_at_mut(position)` or similar method 
    to obtain two mutable non-overlapping sub-slices

Блин! Rust не отслеживает индексы массива, чтобы доказать, что эти заимствования не пересекаются, но он предоставляет нам метод split_at_mut позволяющий безопасности разделить срез на несколько частей:

unsafe {
    let mut data = [0; 10];

    let slice1 = &mut data[..];
    let (slice2_at_0, slice3_at_1) = slice1.split_at_mut(1); 
    
    let ref4_at_0 = &mut slice2_at_0[0];    // Ссылка на 0-й элемент
    let ref5_at_1 = &mut slice3_at_1[0];    // Ссылка на 1-й элемент
    let ptr6_at_0 = ref4_at_0 as *mut i32;  // Указатель на 0-й элемент
    let ptr7_at_1 = ref5_at_1 as *mut i32;  // Указатель на 1-й элемент

    *ptr7_at_1 += 7;
    *ptr6_at_0 += 6;
    *ref5_at_1 += 5;
    *ref4_at_0 += 4;

    // Должно быть [10, 12, 0, ...]
    println!("{:?}", &data[..]);
}

cargo run
[10, 12, 0, 0, 0, 0, 0, 0, 0, 0]

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
[10, 12, 0, 0, 0, 0, 0, 0, 0, 0]

Да, так работает! Срезы сообщают компилятору и miri: «Эй, я владею куском памяти в этом диапазоне», так что они знают, что все элементы могут быть изменены.

Обратите внимание, что операции наподобие split_at_mut позволяют нам утверждать, что заимствования организуются не в виде стека, а в виде дерева, так как мы можем разбить одно большое заимствование на несколько непересекающихся маленьких, и всё будет работать.

(Мне кажется, что в самой модели заимствований всё продолжает считаться стеком, потому что стек концептуально отслеживает права доступа к каждому байту программы.)

А что, если мы напрямую преобразуем срез в указатель? Будет ли этот указатель иметь доступ к полному срезу?

unsafe {
    let mut data = [0; 10];

    let slice1_all = &mut data[..];         // Срез всего массива
    let ptr2_all = slice1_all.as_mut_ptr(); // Указатель на весь массив
    
    let ptr3_at_0 = ptr2_all;               // Указатель на (тот же) 0-й элемент
    let ptr4_at_1 = ptr2_all.add(1);        // Указатель на 1-й элемент
    let ref5_at_0 = &mut *ptr3_at_0;        // Ссылка на 0-й элемент
    let ref6_at_1 = &mut *ptr4_at_1;        // Ссылка на 1-й элемент

    *ref6_at_1 += 6;
    *ref5_at_0 += 5;
    *ptr4_at_1 += 4;
    *ptr3_at_0 += 3;

    // Просто для смеха, поменяем все элементы в цикле
    // (Для этого можно использовать любой из сырых указателей, так как они разделяют заимствование!)
    for idx in 0..10 {
        *ptr2_all.add(idx) += idx;
    }

    // Безопасная версия того же самого кода, для развлечения
    for (idx, elem_ref) in slice1_all.iter_mut().enumerate() {
        *elem_ref += idx; 
    }

    // Должно быть [8, 12, 4, 6, 8, 10, 12, 14, 16, 18]
    println!("{:?}", &data[..]);
}

cargo run
[8, 12, 4, 6, 8, 10, 12, 14, 16, 18]

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
[8, 12, 4, 6, 8, 10, 12, 14, 16, 18]

Прекрасно! Указатели — это не просто целые числа: у них есть область памяти, ассоциированная с ними, и с помощью Rust мы можем сузить эту область!

Тестирование разделяемых ссылок

Во всех наших примерах я использовала только изменяемые ссылки и применяла операции чтения-изменения-записи (+=), чтобы не привносить в код ненужной сложности.

Но в Rust есть разделяемые ссылки, которые предназначены только для чтения и могут быть свободно скопированы. Как будут работать они? Ладно, мы видели, что сырые указатели можно свободно копировать и что с ними можно работать, считая, что копии «разделяют» единственное заимствование. Нельзя ли подобным образом думать и о разделяемых ссылках?

Давайте проверим наше предположение с помощью функции, которая читает значение. (Макрос `println! может работать волшебным образом, когда речь заходит о получении и разыменовании ссылок, так что я завернула его в функцию, чтобы быть уверенной, что мы тестируем то, что нужно):

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = 10;
    let mref1 = &mut data;
    let sref2 = &mref1;
    let sref3 = sref2;
    let sref4 = &*sref2;

    // Читаем разделяемые ссылки в случайном порядке
    opaque_read(sref3);
    opaque_read(sref2);
    opaque_read(sref4);
    opaque_read(sref2);
    opaque_read(sref3);

    *mref1 += 1;

    opaque_read(&data);
}

cargo run

warning: unnecessary `unsafe` block
 --> src\main.rs:6:1
  |
6 | unsafe {
  | ^^^^^^ unnecessary `unsafe` block
  |
  = note: `#[warn(unused_unsafe)]` on by default

warning: `miri-sandbox` (bin "miri-sandbox") generated 1 warning

10
10
10
10
10
11

Ах, да, мы не делаем с сырыми указателями ничего потенциально опасного, поэтому компилятор ругается на нужный unsafe. Но, по крайней мере мы видим, что использовать разделяемые указатели совместно — вполне нормально. Добавим несколько сырых указателей:

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = 10;
    let mref1 = &mut data;
    let ptr2 = mref1 as *mut i32;
    let sref3 = &mref1;
    let ptr4 = sref3 as *mut i32;

    *ptr4 += 4;
    opaque_read(sref3);
    *ptr2 += 2;
    *mref1 += 1;

    opaque_read(&data);
}

cargo run

error[E0606]: casting `&&mut i32` as `*mut i32` is invalid
  --> src\main.rs:11:16
   |
11 |     let ptr4 = sref3 as *mut i32;
   |                ^^^^^^^^^^^^^^^^^

Ой, извините, на самом деле мы работали с & &mut вместо &! Rust очень хорошо умеет скрывать такие вещи, когда они не имеют значения. Сделаем правильное повторное заимствование: let sref3 = &*mref1:

cargo run

error[E0606]: casting `&i32` as `*mut i32` is invalid
  --> src\main.rs:11:16
   |
11 |     let ptr4 = sref3 as *mut i32;
   |                ^^^^^^^^^^^^^^^^^

Нет, Rust всё ещё не в восторге от нашего кода! Разделяемую ссылку можно приводить только к указателю *const, доступному только для чтения. Но что, если мы просто… сделаем… так…?

    let ptr4 = sref3 as *const i32 as *mut i32;

cargo run

14
17

ЧТО? ПРОСТО РАБОТАЕТ? Отличная система приведения типов, Rust. Выглядит так, как будто *const — это практически бесполезный тип, нужный только для описания C API и правильных сценариев использования (на самом деле, так и есть). А что по этому поводу думает miri?

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: no item granting write access to 
tag <1621> at alloc742 found in borrow stack.
  --> src\main.rs:13:5
   |
13 |     *ptr4 += 4;
   |     ^^^^^^^^^^ no item granting write access to tag <1621>
   |                at alloc742 found in borrow stack.

К сожалению, хотя с помощью двойного приведения мы можем избавиться от жалоб компилятора, это не делает операцию *разрешённой". Получая разделяемую ссылку, мы обещаем не модифицировать значение.

Это важно, потому что когда мы удаляем разделяемое заимствование из стека заимствований, изменяемые указатели перед ним могут быть уверены, что память не изменилась. Может быть, какие-то сердитые человечки и читали память, но у них не было возможности её изменить, так что изменяемые указатели могут предполагать, что последнее значение, которое они записали, всё ещё там!

Как только в стек заимствований попадает разделяемая ссылка, всё, что вставляется после неё, обладает только правами на чтение.

Однако мы можем сделать так:

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = 10;
    let mref1 = &mut data;
    let ptr2 = mref1 as *mut i32;
    let sref3 = &*mref1;
    let ptr4 = sref3 as *const i32 as *mut i32;

    opaque_read(&*ptr4);
    opaque_read(sref3);
    *ptr2 += 2;
    *mref1 += 1;

    opaque_read(&data);
}

Обратите внимание, что создание изменяемого сырого указателя считается «нормальным», если мы только читаем его данные!

cargo run
10
10
13

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
10
10
13

И, на всякий случай давайте убедимся, что разделяемая ссылка удаляется из стека заимствований как надо:

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = 10;
    let mref1 = &mut data;
    let ptr2 = mref1 as *mut i32;
    let sref3 = &*mref1;

    *ptr2 += 2;
    opaque_read(sref3); // Читаем в неправильном порядке?
    *mref1 += 1;

    opaque_read(&data);
}

cargo run
12
13

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: trying to reborrow for SharedReadOnly 
at alloc742, but parent tag <1620> does not have an appropriate 
item in the borrow stack

  --> src\main.rs:13:17
   |
13 |     opaque_read(sref3); // Read in the wrong order?
   |                 ^^^^^ trying to reborrow for SharedReadOnly 
   |                       at alloc742, but parent tag <1620> 
   |                       does not have an appropriate item 
   |                       in the borrow stack
   |

Смотрите, мы получили другое сообщение об ошибке. Теперь вместо вообщения о конкретном маркере, речь идёт о SharedReadOnly. Это логично: как только появляется несколько разделяемых ссылок, все они объединяются в один большой объект SharedReadOnly, так как незачем различать конкретные ссылки!

Тестирование внутренней изменчивости

Помните ту действително ужасную главу, где мы пытались написать связный список с помощью RefCell и Rc? Ту, где всё было даже хуже, чем обычно?

Всё это время мы настаивали, что разделяемые ссылки нельзя использовать для изменения, но вся та глава была про то, что на самом деле мы можем менять значения разделяемых ссылок с помощью внутренней изменчивости. Пришла время исследовать простой и удобный тип std::cell::Cell:

use std::cell::Cell;

unsafe {
    let mut data = Cell::new(10);
    let mref1 = &mut data;
    let ptr2 = mref1 as *mut Cell<i32>;
    let sref3 = &*mref1;

    sref3.set(sref3.get() + 3);
    (*ptr2).set((*ptr2).get() + 2);
    mref1.set(mref1.get() + 1);

    println!("{}", data.get());
}

Ах, какая великолепная мешанина! Будет здорово увидеть, как miri её обругает.

cargo run
16

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
16

Подождите, правда? Тут всё нормально? Почему? Как? Что вообще такое эта ячейка Cell?

Расчехляет стандартную библиотеку

pub struct Cell<T: ?Sized> {
    value: UnsafeCell<T>,
}

Что это за ерундовина, UnsafeCell?

Расчехляет дальше, просто чтобы показать стандартной библиотеке, что мы настроены серьёзно

#[lang = "unsafe_cell"]
#[repr(transparent)]
#[repr(no_niche)]
pub struct UnsafeCell<T: ?Sized> {
    value: T,
}

А, так это магия. Понятно. Наверное. #[lang = "unsafe_cell"] — это буквально способ сказать, что UnsafeCell — это UnsafeCell. Давайте не будем больше расчехлять код, а проверим актуальную документацию на std::cell::UnsafeCell.

Базовый примитив для реализации внутренней изменчивости в Rust.

Если у вас есть ссылка &T, компилятор Rust оптимизирует код, рассчитывая на то, что &T ссылается на неизменяемые данные. Изменение этих данных, например, через псевдоним или после преобразования &T в &mut T ведёт к неопределённому поведению. UnsafeCell<T> отключает гарантию неизменяемости для &T: разделяемая ссылка &UnsaveCell<T> ссылается на данные, которые могут измениться. Это называется «внутренней изменчивостью».

А, так это на самом деле просто магия.

По сути, UnsafeCell говорит компилятору: «Эй, послушай, мы будем прикалываться с этой памятью, так что не делай по поводу её никаких обычных предположений». Это как повесить большой знак «ВНИМАНИЕ: ПЕРЕХОД ДЛЯ СЕРДИТЫХ ЧЕЛОВЕЧКОВ».

Провеим, действительно ли UnsafeCell может осчастливить miri:

use std::cell::UnsafeCell;

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = UnsafeCell::new(10);
    let mref1 = data.get_mut();      // Получаем изменяемиую ссылку на содержимое
    let ptr2 = mref1 as *mut i32;
    let sref3 = &*ptr2;

    *ptr2 += 2;
    opaque_read(sref3);
    *mref1 += 1;

    println!("{}", *data.get());
}

cargo run
12
13

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: trying to reborrow for SharedReadOnly
at alloc748, but parent tag <1629> does not have an appropriate
item in the borrow stack

  --> src\main.rs:15:17
   |
15 |     opaque_read(sref3);
   |                 ^^^^^ trying to reborrow for SharedReadOnly 
   |                       at alloc748, but parent tag <1629> does
   |                       not have an appropriate item in the
   |                       borrow stack
   |

Подождите, что? Мы же сказали заклинание! Куда теперь мне девать всю эту сертифицированную кровь для жертвоприношений?

Что ж, начали мы правильно, но затем всё испортили, вызвав get_mut, который взял UnsafeCell и превратил его в полноценный &mut i32.

Подумайте об этом: если компилятор считает, что &mut i32 может изменить UnsafeCell, он вообще не может делать никаких предположений! Код, полный сердитых человечков.

Нам надо оставить UnsafeCel в наших типах указателей, чтобы компилятор понимал, что мы хотим сделать.

use std::cell::UnsafeCell;

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = UnsafeCell::new(10);
    let mref1 = &mut data;              // Изменяемая ссылка на *весь объект*
    let ptr2 = mref1.get();             // Получаем сырой указатель на содержимое
    let sref3 = &*mref1;                // Получаем разделяемую ссылку на *весь объект*

    *ptr2 += 2;                         // Меняем значение по сырому указателю
    opaque_read(&*sref3.get());         // Читаем из разделяемой ссылки
    *sref3.get() += 3;                  // Пишем через разделяемую ссылку
    *mref1.get() += 1;                  // Меняем через изменяемую ссылку

    println!("{}", *data.get());
}

cargo run
12
16

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
12
16

Заработало! В итоге мне не придётся выливать всю эту жертвенную кровь.

На самом деле, эй, подождите. Мы всё ещё не до конца разобрались с порядком. Сначала мы создали ptr2, а затем создали sref3 из изменяемого указателя. А потом мы использовали сырой указатель перед разделяемым указателем. Это кажется… неправильным.

Но ведь мы делали то же самое и в примере с Cell. Хммм.

Мы должны один из двух выводов:

• Miri несовершенна и на самом деле у нас здесь UB.

• Наша упрощённая модель оказалсь чрезмерно упрощённой.

Я бы поставила на второй вариант, но, просто чтобы быть уверенной, сделаю версию, которая будет абсолютно надёжной в нашей упрощённой модели:

use std::cell::UnsafeCell;

fn opaque_read(val: &i32) {
    println!("{}", val);
}

unsafe {
    let mut data = UnsafeCell::new(10);
    let mref1 = &mut data;
    // Меняем местами, теперь заимствования в *точном* соответствии со стеком
    let sref2 = &*mref1;
    // Создаём ptr из разделяемой ссылки для максимальной безопасности!
    let ptr3 = sref2.get();             

    *ptr3 += 3;
    opaque_read(&*sref2.get());
    *sref2.get() += 2;
    *mref1.get() += 1;

    println!("{}", *data.get());
}

cargo run
13
16

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
13
16

Одна из причин, почему первая реализация, могла быть совершенно корректной, заключается в том, что &UnsafeCell<T> по сути не отличается от *mut T. Его можно бесконечно копировать его и менять!

Так что мы, как обычно, создали два сырых указателя и использовали их по очереди. Немного подозрительно, что оба указателя получены из изменяемой ссылки, так что, кажется, при создании второго надо удалять из стека заимствований первый. Но на самом деле мы не обращаемся к содержимому изменяемой ссылки, а просто копируем адрес, так что всё нормально.

Строка let sref2 = &*mref1 — довольно хитрая штука. Синтаксически кажется, что мы разыменовали указатель, но разыменование само по себе не являтеся чем-то реальным. Сравните с &my_tuple.0: вы ничего не делаете ни с my_tuple, ни с .0, вы просто используете выражение, чтобы получить адрес в памяти, а, написав перед ним & как бы говорите: «не загружай содержимое, просто запомни адрес».

&* — это то же самое: * говорит «обсудим местоположение, на которое указывает этот указатель», а & говорит «теперь запиши этот адрес». Естественно, адрес остался тем же. Но тип указателя изменился, потому что… ну, типы!

С другой стороны, если вы пишете &**, то, по факту, загружаете значение сразу после первой операции *! Эта * такая странная!

ГОЛОС ЗА КАДРОМ: Никого не волнует, что вы знаете, что такое «л-значение», Джонатан. В Rust мы называем л-значения местами (places), что гораздо круче, не находите?

Тестирование Box

Помните, почему мы начали это затянувшееся отступление? Нет? Странно.

Это было потому, что мы смешали Box и сырой указатель. Box — это что-то вроде &mut, поскольку он заявляет об единоличном владении памятью, на которую указывает. Проверим это утверждение:

unsafe {
    let mut data = Box::new(10);
    let ptr1 = (&mut *data) as *mut i32;

    *data += 10;
    *ptr1 += 1;

    // Должно быть 21
    println!("{}", data);
}

cargo run
21

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run

error: Undefined Behavior: no item granting read access 
       to tag <1707> at alloc763 found in borrow stack.

 --> src\main.rs:7:5
  |
7 |     *ptr1 += 1;
  |     ^^^^^^^^^^ no item granting read access to tag <1707> 
  |                at alloc763 found in borrow stack.
  |

Да, miri это не нравится. Убедимся, что выполнение действий в правильном порядке не приводит к ошибкам:

unsafe {
    let mut data = Box::new(10);
    let ptr1 = (&mut *data) as *mut i32;

    *ptr1 += 1;
    *data += 10;

    // Должно быть 21
    println!("{}", data);
}

cargo run
21

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri run
21

Так!

Что ж, на этом всё, мы, наконец, закончили обсуждать стековые заимствования!

…хотя, как нам решить проблему с Box? Конечно, мы можем писать игрушечные программы, но всё-таки — нам надо хранить Box и удерживать значения сырых указателей в течение довольно долгого времени. Наверняка всё перепутается и станет недействительным?

Хороший вопрос! Чтобы на него ответить, вернёмся, наконец, к нашей истинной задаче — написанию богом проклятых связных списков.

Подождите, мы снова станем писать связные списки? Не будем торопиться, друзья. Будем благоразумны. Я уверена, что у меня есть несколько интересных вопросов для обсуждения.

Представление и основы 2: добавляем сырости

Краткое содержание трёх предыдущих частей: перемешивание ссылок &, & mut и Box с небезопасными указателями *mut и *const — верный способ получить Неопределённое Поведение, поскольку безопасные указатели вводят дополнительные ограничения, которым сырые указатели не обязаны подчиняться.

Господи, мне опять придётся писать связные списки. Прекрасно. ПРЕКРАСНО. Всё прекрасно. У нас всё прекрасно.

Мы быстро разберём большую часть этого раздела, поскольку мы уже обсудили дизайн в первой части. Всё, что бы делали, было в основном правильно, за исключением того, что мы смешивали безопасные и небезопасные указатели.

Представление

Итак, в новом представлении мы собираемся использовать только сырые указатели. Всё будет нормально и мы никогда больше не ошибёмся.

Вот наше старое проблемное представление:

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>,
}

А вот наше новое представление.

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, но в данном случае это как брать катану на кухню. Свою работу мы сделаем, но это будет и неудобно, и слишком наворочено.

Мы хотим использовать боксы, но, в то же время, нет. Один совершенно безумный вариант, но возможно жизнеспособный — сделать что-то такое:

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 для автоматической очистки:

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 означает мужской половой орган.)

Что и требовалось доказать.

Всё остальное

Теперь, написав push и pop, мы можем взять остальные функции из старой реализации стека, каким бы странным это ни казалось. Только в операциях, изменяющих длину списка, надо менять и указатель на хвост.

Конечно, поскольку у нас везде небезопасные указатели, придётся подкорректировать код! И, раз уж мы будем его корректировать, почему бы не воспользоваться случаем и не убедиться, что мы ничего не упустили!

Что ж, начнём копи-пастить код из старой реализации:

// ...

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

IntoIter выглядит нормально, но Iter и IterMut нарушают наше правило никогда не использовать безопасные указатели в наших типах. Перестрахуемся и перепишем их на сырые указатели:

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: *mut Node<T>,
}

pub struct IterMut<'a, T> {
    next: *mut Node<T>,
}

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        Iter { next: self.head }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.head }
    }
}

Выглядит хорошо!

error[E0392]: parameter `'a` is never used
  --> src\fifth.rs:17:17
   |
17 | pub struct Iter<'a, T> {
   |                 ^^ unused parameter
   |
   = help: consider removing `'a`, referring to it in a field, 
     or using a marker such as `PhantomData`

error[E0392]: parameter `'a` is never used
  --> src\fifth.rs:21:20
   |
21 | pub struct IterMut<'a, T> {
   |                    ^^ unused parameter
   |
   = help: consider removing `'a`, referring to it in a field, 
     or using a marker such as `PhantomData`

Выглядит нехорошо! О каком PhantomData они пишут?

Тип нулевого размера. Используется для маркировки объектов, которые «ведут себя так», словно владеют T.

Добавление поля PhantomData<T> к вашему типу говорит компилятору, что он действует так, будто хранит значение типа T, хотя на самом деле это не так. Эта информация используется при вычислении определённых свойств безопасности.

Для более глубокого объяснения, как использовать PhantomData<T>, читайте, пожалуйста, Nomicon.

Эй, потише, мы говорим о книге, которую написала я. Не про ту другую книгу, которую, написал какой-то неимоверный ботан! Держу пари, если он и напишет какую-нибудь структуру данных, это будет стек на основе массива, а не связный список.

Неиспользуемые параметры времени жизни

Чаще всего PhantomData применяют для описания структур с неиспользуемым параметром времени жизни, обычно как часть небезопасного кода.

А, так мы объявили в нашем типе время жизни, но на самом деле его не используем. Мы могли бы пойти по пути PhantomData, но я оставлю его для двусвязного списка из следующей главы, где такое решение на самом деле имеет смысл.

Сейчас мы в интересной ситуации, когда на самом деле нам не нужен тип PhantomData. Мне кажется. Я просто надеюсь, что это правда, а если miri будет ругаться, я уступлю и попробую прикрутить PhantomData.

Что мы на самом деле собираемся сделать: вернём ссылки в итераторы, поскольку они удобны для перебора элементов. Кажется, что с этим не должно быть проблем, поскольку мы соблюдаем вложенность: создаём итератор, использует безопасные ссылки, удаляем итератор.

Только после завершения итерации можно вызывать у списка push и pop, которым нужен указатель на хвост и боксы. А пока на время итерации мы разыменуем груду сырых указателей, поэтому здесь возможно перемешивание, но мы будем думать об этих ссылках, как о повторно заимствованных небезопасных указателях.

Я даже не уверена на 100%, но я хочу попробовать и проверить!

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        unsafe {
            Iter { next: self.head.as_ref() }
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        unsafe {
            IterMut { next: self.head.as_mut() }
        }
    }
}

Если мы будем хранить ссылки, нам надо преобразовать сырые указатели в Options для ссылок. Мы могли бы проверять указатели на null, но это один из тех редких случаев, когда я допускаю использование неприятных методов ptr::as_ref и ptr::as_mut.

Обычно я рекомендую избегать этих методов, как чумы, потому что они делают неожиданные и неприятные вещи и по сути повторно вводят ссылки, тогда как моё «простое правило» — не делать так!

Эти методы сопровождаются множеством предупреждений, но самое интересное вот это:

Необходимо соблюдать правила Rust о псевдонимах, поскольку возвращаемое время жизни 'a выбирается произвольно и не отражает реальное время жизни данных. В частности, в течение этого времени жизни, доступ к этой памяти (чтение или запись) не должен осуществляться ни через один другой указатель

Смотрите, это то, о чём мы говорили на протяжении 25 страниц! Я уже говорила, что использование ссылок здесь определённо допустимо, так что проблема псевдонимов решена! Но есть и другая проблема — сигнатура:

pub unsafe fn as_mut<'a>(self) -> Option<&'a mut T>

Вы видите, что время жизни вообще не привязано к входному значению, потому что self передаётся по значению? Да, это то, что мы называем «неограниченным временем жизни» и это очень неприятная штука. Это время претворяется настолько длинным, насколько нам нужно, даже «статическим»!

Способ справиться с ним — поместить его туда, где оно будет ограничено, что обычно означает «вернуть его из функции как можно быстрее, так что теперь его будет ограничивать сигнатура функции».

Боже, я нервничаю, но мы будем двигаться дальше! Позаимствуем несколько реализаций итератора из стека:

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            self.next.map(|node| {
                self.next = node.next.as_ref();
                &node.elem
            })
        }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            self.next.take().map(|node| {
                self.next = node.next.as_mut();
                &mut node.elem
            })
        }
    }
}

Moment of truth time…

Время момента истины…

cargo test

running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::basics ... 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::iter ... ok
test third::test::basics ... ok

test result: ok. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;

MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test

running 15 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::basics ... 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. 15 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

ДА!!! Вот тебе, ГОЛОС ЗА КАДРОМ! Иногда и я не ошибаюсь!

ГОЛОС ЗА КАДРОМ: но разве вся суть не в том, что ошибки нужны, чтобы научить читателя?

ДА, НО ИНОГДА СУТЬ В ТОМ, ЧТО Я ПРАВА И ВСЕ ДОЛЖНЫ ПРИСЛУШИВАТЬСЯ КО МНЕ, КОГДА Я ГОВОРЮ О НЕБЕЗОПАСНОМ КОДЕ, ПОТОМУ ЧТО Я ПРОВЕЛА МНОГО ВРЕМЕНИ В РАЗМЫШЛЕНИЯХ О НАДЁЖНОСТИ РЕАЛИЗАЦИИ ИТЕРАТОРОВ! ЛАДЫ?! ЛАДЫ.

Наконец, вот peek и peek_mut.

pub fn peek(&self) -> Option<&T> {
    unsafe {
        self.head.as_ref()
    }
}

pub fn peek_mut(&mut self) -> Option<&mut T> {
    unsafe {
        self.head.as_mut()
    }
}

Я даже не буду их тестировать, потому что я больше не ошибаюсь.

ГОЛОС ЗА КАДРОМ: cargo build

error[E0308]: mismatched types
  --> src\fifth.rs:66:13
   |
25 | impl<T> List<T> {
   |      - this type parameter
...
64 |     pub fn peek(&self) -> Option<&T> {
   |                           ---------- expected `Option<&T>` 
   |                                      because of return type
65 |         unsafe {
66 |             self.head.as_ref()
   |             ^^^^^^^^^^^^^^^^^^ expected type parameter `T`, 
   |                                found struct `fifth::Node`
   |
   = note: expected enum `Option<&T>`
              found enum `Option<&fifth::Node<T>>`

ПРЕКРАСНО.

pub fn peek(&self) -> Option<&T> {
    unsafe {
        self.head.as_ref().map(|node| &node.elem)
    }
}

pub fn peek_mut(&mut self) -> Option<&mut T> {
    unsafe {
        self.head.as_mut().map(|node| &mut node.elem)
    }
}

Полагаю, я всё-таки буду ошибаться время от времени, так что мы добавим новый тест, который я назову «приманка для miri»: что-то, что вызывает наши методы в произвольном порядке и помогает miri искать наши ошибки.

#[test]
fn miri_food() {
    let mut list = List::new();

    list.push(1);
    list.push(2);
    list.push(3);

    assert!(list.pop() == Some(1));
    list.push(4);
    assert!(list.pop() == Some(2));
    list.push(5);

    assert!(list.peek() == Some(&3));
    list.push(6);
    list.peek_mut().map(|x| *x *= 10);
    assert!(list.peek() == Some(&30));
    assert!(list.pop() == Some(30));

    for elem in list.iter_mut() {
        *elem *= 100;
    }

    let mut iter = list.iter();
    assert_eq!(iter.next(), Some(&400));
    assert_eq!(iter.next(), Some(&500));
    assert_eq!(iter.next(), Some(&600));
    assert_eq!(iter.next(), None);
    assert_eq!(iter.next(), None);

    assert!(list.pop() == Some(400));
    list.peek_mut().map(|x| *x *= 10);
    assert!(list.peek() == Some(&5000));
    list.push(7);

    // Ну а здесь пусть запуститься деструктор
}

cargo test

running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out



MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo +nightly-2022-01-21 miri test

running 16 tests
test fifth::test::basics ... ok
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test fourth::test::peek ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::iter ... ok
test second::test::iter ... ok
test third::test::basics ... ok

test result: ok. 16 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Идеально.

Финальный код

Что ж, с небольшой долей небезопасности нам удалось добиться линейного улучшения времени по сравнению с наивной безопасной очередью, и мы смогли повторно использовать почти всю логику из безопасного стека!

За исключением той части, где miri полностью нас подвёл и нам пришлось писать небольшую магистерскую работу о модели памяти в Rust. Как это обычно и бывает.

Но светлая сторона в том, что нам не пришлось писать всех этих ужасных Rc или RefCell.

use std::ptr;

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>,
}

pub struct IntoIter<T>(List<T>);

pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

pub struct IterMut<'a, T> {
    next: Option<&'a mut Node<T>>,
}

impl<T> List<T> {
    pub fn new() -> Self {
        List { head: ptr::null_mut(), tail: ptr::null_mut() }
    }
    pub fn push(&mut self, elem: T) {
        unsafe {
            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;
        }
    }
    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)
            }
        }
    }

    pub fn peek(&self) -> Option<&T> {
        unsafe {
            self.head.as_ref().map(|node| &node.elem)
        }
    }

    pub fn peek_mut(&mut self) -> Option<&mut T> {
        unsafe {
            self.head.as_mut().map(|node| &mut node.elem)
        }
    }

    pub fn into_iter(self) -> IntoIter<T> {
        IntoIter(self)
    }

    pub fn iter(&self) -> Iter<'_, T> {
        unsafe {
            Iter { next: self.head.as_ref() }
        }
    }

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        unsafe {
            IterMut { next: self.head.as_mut() }
        }
    }
}

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while let Some(_) = self.pop() { }
    }
}

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.pop()
    }
}

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            self.next.map(|node| {
                self.next = node.next.as_ref();
                &node.elem
            })
        }
    }
}

impl<'a, T> Iterator for IterMut<'a, T> {
    type Item = &'a mut T;

    fn next(&mut self) -> Option<Self::Item> {
        unsafe {
            self.next.take().map(|node| {
                self.next = node.next.as_mut();
                &mut node.elem
            })
        }
    }
}

#[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);
    }

    #[test]
    fn into_iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.into_iter();
        assert_eq!(iter.next(), Some(1));
        assert_eq!(iter.next(), Some(2));
        assert_eq!(iter.next(), Some(3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&1));
        assert_eq!(iter.next(), Some(&2));
        assert_eq!(iter.next(), Some(&3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn iter_mut() {
        let mut list = List::new();
        list.push(1); list.push(2); list.push(3);

        let mut iter = list.iter_mut();
        assert_eq!(iter.next(), Some(&mut 1));
        assert_eq!(iter.next(), Some(&mut 2));
        assert_eq!(iter.next(), Some(&mut 3));
        assert_eq!(iter.next(), None);
    }

    #[test]
    fn miri_food() {
        let mut list = List::new();

        list.push(1);
        list.push(2);
        list.push(3);

        assert!(list.pop() == Some(1));
        list.push(4);
        assert!(list.pop() == Some(2));
        list.push(5);

        assert!(list.peek() == Some(&3));
        list.push(6);
        list.peek_mut().map(|x| *x *= 10);
        assert!(list.peek() == Some(&30));
        assert!(list.pop() == Some(30));

        for elem in list.iter_mut() {
            *elem *= 100;
        }

        let mut iter = list.iter();
        assert_eq!(iter.next(), Some(&400));
        assert_eq!(iter.next(), Some(&500));
        assert_eq!(iter.next(), Some(&600));
        assert_eq!(iter.next(), None);
        assert_eq!(iter.next(), None);

        assert!(list.pop() == Some(400));
        list.peek_mut().map(|x| *x *= 10);
        assert!(list.peek() == Some(&5000));
        list.push(7);

        // Ну а здесь пусть запуститься деструктор
    }
}

Эта глава на сайте перевода