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