Transient undo history test

history.rs

//! 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);
    }
}