In this case, if I try to drop the owner before the borrower, I get a compiler error:
use refbox::RefBox;
fn main() {
let owner = RefBox::new(42);
let borrow = owner.try_borrow_mut().unwrap();
consume_owner(owner);
}
fn consume_owner<T>(owner: RefBox<T>) {}
If they were both owners I would not get an error.
EDIT: Sorry, I agree that what is going on in your example does conflict with the idea of single ownership.
Obviously. You haven't create 2nd owner and thus haven't used them functionality which RefBox adds to the Box. There are no 2nd owner and compiler prevents abuse of the single one.
But if you do this:
use refbox::RefBox;
fn main() {
let owner = RefBox::new(42);
let weak = owner.create_ref();
let borrow = weak.try_borrow_mut().unwrap();
consume_owner(owner);
}
fn consume_owner<T>(owner: RefBox<T>) {}
Then you get two owners and everything compiles and works as expected.
You need shared ownership at some point if you want to modify your trees. Even if high level API doesn't need it.
The only question is: what API which temporary does that shared ownership would look like.
If that interface is safe and sound then it would, usually, give you two owners (like RefBox does), although operations which do higher-level things may hide that fact.
I agree with that, but it's not about whether RefBox have a nice, intuitive interface (it does have it, absolutely), but about whether we are avoiding âshared ownershipâ with it. And answer is: no, we are not avoiding it. We are hiding it.
I see, that's not what I expected. I thought:
RefBox while there was an active Borrow would give an error;Borrow then dropping the RefBox frees the memory where the actual value is stored;RefBox is dropped and there is a nonzero Ref count, the actual value is still dropped, but a structure remains containing the status, so that a remaining Ref could ask to borrow and be told the value has been dropped.Clearly this model is not what RefBox implements, as demonstrated by the two examples you gave.
The way to avoid the compilation error is to drop the RefBox while holding an active Borrow that was not directly created from that RefBox but instead indirectly, i.e. it was created from a weak Ref for the same RefBox.
In this case, not only the memory but also the value is not dropped immediately. Instead, the value will be dropped as soon as the Borrow is dropped, and the memory will still be freed only once the last Ref is dropped.
It's the model which RefBox is actually trying to implement, but it has one corner case which you haven't considered: what if someone would try to drop RefBox when there are active Borrow created from Weak reference?
Alternatives are, basically, two:
Borrow goes away.RefBox have picked #1 there.
I thought that when you borrow from a Ref that was created from a RefBox, both the Ref and the RefBox would go into borrowed state. Then one would get an error if trying to drop the RefBox, saying the RefBox can't be dropped while borrowed.
So the compiler can detect when we try to drop a RefBox which is directly borrowed, but not when we try to drop a RefBox which has been borrowed via a Ref? That seems to be the case, but I'm not sure I understand why.
Sure. They would do that. But only information about Ref is known to the compiler statically! RefBox would also go into borrowed state â but only in runtime.
One would get an error if there would be an attempt to drop Ref. But since compiler have to idea Ref and RefBox are related at all (that was our goal, when we introduced Weak references, refcounting, updates and the whole machinery, remember?), it can not prevent us from dropping RefBox.
Yes.
The whole point of adding weak references (in a Rc form or RefBox form) was to allow us to remove that check. If you can organize your data in a way where compiler can clearly see owner of the data and borrower from that data there are no need for refcounting, weak references and other such things. Lifetimes would ensure that your program is correct.
But if that's impossible (and you said that you understand why that's impossible in a Tree-like data structure) then this check must be moved from compile-time to runtime.
But then, if you moved that check from compiler-time to runtime⌠you have to do something when it fails.
And, as I have said, there are only two sound choices:
And if you picked #2 route (which is much safer route since in that case the worst scenario is some memory waste and not meltdown of your program), then, obviously, borrow from Ref becomes 2nd shared owner of the object.
It's kinda ârestricted ownerâ, because it can not reenable the whole RefBox machinery. But it may keep value alive for as long as it's needed and you can pass that Borrow-which-is-not-borrow to another function, etc.
Thanks! This makes a lot of sense. I think I have really learned a lot from the whole discussion in this thread.
This is why it's using Rc. Parent pointers are a huge ownership mess.
Remove the parent links and you won't need Rc.
@mlharaujo If you don't want to deal with multiple ownership in tree structures, have a look at the ĂŹndextree crate.
It uses an arena internally and creates node relationships by indexing into a Vec.
From their docs:
This arena tree structure is using just a single
Vecand numerical identifiers (indices in the vector) instead of reference counted pointers like. This means there is noRefCelland mutability is handled in a way much more idiomatic to Rust through unique (&mut) access to the arena. The tree can be sent or shared across threads like aVec. This enables general multiprocessing support like parallel tree traversals.
Modeling relationships between data through indices is a very common approach in Rust to circumvent "ownership mess".
Of course, there are also downsides to this approach: for example index-based data structures are not well suited, when you need to frequently delete nodes from it's structure, because you need to either:
or
Having said that, indextree does all of this for you, so you don't need to manage this yourself.
If you are further interested in "modeling data structures with indices", I can highly recommend the following blog post by @nikomatsakis, where I've taken the above information from:
Thanks! My point here was really to learn about reference counting and shared ownership, but I will look into this crate as well!
There are many tree implementations, 3 of them are:
The linkage fields( parent, child ) in #1 and #2 can be implemented with:
raw pointers.
This is what std LinkedList does. Analogy: trees are lists in two dimensions. Good news: it's straightforward for C/C++ guys. Bad news: too many usnafe in implementations.
reference counters and interior mutability.
This is what you see in the Rust book. Good news: we can have a lesson about Rc/RefCell. Bad news: we may be confused why accessing to child nodes requires shared ownership -- this is what you ask in this thread. Worse news: Rust beginners may get an impression that the rusty way of implementing trees are using Rc/RefCell( get rid of evil raw pointers ), and, let's make them pub in API for convenience!
Vec index.
Let's pretend that index is not pointer - oh no, it never is. Good news: no unsafe, and we get a memory pool. Bad news: we have to use two integers instead of one integer. The "memory pool parameters" are spread all over the API( I didn't want to know if the tree is planted in a memory pool or not. And, as @janriemer said, downsides for deletion.
The #3 is less general and more domain specific so let's pass it.
By the way, you can have a look at trees, when you want to learn about raw pointers.
It provides both exclusive and shared ownership, scattered(LinkedList alike) and contiguous storage(memory pool alike).
This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.