1// This file is part of ICU4X. For terms of use, please see the file
2// called LICENSE at the top level of the ICU4X source tree
3// (online at: https://github.com/unicode-org/icu4x/blob/main/LICENSE ).
4
5//! Types for optional pointers with niche optimization.
6//!
7//! The main type is [`CartableOptionPointer`], which is like `Option<Rc>` but
8//! with a niche so that the resulting `Yoke` has a niche. The following four
9//! types can be stored in the `CartableOptionPointer`:
10//!
11//! 1. `&T`
12//! 2. `Box<T>`
13//! 3. `Rc<T>`
14//! 4. `Arc<T>`
15//!
16//! These four types implement the sealed unsafe trait [`CartablePointerLike`].
17//! In addition, all except `Box<T>` impl [`CloneableCartablePointerLike`],
18//! which allows [`CartableOptionPointer`] to implement `Clone`.
19
20use crate::CloneableCart;
21#[cfg(feature = "alloc")]
22use alloc::boxed::Box;
23#[cfg(feature = "alloc")]
24use alloc::rc::Rc;
25#[cfg(feature = "alloc")]
26use alloc::sync::Arc;
27#[cfg(test)]
28use core::cell::Cell;
29use core::marker::PhantomData;
30use core::ptr::NonNull;
31use stable_deref_trait::StableDeref;
32
33// Safety note: this method MUST return the same value for the same T, even if i.e. the method gets
34// instantiated in different crates. This can be untrue in surprising ways! For example, just
35// returning a const-ref-to-const would not guarantee that.
36// The current implementation always returns the same address for any T, see
37// [the reference](https://doc.rust-lang.org/reference/items/static-items.html#statics--generics):
38// there is exactly one `SENTINEL` item for any T.
39#[inline]
40fn sentinel_for<T>() -> NonNull<T> {
41 static SENTINEL: &u8 = &0x1a; // SUB
42
43 // Safety: SENTINEL is indeed not a null pointer, even after the casts.
44 unsafe { NonNull::new_unchecked(ptr:SENTINEL as *const u8 as *mut T) }
45}
46
47#[cfg(test)]
48thread_local! {
49 static DROP_INVOCATIONS: Cell<usize> = const { Cell::new(0) };
50}
51
52mod private {
53 pub trait Sealed {}
54}
55
56use private::Sealed;
57
58/// An object fully representable by a non-null pointer.
59///
60/// # Safety
61///
62/// Implementer safety:
63///
64/// 1. `into_raw` transfers ownership of the values referenced by StableDeref to the caller,
65/// if there is ownership to transfer
66/// 2. `drop_raw` returns ownership back to the impl, if there is ownership to transfer
67///
68/// Note: if `into_raw` returns the sentinel pointer, memory leaks may occur, but this will not
69/// lead to undefined behaviour.
70///
71/// Note: the pointer `NonNull<Self::Raw>` may or may not be aligned and it should never
72/// be dereferenced. Rust allows unaligned pointers; see [`std::ptr::read_unaligned`].
73pub unsafe trait CartablePointerLike: StableDeref + Sealed {
74 /// The raw type used for [`Self::into_raw`] and [`Self::drop_raw`].
75 #[doc(hidden)]
76 type Raw;
77
78 /// Converts this pointer-like into a pointer.
79 #[doc(hidden)]
80 fn into_raw(self) -> NonNull<Self::Raw>;
81
82 /// Drops any memory associated with this pointer-like.
83 ///
84 /// # Safety
85 ///
86 /// Caller safety:
87 ///
88 /// 1. The pointer MUST have been returned by this impl's `into_raw`.
89 /// 2. The pointer MUST NOT be dangling.
90 #[doc(hidden)]
91 unsafe fn drop_raw(pointer: NonNull<Self::Raw>);
92}
93
94/// An object that implements [`CartablePointerLike`] that also
95/// supports cloning without changing the address of referenced data.
96///
97/// # Safety
98///
99/// Implementer safety:
100///
101/// 1. `addref_raw` must create a new owner such that an additional call to
102/// `drop_raw` does not create a dangling pointer
103/// 2. `addref_raw` must not change the address of any referenced data.
104pub unsafe trait CloneableCartablePointerLike: CartablePointerLike {
105 /// Clones this pointer-like.
106 ///
107 /// # Safety
108 ///
109 /// Caller safety:
110 ///
111 /// 1. The pointer MUST have been returned by this impl's `into_raw`.
112 /// 2. The pointer MUST NOT be dangling.
113 #[doc(hidden)]
114 unsafe fn addref_raw(pointer: NonNull<Self::Raw>);
115}
116
117impl<'a, T> Sealed for &'a T {}
118
119// Safety:
120// 1. There is no ownership to transfer
121// 2. There is no ownership to transfer
122unsafe impl<'a, T> CartablePointerLike for &'a T {
123 type Raw = T;
124
125 #[inline]
126 fn into_raw(self) -> NonNull<T> {
127 self.into()
128 }
129 #[inline]
130 unsafe fn drop_raw(_pointer: NonNull<T>) {
131 // No-op: references are borrowed from elsewhere
132 }
133}
134
135// Safety:
136// 1. There is no ownership
137// 2. The impl is a no-op so no addresses are changed.
138unsafe impl<'a, T> CloneableCartablePointerLike for &'a T {
139 #[inline]
140 unsafe fn addref_raw(_pointer: NonNull<T>) {
141 // No-op: references are borrowed from elsewhere
142 }
143}
144
145#[cfg(feature = "alloc")]
146impl<T> Sealed for Box<T> {}
147
148#[cfg(feature = "alloc")]
149// Safety:
150// 1. `Box::into_raw` says: "After calling this function, the caller is responsible for the
151// memory previously managed by the Box."
152// 2. `Box::from_raw` says: "After calling this function, the raw pointer is owned by the
153// resulting Box."
154unsafe impl<T> CartablePointerLike for Box<T> {
155 type Raw = T;
156
157 #[inline]
158 fn into_raw(self) -> NonNull<T> {
159 // Safety: `Box::into_raw` says: "The pointer will be properly aligned and non-null."
160 unsafe { NonNull::new_unchecked(ptr:Box::into_raw(self)) }
161 }
162 #[inline]
163 unsafe fn drop_raw(pointer: NonNull<T>) {
164 // Safety: per the method's precondition, `pointer` is dereferenceable and was returned by
165 // `Self::into_raw`, i.e. by `Box::into_raw`. In this circumstances, calling
166 // `Box::from_raw` is safe.
167 let _box: Box = unsafe { Box::from_raw(pointer.as_ptr()) };
168
169 // Boxes are always dropped
170 #[cfg(test)]
171 DROP_INVOCATIONS.with(|x| x.set(x.get() + 1))
172 }
173}
174
175#[cfg(feature = "alloc")]
176impl<T> Sealed for Rc<T> {}
177
178#[cfg(feature = "alloc")]
179// Safety:
180// 1. `Rc::into_raw` says: "Consumes the Rc, returning the wrapped pointer. To avoid a memory
181// leak the pointer must be converted back to an Rc using Rc::from_raw."
182// 2. See 1.
183unsafe impl<T> CartablePointerLike for Rc<T> {
184 type Raw = T;
185
186 #[inline]
187 fn into_raw(self) -> NonNull<T> {
188 // Safety: Rcs must contain data (and not be null)
189 unsafe { NonNull::new_unchecked(ptr:Rc::into_raw(self) as *mut T) }
190 }
191
192 #[inline]
193 unsafe fn drop_raw(pointer: NonNull<T>) {
194 // Safety: per the method's precondition, `pointer` is dereferenceable and was returned by
195 // `Self::into_raw`, i.e. by `Rc::into_raw`. In this circumstances, calling
196 // `Rc::from_raw` is safe.
197 let _rc: Rc = unsafe { Rc::from_raw(pointer.as_ptr()) };
198
199 // Rc is dropped if refcount is 1
200 #[cfg(test)]
201 if Rc::strong_count(&_rc) == 1 {
202 DROP_INVOCATIONS.with(|x| x.set(x.get() + 1))
203 }
204 }
205}
206
207#[cfg(feature = "alloc")]
208// Safety:
209// 1. The impl increases the refcount such that `Drop` will decrease it.
210// 2. The impl increases refcount without changing the address of data.
211unsafe impl<T> CloneableCartablePointerLike for Rc<T> {
212 #[inline]
213 unsafe fn addref_raw(pointer: NonNull<T>) {
214 // Safety: The caller safety of this function says that:
215 // 1. The pointer was obtained through Rc::into_raw
216 // 2. The associated Rc instance is valid
217 // Further, this impl is not defined for anything but the global allocator.
218 unsafe {
219 Rc::increment_strong_count(pointer.as_ptr());
220 }
221 }
222}
223
224#[cfg(feature = "alloc")]
225impl<T> Sealed for Arc<T> {}
226
227#[cfg(feature = "alloc")]
228// Safety:
229// 1. `Rc::into_raw` says: "Consumes the Arc, returning the wrapped pointer. To avoid a memory
230// leak the pointer must be converted back to an Arc using Arc::from_raw."
231// 2. See 1.
232unsafe impl<T> CartablePointerLike for Arc<T> {
233 type Raw = T;
234
235 #[inline]
236 fn into_raw(self) -> NonNull<T> {
237 // Safety: Arcs must contain data (and not be null)
238 unsafe { NonNull::new_unchecked(ptr:Arc::into_raw(self) as *mut T) }
239 }
240 #[inline]
241 unsafe fn drop_raw(pointer: NonNull<T>) {
242 // Safety: per the method's precondition, `pointer` is dereferenceable and was returned by
243 // `Self::into_raw`, i.e. by `Rc::into_raw`. In this circumstances, calling
244 // `Rc::from_raw` is safe.
245 let _arc: Arc = unsafe { Arc::from_raw(pointer.as_ptr()) };
246
247 // Arc is dropped if refcount is 1
248 #[cfg(test)]
249 if Arc::strong_count(&_arc) == 1 {
250 DROP_INVOCATIONS.with(|x| x.set(x.get() + 1))
251 }
252 }
253}
254
255#[cfg(feature = "alloc")]
256// Safety:
257// 1. The impl increases the refcount such that `Drop` will decrease it.
258// 2. The impl increases refcount without changing the address of data.
259unsafe impl<T> CloneableCartablePointerLike for Arc<T> {
260 #[inline]
261 unsafe fn addref_raw(pointer: NonNull<T>) {
262 // Safety: The caller safety of this function says that:
263 // 1. The pointer was obtained through Arc::into_raw
264 // 2. The associated Arc instance is valid
265 // Further, this impl is not defined for anything but the global allocator.
266 unsafe {
267 Arc::increment_strong_count(pointer.as_ptr());
268 }
269 }
270}
271
272/// A type with similar semantics as `Option<C<T>>` but with a niche.
273///
274/// This type cannot be publicly constructed. To use this in a `Yoke`, see
275/// [`Yoke::convert_cart_into_option_pointer`].
276///
277/// [`Yoke::convert_cart_into_option_pointer`]: crate::Yoke::convert_cart_into_option_pointer
278#[derive(Debug)]
279pub struct CartableOptionPointer<C>
280where
281 C: CartablePointerLike,
282{
283 /// The inner pointer.
284 ///
285 /// # Invariants
286 ///
287 /// 1. Must be either `SENTINEL_PTR` or created from `CartablePointerLike::into_raw`
288 /// 2. If non-sentinel, must _always_ be for a valid SelectedRc
289 inner: NonNull<C::Raw>,
290 _cartable: PhantomData<C>,
291}
292
293impl<C> CartableOptionPointer<C>
294where
295 C: CartablePointerLike,
296{
297 /// Creates a new instance corresponding to a `None` value.
298 #[inline]
299 pub(crate) fn none() -> Self {
300 Self {
301 inner: sentinel_for::<C::Raw>(),
302 _cartable: PhantomData,
303 }
304 }
305
306 /// Creates a new instance corresponding to a `Some` value.
307 #[inline]
308 pub(crate) fn from_cartable(cartable: C) -> Self {
309 let inner = cartable.into_raw();
310 debug_assert_ne!(inner, sentinel_for::<C::Raw>());
311 Self {
312 inner,
313 _cartable: PhantomData,
314 }
315 }
316
317 /// Returns whether this instance is `None`. From the return value:
318 ///
319 /// - If `true`, the instance is `None`
320 /// - If `false`, the instance is a valid `SelectedRc`
321 #[inline]
322 pub fn is_none(&self) -> bool {
323 self.inner == sentinel_for::<C::Raw>()
324 }
325}
326
327impl<C> Drop for CartableOptionPointer<C>
328where
329 C: CartablePointerLike,
330{
331 #[inline]
332 fn drop(&mut self) {
333 let ptr: NonNull<::Raw> = self.inner;
334 if ptr != sentinel_for::<C::Raw>() {
335 // By the invariants, `ptr` is a valid raw value since it's
336 // either that or sentinel, and we just checked for sentinel.
337 // We will replace it with the sentinel and then drop `ptr`.
338 self.inner = sentinel_for::<C::Raw>();
339 // Safety: by the invariants, `ptr` is a valid raw value.
340 unsafe { C::drop_raw(pointer:ptr) }
341 }
342 }
343}
344
345impl<C> Clone for CartableOptionPointer<C>
346where
347 C: CloneableCartablePointerLike,
348{
349 #[inline]
350 fn clone(&self) -> Self {
351 let ptr: NonNull<::Raw> = self.inner;
352 if ptr != sentinel_for::<C::Raw>() {
353 // By the invariants, `ptr` is a valid raw value since it's
354 // either that or sentinel, and we just checked for sentinel.
355 // Safety: by the invariants, `ptr` is a valid raw value.
356 unsafe { C::addref_raw(pointer:ptr) }
357 }
358 Self {
359 inner: self.inner,
360 _cartable: PhantomData,
361 }
362 }
363}
364
365// Safety: logically an Option<C>. Has same bounds as Option<C>.
366// The `StableDeref` parts of `C` continue to be `StableDeref`.
367unsafe impl<C> CloneableCart for CartableOptionPointer<C> where
368 C: CloneableCartablePointerLike + CloneableCart
369{
370}
371
372// Safety: logically an Option<C>. Has same bounds as Option<C>
373unsafe impl<C> Send for CartableOptionPointer<C> where C: Sync + CartablePointerLike {}
374
375// Safety: logically an Option<C>. Has same bounds as Option<C>
376unsafe impl<C> Sync for CartableOptionPointer<C> where C: Send + CartablePointerLike {}
377
378#[cfg(test)]
379mod tests {
380 use super::*;
381 use crate::Yoke;
382 use core::mem::size_of;
383
384 const SAMPLE_BYTES: &[u8] = b"abCDEfg";
385 const W: usize = size_of::<usize>();
386
387 #[test]
388 fn test_sizes() {
389 assert_eq!(W * 4, size_of::<Yoke<[usize; 3], &&[u8]>>());
390 assert_eq!(W * 4, size_of::<Yoke<[usize; 3], Option<&&[u8]>>>());
391 assert_eq!(
392 W * 4,
393 size_of::<Yoke<[usize; 3], CartableOptionPointer<&&[u8]>>>()
394 );
395
396 assert_eq!(W * 4, size_of::<Option<Yoke<[usize; 3], &&[u8]>>>());
397 assert_eq!(W * 5, size_of::<Option<Yoke<[usize; 3], Option<&&[u8]>>>>());
398 assert_eq!(
399 W * 4,
400 size_of::<Option<Yoke<[usize; 3], CartableOptionPointer<&&[u8]>>>>()
401 );
402 }
403
404 #[test]
405 fn test_new_sentinel() {
406 let start = DROP_INVOCATIONS.with(Cell::get);
407 {
408 let _ = CartableOptionPointer::<Rc<&[u8]>>::none();
409 }
410 assert_eq!(start, DROP_INVOCATIONS.with(Cell::get));
411 {
412 let _ = CartableOptionPointer::<Rc<&[u8]>>::none();
413 }
414 assert_eq!(start, DROP_INVOCATIONS.with(Cell::get));
415 }
416
417 #[test]
418 fn test_new_rc() {
419 let start = DROP_INVOCATIONS.with(Cell::get);
420 {
421 let _ = CartableOptionPointer::<Rc<&[u8]>>::from_cartable(SAMPLE_BYTES.into());
422 }
423 assert_eq!(start + 1, DROP_INVOCATIONS.with(Cell::get));
424 }
425
426 #[test]
427 fn test_rc_clone() {
428 let start = DROP_INVOCATIONS.with(Cell::get);
429 {
430 let x = CartableOptionPointer::<Rc<&[u8]>>::from_cartable(SAMPLE_BYTES.into());
431 assert_eq!(start, DROP_INVOCATIONS.with(Cell::get));
432 {
433 let _ = x.clone();
434 }
435 assert_eq!(start, DROP_INVOCATIONS.with(Cell::get));
436 {
437 let _ = x.clone();
438 let _ = x.clone();
439 let _ = x.clone();
440 }
441 assert_eq!(start, DROP_INVOCATIONS.with(Cell::get));
442 }
443 assert_eq!(start + 1, DROP_INVOCATIONS.with(Cell::get));
444 }
445}
446