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

Прошлый урок выдал ящик с инструментами: Box для единственного хозяина, Rc и Weak для разделённого, Cell и RefCell для изменения через общую ссылку. Сегодня берём одну простую структуру, связный список, и строим её тремя способами подряд. На каждом из них меняется набор инструментов, цена и то, о чём именно с тобой спорит borrow checker. Знаменитый учебник «слишком много списков» придумал этот трюк: список так плохо ложится на модель владения, что становится идеальным тренажёром.

Почему именно список

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

Первая точка это владение. Кто хозяин узла, на который показывает next? Если предыдущий узел, то при удалении он унесёт за собой весь хвост, и это надо как-то выразить в типах. Вторая точка это заём: чтобы вставить или удалить элемент в середине, нужно подержать изменяющую ссылку на узел и одновременно перецепить соседей, а borrow checker запрещает две &mut на пересекающиеся данные. Третья точка это разделение: если два списка хотят разделить общий хвост, узлом владеет уже не один хозяин, и нужен подсчёт ссылок.

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

Сразу честная оговорка, та же, что делает сам учебник. В реальном коде связный список почти всегда проигрывает массиву. Vec и VecDeque из урока про коллекции кладут элементы подряд, процессор любит такую раскладку и читает её из кэша пачками, а список раскидан по куче, и каждый переход по next это промах мимо кэша. Так что списки мы пишем не ради списков, а ради того, чтобы прочувствовать на руках, где какой умный указатель уместен и почему компилятор разрешает одно и запрещает другое.

Способ первый: безопасный стек на Box

Начнём с самого скромного списка, который вообще ничего не делит. Это стек: добавляем и снимаем только с одного конца, с головы. Один владелец на всю цепочку, поэтому хватит Box.

Наивная первая попытка

Кажется, что список это просто перечисление: либо пусто, либо значение и хвост.

pub enum List {
    Empty,
    Elem(i32, Box<List>),
}

Скомпилируется, но раскладка кривая. Возьми список из двух элементов: Elem(1, Box(Elem(2, Box(Empty)))). Первый Elem лежит прямо на стеке, не в куче. Последний узел это Box вокруг Empty, то есть отдельная аллокация в куче ради значения, которое не несёт никаких данных. Узлы неоднородны: один на стеке, другой впустую занял кучу. Неудобно.

Лекарство простое: разнести голову списка и узел. Список это структура с одним полем head, а пустоту выражает Option, который ничего не аллоцирует.

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

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

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

Теперь None это компактный признак конца без всякой кучи (компилятор даже укладывает Option<Box<_>> в одно слово через niche-оптимизацию), а каждый Node лежит в куче и однороден с остальными. Link это просто псевдоним, чтобы тип читался.

push и pop через take

Главная трудность с push не в аллокации, а в заёме. Чтобы добавить новую голову, надо забрать старую и подвесить её новому узлу в next. Но self.head мы держим только по &mut self, и просто прочитать значение из него нельзя: это был бы move из заимствованного поля, оставивший там дыру. Компилятор такого не разрешит.

Выход это Option::take: он забирает значение из Option во владение, а на его место кладёт None. Дыры не остаётся ни на миг, заём цел.

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,
            next: self.head.take(), // забрали старую голову, на её место легло None
        });
        self.head = Some(new_node); // теперь голова это новый узел
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|node| {
            self.head = node.next; // голова перескочила на следующий узел
            node.elem // старый Box тут же освободился, значение уехало наружу
        })
    }
}

take это вежливая обёртка над std::mem::replace(&mut self.head, None): тот же приём, поменять значение в заимствованном месте на заглушку и забрать старое во владение. Запомни его, в Rust он встречается постоянно.

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

Заглянуть, не снимая: peek

pop забирает значение во владение. Часто хочется просто посмотреть на верхушку, не разбирая стек. Тут нужна ссылка внутрь Option, и её даёт as_ref (а изменяющую as_mut).

impl<T> List<T> {
    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)
    }
}

as_ref превращает &Option<Box<Node>> в Option<&Box<Node>>, дальше map достаёт ссылку на сам elem. Через peek_mut верхушку можно поменять на месте: if let Some(top) = list.peek_mut() { *top += 10; }.

Три итератора

Хороший контейнер умеет отдавать свои элементы итератором. Их традиционно три, по виду доступа: по значению, по ссылке и по изменяющей ссылке (трейт Iterator подробно разбирал урок про итераторы).

IntoIter забирает список во владение и просто зовёт 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<T> {
        self.0.pop()
    }
}

Iter идёт по ссылкам и хранит ссылку на следующий узел. as_deref снимает Box и даёт сразу Option<&Node>:

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

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

impl<'a, T> Iterator for Iter<'a, T> {
    type Item = &'a T;
    fn next(&mut self) -> Option<&'a T> {
        self.next.map(|node| {
            self.next = node.next.as_deref(); // шагнули на следующий узел
            &node.elem
        })
    }
}

IterMut самый коварный. Он выдаёт &mut T, а изменяющая ссылка не Copy: её нельзя просто прочитать из self.next, оставив копию на месте. Поэтому здесь снова take, который забирает ссылку во владение и кладёт None.

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

impl<T> List<T> {
    pub fn iter_mut(&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<&'a mut T> {
        self.next.take().map(|node| {
            self.next = node.next.as_deref_mut();
            &mut node.elem
        })
    }
}

Если бы вместо take мы написали self.next.map(...), компилятор отказал бы: нельзя скопировать &mut, ведь тогда на один узел появилось бы две изменяющих ссылки сразу. take решает это честно: старую ссылку забрали целиком, и она ушла наружу единственной. Borrow checker доволен, и это тот случай, когда его придирка прямо указывает на настоящую опасность.

Свой Drop: почему рекурсия переполнит стек

Остался неприятный сюрприз, спрятанный в автоматическом Drop. Когда длинный список выходит из области, компилятор роняет голову, а чтобы уронить её, надо сначала уронить поле next, то есть следующий узел, а для него следующий. Это рекурсия по стеку вызовов, и её глубина равна длине списка. На списке в миллион узлов программа просто переполнит стек и упадёт.

Лечится ручным Drop, который снимает узлы в обычном цикле, без рекурсии:

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut cur = self.head.take();
        while let Some(mut node) = cur {
            cur = node.next.take(); // вынули хвост, текущий узел тут же освободился
        }
    }
}

На каждом витке take вынимает next, прежний Box остаётся без ссылок и освобождается на месте. Глубина стека вызовов постоянна на любой длине списка. Это редкий, но важный случай, когда стандартный Drop не годится и его пишут руками. Открой во виджете вкладку «почему свой Drop», там видно разницу между рекурсией и циклом.

Способ второй: разделяемый список на Rc

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

Идея такая. Есть список [1, 2, 3]. Я хочу второй список [2, 3] (без головы) и третий [4, 1, 2, 3] (с новой головой), но не копируя общие узлы. Все три должны смотреть в одну и ту же цепочку в куче. Раз на узел 2 теперь ссылаются и первый список, и второй, владелец у него не один. Значит, Box не подходит, нужен Rc с его подсчётом ссылок.

use std::rc::Rc;

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

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

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

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

    pub fn prepend(&self, elem: T) -> List<T> {
        List {
            head: Some(Rc::new(Node {
                elem,
                next: self.head.clone(), // клон Rc это +1 к счётчику, не копия узла
            })),
        }
    }

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

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

Заметь главное отличие от стека: prepend и tail берут &self, а не &mut self, и возвращают новый список, ничего не меняя в старом. Старая версия остаётся жить нетронутой, это и есть персистентность. А self.head.clone() копирует не Node, а только Rc: данные остаются на месте, растёт лишь счётчик владельцев.

Прокрути сценарий по шагам. Следи за полем strong у каждого узла: подсвеченный узел это тот, на который смотрят сразу несколько списков.

Виджет показывает суть: списки a, b и c физически делят одни и те же узлы в куче, а счётчик strong точно знает, сколько версий держат каждый узел. Когда уходит a, освобождается только то, на что больше никто не смотрит. Память отдаётся узел за узлом, ровно по последнему владельцу.

Почему здесь только чтение

За удобство разделения Rc берёт цену: он даёт только чтение. Rc<T> разыменовывается в &T, не в &mut T, ведь владельцев много, и выдать одному изменяющую ссылку значило бы дать ему испортить данные под носом у остальных. Поэтому у персистентного списка нет ни push, ни pop, ни iter_mut: менять разделённый узел на месте нельзя вообще. Можно только построить новую версию поверх старой.

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

impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();
        while let Some(node) = head {
            // вынимаем хвост, только если это последний владелец узла
            match Rc::try_unwrap(node) {
                Ok(mut node) => head = node.next.take(),
                Err(_) => break, // на узел смотрит кто-то ещё, дальше не наша забота
            }
        }
    }
}

Когда разделённое нужно ещё и менять: Rc и RefCell

Персистентный список только читают. А если хочется именно двусвязный список, где у узла есть и next, и prev, и его можно править с обоих концов? Тут владельцев у узла снова несколько (слева сосед, справа сосед), значит Rc, но менять-то надо, значит внутрь ещё и RefCell. Получается та самая рабочая лошадка из прошлого урока, Rc<RefCell<Node>>.

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

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

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

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

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

pub fn push_front(&mut self, elem: T) {
    let new_head = Rc::new(RefCell::new(Node { elem, next: None, prev: None }));
    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);
        }
    }
}

И вот где цена бьёт по рукам сильнее всего. Заглянуть в голову, вернув простой &T, уже не выйдет: данные спрятаны за RefCell, и наружу отдаётся Ref<T>, страж заёма из прошлого урока.

use std::cell::Ref;

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

Сложи всё вместе: каждое поле через borrow, наружу торчат Ref вместо ссылок, при ошибке заёма прилетит паника в рантайме вместо ошибки компиляции, и при всём этом список по-прежнему живёт в одном потоке. Borrow checker мы не обманули, мы лишь переселили его в рантайм и платим за это на каждом шаге. Для двусвязного списка это перебор, и тут руки тянутся к третьему способу.

Способ третий: unsafe на сырых указателях

Посмотрим на задачу, где даже Rc<RefCell> неудобен, а безопасный Rust прямо не справляется. Это очередь: кладём в хвост, снимаем с головы. Чтобы класть в хвост за константу, нужен указатель на последний узел. Но цепочкой уже владеет голова через next, и держать вдобавок безопасную &mut на её конец нельзя: это две изменяющих ссылки на пересекающиеся данные, ровно то, что правило заёма запрещает.

Выход это сырой указатель *mut Node. Он не владеет узлом и не считается borrow checker, поэтому может спокойно лежать рядом с владеющей цепочкой. Цена: разыменовать его разрешено только внутри unsafe, и за то, что он валиден, отвечаешь ты, а не компилятор.

use std::ptr;

pub struct List<T> {
    head: Link<T>,
    tail: *mut Node<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, tail: ptr::null_mut() } // пустой хвост это нулевой указатель
    }

    pub fn push(&mut self, elem: T) {
        let mut new_tail = Box::new(Node { elem, next: None });
        let raw_tail: *mut _ = &mut *new_tail; // адрес нового узла как сырой указатель

        if !self.tail.is_null() {
            // очередь не пуста: дотянулись до старого хвоста и подцепили новый узел
            unsafe { (*self.tail).next = Some(new_tail); }
        } else {
            // очередь была пуста: новый узел это и голова тоже
            self.head = Some(new_tail);
        }
        self.tail = raw_tail; // хвост теперь показывает на свежий узел
    }

    pub fn pop(&mut self) -> Option<T> {
        self.head.take().map(|head| {
            let head = *head;
            self.head = head.next;
            if self.head.is_none() {
                self.tail = ptr::null_mut(); // очередь опустела: хвост обязан стать нулевым
            }
            head.elem
        })
    }
}

В безопасном коде инвариант «у данных либо много читателей, либо один писатель» держал компилятор. Здесь инвариант держишь ты, и формулируется он так: tail указывает на валидный узел ровно тогда, когда очередь не пуста, и равен null, когда пуста. Вся корректность висит на единственной строчке self.tail = ptr::null_mut() внутри pop. Забудешь её, и tail останется смотреть на освобождённую память, а следующий push запишет в неё.

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

Контракт и miri

Самое коварное в unsafe это что баг с висячим tail часто не падает сразу. Освобождённую память не успели переиспользовать, запись прошла «куда-то», и тесты даже зеленеют. Такая ошибка всплывёт через неделю в продакшене, в другом месте, без всякой связи с причиной.

Поэтому весь unsafe-код прогоняют через miri. Он исполняет код на интерпретаторе, следит за каждым указателем по модели алиасинга и ловит обращение к освобождённому адресу ровно в тот момент, когда оно происходит, а не когда-нибудь потом. Команда cargo +nightly miri test для unsafe-структуры так же обязательна, как обычные тесты.

Правило, которое стоит унести: безопасную обёртку вокруг unsafe пишут так, чтобы снаружи нарушить инвариант было нельзя. Поля head и tail приватны, трогать их можно только через push и pop, а уж они держат инвариант сами. Пользователь очереди не пишет ни строчки unsafe и не может уронить её в UB. Это и есть контракт безопасной абстракции, и ему целиком посвящён отдельный урок про Unsafe Rust.

Цена: три способа рядом

Один список, три набора инструментов. Сведём их в таблицу, чтобы выбор был наглядным.

Лесенка та же, что и в прошлом уроке: бери самый слабый инструмент, которого хватает. Доступ с одного конца это Box. Нужно разделить неизменяемый хвост между версиями, поднимайся на Rc. Понадобились связи в обе стороны без спуска в unsafe, плати за Rc<RefCell>. И только когда замерил, что эта цена реально мешает, и готов держать инвариант руками и гонять miri, спускайся к сырым указателям.

А самый частый правильный ответ для рабочего кода стоит за пределами всех трёх: Vec или VecDeque. Они кладут элементы подряд, дружат с кэшем и почти всегда обгоняют любой связный список. Три способа выше это не рецепт «как написать список в проекте», а тренажёр, на котором видно, как каждый умный указатель отвечает на свой вопрос владения.

Практика

Собери безопасный стек на Box своими руками: push, pop, peek, peek_mut и итератор по значению. Это первый способ из урока, та самая пара Option<Box<Node>> плюс take. В тестах есть и длинный список на миллион узлов: пройти его получится только со своим нерекурсивным Drop.

ДЗ

Дальше

Три способа построить один список показали главное: borrow checker это не препятствие, а собеседник, который на каждом варианте задаёт ровно один вопрос про владение. Box отвечает «хозяин один», Rc отвечает «хозяев много, но менять нельзя», unsafe отвечает «инвариант держу я сам». В следующем уроке мы перестанем смотреть на borrow checker через структуры данных и разберём его напрямую: времена жизни как граф ограничений, подтипизация, elision и ловушки с возвратом ссылок. Список был наглядным поводом подружиться с ним, дальше идёт сама теория.