Undo: Detect/find proper memchunk for a given ID during undo step writing.

Most of the time current (based on order) system works fine, but when you add
or rename (i.e. re-sort) some ID, every data/memchunk afterwards would be out
of sync and hence re-stored in memory (and reported as changed).

Now we are storing the ID's session_uuid in the memchunks, which allows to
actually always find the first memchunk for an already existing ID stored in
previous undo steps, and compare the right memory.

Note that current, based-on-order system is still used almost all of the time,
search in the new ghash is only performed for a few data-blocks (when needed at all).

Reviewed By: brecht

Maniphest Tasks: T60695

Differential Revision: https://developer.blender.org/D7877

source/blender/blenloader/BLO_undofile.h

@@ -26,6 +26,7 @@
  */
 
 struct Scene;
+struct GHash;
 
 typedef struct {
   void *next, *prev;
@@ -38,6 +39,9 @@ typedef struct {
    * detect unchanged IDs).
    * Defined when writing the next step (i.e. last undo step has those always false). */
   bool is_identical_future;
+  /** Session uuid of the ID being curently written (MAIN_ID_SESSION_UUID_UNSET when not writing
+   * ID-related data). Used to find matching chunks in previous memundo step. */
+  uint id_session_uuid;
 } MemFileChunk;
 
 typedef struct MemFile {
@@ -45,6 +49,17 @@ typedef struct MemFile {
   size_t size;
 } MemFile;
 
+typedef struct MemFileWriteData {
+  MemFile *written_memfile;
+  MemFile *reference_memfile;
+
+  uint current_id_session_uuid;
+  MemFileChunk *reference_current_chunk;
+
+  /** Maps an ID session uuid to its first reference MemFileChunk, if existing. */
+  struct GHash *id_session_uuid_mapping;
+} MemFileWriteData;
+
 typedef struct MemFileUndoData {
   char filename[1024]; /* FILE_MAX */
   MemFile memfile;
@@ -52,10 +67,13 @@ typedef struct MemFileUndoData {
 } MemFileUndoData;
 
 /* actually only used writefile.c */
-extern void memfile_chunk_add(MemFile *memfile,
-                              const char *buf,
-                              unsigned int size,
-                              MemFileChunk **compchunk_step);
+
+void BLO_memfile_write_init(MemFileWriteData *mem_data,
+                            MemFile *written_memfile,
+                            MemFile *reference_memfile);
+void BLO_memfile_write_finalize(MemFileWriteData *mem_data);
+
+void BLO_memfile_chunk_add(MemFileWriteData *mem_data, const char *buf, unsigned int size);
 
 /* exports */
 extern void BLO_memfile_free(MemFile *memfile);

source/blender/blenloader/intern/undofile.c

@@ -41,10 +41,12 @@
 #include "DNA_listBase.h"
 
 #include "BLI_blenlib.h"
+#include "BLI_ghash.h"
 
 #include "BLO_readfile.h"
 #include "BLO_undofile.h"
 
+#include "BKE_lib_id.h"
 #include "BKE_main.h"
 
 /* keep last */
@@ -100,8 +102,52 @@ void BLO_memfile_clear_future(MemFile *memfile)
   }
 }
 
-void memfile_chunk_add(MemFile *memfile, const char *buf, uint size, MemFileChunk **compchunk_step)
+void BLO_memfile_write_init(MemFileWriteData *mem_data,
+                            MemFile *written_memfile,
+                            MemFile *reference_memfile)
 {
+  mem_data->written_memfile = written_memfile;
+  mem_data->reference_memfile = reference_memfile;
+  mem_data->reference_current_chunk = reference_memfile ? reference_memfile->chunks.first : NULL;
+
+  /* If we have a reference memfile, we generate a mapping between the session_uuid's of the IDs
+   * stored in that previous undo step, and its first matching memchunk.
+   * This will allow us to easily find the existing undo memory storage of IDs even when some
+   * re-ordering in current Main data-base broke the order matching with the memchunks from
+   * previous step. */
+  if (reference_memfile != NULL) {
+    mem_data->id_session_uuid_mapping = BLI_ghash_new(
+        BLI_ghashutil_inthash_p_simple, BLI_ghashutil_intcmp, __func__);
+    uint current_session_uuid = MAIN_ID_SESSION_UUID_UNSET;
+    LISTBASE_FOREACH (MemFileChunk *, mem_chunk, &reference_memfile->chunks) {
+      if (!ELEM(mem_chunk->id_session_uuid, MAIN_ID_SESSION_UUID_UNSET, current_session_uuid)) {
+        current_session_uuid = mem_chunk->id_session_uuid;
+        void **entry;
+        if (!BLI_ghash_ensure_p(mem_data->id_session_uuid_mapping,
+                                POINTER_FROM_UINT(current_session_uuid),
+                                &entry)) {
+          *entry = mem_chunk;
+        }
+        else {
+          BLI_assert(0);
+        }
+      }
+    }
+  }
+}
+
+void BLO_memfile_write_finalize(MemFileWriteData *mem_data)
+{
+  if (mem_data->id_session_uuid_mapping != NULL) {
+    BLI_ghash_free(mem_data->id_session_uuid_mapping, NULL, NULL);
+  }
+}
+
+void BLO_memfile_chunk_add(MemFileWriteData *mem_data, const char *buf, uint size)
+{
+  MemFile *memfile = mem_data->written_memfile;
+  MemFileChunk **compchunk_step = &mem_data->reference_current_chunk;
+
   MemFileChunk *curchunk = MEM_mallocN(sizeof(MemFileChunk), "MemFileChunk");
   curchunk->size = size;
   curchunk->buf = NULL;
@@ -110,6 +156,7 @@ void memfile_chunk_add(MemFile *memfile, const char *buf, uint size, MemFileChun
    * perform an undo push may make changes after the last undo push that
    * will then not be undo. Though it's not entirely clear that is wrong behavior. */
   curchunk->is_identical_future = true;
+  curchunk->id_session_uuid = mem_data->current_id_session_uuid;
   BLI_addtail(&memfile->chunks, curchunk);
 
   /* we compare compchunk with buf */

source/blender/blenloader/intern/writefile.c

@@ -162,6 +162,7 @@
 #include "BKE_gpencil_modifier.h"
 #include "BKE_idtype.h"
 #include "BKE_layer.h"
+#include "BKE_lib_id.h"
 #include "BKE_lib_override.h"
 #include "BKE_main.h"
 #include "BKE_modifier.h"
@@ -326,12 +327,7 @@ typedef struct {
   bool error;
 
   /** #MemFile writing (used for undo). */
-  struct {
-    MemFile *current;
-    MemFile *compare;
-    /** Use to de-duplicate chunks when writing. */
-    MemFileChunk *compare_chunk;
-  } mem;
+  MemFileWriteData mem;
   /** When true, write to #WriteData.current, could also call 'is_undo'. */
   bool use_memfile;
 
@@ -370,7 +366,7 @@ static void writedata_do_write(WriteData *wd, const void *mem, int memlen)
 
   /* memory based save */
   if (wd->use_memfile) {
-    memfile_chunk_add(wd->mem.current, mem, memlen, &wd->mem.compare_chunk);
+    BLO_memfile_chunk_add(&wd->mem, mem, memlen);
   }
   else {
     if (wd->ww->write(wd->ww, mem, memlen) != memlen) {
@@ -471,9 +467,7 @@ static WriteData *mywrite_begin(WriteWrap *ww, MemFile *compare, MemFile *curren
   WriteData *wd = writedata_new(ww);
 
   if (current != NULL) {
-    wd->mem.current = current;
-    wd->mem.compare = compare;
-    wd->mem.compare_chunk = compare ? compare->chunks.first : NULL;
+    BLO_memfile_write_init(&wd->mem, current, compare);
     wd->use_memfile = true;
   }
 
@@ -493,12 +487,58 @@ static bool mywrite_end(WriteData *wd)
     wd->buf_used_len = 0;
   }
 
+  if (wd->use_memfile) {
+    BLO_memfile_write_finalize(&wd->mem);
+  }
+
   const bool err = wd->error;
   writedata_free(wd);
 
   return err;
 }
 
+/**
+ * Start writing of data related to a single ID.
+ *
+ * Only does something when storing an undo step.
+ */
+static void mywrite_id_begin(WriteData *wd, ID *id)
+{
+  if (wd->use_memfile) {
+    wd->mem.current_id_session_uuid = id->session_uuid;
+
+    /* If current next memchunk does not match the ID we are about to write, try to find the
+     * correct memchunk in the mapping using ID's session_uuid. */
+    if (wd->mem.id_session_uuid_mapping != NULL &&
+        (wd->mem.reference_current_chunk == NULL ||
+         wd->mem.reference_current_chunk->id_session_uuid != id->session_uuid)) {
+      void *ref = BLI_ghash_lookup(wd->mem.id_session_uuid_mapping,
+                                   POINTER_FROM_UINT(id->session_uuid));
+      if (ref != NULL) {
+        wd->mem.reference_current_chunk = ref;
+      }
+      /* Else, no existing memchunk found, i.e. this is supposed to be a new ID. */
+    }
+    /* Otherwise, we try with the current memchunk in any case, whether it is matching current
+     * ID's session_uuid or not. */
+  }
+}
+
+/**
+ * Start writing of data related to a single ID.
+ *
+ * Only does something when storing an undo step.
+ */
+static void mywrite_id_end(WriteData *wd, ID *id)
+{
+  if (wd->use_memfile) {
+    /* Very important to do it after every ID write now, otherwise we cannot know whether a
+     * specific ID changed or not. */
+    mywrite_flush(wd);
+    wd->mem.current_id_session_uuid = MAIN_ID_SESSION_UUID_UNSET;
+  }
+}
+
 /** \} */
 
 /* -------------------------------------------------------------------- */
@@ -4138,6 +4178,8 @@ static bool write_file_handle(Main *mainvar,
           }
         }
 
+        mywrite_id_begin(wd, id);
+
         memcpy(id_buffer, id, idtype_struct_size);
 
         ((ID *)id_buffer)->tag = 0;
@@ -4279,11 +4321,7 @@ static bool write_file_handle(Main *mainvar,
           BKE_lib_override_library_operations_store_end(override_storage, id);
         }
 
-        if (wd->use_memfile) {
-          /* Very important to do it after every ID write now, otherwise we cannot know whether a
-           * specific ID changed or not. */
-          mywrite_flush(wd);
-        }
+        mywrite_id_end(wd, id);
       }
 
       if (id_buffer != id_buffer_static) {