为什么由于"overflow while adding drop-check rules"无法实例化数据结构？

Question

这是一个我可以写下来并被 Rust 编译器接受的数据结构：

pub struct Pair<S, T>(S, T);

pub enum List<T> {
    Nil,
    Cons(T, Box<List<Pair<i32, T>>>),
}

但是，我不会写

let x: List<i32> = List::Nil;

playground

因为 Rust 会抱怨 "overflow while adding drop-check rules"。为什么不能实例化 List::Nil?

需要注意的是以下作品：

pub struct Pair<S, T>(S, T);

pub enum List<T> {
    Nil,
    Cons(T, Box<List<T>>),
}

fn main() {
    let x: List<i32> = List::Nil;
}

playground

Answer 1

当类型还没有被实例化时，编译器主要担心类型的 size 是常量并且在 compile-time 处已知，所以它可以被放置在堆栈上。如果类型是无限的，Rust 编译器会报错，并且经常一个 Box 将通过创建一个指向 child 节点的间接级别来解决这个问题，这是也是众所周知的大小，因为它也装箱了自己的 child。

不过这不适用于您的类型。

实例化List<T>时，Cons变体的第二个参数的类型是：

Box<List<Pair<i32, T>>>

注意内部 List 有一个类型参数 Pair<i32, T>，而不是 T。

该内部列表还有一个 Cons，其第二个参数的类型为：

Box<List<Pair<i32, Pair<i32, T>>>>

其中有一个 Cons，其第二个参数的类型为：

Box<List<Pair<i32, Pair<i32, Pair<i32, T>>>>>

以此类推

现在这并不能完全解释为什么不能使用这种类型。类型的大小将随着它在 List 结构中的深度线性增加。当列表很短（或为空）时，它不会引用任何复杂类型。

根据错误文本，溢出的原因与drop-checking有关。编译器正在检查该类型是否被正确删除，如果它在此过程中遇到另一种类型，它将检查 that 类型是否也被正确删除。问题是每个连续的 Cons 都包含一个全新的类型，你越深入它就越大，编译器必须检查它们是否会被正确删除。这个过程永远不会结束。

为什么由于"overflow while adding drop-check rules"无法实例化数据结构？

Why is it impossible to instantiate a data structure due to "overflow while adding drop-check rules"?

rust

data-structures

recursive-type