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