Why are recursive struct types illegal in Rust?

by

Data inside structs and enums (and tuples) is stored directly inline inside the memory of the struct value. Given a struct like

struct Recursive {
    x: u8,
    y: Option<Recursive>
}

let’s compute the size: size_of::<Recursive>(). Clearly it has 1 byte from the x field, and then the Option has size 1 (for the discriminant) + size_of::<Recursive>() (for the contained data), so, in summary, the size is the sum:

size_of::<Recursive>() == 2 + size_of::<Recursive>()

That is, the size would have to be infinite.

Another way to look at it is just expanding Recursive repeatedly (as tuples, for clarity):

Recursive ==
(u8, Option<Recursive>) ==
(u8, Option<(u8, Option<Recursive>)>) ==
(u8, Option<(u8, Option<(u8, Option<Recursive>)>)>) ==
...

and all of this is stored inline in a single chunk of memory.

A Box<T> is a pointer, i.e. it has a fixed size, so (u8, Option<Box<Recursive>>) is 1 + 8 bytes. (One way to regard Box<T> is that it’s a normal T with the guarantee that it has a fixed size.)

More Related Contents:

  1. Why is a trait not implemented for a type that clearly has it implemented?
  2. How can I include a module from another file from the same project?
  3. What does “Sized is not implemented” mean?
  4. Deriving a trait results in unexpected compiler error, but the manual implementation works
  5. How do I implement a trait I don’t own for a type I don’t own?
  6. How do I implement Copy and Clone for a type that contains a String (or any type that doesn’t implement Copy)?
  7. What makes something a “trait object”?
  8. What is the return type of the indexing operation?
  9. How to do a binary search on a Vec of floats?
  10. Change enum variant while moving the field to the new variant
  11. I implemented a trait for another trait but cannot call methods from both traits
  12. When is it useful to define multiple lifetimes in a struct?
  13. Can I write an Iterator that mutates itself and then yields a reference into itself?
  14. How to update-or-insert on a Vec?
  15. How do I specify lifetime parameters in an associated type?
  16. How to return a string (or similar) from Rust in WebAssembly?
  17. What is the difference between Copy and Clone?
  18. Is it possible to have stack allocated arrays with the size determined at runtime in Rust?
  19. Temporary value is freed at the end of this statement [duplicate]
  20. What is the right way to allocate data to pass to an FFI call?
  21. Sharing a struct with trait objects as properties across threads
  22. Why does compilation not fail when a member of a moved value is assigned to?
  23. How to switch between Rust toolchains?
  24. What does “missing lifetime specifier” mean when storing a &str in a structure?
  25. How to quiet a warning for a single statement in Rust?
  26. Use of undeclared type or module `std` when used in a separate module
  27. Is there an elegant solution to modifying a structure while iterating?
  28. Can a struct containing a raw pointer implement Send and be FFI safe?
  29. Lazy sequence generation in Rust
  30. Is there a way to get the field names of a struct in a macro?

Leave a Comment