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