This crate provides the struct Prison.visit() methods
that take closures that are passed mutable references to the values.
This documentation describes the usage of Prison.visit() methods, and how it achieves memory safety.
This package is still UNSTABLE and may go through several iterations before I consider it good enough to set in stone See changelog
I wanted a data structure that met these criteria:
- Backed by a [Vec
This crate is on crates.io
First, add this crate as a dependency to your project:
toml
[dependencies]
grit-data-prison = "0.2"
Then import [AccessError] and [CellKey] from the crate root, along with the relevant version you wish to use in
the file where it is needed (right now only one flavor is available, [single_threaded]):
rust
use grit_data_prison::{AccessError, CellKey, single_threaded::Prison};
Create a Prisoninsert() type methods
Note the following quirks:
- A Prison does not need to be declared mut to mutate it
- insert() and its variants return a [Result]<[CellKey], [AccessError]> that you need to handle
- You can ignore the [CellKey] and simply look up the value by index if you wish (shown later)
rust
let prison: Prison<String> = Prison::new();
let key_hello = prison.insert(String::from("Hello, "))?;
prison.insert(String::from("World!"))?;
You can then use one of the .visit() methods to access a mutable reference
to your data from within a closure
rust
prison.visit_idx(1, |val_at_idx_1| {
*val_at_idx_1 = String::from("Rust!!");
Ok(())
});
Visiting multiple values at the same time can be done by nesting .visit() calls,
or by using one of the batch .visit() methods
rust
prison.visit(key_hello, |val_0| {
prison.visit_idx(1, |val_1| {
println!("{}{}", *val_0, *val_1); // Prints "Hello, Rust!!"
Ok(())
});
Ok(())
});
prison.visit_many_idx(&[0, 1], |vals| {
println!("{}{}", vals[0], vals[1]); // Also prints "Hello, Rust!!"
Ok(())
});
```rust use gritdataprison::{AccessError, CellKey, single_threaded::Prison};
fn main() -> Result<(), AccessError> {
let prison: Prison
Operations that affect the underlying [Vec] can also be done
from *within* `.visit()` closures as long as none of the following rules are violated:
- The operation does not remove, read, or modify any element that is *currently* being visited
- The operation does not cause a re-allocation of the entire [Vec] (or otherwise cause the entire [Vec] to relocate to another memory address)
rust
let prison: Prison
Closures provide a safe sandbox to access mutable references, as they cant be moved out of the closure,
and because the visit() functions that take the closures handle all of the
safety and housekeeping needed before and after.
Since closures use generics the rust compiler can inline them in many/most/all? cases.
The short answer is: it should be mostly safe. I welcome any feedback and analysis showing otherwise so I can fix it or revise my methodology.
Prison follows a few simple rules:
- One and ONLY one reference to any element can be in scope at any given time
- Because we are only allowing one reference, that one reference will always be a mutable reference
- Any method that would or could read, modify, or delete any element cannot be performed while that element is currently being visited
- Any method that would or could cause the underlying [Vec] to relocate to a different spot in memory cannot be performed while even ONE visit is in progress
In addition, it provides the functionality of a Generational Arena with these additional rules:
- The Prison has a master generation counter to track the largest generation of any element inside it
- Every valid element has a generation attatched to it, and insert() operations return a [CellKey] that pairs the element index with the current largest generation value
- Any operation that removes or overwrites a valid element with a genreation counter that is equal to the largest generation causes the master generation counter to increase by one
It achieves all of the above with a few lightweight sentinel values:
- A single UnsafeCell to hold all of the Prison internals and provide interior mutability
- A master visit_count [usize] on Prison itself to track whether any visit is in progress
- A master generation [usize] on Prison itself to track largest generation
- Each element is either a Cell or Free variant:
- A Free Simply contains the value of the next free index after this one is filled
- A locked [bool] on each Cell that prevents getting 2 mutable references to the same element
- A generation [usize] on each Cell to use when matching to the [CellKey] used to access the index
(see performance for more info on specifics)
Attempting to perform an action that would violate any of these rules will either be prevented from compiling or return an [AccessError] that describes why it was an error, and should never panic.
rust
let prison: Prison<String> = Prison::new();
prison.insert(String::from("cannot be stolen"));
let mut steal_mut_ref: &mut String;
let mut steal_prison: Prison<String>;
prison.visit_idx(0, |mut_ref| {
// will not compile: (error[E0521]: borrowed data escapes outside of closure)
steal_mut_ref = mut_ref;
// will not compile: (error[E0505]: cannot move out of `prison` because it is borrowed)
steal_prison = prison;
Ok(())
});
```rust struct MyStruct(u32);
fn main() -> Result<(), AccessError> {
let prison: Prison
(Benchmarks are Coming Soon™)
Prison
Each element in [VecCell variant or Free variant, so the marker is only a [u8]
Free variant only contains a single [usize], so it is not the limiting variant
Cell variant contains a [usize] generation counter, [bool] access lock, and a value of type T
Therefore the total additional size compared to a [Vec
This crate is very much UNSTABLE, meaning that not every error condition may have a test, methods may return different errors/values as my understanding of how they should be properly implemented evolves, I may add/remove methods altogether, etc.
Possible future additions may include:
- [x] Single-thread safe PrisonAtomicPrison<T>
- [ ] ? Single standalone value version, JailCell<T>
- [ ] ? Multi-thread safe standalone value version, AtomicJailCell<T>
- [ ] ?? Completely unchecked and unsafe version UnPrison<T>
- [ ] ??? Multi-thread ~~safe~~ unsafe version AtomicUnPrison<T>
This crate is on crates.io The repo is on github
Feel free to leave feedback, or fork/branch the project and submit fixes/optimisations!
If you can give me concrete examples that definitely violate memory-safety, meaning that the provided mutable references can be made to point to invalid/illegal memory (without the use of additional unsafe :P), or otherwise cause unsafe conditions (for example changing an expected enum variant to another where the compiler doesnt expect it to be possible), I'd love to fix, further restrict, or rethink the crate entirely.