From: Ralf Jung Date: Wed, 12 Oct 2022 11:37:06 +0000 (+0200) Subject: intrustive collections: add caveat about by-ref iteration X-Git-Url: https://git.ralfj.de/web.git/commitdiff_plain/5368e11cf948e51c60d7936df73b86696b1a8911 intrustive collections: add caveat about by-ref iteration --- diff --git a/personal/_posts/2018-04-10-safe-intrusive-collections-with-pinning.md b/personal/_posts/2018-04-10-safe-intrusive-collections-with-pinning.md index db706ae..0ffae02 100644 --- a/personal/_posts/2018-04-10-safe-intrusive-collections-with-pinning.md +++ b/personal/_posts/2018-04-10-safe-intrusive-collections-with-pinning.md @@ -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>) -> Pin`, 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>) -> Pin`, 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