Closed Bug 379517 (jsonsync) Opened 18 years ago Closed 16 years ago

JSON sync code

Categories

(Core :: General, defect)

Product:
Core
Component:
General
Platform:
x86
macOS
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: sayrer, Assigned: sayrer)

Details

Attachments

(2 files, 9 obsolete files)

updated full file
17.36 KB, application/x-javascript
Details
updated tests
23.23 KB, application/x-javascript
Details
Attached file sync.js (obsolete) —
Attached file test.js (obsolete) —
Assignee: nobody → sayrer
Status: NEW → ASSIGNED
Attached patch sync.js (obsolete) — — Splinter Review
Attachment #263522 - Attachment is obsolete: true
Attached patch test.js (obsolete) — — Splinter Review
Attachment #263523 - Attachment is obsolete: true
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>
Attached file test.js (obsolete) —
more tests
Attachment #263532 - Attachment is obsolete: true
Alias: jsonsync
Attached file sync.js with mochikit inlined (obsolete) —
we don't need everything I inlined, but this will get us going.
~> 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
Attachment #267529 - Attachment is obsolete: true
Attached file updated full file —
This has a little bit of extra stuff at the bottom... starting on an OO-damaged API. ;)
Attachment #263531 - Attachment is obsolete: true
Attachment #263882 - Attachment is obsolete: true
Attachment #267348 - Attachment is obsolete: true
Attachment #267678 - Attachment is obsolete: true
Attached file updated tests —
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.
now available here: http://github.com/sayrer/json-sync
Status: ASSIGNED → RESOLVED
Closed: 16 years ago
Resolution: --- → FIXED
You need to log in before you can comment on or make changes to this bug.

Attachment

General

Creator:
Created:
Updated:
Size: