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

Last modified: Sunday, 28 July 2019, 9:04 PM