Add 'multiple' variant of ID relink function.

Similar to other changes to ID remapping, gives huge speedups in some
cases, like certain types of liboverride creation.

Case from {T96092} goes from 1725 seconds (almost 30 minutes) to 45
seconds to generate the liboverride, on my machine.

Reviewed By: jbakker

Maniphest Tasks: T96092

Differential Revision: https://developer.blender.org/D14240

3 files changed, 219 insertions, 114 deletions

diff --git a/source/blender/blenkernel/BKE_lib_remap.h b/source/blender/blenkernel/BKE_lib_remap.h
index fd7d39fc250..b66d53b2321 100644
--- a/source/blender/blenkernel/BKE_lib_remap.h
+++ b/source/blender/blenkernel/BKE_lib_remap.h
@@ -26,6 +26,7 @@ extern "C" {
 
 struct ID;
 struct IDRemapper;
+struct LinkNode;
 
 /* BKE_libblock_free, delete are declared in BKE_lib_id.h for convenience. */
 
@@ -133,6 +134,15 @@ void BKE_libblock_relink_ex(struct Main *bmain,
                             void *old_idv,
                             void *new_idv,
                             short remap_flags) ATTR_NONNULL(1, 2);
+/**
+ * Same as #BKE_libblock_relink_ex, but applies all rules defined in \a id_remapper to \a ids (or
+ * does cleanup if `ID_REMAP_TYPE_CLEANUP` is specified as \a remap_type).
+ */
+void BKE_libblock_relink_multiple(struct Main *bmain,
+                                  struct LinkNode *ids,
+                                  const eIDRemapType remap_type,
+                                  struct IDRemapper *id_remapper,
+                                  const short remap_flags);
 
 /**
  * Remaps ID usages of given ID to their `id->newid` pointer if not None, and proceeds recursively
diff --git a/source/blender/blenkernel/intern/lib_override.c b/source/blender/blenkernel/intern/lib_override.c
index 701788a4e29..64ebb08f5d0 100644
--- a/source/blender/blenkernel/intern/lib_override.c
+++ b/source/blender/blenkernel/intern/lib_override.c
@@ -417,6 +417,39 @@ bool BKE_lib_override_library_create_from_tag(Main *bmain,
     }
     BLI_assert(id_hierarchy_root != NULL);
 
+    LinkNode *relinked_ids = NULL;
+    /* Still checking the whole Main, that way we can tag other local IDs as needing to be
+     * remapped to use newly created overriding IDs, if needed. */
+    ID *id;
+    FOREACH_MAIN_ID_BEGIN (bmain, id) {
+      ID *other_id;
+      /* In case we created new overrides as 'no main', they are not accessible directly in this
+       * loop, but we can get to them through their reference's `newid` pointer. */
+      if (do_no_main && id->lib == id_root_reference->lib && id->newid != NULL) {
+        other_id = id->newid;
+        /* Otherwise we cannot properly distinguish between IDs that are actually from the
+         * linked library (and should not be remapped), and IDs that are overrides re-generated
+         * from the reference from the linked library, and must therefore be remapped.
+         *
+         * This is reset afterwards at the end of this loop. */
+        other_id->lib = NULL;
+      }
+      else {
+        other_id = id;
+      }
+
+      /* If other ID is a linked one, but not from the same library as our reference, then we
+       * consider we should also relink it, as part of recursive resync. */
+      if ((other_id->tag & LIB_TAG_DOIT) != 0 && other_id->lib != id_root_reference->lib) {
+        BLI_linklist_prepend(&relinked_ids, other_id);
+      }
+      if (other_id != id) {
+        other_id->lib = id_root_reference->lib;
+      }
+    }
+    FOREACH_MAIN_ID_END;
+
+    struct IDRemapper *id_remapper = BKE_id_remapper_create();
     for (todo_id_iter = todo_ids.first; todo_id_iter != NULL; todo_id_iter = todo_id_iter->next) {
       reference_id = todo_id_iter->data;
       ID *local_id = reference_id->newid;
@@ -427,55 +460,25 @@ bool BKE_lib_override_library_create_from_tag(Main *bmain,
 
       local_id->override_library->hierarchy_root = id_hierarchy_root;
 
+      BKE_id_remapper_add(id_remapper, reference_id, local_id);
+
       Key *reference_key, *local_key = NULL;
       if ((reference_key = BKE_key_from_id(reference_id)) != NULL) {
         local_key = BKE_key_from_id(reference_id->newid);
         BLI_assert(local_key != NULL);
-      }
-
-      /* Still checking the whole Main, that way we can tag other local IDs as needing to be
-       * remapped to use newly created overriding IDs, if needed. */
-      ID *id;
-      FOREACH_MAIN_ID_BEGIN (bmain, id) {
-        ID *other_id;
-        /* In case we created new overrides as 'no main', they are not accessible directly in this
-         * loop, but we can get to them through their reference's `newid` pointer. */
-        if (do_no_main && id->lib == reference_id->lib && id->newid != NULL) {
-          other_id = id->newid;
-          /* Otherwise we cannot properly distinguish between IDs that are actually from the
-           * linked library (and should not be remapped), and IDs that are overrides re-generated
-           * from the reference from the linked library, and must therefore be remapped.
-           *
-           * This is reset afterwards at the end of this loop. */
-          other_id->lib = NULL;
-        }
-        else {
-          other_id = id;
-        }
 
-        /* If other ID is a linked one, but not from the same library as our reference, then we
-         * consider we should also remap it, as part of recursive resync. */
-        if ((other_id->tag & LIB_TAG_DOIT) != 0 && other_id->lib != reference_id->lib &&
-            other_id != local_id) {
-          BKE_libblock_relink_ex(bmain,
-                                 other_id,
-                                 reference_id,
-                                 local_id,
-                                 ID_REMAP_SKIP_OVERRIDE_LIBRARY | ID_REMAP_FORCE_USER_REFCOUNT);
-          if (reference_key != NULL) {
-            BKE_libblock_relink_ex(bmain,
-                                   other_id,
-                                   &reference_key->id,
-                                   &local_key->id,
-                                   ID_REMAP_SKIP_OVERRIDE_LIBRARY | ID_REMAP_FORCE_USER_REFCOUNT);
-          }
-        }
-        if (other_id != id) {
-          other_id->lib = reference_id->lib;
-        }
+        BKE_id_remapper_add(id_remapper, &reference_key->id, &local_key->id);
       }
-      FOREACH_MAIN_ID_END;
     }
+
+    BKE_libblock_relink_multiple(bmain,
+                                 relinked_ids,
+                                 ID_REMAP_TYPE_REMAP,
+                                 id_remapper,
+                                 ID_REMAP_SKIP_OVERRIDE_LIBRARY | ID_REMAP_FORCE_USER_REFCOUNT);
+
+    BKE_id_remapper_free(id_remapper);
+    BLI_linklist_free(relinked_ids, NULL);
   }
   else {
     /* We need to cleanup potentially already created data. */
@@ -1353,8 +1356,9 @@ static void lib_override_library_remap(Main *bmain,
 {
   ID *id;
   struct IDRemapper *remapper = BKE_id_remapper_create();
-  FOREACH_MAIN_ID_BEGIN (bmain, id) {
+  LinkNode *nomain_ids = NULL;
 
+  FOREACH_MAIN_ID_BEGIN (bmain, id) {
     if (id->tag & LIB_TAG_DOIT && id->newid != NULL && id->lib == id_root_reference->lib) {
       ID *id_override_new = id->newid;
       ID *id_override_old = BLI_ghash_lookup(linkedref_to_old_override, id);
@@ -1363,26 +1367,28 @@ static void lib_override_library_remap(Main *bmain,
       }
 
       BKE_id_remapper_add(remapper, id_override_old, id_override_new);
-      /* Remap no-main override IDs we just created too. */
-      GHashIterator linkedref_to_old_override_iter;
-      GHASH_ITER (linkedref_to_old_override_iter, linkedref_to_old_override) {
-        ID *id_override_old_iter = BLI_ghashIterator_getValue(&linkedref_to_old_override_iter);
-        if ((id_override_old_iter->tag & LIB_TAG_NO_MAIN) == 0) {
-          continue;
-        }
-
-        BKE_libblock_relink_ex(bmain,
-                               id_override_old_iter,
-                               id_override_old,
-                               id_override_new,
-                               ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
-      }
     }
   }
   FOREACH_MAIN_ID_END;
 
+  /* Remap no-main override IDs we just created too. */
+  GHashIterator linkedref_to_old_override_iter;
+  GHASH_ITER (linkedref_to_old_override_iter, linkedref_to_old_override) {
+    ID *id_override_old_iter = BLI_ghashIterator_getValue(&linkedref_to_old_override_iter);
+    if ((id_override_old_iter->tag & LIB_TAG_NO_MAIN) == 0) {
+      continue;
+    }
+
+    BLI_linklist_prepend(&nomain_ids, id_override_old_iter);
+  }
+
   /* Remap all IDs to use the new override. */
   BKE_libblock_remap_multiple(bmain, remapper, 0);
+  BKE_libblock_relink_multiple(bmain,
+                               nomain_ids,
+                               ID_REMAP_TYPE_REMAP,
+                               remapper,
+                               ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
   BKE_id_remapper_free(remapper);
 }
 
@@ -1641,6 +1647,8 @@ static bool lib_override_library_resync(Main *bmain,
 
   BKE_main_collection_sync(bmain);
 
+  LinkNode *id_override_old_list = NULL;
+
   /* We need to apply override rules in a separate loop, after all ID pointers have been properly
    * remapped, and all new local override IDs have gotten their proper original names, otherwise
    * override operations based on those ID names would fail. */
@@ -1690,19 +1698,27 @@ static bool lib_override_library_resync(Main *bmain,
                                       RNA_OVERRIDE_APPLY_FLAG_NOP);
       }
 
-      /* Once overrides have been properly 'transferred' from old to new ID, we can clear ID usages
-       * of the old one.
-       * This is necessary in case said old ID is not in Main anymore. */
-      BKE_libblock_relink_ex(bmain,
-                             id_override_old,
-                             NULL,
-                             NULL,
-                             ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
-      id_override_old->tag |= LIB_TAG_NO_USER_REFCOUNT;
+      BLI_linklist_prepend(&id_override_old_list, id_override_old);
     }
   }
   FOREACH_MAIN_ID_END;
 
+  /* Once overrides have been properly 'transferred' from old to new ID, we can clear ID usages
+   * of the old one.
+   * This is necessary in case said old ID is not in Main anymore. */
+  struct IDRemapper *id_remapper = BKE_id_remapper_create();
+  BKE_libblock_relink_multiple(bmain,
+                               id_override_old_list,
+                               ID_REMAP_TYPE_CLEANUP,
+                               id_remapper,
+                               ID_REMAP_FORCE_USER_REFCOUNT | ID_REMAP_FORCE_NEVER_NULL_USAGE);
+  for (LinkNode *ln_iter = id_override_old_list; ln_iter != NULL; ln_iter = ln_iter->next) {
+    ID *id_override_old = ln_iter->link;
+    id_override_old->tag |= LIB_TAG_NO_USER_REFCOUNT;
+  }
+  BKE_id_remapper_free(id_remapper);
+  BLI_linklist_free(id_override_old_list, NULL);
+
   /* Delete old override IDs.
    * Note that we have to use tagged group deletion here, since ID deletion also uses
    * LIB_TAG_DOIT. This improves performances anyway, so everything is fine. */
diff --git a/source/blender/blenkernel/intern/lib_remap.c b/source/blender/blenkernel/intern/lib_remap.c
index 24e7178dd63..468bc491a83 100644
--- a/source/blender/blenkernel/intern/lib_remap.c
+++ b/source/blender/blenkernel/intern/lib_remap.c
@@ -8,6 +8,7 @@
 
 #include "CLG_log.h"
 
+#include "BLI_linklist.h"
 #include "BLI_utildefines.h"
 
 #include "DNA_collection_types.h"
@@ -681,6 +682,126 @@ void BKE_libblock_unlink(Main *bmain,
  *     ... sigh
  */
 
+typedef struct LibblockRelinkMultipleUserData {
+  Main *bmain;
+  LinkNode *ids;
+} LibBlockRelinkMultipleUserData;
+
+static void libblock_relink_foreach_idpair_cb(ID *old_id, ID *new_id, void *user_data)
+{
+  LibBlockRelinkMultipleUserData *data = user_data;
+  Main *bmain = data->bmain;
+  LinkNode *ids = data->ids;
+
+  BLI_assert(old_id != NULL);
+  BLI_assert((new_id == NULL) || GS(old_id->name) == GS(new_id->name));
+  BLI_assert(old_id != new_id);
+
+  bool is_object_update_processed = false;
+  for (LinkNode *ln_iter = ids; ln_iter != NULL; ln_iter = ln_iter->next) {
+    ID *id_iter = ln_iter->link;
+
+    /* Some after-process updates.
+     * This is a bit ugly, but cannot see a way to avoid it.
+     * Maybe we should do a per-ID callback for this instead?
+     */
+    switch (GS(id_iter->name)) {
+      case ID_SCE:
+      case ID_GR: {
+        /* NOTE: here we know which collection we have affected, so at lest for NULL children
+         * detection we can only process that one.
+         * This is also a required fix in case `id` would not be in Main anymore, which can happen
+         * e.g. when called from `id_delete`. */
+        Collection *owner_collection = (GS(id_iter->name) == ID_GR) ?
+                                           (Collection *)id_iter :
+                                           ((Scene *)id_iter)->master_collection;
+        switch (GS(old_id->name)) {
+          case ID_OB:
+            if (!is_object_update_processed) {
+              libblock_remap_data_postprocess_object_update(
+                  bmain, (Object *)old_id, (Object *)new_id);
+              is_object_update_processed = true;
+            }
+            break;
+          case ID_GR:
+            libblock_remap_data_postprocess_collection_update(
+                bmain, owner_collection, (Collection *)old_id, (Collection *)new_id);
+            break;
+          default:
+            break;
+        }
+        break;
+      }
+      case ID_OB:
+        if (new_id != NULL) { /* Only affects us in case obdata was relinked (changed). */
+          libblock_remap_data_postprocess_obdata_relink(bmain, (Object *)id_iter, new_id);
+        }
+        break;
+      default:
+        break;
+    }
+  }
+}
+
+void BKE_libblock_relink_multiple(Main *bmain,
+                                  LinkNode *ids,
+                                  const eIDRemapType remap_type,
+                                  struct IDRemapper *id_remapper,
+                                  const short remap_flags)
+{
+  BLI_assert(remap_type == ID_REMAP_TYPE_REMAP || BKE_id_remapper_is_empty(id_remapper));
+
+  for (LinkNode *ln_iter = ids; ln_iter != NULL; ln_iter = ln_iter->next) {
+    ID *id_iter = ln_iter->link;
+    libblock_remap_data(bmain, id_iter, remap_type, id_remapper, remap_flags);
+  }
+
+  switch (remap_type) {
+    case ID_REMAP_TYPE_REMAP: {
+      LibBlockRelinkMultipleUserData user_data = {0};
+      user_data.bmain = bmain;
+      user_data.ids = ids;
+
+      BKE_id_remapper_iter(id_remapper, libblock_relink_foreach_idpair_cb, &user_data);
+      break;
+    }
+    case ID_REMAP_TYPE_CLEANUP: {
+      bool is_object_update_processed = false;
+      for (LinkNode *ln_iter = ids; ln_iter != NULL; ln_iter = ln_iter->next) {
+        ID *id_iter = ln_iter->link;
+
+        switch (GS(id_iter->name)) {
+          case ID_SCE:
+          case ID_GR: {
+            /* NOTE: here we know which collection we have affected, so at lest for NULL children
+             * detection we can only process that one.
+             * This is also a required fix in case `id` would not be in Main anymore, which can
+             * happen e.g. when called from `id_delete`. */
+            Collection *owner_collection = (GS(id_iter->name) == ID_GR) ?
+                                               (Collection *)id_iter :
+                                               ((Scene *)id_iter)->master_collection;
+            /* No choice but to check whole objects once, and all children collections. */
+            libblock_remap_data_postprocess_collection_update(bmain, owner_collection, NULL, NULL);
+            if (!is_object_update_processed) {
+              libblock_remap_data_postprocess_object_update(bmain, NULL, NULL);
+              is_object_update_processed = true;
+            }
+            break;
+          }
+          default:
+            break;
+        }
+      }
+
+      break;
+    }
+    default:
+      BLI_assert_unreachable();
+  }
+
+  DEG_relations_tag_update(bmain);
+}
+
 void BKE_libblock_relink_ex(
     Main *bmain, void *idv, void *old_idv, void *new_idv, const short remap_flags)
 {
@@ -690,13 +811,15 @@ void BKE_libblock_relink_ex(
   ID *id = idv;
   ID *old_id = old_idv;
   ID *new_id = new_idv;
+  LinkNode ids = {.next = NULL, .link = idv};
 
   /* No need to lock here, we are only affecting given ID, not bmain database. */
   struct IDRemapper *id_remapper = BKE_id_remapper_create();
   eIDRemapType remap_type = ID_REMAP_TYPE_REMAP;
 
-  BLI_assert(id);
-  if (old_id) {
+  BLI_assert(id != NULL);
+  UNUSED_VARS_NDEBUG(id);
+  if (old_id != NULL) {
     BLI_assert((new_id == NULL) || GS(old_id->name) == GS(new_id->name));
     BLI_assert(old_id != new_id);
     BKE_id_remapper_add(id_remapper, old_id, new_id);
@@ -706,53 +829,9 @@ void BKE_libblock_relink_ex(
     remap_type = ID_REMAP_TYPE_CLEANUP;
   }
 
-  libblock_remap_data(bmain, id, remap_type, id_remapper, remap_flags);
-  BKE_id_remapper_free(id_remapper);
-
-  /* Some after-process updates.
-   * This is a bit ugly, but cannot see a way to avoid it.
-   * Maybe we should do a per-ID callback for this instead?
-   */
-  switch (GS(id->name)) {
-    case ID_SCE:
-    case ID_GR: {
-      /* NOTE: here we know which collection we have affected, so at lest for NULL children
-       * detection we can only process that one.
-       * This is also a required fix in case `id` would not be in Main anymore, which can happen
-       * e.g. when called from `id_delete`. */
-      Collection *owner_collection = (GS(id->name) == ID_GR) ? (Collection *)id :
-                                                               ((Scene *)id)->master_collection;
-      if (old_id) {
-        switch (GS(old_id->name)) {
-          case ID_OB:
-            libblock_remap_data_postprocess_object_update(
-                bmain, (Object *)old_id, (Object *)new_id);
-            break;
-          case ID_GR:
-            libblock_remap_data_postprocess_collection_update(
-                bmain, owner_collection, (Collection *)old_id, (Collection *)new_id);
-            break;
-          default:
-            break;
-        }
-      }
-      else {
-        /* No choice but to check whole objects/collections. */
-        libblock_remap_data_postprocess_collection_update(bmain, owner_collection, NULL, NULL);
-        libblock_remap_data_postprocess_object_update(bmain, NULL, NULL);
-      }
-      break;
-    }
-    case ID_OB:
-      if (new_id) { /* Only affects us in case obdata was relinked (changed). */
-        libblock_remap_data_postprocess_obdata_relink(bmain, (Object *)id, new_id);
-      }
-      break;
-    default:
-      break;
-  }
+  BKE_libblock_relink_multiple(bmain, &ids, remap_type, id_remapper, remap_flags);
 
-  DEG_relations_tag_update(bmain);
+  BKE_id_remapper_free(id_remapper);
 }
 
 static void libblock_relink_to_newid(Main *bmain, ID *id, const int remap_flag);