Add latest changes from gitlab-org/gitlab@13-10-stable-eev13.10.0-rc40

2 files changed, 472 insertions, 0 deletions

diff --git a/lib/gitlab/pagination/keyset/column_order_definition.rb b/lib/gitlab/pagination/keyset/column_order_definition.rb
new file mode 100644
index 00000000000..0c8ec02a56b
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/column_order_definition.rb
@@ -0,0 +1,224 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      # This class stores information for one column (or SQL expression) which can be used in an
+      # ORDER BY SQL clasue.
+      # The goal of this class is to encapsulate all the metadata in one place which are needed to
+      # make keyset pagination work in a generalized way.
+      #
+      # == Arguments
+      #
+      # **order expression** (Arel::Nodes::Node | String)
+      #
+      # The actual SQL expression for the ORDER BY clause.
+      #
+      # Examples:
+      #   # Arel column order definition
+      #   Project.arel_table[:id].asc # ORDER BY projects.id ASC
+      #
+      #   # Arel expression, calculated order definition
+      #   Arel::Nodes::NamedFunction.new("COALESCE", [Project.arel_table[:issue_count].asc, 0]).asc # ORDER BY COALESCE(projects.issue_count, 0)
+      #
+      #   # Another Arel expression
+      #   Arel::Nodes::Multiplication(Issue.arel_table[:weight], Issue.arel_table[:time_spent]).desc
+      #
+      #   # Raw string order definition
+      #   'issues.type DESC NULLS LAST'
+      #
+      # **column_expression** (Arel::Nodes::Node | String)
+      #
+      # Expression for the database column or an expression. This value will be used with logical operations (>, <, =, !=)
+      # when building the database query for the next page.
+      #
+      # Examples:
+      #   # Arel column reference
+      #   Issue.arel_table[:title]
+      #
+      #   # Calculated value
+      #   Arel::Nodes::Multiplication(Issue.arel_table[:weight], Issue.arel_table[:time_spent])
+      #
+      # **attribute_name** (String | Symbol)
+      #
+      # An attribute on the loaded ActiveRecord model where the value can be obtained.
+      #
+      # Examples:
+      #   # Simple attribute definition
+      #   attribute_name = :title
+      #
+      #   # Later on this attribute will be used like this:
+      #   my_record = Issue.find(x)
+      #   value = my_record[attribute_name] # reads data from the title column
+      #
+      #   # Calculated value based on an Arel or raw SQL expression
+      #
+      #   attribute_name = :lowercase_title
+      #
+      #   # `lowercase_title` is not is not a table column therefore we need to make sure it's available in the `SELECT` clause
+      #
+      #   my_record = Issue.select(:id, 'LOWER(title) as lowercase_title').last
+      #   value = my_record[:lowercase_title]
+      #
+      # **distinct**
+      #
+      # Boolean value.
+      #
+      # Tells us whether the database column contains only distinct values. If the column is covered by
+      # a unique index then set to true.
+      #
+      # **nullable** (:not_nullable | :nulls_last | :nulls_first)
+      #
+      # Tells us whether the database column is nullable or not. This information can be
+      # obtained from the DB schema.
+      #
+      # If the column is not nullable, set this attribute to :not_nullable.
+      #
+      # If the column is nullable, then additional information is needed. Based on the ordering, the null values
+      # will show up at the top or at the bottom of the resultset.
+      #
+      # Examples:
+      #     # Nulls are showing up at the top (for example: ORDER BY column ASC):
+      #     nullable = :nulls_first
+      #
+      #     # Nulls are showing up at the bottom (for example: ORDER BY column DESC):
+      #     nullable = :nulls_last
+      #
+      # **order_direction**
+      #
+      # :asc or :desc
+      #
+      # Note: this is an optional attribute, the value will be inferred from the order_expression.
+      # Sometimes it's not possible to infer the order automatically. In this case an exception will be
+      # raised (when the query is executed). If the reverse order cannot be computed, it must be provided explicitly.
+      #
+      # **reversed_order_expression**
+      #
+      # The reversed version of the order_expression.
+      #
+      # A ColumnOrderDefinition object is able to reverse itself which is used when paginating backwards.
+      # When a complex order_expression is provided (raw string), then reversing the order automatically
+      # is not possible. In this case an exception will be raised.
+      #
+      # Example:
+      #
+      #   order_expression = Project.arel_table[:id].asc
+      #   reversed_order_expression = Project.arel_table[:id].desc
+      #
+      # **add_to_projections**
+      #
+      # Set to true if the column is not part of the queried table. (Not part of SELECT *)
+      #
+      #  Example:
+      #
+      #  - When the order is a calculated expression or the column is in another table (JOIN-ed)
+      #
+      #  If the add_to_projections is true, the query builder will automatically add the column to the SELECT values
+      class ColumnOrderDefinition
+        REVERSED_ORDER_DIRECTIONS = { asc: :desc, desc: :asc }.freeze
+        REVERSED_NULL_POSITIONS = { nulls_first: :nulls_last, nulls_last: :nulls_first }.freeze
+        AREL_ORDER_CLASSES = { Arel::Nodes::Ascending => :asc, Arel::Nodes::Descending => :desc }.freeze
+        ALLOWED_NULLABLE_VALUES = [:not_nullable, :nulls_first, :nulls_last].freeze
+
+        attr_reader :attribute_name, :column_expression, :order_expression, :add_to_projections
+
+        def initialize(attribute_name:, order_expression:, column_expression: nil, reversed_order_expression: nil, nullable: :not_nullable, distinct: true, order_direction: nil, add_to_projections: false)
+          @attribute_name = attribute_name
+          @order_expression = order_expression
+          @column_expression = column_expression || calculate_column_expression(order_expression)
+          @distinct = distinct
+          @reversed_order_expression = reversed_order_expression || calculate_reversed_order(order_expression)
+          @nullable = parse_nullable(nullable, distinct)
+          @order_direction = parse_order_direction(order_expression, order_direction)
+          @add_to_projections = add_to_projections
+        end
+
+        def reverse
+          self.class.new(
+            attribute_name: attribute_name,
+            column_expression: column_expression,
+            order_expression: reversed_order_expression,
+            reversed_order_expression: order_expression,
+            nullable: not_nullable? ? :not_nullable : REVERSED_NULL_POSITIONS[nullable],
+            distinct: distinct,
+            order_direction: REVERSED_ORDER_DIRECTIONS[order_direction]
+          )
+        end
+
+        def ascending_order?
+          order_direction == :asc
+        end
+
+        def descending_order?
+          order_direction == :desc
+        end
+
+        def nulls_first?
+          nullable == :nulls_first
+        end
+
+        def nulls_last?
+          nullable == :nulls_last
+        end
+
+        def not_nullable?
+          nullable == :not_nullable
+        end
+
+        def nullable?
+          !not_nullable?
+        end
+
+        def distinct?
+          distinct
+        end
+
+        private
+
+        attr_reader :reversed_order_expression, :nullable, :distinct, :order_direction
+
+        def calculate_reversed_order(order_expression)
+          unless AREL_ORDER_CLASSES.has_key?(order_expression.class) # Arel can reverse simple orders
+            raise "Couldn't determine reversed order for `#{order_expression}`, please provide the `reversed_order_expression` parameter."
+          end
+
+          order_expression.reverse
+        end
+
+        def calculate_column_expression(order_expression)
+          if order_expression.respond_to?(:expr)
+            order_expression.expr
+          else
+            raise("Couldn't calculate the column expression. Please pass an ARel node as the order_expression, not a string.")
+          end
+        end
+
+        def parse_order_direction(order_expression, order_direction)
+          transformed_order_direction = if order_direction.nil? && AREL_ORDER_CLASSES[order_expression.class]
+                                          AREL_ORDER_CLASSES[order_expression.class]
+                                        elsif order_direction.present?
+                                          order_direction.to_s.downcase.to_sym
+                                        end
+
+          unless REVERSED_ORDER_DIRECTIONS.has_key?(transformed_order_direction)
+            raise "Invalid or missing `order_direction` (value: #{order_direction}) was given, the allowed values are: :asc or :desc"
+          end
+
+          transformed_order_direction
+        end
+
+        def parse_nullable(nullable, distinct)
+          if ALLOWED_NULLABLE_VALUES.exclude?(nullable)
+            raise "Invalid `nullable` is given (value: #{nullable}), the allowed values are: #{ALLOWED_NULLABLE_VALUES.join(', ')}"
+          end
+
+          if nullable != :not_nullable && distinct
+            raise 'Invalid column definition, `distinct` and `nullable` columns are not allowed at the same time'
+          end
+
+          nullable
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/pagination/keyset/order.rb b/lib/gitlab/pagination/keyset/order.rb
new file mode 100644
index 00000000000..e8e68a5c4a5
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/order.rb
@@ -0,0 +1,248 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      # This class is a special ORDER BY clause which is compatible with ActiveRecord. It helps
+      # building keyset paginated queries.
+      #
+      # In ActiveRecord we use the `order()` method which will generate the `ORDER BY X` SQL clause
+      #
+      # Project.where(active: true).order(id: :asc)
+      #
+      # # Or
+      #
+      # Project.where(active: true).order(created_at: :asc, id: desc)
+      #
+      # Gitlab::Pagination::Keyset::Order class encapsulates more information about the order columns
+      # in order to implement keyset pagination in a generic way
+      #
+      # - Extract values from a record (usually the last item of the previous query)
+      # - Build query conditions based on the column configuration
+      #
+      # Example 1: Order by primary key
+      #
+      #   # Simple order definition for the primary key as an ActiveRecord scope
+      #   scope :id_asc_ordered, -> {
+      #     keyset_order = Gitlab::Pagination::Keyset::Order.build([
+      #       Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
+      #         attribute: :id,
+      #         order_expression: Project.arel_table[:id].asc
+      #       )
+      #     ])
+      #
+      #     reorder(keyset_order)
+      #   }
+      #
+      #   # ... Later in the application code:
+      #
+      #   # Compatible with ActiveRecord's `order()` method
+      #   page1 = Project.where(active: true).id_asc_ordered.limit(5)
+      #   keyset_order = Gitlab::Pagination::Keyset::Order.extract_keyset_order_object(page1)
+      #
+      #   last_record = page1.last
+      #   cursor_values = keyset_order.cursor_attributes_for_node(last_record) # { id: x }
+      #
+      #   page2 = keyset_order.apply_cursor_conditions(Project.where(active: true).id_asc_ordered, cursor_values).limit(5)
+      #
+      #   last_record = page2.last
+      #   cursor_values = keyset_order.cursor_attributes_for_node(last_record)
+      #
+      #   page3 = keyset_order.apply_cursor_conditions(Project.where(active: true).id_asc_ordered, cursor_values).limit(5)
+      #
+      # Example 2: Order by creation time and primary key (primary key is the tie breaker)
+      #
+      #   scope :created_at_ordered, -> {
+      #     keyset_order = Gitlab::Pagination::Keyset::Order.build([
+      #       Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
+      #         attribute: :created_at,
+      #         column_expression: Project.arel_table[:created_at],
+      #         order_expression: Project.arel_table[:created_at].asc,
+      #         distinct: false, # values in the column are not unique
+      #         nullable: :nulls_last # we might see NULL values (bottom)
+      #       ),
+      #       Gitlab::Pagination::Keyset::ColumnOrderDefinition.new(
+      #         attribute: :id,
+      #         order_expression: Project.arel_table[:id].asc
+      #       )
+      #     ])
+      #
+      #     reorder(keyset_order)
+      #   }
+      #
+      class Order < Arel::Nodes::SqlLiteral
+        attr_reader :column_definitions
+
+        def initialize(column_definitions:)
+          @column_definitions = column_definitions
+
+          super(to_sql_literal(@column_definitions))
+        end
+
+        # Tells whether the given ActiveRecord::Relation has keyset ordering
+        def self.keyset_aware?(scope)
+          scope.order_values.first.is_a?(self) && scope.order_values.one?
+        end
+
+        def self.extract_keyset_order_object(scope)
+          scope.order_values.first
+        end
+
+        def self.build(column_definitions)
+          new(column_definitions: column_definitions)
+        end
+
+        def cursor_attributes_for_node(node)
+          column_definitions.each_with_object({}) do |column_definition, hash|
+            field_value = node[column_definition.attribute_name]
+            hash[column_definition.attribute_name] = if field_value.is_a?(Time)
+                                                       field_value.strftime('%Y-%m-%d %H:%M:%S.%N %Z')
+                                                     elsif field_value.nil?
+                                                       nil
+                                                     else
+                                                       field_value.to_s
+                                                     end
+          end
+        end
+
+        # This methods builds the conditions for the keyset pagination
+        #
+        # Example:
+        #
+        # |created_at|id|
+        # |----------|--|
+        # |2020-01-01| 1|
+        # |      null| 2|
+        # |      null| 3|
+        # |2020-02-01| 4|
+        #
+        # Note: created_at is not distinct and nullable
+        # Order `ORDER BY created_at DESC, id DESC`
+        #
+        # We get the following cursor values from the previous page:
+        # { id: 4, created_at: '2020-02-01' }
+        #
+        # To get the next rows, we need to build the following conditions:
+        #
+        # (created_at = '2020-02-01' AND id < 4) OR (created_at < '2020-01-01')
+        #
+        # DESC ordering ensures that NULL values are on top so we don't need conditions for NULL values
+        #
+        # Another cursor example:
+        # { id: 3, created_at: nil }
+        #
+        # To get the next rows, we need to build the following conditions:
+        #
+        # (id < 3 AND created_at IS NULL) OR (created_at IS NOT NULL)
+        def build_where_values(values)
+          return if values.blank?
+
+          verify_incoming_values!(values)
+
+          where_values = []
+
+          reversed_column_definitions = column_definitions.reverse
+          reversed_column_definitions.each_with_index do |column_definition, i|
+            value = values[column_definition.attribute_name]
+
+            conditions_for_column(column_definition, value).each do |condition|
+              column_definitions_after_index = reversed_column_definitions.last(column_definitions.reverse.size - i - 1)
+
+              equal_conditon_for_rest = column_definitions_after_index.map do |definition|
+                definition.column_expression.eq(values[definition.attribute_name])
+              end
+
+              where_values << Arel::Nodes::Grouping.new(Arel::Nodes::And.new([condition, *equal_conditon_for_rest].compact))
+            end
+          end
+
+          build_or_query(where_values)
+        end
+
+        # rubocop: disable CodeReuse/ActiveRecord
+        def apply_cursor_conditions(scope, values = {})
+          scope = apply_custom_projections(scope)
+          scope.where(build_where_values(values))
+        end
+        # rubocop: enable CodeReuse/ActiveRecord
+
+        def reversed_order
+          self.class.build(column_definitions.map(&:reverse))
+        end
+
+        private
+
+        # Adds extra columns to the SELECT clause
+        def apply_custom_projections(scope)
+          additional_projections = column_definitions.select(&:add_to_projections).map do |column_definition|
+            # avoid mutating the original column_expression
+            column_definition.column_expression.dup.as(column_definition.attribute_name).to_sql
+          end
+
+          scope = scope.select(*scope.arel.projections, *additional_projections) if additional_projections
+          scope
+        end
+
+        def conditions_for_column(column_definition, value)
+          conditions = []
+          # Depending on the order, build a query condition fragment for taking the next rows
+          if column_definition.distinct? || (!column_definition.distinct? && value.present?)
+            conditions << compare_column_with_value(column_definition, value)
+          end
+
+          # When the column is nullable, additional conditions for NULL a NOT NULL values are necessary.
+          # This depends on the position of the nulls (top or bottom of the resultset).
+          if column_definition.nulls_first? && value.blank?
+            conditions << column_definition.column_expression.not_eq(nil)
+          elsif column_definition.nulls_last? && value.present?
+            conditions << column_definition.column_expression.eq(nil)
+          end
+
+          conditions
+        end
+
+        def compare_column_with_value(column_definition, value)
+          if column_definition.descending_order?
+            column_definition.column_expression.lt(value)
+          else
+            column_definition.column_expression.gt(value)
+          end
+        end
+
+        def build_or_query(expressions)
+          or_expression = expressions.reduce { |or_expression, expression| Arel::Nodes::Or.new(or_expression, expression) }
+
+          Arel::Nodes::Grouping.new(or_expression)
+        end
+
+        def to_sql_literal(column_definitions)
+          column_definitions.map do |column_definition|
+            if column_definition.order_expression.respond_to?(:to_sql)
+              column_definition.order_expression.to_sql
+            else
+              column_definition.order_expression.to_s
+            end
+          end.join(', ')
+        end
+
+        def verify_incoming_values!(values)
+          value_keys = values.keys.map(&:to_s)
+          order_attrbute_names = column_definitions.map(&:attribute_name).map(&:to_s)
+          missing_items = order_attrbute_names - value_keys
+          extra_items = value_keys - order_attrbute_names
+
+          if missing_items.any? || extra_items.any?
+            error_text = ['Incorrect cursor values were given']
+
+            error_text << "Extra items: #{extra_items.join(', ')}" if extra_items.any?
+            error_text << "Missing items: #{missing_items.join(', ')}" if missing_items.any?
+
+            error_text.compact
+
+            raise error_text.join('. ')
+          end
+        end
+      end
+    end
+  end
+end