diff options
author | GitLab Bot <gitlab-bot@gitlab.com> | 2020-09-16 21:09:47 +0300 |
---|---|---|
committer | GitLab Bot <gitlab-bot@gitlab.com> | 2020-09-16 21:09:47 +0300 |
commit | bf1600d157465f9408aace91073954fd5790c054 (patch) | |
tree | f317bb99330769c4eb37621c860af014810e554b /lib/gitlab/relative_positioning | |
parent | 6de7d2c195a8a7fa5702cafa4365f7a9fcac37cd (diff) |
Add latest changes from gitlab-org/gitlab@master
Diffstat (limited to 'lib/gitlab/relative_positioning')
-rw-r--r-- | lib/gitlab/relative_positioning/gap.rb | 21 | ||||
-rw-r--r-- | lib/gitlab/relative_positioning/item_context.rb | 259 | ||||
-rw-r--r-- | lib/gitlab/relative_positioning/mover.rb | 155 | ||||
-rw-r--r-- | lib/gitlab/relative_positioning/range.rb | 83 |
4 files changed, 518 insertions, 0 deletions
diff --git a/lib/gitlab/relative_positioning/gap.rb b/lib/gitlab/relative_positioning/gap.rb new file mode 100644 index 00000000000..ab894141a60 --- /dev/null +++ b/lib/gitlab/relative_positioning/gap.rb @@ -0,0 +1,21 @@ +# frozen_string_literal: true +# +module Gitlab + module RelativePositioning + class Gap + attr_reader :start_pos, :end_pos + + def initialize(start_pos, end_pos) + @start_pos, @end_pos = start_pos, end_pos + end + + def ==(other) + other.is_a?(self.class) && other.start_pos == start_pos && other.end_pos == end_pos + end + + def delta + ((start_pos - end_pos) / 2.0).abs.ceil.clamp(0, RelativePositioning::IDEAL_DISTANCE) + end + end + end +end diff --git a/lib/gitlab/relative_positioning/item_context.rb b/lib/gitlab/relative_positioning/item_context.rb new file mode 100644 index 00000000000..cd03a347355 --- /dev/null +++ b/lib/gitlab/relative_positioning/item_context.rb @@ -0,0 +1,259 @@ +# frozen_string_literal: true + +module Gitlab + module RelativePositioning + # This class is API private - it should not be explicitly instantiated + # outside of tests + # rubocop: disable CodeReuse/ActiveRecord + class ItemContext + include Gitlab::Utils::StrongMemoize + + attr_reader :object, :model_class, :range + attr_accessor :ignoring + + def initialize(object, range, ignoring: nil) + @object = object + @range = range + @model_class = object.class + @ignoring = ignoring + end + + def ==(other) + other.is_a?(self.class) && other.object == object && other.range == range && other.ignoring == ignoring + end + + def positioned? + relative_position.present? + end + + def min_relative_position + strong_memoize(:min_relative_position) { calculate_relative_position('MIN') } + end + + def max_relative_position + strong_memoize(:max_relative_position) { calculate_relative_position('MAX') } + end + + def prev_relative_position + calculate_relative_position('MAX') { |r| nextify(r, false) } if object.relative_position + end + + def next_relative_position + calculate_relative_position('MIN') { |r| nextify(r) } if object.relative_position + end + + def nextify(relation, gt = true) + if gt + relation.where("relative_position > ?", relative_position) + else + relation.where("relative_position < ?", relative_position) + end + end + + def relative_siblings(relation = scoped_items) + object.exclude_self(relation) + end + + # Handles the possibility that the position is already occupied by a sibling + def place_at_position(position, lhs) + current_occupant = relative_siblings.find_by(relative_position: position) + + if current_occupant.present? + Mover.new(position, range).move(object, lhs.object, current_occupant) + else + object.relative_position = position + end + end + + def lhs_neighbour + scoped_items + .where('relative_position < ?', relative_position) + .reorder(relative_position: :desc) + .first + .then { |x| neighbour(x) } + end + + def rhs_neighbour + scoped_items + .where('relative_position > ?', relative_position) + .reorder(relative_position: :asc) + .first + .then { |x| neighbour(x) } + end + + def neighbour(item) + return unless item.present? + + self.class.new(item, range, ignoring: ignoring) + end + + def scoped_items + r = model_class.relative_positioning_query_base(object) + r = object.exclude_self(r, excluded: ignoring) if ignoring.present? + r + end + + def calculate_relative_position(calculation) + # When calculating across projects, this is much more efficient than + # MAX(relative_position) without the GROUP BY, due to index usage: + # https://gitlab.com/gitlab-org/gitlab-foss/issues/54276#note_119340977 + relation = scoped_items + .order(Gitlab::Database.nulls_last_order('position', 'DESC')) + .group(grouping_column) + .limit(1) + + relation = yield relation if block_given? + + relation + .pluck(grouping_column, Arel.sql("#{calculation}(relative_position) AS position")) + .first&.last + end + + def grouping_column + model_class.relative_positioning_parent_column + end + + def max_sibling + sib = relative_siblings + .order(Gitlab::Database.nulls_last_order('relative_position', 'DESC')) + .first + + neighbour(sib) + end + + def min_sibling + sib = relative_siblings + .order(Gitlab::Database.nulls_last_order('relative_position', 'ASC')) + .first + + neighbour(sib) + end + + def shift_left + move_sequence_before(true) + object.reset + end + + def shift_right + move_sequence_after(true) + object.reset + end + + def create_space_left + find_next_gap_before.tap { |gap| move_sequence_before(false, next_gap: gap) } + end + + def create_space_right + find_next_gap_after.tap { |gap| move_sequence_after(false, next_gap: gap) } + end + + def find_next_gap_before + items_with_next_pos = scoped_items + .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position DESC) AS next_pos') + .where('relative_position <= ?', relative_position) + .order(relative_position: :desc) + + find_next_gap(items_with_next_pos, range.first) + end + + def find_next_gap_after + items_with_next_pos = scoped_items + .select('relative_position AS pos, LEAD(relative_position) OVER (ORDER BY relative_position ASC) AS next_pos') + .where('relative_position >= ?', relative_position) + .order(:relative_position) + + find_next_gap(items_with_next_pos, range.last) + end + + def find_next_gap(items_with_next_pos, default_end) + gap = model_class + .from(items_with_next_pos, :items) + .where('next_pos IS NULL OR ABS(pos::bigint - next_pos::bigint) >= ?', MIN_GAP) + .limit(1) + .pluck(:pos, :next_pos) + .first + + return if gap.nil? || gap.first == default_end + + Gap.new(gap.first, gap.second || default_end) + end + + def relative_position + object.relative_position + end + + private + + # Moves the sequence before the current item to the middle of the next gap + # For example, we have + # + # 5 . . . . . 11 12 13 14 [15] 16 . 17 + # ----------- + # + # This moves the sequence [11 12 13 14] to [8 9 10 11], so we have: + # + # 5 . . 8 9 10 11 . . . [15] 16 . 17 + # --------- + # + # Creating a gap to the left of the current item. We can understand this as + # dividing the 5 spaces between 5 and 11 into two smaller gaps of 2 and 3. + # + # If `include_self` is true, the current item will also be moved, creating a + # gap to the right of the current item: + # + # 5 . . 8 9 10 11 [14] . . . 16 . 17 + # -------------- + # + # As an optimization, the gap can be precalculated and passed to this method. + # + # @api private + # @raises NoSpaceLeft if the sequence cannot be moved + def move_sequence_before(include_self = false, next_gap: find_next_gap_before) + raise NoSpaceLeft unless next_gap.present? + + delta = next_gap.delta + + move_sequence(next_gap.start_pos, relative_position, -delta, include_self) + end + + # Moves the sequence after the current item to the middle of the next gap + # For example, we have: + # + # 8 . 10 [11] 12 13 14 15 . . . . . 21 + # ----------- + # + # This moves the sequence [12 13 14 15] to [15 16 17 18], so we have: + # + # 8 . 10 [11] . . . 15 16 17 18 . . 21 + # ----------- + # + # Creating a gap to the right of the current item. We can understand this as + # dividing the 5 spaces between 15 and 21 into two smaller gaps of 3 and 2. + # + # If `include_self` is true, the current item will also be moved, creating a + # gap to the left of the current item: + # + # 8 . 10 . . . [14] 15 16 17 18 . . 21 + # ---------------- + # + # As an optimization, the gap can be precalculated and passed to this method. + # + # @api private + # @raises NoSpaceLeft if the sequence cannot be moved + def move_sequence_after(include_self = false, next_gap: find_next_gap_after) + raise NoSpaceLeft unless next_gap.present? + + delta = next_gap.delta + + move_sequence(relative_position, next_gap.start_pos, delta, include_self) + end + + def move_sequence(start_pos, end_pos, delta, include_self = false) + relation = include_self ? scoped_items : relative_siblings + + object.update_relative_siblings(relation, (start_pos..end_pos), delta) + end + end + # rubocop: enable CodeReuse/ActiveRecord + end +end diff --git a/lib/gitlab/relative_positioning/mover.rb b/lib/gitlab/relative_positioning/mover.rb new file mode 100644 index 00000000000..9d891bfbe3b --- /dev/null +++ b/lib/gitlab/relative_positioning/mover.rb @@ -0,0 +1,155 @@ +# frozen_string_literal: true + +module Gitlab + module RelativePositioning + class Mover + attr_reader :range, :start_position + + def initialize(start, range) + @range = range + @start_position = start + end + + def move_to_end(object) + focus = context(object, ignoring: object) + max_pos = focus.max_relative_position + + move_to_range_end(focus, max_pos) + end + + def move_to_start(object) + focus = context(object, ignoring: object) + min_pos = focus.min_relative_position + + move_to_range_start(focus, min_pos) + end + + def move(object, first, last) + raise ArgumentError, 'object is required' unless object + + lhs = context(first, ignoring: object) + rhs = context(last, ignoring: object) + focus = context(object) + range = RelativePositioning.range(lhs, rhs) + + if range.cover?(focus) + # Moving a object already within a range is a no-op + elsif range.open_on_left? + move_to_range_start(focus, range.rhs.relative_position) + elsif range.open_on_right? + move_to_range_end(focus, range.lhs.relative_position) + else + pos_left, pos_right = create_space_between(range) + desired_position = position_between(pos_left, pos_right) + focus.place_at_position(desired_position, range.lhs) + end + end + + def context(object, ignoring: nil) + return unless object + + ItemContext.new(object, range, ignoring: ignoring) + end + + private + + def gap_too_small?(pos_a, pos_b) + return false unless pos_a && pos_b + + (pos_a - pos_b).abs < MIN_GAP + end + + def move_to_range_end(context, max_pos) + range_end = range.last + 1 + + new_pos = if max_pos.nil? + start_position + elsif gap_too_small?(max_pos, range_end) + max = context.max_sibling + max.ignoring = context.object + max.shift_left + position_between(max.relative_position, range_end) + else + position_between(max_pos, range_end) + end + + context.object.relative_position = new_pos + end + + def move_to_range_start(context, min_pos) + range_end = range.first - 1 + + new_pos = if min_pos.nil? + start_position + elsif gap_too_small?(min_pos, range_end) + sib = context.min_sibling + sib.ignoring = context.object + sib.shift_right + position_between(sib.relative_position, range_end) + else + position_between(min_pos, range_end) + end + + context.object.relative_position = new_pos + end + + def create_space_between(range) + pos_left = range.lhs&.relative_position + pos_right = range.rhs&.relative_position + + return [pos_left, pos_right] unless gap_too_small?(pos_left, pos_right) + + gap = range.rhs.create_space_left + [pos_left - gap.delta, pos_right] + rescue NoSpaceLeft + gap = range.lhs.create_space_right + [pos_left, pos_right + gap.delta] + end + + # This method takes two integer values (positions) and + # calculates the position between them. The range is huge as + # the maximum integer value is 2147483647. + # + # We avoid open ranges by clamping the range to [MIN_POSITION, MAX_POSITION]. + # + # Then we handle one of three cases: + # - If the gap is too small, we raise NoSpaceLeft + # - If the gap is larger than MAX_GAP, we place the new position at most + # IDEAL_DISTANCE from the edge of the gap. + # - otherwise we place the new position at the midpoint. + # + # The new position will always satisfy: pos_before <= midpoint <= pos_after + # + # As a precondition, the gap between pos_before and pos_after MUST be >= 2. + # If the gap is too small, NoSpaceLeft is raised. + # + # @raises NoSpaceLeft + def position_between(pos_before, pos_after) + pos_before ||= range.first + pos_after ||= range.last + + pos_before, pos_after = [pos_before, pos_after].sort + + gap_width = pos_after - pos_before + + if gap_too_small?(pos_before, pos_after) + raise NoSpaceLeft + elsif gap_width > MAX_GAP + if pos_before <= range.first + pos_after - IDEAL_DISTANCE + elsif pos_after >= range.last + pos_before + IDEAL_DISTANCE + else + midpoint(pos_before, pos_after) + end + else + midpoint(pos_before, pos_after) + end + end + + def midpoint(lower_bound, upper_bound) + ((lower_bound + upper_bound) / 2.0).ceil.clamp(lower_bound, upper_bound - 1) + end + end + end +end diff --git a/lib/gitlab/relative_positioning/range.rb b/lib/gitlab/relative_positioning/range.rb new file mode 100644 index 00000000000..174d5ef4b35 --- /dev/null +++ b/lib/gitlab/relative_positioning/range.rb @@ -0,0 +1,83 @@ +# frozen_string_literal: true + +module Gitlab + module RelativePositioning + IllegalRange = Class.new(ArgumentError) + + class Range + attr_reader :lhs, :rhs + + def open_on_left? + lhs.nil? + end + + def open_on_right? + rhs.nil? + end + + def cover?(item_context) + return false unless item_context + return false unless item_context.positioned? + return true if item_context.object == lhs&.object + return true if item_context.object == rhs&.object + + pos = item_context.relative_position + + return lhs.relative_position < pos if open_on_right? + return pos < rhs.relative_position if open_on_left? + + lhs.relative_position < pos && pos < rhs.relative_position + end + + def ==(other) + other.is_a?(RelativePositioning::Range) && lhs == other.lhs && rhs == other.rhs + end + end + + def self.range(lhs, rhs) + if lhs && rhs + ClosedRange.new(lhs, rhs) + elsif lhs + StartingFrom.new(lhs) + elsif rhs + EndingAt.new(rhs) + else + raise IllegalRange, 'One of rhs or lhs must be provided' unless lhs && rhs + end + end + + class ClosedRange < RelativePositioning::Range + def initialize(lhs, rhs) + @lhs, @rhs = lhs, rhs + raise IllegalRange, 'Either lhs or rhs is missing' unless lhs && rhs + raise IllegalRange, 'lhs and rhs cannot be the same object' if lhs == rhs + end + end + + class StartingFrom < RelativePositioning::Range + include Gitlab::Utils::StrongMemoize + + def initialize(lhs) + @lhs = lhs + raise IllegalRange, 'lhs is required' unless lhs + end + + def rhs + strong_memoize(:rhs) { lhs.rhs_neighbour } + end + end + + class EndingAt < RelativePositioning::Range + include Gitlab::Utils::StrongMemoize + + def initialize(rhs) + @rhs = rhs + raise IllegalRange, 'rhs is required' unless rhs + end + + def lhs + strong_memoize(:lhs) { rhs.lhs_neighbour } + end + end + end +end |