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