1# frozen_string_literal: true
2
3# This module makes it possible to handle items as a list, where the order of items can be easily altered
4# Requirements:
5#
6# The model must have the following named columns:
7#  - id: integer
8#  - relative_position: integer
9#
10# The model must support a concept of siblings via a child->parent relationship,
11# to enable rebalancing and `GROUP BY` in queries.
12# - example: project -> issues, project is the parent relation (issues table has a parent_id column)
13#
14# Two class methods must be defined when including this concern:
15#
16#     include RelativePositioning
17#
18#     # base query used for the position calculation
19#     def self.relative_positioning_query_base(issue)
20#       where(deleted: false)
21#     end
22#
23#     # column that should be used in GROUP BY
24#     def self.relative_positioning_parent_column
25#       :project_id
26#     end
27#
28module RelativePositioning
29  extend ActiveSupport::Concern
30  include ::Gitlab::RelativePositioning
31
32  class_methods do
33    def move_nulls_to_end(objects)
34      move_nulls(objects, at_end: true)
35    end
36
37    def move_nulls_to_start(objects)
38      move_nulls(objects, at_end: false)
39    end
40
41    private
42
43    # @api private
44    def gap_size(context, gaps:, at_end:, starting_from:)
45      total_width = IDEAL_DISTANCE * gaps
46      size = if at_end && starting_from + total_width >= MAX_POSITION
47               (MAX_POSITION - starting_from) / gaps
48             elsif !at_end && starting_from - total_width <= MIN_POSITION
49               (starting_from - MIN_POSITION) / gaps
50             else
51               IDEAL_DISTANCE
52             end
53
54      return [size, starting_from] if size >= MIN_GAP
55
56      terminus = context.at_position(starting_from)
57
58      if at_end
59        terminus.shift_left
60        max_relative_position = terminus.relative_position
61        [[(MAX_POSITION - max_relative_position) / gaps, IDEAL_DISTANCE].min, max_relative_position]
62      else
63        terminus.shift_right
64        min_relative_position = terminus.relative_position
65        [[(min_relative_position - MIN_POSITION) / gaps, IDEAL_DISTANCE].min, min_relative_position]
66      end
67    end
68
69    # @api private
70    # @param [Array<RelativePositioning>] objects The objects to give positions to. The relative
71    #                                             order will be preserved (i.e. when this method returns,
72    #                                             objects.first.relative_position < objects.last.relative_position)
73    # @param [Boolean] at_end: The placement.
74    #                          If `true`, then all objects with `null` positions are placed _after_
75    #                          all siblings with positions. If `false`, all objects with `null`
76    #                          positions are placed _before_ all siblings with positions.
77    # @returns [Number] The number of moved records.
78    def move_nulls(objects, at_end:)
79      objects = objects.reject(&:relative_position)
80      return 0 if objects.empty?
81
82      objects.first.check_repositioning_allowed!
83
84      number_of_gaps = objects.size # 1 to the nearest neighbour, and one between each
85      representative = RelativePositioning.mover.context(objects.first)
86
87      position = if at_end
88                   representative.max_relative_position
89                 else
90                   representative.min_relative_position
91                 end
92
93      position ||= START_POSITION # If there are no positioned siblings, start from START_POSITION
94
95      gap = 0
96      attempts = 10 # consolidate up to 10 gaps to find enough space
97      while gap < 1 && attempts > 0
98        gap, position = gap_size(representative, gaps: number_of_gaps, at_end: at_end, starting_from: position)
99        attempts -= 1
100      end
101
102      # Allow placing items next to each other, if we have to.
103      gap = 1 if gap < MIN_GAP
104      delta = at_end ? gap : -gap
105      indexed = (at_end ? objects : objects.reverse).each_with_index
106
107      lower_bound, upper_bound = at_end ? [position, MAX_POSITION] : [MIN_POSITION, position]
108
109      representative.model_class.transaction do
110        indexed.each_slice(100) do |batch|
111          mapping = batch.to_h.transform_values! do |i|
112            desired_pos = position + delta * (i + 1)
113            { relative_position: desired_pos.clamp(lower_bound, upper_bound) }
114          end
115
116          ::Gitlab::Database::BulkUpdate.execute([:relative_position], mapping, &:model_class)
117        end
118      end
119
120      objects.size
121    end
122  end
123
124  def self.mover
125    ::Gitlab::RelativePositioning::Mover.new(START_POSITION, (MIN_POSITION..MAX_POSITION))
126  end
127
128  # To be overriden on child classes whenever
129  # blocking position updates is necessary.
130  def check_repositioning_allowed!
131    nil
132  end
133
134  def move_between(before, after)
135    before, after = [before, after].sort_by(&:relative_position) if before && after
136
137    RelativePositioning.mover.move(self, before, after)
138  rescue NoSpaceLeft => e
139    could_not_move(e)
140    raise e
141  end
142
143  def move_after(before = self)
144    RelativePositioning.mover.move(self, before, nil)
145  rescue NoSpaceLeft => e
146    could_not_move(e)
147    raise e
148  end
149
150  def move_before(after = self)
151    RelativePositioning.mover.move(self, nil, after)
152  rescue NoSpaceLeft => e
153    could_not_move(e)
154    raise e
155  end
156
157  def move_to_end
158    RelativePositioning.mover.move_to_end(self)
159  rescue NoSpaceLeft => e
160    could_not_move(e)
161    self.relative_position = MAX_POSITION
162  end
163
164  def move_to_start
165    RelativePositioning.mover.move_to_start(self)
166  rescue NoSpaceLeft => e
167    could_not_move(e)
168    self.relative_position = MIN_POSITION
169  end
170
171  def next_object_by_relative_position(ignoring: nil, order: :asc)
172    relation = relative_positioning_scoped_items(ignoring: ignoring).reorder(relative_position: order)
173
174    relation = if order == :asc
175                 relation.where(self.class.arel_table[:relative_position].gt(relative_position))
176               else
177                 relation.where(self.class.arel_table[:relative_position].lt(relative_position))
178               end
179
180    relation.first
181  end
182
183  def relative_positioning_scoped_items(ignoring: nil)
184    relation = self.class.relative_positioning_query_base(self)
185    relation = exclude_self(relation, excluded: ignoring) if ignoring.present?
186    relation
187  end
188
189  # This method is used during rebalancing - override it to customise the update
190  # logic:
191  def update_relative_siblings(relation, range, delta)
192    relation
193      .where(relative_position: range)
194      .update_all("relative_position = relative_position + #{delta}")
195  end
196
197  # This method is used to exclude the current self (or another object)
198  # from a relation. Customize this if `id <> :id` is not sufficient
199  def exclude_self(relation, excluded: self)
200    relation.id_not_in(excluded.id)
201  end
202
203  # Override if you want to be notified of failures to move
204  def could_not_move(exception)
205  end
206
207  # Override if the implementing class is not a simple application record, for
208  # example if the record is loaded from a union.
209  def reset_relative_position
210    reset.relative_position
211  end
212
213  # Override if the model class needs a more complicated computation (e.g. the
214  # object is a member of a union).
215  def model_class
216    self.class
217  end
218end
219