379517 - (jsonsync) JSON sync code

Status: RESOLVED FIXED

(Core :: General, defect)

Description

[Robert Sayre]

Comment 1

[Robert Sayre]

Attachment: sync.js

Comment 2

[Robert Sayre]

Attachment: test.js

Comment 3

[Robert Sayre]

Attachment: sync.js

Comment 4

[Robert Sayre]

Attachment: test.js

Comment 5

[Robert Sayre]

this code is almost done. It's not very long, but it's surprisingly dense. Right now, it only has an API for commands that should be propagated to all replicas. It detects conflicts correctly in almost all cases, I just haven't exposed API for it. The remaining edge case is handling an edit from {} to [] at the same path, like:

{"foo": {"bar":{"baz:"hmm"}}} 

to 

{"foo": {"bar":["hmm"]}}

The algorithm calls this an "edit" operation at path /foo/bar from {} to []. Need to make sure accompanying child deletions and creations happen in a sound sequence in the presence of conflicts. This is the only aspect of JSON not accounted for in the Ramsey paper, so I'll have to do a little math.

Here's a shell example of syncing two replicas, as one might do over HTTP:

js> load("/Users/sayrer/Cosimo/js/MochiKit_Base.js");
js> load("/Users/sayrer/Cosimo/js/MochiKit_Iter.js");
js> load("/Users/sayrer/Cosimo/js/sync.js");

js> /* start from the same copy */
js> var originalJSON = {"foo": {"bar": "baz"}, "toBeRemoved":"goner", 
                        "someArray":["tobeEdited"]}
js> var clientJSON   = {"foo": {"bar": "baz"}, "toBeRemoved":"goner", 
                        "someArray":["tobeEdited"]};
js> var serverJSON   = {"foo": {"bar": "baz"}, "toBeRemoved":"goner", 
                        "someArray":["tobeEdited"]};

js> /* make disconected edits */
js> clientJSON["foo"]["clientAddition"] = "the client added this";
the client added this
js> serverJSON["foo"]["serverAddition"] = "the server added this";
the server added this
js> delete clientJSON["toBeRemoved"]
true
js> delete serverJSON["toBeRemoved"]
true
js> clientJSON["someArray"][0] = "been edited";
been edited
js> serverJSON["someArray"][0] = "been edited";
been edited

js> /* figure out which edits to propagate to each replica */
js> var propagations = reconcile([detectUpdates(originalJSON, clientJSON), 
                                  detectUpdates(originalJSON, serverJSON)]);
js> applyCommands(clientJSON, propagations[0]);
js> applyCommands(serverJSON, propagations[1]);

js> /* since none of our edits conflict, each copy has all edits */
js> clientJSON["foo"]["bar"] == serverJSON["foo"]["bar"]
true
js> clientJSON["foo"]["clientAddition"] == serverJSON["foo"]["clientAddition"]        
true
js> clientJSON["foo"]["serverAddition"] == serverJSON["foo"]["serverAddition"]
true
js> clientJSON["toBeRemoved"] == undefined
true
js> serverJSON["toBeRemoved"] == undefined
true
js> clientJSON["someArray"][0] == serverJSON["someArray"][0]
true

js> /* now all the fields are the same, we work from this state */
js> originalJSON = { "foo": {"bar":"baz", 
                             "clientAddition":"the client added this", 
                             "serverAddition":"the server added this"}, 
                     "someArray":["been edited"] };
[object Object]

js> /* so we synced once, let's edit and sync again */
js> clientJSON["someArray"][0] = "edited again";
edited again
js> serverJSON["foo"]["bar"] = "edit some other field";
edit some other field

/* sync again */
js> propagations = reconcile([detectUpdates(originalJSON, clientJSON), 
                              detectUpdates(originalJSON, serverJSON)]);
[object Object],[object Object]
js> applyCommands(clientJSON, propagations[0]);
js> applyCommands(serverJSON, propagations[1]);

/* once again, we have each other's edits */
js> serverJSON["someArray"][0]
edited again
js> clientJSON["foo"]["bar"]
edit some other field
js>

Comment 6

[Robert Sayre]

Attachment: test.js

more tests

Comment 7

[Robert Sayre]

Attachment: sync.js with mochikit inlined

we don't need everything I inlined, but this will get us going.

Comment 8

[Robert Sayre]

Attachment: fix some conflict bugs, add tests

~> firefox/mozilla/fb-debug/dist/bin/run-mozilla.sh firefox/mozilla/fb-debug/dist/bin/xpcshell -f /Users/sayrer/Cosimo/js/MochiKit_Base.js -f /Users/sayrer/Cosimo/js/MochiKit_Iter.js -f /Users/sayrer/Cosimo/js/sync.js -f /Users/sayrer/Cosimo/js/test.js 
Type Manifest File: /Users/sayrer/firefox/mozilla/fb-debug/dist/bin/components/xpti.dat


Tests Starting
--------------
OK:   isObjectOrArray detects an object
OK:   isObjectOrArray detects an array
OK:   isObjectOrArray shouldn't detect string
OK:   isObjectOrArray shouldn't detect integer
OK:   isObjectOrArray shouldn't detect float
OK:   isObjectOrArray shouldn't detect undefined
OK:   isObjectOrArray shouldn't detect null
OK:   shouldn't be any suspects for matching primitives
OK:   should detect edited primitives
OK:   should detect matching objects
OK:   should detect primitive type change
OK:   should detect string edit
OK:   should detect differing keys
OK:   should not detect key type changes
OK:   created empty object is length 1
OK:   created primitive is length 1
OK:   created populated object is length 2
OK:   created populated object is length 3
OK:   create action is correct
OK:   creation paths in preorder
OK:   creation paths in preorder
OK:   create has correct value
OK:   creation paths in preorder
OK:   create has correct value
OK:   removed empty object is length 1
OK:   removed primitive is length 1
OK:   removed populated object is length 2
OK:   removed populated object is length 3
OK:   remove action is correct
OK:   removal paths in postorder
OK:   removal paths in postorder
OK:   removal paths in postorder
OK:   primitive edit is length 1
OK:   edit action is correct
OK:   edit has correct value
OK:   edit path is correct
OK:   obj2primitive contains removals
OK:   edits precede removals
OK:   remove action is there
OK:   primitive2object contains creations
OK:   edits precede creations
OK:   create action is there
OK:   replica1 has correct number of updates
OK:   replica1 should have an edit
OK:   replica1 should have value 0
OK:   replica2 has correct number of updates
OK:   replica2 should have an edit
OK:   replica2 should have value 0
OK:   replica3 has correct number of updates
OK:   replica3 should have an edit
OK:   replica3 should have value 0
OK:   replica4 has correct number of updates
OK:   replica4 should have an edit
OK:   replica4 should have value 0
OK:   instanceof
OK:   equals method of Command works
OK:   findValue locates Command object
OK:   equals method of Command detects type changes
OK:   equals method of Command matches {} values
OK:   equals method of Command matches [] values
OK:   equals method of Command detects obj vs. primitive
OK:   commandInList matches identical
OK:   commandInList matches removes
OK:   edits match
OK:   commandInList fails differing values
OK:   doesConflict finds identical paths with different values
OK:   doesConflict ignores mismatched paths
OK:   applying edit commands works
OK:   correct number of propogation arrays
OK:   correct number of commands to exec
OK:   is it an edit?
OK:   replica.foo is zero
OK:   replica.bar is zero
OK:   replica.baz is zero
OK:   replica.qux is zero
OK:   replica.foo is zero
OK:   replica.bar is zero
OK:   replica.baz is zero
OK:   replica.qux is zero
OK:   replica.foo is zero
OK:   replica.bar is zero
OK:   replica.baz is zero
OK:   replica.qux is zero
OK:   replica.foo is zero
OK:   replica.bar is zero
OK:   replica.baz is zero
OK:   replica.qux is zero
OK:   detect correct number of updates
OK:   /x action
OK:   /x value
OK:   /x path
OK:   /new action
OK:   /new value
OK:   /new path
OK:   /b/new2 action
OK:   /b/new2 value
OK:   /b/new2 path
OK:   /b/d/f action
OK:   /b/d/f value
OK:   /b/d/f path
OK:   /b/g action
OK:   /b/g value
OK:   /b/g path
OK:   /h action
OK:   /h value
OK:   /h path
OK:   /i/3 action
OK:   /i/3 value
OK:   /i/3 path
OK:   /k/m action
OK:   /k/m value
OK:   /k/m path
OK:   /k action
OK:   /k value
OK:   /k path
OK:   /n action
OK:   /n value
OK:   /n path
OK:   /n/new3 action
OK:   /n/new3 value
OK:   /n/new3 path
OK:   /x action
OK:   /x value
OK:   /x path
OK:   /a action
OK:   /a value
OK:   /a path
OK:   /b/c action
OK:   /b/c value
OK:   /b/c path
OK:   /b/d/f action
OK:   /b/d/f value
OK:   /b/d/f path
OK:   /i/3 action
OK:   /i/3 value
OK:   /i/3 path
OK:   /x in sync
OK:   /x correct value
OK:   /a in sync
OK:   /a correct value
OK:   /new in sync
OK:   /new correct value
OK:   /b/c in sync
OK:   /b/c correct value
OK:   /b/new2 in sync
OK:   /b/new2 correct value
OK:   /b/d/f in sync
OK:   /b/d/f correct value
OK:   /b/g in sync
OK:   /b/g correct value
OK:   /b/foo in sync
OK:   /b/foo correct value
OK:   /h in sync
OK:   /h correct value
OK:   /i/3 in sync
OK:   /i/3 correct value
OK:   /k in sync
OK:   /k correct value
OK:   /n/new3 in sync
OK:   /n/new3 correct value
OK:   /j in sync
OK:   /j correct value
OK:   unchanged fields remain
OK:   server has client addition
OK:   client has server addition
OK:   removed from client
OK:   removed from server
OK:   identically edited array ok
OK:   repeated edit works
OK:   repeated edit works
OK:   identical commands don't conflict
OK:   complete edit conflict should have no propagations
OK:   complete edit conflict should have no propagations
OK:   single edit field conflicting should have one conflict
OK:   single edit field conflicting should have one conflict
OK:   complete create conflict should have no propagations
OK:   complete create conflict should have no propagations
OK:   single create field conflicting should have one conflict
OK:   single create field conflicting should have one conflict

Tests Complete
--------------
Passed: 179
Failed: 0

Comment 9

[Robert Sayre]

Attachment: fix hierarchical conflict detection, add tests

Comment 10

[Robert Sayre]

Attachment: fix definition of break, conflict based on previous conflicts where needed, add tests

Comment 11

[Robert Sayre]

Attachment: updated full file

This has a little bit of extra stuff at the bottom... starting on an OO-damaged API. ;)

Comment 12

[Robert Sayre]

Attachment: updated tests

Comment 13

[Garrett Smith]

Rob,

Please remember to add a description. 

It helps me to understand the use case if I can read a brief summary of
the bug description.

"How would you describe the bug, in approximately 60 or fewer characters?"
http://developer.mozilla.org/en/docs/Bug_writing_guidelines

thanks.

Comment 14

[Robert Sayre]

now available here:

http://github.com/sayrer/json-sync