Связный список на Rust в стиле С/C++ +6
93
5000Рекомендация: подборка платных и бесплатных курсов C++ - https://katalog-kursov.ru/
Может ли безопасный и стабильный 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.
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
Тем-не менее, сейчас состоится???? разбор примера программирования списка на 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 — в нем нельзя без ночного шаманства безопасно поместить значение в кучу и также отсутствует возможность форматировать список значений разных типов.
Такие дела.
Для Java пятьдесят одно ключевое слово - это включая те, которые пишут в modules-info.java?
Код, что написан на картинке ниже этого предложения — образец того как нельзя писать код. Ну нельзя делать циклы из Rc, это не имеет смысла.
Вообще-то можно, Box::new. Что там внутри — не важно совершенно, сама функция Box::new стабильна и безопасна.
На картинке нет цикла из Rc
Предлагается считать функцию Box безопасной, но гарантий, в данном случае, нет. Целиком полагаемся на разработчика. Мало ли что он там поместил внутрь, на то и служат маркеры version=nightly/unsafe чтобы не доверять, а проверять.
Возможно я чего-то не понимаю но если я правильно понимаю зачем написаны
previousиnextто предполагается сделать как раз цикл, если конечно в списке планируется более чем 1 элемент. Поправьте если не прав.Каких гарантий? Единственной гарантии которую не дает бокс — то что значение будет сразу в куче создано, а не скопировано туда со стека. Это иногда вышибает память при попытке саллоцировать гигабайтные массивы. Это правда, для этого есть нестабильный кейворд
box(который вы и использовали).Во всех остальных случаях
Box::newдля всего подходит.Как же может получиться цикл, если список, как бы это… односвязный, т.е. узлы связаны только через previous. Понятно, ребра в некоторомы смысле моделируются еще и через next, но там нет ссылок на другие узлы (т.е. значения типа Node).
Есть определенная загадка в том, как автор инициализирует ЭТО без Option, и зачем ему ЭТО. Возможно, это был некий черновичок.
Гарантий, предоставляемых стабильным компилятором Rust.
Подходит-то он подходит, но речь ведь не об этом.
Если это и правда граф, а не двусвязный список, то в нём циклы могут быть просто по постановке задачи.
Box::new — это метод стандартной библиотеки. Разумеется, все гарантии компилятора на него распространяются независимо от того что там внутри.
На картинке скорее односвязный список с локальными "побегами" одиночной длины.
Как могут гарантии стабильного компилятора распространяться на то, что не компилируется?
Компилятор даёт гарантии безопасной композиции кода. Проверять корректность базовых элементов кода — вообще не его задача.
Гм, а как вы в таком случае доверяете функциям выделения памяти в других языках? Там ведь тоже приходится, о ужас, полагаться на разработчика рантайма, разработчика SDK операционной системы… Мало ли что они там внутри понаписывали.
Если серьёзно, box — такой себе интринсик, завёрнутый в нормальную функцию.
Приходится именно что доверять, "гарантий" компилятора же нет. Понятно, что даже в случае наличия таковых встает вопрос о доверии самому компилятору, но тем не менее...
Ну вот и тут вам ничего не мешает доверять стандартной библиотеке в той же степени, в какой вы доверяете компилятору — благо, их одни и те же люди пишут.
Максим, nightly в компиляторе и стд — это прямое Quod licet Iovi, non licet bovi. Вы правильно делаете, что копаетесь в кишках стандартной библиотеки, но делаете неправильные выводы.
В целом мотивация упрятать нестабильный box внутрь Box понятна, тут вопросов нет.
Нет возражений также считать код Box "надёжным", в том смысле, в каком "надёжен" код на любом ЯП — не меньше, но и не больше.
PS. Для саморазвития — можно глянуть на примеры нестабильного C++ в стд C++?
Ну вот, держите:
https://code.woboq.org/userspace/glibc/bits/stdint-intn.h.html:
Совершенно некорректный с точки зрения стандарта typedef, потому что нет никаких гарантий что signed int имеет разрядность 32 бита в общем случае. Но в glibc такое писать можно.
Пример по ссылке компилируется.
Нестабильный компилироваться не должен.
На какой-то платформе соберется и будет нормально работать, на какой-то взорвется нафиг. Мы ж про плюсы говорим, а сам по себе плюсовый компилятор не склонен помогать программисту замечать что тот делает странное
Вот это взорвется? https://www.onlinegdb.com/vmdoJZFgL
Поясните, из-за чего?
Вообще меня интересовали примеры нестабильного C++ в стандартной библиотеке C++.
Пока рассматриваем стабильный из С.
Выше пример не такой был, суть же в - `typedef signed int __int32_t;` - такое можно писать только в частном случае, когда мы знаем каким компилятором собираемся и на какой архитектуре, иначе это лютое UB и код использующий __int32_t дальше или тупо не соберется, или принесет много веселья в отладке странных ошибок.
Аналогичным образом msvc реализация плюсовой стандартной либы использует дофига компилятор-специфичных интринсиков и предположений.
Это разве был интересующий пример нестабильного C++ в стандартной библиотеке C++?
Чем же лучше версия на Rust:
?
Во-первых, ничем не лучше — вы как бы просили аналог же.
Во-вторых, где вы в стандартной библиотеке Rust нашли эту строчку?
а разве нет? ну хорошо, вот прям ссылка на то как GCC реализация stdc++ использует кучу builtin штук компилятора https://github.com/gcc-mirror/gcc/search?q=path%3Alibstdc%2B%2B-v3%2Fsrc+builtin так убедительней? Или может я вопрос как-то не так понял?
Стоп, откуда тут лучше-хуже взялось и какое отношение этот пример имеет к стандартным библиотекам раста и плюсов? ????????Разговор же был о том, что стандартные библиотеки языков часто используют платформо-компиляторо-специфичный код в своих реализациях и это нормально.
typedef signed int __int32_t;? — Нет.Это все компилируется стабильным компилятором
https://godbolt.org/z/8qEezhbch
Меня интересуют примеры, когда для компиляции стандартной библиотеки надо включить "ночную" опцию у компилятора.
Эм. Такого нет, конечно - в плюсах отсутсвует явный механизм индикации нестабильности чего-то и явное разделение на стабильный-ночной версии компилятора. Только нестабильные штуки из реализации std от этого не пропадают, просто, как выше сказано, это все руками надо отслеживать.
Вообще, это означает, что "нестабильных штук" там нет, т.е. можно взять компилятор и скомпилировать к нему библиотеку.
Есть "нестандартные штуки", т.е. другим компилятором эта библиотека может не скопилироваться.
А мы какое определение "нестабильности" тут используем? В моем понимании это все, что не входит в стандарт языка.
Это хороший подход — договориться про определения.
Нестабильный код (или unstable feature) требует особой версии компилятора — альфа, ночная и прочая. Стабильной версией (release, production) нестабильный код компилироваться не должен. Вкратце эти тезисы излагал тут.
Я лично уже запутался, какие у вас претензии к тому, что
boxне работает в пользовательсокм коде в стабильной версии Rust?Вроде всё очевидно - интерфейс этого "оператора" ещё не стабилизирован. Всё ещё есть вероятность, что его могут поменять (например решат, что он должен возвращать Result<Box<T>>, вместо Box<T>).
Но это не означает, что стандартная библиотека не может его использовать. Если бы это был не "оператор" языка, а функция, то её могли бы сделать приватной, и у вас точно так же не получилось бы её использовать в своём коде.
Давайте так поступим — процитируйте какое-либо мое утверждение из статьи и далее я поясню его, если это нужно.
Ну у меня вопрос к вот этой части
Просто не очень понятно с чего вы решили что можно просто скопировать код из STD и он заработает. Ну возьмем для примера тип int из стд сишарпа:
https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Int32.cs#L16
Мы там увидем примерно такое:
Как думаете, можно такое скопировать в свой код чтобы оно скомпилировалось?
Я разве написал, что он должен заработать? В цитате этого нет. В цитате есть "Попробуем".
Тут странно. Я вижу такое:
И это работает, по крайней мере, тут.
А я специально для вас упростил, чтобы лучше поинт передать. Потому что это одно и то же
int — это как бы синоним для System.Int32
Я в принципе не понимаю зачем вы полезли в реализацию Box::new(), зачем решили использовать в своём коде
box. И после этого сделали выводы как в анекдоте про сибирских лесорубов, которые засунули стальной лом в японскую лесопилку.Почему нельзя было использовать Box::new()? Вам что-ли принципильно хотелось с самого начала оперировать только указателями, что бы "всё как в С"?
Ночную-не ночную, но вот кучу флагов включать придётся хотя бы для того, чтобы компилятор реализацию какого-нибудь memset не заменил на вызов memset (имеет право, однако!)
Вот мне интересно, на Swift я решал бы задачу двусвязного списка через сильную ссылку next и слабую на previous. То есть в мире раста это вроде бы было что-то типа Rc<Option<T>> и Weak<T>. Сработает ли так в мире Rust?
Сработает. Только не забывайте про Cell/RefCell если вам нужна внутренняя мутабельность (а она точно нужна).
Сработает, как написал mayorovp. Но более каноничным будет сделать такой базовый контейнер на unsafe и голых указателях, верифицировать все unsafe места и предоставить safe интерфейс.
Я так и не понял, зачем автор полез в box. Чем его Box::new не устраивает?
Там если выше в комментариях почитать - у автора какая-то каша в понимании того, что такое box и чем он отличается от Box::new
Ну... если брать Си, то там чаще для списка есть базовая структура, для которой реализуется общая работа со списками для всех, и есть струтктура, которая содержит поле связи. И часто чтобы получить родительскую структуру, используют
offsetof
struct dlist {
struct list * next;
struct list * prev;
};
struct payload {
int data;
struct dlist link;
};
Ну и мне, в общем-то непонятно, почему Rust замена Си, если вещи, которые легко делать на Си, вызывают проблемы в Rust? Это два разных подхода к написанию софта, которые очень плохо взаимозаменяются и сочетаются, два разных инструмента.
Собственно говоря, для меня это достаточно большая проблема, если рассматривать миграцию на Rust: я беру свой сишны проект, который хочу переписать на Rust, Вижу там агрегацию нескольких
mallocв один, вижу там двусвязныё двусвязные циклические списки, где элемент может и не знать, в каком он контейнере расположен, или можно сказать, что он сам по себе контейнер. Какие-то пулы аллокации. И понимаю, что это надо переписывать как-то совершенно по-другому.В C++ да, там мышление контейнерно-оринетированное (STL) и в общем-то перевести его на Rust в общем-то достаточно техническая задача, ИМХО.
Если вам нужно писать свои двусвязные списки — да, в Rust это делается не так просто. Но если ваша задача не писать списки, а использовать их — вы просто вбиваете в гугл "rust intrusive linked list" и находите крейт intrusive_collections.
Во-первых со всем этим не так просто разобраться мне. Это раз. Во-вторых, не факт, что там всё что мне надо. Например, отменить последнее удаление из списке, как в случае реализации алгоритма танцующих связей. Такого метода навскидку я не нашёл. Поэтому то время, что ты потратишь на изучение, не факт, что не придёшь к выводу, что это под это не заточено. Что скорее всего наталкивает на мысль, что в практической реализации я скорее всего использовал бы массив объектов и индексы, так куда больше контроля.
статья очень сумбурная и не уверен к каким выводам приводит читателя, но практичеческий подход в таких ситуациях такой: если структура данных плохо ложится на модель памяти раста и нет подходящей готовой надежной реализации, то ты берешь unsafe и пишешь свою реализацию на сырых указателях, а потом заворачиваешь в безопасное API, которое не даст пользователю порушить никакие инварианты.
если хочется уменьшить шансы накосячить, то обмазываешь тестами, прогоняешь miri, выкладываешь на crates.io и просишь ревью у сообщества - готово.
Про массив объектов и индексы вы думаете зря, можно же в Rust и с указателями работать.
Ну... я больше на примере конкретной задачи типа перебора методом танцующих связей. В этом случае у нас все элементы известных заранее, мы просто добавляем-удаляем их из двусвязных циклических списков. Почему тогда бы тогда не выделить один раз массив и не использовать индексы в нём? Это 100% достаточно для этой задачи. Ну а главное (1) сразу понятно как решать, не надо ничего гуглить и думать, подходит оно или нет (2) не наступишь на грабли, что ты что-то выбрал, начал преализовывать и застакался, потому что кто-то при удалении элемента их списка очищает указатели внутри него, а это ценная информация о том, куда его надо будет вставить назад. А целочисленные переменные Rust точно обнулять не станет.
Если вам настолько не важна константа в производительности — то вам и алгоритм танцующих связей нафиг не нужен. Той же самой асимптотики можно достичь если запоминать удаляемые ноды и их соседей в стеке или в локальных переменных.
Rust и указатели сам по себе не очищает
Ок, давай более конкретный пример. Например,по твоей ссылке
intrusive_collections
Там пример использования
Но для того, чтобы удалиться из двусвязного списка, не надо знать в каком ты списке вообще. Достаточно
a.link.unlink() или list.get_front().link.unlink()Я не понял откуда в вашем примере берется
a. В коде что вы привели pop уже удалил его из списка.Я просто плохо представляю себе сценарий использования. У нас есть список элементов — ок. Мы хотим из него удалить элемент — какой? Ну либо по индексу, либо по какому-то условию. Оба этих сценария кажется библиотека поддерживает через
CursorMut. Чего не хватает?Основной сценарий использования интрузивных коллекций — "прошивание" связями внешних сущностей, которые одновременно использует кто-то ещё.
Не просто же так тот же intrusive_collections разрешает "класть" в списки не только
Box<>с передачей владения, но иRc<>Единственный способ этого достичь это отдавать кишки наружу при вставке, но это плохая идея мне кажется. А без кишок нужно сидеть и за O(N) искать где же элемент в списке, лучше никак не сделать.
Впрочем до сих пор жду какого-нибудь применения для списков в моих задачах. Может быть, когда-нибудь...
Что есть "отдавать кишки наружу при вставке"?
Где тут "кишки наружу"?
link: Link.Remove должен удалять из списка, для этого лежащая внутри списка структура должна про него знать. например это должно быть
List<Linkable<i32>>а не простоList<i32>. Это я и имею в видуВ том то и дело, что не должна. Двусвязный циклический список это такая структура, чтобы удалится из которой не надо вообще знать, откуда удаляться. Я приводил синшный код удаления элемента
В общем это как раз её преимущество: процесс может быть в списке зомби, в списке заблокированных, в списке ожидающих, вообще висеть в воздухе. Но нам это знать не надо, мы просто удаляем его оттуда, где он есть сейчас.
Я просто не сказал бы что это связаный списко. Не любая структура с prev,next это список. Это скорее ListNode. В шарповой стд кстати так и сделано:
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlistnode-1
Это отдельная сущность от
https://docs.microsoft.com/en-us/dotnet/api/system.collections.generic.linkedlist-1
Ну так про ноду и разговор был.
А от куда node будет знать из какого именно списка надо удалиться? Судя по API ничто не мешает добавить его в несколько разных списков (и даже несколько раз в один и тот же).
Разве что list.push_back(node) будет "съедать" node и возвращать какой-то враппер вокруг него, тогда у враппера может быть метод remove().
А знать и не надо, там достаточно два указателя переставить.
И нет, добавить один элемент в два разных интрузивных списка по одному полю невозможно — будет ошибка.
Рантайм ошибка? Т.к. очевидно что компилятор тут ничем не поможет - тип ноды не изменяется от того, что её добавили в список.
В принципе это тоже вариант, но он мне не очень нравится. Зачем перекладывать эту проверку в рантайм, если можно на этапе компиляции гарантировать отсутствие попытки добавить ноду во второй список.
Для того, чтобы не нужно было знать, в каком ты списке. Для построения децентрализованых сетей разных. В целом API можно пофиксить, например, так, если нужна именно надёжность, и тогда неконсистентных состояний не будет (и опять же будет немного неудобно для бэктрекинга):
Не получится у вас ничего гарантировать во время компиляции для интрузивного списка. По крайней мере, без очень сильного макроколдунства.
Рассмотрим для примера простейшую трёхсвязную ноду:
Добавим её в один из списков. Согласно вашей идее, теперь она должна выглядеть как-то так:
Добавим её во второй список:
Видите как наступает комбинаторный взрыв? А ведь мы ещё не касались вопроса как гарантировать что FooInListAB будет лежать по тому же адресу что и FooInListA, и что смещения всех связей у них совпадают...
Если у тебя есть молоток, ты везде видишь гвозди. Если ты не знаешь типичное использование списков, то и не увидишь, где их можно применить.
Обычно про молоток и гвозди вспоминают как про отрицательный пример...
Мы хотим удалить себя. Откуда-нибудь, нам это не важно.
Просто если брать двусвязные циклические списки, то это может быть децентрализованная структура. Например, мы создали пять сущностей, и у всех проиницилизировали линки указателями на себя. Мы получим пять контейнеров с одним элементом:
O1 {O1 O1 }; O2 {O2 O2 }; O3 {O3 O3}; O4 {O4 O4}; O5 {O5 O5}
Потому добавили первый объект к третьему, что в общем-то не отличается от того, что мы добавили третий к первому:
O1 {O3 O3}; O2 {O2 O2}; O3 {O1 O1}; O4 {O4 O4}; O5 {O5 O5}
И у нас четыре контейнера.
Теперь можно добавить пятый после третьему, тогда получится кольцо первый, третий, пятый
O1 {O3 O5}; O2 {O2 O2}; O3 {O5 O1}; O4 {O4 O4}; O5 {O1, O3}
И по сути три контейнера. И т. п.
Получается, что у нас нигде специально выделенного головного контейнера нету. Сам элемент по сути и есть контейнер. Не говоря о том, что в двусвязном списке могут быть элементы самых разных типов.
А все реализации двусвязных циклических списков, которые я видел на Rust, обычно подразумевает, что есть некая единая сущность, которая занимается вопросами удаления/добавления. И строго задают тип элементов в структуре.
Тут соглашусь, не знаю почему они этого API не предоставили.
Работу с памятью можно практически не менять, malloc — нет проблем.
Чтобы задействовать всю мощь Rust надо, действительно, писать несколько иначе. Но можно оставаться и во вполне "сишных" рамках, почему нет. Бонусом будет кросс-компиляция "из-коробки", для embedded скорее всего надо будет побороться с размером исполняемого модуля, недавно была статья по этой теме.
Вызвать malloc проблем нет. Вот только в реальном сишном коде у тебя перемешивается
mallocразные преобразования кintptr_t,offsetofразные прогулки по памяти и т. п. И в Rust это всё делается и более многословно, и с меньшим контролем. Вот, например, если я знаю, что последний элемент типаTэто массив, то могу ли я добавить вmallocнекоторое количество элементов для него?Мощь Rust я понимаю больше как гарантию отсутствия race conditions в сложном многопоточном коде. Но если код однопоточный или достаточно замкнут на свой контекст, вычислительный, то как-бы borrow чекер мне не сильно поможет. И зачем мучиться?
Даже в однопоточном коде можно получить аналоги рейсов. Например добавлять новые элементы в вектор при итерации по нему же. В общем случае это может привести переаллокации куска памяти под вектор и дальнейшей итерации по уже освобождённому куску памяти. Borrow чекер просто не позволит реализвовать такое незаметно. Придётся поприседать, что бы сделать это.
Вектор это плюсы, я говорю про чистый сишный код. Да, возможно это сделать, но в общем-то не могу сказать, что это частая ситуация именно в Си.
Вектор он и в африке вектор, отличаться может только название (например массивом могут называть) - "плоская" коллекция однотипных структур. Моя мысль была в том что однопоточность это не гарантия отсутствия проблем которые предотвращает borrow-чекер. Причём это зачастую не очень очевидные проблемы (как переаллокация вектора при добавлении в него элементов).
Можно глянуть на код для С?
Что насчет автоматического освобождения ресурсов, обобщенных типов, контроля за явной инициализацией всех полей структур, решения проблемы висячих ссылок? Еще есть такая приятная мелочь как "каждое значение имеет одного и только одного владельца-переменную".
КМК и вне рамок многопоточности тут много "плюшек".
Зачем кому-то может понадобиться писать такой код? Для этого в расте (и других языках) есть векторы и массивы, имеющие длину.
https://doc.rust-lang.org/book/ch04-03-slices.html
Все это можно положить в структуру с любыми нужными дополнительными полями. Код для аллокаций и деаллокаций писать не нужно.
Затем что это позволяет избежать дочерних выделений памяти в объекте, которому нужен вектор не-compile-tile длины, которая, тем не менее, известна на этапе инициализации объекта.
А с чего они должны появиться? Если размер известен изначально, то есть
https://doc.rust-lang.org/std/vec/struct.Vec.html#method.with_capacity
Я бы понял всю эту мышиную возню, если бы нужно было иметь структуру с массивом на стэке.
А вы просто заколхозили структуру с массивом и выделяете ее в куче, с помощью кода, чуть менее, чем полностью состоящего из UB.
В связи с чем, я не понял, что мешет в структуру положить указатель на вектор?
Есть у меня объект такого плана:
Мне нужно этот этот объект создавать в куче. Допустим имя объекту дается при инициализации и дальше не меняется - тогда я декларацию заменяю на такую:
и работаю с объектом так, как было написано выше. Зачем? Затем чтобы делать одно выделение памяти вместо двух, что обычно увеличивает производительность/уменьшает фрагментацию кучи.
Не знаю, умеет ли Ваш Vec в такое поведение, если умеет - вопросов нет. Но в плюсах я не знаю как по-другому это сделать.
А с этого места поподробнее, покажите, пожалуйста, пальчиком на конкретные UB, из которых состоит этот код.
Rust умеет вот так:
К сожалению, объявление такого типа — на данный момент это всё что он умеет, создать-инициализировать такую структуру в Rust уже не получится.
Ну... в целом я не вижу большой проблемы в случае автоматического освобождения ресурсов. Сейчас санитайзер в общем-то покажет большую часть таких проблем, и на практике такое фиксится достаточно быстро. Один владелец тоже, если у тебя однопоточный код, что может немного напрягать. И уж точно деля меня это не причина переходить на Rust.
Для меня куда большей плюшкой является паттерн-матчинг на алгебраических типах, что в общем-то заставляет зафорсить обработку всех состояний, которые ты постоянно забываешь. Лично мне это приятнее, чем ООП.
https://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/
Кому лень открывать ссылку проблема есть даже с таким невинным кодом:
Я не спорю. Я не утверждаю, что такого не может быть в принципе. Я написал "не вижу большой проблемы", а не "такое невозможно в принципе".
Мой мойнт больше в том, что такая ситуация больше характерна для C++ где есть контейнеры и неявные операции. И гораздо меньше возникает при чистом сишном стиле кодирования, если мы только не будет писать в нём свою реализацию STL.
Что хочет рассказать автор? Как делать списки в Rust? Эта тема во многом разобрана вот этой замечательной книгой https://rust-unofficial.github.io/too-many-lists/
Имитировать C? Но зачем?
В общем, чепуха какая-то.
Ну вот у автора
но это совсем не в духе сишных двусвязных списков. Хочется иметь что-то в духе
когда элемент удаляется из двусвязного списка, он в принципе не должен знать, из какого списка он удаляется (и список ли это вообще). В Си это две строчки
Собственно говоря интересно, как эти две строки нормально реализовать в Rust.
Так же:
Я этот ответ уже принял, по сути это то, о чём писал
Просто точно так же я могу написать всё на си, и обернуть в so-файл какой-нить.
А на что вы намекаете, говоря, что на С точно так же можно написать? Типа зачем тогда нужен Rust?
Написание программ состоит не только из написания списков. То что оптимальная (по скорости) реализация списков в Rust, посути копирует реализацию из C, не означает, что Rust безполезен и в нём в принципе нельзя писать быстрый код без сырых указателей, unsafe и обхода borrow-чекера.
Вот мы и выяснили, что оне нужен и это все проделки хипстеров чтобы не давать нормальным программистам писать код без головной боли и придирок со стороны компилятора.
Моя мысль была не в том что все надо ансейфом писать, конечно) Плохо ложащуюся на раст структуру написал с ансейфом, завернул в безопасное апи - а дальше весь свой код пишешь на обычном идиоматичном и безопасном Rust.
Просто мой пет-проект это шашечная программа, в которой есть большая сеть из позиций, которая ссылается друг на друга, все они в двусвязных циклических списках. А если весь код выбора хода обернуть unsafe, то какбы ничего и не останется, кроме там парсинга команд из консоли :)
В unsafe надо оборачивать не код выбора кода, а код для работы с позициями. Я более чем уверен, что в шашечная программа не может состоять из одних только перемещений по ссылкам.
Нет, я скорее говорю о том, что Си и Rust достаточно разные инструменты, и я не готов рассматривать Rust как замену для C. Если брать сишный код, то его можно полностью переписать на Rust переосмыслив, но нельзя перевести. И кстати, C++ в этом плане куда ближе к Rust, чем Си. Поэтому лично я готов переходить на Rust из плюсов, там STL навязывает контейнерное мышление. Я понимаю понимаю преимущества Rust для конкурентного программирования и чего-нить более бизнес-ориентированого. Но несколько не готов переходить из Си.
Опять же, мой опыт такой, что я пробовал начинать какие-то пет-проекты на Rust и... не осилил (в основном логические игры типа шашек, футбол на листе бумаги, ...). Большей частью потому, что у тебя сразу возникает видение всего с использованием разных двусвязных кольцевых списков, указателей, несколько децентрализированная система без контейнеров но со ссылками. И ты начинаешь много парится, читать все те ссылки, что тут возникали, через пару дней я чувствую, что "I am wasting fucking life", никакого прогресса и берёшь в руки Си. Поэтому тема списков в Rust несколько больная.
Кстати, а как вы очищаете память в таких системах?
С помощью SIGSEGV, SIGHUP и SIGKILL, вероятно
Про "стиль C++" в списке, а именно про это
Это скорее реализация
std::forward_list(односвязный список), чемstd::list(двусвязный).В C++ можно передать кастомный аллокатор, если нет желания использовать дефолтный.
Эта строка:
Что насчет placement new? В вашем примере объект создается и только потом мувается в это место, но он мог бы сразу создаваться. Это "стиль C++" с С++11. Вместо этой строки должен быть растовый аналог std::aligned_storage<T>, а в методе
push- perfect forwarding аргументов.Все правильно, все справедливо. Список односвязный, как и показано на первой картинке.
Это можно сделать штатно в Rust, но в разбираемых примерах штатный механизм работы с памятью вообще не задействован. В рамках такого подхода невозможного мало, за исключением:
Пробросить параметры конструктора и собрать объект по нужному месту — нет, так нельзя. Даже в кучу поместить, гарантированно минуя стек, можно только в "ночной версии". В ряде случаев компилятор соптимизирует
Box::new::(), конечно.Собственно, как я говорил, если рассматривать Rust как "замену", то это скорее "замена" языка C, чем C++.