Представление
Так на что похожа односвязная очередь? Когда речь шла об односвязном стеке, мы вставляли элементы с одного конца списка и затем удаляли их с того же конца. Единственное отличие между стеком и очередью в том, что элементы очереди удаляются с другого конца. Из нашей реализации стека мы получаем:
список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
вставка X:
[Some(ptr)] -> (X, Some(ptr)) -> (A, Some(ptr)) -> (B, None)
удаление:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
Чтобы превратить стек в очередь надо решить, какую операцию перенести на другой конец списка — вставку или удаление? Так как у нас односвязный список, мы с одинаковыми усилиями можем перенести на другой конец любую из операций.
Чтобы перенести в конец вставку, мы должны пробежаться по списку до None и заменить его на Some с новым элементом.
список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
вставка X в конец:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
Чтобы перенести в конец удаление, мы должны пробежаться по списку до узла перед None и изъять узел.
список на входе:
[Some(ptr)] -> (A, Some(ptr)) -> (B, Some(ptr)) -> (X, None)
удаление с конца:
[Some(ptr)] -> (A, Some(ptr)) -> (B, None)
Мы могли бы закрыть задачу прямо сейчас, но, скажем прямо, это решение ужасно! Обе операции пробегаются по всему списку. Вы возразите, что такая реализация вполне нормальна, поскольку полностью соответствует интерфейсу. Однако, я уверена, что гарантии производительности тоже являются частью интерфейса. Меня не волнуют точные асимптотические границы, просто «быстро» или «медленно». Гарантии очереди в том, что вставка и удаление быстрые, а обход всего списка — определённо не быстрый.
Обратите внимание, что мы делаем тучу работы, повторяя одну и ту же вещь снова и снова. Можем ли мы «кешировать» всю эту работу и переиспользовать результат? Да, разумеется! Мы можем сохранить указатель на конец списка и просто перепрыгивать туда!
Оказывается, что с этой идеей работает только один из вариантов инверсии вставки/удаления.
Чтобы инвертировать pop, мы должны передвинуть назад указатель на хвост, но, поскольку наш список односвязный, этого нельзя сделать эффективно.
Однако, если инвертируем push, надо будет передвинуть вперёд указатель на голову, а легко.
Давайте попробуем:
use std::mem;
pub struct List<T> {
head: Link<T>,
tail: Link<T>, // НОВАЯ СТРОКА!
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// Когда вставляете в конец списка, следующий узел всегда None
next: None,
});
// теперь указатель на хвост указывает на новый хвост
let old_tail = mem::replace(&mut self.tail, Some(new_tail));
match old_tail {
Some(mut old_tail) => {
// Если старый хвост был, обновляем его, чтобы он указывал на новый
old_tail.next = Some(new_tail);
}
None => {
// В противном случае, обновляем голову, чтобы указывала на него
self.head = Some(new_tail);
}
}
}
}Я собираюсь ускорить повествование, опуская некоторые детали, поскольку к настоящему моменту вы уже должны понимать, как работает Rust.
Похоже, что этот код запустится с первого раза.
Сейчас я не показываю ошибки, которые показывала раньше, вроде пропусков mut или ;, так как они перестали быть поучительными.
Не переживайте, мы столкнёмся с множеством других ошибок!
> cargo build
error[E0382]: use of moved value: `new_tail`
--> src/fifth.rs:38:38
|
26 | let new_tail = Box::new(Node {
| -------- move occurs because `new_tail` has type `std::boxed::Box<fifth::Node<T>>`, which does not implement the `Copy` trait
...
33 | let old_tail = mem::replace(&mut self.tail, Some(new_tail));
| -------- value moved here
...
38 | old_tail.next = Some(new_tail);
| ^^^^^^^^ value used here after move
Да что ж такое!
use of moved value:
new_tail
Использование перемещённого значения: new_tail.
Box не реализует Copy, так что мы просто не можем присвоить его двум разным переменным.
Что важнее, Box владеет значением, на которое указывает, и постарается освободить его в своём деструкторе.
Если бы наша реализация push компилировалась, мы бы дважды освобождали хвост нашего списка!
На самом деле, наш текущий код будет освобождать old_tail при каждом вызове push.
Кошмар!
Ладно, мы знаем, как создать указатель без владения. Это будет просто ссылка!
pub struct List<T> {
head: Link<T>,
tail: Option<&mut Node<T>>, // НОВАЯ СТРОКА!
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<T> List<T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// Когда вставляете в конец списка, следующий узел всегда None
next: None,
});
// Помещаем бокс в правильное место получем ссылку на его узел
let new_tail = match self.tail.take() {
Some(old_tail) => {
// Если старый хвост был, обновляем его, чтобы он указывал на новый
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
// В противном случае, обновляем голову, чтобы указывала на него
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
}Никакого особого трюкачества. Та же базовая идея, что и в предыдущем коде, за исключением того, что мы используем преимущества неявного возврата и получем ссылку на хвост прямо оттуда, куда мы только что поместили Box.
> cargo build
error[E0106]: missing lifetime specifier
--> src/fifth.rs:3:18
|
3 | tail: Option<&mut Node<T>>, // NEW!
| ^ expected lifetime parameter
Да, правильно, мы ведь должны указывать время жизни ссылок в типах.
Хмм... а какое время жизни у этой ссылки?
Ну, код похож на IterMut, правда?
Давайте попробуем, то же самое, что мы делали в IterMut и просто добавим обобщённый 'a:
pub struct List<'a, T> {
head: Link<T>,
tail: Option<&'a mut Node<T>>, // НОВЫЙ КОД!
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}
impl<'a, T> List<'a, T> {
pub fn new() -> Self {
List { head: None, tail: None }
}
pub fn push(&mut self, elem: T) {
let new_tail = Box::new(Node {
elem: elem,
// Когда вставляете в конец списка, следующий узел всегда None
next: None,
});
// Помещаем бокс в правильное место и получем ссылку на его узел
let new_tail = match self.tail.take() {
Some(old_tail) => {
// Если старый хвост был, обновляем его, чтобы он указывал на новый
old_tail.next = Some(new_tail);
old_tail.next.as_deref_mut()
}
None => {
// В противном случае, обновляем голову, чтобы указывала на него
self.head = Some(new_tail);
self.head.as_deref_mut()
}
};
self.tail = new_tail;
}
}cargo build
error[E0495]: cannot infer an appropriate lifetime for autoref due to conflicting requirements
--> src/fifth.rs:35:27
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^^^^
|
note: first, the lifetime cannot outlive the anonymous lifetime #1 defined on the method body at 18:5...
--> src/fifth.rs:18:5
|
18 | / pub fn push(&mut self, elem: T) {
19 | | let new_tail = Box::new(Node {
20 | | elem: elem,
21 | | // When you push onto the tail, your next is always None
... |
39 | | self.tail = new_tail;
40 | | }
| |_____^
note: ...so that reference does not outlive borrowed content
--> src/fifth.rs:35:17
|
35 | self.head.as_deref_mut()
| ^^^^^^^^^
note: but, the lifetime must be valid for the lifetime 'a as defined on the impl at 13:6...
--> src/fifth.rs:13:6
|
13 | impl<'a, T> List<'a, T> {
| ^^
= note: ...so that the expression is assignable:
expected std::option::Option<&'a mut fifth::Node<T>>
found std::option::Option<&mut fifth::Node<T>>
Ого, вот действительно подробное сообщение об ошибке. Оно настораживает, потому что утверждает, что мы делаем что-то по настоящему неправильное. Вот интересная часть:
the lifetime must be valid for the lifetime
'aas defined on the impl
Время жизни должно быть действительно в течение времени жизни 'a, заданного в блоке impl.
Мы заимствуем self, но компилятор хочет, чтобы мы существовали столько же, сколько и 'a, а что, если мы скажем ему, что self действительно существует столько же?
pub fn push(&'a mut self, elem: T) {cargo build
warning: field is never used: `elem`
--> src/fifth.rs:9:5
|
9 | elem: T,
| ^^^^^^^
|
= note: #[warn(dead_code)] on by default
О, здорово, так работает! Отлично!
Теперь давайте реализуем pop:
pub fn pop(&'a mut self) -> Option<T> {
// Извлекаем текущую голову списка
self.head.take().map(|head| {
let head = *head;
self.head = head.next;
// Если новый список пуст, хвост должен быть установлен в `None`.
if self.head.is_none() {
self.tail = None;
}
head.elem
})
}И напишем небольшой тест для нашего кода.
#[cfg(test)]
mod test {
use super::List;
#[test]
fn basics() {
let mut list = List::new();
// Проверяем, что пустой список ведёт себя правильно
assert_eq!(list.pop(), None);
// Заполняем список
list.push(1);
list.push(2);
list.push(3);
// Проверяем обычное удаление
assert_eq!(list.pop(), Some(1));
assert_eq!(list.pop(), Some(2));
// Вставляем новые значения, просто чтобы проверить, что ничего не сломается
list.push(4);
list.push(5);
// Проверяем обычное удаление
assert_eq!(list.pop(), Some(3));
assert_eq!(list.pop(), Some(4));
// Проверяем граничный случай
assert_eq!(list.pop(), Some(5));
assert_eq!(list.pop(), None);
}
}cargo test
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:68:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
68 | list.push(1);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:69:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
69 | list.push(2);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
error[E0499]: cannot borrow `list` as mutable more than once at a time
--> src/fifth.rs:70:9
|
65 | assert_eq!(list.pop(), None);
| ---- first mutable borrow occurs here
...
70 | list.push(3);
| ^^^^
| |
| second mutable borrow occurs here
| first borrow later used here
....
** ЕЩЁ МНОГО СТРОК С ОШИБКАМИ **
....
error: aborting due to 11 previous errors
🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀🙀
Да божечки мои.
Компилятор совершенно прав, ругаясь на наш код.
Мы только что совершили смертный грех языка Rust: сохранили ссылку на себя внутри себя.
Нам как-то удалось убедить компилятор, что это действительно имеет смысл в наших реализациях push и pop (я искренне удивляюсь, что мы смогли).
Причина, по которой это вроде бы работает в том, что в Rust вообще нет такого понятия, как указатель на себя.
Каждая часть кода технически корректна сама по себе (мы можем вызывать push и pop один раз), но затем вступает в силу абсурдность нашего решения и всё просто ломается.
Я уверена, что у написанного нами может быть какое-то применение, но, насколько мне известно, это всего лишь синтаксически корректная тарабарщина.
Мы говорим, что у нас есть что-то с временем жизни 'a, и что push и pop заимствуют self на это время.
Это странно, но Rust смотрит на каждую часть нашего кода по отдельности и ни видит никаких нарушений.
Но как только мы пытаемся действительно использовать список, компилятор нам сообщает: «так, вы заимствовали self изменяемым образом на время 'a, так что вы не можете использовать self до конца 'a», но также: «поскольку вы содержите 'a, он должен быть действителен в течение всего времени существования списка».
Это почти противоречие, но есть одно решение: сразу после вызова push или pop список себя закрепляет и к нему больше нельзя получить доступ.
Образно говоря, он проглатывает свой хвост и возносится в мир грёз.
ГОЛОС ЗА КАДРОМ: с тех пор, как была написана эта книга, Rust, фактически, формализовал закрепление и нашёл ему применение! Возможно, это было самое сложное расширение языка со времён появления анализатора заимствований (borrow checker). Но нам, в любом случае, не надо закреплять наш список!
Закрепления нужны и полезны для async/await, футур, сопрограмм, поскольку компилятору надо собирать локальные переменные в некоторое подобие структуры и хранить их, пока футура/сопрограмма не будет готова к возобновлению. Поскольку локальные переменные могут ссылаться на другие локальные переменные, и мы хотим, чтобы всё работало, эти структуры в конечном счёте могут содержать ссылки на самих себя!
Таким образом, для
awaitилиyieldRust нуждается в корректном способе описания и манипулирования закреплёнными значениями. К счастью, в основном всё это скрыто глубоко в недрах компилятора и при обычных обстоятельствах никому не приходится думать проPin(или даже про футуры). Главное исключение из этого правила: разработчики и проектировщики асинхронных библиотек, таких как tokio.Мы не станем реализовывать асинхронную библиотеку в этой книге. Мои друзья знают все виды «крутых» (и странных) трюков, которые можно провернуть с
Pin, но я бы не хотела погружаться в эту тему. Продолжу убеждать себя, что закреплённых типов не существуют и они не могут мне навредить.
Наша реализация pop подсказывает, почему хранение ссылки на себя внутри себя может быть опасным:
// ...
if self.head.is_none() {
self.tail = None;
}Что, если мы забудем это сделать? Тогда наш хвост будет указывать на какой-то узел, который уже удалён из списка. Такой узел будет мгновенно освобождён и мы получили бы висящий указатель, от чего Rust должен был нас защитить!
И действительно Rust защищает нас от подобной опасности. Просто очень... окольным путём.
Так что же нам теперь делать?
Возвращаться в ад Rc<RefCell>>?
Спасибо. Не надо.
Нет, вместо этого пустимся во все тяжкие и начнём использовать сырыми указателями. Теперь наша структура будет выглядеть так.
pub struct List<T> {
head: Link<T>,
tail: *mut Node<T>, // ОПАСНО!
}
type Link<T> = Option<Box<Node<T>>>;
struct Node<T> {
elem: T,
next: Link<T>,
}И это всё. Никакого детского лепета про подсчёт ссылок и динамическую проверку заимствований! Реальные. Сложные. Непроверяемые. Указатели.
ГОЛОС ЗА КАДРОМ: наша реализация фактически была не просто неправильной, а опасно неправильной. Но для этого урока время ещё не пришло. В следующей части усвоим его на собственном горьком опыте, как и всегда.
Да будет C ныне, присно и во веки веков!
Я возвращаюсь домой. Я готова.
Привет, unsafe.
ГОЛОС ЗА КАДРОМ: какая невероятная самонадеянность со стороны автора.