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#[cfg(feature = "alloc")]
6use alloc::borrow::{Cow, ToOwned};
7use core::{marker::PhantomData, mem};
8
9/// The `Yokeable<'a>` trait is implemented on the `'static` version of any zero-copy type; for
10/// example, `Cow<'static, T>` implements `Yokeable<'a>` (for all `'a`).
11///
12/// One can use
13/// `Yokeable::Output` on this trait to obtain the "lifetime'd" value of the `Cow<'static, T>`,
14/// e.g. `<Cow<'static, T> as Yokeable<'a>'>::Output` is `Cow<'a, T>`.
15///
16/// A [`Yokeable`] type is essentially one with a covariant lifetime parameter,
17/// matched to the parameter in the trait definition. The trait allows one to cast
18/// the covariant lifetime to and from `'static`.
19///
20/// **Most of the time, if you need to implement [`Yokeable`], you should be able to use the safe
21/// [`#[derive(Yokeable)]`](yoke_derive::Yokeable) custom derive.**
22///
23/// While Rust does not yet have GAT syntax, for the purpose of this documentation
24/// we shall refer to "`Self` with a lifetime `'a`" with the syntax `Self<'a>`.
25/// Self<'static> is a stand-in for the HKT Self<'_>: lifetime -> type.
26///
27/// With this terminology, [`Yokeable`] exposes ways to cast between `Self<'static>` and `Self<'a>` generically.
28/// This is useful for turning covariant lifetimes to _dynamic_ lifetimes, where `'static` is
29/// used as a way to "erase" the lifetime.
30///
31/// # Safety
32///
33/// This trait is safe to implement on types with a _covariant_ lifetime parameter, i.e. one where
34/// [`Self::transform()`]'s body can simply be `{ self }`. This will occur when the lifetime
35/// parameter is used within references, but not in the arguments of function pointers or in mutable
36/// positions (either in `&mut` or via interior mutability)
37///
38/// This trait must be implemented on the `'static` version of such a type, e.g. one should
39/// implement `Yokeable<'a>` (for all `'a`) on `Cow<'static, T>`.
40///
41/// This trait is also safe to implement on types that do not borrow memory.
42///
43/// There are further constraints on implementation safety on individual methods.
44///
45/// # Trait bounds
46///
47/// [Compiler bug #85636](https://github.com/rust-lang/rust/issues/85636) makes it tricky to add
48/// trait bounds on `Yokeable::Output`. For more information and for workarounds, see
49/// [`crate::trait_hack`].
50///
51/// # Implementation example
52///
53/// Implementing this trait manually is unsafe. Where possible, you should use the safe
54/// [`#[derive(Yokeable)]`](yoke_derive::Yokeable) custom derive instead. We include an example
55/// in case you have your own zero-copy abstractions you wish to make yokeable.
56///
57/// ```rust
58/// # use yoke::Yokeable;
59/// # use std::borrow::Cow;
60/// # use std::{mem, ptr};
61/// struct Bar<'a> {
62/// numbers: Cow<'a, [u8]>,
63/// string: Cow<'a, str>,
64/// owned: Vec<u8>,
65/// }
66///
67/// unsafe impl<'a> Yokeable<'a> for Bar<'static> {
68/// type Output = Bar<'a>;
69/// fn transform(&'a self) -> &'a Bar<'a> {
70/// // covariant lifetime cast, can be done safely
71/// self
72/// }
73///
74/// fn transform_owned(self) -> Bar<'a> {
75/// // covariant lifetime cast, can be done safely
76/// self
77/// }
78///
79/// unsafe fn make(from: Bar<'a>) -> Self {
80/// // We're just doing mem::transmute() here, however Rust is
81/// // not smart enough to realize that Bar<'a> and Bar<'static> are of
82/// // the same size, so instead we use transmute_copy
83///
84/// // This assert will be optimized out, but is included for additional
85/// // peace of mind as we are using transmute_copy
86/// debug_assert!(mem::size_of::<Bar<'a>>() == mem::size_of::<Self>());
87/// let ptr: *const Self = (&from as *const Self::Output).cast();
88/// mem::forget(from);
89/// ptr::read(ptr)
90/// }
91///
92/// fn transform_mut<F>(&'a mut self, f: F)
93/// where
94/// F: 'static + FnOnce(&'a mut Self::Output),
95/// {
96/// unsafe { f(mem::transmute::<&mut Self, &mut Self::Output>(self)) }
97/// }
98/// }
99/// ```
100pub unsafe trait Yokeable<'a>: 'static {
101 /// This type MUST be `Self` with the `'static` replaced with `'a`, i.e. `Self<'a>`
102 type Output: 'a;
103
104 /// This method must cast `self` between `&'a Self<'static>` and `&'a Self<'a>`.
105 ///
106 /// # Implementation safety
107 ///
108 /// If the invariants of [`Yokeable`] are being satisfied, the body of this method
109 /// should simply be `{ self }`, though it's acceptable to include additional assertions
110 /// if desired.
111 fn transform(&'a self) -> &'a Self::Output;
112
113 /// This method must cast `self` between `Self<'static>` and `Self<'a>`.
114 ///
115 /// # Implementation safety
116 ///
117 /// If the invariants of [`Yokeable`] are being satisfied, the body of this method
118 /// should simply be `{ self }`, though it's acceptable to include additional assertions
119 /// if desired.
120 fn transform_owned(self) -> Self::Output;
121
122 /// This method can be used to cast away `Self<'a>`'s lifetime.
123 ///
124 /// # Safety
125 ///
126 /// The returned value must be destroyed before the data `from` was borrowing from is.
127 ///
128 /// # Implementation safety
129 ///
130 /// A safe implementation of this method must be equivalent to a transmute between
131 /// `Self<'a>` and `Self<'static>`
132 unsafe fn make(from: Self::Output) -> Self;
133
134 /// This method must cast `self` between `&'a mut Self<'static>` and `&'a mut Self<'a>`,
135 /// and pass it to `f`.
136 ///
137 /// # Implementation safety
138 ///
139 /// A safe implementation of this method must be equivalent to a pointer cast/transmute between
140 /// `&mut Self<'a>` and `&mut Self<'static>` being passed to `f`
141 ///
142 /// # Why is this safe?
143 ///
144 /// Typically covariant lifetimes become invariant when hidden behind an `&mut`,
145 /// which is why the implementation of this method cannot just be `f(self)`.
146 /// The reason behind this is that while _reading_ a covariant lifetime that has been cast to a shorter
147 /// one is always safe (this is roughly the definition of a covariant lifetime), writing
148 /// may not necessarily be safe since you could write a smaller reference to it. For example,
149 /// the following code is unsound because it manages to stuff a `'a` lifetime into a `Cow<'static>`
150 ///
151 /// ```rust,compile_fail
152 /// # use std::borrow::Cow;
153 /// # use yoke::Yokeable;
154 /// struct Foo {
155 /// str: String,
156 /// cow: Cow<'static, str>,
157 /// }
158 ///
159 /// fn unsound<'a>(foo: &'a mut Foo) {
160 /// let a: &str = &foo.str;
161 /// foo.cow.transform_mut(|cow| *cow = Cow::Borrowed(a));
162 /// }
163 /// ```
164 ///
165 /// However, this code will not compile because [`Yokeable::transform_mut()`] requires `F: 'static`.
166 /// This enforces that while `F` may mutate `Self<'a>`, it can only mutate it in a way that does
167 /// not insert additional references. For example, `F` may call `to_owned()` on a `Cow` and mutate it,
168 /// but it cannot insert a new _borrowed_ reference because it has nowhere to borrow _from_ --
169 /// `f` does not contain any borrowed references, and while we give it `Self<'a>` (which contains borrowed
170 /// data), that borrowed data is known to be valid
171 ///
172 /// Note that the `for<'b>` is also necessary, otherwise the following code would compile:
173 ///
174 /// ```rust,compile_fail
175 /// # use std::borrow::Cow;
176 /// # use yoke::Yokeable;
177 /// # use std::mem;
178 /// #
179 /// // also safely implements Yokeable<'a>
180 /// struct Bar<'a> {
181 /// num: u8,
182 /// cow: Cow<'a, u8>,
183 /// }
184 ///
185 /// fn unsound<'a>(bar: &'a mut Bar<'static>) {
186 /// bar.transform_mut(move |bar| bar.cow = Cow::Borrowed(&bar.num));
187 /// }
188 /// #
189 /// # unsafe impl<'a> Yokeable<'a> for Bar<'static> {
190 /// # type Output = Bar<'a>;
191 /// # fn transform(&'a self) -> &'a Bar<'a> {
192 /// # self
193 /// # }
194 /// #
195 /// # fn transform_owned(self) -> Bar<'a> {
196 /// # // covariant lifetime cast, can be done safely
197 /// # self
198 /// # }
199 /// #
200 /// # unsafe fn make(from: Bar<'a>) -> Self {
201 /// # let ret = mem::transmute_copy(&from);
202 /// # mem::forget(from);
203 /// # ret
204 /// # }
205 /// #
206 /// # fn transform_mut<F>(&'a mut self, f: F)
207 /// # where
208 /// # F: 'static + FnOnce(&'a mut Self::Output),
209 /// # {
210 /// # unsafe { f(mem::transmute(self)) }
211 /// # }
212 /// # }
213 /// ```
214 ///
215 /// which is unsound because `bar` could be moved later, and we do not want to be able to
216 /// self-insert references to it.
217 ///
218 /// The `for<'b>` enforces this by stopping the author of the closure from matching up the input
219 /// `&'b Self::Output` lifetime with `'a` and borrowing directly from it.
220 ///
221 /// Thus the only types of mutations allowed are ones that move around already-borrowed data, or
222 /// introduce new owned data:
223 ///
224 /// ```rust
225 /// # use std::borrow::Cow;
226 /// # use yoke::Yokeable;
227 /// struct Foo {
228 /// str: String,
229 /// cow: Cow<'static, str>,
230 /// }
231 ///
232 /// fn sound<'a>(foo: &'a mut Foo) {
233 /// foo.cow.transform_mut(move |cow| cow.to_mut().push('a'));
234 /// }
235 /// ```
236 ///
237 /// More formally, a reference to an object that `f` assigns to a reference
238 /// in Self<'a> could be obtained from:
239 /// - a local variable: the compiler rejects the assignment because 'a certainly
240 /// outlives local variables in f.
241 /// - a field in its argument: because of the for<'b> bound, the call to `f`
242 /// must be valid for a particular 'b that is strictly shorter than 'a. Thus,
243 /// the compiler rejects the assignment.
244 /// - a reference field in Self<'a>: this does not extend the set of
245 /// non-static lifetimes reachable from Self<'a>, so this is fine.
246 /// - one of f's captures: since F: 'static, the resulting reference must refer
247 /// to 'static data.
248 /// - a static or thread_local variable: ditto.
249 fn transform_mut<F>(&'a mut self, f: F)
250 where
251 // be VERY CAREFUL changing this signature, it is very nuanced (see above)
252 F: 'static + for<'b> FnOnce(&'b mut Self::Output);
253}
254
255#[cfg(feature = "alloc")]
256// Safety: Cow<'a, _> is covariant in 'a.
257unsafe impl<'a, T: 'static + ToOwned + ?Sized> Yokeable<'a> for Cow<'static, T>
258where
259 <T as ToOwned>::Owned: Sized,
260{
261 type Output = Cow<'a, T>;
262 #[inline]
263 fn transform(&'a self) -> &'a Cow<'a, T> {
264 // Doesn't need unsafe: `'a` is covariant so this lifetime cast is always safe
265 self
266 }
267 #[inline]
268 fn transform_owned(self) -> Cow<'a, T> {
269 // Doesn't need unsafe: `'a` is covariant so this lifetime cast is always safe
270 self
271 }
272 #[inline]
273 unsafe fn make(from: Cow<'a, T>) -> Self {
274 // i hate this
275 // unfortunately Rust doesn't think `mem::transmute` is possible since it's not sure the sizes
276 // are the same
277 debug_assert!(mem::size_of::<Cow<'a, T>>() == mem::size_of::<Self>());
278 let ptr: *const Self = (&from as *const Self::Output).cast();
279 let _ = core::mem::ManuallyDrop::new(from);
280 // Safety: `ptr` is certainly valid, aligned and points to a properly initialized value, as
281 // it comes from a value that was moved into a ManuallyDrop.
282 unsafe { core::ptr::read(ptr) }
283 }
284 #[inline]
285 fn transform_mut<F>(&'a mut self, f: F)
286 where
287 F: 'static + for<'b> FnOnce(&'b mut Self::Output),
288 {
289 // Cast away the lifetime of Self
290 // Safety: this is equivalent to f(transmute(self)), and the documentation of the trait
291 // method explains why doing so is sound.
292 unsafe { f(mem::transmute::<&'a mut Self, &'a mut Self::Output>(self)) }
293 }
294}
295
296// Safety: &'a T is covariant in 'a.
297unsafe impl<'a, T: 'static + ?Sized> Yokeable<'a> for &'static T {
298 type Output = &'a T;
299 #[inline]
300 fn transform(&'a self) -> &'a &'a T {
301 // Doesn't need unsafe: `'a` is covariant so this lifetime cast is always safe
302 self
303 }
304 #[inline]
305 fn transform_owned(self) -> &'a T {
306 // Doesn't need unsafe: `'a` is covariant so this lifetime cast is always safe
307 self
308 }
309 #[inline]
310 unsafe fn make(from: &'a T) -> Self {
311 // Safety: function safety invariant guarantees that the returned reference
312 // will never be used beyond its original lifetime.
313 unsafe { mem::transmute(from) }
314 }
315 #[inline]
316 fn transform_mut<F>(&'a mut self, f: F)
317 where
318 F: 'static + for<'b> FnOnce(&'b mut Self::Output),
319 {
320 // Cast away the lifetime of Self
321 // Safety: this is equivalent to f(transmute(self)), and the documentation of the trait
322 // method explains why doing so is sound.
323 unsafe { f(mem::transmute::<&'a mut Self, &'a mut Self::Output>(self)) }
324 }
325}
326
327#[cfg(feature = "alloc")]
328// Safety: Vec<T: 'static> never borrows.
329unsafe impl<'a, T: 'static> Yokeable<'a> for alloc::vec::Vec<T> {
330 type Output = alloc::vec::Vec<T>;
331 #[inline]
332 fn transform(&'a self) -> &'a alloc::vec::Vec<T> {
333 self
334 }
335 #[inline]
336 fn transform_owned(self) -> alloc::vec::Vec<T> {
337 self
338 }
339 #[inline]
340 unsafe fn make(from: alloc::vec::Vec<T>) -> Self {
341 from
342 }
343 #[inline]
344 fn transform_mut<F>(&'a mut self, f: F)
345 where
346 F: 'static + for<'b> dynFnOnce(&'b mut Self::Output),
347 {
348 f(self)
349 }
350}
351
352// Safety: PhantomData is a ZST.
353unsafe impl<'a, T: ?Sized + 'static> Yokeable<'a> for PhantomData<T> {
354 type Output = PhantomData<T>;
355
356 fn transform(&'a self) -> &'a Self::Output {
357 self
358 }
359
360 fn transform_owned(self) -> Self::Output {
361 self
362 }
363
364 unsafe fn make(from: Self::Output) -> Self {
365 from
366 }
367
368 fn transform_mut<F>(&'a mut self, f: F)
369 where
370 // be VERY CAREFUL changing this signature, it is very nuanced (see above)
371 F: 'static + for<'b> dynFnOnce(&'b mut Self::Output),
372 {
373 f(self)
374 }
375}
376