如何在Rust中定义递归的trait bound？

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，我不能直接创建一个特征对象如下：

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

我们无法返回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禁止像Box<impl Linkable>这样的impl Linkable语法糖？以及为什么在trait中返回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,
}

这在另一个问题中有提到：在Rust中，我能否定义一个具有其自身类型参数的trait？。

- Forsworn

---

另一个值得考虑的选项是将关联类型用于特质。根据您的使用方式，这可能更可取。 - user1937198

@user1937198 谢谢。这是一个好主意。我认为在编译期间使用关联类型或泛型会更有效率。trait object 的成本很高吗？我知道它是通过动态分派实现的，类似于 C++ 中的虚方法。 - Forsworn

这取决于你对“巨大”的定义。主要成本在于内联和动态分派。值得知道的是，动态指针的大小是C++的两倍，但除此之外，它与C++并没有太大区别。 - user1937198

成本取决于你正在做什么。对于某些事情来说，它只是噪音。对于其他事情来说，它是禁止的。一般来说，最好避免动态分派，除非你的设计确实需要它。 - Acorn

Answer 1

Linkable 可以有一个叫做 Next 的关联类型。

pub trait Linkable {
    type Next: Linkable;
}

get_next现在返回类型为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
    }
}

为什么 Rust 禁止像 Box 一样使用 impl Linkable 语法糖？为什么在 trait 中返回 impl Linkable 是禁止的？

您可以参考 在 trait 定义中，是否可能使用 impl Trait 作为函数的返回类型？ 来获取答案。

- Ibraheem Ahmed