Оглавление

Ладно. Вот и всё. Мы написали все списки.

ахахахаха

Нет

Всегда есть ещё немного списков.

Эта глава — живой документ про самые нелепые связные списки и про их реализацию в Rust.

Двойной односвязный
Список размещённый на стеке
Само-ссылающийся список-арена?
Список GhostCell?

Двойной односвязный список

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

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

// lib.rs
// ...
pub mod silly1;     // НОВЫЙ!

// silly1.rs
use crate::second::List as Stack;

struct List<T> {
    left: Stack<T>,
    right: Stack<T>,
}

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

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

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

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

impl<T> Stack<T> {
    pub fn new() -> Self {
        Stack { 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| {
            let node = *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
        })
    }
}

impl<T> Drop for Stack<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();
        }
    }
}

И немного переработаем push и pop:

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

    self.push_node(new_node);
}

fn push_node(&mut self, mut node: Box<Node<T>>) {
    node.next = self.head.take();
    self.head = Some(node);
}

pub fn pop(&mut self) -> Option<T> {
    self.pop_node().map(|node| {
        node.elem
    })
}

fn pop_node(&mut self) -> Option<Box<Node<T>>> {
    self.head.take().map(|mut node| {
        self.head = node.next.take();
        node
    })
}

Теперь мы можем написать наш список:

pub struct List<T> {
    left: Stack<T>,
    right: Stack<T>,
}

impl<T> List<T> {
    fn new() -> Self {
        List { left: Stack::new(), right: Stack::new() }
    }
}

И выполнять над ним обычные операции:

pub fn push_left(&mut self, elem: T) { self.left.push(elem) }
pub fn push_right(&mut self, elem: T) { self.right.push(elem) }
pub fn pop_left(&mut self) -> Option<T> { self.left.pop() }
pub fn pop_right(&mut self) -> Option<T> { self.right.pop() }
pub fn peek_left(&self) -> Option<&T> { self.left.peek() }
pub fn peek_right(&self) -> Option<&T> { self.right.peek() }
pub fn peek_left_mut(&mut self) -> Option<&mut T> { self.left.peek_mut() }
pub fn peek_right_mut(&mut self) -> Option<&mut T> { self.right.peek_mut() }

Но, что гораздо интереснее, мы можем его прокручивать!

pub fn go_left(&mut self) -> bool {
    self.left.pop_node().map(|node| {
        self.right.push_node(node);
    }).is_some()
}

pub fn go_right(&mut self) -> bool {
    self.right.pop_node().map(|node| {
        self.left.push_node(node);
    }).is_some()
}

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

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

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

        list.push_left(0);                      // [0,_]
        list.push_right(1);                     // [0, _, 1]
        assert_eq!(list.peek_left(), Some(&0));
        assert_eq!(list.peek_right(), Some(&1));

        list.push_left(2);                      // [0, 2, _, 1]
        list.push_left(3);                      // [0, 2, 3, _, 1]
        list.push_right(4);                     // [0, 2, 3, _, 4, 1]

        while list.go_left() {}                 // [_, 0, 2, 3, 4, 1]

        assert_eq!(list.pop_left(), None);
        assert_eq!(list.pop_right(), Some(0));  // [_, 2, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(2));  // [_, 3, 4, 1]

        list.push_left(5);                      // [5, _, 3, 4, 1]
        assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
        assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]
        assert_eq!(list.pop_right(), Some(4));  // [_, 1]
        assert_eq!(list.pop_right(), Some(1));  // [_]

        assert_eq!(list.pop_right(), None);
        assert_eq!(list.pop_left(), None);
    }
}

> cargo test

     Running target/debug/lists-5c71138492ad4b4a

running 16 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fourth::test::into_iter ... ok
test fourth::test::basics ... ok
test fourth::test::peek ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::iter_mut ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok

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

Перед нами — экстремальный пример структуры данных с указателем (finger data structure). Благодаря своеобразному указателю, структура позволяет выполнять операции над элементами за время, пропорциональное расстоянию до него.

Можно быстро вносить изменения рядом с указателем, но если нам надо поправить список где-то далеко, туда придётся добраться. Можно либо идти по списку, перекладывая элементы из одного стека в другой, либо двигаться с помощью временного изменяемого итератора &mut. Но помните, итератор не позволит нам вернуться назад, в то время как указатель позволит!

Связный список, размещённый на стеке

Эта книга посвящена связным спискам, размещаемым в куче, поскольку они и распространены, и практичны. Но не обязательно выделять память в куче, хотя это удобно, поскольку позволяет выделять память динамически. В этом смысле выделение памяти в стеке менее дружелюбно: такие вещи, как alloca из C достаточно Ужасны и Проблемны.

Будем выделять память в стеке простым способом: вызвав функцию и получая новый фрейм стека для нового узла! Это очень простое решение нашей проблемы, в то же время практичное и полезное. Многие так делают, даже не подозревая, что реализуют связный список!

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

Теперь, когда мы перешли к нелепой части книги, мы будем программировать нелепым способом: связный список будет главной звездой а весь пользовательский код окажется среди функций обратного вызова (callback)! Все любят вложенные функции обратного вызова!

Наш тип списка будет обычным узлом со ссылкой на другой узел.

pub struct List<'a, T> {
    pub data: T,
    pub prev: Option<&'a List<'a, T>>,
}

И у нас будет всего одна операция, push, принимающая в параметрах старый список, состояние текущего узла и функцию обратного вызова. Новый список будет передан в функцию обратного вызова. Функция обратного вызова может вернуть любое значение, которое затем вернёт и метод push:

impl<'a, T> List<'a, T> {
    pub fn push<U>(
        prev: Option<&'a List<'a, T>>, 
        data: T, 
        callback: impl FnOnce(&List<'a, T>) -> U,
    ) -> U {
        let list = List { data, prev };
        callback(&list)
    }
}

Вот и всё! Использовать этот код можно так:

List::push(None, 3, |list| {
    println!("{}", list.data);
    List::push(Some(list), 5, |list| {
        println!("{}", list.data);
        List::push(Some(list), 13, |list| {
            println!("{}", list.data);
        })
    })
})

Красиво. 😿

Пользователь может перемещаться по списку, используя конструкцию while-let и извлекая значения prev, но, веселья ради, давайте реализуем наш обычный итератор:

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

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.prev;
            &node.data
        })
    }
}

Протестируем:

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

    #[test]
    fn elegance() {
        List::push(None, 3, |list| {
            assert_eq!(list.iter().copied().sum::<i32>(), 3);
            List::push(Some(list), 5, |list| {
                assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
                List::push(Some(list), 13, |list| {
                    assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
                })
            })
        })
    }
}

> cargo test

running 18 tests
test fifth::test::into_iter ... ok
test fifth::test::iter ... ok
test fifth::test::iter_mut ... ok
test fifth::test::basics ... ok
test fifth::test::miri_food ... ok
test first::test::basics ... ok
test second::test::into_iter ... ok
test fourth::test::peek ... ok
test fourth::test::into_iter ... ok
test second::test::iter_mut ... ok
test fourth::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test second::test::peek ... ok
test third::test::iter ... ok

test result: ok. 18 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;

Сейчас, вероятно, вы задаётесь вопросом, можно ли менять данные внутри узла? Давайте проверим. Будем хранить в списке изменяемые ссылки вместо разделяемых:

pub struct List<'a, T> {
    pub data: T,
    pub prev: Option<&'a mut List<'a, T>>,
}

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

impl<'a, T> List<'a, T> {
    pub fn push<U>(
        prev: Option<&'a mut List<'a, T>>, 
        data: T, 
        callback: impl FnOnce(&mut List<'a, T>) -> U,
    ) -> U {
        let mut list = List { data, prev };
        callback(&mut list)
    }

    pub fn iter(&'a self) -> Iter<'a, T> {
        Iter { next: Some(self) }
    }
}

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

> cargo test

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:47:32
   |
46 |  List::push(Some(list), 13, |list| {
   |                              ----
   |                              |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
47 |      assert_eq!(list.iter().copied().sum::<i32>(), 13 + 5 + 3);
   |                 ^^^^^^^^^^^ `list` escapes the closure body here

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:45:28
   |
44 |  List::push(Some(list), 5, |list| {
   |                             ----
   |                             |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
45 |      assert_eq!(list.iter().copied().sum::<i32>(), 5 + 3);
   |                 ^^^^^^^^^^^ `list` escapes the closure body here


<до бесконечности>

Что ж. Кажется, компилятору не понравился наш итератор. Возможно, мы что-то упустили? Попробуем упростить наш тест:

#[test]
fn elegance() {
    List::push(None, 3, |list| {
        assert_eq!(list.data, 3);
        List::push(Some(list), 5, |list| {
            assert_eq!(list.data, 5);
            List::push(Some(list), 13, |list| {
                assert_eq!(list.data, 13);
            })
        })
    })
}

> cargo test

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:46:17
   |
44 |   List::push(Some(list), 5, |list| {
   |                              ----
   |                              |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
45 |       assert_eq!(list.data, 5);
46 | /     List::push(Some(list), 13, |list| {
47 | |         assert_eq!(list.data, 13);
48 | |     })
   | |______^ `list` escapes the closure body here

error[E0521]: borrowed data escapes outside of closure
  --> src\silly2.rs:44:13
   |
42 |   List::push(None, 3, |list| {
   |                        ----
   |                        |
   |              `list` declared here, outside of the closure body
   |              `list` is a reference that is only valid in the closure body
43 |       assert_eq!(list.data, 3);
44 | /     List::push(Some(list), 5, |list| {
45 | |         assert_eq!(list.data, 5);
46 | |         List::push(Some(list), 13, |list| {
47 | |             assert_eq!(list.data, 13);
48 | |         })
49 | |     })
   | |______________^ `list` escapes the closure body here

Хмм, нет, это всё ещё ерунда.

Проблема в том, что наш список случайно (😉) полагается на вариантность. Вариантность — сложная тема, но давайте рассмотрим её в упрощённом виде:

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

Так… почему всё компилировалось, когда мы использовали разделяемые ссылки? Потому что в большинстве случаев компилятор знает, что «долгожители» безопасны! Когда мы помещаем ссылку на список в следующий список, компилятор втихую «урезает» время жизни, чтобы оно совпадало с ожиданиями нового списка. Это урезание времени жизни и создаёт вариантность.

Тот же самый трюк, как в языках с наследованием, где вы можете передать Cat туда, где ожидается Animal (базовый тип Cat). Интуитивно мы понимаем, что передавать Cat, когда ожидается Animal — это нормально, потому что Animal включает Cat и что-то ещё. Нормально временно забыть про что-то ещё, так ведь?

Точно также, меньшее время жизни включает большее время жизни и что-то ещё. Нормально и здесь забыть про что-то ещё!

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

Ну, потому что вариантность не всегда безопасна. Если бы наш код компилировался, мы могли бы реализовать использование-после-освобождения (use-after-free), например, вот так:

List::push(None, 3, |list| {
    List::push(Some(list), 5, |list| {
        List::push(Some(list), 13, |list| {
            // ХАХАХА все временя жизни одинаковы, так что компилятор
            // позволит мне поменять моего родителя, чтобы оставить
            // мутабельную ссылку на меня!
            // Я создам объект, который можно использовать-после-освобождения!!!
            *list.prev.as_mut().unwrap().prev = Some(list);
        })
    })
})

Главная беда забытых мелочей в том, что где-то помнят про них и рассчитывают на них. Изменяемые данные остаются очень большой проблемой. Если вы не проявите осторожность, код, который не помнит про что-то ещё, может заменить что-то ещё и сломать те части программы, которые «помнят» и ожидают, что что-то ещё будет на месте.

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

let mut my_kitty = Cat;                  // Создаём Кота (длинное время жизни)
let animal: &mut Animal = &mut my_kitty; // Забываем, что это Кот (кратчайшее время жизни)
*animal = Dog;                           // Меняем на Собаку (короткое время жизни)
my_kitty.meow();                         // Мяукающая Собака! (использование-после-освобождения)

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

В частности, &mut &'big mut T нельзя преобразовывать в &mut &'small mut T, где 'big живёт дольше, чем 'small. Или, более формально &'a mut T ковариантен относительно 'a, но инвариантен относительно T.

Занимательный факт: Java в принципе позволяет проворачивать такие трюки, но в ней есть проверка времени выполнения, которая предотвращает мяуканье собак.

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

Вернём предыдущую версию нашего кода с разделяемыми ссылками и используем Cell в новом тесте:

#[test]
fn cell() {
    use std::cell::Cell;

    List::push(None, Cell::new(3), |list| {
        List::push(Some(list), Cell::new(5), |list| {
            List::push(Some(list), Cell::new(13), |list| {
                // Умножаем каждое значение в списке на 10
                for val in list.iter() {
                    val.set(val.get() * 10)
                }

                let mut vals = list.iter();
                assert_eq!(vals.next().unwrap().get(), 130);
                assert_eq!(vals.next().unwrap().get(), 50);
                assert_eq!(vals.next().unwrap().get(), 30);
                assert_eq!(vals.next(), None);
                assert_eq!(vals.next(), None);
            })
        })
    })
}

> cargo test

running 19 tests
test fifth::test::into_iter ... ok
test fifth::test::basics ... ok
test fifth::test::iter_mut ... ok
test fifth::test::iter ... ok
test fourth::test::basics ... ok
test fourth::test::into_iter ... ok
test second::test::into_iter ... ok
test first::test::basics ... ok
test fourth::test::peek ... ok
test second::test::basics ... ok
test fifth::test::miri_food ... ok
test silly2::test::cell ... ok
test third::test::iter ... ok
test second::test::iter_mut ... ok
test second::test::peek ... ok
test silly1::test::walk_aboot ... ok
test silly2::test::elegance ... ok
test third::test::basics ... ok
test second::test::iter ... ok

test result: ok. 19 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out;

Проще рекурсивной репы! ✨

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

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