summaryrefslogtreecommitdiff
path: root/app/models/concerns/relative_positioning.rb
blob: c32e499c32965590e3ff92d42c8714af52aa159d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
# frozen_string_literal: true

# This module makes it possible to handle items as a list, where the order of items can be easily altered
# Requirements:
#
# The model must have the following named columns:
#  - id: integer
#  - relative_position: integer
#
# The model must support a concept of siblings via a child->parent relationship,
# to enable rebalancing and `GROUP BY` in queries.
# - example: project -> issues, project is the parent relation (issues table has a parent_id column)
#
# Two class methods must be defined when including this concern:
#
#     include RelativePositioning
#
#     # base query used for the position calculation
#     def self.relative_positioning_query_base(issue)
#       where(deleted: false)
#     end
#
#     # column that should be used in GROUP BY
#     def self.relative_positioning_parent_column
#       :project_id
#     end
#
module RelativePositioning
  extend ActiveSupport::Concern
  include ::Gitlab::RelativePositioning

  class_methods do
    def move_nulls_to_end(objects)
      move_nulls(objects, at_end: true)
    end

    def move_nulls_to_start(objects)
      move_nulls(objects, at_end: false)
    end

    private

    # @api private
    def gap_size(context, gaps:, at_end:, starting_from:)
      total_width = IDEAL_DISTANCE * gaps
      size = if at_end && starting_from + total_width >= MAX_POSITION
               (MAX_POSITION - starting_from) / gaps
             elsif !at_end && starting_from - total_width <= MIN_POSITION
               (starting_from - MIN_POSITION) / gaps
             else
               IDEAL_DISTANCE
             end

      return [size, starting_from] if size >= MIN_GAP

      terminus = context.at_position(starting_from)

      if at_end
        terminus.shift_left
        max_relative_position = terminus.relative_position
        [[(MAX_POSITION - max_relative_position) / gaps, IDEAL_DISTANCE].min, max_relative_position]
      else
        terminus.shift_right
        min_relative_position = terminus.relative_position
        [[(min_relative_position - MIN_POSITION) / gaps, IDEAL_DISTANCE].min, min_relative_position]
      end
    end

    # @api private
    # @param [Array<RelativePositioning>] objects The objects to give positions to. The relative
    #                                             order will be preserved (i.e. when this method returns,
    #                                             objects.first.relative_position < objects.last.relative_position)
    # @param [Boolean] at_end: The placement.
    #                          If `true`, then all objects with `null` positions are placed _after_
    #                          all siblings with positions. If `false`, all objects with `null`
    #                          positions are placed _before_ all siblings with positions.
    # @returns [Number] The number of moved records.
    def move_nulls(objects, at_end:)
      objects = objects.reject(&:relative_position)
      return 0 if objects.empty?

      objects.first.check_repositioning_allowed!

      number_of_gaps = objects.size # 1 to the nearest neighbour, and one between each
      representative = RelativePositioning.mover.context(objects.first)

      position = if at_end
                   representative.max_relative_position
                 else
                   representative.min_relative_position
                 end

      position ||= START_POSITION # If there are no positioned siblings, start from START_POSITION

      gap = 0
      attempts = 10 # consolidate up to 10 gaps to find enough space
      while gap < 1 && attempts > 0
        gap, position = gap_size(representative, gaps: number_of_gaps, at_end: at_end, starting_from: position)
        attempts -= 1
      end

      # Allow placing items next to each other, if we have to.
      gap = 1 if gap < MIN_GAP
      delta = at_end ? gap : -gap
      indexed = (at_end ? objects : objects.reverse).each_with_index

      lower_bound, upper_bound = at_end ? [position, MAX_POSITION] : [MIN_POSITION, position]

      representative.model_class.transaction do
        indexed.each_slice(100) do |batch|
          mapping = batch.to_h.transform_values! do |i|
            desired_pos = position + delta * (i + 1)
            { relative_position: desired_pos.clamp(lower_bound, upper_bound) }
          end

          ::Gitlab::Database::BulkUpdate.execute([:relative_position], mapping, &:model_class)
        end
      end

      objects.size
    end
  end

  def self.mover
    ::Gitlab::RelativePositioning::Mover.new(START_POSITION, (MIN_POSITION..MAX_POSITION))
  end

  # To be overriden on child classes whenever
  # blocking position updates is necessary.
  def check_repositioning_allowed!
    nil
  end

  def move_between(before, after)
    before, after = [before, after].sort_by(&:relative_position) if before && after

    RelativePositioning.mover.move(self, before, after)
  rescue NoSpaceLeft => e
    could_not_move(e)
    raise e
  end

  def move_after(before = self)
    RelativePositioning.mover.move(self, before, nil)
  rescue NoSpaceLeft => e
    could_not_move(e)
    raise e
  end

  def move_before(after = self)
    RelativePositioning.mover.move(self, nil, after)
  rescue NoSpaceLeft => e
    could_not_move(e)
    raise e
  end

  def move_to_end
    RelativePositioning.mover.move_to_end(self)
  rescue NoSpaceLeft => e
    could_not_move(e)
    self.relative_position = MAX_POSITION
  end

  def move_to_start
    RelativePositioning.mover.move_to_start(self)
  rescue NoSpaceLeft => e
    could_not_move(e)
    self.relative_position = MIN_POSITION
  end

  # This method is used during rebalancing - override it to customise the update
  # logic:
  def update_relative_siblings(relation, range, delta)
    relation
      .where(relative_position: range)
      .update_all("relative_position = relative_position + #{delta}")
  end

  # This method is used to exclude the current self (or another object)
  # from a relation. Customize this if `id <> :id` is not sufficient
  def exclude_self(relation, excluded: self)
    relation.id_not_in(excluded.id)
  end

  # Override if you want to be notified of failures to move
  def could_not_move(exception)
  end

  # Override if the implementing class is not a simple application record, for
  # example if the record is loaded from a union.
  def reset_relative_position
    reset.relative_position
  end

  # Override if the model class needs a more complicated computation (e.g. the
  # object is a member of a union).
  def model_class
    self.class
  end
end