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