source/blender/blenkernel/intern/collection.c

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