From b44eaf8e0772d4ab076bd0df10b13085483e5e66 Mon Sep 17 00:00:00 2001 From: Timothy Andrew Date: Wed, 3 May 2017 09:29:49 +0000 Subject: Sort the network graph both by commit date and topographically. - Previously, we sorted commits by date, which seemed to work okay. - The one edge case where this failed was when multiple commits have the same commit date (for example: when a range of commits are cherry picked with a single command, they all have the same commit date [and different author dates]). - Commits with the same commit date would be sorted arbitrarily, and usually break the network graph. - This commit solves the problem by both sorting by date, and by sorting topographically (parents aren't displayed until all their children are displayed) - Include review comments from @adamniedzielski A more detailed explanation is present here: https://gitlab.com/gitlab-org/gitlab-ce/issues/30973#note_28706230 --- .../30973-network-graph-sorted-by-date-and-topo.yml | 4 ++++ lib/gitlab/git/repository.rb | 17 ++++++++++------- spec/lib/gitlab/git/repository_spec.rb | 2 +- spec/models/network/graph_spec.rb | 21 ++++++++++++++++++--- 4 files changed, 33 insertions(+), 11 deletions(-) create mode 100644 changelogs/unreleased/30973-network-graph-sorted-by-date-and-topo.yml diff --git a/changelogs/unreleased/30973-network-graph-sorted-by-date-and-topo.yml b/changelogs/unreleased/30973-network-graph-sorted-by-date-and-topo.yml new file mode 100644 index 00000000000..42426c1865e --- /dev/null +++ b/changelogs/unreleased/30973-network-graph-sorted-by-date-and-topo.yml @@ -0,0 +1,4 @@ +--- +title: Sort the network graph both by commit date and topographically +merge_request: 11057 +author: diff --git a/lib/gitlab/git/repository.rb b/lib/gitlab/git/repository.rb index acd0037ee4f..684b2e72875 100644 --- a/lib/gitlab/git/repository.rb +++ b/lib/gitlab/git/repository.rb @@ -499,8 +499,9 @@ module Gitlab # :contains is the commit contained by the refs from which to begin (SHA1 or name) # :max_count is the maximum number of commits to fetch # :skip is the number of commits to skip - # :order is the commits order and allowed value is :none (default), :date, or :topo - # commit ordering types are documented here: + # :order is the commits order and allowed value is :none (default), :date, + # :topo, or any combination of them (in an array). Commit ordering types + # are documented here: # http://www.rubydoc.info/github/libgit2/rugged/Rugged#SORT_NONE-constant) # def find_commits(options = {}) @@ -1290,16 +1291,18 @@ module Gitlab raise CommandError.new(e) end - # Returns the `Rugged` sorting type constant for a given - # sort type key. Valid keys are `:none`, `:topo`, and `:date` - def rugged_sort_type(key) + # Returns the `Rugged` sorting type constant for one or more given + # sort types. Valid keys are `:none`, `:topo`, and `:date`, or an array + # containing more than one of them. `:date` uses a combination of date and + # topological sorting to closer mimic git's native ordering. + def rugged_sort_type(sort_type) @rugged_sort_types ||= { none: Rugged::SORT_NONE, topo: Rugged::SORT_TOPO, - date: Rugged::SORT_DATE + date: Rugged::SORT_DATE | Rugged::SORT_TOPO } - @rugged_sort_types.fetch(key, Rugged::SORT_NONE) + @rugged_sort_types.fetch(sort_type, Rugged::SORT_NONE) end end end diff --git a/spec/lib/gitlab/git/repository_spec.rb b/spec/lib/gitlab/git/repository_spec.rb index ddedb7c3443..fea186fd4f4 100644 --- a/spec/lib/gitlab/git/repository_spec.rb +++ b/spec/lib/gitlab/git/repository_spec.rb @@ -1062,7 +1062,7 @@ describe Gitlab::Git::Repository, seed_helper: true do end it "allows ordering by date" do - expect_any_instance_of(Rugged::Walker).to receive(:sorting).with(Rugged::SORT_DATE) + expect_any_instance_of(Rugged::Walker).to receive(:sorting).with(Rugged::SORT_DATE | Rugged::SORT_TOPO) repository.find_commits(order: :date) end diff --git a/spec/models/network/graph_spec.rb b/spec/models/network/graph_spec.rb index 46b36e11c23..0fe8a591a45 100644 --- a/spec/models/network/graph_spec.rb +++ b/spec/models/network/graph_spec.rb @@ -10,17 +10,17 @@ describe Network::Graph, models: true do expect(graph.notes).to eq( { note_on_commit.commit_id => 1 } ) end - describe "#commits" do + describe '#commits' do let(:graph) { described_class.new(project, 'refs/heads/master', project.repository.commit, nil) } - it "returns a list of commits" do + it 'returns a list of commits' do commits = graph.commits expect(commits).not_to be_empty expect(commits).to all( be_kind_of(Network::Commit) ) end - it "sorts the commits by commit date (descending)" do + it 'it the commits by commit date (descending)' do # Remove duplicate timestamps because they make it harder to # assert that the commits are sorted as expected. commits = graph.commits.uniq(&:date) @@ -29,5 +29,20 @@ describe Network::Graph, models: true do expect(commits).not_to be_empty expect(commits.map(&:id)).to eq(sorted_commits.map(&:id)) end + + it 'sorts children before parents for commits with the same timestamp' do + commits_by_time = graph.commits.group_by(&:date) + + commits_by_time.each do |time, commits| + commit_ids = commits.map(&:id) + + commits.each_with_index do |commit, index| + parent_indexes = commit.parent_ids.map { |parent_id| commit_ids.find_index(parent_id) }.compact + + # All parents of the current commit should appear after it + expect(parent_indexes).to all( be > index ) + end + end + end end end -- cgit v1.2.1