Outliner: Workaround for big performance issue in Library Overrides mode

When displaying the Hierarchies view of the Library Overrides display
mode in a specific Heist production file, Blender would become
unresponsive for about 30 seconds and every redraw in the Outliner would
lag noticably. Issue is that the sum of hierarchy elements is multiple
thousands, and that really brings the Outliner to its knees. I've looked
into some improvents and committed a few minor ones already, but it
seems it's really the big sum of elements causing the issue. There
doesn't appear to be a single bottle-neck.

To work around this, "lazy build" children, so that children of
collapsed elements are not actually created. This brings the tree
building down to some tens of miliseconds, and redrawing becomes
rather lag-free again, even with big parts of the tree un-collapsed.

Problem: Searching still needs to build the entire tree, so it's
essentially unusable right now. Should we disallow searching
altogether?

source/blender/editors/space_outliner/tree/tree_display.hh

@@ -166,6 +166,8 @@ class TreeDisplayOverrideLibraryHierarchies final : public AbstractTreeDisplay {
 
   ListBase buildTree(const TreeSourceData &source_data) override;
 
+  bool is_lazy_built() const override;
+
  private:
   ListBase build_hierarchy_for_lib_or_main(Main *bmain,
                                            TreeElement &parent_te,

source/blender/editors/space_outliner/tree/tree_display_override_library_hierarchies.cc

@@ -75,6 +75,11 @@ ListBase TreeDisplayOverrideLibraryHierarchies::buildTree(const TreeSourceData &
   return tree;
 }
 
+bool TreeDisplayOverrideLibraryHierarchies::is_lazy_built() const
+{
+  return true;
+}
+
 /* -------------------------------------------------------------------- */
 /** \name Library override hierarchy building
  * \{ */
@@ -165,10 +170,14 @@ void OverrideIDHierarchyBuilder::build_hierarchy_for_ID(ID &override_root_id,
   build_hierarchy_for_ID_recursive(override_root_id, build_data, te_to_expand);
 }
 
+enum ForeachChildReturn {
+  FOREACH_CONTINUE,
+  FOREACH_BREAK,
+};
 /* Helpers (defined below). */
 static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
                                             const ID &parent_id,
-                                            FunctionRef<void(ID &)> fn);
+                                            FunctionRef<ForeachChildReturn(ID &)> fn);
 static bool id_is_in_override_hierarchy(const Main &bmain,
                                         const ID &id,
                                         const ID &relationship_parent_id,
@@ -184,22 +193,30 @@ void OverrideIDHierarchyBuilder::build_hierarchy_for_ID_recursive(const ID &pare
   foreach_natural_hierarchy_child(id_relations_, parent_id, [&](ID &id) {
     /* Some IDs can use themselves, early abort. */
     if (&id == &parent_id) {
-      return;
+      return FOREACH_CONTINUE;
     }
     if (!id_is_in_override_hierarchy(bmain_, id, parent_id, build_data.override_root_id_)) {
-      return;
+      return FOREACH_CONTINUE;
     }
 
     /* 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;
+      return FOREACH_CONTINUE;
     }
 
     /* 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;
+      return FOREACH_CONTINUE;
+    }
+
+    /* We only want to add children whose parent isn't collapsed. Otherwise, in complex scenes with
+     * thousands of relationships, the building can slow down tremendously. Tag the parent to allow
+     * un-collapsing, but don't actually add the children. */
+    if (!TSELEM_OPEN(TREESTORE(&te_to_expand), &space_outliner_)) {
+      te_to_expand.flag |= TE_PRETEND_HAS_CHILDREN;
+      return FOREACH_BREAK;
     }
 
     TreeElement *new_te = outliner_add_element(
@@ -213,6 +230,8 @@ void OverrideIDHierarchyBuilder::build_hierarchy_for_ID_recursive(const ID &pare
     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);
+
+    return FOREACH_CONTINUE;
   });
 }
 
@@ -238,7 +257,7 @@ void OverrideIDHierarchyBuilder::build_hierarchy_for_ID_recursive(const ID &pare
  */
 static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
                                             const ID &parent_id,
-                                            FunctionRef<void(ID &)> fn)
+                                            FunctionRef<ForeachChildReturn(ID &)> fn)
 {
   const MainIDRelationsEntry *relations_of_id = static_cast<MainIDRelationsEntry *>(
       BLI_ghash_lookup(id_relations.relations_from_pointers, &parent_id));
@@ -259,12 +278,16 @@ static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
     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);
+        if (fn(potential_child_ob.parent->id) == FOREACH_BREAK) {
+          return;
+        }
         continue;
       }
     }
 
-    fn(target_id);
+    if (fn(target_id) == FOREACH_BREAK) {
+      return;
+    }
   }
 
   /* If the ID is an object, find and iterate over any child objects. */
@@ -277,9 +300,13 @@ static void foreach_natural_hierarchy_child(const MainIDRelations &id_relations,
         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);
+      const Object &potential_child_ob = reinterpret_cast<Object &>(potential_child_id);
+      if (!potential_child_ob.parent || &potential_child_ob.parent->id != &parent_id) {
+        continue;
+      }
+
+      if (fn(potential_child_id) == FOREACH_BREAK) {
+        return;
       }
     }
   }