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

4 files changed, 126 insertions, 156 deletions

diff --git a/source/blender/editors/physics/particle_edit.c b/source/blender/editors/physics/particle_edit.c
index 93bfd156707..fce43fa6425 100644
--- a/source/blender/editors/physics/particle_edit.c
+++ b/source/blender/editors/physics/particle_edit.c
@@ -126,8 +126,6 @@ void PE_free_ptcache_edit(PTCacheEdit *edit)
 
 	if (edit==0) return;
 
-	PTCacheUndo_clear(edit);
-
 	if (edit->points) {
 		LOOP_POINTS {
 			if (point->keys)
@@ -4380,8 +4378,11 @@ void PE_create_particle_edit(Scene *scene, Object *ob, PointCache *cache, Partic
 			recalc_emitter_field(ob, psys);
 		PE_update_object(scene, ob, 1);
 
-		PTCacheUndo_clear(edit);
+		/* Causes issues, adding undo pushes while performing undo history.
+		 * Seems not to like this isn't needed anyway - Campbell. */
+#if 0
 		PE_undo_push(scene, "Original");
+#endif
 	}
 }
 
diff --git a/source/blender/editors/physics/particle_edit_undo.c b/source/blender/editors/physics/particle_edit_undo.c
index 288e59a8671..329658a56e1 100644
--- a/source/blender/editors/physics/particle_edit_undo.c
+++ b/source/blender/editors/physics/particle_edit_undo.c
@@ -38,6 +38,7 @@
 
 #include "DNA_scene_types.h"
 #include "DNA_meshdata_types.h"
+#include "DNA_windowmanager_types.h"
 
 #include "BLI_listbase.h"
 #include "BLI_string.h"
@@ -47,38 +48,29 @@
 #include "BKE_global.h"
 #include "BKE_particle.h"
 #include "BKE_pointcache.h"
+#include "BKE_context.h"
+#include "BKE_main.h"
+#include "BKE_undo_system.h"
 
+#include "ED_object.h"
 #include "ED_particle.h"
+#include "ED_physics.h"
 
 #include "particle_edit_utildefines.h"
 
 #include "physics_intern.h"
 
-static void free_PTCacheUndo(PTCacheUndo *undo)
-{
-	PTCacheEditPoint *point;
-	int i;
-
-	for (i=0, point=undo->points; i<undo->totpoint; i++, point++) {
-		if (undo->particles && (undo->particles + i)->hair)
-			MEM_freeN((undo->particles + i)->hair);
-		if (point->keys)
-			MEM_freeN(point->keys);
-	}
-	if (undo->points)
-		MEM_freeN(undo->points);
+/* -------------------------------------------------------------------- */
+/** \name Undo Conversion
+ * \{ */
 
-	if (undo->particles)
-		MEM_freeN(undo->particles);
-
-	BKE_ptcache_free_mem(&undo->mem_cache);
-}
-
-static void make_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
+static void undoptcache_from_editcache(PTCacheUndo *undo, PTCacheEdit *edit)
 {
 	PTCacheEditPoint *point;
 	int i;
 
+	size_t mem_used_prev = MEM_get_memory_in_use();
+
 	undo->totpoint= edit->totpoint;
 
 	if (edit->psys) {
@@ -86,8 +78,9 @@ static void make_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 
 		pa= undo->particles= MEM_dupallocN(edit->psys->particles);
 
-		for (i=0; i<edit->totpoint; i++, pa++)
+		for (i=0; i<edit->totpoint; i++, pa++) {
 			pa->hair= MEM_dupallocN(pa->hair);
+		}
 
 		undo->psys_flag = edit->psys->flag;
 	}
@@ -98,8 +91,9 @@ static void make_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 		pm = undo->mem_cache.first;
 
 		for (; pm; pm=pm->next) {
-			for (i=0; i<BPHYS_TOT_DATA; i++)
+			for (i=0; i<BPHYS_TOT_DATA; i++) {
 				pm->data[i] = MEM_dupallocN(pm->data[i]);
+			}
 		}
 	}
 
@@ -110,9 +104,13 @@ static void make_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 		point->keys= MEM_dupallocN(point->keys);
 		/* no need to update edit key->co & key->time pointers here */
 	}
+
+	size_t mem_used_curr = MEM_get_memory_in_use();
+
+	undo->undo_size = mem_used_prev < mem_used_curr ? mem_used_curr - mem_used_prev : sizeof(PTCacheUndo);
 }
 
-static void get_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
+static void undoptcache_to_editcache(PTCacheUndo *undo, PTCacheEdit *edit)
 {
 	ParticleSystem *psys = edit->psys;
 	ParticleData *pa;
@@ -120,16 +118,20 @@ static void get_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 	POINT_P; KEY_K;
 
 	LOOP_POINTS {
-		if (psys && psys->particles[p].hair)
+		if (psys && psys->particles[p].hair) {
 			MEM_freeN(psys->particles[p].hair);
+		}
 
-		if (point->keys)
+		if (point->keys) {
 			MEM_freeN(point->keys);
+		}
 	}
-	if (psys && psys->particles)
+	if (psys && psys->particles) {
 		MEM_freeN(psys->particles);
-	if (edit->points)
+	}
+	if (edit->points) {
 		MEM_freeN(edit->points);
+	}
 	if (edit->mirror_cache) {
 		MEM_freeN(edit->mirror_cache);
 		edit->mirror_cache= NULL;
@@ -171,9 +173,9 @@ static void get_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 		pm = edit->pid.cache->mem_cache.first;
 
 		for (; pm; pm=pm->next) {
-			for (i=0; i<BPHYS_TOT_DATA; i++)
+			for (i = 0; i < BPHYS_TOT_DATA; i++) {
 				pm->data[i] = MEM_dupallocN(pm->data[i]);
-
+			}
 			BKE_ptcache_mem_pointers_init(pm);
 
 			LOOP_POINTS {
@@ -191,150 +193,122 @@ static void get_PTCacheUndo(PTCacheEdit *edit, PTCacheUndo *undo)
 	}
 }
 
-void PE_undo_push(Scene *scene, const char *str)
+static void undoptcache_free_data(PTCacheUndo *undo)
 {
-	PTCacheEdit *edit= PE_get_current(scene, OBACT);
-	PTCacheUndo *undo;
-	int nr;
-
-	if (!edit) return;
-
-	/* remove all undos after (also when curundo==NULL) */
-	while (edit->undo.last != edit->curundo) {
-		undo= edit->undo.last;
-		BLI_remlink(&edit->undo, undo);
-		free_PTCacheUndo(undo);
-		MEM_freeN(undo);
-	}
+	PTCacheEditPoint *point;
+	int i;
 
-	/* make new */
-	edit->curundo= undo= MEM_callocN(sizeof(PTCacheUndo), "particle undo file");
-	BLI_strncpy(undo->name, str, sizeof(undo->name));
-	BLI_addtail(&edit->undo, undo);
-	
-	/* and limit amount to the maximum */
-	nr= 0;
-	undo= edit->undo.last;
-	while (undo) {
-		nr++;
-		if (nr==U.undosteps) break;
-		undo= undo->prev;
-	}
-	if (undo) {
-		while (edit->undo.first != undo) {
-			PTCacheUndo *first= edit->undo.first;
-			BLI_remlink(&edit->undo, first);
-			free_PTCacheUndo(first);
-			MEM_freeN(first);
+	for (i = 0, point=undo->points; i < undo->totpoint; i++, point++) {
+		if (undo->particles && (undo->particles + i)->hair) {
+			MEM_freeN((undo->particles + i)->hair);
+		}
+		if (point->keys) {
+			MEM_freeN(point->keys);
 		}
 	}
-
-	/* copy  */
-	make_PTCacheUndo(edit, edit->curundo);
+	if (undo->points) {
+		MEM_freeN(undo->points);
+	}
+	if (undo->particles) {
+		MEM_freeN(undo->particles);
+	}
+	BKE_ptcache_free_mem(&undo->mem_cache);
 }
 
-void PE_undo_step(Scene *scene, int step)
-{	
-	PTCacheEdit *edit= PE_get_current(scene, OBACT);
+/** \} */
 
-	if (!edit) return;
+/* -------------------------------------------------------------------- */
+/** \name Implements ED Undo System
+ * \{ */
 
-	if (step==0) {
-		get_PTCacheUndo(edit, edit->curundo);
-	}
-	else if (step==1) {
-		
-		if (edit->curundo==NULL || edit->curundo->prev==NULL) {
-			/* pass */
-		}
-		else {
-			if (G.debug & G_DEBUG) printf("undo %s\n", edit->curundo->name);
-			edit->curundo= edit->curundo->prev;
-			get_PTCacheUndo(edit, edit->curundo);
-		}
-	}
-	else {
-		/* curundo has to remain current situation! */
-		
-		if (edit->curundo==NULL || edit->curundo->next==NULL) {
-			/* pass */
-		}
-		else {
-			get_PTCacheUndo(edit, edit->curundo->next);
-			edit->curundo= edit->curundo->next;
-			if (G.debug & G_DEBUG) printf("redo %s\n", edit->curundo->name);
-		}
-	}
+typedef struct ParticleUndoStep {
+	UndoStep step;
+	UndoRefID_Scene scene_ref;
+	UndoRefID_Object object_ref;
+	PTCacheUndo data;
+} ParticleUndoStep;
 
-	DAG_id_tag_update(&OBACT->id, OB_RECALC_DATA);
+static bool particle_undosys_poll(struct bContext *C)
+{
+	Scene *scene = CTX_data_scene(C);
+	Object *ob = OBACT;
+	PTCacheEdit *edit = PE_get_current(scene, ob);
+	return (edit != NULL);
 }
 
-bool PE_undo_is_valid(Scene *scene)
+static bool particle_undosys_step_encode(struct bContext *C, UndoStep *us_p)
 {
-	PTCacheEdit *edit= PE_get_current(scene, OBACT);
-	
-	if (edit) {
-		return (edit->undo.last != edit->undo.first);
-	}
-	return 0;
+	ParticleUndoStep *us = (ParticleUndoStep *)us_p;
+	us->scene_ref.ptr = CTX_data_scene(C);
+	us->object_ref.ptr = us->scene_ref.ptr->basact->object;
+	PTCacheEdit *edit = PE_get_current(us->scene_ref.ptr, us->object_ref.ptr);
+	undoptcache_from_editcache(&us->data, edit);
+	return true;
 }
 
-void PTCacheUndo_clear(PTCacheEdit *edit)
+static void particle_undosys_step_decode(struct bContext *C, UndoStep *us_p, int UNUSED(dir))
 {
-	PTCacheUndo *undo;
-
-	if (edit==NULL) return;
-	
-	undo= edit->undo.first;
-	while (undo) {
-		free_PTCacheUndo(undo);
-		undo= undo->next;
+	/* TODO(campbell): undo_system: use low-level API to set mode. */
+	ED_object_mode_set(C, OB_MODE_PARTICLE_EDIT);
+	BLI_assert(particle_undosys_poll(C));
+
+	ParticleUndoStep *us = (ParticleUndoStep *)us_p;
+	Scene *scene = us->scene_ref.ptr;
+	Object *ob = us->object_ref.ptr;
+	PTCacheEdit *edit = PE_get_current(scene, ob);
+	if (edit) {
+		undoptcache_to_editcache(&us->data, edit);
+		DAG_id_tag_update(&ob->id, OB_RECALC_DATA);
+	}
+	else {
+		BLI_assert(0);
 	}
-	BLI_freelistN(&edit->undo);
-	edit->curundo= NULL;
 }
 
-void PE_undo(Scene *scene)
+static void particle_undosys_step_free(UndoStep *us_p)
 {
-	PE_undo_step(scene, 1);
+	ParticleUndoStep *us = (ParticleUndoStep *)us_p;
+	undoptcache_free_data(&us->data);
 }
 
-void PE_redo(Scene *scene)
+static void particle_undosys_foreach_ID_ref(
+        UndoStep *us_p, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
 {
-	PE_undo_step(scene, -1);
+	ParticleUndoStep *us = (ParticleUndoStep *)us_p;
+	foreach_ID_ref_fn(user_data, ((UndoRefID *)&us->scene_ref));
+	foreach_ID_ref_fn(user_data, ((UndoRefID *)&us->object_ref));
 }
 
-void PE_undo_number(Scene *scene, int nr)
+/* Export for ED_undo_sys. */
+void ED_particle_undosys_type(UndoType *ut)
 {
-	PTCacheEdit *edit= PE_get_current(scene, OBACT);
-	PTCacheUndo *undo;
-	int a=0;
-	
-	for (undo= edit->undo.first; undo; undo= undo->next, a++) {
-		if (a==nr) break;
-	}
-	edit->curundo= undo;
-	PE_undo_step(scene, 0);
+	ut->name = "Edit Particle";
+	ut->poll = particle_undosys_poll;
+	ut->step_encode = particle_undosys_step_encode;
+	ut->step_decode = particle_undosys_step_decode;
+	ut->step_free = particle_undosys_step_free;
+
+	ut->step_foreach_ID_ref = particle_undosys_foreach_ID_ref;
+
+	ut->mode = BKE_UNDOTYPE_MODE_STORE;
+	ut->use_context = true;
+
+	ut->step_size = sizeof(ParticleUndoStep);
 }
 
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Utilities
+ * \{ */
 
-/* get name of undo item, return null if no item with this index */
-/* if active pointer, set it to 1 if true */
-const char *PE_undo_get_name(Scene *scene, int nr, bool *r_active)
+void PE_undo_push(struct Scene *scene, const char *str)
 {
-	PTCacheEdit *edit= PE_get_current(scene, OBACT);
-	PTCacheUndo *undo;
-	
-	if (r_active) *r_active = false;
-	
-	if (edit) {
-		undo= BLI_findlink(&edit->undo, nr);
-		if (undo) {
-			if (r_active && (undo == edit->curundo)) {
-				*r_active = true;
-			}
-			return undo->name;
-		}
-	}
-	return NULL;
+	wmWindowManager *wm = G.main->wm.first;
+	bContext *C_temp = CTX_create();
+	CTX_data_scene_set(C_temp, scene);
+	BKE_undosys_step_push_with_type(wm->undo_stack, C_temp, str, BKE_UNDOSYS_TYPE_PARTICLE);
+	CTX_free(C_temp);
 }
+
+/** \} */
diff --git a/source/blender/editors/physics/particle_object.c b/source/blender/editors/physics/particle_object.c
index d85720f956c..63b84df9fce 100644
--- a/source/blender/editors/physics/particle_object.c
+++ b/source/blender/editors/physics/particle_object.c
@@ -911,10 +911,7 @@ static void copy_particle_edit(Scene *scene, Object *ob, ParticleSystem *psys, P
 	
 	edit->emitter_field = NULL;
 	edit->emitter_cosnos = NULL;
-	
-	BLI_listbase_clear(&edit->undo);
-	edit->curundo = NULL;
-	
+
 	edit->points = MEM_dupallocN(edit_from->points);
 	pa = psys->particles;
 	LOOP_POINTS {
@@ -943,8 +940,7 @@ static void copy_particle_edit(Scene *scene, Object *ob, ParticleSystem *psys, P
 	recalc_lengths(edit);
 	recalc_emitter_field(ob, psys);
 	PE_update_object(scene, ob, true);
-	
-	PTCacheUndo_clear(edit);
+
 	PE_undo_push(scene, "Original");
 }
 
diff --git a/source/blender/editors/physics/physics_intern.h b/source/blender/editors/physics/physics_intern.h
index cb281936634..f3f3697caaa 100644
--- a/source/blender/editors/physics/physics_intern.h
+++ b/source/blender/editors/physics/physics_intern.h
@@ -68,7 +68,6 @@ void PARTICLE_OT_edited_clear(struct wmOperatorType *ot);
 
 void PARTICLE_OT_unify_length(struct wmOperatorType *ot);
 
-void PTCacheUndo_clear(struct PTCacheEdit *edit);
 void PE_create_particle_edit(struct Scene *scene, struct Object *ob, struct PointCache *cache, struct ParticleSystem *psys);
 void recalc_lengths(struct PTCacheEdit *edit);
 void recalc_emitter_field(struct Object *ob, struct ParticleSystem *psys);