8 files changed, 247 insertions, 125 deletions

diff --git a/source/blender/sequencer/SEQ_iterator.h b/source/blender/sequencer/SEQ_iterator.h
index 669c55e1f4c..b4068bac1d0 100644
--- a/source/blender/sequencer/SEQ_iterator.h
+++ b/source/blender/sequencer/SEQ_iterator.h
@@ -27,39 +27,65 @@
 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;
+    if (ed != NULL) { \
+      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);
-int SEQ_iterator_seqbase_recursive_apply(struct ListBase *seqbase,
-                                         int (*apply_fn)(struct Sequence *seq, void *),
-                                         void *arg);
-int SEQ_iterator_recursive_apply(struct Sequence *seq,
-                                 int (*apply_fn)(struct Sequence *, void *),
-                                 void *arg);
+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 *collection);
+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/SEQ_utils.h b/source/blender/sequencer/SEQ_utils.h
index 45f53a64688..52fac5d7d0e 100644
--- a/source/blender/sequencer/SEQ_utils.h
+++ b/source/blender/sequencer/SEQ_utils.h
@@ -54,7 +54,12 @@ void SEQ_set_scale_to_fit(const struct Sequence *seq,
                           const int preview_width,
                           const int preview_height,
                           const eSeqImageFitMethod fit_method);
-
+int SEQ_seqbase_recursive_apply(struct ListBase *seqbase,
+                                int (*apply_fn)(struct Sequence *seq, void *),
+                                void *arg);
+int SEQ_recursive_apply(struct Sequence *seq,
+                        int (*apply_fn)(struct Sequence *, void *),
+                        void *arg);
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/sequencer/intern/effects.c b/source/blender/sequencer/intern/effects.c
index 278320d873e..d41a2c19d55 100644
--- a/source/blender/sequencer/intern/effects.c
+++ b/source/blender/sequencer/intern/effects.c
@@ -3033,10 +3033,9 @@ static ImBuf *do_adjustment_impl(const SeqRenderData *context, Sequence *seq, fl
     i = seq_render_give_ibuf_seqbase(context, timeline_frame, seq->machine - 1, seqbasep);
   }
 
-  /* found nothing? so let's work the way up the metastrip stack, so
+  /* Found nothing? so let's work the way up the meta-strip stack, so
    * that it is possible to group a bunch of adjustment strips into
-   * a metastrip and have that work on everything below the metastrip
-   */
+   * a meta-strip and have that work on everything below the meta-strip. */
 
   if (!i) {
     Sequence *meta;
diff --git a/source/blender/sequencer/intern/iterator.c b/source/blender/sequencer/intern/iterator.c
index f99667dea04..e49594f91f5 100644
--- a/source/blender/sequencer/intern/iterator.c
+++ b/source/blender/sequencer/intern/iterator.c
@@ -31,138 +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;
-
-  if (ed == NULL) {
-    return;
-  }
-
-  if (use_current_sequences) {
-    seq_count(ed->seqbasep, r_seqarray_len);
-  }
-  else {
-    seq_count(&ed->seqbase, r_seqarray_len);
-  }
-
-  if (*r_seqarray_len == 0) {
-    return;
-  }
+  Sequence *seq = BLI_gsetIterator_done(&iterator->gsi) ? NULL :
+                                                          BLI_gsetIterator_getKey(&iterator->gsi);
+  BLI_gsetIterator_step(&iterator->gsi);
+  return seq;
+}
 
-  *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);
-  }
+/**
+ * Free strip collection.
+ *
+ * \param collection: collection to be freed
+ */
+void SEQ_collection_free(SeqCollection *collection)
+{
+  BLI_gset_free(collection->set, NULL);
+  MEM_freeN(collection);
 }
 
-void SEQ_iterator_begin(Editing *ed, SeqIterator *iter, const bool use_current_sequences)
+/**
+ * Create new empty strip collection.
+ *
+ * \return empty strip collection.
+ */
+SeqCollection *SEQ_collection_create(void)
 {
-  memset(iter, 0, sizeof(*iter));
-  seq_array(ed, use_current_sequences, &iter->array, &iter->tot);
+  SeqCollection *collection = MEM_callocN(sizeof(SeqCollection), "SeqCollection");
+  collection->set = BLI_gset_new(
+      BLI_ghashutil_ptrhash, BLI_ghashutil_ptrcmp, "SeqCollection GSet");
+  return collection;
+}
 
-  if (iter->tot) {
-    iter->cur = 0;
-    iter->seq = iter->array[iter->cur];
-    iter->valid = 1;
+/**
+ * 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;
 }
 
-void SEQ_iterator_next(SeqIterator *iter)
+/**
+ * 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)
 {
-  if (++iter->cur < iter->tot) {
-    iter->seq = iter->array[iter->cur];
-  }
-  else {
-    iter->valid = 0;
+  Sequence *seq;
+  SEQ_ITERATOR_FOREACH (seq, collection_src) {
+    SEQ_collection_append_strip(seq, collection_dst);
   }
+  SEQ_collection_free(collection_src);
 }
 
-void SEQ_iterator_end(SeqIterator *iter)
+/**
+ * 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))
 {
-  if (iter->array) {
-    MEM_freeN(iter->array);
+  /* Collect expanded results for each sequence in provided SeqIteratorCollection. */
+  ListBase expand_collections = {0};
+
+  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);
   }
 
-  iter->valid = 0;
+  /* 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);
+  }
 }
 
-int SEQ_iterator_seqbase_recursive_apply(ListBase *seqbase,
-                                         int (*apply_fn)(Sequence *seq, void *),
-                                         void *arg)
+/** \} */
+
+/**
+ * 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)
 {
-  Sequence *iseq;
-  for (iseq = seqbase->first; iseq; iseq = iseq->next) {
-    if (SEQ_iterator_recursive_apply(iseq, apply_fn, arg) == -1) {
-      return -1; /* bail out */
+  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 1;
+  return collection;
 }
 
-int SEQ_iterator_recursive_apply(Sequence *seq, int (*apply_fn)(Sequence *, void *), void *arg)
+/**
+ * Query all selected strips in seqbase.
+ *
+ * \param seqbase: ListBase in which strips are queried
+ * \return strip collection
+ */
+SeqCollection *SEQ_query_selected_strips(ListBase *seqbase)
 {
-  int ret = apply_fn(seq, arg);
-
-  if (ret == -1) {
-    return -1; /* bail out */
-  }
-
-  if (ret && seq->seqbase.first) {
-    ret = SEQ_iterator_seqbase_recursive_apply(&seq->seqbase, apply_fn, arg);
+  SeqCollection *collection = SEQ_collection_create();
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if ((seq->flag & SELECT) == 0) {
+      continue;
+    }
+    SEQ_collection_append_strip(seq, collection);
   }
-
-  return ret;
+  return collection;
 }
diff --git a/source/blender/sequencer/intern/sequencer.c b/source/blender/sequencer/intern/sequencer.c
index cc11796496c..55c14944a23 100644
--- a/source/blender/sequencer/intern/sequencer.c
+++ b/source/blender/sequencer/intern/sequencer.c
@@ -448,8 +448,8 @@ static Sequence *seq_dupli(const Scene *scene_src,
     seqn->strip->stripdata = NULL;
 
     BLI_listbase_clear(&seqn->seqbase);
-    /* WATCH OUT!!! - This metastrip is not recursively duplicated here - do this after!!! */
-    /* - seq_dupli_recursive(&seq->seqbase, &seqn->seqbase);*/
+    /* WARNING: This meta-strip is not recursively duplicated here - do this after! */
+    // seq_dupli_recursive(&seq->seqbase, &seqn->seqbase);
   }
   else if (seq->type == SEQ_TYPE_SCENE) {
     seqn->strip->stripdata = NULL;
diff --git a/source/blender/sequencer/intern/strip_edit.c b/source/blender/sequencer/intern/strip_edit.c
index 4a27fb3a087..f1d4592fdec 100644
--- a/source/blender/sequencer/intern/strip_edit.c
+++ b/source/blender/sequencer/intern/strip_edit.c
@@ -149,7 +149,7 @@ void SEQ_edit_update_muting(Editing *ed)
 static void sequencer_flag_users_for_removal(Scene *scene, ListBase *seqbase, Sequence *seq)
 {
   LISTBASE_FOREACH (Sequence *, user_seq, seqbase) {
-    /* Look in metas for usage of seq. */
+    /* Look in meta-strips for usage of seq. */
     if (user_seq->type == SEQ_TYPE_META) {
       sequencer_flag_users_for_removal(scene, &user_seq->seqbase, seq);
     }
diff --git a/source/blender/sequencer/intern/strip_time.c b/source/blender/sequencer/intern/strip_time.c
index 4a01b0e1938..a7a6e2595be 100644
--- a/source/blender/sequencer/intern/strip_time.c
+++ b/source/blender/sequencer/intern/strip_time.c
@@ -187,7 +187,7 @@ static void seq_time_update_meta_strip_range(Scene *scene, Sequence *seq_meta)
 {
   seq_time_update_meta_strip(scene, seq_meta);
 
-  /*  Prevent metastrip to move in timeline. */
+  /* Prevent meta-strip to move in timeline. */
   SEQ_transform_set_left_handle_frame(seq_meta, seq_meta->startdisp);
   SEQ_transform_set_right_handle_frame(seq_meta, seq_meta->enddisp);
 }
@@ -196,7 +196,7 @@ void SEQ_time_update_sequence(Scene *scene, Sequence *seq)
 {
   Sequence *seqm;
 
-  /* check all metas recursively */
+  /* Check all meta-strips recursively. */
   seqm = seq->seqbase.first;
   while (seqm) {
     if (seqm->seqbase.first) {
diff --git a/source/blender/sequencer/intern/utils.c b/source/blender/sequencer/intern/utils.c
index a15465eb3c0..6d5332b2b15 100644
--- a/source/blender/sequencer/intern/utils.c
+++ b/source/blender/sequencer/intern/utils.c
@@ -160,7 +160,7 @@ void SEQ_sequence_base_unique_name_recursive(ListBase *seqbasep, Sequence *seq)
   while (sui.match) {
     sui.match = 0;
     seqbase_unique_name(seqbasep, &sui);
-    SEQ_iterator_seqbase_recursive_apply(seqbasep, seqbase_unique_name_recursive_fn, &sui);
+    SEQ_seqbase_recursive_apply(seqbasep, seqbase_unique_name_recursive_fn, &sui);
   }
 
   BLI_strncpy(seq->name + 2, sui.name_dest, sizeof(seq->name) - 2);
@@ -584,3 +584,31 @@ void SEQ_set_scale_to_fit(const Sequence *seq,
       break;
   }
 }
+
+int SEQ_seqbase_recursive_apply(ListBase *seqbase,
+                                int (*apply_fn)(Sequence *seq, void *),
+                                void *arg)
+{
+  Sequence *iseq;
+  for (iseq = seqbase->first; iseq; iseq = iseq->next) {
+    if (SEQ_recursive_apply(iseq, apply_fn, arg) == -1) {
+      return -1; /* bail out */
+    }
+  }
+  return 1;
+}
+
+int SEQ_recursive_apply(Sequence *seq, int (*apply_fn)(Sequence *, void *), void *arg)
+{
+  int ret = apply_fn(seq, arg);
+
+  if (ret == -1) {
+    return -1; /* bail out */
+  }
+
+  if (ret && seq->seqbase.first) {
+    ret = SEQ_seqbase_recursive_apply(&seq->seqbase, apply_fn, arg);
+  }
+
+  return ret;
+}