ChangeList library to do OT on JSON and Strings.

changelist.js

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;
};