VSE: Move remove gaps operator logic to module code

Logic was broken into finding gaps and ofsetting strips.
Functions were modified so they work on explicitly defined seqbase,
so they can be used as python API functions.

Functional changes:
 - Improve performance by calculating gap length and offseting strips
   at once. Previously strips were offset by one frame.
 - Calculate gap from start frame. Previously gap was considered only
   inbetween strips.

Reviewed By: sergey

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

10 files changed, 212 insertions, 122 deletions

diff --git a/source/blender/editors/space_sequencer/sequencer_draw.c b/source/blender/editors/space_sequencer/sequencer_draw.c
index 081714991ff..e31fa3205ba 100644
--- a/source/blender/editors/space_sequencer/sequencer_draw.c
+++ b/source/blender/editors/space_sequencer/sequencer_draw.c
@@ -2292,7 +2292,7 @@ void draw_timeline_seq(const bContext *C, ARegion *region)
 
   UI_view2d_view_ortho(v2d);
   /* Get timeline bound-box, needed for the scroll-bars. */
-  boundbox_seq(scene, &v2d->tot);
+  SEQ_timeline_boundbox(scene, ed->seqbasep, &v2d->tot);
   draw_seq_backdrop(v2d);
   UI_view2d_constant_grid_draw(v2d, FPS);
 
diff --git a/source/blender/editors/space_sequencer/sequencer_edit.c b/source/blender/editors/space_sequencer/sequencer_edit.c
index 953a77d22a6..184f821d411 100644
--- a/source/blender/editors/space_sequencer/sequencer_edit.c
+++ b/source/blender/editors/space_sequencer/sequencer_edit.c
@@ -183,117 +183,13 @@ bool sequencer_view_strips_poll(bContext *C)
 /** \name Remove Gaps Operator
  * \{ */
 
-static bool sequence_offset_after_frame(Scene *scene, const int delta, const int timeline_frame)
-{
-  Sequence *seq;
-  Editing *ed = BKE_sequencer_editing_get(scene, false);
-  bool done = false;
-  TimeMarker *marker;
-
-  /* All strips >= timeline_frame are shifted. */
-
-  if (ed == NULL) {
-    return 0;
-  }
-
-  for (seq = ed->seqbasep->first; seq; seq = seq->next) {
-    if (seq->startdisp >= timeline_frame) {
-      BKE_sequence_translate(scene, seq, delta);
-      BKE_sequence_calc(scene, seq);
-      BKE_sequence_invalidate_cache_preprocessed(scene, seq);
-      done = true;
-    }
-  }
-
-  if (!scene->toolsettings->lock_markers) {
-    for (marker = scene->markers.first; marker; marker = marker->next) {
-      if (marker->frame >= timeline_frame) {
-        marker->frame += delta;
-      }
-    }
-  }
-
-  return done;
-}
-
-void boundbox_seq(Scene *scene, rctf *rect)
-{
-  Sequence *seq;
-  Editing *ed = BKE_sequencer_editing_get(scene, false);
-  float min[2], max[2];
-
-  if (ed == NULL) {
-    return;
-  }
-
-  min[0] = SFRA;
-  max[0] = EFRA + 1;
-  min[1] = 0.0;
-  max[1] = 8.0;
-
-  seq = ed->seqbasep->first;
-  while (seq) {
-
-    if (min[0] > seq->startdisp - 1) {
-      min[0] = seq->startdisp - 1;
-    }
-    if (max[0] < seq->enddisp + 1) {
-      max[0] = seq->enddisp + 1;
-    }
-    if (max[1] < seq->machine + 2) {
-      max[1] = seq->machine + 2;
-    }
-
-    seq = seq->next;
-  }
-
-  rect->xmin = min[0];
-  rect->xmax = max[0];
-  rect->ymin = min[1];
-  rect->ymax = max[1];
-}
-
 static int sequencer_gap_remove_exec(bContext *C, wmOperator *op)
 {
   Scene *scene = CTX_data_scene(C);
-  rctf rectf;
-  int timeline_frame, efra, sfra;
-  bool first = false, done;
-  bool do_all = RNA_boolean_get(op->ptr, "all");
-
-  /* Get first and last frame. */
-  boundbox_seq(scene, &rectf);
-  sfra = (int)rectf.xmin;
-  efra = (int)rectf.xmax;
-
-  /* Check if the current frame has a gap already. */
-  for (timeline_frame = CFRA; timeline_frame >= sfra; timeline_frame--) {
-    if (SEQ_render_evaluate_frame(scene, timeline_frame)) {
-      first = true;
-      break;
-    }
-  }
+  const bool do_all = RNA_boolean_get(op->ptr, "all");
+  const Editing *ed = BKE_sequencer_editing_get(scene, false);
 
-  for (; timeline_frame < efra; timeline_frame++) {
-    /* There's still no strip to remove a gap for. */
-    if (first == false) {
-      if (SEQ_render_evaluate_frame(scene, timeline_frame)) {
-        first = true;
-      }
-    }
-    else if (SEQ_render_evaluate_frame(scene, timeline_frame) == 0) {
-      done = true;
-      while (SEQ_render_evaluate_frame(scene, timeline_frame) == 0) {
-        done = sequence_offset_after_frame(scene, -1, timeline_frame);
-        if (done == false) {
-          break;
-        }
-      }
-      if (done == false || do_all == false) {
-        break;
-      }
-    }
-  }
+  SEQ_edit_remove_gaps(scene, ed->seqbasep, CFRA, do_all);
 
   WM_event_add_notifier(C, NC_SCENE | ND_SEQUENCER, scene);
   DEG_id_tag_update(&scene->id, ID_RECALC_SEQUENCER_STRIPS);
@@ -330,9 +226,9 @@ void SEQUENCER_OT_gap_remove(struct wmOperatorType *ot)
 static int sequencer_gap_insert_exec(bContext *C, wmOperator *op)
 {
   Scene *scene = CTX_data_scene(C);
-  int frames = RNA_int_get(op->ptr, "frames");
-
-  sequence_offset_after_frame(scene, frames, CFRA);
+  const int frames = RNA_int_get(op->ptr, "frames");
+  const Editing *ed = BKE_sequencer_editing_get(scene, false);
+  SEQ_offset_after_frame(scene, ed->seqbasep, frames, CFRA);
 
   WM_event_add_notifier(C, NC_SCENE | ND_SEQUENCER, scene);
 
diff --git a/source/blender/editors/space_sequencer/sequencer_intern.h b/source/blender/editors/space_sequencer/sequencer_intern.h
index 1ea4fb05d53..6ccfd3a9045 100644
--- a/source/blender/editors/space_sequencer/sequencer_intern.h
+++ b/source/blender/editors/space_sequencer/sequencer_intern.h
@@ -71,7 +71,6 @@ struct ImBuf *sequencer_ibuf_get(struct Main *bmain,
 /* sequencer_edit.c */
 struct View2D;
 void seq_rectf(struct Sequence *seq, struct rctf *rectf);
-void boundbox_seq(struct Scene *scene, struct rctf *rect);
 struct Sequence *find_nearest_seq(struct Scene *scene,
                                   struct View2D *v2d,
                                   int *hand,
diff --git a/source/blender/editors/space_sequencer/sequencer_view.c b/source/blender/editors/space_sequencer/sequencer_view.c
index 75d92d5f00d..d2166705943 100644
--- a/source/blender/editors/space_sequencer/sequencer_view.c
+++ b/source/blender/editors/space_sequencer/sequencer_view.c
@@ -87,8 +87,14 @@ static int sequencer_view_all_exec(bContext *C, wmOperator *op)
   rctf box;
 
   const int smooth_viewtx = WM_operator_smooth_viewtx_get(op);
+  Scene *scene = CTX_data_scene(C);
+  const Editing *ed = BKE_sequencer_editing_get(scene, false);
+
+  if (ed == NULL) {
+    return OPERATOR_FINISHED;
+  }
 
-  boundbox_seq(CTX_data_scene(C), &box);
+  SEQ_timeline_boundbox(scene, ed->seqbasep, &box);
   UI_view2d_smooth_view(C, region, &box, smooth_viewtx);
   return OPERATOR_FINISHED;
 }
diff --git a/source/blender/sequencer/SEQ_sequencer.h b/source/blender/sequencer/SEQ_sequencer.h
index 11e213d842d..a024d5e10d3 100644
--- a/source/blender/sequencer/SEQ_sequencer.h
+++ b/source/blender/sequencer/SEQ_sequencer.h
@@ -161,7 +161,7 @@ void SEQ_render_new_render_data(struct Main *bmain,
                                 int preview_render_size,
                                 int for_render,
                                 SeqRenderData *r_context);
-int SEQ_render_evaluate_frame(struct Scene *scene, int timeline_frame);
+int SEQ_render_evaluate_frame(struct ListBase *seqbase, int timeline_frame);
 struct StripElem *SEQ_render_give_stripelem(struct Sequence *seq, int timeline_frame);
 
 /* **********************************************************************
@@ -595,6 +595,33 @@ struct Sequence *SEQ_edit_strip_split(struct Main *bmain,
                                       struct Sequence *seq,
                                       const int timeline_frame,
                                       const eSeqSplitMethod method);
+bool SEQ_edit_remove_gaps(struct Scene *scene,
+                          struct ListBase *seqbase,
+                          const int initial_frame,
+                          const bool remove_all_gaps);
+
+/* **********************************************************************
+ * strip_time.c
+ *
+ * Editing functions
+ * **********************************************************************
+ */
+
+void SEQ_timeline_boundbox(const struct Scene *scene,
+                           const struct ListBase *seqbase,
+                           struct rctf *rect);
+
+/* **********************************************************************
+ * strip_transform.c
+ *
+ * Editing functions
+ * **********************************************************************
+ */
+
+void SEQ_offset_after_frame(struct Scene *scene,
+                            struct ListBase *seqbase,
+                            const int delta,
+                            const int timeline_frame);
 
 #ifdef __cplusplus
 }
diff --git a/source/blender/sequencer/intern/render.c b/source/blender/sequencer/intern/render.c
index 008ea1cd3a0..155258dc2c3 100644
--- a/source/blender/sequencer/intern/render.c
+++ b/source/blender/sequencer/intern/render.c
@@ -337,16 +337,17 @@ static int evaluate_seq_frame_gen(Sequence **seq_arr,
   return totseq;
 }
 
-int SEQ_render_evaluate_frame(Scene *scene, int timeline_frame)
+/**
+ * Count number of strips in timeline at timeline_frame
+ *
+ * \param seqbase: ListBase in which strips are located
+ * \param timeline_frame: frame on timeline from where gaps are searched for
+ * \return number of strips
+ */
+int SEQ_render_evaluate_frame(ListBase *seqbase, int timeline_frame)
 {
-  Editing *ed = BKE_sequencer_editing_get(scene, false);
   Sequence *seq_arr[MAXSEQ + 1];
-
-  if (ed == NULL) {
-    return 0;
-  }
-
-  return evaluate_seq_frame_gen(seq_arr, ed->seqbasep, timeline_frame, 0);
+  return evaluate_seq_frame_gen(seq_arr, seqbase, timeline_frame, 0);
 }
 
 static bool video_seq_is_rendered(Sequence *seq)
diff --git a/source/blender/sequencer/intern/strip_edit.c b/source/blender/sequencer/intern/strip_edit.c
index 3137a471470..a29810cc9ee 100644
--- a/source/blender/sequencer/intern/strip_edit.c
+++ b/source/blender/sequencer/intern/strip_edit.c
@@ -38,6 +38,8 @@
 #include "BKE_scene.h"
 #include "BKE_sound.h"
 
+#include "strip_time.h"
+
 #include "SEQ_sequencer.h"
 
 int BKE_sequence_swap(Sequence *seq_a, Sequence *seq_b, const char **error_str)
@@ -319,3 +321,36 @@ Sequence *SEQ_edit_strip_split(Main *bmain,
   BKE_sequence_calc(scene, right_seq);
   return right_seq;
 }
+
+/**
+ * Find gap after initial_frame and move strips on right side to close the gap
+ *
+ * \param scene: Scene in which strips are located
+ * \param seqbase: ListBase in which strips are located
+ * \param initial_frame: frame on timeline from where gaps are searched for
+ * \param remove_all_gaps: remove all gaps instead of one gap
+ * \return true if gap is removed, otherwise false
+ */
+bool SEQ_edit_remove_gaps(Scene *scene,
+                          ListBase *seqbase,
+                          const int initial_frame,
+                          const bool remove_all_gaps)
+{
+  GapInfo gap_info = {0};
+  seq_time_gap_info_get(scene, seqbase, initial_frame, &gap_info);
+
+  if (!gap_info.gap_exists) {
+    return false;
+  }
+
+  if (remove_all_gaps) {
+    while (gap_info.gap_exists) {
+      SEQ_offset_after_frame(scene, seqbase, -gap_info.gap_length, gap_info.gap_start_frame);
+      seq_time_gap_info_get(scene, seqbase, initial_frame, &gap_info);
+    }
+  }
+  else {
+    SEQ_offset_after_frame(scene, seqbase, -gap_info.gap_length, gap_info.gap_start_frame);
+  }
+  return true;
+}
diff --git a/source/blender/sequencer/intern/strip_time.c b/source/blender/sequencer/intern/strip_time.c
index a0ae6d6f16d..015d81cc217 100644
--- a/source/blender/sequencer/intern/strip_time.c
+++ b/source/blender/sequencer/intern/strip_time.c
@@ -351,3 +351,87 @@ float BKE_sequence_get_fps(Scene *scene, Sequence *seq)
   }
   return 0.0f;
 }
+
+/**
+ * Define boundary rectangle of sequencer timeline and fill in rect data
+ *
+ * \param scene: Scene in which strips are located
+ * \param seqbase: ListBase in which strips are located
+ * \param rect: data structure describing rectangle, that will be filled in by this function
+ */
+void SEQ_timeline_boundbox(const Scene *scene, const ListBase *seqbase, rctf *rect)
+{
+  float min[2], max[2];
+  min[0] = scene->r.sfra;
+  max[0] = scene->r.efra + 1;
+  min[1] = 0.0;
+  max[1] = 8.0;
+
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if (min[0] > seq->startdisp - 1) {
+      min[0] = seq->startdisp - 1;
+    }
+    if (max[0] < seq->enddisp + 1) {
+      max[0] = seq->enddisp + 1;
+    }
+    if (max[1] < seq->machine + 2) {
+      max[1] = seq->machine + 2;
+    }
+  }
+
+  rect->xmin = min[0];
+  rect->xmax = max[0];
+  rect->ymin = min[1];
+  rect->ymax = max[1];
+}
+
+/**
+ * Find first gap between strips after initial_frame and describe it by filling data of r_gap_info
+ *
+ * \param scene: Scene in which strips are located
+ * \param seqbase: ListBase in which strips are located
+ * \param initial_frame: frame on timeline from where gaps are searched for
+ * \param r_gap_info: data structure describing gap, that will be filled in by this function
+ */
+void seq_time_gap_info_get(const Scene *scene,
+                           ListBase *seqbase,
+                           const int initial_frame,
+                           GapInfo *r_gap_info)
+{
+  rctf rectf;
+  /* Get first and last frame. */
+  SEQ_timeline_boundbox(scene, seqbase, &rectf);
+  const int sfra = (int)rectf.xmin;
+  const int efra = (int)rectf.xmax;
+  int timeline_frame = initial_frame;
+  r_gap_info->gap_exists = false;
+
+  if (SEQ_render_evaluate_frame(seqbase, initial_frame) == 0) {
+    /* Search backward for gap_start_frame. */
+    for (; timeline_frame >= sfra; timeline_frame--) {
+      if (SEQ_render_evaluate_frame(seqbase, timeline_frame) != 0) {
+        break;
+      }
+    }
+    r_gap_info->gap_start_frame = timeline_frame + 1;
+    timeline_frame = initial_frame;
+  }
+  else {
+    /* Search forward for gap_start_frame. */
+    for (; timeline_frame <= efra; timeline_frame++) {
+      if (SEQ_render_evaluate_frame(seqbase, timeline_frame) == 0) {
+        r_gap_info->gap_start_frame = timeline_frame;
+        break;
+      }
+    }
+  }
+  /* Search forward for gap_end_frame. */
+  for (; timeline_frame <= efra; timeline_frame++) {
+    if (SEQ_render_evaluate_frame(seqbase, timeline_frame) != 0) {
+      const int gap_end_frame = timeline_frame;
+      r_gap_info->gap_length = gap_end_frame - r_gap_info->gap_start_frame;
+      r_gap_info->gap_exists = true;
+      break;
+    }
+  }
+}
diff --git a/source/blender/sequencer/intern/strip_time.h b/source/blender/sequencer/intern/strip_time.h
index e4fb7f1d2ec..e435ff1ec5d 100644
--- a/source/blender/sequencer/intern/strip_time.h
+++ b/source/blender/sequencer/intern/strip_time.h
@@ -29,10 +29,22 @@ extern "C" {
 
 struct Scene;
 struct Sequence;
+struct ListBase;
 
 float seq_give_frame_index(struct Sequence *seq, float timeline_frame);
 void seq_update_sound_bounds_recursive(struct Scene *scene, struct Sequence *metaseq);
 
+/* Describes gap between strips in timeline. */
+typedef struct GapInfo {
+  int gap_start_frame; /* Start frame of the gap. */
+  int gap_length;      /* Length of the gap. */
+  bool gap_exists;     /* False if there are no gaps. */
+} GapInfo;
+void seq_time_gap_info_get(const struct Scene *scene,
+                           struct ListBase *seqbase,
+                           const int initial_frame,
+                           struct GapInfo *r_gap_info);
+
 #ifdef __cplusplus
 }
 #endif
diff --git a/source/blender/sequencer/intern/strip_transform.c b/source/blender/sequencer/intern/strip_transform.c
index 233f8e5b22e..4aabe87bce1 100644
--- a/source/blender/sequencer/intern/strip_transform.c
+++ b/source/blender/sequencer/intern/strip_transform.c
@@ -397,3 +397,33 @@ bool BKE_sequence_base_shuffle_time(ListBase *seqbasep,
 
   return offset ? false : true;
 }
+
+/**
+ * Move strips and markers (if not locked) that start after timeline_frame by delta frames
+ *
+ * \param scene: Scene in which strips are located
+ * \param seqbase: ListBase in which strips are located
+ * \param delta: offset in frames to be applied
+ * \param timeline_frame: frame on timeline from where strips are moved
+ */
+void SEQ_offset_after_frame(Scene *scene,
+                            ListBase *seqbase,
+                            const int delta,
+                            const int timeline_frame)
+{
+  LISTBASE_FOREACH (Sequence *, seq, seqbase) {
+    if (seq->startdisp >= timeline_frame) {
+      BKE_sequence_translate(scene, seq, delta);
+      BKE_sequence_calc(scene, seq);
+      BKE_sequence_invalidate_cache_preprocessed(scene, seq);
+    }
+  }
+
+  if (!scene->toolsettings->lock_markers) {
+    LISTBASE_FOREACH (TimeMarker *, marker, &scene->markers) {
+      if (marker->frame >= timeline_frame) {
+        marker->frame += delta;
+      }
+    }
+  }
+}