path: root/vendor/generic-array-0.14.4/DESIGN.md

Design and Usage Notes
======================

## Sections

1. [How it Works](#how-it-works)
2. [Initialization](#initialization)
3. [Functional Programming](#functional-programming)
4. [Miscellaneous Utilities](#miscellaneous-utilities)
5. [Safety](#safety)
6. [Optimization](#optimization)
7. [The Future](#the-future)

**NOTE**: This document uses `<details>` sections, so look out for collapsible parts with an arrow on the left.

# How it works

`generic-array` is a method of achieving fixed-length fixed-size stack-allocated generic arrays without needing const generics in stable Rust.

That is to say this:

```rust
struct Foo<const N: usize> {
    data: [i32; N],
}
```

or anything similar is not currently supported.

However, Rust's type system is sufficiently advanced, and a "hack" for solving this was created in the form of the `typenum` crate, which recursively defines integer values in binary as nested types, and operations which can be applied to those type-numbers, such as `Add`, `Sub`, etc.

e.g. `6` would be `UInt<UInt<UInt<UTerm, B1>, B1>, B0>`

Over time, I've come to see `typenum` as less of a hack and more as an elegant solution.

The recursive binary nature of `typenum` is what makes `generic-array` possible, so:

```rust
struct Foo<N: ArrayLength<i32>> {
    data: GenericArray<i32, N>,
}
```

is supported.

I often see questions about why `ArrayLength` requires the element type `T` in it's signature, even though it's not used in the inner `ArrayType`.

This is because `GenericArray` itself does not define the actual array. Rather, it is defined as:

```rust
pub struct GenericArray<T, N: ArrayLength<T>> {
    data: N::ArrayType,
}
```

The trait `ArrayLength` does all the real heavy lifting for defining the data, with implementations on `UInt<N, B0>`, `UInt<N, B1>` and `UTerm`, which correspond to even, odd and zero numeric values, respectively.

`ArrayLength`'s implementations use type-level recursion to peel away each least significant bit and form sort of an opaque binary tree of contiguous data the correct physical size to store `N` elements of `T`. The tree, or block of data, is then stored inside of `GenericArray` to be reinterpreted as the array.

For example, `GenericArray<T, U6>` more or less expands to (at compile time):

<details>
<summary>Expand for code</summary>

```rust
GenericArray {
    // UInt<UInt<UInt<UTerm, B1>, B1>, B0>
    data: EvenData {
        // UInt<UInt<UTerm, B1>, B1>
        left: OddData {
            // UInt<UTerm, B1>
            left: OddData {
                left: (),  // UTerm
                right: (), // UTerm
                data: T,   // Element 0
            },
            // UInt<UTerm, B1>
            right: OddData {
                left: (),  // UTerm
                right: (), // UTerm
                data: T,   // Element 1
            },
            data: T        // Element 2
        },
        // UInt<UInt<UTerm, B1>, B1>
        right: OddData {
            // UInt<UTerm, B1>
            left: OddData {
                left: (),  // UTerm
                right: (), // UTerm
                data: T,   // Element 3
            },
            // UInt<UTerm, B1>
            right: OddData {
                left: (),  // UTerm
                right: (), // UTerm
                data: T,   // Element 4
            },
            data: T        // Element 5
        }
    }
}
```

</details>

This has the added benefit of only being `log2(N)` deep, which is important for things like `Drop`, which we'll go into later.

Then, we take `data` and cast it to `*const T` or `*mut T` and use it as a slice like:

```rust
unsafe {
    slice::from_raw_parts(
        self as *const Self as *const T,
        N::to_usize()
    )
}
```

It is useful to note that because `typenum` is compile-time with nested generics, `to_usize`, even if it isn't a `const fn`, *does* expand to effectively `1 + 2 + 4 + 8 + ...` and so forth, which LLVM is smart enough to reduce to a single compile-time constant. This helps hint to the optimizers about things such as bounds checks.

So, to reiterate, we're working with a raw block of contiguous memory the correct physical size to store `N` elements of `T`. It's really no different from how normal arrays are stored.

## Pointer Safety

Of course, casting pointers around and constructing blocks of data out of thin air is normal for C, but here in Rust we try to be a bit less prone to segfaults. Therefore, great care is taken to minimize casual `unsafe` usage and restrict `unsafe` to specific parts of the API, making heavy use those exposed safe APIs internally.

For example, the above `slice::from_raw_parts` is only used twice in the entire library, once for `&[T]` and `slice::from_raw_parts_mut` once for `&mut [T]`. Everything else goes through those slices.

# Initialization

## Constant

"Constant" initialization, that is to say - without dynamic values, can be done via the `arr![]` macro, which works almost exactly like `vec![]`, but with an additional type parameter.

Example:

```rust
let my_arr = arr![i32; 1, 2, 3, 4, 5, 6, 7, 8];
```

## Dynamic

Although some users have opted to use their own initializers, as of version `0.9` and beyond `generic-array` includes safe methods for initializing elements in the array.

The `GenericSequence` trait defines a `generate` method which can be used like so:

```rust
use generic_array::{GenericArray, sequence::GenericSequence};

let squares: GenericArray<i32, U4> =
             GenericArray::generate(|i: usize| i as i32 * 2);
```

and `GenericArray` additionally implements `FromIterator`, although `from_iter` ***will*** panic if the number of elements is not *at least* `N`. It will ignore extra items.

The safety of these operations is described later.

# Functional Programming

In addition to `GenericSequence`, this crate provides a `FunctionalSequence`, which allows extremely efficient `map`, `zip` and `fold` operations on `GenericArray`s.

As described at the end of the [Optimization](#optimization) section, `FunctionalSequence` uses clever specialization tactics to provide optimized methods wherever possible, while remaining perfectly safe.

Some examples, taken from `tests/generic.rs`:

<details>
<summary>Expand for code</summary>

This is so extensive to show how you can build up to processing totally arbitrary sequences, but for the most part these can be used on `GenericArray` instances without much added complexity.

```rust
/// Super-simple fixed-length i32 `GenericArray`s
pub fn generic_array_plain_zip_sum(a: GenericArray<i32, U4>, b: GenericArray<i32, U4>) -> i32 {
    a.zip(b, |l, r| l + r)
     .map(|x| x + 1)
     .fold(0, |a, x| x + a)
}

pub fn generic_array_variable_length_zip_sum<N>(a: GenericArray<i32, N>, b: GenericArray<i32, N>) -> i32
where
    N: ArrayLength<i32>,
{
    a.zip(b, |l, r| l + r)
     .map(|x| x + 1)
     .fold(0, |a, x| x + a)
}

pub fn generic_array_same_type_variable_length_zip_sum<T, N>(a: GenericArray<T, N>, b: GenericArray<T, N>) -> i32
where
    N: ArrayLength<T> + ArrayLength<<T as Add<T>>::Output>,
    T: Add<T, Output=i32>,
{
    a.zip(b, |l, r| l + r)
     .map(|x| x + 1)
     .fold(0, |a, x| x + a)
}

/// Complex example using fully generic `GenericArray`s with the same length.
///
/// It's mostly just the repeated `Add` traits, which would be present in other systems anyway.
pub fn generic_array_zip_sum<A, B, N: ArrayLength<A> + ArrayLength<B>>(a: GenericArray<A, N>, b: GenericArray<B, N>) -> i32
where
    A: Add<B>,
    N: ArrayLength<<A as Add<B>>::Output> +
        ArrayLength<<<A as Add<B>>::Output as Add<i32>>::Output>,
    <A as Add<B>>::Output: Add<i32>,
    <<A as Add<B>>::Output as Add<i32>>::Output: Add<i32, Output=i32>,
{
    a.zip(b, |l, r| l + r)
     .map(|x| x + 1)
     .fold(0, |a, x| x + a)
}
```
</details>

and if you really want to go off the deep end and support any arbitrary *`GenericSequence`*:

<details>
<summary>Expand for code</summary>

```rust
/// Complex example function using generics to pass N-length sequences, zip them, and then map that result.
///
/// If used with `GenericArray` specifically this isn't necessary
pub fn generic_sequence_zip_sum<A, B>(a: A, b: B) -> i32
where
    A: FunctionalSequence<i32>,                                                                 // `.zip`
    B: FunctionalSequence<i32, Length = A::Length>,                                             // `.zip`
    A: MappedGenericSequence<i32, i32>,                                                         // `i32` -> `i32`
    B: MappedGenericSequence<i32, i32, Mapped = MappedSequence<A, i32, i32>>,                   // `i32` -> `i32`, prove A and B can map to the same output
    A::Item: