Может ли безопасный и стабильный Rust противопоставить что-то аккумулированному опыту многих десятилетий от Си и C++? Вот, например, типобезопасный список на Си:
int *nums = NULL; int sum = 0; *(nums = ll_new(nums)) = 5; *(nums = ll_new(nums)) = 10; ll_foreach(nums, num) { sum += *num; } /* sum == 15 */
СД; НО: не может. Придется встать на путь, полный опасностей и приключений.
Трудности графо-мании
Во времена, когда я изучал Си и С++, программирование списков и прочих графов было весьма популярной задачей. Судя по всему для изучающих 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.
Автор демонстрирует, что для новоприбывших в Rust устройство ребер графов традиционным способом выглядит пугающе:
В качестве решения предлагается поместить все вершины графа в «арену» и для моделирования ребер использовать целочисленные идентификаторы вершин. Идем дальше.
Частая ошибка пробующих ржавчину новичков — пробовать написать свой двусвязный список, т.к. в большинстве языков это довольно простая задача. Быстро оказывается что сделать это в ржавчине в лоб не так-то и просто из-за модели работы с памятью
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.
Занятный вариант изучения Rust на практических примерах в виде связных списков, в принципе, почему нет? Ну и, наконец:
Просто все интуитивно знают, что «связный список» — классическая задача на языках с ГЦ, и идут автоматически пытаться её реализовать в раст. Это неправильный подход.
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.
Тем-не менее, сейчас состоится🎥 разбор примера программирования списка на Rust в стиле, подобном C/C++.
Попытка не пытка
Начнем с простого примера для подражания на 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++. С учетом гарантий безопасности стремление использовать Rust в ядре Linux вместо С мне вполне понятно (впрочем, также понятны и сомнения по этому поводу).
Однако, если сравнивать по другим критериям, то может оказаться, что Rust ближе всего к Go — именно такой тезис я выдвинул в первой части. С точки зрения «гофера» изложенный материал может быть оценен такий образом. Какие проблемы решает Rust?
- Висячие указатели (dangling reference). В Go неактуально, ввиду автоматического управления памятью
- GC overhead. В Go проблема имеет место, но не так горяча, как ранее. Кроме того, существуют кардинальные средства решения проблем больших кэшей
- Data race. Safe Rust guarantees an absence of data races, это очень круто. В Go эта боль весьма сильна, однако, она облегчается инструментами тестирования, которые позволяют ловить существенную часть таких ошибок
И все-таки, есть кое-что…
- ЭТО заставляет разработчика Go ежедневно страдать
- В Rust ЭТО делать легко и приятно
Про ЭТО речь впереди🎥.
Приложение. Про 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 */ }}; }
В общем, прикольный язык этот Rust — в нем нельзя без ночного шаманства безопасно поместить значение в кучу и также отсутствует возможность форматировать список значений разных типов.
Такие дела.
ссылка на оригинал статьи https://habr.com/ru/post/646105/