Оглавление

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

Переизобрести велосипед
Сделать наш список способным содержать элементы любого типа
Добавить метод peek
Реализовать итератор

В процессе мы узнаем о:

Продвинутом использовании Option
Обобщениях
Времени жизни
Итераторах

Для начала создадим новый файл second.rs:

// в lib.rs

pub mod first;
pub mod second;

И скопируем в него содержимое first.rs.

Использование Option

Внимательные читатели могли заметить, что мы, фактически, переизобрели не самую удачную версию Option:

enum Link {
    Empty,
    More(Box<Node>),
}

Link — это просто Option<Box<Node>>. Приятно, что нам не надо было везде писать Option<Box<Node>> и, в отличие от pop, не надо было делать реализацию, доступную всему внешнему миру, что, кажется, неплохо. Однако, в Option есть несколько поистине приятных методов, которые нам пришлось написать самим. Давайте не будем больше так делать и заменим всё на вызовы методов Option. Для начала давайте без изысков просто переименуем все элементы в Some и None:

use std::mem;

pub struct List {
    head: Link,
}

// да, псевдонимы типов!
type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

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

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: mem::replace(&mut self.head, None),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match mem::replace(&mut self.head, None) {
            None => None,
            Some(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    fn drop(&mut self) {
        let mut cur_link = mem::replace(&mut self.head, None);
        while let Some(mut boxed_node) = cur_link {
            cur_link = mem::replace(&mut boxed_node.next, None);
        }
    }
}

Код не стал кардинально лучше, но основную выгоду нам принесут методы Option.

Во-первых, mem::replace(&mut option, None) — настолько распространённая идиома, что Option просто взял и превратил её в метод take.

pub struct List {
    head: Link,
}

type Link = Option<Box<Node>>;

struct Node {
    elem: i32,
    next: Link,
}

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

    pub fn push(&mut self, elem: i32) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<i32> {
        match self.head.take() {
            None => None,
            Some(node) => {
                self.head = node.next;
                Some(node.elem)
            }
        }
    }
}

impl Drop for List {
    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();
        }
    }
}

Во-вторых, match option { None => None, Some(x) => Some(y) } — настолько распространённая идиома, что её назвали map (отображение). Метод map принимает функцию, которая берёт x, отдаёт y, а затем с её помощью превращает Some(x) в Some(y). Мы могли бы написать подходящую функции и передать её в map, но вместо этого мы встроим её в место вызова.

Для этого воспользуемся замыканиями. Замыкания — это анонимные функции (то есть функции без имени) с дополнительной супер-способностью: им доступны локальные переменные вне замыкания! Благодаря этому они супер-удобны для условной логики любого рода. В нашем коде match встречается в единственном месте — методе pop, так что давайте просто его перепишем:

pub fn pop(&mut self) -> Option<i32> {
    self.head.take().map(|node| {
        self.head = node.next;
        node.elem
    })
}

Так намного лучше. Давайте убедимся, что мы ничего не сломали:

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok

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

Великолепно! Теперь от внешнего вида перейдём к улучшению поведения.

Всё обобщаем

Мы уже немного затронули тему обобщений при обсуждении Option и Box. Однако, пока мы избегали объявления нового типа, который бы обобщал произвольные элементы.

На самом деле это очень просто. Давайте прямо сейчас сделаем наши типы обобщёнными:

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

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

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

Вы добавили несколько угловых скобок — и внезапно ваш код стал универсальным. Естественно, не всё так просто. Компилятор начал Очень Сильно Ругался.

> cargo test

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/second.rs:14:6
   |
14 | impl List {
   |      ^^^^ expected 1 type argument

error[E0107]: wrong number of type arguments: expected 1, found 0
  --> src/second.rs:36:15
   |
36 | impl Drop for List {
   |               ^^^^ expected 1 type argument

Проблема довольно прозрачна: мы везде пишем List, но это неправильно. Как и в случае с Option, и Box, теперь мы должны писать List<Something>, то есть «Список чего-то».

Но что такое это «что-то», которое мы используем во всех реализациях? Как и в случае с List, мы хотим, чтобы реализация работала со всеми T. Поэтому, как и в случае с List, давайте добавим угловые скобки к impl:

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

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
    }
}

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();
        }
    }
}

…и это всё!

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 2 tests
test first::test::basics ... ok
test second::test::basics ... ok

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

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

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

Купайтесь в лучах Славы, дарованной вам Self, хранителем рефакторинга и кодирования методом копи-пасты. Кстати, интересно, что мы не пишем List<T> при создании экземпляра списка. Тип выводится автоматически, на основании того факта, что мы возвращаем значение из функции, которая имеет тип List<T>.

Хорошо, теперь перейдём к реализации нового поведения!

Метод Peek

В прошлой версии списка мы не реализовали один полезный метод, а именно — заглядывание. Настало время реализации. Всё, что нам надо — вернуть ссылку на элемент в голове списка, если он существует. Звучит легко, попробуем сделать:

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

> cargo build

error[E0515]: cannot return reference to local data `node.elem`
  --> src/second.rs:37:13
   |
37 |             &node.elem
   |             ^^^^^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:36:9
   |
36 |         self.head.map(|node| {
   |         ^^^^^^^^^ cannot move out of borrowed content

Вздох. Что теперь, Rust?

Функция map получает self по значению, что удаляет Option из self.head. Раньше это было нормально, потому что мы забирали узел себе, но сейчас мы хотим оставить его на месте. Корректный способ обработать такую ситуацию — вызвать у Option метод as_ref. Он имеет определение:

impl<T> Option<T> {
    pub fn as_ref(&self) -> Option<&T>;
}

Метод сужает Option<T> до опциональной ссылки на внутреннее содержимое. То же самое можно сделать с помощью оператора match, но в этом нет смысла, поскольку в стандартной библиотеке есть готовый метод. Теоретически, нам надо выполнить дополнительное разыменование, чтобы убрать один уровень косвенности, но, к счастью оператор . делает это за нас.

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

cargo build

    Finished dev [unoptimized + debuginfo] target(s) in 0.32s

Справились.

Мы также можем сделать изменяемую версию этого метода, используя as_mut:

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

cargo build

Лег! Ко!

Не забудем протестировать:

#[test]
fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);
    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
}

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok

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

Всё это здорово, но мы так и не проверили, можно ли изменить значение, которое возвращает peek_mut, ведь так? Если ссылка изменяемая, но никто её не изменил, действительно ли мы протестировали изменяемость? Попробуем вызвать map на экземпляре Option<&mut T>, чтобы изменить содержимое:

#[test]
fn peek() {
    let mut list = List::new();
    assert_eq!(list.peek(), None);
    assert_eq!(list.peek_mut(), None);
    list.push(1); list.push(2); list.push(3);

    assert_eq!(list.peek(), Some(&3));
    assert_eq!(list.peek_mut(), Some(&mut 3));
    list.peek_mut().map(|&mut value| {
        value = 42
    });

    assert_eq!(list.peek(), Some(&42));
    assert_eq!(list.pop(), Some(42));
}

> cargo test

error[E0384]: cannot assign twice to immutable variable `value`
   --> src/second.rs:100:13
    |
99  |         list.peek_mut().map(|&mut value| {
    |                                   -----
    |                                   |
    |                                   first assignment to `value`
    |                                   help: make this binding mutable: `mut value`
100 |             value = 42
    |             ^^^^^^^^^^ cannot assign twice to immutable variable          ^~~~~

Компилятор жалуется, что переменная value неизменяемая, но мы довольно ясно написали &mut value. Так в чём же дело? Оказывается, эта запись не означает, что value является неизменяемой ссылкой. Она означает образец, который сопоставляется с аргументом замыкания; |&mut value| — это «аргумент является изменяемой ссылкой, но ты просто скопируй значение, на которое она ссылается, в переменную value, пожалуйста». А вот если мы напишем просто |value|, тип переменной value превратится в &mut i32 и мы действительно сможем изменить голову:

    #[test]
    fn peek() {
        let mut list = List::new();
        assert_eq!(list.peek(), None);
        assert_eq!(list.peek_mut(), None);
        list.push(1); list.push(2); list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        list.peek_mut().map(|value| {
            *value = 42
        });

        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
    }

cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 3 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::peek ... ok

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

Гораздо лучше!

IntoIter

Перебор коллекций в Rust выполняется с помощью типажа Iterator. Он ненамного сложнее, чем Drop:

pub trait Iterator {
    type Item;
    fn next(&mut self) -> Option<Self::Item>;
}

Новая штука здесь — это type Item. Она объявляет, что каждая реализация типажа Iterator имеет связанный с ней тип, называемый Iter. В это тот самый тип, который возвращает функция next.

Причина по которой интерфейс Iterator возвращает значения Option<Self::Item> в том, что он объединяет концепции has_next (есть ли следующий элемент?) и get_next (верни следующий элемент). Когда у вас есть следующее значение, вы возвращаете Some(value), а когда нет — None. Такой подход делает API более эргономичным и безопасным как для реализации, так и для использования, поскольку позволяет убрать проверки и логику между has_next и get_next. Прекрасно!

К сожалению, (пока) в Rust нет ничего похожего на оператор yield, так что нам предстоит самостоятельно реализовывать логику перебора. Есть три различных вида итераторов, которые должна постараться реализовать каждая коллекция:

IntoIter (итератор по значениям) — T
IterMut (итератор по изменяемым ссылкам) — &mut T
Iter (итератор по разделяемым ссылкам) — &T

На самом деле у нас уже есть всё, что нужно, чтобы реализовать IntoIter используя интерфейс List: нам всего лишь надо раз за разом вызывать pop. Поэтому мы просто реализуем IntoInter, как новый тип поверх List:

// Кортежи — альтернативная форма структур,
// полезная для тривиальных обёрток вокруг других типов.
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()
    }
}

Ну, а теперь напишем тест:

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

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

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 4 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok

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

Прекрасно!

Iter

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

Хорошо, давайте попробуем:

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

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

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

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

> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:72:18
   |
72 |     next: Option<&Node<T>>,
   |                  ^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:82:17
   |
82 |     type Item = &T;
   |                 ^ expected lifetime parameter

О, боже. Время жизни. Я слышал про эту штуку. Я слышал, что это кошмар.

Давайте попробуем что-то новое: видите ошибку error[E0106]? Это код ошибки компилятора. Мы можем попросить rustc объяснить её с помощью --explain:

> rustc --explain E0106
This error indicates that a lifetime is missing from a type. If it is an error
inside a function signature, the problem may be with failing to adhere to the
lifetime elision rules (see below).

Here are some simple examples of where you'll run into this error:

struct Foo { x: &bool }        // error
struct Foo<'a> { x: &'a bool } // correct

enum Bar { A(u8), B(&bool), }        // error
enum Bar<'a> { A(u8), B(&'a bool), } // correct

type MyStr = &str;        // error
type MyStr<'a> = &'a str; //correct
...

Так, хм… Это не очень прояснило ситуацию (дока думает, что мы разбираемся в Rust намного лучше, чем есть на самом деле). Но разве всё не звучит так, что мы должны добавить эти 'a к нашей структуре? Давайте попробуем.

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

> cargo build

error[E0106]: missing lifetime specifier
  --> src/second.rs:83:22
   |
83 | impl<T> Iterator for Iter<T> {
   |                      ^^^^^^^ expected lifetime parameter

error[E0106]: missing lifetime specifier
  --> src/second.rs:84:17
   |
84 |     type Item = &T;
   |                 ^ expected lifetime parameter

error: aborting due to 2 previous errors

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

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

impl<'a, T> List<T> {
    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &'a node) }
    }
}

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

> cargo build

error: expected `:`, found `node`
  --> src/second.rs:77:47
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ---- while parsing this struct        ^^^^ expected `:`

error: expected `:`, found `node`
  --> src/second.rs:85:50
   |
85 |             self.next = node.next.map(|node| &'a node);
   |                                                  ^^^^ expected `:`

error[E0063]: missing field `next` in initializer of `second::Iter<'_, _>`
  --> src/second.rs:77:9
   |
77 |         Iter { next: self.head.map(|node| &'a node) }
   |         ^^^^ missing `next`

Боже. Мы сломали Rust.

Может быть, нам всё-таки пора разобраться, что за хрень это самое время жизни 'a?

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

В языках программирования со сборкой мусора время жизни не требуется, поскольку сборщик мусора гарантирует, что все объекты волшебным образом проживут столько, сколько нужно. Большинство данных в Rust управляется вручную, так что для них нужно другое решение. C и C++ дают нам ясный пример, что происходит, если вы даёте людям возможность просто указывать на произвольные данные в стеке: повсеместная неуправляемая небезопасность. Возникающие ошибки можно условно разделить на два класса:

Хранить указатель на что-то, чего больше не существует
Хранить указатель на что-то, что было кем-то изменено

Время жизни решает обе эти проблемы и в 99% случаев делает это совершенно прозрачно.

Так что ж такое время жизни?

Говоря простыми словами, время жизни — это название участка кода (блока/области видимости) где-то в программе. Вот и всё. Когда ссылка помечена временем жизни, мы говорим, что она должна быть действительна на всём участке. То, как долго ссылка должна быть и может быть действительна, зависит от множества вещей. Вся система управления временем жизни представляет собой систему решения ограничений, которая пытается минимизировать участок, где каждая ссылка действительна. Если ей удаётся найти множество времён жизни, которые удовлетворяют всем ограничениям, ваша программа компилируется! В противном случае вы получаете ошибку, которая утверждает, что какая-то переменная живёт недостаточно долго.

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

В принципе, времена жизни можно было бы опустить, но тогда проверка заимствований привела бы к чудовищному анализу всей программы и сложным нелокальным ошибкам. (Речь о том, что ошибка в функции A приводила бы к ошибке в вызывающей её функции B и вам предстояла бы большая работа, чтобы найти истинную причину — прим. пер.) С другой стороны, если вы явно указываете время жизни, Rust может независимо проверить каждую функцию, и все ваши ошибки должны быть довольно локальными (или у ваших типов некорректные сигнатуры).

Впрочем, мы и раньше писали ссылки в сигнатурах функций, и всё было нормально! Оказывается, всё работало потому, что есть несколько распространенных случаев, когда Rust может вывести время жизни за нас. Речь идёт о неявном выведении времени жизни (lifetime elision).

В частности:

// Только одна ссылка на входе, так что выход можно вывести из входа
fn foo(&A) -> &B; // сахар для:
fn foo<'a>(&'a A) -> &'a B;

// Много ссылок на входе, предполагаем, что все они независимы
fn foo(&A, &B, &C); сахар для:
fn foo<'a, 'b, 'c>(&'a A, &'b B, &'c C);

// Методы, выводим все выходные времена жизни из `self`.
fn foo(&self, &B, &C) -> &D; // sugar for: сахар для:
fn foo<'a, 'b, 'c>(&'a self, &'b B, &'c C) -> &'a D;

Итак, что значит fn foo<'a>(&'a A) -> &'a B? Всего лишь то, что входная переменная должна жить по крайней мере столько же, сколько и выходная. Следовательно, если мы храним выходные переменные в течение длительного времени, участок, в котором должны быть действительны и входные переменные, становится больше. После того, как вы прекращаете использовать выходную переменную, компилятор понимает, что входная переменная тоже стала недействительной.

Благодаря этой системе правил Rust гарантирует, что переменную нельзя использовать после освобождения, и нельзя изменить, пока на неё есть внешние ссылки. По сути, Rust всего лишь проверяет, что наложенные ограничения не конфликтуют друг с другом!

Хорошо. Так. Iter.

Откатимся к коду без времени жизни:

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

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

impl<T> Iterator for Iter<T> {
    type Item = &T;
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

Мы должны добавить времена жизни только в сигнатуры функций и типов:

// Iter это обобщённый тип с каким-то временем, остальное ему не важно
pub struct Iter<'a, T> {
    next: Option<&'a Node<T>>,
}

// Никакого врмени жизни: у List нет никаких связанных времён жизни
impl<T> List<T> {
    // Здесь мы объявляем новое время жизни для заимствования, чтобы
    // создать итератор. Теперь &self должен оставаться действительным до тех
    // пор, пока существует Iter.
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &node) }
    }
}

// Здесь *нужно* время жизни, потому что оно есть у Iter
impl<'a, T> Iterator for Iter<'a, T> {
    // Здесь тоже нужно, поскольку это декларация типа
    type Item = &'a T;

    // Здесь ничего менять не нужно, всё будет работать, как и раньше
    // Self всё ещё невероятно чудесен и хайпов
    fn next(&mut self) -> Option<Self::Item> {
        self.next.map(|node| {
            self.next = node.next.map(|node| &node);
            &node.elem
        })
    }
}

Ладно, надеюсь, на этот раз у нас получилось.

cargo build

error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

(╯°□°)╯︵ ┻━┻

Так. Хорошо. Мы исправили ошибки с временем жизни, но у нас появился новый тип ошибок.

Нам нужны &Node, но у нас есть только &Box<Node>. Ладно, это достаточно просто, мы всего лишь должны разыменовать бокс, чтобы получить нашу ссылку:

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.map(|node| &*node) }
    }
}

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.map(|node| &*node);
            &node.elem
        })
    }
}

cargo build
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:77:43
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                                           ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.map(|node| &*node) }
   |                      ^^^^^^^^^ cannot move out of borrowed content

error[E0515]: cannot return reference to local data `*node`
  --> src/second.rs:85:46
   |
85 |             self.next = node.next.map(|node| &*node);
   |                                              ^^^^^^ returns a reference to data owned by the current function

error[E0507]: cannot move out of borrowed content
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.map(|node| &*node);
   |                         ^^^^^^^^^ cannot move out of borrowed content

(ﾉಥ益ಥ）ﾉ ┻━┻

Мы забыли вызвать as_ref, так что мы передаём бокс в map, что означает, что он будет удалён, что означает, что наши ссылки станут висячими (перестанут ссылаться на реальный объект).

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

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, T> {
        Iter { next: self.head.as_ref().map(|node| &*node) }
    }
}

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_ref().map(|node| &*node);
            &node.elem
        })
    }
}

cargo build
   Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0308]: mismatched types
  --> src/second.rs:77:22
   |
77 |         Iter { next: self.head.as_ref().map(|node| &*node) }
   |                      ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

error[E0308]: mismatched types
  --> src/second.rs:85:25
   |
85 |             self.next = node.next.as_ref().map(|node| &*node);
   |                         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `second::Node`, found struct `std::boxed::Box`
   |
   = note: expected type `std::option::Option<&'a second::Node<T>>`
              found type `std::option::Option<&std::boxed::Box<second::Node<T>>>`

😭

as_ref добавил ещё один уровень косвенности и его надо убрать:

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

impl<T> List<T> {
    pub fn iter<'a>(&'a self) -> Iter<'a, 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
        })
    }
}

cargo build

🎉 🎉 🎉

Функции as_deref и as_deref_mut стабильны, начиная с Rust 1.40. До этого вам надо было писать map(|node| &**node) и map(|node| &mut**node). Вам может показаться, что эта штука с &** на самом деле корявая, и в этом вы не ошибаетесь. Но, как хорошее вино, Rust со временем становится только лучше и нам больше не нужно так писать. Обычно Rust справляется с такими преобразованиями неявно, посредством процесса, называемого автоматическим разыменованием (deref coercion), во время которого он может вставлять * по всему коду, чтобы код прошёл проверку типов. Такой подход работает благодаря проверке заимствований, которая гарантирует, что мы никогда не сломаем указатели!

Но в нашем случае замыкание в сочетании с тем фактом, что нам нужен Option<&T> вместо &T, оказалось слишком сложным. В результате пришлось явно указывать время жизни. К счастью, по моему опыту, такое случается довольно редко.

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

    self.next = node.next.as_ref().map::<&Node<T>, _>(|node| &node);

Смотрите, map — это обобщённая функция:

pub fn map<U, F>(self, f: F) -> Option<U>

Турборыба ::<> позволяет нам сообщить компилятору, какими, как нам кажется, должны быть обобщённые типы. В данном случае ::<&Node<T>, _> говорит «функция должна вернуть &Node<T>, а второй тип меня не волнует».

Это, в свою очередь сообщает компилятору, что к &node следует применить автоматическое разыменование, так что нам не придётся писать все эти * вручную!

Но в данном случае я не думаю, что так следует писать. Это был всего лишь плохо завуалированный предлог, чтобы рассказать про автоматическое разыменование и оператор ::<>, весьма полезный время от времени. 😅

Давайте напишем тест, чтобы убедиться, что мы всё сделали правильно и не оставили без внимания ничего важного:

#[test]
fn iter() {
    let mut list = List::new();
    list.push(1); list.push(2); list.push(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 5 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::peek ... ok

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

Блин, да.

Наконец, следует заметить, что мы действительно можем полагаться на неявное выведение времени жизни:

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

эквивалентно:

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

Ура, меньше времён жизни!

Или, если вам некомфортно «скрывать», что у структуры есть время жизни, мы можете использовать синтаксис «явно пропущенного времени жизни» '_, который появился в Rust 2018.

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

IterMut

Я хочу быть честной: IterMut это БЕЗУМИЕ. Что само по себе звучит безумно: он ведь должен быть похож на Iter!

Семантически да, но природа разделяемых и изменяемых ссылок такова, что Iter можно считать «тривиальным», в то время как IterMut — это Настоящее Колдовство.

Возьмём ключевую идею из нашей реализации Iterator для Iter:

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

    fn next(&mut self) -> Option<Self::Item> { /* что-то */ }
}

Которую можно преобразовать в:

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

    fn next<'b>(&'b mut self) -> Option<&'a T> { /* что-то */ }
}

Сигнатура next не устанавливает ограничений между временем жизни входной и выходной переменных! Почему для нас это важно? Потому, что мы можем вызывать next снова и снова без всяких условий!

let mut list = List::new();
list.push(1); list.push(2); list.push(3);

let mut iter = list.iter();
let x = iter.next().unwrap();
let y = iter.next().unwrap();
let z = iter.next().unwrap();

Круто!

Это совершенно нормально для разделяемых ссылок, потому что их смысл в том, что их одновременно может быть очень много. А вот изменяемые ссылки сосуществовать не могут. Их смысл в том, что они эксклюзивные.

В результате, написать безопасный код для IterMut гораздо сложнее (и мы, кстати, пока не выяснили, что это значит…). Удивительно, но IterMut можно совершенно безопасно реализовать для многих структур данных!

Начнём с того, что просто возьмём код Iter и перепишем всё так, чтобы ссылки стали изменяемыми:

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

impl<T> List<T> {
    pub fn iter_mut(&self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_deref_mut() }
    }
}

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

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

> cargo build
error[E0596]: cannot borrow `self.head` as mutable, as it is behind a `&` reference
  --> src/second.rs:95:25
   |
94 |     pub fn iter_mut(&self) -> IterMut<'_, T> {
   |                     ----- help: consider changing this to be a mutable reference: `&mut self`
95 |         IterMut { next: self.head.as_deref_mut() }
   |                         ^^^^^^^^^ `self` is a `&` reference, so the data it refers to cannot be borrowed as mutable

error[E0507]: cannot move out of borrowed content
   --> src/second.rs:103:9
    |
103 |         self.next.map(|node| {
    |         ^^^^^^^^^ cannot move out of borrowed content

Хорошо, выглядит так, словно у нас тут две разные ошибки. Первая очень понятная и в сообщении даже написано, как её исправить! Нельзя преобразовать разделяемую ссылку в изменяемую, так что iter_mut должен принимать &mut self. Обычная глупая ошибка копи-пасты.

pub fn iter_mut(&mut self) -> IterMut<'_, T> {
    IterMut { next: self.head.as_deref_mut() }
}

А что насчёт второй?

Ой! На самом дела я случайно ошиблась при написании iter в прошлом разделе, и нам просто повезло, что всё заработало!

Мы только что столкнулись с типажом Copy. Когда мы вводили понятие владения, то сказали, что передав владение, вы больше не можете использовать переменную. Для многих типов это правда. Наш добрый друг Box управляет размещением памяти в куче и мы конечно же не хотим, чтобы два куска кода думали, что они должны освободить эту память.

В то же время для других типов всё это мусор. Целые числа не обладают семантикой владения, они всего лишь бессмысленные числа! Именно по этой причине, целые числа реализуют типаж Copy. Известно, что типы, помеченные как Copy, идеально копируется побитовым копированием. Поэтому они обладают сверхспособностью: при перемещении старое значение всё ещё можно использовать. Как следствие, вы можете даже забрать копируемый тип из ссылки без замены!

Копируемыми являются все численные примитивы Rust (i32, u64, bool, f32, char и т. д.). Вы также можете объявить свой тип копируемым, если все его компоненты — также копируемые.

Ключевым моментом, объясняющим, почему этот код работал, является то, что разделяемые ссылки также копируемые! А, поскольку & можно копировать, Option<&> также можно копировать. Так что когда мы вызывали self.next.map, это работало потому что что Option просто копировался. Но теперь мы не можем так сделать, потому что &mut не копируется (если вы скопируете &mut, у вас будет две изменяемые ссылки на одно и то же место в памяти, что запрещено). Вместо копирования, мы должны забрать владение, вызвав метод take.

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

cargo build

Так… подождите. Охренеть! IterMut просто работает!

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

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

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

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 6 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter_mut ... ok
test second::test::into_iter ... ok
test second::test::iter ... ok
test second::test::peek ... ok

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

Да. Он работает.

Охренеть.

Хотя.

Конечно, IterMut должен работать, но обычно этому мешает какая-нибудь глупость! Проясню:

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

Как по мне, это большое достижение. Есть пара причин, поэтому всё работает.

Мы вызываем take у Option<&mut>, так что получаем эксклюзивный доступ к изменяемой ссылке. Не надо беспокоиться, что кто-то ещё сможет получить к ней доступ.
Rust понимает, что это нормально — разбить изменяемую ссылку на отдельные поля указываемой структуры, потому что нет способа «собрать её обратно» и поля определённо не пересекаются.

Та же самая базовая логика применима при реализации безопасного IterMut для массива или дерева! Можно даже сделать итератор DoubleEnded, чтобы перебирать элементы одновременно от начала к концу, и от конца к началу! Вот как!

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

Итак, мы дописали второй список и вот финальный код!

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

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

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

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

    pub fn push(&mut self, elem: T) {
        let new_node = Box::new(Node {
            elem: elem,
            next: self.head.take(),
        });

        self.head = Some(new_node);
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next;
            node.elem
        })
    }

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

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

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

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

    pub fn iter_mut(&mut self) -> IterMut<'_, T> {
        IterMut { next: self.head.as_deref_mut() }
    }
}

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();
        }
    }
}

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

impl<T> Iterator for IntoIter<T> {
    type Item = T;
    fn next(&mut self) -> Option<Self::Item> {
        // получаем доступ к полям кортежа по номеру
        self.0.pop()
    }
}

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
        })
    }
}

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

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

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

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

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

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

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

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

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

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

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

    #[test]
    fn peek() {
        let mut list = List::new();
        assert_eq!(list.peek(), None);
        assert_eq!(list.peek_mut(), None);
        list.push(1); list.push(2); list.push(3);

        assert_eq!(list.peek(), Some(&3));
        assert_eq!(list.peek_mut(), Some(&mut 3));

        list.peek_mut().map(|value| {
            *value = 42
        });

        assert_eq!(list.peek(), Some(&42));
        assert_eq!(list.pop(), Some(42));
    }

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

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

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

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

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

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

Обрастаем функционалом!

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

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