UI Code Quality: Start refactoring Outliner tree building (using C++)

This introduces a new C++ abstraction "tree-display" (in this commit named
tree-view, renamed in a followup) to help constructing and managing the tree
for the different display types (View Layer, Scene, Blender file, etc.).

See https://developer.blender.org/D9499 for more context. Other developers
approved this rather significantly different design approach there.

----

Motivation

General problems with current design:
* The Outliner tree building code is messy and hard to follow.
* Hard-coded display mode checks are scattered over many places.
* Data is passed around in rather unsafe ways (e.g. lots of `void *`).
* There are no individually testable units.
* Data-structure use is inefficient.

The current Outliner code needs quite some untangling, the tree building seems
like a good place to start. This and the followup commits tackle that.

----

Design Idea

Idea is to have an abstract base class (`AbstractTreeDisplay`), and then
sub-classes with the implementation for each display type (e.g.
`TreeDisplayViewLayer`, `TreeDisplayDataAPI`, etc). The tree-display is kept
alive until tree-rebuild as runtime data of the space, so that further queries
based on the display type can be executed (e.g. "does the display support
selection syncing?", "does it support restriction toggle columns?", etc.).

New files are in a new `space_outliner/tree` sub-directory.

With the new design, display modes become proper units, making them more
maintainable, safer and testable. It should also be easier now to add new
display modes.

source/blender/blenkernel/intern/screen.c

@@ -1640,6 +1640,7 @@ static void direct_link_area(BlendDataReader *reader, ScrArea *area)
       }
       space_outliner->treehash = NULL;
       space_outliner->tree.first = space_outliner->tree.last = NULL;
+      space_outliner->runtime = NULL;
     }
     else if (sl->spacetype == SPACE_IMAGE) {
       SpaceImage *sima = (SpaceImage *)sl;

source/blender/editors/space_outliner/CMakeLists.txt

@@ -44,8 +44,11 @@ set(SRC
   outliner_tree.c
   outliner_utils.c
   space_outliner.c
+  tree/tree_view.cc
+  tree/tree_view_view_layer.cc
 
   outliner_intern.h
+  tree/tree_view.hh
 )
 
 set(LIB

source/blender/editors/space_outliner/outliner_intern.h

@@ -25,6 +25,10 @@
 
 #include "RNA_types.h"
 
+#ifdef __cplusplus
+extern "C" {
+#endif
+
 /* internal exports only */
 
 struct ARegion;
@@ -42,6 +46,10 @@ struct bPoseChannel;
 struct wmKeyConfig;
 struct wmOperatorType;
 
+typedef struct SpaceOutliner_Runtime {
+  struct TreeView *tree_view;
+} SpaceOutliner_Runtime;
+
 typedef enum TreeElementInsertType {
   TE_INSERT_BEFORE,
   TE_INSERT_AFTER,
@@ -534,3 +542,7 @@ void outliner_tag_redraw_avoid_rebuild_on_open_change(const struct SpaceOutliner
 /* outliner_sync.c ---------------------------------------------- */
 
 void outliner_sync_selection(const struct bContext *C, struct SpaceOutliner *space_outliner);
+
+#ifdef __cplusplus
+}
+#endif

source/blender/editors/space_outliner/outliner_tree.c

@@ -85,6 +85,7 @@
 #include "UI_interface.h"
 
 #include "outliner_intern.h"
+#include "tree/tree_view.hh"
 
 #ifdef WIN32
 #  include "BLI_math_base.h" /* M_PI */
@@ -94,7 +95,6 @@
 static TreeElement *outliner_add_collection_recursive(SpaceOutliner *space_outliner,
                                                       Collection *collection,
                                                       TreeElement *ten);
-static void outliner_make_object_parent_hierarchy(ListBase *lb);
 static int outliner_exclude_filter_get(const SpaceOutliner *space_outliner);
 
 /* ********************************************************* */
@@ -237,14 +237,6 @@ void outliner_free_tree_element(TreeElement *element, ListBase *parent_subtree)
 
 /* ********************************************************* */
 
-/* Prototype, see functions below */
-static TreeElement *outliner_add_element(SpaceOutliner *space_outliner,
-                                         ListBase *lb,
-                                         void *idv,
-                                         TreeElement *parent,
-                                         short type,
-                                         short index);
-
 /* -------------------------------------------------------- */
 
 bool outliner_requires_rebuild_on_select_or_active_change(const SpaceOutliner *space_outliner)
@@ -920,12 +912,12 @@ static void outliner_add_id_contents(SpaceOutliner *space_outliner,
  * \note: If child items are only added to the tree if the item is open, the TSE_ type _must_ be
  *        added to #outliner_element_needs_rebuild_on_open_change().
  */
-static TreeElement *outliner_add_element(SpaceOutliner *space_outliner,
-                                         ListBase *lb,
-                                         void *idv,
-                                         TreeElement *parent,
-                                         short type,
-                                         short index)
+TreeElement *outliner_add_element(SpaceOutliner *space_outliner,
+                                  ListBase *lb,
+                                  void *idv,
+                                  TreeElement *parent,
+                                  short type,
+                                  short index)
 {
   TreeElement *te;
   TreeStoreElem *tselem;
@@ -1546,82 +1538,6 @@ static void outliner_add_orphaned_datablocks(Main *mainvar, SpaceOutliner *space
   }
 }
 
-static void outliner_add_layer_collection_objects(SpaceOutliner *space_outliner,
-                                                  ListBase *tree,
-                                                  ViewLayer *layer,
-                                                  LayerCollection *lc,
-                                                  TreeElement *ten)
-{
-  LISTBASE_FOREACH (CollectionObject *, cob, &lc->collection->gobject) {
-    Base *base = BKE_view_layer_base_find(layer, cob->ob);
-    TreeElement *te_object = outliner_add_element(space_outliner, tree, base->object, ten, 0, 0);
-    te_object->directdata = base;
-
-    if (!(base->flag & BASE_VISIBLE_VIEWLAYER)) {
-      te_object->flag |= TE_DISABLED;
-    }
-  }
-}
-
-static void outliner_add_layer_collections_recursive(SpaceOutliner *space_outliner,
-                                                     ListBase *tree,
-                                                     ViewLayer *layer,
-                                                     ListBase *layer_collections,
-                                                     TreeElement *parent_ten,
-                                                     const bool show_objects)
-{
-  LISTBASE_FOREACH (LayerCollection *, lc, layer_collections) {
-    const bool exclude = (lc->flag & LAYER_COLLECTION_EXCLUDE) != 0;
-    TreeElement *ten;
-
-    if (exclude && ((space_outliner->show_restrict_flags & SO_RESTRICT_ENABLE) == 0)) {
-      ten = parent_ten;
-    }
-    else {
-      ID *id = &lc->collection->id;
-      ten = outliner_add_element(space_outliner, tree, id, parent_ten, TSE_LAYER_COLLECTION, 0);
-
-      ten->name = id->name + 2;
-      ten->directdata = lc;
-
-      /* Open by default, except linked collections, which may contain many elements. */
-      TreeStoreElem *tselem = TREESTORE(ten);
-      if (!(tselem->used || ID_IS_LINKED(id) || ID_IS_OVERRIDE_LIBRARY(id))) {
-        tselem->flag &= ~TSE_CLOSED;
-      }
-
-      if (exclude || (lc->runtime_flag & LAYER_COLLECTION_VISIBLE_VIEW_LAYER) == 0) {
-        ten->flag |= TE_DISABLED;
-      }
-    }
-
-    outliner_add_layer_collections_recursive(
-        space_outliner, &ten->subtree, layer, &lc->layer_collections, ten, show_objects);
-    if (!exclude && show_objects) {
-      outliner_add_layer_collection_objects(space_outliner, &ten->subtree, layer, lc, ten);
-    }
-  }
-}
-
-static void outliner_add_view_layer(SpaceOutliner *space_outliner,
-                                    ListBase *tree,
-                                    TreeElement *parent,
-                                    ViewLayer *layer,
-                                    const bool show_objects)
-{
-  /* First layer collection is for master collection, don't show it. */
-  LayerCollection *lc = layer->layer_collections.first;
-  if (lc == NULL) {
-    return;
-  }
-
-  outliner_add_layer_collections_recursive(
-      space_outliner, tree, layer, &lc->layer_collections, parent, show_objects);
-  if (show_objects) {
-    outliner_add_layer_collection_objects(space_outliner, tree, layer, lc, parent);
-  }
-}
-
 BLI_INLINE void outliner_add_collection_init(TreeElement *te, Collection *collection)
 {
   te->name = BKE_collection_ui_name_get(collection);
@@ -1661,7 +1577,7 @@ static TreeElement *outliner_add_collection_recursive(SpaceOutliner *space_outli
 /* Hierarchy --------------------------------------------- */
 
 /* make sure elements are correctly nested */
-static void outliner_make_object_parent_hierarchy(ListBase *lb)
+void outliner_make_object_parent_hierarchy(ListBase *lb)
 {
   TreeElement *te, *ten, *tep;
   TreeStoreElem *tselem;
@@ -1686,103 +1602,6 @@ static void outliner_make_object_parent_hierarchy(ListBase *lb)
   }
 }
 
-/**
- * For all objects in the tree, lookup the parent in this map,
- * and move or add tree elements as needed.
- */
-static void outliner_make_object_parent_hierarchy_collections(SpaceOutliner *space_outliner,
-                                                              GHash *object_tree_elements_hash)
-{
-  GHashIterator gh_iter;
-  GHASH_ITER (gh_iter, object_tree_elements_hash) {
-    Object *child = BLI_ghashIterator_getKey(&gh_iter);
-
-    if (child->parent == NULL) {
-      continue;
-    }
-
-    ListBase *child_ob_tree_elements = BLI_ghashIterator_getValue(&gh_iter);
-    ListBase *parent_ob_tree_elements = BLI_ghash_lookup(object_tree_elements_hash, child->parent);
-    if (parent_ob_tree_elements == NULL) {
-      continue;
-    }
-
-    LISTBASE_FOREACH (LinkData *, link, parent_ob_tree_elements) {
-      TreeElement *parent_ob_tree_element = link->data;
-      TreeElement *parent_ob_collection_tree_element = NULL;
-      bool found = false;
-
-      /* We always want to remove the child from the direct collection its parent is nested under.
-       * This is particularly important when dealing with multi-level nesting (grandchildren). */
-      parent_ob_collection_tree_element = parent_ob_tree_element->parent;
-      while (!ELEM(TREESTORE(parent_ob_collection_tree_element)->type,
-                   TSE_VIEW_COLLECTION_BASE,
-                   TSE_LAYER_COLLECTION)) {
-        parent_ob_collection_tree_element = parent_ob_collection_tree_element->parent;
-      }
-
-      LISTBASE_FOREACH (LinkData *, link_iter, child_ob_tree_elements) {
-        TreeElement *child_ob_tree_element = link_iter->data;
-
-        if (child_ob_tree_element->parent == parent_ob_collection_tree_element) {
-          /* Move from the collection subtree into the parent object subtree. */
-          BLI_remlink(&parent_ob_collection_tree_element->subtree, child_ob_tree_element);
-          BLI_addtail(&parent_ob_tree_element->subtree, child_ob_tree_element);
-          child_ob_tree_element->parent = parent_ob_tree_element;
-          found = true;
-          break;
-        }
-      }
-
-      if (!found) {
-        /* We add the child in the tree even if it is not in the collection.
-         * We deliberately clear its sub-tree though, to make it less prominent. */
-        TreeElement *child_ob_tree_element = outliner_add_element(
-            space_outliner, &parent_ob_tree_element->subtree, child, parent_ob_tree_element, 0, 0);
-        outliner_free_tree(&child_ob_tree_element->subtree);
-        child_ob_tree_element->flag |= TE_CHILD_NOT_IN_COLLECTION;
-        BLI_addtail(child_ob_tree_elements, BLI_genericNodeN(child_ob_tree_element));
-      }
-    }
-  }
-}
-
-/**
- * Build a map from Object* to a list of TreeElement* matching the object.
- */
-static void outliner_object_tree_elements_lookup_create_recursive(GHash *object_tree_elements_hash,
-                                                                  TreeElement *te_parent)
-{
-  LISTBASE_FOREACH (TreeElement *, te, &te_parent->subtree) {
-    TreeStoreElem *tselem = TREESTORE(te);
-
-    if (tselem->type == TSE_LAYER_COLLECTION) {
-      outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, te);
-    }
-    else if (tselem->type == 0 && te->idcode == ID_OB) {
-      Object *ob = (Object *)tselem->id;
-      ListBase *tree_elements = BLI_ghash_lookup(object_tree_elements_hash, ob);
-
-      if (tree_elements == NULL) {
-        tree_elements = MEM_callocN(sizeof(ListBase), __func__);
-        BLI_ghash_insert(object_tree_elements_hash, ob, tree_elements);
-      }
-
-      BLI_addtail(tree_elements, BLI_genericNodeN(te));
-      outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, te);
-    }
-  }
-}
-
-static void outliner_object_tree_elements_lookup_free(GHash *object_tree_elements_hash)
-{
-  GHASH_FOREACH_BEGIN (ListBase *, tree_elements, object_tree_elements_hash) {
-    BLI_freelistN(tree_elements);
-    MEM_freeN(tree_elements);
-  }
-  GHASH_FOREACH_END();
-}
-
 /* Sorting ------------------------------------------------------ */
 
 typedef struct tTreeSort {
@@ -2499,9 +2318,18 @@ void outliner_build_tree(Main *mainvar,
 
   outliner_free_tree(&space_outliner->tree);
   outliner_storage_cleanup(space_outliner);
+  outliner_tree_view_destroy(&space_outliner->runtime->tree_view);
 
+  TreeSourceData source_data = {.bmain = mainvar, .scene = scene, .view_layer = view_layer};
+  space_outliner->runtime->tree_view = outliner_tree_view_create(space_outliner->outlinevis);
+  space_outliner->tree = outliner_tree_view_build_tree(
+      space_outliner->runtime->tree_view, &source_data, space_outliner);
+
+  if (!BLI_listbase_is_empty(&space_outliner->tree)) {
+    /* Skip. */
+  }
   /* options */
-  if (space_outliner->outlinevis == SO_LIBRARIES) {
+  else if (space_outliner->outlinevis == SO_LIBRARIES) {
     Library *lib;
 
     /* current file first - mainvar provides tselem with unique pointer - not used */
@@ -2612,38 +2440,8 @@ void outliner_build_tree(Main *mainvar,
     outliner_add_orphaned_datablocks(mainvar, space_outliner);
   }
   else if (space_outliner->outlinevis == SO_VIEW_LAYER) {
-    if (space_outliner->filter & SO_FILTER_NO_COLLECTION) {
-      /* Show objects in the view layer. */
-      LISTBASE_FOREACH (Base *, base, &view_layer->object_bases) {
-        TreeElement *te_object = outliner_add_element(
-            space_outliner, &space_outliner->tree, base->object, NULL, 0, 0);
-        te_object->directdata = base;
-      }
-
-      if ((space_outliner->filter & SO_FILTER_NO_CHILDREN) == 0) {
-        outliner_make_object_parent_hierarchy(&space_outliner->tree);
-      }
-    }
-    else {
-      /* Show collections in the view layer. */
-      ten = outliner_add_element(
-          space_outliner, &space_outliner->tree, scene, NULL, TSE_VIEW_COLLECTION_BASE, 0);
-      ten->name = IFACE_("Scene Collection");
-      TREESTORE(ten)->flag &= ~TSE_CLOSED;
-
-      bool show_objects = !(space_outliner->filter & SO_FILTER_NO_OBJECT);
-      outliner_add_view_layer(space_outliner, &ten->subtree, ten, view_layer, show_objects);
-
-      if ((space_outliner->filter & SO_FILTER_NO_CHILDREN) == 0) {
-        GHash *object_tree_elements_hash = BLI_ghash_new(
-            BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
-        outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, ten);
-        outliner_make_object_parent_hierarchy_collections(space_outliner,
-                                                          object_tree_elements_hash);
-        outliner_object_tree_elements_lookup_free(object_tree_elements_hash);
-        BLI_ghash_free(object_tree_elements_hash, NULL, NULL);
-      }
-    }
+    /* Ported to new tree-view, should be built there already. */
+    BLI_assert(false);
   }
 
   if ((space_outliner->flag & SO_SKIP_SORT_ALPHA) == 0) {

source/blender/editors/space_outliner/space_outliner.c

@@ -351,11 +351,21 @@ static void outliner_free(SpaceLink *sl)
   if (space_outliner->treehash) {
     BKE_outliner_treehash_free(space_outliner->treehash);
   }
+
+  if (space_outliner->runtime) {
+    MEM_freeN(space_outliner->runtime);
+  }
 }
 
 /* spacetype; init callback */
-static void outliner_init(wmWindowManager *UNUSED(wm), ScrArea *UNUSED(area))
+static void outliner_init(wmWindowManager *UNUSED(wm), ScrArea *area)
 {
+  SpaceOutliner *space_outliner = area->spacedata.first;
+
+  if (space_outliner->runtime == NULL) {
+    space_outliner->runtime = MEM_callocN(sizeof(*space_outliner->runtime),
+                                          "SpaceOutliner_Runtime");
+  }
 }
 
 static SpaceLink *outliner_duplicate(SpaceLink *sl)
@@ -369,6 +379,10 @@ static SpaceLink *outliner_duplicate(SpaceLink *sl)
 
   space_outliner_new->sync_select_dirty = WM_OUTLINER_SYNC_SELECT_FROM_ALL;
 
+  if (space_outliner->runtime) {
+    space_outliner_new->runtime = MEM_dupallocN(space_outliner->runtime);
+  }
+
   return (SpaceLink *)space_outliner_new;
 }
 

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

@@ -0,0 +1,61 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup spoutliner
+ */
+
+#include "BLI_listbase.h"
+
+#include "DNA_listBase.h"
+
+#include "tree_view.hh"
+
+namespace outliner = blender::outliner;
+/* Convenience. */
+using blender::outliner::AbstractTreeView;
+
+TreeView *outliner_tree_view_create(eSpaceOutliner_Mode mode)
+{
+  AbstractTreeView *tree_view = nullptr;
+
+  switch (mode) {
+    case SO_SCENES:
+    case SO_LIBRARIES:
+    case SO_SEQUENCE:
+    case SO_DATA_API:
+    case SO_ID_ORPHANS:
+      break;
+    case SO_VIEW_LAYER:
+      tree_view = new outliner::TreeViewViewLayer();
+      break;
+  }
+
+  return reinterpret_cast<TreeView *>(tree_view);
+}
+
+void outliner_tree_view_destroy(TreeView **tree_view)
+{
+  delete reinterpret_cast<AbstractTreeView *>(*tree_view);
+  *tree_view = nullptr;
+}
+
+ListBase outliner_tree_view_build_tree(TreeView *tree_view,
+                                       TreeSourceData *source_data,
+                                       SpaceOutliner *space_outliner)
+{
+  return reinterpret_cast<AbstractTreeView *>(tree_view)->buildTree(*source_data, *space_outliner);
+}

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

@@ -0,0 +1,89 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup spoutliner
+ */
+
+#pragma once
+
+#include "DNA_space_types.h"
+
+struct bContext;
+struct ListBase;
+struct SpaceOutliner;
+struct TreeSourceData;
+
+#ifdef __cplusplus
+
+namespace blender {
+namespace outliner {
+
+using Tree = ListBase;
+
+class AbstractTreeView {
+ public:
+  virtual ~AbstractTreeView() = default;
+
+  /** Build a tree for this view and the current context. */
+  virtual Tree buildTree(const TreeSourceData &source_data, SpaceOutliner &space_outliner) = 0;
+};
+
+class TreeViewViewLayer : public AbstractTreeView {
+ public:
+  Tree buildTree(const TreeSourceData &source_data, SpaceOutliner &space_outliner) override final;
+};
+
+}  // namespace outliner
+}  // namespace blender
+
+extern "C" {
+#endif
+
+/* -------------------------------------------------------------------- */
+/* C-API */
+
+typedef struct TreeView TreeView;
+
+/**
+ * \brief The data to build the tree from.
+ */
+typedef struct TreeSourceData {
+  struct Main *bmain;
+  struct Scene *scene;
+  struct ViewLayer *view_layer;
+} TreeSourceData;
+
+TreeView *outliner_tree_view_create(eSpaceOutliner_Mode mode);
+void outliner_tree_view_destroy(TreeView **tree_view);
+
+ListBase outliner_tree_view_build_tree(TreeView *tree_view,
+                                       TreeSourceData *source_data,
+                                       struct SpaceOutliner *space_outliner);
+
+/* The following functions are needed to build the actual tree. Could be moved to a helper class
+ * (e.g. TreeBuilder). */
+struct TreeElement *outliner_add_element(struct SpaceOutliner *space_outliner,
+                                         ListBase *lb,
+                                         void *idv,
+                                         struct TreeElement *parent,
+                                         short type,
+                                         short index);
+void outliner_make_object_parent_hierarchy(ListBase *lb);
+
+#ifdef __cplusplus
+}
+#endif

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

@@ -0,0 +1,258 @@
+/*
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; either version 2
+ * of the License, or (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
+ */
+
+/** \file
+ * \ingroup spoutliner
+ */
+
+#include <iostream>
+
+#include "DNA_scene_types.h"
+
+#include "BKE_layer.h"
+
+#include "BLI_ghash.h"
+#include "BLI_listbase.h"
+
+#include "BLT_translation.h"
+
+#include "MEM_guardedalloc.h"
+
+#include "../outliner_intern.h"
+#include "tree_view.hh"
+
+namespace blender {
+namespace outliner {
+
+/**
+ * For all objects in the tree, lookup the parent in this map,
+ * and move or add tree elements as needed.
+ */
+static void outliner_make_object_parent_hierarchy_collections(SpaceOutliner *space_outliner,
+                                                              GHash *object_tree_elements_hash)
+{
+  GHashIterator gh_iter;
+  GHASH_ITER (gh_iter, object_tree_elements_hash) {
+    Object *child = static_cast<Object *>(BLI_ghashIterator_getKey(&gh_iter));
+
+    if (child->parent == NULL) {
+      continue;
+    }
+
+    ListBase *child_ob_tree_elements = static_cast<ListBase *>(
+        BLI_ghashIterator_getValue(&gh_iter));
+    ListBase *parent_ob_tree_elements = static_cast<ListBase *>(
+        BLI_ghash_lookup(object_tree_elements_hash, child->parent));
+    if (parent_ob_tree_elements == NULL) {
+      continue;
+    }
+
+    LISTBASE_FOREACH (LinkData *, link, parent_ob_tree_elements) {
+      TreeElement *parent_ob_tree_element = static_cast<TreeElement *>(link->data);
+      TreeElement *parent_ob_collection_tree_element = NULL;
+      bool found = false;
+
+      /* We always want to remove the child from the direct collection its parent is nested under.
+       * This is particularly important when dealing with multi-level nesting (grandchildren). */
+      parent_ob_collection_tree_element = parent_ob_tree_element->parent;
+      while (!ELEM(TREESTORE(parent_ob_collection_tree_element)->type,
+                   TSE_VIEW_COLLECTION_BASE,
+                   TSE_LAYER_COLLECTION)) {
+        parent_ob_collection_tree_element = parent_ob_collection_tree_element->parent;
+      }
+
+      LISTBASE_FOREACH (LinkData *, link_iter, child_ob_tree_elements) {
+        TreeElement *child_ob_tree_element = static_cast<TreeElement *>(link_iter->data);
+
+        if (child_ob_tree_element->parent == parent_ob_collection_tree_element) {
+          /* Move from the collection subtree into the parent object subtree. */
+          BLI_remlink(&parent_ob_collection_tree_element->subtree, child_ob_tree_element);
+          BLI_addtail(&parent_ob_tree_element->subtree, child_ob_tree_element);
+          child_ob_tree_element->parent = parent_ob_tree_element;
+          found = true;
+          break;
+        }
+      }
+
+      if (!found) {
+        /* We add the child in the tree even if it is not in the collection.
+         * We deliberately clear its sub-tree though, to make it less prominent. */
+        TreeElement *child_ob_tree_element = outliner_add_element(
+            space_outliner, &parent_ob_tree_element->subtree, child, parent_ob_tree_element, 0, 0);
+        outliner_free_tree(&child_ob_tree_element->subtree);
+        child_ob_tree_element->flag |= TE_CHILD_NOT_IN_COLLECTION;
+        BLI_addtail(child_ob_tree_elements, BLI_genericNodeN(child_ob_tree_element));
+      }
+    }
+  }
+}
+
+/**
+ * Build a map from Object* to a list of TreeElement* matching the object.
+ */
+static void outliner_object_tree_elements_lookup_create_recursive(GHash *object_tree_elements_hash,
+                                                                  TreeElement *te_parent)
+{
+  LISTBASE_FOREACH (TreeElement *, te, &te_parent->subtree) {
+    TreeStoreElem *tselem = TREESTORE(te);
+
+    if (tselem->type == TSE_LAYER_COLLECTION) {
+      outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, te);
+    }
+    else if (tselem->type == 0 && te->idcode == ID_OB) {
+      Object *ob = (Object *)tselem->id;
+      ListBase *tree_elements = static_cast<ListBase *>(
+          BLI_ghash_lookup(object_tree_elements_hash, ob));
+
+      if (tree_elements == NULL) {
+        tree_elements = static_cast<ListBase *>(MEM_callocN(sizeof(ListBase), __func__));
+        BLI_ghash_insert(object_tree_elements_hash, ob, tree_elements);
+      }
+
+      BLI_addtail(tree_elements, BLI_genericNodeN(te));
+      outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, te);
+    }
+  }
+}
+
+static void outliner_object_tree_elements_lookup_free(GHash *object_tree_elements_hash)
+{
+  GHASH_FOREACH_BEGIN (ListBase *, tree_elements, object_tree_elements_hash) {
+    BLI_freelistN(tree_elements);
+    MEM_freeN(tree_elements);
+  }
+  GHASH_FOREACH_END();
+}
+
+static void outliner_add_layer_collection_objects(SpaceOutliner *space_outliner,
+                                                  ListBase *tree,
+                                                  ViewLayer *layer,
+                                                  LayerCollection *lc,
+                                                  TreeElement *ten)
+{
+  LISTBASE_FOREACH (CollectionObject *, cob, &lc->collection->gobject) {
+    Base *base = BKE_view_layer_base_find(layer, cob->ob);
+    TreeElement *te_object = outliner_add_element(space_outliner, tree, base->object, ten, 0, 0);
+    te_object->directdata = base;
+
+    if (!(base->flag & BASE_VISIBLE_VIEWLAYER)) {
+      te_object->flag |= TE_DISABLED;
+    }
+  }
+}
+
+static void outliner_add_layer_collections_recursive(SpaceOutliner *space_outliner,
+                                                     ListBase *tree,
+                                                     ViewLayer *layer,
+                                                     ListBase *layer_collections,
+                                                     TreeElement *parent_ten,
+                                                     const bool show_objects)
+{
+  LISTBASE_FOREACH (LayerCollection *, lc, layer_collections) {
+    const bool exclude = (lc->flag & LAYER_COLLECTION_EXCLUDE) != 0;
+    TreeElement *ten;
+
+    if (exclude && ((space_outliner->show_restrict_flags & SO_RESTRICT_ENABLE) == 0)) {
+      ten = parent_ten;
+    }
+    else {
+      ID *id = &lc->collection->id;
+      ten = outliner_add_element(space_outliner, tree, id, parent_ten, TSE_LAYER_COLLECTION, 0);
+
+      ten->name = id->name + 2;
+      ten->directdata = lc;
+
+      /* Open by default, except linked collections, which may contain many elements. */
+      TreeStoreElem *tselem = TREESTORE(ten);
+      if (!(tselem->used || ID_IS_LINKED(id) || ID_IS_OVERRIDE_LIBRARY(id))) {
+        tselem->flag &= ~TSE_CLOSED;
+      }
+
+      if (exclude || (lc->runtime_flag & LAYER_COLLECTION_VISIBLE_VIEW_LAYER) == 0) {
+        ten->flag |= TE_DISABLED;
+      }
+    }
+
+    outliner_add_layer_collections_recursive(
+        space_outliner, &ten->subtree, layer, &lc->layer_collections, ten, show_objects);
+    if (!exclude && show_objects) {
+      outliner_add_layer_collection_objects(space_outliner, &ten->subtree, layer, lc, ten);
+    }
+  }
+}
+
+static void outliner_add_view_layer(SpaceOutliner *space_outliner,
+                                    ListBase *tree,
+                                    TreeElement *parent,
+                                    ViewLayer *layer,
+                                    const bool show_objects)
+{
+  /* First layer collection is for master collection, don't show it. */
+  LayerCollection *lc = static_cast<LayerCollection *>(layer->layer_collections.first);
+  if (lc == NULL) {
+    return;
+  }
+
+  outliner_add_layer_collections_recursive(
+      space_outliner, tree, layer, &lc->layer_collections, parent, show_objects);
+  if (show_objects) {
+    outliner_add_layer_collection_objects(space_outliner, tree, layer, lc, parent);
+  }
+}
+
+Tree TreeViewViewLayer::buildTree(const TreeSourceData &source_data, SpaceOutliner &space_outliner)
+{
+  Tree tree = {nullptr};
+
+  if (space_outliner.filter & SO_FILTER_NO_COLLECTION) {
+    /* Show objects in the view layer. */
+    LISTBASE_FOREACH (Base *, base, &source_data.view_layer->object_bases) {
+      TreeElement *te_object = outliner_add_element(
+          &space_outliner, &tree, base->object, nullptr, 0, 0);
+      te_object->directdata = base;
+    }
+
+    if ((space_outliner.filter & SO_FILTER_NO_CHILDREN) == 0) {
+      outliner_make_object_parent_hierarchy(&tree);
+    }
+  }
+  else {
+    /* Show collections in the view layer. */
+    TreeElement *ten = outliner_add_element(
+        &space_outliner, &tree, source_data.scene, nullptr, TSE_VIEW_COLLECTION_BASE, 0);
+    ten->name = IFACE_("Scene Collection");
+    TREESTORE(ten)->flag &= ~TSE_CLOSED;
+
+    bool show_objects = !(space_outliner.filter & SO_FILTER_NO_OBJECT);
+    outliner_add_view_layer(
+        &space_outliner, &ten->subtree, ten, source_data.view_layer, show_objects);
+
+    if ((space_outliner.filter & SO_FILTER_NO_CHILDREN) == 0) {
+      GHash *object_tree_elements_hash = BLI_ghash_new(
+          BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, __func__);
+      outliner_object_tree_elements_lookup_create_recursive(object_tree_elements_hash, ten);
+      outliner_make_object_parent_hierarchy_collections(&space_outliner,
+                                                        object_tree_elements_hash);
+      outliner_object_tree_elements_lookup_free(object_tree_elements_hash);
+      BLI_ghash_free(object_tree_elements_hash, nullptr, nullptr);
+    }
+  }
+
+  return tree;
+}
+
+}  // namespace outliner
+}  // namespace blender

source/blender/makesdna/DNA_space_types.h

@@ -234,6 +234,9 @@ typedef enum eSpaceButtons_Flag {
 /** \name Outliner
  * \{ */
 
+/* Defined in `outliner_intern.h`. */
+typedef struct SpaceOutliner_Runtime SpaceOutliner_Runtime;
+
 /* Outliner */
 typedef struct SpaceOutliner {
   SpaceLink *next, *prev;
@@ -276,6 +279,8 @@ typedef struct SpaceOutliner {
    * Pointers to treestore elements, grouped by (id, type, nr)
    * in hashtable for faster searching */
   void *treehash;
+
+  SpaceOutliner_Runtime *runtime;
 } SpaceOutliner;
 
 /* SpaceOutliner.flag */