diff options
author | Douwe Maan <douwe@gitlab.com> | 2017-03-14 17:00:13 +0000 |
---|---|---|
committer | Douwe Maan <douwe@gitlab.com> | 2017-03-14 17:00:13 +0000 |
commit | 55e0923b7e36d2e27bc11d6edfd6369135122f78 (patch) | |
tree | cc970b86007d6008017f33a61f1f2b326bd10449 | |
parent | ffcddb295950729dbc4ee7a3c0e32f7dec00da99 (diff) | |
parent | e752d6d157321f9f10d70cdef1ce1992e263634f (diff) | |
download | gitlab-ce-55e0923b7e36d2e27bc11d6edfd6369135122f78.tar.gz |
Merge branch 'fix_relative_position_calculation' into 'master'
Fix relative position calculation
Closes #29269
See merge request !9837
-rw-r--r-- | .flayignore | 1 | ||||
-rw-r--r-- | app/models/concerns/relative_positioning.rb | 90 | ||||
-rw-r--r-- | db/post_migrate/20170309171644_reset_relative_position_for_issue.rb | 17 | ||||
-rw-r--r-- | spec/models/concerns/relative_positioning_spec.rb | 120 |
4 files changed, 192 insertions, 36 deletions
diff --git a/.flayignore b/.flayignore index fc64b0b5892..47597025115 100644 --- a/.flayignore +++ b/.flayignore @@ -2,3 +2,4 @@ lib/gitlab/sanitizers/svg/whitelist.rb lib/gitlab/diff/position_tracer.rb app/policies/project_policy.rb +app/models/concerns/relative_positioning.rb diff --git a/app/models/concerns/relative_positioning.rb b/app/models/concerns/relative_positioning.rb index 603f2dd7e5d..f1d8532a6d6 100644 --- a/app/models/concerns/relative_positioning.rb +++ b/app/models/concerns/relative_positioning.rb @@ -2,16 +2,14 @@ module RelativePositioning extend ActiveSupport::Concern MIN_POSITION = 0 + START_POSITION = Gitlab::Database::MAX_INT_VALUE / 2 MAX_POSITION = Gitlab::Database::MAX_INT_VALUE + IDEAL_DISTANCE = 500 included do after_save :save_positionable_neighbours end - def min_relative_position - self.class.in_projects(project.id).minimum(:relative_position) - end - def max_relative_position self.class.in_projects(project.id).maximum(:relative_position) end @@ -26,7 +24,7 @@ module RelativePositioning maximum(:relative_position) end - prev_pos || MIN_POSITION + prev_pos end def next_relative_position @@ -39,55 +37,95 @@ module RelativePositioning minimum(:relative_position) end - next_pos || MAX_POSITION + next_pos end def move_between(before, after) return move_after(before) unless after return move_before(after) unless before + # If there is no place to insert an issue we need to create one by moving the before issue closer + # to its predecessor. This process will recursively move all the predecessors until we have a place + if (after.relative_position - before.relative_position) < 2 + before.move_before + @positionable_neighbours = [before] + end + + self.relative_position = position_between(before.relative_position, after.relative_position) + end + + def move_after(before = self) pos_before = before.relative_position + pos_after = before.next_relative_position + + if before.shift_after? + issue_to_move = self.class.in_projects(project.id).find_by!(relative_position: pos_after) + issue_to_move.move_after + @positionable_neighbours = [issue_to_move] + + pos_after = issue_to_move.relative_position + end + + self.relative_position = position_between(pos_before, pos_after) + end + + def move_before(after = self) pos_after = after.relative_position + pos_before = after.prev_relative_position - if pos_after && (pos_before == pos_after) - self.relative_position = pos_before - before.move_before(self) - after.move_after(self) + if after.shift_before? + issue_to_move = self.class.in_projects(project.id).find_by!(relative_position: pos_before) + issue_to_move.move_before + @positionable_neighbours = [issue_to_move] - @positionable_neighbours = [before, after] - else - self.relative_position = position_between(pos_before, pos_after) + pos_before = issue_to_move.relative_position end + + self.relative_position = position_between(pos_before, pos_after) end - def move_before(after) - self.relative_position = position_between(after.prev_relative_position, after.relative_position) + def move_to_end + self.relative_position = position_between(max_relative_position || START_POSITION, MAX_POSITION) end - def move_after(before) - self.relative_position = position_between(before.relative_position, before.next_relative_position) + # Indicates if there is an issue that should be shifted to free the place + def shift_after? + next_pos = next_relative_position + next_pos && (next_pos - relative_position) == 1 end - def move_to_end - self.relative_position = position_between(max_relative_position, MAX_POSITION) + # Indicates if there is an issue that should be shifted to free the place + def shift_before? + prev_pos = prev_relative_position + prev_pos && (relative_position - prev_pos) == 1 end private # This method takes two integer values (positions) and - # calculates some random position between them. The range is huge as - # the maximum integer value is 2147483647. Ideally, the calculated value would be - # exactly between those terminating values, but this will introduce possibility of a race condition - # so two or more issues can get the same value, we want to avoid that and we also want to avoid - # using a lock here. If we have two issues with distance more than one thousand, we are OK. - # Given the huge range of possible values that integer can fit we shoud never face a problem. + # calculates the position between them. The range is huge as + # the maximum integer value is 2147483647. We are incrementing position by IDEAL_DISTANCE * 2 every time + # when we have enough space. If distance is less then IDEAL_DISTANCE we are calculating an average number def position_between(pos_before, pos_after) pos_before ||= MIN_POSITION pos_after ||= MAX_POSITION pos_before, pos_after = [pos_before, pos_after].sort - rand(pos_before.next..pos_after.pred) + halfway = (pos_after + pos_before) / 2 + distance_to_halfway = pos_after - halfway + + if distance_to_halfway < IDEAL_DISTANCE + halfway + else + if pos_before == MIN_POSITION + pos_after - IDEAL_DISTANCE + elsif pos_after == MAX_POSITION + pos_before + IDEAL_DISTANCE + else + halfway + end + end end def save_positionable_neighbours diff --git a/db/post_migrate/20170309171644_reset_relative_position_for_issue.rb b/db/post_migrate/20170309171644_reset_relative_position_for_issue.rb new file mode 100644 index 00000000000..b61dd7cfc61 --- /dev/null +++ b/db/post_migrate/20170309171644_reset_relative_position_for_issue.rb @@ -0,0 +1,17 @@ +# See http://doc.gitlab.com/ce/development/migration_style_guide.html +# for more information on how to write migrations for GitLab. + +class ResetRelativePositionForIssue < ActiveRecord::Migration + include Gitlab::Database::MigrationHelpers + + DOWNTIME = false + + def up + update_column_in_batches(:issues, :relative_position, nil) do |table, query| + query.where(table[:relative_position].not_eq(nil)) + end + end + + def down + end +end diff --git a/spec/models/concerns/relative_positioning_spec.rb b/spec/models/concerns/relative_positioning_spec.rb index 69906382545..255b584a85e 100644 --- a/spec/models/concerns/relative_positioning_spec.rb +++ b/spec/models/concerns/relative_positioning_spec.rb @@ -12,12 +12,6 @@ describe Issue, 'RelativePositioning' do end end - describe '#min_relative_position' do - it 'returns maximum position' do - expect(issue.min_relative_position).to eq issue.relative_position - end - end - describe '#max_relative_position' do it 'returns maximum position' do expect(issue.max_relative_position).to eq issue1.relative_position @@ -29,8 +23,8 @@ describe Issue, 'RelativePositioning' do expect(issue1.prev_relative_position).to eq issue.relative_position end - it 'returns minimum position if there is no issue above' do - expect(issue.prev_relative_position).to eq RelativePositioning::MIN_POSITION + it 'returns nil if there is no issue above' do + expect(issue.prev_relative_position).to eq nil end end @@ -39,8 +33,8 @@ describe Issue, 'RelativePositioning' do expect(issue.next_relative_position).to eq issue1.relative_position end - it 'returns next position if there is no issue below' do - expect(issue1.next_relative_position).to eq RelativePositioning::MAX_POSITION + it 'returns nil if there is no issue below' do + expect(issue1.next_relative_position).to eq nil end end @@ -72,6 +66,34 @@ describe Issue, 'RelativePositioning' do end end + describe '#shift_after?' do + it 'returns true' do + issue.update(relative_position: issue1.relative_position - 1) + + expect(issue.shift_after?).to be_truthy + end + + it 'returns false' do + issue.update(relative_position: issue1.relative_position - 2) + + expect(issue.shift_after?).to be_falsey + end + end + + describe '#shift_before?' do + it 'returns true' do + issue.update(relative_position: issue1.relative_position + 1) + + expect(issue.shift_before?).to be_truthy + end + + it 'returns false' do + issue.update(relative_position: issue1.relative_position + 2) + + expect(issue.shift_before?).to be_falsey + end + end + describe '#move_between' do it 'positions issue between two other' do new_issue.move_between(issue, issue1) @@ -100,5 +122,83 @@ describe Issue, 'RelativePositioning' do expect(new_issue.relative_position).to be > issue.relative_position expect(issue.relative_position).to be < issue1.relative_position end + + it 'positions issues between other two if distance is 1' do + issue1.update relative_position: issue.relative_position + 1 + + new_issue.move_between(issue, issue1) + + expect(new_issue.relative_position).to be > issue.relative_position + expect(issue.relative_position).to be < issue1.relative_position + end + + it 'positions issue in the middle of other two if distance is big enough' do + issue.update relative_position: 6000 + issue1.update relative_position: 10000 + + new_issue.move_between(issue, issue1) + + expect(new_issue.relative_position).to eq(8000) + end + + it 'positions issue closer to the middle if we are at the very top' do + issue1.update relative_position: 6000 + + new_issue.move_between(nil, issue1) + + expect(new_issue.relative_position).to eq(6000 - RelativePositioning::IDEAL_DISTANCE) + end + + it 'positions issue closer to the middle if we are at the very bottom' do + issue.update relative_position: 6000 + issue1.update relative_position: nil + + new_issue.move_between(issue, nil) + + expect(new_issue.relative_position).to eq(6000 + RelativePositioning::IDEAL_DISTANCE) + end + + it 'positions issue in the middle of other two if distance is not big enough' do + issue.update relative_position: 100 + issue1.update relative_position: 400 + + new_issue.move_between(issue, issue1) + + expect(new_issue.relative_position).to eq(250) + end + + it 'positions issue in the middle of other two is there is no place' do + issue.update relative_position: 100 + issue1.update relative_position: 101 + + new_issue.move_between(issue, issue1) + + expect(new_issue.relative_position).to be_between(issue.relative_position, issue1.relative_position) + end + + it 'uses rebalancing if there is no place' do + issue.update relative_position: 100 + issue1.update relative_position: 101 + issue2 = create(:issue, relative_position: 102, project: project) + new_issue.update relative_position: 103 + + new_issue.move_between(issue1, issue2) + new_issue.save! + + expect(new_issue.relative_position).to be_between(issue1.relative_position, issue2.relative_position) + expect(issue.reload.relative_position).not_to eq(100) + end + + it 'positions issue right if we pass none-sequential parameters' do + issue.update relative_position: 99 + issue1.update relative_position: 101 + issue2 = create(:issue, relative_position: 102, project: project) + new_issue.update relative_position: 103 + + new_issue.move_between(issue, issue2) + new_issue.save! + + expect(new_issue.relative_position).to be(100) + end end end |