Edmund Smith
December 05, 2023
Reading time:
This is the third part of a series of posts on persian-rug, a Rust crate for interconnected objects. In the first part of this series, we described the problem in more detail, and part 2 gave some alternate solutions.
Let's go back to our soup of objects, in all their mutually interconnected glory. We've already seen that even creating such a soup is difficult in Rust, because such collections make enforcing memory safety very difficult.
In the previous part, we looked at the different trade-offs we can make in order to model this in Rust. We can risk the program crashing (RefCell
), deadlocking (Mutex
), or having stale duplicated data. Alternatively, we could pare down our links (Arc
).
But what if the handles to the objects could be weakened, such that having a handle didn't automatically allow you to take additional references to the pointed to object? Then you might be able to obtain a mutable reference to an object even when there are many handles for it, provided you can prove to Rust that none of those handles can be used to generate a new reference to it.
Here's the C++ example we started from:
class group; class user { std::vector<std::shared_ptr> groups; }; class group { std::optional<std::shared_ptr> leader; };
What if, in Rust, we did this:
struct User { groups: Vec<usize>, } struct Group { leader: Option<usize> } struct Container { users: Vec<User>, groups: Vec<Group> }
Now all of our User
objects are in one array, all of our Group
objects are in another, and everything is held in a single Container
. We can use indices into the arrays as our object handles. The important thing here is that you can only convert one of these indices into a reference if you already have a reference to the Container
instance as well.
This approach allows us to construct arbitrary collections of objects, and to mutate them. The compiler performs meaningful checking by tracking references to a Container
instance, freeing us from the responsibility we had with RefCell
. And there's no risk of deadlock, as there was with Mutex
.
However, now our handles - which are just array indices - can dangle, or be invalidated, and that is a general problem to overcome for this class of solutions. Nothing ensures our indices continue to point to the same thing, or indeed anything.
It's a bad joke, but perhaps it gives some idea of the purpose of persian-rug
: to make convenient container solutions like the one from the previous section, and to try to provide the broadest possible safety net around their use.
Here's what our example looks like again using persian-rug
:
rust use persian_rug::{contextual, persian_rug, Proxy}; #[contextual(Rug)] struct User { groups: Vec<Proxy<Group>>, } #[contextual(Rug)] struct Group { leader: Option<Proxy<User>> } #[persian_rug] #[derive(Default)] struct Rug(#[table] User, #[table] Group); let r: Rug = Default::default(); let u = r.add(User { groups: Vec::new() }); let g = r.add(Group { leader: Some(u) }); r.get_mut(&u).groups.push(g);
A Proxy
type is a type-safe wrapper over an index. You can pass a Proxy
to an instance of its container type, and get back a reference to the underlying T
. This is the most important thing persian-rug
offers: provided you follow the usage pattern outlined in the next section, you are guaranteed to receive a T
reference back for your Proxy
.
The contextual
attribute macro lets you declare what the container type for your struct is. There can only be one container for a given type in this system: a User
will never be contained in any other persian-rug
derived container than Rug
, and that will be verified by the compiler. As we shall see, this is a key part of the proxy guarantee just described.
The persian_rug
attribute causes the Rug
type to be expanded to contain two tables (essentially beefed up arrays), one for User
s and one for Group
s. It provides a standard interface for interacting with objects held by the Rug
.
A new proxy object can only ever come into existence from adding an item to a container. Since there is one container type that can ever hold objects of a given type, the originating container type for each proxy is unambiguous. If you have a Proxy
it came from a Rug
. If you only ever create one instance of each container type, then it is impossible to use a proxy with the wrong container: type checking will catch invalid uses.
persian-rug
currently does not permit object deletion. This is by far its biggest limitation, and we'll discuss it more in the next part. Banning deletion, in conjunction with the single instance of each container, means that if you have a Proxy
, and the container, the proxy is still valid. As we showed before, it came from the container you have (since there has only ever been one), and the underlying object cannot have been deleted, therefore it is still there.
To summarize: if you only ever instantiate each container type once, none of your proxies will ever dangle, and you will never fail to read back data you stored, nor will you read back the wrong data.
In the next part, we'll look at some other third-party solutions that follow the same ideas as persian-rug
, and talk about how to lift the most onerous restrictions in this crate: the lack of deletion, and the lack of checks that only a single container instance is ever created.
15/08/2024
After rigorous debugging, a new unit testing framework was added to the backend compiler for NVK. This is a walkthrough of the steps taken…
01/08/2024
We're reflecting on the steps taken as we continually seek to improve Linux kernel integration. This will include more detail about the…
27/06/2024
With each board running a mainline-first Linux software stack and tested in a CI loop with the LAVA test framework, the Farm showcased Collabora's…
26/06/2024
WirePlumber 0.5 arrived recently with many new and essential features including the Smart Filter Policy, enabling audio filters to automatically…
12/06/2024
Part 3 of the cmtp-responder series with a focus on USB gadgets explores several new elements including a unified build environment with…
06/06/2024
The final installment of a series explaining how Collabora is helping shape the video virtualization story for Chromebooks with a focus…
Comments (1)
Hojjat:
Dec 06, 2023 at 05:55 AM
Fantastic name!
Reply to this comment
Reply to this comment
Add a Comment