Трудности графо-мании
Во времена, когда я изучал Си и С++, программирование списков и прочих графов было весьма популярной задачей. Судя по всему для изучающих Rust эта тема весьма актуальна, если не сказать — горяча. Рассмотрим несколько цитат.
If you want to create data structures which can be modified during runtime, a possible solution could lead into tree or graph like structures. Writing tree structures in Rust is no trivial problem.
Idiomatic tree and graph like structures in Rust,
Автор демонстрирует, что для новоприбывших в Rust устройство ребер графов традиционным способом выглядит пугающе:
В качестве решения предлагается поместить все вершины графа в "арену" и для моделирования ребер использовать целочисленные идентификаторы вершин. Идем дальше.
Частая ошибка пробующих ржавчину новичков — пробовать написать свой двусвязный список, т.к. в большинстве языков это довольно простая задача. Быстро оказывается что сделать это в ржавчине в лоб не так-то и просто из-за модели работы с памятью
Комментарий от @ ozkriff
ozkriff приводит две ссылки, одна из которых, КМК, особенно интересна:
I fairly frequently get asked how to implement a linked list in Rust. The answer honestly depends on what your requirements are, and it's obviously not super easy to answer the question on the spot. As such I've decided to write this book to comprehensively answer the question once and for all.
Learn Rust With Entirely Too Many Linked Lists
Занятный вариант изучения Rust на практических примерах в виде связных списков, в принципе, почему нет? Ну и, наконец:
Просто все интуитивно знают, что «связный список» — классическая задача на языках с ГЦ, и идут автоматически пытаться её реализовать в раст. Это неправильный подход.
Комментарий от @ PsyHaSTe
Cкладывается ощущение, что опытные разработчики Rust тему списков не любят. А за что ее любить? Ведь и сам Бьёрн Страуструп занял такую позицию:
And, yes, my recomendation is to use std::vector by default. More generally, use a contiguous representation unless there is a good reason not to.
Are lists evil? — Bjarne Stroustrup
В случае наличия "good reason not to" можно попробовать обратиться к стандартной релизации двузвязного списка, здесь же мы в учебных целях рассмотрим реализацию односвязного списка, задействуя ранее пройденный материал, в частности, "сырые указатели".
Попытка не пытка
Начнем с простого примера для подражания на C:
struct Node
{
int data;
struct Node *next;
}Такую структуру вполне можно определить и на Rust:
struct Node<'a> {
data: i32,
next: &'a Node<'a>,
}Определить можно, а создать первый и последний элементы списка нельзя — при создании структуры требуется явная инициализация всех полей (отсюда проблема с первым элементом, где есть ссылка на следующий), а значения null для ссылок нет (что порождает проблему с последним элементом, который ссылается в никуда).
"Идиоматический" подход подразумевает использование умных указателей и ряда других уловок, типа Option. Посмотрим на представителя семейства умных указателей Box:
pub struct Box< T: ?Sized, A: Allocator = Global,
...
impl<T> Box<T> {
...
pub fn new(x: T) -> Self {
box x
}
...Что такое box x? Попробуем:
struct MyBox<T>(*mut T);
impl<T> MyBox<T> {
pub fn new(x: T) -> Self {
box x
}
}Результат:
> error[E0658]: box expression syntax is experimental; you can call `Box::new` instead
> ...
> 4 | pub fn new(x: T) -> Self {
> | ---- expected `MyBox<T>` because of return type
> 5 | box x
> | ^^^^^ expected struct `MyBox`, found struct `Box`Ясно — ключевое слово box все еще является экспериментальным и делает исключительно Box. Умные указатели надо, конечно, рассматривать отдельной статьей, но один любопытный момент, обнаруженный в процессе исследования, вынес в Приложение.
Ладно, мы и так уже знаем, как работать с кучей — будет немного опасно, зато стабильно. Поехали.
Список в стиле Си
У гиков Си-версия "Linked List Traversal" выглядит так:
int main()
{
struct Node* head = NULL;
struct Node* second = NULL;
struct Node* third = NULL;
// allocate 3 nodes in the heap
head = (struct Node*)malloc(sizeof(struct Node));
second = (struct Node*)malloc(sizeof(struct Node));
third = (struct Node*)malloc(sizeof(struct Node));
head->data = 1; // assign data in first node
head->next = second; // Link first node with second
second->data = 2; // assign data to second node
second->next = third;
third->data = 3; // assign data to third node
third->next = NULL;
printList(head);
return 0;
}Можно ли такое сделать на Rust? Да запросто:
unsafe fn unsafe_main() {
let first: *mut Node = ptr::null_mut();
let second: *mut Node = ptr::null_mut();
let third: *mut Node = ptr::null_mut();
// allocate 3 nodes in the heap
let third = alloc(Layout::new::<Node>()) as *mut Node;
let second = alloc(Layout::new::<Node>()) as *mut Node;
let head = alloc(Layout::new::<Node>()) as *mut Node;
(*head).data = 1; // assign data in first node
(*head).next = second; // Link first node with second
(*second).data = 2; // assign data to second node
(*second).next = third;
(*third).data = 3; // assign data to third node
(*third).next = ptr::null_mut();
print_list(head);
free_list(head);
}Гики, правда, забыли освободить память, этот момент повторить не удалось.
В принципе, особой разницы нет, за исключением того, что надо писать unsafe.
Список в стиле C++
В Rust есть прекрасные возможности в виде системы обобщенных типов (список будет работать для всех типов), автоматического вызова drop() (не надо думать про вызов free_list()), а также контроля времен жизни (нелья поместить в список короткоживущую ссылку и проч.). Задействуем же все это и рассмотрим некоторые детали реализации.
Список построен на "сырых указателях" (raw pointers):
pub struct Item<T> {
data: T,
next: *const Item<T>,
}
pub struct List<T> {
head: *const Item<T>,
}Напоминаю, что можно менять и читать значения переменных такого типа обычным образом, а вот разыменование является опасной операцией.
Для итерирования по списку будем использовать замыкание:
pub fn for_each<F: FnMut(&T)>(&self, mut f: F) {
let mut cur = self.head;
while !cur.is_null() {
unsafe {
f(&(*cur).data);
cur = (*cur).next;
}
}
}- Появился небольшой блок
unsafe, посвященный разыменованию сырых указателей
push() выделяет память и перемещает туда переданное значение:
pub fn push(&mut self, value: T) {
let pitem;
unsafe {
pitem = alloc(Layout::new::<Item<T>>()) as *mut Item<T>;
std::ptr::write(&mut (*pitem).data, value);
(*(pitem)).next = self.head;
}
self.head = pitem;
}alloc()иwrite()являются unsafe, как и еще одно разыменование- В недрах
write()происходит "забывание"value, так что деструкторdrop()для этого значения не вызывается
Серия тестов вынесена в свой модуль, чудесная песочница позволяет запускать тесты отдельно от запуска main:
#[cfg(test)]
mod tests {
use super::*;
...main(), однако, тоже сделал — было интересно визуально проконтролировать последовательность вызова деструкторов:
...
// List of Points
{
let mut ls = List::<Point>::new();
ls.push(Point { x: 1, y: 2 });
ls.push(Point { x: 10, y: 20 });
ls.pop();
ls.push(Point { x: 100, y: 200 });
}
...Последовательностью вызовов деструкторов удовлетворен:
Dropping Point { x: 10, y: 20 }...
Dropping List<playground::Point>...
Dropping Point { x: 100, y: 200 }...
Dropping Point { x: 1, y: 2 }...
...В комментариях, на мой взгляд, тоже интересно, хотя и не компилируется.
Первый пример: пытаемся поместить короткоживущую ссылку в долгоживущий список ссылок (не компилируется):
// Attempt to put a short-lived reference to a long-lived list
{
let mut ls = List::<&String>::new();
let rstr: &String;
let s = String::from("String 1");
ls.push(&s); // error[E0597]: `s` does not live long enough
rstr = ls.pop();
dbg!(rstr);
}Второй пример: пытаемся записать ссылку на короткоживущее значение в ссылку на долгоживущее (не компилируется):
// Attempt to pop a reference to a short-lived value to a long-lived value reference
{
let rstr: &String;
{
let s = String::from("String 1");
let mut ls = List::<&String>::new();
ls.push(&s); // error[E0597]: `s` does not live long enough
rstr = ls.pop();
}
dbg!(rstr);
} Compiling playground v0.0.1 (/playground)
error[E0597]: `s` does not live long enough
--> src/main.rs:181:21
|
181 | ls.push(&s); // error[E0597]: `s` does not live long enough
| ^^ borrowed value does not live long enough
182 | rstr = ls.pop();
183 | }
| - `s` dropped here while still borrowed
184 | dbg!(rstr);
| ---- borrow later used hereДля разнообразия третий пример, который показывает, что компилятор могуч, но не всемогущ (код компилируется и паникует):
// Pop from an empty list to a long-lived reference
{
let rstr: &String;
{
let mut ls = List::<&String>::new();
rstr = ls.pop(); // thread 'main' panicked at 'assertion failed: !cur.is_null()', src/main.rs:50:9
}
dbg!(rstr);
}Некоторые размышления
Склонен согласиться с тем, что Rust занимает промежуточное положение между C и C++, в качестве метрики для сравнения можно рассмотреть количество ключевых слов:
┌───────────────────────────────────────────────────────────────────────────────────────────┐
│ ...... │
│ ...... │
│ ...... ...... │
│ ...... ...... │
│ ...... ...... ...... │
│ ...... ...... ...... │
│ ...... ...... ...... │
│ ...... ...... ...... │
│ ...... ...... ...... │
│ ...... ...... ...... ...... ...... │
│ ...... ...... ...... ...... ...... ...... ...... │
│ ...... ...... ...... ...... ...... ...... ...... │
│ ...... ...... ...... ...... ...... ...... ...... ...... ...... │
│ ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... │
│...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... │
│...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... ...... │
│..22.. ..25.. ..26.. ..32.. ..35.. ..36.. ..49.. ..51.. ..52.. ..54.. ..89.. .100.. .109.. │
│Lua Go Erlang C Python Ruby JS Java Rust Dart Swift C# C++ │
└───────────────────────────────────────────────────────────────────────────────────────────┘Т.е., если рассматривать Rust как "замену", то это скорее "замена" языка C, чем C++.
Приложение. Про box и println!()
В "ночной" версии box прекрасно работает:
#![feature(box_syntax)]
fn type_name<T>(_: T) -> &'static str {
std::any::type_name::<T>()
}
fn main() {
let five = box 5;
println!("{}", five);
println!("{}", type_name(five)); // alloc::boxed::Box<i32>
}- Имя получаемого типа выводится несколько экзотическим образом, но другого способа не нашел
- Как и обещал компилятор, из
boxполучается толькоBox
Обнаружил такой нюанс — если заменить println! на dbg!, то получим ошибку:
8 | let five = box 5;
| ---- move occurs because `five` has type `Box<i32>`, which does not implement the `Copy` trait
9 | dbg!("{}", five);
| ---------------- value moved here
10 | dbg!("{}", type_name(five)); // alloc::boxed::Box<i32>
| ^^^^ value used here after moveС dbg!() все понятно — обернутая "пятерка" передаётся по значению, trait Copy для alloc::boxed::Box не реализован, так что дальнейшее использование переменной five исключено. Но как же тогда работает println!()?! Тут какое-то колдунство (дело-то происходит ночью).
Поиск по исходникам дает такой результат:
macro_rules! println {
() => ($crate::print!("\n"));
($($arg:tt)*) => ({
$crate::io::_print($crate::format_args_nl!($($arg)*));
})
} /// Same as `format_args`, but adds a newline in the end.
macro_rules! format_args_nl {
($fmt:expr) => {{ /* compiler built-in */ }};
($fmt:expr, $($args:tt)*) => {{ /* compiler built-in */ }};
} macro_rules! format_args {
($fmt:expr) => {{ /* compiler built-in */ }};
($fmt:expr, $($args:tt)*) => {{ /* compiler built-in */ }};
}В общем, println, в конечном счете, работает через compiler built-in. Поэтому и работает.
