729be02bfc70b876006d1ba52bc99fa834f37305
[blender.git] / source / blender / blenkernel / intern / collection.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  * Contributor(s): Dalai Felinto
19  *
20  * ***** END GPL LICENSE BLOCK *****
21  */
22
23 /** \file blender/blenkernel/intern/collection.c
24  *  \ingroup bke
25  */
26
27 #include <string.h>
28
29 #include "BLI_blenlib.h"
30 #include "BLI_ghash.h"
31 #include "BLI_iterator.h"
32 #include "BLI_listbase.h"
33 #include "BLI_math_base.h"
34 #include "BLT_translation.h"
35 #include "BLI_string_utils.h"
36
37 #include "BKE_collection.h"
38 #include "BKE_group.h"
39 #include "BKE_idprop.h"
40 #include "BKE_layer.h"
41 #include "BKE_library.h"
42 #include "BKE_main.h"
43 #include "BKE_scene.h"
44
45 #include "DNA_group_types.h"
46 #include "DNA_ID.h"
47 #include "DNA_layer_types.h"
48 #include "DNA_object_types.h"
49 #include "DNA_scene_types.h"
50
51 #include "MEM_guardedalloc.h"
52
53 /* Prototypes. */
54 static SceneCollection *find_collection_parent(const struct SceneCollection *sc_child, struct SceneCollection *sc_parent);
55 static bool is_collection_in_tree(const struct SceneCollection *sc_reference, struct SceneCollection *sc_parent);
56
57 static SceneCollection *collection_master_from_id(const ID *owner_id)
58 {
59         switch (GS(owner_id->name)) {
60                 case ID_SCE:
61                         return ((Scene *)owner_id)->collection;
62                 case ID_GR:
63                         return ((Group *)owner_id)->collection;
64                 default:
65                         BLI_assert(!"ID doesn't support collections");
66                         return NULL;
67         }
68 }
69
70 /**
71  * Add a new collection, but don't handle syncing with layer collections
72  */
73 static SceneCollection *collection_add(ID *owner_id, SceneCollection *sc_parent, const int type, const char *name_custom)
74 {
75         SceneCollection *sc_master = collection_master_from_id(owner_id);
76         SceneCollection *sc = MEM_callocN(sizeof(SceneCollection), "New Collection");
77         sc->type = type;
78         const char *name = name_custom;
79
80         if (!sc_parent) {
81                 sc_parent = sc_master;
82         }
83
84         if (!name) {
85                 if (sc_parent == sc_master) {
86                         name = BLI_sprintfN("Collection %d", BLI_listbase_count(&sc_master->scene_collections) + 1);
87                 }
88                 else {
89                         const int number = BLI_listbase_count(&sc_parent->scene_collections) + 1;
90                         const int digits = integer_digits_i(number);
91                         const int max_len = sizeof(sc_parent->name)
92                                             - 1 /* NULL terminator */
93                                             - (1 + digits) /* " %d" */;
94                         name = BLI_sprintfN("%.*s %d", max_len, sc_parent->name, number);
95                 }
96         }
97
98         BLI_addtail(&sc_parent->scene_collections, sc);
99         BKE_collection_rename((Scene *)owner_id, sc, name);
100
101         if (name != name_custom) {
102                 MEM_freeN((char *)name);
103         }
104
105         return sc;
106 }
107
108 /**
109  * Add a collection to a collection ListBase and syncronize all render layers
110  * The ListBase is NULL when the collection is to be added to the master collection
111  */
112 SceneCollection *BKE_collection_add(ID *owner_id, SceneCollection *sc_parent, const int type, const char *name_custom)
113 {
114         SceneCollection *scene_collection = collection_add(owner_id, sc_parent, type, name_custom);
115         BKE_layer_sync_new_scene_collection(owner_id, sc_parent, scene_collection);
116         return scene_collection;
117 }
118
119 /**
120  * Free the collection items recursively
121  */
122 static void collection_free(SceneCollection *sc, const bool do_id_user)
123 {
124         if (do_id_user) {
125                 for (LinkData *link = sc->objects.first; link; link = link->next) {
126                         id_us_min(link->data);
127                 }
128         }
129
130         BLI_freelistN(&sc->objects);
131
132         for (SceneCollection *nsc = sc->scene_collections.first; nsc; nsc = nsc->next) {
133                 collection_free(nsc, do_id_user);
134         }
135         BLI_freelistN(&sc->scene_collections);
136 }
137
138 /**
139  * Unlink the collection recursively
140  * \return true if unlinked.
141  */
142 static bool collection_remlink(SceneCollection *sc_parent, SceneCollection *sc_gone)
143 {
144         for (SceneCollection *sc = sc_parent->scene_collections.first; sc; sc = sc->next) {
145                 if (sc == sc_gone) {
146                         BLI_remlink(&sc_parent->scene_collections, sc_gone);
147                         return true;
148                 }
149
150                 if (collection_remlink(sc, sc_gone)) {
151                         return true;
152                 }
153         }
154         return false;
155 }
156
157 /**
158  * Recursively remove any instance of this SceneCollection
159  */
160 static void layer_collection_remove(ViewLayer *view_layer, ListBase *lb, const SceneCollection *sc)
161 {
162         LayerCollection *lc = lb->first;
163         while (lc) {
164                 if (lc->scene_collection == sc) {
165                         BKE_layer_collection_free(view_layer, lc);
166                         BLI_remlink(lb, lc);
167
168                         LayerCollection *lc_next = lc->next;
169                         MEM_freeN(lc);
170                         lc = lc_next;
171
172                         /* only the "top-level" layer collections may have the
173                          * same SceneCollection in a sibling tree.
174                          */
175                         if (lb != &view_layer->layer_collections) {
176                                 return;
177                         }
178                 }
179
180                 else {
181                         layer_collection_remove(view_layer, &lc->layer_collections, sc);
182                         lc = lc->next;
183                 }
184         }
185 }
186
187 /**
188  * Remove a collection from the scene, and syncronize all render layers
189  *
190  * If an object is in any other collection, link the object to the master collection.
191  */
192 bool BKE_collection_remove(ID *owner_id, SceneCollection *sc)
193 {
194         SceneCollection *sc_master = collection_master_from_id(owner_id);
195
196         /* The master collection cannot be removed. */
197         if (sc == sc_master) {
198                 return false;
199         }
200
201         /* We need to do bottom up removal, otherwise we get a crash when we remove a collection that
202          * has one of its nested collections linked to a view layer. */
203         SceneCollection *scene_collection_nested = sc->scene_collections.first;
204         while (scene_collection_nested != NULL) {
205                 SceneCollection *scene_collection_next = scene_collection_nested->next;
206                 BKE_collection_remove(owner_id, scene_collection_nested);
207                 scene_collection_nested = scene_collection_next;
208         }
209
210         /* Unlink from the respective collection tree. */
211         if (!collection_remlink(sc_master, sc)) {
212                 BLI_assert(false);
213         }
214
215         /* If an object is no longer in any collection, we add it to the master collection. */
216         ListBase collection_objects;
217         BLI_duplicatelist(&collection_objects, &sc->objects);
218
219         FOREACH_SCENE_COLLECTION(owner_id, scene_collection_iter)
220         {
221                 if (scene_collection_iter == sc) {
222                         continue;
223                 }
224
225                 LinkData *link_next, *link = collection_objects.first;
226                 while (link) {
227                         link_next = link->next;
228
229                         if (BLI_findptr(&scene_collection_iter->objects, link->data, offsetof(LinkData, data))) {
230                                 BLI_remlink(&collection_objects, link);
231                                 MEM_freeN(link);
232                         }
233
234                         link = link_next;
235                 }
236         }
237         FOREACH_SCENE_COLLECTION_END
238
239         for (LinkData *link = collection_objects.first; link; link = link->next) {
240                 BKE_collection_object_add(owner_id, sc_master, link->data);
241         }
242
243         BLI_freelistN(&collection_objects);
244
245         /* Clear the collection items. */
246         collection_free(sc, true);
247
248         /* check all layers that use this collection and clear them */
249         for (ViewLayer *view_layer = BKE_view_layer_first_from_id(owner_id); view_layer; view_layer = view_layer->next) {
250                 layer_collection_remove(view_layer, &view_layer->layer_collections, sc);
251                 view_layer->active_collection = 0;
252         }
253
254         MEM_freeN(sc);
255         return true;
256 }
257
258 /**
259  * Copy SceneCollection tree but keep pointing to the same objects
260  *
261  * \param flag  Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
262  */
263 void BKE_collection_copy_data(SceneCollection *sc_dst, SceneCollection *sc_src, const int flag)
264 {
265         BLI_duplicatelist(&sc_dst->objects, &sc_src->objects);
266         if ((flag & LIB_ID_CREATE_NO_USER_REFCOUNT) == 0) {
267                 for (LinkData *link = sc_dst->objects.first; link; link = link->next) {
268                         id_us_plus(link->data);
269                 }
270         }
271
272         BLI_duplicatelist(&sc_dst->scene_collections, &sc_src->scene_collections);
273         for (SceneCollection *nsc_src = sc_src->scene_collections.first, *nsc_dst = sc_dst->scene_collections.first;
274              nsc_src;
275              nsc_src = nsc_src->next, nsc_dst = nsc_dst->next)
276         {
277                 BKE_collection_copy_data(nsc_dst, nsc_src, flag);
278         }
279 }
280
281 /**
282  * Makes a shallow copy of a SceneCollection
283  *
284  * Add a new collection in the same level as the old one, copy any nested collections
285  * but link the objects to the new collection (as oppose to copy them).
286  */
287 SceneCollection *BKE_collection_duplicate(ID *owner_id, SceneCollection *scene_collection)
288 {
289         SceneCollection *scene_collection_master = BKE_collection_master(owner_id);
290         SceneCollection *scene_collection_parent = find_collection_parent(scene_collection, scene_collection_master);
291
292         /* It's not allowed to copy the master collection. */
293         if (scene_collection_master == scene_collection) {
294                 return NULL;
295         }
296
297         SceneCollection *scene_collection_new = collection_add(
298                                                     owner_id,
299                                                     scene_collection_parent,
300                                                     scene_collection->type,
301                                                     scene_collection->name);
302
303         if (scene_collection_new != scene_collection->next) {
304                 BLI_remlink(&scene_collection_parent->scene_collections, scene_collection_new);
305                 BLI_insertlinkafter(&scene_collection_parent->scene_collections, scene_collection, scene_collection_new);
306         }
307
308         BKE_collection_copy_data(scene_collection_new, scene_collection, 0);
309         BKE_layer_sync_new_scene_collection(owner_id, scene_collection_parent, scene_collection_new);
310
311         /* Make sure every linked instance of the new collection has the same values (flags, overrides, ...) as the
312          * corresponding original collection. */
313         BKE_layer_collection_sync_flags(owner_id, scene_collection_new, scene_collection);
314
315         return scene_collection_new;
316 }
317
318 static SceneCollection *master_collection_from_id(const ID *owner_id)
319 {
320         switch (GS(owner_id->name)) {
321                 case ID_SCE:
322                         return ((const Scene *)owner_id)->collection;
323                 case ID_GR:
324                         return ((const Group *)owner_id)->collection;
325                 default:
326                         BLI_assert(!"ID doesn't support scene collection");
327                         return NULL;
328         }
329 }
330
331 /**
332  * Returns the master collection of the scene or group
333  */
334 SceneCollection *BKE_collection_master(const ID *owner_id)
335 {
336         return master_collection_from_id(owner_id);
337 }
338
339 static void collection_rename(const ID *owner_id, SceneCollection *sc, const char *name)
340 {
341         SceneCollection *sc_parent = find_collection_parent(sc, collection_master_from_id(owner_id));
342         BLI_strncpy(sc->name, name, sizeof(sc->name));
343         BLI_uniquename(&sc_parent->scene_collections, sc, DATA_("Collection"), '.', offsetof(SceneCollection, name), sizeof(sc->name));
344 }
345
346 void BKE_collection_rename(const Scene *scene, SceneCollection *sc, const char *name)
347 {
348         collection_rename(&scene->id, sc, name);
349 }
350
351 /**
352  * Make sure the collection name is still unique within its siblings.
353  */
354 static void collection_name_check(const ID *owner_id, SceneCollection *sc)
355 {
356         /* It's a bit of a hack, we simply try to make sure the collection name is valid. */
357         collection_rename(owner_id, sc, sc->name);
358 }
359
360 /**
361  * Free (or release) any data used by the master collection (does not free the master collection itself).
362  * Used only to clear the entire scene or group data since it's not doing re-syncing of the LayerCollection tree
363  */
364 void BKE_collection_master_free(ID *owner_id, const bool do_id_user)
365 {
366         collection_free(BKE_collection_master(owner_id), do_id_user);
367 }
368
369 static void collection_object_add(const ID *owner_id, SceneCollection *sc, Object *ob)
370 {
371         BLI_addtail(&sc->objects, BLI_genericNodeN(ob));
372
373         if (GS(owner_id->name) == ID_SCE) {
374                 id_us_plus((ID *)ob);
375         }
376         else {
377                 BLI_assert(GS(owner_id->name) == ID_GR);
378                 if ((ob->flag & OB_FROMGROUP) == 0) {
379                         ob->flag |= OB_FROMGROUP;
380                 }
381         }
382
383         BKE_layer_sync_object_link(owner_id, sc, ob);
384 }
385
386 /**
387  * Add object to collection
388  */
389 bool BKE_collection_object_add(const ID *owner_id, SceneCollection *sc, Object *ob)
390 {
391         if (BLI_findptr(&sc->objects, ob, offsetof(LinkData, data))) {
392                 /* don't add the same object twice */
393                 return false;
394         }
395
396         collection_object_add(owner_id, sc, ob);
397         return true;
398 }
399
400 /**
401  * Add object to all collections that reference objects is in
402  * (used to copy objects)
403  */
404 void BKE_collection_object_add_from(Scene *scene, Object *ob_src, Object *ob_dst)
405 {
406         FOREACH_SCENE_COLLECTION(scene, sc)
407         {
408                 if (BLI_findptr(&sc->objects, ob_src, offsetof(LinkData, data))) {
409                         collection_object_add(&scene->id, sc, ob_dst);
410                 }
411         }
412         FOREACH_SCENE_COLLECTION_END
413
414         for (ViewLayer *view_layer = scene->view_layers.first; view_layer; view_layer = view_layer->next) {
415                 Base *base_src = BKE_view_layer_base_find(view_layer, ob_src);
416                 if (base_src != NULL) {
417                         if (base_src->collection_properties == NULL) {
418                                 continue;
419                         }
420                         Base *base_dst = BKE_view_layer_base_find(view_layer, ob_dst);
421                         IDP_MergeGroup(base_dst->collection_properties, base_src->collection_properties, true);
422                 }
423         }
424 }
425
426 /**
427  * Remove object from collection.
428  * \param bmain: Can be NULL if free_us is false.
429  */
430 bool BKE_collection_object_remove(Main *bmain, ID *owner_id, SceneCollection *sc, Object *ob, const bool free_us)
431 {
432         LinkData *link = BLI_findptr(&sc->objects, ob, offsetof(LinkData, data));
433
434         if (link == NULL) {
435                 return false;
436         }
437
438         BLI_remlink(&sc->objects, link);
439         MEM_freeN(link);
440
441         BKE_layer_sync_object_unlink(owner_id, sc, ob);
442
443         if (GS(owner_id->name) == ID_SCE) {
444                 if (free_us) {
445                         BKE_libblock_free_us(bmain, ob);
446                 }
447                 else {
448                         id_us_min(&ob->id);
449                 }
450         }
451         else {
452                 BLI_assert(GS(owner_id->name) == ID_GR);
453         }
454
455         return true;
456 }
457
458 /**
459  * Move object from a collection into another
460  */
461 void BKE_collection_object_move(ID *owner_id, SceneCollection *sc_dst, SceneCollection *sc_src, Object *ob)
462 {
463         if (BKE_collection_object_add(owner_id, sc_dst, ob)) {
464                 BKE_collection_object_remove(NULL, owner_id, sc_src, ob, false);
465         }
466 }
467
468 /**
469  * Remove object from all collections of scene
470  */
471 bool BKE_collections_object_remove(Main *bmain, ID *owner_id, Object *ob, const bool free_us)
472 {
473         bool removed = false;
474         if (GS(owner_id->name) == ID_SCE) {
475                 BKE_scene_remove_rigidbody_object((Scene *)owner_id, ob);
476         }
477         else {
478                 BLI_assert(GS(owner_id->name) == ID_GR);
479         }
480
481         FOREACH_SCENE_COLLECTION(owner_id, sc)
482         {
483                 removed |= BKE_collection_object_remove(bmain, owner_id, sc, ob, free_us);
484         }
485         FOREACH_SCENE_COLLECTION_END
486         return removed;
487 }
488
489 static void layer_collection_sync(LayerCollection *lc_dst, LayerCollection *lc_src)
490 {
491         lc_dst->flag = lc_src->flag;
492
493         /* Pending: sync overrides. */
494         IDP_MergeGroup(lc_dst->properties, lc_src->properties, true);
495
496         /* Continue recursively. */
497         LayerCollection *lc_dst_nested, *lc_src_nested;
498         lc_src_nested = lc_src->layer_collections.first;
499         for (lc_dst_nested = lc_dst->layer_collections.first;
500              lc_dst_nested && lc_src_nested;
501              lc_dst_nested = lc_dst_nested->next, lc_src_nested = lc_src_nested->next)
502         {
503                 layer_collection_sync(lc_dst_nested, lc_src_nested);
504         }
505 }
506
507 /**
508  * Leave only the master collection in, remove everything else.
509  * @param group
510  */
511 static void collection_group_cleanup(Group *group)
512 {
513         /* Unlink all the LayerCollections. */
514         while (group->view_layer->layer_collections.last != NULL) {
515                 BKE_collection_unlink(group->view_layer, group->view_layer->layer_collections.last);
516         }
517
518         /* Remove all the SceneCollections but the master. */
519         collection_free(group->collection, false);
520 }
521
522 /**
523  * Create a group from a collection
524  *
525  * Any ViewLayer that may have this the related SceneCollection linked is converted
526  * to a Group Collection.
527  */
528 Group *BKE_collection_group_create(Main *bmain, Scene *scene, LayerCollection *lc_src)
529 {
530         SceneCollection *sc_dst, *sc_src = lc_src->scene_collection;
531         LayerCollection *lc_dst;
532
533         /* The master collection can't be converted. */
534         if (sc_src == BKE_collection_master(&scene->id)) {
535                 return NULL;
536         }
537
538         /* If a sub-collection of sc_dst is directly linked into a ViewLayer we can't convert. */
539         for (ViewLayer *view_layer = scene->view_layers.first; view_layer; view_layer = view_layer->next) {
540                 for (LayerCollection *lc_child = view_layer->layer_collections.first; lc_child; lc_child = lc_child->next) {
541                         if (is_collection_in_tree(lc_child->scene_collection, sc_src)) {
542                                 return NULL;
543                         }
544                 }
545         }
546
547         /* Create new group with the same data as the original collection. */
548         Group *group = BKE_group_add(bmain, sc_src->name);
549         collection_group_cleanup(group);
550
551         sc_dst = BKE_collection_add(&group->id, NULL, COLLECTION_TYPE_GROUP_INTERNAL, sc_src->name);
552         BKE_collection_copy_data(sc_dst, sc_src, 0);
553         FOREACH_SCENE_COLLECTION(&group->id, sc_group)
554         {
555                 sc_group->type = COLLECTION_TYPE_GROUP_INTERNAL;
556         }
557         FOREACH_SCENE_COLLECTION_END
558
559         lc_dst = BKE_collection_link(group->view_layer, sc_dst);
560         layer_collection_sync(lc_dst, lc_src);
561
562         return group;
563 }
564
565 /* ---------------------------------------------------------------------- */
566 /* Outliner drag and drop */
567
568 /**
569  * Find and return the SceneCollection that has \a sc_child as one of its directly
570  * nested SceneCollection.
571  *
572  * \param sc_parent Initial SceneCollection to look into recursively, usually the master collection
573  */
574 static SceneCollection *find_collection_parent(const SceneCollection *sc_child, SceneCollection *sc_parent)
575 {
576         for (SceneCollection *sc_nested = sc_parent->scene_collections.first; sc_nested; sc_nested = sc_nested->next) {
577                 if (sc_nested == sc_child) {
578                         return sc_parent;
579                 }
580
581                 SceneCollection *found = find_collection_parent(sc_child, sc_nested);
582                 if (found) {
583                         return found;
584                 }
585         }
586
587         return NULL;
588 }
589
590 /**
591  * Check if \a sc_reference is nested to \a sc_parent SceneCollection
592  */
593 static bool is_collection_in_tree(const SceneCollection *sc_reference, SceneCollection *sc_parent)
594 {
595         return find_collection_parent(sc_reference, sc_parent) != NULL;
596 }
597
598 bool BKE_collection_move_above(const ID *owner_id, SceneCollection *sc_dst, SceneCollection *sc_src)
599 {
600         /* Find the SceneCollection the sc_src belongs to */
601         SceneCollection *sc_master = master_collection_from_id(owner_id);
602
603         /* Master Layer can't be moved around*/
604         if (ELEM(sc_master, sc_src, sc_dst)) {
605                 return false;
606         }
607
608         /* collection is already where we wanted it to be */
609         if (sc_dst->prev == sc_src) {
610                 return false;
611         }
612
613         /* We can't move a collection fs the destiny collection
614          * is nested to the source collection */
615         if (is_collection_in_tree(sc_dst, sc_src)) {
616                 return false;
617         }
618
619         SceneCollection *sc_src_parent = find_collection_parent(sc_src, sc_master);
620         SceneCollection *sc_dst_parent = find_collection_parent(sc_dst, sc_master);
621         BLI_assert(sc_src_parent);
622         BLI_assert(sc_dst_parent);
623
624         /* Remove sc_src from its parent */
625         BLI_remlink(&sc_src_parent->scene_collections, sc_src);
626
627         /* Re-insert it where it belongs */
628         BLI_insertlinkbefore(&sc_dst_parent->scene_collections, sc_dst, sc_src);
629
630         /* Update the tree */
631         BKE_layer_collection_resync(owner_id, sc_src_parent);
632         BKE_layer_collection_resync(owner_id, sc_dst_parent);
633
634         /* Keep names unique. */
635         collection_name_check(owner_id, sc_src);
636
637         return true;
638 }
639
640 bool BKE_collection_move_below(const ID *owner_id, SceneCollection *sc_dst, SceneCollection *sc_src)
641 {
642         /* Find the SceneCollection the sc_src belongs to */
643         SceneCollection *sc_master = master_collection_from_id(owner_id);
644
645         /* Master Layer can't be moved around*/
646         if (ELEM(sc_master, sc_src, sc_dst)) {
647                 return false;
648         }
649
650         /* Collection is already where we wanted it to be */
651         if (sc_dst->next == sc_src) {
652                 return false;
653         }
654
655         /* We can't move a collection if the destiny collection
656          * is nested to the source collection */
657         if (is_collection_in_tree(sc_dst, sc_src)) {
658                 return false;
659         }
660
661         SceneCollection *sc_src_parent = find_collection_parent(sc_src, sc_master);
662         SceneCollection *sc_dst_parent = find_collection_parent(sc_dst, sc_master);
663         BLI_assert(sc_src_parent);
664         BLI_assert(sc_dst_parent);
665
666         /* Remove sc_src from its parent */
667         BLI_remlink(&sc_src_parent->scene_collections, sc_src);
668
669         /* Re-insert it where it belongs */
670         BLI_insertlinkafter(&sc_dst_parent->scene_collections, sc_dst, sc_src);
671
672         /* Update the tree */
673         BKE_layer_collection_resync(owner_id, sc_src_parent);
674         BKE_layer_collection_resync(owner_id, sc_dst_parent);
675
676         /* Keep names unique. */
677         collection_name_check(owner_id, sc_src);
678
679         return true;
680 }
681
682 bool BKE_collection_move_into(const ID *owner_id, SceneCollection *sc_dst, SceneCollection *sc_src)
683 {
684         /* Find the SceneCollection the sc_src belongs to */
685         SceneCollection *sc_master = master_collection_from_id(owner_id);
686         if (sc_src == sc_master) {
687                 return false;
688         }
689
690         /* We can't move a collection if the destiny collection
691          * is nested to the source collection */
692         if (is_collection_in_tree(sc_dst, sc_src)) {
693                 return false;
694         }
695
696         SceneCollection *sc_src_parent = find_collection_parent(sc_src, sc_master);
697         BLI_assert(sc_src_parent);
698
699         /* collection is already where we wanted it to be */
700         if (sc_dst->scene_collections.last == sc_src) {
701                 return false;
702         }
703
704         /* Remove sc_src from it */
705         BLI_remlink(&sc_src_parent->scene_collections, sc_src);
706
707         /* Insert sc_src into sc_dst */
708         BLI_addtail(&sc_dst->scene_collections, sc_src);
709
710         /* Update the tree */
711         BKE_layer_collection_resync(owner_id, sc_src_parent);
712         BKE_layer_collection_resync(owner_id, sc_dst);
713
714         /* Keep names unique. */
715         collection_name_check(owner_id, sc_src);
716
717         return true;
718 }
719
720 /* ---------------------------------------------------------------------- */
721 /* Iteractors */
722 /* scene collection iteractor */
723
724 typedef struct SceneCollectionsIteratorData {
725         ID *owner_id;
726         void **array;
727         int tot, cur;
728 } SceneCollectionsIteratorData;
729
730 static void scene_collection_callback(SceneCollection *sc, BKE_scene_collections_Cb callback, void *data)
731 {
732         callback(sc, data);
733
734         for (SceneCollection *nsc = sc->scene_collections.first; nsc; nsc = nsc->next) {
735                 scene_collection_callback(nsc, callback, data);
736         }
737 }
738
739 static void scene_collections_count(SceneCollection *UNUSED(sc), void *data)
740 {
741         int *tot = data;
742         (*tot)++;
743 }
744
745 static void scene_collections_build_array(SceneCollection *sc, void *data)
746 {
747         SceneCollection ***array = data;
748         **array = sc;
749         (*array)++;
750 }
751
752 static void scene_collections_array(ID *owner_id, SceneCollection ***collections_array, int *tot)
753 {
754         SceneCollection *sc;
755         SceneCollection **array;
756
757         *collections_array = NULL;
758         *tot = 0;
759
760         if (owner_id == NULL) {
761                 return;
762         }
763
764         sc = master_collection_from_id(owner_id);
765         BLI_assert(sc != NULL);
766         scene_collection_callback(sc, scene_collections_count, tot);
767
768         if (*tot == 0)
769                 return;
770
771         *collections_array = array = MEM_mallocN(sizeof(SceneCollection *) * (*tot), "SceneCollectionArray");
772         scene_collection_callback(sc, scene_collections_build_array, &array);
773 }
774
775 /**
776  * Only use this in non-performance critical situations
777  * (it iterates over all scene collections twice)
778  */
779 void BKE_scene_collections_iterator_begin(BLI_Iterator *iter, void *data_in)
780 {
781         ID *owner_id = data_in;
782         SceneCollectionsIteratorData *data = MEM_callocN(sizeof(SceneCollectionsIteratorData), __func__);
783
784         data->owner_id = owner_id;
785         iter->data = data;
786         iter->valid = true;
787
788         scene_collections_array(owner_id, (SceneCollection ***)&data->array, &data->tot);
789         BLI_assert(data->tot != 0);
790
791         data->cur = 0;
792         iter->current = data->array[data->cur];
793 }
794
795 void BKE_scene_collections_iterator_next(struct BLI_Iterator *iter)
796 {
797         SceneCollectionsIteratorData *data = iter->data;
798
799         if (++data->cur < data->tot) {
800                 iter->current = data->array[data->cur];
801         }
802         else {
803                 iter->valid = false;
804         }
805 }
806
807 void BKE_scene_collections_iterator_end(struct BLI_Iterator *iter)
808 {
809         SceneCollectionsIteratorData *data = iter->data;
810
811         if (data) {
812                 if (data->array) {
813                         MEM_freeN(data->array);
814                 }
815                 MEM_freeN(data);
816         }
817         iter->valid = false;
818 }
819
820
821 /* scene objects iteractor */
822
823 typedef struct SceneObjectsIteratorData {
824         GSet *visited;
825         LinkData *link_next;
826         BLI_Iterator scene_collection_iter;
827 } SceneObjectsIteratorData;
828
829 void BKE_scene_objects_iterator_begin(BLI_Iterator *iter, void *data_in)
830 {
831         Scene *scene = data_in;
832         SceneObjectsIteratorData *data = MEM_callocN(sizeof(SceneObjectsIteratorData), __func__);
833         iter->data = data;
834
835         /* lookup list ot make sure each object is object called once */
836         data->visited = BLI_gset_ptr_new(__func__);
837
838         /* we wrap the scenecollection iterator here to go over the scene collections */
839         BKE_scene_collections_iterator_begin(&data->scene_collection_iter, scene);
840
841         SceneCollection *sc = data->scene_collection_iter.current;
842         if (sc->objects.first != NULL) {
843                 iter->current = ((LinkData *)sc->objects.first)->data;
844         }
845         else {
846                 BKE_scene_objects_iterator_next(iter);
847         }
848 }
849
850 /**
851  * Gets the first unique object in the sequence
852  */
853 static LinkData *object_base_unique(GSet *gs, LinkData *link)
854 {
855         for (; link != NULL; link = link->next) {
856                 Object *ob = link->data;
857                 void **ob_key_p;
858                 if (!BLI_gset_ensure_p_ex(gs, ob, &ob_key_p)) {
859                         *ob_key_p = ob;
860                         return link;
861                 }
862         }
863         return NULL;
864 }
865
866 void BKE_scene_objects_iterator_next(BLI_Iterator *iter)
867 {
868         SceneObjectsIteratorData *data = iter->data;
869         LinkData *link = data->link_next ? object_base_unique(data->visited, data->link_next) : NULL;
870
871         if (link) {
872                 data->link_next = link->next;
873                 iter->current = link->data;
874         }
875         else {
876                 /* if this is the last object of this ListBase look at the next SceneCollection */
877                 SceneCollection *sc;
878                 BKE_scene_collections_iterator_next(&data->scene_collection_iter);
879                 do {
880                         sc = data->scene_collection_iter.current;
881                         /* get the first unique object of this collection */
882                         LinkData *new_link = object_base_unique(data->visited, sc->objects.first);
883                         if (new_link) {
884                                 data->link_next = new_link->next;
885                                 iter->current = new_link->data;
886                                 return;
887                         }
888                         BKE_scene_collections_iterator_next(&data->scene_collection_iter);
889                 } while (data->scene_collection_iter.valid);
890
891                 if (!data->scene_collection_iter.valid) {
892                         iter->valid = false;
893                 }
894         }
895 }
896
897 void BKE_scene_objects_iterator_end(BLI_Iterator *iter)
898 {
899         SceneObjectsIteratorData *data = iter->data;
900         if (data) {
901                 BKE_scene_collections_iterator_end(&data->scene_collection_iter);
902                 BLI_gset_free(data->visited, NULL);
903                 MEM_freeN(data);
904         }
905 }