Undo tree draft.

We keep a tree of transactions. This allows for persistent undo by
simply serializing the changesets.

7 files changed, 148 insertions, 3 deletions

diff --git a/helix-core/src/history.rs b/helix-core/src/history.rs
new file mode 100644
index 00000000..8d7164db
--- /dev/null
+++ b/helix-core/src/history.rs
@@ -0,0 +1,127 @@
+use crate::{ChangeSet, Rope, State, Transaction};
+
+/// Undo-tree style history store.
+pub struct History {
+    revisions: Vec<Revision>,
+    cursor: usize,
+    //
+}
+
+#[derive(Debug)]
+struct Revision {
+    // prev: usize,
+    parent: usize,
+    /// The transaction to revert to previous state.
+    revert: Transaction,
+    // selection before, selection after?
+}
+
+impl Default for History {
+    fn default() -> Self {
+        // Add a dummy root revision with empty transaction
+        Self {
+            revisions: vec![Revision {
+                parent: 0,
+                revert: Transaction::from(ChangeSet::new(&Rope::new())),
+            }],
+            cursor: 0,
+        }
+    }
+}
+
+impl History {
+    pub fn commit_revision(&mut self, transaction: &Transaction, original: &State) {
+        // TODO: store both directions
+        // TODO: could store a single set if deletes also stored the text they delete
+        let revert = transaction.invert(original);
+
+        let new_cursor = self.revisions.len();
+        self.revisions.push(Revision {
+            parent: self.cursor,
+            revert,
+        });
+        self.cursor = new_cursor;
+
+        // TODO: child tracking too?
+    }
+
+    #[inline]
+    pub fn at_root(&self) -> bool {
+        self.cursor == 0
+    }
+
+    pub fn undo(&mut self, state: &mut State) {
+        if self.at_root() {
+            // We're at the root of undo, nothing to do.
+            return;
+        }
+
+        let current_revision = &self.revisions[self.cursor];
+        // unimplemented!("{:?}", revision);
+        // unimplemented!("{:?}", state.doc().len_chars());
+        // TODO: pass the return value through?
+        let success = current_revision.revert.apply(state);
+
+        if !success {
+            panic!("Failed to apply undo!");
+        }
+
+        self.cursor = current_revision.parent;
+    }
+
+    pub fn redo(&mut self, state: &mut State) {
+        let current_revision = &self.revisions[self.cursor];
+
+        // TODO: pick the latest child
+
+        // if !success {
+        //     panic!("Failed to apply undo!");
+        // }
+
+        unimplemented!()
+    }
+}
+
+#[cfg(test)]
+mod test {
+    use super::*;
+
+    #[test]
+    fn test_undo_redo() {
+        let mut history = History::default();
+        let doc = Rope::from("hello");
+        let mut state = State::new(doc);
+
+        let transaction1 =
+            Transaction::change(&state, vec![(5, 5, Some(" world!".into()))].into_iter());
+
+        // Need to commit before applying!
+        history.commit_revision(&transaction1, &state);
+        transaction1.apply(&mut state);
+        assert_eq!("hello world!", state.doc());
+
+        // ---
+
+        let transaction2 =
+            Transaction::change(&state, vec![(6, 11, Some("世界".into()))].into_iter());
+
+        // Need to commit before applying!
+        history.commit_revision(&transaction2, &state);
+        transaction2.apply(&mut state);
+        assert_eq!("hello 世界!", state.doc());
+
+        // ---
+
+        history.undo(&mut state);
+        assert_eq!("hello world!", state.doc());
+        history.redo(&mut state);
+        assert_eq!("hello 世界!", state.doc());
+        history.undo(&mut state);
+        history.undo(&mut state);
+        assert_eq!("hello", state.doc());
+
+        // undo at root is a no-op
+        history.undo(&mut state);
+        assert_eq!("hello", state.doc());
+    }
+}
diff --git a/helix-core/src/lib.rs b/helix-core/src/lib.rs
index 0f58fbbc..9bc5d003 100644
--- a/helix-core/src/lib.rs
+++ b/helix-core/src/lib.rs
@@ -1,5 +1,6 @@
 #![allow(unused)]
 pub mod graphemes;
+mod history;
 pub mod macros;
 mod position;
 pub mod selection;
@@ -19,6 +20,7 @@ pub use selection::Range;
 pub use selection::Selection;
 pub use syntax::Syntax;
 
+pub use history::History;
 pub use state::State;
 
 pub use transaction::{Assoc, Change, ChangeSet, Transaction};
diff --git a/helix-core/src/state.rs b/helix-core/src/state.rs
index 047ff83d..9d51c8c5 100644
--- a/helix-core/src/state.rs
+++ b/helix-core/src/state.rs
@@ -48,8 +48,8 @@ impl State {
             doc,
             selection: Selection::single(0, 0),
             mode: Mode::Normal,
-            syntax: None,
             restore_cursor: false,
+            syntax: None,
         }
     }
 
diff --git a/helix-core/src/transaction.rs b/helix-core/src/transaction.rs
index 14cb1c41..d6b151ba 100644
--- a/helix-core/src/transaction.rs
+++ b/helix-core/src/transaction.rs
@@ -338,7 +338,7 @@ impl ChangeSet {
 
 /// Transaction represents a single undoable unit of changes. Several changes can be grouped into
 /// a single transaction.
-#[derive(Clone)]
+#[derive(Debug, Clone)]
 pub struct Transaction {
     /// Changes made to the buffer.
     pub(crate) changes: ChangeSet,
diff --git a/helix-view/src/commands.rs b/helix-view/src/commands.rs
index 18135f0f..c92b33f5 100644
--- a/helix-view/src/commands.rs
+++ b/helix-view/src/commands.rs
@@ -417,3 +417,15 @@ pub fn delete_char_forward(view: &mut View, count: usize) {
     transaction.apply(&mut view.state);
     // TODO: need to store into history if successful
 }
+
+// Undo / Redo
+
+pub fn undo(view: &mut View, _count: usize) {
+    view.history.undo(&mut view.state);
+
+    // TODO: each command should simply return a Option<transaction>, then the higher level handles storing it?
+}
+
+pub fn redo(view: &mut View, _count: usize) {
+    view.history.redo(&mut view.state);
+}
diff --git a/helix-view/src/keymap.rs b/helix-view/src/keymap.rs
index 72fc0e79..e108324e 100644
--- a/helix-view/src/keymap.rs
+++ b/helix-view/src/keymap.rs
@@ -145,6 +145,8 @@ pub fn default() -> Keymaps {
                 vec![key!('c')] => commands::change_selection,
                 vec![key!('s')] => commands::split_selection_on_newline,
                 vec![key!(';')] => commands::collapse_selection,
+                vec![key!('u')] => commands::undo,
+                vec![shift!('U')] => commands::redo,
                 vec![Key {
                     code: KeyCode::Esc,
                     modifiers: Modifiers::NONE
diff --git a/helix-view/src/view.rs b/helix-view/src/view.rs
index 887c45a2..732c5081 100644
--- a/helix-view/src/view.rs
+++ b/helix-view/src/view.rs
@@ -5,12 +5,13 @@ use std::{borrow::Cow, path::PathBuf};
 use crate::theme::Theme;
 use helix_core::{
     graphemes::{grapheme_width, RopeGraphemes},
-    Position, RopeSlice, State,
+    History, Position, RopeSlice, State,
 };
 use tui::layout::Rect;
 
 pub struct View {
     pub state: State,
+    pub history: History,
     pub first_line: usize,
     pub size: (u16, u16),
     pub theme: Theme, // TODO: share one instance
@@ -26,6 +27,7 @@ impl View {
             first_line: 0,
             size, // TODO: pass in from term
             theme,
+            history: History::default(),
         };
 
         Ok(view)