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 402 403 404 405 406 407
use std::{
borrow::Borrow,
fmt::{self, Debug, Display, Formatter},
hash::{Hash, Hasher},
marker::PhantomData,
mem::{self, MaybeUninit},
ops::Deref,
ptr,
};
/// Allows for aliasing typically non-aliasable types without undefined behavior or SB violations.
///
/// This type is very similar to [`ManuallyDrop`](std::mem::ManuallyDrop) in that the underlying
/// value will be leaked without manual intervention, but additionally this type allows aliasing
/// of the inner value through the [`copy`](crate::Alias::copy) method.
///
/// # Alias Families
///
/// When describing the safety contracts of this type, it is useful to have a notion of "all
/// aliases that refer to the same data." We'll call that collection of alises an "alias family."
/// If an alias `b` is created by copying an alias `a` via [`Alias::copy`](crate::Alias::copy),
/// then `b` is a member of the same alias family as `a`. However if the value being aliased
/// implements `Clone`, then a deep copy of the underlying data can be performed via
/// [`Alias::clone`](crate::Alias::clone). If instead `b` were created by cloning `a`, then `b`
/// would **not** be in the same alias family as `a`, rather it would be the sole member of its
/// own unique alias family.
///
/// # Safety
///
/// This type and its associated operations are sound because it wraps the aliased value in
/// [`MaybeUninit`](std::mem::MaybeUninit), which causes the compiler to no longer assume any
/// pointers contained within are unique or dereferenceable. Most of the APIs of this type are
/// `unsafe`, but notably `Alias<T>` has a [`Deref`](std::ops::Deref) implementation for `T` which
/// is guaranteed to be safe. The only reason this guarantee can be made is because `Alias<T>`
/// will only ever safely give out shared references to the inner `T`, and all operations which
/// require mutable access or ownership of the underlying value are unsafe. If you plan to use
/// this type, please carefully read the safety comments for its associated methods since the
/// unsafe contracts often ask the caller to assert facts about the program which cannot easily be
/// verified locally.
///
/// # Thread Safety
///
/// `Alias<T>` is `Send` if and only if `T: Send + Sync`, and similarly `Alias<T>` is `Sync` if and
/// only if `T: Send + Sync`. Clearly if `T: !Send`, then `Alias<T>` cannot be `Send`, however if
/// `Alias<T>` were `Send` when `T: Send + !Sync`, then one could construct an `Alias<Box<T>>`,
/// copy it, and send it to another thread, and obtain a shared reference to the inner `T`,
/// violating the fact that `T: !Sync`.
///
/// `T` must also be `Send` in order for `Alias<T>` to be `Sync` due to the following scenario:
/// ```compile_fail
/// # use flashmap::Alias;
/// use std::{marker::PhantomData, thread};
///
/// struct NotSend(PhantomData<*const ()>);
/// unsafe impl Sync for NotSend {}
///
/// let dont_send = NotSend(PhantomData);
/// let alias = Alias::new(dont_send);
/// let alias_ref: &'static Alias<NotSend> = Box::leak(Box::new(alias));
///
/// thread::spawn(move || {
/// let alias_copy = unsafe { Alias::copy(alias_ref) };
/// let dont_send = unsafe { Alias::into_owned(alias_copy) };
/// // Ownership of `dont_send` has been safely obtained in another thread.
/// });
/// ```
/// According to the safety contracts of `copy` and `into_owned`, this program is safe. However,
/// this program should fail to compile since we've transferred ownership of `dont_send` to
/// another thread. Hence, for `Alias<T>` to be `Sync`, `T` must be `Send`.
///
/// # Examples
///
/// You can alias mutable references through this type without undefined behavior:
/// ```
/// # use flashmap::Alias;
/// let mut x = 10i32;
///
/// // Store a mutable reference to `x` in an alias
/// let a: Alias<&mut i32> = Alias::new(&mut x);
/// // Make a copy to alias the underlying pointer
/// // Safety: the value being aliased (in this case the mutable reference to `x`) is
/// // not currently being modified.
/// let b: Alias<&mut i32> = unsafe { Alias::copy(&a) };
///
/// // Same value
/// assert_eq!(**a, **b);
/// // Same pointer
/// assert_eq!(*a as *const i32, *b as *const i32);
///
/// // Convert an alias back into an owned value
/// // Safety: no alias in the same alias family as b is accessed beyond this point
/// let x_mut: &mut i32 = unsafe { Alias::into_owned(b) };
///
/// *x_mut += 1;
/// assert_eq!(x, 11);
/// ```
///
/// Similarly, you can alias boxes and other pointer types to avoid making deep copies. However,
/// the aliased value will need to be manually dropped.
/// ```
/// # use flashmap::Alias;
/// let mut boks = Alias::new(Box::new(42i32));
/// // Safety: the value being aliased is not currently being modified
/// let another_boks = unsafe { Alias::copy(&boks) };
///
/// assert_eq!(**boks, **another_boks);
///
/// // Safety: no alias in the same alias family as boks is accessed beyond this point
/// unsafe { Alias::drop(&mut boks); }
/// ```
#[repr(transparent)]
pub struct Alias<T> {
value: MaybeUninit<T>,
_not_send_sync: PhantomData<*const ()>,
}
// See the Thread Safety section in the documentation of Alias
unsafe impl<T> Send for Alias<T> where T: Send + Sync {}
unsafe impl<T> Sync for Alias<T> where T: Send + Sync {}
impl<T> Alias<T> {
/// Takes ownership of the given value and returns an alias of that value. The alias must be
/// manually dropped after calling this function, else the inner value will be leaked.
///
/// Note that the alias returned is conceptually associated with a new, unique alias family
/// in which it is the only member.
///
/// # Examples
///
/// ```
/// # use flashmap::Alias;
/// let alias = Alias::new(5i32);
/// assert_eq!(*alias, 5);
/// // Since i32 is Copy there's no need to drop it
/// ```
#[inline]
pub const fn new(val: T) -> Self {
Self {
value: MaybeUninit::new(val),
_not_send_sync: PhantomData,
}
}
/// Performs a deep clone of the underlying value, and returns an alias of the cloned value.
///
/// Similar to [`new`](crate::Alias::new), the returned value is conceptually part of a new
/// alias family in which it is the only member.
///
/// # Examples
///
/// Cloning an aliased string:
/// ```
/// # use flashmap::Alias;
/// let mut a = Alias::new("foo".to_owned());
/// let mut b = Alias::clone(&a);
///
/// // Equivalent values
/// assert_eq!(a, b);
/// // Different objects in memory
/// assert_ne!(a.as_ptr(), b.as_ptr());
///
/// // Ensure we don't leak memory
/// unsafe {
/// Alias::drop(&mut a);
/// Alias::drop(&mut b);
/// }
/// ```
#[inline]
pub fn clone(other: &Self) -> Self
where
T: Clone,
{
Self::new(T::clone(&**other))
}
/// Create a copy of the given alias.
///
/// This function performs a shallow copy. So, for example, if you `copy` an
/// `Alias<Box<String>>`, then only the 8 bytes (or however many for your architecture)
/// constituting the pointer to the `String` will be copied, and the actual data in the string
/// will not be copied or read.
///
/// The returned alias is conceptually a member of the same alias family as the argument
/// provided.
///
/// # Safety
///
/// The caller must assert that the `T` being aliased is safe to read. An example of when
/// this is **not** safe is shown below:
///
/// ```no_run
/// # use flashmap::Alias;
/// use std::{sync::Mutex, thread};
///
/// // Mutexes allow for interior mutability, in other words you can modify the value
/// // within a mutex through an immutable reference to that mutex
/// let aliased_mutex = Alias::new(Mutex::new(0i32));
/// // Obtain an immutable reference to the aliased mutex
/// let x: &'static Alias<Mutex<_>> = Box::leak(Box::new(aliased_mutex));
///
/// thread::spawn(move || {
/// // Modify the value within the mutex in parallel with the execution of the
/// // spawning thread
/// *x.lock().unwrap() = 42;
/// });
///
/// // !!!!! UNDEFINED BEHAVIOR !!!!!
/// // Copying the alias does a shallow copy of the underlying mutex, which includes
/// // copying (and thus reading) the integer being modified in this example.
/// // This is a concurrent read+write data race.
/// let y = unsafe { Alias::copy(x) };
/// ```
///
/// The reason that copying `x` is unsound here is because the data it points to could be
/// concurrently modified by the spawned thread. `Alias` induces no indirection, and neither
/// does `Mutex`, so the reference stored in `x` points to the actual bytes of the integer
/// being modified, hence when we copy the alias into `y`, we read those bytes while they are
/// being modified, causing a data race.
///
/// # Examples
///
/// Aliasing a `String`:
/// ```
/// # use flashmap::Alias;
/// let mut a = Alias::new("foo".to_owned());
/// // Safety: the value `a` is aliasing is not being concurrently modified
/// let b = unsafe { Alias::copy(&a) };
///
/// // Equivalent values
/// assert_eq!(a, b);
/// // Same object in memory
/// assert_eq!(a.as_ptr(), b.as_ptr());
///
/// // Ensure we don't leak memory
/// unsafe {
/// // We only need to drop one of the aliases since they both alias the same
/// // location in memory
/// Alias::drop(&mut a);
/// }
/// ```
#[inline]
pub unsafe fn copy(other: &Self) -> Self {
Self {
value: unsafe { ptr::read(&other.value) },
_not_send_sync: PhantomData,
}
}
/// Converts an alias of a value into an owned value.
///
/// # Safety
///
/// The caller must assert that no alias within the same alias family as the argument is
/// accessed during, or at any point after this function is called. Note that implicitly
/// dropping an `Alias<T>` does **not** count as an access since the `Drop` implementation for
/// `Alias<T>` is a no-op and does not access the underlying data.
///
/// The following example shows an **incorrect** use of `into_owned`, resulting in undefined
/// behavior:
/// ```no_run
/// # use flashmap::Alias;
/// let a = Alias::new(Box::new(10i32));
/// // Safety: the data aliased by `a` is not currently being modified
/// let b = unsafe { Alias::copy(&a) };
///
/// // !!!!! UNDEFINED BEHAVIOR !!!!!
/// // `b` is in the same alias family as `a`, and `a` is accessed after this
/// // function call.
/// let boks = unsafe { Alias::into_owned(b) };
/// drop(boks);
///
/// // Alias guarantees that calling `deref` is always safe, so although the actual
/// // operation (use after free) which immediately causes UB occurs here, this is
/// // due to the violation of the unsafe contract on `into_owned` above.
/// assert_eq!(**a, 10);
/// ```
///
/// # Examples
///
/// ```
/// # use flashmap::Alias;
/// let a = Alias::new("foo".to_owned());
/// // Safety: the data aliased by `a` is not currently being modified
/// let b = unsafe { Alias::copy(&a) };
///
/// // Safety: `a` is the only other member of `b`'s alias family, and is not accessed
/// // after this point
/// let string = unsafe { Alias::into_owned(b) };
///
/// assert_eq!(string, "foo");
///
/// // Calling Drop::drop on an Alias<T> does not count as an access
/// drop(a);
/// ```
#[inline]
pub const unsafe fn into_owned(alias: Self) -> T {
unsafe { alias.value.assume_init() }
}
/// Drops the aliased value, potentially invalidating all other aliases to that value.
///
/// # Safety
///
/// This function has the same safety requirements as [`into_owned`](crate::Alias::into_owned).
///
/// The following example shows an **incorrect** use of `drop`, resulting in undefined
/// behavior:
/// ```no_run
/// # use flashmap::Alias;
/// let a = Alias::new(Box::new(10i32));
/// // Safety: the data aliased by `a` is not currently being modified
/// let mut b = unsafe { Alias::copy(&a) };
///
/// // !!!!! UNDEFINED BEHAVIOR !!!!!
/// // `b` is in the same alias family as `a`, and `a` is accessed after this
/// // function call.
/// unsafe { Alias::drop(&mut b); }
///
/// // Alias guarantees that calling `deref` is always safe, so although the actual
/// // operation (use after free) which immediately causes UB occurs here, this is
/// // due to the violation of the unsafe contract on `drop` above.
/// assert_eq!(**a, 10);
/// ```
///
/// # Examples
///
/// ```
/// # use flashmap::Alias;
/// let a = Alias::new("foo".to_owned());
/// // Safety: the data aliased by `a` is not currently being modified
/// let mut b = unsafe { Alias::copy(&a) };
///
/// // Safety: neither `a` or `b` are accessed after this point
/// unsafe { Alias::drop(&mut b) };
///
/// // Calling Drop::drop on an Alias<T> does not count as an access
/// drop(a);
/// ```
#[inline]
pub unsafe fn drop(alias: &mut Self) {
unsafe { alias.value.assume_init_drop() }
}
}
impl<T> Deref for Alias<T> {
type Target = T;
#[inline]
fn deref(&self) -> &Self::Target {
// Safety: the caller has asserted that this method will never be called after into_owned
// or drop by either never calling those methods or abiding to their safety contracts, so
// it is safe to give out a shared reference to the underlying value here.
unsafe { self.value.assume_init_ref() }
}
}
impl<T: Debug> Debug for Alias<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
Debug::fmt(&**self, f)
}
}
impl<T: Display> Display for Alias<T> {
fn fmt(&self, f: &mut Formatter<'_>) -> fmt::Result {
Display::fmt(&**self, f)
}
}
impl<T: PartialEq> PartialEq for Alias<T> {
#[inline]
fn eq(&self, other: &Self) -> bool {
PartialEq::eq(&**self, &**other)
}
}
impl<T: Eq> Eq for Alias<T> {}
impl<T: Hash> Hash for Alias<T> {
#[inline]
fn hash<H: Hasher>(&self, state: &mut H) {
(**self).hash(state)
}
}
// Workaround for orphan rules when implementing Borrow for Alias
#[repr(transparent)]
#[derive(PartialEq, Eq, Hash)]
pub(crate) struct BorrowHelper<T: ?Sized> {
pub(crate) value: T,
}
impl<T: ?Sized> BorrowHelper<T> {
#[inline]
pub fn new_ref(value: &T) -> &Self {
unsafe { mem::transmute(value) }
}
}
impl<T, U: ?Sized> Borrow<BorrowHelper<U>> for Alias<T>
where
T: Borrow<U>,
{
#[inline]
fn borrow(&self) -> &BorrowHelper<U> {
unsafe { mem::transmute(<T as Borrow<U>>::borrow(&**self)) }
}
}