localModify.js

// XXX need a strategy for passing the binding of $ into this
// function, from the compiled selector
//
// maybe just {key.up.to.just.before.dollarsign: array_index}
//
// XXX atomicity: if one modification fails, do we roll back the whole
// change?
//
// options:
//   - isInsert is set when _modify is being called to compute the document to
//     insert as part of an upsert operation. We use this primarily to figure
//     out when to set the fields in $setOnInsert, if present.
var _ = require("underscore");


isOperatorObject = function(valueSelector, inconsistentOK) {
  if (!isPlainObject(valueSelector)) return false;
  var theseAreOperators = undefined;
  _.each(valueSelector, function(value, selKey) {
    var thisIsOperator = selKey.substr(0, 1) === "$";
    if (theseAreOperators === undefined) {
      theseAreOperators = thisIsOperator;
    } else if (theseAreOperators !== thisIsOperator) {
      if (!inconsistentOK) throw new Error("Inconsistent operator: " + JSON.stringify(valueSelector));
      theseAreOperators = false;
    }
  });
  return !!theseAreOperators;
};

var BASE_64_CHARS = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
var BASE_64_VALS = {};
for (var i = 0; i < BASE_64_CHARS.length; i++) {
  BASE_64_VALS[BASE_64_CHARS.charAt(i)] = i;
}
Base64 = {};
Base64.encode = function(array) {
  if (typeof array === "string") {
    var str = array;
    array = Base64.newBinary(str.length);
    for (var i = 0; i < str.length; i++) {
      var ch = str.charCodeAt(i);
      if (ch > 255) {
        throw new Error("Not ascii. Base64.encode can only take ascii strings.");
      }
      array[i] = ch;
    }
  }
  var answer = [];
  var a = null;
  var b = null;
  var c = null;
  var d = null;
  for (var i = 0; i < array.length; i++) {
    switch (i % 3) {
      case 0:
        a = array[i] >> 2 & 63;
        b = (array[i] & 3) << 4;
        break;

      case 1:
        b = b | array[i] >> 4 & 15;
        c = (array[i] & 15) << 2;
        break;

      case 2:
        c = c | array[i] >> 6 & 3;
        d = array[i] & 63;
        answer.push(getChar(a));
        answer.push(getChar(b));
        answer.push(getChar(c));
        answer.push(getChar(d));
        a = null;
        b = null;
        c = null;
        d = null;
        break;
    }
  }
  if (a != null) {
    answer.push(getChar(a));
    answer.push(getChar(b));
    if (c == null) answer.push("="); else answer.push(getChar(c));
    if (d == null) answer.push("=");
  }
  return answer.join("");
};
var getChar = function(val) {
  return BASE_64_CHARS.charAt(val);
};
var getVal = function(ch) {
  if (ch === "=") {
    return -1;
  }
  return BASE_64_VALS[ch];
};
// XXX This is a weird place for this to live, but it's used both by
// this package and 'ejson', and we can't put it in 'ejson' without
// introducing a circular dependency. It should probably be in its own
// package or as a helper in a package that both 'base64' and 'ejson'
// use.
Base64.newBinary = function(len) {
  if (typeof Uint8Array === "undefined" || typeof ArrayBuffer === "undefined") {
    var ret = [];
    for (var i = 0; i < len; i++) {
      ret.push(0);
    }
    ret.$Uint8ArrayPolyfill = true;
    return ret;
  }
  return new Uint8Array(new ArrayBuffer(len));
};
Base64.decode = function(str) {
  var len = Math.floor(str.length * 3 / 4);
  if (str.charAt(str.length - 1) == "=") {
    len--;
    if (str.charAt(str.length - 2) == "=") len--;
  }
  var arr = Base64.newBinary(len);
  var one = null;
  var two = null;
  var three = null;
  var j = 0;
  for (var i = 0; i < str.length; i++) {
    var c = str.charAt(i);
    var v = getVal(c);
    switch (i % 4) {
      case 0:
        if (v < 0) throw new Error("invalid base64 string");
        one = v << 2;
        break;

      case 1:
        if (v < 0) throw new Error("invalid base64 string");
        one = one | v >> 4;
        arr[j++] = one;
        two = (v & 15) << 4;
        break;

      case 2:
        if (v >= 0) {
          two = two | v >> 2;
          arr[j++] = two;
          three = (v & 3) << 6;
        }
        break;

      case 3:
        if (v >= 0) {
          arr[j++] = three | v;
        }
        break;
    }
  }
  return arr;
};

EJSON = {};
EJSONTest = {};
// Custom type interface definition
/**
 * @class CustomType
 * @instanceName customType
 * @memberOf EJSON
 * @summary The interface that a class must satisfy to be able to become an
 * EJSON custom type via EJSON.addType.
 */
/**
 * @function typeName
 * @memberOf EJSON.CustomType
 * @summary Return the tag used to identify this type.  This must match the tag used to register this type with [`EJSON.addType`](#ejson_add_type).
 * @locus Anywhere
 * @instance
 */
/**
 * @function toJSONValue
 * @memberOf EJSON.CustomType
 * @summary Serialize this instance into a JSON-compatible value.
 * @locus Anywhere
 * @instance
 */
/**
 * @function clone
 * @memberOf EJSON.CustomType
 * @summary Return a value `r` such that `this.equals(r)` is true, and modifications to `r` do not affect `this` and vice versa.
 * @locus Anywhere
 * @instance
 */
/**
 * @function equals
 * @memberOf EJSON.CustomType
 * @summary Return `true` if `other` has a value equal to `this`; `false` otherwise.
 * @locus Anywhere
 * @param {Object} other Another object to compare this to.
 * @instance
 */
var customTypes = {};
// Add a custom type, using a method of your choice to get to and
// from a basic JSON-able representation.  The factory argument
// is a function of JSON-able --> your object
// The type you add must have:
// - A toJSONValue() method, so that Meteor can serialize it
// - a typeName() method, to show how to look it up in our type table.
// It is okay if these methods are monkey-patched on.
// EJSON.clone will use toJSONValue and the given factory to produce
// a clone, but you may specify a method clone() that will be
// used instead.
// Similarly, EJSON.equals will use toJSONValue to make comparisons,
// but you may provide a method equals() instead.
/**
 * @summary Add a custom datatype to EJSON.
 * @locus Anywhere
 * @param {String} name A tag for your custom type; must be unique among custom data types defined in your project, and must match the result of your type's `typeName` method.
 * @param {Function} factory A function that deserializes a JSON-compatible value into an instance of your type.  This should match the serialization performed by your type's `toJSONValue` method.
 */
EJSON.addType = function(name, factory) {
  if (_.has(customTypes, name)) throw new Error("Type " + name + " already present");
  customTypes[name] = factory;
};
var isInfOrNan = function(obj) {
  return _.isNaN(obj) || obj === Infinity || obj === -Infinity;
};
var builtinConverters = [ {
  // Date
  matchJSONValue: function(obj) {
    return _.has(obj, "$date") && _.size(obj) === 1;
  },
  matchObject: function(obj) {
    return obj instanceof Date;
  },
  toJSONValue: function(obj) {
    return {
      $date: obj.getTime()
    };
  },
  fromJSONValue: function(obj) {
    return new Date(obj.$date);
  }
}, {
  // NaN, Inf, -Inf. (These are the only objects with typeof !== 'object'
  // which we match.)
  matchJSONValue: function(obj) {
    return _.has(obj, "$InfNaN") && _.size(obj) === 1;
  },
  matchObject: isInfOrNan,
  toJSONValue: function(obj) {
    var sign;
    if (_.isNaN(obj)) sign = 0; else if (obj === Infinity) sign = 1; else sign = -1;
    return {
      $InfNaN: sign
    };
  },
  fromJSONValue: function(obj) {
    return obj.$InfNaN / 0;
  }
}, {
  // Binary
  matchJSONValue: function(obj) {
    return _.has(obj, "$binary") && _.size(obj) === 1;
  },
  matchObject: function(obj) {
    return typeof Uint8Array !== "undefined" && obj instanceof Uint8Array || obj && _.has(obj, "$Uint8ArrayPolyfill");
  },
  toJSONValue: function(obj) {
    return {
      $binary: Base64.encode(obj)
    };
  },
  fromJSONValue: function(obj) {
    return Base64.decode(obj.$binary);
  }
}, {
  // Escaping one level
  matchJSONValue: function(obj) {
    return _.has(obj, "$escape") && _.size(obj) === 1;
  },
  matchObject: function(obj) {
    if (_.isEmpty(obj) || _.size(obj) > 2) {
      return false;
    }
    return _.any(builtinConverters, function(converter) {
      return converter.matchJSONValue(obj);
    });
  },
  toJSONValue: function(obj) {
    var newObj = {};
    _.each(obj, function(value, key) {
      newObj[key] = EJSON.toJSONValue(value);
    });
    return {
      $escape: newObj
    };
  },
  fromJSONValue: function(obj) {
    var newObj = {};
    _.each(obj.$escape, function(value, key) {
      newObj[key] = EJSON.fromJSONValue(value);
    });
    return newObj;
  }
}, {
  // Custom
  matchJSONValue: function(obj) {
    return _.has(obj, "$type") && _.has(obj, "$value") && _.size(obj) === 2;
  },
  matchObject: function(obj) {
    return EJSON._isCustomType(obj);
  },
  toJSONValue: function(obj) {
    var jsonValue = Meteor._noYieldsAllowed(function() {
      return obj.toJSONValue();
    });
    return {
      $type: obj.typeName(),
      $value: jsonValue
    };
  },
  fromJSONValue: function(obj) {
    var typeName = obj.$type;
    if (!_.has(customTypes, typeName)) throw new Error("Custom EJSON type " + typeName + " is not defined");
    var converter = customTypes[typeName];
    return Meteor._noYieldsAllowed(function() {
      return converter(obj.$value);
    });
  }
} ];
EJSON._isCustomType = function(obj) {
  return obj && typeof obj.toJSONValue === "function" && typeof obj.typeName === "function" && _.has(customTypes, obj.typeName());
};
// for both arrays and objects, in-place modification.
var adjustTypesToJSONValue = EJSON._adjustTypesToJSONValue = function(obj) {
  // Is it an atom that we need to adjust?
  if (obj === null) return null;
  var maybeChanged = toJSONValueHelper(obj);
  if (maybeChanged !== undefined) return maybeChanged;
  // Other atoms are unchanged.
  if (typeof obj !== "object") return obj;
  // Iterate over array or object structure.
  _.each(obj, function(value, key) {
    if (typeof value !== "object" && value !== undefined && !isInfOrNan(value)) return;
    // continue
    var changed = toJSONValueHelper(value);
    if (changed) {
      obj[key] = changed;
      return;
    }
    // if we get here, value is an object but not adjustable
    // at this level.  recurse.
    adjustTypesToJSONValue(value);
  });
  return obj;
};
// Either return the JSON-compatible version of the argument, or undefined (if
// the item isn't itself replaceable, but maybe some fields in it are)
var toJSONValueHelper = function(item) {
  for (var i = 0; i < builtinConverters.length; i++) {
    var converter = builtinConverters[i];
    if (converter.matchObject(item)) {
      return converter.toJSONValue(item);
    }
  }
  return undefined;
};
/**
 * @summary Serialize an EJSON-compatible value into its plain JSON representation.
 * @locus Anywhere
 * @param {EJSON} val A value to serialize to plain JSON.
 */
EJSON.toJSONValue = function(item) {
  var changed = toJSONValueHelper(item);
  if (changed !== undefined) return changed;
  if (typeof item === "object") {
    item = EJSON.clone(item);
    adjustTypesToJSONValue(item);
  }
  return item;
};
// for both arrays and objects. Tries its best to just
// use the object you hand it, but may return something
// different if the object you hand it itself needs changing.
//
var adjustTypesFromJSONValue = EJSON._adjustTypesFromJSONValue = function(obj) {
  if (obj === null) return null;
  var maybeChanged = fromJSONValueHelper(obj);
  if (maybeChanged !== obj) return maybeChanged;
  // Other atoms are unchanged.
  if (typeof obj !== "object") return obj;
  _.each(obj, function(value, key) {
    if (typeof value === "object") {
      var changed = fromJSONValueHelper(value);
      if (value !== changed) {
        obj[key] = changed;
        return;
      }
      // if we get here, value is an object but not adjustable
      // at this level.  recurse.
      adjustTypesFromJSONValue(value);
    }
  });
  return obj;
};
// Either return the argument changed to have the non-json
// rep of itself (the Object version) or the argument itself.
// DOES NOT RECURSE.  For actually getting the fully-changed value, use
// EJSON.fromJSONValue
var fromJSONValueHelper = function(value) {
  if (typeof value === "object" && value !== null) {
    if (_.size(value) <= 2 && _.all(value, function(v, k) {
        return typeof k === "string" && k.substr(0, 1) === "$";
      })) {
      for (var i = 0; i < builtinConverters.length; i++) {
        var converter = builtinConverters[i];
        if (converter.matchJSONValue(value)) {
          return converter.fromJSONValue(value);
        }
      }
    }
  }
  return value;
};
/**
 * @summary Deserialize an EJSON value from its plain JSON representation.
 * @locus Anywhere
 * @param {JSONCompatible} val A value to deserialize into EJSON.
 */
EJSON.fromJSONValue = function(item) {
  var changed = fromJSONValueHelper(item);
  if (changed === item && typeof item === "object") {
    item = EJSON.clone(item);
    adjustTypesFromJSONValue(item);
    return item;
  } else {
    return changed;
  }
};
/**
 * @summary Serialize a value to a string.
 For EJSON values, the serialization fully represents the value. For non-EJSON values, serializes the same way as `JSON.stringify`.
 * @locus Anywhere
 * @param {EJSON} val A value to stringify.
 * @param {Object} [options]
 * @param {Boolean | Integer | String} options.indent Indents objects and arrays for easy readability.  When `true`, indents by 2 spaces; when an integer, indents by that number of spaces; and when a string, uses the string as the indentation pattern.
 * @param {Boolean} options.canonical When `true`, stringifies keys in an object in sorted order.
 */
EJSON.stringify = function(item, options) {
  var json = EJSON.toJSONValue(item);
  if (options && (options.canonical || options.indent)) {
    return EJSON._canonicalStringify(json, options);
  } else {
    return JSON.stringify(json);
  }
};
/**
 * @summary Parse a string into an EJSON value. Throws an error if the string is not valid EJSON.
 * @locus Anywhere
 * @param {String} str A string to parse into an EJSON value.
 */
EJSON.parse = function(item) {
  if (typeof item !== "string") throw new Error("EJSON.parse argument should be a string");
  return EJSON.fromJSONValue(JSON.parse(item));
};
/**
 * @summary Returns true if `x` is a buffer of binary data, as returned from [`EJSON.newBinary`](#ejson_new_binary).
 * @param {Object} x The variable to check.
 * @locus Anywhere
 */
EJSON.isBinary = function(obj) {
  return !!(typeof Uint8Array !== "undefined" && obj instanceof Uint8Array || obj && obj.$Uint8ArrayPolyfill);
};
/**
 * @summary Return true if `a` and `b` are equal to each other.  Return false otherwise.  Uses the `equals` method on `a` if present, otherwise performs a deep comparison.
 * @locus Anywhere
 * @param {EJSON} a
 * @param {EJSON} b
 * @param {Object} [options]
 * @param {Boolean} options.keyOrderSensitive Compare in key sensitive order, if supported by the JavaScript implementation.  For example, `{a: 1, b: 2}` is equal to `{b: 2, a: 1}` only when `keyOrderSensitive` is `false`.  The default is `false`.
 */
EJSON.equals = function(a, b, options) {
  var i;
  var keyOrderSensitive = !!(options && options.keyOrderSensitive);
  if (a === b) return true;
  if (_.isNaN(a) && _.isNaN(b)) return true;
  // This differs from the IEEE spec for NaN equality, b/c we don't want
  // anything ever with a NaN to be poisoned from becoming equal to anything.
  if (!a || !b) // if either one is falsy, they'd have to be === to be equal
    return false;
  if (!(typeof a === "object" && typeof b === "object")) return false;
  if (a instanceof Date && b instanceof Date) return a.valueOf() === b.valueOf();
  if (EJSON.isBinary(a) && EJSON.isBinary(b)) {
    if (a.length !== b.length) return false;
    for (i = 0; i < a.length; i++) {
      if (a[i] !== b[i]) return false;
    }
    return true;
  }
  if (typeof a.equals === "function") return a.equals(b, options);
  if (typeof b.equals === "function") return b.equals(a, options);
  if (a instanceof Array) {
    if (!(b instanceof Array)) return false;
    if (a.length !== b.length) return false;
    for (i = 0; i < a.length; i++) {
      if (!EJSON.equals(a[i], b[i], options)) return false;
    }
    return true;
  }
  // fallback for custom types that don't implement their own equals
  switch (EJSON._isCustomType(a) + EJSON._isCustomType(b)) {
    case 1:
      return false;

    case 2:
      return EJSON.equals(EJSON.toJSONValue(a), EJSON.toJSONValue(b));
  }
  // fall back to structural equality of objects
  var ret;
  if (keyOrderSensitive) {
    var bKeys = [];
    _.each(b, function(val, x) {
      bKeys.push(x);
    });
    i = 0;
    ret = _.all(a, function(val, x) {
      if (i >= bKeys.length) {
        return false;
      }
      if (x !== bKeys[i]) {
        return false;
      }
      if (!EJSON.equals(val, b[bKeys[i]], options)) {
        return false;
      }
      i++;
      return true;
    });
    return ret && i === bKeys.length;
  } else {
    i = 0;
    ret = _.all(a, function(val, key) {
      if (!_.has(b, key)) {
        return false;
      }
      if (!EJSON.equals(val, b[key], options)) {
        return false;
      }
      i++;
      return true;
    });
    return ret && _.size(b) === i;
  }
};
/**
 * @summary Return a deep copy of `val`.
 * @locus Anywhere
 * @param {EJSON} val A value to copy.
 */
EJSON.clone = function(v) {
  var ret;
  if (typeof v !== "object") return v;
  if (v === null) return null;
  // null has typeof "object"
  if (v instanceof Date) return new Date(v.getTime());
  // RegExps are not really EJSON elements (eg we don't define a serialization
  // for them), but they're immutable anyway, so we can support them in clone.
  if (v instanceof RegExp) return v;
  if (EJSON.isBinary(v)) {
    ret = EJSON.newBinary(v.length);
    for (var i = 0; i < v.length; i++) {
      ret[i] = v[i];
    }
    return ret;
  }
  // XXX: Use something better than underscore's isArray
  if (_.isArray(v) || _.isArguments(v)) {
    // For some reason, _.map doesn't work in this context on Opera (weird test
    // failures).
    ret = [];
    for (i = 0; i < v.length; i++) ret[i] = EJSON.clone(v[i]);
    return ret;
  }
  // handle general user-defined typed Objects if they have a clone method
  if (typeof v.clone === "function") {
    return v.clone();
  }
  // handle other custom types
  if (EJSON._isCustomType(v)) {
    return EJSON.fromJSONValue(EJSON.clone(EJSON.toJSONValue(v)), true);
  }
  // handle other objects
  ret = {};
  _.each(v, function(value, key) {
    ret[key] = EJSON.clone(value);
  });
  return ret;
};
/**
 * @summary Allocate a new buffer of binary data that EJSON can serialize.
 * @locus Anywhere
 * @param {Number} size The number of bytes of binary data to allocate.
 */
// EJSON.newBinary is the public documented API for this functionality,
// but the implementation is in the 'base64' package to avoid
// introducing a circular dependency. (If the implementation were here,
// then 'base64' would have to use EJSON.newBinary, and 'ejson' would
// also have to use 'base64'.)
EJSON.newBinary = Base64.newBinary;
IdMap = function(idStringify, idParse) {
  var self = this;
  self._map = {};
  self._idStringify = idStringify || JSON.stringify;
  self._idParse = idParse || JSON.parse;
};
// Some of these methods are designed to match methods on OrderedDict, since
// (eg) ObserveMultiplex and _CachingChangeObserver use them interchangeably.
// (Conceivably, this should be replaced with "UnorderedDict" with a specific
// set of methods that overlap between the two.)
_.extend(IdMap.prototype, {
  get: function(id) {
    var self = this;
    var key = self._idStringify(id);
    return self._map[key];
  },
  set: function(id, value) {
    var self = this;
    var key = self._idStringify(id);
    self._map[key] = value;
  },
  remove: function(id) {
    var self = this;
    var key = self._idStringify(id);
    delete self._map[key];
  },
  has: function(id) {
    var self = this;
    var key = self._idStringify(id);
    return _.has(self._map, key);
  },
  empty: function() {
    var self = this;
    return _.isEmpty(self._map);
  },
  clear: function() {
    var self = this;
    self._map = {};
  },
  // Iterates over the items in the map. Return `false` to break the loop.
  forEach: function(iterator) {
    var self = this;
    // don't use _.each, because we can't break out of it.
    var keys = _.keys(self._map);
    for (var i = 0; i < keys.length; i++) {
      var breakIfFalse = iterator.call(null, self._map[keys[i]], self._idParse(keys[i]));
      if (breakIfFalse === false) return;
    }
  },
  size: function() {
    var self = this;
    return _.size(self._map);
  },
  setDefault: function(id, def) {
    var self = this;
    var key = self._idStringify(id);
    if (_.has(self._map, key)) return self._map[key];
    self._map[key] = def;
    return def;
  },
  // Assumes that values are EJSON-cloneable, and that we don't need to clone
  // IDs (ie, that nobody is going to mutate an ObjectId).
  clone: function() {
    var self = this;
    var clone = new IdMap(self._idStringify, self._idParse);
    self.forEach(function(value, id) {
      clone.set(id, EJSON.clone(value));
    });
    return clone;
  }
});
// This file defines an ordered dictionary abstraction that is useful for
// maintaining a dataset backed by observeChanges.  It supports ordering items
// by specifying the item they now come before.
// The implementation is a dictionary that contains nodes of a doubly-linked
// list as its values.
// constructs a new element struct
// next and prev are whole elements, not keys.
var element = function(key, value, next, prev) {
  return {
    key: key,
    value: value,
    next: next,
    prev: prev
  };
};
OrderedDict = function() {
  var self = this;
  self._dict = {};
  self._first = null;
  self._last = null;
  self._size = 0;
  var args = _.toArray(arguments);
  self._stringify = function(x) {
    return x;
  };
  if (typeof args[0] === "function") self._stringify = args.shift();
  _.each(args, function(kv) {
    self.putBefore(kv[0], kv[1], null);
  });
};
_.extend(OrderedDict.prototype, {
  // the "prefix keys with a space" thing comes from here
  // https://github.com/documentcloud/underscore/issues/376#issuecomment-2815649
  _k: function(key) {
    return " " + this._stringify(key);
  },
  empty: function() {
    var self = this;
    return !self._first;
  },
  size: function() {
    var self = this;
    return self._size;
  },
  _linkEltIn: function(elt) {
    var self = this;
    if (!elt.next) {
      elt.prev = self._last;
      if (self._last) self._last.next = elt;
      self._last = elt;
    } else {
      elt.prev = elt.next.prev;
      elt.next.prev = elt;
      if (elt.prev) elt.prev.next = elt;
    }
    if (self._first === null || self._first === elt.next) self._first = elt;
  },
  _linkEltOut: function(elt) {
    var self = this;
    if (elt.next) elt.next.prev = elt.prev;
    if (elt.prev) elt.prev.next = elt.next;
    if (elt === self._last) self._last = elt.prev;
    if (elt === self._first) self._first = elt.next;
  },
  putBefore: function(key, item, before) {
    var self = this;
    if (self._dict[self._k(key)]) throw new Error("Item " + key + " already present in OrderedDict");
    var elt = before ? element(key, item, self._dict[self._k(before)]) : element(key, item, null);
    if (elt.next === undefined) throw new Error("could not find item to put this one before");
    self._linkEltIn(elt);
    self._dict[self._k(key)] = elt;
    self._size++;
  },
  append: function(key, item) {
    var self = this;
    self.putBefore(key, item, null);
  },
  remove: function(key) {
    var self = this;
    var elt = self._dict[self._k(key)];
    if (elt === undefined) throw new Error("Item " + key + " not present in OrderedDict");
    self._linkEltOut(elt);
    self._size--;
    delete self._dict[self._k(key)];
    return elt.value;
  },
  get: function(key) {
    var self = this;
    if (self.has(key)) return self._dict[self._k(key)].value;
    return undefined;
  },
  has: function(key) {
    var self = this;
    return _.has(self._dict, self._k(key));
  },
  // Iterate through the items in this dictionary in order, calling
  // iter(value, key, index) on each one.
  // Stops whenever iter returns OrderedDict.BREAK, or after the last element.
  forEach: function(iter) {
    var self = this;
    var i = 0;
    var elt = self._first;
    while (elt !== null) {
      var b = iter(elt.value, elt.key, i);
      if (b === OrderedDict.BREAK) return;
      elt = elt.next;
      i++;
    }
  },
  first: function() {
    var self = this;
    if (self.empty()) return undefined;
    return self._first.key;
  },
  firstValue: function() {
    var self = this;
    if (self.empty()) return undefined;
    return self._first.value;
  },
  last: function() {
    var self = this;
    if (self.empty()) return undefined;
    return self._last.key;
  },
  lastValue: function() {
    var self = this;
    if (self.empty()) return undefined;
    return self._last.value;
  },
  prev: function(key) {
    var self = this;
    if (self.has(key)) {
      var elt = self._dict[self._k(key)];
      if (elt.prev) return elt.prev.key;
    }
    return null;
  },
  next: function(key) {
    var self = this;
    if (self.has(key)) {
      var elt = self._dict[self._k(key)];
      if (elt.next) return elt.next.key;
    }
    return null;
  },
  moveBefore: function(key, before) {
    var self = this;
    var elt = self._dict[self._k(key)];
    var eltBefore = before ? self._dict[self._k(before)] : null;
    if (elt === undefined) throw new Error("Item to move is not present");
    if (eltBefore === undefined) {
      throw new Error("Could not find element to move this one before");
    }
    if (eltBefore === elt.next) // no moving necessary
      return;
    // remove from its old place
    self._linkEltOut(elt);
    // patch into its new place
    elt.next = eltBefore;
    self._linkEltIn(elt);
  },
  // Linear, sadly.
  indexOf: function(key) {
    var self = this;
    var ret = null;
    self.forEach(function(v, k, i) {
      if (self._k(k) === self._k(key)) {
        ret = i;
        return OrderedDict.BREAK;
      }
      return undefined;
    });
    return ret;
  },
  _checkRep: function() {
    var self = this;
    _.each(self._dict, function(k, v) {
      if (v.next === v) throw new Error("Next is a loop");
      if (v.prev === v) throw new Error("Prev is a loop");
    });
  }
});
OrderedDict.BREAK = {
  "break": true
};

MinimongoError = function(message) {
  var e = new Error(message);
  e.name = "MinimongoError";
  return e;
};

LocalCollection = function(name) {
  var self = this;
  self.name = name;
  // _id -> document (also containing id)
  self.next_qid = 1;
  // live query id generator
  // qid -> live query object. keys:
  //  ordered: bool. ordered queries have addedBefore/movedBefore callbacks.
  //  results: array (ordered) or object (unordered) of current results
  //    (aliased with self._docs!)
  //  resultsSnapshot: snapshot of results. null if not paused.
  //  cursor: Cursor object for the query.
  //  selector, sorter, (callbacks): functions
  self.queries = {};
  // null if not saving originals; an IdMap from id to original document value if
  // saving originals. See comments before saveOriginals().
  self._savedOriginals = null;
  // True when observers are paused and we should not send callbacks.
  self.paused = false;
};

LocalCollection._f = {
  // XXX for _all and _in, consider building 'inquery' at compile time..
  _type: function(v) {
    if (typeof v === "number") return 1;
    if (typeof v === "string") return 2;
    if (typeof v === "boolean") return 8;
    if (isArray(v)) return 4;
    if (v === null) return 10;
    if (v instanceof RegExp) // note that typeof(/x/) === "object"
      return 11;
    if (typeof v === "function") return 13;
    if (v instanceof Date) return 9;
    if (EJSON.isBinary(v)) return 5;
    // if (v instanceof LocalCollection._ObjectID) return 7;
    return 3;
  },
  // deep equality test: use for literal document and array matches
  _equal: function(a, b) {
    return EJSON.equals(a, b, {
      keyOrderSensitive: true
    });
  },
  // maps a type code to a value that can be used to sort values of
  // different types
  _typeorder: function(t) {
    // http://www.mongodb.org/display/DOCS/What+is+the+Compare+Order+for+BSON+Types
    // XXX what is the correct sort position for Javascript code?
    // ('100' in the matrix below)
    // XXX minkey/maxkey
    return [ -1, // (not a type)
             1, // number
             2, // string
             3, // object
             4, // array
             5, // binary
             -1, // deprecated
             6, // ObjectID
             7, // bool
             8, // Date
             0, // null
             9, // RegExp
             -1, // deprecated
             100, // JS code
             2, // deprecated (symbol)
             100, // JS code
             1, // 32-bit int
             8, // Mongo timestamp
             1 ][t];
  },
  // compare two values of unknown type according to BSON ordering
  // semantics. (as an extension, consider 'undefined' to be less than
  // any other value.) return negative if a is less, positive if b is
  // less, or 0 if equal
  _cmp: function(a, b) {
    if (a === undefined) return b === undefined ? 0 : -1;
    if (b === undefined) return 1;
    var ta = LocalCollection._f._type(a);
    var tb = LocalCollection._f._type(b);
    var oa = LocalCollection._f._typeorder(ta);
    var ob = LocalCollection._f._typeorder(tb);
    if (oa !== ob) return oa < ob ? -1 : 1;
    if (ta !== tb) // XXX need to implement this if we implement Symbol or integers, or
    // Timestamp
      throw Error("Missing type coercion logic in _cmp");
    if (ta === 7) {
      // ObjectID
      // Convert to string.
      ta = tb = 2;
      a = a.toHexString();
      b = b.toHexString();
    }
    if (ta === 9) {
      // Date
      // Convert to millis.
      ta = tb = 1;
      a = a.getTime();
      b = b.getTime();
    }
    if (ta === 1) // double
      return a - b;
    if (tb === 2) // string
      return a < b ? -1 : a === b ? 0 : 1;
    if (ta === 3) {
      // Object
      // this could be much more efficient in the expected case ...
      var to_array = function(obj) {
        var ret = [];
        for (var key in obj) {
          ret.push(key);
          ret.push(obj[key]);
        }
        return ret;
      };
      return LocalCollection._f._cmp(to_array(a), to_array(b));
    }
    if (ta === 4) {
      // Array
      for (var i = 0; ;i++) {
        if (i === a.length) return i === b.length ? 0 : -1;
        if (i === b.length) return 1;
        var s = LocalCollection._f._cmp(a[i], b[i]);
        if (s !== 0) return s;
      }
    }
    if (ta === 5) {
      // binary
      // Surprisingly, a small binary blob is always less than a large one in
      // Mongo.
      if (a.length !== b.length) return a.length - b.length;
      for (i = 0; i < a.length; i++) {
        if (a[i] < b[i]) return -1;
        if (a[i] > b[i]) return 1;
      }
      return 0;
    }
    if (ta === 8) {
      // boolean
      if (a) return b ? 0 : 1;
      return b ? -1 : 0;
    }
    if (ta === 10) // null
      return 0;
    if (ta === 11) // regexp
      throw Error("Sorting not supported on regular expression");
    // XXX
    // 13: javascript code
    // 14: symbol
    // 15: javascript code with scope
    // 16: 32-bit integer
    // 17: timestamp
    // 18: 64-bit integer
    // 255: minkey
    // 127: maxkey
    if (ta === 13) // javascript code
      throw Error("Sorting not supported on Javascript code");
    // XXX
    throw Error("Unknown type to sort");
  }
};

isArray = function(x) {
  return _.isArray(x) && !EJSON.isBinary(x);
};

isPlainObject = LocalCollection._isPlainObject = function(x) {
  return x && LocalCollection._f._type(x) === 3;
};
isIndexable = function(x) {
  return isArray(x) || isPlainObject(x);
};

LocalCollection._modify = function(doc, mod, options) {
  options = options || {};
  if (!isPlainObject(mod)) throw MinimongoError("Modifier must be an object");
  var isModifier = isOperatorObject(mod);
  var newDoc;
  if (!isModifier) {
    if (mod._id && !EJSON.equals(doc._id, mod._id)) throw MinimongoError("Cannot change the _id of a document");
    // replace the whole document
    for (var k in mod) {
      if (/\./.test(k)) throw MinimongoError("When replacing document, field name may not contain '.'");
    }
    newDoc = mod;
  } else {
    // apply modifiers to the doc.
    newDoc = EJSON.clone(doc);
    _.each(mod, function(operand, op) {
      var modFunc = MODIFIERS[op];
      // Treat $setOnInsert as $set if this is an insert.
      if (options.isInsert && op === "$setOnInsert") modFunc = MODIFIERS["$set"];
      if (!modFunc) throw MinimongoError("Invalid modifier specified " + op);
      _.each(operand, function(arg, keypath) {
        if (keypath === "") {
          throw MinimongoError("An empty update path is not valid.");
        }
        if (keypath === "_id") {
          throw MinimongoError("Mod on _id not allowed");
        }
        var keyparts = keypath.split(".");
        if (!_.all(keyparts, _.identity)) {
          throw MinimongoError("The update path '" + keypath + "' contains an empty field name, which is not allowed.");
        }
        var noCreate = _.has(NO_CREATE_MODIFIERS, op);
        var forbidArray = op === "$rename";
        var target = findModTarget(newDoc, keyparts, {
          noCreate: NO_CREATE_MODIFIERS[op],
          forbidArray: op === "$rename",
          arrayIndices: options.arrayIndices
        });
        var field = keyparts.pop();
        modFunc(target, field, arg, keypath, newDoc);
      });
    });
  }
  // move new document into place.
  _.each(_.keys(doc), function(k) {
    // Note: this used to be for (var k in doc) however, this does not
    // work right in Opera. Deleting from a doc while iterating over it
    // would sometimes cause opera to skip some keys.
    if (k !== "_id") delete doc[k];
  });
  _.each(newDoc, function(v, k) {
    doc[k] = v;
  });
};
// for a.b.c.2.d.e, keyparts should be ['a', 'b', 'c', '2', 'd', 'e'],
// and then you would operate on the 'e' property of the returned
// object.
//
// if options.noCreate is falsey, creates intermediate levels of
// structure as necessary, like mkdir -p (and raises an exception if
// that would mean giving a non-numeric property to an array.) if
// options.noCreate is true, return undefined instead.
//
// may modify the last element of keyparts to signal to the caller that it needs
// to use a different value to index into the returned object (for example,
// ['a', '01'] -> ['a', 1]).
//
// if forbidArray is true, return null if the keypath goes through an array.
//
// if options.arrayIndices is set, use its first element for the (first) '$' in
// the path.
var findModTarget = function(doc, keyparts, options) {
  options = options || {};
  var usedArrayIndex = false;
  for (var i = 0; i < keyparts.length; i++) {
    var last = i === keyparts.length - 1;
    var keypart = keyparts[i];
    var indexable = isIndexable(doc);
    if (!indexable) {
      if (options.noCreate) return undefined;
      var e = MinimongoError("cannot use the part '" + keypart + "' to traverse " + doc);
      e.setPropertyError = true;
      throw e;
    }
    if (doc instanceof Array) {
      if (options.forbidArray) return null;
      if (keypart === "$") {
        if (usedArrayIndex) throw MinimongoError("Too many positional (i.e. '$') elements");
        if (!options.arrayIndices || !options.arrayIndices.length) {
          throw MinimongoError("The positional operator did not find the " + "match needed from the query");
        }
        keypart = options.arrayIndices[0];
        usedArrayIndex = true;
      } else if (isNumericKey(keypart)) {
        keypart = parseInt(keypart);
      } else {
        if (options.noCreate) return undefined;
        throw MinimongoError("can't append to array using string field name [" + keypart + "]");
      }
      if (last) // handle 'a.01'
        keyparts[i] = keypart;
      if (options.noCreate && keypart >= doc.length) return undefined;
      while (doc.length < keypart) doc.push(null);
      if (!last) {
        if (doc.length === keypart) doc.push({}); else if (typeof doc[keypart] !== "object") throw MinimongoError("can't modify field '" + keyparts[i + 1] + "' of list value " + JSON.stringify(doc[keypart]));
      }
    } else {
      if (keypart.length && keypart.substr(0, 1) === "$") throw MinimongoError("can't set field named " + keypart);
      if (!(keypart in doc)) {
        if (options.noCreate) return undefined;
        if (!last) doc[keypart] = {};
      }
    }
    if (last) return doc;
    doc = doc[keypart];
  }
};
var NO_CREATE_MODIFIERS = {
  $unset: true,
  $pop: true,
  $rename: true,
  $pull: true,
  $pullAll: true
};
var MODIFIERS = {
  $inc: function(target, field, arg) {
    if (typeof arg !== "number") throw MinimongoError("Modifier $inc allowed for numbers only");
    if (field in target) {
      if (typeof target[field] !== "number") throw MinimongoError("Cannot apply $inc modifier to non-number");
      target[field] += arg;
    } else {
      target[field] = arg;
    }
  },
  $set: function(target, field, arg) {
    if (!_.isObject(target)) {
      // not an array or an object
      var e = MinimongoError("Cannot set property on non-object field");
      e.setPropertyError = true;
      throw e;
    }
    if (target === null) {
      var e = MinimongoError("Cannot set property on null");
      e.setPropertyError = true;
      throw e;
    }
    target[field] = EJSON.clone(arg);
  },
  $setOnInsert: function(target, field, arg) {},
  $unset: function(target, field, arg) {
    if (target !== undefined) {
      if (target instanceof Array) {
        if (field in target) target[field] = null;
      } else delete target[field];
    }
  },
  $push: function(target, field, arg) {
    if (target[field] === undefined) target[field] = [];
    if (!(target[field] instanceof Array)) throw MinimongoError("Cannot apply $push modifier to non-array");
    if (!(arg && arg.$each)) {
      // Simple mode: not $each
      target[field].push(EJSON.clone(arg));
      return;
    }
    // Fancy mode: $each (and maybe $slice and $sort)
    var toPush = arg.$each;
    if (!(toPush instanceof Array)) throw MinimongoError("$each must be an array");
    // Parse $slice.
    var slice = undefined;
    if ("$slice" in arg) {
      if (typeof arg.$slice !== "number") throw MinimongoError("$slice must be a numeric value");
      // XXX should check to make sure integer
      if (arg.$slice > 0) throw MinimongoError("$slice in $push must be zero or negative");
      slice = arg.$slice;
    }
    // Parse $sort.
    var sortFunction = undefined;
    if (arg.$sort) {
      if (slice === undefined) throw MinimongoError("$sort requires $slice to be present");
      // XXX this allows us to use a $sort whose value is an array, but that's
      // actually an extension of the Node driver, so it won't work
      // server-side. Could be confusing!
      // XXX is it correct that we don't do geo-stuff here?
      sortFunction = new Minimongo.Sorter(arg.$sort).getComparator();
      for (var i = 0; i < toPush.length; i++) {
        if (LocalCollection._f._type(toPush[i]) !== 3) {
          throw MinimongoError("$push like modifiers using $sort " + "require all elements to be objects");
        }
      }
    }
    // Actually push.
    for (var j = 0; j < toPush.length; j++) target[field].push(EJSON.clone(toPush[j]));
    // Actually sort.
    if (sortFunction) target[field].sort(sortFunction);
    // Actually slice.
    if (slice !== undefined) {
      if (slice === 0) target[field] = []; else target[field] = target[field].slice(slice);
    }
  },
  $pushAll: function(target, field, arg) {
    if (!(typeof arg === "object" && arg instanceof Array)) throw MinimongoError("Modifier $pushAll/pullAll allowed for arrays only");
    var x = target[field];
    if (x === undefined) target[field] = arg; else if (!(x instanceof Array)) throw MinimongoError("Cannot apply $pushAll modifier to non-array"); else {
      for (var i = 0; i < arg.length; i++) x.push(arg[i]);
    }
  },
  $addToSet: function(target, field, arg) {
    var isEach = false;
    if (typeof arg === "object") {
      //check if first key is '$each'
      for (var k in arg) {
        if (k === "$each") isEach = true;
        break;
      }
    }
    var values = isEach ? arg["$each"] : [ arg ];
    var x = target[field];
    if (x === undefined) target[field] = values; else if (!(x instanceof Array)) throw MinimongoError("Cannot apply $addToSet modifier to non-array"); else {
      _.each(values, function(value) {
        for (var i = 0; i < x.length; i++) if (LocalCollection._f._equal(value, x[i])) return;
        x.push(EJSON.clone(value));
      });
    }
  },
  $pop: function(target, field, arg) {
    if (target === undefined) return;
    var x = target[field];
    if (x === undefined) return; else if (!(x instanceof Array)) throw MinimongoError("Cannot apply $pop modifier to non-array"); else {
      if (typeof arg === "number" && arg < 0) x.splice(0, 1); else x.pop();
    }
  },
  $pull: function(target, field, arg) {
    if (target === undefined) return;
    var x = target[field];
    if (x === undefined) return; else if (!(x instanceof Array)) throw MinimongoError("Cannot apply $pull/pullAll modifier to non-array"); else {
      var out = [];
      if (typeof arg === "object" && !(arg instanceof Array)) {
        // XXX would be much nicer to compile this once, rather than
        // for each document we modify.. but usually we're not
        // modifying that many documents, so we'll let it slide for
        // now
        // XXX Minimongo.Matcher isn't up for the job, because we need
        // to permit stuff like {$pull: {a: {$gt: 4}}}.. something
        // like {$gt: 4} is not normally a complete selector.
        // same issue as $elemMatch possibly?
        var matcher = new Minimongo.Matcher(arg);
        for (var i = 0; i < x.length; i++) if (!matcher.documentMatches(x[i]).result) out.push(x[i]);
      } else {
        for (var i = 0; i < x.length; i++) if (!LocalCollection._f._equal(x[i], arg)) out.push(x[i]);
      }
      target[field] = out;
    }
  },
  $pullAll: function(target, field, arg) {
    if (!(typeof arg === "object" && arg instanceof Array)) throw MinimongoError("Modifier $pushAll/pullAll allowed for arrays only");
    if (target === undefined) return;
    var x = target[field];
    if (x === undefined) return; else if (!(x instanceof Array)) throw MinimongoError("Cannot apply $pull/pullAll modifier to non-array"); else {
      var out = [];
      for (var i = 0; i < x.length; i++) {
        var exclude = false;
        for (var j = 0; j < arg.length; j++) {
          if (LocalCollection._f._equal(x[i], arg[j])) {
            exclude = true;
            break;
          }
        }
        if (!exclude) out.push(x[i]);
      }
      target[field] = out;
    }
  },
  $rename: function(target, field, arg, keypath, doc) {
    if (keypath === arg) // no idea why mongo has this restriction..
      throw MinimongoError("$rename source must differ from target");
    if (target === null) throw MinimongoError("$rename source field invalid");
    if (typeof arg !== "string") throw MinimongoError("$rename target must be a string");
    if (target === undefined) return;
    var v = target[field];
    delete target[field];
    var keyparts = arg.split(".");
    var target2 = findModTarget(doc, keyparts, {
      forbidArray: true
    });
    if (target2 === null) throw MinimongoError("$rename target field invalid");
    var field2 = keyparts.pop();
    target2[field2] = v;
  },
  $bit: function(target, field, arg) {
    // XXX mongo only supports $bit on integers, and we only support
    // native javascript numbers (doubles) so far, so we can't support $bit
    throw MinimongoError("$bit is not supported");
  }
};


export default LocalCollection._modify;
// var newObject = {_id: "test", abc: "def"}
// var newTest = LocalCollection._modify(newObject, {$set: {abc: "werwe"}})
// console.log("newTest", newObject);