Сборка

Как водится, начнём со сборки списка. С нашей новой системой это довольно просто. Метод 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

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

Целая прорва связных списков, чтобы выучить Rust

Сборка

Когда следует выбирать внутреннюю изменчивость

Внедрение корней унаследованной изменчивости в разделяемые типы