Add latest changes from gitlab-org/gitlab@master

4 files changed, 213 insertions, 0 deletions

diff --git a/lib/gitlab/pagination/keyset.rb b/lib/gitlab/pagination/keyset.rb
new file mode 100644
index 00000000000..5bd45fa9b56
--- /dev/null
+++ b/lib/gitlab/pagination/keyset.rb
@@ -0,0 +1,21 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      def self.paginate(request_context, relation)
+        Gitlab::Pagination::Keyset::Pager.new(request_context).paginate(relation)
+      end
+
+      def self.available?(request_context, relation)
+        order_by = request_context.page.order_by
+
+        # This is only available for Project and order-by id (asc/desc)
+        return false unless relation.klass == Project
+        return false unless order_by.size == 1 && order_by[:id]
+
+        true
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/pagination/keyset/page.rb b/lib/gitlab/pagination/keyset/page.rb
new file mode 100644
index 00000000000..735f54faf0f
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/page.rb
@@ -0,0 +1,47 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      # A Page models the pagination information for a particular page of the collection
+      class Page
+        # Default number of records for a page
+        DEFAULT_PAGE_SIZE = 20
+
+        # Maximum number of records for a page
+        MAXIMUM_PAGE_SIZE = 100
+
+        attr_accessor :lower_bounds, :end_reached
+        attr_reader :order_by
+
+        def initialize(order_by: {}, lower_bounds: nil, per_page: DEFAULT_PAGE_SIZE, end_reached: false)
+          @order_by = order_by.symbolize_keys
+          @lower_bounds = lower_bounds&.symbolize_keys
+          @per_page = per_page
+          @end_reached = end_reached
+        end
+
+        # Number of records to return per page
+        def per_page
+          return DEFAULT_PAGE_SIZE if @per_page <= 0
+
+          [@per_page, MAXIMUM_PAGE_SIZE].min
+        end
+
+        # Determine whether this page indicates the end of the collection
+        def end_reached?
+          @end_reached
+        end
+
+        # Construct a Page for the next page
+        # Uses identical order_by/per_page information for the next page
+        def next(lower_bounds, end_reached)
+          dup.tap do |next_page|
+            next_page.lower_bounds = lower_bounds&.symbolize_keys
+            next_page.end_reached = end_reached
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/pagination/keyset/pager.rb b/lib/gitlab/pagination/keyset/pager.rb
new file mode 100644
index 00000000000..99b125cc2a0
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/pager.rb
@@ -0,0 +1,56 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      class Pager
+        attr_reader :request
+
+        def initialize(request)
+          @request = request
+        end
+
+        def paginate(relation)
+          # Validate assumption: The last two columns must match the page order_by
+          validate_order!(relation)
+
+          # This performs the database query and retrieves records
+          # We retrieve one record more to check if we have data beyond this page
+          all_records = relation.limit(page.per_page + 1).to_a # rubocop: disable CodeReuse/ActiveRecord
+
+          records_for_page = all_records.first(page.per_page)
+
+          # If we retrieved more records than belong on this page,
+          # we know there's a next page
+          there_is_more = all_records.size > records_for_page.size
+          apply_headers(records_for_page.last, there_is_more)
+
+          records_for_page
+        end
+
+        private
+
+        def apply_headers(last_record_in_page, there_is_more)
+          end_reached = last_record_in_page.nil? || !there_is_more
+          lower_bounds = last_record_in_page&.slice(page.order_by.keys)
+
+          next_page = page.next(lower_bounds, end_reached)
+
+          request.apply_headers(next_page)
+        end
+
+        def page
+          @page ||= request.page
+        end
+
+        def validate_order!(rel)
+          present_order = rel.order_values.map { |val| [val.expr.name.to_sym, val.direction] }.last(2).to_h
+
+          unless page.order_by == present_order
+            raise ArgumentError, "Page's order_by does not match the relation's order: #{present_order} vs #{page.order_by}"
+          end
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/pagination/keyset/request_context.rb b/lib/gitlab/pagination/keyset/request_context.rb
new file mode 100644
index 00000000000..aeaed7587b3
--- /dev/null
+++ b/lib/gitlab/pagination/keyset/request_context.rb
@@ -0,0 +1,89 @@
+# frozen_string_literal: true
+
+module Gitlab
+  module Pagination
+    module Keyset
+      class RequestContext
+        attr_reader :request
+
+        DEFAULT_SORT_DIRECTION = :desc
+        PRIMARY_KEY = :id
+
+        # A tie breaker is added as an additional order-by column
+        # to establish a well-defined order. We use the primary key
+        # column here.
+        TIE_BREAKER = { PRIMARY_KEY => DEFAULT_SORT_DIRECTION }.freeze
+
+        def initialize(request)
+          @request = request
+        end
+
+        # extracts Paging information from request parameters
+        def page
+          @page ||= Page.new(order_by: order_by, per_page: params[:per_page])
+        end
+
+        def apply_headers(next_page)
+          request.header('Links', pagination_links(next_page))
+        end
+
+        private
+
+        def order_by
+          return TIE_BREAKER.dup unless params[:order_by]
+
+          order_by = { params[:order_by].to_sym => params[:sort]&.to_sym || DEFAULT_SORT_DIRECTION }
+
+          # Order by an additional unique key, we use the primary key here
+          order_by = order_by.merge(TIE_BREAKER) unless order_by[PRIMARY_KEY]
+
+          order_by
+        end
+
+        def params
+          @params ||= request.params
+        end
+
+        def lower_bounds_params(page)
+          page.lower_bounds.each_with_object({}) do |(column, value), params|
+            filter = filter_with_comparator(page, column)
+            params[filter] = value
+          end
+        end
+
+        def filter_with_comparator(page, column)
+          direction = page.order_by[column]
+
+          if direction&.to_sym == :desc
+            "#{column}_before"
+          else
+            "#{column}_after"
+          end
+        end
+
+        def page_href(page)
+          base_request_uri.tap do |uri|
+            uri.query = query_params_for(page).to_query
+          end.to_s
+        end
+
+        def pagination_links(next_page)
+          return if next_page.end_reached?
+
+          %(<#{page_href(next_page)}>; rel="next")
+        end
+
+        def base_request_uri
+          @base_request_uri ||= URI.parse(request.request.url).tap do |uri|
+            uri.host = Gitlab.config.gitlab.host
+            uri.port = Gitlab.config.gitlab.port
+          end
+        end
+
+        def query_params_for(page)
+          request.params.merge(lower_bounds_params(page))
+        end
+      end
+    end
+  end
+end