How would you go about implementing a dynamically typed/heterogeneous undo stack in Rust?

[uniqueSpaceUsername]

Specifically i was hoping to have some sort of a system where any heap allocated variable could ask to hook into the undo system and when a undo() method is called the system would automatically figure out exactly which one of these variables needs to be undone.

This is different from having a completely separate undo stack for each variable, which is much easier to implement but at least as far as i can tell would have the limitation that
the number of variables that need to get undone must be know at compile time.

I do have a generic type parameter version working here -

use std::cell::RefCell;
use std::rc::Rc;

#[derive(Debug)]
struct PointerDataPair<T> {
    smart_pointer: Rc<RefCell<T>>,
    old_value: T,
}

#[derive(Debug)]
struct UndoableReplacer<T> {
    undo_stack: Vec<PointerDataPair<T>>,
    undo_index: usize,
}

impl<T> UndoableReplacer<T> {
    fn new() -> Self {
        Self {
            undo_stack: Vec::new(),
            undo_index: 0,
        }
    }
}

impl<T: Clone> UndoableReplacer<T> {
    fn replace(&mut self, smart_pointer: &Rc<RefCell<T>>, new_value: T) {
        self.undo_stack.truncate(self.undo_index);

        let inner_data_before_modification = smart_pointer.borrow().clone();
        self.undo_stack.push(PointerDataPair {
            smart_pointer: Rc::clone(smart_pointer),
            old_value: inner_data_before_modification,
        });

        let mut heap_alloc_mut_borrow = smart_pointer.borrow_mut();
        *heap_alloc_mut_borrow = new_value.clone();

        self.undo_index += 1;
    }

    fn undo(&mut self) {
        if self.undo_index != 0 {
            let undo_step = &self.undo_stack[self.undo_index - 1];

            let mut mut_borrow_of_inner = undo_step.smart_pointer.borrow_mut();
            *mut_borrow_of_inner = undo_step.old_value.clone();

            self.undo_index -= 1;
        }
    }
}

fn main() {
    let a = Rc::new(RefCell::new("a0".to_owned()));
    let b = Rc::new(RefCell::new("b0".to_owned()));
    let c = Rc::new(RefCell::new("c0".to_owned()));

    let mut undo_state = UndoableReplacer::new();

    println!("[{:?}, {:?}, {:?}]", a, b, c); // a0, b0, c0

    undo_state.replace(&a, "a1".to_owned());
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a1, b0, c0

    undo_state.replace(&b, "b1".to_owned());
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a1, b1, c0

    undo_state.undo();
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a1, b0, c0

    undo_state.replace(&c, "c1".to_owned());
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a1, b0, c1

    undo_state.undo();
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a1, b0, c0

    undo_state.undo();
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a0, b0, c0

    undo_state.undo(); // should do nothing as there is nothing to undo anymore
    println!("[{:?}, {:?}, {:?}]", a, b, c); // a0, b0, c0

    println!("{:?}", undo_state);
}

link to the playground - Rust Playground

But as you can tell from the code it's limitation is that an instance of the undo_state struct can only handle one type.

I tried many things including trait objects, nightly features, transmute ... but ran into some problem or another that i didn't know how to solve.

After spending many days on this with nothing to show for it, having some working code for this would be an absolute godsend.

Any help would be much appreciated. Thanks!

[Tom47]

You can define a trait that would be implemented by undo step:

trait Undo: Debug {
    fn undo(&self);
}

impl<T: Clone + Debug> Undo for PointerDataPair<T> {
    fn undo(&self) {
        let mut mut_borrow_of_inner = self.smart_pointer.borrow_mut();
        *mut_borrow_of_inner = self.old_value.clone();
    }
}

... and then store a Vec<Box<dyn Undo>> in your undo stack:

#[derive(Debug)]
struct UndoableReplacer {
    undo_stack: Vec<Box<dyn Undo>>,
    undo_index: usize,
}

Full code:

Rust Playground

(There is still room for improvement, e.g. you could use Vec::push() and Vec::pop() for stack operations, play around with _: Debug and _: 'static bounds and so on, you should not need any clones (I think) unless you want to add a "redo" functionality or something ... I was just trying to make something functional quickly)

[uniqueSpaceUsername]

You my friend are an absolute lifesaver!!
I had literally spent like 4-5 days on this! I finally have something that actually works to go off of, and try and build on.

You are awesome, thank you!

[Tom47]

Slightly improved version without T: Clone:

Rust Playground