Interior mutability, tree algorithms and the mindset

[reevik]

I am working on a tree algorithm. Inner nodes are used to navigate to the leaves, where the data resides. You can consider inner nodes to be index keys. The tree provides a query(index_key: String) method. While traversing down the tree, we compare the index_key provided with the index_keys stored in inner nodes. The query method should take a second argument, which is a closure implementing the logic for different operations, e.g.,

query(&self, index_key: String, op: impl FnMut() -> Vec<& Records>) -> Vec<& Records>

The method is implemented by Inner and Data nodes and should return modified (updated, deleted or found) records back. My dilemma is, whenever I use interior mutability, which looks like a logical option here, I am unable to return & Record references because the method calls borrow() to iterate through the children on a node, and the compiler complains:

cannot return value referencing temporary value

If I use references, since the op closure modifies the vectors in structs while iterating the tree, I need to use & mut references, which is a dead-end:

query(& mut self, index_key: String, op: impl FnMut() -> Vec<& mut Records>) -> Vec<& mut Records>

Because at some point I need another reference to the same struct, for example, to find out the number of children in a node etc., which is not allowed.

How does your design approach and mindset if you take on a Rust project? Meanwhile, I noticed that just focusing the algorithm doesn't help much.

[steffahn]

One easy solution, if that's sufficient for your use case, would be to just offer only API accepting a visitor-style FnMut(Vec<&Record>) callback.

For more specific solutions avoiding this, you might want to share a bit more about how, where and why the use of interior mutability exists. Maybe even some code example - you're already quoting compilation errors anyway, so you could share what you have so far.

[paramagnetic]

@reevik

I am unable to return & Record references because the method calls borrow() to iterate through the children on a node, and the compiler complains:

Return Vec<Ref<'_, _>> instead.

It's not possible to get long-lived borrows to the wrapped value of a RefCell. Just think about it — what would happen if it were allowed and then you called borrow_mut()? It would be very obviously unsound.

You have to access the contents of a RefCell through the Ref guard.