Целая прорва связных списков, чтобы выучить Rust
Возникли какие-то сложности или хотите сразу получить весь финальный код? Всё на Github!
ПРИМЕЧАНИЕ: Текущая редакция этой книги написана для Rust 2018, выпущенного совместно с rustc 1.31 (8 декабря 2018). Если у вас достаточно новый инструментарий Rust, файл Carto.toml, созданный при запуске
cargo new, будет содержать строкуedition = "2018"(или, если вы из далёкого будущего, большее число!). Можно использовать старый инструментарий, но тогда вы разблокируете секретный режим повышенной сложности: больше ошибок от компилятора, совершенно не упомянутых в этой книге. Как по мне, звучит весело!
Меня довольно часто спрашивают, как реализовать в Rust односвязный список. Ответ определённо зависит от требований и, очевидно, ответить на этот вопрос не так просто. Поэтому я решила написать эту книгу, чтобы рассказать обо всём раз и навсегда.
В этом цикле я научу вас и базовому, и продвинутому программированию на Rust, с помощью реализации 6 связных списков. За время изучения вы освоите:
- Следующие типы указателей:
&,&mut,Box,Rc,Arc,*const,*mut,NonNull(?) - Владение, заимствование, наследуемую изменчивость, внутреннюю изменчивость, типаж Copy
- Все ключевые слова: struct, enum, fn, pub, impl, use, ...
- Сопоставление с образцом, обобщения, деструкторы
- Тестирование, установку новых инструментов, использование
miri - Небезопасный Rust: сырые указатели, псевдонимы, многоуровневые заимствования, вариантность
Да, связные списки настолько ужасны, что вам, для того, чтобы они заработали, придётся освоить все эти концепции.
Everything's in the sidebar (may be collapsed on mobile), but for quick reference, here's what we're going to be making:
Полное содержание книги есть на боковой панели (может быть свёрнута на смартфоне), но, чтобы вы получили представление, вот что мы собираемся сделать:
- Неправильный односвязный стек
- Правильный односвязный стек
- Устойчивый односвязный стек
- Неправильный, но безопасный двусвязный дек
- Правильная небезопасная односвязная очередь
- Небезопасный двусвязный дек для прода
- Куча странных списков
Чтобы мы понимали друг друга, я буду писать здесь все команды, которые ввожу в терминал. Также, для разработки проекта, я использую стандартный растовский пакетный менеджер Cargo. Писать программы на Rust можно и без Cargo, но с ним намного удобнее, чем с rustc. Если вам захочется поэкспериментировать, простые программы можно запускать в браузере через play.rust-lang.org.
В следующих разделах мы будем использовать rustup для установки дополнительных инструментов Rust. Я настоятельно рекомендую устанавливать весь инструментарий Rust, используя rustup.
Давайте начнём и создадим наш проект:
cargo new --lib lists
cd lists
Мы будем помещать каждый список в отдельный файл, так что не потеряем результаты нашей работы.
Следует заметить, что аутентичный способ изучения Rust состоит из написания кода, на который ругается компилятор и попыток понять, какого хрена означают эти ругательства. Я будут тщательно следить за тем, чтобы это случалось как можно чаще. Умение читать и понимать в целом превосходные ошибки компилятора и документацию — невероятно важны для того, чтобы стать продуктивным программистом на Rust.
Впрочем, при написании этого текста, я получила гораздо больше ошибок компилятора, чем оставила в книге. В частности, я выбросила все ошибки, связанные с опечатками и неудачной копи-пастой, которые встречаются во всех больших проектах. В общем, у нас тут экскурсия с гидом по тому, как умеет ругаться компилятор.
Мы будем двигаться достаточно медленно, и я на 100% не собираюсь всё это время быть серьёзной. Я, блин, думаю, что программирование должно быть весёлым! Если вы — читатель, которому нужен максимально информативный, серьёзный и формальный текст, эта книга не для вас. Вообще всё, что я когда-либо напишу — не для вас. Читайте другие книги.
Обязательное Общественное Обращение
Просто чтобы быть предельно ясной: я ненавижу связные списки. Со страстью. Связные списки — ужасные структуры данных. Впрочем, есть несколько отличных сценариев использования связных списков:
- Вам надо много раз сливать и разделять большие списки. Много раз.
- Вы пишите какую-то удивительную неблокирующую конкурентную штуку.
- Вы пишите системную/низкоуровневую штуку и вам нужны интрузивные списки.
- Вы пишите на чистом функциональном языке, где ограниченная семантика вкупе с неизменяемостью делают связные списки простейшим решением.
- ...ну и так далее!
Но у всех, кто пишет на Rust, эти задачи встречаются супер редко. В 99% случаев вы должны просто использовать Vec (массив-стек), а в 99% из оставшегося 1% — VecDeque (массив-дек). Это безусловно лучшие структуры данных для большинства рабочих задач из-за нечастых выделений, небольшой служебной памяти, честного произвольного доступа и локальности кэша.
Связные списки — такая же нишевая и расплывчатая структура данных, как и префиксное дерево. Мало кто станет возражать против моего утверждения, что префиксное дерево — нишевая структура, с которой средний программист, к счастью, никогда в своей жизни не столкнётся. В то же время, у связных списков какая-то необъяснимая популярность. Каждого студента мы учим, как писать связные списки. Это единственная нишевая коллекция, которую я не смогла удалить из std::collections. И в стандартной библиотеке C++ связный список тоже есть!
Мы, как сообщество, должны сказать нет связным спискам как «стандартной» структуре данных. Это — прекрасная структура данных, для которой есть несколько прекрасных сценариев использования, но эти сценарии — исключения, а не правила.
Возможно, кто-то прочитает первый параграф этого Общественного Обращения, бросит чтение, и начнёт мысленный спор, где слово в слово повторит один из пунктов моего списка отличных сценариев. Который, напомню, следует сразу за первым параграфом!
Я собрала здесь несколько контр-аргументов и свои ответы на них, просто чтобы у меня под рукой была ссылка на подробную дискуссию. Можете смело переходить к первой главе, если просто хотите изучить немного Rust!
Производительность не всегда имеет значение
Да! Скажем, ваше приложение занимается в основном вводом и выводом. Или его запускают пару раз в год и время его работы действительно не имеет значения. Но это не аргумент в пользу связного списка. Это аргумент в пользу чего угодно. Зачем ограничиваться связным списком? Используйте связный ассоциативный массив!
Если производительность не имеет значения, то в качестве структуры данных безусловно подойдёт и массив.
У списков разделение-добавление-вставка-удаление выполняются за O(1), если есть указатель на нужный узел
Точняк! Хотя, как заметил Бьёрн Страуструп, на самом деле это неважно, поскольку получение указателя на нужный узел занимает гигантское время по сравнению с простым копированием элементов массива (что на практике довольно быстро).
Если основная работа программы — не слияние и разделение, стоимость любых других операций сводит на нет всю теоретическую выгоду из-за особенностей работы кэша и сложности кодирования.
Но — да, если профилирование показало, что приложение тратит всё время на слияние и разделение, вы получите выгоду от связных списков.
Я не могу позволить себе амортизированную сложность
Вы — уже в достаточно узкой нише, поскольку большинство программистов могут позволить себе амортизированную сложность.
Даже для массивов амортизированная сложность — это худший случай, а не основной.
Если вы знаете максимальное количество элементов (верхнюю границу), можно зарезервировать столько памяти, сколько вам надо.
По моему опыту, количество элементов известно достаточно часто.
Скажем, итераторы Rust как раз для этого предоставляют метод size_hint.
В таком сценарии push и pop гарантированно будут выполняться за O(1).
И они окажутся значительно быстрее, чем push и pop на связных списках.
Вы смещаете указатель, пишите байты и увеличиваете целое число.
И на надо выделять память.
Как вам такая скорость?
Но — да, если вы не можете предсказать количество элементов, связные списки работают быстро даже в худшем случае!
Связные списки занимают меньше места
Ну, это сложно. «Стандартная» стратегия при изменении размера массива — следить, чтобы при увеличении или уменьшении, по меньшей мере половина массива оставалась пустой. При этом действительно уходит много места. Особенно в Rust, где мы не уплотняем коллекции автоматически (что оправданно, если вы собираетесь заполнять их снова), так что потери могут стремиться к бесконечности!
Но это худший случай. В лучшем случае массив-стек имеет всего три дополнительных указателя. Считайте, никаких накладных расходов.
С другой стороны, связные списки гарантированно требуют места для каждого элемент. Служебные данные в односвязном списке — это один указатель, а в двусвязном — два. В отличие от массивов, относительные расходы у списков обратно пропорциональны размеру элементов. Если элементы огромные, накладные расходы близки к 0. Если элементы крошечные (скажем, байты), служебные данные в 16 раз превышают размер самих элементов (в 8 — на 32-хбитных машинах)!
А, если учесть выравнивание по размеру указателя — в 23 раза (в 11 за 32-хбитные машинах).
При этом предполагается лучший случай для выделения памяти: выделяемые и возвращаемые узлы находятся близко друг к другу, и память не теряется из-за фрагментации.
Но — да, если у вас огромные элементы, вы не можете предсказать их количество и фрагментация не очень высокая — можно добиться экономии памяти!
Я всё время использую связные списки в «функциональных языках»
Великолепно! Связные списки идеально подходят для функциональных языков, поскольку обеспечивают неизменяемость, могут быть рекурсивно описаны, а также, благодаря магии ленивых вычислений, могут быть бесконечными.
Даже для итерации по связному списку нет необходимости изменять состояние программы. Следующий шаг — это просто переход к следующему под-списку.
В Rust подобные вещи делаются с помощью [итераторов][].
Они могут быть бесконечными.
Над ними можно выполнять операции map, filter, reverse и concatenate, как и над обычными функциональными списками.
Помимо прочего, они ещё и ленивые!
Наконец, Rust облегчает работу с под-массивами с помощью [срезов][].
В функцинальных языках списки обычно делят на голову и хвост, точно также, как это делает slice.split_at_mut(1).
На протяжении долгого времени в Rust существовала крутая экспериментальная система сопоставления с образцом для срезов.
Во время стабилизации её всё-таки упростили, но даже сейчас образцы для срезов весьма изящны!
Кстати, срезы легко превратить в итераторы!
Но — да, если вы ограничены иммутабельной семантикой, связные списки очень удобны.
Заметьте, я не утверждаю, что функциональное программирование — какое-то плохое и недоделаное. Однако, речь идёт о фундаментальном семантическом ограничении: вы можете рассуждать о том, что вещи из себя представляют, но не можете — о том, что они могут делать. На самом деле это такая фича, позволяющая компилятору выполнить тонны экзотических преобразований и может быть даже найти лучший способ решения, снимая с вас необходимость об этом думать. Цена, однако — потеря самой возможности об этом думать. Как правило, есть обходные пути, но время от времени вам всё равно приходиться писать обычный процедурный код.
Даже в функциональных языках следует стремиться использовать подходящую структуру данных для задач, где действительно нужна какая-то структура данных. Да, односвязные списки — ваш основной инструмент для работы, но он действительно плохо подходит для хранения больших объёмов данных и поиска в нём значений.
Связные списки отлично подходят для реализации потокобезопасных структур данных
Да! Хотя создание потокобезопасных структур данных совершенно из другой оперы, и к нему нельзя относиться легкомысленно. Однозначно, в теме разбираются не так много людей. И как только они разработают для вас готовую структуру, вы больше не будете выбирать связный список. Вы будете выбирать MPSC-очередь или что-то такое. А для этого очереди стратегия реализации очень сильно отличается!
Но — да, связные списки — де факто герои тёмного мира неблокирующей конкуррентности.
Тык-пык ядро, встраиваемые системы, туда-сюда интрузивные
Это — ниши. Вы говорите о ситуациях, в которых нельзя использовать даже стандартную библиотеку. Разве это не красный флаг, что вы делаете что-то очень необычное?
Плюс ко всему, всё это крайне небезопасно.
Но — ладно. Пишите свои потрясающие списки без выделения памяти в куче.
Итераторы могут работать после вставки/удаления элементов
Вы играете в очень деликатную игру. Особенно, если у вас нет сборщика мусора. Не вдаваясь в детали, могу предоположить, что ваш код, вероятно, несколько запутан.
Но — да, с помощью курсоров можно делать действительно крутые и безумные штуки.
Они простые и хорошо подходят для обучения!
Ну, да. Вы читаете книгу, основанную как раз на этой предпосылке. Односвязные списки, и правда ,достаточно просты. А вот двусвязные списки, как мы увидим, могут быть довольно жуткими.
Сделайте вдох
Что ж. С этим разобрались. Давайте теперь напишем хреналлиард связных списков.
Плохой односвязный стек
Эта глава будет гораздо длиннее прочих, поскольку нам предстоит познакомиться практически со всем языком Rust и, чтобы лучше разобраться, часть материала мы будем осваивать «сложным путём».
Наш первый список мы поместим в файл src/first.rs.
Надо сказать компилятору Rust, что first.rs входит в состав нашей библиотеки.
Для этого в начале файла src/lib.rus (который создала для нас утилита Cargo) достаточно написать :
// в lib.rs
pub mod first;Базовое представление данных
Ладно, что такое связный список? Ну, в целом, это набор кусочков данных в куче, которые последовательно указывают друг на друга. (Да, я знаю, что разработчикам ядра куча недоступна, мы сейчас не об этом!) Связные списки — это то, что процедурные программисты не станут трогать 10-метровой палкой, а функциональные программисты используют вообще для всего. Кажется справедливым, что определение связного списка в этом случае что мы должны спросить у функциональных программистов. И они дадут вам что-то такое:
List a = Empty | Elem a (List a)
Что приблизительно читается как «Список является либо Пустым, либо Элементом за которым следует Список».
Это рекурсивное определение, выраженное через тип-сумму или, если подробнее, через тип, который «может принимать одно из нескольких значений, у каждого из которых может быть свой тип».
В языке Rust типы-суммы называются перечислениями (enum)!
Если вы пришли из C-подобного языка, то речь идёт о знакомых и любимых нами enum, но на максималках.
Ладно, давайте перепишем это функциональное определение на Rust!
Для простоты первое время мы не будем использовать обобщения (generics). Значениями узлов у нас будут обычные 32-битные числа.:
// в first.rs
// pub говорит, что мы хотим, чтобы авторы других модулей могли использовать List
pub enum List {
Empty,
Elem(i32, List),
}Уф, как сложно. Попробуем скомпилировать:
> cargo build
error[E0072]: recursive type `first::List` has infinite size
--> src/first.rs:4:1
|
4 | pub enum List {
| ^^^^^^^^^^^^^ recursive type has infinite size
5 | Empty,
6 | Elem(i32, List),
| ---- recursive without indirection
|
= help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `first::List` representable
Текст ошибки: рекурсивный тип first::List имеет бесконечный размер.
Ну. Не знаю, как вы, а я определённо чувствую себя преданной всем сообществом функциональных программистов.
Подумав над сообщением об ошибке (после того, как переживём всю эту историю с предательством), мы обнаружим, что rustc на самом деле подсказывает нам, как решить нашу проблему:
insert indirection (e.g., a
Box,Rc, or&) at some point to makefirst::Listrepresentable
Перевод: чтобы сделать first::List представимым, добавьте в нужном месте косвенный доступ, т. е. Box, Rc или &
Так, box.
Что это такое?
Давайте погуглим rust box...
Посмотрим, что пишут...
pub struct Box<T>(_);Тип-указатель для размещения в куче. Дополнительную информацию см. в документации к модулю boxed.
щёлкает по ссылке
Box<T>, обычно называемый «боксом» — простейшая форма размещения объекта в куче в языке Rust. Боксы являются владельцами этого объекта и уничтожают его, когда выходят из области видимости.Примеры
Создание бокса
let x = Box::new(5);Создание рекурсивной структуры данных:
#![allow(unused)] fn main() { #[derive(Debug)] enum List<T> { Cons(T, Box<List<T>>), Nil, } }fn main() { let list: List<i32> = List::Cons(1, Box::new(List::Cons(2, Box::new(List::Nil)))); println!("{:?}", list); }Этот код напечатает
Cons(1, Box(Cons(2, Box(Nil)))).Рекурсивные структуры должны быть помещены в бокс, потому что определение:
Cons(T, List<T>),не работает. В данном случае размер List зависит от количества элементов, так что мы не знаем, сколько памяти выделить для Cons. Box, который по сути является указателем, имеет фиксированный размер, поэтому компилятор может вычислить размер Cons.
Ого! Хм. Кажется, это самая релевантная и полезная документация, которую я когда-либо видела. Первые абзацы — буквально о том, что мы пытаемся написать, почему оно не работает и как всё исправить.
Блин, доки рулят.
Ладно, давайте напишем так:
pub enum List {
Empty,
Elem(i32, Box<List>),
}> cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
Ага, проект собрался!
...но у нас получилось достаточно дурацкое определение списка. Сразу по нескольким причинам.
Представим список из двух элементов.
[] = Стек
() = Куча
[Elem A, ptr] -> (Elem B, ptr) -> (Empty, *junk*)
Есть два ключевых момента:
- Мы выделили память под узел, который как бы говорит «На самом деле я не Узел»
- Один из наших узлов вообще не размещён в куче
Впрочем, кажется, эта пара могла бы нейтрализовать друг друга. Мы разместили в куче дополнительный узел, но один из узлов вообще не должен быть в куче. Взглянем на другой потенциальный способ хранения нашего списка:
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
Здесь мы размещаем в куче все наши узлы без исключения.
Ключевое отличие в отсутствии мусора (junk) из нашего первого сценария.
Что это за мусор?
Что в этом разобраться, рассмотрим, как наш enum размещается в памяти.
Пусть у нас будет такой enum:
enum Foo {
D1(T1),
D2(T2),
...
Dn(Tn),
}В Foo хранится целое число, которое обозначает, какой из вариантов перечисления (D1, D2, .. Dn) представлен.
Это — метка (tag) перечисления.
Ему также требуется достаточно памяти, чтобы сохранить наибольший из типов T1, T2, .. Tn (плюс немного дополнительного пространства, чтобы удовлетворить требования выравнивания).
Это значит, что хотя Empty хранит один бит информации, он в любом случае резервирует место для указателя и элемента, поскольку в любой момент может превратиться в Elem.
Поэтому в первом сценарии в куче хранится дополнительный элемент, где полезным является один бит, а всё остальное — мусор.
Во втором сценарии последний узел содержит нулевой указатель, который означает конец списка, то есть, не является мусором.
Один из узлов вообще не размещается в куче и это, как ни странно, не очень хорошо. Причина — в неунифицированном размещении узлов (часть узлов хранится одним способом, а часть — другим). Для вставки и удаления узлов это не важно, но разделение и слияние списков становятся сложнее.
Сравним разделение списка в обоих сценариях.
сценарий 1:
[Elem A, ptr] -> (Elem B, ptr) -> (Elem C, ptr) -> (Empty *junk*)
разбиваем список на элементе C:
[Elem A, ptr] -> (Elem B, ptr) -> (Empty *junk*)
[Elem C, ptr] -> (Empty *junk*)
сценарий 2:
[ptr] -> (Elem A, ptr) -> (Elem B, ptr) -> (Elem C, *null*)
разбиваем список на элементе C:
[ptr] -> (Elem A, ptr) -> (Elem B, *null*)
[ptr] -> (Elem C, *null*)
Во втором сценарии разделение сводится к копированию указателя на B в стек и обнулению указателя на C. В первом сценарии в целом происходит то же самое, но, помимо прочего, приходиться копировать C из кучи в стек. Со слияние ситуация похожая, только действия выполняются в обратном порядке.
Одно из немногих преимуществ связных списков в том, что элемент хранится непосредственно в узле. Его можно свободно перемещать по списку, в то же время оставляя на одном и том же месте в памяти. Вы играете с указателями — и элементы «перемещаются». Первый сценарий ломает это свойство.
Хорошо, я почти уверена, что первый сценарий плох. Как нам переписать список теперь? Для начала, мы могли бы сделать что-то вроде этого:
pub enum List {
Empty,
ElemThenEmpty(i32),
ElemThenNotEmpty(i32, Box<List>),
}Надеюсь, вы заметили, что эта идея ещё хуже.
Во-первых, теперь нам придётся писать дополнительные проверки, потому что появился совершенно недопустимый вариант ElemThenNotEmpty(0, Box(Empty)).
А во-вторых, мы всё ещё не избавились от неунифицированного размещения элементов.
Впрочем, у этого варианта есть одно интересное свойство: он позволяет полностью избавиться от размещения узла Empty, сокращая общее число размещений в куче на 1. К сожалению, при этом расходуется ещё больше места! Связано это с тем, что в прошлом сценарии применялась оптимизация указателей на null.
Ранее мы видели ранее, что каждое перечисление хранит метку, чтобы знать, какой из вариантов представлен. Однако, если мы имеем дело с особым видом перечисления:
enum Foo {
A,
B(ContainsANonNullPtr), // ContainsANonNullPtr — ненулевой указатель
}срабатывает оптимизация указателя на null, которая избавляется от места, выделяемого под метку. Для варианта A все байты перечисления равны 0. Если байты не равны 0, у нас неизбежно вариант B. Всё работает, поскольку B не может состоять из одних 0, так как содержит ненулевой указатель. Ловко!
Не приходят ли вам в голову другие перечисления и типы, где могла бы работать такого рода оптимизация?
На самом деле их очень много!
По этой причине Rust не регламентирует способ хранения перечислений.
Существует несколько сложных оптимизаций, которые для нас делает Rust, но указатель на null безусловно один из самых важных!
Это значит, что &, &mut, Box, Rc, Arc, Vec и некоторые другие важные типы Rust не требуют дополнительной памяти, если завернуть их в тип Option!
(Большинство из них мы обсудим позже.)
Итак, как избавиться от мусора, унифицировано хранить узлы и добиться заветной оптимизации указателя на null? Попробуем разграничить идеи наличия элемента и размещения последующего списка. Чтобы это сделать, будем думать в стиле C. Конечно, структуры!
В то время, как перечисления позволяют нам объявлять типы, которые содержат одно из нескольких значений, структуры позволяют нам объявлять типы, которые одновременно содержат много значений. Разделим наш List на два типа: List и Node.
Как и раньше, List может быть либо пустым, либо содержать элемент, за которым следует другой список. Представив вариант «содержать элемент, за которым следует другой список" в виде структуры, мы приводим Box в оптимальное положение:
struct Node {
elem: i32,
next: List,
}
pub enum List {
Empty,
More(Box<Node>),
}Проверим, всех ли целей мы добились?
- Хвост списка никогда не выделяет дополнительное пространство: есть!
enumхранится в заветной форме оптимизированного указателя на null: есть!- Все элементы хранятся унифицировано: есть!
Прекрасно! Мы сконструировали тот самый способ представления, который использовали, чтобы продемонстрировать, что наш первый способ был неверным (о чём нам поведала документация Rust).
> cargo build
warning: private type `first::Node` in public interface (error E0446)
--> src/first.rs:8:10
|
8 | More(Box<Node>),
| ^^^^^^^^^
|
= note: #[warn(private_in_public)] on by default
= warning: this was previously accepted by the compiler but
is being phased out; it will become a hard error in a future release!
Текст ошибки: приватный тип first::Node в публичном интерфейсе.
:(
Rust снова сердится — и всё по нашей вине.
Мы сделали List публичным (чтобы люди могли его использовать), а Node — нет.
Проблема в том, что внутренности enum публичны и там, по идее, не должно быть приватных типов.
Можно было бы сделать Node публичным, однако мы в Rust предпочитаем скрывать детали реализации.
Сделаем List структурой:
pub struct List {
head: Link,
}
enum Link {
Empty,
More(Box<Node>),
}
struct Node {
elem: i32,
next: Link,
}Поскольку List — это структура с единственным полем, её размер будет совпадать с размером поля.
Сила абстракций с нулевой стоимостью!
> cargo build
warning: field is never used: `head`
--> src/first.rs:2:5
|
2 | head: Link,
| ^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: variant is never constructed: `Empty`
--> src/first.rs:6:5
|
6 | Empty,
| ^^^^^
warning: variant is never constructed: `More`
--> src/first.rs:7:5
|
7 | More(Box<Node>),
| ^^^^^^^^^^^^^^^
warning: field is never used: `elem`
--> src/first.rs:11:5
|
11 | elem: i32,
| ^^^^^^^^^
warning: field is never used: `next`
--> src/first.rs:12:5
|
12 | next: Link,
| ^^^^^^^^^^
Rust выводит множество предупреждений, потому что, насколько он может судить, мы написали совершенно бесполезный код.
Мы не используем head и никто из пользователей нашей библиотекой не может этого сделать, потому что это приватное поле.
Транзитивно это значит, что List и Node тоже никто не использует.
Давайте с этим разберёмся!
Напишем немного кода для нашего списка!
Метод new
Чтобы связать написанный код с типом, используем блоки impl:
impl List {
// воплотить код в жизнь
}Разберёмся, как писать код правильно. В Rust объявление функции выглядит так:
fn foo(arg1: Type1, arg2: Type2) -> ReturnType {
// тело
}Первая вещь, которая нам нужна: способ создания (конструирования) списка.
Поскольку мы спрятали детали реализации, эту возможность надо предоставить, как функцию.
В Rust для этого пишут статический метод, который по сути является обычной функцией внутри блока impl:
impl List {
pub fn new() -> Self {
List { head: Link::Empty }
}
}Несколько замечаний по поводу кода:
Self— это псевдоним для «того тип, который я написал в заголовкеimpl». Отличный способ не повторяться!- Мы создаём экземпляр структуры практически также, как объявляем её, за исключением того, чтобы вместо указания типов полей, мы инициализируем их значениями.
- Мы ссылаемся на варианты перечисления, используя
::, то есть оператор указания пространства имён. - Последнее выражение функции считается её результатом.
Такой подход позволяет делает простые функции лаконичными.
Но всё ещё можно использовать
returnдля досрочного возврата из функции, как и в других C-подобных языках.
Основы владения
Теперь, когда мы можем сконструировать список, было бы неплохо что-нибудь с ним сделать.
Делать будем при помощи «обычных» (не статических) методов.
Метод — это особый вид функции в Rust.
У него есть аргумент self без типа:
fn foo(self, arg2: Type2) -> ReturnType {
// тело
}Есть три основные формы, которые он может принимать: self, &must self и &self.
Эти три формы представляют три основные формы владения в Rust:
self— Значение&mut self— изменяемая ссылка&self— разделяемая ссылка
Значение — это, по сути, истинное владение.
Вы можете делать со значением всё, что хотите: отдать, уничтожить, изменить или передавать по ссылке.
Если вы передаёте что-то по значению, оно отдаётся в новое место.
Новое место теперь владеет значением, а старое место больше не имеет к нему доступа.
По этой причине большинство методов не используют self — было бы довольно глупо работать со списком, теряя к нему доступ!
Изменяемая ссылка означает временный эксклюзивный доступ к значению, которым вы не владеете.
Вы можете делать со значением абсолютно всё, что хотите, если в конце вы оставляете его в рабочем состоянии (иное было бы невежливым по отношению к владельцу!).
Это значит, что на самом деле значение можно полностью перезаписать.
Очень полезный частный случай — обмен двух значений, который нам пригодится, и не единожды.
Единственное, что нельзя сделать с &mut — уничтожить, не заменив другим значением.
&mut self отлично подходит для методов, которым надо изменить self.
Разделяемое владение означает временный разделяемый доступ к значению, которым вы не владеете.
Имея разделяемый доступ, вы в общем случае ничего не можете изменить.
Как в музее: смотреть можно, руками трогать нельзя!
& отлично подходит для методов, которым self нужен только для чтения.
Позже мы узнаем, что правило об изменении в определённых случаях можно обойти. По этой причине разделяемые ссылки не называют неизменяемыми. Скорее, изменяемые ссылки можно было бы называть уникальными, но, как выяснило Rust-сообщество, связь между владением и изменяемостью интуитивно понятна в 99% случаев.
Метод push
Пришло время написать функцию вставки числа в начало списка.
Вставка (push) изменяет список, поэтому нам нужен параметр &mut self.
Кроме того, нам потребуется значение i32, которое мы будем вставлять.
impl List {
pub fn push(&mut self, elem: i32) {
// написать
}
}Прежде всего нам надо создать узел и сохранить в нём наш элемент:
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: ?????
};
}Что должно быть по ссылке next?
Ну, весь наш старый список!
Можем ли мы... просто так и написать?
impl List {
pub fn push(&mut self, elem: i32) {
let new_node = Node {
elem: elem,
next: self.head,
};
}
}> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:19:19
|
19 | next: self.head,
| ^^^^^^^^^ cannot move out of borrowed content
Неееееет. Наверное, Rust написал всё правильно, но непонятно, что это значит и что с этим делать:
cannot move out of borrowed content
Нельзя переместить заимствованное содержимое.
Мы пытаемся переместить поле self.head в next, но Rust не разрешает нам это сделать.
Проблема в том, что когда мы завершим заимствование и «вернём назад» законному владельцу, self останется частично инициализированным.
Как мы уже говорили, это единственное, что нельзя сделать с помощью &mut.
Rust очень вежлив, а это — невежливо (кстати, и опасно тоже, но вряд ли компилятор беспокоит какая-то опасность).
Что если вместо старого значения мы разместим узел, который мы создаём:
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: self.head,
});
self.head = Link::More(new_node);
}> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:19:19
|
19 | next: self.head,
| ^^^^^^^^^ cannot move out of borrowed content
Ничего не вышло.
В принципе, это одна из тех штук, которую Rust мог бы принять, но не принимает (по многим причинам, одна из которых — это [безопасность исключений][]).
Нам нужен способ забрать значение head так, чтобы Rust не заметил пропажи.
Обратимся за советом к печально известному взломщику ржавых замков Индиане Джонсу:
Хм, Инди советует прибегнуть к маневру mem::replace.
Эта невероятно полезная функция позволяет нам забрать значение заимствованного объекта, заменив его другим значением.
Добавим std::mem в начало файла, чтобы модуль mem оказался в локальной области видимости:
use std::mem;и используем надлежащим образом:
pub fn push(&mut self, elem: i32) {
let new_node = Box::new(Node {
elem: elem,
next: mem::replace(&mut self.head, Link::Empty),
});
self.head = Link::More(new_node);
}Здесь мы временно заменяем (replace) self.head значением Link::Empty перед тем, как заменить его новой головой списка.
Не стану врать: так делать не надо (по меньшей мере, это решение не простое, и не очевидное), но в учебных целях мы должны проверить все грабли.
Позже мы познакомимся с простым и очевидным способом.
Но, подождите, метод push уже готов!
Кажется.
Честно говоря, это стоит протестировать.
Как это сделать проще всего?
Написать метод pop и убедиться, что он возвращает правильные результаты.
Метод pop
Как и push, метод pop меняет список.
Но, в отличие от push, метод pop возвращает какое-то значение.
При этом он должен учитывать каверзный граничный случай: что, если список пуст?
Чтобы представить этот случай, воспользуемся проверенным типом Option:
pub fn pop(&mut self) -> Option<i32> {
// дописать
}Option<T> — это перечисление, которое представляет опциональное значение, которое, возможно, существует.
Вариант Some(T) соответствует существующему значению, а None — отсутствию значения.
Как и в случае с Link, можно было бы придумать собственный тип, но мы хотим, чтобы пользователи понимали, что именно представляет из себя возвращаемое значение, а Option настолько вездесущ, что все про него все знают.
Фактически, он настолько фундаментален, что неявно импортируется в область видимости каждого модуля вместе с вариантами Some и None (поэтому мы и не пишем Option::None).
Угловые скобки в Option<T> означают, что Option, на самом деле — обобщённый тип над T.
То есть, опциональным можно сделать значение любого типа!
Хорошо, у нас есть ссылка Link, как нам узнать, содержит ли она Empty или More?
Конечно же с помощью сопоставления с образцом и оператора match!
pub fn pop(&mut self) -> Option<i32> {
match self.head {
Link::Empty => {
// дописать
}
Link::More(node) => {
// дописать
}
};
}> cargo build
error[E0308]: mismatched types
--> src/first.rs:27:30
|
27 | pub fn pop(&mut self) -> Option<i32> {
| --- ^^^^^^^^^^^ expected enum `std::option::Option`, found ()
| |
| this function's body doesn't return
|
= note: expected type `std::option::Option<i32>`
found type `()`
Ой, pop должна вернуть значение, но этого мы пока не написали.
Мы могли бы вернуть None, но, возможно в данном случае лучше вернуть unimplemented!(), чтобы показать, что мы ещё не завершили реализацию функции.
unimplemented!() — это макрос (! указывает на макрос), который вызывает панику, когда к нему обращаются.
Происходит так называемый контролируемый сбой.
pub fn pop(&mut self) -> Option<i32> {
match self.head {
Link::Empty => {
// дописать
}
Link::More(node) => {
// дописать
}
};
unimplemented!()
}Безусловная паника — это пример расходящейся функции.
Расходящиеся функции не возвращают управления вызывающей функции, поэтому их можно использовать в любом месте, где ожидается значение любого типа.
В нашем случае unimplemented!() используется вместо значения типа Option<T>.
Обратите внимание, что в методе pop мы не используем оператор return.
Значением функции становится её последнее выражение (обычно, последняя строка).
Благодаря этому, действительно простые функции можно сделать намного короче.
Однако, вы всегда можете завершить функцию досрочно с помощью оператора return, как и в любом другом C-подобном языке.
> cargo build
error[E0507]: cannot move out of borrowed content
--> src/first.rs:28:15
|
28 | match self.head {
| ^^^^^^^^^
| |
| cannot move out of borrowed content
| help: consider borrowing here: `&self.head`
...
32 | Link::More(node) => {
| ---- data moved here
|
note: move occurs because `node` has type `std::boxed::Box<first::Node>`, which does not implement the `Copy` trait
--> src/first.rs:32:24
|
32 | Link::More(node) => {
| ^^^^
Да ладно, Rust, перестань! Компилятор, как всегда, на что-то ругается. К счастью, сейчас он предоставил нам всю информацию! По умолчанию, при совпадении с образцом происходит перемещение значения в совпавшую ветку, но, поскольку мы не владеем значением, так делать нельзя.
help: consider borrowing here: `&self.head`
Rust утверждает, что мы должны добавить ссылку в оператор match, чтобы исправить ошибку. 🤷♀️
Попробуем:
pub fn pop(&mut self) -> Option<i32> {
match &self.head {
Link::Empty => {
// дописать
}
Link::More(node) => {
// дописать
}
};
unimplemented!()
}> cargo build
warning: unused variable: `node`
--> src/first.rs:32:24
|
32 | Link::More(node) => {
| ^^^^ help: consider prefixing with an underscore: `_node`
|
= note: #[warn(unused_variables)] on by default
warning: field is never used: `elem`
--> src/first.rs:13:5
|
13 | elem: i32,
| ^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `next`
--> src/first.rs:14:5
|
14 | next: Link,
| ^^^^^^^^^^
Ура, снова компилируется!
Теперь давайте обсудим логику работы нашего метода.
Мы хотим создать Option, так что пусть у нас будет переменная для опционального значения.
В случае пустого списка мы присвоим ей None.
В случае непустого списка, мы присвоим ей Some(i32) и заменим голову списка.
Что ж, попробуем?
pub fn pop(&mut self) -> Option<i32> {
let result;
match &self.head {
Link::Empty => {
result = None;
}
Link::More(node) => {
result = Some(node.elem);
self.head = node.next;
}
};
result
}> cargo build
Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
error[E0507]: cannot move out of borrowed content
--> src/first.rs:35:29
|
35 | self.head = node.next;
| ^^^^^^^^^ cannot move out of borrowed content
голова
стол
Мы пытаемся забрать владение node в то время как узел доступен нам только по разделяемой ссылке.
Возможно, нам следует вернуться на шаг назад и подумать, что мы пытаемся сделать. Мы хотим:
- Проверить, не пустой ли список.
- Если пустой, просто вернуть
None. - Если не пустой:
- удалить голову списка
- удалить
elem - заменить голову списка следующим узлом
- вернуть
Some(elem)
Ключевая мысль заключается в том, что мы хотим что-то удалить, а это значит, что доступ к голове списка нам нужен по значению.
Мы определённо не можем ничего менять через разделяемую ссылку, которую получаем с помощью &self.head.
Кроме того, имея на руках только изменяемую ссылку на self, мы можем переместить что-либо единственным способом — через замену.
Выглядит так, словно нам опять предстоит танец вокруг Empty!
Попробуем:
pub fn pop(&mut self) -> Option<i32> {
let result;
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => {
result = None;
}
Link::More(node) => {
result = Some(node.elem);
self.head = node.next;
}
};
result
}cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
Боже мой!
Всё скомпилировалось без единого предупреждения!!!!!
Я собираюсь выступить в роли линтера для нашего кода.
Мы сделали result возвращаемым значением, но на самом деле эта переменная нам вообще не нужна!
Также, как и функция получает значение своего последнего выражения, каждый блок получает значение своего последнего выражения.
Обычно мы ставим в конце операторов точку с запятой, а это значит, что блок возвращает пустой кортеж, ().
На самом деле, пустой кортеж — то самое значение, которое возвращают функции без возвращаемого значения, такие, как push.
Так что мы можем переписать pop так:
pub fn pop(&mut self) -> Option<i32> {
match mem::replace(&mut self.head, Link::Empty) {
Link::Empty => None,
Link::More(node) => {
self.head = node.next;
Some(node.elem)
}
}
}Так чуть лаконичнее и идиоматичнее.
Обратите внимание, что ветка Link::Empty полностью избавилась от фигурных скобок, потому что состоит теперь только из одного выражения.
Удобная короткая запись для простых случаев.
cargo build
Finished dev [unoptimized + debuginfo] target(s) in 0.22s
Прекрасно, всё ещё работает!
Тестирование
Прекрасно, теперь, когда у нас есть push и pop, мы можем протестировать наш стек!
Для Rust и cargo тестирование — это гражданин первого класса, так что всё должно быть очень просто.
Достаточно написать функцию и пометить её аннотацией #[test].
В целом, мы пытаемся размещать наши тесты рядом с тестируемым кодом, как это принято в сообществе Rust. Тем не менее, обычно мы пишем тесты в новом пространстве имён, чтобы избежать конфликтов с «реальным» кодом.
Ключевое слово mod можно использовать не только для объявления внешнего модуля (как мы сделали это с first.rs и lib.rs), но и для создания встроенного модуля:
// в first.rs
mod test {
#[test]
fn basics() {
// написать
}
}Мы запускаем тесты командой cargo test.
> cargo test
Compiling lists v0.1.0 (/Users/ADesires/dev/temp/lists)
Finished dev [unoptimized + debuginfo] target(s) in 1.00s
Running /Users/ADesires/dev/lists/target/debug/deps/lists-86544f1d97438f1f
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
; 0 filtered out
Ура, наш тест, который ничего не проверяет, успешно пройден!
Теперь давайте напишем какую-нибудь проверку.
В этом нам поможет макрос assert_eq!.
В нём нет никакой особой магии тестирования.
Он всего навсего сравнивает две штуки, которые ему передали, и паникует, если они не совпадают.
Да, мы сигнализируем о проблеме при помощи паники!
mod test {
#[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);
}
}> cargo test
error[E0433]: failed to resolve: use of undeclared type or module `List`
--> src/first.rs:43:24
|
43 | let mut list = List::new();
| ^^^^ use of undeclared type or module `List`
Ой!
Поскольку мы создали новый модуль, в него надо явным образом импортировать List.
mod test {
use super::List;
// всё остальное точно также
}> cargo test
warning: unused import: `super::List`
--> src/first.rs:45:9
|
45 | use super::List;
| ^^^^^^^^^^^
|
= note: #[warn(unused_imports)] on by default
Finished dev [unoptimized + debuginfo] target(s) in 0.43s
Running /Users/ADesires/dev/lists/target/debug/deps/lists-86544f1d97438f1f
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
; 0 filtered out
Да!
Хотя, что это за предупреждение?.. В нашем тесте мы используем List явным образом!
...но только при запуске тестов!
Чтобы угодить компилятору (и быть дружелюбным к другим программистам) мы должны явно указать, что весь модуль test должен быть скомпилирован только когда мы запускаем тесты.
#[cfg(test)]
mod test {
use super::List;
// всё остальное точно также
}На этом тестирование завершено!
Метод drop
Мы можем создать стек, вставить в него элемент, извлечь его обратно. Мы даже протестировали, что всё это правильно работает!
Надо ли нам беспокоиться об освобождении памяти? Технически — нет, вообще не надо! Как и C++, Rust использует деструкторы, чтобы автоматически освобождать ресурсы, после их использования. Тип имеет деструктор, если он реализует типаж, который называется Drop. Типажи — это научное название интерфейсов в языке Rust. Типаж Drop имеет следующий вид:
pub trait Drop {
fn drop(&mut self);
}Что-то вроде: «когда вы выйдете из области видимости, я дам вам секунду, чтобы прибрать за собой».
Вы не должны реализовывать Drop, если у вас есть типы, реализующие Drop и всё, что вы хотите — это вызвать их деструкторы.
В случае List, всё что ему нужно — это освободить голову, что, по идее приведёт к освобождению Box<Node>.
Всё это будет сделано автоматически... с одним «но».
Автоматическая уборка может пойти не по плану.
Посмотрим на простой список:
list -> A -> B -> C
Когда удаляется list, он попытается удалить A, который попытается удалить B, который попытается удалить C.
Возможно, кое-кто из вас занервничал.
Это рекурсивный код, а рекурсивный код может привести к переполнению стека!
Некоторые из вас, возможно, подумали: «здесь точно хвостовая рекурсия, а любой приличный язык программирования гарантирует, что при хвостовой рекурсии переполнения не будет». На самом деле это неверно! Чтобы понять, почему, давайте вручную реализуем Drop так, как это сделал бы компилятор:
impl Drop for List {
fn drop(&mut self) {
// ПРИМЕЧАНИЕ: в реальном коде нельзя вызвать `drop` явно;
// так что мы притворимся компилятором!
self.head.drop(); // хвостовая рекурсия - хорошо!
}
}
impl Drop for Link {
fn drop(&mut self) {
match *self {
Link::Empty => {} // Готово!
Link::More(ref mut boxed_node) => {
boxed_node.drop(); // хвостовая рекурсия - хорошо!
}
}
}
}
impl Drop for Box<Node> {
fn drop(&mut self) {
self.ptr.drop(); // ой, подождите, не хвостовая рекурсия!
deallocate(self.ptr);
}
}
impl Drop for Node {
fn drop(&mut self) {
self.next.drop();
}
}Мы не можем освободить содержимое Box после вызова deallocate, так что здесь у нас хвостовая рекурсия отменяется!
Вместо этого, напишем итеративное освобождение List, которое выведет узлы из их боксов.
impl Drop for List {
fn drop(&mut self) {
let mut cur_link = mem::replace(&mut self.head, Link::Empty);
// `while let` == "повторяй, пока образец совпадает"
while let Link::More(mut boxed_node) = cur_link {
cur_link = mem::replace(&mut boxed_node.next, Link::Empty);
// здесь boxed_node выходит из области видимости и уничтожается;
// но поле `next` заменяется на `Link::Empty`,
// поэтому бесконечная рекурсия не возникает
}
}
}> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 1 test
test first::test::basics ... ok
test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured
Великолепно!
Бонусный раздел для преждевременной оптимизации!
Наша реализация освобождения очень напоминает код while let Some(_) = self.pop() { }, который, безусловно, проще.
Чем они отличаются, и какие проблемы с производительностью могут возникнуть, если мы обобщим наш список для хранения объектов любого типа, а не только целых чисел?
Раскрыть ответ
pop возвращает Option<i32> в то время, как наша реализация манипулирует только ссылками (Box<Node>).
Поэтому наша реализация всего лишь переносит указатели на узлы, в то время как pop переносит значения, которые хранятся в узлах.
Может быть очень дорого обобщать наш список, ведь кто-то может использовать его для экземпляров типа VBTWADI (VeryBigThingWithADropImpl — очень большая штука с реализацией Drop).
Боксы способны запускать реализацию drop для своего содержимого непосредственно, так что у них нет такой проблемы.
Ну, а поскольку VBTWADI — именно та штука, для которой связные списки гораздо предпочтительнее массивов, такое поведение немного разочарует.
Если вы хотите взять лучшее от обеих реализаций, вы можете добавить новый метод fn pop_node(&mut sefl) -> Link который корректно вызывается как из pop, так и из drop.
Финальный код
Итак, 6000 слов спустя, мы написали такой код:
#![allow(unused)] fn main() { use std::mem; pub struct List { head: Link, } enum Link { Empty, More(Box<Node>), } struct Node { elem: i32, next: Link, } impl List { pub fn new() -> Self { List { head: Link::Empty } } pub fn push(&mut self, elem: i32) { let new_node = Box::new(Node { elem: elem, next: mem::replace(&mut self.head, Link::Empty), }); self.head = Link::More(new_node); } pub fn pop(&mut self) -> Option<i32> { match mem::replace(&mut self.head, Link::Empty) { Link::Empty => None, Link::More(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, Link::Empty); while let Link::More(mut boxed_node) = cur_link { cur_link = mem::replace(&mut boxed_node.next, Link::Empty); } } } #[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); } } }
Только посмотрите! 80 строк, из них половина — тесты! Ну, я предупреждала, что первая глава потребует времени!
Хороший односвязный стек
В прошлой главе мы написали минимальный жизнеспособный односвязный стек. Правда, было несколько проектных решений, которые сделали его довольно отстойным. Предлагаю сделать его не таким отстойным, а для этого:
- Переизобрести велосипед
- Сделать наш список способным содержать элементы любого типа
- Добавить метод
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, чтобы перебирать элементы одновременно от начала к концу, и от конца к началу! Вот как!
Финальный код
Итак, мы дописали второй список и вот финальный код!
#![allow(unused)] fn main() { 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)); } } }
Обрастаем функционалом!
A Persistent Singly-Linked Stack
Устойчивый односвязный стек
Alright, we've mastered the art of mutable singly-linked stacks.
Прекрасно, мы овладели искусством мутебельных односвязных стеков.
Let's move from single ownership to shared ownership by writing a persistent immutable singly-linked list. This will be exactly the list that functional programmers have come to know and love. You can get the head or the tail and put someone's head on someone else's tail... and... that's basically it. Immutability is a hell of a drug.
Давайте перейдём с единоличного владения к разделямому владению путём написания устойчивого иммутабельного односвязного списка. Это именно такой список, который знают и любят функциональные программисты. Вы можете получить голову или хвост и поместить чью-то голову на чей-то ещё хвост... и... в принципе, это всё. Иммутабельность — охренительный наркотик.
In the process we'll largely just become familiar with Rc and Arc, but this will set us up for the next list which will change the game.
В процессе мы, в основном, будем знакомиться с Rc и Arc, но это подготовит нас к следующему списоку, который изменит игру.
Let's add a new file called
third.rs:
Создадим новый файл с именем third.rs:
// in lib.rs
// в lib.rs
pub mod first;
pub mod second;
pub mod third;No copy-pasta this time. This is a clean room operation.
Пока никакой копи-пасты. Начинаем с чистого листа.
Layout
Представление данных
Alright, back to the drawing board on layout.
Ладно, возвращаемся к чертёжной доске, чтобы нарисовать представление.
The most important thing about a persistent list is that you can manipulate the tails of lists basically for free:
Важнейшая вещь об устойчивых списках заключается в том, что вы свободно можете манипулировать хвостами списков:
For instance, this isn't an uncommon workload to see with a persistent list:
Например, такое поведение не является чем то необычным при работе с устойчивым списком:
list1 = A -> B -> C -> D
list2 = tail(list1) = B -> C -> D
list3 = push(list2, X) = X -> B -> C -> D
But at the end we want the memory to look like this:
Но в итоге мы хотим, чтобы память выглядела так:
list1 -> A ---+
|
v
list2 ------> B -> C -> D
^
|
list3 -> X ---+
This just can't work with Boxes, because ownership of
Bis shared. Who should free it? If I drop list2, does it free B? With boxes we certainly would expect so!
Это просто не будет работать с Box, потому что владение B разделяется.
Кто должне его особождать?
Если удалить list2, должно ли это привести к освобождению B?
В случае боксов, мы определённо должны ли бы этого ожидать!
Functional languages — and indeed almost every other language — get away with this by using garbage collection. With the magic of garbage collection, B will be freed only after everyone stops looking at it. Hooray!
Функиональным языкам — да, по сути, всем языкам — это сходит с рук за счёт сборки мусора. Благодаря магии сборки мусора, B будет освобождён только после того, как все перестанут на него смотреть . Ура!
Rust doesn't have anything like the garbage collectors these languages have. They have tracing GC, which will dig through all the memory that's sitting around at runtime and figure out what's garbage automatically. Instead, all Rust has today is reference counting. Reference counting can be thought of as a very simple GC. For many workloads, it has significantly less throughput than a tracing collector, and it completely falls over if you manage to build cycles. But hey, it's all we've got! Thankfully, for our usecase we'll never run into cycles (feel free to try to prove this to yourself — I sure won't).
В Rust нет ничего похожего на сборщики мусора, которые есть в этих языках. У них есть отслеживающий сборщик мусора, который перелопатит всю помять во время выполнения и найдёт, что убрать автоматически. Вместо этого, всё, что есть сегодня в Rust — это подсчёт ссылок. О подсчёте ссылок можно думать, как об очень простом сборщике мусора. Во многих сценариях его производительность значительно ниже, чем у отслеживающих сборщиков и он полностью выходит из строя, если вы суммете создать циклы. Но — эй, это всё, что у нас есть! К счастью, в наших сценарив мы никогда не зайдём в циклы (можете попробовать доказать это сами себе — я точно не буду).
So how do we do reference-counted garbage collection?
Rc! Rc is just like Box, but we can duplicate it, and its memory will only be freed when all the Rc's derived from it are dropped. Unfortunately, this flexibility comes at a serious cost: we can only take a shared reference to its internals. This means we can't ever really get data out of one of our lists, nor can we mutate them.
Так как же нам сделать сборку мусора, осносванную на подсчёте ссылок?
Rc!
Rc — то же самое, что и Box, но мы можем дублировать его, и его память будет освобождена только тогда, когда все производные Rc будут уничтожены.
К сожалению, эта гибкость ведёт к серьёзному ограничению: мы можем только получить только разделяемую ссылку на внутренний объект.
Это озачает, что мы не можем даже ни по настоящему забрать данные из наших списков, ни изменить их.
So what's our layout gonna look like? Well, previously we had:
Так что на что же должно быть похоже наше представление? Ну, раньше у нас было:
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}Can we just change Box to Rc?
Можем ли мы просто заменить Box на Rc?
// in third.rs
// в third.rs
pub struct List<T> {
head: Link<T>,
}
type Link<T> = Option<Rc<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}cargo build
error[E0412]: cannot find type `Rc` in this scope
--> src/third.rs:5:23
|
5 | type Link<T> = Option<Rc<Node<T>>>;
| ^^ not found in this scope
help: possible candidate is found in another module, you can import it into scope
|
1 | use std::rc::Rc;
|
Oh dang, sick burn. Unlike everything we used for our mutable lists, Rc is so lame that it's not even implicitly imported into every single Rust program. What a loser.
Блин какая едкая насмешка. В отличие от всего, что мы использовали для мутабельных списков, Rc настолько отстойный, что даже неявно не импотируется ни в какую программу на Rust. Что за неудачник.
use std::rc::Rc;cargo build
warning: field is never used: `head`
--> src/third.rs:4:5
|
4 | head: Link<T>,
| ^^^^^^^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
Seems legit. Rust continues to be completely trivial to write. I bet we can just find-and-replace Box with Rc and call it a day!
Выглядит правильно. Rust продолжает быть полность тривиальным для написания. Держу пари, мы просто заменим Box на Rc, и на этом закончим!
...
No. No we can't.
Нет. У нас не выйдет.
Basics
Основы
We already know a lot of the basics of Rust now, so we can do a lot of the simple stuff again.
Сейчас мы уже знаем множество основ языка Rust,
For the constructor, we can again just copy-paste:
В конструкторе мы можем просто использовать копи-пасту:
impl<T> List<T> {
pub fn new() -> Self {
List { head: None }
}
}
pushandpopdon't really make sense anymore. Instead we can provideprependandtail, which provide approximately the same thing.
push и pop в любом случае больше не имеют смысла.
Вместо них мы должны предоставить операции prepend (вставить в начало) и tail (хвост), которые предоставят приблизительно те же возможности.
Let's start with prepending. It takes a list and an element, and returns a List. Like the mutable list case, we want to make a new node, that has the old list as its
nextvalue. The only novel thing is how to get that next value, because we're not allowed to mutate anything.
Давайте начнём со вставки.
Она получает список и элемент и возвращает список.
Как и в случае с мутабельным списком, мы хотим создать новый узел, у которого старый список хранится в поле next.
Единственное нововведение заключается в том, как получить значение для next, поскольку мы не можем ничего менять.
The answer to our prayers is the Clone trait. Clone is implemented by almost every type, and provides a generic way to get "another one like this one" that is logically disjoint, given only a shared reference. It's like a copy constructor in C++, but it's never implicitly invoked.
Ответом на наши молитвы является типаж Clone. Clone реализуется практически любым типом и предоставляет универсальный способ получить «что-то похожее на вот это», используя при этом только разделяемую ссылку, при этом клон будет логически отличаться от оригинала. Метод похож на компирующий конструктор в C++, но никогда не вызывается неявно.
Rc in particular uses Clone as the way to increment the reference count. So rather than moving a Box to be in the sublist, we just clone the head of the old list. We don't even need to match on the head, because Option exposes a Clone implementation that does exactly the thing we want.
В частности, Rc испозьуте Clone, как способ увеличить счётчик ссылок на единицу.
Так что вместо того, чтобы перемещать Box в подсписок, мы просто клонируем голову старого списка.
Нам даже не надо выполнять match над головой, потому что Option предоставляет реализацию Clone, которая делает точно то, что нам нужно.
Alright, let's give it a shot:
pub fn prepend(&self, elem: T) -> List<T> {
List { head: Some(Rc::new(Node {
elem: elem,
next: self.head.clone(),
}))}
}> cargo build
warning: field is never used: `elem`
--> src/third.rs:10:5
|
10 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
warning: field is never used: `next`
--> src/third.rs:11:5
|
11 | next: Link<T>,
| ^^^^^^^^^^^^^
Wow, Rust is really hard-nosed about actually using fields. It can tell no consumer can ever actually observe the use of these fields! Still, we seem good so far.
Да уж, Rust поистине непреклонен по поводу фактического использования полей. Можно сказать, ни один потребитель не может на самом деле наблюдать использование этих полей! В любом случае, пока всё выглядит неплохо.
tailis the logical inverse of this operation. It takes a list and returns the whole list with the first element removed. All that is is cloning the second element in the list (if it exists). Let's try this:
tail — это логическая инверсия этой операции.
Она получает список и возвращает список без первого элемента.
Всё, что нужно сделать — это клонировать второй элемент в списке (если он существует).
Давайте попробуем:
pub fn tail(&self) -> List<T> {
List { head: self.head.as_ref().map(|node| node.next.clone()) }
}cargo build
error[E0308]: mismatched types
--> src/third.rs:27:22
|
27 | List { head: self.head.as_ref().map(|node| node.next.clone()) }
| ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::rc::Rc`, found enum `std::option::Option`
|
= note: expected type `std::option::Option<std::rc::Rc<_>>`
found type `std::option::Option<std::option::Option<std::rc::Rc<_>>>`
Hrm, we messed up.
mapexpects us to return a Y, but here we're returning anOption<Y>. Thankfully, this is another common Option pattern, and we can just useand_thento let us return an Option.
Грм, мы всё испортили.
map ожидает, что мы вернём Y, но здесь мы возвращаем Option<Y>.
К счастью, есть ещё один известный способ использовать Option, так что мы можем просто вызвать and_then, чтобы мы могли вернуть Option.
pub fn tail(&self) -> List<T> {
List { head: self.head.as_ref().and_then(|node| node.next.clone()) }
}> cargo build
Great.
Великолепно.
Now that we have
tail, we should probably providehead, which returns a reference to the first element. That's justpeekfrom the mutable list:
Теперь, когда у нас есть tail, мы, возможно, должны написать head, чтобы возвращать ссылку на первый элемент.
По сути, это peek из мутабельного списка:
pub fn head(&self) -> Option<&T> {
self.head.as_ref().map(|node| &node.elem)
}> cargo build
Nice.
Здорово.
That's enough functionality that we can test it:
У нас достаточно функциональность, чтобы мы захотели её протестировать:
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let list = List::new();
assert_eq!(list.head(), None);
let list = list.prepend(1).prepend(2).prepend(3);
assert_eq!(list.head(), Some(&3));
let list = list.tail();
assert_eq!(list.head(), Some(&2));
let list = list.tail();
assert_eq!(list.head(), Some(&1));
let list = list.tail();
assert_eq!(list.head(), None);
// Make sure empty tail works
let list = list.tail();
assert_eq!(list.head(), None);
}
}> cargo test
Running target/debug/lists-5c71138492ad4b4a
running 5 tests
test first::test::basics ... ok
test second::test::into_iter ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test third::test::basics ... ok
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured
Perfect!
Превосходно!
Iter is also identical to how it was for our mutable list:
Iter тоже идентичен реализации из нашего мутабельного списка:
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<Self::Item> {
self.next.map(|node| {
self.next = node.next.as_deref();
&node.elem
})
}
}#[test]
fn iter() {
let list = List::new().prepend(1).prepend(2).prepend(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 7 tests
test first::test::basics ... ok
test second::test::basics ... ok
test second::test::iter ... ok
test second::test::into_iter ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 6 passed; 0 failed; 0 ignored; 0 measured
Who ever said dynamic typing was easier?
Кто вообще сказал, что динамическая типизация проще?
(chumps did)
(это говорили болваны)
Note that we can't implement IntoIter or IterMut for this type. We only have shared access to elements.
Обратите внимание, что мы не можем реализовать IntoIter или IterMut для этого типа. У нас может быть только разделяемый доступ к элементам.
Drop
Уничтожение
Like the mutable lists, we have a recursive destructor problem. Admittedly, this isn't as bad of a problem for the immutable list: if we ever hit another node that's the head of another list somewhere, we won't recursively drop it. However it's still a thing we should care about, and how to deal with isn't as clear. Here's how we solved it before:
Как и у мутабельных списков, у нас есть проблема рекурсивного уничтожения. Следует признать, что для иммутабельного списка это не такая серьёзная проблема: даже если мы наткнёмся на другой узел, который является головой другого списка где-то, мы не должны рекурсивно его уничтожать. Однако, это всё ещё та вещь, о которой мы должны беспокоиться, поскольку не совсем понятно, как с ней быть. Вот как мы решали эту проблему раньше:
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();
}
}
}The problem is the body of the loop:
Проблема заключается в теле цикла:
cur_link = boxed_node.next.take();This is mutating the Node inside the Box, but we can't do that with Rc; it only gives us shared access, because any number of other Rc's could be pointing at it.
Здесь изменяется узел внутри Box, но мы не может сделать то же самое с Rc; он продоставляет нам только разделяемый доступ, потому что на него может указывать любое количество Rc-указателей.
But if we know that we're the last list that knows about this node, it would actually be fine to move the Node out of the Rc. Then we could also know when to stop: whenever we can't hoist out the Node.
Но если мы точно знаем, что имеем дело с последним списком, который знает о данном узле, на самом деле было бы правильно забрать узел у Rc. Тогда мы могли бы знвть, когда остановиться, всякий раз, когда мы не можем забрать узел.
And look at that, Rc has a method that does exactly this:
try_unwrap:
И смотрите: в Rc есть метод, который делает именно это: try_unwrap:
impl<T> Drop for List<T> {
fn drop(&mut self) {
let mut head = self.head.take();
while let Some(node) = head {
if let Ok(mut node) = Rc::try_unwrap(node) {
head = node.next.take();
} else {
break;
}
}
}
}cargo test
Compiling lists v0.1.0 (/Users/ADesires/dev/too-many-lists/lists)
Finished dev [unoptimized + debuginfo] target(s) in 1.10s
Running /Users/ADesires/dev/too-many-lists/lists/target/debug/deps/lists-86544f1d97438f1f
running 8 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::iter_mut ... ok
test second::test::peek ... ok
test third::test::basics ... ok
test third::test::iter ... ok
test result: ok. 8 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
Great! Nice.
Великолепно! Здорово.
Arc
Arc
One reason to use an immutable linked list is to share data across threads. After all, shared mutable state is the root of all evil, and one way to solve that is to kill the mutable part forever.
Одна из причин использовать иммутабельный связный список — разделение данных между потоками. Помимо прочего, разделяемое мутабельное состояние — корень всех зол, и один из способов справиться с этим — навсегда избавиться от мутабельного.
Except our list isn't thread-safe at all. In order to be thread-safe, we need to fiddle with reference counts atomically. Otherwise, two threads could try to increment the reference count, and only one would happen. Then the list could get freed too soon!
Впрочем, наш список вовсе не является потокобезопасным. Чтобы считаться потокобезопасным, нужно решить проблему атомарного подсчёта ссылок. В противном случае два потока могут попытаться увеличить счётчик ссылок и только одному это удастся. Тогда этот список будет освобождён слишком скоро!
In order to get thread safety, we have to use Arc. Arc is completely identical to Rc except for the fact that reference counts are modified atomically. This has a bit of overhead if you don't need it, so Rust exposes both. All we need to do to make our list is replace every reference to Rc with
std::sync::Arc. That's it. We're thread safe. Done!
Чтобы получить потокобезопасность, мы должны использовать Arc.
Arc полностью идентичен Rc за исключением того факт, что счётчики ссылок модифицируются атомарно.
Это влечёт небольшие накладные расходы, если оно вам не надо, так что Rust предоставляет оба варианта.
Всё, что нам надо с делать с нашим списком, это заменить каждое упоминание Rc на std::sync::Arc.
Это всё.
Мы потокобезопасны.
Сделано!
But this raises an interesting question: how do we know if a type is thread-safe or not? Can we accidentally mess up?
Но это влечёт интересный вопрос: откуда мы знаем, потокобезопасен тип или нет? Можем ли мы случайно ошибиться?
No! You can't mess up thread-safety in Rust!
Нет! В Rust невозможно сломать потокобезопасность!
The reason this is the case is because Rust models thread-safety in a first-class way with two traits:
SendandSync.
Причина в том, что Rust моделирует потокобезопасность путём объектов первого сорта с помощью двух типажей: Send и Sync.
A type is Send if it's safe to move to another thread. A type is Sync if it's safe to share between multiple threads. That is, if
Tis Sync,&Tis Send. Safe in this case means it's impossible to cause data races, (not to be mistaken with the more general issue of race conditions).
Тип относится к Send (отправляемый), если его можно безопасно передать в другой поток.
Тип относится к Sync (синхронный), если его можно безопасно разделить между многими потоками.
То есть , если T реализует Sync, то
&T реализует Send.
Безопасность в данном случае означает, что невозможно устроить гонку данных (что не надо путать с более общий случаем, состоянием гонки).
These are marker traits, which is a fancy way of saying they're traits that provide absolutely no interface. You either are Send, or you aren't. It's just a property other APIs can require. If you aren't appropriately Send, then it's statically impossible to be sent to a different thread! Sweet!
Это типажи-маркеры, что является умным способом сказать, что они не предоставляют ни одного метода. Вы просто либо являетесь Send, либо не являтесь. Это всего лишь свойство, которое могут требовать другие API. Если вы не являетесь полноценным Send, вас нельзя отправить в другой поток статически! Идеально!
Send and Sync are also automatically derived traits based on whether you are totally composed of Send and Sync types. It's similar to how you can only implement Copy if you're only made of Copy types, but then we just go ahead and implement it automatically if you are.
Send и Sync также автоматически реализуются для типов, состоящими только из полей Send и Sync. Это похоже на то, что вы можете реализовать Copy только если состоите исключительно из полей, реализующих Copy, но теперь мы пошли ещё дальше и реализовали всё за вас.
Almost every type is Send and Sync. Most types are Send because they totally own their data. Most types are Sync because the only way to share data across threads is to put them behind a shared reference, which makes them immutable!
Почти все типы — одновременно Send и Sync. Большинство типов относятся к Send, потому что они полностью владеют своими данными. Большинсвто типов относятся к Sync, потому что единственный способ разделить данные между потоками, это спрятать их за разделяемой ссылкой, которая делает их иммутабельными!
However there are special types that violate these properties: those that have interior mutability. So far we've only really interacted with inherited mutability (AKA external mutability): the mutability of a value is inherited from the mutability of its container. That is, you can't just randomly mutate some field of a non-mutable value because you feel like it.
Однако существуют особые типы, которые нарушают эти свойства, они обладают внутренней мутабельностью. До сих пор мы сталкивались только с унаследованной мутабельностью (или внешней мутабельностью): мутабельность значения наследуется от мутабельность её контейнера. То есть, вы не можете просто взять и поменять какое-то поле немутабельного значения , просто потому, что вам так захотелось.
Interior mutability types violate this: they let you mutate through a shared reference. There are two major classes of interior mutability: cells, which only work in a single-threaded context; and locks, which work in a multi-threaded context. For obvious reasons, cells are cheaper when you can use them. There's also atomics, which are primitives that act like a lock.
Типы с внутренней мутабельностью нарушают это правило: оин позволяют менять значения полей через разделяемую ссылку. Есть два важных класса внутренней мутебельности: ячейке, которые работают только в однопоточном контексте и блокировки, которые работают в многопоточном контексте. По очевидным причинам, ячейки дешевле , если вы можете их использовать. Есть также атомарные объекты , то есть примитивы, работающие, как блокировки.
So what does all of this have to do with Rc and Arc? Well, they both use interior mutability for their reference count. Worse, this reference count is shared between every instance! Rc just uses a cell, which means it's not thread safe. Arc uses an atomic, which means it is thread safe. Of course, you can't magically make a type thread safe by putting it in Arc. Arc can only derive thread-safety like any other type.
Так какое отношение всё это имеет к Rc и Arc? Ну, оба они внутренне мутабельны в отношении их счётчков ссылок. Хуже того, этот счётчик ссылок разделяется между всеми экземплярами! Rc просто использует ячейку, что означает, что он не является потокобезопасным. Arc использует атомарные объекты, что означает, что он является потокобезопасным. Естественно, вы не можете магически сделать тип потокобезопасным, просто поместив его в Arc. Arc может только наследовать потокобезопасность, как любой другой тип.
I really really really don't want to get into the finer details of atomic memory models or non-derived Send implementations. Needless to say, as you get deeper into Rust's thread-safety story, stuff gets more complicated. As a high-level consumer, it all just works and you don't really need to think about it.
Я очень-очень-очень не хочу углубляться в тонкости атомарных моделей памяти или не-унаследованной реализации Send. Излишне упоминать, что по мере погружения в историю потокобезопасности Rust, вещи становятся сложнее. Для пользователя высокого уровня всё это просто работает и вам на самом деле не надо об этом думать.
Final Code
Финальный код
That's all I really have to say on the immutable stack. We're getting pretty good at implementing lists now!
Это всё, что я реально хотел сказать об иммутабельном стеке. Мы уже неплохо освоили работу со списками!
#![allow(unused)] fn main() { 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: elem, next: self.head.clone(), }))} } 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) } pub fn iter(&self) -> Iter<'_, T> { Iter { next: self.head.as_deref() } } } impl<T> Drop for List<T> { fn drop(&mut self) { let mut head = self.head.take(); while let Some(node) = head { if let Ok(mut node) = Rc::try_unwrap(node) { head = node.next.take(); } else { break; } } } } 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 }) } } #[cfg(test)] mod test { use super::List; #[test] fn basics() { let list = List::new(); assert_eq!(list.head(), None); let list = list.prepend(1).prepend(2).prepend(3); assert_eq!(list.head(), Some(&3)); let list = list.tail(); assert_eq!(list.head(), Some(&2)); let list = list.tail(); assert_eq!(list.head(), Some(&1)); let list = list.tail(); assert_eq!(list.head(), None); // Make sure empty tail works let list = list.tail(); assert_eq!(list.head(), None); } #[test] fn iter() { let list = List::new().prepend(1).prepend(2).prepend(3); let mut iter = list.iter(); assert_eq!(iter.next(), Some(&3)); assert_eq!(iter.next(), Some(&2)); assert_eq!(iter.next(), Some(&1)); } } }
A Bad but Safe Doubly-Linked Deque
Плохой, но безопасный двусвязный дек
Now that we've seen Rc and heard about interior mutability, this gives an interesting thought... maybe we can mutate through an Rc. And if that's the case, maybe we can implement a doubly-linked list totally safely!
Теперь, когда мы познакомились с Rc и с внутренней изменчивостью, появляется интересная мысль... может быть мы можем изменять объекты с помощью Rc. И если это так, может быть мы можем сделать двусвязный список совершенно безопасным!
In the process we'll become familiar with interior mutability, and probably learn the hard way that safe doesn't mean correct. Doubly-linked lists are hard, and I always make a mistake somewhere.
В процессе мы познакомимся с внутренней изменчивостью и, возможно, на горьком опыте убедимся, что безопасность не означает корректность.
Let's add a new file called
fourth.rs:
Создадим новый файл fourth.rs:
// in lib.rs
// и lib.rs
pub mod first;
pub mod second;
pub mod third;
pub mod fourth;This will be another clean-room operation, though as usual we'll probably find some logic that applies verbatim again.
В этот раз нам снова предстоит начать работу с чистым файлом, хотя, как обычно мы, возможно найдём какую-то логику, которую сможем перенести без изменений.
Disclaimer: this chapter is basically a demonstration that this is a very bad idea.
Предупреждение: эта глава, по сути, демонстрирует, что у нас возникла очень плохая идея.
Layout
Представление данных
The key to our design is the
RefCelltype. The heart of RefCell is a pair of methods:
Ключевым элементом нашей архитектуры является тип RefCell.
Сердцем RefCell является пара методов:
fn borrow(&self) -> Ref<'_, T>;
fn borrow_mut(&self) -> RefMut<'_, T>;The rules for
borrowandborrow_mutare exactly those of&and&mut: you can call borrowas many times as you want, butborrow_mut` requires exclusivity.
Правила для borrow и borrow_mut точно такие же, как и для & и &mut: вы можете вызвать borrow столько раз, сколько захотите, но borrow_mut требует эксклюзивности.
Rather than enforcing this statically, RefCell enforces them at runtime. If you break the rules, RefCell will just panic and crash the program. Why does it return these Ref and RefMut things? Well, they basically behave like
Rcs but for borrowing. They also keep the RefCell borrowed until they go out of scope. We'll get to that later.
Вместо статической проверки RefCell проверяет их во время выполнения.
Если вы нарушаете правила, RefCell вызовет panic! и завершит программу.
Для чего она возвращает эти объекты Ref и RefMut?
Ну, они по сути ведёт себя как Rc, но только по отношению к заимствованию.
Они также оставляют заимстованным сам объект RefCell, пока не выйдут из области видимости.
Позже мы обсудим этот момент.
Now with Rc and RefCell we can become... an incredibly verbose pervasively mutable garbage collected language that can't collect cycles! Y-yaaaaay...
Теперь, имея на руках Rc и RefCell, мы можем сделать из Rust... невероятно многословным, полностью изменяемым языком со сборкой мусора, который не умеет собирать циклические ссылки! О-фи-геть!
Alright, we want to be doubly-linked. This means each node has a pointer to the previous and next node. Also, the list itself has a pointer to the first and last node. This gives us fast insertion and removal on both ends of the list.
Ладно, нам нужна двусвязность. Это значит, в каждом узле хранится указатель на следующий и предыдущий узел. Также, у самого списка есть указатели на первый и последний узел. Это даёт нам быструю вставку и удаление на обоих концах списка.
So we probably want something like:
Так что, возможно, мы хотим что-то такое:
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>,
| ^^^^^^^^^^^^^
Hey, it built! Lots of dead code warnings, but it built! Let's try to use it.
Ого, оно собралось! Много предупреждений о неиспользуемых переменных, но оно собралось! Давайте попробуем его использовать.
Building Up
Собираем
Alright, we'll start with building the list. That's pretty straight-forward with this new system.
newis still trivial, just None out all the fields. Also because it's getting a bit unwieldy, let's break out a Node constructor too:
Ладно, начнём с построения списка.
С нашей новой системой это довольно просто.
Метод 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
**A BUNCH OF DEAD CODE WARNINGS BUT IT BUILT**
Yay!
Ура!
Now let's try to write pushing onto the front of the list. Because doubly-linked lists are significantly more complicated, we're going to need to do a fair bit more work. Where singly-linked list operations could be reduced to an easy one-liner, doubly-linked list ops are fairly complicated.
Теперь давайте попытаемся написать вставку в начало списка. Поскольку двусвязные списки существенно сложнее, нам предстоит довольно много работы. Там, где операции с односвязным списком могут быть сокращены до простой однострочной функции, операции с двусвязным списком гораздо сложнее.
In particular we now need to specially handle some boundary cases around empty lists. Most operations will only touch the
headortailpointer. However when transitioning to or from the empty list, we need to edit both at once.
В частности, теперь нам надо особым образом обрабатывать некоторые граничные условия, связанные с пустыми списками.
Большинство операций затрагивают только указатели head или tail.
Однако при переходе к пустому списку и обратно, нам надо редактировать оба одновременно.
An easy way for us to validate if our methods make sense is if we maintain the following invariant: each node should have exactly two pointers to it. Each node in the middle of the list is pointed at by its predecessor and successor, while the nodes on the ends are pointed to by the list itself.
Простой способ убедиться в корректности наших методов — сохранять следующий инвариант: на каждый узел должено быть ровно два указателя. На каждый узел в седине списока указывают предшествующий ему и следующий за ним, в то время как на узлы на концах указывают поля списка.
Let's take a crack at it:
Давайте попробуем: <!-- take a crack -- пробовать, пытаться -->
pub fn push_front(&mut self, elem: T) {
// new node needs +2 links, everything else should be +0
// новому узлы нужны +2 ссылки, любому другому +0
let new_head = Node::new(elem);
match self.head.take() {
Some(old_head) => {
// non-empty list, need to connect the 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
// total: +2 new_head, +0 old_head -- OK!
// всего: +2 new_head, +0 old_head -- правильно!
}
None => {
// empty list, need to set the tail
// пустой список, надо установить значение tail
self.tail = Some(new_head.clone()); // +1 new_head
self.head = Some(new_head); // +1 new_head
// total: +2 new_head -- OK!
// всего: +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
Alright. Compiler error. Good start. Good start.
Что ж. Ошибка компилятора. Хорошее начало. Хорошее начало.
Why can't we access the
prevandnextfields on our nodes? It worked before when we just had anRc<Node>. Seems like theRefCellis getting in the way.
Почему нам недоступны поля prev и next в наших узлах?
Раньше это работало, потому что нас был Rc<Node>.
Похоже, проблемы возникают из-за RefCell.
We should probably check the docs.
Кажется, нам следует проверить доки.
Google's "rust refcell"
Гуглим "rust refcell"
A mutable memory location with dynamically checked borrow rules
See the module-level documentation for more.
Работа с изменяймой памятью с динамической проверкой правил заимствования
См. документацию на модуль for more.
clicks link
щёлкает по ссылке
Shareable mutable containers.
Values of the
Cell<T>andRefCell<T>types may be mutated through shared references (i.e. the common&Ttype), whereas most Rust types can only be mutated through unique (&mut T) references. We say thatCell<T>andRefCell<T>provide 'interior mutability', in contrast with typical Rust types that exhibit 'inherited mutability'.Cell types come in two flavors:
Cell<T>andRefCell<T>.Cell<T>providesgetandsetmethods that change the interior value with a single method call.Cell<T>though is only compatible with types that implementCopy. For other types, one must use theRefCell<T>type, acquiring a write lock before mutating.
RefCell<T>uses Rust's lifetimes to implement 'dynamic borrowing', a process whereby one can claim temporary, exclusive, mutable access to the inner value. Borrows forRefCell<T>s are tracked 'at runtime', unlike Rust's native reference types which are entirely tracked statically, at compile time. BecauseRefCell<T>borrows are dynamic it is possible to attempt to borrow a value that is already mutably borrowed; when this happens it results in thread panic.When to choose interior mutability
The more common inherited mutability, where one must have unique access to mutate a value, is one of the key language elements that enables Rust to reason strongly about pointer aliasing, statically preventing crash bugs. Because of that, inherited mutability is preferred, and interior mutability is something of a last resort. Since cell types enable mutation where it would otherwise be disallowed though, there are occasions when interior mutability might be appropriate, or even must be used, e.g.
- Introducing inherited mutability roots to shared types.
- Implementation details of logically-immutable methods.
- Mutating implementations of
Clone.Introducing inherited mutability roots to shared types
Shared smart pointer types, including
Rc<T>andArc<T>, provide containers that can be cloned and shared between multiple parties. Because the contained values may be multiply-aliased, they can only be borrowed as shared references, not mutable references. Without cells it would be impossible to mutate data inside of shared boxes at all!It's very common then to put a
RefCell<T>inside shared pointer types to reintroduce mutability: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); }Note that this example uses
Rc<T>and notArc<T>.RefCell<T>s are for single-threaded scenarios. Consider usingMutex<T>if you need shared mutability in a multi-threaded situation.
Разделяемые изменяемые контейнеры
Значения типов
Cell<T>иRefCell<T>могут быть изменены через разделяемые ссылки (т. е., в целом, через&Tтип), в то время как большинство типов Rust могут быть изменены через уникальные (&mut T) ссылки. Мы говорим, чтоCell<T>иRefCell<T>обеспечивают «внутреннюю изменяемость», в то время как обычные типы <!-- типичные типы -- масло маслянное --> Rust демонстрируют «унаследованную изменямость».Типы-ячейки бывают двух видов:
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>, если вам нужна разделяемая изменчивость в многопоточном окружении.
Hey, Rust's docs continue to be incredibly awesome.
Эй, дока по Rust всё ещё невероятно крута.
The meaty bit we care about is this line:
Больше всего в приведённом коде нас интересует вот эта строка:
shared_map.borrow_mut().insert("africa", 92388);In particular, the
borrow_mutthing. Seems we need to explicitly borrow a RefCell. The.operator's not going to do it for us. Weird. Let's try:
А конкретно — вызов 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
Hey, it built! Docs win again.
Эй, получилось! Доки снова победили.
Breaking Down
Разбираем
pop_frontshould be the same basic logic aspush_front, but backwards. Let's try:
У pop_front должна быть та же самая базовая логика, что и у push_front, только обращённая.
pub fn pop_front(&mut self) -> Option<T> {
// need to take the old head, ensuring it's -2
// надо получить старую голову, убедимся, что количество ссылок -2
self.head.take().map(|old_head| { // -1 old старая
match old_head.borrow_mut().next.take() {
Some(new_head) => { // -1 new новая
// not emptying list
// не пустой список
new_head.borrow_mut().prev.take(); // -1 old старая
self.head = Some(new_head); // +1 new новая
// total: -2 old, +0 new
// всего: -2 старыъ, +0 новых
}
None => {
// emptying list
// пустой список
self.tail.take(); // -1 old
// total: -2 old, (no new)
// всего: -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
ACK. RefCells. Gotta
borrow_mutagain I guess...
ТАК.
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
sigh
вздох
cannot move out of borrowed content
не могу извлечь заимствованное содержимое
Hrm... It seems that Box was really spoiling us.
borrow_mutonly gets us an&mut Node<T>, but we can't move out of that!
Грм...
Похоже, Box нас в действительности баловал.
borrow_num возращает нам только &mut Nude<T>, но мы не можем ничего оттуда извлечь!
We need something that takes a
RefCell<T>and gives us aT. Let's check the docs for something like that:
Нам нужно что-то, что возьмёт у нас RefCell<T> и вернёт нам T.
Давайте проверим доки на предмет наличия чего-то подобного:
fn into_inner(self) -> TConsumes the RefCell, returning the wrapped value.
fn into_inner(self) -> TПолучает RefCell, возвращает завёрнутое значение.
That looks promising!
Выглядит многообещающе!
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`
Ah dang.
into_innerwants to move out the RefCell, but we can't, because it's in anRc. As we saw in the previous chapter,Rc<T>only lets us get shared references into its internals. That makes sense, because that's the whole point of reference counted pointers: they're shared!
Вот блин.
into_inner хочет извлечь RefCell, но мы не можем её предоставить, потому что она находится в Rc.
Как мы видели в предыдущей главе, Rc<T> разрешает нам только разделяемую ссылку на свои внутренности.
И это правильно, потому что главный смысл указателей с подсчётом ссылок в том, что они разделяемые!
This was a problem for us when we wanted to implement Drop for our reference counted list, and the solution is the same:
Rc::try_unwrap, which moves out the contents of an Rc if its refcount is 1.
Это стало для нас проблемой, когда мы хотели реализовать Drop для нашего списка с подсчётом ссылок, и решение не изменилось: Rc::try_unwrap, который возвращает содержимое Rc, если счётчик ссылок равен 1.
Rc::try_unwrap(old_head).unwrap().into_inner().elem
Rc::try_unwrapreturns aResult<T, Rc<T>>. Results are basically a generalizedOption, where theNonecase has data associated with it. In this case, theRcyou tried to unwrap. Since we don't care about the case where it fails (if we wrote our program correctly, it has to succeed), we just callunwrapon it.
Rc::try_unwrap возвращает Result<T, Rc<T>>.
Значения типа Result — расширенный тип Option в котором у варианта None появляются связанные с ним данные.
В нашем случае — Rc, из которого мы пытаемся достать значение.
Поскольку нас не беспокоят возможные ошибки (если мы правильно написали программу, она обязана успешно завершиться), мы просто вызываем unwrap.
Anyway, let's see what compiler error we get next (let's face it, there's going to be one).
В любом случае, давайте посмотрим, когда ошибка компиляции возникнет на этот раз (и давайте будем честными — она обязательно возникнет).
> 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`
UGH.
unwrapon Result requires that you can debug-print the error case.RefCell<T>only implementsDebugifTdoes.Nodedoesn't implement Debug.
Да что ты будешь делать?
unwrap у Result требует, чтобы тип ошибки мог напечатать себя в отладочном режиме.
А RefCell<T> реализует Debug только тогда, когда его реализует T.
А Node не реализует Debug.
Rather than doing that, let's just work around it by converting the Result to an Option with
ok:
Вместо того, чтобы сделать это, давайте просто обойдём это, преобразовав Result в Options с помощью вызова ok:
Rc::try_unwrap(old_head).ok().unwrap().into_inner().elemPLEASE.
НУ, ПОЖАЛУЙСТА.
cargo build
YES.
ДА.
phew
уф
We did it.
У нас получилось.
We implemented
pushandpop.
Мы реализовали push и pop.
Let's test by stealing the old
stackbasic test (because that's all that we've implemented so far):
Давайте потестируем с помощю нашего базового теста старого стека (поэтому он единственный, который мы на данный момент написали):
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop_front(), None);
// Populate list
list.push_front(1);
list.push_front(2);
list.push_front(3);
// Check normal removal
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_front(4);
list.push_front(5);
// Check normal removal
assert_eq!(list.pop_front(), Some(5));
assert_eq!(list.pop_front(), Some(4));
// Check exhaustion
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
Nailed it.
В яблочко.
Now that we can properly remove things from the list, we can implement Drop. Drop is a little more conceptually interesting this time around. Where previously we bothered to implement Drop for our stacks just to avoid unbounded recursion, now we need to implement Drop to get anything to happen at all.
Теперь, когда мы можем корректно удалять элементы из списка, мы можем реализовать и типаж Drop. На этот раз Drop чуть более интересен с концептуальной точки зрения. В то время, как раньше мы реализовывали Drop для наших стеков просто чтобы избавиться от неограниченной рекурсии, сейчас нам надо реализовать Drop, чтобы хоть-нибудь вообще работало.
Rccan't deal with cycles. If there's a cycle, everything will keep everything else alive. A doubly-linked list, as it turns out, is just a big chain of tiny cycles! So when we drop our list, the two end nodes will have their refcounts decremented down to 1... and then nothing else will happen. Well, if our list contains exactly one node we're good to go. But ideally a list should work right if it contains multiple elements. Maybe that's just me.
Rc не умеет работать с циклами.
Если есть цикл, все объекты поддерживают существование друг друга.
Двусвязный список, как выяснилось, всег лишь большая цепочка крошечных циклов!
Так что когда мы уничтожает наш список, два конечных узла уменьшают свои счётчики до 1... а затем ничего не происходит.
Ладно, если наш список содержит точно один узел, можно оставить всё, как есть.
Но в идеалее, список должен корректно работать, если в нём множество элементов.
Возможно, это только моё мнение.
As we saw, removing elements was a bit painful. So the easiest thing for us todo is just
popuntil we get None:
Как мы видели, удаление элементов было довольно болезненным.
Поэтому простейший способ для нас — просто вызывать pop, пока мы не получим None:
impl<T> Drop for List<T> {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}cargo build
(We actually could have done this with our mutable stacks, but shortcuts are for people who understand things!)
(На самом деле мы могли бы сделать это с помощью наших изменяемых стеков, но короткий путь только для тех, кто знает, куда идти!)
We could look at implementing the
_backversions ofpushandpop, but they're just copy-paste jobs which we'll defer to later in the chapter. For now let's look at more interesting things!
Мы могли бы взглянуть на реализацию _back версий методов push и pop, но это всего лишь копи-паста, к которым мы вернёмся позже в этой главе.
А сейчас давайте посмотрим на более интересные вещи!
Peeking
Метод Peek
Alright, we made it through
pushandpop. I'm not gonna lie, it got a bit emotional there. Compile-time correctness is a hell of a drug.
Хорошо, мы справились с методами push и pop.
Не буду врать, я немного разволновалась.
Проверка правильности на этапе компиляции — охнеренное чувство.
Let's cool off by doing something simple: let's just implement
peek_front. That was always really easy before. Gotta still be easy, right?
Надо немнго успокоиться и сделать что-нибудь простое: скажем, реализовать peek_front.
Это то, что всегда было простым раньше.
Должно и остаться простым, правда?
Right?
Правда?
In fact, I think I can just copy-paste it!
Фактически, я уверена, что могу просто скопи-пастить старое решение!
pub fn peek_front(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
&node.elem
})
}Wait. Not this time.
Подождите. Не в этот раз.
pub fn peek_front(&self) -> Option<&T> {
self.head.as_ref().map(|node| {
// BORROW!!!!
&node.borrow().elem
})
}HAH.
ХА.
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
Ok I'm just burning my computer.
Ладно, просто сожгу свой компьютер.
This is exactly the same logic as our singly-linked stack. Why are things different. WHY.
Здесь та же самая логика, что и в нашем односвязном стеке. Почему всё по другому? ПОЧЕМУ.
The answer is really the whole moral of this chapter: RefCells make everything sadness. Up until now, RefCells have just been a nuisance. Now they're going to become a nightmare.
Ответ на самом деле представляет мораль всей этой главы: RefCell делает всё грустным. До текущего момента RefCell просто доставлял неудобства. Теперь он стал ночным кошмаром.
So what's going on? To understand that, we need to go back to the definition of
borrow:
Так что случилось?
Чтобы в этом разобраться, нам надо вернуться к определению borrow:
fn borrow<'a>(&'a self) -> Ref<'a, T>
fn borrow_mut<'a>(&'a self) -> RefMut<'a, T>In the layout section we said:
В разделе о представлении мы говорили:
Rather than enforcing this statically, RefCell enforces them at runtime. If you break the rules, RefCell will just panic and crash the program. Why does it return these Ref and RefMut things? Well, they basically behave like
Rcs but for borrowing. Also they keep the RefCell borrowed until they go out of scope. We'll get to that later.
It's later.
Это «позже» настало.
RefandRefMutimplementDerefandDerefMutrespectively. So for most intents and purposes they behave exactly like&Tand&mut T. However, because of how those traits work, the reference that's returned is connected to the lifetime of the Ref, and not the actual RefCell. This means that the Ref has to be sitting around as long as we keep the reference around.
Ref и RefMut реализуют Deref и DerefMut соответственно.
Так что в большинстве случаев они ведут себя точно так же как &T и &mut T.
Однако из-за особенностей работы этих типажей, возвращаемая ссылка связана с временем жизни Ref, а не с самой ячейкой RefCell.
Это значит, что Ref должна оставаться доступна до тех пор, пока мы её используем.
This is in fact necessary for correctness. When a Ref gets dropped, it tells the RefCell that it's not borrowed anymore. So if we did manage to hold onto our reference longer than the Ref existed, we could get a RefMut while a reference was kicking around and totally break Rust's type system in half.
Это нужно, чтобы сохранить корректность. Когда Ref уничтожается, он сообщает RefCell, что больше не заимствуется. Таким образом если бы нам удалось сохранить нашу ссылку дольше, чем существовала Ref, мы бы могли получить RefMut, в то время, как ссылка где-то слоняется и полностью сломали бы надвое систему типов Rust.
So where does that leave us? We only want to return a reference, but we need to keep this Ref thing around. But as soon as we return the reference from
peek, the function is over and theRefgoes out of scope.
Итак, что нам остаётся?
Мы всего лишь хотим вернуть ссылку, но для этого мы должны сохранить Ref.
Но как только мы возвращаем ссылку из peek, функция завершается из Ref выходит из области видимости.
😖
As far as I know, we're actually totally dead in the water here. You can't totally encapsulate the use of RefCells like that.
Насколько я понимаю, сейчас мы полностью оказались в тупике. Вы не можете полностью инкапсулировать использование RefCell подобным образом.
But... what if we just give up on totally hiding our implementation details? What if we returns Refs?
Но... что если мы откажемся от идеи полностью скрывать детали реализации? Что если мы будуем возвращать 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;
|
Blurp. Gotta import some stuff.
Бла, бла, бла. Надо кое-что импортировать.
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>>>`
Hmm... that's right. We have a
Ref<Node<T>>, but we want aRef<T>. We could abandon all hope of encapsulation and just return that. We could also make things even more complicated and wrapRef<Node<T>>in a new type to only expose access to an&T.
Хмм... всё правильно.
У нас есть Ref<Node<T>>, но нам нужен Ref<T>.
Мы могли бы отказаться от всякой надежды на инкапсуляцию и просто возвращать его.
Мы могли бы ещё больше усложнить код и завернуть Ref<Node<T>> в новый тип, чтобы предоставлять доступ только к &T.
Both of those options are kinda lame.
Оба варианта как бы увечные.
Instead, we're going to go deeper down. Let's have some fun. Our source of fun is this beast:
Вместо этого, углубимся в тему. Давайте немного повеселимся. Источник нашего веселья — вот это чудовище:
map<U, F>(orig: Ref<'b, T>, f: F) -> Ref<'b, U>
where F: FnOnce(&T) -> &U,
U: ?SizedMake a new Ref for a component of the borrowed data.
Создаёт новую Ref для компонента заимствованных данных.
Yes: just like you can map over an Option, you can map over a Ref.
Да: точно также, как вы можете вызывать map для Option, вы можете вызывать map для Ref.
I'm sure someone somewhere is really excited because monads or whatever but I don't care about any of that. Also I don't think it's a proper monad since there's no None-like case, but I digress.
Я уверена, что кто-то где-то действительно возбудился из-за монад или чего-то подобного, но меня они совершенно не волнуют. К тому же я не думаю, что это настоящая монада, поскольку нет варианта, похожего на None, но я отвлеклась.
It's cool and that's all that matters to me. I need this.
Это круто, и это всё, что имеет для меня значение. Мне это нужно.
pub fn peek_front(&self) -> Option<Ref<T>> {
self.head.as_ref().map(|node| {
Ref::map(node.borrow(), |node| &node.elem)
})
}> cargo build
Awww yissss
Да-да-да-да.
Let's make sure this is working by munging up the test from our stack. We need to do some munging to deal with the fact that Refs don't implement comparisons.
Давайте убедимся, что это работает, немного изменив тест, написанный для нашего стека. Нам нужно кое-что добавить, чтобы справиться с тем фактом, что 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
Great!
Великолепно!
Symmetric Junk
Симметричный мусор
Alright let's get all that combinatoric symmetry over with.
Что ж, давайте разберёмся со всей этой комбинаторной симметрией.
All we have to do is some basic text replacement:
Всё, что нам нужно, это выполнить простую замену текста:
tail <-> head
next <-> prev
front -> back
Oh, also we need to add
_mutvariants for peeking.
О, нам также надо написать варианты _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)
})
}And massively flesh out our tests:
И значительно расширить наши тесты:
#[test]
fn basics() {
let mut list = List::new();
// Check empty list behaves right
assert_eq!(list.pop_front(), None);
// Populate list
list.push_front(1);
list.push_front(2);
list.push_front(3);
// Check normal removal
assert_eq!(list.pop_front(), Some(3));
assert_eq!(list.pop_front(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_front(4);
list.push_front(5);
// Check normal removal
assert_eq!(list.pop_front(), Some(5));
assert_eq!(list.pop_front(), Some(4));
// Check exhaustion
assert_eq!(list.pop_front(), Some(1));
assert_eq!(list.pop_front(), None);
// ---- back -----
// Check empty list behaves right
assert_eq!(list.pop_back(), None);
// Populate list
list.push_back(1);
list.push_back(2);
list.push_back(3);
// Check normal removal
assert_eq!(list.pop_back(), Some(3));
assert_eq!(list.pop_back(), Some(2));
// Push some more just to make sure nothing's corrupted
list.push_back(4);
list.push_back(5);
// Check normal removal
assert_eq!(list.pop_back(), Some(5));
assert_eq!(list.pop_back(), Some(4));
// Check exhaustion
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);
}Are there some cases we're not testing? Probably. The combinatoric space has really blown up here. Our code is at very least not obviously wrong.
Есть ли сценарии, которые мы не протестировали? Возможно. Комбинаторное пространство действительно здесь разрослось.
По крайней мере, наш код не явно ошибочный.
> 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
Nice. Copy-pasting is the best kind of programming.
Прекрасно. Копи-паста — лучший способ программирования.
Iteration
Итерация
Let's take a crack at iterating this bad-boy.
Давайте попробуем написать итераторы для этого плохого парня.
IntoIter
IntoIter
IntoIter, as always, is going to be the easiest. Just wrap the stack and call
pop:
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()
}
}But we have an interesting new development. Where previously there was only ever one "natural" iteration order for our lists, a Deque is inherently bi-directional. What's so special about front-to-back? What if someone wants to iterate in the other direction?
Но у нас появилось новое интересное усовершенствование. В то время как раньше был только один «натуральный» порядок перебора для нашех списков, дек по своей природе двунаправленный. Что особенного в итерации от начала к коцу? Что если кому-то понадобится итерация в другом направлении?
Rust actually has an answer to this:
DoubleEndedIterator. DoubleEndedIterator inherits from Iterator (meaning all DoubleEndedIterator are Iterators) and requires one new method:next_back. It has the exact same signature asnext, but it's supposed to yield elements from the other end. The semantics of DoubleEndedIterator are super convenient for us: the iterator becomes a deque. You can consume elements from the front and back until the two ends converge, at which point the iterator is empty.
На самом деле в Rust есть ответ на этот вопрос: DoubleEndedIterator.
DoubleEndedIterator наследует Iterator (это значит, что все объекты, реализующие DoubleEndedIterator реализуют так же и Iterator) и добавляет один новый метод: next_back.
У него такая же сигнатура, как и у next, но он перебирает элементы с другого конца.
Семантика DoubleEndedIterator очень удобная для нас: итератор становится деком.
Вы можете брать элементы как с начала, так и с конца, пока два конца не встретятся и в этой точке итератор станет пустым.
Much like Iterator and
next, it turns out thatnext_backisn't really something consumers of the DoubleEndedIterator really care about. Rather, the best part of this interface is that it exposes therevmethod, which wraps up the iterator to make a new one that yields the elements in reverse order. The semantics of this are fairly straight-forward: calls tonexton the reversed iterator are just calls tonext_back.
Как и в случае с Iterator и next, оказывается, что next_back — это не то, что на самом деле важно пользователям DoubleEndedIterator.
Скорее, лучшая часть интерфейса — предоставление метода rev, которые заворачивает итератор для того, чтобы сделать другой итератор, который возвращает элементы в обратном порядке.
Семантика здесь довольно проста: вызов next у обращённого итератора — это на самом деле вызов next_back.
Anyway, because we're already a deque providing this API is pretty easy:
В любом случае, поскольку у нас уже есть дек, предоставить новый API довольно просто:
impl<T> DoubleEndedIterator for IntoIter<T> {
fn next_back(&mut self) -> Option<T> {
self.0.pop_back()
}
}And let's test it out:
И давайте протестируем:
#[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
Nice.
Прекрасно.
Iter
Iter
Iter will be a bit less forgiving. We'll have to deal with those awful
Refthings again! Because of Refs, we can't store&Nodes like we did before. Instead, let's try to storeRef<Node>s:
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
So far so good. Implementing
nextis going to be a bit hairy, but I think it's the same basic logic as the old stack IterMut but with extra RefCell madness:
Пока всё хорошо.
Реализация 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
Shoot.
Началось! <!-- вариант Пристретие меня, кто нибудь. >
node_refdoesn't live long enough. Unlike normal references, Rust doesn't let us just split Refs up like that. The Ref we get out ofhead.borrow()is only allowed to live as long asnode_ref, but we end up trashing that in ourRef::mapcall.
node_ref живёт недостаточно долго.
В отличие от нормальных ссылок, Rust не позвоялет нам просто разделить Ref подобным образом.
Ref, который мы получили из head.borrow(), может существовать только до тех пор, пока существует node_ref, но в итоге уничтожаем её при вызове Ref::map.
The function we want exists, and it's called [map_split][]:
Функциая, которая нам нужна, существует, и она называется [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,Woof. Let's give it a try...
Уф. Давайте попробуем.
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
Ergh. We need to
Ref::Mapagain to get our lifetimes right. ButRef::Mapreturns aRefand we need anOption<Ref>, but we need to go through the Ref to map over our Option...
Рррр.
Нам снова нужен Ref::map чтобы у нас было правильное время жизни.
Но Ref::map возвращает Ref, а нам нужен Option<ref>, но для этого нам надо пройти сквозь Ref, чтобы вызвать map для нашего Option...
stares into distance for a long time
долго смотрит вдаль
??????
??????
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<_>>>`
Oh. Right. There's multiple RefCells. The deeper we walk into the list, the more nested we become under each RefCell. We would need to maintain, like, a stack of Refs to represent all the outstanding loans we're holding, because if we stop looking at an element we need to decrement the borrow-count on every RefCell that comes before it.................
О. Правильно. Есть несколько RefCell. Чем дальше мы углубляемся в список, тем более вложенными становяся RefCell. Нам потребуется поддерживать что-то вроде стека Ref для представления всех объектов, на которые мы ссылаемся, потому что если мы перестаём наблидать за элементом, нам надо снизить на единицу счётчкик заимствований у кажого RefCell, который находится перед ним...
I don't think there's anything we can do here. It's a dead end. Let's try getting out of the RefCells.
Кажется, мы ничего не можем здесь сделать. Это тупик. Давайте выбираться из всех этих RefCell.
What about our
Rcs. Who said we even needed to store references? Why can't we just Clone the whole Rc to get a nice owning handle into the middle of the list?
Что насчёт наших 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 =Uh... Wait what do we return now?
&T?Ref<T>?
Э-э-э...
Подождите, а что мы теперь возвращаем?
&T?
Ref<T>?
No, none of those work... our Iter doesn't have a lifetime anymore! Both
&TandRef<T>require us to declare some lifetime up front before we get intonext. But anything we manage to get out of our Rc would be borrowing the Iterator... brain... hurt... aaaaaahhhhhh
Нет, ни один из них не работает... у нашего Iter в любом случае нет времени жизни!
И &T, и Ref<T> требуют объявления какого-то времени жизни перед тем, как мы сможем вызвать next.
Но всё, что мы сможем получить из нашего Rc будет заимстованием Iterator... мозг... болит... аааааааааааа!
Maybe we can... map... the Rc... to get an
Rc<T>? Is that a thing? Rc's docs don't seem to have anything like that. Actually someone made a crate that lets you do that.
Может быть, мы можем... вызвать map... для Rc... чтобы получить Rc<T>?
Так вообще бывает?
В доках Rc, похоже, ничего подобного нет.
На самом деле, кто сделал крейт, который позволяет это сделать.
But wait, even if we do that then we've got an even bigger problem: the dreaded spectre of iterator invalidation. Previously we've been totally immune to iterator invalidation, because the Iter borrowed the list, leaving it totally immutable. However if our Iter was yielding Rcs, they wouldn't borrow the list at all! That means people can start calling
pushandpopon the list while they hold pointers into it!
Но похождите, даже если мы это сделаем, у нас появится ещё большая проблема: ужасная угроза инвалидации итератора.
Раньше мы не сталкивались с инвалидацией итератора, потому что Iter заимствовал список, оставляя его в целом неизменяемым.
Однако, если бы наш итератор возвращал Rc, ему вообще бы не пришлось заимствовать список!
Это значит, что люди могут начать вызывать push и pop у списка, пока они хранят указатели на него.
Oh lord, what will that do?!
О, боже, что из этого получится?
Well, pushing is actually fine. We've got a view into some sub-range of the list, and the list will just grow beyond our sights. No biggie.
Ну, в принципе, с push всё в порядке.
Мы видим какую-то часть списка и список будет расти за пределами поля нашего зрения.
Ничего страшного.
However
popis another story. If they're popping elements outside of our range, it should still be fine. We can't see those nodes so nothing will happen. However if they try to pop off the node we're pointing at... everything will blow up! In particular when they go tounwrapthe result of thetry_unwrap, it will actually fail, and the whole program will panic.
Однако, с pop ситуация другая.
Если элементы извлекаются за пределами поля нашего зрения, это всё ещё должно быть нормально.
Мы не можем видеть эти узлы, так что ничего случиться не может.
В то же время если попытаться извлечь узел, на который мы указываем... всё взорвётся!
В частности, если вызвать unwrap у результата, полученного с помощью try_unwrap, это на самом деле приведёт к панике и программа аварийно завершится.
That's actually pretty cool. We can get tons of interior owning pointers into the list and mutate it at the same time and it will just work until they try to remove the nodes that we're pointing at. And even then we don't get dangling pointers or anything, the program will deterministically panic!
Это действительно здорово. Мы можем добавлять в список тонны указателей с внутренним владением и одновременно менять их и это будет просто работать, если не удалять узла, на которые мы указываем.
И даже тогда у нас не возникнет висячих указателей или чего-то похожего: программа детерминированно запаникует!
But having to deal with iterator invalidation on top of mapping Rcs just seems... bad.
Rc<RefCell>has really truly finally failed us. Interestingly, we've experienced an inversion of the persistent stack case. Where the persistent stack struggled to ever reclaim ownership of the data but could get references all day every day, our list had no problem gaining ownership, but really struggled to loan our references.
Но необходимость иметь дело с инвалидацией итераторов в дополнение к вызовам map у Rc кажется просто... плохой.
Rc<RefCell> окончательно подвёл нас.
Интересно, мы столкнулись с инверсией случая с устойчивым стеком.
В то время как устойчивый стек не мог справиться с владением, но мог предоставлять ссылки днями напролёт, нас список не испытвает проблем с владением, не не может справиться с нашими ссылками.
Although to be fair, most of our struggles revolved around wanting to hide the implementation details and have a decent API. We could do everything fine if we wanted to just pass around Nodes all over the place.
Хотя, если быть честными, большая часть нашей борьбы вращалась вокруг желания спрятать детали реализации и иметь пристойный API. Мы могли бы сделать всё хорошо, если бы просто передавали везде узлы.
Heck, we could make multiple concurrent IterMuts that were runtime checked to not be mutable accessing the same element!
Блин, да мы могли бы сделать несколько конкурентных IterMuts, которые бы во время выполнения программы проверяли бы, что нет изменяемого доступа к одному и тому же элементу!
Really, this design is more appropriate for an internal data structure that never makes it out to consumers of the API. Interior mutability is great for writing safe applications. Not so much safe libraries.
На самом деле, такой дизайн больше подходит для внутренней структуры данных, которая никогда не попадает к пользователям API. Внутренняя изменчивость отлично подходит для написания безопасных приложений. Но не для безопасных библиотек.
Anyway, that's me giving up on Iter and IterMut. We could do them, but ugh.
В любом случае, я отказываюсь от реализации Iter и IterMut. Мы могли бы, но... получается некрасиво.
Final Code
Финальный код
Alright, so that's implementing a 100% safe doubly-linked list in Rust. It was a nightmare to implement, leaks implementation details, and doesn't support several fundamental operations.
Ладно, вот реализация 100% безопасного двусвязного списка на Rust. Реализация оказалась ночным кошмаром, список раскрывает детали реализации и не поддерживает ряд фундаментальных операций.
But, it exists.
Тем не менее, его можно реализовать.
Oh, I guess it's also riddled with tons of "unnecessary" runtime checks for correctness between
RcandRefCell. I put unnecessary in quotes because they're actually necessary to guarantee the whole actually being safe thing. We encountered a few places where those checks actually were necessary. Doubly-linked lists have a horribly tangled aliasing and ownership story!
Кстати, я думаю, что здесь слишком много «ненунжных» проверок между Rc и RefCell.
В взяла слово ненужных в кавычки, потому что на самом деле они необходимы для гарантий реальной безопасности.
У нас есть несколько мест, где эти проверки действительно необходимы.
Двусвязные списке имеют действительно запутанную историю псевдонимов и владения!
Still, it's a thing we can do. Especially if we don't care about exposing internal data structures to our consumers.
Тем не менее, вот то, что нам удалось сделать. Особенно если нас не страшит раскрытие дателей реализации нашим пользователям.
From here on out, we're going to be focusing on other side of this coin: getting back all the control by making our implementation unsafe.
Далее мы сосредоточимся на другой стороне медали: вернём себе контроль, сделав реализацию небезопасной.
#![allow(unused)] fn main() { 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(); // Check empty list behaves right assert_eq!(list.pop_front(), None); // Populate list list.push_front(1); list.push_front(2); list.push_front(3); // Check normal removal assert_eq!(list.pop_front(), Some(3)); assert_eq!(list.pop_front(), Some(2)); // Push some more just to make sure nothing's corrupted list.push_front(4); list.push_front(5); // Check normal removal assert_eq!(list.pop_front(), Some(5)); assert_eq!(list.pop_front(), Some(4)); // Check exhaustion assert_eq!(list.pop_front(), Some(1)); assert_eq!(list.pop_front(), None); // ---- back ----- // Check empty list behaves right assert_eq!(list.pop_back(), None); // Populate list list.push_back(1); list.push_back(2); list.push_back(3); // Check normal removal assert_eq!(list.pop_back(), Some(3)); assert_eq!(list.pop_back(), Some(2)); // Push some more just to make sure nothing's corrupted list.push_back(4); list.push_back(5); // Check normal removal assert_eq!(list.pop_back(), Some(5)); assert_eq!(list.pop_back(), Some(4)); // Check exhaustion 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); } } }