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