Is it possible to imply Copy for Option::None?

I have problem initialize a recursive struct with Box allocation in safe && stable rust.

code

#[derive(Clone)]
struct Trie<const N:usize> (Box<([Option<Trie<N>>;N],bool)>);

impl<const N:usize> Trie<N> { // for arbitrary N, failed to compile.
//impl Trie<26> { // for a specific number smaller than 32, it compiles.
    fn new() -> Self {Self ( Box::new((Default::default(),false)))}
}

I tried #[derive(Clone,Copy,Default)], but since Trie's default is not yet implemented, and Box is not Copy, all these tries failed.

I also tried wrapper type like

struct Trie<const N:usize> (Box<([MyOption<Trie<N>>;N],bool)>);
struct MyOption<T>(Option<T>)
impl<T> Default for MyOption<T>{fn default()->Self{Self(None)}}

but since [T;33] have no Default impls, the code failed to execute.

I even tried a very unsafe way, impl Copy for MyOption<T>, but compiler stops me since T might not Copy.

Is there any good method to initialize something like struct Trie<const N:usize> (Box<([Option<Trie<N>>;N],bool)>); in stable and safe rust?

Or, is it possible to crate a discussion about some crazy idea like impl Copy for Option::None or new grammar like [some_default_function:N] which generates a length N array [some_default_function(),some_default_function(),...,some_default_function()]

Default for arrays is currently only implemented for sizes up to 32 due to [T; 0] implementing Default even if T doesn't implement Default. This prevents a generic implementation, although people are working on a solution.

You also can't use the syntax [expr; N] because the type of expr needs to implement Copy, but there's an alternative: expr can be a const variable. Translating this to code is a bit boilerplaty though because const items can't access generics from their environment:

#[derive(Clone)]
struct Trie<const N: usize>(Box<([Option<Trie<N>>; N], bool)>);

impl<const N: usize> Trie<N> {
    fn new() -> Self {
        struct Helper<const N: usize>;
        impl<const N: usize> Helper<N> {
            const OPTION_TRIE: Option<Trie<N>> = None;
        }
        Self(Box::new(([Helper::<N>::OPTION_TRIE; N], false)))
    }
}

This also has the advantage of being usable in const contexts, while the next solution is not.

This is pretty much std::array::from_fn, which is however unstable until the next release. For now you can use [(); N].map(|_| some_default_expression()).

2 Likes

There's already a plan for your scenario. It looks like this:

pub fn demo() -> [Option<String>; 100] {
    [const { None }; 100]
}

https://play.rust-lang.org/?version=nightly&mode=debug&edition=2021&gist=7baacd534e95411c7987bdce99b562ba

Hopefully it won't be too long until it stabilizes.

3 Likes

For completeness, this will become less boilerplaty if we get const { … } blocks.

#![feature(inline_const)]

#[derive(Clone)]
struct Trie<const N: usize>(Box<([Option<Trie<N>>; N], bool)>);

impl<const N: usize> Trie<N> {
    fn new() -> Self {
        Self(Box::new(([const { None }; N], false)))
    }
}
1 Like

Thank you for your excellent answer which allows me play such magic in some stable only plantform.

and thanks for all of your answers.

Hope Rust be better in the future:)

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.