Implementing a dynamic-typed LinkedList in Rust

Question

This is a follow-up on the question asked here: Possible to implement dynamically-typed linked list in safe Rust?

I successfully implemented a dynamic type LinkedList using the std::any::Any trait.

However, I want to challenge myself by trying to implement it in another way, e.g. using generic type - Node where T can be any type, u32, u64, String, ...

Example

Node<String> -> Node<u32> -> Node<u64> -> Node<String> -> ...

My approach is to use a trait called Next to give Node<T> the ability to "go next".

Node<T> looks like this.

struct Node<T> {
    data: T,
    next: Option<Rc<RefCell<dyn Next>>>,
}

The trait Next looks like this.

pub trait Next {
    fn borrow_next(&self) -> Option<Ref<dyn Next>>;
    fn set_next(&mut self, next: Rc<RefCell<dyn Next>>);
}

These are the implementation of Next for any Node.

impl<T> Next for Node<T> {
    fn set_next(&mut self, next: Rc<RefCell<dyn Next>>) {
        self.next = Some(next);
    }

    fn borrow_next(&self) -> Option<Ref<dyn Next>> {
        match &self.next {
          None => None,
          Some(stmt) => Some(stmt.borrow()),
        }
    }
}

Here are the implementations for the actual struct Node<T>.

impl<T> Node<T> {
    pub fn new<P>(data: P) -> Node<P> {
        Node::<P> { data, next: None }
    }

    pub fn new_wrapped<P>(data: P) -> Rc<RefCell<Node<P>>> {
        Rc::new(RefCell::new(Node::<P>::new(data)))
    }

    pub fn into_wrapped(self) -> Rc<RefCell<Self>> {
        Rc::new(RefCell::new(self))
    }

    pub fn borrow_data(&self) -> &T {
        &self.data
    }

    pub fn set_data(&mut self, data: T) {
        self.data = data;
    }
}

Lastly, the declaration and its implementations of methods of struct DynLinkedList, holding two fields, head and tail, look like this.

struct DynLinkedList {
    head: Option<Rc<RefCell<dyn Next>>>,
    tail: Option<Rc<RefCell<dyn Next>>>,
}


impl DynLinkedList {
    pub fn new_empty() -> Self {
        Self {
            head: None,
            tail: None,
        }
    }

    pub fn new_with_node(node: Rc<RefCell<dyn Next>>) -> Self {
        Self {
            head: Some(node.clone()),
            tail: Some(node),
        }
    }

    pub fn append(&mut self, node: Rc<RefCell<dyn Next>>) {
        self.tail.take().map_or_else(
            || self.head = Some(node.clone()),
            |old_tail| old_tail.borrow_mut().set_next(node.clone()),
        );
        self.tail = Some(node);
    }
}

Here comes the problem:

I am unable to access the data field of Node<T> as it is being treated as a trait object dyn Next by the compiler.

For example, this test would not work:

#[cfg(test)]
mod tests {
  use super::*;

  #[test]
  fn test_dynll_new_with_node() {
    let node = Node::<u32>::new(77_u32);
    let dynll = DynLinkedList::new_with_node(node.into_wrapped());
    assert_eq!(&dynll.head.unwrap().borrow().borrow_data(), &77);
    assert_eq!(&dynll.tail.unwrap().borrow().borrow_data(), &77)
  }
}

The compiler error is:

error[E0599]: no method named `borrow_data` found for struct `Ref<'_, (dyn Next + 'static)>` in the current scope
   --> src/dyn_ll_idea_five.rs:125:47
    |
125 |     assert_eq!(&*dynll.head.unwrap().borrow().borrow_data(), &77);
    |                                               ^^^^^^^^^^^ method not found in `Ref<'_, (dyn Next + 'static)>`

But, when the .borrow() after .unwrap() returns, it should return an object of type Node which would have the method .borrow_data(), how can I let Rust know that this is the case? Thank you.

I would effectively want to be able to do this:

let mut list = DynLinkedList::new();

list.push_front("hello".to_string());
list.push_back("world".to_string());
list.push_front(123);
list.push_back(456);

assert_eq!(list.pop_front(), Some("hello".to_string()));
assert_eq!(list.pop_back(), Some("world".to_string()));
assert_eq!(list.pop_front(), Some(123));
assert_eq!(list.pop_back(), Some(456));

Answer 1

Well, nowhere in the definition of trait Next does it talk about objects of type Node. Thus, how would the compiler ever know that you can call borrow_data on it? That's where you'd do the downcast via the Any trait.

What's more, the compiler would also want to know which sort of Node we're talking about. Node<i32> or Node<String> or what? And that's downright impossible because your list is dynamic and hence whatever type is contained within a node is also dynamic.

Let's take your example:

Node<String> -> Node<u32> -> Node<u64> -> Node<String> -> ...

So if that's your list, then, using very rough ugly pseudocode, what about this:

let x: String = my_list.head.borrow_data();
let y: u32 = my_list.head.next.borrow_data();
let z: u64 = my_list.head.next.next.borrow_data();

You see the problem here? How is the compiler to know, at compile time, that the third item in the list has type u64? This just isn't a case where generics work in the way you want it.