How to create a recursive queue?

Question

I am trying to implement a recursive queue using the trait Element<T> as a container for all the functions of the different nodes of the queue and two structs implementing it called Node<T> and End.

The Node<T> struct is supposed to handle all the functionality within the queue itself and the End struct's purpose is to deal with the case of the last node.

I've got the following code:

trait Element<T> {
    fn append_item(self, item: T) -> Node<T>;
}

struct Node<T> {
    data: T,
    successor: Box<dyn Element<T>>
}

impl<T> Element<T> for Node<T> {
    fn append_item(mut self, item: T) -> Node<T> {
        self.successor = Box::new(self.successor.append_item(item));
        self
    }
}

struct End;

impl<T> Element<T> for End {
    fn append_item(self, item: T) -> Node<T> {
        Node { data: item, successor: Box::new(self) }
    }
}

The problem is, that I get two errors:

1. Cannot move a value of type dyn Element<T>
2. The parameter type T may not live long enough

both on the same line in Node::append_item.

Now, I get why the first error occurs (because the size of dyn Element<T> cannot be statically determined) but I don't know how to work around it and I have no idea why the second error occurs.

Answer 1

Frxstrem already elaborated how to get around the need to move by using Box<Self> as receiver. If you need more flexibility in the parameter type (i.e. be able to hold on to references as well as owned types) instead of requiring T: 'static you can introduce a named lifetime:

trait Element<'a, T: 'a> {
    fn append_item(self: Box<Self>, item: T) -> Node<'a, T>;
}

struct Node<'a, T: 'a> {
    data: T,
    successor: Box<dyn Element<'a, T> + 'a>,
}

impl<'a, T: 'a> Element<'a, T> for Node<'a, T> {
    fn append_item(self: Box<Self>, new_data: T) -> Node<'a, T> {
        Node {
            successor: Box::new(self.successor.append_item(new_data)),
            ..*self
        }
    }
}

struct End;

impl<'a, T: 'a> Element<'a, T> for End {
    fn append_item(self: Box<Self>, data: T) -> Node<'a, T> {
        Node {
            data,
            successor: self,
        }
    }
}