在 Deref<Target=Self> 上泛型的 Rust 结构字段

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(通用关联类型)的方法，不幸的是仍然只在夜间使用(playground):

#![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});
}