I’m sharing the following in the hope that someone will find this interesting, or might want to point out possible problems with/alternatives to this approach.

Let’s say that in our library we have a type Something that can be modified in a way that can be expressed as a sequence of “patches”. That something could be an image, a 3d model, a graph, a database, a text buffer, etc. Let’s say that we routinely have to examine different sequences of (slight) modifications based on the same original, but we don’t want to clone the original many times, only to modify each clone and drop it.

We could introduce a type Overlay<'_> that stores a shared reference to an original Something plus the modifications to apply to it. Ideally Overlay values would allow the same operations that the original Something type allows. It might be even possible to chain several overlays. (This might be inefficient for long chains, but then long chains of overlays might not be needed.)

The nice thing about Rust is that it allows to implement the above pattern safely without any runtime cost like runtime reference counting or locking! It’s a simple idea, but it seems to be relevant to my work, and I think that it gives a nice example of the power of the borrow checker. I wonder if there are any libraries in the wild that utilize this pattern.

One problem with the idea is that since an overlay keeps a reference to an original, returning an overlay from a function or storing it somewhere is not straightforward. Here comes an idea how to mitigate this situation: we could introduce an operation, let’s call it “absorb”, that allows to absorb one overlay into the original. (Since this mutates the original, this is only allowed if no other overlays of the same original exist.) In this way, instead of returning an overlay, we can absorb it into the original.

If this “absorb” operation was a function, it would have to take a mutable reference to the original plus it would have to take ownership of the overlay to be absorbed (which includes a reference to the orignal). The borrow checker will not allow this.

But with a macro it’s possible! (The listing below demonstrates the technique.)

// A modifiable overlay of a Vec that behaves itself as a Vec.
// This toy version only allows extending the original.
#[derive(Debug)]
struct VecOverlay<'a, T> {
    orig: &'a Vec<T>,
    ext: Vec<T>,
}

macro_rules! absorb {
    (&mut $v:expr, $o:expr $(,)?) => {{
        // Make sure that the overlay refers to the original.
        assert_eq!(&($v) as *const _, ($o).orig as *const _);
        // We took possession of o, so we can as well mutate it.
        let mut o = ($o);
        // Append the supplement to the original.
        ($v).append(&mut o.ext);
    }};
}

fn main() {
    let mut v = vec![0, 1, 2];
    let mut o = VecOverlay { orig: &v, ext: vec![3] };

    // The overlay can be modified.
    o.ext.push(4);

    // There can be another overlay ...
    let mut o2 = VecOverlay { orig: &v, ext: vec![10, 11] };
    // ... that can be modified as well.
    o2.ext.push(12);

    // Absorb one overlay.  The macro effectively takes a mutable reference to a Vec and AT THE
    // SAME TIME takes ownership of a VecOverlay (that must refer to the same Vec).
    absorb!(&mut v, o);

    dbg!(&v);
}

2 posts - 2 participants

Read full topic