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

1 files changed, 187 insertions, 0 deletions

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__ */