如何在 Rust 中定义递归特征边界？

Question

首先，我知道如果我想定义一个递归结构我可以使用Box。例如，

struct LinkNode {
    next: Option<Box<LinkNode>>
}

impl LinkNode{
    fn get_next(&self) -> Option<Box<LinkNode>>{
        None
    }
    fn append_next(&mut self, next: LinkNode) -> Self{
        self
    }
}

但是如何通过模板或特征对象在这些结构上创建特征？由于fn append_next(...) -> Self的存在，我不能像这样直接创建一个trait对象：

pub trait Linkable {
    fn get_next(&self) -> Option<Box<dyn Linkable>>; 
    fn append_next(&mut self, next: impl Linkable) -> Self;
}

我们不能 return Option<Box<impl Linkable>> 或 impl Linkable fn get_next(&self).

然后我通过通用模板尝试了以下实现，但它不起作用。因为我在构造一个新的 LinkNode.

时需要递归地分配 T 的类型

pub trait Linkable<T:Linkable<T> + Clone> : Clone {
    fn get_next(&self) -> Option<Box<T>>;
    fn append_next(&mut self, next: T) -> Self;
}

我最终以这种方式实现了它，通过创建其他特征来提供帮助。它运作良好。再次...还有其他更好的方法吗？

pub trait Linkable: LinkClone{
    fn get_next(&self) -> Option<Box<dyn Linkable>>;
}

pub trait LinkAppend {
    fn append_next(&mut self, next: Box<dyn Linkable>) -> Box<dyn Linkable>;
}
pub trait LinkClone{
    fn clone_box(&self) -> Box<dyn Linkable>;
}

impl<T> LinkClonefor T
where
    T: 'static + Linkable+ LinkAppend + Clone,
{
    fn clone_box(&self) -> Box<dyn Linkable> {
        Box::new(self.clone())
    }
}

impl Clone for Box<dyn Linkable> {
    fn clone(&self) -> Box<dyn Linkable> {
        self.clone_box()
    }
}

顺便说一句，在上面的探索过程中我还有一些其他问题：为什么 Rust 禁止 impl Linkable 糖，比如 Box<impl Linkale>？为什么 returning impl Linkable 在特征中被禁止？

在 Ibraheem 的回答后更新：

除了来自Ibraheem的关联类型实现，这样也可以。核心思想是避免trait中的递归类型声明。

pub trait Linkable {
    fn get_next<T:Linkable>(&self) -> Next<T>; 
    fn append_next<T:Linkable>(&mut self, next: Next<T>) -> Self;
}

struct Next<T: Linkable> {
    node: T,
}

另一个question: Can I define a trait with a type parameter of itself in Rust?

中提到了这个

Answer 1

Linkable 可能具有名为 Next.

的关联类型

pub trait Linkable {
    type Next: Linkable;
}

get_next 现在 returns 类型 Self::Next 的实例，并且 append_next 将 Self::Next 作为参数：

pub trait Linkable {
    type Next: Linkable;
    
    fn get_next(&self) -> Option<Self::Next>;
    fn append_next(&mut self, next: Self::Next) -> &Self;
}

现在您可以为 Linknode 实施 Linkable:

impl Linkable for LinkNode {
    type Next = LinkNode;
    
    fn get_next(&self) -> Option<Box<LinkNode>> { 
        None
    }
    fn append_next(&mut self, next: LinkNode) -> &Self {
        self
    }
}

Why Rust forbids the impl Linkable sugar, like the Box? And why returning impl Linkable is forbidden in a trait?

这个问题的答案可以参考

如何在 Rust 中定义递归特征边界？

How to define a recursive trait bound in Rust?

rust

traits

trait-objects