Struct UnsafeCursor 

pub struct UnsafeCursor<'a, T> { /* private fields */ }

An unsafe version of CursorMut

Principle

UnsafeCursor exists to overcome the limitation of CursorMut. In order to respect the Rust ownership system, mutable methods in CursorMut takes &mut self as signature. This means that has long as the as the mutable reference is alive, it is not possible to mutate the cursor, to navigate it around the tree, and to get a mutable reference to another node of the tree. If you had to mutate the tree in multiple place in a concurrent way, it would be impossible with CursorMut.

In order to achieve this, the narrator only sees two options :

• rewrite everything using RefCell and interior mutability (no.).
• implements a shotgun for the foot of the user of this crate (yes).

How do we achieve it

We simply change the signature of methods that return a mutable reference by fn peek_mut(&self) -> &mut T. Doing so disconnect the link that Rust was making between the &mut self and the &mut T returned (as a immutable reference would never produce a mutable reference). This mean that we can now navigate the UnsafeCursor while keeping the mutable reference alive, have multiples mutable reference alive and even multiples UnsafeCursor alive. But as great powers came with responsability, we also now can create two mutable references point at the same node

let mut tree = Tree::from_element(vec![10]);
let cursor1 = tree.unsafe_cursor();
let cursor2 = tree.unsafe_cursor();
let ref1 = unsafe { cursor1.peek_mut() };
let ref2 = unsafe { cursor2.peek_mut() };
// We now have two mutable references toward [10]

Safety

Using this unsafe cursor, we see that we have completly bypassed the rust ownership system, and it will be a problem. What you should avoid at all costs is having two mutable references (or more) that points at the same object.

But how to prevent this ? The first idea is to have only one UnsafeCursor that does a travel around the tree but never peek_mut twice on the same node (This how crate::Tree::lazyiter_mut is implemented). The second idea is to not keep the references, but the unsafe cursor and call peek_mut every times you need to mutate the elements stored. Doing so will always deliver a correct mutable reference, on the top of stack of pointer. This is why every mutable methods are marked as unsafe.

UnsafeCursor are safe as long as you make sure to not have two mutable reference (or a immutable reference followed by a mutable reference) on a same node of tree. The unsafe keyword is more to warn you about the risk of using UnsafeCursor, but it is up to you to verify that the use is safe.

To avoid shooting yourself in the foot, UnsafeCursor does not implement any iter methods, except for children but only as immutable reference (to decide to which branch to navigate).

A safe usage example

let mut tree = Tree::from_element(0);
tree.push_iter(vec![1, 2]);
let mut cursor1 = tree.unsafe_cursor();
let mut cursor2 = tree.unsafe_cursor();
cursor1.navigate_to(0);
cursor2.navigate_to(1);
unsafe {
assert_eq!(cursor1.peek_mut(), &mut 1);
assert_eq!(cursor2.peek_mut(), &mut 2);
}

Anyways, if you don’t need, don’t use it.

Implementations

impl<'a, T> UnsafeCursor<'a, T>

pub fn peek(&self) -> &'a T

Peek at ‘current’, returning a reference to the element stored in ‘current’.

Examples

let tree = Tree::from_element(10);
let cursor = tree.unsafe_cursor();
assert_eq!(cursor.peek(), &10);

pub unsafe fn peek_mut(&self) -> &'a mut T

Peek at ‘current’, returning a mutable reference to the element stored in ‘current’.

Safety

Bad usages of peek_mut can lead to two mutable references pointing at the same object. Be always sure when you use this method that no other mutable references or normal references are alive at the moment you use it.

Examples

let tree = Tree::from_element(1);
let cursor = tree.unsafe_cursor();
unsafe {assert_eq!(cursor.peek_mut(), &mut 1);}

pub fn peek_child(&self, index: usize) -> &'a T

Peek at ‘current’.childs[index], returning a reference to the element stored.

Examples

let mut tree = Tree::from_element(10);
tree.push(5);
let cursor = tree.unsafe_cursor();
assert_eq!(cursor.peek_child(0), &5);

pub unsafe fn peek_child_mut(&self, index: usize) -> &'a mut T

Peek at ‘current’.childs[index], returning a mutable reference to the element stored in child.

Safety

Bad usages of peek_child_mut can lead to two mutable references pointing at the same object. Be always sure when you use this method that no other mutable references or normal references are alive at the moment you use it.

Examples

let mut tree = Tree::from_element(10);
tree.push(5);
let cursor = tree.unsafe_cursor();
unsafe {assert_eq!(cursor.peek_child_mut(0), &5);}

pub fn navigate_to(&mut self, index: usize)

Set ‘current’ to ‘current’.childs[index], therefore navigating to this child

Examples

let mut tree = Tree::from_element(0);
tree.push(1);
let mut cursor = tree.unsafe_cursor();
cursor.navigate_to(0);
assert_eq!(cursor.peek(), &1);

Panics

This method will panic if index >= self.childs_len

pub fn ascend(&mut self)

Set ‘current’ to ‘current’.father, therefore navigating up.

Examples

let mut tree = Tree::from_element(0);
tree.push(1);
tree.navigate_to(0);
let mut cursor = tree.unsafe_cursor();
cursor.ascend();
assert_eq!(cursor.peek(), &0);

Panics

This method will panic if ‘current’ has no father i.e. if ‘current’.father.is_none()

pub fn has_father(&self) -> bool

Return true if ‘current’ has a father.

Examples

let mut tree = Tree::from_element(0);
tree.push(1);
tree.navigate_to(0);
let mut cursor = tree.unsafe_cursor();
assert!(cursor.has_father());
cursor.ascend();
assert!(!cursor.has_father());

pub fn childs_len(&self) -> usize

Return the number of childrens of current.

Examples

let mut tree = Tree::from_element(0);
tree.push_iter(vec![1, 1, 1, 1, 1]);
let cursor = tree.unsafe_cursor();
assert_eq!(cursor.childs_len(), 5);

pub fn iter_childs(&self) -> ChildIterator<'a, T>

Return an Iterator over the elements stored in ‘current’.childs

Examples

let mut tree = Tree::from_element(0);
tree.push_iter(vec![1, 2, 3]);
let cursor = tree.unsafe_cursor();
assert_eq!(cursor.iter_childs().collect::<Vec<&i32>>(), vec![&1, &2, &3]);

pub fn push(&mut self, el: T)

Push el to ‘current’.child as a new node in the tree.

Examples

let mut tree = Tree::from_element(1);
let mut cursor = tree.unsafe_cursor();
cursor.push(2);
cursor.navigate_to(0);
assert_eq!(cursor.peek(), &2);
assert_eq!(tree.into_vec(), vec![1, 2]);

pub fn push_iter<I>(&mut self, iter: I)

where I: IntoIterator<Item = T>,

Convenient method to push the elements of an iterator into the tree. It’s litteraly : for el in iter.into_iter() { tree.push(el) }

Examples

let mut tree = Tree::from_element(0);
let mut cursor = tree.unsafe_cursor();
cursor.push_iter(vec![1, 2, 3]);
cursor.navigate_to(2);
assert_eq!(cursor.peek(), &3);
assert_eq!(tree.into_vec(), vec![0, 1, 2, 3]);