Prevent deep_merge from mutating nested hashes

The `DeepMerge` extension has two methods of mutating hashes: a
destructive one and a non-destructive one. The `#deep_merge` version
should not mutate the original hash or any hash nested within it. The
`#deep_merge!` version is free to mutate the receiver.

Without deeply duplicating the values contained within the hash, the
invariant of immutability cannot be held for the original hash. In order
to preserve that invariant, we need to introduce a method of deeply
duplicating the hash.

The trick here is that we cannot rely on a simple call to `Object#dup`.
Some classes within the Ruby standard library are not duplicable in
particular versions of Ruby. Newer versions of Ruby allow these classes
to be "duplicated" in a way that returns the original value. These
classes represent value objects, so it is safe to return the original
value ... unless the classes are monkey-patched, but that isn't
something we can protect against.

This implementation does a best-effort to deeply duplicate an entire
hash by relying on these value object classes being able to return
themselves without violating immutability.

4 files changed, 93 insertions, 6 deletions

diff --git a/CHANGELOG.md b/CHANGELOG.md
index 1408cb5..d4996d1 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -28,6 +28,7 @@ scheme are considered to be bugs.
 
 ### Fixed
 
+* [#467](https://github.com/intridea/hashie/pull/467): Fixed `DeepMerge#deep_merge` mutating nested values within the receiver - [@michaelherold](https://github.com/michaelherold).
 * Your contribution here.
 
 ### Security
diff --git a/lib/hashie/extensions/deep_merge.rb b/lib/hashie/extensions/deep_merge.rb
index 5363904..1890e8f 100644
--- a/lib/hashie/extensions/deep_merge.rb
+++ b/lib/hashie/extensions/deep_merge.rb
@@ -3,7 +3,7 @@ module Hashie
     module DeepMerge
       # Returns a new hash with +self+ and +other_hash+ merged recursively.
       def deep_merge(other_hash, &block)
-        copy = dup
+        copy = _deep_dup(self)
         copy.extend(Hashie::Extensions::DeepMerge) unless copy.respond_to?(:deep_merge!)
         copy.deep_merge!(other_hash, &block)
       end
@@ -18,6 +18,21 @@ module Hashie
 
       private
 
+      def _deep_dup(hash)
+        copy = hash.dup
+
+        copy.each do |key, value|
+          copy[key] =
+            if value.is_a?(::Hash)
+              _deep_dup(value)
+            else
+              Hashie::Utils.safe_dup(value)
+            end
+        end
+
+        copy
+      end
+
       def _recursive_merge(hash, other_hash, &block)
         other_hash.each do |k, v|
           hash[k] =
diff --git a/lib/hashie/utils.rb b/lib/hashie/utils.rb
index d8e05fe..5b55b9a 100644
--- a/lib/hashie/utils.rb
+++ b/lib/hashie/utils.rb
@@ -12,5 +12,33 @@ module Hashie
         "defined in #{bound_method.owner}"
       end
     end
+
+    # Duplicates a value or returns the value when it is not duplicable
+    #
+    # @api public
+    #
+    # @param value [Object] the value to safely duplicate
+    # @return [Object] the duplicated value
+    def self.safe_dup(value)
+      case value
+      when Complex, FalseClass, NilClass, Rational, Method, Symbol, TrueClass, *integer_classes
+        value
+      else
+        value.dup
+      end
+    end
+
+    # Lists the classes Ruby uses for integers
+    #
+    # @api private
+    # @return [Array<Class>]
+    def self.integer_classes
+      @integer_classes ||=
+        if const_defined?(:Fixnum)
+          [Fixnum, Bignum] # rubocop:disable Lint/UnifiedInteger
+        else
+          [Integer]
+        end
+    end
   end
 end
diff --git a/spec/hashie/extensions/deep_merge_spec.rb b/spec/hashie/extensions/deep_merge_spec.rb
index ab79ff6..4ff6c30 100644
--- a/spec/hashie/extensions/deep_merge_spec.rb
+++ b/spec/hashie/extensions/deep_merge_spec.rb
@@ -14,19 +14,62 @@ describe Hashie::Extensions::DeepMerge do
 
   context 'without &block' do
     let(:h1) do
-      subject.new.merge(a: 'a', a1: 42, b: 'b', c: { c1: 'c1', c2: { a: 'b' }, c3: { d1: 'd1' } })
+      subject.new.merge(
+        a: 'a',
+        a1: 42,
+        b: 'b',
+        c: { c1: 'c1', c2: { a: 'b' }, c3: { d1: 'd1' } },
+        d: nil,
+        d1: false,
+        d2: true,
+        d3: unbound_method,
+        d4: Complex(1),
+        d5: Rational(1)
+      )
     end
     let(:h2) { { a: 1, a1: 1, c: { c1: 2, c2: 'c2', c3: { d2: 'd2' } }, e: { e1: 1 } } }
+    let(:unbound_method) { method(:puts) }
     let(:expected_hash) do
-      { a: 1, a1: 1, b: 'b', c: { c1: 2, c2: 'c2', c3: { d1: 'd1', d2: 'd2' } }, e: { e1: 1 } }
+      {
+        a: 1,
+        a1: 1,
+        b: 'b',
+        c: { c1: 2, c2: 'c2', c3: { d1: 'd1', d2: 'd2' } },
+        d: nil,
+        d1: false,
+        d2: true,
+        d3: unbound_method,
+        d4: Complex(1),
+        d5: Rational(1),
+        e: { e1: 1 }
+      }
     end
 
-    it 'deep merges two hashes' do
-      expect(h1.deep_merge(h2)).to eq expected_hash
+    it 'deep merges two hashes without modifying them' do
+      result = h1.deep_merge(h2)
+
+      expect(result).to eq expected_hash
+      expect(h1).to(
+        eq(
+          a: 'a',
+          a1: 42,
+          b: 'b',
+          c: { c1: 'c1', c2: { a: 'b' }, c3: { d1: 'd1' } },
+          d: nil,
+          d1: false,
+          d2: true,
+          d3: unbound_method,
+          d4: Complex(1),
+          d5: Rational(1)
+        )
+      )
+      expect(h2).to eq(a: 1, a1: 1, c: { c1: 2, c2: 'c2', c3: { d2: 'd2' } }, e: { e1: 1 })
     end
 
     it 'deep merges another hash in place via bang method' do
-      h1.deep_merge!(h2)
+      result = h1.deep_merge!(h2)
+
+      expect(result).to eq expected_hash
       expect(h1).to eq expected_hash
     end