Атака на пакет arrayref Rust

есть возможность включить unsafe и всё равно использовать

Неатомарный без синхронизации - нельзя.

и прочие другие тем не менее отъели у с/с++ изрядный кусок. Хотя и не похо

но хоронили-то как. прямо тут на сайте лет 20 назад

это не решает никак проблему с владением и временем жизни узлов в исходном примере

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

type NodePtr<T> = *mut Node<T>;

struct Node<T> {
    val: T,
    prev: NodePtr<T>,
    next: NodePtr<T>,
}
#[derive(Default)]
struct DList<T> {
    head: NodePtr<T>,
    tail: NodePtr<T>,
}
impl<T> DList<T> {
    pub fn push_front(&mut self, val: T) {
        unsafe {
            let node = alloc(Layout::new::<Node<T>>()) as NodePtr<T>;
            assert!( !node.is_null() );
            node.write(Node {
                val: val,
                prev: self.tail,
                next: null_mut(),
            });
            if !self.tail.is_null() {
                (*self.tail).next = node;
            } else {
                self.head = node;
            }
            self.tail = node;
        }
    }
    // такое должно быть ансейф т.к. node может быть какой угодно
    pub unsafe fn remove(&mut self, node: NodePtr<T>) {
        unsafe {
            if !(*node).prev.is_null() {
                 (*((*node).prev)).next = (*node).next;
            } else {
                self.head = (*node).next;
            }
            if !(*node).next.is_null() {
                (*((*node).next)).prev = (*node).prev;
            } else {
                self.tail = (*node).next;
            }
            dealloc(node as *mut u8, Layout::new::<Node<T>>());
        }
    }
    pub fn head_iter(&self) -> DListIter<'_, T> {
        DListIter { node: self.head, _p: PhantomData }
    }
}

impl<T> Drop for DList<T> {
    fn drop(&mut self) {
        let mut p = self.head;
        unsafe {
            while !p.is_null() {
                let next = (*p).next;
                dealloc(p as *mut u8, Layout::new::<Node<T>>());
                p = next;
            }
        }
    }
}
// а вот это на плюсах так же зерокстно повторить не возможно
struct DListIter<'list, T> {
    node: NodePtr<T>,
    _p: PhantomData<&'list Node<T>>
}
impl<'list, T> DListIter<'list, T> {
    pub fn next(&mut self) -> Option<&T> {
        if self.node.is_null() { return None }
        unsafe {
            self.node = (*(self.node)).next;
            Some( &(*(self.node)).val )
        }
    }
    pub fn value_ref(&self) -> Option<&T> {
         if self.node.is_null() { return  None }
         unsafe { Some( &(*self.node).val) }
    }
}

как-то так, примерно так же как и на плюсах. Делать так списки, естественно, не нужно. Но даже так плюсы сильно сливают, а сишка вообще дно, т.к. уже похерит void* -ами типы, а RAII - отродясь не было. В плюсах невозможно эффективно огородить код с УБ-шными эффектами, нет unsafe совместно действуещего с системой типов. Этим - «_p: PhantomData<&’list Node>» - мы придали ссылочную семантику типу DListIter и компилятор будет отслеживать лайфтаймы так же как и с встроенными ссылками:

fn main() {
    let mut lst = DList::<i32>::default();
    lst.push_front(11);  lst.push_front(22);
    let mut it = lst.head_iter();
    it.next();
    // lst.push_front(5); // ошибка компиляции 
    dbg!( it.value_ref().unwrap() );
}

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

это плохо, для оптимизации может быть полезно

и прочие другие тем не менее отъели у с/с++ изрядный кусок. Хотя и не

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

питон обосновался там где надо быстро наскриптовать и/или заставить работать написанную на С++ библиотеку.

я бы не сказал что это «подвинули». скорее заняли те области которые были заняты башем и коболом.

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

А Андроид припоминаешь? :) Там правда сейчас ещё котлин какой-то… И я сказал бы весь ынтерпрайс, а не только банки.

питон обосновался там где надо быстро … заставить работать написанную на С++ библиотеку.

А ты не находишь несколько странным, что для задачи «быстро написать управляющую логику вокруг с/с++-библиотеки» индустрия массово (и главное стихийно, в отличие от Андроида) выбрала питон, а не сам с++?

Это по-моему, уже не просто звоночек. с++ оказался настолько неудобен для высокоуровневого программирования, скриптинга, прототипирования и склейки c++(!) кода, что вокруг высокопроизводительного ядра на с/с++ часто проще построить второй слой на другом языке!

Например?

fn main() {

    let mut lst = DList::<i32>::default();

    lst.push_front(11);  lst.push_front(22);

    let mut it = lst.head_iter();

    it.next();

    // lst.push_front(5); // ошибка компиляции 

    dbg!( it.value_ref().unwrap() );

}

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

Так это антипример получается. Список же потому и выбирают, что он позволяет делать вставки и удаления без инвалидации итераторов. И как же это исправить в расте, чтобы можно было использовать преимущества списка? Небось опять какие-то трёхэтажные маты заклинания получатся?

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

Список же потому и выбирают, что он позволяет делать вставки и удаления без инвалидации итераторов

Впервые слышу. Список выбирают, потому что вставка дешëвая.

Список же потому и выбирают, что он позволяет делать вставки и удаления без инвалидации итераторов

Впервые слышу. Список выбирают, потому что вставка дешëвая.

Ну, одно другому не противоречит. :) Дешёвая вставка и удаление это одно из основных свойств списка, а отсутствие инвалидации указателей/итераторов при этих операциях это другое свойство. Оба вытекают из его устройства.

В с++ это даже часть контракта std::list: вставка не инвалидирует существующие итераторы и ссылки, а удаление инвалидирует только для удаляемых элементов. Естественно, в си будет тоже самое при «классической» реализации.

Поэтому если можно дёшево вставить элемент, но ради этого запрещено менять список, пока существует хоть один итератор, то теряется существенная часть практических преимуществ списка.

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

Кстати. У меня первый смарт был без андроида. Ось от лыжи на c++ и на 256мб рамы она летала как самолет. А потом андроид2.3 на полгигах еле шевелящийся. Была бы версия c++17 с какими нибудь фичами безопасности на тот момент… Может быть андроид бы умер.

То есть или ынтерпрайз или майнкрафт с андроидом где имело место решение разработчика.

Кстати. У меня первый смарт был без андроида. Ось от лыжи на c++ и на 256мб рамы она летала как самолет. А потом андроид2.3 на полгигах еле шевелящийся. Была бы версия c++17 с какими нибудь фичами безопасности на тот момент… Может быть андроид бы умер.

Ха. Я даже успел портировать си/с++ программу на Симбиан, работала на смартфоне от Нокии, распознавала всякие коды с камеры (баркоды, pdf417, datamatrix…). Симбиан имел все шансы стать открытой мобильной ОС, но они не захотели открывать исходники вовремя. Производительность действительно была великолепная, распознавание шло в реальном времени, но api там был весьма извратный.

Мне даже интересно стало, как оно должно отработать, если элемент, на который указывает итератор, и последующий, будут удалены. Что он тогда итерировать должен? Или если последний элемент, на котором итератор, переставили в начало. Он заново весь список прогнать должен?

Что-то мне кажется, погорясились Вы с таким контрактом. Я бы не стал такое гарантировать. Единственный способ сделать нормальный итератор: откопировать объект (хотя бы ссылки) и уже по копии бежать.

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

Прочитай внимательно ещё раз моё сообщение, я подробно и достаточно точно расписал условия (единственное что инвалидирует итератор это удаление элемента на который он указывает, вставка вообще без ограничений). Это довольно базовые вещи, если ты получал профильное образование, должен был это тоже проходить. Список это не что-то особенное, что придумали в с++.

погорясились Вы с таким контрактом. Я бы не стал такое гарантировать

в любом букваре по с++ это написано, вот например https://ru.cppreference.com/cpp/container/list (второй абзац)

Понятно. Прочитал черезпо диагонали.

Получается, что это не контракт, а такое свойство. Всё равно не понимаю, какая в этом польза, если итератор может остановиться на середине из-за удаления конкретного элемента. А может не остановиться. Этим можно пользоваться только если удаления из середины в принципе запрещены, пусть и не явно.

Меня пугает подсяет ссылок в связном списке

Тебя пугают умные указатели? Надо свои фобии прорабатывать.

Ты прочитал сообщение, на которое отвечаешь?

Получается, что это не контракт, а такое свойство. Всё равно не понимаю, какая в этом польза, если итератор может остановиться на середине из-за удаления конкретного элемента. А может не остановиться. Этим можно пользоваться только если удаления из середины в принципе запрещены, пусть и не явно.

В с++ словом «контракт» иногда называют обещание, которое даёт разработчик класса, в данном случае контейнера. В случае std::list это гарантированное свойство интерфейса.

Удаление какого-то другого элемента не заставляет итератор «остановиться»: он остаётся валидным и просто идёт дальше. Недействительным становится только тот итератор, элемент которого удалили. Если после этого им пользоваться, будет UB.

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

Решить вопрос с UB при удалении текущего элемента в принципе можно, но потребует дополнительного механизма отслеживания валидности, что повлечёт за собой заметное усложнение и замедление кода.

И на safe Расте, уверен, тоже можно реализовать полноценный список, но это будет скорее всего ещё сложнее и тормознутей (хотя наверняка найдётся кто-то с ядерным реактором кому это понадобится). А в unsafe ты получишь всё тот же UB.

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

очень дешёвую модель итераторов

При этом безопасная версия в Расте - это просто счётчик ссылок, даже не атомарный. Прямо скажем, не дохрена высокая цена.

При этом безопасная версия в Расте - это просто счётчик ссылок, даже не атомарный. Прямо скажем, не дохрена высокая цена.

Не только счётчик ссылок. В том примере ещё weak, refcell, с рантайм-проверкой borrow, upgrade(), clone() и больший размер узла. По-отдельности это всё недорого, но есть цена и по времени исполнения и по памяти и по сложности кода.

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

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

Я ровно про это и написал.

В с++ словом «контракт» иногда называют обещание, которое даёт разработчик класса, в данном случае контейнера. В случае std::list это гарантированное свойство интерфейса.

В целом верно. Я имел в виду «контракт» в широком понимании: получение определённых гарантий при соблюдении определённых требований. Быстрая вставка (О(1) при вставке «по месту») - контракт, причина его создания. А вот валидация/инвалидация указателей итераторов - нет. Приятное свойство, но не более того.

Со вставкой ещё удобнее: можно добавлять элементы в любом месте списка, и все существующие итераторы остаются валидными.

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

Это не отменяет вопроса:

Зачем нужен итератор [для списка, в котором производятся удаления или перестановки в середине], если его корректная работа не гарантирована. Это ж надо следить, чтобы никакая падла из него ничего не удаляла.

Раст всего лишь указывает на это обстоятельство. По сути, раст предлагает контрактное программирование: ты соблюдаешь определённые требования, он даёт определённые гарантии.

Зачем нужен итератор [для списка, в котором производятся удаления или перестановки в середине], если его корректная работа не гарантирована. Это ж надо следить, чтобы никакая падла из него ничего не удаляла.

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

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

Вот тебе и цена гарантии: раст запрещает не только опасные операции, но заодно и совершенно безопасные.

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

Потому что для этого надо делать не обычный список, а накладывать на него дополнительные ограничения. Не полагаясь на «безопасность вполне очевидно следует из кода». Сложно ли это? Не знаю, скорее да, чем нет.

Вот тебе и цена гарантии: раст запрещает не только опасные операции, но заодно и совершенно безопасные.

Это ж очевидные вещи. Впрочем, я об этом писал: у Раста довольно тупенький компилятор* [в части борова], не надо ему приписывать. Станет ли он когда-нибудь умнее? Тем более не знаю.

• под словом «тупенький» я подразумевал «прямолинейный».

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

С чего это?

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

Потому что для этого надо делать не обычный список, а накладывать на него дополнительные ограничения. Не полагаясь на «безопасность вполне очевидно следует из кода». Сложно ли это? Не знаю, скорее да, чем нет.

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

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

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

С чего это?

Если я правильно понял @bbc69, в safe расте невозможно иметь обычный живой итератор и одновременно делать вставку в этот список.

Вот как в с++:

auto a = list.begin();
auto b = list.begin();

++a;
list.push_back(123); // OK
++b;                 // OK, старые итераторы валидны

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

Могу общие идеи накидать. Делается это не обёрткой, а перепроектированием класса. Поскольку элементы не удаляются, надо прописать, что время жизни элемента равно времени жизни самого списка, тогда к итератору не должно быть вопросов. Почти наверняка проще это написать через unsave. Можно ли без этого - не знаю.

Да, выглядеть (скорее всего) будет так себе.

В языке наверняка есть такая штука, как очередь (queue), за вдохновением туда.

Если я правильно понял @bbc69, в safe расте невозможно иметь обычный живой итератор и одновременно делать вставку в этот список.

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

Если я правильно понял

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

С unsafe для самописного списка точно должно быть можно. Без unsafe не знаю, но очень хотелось бы посмотреть на код, чтобы оценить, на сколько труднее. Может @unC0Rr поможет? Особенно для того списка который был приведён выше. Но можно и для другого списка, главное без unsafe.

А вот для стандартного растовского списка и стандартного итератора в safe режиме действительно нельзя. Хотя у них у обоих внутре unsafe! Я даже лично проверил, чтобы не полагаться на «непроверенные источники» и не «вытягивать из пальца».

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::from([1, 2, 3]);

    let mut a = list.iter();
    let mut b = list.iter();

    println!("a: {:?}", a.next());
    println!("b: {:?}", b.next());

    list.push_back(123); // <-- ошибка компиляции

    println!("a: {:?}", a.next());
    println!("b: {:?}", b.next());
}

error[E0502]: cannot borrow `list` as mutable because it is also borrowed as immutable
  --> sp.rs:12:5
   |
6  |     let mut a = list.iter();
   |                 ---- immutable borrow occurs here
...
12 |     list.push_back(123); // <-- ошибка компиляции
   |     ^^^^^^^^^^^^^^^^^^^ mutable borrow occurs here
13 |
14 |     println!("a: {:?}", a.next());
   |                         - immutable borrow later used here

error: aborting due to 1 previous error

For more information about this error, try `rustc --explain E0502`.

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

Я-то тут причём? Я об этом даже не знал, пока мне @bbc69 не рассказал. И это правда, я проверил.

На рабочий safe-код списка с умными указателями, который позволяет живые итераторы и вставку/удаление интересно было бы посмотреть, чтобы заценить сложность.

Вот что ты делаешь, чертяка. Пришлось с искусственным болваном пообщаться.

Первый вариант, как и предполагал, идет через копирование:

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::from([1, 2, 3]);

    let a: LinkedList<_> = list.iter().copied().collect();
    let b: LinkedList<_> = list.iter().copied().collect();

    list.push_back(123);

    for x in a {
        println!("a: {:?}", x);
    }

    list.push_back(456);

    for x in b {
        println!("b: {:?}", x);
    }
}

Вывод будет 1, 2, 3.

Существует так называемый appendList, который делает что-то похожее:

use appendlist::AppendList;

fn main() {
    let mut list: AppendList<i32> = (1..=3).collect();

    let mut a = list.iter();     // immutable borrow
    let mut b = list.iter();    // ещё один

    list.push(123);             // компилируется! push(&self, ...)

    println!("a: {:?}", a.next()); // Some(1)
    println!("b: {:?}", b.next()); // Some(1)
    println!("a: {:?}", a.next()); // Some(2)
    println!("b: {:?}", b.next()); // Some(2)
}

А если ещё и сами объекты менять надо, то:

use appendlist::AppendList;
use std::cell::Cell;

fn main() {
    let list: AppendList<Cell<i32>> = [1, 2, 3].into_iter().map(Cell::new).collect();

    let mut a = list.iter();      // итератор по ссылкам

    list.push(Cell::new(123));   // вставляем — ОК

    // Меняем существующее значение, пока итератор активен
    list[0].set(999);             // ОК, Cell — interior mutability

    println!("a: {:?}", a.next().unwrap().get()); // 999
    println!("a: {:?}", a.next().unwrap().get()); // 2

    list.push(Cell::new(456));   // снова вставляем

    println!("a: {:?}", a.next().unwrap().get()); // 3
}

appendlist обходит это через unsafe внутри, гарантируя инвариант «узлы не двигаются и не освобождаются» вручную.

Это не полностью соответствует задаче, но неплохой задел. Подозреваю, что можно докрутить решение.

Это не полностью соответствует задаче, но неплохой задел. Подозреваю, что можно докрутить решение.

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

У нас тут академический спор. Требуется создать контейнер с определенными свойствами. На «определенных классах задач» это может быть очень полезно.

Можно полностью как в с++ сделать, только будет ансейф итератор свой. Можно CursorMut заюзать. Вот найтли версия раста такое позволяет:

#![feature(linked_list_cursors)]

use std::collections::LinkedList;

fn main() {
    let mut list = LinkedList::from([1, 2, 3, 4, 5]);
    let mut cursor = list.cursor_front_mut();
    while cursor.current().is_some() {
        let value = *cursor.current().unwrap();
        if value == 2 {
            cursor.insert_after(20);
        }
        if value == 4 {
            cursor.remove_current();
        } else {
            cursor.move_next();
        }
    }
    println!("{list:?}");
}

вывод:

[1, 2, 20, 3, 5]

ДАже удалить можно. Если T: Send, можно курсор по потокам таскать.

• вставка рядом с курсором O(1)
• удаление текущего O(1)
• переход next/prev O(1)

Сойдет?

Вот тут неплохой обзор различных двусвязных списков с разными свойствами: https://docs.rs/rc-dlist-deque/latest/rc_dlist_deque/#survey-of-available-rust-doubly-linked-lists-compared-to-vecdeque

Боже, сколько всего всякого)

Осталось только понять зачем это всё нужно городить.

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

Нужна реальная задача,

Обработка буферов ввода / ввода любого блочного устройства. Для жысоноукладки это всё, конечно, не нужно.

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

Здесь список вообще не является узким местом. От него нужна в первую очередь семантика вставка/удаление по известной позиции за O(1). Реальная нагрузка всё равно лежит в непрерывных аренах. Поэтому несколько лишних разыменований/проверок в safe-реализации списка на общей производительности практически ничего не меняют.

И главное, все перечисленные свойства не требуют именно linked list. Их можно получить на arena/slab с индексами, и это бдет работать быстрее.

Для производительности.

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

все перечисленные свойства не требуют именно linked list. Их можно получить на arena/slab с индексами

Я не уверен, что ты понял смысл поста, на который отвечаешь.

Да, точно, твой пост на вопрос «зачем это нужно» формально отвечает.

Сойдет?

нет, к сожалению

CursorMut сам эксклюзивно заимствует весь список. Через него действительно всё можно делать, но второй такой CursorMut одновременно создать нельзя, и list.push_*() пока жив первый cursor тоже вызвать нельзя.

То есть твой пример как раз подтверждает ограничение. Но за попытку спасибо.

Вот тут неплохой обзор различных двусвязных списков

Я так понимаю, с исходным списком, с которого всё началось ничего не выйдет, как и со стандартным LinkedList. ОК.

Судя по обзору, по ссылке находятся разной степени извращения, начиная от размещения элементов в векторе (generational_token_list), заканчивая почти что классическим списком, но с разделением владения узлами (rc-dlist-deque).

Наверное идеал, чтобы сочетание всех свойств одновременно: классические узлы + владение контейнером + независимые стабильные итераторы + только safe Rust, похоже невозможен.

Но rc-dlist-deque пожалуй очень близок. Мне вот жптшечка набросала, всё работает

use rc_dlist_deque::dlist::{List1, Node1};

fn main() {
    let mut list = List1::<i32>::new();

    let n1 = Node1::pointer(1);
    let n2 = Node1::pointer(2);
    let n3 = Node1::pointer(3);
    let n4 = Node1::pointer(4);

    list.push_back(&n1);
    list.push_back(&n2);
    list.push_back(&n3);
    list.push_back(&n4);

    let mut a = list.iter();
    let mut b = list.iter();

    // Продвигаем a и b, пока оба живы.
    assert!(a.next().is_some());
    assert!(a.next().is_some());

    assert!(b.next().is_some());

    // Вставляем новый узел при двух живых итераторах.
    let n5 = Node1::pointer(5);
    list.push_back(&n5);

    // Оба старых итератора продолжают работать.
    assert!(a.next().is_some());
    assert!(b.next().is_some());

    // Удаляем n4 — узел, на который наши итераторы сейчас не обязаны
    // указывать.
    list.remove(&n4);

    // И снова оба итератора остаются usable.
    assert!(a.next().is_some());
    assert!(b.next().is_some());

    println!("OK");
}

Конечно интересная дискуссия получилась. Всем спасибо.

с исходным списком, с которого всё началось ничего не выйдет

Мне кажется, выйдет. Только у него не реализованы нужные методы, проще найти другую готовую реализацию.

Тогда берешь *mut T + unsafe и делаешь также как в с++.

use std::{collections::LinkedList, sync::Mutex, thread};

#[derive(Clone, Copy)]
struct Ptr(*mut LinkedList<i32>);

unsafe impl Send for Ptr {}

impl Ptr {
    unsafe fn push_back(self, x: i32) {
        unsafe {
            (*self.0).push_back(x);
        }
    }
}

fn main() {
    let mut list = LinkedList::new();
    let lock = Mutex::new(());
    let p = Ptr(&mut list);

    thread::scope(|s| {
        let p1 = p;
        let p2 = p;
        let l1 = &lock;
        let l2 = &lock;

        s.spawn(move || {
            for i in 0..1000 {
                let _g = l1.lock().unwrap();
                unsafe { p1.push_back(i) };
            }
        });

        s.spawn(move || {
            for i in 1000..2000 {
                let _g = l2.lock().unwrap();
                unsafe { p2.push_back(i) };
            }
        });
    });

    assert_eq!(list.len(), 2000);
}

Наверное идеал, чтобы сочетание всех свойств одновременно: классические узлы + владение контейнером + независимые стабильные итераторы + только safe Rust, похоже невозможен.

Мне кажется, ты не понимаешь концепцию контрактов. Это ситуация не идеальная, а очень даже ошибкогенерирующая. Идеал: под задачу выбирать контейнер. Под одну - одну, под другую - другую.

Что до ансейв. Как я и писал, у раста довольно тупенький компилятор. И именно это причина наличия unsave. Если бы он мог описывать более сложные контракты, ансейв ему был бы не нужен.

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

c unsafe никто не сомневается что можно, речь же именно про safe rust

Что до ансейв. Как я и писал, у раста довольно тупенький компилятор. И именно это причина наличия unsave. Если бы он мог описывать более сложные контракты, ансейв ему был бы не нужен.

Всегда будут ситуации, когда unsafe необходим, это неизбежно в реальном мире. Другое дело, что таких ситуаций может быть гораздо меньше в прикладных программах, если их спрятать в библиотеку. Даже тот вариант списка, который я привёл и который якобы «safe» всё равно косвенно использует unsafe на нижнем уровне. Он есть, например, внутри Rc, Cell, Vec, Box…

Список без unsafe полностью, на всех уровнях, невозможен, да наверное почти ничего не сделаешь без unsafe на каком-то уровне. Даже простейший hello world невозможен без unsafe.

Safe Rust это такая абстракция верхнего уровня над unsafe rust. Но понял я это только сейчас, за что всем участникам спасибо.

Даже простейший hello world невозможен без unsafe.

Не, ну уж не надо так сильно преувеличивать.