Merge pull request #2847 from hiroponz/improve-overlap-lines

Improve overlap of lines in network graph

2 files changed, 71 insertions, 21 deletions

diff --git a/lib/gitlab/graph/commit.rb b/lib/gitlab/graph/commit.rb
index a6bf23a2381..13c8ebc9952 100644
--- a/lib/gitlab/graph/commit.rb
+++ b/lib/gitlab/graph/commit.rb
@@ -5,12 +5,13 @@ module Gitlab
     class Commit
       include ActionView::Helpers::TagHelper
 
-      attr_accessor :time, :space, :refs
+      attr_accessor :time, :space, :refs, :parent_spaces
 
       def initialize(commit)
         @_commit = commit
         @time = -1
         @space = 0
+        @parent_spaces = []
       end
 
       def method_missing(m, *args, &block)
@@ -28,6 +29,7 @@ module Gitlab
         }
         h[:time]    = time
         h[:space]   = space
+        h[:parent_spaces]   = parent_spaces
         h[:refs]    = refs.collect{|r|r.name}.join(" ") unless refs.nil?
         h[:id]      = sha
         h[:date]    = date
diff --git a/lib/gitlab/graph/json_builder.rb b/lib/gitlab/graph/json_builder.rb
index 5a2f27fc1af..90d384449f5 100644
--- a/lib/gitlab/graph/json_builder.rb
+++ b/lib/gitlab/graph/json_builder.rb
@@ -17,7 +17,6 @@ module Gitlab
 
         @commits = collect_commits
         @days = index_commits
-        @space = 0
       end
 
       def to_json(*args)
@@ -54,7 +53,7 @@ module Gitlab
       #
       # @return [Array<TimeDate>] list of commit dates corelated with time on commits
       def index_commits
-        days, heads = [], []
+        days, heads, times = [], [], []
         map = {}
 
         commits.reverse.each_with_index do |c,i|
@@ -62,6 +61,7 @@ module Gitlab
           days[i] = c.committed_date
           map[c.id] = c
           heads += c.refs unless c.refs.nil?
+          times[i] = c
         end
 
         heads.select!{|h| h.is_a? Grit::Head or h.is_a? Grit::Remote}
@@ -87,9 +87,62 @@ module Gitlab
           end
         end
 
+        # find parent spaces for not overlap lines
+        times.each do |c|
+          c.parent_spaces.concat(find_free_parent_spaces(c, map, times))
+        end
+
         days
       end
 
+      def find_free_parent_spaces(commit, map, times)
+        spaces = []
+
+        commit.parents.each do |p|
+          if map.include?(p.id) then
+            parent = map[p.id]
+
+            range = if commit.time < parent.time then
+                      commit.time..parent.time
+                    else
+                      parent.time..commit.time
+                    end
+
+            space = if commit.space >= parent.space then
+                      find_free_parent_space(range, map, parent.space, 1, commit.space, times)
+                    else
+                      find_free_parent_space(range, map, parent.space, -1, parent.space, times)
+                    end
+
+            mark_reserved(range, space)
+            spaces << space
+          end
+        end
+
+        spaces
+      end
+
+      def find_free_parent_space(range, map, space_base, space_step, space_default, times)
+        if is_overlap?(range, times, space_default) then
+          find_free_space(range, map, space_base, space_step)
+        else
+          space_default
+        end
+      end
+
+      def is_overlap?(range, times, overlap_space)
+        range.each do |i|
+          if i != range.first &&
+            i != range.last &&
+            times[i].space == overlap_space then
+
+            return true;
+          end
+        end
+
+        false
+      end
+
       # Add space mark on commit and its parents
       #
       # @param [Graph::Commit] the commit object.
@@ -99,8 +152,9 @@ module Gitlab
         if leaves.empty?
           return
         end
-        @space = find_free_space(leaves, map)
-        leaves.each{|l| l.space = @space}
+        time_range = leaves.last.time..leaves.first.time
+        space = find_free_space(time_range, map, 1, 2)
+        leaves.each{|l| l.space = space}
         # and mark it as reserved
         min_time = leaves.last.time
         parents = leaves.last.parents.collect
@@ -117,7 +171,7 @@ module Gitlab
         else
           max_time = parent_time - 1
         end
-        mark_reserved(min_time..max_time, @space)
+        mark_reserved(min_time..max_time, space)
 
         # Visit branching chains
         leaves.each do |l|
@@ -134,28 +188,22 @@ module Gitlab
         end
       end
 
-      def find_free_space(leaves, map)
-        time_range = leaves.last.time..leaves.first.time
+      def find_free_space(time_range, map, space_base, space_step)
         reserved = []
         for day in time_range
           reserved += @_reserved[day]
         end
-        space = base_space(leaves, map)
-        while (reserved.include? space) || (space == @space) do
-          space += 1
-        end
-
-        space
-      end
 
-      def base_space(leaves, map)
-        parents = []
-        leaves.each do |l|
-          parents.concat l.parents.collect.select{|p| map.include? p.id and map[p.id].space.nonzero?}
+        space = space_base
+        while reserved.include?(space) do
+          space += space_step
+          if space <= 0 then
+            space_step *= -1
+            space = space_base + space_step
+          end
         end
 
-        space = parents.map{|p| map[p.id].space}.max || 0
-        space += 1
+        space
       end
 
       # Takes most left subtree branch of commits