Наконец, мы добрались. Мой величайший враг: std::collections::LinkedList, двусвязный дек.
Который я безуспешно пыталась уничтожить.
Наша история начинается в 2014 году, когда мы стремительно приближались к выпуску Rust 1.0, первой стабильной версии Rust. Я была ответственна за std::collections или, как мы тогда называли эту библиотеку, libcollections.
Библиотека годами служила свалкой для интересных идей и мало-мальски полезных реализаций. Это было здорово, пока Rust оставался экспериментальным языком, но если мои дети собрались вырваться из гнезда и обрести свободу, им надо доказать свою состоятельность.
До той поры я поддерживала их всех, но пришло время для них предстать перед судом за их прегрешения.
Я вонзила когти в твердь и вырезала надгробные плиты для самых неразумных своих детей. Жуткий памятник, который я установила на городской площади, чтобы все могли его видеть:
Удалить TreeMap, TreeSet, TrieMap, TrieSet, LruCache и EnumSet
Их судьбы были предрешены, ибо моё слово было нерушимо. Другие коллекции были в ужасе от моей жестокости, но и они не были в безопасности от гнева своей матери. Вскоре я вернулась ещё с двумя надгробиями:
Объявить устаревшими BitSet и BitVec
Близнецы Bit оказались хитрее своих павших товарищей, но и им не хватило сил сбежать от меня. Большинство думало, что моя работа выполнена, но вскоре я поймала ещё одного:
VecMap пытался выжить, полагаясь на свою незаметность — он был таким маленьким и безобидным! Но этого оказалось недостаточно для libcollections, которую я рисовала в своём воображении.
Я оглянулась и увидела тех, кто остался:
Vec и VecDeque — простые и надёжные, сердце вычислений.
HashMap и HashSet — мощные и требующие знаний, мозг вычислений.
BTreeMap и BTreeSet — неуклюжие, но нужные, печень вычислений.
BinaryHeap — хитрая и ловкая, лодыжка вычислений.
Я удовлетворённо кивнула. Просто и эффективно. Моя работа подошла к концу.
Нет, DList, этого не может быть! Я думала, ты погиб в том трагическом инциденте со сборкой мусора! Единственный, кто появился случайно, а не вследствие какого-то намерения!
Он инсценировал свою смерть и взял себе новое имя, но это всё ещё был он: связный список, тёмный и ненадёжный интриган вычислений.
Я рассказывала о его злодеяниях всем, кто готов был слушать, но их сердца оставались непоколебимыми. Связный список оказался красноречивым дьяволом, который убедил всех вокруг, что является фундаментальной и естественной структурой данных. Он даже убедил C++, что был тем самым списком!
«Как стандартная библиотека может быть без связного списка?»
Легко! Тривиально!
«Это нетривиальный небезопасный код, поэтому вполне логично включить его в стандартную библиотеку!»
То же самое можно сказать про драйверы GPU и видео кодеки. Библиотека libcollections должна быть минималистична!
Увы, связный список обзавёлся слишком большим числом сторонников и стал слишком сильным, пока я занималась его братьями.
Я спряталась в своей лаборатории и попыталась создать некоего злого клона или продвинутого кибернетического репликанта, который мог бы соперничать с ним и уничтожить его, но мой грант приостановили, потому что мои исследования были признаны «очевидно кровожадными» или что-то в этом роде.
Связный список победил. Я потерпела поражение и отправилась в изгнание.
Но сейчас вы здесь. Вы проделали весь этот путь. И, конечно, сейчас вы понимаете всю глубину извращённости связного списка! Пойдёмте, я покажу вам всё, что нужно знать, чтобы помочь мне уничтожить его раз и навсегда. Всё, что нужно знать, чтобы реализовать небезопасный двусвязный дек продуктового уровня.
Действительно продуктового уровня? Ну, я собираюсь полностью переписать мой старую реализацию связного списка из Rust 1.0, ту самую, которая объективно лучше реализации из стандартной библиотеки. Ту, в которой были Курсоры, из стабильной версии Rust 2015 года! Ту, которой всё ещё нет в стандартной библиотеке 2022 года!
Представление
Давайте начнём с изучения структуры нашего врага. Двусвязный список концептуально прост, но именно так он обманывает вас и манипулирует вами. Это тот же связный список, с которым мы неоднократно сталкивались, но ссылки в нём идут в обе стороны. Двойные ссылки — двойное зло.
Так что вместо этого (для большей ясности прячу Some/None):
... -> (A, ptr) -> (B, ptr) -> ...
Мы получаем:
... <-> (ptr, A, ptr) <-> (ptr, B, ptr) <-> ...
Благодаря двойным ссылкам, обходить список можно в любом направлении, а также, с помощью курсора можно искать и вперёд, и назад.
Взамен на эту гибкость, каждый узел вынужден хранить в два раза больше указателей, и каждая операция требует изменения большего числа указателей. Это значимое усложнение, при котором гораздо проще допустить ошибку, так что нам придётся написать много дополнительных тестов.
Вы должно быть заметили, что я умышленно не писала о концах списка. Это потому, что концы — одно из тех мест, где есть действительно обоснованные способы реализации. Нам определённо нужно, чтобы у нас было указателя: один на начало списка, и один — на конец.
Есть два известных способа реализации: «традиционный» и «фиктивный узел».
Традиционный подход — простое расширение способа, который мы использовали для стека — просто хранить указатели на голову и хвост:
[ptr, ptr] <-> (ptr, A, ptr) <-> (ptr, B, ptr) ^ ^ +----------------------------------------+
Он работает, но у его есть обратная сторона — граничные случаи. А теперь в нашем списке два конца, что означает в два раза больше граничных случаев. Легко забыть об одном из них и получить серьёзную ошибку.
Подход с фиктивным узлом пытается сгладить граничные случаи путём добавления в наш список внешнего узла, в котором нет данных, а есть только ссылки на оба конца, что превращает структуру в кольцо:
[ptr] -> (ptr, ?DUMMY?, ptr) <-> (ptr, A, ptr) <-> (ptr, B, ptr) ^ ^ +-------------------------------------------------+
В такой реализации у каждого узла всегда есть действительные указатели на предыдущий и следующий узлы в списке. Даже когда вы удаляете последний элементы из списка, вы просто замыкаете фиктивный узел сам на себя:
[ptr] -> (ptr, ?DUMMY?, ptr) ^ ^ +-------------+
Есть часть меня, которая находит это решение вполне удовлетворительным и элегантным. К сожалению, у него есть пара практических проблем:
Проблема 1: Дополнительные уровень косвенности и выделение памяти, особенно для пустого списка, который должен включать фиктивный узел. Потенциальные решения включают:
Не создавать фиктивный узел до тех пор, пока в список не будет вставлен первый элемент: просто и эффективно, но это возвращает некоторые из граничных случаев, от которых мы пытались избавиться, используя фиктивные указатели!
Использовать статический одиночный фиктивный узел с копированием при записи и с каким-нибудь хитроумным методом, позволяющим совместить проверки Copy-On-Write с обычными проверками. Этот подход мне очень нравится, но мы не станем заниматься в этой книге тёмной магией. Читайте исходный код ThinVec, если хотите познакомиться с подобной странной реализацией.
Хранить фиктивный узел на стеке — не практично в языке, где не поддерживаются конструкторы перемещения (move constructors) из C++. Я уверена, что можно было бы придумать странное решение с закреплением (pin), но и этого мы делать не будем.
Проблема 2: Какое значение хранить в фиктивном узле? Ладно бы, речь шла о целом числе, но что если в нашем списке хранятся сплошь экземпляры Box? Мы бы не смогли инициализировать такое значение! Потенциальные решения включают:
Хранить в каждом узле
Option<T>: просто и эффективно, в то же время неэкономно и «по ощущениям» неправильно.Хранить в каждом узле
MaybeUninit<T>. Не только неправильно, но и ужасно.По настоящему осторожно и хитроумно, в стиле наследования, сделать так, чтобы фиктивный узел не хранил данных. Тоже заманчиво, но крайне опасно и неправильно. Читайте исходный код BTreeMap если хотите познакомиться с подобной странной реализацией.
Для такого языка, как Rust, проблемы действительно перевешивают удобство, так что мы будем придерживаться традиционного представления. Используем тот же базовый дизайн, что и в случае с небезопасной очередью из предыдущей главы:
pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, } type Link<T> = *mut Node<T>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, }
(Теперь, когда мы добрались до двусвязного дека, мы, наконец, заслужили право назвать структуру LinkedList, поскольку речь идёт об истинном связном списке.)
Это ещё не совсем представление настоящего продуктового уровня. Оно неплохое, но есть волшебные приёмы, которые помогают лучше объяснить Rust, что мы хотим сделать. Для этого нам придётся двигаться… глубже.
Вариантность и PhantomData
Будет неправильно откладывать эту часть на потом, так что мы прямо сейчас займёмся Хардкорным Представлением.
Есть пять ужасных всадников создания небезопасных коллекций в Rust:
Слава небесам, последние два не являются для нас проблемой.
Третий всадник мог бы стать проблемой, но овчинка не стоит выделки — если вы выбрали связный список, вы уже стократно проиграли битву за эффективное использование памяти.
Второго всадника я когда-то считала очень важным, поскольку стандартная библиотека применяет для дроп-чека разные трюки, но настройки по умолчанию безопасны, а способы их «подкрутить» — нестабильны. Вам надо очень постараться, чтобы заметить ограничения этих настроек, так что просто забудьте об этом.
Остаётся Вариантность. Честно говоря, на ней, наверное, тоже можно было не настаивать, но я всё ещё горжусь своей работой в качестве человека, разработавшего std::collections, так что мы всё-таки займёмся Этой Штукой.
Так вот, сюрприз: в Rust есть подтипы. В частности, &'big T — это подтип &'small T. (Прим. перевод.: время жизни big больше, чем время жизни small). Почему? Ну, потому что если какому-то коду нужна ссылка, живущая в течение определённого времени, вполне допустимо дать ему ссылку, которая живёт дольше. Интуитивно это же понятно, так?
Почему это важно? Представьте код, который получает два значения одного и того же типа:
fn take_two<T>(_val1: T, _val2: T) { }
Это поистине скучный код, поэтому мы ожидаем, что он будет работать при T=&u32, так?
fn two_refs<'big: 'small, 'small>( big: &'big u32, small: &'small u32, ) { take_two(big, small); } fn take_two<T>(_val1: T, _val2: T) { }
Да, без проблем компилируется!
А теперь давайте немного повеселимся и завернём его, ну, я не знаю, в std::cell::Cell:
use std::cell::Cell; fn two_refs<'big: 'small, 'small>( // ОБРАТИТЕ ВНИМАНИЕ: эти две строки изменились big: Cell<&'big u32>, small: Cell<&'small u32>, ) { take_two(big, small); } fn take_two<T>(_val1: T, _val2: T) { }
error[E0623]: lifetime mismatch --> src/main.rs:7:19 | 4 | big: Cell<&'big u32>, | --------- 5 | small: Cell<&'small u32>, | ----------- these two types are declared with different lifetimes... 6 | ) { 7 | take_two(big, small); | ^^^^^ ...but data from `small` flows into `big` here
Что??? Мы не трогали время жизни, почему компилятор стал ругаться?
Хорошо, штука со временем жизни «подтипов» должна быть очень простой, поэтому она даёт сбой, если завернуть ссылки во что-то ещё. Смотрите, она ломается и с Vec:
fn two_refs<'big: 'small, 'small>( big: Vec<&'big u32>, small: Vec<&'small u32>, ) { take_two(big, small); } fn take_two<T>(_val1: T, _val2: T) { }
Finished dev [unoptimized + debuginfo] target(s) in 1.07s Running `target/debug/playground`
Видите, этот код тоже не компилиру… — подождите, что??? Vec что, магический???
Ну, да. Но, и в то же время — нет. Эта магия всегда была с нами и имя ей — ✨Вариантность✨.
Прочитайте главу про подтипы в Растономиконе, если вам нужны кровавые подробности, но, вкратце: подтипы не всегда безопасны. В частности, небезопасно когда смешиваются изменяемые ссылки, потому что вы можете вызывать что-то вроде mem::swap и получить висячие указатели!
Штуки, которые выглядят как «изменяемые ссылки» являются инвариантными. Это значит, что они не разрешают использовать подтипы вместо типов. Так что, в целях безопасности, &mut T — инвариантен относительно T, и Cell<T> — инвариантен относительно T, потому что &Cell<T> по сути является обычным &mut T (из-за внутренней изменчивости).
Почти всё, что не является инвариантным, ковариантно. Это значит, что подтипы можно использовать везде, где можно использовать типы, и всё будет работать. (Есть также контравариантные типы, где типы можно использовать вместо подтипов, но они встречаются редко и никому не нравятся, так что я не буду про них говорить).
Обычно коллекции содержат изменяемый указатель на свои данные, так что они должны быть инвариантными, но на самом деле, это не так! Из-за системы владения Rust, Vec<T> семантически эквивалентен T и это значит, что его можно сделать ковариантным и это будет безопасно!
К сожалению, такое определение инвариантно:
pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, } type Link<T> = *mut Node<T>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, }
Но как на самом деле Rust принимает решение о вариантности типов? В старые добрые времена (до версии 1.0) мы разрешали людям просто указывать нужную им вариантность… и это был полный провал! Подтипы и вариантность — действительно сложные понятия. Разработчики ядра вполне искренне не могли договориться даже о базовой терминологии! В конце концов мы остановились на «вариантности на примере»: компилятор смотрит на ваши поля и копирует их вариантность. Если возникают противоречия, побеждает инвариантность, потому что это безопасно.
Так что же такого есть в наших определениях, что так не нравится Rust? *mut!
Сырые указатели в Rust и в самом деле позволяют вам делать всё, что угодно, но и они имеют одну безопасную черту: из-за того, что большинство людей не имеют представления о вариантности и подтипах, и из-за того, что некорректная ковариантность может привести к ужасным последствиям, *mut T инвариантен, поскольку обычно его используют «как» &mut T.
Это крайне раздражает меня, человека, потратившего много времени на реализую коллекций в Rust. Именно поэтому, когда я писала std::ptr::NonNull, я добавила этот кусочек магии:
В отличие от
*mut T,NonNull<T>ковариантен относительноT. Благодаря этому можно использоватьNonNull<T>для построения ковариантных типов. Это может привести к ошибкам, если тип не должен быть ковариантным.
Однако интерфейс NonNull<T> построен на базе *mut T, почему всё работает? Опять магия? Давайте посмотрим:
pub struct NonNull<T> { pointer: *const T, } impl<T> NonNull<T> { pub unsafe fn new_unchecked(ptr: *mut T) -> Self { // БЕЗОПАСНОСТЬ: вызывающая сторона должна гарантировать, что `ptr` не равен null. unsafe { NonNull { pointer: ptr as *const T } } } }
НЕТ. НИКАКОЙ МАГИИ! NonNull полагается на то, что *const T ковариантен и хранит его вместо *mut T, преобразовывая значения туда и обратно, чтобы создать впечатление, будто он хранит *mut T. Весь трюк в этом! Вот почему коллекции в Rust ковариантны. Было бы довольно грустно всё время писать так. Поэтому я заставила Правильный Тип Указателя делать всю грязную работу! Пожалуйста! Наслаждайтесь своими подтипами!
Решение в том, чтобы использовать NonNull<T>, а если вам потребуются нулевые указатели, использовать Option<NonNull<T>>. Мы действительно станем так делать?
Ага! Мы пишем связные списки продуктового уровня, поэтому будем героически разбираться в деталях и писать сложный код. (Можно было бы просто использовать *const T и приводить типы, но я искренне хочу узнать, насколько это больно… в Интересах Науки).
Так что принимайте окончательное определение нашего типа:
use std::ptr::NonNull; // !!!Изменилось!!! pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, }
…хотя, подождите, ещё одна деталь. Всякий раз, используя сырые указатели, добавляйте поле PhantomData для их защиты:
use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, /// Логически мы владеем объектами типа T и храним их по значению. _boo: PhantomData<T>, }
В этом случае я не уверена, что нам действительно нужен PhantomData, но всякий раз, когда вы используете NonNull (или просто сырые указатели), вы должны добавлять его для безопасности, чтобы компилятору и всем другим было понятно, что вы подумали над тем, что делаете.
PhantomData — это способ предоставить компилятору «пример» поля, которое концептуально присутствует в вашем типе, но физически — нет. (Прим. перевод.: физически LinkedList содержит два сырых указателя на значения типа T. Компилятор не знает, владеет ли LinkedList этими значениями и будет ли их освобождать при вызове drop. С помощью PhantomData мы даём подсказку: LinkedList владеет значениями типа T — не &T и не &mut T.) В данном случае мы используем NonNull, поэтому можем утверждать, что наш тип ведёт себя так, как будто хранит значения T, и мы добавляем PhantomData, чтобы явно это выразить.
Раньше в стандартной библиотеке PhantomData часто использовался из-за сложных и опасных трюков с деструкторами, но эти правила менялись столько раз, что я уже не уверена в необходимости фантомного поля. Впрочем, успела выработать привычку, так что буду следовать карго-культу и ставить PhantomData, даже если он не обязателен!
(Кстати, узел действительно хранит значение типа T, так что маркер для LinkedList не обязателен!)
…ладно, с представлением мы закончили! Переходим к основным функциям!
Основы
Ладно, самая ужасная часть книги. Вот почему мне потребовалось 7 лет, чтобы написать эту главу! Настало время ещё раз написать множеству скучнейших функций, которые мы писали уже 5 раз, но теперь они стали ещё многословнее и длиннее, потому теперь у нас два указателя формата Option<NonNull<Node<T>>>!
impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } }
PhantomData — тип без полей и его можно создать, просто написав его имя. пожимает плечами
pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old).front = Some(new); (*new).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. Кроме того, мы добавили // несколько проверок, на случай, если что-то напутали. debug_assert!(self.back.is_none()); debug_assert!(self.front.is_none()); debug_assert!(self.len == 0); self.back = Some(new); } self.front = Some(new); self.len += 1; } }
error[E0614]: type `NonNull<Node<T>>` cannot be dereferenced --> src\lib.rs:39:17 | 39 | (*old).front = Some(new); | ^^^^^^
Ах, да, именно поэтому я ненавижу своих детей, напичканных указателями. Нам нужно явно извлечь сырой указатель из NotNull с помощью as_ptr, потому что DerefMut определён через &mut, а мы не хотим вводить безопасные ссылки в наш небезопасный код!
(*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old);
Compiling linked-list v0.0.3 warning: field is never read: `elem` --> src\lib.rs:16:5 | 16 | elem: T, | ^^^^^^^ | = note: `#[warn(dead_code)]` on by default warning: `linked-list` (lib) generated 1 warning (1 duplicate) warning: `linked-list` (lib test) generated 1 warning Finished test [unoptimized + debuginfo] target(s) in 0.33s
Прекрасно, теперь pop (и len):
pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. // Обратите внимание, что мы больше не должны беспокоиться // о `take`, потому что копирование сырых указателей не приводит к // вызову деструкторов, если мы что-то напутаем... правда? :) // Праааавда? :))) self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! debug_assert!(self.len == 1); self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn len(&self) -> usize { self.len }
Compiling linked-list v0.0.3 Finished dev [unoptimized + debuginfo] target(s) in 0.37s
Мне кажется, всё в порядке, пора писать тест!
#[cfg(test)] mod test { use super::LinkedList; #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Пытаемся сломать пустой список assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Пытаемся сломать список из одного элемента list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Всё перемешиваем list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } }
Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.40s Running unittests src\lib.rs running 1 test test test::test_basic_front ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
Ура, у нас всё идеально!
…Правда?
Метод drop и устойчивость к панике
А вы заметили этот комментарий:
// Обратите внимание, что мы больше не должны беспокоиться // о `take`, потому что копирование сырых указателей не приводит к // вызову деструкторов, если мы что-то напутаем... правда? :) // Праааавда? :)))
Это правда?
Простите, вы забыли, какую книгу читаете? Конечно, нет! (В каком-то смысле.)
Снова заглянем внутрь pop_front:
// Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! debug_assert!(self.len == 1); self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T.
Видите ошибку? Ужасно, но она в этой строчке:
debug_assert!(self.len == 1);
Серьёзно? Проклятая проверка целостности, сделанная для тестов — ошибка? Да!!! Впрочем, если коллекция реализована корректно, ошибка не должна возникнуть. Но может получиться так, что вполне безобидная штука вроде «некорректного обновления len» превратится в Уязвимость, вызванную ошибкой безопасности памяти! Почему? Потому что может возникнуть паника! Большую часть времени вам не стоит беспокоиться о панике, но однажды вы начинаете писать поистине небезопасный код и вольно обращаетесь с «инвариантностью», и вам приходится проявлять повышенную бдительность!
Нам нужно поговорить об устойчивости к исключениям (ИЛИ устойчивости к панике, ИЛИ устойчивости к раскрутке стека…).
Итак, паника по умолчанию приводит к раскрутке стека (unwinding). Раскрутка — это красивый способ сказать «немедленно завершить каждую функцию». Вы можете подумать «Ладно, если всё завершается, значит, программа тоже завершается, так что не о чем беспокоиться?», но вы не правы!
Мы должны беспокоиться по двум причинам: из-за запуска деструкторов, и возможного перехвата раскрутки. В обоих случаях, код будет выполняться после паники, так что нам надо быть очень осторожными и убедиться, что наши небезопасные коллекции находятся в каком-то когерентном состоянии независимо от паники, потому что паника неявно означает ранний возврат (early return)!
Подумайте, в каком состоянии находится коллекция, когда мы доходим до строки с ошибкой.
У нас есть boxed_node на стеке, и мы извлекли из него элемент. Если бы мы завершили функцию в этой точке, Box должен был быть уничтожен, и узел должен был быть освобождён. Теперь вы видите?.. self.back всё ещё указывает на освобождённый узел! Как только мы реализуем оставшиеся функции и начнём использовать self.back для разных вещей, это приведёт к ошибке использование-после-освобождения (use-after-free)! Кошмар!
Интересно, что в этой строке встречается похожая проблема, но гораздо более безопасная:
self.len -= 1;
По умолчанию в отладочных сборках Rust проверяет выход за нижнюю и верхнюю границы, и паникует, когда они случаются. Да, любая арифметическая операция представляет собой угрозу для устойчивости к панике! Этот случай лучше, потому что он происходит после того, как мы восстановили все наши инварианты, так что он не может привести к проблемам с безопасностью памяти… Если мы вышли за нижнюю границу, ошибка уже случилась, так что программа упала бы в любом случае! В каком смысле debug_assert хуже, потому что превращает неважную проблему в критическую!
Я уже несколько раз употребляла термин «инвариант», а всё потому, что это действительно полезная концепция для разговора про устойчивость к панике! В каком-то смысле, для стороннего наблюдателя у нашей коллекции есть определённые свойства, которые всегда соблюдаются. Для связного списка одним из таких свойств является следующее: для любого достижимого узла в нашем списке выделена и проинициализирована память.
Внутри реализации нам доступно чуть больше гибкости, чтобы временно нарушать инварианты, пока мы уверены, что восстановим их до того, как кто-нибудь заметит. По сути, это одно из «главных преимуществ» системы владения и заимствования в Rust для коллекций: если операции нужен параметр &mut Self, мы гарантированно получаем эксклюзивный доступ к нашей коллекции и свободно можем временно нарушить инварианты, зная, что никто не сможет незаметно нам помешать.
Возможно, наилучшим воплощением этой идеи является Vec::drain, который, фактически, позволяет вам полностью нарушить основной инвариант Vec и начать извлекать значения не только из начала Vec, но и из середины. Причина, по которой это правильно заключается в том, что итератор Drain, который мы возвращаем, хранит &mut на Vec, поэтому любой доступ к нему ограничен! Никто не сможет пользоваться Vec до тех пор, пока итератор Drain не завершится, и тогда деструктор «восстановит» Vec до того, как кто-либо это заметит, что идеа—
Нет, это не идеально. К сожалению вы не можете полагаться на выполнение деструкторов в коде, который вы не контролируете, так что даже с Drain нам нужно делать небольшую дополнительную работу, чтобы инварианты нашего типа всегда сохранялись, но в несколько нелепой манере: в начале мы просто сбрасываем длину Vec в 0, так что если у кого-то утечёт Drain, он получит безопасный Vec… потеряв при этом все данные. Ты устроил утечку мне? Я устрою утечку тебе! Око за око! Истинная справедливость!
Чтобы разобраться, когда для устойчивости при панике действительно можно использовать деструкторы, познакомьтесь с учебным примером использования BinaryHeap::sift_up.
Нам в любом случае не нужны все эти навороченные штуки для наших связных списков. Нам всего лишь надо быть внимательнее по отношению к тому, где мы нарушаем инварианты, чтобы обеспечить корректность и избегать ненужной раскрутки стека в середине сложных задач.
В этом случае у нас есть две возможности сделать код надёжнее:
Чаще использовать такие операции, как Option::take, потому что они более «транзакционные» и имеют тенденцию сохранять инварианты.
Удалить все debug_assert и доверять себе в написании лучших тестов со специальными функциями «проверки целостности», которые никогда не будут выполняться в пользовательском коде.
В принципе мне нравится первый вариант, но на самом деле он не сработает для двусвязного списка, потому что нам одновременно требуются два значения, а не одно. Option::take не решит нашей проблемы, а вот перенос debug_assert на строку ниже — решит. Но, правда, зачем усложнять себе жизнь? Давайте просто удалим все debug_assert и убедимся, что любая паника может возникнуть только в начале или конце наших методов, где, как известно, выполняются все инварианты.
(Возможно про них следует думать, как о предусловиях и постусловиях, но на самом деле к ним правильнее относиться, как к инвариантам!)
Вот наша полная текущая реализация:
use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. Кроме того, мы добавили // несколько проверок, на случай, если что-то напутали. self.back = Some(new); } // Этот код выполняется всегда! self.front = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn len(&self) -> usize { self.len } }
Что здесь может привести к панике? Чтобы ответить на этот вопрос, надо быть экспертом по Rust, но, к счастью, я им являюсь!
Единственные места, которые я вижу, где код может вызвать панику (за исключением совершенно безумной идеи перекомпилировать стандартную библиотеку с включенными debug_assert, чего никогда не следует делать) — это Box::new (в случае нехватки памяти) и арифметические операции с len. Всё это находится или в самом конце или в самом начале наших методов, так что да, наш код красивый и безопасный!
…удивились, что Bos::new может вызывать панику? Паника может достать вас самым непредсказуемым образом! Держите свои инварианты в целости, чтобы вас это не беспокоило!
Скучная комбинаторика
Ладно, возвращаемся к нашим ежедневным связным спискам!
Для начала разберёмся с Drop, который тривиально реализуется с помощью pop:
impl<T> Drop for LinkedList<T> { fn drop(&mut self) { // Вызываем pop, пока есть элементы while let Some(_) = self.pop_front() { } } }
Нам предстоит написать множество действительно скучных комбинаторных реализаций, таких как front, front_mut, back, back_mut, iter, iter_mut, into_iter, …
Можно было бы воспользоваться макросами или чем то подобным, но, честно говоря, это хуже, чем обычная копи-паста. Нам предстоит много копи-пасты. Я очень тщательно подошла к реализации предыдущих push/pop. Нам осталось буквально поменять местами front и back, и код будет работать! Да здравствует болезненный опыт! (Заманчиво говорить о «предыдущем и следующем» узлах, но я обнаружила, что термины «передний» и «задний» ведут к большей согласованности и позволяют избегать ошибок.)
Хорошо, начнём с front:
pub fn front(&self) -> Option<&T> { unsafe { self.front.map(|node| &(*node.as_ptr()).elem) } }
На самом деле эта книга очень старая, так что я решила добавить в код несколько приятных нововведений, скажем, оператор ?, который приводит к раннему возврату в случае Option::None. Получится улучшить код?
pub fn front(&self) -> Option<&T> { unsafe { Some(&(*self.front?.as_ptr()).elem) } }
Нормально? В таком простом код практически ничего не улучшилось, а, кроме того, в предыдущем разделе мы говорили о том, что ранние возвраты для нас опасны. Возможно, нам надо писать здесь чуть более явный код (мне всё ещё нравится старая реализация через map). Теперь front_mut:
pub fn front_mut(&mut self) -> Option<&mut T> { unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) } }
Чуть позже я добавлю все версии back.
Далее, итераторы. В отличие от наших прошлых списков, мы наконец можем реализовать [DoubleEndedIterator](https://doc.rust-lang.org/std/iter/trait.DoubleEndedIterator.html, и, поскольку мы вышли на продуктовый уровень — и ExactSizeIterator.
Таким образом, помимо next и size_hint, мы реализуем next_back и len.
Самые внимательные читатели могут заметить, что IterMut в случае итерации с двумя концами выглядит гораздо подозрительнее, но но самом деле он всё ещё работает!
…боже, будет тонна рутинного кода. Возможно, мне следует написать макрос… нет, нет, это всё ещё плохая идея.
pub struct Iter<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a T>, } impl<T> LinkedList<T> { pub fn iter(&self) -> Iter<T> { Iter { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } } impl<'a, T> IntoIterator for &'a LinkedList<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &(*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &(*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for Iter<'a, T> { fn len(&self) -> usize { self.len } }
…это всего лишь .iter()…
Позже мы добавим IterMut. Будет буквально тот же код, но с большим количеством mut. Для начала разберёмся с into_iter. К счастью, мы всё ещё можем положиться на проверенное решение: завернуть нашу коллекцию и использовать pop для next:
pub struct IntoIter<T> { list: LinkedList<T>, } impl<T> LinkedList<T> { pub fn into_iter(self) -> IntoIter<T> { IntoIter { list: self } } } impl<T> IntoIterator for LinkedList<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(self) -> Self::IntoIter { self.into_iter() } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.list.pop_front() } fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.list.pop_back() } } impl<T> ExactSizeIterator for IntoIter<T> { fn len(&self) -> usize { self.list.len } }
Всё ещё много рутинного кода, но, по крайней мере, это удовлетворительный рутинный код.
Хорошо, вот весь наш код со всеми комбинаторными вариантами:
use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } pub struct Iter<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a T>, } pub struct IterMut<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a mut T>, } pub struct IntoIter<T> { list: LinkedList<T>, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. self.back = Some(new); } // Этот код выполняется всегда! self.front = Some(new); self.len += 1; } } pub fn push_back(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { back: None, front: None, elem, }))); if let Some(old) = self.back { // Вставляем новый задний узел перед старым (*old.as_ptr()).back = Some(new); (*new.as_ptr()).front = Some(old); } else { // Если заднего узла нет, у нас пустой список и нам надо // установить и значение переднего узла. self.front = Some(new); } // Этот код выполняется всегда! self.back = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn pop_back(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть задний узел. self.back.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым задним узлом. self.back = boxed_node.front; if let Some(new) = self.back { // Убираем ссылку заднего узла на удалённый узел. (*new.as_ptr()).back = None; } else { // Если задний узел равен null, значит, список пустой! self.front = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn front(&self) -> Option<&T> { unsafe { self.front.map(|node| &(*node.as_ptr()).elem) } } pub fn front_mut(&mut self) -> Option<&mut T> { unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) } } pub fn back(&self) -> Option<&T> { unsafe { self.back.map(|node| &(*node.as_ptr()).elem) } } pub fn back_mut(&mut self) -> Option<&mut T> { unsafe { self.back.map(|node| &mut (*node.as_ptr()).elem) } } pub fn len(&self) -> usize { self.len } pub fn iter(&self) -> Iter<T> { Iter { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn iter_mut(&mut self) -> IterMut<T> { IterMut { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn into_iter(self) -> IntoIter<T> { IntoIter { list: self } } } impl<T> Drop for LinkedList<T> { fn drop(&mut self) { // Вызываем pop, пока есть элементы while let Some(_) = self.pop_front() { } } } impl<'a, T> IntoIterator for &'a LinkedList<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &(*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &(*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for Iter<'a, T> { fn len(&self) -> usize { self.len } } impl<'a, T> IntoIterator for &'a mut LinkedList<T> { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &mut (*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &mut (*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for IterMut<'a, T> { fn len(&self) -> usize { self.len } } impl<T> IntoIterator for LinkedList<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(self) -> Self::IntoIter { self.into_iter() } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.list.pop_front() } fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.list.pop_back() } } impl<T> ExactSizeIterator for IntoIter<T> { fn len(&self) -> usize { self.list.len } } #[cfg(test)] mod test { use super::LinkedList; #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Пытаемся сломать пустой список assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Пытаемся сломать список из одного элемента list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Всё перемешиваем list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } }
Всякая всячина
Вы говорили, что хотите продуктового кода, нет?
Вот немного всякой всячины, чтобы получилась «хорошая» коллекция:
impl<T> LinkedList<T> { pub fn is_empty(&self) -> bool { self.len == 0 } pub fn clear(&mut self) { // О, смотрите, это снова drop while let Some(_) = self.pop_front() { } } }
Теперь реализуем набор типажей, которые должны быть у коллекции:
impl<T> Default for LinkedList<T> { fn default() -> Self { Self::new() } } impl<T: Clone> Clone for LinkedList<T> { fn clone(&self) -> Self { let mut new_list = Self::new(); for item in self { new_list.push_back(item.clone()); } new_list } } impl<T> Extend<T> for LinkedList<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { for item in iter { self.push_back(item); } } } impl<T> FromIterator<T> for LinkedList<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { let mut list = Self::new(); list.extend(iter); list } } impl<T: Debug> Debug for LinkedList<T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self).finish() } } impl<T: PartialEq> PartialEq for LinkedList<T> { fn eq(&self, other: &Self) -> bool { self.len() == other.len() && self.iter().eq(other) } fn ne(&self, other: &Self) -> bool { self.len() != other.len() || self.iter().ne(other) } } impl<T: Eq> Eq for LinkedList<T> { } impl<T: PartialOrd> PartialOrd for LinkedList<T> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other) } } impl<T: Ord> Ord for LinkedList<T> { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other) } } impl<T: Hash> Hash for LinkedList<T> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); for item in self { item.hash(state); } } }
Я написала весь код с нуля, а не просто скопировала из стандартной библиотеки. Здесь всё такое интересное и я определённо помню все тонкости ручной реализации Hash. Да, я постоянно думаю об этом…
Ладно, здесь действительно есть пара моментов, на которые надо обратить внимание.
Во-первых, неприятный конфликт пространств имён. По какой-то причине в стандартной библиотеке теперь есть макросы с именами Hash и Debug, так что если вы не импортировали типажи, вы получите поистине таинственные ошибки о макросах вместо простого «типаж не найден».
Другая интересная вещь касается самого Hash. Вы видите, что мы вызываем hash у len? Это на самом деле важно! Если коллекции не учитывают свою длину при вычислении хеша, они могут случайно стать уязвимыми для коллизии префиксов. Например, чем отличаются ["he", "llo"] и ["hello"]? Если при вычислении хеша вы не используете длину или какой-то разделитель, то ничем! Слишком высокая вероятность коллизий при вычислении хеша может привести к большим неприятностям, так что просто напишите правильно!
Хорошо, вот наш текущий код:
use std::cmp::Ordering; use std::fmt::{self, Debug}; use std::hash::{Hash, Hasher}; use std::iter::FromIterator; use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } pub struct Iter<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a T>, } pub struct IterMut<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a mut T>, } pub struct IntoIter<T> { list: LinkedList<T>, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. debug_assert!(self.back.is_none()); debug_assert!(self.front.is_none()); debug_assert!(self.len == 0); self.back = Some(new); } // Этот код выполняется всегда! self.front = Some(new); self.len += 1; } } pub fn push_back(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { back: None, front: None, elem, }))); if let Some(old) = self.back { // Вставляем новый задний узел перед старым (*old.as_ptr()).back = Some(new); (*new.as_ptr()).front = Some(old); } else { // Если заднего узла нет, у нас пустой список и нам надо // установить и значение переднего узла. self.front = Some(new); } // Этот код выполняется всегда! self.back = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! debug_assert!(self.len == 1); self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn pop_back(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть задний узел. self.back.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым задним узлом. self.back = boxed_node.front; if let Some(new) = self.back { // Убираем ссылку заднего узла на удалённый узел. (*new.as_ptr()).back = None; } else { // Если задний узел равен null, значит, список пустой! self.front = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn front(&self) -> Option<&T> { unsafe { self.front.map(|node| &(*node.as_ptr()).elem) } } pub fn front_mut(&mut self) -> Option<&mut T> { unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) } } pub fn back(&self) -> Option<&T> { unsafe { self.back.map(|node| &(*node.as_ptr()).elem) } } pub fn back_mut(&mut self) -> Option<&mut T> { unsafe { self.back.map(|node| &mut (*node.as_ptr()).elem) } } pub fn len(&self) -> usize { self.len } pub fn is_empty(&self) -> bool { self.len == 0 } pub fn clear(&mut self) { // Oh look it's drop again while let Some(_) = self.pop_front() { } } pub fn iter(&self) -> Iter<T> { Iter { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn iter_mut(&mut self) -> IterMut<T> { IterMut { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn into_iter(self) -> IntoIter<T> { IntoIter { list: self } } } impl<T> Drop for LinkedList<T> { fn drop(&mut self) { // Вызываем pop, пока есть элементы while let Some(_) = self.pop_front() { } } } impl<T> Default for LinkedList<T> { fn default() -> Self { Self::new() } } impl<T: Clone> Clone for LinkedList<T> { fn clone(&self) -> Self { let mut new_list = Self::new(); for item in self { new_list.push_back(item.clone()); } new_list } } impl<T> Extend<T> for LinkedList<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { for item in iter { self.push_back(item); } } } impl<T> FromIterator<T> for LinkedList<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { let mut list = Self::new(); list.extend(iter); list } } impl<T: Debug> Debug for LinkedList<T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self).finish() } } impl<T: PartialEq> PartialEq for LinkedList<T> { fn eq(&self, other: &Self) -> bool { self.len() == other.len() && self.iter().eq(other) } fn ne(&self, other: &Self) -> bool { self.len() != other.len() || self.iter().ne(other) } } impl<T: Eq> Eq for LinkedList<T> { } impl<T: PartialOrd> PartialOrd for LinkedList<T> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other) } } impl<T: Ord> Ord for LinkedList<T> { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other) } } impl<T: Hash> Hash for LinkedList<T> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); for item in self { item.hash(state); } } } impl<'a, T> IntoIterator for &'a LinkedList<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &(*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &(*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for Iter<'a, T> { fn len(&self) -> usize { self.len } } impl<'a, T> IntoIterator for &'a mut LinkedList<T> { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &mut (*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &mut (*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for IterMut<'a, T> { fn len(&self) -> usize { self.len } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.list.pop_front() } fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.list.pop_back() } } impl<T> ExactSizeIterator for IntoIter<T> { fn len(&self) -> usize { self.list.len } } #[cfg(test)] mod test { use super::LinkedList; #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Пытаемся сломать пустой список assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Пытаемся сломать список из одного элемента list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Всё перемешиваем list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } }
Тестирование
Я отложила тестирования на потом, потому что, ну, теперь мы оба знаем, что мы мастера Rust и больше не допускаем ошибок! Кроме того, это переписанная версия старого крейта, так что у меня уже были все тесты. Вы их уже видели, и не раз. Вот они:
#[cfg(test)] mod test { use super::LinkedList; fn generate_test() -> LinkedList<i32> { list_from(&[0, 1, 2, 3, 4, 5, 6]) } fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { v.iter().map(|x| (*x).clone()).collect() } #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Пытаемся сломать пустой список assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Пытаемся сломать список из одного элемента list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Всё перемешиваем list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } #[test] fn test_basic() { let mut m = LinkedList::new(); assert_eq!(m.pop_front(), None); assert_eq!(m.pop_back(), None); assert_eq!(m.pop_front(), None); m.push_front(1); assert_eq!(m.pop_front(), Some(1)); m.push_back(2); m.push_back(3); assert_eq!(m.len(), 2); assert_eq!(m.pop_front(), Some(2)); assert_eq!(m.pop_front(), Some(3)); assert_eq!(m.len(), 0); assert_eq!(m.pop_front(), None); m.push_back(1); m.push_back(3); m.push_back(5); m.push_back(7); assert_eq!(m.pop_front(), Some(1)); let mut n = LinkedList::new(); n.push_front(2); n.push_front(3); { assert_eq!(n.front().unwrap(), &3); let x = n.front_mut().unwrap(); assert_eq!(*x, 3); *x = 0; } { assert_eq!(n.back().unwrap(), &2); let y = n.back_mut().unwrap(); assert_eq!(*y, 2); *y = 1; } assert_eq!(n.pop_front(), Some(0)); assert_eq!(n.pop_front(), Some(1)); } #[test] fn test_iterator() { let m = generate_test(); for (i, elt) in m.iter().enumerate() { assert_eq!(i as i32, *elt); } let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); let mut it = n.iter(); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next().unwrap(), &4); assert_eq!(it.size_hint(), (0, Some(0))); assert_eq!(it.next(), None); } #[test] fn test_iterator_double_end() { let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); n.push_front(5); n.push_front(6); let mut it = n.iter(); assert_eq!(it.size_hint(), (3, Some(3))); assert_eq!(it.next().unwrap(), &6); assert_eq!(it.size_hint(), (2, Some(2))); assert_eq!(it.next_back().unwrap(), &4); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next_back().unwrap(), &5); assert_eq!(it.next_back(), None); assert_eq!(it.next(), None); } #[test] fn test_rev_iter() { let m = generate_test(); for (i, elt) in m.iter().rev().enumerate() { assert_eq!(6 - i as i32, *elt); } let mut n = LinkedList::new(); assert_eq!(n.iter().rev().next(), None); n.push_front(4); let mut it = n.iter().rev(); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next().unwrap(), &4); assert_eq!(it.size_hint(), (0, Some(0))); assert_eq!(it.next(), None); } #[test] fn test_mut_iter() { let mut m = generate_test(); let mut len = m.len(); for (i, elt) in m.iter_mut().enumerate() { assert_eq!(i as i32, *elt); len -= 1; } assert_eq!(len, 0); let mut n = LinkedList::new(); assert!(n.iter_mut().next().is_none()); n.push_front(4); n.push_back(5); let mut it = n.iter_mut(); assert_eq!(it.size_hint(), (2, Some(2))); assert!(it.next().is_some()); assert!(it.next().is_some()); assert_eq!(it.size_hint(), (0, Some(0))); assert!(it.next().is_none()); } #[test] fn test_iterator_mut_double_end() { let mut n = LinkedList::new(); assert!(n.iter_mut().next_back().is_none()); n.push_front(4); n.push_front(5); n.push_front(6); let mut it = n.iter_mut(); assert_eq!(it.size_hint(), (3, Some(3))); assert_eq!(*it.next().unwrap(), 6); assert_eq!(it.size_hint(), (2, Some(2))); assert_eq!(*it.next_back().unwrap(), 4); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(*it.next_back().unwrap(), 5); assert!(it.next_back().is_none()); assert!(it.next().is_none()); } #[test] fn test_eq() { let mut n: LinkedList<u8> = list_from(&[]); let mut m = list_from(&[]); assert!(n == m); n.push_front(1); assert!(n != m); m.push_back(1); assert!(n == m); let n = list_from(&[2, 3, 4]); let m = list_from(&[1, 2, 3]); assert!(n != m); } #[test] fn test_ord() { let n = list_from(&[]); let m = list_from(&[1, 2, 3]); assert!(n < m); assert!(m > n); assert!(n <= n); assert!(n >= n); } #[test] fn test_ord_nan() { let nan = 0.0f64 / 0.0; let n = list_from(&[nan]); let m = list_from(&[nan]); assert!(!(n < m)); assert!(!(n > m)); assert!(!(n <= m)); assert!(!(n >= m)); let n = list_from(&[nan]); let one = list_from(&[1.0f64]); assert!(!(n < one)); assert!(!(n > one)); assert!(!(n <= one)); assert!(!(n >= one)); let u = list_from(&[1.0f64, 2.0, nan]); let v = list_from(&[1.0f64, 2.0, 3.0]); assert!(!(u < v)); assert!(!(u > v)); assert!(!(u <= v)); assert!(!(u >= v)); let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]); let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]); assert!(!(s < t)); assert!(s > one); assert!(!(s <= one)); assert!(s >= one); } #[test] fn test_debug() { let list: LinkedList<i32> = (0..10).collect(); assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); let list: LinkedList<&str> = vec!["just", "one", "test", "more"] .iter().copied() .collect(); assert_eq!(format!("{:?}", list), r#"["just", "one", "test", "more"]"#); } #[test] fn test_hashmap() { // Убеждаемся, что HashMap работает со списком в качестве ключа let list1: LinkedList<i32> = (0..10).collect(); let list2: LinkedList<i32> = (1..11).collect(); let mut map = std::collections::HashMap::new(); assert_eq!(map.insert(list1.clone(), "list1"), None); assert_eq!(map.insert(list2.clone(), "list2"), None); assert_eq!(map.len(), 2); assert_eq!(map.get(&list1), Some(&"list1")); assert_eq!(map.get(&list2), Some(&"list2")); assert_eq!(map.remove(&list1), Some("list1")); assert_eq!(map.remove(&list2), Some("list2")); assert!(map.is_empty()); } }
А сейчас момент истины:
cargo test Finished test [unoptimized + debuginfo] target(s) in 0.00s Running unittests src\lib.rs running 12 tests test test::test_basic ... ok test test::test_basic_front ... ok test test::test_eq ... ok test test::test_iterator ... ok test test::test_iterator_mut_double_end ... ok test test::test_ord_nan ... ok test test::test_iterator_double_end ... ok test test::test_mut_iter ... ok test test::test_rev_iter ... ok test test::test_hashmap ... ok test test::test_ord ... ok test test::test_debug ... ok test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
$env:MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo miri test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.35s Running unittests src\lib.rs running 12 tests test test::test_basic ... ok test test::test_basic_front ... ok test test::test_debug ... ok test test::test_eq ... ok test test::test_hashmap ... ok test test::test_iterator ... ok test test::test_iterator_double_end ... ok test test::test_iterator_mut_double_end ... ok test test::test_mut_iter ... ok test test::test_ord ... ok test test::test_ord_nan ... ok test test::test_rev_iter ... ok test result: ok. 12 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out
?
У нас получилось и мы не облажались. Это не трюк! Вся наша практика, все тренировки наконец окупились, мы, наконец, написали хороший код!!!
Теперь, разобравшись со всякой ерунда, мы можем вернуться к Интересным Вещам!
Send, Sync и тесты этапа компиляции
У нас есть ещё пара типажей, о которых стоит подумать, но они особенные. Нам предстоит иметь дело со Древним Римом языка Rust: небезопасными встроенными явно-включаемыми типажами (The Unsafe Opt-In Built-In Traits, OIBITs): Send и Sync, которые на самом деле и не-встроенные и явно-отключаемые (есть 1 свойство из 3 — уже неплохо!).
Как и у Copy, у этих типажей нет никакого связанного с ними кода — они являются маркерами, показывающими, что ваш тип обладает определённым свойством. Send говорит, что ваш тип можно безопасно передать в другой поток. Sync говорит, что ваш тип можно безопасно разделять между потоками (&Self: Send).
Тот же аргумент, что и в случае ковариантности LinkedList, применим и здесь: в общем и целом нормальные коллекции, которые не используют причудливых трюков с внутренней изменчивостью, безопасны и для Send, и для Sync.
Но, как я сказала, они явно отключаемые. Так что, на самом деле, может, у нас уже всё работает? Как это можно проверить?
Давайте добавим немного новой магии к нашему коду: случайный приватный мусор, который не будет компилироваться, пока наши типы не обладают свойствами, которые мы ожидаем:
#[allow(dead_code)] fn assert_properties() { fn is_send<T: Send>() {} fn is_sync<T: Sync>() {} is_send::<LinkedList<i32>>(); is_sync::<LinkedList<i32>>(); is_send::<IntoIter<i32>>(); is_sync::<IntoIter<i32>>(); is_send::<Iter<i32>>(); is_sync::<Iter<i32>>(); is_send::<IterMut<i32>>(); is_sync::<IterMut<i32>>(); fn linked_list_covariant<'a, T>(x: LinkedList<&'static T>) -> LinkedList<&'a T> { x } fn iter_covariant<'i, 'a, T>(x: Iter<'i, &'static T>) -> Iter<'i, &'a T> { x } fn into_iter_covariant<'a, T>(x: IntoIter<&'static T>) -> IntoIter<&'a T> { x } }
cargo build Compiling linked-list v0.0.3 error[E0277]: `NonNull<Node<i32>>` cannot be sent between threads safely --> src\lib.rs:433:5 | 433 | is_send::<LinkedList<i32>>(); | ^^^^^^^^^^^^^^^^^^^^^^^^^^ `NonNull<Node<i32>>` cannot be sent between threads safely | = help: within `LinkedList<i32>`, the trait `Send` is not implemented for `NonNull<Node<i32>>` = note: required because it appears within the type `Option<NonNull<Node<i32>>>` note: required because it appears within the type `LinkedList<i32>` --> src\lib.rs:8:12 | 8 | pub struct LinkedList<T> { | ^^^^^^^^^^ note: required by a bound in `is_send` --> src\lib.rs:430:19 | 430 | fn is_send<T: Send>() {} | ^^^^ required by this bound in `is_send` <и ещё миллион ошибок>
Боже, ну что за дела? А я ведь уже заготовила отличную шутку про Древний Рим!
Ладно, я соврала вам, когда сказала, что у сырых указателей есть только одна защита. Есть и вторая. У *const И *mut в целях безопасности явно отключены Send и Sync, так что нам на самом деле надо включить их обратно:
unsafe impl<T: Send> Send for LinkedList<T> {} unsafe impl<T: Sync> Sync for LinkedList<T> {} unsafe impl<'a, T: Send> Send for Iter<'a, T> {} unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {} unsafe impl<'a, T: Send> Send for IterMut<'a, T> {} unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {}
Обратите внимание, что здесь мы должны писать unsafe impl: ведь это небезопасные типажи! Небезопасный код (например, конкурентные библиотеки) зависят от того, насколько правильно мы их реализуем! Но, поскольку в них нет никакого кода, мы гарантируем лишь то, что да, мы действительно можем передавать и разделять список между потоками!
Не стоит добавлять их просто так, но я, как Сертифицированный Специалист, могу сказать, да, с ними всё в порядке. Обратите внимание, что нам не надо реализовывать Send и Sync для IntoIter: поскольку он просто содержит LinkedList, они для него определены автоматически. Я же говорила, что Send и Sync явно отключаемые!
cargo build Compiling linked-list v0.0.3 Finished dev [unoptimized + debuginfo] target(s) in 0.18s
Что ж, прекрасно!
…Подождите, на самом деле это очень опасно, когда типы обладают свойством, которым не должны обладать. Например, IterMut определённо не должен быть ковариантным, потому что он «как бы» &mut T. Но как нам это проверить?
С помощью Магии! Ну, на самом деле, с помощью rustdoc! Ладно, нам не обязательно использовать для этого rustdoc, но это самый весёлый способ проверки. Смотрите, если вы напишите документацию и включите в неё блок кода, rustdoc попытается скомпилировать и запустить его, и с помощью этого мы можем создавать новые безымянные «программы», которые не оказывают влияния на главный код:
/// ``` /// use linked_list::IterMut; /// /// fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x } /// ``` fn iter_mut_invariant() {}
cargo test ... Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 458) ... FAILED failures: ---- src\lib.rs - assert_properties::iter_mut_invariant (line 458) stdout ---- error[E0308]: mismatched types --> src\lib.rs:461:86 | 6 | fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x } | ^ lifetime mismatch | = note: expected struct `linked_list::IterMut<'_, &'a T>` found struct `linked_list::IterMut<'_, &'static T>`
Хорошо, мы доказали что наш тип инвариантный, но, хм, теперь наши тесты не проходят. Не беспокойтесь, rustdoc позволяет написать аннотацию, которая подскажет, что это ожидаемое поведение: compile_fail!
(На самом деле мы всего лишь доказали, что тип «не ковариантный», но если вам удастся случайно сделать неправильный «контравариантный» тип, то… мои поздравления?)
/// ```compile_fail /// use linked_list::IterMut; /// /// fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x } /// ``` fn iter_mut_invariant() {}
cargo test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.49s Running unittests src\lib.rs ... Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 458) - compile fail ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.12s
Ура! Я рекомендую в начале всегда создавать тест без compile_fail, чтобы убедиться, что он не компилируется по правильной причине. Например, в этом же тесте возникнет ошибка (и, соответственно, он будет пройден), если вы забудете написать use, но это ведь не то, что нам нужно! Хотя теоретически было бы правильно «требовать» у компилятора проверки на определённую ошибку, это стало бы абсолютным кошмаром, поскольку всякий раз, когда в компиляторе улучшали бы выдачу ошибок, это ломало бы тесты. А мы хотим, чтобы компилятор улучшался, поэтому нет, вы этого не получите.
(Впрочем, мы можем просто указать нужный код ошибки вместе с compile_fail, но это работает только в nightly-версиях и на это не стоит полагаться по причинам, озвученным выше. В не-nightly-версиях код ошибки молча игнорируется.)
/// ```compile_fail,E0308 /// use linked_list::IterMut; /// /// fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x } /// ``` fn iter_mut_invariant() {}
…кстати, вы заметили, когда мы на самом деле сделали IterMut инвариантным? Пропустить было легко, поскольку я «всего-навсего» скопировала Iter и вставила его в конец. Вот, в последней строке:
pub struct IterMut<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a mut T>, }
Попробуем удалить PhantomData:
cargo build Compiling linked-list v0.0.3 (C:\Users\ninte\dev\contain\linked-list) error[E0392]: parameter `'a` is never used --> src\lib.rs:30:20 | 30 | pub struct IterMut<'a, T> { | ^^ unused parameter | = help: consider removing `'a`, referring to it in a field, or using a marker such as `PhantomData`
Ха! Компилятор поддерживает нас и не позволяет нам просто не указывать время жизни. Давайте теперь попробуем использовать неправильный пример:
_boo: PhantomData<&'a T>,
cargo build Compiling linked-list v0.0.3 (C:\Users\ninte\dev\contain\linked-list) Finished dev [unoptimized + debuginfo] target(s) in 0.17s
Он собрался! Смогут ли сейчас наши тесты выявить проблему?
cargo test ... Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 458) - compile fail ... FAILED failures: ---- src\lib.rs - assert_properties::iter_mut_invariant (line 458) stdout ---- Test compiled successfully, but it's marked `compile_fail`. failures: src\lib.rs - assert_properties::iter_mut_invariant (line 458) test result: FAILED. 0 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.15s
Йееее!!! Система работает! Мне очень нравится, когда тесты делают свою работу, так что мне не приходиться переживать из-за возможных ошибок!
Введение в Курсоры
Здорово!!! Теперь у нас есть LinkedList, не уступающий по качеству реализации списку из стандартной библиотеки 1.0! Что, конечно, означает, что наш LinkedList всё ещё совершенно бесполезен. Мы смирились с огромными потерями производительности, реализуя дек как связный список, и у нас нет ни одного API, который бы сделал его полезным.
Вот как у нас обстоят дела с «киллер-фичами» связных списков:
? Возможность делать странные интрузивные штуки
? Возможность делать странные неблокирующие штуки
? Возможность хранить типы переменного размера
? push/pop за O(1) без амортизации (если вы, конечно, верите, что malloc выполняется за O(1))
? Разбиение списка за O(1)
? Вставка списка за O(1)
Ну… 1 из 6… лучше, чем ничего! Понимаете, почему я хотела выдрать эту штуку из стандартной библиотеки?
Мы не станем реализовывать «странные» штуки, потому что они зависят от предметной области и обычно делаются для решения конкретной задачи (adhoc). Но вот разбиение и вставка — совсем другое дело!
Однако, здесь есть проблема: на самом деле получение k-того элемента в связном списке требует времени O(k), так как же мы можем произвольно разбить или вставить список за O(1)? Ну, трюк в том, что вы не предоставляете API наподобие split_at(index) — вы создаёте систему, где пользователь может добраться до нужной позиции в списке, а затем, в этой точке, модифицировать его за O(1)!
Эй, а ведь у нас уже есть итераторы! Можем ли мы использовать их для перебора? Вроде бы… но мешает одна из их супер-способностей. Возможно, вы помните, что способ, которым мы указываем время жизни итераторов, возвращающих ссылку на элемент, работает так, что они возвращают ссылку, которая не привязана к итератору. Это позволяет нам повторно вызывать next и хранить элементы:
let mut list = ...; let iter = list.iter_mut(); let elem1 = list.next(); let elem2 = list.next(); if elem1 == elem2 { ... }
Если бы возвращаемые ссылки заимствовали итератор, этот код вообще бы не работал. Компилятор бы просто жаловался на второй вызов next! Эта гибкость великолепна, но она накладывает на нас некоторые неявные ограничения:
Итераторы, возвращающие изменяемую ссылку, не могут двигаться назад и возвращать элемент повторно, поскольку тогда пользовать мог бы получить две ссылки
&mutна один и тот же элемент, что ломает фундаментальные правила языка.Итераторы, возвращающие разделяемую ссылку, не должны иметь других методов, которые могут модифицировать нижележащую коллекцию способом, который сделает невалидными уже полученные ссылки.
К сожалению, нам от LinkedList API нужны именно эти два пункта! Поэтому мы не можем просто использовать итераторы, нам нужно что-то новое: Курсоры.
Курсоры очень похожи на маленькие мигающие |, которые вы видите, редактируя текст на компьютере. По сути, они представляют собой позицию в последовательности (тексте), которую вы можете двигать (с помощью стрелок), и которая показывает место, где происходят изменения.
Смотрите, если я просто
нажму
Enter
весь
текст
сломается.
Извините, вы сейчас стоит за моей спиной и смотрите, как я это печатаю, да? Ну, теперь то логика понятна, правда? Правда.
Если вам не посчастливилось иметь клавиатуру с клавишей «Insert» и время от времени её нажимать, вы знаете, что технически есть две интерпретации курсоров: они могут находиться между элементами (символами) или над элементами. Я почти уверена, что никто никогда в жизни целенаправленно не нажимал клавишу «Insert», и что она существует исключительно, как Клавиша Страдания. Ведь совершенно очевидно, какая интерпретация лучше: курсоры находятся между элементами!
Довольно убедительная логика: я думаю, никто не станет со мной спорить.
Простите, что? В 2018 был RFC по добавлению Курсоров в LinkedList библиотеки Rust?
С помощью Cursor можно перемещаться по списку вперёд и назад и получать текущий элемент. С помощью CursorMut можно перемещаться по списку вперёд и назад, получать изменяемые ссылки на элементы, а также вставлять и удалять элементы до/после текущего (наряду с такими операциями, как разбиение и вставка).
Текущий элемент? Такой курсор может быть только над элементом, а не между ними! Не могу поверить, что они не вняли моей убедительной логике! Так что да, вы можете просто взять Cursor из стандартной библиотеки… подождите, в 2022 в Rust 1.60 Cursor всё ещё помечен, как нестабильный?
Эй, подождите:
Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.
ЭЙ, ПОДОЖДИТЕ. Это ведь противоречит тому, что написано в RFC??? Однако вся дока по методам продолжается ссылаться на «текущие» элементы… так, минутку, я ведь где-то уже видела этот псевдоэлемент раньше. Разве не я написала его в своём старом прототипе связного списка?
Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.
Что за хрень здесь творится? Я не шучу, я действительно прямо сейчас пытаюсь Читать Доки. Стандартная библиотека взяла дизайн, отличный от того, что я предложила в 2015, а затем просто скопи-пастила документацию из моего прототипа??? Они что, троллят меня за то, что я пишу книгу, как сильно я ненавижу связные списки??? Да, я написала этот прототип, чтобы продемонстрировать концепцию, чтобы мне разрешили добавить его в стандартную библиотеку и сделать LinkedList не таким бесполезным. Но… простите мой французский, это что за хрень?
Ладно, знаете, очевидно, что стандартная библиотека одобрила мой дизайн, как объективно лучший, так что именно его мы и будем использовать. А, кроме того, я целую главу буду писать с нуля свою же библиотеку, что меня полностью устраивает!
Вот полный текст документации верхнего уровня, которую я написала:
Курсоры похожи на итераторы, за тем исключением, что могут перемещаться вперёд-и-назад и безопасно менять список в процессе перемещения. Это возможно благодаря тому, что время жизни возвращаемых ссылок совпадает с временем жизни курсоров, а не нижележащих списков. Это значит, что курсоры не могут вернуть несколько элементов за раз.
Курсоры всегда располагаются между двумя элементами в списке и нумеруются циклически. Чтобы это работало, между концом и началом списка существует специальный «псевдоэлемент», который возвращает None.
Будучи созданными, курсоры находятся между псевдоэлементом и передним элементом списка. Таким образом, вызов next вернёт передний элемент списка, а вызов prev вернёт None. Повторный вызов prev вернёт хвост.
Мило, хотя мы вроде бы договорились, что от «сторожевого узла» больше вреда, чем пользы, в итоге мы всё равно пришли к семантике, которая «притворяется», что сторожевой узел существует и позволяет нам перескакивать на другой конец списка.
Ещё раз пролистывает свои старые API
fn splice(&mut self, other: &mut LinkedList<T>)
Вставляет содержимое целого списка прямо после курсора.
О, да, начинаю вспоминать. Я писала это в жутком расстройстве из-за комбинаторного взрыва и пыталась придумать, как сделать так, чтобы была только одна копия каждой операции. К сожалению, это… семантически проблематично. Смотрите, когда пользовать вставляет один список в другой, ему может быть надо, чтобы курсор остался перед вставляемым списком или за ним. Вставляемый список может быть произвольно большим, поэтому разрешать только один способ и ожидать, что пользователь переберёт весь вставленный список, чтобы добраться до другого конца — это подлинная проблема.
We’re gonna have to rework this design from the ground up after all. What does our Cursor type need? Well it needs to:
Похоже, нам придётся заново разработать весь дизайн. Что должен делать наш тип Cursor? Ну, он должен:
указывать между двумя элементами
отслеживать «индекс» следующего элемента — в качестве удобной небольшой функции
обновлять сам список, чтобы менять значения front/back/len
Как вы можете указывать между двумя элементами? Ладно, вы не можете. Вы просто указываете на «следующий» элемент. Так что да, несмотря на то. что мы подразумеваем семантику «курсор между элементами», на самом деле мы реализуем «курсор над элементом» и просто притворяемся, что всё происходит перед этой точкой, или за ней.
Но для этого есть причина! В сценарии вставки пользователь может выбрать, должен ли курсор оказаться за вставляемым списком или перед ним… но всё это ужасно трудно выразить с помощью стандартного API! У них есть splice_after и splice_before, но они не меняют позицию курсора, поэтому нам потребуются также splice_after_before и splice_after_after…
Подождите, я шучу. В стандартном API вы можете выбрать узел, где хотите оказаться и затем просто вызывать splice_after/splice_before в зависимости от того, что вам нужно.
прищуривается
Хм, а стандартный API действительно хорош.
пробегает код глазами
Правда, стандартный API действительно хорош.
Ладно, к чёрту всё, будем реализовывать RFC. Или по крайней мере самые интересные его части.
У меня есть пара претензий к терминологии, которую использует стандартная библиотека, но курсоры всегда немного сбивают с толку: iter().next_back() означает по сути back() (то есть назад), что в целом правильно, но каждый вызов next_back() делает нас ближе к переднему элементу, а это значит, что мы двигаемся не назад, а вперёд! Когда я начинаю слишком много думать об этом парадоксе, у меня начинает болеть голова. Так что я могу понять необходимость в другой терминологии, чтобы избежать таких проблем.
В стандартному API операции описаны, как «before» (в сторону переднего элемента) и «after» (в сторону заднего элемента), а вместо next/back_next… есть вызовы move_next и move_prev. ГРМ. Ладно, они позаимствовали терминологию итераторов, но, в конце концов next не вызывает неверных ассоциаций по отношению к front/back. И, по аналогии с итераторами, помогает понять, как всё работает.
С этим можно работать.
Реализация Курсоров
Мы займёмся типом CursorMut из стандартной библиотеки, поскольку неизменяемая версия на самом деле не так интересна. Как и в оригинальном дизайне, у неё есть «псевдоэлемент», который содержит None, чтобы обозначить начало/конец списка, и через который можно «пройти», чтобы перепрыгнуть на другую сторону списка. Для реализации нам потребуются:
Указатель на текущий узел
Указатель на список
Текущий индекс
Так, а каково должно быть значение индекса, когда мы указываем на «псевдоэлемент»?
хмурит брови… проверяет стандартную библиотеку… отвергает решение из стандартной библиотеки…
Ладно, вполне логично, что index Курсора возвращает Option<usize>. Стандартная реализация делает кучу ненужных вещей, чтобы избежать хранения индекса, как Option, но… у нас же связный список, это вполне нормально. Так же в стандартной библиотеке есть функции cursor_front/cursor_back, которые передвигают курсор на передний/задний элементы, что кажется интуитивным, пока речь не заходит о пустом списке.
Вы можете написать такой код, какой захотите, но я собираюсь выкинуть весь повторяющийся мусор, все граничные случае и сделать простой метод cursor_mut, который начинается в псевдоэлементе, и который можно передвигать вперёд/назад, чтобы получить нужную позицию. И, если, очень хотите, можете написать свой cursor_front.
Приступим:
pub struct CursorMut<'a, T> { cur: Link<T>, list: &'a mut LinkedList<T>, index: Option<usize>, }
Всё довольно просто: одно поле на каждый пункт нашего списка! Теперь напишем метод cursor_mut:
impl<T> LinkedList<T> { pub fn cursor_mut(&mut self) -> CursorMut<T> { CursorMut { list: self, cur: None, index: None, } } }
Поскольку мы стартуем на псевдоэлементе, мы можем проинициализировать все поля значением None: красиво и и просто! Далее, перемещение:
impl<'a, T> CursorMut<'a, T> { pub fn index(&self) -> Option<usize> { self.index } pub fn move_next(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к следующему (в сторону заднего) self.cur = (*cur.as_ptr()).back; if self.cur.is_some() { *self.index.as_mut().unwrap() += 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный передний элемент, так что перемещаемся на него! self.cur = self.list.front; self.index = Some(0) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } } }
Итак, есть 4 интересные варианта:
Обычный вариант
Обычный вариант, но мы перемещаемся к псевдоэлементу
Вариант псевдоэлемента, когда мы перемещаемся к переднему элементу
Вариант псевдоэлемента, но список пуст, так что ничего не делаем
В move_prev точно такая же логика, но мы меняем front/back местами и инвертируем изменение индекса:
pub fn move_prev(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к предыдущему (в сторону переднего) self.cur = (*cur.as_ptr()).front; if self.cur.is_some() { *self.index.as_mut().unwrap() -= 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный задний элемент, так что перемещаемся на него! self.cur = self.list.back; self.index = Some(self.list.len - 1) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } }
Добавим методы для просмотра элементов вокруг курсора: current, peek_next и peek_prev. Очень важное примечание: эти методы должны заимствовать наш курсор через &mut self и результаты должны быть привязаны к этому заимствованию. Мы не можем позволить пользователю получить несколько копий изменяемой ссылки и мы не можем позволить ему использовать любой из методов insert/remove/split/splice, пока у него есть такая ссылка!
К счастью, неявное выведение времени жизни работает в Rust именно так, как нужно, поэтому мы по умолчанию пишем правильный код!
pub fn current(&mut self) -> Option<&mut T> { unsafe { self.cur.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).front) .map(|node| &mut (*node.as_ptr()).elem) } }
Даже думать не пришлось, всю работу сделали методы Option и (опущенные) ошибки компилятора. Я была настроена скептически по отношению к Option<NonNull>, но, будь я проклята, этот тип позволил мне писать код на автопилоте. Я потратила слишком много времени на написание коллекций на основе массивов, где вам никогда не приходится использовать Option, так что мне есть, с чем сравнивать! ((*node.as_ptr()), конечно, выглядит кринжово, но, с другой стороны, для вас это всего лишь обычные указатели Rust…)
Далее у нас есть выбор: мы можем сразу заняться split и splice, центральной темой этого API, или мы можем сделать небольшой шажок, реализовав insert/remove для одного элемента. У меня такое чувство, что нам придётся реализовать insert/remove через split и splice, так что… давайте попробуем и посмотрим, как ляжет карта (честно говоря, понятия не имею, пока пишу эти строки).
Разбиение
Итак, split_before и split_after возвращают всё до/после текущего элемента в виде LinkedList (и останавливаются на псевдоэлементе, а если они сразу находятся на псевдоэлементе, то возвращают весь список, а курсор после этого указывает на пустой список).
прищуривается ладно, здесь и правда есть нетривиальная логика, так что давайте разобьём её на части.
Я вижу 4 потенциально интересных варианта для split_before:
Обычный вариант
Обычный вариант, но предыдущий элемент является псевдоэлементом
Вариант псевдоэлемента, где мы возвращаем весь список, а оставляем пустой
Вариант псевдоэлемента, но список пустой, так что ничего не делаем и возвращаем пустой список
Начнём с граничных вариантов. Третий вариант, мне кажется, самый простой.
mem::replace(self.list, LinkedList::new())
Так? Список становится пустым, мы возвращаем весь предыдущий список и теперь наши поля хранят None, так что нам нечего исправлять. Прекрасно. О, кстати, этот метод закрывает и четвёртый вариант!
Так, теперь обычные варианты… ладно, здесь мне потребуется несколько ASCII-диаграмм. В самом общем случае, у нас есть что-то такое:
list.front -> A <-> B <-> C <-> D <- list.back ^ cur
А мы хотим получить вот это:
list.front -> C <-> D <- list.back ^ cur return.front -> A <-> B <- return.back
Так что нам надо разорвать связь между cur и prev, и… боже, сколько всего надо менять. Ладно, мне просто надо разбить весь путь на отдельные шаги, чтобы быть уверенной, что я нигде не ошиблась. Будет чуток многословно, но я по крайней мере ничего не пропущу:
pub fn split_before(&mut self) -> LinkedList<T> { if let Some(cur) = self.cur { // Указываем на реальный элемент, так что список не пустой. unsafe { // Текущее состояние let old_len = self.list.len; let old_idx = self.index.unwrap(); let prev = (*cur.as_ptr()).front; // Во что должен превратиться self let new_len = old_len - old_idx; let new_front = self.cur; let new_back = self.list.back; let new_idx = Some(0); // Что мы должны вернуть let output_len = old_len - new_len; let output_front = self.list.front; let output_back = prev; // Разрываем связь между cur и prev if let Some(prev) = prev { (*cur.as_ptr()).front = None; (*prev.as_ptr()).back = None; } // Создаём результат: self.list.len = new_len; self.list.front = new_front; self.list.back = new_back; self.index = new_idx; LinkedList { front: output_front, back: output_back, len: output_len, _boo: PhantomData, } } } else { // Мы на псевдолементе, просто меняем наш список на пустой. // Никаких других изменений состояния не нужно. std::mem::replace(self.list, LinkedList::new()) } }
Обратите внимание, что конструкция if-let помогает справиться с «обычным вариантом, когда предыдущий элемент — это псевдоэлемент»:
if let Some(prev) = prev { (*cur.as_ptr()).front = None; (*prev.as_ptr()).back = None; }
Если вы хотите, можете рассмотреть весь код, как единое целое и сделать такие оптимизации:
заменить два обращения к
(*cur.as_ptr()).frontна вызов(*cur.as_ptr()).front.take()заметить, что new_back не выполняет никакой работы, поэтому переменную можно удалить
Насколько я могу судить, оставшийся код должен работать. Узнаем, когда напишем тесты. (копи-пастим метод split_after)
Я больше не хочу совершать ошибки, я хочу писать самый надёжный код, который могу. Вот как я на самом деле разрабатывала коллекции: для начала разбивала задачу на тривиальные шаги и варианты, пока они не становились понятными и не помещались у меня в голове. Затем писала тонну тестов, чтобы быть уверенной, что не напортачила.
Поскольку большая часть моей работы с коллекциями крайней небезопасна, я, в целом, не могла полагаться на то, что компилятор обнаружит ошибки, а miri в то время ещё небыло! Поэтому мне приходилось изучать проблему, пока у меня не начинала болеть голова и стараться изо всех сил, чтобы Никогда Никогда Никогда не совершать ошибок.
Не пишите на Rust небезопасный код! Безопасный Rust гораздо лучше!!!
Вставка
Остался последний босс, с которым нужно сразиться — splice_before и splice_after. И в них, похоже, будет больше всего граничных случаев. Эти функции принимают на вход один LinkedList и вставляют его содержимое в наш список. Наш список может быть пустым, их список может быть пустым, нужно что-то решать с псевдоэлементами… вздыхает Давайте просто действовать шаг за шагом на примере splice_before.
Если их список пустой, ничего не делаем
Если наш список пустой, тогда их список становится нашим списком
Если мы указываем на псевдоэлемент, их список добавляется сзади (изменяя list.back)
Если мы указываем на первый элемент (0), их список добавляется спереди (изменяя list.front)
В других случаях, мы очень много возимся с указателями.
Общий случай:
input.front -> 1 <-> 2 <- input.back list.front -> A <-> B <-> C <- list.back ^ cur
Превращается в:
list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back
Так? Так. Будем писать… **ГЛУБОКО ВЗДЫХАЕТ И ПИШЕТ:
pub fn splice_before(&mut self, mut input: LinkedList<T>) { unsafe { if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { if let Some(0) = self.index { // Добавляем спереди, сравните с добавлением сзади (*cur.as_ptr()).front = input.back.take(); (*input.back.unwrap().as_ptr()).back = Some(cur); self.list.front = input.front.take(); // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; self.list.len += input.len; input.len = 0; } else { // Общий случай, никаких граничных случаев: // просто правим приватные поля let prev = (*cur.as_ptr()).front.unwrap(); let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*prev.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(prev); (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; self.list.len += input.len; input.len = 0; } } else if let Some(back) = self.list.back { // Мы на псевдоэлементе и список не пуст, добавляем сзади. // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! (*back.as_ptr()).back = input.front.take(); (*input.front.unwrap().as_ptr()).front = Some(back); self.list.back = input.back.take(); self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе *self.list = input; } } }
Этот код по настоящему ужасен и я ощущаю всю боль от выбора Option<NonNull>. Но многое можно исправить. Во-первых, эти две строки можно вынести в самый конец, поскольку они нужны всегда. (согласна, в некоторых сценариях они не обязательны, но ничего не ломают, а установка input.len вызвана, скорее, паранойей):
self.list.len += input.len; input.len = 0;
Использование перемещённого значения:
input
Ах, да, в случае «наш список пуст» мы перемещаем list. Заменим эту строку на вызов swap:
// Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input);
В этом случае операторы, меняющие значения self.list.len и input.len, не делают ничего, так как значения уже корректны, но они ничего и не ломают (и, в принципе, мы могли бы сделать в этом месте ранний возврат из функции).
Вызов unwrap вызван тем, что я рассматривала варианты в неудобном порядке. От него можно избавиться, если мы правильно зададим вопрос в операторе if-let:
if let Some(0) = self.index { } else { let prev = (*cur.as_ptr()).front.unwrap(); }
Корректировка индекса повторяется в обоих ветках, так что и её можно вынести наружу:
*self.index.as_mut().unwrap() += input.len;
Сложив всё воедино, получаем:
if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые if let Some(prev) = (*cur.as_ptr()).front { // Общий случай, никаких граничных случаев: // просто правим приватные поля let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*prev.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(prev); (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); } else { // Добавляем спереди, сравните с добавлением сзади (*cur.as_ptr()).front = input.back.take(); (*input.back.unwrap().as_ptr()).back = Some(cur); self.list.front = input.front.take(); } // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; } else if let Some(back) = self.list.back { // Мы на псевдоэлементе и список не пуст, добавляем сзади. // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! (*back.as_ptr()).back = input.front.take(); (*input.front.unwrap().as_ptr()).front = Some(back); self.list.back = input.back.take(); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь
Ладно, это всё ещё отстой, но, в основном из-за… нет, так, я только что нашла ошибку:
(*back.as_ptr()).back = input.front.take(); (*input.front.unwrap().as_ptr()).front = Some(back);
Мы вызываем take у input.front и затем, буквально на следующей строке вызываем unwrap! вздыхает и то же самое мы делаем в эквивалентном зеркальном методе. Мы бы нашли эту ошибку с помощью тестов, но сейчас я пытаюсь быть Идеальной и пишу код в режиме реального времени, так что я увидела эту ошибку только что. Вот что бывает, когда выполняешь работу не так, как привыкла, и не в том порядке. Даёшь больше ясности в коде!
// Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); if let Some(prev) = (*cur.as_ptr()).front { // Общий случай, никаких граничных случаев: // просто правим приватные поля (*prev.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(prev); (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); } else { // Нет предыдущего элемента, добавляем спереди (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); self.list.front = Some(in_front); } // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; } else if let Some(back) = self.list.back { // Мы на псевдоэлементе и список не пуст, добавляем сзади. let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*back.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(back); self.list.back = Some(in_back); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь
Ладно, с таким кодом уже можно смириться. Единственный его недостаток в том, что мы два раза инициализируем in_front/in_back (возможно мы могли бы поправить наши условия, но не суть). Подобный код мы бы написали и на C, но Option<NonNull> делает его многословным. С этим можно жить. По уму, надо сделать сырые указатели удобнее для решения таких задач. Но это выходит за рамки этой книги.
В любом случае, я абсолютно измучена, так что insert, remove и все остальные методы оставляю читателю в качестве упражнения.
Финальный код нашего курсора вместе с копи-пастой комбинаторных методов. Всё ли здесь правильно? Это я узнаю только после написания следующего раздела и тестирования этого монстра!
pub struct CursorMut<'a, T> { list: &'a mut LinkedList<T>, cur: Link<T>, index: Option<usize>, } impl<T> LinkedList<T> { pub fn cursor_mut(&mut self) -> CursorMut<T> { CursorMut { list: self, cur: None, index: None, } } } impl<'a, T> CursorMut<'a, T> { pub fn index(&self) -> Option<usize> { self.index } pub fn move_next(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к следующему (в сторону заднего) self.cur = (*cur.as_ptr()).back; if self.cur.is_some() { *self.index.as_mut().unwrap() += 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный передний элемент, так что перемещаемся на него! self.cur = self.list.front; self.index = Some(0) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } } pub fn move_prev(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к предыдущему (в сторону переднего) self.cur = (*cur.as_ptr()).front; if self.cur.is_some() { *self.index.as_mut().unwrap() -= 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный задний элемент, так что перемещаемся на него! self.cur = self.list.back; self.index = Some(self.list.len - 1) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } } pub fn current(&mut self) -> Option<&mut T> { unsafe { self.cur.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).front) .map(|node| &mut (*node.as_ptr()).elem) } } pub fn split_before(&mut self) -> LinkedList<T> { // У нас есть что-то такое: // // list.front -> A <-> B <-> C <-> D <- list.back // ^ // cur // // А мы хотим получить вот это: // // list.front -> C <-> D <- list.back // ^ // cur // // return.front -> A <-> B <- return.back // if let Some(cur) = self.cur { // Указываем на реальный элемент, так что список не пустой. unsafe { // Текущее состояние let old_len = self.list.len; let old_idx = self.index.unwrap(); let prev = (*cur.as_ptr()).front; // Во что должен превратиться self let new_len = old_len - old_idx; let new_front = self.cur; let new_back = self.list.back; let new_idx = Some(0); // Что мы должны вернуть let output_len = old_len - new_len; let output_front = self.list.front; let output_back = prev; // Разрываем связь между cur и prev if let Some(prev) = prev { (*cur.as_ptr()).front = None; (*prev.as_ptr()).back = None; } // Создаём результат: self.list.len = new_len; self.list.front = new_front; self.list.back = new_back; self.index = new_idx; LinkedList { front: output_front, back: output_back, len: output_len, _boo: PhantomData, } } } else { // Мы на псевдолементе, просто меняем наш список на пустой. // Никаких других изменений состояния не нужно. std::mem::replace(self.list, LinkedList::new()) } } pub fn split_after(&mut self) -> LinkedList<T> { // У нас есть что-то такое: // // list.front -> A <-> B <-> C <-> D <- list.back // ^ // cur // // // А мы хотим получить вот это: // // list.front -> A <-> B <- list.back // ^ // cur // // // return.front -> C <-> D <- return.back // if let Some(cur) = self.cur { // Указываем на реальный элемент, так что список не пустой. unsafe { // Текущее состояние let old_len = self.list.len; let old_idx = self.index.unwrap(); let next = (*cur.as_ptr()).back; // Во что должен превратиться self let new_len = old_idx + 1; let new_back = self.cur; let new_front = self.list.front; let new_idx = Some(old_idx); // Что мы должны вернуть let output_len = old_len - new_len; let output_front = next; let output_back = self.list.back; // Разрываем связь между cur и next if let Some(next) = next { (*cur.as_ptr()).back = None; (*next.as_ptr()).front = None; } // Создаём результат: self.list.len = new_len; self.list.front = new_front; self.list.back = new_back; self.index = new_idx; LinkedList { front: output_front, back: output_back, len: output_len, _boo: PhantomData, } } } else { // Мы на псевдолементе, просто меняем наш список на пустой. // Никаких других изменений состояния не нужно. std::mem::replace(self.list, LinkedList::new()) } } pub fn splice_before(&mut self, mut input: LinkedList<T>) { // Наше: // // input.front -> 1 <-> 2 <- input.back // // list.front -> A <-> B <-> C <- list.back // ^ // cur // // Превращается в: // // list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back // unsafe { // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); if let Some(prev) = (*cur.as_ptr()).front { // Общий случай, никаких граничных случаев: // просто правим приватные поля (*prev.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(prev); (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); } else { // Нет предыдущего элемента, добавляем спереди (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); self.list.front = Some(in_front); } // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; } else if let Some(back) = self.list.back { // Мы на псевдоэлементе и список не пуст, добавляем сзади. let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*back.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(back); self.list.back = Some(in_back); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь } } pub fn splice_after(&mut self, mut input: LinkedList<T>) { // Наше: // // input.front -> 1 <-> 2 <- input.back // // list.front -> A <-> B <-> C <- list.back // ^ // cur // // // Превращается в : // // list.front -> A <-> B <-> 1 <-> 2 <-> C <- list.back // ^ // cur // unsafe { // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); if let Some(next) = (*cur.as_ptr()).back { // Общий случай, никаких граничных случаев: // просто правим приватные поля (*next.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(next); (*cur.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(cur); } else { // Нет следующего элемента, добавляем сзади (*cur.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(cur); self.list.back = Some(in_back); } // Индекс не меняется } else if let Some(front) = self.list.front { // Мы на псевдоэлементе и список не пуст, добавляем спереди. let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*front.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(front); self.list.front = Some(in_front); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь } } }
Тестирование Курсоров
Время узнать, сколько ужасных и неловких ошибок я допустила в предыдущем разделе!
К несчастью, наш API отличается, как от стандартной библиотеки, так и от моей старой реализации, так что мне придётся собирать работающие тесты из них обеих. Эти тесты «позаимствуем» из стандартной реализации:
#[test] fn test_cursor_move_peek() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 1)); assert_eq!(cursor.peek_next(), Some(&mut 2)); assert_eq!(cursor.peek_prev(), None); assert_eq!(cursor.index(), Some(0)); cursor.move_prev(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 2)); assert_eq!(cursor.peek_next(), Some(&mut 3)); assert_eq!(cursor.peek_prev(), Some(&mut 1)); assert_eq!(cursor.index(), Some(1)); let mut cursor = m.cursor_mut(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 6)); assert_eq!(cursor.peek_next(), None); assert_eq!(cursor.peek_prev(), Some(&mut 5)); assert_eq!(cursor.index(), Some(5)); cursor.move_next(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 5)); assert_eq!(cursor.peek_next(), Some(&mut 6)); assert_eq!(cursor.peek_prev(), Some(&mut 4)); assert_eq!(cursor.index(), Some(4)); } #[test] fn test_cursor_mut_insert() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.splice_before(Some(7).into_iter().collect()); cursor.splice_after(Some(8).into_iter().collect()); // check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); cursor.splice_before(Some(9).into_iter().collect()); cursor.splice_after(Some(10).into_iter().collect()); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]); /* удаляем, сейчас не реализовано: let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); assert_eq!(cursor.remove_current(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(7)); cursor.move_prev(); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.remove_current(), Some(9)); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(10)); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]); */ let mut cursor = m.cursor_mut(); cursor.move_next(); let mut p: LinkedList<u32> = LinkedList::new(); p.extend([100, 101, 102, 103]); let mut q: LinkedList<u32> = LinkedList::new(); q.extend([200, 201, 202, 203]); cursor.splice_after(p); cursor.splice_before(q); check_links(&m); assert_eq!( m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6] ); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); let tmp = cursor.split_before(); assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); m = tmp; let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); let tmp = cursor.split_after(); assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]); } fn check_links<T>(_list: &LinkedList<T>) { // было бы неплохо написать! }
Момент истины!
cargo test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 1.03s Running unittests src\lib.rs running 14 tests test test::test_basic_front ... ok test test::test_basic ... ok test test::test_debug ... ok test test::test_iterator_mut_double_end ... ok test test::test_ord ... ok test test::test_cursor_move_peek ... FAILED test test::test_cursor_mut_insert ... FAILED test test::test_iterator ... ok test test::test_mut_iter ... ok test test::test_eq ... ok test test::test_rev_iter ... ok test test::test_iterator_double_end ... ok test test::test_hashmap ... ok test test::test_ord_nan ... ok failures: ---- test::test_cursor_move_peek stdout ---- thread 'test::test_cursor_move_peek' panicked at 'assertion failed: `(left == right)` left: `None`, right: `Some(1)`', src\lib.rs:1079:9 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace ---- test::test_cursor_mut_insert stdout ---- thread 'test::test_cursor_mut_insert' panicked at 'assertion failed: `(left == right)` left: `[200, 201, 202, 203, 10, 100, 101, 102, 103, 7, 1, 8, 2, 3, 4, 5, 6, 9]`, right: `[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]`', src\lib.rs:1153:9 failures: test::test_cursor_move_peek test::test_cursor_mut_insert test result: FAILED. 12 passed; 2 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
Признаюсь, я была немного самонадеянна и думала, что всё сделала правильно. Вот почему мы пишем тесты. Впрочем, может быть, я их просто неаккуратно скопи-пастила?
В чём первая ошибка?
let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 1)); assert_eq!(cursor.peek_next(), Some(&mut 2)); assert_eq!(cursor.peek_prev(), None); assert_eq!(cursor.index(), Some(0)); cursor.move_prev(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); // DIES HERE
Блин, я и правда накосячила с базовой функциональностью. Подождите,
Даже думать не пришлось, всю работу сделали методы Option и (опущенные) ошибки компилятора.
Что ж, я человек честный.
pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .map(|node| &mut (*node.as_ptr()).elem) } }
Да, это просто неправильно. Если self.cur равен None, мы не должны завершать проверку, мы должны также проверить self.list.front, потому что находимся над псевдоэлементом! Так что нам надо добавить or_else в цепочку вызов:
pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).back) .or_else(|| self.list.front) .map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { self.cur .and_then(|node| (*node.as_ptr()).front) .or_else(|| self.list.back) .map(|node| &mut (*node.as_ptr()).elem) } }
Помогло?
---- test::test_cursor_move_peek stdout ---- thread 'test::test_cursor_move_peek' panicked at 'assertion failed: `(left == right)` left: `Some(6)`, right: `None`', src\lib.rs:1078:9
Подождите, теперь ошибка сдвинулась на элемент назад. Ладно, мне надо остановить своё «даже думать не пришлось» в отношении peek, потому что, оказывается, всё намного сложнее, чем я представляла. Просто пытаться связать в цепочку все эти варианты — как мы видим, не работает. Давайте добавим явное условие if для псевдоэлемента и обычного элемента:
pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { let next = if let Some(cur) = self.cur { // Обычный вариант, пытаемся следовать заднему указателю текущего узла (*cur.as_ptr()).back } else { // Псевдоэлемент, пытаемся использовать передний указатель списка self.list.front }; // Возвращаем элемент, если следующий узел существует next.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { let prev = if let Some(cur) = self.cur { // Обычный вариант, пытаемся следовать переднему указателю текущего узла (*cur.as_ptr()).front } else { // Псевдоэлемент, пытаемся использовать задний указатель списка self.list.back }; // Возвращаем элемент, если предыдущий узел существует prev.map(|node| &mut (*node.as_ptr()).elem) } }
Ну, в этом коде я уверена!
failures: ---- test::test_cursor_mut_insert stdout ---- thread 'test::test_cursor_mut_insert' panicked at 'assertion failed: `(left == right)` left: `[200, 201, 202, 203, 10, 100, 101, 102, 103, 7, 1, 8, 2, 3, 4, 5, 6, 9]`, right: `[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6]`', src\lib.rs:1168:9 note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace failures: test::test_cursor_mut_insert test result: FAILED. 13 passed; 1 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s
Даааа. Что ж, осталась одна ошибка… уф.
Вы заметили, что я закомментировала часть кода, предназначенного для тестирования remove_current? Оказывается, я не обратила внимания, что этот тест меняет состояние. Давайте просто создадим новый список в том виде, в каком бы его оставил вызов remove_current:
let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 8, 2, 3, 4, 5, 6]);
cargo test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.70s Running unittests src\lib.rs running 14 tests test test::test_basic_front ... ok test test::test_basic ... ok test test::test_cursor_move_peek ... ok test test::test_eq ... ok test test::test_cursor_mut_insert ... ok test test::test_iterator ... ok test test::test_iterator_double_end ... ok test test::test_ord_nan ... ok test test::test_mut_iter ... ok test test::test_hashmap ... ok test test::test_debug ... ok test test::test_ord ... ok test test::test_iterator_mut_double_end ... ok test test::test_rev_iter ... ok test result: ok. 14 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.00s Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 803) - compile fail ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.12s
Эээй, только взгляните на… ладно, у уже начинаю параноить. Давайте аккуратно заполним check_links и протестируем его в miri:
fn check_links<T: Eq + std::fmt::Debug>(list: &LinkedList<T>) { let from_front: Vec<_> = list.iter().collect(); let from_back: Vec<_> = list.iter().rev().collect(); let re_reved: Vec<_> = from_back.into_iter().rev().collect(); assert_eq!(from_front, re_reved); }
Это лучшим способ проверки? Нет. Нормальный? Да.
$env:MIRIFLAGS="-Zmiri-tag-raw-pointers" cargo miri test Compiling linked-list v0.0.3 Finished test [unoptimized + debuginfo] target(s) in 0.25s Running unittests src\lib.rs running 14 tests test test::test_basic ... ok test test::test_basic_front ... ok test test::test_cursor_move_peek ... ok test test::test_cursor_mut_insert ... ok test test::test_debug ... ok test test::test_eq ... ok test test::test_hashmap ... ok test test::test_iterator ... ok test test::test_iterator_double_end ... ok test test::test_iterator_mut_double_end ... ok test test::test_mut_iter ... ok test test::test_ord ... ok test test::test_ord_nan ... ok test test::test_rev_iter ... ok test result: ok. 14 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out Doc-tests linked-list running 1 test test src\lib.rs - assert_properties::iter_mut_invariant (line 803) - compile fail ... ok test result: ok. 1 passed; 0 failed; 0 ignored; 0 measured; 0 filtered out; finished in 0.10s
ГОТОВО.
Готово.
У нас получилось. Мы сделали связный список офигенно продуктового уровня, практически со всеми функциями из стандартной библиотеки. Нам не хватает пары удобных методов? Никаких сомнений. Добавлю ли я их позже? Возможно!
Но Сейчас Я Очень Устала.
В любом случае. Мы победили.
Блин, подождите. Нам же нужно продуктовое качество. Ладно, последний финальный босс: clippy.
cargo clippy cargo clippy Checking linked-list v0.0.3 (C:\Users\ninte\dev\contain\linked-list) warning: redundant pattern matching, consider using `is_some()` --> src\lib.rs:189:19 | 189 | while let Some(_) = self.pop_front() { } | ----------^^^^^^^------------------- help: try this: `while self.pop_front().is_some()` | = note: `#[warn(clippy::redundant_pattern_matching)]` on by default = note: this will change drop order of the result, as well as all temporaries = note: add `#[allow(clippy::redundant_pattern_matching)]` if this is important = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_pattern_matching warning: method `into_iter` can be confused for the standard trait method `std::iter::IntoIterator::into_iter` --> src\lib.rs:210:5 | 210 | / pub fn into_iter(self) -> IntoIter<T> { 211 | | IntoIter { 212 | | list: self 213 | | } 214 | | } | |_____^ | = note: `#[warn(clippy::should_implement_trait)]` on by default = help: consider implementing the trait `std::iter::IntoIterator` or choosing a less ambiguous method name = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#should_implement_trait warning: redundant pattern matching, consider using `is_some()` --> src\lib.rs:228:19 | 228 | while let Some(_) = self.pop_front() { } | ----------^^^^^^^------------------- help: try this: `while self.pop_front().is_some()` | = note: this will change drop order of the result, as well as all temporaries = note: add `#[allow(clippy::redundant_pattern_matching)]` if this is important = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#redundant_pattern_matching warning: re-implementing `PartialEq::ne` is unnecessary --> src\lib.rs:275:5 | 275 | / fn ne(&self, other: &Self) -> bool { 276 | | self.len() != other.len() || self.iter().ne(other) 277 | | } | |_____^ | = note: `#[warn(clippy::partialeq_ne_impl)]` on by default = help: for further information visit https://rust-lang.github.io/rust-clippy/master/index.html#partialeq_ne_impl warning: `linked-list` (lib) generated 4 warnings Finished dev [unoptimized + debuginfo] target(s) in 0.29s
Ладно, clippy, добьём.
Предупреждение 1 (и 3): мы используем while let Some(_) = вместо while .is_some(). Тело цикла пустое, так что писать можно как угодно, но, хорошо, clippy, я сделаю по твоему.
Предупреждение 2: У нас уже есть унаследованный метод into_iter. Подождите, что… проверяет стандартную библиотеку… ладно, очко уходит clippy. IntoIterator уже есть в прелюдии (и по сути является языковым примитивом), так что нам не нужна своя версия into_iter.
Предупреждение 4: мы скопировали кусок странного карго-кода из стандартной библиотеки. пожимает плечами ладно, просто удалю его.
cargo clippy Finished dev [unoptimized + debuginfo] target(s) in 0.00s
Прекрасно. Ещё одно, прежде чем мы сможем считать наш код продуктовым: fmt.
cargo fmt
…так, он добавил несколько новый строк и удалил несколько конечных пробелов. Ничего интересного.
НАКОНЕЦ, МЫ И ПРАВДА ЗАКОНЧИЛИ!!!
Финальный код
Не могу поверить, что заставила вас пройти через переработку std::collections::LinkedList от начала и до конца, с разбором всех ошибок, которые я сделала.
Ну, моя работа завершена, книга готова и я, наконец, могу отдохнуть.
Хорошо, вот 1200 строк нашего нового кода во всей красе. Это должен быть тот же код, что и в коммите.
Позже я немного его отполирую, документирую, и опубликую версию 0.1.0.
use std::cmp::Ordering; use std::fmt::{self, Debug}; use std::hash::{Hash, Hasher}; use std::iter::FromIterator; use std::ptr::NonNull; use std::marker::PhantomData; pub struct LinkedList<T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<T>, } type Link<T> = Option<NonNull<Node<T>>>; struct Node<T> { front: Link<T>, back: Link<T>, elem: T, } pub struct Iter<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a T>, } pub struct IterMut<'a, T> { front: Link<T>, back: Link<T>, len: usize, _boo: PhantomData<&'a mut T>, } pub struct IntoIter<T> { list: LinkedList<T>, } pub struct CursorMut<'a, T> { cur: Link<T>, list: &'a mut LinkedList<T>, index: Option<usize>, } impl<T> LinkedList<T> { pub fn new() -> Self { Self { front: None, back: None, len: 0, _boo: PhantomData, } } pub fn push_front(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { front: None, back: None, elem, }))); if let Some(old) = self.front { // Вставляем новый передний узел перед старым (*old.as_ptr()).front = Some(new); (*new.as_ptr()).back = Some(old); } else { // Если переднего узла нет, у нас пустой список и нам надо // установить и значение заднего узла. debug_assert!(self.back.is_none()); debug_assert!(self.front.is_none()); debug_assert!(self.len == 0); self.back = Some(new); } // Этот код выполняется всегда! self.front = Some(new); self.len += 1; } } pub fn push_back(&mut self, elem: T) { // БЕЗОПАСНОСТЬ: это связный список, что вы делаете? unsafe { let new = NonNull::new_unchecked(Box::into_raw(Box::new(Node { back: None, front: None, elem, }))); if let Some(old) = self.back { // Вставляем новый задний узел перед старым (*old.as_ptr()).back = Some(new); (*new.as_ptr()).front = Some(old); } else { // Если заднего узла нет, у нас пустой список и нам надо // установить и значение переднего узла. self.front = Some(new); } // Этот код выполняется всегда! self.back = Some(new); self.len += 1; } } pub fn pop_front(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть передний узел. self.front.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым передним узлом. self.front = boxed_node.back; if let Some(new) = self.front { // Убираем ссылку переднего узла на удалённый узел. (*new.as_ptr()).front = None; } else { // Если передний узел равен null, значит, список пустой! debug_assert!(self.len == 1); self.back = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn pop_back(&mut self) -> Option<T> { unsafe { // Будем что-то делать, только если у списка есть задний узел. self.back.map(|node| { // Возвращаем к жизни Box, так что можно извлечь и уничтожить его // значение (Box магически делает это за нас). let boxed_node = Box::from_raw(node.as_ptr()); let result = boxed_node.elem; // Делаем следующий узел новым задним узлом. self.back = boxed_node.front; if let Some(new) = self.back { // Убираем ссылку заднего узла на удалённый узел. (*new.as_ptr()).back = None; } else { // Если задний узел равен null, значит, список пустой! self.front = None; } self.len -= 1; result // Здесь Box неявным образом освобождается, потому что больше нет T. }) } } pub fn front(&self) -> Option<&T> { unsafe { self.front.map(|node| &(*node.as_ptr()).elem) } } pub fn front_mut(&mut self) -> Option<&mut T> { unsafe { self.front.map(|node| &mut (*node.as_ptr()).elem) } } pub fn back(&self) -> Option<&T> { unsafe { self.back.map(|node| &(*node.as_ptr()).elem) } } pub fn back_mut(&mut self) -> Option<&mut T> { unsafe { self.back.map(|node| &mut (*node.as_ptr()).elem) } } pub fn len(&self) -> usize { self.len } pub fn is_empty(&self) -> bool { self.len == 0 } pub fn clear(&mut self) { // О, смотрите, это снова drop while self.pop_front().is_some() { } } pub fn iter(&self) -> Iter<'_, T> { Iter { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn iter_mut(&mut self) -> IterMut<'_, T> { IterMut { front: self.front, back: self.back, len: self.len, _boo: PhantomData, } } pub fn cursor_mut(&mut self) -> CursorMut<'_, T> { CursorMut { list: self, cur: None, index: None, } } } impl<T> Drop for LinkedList<T> { fn drop(&mut self) { // Вызываем pop, пока есть элементы while self.pop_front().is_some() { } } } impl<T> Default for LinkedList<T> { fn default() -> Self { Self::new() } } impl<T: Clone> Clone for LinkedList<T> { fn clone(&self) -> Self { let mut new_list = Self::new(); for item in self { new_list.push_back(item.clone()); } new_list } } impl<T> Extend<T> for LinkedList<T> { fn extend<I: IntoIterator<Item = T>>(&mut self, iter: I) { for item in iter { self.push_back(item); } } } impl<T> FromIterator<T> for LinkedList<T> { fn from_iter<I: IntoIterator<Item = T>>(iter: I) -> Self { let mut list = Self::new(); list.extend(iter); list } } impl<T: Debug> Debug for LinkedList<T> { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self).finish() } } impl<T: PartialEq> PartialEq for LinkedList<T> { fn eq(&self, other: &Self) -> bool { self.len() == other.len() && self.iter().eq(other) } } impl<T: Eq> Eq for LinkedList<T> { } impl<T: PartialOrd> PartialOrd for LinkedList<T> { fn partial_cmp(&self, other: &Self) -> Option<Ordering> { self.iter().partial_cmp(other) } } impl<T: Ord> Ord for LinkedList<T> { fn cmp(&self, other: &Self) -> Ordering { self.iter().cmp(other) } } impl<T: Hash> Hash for LinkedList<T> { fn hash<H: Hasher>(&self, state: &mut H) { self.len().hash(state); for item in self { item.hash(state); } } } impl<'a, T> IntoIterator for &'a LinkedList<T> { type IntoIter = Iter<'a, T>; type Item = &'a T; fn into_iter(self) -> Self::IntoIter { self.iter() } } impl<'a, T> Iterator for Iter<'a, T> { type Item = &'a T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &(*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for Iter<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &(*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for Iter<'a, T> { fn len(&self) -> usize { self.len } } impl<'a, T> IntoIterator for &'a mut LinkedList<T> { type IntoIter = IterMut<'a, T>; type Item = &'a mut T; fn into_iter(self) -> Self::IntoIter { self.iter_mut() } } impl<'a, T> Iterator for IterMut<'a, T> { type Item = &'a mut T; fn next(&mut self) -> Option<Self::Item> { // Хотя условие self.front == self.back кажется очевидным, // оно не подходит для возврата последнего элемента! Подобный код // работает только с массивами из-за указателя «на элемент, следующий // за последним» if self.len > 0 { // Мы могли бы извлечь значение из front, но так быстрее и безопаснее self.front.map(|node| unsafe { self.len -= 1; self.front = (*node.as_ptr()).back; &mut (*node.as_ptr()).elem }) } else { None } } fn size_hint(&self) -> (usize, Option<usize>) { (self.len, Some(self.len)) } } impl<'a, T> DoubleEndedIterator for IterMut<'a, T> { fn next_back(&mut self) -> Option<Self::Item> { if self.len > 0 { self.back.map(|node| unsafe { self.len -= 1; self.back = (*node.as_ptr()).front; &mut (*node.as_ptr()).elem }) } else { None } } } impl<'a, T> ExactSizeIterator for IterMut<'a, T> { fn len(&self) -> usize { self.len } } impl<T> IntoIterator for LinkedList<T> { type IntoIter = IntoIter<T>; type Item = T; fn into_iter(self) -> Self::IntoIter { IntoIter { list: self } } } impl<T> Iterator for IntoIter<T> { type Item = T; fn next(&mut self) -> Option<Self::Item> { self.list.pop_front() } fn size_hint(&self) -> (usize, Option<usize>) { (self.list.len, Some(self.list.len)) } } impl<T> DoubleEndedIterator for IntoIter<T> { fn next_back(&mut self) -> Option<Self::Item> { self.list.pop_back() } } impl<T> ExactSizeIterator for IntoIter<T> { fn len(&self) -> usize { self.list.len } } impl<'a, T> CursorMut<'a, T> { pub fn index(&self) -> Option<usize> { self.index } pub fn move_next(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к следующему (в сторону заднего) self.cur = (*cur.as_ptr()).back; if self.cur.is_some() { *self.index.as_mut().unwrap() += 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный передний элемент, так что перемещаемся на него! self.cur = self.list.front; self.index = Some(0) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } } pub fn move_prev(&mut self) { if let Some(cur) = self.cur { unsafe { // Мы на реальном элементе, двигаемся к предыдущему (в сторону переднего) self.cur = (*cur.as_ptr()).front; if self.cur.is_some() { *self.index.as_mut().unwrap() -= 1; } else { // Мы попали на псевдоэлемент, убираем индекс self.index = None; } } } else if !self.list.is_empty() { // Мы на псевдоэлементе и у нас есть реальный задний элемент, так что перемещаемся на него! self.cur = self.list.back; self.index = Some(self.list.len - 1) } else { // Мы на псевдоэлементе, но никаких других элементов нет... ничего не делаем. } } pub fn current(&mut self) -> Option<&mut T> { unsafe { self.cur.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_next(&mut self) -> Option<&mut T> { unsafe { let next = if let Some(cur) = self.cur { // Обычный вариант, пытаемся следовать заднему указателю текущего узла (*cur.as_ptr()).back } else { // Псевдоэлемент, пытаемся использовать передний указатель списка self.list.front }; // Возвращаем элемент, если следующий узел существует next.map(|node| &mut (*node.as_ptr()).elem) } } pub fn peek_prev(&mut self) -> Option<&mut T> { unsafe { let prev = if let Some(cur) = self.cur { // Normal case, try to follow the cur node's front pointer // Обычный вариант, пытаемся следовать переднему указателю текущего узла (*cur.as_ptr()).front } else { // Псевдоэлемент, пытаемся использовать задний указатель списка self.list.back }; // Возвращаем элемент, если предыдущий узел существует prev.map(|node| &mut (*node.as_ptr()).elem) } } pub fn split_before(&mut self) -> LinkedList<T> { // У нас есть что-то такое: // // list.front -> A <-> B <-> C <-> D <- list.back // ^ // cur // // А мы хотим получить вот это: // // list.front -> C <-> D <- list.back // ^ // cur // // return.front -> A <-> B <- return.back // if let Some(cur) = self.cur { // Указываем на реальный элемент, так что список не пустой. unsafe { // Текущее состояние let old_len = self.list.len; let old_idx = self.index.unwrap(); let prev = (*cur.as_ptr()).front; // Во что должен превратиться self let new_len = old_len - old_idx; let new_front = self.cur; let new_back = self.list.back; let new_idx = Some(0); // Что мы должны вернуть let output_len = old_len - new_len; let output_front = self.list.front; let output_back = prev; // Разрываем связь между cur и prev if let Some(prev) = prev { (*cur.as_ptr()).front = None; (*prev.as_ptr()).back = None; } // Создаём результат: self.list.len = new_len; self.list.front = new_front; self.list.back = new_back; self.index = new_idx; LinkedList { front: output_front, back: output_back, len: output_len, _boo: PhantomData, } } } else { // Мы на псевдолементе, просто меняем наш список на пустой. // Никаких других изменений состояния не нужно. std::mem::replace(self.list, LinkedList::new()) } } pub fn split_after(&mut self) -> LinkedList<T> { // У нас есть что-то такое: // // list.front -> A <-> B <-> C <-> D <- list.back // ^ // cur // // // А мы хотим получить вот это: // // list.front -> A <-> B <- list.back // ^ // cur // // // return.front -> C <-> D <- return.back // if let Some(cur) = self.cur { // Указываем на реальный элемент, так что список не пустой. unsafe { // Текущее состояние let old_len = self.list.len; let old_idx = self.index.unwrap(); let next = (*cur.as_ptr()).back; // Во что должен превратиться self let new_len = old_idx + 1; let new_back = self.cur; let new_front = self.list.front; let new_idx = Some(old_idx); // Что мы должны вернуть let output_len = old_len - new_len; let output_front = next; let output_back = self.list.back; // Разрываем связь между cur и next if let Some(next) = next { (*cur.as_ptr()).back = None; (*next.as_ptr()).front = None; } // Создаём результат: self.list.len = new_len; self.list.front = new_front; self.list.back = new_back; self.index = new_idx; LinkedList { front: output_front, back: output_back, len: output_len, _boo: PhantomData, } } } else { // Мы на псевдолементе, просто меняем наш список на пустой. // Никаких других изменений состояния не нужно. std::mem::replace(self.list, LinkedList::new()) } } pub fn splice_before(&mut self, mut input: LinkedList<T>) { // Наше: // // input.front -> 1 <-> 2 <- input.back // // list.front -> A <-> B <-> C <- list.back // ^ // cur // // Превращается в: // // list.front -> A <-> 1 <-> 2 <-> B <-> C <- list.back // unsafe { // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); if let Some(prev) = (*cur.as_ptr()).front { // Общий случай, никаких граничных случаев: // просто правим приватные поля (*prev.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(prev); (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); } else { // Нет предыдущего элемента, добавляем спереди (*cur.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(cur); self.list.front = Some(in_front); } // Индекс увеличивается на длину входного списка *self.index.as_mut().unwrap() += input.len; } else if let Some(back) = self.list.back { // Мы на псевдоэлементе и список не пуст, добавляем сзади. let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*back.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(back); self.list.back = Some(in_back); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь } } pub fn splice_after(&mut self, mut input: LinkedList<T>) { // Наше: // // input.front -> 1 <-> 2 <- input.back // // list.front -> A <-> B <-> C <- list.back // ^ // cur // // // Превращается в : // // list.front -> A <-> B <-> 1 <-> 2 <-> C <- list.back // ^ // cur // unsafe { // Мы можем вызывать для входных указателей либо `take`, // либо `mem::forget`. Take корректнее, если мы используем // собственный аллокатор или что-то, что тоже требует очистки! if input.is_empty() { // Пустой входной список, ничего не делаем } else if let Some(cur) = self.cur { // Оба списка не пустые let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); if let Some(next) = (*cur.as_ptr()).back { // Общий случай, никаких граничных случаев: // просто правим приватные поля (*next.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(next); (*cur.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(cur); } else { // Нет следующего элемента, добавляем сзади (*cur.as_ptr()).back = Some(in_front); (*in_front.as_ptr()).front = Some(cur); self.list.back = Some(in_back); } // Индекс не меняется } else if let Some(front) = self.list.front { // Мы на псевдоэлементе и список не пуст, добавляем спереди. let in_front = input.front.take().unwrap(); let in_back = input.back.take().unwrap(); (*front.as_ptr()).front = Some(in_back); (*in_back.as_ptr()).back = Some(front); self.list.front = Some(in_front); } else { // Наш список пуст, заменяем его на входной, остаёмся на псевдоэлементе std::mem::swap(self.list, &mut input); } self.list.len += input.len; // Не обязательно, но вежливо input.len = 0; // input освобождается здесь } } } unsafe impl<T: Send> Send for LinkedList<T> {} unsafe impl<T: Sync> Sync for LinkedList<T> {} unsafe impl<'a, T: Send> Send for Iter<'a, T> {} unsafe impl<'a, T: Sync> Sync for Iter<'a, T> {} unsafe impl<'a, T: Send> Send for IterMut<'a, T> {} unsafe impl<'a, T: Sync> Sync for IterMut<'a, T> {} #[allow(dead_code)] fn assert_properties() { fn is_send<T: Send>() {} fn is_sync<T: Sync>() {} is_send::<LinkedList<i32>>(); is_sync::<LinkedList<i32>>(); is_send::<IntoIter<i32>>(); is_sync::<IntoIter<i32>>(); is_send::<Iter<i32>>(); is_sync::<Iter<i32>>(); is_send::<IterMut<i32>>(); is_sync::<IterMut<i32>>(); fn linked_list_covariant<'a, T>(x: LinkedList<&'static T>) -> LinkedList<&'a T> { x } fn iter_covariant<'i, 'a, T>(x: Iter<'i, &'static T>) -> Iter<'i, &'a T> { x } fn into_iter_covariant<'a, T>(x: IntoIter<&'static T>) -> IntoIter<&'a T> { x } /// ```compile_fail /// use lists::linked_list::IterMut; /// /// fn iter_mut_covariant<'i, 'a, T>(x: IterMut<'i, &'static T>) -> IterMut<'i, &'a T> { x } /// ``` fn iter_mut_invariant() {} } #[cfg(test)] mod test { use super::LinkedList; fn generate_test() -> LinkedList<i32> { list_from(&[0, 1, 2, 3, 4, 5, 6]) } fn list_from<T: Clone>(v: &[T]) -> LinkedList<T> { v.iter().map(|x| (*x).clone()).collect() } #[test] fn test_basic_front() { let mut list = LinkedList::new(); // Пытаемся сломать пустой список assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Пытаемся сломать список из одного элемента list.push_front(10); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); // Всё перемешиваем list.push_front(10); assert_eq!(list.len(), 1); list.push_front(20); assert_eq!(list.len(), 2); list.push_front(30); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(30)); assert_eq!(list.len(), 2); list.push_front(40); assert_eq!(list.len(), 3); assert_eq!(list.pop_front(), Some(40)); assert_eq!(list.len(), 2); assert_eq!(list.pop_front(), Some(20)); assert_eq!(list.len(), 1); assert_eq!(list.pop_front(), Some(10)); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); assert_eq!(list.pop_front(), None); assert_eq!(list.len(), 0); } #[test] fn test_basic() { let mut m = LinkedList::new(); assert_eq!(m.pop_front(), None); assert_eq!(m.pop_back(), None); assert_eq!(m.pop_front(), None); m.push_front(1); assert_eq!(m.pop_front(), Some(1)); m.push_back(2); m.push_back(3); assert_eq!(m.len(), 2); assert_eq!(m.pop_front(), Some(2)); assert_eq!(m.pop_front(), Some(3)); assert_eq!(m.len(), 0); assert_eq!(m.pop_front(), None); m.push_back(1); m.push_back(3); m.push_back(5); m.push_back(7); assert_eq!(m.pop_front(), Some(1)); let mut n = LinkedList::new(); n.push_front(2); n.push_front(3); { assert_eq!(n.front().unwrap(), &3); let x = n.front_mut().unwrap(); assert_eq!(*x, 3); *x = 0; } { assert_eq!(n.back().unwrap(), &2); let y = n.back_mut().unwrap(); assert_eq!(*y, 2); *y = 1; } assert_eq!(n.pop_front(), Some(0)); assert_eq!(n.pop_front(), Some(1)); } #[test] fn test_iterator() { let m = generate_test(); for (i, elt) in m.iter().enumerate() { assert_eq!(i as i32, *elt); } let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); let mut it = n.iter(); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next().unwrap(), &4); assert_eq!(it.size_hint(), (0, Some(0))); assert_eq!(it.next(), None); } #[test] fn test_iterator_double_end() { let mut n = LinkedList::new(); assert_eq!(n.iter().next(), None); n.push_front(4); n.push_front(5); n.push_front(6); let mut it = n.iter(); assert_eq!(it.size_hint(), (3, Some(3))); assert_eq!(it.next().unwrap(), &6); assert_eq!(it.size_hint(), (2, Some(2))); assert_eq!(it.next_back().unwrap(), &4); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next_back().unwrap(), &5); assert_eq!(it.next_back(), None); assert_eq!(it.next(), None); } #[test] fn test_rev_iter() { let m = generate_test(); for (i, elt) in m.iter().rev().enumerate() { assert_eq!(6 - i as i32, *elt); } let mut n = LinkedList::new(); assert_eq!(n.iter().rev().next(), None); n.push_front(4); let mut it = n.iter().rev(); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(it.next().unwrap(), &4); assert_eq!(it.size_hint(), (0, Some(0))); assert_eq!(it.next(), None); } #[test] fn test_mut_iter() { let mut m = generate_test(); let mut len = m.len(); for (i, elt) in m.iter_mut().enumerate() { assert_eq!(i as i32, *elt); len -= 1; } assert_eq!(len, 0); let mut n = LinkedList::new(); assert!(n.iter_mut().next().is_none()); n.push_front(4); n.push_back(5); let mut it = n.iter_mut(); assert_eq!(it.size_hint(), (2, Some(2))); assert!(it.next().is_some()); assert!(it.next().is_some()); assert_eq!(it.size_hint(), (0, Some(0))); assert!(it.next().is_none()); } #[test] fn test_iterator_mut_double_end() { let mut n = LinkedList::new(); assert!(n.iter_mut().next_back().is_none()); n.push_front(4); n.push_front(5); n.push_front(6); let mut it = n.iter_mut(); assert_eq!(it.size_hint(), (3, Some(3))); assert_eq!(*it.next().unwrap(), 6); assert_eq!(it.size_hint(), (2, Some(2))); assert_eq!(*it.next_back().unwrap(), 4); assert_eq!(it.size_hint(), (1, Some(1))); assert_eq!(*it.next_back().unwrap(), 5); assert!(it.next_back().is_none()); assert!(it.next().is_none()); } #[test] fn test_eq() { let mut n: LinkedList<u8> = list_from(&[]); let mut m = list_from(&[]); assert!(n == m); n.push_front(1); assert!(n != m); m.push_back(1); assert!(n == m); let n = list_from(&[2, 3, 4]); let m = list_from(&[1, 2, 3]); assert!(n != m); } #[test] fn test_ord() { let n = list_from(&[]); let m = list_from(&[1, 2, 3]); assert!(n < m); assert!(m > n); assert!(n <= n); assert!(n >= n); } #[test] fn test_ord_nan() { let nan = 0.0f64 / 0.0; let n = list_from(&[nan]); let m = list_from(&[nan]); assert!(!(n < m)); assert!(!(n > m)); assert!(!(n <= m)); assert!(!(n >= m)); let n = list_from(&[nan]); let one = list_from(&[1.0f64]); assert!(!(n < one)); assert!(!(n > one)); assert!(!(n <= one)); assert!(!(n >= one)); let u = list_from(&[1.0f64, 2.0, nan]); let v = list_from(&[1.0f64, 2.0, 3.0]); assert!(!(u < v)); assert!(!(u > v)); assert!(!(u <= v)); assert!(!(u >= v)); let s = list_from(&[1.0f64, 2.0, 4.0, 2.0]); let t = list_from(&[1.0f64, 2.0, 3.0, 2.0]); assert!(!(s < t)); assert!(s > one); assert!(!(s <= one)); assert!(s >= one); } #[test] fn test_debug() { let list: LinkedList<i32> = (0..10).collect(); assert_eq!(format!("{:?}", list), "[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]"); let list: LinkedList<&str> = vec!["just", "one", "test", "more"] .iter().copied() .collect(); assert_eq!(format!("{:?}", list), r#"["just", "one", "test", "more"]"#); } #[test] fn test_hashmap() { // Убеждаемся, что HashMap работает со списком в качестве ключа let list1: LinkedList<i32> = (0..10).collect(); let list2: LinkedList<i32> = (1..11).collect(); let mut map = std::collections::HashMap::new(); assert_eq!(map.insert(list1.clone(), "list1"), None); assert_eq!(map.insert(list2.clone(), "list2"), None); assert_eq!(map.len(), 2); assert_eq!(map.get(&list1), Some(&"list1")); assert_eq!(map.get(&list2), Some(&"list2")); assert_eq!(map.remove(&list1), Some("list1")); assert_eq!(map.remove(&list2), Some("list2")); assert!(map.is_empty()); } #[test] fn test_cursor_move_peek() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 1)); assert_eq!(cursor.peek_next(), Some(&mut 2)); assert_eq!(cursor.peek_prev(), None); assert_eq!(cursor.index(), Some(0)); cursor.move_prev(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.current(), Some(&mut 2)); assert_eq!(cursor.peek_next(), Some(&mut 3)); assert_eq!(cursor.peek_prev(), Some(&mut 1)); assert_eq!(cursor.index(), Some(1)); let mut cursor = m.cursor_mut(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 6)); assert_eq!(cursor.peek_next(), None); assert_eq!(cursor.peek_prev(), Some(&mut 5)); assert_eq!(cursor.index(), Some(5)); cursor.move_next(); assert_eq!(cursor.current(), None); assert_eq!(cursor.peek_next(), Some(&mut 1)); assert_eq!(cursor.peek_prev(), Some(&mut 6)); assert_eq!(cursor.index(), None); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.current(), Some(&mut 5)); assert_eq!(cursor.peek_next(), Some(&mut 6)); assert_eq!(cursor.peek_prev(), Some(&mut 4)); assert_eq!(cursor.index(), Some(4)); } #[test] fn test_cursor_mut_insert() { let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.splice_before(Some(7).into_iter().collect()); cursor.splice_after(Some(8).into_iter().collect()); // check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[7, 1, 8, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); cursor.splice_before(Some(9).into_iter().collect()); cursor.splice_after(Some(10).into_iter().collect()); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[10, 7, 1, 8, 2, 3, 4, 5, 6, 9]); /* удаляем, сейчас не реализовано: let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); assert_eq!(cursor.remove_current(), None); cursor.move_next(); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(7)); cursor.move_prev(); cursor.move_prev(); cursor.move_prev(); assert_eq!(cursor.remove_current(), Some(9)); cursor.move_next(); assert_eq!(cursor.remove_current(), Some(10)); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[1, 8, 2, 3, 4, 5, 6]); */ check_links(&m); let mut m: LinkedList<u32> = LinkedList::new(); m.extend([1, 8, 2, 3, 4, 5, 6]); let mut cursor = m.cursor_mut(); cursor.move_next(); let mut p: LinkedList<u32> = LinkedList::new(); p.extend([100, 101, 102, 103]); let mut q: LinkedList<u32> = LinkedList::new(); q.extend([200, 201, 202, 203]); cursor.splice_after(p); cursor.splice_before(q); assert_eq!( m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101, 102, 103, 8, 2, 3, 4, 5, 6] ); let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_prev(); let tmp = cursor.split_before(); assert_eq!(m.into_iter().collect::<Vec<_>>(), &[]); m = tmp; let mut cursor = m.cursor_mut(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); cursor.move_next(); let tmp = cursor.split_after(); assert_eq!(tmp.into_iter().collect::<Vec<_>>(), &[102, 103, 8, 2, 3, 4, 5, 6]); check_links(&m); assert_eq!(m.iter().cloned().collect::<Vec<_>>(), &[200, 201, 202, 203, 1, 100, 101]); } fn check_links<T: Eq + std::fmt::Debug>(list: &LinkedList<T>) { let from_front: Vec<_> = list.iter().collect(); let from_back: Vec<_> = list.iter().rev().collect(); let re_reved: Vec<_> = from_back.into_iter().rev().collect(); assert_eq!(from_front, re_reved); } }
EvilBlueBeaver
["hel", "lo"]