HashDiff
HashDiff is a ruby library to compute the smallest difference between two hashes.
Demo: HashDiff
Docs: Documentation
Why HashDiff?
Given two Hashes A and B, sometimes you face the question: what's the smallest modification that can be made to change A into B?
An algorithm that responds to this question has to do following:
- Generate a list of additions, deletions and changes, so that
A + ChangeSet = B
andB - ChangeSet = A
. - Compute recursively -- Arrays and Hashes may be nested arbitrarily in A or B.
- Compute the smallest change -- it should recognize similar child Hashes or child Arrays between A and B.
HashDiff answers the question above using an opinionated approach:
- Hash can be represented as a list of (dot-syntax-path, value) pairs. For example,
{a:[{c:2}]}
can be represented as["a[0].c", 2]
. - The change set can be represented using the dot-syntax representation. For example,
[['-', 'b.x', 3], ['~', 'b.z', 45, 30], ['+', 'b.y', 3]]
. - It compares Arrays using the LCS(longest common subsequence) algorithm.
- It recognizes similar Hashes in an Array using a similarity value (0 < similarity <= 1).
Usage
To use the gem, add the following to your Gemfile:
gem 'hashdiff'
Quick Start
Diff
Two simple hashes:
a = {a:3, b:2}
b = {}
diff = HashDiff.diff(a, b)
diff.should == [['-', 'a', 3], ['-', 'b', 2]]
More complex hashes:
a = {a:{x:2, y:3, z:4}, b:{x:3, z:45}}
b = {a:{y:3}, b:{y:3, z:30}}
diff = HashDiff.diff(a, b)
diff.should == [['-', 'a.x', 2], ['-', 'a.z', 4], ['-', 'b.x', 3], ['~', 'b.z', 45, 30], ['+', 'b.y', 3]]
Arrays in hashes:
a = {a:[{x:2, y:3, z:4}, {x:11, y:22, z:33}], b:{x:3, z:45}}
b = {a:[{y:3}, {x:11, z:33}], b:{y:22}}
diff = HashDiff.best_diff(a, b)
diff.should == [['-', 'a[0].x', 2], ['-', 'a[0].z', 4], ['-', 'a[1].y', 22], ['-', 'b.x', 3], ['-', 'b.z', 45], ['+', 'b.y', 22]]
Patch
patch example:
a = {a: 3}
b = {a: {a1: 1, a2: 2}}
diff = HashDiff.diff(a, b)
HashDiff.patch!(a, diff).should == b
unpatch example:
a = [{a: 1, b: 2, c: 3, d: 4, e: 5}, {x: 5, y: 6, z: 3}, 1]
b = [1, {a: 1, b: 2, c: 3, e: 5}]
diff = HashDiff.diff(a, b) # diff two array is OK
HashDiff.unpatch!(b, diff).should == a
Options
There are five options available: :delimiter
, :similarity
, :strict
, :numeric_tolerance
and :strip
.
:delimiter
You can specify :delimiter
to be something other than the default dot. For example:
a = {a:{x:2, y:3, z:4}, b:{x:3, z:45}}
b = {a:{y:3}, b:{y:3, z:30}}
diff = HashDiff.diff(a, b, :delimiter => '\t')
diff.should == [['-', 'a\tx', 2], ['-', 'a\tz', 4], ['-', 'b\tx', 3], ['~', 'b\tz', 45, 30], ['+', 'b\ty', 3]]
:similarity
In cases where you have similar hash objects in arrays, you can pass a custom value for :similarity
instead of the default 0.8
. This is interpreted as a ratio of similarity (default is 80% similar, whereas :similarity => 0.5
would look for at least a 50% similarity).
:strict
The :strict
option, which defaults to true
, specifies whether numeric types are compared on type as well as value. By default, a Fixnum will never be equal to a Float (e.g. 4 != 4.0). Setting :strict
to false makes the comparison looser (e.g. 4 == 4.0).
:numeric_tolerance
The :numeric_tolerance option allows for a small numeric tolerance.
a = {x:5, y:3.75, z:7}
b = {x:6, y:3.76, z:7}
diff = HashDiff.diff(a, b, :numeric_tolerance => 0.1)
diff.should == [["~", "x", 5, 6]]
:strip
The :strip option strips all strings before comparing.
a = {x:5, s:'foo '}
b = {x:6, s:'foo'}
diff = HashDiff.diff(a, b, :comparison => { :numeric_tolerance => 0.1, :strip => true })
diff.should == [["~", "x", 5, 6]]
Specifying a custom comparison method
It's possible to specify how the values of a key should be compared.
a = {a:'car', b:'boat', c:'plane'}
b = {a:'bus', b:'truck', c:' plan'}
diff = HashDiff.diff(a, b) do |path, obj1, obj2|
case path
when /a|b|c/
obj1.length == obj2.length
end
end
diff.should == [['~', 'b', 'boat', 'truck']]
The yielded params of the comparison block is |path, obj1, obj2|
, in which path is the key (or delimited compound key) to the value being compared. When comparing elements in array, the path is with the format array[*]
. For example:
a = {a:'car', b:['boat', 'plane'] }
b = {a:'bus', b:['truck', ' plan'] }
diff = HashDiff.diff(a, b) do |path, obj1, obj2|
case path
when 'b[*]'
obj1.length == obj2.length
end
end
diff.should == [["~", "a", "car", "bus"], ["~", "b[1]", "plane", " plan"], ["-", "b[0]", "boat"], ["+", "b[0]", "truck"]]
When a comparison block is given, it'll be given priority over other specified options. If the block returns value other than true
or false
, then the two values will be compared with other specified options.
Sorting arrays before comparison
An order difference alone between two arrays can create too many diffs to be useful. Consider sorting them prior to diffing.
a = {a:'car', b:['boat', 'plane'] }
b = {a:'car', b:['plane', 'boat'] }
HashDiff.diff(a, b) => [["+", "b[0]", "plane"], ["-", "b[2]", "plane"]]
b[:b].sort!
HashDiff.diff(a, b) => []
Special use cases
Using HashDiff on JSON API results
require 'uri'
require 'net/http'
require 'json'
uri = URI('http://time.jsontest.com/')
json_resp = ->(uri) { JSON.parse(Net::HTTP.get_response(uri).body) }
a = json_resp.call(uri)
b = json_resp.call(uri)
HashDiff.diff(a,b) => [["~", "milliseconds_since_epoch", 1410542545874, 1410542545985]]
License
HashDiff is distributed under the MIT-LICENSE.