diff options
35 files changed, 1777 insertions, 0 deletions
diff --git a/.gitignore b/.gitignore new file mode 100644 index 0000000..134a870 --- /dev/null +++ b/.gitignore @@ -0,0 +1,15 @@ +# See http://help.github.com/ignore-files/ for more about ignoring files. +# +# If you find yourself ignoring temporary files generated by your text editor +# or operating system, you probably want to add a global ignore instead: +# git config --global core.excludesfile ~/.gitignore_global + +# Ignore bundler config +/.bundle +/doc +/.yardoc +/Gemfile.lock + +*.swp +*.bak +*.gem @@ -0,0 +1 @@ +--color diff --git a/.travis.yml b/.travis.yml new file mode 100644 index 0000000..c931dfd --- /dev/null +++ b/.travis.yml @@ -0,0 +1,7 @@ +language: ruby +rvm: + - 1.8.7 + - 1.9.3 + - 2.0.0 + - 2.1.1 +script: "bundle exec rake spec" diff --git a/.yardopts b/.yardopts new file mode 100644 index 0000000..22ce944 --- /dev/null +++ b/.yardopts @@ -0,0 +1 @@ +--no-private @@ -0,0 +1,6 @@ +source "http://rubygems.org" +gemspec + +group :test do + gem 'rake' +end @@ -0,0 +1,19 @@ +Copyright (c) 2012 Liu Fengyun + +Permission is hereby granted, free of charge, to any person obtaining a copy +of this software and associated documentation files (the "Software"), to deal +in the Software without restriction, including without limitation the rights +to use, copy, modify, merge, publish, distribute, sublicense, and/or sell +copies of the Software, and to permit persons to whom the Software is +furnished to do so, subject to the following conditions: + +The above copyright notice and this permission notice shall be included in +all copies or substantial portions of the Software. + +THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR +IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, +FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE +AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER +LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, +OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN +THE SOFTWARE. diff --git a/README.md b/README.md new file mode 100644 index 0000000..9b94662 --- /dev/null +++ b/README.md @@ -0,0 +1,207 @@ +# HashDiff [](http://travis-ci.org/liufengyun/hashdiff) [](http://badge.fury.io/rb/hashdiff) + +HashDiff is a ruby library to compute the smallest difference between two hashes. + +**Docs**: [Documentation](http://rubydoc.info/gems/hashdiff) + +## 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` and `B - 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)](http://en.wikipedia.org/wiki/Longest_common_subsequence_problem) 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: + +```ruby +gem 'hashdiff' +``` + +## Quick Start + +### Diff + +Two simple hashes: + +```ruby +a = {a:3, b:2} +b = {} + +diff = HashDiff.diff(a, b) +diff.should == [['-', 'a', 3], ['-', 'b', 2]] +``` + +More complex hashes: + +```ruby +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: + +```ruby +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: + +```ruby +a = {a: 3} +b = {a: {a1: 1, a2: 2}} + +diff = HashDiff.diff(a, b) +HashDiff.patch!(a, diff).should == b +``` + +unpatch example: + +```ruby +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: + +```ruby +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. + +```ruby +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. + +```ruby +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. + +```ruby +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: + +```ruby +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. + +```ruby +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 + +```ruby +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. + diff --git a/Rakefile b/Rakefile new file mode 100644 index 0000000..66fe6ac --- /dev/null +++ b/Rakefile @@ -0,0 +1,13 @@ +$:.push File.expand_path("../lib", __FILE__) + +require 'bundler' +Bundler::GemHelper.install_tasks + +require 'rspec/core/rake_task' + +task :default => :spec + +RSpec::Core::RakeTask.new(:spec) do |spec| + spec.pattern = "./spec/**/*_spec.rb" +end + diff --git a/changelog.md b/changelog.md new file mode 100644 index 0000000..a370e35 --- /dev/null +++ b/changelog.md @@ -0,0 +1,44 @@ +# Change Log + +## v0.2.3 2015-11-5 + +* improve performance of LCS algorithm #12 + +## v0.2.2 2014-10-6 + +* make library 1.8.7 compatible + +## v0.2.1 2014-7-13 + +* yield added/deleted keys for custom comparison + +## v0.2.0 2014-3-29 + +* support custom comparison blocks +* support `:strip`, `:numeric_tolerance` and `:strict` options + +## v0.1.0 2013-8-25 + +* use options for parameters `:delimiter` and `:similarity` in interfaces + +## v0.0.6 2013-3-2 + +* Add parameter for custom property-path delimiter. + +## v0.0.5 2012-7-1 + +* fix a bug in judging whehter two objects are similiar. +* add more spec test for HashDiff.best_diff + +## v0.0.4 2012-6-24 + +Main changes in this version is to output the whole object in addition & deletion, instead of recursely add/deletes the object. + +For example, `diff({a:2, c:[4, 5]}, {a:2}) will generate following output: + + [['-', 'c', [4, 5]]] + +instead of following: + + [['-', 'c[0]', 4], ['-', 'c[1]', 5], ['-', 'c', []]] + diff --git a/debian/changelog b/debian/changelog new file mode 100644 index 0000000..04954fa --- /dev/null +++ b/debian/changelog @@ -0,0 +1,5 @@ +ruby-hashdiff (0.2.3-1) unstable; urgency=medium + + * Initial release + + -- Antonio Terceiro <terceiro@debian.org> Fri, 22 Jan 2016 12:12:33 -0200 diff --git a/debian/compat b/debian/compat new file mode 100644 index 0000000..ec63514 --- /dev/null +++ b/debian/compat @@ -0,0 +1 @@ +9 diff --git a/debian/control b/debian/control new file mode 100644 index 0000000..0a19e4f --- /dev/null +++ b/debian/control @@ -0,0 +1,25 @@ +Source: ruby-hashdiff +Section: ruby +Priority: optional +Maintainer: Debian Ruby Extras Maintainers <pkg-ruby-extras-maintainers@lists.alioth.debian.org> +Uploaders: Antonio Terceiro <terceiro@debian.org> +Build-Depends: debhelper (>= 9~), + gem2deb, + rake, + ruby-rspec +Standards-Version: 3.9.6 +Vcs-Git: https://anonscm.debian.org/git/pkg-ruby-extras/ruby-hashdiff.git +Vcs-Browser: https://anonscm.debian.org/cgit/pkg-ruby-extras/ruby-hashdiff.git +Homepage: https://github.com/liufengyun/hashdiff +Testsuite: autopkgtest-pkg-ruby +XS-Ruby-Versions: all + +Package: ruby-hashdiff +Architecture: all +XB-Ruby-Versions: ${ruby:Versions} +Depends: ruby | ruby-interpreter, + ${misc:Depends}, + ${shlibs:Depends} +Description: library for computing the smallest difference between two hashes + Given two Hashes A and B, HashDiff will calculate the smallest modification + that can be made to change A into B. diff --git a/debian/copyright b/debian/copyright new file mode 100644 index 0000000..08eef59 --- /dev/null +++ b/debian/copyright @@ -0,0 +1,31 @@ +Format: http://www.debian.org/doc/packaging-manuals/copyright-format/1.0/ +Upstream-Name: hashdiff +Source: https://github.com/liufengyun/hashdiff + +Files: * +Copyright: (c) 2012 Liu Fengyun +License: Expat + +Files: debian/* +Copyright: 2016 Antonio Terceiro <terceiro@debian.org> +License: Expat +Comment: the Debian packaging is licensed under the same terms as the original package. + +License: Expat + Permission is hereby granted, free of charge, to any person obtaining a copy + of this software and associated documentation files (the "Software"), to deal + in the Software without restriction, including without limitation the rights + to use, copy, modify, merge, publish, distribute, sublicense, and/or sell + copies of the Software, and to permit persons to whom the Software is + furnished to do so, subject to the following conditions: + . + The above copyright notice and this permission notice shall be included in + all copies or substantial portions of the Software. + . + THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, + OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN + THE SOFTWARE. diff --git a/debian/patches/0001-Port-tests-to-rspec-3.patch b/debian/patches/0001-Port-tests-to-rspec-3.patch new file mode 100644 index 0000000..fb18633 --- /dev/null +++ b/debian/patches/0001-Port-tests-to-rspec-3.patch @@ -0,0 +1,89 @@ +From: Antonio Terceiro <terceiro@debian.org> +Date: Fri, 22 Jan 2016 12:14:40 -0200 +Subject: Port tests to rspec 3 + +--- + spec/hashdiff/util_spec.rb | 34 +++++++++++++++++----------------- + 1 file changed, 17 insertions(+), 17 deletions(-) + +diff --git a/spec/hashdiff/util_spec.rb b/spec/hashdiff/util_spec.rb +index bce861c..9130686 100644 +--- a/spec/hashdiff/util_spec.rb ++++ b/spec/hashdiff/util_spec.rb +@@ -14,59 +14,59 @@ describe HashDiff do + it "should be able to tell similiar hash" do + a = {'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5} + b = {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5} +- HashDiff.similar?(a, b).should be_true +- HashDiff.similar?(a, b, :similarity => 1).should be_false ++ HashDiff.similar?(a, b).should be true ++ HashDiff.similar?(a, b, :similarity => 1).should be false + end + + it "should be able to tell similiar hash with values within tolerance" do + a = {'a' => 1.5, 'b' => 2.25, 'c' => 3, 'd' => 4, 'e' => 5} + b = {'a' => 1.503, 'b' => 2.22, 'c' => 3, 'e' => 5} +- HashDiff.similar?(a, b, :numeric_tolerance => 0.05).should be_true +- HashDiff.similar?(a, b).should be_false ++ HashDiff.similar?(a, b, :numeric_tolerance => 0.05).should be true ++ HashDiff.similar?(a, b).should be false + end + + it "should be able to tell numbers and strings" do +- HashDiff.similar?(1, 2).should be_false +- HashDiff.similar?("a", "b").should be_false +- HashDiff.similar?("a", [1, 2, 3]).should be_false +- HashDiff.similar?(1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}).should be_false ++ HashDiff.similar?(1, 2).should be false ++ HashDiff.similar?("a", "b").should be false ++ HashDiff.similar?("a", [1, 2, 3]).should be false ++ HashDiff.similar?(1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}).should be false + end + + it "should be able to tell true when similarity == 0.5" do + a = {"value" => "New1", "onclick" => "CreateNewDoc()"} + b = {"value" => "New", "onclick" => "CreateNewDoc()"} + +- HashDiff.similar?(a, b, :similarity => 0.5).should be_true ++ HashDiff.similar?(a, b, :similarity => 0.5).should be true + end + + it "should be able to tell false when similarity == 0.5" do + a = {"value" => "New1", "onclick" => "open()"} + b = {"value" => "New", "onclick" => "CreateNewDoc()"} + +- HashDiff.similar?(a, b, :similarity => 0.5).should be_false ++ HashDiff.similar?(a, b, :similarity => 0.5).should be false + end + + describe '.compare_values' do + it "should compare numeric values exactly when no tolerance" do +- expect(HashDiff.compare_values(10.004, 10.003)).to be_false ++ expect(HashDiff.compare_values(10.004, 10.003)).to be false + end + + it "should allow tolerance with numeric values" do +- expect(HashDiff.compare_values(10.004, 10.003, :numeric_tolerance => 0.01)).to be_true ++ expect(HashDiff.compare_values(10.004, 10.003, :numeric_tolerance => 0.01)).to be true + end + + it "should compare other objects with or without tolerance" do +- expect(HashDiff.compare_values('hats', 'ninjas')).to be_false +- expect(HashDiff.compare_values('hats', 'ninjas', :numeric_tolerance => 0.01)).to be_false +- expect(HashDiff.compare_values('horse', 'horse')).to be_true ++ expect(HashDiff.compare_values('hats', 'ninjas')).to be false ++ expect(HashDiff.compare_values('hats', 'ninjas', :numeric_tolerance => 0.01)).to be false ++ expect(HashDiff.compare_values('horse', 'horse')).to be true + end + + it 'should compare strings exactly by default' do +- expect(HashDiff.compare_values(' horse', 'horse')).to be_false ++ expect(HashDiff.compare_values(' horse', 'horse')).to be false + end + + it 'should strip strings before comparing when requested' do +- expect(HashDiff.compare_values(' horse', 'horse', :strip => true)).to be_true ++ expect(HashDiff.compare_values(' horse', 'horse', :strip => true)).to be true + end + end + end diff --git a/debian/patches/series b/debian/patches/series new file mode 100644 index 0000000..13e8bcc --- /dev/null +++ b/debian/patches/series @@ -0,0 +1 @@ +0001-Port-tests-to-rspec-3.patch diff --git a/debian/ruby-hashdiff.docs b/debian/ruby-hashdiff.docs new file mode 100644 index 0000000..b43bf86 --- /dev/null +++ b/debian/ruby-hashdiff.docs @@ -0,0 +1 @@ +README.md diff --git a/debian/ruby-tests.rake b/debian/ruby-tests.rake new file mode 100644 index 0000000..cf1591e --- /dev/null +++ b/debian/ruby-tests.rake @@ -0,0 +1,5 @@ +require 'gem2deb/rake/spectask' + +Gem2Deb::Rake::RSpecTask.new do |spec| + spec.pattern = './spec/**/*_spec.rb' +end diff --git a/debian/rules b/debian/rules new file mode 100755 index 0000000..3454d59 --- /dev/null +++ b/debian/rules @@ -0,0 +1,6 @@ +#!/usr/bin/make -f + +export GEM2DEB_TEST_RUNNER = --check-dependencies + +%: + dh $@ --buildsystem=ruby --with ruby diff --git a/debian/source/format b/debian/source/format new file mode 100644 index 0000000..163aaf8 --- /dev/null +++ b/debian/source/format @@ -0,0 +1 @@ +3.0 (quilt) diff --git a/debian/watch b/debian/watch new file mode 100644 index 0000000..5d70f52 --- /dev/null +++ b/debian/watch @@ -0,0 +1,2 @@ +version=3 +http://pkg-ruby-extras.alioth.debian.org/cgi-bin/gemwatch/hashdiff .*/hashdiff-(.*).tar.gz diff --git a/hashdiff.gemspec b/hashdiff.gemspec new file mode 100644 index 0000000..251b504 --- /dev/null +++ b/hashdiff.gemspec @@ -0,0 +1,25 @@ +$LOAD_PATH << File.expand_path("../lib", __FILE__) +require 'hashdiff/version' + +Gem::Specification.new do |s| + s.name = %q{hashdiff} + s.version = HashDiff::VERSION + s.license = 'MIT' + s.summary = %q{ HashDiff is a diff lib to compute the smallest difference between two hashes. } + s.description = %q{ HashDiff is a diff lib to compute the smallest difference between two hashes. } + + s.files = `git ls-files`.split("\n") + s.test_files = `git ls-files -- Appraisals {spec}/*`.split("\n") + + s.require_paths = ['lib'] + s.required_ruby_version = Gem::Requirement.new(">= 1.8.7") + + s.authors = ["Liu Fengyun"] + s.email = ["liufengyunchina@gmail.com"] + + s.homepage = "https://github.com/liufengyun/hashdiff" + + s.add_development_dependency("rspec", "~> 2.0") + s.add_development_dependency("yard") + s.add_development_dependency("bluecloth") +end diff --git a/lib/hashdiff.rb b/lib/hashdiff.rb new file mode 100644 index 0000000..08e4936 --- /dev/null +++ b/lib/hashdiff.rb @@ -0,0 +1,5 @@ +require 'hashdiff/util' +require 'hashdiff/lcs' +require 'hashdiff/diff' +require 'hashdiff/patch' +require 'hashdiff/version' diff --git a/lib/hashdiff/diff.rb b/lib/hashdiff/diff.rb new file mode 100644 index 0000000..9f2a0c9 --- /dev/null +++ b/lib/hashdiff/diff.rb @@ -0,0 +1,220 @@ +module HashDiff + + # Best diff two objects, which tries to generate the smallest change set using different similarity values. + # + # HashDiff.best_diff is useful in case of comparing two objects which include similar hashes in arrays. + # + # @param [Array, Hash] obj1 + # @param [Array, Hash] obj2 + # @param [Hash] options the options to use when comparing + # * :strict (Boolean) [true] whether numeric values will be compared on type as well as value. Set to false to allow comparing Fixnum, Float, BigDecimal to each other + # * :delimiter (String) ['.'] the delimiter used when returning nested key references + # * :numeric_tolerance (Numeric) [0] should be a positive numeric value. Value by which numeric differences must be greater than. By default, numeric values are compared exactly; with the :tolerance option, the difference between numeric values must be greater than the given value. + # * :strip (Boolean) [false] whether or not to call #strip on strings before comparing + # + # @yield [path, value1, value2] Optional block is used to compare each value, instead of default #==. If the block returns value other than true of false, then other specified comparison options will be used to do the comparison. + # + # @return [Array] an array of changes. + # e.g. [[ '+', 'a.b', '45' ], [ '-', 'a.c', '5' ], [ '~', 'a.x', '45', '63']] + # + # @example + # a = {'x' => [{'a' => 1, 'c' => 3, 'e' => 5}, {'y' => 3}]} + # b = {'x' => [{'a' => 1, 'b' => 2, 'e' => 5}] } + # diff = HashDiff.best_diff(a, b) + # diff.should == [['-', 'x[0].c', 3], ['+', 'x[0].b', 2], ['-', 'x[1].y', 3], ['-', 'x[1]', {}]] + # + # @since 0.0.1 + def self.best_diff(obj1, obj2, options = {}, &block) + options[:comparison] = block if block_given? + + opts = { :similarity => 0.3 }.merge!(options) + diffs_1 = diff(obj1, obj2, opts) + count_1 = count_diff diffs_1 + + opts = { :similarity => 0.5 }.merge!(options) + diffs_2 = diff(obj1, obj2, opts) + count_2 = count_diff diffs_2 + + opts = { :similarity => 0.8 }.merge!(options) + diffs_3 = diff(obj1, obj2, opts) + count_3 = count_diff diffs_3 + + count, diffs = count_1 < count_2 ? [count_1, diffs_1] : [count_2, diffs_2] + diffs = count < count_3 ? diffs : diffs_3 + end + + # Compute the diff of two hashes or arrays + # + # @param [Array, Hash] obj1 + # @param [Array, Hash] obj2 + # @param [Hash] options the options to use when comparing + # * :strict (Boolean) [true] whether numeric values will be compared on type as well as value. Set to false to allow comparing Fixnum, Float, BigDecimal to each other + # * :similarity (Numeric) [0.8] should be between (0, 1]. Meaningful if there are similar hashes in arrays. See {best_diff}. + # * :delimiter (String) ['.'] the delimiter used when returning nested key references + # * :numeric_tolerance (Numeric) [0] should be a positive numeric value. Value by which numeric differences must be greater than. By default, numeric values are compared exactly; with the :tolerance option, the difference between numeric values must be greater than the given value. + # * :strip (Boolean) [false] whether or not to call #strip on strings before comparing + # + # @yield [path, value1, value2] Optional block is used to compare each value, instead of default #==. If the block returns value other than true of false, then other specified comparison options will be used to do the comparison. + # + # @return [Array] an array of changes. + # e.g. [[ '+', 'a.b', '45' ], [ '-', 'a.c', '5' ], [ '~', 'a.x', '45', '63']] + # + # @example + # a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + # b = {"a" => 1, "b" => {}} + # + # diff = HashDiff.diff(a, b) + # diff.should == [['-', 'b.b1', 1], ['-', 'b.b2', 2]] + # + # @since 0.0.1 + def self.diff(obj1, obj2, options = {}, &block) + opts = { + :prefix => '', + :similarity => 0.8, + :delimiter => '.', + :strict => true, + :strip => false, + :numeric_tolerance => 0 + }.merge!(options) + + opts[:comparison] = block if block_given? + + # prefer to compare with provided block + result = custom_compare(opts[:comparison], opts[:prefix], obj1, obj2) + return result if result + + if obj1.nil? and obj2.nil? + return [] + end + + if obj1.nil? + return [['~', opts[:prefix], nil, obj2]] + end + + if obj2.nil? + return [['~', opts[:prefix], obj1, nil]] + end + + unless comparable?(obj1, obj2, opts[:strict]) + return [['~', opts[:prefix], obj1, obj2]] + end + + result = [] + if obj1.is_a?(Array) + changeset = diff_array(obj1, obj2, opts) do |lcs| + # use a's index for similarity + lcs.each do |pair| + result.concat(diff(obj1[pair[0]], obj2[pair[1]], opts.merge(:prefix => "#{opts[:prefix]}[#{pair[0]}]"))) + end + end + + changeset.each do |change| + if change[0] == '-' + result << ['-', "#{opts[:prefix]}[#{change[1]}]", change[2]] + elsif change[0] == '+' + result << ['+', "#{opts[:prefix]}[#{change[1]}]", change[2]] + end + end + elsif obj1.is_a?(Hash) + if opts[:prefix].empty? + prefix = "" + else + prefix = "#{opts[:prefix]}#{opts[:delimiter]}" + end + + deleted_keys = obj1.keys - obj2.keys + common_keys = obj1.keys & obj2.keys + added_keys = obj2.keys - obj1.keys + + # add deleted properties + deleted_keys.sort.each do |k| + custom_result = custom_compare(opts[:comparison], "#{prefix}#{k}", obj1[k], nil) + + if custom_result + result.concat(custom_result) + else + result << ['-', "#{prefix}#{k}", obj1[k]] + end + end + + # recursive comparison for common keys + common_keys.sort.each {|k| result.concat(diff(obj1[k], obj2[k], opts.merge(:prefix => "#{prefix}#{k}"))) } + + # added properties + added_keys.sort.each do |k| + unless obj1.key?(k) + custom_result = custom_compare(opts[:comparison], "#{prefix}#{k}", nil, obj2[k]) + + if custom_result + result.concat(custom_result) + else + result << ['+', "#{prefix}#{k}", obj2[k]] + end + end + end + else + return [] if compare_values(obj1, obj2, opts) + return [['~', opts[:prefix], obj1, obj2]] + end + + result + end + + # @private + # + # diff array using LCS algorithm + def self.diff_array(a, b, options = {}) + opts = { + :prefix => '', + :similarity => 0.8, + :delimiter => '.' + }.merge!(options) + + change_set = [] + if a.size == 0 and b.size == 0 + return [] + elsif a.size == 0 + b.each_index do |index| + change_set << ['+', index, b[index]] + end + return change_set + elsif b.size == 0 + a.each_index do |index| + i = a.size - index - 1 + change_set << ['-', i, a[i]] + end + return change_set + end + + links = lcs(a, b, opts) + + # yield common + yield links if block_given? + + # padding the end + links << [a.size, b.size] + + last_x = -1 + last_y = -1 + links.each do |pair| + x, y = pair + + # remove from a, beginning from the end + (x > last_x + 1) and (x - last_x - 2).downto(0).each do |i| + change_set << ['-', last_y + i + 1, a[i + last_x + 1]] + end + + # add from b, beginning from the head + (y > last_y + 1) and 0.upto(y - last_y - 2).each do |i| + change_set << ['+', last_y + i + 1, b[i + last_y + 1]] + end + + # update flags + last_x = x + last_y = y + end + + change_set + end + +end diff --git a/lib/hashdiff/lcs.rb b/lib/hashdiff/lcs.rb new file mode 100644 index 0000000..1cc27d5 --- /dev/null +++ b/lib/hashdiff/lcs.rb @@ -0,0 +1,69 @@ +module HashDiff + # @private + # + # caculate array difference using LCS algorithm + # http://en.wikipedia.org/wiki/Longest_common_subsequence_problem + def self.lcs(a, b, options = {}) + opts = { :similarity => 0.8 }.merge!(options) + + opts[:prefix] = "#{opts[:prefix]}[*]" + + return [] if a.size == 0 or b.size == 0 + + a_start = b_start = 0 + a_finish = a.size - 1 + b_finish = b.size - 1 + vector = [] + + lcs = [] + (b_start..b_finish).each do |bi| + lcs[bi] = [] + (a_start..a_finish).each do |ai| + if similar?(a[ai], b[bi], opts) + topleft = (ai > 0 and bi > 0)? lcs[bi-1][ai-1][1] : 0 + lcs[bi][ai] = [:topleft, topleft + 1] + elsif + top = (bi > 0)? lcs[bi-1][ai][1] : 0 + left = (ai > 0)? lcs[bi][ai-1][1] : 0 + count = (top > left) ? top : left + + direction = :both + if top > left + direction = :top + elsif top < left + direction = :left + else + if bi == 0 + direction = :top + elsif ai == 0 + direction = :left + else + direction = :both + end + end + + lcs[bi][ai] = [direction, count] + end + end + end + + x = a_finish + y = b_finish + while x >= 0 and y >= 0 and lcs[y][x][1] > 0 + if lcs[y][x][0] == :both + x -= 1 + elsif lcs[y][x][0] == :topleft + vector.insert(0, [x, y]) + x -= 1 + y -= 1 + elsif lcs[y][x][0] == :top + y -= 1 + elsif lcs[y][x][0] == :left + x -= 1 + end + end + + vector + end + +end diff --git a/lib/hashdiff/patch.rb b/lib/hashdiff/patch.rb new file mode 100644 index 0000000..3c184c4 --- /dev/null +++ b/lib/hashdiff/patch.rb @@ -0,0 +1,84 @@ +# +# This module provides methods to diff two hash, patch and unpatch hash +# +module HashDiff + + # Apply patch to object + # + # @param [Hash, Array] obj the object to be patched, can be an Array or a Hash + # @param [Array] changes e.g. [[ '+', 'a.b', '45' ], [ '-', 'a.c', '5' ], [ '~', 'a.x', '45', '63']] + # @param [Hash] options supports following keys: + # * :delimiter (String) ['.'] delimiter string for representing nested keys in changes array + # + # @return the object after patch + # + # @since 0.0.1 + def self.patch!(obj, changes, options = {}) + delimiter = options[:delimiter] || '.' + + changes.each do |change| + parts = decode_property_path(change[1], delimiter) + last_part = parts.last + + parent_node = node(obj, parts[0, parts.size-1]) + + if change[0] == '+' + if last_part.is_a?(Fixnum) + parent_node.insert(last_part, change[2]) + else + parent_node[last_part] = change[2] + end + elsif change[0] == '-' + if last_part.is_a?(Fixnum) + parent_node.delete_at(last_part) + else + parent_node.delete(last_part) + end + elsif change[0] == '~' + parent_node[last_part] = change[3] + end + end + + obj + end + + # Unpatch an object + # + # @param [Hash, Array] obj the object to be unpatched, can be an Array or a Hash + # @param [Array] changes e.g. [[ '+', 'a.b', '45' ], [ '-', 'a.c', '5' ], [ '~', 'a.x', '45', '63']] + # @param [Hash] options supports following keys: + # * :delimiter (String) ['.'] delimiter string for representing nested keys in changes array + # + # @return the object after unpatch + # + # @since 0.0.1 + def self.unpatch!(obj, changes, options = {}) + delimiter = options[:delimiter] || '.' + + changes.reverse_each do |change| + parts = decode_property_path(change[1], delimiter) + last_part = parts.last + + parent_node = node(obj, parts[0, parts.size-1]) + + if change[0] == '+' + if last_part.is_a?(Fixnum) + parent_node.delete_at(last_part) + else + parent_node.delete(last_part) + end + elsif change[0] == '-' + if last_part.is_a?(Fixnum) + parent_node.insert(last_part, change[2]) + else + parent_node[last_part] = change[2] + end + elsif change[0] == '~' + parent_node[last_part] = change[2] + end + end + + obj + end + +end diff --git a/lib/hashdiff/util.rb b/lib/hashdiff/util.rb new file mode 100644 index 0000000..862d39a --- /dev/null +++ b/lib/hashdiff/util.rb @@ -0,0 +1,127 @@ +module HashDiff + + # @private + # + # judge whether two objects are similar + def self.similar?(a, b, options = {}) + opts = { :similarity => 0.8 }.merge(options) + + count_a = count_nodes(a) + count_b = count_nodes(b) + diffs = count_diff diff(a, b, opts) + + if count_a + count_b == 0 + return true + else + (1 - diffs.to_f/(count_a + count_b).to_f) >= opts[:similarity] + end + end + + # @private + # + # count node differences + def self.count_diff(diffs) + diffs.inject(0) do |sum, item| + old_change_count = count_nodes(item[2]) + new_change_count = count_nodes(item[3]) + sum += (old_change_count + new_change_count) + end + end + + # @private + # + # count total nodes for an object + def self.count_nodes(obj) + return 0 unless obj + + count = 0 + if obj.is_a?(Array) + obj.each {|e| count += count_nodes(e) } + elsif obj.is_a?(Hash) + obj.each {|k, v| count += count_nodes(v) } + else + return 1 + end + + count + end + + # @private + # + # decode property path into an array + # @param [String] path Property-string + # @param [String] delimiter Property-string delimiter + # + # e.g. "a.b[3].c" => ['a', 'b', 3, 'c'] + def self.decode_property_path(path, delimiter='.') + parts = path.split(delimiter).collect do |part| + if part =~ /^(\w*)\[(\d+)\]$/ + if $1.size > 0 + [$1, $2.to_i] + else + $2.to_i + end + else + part + end + end + + parts.flatten + end + + # @private + # + # get the node of hash by given path parts + def self.node(hash, parts) + temp = hash + parts.each do |part| + temp = temp[part] + end + temp + end + + # @private + # + # check for equality or "closeness" within given tolerance + def self.compare_values(obj1, obj2, options = {}) + if (options[:numeric_tolerance].is_a? Numeric) && + [obj1, obj2].all? { |v| v.is_a? Numeric } + return (obj1 - obj2).abs <= options[:numeric_tolerance] + end + + if options[:strip] == true + first = obj1.strip if obj1.respond_to?(:strip) + second = obj2.strip if obj2.respond_to?(:strip) + return first == second + end + + obj1 == obj2 + end + + # @private + # + # check if objects are comparable + def self.comparable?(obj1, obj2, strict = true) + [Array, Hash].each do |type| + return true if obj1.is_a?(type) && obj2.is_a?(type) + end + return true if !strict && obj1.is_a?(Numeric) && obj2.is_a?(Numeric) + obj1.is_a?(obj2.class) && obj2.is_a?(obj1.class) + end + + # @private + # + # try custom comparison + def self.custom_compare(method, key, obj1, obj2) + if method + res = method.call(key, obj1, obj2) + + # nil != false here + if res == false + return [['~', key, obj1, obj2]] + elsif res == true + return [] + end + end + end +end diff --git a/lib/hashdiff/version.rb b/lib/hashdiff/version.rb new file mode 100644 index 0000000..452c3f3 --- /dev/null +++ b/lib/hashdiff/version.rb @@ -0,0 +1,3 @@ +module HashDiff + VERSION = '0.2.3' +end diff --git a/metadata.yml b/metadata.yml new file mode 100644 index 0000000..9f51629 --- /dev/null +++ b/metadata.yml @@ -0,0 +1,110 @@ +--- !ruby/object:Gem::Specification +name: hashdiff +version: !ruby/object:Gem::Version + version: 0.2.3 +platform: ruby +authors: +- Liu Fengyun +autorequire: +bindir: bin +cert_chain: [] +date: 2015-11-05 00:00:00.000000000 Z +dependencies: +- !ruby/object:Gem::Dependency + name: rspec + requirement: !ruby/object:Gem::Requirement + requirements: + - - ~> + - !ruby/object:Gem::Version + version: '2.0' + type: :development + prerelease: false + version_requirements: !ruby/object:Gem::Requirement + requirements: + - - ~> + - !ruby/object:Gem::Version + version: '2.0' +- !ruby/object:Gem::Dependency + name: yard + requirement: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: '0' + type: :development + prerelease: false + version_requirements: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: '0' +- !ruby/object:Gem::Dependency + name: bluecloth + requirement: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: '0' + type: :development + prerelease: false + version_requirements: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: '0' +description: ' HashDiff is a diff lib to compute the smallest difference between two + hashes. ' +email: +- liufengyunchina@gmail.com +executables: [] +extensions: [] +extra_rdoc_files: [] +files: +- .gitignore +- .rspec +- .travis.yml +- .yardopts +- Gemfile +- LICENSE +- README.md +- Rakefile +- changelog.md +- hashdiff.gemspec +- lib/hashdiff.rb +- lib/hashdiff/diff.rb +- lib/hashdiff/lcs.rb +- lib/hashdiff/patch.rb +- lib/hashdiff/util.rb +- lib/hashdiff/version.rb +- spec/hashdiff/best_diff_spec.rb +- spec/hashdiff/diff_array_spec.rb +- spec/hashdiff/diff_spec.rb +- spec/hashdiff/lcs_spec.rb +- spec/hashdiff/patch_spec.rb +- spec/hashdiff/util_spec.rb +- spec/spec_helper.rb +homepage: https://github.com/liufengyun/hashdiff +licenses: +- MIT +metadata: {} +post_install_message: +rdoc_options: [] +require_paths: +- lib +required_ruby_version: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: 1.8.7 +required_rubygems_version: !ruby/object:Gem::Requirement + requirements: + - - '>=' + - !ruby/object:Gem::Version + version: '0' +requirements: [] +rubyforge_project: +rubygems_version: 2.0.14 +signing_key: +specification_version: 4 +summary: HashDiff is a diff lib to compute the smallest difference between two hashes. +test_files: [] diff --git a/spec/hashdiff/best_diff_spec.rb b/spec/hashdiff/best_diff_spec.rb new file mode 100644 index 0000000..c444e88 --- /dev/null +++ b/spec/hashdiff/best_diff_spec.rb @@ -0,0 +1,65 @@ +require 'spec_helper' + +describe HashDiff do + it "should be able to best diff" do + a = {'x' => [{'a' => 1, 'c' => 3, 'e' => 5}, {'y' => 3}]} + b = {'x' => [{'a' => 1, 'b' => 2, 'e' => 5}] } + + diff = HashDiff.best_diff(a, b) + diff.should == [["-", "x[0].c", 3], ["+", "x[0].b", 2], ["-", "x[1]", {"y"=>3}]] + end + + it "should use custom delimiter when provided" do + a = {'x' => [{'a' => 1, 'c' => 3, 'e' => 5}, {'y' => 3}]} + b = {'x' => [{'a' => 1, 'b' => 2, 'e' => 5}] } + + diff = HashDiff.best_diff(a, b, :delimiter => "\t") + diff.should == [["-", "x[0]\tc", 3], ["+", "x[0]\tb", 2], ["-", "x[1]", {"y"=>3}]] + end + + it "should use custom comparison when provided" do + a = {'x' => [{'a' => 'foo', 'c' => 'goat', 'e' => 'snake'}, {'y' => 'baz'}]} + b = {'x' => [{'a' => 'bar', 'b' => 'cow', 'e' => 'puppy'}] } + + diff = HashDiff.best_diff(a, b) do |path, obj1, obj2| + case path + when /^x\[.\]\..$/ + obj1.length == obj2.length if obj1 and obj2 + end + end + + diff.should == [["-", "x[0].c", 'goat'], ["+", "x[0].b", 'cow'], ["-", "x[1]", {"y"=>'baz'}]] + end + + it "should be able to best diff array in hash" do + a = {"menu" => { + "id" => "file", + "value" => "File", + "popup" => { + "menuitem" => [ + {"value" => "New", "onclick" => "CreateNewDoc()"}, + {"value" => "Close", "onclick" => "CloseDoc()"} + ] + } + }} + + b = {"menu" => { + "id" => "file 2", + "value" => "File", + "popup" => { + "menuitem" => [ + {"value" => "New1", "onclick" => "CreateNewDoc()"}, + {"value" => "Open", "onclick" => "OpenDoc()"}, + {"value" => "Close", "onclick" => "CloseDoc()"} + ] + } + }} + + diff = HashDiff.best_diff(a, b) + diff.should == [ + ['~', 'menu.id', 'file', 'file 2'], + ['~', 'menu.popup.menuitem[0].value', 'New', 'New1'], + ['+', 'menu.popup.menuitem[1]', {"value" => "Open", "onclick" => "OpenDoc()"}] + ] + end +end diff --git a/spec/hashdiff/diff_array_spec.rb b/spec/hashdiff/diff_array_spec.rb new file mode 100644 index 0000000..c22af75 --- /dev/null +++ b/spec/hashdiff/diff_array_spec.rb @@ -0,0 +1,60 @@ +require 'spec_helper' + +describe HashDiff do + it "should be able to diff two equal array" do + a = [1, 2, 3] + b = [1, 2, 3] + + diff = HashDiff.diff_array(a, b) + diff.should == [] + end + + it "should be able to diff two arrays with one element in common" do + a = [1, 2, 3] + b = [1, 8, 7] + + diff = HashDiff.diff_array(a, b) + diff.should == [['-', 2, 3], ['-', 1, 2], ['+', 1, 8], ['+', 2, 7]] + end + + it "should be able to diff two arrays with nothing in common" do + a = [1, 2] + b = [] + + diff = HashDiff.diff_array(a, b) + diff.should == [['-', 1, 2], ['-', 0, 1]] + end + + it "should be able to diff an empty array with an non-empty array" do + a = [] + b = [1, 2] + + diff = HashDiff.diff_array(a, b) + diff.should == [['+', 0, 1], ['+', 1, 2]] + end + + it "should be able to diff two arrays with two elements in common" do + a = [1, 3, 5, 7] + b = [2, 3, 7, 5] + + diff = HashDiff.diff_array(a, b) + diff.should == [['-', 0, 1], ['+', 0, 2], ['+', 2, 7], ['-', 4, 7]] + end + + it "should be able to test two arrays with two common elements in different order" do + a = [1, 3, 4, 7] + b = [2, 3, 7, 5] + + diff = HashDiff.diff_array(a, b) + diff.should == [['-', 0, 1], ['+', 0, 2], ['-', 2, 4], ['+', 3, 5]] + end + + it "should be able to diff two arrays with similar elements" do + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, 3] + b = [1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}] + diff = HashDiff.diff_array(a, b) + diff.should == [['+', 0, 1], ['-', 2, 3]] + end + +end + diff --git a/spec/hashdiff/diff_spec.rb b/spec/hashdiff/diff_spec.rb new file mode 100644 index 0000000..903e35f --- /dev/null +++ b/spec/hashdiff/diff_spec.rb @@ -0,0 +1,232 @@ +require 'spec_helper' + +describe HashDiff do + it "should be able to diff two empty hashes" do + diff = HashDiff.diff({}, {}) + diff.should == [] + end + + it "should be able to diff an hash with an empty hash" do + a = { 'a' => 3, 'b' => 2 } + b = {} + + diff = HashDiff.diff(a, b) + diff.should == [['-', 'a', 3], ['-', 'b', 2]] + + diff = HashDiff.diff(b, a) + diff.should == [['+', 'a', 3], ['+', 'b', 2]] + end + + it "should be able to diff two equal hashes" do + diff = HashDiff.diff({ 'a' => 2, 'b' => 2}, { 'a' => 2, 'b' => 2 }) + diff.should == [] + end + + it "should be able to diff two hashes with equivalent numerics, when strict is false" do + diff = HashDiff.diff({ 'a' => 2.0, 'b' => 2 }, { 'a' => 2, 'b' => 2.0 }, :strict => false) + diff.should == [] + end + + it "should be able to diff changes in hash value" do + diff = HashDiff.diff({ 'a' => 2, 'b' => 3, 'c' => " hello" }, { 'a' => 2, 'b' => 4, 'c' => "hello" }) + diff.should == [['~', 'b', 3, 4], ['~', 'c', " hello", "hello"]] + end + + it "should be able to diff changes in hash value which is array" do + diff = HashDiff.diff({ 'a' => 2, 'b' => [1, 2, 3] }, { 'a' => 2, 'b' => [1, 3, 4]}) + diff.should == [['-', 'b[1]', 2], ['+', 'b[2]', 4]] + end + + it "should be able to diff changes in hash value which is hash" do + diff = HashDiff.diff({ 'a' => { 'x' => 2, 'y' => 3, 'z' => 4 }, 'b' => { 'x' => 3, 'z' => 45 } }, + { 'a' => { 'y' => 3 }, 'b' => { 'y' => 3, 'z' => 30 } }) + diff.should == [['-', 'a.x', 2], ['-', 'a.z', 4], ['-', 'b.x', 3], ['~', 'b.z', 45, 30], ['+', 'b.y', 3]] + end + + it "should be able to diff similar objects in array" do + diff = HashDiff.best_diff({ 'a' => [{ 'x' => 2, 'y' => 3, 'z' => 4 }, { 'x' => 11, 'y' => 22, 'z' => 33 }], 'b' => { 'x' => 3, 'z' => 45 } }, + { 'a' => [{ 'y' => 3 }, { 'x' => 11, 'z' => 33 }], 'b' => { 'y' => 22 } }) + diff.should == [['-', 'a[0].x', 2], ['-', 'a[0].z', 4], ['-', 'a[1].y', 22], ['-', 'b.x', 3], ['-', 'b.z', 45], ['+', 'b.y', 22]] + end + + it 'should be able to diff addition of key value pair' do + a = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200} + b = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200, "g"=>300} + + diff = HashDiff.diff(a, b) + diff.should == [['+', 'g', 300]] + + diff = HashDiff.diff(b, a) + diff.should == [['-', 'g', 300]] + end + + it 'should be able to diff value type changes' do + a = {"a" => 3} + b = {"a" => {"a1" => 1, "a2" => 2}} + + diff = HashDiff.diff(a, b) + diff.should == [['~', 'a', 3, {"a1" => 1, "a2" => 2}]] + + diff = HashDiff.diff(b, a) + diff.should == [['~', 'a', {"a1" => 1, "a2" => 2}, 3]] + end + + it "should be able to diff value changes: array <=> []" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => []} + + diff = HashDiff.diff(a, b) + diff.should == [['-', 'b[1]', 2], ['-', 'b[0]', 1]] + end + + it "should be able to diff value changes: array <=> nil" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => nil} + + diff = HashDiff.diff(a, b) + diff.should == [["~", "b", [1, 2], nil]] + end + + it "should be able to diff value chagnes: remove array completely" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1} + + diff = HashDiff.diff(a, b) + diff.should == [["-", "b", [1, 2]]] + end + + it "should be able to diff value changes: remove whole hash" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1} + + diff = HashDiff.diff(a, b) + diff.should == [["-", "b", {"b1"=>1, "b2"=>2}]] + end + + it "should be able to diff value changes: hash <=> {}" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => {}} + + diff = HashDiff.diff(a, b) + diff.should == [['-', 'b.b1', 1], ['-', 'b.b2', 2]] + end + + it "should be able to diff value changes: hash <=> nil" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => nil} + + diff = HashDiff.diff(a, b) + diff.should == [["~", "b", {"b1"=>1, "b2"=>2}, nil]] + end + + it "should be able to diff similar objects in array" do + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, 3] + b = [1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}] + + diff = HashDiff.diff(a, b) + diff.should == [['-', '[0].d', 4], ['+', '[0]', 1], ['-', '[2]', 3]] + end + + it "should be able to diff similar & equal objects in array" do + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, {'x' => 5, 'y' => 6, 'z' => 3}, 3] + b = [{'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}, 3] + + diff = HashDiff.diff(a, b) + diff.should == [["-", "[0].d", 4], ["-", "[1]", {"x"=>5, "y"=>6, "z"=>3}]] + end + + it "should use custom delimiter when provided" do + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, {'x' => 5, 'y' => 6, 'z' => 3}, 3] + b = [{'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}, 3] + + diff = HashDiff.diff(a, b, :similarity => 0.8, :delimiter => "\t") + diff.should == [["-", "[0]\td", 4], ["-", "[1]", {"x"=>5, "y"=>6, "z"=>3}]] + end + + context 'when :numeric_tolerance requested' do + it "should be able to diff changes in hash value" do + a = {'a' => 0.558, 'b' => 0.0, 'c' => 0.65, 'd' => 'fin'} + b = {'a' => 0.557, 'b' => 'hats', 'c' => 0.67, 'd' => 'fin'} + + diff = HashDiff.diff(a, b, :numeric_tolerance => 0.01) + diff.should == [["~", "b", 0.0, 'hats'], ["~", "c", 0.65, 0.67]] + + diff = HashDiff.diff(b, a, :numeric_tolerance => 0.01) + diff.should == [["~", "b", 'hats', 0.0], ["~", "c", 0.67, 0.65]] + end + + it "should be able to diff changes in nested values" do + a = {'a' => {'x' => 0.4, 'y' => 0.338}, 'b' => [13, 68.03]} + b = {'a' => {'x' => 0.6, 'y' => 0.341}, 'b' => [14, 68.025]} + + diff = HashDiff.diff(a, b, :numeric_tolerance => 0.01) + diff.should == [["~", "a.x", 0.4, 0.6], ["-", "b[0]", 13], ["+", "b[0]", 14]] + + diff = HashDiff.diff(b, a, :numeric_tolerance => 0.01) + diff.should == [["~", "a.x", 0.6, 0.4], ["-", "b[0]", 14], ["+", "b[0]", 13]] + end + end + + context 'when :strip requested' do + it "should strip strings before comparing" do + a = { 'a' => " foo", 'b' => "fizz buzz"} + b = { 'a' => "foo", 'b' => "fizzbuzz"} + diff = HashDiff.diff(a, b, :strip => true) + diff.should == [['~', 'b', "fizz buzz", "fizzbuzz"]] + end + + it "should strip nested strings before comparing" do + a = { 'a' => { 'x' => " foo" }, 'b' => ["fizz buzz", "nerf"] } + b = { 'a' => { 'x' => "foo" }, 'b' => ["fizzbuzz", "nerf"] } + diff = HashDiff.diff(a, b, :strip => true) + diff.should == [['-', 'b[0]', "fizz buzz"], ['+', 'b[0]', "fizzbuzz"]] + end + end + + context 'when both :strip and :numeric_tolerance requested' do + it 'should apply filters to proper object types' do + a = { 'a' => " foo", 'b' => 35, 'c' => 'bar', 'd' => 'baz' } + b = { 'a' => "foo", 'b' => 35.005, 'c' => 'bar', 'd' => 18.5} + diff = HashDiff.diff(a, b, :strict => false, :numeric_tolerance => 0.01, :strip => true) + diff.should == [['~', 'd', "baz", 18.5]] + end + end + + context 'with custom comparison' do + let(:a) { { 'a' => 'car', 'b' => 'boat', 'c' => 'plane'} } + let(:b) { { 'a' => 'bus', 'b' => 'truck', 'c' => ' plan'} } + + it 'should compare using proc specified in block' do + diff = HashDiff.diff(a, b) do |prefix, obj1, obj2| + case prefix + when /a|b|c/ + obj1.length == obj2.length + end + end + diff.should == [['~', 'b', 'boat', 'truck']] + end + + it 'should yield added keys' do + x = { 'a' => 'car', 'b' => 'boat'} + y = { 'a' => 'car' } + + diff = HashDiff.diff(x, y) do |prefix, obj1, obj2| + case prefix + when /b/ + true + end + end + diff.should == [] + end + + it 'should compare with both proc and :strip when both provided' do + diff = HashDiff.diff(a, b, :strip => true) do |prefix, obj1, obj2| + case prefix + when 'a' + obj1.length == obj2.length + end + end + diff.should == [['~', 'b', 'boat', 'truck'], ['~', 'c', 'plane', ' plan']] + end + end +end diff --git a/spec/hashdiff/lcs_spec.rb b/spec/hashdiff/lcs_spec.rb new file mode 100644 index 0000000..7b8cece --- /dev/null +++ b/spec/hashdiff/lcs_spec.rb @@ -0,0 +1,75 @@ +require 'spec_helper' + +describe HashDiff do + it "should be able to find LCS between two equal array" do + a = [1, 2, 3] + b = [1, 2, 3] + + lcs = HashDiff.lcs(a, b) + lcs.should == [[0, 0], [1, 1], [2, 2]] + end + + it "should be able to find LCS between two close arrays" do + a = [1.05, 2, 3.25] + b = [1.06, 2, 3.24] + + lcs = HashDiff.lcs(a, b, :numeric_tolerance => 0.1) + lcs.should == [[0, 0], [1, 1], [2, 2]] + end + + it "should strip strings when finding LCS if requested" do + a = ['foo', 'bar', 'baz'] + b = [' foo', 'bar', 'zab'] + + lcs = HashDiff.lcs(a, b, :strip => true) + lcs.should == [[0, 0], [1, 1]] + end + + it "should be able to find LCS with one common elements" do + a = [1, 2, 3] + b = [1, 8, 7] + + lcs = HashDiff.lcs(a, b) + lcs.should == [[0, 0]] + end + + it "should be able to find LCS with two common elements" do + a = [1, 3, 5, 7] + b = [2, 3, 7, 5] + + lcs = HashDiff.lcs(a, b) + lcs.should == [[1, 1], [2, 3]] + end + + it "should be able to find LCS with two close elements" do + a = [1, 3.05, 5, 7] + b = [2, 3.06, 7, 5] + + lcs = HashDiff.lcs(a, b, :numeric_tolerance => 0.1) + lcs.should == [[1, 1], [2, 3]] + end + + it "should be able to find LCS with two common elements in different ordering" do + a = [1, 3, 4, 7] + b = [2, 3, 7, 5] + + lcs = HashDiff.lcs(a, b) + lcs.should == [[1, 1], [3, 2]] + end + + it "should be able to find LCS with a similarity value" do + a = [ + {"value" => "New", "onclick" => "CreateNewDoc()"}, + {"value" => "Close", "onclick" => "CloseDoc()"} + ] + b = [ + {"value" => "New1", "onclick" => "CreateNewDoc()"}, + {"value" => "Open", "onclick" => "OpenDoc()"}, + {"value" => "Close", "onclick" => "CloseDoc()"} + ] + + lcs = HashDiff.lcs(a, b, :similarity => 0.5) + lcs.should == [[0, 0], [1, 2]] + end +end + diff --git a/spec/hashdiff/patch_spec.rb b/spec/hashdiff/patch_spec.rb new file mode 100644 index 0000000..30d5a2e --- /dev/null +++ b/spec/hashdiff/patch_spec.rb @@ -0,0 +1,136 @@ +require 'spec_helper' + +describe HashDiff do + it "it should be able to patch key addition" do + a = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200} + b = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200, "g"=>300} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200} + b = {"a"=>3, "c"=>11, "d"=>45, "e"=>100, "f"=>200, "g"=>300} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value type changes" do + a = {"a" => 3} + b = {"a" => {"a1" => 1, "a2" => 2}} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 3} + b = {"a" => {"a1" => 1, "a2" => 2}} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value array <=> []" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => []} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => []} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value array <=> nil" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => nil} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1, "b" => nil} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch array value removal" do + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => [1, 2]} + b = {"a" => 1} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch hash value removal" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value hash <=> {}" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => {}} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => {}} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value hash <=> nil" do + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => nil} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => {"b1" => 1, "b2" =>2}} + b = {"a" => 1, "b" => nil} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch value nil removal" do + a = {"a" => 1, "b" => nil} + b = {"a" => 1} + diff = HashDiff.diff(a, b) + + HashDiff.patch!(a, diff).should == b + + a = {"a" => 1, "b" => nil} + b = {"a" => 1} + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch similar objects between arrays" do + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, 3] + b = [1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}] + + diff = HashDiff.diff(a, b) + HashDiff.patch!(a, diff).should == b + + a = [{'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5}, 3] + b = [1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}] + HashDiff.unpatch!(b, diff).should == a + end + + it "should be able to patch similar & equal objects between arrays" do + 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) + HashDiff.patch!(a, diff).should == b + + 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}] + HashDiff.unpatch!(b, diff).should == a + end + +end diff --git a/spec/hashdiff/util_spec.rb b/spec/hashdiff/util_spec.rb new file mode 100644 index 0000000..bce861c --- /dev/null +++ b/spec/hashdiff/util_spec.rb @@ -0,0 +1,73 @@ +require 'spec_helper' + +describe HashDiff do + it "should be able to decode property path" do + decoded = HashDiff.send(:decode_property_path, "a.b[0].c.city[5]") + decoded.should == ['a', 'b', 0, 'c', 'city', 5] + end + + it "should be able to decode property path with custom delimiter" do + decoded = HashDiff.send(:decode_property_path, "a\tb[0]\tc\tcity[5]", "\t") + decoded.should == ['a', 'b', 0, 'c', 'city', 5] + end + + it "should be able to tell similiar hash" do + a = {'a' => 1, 'b' => 2, 'c' => 3, 'd' => 4, 'e' => 5} + b = {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5} + HashDiff.similar?(a, b).should be_true + HashDiff.similar?(a, b, :similarity => 1).should be_false + end + + it "should be able to tell similiar hash with values within tolerance" do + a = {'a' => 1.5, 'b' => 2.25, 'c' => 3, 'd' => 4, 'e' => 5} + b = {'a' => 1.503, 'b' => 2.22, 'c' => 3, 'e' => 5} + HashDiff.similar?(a, b, :numeric_tolerance => 0.05).should be_true + HashDiff.similar?(a, b).should be_false + end + + it "should be able to tell numbers and strings" do + HashDiff.similar?(1, 2).should be_false + HashDiff.similar?("a", "b").should be_false + HashDiff.similar?("a", [1, 2, 3]).should be_false + HashDiff.similar?(1, {'a' => 1, 'b' => 2, 'c' => 3, 'e' => 5}).should be_false + end + + it "should be able to tell true when similarity == 0.5" do + a = {"value" => "New1", "onclick" => "CreateNewDoc()"} + b = {"value" => "New", "onclick" => "CreateNewDoc()"} + + HashDiff.similar?(a, b, :similarity => 0.5).should be_true + end + + it "should be able to tell false when similarity == 0.5" do + a = {"value" => "New1", "onclick" => "open()"} + b = {"value" => "New", "onclick" => "CreateNewDoc()"} + + HashDiff.similar?(a, b, :similarity => 0.5).should be_false + end + + describe '.compare_values' do + it "should compare numeric values exactly when no tolerance" do + expect(HashDiff.compare_values(10.004, 10.003)).to be_false + end + + it "should allow tolerance with numeric values" do + expect(HashDiff.compare_values(10.004, 10.003, :numeric_tolerance => 0.01)).to be_true + end + + it "should compare other objects with or without tolerance" do + expect(HashDiff.compare_values('hats', 'ninjas')).to be_false + expect(HashDiff.compare_values('hats', 'ninjas', :numeric_tolerance => 0.01)).to be_false + expect(HashDiff.compare_values('horse', 'horse')).to be_true + end + + it 'should compare strings exactly by default' do + expect(HashDiff.compare_values(' horse', 'horse')).to be_false + end + + it 'should strip strings before comparing when requested' do + expect(HashDiff.compare_values(' horse', 'horse', :strip => true)).to be_true + end + end +end + diff --git a/spec/spec_helper.rb b/spec/spec_helper.rb new file mode 100644 index 0000000..c52a6fc --- /dev/null +++ b/spec/spec_helper.rb @@ -0,0 +1,13 @@ +$LOAD_PATH << File.join(File.dirname(__FILE__), '..', 'lib') + +require 'rubygems' +require 'rspec' +require 'rspec/autorun' + +require 'hashdiff' + +RSpec.configure do |config| + config.mock_framework = :rspec + + config.include RSpec::Matchers +end |