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

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

В процессе мы, в основном, познакомимся с Rc и Arc, и это подготовит нас к следующему, кардинально отличному списку.

Создадим новый файл и назовём его third.rs:

// в lib.rs

pub mod first;
pub mod second;
pub mod third;

Пока никакой копи-пасты. Начнём с чистого листа.

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

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

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

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, и на этом закончим!

…

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

Основы

Сейчас мы уже знаем основы языка Rust, так что можем делать множество простых вещей.

Конструктор можно просто скопировать из предыдущей главы:

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

Методы push и pop теперь не имеют смысла. Вместо них мы напишем prepend (вставить в начало) и tail (получить хвост), которые делают приблизительно то же самое.

Начнём с prepend. Метод получает элемент и список. и возвращает список. Как и в случае с изменяемым списком, мы создадим новый узел, у которого старый список помещается в поле next. Единственное нововведение заключается в том, как получить значение для next, поскольку мы не можем ничего менять.

Ответом на наши молитвы является типаж Clone. Его реализуют практически все типы. Он предоставляет универсальный способ получить «похожую штуку» и при этом использует только разделяемую ссылку. Логически клон отличается от оригинала. Метод похож на копирующий конструктор в C++, но всегда вызывается явно.

Конкретно Rc использует Clone, чтобы увеличить счётчик ссылок на единицу. Поэтому вместо того, чтобы перемещать Box в подсписок, мы просто клонируем голову старого списка. Нам даже не придётся писать оператор match, поскольку Option предоставляет реализацию Clone, которая делает именно то, что нам нужно.

Ладно, давайте попробуем:

pub fn prepend(&self, elem: T) -> List<T> {
    List { head: Some(Rc::new(Node {
        elem: elem,
        next: self.head.clone(),
    }))}
}

> cargo build

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

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

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

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

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().map(|node| node.next.clone()) }
}

cargo build

error[E0308]: mismatched types
  --> src/third.rs:27:22
   |
27 |         List { head: self.head.as_ref().map(|node| node.next.clone()) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
   |
   = note: expected type `std::option::Option<std::rc::Rc<_>>`
              found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`

Грм, здесь мы напортачили. map ожидает, что мы вернём Y, но мы возвращаем Option<Y>. К счастью, есть ещё один известный паттерн для Option, так что мы можем просто вызвать and_then вместо map.

pub fn tail(&self) -> List<T> {
    List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}

cargo build

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

Теперь, когда у нас есть tail, мы, возможно, должны написать head, чтобы возвращать ссылку на первый элемент. По сути, это метод peek, который мы реализовали для изменяемого списка:

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

cargo build

Здорово.

Теперь у нас достаточно функциональности, чтобы её протестировать:

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.prepend(1).prepend(2).prepend(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // Убеждаемся, что tail работает с пустым списком
        let list = list.tail();
        assert_eq!(list.head(), None);

    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok

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

Превосходно!

Iter тоже идентичен реализации из нашего изменяемого списка:

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

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

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

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

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

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

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok

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

Кто вообще сказал, что динамическая типизация проще?

(наверняка, какие-то болваны)

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

Метод drop

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

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur_link = self.head.take();
        while let Some(mut boxed_node) = cur_link {
            cur_link = boxed_node.next.take();
        }
    }
}

Но теперь проблема возникает в теле цикла:

cur_link = boxed_node.next.take();

Здесь меняется узел внутри Box, но мы не может сделать то же самое с Rc; он предоставляет нам только разделяемый доступ, так как на него может указывать любое количество Rc-указателей.

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

Оказывается, в Rc есть метод, который делает именно то, что нам нужно — try_unwrap:

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

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

running 8 tests
test first::test::basics ... 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. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out

Великолепно! Здорово.

Arc

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

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

Чтобы получить потокобезопасность, мы должны использовать Arc. Arc полностью идентичен Rc за тем исключением, что счётчик ссылок модифицируется атомарно. Это влечёт небольшие накладные расходы, и если оно вам не надо, вы всегда можете использовать Rc. Всё, что нам надо с делать с нашим списком, это заменить каждое упоминание Rc на std::sync::Arc. И это всё. Мы потокобезопасны. Сделано!

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

Нет! В Rust потокобезопасность сломать нельзя!

Причина в том, что Rust моделирует потокобезопасность с помощью двух типажей: Send и Sync.

Тип относится к Send (отправляемый), если его можно безопасно передать в другой поток. Тип относится к Sync (синхронный), если его можно безопасно разделить между потоками. Есть правило: если T реализует Sync, то &T реализует Send. Безопасность в данном случае означает, что мы не можем устроить гонку данных (data races). Не путайте её с более общий случаем — состоянием гонки (race conditions).

Это типажи-маркеры или, говоря простым языком, они не предоставляют ни одного метода. Тип просто либо является Send, либо не является. Можно сказать, что это свойство типа, которое могут требовать другие API. Если тип не помечен как Send, компилятор проверяет, что его нельзя передавать в другой поток! Идеально!

Send и Sync автоматически реализуются для типов, состоящих только из полей Send и Sync. Похожим образом, типаж Copy может быть реализован только для типов, состоящих из Copy-типов. Но для Send и Sync компилятор идёт ещё дальше и реализует всё за вас.

Почти все типы — одновременно и Send, и Sync. Большинство типов относятся к Send, потому что они полностью владеют своими данными. Большинство типов относятся к Sync, потому что единственный способ разделить данные между потоками — воспользоваться разделяемой ссылкой, которая, как мы знаем, неизменяемая!

Однако существуют особые типы, которые нарушают эти свойства. Они обладают внутренней изменчивостью (interior mutability). До сих пор мы сталкивались только с унаследованной изменчивостью (или внешней изменчивостью): изменчивость значения наследуется у контейнера. Вы не можете просто взять и поменять какое-то поле неизменяемого объекта, просто потому, что вам так захотелось.

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

Какое отношение всё это имеет к Rc и Arc, спросите вы? Ну, они оба внутренне изменчивы из-за счётчика ссылок. Хуже того, этот счётчик разделяется между всеми экземплярами! Rc просто использует ячейку и это значит, что он не является потокобезопасным. Arc использует атомарный тип и это значит, что он является потокобезопасным. Естественно, вы не можете магически превратить тип в потокобезопасный, просто поместив его в Arc. Arc может только наследовать потокобезопасность, как и любой другой тип.

Я очень-очень-очень не хочу углубляться в тонкости атомарных моделей памяти или не-унаследованных реализаций Send. Излишне говорить, что по мере погружения в тему потокобезопасности Rust, всё становится сложнее. Для обычных программистов всё это просто работает и вам на самом деле не надо об этом думать.

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

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

use std::rc::Rc;

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

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

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

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

    pub fn prepend(&self, elem: T) -> List<T> {
        List { head: Some(Rc::new(Node {
            elem: elem,
            next: self.head.clone(),
        }))}
    }

    pub fn tail(&self) -> List<T> {
        List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
    }

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

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

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

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

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

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

#[cfg(test)]
mod test {
    use super::List;

    #[test]
    fn basics() {
        let list = List::new();
        assert_eq!(list.head(), None);

        let list = list.prepend(1).prepend(2).prepend(3);
        assert_eq!(list.head(), Some(&3));

        let list = list.tail();
        assert_eq!(list.head(), Some(&2));

        let list = list.tail();
        assert_eq!(list.head(), Some(&1));

        let list = list.tail();
        assert_eq!(list.head(), None);

        // Убеждаемся, что tail работает с пустым списком
        let list = list.tail();
        assert_eq!(list.head(), None);
    }

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

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

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