Undo: unified undo system w/ linear history

- Use a single undo history for all operations.
- UndoType's are registered and poll the context to check if they
  should be used when performing an undo push.
- Mode switching is used to ensure the state is correct before
  undo data is restored.
- Some undo types accumulate changes (image & text editing)
  others store the state multiple times (with de-duplication).
  This is supported by checking UndoStack.mode `ACCUMULATE` / `STORE`.
- Each undo step stores ID datablocks they use with utilities to help
  manage restoring correct ID's.
  Needed since global undo is now mixed with other modes undo.
- Currently performs each undo step when going up/down history
  Previously this wasn't done, making history fail in some cases.
  This can be optimized to skip some combinations of undo steps.

grease-pencil is an exception which has not been updated
since it integrates undo into the draw-session.

See D3113

8 files changed, 1012 insertions, 307 deletions

diff --git a/source/blender/blenkernel/BKE_blender_undo.h b/source/blender/blenkernel/BKE_blender_undo.h
index 84a6d07be7d..a96f8af1fdb 100644
--- a/source/blender/blenkernel/BKE_blender_undo.h
+++ b/source/blender/blenkernel/BKE_blender_undo.h
@@ -31,22 +31,13 @@ extern "C" {
 struct bContext;
 struct Scene;
 struct Main;
+struct MemFileUndoData;
 
 #define BKE_UNDO_STR_MAX 64
 
-/* global undo */
-extern void          BKE_undo_write(struct bContext *C, const char *name);
-extern void          BKE_undo_step(struct bContext *C, int step);
-extern void          BKE_undo_name(struct bContext *C, const char *name);
-extern bool          BKE_undo_is_valid(const char *name);
-extern void          BKE_undo_reset(void);
-extern void          BKE_undo_number(struct bContext *C, int nr);
-extern const char   *BKE_undo_get_name(int nr, bool *r_active);
-extern const char   *BKE_undo_get_name_last(void);
-extern bool          BKE_undo_save_file(const char *filename);
-extern struct Main  *BKE_undo_get_main(struct Scene **r_scene);
-
-extern void          BKE_undo_callback_wm_kill_jobs_set(void (*callback)(struct bContext *C));
+struct MemFileUndoData *BKE_memfile_undo_encode(struct Main *bmain, struct MemFileUndoData *mfu_prev);
+bool                    BKE_memfile_undo_decode(struct MemFileUndoData *mfu, struct bContext *C);
+void                    BKE_memfile_undo_free(struct MemFileUndoData *mfu);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/blenkernel/BKE_main.h b/source/blender/blenkernel/BKE_main.h
index d8318bfcf5d..e224155726f 100644
--- a/source/blender/blenkernel/BKE_main.h
+++ b/source/blender/blenkernel/BKE_main.h
@@ -84,10 +84,12 @@ typedef struct Main {
 	short minversionfile, minsubversionfile;
 	uint64_t build_commit_timestamp; /* commit's timestamp from buildinfo */
 	char build_hash[16];  /* hash from buildinfo */
-	short recovered;	/* indicate the main->name (file) is the recovered one */
+	char recovered;	/* indicate the main->name (file) is the recovered one */
+	/** All current ID's exist in the last memfile undo step. */
+	char is_memfile_undo_written;
 
 	BlendThumbnail *blen_thumb;
-	
+
 	struct Library *curlib;
 	ListBase scene;
 	ListBase library;
diff --git a/source/blender/blenkernel/BKE_pointcache.h b/source/blender/blenkernel/BKE_pointcache.h
index f31ae715539..cc60df1b2d6 100644
--- a/source/blender/blenkernel/BKE_pointcache.h
+++ b/source/blender/blenkernel/BKE_pointcache.h
@@ -227,7 +227,6 @@ typedef struct PTCacheEditPoint {
 } PTCacheEditPoint;
 
 typedef struct PTCacheUndo {
-	struct PTCacheUndo *next, *prev;
 	struct PTCacheEditPoint *points;
 
 	/* particles stuff */
@@ -240,12 +239,11 @@ typedef struct PTCacheUndo {
 	struct ListBase mem_cache;
 
 	int totpoint;
-	char name[64];
+
+	size_t undo_size;
 } PTCacheUndo;
 
 typedef struct PTCacheEdit {
-	ListBase undo;
-	struct PTCacheUndo *curundo;
 	PTCacheEditPoint *points;
 
 	struct PTCacheID pid;
diff --git a/source/blender/blenkernel/BKE_undo_system.h b/source/blender/blenkernel/BKE_undo_system.h
new file mode 100644
index 00000000000..6072ecfae4a
--- /dev/null
+++ b/source/blender/blenkernel/BKE_undo_system.h
@@ -0,0 +1,187 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+#ifndef __BKE_UNDO_SYSTEM_H__
+#define __BKE_UNDO_SYSTEM_H__
+
+/** \file BKE_undo_system.h
+ *  \ingroup bke
+ */
+
+struct Main;
+struct UndoStep;
+struct bContext;
+
+/* ID's */
+struct Mesh;
+struct Object;
+struct Scene;
+struct Text;
+
+#include "DNA_ID.h"
+#include "DNA_listBase.h"
+
+typedef struct UndoRefID { struct ID *ptr; char name[MAX_ID_NAME]; } UndoRefID;
+/* UndoRefID_Mesh & friends. */
+#define UNDO_REF_ID_TYPE(ptr_ty) \
+	typedef struct UndoRefID_##ptr_ty { struct ptr_ty *ptr; char name[MAX_ID_NAME]; } UndoRefID_##ptr_ty
+UNDO_REF_ID_TYPE(Mesh);
+UNDO_REF_ID_TYPE(Object);
+UNDO_REF_ID_TYPE(Scene);
+UNDO_REF_ID_TYPE(Text);
+
+typedef struct UndoStack {
+	ListBase         steps;
+	struct UndoStep *step_active;
+
+	/**
+	 * Some undo systems require begin/end, see: #UndoType.step_encode_init
+	 *
+	 * \note This is not included in the 'steps' list.
+	 * That is done once end is called.
+	 */
+	struct UndoStep *step_init;
+} UndoStack;
+
+
+typedef struct UndoStep {
+	struct UndoStep *next, *prev;
+	char name[64];
+	const struct UndoType *type;
+	/** Size in bytes of all data in step (not including the step). */
+	size_t data_size;
+	/** Users should never see this step (only use for internal consistency). */
+	bool skip;
+	/* Over alloc 'type->struct_size'. */
+} UndoStep;
+
+typedef enum eUndoTypeMode {
+	/**
+	 * Each undo step stores a version of the state.
+	 * This means we can simply load in a previous state at any time.
+	 */
+	BKE_UNDOTYPE_MODE_STORE = 1,
+	/**
+	 * Each undo step is a series of edits.
+	 * This means to change states we need to apply each edit.
+	 * It also means the 'step_decode' callback needs to detect the difference between undo and redo.
+	 * (Currently used for text edit and image & sculpt painting).
+	 */
+	BKE_UNDOTYPE_MODE_ACCUMULATE = 2,
+} eUndoTypeMode;
+
+typedef void (*UndoTypeForEachIDRefFn)(void *user_data, struct UndoRefID *id_ref);
+
+typedef struct UndoType {
+	struct UndoType *next, *prev;
+	/** Only for debugging. */
+	const char *name;
+
+	/**
+	 * When NULL, we don't consider this undo type for context checks.
+	 * Operators must explicitly set the undo type and handle adding the undo step.
+	 * This is needed when tools operate on data which isn't the primary mode (eg, paint-curve in sculpt mode).
+	 */
+	bool (*poll)(struct bContext *C);
+
+	/**
+	 * None of these callbacks manage list add/removal.
+	 *
+	 * Note that 'step_encode_init' is optional,
+	 * some undo types need to perform operatons before undo push finishes.
+	 */
+	void (*step_encode_init)(struct bContext *C, UndoStep *us);
+
+	bool (*step_encode)(struct bContext *C, UndoStep *us);
+	void (*step_decode)(struct bContext *C, UndoStep *us, int dir);
+
+	/**
+	 * \note When freeing all steps,
+	 * free from the last since #MemFileUndoType will merge with the next undo type in the list. */
+	void (*step_free)(UndoStep *us);
+
+	void (*step_foreach_ID_ref)(UndoStep *us, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data);
+
+	eUndoTypeMode mode;
+	bool use_context;
+
+	int step_size;
+} UndoType;
+
+/* expose since we need to perform operations on spesific undo types (rarely). */
+extern const UndoType *BKE_UNDOSYS_TYPE_MEMFILE;
+extern const UndoType *BKE_UNDOSYS_TYPE_IMAGE;
+extern const UndoType *BKE_UNDOSYS_TYPE_SCULPT;
+extern const UndoType *BKE_UNDOSYS_TYPE_PARTICLE;
+extern const UndoType *BKE_UNDOSYS_TYPE_PAINTCURVE;
+
+UndoStack      *BKE_undosys_stack_create(void);
+void            BKE_undosys_stack_destroy(UndoStack *ustack);
+void            BKE_undosys_stack_clear(UndoStack *ustack);
+bool            BKE_undosys_stack_has_undo(UndoStack *ustack, const char *name);
+void            BKE_undosys_stack_init_from_main(UndoStack *ustack, struct Main *bmain);
+UndoStep       *BKE_undosys_stack_active_with_type(UndoStack *ustack, const UndoType *ut);
+UndoStep       *BKE_undosys_stack_init_or_active_with_type(UndoStack *ustack, const UndoType *ut);
+void            BKE_undosys_stack_limit_steps_and_memory(UndoStack *ustack, int steps, size_t memory_limit);
+
+/* Only some UndoType's require init. */
+void BKE_undosys_step_push_init_with_type(UndoStack *ustack, struct bContext *C, const char *name, const UndoType *ut);
+void BKE_undosys_step_push_init(UndoStack *ustack, struct bContext *C, const char *name);
+
+bool BKE_undosys_step_push_with_type(UndoStack *ustack, struct bContext *C, const char *name, const UndoType *ut);
+bool BKE_undosys_step_push(UndoStack *ustack, struct bContext *C, const char *name);
+
+UndoStep *BKE_undosys_step_find_by_name_with_type(UndoStack *ustack, const char *name, const UndoType *ut);
+UndoStep *BKE_undosys_step_find_by_name(UndoStack *ustack, const char *name);
+
+bool BKE_undosys_step_undo_with_data_ex(UndoStack *ustack, struct bContext *C, UndoStep *us, bool use_skip);
+bool BKE_undosys_step_undo_with_data(UndoStack *ustack, struct bContext *C, UndoStep *us);
+bool BKE_undosys_step_undo(UndoStack *ustack, struct bContext *C);
+
+bool BKE_undosys_step_redo_with_data_ex(UndoStack *ustack, struct bContext *C, UndoStep *us, bool use_skip);
+bool BKE_undosys_step_redo_with_data(UndoStack *ustack, struct bContext *C, UndoStep *us);
+bool BKE_undosys_step_redo(UndoStack *ustack, struct bContext *C);
+
+bool BKE_undosys_step_load_data(UndoStack *ustack, struct bContext *C, UndoStep *us);
+
+bool BKE_undosys_step_undo_compat_only(UndoStack *ustack, struct bContext *C, int step);
+void BKE_undosys_step_undo_from_index(UndoStack *ustack, struct bContext *C, int index);
+UndoStep *BKE_undosys_step_same_type_next(UndoStep *us);
+UndoStep *BKE_undosys_step_same_type_prev(UndoStep *us);
+
+/* Type System */
+UndoType *BKE_undosys_type_append(void (*undosys_fn)(UndoType *));
+void      BKE_undosys_type_free_all(void);
+
+/* ID Accessor */
+#if 0  /* functionality is only used internally for now. */
+void BKE_undosys_foreach_ID_ref(UndoStack *ustack, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data);
+#endif
+
+/* Use when the undo step stores many arbitrary pointers. */
+struct UndoIDPtrMap;
+struct UndoIDPtrMap *BKE_undosys_ID_map_create(void);
+void                 BKE_undosys_ID_map_destroy(struct UndoIDPtrMap *map);
+void                 BKE_undosys_ID_map_add(struct UndoIDPtrMap *map, ID *id);
+struct ID           *BKE_undosys_ID_map_lookup(const struct UndoIDPtrMap *map, const struct ID *id_src);
+void                 BKE_undosys_ID_map_foreach_ID_ref(
+        struct UndoIDPtrMap *map,
+        UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data);
+
+#endif  /* __BKE_UNDO_SYSTEM_H__ */
diff --git a/source/blender/blenkernel/CMakeLists.txt b/source/blender/blenkernel/CMakeLists.txt
index 25954f277b8..d789671ab24 100644
--- a/source/blender/blenkernel/CMakeLists.txt
+++ b/source/blender/blenkernel/CMakeLists.txt
@@ -188,6 +188,7 @@ set(SRC
 	intern/tracking_solver.c
 	intern/tracking_stabilize.c
 	intern/tracking_util.c
+	intern/undo_system.c
 	intern/unit.c
 	intern/world.c
 	intern/writeavi.c
@@ -296,6 +297,7 @@ set(SRC
 	BKE_text.h
 	BKE_texture.h
 	BKE_tracking.h
+	BKE_undo_system.h
 	BKE_unit.h
 	BKE_world.h
 	BKE_writeavi.h
diff --git a/source/blender/blenkernel/intern/blender_undo.c b/source/blender/blenkernel/intern/blender_undo.c
index 4efca5bcc41..6b31c8c96f9 100644
--- a/source/blender/blenkernel/intern/blender_undo.c
+++ b/source/blender/blenkernel/intern/blender_undo.c
@@ -42,28 +42,19 @@
 
 #include "DNA_scene_types.h"
 
-#include "BLI_fileops.h"
-#include "BLI_listbase.h"
 #include "BLI_path_util.h"
 #include "BLI_string.h"
 #include "BLI_utildefines.h"
 
-#include "IMB_imbuf.h"
-#include "IMB_moviecache.h"
-
 #include "BKE_blender_undo.h"  /* own include */
 #include "BKE_blendfile.h"
 #include "BKE_appdir.h"
-#include "BKE_brush.h"
 #include "BKE_context.h"
 #include "BKE_depsgraph.h"
 #include "BKE_global.h"
-#include "BKE_image.h"
 #include "BKE_main.h"
-#include "RE_pipeline.h"
 
 #include "BLO_undofile.h"
-#include "BLO_readfile.h"
 #include "BLO_writefile.h"
 
 /* -------------------------------------------------------------------- */
@@ -73,46 +64,21 @@
 
 #define UNDO_DISK   0
 
-typedef struct UndoElem {
-	struct UndoElem *next, *prev;
-	/* Only for 'UNDO_DISK' */
-	char filename[FILE_MAX];
-	char name[BKE_UNDO_STR_MAX];
-	MemFile memfile;
-	size_t undo_size;
-} UndoElem;
-
-static ListBase undobase = {NULL, NULL};
-static UndoElem *curundo = NULL;
-
-/**
- * Avoid bad-level call to #WM_jobs_kill_all_except()
- */
-static void (*undo_wm_job_kill_callback)(struct bContext *C) = NULL;
-
-void BKE_undo_callback_wm_kill_jobs_set(void (*callback)(struct bContext *C))
-{
-	undo_wm_job_kill_callback = callback;
-}
-
-static int read_undosave(bContext *C, UndoElem *uel)
+bool BKE_memfile_undo_decode(MemFileUndoData *mfu, bContext *C)
 {
 	char mainstr[sizeof(G.main->name)];
 	int success = 0, fileflags;
 
-	/* This is needed so undoing/redoing doesn't crash with threaded previews going */
-	undo_wm_job_kill_callback(C);
-
 	BLI_strncpy(mainstr, G.main->name, sizeof(mainstr));    /* temporal store */
 
 	fileflags = G.fileflags;
 	G.fileflags |= G_FILE_NO_UI;
 
 	if (UNDO_DISK) {
-		success = (BKE_blendfile_read(C, uel->filename, NULL, 0) != BKE_BLENDFILE_READ_FAIL);
+		success = (BKE_blendfile_read(C, mfu->filename, NULL, 0) != BKE_BLENDFILE_READ_FAIL);
 	}
 	else {
-		success = BKE_blendfile_read_from_memfile(C, &uel->memfile, NULL, 0);
+		success = BKE_blendfile_read_from_memfile(C, &mfu->memfile, NULL, 0);
 	}
 
 	/* restore */
@@ -127,51 +93,9 @@ static int read_undosave(bContext *C, UndoElem *uel)
 	return success;
 }
 
-/* name can be a dynamic string */
-void BKE_undo_write(bContext *C, const char *name)
+MemFileUndoData *BKE_memfile_undo_encode(Main *bmain, MemFileUndoData *mfu_prev)
 {
-	int nr /*, success */ /* UNUSED */;
-	UndoElem *uel;
-
-	if ((U.uiflag & USER_GLOBALUNDO) == 0) {
-		return;
-	}
-
-	if (U.undosteps == 0) {
-		return;
-	}
-
-	/* remove all undos after (also when curundo == NULL) */
-	while (undobase.last != curundo) {
-		uel = undobase.last;
-		BLI_remlink(&undobase, uel);
-		BLO_memfile_free(&uel->memfile);
-		MEM_freeN(uel);
-	}
-
-	/* make new */
-	curundo = uel = MEM_callocN(sizeof(UndoElem), "undo file");
-	BLI_strncpy(uel->name, name, sizeof(uel->name));
-	BLI_addtail(&undobase, uel);
-
-	/* and limit amount to the maximum */
-	nr = 0;
-	uel = undobase.last;
-	while (uel) {
-		nr++;
-		if (nr == U.undosteps) break;
-		uel = uel->prev;
-	}
-	if (uel) {
-		while (undobase.first != uel) {
-			UndoElem *first = undobase.first;
-			BLI_remlink(&undobase, first);
-			/* the merge is because of compression */
-			BLO_memfile_merge(&first->memfile, &first->next->memfile);
-			MEM_freeN(first);
-		}
-	}
-
+	MemFileUndoData *mfu = MEM_callocN(sizeof(MemFileUndoData), __func__);
 
 	/* disk save version */
 	if (UNDO_DISK) {
@@ -187,222 +111,25 @@ void BKE_undo_write(bContext *C, const char *name)
 		BLI_snprintf(numstr, sizeof(numstr), "%d.blend", counter);
 		BLI_make_file_string("/", filename, BKE_tempdir_session(), numstr);
 
-		/* success = */ /* UNUSED */ BLO_write_file(CTX_data_main(C), filename, fileflags, NULL, NULL);
+		/* success = */ /* UNUSED */ BLO_write_file(bmain, filename, fileflags, NULL, NULL);
 
-		BLI_strncpy(curundo->filename, filename, sizeof(curundo->filename));
+		BLI_strncpy(mfu->filename, filename, sizeof(mfu->filename));
 	}
 	else {
-		MemFile *prevfile = NULL;
-
-		if (curundo->prev) prevfile = &(curundo->prev->memfile);
-
-		/* success = */ /* UNUSED */ BLO_write_file_mem(CTX_data_main(C), prevfile, &curundo->memfile, G.fileflags);
-		curundo->undo_size = curundo->memfile.size;
-	}
-
-	if (U.undomemory != 0) {
-		size_t maxmem, totmem;
-		/* limit to maximum memory (afterwards, we can't know in advance) */
-		totmem = 0;
-		maxmem = ((size_t)U.undomemory) * 1024 * 1024;
-
-		/* keep at least two (original + other) */
-		uel = undobase.last;
-		while (uel && uel->prev) {
-			totmem += uel->undo_size;
-			if (totmem > maxmem) break;
-			uel = uel->prev;
-		}
-
-		if (uel) {
-			if (uel->prev && uel->prev->prev)
-				uel = uel->prev;
-
-			while (undobase.first != uel) {
-				UndoElem *first = undobase.first;
-				BLI_remlink(&undobase, first);
-				/* the merge is because of compression */
-				BLO_memfile_merge(&first->memfile, &first->next->memfile);
-				MEM_freeN(first);
-			}
-		}
-	}
-}
-
-/* 1 = an undo, -1 is a redo. we have to make sure 'curundo' remains at current situation */
-void BKE_undo_step(bContext *C, int step)
-{
-
-	if (step == 0) {
-		read_undosave(C, curundo);
-	}
-	else if (step == 1) {
-		/* curundo should never be NULL, after restart or load file it should call undo_save */
-		if (curundo == NULL || curundo->prev == NULL) {
-			// XXX error("No undo available");
-		}
-		else {
-			if (G.debug & G_DEBUG) printf("undo %s\n", curundo->name);
-			curundo = curundo->prev;
-			read_undosave(C, curundo);
-		}
-	}
-	else {
-		/* curundo has to remain current situation! */
-
-		if (curundo == NULL || curundo->next == NULL) {
-			// XXX error("No redo available");
-		}
-		else {
-			read_undosave(C, curundo->next);
-			curundo = curundo->next;
-			if (G.debug & G_DEBUG) printf("redo %s\n", curundo->name);
-		}
-	}
-}
-
-void BKE_undo_reset(void)
-{
-	UndoElem *uel;
-
-	uel = undobase.first;
-	while (uel) {
-		BLO_memfile_free(&uel->memfile);
-		uel = uel->next;
-	}
-
-	BLI_freelistN(&undobase);
-	curundo = NULL;
-}
-
-/* based on index nr it does a restore */
-void BKE_undo_number(bContext *C, int nr)
-{
-	curundo = BLI_findlink(&undobase, nr);
-	BKE_undo_step(C, 0);
-}
-
-/* go back to the last occurance of name in stack */
-void BKE_undo_name(bContext *C, const char *name)
-{
-	UndoElem *uel = BLI_rfindstring(&undobase, name, offsetof(UndoElem, name));
-
-	if (uel && uel->prev) {
-		curundo = uel->prev;
-		BKE_undo_step(C, 0);
-	}
-}
-
-/* name optional */
-bool BKE_undo_is_valid(const char *name)
-{
-	if (name) {
-		UndoElem *uel = BLI_rfindstring(&undobase, name, offsetof(UndoElem, name));
-		return uel && uel->prev;
+		MemFile *prevfile = (mfu_prev) ? &(mfu_prev->memfile) : NULL;
+		/* success = */ /* UNUSED */ BLO_write_file_mem(bmain, prevfile, &mfu->memfile, G.fileflags);
+		mfu->undo_size = mfu->memfile.size;
 	}
 
-	return undobase.last != undobase.first;
-}
-
-/* get name of undo item, return null if no item with this index */
-/* if active pointer, set it to 1 if true */
-const char *BKE_undo_get_name(int nr, bool *r_active)
-{
-	UndoElem *uel = BLI_findlink(&undobase, nr);
+	bmain->is_memfile_undo_written = true;
 
-	if (r_active) *r_active = false;
-
-	if (uel) {
-		if (r_active && (uel == curundo)) {
-			*r_active = true;
-		}
-		return uel->name;
-	}
-	return NULL;
+	return mfu;
 }
 
-/* return the name of the last item */
-const char *BKE_undo_get_name_last(void)
+void BKE_memfile_undo_free(MemFileUndoData *mfu)
 {
-	UndoElem *uel = undobase.last;
-	return (uel ? uel->name : NULL);
-}
-
-/**
- * Saves .blend using undo buffer.
- *
- * \return success.
- */
-bool BKE_undo_save_file(const char *filename)
-{
-	UndoElem *uel;
-	MemFileChunk *chunk;
-	int file, oflags;
-
-	if ((U.uiflag & USER_GLOBALUNDO) == 0) {
-		return false;
-	}
-
-	uel = curundo;
-	if (uel == NULL) {
-		fprintf(stderr, "No undo buffer to save recovery file\n");
-		return false;
-	}
-
-	/* note: This is currently used for autosave and 'quit.blend', where _not_ following symlinks is OK,
-	 * however if this is ever executed explicitly by the user, we may want to allow writing to symlinks.
-	 */
-
-	oflags = O_BINARY | O_WRONLY | O_CREAT | O_TRUNC;
-#ifdef O_NOFOLLOW
-	/* use O_NOFOLLOW to avoid writing to a symlink - use 'O_EXCL' (CVE-2008-1103) */
-	oflags |= O_NOFOLLOW;
-#else
-	/* TODO(sergey): How to deal with symlinks on windows? */
-#  ifndef _MSC_VER
-#    warning "Symbolic links will be followed on undo save, possibly causing CVE-2008-1103"
-#  endif
-#endif
-	file = BLI_open(filename,  oflags, 0666);
-
-	if (file == -1) {
-		fprintf(stderr, "Unable to save '%s': %s\n",
-		        filename, errno ? strerror(errno) : "Unknown error opening file");
-		return false;
-	}
-
-	for (chunk = uel->memfile.chunks.first; chunk; chunk = chunk->next) {
-		if (write(file, chunk->buf, chunk->size) != chunk->size) {
-			break;
-		}
-	}
-
-	close(file);
-
-	if (chunk) {
-		fprintf(stderr, "Unable to save '%s': %s\n",
-		        filename, errno ? strerror(errno) : "Unknown error writing file");
-		return false;
-	}
-	return true;
-}
-
-/* sets curscene */
-Main *BKE_undo_get_main(Scene **r_scene)
-{
-	Main *mainp = NULL;
-	BlendFileData *bfd = BLO_read_from_memfile(G.main, G.main->name, &curundo->memfile, NULL, BLO_READ_SKIP_NONE);
-
-	if (bfd) {
-		mainp = bfd->main;
-		if (r_scene) {
-			*r_scene = bfd->curscene;
-		}
-
-		MEM_freeN(bfd);
-	}
-
-	return mainp;
+	BLO_memfile_free(&mfu->memfile);
+	MEM_freeN(mfu);
 }
 
 /** \} */
diff --git a/source/blender/blenkernel/intern/library.c b/source/blender/blenkernel/intern/library.c
index 99423ee26a6..10b724f9f69 100644
--- a/source/blender/blenkernel/intern/library.c
+++ b/source/blender/blenkernel/intern/library.c
@@ -757,6 +757,7 @@ void BKE_libblock_management_main_add(Main *bmain, void *idv)
 	new_id(lb, id, NULL);
 	/* alphabetic insertion: is in new_id */
 	id->tag &= ~(LIB_TAG_NO_MAIN | LIB_TAG_NO_USER_REFCOUNT);
+	bmain->is_memfile_undo_written = false;
 	BKE_main_unlock(bmain);
 }
 
@@ -776,6 +777,7 @@ void BKE_libblock_management_main_remove(Main *bmain, void *idv)
 	BKE_main_lock(bmain);
 	BLI_remlink(lb, id);
 	id->tag |= LIB_TAG_NO_MAIN;
+	bmain->is_memfile_undo_written = false;
 	BKE_main_unlock(bmain);
 }
 
@@ -1138,6 +1140,7 @@ void *BKE_libblock_alloc(Main *bmain, short type, const char *name, const int fl
 			BKE_main_lock(bmain);
 			BLI_addtail(lb, id);
 			new_id(lb, id, name);
+			bmain->is_memfile_undo_written = false;
 			/* alphabetic insertion: is in new_id */
 			BKE_main_unlock(bmain);
 
diff --git a/source/blender/blenkernel/intern/undo_system.c b/source/blender/blenkernel/intern/undo_system.c
new file mode 100644
index 00000000000..ddcd16f998e
--- /dev/null
+++ b/source/blender/blenkernel/intern/undo_system.c
@@ -0,0 +1,795 @@
+/*
+ * ***** BEGIN GPL LICENSE BLOCK *****
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ *
+ * ***** END GPL LICENSE BLOCK *****
+ */
+
+/** \file blender/editors/util/undo_system.c
+ *  \ingroup edutil
+ *
+ * Used by ED_undo.h, internal implementation.
+ */
+
+#include <string.h>
+
+#include "CLG_log.h"
+
+#include "BLI_utildefines.h"
+#include "BLI_sys_types.h"
+#include "BLI_listbase.h"
+#include "BLI_string.h"
+#include "BLI_sort_utils.h"
+
+#include "DNA_listBase.h"
+#include "DNA_windowmanager_types.h"
+
+#include "BKE_context.h"
+#include "BKE_global.h"
+#include "BKE_main.h"
+#include "BKE_undo_system.h"
+
+#include "MEM_guardedalloc.h"
+
+#define undo_stack _wm_undo_stack_disallow  /* pass in as a variable always. */
+
+/** Odd requirement of Blender that we always keep a memfile undo in the stack. */
+#define WITH_GLOBAL_UNDO_KEEP_ONE
+
+/** Make sure all ID's created at the point we add an undo step that uses ID's. */
+#define WITH_GLOBAL_UNDO_ENSURE_UPDATED
+
+/** We only need this locally. */
+static CLG_LogRef LOG = {"bke.undosys"};
+
+/* -------------------------------------------------------------------- */
+/** \name Internal Nested Undo Checks
+ *
+ * Make sure we're not running undo operations from 'step_encode', 'step_decode' callbacks.
+ * bugs caused by this situation aren't _that_ hard to spot but aren't always so obvious.
+ * Best we have a check which shows the problem immediately.
+ *
+ * \{ */
+#define WITH_NESTED_UNDO_CHECK
+
+#ifdef WITH_NESTED_UNDO_CHECK
+static bool g_undo_callback_running = false;
+#  define UNDO_NESTED_ASSERT(state) BLI_assert(g_undo_callback_running == state)
+#  define UNDO_NESTED_CHECK_BEGIN { \
+	UNDO_NESTED_ASSERT(false); \
+	g_undo_callback_running = true; \
+} ((void)0)
+#  define UNDO_NESTED_CHECK_END { \
+	UNDO_NESTED_ASSERT(true); \
+	g_undo_callback_running = false; \
+} ((void)0)
+#else
+#  define UNDO_NESTED_ASSERT(state) ((void)0)
+#  define UNDO_NESTED_CHECK_BEGIN ((void)0)
+#  define UNDO_NESTED_CHECK_END   ((void)0)
+#endif
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Public Undo Types
+ *
+ * Unfortunately we need this for a handful of places.
+ */
+const UndoType *BKE_UNDOSYS_TYPE_MEMFILE = NULL;
+const UndoType *BKE_UNDOSYS_TYPE_IMAGE = NULL;
+const UndoType *BKE_UNDOSYS_TYPE_SCULPT = NULL;
+const UndoType *BKE_UNDOSYS_TYPE_PARTICLE = NULL;
+const UndoType *BKE_UNDOSYS_TYPE_PAINTCURVE = NULL;
+/** \} */
+
+/* UndoType */
+
+static ListBase g_undo_types = {NULL, NULL};
+
+static const UndoType *BKE_undosys_type_from_context(bContext *C)
+{
+	for (const UndoType *ut = g_undo_types.first; ut; ut = ut->next) {
+		/* No poll means we don't check context. */
+		if (ut->poll && ut->poll(C)) {
+			return ut;
+		}
+	}
+	return NULL;
+}
+
+/* -------------------------------------------------------------------- */
+/** \name Internal Callback Wrappers
+ *
+ * #UndoRefID is simply a way to avoid inlining name copy and lookups,
+ * since it's easy to forget a single case when done inline (crashing in some cases).
+ *
+ * \{ */
+
+static void undosys_id_ref_store(void *UNUSED(user_data), UndoRefID *id_ref)
+{
+	BLI_assert(id_ref->name[0] == '\0');
+	if (id_ref->ptr) {
+		BLI_strncpy(id_ref->name, id_ref->ptr->name, sizeof(id_ref->name));
+		/* Not needed, just prevents stale data access. */
+		id_ref->ptr = NULL;
+	}
+}
+
+static void undosys_id_ref_resolve(void *user_data, UndoRefID *id_ref)
+{
+	/* Note: we could optimize this, for now it's not too bad since it only runs when we access undo! */
+	Main *bmain = user_data;
+	ListBase *lb = which_libbase(bmain, GS(id_ref->name));
+	for (ID *id = lb->first; id; id = id->next) {
+		if (STREQ(id_ref->name, id->name) && (id->lib == NULL)) {
+			id_ref->ptr = id;
+			break;
+		}
+	}
+}
+
+static bool undosys_step_encode(bContext *C, UndoStep *us)
+{
+	CLOG_INFO(&LOG, 2, "%p '%s', type='%s'", us, us->name, us->type->name);
+	UNDO_NESTED_CHECK_BEGIN;
+	bool ok = us->type->step_encode(C, us);
+	UNDO_NESTED_CHECK_END;
+	if (ok) {
+		if (us->type->step_foreach_ID_ref != NULL) {
+			/* Don't use from context yet because sometimes context is fake and not all members are filled in. */
+			Main *bmain = G.main;
+			us->type->step_foreach_ID_ref(us, undosys_id_ref_store, bmain);
+		}
+	}
+	return ok;
+}
+
+static void undosys_step_decode(bContext *C, UndoStep *us, int dir)
+{
+	CLOG_INFO(&LOG, 2, "%p '%s', type='%s'", us, us->name, us->type->name);
+	if (us->type->step_foreach_ID_ref) {
+		/* Don't use from context yet because sometimes context is fake and not all members are filled in. */
+		Main *bmain = G.main;
+		us->type->step_foreach_ID_ref(us, undosys_id_ref_resolve, bmain);
+	}
+
+	UNDO_NESTED_CHECK_BEGIN;
+	us->type->step_decode(C, us, dir);
+	UNDO_NESTED_CHECK_END;
+}
+
+static void undosys_step_free_and_unlink(UndoStack *ustack, UndoStep *us)
+{
+	CLOG_INFO(&LOG, 2, "%p '%s', type='%s'", us, us->name, us->type->name);
+	UNDO_NESTED_CHECK_BEGIN;
+	us->type->step_free(us);
+	UNDO_NESTED_CHECK_END;
+
+	BLI_remlink(&ustack->steps, us);
+	MEM_freeN(us);
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Undo Stack
+ * \{ */
+
+#ifndef NDEBUG
+static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
+{
+	if (ustack->step_active != NULL) {
+		BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
+		BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
+	}
+	if (expect_non_empty) {
+		BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
+	}
+}
+#else
+static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
+{
+	UNUSED_VARS(ustack, expect_non_empty);
+}
+#endif
+
+UndoStack *BKE_undosys_stack_create(void)
+{
+	UndoStack *ustack = MEM_callocN(sizeof(UndoStack), __func__);
+	return ustack;
+}
+
+void BKE_undosys_stack_destroy(UndoStack *ustack)
+{
+	BKE_undosys_stack_clear(ustack);
+	MEM_freeN(ustack);
+}
+
+void BKE_undosys_stack_clear(UndoStack *ustack)
+{
+	UNDO_NESTED_ASSERT(false);
+	CLOG_INFO(&LOG, 1, "steps=%d", BLI_listbase_count(&ustack->steps));
+	for (UndoStep *us = ustack->steps.last, *us_prev; us; us = us_prev) {
+		us_prev = us->prev;
+		undosys_step_free_and_unlink(ustack, us);
+	}
+	BLI_listbase_clear(&ustack->steps);
+	ustack->step_active = NULL;
+}
+
+static bool undosys_stack_push_main(UndoStack *ustack, const char *name, struct Main *bmain)
+{
+	UNDO_NESTED_ASSERT(false);
+	CLOG_INFO(&LOG, 1, "'%s'", name);
+	bContext *C_temp = CTX_create();
+	CTX_data_main_set(C_temp, bmain);
+	bool ok = BKE_undosys_step_push_with_type(ustack, C_temp, name, BKE_UNDOSYS_TYPE_MEMFILE);
+	CTX_free(C_temp);
+	return ok;
+}
+
+void BKE_undosys_stack_init_from_main(UndoStack *ustack, struct Main *bmain)
+{
+	UNDO_NESTED_ASSERT(false);
+	undosys_stack_push_main(ustack, "original", bmain);
+}
+
+/* name optional */
+bool BKE_undosys_stack_has_undo(UndoStack *ustack, const char *name)
+{
+	if (name) {
+		UndoStep *us = BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
+		return us && us->prev;
+	}
+
+	return !BLI_listbase_is_empty(&ustack->steps);
+}
+
+UndoStep *BKE_undosys_stack_active_with_type(UndoStack *ustack, const UndoType *ut)
+{
+	UndoStep *us = ustack->step_active;
+	while (us && (us->type != ut)) {
+		us = us->prev;
+	}
+	return us;
+}
+
+UndoStep *BKE_undosys_stack_init_or_active_with_type(UndoStack *ustack, const UndoType *ut)
+{
+	UNDO_NESTED_ASSERT(false);
+	CLOG_INFO(&LOG, 1, "type='%s'", ut->name);
+	if (ustack->step_init && (ustack->step_init->type == ut)) {
+		return ustack->step_init;
+	}
+	return BKE_undosys_stack_active_with_type(ustack, ut);
+}
+
+/**
+ * \param steps: Limit the number of undo steps.
+ * \param memory_limit: Limit the amount of memory used by the undo stack.
+ */
+void BKE_undosys_stack_limit_steps_and_memory(UndoStack *ustack, int steps, size_t memory_limit)
+{
+	UNDO_NESTED_ASSERT(false);
+	if (!(steps || memory_limit)) {
+		return;
+	}
+
+	CLOG_INFO(&LOG, 1, "steps=%d, memory_limit=%zu", steps, memory_limit);
+	UndoStep *us;
+#ifdef WITH_GLOBAL_UNDO_KEEP_ONE
+	UndoStep *us_exclude = NULL;
+#endif
+	/* keep at least two (original + other) */
+	size_t data_size_all = 0;
+	size_t us_count = 0;
+	for (us = ustack->steps.last; us && us->prev; us = us->prev) {
+		if (memory_limit) {
+			data_size_all += us->data_size;
+			if (data_size_all > memory_limit) {
+				break;
+			}
+		}
+		if (steps) {
+			if (us_count == steps) {
+				break;
+			}
+			if (us->skip == false) {
+				us_count += 1;
+			}
+		}
+	}
+
+	if (us) {
+		if (us->prev && us->prev->prev) {
+			us = us->prev;
+		}
+
+#ifdef WITH_GLOBAL_UNDO_KEEP_ONE
+		/* Hack, we need to keep at least one BKE_UNDOSYS_TYPE_MEMFILE. */
+		if (us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
+			us_exclude = us->prev;
+			while (us_exclude && us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
+				us_exclude = us_exclude->prev;
+			}
+			if (us_exclude) {
+				BLI_remlink(&ustack->steps, us_exclude);
+			}
+		}
+#endif
+		/* Free from first to last, free functions may update de-duplication info (see #MemFileUndoStep). */
+		while (ustack->steps.first != us) {
+			UndoStep *us_first = ustack->steps.first;
+			BLI_assert(us_first != ustack->step_active);
+			undosys_step_free_and_unlink(ustack, us_first);
+		}
+
+#ifdef WITH_GLOBAL_UNDO_KEEP_ONE
+		if (us_exclude) {
+			BLI_addhead(&ustack->steps, us_exclude);
+		}
+#endif
+	}
+}
+
+/** \} */
+
+void BKE_undosys_step_push_init_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
+{
+	UNDO_NESTED_ASSERT(false);
+	/* We could detect and clean this up (but it should never happen!). */
+	BLI_assert(ustack->step_init == NULL);
+	if (ut->step_encode_init) {
+		undosys_stack_validate(ustack, false);
+		UndoStep *us = MEM_callocN(ut->step_size, __func__);
+		CLOG_INFO(&LOG, 1, "%p, '%s', type='%s'", us, name, us->type->name);
+		if (name != NULL) {
+			BLI_strncpy(us->name, name, sizeof(us->name));
+		}
+		us->type = ut;
+		ustack->step_init = us;
+		ut->step_encode_init(C, us);
+		undosys_stack_validate(ustack, true);
+	}
+}
+
+void BKE_undosys_step_push_init(UndoStack *ustack, bContext *C, const char *name)
+{
+	UNDO_NESTED_ASSERT(false);
+	/* We could detect and clean this up (but it should never happen!). */
+	BLI_assert(ustack->step_init == NULL);
+	const UndoType *ut = BKE_undosys_type_from_context(C);
+	if (ut == NULL) {
+		return;
+	}
+	return BKE_undosys_step_push_init_with_type(ustack, C, name, ut);
+}
+
+bool BKE_undosys_step_push_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
+{
+	UNDO_NESTED_ASSERT(false);
+	undosys_stack_validate(ustack, false);
+	bool is_not_empty = ustack->step_active != NULL;
+
+	/* Remove all undos after (also when 'ustack->step_active == NULL'). */
+	while (ustack->steps.last != ustack->step_active) {
+		UndoStep *us_iter = ustack->steps.last;
+		undosys_step_free_and_unlink(ustack, us_iter);
+		undosys_stack_validate(ustack, is_not_empty);
+	}
+
+	if (ustack->step_active) {
+		BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
+	}
+
+#ifdef WITH_GLOBAL_UNDO_ENSURE_UPDATED
+	if (ut->step_foreach_ID_ref != NULL) {
+		Main *bmain = G.main;
+		if (bmain->is_memfile_undo_written == false) {
+			const char *name_internal = "MemFile Internal";
+			if (undosys_stack_push_main(ustack, name_internal, bmain)) {
+				UndoStep *us = ustack->steps.last;
+				BLI_assert(STREQ(us->name, name_internal));
+				us->skip = true;
+			}
+		}
+	}
+#endif
+
+	UndoStep *us = ustack->step_init ? ustack->step_init : MEM_callocN(ut->step_size, __func__);
+	ustack->step_init = NULL;
+	if (us->name[0] == '\0') {
+		BLI_strncpy(us->name, name, sizeof(us->name));
+	}
+	us->type = ut;
+	/* initialized, not added yet. */
+
+	if (undosys_step_encode(C, us)) {
+		ustack->step_active = us;
+		BLI_addtail(&ustack->steps, us);
+		undosys_stack_validate(ustack, true);
+		return true;
+	}
+	else {
+		MEM_freeN(us);
+		undosys_stack_validate(ustack, true);
+		return false;
+	}
+}
+
+bool BKE_undosys_step_push(UndoStack *ustack, bContext *C, const char *name)
+{
+	UNDO_NESTED_ASSERT(false);
+	const UndoType *ut = ustack->step_init ? ustack->step_init->type : BKE_undosys_type_from_context(C);
+	if (ut == NULL) {
+		return false;
+	}
+	return BKE_undosys_step_push_with_type(ustack, C, name, ut);
+}
+
+
+/**
+ * Useful when we want to diff against previous undo data but can't be sure the types match.
+ */
+UndoStep *BKE_undosys_step_same_type_next(UndoStep *us)
+{
+	if (us) {
+		const UndoType *ut = us->type;
+		while ((us = us->next)) {
+			if (us->type == ut) {
+				return us;
+			}
+		}
+
+	}
+	return us;
+}
+
+/**
+ * Useful when we want to diff against previous undo data but can't be sure the types match.
+ */
+UndoStep *BKE_undosys_step_same_type_prev(UndoStep *us)
+{
+	if (us) {
+		const UndoType *ut = us->type;
+		while ((us = us->prev)) {
+			if (us->type == ut) {
+				return us;
+			}
+		}
+
+	}
+	return us;
+}
+
+UndoStep *BKE_undosys_step_find_by_name_with_type(UndoStack *ustack, const char *name, const UndoType *ut)
+{
+	for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
+		if (us->type == ut) {
+			if (STREQ(name, us->name)) {
+				return us;
+			}
+		}
+	}
+	return NULL;
+}
+
+UndoStep *BKE_undosys_step_find_by_name(UndoStack *ustack, const char *name)
+{
+	return BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
+}
+
+bool BKE_undosys_step_undo_with_data_ex(
+        UndoStack *ustack, bContext *C, UndoStep *us,
+        bool use_skip)
+{
+	UNDO_NESTED_ASSERT(false);
+	if (us) {
+		undosys_stack_validate(ustack, true);
+	}
+	UndoStep *us_prev = us ? us->prev : NULL;
+	if (us && us->type->mode == BKE_UNDOTYPE_MODE_STORE) {
+		/* The current state is a copy, we need to load the previous state. */
+		us = us_prev;
+	}
+
+	if (us != NULL) {
+		CLOG_INFO(&LOG, 1, "%p, '%s', type='%s'", us, us->name, us->type->name);
+		undosys_step_decode(C, us, -1);
+		ustack->step_active = us_prev;
+		undosys_stack_validate(ustack, true);
+		if (use_skip) {
+			if (ustack->step_active && ustack->step_active->skip) {
+				CLOG_INFO(&LOG, 2, "undo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
+				BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
+			}
+		}
+		return true;
+	}
+	return false;
+}
+bool BKE_undosys_step_undo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
+{
+	return BKE_undosys_step_undo_with_data_ex(ustack, C, us, true);
+}
+
+bool BKE_undosys_step_undo(UndoStack *ustack, bContext *C)
+{
+	return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
+}
+
+void BKE_undosys_step_undo_from_index(UndoStack *ustack, bContext *C, int index)
+{
+	UndoStep *us = BLI_findlink(&ustack->steps, index);
+	BLI_assert(us->skip == false);
+	BKE_undosys_step_load_data(ustack, C, us);
+}
+
+bool BKE_undosys_step_redo_with_data_ex(
+        UndoStack *ustack, bContext *C, UndoStep *us,
+        bool use_skip)
+{
+	UNDO_NESTED_ASSERT(false);
+	UndoStep *us_next = us ? us->next : NULL;
+	/* Unlike undo accumulate, we always use the next. */
+	us = us_next;
+
+	if (us != NULL) {
+		CLOG_INFO(&LOG, 1, "%p, '%s', type='%s'", us, us->name, us->type->name);
+		undosys_step_decode(C, us, 1);
+		ustack->step_active = us_next;
+		if (use_skip) {
+			if (ustack->step_active && ustack->step_active->skip) {
+				CLOG_INFO(&LOG, 2, "redo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
+				BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
+			}
+		}
+		return true;
+	}
+	return false;
+}
+bool BKE_undosys_step_redo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
+{
+	return BKE_undosys_step_redo_with_data_ex(ustack, C, us, true);
+}
+
+bool BKE_undosys_step_redo(UndoStack *ustack, bContext *C)
+{
+	return BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
+}
+
+bool BKE_undosys_step_load_data(UndoStack *ustack, bContext *C, UndoStep *us)
+{
+	UNDO_NESTED_ASSERT(false);
+	const int index_active = BLI_findindex(&ustack->steps, ustack->step_active);
+	const int index_target = BLI_findindex(&ustack->steps, us);
+	BLI_assert(!ELEM(-1, index_active, index_target));
+	bool ok = true;
+
+	if (index_target < index_active) {
+		uint i = index_active - index_target;
+		while (i-- && ok) {
+			ok = BKE_undosys_step_undo_with_data_ex(ustack, C, ustack->step_active, false);
+		}
+	}
+	else if (index_target > index_active) {
+		uint i = index_target - index_active;
+		while (i-- && ok) {
+			ok = BKE_undosys_step_redo_with_data_ex(ustack, C, ustack->step_active, false);
+		}
+	}
+
+	if (ok) {
+		BLI_assert(ustack->step_active == us);
+	}
+
+	return ok;
+}
+
+bool BKE_undosys_step_undo_compat_only(UndoStack *ustack, bContext *C, int step)
+{
+	if (step == 0) {
+		return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
+	}
+	else if (step == 1) {
+		return BKE_undosys_step_undo(ustack, C);
+	}
+	else {
+		return BKE_undosys_step_redo(ustack, C);
+	}
+}
+/**
+ * Similar to #WM_operatortype_append
+ */
+UndoType *BKE_undosys_type_append(void (*undosys_fn)(UndoType *))
+{
+	UndoType *ut;
+
+	ut = MEM_callocN(sizeof(UndoType), __func__);
+
+	undosys_fn(ut);
+
+	BLI_assert(ut->mode != 0);
+
+	BLI_addtail(&g_undo_types, ut);
+
+	return ut;
+}
+
+void BKE_undosys_type_free_all(void)
+{
+	UndoType *ut;
+	while ((ut = BLI_pophead(&g_undo_types))) {
+		MEM_freeN(ut);
+	}
+}
+
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name ID Reference Utilities
+ *
+ * Unfortunately we need this for a handful of places.
+ */
+
+static void UNUSED_FUNCTION(BKE_undosys_foreach_ID_ref(
+        UndoStack *ustack, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data))
+{
+	for (UndoStep *us = ustack->steps.first; us; us = us->next) {
+		const UndoType *ut = us->type;
+		if (ut->step_foreach_ID_ref != NULL) {
+			ut->step_foreach_ID_ref(us, foreach_ID_ref_fn, user_data);
+		}
+	}
+}
+
+typedef struct UndoIDPtrMapItem {
+	/** Never changes (matches undo data). Use as sort key for binary search. */
+	const void *ptr;
+	/** Write the new pointers here. */
+	uint index;
+} UndoIDPtrMapItem;
+
+typedef struct UndoIDPtrMap {
+	UndoRefID *refs;
+	/**
+	 * Pointer map, update 'dst' members before use.
+	 * This is always sorted (adds some overhead when adding, in practice it's acceptable since).
+	 */
+	UndoIDPtrMapItem *pmap;
+
+	/** Length for both 'refs' & 'pmap' */
+	uint len;
+	uint len_alloc;
+} UndoIDPtrMap;
+
+#ifdef DEBUG
+#  define PMAP_DEFAULT_ALLOC 1
+#else
+#  define PMAP_DEFAULT_ALLOC 32
+#endif
+
+void BKE_undosys_ID_map_foreach_ID_ref(
+        UndoIDPtrMap *map,
+        UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
+{
+	for (uint i = 0; i < map->len; i++) {
+		foreach_ID_ref_fn(user_data, &map->refs[i]);
+	}
+}
+
+/**
+ * Return true when found, otherwise index is set to the index we should insert.
+ */
+static bool undosys_ID_map_lookup_index(const UndoIDPtrMap *map, const void *key, uint *r_index)
+{
+	const UndoIDPtrMapItem *pmap = map->pmap;
+	const uint len = map->len;
+	if (len == 0) {
+		if (*r_index) {
+			*r_index = 0;
+		}
+		return false;
+	}
+	int min = 0, max = len - 1;
+	while (min <= max) {
+		const uint mid = (min + max) / 2;
+		if (pmap[mid].ptr < key) {
+			min = mid + 1;
+		}
+		else if (pmap[mid].ptr == key) {
+			if (r_index) {
+				*r_index = mid;
+			}
+			return true;
+		}
+		else if (pmap[mid].ptr > key) {
+			max = mid - 1;
+		}
+	}
+	return false;
+}
+
+/**
+ * A set of ID's use for efficient decoding, so we can map pointers back to the newly loaded data
+ * without performing full look ups each time.
+ *
+ * This can be used as an old_pointer -> new_pointer lookup.
+ */
+UndoIDPtrMap *BKE_undosys_ID_map_create(void)
+{
+	UndoIDPtrMap *map = MEM_mallocN(sizeof(*map), __func__);
+	map->len_alloc = PMAP_DEFAULT_ALLOC;
+	map->refs = MEM_mallocN(sizeof(*map->refs) * map->len_alloc, __func__);
+	map->pmap = MEM_mallocN(sizeof(*map->pmap) * map->len_alloc, __func__);
+	map->len = 0;
+	return map;
+}
+void BKE_undosys_ID_map_destroy(UndoIDPtrMap *idpmap)
+{
+	MEM_SAFE_FREE(idpmap->refs);
+	MEM_SAFE_FREE(idpmap->pmap);
+	MEM_freeN(idpmap);
+}
+
+void BKE_undosys_ID_map_add(UndoIDPtrMap *map, ID *id)
+{
+	uint index;
+	if (id->lib != NULL) {
+		return;
+	}
+
+	if (undosys_ID_map_lookup_index(map, id, &index)) {
+		return;  /* exists. */
+	}
+
+	const uint len_src = map->len;
+	const uint len_dst = map->len + 1;
+	if (len_dst > map->len_alloc) {
+		map->len_alloc *= 2;
+		BLI_assert(map->len_alloc >= len_dst);
+		map->pmap = MEM_reallocN(map->pmap, sizeof(*map->pmap) * map->len_alloc);
+		map->refs = MEM_reallocN(map->refs, sizeof(*map->refs) * map->len_alloc);
+	}
+
+#if 0  /* Will be done automatically in callback. */
+	BLI_strncpy(map->refs[len_src].name, id->name, sizeof(id->name));
+#else
+	map->refs[len_src].name[0] = '\0';
+#endif
+	map->refs[len_src].ptr = id;
+
+	map->pmap[len_src].ptr = id;
+	map->pmap[len_src].index = len_src;
+	map->len = len_dst;
+
+	qsort(map->pmap, map->len, sizeof(*map->pmap), BLI_sortutil_cmp_ptr);
+}
+
+ID *BKE_undosys_ID_map_lookup(const UndoIDPtrMap *map, const ID *id_src)
+{
+	/* We should only ever lookup indices which exist! */
+	uint index;
+	if (!undosys_ID_map_lookup_index(map, id_src, &index)) {
+		BLI_assert(0);
+	}
+	ID *id_dst = map->refs[index].ptr;
+	BLI_assert(id_dst != NULL);
+	BLI_assert(STREQ(id_dst->name, map->refs[index].name));
+	return id_dst;
+}
+
+/** \} */