1

Generalized Question

How can I implement a general function pinned_array_of_default in stable Rust where [T; N] is too large to fit on the stack?

fn pinned_array_of_default<T: Default, const N: usize>() -> Pin<Box<[T; N]>> {
    unimplemented!()
}

Alternatively, T can implement Copy if that makes the process easier.

fn pinned_array_of_element<T: Copy, const N: usize>(x: T) -> Pin<Box<[T; N]>> {
    unimplemented!()
}

Keeping the solution in safe Rust would have been preferable, but it seems unlikely that it is possible.

Approaches

Initially I was hopping that by implementing Default I might be able to get Default to handle the initial allocation, however it still creates it on the stack so this will not work for large values of N.

let boxed: Box<[T; N]> = Box::default();
let foo = Pin::new(boxed);

I suspect I need to use MaybeUninit to achieve this and there is a Box::new_uninit() function, but it is currently unstable and I would ideally like to keep this within stable Rust. I also somewhat unsure if transmuting Pin<Box<MaybeUninit<B>>> to Pin<Box<B>> could somehow have negative effects on the Pin.

Background

The purpose behind using a Pin<Box<[T; N]>> is to hold a block of pointers where N is some constant factor/multiple of the page size.

#[repr(C)]
#[derive(Copy, Clone)]
pub union Foo<R: ?Sized> {
    assigned: NonNull<R>,
    next_unused: Option<NonNull<Self>>,
}

Each pointer may or may not be in use at a given point in time. An in-use Foo points to R, and an unused/empty Foo has a pointer to either the next empty Foo in the block or None. A pointer to the first unused Foo in the block is stored separately. When a block is full, a new block is created and then pointer chain of unused positions continues through the next block.

The box needs to be pinned since it will contain self referential pointers as well as outside structs holding pointers into assigned positions in each block.

I know that Foo is wildly unsafe by Rust standards, but the general question of creating a Pin<Box<[T; N]>> still stands

Locke
  • 7,626
  • 2
  • 21
  • 41
  • 1
    A possible approach: create a `Vec` of length `N`, then use `Vec::into_boxed_slice` to get a `Box<[T]>`, and then you can [`.try_into()` a `Box<[T; N]>`](https://doc.rust-lang.org/stable/std/convert/trait.TryFrom.html#impl-TryFrom%3CBox%3C%5BT%5D%2C%20Global%3E%3E). – PitaJ Mar 17 '22 at 21:45

1 Answers1

7

A way to construct a large array on the heap and avoid creating it on the stack is to proxy through a Vec. You can construct the elements and use .into_boxed_slice() to get a Box<[T]>. You can then use .try_into() to convert it to a Box<[T; N]>. And then use .into() to convert it to a Pin<Box<[T; N]>>:

fn pinned_array_of_default<T: Default, const N: usize>() -> Pin<Box<[T; N]>> {
    let mut vec = vec![];
    vec.resize_with(N, T::default);
    let boxed: Box<[T; N]> = match vec.into_boxed_slice().try_into() {
        Ok(boxed) => boxed,
        Err(_) => unreachable!(),
    };
    
    boxed.into()
}

You can optionally make this look more straight-forward if you add T: Clone so that you can do vec![T::default(); N] and/or add T: Debug so you can use .unwrap() or .expect().

See also:

kmdreko
  • 42,554
  • 6
  • 57
  • 106
  • I'd keep `unreachable!()`, even if you could require `Debug` in that case, because it conveys that this will never happen, and can be easily replaced with `unreachable_unchecked` in the future if necessary. – PitaJ Mar 17 '22 at 22:11
  • Will `.into_boxed_slice().try_into()` cause the contents to be copied to create the new `Box`? – Locke Mar 17 '22 at 22:15
  • 1
    No, it essentially just transmutes unless the slice isn't long enough: https://doc.rust-lang.org/src/alloc/boxed.rs.html#1552 You could implement the `from_raw(into_raw)` yourself if you'd prefer to avoid the `try_into`. – PitaJ Mar 17 '22 at 22:18
  • @Locke The [`.into_boxed_slice()`](https://doc.rust-lang.org/src/alloc/vec/mod.rs.html#995) call may re-allocate if there is unused capacity because a box must refer to the whole allocation. However, with a resize from 0->N, that would only happen with [certain combinations](https://doc.rust-lang.org/src/alloc/raw_vec.rs.html#111) of small `N` and `size_of::()`. – kmdreko Mar 17 '22 at 22:58