Smartly calculate real running time and pending time

4 files changed, 200 insertions, 1 deletions

diff --git a/app/models/ci/pipeline.rb b/app/models/ci/pipeline.rb
index 03812cd195f..e59c90e7e0c 100644
--- a/app/models/ci/pipeline.rb
+++ b/app/models/ci/pipeline.rb
@@ -258,7 +258,13 @@ module Ci
     end
 
     def update_duration
-      self.duration = calculate_duration
+      calculated_status = %w[success failed running canceled]
+      calculated_builds = builds.latest.where(status: calculated_status)
+      calculator = PipelineDuration.from_builds(calculated_builds)
+
+      self.duration = calculator.duration
+      self.pending_duration =
+        started_at - created_at + calculator.pending_duration
     end
 
     def execute_hooks
diff --git a/db/migrate/20160829122117_add_pending_duration_to_pipelines.rb b/db/migrate/20160829122117_add_pending_duration_to_pipelines.rb
new file mode 100644
index 00000000000..f056f45c840
--- /dev/null
+++ b/db/migrate/20160829122117_add_pending_duration_to_pipelines.rb
@@ -0,0 +1,8 @@
+class AddPendingDurationToPipelines < ActiveRecord::Migration
+
+  DOWNTIME = false
+
+  def change
+    add_column :ci_commits, :pending_duration, :integer
+  end
+end
diff --git a/lib/gitlab/ci/pipeline_duration.rb b/lib/gitlab/ci/pipeline_duration.rb
new file mode 100644
index 00000000000..e4c0be3b640
--- /dev/null
+++ b/lib/gitlab/ci/pipeline_duration.rb
@@ -0,0 +1,90 @@
+module Gitlab
+  module Ci
+    class PipelineDuration
+      SegmentStruct = Struct.new(:first, :last)
+      class Segment < SegmentStruct
+        def duration
+          last - first
+        end
+      end
+
+      def self.from_builds(builds)
+        now = Time.now
+
+        segments = builds.map do |b|
+          Segment.new(b.started_at, b.finished_at || now)
+        end
+
+        new(segments)
+      end
+
+      attr_reader :duration, :pending_duration
+
+      def initialize(segments)
+        process(segments.sort_by(&:first))
+      end
+
+      private
+
+      def process(segments)
+        merged = process_segments(segments)
+
+        @duration = process_duration(merged)
+        @pending_duration = process_pending_duration(merged, @duration)
+      end
+
+      def process_segments(segments)
+        if segments.empty?
+          segments
+        else
+          segments[1..-1].inject([segments.first]) do |current, target|
+            left, result = insert_segment(current, target)
+
+            if left # left is the latest one
+              result << left
+            else
+              result
+            end
+          end
+        end
+      end
+
+      def insert_segment(segments, init)
+        segments.inject([init, []]) do |target_result, member|
+          target, result = target_result
+
+          if target.nil? # done
+            result << member
+            [nil, result]
+          elsif merged = try_merge_segment(target, member) # overlapped
+            [merged, result] # merge and keep finding the hole
+          elsif target.last < member.first # found the hole
+            result << target << member
+            [nil, result]
+          else
+            result << member
+            target_result
+          end
+        end
+      end
+
+      def try_merge_segment(target, member)
+        if target.first <= member.last && target.last >= member.first
+          Segment.new([target.first, member.first].min,
+                      [target.last, member.last].max)
+        end
+      end
+
+      def process_duration(segments)
+        segments.inject(0) do |result, seg|
+          result + seg.duration
+        end
+      end
+
+      def process_pending_duration(segments, duration)
+        total = segments.last.last - segments.first.first
+        total - duration
+      end
+    end
+  end
+end
diff --git a/spec/lib/gitlab/ci/pipeline_duration_spec.rb b/spec/lib/gitlab/ci/pipeline_duration_spec.rb
new file mode 100644
index 00000000000..7ac9a3bd6bc
--- /dev/null
+++ b/spec/lib/gitlab/ci/pipeline_duration_spec.rb
@@ -0,0 +1,95 @@
+require 'spec_helper'
+
+describe Gitlab::Ci::PipelineDuration do
+  let(:calculator) { create_calculator(data) }
+
+  shared_examples 'calculating duration' do
+    it do
+      expect(calculator.duration).to eq(duration)
+      expect(calculator.pending_duration).to eq(pending_duration)
+    end
+  end
+
+  context 'test sample A' do
+    let(:data) do
+      [[0, 1],
+       [1, 2],
+       [3, 4],
+       [5, 6]]
+    end
+
+    let(:duration) { 4 }
+    let(:pending_duration) { 2 }
+
+    it_behaves_like 'calculating duration'
+  end
+
+  context 'test sample B' do
+    let(:data) do
+      [[0, 1],
+       [1, 2],
+       [2, 3],
+       [3, 4],
+       [0, 4]]
+    end
+
+    let(:duration) { 4 }
+    let(:pending_duration) { 0 }
+
+    it_behaves_like 'calculating duration'
+  end
+
+  context 'test sample C' do
+    let(:data) do
+      [[0, 4],
+       [2, 6],
+       [5, 7],
+       [8, 9]]
+    end
+
+    let(:duration) { 8 }
+    let(:pending_duration) { 1 }
+
+    it_behaves_like 'calculating duration'
+  end
+
+  context 'test sample D' do
+    let(:data) do
+      [[0, 1],
+       [2, 3],
+       [4, 5],
+       [6, 7]]
+    end
+
+    let(:duration) { 4 }
+    let(:pending_duration) { 3 }
+
+    it_behaves_like 'calculating duration'
+  end
+
+  context 'test sample E' do
+    let(:data) do
+      [[0, 1],
+       [3, 9],
+       [3, 4],
+       [3, 5],
+       [3, 8],
+       [4, 5],
+       [4, 7],
+       [5, 8]]
+    end
+
+    let(:duration) { 7 }
+    let(:pending_duration) { 2 }
+
+    it_behaves_like 'calculating duration'
+  end
+
+  def create_calculator(data)
+    segments = data.shuffle.map do |(first, last)|
+      Gitlab::Ci::PipelineDuration::Segment.new(first, last)
+    end
+
+    Gitlab::Ci::PipelineDuration.new(segments)
+  end
+end