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