2008.01.15

JSON diffing

Kategori: JSON, Programmering — Michael Schøler, Kl. 21:02:12

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. // LGPL license, 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).

Enjoy!

5 kommentarer »

  1. Nice! That just might come in handy!

    Kommentar skrevet af Jakob Kruse
    D. 16/01-2008 Kl. 07:07:33

  2. 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!

    Kommentar skrevet af Matt
    D. 25/02-2008 Kl. 23:08:59

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

    Kommentar skrevet af Matt
    D. 26/02-2008 Kl. 01:02:41

  4. 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.

    Kommentar skrevet af Basement Hum
    D. 26/02-2009 Kl. 11:19:44

  5. 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.

    Kommentar skrevet af Michael Schøler
    D. 26/02-2009 Kl. 18:06:51

RSS feed for kommentarer til dette indlæg. TrackBack URI

Send kommentar

*
For at bevise at du er en person, og ikke en spam-robot, skal du indtaste dette kodeord. Bemærk at kodeordet altid starter eller slutter med et tal. Klik på billedet for at få kodeordet læst op.
Click to hear an audio file of the anti-spam word