OT Composition in JS

compose.js

var assert = require('assert');


function dump(actions, graph) {
  console.log();
  actions.forEach(function (action) {
    if (graph) {
      switch (action[0]) {
      case 'retain':
        process.stdout.write(new Array(action[1] + 1).join('>') + ' | ');
        break;
      case 'insert':
        process.stdout.write(action[1] + ' | ');
        break;
      case 'delete':
        process.stdout.write(new Array(action[1] + 1).join('-') + ' | ');
        break;
      }
    } else {
      console.log(action[0], action[1]);
    }
  });
  console.log();
}




function compose(as, bs) {
  as = as.map(function (action) { return action.slice(); });
  bs = bs.map(function (action) { return action.slice(); });

  var cursor;

  cursor = 0;
  bs.forEach(function (b) {
    var b_len = getActionLength(b);
    if (b[0] === 'insert') {
      addRetainOfLengthAtIndex(as, b_len, cursor);
    }
    cursor += b_len;
  });

  cursor = 0;
  as.forEach(function (a) {
    var a_len = getActionLength(a);
    if (a[0] === 'delete') {
      addRetainOfLengthAtIndex(bs, a_len, cursor);
    }
    cursor += a_len;
  });

  var result = mergeActionStreams(as, bs);

  return result;
}


function getActionLength(action) {
  return action[1].length || action[1] || 0;
}


function addRetainOfLengthAtIndex(actions, len, index) {
  var retain = [ 'retain', len ];

  var cursor = 0;
  for (var i = 0, ii = actions.length; i < ii; ++i) {
    var action = actions[i];
    var action_len = getActionLength(action);
    var end_index = cursor + action_len;

    if (index <= end_index) {
      if (index < end_index) {
        var remainder = splitActionAtIndex(action, index - cursor);
        actions.splice(i + 1, 0, remainder);
      }

      actions.splice(i + 1, 0, retain);

      // Drop zero-length actions
      if (getActionLength(action) === 0) {
        actions.splice(i, 1);
      }
      return;
    }

    cursor += action_len;
  }

  throw new Error('Invalid state, index out of range');
}


function splitActionAtIndex(action, index) {
  var remainder = [ action[0] ];

  switch (action[0]) {
  case 'insert':
    remainder[1] = action[1].substr(index);
    action[1] = action[1].substr(0, index);
    break;
  default:
    remainder[1] = action[1] - index;
    action[1] = index;
  }

  return remainder;
}


function mergeActionStreams(as, bs) {
  var result = [];

  for (var i = 0; i < Math.max(as.length, bs.length); ++i) {
    var a = as[i];
    var b = bs[i];

    if (!a || !b) {
      var action = a || b;
      if (result.length !== 0 && action[0] === result[result.length - 1][0]) {
        result[result.length - 1] = joinActions(result[result.length - 1], action);
      } else {
        result.push(action);
      }
      break;
    }

    var a_len = getActionLength(a);
    var b_len = getActionLength(b);

    if (a_len !== b_len) {
      if (a_len < b_len) {
        var b_remainder = splitActionAtIndex(b, a_len);
        bs.splice(i + 1, 0, b_remainder);
      } else {
        var a_remainder = splitActionAtIndex(a, b_len);
        as.splice(i + 1, 0, a_remainder);
      }
    }

    // Merge actions
    var parts = mergeActions(a, b);
    // Join two consequential actions of the same type
    if (result.length !== 0 && parts[0] && parts[0][0] === result[result.length - 1][0]) {
      var part = parts.shift();
      result[result.length - 1] = joinActions(result[result.length - 1], part);
    }
    // Push the iteration parts to the result
    result.push.apply(result, parts);
  }

  return result;
}


function mergeActions(a, b) {
  switch (a[0]) {
  case 'retain':
    switch (b[0]) {
    case 'retain': return [ a ];
    default: return [ b ];
    }
  case 'insert':
    switch (b[0]) {
    case 'retain': return [ a ];
    case 'insert': return [ b, a ];
    case 'delete': return [];
    }
    break;
  case 'delete':
    switch (b[0]) {
    case 'retain': return [ a ];
    case 'insert': return [];
    case 'delete': throw new Error('Invalid state, cannot merge two delete actions');
    }
    break;
  }

  throw new Error('Unknown action type');
}


function joinActions(a, b) {
  var result = [ a[0], a[1] + b[1] ];
  return result;
}


// testing

function use(contents, actions) {
  contents = contents.slice();
  var cursor = 0;
  actions.forEach(function (action) {
    switch (action[0]) {
    case 'retain':
      cursor += action[1];
      break;
    case 'insert':
      contents.splice.apply(contents, [ cursor, 0 ].concat(action[1].split('')));
      cursor += action[1].length;
      break;
    case 'delete':
      contents.splice(cursor, action[1]);
      break;
    }
  });

  return contents;
}


function test(/* ...action sets */) {
  var ops = Array.prototype.slice.call(arguments);

  var state_a = new Array(9).join('0123456789abcdefghijklmnopqrstuvwxyz').split('');
  var state_b = state_a;

  var as = ops.shift();
  state_a = use(state_a, as);

  var bs;
  while (bs = ops.shift()) {
    state_a = use(state_a, bs);
    as = compose(as, bs);
  }

  //dump(composition);

  state_b = use(state_b, as);

  assert.equal(state_a.join(''), state_b.join(''));

  console.log('\nOK!');
}


exports.compose = compose;
exports.dump = dump;
exports.test = test;

test-01.js

var test = require('./compose').test;


var as = [
  [ 'retain', 4 ],
  [ 'insert', 'AB' ],
  [ 'retain', 3 ],
  [ 'delete', 2 ],
  [ 'retain', 4 ]
];

var bs = [
  [ 'retain', 3 ],
  [ 'insert', 'CD' ],
  [ 'retain', 1 ],
  [ 'delete', 3 ],
  [ 'retain', 1 ],
  [ 'insert', 'EF' ],
  [ 'retain', 2 ],
  [ 'delete', 2 ],
  [ 'retain', 1 ]
];


test(as, bs);

test-02.js

var test = require('./compose').test;


var as = [
  [ 'delete', 1 ],
  [ 'retain', 5 ],
  [ 'delete', 8 ],
  [ 'retain', 1 ],
  [ 'insert', 'yRunFmyJ' ],
  [ 'delete', 10 ],
  [ 'insert', 'p' ],
  [ 'retain', 200 ]
];

var bs = [
  [ 'insert', 'wEvque5f' ],
  [ 'retain', 10 ],
  [ 'delete', 15 ],
  [ 'delete', 14 ],
  [ 'insert', 'HL' ],
  [ 'retain', 200 + 1 + 8 - 10 ]
];


test(as, bs);

test-03.js

var test = require('./compose').test;


var as = [
  [ 'delete', 1 ],
  [ 'retain', 5 ],
  [ 'delete', 8 ],
  [ 'retain', 1 ],
  [ 'insert', 'yRunFmyJ' ],
  [ 'delete', 10 ],
  [ 'insert', 'p' ],
  [ 'retain', 200 ]
];

var bs = [
  [ 'insert', 'wEvque5f' ],
  [ 'retain', 10 ],
  [ 'delete', 15 ],
  [ 'delete', 14 ],
  [ 'insert', 'HL' ],
  [ 'retain', 200 + 1 + 8 - 10 ]
];

var cs = [
  [ 'retain', 10 ],
  [ 'insert', 'lolrofl' ],
  [ 'delete', 4 ],
  [ 'retain', 2 ],
  [ 'delete', 12 ],
  [ 'retain', 191 ]
];


test(as, bs, cs);