Плохой односвязный список

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

Наш первый список мы поместим в файл src/first.rs. Надо сказать компилятору Rust, что first.rs входит в состав нашей библиотеки. Для этого в начале файла src/lib.rus (который создала для нас утилита Cargo) достаточно написать :

// в lib.rs
pub mod first;

Базовое представление данных

Ладно, что такое связный список? Ну, в целом, это набор кусочков данных в куче, которые последовательно указывают друг на друга. (Да, я знаю, что разработчикам ядра куча недоступна, мы сейчас не об этом!) Связные списки — это то, что процедурные программисты не станут трогать 10-метровой палкой, а функциональные программисты используют вообще для всего. Кажется справедливым, что определение связного списка в этом случае что мы должны спросить у функциональных программистов. И они дадут вам что-то такое:

List a = Empty | Elem a (List a)

Что приблизительно читается как «Список является либо Пустым, либо Элементом за которым следует Список». Это рекурсивное определение, выраженное через тип-сумму или, если подробнее, через тип, который «может принимать одно из нескольких значений, у каждого из которых может быть свой тип». В языке Rust типы-суммы называются перечислениями (enum)! Если вы пришли из C-подобного языка, то речь идёт о знакомых и любимых нами enum, но на максималках. Ладно, давайте перепишем это функциональное определение на Rust!

Для простоты первое время мы не будем использовать обобщения (generics). Значениями узлов у нас будут обычные 32-битные числа.:

// в first.rs

// pub говорит, что мы хотим, чтобы авторы других модулей могли использовать List
pub enum List {
    Empty,
    Elem(i32, List),
}

Уф, как сложно. Попробуем скомпилировать:

> cargo build

error[E0072]: recursive type `first::List` has infinite size
 --> src/first.rs:4:1
  |
4 | pub enum List {
  | ^^^^^^^^^^^^^ recursive type has infinite size
5 |     Empty,
6 |     Elem(i32, List),
  |               ---- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable

Текст ошибки: рекурсивный тип first::List имеет бесконечный размер.

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

Подумав над сообщением об ошибке (после того, как переживём всю эту историю с предательством), мы обнаружим, что rustc на самом деле подсказывает нам, как решить нашу проблему:

insert indirection (e.g., a Box, Rc, or &) at some point to make first::List representable

Перевод: чтобы сделать first::List представимым, добавьте в нужном месте косвенный доступ, т. е. Box, Rc или &

Так, box. Что это такое? Давайте погуглим rust box…

std::boxed::Box - Rust

Посмотрим, что пишут…

pub struct Box<T>(_);
Тип-указатель для размещения в куче. Дополнительную информацию см. в документации к модулю boxed.

щёлкает по ссылке

Box<T>, обычно называемый «боксом» — простейшая форма размещения объекта в куче в языке Rust. Боксы являются владельцами этого объекта и уничтожают его, когда выходят из области видимости.
Примеры
Создание бокса
let x = Box::new(5);
Создание рекурсивной структуры данных:
#[derive(Debug)] enum List<T> { Cons(T, Box<List<T>>), Nil, } fn main() { let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil)))); println!("{:?}", list); }
Этот код напечатает Cons(1, Box(Cons(2, Box(Nil)))).
Рекурсивные структуры должны быть помещены в бокс, потому что определение:
Cons(T, List<T>),
не работает. В данном случае размер List зависит от количества элементов, так что мы не знаем, сколько памяти выделить для Cons. Box, который по сути является указателем, имеет фиксированный размер, поэтому компилятор может вычислить размер Cons.

Ого! Хм. Кажется, это самая релевантная и полезная документация, которую я когда-либо видела. Первые абзацы — буквально о том, что мы пытаемся написать, почему оно не работает и как всё исправить.

Блин, доки рулят.

Ладно, давайте напишем так:

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

> cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

Ага, проект собрался!

…но у нас получилось достаточно дурацкое определение списка. Сразу по нескольким причинам.

Представим список из двух элементов.

[] = Стек
() = Куча

[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)

Есть два ключевых момента:

Мы выделили память под узел, который как бы говорит «На самом деле я не Узел»
Один из наших узлов вообще не размещён в куче

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

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)

Здесь мы размещаем в куче все наши узлы без исключения. Ключевое отличие в отсутствии мусора (junk) из нашего первого сценария. Что это за мусор? Что в этом разобраться, рассмотрим, как наш enum размещается в памяти.

Пусть у нас будет такой enum:

enum Foo {
    D1(T1),
    D2(T2),
    ...
    Dn(Tn),
}

В Foo хранится целое число, которое обозначает, какой из вариантов перечисления (D1, D2, … Dn) представлен. Это — метка (tag) перечисления. Ему также требуется достаточно памяти, чтобы сохранить наибольший из типов T1, T2, … Tn (плюс немного дополнительного пространства, чтобы удовлетворить требования выравнивания).

Это значит, что хотя Empty хранит один бит информации, он в любом случае резервирует место для указателя и элемента, поскольку в любой момент может превратиться в Elem. Поэтому в первом сценарии в куче хранится дополнительный элемент, где полезным является один бит, а всё остальное — мусор. Во втором сценарии последний узел содержит нулевой указатель, который означает конец списка, то есть, не является мусором.

Один из узлов вообще не размещается в куче и это, как ни странно, не очень хорошо. Причина — в неунифицированном размещении узлов (часть узлов хранится одним способом, а часть — другим). Для вставки и удаления узлов это не важно, но разделение и слияние списков становятся сложнее.

Сравним разделение списка в обоих сценариях.

сценарий 1:

[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)

разбиваем список на элементе C:

[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)

сценарий 2:

[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)

разбиваем список на элементе C:

[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)

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

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

Хорошо, я почти уверена, что первый сценарий плох. Как нам переписать список теперь? Для начала, мы могли бы сделать что-то вроде этого:

pub enum List {
    Empty,
    ElemThenEmpty(i32),
    ElemThenNotEmpty(i32, Box<List>),
}

Надеюсь, вы заметили, что эта идея ещё хуже. Во-первых, теперь нам придётся писать дополнительные проверки, потому что появился совершенно недопустимый вариант ElemThenNotEmpty(0, Box(Empty)). А во-вторых, мы всё ещё не избавились от неунифицированного размещения элементов.

Впрочем, у этого варианта есть одно интересное свойство: он позволяет полностью избавиться от размещения узла Empty, сокращая общее число размещений в куче на 1. К сожалению, при этом расходуется ещё больше места! Связано это с тем, что в прошлом сценарии применялась оптимизация указателей на null.

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

enum Foo {
    A,
    B(ContainsANonNullPtr), // ContainsANonNullPtr — ненулевой указатель
}

срабатывает оптимизация указателя на null, которая избавляется от места, выделяемого под метку. Для варианта A все байты перечисления равны 0. Если байты не равны 0, у нас неизбежно вариант B. Всё работает, поскольку B не может состоять из одних 0, так как содержит ненулевой указатель. Ловко!

Не приходят ли вам в голову другие перечисления и типы, где могла бы работать такого рода оптимизация? На самом деле их очень много! По этой причине Rust не регламентирует способ хранения перечислений. Существует несколько сложных оптимизаций, которые для нас делает Rust, но указатель на null безусловно один из самых важных! Это значит, что &, &mut, Box, Rc, Arc, Vec и некоторые другие важные типы Rust не требуют дополнительной памяти, если завернуть их в тип Option! (Большинство из них мы обсудим позже.)

Итак, как избавиться от мусора, унифицировано хранить узлы и добиться заветной оптимизации указателя на null? Попробуем разграничить идеи наличия элемента и размещения последующего списка. Чтобы это сделать, будем думать в стиле C. Конечно, структуры!

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

Как и раньше, List может быть либо пустым, либо содержать элемент, за которым следует другой список. Представив вариант «содержать элемент, за которым следует другой список» в виде структуры, мы приводим Box в оптимальное положение:

struct Node {
    elem: i32,
    next: List,
}

pub enum List {
    Empty,
    More(Box<Node>),
}

Проверим, всех ли целей мы добились?

Хвост списка никогда не выделяет дополнительное пространство: есть!
enum хранится в заветной форме оптимизированного указателя на null: есть!
Все элементы хранятся унифицировано: есть!

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

> cargo build

warning: private type `first::Node` in public interface (error E0446)
 --> src/first.rs:8:10
  |
8 |     More(Box<Node>),
  |          ^^^^^^^^^
  |
  = note: #[warn(private_in_public)] on by default
  = warning: this was previously accepted by the compiler but
    is being phased out; it will become a hard error in a future release!

Текст ошибки: приватный тип first::Node в публичном интерфейсе.

:(

Rust снова сердится — и всё по нашей вине. Мы сделали List публичным (чтобы люди могли его использовать), а Node — нет. Проблема в том, что внутренности enum публичны и там, по идее, не должно быть приватных типов. Можно было бы сделать Node публичным, однако мы в Rust предпочитаем скрывать детали реализации. Сделаем List структурой:

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

Поскольку List — это структура с единственным полем, её размер будет совпадать с размером поля. Сила абстракций с нулевой стоимостью!

> cargo build

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

warning: variant is never constructed: `Empty`
 --> src/first.rs:6:5
  |
6 |     Empty,
  |     ^^^^^

warning: variant is never constructed: `More`
 --> src/first.rs:7:5
  |
7 |     More(Box<Node>),
  |     ^^^^^^^^^^^^^^^

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

warning: field is never used: `next`
  --> src/first.rs:12:5
   |
12 |     next: Link,
   |     ^^^^^^^^^^

Rust выводит множество предупреждений, потому что, насколько он может судить, мы написали совершенно бесполезный код. Мы не используем head и никто из пользователей нашей библиотекой не может этого сделать, потому что это приватное поле. Транзитивно это значит, что List и Node тоже никто не использует. Давайте с этим разберёмся! Напишем немного кода для нашего списка!

Метод new

Чтобы связать написанный код с типом, используем блоки impl:

impl List {
    // воплотить код в жизнь
}

Разберёмся, как писать код правильно. В Rust объявление функции выглядит так:

fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
    // тело
}

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

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }
}

Несколько замечаний по поводу кода:

Self — это псевдоним для «того тип, который я написал в заголовке impl». Отличный способ не повторяться!
Мы создаём экземпляр структуры практически также, как объявляем её, за исключением того, чтобы вместо указания типов полей, мы инициализируем их значениями.
Мы ссылаемся на варианты перечисления, используя ::, то есть оператор указания пространства имён.
Последнее выражение функции считается её результатом. Такой подход позволяет делает простые функции лаконичными. Но всё ещё можно использовать return для досрочного возврата из функции, как и в других C-подобных языках.

Основы владения

Теперь, когда мы можем сконструировать список, было бы неплохо что-нибудь с ним сделать. Делать будем при помощи «обычных» (не статических) методов. Метод — это особый вид функции в Rust. У него есть аргумент self без типа:

fn foo(self, arg2: Type2) -> ReturnType {
    // тело
}

Есть три основные формы, которые он может принимать: self, &must self и &self. Эти три формы представляют три основные формы владения в Rust:

self — Значение
&mut self — изменяемая ссылка
&self — разделяемая ссылка

Значение — это, по сути, истинное владение. Вы можете делать со значением всё, что хотите: отдать, уничтожить, изменить или передавать по ссылке. Если вы передаёте что-то по значению, оно отдаётся в новое место. Новое место теперь владеет значением, а старое место больше не имеет к нему доступа. По этой причине большинство методов не используют self — было бы довольно глупо работать со списком, теряя к нему доступ!

Изменяемая ссылка означает временный эксклюзивный доступ к значению, которым вы не владеете. Вы можете делать со значением абсолютно всё, что хотите, если в конце вы оставляете его в рабочем состоянии (иное было бы невежливым по отношению к владельцу!). Это значит, что на самом деле значение можно полностью перезаписать. Очень полезный частный случай — обмен двух значений, который нам пригодится, и не единожды. Единственное, что нельзя сделать с &mut — уничтожить, не заменив другим значением. &mut self отлично подходит для методов, которым надо изменить self.

Разделяемое владение означает временный разделяемый доступ к значению, которым вы не владеете. Имея разделяемый доступ, вы в общем случае ничего не можете изменить. Как в музее: смотреть можно, руками трогать нельзя! & отлично подходит для методов, которым self нужен только для чтения.

Позже мы узнаем, что правило об изменении в определённых случаях можно обойти. По этой причине разделяемые ссылки не называют неизменяемыми. Скорее, изменяемые ссылки можно было бы называть уникальными, но, как выяснило Rust-сообщество, связь между владением и изменяемостью интуитивно понятна в 99% случаев.

Метод push

Пришло время написать функцию вставки числа в начало списка. Вставка (push) изменяет список, поэтому нам нужен параметр &mut self. Кроме того, нам потребуется значение i32, которое мы будем вставлять.

impl List {
    pub fn push(&mut self, elem: i32) {
        // написать
    }
}

Прежде всего нам надо создать узел и сохранить в нём наш элемент:

    pub fn push(&mut self, elem: i32) {
        let new_node = Node {
            elem: elem,
            next: ?????
        };
    }

Что должно быть по ссылке next? Ну, весь наш старый список! Можем ли мы… просто так и написать?

impl List {
    pub fn push(&mut self, elem: i32) {
        let new_node = Node {
            elem: elem,
            next: self.head,
        };
    }
}

> cargo build
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:19:19
   |
19 |             next: self.head,
   |                   ^^^^^^^^^ cannot move out of borrowed content

Неееееет. Наверное, Rust написал всё правильно, но непонятно, что это значит и что с этим делать:

cannot move out of borrowed content

Нельзя переместить заимствованное содержимое.

Мы пытаемся переместить поле self.head в next, но Rust не разрешает нам это сделать. Проблема в том, что когда мы завершим заимствование и «вернём назад» законному владельцу, self останется частично инициализированным. Как мы уже говорили, это единственное, что нельзя сделать с помощью &mut. Rust очень вежлив, а это — невежливо (кстати, и опасно тоже, но вряд ли компилятор беспокоит какая-то опасность).

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

pub fn push(&mut self, elem: i32) {
    let new_node = Box::new(Node {
        elem: elem,
        next: self.head,
    });

    self.head = Link::More(new_node);
}

> cargo build
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:19:19
   |
19 |             next: self.head,
   |                   ^^^^^^^^^ cannot move out of borrowed content

Ничего не вышло. В принципе, это одна из тех штук, которую Rust мог бы принять, но не принимает (по многим причинам, одна из которых — это безопасность исключений). Нам нужен способ забрать значение head так, чтобы Rust не заметил пропажи. Обратимся за советом к печально известному взломщику ржавых замков Индиане Джонсу:

Хм, Инди советует прибегнуть к маневру mem::replace. Эта невероятно полезная функция позволяет нам забрать значение заимствованного объекта, заменив его другим значением. Добавим std::mem в начало файла, чтобы модуль mem оказался в локальной области видимости:

use std::mem;

и используем надлежащим образом:

pub fn push(&mut self, elem: i32) {
    let new_node = Box::new(Node {
        elem: elem,
        next: mem::replace(&mut self.head, Link::Empty),
    });

    self.head = Link::More(new_node);
}

Здесь мы временно заменяем (replace) self.head значением Link::Empty перед тем, как заменить его новой головой списка. Не стану врать: так делать не надо (по меньшей мере, это решение не простое, и не очевидное), но в учебных целях мы должны проверить все грабли. Позже мы познакомимся с простым и очевидным способом.

Но, подождите, метод push уже готов! Кажется. Честно говоря, это стоит протестировать. Как это сделать проще всего? Написать метод pop и убедиться, что он возвращает правильные результаты.

Метод pop

Как и push, метод pop меняет список. Но, в отличие от push, метод pop возвращает какое-то значение. При этом он должен учитывать каверзный граничный случай: что, если список пуст? Чтобы представить этот случай, воспользуемся проверенным типом Option:

pub fn pop(&mut self) -> Option<i32> {
    // дописать
}

Option<T> — это перечисление, которое представляет опциональное значение, которое, возможно, существует. Вариант Some(T) соответствует существующему значению, а None — отсутствию значения. Как и в случае с Link, можно было бы придумать собственный тип, но мы хотим, чтобы пользователи понимали, что именно представляет из себя возвращаемое значение, а Option настолько вездесущ, что все про него все знают. Фактически, он настолько фундаментален, что неявно импортируется в область видимости каждого модуля вместе с вариантами Some и None (поэтому мы и не пишем Option::None).

Угловые скобки в Option<T> означают, что Option, на самом деле — обобщённый тип над T. То есть, опциональным можно сделать значение любого типа!

Хорошо, у нас есть ссылка Link, как нам узнать, содержит ли она Empty или More? Конечно же с помощью сопоставления с образцом и оператора match!

pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // дописать
        }
        Link::More(node) => {
            // дописать
        }
    };
}

> cargo build

error[E0308]: mismatched types
  --> src/first.rs:27:30
   |
27 |     pub fn pop(&mut self) -> Option<i32> {
   |            ---               ^^^^^^^^^^^ expected enum `std::option::Option`, found ()
   |            |
   |            this function's body doesn't return
   |
   = note: expected type `std::option::Option<i32>`
              found type `()`

Ой, pop должна вернуть значение, но этого мы пока не написали. Мы могли бы вернуть None, но, возможно в данном случае лучше вернуть unimplemented!(), чтобы показать, что мы ещё не завершили реализацию функции. unimplemented!() — это макрос (! указывает на макрос), который вызывает панику, когда к нему обращаются. Происходит так называемый контролируемый сбой.

pub fn pop(&mut self) -> Option<i32> {
    match self.head {
        Link::Empty => {
            // дописать
        }
        Link::More(node) => {
            // дописать
        }
    };
    unimplemented!()
}

Безусловная паника — это пример расходящейся функции. Расходящиеся функции не возвращают управления вызывающей функции, поэтому их можно использовать в любом месте, где ожидается значение любого типа. В нашем случае unimplemented!() используется вместо значения типа Option<T>.

Обратите внимание, что в методе pop мы не используем оператор return. Значением функции становится её последнее выражение (обычно, последняя строка). Благодаря этому, действительно простые функции можно сделать намного короче. Однако, вы всегда можете завершить функцию досрочно с помощью оператора return, как и в любом другом C-подобном языке.

> cargo build

error[E0507]: cannot move out of borrowed content
  --> src/first.rs:28:15
   |
28 |         match self.head {
   |               ^^^^^^^^^
   |               |
   |               cannot move out of borrowed content
   |               help: consider borrowing here: `&self.head`
...
32 |             Link::More(node) => {
   |                        ---- data moved here
   |
note: move occurs because `node` has type `std::boxed::Box<first::Node>`, which does not implement the `Copy` trait
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^

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

help: consider borrowing here: `&self.head`

Rust утверждает, что мы должны добавить ссылку в оператор match, чтобы исправить ошибку. 🤷‍♀️ Попробуем:

pub fn pop(&mut self) -> Option<i32> {
    match &self.head {
        Link::Empty => {
            // дописать
        }
        Link::More(node) => {
            // дописать
        }
    };
    unimplemented!()
}

> cargo build

warning: unused variable: `node`
  --> src/first.rs:32:24
   |
32 |             Link::More(node) => {
   |                        ^^^^ help: consider prefixing with an underscore: `_node`
   |
   = note: #[warn(unused_variables)] on by default

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

warning: field is never used: `next`
  --> src/first.rs:14:5
   |
14 |     next: Link,
   |     ^^^^^^^^^^

Ура, снова компилируется! Теперь давайте обсудим логику работы нашего метода. Мы хотим создать Option, так что пусть у нас будет переменная для опционального значения. В случае пустого списка мы присвоим ей None. В случае непустого списка, мы присвоим ей Some(i32) и заменим голову списка. Что ж, попробуем?

pub fn pop(&mut self) -> Option<i32> {
    let result;
    match &self.head {
        Link::Empty => {
            result = None;
        }
        Link::More(node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

> cargo build
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
  --> src/first.rs:35:29
   |
35 |                 self.head = node.next;
   |                             ^^^^^^^^^ cannot move out of borrowed content

голова

стол

Мы пытаемся забрать владение node в то время как узел доступен нам только по разделяемой ссылке.

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

Проверить, не пустой ли список.
Если пустой, просто вернуть None.
Если не пустой:
- удалить голову списка
- удалить elem
- заменить голову списка следующим узлом
- вернуть Some(elem)

Ключевая мысль заключается в том, что мы хотим что-то удалить, а это значит, что доступ к голове списка нам нужен по значению. Мы определённо не можем ничего менять через разделяемую ссылку, которую получаем с помощью &self.head. Кроме того, имея на руках только изменяемую ссылку на self, мы можем переместить что-либо единственным способом — через замену. Выглядит так, словно нам опять предстоит танец вокруг Empty!

Попробуем:

pub fn pop(&mut self) -> Option<i32> {
    let result;
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => {
            result = None;
        }
        Link::More(node) => {
            result = Some(node.elem);
            self.head = node.next;
        }
    };
    result
}

cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

Боже мой!

Всё скомпилировалось без единого предупреждения!!!

Я собираюсь выступить в роли линтера для нашего кода. Мы сделали result возвращаемым значением, но на самом деле эта переменная нам вообще не нужна! Также, как и функция получает значение своего последнего выражения, каждый блок получает значение своего последнего выражения. Обычно мы ставим в конце операторов точку с запятой, а это значит, что блок возвращает пустой кортеж, (). На самом деле, пустой кортеж — то самое значение, которое возвращают функции без возвращаемого значения, такие, как push.

Так что мы можем переписать pop так:

pub fn pop(&mut self) -> Option<i32> {
    match mem::replace(&mut self.head, Link::Empty) {
        Link::Empty => None,
        Link::More(node) => {
            self.head = node.next;
            Some(node.elem)
        }
    }
}

Так чуть лаконичнее и идиоматичнее. Обратите внимание, что ветка Link::Empty полностью избавилась от фигурных скобок, потому что состоит теперь только из одного выражения. Удобная короткая запись для простых случаев.

cargo build

   Finished dev [unoptimized + debuginfo] target(s) in 0.22s

Прекрасно, всё ещё работает!

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

Прекрасно, теперь, когда у нас есть push и pop, мы можем протестировать наш стек! Для Rust и cargo тестирование — это гражданин первого класса, так что всё должно быть очень просто. Достаточно написать функцию и пометить её аннотацией #[test].

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

Ключевое слово mod можно использовать не только для объявления внешнего модуля (как мы сделали это с first.rs и lib.rs), но и для создания встроенного модуля:

// в first.rs

mod test {
    #[test]
    fn basics() {
        // написать
    }
}

Мы запускаем тесты командой cargo test.

> cargo test
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
    Finished dev [unoptimized + debuginfo] target(s) in 1.00s
     Running /Users/ADesires/dev/lists/target/debug/deps/lists-86544f1d97438f1f

running 1 test
test first::test::basics ... ok

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

Ура, наш тест, который ничего не проверяет, успешно пройден! Теперь давайте напишем какую-нибудь проверку. В этом нам поможет макрос assert_eq!. В нём нет никакой особой магии тестирования. Он всего навсего сравнивает две штуки, которые ему передали, и паникует, если они не совпадают. Да, мы сигнализируем о проблеме при помощи паники!

mod test {
    #[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(3));
        assert_eq!(list.pop(), Some(2));

        // Вставляем новые значения, просто чтобы проверить, что ничего не сломается
        list.push(4);
        list.push(5);

        // Проверяем обычное удаление
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), Some(4));

        // Проверяем граничный случай
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), None);
    }
}

> cargo test

error[E0433]: failed to resolve: use of undeclared type or module `List`
  --> src/first.rs:43:24
   |
43 |         let mut list = List::new();
   |                        ^^^^ use of undeclared type or module `List`

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

mod test {
    use super::List;
    // всё остальное точно также
}

> cargo test

warning: unused import: `super::List`
  --> src/first.rs:45:9
   |
45 |     use super::List;
   |         ^^^^^^^^^^^
   |
   = note: #[warn(unused_imports)] on by default

    Finished dev [unoptimized + debuginfo] target(s) in 0.43s
     Running /Users/ADesires/dev/lists/target/debug/deps/lists-86544f1d97438f1f

running 1 test
test first::test::basics ... ok

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

Да!

Хотя, что это за предупреждение?.. В нашем тесте мы используем List явным образом!

…но только при запуске тестов! Чтобы угодить компилятору (и быть дружелюбным к другим программистам) мы должны явно указать, что весь модуль test должен быть скомпилирован только когда мы запускаем тесты.

#[cfg(test)]
mod test {
    use super::List;
    // всё остальное точно также
}

На этом тестирование завершено!

Метод drop

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

Надо ли нам беспокоиться об освобождении памяти? Технически — нет, вообще не надо! Как и C++, Rust использует деструкторы, чтобы автоматически освобождать ресурсы, после их использования. Тип имеет деструктор, если он реализует типаж, который называется Drop. Типажи — это научное название интерфейсов в языке Rust. Типаж Drop имеет следующий вид:

pub trait Drop {
    fn drop(&mut self);
}

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

Вы не должны реализовывать Drop, если у вас есть типы, реализующие Drop и всё, что вы хотите — это вызвать их деструкторы. В случае List, всё что ему нужно — это освободить голову, что, по идее приведёт к освобождению Box<Node>. Всё это будет сделано автоматически… с одним «но».

Автоматическая уборка может пойти не по плану.

Посмотрим на простой список:

list -> A -> B -> C

Когда удаляется list, он попытается удалить A, который попытается удалить B, который попытается удалить C. Возможно, кое-кто из вас занервничал. Это рекурсивный код, а рекурсивный код может привести к переполнению стека!

Некоторые из вас, возможно, подумали: «здесь точно хвостовая рекурсия, а любой приличный язык программирования гарантирует, что при хвостовой рекурсии переполнения не будет». На самом деле это неверно! Чтобы понять, почему, давайте вручную реализуем Drop так, как это сделал бы компилятор:

impl Drop for List {
    fn drop(&mut self) {
        // ПРИМЕЧАНИЕ: в реальном коде нельзя вызвать `drop` явно;
        // так что мы притворимся компилятором!
        self.head.drop(); // хвостовая рекурсия - хорошо!
    }
}

impl Drop for Link {
    fn drop(&mut self) {
        match *self {
            Link::Empty => {} // Готово!
            Link::More(ref mut boxed_node) => {
                boxed_node.drop(); // хвостовая рекурсия - хорошо!
            }
        }
    }
}

impl Drop for Box<Node> {
    fn drop(&mut self) {
        self.ptr.drop(); // ой, подождите, не хвостовая рекурсия!
        deallocate(self.ptr);
    }
}

impl Drop for Node {
    fn drop(&mut self) {
        self.next.drop();
    }
}

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

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);
        // `while let` == "повторяй, пока образец совпадает"
        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
            // здесь boxed_node выходит из области видимости и уничтожается;
            // но поле `next` заменяется на `Link::Empty`,
            // поэтому бесконечная рекурсия не возникает
        }
    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 1 test
test first::test::basics ... ok

test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured

Великолепно!

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

Наша реализация освобождения очень напоминает код while let Some(_) = self.pop() { }, который, безусловно, проще. Чем они отличаются, и какие проблемы с производительностью могут возникнуть, если мы обобщим наш список для хранения объектов любого типа, а не только целых чисел?

Раскрыть ответ

pop возвращает Option<i32> в то время, как наша реализация манипулирует только ссылками (Box<Node>). Поэтому наша реализация всего лишь переносит указатели на узлы, в то время как pop переносит значения, которые хранятся в узлах. Может быть очень дорого обобщать наш список, ведь кто-то может использовать его для экземпляров типа VBTWADI (VeryBigThingWithADropImpl — очень большая штука с реализацией Drop). Боксы способны запускать реализацию drop для своего содержимого непосредственно, так что у них нет такой проблемы. Ну, а поскольку VBTWADI — именно та штука, для которой связные списки гораздо предпочтительнее массивов, такое поведение немного разочарует.

Если вы хотите взять лучшее от обеих реализаций, вы можете добавить новый метод fn pop_node(&mut sefl) -> Link который корректно вызывается как из pop, так и из drop.

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

Итак, 6000 слов спустя, мы написали такой код:

use std::mem;

pub struct List {
    head: Link,
}

enum Link {
    Empty,
    More(Box<Node>),
}

struct Node {
    elem: i32,
    next: Link,
}

impl List {
    pub fn new() -> Self {
        List { head: Link::Empty }
    }

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: mem::replace(&mut self.head, Link::Empty),
        });

        self.head = Link::More(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match mem::replace(&mut self.head, Link::Empty) {
            Link::Empty => None,
            Link::More(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, Link::Empty);

        while let Link::More(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
        }
    }
}

#[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(3));
        assert_eq!(list.pop(), Some(2));

        // Вставляем новые значения, просто чтобы проверить, что ничего не сломается
        list.push(4);
        list.push(5);

        // Проверяем обычное удаление
        assert_eq!(list.pop(), Some(5));
        assert_eq!(list.pop(), Some(4));

        // Проверяем граничный случай
        assert_eq!(list.pop(), Some(1));
        assert_eq!(list.pop(), None);
    }
}

Только посмотрите! 80 строк, из них половина — тесты! Ну, я предупреждала, что первая глава потребует времени!

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

1/7. Целая прорва связных списков, чтобы выучить Rust: Плохой односвязный стек