Shared mutability in Rust Part 2 of 3: Acyclic graphs

Summary

• Child entities which are both mutable and shared can make any, or all of their parents invalid.
• In freeform shared mutability, we cannot cache any calculation that depends on a shared mutable entity.
• If we limit the scope of sharing to code we trust not to invalidate our cache, then we can cache results as much as we like.
• Limiting the scope of sharing implies that we have some kind of container entity: an Arena.

Interfaces, encapsulation and references.

First of all a disclaimer. I’m going to use the terms such as “interface” and “encapsulation”, and I’m going to define them a little bit differently to normal. It may be a bit strange, but hopefully it will make sense.

Instead of writing some code and trying to fix it, let’s try creating some good code first try. I won’t guarantee that it’s performant, but I’ll settle for (mostly) correct. To do that, we have to somehow prove that our code works. Generally speaking, we start off logical derivation with some definitions.

We imagine an entity A which is part of your program. A holds some data, which can either be in a valid state or invalid. If A ever manages to get into an invalid state and stay there, then we say that our program is broken. Sometimes we need to break A temporarily when we are transitioning from two valid states. To ensure that A doesn’t…