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")] 6 use alloc::borrow::{Cow, ToOwned}; 7 use 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 /// ``` 100 pub 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. transform(&'a self) -> &'a Self::Output111 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. transform_owned(self) -> Self::Output120 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>` make(from: Self::Output) -> Self132 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. transform_mut<F>(&'a mut self, f: F) where F: 'static + for<'b> FnOnce(&'b mut Self::Output)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. 257 unsafe impl<'a, T: 'static + ToOwned + ?Sized> Yokeable<'a> for Cow<'static, T> 258 where 259 <T as ToOwned>::Owned: Sized, 260 { 261 type Output = Cow<'a, T>; 262 #[inline] transform(&'a self) -> &'a Cow<'a, T>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] transform_owned(self) -> Cow<'a, T>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] make(from: Cow<'a, T>) -> Self273 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] transform_mut<F>(&'a mut self, f: F) where F: 'static + for<'b> FnOnce(&'b mut Self::Output),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. 297 unsafe impl<'a, T: 'static + ?Sized> Yokeable<'a> for &'static T { 298 type Output = &'a T; 299 #[inline] transform(&'a self) -> &'a &'a T300 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] transform_owned(self) -> &'a T305 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] make(from: &'a T) -> Self310 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] transform_mut<F>(&'a mut self, f: F) where F: 'static + for<'b> FnOnce(&'b mut Self::Output),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. 329 unsafe impl<'a, T: 'static> Yokeable<'a> for alloc::vec::Vec<T> { 330 type Output = alloc::vec::Vec<T>; 331 #[inline] transform(&'a self) -> &'a alloc::vec::Vec<T>332 fn transform(&'a self) -> &'a alloc::vec::Vec<T> { 333 self 334 } 335 #[inline] transform_owned(self) -> alloc::vec::Vec<T>336 fn transform_owned(self) -> alloc::vec::Vec<T> { 337 self 338 } 339 #[inline] make(from: alloc::vec::Vec<T>) -> Self340 unsafe fn make(from: alloc::vec::Vec<T>) -> Self { 341 from 342 } 343 #[inline] transform_mut<F>(&'a mut self, f: F) where F: 'static + for<'b> FnOnce(&'b mut Self::Output),344 fn transform_mut<F>(&'a mut self, f: F) 345 where 346 F: 'static + for<'b> FnOnce(&'b mut Self::Output), 347 { 348 f(self) 349 } 350 } 351 352 // Safety: PhantomData is a ZST. 353 unsafe impl<'a, T: ?Sized + 'static> Yokeable<'a> for PhantomData<T> { 354 type Output = PhantomData<T>; 355 transform(&'a self) -> &'a Self::Output356 fn transform(&'a self) -> &'a Self::Output { 357 self 358 } 359 transform_owned(self) -> Self::Output360 fn transform_owned(self) -> Self::Output { 361 self 362 } 363 make(from: Self::Output) -> Self364 unsafe fn make(from: Self::Output) -> Self { 365 from 366 } 367 transform_mut<F>(&'a mut self, f: F) where F: 'static + for<'b> FnOnce(&'b mut Self::Output),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> FnOnce(&'b mut Self::Output), 372 { 373 f(self) 374 } 375 } 376