1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 334 335 336 337 338 339 340 341 342 343 344 345 346 347 348 349 350 351 352 353 354 355 356 357 358 359 360 361 362 363 364 365 366 367 368 369 370 371 372 373 374 375 376 377 378 379 380 381 382 383 384 385 386 387 388 389 390 391 392 393 394 395 396 397 398 399 400 401
//! `Pin`-based stopgap for unboxed aliasable values in self-referential data structures.
//!
//! # Uniqueness
//!
//! For the sake of optimization, the Rust compiler likes to assume that all mutable references
//! (`&mut`) are completely unique. This uniqueness gives it some extremely important guarantees
//! that can be easily exploited for faster code, such as:
//! - All reads from an `&mut` location are guaranteed to be the same if the reference is not
//! written to in between.
//! - Writes to the location are guaranteed to stay there unless explicitly overwritten with the
//! same mutable reference.
//! - No one is able to see the data stored behind the mutable reference while it exists without
//! using that mutable reference.
//!
//! A simple example of where `&mut` uniqueness is useful is in this code:
//!
//! ```rust
//! fn foo(x: &mut i32) -> i32 {
//! *x = 400;
//! do_some_other_stuff();
//! *x
//! }
//! # fn do_some_other_stuff() {}
//! ```
//!
//! The compiler will optimize this function to always return the constant 400, instead of having
//! to actually load the value stored behind `x` every time. It was only able to do this because `x`
//! is a unique pointer; if it wasn't, it could be possible that `do_some_other_stuff` would mutate
//! it in between and always returning the constant would result in unexpected behaviour.
//!
//! # Self-referential types
//!
//! However, this assumption starts to run into problems when using self-referential types. What
//! if, instead of being a simple integer, `x` was a type that held a reference to itself? Although
//! it isn't immediately obvious, the uniqueness guarantee is actually violated here: the
//! self-reference held in `x` aliases with the `&mut` to `x`, meaning the mutable reference _is no
//! longer unique_! And this issue isn't just theoretical, it causes miscompilations in the wild.
//! For example this code, which was based off [an actual soundness issue in
//! the `owning-ref` crate](https://github.com/Kimundi/owning-ref-rs/issues/49):
//!
//! ```no_run
//! use std::cell::Cell;
//!
//! struct Helper {
//! reference: &'static Cell<u8>,
//! owner: Box<Cell<u8>>,
//! }
//! fn helper(x: Helper) -> u8 {
//! x.owner.set(10);
//! x.reference.set(20);
//! x.owner.get()
//! }
//!
//! let owner = Box::new(Cell::new(0));
//! let reference = unsafe { &*(&*owner as *const Cell<u8>) };
//! let x = Helper { reference, owner };
//! println!("{}", helper(x));
//! ```
//!
//! When run in release mode, this program prints out `10` instead of the expected value of `20`.
//! This is because inside `helper`, the optimizer sees that we have unique access to the
//! `Cell<u8>` (`Box`es, like `&mut`s, are seen as unique pointers), and so it assumes that any
//! writes to that location will never be overwritten. But because we violated the optimizer's
//! expectations, we ended up with a nonsensical result.
//!
//! So what's the solution to this? Well, as it stands, there isn't one - at least not one that's
//! both sound and doesn't sacrifice performance. It is possible to use a different kind of smart
//! pointer than `Box`, one that doesn't allow the compiler to assume its pointer is unique, and
//! that _would_ work for the above case with almost no performance impact - but in cases where the
//! self-referenced value is not boxed in the first place it's a much tougher choice to make.
//!
//! It is very likely Rust eventually will have a solution to this, it's a well known bug that
//! needs to be fixed. In terms of what this solution will look like, it will most likely take the
//! shape of a `Aliasable<T>` wrapper type that exists in libcore and gives the guarantee that any
//! `&mut` references to the value will _not_ be considered to be unique, so that one
//! `&mut Aliasable<T>` and either one `&mut T` or any number of `&T`s can coexist (but not two
//! `&mut T`s or two `&mut Aliasable<T>`s; the regular borrowing rules still apply). Unfortunately,
//! this type doesn't exist today and there aren't even any concrete proposals for it yet. So what
//! can we do in the meantime?
//!
//! # A Solution
//!
//! Although it isn't possible to create sound self-referential types, as it turns out it _is_
//! possible to create unsound self-referential types _that we know won't miscompile_. This is
//! because to ensure that async blocks (which generate self-referential types) do not miscompile
//! in today's Rust, a temporary loophole was added to the `&mut` uniqueness rule: it only applies
//! when the referenced type doesn't implement `Unpin`. Thus to create these self-referential types
//! we simply have to make sure that they are `!Unpin`, and everything will work as expected.
//!
//! However, doing this manually and upholding all the invariants that come with it is a pain, not
//! to mention the migration effort that will be required in future once Rust does support true
//! self-referential types. So that's where this crate comes in. It provides a type `Aliasable<T>`
//! which both abstracts the work of making the container type `!Unpin` and should be forward
//! compatible with the hypothetical libcore equivalent. As soon as `Aliasable<T>` _does_ get
//! added to the language itself, I will be able to publish a new version of this crate internally
//! based on it and yank all previous versions, which would then be unsound and obsolete.
//!
//! And that's it! Although this crate is tiny, it is really useful for defining any kind of
//! self-referential type because you no longer have to worry so much about whether you can cause
//! miscompilations.
//!
//! However, there is one important detail to be aware of. Remember how above I said that `Box`es
//! are also treated as always-unique pointers? This is true, and unfortunately they don't get the
//! same loophole that `&mut` does. This means you have to be very careful when working with boxed
//! `Aliasable<T>`s - make sure that any functions that take them by value always delegate to a
//! second function that takes them by unique or shared reference, so Rust doesn't assume your
//! pointer to it is unique.
//!
//! # Examples
//!
//! A boxed slice that also stores a subslice of itself:
//!
//! ```rust
//! use core::pin::Pin;
//! use core::ptr::NonNull;
//! use core::slice::SliceIndex;
//! use core::cell::UnsafeCell;
//!
//! use pin_project::pin_project;
//! use pin_utils::pin_mut;
//! use pinned_aliasable::Aliasable;
//!
//! #[pin_project]
//! pub struct OwningSlice<T: 'static> {
//! // In a real implementation you would avoid the `T: 'static` bound by using some kind of
//! // raw pointer here.
//! slice: Option<&'static mut [T]>,
//! #[pin]
//! data: Aliasable<UnsafeCell<Box<[T]>>>,
//! }
//! impl<T: 'static> From<Box<[T]>> for OwningSlice<T> {
//! fn from(data: Box<[T]>) -> Self {
//! Self {
//! slice: None,
//! data: Aliasable::new(UnsafeCell::new(data)),
//! }
//! }
//! }
//! impl<T> OwningSlice<T> {
//! pub fn slice(self: Pin<&mut Self>, range: impl SliceIndex<[T], Output = [T]>) {
//! let mut this = self.project();
//! let current_slice = this.slice.take().unwrap_or_else(|| {
//! unsafe { &mut **this.data.as_ref().get_extended().get() }
//! });
//! *this.slice = Some(&mut current_slice[range]);
//! }
//! pub fn get(self: Pin<&Self>) -> &[T] {
//! let this = self.project_ref();
//! this.slice.as_deref().unwrap_or_else(|| unsafe { &**this.data.get().get() })
//! }
//! pub fn get_mut(self: Pin<&mut Self>) -> &mut [T] {
//! let this = self.project();
//! let data = this.data.as_ref();
//! this.slice.as_deref_mut().unwrap_or_else(|| unsafe { &mut **data.get().get() })
//! }
//! }
//!
//! let slice = OwningSlice::from(vec![1, 2, 3, 4, 5].into_boxed_slice());
//! pin_mut!(slice);
//! assert_eq!(slice.as_ref().get(), &[1, 2, 3, 4, 5]);
//!
//! slice.as_mut().slice(1..);
//! assert_eq!(slice.as_ref().get(), &[2, 3, 4, 5]);
//!
//! slice.as_mut().slice(2..=3);
//! assert_eq!(slice.as_ref().get(), &[4, 5]);
//!
//! slice.as_mut().slice(0..0);
//! assert_eq!(slice.as_ref().get(), &[]);
//! ```
//!
//! A pair type:
//!
//! ```rust
//! use core::pin::Pin;
//! use core::cell::Cell;
//!
//! use pin_project::{pin_project, pinned_drop};
//! use pin_utils::pin_mut;
//! use pinned_aliasable::Aliasable;
//!
//! #[pin_project(PinnedDrop)]
//! pub struct Pair(#[pin] Aliasable<PairInner>);
//!
//! struct PairInner {
//! value: u64,
//! other: Cell<Option<&'static PairInner>>,
//! }
//!
//! #[pinned_drop]
//! impl PinnedDrop for Pair {
//! fn drop(self: Pin<&mut Self>) {
//! if let Some(other) = self.project().0.as_ref().get().other.get() {
//! other.other.set(None);
//! }
//! }
//! }
//!
//! impl Pair {
//! pub fn new(value: u64) -> Self {
//! Self(Aliasable::new(PairInner {
//! value,
//! other: Cell::new(None),
//! }))
//! }
//! pub fn get(self: Pin<&Self>) -> u64 {
//! self.project_ref().0.get().other.get().unwrap().value
//! }
//! }
//!
//! pub fn link_up(left: Pin<&Pair>, right: Pin<&Pair>) {
//! let left = unsafe { left.project_ref().0.get_extended() };
//! let right = unsafe { right.project_ref().0.get_extended() };
//! left.other.set(Some(right));
//! right.other.set(Some(left));
//! }
//!
//! fn main() {
//! let pair_1 = Pair::new(10);
//! let pair_2 = Pair::new(20);
//! pin_mut!(pair_1);
//! pin_mut!(pair_2);
//!
//! link_up(pair_1.as_ref(), pair_2.as_ref());
//!
//! assert_eq!(pair_1.as_ref().get(), 20);
//! assert_eq!(pair_2.as_ref().get(), 10);
//! }
//! ```
#![no_std]
#![warn(
clippy::pedantic,
rust_2018_idioms,
missing_docs,
unused_qualifications,
missing_debug_implementations,
explicit_outlives_requirements,
unused_lifetimes,
unsafe_op_in_unsafe_fn
)]
#![allow(clippy::items_after_statements)]
use core::fmt::{self, Debug, Formatter};
use core::marker::PhantomPinned;
use core::pin::Pin;
/// An unboxed aliasable value.
#[derive(Default)]
pub struct Aliasable<T> {
val: T,
_pinned: PhantomPinned,
}
impl<T> Aliasable<T> {
/// Create a new `Aliasable` that stores `val`.
#[must_use]
#[inline]
pub fn new(val: T) -> Self {
Self {
val,
_pinned: PhantomPinned,
}
}
/// Get a shared reference to the value inside the `Aliasable`.
///
/// This method takes [`Pin`]`<&Self>` instead of `&self` to enforce that all parent containers
/// are `!`[`Unpin`], and thus won't be annotated with `noalias`.
///
/// This crate intentionally does not provide a method to get an `&mut T`, because the value
/// may be shared. To obtain an `&mut T` you should use an interior mutable container such as a
/// mutex or [`UnsafeCell`](core::cell::UnsafeCell).
#[must_use]
#[inline]
pub fn get(self: Pin<&Self>) -> &T {
&self.get_ref().val
}
/// Get a shared reference to the value inside the `Aliasable` with an extended lifetime.
///
/// # Safety
///
/// The reference must not be held for longer than the `Aliasable` exists.
#[must_use]
#[inline]
pub unsafe fn get_extended<'a>(self: Pin<&Self>) -> &'a T {
unsafe { &*(self.get() as *const T) }
}
/// Consume the `Aliasable`, returning its inner value.
///
/// If [`get`] has already been called and the type is now pinned, obtaining the owned
/// `Aliasable<T>` required to call this function requires breaking the pinning guarantee (as
/// the `Aliasable<T>` is moved). However, this is sound as long as the `Aliasable<T>` isn't
/// actually aliased at that point in time.
///
/// [`get`]: Self::get
#[must_use]
pub fn into_inner(self) -> T {
self.val
}
}
impl<T> Debug for Aliasable<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
f.pad("Aliasable")
}
}
#[cfg(test)]
mod tests {
extern crate alloc;
use alloc::boxed::Box;
use core::cell::{Cell, UnsafeCell};
use core::ops::DerefMut;
use core::pin::Pin;
use pin_project::pin_project;
use super::Aliasable;
#[test]
fn miri_is_happy() {
#[pin_project]
struct SelfRef {
#[pin]
value: Aliasable<UnsafeCell<i32>>,
reference: Option<&'static mut i32>,
}
let self_ref = SelfRef {
value: Aliasable::new(UnsafeCell::new(1)),
reference: None,
};
pin_utils::pin_mut!(self_ref);
let projected = self_ref.as_mut().project();
*projected.reference = Some(unsafe { &mut *projected.value.as_ref().get_extended().get() });
fn helper(self_ref: Pin<&mut SelfRef>) {
let projected = self_ref.project();
{
let reference = projected.reference.take().unwrap();
*reference = 2;
}
assert_eq!(unsafe { *projected.value.as_ref().get().get() }, 2);
}
helper(self_ref);
}
#[test]
fn self_ref() {
#[pin_project]
struct SelfRef {
reference: Option<&'static Cell<i32>>,
#[pin]
value: Aliasable<Cell<i32>>,
}
let mut self_ref = Box::pin(SelfRef {
value: Aliasable::new(Cell::new(0)),
reference: None,
});
let projected = self_ref.as_mut().project();
*projected.reference = Some(unsafe { projected.value.as_ref().get_extended() });
#[inline(never)]
fn helper(mut self_ref: Pin<impl DerefMut<Target = SelfRef>>) -> i32 {
let projected = self_ref.as_mut().project();
projected.value.as_ref().get().set(10);
projected.reference.unwrap().set(20);
projected.value.as_ref().get().get()
}
assert_eq!(helper(self_ref.as_mut()), 20);
assert_eq!(helper(self_ref), 20);
}
#[test]
fn external_ref() {
let mut value = Box::pin(Aliasable::new(Cell::new(0)));
let reference = unsafe { value.as_ref().get_extended() };
#[inline(never)]
#[allow(clippy::needless_pass_by_value)]
fn helper(
value: Pin<impl DerefMut<Target = Aliasable<Cell<i32>>>>,
reference: &Cell<i32>,
) -> i32 {
value.as_ref().get().set(10);
reference.set(20);
value.as_ref().get().get()
}
assert_eq!(helper(value.as_mut(), reference), 20);
// This currently miscompiles in release mode because `Box`es are never given `noalias`.
// See the last paragraph of the crate documentation.
//assert_eq!(helper(value, reference), 20);
}
}