Add latest changes from gitlab-org/gitlab@14-5-stable-eev14.5.0-rc42

5 files changed, 88 insertions, 22 deletions

diff --git a/app/models/namespaces/project_namespace.rb b/app/models/namespaces/project_namespace.rb
index d1806c1c088..22ec550dee2 100644
--- a/app/models/namespaces/project_namespace.rb
+++ b/app/models/namespaces/project_namespace.rb
@@ -4,8 +4,6 @@ module Namespaces
   class ProjectNamespace < Namespace
     has_one :project, foreign_key: :project_namespace_id, inverse_of: :project_namespace
 
-    validates :project, presence: true
-
     def self.sti_name
       'Project'
     end
diff --git a/app/models/namespaces/traversal/linear.rb b/app/models/namespaces/traversal/linear.rb
index d7130322ed1..1736fe82ca5 100644
--- a/app/models/namespaces/traversal/linear.rb
+++ b/app/models/namespaces/traversal/linear.rb
@@ -161,7 +161,7 @@ module Namespaces
       def lineage(top: nil, bottom: nil, hierarchy_order: nil)
         raise UnboundedSearch, 'Must bound search by either top or bottom' unless top || bottom
 
-        skope = self.class.without_sti_condition
+        skope = self.class
 
         if top
           skope = skope.where("traversal_ids @> ('{?}')", top.id)
@@ -181,7 +181,6 @@ module Namespaces
           # standard SELECT to avoid mismatched attribute errors when trying to
           # chain future ActiveRelation commands, and retain the ordering.
           skope = self.class
-            .without_sti_condition
             .from(skope, self.class.table_name)
             .select(skope.arel_table[Arel.star])
             .order(depth: hierarchy_order)
diff --git a/app/models/namespaces/traversal/linear_scopes.rb b/app/models/namespaces/traversal/linear_scopes.rb
index 2da0e48c2da..f5c44171c42 100644
--- a/app/models/namespaces/traversal/linear_scopes.rb
+++ b/app/models/namespaces/traversal/linear_scopes.rb
@@ -15,12 +15,18 @@ module Namespaces
           select('namespaces.traversal_ids[array_length(namespaces.traversal_ids, 1)] AS id')
         end
 
+        def roots
+          return super unless use_traversal_ids_roots?
+
+          root_ids = all.select("#{quoted_table_name}.traversal_ids[1]").distinct
+          unscoped.where(id: root_ids)
+        end
+
         def self_and_ancestors(include_self: true, hierarchy_order: nil)
           return super unless use_traversal_ids_for_ancestor_scopes?
 
           records = unscoped
-            .without_sti_condition
-            .where(id: without_sti_condition.select('unnest(traversal_ids)'))
+            .where(id: select('unnest(traversal_ids)'))
             .order_by_depth(hierarchy_order)
             .normal_select
 
@@ -40,24 +46,24 @@ module Namespaces
         def self_and_descendants(include_self: true)
           return super unless use_traversal_ids?
 
-          records = self_and_descendants_with_duplicates(include_self: include_self)
-
-          distinct = records.select('DISTINCT on(namespaces.id) namespaces.*')
-
-          distinct.normal_select
+          if Feature.enabled?(:traversal_ids_btree, default_enabled: :yaml)
+            self_and_descendants_with_comparison_operators(include_self: include_self)
+          else
+            records = self_and_descendants_with_duplicates_with_array_operator(include_self: include_self)
+            distinct = records.select('DISTINCT on(namespaces.id) namespaces.*')
+            distinct.normal_select
+          end
         end
 
         def self_and_descendant_ids(include_self: true)
           return super unless use_traversal_ids?
 
-          self_and_descendants_with_duplicates(include_self: include_self)
-            .select('DISTINCT namespaces.id')
-        end
-
-        # Make sure we drop the STI `type = 'Group'` condition for better performance.
-        # Logically equivalent so long as hierarchies remain homogeneous.
-        def without_sti_condition
-          unscope(where: :type)
+          if Feature.enabled?(:traversal_ids_btree, default_enabled: :yaml)
+            self_and_descendants_with_comparison_operators(include_self: include_self).as_ids
+          else
+            self_and_descendants_with_duplicates_with_array_operator(include_self: include_self)
+              .select('DISTINCT namespaces.id')
+          end
         end
 
         def order_by_depth(hierarchy_order)
@@ -75,7 +81,7 @@ module Namespaces
         # When we have queries that break this SELECT * format we can run in to errors.
         # For example `SELECT DISTINCT on(...)` will fail when we chain a `.count` c
         def normal_select
-          unscoped.without_sti_condition.from(all, :namespaces)
+          unscoped.from(all, :namespaces)
         end
 
         private
@@ -84,16 +90,52 @@ module Namespaces
           Feature.enabled?(:use_traversal_ids, default_enabled: :yaml)
         end
 
+        def use_traversal_ids_roots?
+          Feature.enabled?(:use_traversal_ids_roots, default_enabled: :yaml) &&
+          use_traversal_ids?
+        end
+
         def use_traversal_ids_for_ancestor_scopes?
           Feature.enabled?(:use_traversal_ids_for_ancestor_scopes, default_enabled: :yaml) &&
           use_traversal_ids?
         end
 
-        def self_and_descendants_with_duplicates(include_self: true)
+        def self_and_descendants_with_comparison_operators(include_self: true)
+          base = all.select(
+            :traversal_ids,
+            'LEAD (namespaces.traversal_ids, 1) OVER (ORDER BY namespaces.traversal_ids ASC) next_traversal_ids'
+          )
+          cte = Gitlab::SQL::CTE.new(:base_cte, base)
+
+          namespaces = Arel::Table.new(:namespaces)
+          records = unscoped
+            .with(cte.to_arel)
+            .from([cte.table, namespaces])
+
+          # Bound the search space to ourselves (optional) and descendants.
+          #
+          # WHERE (base_cte.next_traversal_ids IS NULL OR base_cte.next_traversal_ids > namespaces.traversal_ids)
+          #   AND next_traversal_ids_sibling(base_cte.traversal_ids) > namespaces.traversal_ids
+          records = records
+            .where(cte.table[:next_traversal_ids].eq(nil).or(cte.table[:next_traversal_ids].gt(namespaces[:traversal_ids])))
+            .where(next_sibling_func(cte.table[:traversal_ids]).gt(namespaces[:traversal_ids]))
+
+          #   AND base_cte.traversal_ids <= namespaces.traversal_ids
+          if include_self
+            records.where(cte.table[:traversal_ids].lteq(namespaces[:traversal_ids]))
+          else
+            records.where(cte.table[:traversal_ids].lt(namespaces[:traversal_ids]))
+          end
+        end
+
+        def next_sibling_func(*args)
+          Arel::Nodes::NamedFunction.new('next_traversal_ids_sibling', args)
+        end
+
+        def self_and_descendants_with_duplicates_with_array_operator(include_self: true)
           base_ids = select(:id)
 
           records = unscoped
-            .without_sti_condition
             .from("namespaces, (#{base_ids.to_sql}) base")
             .where('namespaces.traversal_ids @> ARRAY[base.id]')
 
diff --git a/app/models/namespaces/traversal/recursive_scopes.rb b/app/models/namespaces/traversal/recursive_scopes.rb
index 6659cefe095..925d9b8bb0c 100644
--- a/app/models/namespaces/traversal/recursive_scopes.rb
+++ b/app/models/namespaces/traversal/recursive_scopes.rb
@@ -10,6 +10,13 @@ module Namespaces
           select('id')
         end
 
+        def roots
+          Gitlab::ObjectHierarchy
+            .new(all)
+            .base_and_ancestors
+            .where(namespaces: { parent_id: nil })
+        end
+
         def self_and_ancestors(include_self: true, hierarchy_order: nil)
           records = Gitlab::ObjectHierarchy.new(all).base_and_ancestors(hierarchy_order: hierarchy_order)
 
diff --git a/app/models/namespaces/user_namespace.rb b/app/models/namespaces/user_namespace.rb
index 22b7a0a3b2b..d4d7d352e71 100644
--- a/app/models/namespaces/user_namespace.rb
+++ b/app/models/namespaces/user_namespace.rb
@@ -3,6 +3,26 @@
 # TODO: currently not created/mapped in the database, will be done in another issue
 #       https://gitlab.com/gitlab-org/gitlab/-/issues/341070
 module Namespaces
+  ####################################################################
+  # PLEASE DO NOT OVERRIDE METHODS IN THIS CLASS!
+  #
+  # This class is a placeholder for STI. But we also want to ensure
+  # tests using `:namespace` factory are still testing the same functionality.
+  #
+  # Many legacy tests use `:namespace` which has a slight semantic
+  # mismatch as it always has been a User (personal) namespace.
+  #
+  # If you need to make a change here, please ping the
+  # Manage/Workspaces group so we can ensure that the
+  # changes do not break existing functionality.
+  #
+  # As Namespaces evolve we may be able to relax this restriction
+  # but for now, please check in with us <3
+  #
+  # For details, see the discussion in
+  # https://gitlab.com/gitlab-org/gitlab/-/merge_requests/74152
+  ####################################################################
+
   class UserNamespace < Namespace
     def self.sti_name
       'User'