Связный список на Rust в стиле С/C++ +6



Может ли безопасный и стабильный 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!()?! Тут какое-то колдунство (дело-то происходит ночью).


Поиск по исходникам дает такой результат:


println:


macro_rules! println {
    () => ($crate::print!("\n"));
    ($($arg:tt)*) => ({
        $crate::io::_print($crate::format_args_nl!($($arg)*));
    })
}

format_args_nl:


    /// 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 */ }};
    }

format_args:


    macro_rules! format_args {
        ($fmt:expr) => {{ /* compiler built-in */ }};
        ($fmt:expr, $($args:tt)*) => {{ /* compiler built-in */ }};
    }

В общем, прикольный язык этот Rust — в нем нельзя без ночного шаманства безопасно поместить значение в кучу и также отсутствует возможность форматировать список значений разных типов.


Такие дела.




Комментарии (93):

  1. csl
    /#23953111 / +1

    рассмотреть количество ключевых слов

    Для Java пятьдесят одно ключевое слово - это включая те, которые пишут в modules-info.java?

  2. mayorovp
    /#23953137 / +9

    Автор демонстрирует, что для новоприбывших в Rust устройство ребер графов традиционным способом выглядит пугающе

    Код, что написан на картинке ниже этого предложения — образец того как нельзя писать код. Ну нельзя делать циклы из Rc, это не имеет смысла.


    В общем, прикольный язык этот Rust — в нем нельзя без ночного шаманства безопасно поместить значение в кучу

    Вообще-то можно, Box::new. Что там внутри — не важно совершенно, сама функция Box::new стабильна и безопасна.

    • maxim_ge
      /#23953369 / -8

      Код, что написан на картинке ниже этого предложения — образец того как нельзя писать код. Ну нельзя делать циклы из Rc, это не имеет смысла.

      На картинке нет цикла из Rc


      Что там внутри — не важно совершенно, сама функция Box::new стабильна и безопасна.

      Предлагается считать функцию Box безопасной, но гарантий, в данном случае, нет. Целиком полагаемся на разработчика. Мало ли что он там поместил внутрь, на то и служат маркеры version=nightly/unsafe чтобы не доверять, а проверять.

      • PsyHaSTe
        /#23953377 / +5

        На картинке нет цикла из Rc

        Возможно я чего-то не понимаю но если я правильно понимаю зачем написаны previous и next то предполагается сделать как раз цикл, если конечно в списке планируется более чем 1 элемент. Поправьте если не прав.


        Предлагается считать функцию Box безопасной, но гарантий, в данном случае, нет. Целиком полагаемся на разработчика. Мало ли что он там поместил внутрь, на то и служат маркеры version=nightly/unsafe чтобы не доверять, а проверять.

        Каких гарантий? Единственной гарантии которую не дает бокс — то что значение будет сразу в куче создано, а не скопировано туда со стека. Это иногда вышибает память при попытке саллоцировать гигабайтные массивы. Это правда, для этого есть нестабильный кейворд box (который вы и использовали).


        Во всех остальных случаях Box::new для всего подходит.

        • maxim_ge
          /#23954323 / -4

          Возможно я чего-то не понимаю но если я правильно понимаю зачем написаны previous и next то предполагается сделать как раз цикл, если конечно в списке планируется более чем 1 элемент.

          Как же может получиться цикл, если список, как бы это… односвязный, т.е. узлы связаны только через previous. Понятно, ребра в некоторомы смысле моделируются еще и через next, но там нет ссылок на другие узлы (т.е. значения типа Node).


          Есть определенная загадка в том, как автор инициализирует ЭТО без Option, и зачем ему ЭТО. Возможно, это был некий черновичок.


          Каких гарантий?

          Гарантий, предоставляемых стабильным компилятором Rust.


          Во всех остальных случаях Box::new для всего подходит.

          Подходит-то он подходит, но речь ведь не об этом.

          • mayorovp
            /#23954359

            Если это и правда граф, а не двусвязный список, то в нём циклы могут быть просто по постановке задачи.


            Гарантий, предоставляемых стабильным компилятором Rust.

            Box::new — это метод стандартной библиотеки. Разумеется, все гарантии компилятора на него распространяются независимо от того что там внутри.

            • maxim_ge
              /#23954431 / -2

              Если это и правда граф, а не двусвязный список, то в нём циклы могут быть просто по постановке задачи.

              На картинке скорее односвязный список с локальными "побегами" одиночной длины.


              Разумеется, все гарантии компилятора на него распространяются независимо от того что там внутри.

              Как могут гарантии стабильного компилятора распространяться на то, что не компилируется?

              • mayorovp
                /#23954783 / +1

                Компилятор даёт гарантии безопасной композиции кода. Проверять корректность базовых элементов кода — вообще не его задача.

      • TargetSan
        /#23953413 / +4

        Предлагается считать функцию Box безопасной, но гарантий, в данном случае, нет. Целиком полагаемся на разработчика. Мало ли что он там поместил внутрь, на то и служат маркеры version=nightly/unsafe чтобы не доверять, а проверять.

        Гм, а как вы в таком случае доверяете функциям выделения памяти в других языках? Там ведь тоже приходится, о ужас, полагаться на разработчика рантайма, разработчика SDK операционной системы… Мало ли что они там внутри понаписывали.


        Если серьёзно, box — такой себе интринсик, завёрнутый в нормальную функцию.

        • maxim_ge
          /#23954533 / -2

          Гм, а как вы в таком случае доверяете функциям выделения памяти в других языках?

          Приходится именно что доверять, "гарантий" компилятора же нет. Понятно, что даже в случае наличия таковых встает вопрос о доверии самому компилятору, но тем не менее...

          • mayorovp
            /#23954789

            Ну вот и тут вам ничего не мешает доверять стандартной библиотеке в той же степени, в какой вы доверяете компилятору — благо, их одни и те же люди пишут.

      • humbug
        /#23953587 / +5

        Максим, nightly в компиляторе и стд — это прямое Quod licet Iovi, non licet bovi. Вы правильно делаете, что копаетесь в кишках стандартной библиотеки, но делаете неправильные выводы.

        • maxim_ge
          /#23954579 / -1

          Quod licet Iovi, non licet bovi

          В целом мотивация упрятать нестабильный box внутрь Box понятна, тут вопросов нет.


          Нет возражений также считать код Box "надёжным", в том смысле, в каком "надёжен" код на любом ЯП — не меньше, но и не больше.


          PS. Для саморазвития — можно глянуть на примеры нестабильного C++ в стд C++?

          • mayorovp
            /#23954903 / -1

            Ну вот, держите:


            https://code.woboq.org/userspace/glibc/bits/stdint-intn.h.html:


            typedef signed int __int32_t;
            typedef __int32_t int32_t;

            Совершенно некорректный с точки зрения стандарта typedef, потому что нет никаких гарантий что signed int имеет разрядность 32 бита в общем случае. Но в glibc такое писать можно.

            • maxim_ge
              /#23954991 / -1

              Пример по ссылке компилируется.


              Нестабильный компилироваться не должен.

              • ozkriff
                /#23955019

                На какой-то платформе соберется и будет нормально работать, на какой-то взорвется нафиг. Мы ж про плюсы говорим, а сам по себе плюсовый компилятор не склонен помогать программисту замечать что тот делает странное

                • maxim_ge
                  /#23955053

                  На какой-то платформе соберется и будет нормально работать, на какой-то взорвется нафиг.

                  Вот это взорвется? https://www.onlinegdb.com/vmdoJZFgL


                  Поясните, из-за чего?


                  Мы ж про плюсы говорим

                  Вообще меня интересовали примеры нестабильного C++ в стандартной библиотеке C++.


                  Пока рассматриваем стабильный из С.

                  • ozkriff
                    /#23955177 / -2

                    Выше пример не такой был, суть же в - `typedef signed int __int32_t;` - такое можно писать только в частном случае, когда мы знаем каким компилятором собираемся и на какой архитектуре, иначе это лютое UB и код использующий __int32_t дальше или тупо не соберется, или принесет много веселья в отладке странных ошибок.
                    Аналогичным образом msvc реализация плюсовой стандартной либы использует дофига компилятор-специфичных интринсиков и предположений.

                    • maxim_ge
                      /#23955245 / -1

                      Выше пример не такой был

                      Это разве был интересующий пример нестабильного C++ в стандартной библиотеке C++?


                      и код использующий __int32_t дальше или тупо не соберется, или принесет много веселья в отладке странных ошибок.

                      Чем же лучше версия на Rust:


                      type Int32T = isize;

                      ?

                      • mayorovp
                        /#23955313 / +1

                        Во-первых, ничем не лучше — вы как бы просили аналог же.
                        Во-вторых, где вы в стандартной библиотеке Rust нашли эту строчку?

                      • ozkriff
                        /#23955405

                        Это разве был интересующий пример нестабильного C++ в стандартной библиотеке C++?

                        а разве нет? ну хорошо, вот прям ссылка на то как GCC реализация stdc++ использует кучу builtin штук компилятора https://github.com/gcc-mirror/gcc/search?q=path%3Alibstdc%2B%2B-v3%2Fsrc+builtin так убедительней? Или может я вопрос как-то не так понял?

                        Чем же лучше версия на Rust: `type Int32T = isize;`?

                        Стоп, откуда тут лучше-хуже взялось и какое отношение этот пример имеет к стандартным библиотекам раста и плюсов? ????‍????Разговор же был о том, что стандартные библиотеки языков часто используют платформо-компиляторо-специфичный код в своих реализациях и это нормально.

                      • maxim_ge
                        /#23955577 / -1

                        а разве нет?

                        typedef signed int __int32_t;? — Нет.


                        ну хорошо, вот прям ссылка на то как GCC реализация stdc++ использует кучу builtin штук компилятора

                        Это все компилируется стабильным компилятором
                        https://godbolt.org/z/8qEezhbch


                        Меня интересуют примеры, когда для компиляции стандартной библиотеки надо включить "ночную" опцию у компилятора.

                      • ozkriff
                        /#23955603 / +2

                        Эм. Такого нет, конечно - в плюсах отсутсвует явный механизм индикации нестабильности чего-то и явное разделение на стабильный-ночной версии компилятора. Только нестабильные штуки из реализации std от этого не пропадают, просто, как выше сказано, это все руками надо отслеживать.

                      • maxim_ge
                        /#23955689 / -4

                        Такого нет, конечно — в плюсах отсутсвует явный механизм индикации нестабильности чего-то и явное разделение на стабильный-ночной версии компилятора. Только нестабильные штуки из реализации std от этого не пропадают,

                        Вообще, это означает, что "нестабильных штук" там нет, т.е. можно взять компилятор и скомпилировать к нему библиотеку.


                        Есть "нестандартные штуки", т.е. другим компилятором эта библиотека может не скопилироваться.

                      • ozkriff
                        /#23955725

                        А мы какое определение "нестабильности" тут используем? В моем понимании это все, что не входит в стандарт языка.

                      • maxim_ge
                        /#23955803

                        Это хороший подход — договориться про определения.


                        Нестабильный код (или unstable feature) требует особой версии компилятора — альфа, ночная и прочая. Стабильной версией (release, production) нестабильный код компилироваться не должен. Вкратце эти тезисы излагал тут.

                      • Cykooz
                        /#23955839 / +5

                        Я лично уже запутался, какие у вас претензии к тому, что box не работает в пользовательсокм коде в стабильной версии Rust?

                        Вроде всё очевидно - интерфейс этого "оператора" ещё не стабилизирован. Всё ещё есть вероятность, что его могут поменять (например решат, что он должен возвращать Result<Box<T>>, вместо Box<T>).

                        Но это не означает, что стандартная библиотека не может его использовать. Если бы это был не "оператор" языка, а функция, то её могли бы сделать приватной, и у вас точно так же не получилось бы её использовать в своём коде.

                      • maxim_ge
                        /#23955873

                        Я лично уже запутался, какие у вас претензии к тому, что box не работает в пользовательсокм коде в стабильной версии Rust?

                        Давайте так поступим — процитируйте какое-либо мое утверждение из статьи и далее я поясню его, если это нужно.

                      • PsyHaSTe
                        /#23955929 / +3

                        Ну у меня вопрос к вот этой части


                        Что такое box x? Попробуем:

                        Просто не очень понятно с чего вы решили что можно просто скопировать код из STD и он заработает. Ну возьмем для примера тип int из стд сишарпа:


                        https://github.com/dotnet/runtime/blob/main/src/libraries/System.Private.CoreLib/src/System/Int32.cs#L16


                        Мы там увидем примерно такое:


                        public readonly struct Int32
                        {
                          private readonly Int32 m_value;
                          ...
                        }

                        Как думаете, можно такое скопировать в свой код чтобы оно скомпилировалось?

                      • maxim_ge
                        /#23956049 / -1

                        Просто не очень понятно с чего вы решили что можно просто скопировать код из STD и он заработает.

                        Я разве написал, что он должен заработать? В цитате этого нет. В цитате есть "Попробуем".


                        Мы там увидем примерно такое:
                        public readonly struct Int32
                        {
                        private readonly Int32 m_value;
                        ...
                        }

                        Тут странно. Я вижу такое:


                        public readonly struct Int32
                        {
                          private readonly int m_value;
                        }

                        И это работает, по крайней мере, тут.

                      • PsyHaSTe
                        /#23956291 / +1

                        Тут странно. Я вижу такое

                        А я специально для вас упростил, чтобы лучше поинт передать. Потому что это одно и то же

                      • mayorovp
                        /#23958001 / +1

                        int — это как бы синоним для System.Int32

                      • Cykooz
                        /#23955973 / +5

                        Я в принципе не понимаю зачем вы полезли в реализацию Box::new(), зачем решили использовать в своём коде box. И после этого сделали выводы как в анекдоте про сибирских лесорубов, которые засунули стальной лом в японскую лесопилку.

                        Почему нельзя было использовать Box::new()? Вам что-ли принципильно хотелось с самого начала оперировать только указателями, что бы "всё как в С"?

                      • mayorovp
                        /#23955605 / +1

                        Ночную-не ночную, но вот кучу флагов включать придётся хотя бы для того, чтобы компилятор реализацию какого-нибудь memset не заменил на вызов memset (имеет право, однако!)

  3. MFilonen2
    /#23953157

    Вот мне интересно, на Swift я решал бы задачу двусвязного списка через сильную ссылку next и слабую на previous. То есть в мире раста это вроде бы было что-то типа Rc<Option<T>> и Weak<T>. Сработает ли так в мире Rust?

    • mayorovp
      /#23953269 / +4

      Сработает. Только не забывайте про Cell/RefCell если вам нужна внутренняя мутабельность (а она точно нужна).

    • TargetSan
      /#23953429 / +3

      Сработает, как написал mayorovp. Но более каноничным будет сделать такой базовый контейнер на unsafe и голых указателях, верифицировать все unsafe места и предоставить safe интерфейс.

  4. middle
    /#23954167 / +5

    Я так и не понял, зачем автор полез в box. Чем его Box::new не устраивает?

    • Ritan
      /#23954893 / +1

      Там если выше в комментариях почитать - у автора какая-то каша в понимании того, что такое box и чем он отличается от Box::new

  5. mustitz
    /#23954287

    Ну... если брать Си, то там чаще для списка есть базовая структура, для которой реализуется общая работа со списками для всех, и есть струтктура, которая содержит поле связи. И часто чтобы получить родительскую структуру, используют offsetof

    struct dlist {
    struct list * next;
    struct list * prev;
    };

    struct payload {
    int data;
    struct dlist link;
    };


    Ну и мне, в общем-то непонятно, почему Rust замена Си, если вещи, которые легко делать на Си, вызывают проблемы в Rust? Это два разных подхода к написанию софта, которые очень плохо взаимозаменяются и сочетаются, два разных инструмента.

    Собственно говоря, для меня это достаточно большая проблема, если рассматривать миграцию на Rust: я беру свой сишны проект, который хочу переписать на Rust, Вижу там агрегацию нескольких malloc в один, вижу там двусвязныё двусвязные циклические списки, где элемент может и не знать, в каком он контейнере расположен, или можно сказать, что он сам по себе контейнер. Какие-то пулы аллокации. И понимаю, что это надо переписывать как-то совершенно по-другому.

    В C++ да, там мышление контейнерно-оринетированное (STL) и в общем-то перевести его на Rust в общем-то достаточно техническая задача, ИМХО.

    • mayorovp
      /#23954345 / +3

      Если вам нужно писать свои двусвязные списки — да, в Rust это делается не так просто. Но если ваша задача не писать списки, а использовать их — вы просто вбиваете в гугл "rust intrusive linked list" и находите крейт intrusive_collections.

      • mustitz
        /#23954859

        Во-первых со всем этим не так просто разобраться мне. Это раз. Во-вторых, не факт, что там всё что мне надо. Например, отменить последнее удаление из списке, как в случае реализации алгоритма танцующих связей. Такого метода навскидку я не нашёл. Поэтому то время, что ты потратишь на изучение, не факт, что не придёшь к выводу, что это под это не заточено. Что скорее всего наталкивает на мысль, что в практической реализации я скорее всего использовал бы массив объектов и индексы, так куда больше контроля.

        • ozkriff
          /#23954945 / +7

          статья очень сумбурная и не уверен к каким выводам приводит читателя, но практичеческий подход в таких ситуациях такой: если структура данных плохо ложится на модель памяти раста и нет подходящей готовой надежной реализации, то ты берешь unsafe и пишешь свою реализацию на сырых указателях, а потом заворачиваешь в безопасное API, которое не даст пользователю порушить никакие инварианты.

          если хочется уменьшить шансы накосячить, то обмазываешь тестами, прогоняешь miri, выкладываешь на crates.io и просишь ревью у сообщества - готово.

        • mayorovp
          /#23955303

          Про массив объектов и индексы вы думаете зря, можно же в Rust и с указателями работать.

          • mustitz
            /#23955535

            Ну... я больше на примере конкретной задачи типа перебора методом танцующих связей. В этом случае у нас все элементы известных заранее, мы просто добавляем-удаляем их из двусвязных циклических списков. Почему тогда бы тогда не выделить один раз массив и не использовать индексы в нём? Это 100% достаточно для этой задачи. Ну а главное (1) сразу понятно как решать, не надо ничего гуглить и думать, подходит оно или нет (2) не наступишь на грабли, что ты что-то выбрал, начал преализовывать и застакался, потому что кто-то при удалении элемента их списка очищает указатели внутри него, а это ценная информация о том, куда его надо будет вставить назад. А целочисленные переменные Rust точно обнулять не станет.

            • mayorovp
              /#23955565

              Если вам настолько не важна константа в производительности — то вам и алгоритм танцующих связей нафиг не нужен. Той же самой асимптотики можно достичь если запоминать удаляемые ноды и их соседей в стеке или в локальных переменных.


              А целочисленные переменные Rust точно обнулять не станет.

              Rust и указатели сам по себе не очищает

              • mustitz
                /#23955765

                Ок, давай более конкретный пример. Например,по твоей ссылке
                intrusive_collections

                Там пример использования

                // Insert the objects at the front of the list
                list.push_front(a);
                list.push_front(b);
                list.push_front(c);
                
                // .....
                let a = list.pop_front().unwrap();


                Но для того, чтобы удалиться из двусвязного списка, не надо знать в каком ты списке вообще. Достаточно a.link.unlink() или list.get_front().link.unlink()

                • PsyHaSTe
                  /#23955887 / -1

                  Я не понял откуда в вашем примере берется a. В коде что вы привели pop уже удалил его из списка.


                  Я просто плохо представляю себе сценарий использования. У нас есть список элементов — ок. Мы хотим из него удалить элемент — какой? Ну либо по индексу, либо по какому-то условию. Оба этих сценария кажется библиотека поддерживает через CursorMut. Чего не хватает?

                  • mayorovp
                    /#23955933

                    Основной сценарий использования интрузивных коллекций — "прошивание" связями внешних сущностей, которые одновременно использует кто-то ещё.


                    Не просто же так тот же intrusive_collections разрешает "класть" в списки не только Box<> с передачей владения, но и Rc<>

                    • PsyHaSTe
                      /#23955971 / -1

                      Единственный способ этого достичь это отдавать кишки наружу при вставке, но это плохая идея мне кажется. А без кишок нужно сидеть и за O(N) искать где же элемент в списке, лучше никак не сделать.


                      Впрочем до сих пор жду какого-нибудь применения для списков в моих задачах. Может быть, когда-нибудь...

                      • mayorovp
                        /#23956015

                        Что есть "отдавать кишки наружу при вставке"?


                        struct Foo {
                            link: Link,
                        }
                        
                        intrusive_adapter!(FooLink = Rc<Foo>: Foo { link:L Link });
                        
                        // ...
                        
                        let node: Rc<Foo>;
                        let list: LinkedList<FooLink>;
                        
                        list.push_back(node);
                        node.remove(); // нету такого API

                        Где тут "кишки наружу"?

                      • PsyHaSTe
                        /#23956037

                        Где тут "кишки наружу"?

                        link: Link.
                        Remove должен удалять из списка, для этого лежащая внутри списка структура должна про него знать. например это должно быть List<Linkable<i32>> а не просто List<i32>. Это я и имею в виду

                      • mustitz
                        /#23956359

                        В том то и дело, что не должна. Двусвязный циклический список это такая структура, чтобы удалится из которой не надо вообще знать, откуда удаляться. Я приводил синшный код удаления элемента

                        struct dlist
                        {
                            struct dlist * next;
                            struct dlist * prev;
                        };
                        
                        static inline void dlist_remove(struct dlist * elem)
                        {
                            elem->prev->next = elem->next;
                            elem->next->prev = elem->prev;
                        }


                        В общем это как раз её преимущество: процесс может быть в списке зомби, в списке заблокированных, в списке ожидающих, вообще висеть в воздухе. Но нам это знать не надо, мы просто удаляем его оттуда, где он есть сейчас.

                      • mayorovp
                        /#23958013

                        Ну так про ноду и разговор был.

                      • Cykooz
                        /#23956093 / +1

                        А от куда node будет знать из какого именно списка надо удалиться? Судя по API ничто не мешает добавить его в несколько разных списков (и даже несколько раз в один и тот же).

                        Разве что list.push_back(node) будет "съедать" node и возвращать какой-то враппер вокруг него, тогда у враппера может быть метод remove().

                      • mayorovp
                        /#23956153

                        А от куда node будет знать из какого именно списка надо удалиться? Судя по API ничто не мешает добавить его в несколько разных списков (и даже несколько раз в один и тот же).

                        А знать и не надо, там достаточно два указателя переставить.


                        И нет, добавить один элемент в два разных интрузивных списка по одному полю невозможно — будет ошибка.

                      • Cykooz
                        /#23956247

                        Рантайм ошибка? Т.к. очевидно что компилятор тут ничем не поможет - тип ноды не изменяется от того, что её добавили в список.

                        В принципе это тоже вариант, но он мне не очень нравится. Зачем перекладывать эту проверку в рантайм, если можно на этапе компиляции гарантировать отсутствие попытки добавить ноду во второй список.

                      • mustitz
                        /#23956597

                        Для того, чтобы не нужно было знать, в каком ты списке. Для построения децентрализованых сетей разных. В целом API можно пофиксить, например, так, если нужна именно надёжность, и тогда неконсистентных состояний не будет (и опять же будет немного неудобно для бэктрекинга):

                        struct dlist
                        {
                            struct dlist * next;
                            struct dlist * prev;
                        };
                        
                        static inline void dlist_init(struct dlist * restrict me)
                        {
                            me->next = me;
                            me->prev = me;
                        }
                        
                        static inline void dlist_insert_after(struct dlist * me infant, struct dlist * prev)
                        {
                            dlist_remove(me);
                        
                            struct dlist * next = prev->next;
                            me->next = next;
                            me->prev = prev;
                            next->prev = me;
                            prev->next = me;
                        };
                        
                        static inline void dlist_insert_before(struct dlist * me infant, struct dlist * next)
                        {
                            dlist_remove(me);
                        
                            struct dlist * prev = next->prev;
                            me->next = next;
                            me->prev = prev;
                            next->prev = me;
                            prev->next = me;
                        }
                        
                        
                        static inline void dlist_remove(struct dlist * me)
                        {
                            me->prev->next = me->next;
                            me->next->prev = me->prev;
                            dlist_init(me);
                        }

                      • mayorovp
                        /#23957989 / +1

                        Не получится у вас ничего гарантировать во время компиляции для интрузивного списка. По крайней мере, без очень сильного макроколдунства.


                        Рассмотрим для примера простейшую трёхсвязную ноду:


                        struct Foo {
                            linkA: Link,
                            linkB: Link,
                            linkC: Link,
                        
                            // поля с данными
                        }

                        Добавим её в один из списков. Согласно вашей идее, теперь она должна выглядеть как-то так:


                        struct FooInListA {
                            linkA: UsedLink,
                            linkB: Link,
                            linkC: Link,
                        
                            // поля с данными
                        }

                        Добавим её во второй список:


                        struct FooInListAB {
                            linkA: UsedLink,
                            linkB: UsedLink,
                            linkC: Link,
                        
                            // поля с данными
                        }

                        Видите как наступает комбинаторный взрыв? А ведь мы ещё не касались вопроса как гарантировать что FooInListAB будет лежать по тому же адресу что и FooInListA, и что смещения всех связей у них совпадают...

                      • mustitz
                        /#23956389

                        Впрочем до сих пор жду какого-нибудь применения для списков в моих задачах. Может быть, когда-нибудь...


                        Если у тебя есть молоток, ты везде видишь гвозди. Если ты не знаешь типичное использование списков, то и не увидишь, где их можно применить.

                      • mayorovp
                        /#23958021

                        Обычно про молоток и гвозди вспоминают как про отрицательный пример...

                  • mustitz
                    /#23956317

                    Мы хотим из него удалить элемент — какой?


                    Мы хотим удалить себя. Откуда-нибудь, нам это не важно.

                    Просто если брать двусвязные циклические списки, то это может быть децентрализованная структура. Например, мы создали пять сущностей, и у всех проиницилизировали линки указателями на себя. Мы получим пять контейнеров с одним элементом:

                    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, обычно подразумевает, что есть некая единая сущность, которая занимается вопросами удаления/добавления. И строго задают тип элементов в структуре.

                • mayorovp
                  /#23955903 / +1

                  Тут соглашусь, не знаю почему они этого API не предоставили.

    • maxim_ge
      /#23954393 / +1

      Вижу там агрегацию нескольких malloc в один, вижу там двусвязныё двусвязные циклические списки, где элемент может и не знать, в каком он контейнере расположен, или можно сказать, что он сам по себе контейнер.

      Работу с памятью можно практически не менять, malloc — нет проблем.


      res = libc::malloc(std::mem::size_of::<T>()) as *mut T;

      И понимаю, что это надо переписывать как-то совершенно по-другому.

      Чтобы задействовать всю мощь Rust надо, действительно, писать несколько иначе. Но можно оставаться и во вполне "сишных" рамках, почему нет. Бонусом будет кросс-компиляция "из-коробки", для embedded скорее всего надо будет побороться с размером исполняемого модуля, недавно была статья по этой теме.

      • mustitz
        /#23954949

        Вызвать malloc проблем нет. Вот только в реальном сишном коде у тебя перемешивается malloc разные преобразования к intptr_t, offsetof разные прогулки по памяти и т. п. И в Rust это всё делается и более многословно, и с меньшим контролем. Вот, например, если я знаю, что последний элемент типа T это массив, то могу ли я добавить в malloc некоторое количество элементов для него?

        Мощь Rust я понимаю больше как гарантию отсутствия race conditions в сложном многопоточном коде. Но если код однопоточный или достаточно замкнут на свой контекст, вычислительный, то как-бы borrow чекер мне не сильно поможет. И зачем мучиться?

        • Cykooz
          /#23955143 / +1

          Даже в однопоточном коде можно получить аналоги рейсов. Например добавлять новые элементы в вектор при итерации по нему же. В общем случае это может привести переаллокации куска памяти под вектор и дальнейшей итерации по уже освобождённому куску памяти. Borrow чекер просто не позволит реализвовать такое незаметно. Придётся поприседать, что бы сделать это.

          • mustitz
            /#23955169

            Вектор это плюсы, я говорю про чистый сишный код. Да, возможно это сделать, но в общем-то не могу сказать, что это частая ситуация именно в Си.

            • Cykooz
              /#23955381 / +1

              Вектор он и в африке вектор, отличаться может только название (например массивом могут называть) - "плоская" коллекция однотипных структур. Моя мысль была в том что однопоточность это не гарантия отсутствия проблем которые предотвращает borrow-чекер. Причём это зачастую не очень очевидные проблемы (как переаллокация вектора при добавлении в него элементов).

        • maxim_ge
          /#23955147 / +3

          Вот, например, если я знаю, что последний элемент типа T это массив, то могу ли я добавить в malloc некоторое количество элементов для него?

          Можно глянуть на код для С?


          Мощь Rust я понимаю больше как гарантию отсутствия race conditions в сложном многопоточном коде.

          Что насчет автоматического освобождения ресурсов, обобщенных типов, контроля за явной инициализацией всех полей структур, решения проблемы висячих ссылок? Еще есть такая приятная мелочь как "каждое значение имеет одного и только одного владельца-переменную".


          КМК и вне рамок многопоточности тут много "плюшек".

          • mustitz
            /#23955235

            #include <stdlib.h>
            #include <stdio.h>
            
            struct test {
              int len;
              int data[0];
            };
            
            struct test * create(int len)
            {
                struct test * result = malloc(sizeof(struct test) + len * sizeof(int));
                result->len = len;
                for (int i=0; i<len; ++i) {
                    result->data[i] = 1 + i * 2;
                }
                return result;
            }
            
            void echo(const struct test * test)
            {
                printf("Data:");
                for (int i=0; i<test->len; ++i) {
                    printf(" %d", test->data[i]);
                }
                printf("\n");
            }
            
            int main() {
                struct test * restrict test = create(5);
                echo(test);
                free(test);
                return 0;
            }

            • Gordon01
              /#23961403 / +1

              Зачем кому-то может понадобиться писать такой код? Для этого в расте (и других языках) есть векторы и массивы, имеющие длину.

              https://doc.rust-lang.org/book/ch04-03-slices.html

              Все это можно положить в структуру с любыми нужными дополнительными полями. Код для аллокаций и деаллокаций писать не нужно.

              • picul
                /#23961917

                Затем что это позволяет избежать дочерних выделений памяти в объекте, которому нужен вектор не-compile-tile длины, которая, тем не менее, известна на этапе инициализации объекта.

                • Gordon01
                  /#23962393

                  избежать дочерних выделений памяти в объекте

                  А с чего они должны появиться? Если размер известен изначально, то есть

                  https://doc.rust-lang.org/std/vec/struct.Vec.html#method.with_capacity

                  Я бы понял всю эту мышиную возню, если бы нужно было иметь структуру с массивом на стэке.

                  А вы просто заколхозили структуру с массивом и выделяете ее в куче, с помощью кода, чуть менее, чем полностью состоящего из UB.

                  В связи с чем, я не понял, что мешет в структуру положить указатель на вектор?

                  • picul
                    /#23962713 / +2

                    Есть у меня объект такого плана:

                    struct Obj
                    {
                    	uint32 a;
                      float b;
                      string name;
                    };

                    Мне нужно этот этот объект создавать в куче. Допустим имя объекту дается при инициализации и дальше не меняется - тогда я декларацию заменяю на такую:

                    struct Obj
                    {
                    	uint32 a;
                      float b;
                      size_t name_length;
                      char name[0];
                    };

                    и работаю с объектом так, как было написано выше. Зачем? Затем чтобы делать одно выделение памяти вместо двух, что обычно увеличивает производительность/уменьшает фрагментацию кучи.

                    Не знаю, умеет ли Ваш Vec в такое поведение, если умеет - вопросов нет. Но в плюсах я не знаю как по-другому это сделать.

                    А вы просто заколхозили структуру с массивом и выделяете ее в куче, с помощью кода, чуть менее, чем полностью состоящего из UB.

                    А с этого места поподробнее, покажите, пожалуйста, пальчиком на конкретные UB, из которых состоит этот код.

                    • mayorovp
                      /#23963459

                      Rust умеет вот так:


                      struct Obj
                      {
                          a: u32,
                          b: f32,
                          name: str, // строка неизвестного размера
                      }

                      К сожалению, объявление такого типа — на данный момент это всё что он умеет, создать-инициализировать такую структуру в Rust уже не получится.

          • mustitz
            /#23955293

            Что насчет автоматического освобождения ресурсов, обобщенных типов, контроля за явной инициализацией всех полей структур, решения проблемы висячих ссылок? Еще есть такая приятная мелочь как "каждое значение имеет одного и только одного владельца-переменную".


            Ну... в целом я не вижу большой проблемы в случае автоматического освобождения ресурсов. Сейчас санитайзер в общем-то покажет большую часть таких проблем, и на практике такое фиксится достаточно быстро. Один владелец тоже, если у тебя однопоточный код, что может немного напрягать. И уж точно деля меня это не причина переходить на Rust.

            Для меня куда большей плюшкой является паттерн-матчинг на алгебраических типах, что в общем-то заставляет зафорсить обработку всех состояний, которые ты постоянно забываешь. Лично мне это приятнее, чем ООП.

            • PsyHaSTe
              /#23955947 / +2

              Один владелец тоже, если у тебя однопоточный код, что может немного напрягать.

              https://manishearth.github.io/blog/2015/05/17/the-problem-with-shared-mutability/


              Кому лень открывать ссылку проблема есть даже с таким невинным кодом:


              enum StringOrInt {
                  Str(String),
                  Int(i64)
              }
              
              // Create an instance of the `Str` variant with associated string "Hi!"
              let x = Str("Hi!".to_string()); 
               // Create a mutable alias to x
              let y = &mut x;
              // If x is a `Str`, assign its inner data to the variable `insides`
              if let Str(ref insides) = x { 
                  // Set `*y` to `Int(1), therefore setting `x` to `Int(1)` too
                  *y = Int(1); 
                  println!("x says: {}", insides); // Uh oh!
              }

              • mustitz
                /#23956033

                Я не спорю. Я не утверждаю, что такого не может быть в принципе. Я написал "не вижу большой проблемы", а не "такое невозможно в принципе".

                Мой мойнт больше в том, что такая ситуация больше характерна для C++ где есть контейнеры и неявные операции. И гораздо меньше возникает при чистом сишном стиле кодирования, если мы только не будет писать в нём свою реализацию STL.

  6. enabokov
    /#23955673 / +1

    Что хочет рассказать автор? Как делать списки в Rust? Эта тема во многом разобрана вот этой замечательной книгой https://rust-unofficial.github.io/too-many-lists/

    Имитировать C? Но зачем?

    В общем, чепуха какая-то.

    • mustitz
      /#23955913

      Ну вот у автора

      list.push_left(5);                      // [5, _, 3, 4, 1]
      assert_eq!(list.pop_right(), Some(3));  // [5, _, 4, 1]
      assert_eq!(list.pop_left(), Some(5));   // [_, 4, 1]

      но это совсем не в духе сишных двусвязных списков. Хочется иметь что-то в духе

      list.get_front().link.unlink()

      когда элемент удаляется из двусвязного списка, он в принципе не должен знать, из какого списка он удаляется (и список ли это вообще). В Си это две строчки

      struct dlist
      {
          struct dlist * next;
          struct dlist * prev;
      };
      
      static inline void dlist_remove(struct dlist * elem)
      {
          elem->prev->next = elem->next;
          elem->next->prev = elem->prev;
      }

      Собственно говоря интересно, как эти две строки нормально реализовать в Rust.

      • mayorovp
        /#23955989 / +3

        Так же:


        struct dlist {
            next: *mut dlist,
            prev: *mut dlist,
        }
        
        impl dlist {
            unsafe fn remove(&mut self) {
                (*self.prev).next = self.next;
                (*self.next).prev = self.prev;
            }
        }

        • mustitz
          /#23956185

          Я этот ответ уже принял, по сути это то, о чём писал

          @ozkrif
          то ты берешь unsafe и пишешь свою реализацию на сырых указателях, а потом заворачиваешь в безопасное API


          Просто точно так же я могу написать всё на си, и обернуть в so-файл какой-нить.

          • Cykooz
            /#23956327

            А на что вы намекаете, говоря, что на С точно так же можно написать? Типа зачем тогда нужен Rust?

            Написание программ состоит не только из написания списков. То что оптимальная (по скорости) реализация списков в Rust, посути копирует реализацию из C, не означает, что Rust безполезен и в нём в принципе нельзя писать быстрый код без сырых указателей, unsafe и обхода borrow-чекера.

            • PsyHaSTe
              /#23956357 / -1

              Типа зачем тогда нужен Rust?

              Вот мы и выяснили, что оне нужен и это все проделки хипстеров чтобы не давать нормальным программистам писать код без головной боли и придирок со стороны компилятора.

            • ozkriff
              /#23956427

              Моя мысль была не в том что все надо ансейфом писать, конечно) Плохо ложащуюся на раст структуру написал с ансейфом, завернул в безопасное апи - а дальше весь свой код пишешь на обычном идиоматичном и безопасном Rust.

              • mustitz
                /#23956805

                Просто мой пет-проект это шашечная программа, в которой есть большая сеть из позиций, которая ссылается друг на друга, все они в двусвязных циклических списках. А если весь код выбора хода обернуть unsafe, то какбы ничего и не останется, кроме там парсинга команд из консоли :)

                • mayorovp
                  /#23958043 / +4

                  В unsafe надо оборачивать не код выбора кода, а код для работы с позициями. Я более чем уверен, что в шашечная программа не может состоять из одних только перемещений по ссылкам.

            • mustitz
              /#23956745

              Нет, я скорее говорю о том, что Си и Rust достаточно разные инструменты, и я не готов рассматривать Rust как замену для C. Если брать сишный код, то его можно полностью переписать на Rust переосмыслив, но нельзя перевести. И кстати, C++ в этом плане куда ближе к Rust, чем Си. Поэтому лично я готов переходить на Rust из плюсов, там STL навязывает контейнерное мышление. Я понимаю понимаю преимущества Rust для конкурентного программирования и чего-нить более бизнес-ориентированого. Но несколько не готов переходить из Си.

              Опять же, мой опыт такой, что я пробовал начинать какие-то пет-проекты на Rust и... не осилил (в основном логические игры типа шашек, футбол на листе бумаги, ...). Большей частью потому, что у тебя сразу возникает видение всего с использованием разных двусвязных кольцевых списков, указателей, несколько децентрализированная система без контейнеров но со ссылками. И ты начинаешь много парится, читать все те ссылки, что тут возникали, через пару дней я чувствую, что "I am wasting fucking life", никакого прогресса и берёшь в руки Си. Поэтому тема списков в Rust несколько больная.

              • mayorovp
                /#23958051 / +2

                несколько децентрализированная система без контейнеров но со ссылками

                Кстати, а как вы очищаете память в таких системах?

                • Gordon01
                  /#23961433

                  С помощью SIGSEGV, SIGHUP и SIGKILL, вероятно

  7. Izaron
    /#23956391 / +1

    Про "стиль C++" в списке, а именно про это

    pub struct Item<T> {
        data: T,
        next: *const Item<T>,
    }
    
    pub struct List<T> {
        head: *const Item<T>,
    }

    Это скорее реализация std::forward_list (односвязный список), чем std::list (двусвязный).

    В C++ можно передать кастомный аллокатор, если нет желания использовать дефолтный.

    Эта строка:

    data: T,

    Что насчет placement new? В вашем примере объект создается и только потом мувается в это место, но он мог бы сразу создаваться. Это "стиль C++" с С++11. Вместо этой строки должен быть растовый аналог std::aligned_storage<T>, а в методе push - perfect forwarding аргументов.

    • maxim_ge
      /#23961911

      Все правильно, все справедливо. Список односвязный, как и показано на первой картинке.


      В C++ можно передать кастомный аллокатор, если нет желания использовать дефолтный.

      Это можно сделать штатно в Rust, но в разбираемых примерах штатный механизм работы с памятью вообще не задействован. В рамках такого подхода невозможного мало, за исключением:


      Вместо этой строки должен быть растовый аналог std::aligned_storageT, а в методе push — perfect forwarding аргументов.

      Пробросить параметры конструктора и собрать объект по нужному месту — нет, так нельзя. Даже в кучу поместить, гарантированно минуя стек, можно только в "ночной версии". В ряде случаев компилятор соптимизирует Box::new::(), конечно.


      Собственно, как я говорил, если рассматривать Rust как "замену", то это скорее "замена" языка C, чем C++.