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