Теперь, когда мы познакомились с Rc и внутренней изменчивостью, возникает интересный вопрос… а нельзя ли изменять объекты с помощью Rc? И, если это так, может быть двусвязный список можно сделать совершенно безопасным!

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

Создадим новый файл fourth.rs:

// и lib.rs

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

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

Предупреждение: по сути эта глава доказывает, что у нас возникла очень плохая идея.

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

Ключевой элемент нашей архитектуры — это тип RefCell. А сердцем RefCell являются пара методов:

fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;

Правила для borrow и borrow_mut точно такие же, как и для & и &mut: вы можете вызвать borrow столько раз, сколько захотите, но borrow_mut требует эксклюзивности.

RefCell проверяет возможность заимствования не статически (во время компиляции), а динамически (во время выполнения). Если вы нарушили правила, RefCell вызовет panic! и завершит программу. Почему методы возвращают объекты Ref и RefMut? Они, по сути, ведут себя как Rc, но только по отношению к заимствованию. Они также держат объект RefCell заимствованным, пока не выйдут из области видимости. Позже мы вернёмся к этому моменту.

Теперь, имея на руках Rc и RefCell, мы можем сделать из Rust… невероятно многословный, полностью изменяемый язык со сборкой мусора, который не умеет собирать циклические ссылки! О-фи-геть!

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

Так что, кажется, нам нужно что-то такое:

use std::rc::Rc;
use std::cell::RefCell;

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

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

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

> cargo build

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

warning: field is never used: `tail`
 --> src/fourth.rs:6:5
  |
6 |     tail: Link<T>,
  |     ^^^^^^^^^^^^^

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

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

warning: field is never used: `prev`
  --> src/fourth.rs:14:5
   |
14 |     prev: Link<T>,
   |     ^^^^^^^^^^^^^

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

Сборка

Как водится, начнём со сборки списка. С нашей новой системой это довольно просто. Метод new всё ещё тривиален — он просто заполняет все поля значением None. Кроме того, поскольку создание узла стало достаточно громоздким, вынесем его в отдельный метод.

impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

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

> cargo build

**МНОГО ПРЕДУПРЕЖДЕНИЙ О НЕИСПОЛЬЗУЕМЫХ ПЕРЕМЕННЫХ, НО КОД СОБИРАЕТСЯ**

Ура!

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

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

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

Хорошо, приступим:

pub fn push_front(&mut self, elem: T) {
    // новому узлы нужны +2 ссылки, любому другому +0
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            // не-пустой список, надо связать со старой головой
            old_head.prev = Some(new_head.clone()); // +1 new_head
            new_head.next = Some(old_head);         // +1 old_head
            self.head = Some(new_head);             // +1 new_head, -1 old_head
            // всего: +2 new_head, +0 old_head -- правильно!
        }
        None => {
            // пустой список, надо установить значение tail
            self.tail = Some(new_head.clone());     // +1 new_head
            self.head = Some(new_head);             // +1 new_head
            // всего: +2 new_head -- правильно!
        }
    }
}

cargo build

error[E0609]: no field `prev` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:39:26
   |
39 |                 old_head.prev = Some(new_head.clone()); // +1 new_head
   |                          ^^^^ unknown field

error[E0609]: no field `next` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:40:26
   |
40 |                 new_head.next = Some(old_head);         // +1 old_head
   |                          ^^^^ unknown field

Что ж. Ошибка компилятора. Хорошее начало. Хорошее начало.

Почему нам недоступны поля prev и next в наших узлах? Раньше это работало, потому что у нас был Rc<Node>. Похоже, проблемы возникают из-за RefCell.

Кажется, пора прочитать документацию.

Гуглим «rust refcell»

щёлкает по первой ссылке

Работа с изменяемой памятью с динамической проверкой правил заимствования
См. документацию на модуль for more.

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

Разделяемые изменяемые контейнеры
Значения типов Cell<T> и RefCell<T> можно изменять через разделяемые ссылки (т. е., в целом, через тип &T), в то время как большинство типов Rust можно изменять только через уникальные ссылки (&mut T). Говорят, что Cell<T> и RefCell<T> обеспечивают «внутреннюю изменяемость» (interior mutability), в то время как обычные типы Rust демонстрируют «унаследованную изменяемость» (inherited mutability).
Типы-ячейки бывают двух видов: Cell<T> и RefCell<T>. Cell<T> предоставляет методы get и set, которые изменяют внутреннее значение за один вызов метода. Однако, Cell<T> совместим только с типами, реализующими Copy. Для других типов необходимо использовать тип RefCell<T>, получая блокировку на запись перед изменением.
RefCell<T> использует время жизни Rust, чтобы реализовать «динамическое заимствование» — процесс, посредством которого можно претендовать на временный, эксклюзивный изменяемый доступ к внутреннему значению. Заимствование для RefCell<T> отслеживается «во время выполнения», в отличие от обычных ссылочных типов Rust, которые отслеживаются полностью статически, во время компиляции. Поскольку заимствования RefCell<T> динамичны, возможна попытка заимствовать значение, которое уже заимствовано на изменение; когда это происходит, в потоке возникает паника.
Когда следует выбирать внутреннюю изменчивость
Обычная для языка унаследованная изменчивость предполагает, что для изменения значения требуется эксклюзивный доступ. Именно благодаря ей Rust может эффективно рассуждать о псевдонимах (указателях, ссылающихся на одну и ту же область памяти), предотвращая ошибки уже на этапе компиляции. По этой причине наследуемая изменчивость является предпочтительной, а внутреннюю изменчивость следует считать чем-то вроде крайней меры. Поскольку типы-ячейки допускают мутации там, где они обычно запрещены, встречаются ситуации, где внутренняя изменчивость не только уместна, но даже необходима. Например:
Внедрение корней унаследованной изменчивости в разделяемые типы.
Детали реализации логически чистых методов.
Изменяющие реализации Clone.
Внедрение корней унаследованной изменчивости в разделяемые типы
Разделяемые умные типы-указатели, включая Rc<T> и Arc<T> предоставляют контейнеры, которые могут быть клонированы и разделены между несколькими частями приложения. Поскольку может существовать несколько ссылок на хранящиеся в них значения, их можно заимствовать только посредством разделяемых, а не изменяемых ссылок. Без ячеек было бы вообще невозможно менять данные внутри разделяемых боксов!
Общей практикой является помещение RefCell<T> в разделяемый тип-указатель, чтобы обеспечить возможность изменения:
use std::collections::HashMap; use std::cell::RefCell; use std::rc::Rc; fn main() { let shared_map: Rc<RefCell<_>> = Rc::new(RefCell::new(HashMap::new())); shared_map.borrow_mut().insert("africa", 92388); shared_map.borrow_mut().insert("kyoto", 11837); shared_map.borrow_mut().insert("piccadilly", 11826); shared_map.borrow_mut().insert("marbles", 38); }
Обратите внимание, что в этом примере используется Rc<T>, а не Arc<T>. RefCell<T> можно использовать только в однопоточных сценариях. Используйте Mutex<T>, если вам нужна разделяемая изменчивость в многопоточном окружении.

Да, дока по Rust всё ещё невероятно крута.

Больше всего в приведённом коде нас интересует вот эта строка:

shared_map.borrow_mut().insert("africa", 92388);

А конкретно — вызов borrow_mut. Похоже, мы должны явно заимствовать RefCell. Оператор . за нас этого не делает. Странно. Попробуем:

pub fn push_front(&mut self, elem: T) {
    let new_head = Node::new(elem);
    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        }
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

> cargo build

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

Ага, получилось! Снова победили доки.

Разборка

У pop_front должна быть та же самая базовая логика, что и у push_front, но обращённая. Попробуем:

pub fn pop_front(&mut self) -> Option<T> {
    // надо получить старую голову, убедимся, что количество ссылок -2
    self.head.take().map(|old_head| {                         // -1 old_head
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {                               // -1 new_head
                // не пустой список
                new_head.borrow_mut().prev.take();            // -1 old_head
                self.head = Some(new_head);                   // +1 new_head
                // всего: -2 старых, +0 новых
            }
            None => {
                // пустой список
                self.tail.take();                             // -1 old_head
                // всего: -2 старых, (новых нет)
            }
        }
        old_head.elem
    })
}

> cargo build

error[E0609]: no field `elem` on type `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>`
  --> src/fourth.rs:64:22
   |
64 |             old_head.elem
   |                      ^^^^ unknown field

ТАК. RefCells. Чувствую, нам снова нужен borrow_mut…

pub fn pop_front(&mut self) -> Option<T> {
    self.head.take().map(|old_head| {
        match old_head.borrow_mut().next.take() {
            Some(new_head) => {
                new_head.borrow_mut().prev.take();
                self.head = Some(new_head);
            }
            None => {
                self.tail.take();
            }
        }
        old_head.borrow_mut().elem
    })
}

cargo build

error[E0507]: cannot move out of borrowed content
  --> src/fourth.rs:64:13
   |
64 |             old_head.borrow_mut().elem
   |             ^^^^^^^^^^^^^^^^^^^^^^^^^^ cannot move out of borrowed content

вздох

cannot move out of borrowed content

Не могу извлечь заимствованное содержимое.

Грм… Похоже, на самом деле Box нас баловал. borrow_num возвращает нам &mut Nude<T>, но мы не можем извлечь оттуда ничего!

Нам нужно что-то, что возьмёт у нас RefCell<T> и вернёт нам T. Давайте проверим доки на предмет наличия чего-то похожего:

fn into_inner(self) -> T
Получает RefCell, возвращает завёрнутое значение.

Выглядит многообещающе!

old_head.into_inner().elem

> cargo build

error[E0507]: cannot move out of an `Rc`
  --> src/fourth.rs:64:13
   |
64 |             old_head.into_inner().elem
   |             ^^^^^^^^ cannot move out of an `Rc`

Вот блин. into_inner хочет извлечь RefCell, но мы не можем её предоставить, потому что она находится в Rc. В предыдущей главе мы видели, что Rc<T> разрешает доступ к своему значению только по разделяемой ссылке. И это правильно, потому что главный смысл указателей с подсчётом ссылок в том, что они разделяемые!

Это стало для нас проблемой, когда мы писали drop для списка с подсчётом ссылок. Воспользуемся тем же решением, а именно, методом Rc::try_unwrap, который возвращает содержимое Rc, если счётчик ссылок равен 1.

Rc::try_unwrap(old_head).unwrap().into_inner().elem

Rc::try_unwrap возвращает Result<T, Rc<T>>. Значения типа Result — расширенный тип Option в котором у варианта None появляются связанные с ним данные. В нашем случае — Rc, из которого мы пытаемся достать значение. Поскольку нас не беспокоят возможные ошибки (если мы правильно написали программу, она обязана завершиться успешно), мы просто вызываем unwrap.

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

> cargo build

error[E0599]: no method named `unwrap` found for type `std::result::Result<std::cell::RefCell<fourth::Node<T>>, std::rc::Rc<std::cell::RefCell<fourth::Node<T>>>>` in the current scope
  --> src/fourth.rs:64:38
   |
64 |             Rc::try_unwrap(old_head).unwrap().into_inner().elem
   |                                      ^^^^^^
   |
   = note: the method `unwrap` exists but the following trait bounds were not satisfied:
           `std::rc::Rc<std::cell::RefCell<fourth::Node<T>>> : std::fmt::Debug`

Да что ты будешь делать? unwrap у Result требует, чтобы тип ошибки мог печатать себя при отладке. А RefCell<T> реализует Debug только тогда, когда его реализует T. А Node не реализует Debug.

Вместо того, чтобы добавлять реализацию, выполним обходной маневр, преобразовав Result в Options с помощью вызова ok:

Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem

НУ, ПОЖАЛУЙСТА.

cargo build

ДА.

уф

Получилось.

Мы реализовали push и pop.

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

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

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

        // Проверяем, что пустой список ведёт себя правильно
        assert_eq!(list.pop_front(), None);

        // Заполняем список
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

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

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

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

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

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 9 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::basics ... ok
test fifth::test::iter_mut ... ok
test third::test::basics ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok

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

В яблочко.

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

Rc не умеет работать с циклическими ссылками. Если есть цикл, объекты поддерживают существование друг друга. А двусвязный список, как выяснилось — одна большая цепочка из крошечных циклов! Так что когда мы уничтожаем наш список, два конечных узла уменьшают свои счётчики до 1… а затем ничего не происходит. Ладно, когда наш список содержит ровно один узел, счётчик ссылок сбрасывается но нуля. Но в идеале список должен корректно работать даже когда нём больше одного элемента. Возможно, это только моё мнение.

Как мы видели, удаление элементов оказалось довольно болезненным. Поэтому простейший способ для нас — это просто вызывать pop, пока мы не получим None:

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

cargo build

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

Можно было заняться реализацией версий _back для методов push и pop, но это всего лишь копи-паста. К ней мы вернёмся позже в этой главе. А сейчас давайте посмотрим на более интересные вещи!

Метод peek

Хорошо, мы справились с методами push и pop. Не буду врать, я немного волнуюсь. Проверка правильности на этапе компиляции — охрененное чувство.

Надо немного успокоиться и сделать что-нибудь простое: скажем, реализовать peek_front. Этот метод всегда был простым. Должен и остаться простым, правда?

Правда?

Фактически, я уверена, что могу просто скопировать старое решение!

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

Но, погодите. Не в этот раз.

pub fn peek_front(&self) -> Option<&T> {
    self.head.as_ref().map(|node| {
        // ЗАИМСТВОВАНИЕ!!!!
        &node.borrow().elem
    })
}

ХА.

cargo build

error[E0515]: cannot return value referencing temporary value
  --> src/fourth.rs:66:13
   |
66 |             &node.borrow().elem
   |             ^   ----------^^^^^
   |             |   |
   |             |   temporary value created here
   |             |
   |             returns a value referencing data owned by the current function

Ладно, просто сожгу свой компьютер.

Здесь та же самая логика, что и в односвязном стеке. Почему всё по другому? ПОЧЕМУ?

Ответ на самом деле отражает мораль всей этой главы: RefCell всё усложняет. До текущего момента RefCell просто доставлял неудобства. Теперь он превратился в ночной кошмар.

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

fn borrow<'a>(&'a self) -> Ref<'a, T>;
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>;

В разделе о представлении я писала:

RefCell проверяет возможность заимствования не статически (во время компиляции), а > динамически (во время выполнения). Если вы нарушили правила, RefCell вызовет panic! и завершит программу. Почему методы возвращают объекты Ref и RefMut? Они, по сути, ведут себя как Rc, но только по отношению к заимствованию. Они также держат объект RefCell заимствованным, пока не выйдут из области видимости. Позже мы вернёмся к этому моменту.

Это «позже» наступило.

Ref и RefMut реализуют Deref и DerefMut соответственно. В большинстве случаев они ведут себя точно так же как &T и &mut T. Однако из-за особенностей работы этих типажей, возвращаемая ссылка связана с временем жизни Ref, а не с самой ячейкой RefCell. Это значит, что Ref должна оставаться доступна до тех пор, пока мы пользуемся полученной ссылкой.

Это нужно, чтобы сохранить корректность. Когда Ref уничтожается, он сообщает RefCell, что больше не заимствуется. Таким образом, если бы нам удалось сохранить нашу ссылку дольше, чем существует Ref, мы бы могли создать RefMut на ту же самую область памяти. Тогда бы у нас одновременны были изменяемая и разделяемая ссылки на одно и то же значение, что полностью ломает систему типов Rust.

Итак, что нам остаётся? Мы хотим всего лишь вернуть ссылку, но для этого нам надо сохранить Ref. Но как только мы возвращаем ссылку из peek, функция завершается и Ref выходит из области видимости.

😖

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

Но… что если мы откажемся от идеи полностью скрывать детали реализации? Что если мы будем возвращать Ref?

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

> cargo build

error[E0412]: cannot find type `Ref` in this scope
  --> src/fourth.rs:63:40
   |
63 |     pub fn peek_front(&self) -> Option<Ref<T>> {
   |                                        ^^^ not found in this scope
help: possible candidates are found in other modules, you can import them into scope
   |
1  | use core::cell::Ref;
   |
1  | use std::cell::Ref;
   |

Бла, бла, бла. Надо кое-что импортировать.

use std::cell::{Ref, RefCell};

> cargo build

error[E0308]: mismatched types
  --> src/fourth.rs:64:9
   |
64 | /         self.head.as_ref().map(|node| {
65 | |             node.borrow()
66 | |         })
   | |__________^ expected type parameter, found struct `fourth::Node`
   |
   = note: expected type `std::option::Option<std::cell::Ref<'_, T>>`
              found type `std::option::Option<std::cell::Ref<'_, fourth::Node<T>>>`

Хмм… всё правильно. У нас есть Ref<Node<T>>, но нам нужен Ref<T>. Мы могли бы отказаться от всякой надежды на инкапсуляцию и просто возвращать то, что есть. Мы могли бы ещё больше усложнить код и завернуть Ref<Node<T>> в новый тип, чтобы предоставлять доступ только к &T.

Оба варианта так себе.

Вместо этого, углубимся в тему. Давайте немного повеселимся. Источник нашего веселья — вот это чудовище:

fn map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
    where F: FnOnce(&T) -> &U,
          U: ?Sized

Создаёт новую Ref для компонента заимствованных данных.

Да: точно также, как вы можете вызывать map для Option, вы можете вызывать map для Ref.

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

Мне нравится, что я нашла крутое решение. Люблю такие штуки.

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

> cargo build

Да-да-да-да.

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

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    list.push_front(1); list.push_front(2); list.push_front(3);

    assert_eq!(&*list.peek_front().unwrap(), &3);
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test third::test::basics ... ok
test second::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok

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

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

Симметричный мусор

Что ж, давайте разберёмся со всей этой комбинаторной симметрией.

Всё, что нам нужно, это выполнить простую замену текста:

tail <-> head
next <-> prev
front -> back

Да, нам также надо написать варианты _mut для методов peek.

use std::cell::{Ref, RefCell, RefMut};

//..

pub fn push_back(&mut self, elem: T) {
    let new_tail = Node::new(elem);
    match self.tail.take() {
        Some(old_tail) => {
            old_tail.borrow_mut().next = Some(new_tail.clone());
            new_tail.borrow_mut().prev = Some(old_tail);
            self.tail = Some(new_tail);
        }
        None => {
            self.head = Some(new_tail.clone());
            self.tail = Some(new_tail);
        }
    }
}

pub fn pop_back(&mut self) -> Option<T> {
    self.tail.take().map(|old_tail| {
        match old_tail.borrow_mut().prev.take() {
            Some(new_tail) => {
                new_tail.borrow_mut().next.take();
                self.tail = Some(new_tail);
            }
            None => {
                self.head.take();
            }
        }
        Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
    })
}

pub fn peek_back(&self) -> Option<Ref<T>> {
    self.tail.as_ref().map(|node| {
        Ref::map(node.borrow(), |node| &node.elem)
    })
}

pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
    self.tail.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
    self.head.as_ref().map(|node| {
        RefMut::map(node.borrow_mut(), |node| &mut node.elem)
    })
}

И значительно расширить наши тесты:

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

    // Проверяем, что пустой список ведёт себя правильно
    assert_eq!(list.pop_front(), None);

    // Заполняем список
    list.push_front(1);
    list.push_front(2);
    list.push_front(3);

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

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

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

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

    // ---- back -----

    // Проверяем, что пустой список ведёт себя правильно
    assert_eq!(list.pop_back(), None);

    // Заполняем список
    list.push_back(1);
    list.push_back(2);
    list.push_back(3);

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

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

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

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

#[test]
fn peek() {
    let mut list = List::new();
    assert!(list.peek_front().is_none());
    assert!(list.peek_back().is_none());
    assert!(list.peek_front_mut().is_none());
    assert!(list.peek_back_mut().is_none());

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

    assert_eq!(&*list.peek_front().unwrap(), &3);
    assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
    assert_eq!(&*list.peek_back().unwrap(), &1);
    assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
}

Есть ли сценарии, которые мы не протестировали? Возможно. Количество комбинаций методов действительно стало очень большим. Но, по крайней мере, наш код не явно ошибочный.

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 10 tests
test first::test::basics ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test fourth::test::peek ... ok
test second::test::iter ... ok
test third::test::iter ... ok
test second::test::into_iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok

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

Прекрасно. Копи-паста — лучший способ программирования.

Итерация

Попробуем написать итераторы для нашего неудачливого списка.

IntoIter

IntoInter, как всегда — самый простой. Просто завернём стек в новый тип и вызовем pop:

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

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

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

Но у нас появилось новое интересное усовершенствование. Раньше у нас был только один «натуральный» порядок перебора элементов, а дек по своей природе двунаправленный. Что особенного в переборе от начала к концу? Что если кому-то понадобится итерация в другом направлении?

На самом деле в Rust есть ответ на этот вопрос: DoubleEndedIterator. DoubleEndedIterator наследует Iterator (это значит, что все объекты, реализующие DoubleEndedIterator реализуют так же и Iterator) и добавляет один новый метод: next_back. У него такая же сигнатура, как и у next, но он перебирает элементы с другого конца. Семантика DoubleEndedIterator очень удобна для нашего случая: итератор становится деком. Мы можем брать элементы как с начала, так и с конца, пока два конца не встретятся и в этой точке итератор станет пустым.

Нам нечасто приходится вызывать next вручную. То же самое и с next_back — этот метод не так важен пользователям DoubleEndedIterator. Лучшая часть интерфейса — это метод rev, который заворачивает итератор, чтобы создать другой итератор, который возвращает элементы в обратном порядке. Семантика здесь довольно проста: вызов next у обращённого итератора — это на самом деле вызов next_back.

В любом случае, поскольку у нас уже есть дек, предоставить новый API довольно просто:

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

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

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

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

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 11 tests
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::iter ... ok
test third::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok

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

Прекрасно.

Iter

Iter не будет таким снисходительным. Нам снова придётся иметь дело с этими ужасными Ref! Из-за Ref мы не сможем хранить &Node, как мы делали раньше. Вместо этого попробуем хранить Ref<Node>.

pub struct Iter<'a, T>(Option<Ref<'a, Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.borrow()))
    }
}

> cargo build

Пока всё хорошо. Реализация next окажется чуть сложнее, но я думаю, это будет та же самая базовая логика, как и в старом IterMut для стека, с некоторыми дополнительными приседаниями из-за RefCell:

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = Ref<'a, T>;
    fn next(&mut self) -> Option<Self::Item> {
        self.0.take().map(|node_ref| {
            self.0 = node_ref.next.as_ref().map(|head| head.borrow());
            Ref::map(node_ref, |node| &node.elem)
        })
    }
}

cargo build

error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:155:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   -------- borrow is only valid in the closure body
    |             |
    |             reference to `node_ref` escapes the closure body here

error[E0505]: cannot move out of `node_ref` because it is borrowed
   --> src/fourth.rs:156:22
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- lifetime `'1` appears in the type of `self`
154 |         self.0.take().map(|node_ref| {
155 |             self.0 = node_ref.next.as_ref().map(|head| head.borrow());
    |             ------   -------- borrow of `node_ref` occurs here
    |             |
    |             assignment requires that `node_ref` is borrowed for `'1`
156 |             Ref::map(node_ref, |node| &node.elem)
    |                      ^^^^^^^^ move out of `node_ref` occurs here

Ну, понеслась!

node_ref живёт недостаточно долго. В отличие от обычных ссылок, Rust не позволяет нам повторно использовать Ref подобным образом. Ref, который мы получили из head.borrow(), существует до тех пор, пока существует node_ref, который уничтожается при вызове Ref::map.

Функция, которая нам нужна, существует, и она называется map_split:

pub fn map_split<U, V, F>(orig: Ref<'b, T>, f: F) -> (Ref<'b, U>, Ref<'b, V>) where
    F: FnOnce(&T) -> (&U, &V),
    U: ?Sized,
    V: ?Sized,

Уф. Давайте попробуем.

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = next.as_ref().map(|head| head.borrow());

        elem
    })
}

cargo build
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0521]: borrowed data escapes outside of closure
   --> src/fourth.rs:159:13
    |
153 |     fn next(&mut self) -> Option<Self::Item> {
    |             --------- `self` is declared here, outside of the closure body
...
159 |             self.0 = next.as_ref().map(|head| head.borrow());
    |             ^^^^^^   ---- borrow is only valid in the closure body
    |             |
    |             reference to `next` escapes the closure body here

Рррр. Нам снова нужен Ref::map чтобы у нас было правильное время жизни. Но Ref::map возвращает Ref, а нам нужен Option<Ref>, но для этого нам надо пройти сквозь Ref, чтобы вызвать map для нашего Option…

долго смотрит вдаль

???

fn next(&mut self) -> Option<Self::Item> {
    self.0.take().map(|node_ref| {
        let (next, elem) = Ref::map_split(node_ref, |node| {
            (&node.next, &node.elem)
        });

        self.0 = if next.is_some() {
            Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
        } else {
            None
        };

        elem
    })
}

error[E0308]: mismatched types
   --> src/fourth.rs:162:22
    |
162 |                 Some(Ref::map(next, |next| &**next.as_ref().unwrap()))
    |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `fourth::Node`, found struct `std::cell::RefCell`
    |
    = note: expected type `std::cell::Ref<'_, fourth::Node<_>>`
               found type `std::cell::Ref<'_, std::cell::RefCell<fourth::Node<_>>>`

Ну да. Правильно. У нас несколько RefCell. Чем дальше мы углубляемся в список, тем более вложенными становятся RefCell. Нам потребуется поддерживать что-то вроде стека Ref для представления всех объектов, на которые мы ссылаемся, потому что если мы перестаём наблюдать за элементом, нам надо снизить на единицу счётчик заимствований у каждого RefCell, который находится перед ним…

Кажется, здесь уже ничего не сделаешь. Это тупик. Давайте выбираться из всех этих RefCell.

Что насчёт наших Rc? Кто вообще сказал, что нам нужно хранить ссылки? Почему мы не можем просто вызвать Clone у Rc, чтобы получить удобный указатель в середине списка?

pub struct Iter<T>(Option<Rc<Node<T>>>);

impl<T> List<T> {
    pub fn iter(&self) -> Iter<T> {
        Iter(self.head.as_ref().map(|head| head.clone()))
    }
}

impl<T> Iterator for Iter<T> {
    type Item =

Э-э-э… Подождите, а что мы теперь возвращаем? &T? Ref<T>?

Ни один из них не работает… у нашего Iter в любом случае нет времени жизни! И &T, и Ref<T> требуют объявления какого-то времени жизни перед тем, как мы сможем вызвать next. Но всё, что мы сможем получить из нашего Rc, будет заимствованием Iterator… мозг… кипит… аааааааааааа

Может быть, мы можем… вызвать map… для Rc… чтобы получить Rc<T>? Так вообще можно? В доках Rc, похоже, ничего подобного нет. На самом деле, кто-то сделал крейт, который это умеет.

Но, подождите, даже если у нас это получится, мы получим ещё большую проблему: ужасную угрозу инвалидации итератора. Раньше мы не сталкивались с инвалидацией итератора, потому что Iter заимствовал список, оставляя его, в целом, неизменяемым. Однако, если бы наш итератор возвращал Rc, ему вообще бы не пришлось заимствовать список! Это значит, что люди могут начать вызывать push и pop, пока у них есть указатель на список!

О, боже, во что всё это выльется?

Ну, в принципе, с push всё в порядке. Мы видим какую-то часть списка и список будет расти за пределами поля нашего зрения. Ничего страшного.

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

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

И даже тогда у нас не возникнет висячих указателей или чего-то похожего: программа детерминировано запаникует!

Но необходимость иметь дело с инвалидацией итераторов в дополнение к вызову map у Rc кажется просто… плохой. Rc<RefCell> окончательно нас подвёл. Интересно, мы столкнулись с инверсией случая с устойчивым стеком. В то время как устойчивый стек не мог справиться с владением, но мог днями напролёт предоставлять ссылки, наш список не испытывает проблем с владением, не не может справиться со ссылками.

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

Блин, да мы могли бы сделать несколько конкурентных IterMuts, которые проверяли бы наличие изменяемого доступа к одному и тому же элементу прямо во время работы программы!

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

В любом случае, я отказываюсь от реализации Iter и IterMut. Можно было бы, но… получается некрасиво.

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

Ладно, вот реализация 100% безопасного двусвязного списка на Rust. Реализация оказалась ночным кошмаром, список раскрывает детали реализации и не поддерживает ряд фундаментальных операций.

Но его можно реализовать.

Кстати, я думаю, что у нас слишком много «ненужных» проверок между Rc и RefCell. В взяла слово ненужных в кавычки, потому что на самом деле они необходимы для гарантий реальной безопасности. У нас есть несколько мест, где они нужны. У двусвязных списков действительно запутанное взаимодействие псевдонимов и владения!

Тем не менее, вот то, что нам удалось сделать. Особенно если нас не страшит раскрытие дателей реализации.

Далее мы попробуем другой подход: вернём себе контроль, сделав реализацию небезопасной.

use std::rc::Rc;
use std::cell::{Ref, RefMut, RefCell};

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

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

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


impl<T> Node<T> {
    fn new(elem: T) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(Node {
            elem: elem,
            prev: None,
            next: None,
        }))
    }
}

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

    pub fn push_front(&mut self, elem: T) {
        let new_head = Node::new(elem);
        match self.head.take() {
            Some(old_head) => {
                old_head.borrow_mut().prev = Some(new_head.clone());
                new_head.borrow_mut().next = Some(old_head);
                self.head = Some(new_head);
            }
            None => {
                self.tail = Some(new_head.clone());
                self.head = Some(new_head);
            }
        }
    }

    pub fn push_back(&mut self, elem: T) {
        let new_tail = Node::new(elem);
        match self.tail.take() {
            Some(old_tail) => {
                old_tail.borrow_mut().next = Some(new_tail.clone());
                new_tail.borrow_mut().prev = Some(old_tail);
                self.tail = Some(new_tail);
            }
            None => {
                self.head = Some(new_tail.clone());
                self.tail = Some(new_tail);
            }
        }
    }

    pub fn pop_back(&mut self) -> Option<T> {
        self.tail.take().map(|old_tail| {
            match old_tail.borrow_mut().prev.take() {
                Some(new_tail) => {
                    new_tail.borrow_mut().next.take();
                    self.tail = Some(new_tail);
                }
                None => {
                    self.head.take();
                }
            }
            Rc::try_unwrap(old_tail).ok().unwrap().into_inner().elem
        })
    }

    pub fn pop_front(&mut self) -> Option<T> {
        self.head.take().map(|old_head| {
            match old_head.borrow_mut().next.take() {
                Some(new_head) => {
                    new_head.borrow_mut().prev.take();
                    self.head = Some(new_head);
                }
                None => {
                    self.tail.take();
                }
            }
            Rc::try_unwrap(old_head).ok().unwrap().into_inner().elem
        })
    }

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

    pub fn peek_back(&self) -> Option<Ref<T>> {
        self.tail.as_ref().map(|node| {
            Ref::map(node.borrow(), |node| &node.elem)
        })
    }

    pub fn peek_back_mut(&mut self) -> Option<RefMut<T>> {
        self.tail.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

    pub fn peek_front_mut(&mut self) -> Option<RefMut<T>> {
        self.head.as_ref().map(|node| {
            RefMut::map(node.borrow_mut(), |node| &mut node.elem)
        })
    }

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

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        while self.pop_front().is_some() {}
    }
}

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

impl<T> Iterator for IntoIter<T> {
    type Item = T;

    fn next(&mut self) -> Option<T> {
        self.0.pop_front()
    }
}

impl<T> DoubleEndedIterator for IntoIter<T> {
    fn next_back(&mut self) -> Option<T> {
        self.0.pop_back()
    }
}

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

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

        // Проверяем, что пустой список ведёт себя правильно
        assert_eq!(list.pop_front(), None);

        // Заполняем список
        list.push_front(1);
        list.push_front(2);
        list.push_front(3);

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

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

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

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

        // ---- back -----

        // Проверяем, что пустой список ведёт себя правильно
        assert_eq!(list.pop_back(), None);

        // Заполняем список
        list.push_back(1);
        list.push_back(2);
        list.push_back(3);

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

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

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

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

    #[test]
    fn peek() {
        let mut list = List::new();
        assert!(list.peek_front().is_none());
        assert!(list.peek_back().is_none());
        assert!(list.peek_front_mut().is_none());
        assert!(list.peek_back_mut().is_none());

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

        assert_eq!(&*list.peek_front().unwrap(), &3);
        assert_eq!(&mut *list.peek_front_mut().unwrap(), &mut 3);
        assert_eq!(&*list.peek_back().unwrap(), &1);
        assert_eq!(&mut *list.peek_back_mut().unwrap(), &mut 1);
    }

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

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

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

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