I recently came across the situation where I wanted to replace a mutable reference with something else that contains it. See this toy example. For obvious reasons, the borrow checker does not allow this.
However, since the value of the mutable reference is immediately replaced with something else, much like mem::swap does, I think there should be a safe way to do this. I was hoping I could overcome this by using either (or a combination of) mem::replace and mem::swap so as not to litter the code with unsafe blocks. I could not find a way, however. I ended up implementing the following helper function:
fn swap_using<T, F>(x: &mut T, f: F)
where F: FnOnce(T) -> T
{
unsafe {
let y = mem::replace(x, mem::uninitialized());
*x = f(y);
}
}
The toy example can then cleanly be written like this.
I wonder
- if there was another way of solving this problem without changing the struct or passing by value;
- whether this helper function (regardless of its implementation) would make a useful addition to the
core::mem module.
This is basically the same as the closed RFC for mem::replace_with. The biggest challenge is what to do when that function panics.
Beware, if your type implements Drop, this assignment to *x will call x.drop() first -- on your uninitialized value! This is why the RFC used ptr::write to just clobber the existing contents.
1 Like
Thank you very much for the clarification!
I was a bit disappointed to hear that the RFC got closed (or at least postponed). It was quite an interesting read. I guess I can use the take_mut crate that the RFC refers to, for now.
I am still curious how other programmers solve this.
- By using a different data structure? (e.g. using
Option and Option.take)
- By using two
mem::replaces with a nonsense/default value?
- By using the aforementioned crate or by implementing a something helper function?
- By using unsafe code?
- Something I haven't thought about?
One thought: since you're already committed to moving self into newly-allocated memory, why not let Rust do it?
Consuming self is great if that fits your usage model. But I think that only helps here if you're only inserting at the root of the tree, otherwise you'd have the same problem about moving out of parent nodes.
Using Option is not too bad, or in this toy example I might add an Empty variant to your enum Tree. You might want to have the possibility of an empty root anyway, right? Then insert is just:
impl<T> Tree<T> {
pub fn insert(&mut self, item: T) {
let x = std::mem::replace(self, Tree::Empty);
*self = Tree::Branch(Box::new(x), Box::new(Tree::Leaf(item)))
}
}
Or since you probably want to normalize Empty away, more like:
impl<T> Tree<T> {
pub fn insert(&mut self, item: T) {
if let Tree::Empty = *self {
*self = Tree::Leaf(item);
} else {
let x = std::mem::replace(self, Tree::Empty);
*self = Tree::Branch(Box::new(x), Box::new(Tree::Leaf(item)));
}
}
}
1 Like
Thank you for sharing your thoughts!
@derspiny: Yeah, I think I agree with @cuviper that passing by value doesn't seem to fit here because it is only changing a small part the tree. (Or maybe I should re-evaluate my views which are probably biased by other languages. Feel free to tell me!)
@cuviper: When looking at other implementations of trees in Rust, they were indeed almost always using Option. Your alternative also totally makes sense in this toy example. The kind of tree where this problem arose, is a sort of "partition tree". I modelled it like this:
struct PartitionTree<'a, T: 'a, D: 'a> {
root: Option<Node<'a, T, D>>,
scope: Option<Range<T>>,
}
enum Node<'a, T: 'a, D: 'a> {
Leaf { start: T, end: T, data: &'a D },
Branch {
left: Box<Node<'a, T, D>>,
right: Box<Node<'a, T, D>>,
free: Range<T>,
},
}
I don't know if this structure makes sense. Feel free to share your thoughts. The cool thing about it, is that by not using empty variants, you can simplify the code handling it, because you only have to consider two cases (a leaf or a branch) instead of four cases (a branch with no children (empty leafs), branch with a left child, a branch with a right child and a branch with two children).
OK, but this model still doesn't have a way to represent temporary node absence, right? So you can either add an Empty variant, or make the branch children Option<Box<Node>>, but either way the cases you have to consider are about the same. Or you can very carefully dip into unsafe code to move stuff.
The good news is that both safe options are free in memory size, as Empty is just another discriminant value, and Option<Box<_>> uses the fact that Box's pointer is never null to represent None vs Some. So the only cost is having to deal with possibly-absent nodes everywhere, even when this is only supposed to happen temporarily in isolated cases.
@cuviper: You're right. However, checking everywhere for nodes that are None or Empty which can never happen except at the root, was what I was trying to avoid by structuring it like this.
Maybe a combination of what @derspiny and you suggest might be the best of both worlds? See this example. The wrapper struct with Option allows ownership on the inner struct, while still providing the same external interface. I think I am happy with this.
What do you think?
I think that only lets you insert at the root, and other tree operations like balance and remove will be difficult. But try it and see how it goes! 
This is what I have so far for the partition tree I mentioned earlier. Only the insert operation is implemented at the moment. The version using take_mut looks a lot cleaner and shorter though because it doesn't involve reconstructing and passing self around. Yeah, I guess we'll see how the balancing, removal and iteration goes.
Thank you for the interesting conversation!