Switch undo storage from a tree to a plain list

Whenever a new history node is committed after some undo steps, instead
of creating a new branch in the undo graph, we first append the inverse
modifications starting from the end of the undo list up to the current
position before adding the new node.

For example let's assume that the undo history is A-B-C, that a single undo
has been done (bringing us to state B) and that a new change D is committed.
Instead of creating a new branch starting at B, we add the inverse of C
(noted ^C) at the end, and D afterwards. This results in the undo history
A-B-C-^C-D. Since C-^C collapses to a null change, this is equivalent to
A-B-D but without having lost the C branch of the history.

If a new change is committed while no undo has been done, the new history
node is simply appended to the list, as was the case previously.

This results in a simplification of the user interaction, as two bindings
are now sufficient to walk the entire undo history, as opposed to needing
extra bindings to switch branches whenever they occur.
The <a-u> and <a-U> bindings are now free.

It also simplifies the implementation, as the graph traversal and
branching code are not needed anymore. The parent and child of a node are
now respectively the previous and the next elements in the list, so there
is no need to store their ID as part of the node.
Only the committing of an undo group is slightly more complex, as inverse
history nodes need to be added depending on the current position in the
undo list.

The following article was the initial motivation for this change:
https://github.com/zaboople/klonk/blob/master/TheGURQ.md

1 files changed, 8 insertions, 15 deletions

diff --git a/src/buffer.hh b/src/buffer.hh
index 7b671c0e..415d32da 100644
--- a/src/buffer.hh
+++ b/src/buffer.hh
@@ -123,8 +123,6 @@ public:
     };
     friend constexpr bool with_bit_ops(Meta::Type<Flags>) { return true; }
 
-    enum class HistoryId : size_t { First = 0, Invalid = (size_t)-1 };
-
     Buffer(String name, Flags flags, BufferLines lines,
            ByteOrderMark bom = ByteOrderMark::None,
            EolFormat eolformat = EolFormat::Lf,
@@ -150,9 +148,7 @@ public:
     void           commit_undo_group();
     bool           undo(size_t count = 1);
     bool           redo(size_t count = 1);
-    bool           move_to(HistoryId id);
-    HistoryId      current_history_id() const noexcept { return m_history_id; }
-    HistoryId      next_history_id() const noexcept { return (HistoryId)m_history.size(); }
+    size_t         current_history_id() const noexcept { return m_history_id; }
 
     String         string(BufferCoord begin, BufferCoord end) const;
     StringView     substr(BufferCoord begin, BufferCoord end) const;
@@ -245,14 +241,14 @@ public:
 
     struct HistoryNode : UseMemoryDomain<MemoryDomain::BufferMeta>
     {
-        HistoryNode(HistoryId parent);
+        HistoryNode();
 
-        HistoryId parent;
-        HistoryId redo_child = HistoryId::Invalid;
         TimePoint committed;
         UndoGroup undo_group;
     };
 
+    static constexpr size_t InvalidHistoryId = (size_t)-1;
+
     const Vector<HistoryNode>& history() const { return m_history; }
     const UndoGroup& current_undo_group() const { return m_current_undo_group; }
 
@@ -263,7 +259,6 @@ private:
     BufferCoord do_erase(BufferCoord begin, BufferCoord end);
 
     void apply_modification(const Modification& modification);
-    void revert_modification(const Modification& modification);
 
     struct LineList : BufferLines
     {
@@ -289,14 +284,12 @@ private:
     Flags  m_flags;
 
     Vector<HistoryNode> m_history;
-    HistoryId           m_history_id = HistoryId::Invalid;
-    HistoryId           m_last_save_history_id = HistoryId::Invalid;
+    size_t              m_history_id = InvalidHistoryId;
+    size_t              m_last_save_history_id = InvalidHistoryId;
     UndoGroup           m_current_undo_group;
 
-          HistoryNode& history_node(HistoryId id)       { return m_history[(size_t)id]; }
-    const HistoryNode& history_node(HistoryId id) const { return m_history[(size_t)id]; }
-          HistoryNode& current_history_node()           { return m_history[(size_t)m_history_id]; }
-    const HistoryNode& current_history_node()     const { return m_history[(size_t)m_history_id]; }
+          HistoryNode& current_history_node()           { return m_history[m_history_id]; }
+    const HistoryNode& current_history_node()     const { return m_history[m_history_id]; }
 
     Vector<Change, MemoryDomain::BufferMeta> m_changes;