Почему рекурсивные типы структур недопустимы в Rust?
Я пробую случайные вещи, чтобы углубить мое понимание 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 в 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)),
};
}
Я хотел бы понять всю историю этого. Я знаю, что бокс означает, что он будет храниться в куче, а не в стеке, но я не понимаю, почему это косвенное обращение необходимо.
3 ответа
Данные внутри structс и enums (и кортежи) хранятся непосредственно в памяти внутри значения структуры. Учитывая структуру как
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>)>)>) ==
...
и все это хранится встроенным в один кусок памяти.
Box<T> это указатель, т.е. он имеет фиксированный размер, поэтому (u8, Option<Box<Recursive>>) 1 + 8 байт. (Один из способов расценивать Box<T> это нормально T с гарантией того, что он имеет фиксированный размер.)
Язык программирования Rust, второе издание, говорит о рекурсивных типах:
Rust должен знать во время компиляции, сколько места занимает тип. Один тип типа, размер которого не может быть известен во время компиляции, является рекурсивным типом, где значение может иметь как часть самого себя другое значение того же типа. Это вложение значений теоретически может продолжаться бесконечно, поэтому Rust не знает, сколько места требуется значению рекурсивного типа. Однако ящики имеют известный размер, поэтому, вставляя поле в определение рекурсивного типа, мы можем иметь рекурсивные типы.
По сути, структура будет иметь бесконечный размер, если вы не используете бокс. Например, у Сьюзен есть мать, отец и партнер, у каждого из которых есть мать, отец и партнер.... и т. Д. Бокс использует указатель, который имеет фиксированный размер, и динамическое распределение памяти.
Имейте в виду, что, хотя на самом деле a решает вашу проблему на поверхности, это делает невозможным фактическое создание ее экземпляра, если вы намерены иметь двунаправленную связь между партнерами:
struct Person {
partner: Option<Box<Person>>,
}
pub fn main() {
let susan = Person { partner: None };
let mut john = Person {
partner: Some(Box::new(susan)),
};
// This moves `susan` into `john`, meaning `susan` is now only
// accessible through `john.partner`.
let susan = john.partner.as_mut().unwrap();
// It is literally impossible to set john as a partner of susan,
// no matter what you try. (without using `unsafe`)
susan.partner = Some(Box::new(john));
}
error[E0505]: cannot move out of `john` because it is borrowed
--> src/main.rs:18:35
|
14 | let susan = john.partner.as_mut().unwrap();
| --------------------- borrow of `john.partner` occurs here
...
18 | susan.partner = Some(Box::new(john));
| ------------- ^^^^ move out of `john` occurs here
| |
| borrow later used here
полезен только в том случае, если у вас есть древовидная цепочка владения, где кто-то владеет самым верхним элементом.
Ваша ситуация не полностью потеряна, однако, просто немного сложнее.
На этот раз вы можете использовать вместоBoxсделать это. Однако это немного опасно, потому что круговая цепь будет протекать и никогда не будет сброшена, если вы не прервете цикл вручную в какой-то момент. Помните, что в Rust нет сборщика мусора.
Одно решение, которое я мог видеть, этоWeak, который является версиейRcэто специально не поддерживает объект, на который он указывает, живым. Это сделано специально для циклических ссылок, подобных этой. Обратите внимание, однако, что это делает объекты неизменяемыми, и поэтому нам нужно создать внутреннюю изменчивость с помощьюRefCell.
use std::{
cell::RefCell,
rc::{Rc, Weak},
};
#[derive(Debug)]
struct Person {
name: String,
partner: Option<Weak<RefCell<Person>>>,
}
impl Person {
fn partner_name(&self) -> Option<String> {
self.partner
.as_ref()
.map(|partner| Weak::upgrade(partner).unwrap())
.map(|partner| RefCell::borrow(&partner).name.clone())
}
}
pub fn main() {
let susan = Rc::new(RefCell::new(Person {
name: "Susan".to_string(),
partner: None,
}));
let john = Rc::new(RefCell::new(Person {
name: "John".to_string(),
partner: Some(Rc::downgrade(&susan)),
}));
// Now we can actually set them to be each other's partner:
RefCell::borrow_mut(&susan).partner = Some(Rc::downgrade(&john));
// Both `susan` and `john` are still accessible
println!("John: {:?}", john);
println!(
"John's partner: {:?}\n",
RefCell::borrow(&john).partner_name()
);
println!("Susan: {:?}", susan);
println!(
"Susan's partner: {:?}\n",
RefCell::borrow(&susan).partner_name()
);
// Note that `susan` and `john` do not keep each other alive, as they
// are only `Weak` references. Therefore dropping the `Rc` handle
// Will cause the `Weak` handle to lose the connection.
drop(susan);
println!("John's partner after dropping Susan:");
println!("{:?}", RefCell::borrow(&john).partner_name());
}
John: RefCell { value: Person { name: "John", partner: Some((Weak)) } }
John's partner: Some("Susan")
Susan: RefCell { value: Person { name: "Susan", partner: Some((Weak)) } }
Susan's partner: Some("John")
John's partner after dropping Susan:
thread 'main' panicked at 'called `Option::unwrap()` on a `None` value', src/main.rs:16:51