Techniques for accessing data from a pool

I am working on a kind of type-safe "database" for an application. Here is a quite simplified dummy API:

fn get(d: &D, i: I) -> &X;
fn get_mut(d: &mut D, i: I) -> &mut X;

A user defines a helper function, wants to use if with some data and runs into a familiar problem:

fn foo(x1: &mut X, x2: &X);
foo(get_mut(d, 42), get(d, 43)); // ERR: cannot borrow as immutable because 
                                 //      it is also borrowed as mutable

My question: Which techniques can be used to solve this problem using a flexible API with little inconvenience for the user while providing maximum performance and safety?

Here are the techniques I am currently aware of to solve this problem:

  1. Unsafe:
fn get(d: &D, i: I) -> &X;
fn get_mut(d: &D, i: I) -> &mut X;  // magic &mut X from &D

Unsafe code is used to magically create a &mut field from a & database. This is a great way to shoot yourself in the foot.

  1. Copy:
fn get(d: &D, i: I) -> X;  // note the copy
fn get_mut(d: &mut D, i: I) -> &mut X;
fn foo(x1: &mut X, x2: X);
let x2 = get(d, 43); // need a temporary to get the order right
foo(get_mut(d, 42), x2);

All read operations create copies. This comes with considerable performance cost for larger data structures. It also still only allows a single &mut reference at the same time, so user functions which want multiple &mut are still not possible. It also requires some weird temporary arguments to call the get functions in the right order.

  1. Tuple get:
fn get(d: &mut D, i: (I, I)) -> (&X, &mut X);  // fails if `i.0 == i.1`
fn foo(x1: &mut X, x2: &X);
let (x2, x1) = get((43, 42));
foo(x1, x2);

The get function provides multiple references at the same time with a single function call. It checks internally that no mutable references to the same fields are returned. The example below is a bit crude but with the help of macros this can be extended to allow arbitrary tuples and specification which ones to return with & and which with &mut references. If any &mut are involved still only a single of these functions can be called at the same time, i.e. a second call to get would be rejected by the compiler with a borrow error.

  1. Interior mutability:
fn get(d: &D, i: I) -> Ref<X>;
fn get_mut(d: &D, i: I) -> RefMut<X>;  // RefMut can be safely created from &D
fn foo(x1: RefMut<X>, x2: Ref<X>);
foo(get_mut(d, 42), get(d, 43));

Borrow rules are ensured with runtime reference counting. This has a small runtime overhead due to the counting and user code needs to deal with potential borrow errors (i.e. from try_borrow) at runtime. The big disadvantage I see with this method is that it changes the API of user code: foo now takes Ref<X> and cannot be used with a "normal" &X anymore leading to severe code duplication for the user.

Example code for playground with dummy implementation. Note that in my application D and types like X are non-trivial.

type D = Vec<i32>;
type I = usize;
type X = i32;

fn get(d: &D, i: I) -> &X {

fn get_mut(d: &mut D, i: I) -> &mut X {
    &mut d[i]    

fn foo(x1: &mut X, x2: &X) {
    *x1 = *x2 + 1;

fn main() {
    let mut d = vec![0; 100];
    let d = &mut d;
    foo(get_mut(d, 42), get(d, 43));

That's an understatement. It's instant UB.

Collection types face this same question, so you could look to see what they do. Copying or cloning out values and interior mutability are approaches which users of a collection type can generally choose to use themselves. I'm not sure if that's true of interior mutability in your case (are "users" choosing the types?), but with a traditional get(&self, key: &Key) -> &Value the user can still copy or clone the Value when needed; it doesn't need to baked into the API.

I.e. you may not need to build in either of those approaches to your API in order for them to be utilized.

The tuple approach is similar to the experimental HashMap::get_many_mut method.

Depending on how your pool works, you could perhaps implement some sort of borrow splitting to segment the pool into non-overlapping subsets:

fn split_based_on<F>(&mut self, f: F) -> (&mut Self, &mut Self)
    F: FnMut((&Key, &Value)) -> bool, // spitballing

Like a generalized split_at_mut.

1 Like

This is great technique! Thank you

Isn't that essentially how RefCell::borrow_mut magically produces a RefMut which can derf into a &mut although borrow_mut only takes a &self argument?

No. RefCell is build on top of UnsafeCell, a language primitive which enables "interior mutability" or "shared mutability". It doesn't transmute &T to &mut T, it calls UnsafeCell::get (or maybe raw_get) after guaranteeing there are no outstanding shared references.

There's no way to emulate the language primitive's magic with transmute.

  • Transmuting an & to &mut is always Undefined Behavior.
  • No you can't do it.
  • No you're not special.

This topic was automatically closed 90 days after the last reply. We invite you to open a new topic if you have further questions or comments.