Familien Schøler’s blog

Lidt af hvert fra hverdagen hos Michael, Kamilla, Marie og Katrine Schøler

JSON diffing

15. januar, 2008

I have now created a method for returning structural differences between two JSON objects. This completes my work with making a JSON merge and JSON diff implementation (although it will most certainly undergo future revisions and quirk resolving changes).

Why? Say for instance you have two JSON structures, json1 and json2. The object json1 holds an original set of data, whereas json2 represents an updated edition of json1. With the diff method you can programatically extract the differences between the two. This could e.g. be used to further limit the amount of data transmitted between the client/server (e.g. with ajax requests), without the need for specialized client side code tracking data changes. When you need to transmit the changes you simply diff the latest set received with the current.

Read my earlier article regarding JSON merging here.

Both the merge and diff methods I have created, can operate on cyclic (self-referencing) JSON structures.

Updated: Now correctly handles arrays. Please note that the ordering of items in the arrays are considered application critical. Thus, the array [1,2] is not considered similar to [2,1].

The diff and merge implementations require the Array.indexOf, Object.isArray and Object.keys methods from the prototype framework.

Further information and demos are available here:
jsonDiff and jsonMerge.

Here is the new implementation with the diff and merge methods (validates in JSLint):

  1. // Author: Michael Schøler, 2008
  2. // Dual licensed as MIT and LGPL, use as you like, don’t hold me responsible for success or failure though.
  3. Array.prototype.compareTo = function(compareAry) {
  4.   if (this.length === compareAry.length) {
  5.     var i;
  6.     for (i = 0; i < compareAry.length; i+=1) {
  7.       if (Object.isArray(this[i]) === true) {
  8.         if (this[i].compareTo(compareAry[i]) === false) {
  9.           return false;
  10.         }
  11.         continue;
  12.       }
  13.       else if (this[i] !== compareAry[i]) {
  14.         return false;
  15.       }
  16.     }
  17.     return true;
  18.   }
  19.   return false;
  20. };
  21. var jsonDataHandler = {
  22.   merge: function(j1, j2) {
  23.     if (typeof this.merging === “undefined” || this.merging === 0) {
  24.       this.mergeCyclicCheck = [];
  25.       this.merging = 0;
  26.     }
  27.     this.merging += 1;
  28.     if (typeof j1 === “undefined”) {
  29.       j1 = {};
  30.     }
  31.     if (typeof j2 === “undefined”) {
  32.       j2 = {};
  33.     }
  34.     if (typeof this.mergeCyclicCheck === “undefined”) {
  35.       this.mergeCyclicCheck = [];
  36.     }
  37.     var key;
  38.     for (key in j2) if (j2.hasOwnProperty(key)) {
  39.       if (typeof j1[key] === “undefined”) {
  40.         j1[key] = j2[key];
  41.       }
  42.       else {
  43.         if (typeof j2[key] === “object”) {
  44.           if (this.mergeCyclicCheck.indexOf(j1[key]) >= 0) {
  45.             break;
  46.           }
  47.           this.merge(j1[key], j2[key]);
  48.           this.mergeCyclicCheck.push(j1[key]);
  49.         }
  50.         else {
  51.           j1[key] = j2[key];
  52.         }
  53.       }
  54.     }
  55.     this.merging -= 1;
  56.   },
  57.   diff: function(j1, j2) {
  58.     if (typeof this.diffing === "undefined" || this.diffing === 0) {
  59.       this.diffCyclicCheck = [];
  60.       this.diffing = 0;
  61.     }
  62.     var diffRes = {};
  63.     this.diffing += 1;
  64.     if (typeof j1 === "undefined") {
  65.       j1 = {};
  66.     }
  67.     if (typeof j2 === "undefined") {
  68.       j2 = {};
  69.     }
  70.     if (typeof this.diffCyclicCheck === "undefined") {
  71.       this.diffCyclicCheck = [];
  72.     }
  73.     var key, bDiff;
  74.     for (key in j2) if (j2.hasOwnProperty(key)) {  
  75.       bDiff = false;
  76.       if (typeof j1[key] === "undefined" || typeof j1[key] != typeof j2[key]) {
  77.         bDiff = true;
  78.       }
  79.       else if (j1[key] !== j2[key]) {
  80.         if (typeof j2[key] === "object") {
  81.           if (this.diffCyclicCheck.indexOf(j2[key]) >= 0) {
  82.             break;
  83.           }
  84.           else if (Object.isArray(j2[key])) {
  85.             if (j1[key].length !== j2[key].length || j1[key] !== j2[key]) {
  86.               if (j2[key].compareTo(j1[key]) === false) {
  87.                 bDiff = true;
  88.               }
  89.             }
  90.           }
  91.           else if (typeof j1[key] === "object") {
  92.             var dR = this.diff(j1[key], j2[key]);
  93.             if (Object.keys(dR).length > 0) {
  94.               diffRes[key] = dR;
  95.             }
  96.           }
  97.           else {
  98.             bDiff = true;
  99.           }
  100.           this.diffCyclicCheck.push(j2[key]);
  101.         }
  102.         else if (j1[key] !== j2[key]) {
  103.           bDiff = true;
  104.         }
  105.       }
  106.       if (bDiff) {
  107.         diffRes[key] = j2[key];
  108.       }
  109.     }
  110.     for (key in j1) if (j1.hasOwnProperty(key)) {
  111.       bDiff = false;
  112.       if (typeof j2[key] === "undefined") {
  113.         diffRes[key] = j1[key];
  114.       }
  115.     }
  116.     this.diffing -= 1;
  117.     return diffRes;
  118.   }
  119. };

You are free to download jsonDataHandler.zip which is a zip archive of the code in plain javascript and in JSMin minified format. The code is LGPL licensed (read more) and MIT licensed (read more).

Enjoy!

Udgivet i JSON, Programmering

8 Responses to “JSON diffing”


  1. Jakob Kruse

    Nice! That just might come in handy!

    16. januar, 2008 at 07:07:33

  2. Matt

    Hi Michael,
    Thanks for your work on this. I’m working on a js program that needs json diffing, and I’m trying to work some examples. I tried the following examples to diff, and it seems like the elements that are the same are still getting returned. Do you have any insight on why this might be? All I changed was one value from lcsh to lcsh2, so that is all i would expect to see back from the diff. Thanks.

    json1: [[{"bb68609635":"lcsh"},{"bb17073259":"Anti-fascist movements"},{"bb04445165":"Spain"},{"bb17073259":"Posters"}],[{"bb68609635":"lcsh"},{"bb04445165":"Spain"},{"bb17073259":"History"},{"bb9147665h":"Civil War, 1936-1939"},{"bb17073259":"Propaganda"}]]

    json2:
    [[{"bb68609635":"lcsh"},{"bb17073259":"Anti-fascist movements"},{"bb04445165":"Spain"},{"bb17073259":"Posters"}],[{"bb68609635":"lcsh2"},{"bb04445165":"Spain"},{"bb17073259":"History"},{"bb9147665h":"Civil War, 1936-1939"},{"bb17073259":"Propaganda"}]]

    results i’m getting:
    {“0″: [{"bb68609635": "lcsh"}, {"bb17073259": "Anti-fascist movements"}, {"bb04445165": "Spain"}, {"bb17073259": "Posters"}], “1″: [{"bb68609635": "lcsh2"}, {"bb04445165": "Spain"}, {"bb17073259": "History"}, {"bb9147665h": "Civil War, 1936-1939"}, {"bb17073259": "Propaganda"}]}

    thanks!

    25. februar, 2008 at 23:08:59

  3. Matt

    please disregard, this was an issue in my code, not yours. thanks again for this!

    26. februar, 2008 at 01:02:41

  4. Basement Hum

    This looks very interesting. Have you tried integrating something like this with a scm like git for projects that include JSON files that need structural diffing rather than a purely line based comparison? I’m trying to find information about how to to do structural JSON diffing for max/msp projects managed by git.

    26. februar, 2009 at 11:19:44

  5. Michael Schøler

    Thanks! No, I have not tried using the diffs in that manner. I’d like to know about your results, and if you found my jsonDiff useful for the task.

    26. februar, 2009 at 18:06:51

  6. Roberto

    Are you aware of a porting of your tool to python or any other server side language? I’m using json to exchange data between two application and your tool would save some bandwidth, however i cannot use it since there is no javascript interpreter on my platform.

    13. april, 2010 at 16:33:27

  7. MB

    I’m going to be making use of your diff and merge methods in conjunction with google-diff-match-patch.

    The combo lib/methods will be released as a utility distribution for Joose v3 via GitHub; after some refinement perhaps via openjsan too.

    As it will be a derivative work, it then needs to be licensed as LGPL (per your LGPL licensing), but I was wondering if you’d be willing to (re)license your jsonDataHandler with dual licenses, namely MIT *and* LGPL.

    If so, I would then license dual-license my work under MIT and LGPL.

    Dual-licesning is growingly increasingly popular so I was hoping you’d consider this change, but I’ll understand if you wish not to do so.

    12. august, 2010 at 20:50:58

  8. Michael Schøler

    Sure thing – consider this my OK for MIT licensing also. (I’ve updated the displayed src in the blog post also).

    I’m not trying to hinder anyone from using it for any form or purpose.

    So just go nuts! Enjoy! =)

    22. august, 2010 at 18:17:57

Send en kommentar