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.

Shared mutability

Consider that we have two entities in out program A and B. A knows about B, but B doesn’t know about A. We’ll draw this like so:

  • If an entity A knows about another entity B, then the danger zone for A includes the danger zone for B.
  • If an entity A does not know about another entity B, then B is outside the danger zone for A, because B can’t make A invalid by our definition of a reference.

Example problem.

For the purposes of this article we will look at a series of entities called tasks. Each task has a duration (in days) and a name. A task can only be completed after all of its dependencies have been completed. A task with no dependencies starts straight away. For this article, We’ll use the following example:

Solution 1: Freeform shared mutability.

In safe rust, we can share ownership using Rc. This means we don’t have to worry about how long something is going to live for; it will automatically be dropped when nothing else references it. To have shared mutability in a single threaded context, we can use RefCell. If we combine the two we can generate arbitrary graph like structures which have shared mutability. I mention this implementation for completeness, and advise that with almost certainty a RefCell inside of an Rc is an anti-pattern.

use std::cell::RefCell;
use std::rc::Rc;
#[derive(Clone, Eq, PartialEq, Debug, PartialOrd, Ord)]
pub struct InnerTask {
name: &'static str,
duration: u32,
dependencies: Vec<Task>,
}
#[derive(Clone, Eq, PartialEq, Debug, PartialOrd, Ord)]
struct Task(Rc<RefCell<InnerTask>>);
impl Task {
fn new (name: &'static str, duration: u32, dependencies: Vec<Task>) -> Self {
Task(Rc::new(RefCell::new(InnerTask {
name: name,
duration: duration,
dependencies: dependencies,
})))
}
fn set_duration (&self, duration: u32) {
self.0.borrow_mut().duration = duration;
}
fn start_time (&self) -> u32 {
(&self.0.borrow().dependencies)
.into_iter()
.map(|dependency| dependency.end_time())
.max()
.unwrap_or(0)
}
fn end_time(&self) -> u32 {
self.start_time() + self.0.borrow().duration
}
}
fn main () {
let lay_foundation =
Task::new("Lay Foundation", 10, vec![]);
let build_walls =
Task::new("Build Walls", 5, vec![lay_foundation.clone()]);
let build_roof =
Task::new("Build Roof", 11, vec![build_walls.clone()]);
let paint_walls =
Task::new("Paint Walls", 2, vec![build_walls.clone()]);
let furnish_house =
Task::new("Furnish House", 3, vec![build_roof.clone(), paint_walls.clone()]);
println!("Days require to finish house: {}", furnish_house.end_time());
}

Solution 2: An Arena.

The previous example has shared mutability, but no “internal consistency”. However, if we limit the spread of mutable references to entities that we trust not to break our structure, we can cache the results as much as we like. All the nodes themselves must be “trusted” since they could have a reference to any other node, and we can only give mutable references to “trusted” entities.

use std::collections::{HashMap, HashSet};
use std::hash::Hash;
use uuid::Uuid;#[derive(Debug, Clone, Eq, PartialEq)]
struct GraphNode<T> {
data: T,
incoming: HashSet<Uuid>,
outgoing: HashSet<Uuid>,
}
impl<T> GraphNode<T> {
fn new (data: T) -> Self {
GraphNode {
data: data,
incoming: HashSet::new(),
outgoing: HashSet::new(),
}
}
}
#[derive(Debug, Clone)]
pub struct Graph<T: Eq + Hash> (
HashMap<Uuid, GraphNode<T>>
);
impl<T: Eq + Hash> Graph<T> {
pub fn new() -> Self {
Graph(HashMap::new())
}
pub fn add_edge(&mut self, start: &Uuid, end: &Uuid) {
self.0.get_mut(start).map(|node| {
node.outgoing.insert(*end);
});
self.0.get_mut(end).map(|node| {
node.incoming.insert(*start);
});
}
pub fn remove_edge(&mut self, start: &Uuid, end: &Uuid) {
self.0.get_mut(start).map(|node| {
node.outgoing.remove(end);
});
self.0.get_mut(end).map(|node| {
node.incoming.remove(start);
});
}
pub fn remove_node(&mut self, node_id: &Uuid) -> T {
let node = self.0.remove(node_id).expect("remove_node: invalid key");
for start in node.incoming.iter() {
self.0.get_mut(start).map(|start_node| {
start_node.outgoing.remove(node_id);
});
}
for end in node.outgoing.iter() {
self.0.get_mut(end).map(|end_node| {
end_node.incoming.remove(node_id);
});
}
node.data
}
pub fn add_node(&mut self, node: T) -> Uuid {
let key = Uuid::new_v4();
self.0.insert(key, GraphNode::new(node));
key
}
pub fn get(&self, key: &Uuid) -> &T {
&self.0.get(key).expect("get: invalid key.").data
}
pub fn get_outgoing(&self, key: &Uuid) -> &HashSet<Uuid> {
&self.0.get(key).expect("get_outgoing: invalid key.").outgoing
}
pub fn get_incoming(&self, key: &Uuid) -> &HashSet<Uuid> {
&self.0.get(key).expect("get_incoming: invalid key.").incoming
}
}
#[derive(Clone, Eq, PartialEq, Hash, Debug, PartialOrd, Ord)]
pub struct Task {
name: &'static str,
duration: u32,
}
impl Task {
fn new (name: &'static str, duration: u32) -> Self {
Task {
name: name,
duration: duration,
}
}
}
struct GraphView<'a> {
graph: &'a Graph<Task>,
start_times: HashMap<Uuid, u32>,
end_times: HashMap<Uuid, u32>,
}
impl<'a> GraphView<'a> {
fn new (graph: &'a Graph<Task>) -> Self {
GraphView {
graph: graph,
start_times: HashMap::new(),
end_times: HashMap::new(),
}
}
fn end_time(&mut self, key: &Uuid) -> u32 {
// Boilerplate
if let Some(result) = self.end_times.get(key) {
return result.clone();
}

// Actual query
let result = self.graph.get(key).duration + self.start_time(key);
// Boilerplate
self.end_times.insert(key.clone(), result);
result
}
fn start_time(&mut self, key: &Uuid) -> u32 {
// Boilerplate
if let Some(result) = self.start_times.get(key) {
return result.clone();
}
// Actual query.
let result = self.graph.get_incoming(key)
.into_iter()
.map(|key_out| self.end_time(key_out))
.max()
.unwrap_or(0);
// Boilerplate
self.start_times.insert(key.clone(), result);
result
}
}
fn main() {
let mut graph = Graph::new();
let lay_foundation = graph.add_node(Task::new("Lay foundation", 1));
let build_walls = graph.add_node(Task::new("Build walls", 2));
graph.add_edge(&lay_foundation, &build_walls);
let build_roof = graph.add_node(Task::new("Build roof", 4));
graph.add_edge(&build_walls, &build_roof);
let paint_walls = graph.add_node(Task::new("Paint walls", 8));
graph.add_edge(&build_walls, &paint_walls);
let furnish_house = graph.add_node(Task::new("Furnish house", 16));
graph.add_edge(&paint_walls, &furnish_house);
let mut view = GraphView::new(&graph);
println!("Days require to finish house: {:?}", view.end_time(&furnish_house));
}
struct GraphView2<'a> {
graph: &'a Graph<Task>,
// Store an Option rather than the value itself.
// None means a circular reference
start_times: HashMap<Uuid, Option<u32>>,
end_times: HashMap<Uuid, Option<u32>>,
}
impl<'a> GraphView2<'a> {
fn new (graph: &'a Graph<Task>) -> Self {
GraphView2 {
graph: graph,
start_times: HashMap::new(),
end_times: HashMap::new(),
}
}
fn end_time(&mut self, key: &Uuid) -> Option<u32> {
if let Some(result) = self.end_times.get(key) {
return result.clone();
}
// We assume that a node is part of a circular reference
// until proved otherwise.
self.end_times.insert(key.clone(), None);

let result = self.start_time(key)
.map(|time| time + self.graph.get(key).duration);
self.end_times.insert(key.clone(), result);
result
}
fn start_time(&mut self, key: &Uuid) -> Option<u32> {
if let Some(result) = self.start_times.get(key) {
return result.clone();
}
self.start_times.insert(key.clone(), None);
let result = self.graph.get_incoming(key)
.into_iter()
.map(|key_out| self.end_time(key_out))
.fold(Some(0), |max_time, end_time| Some(max_time?.max(end_time?)));
self.start_times.insert(key.clone(), result);
result
}
}

Conclusion

I present two ways to construct code that has shared mutability in some kind of arbitrary acyclic graph structure in Rust. On one hand we have a freeform structure which involves Rc and RefCell. The disadvantage of this kind of structure is that we cannot cache results that depend on other entities. In addition, we have to be careful not to introduce reference cycles. It appears simple but has some complicated caveats.

The stories I write are a part of a learning journey through life, logic and programming. Share this journey with me.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store