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

Что ж, назад — к чертёжной доске! Будем рисовать представление.

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

list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D

Но в итоге мы хотим, чтобы память выглядела так:

list1 -> A ---+
              |
              v
list2 ------> B -> C -> D
              ^
              |
list3 -> X ---+

С боксами такая штука работать не будет, поскольку элементом B на рисунке одновременно владеют (разделяют владение) три переменные. Какая из них будет его освобождать? Если удалить list2, приведёт ли это к освобождению B? В случае боксов мы определённо должны были бы этого ожидать!

Функциональным языкам — да, по сути, всем языкам — это сходит с рук за счёт сборки мусора. Благодаря этой магии, B освободится только после того, как исчезнет последняя ссылка на него. Ура!

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

Как же работает сборка мусора на основе подсчёта ссылок? Rc! Rc — это то же самое, что и Box, который можно дублировать. Его память освободится только тогда, когда будут уничтожены все дубли Rc. К сожалению, эта гибкость ведёт к серьёзному ограничению: можно получить только разделяемую ссылку на внутренний объект. Это означает, что мы не можем даже ни забрать данные из наших списков, ни изменить их.

Так что на что должно быть похоже наше представление данных? Ну, раньше у нас было:

pub struct List<T> {
    head: Link<T>,
}

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

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

Можем ли мы просто заменить Box на Rc?

// в third.rs

pub struct List<T> {
    head: Link<T>,
}

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

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

cargo build

error[E0412]: cannot find type `Rc` in this scope
 --> src/third.rs:5:23
  |
5 | type Link<T> = Option<Rc<Node<T>>>;
  |                       ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
  |
1 | use std::rc::Rc;
  |

Блин, какая едкая насмешка. В отличие от всего, что мы использовали при разработке изменяемых списков, Rc настолько отстоен, что даже не импортируется автоматически. Что за неудачник.

use std::rc::Rc;

cargo build

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

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

warning: field is never used: `next`
  --> src/third.rs:11:5
   |
11 |     next: Link<T>,
   |     ^^^^^^^^^^^^^

Выглядит неплохо. Rust — всё ещё полностью тривиален для написания. Держу пари, мы просто заменим Box на Rc, и на этом закончим!

...

Нет. У нас не выйдет.