Create a gist now

Instantly share code, notes, and snippets.

What would you like to do?
ChangeList library to do OT on JSON and Strings.
var ChangeList = {};
if (typeof module !== 'undefined') {
module.exports = ChangeList;
}
// Creates a new change list struct.
//
ChangeList.create = function(type) {
var type = type || ChangeList.Object;
return {
type: type,
types: {},
version: 0,
snapshot: {version: 0, content: ChangeList.zero(type), cursors: {}},
changeList: [],
newChanges: []
};
};
ChangeList.Set = 1;
ChangeList.Number = 2;
ChangeList.String = 3;
ChangeList.Object = 4;
ChangeList.Boolean = 5;
ChangeList.Value = 6;
ChangeList.zero = function(type) {
switch(type) {
case ChangeList.Object: return {};
case ChangeList.String: return '';
case ChangeList.Set: return [];
case ChangeList.Number: return 0;
case ChangeList.Boolean: return false;
case ChangeList.Value: return null;
default: throw Error("Unknown type");
}
};
ChangeList.typeOf = function(value) {
switch(typeof value) {
case 'object':
if (value instanceof Array) {
return ChangeList.Set;
} else {
return ChangeList.Object;
}
case 'string': return ChangeList.String;
case 'number': return ChangeList.Number;
case 'boolean': return ChangeList.Boolean;
default: return null;
}
};
ChangeList.cursor = function(cl, id) {
return ChangeList.exec(cl).cursors[id];
};
Object.clone = function(obj) {
switch (typeof obj) {
case 'string': return obj.slice(0);
case 'object':
if (obj instanceof Array) {
return obj.map(Object.clone);
} else {
var o = {};
for (var i in obj) {
o[i] = Object.clone(obj[i]);
}
return o;
}
default: return obj;
}
};
ChangeList.exec = function(ch) {
var cl = ChangeList.changesSince(ch, ch.snapshot.version);
var str = ch.snapshot.content;
var cursors = Object.clone(ch.snapshot.cursors);
var i,j,cll,c;
for (i=0; i<cl.length; i++) {
cll = cl[i].changes;
for (j=0; j<cll.length; j++) {
c = cll[j];
str = ChangeList.processChange(c, str, cursors, ch.type, ch.types);
}
}
ch.snapshot.version = ch.version;
ch.snapshot.cursors = Object.clone(cursors);
ch.snapshot.content = Object.clone(str);
cll = ch.newChanges;
for (j=0; j<cll.length; j++) {
c = cll[j];
str = ChangeList.processChange(c, str, cursors, ch.type, ch.types);
}
return {cursors: cursors, result: str};
};
ChangeList.processChange = function(c, str, cursors, type, types) {
switch(type) {
case ChangeList.Object: return ChangeList.processObjectChange(c, str, cursors, types);
case ChangeList.String: return ChangeList.processStringChange(c, str, cursors);
case ChangeList.Set: return ChangeList.processSetChange(c, str, cursors);
case ChangeList.Value: return c.set;
case ChangeList.Number: return c.set;
case ChangeList.Boolean: return c.set;
default: throw Error("Unknown type");
}
};
ChangeList.processObjectChange = function(c, str, cursors, types) {
if (c.add !== undefined) {
if (ChangeList.typeOf(str[c.add]) !== c.type) {
types[c.add] = c.type;
str[c.add] = ChangeList.zero(c.type);
}
}
if (c.edit !== undefined) {
var v = str[c.edit];
cursors[c.edit] = cursors[c.edit] || {};
str[c.edit] = ChangeList.processChange(c.value, v, cursors[c.edit], ChangeList.typeOf(v));
}
if (c.del !== undefined) {
delete str[c.del];
}
return str;
};
ChangeList.processSetChange = function(c, str, cursors) {
var i, v, found;
if (c.add !== undefined) {
v = JSON.stringify(c.add);
found = false;
for (i=0; i<str.length; i++) {
if (JSON.stringify(str[i]) === v) {
found = true;
break;
}
}
if (!found) {
str.push(c.add);
}
}
if (c.del !== undefined) {
v = JSON.stringify(c.del);
for (i=0; i<str.length; i++) {
if (JSON.stringify(str[i]) === v) {
str.splice(i, 1);
break;
}
}
}
return str;
};
ChangeList.processStringChange = function(c, str, cursors) {
var cursor = cursors.__current;
if (c.cursor !== undefined) {
cursor = {id: c.cursor.id, pos: Math.max(0, Math.min(str.length, c.cursor.pos))};
cursors.__current = cursor;
cursors[cursor.id] = cursor;
}
if (c.add !== undefined) {
var start = str.substring(0, cursor.pos);
var end = str.slice(cursor.pos);
str = start + c.add + end;
for (var n in cursors) {
var nc = cursors[n];
if (nc.id !== cursor.id && cursor.pos <= nc.pos) {
nc.pos += c.add.length;
}
}
cursor.pos += c.add.length;
}
if (c.del !== undefined) {
var start = str.substring(0, cursor.pos);
var end = str.slice(cursor.pos + c.del);
str = start + end;
for (var n in cursors) {
var nc = cursors[n];
if (nc.id !== cursor.id && cursor.pos < nc.pos) {
nc.pos = Math.max(cursor.pos, nc.pos - c.del);
}
}
}
return str;
};
ChangeList.sync = function(master, client) {
ChangeList.append(master, client);
var changes = ChangeList.changesSince(master, client.version);
ChangeList.applyChanges(client, changes);
};
ChangeList.addChange = function(cl, change) {
cl.newChanges.push(change);
};
// Appends the src changeList to dst.
ChangeList.append = function(dst, src) {
dst.version++;
var cs = ChangeList.changesSince(dst, src.version);
var changes = ChangeList.normalize(cs, src.newChanges, dst.type, dst.types);
dst.changeList.push({version: dst.version, changes: changes});
};
ChangeList.normalize = function(prev, changes, type, types) {
if (type === ChangeList.String) {
return ChangeList.normalizeString(prev, changes);
} else if (type === ChangeList.Object) {
return ChangeList.normalizeObject(prev, changes, types);
}
return changes.slice(0);
};
ChangeList.normalizeObject = function(prev, changes, types) {
changes = changes.slice(0);
var subs = {};
var subArr = [];
for (var j=0; j<prev.length; j++) {
var cl = prev[j].changes;
for (var k=0; k<cl.length; k++) {
var ch = cl[k];
if (ch.edit !== undefined) {
var t = types[ch.edit];
if (t === ChangeList.Object || t === ChangeList.String) {
var obj = subs[ch.edit];
if (!obj) {
obj = {type: types[ch.edit], prev: [{changes: []}], changes: []};
subs[ch.edit] = obj;
subArr.push(obj);
}
obj.prev[0].changes.push(ch.value);
}
}
}
}
for (var i=0; i<changes.length; i++) {
var ch = changes[i];
if (ch.edit !== undefined) {
var t = types[ch.edit];
if (t === ChangeList.Object || t === ChangeList.String) {
var obj = subs[ch.edit];
if (!obj) {
obj = {type: types[ch.edit], prev: [{changes: []}], changes: []};
subs[ch.edit] = obj;
subArr.push(obj);
}
obj.changes.push(ch.value);
}
}
}
for (var i=0; i<subArr.length; i++) {
var sub = subArr[i];
ChangeList.normalize(sub.prev, sub.changes, sub.type, {});
}
return changes;
};
ChangeList.normalizeString = function(prev, changes) {
changes = changes.slice(0);
for (var j=0; j<prev.length; j++) {
var cl = prev[j].changes;
for (var k=0; k<cl.length; k++) {
var ch = cl[k];
if (ch.cursor !== undefined || ch.add !== undefined || ch.del !== undefined) {
for (var i=0; i<changes.length; i++) {
var c = changes[i];
var chPos = 0;
if (c.cursor !== undefined) {
if (ch.cursor !== undefined) {
chPos = ch.cursor.pos;
}
if (ch.add !== undefined) {
if (chPos <= c.cursor.pos) {
c.cursor.pos += ch.add.length;
}
chPos += ch.add.length;
}
if (ch.del !== undefined) {
if (chPos < c.cursor.pos) {
c.cursor.pos = Math.max(chPos, c.cursor.pos - ch.del);
}
}
}
}
}
}
}
return changes;
};
// Returns a list of changes that have taken place after the given version.
ChangeList.changesSince = function(cl, version) {
var changeList = cl.changeList, i = cl.changeList.length-1;
while (i >= 0 && changeList[i].version > version) {
i--;
}
return changeList.slice(i+1);
};
// Applies a changes array returned by changesSince to changeList.
// Overwrites newChanges.
ChangeList.applyChanges = function(changeList, changes) {
changeList.newChanges.splice(0);
if (changes.length > 0) {
var cl = changeList.changeList;
for (var i=0; i<changes.length; i++) {
cl.push(changes[i]);
changeList.version = changes[i].version;
}
}
};
var assertEq = function(a, b) {
if (a != b) {
throw Error("assertEq: "+a+' != '+b);
}
}
ChangeList.test = function() {
this.testString();
this.testObject();
this.testStringRandom();
};
ChangeList.testObject = function() {
var master = ChangeList.create(ChangeList.Object);
var a = ChangeList.create(ChangeList.Object);
var b = ChangeList.create(ChangeList.Object);
var cl = ChangeList;
cl.addChange( a, {add: "x", type: cl.Number} );
cl.addChange( a, {edit: "x", value: {set: 2}} );
cl.addChange( b, {add: "y", type: cl.Number} );
cl.addChange( b, {edit: "y", value: {set: 5}} );
assertEq(null, cl.exec(master).result.x);
assertEq(null, cl.exec(master).result.y);
assertEq(2, cl.exec(a).result.x);
assertEq(null, cl.exec(a).result.y);
assertEq(null, cl.exec(b).result.x);
assertEq(5, cl.exec(b).result.y);
cl.sync(master, a);
cl.sync(master, b);
cl.sync(master, a);
assertEq(2, cl.exec(master).result.x);
assertEq(5, cl.exec(master).result.y);
assertEq(2, cl.exec(a).result.x);
assertEq(5, cl.exec(a).result.y);
assertEq(2, cl.exec(b).result.x);
assertEq(5, cl.exec(b).result.y);
cl.addChange( a, {add: 'published', type: cl.Boolean} );
cl.addChange( a, {edit: 'published', value: {set: true}} );
cl.addChange( b, {add: 'published', type: cl.Boolean} );
cl.addChange( b, {add: 'body', type: cl.String} );
ChangeList.addChange(b, {edit: 'body', value: {cursor: {id: 'b', pos: 0}}});
ChangeList.addChange(b, {edit: 'body', value: {add: "Hel"}});
ChangeList.addChange(b, {edit: 'body', value: {add: "lo!"}});
cl.sync(master, a);
cl.sync(master, b);
cl.sync(master, a);
assertEq(true, cl.exec(master).result.published);
assertEq(true, cl.exec(a).result.published);
assertEq(true, cl.exec(b).result.published);
assertEq("Hello!", cl.exec(master).result.body);
assertEq("Hello!", cl.exec(a).result.body);
assertEq("Hello!", cl.exec(b).result.body);
ChangeList.addChange(a, {edit: 'body', value: {cursor: {id: 'a', pos: 5}}});
ChangeList.addChange(a, {edit: 'body', value: {add: ", World"}});
ChangeList.addChange(b, {edit: 'body', value: {cursor: {id: 'b', pos: 6}}});
ChangeList.addChange(b, {edit: 'body', value: {add: " I feel fine."}});
ChangeList.addChange(b, {edit: 'body', value: {cursor: {id: 'b', pos: 14}}});
ChangeList.addChange(b, {edit: 'body', value: {del: 4}});
ChangeList.addChange(b, {edit: 'body', value: {add: "SUPER"}});
ChangeList.addChange(b, {add: 'acl', type: cl.Set});
ChangeList.addChange(b, {edit: 'acl', value: {add: {user: "James", cap: "read"}}});
ChangeList.addChange(b, {edit: 'acl', value: {add: {user: "James", cap: "dance"}}});
cl.sync(master, a);
cl.sync(master, b);
cl.sync(master, a);
assertEq("Hello, World! I feel SUPER.", cl.exec(master).result.body);
ChangeList.addChange(a, {edit: 'acl', value: {add: {user: "James", cap: "write"}}});
ChangeList.addChange(a, {edit: 'acl', value: {add: {user: "James", cap: "read"}}});
ChangeList.addChange(a, {edit: 'acl', value: {del: {user: "James", cap: "dance"}}});
cl.sync(master, a);
cl.sync(master, b);
cl.sync(master, a);
assertEq("Hello, World! I feel SUPER.", cl.exec(master).result.body);
assertEq("Hello, World! I feel SUPER.", cl.exec(a).result.body);
assertEq("Hello, World! I feel SUPER.", cl.exec(b).result.body);
var caps = cl.exec(master).result.acl;
assertEq(JSON.stringify(caps.sort()), JSON.stringify(([{user: "James", cap: "read"}, {user: "James", cap: "write"}]).sort()));
console.log("testObject OK");
};
ChangeList.testString = function() {
var master = ChangeList.create(ChangeList.String);
var a = ChangeList.create(ChangeList.String);
var b = ChangeList.create(ChangeList.String);
ChangeList.addChange(a, {cursor: {id: 'a', pos: 0}});
ChangeList.addChange(a, {add: "Der "});
ChangeList.addChange(b, {cursor: {id: 'b', pos: 0}});
ChangeList.addChange(b, {add: "Wie"});
ChangeList.addChange(b, {add: "nin"});
assertEq("", ChangeList.exec(master).result);
assertEq("Der ", ChangeList.exec(a).result);
assertEq("Wienin", ChangeList.exec(b).result);
ChangeList.sync(master, a);
ChangeList.sync(master, b);
ChangeList.sync(master, a);
assertEq("Der Wienin", ChangeList.exec(master).result);
assertEq("Der Wienin", ChangeList.exec(a).result);
assertEq("Der Wienin", ChangeList.exec(b).result);
ChangeList.addChange(b, {cursor: {id: 'b', pos: 4}});
ChangeList.addChange(b, {add: "Wiener"});
ChangeList.addChange(a, {cursor: {id: 'a', pos: 4}});
ChangeList.addChange(a, {add: "sch"});
ChangeList.addChange(a, {add: "ni"});
ChangeList.addChange(a, {cursor: {id: 'a', pos: 15}});
ChangeList.addChange(a, {add: "leike"});
ChangeList.sync(master, b);
ChangeList.sync(master, a);
ChangeList.sync(master, b);
assertEq("Der WienerschniWieninleike", ChangeList.exec(master).result);
assertEq("Der WienerschniWieninleike", ChangeList.exec(a).result);
assertEq("Der WienerschniWieninleike", ChangeList.exec(b).result);
ChangeList.addChange(b, {cursor: {id: 'b', pos: 15}, add: "tzel = "});
ChangeList.addChange(b, {cursor: {id: 'b', pos: 20}, del: 1});
ChangeList.addChange(b, {add: "on"});
ChangeList.addChange(a, {cursor: {id: 'a', pos: ChangeList.exec(a).result.length}});
ChangeList.addChange(a, {add: "."});
ChangeList.sync(master, b);
ChangeList.sync(master, a);
ChangeList.sync(master, b);
assertEq("Der Wienerschnitzel on Wieninleike.", ChangeList.exec(master).result);
assertEq("Der Wienerschnitzel on Wieninleike.", ChangeList.exec(a).result);
assertEq("Der Wienerschnitzel on Wieninleike.", ChangeList.exec(b).result);
assertEq(ChangeList.exec(b).result.length, ChangeList.cursor(master, 'a').pos);
assertEq("Der Wienerschnitzel on".length, ChangeList.cursor(master, 'b').pos);
console.log("testString OK");
};
ChangeList.testStringRandom = function() {
var makeDoc = function() {
var cl = ChangeList.create(ChangeList.Object);
props.forEach(function(prop) {
ChangeList.addChange(cl, {add: prop, type: ChangeList.String});
});
return cl;
};
var props = ['slides', 'notes', 'script'];
var a, b, c, master;
for (var i=0; i<10; i++) {
a = makeDoc();
a.id = 'a';
b = makeDoc();
b.id = 'b';
c = makeDoc();
master = makeDoc();
var t = Date.now();
var changes = 0;
var written = 0;
console.log('test run '+(i+1));
for (var j=0; j<10000; j++) {
var r = Math.random();
var tgt = (r > 0.5) ? a : b;
var tgtProp = props[(Math.random()*3) | 0];
ChangeList.addChange(tgt, {edit: tgtProp, value: {cursor: {id: tgt.id, pos: (Math.random()*6000) | 0}}});
for (var k=0; k<20; k++) {
var cmd;
if (Math.random() > 0.7) {
var str = "";
for (var l=0,len=Math.random()*10; l<len; l++) {
str += String.fromCharCode((Math.random()*26+65) | 0);
}
written += str.length;
cmd = {add: str};
} else if (Math.random() > 0.5) {
cmd = {del: (Math.random()*10) | 0}
} else {
cmd = {cursor: {id: tgt.id, pos: (Math.random()*6000) | 0}};
}
ChangeList.addChange(tgt, {edit: tgtProp, value: cmd});
}
ChangeList.sync(master, tgt);
//assertEq( JSON.stringify(ChangeList.exec(master)), JSON.stringify(ChangeList.exec(tgt)) );
}
ChangeList.sync(master, a);
ChangeList.sync(master, b);
ChangeList.sync(master, a);
var elapsed = Date.now() - t;
ChangeList.sync(master, c);
var syncElapsed = (Date.now() - t) - elapsed;
var execM0 = Date.now();
var mr = ChangeList.exec(master)
var execMElapsed = Date.now() - execM0;
var execA0 = Date.now();
ChangeList.exec(master);
var execAElapsed = Date.now() - execA0;
var ar = ChangeList.exec(a);
var br = ChangeList.exec(b);
var execT0 = Date.now();
var cr = ChangeList.exec(c);
var execElapsed = Date.now() - execT0;
assertEq(JSON.stringify(mr), JSON.stringify(ar));
assertEq(JSON.stringify(mr), JSON.stringify(br));
assertEq(JSON.stringify(mr), JSON.stringify(cr));
//console.log(n+": "+JSON.stringify(mr));
if (i === 0) {
changes = master.changeList.reduce(function(s,i) { return s + i.changes.length; }, 0);
console.log("wrote "+written+" characters, " + changes + " changes in "+elapsed+" ms ("+Math.floor(1000*changes/elapsed)+" / sec)");
console.log("exec changes in "+execElapsed+" ms ("+Math.floor(1000*changes/execElapsed)+" / sec)");
console.log("sync to an empty doc " +syncElapsed+ " ms, first exec: "+execMElapsed+" ms, subsequent exec: "+ execAElapsed+" ms");
console.log("snapshot JSON size: "+JSON.stringify(master.snapshot).length+ " B, changelog size: "+gzip(JSON.stringify(master.changeList)).length+" B");
props.forEach(function(n) {
var snapshot = master.snapshot;
console.log(n+" size: "+snapshot.content[n].length+" B");
});
}
}
};
var gzip = function(str) {
var gz = require('zlib').createGzip();
gz.end(str);
var rb = 0;
gz.on('data', function(c) { rb += c.length; });
gz.on('end', function() { console.log("GZIP change list: " + str.length + " -> " + rb + " (" + Math.floor(100*(rb/str.length)) + "%)"); });
return str;
};
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment