sky/framework/sky-element/observe.sky

<!--
// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.
-->

<script>
function detectEval() {
  // Don't test for eval if we're running in a Chrome App environment.
  // We check for APIs set that only exist in a Chrome App context.
  if (typeof chrome !== 'undefined' && chrome.app && chrome.app.runtime) {
    return false;
  }

  // Firefox OS Apps do not allow eval. This feature detection is very hacky
  // but even if some other platform adds support for this function this code
  // will continue to work.
  if (typeof navigator != 'undefined' && navigator.getDeviceStorage) {
    return false;
  }

  try {
    var f = new Function('', 'return true;');
    return f();
  } catch (ex) {
    return false;
  }
}

var hasEval = detectEval();

function isIndex(s) {
  return +s === s >>> 0 && s !== '';
}

function toNumber(s) {
  return +s;
}

function isObject(obj) {
  return obj === Object(obj);
}

function areSameValue(left, right) {
  if (left === right)
    return left !== 0 || 1 / left === 1 / right;
  if (Number.isNaN(left) && Number.isNaN(right))
    return true;

  return left !== left && right !== right;
}

var createObject = ('__proto__' in {}) ?
  function(obj) { return obj; } :
  function(obj) {
    var proto = obj.__proto__;
    if (!proto)
      return obj;
    var newObject = Object.create(proto);
    Object.getOwnPropertyNames(obj).forEach(function(name) {
      Object.defineProperty(newObject, name,
                           Object.getOwnPropertyDescriptor(obj, name));
    });
    return newObject;
  };

var identStart = '[\$_a-zA-Z]';
var identPart = '[\$_a-zA-Z0-9]';
var identRegExp = new RegExp('^' + identStart + '+' + identPart + '*' + '$');

function getPathCharType(char) {
  if (char === undefined)
    return 'eof';

  var code = char.charCodeAt(0);

  switch(code) {
    case 0x5B: // [
    case 0x5D: // ]
    case 0x2E: // .
    case 0x22: // "
    case 0x27: // '
    case 0x30: // 0
      return char;

    case 0x5F: // _
    case 0x24: // $
      return 'ident';

    case 0x20: // Space
    case 0x09: // Tab
    case 0x0A: // Newline
    case 0x0D: // Return
    case 0xA0:  // No-break space
    case 0xFEFF:  // Byte Order Mark
    case 0x2028:  // Line Separator
    case 0x2029:  // Paragraph Separator
      return 'ws';
  }

  // a-z, A-Z
  if ((0x61 <= code && code <= 0x7A) || (0x41 <= code && code <= 0x5A))
    return 'ident';

  // 1-9
  if (0x31 <= code && code <= 0x39)
    return 'number';

  return 'else';
}

var pathStateMachine = {
  'beforePath': {
    'ws': ['beforePath'],
    'ident': ['inIdent', 'append'],
    '[': ['beforeElement'],
    'eof': ['afterPath']
  },

  'inPath': {
    'ws': ['inPath'],
    '.': ['beforeIdent'],
    '[': ['beforeElement'],
    'eof': ['afterPath']
  },

  'beforeIdent': {
    'ws': ['beforeIdent'],
    'ident': ['inIdent', 'append']
  },

  'inIdent': {
    'ident': ['inIdent', 'append'],
    '0': ['inIdent', 'append'],
    'number': ['inIdent', 'append'],
    'ws': ['inPath', 'push'],
    '.': ['beforeIdent', 'push'],
    '[': ['beforeElement', 'push'],
    'eof': ['afterPath', 'push']
  },

  'beforeElement': {
    'ws': ['beforeElement'],
    '0': ['afterZero', 'append'],
    'number': ['inIndex', 'append'],
    "'": ['inSingleQuote', 'append', ''],
    '"': ['inDoubleQuote', 'append', '']
  },

  'afterZero': {
    'ws': ['afterElement', 'push'],
    ']': ['inPath', 'push']
  },

  'inIndex': {
    '0': ['inIndex', 'append'],
    'number': ['inIndex', 'append'],
    'ws': ['afterElement'],
    ']': ['inPath', 'push']
  },

  'inSingleQuote': {
    "'": ['afterElement'],
    'eof': ['error'],
    'else': ['inSingleQuote', 'append']
  },

  'inDoubleQuote': {
    '"': ['afterElement'],
    'eof': ['error'],
    'else': ['inDoubleQuote', 'append']
  },

  'afterElement': {
    'ws': ['afterElement'],
    ']': ['inPath', 'push']
  }
}

function noop() {}

function parsePath(path) {
  var keys = [];
  var index = -1;
  var c, newChar, key, type, transition, action, typeMap, mode = 'beforePath';

  var actions = {
    push: function() {
      if (key === undefined)
        return;

      keys.push(key);
      key = undefined;
    },

    append: function() {
      if (key === undefined)
        key = newChar
      else
        key += newChar;
    }
  };

  function maybeUnescapeQuote() {
    if (index >= path.length)
      return;

    var nextChar = path[index + 1];
    if ((mode == 'inSingleQuote' && nextChar == "'") ||
        (mode == 'inDoubleQuote' && nextChar == '"')) {
      index++;
      newChar = nextChar;
      actions.append();
      return true;
    }
  }

  while (mode) {
    index++;
    c = path[index];

    if (c == '\\' && maybeUnescapeQuote(mode))
      continue;

    type = getPathCharType(c);
    typeMap = pathStateMachine[mode];
    transition = typeMap[type] || typeMap['else'] || 'error';

    if (transition == 'error')
      return; // parse error;

    mode = transition[0];
    action = actions[transition[1]] || noop;
    newChar = transition[2] === undefined ? c : transition[2];
    action();

    if (mode === 'afterPath') {
      return keys;
    }
  }

  return; // parse error
}

function isIdent(s) {
  return identRegExp.test(s);
}

var constructorIsPrivate = {};

function Path(parts, privateToken) {
  if (privateToken !== constructorIsPrivate)
    throw Error('Use Path.get to retrieve path objects');

  for (var i = 0; i < parts.length; i++) {
    this.push(String(parts[i]));
  }

  if (hasEval && this.length) {
    this.getValueFrom = this.compiledGetValueFromFn();
  }
}

// TODO(rafaelw): Make simple LRU cache
var pathCache = {};

function getPath(pathString) {
  if (pathString instanceof Path)
    return pathString;

  if (pathString == null || pathString.length == 0)
    pathString = '';

  if (typeof pathString != 'string') {
    if (isIndex(pathString.length)) {
      // Constructed with array-like (pre-parsed) keys
      return new Path(pathString, constructorIsPrivate);
    }

    pathString = String(pathString);
  }

  var path = pathCache[pathString];
  if (path)
    return path;

  var parts = parsePath(pathString);
  if (!parts)
    return invalidPath;

  var path = new Path(parts, constructorIsPrivate);
  pathCache[pathString] = path;
  return path;
}

Path.get = getPath;

function formatAccessor(key) {
  if (isIndex(key)) {
    return '[' + key + ']';
  } else {
    return '["' + key.replace(/"/g, '\\"') + '"]';
  }
}

Path.prototype = createObject({
  __proto__: [],
  valid: true,

  toString: function() {
    var pathString = '';
    for (var i = 0; i < this.length; i++) {
      var key = this[i];
      if (isIdent(key)) {
        pathString += i ? '.' + key : key;
      } else {
        pathString += formatAccessor(key);
      }
    }

    return pathString;
  },

  getValueFrom: function(obj, directObserver) {
    for (var i = 0; i < this.length; i++) {
      if (obj == null)
        return;
      obj = obj[this[i]];
    }
    return obj;
  },

  iterateObjects: function(obj, observe) {
    for (var i = 0; i < this.length; i++) {
      if (i)
        obj = obj[this[i - 1]];
      if (!isObject(obj))
        return;
      observe(obj, this[i]);
    }
  },

  compiledGetValueFromFn: function() {
    var str = '';
    var pathString = 'obj';
    str += 'if (obj != null';
    var i = 0;
    var key;
    for (; i < (this.length - 1); i++) {
      key = this[i];
      pathString += isIdent(key) ? '.' + key : formatAccessor(key);
      str += ' &&\n     ' + pathString + ' != null';
    }
    str += ')\n';

    var key = this[i];
    pathString += isIdent(key) ? '.' + key : formatAccessor(key);

    str += '  return ' + pathString + ';\nelse\n  return undefined;';
    return new Function('obj', str);
  },

  setValueFrom: function(obj, value) {
    if (!this.length)
      return false;

    for (var i = 0; i < this.length - 1; i++) {
      if (!isObject(obj))
        return false;
      obj = obj[this[i]];
    }

    if (!isObject(obj))
      return false;

    obj[this[i]] = value;
    return true;
  }
});

var invalidPath = new Path('', constructorIsPrivate);
invalidPath.valid = false;
invalidPath.getValueFrom = invalidPath.setValueFrom = function() {};

var MAX_DIRTY_CHECK_CYCLES = 1000;

function dirtyCheck(observer) {
  var cycles = 0;
  while (cycles < MAX_DIRTY_CHECK_CYCLES && observer.check_()) {
    cycles++;
  }

  return cycles > 0;
}

function runEOM(fn) {
  return Promise.resolve().then(fn);
}

var observedObjectCache = [];

function newObservedObject() {
  var observer;
  var object;
  var discardRecords = false;
  var first = true;

  function callback(records) {
    if (observer && observer.state_ === OPENED && !discardRecords)
      observer.check_(records);
  }

  return {
    open: function(obs) {
      if (observer)
        throw Error('ObservedObject in use');

      if (!first)
        Object.deliverChangeRecords(callback);

      observer = obs;
      first = false;
    },
    observe: function(obj, arrayObserve) {
      object = obj;
      if (arrayObserve)
        Array.observe(object, callback);
      else
        Object.observe(object, callback);
    },
    deliver: function(discard) {
      discardRecords = discard;
      Object.deliverChangeRecords(callback);
      discardRecords = false;
    },
    close: function() {
      observer = undefined;
      Object.unobserve(object, callback);
      observedObjectCache.push(this);
    }
  };
}

/*
 * The observedSet abstraction is a perf optimization which reduces the total
 * number of Object.observe observations of a set of objects. The idea is that
 * groups of Observers will have some object dependencies in common and this
 * observed set ensures that each object in the transitive closure of
 * dependencies is only observed once. The observedSet acts as a write barrier
 * such that whenever any change comes through, all Observers are checked for
 * changed values.
 *
 * Note that this optimization is explicitly moving work from setup-time to
 * change-time.
 *
 * TODO(rafaelw): Implement "garbage collection". In order to move work off
 * the critical path, when Observers are closed, their observed objects are
 * not Object.unobserve(d). As a result, it's possible that if the observedSet
 * is kept open, but some Observers have been closed, it could cause "leaks"
 * (prevent otherwise collectable objects from being collected). At some
 * point, we should implement incremental "gc" which keeps a list of
 * observedSets which may need clean-up and does small amounts of cleanup on a
 * timeout until all is clean.
 */

function getObservedObject(observer, object, arrayObserve) {
  var dir = observedObjectCache.pop() || newObservedObject();
  dir.open(observer);
  dir.observe(object, arrayObserve);
  return dir;
}

var observedSetCache = [];

function newObservedSet() {
  var observerCount = 0;
  var observers = [];
  var objects = [];
  var rootObj;
  var rootObjProps;

  function observe(obj, prop) {
    if (!obj)
      return;

    if (obj === rootObj)
      rootObjProps[prop] = true;

    if (objects.indexOf(obj) < 0) {
      objects.push(obj);
      Object.observe(obj, callback);
    }

    observe(Object.getPrototypeOf(obj), prop);
  }

  function allRootObjNonObservedProps(recs) {
    for (var i = 0; i < recs.length; i++) {
      var rec = recs[i];
      if (rec.object !== rootObj ||
          rootObjProps[rec.name] ||
          rec.type === 'setPrototype') {
        return false;
      }
    }
    return true;
  }

  function callback(recs) {
    if (allRootObjNonObservedProps(recs))
      return;

    var observer;
    for (var i = 0; i < observers.length; i++) {
      observer = observers[i];
      if (observer.state_ == OPENED) {
        observer.iterateObjects_(observe);
      }
    }

    for (var i = 0; i < observers.length; i++) {
      observer = observers[i];
      if (observer.state_ == OPENED) {
        observer.check_();
      }
    }
  }

  var record = {
    objects: objects,
    get rootObject() { return rootObj; },
    set rootObject(value) {
      rootObj = value;
      rootObjProps = {};
    },
    open: function(obs, object) {
      observers.push(obs);
      observerCount++;
      obs.iterateObjects_(observe);
    },
    close: function(obs) {
      observerCount--;
      if (observerCount > 0) {
        return;
      }

      for (var i = 0; i < objects.length; i++) {
        Object.unobserve(objects[i], callback);
        Observer.unobservedCount++;
      }

      observers.length = 0;
      objects.length = 0;
      rootObj = undefined;
      rootObjProps = undefined;
      observedSetCache.push(this);
      if (lastObservedSet === this)
        lastObservedSet = null;
    },
  };

  return record;
}

var lastObservedSet;

function getObservedSet(observer, obj) {
  if (!lastObservedSet || lastObservedSet.rootObject !== obj) {
    lastObservedSet = observedSetCache.pop() || newObservedSet();
    lastObservedSet.rootObject = obj;
  }
  lastObservedSet.open(observer, obj);
  return lastObservedSet;
}

var UNOPENED = 0;
var OPENED = 1;
var CLOSED = 2;
var RESETTING = 3;

var nextObserverId = 1;

function Observer() {
  this.state_ = UNOPENED;
  this.callback_ = undefined;
  this.target_ = undefined; // TODO(rafaelw): Should be WeakRef
  this.directObserver_ = undefined;
  this.value_ = undefined;
  this.id_ = nextObserverId++;
}

Observer.prototype = {
  open: function(callback, target) {
    if (this.state_ != UNOPENED)
      throw Error('Observer has already been opened.');

    this.callback_ = callback;
    this.target_ = target;
    this.connect_();
    this.state_ = OPENED;
    return this.value_;
  },

  setValue: function(newValue) {
  },

  close: function() {
    if (this.state_ != OPENED)
      return;

    this.disconnect_();
    this.value_ = undefined;
    this.callback_ = undefined;
    this.target_ = undefined;
    this.state_ = CLOSED;
  },

  deliver: function() {
    if (this.state_ != OPENED)
      return;

    dirtyCheck(this);
  },

  report_: function(changes) {
    try {
      this.callback_.apply(this.target_, changes);
    } catch (ex) {
      Observer._errorThrownDuringCallback = true;
      console.error('Exception caught during observer callback: ' +
                     (ex.stack || ex));
    }
  },

  discardChanges: function() {
    this.check_(undefined, true);
    return this.value_;
  }
}

function ArrayObserver(array) {
  if (!Array.isArray(array))
    throw Error('Provided object is not an Array');
  Observer.call(this);
  this.value_ = array;
  this.oldObject_ = undefined;
}

ArrayObserver.prototype = createObject({

  __proto__: Observer.prototype,

  connect_: function(callback, target) {
    this.directObserver_ = getObservedObject(this, this.value_,
                                             true /* arrayObserve */);
  },

  copyObject: function(arr) {
    return arr.slice();
  },

  check_: function(changeRecords) {
    var splices;
    if (!changeRecords)
      return false;
    splices = projectArraySplices(this.value_, changeRecords);

    if (!splices || !splices.length)
      return false;

    this.report_([splices]);
    return true;
  },

  disconnect_: function() {
    this.directObserver_.close();
    this.directObserver_ = undefined;
  },

  deliver: function() {
    if (this.state_ != OPENED)
      return;

    this.directObserver_.deliver(false);
  },

  discardChanges: function() {
    if (this.directObserver_)
      this.directObserver_.deliver(true);
    else
      this.oldObject_ = this.copyObject(this.value_);

    return this.value_;
  }
});

ArrayObserver.applySplices = function(previous, current, splices) {
  splices.forEach(function(splice) {
    var spliceArgs = [splice.index, splice.removed.length];
    var addIndex = splice.index;
    while (addIndex < splice.index + splice.addedCount) {
      spliceArgs.push(current[addIndex]);
      addIndex++;
    }

    Array.prototype.splice.apply(previous, spliceArgs);
  });
};

function PathObserver(object, path) {
  Observer.call(this);

  this.object_ = object;
  this.path_ = getPath(path);
  this.directObserver_ = undefined;
}

PathObserver.prototype = createObject({
  __proto__: Observer.prototype,

  get path() {
    return this.path_;
  },

  connect_: function() {
    this.directObserver_ = getObservedSet(this, this.object_);
    this.check_(undefined, true);
  },

  disconnect_: function() {
    this.value_ = undefined;

    if (this.directObserver_) {
      this.directObserver_.close(this);
      this.directObserver_ = undefined;
    }
  },

  iterateObjects_: function(observe) {
    this.path_.iterateObjects(this.object_, observe);
  },

  check_: function(changeRecords, skipChanges) {
    var oldValue = this.value_;
    this.value_ = this.path_.getValueFrom(this.object_);
    if (skipChanges || areSameValue(this.value_, oldValue))
      return false;

    this.report_([this.value_, oldValue, this]);
    return true;
  },

  setValue: function(newValue) {
    if (this.path_)
      this.path_.setValueFrom(this.object_, newValue);
  }
});

function CompoundObserver(reportChangesOnOpen) {
  Observer.call(this);

  this.reportChangesOnOpen_ = reportChangesOnOpen;
  this.value_ = [];
  this.directObserver_ = undefined;
  this.observed_ = [];
}

var observerSentinel = {};

CompoundObserver.prototype = createObject({
  __proto__: Observer.prototype,

  connect_: function() {
    var object;
    var needsDirectObserver = false;
    for (var i = 0; i < this.observed_.length; i += 2) {
      object = this.observed_[i]
      if (object !== observerSentinel) {
        needsDirectObserver = true;
        break;
      }
    }

    if (needsDirectObserver)
      this.directObserver_ = getObservedSet(this, object);

    this.check_(undefined, !this.reportChangesOnOpen_);
  },

  disconnect_: function() {
    for (var i = 0; i < this.observed_.length; i += 2) {
      if (this.observed_[i] === observerSentinel)
        this.observed_[i + 1].close();
    }
    this.observed_.length = 0;
    this.value_.length = 0;

    if (this.directObserver_) {
      this.directObserver_.close(this);
      this.directObserver_ = undefined;
    }
  },

  addPath: function(object, path) {
    if (this.state_ != UNOPENED && this.state_ != RESETTING)
      throw Error('Cannot add paths once started.');

    var path = getPath(path);
    this.observed_.push(object, path);
    if (!this.reportChangesOnOpen_)
      return;
    var index = this.observed_.length / 2 - 1;
    this.value_[index] = path.getValueFrom(object);
  },

  addObserver: function(observer) {
    if (this.state_ != UNOPENED && this.state_ != RESETTING)
      throw Error('Cannot add observers once started.');

    this.observed_.push(observerSentinel, observer);
    if (!this.reportChangesOnOpen_)
      return;
    var index = this.observed_.length / 2 - 1;
    this.value_[index] = observer.open(this.deliver, this);
  },

  startReset: function() {
    if (this.state_ != OPENED)
      throw Error('Can only reset while open');

    this.state_ = RESETTING;
    this.disconnect_();
  },

  finishReset: function() {
    if (this.state_ != RESETTING)
      throw Error('Can only finishReset after startReset');
    this.state_ = OPENED;
    this.connect_();

    return this.value_;
  },

  iterateObjects_: function(observe) {
    var object;
    for (var i = 0; i < this.observed_.length; i += 2) {
      object = this.observed_[i]
      if (object !== observerSentinel)
        this.observed_[i + 1].iterateObjects(object, observe)
    }
  },

  check_: function(changeRecords, skipChanges) {
    var oldValues;
    for (var i = 0; i < this.observed_.length; i += 2) {
      var object = this.observed_[i];
      var path = this.observed_[i+1];
      var value;
      if (object === observerSentinel) {
        var observable = path;
        value = this.state_ === UNOPENED ?
            observable.open(this.deliver, this) :
            observable.discardChanges();
      } else {
        value = path.getValueFrom(object);
      }

      if (skipChanges) {
        this.value_[i / 2] = value;
        continue;
      }

      if (areSameValue(value, this.value_[i / 2]))
        continue;

      oldValues = oldValues || [];
      oldValues[i / 2] = this.value_[i / 2];
      this.value_[i / 2] = value;
    }

    if (!oldValues)
      return false;

    // TODO(rafaelw): Having observed_ as the third callback arg here is
    // pretty lame API. Fix.
    this.report_([this.value_, oldValues, this.observed_]);
    return true;
  }
});

function identFn(value) { return value; }

function ObserverTransform(observable, getValueFn) {
  this.callback_ = undefined;
  this.target_ = undefined;
  this.value_ = undefined;
  this.observable_ = observable;
  this.getValueFn_ = getValueFn || identFn;
}

ObserverTransform.prototype = {
  open: function(callback, target) {
    this.callback_ = callback;
    this.target_ = target;
    this.value_ =
        this.getValueFn_(this.observable_.open(this.observedCallback_, this));
    return this.value_;
  },

  observedCallback_: function(value) {
    value = this.getValueFn_(value);
    if (areSameValue(value, this.value_))
      return;
    var oldValue = this.value_;
    this.value_ = value;
    this.callback_.call(this.target_, this.value_, oldValue);
  },

  setValue: function(oldValue) {
  },

  discardChanges: function() {
    this.value_ = this.getValueFn_(this.observable_.discardChanges());
    return this.value_;
  },

  deliver: function() {
    return this.observable_.deliver();
  },

  close: function() {
    if (this.observable_)
      this.observable_.close();
    this.callback_ = undefined;
    this.target_ = undefined;
    this.observable_ = undefined;
    this.value_ = undefined;
    this.getValueFn_ = undefined;
  }
}

function newSplice(index, removed, addedCount) {
  return {
    index: index,
    removed: removed,
    addedCount: addedCount
  };
}

var EDIT_LEAVE = 0;
var EDIT_UPDATE = 1;
var EDIT_ADD = 2;
var EDIT_DELETE = 3;

function ArraySplice() {}

ArraySplice.prototype = {

  // Note: This function is *based* on the computation of the Levenshtein
  // "edit" distance. The one change is that "updates" are treated as two
  // edits - not one. With Array splices, an update is really a delete
  // followed by an add. By retaining this, we optimize for "keeping" the
  // maximum array items in the original array. For example:
  //
  //   'xxxx123' -> '123yyyy'
  //
  // With 1-edit updates, the shortest path would be just to update all seven
  // characters. With 2-edit updates, we delete 4, leave 3, and add 4. This
  // leaves the substring '123' intact.
  calcEditDistances: function(current, currentStart, currentEnd,
                              old, oldStart, oldEnd) {
    // "Deletion" columns
    var rowCount = oldEnd - oldStart + 1;
    var columnCount = currentEnd - currentStart + 1;
    var distances = new Array(rowCount);

    // "Addition" rows. Initialize null column.
    for (var i = 0; i < rowCount; i++) {
      distances[i] = new Array(columnCount);
      distances[i][0] = i;
    }

    // Initialize null row
    for (var j = 0; j < columnCount; j++)
      distances[0][j] = j;

    for (var i = 1; i < rowCount; i++) {
      for (var j = 1; j < columnCount; j++) {
        if (this.equals(current[currentStart + j - 1], old[oldStart + i - 1]))
          distances[i][j] = distances[i - 1][j - 1];
        else {
          var north = distances[i - 1][j] + 1;
          var west = distances[i][j - 1] + 1;
          distances[i][j] = north < west ? north : west;
        }
      }
    }

    return distances;
  },

  // This starts at the final weight, and walks "backward" by finding
  // the minimum previous weight recursively until the origin of the weight
  // matrix.
  spliceOperationsFromEditDistances: function(distances) {
    var i = distances.length - 1;
    var j = distances[0].length - 1;
    var current = distances[i][j];
    var edits = [];
    while (i > 0 || j > 0) {
      if (i == 0) {
        edits.push(EDIT_ADD);
        j--;
        continue;
      }
      if (j == 0) {
        edits.push(EDIT_DELETE);
        i--;
        continue;
      }
      var northWest = distances[i - 1][j - 1];
      var west = distances[i - 1][j];
      var north = distances[i][j - 1];

      var min;
      if (west < north)
        min = west < northWest ? west : northWest;
      else
        min = north < northWest ? north : northWest;

      if (min == northWest) {
        if (northWest == current) {
          edits.push(EDIT_LEAVE);
        } else {
          edits.push(EDIT_UPDATE);
          current = northWest;
        }
        i--;
        j--;
      } else if (min == west) {
        edits.push(EDIT_DELETE);
        i--;
        current = west;
      } else {
        edits.push(EDIT_ADD);
        j--;
        current = north;
      }
    }

    edits.reverse();
    return edits;
  },

  /**
   * Splice Projection functions:
   *
   * A splice map is a representation of how a previous array of items
   * was transformed into a new array of items. Conceptually it is a list of
   * tuples of
   *
   *   <index, removed, addedCount>
   *
   * which are kept in ascending index order of. The tuple represents that at
   * the |index|, |removed| sequence of items were removed, and counting forward
   * from |index|, |addedCount| items were added.
   */

  /**
   * Lacking individual splice mutation information, the minimal set of
   * splices can be synthesized given the previous state and final state of an
   * array. The basic approach is to calculate the edit distance matrix and
   * choose the shortest path through it.
   *
   * Complexity: O(l * p)
   *   l: The length of the current array
   *   p: The length of the old array
   */
  calcSplices: function(current, currentStart, currentEnd,
                        old, oldStart, oldEnd) {
    var prefixCount = 0;
    var suffixCount = 0;

    var minLength = Math.min(currentEnd - currentStart, oldEnd - oldStart);
    if (currentStart == 0 && oldStart == 0)
      prefixCount = this.sharedPrefix(current, old, minLength);

    if (currentEnd == current.length && oldEnd == old.length)
      suffixCount = this.sharedSuffix(current, old, minLength - prefixCount);

    currentStart += prefixCount;
    oldStart += prefixCount;
    currentEnd -= suffixCount;
    oldEnd -= suffixCount;

    if (currentEnd - currentStart == 0 && oldEnd - oldStart == 0)
      return [];

    if (currentStart == currentEnd) {
      var splice = newSplice(currentStart, [], 0);
      while (oldStart < oldEnd)
        splice.removed.push(old[oldStart++]);

      return [ splice ];
    } else if (oldStart == oldEnd)
      return [ newSplice(currentStart, [], currentEnd - currentStart) ];

    var ops = this.spliceOperationsFromEditDistances(
        this.calcEditDistances(current, currentStart, currentEnd,
                               old, oldStart, oldEnd));

    var splice = undefined;
    var splices = [];
    var index = currentStart;
    var oldIndex = oldStart;
    for (var i = 0; i < ops.length; i++) {
      switch(ops[i]) {
        case EDIT_LEAVE:
          if (splice) {
            splices.push(splice);
            splice = undefined;
          }

          index++;
          oldIndex++;
          break;
        case EDIT_UPDATE:
          if (!splice)
            splice = newSplice(index, [], 0);

          splice.addedCount++;
          index++;

          splice.removed.push(old[oldIndex]);
          oldIndex++;
          break;
        case EDIT_ADD:
          if (!splice)
            splice = newSplice(index, [], 0);

          splice.addedCount++;
          index++;
          break;
        case EDIT_DELETE:
          if (!splice)
            splice = newSplice(index, [], 0);

          splice.removed.push(old[oldIndex]);
          oldIndex++;
          break;
      }
    }

    if (splice) {
      splices.push(splice);
    }
    return splices;
  },

  sharedPrefix: function(current, old, searchLength) {
    for (var i = 0; i < searchLength; i++)
      if (!this.equals(current[i], old[i]))
        return i;
    return searchLength;
  },

  sharedSuffix: function(current, old, searchLength) {
    var index1 = current.length;
    var index2 = old.length;
    var count = 0;
    while (count < searchLength &&
           this.equals(current[--index1], old[--index2])) {
      count++;
    }

    return count;
  },

  calculateSplices: function(current, previous) {
    return this.calcSplices(current, 0, current.length, previous, 0,
                            previous.length);
  },

  equals: function(currentValue, previousValue) {
    return currentValue === previousValue;
  }
};

var arraySplice = new ArraySplice();

function calcSplices(current, currentStart, currentEnd,
                     old, oldStart, oldEnd) {
  return arraySplice.calcSplices(current, currentStart, currentEnd,
                                 old, oldStart, oldEnd);
}

function intersect(start1, end1, start2, end2) {
  // Disjoint
  if (end1 < start2 || end2 < start1)
    return -1;

  // Adjacent
  if (end1 == start2 || end2 == start1)
    return 0;

  // Non-zero intersect, span1 first
  if (start1 < start2) {
    if (end1 < end2)
      return end1 - start2; // Overlap
    else
      return end2 - start2; // Contained
  } else {
    // Non-zero intersect, span2 first
    if (end2 < end1)
      return end2 - start1; // Overlap
    else
      return end1 - start1; // Contained
  }
}

function mergeSplice(splices, index, removed, addedCount) {

  var splice = newSplice(index, removed, addedCount);

  var inserted = false;
  var insertionOffset = 0;

  for (var i = 0; i < splices.length; i++) {
    var current = splices[i];
    current.index += insertionOffset;

    if (inserted)
      continue;

    var intersectCount = intersect(splice.index,
                                   splice.index + splice.removed.length,
                                   current.index,
                                   current.index + current.addedCount);

    if (intersectCount >= 0) {
      // Merge the two splices

      splices.splice(i, 1);
      i--;

      insertionOffset -= current.addedCount - current.removed.length;

      splice.addedCount += current.addedCount - intersectCount;
      var deleteCount = splice.removed.length +
                        current.removed.length - intersectCount;

      if (!splice.addedCount && !deleteCount) {
        // merged splice is a noop. discard.
        inserted = true;
      } else {
        var removed = current.removed;

        if (splice.index < current.index) {
          // some prefix of splice.removed is prepended to current.removed.
          var prepend = splice.removed.slice(0, current.index - splice.index);
          Array.prototype.push.apply(prepend, removed);
          removed = prepend;
        }

        if (splice.index + splice.removed.length >
            current.index + current.addedCount) {
          // some suffix of splice.removed is appended to current.removed.
          var append = splice.removed.slice(
              current.index + current.addedCount - splice.index);
          Array.prototype.push.apply(removed, append);
        }

        splice.removed = removed;
        if (current.index < splice.index) {
          splice.index = current.index;
        }
      }
    } else if (splice.index < current.index) {
      // Insert splice here.

      inserted = true;

      splices.splice(i, 0, splice);
      i++;

      var offset = splice.addedCount - splice.removed.length
      current.index += offset;
      insertionOffset += offset;
    }
  }

  if (!inserted)
    splices.push(splice);
}

function createInitialSplices(array, changeRecords) {
  var splices = [];

  for (var i = 0; i < changeRecords.length; i++) {
    var record = changeRecords[i];
    switch(record.type) {
      case 'splice':
        mergeSplice(splices, record.index, record.removed.slice(),
                    record.addedCount);
        break;
      case 'add':
      case 'update':
      case 'delete':
        if (!isIndex(record.name))
          continue;
        var index = toNumber(record.name);
        if (index < 0)
          continue;
        mergeSplice(splices, index, [record.oldValue], 1);
        break;
      default:
        console.error('Unexpected record type: ' + JSON.stringify(record));
        break;
    }
  }

  return splices;
}

function projectArraySplices(array, changeRecords) {
  var splices = [];

  createInitialSplices(array, changeRecords).forEach(function(splice) {
    if (splice.addedCount == 1 && splice.removed.length == 1) {
      if (splice.removed[0] !== array[splice.index])
        splices.push(splice);

      return
    };

    splices = splices.concat(calcSplices(array, splice.index,
                                         splice.index + splice.addedCount,
                                         splice.removed,
                                         0,
                                         splice.removed.length));
  });

  return splices;
}

ArrayObserver.calculateSplices = function(current, previous) {
  return arraySplice.calculateSplices(current, previous);
};

module.exports = {
  Observer: Observer,
  runEOM_: runEOM,
  observerSentinel_: observerSentinel,
  PathObserver: PathObserver,
  ArrayObserver: ArrayObserver,
  ArraySplice: ArraySplice,
  CompoundObserver: CompoundObserver,
  Path: Path,
  ObserverTransform: ObserverTransform
}
</script>