Merge branch 'master' into sh-security-fix-backports-master

16 files changed, 283 insertions, 53 deletions

diff --git a/lib/api/api.rb b/lib/api/api.rb
index 79e55a2f4f7..99fcc59ba04 100644
--- a/lib/api/api.rb
+++ b/lib/api/api.rb
@@ -4,6 +4,10 @@ module API
 
     LOG_FILENAME = Rails.root.join("log", "api_json.log")
 
+    NO_SLASH_URL_PART_REGEX = %r{[^/]+}
+    PROJECT_ENDPOINT_REQUIREMENTS = { id: NO_SLASH_URL_PART_REGEX }.freeze
+    COMMIT_ENDPOINT_REQUIREMENTS = PROJECT_ENDPOINT_REQUIREMENTS.merge(sha: NO_SLASH_URL_PART_REGEX).freeze
+
     use GrapeLogging::Middleware::RequestLogger,
         logger: Logger.new(LOG_FILENAME),
         formatter: Gitlab::GrapeLogging::Formatters::LogrageWithTimestamp.new,
@@ -96,9 +100,6 @@ module API
     helpers ::API::Helpers
     helpers ::API::Helpers::CommonHelpers
 
-    NO_SLASH_URL_PART_REGEX = %r{[^/]+}
-    PROJECT_ENDPOINT_REQUIREMENTS = { id: NO_SLASH_URL_PART_REGEX }.freeze
-
     # Keep in alphabetical order
     mount ::API::AccessRequests
     mount ::API::AwardEmoji
diff --git a/lib/api/commits.rb b/lib/api/commits.rb
index 62565e2d522..2685dc27252 100644
--- a/lib/api/commits.rb
+++ b/lib/api/commits.rb
@@ -4,8 +4,6 @@ module API
   class Commits < Grape::API
     include PaginationParams
 
-    COMMIT_ENDPOINT_REQUIREMENTS = API::PROJECT_ENDPOINT_REQUIREMENTS.merge(sha: API::NO_SLASH_URL_PART_REGEX)
-
     before { authorize! :download_code, user_project }
 
     params do
@@ -85,7 +83,7 @@ module API
       params do
         requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
       end
-      get ':id/repository/commits/:sha', requirements: COMMIT_ENDPOINT_REQUIREMENTS do
+      get ':id/repository/commits/:sha', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
         commit = user_project.commit(params[:sha])
 
         not_found! 'Commit' unless commit
@@ -99,7 +97,7 @@ module API
       params do
         requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
       end
-      get ':id/repository/commits/:sha/diff', requirements: COMMIT_ENDPOINT_REQUIREMENTS do
+      get ':id/repository/commits/:sha/diff', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
         commit = user_project.commit(params[:sha])
 
         not_found! 'Commit' unless commit
@@ -115,7 +113,7 @@ module API
         use :pagination
         requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
       end
-      get ':id/repository/commits/:sha/comments', requirements: COMMIT_ENDPOINT_REQUIREMENTS do
+      get ':id/repository/commits/:sha/comments', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
         commit = user_project.commit(params[:sha])
 
         not_found! 'Commit' unless commit
@@ -132,7 +130,7 @@ module API
         requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag to be cherry picked'
         requires :branch, type: String, desc: 'The name of the branch'
       end
-      post ':id/repository/commits/:sha/cherry_pick', requirements: COMMIT_ENDPOINT_REQUIREMENTS do
+      post ':id/repository/commits/:sha/cherry_pick', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
         authorize! :push_code, user_project
 
         commit = user_project.commit(params[:sha])
@@ -169,7 +167,7 @@ module API
           requires :line_type, type: String, values: %w(new old), default: 'new', desc: 'The type of the line'
         end
       end
-      post ':id/repository/commits/:sha/comments', requirements: COMMIT_ENDPOINT_REQUIREMENTS do
+      post ':id/repository/commits/:sha/comments', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
         commit = user_project.commit(params[:sha])
         not_found! 'Commit' unless commit
 
diff --git a/lib/api/repositories.rb b/lib/api/repositories.rb
index ceee3226732..7887b886c03 100644
--- a/lib/api/repositories.rb
+++ b/lib/api/repositories.rb
@@ -57,7 +57,7 @@ module API
 
       desc 'Get raw blob contents from the repository'
       params do
-        requires :sha, type: String, desc: 'The commit, branch name, or tag name'
+        requires :sha, type: String, desc: 'The commit hash'
       end
       get ':id/repository/blobs/:sha/raw' do
         assign_blob_vars!
@@ -67,7 +67,7 @@ module API
 
       desc 'Get a blob from the repository'
       params do
-        requires :sha, type: String, desc: 'The commit, branch name, or tag name'
+        requires :sha, type: String, desc: 'The commit hash'
       end
       get ':id/repository/blobs/:sha' do
         assign_blob_vars!
diff --git a/lib/api/v3/builds.rb b/lib/api/v3/builds.rb
index c189d486f50..f493fd7c7ec 100644
--- a/lib/api/v3/builds.rb
+++ b/lib/api/v3/builds.rb
@@ -8,7 +8,7 @@ module API
       params do
         requires :id, type: String, desc: 'The ID of a project'
       end
-      resource :projects do
+      resource :projects, requirements: API::PROJECT_ENDPOINT_REQUIREMENTS do
         helpers do
           params :optional_scope do
             optional :scope, types: [String, Array[String]], desc: 'The scope of builds to show',
diff --git a/lib/api/v3/commits.rb b/lib/api/v3/commits.rb
index bd5c6b34d12..ed206a6def0 100644
--- a/lib/api/v3/commits.rb
+++ b/lib/api/v3/commits.rb
@@ -11,7 +11,7 @@ module API
       params do
         requires :id, type: String, desc: 'The ID of a project'
       end
-      resource :projects, requirements: { id: %r{[^/]+} } do
+      resource :projects, requirements: API::PROJECT_ENDPOINT_REQUIREMENTS do
         desc 'Get a project repository commits' do
           success ::API::Entities::Commit
         end
@@ -72,7 +72,7 @@ module API
         params do
           requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
         end
-        get ":id/repository/commits/:sha" do
+        get ":id/repository/commits/:sha", requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           commit = user_project.commit(params[:sha])
 
           not_found! "Commit" unless commit
@@ -86,7 +86,7 @@ module API
         params do
           requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
         end
-        get ":id/repository/commits/:sha/diff" do
+        get ":id/repository/commits/:sha/diff", requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           commit = user_project.commit(params[:sha])
 
           not_found! "Commit" unless commit
@@ -102,7 +102,7 @@ module API
           use :pagination
           requires :sha, type: String, desc: 'A commit sha, or the name of a branch or tag'
         end
-        get ':id/repository/commits/:sha/comments' do
+        get ':id/repository/commits/:sha/comments', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           commit = user_project.commit(params[:sha])
 
           not_found! 'Commit' unless commit
@@ -119,7 +119,7 @@ module API
           requires :sha, type: String, desc: 'A commit sha to be cherry picked'
           requires :branch, type: String, desc: 'The name of the branch'
         end
-        post ':id/repository/commits/:sha/cherry_pick' do
+        post ':id/repository/commits/:sha/cherry_pick', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           authorize! :push_code, user_project
 
           commit = user_project.commit(params[:sha])
@@ -156,7 +156,7 @@ module API
             requires :line_type, type: String, values: %w(new old), default: 'new', desc: 'The type of the line'
           end
         end
-        post ':id/repository/commits/:sha/comments' do
+        post ':id/repository/commits/:sha/comments', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           commit = user_project.commit(params[:sha])
           not_found! 'Commit' unless commit
 
diff --git a/lib/api/v3/repositories.rb b/lib/api/v3/repositories.rb
index 41a7c6b83ae..f9a47101e27 100644
--- a/lib/api/v3/repositories.rb
+++ b/lib/api/v3/repositories.rb
@@ -8,7 +8,7 @@ module API
       params do
         requires :id, type: String, desc: 'The ID of a project'
       end
-      resource :projects, requirements: { id: %r{[^/]+} } do
+      resource :projects, requirements: API::PROJECT_ENDPOINT_REQUIREMENTS do
         helpers do
           def handle_project_member_errors(errors)
             if errors[:project_access].any?
@@ -43,7 +43,7 @@ module API
           requires :sha, type: String, desc: 'The commit, branch name, or tag name'
           requires :filepath, type: String, desc: 'The path to the file to display'
         end
-        get [":id/repository/blobs/:sha", ":id/repository/commits/:sha/blob"] do
+        get [":id/repository/blobs/:sha", ":id/repository/commits/:sha/blob"], requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           repo = user_project.repository
           commit = repo.commit(params[:sha])
           not_found! "Commit" unless commit
@@ -56,7 +56,7 @@ module API
         params do
           requires :sha, type: String, desc: 'The commit, branch name, or tag name'
         end
-        get ':id/repository/raw_blobs/:sha' do
+        get ':id/repository/raw_blobs/:sha', requirements: API::COMMIT_ENDPOINT_REQUIREMENTS do
           repo = user_project.repository
           begin
             blob = Gitlab::Git::Blob.raw(repo, params[:sha])
diff --git a/lib/gitlab/background_migration/deserialize_merge_request_diffs_and_commits.rb b/lib/gitlab/background_migration/deserialize_merge_request_diffs_and_commits.rb
index 8e5c95f2287..380802258f5 100644
--- a/lib/gitlab/background_migration/deserialize_merge_request_diffs_and_commits.rb
+++ b/lib/gitlab/background_migration/deserialize_merge_request_diffs_and_commits.rb
@@ -81,6 +81,7 @@ module Gitlab
       def single_diff_rows(merge_request_diff)
         sha_attribute = Gitlab::Database::ShaAttribute.new
         commits = YAML.load(merge_request_diff.st_commits) rescue []
+        commits ||= []
 
         commit_rows = commits.map.with_index do |commit, index|
           commit_hash = commit.to_hash.with_indifferent_access.except(:parent_ids)
diff --git a/lib/gitlab/git/storage/circuit_breaker.rb b/lib/gitlab/git/storage/circuit_breaker.rb
index 1eaa2d83fb6..0456ad9a1f3 100644
--- a/lib/gitlab/git/storage/circuit_breaker.rb
+++ b/lib/gitlab/git/storage/circuit_breaker.rb
@@ -2,15 +2,13 @@ module Gitlab
   module Git
     module Storage
       class CircuitBreaker
+        include CircuitBreakerSettings
+
         FailureInfo = Struct.new(:last_failure, :failure_count)
 
         attr_reader :storage,
                     :hostname,
-                    :storage_path,
-                    :failure_count_threshold,
-                    :failure_wait_time,
-                    :failure_reset_time,
-                    :storage_timeout
+                    :storage_path
 
         delegate :last_failure, :failure_count, to: :failure_info
 
@@ -18,7 +16,7 @@ module Gitlab
           pattern = "#{Gitlab::Git::Storage::REDIS_KEY_PREFIX}*"
 
           Gitlab::Git::Storage.redis.with do |redis|
-            all_storage_keys = redis.keys(pattern)
+            all_storage_keys = redis.scan_each(match: pattern).to_a
             redis.del(*all_storage_keys) unless all_storage_keys.empty?
           end
 
@@ -53,10 +51,6 @@ module Gitlab
 
           config = Gitlab.config.repositories.storages[@storage]
           @storage_path = config['path']
-          @failure_count_threshold = config['failure_count_threshold']
-          @failure_wait_time = config['failure_wait_time']
-          @failure_reset_time = config['failure_reset_time']
-          @storage_timeout = config['storage_timeout']
         end
 
         def perform
diff --git a/lib/gitlab/git/storage/circuit_breaker_settings.rb b/lib/gitlab/git/storage/circuit_breaker_settings.rb
new file mode 100644
index 00000000000..d2313fe7c1b
--- /dev/null
+++ b/lib/gitlab/git/storage/circuit_breaker_settings.rb
@@ -0,0 +1,29 @@
+module Gitlab
+  module Git
+    module Storage
+      module CircuitBreakerSettings
+        def failure_count_threshold
+          application_settings.circuitbreaker_failure_count_threshold
+        end
+
+        def failure_wait_time
+          application_settings.circuitbreaker_failure_wait_time
+        end
+
+        def failure_reset_time
+          application_settings.circuitbreaker_failure_reset_time
+        end
+
+        def storage_timeout
+          application_settings.circuitbreaker_storage_timeout
+        end
+
+        private
+
+        def application_settings
+          Gitlab::CurrentSettings.current_application_settings
+        end
+      end
+    end
+  end
+end
diff --git a/lib/gitlab/git/storage/health.rb b/lib/gitlab/git/storage/health.rb
index 1564e94b7f7..7049772fe3b 100644
--- a/lib/gitlab/git/storage/health.rb
+++ b/lib/gitlab/git/storage/health.rb
@@ -23,26 +23,36 @@ module Gitlab
           end
         end
 
-        def self.all_keys_for_storages(storage_names, redis)
+        private_class_method def self.all_keys_for_storages(storage_names, redis)
           keys_per_storage = {}
 
           redis.pipelined do
             storage_names.each do |storage_name|
               pattern = pattern_for_storage(storage_name)
+              matched_keys = redis.scan_each(match: pattern)
 
-              keys_per_storage[storage_name] = redis.keys(pattern)
+              keys_per_storage[storage_name] = matched_keys
             end
           end
 
-          keys_per_storage
+          # We need to make sure each lazy-loaded `Enumerator` for matched keys
+          # is loaded into an array.
+          #
+          # Otherwise it would be loaded in the second `Redis#pipelined` block
+          # within `.load_for_keys`. In this pipelined call, the active
+          # Redis-client changes again, so the values would not be available
+          # until the end of that pipelined-block.
+          keys_per_storage.each do |storage_name, key_future|
+            keys_per_storage[storage_name] = key_future.to_a
+          end
         end
 
-        def self.load_for_keys(keys_per_storage, redis)
+        private_class_method def self.load_for_keys(keys_per_storage, redis)
           info_for_keys = {}
 
           redis.pipelined do
             keys_per_storage.each do |storage_name, keys_future|
-              info_for_storage = keys_future.value.map do |key|
+              info_for_storage = keys_future.map do |key|
                 { name: key, failure_count: redis.hget(key, :failure_count) }
               end
 
diff --git a/lib/gitlab/git/storage/null_circuit_breaker.rb b/lib/gitlab/git/storage/null_circuit_breaker.rb
index 297c043d054..60c6791a7e4 100644
--- a/lib/gitlab/git/storage/null_circuit_breaker.rb
+++ b/lib/gitlab/git/storage/null_circuit_breaker.rb
@@ -2,15 +2,14 @@ module Gitlab
   module Git
     module Storage
       class NullCircuitBreaker
+        include CircuitBreakerSettings
+
         # These will have actual values
         attr_reader :storage,
                     :hostname
 
         # These will always have nil values
-        attr_reader :storage_path,
-                    :failure_wait_time,
-                    :failure_reset_time,
-                    :storage_timeout
+        attr_reader :storage_path
 
         def initialize(storage, hostname, error: nil)
           @storage = storage
@@ -26,16 +25,12 @@ module Gitlab
           !!@error
         end
 
-        def failure_count_threshold
-          1
-        end
-
         def last_failure
           circuit_broken? ? Time.now : nil
         end
 
         def failure_count
-          circuit_broken? ? 1 : 0
+          circuit_broken? ? failure_count_threshold : 0
         end
 
         def failure_info
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 7c02c9c5c48..22f8dd669d0 100644
--- a/lib/gitlab/path_regex.rb
+++ b/lib/gitlab/path_regex.rb
@@ -26,7 +26,6 @@ module Gitlab
       apple-touch-icon.png
       assets
       autocomplete
-      boards
       ci
       dashboard
       deploy.html
@@ -129,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