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