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 | |
20 | use crate::CloneableCart; |
21 | #[cfg(feature = "alloc")] |
22 | use alloc::boxed::Box; |
23 | #[cfg(feature = "alloc")] |
24 | use alloc::rc::Rc; |
25 | #[cfg(feature = "alloc")] |
26 | use alloc::sync::Arc; |
27 | #[cfg(test)] |
28 | use core::cell::Cell; |
29 | use core::marker::PhantomData; |
30 | use core::ptr::NonNull; |
31 | use 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] |
40 | fn 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)] |
48 | thread_local! { |
49 | static DROP_INVOCATIONS: Cell<usize> = const { Cell::new(0) }; |
50 | } |
51 | |
52 | mod private { |
53 | pub trait Sealed {} |
54 | } |
55 | |
56 | use 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`]. |
73 | pub 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. |
104 | pub 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 | |
117 | impl<'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 |
122 | unsafe 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. |
138 | unsafe 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")] |
146 | impl<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." |
154 | unsafe 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 |
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")] |
176 | impl<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. |
183 | unsafe 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 |
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. |
211 | unsafe 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")] |
225 | impl<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. |
232 | unsafe 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 |
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. |
259 | unsafe 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)] |
279 | pub struct CartableOptionPointer<C> |
280 | where |
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 | |
293 | impl<C> CartableOptionPointer<C> |
294 | where |
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 | |
327 | impl<C> Drop for CartableOptionPointer<C> |
328 | where |
329 | C: CartablePointerLike, |
330 | { |
331 | #[inline] |
332 | fn drop(&mut self) { |
333 | let ptr: NonNull< |
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 | |
345 | impl<C> Clone for CartableOptionPointer<C> |
346 | where |
347 | C: CloneableCartablePointerLike, |
348 | { |
349 | #[inline] |
350 | fn clone(&self) -> Self { |
351 | let ptr: NonNull< |
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`. |
367 | unsafe 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> |
373 | unsafe impl<C> Send for CartableOptionPointer<C> where C: Sync + CartablePointerLike {} |
374 | |
375 | // Safety: logically an Option<C>. Has same bounds as Option<C> |
376 | unsafe impl<C> Sync for CartableOptionPointer<C> where C: Send + CartablePointerLike {} |
377 | |
378 | #[cfg(test)] |
379 | mod 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 |
Definitions
Learn Rust with the experts
Find out more