VSE: New iterator design

This iterator design provides means to create simple and flexible API
to query and work with collection of strips. It should be used in cases
when conditions require multiple stages of recursive iteration of all
strips or similar complex scenarios.

Quick API overview:
Basic queries are standalone functions that return SeqCollection
Use SEQ_collection_create() and SEQ_collection_free() to construct
such query functions.
Use these functions to get strips of known conditions, like selected
strips, movie strips, muted strips and so on.

Use SEQ_reference_query() when querying strips with relation to
some reference strip. For example to get its effects, strips that have
same type or use same input file and so on.
These aren't standalone functions because often you need to query strips
relative to each strip in collection.

Use SEQ_collection_expand() to query strips relative to each strip
in collection. These will be merged to original collection.

Use SEQ_collection_merge() to merge 2 collections

To iterate collection elements use macro SEQ_ITERATOR_FOREACH()

This API is quite specific, but I think it is best suited for tasks
that are usualy solved in sequencer codebase.

Old sequencer iterator has been completely removed.
SEQ_ALL_BEGIN and SEQ_ALL_END macros re-use new iterator design.

As initial use for this iterator select_grouped_effect_link()
function has been rewritten. It was not only broken, but also it used
DNA fields to aid iterating strips.

Reviewed By: sergey

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

4 files changed, 267 insertions, 134 deletions

diff --git a/.clang-format b/.clang-format
index b61ce6018d3..9cc3cdeaaf8 100644
--- a/.clang-format
+++ b/.clang-format
@@ -255,6 +255,7 @@ ForEachMacros:
   - SCULPT_VERTEX_DUPLICATES_AND_NEIGHBORS_ITER_BEGIN
   - SCULPT_VERTEX_NEIGHBORS_ITER_BEGIN
   - SEQ_ALL_BEGIN
+  - SEQ_ITERATOR_FOREACH
   - SURFACE_QUAD_ITER_BEGIN
   - foreach
   - ED_screen_areas_iter
diff --git a/source/blender/editors/space_sequencer/sequencer_select.c b/source/blender/editors/space_sequencer/sequencer_select.c
index a9f8a70d61e..ec5ec5c8ce0 100644
--- a/source/blender/editors/space_sequencer/sequencer_select.c
+++ b/source/blender/editors/space_sequencer/sequencer_select.c
@@ -26,7 +26,6 @@
 #include <string.h>
 
 #include "BLI_blenlib.h"
-#include "BLI_ghash.h"
 #include "BLI_math.h"
 #include "BLI_utildefines.h"
 
@@ -1622,64 +1621,76 @@ static bool select_grouped_time_overlap(Editing *ed, Sequence *actseq)
   return changed;
 }
 
-static bool select_grouped_effect_link(Editing *ed, Sequence *actseq, const int channel)
+/* Query all effect strips that are directly or indirectly connected to seq_reference. */
+void query_strip_effect_chain(Sequence *seq_reference,
+                              ListBase *seqbase,
+                              SeqCollection *collection)
 {
-  bool changed = false;
-  const bool is_audio = ((actseq->type == SEQ_TYPE_META) || SEQ_IS_SOUND(actseq));
-  int startdisp = actseq->startdisp;
-  int enddisp = actseq->enddisp;
-  int machine = actseq->machine;
-  SeqIterator iter;
-
-  LISTBASE_FOREACH (Sequence *, seq, SEQ_active_seqbase_get(ed)) {
-    seq->tmp = NULL;
+  if (!SEQ_collection_append_strip(seq_reference, collection)) {
+    return; /* Strip is already in set, so all effects connected to it are as well. */
   }
 
-  actseq->tmp = POINTER_FROM_INT(true);
-
-  Sequence *seq = NULL;
-  for (SEQ_iterator_begin(ed, &iter, true); iter.valid; SEQ_iterator_next(&iter)) {
-    seq = iter.seq;
+  /* Find all strips that seq_reference is connected to. */
+  if (seq_reference->type & SEQ_TYPE_EFFECT) {
+    if (seq_reference->seq1) {
+      query_strip_effect_chain(seq_reference->seq1, seqbase, collection);
+    }
+    if (seq_reference->seq2) {
+      query_strip_effect_chain(seq_reference->seq2, seqbase, collection);
+    }
+    if (seq_reference->seq3) {
+      query_strip_effect_chain(seq_reference->seq3, seqbase, collection);
+    }
+  }
 
-    /* Ignore all seqs already selected. */
-    /* Ignore all seqs not sharing some time with active one. */
-    /* Ignore all seqs of incompatible types (audio vs video). */
-    if (!SEQ_CHANNEL_CHECK(seq, channel) || (seq->flag & SELECT) || (seq->startdisp >= enddisp) ||
-        (seq->enddisp < startdisp) || (!is_audio && SEQ_IS_SOUND(seq)) ||
-        (is_audio && !((seq->type == SEQ_TYPE_META) || SEQ_IS_SOUND(seq)))) {
-      continue;
+  /* Find all strips connected to seq_reference. */
+  LISTBASE_FOREACH (Sequence *, seq_test, seqbase) {
+    if (seq_test->seq1 == seq_reference || seq_test->seq2 == seq_reference ||
+        seq_test->seq3 == seq_reference) {
+      query_strip_effect_chain(seq_test, seqbase, collection);
     }
+  }
+}
 
-    /* If the seq is an effect one, we need extra checking. */
-    if (SEQ_IS_EFFECT(seq) && ((seq->seq1 && seq->seq1->tmp) || (seq->seq2 && seq->seq2->tmp) ||
-                               (seq->seq3 && seq->seq3->tmp))) {
-      if (startdisp > seq->startdisp) {
-        startdisp = seq->startdisp;
-      }
-      if (enddisp < seq->enddisp) {
-        enddisp = seq->enddisp;
-      }
-      if (machine < seq->machine) {
-        machine = seq->machine;
-      }
+/* Query strips that are in lower channel and intersect in time with seq_reference. */
+static void query_lower_channel_strips(Sequence *seq_reference,
+                                       ListBase *seqbase,
+                                       SeqCollection *collection)
+{
+  LISTBASE_FOREACH (Sequence *, seq_test, seqbase) {
+    if (seq_test->machine > seq_reference->machine) {
+      continue; /* Not lower channel. */
+    }
+    if (seq_test->enddisp <= seq_reference->startdisp ||
+        seq_test->startdisp >= seq_reference->enddisp) {
+      continue; /* Not intersecting in time. */
+    }
+    SEQ_collection_append_strip(seq_test, collection);
+  }
+}
 
-      seq->tmp = POINTER_FROM_INT(true);
+/* Select all strips within time range and with lower channel of initial selection. Then select
+ * effect chains of these strips. */
+static bool select_grouped_effect_link(Editing *ed, Sequence *actseq, const int channel)
+{
+  ListBase *seqbase = SEQ_active_seqbase_get(ed);
 
-      seq->flag |= SELECT;
-      changed = true;
+  /* Get collection of strips. */
+  SeqCollection *collection = SEQ_query_selected_strips(seqbase);
+  const int selected_strip_count = BLI_gset_len(collection->set);
+  SEQ_collection_expand(seqbase, collection, query_lower_channel_strips);
+  SEQ_collection_expand(seqbase, collection, query_strip_effect_chain);
 
-      /* Unfortunately, we must restart checks from the beginning. */
-      SEQ_iterator_end(&iter);
-      SEQ_iterator_begin(ed, &iter, true);
-    }
+  /* Check if other strips will be affected. */
+  const bool changed = BLI_gset_len(collection->set) > selected_strip_count;
 
-    /* Video strips below active one, or any strip for audio (order doesn't matter here). */
-    else if (seq->machine < machine || is_audio) {
-      seq->flag |= SELECT;
-      changed = true;
-    }
+  /* Actual logic. */
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection) {
+    seq->flag |= SELECT;
   }
-  SEQ_iterator_end(&iter);
+
+  SEQ_collection_free(collection);
 
   return changed;
 }
diff --git a/source/blender/sequencer/SEQ_iterator.h b/source/blender/sequencer/SEQ_iterator.h
index b34f0558c56..7517c941c80 100644
--- a/source/blender/sequencer/SEQ_iterator.h
+++ b/source/blender/sequencer/SEQ_iterator.h
@@ -27,33 +27,62 @@
 extern "C" {
 #endif
 
+#include "BLI_ghash.h"
+
 struct Editing;
 struct Sequence;
+struct GSet;
+struct GSetIterator;
 
-typedef struct SeqIterator {
-  struct Sequence **array;
-  int tot, cur;
+#define SEQ_ITERATOR_FOREACH(var, collection) \
+  for (SeqIterator iter = {NULL}; SEQ_iterator_ensure(collection, &iter, &var) && var != NULL; \
+       var = SEQ_iterator_yield(&iter))
 
-  struct Sequence *seq;
-  int valid;
-} SeqIterator;
-
-#define SEQ_ALL_BEGIN(ed, _seq) \
+#define SEQ_ALL_BEGIN(ed, var) \
   { \
-    SeqIterator iter_macro; \
-    for (SEQ_iterator_begin(ed, &iter_macro, false); iter_macro.valid; \
-         SEQ_iterator_next(&iter_macro)) { \
-      _seq = iter_macro.seq;
+    SeqCollection *all_strips = SEQ_query_all_strips_recursive(&ed->seqbase); \
+    GSetIterator gsi; \
+    GSET_ITER (gsi, all_strips->set) { \
+      var = (Sequence *)(BLI_gsetIterator_getKey(&gsi));
 
 #define SEQ_ALL_END \
   } \
-  SEQ_iterator_end(&iter_macro); \
+  SEQ_collection_free(all_strips); \
   } \
   ((void)0)
 
-void SEQ_iterator_begin(struct Editing *ed, SeqIterator *iter, const bool use_current_sequences);
-void SEQ_iterator_next(SeqIterator *iter);
-void SEQ_iterator_end(SeqIterator *iter);
+typedef struct SeqCollection {
+  struct SeqCollection *next, *prev;
+  struct GSet *set;
+} SeqCollection;
+
+typedef struct SeqIterator {
+  GSetIterator gsi;
+  SeqCollection *collection;
+  bool iterator_initialized;
+} SeqIterator;
+
+bool SEQ_iterator_ensure(SeqCollection *collection,
+                         SeqIterator *iterator,
+                         struct Sequence **r_seq);
+struct Sequence *SEQ_iterator_yield(SeqIterator *iterator);
+
+SeqCollection *SEQ_collection_create(void);
+bool SEQ_collection_append_strip(struct Sequence *seq, SeqCollection *data);
+void SEQ_collection_free(SeqCollection *data);
+void SEQ_collection_merge(SeqCollection *collection_dst, SeqCollection *collection_src);
+void SEQ_collection_expand(struct ListBase *seqbase,
+                           SeqCollection *collection,
+                           void query_func(struct Sequence *seq_reference,
+                                           struct ListBase *seqbase,
+                                           SeqCollection *collection));
+SeqCollection *SEQ_query_by_reference(struct Sequence *seq_reference,
+                                      struct ListBase *seqbase,
+                                      void seq_query_func(struct Sequence *seq_reference,
+                                                          struct ListBase *seqbase,
+                                                          SeqCollection *collection));
+SeqCollection *SEQ_query_selected_strips(struct ListBase *seqbase);
+SeqCollection *SEQ_query_all_strips_recursive(ListBase *seqbase);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/sequencer/intern/iterator.c b/source/blender/sequencer/intern/iterator.c
index 356f5db45e8..e49594f91f5 100644
--- a/source/blender/sequencer/intern/iterator.c
+++ b/source/blender/sequencer/intern/iterator.c
@@ -31,110 +31,202 @@
 #include "DNA_scene_types.h"
 #include "DNA_sequence_types.h"
 
+#include "BLI_ghash.h"
 #include "BLI_listbase.h"
 
 #include "BKE_scene.h"
 
 #include "SEQ_iterator.h"
 
-/* ************************* iterator ************************** */
-/* *************** (replaces old WHILE_SEQ) ********************* */
-/* **************** use now SEQ_ALL_BEGIN () SEQ_ALL_END ***************** */
+/* -------------------------------------------------------------------- */
+/** \Iterator API
+ * \{ */
 
-/* sequence strip iterator:
- * - builds a full array, recursively into meta strips
+/**
+ * Utility function for SEQ_ITERATOR_FOREACH macro.
+ * Ensure, that iterator is initialized. During initialization return pointer to collection element
+ * and step gset iterator. When this function is called after iterator has been initialized, it
+ * will do nothing and return true.
+ *
+ * \param collection: collection to iterate
+ * \param iterator: iterator to be initialized
+ * \param r_seq: pointer to Sequence pointer
+ *
+ * \return false when iterator can not be initialized, true otherwise
  */
-
-static void seq_count(ListBase *seqbase, int *tot)
+bool SEQ_iterator_ensure(SeqCollection *collection, SeqIterator *iterator, Sequence **r_seq)
 {
-  Sequence *seq;
-
-  for (seq = seqbase->first; seq; seq = seq->next) {
-    (*tot)++;
-
-    if (seq->seqbase.first) {
-      seq_count(&seq->seqbase, tot);
-    }
+  if (iterator->iterator_initialized) {
+    return true;
   }
-}
 
-static void seq_build_array(ListBase *seqbase, Sequence ***array, int depth)
-{
-  Sequence *seq;
+  if (BLI_gset_len(collection->set) == 0) {
+    return false;
+  }
 
-  for (seq = seqbase->first; seq; seq = seq->next) {
-    seq->depth = depth;
+  iterator->collection = collection;
+  BLI_gsetIterator_init(&iterator->gsi, iterator->collection->set);
+  iterator->iterator_initialized = true;
 
-    if (seq->seqbase.first) {
-      seq_build_array(&seq->seqbase, array, depth + 1);
-    }
+  *r_seq = BLI_gsetIterator_getKey(&iterator->gsi);
+  BLI_gsetIterator_step(&iterator->gsi);
 
-    **array = seq;
-    (*array)++;
-  }
+  return true;
 }
 
-static void seq_array(Editing *ed,
-                      const bool use_current_sequences,
-                      Sequence ***r_seqarray,
-                      int *r_seqarray_len)
+/**
+ * Utility function for SEQ_ITERATOR_FOREACH macro.
+ * Yield collection element
+ *
+ * \param iterator: iterator to be initialized
+ *
+ * \return collection element or NULL when iteration has ended
+ */
+Sequence *SEQ_iterator_yield(SeqIterator *iterator)
 {
-  Sequence **array;
-
-  *r_seqarray = NULL;
-  *r_seqarray_len = 0;
+  Sequence *seq = BLI_gsetIterator_done(&iterator->gsi) ? NULL :
+                                                          BLI_gsetIterator_getKey(&iterator->gsi);
+  BLI_gsetIterator_step(&iterator->gsi);
+  return seq;
+}
 
-  if (ed == NULL) {
-    return;
-  }
+/**
+ * Free strip collection.
+ *
+ * \param collection: collection to be freed
+ */
+void SEQ_collection_free(SeqCollection *collection)
+{
+  BLI_gset_free(collection->set, NULL);
+  MEM_freeN(collection);
+}
 
-  if (use_current_sequences) {
-    seq_count(ed->seqbasep, r_seqarray_len);
-  }
-  else {
-    seq_count(&ed->seqbase, r_seqarray_len);
-  }
+/**
+ * Create new empty strip collection.
+ *
+ * \return empty strip collection.
+ */
+SeqCollection *SEQ_collection_create(void)
+{
+  SeqCollection *collection = MEM_callocN(sizeof(SeqCollection), "SeqCollection");
+  collection->set = BLI_gset_new(
+      BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "SeqCollection GSet");
+  return collection;
+}
 
-  if (*r_seqarray_len == 0) {
-    return;
+/**
+ * Query strips from seqbase. seq_reference is used by query function as filter condition.
+ *
+ * \param seq_reference: reference strip for query function
+ * \param seqbase: ListBase in which strips are queried
+ * \param seq_query_func: query function callback
+ * \return strip collection
+ */
+SeqCollection *SEQ_query_by_reference(Sequence *seq_reference,
+                                      ListBase *seqbase,
+                                      void seq_query_func(Sequence *seq_reference,
+                                                          ListBase *seqbase,
+                                                          SeqCollection *collection))
+{
+  SeqCollection *collection = SEQ_collection_create();
+  seq_query_func(seq_reference, seqbase, collection);
+  return collection;
+}
+/**
+ * Add strip to collection.
+ *
+ * \param seq: strip to be added
+ * \param collection: collection to which strip will be added
+ * \return false if strip is already in set, otherwise true
+ */
+bool SEQ_collection_append_strip(Sequence *seq, SeqCollection *collection)
+{
+  if (BLI_gset_lookup(collection->set, seq) != NULL) {
+    return false;
   }
+  BLI_gset_insert(collection->set, seq);
+  return true;
+}
 
-  *r_seqarray = array = MEM_mallocN(sizeof(Sequence *) * (*r_seqarray_len), "SeqArray");
-  if (use_current_sequences) {
-    seq_build_array(ed->seqbasep, &array, 0);
-  }
-  else {
-    seq_build_array(&ed->seqbase, &array, 0);
+/**
+ * Move strips from collection_src to collection_dst. Source collection will be freed.
+ *
+ * \param collection_dst: destination collection
+ * \param collection_src: source collection
+ */
+void SEQ_collection_merge(SeqCollection *collection_dst, SeqCollection *collection_src)
+{
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection_src) {
+    SEQ_collection_append_strip(seq, collection_dst);
   }
+  SEQ_collection_free(collection_src);
 }
 
-void SEQ_iterator_begin(Editing *ed, SeqIterator *iter, const bool use_current_sequences)
+/**
+ * Expand collection by running SEQ_query() for each strip, which will be used as reference.
+ * Results of these queries will be merged into provided collection.
+ *
+ * \param seqbase: ListBase in which strips are queried
+ * \param collection: SeqCollection to be expanded
+ * \param seq_query_func: query function callback
+ */
+void SEQ_collection_expand(ListBase *seqbase,
+                           SeqCollection *collection,
+                           void seq_query_func(Sequence *seq_reference,
+                                               ListBase *seqbase,
+                                               SeqCollection *collection))
 {
-  memset(iter, 0, sizeof(*iter));
-  seq_array(ed, use_current_sequences, &iter->array, &iter->tot);
+  /* Collect expanded results for each sequence in provided SeqIteratorCollection. */
+  ListBase expand_collections = {0};
 
-  if (iter->tot) {
-    iter->cur = 0;
-    iter->seq = iter->array[iter->cur];
-    iter->valid = 1;
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection) {
+    SeqCollection *expand_collection = SEQ_query_by_reference(seq, seqbase, seq_query_func);
+    BLI_addtail(&expand_collections, expand_collection);
+  }
+
+  /* Merge all expanded results in provided SeqIteratorCollection. */
+  LISTBASE_FOREACH_MUTABLE (SeqCollection *, expand_collection, &expand_collections) {
+    BLI_remlink(&expand_collections, expand_collection);
+    SEQ_collection_merge(collection, expand_collection);
   }
 }
 
-void SEQ_iterator_next(SeqIterator *iter)
+/** \} */
+
+/**
+ * Query all strips in seqbase and nested meta strips.
+ *
+ * \param seqbase: ListBase in which strips are queried
+ * \return strip collection
+ */
+SeqCollection *SEQ_query_all_strips_recursive(ListBase *seqbase)
 {
-  if (++iter->cur < iter->tot) {
-    iter->seq = iter->array[iter->cur];
-  }
-  else {
-    iter->valid = 0;
+  SeqCollection *collection = SEQ_collection_create();
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if (seq->type == SEQ_TYPE_META) {
+      SEQ_collection_merge(collection, SEQ_query_all_strips_recursive(&seq->seqbase));
+    }
+    SEQ_collection_append_strip(seq, collection);
   }
+  return collection;
 }
 
-void SEQ_iterator_end(SeqIterator *iter)
+/**
+ * Query all selected strips in seqbase.
+ *
+ * \param seqbase: ListBase in which strips are queried
+ * \return strip collection
+ */
+SeqCollection *SEQ_query_selected_strips(ListBase *seqbase)
 {
-  if (iter->array) {
-    MEM_freeN(iter->array);
+  SeqCollection *collection = SEQ_collection_create();
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if ((seq->flag & SELECT) == 0) {
+      continue;
+    }
+    SEQ_collection_append_strip(seq, collection);
   }
-
-  iter->valid = 0;
+  return collection;
 }