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.

1 files changed, 20 insertions, 222 deletions

diff --git a/source/blender/editors/space_outliner/outliner_tree.c b/source/blender/editors/space_outliner/outliner_tree.c
index 9cd38ac07f5..874d35112a5 100644
--- a/source/blender/editors/space_outliner/outliner_tree.c
+++ b/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) {