Gizmo: multi-object pose-mode gizmo positioning
[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 "BLI_threads.h"
35 #include "BLT_translation.h"
36 #include "BLI_string_utils.h"
37
38 #include "BKE_collection.h"
39 #include "BKE_icons.h"
40 #include "BKE_idprop.h"
41 #include "BKE_layer.h"
42 #include "BKE_library.h"
43 #include "BKE_main.h"
44 #include "BKE_object.h"
45 #include "BKE_rigidbody.h"
46 #include "BKE_scene.h"
47
48 #include "DNA_ID.h"
49 #include "DNA_collection_types.h"
50 #include "DNA_layer_types.h"
51 #include "DNA_object_types.h"
52 #include "DNA_scene_types.h"
53
54 #include "DEG_depsgraph.h"
55 #include "DEG_depsgraph_query.h"
56
57 #include "MEM_guardedalloc.h"
58
59 /******************************** Prototypes ********************************/
60
61 static bool collection_child_add(Collection *parent, Collection *collection, const int flag, const bool add_us);
62 static bool collection_child_remove(Collection *parent, Collection *collection);
63 static bool collection_object_add(Main *bmain, Collection *collection, Object *ob, int flag, const bool add_us);
64 static bool collection_object_remove(Main *bmain, Collection *collection, Object *ob, const bool free_us);
65
66 static CollectionChild *collection_find_child(Collection *parent, Collection *collection);
67 static CollectionParent *collection_find_parent(Collection *child, Collection *collection);
68
69 static bool collection_find_child_recursive(Collection *parent, Collection *collection);
70
71 /***************************** Add Collection *******************************/
72
73 /* Add new collection, without view layer syncing. */
74 static Collection *collection_add(Main *bmain, Collection *collection_parent, const char *name_custom)
75 {
76         /* Determine new collection name. */
77         char name[MAX_NAME];
78
79         if (name_custom) {
80                 STRNCPY(name, name_custom);
81         }
82         else {
83                 BKE_collection_new_name_get(collection_parent, name);
84         }
85
86         /* Create new collection. */
87         Collection *collection = BKE_libblock_alloc(bmain, ID_GR, name, 0);
88
89         /* We increase collection user count when linking to Collections. */
90         id_us_min(&collection->id);
91
92         /* Optionally add to parent collection. */
93         if (collection_parent) {
94                 collection_child_add(collection_parent, collection, 0, true);
95         }
96
97         return collection;
98 }
99
100 /**
101  * Add a collection to a collection ListBase and synchronize all render layers
102  * The ListBase is NULL when the collection is to be added to the master collection
103  */
104 Collection *BKE_collection_add(Main *bmain, Collection *collection_parent, const char *name_custom)
105 {
106         Collection *collection = collection_add(bmain, collection_parent, name_custom);
107         BKE_main_collection_sync(bmain);
108         return collection;
109 }
110
111 /*********************** Free and Delete Collection ****************************/
112
113 /** Free (or release) any data used by this collection (does not free the collection itself). */
114 void BKE_collection_free(Collection *collection)
115 {
116         /* No animdata here. */
117         BKE_previewimg_free(&collection->preview);
118
119         BLI_freelistN(&collection->gobject);
120         BLI_freelistN(&collection->children);
121         BLI_freelistN(&collection->parents);
122
123         BKE_collection_object_cache_free(collection);
124 }
125
126 /**
127  * Remove a collection, optionally removing its child objects or moving
128  * them to parent collections.
129  */
130 bool BKE_collection_delete(Main *bmain, Collection *collection, bool hierarchy)
131 {
132         /* Master collection is not real datablock, can't be removed. */
133         if (collection->flag & COLLECTION_IS_MASTER) {
134                 BLI_assert(!"Scene master collection can't be deleted");
135                 return false;
136         }
137
138         if (hierarchy) {
139                 /* Remove child objects. */
140                 CollectionObject *cob = collection->gobject.first;
141                 while (cob != NULL) {
142                         collection_object_remove(bmain, collection, cob->ob, true);
143                         cob = collection->gobject.first;
144                 }
145
146                 /* Delete all child collections recursively. */
147                 CollectionChild *child = collection->children.first;
148                 while (child != NULL) {
149                         BKE_collection_delete(bmain, child->collection, hierarchy);
150                         child = collection->children.first;
151                 }
152         }
153         else {
154                 /* Link child collections into parent collection. */
155                 for (CollectionChild *child = collection->children.first; child; child = child->next) {
156                         for (CollectionParent *cparent = collection->parents.first; cparent; cparent = cparent->next) {
157                                 Collection *parent = cparent->collection;
158                                 collection_child_add(parent, child->collection, 0, true);
159                         }
160                 }
161
162                 CollectionObject *cob = collection->gobject.first;
163                 while (cob != NULL) {
164                         /* Link child object into parent collections. */
165                         for (CollectionParent *cparent = collection->parents.first; cparent; cparent = cparent->next) {
166                                 Collection *parent = cparent->collection;
167                                 collection_object_add(bmain, parent, cob->ob, 0, true);
168                         }
169
170                         /* Remove child object. */
171                         collection_object_remove(bmain, collection, cob->ob, true);
172                         cob = collection->gobject.first;
173                 }
174         }
175
176         BKE_libblock_delete(bmain, collection);
177
178         BKE_main_collection_sync(bmain);
179
180         return true;
181 }
182
183 /***************************** Collection Copy *******************************/
184
185 /**
186  * Only copy internal data of Collection ID from source to already allocated/initialized destination.
187  * You probably nerver want to use that directly, use id_copy or BKE_id_copy_ex for typical needs.
188  *
189  * WARNING! This function will not handle ID user count!
190  *
191  * \param flag: Copying options (see BKE_library.h's LIB_ID_COPY_... flags for more).
192  */
193 void BKE_collection_copy_data(
194         Main *bmain, Collection *collection_dst, const Collection *collection_src, const int flag)
195 {
196         /* Do not copy collection's preview (same behavior as for objects). */
197         if ((flag & LIB_ID_COPY_NO_PREVIEW) == 0 && false) {  /* XXX TODO temp hack */
198                 BKE_previewimg_id_copy(&collection_dst->id, &collection_src->id);
199         }
200         else {
201                 collection_dst->preview = NULL;
202         }
203
204         collection_dst->flag &= ~COLLECTION_HAS_OBJECT_CACHE;
205         BLI_listbase_clear(&collection_dst->object_cache);
206
207         BLI_listbase_clear(&collection_dst->gobject);
208         BLI_listbase_clear(&collection_dst->children);
209         BLI_listbase_clear(&collection_dst->parents);
210
211         for (CollectionChild *child = collection_src->children.first; child; child = child->next) {
212                 collection_child_add(collection_dst, child->collection, flag, false);
213         }
214         for (CollectionObject *cob = collection_src->gobject.first; cob; cob = cob->next) {
215                 collection_object_add(bmain, collection_dst, cob->ob, flag, false);
216         }
217 }
218
219 /**
220  * Makes a shallow copy of a Collection
221  *
222  * Add a new collection in the same level as the old one, copy any nested collections
223  * but link the objects to the new collection (as oppose to copy them).
224  */
225 Collection *BKE_collection_copy(Main *bmain, Collection *parent, Collection *collection)
226 {
227         /* It's not allowed to copy the master collection. */
228         if (collection->flag & COLLECTION_IS_MASTER) {
229                 BLI_assert("!Master collection can't be copied");
230                 return NULL;
231         }
232
233         Collection *collection_new;
234         BKE_id_copy_ex(bmain, &collection->id, (ID **)&collection_new, 0, false);
235         id_us_min(&collection_new->id);  /* Copying add one user by default, need to get rid of that one. */
236
237         /* Optionally add to parent. */
238         if (parent) {
239                 if (collection_child_add(parent, collection_new, 0, true)) {
240                         /* Put collection right after existing one. */
241                         CollectionChild *child = collection_find_child(parent, collection);
242                         CollectionChild *child_new = collection_find_child(parent, collection_new);
243
244                         if (child && child_new) {
245                                 BLI_remlink(&parent->children, child_new);
246                                 BLI_insertlinkafter(&parent->children, child, child_new);
247                         }
248                 }
249         }
250
251         BKE_main_collection_sync(bmain);
252
253         return collection_new;
254 }
255
256 Collection *BKE_collection_copy_master(Main *bmain, Collection *collection, const int flag)
257 {
258         BLI_assert(collection->flag & COLLECTION_IS_MASTER);
259
260         Collection *collection_dst = MEM_dupallocN(collection);
261         BKE_collection_copy_data(bmain, collection_dst, collection, flag);
262         return collection_dst;
263 }
264
265 void BKE_collection_copy_full(Main *UNUSED(bmain), Collection *UNUSED(collection))
266 {
267         // TODO: implement full scene copy
268 }
269
270 void BKE_collection_make_local(Main *bmain, Collection *collection, const bool lib_local)
271 {
272         BKE_id_make_local_generic(bmain, &collection->id, true, lib_local);
273 }
274
275 /********************************* Naming *******************************/
276
277 /**
278  * The automatic/fallback name of a new collection.
279  */
280 void BKE_collection_new_name_get(Collection *collection_parent, char *rname)
281 {
282         char *name;
283
284         if (!collection_parent) {
285                 name = BLI_sprintfN("Collection");
286         }
287         else if (collection_parent->flag & COLLECTION_IS_MASTER) {
288                 name = BLI_sprintfN("Collection %d", BLI_listbase_count(&collection_parent->children) + 1);
289         }
290         else {
291                 const int number = BLI_listbase_count(&collection_parent->children) + 1;
292                 const int digits = integer_digits_i(number);
293                 const int max_len =
294                         sizeof(collection_parent->id.name) - 1 /* NULL terminator */ - (1 + digits) /* " %d" */ - 2 /* ID */;
295                 name = BLI_sprintfN("%.*s %d", max_len, collection_parent->id.name + 2, number);
296         }
297
298         BLI_strncpy(rname, name, MAX_NAME);
299         MEM_freeN(name);
300 }
301
302 /**
303  * The name to show in the interface.
304  */
305 const char *BKE_collection_ui_name_get(struct Collection *collection)
306 {
307         if (collection->flag & COLLECTION_IS_MASTER) {
308                 return IFACE_("Scene Collection");
309         }
310         else {
311                 return collection->id.name + 2;
312         }
313 }
314
315 /* **************** Object List Cache *******************/
316
317 static void collection_object_cache_fill(ListBase *lb, Collection *collection, int parent_restrict)
318 {
319         int child_restrict = collection->flag | parent_restrict;
320
321         for (CollectionObject *cob = collection->gobject.first; cob; cob = cob->next) {
322                 Base *base = BLI_findptr(lb, cob->ob, offsetof(Base, object));
323
324                 if (base == NULL) {
325                         base = MEM_callocN(sizeof(Base), "Object Base");
326                         base->object = cob->ob;
327                         BLI_addtail(lb, base);
328                 }
329
330                 int object_restrict = base->object->restrictflag;
331
332                 if (((child_restrict & COLLECTION_RESTRICT_VIEW) == 0) &&
333                     ((object_restrict & OB_RESTRICT_VIEW) == 0))
334                 {
335                         base->flag |= BASE_ENABLED_VIEWPORT;
336                 }
337
338                 if (((child_restrict & COLLECTION_RESTRICT_RENDER) == 0) &&
339                     ((object_restrict & OB_RESTRICT_RENDER) == 0))
340                 {
341                         base->flag |= BASE_ENABLED_RENDER;
342                 }
343         }
344
345         for (CollectionChild *child = collection->children.first; child; child = child->next) {
346                 collection_object_cache_fill(lb, child->collection, child_restrict);
347         }
348 }
349
350 ListBase BKE_collection_object_cache_get(Collection *collection)
351 {
352         if (!(collection->flag & COLLECTION_HAS_OBJECT_CACHE)) {
353                 static ThreadMutex cache_lock = BLI_MUTEX_INITIALIZER;
354
355                 BLI_mutex_lock(&cache_lock);
356                 if (!(collection->flag & COLLECTION_HAS_OBJECT_CACHE)) {
357                         collection_object_cache_fill(&collection->object_cache, collection, 0);
358                         collection->flag |= COLLECTION_HAS_OBJECT_CACHE;
359                 }
360                 BLI_mutex_unlock(&cache_lock);
361         }
362
363         return collection->object_cache;
364 }
365
366 static void collection_object_cache_free(Collection *collection)
367 {
368         /* Clear own cache an for all parents, since those are affected by changes as well. */
369         collection->flag &= ~COLLECTION_HAS_OBJECT_CACHE;
370         BLI_freelistN(&collection->object_cache);
371
372         for (CollectionParent *parent = collection->parents.first; parent; parent = parent->next) {
373                 collection_object_cache_free(parent->collection);
374         }
375 }
376
377 void BKE_collection_object_cache_free(Collection *collection)
378 {
379         collection_object_cache_free(collection);
380 }
381
382 Base *BKE_collection_or_layer_objects(const ViewLayer *view_layer, Collection *collection)
383 {
384         if (collection) {
385                 return BKE_collection_object_cache_get(collection).first;
386         }
387         else {
388                 return FIRSTBASE(view_layer);
389         }
390 }
391
392 /*********************** Scene Master Collection ***************/
393
394 Collection *BKE_collection_master_add()
395 {
396         /* Not an actual datablock, but owned by scene. */
397         Collection *master_collection = MEM_callocN(sizeof(Collection), "Master Collection");
398         STRNCPY(master_collection->id.name, "GRMaster Collection");
399         master_collection->flag |= COLLECTION_IS_MASTER;
400         return master_collection;
401 }
402
403 Collection *BKE_collection_master(const Scene *scene)
404 {
405         return scene->master_collection;
406 }
407
408 /*********************** Cyclic Checks ************************/
409
410 static bool collection_object_cyclic_check_internal(Object *object, Collection *collection)
411 {
412         if (object->dup_group) {
413                 Collection *dup_collection = object->dup_group;
414                 if ((dup_collection->id.tag & LIB_TAG_DOIT) == 0) {
415                         /* Cycle already exists in collections, let's prevent further crappyness */
416                         return true;
417                 }
418                 /* flag the object to identify cyclic dependencies in further dupli collections */
419                 dup_collection->id.tag &= ~LIB_TAG_DOIT;
420
421                 if (dup_collection == collection) {
422                         return true;
423                 }
424                 else {
425                         FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN(dup_collection, collection_object)
426                         {
427                                 if (collection_object_cyclic_check_internal(collection_object, dup_collection)) {
428                                         return true;
429                                 }
430                         }
431                         FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
432                 }
433
434                 /* un-flag the object, it's allowed to have the same collection multiple times in parallel */
435                 dup_collection->id.tag |= LIB_TAG_DOIT;
436         }
437
438         return false;
439 }
440
441 bool BKE_collection_object_cyclic_check(Main *bmain, Object *object, Collection *collection)
442 {
443         /* first flag all collections */
444         BKE_main_id_tag_listbase(&bmain->collection, LIB_TAG_DOIT, true);
445
446         return collection_object_cyclic_check_internal(object, collection);
447 }
448
449 /******************* Collection Object Membership *******************/
450
451 bool BKE_collection_has_object(Collection *collection, Object *ob)
452 {
453         if (ELEM(NULL, collection, ob)) {
454                 return false;
455         }
456
457         return (BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob)));
458 }
459
460 bool BKE_collection_has_object_recursive(Collection *collection, Object *ob)
461 {
462         if (ELEM(NULL, collection, ob)) {
463                 return false;
464         }
465
466         const ListBase objects = BKE_collection_object_cache_get(collection);
467         return (BLI_findptr(&objects, ob, offsetof(Base, object)));
468 }
469
470 Collection *BKE_collection_object_find(Main *bmain, Collection *collection, Object *ob)
471 {
472         if (collection)
473                 collection = collection->id.next;
474         else
475                 collection = bmain->collection.first;
476
477         while (collection) {
478                 if (BKE_collection_has_object(collection, ob))
479                         return collection;
480                 collection = collection->id.next;
481         }
482         return NULL;
483 }
484
485 bool BKE_collection_is_empty(Collection *collection)
486 {
487         return BLI_listbase_is_empty(&collection->gobject) && BLI_listbase_is_empty(&collection->children);
488 }
489
490 /********************** Collection Objects *********************/
491
492 static bool collection_object_add(Main *bmain, Collection *collection, Object *ob, int flag, const bool add_us)
493 {
494         if (ob->dup_group) {
495                 /* Cyclic dependency check. */
496                 if (collection_find_child_recursive(ob->dup_group, collection)) {
497                         return false;
498                 }
499         }
500
501         CollectionObject *cob = BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob));
502         if (cob) {
503                 return false;
504         }
505
506         cob = MEM_callocN(sizeof(CollectionObject), __func__);
507         cob->ob = ob;
508         BLI_addtail(&collection->gobject, cob);
509         BKE_collection_object_cache_free(collection);
510
511         if (add_us && (flag & LIB_ID_CREATE_NO_USER_REFCOUNT) == 0) {
512                 id_us_plus(&ob->id);
513         }
514
515         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
516                 DEG_id_tag_update_ex(bmain, &collection->id, ID_RECALC_COPY_ON_WRITE);
517         }
518
519         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
520 #ifdef WITH_BULLET
521                 BKE_rigidbody_main_collection_object_add(bmain, collection, ob);
522 #endif
523         }
524
525         return true;
526 }
527
528 static bool collection_object_remove(Main *bmain, Collection *collection, Object *ob, const bool free_us)
529 {
530         CollectionObject *cob = BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob));
531         if (cob == NULL) {
532                 return false;
533         }
534
535         BLI_freelinkN(&collection->gobject, cob);
536         BKE_collection_object_cache_free(collection);
537
538         if (free_us) {
539                 BKE_libblock_free_us(bmain, ob);
540         }
541         else {
542                 id_us_min(&ob->id);
543         }
544
545         DEG_id_tag_update_ex(bmain, &collection->id, ID_RECALC_COPY_ON_WRITE);
546
547         return true;
548 }
549
550 /**
551  * Add object to collection
552  */
553 bool BKE_collection_object_add(Main *bmain, Collection *collection, Object *ob)
554 {
555         if (ELEM(NULL, collection, ob)) {
556                 return false;
557         }
558
559         if (!collection_object_add(bmain, collection, ob, 0, true)) {
560                 return false;
561         }
562
563         if (BKE_collection_is_in_scene(collection)) {
564                 BKE_main_collection_sync(bmain);
565         }
566
567         return true;
568 }
569
570 /**
571  * Add object to all scene collections that reference objects is in
572  * (used to copy objects)
573  */
574 void BKE_collection_object_add_from(Main *bmain, Scene *scene, Object *ob_src, Object *ob_dst)
575 {
576         FOREACH_SCENE_COLLECTION_BEGIN(scene, collection)
577         {
578                 if (BKE_collection_has_object(collection, ob_src)) {
579                         collection_object_add(bmain, collection, ob_dst, 0, true);
580                 }
581         }
582         FOREACH_SCENE_COLLECTION_END;
583
584         BKE_main_collection_sync(bmain);
585 }
586
587 /**
588  * Remove object from collection.
589  */
590 bool BKE_collection_object_remove(Main *bmain, Collection *collection, Object *ob, const bool free_us)
591 {
592         if (ELEM(NULL, collection, ob)) {
593                 return false;
594         }
595
596         if (!collection_object_remove(bmain, collection, ob, free_us)) {
597                 return false;
598         }
599
600         if (BKE_collection_is_in_scene(collection)) {
601                 BKE_main_collection_sync(bmain);
602         }
603
604         return true;
605 }
606
607 /**
608  * Remove object from all collections of scene
609  * \param scene_collection_skip: Don't remove base from this collection.
610  */
611 static bool scene_collections_object_remove(Main *bmain, Scene *scene, Object *ob, const bool free_us,
612                                       Collection *collection_skip)
613 {
614         bool removed = false;
615
616         BKE_scene_remove_rigidbody_object(bmain, scene, ob);
617
618         FOREACH_SCENE_COLLECTION_BEGIN(scene, collection)
619         {
620                 if (collection != collection_skip) {
621                         removed |= collection_object_remove(bmain, collection, ob, free_us);
622                 }
623         }
624         FOREACH_SCENE_COLLECTION_END;
625
626         BKE_main_collection_sync(bmain);
627
628         return removed;
629 }
630
631 /**
632  * Remove object from all collections of scene
633  */
634 bool BKE_scene_collections_object_remove(Main *bmain, Scene *scene, Object *ob, const bool free_us)
635 {
636         return scene_collections_object_remove(bmain, scene, ob, free_us, NULL);
637 }
638
639 /*
640  * Remove all NULL objects from collections.
641  * This is used for library remapping, where these pointers have been set to NULL.
642  * Otherwise this should never happen.
643  */
644 static void collection_object_remove_nulls(Collection *collection)
645 {
646         bool changed = false;
647
648         for (CollectionObject *cob = collection->gobject.first, *cob_next = NULL; cob; cob = cob_next) {
649                 cob_next = cob->next;
650
651                 if (cob->ob == NULL) {
652                         BLI_freelinkN(&collection->gobject, cob);
653                         changed = true;
654                 }
655         }
656
657         if (changed) {
658                 BKE_collection_object_cache_free(collection);
659         }
660 }
661
662 void BKE_collections_object_remove_nulls(Main *bmain)
663 {
664         for (Scene *scene = bmain->scene.first; scene; scene = scene->id.next) {
665                 collection_object_remove_nulls(scene->master_collection);
666         }
667
668         for (Collection *collection = bmain->collection.first; collection; collection = collection->id.next) {
669                 collection_object_remove_nulls(collection);
670         }
671 }
672
673 static void collection_null_children_remove(Collection *collection)
674 {
675         for (CollectionChild *child = collection->children.first, *child_next = NULL; child; child = child_next) {
676                 child_next = child->next;
677
678                 if (child->collection == NULL) {
679                         BLI_freelinkN(&collection->children, child);
680                 }
681         }
682 }
683
684 static void collection_missing_parents_remove(Collection *collection)
685 {
686         for (CollectionParent *parent = collection->parents.first, *parent_next; parent != NULL; parent = parent_next) {
687                 parent_next = parent->next;
688
689                 if (!collection_find_child(parent->collection, collection)) {
690                         BLI_freelinkN(&collection->parents, parent);
691                 }
692         }
693 }
694
695 /**
696  * Remove all NULL children from parent collections of changed \a collection.
697  * This is used for library remapping, where these pointers have been set to NULL.
698  * Otherwise this should never happen.
699  *
700  * \note caller must ensure BKE_main_collection_sync_remap() is called afterwards!
701  *
702  * \param collection: may be \a NULL, in which case whole \a bmain database of collections is checked.
703  */
704 void BKE_collections_child_remove_nulls(Main *bmain, Collection *collection)
705 {
706         if (collection == NULL) {
707                 /* We need to do the checks in two steps when more than one collection may be involved,
708                  * otherwise we can miss some cases...
709                  * Also, master collections are not in bmain, so we also need to loop over scenes.
710                  */
711                 for (collection = bmain->collection.first; collection != NULL; collection = collection->id.next) {
712                         collection_null_children_remove(collection);
713                 }
714                 for (Scene *scene = bmain->scene.first; scene != NULL; scene = scene->id.next) {
715                         collection_null_children_remove(BKE_collection_master(scene));
716                 }
717
718                 for (collection = bmain->collection.first; collection != NULL; collection = collection->id.next) {
719                         collection_missing_parents_remove(collection);
720                 }
721                 for (Scene *scene = bmain->scene.first; scene != NULL; scene = scene->id.next) {
722                         collection_missing_parents_remove(BKE_collection_master(scene));
723                 }
724         }
725         else {
726                 for (CollectionParent *parent = collection->parents.first, *parent_next; parent; parent = parent_next) {
727                         parent_next = parent->next;
728
729                         collection_null_children_remove(parent->collection);
730
731                         if (!collection_find_child(parent->collection, collection)) {
732                                 BLI_freelinkN(&collection->parents, parent);
733                         }
734                 }
735         }
736 }
737
738 /**
739  * Move object from a collection into another
740  *
741  * If source collection is NULL move it from all the existing collections.
742  */
743 void BKE_collection_object_move(
744         Main *bmain, Scene *scene, Collection *collection_dst, Collection *collection_src, Object *ob)
745 {
746         /* In both cases we first add the object, then remove it from the other collections.
747          * Otherwise we lose the original base and whether it was active and selected. */
748         if (collection_src != NULL) {
749                 if (BKE_collection_object_add(bmain, collection_dst, ob)) {
750                         BKE_collection_object_remove(bmain, collection_src, ob, false);
751                 }
752         }
753         else {
754                 /* Adding will fail if object is already in collection.
755                  * However we still need to remove it from the other collections. */
756                 BKE_collection_object_add(bmain, collection_dst, ob);
757                 scene_collections_object_remove(bmain, scene, ob, false, collection_dst);
758         }
759 }
760
761 /***************** Collection Scene Membership ****************/
762
763 bool BKE_collection_is_in_scene(Collection *collection)
764 {
765         if (collection->flag & COLLECTION_IS_MASTER) {
766                 return true;
767         }
768
769         for (CollectionParent *cparent = collection->parents.first; cparent; cparent = cparent->next) {
770                 if (BKE_collection_is_in_scene(cparent->collection)) {
771                         return true;
772                 }
773         }
774
775         return false;
776 }
777
778 void BKE_collections_after_lib_link(Main *bmain)
779 {
780         /* Update view layer collections to match any changes in linked
781          * collections after file load. */
782         BKE_main_collection_sync(bmain);
783 }
784
785 /********************** Collection Children *******************/
786
787 bool BKE_collection_find_cycle(Collection *new_ancestor, Collection *collection)
788 {
789         if (collection == new_ancestor) {
790                 return true;
791         }
792
793         for (CollectionParent *parent = new_ancestor->parents.first; parent; parent = parent->next) {
794                 if (BKE_collection_find_cycle(parent->collection, collection)) {
795                         return true;
796                 }
797         }
798
799         return false;
800 }
801
802 static CollectionChild *collection_find_child(Collection *parent, Collection *collection)
803 {
804         return BLI_findptr(&parent->children, collection, offsetof(CollectionChild, collection));
805 }
806
807 static bool collection_find_child_recursive(Collection *parent, Collection *collection)
808 {
809         for (CollectionChild *child = parent->children.first; child; child = child->next) {
810                 if (child->collection == collection) {
811                         return true;
812                 }
813
814                 if (collection_find_child_recursive(child->collection, collection)) {
815                         return true;
816                 }
817         }
818
819         return false;
820 }
821
822 static CollectionParent *collection_find_parent(Collection *child, Collection *collection)
823 {
824         return BLI_findptr(&child->parents, collection, offsetof(CollectionParent, collection));
825 }
826
827 static bool collection_child_add(Collection *parent, Collection *collection, const int flag, const bool add_us)
828 {
829         CollectionChild *child = collection_find_child(parent, collection);
830         if (child) {
831                 return false;
832         }
833         if (BKE_collection_find_cycle(parent, collection)) {
834                 return false;
835         }
836
837         child = MEM_callocN(sizeof(CollectionChild), "CollectionChild");
838         child->collection = collection;
839         BLI_addtail(&parent->children, child);
840
841         /* Don't add parent links for depsgraph datablocks, these are not kept in sync. */
842         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
843                 CollectionParent *cparent = MEM_callocN(sizeof(CollectionParent), "CollectionParent");
844                 cparent->collection = parent;
845                 BLI_addtail(&collection->parents, cparent);
846         }
847
848         if (add_us) {
849                 id_us_plus(&collection->id);
850         }
851
852         BKE_collection_object_cache_free(parent);
853
854         return true;
855 }
856
857 static bool collection_child_remove(Collection *parent, Collection *collection)
858 {
859         CollectionChild *child = collection_find_child(parent, collection);
860         if (child == NULL) {
861                 return false;
862         }
863
864         CollectionParent *cparent = collection_find_parent(collection, parent);
865         BLI_freelinkN(&collection->parents, cparent);
866         BLI_freelinkN(&parent->children, child);
867
868         id_us_min(&collection->id);
869
870         BKE_collection_object_cache_free(parent);
871
872         return true;
873 }
874
875 bool BKE_collection_child_add(Main *bmain, Collection *parent, Collection *child)
876 {
877         if (!collection_child_add(parent, child, 0, true)) {
878                 return false;
879         }
880
881         BKE_main_collection_sync(bmain);
882         return true;
883 }
884
885 bool BKE_collection_child_remove(Main *bmain, Collection *parent, Collection *child)
886 {
887         if (!collection_child_remove(parent, child)) {
888                 return false;
889         }
890
891         BKE_main_collection_sync(bmain);
892         return true;
893 }
894
895 /********************** Collection index *********************/
896
897 static Collection *collection_from_index_recursive(Collection *collection, const int index, int *index_current)
898 {
899         if (index == (*index_current)) {
900                 return collection;
901         }
902
903         (*index_current)++;
904
905         for (CollectionChild *child = collection->children.first; child; child = child->next) {
906                 Collection *nested = collection_from_index_recursive(child->collection, index, index_current);
907                 if (nested != NULL) {
908                         return nested;
909                 }
910         }
911         return NULL;
912 }
913
914 /**
915  * Return Scene Collection for a given index.
916  *
917  * The index is calculated from top to bottom counting the children before the siblings.
918  */
919 Collection *BKE_collection_from_index(Scene *scene, const int index)
920 {
921         int index_current = 0;
922         Collection *master_collection = BKE_collection_master(scene);
923         return collection_from_index_recursive(master_collection, index, &index_current);
924 }
925
926 static bool collection_objects_select(ViewLayer *view_layer, Collection *collection, bool deselect)
927 {
928         bool changed = false;
929
930         if (collection->flag & COLLECTION_RESTRICT_SELECT) {
931                 return false;
932         }
933
934         for (CollectionObject *cob = collection->gobject.first; cob; cob = cob->next) {
935                 Base *base = BKE_view_layer_base_find(view_layer, cob->ob);
936
937                 if (base) {
938                         if (deselect) {
939                                 if (base->flag & BASE_SELECTED) {
940                                         base->flag &= ~BASE_SELECTED;
941                                         changed = true;
942                                 }
943                         }
944                         else {
945                                 if ((base->flag & BASE_SELECTABLE) && !(base->flag & BASE_SELECTED)) {
946                                         base->flag |= BASE_SELECTED;
947                                         changed = true;
948                                 }
949                         }
950                 }
951         }
952
953         for (CollectionChild *child = collection->children.first; child; child = child->next) {
954                 if (collection_objects_select(view_layer, collection, deselect)) {
955                         changed = true;
956                 }
957         }
958
959         return changed;
960 }
961
962 /**
963  * Select all the objects in this Collection (and its nested collections) for this ViewLayer.
964  * Return true if any object was selected.
965  */
966 bool BKE_collection_objects_select(ViewLayer *view_layer, Collection *collection, bool deselect)
967 {
968         LayerCollection *layer_collection = BKE_layer_collection_first_from_scene_collection(view_layer, collection);
969
970         if (layer_collection != NULL) {
971                 return BKE_layer_collection_objects_select(view_layer, layer_collection, deselect);
972         }
973         else {
974                 return collection_objects_select(view_layer, collection, deselect);
975         }
976 }
977
978 /***************** Collection move (outliner drag & drop) *********************/
979
980 bool BKE_collection_move(Main *bmain,
981                          Collection *to_parent,
982                          Collection *from_parent,
983                          Collection *relative,
984                          bool relative_after,
985                          Collection *collection)
986 {
987         if (collection->flag & COLLECTION_IS_MASTER) {
988                 return false;
989         }
990         if (BKE_collection_find_cycle(to_parent, collection)) {
991                 return false;
992         }
993
994         /* Move to new parent collection */
995         if (from_parent) {
996                 collection_child_remove(from_parent, collection);
997         }
998
999         collection_child_add(to_parent, collection, 0, true);
1000
1001         /* Move to specified location under parent. */
1002         if (relative) {
1003                 CollectionChild *child = collection_find_child(to_parent, collection);
1004                 CollectionChild *relative_child = collection_find_child(to_parent, relative);
1005
1006                 if (relative_child) {
1007                         BLI_remlink(&to_parent->children, child);
1008
1009                         if (relative_after) {
1010                                 BLI_insertlinkafter(&to_parent->children, relative_child, child);
1011                         }
1012                         else {
1013                                 BLI_insertlinkbefore(&to_parent->children, relative_child, child);
1014                         }
1015
1016                         BKE_collection_object_cache_free(to_parent);
1017                 }
1018         }
1019
1020         BKE_main_collection_sync(bmain);
1021
1022         return true;
1023 }
1024
1025 /**************************** Iterators ******************************/
1026
1027 /* scene collection iteractor */
1028
1029 typedef struct CollectionsIteratorData {
1030         Scene *scene;
1031         void **array;
1032         int tot, cur;
1033 } CollectionsIteratorData;
1034
1035 static void scene_collection_callback(Collection *collection, BKE_scene_collections_Cb callback, void *data)
1036 {
1037         callback(collection, data);
1038
1039         for (CollectionChild *child = collection->children.first; child; child = child->next) {
1040                 scene_collection_callback(child->collection, callback, data);
1041         }
1042 }
1043
1044 static void scene_collections_count(Collection *UNUSED(collection), void *data)
1045 {
1046         int *tot = data;
1047         (*tot)++;
1048 }
1049
1050 static void scene_collections_build_array(Collection *collection, void *data)
1051 {
1052         Collection ***array = data;
1053         **array = collection;
1054         (*array)++;
1055 }
1056
1057 static void scene_collections_array(Scene *scene, Collection ***collections_array, int *tot)
1058 {
1059         Collection *collection;
1060         Collection **array;
1061
1062         *collections_array = NULL;
1063         *tot = 0;
1064
1065         if (scene == NULL) {
1066                 return;
1067         }
1068
1069         collection = BKE_collection_master(scene);
1070         BLI_assert(collection != NULL);
1071         scene_collection_callback(collection, scene_collections_count, tot);
1072
1073         if (*tot == 0)
1074                 return;
1075
1076         *collections_array = array = MEM_mallocN(sizeof(Collection *) * (*tot), "CollectionArray");
1077         scene_collection_callback(collection, scene_collections_build_array, &array);
1078 }
1079
1080 /**
1081  * Only use this in non-performance critical situations
1082  * (it iterates over all scene collections twice)
1083  */
1084 void BKE_scene_collections_iterator_begin(BLI_Iterator *iter, void *data_in)
1085 {
1086         Scene *scene = data_in;
1087         CollectionsIteratorData *data = MEM_callocN(sizeof(CollectionsIteratorData), __func__);
1088
1089         data->scene = scene;
1090         iter->data = data;
1091         iter->valid = true;
1092
1093         scene_collections_array(scene, (Collection ***)&data->array, &data->tot);
1094         BLI_assert(data->tot != 0);
1095
1096         data->cur = 0;
1097         iter->current = data->array[data->cur];
1098 }
1099
1100 void BKE_scene_collections_iterator_next(struct BLI_Iterator *iter)
1101 {
1102         CollectionsIteratorData *data = iter->data;
1103
1104         if (++data->cur < data->tot) {
1105                 iter->current = data->array[data->cur];
1106         }
1107         else {
1108                 iter->valid = false;
1109         }
1110 }
1111
1112 void BKE_scene_collections_iterator_end(struct BLI_Iterator *iter)
1113 {
1114         CollectionsIteratorData *data = iter->data;
1115
1116         if (data) {
1117                 if (data->array) {
1118                         MEM_freeN(data->array);
1119                 }
1120                 MEM_freeN(data);
1121         }
1122         iter->valid = false;
1123 }
1124
1125
1126 /* scene objects iteractor */
1127
1128 typedef struct SceneObjectsIteratorData {
1129         GSet *visited;
1130         CollectionObject *cob_next;
1131         BLI_Iterator scene_collection_iter;
1132 } SceneObjectsIteratorData;
1133
1134 void BKE_scene_objects_iterator_begin(BLI_Iterator *iter, void *data_in)
1135 {
1136         Scene *scene = data_in;
1137         SceneObjectsIteratorData *data = MEM_callocN(sizeof(SceneObjectsIteratorData), __func__);
1138         iter->data = data;
1139
1140         /* lookup list ot make sure each object is object called once */
1141         data->visited = BLI_gset_ptr_new(__func__);
1142
1143         /* we wrap the scenecollection iterator here to go over the scene collections */
1144         BKE_scene_collections_iterator_begin(&data->scene_collection_iter, scene);
1145
1146         Collection *collection = data->scene_collection_iter.current;
1147         data->cob_next = collection->gobject.first;
1148
1149         BKE_scene_objects_iterator_next(iter);
1150 }
1151
1152 /**
1153  * Ensures we only get each object once, even when included in several collections.
1154  */
1155 static CollectionObject *object_base_unique(GSet *gs, CollectionObject *cob)
1156 {
1157         for (; cob != NULL; cob = cob->next) {
1158                 Object *ob = cob->ob;
1159                 void **ob_key_p;
1160                 if (!BLI_gset_ensure_p_ex(gs, ob, &ob_key_p)) {
1161                         *ob_key_p = ob;
1162                         return cob;
1163                 }
1164         }
1165         return NULL;
1166 }
1167
1168 void BKE_scene_objects_iterator_next(BLI_Iterator *iter)
1169 {
1170         SceneObjectsIteratorData *data = iter->data;
1171         CollectionObject *cob = data->cob_next ? object_base_unique(data->visited, data->cob_next) : NULL;
1172
1173         if (cob) {
1174                 data->cob_next = cob->next;
1175                 iter->current = cob->ob;
1176         }
1177         else {
1178                 /* if this is the last object of this ListBase look at the next Collection */
1179                 Collection *collection;
1180                 BKE_scene_collections_iterator_next(&data->scene_collection_iter);
1181                 do {
1182                         collection = data->scene_collection_iter.current;
1183                         /* get the first unique object of this collection */
1184                         CollectionObject *new_cob = object_base_unique(data->visited, collection->gobject.first);
1185                         if (new_cob) {
1186                                 data->cob_next = new_cob->next;
1187                                 iter->current = new_cob->ob;
1188                                 return;
1189                         }
1190                         BKE_scene_collections_iterator_next(&data->scene_collection_iter);
1191                 } while (data->scene_collection_iter.valid);
1192
1193                 if (!data->scene_collection_iter.valid) {
1194                         iter->valid = false;
1195                 }
1196         }
1197 }
1198
1199 void BKE_scene_objects_iterator_end(BLI_Iterator *iter)
1200 {
1201         SceneObjectsIteratorData *data = iter->data;
1202         if (data) {
1203                 BKE_scene_collections_iterator_end(&data->scene_collection_iter);
1204                 BLI_gset_free(data->visited, NULL);
1205                 MEM_freeN(data);
1206         }
1207 }