Skip to main content

tock_cells/
map_cell.rs

1// Licensed under the Apache License, Version 2.0 or the MIT License.
2// SPDX-License-Identifier: Apache-2.0 OR MIT
3// Copyright Tock Contributors 2022.
4
5//! Tock specific `MapCell` type for sharing references.
6
7use core::cell::{Cell, UnsafeCell};
8use core::mem::MaybeUninit;
9use core::ptr::drop_in_place;
10
11#[derive(Clone, Copy, PartialEq)]
12enum MapCellState {
13    Uninit,
14    Init,
15    Borrowed,
16}
17
18#[inline(never)]
19#[cold]
20fn access_panic() {
21    panic!("`MapCell` accessed while borrowed");
22}
23
24macro_rules! debug_assert_not_borrowed {
25    ($slf:ident) => {
26        if cfg!(debug_assertions) && $slf.occupied.get() == MapCellState::Borrowed {
27            access_panic();
28        }
29    };
30}
31
32/// A mutable, possibly unset, memory location that provides checked `&mut` access
33/// to its contents via a closure.
34///
35/// A `MapCell` provides checked shared access to its mutable memory. Borrow
36/// rules are enforced by forcing clients to either move the memory out of the
37/// cell or operate on a `&mut` within a closure. You can think of a `MapCell`
38/// as a `Cell<Option<T>>` with an extra "in-use" state to prevent `map` from invoking
39/// undefined behavior when called re-entrantly.
40///
41/// # Examples
42/// ```
43/// # use tock_cells::map_cell::MapCell;
44/// let cell: MapCell<i64> = MapCell::empty();
45///
46/// assert!(cell.is_none());
47/// cell.map(|_| unreachable!("The cell is empty; map does not call the closure"));
48/// assert_eq!(cell.take(), None);
49/// cell.put(10);
50/// assert_eq!(cell.take(), Some(10));
51/// assert_eq!(cell.replace(20), None);
52/// assert_eq!(cell.get(), Some(20));
53///
54/// cell.map(|x| {
55///     assert_eq!(x, &mut 20);
56///     // `map` provides a `&mut` to the contents inside the closure
57///     *x = 30;
58/// });
59/// assert_eq!(cell.replace(60), Some(30));
60/// ```
61pub struct MapCell<T> {
62    // Since val is potentially uninitialized memory, we must be sure to check
63    // `.occupied` before calling `.val.get()` or `.val.assume_init()`. See
64    // [mem::MaybeUninit](https://doc.rust-lang.org/core/mem/union.MaybeUninit.html).
65    val: UnsafeCell<MaybeUninit<T>>,
66
67    // Safety invariants:
68    // - The contents of `val` must be initialized if this is `Init` or `Borrowed`.
69    // - It must be sound to mutate `val` behind a shared reference if this is `Uninit` or `Init`.
70    //   No outside mutation can occur while a `&mut` to the contents of `val` exist.
71    occupied: Cell<MapCellState>,
72}
73
74impl<T> Drop for MapCell<T> {
75    fn drop(&mut self) {
76        let state = self.occupied.get();
77        debug_assert_not_borrowed!(self); // This should be impossible
78        if state == MapCellState::Init {
79            unsafe {
80                // SAFETY:
81                // - `occupied` is `Init`; `val` is initialized as an invariant.
82                // - Even though this violates the `occupied` invariant, by causing `val`
83                //   to be no longer valid, `self` is immediately dropped.
84                drop_in_place(self.val.get_mut().as_mut_ptr())
85            }
86        }
87    }
88}
89
90impl<T: Copy> MapCell<T> {
91    /// Gets the contents of the cell, if any.
92    ///
93    /// Returns `None` if the cell is empty.
94    ///
95    /// This requires the held type be `Copy` for the same reason [`Cell::get`] does:
96    /// it leaves the contents of `self` intact and so it can't have drop glue.
97    ///
98    /// This returns `None` in release mode if the `MapCell`'s contents are already borrowed.
99    ///
100    /// # Examples
101    /// ```
102    /// # use tock_cells::map_cell::MapCell;
103    /// let cell: MapCell<u32> = MapCell::empty();
104    /// assert_eq!(cell.get(), None);
105    ///
106    /// cell.put(20);
107    /// assert_eq!(cell.get(), Some(20));
108    /// ```
109    ///
110    /// # Panics
111    /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
112    pub fn get(&self) -> Option<T> {
113        debug_assert_not_borrowed!(self);
114        // SAFETY:
115        // - `Init` means that `val` is initialized and can be read
116        // - `T: Copy` so there is no drop glue
117        (self.occupied.get() == MapCellState::Init)
118            .then(|| unsafe { self.val.get().read().assume_init() })
119    }
120}
121
122impl<T> MapCell<T> {
123    /// Creates an empty `MapCell`.
124    pub const fn empty() -> MapCell<T> {
125        MapCell {
126            val: UnsafeCell::new(MaybeUninit::uninit()),
127            occupied: Cell::new(MapCellState::Uninit),
128        }
129    }
130
131    /// Creates a new `MapCell` containing `value`.
132    pub const fn new(value: T) -> MapCell<T> {
133        MapCell {
134            val: UnsafeCell::new(MaybeUninit::new(value)),
135            occupied: Cell::new(MapCellState::Init),
136        }
137    }
138
139    /// Returns `true` if the `MapCell` contains no value.
140    ///
141    /// # Examples
142    /// ```
143    /// # use tock_cells::map_cell::MapCell;
144    /// let x: MapCell<i32> = MapCell::empty();
145    /// assert!(x.is_none());
146    ///
147    /// x.put(10);
148    /// x.map(|_| assert!(!x.is_none()));
149    /// assert!(!x.is_none());
150    /// ```
151    pub fn is_none(&self) -> bool {
152        !self.is_some()
153    }
154
155    /// Returns `true` if the `MapCell` contains a value.
156    ///
157    /// # Examples
158    /// ```
159    /// # use tock_cells::map_cell::MapCell;
160    /// let x: MapCell<i32> = MapCell::new(10);
161    /// assert!(x.is_some());
162    /// x.map(|_| assert!(x.is_some()));
163    ///
164    /// x.take();
165    /// assert!(!x.is_some());
166    /// ```
167    pub fn is_some(&self) -> bool {
168        self.occupied.get() != MapCellState::Uninit
169    }
170
171    /// Takes the value out of the `MapCell`, leaving it empty.
172    ///
173    /// Returns `None` if the cell is empty.
174    ///
175    /// To save size, this has no effect and returns `None` in release mode
176    /// if the `MapCell`'s contents are already borrowed.
177    ///
178    /// # Examples
179    ///
180    /// ```
181    /// # use tock_cells::map_cell::MapCell;
182    /// let cell = MapCell::new(1234);
183    /// let x = &cell;
184    /// let y = &cell;
185    ///
186    /// assert_eq!(x.take(), Some(1234));
187    /// assert_eq!(y.take(), None);
188    /// ```
189    ///
190    /// # Panics
191    /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
192    pub fn take(&self) -> Option<T> {
193        debug_assert_not_borrowed!(self);
194        (self.occupied.get() == MapCellState::Init).then(|| {
195            // SAFETY: Since `occupied` is `Init`, `val` is initialized and can be mutated
196            //         behind a shared reference. `result` is therefore initialized.
197            unsafe {
198                let result: MaybeUninit<T> = self.val.get().replace(MaybeUninit::uninit());
199                self.occupied.set(MapCellState::Uninit);
200                result.assume_init()
201            }
202        })
203    }
204
205    /// Puts a value into the `MapCell` without returning the old value.
206    ///
207    /// To save size, this has no effect in release mode if `map` is invoking
208    /// a closure for this cell.
209    ///
210    /// # Panics
211    /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
212    pub fn put(&self, val: T) {
213        debug_assert_not_borrowed!(self);
214        // This will ensure the value as dropped
215        self.replace(val);
216    }
217
218    /// Replaces the contents of the `MapCell`, returning the old value if available.
219    ///
220    /// To save size, this has no effect and returns `None` in release mode
221    /// if the `MapCell`'s contents are already borrowed.
222    ///
223    /// # Panics
224    /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
225    pub fn replace(&self, val: T) -> Option<T> {
226        debug_assert_not_borrowed!(self);
227        let was_occupied = self.occupied.get();
228        match was_occupied {
229            MapCellState::Borrowed => None,
230            MapCellState::Uninit | MapCellState::Init => {
231                self.occupied.set(MapCellState::Init);
232
233                let new_contents = MaybeUninit::new(val);
234                // SAFETY:
235                // - Since `was_occupied` is `Init` or `Uninit`, no `&mut` to the `val`
236                //   exists, meaning it is safe to mutate the `get` pointer.
237                let old_contents_maybe_uninit = unsafe { self.val.get().replace(new_contents) };
238
239                (was_occupied == MapCellState::Init).then(|| {
240                    // SAFETY:
241                    // - If was_occupied is `Init`, `old_contents_maybe_uninit` must be initialized.
242                    unsafe { old_contents_maybe_uninit.assume_init() }
243                })
244            }
245        }
246    }
247
248    /// Calls `closure` with a `&mut` of the contents of the `MapCell`, if available.
249    ///
250    /// The closure is only called if the `MapCell` has a value.
251    /// The state of the `MapCell` is unchanged after the closure completes.
252    ///
253    /// # Re-entrancy
254    ///
255    /// This borrows the contents of the cell while the closure is executing.
256    /// Be careful about calling methods on `&self` inside of that closure!
257    /// To save size, this has no effect in release mode, but if debug assertions
258    /// are enabled, this panics to indicate a likely bug.
259    ///
260    /// # Examples
261    ///
262    /// ```
263    /// # use tock_cells::map_cell::MapCell;
264    /// let cell = MapCell::new(1234);
265    /// let x = &cell;
266    /// let y = &cell;
267    ///
268    /// x.map(|value| {
269    ///     // We have mutable access to the value while in the closure
270    ///     *value += 1;
271    /// });
272    ///
273    /// // After the closure completes, the mutable memory is still in the cell,
274    /// // but potentially changed.
275    /// assert_eq!(y.take(), Some(1235));
276    /// ```
277    ///
278    /// # Panics
279    /// If debug assertions are enabled, this panics if the `MapCell`'s contents are already borrowed.
280    #[inline(always)]
281    pub fn map<F, R>(&self, closure: F) -> Option<R>
282    where
283        F: FnOnce(&mut T) -> R,
284    {
285        debug_assert_not_borrowed!(self);
286        (self.occupied.get() == MapCellState::Init).then(move || {
287            self.occupied.set(MapCellState::Borrowed);
288            // `occupied` is reset to initialized at the end of scope,
289            // even if a panic occurs in `closure`.
290            struct ResetToInit<'a>(&'a Cell<MapCellState>);
291            impl Drop for ResetToInit<'_> {
292                #[inline(always)]
293                fn drop(&mut self) {
294                    self.0.set(MapCellState::Init);
295                }
296            }
297            let _reset_to_init = ResetToInit(&self.occupied);
298            let val_ptr_mut: *mut T = self.val.get().cast::<T>();
299            // SAFETY: The pointer points to memory for a `T`. Creating the
300            // reference is only sound if the value is initialized, which we
301            // ensured by checking that the state is `MapCell::Init`.
302            let val_ref_mut = unsafe { &mut *val_ptr_mut };
303            closure(val_ref_mut)
304        })
305    }
306
307    /// Behaves like `map`, but returns `default` if there is no value present.
308    #[inline(always)]
309    pub fn map_or<F, R>(&self, default: R, closure: F) -> R
310    where
311        F: FnOnce(&mut T) -> R,
312    {
313        self.map(closure).unwrap_or(default)
314    }
315
316    /// Behaves the same as `map`, except the closure is allowed to return
317    /// an `Option`.
318    #[inline(always)]
319    pub fn and_then<F, R>(&self, closure: F) -> Option<R>
320    where
321        F: FnOnce(&mut T) -> Option<R>,
322    {
323        self.map(closure).flatten()
324    }
325
326    /// If a value is present `modify` is called with a borrow.
327    /// Otherwise, the value is set with `G`.
328    #[inline(always)]
329    pub fn modify_or_replace<F, G>(&self, modify: F, mkval: G)
330    where
331        F: FnOnce(&mut T),
332        G: FnOnce() -> T,
333    {
334        if self.map(modify).is_none() {
335            self.put(mkval());
336        }
337    }
338}
339
340#[cfg(test)]
341mod tests {
342    use super::MapCell;
343
344    struct DropCheck<'a> {
345        flag: &'a mut bool,
346    }
347    impl<'a> Drop for DropCheck<'a> {
348        fn drop(&mut self) {
349            *self.flag = true;
350        }
351    }
352
353    #[test]
354    fn test_drop() {
355        let mut dropped_after_drop = false;
356        let mut dropped_after_put = false;
357        {
358            let cell = MapCell::new(DropCheck {
359                flag: &mut dropped_after_put,
360            });
361            cell.put(DropCheck {
362                flag: &mut dropped_after_drop,
363            });
364        }
365        assert!(dropped_after_drop);
366        assert!(dropped_after_put);
367    }
368
369    #[test]
370    fn test_replace() {
371        let a_cell = MapCell::new(1);
372        let old = a_cell.replace(2);
373        assert_eq!(old, Some(1));
374        assert_eq!(a_cell.take(), Some(2));
375        assert_eq!(a_cell.take(), None);
376    }
377
378    #[test]
379    #[should_panic = "`MapCell` accessed while borrowed"]
380    fn test_map_in_borrow() {
381        let cell = MapCell::new(1);
382        let borrow1 = &cell;
383        let borrow2 = &cell;
384        borrow1.map(|_| borrow2.map(|_| ()));
385    }
386
387    #[test]
388    #[should_panic = "`MapCell` accessed while borrowed"]
389    fn test_replace_in_borrow() {
390        let my_cell = MapCell::new(55);
391        my_cell.map(|_ref1: &mut i32| {
392            // Should fail
393            my_cell.replace(56);
394        });
395    }
396
397    #[test]
398    #[should_panic = "`MapCell` accessed while borrowed"]
399    fn test_put_in_borrow() {
400        let my_cell = MapCell::new(55);
401        my_cell.map(|_ref1: &mut i32| {
402            // Should fail
403            my_cell.put(56);
404        });
405    }
406
407    #[test]
408    #[should_panic = "`MapCell` accessed while borrowed"]
409    fn test_get_in_borrow() {
410        let my_cell = MapCell::new(55);
411        my_cell.map(|_ref1: &mut i32| {
412            // Should fail
413            my_cell.get();
414        });
415    }
416}