This is the fourth part in a series of posts on persian-rug, a Rust crate for interconnected objects. Part 1 described the problem in more detail, part 2 gave some alternate solutions. and part 3 introduces `persian-rug` in more detail.

We've touched on the two big limitations of persian-rug in the previous part: lack of deletion and lack of enforced matching between proxies and containers. Is it feasible to remedy them? We can start by looking at other solutions in this area.

Alternative crates

persian-rug is by no means the only crate based on these ideas. For example, indextree [1] provides doubly-linked trees of objects of a single type in one managed array. Deleted items are not immediately removed, but are first flagged and removed from the hierarchy. There's an attempt via versioning to detect handles that refer to previous nodes that occupied the same location in the container. There's no attempt to detect handles from one container instance being accidentally passed to another container.

slotmap [2] provides long-lived handles which can become invalid through deletion, but which will never refer to a different object. Storage is once more for objects of a single type. It suggests, but cannot enforce, creating a new handle type for each collection instance in order to avoid accidents.

typed_index_collections [3] provides arrays whose indices are strongly typed. Deletion is supported, but there's no attempt to provide the higher level checking the other crates offer. Exactly the same caveats around multiple containers apply to this crate as all of the others, including persian-rug.

ghost-cell [4] [5] is the most intriguing option. Rather than a single container for controlling access, we now have a "token" which fulfills the same purpose: a reference to the token grants you the ability to get references to the guarded objects. Not only this, but each instance of the token type is made effectively its own type, via a clever abuse of the lifetime mechanism in Rust, which means the compiler will catch accidental mismatches between instances. Deletion is not supported at all here.

Object deletion

Supporting deletion brings trade-offs. Currently, there is no failure case to consider when retrieving an object from a proxy, and the crate's complexity is modest. In many cases, actually deleting objects is not necessary in the lifetime of a program, and here the current behaviour is adequate.

There are two basic approaches we can take if we want deletion. Retrieving a reference from a proxy could be allowed to fail, as we see in slotmap and indextree. Alternatively, we could track and then wipe all handles that refer to data when it is removed.

The first option has consequences for the clarity of code written using the crate. Code trying to obtain a reference from a proxy might just unwrap the result, but then we have only added noise to our clients. Alternatively, that code must consider in each case what remediation to take if the required object has been deleted. In any case, we have an inconsistent graph and that imposes costs.

The second option is far more complex. It amounts to requiring anything holding a Proxy to implement some trait enabling us to wipe it. In practice that would mean that there would be two kinds of proxies: within the collection, everything would implement the interface and the representation would have managed proxies that never dangle. Proxies held outside the collection would behave as the first option and permit failure when obtaining a reference.

Matching proxies to collections

In the current version of persian-rug you can still cause a panic (or worse, you can read the wrong data) if you instantiate your rug twice, and then mingle the proxies from the two sources. Every other crate we reviewed based on this idea has the same issue, except for ghost-cell.

The compile time checking that ghost-cell offers is ingenious, but it is also impractical in its current form. Using lifetimes in the way it does is really a hack, and one that may be extremely hard to maintain. First class language support for types that have compile-time distinguishable instances (also known as brands) would really be required to get this quality of a solution.

Run-time checking in contrast is feasible. It does imply creating mutable static data for each collection type, which creates some complexity within the crate itself. In this case, we could distinguish instances, and panic when a proxy was handed to a container instance that did not create it.

Conclusion

This has been a brief introduction to persian-rug, a newly released crate for creating unstructured object graphs in Rust. The approach it represents is a fairly well established one in the Rust community. Where it differs principally from other crates is in being able to represent object graphs of heterogeneous types, and in providing a lighter API by virtue of lacking deletion.