Undo System: remove accumulate/store modes
[blender.git] / source / blender / blenkernel / intern / undo_system.c
1 /*
2  * This program is free software; you can redistribute it and/or
3  * modify it under the terms of the GNU General Public License
4  * as published by the Free Software Foundation; either version 2
5  * of the License, or (at your option) any later version.
6  *
7  * This program is distributed in the hope that it will be useful,
8  * but WITHOUT ANY WARRANTY; without even the implied warranty of
9  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
10  * GNU General Public License for more details.
11  *
12  * You should have received a copy of the GNU General Public License
13  * along with this program; if not, write to the Free Software Foundation,
14  * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
15  */
16
17 /** \file blender/blenkernel/intern/undo_system.c
18  *  \ingroup bke
19  *
20  * Used by ED_undo.h, internal implementation.
21  */
22
23 #include <string.h>
24
25 #include "CLG_log.h"
26
27 #include "BLI_utildefines.h"
28 #include "BLI_sys_types.h"
29 #include "BLI_listbase.h"
30 #include "BLI_string.h"
31
32 #include "DNA_listBase.h"
33 #include "DNA_windowmanager_types.h"
34
35 #include "BKE_context.h"
36 #include "BKE_global.h"
37 #include "BKE_library_override.h"
38 #include "BKE_main.h"
39 #include "BKE_undo_system.h"
40
41 #include "MEM_guardedalloc.h"
42
43 #define undo_stack _wm_undo_stack_disallow  /* pass in as a variable always. */
44
45 /** Odd requirement of Blender that we always keep a memfile undo in the stack. */
46 #define WITH_GLOBAL_UNDO_KEEP_ONE
47
48 /** Make sure all ID's created at the point we add an undo step that uses ID's. */
49 #define WITH_GLOBAL_UNDO_ENSURE_UPDATED
50
51 /** Make sure we don't apply edits ontop of a newer memfile state, see: T56163.
52  * \note Keep an eye on this, could solve differently. */
53 #define WITH_GLOBAL_UNDO_CORRECT_ORDER
54
55 /** We only need this locally. */
56 static CLG_LogRef LOG = {"bke.undosys"};
57
58 /* -------------------------------------------------------------------- */
59 /** \name Internal Nested Undo Checks
60  *
61  * Make sure we're not running undo operations from 'step_encode', 'step_decode' callbacks.
62  * bugs caused by this situation aren't _that_ hard to spot but aren't always so obvious.
63  * Best we have a check which shows the problem immediately.
64  *
65  * \{ */
66 #define WITH_NESTED_UNDO_CHECK
67
68 #ifdef WITH_NESTED_UNDO_CHECK
69 static bool g_undo_callback_running = false;
70 #  define UNDO_NESTED_ASSERT(state) BLI_assert(g_undo_callback_running == state)
71 #  define UNDO_NESTED_CHECK_BEGIN { \
72         UNDO_NESTED_ASSERT(false); \
73         g_undo_callback_running = true; \
74 } ((void)0)
75 #  define UNDO_NESTED_CHECK_END { \
76         UNDO_NESTED_ASSERT(true); \
77         g_undo_callback_running = false; \
78 } ((void)0)
79 #else
80 #  define UNDO_NESTED_ASSERT(state) ((void)0)
81 #  define UNDO_NESTED_CHECK_BEGIN ((void)0)
82 #  define UNDO_NESTED_CHECK_END   ((void)0)
83 #endif
84 /** \} */
85
86 /* -------------------------------------------------------------------- */
87 /** \name Public Undo Types
88  *
89  * Unfortunately we need this for a handful of places.
90  */
91 const UndoType *BKE_UNDOSYS_TYPE_IMAGE = NULL;
92 const UndoType *BKE_UNDOSYS_TYPE_MEMFILE = NULL;
93 const UndoType *BKE_UNDOSYS_TYPE_PAINTCURVE = NULL;
94 const UndoType *BKE_UNDOSYS_TYPE_PARTICLE = NULL;
95 const UndoType *BKE_UNDOSYS_TYPE_SCULPT = NULL;
96 const UndoType *BKE_UNDOSYS_TYPE_TEXT = NULL;
97 /** \} */
98
99 /* UndoType */
100
101 static ListBase g_undo_types = {NULL, NULL};
102
103 static const UndoType *BKE_undosys_type_from_context(bContext *C)
104 {
105         for (const UndoType *ut = g_undo_types.first; ut; ut = ut->next) {
106                 /* No poll means we don't check context. */
107                 if (ut->poll && ut->poll(C)) {
108                         return ut;
109                 }
110         }
111         return NULL;
112 }
113
114 /* -------------------------------------------------------------------- */
115 /** \name Internal Callback Wrappers
116  *
117  * #UndoRefID is simply a way to avoid inlining name copy and lookups,
118  * since it's easy to forget a single case when done inline (crashing in some cases).
119  *
120  * \{ */
121
122 static void undosys_id_ref_store(void *UNUSED(user_data), UndoRefID *id_ref)
123 {
124         BLI_assert(id_ref->name[0] == '\0');
125         if (id_ref->ptr) {
126                 BLI_strncpy(id_ref->name, id_ref->ptr->name, sizeof(id_ref->name));
127                 /* Not needed, just prevents stale data access. */
128                 id_ref->ptr = NULL;
129         }
130 }
131
132 static void undosys_id_ref_resolve(void *user_data, UndoRefID *id_ref)
133 {
134         /* Note: we could optimize this, for now it's not too bad since it only runs when we access undo! */
135         Main *bmain = user_data;
136         ListBase *lb = which_libbase(bmain, GS(id_ref->name));
137         for (ID *id = lb->first; id; id = id->next) {
138                 if (STREQ(id_ref->name, id->name) && (id->lib == NULL)) {
139                         id_ref->ptr = id;
140                         break;
141                 }
142         }
143 }
144
145 static bool undosys_step_encode(bContext *C, Main *bmain, UndoStack *ustack, UndoStep *us)
146 {
147         CLOG_INFO(&LOG, 2, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
148         UNDO_NESTED_CHECK_BEGIN;
149         bool ok = us->type->step_encode(C, bmain, us);
150         UNDO_NESTED_CHECK_END;
151         if (ok) {
152                 if (us->type->step_foreach_ID_ref != NULL) {
153                         /* Don't use from context yet because sometimes context is fake and not all members are filled in. */
154                         us->type->step_foreach_ID_ref(us, undosys_id_ref_store, bmain);
155                 }
156 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
157                 if (us->type == BKE_UNDOSYS_TYPE_MEMFILE) {
158                         ustack->step_active_memfile = us;
159                 }
160 #endif
161         }
162         if (ok == false) {
163                 CLOG_INFO(&LOG, 2, "encode callback didn't create undo step");
164         }
165         return ok;
166 }
167
168 static void undosys_step_decode(bContext *C, Main *bmain, UndoStack *ustack, UndoStep *us, int dir)
169 {
170         CLOG_INFO(&LOG, 2, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
171
172         if (us->type->step_foreach_ID_ref) {
173 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
174                 if (us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
175                         for (UndoStep *us_iter = us->prev; us_iter; us_iter = us_iter->prev) {
176                                 if (us_iter->type == BKE_UNDOSYS_TYPE_MEMFILE) {
177                                         if (us_iter == ustack->step_active_memfile) {
178                                                 /* Common case, we're already using the last memfile state. */
179                                         }
180                                         else {
181                                                 /* Load the previous memfile state so any ID's referenced in this
182                                                  * undo step will be correctly resolved, see: T56163. */
183                                                 undosys_step_decode(C, bmain, ustack, us_iter, dir);
184                                                 /* May have been freed on memfile read. */
185                                                 bmain = G.main;
186                                         }
187                                         break;
188                                 }
189                         }
190                 }
191 #endif
192                 /* Don't use from context yet because sometimes context is fake and not all members are filled in. */
193                 us->type->step_foreach_ID_ref(us, undosys_id_ref_resolve, bmain);
194         }
195
196         UNDO_NESTED_CHECK_BEGIN;
197         us->type->step_decode(C, bmain, us, dir);
198         UNDO_NESTED_CHECK_END;
199
200 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
201         if (us->type == BKE_UNDOSYS_TYPE_MEMFILE) {
202                 ustack->step_active_memfile = us;
203         }
204 #endif
205 }
206
207 static void undosys_step_free_and_unlink(UndoStack *ustack, UndoStep *us)
208 {
209         CLOG_INFO(&LOG, 2, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
210         UNDO_NESTED_CHECK_BEGIN;
211         us->type->step_free(us);
212         UNDO_NESTED_CHECK_END;
213
214         BLI_remlink(&ustack->steps, us);
215         MEM_freeN(us);
216
217 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
218         if (ustack->step_active_memfile == us) {
219                 ustack->step_active_memfile = NULL;
220         }
221 #endif
222 }
223
224 /** \} */
225
226 /* -------------------------------------------------------------------- */
227 /** \name Undo Stack
228  * \{ */
229
230 #ifndef NDEBUG
231 static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
232 {
233         if (ustack->step_active != NULL) {
234                 BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
235                 BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
236         }
237         if (expect_non_empty) {
238                 BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
239         }
240 }
241 #else
242 static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
243 {
244         UNUSED_VARS(ustack, expect_non_empty);
245 }
246 #endif
247
248 UndoStack *BKE_undosys_stack_create(void)
249 {
250         UndoStack *ustack = MEM_callocN(sizeof(UndoStack), __func__);
251         return ustack;
252 }
253
254 void BKE_undosys_stack_destroy(UndoStack *ustack)
255 {
256         BKE_undosys_stack_clear(ustack);
257         MEM_freeN(ustack);
258 }
259
260 void BKE_undosys_stack_clear(UndoStack *ustack)
261 {
262         UNDO_NESTED_ASSERT(false);
263         CLOG_INFO(&LOG, 1, "steps=%d", BLI_listbase_count(&ustack->steps));
264         for (UndoStep *us = ustack->steps.last, *us_prev; us; us = us_prev) {
265                 us_prev = us->prev;
266                 undosys_step_free_and_unlink(ustack, us);
267         }
268         BLI_listbase_clear(&ustack->steps);
269         ustack->step_active = NULL;
270 }
271
272 void BKE_undosys_stack_clear_active(UndoStack *ustack)
273 {
274         /* Remove active and all following undos. */
275         UndoStep *us = ustack->step_active;
276
277         if (us) {
278                 ustack->step_active = us->prev;
279                 bool is_not_empty = ustack->step_active != NULL;
280
281                 while (ustack->steps.last != ustack->step_active) {
282                         UndoStep *us_iter = ustack->steps.last;
283                         undosys_step_free_and_unlink(ustack, us_iter);
284                         undosys_stack_validate(ustack, is_not_empty);
285                 }
286         }
287 }
288
289 /* Caller is responsible for handling active. */
290 static void undosys_stack_clear_all_last(UndoStack *ustack, UndoStep *us)
291 {
292         if (us) {
293                 bool is_not_empty = true;
294                 UndoStep *us_iter;
295                 do {
296                         us_iter = ustack->steps.last;
297                         BLI_assert(us_iter != ustack->step_active);
298                         undosys_step_free_and_unlink(ustack, us_iter);
299                         undosys_stack_validate(ustack, is_not_empty);
300                 } while ((us != us_iter));
301         }
302 }
303
304 static void undosys_stack_clear_all_first(UndoStack *ustack, UndoStep *us)
305 {
306         if (us) {
307                 bool is_not_empty = true;
308                 UndoStep *us_iter;
309                 do {
310                         us_iter = ustack->steps.first;
311                         BLI_assert(us_iter != ustack->step_active);
312                         undosys_step_free_and_unlink(ustack, us_iter);
313                         undosys_stack_validate(ustack, is_not_empty);
314                 } while ((us != us_iter));
315         }
316 }
317
318 static bool undosys_stack_push_main(UndoStack *ustack, const char *name, struct Main *bmain)
319 {
320         UNDO_NESTED_ASSERT(false);
321         BLI_assert(ustack->step_init == NULL);
322         CLOG_INFO(&LOG, 1, "'%s'", name);
323         bContext *C_temp = CTX_create();
324         CTX_data_main_set(C_temp, bmain);
325         bool ok = BKE_undosys_step_push_with_type(ustack, C_temp, name, BKE_UNDOSYS_TYPE_MEMFILE);
326         CTX_free(C_temp);
327         return ok;
328 }
329
330 void BKE_undosys_stack_init_from_main(UndoStack *ustack, struct Main *bmain)
331 {
332         UNDO_NESTED_ASSERT(false);
333         undosys_stack_push_main(ustack, "original", bmain);
334 }
335
336 /* called after 'BKE_undosys_stack_init_from_main' */
337 void BKE_undosys_stack_init_from_context(UndoStack *ustack, bContext *C)
338 {
339         const UndoType *ut = BKE_undosys_type_from_context(C);
340         if ((ut != NULL) && (ut != BKE_UNDOSYS_TYPE_MEMFILE)) {
341                 BKE_undosys_step_push_with_type(ustack, C, "original mode", ut);
342         }
343 }
344
345 /* name optional */
346 bool BKE_undosys_stack_has_undo(UndoStack *ustack, const char *name)
347 {
348         if (name) {
349                 UndoStep *us = BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
350                 return us && us->prev;
351         }
352
353         return !BLI_listbase_is_empty(&ustack->steps);
354 }
355
356 UndoStep *BKE_undosys_stack_active_with_type(UndoStack *ustack, const UndoType *ut)
357 {
358         UndoStep *us = ustack->step_active;
359         while (us && (us->type != ut)) {
360                 us = us->prev;
361         }
362         return us;
363 }
364
365 UndoStep *BKE_undosys_stack_init_or_active_with_type(UndoStack *ustack, const UndoType *ut)
366 {
367         UNDO_NESTED_ASSERT(false);
368         CLOG_INFO(&LOG, 1, "type='%s'", ut->name);
369         if (ustack->step_init && (ustack->step_init->type == ut)) {
370                 return ustack->step_init;
371         }
372         return BKE_undosys_stack_active_with_type(ustack, ut);
373 }
374
375 /**
376  * \param steps: Limit the number of undo steps.
377  * \param memory_limit: Limit the amount of memory used by the undo stack.
378  */
379 void BKE_undosys_stack_limit_steps_and_memory(UndoStack *ustack, int steps, size_t memory_limit)
380 {
381         UNDO_NESTED_ASSERT(false);
382         if (!(steps || memory_limit)) {
383                 return;
384         }
385
386         CLOG_INFO(&LOG, 1, "steps=%d, memory_limit=%zu", steps, memory_limit);
387         UndoStep *us;
388 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
389         UndoStep *us_exclude = NULL;
390 #endif
391         /* keep at least two (original + other) */
392         size_t data_size_all = 0;
393         size_t us_count = 0;
394         for (us = ustack->steps.last; us && us->prev; us = us->prev) {
395                 if (memory_limit) {
396                         data_size_all += us->data_size;
397                         if (data_size_all > memory_limit) {
398                                 break;
399                         }
400                 }
401                 if (steps) {
402                         if (us_count == steps) {
403                                 break;
404                         }
405                         if (us->skip == false) {
406                                 us_count += 1;
407                         }
408                 }
409         }
410
411         if (us) {
412                 if (us->prev && us->prev->prev) {
413                         us = us->prev;
414                 }
415
416 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
417                 /* Hack, we need to keep at least one BKE_UNDOSYS_TYPE_MEMFILE. */
418                 if (us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
419                         us_exclude = us->prev;
420                         while (us_exclude && us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
421                                 us_exclude = us_exclude->prev;
422                         }
423                         if (us_exclude) {
424                                 BLI_remlink(&ustack->steps, us_exclude);
425                         }
426                 }
427 #endif
428                 /* Free from first to last, free functions may update de-duplication info (see #MemFileUndoStep). */
429                 undosys_stack_clear_all_first(ustack, us->prev);
430
431 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
432                 if (us_exclude) {
433                         BLI_addhead(&ustack->steps, us_exclude);
434                 }
435 #endif
436         }
437 }
438
439 /** \} */
440
441 UndoStep *BKE_undosys_step_push_init_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
442 {
443         UNDO_NESTED_ASSERT(false);
444         /* We could detect and clean this up (but it should never happen!). */
445         BLI_assert(ustack->step_init == NULL);
446         if (ut->step_encode_init) {
447                 undosys_stack_validate(ustack, false);
448
449                 if (ustack->step_active) {
450                         undosys_stack_clear_all_last(ustack, ustack->step_active->next);
451                 }
452
453                 UndoStep *us = MEM_callocN(ut->step_size, __func__);
454                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, name, ut->name);
455                 if (name != NULL) {
456                         BLI_strncpy(us->name, name, sizeof(us->name));
457                 }
458                 us->type = ut;
459                 ustack->step_init = us;
460                 ut->step_encode_init(C, us);
461                 undosys_stack_validate(ustack, false);
462                 return us;
463         }
464         else {
465                 return NULL;
466         }
467 }
468
469 UndoStep *BKE_undosys_step_push_init(UndoStack *ustack, bContext *C, const char *name)
470 {
471         UNDO_NESTED_ASSERT(false);
472         /* We could detect and clean this up (but it should never happen!). */
473         BLI_assert(ustack->step_init == NULL);
474         const UndoType *ut = BKE_undosys_type_from_context(C);
475         if (ut == NULL) {
476                 return NULL;
477         }
478         return BKE_undosys_step_push_init_with_type(ustack, C, name, ut);
479 }
480
481 /**
482  * \param C: Can be NULL from some callers if their encoding function doesn't need it
483  */
484 bool BKE_undosys_step_push_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
485 {
486         UNDO_NESTED_ASSERT(false);
487         undosys_stack_validate(ustack, false);
488         bool is_not_empty = ustack->step_active != NULL;
489
490         /* Might not be final place for this to be called - probably only want to call it from some
491          * undo handlers, not all of them? */
492         if (BKE_override_static_is_enabled()) {
493                 BKE_main_override_static_operations_create(G.main, false);
494         }
495
496         /* Remove all undos after (also when 'ustack->step_active == NULL'). */
497         while (ustack->steps.last != ustack->step_active) {
498                 UndoStep *us_iter = ustack->steps.last;
499                 undosys_step_free_and_unlink(ustack, us_iter);
500                 undosys_stack_validate(ustack, is_not_empty);
501         }
502
503         if (ustack->step_active) {
504                 BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
505         }
506
507 #ifdef WITH_GLOBAL_UNDO_ENSURE_UPDATED
508         if (ut->step_foreach_ID_ref != NULL) {
509                 if (G_MAIN->is_memfile_undo_written == false) {
510                         const char *name_internal = "MemFile Internal (pre)";
511                         /* Don't let 'step_init' cause issues when adding memfile undo step. */
512                         void *step_init = ustack->step_init;
513                         ustack->step_init = NULL;
514                         const bool ok = undosys_stack_push_main(ustack, name_internal, G_MAIN);
515                         /* Restore 'step_init'. */
516                         ustack->step_init = step_init;
517                         if (ok) {
518                                 UndoStep *us = ustack->steps.last;
519                                 BLI_assert(STREQ(us->name, name_internal));
520                                 us->skip = true;
521 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
522                                 ustack->step_active_memfile = us;
523 #endif
524                         }
525                 }
526         }
527 #endif
528
529         bool use_memfile_step = false;
530         {
531                 UndoStep *us = ustack->step_init ? ustack->step_init : MEM_callocN(ut->step_size, __func__);
532                 ustack->step_init = NULL;
533                 if (us->name[0] == '\0') {
534                         BLI_strncpy(us->name, name, sizeof(us->name));
535                 }
536                 us->type = ut;
537                 /* initialized, not added yet. */
538
539                 if (!undosys_step_encode(C, G_MAIN, ustack, us)) {
540                         MEM_freeN(us);
541                         undosys_stack_validate(ustack, true);
542                         return false;
543                 }
544                 ustack->step_active = us;
545                 BLI_addtail(&ustack->steps, us);
546                 use_memfile_step = us->use_memfile_step;
547         }
548
549         if (use_memfile_step) {
550                 const char *name_internal = "MemFile Internal (post)";
551                 const bool ok = undosys_stack_push_main(ustack, name_internal, G_MAIN);
552                 if (ok) {
553                         UndoStep *us = ustack->steps.last;
554                         BLI_assert(STREQ(us->name, name_internal));
555                         us->skip = true;
556 #ifdef WITH_GLOBAL_UNDO_CORRECT_ORDER
557                         ustack->step_active_memfile = us;
558 #endif
559                         ustack->step_active = us;
560                 }
561         }
562
563         undosys_stack_validate(ustack, true);
564         return true;
565 }
566
567 bool BKE_undosys_step_push(UndoStack *ustack, bContext *C, const char *name)
568 {
569         UNDO_NESTED_ASSERT(false);
570         const UndoType *ut = ustack->step_init ? ustack->step_init->type : BKE_undosys_type_from_context(C);
571         if (ut == NULL) {
572                 return false;
573         }
574         return BKE_undosys_step_push_with_type(ustack, C, name, ut);
575 }
576
577
578 /**
579  * Useful when we want to diff against previous undo data but can't be sure the types match.
580  */
581 UndoStep *BKE_undosys_step_same_type_next(UndoStep *us)
582 {
583         if (us) {
584                 const UndoType *ut = us->type;
585                 while ((us = us->next)) {
586                         if (us->type == ut) {
587                                 return us;
588                         }
589                 }
590
591         }
592         return us;
593 }
594
595 /**
596  * Useful when we want to diff against previous undo data but can't be sure the types match.
597  */
598 UndoStep *BKE_undosys_step_same_type_prev(UndoStep *us)
599 {
600         if (us) {
601                 const UndoType *ut = us->type;
602                 while ((us = us->prev)) {
603                         if (us->type == ut) {
604                                 return us;
605                         }
606                 }
607
608         }
609         return us;
610 }
611
612 UndoStep *BKE_undosys_step_find_by_name_with_type(UndoStack *ustack, const char *name, const UndoType *ut)
613 {
614         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
615                 if (us->type == ut) {
616                         if (STREQ(name, us->name)) {
617                                 return us;
618                         }
619                 }
620         }
621         return NULL;
622 }
623
624 UndoStep *BKE_undosys_step_find_by_name(UndoStack *ustack, const char *name)
625 {
626         return BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
627 }
628
629 UndoStep *BKE_undosys_step_find_by_type(UndoStack *ustack, const UndoType *ut)
630 {
631         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
632                 if (us->type == ut) {
633                         return us;
634                 }
635         }
636         return NULL;
637 }
638
639 bool BKE_undosys_step_undo_with_data_ex(
640         UndoStack *ustack, bContext *C, UndoStep *us,
641         bool use_skip)
642 {
643         UNDO_NESTED_ASSERT(false);
644         if (us) {
645                 undosys_stack_validate(ustack, true);
646         }
647         UndoStep *us_prev = us ? us->prev : NULL;
648         if (us) {
649                 /* The current state is a copy, we need to load the previous state. */
650                 us = us_prev;
651         }
652
653         if (us != NULL) {
654                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
655
656                 /* Handle accumulate steps. */
657                 if (ustack->step_active) {
658                         UndoStep *us_iter = ustack->step_active;
659                         while (us_iter != us) {
660                                 /* TODO:
661                                  * - skip successive steps that store the same data, eg: memfile steps.
662                                  * - or steps that include another steps data, eg: a memfile step includes text undo data.
663                                  */
664                                 undosys_step_decode(C, G_MAIN, ustack, us_iter, -1);
665                                 us_iter = us_iter->prev;
666                         }
667                 }
668
669                 undosys_step_decode(C, G_MAIN, ustack, us, -1);
670
671                 ustack->step_active = us_prev;
672                 undosys_stack_validate(ustack, true);
673                 if (use_skip) {
674                         if (ustack->step_active && ustack->step_active->skip) {
675                                 CLOG_INFO(&LOG, 2, "undo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
676                                 BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
677                         }
678                 }
679                 return true;
680         }
681         return false;
682 }
683 bool BKE_undosys_step_undo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
684 {
685         return BKE_undosys_step_undo_with_data_ex(ustack, C, us, true);
686 }
687
688 bool BKE_undosys_step_undo(UndoStack *ustack, bContext *C)
689 {
690         return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
691 }
692
693 void BKE_undosys_step_undo_from_index(UndoStack *ustack, bContext *C, int index)
694 {
695         UndoStep *us = BLI_findlink(&ustack->steps, index);
696         BLI_assert(us->skip == false);
697         BKE_undosys_step_load_data(ustack, C, us);
698 }
699
700 bool BKE_undosys_step_redo_with_data_ex(
701         UndoStack *ustack, bContext *C, UndoStep *us,
702         bool use_skip)
703 {
704         UNDO_NESTED_ASSERT(false);
705         UndoStep *us_next = us ? us->next : NULL;
706         /* Unlike undo accumulate, we always use the next. */
707         us = us_next;
708
709         if (us != NULL) {
710                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
711
712                 /* Handle accumulate steps. */
713                 if (ustack->step_active && ustack->step_active->next) {
714                         UndoStep *us_iter = ustack->step_active->next;
715                         while (us_iter != us) {
716                                 undosys_step_decode(C, G_MAIN, ustack, us_iter, 1);
717                                 us_iter = us_iter->next;
718                         }
719                 }
720
721                 undosys_step_decode(C, G_MAIN, ustack, us, 1);
722                 ustack->step_active = us_next;
723                 if (use_skip) {
724                         if (ustack->step_active && ustack->step_active->skip) {
725                                 CLOG_INFO(&LOG, 2, "redo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
726                                 BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
727                         }
728                 }
729                 return true;
730         }
731         return false;
732 }
733 bool BKE_undosys_step_redo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
734 {
735         return BKE_undosys_step_redo_with_data_ex(ustack, C, us, true);
736 }
737
738 bool BKE_undosys_step_redo(UndoStack *ustack, bContext *C)
739 {
740         return BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
741 }
742
743 bool BKE_undosys_step_load_data(UndoStack *ustack, bContext *C, UndoStep *us)
744 {
745         UNDO_NESTED_ASSERT(false);
746         const int index_active = BLI_findindex(&ustack->steps, ustack->step_active);
747         const int index_target = BLI_findindex(&ustack->steps, us);
748         BLI_assert(!ELEM(-1, index_active, index_target));
749         bool ok = true;
750
751         if (index_target < index_active) {
752                 uint i = index_active - index_target;
753                 while (i-- && ok) {
754                         ok = BKE_undosys_step_undo_with_data_ex(ustack, C, ustack->step_active, false);
755                 }
756         }
757         else if (index_target > index_active) {
758                 uint i = index_target - index_active;
759                 while (i-- && ok) {
760                         ok = BKE_undosys_step_redo_with_data_ex(ustack, C, ustack->step_active, false);
761                 }
762         }
763
764         if (ok) {
765                 BLI_assert(ustack->step_active == us);
766         }
767
768         return ok;
769 }
770
771 bool BKE_undosys_step_undo_compat_only(UndoStack *ustack, bContext *C, int step)
772 {
773         if (step == 0) {
774                 return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
775         }
776         else if (step == 1) {
777                 return BKE_undosys_step_undo(ustack, C);
778         }
779         else {
780                 return BKE_undosys_step_redo(ustack, C);
781         }
782 }
783 /**
784  * Similar to #WM_operatortype_append
785  */
786 UndoType *BKE_undosys_type_append(void (*undosys_fn)(UndoType *))
787 {
788         UndoType *ut;
789
790         ut = MEM_callocN(sizeof(UndoType), __func__);
791
792         undosys_fn(ut);
793
794         BLI_addtail(&g_undo_types, ut);
795
796         return ut;
797 }
798
799 void BKE_undosys_type_free_all(void)
800 {
801         UndoType *ut;
802         while ((ut = BLI_pophead(&g_undo_types))) {
803                 MEM_freeN(ut);
804         }
805 }
806
807 /** \} */
808
809 /* -------------------------------------------------------------------- */
810 /** \name ID Reference Utilities
811  *
812  * Unfortunately we need this for a handful of places.
813  */
814
815 /* Disable for now since it accesses freed memory.
816  * The pointer can only be a key, we can't read it's contents. */
817 #define USE_LIB_SKIP
818
819 static void UNUSED_FUNCTION(BKE_undosys_foreach_ID_ref(
820         UndoStack *ustack, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data))
821 {
822         for (UndoStep *us = ustack->steps.first; us; us = us->next) {
823                 const UndoType *ut = us->type;
824                 if (ut->step_foreach_ID_ref != NULL) {
825                         ut->step_foreach_ID_ref(us, foreach_ID_ref_fn, user_data);
826                 }
827         }
828 }
829
830 typedef struct UndoIDPtrMapItem {
831         /** Never changes (matches undo data). Use as sort key for binary search. */
832         const void *ptr;
833         /** Write the new pointers here. */
834         uint index;
835 } UndoIDPtrMapItem;
836
837 typedef struct UndoIDPtrMap {
838         UndoRefID *refs;
839         /**
840          * Pointer map, update 'dst' members before use.
841          * This is always sorted (adds some overhead when adding, in practice it's acceptable since).
842          */
843         UndoIDPtrMapItem *pmap;
844
845         /** Length for both 'refs' & 'pmap' */
846         uint len;
847         uint len_alloc;
848 } UndoIDPtrMap;
849
850 #ifdef DEBUG
851 #  define PMAP_DEFAULT_ALLOC 1
852 #else
853 #  define PMAP_DEFAULT_ALLOC 32
854 #endif
855
856 void BKE_undosys_ID_map_foreach_ID_ref(
857         UndoIDPtrMap *map,
858         UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
859 {
860         for (uint i = 0; i < map->len; i++) {
861                 foreach_ID_ref_fn(user_data, &map->refs[i]);
862         }
863 }
864
865 /**
866  * Return true when found, otherwise index is set to the index we should insert.
867  */
868 static bool undosys_ID_map_lookup_index(const UndoIDPtrMap *map, const void *key, uint *r_index)
869 {
870         const UndoIDPtrMapItem *pmap = map->pmap;
871         const uint len = map->len;
872         if (len == 0) {
873                 if (*r_index) {
874                         *r_index = 0;
875                 }
876                 return false;
877         }
878         int min = 0, max = len - 1;
879         while (min <= max) {
880                 const uint mid = (min + max) / 2;
881                 if (pmap[mid].ptr < key) {
882                         min = mid + 1;
883                 }
884                 else if (pmap[mid].ptr == key) {
885                         if (r_index) {
886                                 *r_index = mid;
887                         }
888                         return true;
889                 }
890                 else if (pmap[mid].ptr > key) {
891                         max = mid - 1;
892                 }
893         }
894         if (r_index) {
895                 *r_index = min;
896         }
897         return false;
898 }
899
900 /**
901  * A set of ID's use for efficient decoding, so we can map pointers back to the newly loaded data
902  * without performing full look ups each time.
903  *
904  * This can be used as an old_pointer -> new_pointer lookup.
905  */
906 UndoIDPtrMap *BKE_undosys_ID_map_create(void)
907 {
908         UndoIDPtrMap *map = MEM_mallocN(sizeof(*map), __func__);
909         map->len_alloc = PMAP_DEFAULT_ALLOC;
910         map->refs = MEM_mallocN(sizeof(*map->refs) * map->len_alloc, __func__);
911         map->pmap = MEM_mallocN(sizeof(*map->pmap) * map->len_alloc, __func__);
912         map->len = 0;
913         return map;
914 }
915 void BKE_undosys_ID_map_destroy(UndoIDPtrMap *idpmap)
916 {
917         MEM_SAFE_FREE(idpmap->refs);
918         MEM_SAFE_FREE(idpmap->pmap);
919         MEM_freeN(idpmap);
920 }
921
922 void BKE_undosys_ID_map_add(UndoIDPtrMap *map, ID *id)
923 {
924         uint index;
925 #ifdef USE_LIB_SKIP
926         if (id->lib != NULL) {
927                 return;
928         }
929 #endif
930
931         if (undosys_ID_map_lookup_index(map, id, &index)) {
932                 return;  /* exists. */
933         }
934
935         const uint len_src = map->len;
936         const uint len_dst = map->len + 1;
937         if (len_dst > map->len_alloc) {
938                 map->len_alloc *= 2;
939                 BLI_assert(map->len_alloc >= len_dst);
940                 map->pmap = MEM_reallocN(map->pmap, sizeof(*map->pmap) * map->len_alloc);
941                 map->refs = MEM_reallocN(map->refs, sizeof(*map->refs) * map->len_alloc);
942         }
943
944 #if 0  /* Will be done automatically in callback. */
945         BLI_strncpy(map->refs[len_src].name, id->name, sizeof(id->name));
946 #else
947         map->refs[len_src].name[0] = '\0';
948 #endif
949         map->refs[len_src].ptr = id;
950
951         if (len_src != 0 && index != len_src) {
952                 memmove(&map->pmap[index + 1], &map->pmap[index], sizeof(*map->pmap) * (len_src - index));
953         }
954         map->pmap[index].ptr = id;
955         map->pmap[index].index = len_src;
956
957         map->len = len_dst;
958 }
959
960 ID *BKE_undosys_ID_map_lookup(const UndoIDPtrMap *map, const ID *id_src)
961 {
962         /* We should only ever lookup indices which exist! */
963         uint index;
964         if (!undosys_ID_map_lookup_index(map, id_src, &index)) {
965                 BLI_assert(0);
966         }
967         index = map->pmap[index].index;
968         ID *id_dst = map->refs[index].ptr;
969         BLI_assert(id_dst != NULL);
970         BLI_assert(STREQ(id_dst->name, map->refs[index].name));
971         return id_dst;
972 }
973
974 void BKE_undosys_ID_map_add_with_prev(UndoIDPtrMap *map, ID *id, ID **id_prev)
975 {
976         if (id == *id_prev) {
977                 return;
978         }
979         *id_prev = id;
980         BKE_undosys_ID_map_add(map, id);
981 }
982
983 ID *BKE_undosys_ID_map_lookup_with_prev(const UndoIDPtrMap *map, ID *id_src, ID *id_prev_match[2])
984 {
985         if (id_src == id_prev_match[0]) {
986                 return id_prev_match[1];
987         }
988         else {
989 #ifdef USE_LIB_SKIP
990                 ID *id_dst = BKE_undosys_ID_map_lookup(map, id_src);
991 #else
992                 ID *id_dst = (id_src->lib == NULL) ? BKE_undosys_ID_map_lookup(map, id_src) : id_src;
993 #endif
994                 id_prev_match[0] = id_src;
995                 id_prev_match[1] = id_dst;
996                 return id_dst;
997         }
998 }
999
1000 /** \} */
1001
1002
1003 /* -------------------------------------------------------------------- */
1004 /** \name Debug Helpers
1005  * \{ */
1006
1007 void BKE_undosys_print(UndoStack *ustack)
1008 {
1009         printf("Undo %d Steps (*: active, #=applied, M=memfile-active, S=skip)\n",
1010                BLI_listbase_count(&ustack->steps));
1011         int index = 0;
1012         for (UndoStep *us = ustack->steps.first; us; us = us->next) {
1013                 printf("[%c%c%c%c] %3d type='%s', name='%s'\n",
1014                        (us == ustack->step_active) ? '*' : ' ',
1015                        us->is_applied ? '#' : ' ',
1016                        (us == ustack->step_active_memfile) ? 'M' : ' ',
1017                        us->skip ? 'S' : ' ',
1018                        index,
1019                        us->type->name,
1020                        us->name);
1021                 index++;
1022         }
1023 }
1024
1025 /** \} */