Почему рекурсивные типы структур незаконны в Rust?

Я пробую случайные вещи, чтобы углубить свое понимание ржавчины. Я просто столкнулся с следующей ошибкой с этим кодом:

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),
    };
}

Ошибка:

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

Я понимаю, что могу исправить это, если я поставлю Person in a Box, так что это работает:

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)),
    };
}

Я хотел бы понять всю историю этого. Я знаю, что бокс означает, что он будет храниться в куче, а не в стеке, но я не понимаю, почему это направление необходимо.

Ответ 1

Данные внутри struct и enum (и кортежи) хранятся непосредственно внутри строки внутри памяти значения struct. Для такой структуры, как

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

Позвольте вычислить размер: size_of::<Recursive>(). Очевидно, что он имеет 1 байт из поля x, а затем Option имеет размер 1 (для дискриминанта) + size_of::<Recursive>() (для содержащихся данных), поэтому в итоге размер представляет собой сумму:

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

То есть размер должен быть бесконечным.

Другой способ взглянуть на это - это просто развернуть Recursive несколько раз (в качестве кортежей, для ясности):

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

и все это сохраняется в строке в одном блоке памяти.

A Box<T> является указателем, то есть имеет фиксированный размер, поэтому (u8, Option<Box<Recursive>>) составляет 1 + 8 байт. (Один из способов оценить Box<T> заключается в том, что он является нормальным T с гарантией того, что он имеет фиксированный размер.)

Ответ 2

Язык программирования ржавчины, второе издание, говорит об рекурсивных типах:

Rust должен знать во время компиляции, сколько места занимает тип. Один тип типа, размер которого неизвестен во время компиляции, является рекурсивным типом, где значение может иметь как часть себя другое значение того же типа. Это вложение значений теоретически может продолжаться бесконечно, поэтому Rust не знает, сколько пространства требуется для рекурсивного типа. Однако ящики имеют известный размер, поэтому, вставив поле в рекурсивное определение типа, нам разрешено иметь рекурсивные типы.

В принципе, структура будет иметь бесконечный размер, если вы не используете бокс. Например, у Сьюзан есть мать, отец и партнер, у каждого из которых есть мать, отец и партнер... и т.д. Бокс использует указатель, который является фиксированным размером и динамическим распределением памяти.