Help with using the `generativity` pattern to create an Editor where indexes into file contents are checked at compile-time

[nik-rev]

I'm trying to make an editor based on the generativity crate. Pattern is described in this blog post. My editor will have many commands that operate on text. I want to maximize type safety by having an Index<'id>(usize, Id<'id>) newtype that is branded with a non-unifiable lifetime 'id and guarantees it is in-bounds for any FileContents<'id>.

The FileContents represents contents of each file:

#[repr(transparent)]
pub struct FileContents<'id>(String, Id<'id>);

The Index<'id> newtype represents a usize that is known to always be in-bounds for any FileContents with the identical 'id

#[repr(transparent)]
pub struct Index<'id>(usize, Id<'id>);

impl Index {
    /// **Safety:** `index` must be in-bounds for `TextContents` with the same `'id`
    unsafe fn new(index: usize, id: Id<'id>) {
        Self(index, id)
    }
}

• FileContents[Index] is an infallible operation.
• unsafe code should be able to rely on the property that an Index<'id> can never hold a usize that is out-of-bounds for the FileContents<'id>

FileContents<'id> must be invalidated on any mutation that could invalidate existing Index<'id>s, so we must consume self and return the modified version:

impl<'id> FileContents<'id> {
    pub fn new(content: String, guard: Guard<'id>) -> Self {
        FileContents(content, guard.into())
    }

    /// If the `index` is in-bounds, promote it to `Index<'id>` which is
    /// statically known to always be in-bounds
    pub fn char_index(&self, index: usize) -> Option<Index<'id>> {
        if index < self.0.len() {
            // SAFETY: We just checked that `index` is in-bounds
            Some(unsafe { Index::new(index, self.1) })
        } else {
            None
        }
    }

    /// This method mutates our file. Because mutation can invalidate existing indexes,
    /// we must consume the old one and return new with the `'new_id` lifetime.
    ///
    /// This means that any existing `Index<'id>` are invalidated, which is what we want
    pub fn insert_at<'new_id>(
        self,
        content: &str,
        index: Index<'id>,
        new_guard: Guard<'new_id>,
    ) -> FileContents<'new_id> {
        let mut s = self.0;
        s.insert_str(index.0, content);
        FileContents(s, new_guard.into())
    }

    pub fn content(&self) -> &str {
        &self.0
    }
}

I managed to implement an editor that can only edit or keep 1 file in memory, ever. That was easy, I just had a single Guard<'id> at the top which outlives everything. When I need to mutate FileContents, I safely transmute it.

fn main() {
    make_guard!(guard);
    let guard: Guard<'_ /* long */> = guard;

    // Just have a single file in our "editor"
    let mut file: FileContents<'_ /* 'long */> = FileContents::new("foo", guard);

    let mut insert_at = 2; // after "foo"

    // Simulate user typing 4 characters
    for ch in " baz".chars() {
        let index: Index<'_ /* long */> = file.char_index(insert_at).unwrap();

        make_guard!(edit_guard);

        let new_file: FileContents<'_ /* 'short */> = file.insert_at(ch, index, edit_guard);

        // SAFETY: Each iteration of the loop creates a "new world", so we can safely transmute
        //         'short to 'long because 'long outlives 'short, and we don't use `index` created here
        //         in the next iteration of the loop.
        let new_file: FileContents<'_ /* 'long */> = unsafe { std::mem::transmute(new_file) };
        file = new_file;

        insert_at += 1;
    }

    assert_eq!(file.content(), "foo bar");
}

Now here is the hard part, and one that, I don't even know if it is possible. Editors can handle as many files as they want, they can have many of them open at the same time. I want to have a global context that I pass around, which contains all of my opened files:

struct EditorContext {
    files: Vec<FileContents<'?>>,
    current_file: usize
}

impl EditorContext {
    fn insert_text(&mut self, text: &str) { ??? }
}

But putting the 'id lifetime on the EditorContext will be incorrect - each item there must have its own unique lifetime.

I'm struggling to come up with an architecture for an Editor that makes use of this pattern. We start with 0 files. We can open files 1, 2, 3 4. They each have unique 'id lifetimes. We then remove some files. Execute commands on the 1st file and 2nd file etc. How is any of this possible?

Is the thing I'm trying to do just fundamentally impossible / unsound, or are there some workarounds I could do? I really want to create an editor where every command is as type-safe as possible. Where I can guarantee that given an Index, LineIndex etc that they are in-bounds.

Would appreciate some help!

[quinedot]

This is a little meandering as I brainstormed while writing it.

---

Rust lifetimes only exist at compile time, as an analysis of your source code. At compile time, you can approximate this concept as only having one guaranteed-unique^[1] lifetime per source-code-occurrence of make_guard!. (So in your main, you have two.^[2]) And those lifetimes are erased during compilation. You can't dynamically make more at run time (you can't make any -- the borrow checker has done its job, erased all lifetimes, and that metadata is long gone).

So IMO you need some other approach to segment out different files, some sort of encapsulation where it's not possible for different file flows to exchange lifetime branded things.

One way to do this would be to have the global storage store unbranded files. The brands are only created when kick off some subtask. generativity lifetimes are limited to lexical scope anyway. Nothing branded would exist when the subtask completes; if you want branded state to persist, have some way to store it in unbranded form when the subtask completes, too.

This approach starts looking more like GhostCell than generativity.

---

If you wanted to store the branded FileContents<'_> anyway... honestly I don't think it's a great fit with generativity. In a general sense, you can use dyn SomeTrait + '_ to erase the invariant lifetimes and store the objects together. But the way generativity works is by making sure every make_guard! Guard gets invalidated by the next time that occurrence of the macro in the source code is called, within a single body... otherwise you could create non-unique guards in a loop.

I can think of a couple safe ways around this...

• Have a make_guard per maximum number of files
• Use recursion so the same scope stays alive at multiple places on the stack

But you want a dynamic number of files and recursing to an arbitrary depth isn't really an option.

(This is maybe a good time to peek at the playground below).

The dyn SomeTrait idea could still work, I guess, with the right scaffolding... if you allowed the creation of new FileContents with a 'static brand and then immediately erased them to dyn, and then only called them on an implementation of the trait which was generic over all brands. Within that implementation, the lifetime would have to be considered unique.

You don't really need generativity for this though, just invariance, the inability to clone, and a higher-ranked barrier... and we're back to GhostCell like ideas again. The dyn SomeTrait + 'static are the "unbranded" versions and dynamic dispatch to some "could be anything" lifetime is like restoring some new brand.

---

Here's a playground I created to mess around with some ideas, in case it's useful to anyone.

Rust Playground

Edit: It took me awhile to get my thoughts out and I see the OP was edited, so just note I may have missed your edits .

---

1. via generativity ↩︎

2. the edit_guard gets created multiple times due to the loop, and you cannot (safely) have more than one at once, but the Rust lifetime is the same every time ↩︎

[nik-rev]

Thank you for the detailed answer! It made me realize that storing the branded type isn't practical

In my Text Editor I am using the ropey crate which provides a Rope data structure. In my editor's state I will directly store these Ropes.

My editor has a lot of commands that manipulate text. All commands are pure functions fn(&Rope) -> Vec<Edit>, with Edit being a single, atomic action that gets added to the undo history.

I will have struct Text<'a, 'id>(&'a Rope, Id<'id>) being the branded type that contains compile-time-checked guarantees like always-in-bounds indexing.

Then my commands will become fn(Text) -> Vec<Edit>.

I think I would've kept trying the dead-end approach on my own, and your post made me think of a far better way.

The fact that what I originally wanted to do is physically impossible because it is a logic violation:

• Lifetimes only exist at compile time
• We want to create new lifetimes depending on runtime values (open new file = new 'id)

It obviously won't work, the hard part is to actually notice this. It is like gravity - it was always there but people didn't notice it.

I am really satisfied with the "it is impossible" answer. And of course adding the limitation that my Editor can only ever open N files, with all complications that this would add and the extremely pervasive 'id lifetime - is not a practical solution.

[ProgramCrafter]

Well gc-arena supports an arbitrary number of arenas while generatively distinguishing between them. Perhaps the post explaining its design, kyju.org, might help.