ps4 - ¿Por qué los tipos de estructura recursiva son ilegales en Rust?

rust traduccion

Question

Estoy probando cosas al azar para profundizar mi comprensión de Rust. Acabo de encontrar el siguiente error con este código :

struct Person {
    mother: Option<Person>,
    father: Option<Person>,
    partner: Option<Person>,
}

pub fn main() {
    let susan = Person {
        mother: None,
        father: None,
        partner: None,
    };

    let john = Person {
        mother: None,
        father: None,
        partner: Some(susan),
    };
}

El error es :

error[E0072]: recursive type `Person` has infinite size
 --> src/main.rs:1:1
  |
1 | struct Person {
  | ^^^^^^^^^^^^^ recursive type has infinite size
2 |     mother: Option<Person>,
  |     ---------------------- recursive without indirection
3 |     father: Option<Person>,
  |     ---------------------- recursive without indirection
4 |     partner: Option<Person>,
  |     ----------------------- recursive without indirection
  |
  = help: insert indirection (e.g., a `Box`, `Rc`, or `&`) at some point to make `Person` representable

Entiendo que puedo solucionarlo si pongo a la Person en una Box , así que esto funciona :

struct Person {
    mother: Option<Box<Person>>,
    father: Option<Box<Person>>,
    partner: Option<Box<Person>>,
}

pub fn main() {
    let susan = Person {
        mother: None,
        father: None,
        partner: None,
    };

    let john = Person {
        mother: None,
        father: None,
        partner: Some(Box::new(susan)),
    };
}

Me gustaría entender la historia completa detrás de eso. Sé que el boxeo significa que se almacenará en el montón en lugar de en la pila, pero no entiendo por qué es necesaria esta indirección.

Answer 1

Los datos dentro de struct s y enum s (y tuplas) se almacenan directamente en línea dentro de la memoria del valor de struct. Dada una estructura como

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

calculemos el tamaño: size_of::<Recursive>() . Claramente tiene 1 byte del campo x , y luego la Option tiene el tamaño 1 (para el discriminante) + size_of::<Recursive>() (para los datos contenidos), entonces, en resumen, el tamaño es la suma:

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

Es decir, el tamaño debería ser infinito.

Otra forma de verlo es expandir Recursive repetidamente (como tuplas, para mayor claridad):

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

y todo esto se almacena en línea en una sola porción de memoria.

Un Box<T> es un puntero, es decir, tiene un tamaño fijo, por lo que (u8, Option<Box<Recursive>>) es 1 + 8 bytes. (Una forma de considerar el Box<T> es que es una T normal con la garantía de que tiene un tamaño fijo).

Answer 2

The Rust Programming Language , segunda edición tiene esto que decir sobre los tipos recursivos:

Rust necesita saber en tiempo de compilación cuánto espacio ocupa un tipo. Un tipo de tipo cuyo tamaño no se puede conocer en tiempo de compilación es un tipo recursivo donde un valor puede tener como parte de sí mismo otro valor del mismo tipo. Esta anidación de valores teóricamente podría continuar infinitamente, por lo que Rust no sabe cuánto espacio necesita un valor de tipo recursivo. Sin embargo, las cajas tienen un tamaño conocido, por lo que al insertar una caja en una definición de tipo recursivo, se nos permite tener tipos recursivos.

Básicamente, la estructura sería de tamaño infinito si no usa el boxeo. Por ejemplo, Susan tiene una madre, un padre y una pareja, cada uno de los cuales tiene una madre, un padre y una pareja ... etc. El boxeo utiliza un puntero, que es un tamaño fijo, y una asignación de memoria dinámica.