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