Array as a struct field

Question

I would like to create a non binary tree structure in Rust. Here is a try

struct TreeNode<T> {
    tag : T,
    father : Weak<TreeNode<T>>,
    childrenlists : [Rc<TreeNode<T>>]
}

Unfortunately, this does not compile.

main.rs:4:1: 8:2 error: the trait `core::marker::Sized` is not implemented for the type `[alloc::rc::Rc<TreeNode<T>>]` [E0277]
main.rs:4 struct TreeNode<T> {
main.rs:5     tag : T,
main.rs:6     father : Weak<TreeNode<T>>,
main.rs:7     childrenlist : [Rc<TreeNode<T>>]
main.rs:8 }
main.rs:4:1: 8:2 note: `[alloc::rc::Rc<TreeNode<T>>]` does not have a constant size known at compile-time
main.rs:4 struct TreeNode<T> {
main.rs:5     tag : T,
main.rs:6     father : Weak<TreeNode<T>>,
main.rs:7     childrenlist : [Rc<TreeNode<T>>]
main.rs:8 }
error: aborting due to previous error

The code compiles if we replace an array with a Vec. However, the structure is immutable and I do not need an overallocated Vec.

I heard it could be possible to have a struct field with size unknown at compile time, provided it is unique. How can we do it?

Answer 1

Rust doesn't have the concept of a variable-length (stack) array, which you seem to be trying to use here.

Rust has a couple different array-ish types.

• Vec<T> ("vector"): Dynamically sized; dynamically allocated on the heap. This is probably what you want to use. Initialize it with Vec::with_capacity(foo) to avoid overallocation (this creates an empty vector with the given capacity).
• [T; n] ("array"): Statically sized; lives on the stack. You need to know the size at compile time, so this won't work for you (unless I've misanalysed your situation).
• [T] ("slice"): Unsized; usually used from &[T]. This is a view into a contiguous set of Ts in memory somewhere. You can get it by taking a reference to an array, or a vector (called "taking a slice of an array/vector"), or even taking a view into a subset of the array/vector. Being unsized, [T] can't be used directly as a variable (it can be used as a member of an unsized struct), but you can view it from behind a pointer. Pointers referring to [T] are fat ; i.e. they have an extra field for the length. &[T] would be useful if you want to store a reference to an existing array; but I don't think that's what you want to do here.

Answer 2

If you don't know the size of the list in advance, you have two choices:

1. &[T] which is just a reference to some piece of memory that you don't own
2. Vec<T> which is your own storage.

The correct thing here is to use a Vec. Why? Because you want the children list (array of Rc) to be actually owned by the TreeNode. If you used a &[T], it means that someone else would be keeping the list, not the TreeNode. With some lifetime trickery, you could write some valid code but you would have to go very far to please the compiler because the borrowed reference would have to be valid at least as long as the TreeNode.

Finally, a sentence in your question shows a misunderstanding:

However, the structure is immutable and I do not need an overallocated Vec.

You confuse mutability and ownership. Sure you can have an immutable Vec. It seems like you want to avoid allocating memory from the heap, but that's not possible, precisely because you don't know the size of the children list. Now if you're concerned with overallocating, you can fine-tune the vector storage with methods like with_capacity() and shrink_to_fit().

A final note: if you actually know the size of the list because it is fixed at compile time, you just need to use a [T; n] where n is compile-time known. But that's not the same as [T].