Undo System: replace with simpler binary diffing buffer storage

Applying/undoing incremental changes didn't fit well when
mixed with periodic snapshots from mem-file undo.

This moves to a much simpler undo system.

- Uses array storage with de-duplication from `BLI_array_store`.
- Loads the buffer into existing text data,
  for better performance on large files.
- Has the advantage that Python operators can be supported
  since we don't depend on hard coded undo operations.

Solves T67045, T66695, T65909.

3 files changed, 121 insertions, 136 deletions

diff --git a/source/blender/editors/space_text/text_autocomplete.c b/source/blender/editors/space_text/text_autocomplete.c
index c36175489b3..b6c660ae5b2 100644
--- a/source/blender/editors/space_text/text_autocomplete.c
+++ b/source/blender/editors/space_text/text_autocomplete.c
@@ -260,7 +260,7 @@ static void get_suggest_prefix(Text *text, int offset)
   texttool_suggest_prefix(line + i, len);
 }
 
-static void confirm_suggestion(Text *text, TextUndoBuf *utxt)
+static void confirm_suggestion(Text *text)
 {
   SuggItem *sel;
   int i, over = 0;
@@ -285,7 +285,7 @@ static void confirm_suggestion(Text *text, TextUndoBuf *utxt)
   //  for (i = 0; i < skipleft; i++)
   //      txt_move_left(text, 0);
   BLI_assert(memcmp(sel->name, &line[i], over) == 0);
-  txt_insert_buf(text, utxt, sel->name + over);
+  txt_insert_buf(text, sel->name + over);
 
   //  for (i = 0; i < skipleft; i++)
   //      txt_move_right(text, 0);
@@ -308,8 +308,8 @@ static int text_autocomplete_invoke(bContext *C, wmOperator *op, const wmEvent *
     ED_area_tag_redraw(CTX_wm_area(C));
 
     if (texttool_suggest_first() == texttool_suggest_last()) {
-      TextUndoBuf *utxt = ED_text_undo_push_init(C);
-      confirm_suggestion(st->text, utxt);
+      ED_text_undo_push_init(C);
+      confirm_suggestion(st->text);
       text_update_line_edited(st->text->curl);
       text_autocomplete_free(C, op);
       ED_undo_push(C, op->type->name);
@@ -371,8 +371,8 @@ static int text_autocomplete_modal(bContext *C, wmOperator *op, const wmEvent *e
     case MIDDLEMOUSE:
       if (event->val == KM_PRESS) {
         if (text_do_suggest_select(st, ar)) {
-          TextUndoBuf *utxt = ED_text_undo_push_init(C);
-          confirm_suggestion(st->text, utxt);
+          ED_text_undo_push_init(C);
+          confirm_suggestion(st->text);
           text_update_line_edited(st->text->curl);
           ED_undo_push(C, op->type->name);
           swallow = 1;
@@ -410,8 +410,8 @@ static int text_autocomplete_modal(bContext *C, wmOperator *op, const wmEvent *e
     case PADENTER:
       if (event->val == KM_PRESS) {
         if (tools & TOOL_SUGG_LIST) {
-          TextUndoBuf *utxt = ED_text_undo_push_init(C);
-          confirm_suggestion(st->text, utxt);
+          ED_text_undo_push_init(C);
+          confirm_suggestion(st->text);
           text_update_line_edited(st->text->curl);
           ED_undo_push(C, op->type->name);
           swallow = 1;
diff --git a/source/blender/editors/space_text/text_ops.c b/source/blender/editors/space_text/text_ops.c
index 33bacb0a95f..4992a73f936 100644
--- a/source/blender/editors/space_text/text_ops.c
+++ b/source/blender/editors/space_text/text_ops.c
@@ -840,7 +840,7 @@ static int text_paste_exec(bContext *C, wmOperator *op)
 
   text_drawcache_tag_update(CTX_wm_space_text(C), 0);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
   /* Convert clipboard content indentation to spaces if specified */
   if (text->flags & TXT_TABSTOSPACES) {
@@ -849,7 +849,7 @@ static int text_paste_exec(bContext *C, wmOperator *op)
     buf = new_buf;
   }
 
-  txt_insert_buf(text, utxt, buf);
+  txt_insert_buf(text, buf);
   text_update_edited(text);
 
   MEM_freeN(buf);
@@ -893,9 +893,9 @@ static int text_duplicate_line_exec(bContext *C, wmOperator *UNUSED(op))
 {
   Text *text = CTX_data_edit_text(C);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
-  txt_duplicate_line(text, utxt);
+  txt_duplicate_line(text);
 
   WM_event_add_notifier(C, NC_TEXT | NA_EDITED, text);
 
@@ -971,8 +971,8 @@ static int text_cut_exec(bContext *C, wmOperator *UNUSED(op))
 
   txt_copy_clipboard(text);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
-  txt_delete_selected(text, utxt);
+  ED_text_undo_push_init(C);
+  txt_delete_selected(text);
 
   text_update_cursor_moved(C);
   WM_event_add_notifier(C, NC_TEXT | NA_EDITED, text);
@@ -1008,14 +1008,14 @@ static int text_indent_exec(bContext *C, wmOperator *UNUSED(op))
 
   text_drawcache_tag_update(CTX_wm_space_text(C), 0);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
   if (txt_has_sel(text)) {
     txt_order_cursors(text, false);
-    txt_indent(text, utxt);
+    txt_indent(text);
   }
   else {
-    txt_add_char(text, utxt, '\t');
+    txt_add_char(text, '\t');
   }
 
   text_update_edited(text);
@@ -1049,10 +1049,10 @@ static int text_unindent_exec(bContext *C, wmOperator *UNUSED(op))
 
   text_drawcache_tag_update(CTX_wm_space_text(C), 0);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
   txt_order_cursors(text, false);
-  txt_unindent(text, utxt);
+  txt_unindent(text);
 
   text_update_edited(text);
 
@@ -1090,15 +1090,15 @@ static int text_line_break_exec(bContext *C, wmOperator *UNUSED(op))
 
   // double check tabs/spaces before splitting the line
   curts = txt_setcurr_tab_spaces(text, space);
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
-  txt_split_curline(text, utxt);
+  ED_text_undo_push_init(C);
+  txt_split_curline(text);
 
   for (a = 0; a < curts; a++) {
     if (text->flags & TXT_TABSTOSPACES) {
-      txt_add_char(text, utxt, ' ');
+      txt_add_char(text, ' ');
     }
     else {
-      txt_add_char(text, utxt, '\t');
+      txt_add_char(text, '\t');
     }
   }
 
@@ -1139,10 +1139,10 @@ static int text_comment_exec(bContext *C, wmOperator *UNUSED(op))
   if (txt_has_sel(text)) {
     text_drawcache_tag_update(CTX_wm_space_text(C), 0);
 
-    TextUndoBuf *utxt = ED_text_undo_push_init(C);
+    ED_text_undo_push_init(C);
 
     txt_order_cursors(text, false);
-    txt_comment(text, utxt);
+    txt_comment(text);
     text_update_edited(text);
 
     text_update_cursor_moved(C);
@@ -1177,10 +1177,10 @@ static int text_uncomment_exec(bContext *C, wmOperator *UNUSED(op))
   if (txt_has_sel(text)) {
     text_drawcache_tag_update(CTX_wm_space_text(C), 0);
 
-    TextUndoBuf *utxt = ED_text_undo_push_init(C);
+    ED_text_undo_push_init(C);
 
     txt_order_cursors(text, false);
-    txt_uncomment(text, utxt);
+    txt_uncomment(text);
     text_update_edited(text);
 
     text_update_cursor_moved(C);
@@ -1446,9 +1446,9 @@ static int move_lines_exec(bContext *C, wmOperator *op)
   Text *text = CTX_data_edit_text(C);
   const int direction = RNA_enum_get(op->ptr, "direction");
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
-  txt_move_lines(text, utxt, direction);
+  txt_move_lines(text, direction);
 
   text_update_cursor_moved(C);
   WM_event_add_notifier(C, NC_TEXT | NA_EDITED, text);
@@ -2230,13 +2230,13 @@ static int text_delete_exec(bContext *C, wmOperator *op)
     }
   }
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
   if (type == DEL_PREV_WORD) {
     if (txt_cursor_is_line_start(text)) {
-      txt_backspace_char(text, utxt);
+      txt_backspace_char(text);
     }
-    txt_backspace_word(text, utxt);
+    txt_backspace_word(text);
   }
   else if (type == DEL_PREV_CHAR) {
 
@@ -2252,13 +2252,13 @@ static int text_delete_exec(bContext *C, wmOperator *op)
       }
     }
 
-    txt_backspace_char(text, utxt);
+    txt_backspace_char(text);
   }
   else if (type == DEL_NEXT_WORD) {
     if (txt_cursor_is_line_end(text)) {
-      txt_delete_char(text, utxt);
+      txt_delete_char(text);
     }
-    txt_delete_word(text, utxt);
+    txt_delete_word(text);
   }
   else if (type == DEL_NEXT_CHAR) {
 
@@ -2274,7 +2274,7 @@ static int text_delete_exec(bContext *C, wmOperator *op)
       }
     }
 
-    txt_delete_char(text, utxt);
+    txt_delete_char(text);
   }
 
   text_update_line_edited(text->curl);
@@ -3190,18 +3190,18 @@ static int text_insert_exec(bContext *C, wmOperator *op)
 
   str = RNA_string_get_alloc(op->ptr, "text", NULL, 0);
 
-  TextUndoBuf *utxt = ED_text_undo_push_init(C);
+  ED_text_undo_push_init(C);
 
   if (st && st->overwrite) {
     while (str[i]) {
       code = BLI_str_utf8_as_unicode_step(str, &i);
-      done |= txt_replace_char(text, utxt, code);
+      done |= txt_replace_char(text, code);
     }
   }
   else {
     while (str[i]) {
       code = BLI_str_utf8_as_unicode_step(str, &i);
-      done |= txt_add_char(text, utxt, code);
+      done |= txt_add_char(text, code);
     }
   }
 
@@ -3319,8 +3319,8 @@ static int text_find_and_replace(bContext *C, wmOperator *op, short mode)
 
     if (found) {
       if (mode == TEXT_REPLACE) {
-        TextUndoBuf *utxt = ED_text_undo_push_init(C);
-        txt_insert_buf(text, utxt, st->replacestr);
+        ED_text_undo_push_init(C);
+        txt_insert_buf(text, st->replacestr);
         if (text->curl && text->curl->format) {
           MEM_freeN(text->curl->format);
           text->curl->format = NULL;
diff --git a/source/blender/editors/space_text/text_undo.c b/source/blender/editors/space_text/text_undo.c
index 66cbaa8bb5b..6ecb2b731b0 100644
--- a/source/blender/editors/space_text/text_undo.c
+++ b/source/blender/editors/space_text/text_undo.c
@@ -25,6 +25,7 @@
 
 #include "DNA_text_types.h"
 
+#include "BLI_array_store.h"
 #include "BLI_array_utils.h"
 
 #include "BLT_translation.h"
@@ -35,6 +36,7 @@
 #include "BKE_report.h"
 #include "BKE_text.h"
 #include "BKE_undo_system.h"
+#include "BKE_main.h"
 
 #include "WM_api.h"
 #include "WM_types.h"
@@ -53,18 +55,32 @@
 #include "text_intern.h"
 #include "text_format.h"
 
-/* TODO(campbell): undo_system: move text undo out of text block. */
-
 /* -------------------------------------------------------------------- */
 /** \name Implements ED Undo System
  * \{ */
 
+#define ARRAY_CHUNK_SIZE 128
+
 typedef struct TextUndoStep {
   UndoStep step;
   UndoRefID_Text text_ref;
-  TextUndoBuf data;
+  struct {
+    BArrayState *state;
+    int buf_len;
+  } data;
+
+  struct {
+    int line, line_select;
+    int column, column_select;
+  } cursor;
+
 } TextUndoStep;
 
+static struct {
+  BArrayStore *buffer_store;
+  int users;
+} g_text_buffers = {NULL};
+
 static bool text_undosys_poll(bContext *UNUSED(C))
 {
   /* Only use when operators initialized. */
@@ -77,12 +93,8 @@ static void text_undosys_step_encode_init(struct bContext *C, UndoStep *us_p)
   TextUndoStep *us = (TextUndoStep *)us_p;
   BLI_assert(BLI_array_is_zeroed(&us->data, 1));
 
-  UNUSED_VARS(C);
+  UNUSED_VARS(C, us);
   /* XXX, use to set the undo type only. */
-
-  us->data.buf = NULL;
-  us->data.len = 0;
-  us->data.pos = -1;
 }
 
 static bool text_undosys_step_encode(struct bContext *C,
@@ -93,104 +105,66 @@ static bool text_undosys_step_encode(struct bContext *C,
 
   Text *text = CTX_data_edit_text(C);
 
-  /* No undo data was generated. Hint, use global undo here. */
-  if ((us->data.pos == -1) || (us->data.buf == NULL)) {
-    return false;
+  int buf_len = 0;
+
+  uchar *buf = (uchar *)txt_to_buf_for_undo(text, &buf_len);
+  if (g_text_buffers.buffer_store == NULL) {
+    g_text_buffers.buffer_store = BLI_array_store_create(1, ARRAY_CHUNK_SIZE);
   }
+  g_text_buffers.users += 1;
+  const size_t total_size_prev = BLI_array_store_calc_size_compacted_get(
+      g_text_buffers.buffer_store);
 
-  us_p->is_applied = true;
+  us->data.state = BLI_array_store_state_add(g_text_buffers.buffer_store, buf, buf_len, NULL);
+  MEM_freeN(buf);
 
-  us->text_ref.ptr = text;
+  us->cursor.line = txt_get_span(text->lines.first, text->curl);
+  us->cursor.column = text->curc;
 
-  us->step.data_size = us->data.len;
-
-  return true;
-}
-
-static void text_undosys_step_decode_undo_impl(Text *text, TextUndoStep *us)
-{
-  BLI_assert(us->step.is_applied == true);
-  TextUndoBuf data = us->data;
-  while (data.pos > -1) {
-    txt_do_undo(text, &data);
+  if (txt_has_sel(text)) {
+    us->cursor.line_select = (text->curl == text->sell) ?
+                                 us->cursor.line :
+                                 txt_get_span(text->lines.first, text->sell);
+    us->cursor.column_select = text->selc;
   }
-  BLI_assert(data.pos == -1);
-  us->step.is_applied = false;
-}
-
-static void text_undosys_step_decode_redo_impl(Text *text, TextUndoStep *us)
-{
-  BLI_assert(us->step.is_applied == false);
-  TextUndoBuf data = us->data;
-  data.pos = -1;
-  while (data.pos < us->data.pos) {
-    txt_do_redo(text, &data);
+  else {
+    us->cursor.line_select = us->cursor.line;
+    us->cursor.column_select = us->cursor.column;
   }
-  BLI_assert(data.pos == us->data.pos);
-  us->step.is_applied = true;
-}
 
-static void text_undosys_step_decode_undo(TextUndoStep *us, bool is_final)
-{
-  TextUndoStep *us_iter = us;
-  while (us_iter->step.next && (us_iter->step.next->type == us_iter->step.type)) {
-    if (us_iter->step.next->is_applied == false) {
-      break;
-    }
-    us_iter = (TextUndoStep *)us_iter->step.next;
-  }
-  Text *text_prev = NULL;
-  while ((us_iter != us) || (is_final && us_iter == us)) {
-    Text *text = us_iter->text_ref.ptr;
-    text_undosys_step_decode_undo_impl(text, us_iter);
-    if (text_prev != text) {
-      text_update_edited(text);
-      text_prev = text;
-    }
-    if (is_final) {
-      break;
-    }
-    us_iter = (TextUndoStep *)us_iter->step.prev;
-  }
-}
+  us_p->is_applied = true;
 
-static void text_undosys_step_decode_redo(TextUndoStep *us)
-{
-  TextUndoStep *us_iter = us;
-  while (us_iter->step.prev && (us_iter->step.prev->type == us_iter->step.type)) {
-    if (us_iter->step.prev->is_applied == true) {
-      break;
-    }
-    us_iter = (TextUndoStep *)us_iter->step.prev;
-  }
-  Text *text_prev = NULL;
-  while (us_iter && (us_iter->step.is_applied == false)) {
-    Text *text = us_iter->text_ref.ptr;
-    text_undosys_step_decode_redo_impl(text, us_iter);
-    if (text_prev != text) {
-      text_update_edited(text);
-      text_prev = text;
-    }
-    if (us_iter == us) {
-      break;
-    }
-    us_iter = (TextUndoStep *)us_iter->step.next;
-  }
+  us->text_ref.ptr = text;
+
+  us->step.data_size = BLI_array_store_calc_size_compacted_get(g_text_buffers.buffer_store) -
+                       total_size_prev;
+
+  return true;
 }
 
-static void text_undosys_step_decode(
-    struct bContext *C, struct Main *UNUSED(bmain), UndoStep *us_p, int dir, bool is_final)
+static void text_undosys_step_decode(struct bContext *C,
+                                     struct Main *UNUSED(bmain),
+                                     UndoStep *us_p,
+                                     int UNUSED(dir),
+                                     bool UNUSED(is_final))
 {
   TextUndoStep *us = (TextUndoStep *)us_p;
+  Text *text = us->text_ref.ptr;
+  size_t buf_len;
 
-  if (dir < 0) {
-    text_undosys_step_decode_undo(us, is_final);
+  {
+    const uchar *buf = BLI_array_store_state_data_get_alloc(us->data.state, &buf_len);
+    txt_from_buf_for_undo(text, (const char *)buf, buf_len);
+    MEM_freeN((void *)buf);
   }
-  else {
-    text_undosys_step_decode_redo(us);
+
+  const bool has_select = ((us->cursor.line != us->cursor.line_select) ||
+                           (us->cursor.column != us->cursor.column_select));
+  if (has_select) {
+    txt_move_to(text, us->cursor.line_select, us->cursor.column_select, false);
   }
+  txt_move_to(text, us->cursor.line, us->cursor.column, has_select);
 
-  Text *text = us->text_ref.ptr;
   SpaceText *st = CTX_wm_space_text(C);
   if (st) {
     /* Not essential, always show text being undo where possible. */
@@ -204,7 +178,14 @@ static void text_undosys_step_decode(
 static void text_undosys_step_free(UndoStep *us_p)
 {
   TextUndoStep *us = (TextUndoStep *)us_p;
-  MEM_SAFE_FREE(us->data.buf);
+
+  BLI_array_store_state_remove(g_text_buffers.buffer_store, us->data.state);
+
+  g_text_buffers.users -= 1;
+  if (g_text_buffers.users == 0) {
+    BLI_array_store_destroy(g_text_buffers.buffer_store);
+    g_text_buffers.buffer_store = NULL;
+  }
 }
 
 static void text_undosys_foreach_ID_ref(UndoStep *us_p,
@@ -240,12 +221,16 @@ void ED_text_undosys_type(UndoType *ut)
  * \{ */
 
 /* Use operator system to finish the undo step. */
-TextUndoBuf *ED_text_undo_push_init(bContext *C)
+UndoStep *ED_text_undo_push_init(bContext *C)
 {
   UndoStack *ustack = ED_undo_stack_get();
-  UndoStep *us_p = BKE_undosys_step_push_init_with_type(ustack, C, NULL, BKE_UNDOSYS_TYPE_TEXT);
-  TextUndoStep *us = (TextUndoStep *)us_p;
-  return &us->data;
+  Main *bmain = CTX_data_main(C);
+  wmWindowManager *wm = bmain->wm.first;
+  if (wm->op_undo_depth <= 1) {
+    UndoStep *us_p = BKE_undosys_step_push_init_with_type(ustack, C, NULL, BKE_UNDOSYS_TYPE_TEXT);
+    return us_p;
+  }
+  return NULL;
 }
 
 /** \} */