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