25eaf4cb7ab37882bfd6b321b97a5cf26ee109d0
[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 /** 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, 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, 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                         Main *bmain = G.main;
155                         us->type->step_foreach_ID_ref(us, undosys_id_ref_store, bmain);
156                 }
157         }
158         if (ok == false) {
159                 CLOG_INFO(&LOG, 2, "encode callback didn't create undo step");
160         }
161         return ok;
162 }
163
164 static void undosys_step_decode(bContext *C, UndoStep *us, int dir)
165 {
166         CLOG_INFO(&LOG, 2, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
167         if (us->type->step_foreach_ID_ref) {
168                 /* Don't use from context yet because sometimes context is fake and not all members are filled in. */
169                 Main *bmain = G.main;
170                 us->type->step_foreach_ID_ref(us, undosys_id_ref_resolve, bmain);
171         }
172
173         UNDO_NESTED_CHECK_BEGIN;
174         us->type->step_decode(C, us, dir);
175         UNDO_NESTED_CHECK_END;
176 }
177
178 static void undosys_step_free_and_unlink(UndoStack *ustack, UndoStep *us)
179 {
180         CLOG_INFO(&LOG, 2, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
181         UNDO_NESTED_CHECK_BEGIN;
182         us->type->step_free(us);
183         UNDO_NESTED_CHECK_END;
184
185         BLI_remlink(&ustack->steps, us);
186         MEM_freeN(us);
187 }
188
189 /** \} */
190
191 /* -------------------------------------------------------------------- */
192 /** \name Undo Stack
193  * \{ */
194
195 #ifndef NDEBUG
196 static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
197 {
198         if (ustack->step_active != NULL) {
199                 BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
200                 BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
201         }
202         if (expect_non_empty) {
203                 BLI_assert(!BLI_listbase_is_empty(&ustack->steps));
204         }
205 }
206 #else
207 static void undosys_stack_validate(UndoStack *ustack, bool expect_non_empty)
208 {
209         UNUSED_VARS(ustack, expect_non_empty);
210 }
211 #endif
212
213 UndoStack *BKE_undosys_stack_create(void)
214 {
215         UndoStack *ustack = MEM_callocN(sizeof(UndoStack), __func__);
216         return ustack;
217 }
218
219 void BKE_undosys_stack_destroy(UndoStack *ustack)
220 {
221         BKE_undosys_stack_clear(ustack);
222         MEM_freeN(ustack);
223 }
224
225 void BKE_undosys_stack_clear(UndoStack *ustack)
226 {
227         UNDO_NESTED_ASSERT(false);
228         CLOG_INFO(&LOG, 1, "steps=%d", BLI_listbase_count(&ustack->steps));
229         for (UndoStep *us = ustack->steps.last, *us_prev; us; us = us_prev) {
230                 us_prev = us->prev;
231                 undosys_step_free_and_unlink(ustack, us);
232         }
233         BLI_listbase_clear(&ustack->steps);
234         ustack->step_active = NULL;
235 }
236
237 void BKE_undosys_stack_clear_active(UndoStack *ustack)
238 {
239         /* Remove active and all following undos. */
240         UndoStep *us = ustack->step_active;
241
242         if (us) {
243                 ustack->step_active = us->prev;
244                 bool is_not_empty = ustack->step_active != NULL;
245
246                 while (ustack->steps.last != ustack->step_active) {
247                         UndoStep *us_iter = ustack->steps.last;
248                         undosys_step_free_and_unlink(ustack, us_iter);
249                         undosys_stack_validate(ustack, is_not_empty);
250                 }
251         }
252 }
253
254 /* Caller is responsible for handling active. */
255 static void undosys_stack_clear_all_last(UndoStack *ustack, UndoStep *us)
256 {
257         if (us) {
258                 bool is_not_empty = true;
259                 UndoStep *us_iter;
260                 do {
261                         us_iter = ustack->steps.last;
262                         BLI_assert(us_iter != ustack->step_active);
263                         undosys_step_free_and_unlink(ustack, us_iter);
264                         undosys_stack_validate(ustack, is_not_empty);
265                 } while ((us != us_iter));
266         }
267 }
268
269 static void undosys_stack_clear_all_first(UndoStack *ustack, UndoStep *us)
270 {
271         if (us) {
272                 bool is_not_empty = true;
273                 UndoStep *us_iter;
274                 do {
275                         us_iter = ustack->steps.first;
276                         BLI_assert(us_iter != ustack->step_active);
277                         undosys_step_free_and_unlink(ustack, us_iter);
278                         undosys_stack_validate(ustack, is_not_empty);
279                 } while ((us != us_iter));
280         }
281 }
282
283 static bool undosys_stack_push_main(UndoStack *ustack, const char *name, struct Main *bmain)
284 {
285         UNDO_NESTED_ASSERT(false);
286         BLI_assert(ustack->step_init == NULL);
287         CLOG_INFO(&LOG, 1, "'%s'", name);
288         bContext *C_temp = CTX_create();
289         CTX_data_main_set(C_temp, bmain);
290         bool ok = BKE_undosys_step_push_with_type(ustack, C_temp, name, BKE_UNDOSYS_TYPE_MEMFILE);
291         CTX_free(C_temp);
292         return ok;
293 }
294
295 void BKE_undosys_stack_init_from_main(UndoStack *ustack, struct Main *bmain)
296 {
297         UNDO_NESTED_ASSERT(false);
298         undosys_stack_push_main(ustack, "original", bmain);
299 }
300
301 /* called after 'BKE_undosys_stack_init_from_main' */
302 void BKE_undosys_stack_init_from_context(UndoStack *ustack, bContext *C)
303 {
304         const UndoType *ut = BKE_undosys_type_from_context(C);
305         if ((ut != NULL) && (ut != BKE_UNDOSYS_TYPE_MEMFILE) && (ut->mode == BKE_UNDOTYPE_MODE_STORE)) {
306                 BKE_undosys_step_push_with_type(ustack, C, "original mode", ut);
307         }
308 }
309
310 /* name optional */
311 bool BKE_undosys_stack_has_undo(UndoStack *ustack, const char *name)
312 {
313         if (name) {
314                 UndoStep *us = BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
315                 return us && us->prev;
316         }
317
318         return !BLI_listbase_is_empty(&ustack->steps);
319 }
320
321 UndoStep *BKE_undosys_stack_active_with_type(UndoStack *ustack, const UndoType *ut)
322 {
323         UndoStep *us = ustack->step_active;
324         while (us && (us->type != ut)) {
325                 us = us->prev;
326         }
327         return us;
328 }
329
330 UndoStep *BKE_undosys_stack_init_or_active_with_type(UndoStack *ustack, const UndoType *ut)
331 {
332         UNDO_NESTED_ASSERT(false);
333         CLOG_INFO(&LOG, 1, "type='%s'", ut->name);
334         if (ustack->step_init && (ustack->step_init->type == ut)) {
335                 return ustack->step_init;
336         }
337         return BKE_undosys_stack_active_with_type(ustack, ut);
338 }
339
340 /**
341  * \param steps: Limit the number of undo steps.
342  * \param memory_limit: Limit the amount of memory used by the undo stack.
343  */
344 void BKE_undosys_stack_limit_steps_and_memory(UndoStack *ustack, int steps, size_t memory_limit)
345 {
346         UNDO_NESTED_ASSERT(false);
347         if (!(steps || memory_limit)) {
348                 return;
349         }
350
351         CLOG_INFO(&LOG, 1, "steps=%d, memory_limit=%zu", steps, memory_limit);
352         UndoStep *us;
353 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
354         UndoStep *us_exclude = NULL;
355 #endif
356         /* keep at least two (original + other) */
357         size_t data_size_all = 0;
358         size_t us_count = 0;
359         for (us = ustack->steps.last; us && us->prev; us = us->prev) {
360                 if (memory_limit) {
361                         data_size_all += us->data_size;
362                         if (data_size_all > memory_limit) {
363                                 break;
364                         }
365                 }
366                 if (steps) {
367                         if (us_count == steps) {
368                                 break;
369                         }
370                         if (us->skip == false) {
371                                 us_count += 1;
372                         }
373                 }
374         }
375
376         if (us) {
377                 if (us->prev && us->prev->prev) {
378                         us = us->prev;
379                 }
380
381 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
382                 /* Hack, we need to keep at least one BKE_UNDOSYS_TYPE_MEMFILE. */
383                 if (us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
384                         us_exclude = us->prev;
385                         while (us_exclude && us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
386                                 us_exclude = us_exclude->prev;
387                         }
388                         if (us_exclude) {
389                                 BLI_remlink(&ustack->steps, us_exclude);
390                         }
391                 }
392 #endif
393                 /* Free from first to last, free functions may update de-duplication info (see #MemFileUndoStep). */
394                 undosys_stack_clear_all_first(ustack, us->prev);
395
396 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
397                 if (us_exclude) {
398                         BLI_addhead(&ustack->steps, us_exclude);
399                 }
400 #endif
401         }
402 }
403
404 /** \} */
405
406 UndoStep *BKE_undosys_step_push_init_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
407 {
408         UNDO_NESTED_ASSERT(false);
409         /* We could detect and clean this up (but it should never happen!). */
410         BLI_assert(ustack->step_init == NULL);
411         if (ut->step_encode_init) {
412                 undosys_stack_validate(ustack, false);
413
414                 if (ustack->step_active) {
415                         undosys_stack_clear_all_last(ustack, ustack->step_active->next);
416                 }
417
418                 UndoStep *us = MEM_callocN(ut->step_size, __func__);
419                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, name, ut->name);
420                 if (name != NULL) {
421                         BLI_strncpy(us->name, name, sizeof(us->name));
422                 }
423                 us->type = ut;
424                 ustack->step_init = us;
425                 ut->step_encode_init(C, us);
426                 undosys_stack_validate(ustack, false);
427                 return us;
428         }
429         else {
430                 return NULL;
431         }
432 }
433
434 UndoStep *BKE_undosys_step_push_init(UndoStack *ustack, bContext *C, const char *name)
435 {
436         UNDO_NESTED_ASSERT(false);
437         /* We could detect and clean this up (but it should never happen!). */
438         BLI_assert(ustack->step_init == NULL);
439         const UndoType *ut = BKE_undosys_type_from_context(C);
440         if (ut == NULL) {
441                 return NULL;
442         }
443         return BKE_undosys_step_push_init_with_type(ustack, C, name, ut);
444 }
445
446 /**
447  * \param C: Can be NULL from some callers if their encoding function doesn't need it
448  */
449 bool BKE_undosys_step_push_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
450 {
451         UNDO_NESTED_ASSERT(false);
452         undosys_stack_validate(ustack, false);
453         bool is_not_empty = ustack->step_active != NULL;
454
455         /* Might not be final place for this to be called - probably only want to call it from some
456          * undo handlers, not all of them? */
457         if (BKE_override_static_is_enabled()) {
458                 BKE_main_override_static_operations_create(G.main, false);
459         }
460
461         /* Remove all undos after (also when 'ustack->step_active == NULL'). */
462         while (ustack->steps.last != ustack->step_active) {
463                 UndoStep *us_iter = ustack->steps.last;
464                 undosys_step_free_and_unlink(ustack, us_iter);
465                 undosys_stack_validate(ustack, is_not_empty);
466         }
467
468         if (ustack->step_active) {
469                 BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
470         }
471
472 #ifdef WITH_GLOBAL_UNDO_ENSURE_UPDATED
473         if (ut->step_foreach_ID_ref != NULL) {
474                 Main *bmain = G.main;
475                 if (bmain->is_memfile_undo_written == false) {
476                         const char *name_internal = "MemFile Internal";
477                         /* Don't let 'step_init' cause issues when adding memfile undo step. */
478                         void *step_init = ustack->step_init;
479                         ustack->step_init = NULL;
480                         const bool ok = undosys_stack_push_main(ustack, name_internal, bmain);
481                         /* Restore 'step_init'. */
482                         ustack->step_init = step_init;
483                         if (ok) {
484                                 UndoStep *us = ustack->steps.last;
485                                 BLI_assert(STREQ(us->name, name_internal));
486                                 us->skip = true;
487                         }
488                 }
489         }
490 #endif
491
492         UndoStep *us = ustack->step_init ? ustack->step_init : MEM_callocN(ut->step_size, __func__);
493         ustack->step_init = NULL;
494         if (us->name[0] == '\0') {
495                 BLI_strncpy(us->name, name, sizeof(us->name));
496         }
497         us->type = ut;
498         /* initialized, not added yet. */
499
500         if (undosys_step_encode(C, us)) {
501                 ustack->step_active = us;
502                 BLI_addtail(&ustack->steps, us);
503                 undosys_stack_validate(ustack, true);
504                 return true;
505         }
506         else {
507                 MEM_freeN(us);
508                 undosys_stack_validate(ustack, true);
509                 return false;
510         }
511 }
512
513 bool BKE_undosys_step_push(UndoStack *ustack, bContext *C, const char *name)
514 {
515         UNDO_NESTED_ASSERT(false);
516         const UndoType *ut = ustack->step_init ? ustack->step_init->type : BKE_undosys_type_from_context(C);
517         if (ut == NULL) {
518                 return false;
519         }
520         return BKE_undosys_step_push_with_type(ustack, C, name, ut);
521 }
522
523
524 /**
525  * Useful when we want to diff against previous undo data but can't be sure the types match.
526  */
527 UndoStep *BKE_undosys_step_same_type_next(UndoStep *us)
528 {
529         if (us) {
530                 const UndoType *ut = us->type;
531                 while ((us = us->next)) {
532                         if (us->type == ut) {
533                                 return us;
534                         }
535                 }
536
537         }
538         return us;
539 }
540
541 /**
542  * Useful when we want to diff against previous undo data but can't be sure the types match.
543  */
544 UndoStep *BKE_undosys_step_same_type_prev(UndoStep *us)
545 {
546         if (us) {
547                 const UndoType *ut = us->type;
548                 while ((us = us->prev)) {
549                         if (us->type == ut) {
550                                 return us;
551                         }
552                 }
553
554         }
555         return us;
556 }
557
558 UndoStep *BKE_undosys_step_find_by_name_with_type(UndoStack *ustack, const char *name, const UndoType *ut)
559 {
560         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
561                 if (us->type == ut) {
562                         if (STREQ(name, us->name)) {
563                                 return us;
564                         }
565                 }
566         }
567         return NULL;
568 }
569
570 UndoStep *BKE_undosys_step_find_by_name(UndoStack *ustack, const char *name)
571 {
572         return BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
573 }
574
575 UndoStep *BKE_undosys_step_find_by_type(UndoStack *ustack, const UndoType *ut)
576 {
577         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
578                 if (us->type == ut) {
579                         return us;
580                 }
581         }
582         return NULL;
583 }
584
585 bool BKE_undosys_step_undo_with_data_ex(
586         UndoStack *ustack, bContext *C, UndoStep *us,
587         bool use_skip)
588 {
589         UNDO_NESTED_ASSERT(false);
590         if (us) {
591                 undosys_stack_validate(ustack, true);
592         }
593         UndoStep *us_prev = us ? us->prev : NULL;
594         if (us) {
595                 /* The current state is a copy, we need to load the previous state. */
596                 us = us_prev;
597         }
598
599         if (us != NULL) {
600                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
601
602                 /* Handle accumulate steps. */
603                 if (ustack->step_active) {
604                         UndoStep *us_iter = ustack->step_active;
605                         while (us_iter != us) {
606                                 if (us_iter->type->mode == BKE_UNDOTYPE_MODE_ACCUMULATE) {
607                                         undosys_step_decode(C, us_iter, -1);
608                                 }
609                                 us_iter = us_iter->prev;
610                         }
611                 }
612
613                 if (us->type->mode != BKE_UNDOTYPE_MODE_ACCUMULATE) {
614                         undosys_step_decode(C, us, -1);
615                 }
616                 ustack->step_active = us_prev;
617                 undosys_stack_validate(ustack, true);
618                 if (use_skip) {
619                         if (ustack->step_active && ustack->step_active->skip) {
620                                 CLOG_INFO(&LOG, 2, "undo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
621                                 BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
622                         }
623                 }
624                 return true;
625         }
626         return false;
627 }
628 bool BKE_undosys_step_undo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
629 {
630         return BKE_undosys_step_undo_with_data_ex(ustack, C, us, true);
631 }
632
633 bool BKE_undosys_step_undo(UndoStack *ustack, bContext *C)
634 {
635         return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
636 }
637
638 void BKE_undosys_step_undo_from_index(UndoStack *ustack, bContext *C, int index)
639 {
640         UndoStep *us = BLI_findlink(&ustack->steps, index);
641         BLI_assert(us->skip == false);
642         BKE_undosys_step_load_data(ustack, C, us);
643 }
644
645 bool BKE_undosys_step_redo_with_data_ex(
646         UndoStack *ustack, bContext *C, UndoStep *us,
647         bool use_skip)
648 {
649         UNDO_NESTED_ASSERT(false);
650         UndoStep *us_next = us ? us->next : NULL;
651         /* Unlike undo accumulate, we always use the next. */
652         us = us_next;
653
654         if (us != NULL) {
655                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
656
657                 /* Handle accumulate steps. */
658                 if (ustack->step_active && ustack->step_active->next) {
659                         UndoStep *us_iter = ustack->step_active->next;
660                         while (us_iter != us) {
661                                 if (us_iter->type->mode == BKE_UNDOTYPE_MODE_ACCUMULATE) {
662                                         undosys_step_decode(C, us_iter, 1);
663                                 }
664                                 us_iter = us_iter->next;
665                         }
666                 }
667
668                 /* Unlike undo, always redo accumulation state. */
669                 undosys_step_decode(C, us, 1);
670                 ustack->step_active = us_next;
671                 if (use_skip) {
672                         if (ustack->step_active && ustack->step_active->skip) {
673                                 CLOG_INFO(&LOG, 2, "redo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
674                                 BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
675                         }
676                 }
677                 return true;
678         }
679         return false;
680 }
681 bool BKE_undosys_step_redo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
682 {
683         return BKE_undosys_step_redo_with_data_ex(ustack, C, us, true);
684 }
685
686 bool BKE_undosys_step_redo(UndoStack *ustack, bContext *C)
687 {
688         return BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
689 }
690
691 bool BKE_undosys_step_load_data(UndoStack *ustack, bContext *C, UndoStep *us)
692 {
693         UNDO_NESTED_ASSERT(false);
694         const int index_active = BLI_findindex(&ustack->steps, ustack->step_active);
695         const int index_target = BLI_findindex(&ustack->steps, us);
696         BLI_assert(!ELEM(-1, index_active, index_target));
697         bool ok = true;
698
699         if (index_target < index_active) {
700                 uint i = index_active - index_target;
701                 while (i-- && ok) {
702                         ok = BKE_undosys_step_undo_with_data_ex(ustack, C, ustack->step_active, false);
703                 }
704         }
705         else if (index_target > index_active) {
706                 uint i = index_target - index_active;
707                 while (i-- && ok) {
708                         ok = BKE_undosys_step_redo_with_data_ex(ustack, C, ustack->step_active, false);
709                 }
710         }
711
712         if (ok) {
713                 BLI_assert(ustack->step_active == us);
714         }
715
716         return ok;
717 }
718
719 bool BKE_undosys_step_undo_compat_only(UndoStack *ustack, bContext *C, int step)
720 {
721         if (step == 0) {
722                 return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
723         }
724         else if (step == 1) {
725                 return BKE_undosys_step_undo(ustack, C);
726         }
727         else {
728                 return BKE_undosys_step_redo(ustack, C);
729         }
730 }
731 /**
732  * Similar to #WM_operatortype_append
733  */
734 UndoType *BKE_undosys_type_append(void (*undosys_fn)(UndoType *))
735 {
736         UndoType *ut;
737
738         ut = MEM_callocN(sizeof(UndoType), __func__);
739
740         undosys_fn(ut);
741
742         BLI_assert(ut->mode != 0);
743
744         BLI_addtail(&g_undo_types, ut);
745
746         return ut;
747 }
748
749 void BKE_undosys_type_free_all(void)
750 {
751         UndoType *ut;
752         while ((ut = BLI_pophead(&g_undo_types))) {
753                 MEM_freeN(ut);
754         }
755 }
756
757 /** \} */
758
759 /* -------------------------------------------------------------------- */
760 /** \name ID Reference Utilities
761  *
762  * Unfortunately we need this for a handful of places.
763  */
764
765 /* Disable for now since it accesses freed memory.
766  * The pointer can only be a key, we can't read it's contents. */
767 #define USE_LIB_SKIP
768
769 static void UNUSED_FUNCTION(BKE_undosys_foreach_ID_ref(
770         UndoStack *ustack, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data))
771 {
772         for (UndoStep *us = ustack->steps.first; us; us = us->next) {
773                 const UndoType *ut = us->type;
774                 if (ut->step_foreach_ID_ref != NULL) {
775                         ut->step_foreach_ID_ref(us, foreach_ID_ref_fn, user_data);
776                 }
777         }
778 }
779
780 typedef struct UndoIDPtrMapItem {
781         /** Never changes (matches undo data). Use as sort key for binary search. */
782         const void *ptr;
783         /** Write the new pointers here. */
784         uint index;
785 } UndoIDPtrMapItem;
786
787 typedef struct UndoIDPtrMap {
788         UndoRefID *refs;
789         /**
790          * Pointer map, update 'dst' members before use.
791          * This is always sorted (adds some overhead when adding, in practice it's acceptable since).
792          */
793         UndoIDPtrMapItem *pmap;
794
795         /** Length for both 'refs' & 'pmap' */
796         uint len;
797         uint len_alloc;
798 } UndoIDPtrMap;
799
800 #ifdef DEBUG
801 #  define PMAP_DEFAULT_ALLOC 1
802 #else
803 #  define PMAP_DEFAULT_ALLOC 32
804 #endif
805
806 void BKE_undosys_ID_map_foreach_ID_ref(
807         UndoIDPtrMap *map,
808         UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
809 {
810         for (uint i = 0; i < map->len; i++) {
811                 foreach_ID_ref_fn(user_data, &map->refs[i]);
812         }
813 }
814
815 /**
816  * Return true when found, otherwise index is set to the index we should insert.
817  */
818 static bool undosys_ID_map_lookup_index(const UndoIDPtrMap *map, const void *key, uint *r_index)
819 {
820         const UndoIDPtrMapItem *pmap = map->pmap;
821         const uint len = map->len;
822         if (len == 0) {
823                 if (*r_index) {
824                         *r_index = 0;
825                 }
826                 return false;
827         }
828         int min = 0, max = len - 1;
829         while (min <= max) {
830                 const uint mid = (min + max) / 2;
831                 if (pmap[mid].ptr < key) {
832                         min = mid + 1;
833                 }
834                 else if (pmap[mid].ptr == key) {
835                         if (r_index) {
836                                 *r_index = mid;
837                         }
838                         return true;
839                 }
840                 else if (pmap[mid].ptr > key) {
841                         max = mid - 1;
842                 }
843         }
844         if (r_index) {
845                 *r_index = min;
846         }
847         return false;
848 }
849
850 /**
851  * A set of ID's use for efficient decoding, so we can map pointers back to the newly loaded data
852  * without performing full look ups each time.
853  *
854  * This can be used as an old_pointer -> new_pointer lookup.
855  */
856 UndoIDPtrMap *BKE_undosys_ID_map_create(void)
857 {
858         UndoIDPtrMap *map = MEM_mallocN(sizeof(*map), __func__);
859         map->len_alloc = PMAP_DEFAULT_ALLOC;
860         map->refs = MEM_mallocN(sizeof(*map->refs) * map->len_alloc, __func__);
861         map->pmap = MEM_mallocN(sizeof(*map->pmap) * map->len_alloc, __func__);
862         map->len = 0;
863         return map;
864 }
865 void BKE_undosys_ID_map_destroy(UndoIDPtrMap *idpmap)
866 {
867         MEM_SAFE_FREE(idpmap->refs);
868         MEM_SAFE_FREE(idpmap->pmap);
869         MEM_freeN(idpmap);
870 }
871
872 void BKE_undosys_ID_map_add(UndoIDPtrMap *map, ID *id)
873 {
874         uint index;
875 #ifdef USE_LIB_SKIP
876         if (id->lib != NULL) {
877                 return;
878         }
879 #endif
880
881         if (undosys_ID_map_lookup_index(map, id, &index)) {
882                 return;  /* exists. */
883         }
884
885         const uint len_src = map->len;
886         const uint len_dst = map->len + 1;
887         if (len_dst > map->len_alloc) {
888                 map->len_alloc *= 2;
889                 BLI_assert(map->len_alloc >= len_dst);
890                 map->pmap = MEM_reallocN(map->pmap, sizeof(*map->pmap) * map->len_alloc);
891                 map->refs = MEM_reallocN(map->refs, sizeof(*map->refs) * map->len_alloc);
892         }
893
894 #if 0  /* Will be done automatically in callback. */
895         BLI_strncpy(map->refs[len_src].name, id->name, sizeof(id->name));
896 #else
897         map->refs[len_src].name[0] = '\0';
898 #endif
899         map->refs[len_src].ptr = id;
900
901         if (len_src != 0 && index != len_src) {
902                 memmove(&map->pmap[index + 1], &map->pmap[index], sizeof(*map->pmap) * (len_src - index));
903         }
904         map->pmap[index].ptr = id;
905         map->pmap[index].index = len_src;
906
907         map->len = len_dst;
908 }
909
910 ID *BKE_undosys_ID_map_lookup(const UndoIDPtrMap *map, const ID *id_src)
911 {
912         /* We should only ever lookup indices which exist! */
913         uint index;
914         if (!undosys_ID_map_lookup_index(map, id_src, &index)) {
915                 BLI_assert(0);
916         }
917         index = map->pmap[index].index;
918         ID *id_dst = map->refs[index].ptr;
919         BLI_assert(id_dst != NULL);
920         BLI_assert(STREQ(id_dst->name, map->refs[index].name));
921         return id_dst;
922 }
923
924 void BKE_undosys_ID_map_add_with_prev(UndoIDPtrMap *map, ID *id, ID **id_prev)
925 {
926         if (id == *id_prev) {
927                 return;
928         }
929         *id_prev = id;
930         BKE_undosys_ID_map_add(map, id);
931 }
932
933 ID *BKE_undosys_ID_map_lookup_with_prev(const UndoIDPtrMap *map, ID *id_src, ID *id_prev_match[2])
934 {
935         if (id_src == id_prev_match[0]) {
936                 return id_prev_match[1];
937         }
938         else {
939 #ifdef USE_LIB_SKIP
940                 ID *id_dst = BKE_undosys_ID_map_lookup(map, id_src);
941 #else
942                 ID *id_dst = (id_src->lib == NULL) ? BKE_undosys_ID_map_lookup(map, id_src) : id_src;
943 #endif
944                 id_prev_match[0] = id_src;
945                 id_prev_match[1] = id_dst;
946                 return id_dst;
947         }
948 }
949
950 /** \} */