Implementing undo/redo in an editor application

help
1

I am trying to implement an undo/redo system, using the undo_2 crate (I'm creating a 3d editor using bevy). I have a large data structure called Kmp (the data of the program) which contains Sections (wrapper for a Vec) of other data structures, all of which implement the KmpData trait.

pub struct Kmp {
    pub header: Header,
    pub ktpt: Section<Ktpt>,
    pub enpt: Section<Enpt>,
    pub enph: Section<Path>,
    pub itpt: Section<Itpt>,
    pub itph: Section<Path>,
    pub ckpt: Section<Ckpt>,
    pub ckph: Section<Path>,
    pub gobj: Section<Gobj>,
    pub poti: Section<Poti>,
    pub area: Section<Area>,
    pub came: Section<Came>,
    pub jgpt: Section<Jgpt>,
    pub cnpt: Section<Cnpt>,
    pub mspt: Section<Mspt>,
    pub stgi: Section<Stgi>,
}

There are 3 possible ways the data structure can be modified by the program: an entry to a section can be created, modified, or deleted. Using the undo_2 crate, I would have an enum containing these 3 possibilities, something like this:

enum UndoCommand {
    // I imagine each enum variant would need to store an index to the data and the data itself
    // this gives a compiler error though because KmpData can't be created into an object
    Create(usize, Arc<Mutex<dyn KmpData>>),
    // I imagine modify would need to store the 'before' and 'after'
    Modify(usize, Arc<Mutex<dyn KmpData>>, Arc<Mutex<dyn KmpData>>),
    Delete(usize, Arc<Mutex<dyn KmpData>>),
}

The enum variants need to contain the data created/modified/deleted, which could be any one of the different data structures within the Kmp. I need a way to generically store the data, and modify the kmp with that data in the undo/redo functions.
How should I structure my code to make this possible?

2
  1. The type safe way to do it would be to have your enum explicitly list out exactly the kinds of changes that can be made for all of the fields of your data struct. That would probably be really annoying, but it would work.
  2. You could use dyn Any along with some kind of discriminator like a string, and then downcast to the specific type based on the string. That's not really more maintainable than the fully typed enum(s) though.
  3. Probably the least annoying option to implement would be to just store boxed closures that perform the correct operation to undo or redo the change they represent. There are major downsides to that approach in terms of debuggability though, and it also precludes you from storing the undo stack in a file and restoring it if that app crashes or something.
  4. You could also choose a middle ground, create an object safe trait that represents your undo/redo options, and implement your various operations as structs implementing that new trait. Your new trait could help with debugging and potentially even serializing[1] the undo stack, while still avoiding a huge enum.

Here's a simple demonstration of 4, which is probably the direction I would go unless 1 was feasible

Playground

use std::fmt::Debug;

pub trait KmpData: std::fmt::Debug {
    fn get_section(data: &mut Kmp) -> &mut Section<Self>
    where
        Self: Sized;
}

pub type Section<T> = Vec<T>;

#[derive(Debug, Default)]
pub struct Header;

#[derive(Debug, Clone)]
pub struct Ktpt(usize);

impl KmpData for Ktpt {
    fn get_section(data: &mut Kmp) -> &mut Section<Self>
    where
        Self: Sized,
    {
        &mut data.ktpt
    }
}

#[derive(Debug, Clone)]
pub struct Enpt;

impl KmpData for Enpt {
    fn get_section(data: &mut Kmp) -> &mut Section<Self>
    where
        Self: Sized,
    {
        &mut data.enpt
    }
}

#[derive(Debug, Default)]
pub struct Kmp {
    pub header: Header,
    pub ktpt: Section<Ktpt>,
    pub enpt: Section<Enpt>,
}

pub trait UndoItem: std::fmt::Debug {
    fn undo(&self, data: &mut Kmp);

    fn redo(&self, data: &mut Kmp);
}

#[derive(Debug)]
pub struct Create<T> {
    index: usize,
    value: T,
}

impl<T: KmpData + Clone> UndoItem for Create<T> {
    fn undo(&self, data: &mut Kmp) {
        T::get_section(data).remove(self.index);
    }

    fn redo(&self, data: &mut Kmp) {
        T::get_section(data).insert(self.index, self.value.clone())
    }
}

fn main() {
    let mut data = Kmp::default();
    let mut undo: Vec<Box<dyn UndoItem>> = Vec::new();

    let value = Ktpt(0);
    data.ktpt.push(value.clone());
    undo.push(Box::new(Create { index: 0, value }));

    println!("{undo:?}");

    println!("{data:?}");

    undo[0].undo(&mut data);

    println!("{data:?}");

    undo[0].redo(&mut data);

    println!("{data:?}");
}

Output:

[Create { index: 0, value: Ktpt(0) }]
Kmp { header: Header, ktpt: [Ktpt(0)], enpt: [] }
Kmp { header: Header, ktpt: [], enpt: [] }
Kmp { header: Header, ktpt: [Ktpt(0)], enpt: [] }

  1. You would have to manually implement a deserialization function since trait objects can't help you when you don't have an object yet ↩︎

2 Likes
3

Thank you so much for this, I know I’m not really supposed to reply as the issue is solved but I want to say it’s so cool that you put work into helping me out with this, and your solution is very cool and elegant too! :slight_smile:

4

You might also be interested this series of pages from the Xi Editor's documentation. They go into quite a lot of detail on how to build a robust undo/redo system. It's probably overkill for what you need, but it'll be interesting to read up on.

3 Likes