[Pitch] Box

Evolution Pitches
22

I can imagine three kinds of reasons one would want to use a Box:

  1. To implement a recursive tree-like data structure.
  2. To prevent structs from taking too much space on the stack.
  3. To store pointers to a heap allocation while being able to move the Box itself, in order to implement a self-referential data structure.

The first case is (or should be) already served by indirect enum cases. Arguably, the second case is better served by indirect stored properties (and variables), which would allow for copy-on-write optimization (at least for copyable types), and would allow the compiler to merge multiple indirect stored properties into a single heap allocation.

The third case is impossible to do in current Swift, because it's impossible to get a pointer without binding the lifetime of that pointer to some (borrowing or mutating) access of the value, unless the pointer was manually allocated.

More subtly, the third case requires weaker aliasing rules than the first two cases. With the first two cases, presumably, we'd like to guarantee that exclusive access to the Box (or noncopyable indirect property) implies exclusive access to the heap allocation. That allows for better optimizations, but it also breaks the "stable address" semantics required for the third case, because any pointer to the heap allocation will be invalidated by mutating or moving the Box.

The Box type in Rust has the stronger aliasing rules which accommodate the first and second cases, but preclude the third case by breaking "stable address" semantics. That's unfortunate, because people who want the third case have to manually use raw pointers instead. Or they could just ignore the issue and have their code exhibit subtle undefined behavior, which is easy because the aliasing rules aren't well-documented. Some parts of the ecosystem have ended up doing that in practice, such as the owning_ref library formerly used in the Rust compiler. Fixing the problem (without splitting Box into two different types) would likely require some kind of compromise.[1]

Thoughts on self-referential data structures

With Rust's ownership system, it's notoriously difficult to implement self-referential data structures without either failing the borrow checker or breaking Rust's aliasing rules.[2] Unsafely-implemented self-referential data structures are widely used in async Rust, and the end result is that many of those data structures, including the stackless coroutines generated by the Rust compiler, exhibit undefined behavior under the normal aliasing rules.

Currently, the Rust compiler (and MIRI, a tool to catch undefined behavior at runtime) just "turns off" the normal aliasing rules for what it thinks are self-referential data structures.[3] There are proposals to introduce an official way to opt out of the normal aliasing rules, such as an UnsafePinned or UnsafeAliasedCell marker type.[4]

Given that unsafely-implemented self-referential data structures have caused so many problems for Rust, I think it's a bad idea to repeat their mistake by encouraging them in Swift. Currently, Swift does a good job at discouraging people from breaking the aliasing rules by only exposing pointers through closure-based APIs like withUnsafePointer. In the future, we could consider extending the ownership system to accommodate self-referential data structures in a safe way. I'm not sure exactly what that could look like, but we could consider using some of the ideas in region-based isolation, which already allows the compiler to reason about (a different kind of) aliasing.

  1. Some relevant discussion of the issue: What are the uniqueness guarantees of Box and Vec? · Issue #326 · rust-lang/unsafe-code-guidelines · GitHub, https://github.com/Kimundi/owning-ref-rs/issues/49 ↩︎

  2. More specifically, the aliasing rules of Stacked Borrows and/or Tree Borrows, the most prominent proposed formal semantics for Rust. ↩︎

  3. Specifically, it looks at which types opt out of the Unpin trait as a heuristic. ↩︎

  4. Some relevant discussion: 3467-unsafe-pinned - The Rust RFC Book, Tracking Issue for RFC 3467: UnsafePinned · Issue #125735 · rust-lang/rust · GitHub, intrusive.md · GitHub ↩︎

3 Likes