Rust struct field generic over Deref<Target=Self>

Question

我正在尝试构建Rust代码，该代码处理递归(树状(数据结构。天真地，人们可以将其定义为

struct ALinkedList {
value: i32,
next: Option<Box<Self>>
}

为了试验不同的内存布局和将算法设计与存储分离，我想将定义推广到类似的东西

struct ALinkedList<D: Deref<Target=Self>> {
value: i32,
next: Option<D>
}

但是当试图构建ALinkedList的实例时，我得到了

64 |     let t: ALinkedList<Box<_>> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
|            ^^^^^^^^^^^^^^^^^^^ cyclic type of infinite size

我的问题是：

1. 有可能使这些递归类型定义在Rust中工作吗
2. 如果没有，我可以使用哪些其他设计模式来表示树状结构，而不必对其子级在内存中的存储和取消引用进行硬编码

Answer 1

不幸的是，Rust目前无法处理无限深度的泛型。

有一种方法可以绕过GAT(通用关联类型(，不幸的是，它仍然只在夜间使用(操场(：

#![feature(generic_associated_types)]
use std::ops::Deref;
struct ALinkedList<A: Allocator> {
value: i32,
next: Option<A::Allocated<Self>>
}
impl<A: Allocator> ALinkedList<A> {
fn set_next(&mut self, next: Self) {
self.next = Some(next.into()) // create a new allocation via From
}
}
trait Allocator {
type Allocated<T>: Deref<Target=T> + From<T>;
}
struct BoxAllocator;
impl Allocator for BoxAllocator {
type Allocated<T> = Box<T>;
}
fn main() {
let mut t: ALinkedList<BoxAllocator> = ALinkedList{value: 0, next: Some(Box::new(ALinkedList{value: 0, next: None}))};
t.set_next(ALinkedList{value: 1, next: None});
}