text: /*
   This is the implementation of the JSON OT type.
  
   Spec is here: https://github.com/josephg/ShareJS/wiki/JSON-Operations
  
   Note: This is being made obsolete. It will soon be replaced by the JSON2 type.
  */
  
  /**
   * UTILITY FUNCTIONS
   */
  
  /**
   * Checks if the passed object is an Array instance. Can't use Array.isArray
   * yet because its not supported on IE8.
   *
   * @param obj
   * @returns {boolean}
   */
  var isArray = function(obj) {
    return Object.prototype.toString.call(obj) == '[object Array]';
  };
  
  /**
   * Checks if the passed object is an Object instance.
   * No function call (fast) version
   *
   * @param obj
   * @returns {boolean}
   */
  var isObject = function(obj) {
    return (!!obj) && (obj.constructor === Object);
  };
  
  /**
   * Clones the passed object using JSON serialization (which is slow).
   *
   * hax, copied from test/types/json. Apparently this is still the fastest way
   * to deep clone an object, assuming we have browser support for JSON.  @see
   * http://jsperf.com/cloning-an-object/12
   */
  var clone = function(o) {
    return JSON.parse(JSON.stringify(o));
  };
  
  /**
   * JSON OT Type
   * @type {*}
   */
  var json = {
    name: 'json0',
    uri: 'http://sharejs.org/types/JSONv0'
  };
  
  // You can register another OT type as a subtype in a JSON document using
  // the following function. This allows another type to handle certain
  // operations instead of the builtin JSON type.
  var subtypes = {};
  json.registerSubtype = function(subtype) {
    subtypes[subtype.name] = subtype;
  };
  
  json.create = function(data) {
    // Null instead of undefined if you don't pass an argument.
    return data === undefined ? null : clone(data);
  };
  
  json.invertComponent = function(c) {
    var c_ = {p: c.p};
  
    // handle subtype ops
    if (c.t && subtypes[c.t]) {
      c_.t = c.t;
      c_.o = subtypes[c.t].invert(c.o);
    }
  
    if (c.si !== void 0) c_.sd = c.si;
    if (c.sd !== void 0) c_.si = c.sd;
    if (c.oi !== void 0) c_.od = c.oi;
    if (c.od !== void 0) c_.oi = c.od;
    if (c.li !== void 0) c_.ld = c.li;
    if (c.ld !== void 0) c_.li = c.ld;
    if (c.na !== void 0) c_.na = -c.na;
  
    if (c.lm !== void 0) {
      c_.lm = c.p[c.p.length-1];
      c_.p = c.p.slice(0,c.p.length-1).concat([c.lm]);
    }
  
    return c_;
  };
  
  json.invert = function(op) {
    var op_ = op.slice().reverse();
    var iop = [];
    for (var i = 0; i < op_.length; i++) {
      iop.push(json.invertComponent(op_[i]));
    }
    return iop;
  };
  
  json.checkValidOp = function(op) {
    for (var i = 0; i < op.length; i++) {
      if (!isArray(op[i].p)) throw new Error('Missing path');
    }
  };
  
  json.checkList = function(elem) {
    if (!isArray(elem))
      throw new Error('Referenced element not a list');
  };
  
  json.checkObj = function(elem) {
    if (!isObject(elem)) {
      throw new Error("Referenced element not an object (it was " + JSON.stringify(elem) + ")");
    }
  };
  
  // helper functions to convert old string ops to and from subtype ops
  function convertFromText(c) {
    c.t = 'text0';
    var o = {p: c.p.pop()};
    if (c.si != null) o.i = c.si;
    if (c.sd != null) o.d = c.sd;
    c.o = [o];
  }
  
  function convertToText(c) {
    c.p.push(c.o[0].p);
    if (c.o[0].i != null) c.si = c.o[0].i;
    if (c.o[0].d != null) c.sd = c.o[0].d;
    delete c.t;
    delete c.o;
  }
  
  json.apply = function(snapshot, op) {
    json.checkValidOp(op);
  
    op = clone(op);
  
    var container = {
      data: snapshot
    };
  
    for (var i = 0; i < op.length; i++) {
      var c = op[i];
  
      // convert old string ops to use subtype for backwards compatibility
      if (c.si != null || c.sd != null)
        convertFromText(c);
  
      var parent = null;
      var parentKey = null;
      var elem = container;
      var key = 'data';
  
      for (var j = 0; j < c.p.length; j++) {
        var p = c.p[j];
  
        parent = elem;
        parentKey = key;
        elem = elem[key];
        key = p;
  
        if (parent == null)
          throw new Error('Path invalid');
      }
  
      // handle subtype ops
      if (c.t && c.o !== void 0 && subtypes[c.t]) {
        elem[key] = subtypes[c.t].apply(elem[key], c.o);
  
      // Number add
      } else if (c.na !== void 0) {
        if (typeof elem[key] != 'number')
          throw new Error('Referenced element not a number');
  
        elem[key] += c.na;
      }
  
      // List replace
      else if (c.li !== void 0 && c.ld !== void 0) {
        json.checkList(elem);
        // Should check the list element matches c.ld
        elem[key] = c.li;
      }
  
      // List insert
      else if (c.li !== void 0) {
        json.checkList(elem);
        elem.splice(key,0, c.li);
      }
  
      // List delete
      else if (c.ld !== void 0) {
        json.checkList(elem);
        // Should check the list element matches c.ld here too.
        elem.splice(key,1);
      }
  
      // List move
      else if (c.lm !== void 0) {
        json.checkList(elem);
        if (c.lm != key) {
          var e = elem[key];
          // Remove it...
          elem.splice(key,1);
          // And insert it back.
          elem.splice(c.lm,0,e);
        }
      }
  
      // Object insert / replace
      else if (c.oi !== void 0) {
        json.checkObj(elem);
  
        // Should check that elem[key] == c.od
        elem[key] = c.oi;
      }
  
      // Object delete
      else if (c.od !== void 0) {
        json.checkObj(elem);
  
        // Should check that elem[key] == c.od
        delete elem[key];
      }
  
      else {
        throw new Error('invalid / missing instruction in op');
      }
    }
  
    return container.data;
  };
  
  // Helper to break an operation up into a bunch of small ops.
  json.shatter = function(op) {
    var results = [];
    for (var i = 0; i < op.length; i++) {
      results.push([op[i]]);
    }
    return results;
  };
  
  // Helper for incrementally applying an operation to a snapshot. Calls yield
  // after each op component has been applied.
  json.incrementalApply = function(snapshot, op, _yield) {
    for (var i = 0; i < op.length; i++) {
      var smallOp = [op[i]];
      snapshot = json.apply(snapshot, smallOp);
      // I'd just call this yield, but thats a reserved keyword. Bah!
      _yield(smallOp, snapshot);
    }
  
    return snapshot;
  };
  
  // Checks if two paths, p1 and p2 match.
  var pathMatches = json.pathMatches = function(p1, p2, ignoreLast) {
    if (p1.length != p2.length)
      return false;
  
    for (var i = 0; i < p1.length; i++) {
      if (p1[i] !== p2[i] && (!ignoreLast || i !== p1.length - 1))
        return false;
    }
  
    return true;
  };
  
  json.append = function(dest,c) {
    c = clone(c);
  
    if (dest.length === 0) {
      dest.push(c);
      return;
    }
  
    var last = dest[dest.length - 1];
  
    // convert old string ops to use subtype for backwards compatibility
    if ((c.si != null || c.sd != null) && (last.si != null || last.sd != null)) {
      convertFromText(c);
      convertFromText(last);
    }
  
    if (pathMatches(c.p, last.p)) {
      // handle subtype ops
      if (c.t && last.t && c.t === last.t && subtypes[c.t]) {
        last.o = subtypes[c.t].compose(last.o, c.o);
  
        // convert back to old string ops
        if (c.si != null || c.sd != null) {
          var p = c.p;
          for (var i = 0; i < last.o.length - 1; i++) {
            c.o = [last.o.pop()];
            c.p = p.slice();
            convertToText(c);
            dest.push(c);
          }
  
          convertToText(last);
        }
      } else if (last.na != null && c.na != null) {
        dest[dest.length - 1] = {p: last.p, na: last.na + c.na};
      } else if (last.li !== undefined && c.li === undefined && c.ld === last.li) {
        // insert immediately followed by delete becomes a noop.
        if (last.ld !== undefined) {
          // leave the delete part of the replace
          delete last.li;
        } else {
          dest.pop();
        }
      } else if (last.od !== undefined && last.oi === undefined && c.oi !== undefined && c.od === undefined) {
        last.oi = c.oi;
      } else if (last.oi !== undefined && c.od !== undefined) {
        // The last path component inserted something that the new component deletes (or replaces).
        // Just merge them.
        if (c.oi !== undefined) {
          last.oi = c.oi;
        } else if (last.od !== undefined) {
          delete last.oi;
        } else {
          // An insert directly followed by a delete turns into a no-op and can be removed.
          dest.pop();
        }
      } else if (c.lm !== undefined && c.p[c.p.length - 1] === c.lm) {
        // don't do anything
      } else {
        dest.push(c);
      }
    } else {
      // convert string ops back
      if ((c.si != null || c.sd != null) && (last.si != null || last.sd != null)) {
        convertToText(c);
        convertToText(last);
      }
  
      dest.push(c);
    }
  };
  
  json.compose = function(op1,op2) {
    json.checkValidOp(op1);
    json.checkValidOp(op2);
  
    var newOp = clone(op1);
  
    for (var i = 0; i < op2.length; i++) {
      json.append(newOp,op2[i]);
    }
  
    return newOp;
  };
  
  json.normalize = function(op) {
    var newOp = [];
  
    op = isArray(op) ? op : [op];
  
    for (var i = 0; i < op.length; i++) {
      var c = op[i];
      if (c.p == null) c.p = [];
  
      json.append(newOp,c);
    }
  
    return newOp;
  };
  
  // Returns the common length of the paths of ops a and b
  json.commonLengthForOps = function(a, b) {
    var alen = a.p.length;
    var blen = b.p.length;
    if (a.na != null || a.t)
      alen++;
  
    if (b.na != null || b.t)
      blen++;
  
    if (alen === 0) return -1;
    if (blen === 0) return null;
  
    alen--;
    blen--;
  
    for (var i = 0; i < alen; i++) {
      var p = a.p[i];
      if (i >= blen || p !== b.p[i])
        return null;
    }
  
    return alen;
  };
  
  // Returns true if an op can affect the given path
  json.canOpAffectPath = function(op, path) {
    return json.commonLengthForOps({p:path}, op) != null;
  };
  
  // transform c so it applies to a document with otherC applied.
  json.transformComponent = function(dest, c, otherC, type) {
    c = clone(c);
  
    var common = json.commonLengthForOps(otherC, c);
    var common2 = json.commonLengthForOps(c, otherC);
    var cplength = c.p.length;
    var otherCplength = otherC.p.length;
  
    if (c.na != null || c.t)
      cplength++;
  
    if (otherC.na != null || otherC.t)
      otherCplength++;
  
    // if c is deleting something, and that thing is changed by otherC, we need to
    // update c to reflect that change for invertibility.
    if (common2 != null && otherCplength > cplength && c.p[common2] == otherC.p[common2]) {
      if (c.ld !== void 0) {
        var oc = clone(otherC);
        oc.p = oc.p.slice(cplength);
        c.ld = json.apply(clone(c.ld),[oc]);
      } else if (c.od !== void 0) {
        var oc = clone(otherC);
        oc.p = oc.p.slice(cplength);
        c.od = json.apply(clone(c.od),[oc]);
      }
    }
  
    if (common != null) {
      var commonOperand = cplength == otherCplength;
  
      // backward compatibility for old string ops
      var oc = otherC;
      if ((c.si != null || c.sd != null) && (otherC.si != null || otherC.sd != null)) {
        convertFromText(c);
        oc = clone(otherC);
        convertFromText(oc);
      }
  
      // handle subtype ops
      if (oc.t && subtypes[oc.t]) {
        if (c.t && c.t === oc.t) {
          var res = subtypes[c.t].transform(c.o, oc.o, type);
  
          if (res.length > 0) {
            // convert back to old string ops
            if (c.si != null || c.sd != null) {
              var p = c.p;
              for (var i = 0; i < res.length; i++) {
                c.o = [res[i]];
                c.p = p.slice();
                convertToText(c);
                json.append(dest, c);
              }
            } else {
              c.o = res;
              json.append(dest, c);
            }
          }
  
          return dest;
        }
      }
  
      // transform based on otherC
      else if (otherC.na !== void 0) {
        // this case is handled below
      } else if (otherC.li !== void 0 && otherC.ld !== void 0) {
        if (otherC.p[common] === c.p[common]) {
          // noop
  
          if (!commonOperand) {
            return dest;
          } else if (c.ld !== void 0) {
            // we're trying to delete the same element, -> noop
            if (c.li !== void 0 && type === 'left') {
              // we're both replacing one element with another. only one can survive
              c.ld = clone(otherC.li);
            } else {
              return dest;
            }
          }
        }
      } else if (otherC.li !== void 0) {
        if (c.li !== void 0 && c.ld === undefined && commonOperand && c.p[common] === otherC.p[common]) {
          // in li vs. li, left wins.
          if (type === 'right')
            c.p[common]++;
        } else if (otherC.p[common] <= c.p[common]) {
          c.p[common]++;
        }
  
        if (c.lm !== void 0) {
          if (commonOperand) {
            // otherC edits the same list we edit
            if (otherC.p[common] <= c.lm)
              c.lm++;
            // changing c.from is handled above.
          }
        }
      } else if (otherC.ld !== void 0) {
        if (c.lm !== void 0) {
          if (commonOperand) {
            if (otherC.p[common] === c.p[common]) {
              // they deleted the thing we're trying to move
              return dest;
            }
            // otherC edits the same list we edit
            var p = otherC.p[common];
            var from = c.p[common];
            var to = c.lm;
            if (p < to || (p === to && from < to))
              c.lm--;
  
          }
        }
  
        if (otherC.p[common] < c.p[common]) {
          c.p[common]--;
        } else if (otherC.p[common] === c.p[common]) {
          if (otherCplength < cplength) {
            // we're below the deleted element, so -> noop
            return dest;
          } else if (c.ld !== void 0) {
            if (c.li !== void 0) {
              // we're replacing, they're deleting. we become an insert.
              delete c.ld;
            } else {
              // we're trying to delete the same element, -> noop
              return dest;
            }
          }
        }
  
      } else if (otherC.lm !== void 0) {
        if (c.lm !== void 0 && cplength === otherCplength) {
          // lm vs lm, here we go!
          var from = c.p[common];
          var to = c.lm;
          var otherFrom = otherC.p[common];
          var otherTo = otherC.lm;
          if (otherFrom !== otherTo) {
            // if otherFrom == otherTo, we don't need to change our op.
  
            // where did my thing go?
            if (from === otherFrom) {
              // they moved it! tie break.
              if (type === 'left') {
                c.p[common] = otherTo;
                if (from === to) // ugh
                  c.lm = otherTo;
              } else {
                return dest;
              }
            } else {
              // they moved around it
              if (from > otherFrom) c.p[common]--;
              if (from > otherTo) c.p[common]++;
              else if (from === otherTo) {
                if (otherFrom > otherTo) {
                  c.p[common]++;
                  if (from === to) // ugh, again
                    c.lm++;
                }
              }
  
              // step 2: where am i going to put it?
              if (to > otherFrom) {
                c.lm--;
              } else if (to === otherFrom) {
                if (to > from)
                  c.lm--;
              }
              if (to > otherTo) {
                c.lm++;
              } else if (to === otherTo) {
                // if we're both moving in the same direction, tie break
                if ((otherTo > otherFrom && to > from) ||
                    (otherTo < otherFrom && to < from)) {
                  if (type === 'right') c.lm++;
                } else {
                  if (to > from) c.lm++;
                  else if (to === otherFrom) c.lm--;
                }
              }
            }
          }
        } else if (c.li !== void 0 && c.ld === undefined && commonOperand) {
          // li
          var from = otherC.p[common];
          var to = otherC.lm;
          p = c.p[common];
          if (p > from) c.p[common]--;
          if (p > to) c.p[common]++;
        } else {
          // ld, ld+li, si, sd, na, oi, od, oi+od, any li on an element beneath
          // the lm
          //
          // i.e. things care about where their item is after the move.
          var from = otherC.p[common];
          var to = otherC.lm;
          p = c.p[common];
          if (p === from) {
            c.p[common] = to;
          } else {
            if (p > from) c.p[common]--;
            if (p > to) c.p[common]++;
            else if (p === to && from > to) c.p[common]++;
          }
        }
      }
      else if (otherC.oi !== void 0 && otherC.od !== void 0) {
        if (c.p[common] === otherC.p[common]) {
          if (c.oi !== void 0 && commonOperand) {
            // we inserted where someone else replaced
            if (type === 'right') {
              // left wins
              return dest;
            } else {
              // we win, make our op replace what they inserted
              c.od = otherC.oi;
            }
          } else {
            // -> noop if the other component is deleting the same object (or any parent)
            return dest;
          }
        }
      } else if (otherC.oi !== void 0) {
        if (c.oi !== void 0 && c.p[common] === otherC.p[common]) {
          // left wins if we try to insert at the same place
          if (type === 'left') {
            json.append(dest,{p: c.p, od:otherC.oi});
          } else {
            return dest;
          }
        }
      } else if (otherC.od !== void 0) {
        if (c.p[common] == otherC.p[common]) {
          if (!commonOperand)
            return dest;
          if (c.oi !== void 0) {
            delete c.od;
          } else {
            return dest;
          }
        }
      }
    }
  
    json.append(dest,c);
    return dest;
  };
  
  require('./bootstrapTransform')(json, json.transformComponent, json.checkValidOp, json.append);
  
  /**
   * Register a subtype for string operations, using the text0 type.
   */
  var text = require('./text0');
  
  json.registerSubtype(text);
  module.exports = json;
  
  