We're hiring!
*

Persian Rug, Part 3 - The warp and the weft

Edmund Smith avatar

Edmund Smith
December 05, 2023

Share this post:

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.

Back to the future: indices

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 really ties the room together

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.

Collabora - Persian Rug


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 Users and one for Groups. It provides a standard interface for interacting with objects held by the Rug.

The proxy guarantee

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.

Next

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.


Add a Comment






Allowed tags: <b><i><br>Add a new comment:


Search the newsroom

Latest Blog Posts

Almost a fully open-source boot chain for Rockchip's RK3588!

21/02/2024

Now included in our Debian images & available via our GitLab, you can build a complete, working BL31 (Boot Loader stage 3.1), and replace…

What's the latest with WirePlumber?

19/02/2024

Back in 2022, after a series of issues were found in its design, I made the call to rework some of WirePlumber's fundamentals in order to…

DRM-CI: A GitLab-CI pipeline for Linux kernel testing

08/02/2024

Continuing our Kernel Integration series, we're excited to introduce DRM-CI, a groundbreaking solution that enables developers to test their…

Persian Rug, Part 4 - The limitations of proxies

23/01/2024

This is the fourth and final part in a series on persian-rug, a Rust crate for interconnected objects. We've touched on the two big limitations:…

How to share code between Vulkan and Gallium

16/01/2024

One of the key high-level challenges of building Mesa drivers these days is figuring out how to best share code between a Vulkan driver…

Google Open Source Peer Bonus 2023

19/12/2023

Google Open Source have chosen their second group of winners for the 2023 Google Open Source Peer Bonus Program, and Arnaud Ferraris, Senior…

Open Since 2005 logo

We use cookies on this website to ensure that you get the best experience. By continuing to use this website you are consenting to the use of these cookies. To find out more please follow this link.

Collabora Ltd © 2005-2024. All rights reserved. Privacy Notice. Sitemap.