How to define a recursive trait bound in Rust?

user_8481499 0
Viewed 734

First, I know I can use Box if I want to define a recursive structure. For example,

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
    }
}

But how can I make a trait on these structures via templates or trait object? Due to the existence of fn append_next(...) -> Self, I cannot create a trait object directly like this:

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

And we cannot return Option<Box<impl Linkable>> or impl Linkable for fn get_next(&self).

Then I tried the following implementation via generic templates and it does not work. Because I need to assign the type of T recursively when construct a new LinkNode.

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

I finally implement it in this way, by creating other traits for assistance. And it works well. Again...Is there other better ways?

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()
    }
}

BTW, I have some other questions during the exploration above: Why Rust forbids the impl Linkable sugar, like the Box<impl Linkale>? And why returning impl Linkable is forbidden in a trait?

Updated after Ibraheem's answer:

Except the associated type implementation from Ibraheem, it is also fine to work like this. The core idea is to avoid the recursive type declaration in the 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,
}

This is mentioned in another question: Can I define a trait with a type parameter of itself in Rust?

trait-objects rust traits
1 Answers

Linkable could have associated type called Next.

pub trait Linkable {
    type Next: Linkable;
}

get_next now returns an instance of type Self::Next, and append_next takes Self::Next as a parameter:

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

Now you can implement Linkable for Linknode:

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?

You can refer to Is it possible to use impl Trait as a function's return type in a trait definition? for the answer to this question.

user_88589950
Related