Created
October 6, 2020 18:32
-
-
Save HactarCE/98f2fd146dd6943126d07d24efe0b575 to your computer and use it in GitHub Desktop.
Transient undo history test
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//! Undo/redo history. | |
//! | |
//! The simplest model of undo history consists of a single "undo stack." Every | |
//! operation pushes a history entry for the previous state onto the undo stack. | |
//! The "undo" action pops a history entry from the top of the undo stack and | |
//! restores it. | |
//! | |
//! To add "redo" functionality, we make an additional "redo stack." To undo an | |
//! action, we push an entry onto the redo stack and then pop an entry from the | |
//! undo stack to restore. To redo an action, we push an entry onto the undo | |
//! stack and then pop an entry from the redo stack to restore. Every operation | |
//! besides undo/redo clears the redo stack. | |
//! | |
//! NDCell uses a slightly more complicated model, because of the following | |
//! contradiction: | |
//! - It is sometimes useful to undo individual selection operations. | |
//! - Operations that do not change the state of the automaton or are canceled | |
//! should not clear the redo stack. | |
//! | |
//! A solution is to record "transient" history entries for operations like | |
//! selection. Transient history entries work just like normal history entries, | |
//! except for the following: | |
//! - Transient entries are never buried beneath non-transient entries on the | |
//! undo stack and redo stack; they are always on the top. | |
//! - Undoing a non-transient entry will clear transient entries from the | |
//! redo stack. | |
//! - Redoing a non-transient entry is not allowed while there is a | |
//! transient entry on the undo stack. | |
//! - Recording a non-transient entry clears transient entries from the undo | |
//! stack and clears all entries from the redo stack. | |
//! - Recording a transient entry clears only transient entries from the redo | |
//! stack. | |
//! | |
//! Note that operations involving transient entries never clear non-transient | |
//! entries from the redo stack. | |
use crate::gridview::GridView; // required to make `enum_dispatch` happy | |
use enum_dispatch::enum_dispatch; | |
#[derive(Debug, Default)] | |
pub struct HistoryManager<E> { | |
undo_stack: Vec<E>, | |
redo_stack: Vec<E>, | |
transient_undo_stack: Vec<E>, | |
transient_redo_stack: Vec<E>, | |
} | |
impl<E> HistoryManager<E> { | |
pub fn record(&mut self, current: E) { | |
self.transient_undo_stack.clear(); | |
self.transient_redo_stack.clear(); | |
self.undo_stack.push(current); | |
self.redo_stack.clear(); | |
} | |
pub fn can_undo(&self) -> bool { | |
!self.undo_stack.is_empty() | |
} | |
pub fn can_redo(&self) -> bool { | |
!self.redo_stack.is_empty() | |
// Cannot redo non-transient entry while there is a transient entry | |
// on the undo stack | |
&& !(self.transient_redo_stack.is_empty() && !self.transient_undo_stack.is_empty()) | |
} | |
pub fn undo(&mut self, restore_fn: impl FnOnce(E) -> E) -> bool { | |
if let Some(undone_state) = self.transient_undo_stack.pop() { | |
let current = restore_fn(undone_state); | |
self.transient_redo_stack.push(current); | |
true | |
} else if let Some(undone_state) = self.undo_stack.pop() { | |
self.transient_redo_stack.clear(); | |
let current = restore_fn(undone_state); | |
self.redo_stack.push(current); | |
true | |
} else { | |
false | |
} | |
} | |
pub fn redo(&mut self, restore_fn: impl FnOnce(E) -> E) -> bool { | |
if let Some(redone_state) = self.transient_redo_stack.pop() { | |
let current = restore_fn(redone_state); | |
self.transient_undo_stack.push(current); | |
true | |
} else if !self.transient_undo_stack.is_empty() { | |
// Cannot redo non-transient entry while there is a transient entry | |
// on the undo stack | |
false | |
} else if let Some(redone_state) = self.redo_stack.pop() { | |
let current = restore_fn(redone_state); | |
self.undo_stack.push(current); | |
true | |
} else { | |
false | |
} | |
} | |
pub fn record_transient(&mut self, current: E) { | |
self.transient_undo_stack.push(current); | |
self.transient_redo_stack.clear(); | |
} | |
pub fn undo_non_transient(&mut self, restore_fn: impl FnOnce(E) -> E) -> bool { | |
self.transient_redo_stack.clear(); | |
self.transient_undo_stack.clear(); | |
self.undo(restore_fn) | |
} | |
} | |
/* /// Methods for managing history entries. | |
pub trait HistoryManager { | |
/// The type used for history entries. | |
type HistoryEntry; | |
/// Returns a history entry representing the current state. | |
fn history_entry(&self) -> Self::HistoryEntry; | |
/// Replaces this state with the one recorded in the given history entry and | |
/// returns a new history entry representing the state before calling this | |
/// method. | |
/// | |
/// This method is analogous to std::mem::replace(). | |
fn restore(&mut self, entry: Self::HistoryEntry) -> Self::HistoryEntry; | |
/// Returns an immutable reference to the undo stack, with the most recent | |
/// entry on top. | |
fn undo_stack(&self) -> &Vec<Self::HistoryEntry>; | |
/// Returns an immutable reference to the redo stack, with the next entry on | |
/// top. | |
fn redo_stack(&self) -> &Vec<Self::HistoryEntry>; | |
/// Returns a mutable reference to the undo stack, with the most recent | |
/// entry on top. | |
fn undo_stack_mut(&mut self) -> &mut Vec<Self::HistoryEntry>; | |
/// Returns a mutable reference to the redo stack, with the next entry on | |
/// top. | |
fn redo_stack_mut(&mut self) -> &mut Vec<Self::HistoryEntry>; | |
} */ | |
/* /// Undo/redo methods -- the "public" interface of HistoryManager. This is | |
/// automatically implemented for all HistoryManager. | |
#[enum_dispatch] | |
pub trait History { | |
/// Pushes the current state onto the undo stack and clears the redo stack. | |
fn record(&mut self); | |
/// Restores the last state from the undo stack, pushing the current state | |
/// onto the redo stack. | |
/// | |
/// Returns true if the undo was successful, or false if there was nothing | |
/// to undo. | |
fn undo(&mut self) -> bool; | |
/// Restores the next state from the redo stack, pushing the current state | |
/// onto the undo stack. | |
/// | |
/// Returns true if the redo was successful, or false if there was nothing | |
/// to redo. | |
fn redo(&mut self) -> bool; | |
/// Returns true if there is something to undo, or false otherwise. | |
fn has_undo(&self) -> bool; | |
/// Returns true if there is something to redo, or false otherwise. | |
fn has_redo(&self) -> bool; | |
} | |
impl<T: HistoryManager> History for T { | |
fn record(&mut self) { | |
let current = self.history_entry(); | |
// Erase redo history. | |
self.redo_stack_mut().clear(); | |
// Push new entry. | |
self.undo_stack_mut().push(current); | |
} | |
fn undo(&mut self) -> bool { | |
if let Some(new_state) = self.undo_stack_mut().pop() { | |
let redo_state = self.restore(new_state); | |
self.redo_stack_mut().push(redo_state.into()); | |
true | |
} else { | |
false | |
} | |
} | |
fn redo(&mut self) -> bool { | |
if let Some(new_state) = self.redo_stack_mut().pop() { | |
let undo_state = self.restore(new_state); | |
self.undo_stack_mut().push(undo_state.into()); | |
true | |
} else { | |
false | |
} | |
} | |
fn has_undo(&self) -> bool { | |
!self.undo_stack().is_empty() | |
} | |
fn has_redo(&self) -> bool { | |
!self.redo_stack().is_empty() | |
} | |
} | |
*/ | |
#[cfg(test)] | |
mod tests { | |
use super::*; | |
fn replace<'a, T>(state: &'a mut T) -> impl 'a + FnMut(T) -> T { | |
move |x| std::mem::replace(state, x) | |
} | |
#[test] | |
fn test_undo_redo() { | |
let mut h = HistoryManager::default(); | |
let mut current = 10; | |
h.record(current); | |
current = 20; | |
h.record(current); | |
current = 30; | |
/* Try undo() */ | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(10, current); | |
// no more undo history; should fail | |
assert!(!h.undo(replace(&mut current))); | |
assert_eq!(10, current); | |
/* Try redo() */ | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(30, current); | |
// no more redo history; should fail | |
assert!(!h.redo(replace(&mut current))); | |
assert_eq!(30, current); | |
} | |
#[test] | |
fn test_undo_redo_overwrite() { | |
let mut h = HistoryManager::default(); | |
let mut current = 10; | |
h.record(current); | |
current = 20; | |
h.record(current); | |
current = 30; | |
h.record(current); | |
current = 40; | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(30, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
// should clear redo history but not undo history | |
h.record(current); | |
current = 25; | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(25, current); | |
// redo history was deleted; should fail | |
assert!(!h.redo(replace(&mut current))); | |
assert_eq!(25, current); | |
} | |
fn undo_redo_transient_setup() -> (HistoryManager<i32>, i32) { | |
let mut h = HistoryManager::default(); | |
let mut current = 10; | |
h.record(current); | |
current = 20; | |
h.record(current); | |
current = 30; | |
h.record(current); | |
current = 40; | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(30, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
h.record_transient(current); | |
current = 21; | |
h.record_transient(current); | |
current = 22; | |
h.record_transient(current); | |
current = 23; | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(22, current); | |
(h, current) | |
} | |
#[test] | |
fn test_undo_redo_transient() { | |
let (mut h, mut current) = undo_redo_transient_setup(); | |
assert_eq!(22, current); | |
// Can redo transient entry | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(23, current); | |
// but not non-transient entry | |
assert!(!h.redo(replace(&mut current))); | |
assert_eq!(23, current); | |
// Recording transient entry erases transient redo stack | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(22, current); | |
h.record_transient(current); | |
current = 24; | |
assert!(!h.redo(replace(&mut current))); | |
assert_eq!(24, current); | |
// but not transient undo stack | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(22, current); | |
// Undoing a non-transient entry erases all transient entries | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(21, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(30, current); | |
// Adding non-transient entry erases all transient entries | |
let (mut h, mut current) = undo_redo_transient_setup(); | |
assert_eq!(22, current); | |
h.record(current); | |
current = 40; | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(22, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(22, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(40, current); | |
assert!(!h.redo(replace(&mut current))); | |
assert_eq!(40, current); | |
} | |
#[test] | |
fn test_undo_non_transient() { | |
let (mut h, mut current) = undo_redo_transient_setup(); | |
assert_eq!(22, current); | |
assert!(h.undo_non_transient(replace(&mut current))); | |
assert_eq!(20, current); | |
// idempotency | |
assert!(!h.undo_non_transient(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.redo(replace(&mut current))); | |
assert_eq!(30, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(20, current); | |
assert!(h.undo(replace(&mut current))); | |
assert_eq!(10, current); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment