[Bf-blender-cvs] [a4a7af47326] master: Outliner: New C++ based functional tree iterators

[Julian Eisel]

Commit: a4a7af47326f6ca2ba881c3a2a25a0bdeed17c66
Author: Julian Eisel
Date:   Wed May 25 22:51:52 2022 +0200
Branches: master
https://developer.blender.org/rBa4a7af47326f6ca2ba881c3a2a25a0bdeed17c66

Outliner: New C++ based functional tree iterators

(Not meant to cause user visible changes.)

Adds some first new iterators to traverse over tree elements with a
functional syntax. Functional because it meant to be used with C++
lambdas.
For example, this common pattern:
```lang=cpp
void some_recursive_function(SpaceOutliner *space_outliner, ListBase *tree, ...)
{
  LISTBASE_FOREACH (TreeElement *, te, tree) {
    /* ... do something with the element ... */

    /* Recurse into open children. */
    if (TSELEM_OPEN(TREESTORE(te), space_outliner) {
      some_recursive_function(&te->subtree, ...);
    }
  }
}
```
Gets simplified to this:
```lang=cpp
void some_function(SpaceOutliner &space_outliner, ...)
{
  tree_iterator::all_open(space_outliner, [&](TreeElement *te) {
    /* ... do something with the element ... */
  });
}
```

We can add more iterators, e.g. some that support early exiting or
skipping children, returning a custom type, only act on selected
elements, etc.

The following commit will convert a bunch of code to use these. Some
further benefits will become visible there. Not all cases are straight
forward to convert, but hopefully more and more code can be refactored
to work with this. This deduplicates and centralizes the iteration
logic, which will later make it much easier to refactor how the tree
storage is done (e.g. move it to `SpaceOutliner_Runtime` and use a
better container than `ListBase`).

===================================================================

M	source/blender/editors/space_outliner/CMakeLists.txt
A	source/blender/editors/space_outliner/tree/tree_iterator.cc
A	source/blender/editors/space_outliner/tree/tree_iterator.hh

===================================================================

diff --git a/source/blender/editors/space_outliner/CMakeLists.txt b/source/blender/editors/space_outliner/CMakeLists.txt
index 1c09ad2d98f..97d2957eed2 100644
--- a/source/blender/editors/space_outliner/CMakeLists.txt
+++ b/source/blender/editors/space_outliner/CMakeLists.txt
@@ -58,6 +58,7 @@ set(SRC
   tree/tree_element_scene_objects.cc
   tree/tree_element_seq.cc
   tree/tree_element_view_layer.cc
+  tree/tree_iterator.cc
 
   outliner_intern.hh
   tree/common.hh
@@ -76,6 +77,7 @@ set(SRC
   tree/tree_element_scene_objects.hh
   tree/tree_element_seq.hh
   tree/tree_element_view_layer.hh
+  tree/tree_iterator.hh
 )
 
 set(LIB
diff --git a/source/blender/editors/space_outliner/tree/tree_iterator.cc b/source/blender/editors/space_outliner/tree/tree_iterator.cc
new file mode 100644
index 00000000000..85ff9e6437e
--- /dev/null
+++ b/source/blender/editors/space_outliner/tree/tree_iterator.cc
@@ -0,0 +1,58 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+/** \file
+ * \ingroup spoutliner
+ */
+
+#include "DNA_space_types.h"
+
+#include "BLI_listbase.h"
+
+#include "../outliner_intern.hh"
+
+#include "tree_iterator.hh"
+
+namespace blender::ed::outliner::tree_iterator {
+
+void all(const SpaceOutliner &space_outliner, const VisitorFn visitor)
+{
+  all_open(space_outliner, space_outliner.tree, visitor);
+}
+
+void all(const ListBase &subtree, const VisitorFn visitor)
+{
+  LISTBASE_FOREACH_MUTABLE (TreeElement *, element, &subtree) {
+    /* Get needed data out in case element gets freed. */
+    const ListBase subtree = element->subtree;
+
+    visitor(element);
+    /* Don't access element from now on, it may be freed. */
+
+    all(subtree, visitor);
+  }
+}
+
+void all_open(const SpaceOutliner &space_outliner, const VisitorFn visitor)
+{
+  all_open(space_outliner, space_outliner.tree, visitor);
+}
+
+void all_open(const SpaceOutliner &space_outliner,
+              const ListBase &subtree,
+              const VisitorFn visitor)
+{
+  LISTBASE_FOREACH_MUTABLE (TreeElement *, element, &subtree) {
+    /* Get needed data out in case element gets freed. */
+    const bool is_open = TSELEM_OPEN(element->store_elem, &space_outliner);
+    const ListBase subtree = element->subtree;
+
+    visitor(element);
+    /* Don't access element from now on, it may be freed. */
+
+    if (is_open) {
+      all_open(space_outliner, subtree, visitor);
+    }
+  }
+}
+
+}  // namespace blender::ed::outliner::tree_iterator
diff --git a/source/blender/editors/space_outliner/tree/tree_iterator.hh b/source/blender/editors/space_outliner/tree/tree_iterator.hh
new file mode 100644
index 00000000000..e3b3c90eaad
--- /dev/null
+++ b/source/blender/editors/space_outliner/tree/tree_iterator.hh
@@ -0,0 +1,35 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+
+/** \file
+ * \ingroup spoutliner
+ */
+
+#pragma once
+
+#include "BLI_function_ref.hh"
+
+struct ListBase;
+struct SpaceOutliner;
+struct TreeElement;
+
+namespace blender::ed::outliner {
+namespace tree_iterator {
+
+using VisitorFn = FunctionRef<void(TreeElement *)>;
+
+/**
+ * Preorder (meaning depth-first) traversal of all elements (regardless of collapsed state).
+ * Freeing the currently visited element in \a visitor is fine.
+ */
+void all(const SpaceOutliner &space_outliner, VisitorFn visitor);
+void all(const ListBase &subtree, VisitorFn visitor);
+
+/**
+ * Preorder (meaning depth-first) traversal of all elements not part of a collapsed sub-tree.
+ * Freeing the currently visited element in \a visitor is fine.
+ */
+void all_open(const SpaceOutliner &, VisitorFn visitor);
+void all_open(const SpaceOutliner &, const ListBase &subtree, VisitorFn visitor);
+
+}  // namespace tree_iterator
+}  // namespace blender::ed::outliner