Fix undo of transform after frame change undoing too much.
[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_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 static bool undosys_stack_push_main(UndoStack *ustack, const char *name, struct Main *bmain)
255 {
256         UNDO_NESTED_ASSERT(false);
257         CLOG_INFO(&LOG, 1, "'%s'", name);
258         bContext *C_temp = CTX_create();
259         CTX_data_main_set(C_temp, bmain);
260         bool ok = BKE_undosys_step_push_with_type(ustack, C_temp, name, BKE_UNDOSYS_TYPE_MEMFILE);
261         CTX_free(C_temp);
262         return ok;
263 }
264
265 void BKE_undosys_stack_init_from_main(UndoStack *ustack, struct Main *bmain)
266 {
267         UNDO_NESTED_ASSERT(false);
268         undosys_stack_push_main(ustack, "original", bmain);
269 }
270
271 /* called after 'BKE_undosys_stack_init_from_main' */
272 void BKE_undosys_stack_init_from_context(UndoStack *ustack, bContext *C)
273 {
274         const UndoType *ut = BKE_undosys_type_from_context(C);
275         if ((ut != NULL) && (ut != BKE_UNDOSYS_TYPE_MEMFILE) && (ut->mode == BKE_UNDOTYPE_MODE_STORE)) {
276                 BKE_undosys_step_push_with_type(ustack, C, "original mode", ut);
277         }
278 }
279
280 /* name optional */
281 bool BKE_undosys_stack_has_undo(UndoStack *ustack, const char *name)
282 {
283         if (name) {
284                 UndoStep *us = BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
285                 return us && us->prev;
286         }
287
288         return !BLI_listbase_is_empty(&ustack->steps);
289 }
290
291 UndoStep *BKE_undosys_stack_active_with_type(UndoStack *ustack, const UndoType *ut)
292 {
293         UndoStep *us = ustack->step_active;
294         while (us && (us->type != ut)) {
295                 us = us->prev;
296         }
297         return us;
298 }
299
300 UndoStep *BKE_undosys_stack_init_or_active_with_type(UndoStack *ustack, const UndoType *ut)
301 {
302         UNDO_NESTED_ASSERT(false);
303         CLOG_INFO(&LOG, 1, "type='%s'", ut->name);
304         if (ustack->step_init && (ustack->step_init->type == ut)) {
305                 return ustack->step_init;
306         }
307         return BKE_undosys_stack_active_with_type(ustack, ut);
308 }
309
310 /**
311  * \param steps: Limit the number of undo steps.
312  * \param memory_limit: Limit the amount of memory used by the undo stack.
313  */
314 void BKE_undosys_stack_limit_steps_and_memory(UndoStack *ustack, int steps, size_t memory_limit)
315 {
316         UNDO_NESTED_ASSERT(false);
317         if (!(steps || memory_limit)) {
318                 return;
319         }
320
321         CLOG_INFO(&LOG, 1, "steps=%d, memory_limit=%zu", steps, memory_limit);
322         UndoStep *us;
323 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
324         UndoStep *us_exclude = NULL;
325 #endif
326         /* keep at least two (original + other) */
327         size_t data_size_all = 0;
328         size_t us_count = 0;
329         for (us = ustack->steps.last; us && us->prev; us = us->prev) {
330                 if (memory_limit) {
331                         data_size_all += us->data_size;
332                         if (data_size_all > memory_limit) {
333                                 break;
334                         }
335                 }
336                 if (steps) {
337                         if (us_count == steps) {
338                                 break;
339                         }
340                         if (us->skip == false) {
341                                 us_count += 1;
342                         }
343                 }
344         }
345
346         if (us) {
347                 if (us->prev && us->prev->prev) {
348                         us = us->prev;
349                 }
350
351 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
352                 /* Hack, we need to keep at least one BKE_UNDOSYS_TYPE_MEMFILE. */
353                 if (us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
354                         us_exclude = us->prev;
355                         while (us_exclude && us->type != BKE_UNDOSYS_TYPE_MEMFILE) {
356                                 us_exclude = us_exclude->prev;
357                         }
358                         if (us_exclude) {
359                                 BLI_remlink(&ustack->steps, us_exclude);
360                         }
361                 }
362 #endif
363                 /* Free from first to last, free functions may update de-duplication info (see #MemFileUndoStep). */
364                 while (ustack->steps.first != us) {
365                         UndoStep *us_first = ustack->steps.first;
366                         BLI_assert(us_first != ustack->step_active);
367                         undosys_step_free_and_unlink(ustack, us_first);
368                 }
369
370 #ifdef WITH_GLOBAL_UNDO_KEEP_ONE
371                 if (us_exclude) {
372                         BLI_addhead(&ustack->steps, us_exclude);
373                 }
374 #endif
375         }
376 }
377
378 /** \} */
379
380 UndoStep *BKE_undosys_step_push_init_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
381 {
382         UNDO_NESTED_ASSERT(false);
383         /* We could detect and clean this up (but it should never happen!). */
384         BLI_assert(ustack->step_init == NULL);
385         if (ut->step_encode_init) {
386                 undosys_stack_validate(ustack, false);
387                 UndoStep *us = MEM_callocN(ut->step_size, __func__);
388                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, name, ut->name);
389                 if (name != NULL) {
390                         BLI_strncpy(us->name, name, sizeof(us->name));
391                 }
392                 us->type = ut;
393                 ustack->step_init = us;
394                 ut->step_encode_init(C, us);
395                 undosys_stack_validate(ustack, false);
396                 return us;
397         }
398         else {
399                 return NULL;
400         }
401 }
402
403 UndoStep *BKE_undosys_step_push_init(UndoStack *ustack, bContext *C, const char *name)
404 {
405         UNDO_NESTED_ASSERT(false);
406         /* We could detect and clean this up (but it should never happen!). */
407         BLI_assert(ustack->step_init == NULL);
408         const UndoType *ut = BKE_undosys_type_from_context(C);
409         if (ut == NULL) {
410                 return NULL;
411         }
412         return BKE_undosys_step_push_init_with_type(ustack, C, name, ut);
413 }
414
415 bool BKE_undosys_step_push_with_type(UndoStack *ustack, bContext *C, const char *name, const UndoType *ut)
416 {
417         UNDO_NESTED_ASSERT(false);
418         undosys_stack_validate(ustack, false);
419         bool is_not_empty = ustack->step_active != NULL;
420
421         /* Remove all undos after (also when 'ustack->step_active == NULL'). */
422         while (ustack->steps.last != ustack->step_active) {
423                 UndoStep *us_iter = ustack->steps.last;
424                 undosys_step_free_and_unlink(ustack, us_iter);
425                 undosys_stack_validate(ustack, is_not_empty);
426         }
427
428         if (ustack->step_active) {
429                 BLI_assert(BLI_findindex(&ustack->steps, ustack->step_active) != -1);
430         }
431
432 #ifdef WITH_GLOBAL_UNDO_ENSURE_UPDATED
433         if (ut->step_foreach_ID_ref != NULL) {
434                 Main *bmain = G.main;
435                 if (bmain->is_memfile_undo_written == false) {
436                         const char *name_internal = "MemFile Internal";
437                         if (undosys_stack_push_main(ustack, name_internal, bmain)) {
438                                 UndoStep *us = ustack->steps.last;
439                                 BLI_assert(STREQ(us->name, name_internal));
440                                 us->skip = true;
441                         }
442                 }
443         }
444 #endif
445
446         UndoStep *us = ustack->step_init ? ustack->step_init : MEM_callocN(ut->step_size, __func__);
447         ustack->step_init = NULL;
448         if (us->name[0] == '\0') {
449                 BLI_strncpy(us->name, name, sizeof(us->name));
450         }
451         us->type = ut;
452         /* initialized, not added yet. */
453
454         if (undosys_step_encode(C, us)) {
455                 ustack->step_active = us;
456                 BLI_addtail(&ustack->steps, us);
457                 undosys_stack_validate(ustack, true);
458                 return true;
459         }
460         else {
461                 MEM_freeN(us);
462                 undosys_stack_validate(ustack, true);
463                 return false;
464         }
465 }
466
467 bool BKE_undosys_step_push(UndoStack *ustack, bContext *C, const char *name)
468 {
469         UNDO_NESTED_ASSERT(false);
470         const UndoType *ut = ustack->step_init ? ustack->step_init->type : BKE_undosys_type_from_context(C);
471         if (ut == NULL) {
472                 return false;
473         }
474         return BKE_undosys_step_push_with_type(ustack, C, name, ut);
475 }
476
477
478 /**
479  * Useful when we want to diff against previous undo data but can't be sure the types match.
480  */
481 UndoStep *BKE_undosys_step_same_type_next(UndoStep *us)
482 {
483         if (us) {
484                 const UndoType *ut = us->type;
485                 while ((us = us->next)) {
486                         if (us->type == ut) {
487                                 return us;
488                         }
489                 }
490
491         }
492         return us;
493 }
494
495 /**
496  * Useful when we want to diff against previous undo data but can't be sure the types match.
497  */
498 UndoStep *BKE_undosys_step_same_type_prev(UndoStep *us)
499 {
500         if (us) {
501                 const UndoType *ut = us->type;
502                 while ((us = us->prev)) {
503                         if (us->type == ut) {
504                                 return us;
505                         }
506                 }
507
508         }
509         return us;
510 }
511
512 UndoStep *BKE_undosys_step_find_by_name_with_type(UndoStack *ustack, const char *name, const UndoType *ut)
513 {
514         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
515                 if (us->type == ut) {
516                         if (STREQ(name, us->name)) {
517                                 return us;
518                         }
519                 }
520         }
521         return NULL;
522 }
523
524 UndoStep *BKE_undosys_step_find_by_name(UndoStack *ustack, const char *name)
525 {
526         return BLI_rfindstring(&ustack->steps, name, offsetof(UndoStep, name));
527 }
528
529 UndoStep *BKE_undosys_step_find_by_type(UndoStack *ustack, const UndoType *ut)
530 {
531         for (UndoStep *us = ustack->steps.last; us; us = us->prev) {
532                 if (us->type == ut) {
533                         return us;
534                 }
535         }
536         return NULL;
537 }
538
539 bool BKE_undosys_step_undo_with_data_ex(
540         UndoStack *ustack, bContext *C, UndoStep *us,
541         bool use_skip)
542 {
543         UNDO_NESTED_ASSERT(false);
544         if (us) {
545                 undosys_stack_validate(ustack, true);
546         }
547         UndoStep *us_prev = us ? us->prev : NULL;
548         if (us && us->type->mode == BKE_UNDOTYPE_MODE_STORE) {
549                 /* The current state is a copy, we need to load the previous state. */
550                 us = us_prev;
551         }
552
553         if (us != NULL) {
554                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
555                 undosys_step_decode(C, us, -1);
556                 ustack->step_active = us_prev;
557                 undosys_stack_validate(ustack, true);
558                 if (use_skip) {
559                         if (ustack->step_active && ustack->step_active->skip) {
560                                 CLOG_INFO(&LOG, 2, "undo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
561                                 BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
562                         }
563                 }
564                 return true;
565         }
566         return false;
567 }
568 bool BKE_undosys_step_undo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
569 {
570         return BKE_undosys_step_undo_with_data_ex(ustack, C, us, true);
571 }
572
573 bool BKE_undosys_step_undo(UndoStack *ustack, bContext *C)
574 {
575         return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
576 }
577
578 void BKE_undosys_step_undo_from_index(UndoStack *ustack, bContext *C, int index)
579 {
580         UndoStep *us = BLI_findlink(&ustack->steps, index);
581         BLI_assert(us->skip == false);
582         BKE_undosys_step_load_data(ustack, C, us);
583 }
584
585 bool BKE_undosys_step_redo_with_data_ex(
586         UndoStack *ustack, bContext *C, UndoStep *us,
587         bool use_skip)
588 {
589         UNDO_NESTED_ASSERT(false);
590         UndoStep *us_next = us ? us->next : NULL;
591         /* Unlike undo accumulate, we always use the next. */
592         us = us_next;
593
594         if (us != NULL) {
595                 CLOG_INFO(&LOG, 1, "addr=%p, name='%s', type='%s'", us, us->name, us->type->name);
596                 undosys_step_decode(C, us, 1);
597                 ustack->step_active = us_next;
598                 if (use_skip) {
599                         if (ustack->step_active && ustack->step_active->skip) {
600                                 CLOG_INFO(&LOG, 2, "redo continue with skip %p '%s', type='%s'", us, us->name, us->type->name);
601                                 BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
602                         }
603                 }
604                 return true;
605         }
606         return false;
607 }
608 bool BKE_undosys_step_redo_with_data(UndoStack *ustack, bContext *C, UndoStep *us)
609 {
610         return BKE_undosys_step_redo_with_data_ex(ustack, C, us, true);
611 }
612
613 bool BKE_undosys_step_redo(UndoStack *ustack, bContext *C)
614 {
615         return BKE_undosys_step_redo_with_data(ustack, C, ustack->step_active);
616 }
617
618 bool BKE_undosys_step_load_data(UndoStack *ustack, bContext *C, UndoStep *us)
619 {
620         UNDO_NESTED_ASSERT(false);
621         const int index_active = BLI_findindex(&ustack->steps, ustack->step_active);
622         const int index_target = BLI_findindex(&ustack->steps, us);
623         BLI_assert(!ELEM(-1, index_active, index_target));
624         bool ok = true;
625
626         if (index_target < index_active) {
627                 uint i = index_active - index_target;
628                 while (i-- && ok) {
629                         ok = BKE_undosys_step_undo_with_data_ex(ustack, C, ustack->step_active, false);
630                 }
631         }
632         else if (index_target > index_active) {
633                 uint i = index_target - index_active;
634                 while (i-- && ok) {
635                         ok = BKE_undosys_step_redo_with_data_ex(ustack, C, ustack->step_active, false);
636                 }
637         }
638
639         if (ok) {
640                 BLI_assert(ustack->step_active == us);
641         }
642
643         return ok;
644 }
645
646 bool BKE_undosys_step_undo_compat_only(UndoStack *ustack, bContext *C, int step)
647 {
648         if (step == 0) {
649                 return BKE_undosys_step_undo_with_data(ustack, C, ustack->step_active);
650         }
651         else if (step == 1) {
652                 return BKE_undosys_step_undo(ustack, C);
653         }
654         else {
655                 return BKE_undosys_step_redo(ustack, C);
656         }
657 }
658 /**
659  * Similar to #WM_operatortype_append
660  */
661 UndoType *BKE_undosys_type_append(void (*undosys_fn)(UndoType *))
662 {
663         UndoType *ut;
664
665         ut = MEM_callocN(sizeof(UndoType), __func__);
666
667         undosys_fn(ut);
668
669         BLI_assert(ut->mode != 0);
670
671         BLI_addtail(&g_undo_types, ut);
672
673         return ut;
674 }
675
676 void BKE_undosys_type_free_all(void)
677 {
678         UndoType *ut;
679         while ((ut = BLI_pophead(&g_undo_types))) {
680                 MEM_freeN(ut);
681         }
682 }
683
684 /** \} */
685
686 /* -------------------------------------------------------------------- */
687 /** \name ID Reference Utilities
688  *
689  * Unfortunately we need this for a handful of places.
690  */
691
692 static void UNUSED_FUNCTION(BKE_undosys_foreach_ID_ref(
693         UndoStack *ustack, UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data))
694 {
695         for (UndoStep *us = ustack->steps.first; us; us = us->next) {
696                 const UndoType *ut = us->type;
697                 if (ut->step_foreach_ID_ref != NULL) {
698                         ut->step_foreach_ID_ref(us, foreach_ID_ref_fn, user_data);
699                 }
700         }
701 }
702
703 typedef struct UndoIDPtrMapItem {
704         /** Never changes (matches undo data). Use as sort key for binary search. */
705         const void *ptr;
706         /** Write the new pointers here. */
707         uint index;
708 } UndoIDPtrMapItem;
709
710 typedef struct UndoIDPtrMap {
711         UndoRefID *refs;
712         /**
713          * Pointer map, update 'dst' members before use.
714          * This is always sorted (adds some overhead when adding, in practice it's acceptable since).
715          */
716         UndoIDPtrMapItem *pmap;
717
718         /** Length for both 'refs' & 'pmap' */
719         uint len;
720         uint len_alloc;
721 } UndoIDPtrMap;
722
723 #ifdef DEBUG
724 #  define PMAP_DEFAULT_ALLOC 1
725 #else
726 #  define PMAP_DEFAULT_ALLOC 32
727 #endif
728
729 void BKE_undosys_ID_map_foreach_ID_ref(
730         UndoIDPtrMap *map,
731         UndoTypeForEachIDRefFn foreach_ID_ref_fn, void *user_data)
732 {
733         for (uint i = 0; i < map->len; i++) {
734                 foreach_ID_ref_fn(user_data, &map->refs[i]);
735         }
736 }
737
738 /**
739  * Return true when found, otherwise index is set to the index we should insert.
740  */
741 static bool undosys_ID_map_lookup_index(const UndoIDPtrMap *map, const void *key, uint *r_index)
742 {
743         const UndoIDPtrMapItem *pmap = map->pmap;
744         const uint len = map->len;
745         if (len == 0) {
746                 if (*r_index) {
747                         *r_index = 0;
748                 }
749                 return false;
750         }
751         int min = 0, max = len - 1;
752         while (min <= max) {
753                 const uint mid = (min + max) / 2;
754                 if (pmap[mid].ptr < key) {
755                         min = mid + 1;
756                 }
757                 else if (pmap[mid].ptr == key) {
758                         if (r_index) {
759                                 *r_index = mid;
760                         }
761                         return true;
762                 }
763                 else if (pmap[mid].ptr > key) {
764                         max = mid - 1;
765                 }
766         }
767         if (r_index) {
768                 *r_index = min;
769         }
770         return false;
771 }
772
773 /**
774  * A set of ID's use for efficient decoding, so we can map pointers back to the newly loaded data
775  * without performing full look ups each time.
776  *
777  * This can be used as an old_pointer -> new_pointer lookup.
778  */
779 UndoIDPtrMap *BKE_undosys_ID_map_create(void)
780 {
781         UndoIDPtrMap *map = MEM_mallocN(sizeof(*map), __func__);
782         map->len_alloc = PMAP_DEFAULT_ALLOC;
783         map->refs = MEM_mallocN(sizeof(*map->refs) * map->len_alloc, __func__);
784         map->pmap = MEM_mallocN(sizeof(*map->pmap) * map->len_alloc, __func__);
785         map->len = 0;
786         return map;
787 }
788 void BKE_undosys_ID_map_destroy(UndoIDPtrMap *idpmap)
789 {
790         MEM_SAFE_FREE(idpmap->refs);
791         MEM_SAFE_FREE(idpmap->pmap);
792         MEM_freeN(idpmap);
793 }
794
795 void BKE_undosys_ID_map_add(UndoIDPtrMap *map, ID *id)
796 {
797         uint index;
798         if (id->lib != NULL) {
799                 return;
800         }
801
802         if (undosys_ID_map_lookup_index(map, id, &index)) {
803                 return;  /* exists. */
804         }
805
806         const uint len_src = map->len;
807         const uint len_dst = map->len + 1;
808         if (len_dst > map->len_alloc) {
809                 map->len_alloc *= 2;
810                 BLI_assert(map->len_alloc >= len_dst);
811                 map->pmap = MEM_reallocN(map->pmap, sizeof(*map->pmap) * map->len_alloc);
812                 map->refs = MEM_reallocN(map->refs, sizeof(*map->refs) * map->len_alloc);
813         }
814
815 #if 0  /* Will be done automatically in callback. */
816         BLI_strncpy(map->refs[len_src].name, id->name, sizeof(id->name));
817 #else
818         map->refs[len_src].name[0] = '\0';
819 #endif
820         map->refs[len_src].ptr = id;
821
822         if (len_src != 0 && index != len_src) {
823                 memmove(&map->pmap[index + 1], &map->pmap[index], sizeof(*map->pmap) * (len_src - index));
824         }
825         map->pmap[index].ptr = id;
826         map->pmap[index].index = len_src;
827
828         map->len = len_dst;
829 }
830
831 ID *BKE_undosys_ID_map_lookup(const UndoIDPtrMap *map, const ID *id_src)
832 {
833         /* We should only ever lookup indices which exist! */
834         uint index;
835         if (!undosys_ID_map_lookup_index(map, id_src, &index)) {
836                 BLI_assert(0);
837         }
838         index = map->pmap[index].index;
839         ID *id_dst = map->refs[index].ptr;
840         BLI_assert(id_dst != NULL);
841         BLI_assert(STREQ(id_dst->name, map->refs[index].name));
842         return id_dst;
843 }
844
845 void BKE_undosys_ID_map_add_with_prev(UndoIDPtrMap *map, ID *id, ID **id_prev)
846 {
847         if (id == *id_prev) {
848                 return;
849         }
850         *id_prev = id;
851         BKE_undosys_ID_map_add(map, id);
852 }
853
854 ID *BKE_undosys_ID_map_lookup_with_prev(const UndoIDPtrMap *map, ID *id_src, ID *id_prev_match[2])
855 {
856         if (id_src == id_prev_match[0]) {
857                 return id_prev_match[1];
858         }
859         else {
860                 ID *id_dst = BKE_undosys_ID_map_lookup(map, id_src);
861                 id_prev_match[0] = id_src;
862                 id_prev_match[1] = id_dst;
863                 return id_dst;
864         }
865 }
866
867 /** \} */