Crate persian_rug

Expand description

This crate provides a framework for managing arbitrary mutable graphs of objects that link to one another. This is a pattern which is difficult to replicate in Rust, because of the ownership model, but is common in the wider software ecosystem.

Overview and motivation

In the case where you have truly arbitrary graphs, most of an object’s dependencies cannot be usefully represented as being owned by that object. For example, consider two types, Foo and Bar:

struct Foo {
    bars: Vec<Bar>
}

struct Bar {
    my_special_foo: Option<Foo>
}

If no one Foo is the sole owner of a Bar (each Foo holds a subset of available Bars), and no one Bar is the sole owner of any given Foo (the same Foo could be special for multiple Bars), then we end up with multiple copies of every object in this representation, and maintaining consistency is likely to be difficult.

We might next try to use reference counting smart pointers for the links between objects, but neither Rc nor Arc gives us mutability on its own. If we then consider using Mutex to provide mutability, we end up with something like this:

use std::sync::{Arc, Mutex};

struct Foo {
    bars: Vec<Arc<Mutex<Bar>>>
}

struct Bar {
    my_special_foo: Option<Arc<Mutex<Foo>>>
}

in which each object is individually lockable to permit mutation. But there is no meaningful lock order here, and deadlock is all but assured.

The approach taken in this crate is to store everything inside one container (a Context) which gives a single location for locking. Only the Context has ownership of data, everything else is granted a Proxy which can be resolved using the Context into a reference to the real object. We use attribute macros to remove most of the boilerplate: contextual matches a type to its owner, and persian_rug builds a suitable owner.

That means the example using this crate looks like this:

use persian_rug::{contextual, persian_rug, Proxy};

#[contextual(MyRug)]
struct Foo {
  bars: Vec<Proxy<Bar>>
}

#[contextual(MyRug)]
struct Bar {
  my_special_foo: Option<Proxy<Foo>>
}

#[persian_rug]
struct MyRug(#[table] Foo, #[table] Bar);

We will need to have an instance of MyRug available whenever we want to read the contents of a Foo or a Bar. If we have a mutable reference to the context, we can change any Foo or Bar we wish.

The Persian Rug

A Context provides the ability to insert, retrieve and iterate over items by type. It can only support one collection of items per type.

Please note: this crate does not support deletion of objects at present.

use persian_rug::{contextual, persian_rug, Context, Proxy, Table};

#[contextual(C)]
struct Foo<C: Context> {
  _marker: core::marker::PhantomData<C>,
  pub a: i32,
  pub friend: Option<Proxy<Foo<C>>>
}

impl<C: Context> Foo<C> {
  pub fn new(a: i32, friend: Option<Proxy<Foo<C>>>) -> Self {
    Self { _marker: Default::default(), a, friend }
  }
}

#[persian_rug]
struct Rug(#[table] Foo<Rug>);

let mut r = Rug(Table::new());
let p1 = r.add( Foo::new(1, None) );
let p2 = r.add( Foo::new(2, Some(p1)) );
let p3 = r.add( Foo::new(3, Some(p2)) );
r.get_mut(&p1).friend = Some(p3);

Context read access is provided to implementations of Accessor whose context matches. Shared references to the context are accessors, as are Arcs, MutexGuards and RwLockReadGuards.

Write access is provided to implementations of Mutator whose context matches. Exclusive references to the context are mutators, as are MutexGuards and RwLockWriteGuards. If you enable the clone-replace feature, you can also use MutateGuards for this.

To prevent accidental misuse, each participating type must declare its context by implementing Contextual, and can only belong to one context. This apparent restriction is easily lifted by making the context a generic parameter of the participating type. The constraints attribute can help with the boilerplate needed to use generic parameters in this way.