surpass/layout/

slice_cache.rs

// Copyright 2022 The Fuchsia Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

// IMPORTANT: Upon any code-related modification to this file, please ensure that all commented-out
//            tests that start with `fails_` actually fail to compile *independently* from one
//            another.

use std::marker::PhantomData;
use std::ops::{Bound, Deref, DerefMut, RangeBounds};
use std::ptr::NonNull;
use std::{fmt, hint, mem, slice};

use crossbeam_utils::atomic::AtomicCell;

// `SliceCache` is virtually identical to a `Vec<Range<usize>>` whose range are statically
// guaranteed not to overlap or overflow the initial `slice` that the object has been made with.
//
// This is achieved by forcing the user to produce `Span`s in a closure provided to the constructor
// from a root `Span` that cannot escape the closure.
//
// In `SliceCache::access`, we make sure that the slice doesn't overflow the `len` passed in
// `SliceCache::new` and then save the pointer to the global `ROOT` that is then guarded until the
// `Ref` is dropped.

#[repr(transparent)]
#[derive(Clone, Copy, Eq, PartialEq)]
struct SendNonNull<T> {
    ptr: NonNull<T>,
}

unsafe impl<T> Send for SendNonNull<T> {}

impl<T> From<NonNull<T>> for SendNonNull<T> {
    fn from(ptr: NonNull<T>) -> Self {
        Self { ptr }
    }
}

static ROOT: AtomicCell<Option<SendNonNull<()>>> = AtomicCell::new(None);

/// A [`prim@slice`] wrapper produced by [`SliceCache::access`].
#[repr(C)]
pub struct Slice<'a, T> {
    offset: isize,
    len: usize,
    _phantom: PhantomData<&'a mut [T]>,
}

// Since this type is equivalent to `&mut [T]`, it also implements `Send`.
unsafe impl<'a, T: Send> Send for Slice<'a, T> {}

// Since this type is equivalent to `&mut [T]`, it also implements `Sync`.
unsafe impl<'a, T: Sync> Sync for Slice<'a, T> {}

impl<'a, T> Deref for Slice<'a, T> {
    type Target = [T];

    #[inline]
    fn deref(&self) -> &'a Self::Target {
        let root: NonNull<T> = ROOT.load().unwrap().ptr.cast();

        // `Slice`s should only be dereferences when tainted with the `'s` lifetime from the
        // `SliceCache::access` method. This ensures that the slice that results from derefrencing
        // here will also be constrained by the same lifetime.
        //
        // This also expects the `ROOT` pointer to be correctly set up in `SliceCache::access`.
        unsafe { slice::from_raw_parts(root.as_ptr().offset(self.offset), self.len) }
    }
}

impl<'a, T> DerefMut for Slice<'a, T> {
    #[inline]
    fn deref_mut(&mut self) -> &'a mut Self::Target {
        let root: NonNull<T> = ROOT.load().unwrap().ptr.cast();

        // `Slice`s should only be dereferences when tainted with the `'s` lifetime from the
        // `SliceCache::access` method. This ensures that the slice that results from derefrencing
        // here will also be constrained by the same lifetime.
        //
        // This also expects the `ROOT` pointer to be correctly set up in `SliceCache::access`.
        unsafe { slice::from_raw_parts_mut(root.as_ptr().offset(self.offset), self.len) }
    }
}

impl<T: fmt::Debug> fmt::Debug for Slice<'_, T> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        (**self).fmt(f)
    }
}

/// A marker produced by [`SliceCache`] that ensures that all resulting `Span`s will be mutually
/// non-overlapping.
///
/// # Examples
///
/// ```
/// # use surpass::layout::SliceCache;
/// let mut cache = SliceCache::new(4, |span| {
///     Box::new([span])
/// });
/// ```
#[repr(transparent)]
pub struct Span<'a>(Slice<'a, ()>);

impl<'a> Span<'a> {
    fn from_slice(slice: &Slice<'a, ()>) -> Self {
        Self(Slice { offset: slice.offset, len: slice.len, _phantom: PhantomData })
    }

    /// cache span at `mid`. Analogous to [`slice::split_at`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use surpass::layout::SliceCache;
    /// let mut cache = SliceCache::new(4, |span| {
    ///     let (left, right) = span.split_at(2);
    ///     Box::new([left, right])
    /// });
    /// ```
    #[inline]
    pub fn slice<R: RangeBounds<usize>>(&self, range: R) -> Option<Self> {
        let start = match range.start_bound() {
            Bound::Included(&i) => i,
            Bound::Excluded(&i) => i + 1,
            Bound::Unbounded => 0,
        };
        let end = match range.end_bound() {
            Bound::Included(&i) => i + 1,
            Bound::Excluded(&i) => i,
            Bound::Unbounded => self.0.len,
        };

        (start <= end && end <= self.0.len)
            .then(|| Span(Slice { offset: self.0.offset + start as isize, len: end, ..self.0 }))
    }

    /// cache span at `mid`. Analogous to [`slice::split_at`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use surpass::layout::SliceCache;
    /// let mut cache = SliceCache::new(4, |span| {
    ///     let (left, right) = span.split_at(2);
    ///     Box::new([left, right])
    /// });
    /// ```
    #[inline]
    pub fn split_at(&self, mid: usize) -> (Self, Self) {
        assert!(mid <= self.0.len);

        (
            Span(Slice { len: mid, ..self.0 }),
            Span(Slice { offset: self.0.offset + mid as isize, len: self.0.len - mid, ..self.0 }),
        )
    }

    /// Returns an [Iterator](Chunks) over `chunk_size` elements of thr slice. Analogous to [`slice::chunks`].
    ///
    /// # Examples
    ///
    /// ```
    /// # use surpass::layout::SliceCache;
    /// let mut cache = SliceCache::new(4, |span| {
    ///     span.chunks(2).collect()
    /// });
    /// ```
    #[inline]
    pub fn chunks(self, chunk_size: usize) -> Chunks<'a> {
        Chunks { slice: self.0, size: chunk_size }
    }
}

impl fmt::Debug for Span<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        self.0.offset.fmt(f)?;
        write!(f, "..")?;
        self.0.len.fmt(f)?;

        Ok(())
    }
}

/// An [iterator](std::iter::Iterator) returned by [`Span::chunks`].
pub struct Chunks<'a> {
    slice: Slice<'a, ()>,
    size: usize,
}

impl<'a> Iterator for Chunks<'a> {
    type Item = Span<'a>;

    #[inline]
    fn next(&mut self) -> Option<Self::Item> {
        (self.slice.len > 0).then(|| {
            let span = Span(Slice { len: self.size.min(self.slice.len), ..self.slice });

            self.slice.offset += self.size as isize;
            self.slice.len = self.slice.len.saturating_sub(self.size);

            span
        })
    }
}

impl fmt::Debug for Chunks<'_> {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_struct("Chunks")
            .field("span", &Span::from_slice(&self.slice))
            .field("size", &self.size)
            .finish()
    }
}

/// A [reference] wrapper returned by [`SliceCache::access`].
#[repr(transparent)]
#[derive(Debug)]
pub struct Ref<'a, T: ?Sized>(&'a mut T);

impl<'a, T: ?Sized> Ref<'a, T> {
    pub fn get(&'a mut self) -> &'a mut T {
        self.0
    }
}

impl<T: ?Sized> Deref for Ref<'_, T> {
    type Target = T;

    #[inline]
    fn deref(&self) -> &Self::Target {
        self.0
    }
}

impl<T: ?Sized> DerefMut for Ref<'_, T> {
    #[inline]
    fn deref_mut(&mut self) -> &mut Self::Target {
        self.0
    }
}

impl<T: ?Sized> Drop for Ref<'_, T> {
    #[inline]
    fn drop(&mut self) {
        ROOT.store(None);
    }
}

/// A cache of non-overlapping mutable sub-slices of that enforces lifetimes dynamically.
///
/// This type is useful when you have to give up on the mutable reference to a slice but need
/// a way to cache mutable sub-slices deriving from it.
///
/// # Examples
///
/// ```
/// # use surpass::layout::SliceCache;
/// let mut array = [1, 2, 3];
///
/// let mut cache = SliceCache::new(3, |span| {
///     let (left, right) = span.split_at(1);
///     Box::new([left, right])
/// });
///
/// for slice in cache.access(&mut array).unwrap().iter_mut() {
///     for val in slice.iter_mut() {
///         *val += 1;
///     }
/// }
///
/// assert_eq!(array, [2, 3, 4]);
/// ```
pub struct SliceCache {
    len: usize,
    slices: Box<[Slice<'static, ()>]>,
}

impl SliceCache {
    /// Creates a new slice cache by storing sub-spans created from a root passed to the closure
    /// `f`. `len` is the minimum slice length that can then be passed to [`access`](Self::access).
    ///
    /// # Examples
    ///
    /// ```
    /// # use surpass::layout::SliceCache;
    /// let mut cache = SliceCache::new(3, |span| {
    ///     let (left, right) = span.split_at(1);
    ///     // All returned sub-spans stem from the span passed above.
    ///     Box::new([left, right])
    /// });
    /// ```
    #[inline]
    pub fn new<F>(len: usize, f: F) -> Self
    where
        F: Fn(Span<'_>) -> Box<[Span<'_>]> + 'static,
    {
        let span = Span(Slice { offset: 0, len, _phantom: PhantomData });

        // `Span<'_>` is transparent over `Slice<'_, ()>`. Since the `'_` above is used just to
        // trap the span inside the closure, transmuting to `Slice<'static, ()>` does not make any
        // difference.
        Self { len, slices: unsafe { mem::transmute(f(span)) } }
    }

    /// Accesses the `slice` by returning all the sub-slices equivalent to the previously created
    /// [spans](Span) in the closure passed to [`new`](Self::new).
    ///
    /// If the `slice` does not have a length at least as large as the one passed to
    /// [`new`](Self::new), this function returns `None`.
    ///
    /// Note: this method should not be called concurrently with any other `access` calls since it
    /// will wait for the previously returned [`Ref`] to be dropped.
    ///
    /// # Examples
    ///
    /// ```
    /// # use surpass::layout::SliceCache;
    /// let mut array = [1, 2, 3];
    ///
    /// let mut cache = SliceCache::new(3, |span| {
    ///     let (left, right) = span.split_at(1);
    ///     Box::new([left, right])
    /// });
    ///
    /// let mut copy = array;
    /// let skipped_one = cache.access(&mut array).unwrap();
    ///
    /// assert_eq!(&*skipped_one[1], &copy[1..]);
    /// ```
    #[inline]
    pub fn access<'c, 's, T>(&'c mut self, slice: &'s mut [T]) -> Option<Ref<'c, [Slice<'s, T>]>> {
        if slice.len() >= self.len {
            while ROOT
                .compare_exchange(
                    None,
                    Some(NonNull::new(slice.as_mut_ptr()).unwrap().cast().into()),
                )
                .is_err()
            {
                // This spin lock here is mostly for being able to run tests in parallel. Being
                // able to render to `forma::Composition`s in parallel is currently not supported
                // and might poor performance due to priority inversion.
                hint::spin_loop();
            }

            // Generic `Slice<'static, ()>` are transmuted to `Slice<'s, T>`, enforcing the
            // original `slice`'s lifetime. Since slices are simply pairs of `(offset, len)`,
            // transmuting `()` to `T` relies on the `ROOT` being set up above with the correct pointer.
            return Some(unsafe { mem::transmute(&mut *self.slices) });
        }

        None
    }

    #[cfg(test)]
    fn try_access<'c, 's, T>(&'c mut self, slice: &'s mut [T]) -> Option<Ref<'c, [Slice<'s, T>]>> {
        if slice.len() >= self.len
            && ROOT
                .compare_exchange(
                    None,
                    Some(NonNull::new(slice.as_mut_ptr()).unwrap().cast().into()),
                )
                .is_ok()
        {
            // Generic `Slice<'static, ()>` are transmuted to `Slice<'s, T>`, enforcing the
            // original `slice`'s lifetime. Since slices are simply pairs of `(offset, len)`,
            // transmuting `()` to `T` relies on the `ROOT` being set up above with the correct pointer.
            return Some(unsafe { mem::transmute(&mut *self.slices) });
        }

        None
    }
}

impl fmt::Debug for SliceCache {
    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
        f.debug_list().entries(self.slices.iter().map(Span::from_slice)).finish()
    }
}

#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn split_at() {
        let mut cache = SliceCache::new(5, |span| {
            let (left, right) = span.split_at(2);
            Box::new([left, right])
        });
        let mut array = [1, 2, 3, 4, 5];

        for slice in cache.access(&mut array).unwrap().iter_mut() {
            for val in slice.iter_mut() {
                *val += 1;
            }
        }

        assert_eq!(array, [2, 3, 4, 5, 6]);
    }

    #[test]
    fn chunks() {
        let mut cache = SliceCache::new(5, |span| span.chunks(2).collect());
        let mut array = [1, 2, 3, 4, 5];

        for slice in cache.access(&mut array).unwrap().iter_mut() {
            for val in slice.iter_mut() {
                *val += 1;
            }
        }

        assert_eq!(array, [2, 3, 4, 5, 6]);
    }

    #[test]
    fn ref_twice() {
        let mut cache = SliceCache::new(5, |span| {
            let (left, right) = span.split_at(2);
            Box::new([left, right])
        });
        let mut array = [1, 2, 3, 4, 5];

        for slice in cache.access(&mut array).unwrap().iter_mut() {
            for val in slice.iter_mut() {
                *val += 1;
            }
        }

        for slice in cache.access(&mut array).unwrap().iter_mut() {
            for val in slice.iter_mut() {
                *val += 1;
            }
        }

        assert_eq!(array, [3, 4, 5, 6, 7]);
    }

    #[test]
    fn access_twice() {
        let mut cache0 = SliceCache::new(5, |span| Box::new([span]));
        let mut cache1 = SliceCache::new(5, |span| Box::new([span]));

        let mut array0 = [1, 2, 3, 4, 5];
        let mut array1 = [1, 2, 3, 4, 5];

        let _slices = cache0.access(&mut array0).unwrap();

        assert!(matches!(cache1.try_access(&mut array1), None));
    }

    // #[test]
    // fn fails_due_to_too_short_lifetime() {
    //     let mut cache = SliceCache::new(16, |span| Box::new([span]));

    //     let slices = {
    //         let mut buffer = [0u8; 16];

    //         let slices = cache.access(&mut buffer).unwrap();
    //         let slice = &mut *slices[0];

    //         slice
    //     };

    //     &slices[0];
    // }

    // #[test]
    // fn fails_due_to_mixed_spans() {
    //     SliceCache::new(16, |span0| {
    //         let (left, right) = span0.split_at(2);

    //         SliceCache::new(4, |span1| {
    //             Box::new([left])
    //         });

    //         Box::new([right])
    //     });
    // }

    // #[test]
    // fn fails_due_to_t_not_being_send() {
    //     use std::rc::Rc;

    //     use rayon::prelude::*;

    //     let mut array = [Rc::new(1), Rc::new(2), Rc::new(3)];

    //     let mut cache = SliceCache::new(3, |span| {
    //         let (left, right) = span.split_at(1);
    //         Box::new([left, right])
    //     });

    //     cache.access(&mut array).unwrap().par_iter_mut().for_each(|slice| {
    //         for val in slice.iter_mut() {
    //             *val += 1;
    //         }
    //     });
    // }

    // #[test]
    // fn fails_to_export_span() {
    //     let mut leaked = None;

    //     let mut cache0 = SliceCache::new(1, |span| {
    //         leaked = Some(span);
    //         Box::new([])
    //     });

    //     let mut cache1 = SliceCache::new(1, |span| {
    //         Box::new([leaked.take().unwrap()])
    //     });
    // }

    // #[test]
    // fn fails_due_to_dropped_slice() {
    //     let mut array = [1, 2, 3];

    //     let mut cache = SliceCache::new(3, |span| {
    //         let (left, right) = span.split_at(1);
    //         Box::new([left, right])
    //     });

    //     let slices = cache.access(&mut array).unwrap();

    //     std::mem::drop(array);

    //     slices[0][0] = 0;
    // }
}