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