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

3 files changed, 228 insertions, 57 deletions

diff --git a/source/blender/editors/curve/editcurve.c b/source/blender/editors/curve/editcurve.c
index 0dbe526117c..ebf2b63bb49 100644
--- a/source/blender/editors/curve/editcurve.c
+++ b/source/blender/editors/curve/editcurve.c
@@ -1229,7 +1229,10 @@ void ED_curve_editnurb_make(Object *obedit)
 
 		if (actkey) {
 			// XXX strcpy(G.editModeTitleExtra, "(Key) ");
+			/* TODO(campbell): undo_system: investigate why this was needed. */
+#if 0
 			undo_editmode_clear();
+#endif
 		}
 
 		if (editnurb) {
diff --git a/source/blender/editors/curve/editcurve_undo.c b/source/blender/editors/curve/editcurve_undo.c
index f8f96eb3bc9..1bc2d6219b9 100644
--- a/source/blender/editors/curve/editcurve_undo.c
+++ b/source/blender/editors/curve/editcurve_undo.c
@@ -30,18 +30,29 @@
 
 #include "BLI_blenlib.h"
 #include "BLI_ghash.h"
+#include "BLI_array_utils.h"
 
 #include "BKE_context.h"
 #include "BKE_curve.h"
 #include "BKE_fcurve.h"
 #include "BKE_library.h"
 #include "BKE_animsys.h"
+#include "BKE_depsgraph.h"
+#include "BKE_undo_system.h"
 
+#include "ED_object.h"
 #include "ED_util.h"
 #include "ED_curve.h"
 
+#include "WM_types.h"
+#include "WM_api.h"
+
 #include "curve_intern.h"
 
+/* -------------------------------------------------------------------- */
+/** \name Undo Conversion
+ * \{ */
+
 typedef struct {
 	ListBase nubase;
 	int actvert;
@@ -49,13 +60,12 @@ typedef struct {
 	ListBase fcurves, drivers;
 	int actnu;
 	int flag;
+	size_t undo_size;
 } UndoCurve;
 
-static void undoCurve_to_editCurve(void *ucu, void *UNUSED(edata), void *cu_v)
+static void undocurve_to_editcurve(UndoCurve *ucu, Curve *cu)
 {
-	Curve *cu = cu_v;
-	UndoCurve *undoCurve = ucu;
-	ListBase *undobase = &undoCurve->nubase;
+	ListBase *undobase = &ucu->nubase;
 	ListBase *editbase = BKE_curve_editNurbs_get(cu);
 	Nurb *nu, *newnu;
 	EditNurb *editnurb = cu->editnurb;
@@ -63,19 +73,19 @@ static void undoCurve_to_editCurve(void *ucu, void *UNUSED(edata), void *cu_v)
 
 	BKE_nurbList_free(editbase);
 
-	if (undoCurve->undoIndex) {
+	if (ucu->undoIndex) {
 		BKE_curve_editNurb_keyIndex_free(&editnurb->keyindex);
-		editnurb->keyindex = ED_curve_keyindex_hash_duplicate(undoCurve->undoIndex);
+		editnurb->keyindex = ED_curve_keyindex_hash_duplicate(ucu->undoIndex);
 	}
 
 	if (ad) {
 		if (ad->action) {
 			free_fcurves(&ad->action->curves);
-			copy_fcurves(&ad->action->curves, &undoCurve->fcurves);
+			copy_fcurves(&ad->action->curves, &ucu->fcurves);
 		}
 
 		free_fcurves(&ad->drivers);
-		copy_fcurves(&ad->drivers, &undoCurve->drivers);
+		copy_fcurves(&ad->drivers, &ucu->drivers);
 	}
 
 	/* copy  */
@@ -89,75 +99,149 @@ static void undoCurve_to_editCurve(void *ucu, void *UNUSED(edata), void *cu_v)
 		BLI_addtail(editbase, newnu);
 	}
 
-	cu->actvert = undoCurve->actvert;
-	cu->actnu = undoCurve->actnu;
-	cu->flag = undoCurve->flag;
+	cu->actvert = ucu->actvert;
+	cu->actnu = ucu->actnu;
+	cu->flag = ucu->flag;
 	ED_curve_updateAnimPaths(cu);
 }
 
-static void *editCurve_to_undoCurve(void *UNUSED(edata), void *cu_v)
+static void undocurve_from_editcurve(UndoCurve *ucu, Curve *cu)
 {
-	Curve *cu = cu_v;
+	BLI_assert(BLI_array_is_zeroed(ucu, 1));
 	ListBase *nubase = BKE_curve_editNurbs_get(cu);
-	UndoCurve *undoCurve;
 	EditNurb *editnurb = cu->editnurb, tmpEditnurb;
 	Nurb *nu, *newnu;
 	AnimData *ad = BKE_animdata_from_id(&cu->id);
 
-	undoCurve = MEM_callocN(sizeof(UndoCurve), "undoCurve");
+	/* TODO: include size of fcurve & undoIndex */
+	// ucu->undo_size = 0;
 
 	if (editnurb->keyindex) {
-		undoCurve->undoIndex = ED_curve_keyindex_hash_duplicate(editnurb->keyindex);
-		tmpEditnurb.keyindex = undoCurve->undoIndex;
+		ucu->undoIndex = ED_curve_keyindex_hash_duplicate(editnurb->keyindex);
+		tmpEditnurb.keyindex = ucu->undoIndex;
 	}
 
 	if (ad) {
 		if (ad->action)
-			copy_fcurves(&undoCurve->fcurves, &ad->action->curves);
+			copy_fcurves(&ucu->fcurves, &ad->action->curves);
 
-		copy_fcurves(&undoCurve->drivers, &ad->drivers);
+		copy_fcurves(&ucu->drivers, &ad->drivers);
 	}
 
 	/* copy  */
 	for (nu = nubase->first; nu; nu = nu->next) {
 		newnu = BKE_nurb_duplicate(nu);
 
-		if (undoCurve->undoIndex) {
+		if (ucu->undoIndex) {
 			ED_curve_keyindex_update_nurb(&tmpEditnurb, nu, newnu);
 		}
 
-		BLI_addtail(&undoCurve->nubase, newnu);
+		BLI_addtail(&ucu->nubase, newnu);
+
+		ucu->undo_size += (
+		        (nu->bezt ? (sizeof(BezTriple) * nu->pntsu) : 0) +
+		        (nu->bp ? (sizeof(BPoint) * (nu->pntsu * nu->pntsv)) : 0) +
+		        (nu->knotsu ? (sizeof(float) * KNOTSU(nu)) : 0) +
+		        (nu->knotsv ? (sizeof(float) * KNOTSV(nu)) : 0) +
+		        sizeof(Nurb));
 	}
 
-	undoCurve->actvert = cu->actvert;
-	undoCurve->actnu = cu->actnu;
-	undoCurve->flag = cu->flag;
+	ucu->actvert = cu->actvert;
+	ucu->actnu = cu->actnu;
+	ucu->flag = cu->flag;
+}
+
+static void undocurve_free_data(UndoCurve *uc)
+{
+	BKE_nurbList_free(&uc->nubase);
+
+	BKE_curve_editNurb_keyIndex_free(&uc->undoIndex);
 
-	return undoCurve;
+	free_fcurves(&uc->fcurves);
+	free_fcurves(&uc->drivers);
 }
 
-static void free_undoCurve(void *ucv)
+static Object *editcurve_object_from_context(bContext *C)
 {
-	UndoCurve *undoCurve = ucv;
+	Object *obedit = CTX_data_edit_object(C);
+	if (obedit && ELEM(obedit->type, OB_CURVE, OB_SURF)) {
+		Curve *cu = obedit->data;
+		if (BKE_curve_editNurbs_get(cu) != NULL) {
+			return obedit;
+		}
+	}
+	return NULL;
+}
 
-	BKE_nurbList_free(&undoCurve->nubase);
+/** \} */
 
-	BKE_curve_editNurb_keyIndex_free(&undoCurve->undoIndex);
+/* -------------------------------------------------------------------- */
+/** \name Implements ED Undo System
+ * \{ */
 
-	free_fcurves(&undoCurve->fcurves);
-	free_fcurves(&undoCurve->drivers);
+typedef struct CurveUndoStep {
+	UndoStep step;
+	/* note: will split out into list for multi-object-editmode. */
+	UndoRefID_Object obedit_ref;
+	UndoCurve data;
+} CurveUndoStep;
 
-	MEM_freeN(undoCurve);
+static bool curve_undosys_poll(bContext *C)
+{
+	Object *obedit = editcurve_object_from_context(C);
+	return (obedit != NULL);
 }
 
-static void *get_data(bContext *C)
+static bool curve_undosys_step_encode(struct bContext *C, UndoStep *us_p)
 {
-	Object *obedit = CTX_data_edit_object(C);
-	return obedit;
+	CurveUndoStep *us = (CurveUndoStep *)us_p;
+	us->obedit_ref.ptr = editcurve_object_from_context(C);
+	undocurve_from_editcurve(&us->data, us->obedit_ref.ptr->data);
+	us->step.data_size = us->data.undo_size;
+	return true;
 }
 
-/* and this is all the undo system needs to know */
-void undo_push_curve(bContext *C, const char *name)
+static void curve_undosys_step_decode(struct bContext *C, UndoStep *us_p, int UNUSED(dir))
 {
-	undo_editmode_push(C, name, get_data, free_undoCurve, undoCurve_to_editCurve, editCurve_to_undoCurve, NULL);
+	/* TODO(campbell): undo_system: use low-level API to set mode. */
+	ED_object_mode_set(C, OB_MODE_EDIT);
+	BLI_assert(curve_undosys_poll(C));
+
+	CurveUndoStep *us = (CurveUndoStep *)us_p;
+	Object *obedit = us->obedit_ref.ptr;
+	undocurve_to_editcurve(&us->data, obedit->data);
+	DAG_id_tag_update(&obedit->id, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM | ND_DATA, NULL);
 }
+
+static void curve_undosys_step_free(UndoStep *us_p)
+{
+	CurveUndoStep *us = (CurveUndoStep *)us_p;
+	undocurve_free_data(&us->data);
+}
+
+static void curve_undosys_foreach_ID_ref(
+        UndoStep *us_p, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
+{
+	CurveUndoStep *us = (CurveUndoStep *)us_p;
+	foreach_ID_ref_fn(user_data, ((UndoRefID *)&us->obedit_ref));
+}
+
+/* Export for ED_undo_sys. */
+void ED_curve_undosys_type(UndoType *ut)
+{
+	ut->name = "Edit Curve";
+	ut->poll = curve_undosys_poll;
+	ut->step_encode = curve_undosys_step_encode;
+	ut->step_decode = curve_undosys_step_decode;
+	ut->step_free = curve_undosys_step_free;
+
+	ut->step_foreach_ID_ref = curve_undosys_foreach_ID_ref;
+
+	ut->mode = BKE_UNDOTYPE_MODE_STORE;
+	ut->use_context = true;
+
+	ut->step_size = sizeof(CurveUndoStep);
+}
+
+/** \} */
diff --git a/source/blender/editors/curve/editfont_undo.c b/source/blender/editors/curve/editfont_undo.c
index a61f863b61e..3a76d0333f9 100644
--- a/source/blender/editors/curve/editfont_undo.c
+++ b/source/blender/editors/curve/editfont_undo.c
@@ -29,6 +29,8 @@
 #include "MEM_guardedalloc.h"
 
 #include "BLI_utildefines.h"
+#include "BLI_array_utils.h"
+
 
 #include "DNA_curve_types.h"
 #include "DNA_object_types.h"
@@ -36,10 +38,16 @@
 
 #include "BKE_context.h"
 #include "BKE_font.h"
+#include "BKE_depsgraph.h"
+#include "BKE_undo_system.h"
 
+#include "ED_object.h"
 #include "ED_curve.h"
 #include "ED_util.h"
 
+#include "WM_types.h"
+#include "WM_api.h"
+
 #define USE_ARRAY_STORE
 
 #ifdef USE_ARRAY_STORE
@@ -50,6 +58,10 @@
 #  define ARRAY_CHUNK_SIZE 32
 #endif
 
+/* -------------------------------------------------------------------- */
+/** \name Undo Conversion
+ * \{ */
+
 typedef struct UndoFont {
 	wchar_t *textbuf;
 	struct CharInfo *textbufinfo;
@@ -62,6 +74,8 @@ typedef struct UndoFont {
 		BArrayState *textbufinfo;
 	} store;
 #endif
+
+	size_t undo_size;
 } UndoFont;
 
 
@@ -202,23 +216,20 @@ static void uf_arraystore_free(UndoFont *uf)
 
 		BLI_array_store_at_size_clear(&uf_arraystore.bs_stride);
 	}
-
 }
 
 /** \} */
 
 #endif  /* USE_ARRAY_STORE */
 
-static void undoFont_to_editFont(void *uf_v, void *ecu, void *UNUSED(obdata))
+static void undofont_to_editfont(UndoFont *uf, Curve *cu)
 {
-	Curve *cu = (Curve *)ecu;
 	EditFont *ef = cu->editfont;
-	const UndoFont *uf = uf_v;
 
 	size_t final_size;
 
 #ifdef USE_ARRAY_STORE
-	uf_arraystore_expand(uf_v);
+	uf_arraystore_expand(uf);
 #endif
 
 	final_size = sizeof(wchar_t) * (uf->len + 1);
@@ -233,16 +244,17 @@ static void undoFont_to_editFont(void *uf_v, void *ecu, void *UNUSED(obdata))
 	ef->selstart = ef->selend = 0;
 
 #ifdef USE_ARRAY_STORE
-	uf_arraystore_expand_clear(uf_v);
+	uf_arraystore_expand_clear(uf);
 #endif
 }
 
-static void *editFont_to_undoFont(void *ecu, void *UNUSED(obdata))
+static void *undofont_from_editfont(UndoFont *uf, Curve *cu)
 {
-	Curve *cu = (Curve *)ecu;
+	BLI_assert(BLI_array_is_zeroed(uf, 1));
+
 	EditFont *ef = cu->editfont;
 
-	UndoFont *uf = MEM_callocN(sizeof(*uf), __func__);
+	size_t mem_used_prev = MEM_get_memory_in_use();
 
 	size_t final_size;
 
@@ -269,13 +281,15 @@ static void *editFont_to_undoFont(void *ecu, void *UNUSED(obdata))
 	}
 #endif
 
+	size_t mem_used_curr = MEM_get_memory_in_use();
+
+	uf->undo_size = mem_used_prev < mem_used_curr ? mem_used_curr - mem_used_prev : sizeof(UndoFont);
+
 	return uf;
 }
 
-static void free_undoFont(void *uf_v)
+static void undofont_free_data(UndoFont *uf)
 {
-	UndoFont *uf = uf_v;
-
 #ifdef USE_ARRAY_STORE
 	{
 		LinkData *link = BLI_findptr(&uf_arraystore.local_links, uf, offsetof(LinkData, data));
@@ -291,21 +305,91 @@ static void free_undoFont(void *uf_v)
 	if (uf->textbufinfo) {
 		MEM_freeN(uf->textbufinfo);
 	}
-
-	MEM_freeN(uf);
 }
 
-static void *get_undoFont(bContext *C)
+static Object *editfont_object_from_context(bContext *C)
 {
 	Object *obedit = CTX_data_edit_object(C);
 	if (obedit && obedit->type == OB_FONT) {
-		return obedit->data;
+		Curve *cu = obedit->data;
+		EditFont *ef = cu->editfont;
+		if (ef != NULL) {
+			return obedit;
+		}
 	}
 	return NULL;
 }
 
-/* and this is all the undo system needs to know */
-void undo_push_font(bContext *C, const char *name)
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Implements ED Undo System
+ * \{ */
+
+typedef struct FontUndoStep {
+	UndoStep step;
+	/* note: will split out into list for multi-object-editmode. */
+	UndoRefID_Object obedit_ref;
+	UndoFont data;
+} FontUndoStep;
+
+static bool font_undosys_poll(bContext *C)
+{
+	return editfont_object_from_context(C) != NULL;
+}
+
+static bool font_undosys_step_encode(struct bContext *C, UndoStep *us_p)
+{
+	FontUndoStep *us = (FontUndoStep *)us_p;
+	us->obedit_ref.ptr = editfont_object_from_context(C);
+	Curve *cu = us->obedit_ref.ptr->data;
+	undofont_from_editfont(&us->data, cu);
+	us->step.data_size = us->data.undo_size;
+	return true;
+}
+
+static void font_undosys_step_decode(struct bContext *C, UndoStep *us_p, int UNUSED(dir))
+{
+	/* TODO(campbell): undo_system: use low-level API to set mode. */
+	ED_object_mode_set(C, OB_MODE_EDIT);
+	BLI_assert(font_undosys_poll(C));
+
+	FontUndoStep *us = (FontUndoStep *)us_p;
+	Object *obedit = us->obedit_ref.ptr;
+	Curve *cu = obedit->data;
+	undofont_to_editfont(&us->data, cu);
+	DAG_id_tag_update(&obedit->id, OB_RECALC_DATA);
+	WM_event_add_notifier(C, NC_GEOM | ND_DATA, NULL);
+}
+
+static void font_undosys_step_free(UndoStep *us_p)
+{
+	FontUndoStep *us = (FontUndoStep *)us_p;
+	undofont_free_data(&us->data);
+}
+
+static void font_undosys_foreach_ID_ref(
+        UndoStep *us_p, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
 {
-	undo_editmode_push(C, name, get_undoFont, free_undoFont, undoFont_to_editFont, editFont_to_undoFont, NULL);
+	FontUndoStep *us = (FontUndoStep *)us_p;
+	foreach_ID_ref_fn(user_data, ((UndoRefID *)&us->obedit_ref));
 }
+
+/* Export for ED_undo_sys. */
+void ED_font_undosys_type(UndoType *ut)
+{
+	ut->name = "Edit Font";
+	ut->poll = font_undosys_poll;
+	ut->step_encode = font_undosys_step_encode;
+	ut->step_decode = font_undosys_step_decode;
+	ut->step_free = font_undosys_step_free;
+
+	ut->step_foreach_ID_ref = font_undosys_foreach_ID_ref;
+
+	ut->mode = BKE_UNDOTYPE_MODE_STORE;
+	ut->use_context = true;
+
+	ut->step_size = sizeof(FontUndoStep);
+}
+
+/** \} */