Outliner, Library Overrides: List child objects under parents

Because children point to, or "use" their parent, the Library Overrides
Hierarchies mode in the Outliner would show parents contained in children, not
children contained in a parent. See D15339 for pictures.

In production files this would make the rig listed under all its children, so
it would appear many times in the tree. Now it appears once and the children
are collected under it.

Refactors the tree building, so instead of using
`BKE_library_foreach_ID_link()`, it now uses the ID relations mapping in
`MainIDRelations`.

Reviewed By: mont29

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

2 files changed, 183 insertions, 82 deletions

diff --git a/source/blender/editors/space_outliner/tree/tree_display.hh b/source/blender/editors/space_outliner/tree/tree_display.hh
index 190e35c81d6..f8e35655c26 100644
--- a/source/blender/editors/space_outliner/tree/tree_display.hh
+++ b/source/blender/editors/space_outliner/tree/tree_display.hh
@@ -161,7 +161,6 @@ class TreeDisplayOverrideLibraryHierarchies final : public AbstractTreeDisplay {
   ListBase build_hierarchy_for_lib_or_main(Main *bmain,
                                            TreeElement &parent_te,
                                            Library *lib = nullptr);
-  void build_hierarchy_for_ID(Main *bmain, ID &override_root_id, TreeElementID &te_id) const;
 };
 
 /* -------------------------------------------------------------------- */
diff --git a/source/blender/editors/space_outliner/tree/tree_display_override_library_hierarchies.cc b/source/blender/editors/space_outliner/tree/tree_display_override_library_hierarchies.cc
index 67798e978ab..f8705c3f0ad 100644
--- a/source/blender/editors/space_outliner/tree/tree_display_override_library_hierarchies.cc
+++ b/source/blender/editors/space_outliner/tree/tree_display_override_library_hierarchies.cc
@@ -4,25 +4,23 @@
  * \ingroup spoutliner
  */
 
-#include "DNA_ID.h"
-#include "DNA_collection_types.h"
 #include "DNA_key_types.h"
 #include "DNA_space_types.h"
 
-#include "BLI_listbase.h"
+#include "BLI_function_ref.hh"
+#include "BLI_ghash.h"
 #include "BLI_map.hh"
+
 #include "BLI_set.hh"
 
 #include "BLT_translation.h"
 
-#include "BKE_collection.h"
 #include "BKE_lib_query.h"
 #include "BKE_main.h"
 
 #include "../outliner_intern.hh"
 #include "common.hh"
 #include "tree_display.hh"
-#include "tree_element_id.hh"
 
 namespace blender::ed::outliner {
 
@@ -42,8 +40,8 @@ ListBase TreeDisplayOverrideLibraryHierarchies::buildTree(const TreeSourceData &
   TreeElement *current_file_te = outliner_add_element(
       &space_outliner_, &tree, source_data.bmain, nullptr, TSE_ID_BASE, -1);
   current_file_te->name = IFACE_("Current File");
+  AbstractTreeElement::uncollapse_by_default(current_file_te);
   {
-    AbstractTreeElement::uncollapse_by_default(current_file_te);
     build_hierarchy_for_lib_or_main(source_data.bmain, *current_file_te);
 
     /* Add dummy child if there's nothing to display. */
@@ -76,11 +74,49 @@ ListBase TreeDisplayOverrideLibraryHierarchies::buildTree(const TreeSourceData &
   return tree;
 }
 
+/* -------------------------------------------------------------------- */
+/** \name Library override hierarchy building
+ * \{ */
+
+class OverrideIDHierarchyBuilder {
+  SpaceOutliner &space_outliner_;
+  MainIDRelations &id_relations_;
+
+  struct HierarchyBuildData {
+    const ID &override_root_id_;
+    /* The ancestor IDs leading to the current ID, to avoid IDs recursing into themselves. Changes
+     * with every level of recursion. */
+    Set<const ID *> parent_ids{};
+    /* The IDs that were already added to #parent_te, to avoid duplicates. Entirely new set with
+     * every level of recursion. */
+    Set<const ID *> sibling_ids{};
+  };
+
+ public:
+  OverrideIDHierarchyBuilder(SpaceOutliner &space_outliner, MainIDRelations &id_relations)
+      : space_outliner_(space_outliner), id_relations_(id_relations)
+  {
+  }
+
+  void build_hierarchy_for_ID(ID &root_id, TreeElement &te_to_expand);
+
+ private:
+  void build_hierarchy_for_ID_recursive(const ID &parent_id,
+                                        HierarchyBuildData &build_data,
+                                        TreeElement &te_to_expand);
+};
+
 ListBase TreeDisplayOverrideLibraryHierarchies::build_hierarchy_for_lib_or_main(
     Main *bmain, TreeElement &parent_te, Library *lib)
 {
   ListBase tree = {nullptr};
 
+  /* Ensure #Main.relations contains the latest mapping of relations. Must be freed before
+   * returning. */
+  BKE_main_relations_create(bmain, 0);
+
+  OverrideIDHierarchyBuilder builder(space_outliner_, *bmain->relations);
+
   /* Keep track over which ID base elements were already added, and expand them once added. */
   Map<ID_Type, TreeElement *> id_base_te_map;
   /* Index for the ID base elements ("Objects", "Materials", etc). */
@@ -109,108 +145,174 @@ ListBase TreeDisplayOverrideLibraryHierarchies::build_hierarchy_for_lib_or_main(
     TreeElement *new_id_te = outliner_add_element(
         &space_outliner_, &new_base_te->subtree, iter_id, new_base_te, TSE_SOME_ID, 0, false);
 
-    build_hierarchy_for_ID(bmain, *iter_id, *tree_element_cast<TreeElementID>(new_id_te));
+    builder.build_hierarchy_for_ID(*iter_id, *new_id_te);
   }
   FOREACH_MAIN_ID_END;
 
+  BKE_main_relations_free(bmain);
+
   return tree;
 }
 
-struct BuildHierarchyForeachIDCbData {
-  /* Don't allow copies, the sets below would need deep copying. */
-  BuildHierarchyForeachIDCbData(const BuildHierarchyForeachIDCbData &) = delete;
-
-  Main &bmain;
-  SpaceOutliner &space_outliner;
-  ID &override_root_id;
-
-  /* The tree element to expand. Changes with every level of recursion. */
-  TreeElementID *parent_te;
-  /* The ancestor IDs leading to the current ID, to avoid IDs recursing into themselves. Changes
-   * with every level of recursion. */
-  Set<ID *> parent_ids{};
-  /* The IDs that were already added to #parent_te, to avoid duplicates. Entirely new set with
-   * every level of recursion. */
-  Set<ID *> sibling_ids{};
-};
+void OverrideIDHierarchyBuilder::build_hierarchy_for_ID(ID &override_root_id,
+                                                        TreeElement &te_to_expand)
+{
+  HierarchyBuildData build_data{override_root_id};
+  build_hierarchy_for_ID_recursive(override_root_id, build_data, te_to_expand);
+}
+
+/* Helpers (defined below). */
+static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
+                                            const ID &parent_id,
+                                            FunctionRef<void(ID &)> fn);
+static bool id_is_in_override_hierarchy(const ID &id,
+                                        const ID &relationship_parent_id,
+                                        const ID &override_root_id);
+
+void OverrideIDHierarchyBuilder::build_hierarchy_for_ID_recursive(const ID &parent_id,
+                                                                  HierarchyBuildData &build_data,
+                                                                  TreeElement &te_to_expand)
+{
+  /* In case this isn't added to the parents yet (does nothing if already there). */
+  build_data.parent_ids.add(&parent_id);
+
+  foreach_natural_hierarchy_child(id_relations_, parent_id, [&](ID &id) {
+    if (!id_is_in_override_hierarchy(id, parent_id, build_data.override_root_id_)) {
+      return;
+    }
+
+    /* Avoid endless recursion: If there is an ancestor for this ID already, it recurses into
+     * itself. */
+    if (build_data.parent_ids.lookup_key_default(&id, nullptr)) {
+      return;
+    }
+
+    /* Avoid duplicates: If there is a sibling for this ID already, the same ID is just used
+     * multiple times by the same parent. */
+    if (build_data.sibling_ids.lookup_key_default(&id, nullptr)) {
+      return;
+    }
+
+    TreeElement *new_te = outliner_add_element(
+        &space_outliner_, &te_to_expand.subtree, &id, &te_to_expand, TSE_SOME_ID, 0, false);
+
+    build_data.sibling_ids.add(&id);
+
+    /* Recurse into this ID. */
+    HierarchyBuildData child_build_data{build_data.override_root_id_};
+    child_build_data.parent_ids = build_data.parent_ids;
+    child_build_data.parent_ids.add(&id);
+    child_build_data.sibling_ids.reserve(10);
+    build_hierarchy_for_ID_recursive(id, child_build_data, *new_te);
+  });
+}
 
-static int build_hierarchy_foreach_ID_cb(LibraryIDLinkCallbackData *cb_data)
+/** \} */
+
+/* -------------------------------------------------------------------- */
+/** \name Helpers for library override hierarchy building
+ * \{ */
+
+/**
+ * Iterate over the IDs \a parent_id uses. E.g. the child collections and contained objects of a
+ * parent collection. Also does special handling for object parenting, so that:
+ * - When iterating over a child object, \a fn is executed for the parent instead.
+ * - When iterating over a parent object, \a fn is _additionally_ executed for all children. Given
+ *   that the parent object isn't skipped, the caller has to ensure it's not added in the hierarchy
+ *   twice.
+ * This allows us to build the hierarchy in the expected ("natural") order, where parent objects
+ * are actual parent elements in the hierarchy, even though in data, the relation goes the other
+ * way around (children point to or "use" the parent).
+ *
+ * Only handles regular object parenting, not cases like the "Child of" constraint. Other Outliner
+ * display modes don't show this as parent in the hierarchy either.
+ */
+static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
+                                            const ID &parent_id,
+                                            FunctionRef<void(ID &)> fn)
 {
-  if (!*cb_data->id_pointer) {
-    return IDWALK_RET_NOP;
+  const MainIDRelationsEntry *relations_of_id = static_cast<MainIDRelationsEntry *>(
+      BLI_ghash_lookup(id_relations.relations_from_pointers, &parent_id));
+
+  /* Iterate over all IDs used by the parent ID (e.g. the child-collections of a collection). */
+  for (MainIDRelationsEntryItem *to_id_entry = relations_of_id->to_ids; to_id_entry;
+       to_id_entry = to_id_entry->next) {
+    /* An ID pointed to (used) by the ID to recurse into. */
+    ID &target_id = **to_id_entry->id_pointer.to;
+
+    /* Don't walk up the hierarchy, e.g. ignore pointers to parent collections. */
+    if (to_id_entry->usage_flag & IDWALK_CB_LOOPBACK) {
+      continue;
+    }
+
+    /* Special case for objects: Process the parent object instead of the child object. Below the
+     * parent will add the child objects then. */
+    if (GS(target_id.name) == ID_OB) {
+      const Object &potential_child_ob = reinterpret_cast<const Object &>(target_id);
+      if (potential_child_ob.parent) {
+        fn(potential_child_ob.parent->id);
+        continue;
+      }
+    }
+
+    fn(target_id);
+  }
+
+  /* If the ID is an object, find and iterate over any child objects. */
+  if (GS(parent_id.name) == ID_OB) {
+    for (MainIDRelationsEntryItem *from_id_entry = relations_of_id->from_ids; from_id_entry;
+         from_id_entry = from_id_entry->next) {
+      ID &potential_child_id = *from_id_entry->id_pointer.from;
+
+      if (GS(potential_child_id.name) != ID_OB) {
+        continue;
+      }
+
+      Object &potential_child_ob = reinterpret_cast<Object &>(potential_child_id);
+      if (potential_child_ob.parent && &potential_child_ob.parent->id == &parent_id) {
+        fn(potential_child_id);
+      }
+    }
   }
+}
 
-  BuildHierarchyForeachIDCbData &build_data = *reinterpret_cast<BuildHierarchyForeachIDCbData *>(
-      cb_data->user_data);
-  /* Note that this may be an embedded ID (see #real_override_id). */
-  ID &id = **cb_data->id_pointer;
+static bool id_is_in_override_hierarchy(const ID &id,
+                                        const ID &relationship_parent_id,
+                                        const ID &override_root_id)
+{
   /* If #id is an embedded ID, this will be set to the owner, which is a real ID and contains the
    * override data. So queries of override data should be done via this, but the actual tree
    * element we add is the embedded ID. */
   const ID *real_override_id = &id;
 
   if (ID_IS_OVERRIDE_LIBRARY_VIRTUAL(&id)) {
+    /* This assumes that the parent ID is always the owner of the 'embedded' one, I.e. that no
+     * other ID directly uses the embedded one. Should be true, but the debug code adds some checks
+     * to validate this assumption. */
+    real_override_id = &relationship_parent_id;
+
+#ifndef NDEBUG
     if (GS(id.name) == ID_KE) {
-      Key *key = (Key *)&id;
-      real_override_id = key->from;
+      const Key *key = (Key *)&id;
+      BLI_assert(real_override_id == key->from);
     }
-    else if (id.flag & LIB_EMBEDDED_DATA) {
-      /* TODO Needs double-checking if this handles all embedded IDs correctly. */
-      real_override_id = cb_data->id_owner;
+    else {
+      BLI_assert((id.flag & LIB_EMBEDDED_DATA) != 0);
     }
+#endif
   }
 
   if (!ID_IS_OVERRIDE_LIBRARY(real_override_id)) {
-    return IDWALK_RET_NOP;
+    return false;
   }
   /* Is this ID part of the same override hierarchy? */
-  if (real_override_id->override_library->hierarchy_root != &build_data.override_root_id) {
-    return IDWALK_RET_NOP;
-  }
-
-  /* Avoid endless recursion: If there is an ancestor for this ID already, it recurses into itself.
-   */
-  if (build_data.parent_ids.lookup_key_default(&id, nullptr)) {
-    return IDWALK_RET_NOP;
-  }
-
-  /* Avoid duplicates: If there is a sibling for this ID already, the same ID is just used multiple
-   * times by the same parent. */
-  if (build_data.sibling_ids.lookup_key_default(&id, nullptr)) {
-    return IDWALK_RET_NOP;
+  if (real_override_id->override_library->hierarchy_root != &override_root_id) {
+    return false;
   }
 
-  TreeElement *new_te = outliner_add_element(&build_data.space_outliner,
-                                             &build_data.parent_te->getLegacyElement().subtree,
-                                             &id,
-                                             &build_data.parent_te->getLegacyElement(),
-                                             TSE_SOME_ID,
-                                             0,
-                                             false);
-  build_data.sibling_ids.add(&id);
-
-  BuildHierarchyForeachIDCbData child_build_data{build_data.bmain,
-                                                 build_data.space_outliner,
-                                                 build_data.override_root_id,
-                                                 tree_element_cast<TreeElementID>(new_te)};
-  child_build_data.parent_ids = build_data.parent_ids;
-  child_build_data.parent_ids.add(&id);
-  child_build_data.sibling_ids.reserve(10);
-  BKE_library_foreach_ID_link(
-      &build_data.bmain, &id, build_hierarchy_foreach_ID_cb, &child_build_data, IDWALK_READONLY);
-
-  return IDWALK_RET_NOP;
+  return true;
 }
 
-void TreeDisplayOverrideLibraryHierarchies::build_hierarchy_for_ID(Main *bmain,
-                                                                   ID &override_root_id,
-                                                                   TreeElementID &te_id) const
-{
-  BuildHierarchyForeachIDCbData build_data{*bmain, space_outliner_, override_root_id, &te_id};
-  build_data.parent_ids.add(&override_root_id);
-
-  BKE_library_foreach_ID_link(
-      bmain, &te_id.get_ID(), build_hierarchy_foreach_ID_cb, &build_data, IDWALK_READONLY);
-}
+/** \} */
 
 }  // namespace blender::ed::outliner