source/blender/blenkernel/intern/collection.c

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