LibOverride: Add 'hierarchy root ID' info.

This change will make handling of liboverrides hierarchies (especially
resyncing) much easier and efficient. It should also make it more
resilient to 'degenerate' cases, and allow proper support of things like
parenting an override to another override of the same linked data (e.g.
a override character parented to another override of the same
character).

NOTE: this commit only implements minimal changes to add that data and
generate it for existing files on load. Actual refactor of resync code
to take advantage of this new info will happen separately.

9 files changed, 237 insertions, 7 deletions

diff --git a/source/blender/blenkernel/BKE_blender_version.h b/source/blender/blenkernel/BKE_blender_version.h
index fe656166ada..1ba887903c8 100644
--- a/source/blender/blenkernel/BKE_blender_version.h
+++ b/source/blender/blenkernel/BKE_blender_version.h
@@ -39,7 +39,7 @@ extern "C" {
 
 /* Blender file format version. */
 #define BLENDER_FILE_VERSION BLENDER_VERSION
-#define BLENDER_FILE_SUBVERSION 2
+#define BLENDER_FILE_SUBVERSION 3
 
 /* 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
diff --git a/source/blender/blenkernel/BKE_lib_override.h b/source/blender/blenkernel/BKE_lib_override.h
index e8065566c97..e24f8dd8927 100644
--- a/source/blender/blenkernel/BKE_lib_override.h
+++ b/source/blender/blenkernel/BKE_lib_override.h
@@ -113,7 +113,7 @@ struct ID *BKE_lib_override_library_create_from_id(struct Main *bmain,
  */
 bool BKE_lib_override_library_create_from_tag(struct Main *bmain,
                                               struct Library *owner_library,
-                                              const struct Library *reference_library,
+                                              const struct ID *id_root_reference,
                                               bool do_no_main);
 /**
  * Advanced 'smart' function to create fully functional overrides.
@@ -172,6 +172,15 @@ bool BKE_lib_override_library_proxy_convert(struct Main *bmain,
  */
 void BKE_lib_override_library_main_proxy_convert(struct Main *bmain,
                                                  struct BlendFileReadReport *reports);
+
+/**
+ * Find and set the 'hierarchy root' ID pointer of all library overrides in given `bmain`.
+ *
+ * NOTE: Cannot be called from `do_versions_after_linking` as this code needs a single complete
+ * Main database, not a split-by-libraries one.
+ */
+void BKE_lib_override_library_main_hierarchy_root_ensure(struct Main *bmain);
+
 /**
  * Advanced 'smart' function to resync, re-create fully functional overrides up-to-date with linked
  * data, from an existing override hierarchy.
diff --git a/source/blender/blenkernel/intern/blendfile.c b/source/blender/blenkernel/intern/blendfile.c
index 86c2593e2e6..07fd859765a 100644
--- a/source/blender/blenkernel/intern/blendfile.c
+++ b/source/blender/blenkernel/intern/blendfile.c
@@ -374,6 +374,10 @@ static void setup_app_data(bContext *C,
     BKE_lib_override_library_main_proxy_convert(bmain, reports);
   }
 
+  if (mode != LOAD_UNDO && !blendfile_or_libraries_versions_atleast(bmain, 302, 3)) {
+    BKE_lib_override_library_main_hierarchy_root_ensure(bmain);
+  }
+
   bmain->recovered = 0;
 
   /* startup.blend or recovered startup */
diff --git a/source/blender/blenkernel/intern/lib_override.c b/source/blender/blenkernel/intern/lib_override.c
index 314351e4ad7..a4cd057d7a9 100644
--- a/source/blender/blenkernel/intern/lib_override.c
+++ b/source/blender/blenkernel/intern/lib_override.c
@@ -161,6 +161,8 @@ void BKE_lib_override_library_copy(ID *dst_id, const ID *src_id, const bool do_f
                                             (ID *)src_id;
   id_us_plus(dst_id->override_library->reference);
 
+  dst_id->override_library->hierarchy_root = src_id->override_library->hierarchy_root;
+
   if (do_full_copy) {
     BLI_duplicatelist(&dst_id->override_library->properties,
                       &src_id->override_library->properties);
@@ -293,6 +295,7 @@ ID *BKE_lib_override_library_create_from_id(Main *bmain,
    * mess in case there are a lot of hidden, non-instantiated, non-properly organized dependencies.
    * Ref T94650. */
   local_id->override_library->flag |= IDOVERRIDE_LIBRARY_FLAG_NO_HIERARCHY;
+  local_id->override_library->hierarchy_root = local_id;
 
   if (do_tagged_remap) {
     Key *reference_key, *local_key = NULL;
@@ -328,9 +331,11 @@ ID *BKE_lib_override_library_create_from_id(Main *bmain,
 
 bool BKE_lib_override_library_create_from_tag(Main *bmain,
                                               Library *owner_library,
-                                              const Library *reference_library,
+                                              const ID *id_root_reference,
                                               const bool do_no_main)
 {
+  const Library *reference_library = id_root_reference->lib;
+
   ID *reference_id;
   bool success = true;
 
@@ -383,6 +388,8 @@ bool BKE_lib_override_library_create_from_tag(Main *bmain,
   /* Only remap new local ID's pointers, we don't want to force our new overrides onto our whole
    * existing linked IDs usages. */
   if (success) {
+    ID *hierarchy_root_id = id_root_reference->newid;
+
     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;
@@ -391,6 +398,8 @@ bool BKE_lib_override_library_create_from_tag(Main *bmain,
         continue;
       }
 
+      local_id->override_library->hierarchy_root = hierarchy_root_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);
@@ -865,7 +874,10 @@ static bool lib_override_library_create_do(Main *bmain,
   BKE_main_relations_free(bmain);
   lib_override_group_tag_data_clear(&data);
 
-  return BKE_lib_override_library_create_from_tag(bmain, owner_library, id_root->lib, false);
+  const bool success = BKE_lib_override_library_create_from_tag(
+      bmain, owner_library, id_root, false);
+
+  return success;
 }
 
 static void lib_override_library_create_post_process(Main *bmain,
@@ -1047,6 +1059,189 @@ bool BKE_lib_override_library_template_create(struct ID *id)
   return true;
 }
 
+static ID *lib_override_root_find(Main *bmain, ID *id, const int curr_level, int *r_best_level)
+{
+  if (curr_level > 1000) {
+    CLOG_ERROR(&LOG,
+               "Levels of dependency relationships between library overrides IDs is way too high, "
+               "skipping further processing loops (involves at least '%s')",
+               id->name);
+    BLI_assert(0);
+    return NULL;
+  }
+
+  if (!ID_IS_OVERRIDE_LIBRARY(id)) {
+    BLI_assert(0);
+    return NULL;
+  }
+
+  MainIDRelationsEntry *entry = BLI_ghash_lookup(bmain->relations->relations_from_pointers, id);
+  BLI_assert(entry != NULL);
+
+  int best_level_candidate = curr_level;
+  ID *best_root_id_candidate = id;
+
+  for (MainIDRelationsEntryItem *from_id_entry = entry->from_ids; from_id_entry != NULL;
+       from_id_entry = from_id_entry->next) {
+    if ((from_id_entry->usage_flag & IDWALK_CB_OVERRIDE_LIBRARY_NOT_OVERRIDABLE) != 0) {
+      /* Never consider non-overridable relationships as actual dependencies. */
+      continue;
+    }
+
+    ID *from_id = from_id_entry->id_pointer.from;
+    if (ELEM(from_id, NULL, id)) {
+      continue;
+    }
+    if (!ID_IS_OVERRIDE_LIBRARY(from_id) || (from_id->lib != id->lib)) {
+      continue;
+    }
+
+    int level_candidate = curr_level + 1;
+    /* Recursively process the parent. */
+    ID *root_id_candidate = lib_override_root_find(
+        bmain, from_id, curr_level + 1, &level_candidate);
+    if (level_candidate > best_level_candidate && root_id_candidate != NULL) {
+      best_root_id_candidate = root_id_candidate;
+      best_level_candidate = level_candidate;
+    }
+  }
+
+  *r_best_level = best_level_candidate;
+  return best_root_id_candidate;
+}
+
+static void lib_override_root_hierarchy_set(Main *bmain, ID *id_root, ID *id, ID *id_from)
+{
+  if (ID_IS_OVERRIDE_LIBRARY_REAL(id)) {
+    if (id->override_library->hierarchy_root == id_root) {
+      /* Already set, nothing else to do here, sub-hierarchy is also assumed to be properly set
+       * then. */
+      return;
+    }
+
+    /* Hierarchy root already set, and not matching currently propsed one, try to find which is
+     * best. */
+    if (id->override_library->hierarchy_root != NULL) {
+      /* Check if given `id_from` matches with the hierarchy of the linked reference ID, in which
+       * case we assume that the given hierarchy root is the 'real' one.
+       *
+       * NOTE: This can fail if user mixed dependencies between several overrides of a same
+       * reference linked hierarchy. Not much to be done in that case, it's virtually impossible to
+       * fix this automatically in a reliable way. */
+      if (id_from == NULL || !ID_IS_OVERRIDE_LIBRARY_REAL(id_from)) {
+        /* Too complicated to deal with for now. */
+        CLOG_WARN(&LOG,
+                  "Inconsistency in library override hierarchy of ID '%s'.\n"
+                  "\tNot enough data to verify validity of current proposed root '%s', assuming "
+                  "already set one '%s' is valid.",
+                  id->name,
+                  id_root->name,
+                  id->override_library->hierarchy_root->name);
+        return;
+      }
+
+      ID *id_from_ref = id_from->override_library->reference;
+      MainIDRelationsEntry *entry = BLI_ghash_lookup(bmain->relations->relations_from_pointers,
+                                                     id->override_library->reference);
+      BLI_assert(entry != NULL);
+
+      bool do_replace_root = false;
+      for (MainIDRelationsEntryItem *from_id_entry = entry->from_ids; from_id_entry != NULL;
+           from_id_entry = from_id_entry->next) {
+        if ((from_id_entry->usage_flag & IDWALK_CB_OVERRIDE_LIBRARY_NOT_OVERRIDABLE) != 0) {
+          /* Never consider non-overridable relationships as actual dependencies. */
+          continue;
+        }
+
+        if (id_from_ref == from_id_entry->id_pointer.from) {
+          /* A matching parent was found in reference linked data, assume given hierarchy root is
+           * the valid one. */
+          do_replace_root = true;
+          CLOG_WARN(
+              &LOG,
+              "Inconsistency in library override hierarchy of ID '%s'.\n"
+              "\tCurrent proposed root '%s' detected as valid, will replace already set one '%s'.",
+              id->name,
+              id_root->name,
+              id->override_library->hierarchy_root->name);
+          break;
+        }
+      }
+
+      if (!do_replace_root) {
+        CLOG_WARN(
+            &LOG,
+            "Inconsistency in library override hierarchy of ID '%s'.\n"
+            "\tCurrent proposed root '%s' not detected as valid, keeping already set one '%s'.",
+            id->name,
+            id_root->name,
+            id->override_library->hierarchy_root->name);
+        return;
+      }
+    }
+
+    id->override_library->hierarchy_root = id_root;
+  }
+
+  MainIDRelationsEntry *entry = BLI_ghash_lookup(bmain->relations->relations_from_pointers, id);
+  BLI_assert(entry != NULL);
+
+  for (MainIDRelationsEntryItem *to_id_entry = entry->to_ids; to_id_entry != NULL;
+       to_id_entry = to_id_entry->next) {
+    if ((to_id_entry->usage_flag & IDWALK_CB_OVERRIDE_LIBRARY_NOT_OVERRIDABLE) != 0) {
+      /* Never consider non-overridable relationships as actual dependencies. */
+      continue;
+    }
+
+    ID *to_id = *to_id_entry->id_pointer.to;
+    if (ELEM(to_id, NULL, id)) {
+      continue;
+    }
+    if (!ID_IS_OVERRIDE_LIBRARY(to_id) || (to_id->lib != id->lib)) {
+      continue;
+    }
+
+    /* Recursively process the sub-hierarchy. */
+    lib_override_root_hierarchy_set(bmain, id_root, to_id, id);
+  }
+}
+
+void BKE_lib_override_library_main_hierarchy_root_ensure(Main *bmain)
+{
+  ID *id;
+
+  BKE_main_relations_create(bmain, 0);
+
+  FOREACH_MAIN_ID_BEGIN (bmain, id) {
+    if (!ID_IS_OVERRIDE_LIBRARY_REAL(id)) {
+      continue;
+    }
+    if (id->override_library->hierarchy_root != NULL) {
+      continue;
+    }
+
+    int best_level = 0;
+    ID *id_root = lib_override_root_find(bmain, id, best_level, &best_level);
+
+    if (!ELEM(id_root->override_library->hierarchy_root, id_root, NULL)) {
+      CLOG_WARN(&LOG,
+                "Potential inconsistency in library override hierarchy of ID '%s', detected as "
+                "part of the hierarchy of '%s', which has a different root '%s'",
+                id->name,
+                id_root->name,
+                id_root->override_library->hierarchy_root->name);
+      continue;
+    }
+
+    lib_override_root_hierarchy_set(bmain, id_root, id_root, NULL);
+
+    BLI_assert(id->override_library->hierarchy_root != NULL);
+  }
+  FOREACH_MAIN_ID_END;
+
+  BKE_main_relations_free(bmain);
+}
+
 static void lib_override_library_remap(Main *bmain,
                                        const ID *id_root_reference,
                                        GHash *linkedref_to_old_override)
@@ -1214,7 +1409,7 @@ static bool lib_override_library_resync(Main *bmain,
    * override IDs (including within the old overrides themselves, since those are tagged too
    * above). */
   const bool success = BKE_lib_override_library_create_from_tag(
-      bmain, NULL, id_root_reference->lib, true);
+      bmain, NULL, id_root_reference, true);
 
   if (!success) {
     return success;
diff --git a/source/blender/blenkernel/intern/lib_query.c b/source/blender/blenkernel/intern/lib_query.c
index f69fba5b540..f49af9abffe 100644
--- a/source/blender/blenkernel/intern/lib_query.c
+++ b/source/blender/blenkernel/intern/lib_query.c
@@ -323,6 +323,8 @@ static bool library_foreach_ID_link(Main *bmain,
                          IDWALK_CB_USER | IDWALK_CB_OVERRIDE_LIBRARY_REFERENCE);
       CALLBACK_INVOKE_ID(id->override_library->storage,
                          IDWALK_CB_USER | IDWALK_CB_OVERRIDE_LIBRARY_REFERENCE);
+
+      CALLBACK_INVOKE_ID(id->override_library->hierarchy_root, IDWALK_CB_LOOPBACK);
     }
 
     IDP_foreach_property(id->properties,
diff --git a/source/blender/blenloader/intern/readfile.c b/source/blender/blenloader/intern/readfile.c
index 90366f5b80d..6757177a385 100644
--- a/source/blender/blenloader/intern/readfile.c
+++ b/source/blender/blenloader/intern/readfile.c
@@ -1999,6 +1999,7 @@ static void lib_link_id(BlendLibReader *reader, ID *id)
   if (id->override_library) {
     BLO_read_id_address(reader, id->lib, &id->override_library->reference);
     BLO_read_id_address(reader, id->lib, &id->override_library->storage);
+    BLO_read_id_address(reader, id->lib, &id->override_library->hierarchy_root);
   }
 
   lib_link_id_embedded_id(reader, id);
diff --git a/source/blender/editors/interface/interface_templates.c b/source/blender/editors/interface/interface_templates.c
index 1f81dd21b83..03d0cba5ec8 100644
--- a/source/blender/editors/interface/interface_templates.c
+++ b/source/blender/editors/interface/interface_templates.c
@@ -667,6 +667,13 @@ static void template_id_cb(bContext *C, void *arg_litem, void *arg_event)
 
               /* Assign new pointer, takes care of updates/notifiers */
               RNA_id_pointer_create(override_id, &idptr);
+              /* Insert into override hierarchy if possible. */
+              ID *owner_id = template_ui->ptr.owner_id;
+              if (owner_id != NULL && ID_IS_OVERRIDE_LIBRARY_REAL(owner_id)) {
+                override_id->override_library->hierarchy_root =
+                    owner_id->override_library->hierarchy_root;
+                owner_id->override_library->flag &= ~IDOVERRIDE_LIBRARY_FLAG_NO_HIERARCHY;
+              }
             }
             undo_push_label = "Make Library Override";
           }
diff --git a/source/blender/makesdna/DNA_ID.h b/source/blender/makesdna/DNA_ID.h
index 4f479abe2b0..cfee35e147a 100644
--- a/source/blender/makesdna/DNA_ID.h
+++ b/source/blender/makesdna/DNA_ID.h
@@ -310,6 +310,13 @@ typedef struct IDOverrideLibrary {
   /** List of IDOverrideLibraryProperty structs. */
   ListBase properties;
 
+  /** Override hierarchy root ID. Usually the actual root of the hierarchy, but not always
+   * in degenerated cases.
+   *
+   * All liboverrides of a same hierarchy (e.g. a character collection) share the same root.
+   */
+  struct ID *hierarchy_root;
+
   /* Read/write data. */
   /* Temp ID storing extra override data (used for differential operations only currently).
    * Always NULL outside of read/write context. */
@@ -317,8 +324,6 @@ typedef struct IDOverrideLibrary {
 
   IDOverrideLibraryRuntime *runtime;
 
-  void *_pad_0;
-
   unsigned int flag;
   char _pad_1[4];
 } IDOverrideLibrary;
diff --git a/source/blender/makesrna/intern/rna_ID.c b/source/blender/makesrna/intern/rna_ID.c
index 9bb78cb483d..e7f885b2160 100644
--- a/source/blender/makesrna/intern/rna_ID.c
+++ b/source/blender/makesrna/intern/rna_ID.c
@@ -1822,6 +1822,13 @@ static void rna_def_ID_override_library(BlenderRNA *brna)
       srna, "reference", "ID", "Reference ID", "Linked ID used as reference by this override");
   RNA_def_property_update(prop, NC_WM | ND_LIB_OVERRIDE_CHANGED, NULL);
 
+  RNA_def_pointer(
+      srna,
+      "hierarchy_root",
+      "ID",
+      "Hierarchy Root ID",
+      "Library override ID used as root of the override hierarchy this ID is a member of");
+
   prop = RNA_def_boolean(srna,
                          "is_in_hierarchy",
                          true,