Merge branch 'bvl-group-trees' into 'master'

Show collapsible tree on the project show page

Closes #30343

See merge request gitlab-org/gitlab-ce!14055

5 files changed, 209 insertions, 6 deletions

diff --git a/lib/gitlab/group_hierarchy.rb b/lib/gitlab/group_hierarchy.rb
index 635f52131f9..42ded7c286f 100644
--- a/lib/gitlab/group_hierarchy.rb
+++ b/lib/gitlab/group_hierarchy.rb
@@ -17,12 +17,32 @@ module Gitlab
       @model = ancestors_base.model
     end
 
+    # Returns the set of descendants of a given relation, but excluding the given
+    # relation
+    def descendants
+      base_and_descendants.where.not(id: descendants_base.select(:id))
+    end
+
+    # Returns the set of ancestors of a given relation, but excluding the given
+    # relation
+    #
+    # Passing an `upto` will stop the recursion once the specified parent_id is
+    # reached. So all ancestors *lower* than the specified ancestor will be
+    # included.
+    def ancestors(upto: nil)
+      base_and_ancestors(upto: upto).where.not(id: ancestors_base.select(:id))
+    end
+
     # Returns a relation that includes the ancestors_base set of groups
     # and all their ancestors (recursively).
-    def base_and_ancestors
+    #
+    # Passing an `upto` will stop the recursion once the specified parent_id is
+    # reached. So all ancestors *lower* than the specified acestor will be
+    # included.
+    def base_and_ancestors(upto: nil)
       return ancestors_base unless Group.supports_nested_groups?
 
-      read_only(base_and_ancestors_cte.apply_to(model.all))
+      read_only(base_and_ancestors_cte(upto).apply_to(model.all))
     end
 
     # Returns a relation that includes the descendants_base set of groups
@@ -78,17 +98,19 @@ module Gitlab
 
     private
 
-    def base_and_ancestors_cte
+    def base_and_ancestors_cte(stop_id = nil)
       cte = SQL::RecursiveCTE.new(:base_and_ancestors)
 
       cte << ancestors_base.except(:order)
 
       # Recursively get all the ancestors of the base set.
-      cte << model
+      parent_query = model
         .from([groups_table, cte.table])
         .where(groups_table[:id].eq(cte.table[:parent_id]))
         .except(:order)
+      parent_query = parent_query.where(cte.table[:parent_id].not_eq(stop_id)) if stop_id
 
+      cte << parent_query
       cte
     end
 
diff --git a/lib/gitlab/multi_collection_paginator.rb b/lib/gitlab/multi_collection_paginator.rb
new file mode 100644
index 00000000000..eb3c9002710
--- /dev/null
+++ b/lib/gitlab/multi_collection_paginator.rb
@@ -0,0 +1,61 @@
+module Gitlab
+  class MultiCollectionPaginator
+    attr_reader :first_collection, :second_collection, :per_page
+
+    def initialize(*collections, per_page: nil)
+      raise ArgumentError.new('Only 2 collections are supported') if collections.size != 2
+
+      @per_page = per_page || Kaminari.config.default_per_page
+      @first_collection, @second_collection = collections
+    end
+
+    def paginate(page)
+      page = page.to_i
+      paginated_first_collection(page) + paginated_second_collection(page)
+    end
+
+    def total_count
+      @total_count ||= first_collection.size + second_collection.size
+    end
+
+    private
+
+    def paginated_first_collection(page)
+      @first_collection_pages ||= Hash.new do |hash, page|
+        hash[page] = first_collection.page(page).per(per_page)
+      end
+
+      @first_collection_pages[page]
+    end
+
+    def paginated_second_collection(page)
+      @second_collection_pages ||= Hash.new do |hash, page|
+        second_collection_page = page - first_collection_page_count
+
+        offset = if second_collection_page < 1 || first_collection_page_count.zero?
+                   0
+                 else
+                   per_page - first_collection_last_page_size
+                 end
+        hash[page] = second_collection.page(second_collection_page)
+                       .per(per_page - paginated_first_collection(page).size)
+                       .padding(offset)
+      end
+
+      @second_collection_pages[page]
+    end
+
+    def first_collection_page_count
+      return @first_collection_page_count if defined?(@first_collection_page_count)
+
+      first_collection_page = paginated_first_collection(0)
+      @first_collection_page_count = first_collection_page.total_pages
+    end
+
+    def first_collection_last_page_size
+      return @first_collection_last_page_size if defined?(@first_collection_last_page_size)
+
+      @first_collection_last_page_size = paginated_first_collection(first_collection_page_count).count
+    end
+  end
+end
diff --git a/lib/gitlab/path_regex.rb b/lib/gitlab/path_regex.rb
index 894bd5efae5..22f8dd669d0 100644
--- a/lib/gitlab/path_regex.rb
+++ b/lib/gitlab/path_regex.rb
@@ -128,7 +128,6 @@ module Gitlab
       notification_setting
       pipeline_quota
       projects
-      subgroups
     ].freeze
 
     ILLEGAL_PROJECT_PATH_WORDS = PROJECT_WILDCARD_ROUTES
diff --git a/lib/gitlab/sql/union.rb b/lib/gitlab/sql/union.rb
index f30c771837a..c99b262f1ca 100644
--- a/lib/gitlab/sql/union.rb
+++ b/lib/gitlab/sql/union.rb
@@ -26,7 +26,11 @@ module Gitlab
           @relations.map { |rel| rel.reorder(nil).to_sql }.reject(&:blank?)
         end
 
-        fragments.join("\n#{union_keyword}\n")
+        if fragments.any?
+          fragments.join("\n#{union_keyword}\n")
+        else
+          'NULL'
+        end
       end
 
       def union_keyword
diff --git a/lib/gitlab/utils/merge_hash.rb b/lib/gitlab/utils/merge_hash.rb
new file mode 100644
index 00000000000..385141d44d0
--- /dev/null
+++ b/lib/gitlab/utils/merge_hash.rb
@@ -0,0 +1,117 @@
+module Gitlab
+  module Utils
+    module MergeHash
+      extend self
+      # Deep merges an array of hashes
+      #
+      # [{ hello: ["world"] },
+      #  { hello: "Everyone" },
+      #  { hello: { greetings: ['Bonjour', 'Hello', 'Hallo', 'Dzien dobry'] } },
+      #   "Goodbye", "Hallo"]
+      # =>  [
+      #       {
+      #         hello:
+      #           [
+      #             "world",
+      #             "Everyone",
+      #             { greetings: ['Bonjour', 'Hello', 'Hallo', 'Dzien dobry'] }
+      #           ]
+      #       },
+      #       "Goodbye"
+      #     ]
+      def merge(elements)
+        merged, *other_elements = elements
+
+        other_elements.each do |element|
+          merged = merge_hash_tree(merged, element)
+        end
+
+        merged
+      end
+
+      # This extracts all keys and values from a hash into an array
+      #
+      # { hello: "world", this: { crushes: ["an entire", "hash"] } }
+      # => [:hello, "world", :this, :crushes, "an entire", "hash"]
+      def crush(array_or_hash)
+        if array_or_hash.is_a?(Array)
+          crush_array(array_or_hash)
+        else
+          crush_hash(array_or_hash)
+        end
+      end
+
+      private
+
+      def merge_hash_into_array(array, new_hash)
+        crushed_new_hash = crush_hash(new_hash)
+        # Merge the hash into an existing element of the array if there is overlap
+        if mergeable_index = array.index { |element| crushable?(element) && (crush(element) & crushed_new_hash).any? }
+          array[mergeable_index] = merge_hash_tree(array[mergeable_index], new_hash)
+        else
+          array << new_hash
+        end
+
+        array
+      end
+
+      def merge_hash_tree(first_element, second_element)
+        # If one of the elements is an object, and the other is a Hash or Array
+        # we can check if the object is already included. If so, we don't need to do anything
+        #
+        # Handled cases
+        # [Hash, Object], [Array, Object]
+        if crushable?(first_element) && crush(first_element).include?(second_element)
+          first_element
+        elsif crushable?(second_element) && crush(second_element).include?(first_element)
+          second_element
+        # When the first is an array, we need to go over every element to see if
+        # we can merge deeper. If no match is found, we add the element to the array
+        #
+        # Handled cases:
+        # [Array, Hash]
+        elsif first_element.is_a?(Array) && second_element.is_a?(Hash)
+          merge_hash_into_array(first_element, second_element)
+        elsif first_element.is_a?(Hash) && second_element.is_a?(Array)
+          merge_hash_into_array(second_element, first_element)
+        # If both of them are hashes, we can deep_merge with the same logic
+        #
+        # Handled cases:
+        # [Hash, Hash]
+        elsif first_element.is_a?(Hash) && second_element.is_a?(Hash)
+          first_element.deep_merge(second_element) { |key, first, second| merge_hash_tree(first, second) }
+        # If both elements are arrays, we try to merge each element separatly
+        #
+        # Handled cases
+        # [Array, Array]
+        elsif first_element.is_a?(Array) && second_element.is_a?(Array)
+          first_element.map { |child_element| merge_hash_tree(child_element, second_element) }
+        # If one or both elements are a GroupDescendant, we wrap create an array
+        # combining them.
+        #
+        # Handled cases:
+        # [Object, Object], [Array, Array]
+        else
+          (Array.wrap(first_element) + Array.wrap(second_element)).uniq
+        end
+      end
+
+      def crushable?(element)
+        element.is_a?(Hash) || element.is_a?(Array)
+      end
+
+      def crush_hash(hash)
+        hash.flat_map do |key, value|
+          crushed_value = crushable?(value) ? crush(value) : value
+          Array.wrap(key) + Array.wrap(crushed_value)
+        end
+      end
+
+      def crush_array(array)
+        array.flat_map do |element|
+          crushable?(element) ? crush(element) : element
+        end
+      end
+    end
+  end
+end