Mutable Iterator over Nodes of Singly Linked List with Just Box

[Self]

From the code I am able to create 2 mutable "pointers" to the same node. This seems to violate rust mem safety principles. Any idea on how we can iterate mutably over the nodes of the list using Box and without violating Rust mem safety rules. I do not want to use cell/rc things here. Just Box alone. This post seemed relevant but it uses rc/cell stuff as the final solution.

[steffahn]

As the other thread discusses in detail already, and your code demonstrates, too, it can’t ever soundly be an Iterator of &'a mut Box<ListNode<T>> or &'a mut ListNode<T>.

This means, we need to provide some other API.

TL;DR of the below thoughts: if you really want to use “just Box”, no shared mutability (“cell”) or shared-ownership (“rc”) things, and iterating over the items instead of the nodes isn’t an option, then you can’t do an Iterator, but you could consider alternative traits such as this one.

---

The general options I can come up with are the following 3:

1. the iterator offers no mutable access to whole nodes, but only to the elements
   • this way, all the references are offering truly unique access to everything accessible through them
2. the iterator offers mutable access to the whole node, but doesn’t use &mut _-references.
   • Typical shared-mutability solutions do include usage of Rc+RefCell; other shared-mutability primitives seem not out of the question either
3. the access to &'a mut ListNode<T> items is not provided with an ordinary Iterator
   • “lending iterators” (also sometimes “streaming iterators”) are still a WIP in Rust, as a fully general trait quickly reaches existing limitations of the compiler’s reasoning abilities about GATs (generic associated types), for this use case of &mut …-types items, a trait such as streaming_iterator::StreamingIteratorMut seem appropiate though
   • the simplest approach – which might be sufficient for many use-cases – to do this sort of thing would be to use no trait at all and just provide a for_each-method.
   • the common theme of these approaches is that it it’s possible to look at more than one of the items at the same time

Ultimately, you will need to check what use case you’re trying to support. Each approach has some downsides. If you just want mutable access to the items anyways, then approach 1. is sufficient.

If you do want to do other things to the nodes, that could either mean you want to be able to change the structure of the list during iteration, and/or you want to be able to start some form of “sub-iterations” inspecting, perhaps even modifying, subsequent elements from a node you got from the iterator.

Either way, you should be able to identify your access pattern – do you ever want to process the iterator items out-of-order? If not, the lending/streaming-iterator approach might work well.

If you do want out-of-order access, then shared mutability it probably a must. Still, which primitives to involve here is an interesting follow-up question.

• If your goal is to be able to change the list structure, then you quickly will be forced to apply shared ownership (Rc or Arc), because this means that one node can cause subsequent nodes to be removed from the list entirely, so combined with out-of-order processing abilities, the iterator elements must have some degree of ownership of the items.
• If your goal isn’t to change the list structure itself, then you could still work with Box, while only keeping the list elements in a shared-mutability wrapper. The iterator then becomes comparable to an “immutable” iterator over a collection of shared-mutable cells.
• Structural modifications to the list that only involve adding nodes, but not removing them is arguably possible to make sound even without shared ownership; however, this nuance isn’t easily understood by the rust compiler at all; though comparable reasoning can generally be used to design safe wrappers around unsafe implementations^[1] – as a point of comparison: arguing with safety from append-only capabilities is for instance something that APIs in crates such as elsa allow.

---

1. under the hood, one probably need involve some use of UnsafeCell, and the iterator can return a wrapper around &'a ListNode<T> with limited API that allows adding elements to the list, but not removing them. Ironing out the details likely would involve many API design decisions that could be made either way. I.e. choose-your-own-flavor of what’s accessible in a shared-mutable manner and what’s unique-access. Questions such as “are dynamic checks necessary” or “is this thread-safe” would have different answers for different flavors of such API ↩︎