LibOverrides: Refactor how diffing of RNA collections is handled.

Original implementation was a quick prototype which should have never
landed as-is in master. It had very limiting constraints and did not
allow for any real further development.

This commit fixes the internal implementation to make more sensible,
maintainable and evolutive.

NOTE: This commit introduces another forward-incompatibility in the
Blender file format: Files saved after this commit won't open properly
in older versions of blender regarding local inserted constraints or
modifiers into overrides of linked data.

NOTE: Technical details: The 'anchor' item name/index is now stored in
`subitem_reference_` members, and the actual 'source' item name/index is
stored in `subitem_local_` members of the override property operation
data.
Previously, only the `subitem_local_` members were used, storing the
anchor item name/index, and assuming the 'source' item was always the
next in the list.

Milestone I of T82160.

Maniphest Tasks: T82160

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

7 files changed, 232 insertions, 100 deletions

diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index 6bdec0d70f3..326ca746292 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -39,13 +39,13 @@ extern "C" {
 
 /* Blender file format version. */
 #define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 41
+#define BLENDER_FILE_SUBVERSION 42
 
 /* Minimum Blender version that supports reading file written with the current
  * version. Older Blender versions will test this and show a warning if the file
  * was written with too new a version. */
 #define BLENDER_FILE_MIN_VERSION 300
-#define BLENDER_FILE_MIN_SUBVERSION 36
+#define BLENDER_FILE_MIN_SUBVERSION 42
 
 /** User readable version string. */
 const char *BKE_blender_version_string(void);
diff --git a/source/blender/blenloader/intern/versioning_300.c b/source/blender/blenloader/intern/versioning_300.c
index 98264883507..18baebf57fb 100644
--- a/source/blender/blenloader/intern/versioning_300.c
+++ b/source/blender/blenloader/intern/versioning_300.c
@@ -22,6 +22,8 @@
 
 #include <string.h>
 
+#include "CLG_log.h"
+
 #include "MEM_guardedalloc.h"
 
 #include "BLI_listbase.h"
@@ -46,6 +48,7 @@
 #include "DNA_workspace_types.h"
 
 #include "BKE_action.h"
+#include "BKE_anim_data.h"
 #include "BKE_animsys.h"
 #include "BKE_armature.h"
 #include "BKE_asset.h"
@@ -55,6 +58,7 @@
 #include "BKE_fcurve_driver.h"
 #include "BKE_idprop.h"
 #include "BKE_lib_id.h"
+#include "BKE_lib_override.h"
 #include "BKE_main.h"
 #include "BKE_modifier.h"
 #include "BKE_node.h"
@@ -74,6 +78,8 @@
 
 #include "versioning_common.h"
 
+static CLG_LogRef LOG = {"blo.readfile.doversion"};
+
 static IDProperty *idproperty_find_ui_container(IDProperty *idprop_group)
 {
   LISTBASE_FOREACH (IDProperty *, prop, &idprop_group->data.group) {
@@ -1282,6 +1288,140 @@ static bool version_fix_seq_meta_range(Sequence *seq, void *user_data)
   return true;
 }
 
+/* Those `version_liboverride_rnacollections_*` functions mimic the old, pre-3.0 code to find
+ * anchor and source items in the given list of modifiers, constraints etc., using only the
+ * `subitem_local` data of the override property operation.
+ *
+ * Then they convert it into the new, proper `subitem_reference` data for the anchor, and
+ * `subitem_local` for the source.
+ *
+ * NOTE: Here only the stored override ID is available, unlike in the `override_apply` functions.
+ */
+
+static void version_liboverride_rnacollections_insertion_object_constraints(
+    ListBase *constraints, IDOverrideLibraryProperty *op)
+{
+  LISTBASE_FOREACH_MUTABLE (IDOverrideLibraryPropertyOperation *, opop, &op->operations) {
+    if (opop->operation != IDOVERRIDE_LIBRARY_OP_INSERT_AFTER) {
+      continue;
+    }
+    bConstraint *constraint_anchor = BLI_listbase_string_or_index_find(constraints,
+                                                                       opop->subitem_local_name,
+                                                                       offsetof(bConstraint, name),
+                                                                       opop->subitem_local_index);
+    if (constraint_anchor == NULL || constraint_anchor->next == NULL) {
+      /* Invalid case, just remove that override property operation. */
+      CLOG_ERROR(&LOG, "Could not find anchor or source constraints in stored override data");
+      BKE_lib_override_library_property_operation_delete(op, opop);
+      continue;
+    }
+    bConstraint *constraint_src = constraint_anchor->next;
+    opop->subitem_reference_name = opop->subitem_local_name;
+    opop->subitem_local_name = BLI_strdup(constraint_src->name);
+    opop->subitem_reference_index = opop->subitem_local_index;
+    opop->subitem_local_index++;
+  }
+}
+
+static void version_liboverride_rnacollections_insertion_object(Object *object)
+{
+  IDOverrideLibrary *liboverride = object->id.override_library;
+  IDOverrideLibraryProperty *op;
+
+  op = BKE_lib_override_library_property_find(liboverride, "modifiers");
+  if (op != NULL) {
+    LISTBASE_FOREACH_MUTABLE (IDOverrideLibraryPropertyOperation *, opop, &op->operations) {
+      if (opop->operation != IDOVERRIDE_LIBRARY_OP_INSERT_AFTER) {
+        continue;
+      }
+      ModifierData *mod_anchor = BLI_listbase_string_or_index_find(&object->modifiers,
+                                                                   opop->subitem_local_name,
+                                                                   offsetof(ModifierData, name),
+                                                                   opop->subitem_local_index);
+      if (mod_anchor == NULL || mod_anchor->next == NULL) {
+        /* Invalid case, just remove that override property operation. */
+        CLOG_ERROR(&LOG, "Could not find anchor or source modifiers in stored override data");
+        BKE_lib_override_library_property_operation_delete(op, opop);
+        continue;
+      }
+      ModifierData *mod_src = mod_anchor->next;
+      opop->subitem_reference_name = opop->subitem_local_name;
+      opop->subitem_local_name = BLI_strdup(mod_src->name);
+      opop->subitem_reference_index = opop->subitem_local_index;
+      opop->subitem_local_index++;
+    }
+  }
+
+  op = BKE_lib_override_library_property_find(liboverride, "grease_pencil_modifiers");
+  if (op != NULL) {
+    LISTBASE_FOREACH_MUTABLE (IDOverrideLibraryPropertyOperation *, opop, &op->operations) {
+      if (opop->operation != IDOVERRIDE_LIBRARY_OP_INSERT_AFTER) {
+        continue;
+      }
+      GpencilModifierData *gp_mod_anchor = BLI_listbase_string_or_index_find(
+          &object->greasepencil_modifiers,
+          opop->subitem_local_name,
+          offsetof(GpencilModifierData, name),
+          opop->subitem_local_index);
+      if (gp_mod_anchor == NULL || gp_mod_anchor->next == NULL) {
+        /* Invalid case, just remove that override property operation. */
+        CLOG_ERROR(&LOG, "Could not find anchor GP modifier in stored override data");
+        BKE_lib_override_library_property_operation_delete(op, opop);
+        continue;
+      }
+      GpencilModifierData *gp_mod_src = gp_mod_anchor->next;
+      opop->subitem_reference_name = opop->subitem_local_name;
+      opop->subitem_local_name = BLI_strdup(gp_mod_src->name);
+      opop->subitem_reference_index = opop->subitem_local_index;
+      opop->subitem_local_index++;
+    }
+  }
+
+  op = BKE_lib_override_library_property_find(liboverride, "constraints");
+  if (op != NULL) {
+    version_liboverride_rnacollections_insertion_object_constraints(&object->constraints, op);
+  }
+
+  if (object->pose != NULL) {
+    LISTBASE_FOREACH (bPoseChannel *, pchan, &object->pose->chanbase) {
+      char rna_path[FILE_MAXFILE];
+      BLI_snprintf(rna_path, sizeof(rna_path), "pose.bones[\"%s\"].constraints", pchan->name);
+      op = BKE_lib_override_library_property_find(liboverride, rna_path);
+      if (op != NULL) {
+        version_liboverride_rnacollections_insertion_object_constraints(&pchan->constraints, op);
+      }
+    }
+  }
+}
+
+static void version_liboverride_rnacollections_insertion_animdata(ID *id)
+{
+  AnimData *anim_data = BKE_animdata_from_id(id);
+  if (anim_data == NULL) {
+    return;
+  }
+
+  IDOverrideLibrary *liboverride = id->override_library;
+  IDOverrideLibraryProperty *op;
+
+  op = BKE_lib_override_library_property_find(liboverride, "animation_data.nla_tracks");
+  if (op != NULL) {
+    LISTBASE_FOREACH (IDOverrideLibraryPropertyOperation *, opop, &op->operations) {
+      if (opop->operation != IDOVERRIDE_LIBRARY_OP_INSERT_AFTER) {
+        continue;
+      }
+      /* NLA tracks are only referenced by index, which limits possibilities, basically they are
+       * always added at the end of the list, see #rna_NLA_tracks_override_apply.
+       *
+       * This makes things simple here. */
+      opop->subitem_reference_name = opop->subitem_local_name;
+      opop->subitem_local_name = NULL;
+      opop->subitem_reference_index = opop->subitem_local_index;
+      opop->subitem_local_index++;
+    }
+  }
+}
+
 /* NOLINTNEXTLINE: readability-function-size */
 void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
 {
@@ -2158,16 +2298,20 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
     }
   }
 
-  /**
-   * Versioning code until next subversion bump goes here.
-   *
-   * \note Be sure to check when bumping the version:
-   * - "versioning_userdef.c", #blo_do_versions_userdef
-   * - "versioning_userdef.c", #do_versions_theme
-   *
-   * \note Keep this message at the bottom of the function.
-   */
-  {
+  if (!MAIN_VERSION_ATLEAST(bmain, 300, 42)) {
+    /* Update LibOverride operations regarding insertions in RNA collections (i.e. modifiers,
+     * constraints and NLA tracks). */
+    ID *id_iter;
+    FOREACH_MAIN_ID_BEGIN (bmain, id_iter) {
+      if (ID_IS_OVERRIDE_LIBRARY_REAL(id_iter)) {
+        version_liboverride_rnacollections_insertion_animdata(id_iter);
+        if (GS(id_iter->name) == ID_OB) {
+          version_liboverride_rnacollections_insertion_object((Object *)id_iter);
+        }
+      }
+    }
+    FOREACH_MAIN_ID_END;
+
     /* Use consistent socket identifiers for the math node.
      * The code to make unique identifiers from the names was inconsistent. */
     FOREACH_NODETREE_BEGIN (bmain, ntree, id) {
@@ -2215,4 +2359,16 @@ void blo_do_versions_300(FileData *fd, Library *UNUSED(lib), Main *bmain)
       }
     }
   }
+
+  /**
+   * Versioning code until next subversion bump goes here.
+   *
+   * \note Be sure to check when bumping the version:
+   * - "versioning_userdef.c", #blo_do_versions_userdef
+   * - "versioning_userdef.c", #do_versions_theme
+   *
+   * \note Keep this message at the bottom of the function.
+   */
+  {
+  }
 }
diff --git a/source/blender/makesdna/DNA_ID.h b/source/blender/makesdna/DNA_ID.h
index d829d707a71..2c04d0b06ef 100644
--- a/source/blender/makesdna/DNA_ID.h
+++ b/source/blender/makesdna/DNA_ID.h
@@ -211,11 +211,15 @@ typedef struct IDOverrideLibraryPropertyOperation {
   char _pad0[2];
 
   /* Sub-item references, if needed (for arrays or collections only).
-   * We need both reference and local values to allow e.g. insertion into collections
+   * We need both reference and local values to allow e.g. insertion into RNA collections
    * (constraints, modifiers...).
-   * In collection case, if names are defined, they are used in priority.
-   * Names are pointers (instead of char[64]) to save some space, NULL when unset.
-   * Indices are -1 when unset. */
+   * In RNA collection case, if names are defined, they are used in priority.
+   * Names are pointers (instead of char[64]) to save some space, NULL or empty string when unset.
+   * Indices are -1 when unset.
+   *
+   * NOTE: For insertion operations in RNA collections, reference may not actually exist in the
+   * linked reference data. It is used to identify the anchor of the insertion operation (i.e. the
+   * item after or before which the new local item should be inserted), in the local override. */
   char *subitem_reference_name;
   char *subitem_local_name;
   int subitem_reference_index;
diff --git a/source/blender/makesrna/intern/rna_animation.c b/source/blender/makesrna/intern/rna_animation.c
index 52c25bae45a..9068fdb6e72 100644
--- a/source/blender/makesrna/intern/rna_animation.c
+++ b/source/blender/makesrna/intern/rna_animation.c
@@ -761,8 +761,8 @@ bool rna_NLA_tracks_override_apply(Main *bmain,
   /* This is not working so well with index-based insertion, especially in case some tracks get
    * added to lib linked data. So we simply add locale tracks at the end of the list always, order
    * of override operations should ensure order of local tracks is preserved properly. */
-  if (opop->subitem_local_index >= 0) {
-    nla_track_anchor = BLI_findlink(&anim_data_dst->nla_tracks, opop->subitem_local_index);
+  if (opop->subitem_reference_index >= 0) {
+    nla_track_anchor = BLI_findlink(&anim_data_dst->nla_tracks, opop->subitem_reference_index);
   }
   /* Otherwise we just insert in first position. */
 #  else
@@ -773,9 +773,11 @@ bool rna_NLA_tracks_override_apply(Main *bmain,
   if (opop->subitem_local_index >= 0) {
     nla_track_src = BLI_findlink(&anim_data_src->nla_tracks, opop->subitem_local_index);
   }
-  nla_track_src = nla_track_src ? nla_track_src->next : anim_data_src->nla_tracks.first;
 
-  BLI_assert(nla_track_src != NULL);
+  if (nla_track_src == NULL) {
+    BLI_assert(nla_track_src != NULL);
+    return false;
+  }
 
   NlaTrack *nla_track_dst = BKE_nlatrack_copy(bmain, nla_track_src, true, 0);
 
diff --git a/source/blender/makesrna/intern/rna_object.c b/source/blender/makesrna/intern/rna_object.c
index bf64196c8ab..0cb132786cd 100644
--- a/source/blender/makesrna/intern/rna_object.c
+++ b/source/blender/makesrna/intern/rna_object.c
@@ -1705,27 +1705,20 @@ bool rna_Object_constraints_override_apply(Main *UNUSED(bmain),
   /* Remember that insertion operations are defined and stored in correct order, which means that
    * even if we insert several items in a row, we always insert first one, then second one, etc.
    * So we should always find 'anchor' constraint in both _src *and* _dst. */
-  bConstraint *con_anchor = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    con_anchor = BLI_findstring(
-        &ob_dst->constraints, opop->subitem_local_name, offsetof(bConstraint, name));
-  }
-  if (con_anchor == NULL && opop->subitem_local_index >= 0) {
-    con_anchor = BLI_findlink(&ob_dst->constraints, opop->subitem_local_index);
-  }
-  /* Otherwise we just insert in first position. */
-
-  bConstraint *con_src = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    con_src = BLI_findstring(
-        &ob_src->constraints, opop->subitem_local_name, offsetof(bConstraint, name));
-  }
-  if (con_src == NULL && opop->subitem_local_index >= 0) {
-    con_src = BLI_findlink(&ob_src->constraints, opop->subitem_local_index);
+  const size_t name_offset = offsetof(bConstraint, name);
+  bConstraint *con_anchor = BLI_listbase_string_or_index_find(&ob_dst->constraints,
+                                                              opop->subitem_reference_name,
+                                                              name_offset,
+                                                              opop->subitem_reference_index);
+  /* If `con_anchor` is NULL, `con_src` will be inserted in first position. */
+
+  bConstraint *con_src = BLI_listbase_string_or_index_find(
+      &ob_src->constraints, opop->subitem_local_name, name_offset, opop->subitem_local_index);
+
+  if (con_src == NULL) {
+    BLI_assert(con_src != NULL);
+    return false;
   }
-  con_src = con_src ? con_src->next : ob_src->constraints.first;
-
-  BLI_assert(con_src != NULL);
 
   bConstraint *con_dst = BKE_constraint_duplicate_ex(con_src, 0, true);
 
@@ -1827,25 +1820,15 @@ bool rna_Object_modifiers_override_apply(Main *bmain,
   /* Remember that insertion operations are defined and stored in correct order, which means that
    * even if we insert several items in a row, we always insert first one, then second one, etc.
    * So we should always find 'anchor' modifier in both _src *and* _dst. */
-  ModifierData *mod_anchor = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    mod_anchor = BLI_findstring(
-        &ob_dst->modifiers, opop->subitem_local_name, offsetof(ModifierData, name));
-  }
-  if (mod_anchor == NULL && opop->subitem_local_index >= 0) {
-    mod_anchor = BLI_findlink(&ob_dst->modifiers, opop->subitem_local_index);
-  }
-  /* Otherwise we just insert in first position. */
+  const size_t name_offset = offsetof(ModifierData, name);
+  ModifierData *mod_anchor = BLI_listbase_string_or_index_find(&ob_dst->modifiers,
+                                                               opop->subitem_reference_name,
+                                                               name_offset,
+                                                               opop->subitem_reference_index);
+  /* If `mod_anchor` is NULL, `mod_src` will be inserted in first position. */
 
-  ModifierData *mod_src = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    mod_src = BLI_findstring(
-        &ob_src->modifiers, opop->subitem_local_name, offsetof(ModifierData, name));
-  }
-  if (mod_src == NULL && opop->subitem_local_index >= 0) {
-    mod_src = BLI_findlink(&ob_src->modifiers, opop->subitem_local_index);
-  }
-  mod_src = mod_src ? mod_src->next : ob_src->modifiers.first;
+  ModifierData *mod_src = BLI_listbase_string_or_index_find(
+      &ob_src->modifiers, opop->subitem_local_name, name_offset, opop->subitem_local_index);
 
   if (mod_src == NULL) {
     BLI_assert(mod_src != NULL);
@@ -1934,25 +1917,18 @@ bool rna_Object_greasepencil_modifiers_override_apply(Main *bmain,
   /* Remember that insertion operations are defined and stored in correct order, which means that
    * even if we insert several items in a row, we always insert first one, then second one, etc.
    * So we should always find 'anchor' modifier in both _src *and* _dst. */
-  GpencilModifierData *mod_anchor = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    mod_anchor = BLI_findstring(
-        &ob_dst->greasepencil_modifiers, opop->subitem_local_name, offsetof(ModifierData, name));
-  }
-  if (mod_anchor == NULL && opop->subitem_local_index >= 0) {
-    mod_anchor = BLI_findlink(&ob_dst->greasepencil_modifiers, opop->subitem_local_index);
-  }
-  /* Otherwise we just insert in first position. */
-
-  GpencilModifierData *mod_src = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    mod_src = BLI_findstring(
-        &ob_src->greasepencil_modifiers, opop->subitem_local_name, offsetof(ModifierData, name));
-  }
-  if (mod_src == NULL && opop->subitem_local_index >= 0) {
-    mod_src = BLI_findlink(&ob_src->greasepencil_modifiers, opop->subitem_local_index);
-  }
-  mod_src = mod_src ? mod_src->next : ob_src->greasepencil_modifiers.first;
+  const size_t name_offset = offsetof(GpencilModifierData, name);
+  GpencilModifierData *mod_anchor = BLI_listbase_string_or_index_find(
+      &ob_dst->greasepencil_modifiers,
+      opop->subitem_reference_name,
+      name_offset,
+      opop->subitem_reference_index);
+  /* If `mod_anchor` is NULL, `mod_src` will be inserted in first position. */
+
+  GpencilModifierData *mod_src = BLI_listbase_string_or_index_find(&ob_src->greasepencil_modifiers,
+                                                                   opop->subitem_local_name,
+                                                                   name_offset,
+                                                                   opop->subitem_local_index);
 
   if (mod_src == NULL) {
     BLI_assert(mod_src != NULL);
diff --git a/source/blender/makesrna/intern/rna_pose.c b/source/blender/makesrna/intern/rna_pose.c
index cdf7fe5a7aa..87173adc38f 100644
--- a/source/blender/makesrna/intern/rna_pose.c
+++ b/source/blender/makesrna/intern/rna_pose.c
@@ -682,29 +682,18 @@ bool rna_PoseChannel_constraints_override_apply(Main *UNUSED(bmain),
   /* Remember that insertion operations are defined and stored in correct order, which means that
    * even if we insert several items in a row, we always insert first one, then second one, etc.
    * So we should always find 'anchor' constraint in both _src *and* _dst */
-  bConstraint *con_anchor = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    con_anchor = BLI_findstring(
-        &pchan_dst->constraints, opop->subitem_local_name, offsetof(bConstraint, name));
-  }
-  if (con_anchor == NULL && opop->subitem_local_index >= 0) {
-    con_anchor = BLI_findlink(&pchan_dst->constraints, opop->subitem_local_index);
-  }
-  /* Otherwise we just insert in first position. */
+  const size_t name_offset = offsetof(bConstraint, name);
+  bConstraint *con_anchor = BLI_listbase_string_or_index_find(&pchan_dst->constraints,
+                                                              opop->subitem_reference_name,
+                                                              name_offset,
+                                                              opop->subitem_reference_index);
+  /* If `con_anchor` is NULL, `con_src` will be inserted in first position. */
 
-  bConstraint *con_src = NULL;
-  if (opop->subitem_local_name && opop->subitem_local_name[0]) {
-    con_src = BLI_findstring(
-        &pchan_src->constraints, opop->subitem_local_name, offsetof(bConstraint, name));
-  }
-  if (con_src == NULL && opop->subitem_local_index >= 0) {
-    con_src = BLI_findlink(&pchan_src->constraints, opop->subitem_local_index);
-  }
-  con_src = con_src ? con_src->next : pchan_src->constraints.first;
+  bConstraint *con_src = BLI_listbase_string_or_index_find(
+      &pchan_src->constraints, opop->subitem_local_name, name_offset, opop->subitem_local_index);
 
   if (con_src == NULL) {
-    printf("%s: Could not find constraint to insert, doing nothing...\n", __func__);
-    BLI_assert(0);
+    BLI_assert(con_src != NULL);
     return false;
   }
 
diff --git a/source/blender/makesrna/intern/rna_rna.c b/source/blender/makesrna/intern/rna_rna.c
index 12fb7a40d13..e5009305fe5 100644
--- a/source/blender/makesrna/intern/rna_rna.c
+++ b/source/blender/makesrna/intern/rna_rna.c
@@ -1916,16 +1916,21 @@ int rna_property_override_diff_default(Main *bmain,
 
           /* Collections do not support replacement of their data (except for collections of ID
            * pointers), since they do not support removing, only in *some* cases, insertion. We
-           * also assume then that _a data is the one where things are inserted. */
+           * also assume then that _a data is the one where things are inserted.
+           *
+           * NOTE: In insertion case, both 'local' and 'reference' (aka anchor) sub-item
+           * identifiers refer to collection items in the local override. The 'reference' may match
+           * an item in the linked reference data, but it can also be another local-only item added
+           * by a previous INSERT operation. */
           if (is_valid_for_insertion && use_collection_insertion) {
             op = BKE_lib_override_library_property_get(override, rna_path, &created);
 
             BKE_lib_override_library_property_operation_get(op,
                                                             IDOVERRIDE_LIBRARY_OP_INSERT_AFTER,
-                                                            NULL,
                                                             no_prop_name ? NULL : prev_propname_a,
-                                                            -1,
+                                                            no_prop_name ? NULL : propname_a,
                                                             idx_a - 1,
+                                                            idx_a,
                                                             true,
                                                             NULL,
                                                             NULL);