I have an idea for a project that uses a state machine that has a list of deterministic transitions that can be applied to get to a certain state. I want to be able to undo transitions but don't want to have the burden of implementing the "reverse" of every transition. In my case it is much easier to just re-apply all the deterministic transitions except the undone ones.
I have searched for libraries that do something like this and as I have not found anything suiting for me I decided to write my own. As I have not written any open source libraries yet, I would love to get some feedback from the community. This one is fairly tine (fits all in one file <500 lines without tests, including a lot of documentation). My intention is to publish this to crates.io at some point but before I want to get some feedback if this is good quality and useful.
Here is the current state of my little library called (very uncreatively) undoable-state-machine: GitHub - blacktemplar/undoable-state-machine: A generic, undoable state machine backed by an append-only log, where undo is just another log entry. · GitHub
Thank you to everyone that is interested and wants to share feedback with me, go for it and be brutally honest ;).
I want to be able to undo transitions but don't want to have the burden of implementing the "reverse" of every transition.
I have searched for libraries that do something like this and as I have not found anything suiting for me
Can you say why undoredo, my crate, was not suitable for your application? I'm very much interested in that so that I can improve its usability -- it should have worked well with a state machine.
i am a bit confused by the fact that undo are appended to the log rather than simply truncating the log
The reason is that I want the log to represent the full history of what happened, so it is append only, nothing gets removed or changed afterwards.
looked at the source and this is adressed but incorrectly.
to collect undone operations before applying them you have to scan backwards otherwise something like:
Not sure if I understund you correctly here but scanning backwards is exactly what I am doing here: undoable-state-machine/src/lib.rs at 5fd6db0c7761c77631b9a126acc90ce60ded76d6 · blacktemplar/undoable-state-machine · GitHub (see the iter().rev()). To be sure I created now a test that tests exactly your example:
#[test]
fn build_with_undone_undo_computes_current() {
let a_id = TransitionId::new();
let a = LogEntry {
id: a_id,
kind: LogEntryKind::Apply(Box::new(Add(5))),
};
let undo_a_id = TransitionId::new();
let undo_a = LogEntry {
id: undo_a_id,
kind: LogEntryKind::Undo(a_id),
};
let undo_undo_a = LogEntry {
id: TransitionId::new(),
kind: LogEntryKind::Undo(undo_a_id),
};
let sm = StateMachine::build(vec![a, undo_a, undo_undo_a]).unwrap();
assert_eq!(*sm.current(), 5);
assert_eq!(sm.log().len(), 3);
}
and it succeeds.
Thank you for your reply and input. Yes I have seen your crate and it looks interesting and can probably cover my use case.
I think the reason why I didn't use it is that it just comes with different trade-offs which felt not appropriate for my use case. In my use case I definitely want a command pattern like log because I want to be able to run sports tournaments offline but then sync up with a server, the syncing will happen via sending the transitions and the server will replay them and check that everything was computed correctly (the server not trusting the offline client to avoid some kinds of cheating). Also it is just nice to have a full history of what happened.
Your README states that your crate works also with the Command pattern, but once you have the commands the difference between your library and my approach is basically that your library stores diffs to be able to undo them, while my library pays the compute cost of replaying the log from scratch (or maybe in later versions from a checkpoint ;). So in some sense it is a trade-off between memory vs compute. Also I think your approach adds the burden of implementing Delta for the state, which my more naive approach does not need. I know you have a macro for it but it still adds complexity.
One last thing I thought about is that with my approach one can also undo something that is not the last entry, which might become important in my case. Imagine a sports tournament where players report their match results and then you find out that one player reported the wrong one but it was not the last report, more reports came in since then. Now we want to undo the wrongly reported one but keep all others. Of course with your library one could undo all since the wrong one and then reapply them, but I would have to implement this on top adding complexity again.
As for the memory vs compute trade-off I mentioned above: In my situation it can happen that we change quite a bit of the state in every transition (every match report might change quite a lot of rankings for example, especially if one thinks about more complicated ranking metrics like "Buchholz").
Does these points make sense to you or did I misinterpret the power of your library in some way?
Edit: Ah I missed one point: I also want to have a full record of every change happening to a tournament, including undo's, so it is quite an important part of my library that undo is just another entry in the log, not sure how this would get combined with your library, but probably also possible (but yet more plumbing on top).
In my case it is much easier to just re-apply all the deterministic transitions except the undone ones.
The reason is that I want the log to represent the full history of what happened, so it is append only, nothing gets removed or changed afterwards.
If you want to preserve all the old history without having undo erase it, perhaps a history tree could work for you. In a tree with a principal history path, you won't have to traverse all the undone states upon replay, as they will stay on side-branches, yet they will still be remembered.