Cells and Rc

http://github.com/pdx-cs-rust/rust-misc/cells-and-refcounts

Interior Mutability and Reference Counting

• Rust borrow checker is quite conservative in its static rules for ownership

  • References must not outlive referents

• Reader/writer model

  • One mut ref or many shared refs

  • Owner participates in model

• This makes some data structures hard to build

  • Even a simple counter can't really be shared by two data structures under these rules: if either parent is able to mutate it, the other can't even read it

Idea 1: Interior Mutability

• Maybe we could make it so we sometimes do writes into an object without having mutable access to it?

• This sounds dangerous: the whole point of the borrow checker is to keep two things from read-modify-writing the same location at the same time

• Compromise: Check at run time that the borrow rules are followed. Then code can read-modify-write, drop the reference, and someone else can start in

• Can implement this with a wrapper data structure Cell / RefCell that tracks borrowing

• Hazard: If the borrow rules are violated at run time, it's a panic. The compiler can't help anymore

Idea 2: Reference Counting

• Maybe we could track actual lifetime of objects at runtime instead of having the compiler over-approximate it?

• This sounds hard: this plan normally requires a garbage collector, and those are expensive and need language support

• Compromise: Use reference counting; keep track of a count of the number of references to an object and drop it when the count goes to 0

• Can implement this with a wrapper data structure that does the reference counting

• Hazard: it is possible to create reference cycles, which keep objects alive forever

Weak References

• It is possible to create a weak reference: one that acts like a Rc except no reference counting is done, so the inner value could be dropped. See std::rc::Weak

• This is a way to build e.g. tree nodes with weak parent references

• Weak pointers are still safe, so the worst that can happen is runtime panic

• This is a very specialized type: typically using it means that the design should be rethought