How to implement a mutable cactus stack in Rust?

Question

A Cactus Stack or Parent Pointer Tree is a stack where nodes in the stack have pointers to their parent so the stack is climbable in multiple ways.

I'm trying to implement a mutable Cactus Stack in Rust based off of this immutable implementation using the Rc<RefCell<T>> pattern to pass around shared memory:

use std::rc::Rc;
use std::cell::RefCell;

#[derive(Clone, Default)]
pub struct Cactus<T> {
    node: Option<Rc<RefCell<Node<T>>>>,
}

#[derive(Clone)]
pub struct Node<T> {
    val: Rc<RefCell<T>>,
    parent: Option<Rc<RefCell<Node<T>>>>,
    len: usize,
}

impl<T> Cactus<T> {
    pub fn new() -> Cactus<T> {
        Cactus { node: None }
    }

    pub fn is_empty(&self) -> bool {
        self.node.is_none()
    }

    pub fn len(&self) -> usize {
        self.node.as_ref().map_or(0, |x| x.borrow().len)
    }

    pub fn child(&self, val: T) -> Cactus<T> {
        Cactus {
            node: Some(Rc::new(RefCell::new(Node {
                val: Rc::new(RefCell::new(val)),
                parent: self.node.clone(),
                len: self.node.as_ref().map_or(1, |x| x.borrow().len + 1),
            }))),
        }
    }

    pub fn parent(&self) -> Option<Cactus<T>> {
        self.node.as_ref().map(|n| Cactus {
            node: n.borrow().parent.clone(),
        })
    }

    pub fn val(&mut self) -> Option<Rc<RefCell<T>>> {
        self.node.map(|n| n.borrow_mut().val.clone())
    }
}

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

    #[test]
    fn test_simple() {
        let r = Cactus::new();
        assert!(r.is_empty());
        assert_eq!(r.len(), 0);
        assert!(r.val().is_none());
        assert!(r.parent().is_none());
        let r2 = r.child(2);
        assert!(!r2.is_empty());
        assert_eq!(r2.len(), 1);
        assert_eq!(*r2.val().unwrap(), 2);
        let r3 = r2.parent().unwrap();
        assert_eq!(r3.is_empty(), true);
        assert_eq!(r3.len(), 0);
        let r4 = r.child(3);
        assert_eq!(r4.len(), 1);
        assert_eq!(*r4.val().unwrap(), 3);
        let r5 = r4.parent().unwrap();
        assert!(r5.is_empty());
        let r6 = r4.child(4);
        assert_eq!(r6.len(), 2);
        assert_eq!(*r6.val().unwrap(), 4);
        assert_eq!(*r6.parent().unwrap().val().unwrap(), 3);
    }    
}

playground

My issue is getting the val from nodes:

error[E0308]: mismatched types
  --> src/main.rs:64:9
   |
64 |         assert_eq!(*r2.val().unwrap(), 2);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
   |
   = note: expected type `std::cell::RefCell<{integer}>`
              found type `{integer}`
   = note: this error originates in a macro outside of the current crate

error[E0308]: mismatched types
  --> src/main.rs:70:9
   |
70 |         assert_eq!(*r4.val().unwrap(), 3);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
   |
   = note: expected type `std::cell::RefCell<{integer}>`
              found type `{integer}`
   = note: this error originates in a macro outside of the current crate

error[E0308]: mismatched types
  --> src/main.rs:75:9
   |
75 |         assert_eq!(*r6.val().unwrap(), 4);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
   |
   = note: expected type `std::cell::RefCell<{integer}>`
              found type `{integer}`
   = note: this error originates in a macro outside of the current crate

error[E0308]: mismatched types
  --> src/main.rs:76:9
   |
76 |         assert_eq!(*r6.parent().unwrap().val().unwrap(), 3);
   |         ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^ expected struct `std::cell::RefCell`, found integral variable
   |
   = note: expected type `std::cell::RefCell<{integer}>`
              found type `{integer}`
   = note: this error originates in a macro outside of the current crate

Answer 1

I am afraid that you lost yourself here by just trying to throw Option, Rc and RefCell at the issue.

Those are not cure-all, you need to understand when they make sense, and when they don't.

Here is the revised definitions I arrived at:

pub struct Cactus<T>(Option<Rc<Node<T>>>);

struct Node<T> {
    value: RefCell<T>,
    parent: Cactus<T>,
    len: usize,
}

Disclaimer: I have tried to infer where you actually need mutability, and where you don't, since you never actually explained it. My inference may have been incorrect in places; for example I decided that switching parents was unnecessary.

Let's analyze Node:

1. Node uniquely owns it value, it never shares it, therefore there is no point for Rc here.
2. Node may be aliased, and yet you still want to modify its value, this requires wrapping the value in a RefCell.
3. Node always has a parent, because Cactus already embeds a concept of nullity.

and Cactus:

1. Cactus may be null, so it's an Option.
2. Cactus shares its node with others, so Rc is required.
3. Cactus never needs to switch to another Node, it can directly mutate the shared node instead, so RefCell is unnecessary.

From there, we can implement Clone for Cactus (the automatic derivation fails hard):

impl<T> Clone for Cactus<T> {
    fn clone(&self) -> Self { Cactus(self.0.clone()) }
}

Note the use as_ref to obtain a &Rc in the lambda; without it, the map_or call would try to move the Rc out of self.0 which is forbidden because self is borrowed.

The other functions follow as naturally:

impl<T> Cactus<T> {
    pub fn new() -> Cactus<T> { Cactus(None) }

    pub fn is_empty(&self) -> bool { self.0.is_none() }

    pub fn len(&self) -> usize { self.0.as_ref().map_or(0, |n| n.len) }

    pub fn child(&self, val: T) -> Cactus<T> {
        let node = Node {
            value: RefCell::new(val),
            parent: self.clone(),
            len: self.len() + 1,
        };
        Cactus(Some(Rc::new(node)))
    }

    pub fn parent(&self) -> Cactus<T> {
        self.0.as_ref().map_or(Cactus(None), |n| n.parent.clone())
    }

    pub fn value(&self) -> Option<&RefCell<T>> {
        self.0.as_ref().map(|n| &n.value)
    }
}

Note that I changed a few signatures:

1. parent returns Cactus, which may be null. I do not make the difference between having a null parent and being null; this is questionable, I just felt that having a possibly null Cactus wrapped in an Option was bizarre.
2. value returns a reference to RefCell (wrapped in Option), so that the caller can call borrow_mut and mutate the actual value.

This required a few adaptations to the tests:

#[test]
fn test_simple() {
    let r = Cactus::new();
    assert!(r.is_empty());
    assert_eq!(r.len(), 0);
    assert!(r.value().is_none());
    assert!(r.parent().is_empty());

    let r2 = r.child(2);
    assert!(!r2.is_empty());
    assert_eq!(r2.len(), 1);
    assert_eq!(*r2.value().unwrap().borrow(), 2);

    let r3 = r2.parent();
    assert_eq!(r3.is_empty(), true);
    assert_eq!(r3.len(), 0);

    let r4 = r.child(3);
    assert_eq!(r4.len(), 1);
    assert_eq!(*r4.value().unwrap().borrow(), 3);

    let r5 = r4.parent();
    assert!(r5.is_empty());

    let r6 = r4.child(4);
    assert_eq!(r6.len(), 2);
    assert_eq!(*r6.value().unwrap().borrow(), 4);
    assert_eq!(*r6.parent().value().unwrap().borrow(), 3);
}

Mostly, as you can see, calling .borrow() after .unwrap().

Of note, the latest line fails to compile: r6.parent() returns a temporary value out of which we attempt to obtain a reference; the compiler complains that this reference is used after the temporary is dropped, probably as a detail of how assert_eq is implemented.

   |
74 |         assert_eq!(*r6.parent().value().unwrap().borrow(), 3);
   |         ^^^^^^^^^^^^-----------^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
   |         |           |
   |         |           temporary value created here
   |         temporary value dropped here while still borrowed
   |
   = note: values in a scope are dropped in the opposite order they are created
   = note: consider using a `let` binding to increase its lifetime
   = note: this error originates in a macro outside of the current crate

Simply replacing r6.parent() by r4 fixes this issue.