The Generativity Pattern in Rust

blog@​arhan.sh:~$ █

The Generativity Pattern in Rust

Published

• 39 min read<br>• more posts View on

This article was peer-reviewed by my close friends Henry Rovynak, Kartavya Vashishtha, Jack Hogan, Mikhail Khan and Crystal Durham. I thank them for their invaluable feedback. This article also uses special characters like the em-dash (—). These characters were lovingly hand-inserted and are not the result of AI-generated text.

Table of Contents

Introduction

Background

Permutations

Permutation groups

The unsafe approach

The atomic ID approach

The generativity approach

The fundamental purpose

Why the implementation caveat?

How does generativity work?

min_generativity

The first part

The second part

The third part

Verifying soundness

Language support

Benchmarks

Conclusion

Introduction

The generativity pattern in Rust is a combination of typestate and GhostCell, techniques that move what you’d normally check at run-time to compile-time. This pattern is not commonplace; its usage warrants a specific set of circumstances. However, it is a hugely important part of garbage collection utilities and other niche Rust crates.

Aside from thinly spread academic literature1, I haven’t found an accessible analysis of this pattern online. In order to build up a full picture of the “what” and more importantly the “why,” we will first spend some time walking through a realistic example to gauge the type of problem the generativity pattern solves—statically requiring data to come from or refer to the same source—as a stronger form of ownership. Then, we will introduce the generativity pattern and explain how to use it in the latter half of this article. Finally, we will follow up with a study of Crystal Durham’s generativity crate, a novel improvement to the generativity pattern. Buckle up!

Background

Permutations

Let us take the role of a crate author about permutations. We want to investigate the composition of zero-indexed permutations. This can be expressed nicely visually.

Permutation composition𝑎=(2,1,4,3,0)𝑏=(4,3,0,2,1)↓↓↓↓↓𝑎⋅𝑏=(𝑎(4),𝑎(3),𝑎(0),𝑎(2),𝑎(1))=(0,3,2,4,1)

The permutation b defines the remapping of the elements from permutation a. Pretty simple. Notice that permutation composition is only possible under the following three conditions:

a and b must have the same length.

Every element from a and b must be non-negative and less than the length.

Every element from a and b must be unique.

Our library is general-purpose, so it is important to handle these error cases. Here is the simplest way to do that.

/// We provide a `compose_into` function in case the caller already<br>/// has a permutation preallocated. (This is good practice IMO).<br>pub fn compose_into(a: &[usize], b: &[usize], result: &mut [usize]) -> Result(), &'static str> {<br>if a.len() != b.len() || b.len() != result.len() {<br>return Err("Permutations must have the same length");<br>let mut seen_b = vec![false; a.len()];<br>let mut seen_a = vec![false; b.len()];<br>for (result_value, &b_value) in result.iter_mut().zip(b) {<br>if *seen_b<br>.get(b_value)<br>.ok_or("B contains an element greater than or equal to the length")?<br>return Err("B contains repeated elements");<br>seen_b[b_value] = true;

let a_value = a[b_value];<br>if *seen_a<br>.get(a_value)<br>.ok_or("A contains an element greater than or equal to the length")?<br>return Err("A contains repeated elements");<br>seen_a[a_value] = true;

*result_value = a_value;<br>Ok(())<br>Good on you if this made your Rust senses tingle because we shouldn’t have to validate a and b every time. Rust allows us to enforce at the type level that they are valid permutations, using the newtype design pattern.

pub struct Permutation(Box[usize]>);

impl Permutation {<br>pub fn from_mapping(mapping: Vecusize>) -> ResultSelf, &'static str> {<br>// This function errors if `mapping` is an invalid<br>// permutation or its length does not match the second<br>// argument. The implementation is ommitted.<br>validate_permutation(&mapping, mapping.len())?;<br>Ok(Self(mapping.into_boxed_slice()))

pub fn compose_into(&self, b: &Self, result: &mut Self) -> Result(), &'static str> {<br>if self.0.len() != b.0.len() || b.0.len() != result.0.len() {<br>return Err("Permutations must have the same length");<br>for (result_value, &b_value) in result.0.iter_mut().zip(&b.0) {<br>// SAFETY: `b` is guaranteed to be a valid permutation<br>// whose elements can index `self`<br>*result_value = unsafe { *self.0.get_unchecked(b_value) };<br>Ok(())

pub fn compose(&self, b: &Self) -> ResultSelf, &'static str> {<br>let mut result = Self(vec![0; self.0.len()].into_boxed_slice());<br>self.compose_into(b, &mut result)?;<br>Ok(result)<br>Unsafe is going to be a recurring theme here. You’ve had your fair warning.

The newtype pattern is more useful than just for getting around the orphan rule. We restrict construction of Permutation to Permutation::from_mapping, which returns an error if the input is not a valid permutation. That means if we have an instance of Permutation, we...