autonome / json-sync Goto Github PK

This file contains a simple synchronization method for JSON objects
based on the file synchronization algorithm presented by Norman Ramsey
and Elod Csirmaz in

   An Algebraic Approach to File Synchronization
   <http://www.eecs.harvard.edu/~nr/pubs/sync-abstract.html>

   Abstract: "We present a sound and complete proof system for
   reasoning about operations on filesystems. The proof system
   enables us to specify a file-synchronization algorithm that can
   be combined with several different conflict-resolution
   policies. By contrast, previous work builds the
   conflict-resolution policy into the specification, or worse, does
   not specify the behavior formally. We present several
   alternatives for conflict resolution, and we address the knotty
   question of timestamps."

We map this algorithm to JSON records by giving object and array
values the same treatment that Ramsey and Csirmaz give file system
directories.


This algorithm requires that we keep a snapshot around, such as the
last response from a server.

var snapshotJSON =
{
  "x": 42,
  "a": 1,
  "b":
  {
    "c": 2,
    "d":
    {
      "e": 3,
      "f": 4
    },
    "g": 5
  },
  "h": 6.6,
  "i": [7, 8, 9],
  "j": 10,
  "k": { "m": 11 },
  "n": 66,
}

After local updates have occured, the JSON object will have
changed. Our algorithm determines a sequence of updates to the
snapshot that result in an object approximating the current state. We
can perform this detection without logging each change by ignoring
sequences deemed to be insignificant. For example, the field "x" with
value 42 could be deleted and subsequently added with a value of
43. Our algorithm will not track these changes.  The key is present in
both JSON objects, so the change will be represented as an edit.

var currentJSON =
{
  "x": 43,             /* edited */ 
  "a": 1,
  "new": 11,           /* created */
  "b":
  {
    "c": 2,
    "new2": 22,        /* created */
    "d":
    {
      "e": 3,
      /*"f": 4*/       /* removed */
    },
    "g": 55,           /* edited  */
  },
  /* "h": 6.6, */      /* removed */   
  "i": [7, 8, 9, 99],  /* added array element */
  "j": 10,
  "k": 42,             /* replaced object with primitive */
  "n": { "new3": 77 }, /* replaced primitive with object */
}


todo: Synchronizer object at the bottom of the file needs to be completed.
      Arrays need an identity function for their elements, so the algorithm
      can be more intuitive when elements move around.
      I bet you can design a better wire format!