intrustive collections: add caveat about by-ref iteration
authorRalf Jung <post@ralfj.de>
Wed, 12 Oct 2022 11:37:06 +0000 (13:37 +0200)
committerRalf Jung <post@ralfj.de>
Wed, 12 Oct 2022 11:38:39 +0000 (13:38 +0200)
personal/_posts/2018-04-10-safe-intrusive-collections-with-pinning.md

index db706aefb07fab79d341e08795f92e28330d6409..0ffae029954225cbb383a9054919f62cdd757d4b 100644 (file)
@@ -459,7 +459,7 @@ Removing `Pin::deref` (or restricting it to types that implement `Unpin`) would
 I spelled out the details [in the RFC issue](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-372109981).
 So, if we want to declare that shared pinning is a typestate in its own right---which overall seems desirable---do we want it to be restricted like this due to an implementation detail of arbitrary self types?
 
-**Update:** @Diggsey [points out](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-379230538) that we can still have a `PinRefCell` with a method like `fn get_pin(self: Pin<PinRefCell<T>>) -> Pin<T>`, as long as the `PinRefCell` never gives out mutable references. So it turns out that combining interior mutability and pinning should work fine.  Later, @glaebhoerl suggested we can even [combine `RefCell` and `PinRefCell` into one type if we dynamically track the pinning state](https://internals.rust-lang.org/t/safe-intrusive-collections-with-pinning/7281/11?u=ralfjung).  **/Update**
+**Update:** @Diggsey [points out](https://github.com/rust-lang/rfcs/pull/2349#issuecomment-379230538) that we can still have a `PinRefCell` with a method like `fn get_pin(self: Pin<PinRefCell<T>>) -> Pin<T>`, as long as the `PinRefCell` never gives out mutable references. So it turns out that combining interior mutability and pinning should work fine.  Later, @glaebhoerl suggested we can even [combine `RefCell` and `PinRefCell` into one type if we dynamically track the pinning state](https://internals.rust-lang.org/t/safe-intrusive-collections-with-pinning/7281/11?u=ralfjung). **/Update**
 
 ## 4 Conclusion
 
@@ -472,4 +472,9 @@ The situation around shared pinning is still open, and it seems we need to have
 
 Anyway, as usual, please [let me know what you think](https://internals.rust-lang.org/t/safe-intrusive-collections-with-pinning/7281)!
 
+**Update:** Years later, I finally realized that there still is a major problem with intrusive collections -- it is basically impossible to have a by-reference iterator!
+With the collection not actually owning the memory the elements are stored in, it is basically impossible to guarantee that during the iteration, elements do not get removed from the collection, which would invalidate the reference.
+However, for many use-cases (like an intrusive queue) it is sufficient to just support by-value operations such as "enqueue" and "dequeue" over such a collection, and those can be given an entirely safe interface.
+If iteration is required, then more advanced [techniques to control sharing](https://plv.mpi-sws.org/rustbelt/ghostcell/) seem to be needed. **/Update**
+
 #### Footnotes