Move merging of Hashes out of the `GroupDescendant` concern

Since it can technically merge any hash with objects that respond to `==`

3 files changed, 154 insertions, 53 deletions

diff --git a/app/models/concerns/group_descendant.rb b/app/models/concerns/group_descendant.rb
index 11f092db2ae..6c465079753 100644
--- a/app/models/concerns/group_descendant.rb
+++ b/app/models/concerns/group_descendant.rb
@@ -5,22 +5,18 @@ module GroupDescendant
   end
 
   def self.build_hierarchy(descendants, hierarchy_top = nil)
-    descendants = Array.wrap(descendants)
+    descendants = Array.wrap(descendants).uniq
     return [] if descendants.empty?
 
     unless descendants.all? { |hierarchy| hierarchy.is_a?(GroupDescendant) }
       raise ArgumentError.new('element is not a hierarchy')
     end
 
-    first_descendant, *other_descendants = descendants
-    merged = first_descendant.hierarchy(hierarchy_top, descendants)
-
-    other_descendants.each do |descendant|
-      next_descendant = descendant.hierarchy(hierarchy_top, descendants)
-      merged = merge_hash_tree(merged, next_descendant)
+    all_hierarchies = descendants.map do |descendant|
+      descendant.hierarchy(hierarchy_top, descendants)
     end
 
-    merged
+    Gitlab::Utils::MergeHash.merge(all_hierarchies)
   end
 
   private
@@ -50,49 +46,4 @@ module GroupDescendant
       hierarchy
     end
   end
-
-  private_class_method def self.merge_hash_tree(first_child, second_child)
-    # 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]
-    if first_child.is_a?(Array) && second_child.is_a?(Hash)
-      merge_hash_into_array(first_child, second_child)
-    elsif first_child.is_a?(Hash) && second_child.is_a?(Array)
-      merge_hash_into_array(second_child, first_child)
-    # If both of them are hashes, we can deep_merge with the same logic
-    #
-    # Handled cases:
-    # [Hash, Hash]
-    elsif first_child.is_a?(Hash) && second_child.is_a?(Hash)
-      first_child.deep_merge(second_child) { |key, first, second| merge_hash_tree(first, second) }
-    # If only one of them is a hash, and one of them is a GroupHierachy-object
-    # we can check if its already in the hash. If so, we don't need to do anything
-    #
-    # Handled cases
-    # [Hash, GroupDescendant]
-    elsif first_child.is_a?(Hash) && first_child.keys.include?(second_child)
-      first_child
-    elsif second_child.is_a?(Hash) && second_child.keys.include?(first_child)
-      second_child
-    # If one or both elements are a GroupDescendant, we wrap create an array
-    # combining them.
-    #
-    # Handled cases:
-    # [GroupDescendant, Array], [GroupDescendant, GroupDescendant], [Array, Array]
-    else
-      Array.wrap(first_child) + Array.wrap(second_child)
-    end
-  end
-
-  private_class_method def self.merge_hash_into_array(array, new_hash)
-    if mergeable_index = array.index { |element| element.is_a?(Hash) && (element.keys & new_hash.keys).any? }
-      array[mergeable_index] = merge_hash_tree(array[mergeable_index], new_hash)
-    else
-      array << new_hash
-    end
-
-    array
-  end
 end
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
diff --git a/spec/lib/gitlab/utils/merge_hash_spec.rb b/spec/lib/gitlab/utils/merge_hash_spec.rb
new file mode 100644
index 00000000000..4fa7bb31301
--- /dev/null
+++ b/spec/lib/gitlab/utils/merge_hash_spec.rb
@@ -0,0 +1,33 @@
+require 'spec_helper'
+describe Gitlab::Utils::MergeHash do
+  describe '.crush' do
+    it 'can flatten a hash to each element' do
+      input = { hello: "world", this: { crushes: ["an entire", "hash"] } }
+      expected_result = [:hello, "world", :this, :crushes, "an entire", "hash"]
+
+      expect(described_class.crush(input)).to eq(expected_result)
+    end
+  end
+
+  describe '.elements' do
+    it 'deep merges an array of elements' do
+      input = [{ hello: ["world"] },
+               { hello: "Everyone" },
+               { hello: { greetings: ['Bonjour', 'Hello', 'Hallo', 'Dzień dobry'] } },
+               "Goodbye", "Hallo"]
+      expected_output = [
+        {
+          hello:
+            [
+              "world",
+              "Everyone",
+              { greetings: ['Bonjour', 'Hello', 'Hallo', 'Dzień dobry'] }
+            ]
+        },
+        "Goodbye"
+      ]
+
+      expect(described_class.merge(input)).to eq(expected_output)
+    end
+  end
+end