How to create an array of more than 32 elements of a generic type T: Default?

user_14637 0
Viewed 507

This question is similar to Initialize a large, fixed-size array with non-Copy types but for an array of a generic type.

I have this struct:

struct Foo<T>([T; 99]);

If T implements Default, how do I write an implementation of Default for Foo<T>?

impl<T: Default> Default for Foo<T> {
    fn default() -> Self {
        // ???
    }
}

The naive approach does not work because Default is only implemented for arrays up to length 32:

Foo(Default::default())

error[E0277]: the trait bound `[_; 99]: Default` is not satisfied
 --> src/lib.rs:5:13
  |
5 |         Foo(Default::default())
  |             ^^^^^^^^^^^^^^^^^^ the trait `Default` is not implemented for `[_; 99]`
  |

This works (adapted from here), but uses a deprecated function:

Foo(unsafe {
    let mut arr: [T; 99] = std::mem::uninitialized();
    for e in &mut arr {
        std::ptr::write(e, T::default());
    }
    arr
})

warning: use of deprecated function `std::mem::uninitialized`: use `mem::MaybeUninit` instead
 --> src/lib.rs:6:36
  |
6 |             let mut arr: [T; 99] = std::mem::uninitialized();
  |                                    ^^^^^^^^^^^^^^^^^^^^^^^
  |

I tried to use the new and shiny MaybeUninit, following an example in its docs:

Foo(unsafe {
    use std::mem::MaybeUninit;
    let mut arr: [MaybeUninit<T>; 99] = {
        MaybeUninit::uninit().assume_init()
    };
    for e in &mut arr {
        *e = MaybeUninit::new(T::default());
    }
    std::mem::transmute(arr)
})

error[E0512]: cannot transmute between types of different sizes, or dependently-sized types
  --> src/lib.rs:13:13
   |
13 |             std::mem::transmute(arr)
   |             ^^^^^^^^^^^^^^^^^^^
   |
   = note: source type: `[MaybeUninit<T>; 99]` (size can vary because of T)
   = note: target type: `[T; 99]` (size can vary because of T)

It's guaranteed that MaybeUninit<T> has the same size as T, but that doesn't necessarily mean that the same holds for [MaybeUninit<T>; 99] and [T; 99], as per the docs:

However remember that a type containing a MaybeUninit<T> is not necessarily the same layout; Rust does not in general guarantee that the fields of a Foo<T> have the same order as a Foo<U> even if T and U have the same size and alignment.

I'm not sure this sentence applies to arrays, but it seems the compiler isn't sure either.

How can I write this function without using the deprecated std::mem::uninitialized()? Note that I'm using a raw array specifically to avoid allocations, so the solution should be allocation-free as well.

For your convenience, here's a playground link.

rust unsafe arrays
1 Answers

You can avoid the deprecated std::mem::uninitialized() function by following the recipe from MaybeUninit documentation.

As you discovered, you'll need to switch from the scary transmute to the even scarier transmute_copy due to (what's likely) a compiler issue. In this case transmute_copy() is sound because you're transmuting MaybeUninits (which are not dropped) and which you're not touching after the transmute.

impl<T: Default> Default for Foo<T> {
    fn default() -> Self {
        Foo(unsafe {
            // `assume_init` is sound here because the type we are claiming to have
            // initialized consists of `MaybeUninit`s, which do not require initialization.
            let mut arr: [MaybeUninit<T>; 99] = MaybeUninit::uninit().assume_init();
            for e in &mut arr {
                *e = MaybeUninit::new(T::default());
            }
            // transmute_copy required due to a (likely) compiler bug,
            // see https://github.com/rust-lang/rust/issues/62875
            std::mem::transmute_copy(&arr)
        })
    }
}

It's guaranteed that MaybeUninit<T> has the same size as T, but that doesn't necessarily mean that the same holds for [MaybeUninit<T>; 99] and [T; 99], as per the docs: "However remember that a type containing a MaybeUninit<T> is not necessarily the same layout [...]"

The docs are correct to warn about containers in general because of (among other things) niche optimizations; the size of Option<usize> and Option<&u8> are different even though the sizes of usize and &u8 are equal.

The array initialization example from the MaybeUninit docs is a pretty strong indication that the warning doesn't apply to arrays. Even if you don't accept the doc example as a chapter-and-verse guarantee, keep in mind that that code has been in the docs for years now, and there is a lot of code that makes use of it (I wrote some just a couple of weeks ago and found more). Not only would it all break if the guarantee went away, but there would be no way to initialize an array element by element.

user_16008980
Related