Designing a Cursor for tree traversal and mutation

[jessegrosjean]

I have a tree structure like:

pub struct Tree {
    children: Vec<Tree>
}

1. I am using Cursor to do read-only tree traversals. The cursor maintains the current position in the tree by storing traversal state in a stack. I like the design and it's working well.

2. I would also like CursorMut to do read-write tree traversals. This cursor implementation is not passing the borrow checker. Storing mutable ancestors references in the traversal stack seems impossible. I think I understand each individual compiler error that I get, but maybe there's a way around the problems that I just can't figure out.

3. I have managed to get read-write tree traversals in CursorUnsafeMut. There I store raw pointers in the stack to get around the borrowing problems. This seems to work, though I haven't tested much beyond getting it to compile, and it's using unsafe code.

My questions...

1. Is there some way to CursorMut work without unsafe code?

2. If not then is it reasonable to store raw pointers in the stack as CursorUnsafeMut is doing?

pub struct Tree {
    children: Vec<Tree>,
}

// 1. Working, but read-only
pub struct Cursor<'a> {
    root: &'a Tree,
    stack: Vec<&'a Tree>,
}

// 2. Not compiling
pub struct CursorMut<'a> {
    root: &'a mut Tree,
    stack: Vec<&'a mut Tree>,
}

// 3. Working, but using unsafe code
pub struct CursorUnsafeMut<'a> {
    root: &'a mut Tree,
    stack: Vec<*mut Tree>,
}

impl<'a> Cursor<'a> {
    fn first_leaf(&mut self) -> &Tree {
        let parent = self.stack.last().unwrap_or(&self.root);
        if let Some(child) = parent.children.first() {
            self.stack.push(child);
            self.first_leaf()
        } else {
            parent
        }
    }
}

impl<'a> CursorMut<'a> {
    fn first_leaf_mut(&mut self) -> &mut Tree {
        let parent = self.stack.last_mut().unwrap_or(&mut self.root);
        if let Some(child) = parent.children.first_mut() {
            self.stack.push(child);
            self.first_leaf_mut()
        } else {
            parent
        }
    }
}

impl<'a> CursorUnsafeMut<'a> {
    fn first_leaf_mut(&mut self) -> &mut Tree {
        let mut root_prt = self.root as *mut Tree;
        let parent = self.stack.last_mut().unwrap_or(&mut root_prt);
        if let Some(child) = unsafe { (**parent).children.first_mut() } {
            self.stack.push(child);
            self.first_leaf_mut()
        } else {
            unsafe { &mut **parent }
        }
    }
}

(Playground)

[RustyYato]

Your unsafe version looks correct, but Rust can't prove that it is correct. This is one of the limitation of lifetimes. You can do away with the stack and get a 100% safe version. But that you can't cache results.

struct CursorMut<'a> {
    root: &'a mut Tree,
}

impl<'a> CursorMut<'a> {
    fn first_leaf_mut(&mut self) -> &mut Tree {
        let mut root = &mut *self.root;
        
        while !root.children.is_empty() {
            root = &mut root.children[0];
        }
        
        root
    }
}

Another reason why this doesn't work is because in Rust ptr: &mut T means a unique borrow to T. This means no aliasing except by pointers derived from this ptr. While derived pointers are active, you cannot use ptr.

Note that stack may violate this principle because you will have a unique reference in the stack that aliases root, but since they are not guaranteed to be derived from root, or that root won't be accessed while the items in the stack are active.

[jessegrosjean]

Thanks yet again.

I do want caching, so I'll try the unsafe version and see how far I get.