Outliner: Collection - Duplicate Hierarchy, and Duplicate Linked Hierarchy
[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 static void collection_duplicate_recursive(Main *bmain, GHash *visited, Collection *collection, const int dupflag)
213 {
214         const bool is_first_run = (visited == NULL);
215         if (is_first_run) {
216                 visited = BLI_ghash_ptr_new(__func__);
217                 BKE_main_id_tag_idcode(bmain, ID_GR, LIB_TAG_DOIT, false);
218         }
219
220         if (collection->id.tag & LIB_TAG_DOIT) {
221                 return;
222         }
223         collection->id.tag |= LIB_TAG_DOIT;
224
225         ListBase collection_object_list = {NULL, NULL};
226         BLI_duplicatelist(&collection_object_list, &collection->gobject);
227         for (CollectionObject *cob = collection_object_list.first; cob; cob = cob->next) {
228                 Object *ob_old = cob->ob;
229                 Object *ob_new = NULL;
230                 void **ob_key_p, **ob_value_p;
231
232                 if (!BLI_ghash_ensure_p_ex(visited, ob_old, &ob_key_p, &ob_value_p)) {
233                         ob_new = BKE_object_duplicate(bmain, ob_old, dupflag);
234                         *ob_key_p = ob_old;
235                         *ob_value_p = ob_new;
236                 }
237                 else {
238                         ob_new = *ob_value_p;
239                 }
240
241                 collection_object_add(bmain, collection, ob_new, 0, true);
242                 collection_object_remove(bmain, collection, ob_old, false);
243         }
244         BLI_freelistN(&collection_object_list);
245
246         ListBase collection_child_list = {NULL, NULL};
247         BLI_duplicatelist(&collection_child_list, &collection->children);
248         for (CollectionChild *child = collection_child_list.first; child; child = child->next) {
249                 Collection *child_collection_old = child->collection;
250                 Collection *child_collection_new = BKE_collection_copy(bmain, collection, child_collection_old);
251
252                 collection_duplicate_recursive(bmain, visited, child_collection_new, dupflag);
253                 collection_child_remove(collection, child_collection_old);
254         }
255         BLI_freelistN(&collection_child_list);
256
257         if (is_first_run) {
258                 BLI_ghash_free(visited, NULL, NULL);
259         }
260 }
261
262 /**
263  * Makes a shallow copy of a Collection
264  *
265  * Add a new collection in the same level as the old one, link any nested collections
266  * and finally link the objects to the new collection (as oppose to copy them).
267  */
268 Collection *BKE_collection_copy(Main *bmain, Collection *parent, Collection *collection)
269 {
270         return BKE_collection_duplicate(bmain, parent, collection, false, false);
271 }
272
273 Collection *BKE_collection_duplicate(Main *bmain, Collection *parent, Collection *collection, const bool do_hierarchy, const bool do_deep_copy)
274 {
275         /* It's not allowed to copy the master collection. */
276         if (collection->flag & COLLECTION_IS_MASTER) {
277                 BLI_assert("!Master collection can't be duplicated");
278                 return NULL;
279         }
280
281         Collection *collection_new;
282         BKE_id_copy(bmain, &collection->id, (ID **)&collection_new);
283         id_us_min(&collection_new->id);  /* Copying add one user by default, need to get rid of that one. */
284
285         /* Optionally add to parent. */
286         if (parent) {
287                 if (collection_child_add(parent, collection_new, 0, true)) {
288                         /* Put collection right after existing one. */
289                         CollectionChild *child = collection_find_child(parent, collection);
290                         CollectionChild *child_new = collection_find_child(parent, collection_new);
291
292                         if (child && child_new) {
293                                 BLI_remlink(&parent->children, child_new);
294                                 BLI_insertlinkafter(&parent->children, child, child_new);
295                         }
296                 }
297         }
298
299         if (do_hierarchy) {
300                 collection_duplicate_recursive(bmain, NULL, collection_new, (do_deep_copy) ? U.dupflag : 0);
301         }
302
303         BKE_main_collection_sync(bmain);
304
305         return collection_new;
306 }
307
308 Collection *BKE_collection_copy_master(Main *bmain, Collection *collection, const int flag)
309 {
310         BLI_assert(collection->flag & COLLECTION_IS_MASTER);
311
312         Collection *collection_dst = MEM_dupallocN(collection);
313         BKE_collection_copy_data(bmain, collection_dst, collection, flag);
314         return collection_dst;
315 }
316
317 void BKE_collection_copy_full(Main *UNUSED(bmain), Collection *UNUSED(collection))
318 {
319         // TODO: implement full scene copy
320 }
321
322 void BKE_collection_make_local(Main *bmain, Collection *collection, const bool lib_local)
323 {
324         BKE_id_make_local_generic(bmain, &collection->id, true, lib_local);
325 }
326
327 /********************************* Naming *******************************/
328
329 /**
330  * The automatic/fallback name of a new collection.
331  */
332 void BKE_collection_new_name_get(Collection *collection_parent, char *rname)
333 {
334         char *name;
335
336         if (!collection_parent) {
337                 name = BLI_sprintfN("Collection");
338         }
339         else if (collection_parent->flag & COLLECTION_IS_MASTER) {
340                 name = BLI_sprintfN("Collection %d", BLI_listbase_count(&collection_parent->children) + 1);
341         }
342         else {
343                 const int number = BLI_listbase_count(&collection_parent->children) + 1;
344                 const int digits = integer_digits_i(number);
345                 const int max_len =
346                         sizeof(collection_parent->id.name) - 1 /* NULL terminator */ - (1 + digits) /* " %d" */ - 2 /* ID */;
347                 name = BLI_sprintfN("%.*s %d", max_len, collection_parent->id.name + 2, number);
348         }
349
350         BLI_strncpy(rname, name, MAX_NAME);
351         MEM_freeN(name);
352 }
353
354 /**
355  * The name to show in the interface.
356  */
357 const char *BKE_collection_ui_name_get(struct Collection *collection)
358 {
359         if (collection->flag & COLLECTION_IS_MASTER) {
360                 return IFACE_("Scene Collection");
361         }
362         else {
363                 return collection->id.name + 2;
364         }
365 }
366
367 /* **************** Object List Cache *******************/
368
369 static void collection_object_cache_fill(ListBase *lb, Collection *collection, int parent_restrict)
370 {
371         int child_restrict = collection->flag | parent_restrict;
372
373         for (CollectionObject *cob = collection->gobject.first; cob; cob = cob->next) {
374                 Base *base = BLI_findptr(lb, cob->ob, offsetof(Base, object));
375
376                 if (base == NULL) {
377                         base = MEM_callocN(sizeof(Base), "Object Base");
378                         base->object = cob->ob;
379                         BLI_addtail(lb, base);
380                 }
381
382                 int object_restrict = base->object->restrictflag;
383
384                 if (((child_restrict & COLLECTION_RESTRICT_VIEW) == 0) &&
385                     ((object_restrict & OB_RESTRICT_VIEW) == 0))
386                 {
387                         base->flag |= BASE_ENABLED_VIEWPORT;
388                 }
389
390                 if (((child_restrict & COLLECTION_RESTRICT_RENDER) == 0) &&
391                     ((object_restrict & OB_RESTRICT_RENDER) == 0))
392                 {
393                         base->flag |= BASE_ENABLED_RENDER;
394                 }
395         }
396
397         for (CollectionChild *child = collection->children.first; child; child = child->next) {
398                 collection_object_cache_fill(lb, child->collection, child_restrict);
399         }
400 }
401
402 ListBase BKE_collection_object_cache_get(Collection *collection)
403 {
404         if (!(collection->flag & COLLECTION_HAS_OBJECT_CACHE)) {
405                 static ThreadMutex cache_lock = BLI_MUTEX_INITIALIZER;
406
407                 BLI_mutex_lock(&cache_lock);
408                 if (!(collection->flag & COLLECTION_HAS_OBJECT_CACHE)) {
409                         collection_object_cache_fill(&collection->object_cache, collection, 0);
410                         collection->flag |= COLLECTION_HAS_OBJECT_CACHE;
411                 }
412                 BLI_mutex_unlock(&cache_lock);
413         }
414
415         return collection->object_cache;
416 }
417
418 static void collection_object_cache_free(Collection *collection)
419 {
420         /* Clear own cache an for all parents, since those are affected by changes as well. */
421         collection->flag &= ~COLLECTION_HAS_OBJECT_CACHE;
422         BLI_freelistN(&collection->object_cache);
423
424         for (CollectionParent *parent = collection->parents.first; parent; parent = parent->next) {
425                 collection_object_cache_free(parent->collection);
426         }
427 }
428
429 void BKE_collection_object_cache_free(Collection *collection)
430 {
431         collection_object_cache_free(collection);
432 }
433
434 Base *BKE_collection_or_layer_objects(const ViewLayer *view_layer, Collection *collection)
435 {
436         if (collection) {
437                 return BKE_collection_object_cache_get(collection).first;
438         }
439         else {
440                 return FIRSTBASE(view_layer);
441         }
442 }
443
444 /*********************** Scene Master Collection ***************/
445
446 Collection *BKE_collection_master_add()
447 {
448         /* Not an actual datablock, but owned by scene. */
449         Collection *master_collection = MEM_callocN(sizeof(Collection), "Master Collection");
450         STRNCPY(master_collection->id.name, "GRMaster Collection");
451         master_collection->flag |= COLLECTION_IS_MASTER;
452         return master_collection;
453 }
454
455 Collection *BKE_collection_master(const Scene *scene)
456 {
457         return scene->master_collection;
458 }
459
460 /*********************** Cyclic Checks ************************/
461
462 static bool collection_object_cyclic_check_internal(Object *object, Collection *collection)
463 {
464         if (object->instance_collection) {
465                 Collection *dup_collection = object->instance_collection;
466                 if ((dup_collection->id.tag & LIB_TAG_DOIT) == 0) {
467                         /* Cycle already exists in collections, let's prevent further crappyness */
468                         return true;
469                 }
470                 /* flag the object to identify cyclic dependencies in further dupli collections */
471                 dup_collection->id.tag &= ~LIB_TAG_DOIT;
472
473                 if (dup_collection == collection) {
474                         return true;
475                 }
476                 else {
477                         FOREACH_COLLECTION_OBJECT_RECURSIVE_BEGIN(dup_collection, collection_object)
478                         {
479                                 if (collection_object_cyclic_check_internal(collection_object, dup_collection)) {
480                                         return true;
481                                 }
482                         }
483                         FOREACH_COLLECTION_OBJECT_RECURSIVE_END;
484                 }
485
486                 /* un-flag the object, it's allowed to have the same collection multiple times in parallel */
487                 dup_collection->id.tag |= LIB_TAG_DOIT;
488         }
489
490         return false;
491 }
492
493 bool BKE_collection_object_cyclic_check(Main *bmain, Object *object, Collection *collection)
494 {
495         /* first flag all collections */
496         BKE_main_id_tag_listbase(&bmain->collection, LIB_TAG_DOIT, true);
497
498         return collection_object_cyclic_check_internal(object, collection);
499 }
500
501 /******************* Collection Object Membership *******************/
502
503 bool BKE_collection_has_object(Collection *collection, Object *ob)
504 {
505         if (ELEM(NULL, collection, ob)) {
506                 return false;
507         }
508
509         return (BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob)));
510 }
511
512 bool BKE_collection_has_object_recursive(Collection *collection, Object *ob)
513 {
514         if (ELEM(NULL, collection, ob)) {
515                 return false;
516         }
517
518         const ListBase objects = BKE_collection_object_cache_get(collection);
519         return (BLI_findptr(&objects, ob, offsetof(Base, object)));
520 }
521
522 Collection *BKE_collection_object_find(Main *bmain, Collection *collection, Object *ob)
523 {
524         if (collection)
525                 collection = collection->id.next;
526         else
527                 collection = bmain->collection.first;
528
529         while (collection) {
530                 if (BKE_collection_has_object(collection, ob))
531                         return collection;
532                 collection = collection->id.next;
533         }
534         return NULL;
535 }
536
537 bool BKE_collection_is_empty(Collection *collection)
538 {
539         return BLI_listbase_is_empty(&collection->gobject) && BLI_listbase_is_empty(&collection->children);
540 }
541
542 /********************** Collection Objects *********************/
543
544 static bool collection_object_add(Main *bmain, Collection *collection, Object *ob, int flag, const bool add_us)
545 {
546         if (ob->instance_collection) {
547                 /* Cyclic dependency check. */
548                 if (collection_find_child_recursive(ob->instance_collection, collection)) {
549                         return false;
550                 }
551         }
552
553         CollectionObject *cob = BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob));
554         if (cob) {
555                 return false;
556         }
557
558         cob = MEM_callocN(sizeof(CollectionObject), __func__);
559         cob->ob = ob;
560         BLI_addtail(&collection->gobject, cob);
561         BKE_collection_object_cache_free(collection);
562
563         if (add_us && (flag & LIB_ID_CREATE_NO_USER_REFCOUNT) == 0) {
564                 id_us_plus(&ob->id);
565         }
566
567         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
568                 DEG_id_tag_update_ex(bmain, &collection->id, ID_RECALC_COPY_ON_WRITE);
569         }
570
571         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
572                 BKE_rigidbody_main_collection_object_add(bmain, collection, ob);
573         }
574
575         return true;
576 }
577
578 static bool collection_object_remove(Main *bmain, Collection *collection, Object *ob, const bool free_us)
579 {
580         CollectionObject *cob = BLI_findptr(&collection->gobject, ob, offsetof(CollectionObject, ob));
581         if (cob == NULL) {
582                 return false;
583         }
584
585         BLI_freelinkN(&collection->gobject, cob);
586         BKE_collection_object_cache_free(collection);
587
588         if (free_us) {
589                 BKE_id_free_us(bmain, ob);
590         }
591         else {
592                 id_us_min(&ob->id);
593         }
594
595         DEG_id_tag_update_ex(bmain, &collection->id, ID_RECALC_COPY_ON_WRITE);
596
597         return true;
598 }
599
600 /**
601  * Add object to collection
602  */
603 bool BKE_collection_object_add(Main *bmain, Collection *collection, Object *ob)
604 {
605         if (ELEM(NULL, collection, ob)) {
606                 return false;
607         }
608
609         if (!collection_object_add(bmain, collection, ob, 0, true)) {
610                 return false;
611         }
612
613         if (BKE_collection_is_in_scene(collection)) {
614                 BKE_main_collection_sync(bmain);
615         }
616
617         return true;
618 }
619
620 /**
621  * Add object to all scene collections that reference objects is in
622  * (used to copy objects)
623  */
624 void BKE_collection_object_add_from(Main *bmain, Scene *scene, Object *ob_src, Object *ob_dst)
625 {
626         FOREACH_SCENE_COLLECTION_BEGIN(scene, collection)
627         {
628                 if (BKE_collection_has_object(collection, ob_src)) {
629                         collection_object_add(bmain, collection, ob_dst, 0, true);
630                 }
631         }
632         FOREACH_SCENE_COLLECTION_END;
633
634         BKE_main_collection_sync(bmain);
635 }
636
637 /**
638  * Remove object from collection.
639  */
640 bool BKE_collection_object_remove(Main *bmain, Collection *collection, Object *ob, const bool free_us)
641 {
642         if (ELEM(NULL, collection, ob)) {
643                 return false;
644         }
645
646         if (!collection_object_remove(bmain, collection, ob, free_us)) {
647                 return false;
648         }
649
650         if (BKE_collection_is_in_scene(collection)) {
651                 BKE_main_collection_sync(bmain);
652         }
653
654         return true;
655 }
656
657 /**
658  * Remove object from all collections of scene
659  * \param scene_collection_skip: Don't remove base from this collection.
660  */
661 static bool scene_collections_object_remove(Main *bmain, Scene *scene, Object *ob, const bool free_us,
662                                       Collection *collection_skip)
663 {
664         bool removed = false;
665
666         if (collection_skip == NULL) {
667                 BKE_scene_remove_rigidbody_object(bmain, scene, ob);
668         }
669
670         FOREACH_SCENE_COLLECTION_BEGIN(scene, collection)
671         {
672                 if (collection != collection_skip) {
673                         removed |= collection_object_remove(bmain, collection, ob, free_us);
674                 }
675         }
676         FOREACH_SCENE_COLLECTION_END;
677
678         BKE_main_collection_sync(bmain);
679
680         return removed;
681 }
682
683 /**
684  * Remove object from all collections of scene
685  */
686 bool BKE_scene_collections_object_remove(Main *bmain, Scene *scene, Object *ob, const bool free_us)
687 {
688         return scene_collections_object_remove(bmain, scene, ob, free_us, NULL);
689 }
690
691 /*
692  * Remove all NULL objects from collections.
693  * This is used for library remapping, where these pointers have been set to NULL.
694  * Otherwise this should never happen.
695  */
696 static void collection_object_remove_nulls(Collection *collection)
697 {
698         bool changed = false;
699
700         for (CollectionObject *cob = collection->gobject.first, *cob_next = NULL; cob; cob = cob_next) {
701                 cob_next = cob->next;
702
703                 if (cob->ob == NULL) {
704                         BLI_freelinkN(&collection->gobject, cob);
705                         changed = true;
706                 }
707         }
708
709         if (changed) {
710                 BKE_collection_object_cache_free(collection);
711         }
712 }
713
714 void BKE_collections_object_remove_nulls(Main *bmain)
715 {
716         for (Scene *scene = bmain->scene.first; scene; scene = scene->id.next) {
717                 collection_object_remove_nulls(scene->master_collection);
718         }
719
720         for (Collection *collection = bmain->collection.first; collection; collection = collection->id.next) {
721                 collection_object_remove_nulls(collection);
722         }
723 }
724
725 static void collection_null_children_remove(Collection *collection)
726 {
727         for (CollectionChild *child = collection->children.first, *child_next = NULL; child; child = child_next) {
728                 child_next = child->next;
729
730                 if (child->collection == NULL) {
731                         BLI_freelinkN(&collection->children, child);
732                 }
733         }
734 }
735
736 static void collection_missing_parents_remove(Collection *collection)
737 {
738         for (CollectionParent *parent = collection->parents.first, *parent_next; parent != NULL; parent = parent_next) {
739                 parent_next = parent->next;
740                 if ((parent->collection == NULL) ||
741                     !collection_find_child(parent->collection, collection))
742                 {
743                         BLI_freelinkN(&collection->parents, parent);
744                 }
745         }
746 }
747
748 /**
749  * Remove all NULL children from parent collections of changed \a collection.
750  * This is used for library remapping, where these pointers have been set to NULL.
751  * Otherwise this should never happen.
752  *
753  * \note caller must ensure BKE_main_collection_sync_remap() is called afterwards!
754  *
755  * \param collection: may be \a NULL, in which case whole \a bmain database of collections is checked.
756  */
757 void BKE_collections_child_remove_nulls(Main *bmain, Collection *collection)
758 {
759         if (collection == NULL) {
760                 /* We need to do the checks in two steps when more than one collection may be involved,
761                  * otherwise we can miss some cases...
762                  * Also, master collections are not in bmain, so we also need to loop over scenes.
763                  */
764                 for (collection = bmain->collection.first; collection != NULL; collection = collection->id.next) {
765                         collection_null_children_remove(collection);
766                 }
767                 for (Scene *scene = bmain->scene.first; scene != NULL; scene = scene->id.next) {
768                         collection_null_children_remove(BKE_collection_master(scene));
769                 }
770
771                 for (collection = bmain->collection.first; collection != NULL; collection = collection->id.next) {
772                         collection_missing_parents_remove(collection);
773                 }
774                 for (Scene *scene = bmain->scene.first; scene != NULL; scene = scene->id.next) {
775                         collection_missing_parents_remove(BKE_collection_master(scene));
776                 }
777         }
778         else {
779                 for (CollectionParent *parent = collection->parents.first, *parent_next; parent; parent = parent_next) {
780                         parent_next = parent->next;
781
782                         collection_null_children_remove(parent->collection);
783
784                         if (!collection_find_child(parent->collection, collection)) {
785                                 BLI_freelinkN(&collection->parents, parent);
786                         }
787                 }
788         }
789 }
790
791 /**
792  * Move object from a collection into another
793  *
794  * If source collection is NULL move it from all the existing collections.
795  */
796 void BKE_collection_object_move(
797         Main *bmain, Scene *scene, Collection *collection_dst, Collection *collection_src, Object *ob)
798 {
799         /* In both cases we first add the object, then remove it from the other collections.
800          * Otherwise we lose the original base and whether it was active and selected. */
801         if (collection_src != NULL) {
802                 if (BKE_collection_object_add(bmain, collection_dst, ob)) {
803                         BKE_collection_object_remove(bmain, collection_src, ob, false);
804                 }
805         }
806         else {
807                 /* Adding will fail if object is already in collection.
808                  * However we still need to remove it from the other collections. */
809                 BKE_collection_object_add(bmain, collection_dst, ob);
810                 scene_collections_object_remove(bmain, scene, ob, false, collection_dst);
811         }
812 }
813
814 /***************** Collection Scene Membership ****************/
815
816 bool BKE_collection_is_in_scene(Collection *collection)
817 {
818         if (collection->flag & COLLECTION_IS_MASTER) {
819                 return true;
820         }
821
822         for (CollectionParent *cparent = collection->parents.first; cparent; cparent = cparent->next) {
823                 if (BKE_collection_is_in_scene(cparent->collection)) {
824                         return true;
825                 }
826         }
827
828         return false;
829 }
830
831 void BKE_collections_after_lib_link(Main *bmain)
832 {
833         /* Need to update layer collections because objects might have changed
834          * in linked files, and because undo push does not include updated base
835          * flags since those are refreshed after the operator completes. */
836         BKE_main_collection_sync(bmain);
837 }
838
839 /********************** Collection Children *******************/
840
841 bool BKE_collection_find_cycle(Collection *new_ancestor, Collection *collection)
842 {
843         if (collection == new_ancestor) {
844                 return true;
845         }
846
847         for (CollectionParent *parent = new_ancestor->parents.first; parent; parent = parent->next) {
848                 if (BKE_collection_find_cycle(parent->collection, collection)) {
849                         return true;
850                 }
851         }
852
853         return false;
854 }
855
856 static CollectionChild *collection_find_child(Collection *parent, Collection *collection)
857 {
858         return BLI_findptr(&parent->children, collection, offsetof(CollectionChild, collection));
859 }
860
861 static bool collection_find_child_recursive(Collection *parent, Collection *collection)
862 {
863         for (CollectionChild *child = parent->children.first; child; child = child->next) {
864                 if (child->collection == collection) {
865                         return true;
866                 }
867
868                 if (collection_find_child_recursive(child->collection, collection)) {
869                         return true;
870                 }
871         }
872
873         return false;
874 }
875
876 static CollectionParent *collection_find_parent(Collection *child, Collection *collection)
877 {
878         return BLI_findptr(&child->parents, collection, offsetof(CollectionParent, collection));
879 }
880
881 static bool collection_child_add(Collection *parent, Collection *collection, const int flag, const bool add_us)
882 {
883         CollectionChild *child = collection_find_child(parent, collection);
884         if (child) {
885                 return false;
886         }
887         if (BKE_collection_find_cycle(parent, collection)) {
888                 return false;
889         }
890
891         child = MEM_callocN(sizeof(CollectionChild), "CollectionChild");
892         child->collection = collection;
893         BLI_addtail(&parent->children, child);
894
895         /* Don't add parent links for depsgraph datablocks, these are not kept in sync. */
896         if ((flag & LIB_ID_CREATE_NO_MAIN) == 0) {
897                 CollectionParent *cparent = MEM_callocN(sizeof(CollectionParent), "CollectionParent");
898                 cparent->collection = parent;
899                 BLI_addtail(&collection->parents, cparent);
900         }
901
902         if (add_us) {
903                 id_us_plus(&collection->id);
904         }
905
906         BKE_collection_object_cache_free(parent);
907
908         return true;
909 }
910
911 static bool collection_child_remove(Collection *parent, Collection *collection)
912 {
913         CollectionChild *child = collection_find_child(parent, collection);
914         if (child == NULL) {
915                 return false;
916         }
917
918         CollectionParent *cparent = collection_find_parent(collection, parent);
919         BLI_freelinkN(&collection->parents, cparent);
920         BLI_freelinkN(&parent->children, child);
921
922         id_us_min(&collection->id);
923
924         BKE_collection_object_cache_free(parent);
925
926         return true;
927 }
928
929 bool BKE_collection_child_add(Main *bmain, Collection *parent, Collection *child)
930 {
931         if (!collection_child_add(parent, child, 0, true)) {
932                 return false;
933         }
934
935         BKE_main_collection_sync(bmain);
936         return true;
937 }
938
939 bool BKE_collection_child_remove(Main *bmain, Collection *parent, Collection *child)
940 {
941         if (!collection_child_remove(parent, child)) {
942                 return false;
943         }
944
945         BKE_main_collection_sync(bmain);
946         return true;
947 }
948
949 /********************** Collection index *********************/
950
951 static Collection *collection_from_index_recursive(Collection *collection, const int index, int *index_current)
952 {
953         if (index == (*index_current)) {
954                 return collection;
955         }
956
957         (*index_current)++;
958
959         for (CollectionChild *child = collection->children.first; child; child = child->next) {
960                 Collection *nested = collection_from_index_recursive(child->collection, index, index_current);
961                 if (nested != NULL) {
962                         return nested;
963                 }
964         }
965         return NULL;
966 }
967
968 /**
969  * Return Scene Collection for a given index.
970  *
971  * The index is calculated from top to bottom counting the children before the siblings.
972  */
973 Collection *BKE_collection_from_index(Scene *scene, const int index)
974 {
975         int index_current = 0;
976         Collection *master_collection = BKE_collection_master(scene);
977         return collection_from_index_recursive(master_collection, index, &index_current);
978 }
979
980 static bool collection_objects_select(ViewLayer *view_layer, Collection *collection, bool deselect)
981 {
982         bool changed = false;
983
984         if (collection->flag & COLLECTION_RESTRICT_SELECT) {
985                 return false;
986         }
987
988         for (CollectionObject *cob = collection->gobject.first; cob; cob = cob->next) {
989                 Base *base = BKE_view_layer_base_find(view_layer, cob->ob);
990
991                 if (base) {
992                         if (deselect) {
993                                 if (base->flag & BASE_SELECTED) {
994                                         base->flag &= ~BASE_SELECTED;
995                                         changed = true;
996                                 }
997                         }
998                         else {
999                                 if ((base->flag & BASE_SELECTABLE) && !(base->flag & BASE_SELECTED)) {
1000                                         base->flag |= BASE_SELECTED;
1001                                         changed = true;
1002                                 }
1003                         }
1004                 }
1005         }
1006
1007         for (CollectionChild *child = collection->children.first; child; child = child->next) {
1008                 if (collection_objects_select(view_layer, collection, deselect)) {
1009                         changed = true;
1010                 }
1011         }
1012
1013         return changed;
1014 }
1015
1016 /**
1017  * Select all the objects in this Collection (and its nested collections) for this ViewLayer.
1018  * Return true if any object was selected.
1019  */
1020 bool BKE_collection_objects_select(ViewLayer *view_layer, Collection *collection, bool deselect)
1021 {
1022         LayerCollection *layer_collection = BKE_layer_collection_first_from_scene_collection(view_layer, collection);
1023
1024         if (layer_collection != NULL) {
1025                 return BKE_layer_collection_objects_select(view_layer, layer_collection, deselect);
1026         }
1027         else {
1028                 return collection_objects_select(view_layer, collection, deselect);
1029         }
1030 }
1031
1032 /***************** Collection move (outliner drag & drop) *********************/
1033
1034 bool BKE_collection_move(Main *bmain,
1035                          Collection *to_parent,
1036                          Collection *from_parent,
1037                          Collection *relative,
1038                          bool relative_after,
1039                          Collection *collection)
1040 {
1041         if (collection->flag & COLLECTION_IS_MASTER) {
1042                 return false;
1043         }
1044         if (BKE_collection_find_cycle(to_parent, collection)) {
1045                 return false;
1046         }
1047
1048         /* Move to new parent collection */
1049         if (from_parent) {
1050                 collection_child_remove(from_parent, collection);
1051         }
1052
1053         collection_child_add(to_parent, collection, 0, true);
1054
1055         /* Move to specified location under parent. */
1056         if (relative) {
1057                 CollectionChild *child = collection_find_child(to_parent, collection);
1058                 CollectionChild *relative_child = collection_find_child(to_parent, relative);
1059
1060                 if (relative_child) {
1061                         BLI_remlink(&to_parent->children, child);
1062
1063                         if (relative_after) {
1064                                 BLI_insertlinkafter(&to_parent->children, relative_child, child);
1065                         }
1066                         else {
1067                                 BLI_insertlinkbefore(&to_parent->children, relative_child, child);
1068                         }
1069
1070                         BKE_collection_object_cache_free(to_parent);
1071                 }
1072         }
1073
1074         BKE_main_collection_sync(bmain);
1075
1076         return true;
1077 }
1078
1079 /**************************** Iterators ******************************/
1080
1081 /* scene collection iteractor */
1082
1083 typedef struct CollectionsIteratorData {
1084         Scene *scene;
1085         void **array;
1086         int tot, cur;
1087 } CollectionsIteratorData;
1088
1089 static void scene_collection_callback(Collection *collection, BKE_scene_collections_Cb callback, void *data)
1090 {
1091         callback(collection, data);
1092
1093         for (CollectionChild *child = collection->children.first; child; child = child->next) {
1094                 scene_collection_callback(child->collection, callback, data);
1095         }
1096 }
1097
1098 static void scene_collections_count(Collection *UNUSED(collection), void *data)
1099 {
1100         int *tot = data;
1101         (*tot)++;
1102 }
1103
1104 static void scene_collections_build_array(Collection *collection, void *data)
1105 {
1106         Collection ***array = data;
1107         **array = collection;
1108         (*array)++;
1109 }
1110
1111 static void scene_collections_array(Scene *scene, Collection ***collections_array, int *tot)
1112 {
1113         Collection *collection;
1114         Collection **array;
1115
1116         *collections_array = NULL;
1117         *tot = 0;
1118
1119         if (scene == NULL) {
1120                 return;
1121         }
1122
1123         collection = BKE_collection_master(scene);
1124         BLI_assert(collection != NULL);
1125         scene_collection_callback(collection, scene_collections_count, tot);
1126
1127         if (*tot == 0)
1128                 return;
1129
1130         *collections_array = array = MEM_mallocN(sizeof(Collection *) * (*tot), "CollectionArray");
1131         scene_collection_callback(collection, scene_collections_build_array, &array);
1132 }
1133
1134 /**
1135  * Only use this in non-performance critical situations
1136  * (it iterates over all scene collections twice)
1137  */
1138 void BKE_scene_collections_iterator_begin(BLI_Iterator *iter, void *data_in)
1139 {
1140         Scene *scene = data_in;
1141         CollectionsIteratorData *data = MEM_callocN(sizeof(CollectionsIteratorData), __func__);
1142
1143         data->scene = scene;
1144         iter->data = data;
1145         iter->valid = true;
1146
1147         scene_collections_array(scene, (Collection ***)&data->array, &data->tot);
1148         BLI_assert(data->tot != 0);
1149
1150         data->cur = 0;
1151         iter->current = data->array[data->cur];
1152 }
1153
1154 void BKE_scene_collections_iterator_next(struct BLI_Iterator *iter)
1155 {
1156         CollectionsIteratorData *data = iter->data;
1157
1158         if (++data->cur < data->tot) {
1159                 iter->current = data->array[data->cur];
1160         }
1161         else {
1162                 iter->valid = false;
1163         }
1164 }
1165
1166 void BKE_scene_collections_iterator_end(struct BLI_Iterator *iter)
1167 {
1168         CollectionsIteratorData *data = iter->data;
1169
1170         if (data) {
1171                 if (data->array) {
1172                         MEM_freeN(data->array);
1173                 }
1174                 MEM_freeN(data);
1175         }
1176         iter->valid = false;
1177 }
1178
1179
1180 /* scene objects iterator */
1181
1182 typedef struct SceneObjectsIteratorData {
1183         GSet *visited;
1184         CollectionObject *cob_next;
1185         BLI_Iterator scene_collection_iter;
1186 } SceneObjectsIteratorData;
1187
1188 void BKE_scene_objects_iterator_begin(BLI_Iterator *iter, void *data_in)
1189 {
1190         Scene *scene = data_in;
1191         SceneObjectsIteratorData *data = MEM_callocN(sizeof(SceneObjectsIteratorData), __func__);
1192         iter->data = data;
1193
1194         /* lookup list ot make sure each object is object called once */
1195         data->visited = BLI_gset_ptr_new(__func__);
1196
1197         /* we wrap the scenecollection iterator here to go over the scene collections */
1198         BKE_scene_collections_iterator_begin(&data->scene_collection_iter, scene);
1199
1200         Collection *collection = data->scene_collection_iter.current;
1201         data->cob_next = collection->gobject.first;
1202
1203         BKE_scene_objects_iterator_next(iter);
1204 }
1205
1206 /**
1207  * Ensures we only get each object once, even when included in several collections.
1208  */
1209 static CollectionObject *object_base_unique(GSet *gs, CollectionObject *cob)
1210 {
1211         for (; cob != NULL; cob = cob->next) {
1212                 Object *ob = cob->ob;
1213                 void **ob_key_p;
1214                 if (!BLI_gset_ensure_p_ex(gs, ob, &ob_key_p)) {
1215                         *ob_key_p = ob;
1216                         return cob;
1217                 }
1218         }
1219         return NULL;
1220 }
1221
1222 void BKE_scene_objects_iterator_next(BLI_Iterator *iter)
1223 {
1224         SceneObjectsIteratorData *data = iter->data;
1225         CollectionObject *cob = data->cob_next ? object_base_unique(data->visited, data->cob_next) : NULL;
1226
1227         if (cob) {
1228                 data->cob_next = cob->next;
1229                 iter->current = cob->ob;
1230         }
1231         else {
1232                 /* if this is the last object of this ListBase look at the next Collection */
1233                 Collection *collection;
1234                 BKE_scene_collections_iterator_next(&data->scene_collection_iter);
1235                 do {
1236                         collection = data->scene_collection_iter.current;
1237                         /* get the first unique object of this collection */
1238                         CollectionObject *new_cob = object_base_unique(data->visited, collection->gobject.first);
1239                         if (new_cob) {
1240                                 data->cob_next = new_cob->next;
1241                                 iter->current = new_cob->ob;
1242                                 return;
1243                         }
1244                         BKE_scene_collections_iterator_next(&data->scene_collection_iter);
1245                 } while (data->scene_collection_iter.valid);
1246
1247                 if (!data->scene_collection_iter.valid) {
1248                         iter->valid = false;
1249                 }
1250         }
1251 }
1252
1253 void BKE_scene_objects_iterator_end(BLI_Iterator *iter)
1254 {
1255         SceneObjectsIteratorData *data = iter->data;
1256         if (data) {
1257                 BKE_scene_collections_iterator_end(&data->scene_collection_iter);
1258                 BLI_gset_free(data->visited, NULL);
1259                 MEM_freeN(data);
1260         }
1261 }