layout 0.1.0

#![cfg_attr(not(feature = "std"), no_std)]
//! This crate provides a custom derive (`#[derive(SOA)]`) to
//! automatically generate code from a given struct `T` that allow to replace
//! `Vec<T>` with a struct of arrays. For example, the following code
//!
//! ```
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! #[derive(SOA)]
//! pub struct Cheese {
//!     pub smell: f64,
//!     pub color: (f64, f64, f64),
//!     pub with_mushrooms: bool,
//!     pub name: String,
//! }
//! # }
//! ```
//!
//! will generate a `CheeseVec` struct that looks like this:
//!
//! ```
//! pub struct CheeseVec {
//!     pub smell: Vec<f64>,
//!     pub color: Vec<(f64, f64, f64)>,
//!     pub with_mushrooms: Vec<bool>,
//!     pub name: Vec<String>,
//! }
//! ```
//!
//! It will also generate the same functions that a `Vec<Cheese>` would have,
//! and a few helper structs: `CheeseSlice`, `CheeseSliceMut`, `CheeseRef` and
//! `CheeseRefMut` corresponding respectively to `&[Cheese]`, `&mut [Cheese]`,
//! `&Cheese` and `&mut Cheese`.
//!
//! # How to use it
//!
//! Add `#[derive(SOA)]` to each struct you want to derive a struct of
//! array version. If you need the helper structs to derive additional traits
//! (such as `Debug` or `PartialEq`), you can add an attribute `#[layout =
//! "Debug, PartialEq"]` to the struct declaration.
//!
//! ```
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! #[derive(Debug, PartialEq, SOA)]
//! #[layout(Debug, PartialEq)]
//! pub struct Cheese {
//!     pub smell: f64,
//!     pub color: (f64, f64, f64),
//!     pub with_mushrooms: bool,
//!     pub name: String,
//! }
//! # }
//! ```
//!
//! If you want to add attribute to a specific generated struct(such as
//! `#[cfg_attr(test, derive(PartialEq))]` on `CheeseVec`), you can add an
//! attribute `#[soa_attr(Vec, cfg_attr(test, derive(PartialEq)))]` to the
//! struct declaration.
//!
//! ```
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! #[derive(Debug, PartialEq, SOA)]
//! #[soa_attr(Vec, cfg_attr(test, derive(PartialEq)))]
//! pub struct Cheese {
//!     pub smell: f64,
//!     pub color: (f64, f64, f64),
//!     pub with_mushrooms: bool,
//!     pub name: String,
//! }
//! # }
//! ```
//!
//! Mappings for first argument of ``soa_attr`` to the generated struct for
//! ``Cheese``:
//! * `Vec` => `CheeseVec`
//! * `Slice` => `CheeseSlice`
//! * `SliceMut` => `CheeseSliceMut`
//! * `Ref` => `CheeseRef`
//! * `RefMut` => `CheeseRefMut`
//! * `Ptr` => `CheesePtr`
//! * `PtrMut` => `CheesePtrMut`
//!
//! # Usage and API
//!
//! All the generated code have some generated documentation with it, so you
//! should be able to use `cargo doc` on your crate and see the documentation
//! for all the generated structs and functions.
//!
//! Most of the time, you should be able to replace `Vec<Cheese>` by
//! `CheeseVec`, with exception of code using direct indexing in the vector and
//! a few other caveats listed below.
//!
//! ## Caveats and limitations
//!
//! `Vec<T>` functionalities rely a lot on references and automatic *deref*
//! feature, for getting function from `[T]` and indexing. But the SoA vector
//! (let's call it `CheeseVec`, generated from the `Cheese` struct) generated by
//! this crate can not implement `Deref<Target=CheeseSlice>`, because `Deref` is
//! required to return a reference, and `CheeseSlice` is not a reference. The
//! same applies to `Index` and `IndexMut` trait, that can not return
//! `CheeseRef/CheeseRefMut`.
//!
//! This means that we cannot index into a `CheeseVec`, and that a few
//! functions are duplicated, or require a call to `as_ref()/as_mut()` to change
//! the type used.
//!
//! # Iteration
//!
//! It is possible to iterate over the values in a `CheeseVec`
//!
//! ```no_run
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! # #[derive(Debug, PartialEq, SOA)]
//! # pub struct Cheese {
//! #     pub smell: f64,
//! #     pub color: (f64, f64, f64),
//! #     pub with_mushrooms: bool,
//! #     pub name: String,
//! # }
//! # impl Cheese { fn new(name: &str) -> Cheese { unimplemented!() } }
//! # fn main() {
//! let mut vec = CheeseVec::new();
//! vec.push(Cheese::new("stilton"));
//! vec.push(Cheese::new("brie"));
//!
//! for cheese in vec.iter() {
//!     // when iterating over a CheeseVec, we load all members from memory
//!     // in a CheeseRef
//!     let typeof_cheese: CheeseRef = cheese;
//!     println!(
//!         "this is {}, with a smell power of {}",
//!         cheese.name, cheese.smell
//!     );
//! }
//! # }
//! # }
//! ```
//!
//! One of the main advantage of the SoA layout is to be able to only load some
//! fields from memory when iterating over the vector. In order to do so, one
//! can manually pick the needed fields:
//!
//! ```no_run
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! # #[derive(Debug, PartialEq, SOA)]
//! # pub struct Cheese {
//! #     pub smell: f64,
//! #     pub color: (f64, f64, f64),
//! #     pub with_mushrooms: bool,
//! #     pub name: String,
//! # }
//! # impl Cheese { fn new(name: &str) -> Cheese { unimplemented!() } }
//! # fn main() {
//! # let mut vec = CheeseVec::new();
//! # vec.push(Cheese::new("stilton"));
//! # vec.push(Cheese::new("brie"));
//! for name in &vec.name {
//!     // We get references to the names
//!     let typeof_name: &String = name;
//!     println!("got cheese {}", name);
//! }
//! # }
//! # }
//! ```
//!
//! In order to iterate over multiple fields at the same time, one can use the
//! [soa_zip!](macro.soa_zip.html) macro.
//!
//! ```no_run
//! # #[macro_use] extern crate layout;
//! # mod cheese {
//! # #[derive(Debug, PartialEq, SOA)]
//! # pub struct Cheese {
//! #     pub smell: f64,
//! #     pub color: (f64, f64, f64),
//! #     pub with_mushrooms: bool,
//! #     pub name: String,
//! # }
//! # impl Cheese { fn new(name: &str) -> Cheese { unimplemented!() } }
//! # fn main() {
//! # let mut vec = CheeseVec::new();
//! # vec.push(Cheese::new("stilton"));
//! # vec.push(Cheese::new("brie"));
//! for (name, smell, color) in soa_zip!(&mut vec, [name, mut smell, color]) {
//!     println!("this is {}, with color {:#?}", name, color);
//!     // smell is a mutable reference
//!     *smell += 1.0;
//! }
//! # }
//! # }
//! ```
//!
//! ## Nested Struct of Arrays
//!
//! In order to nest a struct of arrays inside another struct of arrays, one can
//! use the `#[nested_soa]` attribute.
//!
//! For example, the following code
//!
//! ```
//! # mod cheese {
//! # use layout::SOA;
//! #[derive(SOA)]
//! pub struct Point {
//!     x: f32,
//!     y: f32,
//! }
//! #[derive(SOA)]
//! pub struct Particle {
//!     #[nested_soa]
//!     point: Point,
//!     mass: f32,
//! }
//! # }
//! ```
//!
//! will generate structs that looks like this:
//!
//! ```
//! pub struct PointVec {
//!     x: Vec<f32>,
//!     y: Vec<f32>,
//! }
//! pub struct ParticleVec {
//!     point: PointVec, // rather than Vec<Point>
//!     mass: Vec<f32>,
//! }
//! ```
//!
//! All helper structs will be also nested, for example `PointSlice` will be
//! nested in `ParticleSlice`.
//!
//! # Use in a generic context
//!
//! `SOA` does not provide a set of common operations by default. Thus if you
//! wanted to use a `SOA` type in a generic context, there is no way to
//! guarantee to the type system that any methods are available.
//!
//! This will also generate implementations of [`SoAVec`], [`SoASlice`], and
//! [`SoASliceMut`] for the respective `Vec`, `Slice` and `SliceMut` types.
//! These rely on GATs, and so require Rust 1.65 or newer.
//!
//! ```ignore
//! # mod cheese {
//! # use layout::{SOA, prelude::*};
//! #[derive(SOA)]
//! pub struct Point {
//!     x: f32,
//!     y: f32,
//! }
//!
//! fn get_num_items<T: SOA, V: SoAVec<T>>(values: &V) -> usize {
//!     values.len()
//! }
//! # }
//! ```

extern crate alloc;
#[allow(unused_imports)]
use alloc::{string::String, vec::Vec};

// The proc macro is implemented in layout_internal, and re-exported by
// this crate. This is because a single crate can not define both a proc
// macro and a macro_rules macro.
pub use layout_internal::soa_impl;
pub use layout_internal::SOA;

pub mod bitpack;
pub mod column;
pub mod compact;

// Re-exported for use in generated code. Not intended for direct use.
#[doc(hidden)]
pub use alloc::vec::Drain;

// Re-exported so generated code can use `::layout::branches::likely` /
// `unlikely` without downstream crates depending on `branches` themselves.
#[doc(hidden)]
pub use branches;
/// Owning, length-locked storage for one plain struct-of-arrays column.
///
/// Generated `Vec` types store each plain field as a `Column<T>` (which
/// dereferences to `[T]`) instead of a bare `Vec<T>`, so that safe code
/// cannot change one column's length independently of the others. See the
/// [`column`] module for details.
pub use column::Column;
/// Trait implemented by types that can be stored in a compact (bit-packed)
/// column: `bool` and any fieldless enum that derives `CompactRepr`.
pub use compact::CompactRepr;
// Visible (not hidden) re-exports: generated struct fields and method
// signatures name these types at the crate root (e.g. a compact column is
// a `layout::CompactVec<T>` field), so this is their documented home.
pub use compact::{
    Compact, CompactBool, CompactChunks, CompactChunksExact,
    CompactChunksExactMut, CompactChunksMut, CompactDrain, CompactIntoIter,
    CompactIter, CompactIterMut, CompactPtr, CompactPtrMut, CompactRefMut,
    CompactSlice, CompactSliceMut, CompactVec,
};
/// Derive macro implementing [`CompactRepr`] for a fieldless enum.
///
/// Requires an unsigned `#[repr(uN)]`. Storage width is sized by the
/// largest discriminant (`1`/`2`/`4`/`8`/`16` bits). The trait and this
/// derive share the name `CompactRepr` in the type and macro namespaces
/// respectively (like `serde::Serialize`), so `#[derive(CompactRepr)]` and
/// `impl CompactRepr` both resolve at the crate root.
pub use layout_internal::CompactRepr;
// Sorting helpers used by the macro-generated code. Inlining the inverse
// permutation here (instead of depending on the `permutation` crate) keeps
// this crate `no_std` + `alloc` only — the `permutation` crate needs `std`.
#[doc(hidden)]
pub fn __invert_permutation(argsort: &[usize]) -> Vec<usize> {
    // `dest[src]` = the sorted position of the element currently at `src`.
    // `argsort[pos] = src`, so invert by assigning `dest[argsort[pos]] = pos`.
    // `usize::MAX` doubles as the "not yet assigned" sentinel: a slice of
    // `usize::MAX` elements cannot exist, so no valid position collides with
    // it. Rejecting out-of-range and duplicate sources here guarantees the
    // returned `dest` is a genuine permutation of `0..argsort.len()`.
    let len = argsort.len();
    let mut dest = alloc::vec![usize::MAX; len];
    for (pos, &src) in argsort.iter().enumerate() {
        assert!(src < len, "index {src} out of bounds for length {len}");
        assert!(
            dest[src] == usize::MAX,
            "duplicate index {src}: indices must form a permutation"
        );
        dest[src] = pos;
    }
    dest
}

/// A bit-packed visited set for the in-place permutation walkers: 8x smaller
/// than a `Vec<bool>`, so the random-access cycle walk touches fewer cache
/// lines. Public (hidden) so generated code can allocate one scratch set and
/// reuse it across every column of a sort.
#[doc(hidden)]
pub struct VisitedBits {
    words: Vec<usize>,
}

impl VisitedBits {
    const W: usize = usize::BITS as usize;

    #[inline]
    pub fn new(len: usize) -> Self {
        // `div_ceil` is not available at the crate's MSRV (1.71).
        Self {
            words: alloc::vec![0usize; (len + Self::W - 1) / Self::W],
        }
    }

    #[inline]
    pub fn test(&self, i: usize) -> bool {
        (self.words[i / Self::W] >> (i % Self::W)) & 1 != 0
    }

    #[inline]
    pub fn set(&mut self, i: usize) {
        self.words[i / Self::W] |= 1 << (i % Self::W);
    }

    #[inline]
    pub fn clear(&mut self) {
        self.words.fill(0);
    }
}

/// Validate that `dest` is a permutation of `0..len`: matching length, every
/// index in range, no duplicates. Panics otherwise. Returns the (fully set)
/// visited bitmap so the caller can reuse the allocation as cycle-walk
/// scratch for every column.
#[doc(hidden)]
pub fn __validate_permutation(dest: &[usize], len: usize) -> VisitedBits {
    // The unchecked cycle-walks `ptr::read` elements out of the columns, so
    // every precondition must hold *before* any of them starts: a
    // wrong-length or non-permutation `dest` would otherwise panic mid-cycle
    // while a bitwise duplicate of a non-`Copy` element is live (double drop
    // on unwind), or walk a cycle that never closes.
    assert!(
        dest.len() == len,
        "permutation length {} does not match slice length {len}",
        dest.len()
    );
    let mut visited = VisitedBits::new(len);
    for &d in dest {
        assert!(d < len, "index {d} out of bounds for length {len}");
        assert!(
            !visited.test(d),
            "duplicate index {d}: indices must form a permutation"
        );
        visited.set(d);
    }
    visited
}

/// Invert an argsort into a destination permutation without validating it:
/// `argsort[pos] = src` becomes `dest[src] = pos`. The caller must pass a
/// reordered `0..len` sequence (as produced by sorting a collected range);
/// out-of-range sources panic on the (checked) `dest` write.
#[doc(hidden)]
pub fn __argsort_to_dest(argsort: &[usize]) -> Vec<usize> {
    let mut dest = alloc::vec![0usize; argsort.len()];
    for (pos, &src) in argsort.iter().enumerate() {
        dest[src] = pos;
    }
    dest
}

/// As [`__argsort_to_dest`], reading the source index from the second slot
/// of pre-computed `(key, index)` pairs.
#[doc(hidden)]
pub fn __keyed_to_dest<K>(keyed: &[(K, usize)]) -> Vec<usize> {
    let mut dest = alloc::vec![0usize; keyed.len()];
    for (pos, (_, src)) in keyed.iter().enumerate() {
        dest[*src] = pos;
    }
    dest
}

/// Apply a destination permutation in place without re-validating it:
/// `dest[i]` is the index the element at `i` should move to. Used by
/// generated code for plain `&mut [T]` columns, after one composite-level
/// validation covers every column. Follows each cycle moving values (works
/// for non-`Copy` `T`).
///
/// # Safety
///
/// `dest` must be a permutation of `0..slice.len()` (equal length, every
/// index in range, no duplicates) and `visited` must have been created with
/// capacity for at least `slice.len()` bits. A non-permutation `dest` walks
/// out of bounds or duplicates non-`Copy` elements.
#[doc(hidden)]
pub unsafe fn __apply_permutation_inplace_unchecked<T>(
    slice: &mut [T],
    dest: &[usize],
    visited: &mut VisitedBits,
) {
    let len = slice.len();
    visited.clear();
    let base = slice.as_mut_ptr();
    for start in 0..len {
        if visited.test(start) {
            continue;
        }
        visited.set(start);
        let mut current = start;
        // SAFETY: `current` walks the cycle start -> dest[start] -> ...; every
        // index is visited exactly once and is `< len` per the caller's
        // permutation contract. `temp` always holds the value that belongs at
        // the next slot; we move it in and keep the displaced value, closing
        // the cycle by writing into `start` when we return to it. No panic
        // can occur inside this block, so no slot is left uninitialized.
        unsafe {
            let mut temp = core::ptr::read(base.add(start));
            loop {
                let next = *dest.get_unchecked(current);
                if next == start {
                    core::ptr::write(base.add(start), temp);
                    break;
                }
                temp = core::ptr::replace(base.add(next), temp);
                visited.set(next);
                current = next;
            }
        }
    }
}

/// Cursor advance for the generated single-counter iterators.
///
/// A generated iterator holds one remaining-length counter plus one
/// sub-iterator per column; `next` checks the counter once and then advances
/// every column through this trait, so each element costs a single bounds
/// decision regardless of column count (a zip chain would re-check every
/// column). Implemented for `slice::Iter`/`IterMut`, the compact column
/// iterators, and the generated iterators themselves (nested SoA fields).
#[doc(hidden)]
pub trait SoACursor {
    type Item;
    /// Yield the next front element without checking for exhaustion.
    ///
    /// # Safety
    /// The total number of `cursor_next` and `cursor_next_back` calls must
    /// not exceed the cursor's initial length.
    unsafe fn cursor_next(&mut self) -> Self::Item;
    /// Yield the next back element without checking for exhaustion.
    ///
    /// # Safety
    /// As [`cursor_next`](Self::cursor_next).
    unsafe fn cursor_next_back(&mut self) -> Self::Item;
}

impl<'a, T> SoACursor for core::slice::Iter<'a, T> {
    type Item = &'a T;
    #[inline(always)]
    unsafe fn cursor_next(&mut self) -> &'a T {
        // SAFETY: the caller guarantees the iterator is not exhausted, so the
        // `None` arm is unreachable and its check folds away.
        unsafe { self.next().unwrap_unchecked() }
    }
    #[inline(always)]
    unsafe fn cursor_next_back(&mut self) -> &'a T {
        // SAFETY: as above.
        unsafe { self.next_back().unwrap_unchecked() }
    }
}

impl<'a, T> SoACursor for core::slice::IterMut<'a, T> {
    type Item = &'a mut T;
    #[inline(always)]
    unsafe fn cursor_next(&mut self) -> &'a mut T {
        // SAFETY: as for `slice::Iter`.
        unsafe { self.next().unwrap_unchecked() }
    }
    #[inline(always)]
    unsafe fn cursor_next_back(&mut self) -> &'a mut T {
        // SAFETY: as for `slice::Iter`.
        unsafe { self.next_back().unwrap_unchecked() }
    }
}

/// Any struct derived by SOA will auto impl this trait. You can use
/// `<Cheese as SOA>::Type` instead of the explicit named type `CheeseVec`,
/// which helps in generic programming where the generated struct is
/// expressed as `<T as SOA>::Type`.
pub trait SOA {
    type Type;
}

/// Any struct derived by SOA will auto impl this trait.
///
/// Useful for generic programming and implementation of attribute `nested_soa`.
///
/// `CheeseVec::iter(&'a self)` returns an iterator which has a type `<Cheese as
/// SoAIter<'a>>::Iter`
///
/// `CheeseVec::iter_mut(&mut 'a self)` returns an iterator which has a type
/// `<Cheese as SoAIter<'a>>::IterMut`
pub trait SoAIter<'a> {
    type Ref;
    type RefMut;
    type Iter: 'a + Iterator<Item = Self::Ref>;
    type IterMut: 'a + Iterator<Item = Self::RefMut>;
}

mod private_soa_indexes {
    // From [`core::slice::SliceIndex`](https://doc.rust-lang.org/std/slice/trait.SliceIndex.html) code.
    // Limits the types that may implement the SoA index traits.
    // It's also helpful to have the exhaustive list of all accepted types.

    use ::core::ops;

    pub trait Sealed {}

    impl Sealed for usize {} // [a]
    impl Sealed for ops::Range<usize> {} // [a..b]
    impl Sealed for ops::RangeTo<usize> {} // [..b]
    impl Sealed for ops::RangeFrom<usize> {} // [a..]
    impl Sealed for ops::RangeFull {} // [..]
    impl Sealed for ops::RangeInclusive<usize> {} // [a..=b]
    impl Sealed for ops::RangeToInclusive<usize> {} // [..=b]
}

/// Helper trait used for indexing operations.
/// Inspired by [`core::slice::SliceIndex`](https://doc.rust-lang.org/std/slice/trait.SliceIndex.html).
pub trait SoAIndex<T>: private_soa_indexes::Sealed {
    /// The output for the non-mutable functions
    type RefOutput;

    /// Returns the reference output in this location if in bounds, `None`
    /// otherwise.
    fn get(self, soa: T) -> Option<Self::RefOutput>;
    /// Returns the reference output in this location without performing any
    /// bounds check.
    ///
    /// # Safety
    /// The index must be in bounds.
    unsafe fn get_unchecked(self, soa: T) -> Self::RefOutput;
    /// Returns the reference output in this location. Panics if it is not in
    /// bounds.
    fn index(self, soa: T) -> Self::RefOutput;
}

/// Helper trait used for indexing operations returning mutable references.
/// Inspired by [`core::slice::SliceIndex`](https://doc.rust-lang.org/std/slice/trait.SliceIndex.html).
pub trait SoAIndexMut<T>: private_soa_indexes::Sealed {
    /// The output for the mutable functions
    type MutOutput;

    /// Returns the mutable reference output in this location if in bounds,
    /// `None` otherwise.
    fn get_mut(self, soa: T) -> Option<Self::MutOutput>;
    /// Returns the mutable reference output in this location without performing
    /// any bounds check.
    ///
    /// # Safety
    /// The index must be in bounds.
    unsafe fn get_unchecked_mut(self, soa: T) -> Self::MutOutput;
    /// Returns the mutable reference output in this location. Panics if it is
    /// not in bounds.
    fn index_mut(self, soa: T) -> Self::MutOutput;
}

/// Create an iterator over multiple fields in a Struct of array style vector.
///
/// This macro takes two main arguments: the array/slice container, and a list
/// of fields to use, inside square brackets. The iterator will give references
/// to the fields, which can be mutable references if the field name is prefixed
/// with `mut`.
///
/// ```
/// # #[macro_use] extern crate layout;
/// # mod cheese {
/// #[derive(SOA)]
/// struct Cheese {
///     size: f64,
///     mass: f64,
///     smell: f64,
///     name: String,
/// }
///
/// # fn main() {
/// let mut vec = CheeseVec::new();
/// // fill the vector
///
/// // Iterate over immutable references
/// for (mass, size, name) in soa_zip!(&vec, [mass, size, name]) {
///     println!("got {} kg and {} cm of {}", mass, size, name);
/// }
///
/// // Iterate over mutable references
/// for (mass, name) in soa_zip!(&mut vec, [mut mass, name]) {
///     println!("got {} kg of {}, eating 1 kg", mass, name);
///     *mass -= 1.0;
/// }
/// # }
/// # }
/// ```
///
/// The iterator can also work with external iterators. In this case, the
/// iterator will yield elements until any of the fields or one external
/// iterator returns None.
///
/// ```
/// # #[macro_use] extern crate layout;
/// # mod cheese {
/// # #[derive(SOA)]
/// # struct Cheese {
/// #     size: f64,
/// #     mass: f64,
/// #     smell: f64,
/// #     name: String,
/// # }
/// # #[derive(Debug)] struct Cellar;
/// # fn main() {
/// let mut vec = CheeseVec::new();
/// let mut cellars = Vec::<Cellar>::new();
///
/// for (name, mass, cellar) in soa_zip!(&vec, [name, mass], &cellars) {
///     println!("we have {} kg of {} in {:#?}", mass, name, cellar);
/// }
/// # }
/// # }
/// ```
#[macro_export]
macro_rules! soa_zip {
    ($self: expr, [$($fields: tt)*] $(, $external: expr)* $(,)*) => {{
        let this = $self;
        $crate::soa_zip_impl!(@munch this, {$($fields)*} -> [] $($external ,)*)
    }};
}

/// This trait is automatically implemented by the relevant generated by
/// [`SOA`].
///
/// Links a [`SOA`] type to its raw pointer types, which is useful for generic
/// programming.
pub trait SoAPointers {
    /// The immutable pointer type for an SoA type
    type Ptr;
    /// The mutable pointer type for an SoA type
    type MutPtr;
}

mod generics {
    use super::*;

    /**
    The interface for the `Slice` immutable slice struct-of-arrays type.
    */
    pub trait SoASlice<T: SOA> {
        /// The type that elements will be proxied with as
        type Ref<'t>
        where
            Self: 't;

        /// The type representing immutable slices of elements
        type Slice<'t>: SoASlice<T>
            + IntoSoAIter<'t, T, Ref<'t> = Self::Ref<'t>>
        where
            Self: 't;

        /// The type used for iteration over [`Self::Ref`]
        type Iter<'t>: Iterator<Item = Self::Ref<'t>>
        where
            Self: 't;

        /// The raw pointer type interface
        type Ptr;

        /// Returns the number of elements in the arrays
        fn len(&self) -> usize;

        /// Returns true if the arrays has a length of 0.
        fn is_empty(&self) -> bool;

        /// Create an immutable slice of the arrays
        fn as_slice(&self) -> Self::Slice<'_>;

        /// Create a slice of this vector matching the given `range`. This
        /// is analogous to `Index<Range<usize>>`.
        fn slice<'c, 'a: 'c>(
            &'c self,
            index: impl core::ops::RangeBounds<usize>,
        ) -> Self::Slice<'c>
        where
            Self: 'a;

        /// Analogous to [`slice::get()`](https://doc.rust-lang.org/std/primitive.slice.html#method.get)
        fn get(&self, index: usize) -> Option<Self::Ref<'_>>;

        /// Analogous to [`core::ops::Index::index()`] for `usize`
        fn index(&self, index: usize) -> Self::Ref<'_>;

        /// Create an immutable iterator
        fn iter(&self) -> Self::Iter<'_>;

        /// Analogous to [`slice::first()`](https://doc.rust-lang.org/std/primitive.slice.html#method.first)
        fn first(&self) -> Option<Self::Ref<'_>> {
            self.get(0)
        }

        /// Analogous to [`slice::last()`](https://doc.rust-lang.org/std/primitive.slice.html#method.last)
        fn last(&self) -> Option<Self::Ref<'_>> {
            self.get(self.len().saturating_sub(1))
        }

        /// Obtain a `const` pointer type for this data
        fn as_ptr(&self) -> Self::Ptr;
    }

    /**
    The interface for the `SliceMut` mutable slice struct-of-arrays type. A generalization of [`SoASlice`]
    whose methods can modify elements of the arrays
    */
    pub trait SoASliceMut<T: SOA> {
        /// The type that elements will be proxied with as
        type Ref<'t>
        where
            Self: 't;

        /// The type representing immutable slices of elements
        type Slice<'t>: SoASlice<T>
            + IntoSoAIter<'t, T, Ref<'t> = Self::Ref<'t>>
        where
            Self: 't;

        /// The type used for iteration over [`Self::Ref`]
        type Iter<'t>: Iterator<Item = Self::Ref<'t>>
        where
            Self: 't;

        /// The const pointer type interface
        type Ptr;

        /// The type that elements will be proxied with as when mutable
        type RefMut<'t>
        where
            Self: 't;

        /// The type representing mutable slices of elements
        type SliceMut<'t>: SoASliceMut<T>
        where
            Self: 't;

        /// The type used for iteration over [`Self::RefMut`]
        type IterMut<'t>: Iterator<Item = Self::RefMut<'t>>
        where
            Self: 't;

        /// The mut pointer type interface
        type PtrMut;

        /// Returns the number of elements in the arrays
        fn len(&self) -> usize;

        /// Returns true if the arrays has a length of 0.
        fn is_empty(&self) -> bool;

        /// Create an immutable slice of the arrays
        fn as_slice(&self) -> Self::Slice<'_>;

        /// Create a slice of this vector matching the given `range`. This
        /// is analogous to `Index<Range<usize>>`.
        fn slice<'c, 'a: 'c>(
            &'c self,
            index: impl core::ops::RangeBounds<usize>,
        ) -> Self::Slice<'c>
        where
            Self: 'a;

        /// Analogous to [`slice::get()`](https://doc.rust-lang.org/std/primitive.slice.html#method.get)
        fn get(&self, index: usize) -> Option<Self::Ref<'_>>;

        /// Analogous to [`core::ops::Index::index()`] for `usize`
        fn index(&self, index: usize) -> Self::Ref<'_>;

        /// Create an immutable iterator
        fn iter(&self) -> Self::Iter<'_>;

        /// Analogous to [`slice::first()`](https://doc.rust-lang.org/std/primitive.slice.html#method.first)
        fn first(&self) -> Option<Self::Ref<'_>> {
            self.get(0)
        }

        /// Analogous to [`slice::last()`](https://doc.rust-lang.org/std/primitive.slice.html#method.last)
        fn last(&self) -> Option<Self::Ref<'_>> {
            self.get(self.len().saturating_sub(1))
        }

        /// Obtain a `const` pointer type for this data
        fn as_ptr(&self) -> Self::Ptr;

        /// Analogous to [`Vec::as_mut_slice()`]
        fn as_mut_slice<'c: 'b, 'b>(&'c mut self) -> Self::SliceMut<'c>
        where
            Self: 'b;

        /// Create a mutable slice of this vector matching the given
        /// `range`. This is analogous to `IndexMut<Range<usize>>`.
        fn slice_mut(
            &mut self,
            index: impl core::ops::RangeBounds<usize>,
        ) -> Self::SliceMut<'_>;

        /// Analogous to [`slice::get_mut()`](https://doc.rust-lang.org/std/primitive.slice.html#method.get_mut)
        fn get_mut(&mut self, index: usize) -> Option<Self::RefMut<'_>>;

        /// Analogous to [`core::ops::IndexMut::index_mut()`] for `usize`
        fn index_mut(&mut self, index: usize) -> Self::RefMut<'_>;

        /// Creates a mutable iterator
        fn iter_mut(&mut self) -> Self::IterMut<'_>;

        /** Re-order the arrays using the provided indices. This is provided so that generic sorting methods
         can be implemented because closure-passing trait methods encounter difficulties with lifetimes.
        */
        fn apply_index(&mut self, indices: &[usize]);

        /// `[slice::sort_by()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by>).
        fn sort_by<F>(&mut self, mut f: F)
        where
            F: FnMut(Self::Ref<'_>, Self::Ref<'_>) -> core::cmp::Ordering,
        {
            let mut permutation: Vec<usize> = (0..self.len()).collect();
            permutation.sort_by(|j, k| f(self.index(*j), self.index(*k)));

            self.apply_index(&permutation);
        }

        /// `[slice::sort_by()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_key>).
        fn sort_by_key<F, K>(&mut self, mut f: F)
        where
            F: FnMut(Self::Ref<'_>) -> K,
            K: Ord,
        {
            let mut permutation: Vec<usize> = (0..self.len()).collect();
            permutation.sort_by_key(|j| f(self.index(*j)));

            self.apply_index(&permutation);
        }

        /// Analogous to [`slice::first_mut()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.first_mut>).
        fn first_mut(&mut self) -> Option<Self::RefMut<'_>> {
            self.get_mut(0)
        }

        /// Analogous to [`slice::last_mut()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.last_mut>).
        fn last_mut(&mut self) -> Option<Self::RefMut<'_>> {
            self.get_mut(self.len().saturating_sub(1))
        }

        /// Obtain a `mut` pointer type for this data
        fn as_mut_ptr(&mut self) -> Self::PtrMut;
    }

    /**
    The interface for the `Vec`-like struct-of-arrays type. A generalization of [`SoASliceMut`] whose methods can
    also re-size the underlying arrays.

    **NOTE**: This interface is incomplete and additional methods may be added as needed.
    */
    pub trait SoAVec<T: SOA> {
        /// The type that elements will be proxied with as
        type Ref<'t>
        where
            Self: 't;

        /// The type representing immutable slices of elements
        type Slice<'t>: SoASlice<T> + IntoSoAIter<'t, T>
        where
            Self: 't;

        /// The type used for iteration over [`Self::Ref`]
        type Iter<'t>: Iterator<Item = Self::Ref<'t>>
        where
            Self: 't;

        /// The const pointer type interface
        type Ptr;

        /// The type that elements will be proxied with as when mutable
        type RefMut<'t>
        where
            Self: 't;

        /// The type representing mutable slices of elements
        type SliceMut<'t>: SoASliceMut<T>
        where
            Self: 't;

        /// The type used for iteration over [`Self::RefMut`]
        type IterMut<'t>: Iterator<Item = Self::RefMut<'t>>
        where
            Self: 't;

        /// The mut pointer type interface
        type PtrMut;

        /// Returns the number of elements in the arrays
        fn len(&self) -> usize;

        /// Returns true if the arrays has a length of 0.
        fn is_empty(&self) -> bool;

        /// Create an immutable slice of the arrays
        fn as_slice<'c, 'a: 'c>(&'c self) -> Self::Slice<'c>
        where
            Self: 'a;

        /// Create a slice of this vector matching the given `range`. This
        /// is analogous to `Index<Range<usize>>`.
        fn slice<'c, 'a: 'c>(
            &'c self,
            index: impl core::ops::RangeBounds<usize>,
        ) -> Self::Slice<'c>
        where
            Self: 'a;

        /// Analogous to [`slice::get()`](https://doc.rust-lang.org/std/primitive.slice.html#method.get)
        fn get(&self, index: usize) -> Option<Self::Ref<'_>>;

        /// Analogous to [`core::ops::Index::index()`] for `usize`
        fn index(&self, index: usize) -> Self::Ref<'_>;

        /// Create an immutable iterator
        fn iter(&self) -> Self::Iter<'_>;

        /// Analogous to [`slice::first()`](https://doc.rust-lang.org/std/primitive.slice.html#method.first)
        fn first(&self) -> Option<Self::Ref<'_>> {
            self.get(0)
        }

        /// Analogous to [`slice::last()`](https://doc.rust-lang.org/std/primitive.slice.html#method.last)
        fn last(&self) -> Option<Self::Ref<'_>> {
            self.get(self.len().saturating_sub(1))
        }

        /// Obtain a `const` pointer type for this data
        fn as_ptr(&self) -> Self::Ptr;

        /// Analogous to [`Vec::as_mut_slice()`]
        fn as_mut_slice<'c, 'a: 'c>(&'c mut self) -> Self::SliceMut<'c>
        where
            Self: 'a;

        /// Create a mutable slice of this vector matching the given
        /// `range`. This is analogous to `IndexMut<Range<usize>>`.
        fn slice_mut(
            &mut self,
            index: impl core::ops::RangeBounds<usize>,
        ) -> Self::SliceMut<'_>;

        /// Analogous to [`slice::get_mut()`](https://doc.rust-lang.org/std/primitive.slice.html#method.get_mut)
        fn get_mut(&mut self, index: usize) -> Option<Self::RefMut<'_>>;

        /// Analogous to [`core::ops::IndexMut::index_mut()`] for `usize`
        fn index_mut(&mut self, index: usize) -> Self::RefMut<'_>;

        /// Creates a mutable iterator
        fn iter_mut(&mut self) -> Self::IterMut<'_>;

        /** Re-order the arrays using the provided indices. This is provided so that generic sorting methods
         can be implemented because closure-passing trait methods encounter difficulties with lifetimes.
        */
        fn apply_index(&mut self, indices: &[usize]);

        /// `[slice::sort_by()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by>).
        fn sort_by<F>(&mut self, mut f: F)
        where
            F: FnMut(Self::Ref<'_>, Self::Ref<'_>) -> core::cmp::Ordering,
        {
            let mut permutation: Vec<usize> = (0..self.len()).collect();
            permutation.sort_by(|j, k| f(self.index(*j), self.index(*k)));

            self.apply_index(&permutation);
        }

        /// `[slice::sort_by()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.sort_by_key>).
        fn sort_by_key<F, K>(&mut self, mut f: F)
        where
            F: FnMut(Self::Ref<'_>) -> K,
            K: Ord,
        {
            let mut permutation: Vec<usize> = (0..self.len()).collect();
            permutation.sort_by_key(|j| f(self.index(*j)));

            self.apply_index(&permutation);
        }

        /// Analogous to [`slice::first_mut()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.first_mut>)
        fn first_mut(&mut self) -> Option<Self::RefMut<'_>> {
            self.get_mut(0)
        }

        /// Analogous to [`slice::last_mut()`](<https://doc.rust-lang.org/std/primitive.slice.html#method.last_mut>)
        fn last_mut(&mut self) -> Option<Self::RefMut<'_>> {
            self.get_mut(self.len().saturating_sub(1))
        }

        /// Obtain a `mut` pointer type for this data
        fn as_mut_ptr(&mut self) -> Self::PtrMut;

        /// Create a new, empty struct of arrays
        fn new() -> Self;

        /// Create a new, empty struct of arrays with the specified capacity
        fn with_capacity(capacity: usize) -> Self;

        /// Analogous to [`Vec::capacity`]
        fn capacity(&self) -> usize;

        /// Analogous to [`Vec::reserve`]
        fn reserve(&mut self, additional: usize);

        /// Analogous to [`Vec::reserve_exact`]
        fn reserve_exact(&mut self, additional: usize);

        /// Analogous to [`Vec::shrink_to_fit`]
        fn shrink_to_fit(&mut self);

        /// Analogous to [`Vec::truncate`]
        fn truncate(&mut self, len: usize);

        /// Add a singular value of `T` to the arrays. Analogous to
        /// [`Vec::push`]
        fn push(&mut self, value: T);

        /// Analogous to [`Vec::swap_remove`]
        fn swap_remove(&mut self, index: usize) -> T;

        /// Analogous to [`Vec::insert`]
        fn insert(&mut self, index: usize, element: T);

        /// Similar to [`core::mem::replace()`](https://doc.rust-lang.org/std/mem/fn.replace.html).
        fn replace(&mut self, index: usize, element: T) -> T;

        /// Analogous to [`Vec::remove`]
        fn remove(&mut self, index: usize) -> T;

        /// Analogous to [`Vec::pop`]
        fn pop(&mut self) -> Option<T>;

        /// Analogous to [`Vec::append`]
        fn append(&mut self, other: &mut Self);

        /// Analogous to [`Vec::clear`]
        fn clear(&mut self);

        /// Analogous to [`Vec::split_off`]
        fn split_off(&mut self, at: usize) -> Self;
    }

    /// A trait to implement `Clone`-dependent behavior to convert a non-owning
    /// SoA type into an owning [`SoAVec`].
    pub trait ToSoAVec<T: SOA> {
        type SoAVecType: SoAVec<T>;

        /// Similar to [`slice::to_vec()`](https://doc.rust-lang.org/std/primitive.slice.html#method.to_vec)
        fn to_vec(&self) -> Self::SoAVecType;
    }

    /// A trait to implement `Clone`-dependent behavior to extend an [`SoAVec`]
    /// with data copied from its associated `Slice` type.
    pub trait SoAAppendVec<T: SOA>: SoAVec<T> {
        /// Analogous to [`Vec::extend_from_slice`]
        fn extend_from_slice(&mut self, other: Self::Slice<'_>);
    }

    /// A trait to express the [`IntoIterator`] guarantee of [`SoASlice`] types
    /// in the type system.
    pub trait IntoSoAIter<'a, T: SOA>:
        SoASlice<T> + IntoIterator<Item = Self::Ref<'a>> + 'a
    {
    }
}
pub use generics::*;

#[macro_export]
#[doc(hidden)]
macro_rules! soa_zip_impl {
    // @flatten creates a tuple-flattening closure for .map() call
    // Finish recursion
    (@flatten $p:pat => $tup:expr ) => {
        |$p| $tup
    };
    // Eat an element ($_iter) and add it to the current closure. Then recurse
    (@flatten $p:pat => ( $($tup:tt)* ) , $_iter:expr $( , $tail:expr )* ) => {
        $crate::soa_zip_impl!(@flatten ($p, a) => ( $($tup)*, a ) $( , $tail )*)
    };

    // The main code is emitted here: we create an iterator, zip it and then
    // map the zipped iterator to flatten it
    (@last , $first: expr, $($tail: expr,)*) => {
        ::core::iter::IntoIterator::into_iter($first)
            $(
                .zip($tail)
            )*
            .map(
                $crate::soa_zip_impl!(@flatten a => (a) $( , $tail )*)
            )
    };

    // Eat the last `mut $field` and then emit code
    (@munch $self: expr, {mut $field: ident} -> [$($output: tt)*] $($ext: expr ,)*) => {
        $crate::soa_zip_impl!(@last $($output)*, $self.$field.iter_mut(), $($ext, )*)
    };
    // Eat the last `$field` and then emit code
    (@munch $self: expr, {$field: ident} -> [$($output: tt)*] $($ext: expr ,)*) => {
        $crate::soa_zip_impl!(@last $($output)*, $self.$field.iter(), $($ext, )*)
    };

    // Eat the next `mut $field` and then recurse
    (@munch $self: expr, {mut $field: ident, $($tail: tt)*} -> [$($output: tt)*] $($ext: expr ,)*) => {
        $crate::soa_zip_impl!(@munch $self, {$($tail)*} -> [$($output)*, $self.$field.iter_mut()] $($ext, )*)
    };
    // Eat the next `$field` and then recurse
    (@munch $self: expr, {$field: ident, $($tail: tt)*} -> [$($output: tt)*] $($ext: expr ,)*) => {
        $crate::soa_zip_impl!(@munch $self, {$($tail)*} -> [$($output)*, $self.$field.iter()] $($ext, )*)
    };
}