Data Branding in Rust

What is this good for?

Data branding can be used to solve the problem of having to validate indices into data collections over and over again. At compile time with almost no overhed.

That is, for example a list of values and an index into said list.

Oversimplified: One can create a collection, obtain a valid index and use it:

// Example collection
let mut list = vec!['a', 'b', 'c'];

// Obtain a known valid index
let index = list
	.iter()
	.position(|item| *item == 'b')
	.unwrap();

// Use the index for something
println!("Item '{}' is at index: {index}", list[index]);
// Output: Item 'b' is at index: 1

This code is pretty straight forward and it is easily verified that the index will always point at valid data.

But now imagine a more complex scenario where the code is doing real work, maybe on a mutable list and across multiple functions or with multiple collection because the problem at hand requires that and now you need the index again.

// Lots of other code

list[index] = 'x';

How do you know that the index is still valid, maybe an item has been removed and half the indices have shifted? That list in fact refers to the correct list and not some other list we confused it with over too much coffe and too little sleep?

Well you don't, the more complex the code is the harder it is to make sure you haven't mixed something up.

If only the compiler could make sure that mixing things up like that is impossible … long story short: It can.

How Branding Works

Time for some Attribution: This approach is from the first two chapters of the paper GhostCell - Separating Permissions from Data in Rust which goes into much more detail than I'll do here.

Branding is a clever hack on the rust type system that makes use of how lifetimes and mutable borrows interact to restrict index types to areas where it is impossible to invalidate them. This comes with the guarantee that when there is an instance of an index it is valid and can only be used with the collection that it belongs to.

If you have rust experience you might know about the "returns a reference to data owned by the current function".

// Take ownership of foo
// Don't worry too much about the static lifetime in the return,
// it is simply the easiest way to set this demo up
fn foo(foo: String) -> &'static Option<String> {

	// Return a reference to foo
	return &Some(foo); // This line will not compile
	
} // foo is dropped here at the end of the function,
  // the returned pointer would be invalid!

This shows that a borrowed value can't escape past the original value being dropped and the compiler will make sure this doesn't happen no matter how many indirections are involved.

This is the most important meachanism that makes branding possible.

This lifetime meachanism can then be used to seperate an inside where indices are never invalidated from an outside where the indices can't go, but operations that would invalidate them are allowed.

To acieve the seperation between an inside and an outside a callback is passed to a function that:

• Holds onto the data to make sure nobody else modifies it
• Creates the scope that is used to make sure that the indices don't escape
• Passes a data structure to the callback that is the "inside" that upholds the guarantees that are neccessary to never invlidate any identifiers (i.e. An read and append only interface for the underlying Vec)

Now you must be wondering how branding looks when in use.

Wonder no more:

let mut list = vec!['a', 'b', 'c'];

BrandedVec::new(&mut list, |branded_list: &mut BrandedVec| {
	let index = branded_list.find('b').unwrap();

	/// lot's of code

	branded_list[index] = 'x'; // This works, every time, guaranteed
});