Add latest changes from gitlab-org/gitlab@14-2-stable-eev14.2.0-rc42

3 files changed, 211 insertions, 44 deletions

diff --git a/lib/gitlab/pagination/keyset/column_condition_builder.rb b/lib/gitlab/pagination/keyset/column_condition_builder.rb
new file mode 100644
index 00000000000..ca436000abe
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/column_condition_builder.rb
@@ -0,0 +1,206 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      class ColumnConditionBuilder
+        # This class builds the WHERE conditions for the keyset pagination library.
+        # It produces WHERE conditions for one column at a time.
+        #
+        # Requisite 1: Only the last column (columns.last) is non-nullable and distinct.
+        # Requisite 2: Only one column is distinct and non-nullable.
+        #
+        # Scenario: We want to order by columns named X, Y and Z and build the conditions
+        #          used in the WHERE clause of a pagination query using a set of cursor values.
+        #   X is the column definition for a nullable column
+        #   Y is the column definition for a non-nullable but not distinct column
+        #   Z is the column definition for a distinct, non-nullable column used as a tie breaker.
+        #
+        #   Then the method is initially invoked with these arguments:
+        #     columns = [ColumnDefinition for X, ColumnDefinition for Y, ColumnDefinition for Z]
+        #     values = { X: x, Y: y, Z: z } => these represent cursor values for pagination
+        #                                      (x could be nil since X is nullable)
+        #     current_conditions is initialized to [] to store the result during the iteration calls
+        #     invoked within the Order#build_where_values method.
+        #
+        #   The elements of current_conditions are instances of Arel::Nodes and -
+        #    will be concatenated using OR or UNION to be used in the WHERE clause.
+        #
+        #   Example: Let's say we want to build WHERE clause conditions for
+        #     ORDER BY X DESC NULLS LAST, Y ASC, Z DESC
+        #
+        #     Iteration 1:
+        #       columns = [X, Y, Z]
+        #       At the end, current_conditions should be:
+        #         [(Z < z)]
+        #
+        #     Iteration 2:
+        #       columns = [X, Y]
+        #       At the end, current_conditions should be:
+        #         [(Y > y) OR (Y = y AND Z < z)]
+        #
+        #     Iteration 3:
+        #       columns = [X]
+        #       At the end, current_conditions should be:
+        #         [((X IS NOT NULL AND Y > y) OR (X IS NOT NULL AND Y = y AND Z < z))
+        #           OR
+        #          ((x IS NULL) OR (X IS NULL))]
+        #
+        # Parameters:
+        #
+        #  - columns: instance of ColumnOrderDefinition
+        #  - value: cursor value for the column
+        def initialize(column, value)
+          @column = column
+          @value = value
+        end
+
+        def where_conditions(current_conditions)
+          return not_nullable_conditions(current_conditions) if column.not_nullable?
+          return nulls_first_conditions(current_conditions) if column.nulls_first?
+
+          # Here we are dealing with the case of column_definition.nulls_last?
+          # Suppose ORDER BY X DESC NULLS FIRST, Y ASC, Z DESC is the ordering clause
+          # and we already have built the conditions for columns Y and Z.
+          #
+          # We first need a set of conditions to use when x (the value for X) is NULL:
+          #   null_conds = [
+          #     (x IS NULL AND X IS NULL AND Y<y),
+          #     (x IS NULL AND X IS NULL AND Y=y AND Z<z),
+          null_conds = current_conditions.map do |conditional|
+            Arel::Nodes::And.new([value_is_null, column_is_null, conditional])
+          end
+
+          # We then need a set of conditions to use when m has an actual value:
+          #   non_null_conds = [
+          #     (x IS NOT NULL AND X IS NULL),
+          #     (x IS NOT NULL AND X < x)
+          #     (x IS NOT NULL AND X = x AND Y > y),
+          #     (x IS NOT NULL AND X = x AND Y = y AND Z < z),
+          tie_breaking_conds = current_conditions.map do |conditional|
+            Arel::Nodes::And.new([column_equals_to_value, conditional])
+          end
+
+          non_null_conds = [column_is_null, compare_column_with_value, *tie_breaking_conds].map do |conditional|
+            Arel::Nodes::And.new([value_is_not_null, conditional])
+          end
+
+          [*null_conds, *non_null_conds]
+        end
+
+        private
+
+        # WHEN THE COLUMN IS NON-NULLABLE AND DISTINCT
+        #   Per Assumption 1, only the last column can be non-nullable and distinct
+        #   (column Z is non-nullable/distinct and comes last in the example).
+        #   So the Order#build_where_conditions is being called for the first time with current_conditions = [].
+        #
+        #   At the end of the call, we should expect:
+        #     current_conditions should be [(Z < z)]
+        #
+        # WHEN THE COLUMN IS NON-NULLABLE BUT NOT DISTINCT
+        #   Let's say Z has been processed and we are about to process the column Y next.
+        #   (per requisite 1, if a non-nullable but not distinct column is being processed,
+        #    at the least, the conditional for the non-nullable/distinct column exists)
+        #
+        #   At the start of the method call:
+        #     current_conditions = [(Z < z)]
+        #     comparison_node = (Y < y)
+        #     eqaulity_node = (Y = y)
+        #
+        #   We should add a comparison node for the next column Y, (Y < y)
+        #    then break a tie using the previous conditionals, (Y = y AND Z < z)
+        #
+        #   At the end of the call, we should expect:
+        #     current_conditions = [(Y < y), (Y = y AND Z < z)]
+        def not_nullable_conditions(current_conditions)
+          tie_break_conds = current_conditions.map do |conditional|
+            Arel::Nodes::And.new([column_equals_to_value, conditional])
+          end
+
+          [compare_column_with_value, *tie_break_conds]
+        end
+
+        def nulls_first_conditions(current_conditions)
+          # Using the same scenario described earlier,
+          # suppose the ordering clause is ORDER BY X DESC NULLS FIRST, Y ASC, Z DESC
+          # and we have built the conditions for columns Y and Z in previous iterations:
+          #
+          #   current_conditions = [(Y > y), (Y = y AND Z < z)]
+          #
+          # In this branch of the iteration,
+          # we first need a set of conditions to use when m (the value for M) is NULL:
+          #   null_conds = [
+          #     (x IS NULL AND X IS NULL AND Y > y),
+          #     (x IS NULL AND X IS NULL AND Y = y AND Z < z),
+          #     (x IS NULL AND X IS NOT NULL)]
+          #
+          # Note that when x has an actual value, say x = 3, null_conds evalutes to FALSE.
+          tie_breaking_conds = current_conditions.map do |conditional|
+            Arel::Nodes::And.new([column_is_null, conditional])
+          end
+
+          null_conds = [*tie_breaking_conds, column_is_not_null].map do |conditional|
+            Arel::Nodes::And.new([value_is_null, conditional])
+          end
+
+          # We then need a set of conditions to use when m has an actual value:
+          #   non_null_conds = [
+          #     (x IS NOT NULL AND X < x),
+          #     (x IS NOT NULL AND X = x AND Y > y),
+          #     (x IS NOT NULL AND X = x AND Y = y AND Z < z)]
+          #
+          # Note again that when x IS NULL, non_null_conds evaluates to FALSE.
+          tie_breaking_conds = current_conditions.map do |conditional|
+            Arel::Nodes::And.new([column_equals_to_value, conditional])
+          end
+
+          # The combined OR condition (null_where_cond OR non_null_where_cond) will return a correct result -
+          # without having to account for whether x is nil or an actual value at the application level.
+          non_null_conds = [compare_column_with_value, *tie_breaking_conds].map do |conditional|
+            Arel::Nodes::And.new([value_is_not_null, conditional])
+          end
+
+          [*null_conds, *non_null_conds]
+        end
+
+        def column_equals_to_value
+          @equality_node ||= column.column_expression.eq(value)
+        end
+
+        def column_is_null
+          @column_is_null ||= column.column_expression.eq(nil)
+        end
+
+        def column_is_not_null
+          @column_is_not_null ||= column.column_expression.not_eq(nil)
+        end
+
+        def value_is_null
+          @value_is_null ||= build_quoted_value.eq(nil)
+        end
+
+        def value_is_not_null
+          @value_is_not_null ||= build_quoted_value.not_eq(nil)
+        end
+
+        def compare_column_with_value
+          if column.descending_order?
+            column.column_expression.lt(value)
+          else
+            column.column_expression.gt(value)
+          end
+        end
+
+        # Turns the given value to an SQL literal by casting it to the proper format.
+        def build_quoted_value
+          return value if value.instance_of?(Arel::Nodes::SqlLiteral)
+
+          Arel::Nodes.build_quoted(value, column.column_expression)
+        end
+
+        attr_reader :column, :value
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/pagination/keyset/order.rb b/lib/gitlab/pagination/keyset/order.rb
index 19d44ee69dd..ccfa9334a12 100644
--- a/lib/gitlab/pagination/keyset/order.rb
+++ b/lib/gitlab/pagination/keyset/order.rb
@@ -141,24 +141,10 @@ module Gitlab
 
           return use_composite_row_comparison(values) if composite_row_comparison_possible?
 
-          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
-
-          where_values
+          column_definitions
+            .map { ColumnConditionBuilder.new(_1, values[_1.attribute_name]) }
+            .reverse
+            .reduce([]) { |where_conditions, column| column.where_conditions(where_conditions) }
         end
 
         def where_values_with_or_query(values)
@@ -222,32 +208,6 @@ module Gitlab
           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)
           return [] if expressions.blank?
 
diff --git a/lib/gitlab/pagination/keyset/simple_order_builder.rb b/lib/gitlab/pagination/keyset/simple_order_builder.rb
index 76d6bbadaa4..5e79910a3e9 100644
--- a/lib/gitlab/pagination/keyset/simple_order_builder.rb
+++ b/lib/gitlab/pagination/keyset/simple_order_builder.rb
@@ -122,6 +122,7 @@ module Gitlab
 
           return unless attribute
           return unless tie_breaker_attribute
+          return unless attribute.respond_to?(:name)
 
           model_class.column_names.include?(attribute.name.to_s) &&
             arel_table[primary_key].to_s == tie_breaker_attribute.to_s