Recursive type and borrow checker issue

[torimus]

Trying to implement Binary tree data structure with all operations - creating, inserting, deleting, searching etc. in a mutable way, ie. without recreating tree but do changes in-place.

type definition:

pub trait Elem: PartialOrd + Clone + Debug {}
impl<T: PartialOrd + Debug + Clone> Elem for T {}

#[derive(Debug, Default, PartialEq)]
pub enum BinTree<T: Elem> {
    #[default]
    Empty,
    Node {
        value: T,
        left: Box<BinTree<T>>,
        right: Box<BinTree<T>>,
    },
}

insertion of an element was straightforward, using mutable reference:

impl<T: Elem> BinTree<T> {
    pub fn insert(&mut self, val: T) -> bool {
        match self {
            Self::Empty => {
                *self = Self::Node {
                    value: val,
                    left: Box::new(Self::Empty),
                    right: Box::new(Self::Empty),
                };
                true
            }
            Self::Node { value, left, right } => {
                if val < *value {
                    left.insert(val);
                } else if val > *value {
                    right.insert(val);
                } else {
                    return false
                };
                true
            }
        }
    }

now there is a struggle with deletion of an element, where subtree (behind Box) has to be moved - rebound. Shortened for simplicity:

pub fn delete(&mut self, val: T) -> bool {
    match self {
        Self::Empty => false,
        &mut BinTree::Node {
            ref value,
            ref mut left,
            ref mut right
        } => if val == *value {
            *self = **left;  // do I really need a clone of BinTree here??
            true
        } else {
            false
        },
    }
}

error[E0507]: cannot move out of **left which is behind a mutable reference
--> src/lib.rs:100:25
|
100 | *self = **left;
| ^^^^^^ move occurs because **left has type BinTree<T>, which does not implement the Copy trait

Can the re-assignment of a subbranch be rewritten in another way, without resolve to its cloning?

[kpreid]

You can use std::mem::take() to take ownership of the node and disassemble it into its branches. Then put back whatever replacement is appropriate.

use std::mem;

...

    pub fn delete(&mut self, val: T) -> bool {
        match mem::take(self) {
            Self::Empty => false,
            BinTree::Node { value, left, right } if val == value => {
                *self = *left;
                true
            }
            node => {
                *self = node;
                false
            }
        }
    }

[torimus]

Thank you, this does work.

Is this a canonical way how to handle such transformations for recursive types?
It seems for &mut T -> T move, it requires unsafe rust under the hood.

Should I rather design BinTree type in a different way? Is using Box special type here a complication? What about using plain references with lifetimes for recursive relation?

[kpreid]

@torimus

Is this a canonical way how to handle such transformations for recursive types?

It’s a canonical way to move data out of &mut. You want to rearrange the tree, so you have to move data out.

Should I rather design BinTree type in a different way?

Not for this reason.

However, a change you might want to make is to define the tree such that its public interface is a boxed node:

pub struct BinTree<T>(Box<Node<T>>);

enum Node<T> {
    Empty,
    Node {
        value: T,
        left: BinTree<T>,
        right: BinTree<T>,
    },
}

impl<T: Elem> BinTree<T> {
    // public methods here
}

This has several advantages:

• The enum Node is private, so users of the tree type cannot mutate the tree structure in ways which would break invariants (e.g. swapping left and right).
• You can write methods that apply to the whole tree separately from methods that are used recursively.
• Allocation and deallocation of the Box happens only when a node is created or destroyed, not when it is moved in or out of the root. This will tend to make your tree manipulation algorithms freer of clutter and may be more efficient.
• The root of the tree, that is owned by the user of the tree, is only Box sized instead of occupying the memory required for a T and two boxes.

Is using Box special type here a complication?

No, it is the normal way to design a tree.

What about using plain references with lifetimes for recursive relation?

You cannot build an ordinary data structure out of references. References borrow data owned by something else, and there is nothing else to borrow the tree nodes from.

You could technically build a tree whose nodes are owned by an allocator like typed-arena, but that would make it an “append-only” tree that can never free nodes. There are use cases for things like this, but “doing data structures 101 in Rust” is not one of them.

Also, even if we suppose all borrowing problems are magically solved, using references in place of Box would not affect your original problem.

[torimus]

Great answer, thanks. Still have a lot to learn it seems