From 8d3e57f338234995c30ae702fff62ed6229f762e Mon Sep 17 00:00:00 2001
From: Bastien Montagne <bastien@blender.org>
Date: Wed, 22 Dec 2021 16:57:07 +0100
Subject: Fix T93799: Outliner: Remaping objects could result in duplicates in
 a collection.

Fix is similar to how CollectionObject with NULL object pointers are handled.

Using one of the 'free' pad bytes in Object_Runtime struct instead of a
gset (or other external way to detect object duplicates), as this is
several times faster.

NOTE: This makes remapping slightly slower again (adds 10 extra seconds
to file case in T94059).

General improvements of remapping time complexity, especially when
remapping a lot of IDs at once, is a separate topic currently
investigated in D13615.
---
 source/blender/blenkernel/BKE_collection.h    | 14 +++++++++
 source/blender/blenkernel/intern/collection.c | 44 +++++++++++++++++++++++++++
 source/blender/blenkernel/intern/lib_remap.c  |  6 ++++
 3 files changed, 64 insertions(+)

(limited to 'source/blender/blenkernel')

diff --git a/source/blender/blenkernel/BKE_collection.h b/source/blender/blenkernel/BKE_collection.h
index 46c1fe0d33d..7dfda7b5121 100644
--- a/source/blender/blenkernel/BKE_collection.h
+++ b/source/blender/blenkernel/BKE_collection.h
@@ -163,7 +163,21 @@ bool BKE_scene_collections_object_remove(struct Main *bmain,
                                          struct Scene *scene,
                                          struct Object *object,
                                          const bool free_us);
+
+/**
+ * Check all collections in \a bmain (including embedded ones in scenes) for CollectionObject with
+ * NULL object pointer, and remove them.
+ */
 void BKE_collections_object_remove_nulls(struct Main *bmain);
+
+/**
+ * Check all collections in \a bmain (including embedded ones in scenes) for duplicate
+ * CollectionObject with a same object pointer within a same object, and remove them.
+ *
+ * NOTE: Always keeps the first of the detected duplicates.
+ */
+void BKE_collections_object_remove_duplicates(struct Main *bmain);
+
 /**
  * Remove all NULL children from parent collections of changed \a collection.
  * This is used for library remapping, where these pointers have been set to NULL.
diff --git a/source/blender/blenkernel/intern/collection.c b/source/blender/blenkernel/intern/collection.c
index 21a9159004f..57fe61b8ad4 100644
--- a/source/blender/blenkernel/intern/collection.c
+++ b/source/blender/blenkernel/intern/collection.c
@@ -1231,6 +1231,50 @@ void BKE_collections_object_remove_nulls(Main *bmain)
   }
 }
 
+/*
+ * Remove all duplicate objects from collections.
+ * This is used for library remapping, happens when remapping an object to another one already
+ * present in the collection. Otherwise this should never happen.
+ */
+static void collection_object_remove_duplicates(Collection *collection)
+{
+  bool changed = false;
+
+  LISTBASE_FOREACH_MUTABLE (CollectionObject *, cob, &collection->gobject) {
+    if (cob->ob->runtime.collection_management) {
+      BLI_freelinkN(&collection->gobject, cob);
+      changed = true;
+      continue;
+    }
+    cob->ob->runtime.collection_management = true;
+  }
+
+  /* Cleanup. */
+  LISTBASE_FOREACH (CollectionObject *, cob, &collection->gobject) {
+    cob->ob->runtime.collection_management = false;
+  }
+
+  if (changed) {
+    BKE_collection_object_cache_free(collection);
+  }
+}
+
+void BKE_collections_object_remove_duplicates(struct Main *bmain)
+{
+  LISTBASE_FOREACH (Object *, ob, &bmain->objects) {
+    ob->runtime.collection_management = false;
+  }
+
+  for (Scene *scene = bmain->scenes.first; scene; scene = scene->id.next) {
+    collection_object_remove_duplicates(scene->master_collection);
+  }
+
+  for (Collection *collection = bmain->collections.first; collection;
+       collection = collection->id.next) {
+    collection_object_remove_duplicates(collection);
+  }
+}
+
 static void collection_null_children_remove(Collection *collection)
 {
   for (CollectionChild *child = collection->children.first, *child_next = NULL; child;
diff --git a/source/blender/blenkernel/intern/lib_remap.c b/source/blender/blenkernel/intern/lib_remap.c
index 9ea85714b4a..b8e0eb2c942 100644
--- a/source/blender/blenkernel/intern/lib_remap.c
+++ b/source/blender/blenkernel/intern/lib_remap.c
@@ -282,6 +282,11 @@ static void libblock_remap_data_postprocess_object_update(Main *bmain,
      * to remove the NULL children from collections not used in any scene. */
     BKE_collections_object_remove_nulls(bmain);
   }
+  else {
+    /* Remapping may have created duplicates of CollectionObject pointing to the same object within
+     * the same collection. */
+    BKE_collections_object_remove_duplicates(bmain);
+  }
 
   BKE_main_collection_sync_remap(bmain);
 
@@ -319,6 +324,7 @@ static void libblock_remap_data_postprocess_collection_update(Main *bmain,
   else {
     /* Temp safe fix, but a "tad" brute force... We should probably be able to use parents from
      * old_collection instead? */
+    /* NOTE: Also takes care of duplicated child collections that remapping may have created. */
     BKE_main_collections_parent_relations_rebuild(bmain);
   }
 
-- 
cgit v1.2.3