Add latest changes from gitlab-org/gitlab@master

9 files changed, 487 insertions, 86 deletions

diff --git a/lib/gitlab/graphql/connections.rb b/lib/gitlab/graphql/connections.rb
index fbccdfa7b08..64f7a268b7e 100644
--- a/lib/gitlab/graphql/connections.rb
+++ b/lib/gitlab/graphql/connections.rb
@@ -6,7 +6,7 @@ module Gitlab
       def self.use(_schema)
         GraphQL::Relay::BaseConnection.register_connection_implementation(
           ActiveRecord::Relation,
-          Gitlab::Graphql::Connections::KeysetConnection
+          Gitlab::Graphql::Connections::Keyset::Connection
         )
       end
     end
diff --git a/lib/gitlab/graphql/connections/keyset/conditions/base_condition.rb b/lib/gitlab/graphql/connections/keyset/conditions/base_condition.rb
new file mode 100644
index 00000000000..22728cc0b65
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/conditions/base_condition.rb
@@ -0,0 +1,40 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        module Conditions
+          class BaseCondition
+            def initialize(arel_table, names, values, operator, before_or_after)
+              @arel_table, @names, @values, @operator, @before_or_after = arel_table, names, values, operator, before_or_after
+            end
+
+            def build
+              raise NotImplementedError
+            end
+
+            private
+
+            attr_reader :arel_table, :names, :values, :operator, :before_or_after
+
+            def table_condition(attribute, value, operator)
+              case operator
+              when '>'
+                arel_table[attribute].gt(value)
+              when '<'
+                arel_table[attribute].lt(value)
+              when '='
+                arel_table[attribute].eq(value)
+              when 'is_null'
+                arel_table[attribute].eq(nil)
+              when 'is_not_null'
+                arel_table[attribute].not_eq(nil)
+              end
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/conditions/not_null_condition.rb b/lib/gitlab/graphql/connections/keyset/conditions/not_null_condition.rb
new file mode 100644
index 00000000000..3b56ddb996d
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/conditions/not_null_condition.rb
@@ -0,0 +1,57 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        module Conditions
+          class NotNullCondition < BaseCondition
+            def build
+              conditions = [first_attribute_condition]
+
+              # If there is only one order field, we can assume it
+              # does not contain NULLs, and don't need additional
+              # conditions
+              unless names.count == 1
+                conditions << [second_attribute_condition, final_condition]
+              end
+
+              conditions.join
+            end
+
+            private
+
+            # ex: "(relative_position > 23)"
+            def first_attribute_condition
+              <<~SQL
+                (#{table_condition(names.first, values.first, operator.first).to_sql})
+              SQL
+            end
+
+            # ex: " OR (relative_position = 23 AND id > 500)"
+            def second_attribute_condition
+              condition = <<~SQL
+                OR (
+                  #{table_condition(names.first, values.first, '=').to_sql}
+                  AND
+                  #{table_condition(names[1], values[1], operator[1]).to_sql}
+                )
+              SQL
+
+              condition
+            end
+
+            # ex: " OR (relative_position IS NULL)"
+            def final_condition
+              if before_or_after == :after
+                <<~SQL
+                  OR (#{table_condition(names.first, nil, 'is_null').to_sql})
+                SQL
+              end
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/conditions/null_condition.rb b/lib/gitlab/graphql/connections/keyset/conditions/null_condition.rb
new file mode 100644
index 00000000000..71a74936d5d
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/conditions/null_condition.rb
@@ -0,0 +1,41 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        module Conditions
+          class NullCondition < BaseCondition
+            def build
+              [first_attribute_condition, final_condition].join
+            end
+
+            private
+
+            # ex: "(relative_position IS NULL AND id > 500)"
+            def first_attribute_condition
+              condition = <<~SQL
+                (
+                  #{table_condition(names.first, nil, 'is_null').to_sql}
+                  AND
+                  #{table_condition(names[1], values[1], operator[1]).to_sql}
+                )
+              SQL
+
+              condition
+            end
+
+            # ex: " OR (relative_position IS NOT NULL)"
+            def final_condition
+              if before_or_after == :before
+                <<~SQL
+                  OR (#{table_condition(names.first, nil, 'is_not_null').to_sql})
+                SQL
+              end
+            end
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/connection.rb b/lib/gitlab/graphql/connections/keyset/connection.rb
new file mode 100644
index 00000000000..0daf726c005
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/connection.rb
@@ -0,0 +1,148 @@
+# frozen_string_literal: true
+
+# Keyset::Connection provides cursor based pagination, to avoid using OFFSET.
+# It basically sorts / filters using WHERE sorting_value > cursor.
+# We do this for performance reasons (https://gitlab.com/gitlab-org/gitlab-foss/issues/45756),
+# as well as for having stable pagination
+# https://graphql-ruby.org/pro/cursors.html#whats-the-difference
+# https://coderwall.com/p/lkcaag/pagination-you-re-probably-doing-it-wrong
+#
+# It currently supports sorting on two columns, but the last column must
+# be the primary key. For example
+#
+#   Issue.order(created_at: :asc).order(:id)
+#   Issue.order(due_date: :asc).order(:id)
+#
+# It will tolerate non-attribute ordering, but only attributes determine the cursor.
+# For example, this is legitimate:
+#
+#   Issue.order('issues.due_date IS NULL').order(due_date: :asc).order(:id)
+#
+# but anything more complex has a chance of not working.
+#
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        class Connection < GraphQL::Relay::BaseConnection
+          include Gitlab::Utils::StrongMemoize
+
+          # TODO https://gitlab.com/gitlab-org/gitlab/issues/35104
+          include Gitlab::Graphql::Connections::Keyset::LegacyKeysetConnection
+
+          def cursor_from_node(node)
+            return legacy_cursor_from_node(node) if use_legacy_pagination?
+
+            encoded_json_from_ordering(node)
+          end
+
+          def sliced_nodes
+            return legacy_sliced_nodes if use_legacy_pagination?
+
+            @sliced_nodes ||=
+              begin
+                OrderInfo.validate_ordering(ordered_nodes, order_list)
+
+                sliced = ordered_nodes
+                sliced = slice_nodes(sliced, before, :before) if before.present?
+                sliced = slice_nodes(sliced, after, :after) if after.present?
+
+                sliced
+              end
+          end
+
+          def paged_nodes
+            # These are the nodes that will be loaded into memory for rendering
+            # So we're ok loading them into memory here as that's bound to happen
+            # anyway. Having them ready means we can modify the result while
+            # rendering the fields.
+            @paged_nodes ||= load_paged_nodes.to_a
+          end
+
+          private
+
+          def load_paged_nodes
+            if first && last
+              raise Gitlab::Graphql::Errors::ArgumentError.new("Can only provide either `first` or `last`, not both")
+            end
+
+            if last
+              sliced_nodes.last(limit_value)
+            else
+              sliced_nodes.limit(limit_value) # rubocop: disable CodeReuse/ActiveRecord
+            end
+          end
+
+          # rubocop: disable CodeReuse/ActiveRecord
+          def slice_nodes(sliced, encoded_cursor, before_or_after)
+            decoded_cursor = ordering_from_encoded_json(encoded_cursor)
+            builder = QueryBuilder.new(arel_table, order_list, decoded_cursor, before_or_after)
+            ordering = builder.conditions
+
+            sliced.where(*ordering).where.not(id: decoded_cursor['id'])
+          end
+          # rubocop: enable CodeReuse/ActiveRecord
+
+          def limit_value
+            @limit_value ||= [first, last, max_page_size].compact.min
+          end
+
+          def ordered_nodes
+            strong_memoize(:order_nodes) do
+              unless nodes.primary_key.present?
+                raise ArgumentError.new('Relation must have a primary key')
+              end
+
+              list = OrderInfo.build_order_list(nodes)
+
+              # ensure there is a primary key ordering
+              if list&.last&.attribute_name != nodes.primary_key
+                nodes.order(arel_table[nodes.primary_key].desc) # rubocop: disable CodeReuse/ActiveRecord
+              else
+                nodes
+              end
+            end
+          end
+
+          def order_list
+            strong_memoize(:order_list) do
+              OrderInfo.build_order_list(ordered_nodes)
+            end
+          end
+
+          def arel_table
+            nodes.arel_table
+          end
+
+          # Storing the current order values in the cursor allows us to
+          # make an intelligent decision on handling NULL values.
+          # Otherwise we would either need to fetch the record first,
+          # or fetch it in the SQL, significantly complicating it.
+          def encoded_json_from_ordering(node)
+            ordering = { 'id' => node[:id].to_s }
+
+            order_list.each do |field|
+              field_name = field.attribute_name
+              ordering[field_name] = node[field_name].to_s
+            end
+
+            encode(ordering.to_json)
+          end
+
+          def ordering_from_encoded_json(cursor)
+            JSON.parse(decode(cursor))
+          rescue JSON::ParserError
+            # for the transition period where a client might request using an
+            # old style cursor.  Once removed, make it an error:
+            #   raise Gitlab::Graphql::Errors::ArgumentError, "Please provide a valid cursor"
+            # TODO can be removed in next release
+            # https://gitlab.com/gitlab-org/gitlab/issues/32933
+            field_name = order_list.first.attribute_name
+
+            { field_name => decode(cursor) }
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/legacy_keyset_connection.rb b/lib/gitlab/graphql/connections/keyset/legacy_keyset_connection.rb
new file mode 100644
index 00000000000..baf900d1048
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/legacy_keyset_connection.rb
@@ -0,0 +1,66 @@
+# frozen_string_literal: true
+
+# TODO https://gitlab.com/gitlab-org/gitlab/issues/35104
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        module LegacyKeysetConnection
+          def legacy_cursor_from_node(node)
+            encode(node[legacy_order_field].to_s)
+          end
+
+          # rubocop: disable CodeReuse/ActiveRecord
+          def legacy_sliced_nodes
+            @sliced_nodes ||=
+              begin
+                sliced = nodes
+
+                sliced = sliced.where(legacy_before_slice) if before.present?
+                sliced = sliced.where(legacy_after_slice) if after.present?
+
+                sliced
+              end
+          end
+          # rubocop: enable CodeReuse/ActiveRecord
+
+          private
+
+          def use_legacy_pagination?
+            strong_memoize(:feature_disabled) do
+              Feature.disabled?(:graphql_keyset_pagination, default_enabled: true)
+            end
+          end
+
+          def legacy_before_slice
+            if legacy_sort_direction == :asc
+              arel_table[legacy_order_field].lt(decode(before))
+            else
+              arel_table[legacy_order_field].gt(decode(before))
+            end
+          end
+
+          def legacy_after_slice
+            if legacy_sort_direction == :asc
+              arel_table[legacy_order_field].gt(decode(after))
+            else
+              arel_table[legacy_order_field].lt(decode(after))
+            end
+          end
+
+          def legacy_order_info
+            @legacy_order_info ||= nodes.order_values.first
+          end
+
+          def legacy_order_field
+            @legacy_order_field ||= legacy_order_info&.expr&.name || nodes.primary_key
+          end
+
+          def legacy_sort_direction
+            @legacy_order_direction ||= legacy_order_info&.direction || :desc
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/order_info.rb b/lib/gitlab/graphql/connections/keyset/order_info.rb
new file mode 100644
index 00000000000..6c4be93bfee
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/order_info.rb
@@ -0,0 +1,66 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        class OrderInfo
+          def initialize(order_value)
+            @order_value = order_value
+          end
+
+          def attribute_name
+            order_value.expr.name
+          end
+
+          def operator_for(before_or_after)
+            case before_or_after
+            when :before
+              sort_direction == :asc ? '<' : '>'
+            when :after
+              sort_direction == :asc ? '>' : '<'
+            end
+          end
+
+          # Only allow specific node types.  For example ignore String nodes
+          def self.build_order_list(relation)
+            order_list = relation.order_values.select do |value|
+              value.is_a?(Arel::Nodes::Ascending) || value.is_a?(Arel::Nodes::Descending)
+            end
+
+            order_list.map { |info| OrderInfo.new(info) }
+          end
+
+          def self.validate_ordering(relation, order_list)
+            if order_list.empty?
+              raise ArgumentError.new('A minimum of 1 ordering field is required')
+            end
+
+            if order_list.count > 2
+              raise ArgumentError.new('A maximum of 2 ordering fields are allowed')
+            end
+
+            # make sure the last ordering field is non-nullable
+            attribute_name = order_list.last&.attribute_name
+
+            if relation.columns_hash[attribute_name].null
+              raise ArgumentError.new("Column `#{attribute_name}` must not allow NULL")
+            end
+
+            if order_list.last.attribute_name != relation.primary_key
+              raise ArgumentError.new("Last ordering field must be the primary key, `#{relation.primary_key}`")
+            end
+          end
+
+          private
+
+          attr_reader :order_value
+
+          def sort_direction
+            order_value.direction
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset/query_builder.rb b/lib/gitlab/graphql/connections/keyset/query_builder.rb
new file mode 100644
index 00000000000..e93c25d85fc
--- /dev/null
+++ b/lib/gitlab/graphql/connections/keyset/query_builder.rb
@@ -0,0 +1,68 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Graphql
+    module Connections
+      module Keyset
+        class QueryBuilder
+          def initialize(arel_table, order_list, decoded_cursor, before_or_after)
+            @arel_table, @order_list, @decoded_cursor, @before_or_after = arel_table, order_list, decoded_cursor, before_or_after
+
+            if order_list.empty?
+              raise ArgumentError.new('No ordering scopes have been supplied')
+            end
+          end
+
+          # Based on whether the main field we're ordering on is NULL in the
+          # cursor, we can more easily target our query condition.
+          # We assume that the last ordering field is unique, meaning
+          # it will not contain NULLs.
+          # We currently only support two ordering fields.
+          #
+          # Example of the conditions for
+          #   relation: Issue.order(relative_position: :asc).order(id: :asc)
+          #   after cursor: relative_position: 1500, id: 500
+          #
+          #   when cursor[relative_position] is not NULL
+          #
+          #       ("issues"."relative_position" > 1500)
+          #       OR (
+          #         "issues"."relative_position" = 1500
+          #         AND
+          #         "issues"."id" > 500
+          #       )
+          #       OR ("issues"."relative_position" IS NULL)
+          #
+          #   when cursor[relative_position] is NULL
+          #
+          #       "issues"."relative_position" IS NULL
+          #       AND
+          #       "issues"."id" > 500
+          #
+          def conditions
+            attr_names  = order_list.map { |field| field.attribute_name }
+            attr_values = attr_names.map { |name| decoded_cursor[name] }
+
+            if attr_names.count == 1 && attr_values.first.nil?
+              raise Gitlab::Graphql::Errors::ArgumentError.new('Before/after cursor invalid: `nil` was provided as only sortable value')
+            end
+
+            if attr_names.count == 1 || attr_values.first.present?
+              Keyset::Conditions::NotNullCondition.new(arel_table, attr_names, attr_values, operators, before_or_after).build
+            else
+              Keyset::Conditions::NullCondition.new(arel_table, attr_names, attr_values, operators, before_or_after).build
+            end
+          end
+
+          private
+
+          attr_reader :arel_table, :order_list, :decoded_cursor, :before_or_after
+
+          def operators
+            order_list.map { |field| field.operator_for(before_or_after) }
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/graphql/connections/keyset_connection.rb b/lib/gitlab/graphql/connections/keyset_connection.rb
deleted file mode 100644
index 715963a44c1..00000000000
--- a/lib/gitlab/graphql/connections/keyset_connection.rb
+++ /dev/null
@@ -1,85 +0,0 @@
-# frozen_string_literal: true
-
-module Gitlab
-  module Graphql
-    module Connections
-      class KeysetConnection < GraphQL::Relay::BaseConnection
-        def cursor_from_node(node)
-          encode(node[order_field].to_s)
-        end
-
-        # rubocop: disable CodeReuse/ActiveRecord
-        def sliced_nodes
-          @sliced_nodes ||=
-            begin
-              sliced = nodes
-
-              sliced = sliced.where(before_slice) if before.present?
-              sliced = sliced.where(after_slice) if after.present?
-
-              sliced
-            end
-        end
-        # rubocop: enable CodeReuse/ActiveRecord
-
-        def paged_nodes
-          # These are the nodes that will be loaded into memory for rendering
-          # So we're ok loading them into memory here as that's bound to happen
-          # anyway. Having them ready means we can modify the result while
-          # rendering the fields.
-          @paged_nodes ||= load_paged_nodes.to_a
-        end
-
-        private
-
-        def load_paged_nodes
-          if first && last
-            raise Gitlab::Graphql::Errors::ArgumentError.new("Can only provide either `first` or `last`, not both")
-          end
-
-          if last
-            sliced_nodes.last(limit_value)
-          else
-            sliced_nodes.limit(limit_value) # rubocop: disable CodeReuse/ActiveRecord
-          end
-        end
-
-        def before_slice
-          if sort_direction == :asc
-            table[order_field].lt(decode(before))
-          else
-            table[order_field].gt(decode(before))
-          end
-        end
-
-        def after_slice
-          if sort_direction == :asc
-            table[order_field].gt(decode(after))
-          else
-            table[order_field].lt(decode(after))
-          end
-        end
-
-        def limit_value
-          @limit_value ||= [first, last, max_page_size].compact.min
-        end
-
-        def table
-          nodes.arel_table
-        end
-
-        def order_info
-          @order_info ||= nodes.order_values.first
-        end
-
-        def order_field
-          @order_field ||= order_info&.expr&.name || nodes.primary_key
-        end
-
-        def sort_direction
-          @order_direction ||= order_info&.direction || :desc
-        end
-      end
-    end
-  end
-end