qcell/lcell.rs
1use core::cell::UnsafeCell;
2use core::marker::PhantomData;
3
4use super::Invariant;
5type Id<'id> = PhantomData<Invariant<&'id ()>>;
6
7/// Borrowing-owner of zero or more [`LCell`](struct.LCell.html)
8/// instances.
9///
10/// Use `LCellOwner::scope(|owner| ...)` to create an instance of this
11/// type. The key piece of Rust syntax that enables this is
12/// `for<'id>`. This allows creating an invariant lifetime within a
13/// closure, which is different to any other Rust lifetime thanks to
14/// the techniques explained in various places: section 6.3 of [this
15/// thesis from Gankra (formerly
16/// Gankro)](https://raw.githubusercontent.com/Gankra/thesis/master/thesis.pdf),
17/// [this Reddit
18/// post](https://www.reddit.com/r/rust/comments/3oo0oe/sound_unchecked_indexing_with_lifetimebased_value/),
19/// and [this Rust playground
20/// example](https://play.rust-lang.org/?gist=21a00b0e181a918f8ca4&version=stable).
21/// Also see [this Reddit
22/// comment](https://www.reddit.com/r/rust/comments/3aahl1/outside_of_closures_what_are_some_other_uses_for/csavac5/)
23/// and its linked playground code.
24///
25/// Alternatively, if the **generativity** feature is enabled, the
26/// [`generativity`](https://crates.io/crates/generativity) crate can
27/// be used to create an owner as follows: `make_guard!(guard); let
28/// mut owner = LCellOwner::new(guard);`. However note that the Rust
29/// compiler error messages may be more confusing with
30/// **generativity** if you make a mistake and use the wrong owner for
31/// a cell.
32///
33/// Some history: `GhostCell` by
34/// [**pythonesque**](https://github.com/pythonesque) predates the
35/// creation of `LCell`, and inspired it. Discussion of `GhostCell`
36/// on Reddit showed that a lifetime-based approach to cells was
37/// feasible, but unfortunately the `ghost_cell.rs` source didn't seem
38/// to be available under a community-friendly licence. So I went
39/// back to first principles and created `LCell` from `TCell` code,
40/// combined with invariant lifetime code derived from the various
41/// community sources that predate `GhostCell`. Later `Send` and
42/// `Sync` support for `LCell` was contributed independently.
43///
44/// See also [crate documentation](index.html).
45pub struct LCellOwner<'id> {
46 _id: Id<'id>,
47}
48
49impl<'id> LCellOwner<'id> {
50 /// Create a new `LCellOwner`, with a new lifetime, that exists
51 /// only within the scope of the execution of the given closure
52 /// call. If two scope calls are nested, then the two owners get
53 /// different lifetimes.
54 ///
55 /// ```rust
56 /// use qcell::{LCellOwner, LCell};
57 /// LCellOwner::scope(|owner| {
58 /// let cell = LCell::new(100);
59 /// assert_eq!(cell.ro(&owner), &100);
60 /// })
61 /// ```
62 pub fn scope<F>(f: F)
63 where
64 F: for<'scope_id> FnOnce(LCellOwner<'scope_id>),
65 {
66 f(Self { _id: PhantomData })
67 }
68
69 /// Create a new `LCellOwner` with a unique lifetime from a `Guard`.
70 ///
71 /// ```rust
72 /// use qcell::{generativity::make_guard, LCellOwner, LCell};
73 /// make_guard!(guard);
74 /// let mut owner = LCellOwner::new(guard);
75 /// let cell = LCell::new(100);
76 /// assert_eq!(cell.ro(&owner), &100);
77 /// ```
78 #[cfg(feature = "generativity")]
79 #[cfg_attr(docsrs, doc(cfg(feature = "generativity")))]
80 pub fn new(_guard: generativity::Guard<'id>) -> Self {
81 Self { _id: PhantomData }
82 }
83
84 /// Create a new cell owned by this owner instance. See also
85 /// [`LCell::new`].
86 ///
87 /// [`LCell::new`]: struct.LCell.html
88 pub fn cell<T>(&self, value: T) -> LCell<'id, T> {
89 LCell::<T>::new(value)
90 }
91
92 /// Borrow contents of a `LCell` immutably (read-only). Many
93 /// `LCell` instances can be borrowed immutably at the same time
94 /// from the same owner.
95 #[inline]
96 pub fn ro<'a, T: ?Sized>(&'a self, lc: &'a LCell<'id, T>) -> &'a T {
97 unsafe { &*lc.value.get() }
98 }
99
100 /// Borrow contents of a `LCell` mutably (read-write). Only one
101 /// `LCell` at a time can be borrowed from the owner using this
102 /// call. The returned reference must go out of scope before
103 /// another can be borrowed.
104 #[inline]
105 pub fn rw<'a, T: ?Sized>(&'a mut self, lc: &'a LCell<'id, T>) -> &'a mut T {
106 unsafe { &mut *lc.value.get() }
107 }
108
109 /// Borrow contents of two `LCell` instances mutably. Panics if
110 /// the two `LCell` instances point to the same memory.
111 #[inline]
112 pub fn rw2<'a, T: ?Sized, U: ?Sized>(
113 &'a mut self,
114 lc1: &'a LCell<'id, T>,
115 lc2: &'a LCell<'id, U>,
116 ) -> (&'a mut T, &'a mut U) {
117 assert!(
118 lc1 as *const _ as *const () as usize != lc2 as *const _ as *const () as usize,
119 "Illegal to borrow same LCell twice with rw2()"
120 );
121 unsafe { (&mut *lc1.value.get(), &mut *lc2.value.get()) }
122 }
123
124 /// Borrow contents of three `LCell` instances mutably. Panics if
125 /// any pair of `LCell` instances point to the same memory.
126 #[inline]
127 pub fn rw3<'a, T: ?Sized, U: ?Sized, V: ?Sized>(
128 &'a mut self,
129 lc1: &'a LCell<'id, T>,
130 lc2: &'a LCell<'id, U>,
131 lc3: &'a LCell<'id, V>,
132 ) -> (&'a mut T, &'a mut U, &'a mut V) {
133 assert!(
134 (lc1 as *const _ as *const () as usize != lc2 as *const _ as *const () as usize)
135 && (lc2 as *const _ as *const () as usize != lc3 as *const _ as *const () as usize)
136 && (lc3 as *const _ as *const () as usize != lc1 as *const _ as *const () as usize),
137 "Illegal to borrow same LCell twice with rw3()"
138 );
139 unsafe {
140 (
141 &mut *lc1.value.get(),
142 &mut *lc2.value.get(),
143 &mut *lc3.value.get(),
144 )
145 }
146 }
147}
148
149/// Cell whose contents are owned (for borrowing purposes) by a
150/// [`LCellOwner`].
151///
152/// To borrow from this cell, use the borrowing calls on the
153/// [`LCellOwner`] instance that owns it, i.e. that shares the same
154/// Rust lifetime.
155///
156/// See also [crate documentation](index.html).
157///
158/// [`LCellOwner`]: struct.LCellOwner.html
159#[repr(transparent)]
160pub struct LCell<'id, T: ?Sized> {
161 _id: Id<'id>,
162 value: UnsafeCell<T>,
163}
164
165impl<'id, T> LCell<'id, T> {
166 /// Create a new `LCell`. The owner of this cell is inferred by
167 /// Rust from the context. So the owner lifetime is whatever
168 /// lifetime is required by the first use of the new `LCell`.
169 #[inline]
170 pub fn new(value: T) -> LCell<'id, T> {
171 LCell {
172 _id: PhantomData,
173 value: UnsafeCell::new(value),
174 }
175 }
176
177 /// Destroy the cell and return the contained value
178 ///
179 /// Safety: Since this consumes the cell, there can be no other
180 /// references to the cell or the data at this point.
181 #[inline]
182 pub fn into_inner(self) -> T {
183 self.value.into_inner()
184 }
185}
186
187impl<'id, T: ?Sized> LCell<'id, T> {
188 /// Borrow contents of this cell immutably (read-only). Many
189 /// `LCell` instances can be borrowed immutably at the same time
190 /// from the same owner.
191 #[inline]
192 pub fn ro<'a>(&'a self, owner: &'a LCellOwner<'id>) -> &'a T {
193 owner.ro(self)
194 }
195
196 /// Borrow contents of this cell mutably (read-write). Only one
197 /// `LCell` at a time can be borrowed from the owner using this
198 /// call. The returned reference must go out of scope before
199 /// another can be borrowed. To mutably borrow from two or three
200 /// cells at the same time, see [`LCellOwner::rw2`] or
201 /// [`LCellOwner::rw3`].
202 #[inline]
203 pub fn rw<'a>(&'a self, owner: &'a mut LCellOwner<'id>) -> &'a mut T {
204 owner.rw(self)
205 }
206
207 /// Returns a mutable reference to the underlying data
208 ///
209 /// Note that this is only useful at the beginning-of-life or
210 /// end-of-life of the cell when you have exclusive access to it.
211 /// Normally you'd use [`LCell::rw`] or [`LCellOwner::rw`] to get
212 /// a mutable reference to the contents of the cell.
213 ///
214 /// Safety: This call borrows `LCell` mutably which guarantees
215 /// that we possess the only reference. This means that there can
216 /// be no active borrows of other forms, even ones obtained using
217 /// an immutable reference.
218 #[inline]
219 pub fn get_mut(&mut self) -> &mut T {
220 self.value.get_mut()
221 }
222}
223
224impl<'id, T: Default + ?Sized> Default for LCell<'id, T> {
225 fn default() -> Self {
226 LCell::new(T::default())
227 }
228}
229
230// LCell already automatically implements Send, but not
231// Sync. We can add these implementations though, since it's fine to
232// send a &LCell to another thread, and even mutably borrow the value
233// there, as long as T is Send and Sync.
234//
235// The reason why LCell<T>'s impl of Sync requires T: Send + Sync
236// instead of just T: Sync is that LCell provides interior mutability.
237// If you send a &LCell<T> (and its owner) to a different thread, you
238// can call .rw() to get a &mut T, and use std::mem::swap() to move
239// the T, effectively sending the T to that other thread. That's not
240// allowed if T: !Send.
241//
242// Note that the bounds on T for LCell<T>'s impl of Sync are the same
243// as those of std::sync::RwLock<T>. That's not a coincidence.
244// The way these types let you access T concurrently is the same,
245// even though the locking mechanisms are different.
246unsafe impl<'id, T: Send + Sync + ?Sized> Sync for LCell<'id, T> {}
247
248#[cfg(test)]
249mod tests {
250 use super::{LCell, LCellOwner};
251 use std::rc::Rc;
252
253 #[test]
254 fn lcell() {
255 LCellOwner::scope(|mut owner| {
256 let c1 = LCell::new(100u32);
257 let c2 = owner.cell(200u32);
258 (*owner.rw(&c1)) += 1;
259 (*owner.rw(&c2)) += 2;
260 let c1ref = owner.ro(&c1);
261 let c2ref = owner.ro(&c2);
262 let total = *c1ref + *c2ref;
263 assert_eq!(total, 303);
264 });
265 }
266
267 #[test]
268 #[cfg(feature = "generativity")]
269 fn generativity() {
270 generativity::make_guard!(guard);
271 let mut owner = LCellOwner::new(guard);
272 let c1 = LCell::new(100_u32);
273 let c2 = LCell::new(200_u32);
274 (*owner.rw(&c1)) += 1;
275 (*owner.rw(&c2)) += 2;
276 let c1ref = owner.ro(&c1);
277 let c2ref = owner.ro(&c2);
278 let total = *c1ref + *c2ref;
279 assert_eq!(total, 303);
280 }
281
282 #[test]
283 #[should_panic]
284 fn lcell_rw2() {
285 LCellOwner::scope(|mut owner| {
286 let c1 = Rc::new(LCell::new(100u32));
287 let (mutref1, mutref2) = owner.rw2(&c1, &c1);
288 *mutref1 += 1;
289 *mutref2 += 1;
290 });
291 }
292
293 #[test]
294 #[should_panic]
295 fn lcell_rw3_1() {
296 LCellOwner::scope(|mut owner| {
297 let c1 = Rc::new(LCell::new(100u32));
298 let c2 = Rc::new(LCell::new(200u32));
299 let (mutref1, mutref2, mutref3) = owner.rw3(&c1, &c1, &c2);
300 *mutref1 += 1;
301 *mutref2 += 1;
302 *mutref3 += 1;
303 });
304 }
305
306 #[test]
307 #[should_panic]
308 fn lcell_rw3_2() {
309 LCellOwner::scope(|mut owner| {
310 let c1 = Rc::new(LCell::new(100u32));
311 let c2 = Rc::new(LCell::new(200u32));
312 let (mutref1, mutref2, mutref3) = owner.rw3(&c1, &c2, &c1);
313 *mutref1 += 1;
314 *mutref2 += 1;
315 *mutref3 += 1;
316 });
317 }
318
319 #[test]
320 #[should_panic]
321 fn lcell_rw3_3() {
322 LCellOwner::scope(|mut owner| {
323 let c1 = Rc::new(LCell::new(100u32));
324 let c2 = Rc::new(LCell::new(200u32));
325 let (mutref1, mutref2, mutref3) = owner.rw3(&c2, &c1, &c1);
326 *mutref1 += 1;
327 *mutref2 += 1;
328 *mutref3 += 1;
329 });
330 }
331
332 #[test]
333 fn lcell_get_mut() {
334 LCellOwner::scope(|owner| {
335 let mut cell = LCell::new(100u32);
336 let mut_ref = cell.get_mut();
337 *mut_ref = 50;
338 let cell_ref = owner.ro(&cell);
339 assert_eq!(*cell_ref, 50);
340 });
341 }
342
343 #[test]
344 fn lcell_into_inner() {
345 let cell = LCell::new(100u32);
346 assert_eq!(cell.into_inner(), 100);
347 }
348
349 #[test]
350 fn lcell_unsized() {
351 LCellOwner::scope(|mut owner| {
352 struct Squares(u32);
353 struct Integers(u64);
354 trait Series {
355 fn step(&mut self);
356 fn value(&self) -> u64;
357 }
358 impl Series for Squares {
359 fn step(&mut self) {
360 self.0 += 1;
361 }
362 fn value(&self) -> u64 {
363 (self.0 as u64) * (self.0 as u64)
364 }
365 }
366 impl Series for Integers {
367 fn step(&mut self) {
368 self.0 += 1;
369 }
370 fn value(&self) -> u64 {
371 self.0
372 }
373 }
374 fn series<'id>(init: u32, is_squares: bool) -> Box<LCell<'id, dyn Series>> {
375 if is_squares {
376 Box::new(LCell::new(Squares(init)))
377 } else {
378 Box::new(LCell::new(Integers(init as u64)))
379 }
380 }
381
382 let own = &mut owner;
383 let cell1 = series(4, false);
384 let cell2 = series(7, true);
385 let cell3 = series(3, true);
386 assert_eq!(cell1.ro(own).value(), 4);
387 cell1.rw(own).step();
388 assert_eq!(cell1.ro(own).value(), 5);
389 assert_eq!(own.ro(&cell2).value(), 49);
390 own.rw(&cell2).step();
391 assert_eq!(own.ro(&cell2).value(), 64);
392 let (r1, r2, r3) = own.rw3(&cell1, &cell2, &cell3);
393 r1.step();
394 r2.step();
395 r3.step();
396 assert_eq!(cell1.ro(own).value(), 6);
397 assert_eq!(cell2.ro(own).value(), 81);
398 assert_eq!(cell3.ro(own).value(), 16);
399 let (r1, r2) = own.rw2(&cell1, &cell2);
400 r1.step();
401 r2.step();
402 assert_eq!(cell1.ro(own).value(), 7);
403 assert_eq!(cell2.ro(own).value(), 100);
404 });
405 }
406}