after much struggle, a brute-force undo

Incredibly inefficient, but I don't yet know how to efficiently encode
undo mutations that can span multiple lines.

There seems to be one bug related to creating new drawings; they're not
spawning events and undoing past drawing creation has some weird
artifacts. Redo seems to consistently work, though.

5 files changed, 214 insertions, 0 deletions

diff --git a/README.md b/README.md
index 68999f3..871379d 100644
--- a/README.md
+++ b/README.md
@@ -6,6 +6,10 @@ http://akkartik.name/lines.html
 
 * No support yet for Unicode graphemes spanning multiple codepoints.
 
+* Undo is extremely inefficient in space. While this app is extremely unlikely
+  to lose the current state of a file at any moment, undo history is volatile
+  and should be considered unstable.
+
 * The text cursor will always stay on the screen. This can have some strange
   implications:
 
diff --git a/drawing.lua b/drawing.lua
index 6b5b6c2..f3433a0 100644
--- a/drawing.lua
+++ b/drawing.lua
@@ -206,6 +206,7 @@ function Drawing.in_drawing(drawing, x,y)
 end
 
 function Drawing.mouse_pressed(drawing, x,y, button)
+  Drawing.before = snapshot_everything()
   if Current_drawing_mode == 'freehand' then
     drawing.pending = {mode=Current_drawing_mode, points={{x=Drawing.coord(x-16), y=Drawing.coord(y-drawing.y)}}}
   elseif Current_drawing_mode == 'line' or Current_drawing_mode == 'manhattan' then
@@ -347,6 +348,7 @@ function Drawing.mouse_released(x,y, button)
     end
   end
   save_to_disk(Lines, Filename)
+  record_undo_event({before=Drawing.before, after=snapshot_everything()})
 end
 
 function Drawing.keychord_pressed(chord)
diff --git a/main.lua b/main.lua
index a6b0d73..9372207 100644
--- a/main.lua
+++ b/main.lua
@@ -65,6 +65,10 @@ Zoom = 1.5
 
 Filename = love.filesystem.getUserDirectory()..'/lines.txt'
 
+-- undo
+History = {}
+Next_history = 1
+
 end  -- App.initialize_globals
 
 function App.initialize(arg)
@@ -102,6 +106,7 @@ function App.initialize(arg)
 end  -- App.initialize
 
 function App.filedropped(file)
+  App.initialize_globals()  -- in particular, forget all undo history
   Filename = file:getFilename()
   file:open('r')
   Lines = load_from_file(file)
diff --git a/text.lua b/text.lua
index d86e2bc..b35de4e 100644
--- a/text.lua
+++ b/text.lua
@@ -3,6 +3,8 @@ Text = {}
 
 local utf8 = require 'utf8'
 
+require 'undo'
+
 -- return values:
 --  y coordinate drawn until in px
 --  position of start of final screen line drawn
@@ -1091,6 +1093,83 @@ function test_backspace_to_start_of_line()
   check_nil(Selection1.line, "F - test_backspace_to_start_of_line/selection")
 end
 
+function test_undo_insert_text()
+  io.write('\ntest_undo_insert_text')
+  App.screen.init{width=120, height=60}
+  Lines = load_array{'abc', 'def', 'xyz'}
+  Line_width = App.screen.width
+  Cursor1 = {line=2, pos=4}
+  Screen_top1 = {line=1, pos=1}
+  Screen_bottom1 = {}
+  Zoom = 1
+  -- insert a character
+  App.run_after_textinput('g')
+  check_eq(Cursor1.line, 2, 'F - test_undo_insert_text/baseline/cursor:line')
+  check_eq(Cursor1.pos, 5, 'F - test_undo_insert_text/baseline/cursor:pos')
+  check_nil(Selection1.line, 'F - test_undo_insert_text/baseline/selection:line')
+  check_nil(Selection1.pos, 'F - test_undo_insert_text/baseline/selection:pos')
+  local screen_top_margin = 15  -- pixels
+  local line_height = 15  -- pixels
+  local y = screen_top_margin
+  App.screen.check(y, 'abc', 'F - test_undo_insert_text/baseline/screen:1')
+  y = y + line_height
+  App.screen.check(y, 'defg', 'F - test_undo_insert_text/baseline/screen:2')
+  y = y + line_height
+  App.screen.check(y, 'xyz', 'F - test_undo_insert_text/baseline/screen:3')
+  -- undo
+  App.run_after_keychord('M-z')
+  check_eq(Cursor1.line, 2, 'F - test_undo_insert_text/cursor:line')
+  check_eq(Cursor1.pos, 4, 'F - test_undo_insert_text/cursor:pos')
+  check_nil(Selection1.line, 'F - test_undo_insert_text/selection:line')
+  check_nil(Selection1.pos, 'F - test_undo_insert_text/selection:pos')
+  y = screen_top_margin
+  App.screen.check(y, 'abc', 'F - test_undo_insert_text/screen:1')
+  y = y + line_height
+  App.screen.check(y, 'def', 'F - test_undo_insert_text/screen:2')
+  y = y + line_height
+  App.screen.check(y, 'xyz', 'F - test_undo_insert_text/screen:3')
+end
+
+function test_undo_delete_text()
+  io.write('\ntest_undo_delete_text')
+  App.screen.init{width=120, height=60}
+  Lines = load_array{'abc', 'defg', 'xyz'}
+  Line_width = App.screen.width
+  Cursor1 = {line=2, pos=5}
+  Screen_top1 = {line=1, pos=1}
+  Screen_bottom1 = {}
+  Zoom = 1
+  -- delete a character
+  App.run_after_keychord('backspace')
+  check_eq(Cursor1.line, 2, 'F - test_undo_delete_text/baseline/cursor:line')
+  check_eq(Cursor1.pos, 4, 'F - test_undo_delete_text/baseline/cursor:pos')
+  check_nil(Selection1.line, 'F - test_undo_delete_text/baseline/selection:line')
+  check_nil(Selection1.pos, 'F - test_undo_delete_text/baseline/selection:pos')
+  local screen_top_margin = 15  -- pixels
+  local line_height = 15  -- pixels
+  local y = screen_top_margin
+  App.screen.check(y, 'abc', 'F - test_undo_delete_text/baseline/screen:1')
+  y = y + line_height
+  App.screen.check(y, 'def', 'F - test_undo_delete_text/baseline/screen:2')
+  y = y + line_height
+  App.screen.check(y, 'xyz', 'F - test_undo_delete_text/baseline/screen:3')
+  -- undo
+--?   -- after undo, the backspaced key is selected
+  App.run_after_keychord('M-z')
+  check_eq(Cursor1.line, 2, 'F - test_undo_delete_text/cursor:line')
+  check_eq(Cursor1.pos, 5, 'F - test_undo_delete_text/cursor:pos')
+  check_nil(Selection1.line, 'F - test_undo_delete_text/selection:line')
+  check_nil(Selection1.pos, 'F - test_undo_delete_text/selection:pos')
+--?   check_eq(Selection1.line, 2, 'F - test_undo_delete_text/selection:line')
+--?   check_eq(Selection1.pos, 4, 'F - test_undo_delete_text/selection:pos')
+  y = screen_top_margin
+  App.screen.check(y, 'abc', 'F - test_undo_delete_text/screen:1')
+  y = y + line_height
+  App.screen.check(y, 'defg', 'F - test_undo_delete_text/screen:2')
+  y = y + line_height
+  App.screen.check(y, 'xyz', 'F - test_undo_delete_text/screen:3')
+end
+
 function Text.compute_fragments(line, line_width)
 --?   print('compute_fragments', line_width)
   line.fragments = {}
@@ -1142,6 +1221,8 @@ end
 
 function Text.insert_at_cursor(t)
   if Selection1.line then Text.delete_selection() end
+  -- Collect what you did in an event that can be undone.
+  local before = snapshot_everything()
   local byte_offset
   if Cursor1.pos > 1 then
     byte_offset = utf8.offset(Lines[Cursor1.line].data, Cursor1.pos)
@@ -1152,6 +1233,8 @@ function Text.insert_at_cursor(t)
   Lines[Cursor1.line].fragments = nil
   Lines[Cursor1.line].screen_line_starting_pos = nil
   Cursor1.pos = Cursor1.pos+1
+  -- finalize undo event
+  record_undo_event({before=before, after=snapshot_everything()})
 end
 
 -- Don't handle any keys here that would trigger love.textinput above.
@@ -1159,6 +1242,7 @@ function Text.keychord_pressed(chord)
 --?   print(chord)
   --== shortcuts that mutate text
   if chord == 'return' then
+    local before = snapshot_everything()
     local byte_offset = utf8.offset(Lines[Cursor1.line].data, Cursor1.pos)
     table.insert(Lines, Cursor1.line+1, {mode='text', data=string.sub(Lines[Cursor1.line].data, byte_offset)})
     local scroll_down = (Cursor_y + math.floor(15*Zoom)) > App.screen.height
@@ -1171,12 +1255,18 @@ function Text.keychord_pressed(chord)
       Screen_top1.line = Cursor1.line
       Text.scroll_up_while_cursor_on_screen()
     end
+    record_undo_event({before=before, after=snapshot_everything()})
   elseif chord == 'tab' then
+    local before = snapshot_everything()
     Text.insert_at_cursor('\t')
     save_to_disk(Lines, Filename)
+    record_undo_event({before=before, after=snapshot_everything()})
   elseif chord == 'backspace' then
+    local before = snapshot_everything()
     if Selection1.line then
       Text.delete_selection()
+      save_to_disk(Lines, Filename)
+      record_undo_event({before=before, after=snapshot_everything()})
       return
     end
     if Cursor1.pos > 1 then
@@ -1210,9 +1300,13 @@ function Text.keychord_pressed(chord)
     end
     assert(Text.le1(Screen_top1, Cursor1))
     save_to_disk(Lines, Filename)
+    record_undo_event({before=before, after=snapshot_everything()})
   elseif chord == 'delete' then
+    local before = snapshot_everything()
     if Selection1.line then
       Text.delete_selection()
+      save_to_disk(Lines, Filename)
+      record_undo_event({before=before, after=snapshot_everything()})
       return
     end
     if Cursor1.pos <= utf8.len(Lines[Cursor1.line].data) then
@@ -1238,6 +1332,37 @@ function Text.keychord_pressed(chord)
       end
     end
     save_to_disk(Lines, Filename)
+    record_undo_event({before=before, after=snapshot_everything()})
+  -- undo/redo really belongs in main.lua, but it's here so I can test the
+  -- text-specific portions of it
+  elseif chord == 'M-z' then
+    local event = undo_event()
+    if event then
+      local src = event.before
+      Screen_top1 = deepcopy(src.screen_top)
+      Cursor1 = deepcopy(src.cursor)
+      Selection1 = deepcopy(src.selection)
+      if src.lines then
+        Lines = deepcopy(src.lines)
+      end
+    end
+  elseif chord == 'M-y' then
+    local event = redo_event()
+    if event then
+      local src = event.after
+      Screen_top1 = deepcopy(src.screen_top)
+      Cursor1 = deepcopy(src.cursor)
+      Selection1 = deepcopy(src.selection)
+      if src.lines then
+        Lines = deepcopy(src.lines)
+--?         for _,line in ipairs(Lines) do
+--?           if line.mode == 'drawing' then
+--?             print('restoring', line.points, 'with', #line.points, 'points')
+--?             print('restoring', line.shapes, 'with', #line.shapes, 'shapes')
+--?           end
+--?         end
+      end
+    end
   -- paste
   elseif chord == 'M-c' then
     local s = Text.selection()
diff --git a/undo.lua b/undo.lua
new file mode 100644
index 0000000..abf5f33
--- /dev/null
+++ b/undo.lua
@@ -0,0 +1,78 @@
+-- undo/redo by managing the sequence of events in the current session
+-- based on https://github.com/akkartik/mu1/blob/master/edit/012-editor-undo.mu
+
+-- Incredibly inefficient; we make a copy of lines on every single keystroke.
+-- The hope here is that we're either editing small files or just reading large files.
+-- TODO: highlight stuff inserted by any undo/redo operation
+-- TODO: coalesce multiple similar operations
+
+function record_undo_event(data)
+  History[Next_history] = data
+  Next_history = Next_history+1
+  for i=Next_history,#History do
+    History[i] = nil
+  end
+end
+
+function undo_event()
+  if Next_history > 1 then
+--?     print('moving to history', Next_history-1)
+    Next_history = Next_history-1
+    local result = History[Next_history]
+    return result
+  end
+end
+
+function redo_event()
+  if Next_history <= #History then
+--?     print('restoring history', Next_history+1)
+    local result = History[Next_history]
+    Next_history = Next_history+1
+    return result
+  end
+end
+
+-- Make copies of objects; the rest of the app may mutate them in place, but undo requires immutable histories.
+function snapshot_everything()
+  -- compare with App.initialize_globals
+  local event = {
+    screen_top=deepcopy(Screen_top1),
+    selection=deepcopy(Selection1),
+    cursor=deepcopy(Cursor1),
+    current_drawing_mode=Drawing_mode,
+    previous_drawing_mode=Previous_drawing_mode,
+    zoom=Zoom,
+    lines={},
+    -- no filename; undo history is cleared when filename changes
+  }
+  -- deep copy lines without cached stuff like text fragments
+  for _,line in ipairs(Lines) do
+    if line.mode == 'text' then
+      table.insert(event.lines, {mode='text', data=line.data})
+    elseif line.mode == 'drawing' then
+      local points=deepcopy(line.points)
+--?       print('copying', line.points, 'with', #line.points, 'points into', points)
+      local shapes=deepcopy(line.shapes)
+--?       print('copying', line.shapes, 'with', #line.shapes, 'shapes into', shapes)
+      table.insert(event.lines, {mode='drawing', y=line.y, h=line.h, points=points, shapes=shapes, pending={}})
+--?       table.insert(event.lines, {mode='drawing', y=line.y, h=line.h, points=deepcopy(line.points), shapes=deepcopy(line.shapes), pending={}})
+    else
+      print(line.mode)
+      assert(false)
+    end
+  end
+  return event
+end
+
+-- https://stackoverflow.com/questions/640642/how-do-you-copy-a-lua-table-by-value/26367080#26367080
+function deepcopy(obj, seen)
+  if type(obj) ~= 'table' then return obj end
+  if seen and seen[obj] then return seen[obj] end
+  local s = seen or {}
+  local result = setmetatable({}, getmetatable(obj))
+  s[obj] = result
+  for k,v in pairs(obj) do
+    result[deepcopy(k, s)] = deepcopy(v, s)
+  end
+  return result
+end