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

Ладно, что такое связный список? Ну, в целом, это набор кусочков данных в куче, которые последовательно указывают друг на друга. (Да, я знаю, что разработчикам ядра куча недоступна, мы сейчас не об этом!) Связные списки — это то, что процедурные программисты не станут трогать 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);

Создание рекурсивной структуры данных:

#![allow(unused)]
fn main() {
#[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 тоже никто не использует. Давайте с этим разберёмся! Напишем немного кода для нашего списка!