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