dotdb.js

// Copyright (C) 2019 rameshvk. All rights reserved.
// Use of this source code is governed by a MIT-style license
// that can be found in the LICENSE file.
// **** Code generated by dotjs/x/generate_dist.js ***

"use strict";






const valueTypes = {};
const changeTypes = {};


class Decoder {
  decode(value) {
    if (value === undefined || value === null) {
      return null;
    }

    for (let key in value) {
      switch (key) {
        case "bool":
          return value.bool;
        case "int":
          return value.int;
        case "float64":
          return +value.float64;
        case "string":
          return value.string;
        case "time.Time":
          return new Date(value[key]);
      }
    }

    const val = this.decodeValue(value);
    if (val !== undefined) {
      return val;
    }

    return this.decodeChange(value);
  }

  decodeValue(v) {
    for (let key in v) {
      if (valueTypes.hasOwnProperty(key)) {
        return valueTypes[key].fromJSON(this, v[key]);
      }
    }
  }

  decodeChange(c) {
    if (c === null) {
      return null;
    }

    for (let key in c) {
      if (changeTypes.hasOwnProperty(key)) {
        return changeTypes[key].fromJSON(this, c[key]);
      }
    }
  }

  // registerValueClass registers value types. This is needed
  // for encoding/decoding value types
  //
  // Value classes should include a static method typeName() which
  // provides the associated golang type
  static registerValueClass(valueConstructor) {
    valueTypes[valueConstructor.typeName()] = valueConstructor;
  }

  // registerChangeClass registers change types. This is needed
  // for encoding/decoding change types
  //
  // Change classes should include a static method typeName() which
  // provides the associated golang type
  static registerChangeClass(changeConstructor) {
    changeTypes[changeConstructor.typeName()] = changeConstructor;
  }
}







class Encoder {
  static encode(value) {
    if (value === undefined || value === null) {
      return null;
    }

    if (value && value.constructor && value.constructor.typeName) {
      return { [value.constructor.typeName()]: value };
    }

    if (value instanceof Date) {
      return { "time.Time": Encoder.encodeDateValue(value) };
    }

    value = value.valueOf();
    switch (typeof value) {
      case "boolean":
        return { bool: Encoder.encodeBoolValue(value) };
      case "number":
        return Encoder.encodeNumber(value);
      case "string":
        return { string: value };
    }
  }

  static encodeBoolValue(b) {
    return b.valueOf();
  }

  static encodeNumber(i) {
    if (Number.isSafeInteger(i)) {
      return { int: i };
    }
    return { float64: i.toString() };
  }

  static encodeDateValue(date) {
    const pad = (n, width) => n.toString().padStart(width, "0");
    const offset = date.getTimezoneOffset();
    return (
      pad(date.getFullYear(), 4) +
      "-" +
      pad(date.getMonth() + 1, 2) +
      "-" +
      pad(date.getDate(), 2) +
      "T" +
      pad(date.getHours(), 2) +
      ":" +
      pad(date.getMinutes(), 2) +
      ":" +
      pad(date.getSeconds(), 2) +
      "." +
      pad(date.getMilliseconds(), 3) +
      (offset > 0 ? "-" : "+") +
      pad(Math.floor(Math.abs(offset) / 60), 2) +
      ":" +
      pad(Math.abs(offset) % 60, 2)
    );
  }

  static encodeArrayValue(a) {
    if (a === undefined || a === null) {
      return null;
    }

    return a.map(Encoder.encode);
  }
}

const encode = Encoder.encode;









/** Replace represents a change one value to another **/
class Replace {
  /**
   * before and after must be valid Value types (that implement apply()).
   *
   * @param {Value} before - the value as it was before.
   * @param {Value} after - the value as it is after.
   */
  constructor(before, after) {
    this.before = before;
    this.after = after;
  }

  /** @returns {Replace} - the inverse of the replace */
  revert() {
    return new Replace(this.after, this.before);
  }

  _isDelete() {
    return this.after.constructor.typeName() == "changes.empty";
  }

  /**
   * Merge another change and return modified version of
   * the other and current change.
   *
   * current + returned[0] and other + returned[1] are guaranteed
   * to result in the same state.
   *
   * @returns {Change[]}
   */
  merge(other) {
    if (other == null) {
      return [null, this];
    }
    if (other instanceof Replace) {
      return this._mergeReplace(other);
    }
    const [left, right] = other.reverseMerge(this);
    return [right, left];
  }

  _mergeReplace(other) {
    if (this._isDelete() && other._isDelete()) {
      return [null, null];
    }
    return [new Replace(this.after, other.after), null];
  }

  toJSON() {
    return Encoder.encodeArrayValue([this.before, this.after]);
  }

  static typeName() {
    return "changes.Replace";
  }

  static fromJSON(decoder, json) {
    const before = decoder.decodeValue(json[0]);
    const after = decoder.decodeValue(json[1]);
    return new Replace(before, after);
  }
}

Decoder.registerChangeClass(Replace);






/**
 * Stream tracks all future changes to a particular value.
 *
 * Use the next property to check if there is a subsequent change.
 *
 * The next property is null if there is no further change yet. It is
 * an object `{change, version}` where change refers to the actual
 * change and version refers to the next stream instance (with its own
 * next field if there are further changes).
 *
 * The whole stream is effectively immutable with the next field only
 * ever getting written to once when a new version happens. If more
 * changes are made on the current stream, those versions are tacked
 * on at the end of the next version (with the changes appropriately
 * factoring all other changes),
 *
 * Streams are convergent: chasing the next pointer of any stream
 * instance in a particular stream will converge (i.e applying the
 * changes will end up with same value even if the changes themselves
 * are a little different).
 *
 */
class Stream {
  constructor() {
    this.next = null;
  }

  /* push commits any changes upstream */
  push() {
    return null;
  }

  /* pull fetches any upstream changes which will be avilable via next */
  pull() {
    return null;
  }

  /* undo reverts the last change on the underlying stream which could
   * be a parent stream. The last change may not really affect the
   * current stream directly.
   *
   * Normal streams do not support undo but a stream created via
   *`undoable` (and all its descendant streams/sub-streams) support
   * undo.
   */
  undo() {
    return null;
  }

  /* redo reapplies the last change that got reverted by undo */
  redo() {
    return null;
  }

  /* append adds a local change */
  append(c) {
    return {change: c, version: this._appendChange(c, false)};
  }

  /* reverseAppend adds an *upstream* change; meant to be used by nw
   * synchronizers */
  reverseAppend(c) {
    return {change: c, version: this._appendChange(c, true)};
  }

  _appendChange(c, reverse) {
    const result = new Stream();
    let s = this;
    let nexts = result;
    while (s.next !== null) {
      let { change, version } = s.next;
      s = version;

      [c, change] = this._merge(change, c, reverse);
      nexts.next = { change, version: new Stream() };
      nexts = nexts.next.version;
    }
    s.next = { change: c, version: nexts };
    return result;
  }

  _merge(left, right, reverse) {
    if (left === null || right === null) {
      return [right, left];
    }

    if (!reverse) {
      return left.merge(right);
    }

    [right, left] = right.merge(left);
    return [left, right];
  }
}

/** DerivedStream is a base class for all derived streams */
class DerivedStream {
  constructor(parent) {
    this.parent = parent;
    this._next = null;
  }

  append() {
    return null;
  }

  reverseAppend() {
    return null;
  }

  push() {
    return this.parent && this.parent.push();
  }

  pull() {
    return this.parent && this.parent.pull();
  }

  undo() {
    return this.parent && this.parent.undo();
  }

  redo() {
    return this.parent && this.parent.redo();
  }

  get next() {
    if (this._next) {
      return this._next;
    }

    const next = this._getNext();
    if (next) {
      this._next = next;
    }
    return next;
  }
}








/**
 * branch creates a branched stream.  Updates to the returned branched
 * stream or the parent stream are not automatically carried over to
 * each other.  Instead, returned branch stream implements push() and
 * pull() to do this on demand.
 *
 * @param {Stream} s - parent stream
 * @returns {Stream}
 */
function branch(s) {
  const child = new Stream();
  return new BranchStream(child, { parent: s, child });
}

class BranchStream {
  constructor(parent, info) {
    this.parent = parent;
    this.info = info;
  }

  push() {
    const info = this.info;
    for (let next = info.child.next; next ; next = info.child.next) {
      const { change, version } = next;
      info.parent = info.parent.append(change).version;
      info.child = version;
    }

    return null;
  }

  pull() {
    const info = this.info;
    for (let next = info.parent.next; next != null; next = info.parent.next) {
      const { change, version } = next;
      info.child = info.child.reverseAppend(change).version;
      info.parent = version;
    }

    return null;
  }

  get next() {
    return this._nextf(this.parent.next);
  }

  append(c) {
    return this._nextf(this.parent && this.parent.append(c));
  }

  reverseAppend(c) {
    return this._nextf(this.parent && this.parent.reverseAppend(c));
  }

  _nextf(n) {
    if (!n) {
      return null;
    }
    const version = new BranchStream(n.version, this.info);
    return {change: n.change, version};
  }

  undo() {
    return this.parent.undo();
  }

  redo() {
    return this.parent.redo();
  }
}









/** Value is the base class for values.
 *
 * It should not be used directly but by subclassing.
 * Subclasses should implement clone(), toJSON(), static typeName() as
 * well as static fromJSON and optionally override apply().
 */
class Value {
  constructor() {
    this.stream = null;
    this._next = null;
  }

  /** setStream mutates the current value and updates it stream **/
  setStream(s) {
    this.stream = s;
    return this;
  }

  /**
   * replace substitutes this with another value
   * @returns {Value} r - r has same stream as this
   **/
  replace(replacement) {
    return this.appendChange(new Replace(this.clone(), replacement.clone())).version;
  }

  /**
   * appendChange applies a change to the value and the underlying stream
   * It returns a {change, version} tuple much like next does.
   */
  appendChange(c) {
    if (!this.stream) {
      return this.apply(c).clone();
    }
    const n = this.stream.append(c);
    if (!n) {
      return this;
    }
    return this._nextf(n.change, n.version);
  }

  /** @type {Object} null or {change, version} */
  get next() {
    if (this._next !== null || !this.stream) {
      return this._next;
    }

    let n = this.stream.next;
    for (; n && !n.change; n = n.version.next) {
      // the following *mutation* is not strictly needed but improves
      // performance when an value is referred to by multiple derived
      // computations. it also helps better garbage collection of streams
      this.stream = n.version;
    }

    if (!n) return null;
    this._next = this._nextf(n.change, n.version);
    return this._next;
  }

  /** latest returns the latest version */
  latest() {
    let result = this;
    for (let n = this.next; n; n = result.next) {
      result = n.version;
    }
    return result;
  }

  _nextf(change, version) {
    return {
      change,
      version: this.apply(change)
        .clone()
        .setStream(version)
    };
  }

  /** default apply only supports Replace */
  apply(c) {
    if (!c) {
      return this.clone();
    }

    if (c instanceof Replace) {
      return c.after;
    }

    return c.applyTo(this);
  }

  /** branch returns a value that is on its own branch with push/pull support **/
  branch() {
    return this.clone().setStream(branch(this.stream));
  }

  /** push pushes the changes up to the parent */
  push() {
    return this.stream && this.stream.push();
  }

  /** pull pulls changes from the parent */
  pull() {
    return this.stream && this.stream.pull();
  }

  /** undoes the last change on this branch */
  undo() {
    return this.stream && this.stream.undo();
  }

  /** redoes the last undo on this branch */
  redo() {
    return this.stream && this.stream.redo();
  }
}









/** Bool represents true/false */
class Bool extends Value {
  constructor(b) {
    super();
    this.b = Boolean(b);
  }

  valueOf() {
    return this.b;
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new Bool(this.b);
  }

  toJSON() {
    return this.b;
  }

  static typeName() {
    return "dotdb.Bool";
  }

  static fromJSON(decoder, json) {
    return new Bool(json);
  }
}

Decoder.registerValueClass(Bool);









/** Implements a collection of change values */
class Changes {
  /** @param {...Change|Change[]} changes - sequentially combine changes */
  constructor(...changes) {
    this._all = [];
    for (let cx of changes) {
      if (cx instanceof Changes) {
        cx = cx._all;
      }
      if (!Array.isArray(cx)) {
        cx = [cx];
      }
      for (let c of cx) {
        this._all.push(c);
      }
    }
  }

  /** @returns {Changes} - the inverse of the collection */
  revert() {
    let result = [];
    for (let kk = this._all.length - 1; kk >= 0; kk--) {
      const c = this._all[kk] && this._all[kk].revert();
      if (c) {
        result.push(c);
      }
    }
    return Changes.create(result);
  }

  /**
   * Merge another change and return modified version of
   * the other and current change.
   *
   * current + returned[0] and other + returned[1] are guaranteed
   * to result in the same state.
   *
   * @returns {Change[]}
   */
  merge(other) {
    if (other == null) {
      return [null, this];
    }

    let result = [];
    for (let c of this._all) {
      if (c !== null) {
        [other, c] = c.merge(other);
      }
      if (c !== null) {
        result.push(c);
      }
    }
    return [other, Changes.create(result)];
  }

  reverseMerge(other) {
    if (other == null) {
      return [null, this];
    }

    let result = [];
    for (let c of this._all) {
      if (other != null) {
        [c, other] = other.merge(c);
      }
      if (c !== null) {
        result.push(c);
      }
    }
    return [other, Changes.create(result)];
  }

  applyTo(value) {
    for (let c of this._all) {
      value = value.apply(c);
    }
    return value;
  }

  *[Symbol.iterator]() {
    for (let c of this._all) {
      yield c;
    }
  }

  toJSON() {
    return Encoder.encodeArrayValue(this._all);
  }

  static typeName() {
    return "changes.ChangeSet";
  }

  static fromJSON(decoder, json) {
    if (!json || !json.length) {
      return null;
    }
    return new Changes(json.map(elt => decoder.decodeChange(elt)));
  }

  static create(elts) {
    if (elts && elts.length === 1) {
      return elts[0];
    }
    return (elts && elts.length && new Changes(elts)) || null;
  }
}

Decoder.registerChangeClass(Changes);








let getRandomValues = null;

/*eslint-disable */
if (typeof crypto !== "undefined") {
  getRandomValues = b => crypto.getRandomValues(b);
}
/*eslint-enable */

/** Operation is the change and metadata needed for network transmission */
class Operation {
  /**
   * @param {string} [id] - the id is typically auto-generated.
   * @param {string} [parentId] - the id of the previous unacknowledged local op.
   * @param {int} [version] - the zero-based index is updated by the server.
   * @param {int} basis -- the version of the last applied acknowledged op.
   * @param {Change} changes -- the actual change being sent to the server.
   */
  constructor(id, parentId, version, basis, changes) {
    this.id = id || Operation.newId();
    this.parentId = parentId;
    this.version = version;
    this.basis = basis;
    this.changes = changes;
  }

  toJSON() {
    const unencoded = [this.id, this.parentId, this.changes];
    const [id, parentId, c] = Encoder.encodeArrayValue(unencoded);
    return [id, parentId, this.version, this.basis, c];
  }

  merge(otherOp) {
    if (!this.changes) {
      return [otherOp, this];
    }

    const [l, r] = this.changes.merge(otherOp.changes);
    return [otherOp.withChanges(l), this.withChanges(r)];
  }

  withChanges(c) {
    return new Operation(this.id, this.parentId, this.version, this.basis, c);
  }

  static typeName() {
    return "ops.Operation";
  }

  static fromJSON(decoder, json) {
    const [id, parentId, version, basis, changes] = json;
    return new Operation(
      decoder.decode(id),
      decoder.decode(parentId),
      version,
      basis,
      decoder.decodeChange(changes)
    );
  }

  static newId() {
    const bytes = new Uint8Array(16);
    getRandomValues(bytes);
    const toHex = x => ("00" + x.toString(16)).slice(-2);
    return Array.prototype.map.call(bytes, toHex).join("");
  }

  /*
   * useCrypto should be used to provide the polyfill for crypto
   * @param [Object] crypto - the crypto module
   * @param [function] cyrpto.randomFillSync -- this is only function used here
   */
  static useCrypto(crypto) {
    getRandomValues = crypto.randomFillSync;
  }
}









class Request {
  constructor(name, ops, version, limit, duration) {
    this.name = name;
    this.ops = ops;
    this.version = version;
    this.limit = limit;
    this.duration = duration;
  }

  toJSON() {
    const ops = Encoder.encodeArrayValue(this.ops);
    return [this.name, ops, this.version, this.limit, this.duration];
  }

  static typeName() {
    return "ops/nw.request";
  }

  static fromJSON(decoder, json) {
    const [name, ops, version, limit, duration] = json;
    const opx = (ops || []).map(op =>
      Operation.fromJSON(decoder, op[Operation.typeName()])
    );
    if (name == "Append") {
      return new AppendRequest(opx);
    } else {
      return new GetSinceRequest(version, limit, duration);
    }
  }
}

class AppendRequest extends Request {
  constructor(ops) {
    super("Append", ops, -1, -1, 0);
  }
}

class GetSinceRequest extends Request {
  constructor(version, limit, duration) {
    super("GetSince", null, version, limit, duration);
  }
}









class Response {
  constructor(ops, err) {
    this.ops = ops || [];
    this.err = err || null;
  }

  toJSON() {
    let err = null;
    if (this.err) {
      const s = this.err.toString().replace("Error: ", "");
      err = { "ops/nw.strError": s };
    }

    return [Encoder.encodeArrayValue(this.ops || []), err];
  }

  static typeName() {
    return "ops/nw.response";
  }

  static fromJSON(decoder, json) {
    const err = (json[1] && new Error(json[1]["ops/nw.strError"])) || null;
    const decode = op => Operation.fromJSON(decoder, op[Operation.typeName()]);
    return new Response((json[0] || []).map(decode), err);
  }
}












/**
 * Conn creates a network connection or use with Session. See {@link Transformer}.
 */
class Conn {
  /**
   * @param {string} url - url to post requests to
   * @param {function} fetch - window.fetch implementation or polyfill
   */
  constructor(url, fetch) {
    this._request = Conn._request.bind(null, url, fetch);
    this._limit = 1000;
    this._duration = 30 * 1000 * 1000 * 1000;
  }

  /** withPollMilliseconds specifies poll interval to pass on to server */
  withPollMilliseconds(ms) {
    this._duration = ms * 1000 * 1000;
    return this;
  }

  /**
   * write ops using fetch
   * @param [Operation[]] ops - ops to write
   * @returns {Promise}
   */
  write(ops) {
    return this._request(new AppendRequest(ops));
  }

  /**
   * read ops using fetch
   * @param [int] version - version of op to start fetching from
   * @param [limit] limit - max number of ops to fetch
   * @param [duration] duration - max long poll interval to pass to server
   * @returns {Promise}
   */
  read(version, limit, duration) {
    duration = duration || this._duration;
    return this._request(new GetSinceRequest(version, limit, duration));
  }

  static async _request(url, fetch, req) {
    const headers = { "Content-Type": " application/x-sjson" };
    const body = JSON.stringify(Encoder.encode(req));

    const res = await fetch(url, { method: "POST", body, headers });
    if (!res.ok) {
      return Promise.reject(new Error(res.status + " " + res.statusText));
    }
    const json = await res.json();
    const r = Response.fromJSON(new Decoder(), json[Response.typeName()]);
    if (r.err) {
      return Promise.reject(r.err);
    }

    return (r.ops && r.ops.length && r.ops) || null;
  }
}









/** PathChange represents an embedded value changing at the specified path. */
class PathChange {
  /**
   * The path is a sequence of index or key name to refer to the embeded value.
   *
   * Example: root.rows[3] will have path ["rows", 3].
   *
   * @param {Any[]} path - path to inner value.
   * @param {Change} change - any change applied to inner value at path.
   */
  constructor(path, change) {
    if (path == undefined) {
      path = null;
    }
    if (change === undefined) {
      change = null;
    }

    this.path = path;
    this.change = change;
  }

  /** @returns {Change} - the inverse of this change */
  revert() {
    if (this.change == null) {
      return null;
    }

    return PathChange.create(this.path, this.change.revert());
  }

  reverseMerge(other) {
    if (this.path === null || this.path.length === 0) {
      const [left, right] = other.merge(this.change);
      return [right, left];
    }

    if (other instanceof Replace) {
      const before = other.before.apply(this);
      return [new Replace(before, other.after), null];
    }
    throw new Error("unexpected PathChange.reverseMerge");
  }

  /**
   * Merge another change and return modified version of
   * the other and current change.
   *
   * current + returned[0] and other + returned[1] are guaranteed
   * to result in the same state.
   *
   * @returns {Change[]}
   */
  merge(other) {
    if (other == null) {
      return [null, this];
    }

    if (this.change == null) {
      return [other, null];
    }

    if (this.path == null) {
      return this.change.merge(other);
    }

    if (!(other instanceof PathChange)) {
      other = new PathChange(null, other);
    }

    const len = PathChange.commonPrefixLen(this.path, other.path);
    const ownLen = (this.path && this.path.length) || 0;
    const otherLen = (other.path && other.path.length) || 0;

    if (len != ownLen && len != otherLen) {
      return [other, this];
    }

    if (len == ownLen && len == otherLen) {
      const [left, right] = this.change.merge(other.change);
      return [
        PathChange.create(other.path, left),
        PathChange.create(this.path, right)
      ];
    }

    if (len == ownLen) {
      const [left, right] = this.change.merge(
        PathChange.create(other.path.slice(len), other.change)
      );
      return [
        PathChange.create(this.path, left),
        PathChange.create(this.path, right)
      ];
    }

    const [left, right] = other.merge(this);
    return [right, left];
  }

  applyTo(value) {
    if (this.path === null || this.path.length === 0) {
      return value.apply(this.change);
    }
    throw new Error("Unexpected use of PathChange.applyTo");
  }

  toJSON() {
    const path = Encoder.encodeArrayValue(this.path);
    return [path, Encoder.encode(this.change)];
  }

  static typeName() {
    return "changes.PathChange";
  }

  static fromJSON(decoder, json) {
    let path = json[0];

    if (path !== null) {
      path = path.map(x => decoder.decode(x));
    }

    const change = decoder.decodeChange(json[1]);
    return new PathChange(path, change);
  }

  static commonPrefixLen(p1, p2) {
    if (p1 == null || p2 == null) {
      return 0;
    }
    let len = 0;
    for (; len < p1.length && len < p2.length; len++) {
      const encode = x => Encoder.encode(x);
      if (JSON.stringify(encode(p1[len])) != JSON.stringify(encode(p2[len]))) {
        return len;
      }
    }
    return len;
  }

  static create(path, change) {
    if (path == null || path.length == 0) {
      return change;
    }
    if (change == null) {
      return null;
    }
    if (change instanceof PathChange) {
      const otherPath = change.path || [];
      return this.create(path.concat(otherPath), change.change);
    }
    return new PathChange(path, change);
  }
}











/**
 * Splice represents the change to replace a sub-sequence with another.
 * It can be used with strings or array-like values.
 */
class Splice {
  /**
   * @param {Number} offset -- where the sub-sequence starts.
   * @param {Value} before -- the subsequnce as it was before.
   * @param {Value} value - the subsequence as it is after.
   */
  constructor(offset, before, after) {
    this.offset = offset;
    this.before = before;
    this.after = after;
  }

  revert() {
    return new Splice(this.offset, this.after, this.before);
  }

  reverseMerge(other) {
    if (other == null) {
      return [null, this];
    }
    if (other instanceof Replace) {
      return this._mergeReplace(other);
    }

    if (other instanceof Splice) {
      const [left, right] = other._mergeSplice(this);
      return [right, left];
    }

    if (other instanceof PathChange) {
      return this._mergePath(other, true);
    }

    const [self, otherx] = other.reverseMerge(this);
    return [otherx, self];
  }

  merge(other) {
    if (other == null) {
      return [null, this];
    }

    if (other instanceof Replace) {
      return this._mergeReplace(other);
    }

    if (other instanceof Splice) {
      return this._mergeSplice(other);
    }

    if (other instanceof PathChange) {
      return this._mergePath(other, false);
    }
    const [left, right] = other.reverseMerge(this);
    return [right, left];
  }

  _mergePath(o, reverse) {
    if (o.path == null || o.path.length === 0) {
      if (reverse) {
        return this.reverseMerge(o.change);
      }
      return this.merge(o.change);
    }

    const newPath = this.mapPath(o.path);
    if (newPath == null) {
      const p = [o.path[0] - this.offset].concat(o.path.slice(1));
      const before = this.before.apply(new PathChange(p, o.change));
      return [null, new Splice(this.offset, before, this.after)];
    }
    return [new PathChange(newPath, o.change), this];
  }

  mapPath(path) {
    const idx = path[0];
    if (idx < this.offset) {
      return path;
    }

    if (idx >= this.offset + this.before.length) {
      const idx2 = idx + this.after.length - this.before.length;
      return [idx2].concat(path.slice(1));
    }

    // path obliterated
    return null;
  }

  _mergeSplice(o) {
    if (Splice._end(this) <= o.offset) {
      // [ ] < >
      const offset = o.offset + Splice._diff(this);
      const other = new Splice(offset, o.before, o.after);
      return [other, this];
    }

    if (Splice._end(o) <= this.offset) {
      // < > [ ]
      const offset = this.offset + Splice._diff(o);
      const updated = new Splice(offset, this.before, this.after);
      return [o, updated];
    }

    if (this.offset < o.offset && Splice._end(this) < Splice._end(o)) {
      // [ < ] >
      const oOffset = this.offset + this.after.length;
      const end = Splice._end(this);
      const oBefore = o.before.slice(end - o.offset, o.before.length);
      const before = this.before.slice(0, o.offset - this.offset);
      return [
        new Splice(oOffset, oBefore, o.after),
        new Splice(this.offset, before, this.after)
      ];
    }

    if (this.offset == o.offset && this.before.length < o.before.length) {
      // <[ ] >
      const oBefore = o.before.slice(this.before.length, o.before.length);
      const oOffset = o.offset + this.after.length;
      const other = new Splice(oOffset, oBefore, o.after);

      return [
        other,
        new Splice(this.offset, this.before.slice(0, 0), this.after)
      ];
      // golang behavior is below
      // const oBefore = o.before.apply(new Splice(0, this.before, this.after));
      // return [new Splice(o.offset, oBefore, o.after), null];
    }

    if (this.offset <= o.offset && Splice._end(this) >= Splice._end(o)) {
      // [ < > ]
      const diff = o.offset - this.offset;
      const slice = this.before.slice(diff, diff + o.before.length);
      const before = this.before.apply(new Splice(diff, slice, o.after));
      return [null, new Splice(this.offset, before, this.after)];
    }

    if (this.offset > o.offset && Splice._end(this) <= Splice._end(o)) {
      // < [ ]>
      const diff = this.offset - o.offset;
      const slice = o.before.slice(diff, diff + this.before.length);
      const oBefore = o.before.apply(
        new Splice(this.offset - o.offset, slice, this.after)
      );
      return [new Splice(o.offset, oBefore, o.after), null];
    }

    // < [ > ]
    const oBefore = o.before.slice(0, this.offset - o.offset);
    const offset = o.offset + o.after.length;
    const before = this.before.slice(
      Splice._end(o) - this.offset,
      this.before.length
    );
    return [
      new Splice(o.offset, oBefore, o.after),
      new Splice(offset, before, this.after)
    ];
  }

  _mergeReplace(other) {
    const after = other.before.apply(this);
    return [new Replace(after, other.after), null];
  }

  toJSON() {
    return [
      this.offset,
      Encoder.encode(this.before),
      Encoder.encode(this.after)
    ];
  }

  static typeName() {
    return "changes.Splice";
  }

  static fromJSON(decoder, json) {
    const before = decoder.decodeValue(json[1]);
    const after = decoder.decodeValue(json[2]);
    return new Splice(json[0], before, after);
  }

  static _end(s) {
    return s.offset + s.before.length;
  }

  static _diff(s) {
    return s.after.length - s.before.length;
  }
}

Decoder.registerChangeClass(Splice);












/**
 * Move represents shifting a sub-sequence over to a different spot.
 * It can be used with strings or array-like values.
 */
class Move {
  /**
   * Example: new Move(1, 2, -1) represents removing the slice
   * value.slice(1, 3) and re-inserting it at index 0.
   *
   * @param {Number} offset - index of first element to shift.
   * @param {Number} count - number of elements to shift.
   * @param {Number} distance - how many elements to skip over.
   *
   */
  constructor(offset, count, distance) {
    this.offset = offset;
    this.count = count;
    this.distance = distance;
  }

  /** @returns {Move} - the inverse of the move */
  revert() {
    return new Move(this.offset + this.distance, this.count, -this.distance);
  }

  reverseMerge(c) {
    if (!c) {
      return [null, this];
    }

    if (c instanceof Replace) {
      return this._mergeReplace(c);
    }

    if (c instanceof PathChange) {
      return this._mergePath(c, true);
    }

    if (c instanceof Splice) {
      return this._mergeSplice(c);
    }

    const [left, right] = c.merge(this);
    return [right, left];
  }

  /**
   * Merge another change and return modified version of
   * the other and current change.
   *
   * current + returned[0] and other + returned[1] are guaranteed
   * to result in the same state.
   *
   * @returns {Change[]}
   */
  merge(c) {
    if (!c) {
      return [null, this];
    }

    if (c instanceof Replace) {
      return this._mergeReplace(c);
    }

    if (c instanceof PathChange) {
      return this._mergePath(c, false);
    }

    if (c instanceof Splice) {
      return this._mergeSplice(c);
    }

    if (c instanceof Move) {
      return this._mergeMove(c);
    }

    const [self, cx] = c.reverseMerge(this);
    return [cx, self];
  }

  _mergeReplace(other) {
    const after = other.before.apply(this);
    return [new Replace(after, other.after), null];
  }

  _mergePath(o, reverse) {
    if (o.path == null || o.path.length === 0) {
      if (reverse) {
        return this.reverseMerge(o.change);
      }
      return this.merge(o.change);
    }

    const newPath = this.mapPath(o.path);
    return [new PathChange(newPath, o.change), this];
  }

  _mergeMove(o) {
    if (
      o.offset === this.offset &&
      o.distance === this.distance &&
      o.count === this.count
    ) {
      return [null, null];
    }

    if (
      this.distance === 0 ||
      this.count === 0 ||
      o.distance === 0 ||
      o.count === 0
    ) {
      return [o, this];
    }

    if (
      this.offset >= o.offset + o.count ||
      o.offset >= this.offset + this.count
    ) {
      return this._mergeMoveNoOverlap(o);
    }

    if (
      this.offset <= o.offset &&
      this.offset + this.count >= o.offset + o.count
    ) {
      return this._mergeMoveContained(o);
    }

    if (
      this.offset >= o.offset &&
      this.offset + this.count <= o.offset + o.count
    ) {
      return this.reverseMerge(o);
    }

    if (this.offset < o.offset) {
      return this._mergeMoveRightOverlap(o);
    }

    return this.reverseMerge(o);
  }

  _mergeMoveNoOverlap(o) {
    const dest = this._dest();
    const odest = o._dest();

    if (!this._contains(odest) && !o._contains(dest)) {
      return this._mergeMoveNoOverlapNoDestMixups(o);
    }

    if (this._contains(odest) && o._contains(dest)) {
      return this._mergeMoveNoOverlapMixedDests(o);
    }

    if (o._contains(dest)) {
      return this.reverseMerge(o);
    }

    return this._mergeMoveNoOverlapContainedDest(o);
  }

  _mergeMoveNoOverlapContainedDest(o) {
    const dest = this._dest();
    let odest = o._dest();

    let destx = dest;
    if (dest >= odest && dest <= o.offset) {
      destx += o.count;
    } else if (dest > o.offset && dest <= odest) {
      destx -= o.count;
    }

    const m1 = new Move(this.offset, this.count + o.count, this.distance);
    if (o.offset <= this.offset) {
      m1.offset -= o.count;
    }
    if (destx <= m1.offset) {
      m1.distance = destx - m1.offset;
    } else {
      m1.distance = destx - m1.offset - m1.count;
    }

    const o1 = new Move(o.offset, o.count, o.distance);
    if (o.offset > this.offset && o.offset < dest) {
      o1.offset -= this.count;
    } else if (o.offset >= dest && o.offset < this.offset) {
      o1.offset += this.count;
    }

    odest += this.distance;
    if (odest <= o1.offset) {
      o1.distance = odest - o1.offset;
    } else {
      o1.distance = odest - o1.offset - o1.count;
    }

    return [o1, m1];
  }

  _mergeMoveNoOverlapNoDestMixups(o) {
    const dest = this._dest();
    const odest = o._dest();

    const o1dest =
      odest == dest ? this.offset + this.distance : this._mapPoint(odest);
    const o1 = Move._withDest(this._mapPoint(o.offset), o.count, o1dest);

    const m1dest = o._mapPoint(dest);
    const m1 = Move._withDest(o._mapPoint(this.offset), this.count, m1dest);

    return [o1, m1];
  }

  _mergeMoveNoOverlapMixedDests(o) {
    const dest = this._dest();
    const odest = o._dest();

    const lcount = dest - o.offset;
    const rcount = o.count - lcount;

    const loffset = this.offset + this.distance - lcount;
    const roffset = this.offset + this.distance + this.count;

    const ldistance = odest - this.offset;
    const rdistance = odest - this.offset - this.count;
    const ox = new Changes(
      new Move(loffset, lcount, ldistance),
      new Move(roffset, rcount, rdistance)
    );

    let distance = o.offset - this.offset - this.count;
    if (distance < 0) {
      distance = -(this.offset - o.offset - o.count);
    }
    const offset = o.offset + o.distance - (odest - this.offset);
    const count = this.count + o.count;

    return [ox, new Move(offset, count, distance)];
  }

  _mergeMoveRightOverlap(o) {
    const overlapSize = this.offset + this.count - o.offset;
    const overlapUndo = new Move(o.offset + o.distance, overlapSize, 0);
    const non = new Move(o.offset + overlapSize, o.count - overlapSize, 0);

    if (o.distance > 0) {
      overlapUndo.distance = -o.distance;
      non.distance = o.distance;
    } else {
      overlapUndo.distance = o.count - overlapSize - o.distance;
      non.distance = o.distance - overlapSize;
    }

    const [l, r] = this._mergeMoveNoOverlap(non);
    return [l, new Changes(overlapUndo, r)];
  }

  _mergeMoveContained(o) {
    const odest = o._dest();
    let ox = new Move(o.offset + this.distance, o.count, o.distance);

    if (this.offset <= odest && odest <= this.offset + this.count) {
      return [ox, this];
    }

    if (odest == this._dest()) {
      ox = Move._withDest(ox.offset, ox.count, this.offset + this.distance);
      let offset = this.offset;
      if (o.distance < 0) {
        offset += o.count;
      }
      const distance = o.offset + o.count + o.distance;
      return [ox, Move._withDest(offset, this.count - o.count, distance)];
    }

    ox = Move._withDest(ox.offset, ox.count, this._mapPoint(odest));
    const offset = o._mapPoint(this.offset);
    const distance = o._mapPoint(this._dest());
    return [ox, Move._withDest(offset, this.count - o.count, distance)];
  }

  _mapPoint(idx) {
    if (idx >= this.offset + this.distance && idx <= this.offset) {
      return idx + this.count;
    }

    if (
      idx >= this.offset + this.count &&
      idx < this.offset + this.count + this.distance
    ) {
      return idx - this.count;
    }
    return idx;
  }

  _dest() {
    if (this.distance < 0) {
      return this.offset + this.distance;
    }
    return this.offset + this.distance + this.count;
  }

  _contains(p) {
    return p > this.offset && p < this.offset + this.count;
  }

  _mergeSplice(o) {
    if (
      this.offset >= o.offset &&
      this.offset + this.count <= o.offset + o.before.length
    ) {
      return this._mergeMoveWithinSpliceBefore(o);
    }

    if (
      this.offset <= o.offset &&
      this.offset + this.count >= o.offset + o.before.length
    ) {
      // splice is fully within move sub-sequence
      const ox = new Splice(o.offset + this.distance, o.before, o.after);
      const thisx = new Move(
        this.offset,
        this.count + o.after.length - o.before.length,
        this.distance
      );
      return [ox, thisx];
    }

    if (
      this.offset >= o.offset + o.before.length ||
      o.offset >= this.offset + this.count
    ) {
      return this._mergeMoveOutsideSpliceBefore(o);
    }

    // first undo the intersection and then merge as before
    const rest = new Move(this.offset, this.count, this.distance);
    const undo = new Move(this.offset + this.distance, 0, 0);

    if (this.offset > o.offset) {
      const left = o.offset + o.before.length - this.offset;
      rest.offset += left;
      rest.count -= left;
      undo.count = left;
      if (this.distance < 0) {
        rest.distance -= left;
        undo.distance = this.count - this.distance - left;
      } else {
        undo.distance = -this.distance;
      }
    } else {
      const right = this.offset + this.count - o.offset;
      rest.count -= right;
      undo.count = right;
      undo.offset += rest.count;
      if (this.distance < 0) {
        undo.distance = -this.distance;
      } else {
        rest.distance += right;
        undo.distance = right - this.distance - this.count;
      }
    }

    // distance seems to become -0 in some cases which causes
    // tests to fail
    undo.distance = undo.distance || 0;
    rest.distance = rest.distance || 0;

    const [ox, restx] = rest._mergeMoveOutsideSpliceBefore(o);
    return [new Changes(undo, ox), restx];
  }

  _mergeMoveOutsideSpliceBefore(o) {
    const diff = o.after.length - o.before.length;
    const dest =
      this.distance < 0
        ? this.offset + this.distance
        : this.offset + this.distance + this.count;

    if (dest > o.offset && dest < o.offset + o.before.length) {
      const right = o.offset + o.before.length - dest;
      const oBefore1 = o.before.slice(0, dest - o.offset);
      const oBefore2 = o.before.slice(dest - o.offset, dest - o.offset + right);
      const empty = o.before.slice(0, 0);
      const splice1 = new Splice(o.offset, oBefore1, o.after);
      const splice2 = new Splice(
        this.offset + this.count + this.distance,
        oBefore2,
        empty
      );

      const move = new Move(this.offset, this.count, this.distance);

      if (this.offset < o.offset) {
        splice1.offset -= this.count;
        move.distance += right + diff;
      } else {
        move.distance += right;
        move.offset += diff;
      }
      return [new Changes([splice2, splice1]), move];
    }

    if (dest <= o.offset) {
      if (this.offset > o.offset) {
        const s = new Splice(o.offset + this.count, o.before, o.after);
        const m = new Move(
          this.offset + diff,
          this.count,
          this.distance - diff
        );
        return [s, m];
      }
    } else if (dest >= o.offset + o.before.length) {
      if (this.offset > o.offset) {
        const m = new Move(this.offset + diff, this.count, this.distance);
        return [o, m];
      }
      const s = new Splice(o.offset - this.count, o.before, o.after);
      const m = new Move(this.offset, this.count, this.distance + diff);
      return [s, m];
    }

    return [o, this];
  }

  _mergeMoveWithinSpliceBefore(o) {
    const dest =
      this.distance > 0
        ? this.offset + this.count + this.distance
        : this.offset + this.distance;

    if (dest >= o.offset && dest <= o.offset + o.before.length) {
      const oBefore = o.before.apply(
        new Move(this.offset - o.offset, this.count, this.distance)
      );
      return [new Splice(o.offset, oBefore, o.after), null];
    }

    const empty = o.before.slice(0, 0);
    const slice = o.before.slice(
      this.offset - o.offset,
      this.offset - o.offset + this.count
    );
    const spliced = o.before.apply(
      new Splice(this.offset - o.offset, slice, empty)
    );

    if (this.distance < 0) {
      const other = new Splice(dest, empty, slice);
      const self = new Splice(o.offset + this.count, spliced, o.after);
      return [self, other];
    }

    const other = new Splice(
      dest + o.after.length - o.before.length,
      empty,
      slice
    );
    const self = new Splice(o.offset, spliced, o.after);
    return [self, other];
  }

  mapPath(path) {
    const idx = path[0];
    if (idx >= this.offset && idx < this.offset + this.count) {
      return [idx + this.distance].concat(path.slice(1));
    }

    if (this.distance > 0) {
      const e = this.offset + this.count + this.distance;
      if (idx >= this.offset + this.count && idx < e) {
        return [idx - this.count].concat(path.slice(1));
      }
    } else if (idx >= this.offset + this.distance && idx < this.offset) {
      return [idx + this.count].concat(path.slice(1));
    }

    return path;
  }

  toJSON() {
    return [this.offset, this.count, this.distance];
  }

  static typeName() {
    return "changes.Move";
  }

  static fromJSON(decoder, json) {
    return new Move(json[0], json[1], json[2]);
  }

  static _withDest(offset, count, dest) {
    let distance = dest - offset - count;
    if (distance < 0) {
      distance = dest - offset;
    }
    return new Move(offset, count, distance);
  }
}

Decoder.registerChangeClass(Move);













/* Substream refers to a field embedded within a container stream */
class Substream extends DerivedStream {
  constructor(parent, key) {
    super(parent);
    this.key = key;
  }

  append(c) {
    const cx = new PathChange([this.key], c);
    return this._nextf(this.parent && this.parent.append(cx));
  }

  reverseAppend(c) {
    const cx = new PathChange([this.key], c);
    return this._nextf(this.parent && this.parent.reverseAppend(cx));
  }

  _nextf(n) {
    if (!n) {
      return null;
    }

    const { xform, key, ok } = transform(n.change, this.key);
    if (!ok) {
      // TODO: this should not be null for append case?
      return null;
    }

    return { change: xform, version: new Substream(n.version, key) };
  }

  _getNext() {
    return this._nextf(this.parent && this.parent.next);
  }
}

function transform(c, key) {
  if (c === null) {
    return { xform: c, key, ok: true };
  }

  if (c instanceof Replace) {
    return { xform: null, key, ok: false };
  }

  if (c instanceof Splice || c instanceof Move) {
    const path = c.mapPath([key]);
    if (path == null) {
      return { xform: null, key, ok: false };
    }
    return { xform: null, key: path[0], ok: true };
  }

  if (c instanceof PathChange) {
    if ((c.path || []).length == 0) {
      return transform(c.change, key);
    }

    const len = PathChange.commonPrefixLen([key], c.path);
    if (len == 0) {
      return { xform: null, key, ok: true };
    }

    const xform = PathChange.create(c.path.slice(1), c.change);
    return { xform, key, ok: true };
  }

  if (c instanceof Changes) {
    const result = [];
    for (let cx of c) {
      const { xform, key: k2, ok } = transform(cx, key);
      if (!ok) {
        return { xform, key, ok };
      }
      key = k2;
      if (xform) {
        result.push(xform);
      }
    }
    const xform = Changes.create(result);
    return { xform, key, ok: true };
  }

  throw new Error("unknown change type: " + c.constructor.name);
}









/** Null represents an empty value */
class Null extends Value {
  /** clone makes a copy but with stream set to null */
  clone() {
    return new Null();
  }

  toJSON() {
    return [];
  }

  static typeName() {
    return "changes.empty";
  }

  static fromJSON() {
    return new Null();
  }
}

Decoder.registerValueClass(Null);






/** MapIterator is implemented by map-like values and yield key-value pairs */
const MapIterator = Symbol("MapIterator");

/** SeqIterator is implemented by seq-like values and yield just values */
const SeqIterator = Symbol("SeqIterator");

/** isMapLike returns if object implements the MapIterator **/
function isMapLike(obj) {
  return Boolean(obj && obj[MapIterator]);
}















/** Dict represents a map/hash/dictionary/collection with string keys */
class Dict extends Value {
  constructor(initial, defaultFn) {
    super();
    this.map = initial || {};
    this._defaultFn = defaultFn || (() => new Null());
  }

  setDefaultFn(defaultFn) {
    this._defaultFn = defaultFn || (() => new Null());
  }

  /** get looks up a key and returns the value (or a default value) */
  get(key) {
    const s = new Substream(this.stream, key);
    return (this.map[key] || this._defaultFn()).clone().setStream(s);
  }

  /** check if key exists */
  keyExists(key) {
    return !!this.map[key];
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new this.constructor(this.map, this._defaultFn);
  }

  apply(c) {
    if (!c) {
      return this.clone();
    }

    if (c instanceof Replace) {
      return c.after;
    }

    if (c instanceof PathChange) {
      if (c.path === null || c.path.length === 0) {
        return this.apply(c.change);
      }
      return this._applyPath(c.path, c.change);
    }

    return c.applyTo(this);
  }

  _applyPath(path, c) {
    let val = this.map[path[0]] || this._defaultFn();
    val = val.apply(new PathChange(path.slice(1), c));
    const clone = {};
    for (let key in this.map) {
      clone[key] = this.map[key];
    }
    if (val instanceof Null) {
      delete clone[path[0]];
    } else {
      clone[path[0]] = val;
    }
    return new this.constructor(clone, this._defaultFn);
  }

  *[MapIterator]() {
    for (let key in this.map) {
      yield [key, this.get(key)];
    }
  }

  toJSON() {
    let all = [];
    for (let key in this.map) {
      all.push(key, Encoder.encode(this.map[key]));
    }
    return all;
  }

  static typeName() {
    return "dotdb.Dict";
  }

  static fromJSON(decoder, json) {
    json = json || [];
    const map = {};
    for (let kk = 0; kk < json.length; kk += 2) {
      map[json[kk]] = decoder.decodeValue(json[kk + 1]);
    }
    return new this(map);
  }
}

Decoder.registerValueClass(Dict);














/** extend creates an object which has all the keys of both args */

function extend(store, obj1, obj2) {
  return new ExtendStream(obj1, obj2).value;
}

class ExtendStream extends DerivedStream {
  constructor(obj1, obj2) {
    super(obj1.stream);
    this.obj1 = obj1;
    this.obj2 = obj2;
  }

  append(c) {
    return this._append(c, false);
  }

  reverseAppend(c) {
    return this._append(c, true);
  }

  _append(c, reverse) {
    const c1 = [];
    const c2 = [];

    this._proxyChange(c, c1, c2, {});
    if (c1.length + c2.length === 0) {
      return this;
    }

    const append = (s, c) => s && (reverse ? s.reverseAppend(c) : s.append(c));
    const s1 = append(this.obj1.stream, Changes.create(c1));
    const s2 = append(this.obj2.stream, Changes.create(c2));
    const obj1 = this.obj1
      .apply(Changes.create(c1))
      .clone()
      .setStream(s1);
    const obj2 = this.obj2
      .apply(Changes.create(c2))
      .clone()
      .setStream(s2);
    return {change: c, version: new ExtendStream(obj1, obj2)};
  }

  get value() {
    if (!isMapLike(this.obj1) && !isMapLike(this.obj2)) {
      return new Null().setStream(this);
    }

    const result = {};
    if (isMapLike(this.obj1)) {
      for (let [key, val] of this.obj1[MapIterator]()) {
        result[key] = val;
      }
    }

    if (isMapLike(this.obj2)) {
      for (let [key, val] of this.obj2[MapIterator]()) {
        result[key] = val;
      }
    }
    return new Dict(result).setStream(this);
  }

  _getNext() {
    const next1 = this.obj1.next;
    const next2 = this.obj2.next;

    if (!next1 && !next2) {
      return null;
    }

    const obj1 = next1 ? next1.version : this.obj1;
    const obj2 = next2 ? next2.version : this.obj2;
    const version = new ExtendStream(obj1, obj2);

    const changes = [];
    const redo =
      !isMapLike(this.obj1) ||
      !isMapLike(this.obj2) ||
      !isMapLike(obj1) ||
      !isMapLike(obj2) ||
      this._filterNext1(next1 && next1.change, changes) ||
      this._filterNext2(next2 && next2.change, obj1, changes);

    if (redo) {
      const change = new Replace(this.value.clone(), version.value.clone());
      return { change, version };
    }

    return { change: Changes.create(changes), version };
  }

  _filterNext1(c, changes) {
    if (!c) {
      return false;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        if (this._filterNext1(cx, changes)) return true;
      }
      return false;
    }

    if (!(c instanceof PathChange)) {
      return true;
    }

    if (!c.path || c.path.length === 0) {
      return this._filterNext1(c.change, changes);
    }

    if (!this.obj2.keyExists(c.path[0])) {
      changes.push(c);
    }

    return false;
  }

  _filterNext2(c, obj1, changes) {
    if (!c) {
      return false;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        if (this._filterNext2(cx, obj1, changes)) return true;
      }
      return false;
    }

    if (!(c instanceof PathChange)) {
      return true;
    }

    if (!c.path || c.path.length === 0) {
      return this._filterNext2(c.change, obj1, changes);
    }

    if (!obj1.keyExists(c.path[0])) {
      changes.push(c);
      return false;
    }

    const inner = [];
    const cx = PathChange.create(c.path.slice(1), c.change);
    if (this._filterOverride(cx, obj1, c.path[0], inner)) {
      return true;
    }
    if (inner.length) {
      changes.push(PathChange.create([c.path[0]], Changes.create(inner)));
    }

    return false;
  }

  _filterOverride(c, obj1, key, changes) {
    if (!c) {
      return false;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        if (this._filterOverride(cx, obj1, key, changes)) {
          return true;
        }
      }
      return false;
    }

    if (c instanceof Replace) {
      const before =
        c.before instanceof Null ? obj1.get(key).clone() : c.before;
      const after = c.after instanceof Null ? obj1.get(key).clone() : c.after;
      changes.push(new Replace(before, after));
      return false;
    }

    if (c instanceof PathChange) {
      if (!c.path || c.path.length === 0) {
        return this._filterOverride(c.change, obj1, key, changes);
      }
      changes.push(c);
      return false;
    }

    return true;
  }

  _proxyChange(c, c1, c2, removed) {
    if (!c) {
      return;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        this._proxyChange(cx, c1, c2, removed);
      }
    }

    if (!(c instanceof PathChange)) {
      throw new Error("cannot proxy change");
    }

    if (!c.path || c.path.length === 0) {
      return this._proxyChange(c.change, c1, c2, removed);
    }

    const cx = PathChange.create(c.path.slice(1), c.change);
    return this._proxyKeyChange(c.path[0], cx, c1, c2, removed);
  }

  _proxyKeyChange(key, inner, c1, c2, removed) {
    if (!inner) {
      return;
    }

    const exists1 =
      isMapLike(this.obj1) &&
      this.obj1.keyExists(key) &&
      !(removed[key] instanceof Null);
    const exists2 = isMapLike(this.obj2) && this.obj2.keyExists(key);

    if (!exists1) {
      c2.push(PathChange.create([key], inner));
      return;
    }

    const before = removed[key] || this.obj1.get(key).clone();

    if (exists1 && !exists2) {
      c1.push(PathChange.create([key], inner));
      removed[key] = before.apply(inner);
      return;
    }

    if (this._isDeletion(inner)) {
      c1.push(PathChange.create([key], new Replace(before, new Null())));
      removed[key] = new Null();
    }
    c2.push(PathChange.create([key], inner));
  }

  _isDeletion(c) {
    if (c instanceof Replace) {
      return c.after instanceof Null;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        if (this._isDeletion(cx)) {
          return true;
        }
      }
    }

    if (c instanceof PathChange) {
      if (!c.path || c.path.length === 0) {
        return this._isDeletion(c.change);
      }
    }

    return false;
  }
}












/** Text represents a string value */
class Text extends Value {
  constructor(text) {
    super();
    this.text = (text || "").toString();
  }

  slice(start, end) {
    return new Text(this.text.slice(start, end));
  }

  get length() {
    return this.text.length;
  }

  /**
   * splice splices a replacement string (or Text)
   *
   * @param {Number} offset - where the replacement starts
   * @param {Number} count - number of characters to remove
   * @param {Text|String} replacement - what to replace with
   *
   * @return {Text}
   */
  splice(offset, count, replacement) {
    if (!(replacement instanceof Text)) {
      replacement = new Text(replacement);
    }

    const before = this.slice(offset, offset + count);
    return this.appendChange(new Splice(offset, before, replacement)).version;
  }

  /**
   * move shifts the sub-sequence by the specified distance.
   * If distance is positive, the sub-sequence shifts over to the
   * right by as many characters as specified in distance. Negative
   * distance shifts left.
   *
   * @param {Number} offset - start of sub-sequence to shift
   * @param {Number} count - size of sub-sequence to shift
   * @param {Number} distance - distance to shift
   *
   * @return {Text}
   */
  move(offset, count, distance) {
    return this.appendChange(new Move(offset, count, distance)).version;
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new Text(this.text);
  }

  /**
   * Apply any change immutably.
   * @param {Change} c -- any change; can be null.
   * @returns {Value}
   */
  apply(c) {
    if (!c) {
      return this.clone();
    }

    if (c instanceof Replace) {
      return c.after;
    }

    if (c instanceof Splice) {
      const left = this.text.slice(0, c.offset);
      const right = this.text.slice(c.offset + c.before.length);
      return new Text(left + c.after.text + right);
    }

    if (c instanceof Move) {
      let { offset: o, distance: d, count: cx } = c;
      if (d < 0) {
        [o, cx, d] = [o + d, -d, cx];
      }

      const s1 = this.text.slice(0, o);
      const s2 = this.text.slice(o, o + cx);
      const s3 = this.text.slice(o + cx, o + cx + d);
      const s4 = this.text.slice(o + cx + d);
      return new Text(s1 + s3 + s2 + s4);
    }

    return c.applyTo(this);
  }

  toJSON() {
    return this.text;
  }

  static typeName() {
    return "dotdb.Text";
  }

  static fromJSON(decoder, json) {
    return new Text(json);
  }
}

Decoder.registerValueClass(Text);









/** run evaluates a runnable object, such as Ref */
function run(store, obj) {
  return new RunStream(store, obj, null).value;
}

class RunStream extends DerivedStream {
  constructor(store, obj, value) {
    if (!value) {
      value = obj;
      if (value.run) {
        value = run(store, value.run(store));
      }
    }

    super(value.stream);

    this.value = value.clone().setStream(this);
    this.store = store;
    this.obj = obj;
  }

  append(c) {
    return this._nextf(this.parent && this.parent.append(c));
  }

  reverseAppend(c) {
    return this._nextf(this.parent && this.parent.reverseAppend(c));
  }

  _nextf(n) {
    if (!n) {
      return null;
    }
    const val = this.value.apply(n.change).setStream(n.version);
    const version = new RunStream(this.store, this.obj, val);
    return {change: n.change, version};
  }

  _getNext() {
    const n = this.store.next;
    if (n) {
      this.store = n.version;
    }

    const objn = this.obj.next;
    if (objn) {
      // object definition has changed
      const updated = run(this.store, objn.version);
      const change = new Replace(this.value.clone(), updated.clone());
      return { change, version: updated.stream };
    }

    const valuen = this.parent && this.parent.next;
    if (valuen) {
      // evaluated value has changed
      const value = this.value.apply(valuen.change).setStream(valuen.version);
      const version = new RunStream(this.store, this.obj, value);
      return { change: valuen.change, version };
    }

    return null;
  }
}














function field(store, obj, key) {
  return new FieldStream(store, run(store, obj), run(store, key), null).value;
}

class FieldStream extends DerivedStream {
  constructor(store, obj, key, value) {
    if (!value) {
      if (!key.text) {
        value = new Null();
      } else if (obj.get) {
        value = obj.get(key.text);
      } else {
        value = new Null();
      }
    }

    super(value.stream);
    this.value = value.clone().setStream(this);
    this.store = store;
    this.obj = obj;
    this.key = key;
  }

  append(c) {
    return this._nextf(this.parent && this.parent.append(c));
  }

  reverseAppend(c) {
    return this._nextf(this.parent && this.parent.reverseAppend(c));
  }

  _nextf(n) {
    if (!n) {
      return null;
    }
    const v = this.value.apply(n.change).clone().setStream(n.version);
    const version = new FieldStream(this.store, this.obj, this.key, v);
    return {change: n.change, version};
  }

  _getNext() {
    const n = this.store.next;
    if (n) {
      this.store = n.version;
    }

    const objn = this.obj.next;
    const keyn = this.key.next;
    if (objn || keyn) {
      const obj = objn ? objn.version : this.obj;
      const key = keyn ? keyn.version : this.key;
      const updated = new FieldStream(this.store, obj, key, null).value;
      const change = new Replace(this.value.clone(), updated.clone());
      return { change, version: updated.stream };
    }

    return this._nextf(this.parent && this.parent.next);
  }
}


















/** invoke invokes a function reactively */
function invoke(store, fn, args) {
  return new InvokeStream(store, run(store, fn), run(store, args), null).value;
}

class InvokeStream extends DerivedStream {
  constructor(store, fn, args, value) {
    if (!value) {
      if (!fn.invoke) {
        value = new Null();
      } else {
        value = fn.invoke(store, args);
      }
    }

    super(value.stream);

    this.value = value.clone().setStream(this);
    this.store = store;
    this.fn = fn;
    this.args = args;
  }

  append(c) {
    return this._nextf(this.parent && this.parent.append(c));
  }

  reverseAppend(c) {
    return this._nextf(this.parent && this.parent.reverseAppend(c));
  }

  _nextf(n) {
    if (!n) {
      return null;
    }
    const val = this.value.apply(n.change).clone().setStream(n.version);
    const version = new InvokeStream(this.store, this.fn, this.args, val);
    return {change: n.change, version};
  }

  _getNext() {
    const n = this.store.next;
    if (n) {
      this.store = n.version;
    }

    const fnNext = this.fn.next;
    const argsNext = this.args.next;
    if (fnNext || argsNext) {
      const fn = fnNext ? fnNext.version : this.fn;
      const args = argsNext ? argsNext.version : this.args;
      const updated = new InvokeStream(this.store, fn, args, null).value;
      const change = new Replace(this.value.clone(), updated.clone());
      return { change, version: updated.stream };
    }

    const valuen = this.parent && this.parent.next;
    if (valuen) {
      // evaluated value has changed
      const value = this.value.apply(valuen.change);
      const version = new InvokeStream(
        this.store,
        this.fn,
        this.args,
        value.setStream(valuen.version)
      );
      return { change: valuen.change, version };
    }

    return null;
  }
}

/** View stores a calculation that invokes a stored fn and args */
class View extends Value {
  constructor(info) {
    super();
    this.info = info || new Null();
  }

  /** clone returns a copy with the stream set to null */
  clone() {
    return new View(this.info);
  }

  run(store) {
    return invoke(
      store,
      field(store, this.info, new Text("viewFn")),
      this.info
    );
  }

  apply(c) {
    if (!(c instanceof PathChange)) return super.apply(c);

    if (!c.path || c.path.length == 0) {
      return this.apply(c.change);
    }
    if (c.path[0] != "info") {
      throw new Error("unexpected field: " + c.path[0]);
    }
    const pc = new PathChange(c.path.slice(1), c.change);
    return new View(this.info.apply(pc));
  }

  get(key) {
    if (key != "info") {
      throw new Error("unexpected key: " + key);
    }
    return this.info.clone().setStream(new Substream(this.stream, "info"));
  }

  toJSON() {
    return Encoder.encode(this.info);
  }

  static typeName() {
    return "dotdb.View";
  }

  static fromJSON(decoder, json) {
    return new View(decoder.decode(json));
  }
}

Decoder.registerValueClass(View);
















/** map calls the provided fn on all keys of the object */
function map(store, obj, fn) {
  const f = (key, val) =>
    invoke(store, fn, toDict({ key: new Text(key), it: val }));
  return new MapStream(obj, f, null).value;
}

/** toDict takes a map where the values are streams and converts it to
 * a live dict */
function toDict(m) {
  return new MapStream(new Dict(m), null, m).value;
}

/** MapStream implement a mapped dictionary-like stream */
class MapStream extends DerivedStream {
  constructor(base, fn, value) {
    super(base.stream);
    this.base = base;
    this.fn = fn || ((k, v) => v);
    if (!value) {
      if (typeof this.base[MapIterator] !== "function") {
        value = null;
      } else {
        value = {};

        for (let [key, val] of this.base[MapIterator]()) {
          value[key] = this.fn(key, val);
        }
      }
    }
    this._value = value;
  }

  append(c) {
    return this._append(c, false);
  }

  reverseAppend(c) {
    return this._append(c, true);
  }

  _append(c, reverse) {
    // proxy any changes to a field over to this._value
    const updated = {};
    if (!this._appendChanges(c, updated, reverse)) {
      // TODO: this is not atomic!! updated could have
      // partially changed at this point. REDO this
      return null;
    }

    const value = Object.assign({}, this._value, updated);
    const version = new MapStream(this.base, this.fn, value);
    return {change: c, version};
  }

  get value() {
    if (!this._value) {
      return new Null().setStream(this);
    }

    const m = {};
    for (let key in this._value) {
      m[key] = this._value[key].clone();
    }
    return new Dict(m).setStream(this);
  }

  _getNext() {
    const basen = this.base.next;

    if (!this._value) {
      if (!basen) {
        return null;
      }
      const version = new MapStream(basen.version, this.fn, null);
      const change = new Replace(this.value.clone(), version.value.clone());
      return { change, version };
    }

    if (basen && typeof basen.version[MapIterator] !== "function") {
      const version = new MapStream(basen.version, this.fn, null);
      const change = new Replace(this.value.clone(), version.value.clone());
      return { change, version };
    }

    const updated = Object.assign({}, this._value);
    const changes = [];

    if (basen) {
      this._updateKeys(basen.version, basen.change, updated, changes);
    }

    for (let key in this._value) {
      if (!updated.hasOwnProperty(key)) continue;
      const val = this._value[key];
      const n = val.next;
      if (n) {
        changes.push(new PathChange([key], n.change));
        updated[key] = n.version;
      }
    }

    if (changes.length === 0) {
      return null;
    }

    const change = changes.length == 1 ? changes[0] : new Changes(changes);
    const version = new MapStream(
      basen ? basen.version : this.base,
      this.fn,
      updated
    );
    return { change, version };
  }

  _updateKeys(base, c, updated, changes) {
    if (!c) {
      return;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        this._updateKeys(base, cx, updated, changes);
      }
      return;
    }

    if (!(c instanceof PathChange)) {
      return;
    }

    if ((c.path || []).length == 0) {
      return this._updateKeys(base, c.change, updated, changes);
    }

    const key = c.path[0];
    const existed = updated.hasOwnProperty(key);
    const nowExists = !(base.get(key) instanceof Null);

    if (!existed && nowExists) {
      updated[key] = this.fn(key, base.get(key));
      const replace = new Replace(new Null(), updated[key].clone());
      changes.push(new PathChange([key], replace));
    } else if (existed && !nowExists) {
      const replace = new Replace(new Null(), updated[key].clone());
      delete updated[key];
      changes.push(new PathChange([key], replace.revert()));
    }
  }

  _appendChanges(c, updated, reverse) {
    if (c instanceof Changes) {
      let result = false;
      for (let cx of c) {
        result = result || this._appendChanges(cx, updated, reverse);
      }
      return result;
    }

    if (!(c instanceof PathChange)) {
      return false;
    }

    if (!c.path || c.path.length === 0) {
      return this._appendChanges(c.change, reverse);
    }

    const key = c.path[0];
    if (this._value.hasOwnProperty(key)) {
      const cx = PathChange.create(c.path.slice(1), c.change);
      const val = this._value[key];
      // TODO: ignores reverse flag!!! Fix
      updated[key] = val.appendChange(cx);
      console.log("updated", val, "to", updated[key])
      return true;
    }

    return false;
  }
}
















/** group calls the provided fn on all keys of the object and
 * aggregates all items with same value of fn. It returns a
 * dictionary where the keys are groups and the values are
 * dictionaries with that group value */

function group(store, obj, fn) {
  return new GroupStream(obj, map(store, obj, fn), null).value;
}

/** GroupStream implements a groupd dict-of-dict-like stream */
class GroupStream extends DerivedStream {
  constructor(base, groups, groupsMap) {
    super(base.stream);
    this.base = base;
    this.groups = groups;
    if (!groupsMap && isMapLike(base)) {
      groupsMap = {};
      for (let [key] of base[MapIterator]()) {
        groupsMap[key] = GroupStream._groupOf(key, groups);
      }
    }
    this.groupsMap = groupsMap;
  }

  append(c) {
    return this._append(c, false);
  }

  reverseAppend(c) {
    return this._append(c, true);
  }

  _append(c, reverse) {
    if (!c || !this.base.stream) {
      return this;
    }

    const groupsMap = Object.assign({}, this.groupsMap);
    c = this._proxyChange(c, groupsMap);
    const s = this.base.stream;
    return this._nextf(reverse ? s.reverseAppend(c) : s.append(c), groupsMap);
  }

  _nextf(n, groupsMap) {
    if(!n) {
      return null;
    }

    const base = this.base
      .apply(n.change)
      .clone()
      .setStream(n.version);
    const version = new GroupStream(base, this.groups, groupsMap);
    return {change: n.change, version};
  }

  get value() {
    if (!isMapLike(this.base)) {
      return new Null().setStream(this);
    }

    const value = {};
    for (let [key] of this.base[MapIterator]()) {
      const group = GroupStream._groupOf(key, this.groups);
      value[group] = value[group] || {};
      value[group][key] = this.base.get(key).clone();
    }
    for (let group in value) {
      value[group] = new Dict(value[group]);
    }

    return GroupStream._collection(value).setStream(this);
  }

  _getNext() {
    let groupsn = this.groups.next;
    let basen = this.base.next;

    const groups = groupsn ? groupsn.version : this.groups;
    const base = basen ? basen.version : this.base;

    if (!isMapLike(this.base) || !isMapLike(base)) {
      if (!groupsn && !basen) {
        return null;
      }

      const version = new GroupStream(base, groups, null);
      const change = new Replace(new Null(), version.value.clone());
      return { change, version };
    }

    const changes = [];
    const oldGroups = {};

    for (let [key, val] of this.base[MapIterator]()) {
      const before = this.groupsMap[key];
      oldGroups[before] = 0;

      const after = GroupStream._groupOf(key, groups);
      if (before !== after) {
        const r1 = new Replace(val.clone(), new Null());
        changes.push(new PathChange([before, key], r1));
        if (base.keyExists(key)) {
          const r2 = new Replace(new Null(), val.clone());
          changes.push(new PathChange([after, key], r2));
        }
      }
    }

    // delete empty groups
    for (let [key] of base[MapIterator]()) {
      oldGroups[GroupStream._groupOf(key, groups)] = 1;
    }
    for (let group in oldGroups) {
      if (!oldGroups[group]) {
        const r = new Replace(GroupStream._collection(null), new Null());
        changes.push(new PathChange([group], r));
      }
    }

    if (!this._groupChanges(base, basen && basen.change, groups, changes)) {
      // an unsupport change type.  replace whole object
      const version = new GroupStream(base, groups, null);
      const change = new Replace(this.value.clone(), version.value.clone());
      return { change, version };
    }

    if (!changes.length) {
      return null;
    }

    const change = new Changes(changes);
    const version = new GroupStream(base, groups, null);
    return { change, version };
  }

  _groupChanges(base, c, groups, changes) {
    if (!c) {
      return true;
    }

    if (c instanceof Changes) {
      for (let cx of c) {
        if (!this._groupChanges(base, cx, groups, changes)) {
          return false;
        }
      }
      return true;
    }

    if (!(c instanceof PathChange)) {
      return false;
    }

    if (!c.path || !c.path.length) {
      return this._groupChanges(base, c.change, groups, changes);
    }

    if (base.keyExists(c.path[0])) {
      const group = GroupStream._groupOf(c.path[0], groups);
      changes.push(PathChange.create([group].concat(c.path), c.change));
    }
    return true;
  }

  _proxyChange(c, groupsMap) {
    if (!c) {
      return null;
    }

    if (c instanceof Changes) {
      const changes = [];
      for (let cx of c) {
        cx = this._proxyChange(cx, groupsMap);
        if (cx) {
          changes.push(cx);
        }
      }
      return Changes.create(changes);
    }

    if (!(c instanceof PathChange)) {
      throw new Error("cannot proxy change");
    }

    if (!c.path || c.path.length === 0) {
      return this._proxyChange(c.change, groupsMap);
    }

    const group = c.path[0];
    const change = PathChange.create(c.path.slice(1), c.change);
    return this._proxyGroupChange(group, change, groupsMap);
  }

  _proxyGroupChange(group, c, groupsMap) {
    if (!c) {
      return null;
    }

    if (c instanceof Changes) {
      const changes = [];
      for (let cx of c) {
        cx = this._proxyGroupChange(group, cx, groupsMap);
        if (cx) {
          changes.push(cx);
        }
      }
      return Changes.create(changes);
    }

    if (c instanceof PathChange) {
      if (!c.path || !c.path.length) {
        return this._proxyGroupChange(group, c.change, groupsMap);
      }

      groupsMap[c.path[0]] = group;
      return c;
    }

    if (!(c instanceof Replace)) {
      throw new Error("unexpected change");
    }

    const changes = [];
    if (isMapLike(c.before)) {
      // delete old items
      for (let [key, before] of c.before[MapIterator]()) {
        const r = new Replace(before, new Null());
        changes.push(new PathChange([key], r));
      }
    }
    if (isMapLike(c.after)) {
      // insert new items
      for (let [key, after] of c.after[MapIterator]()) {
        const r = new Replace(new Null(), after);
        changes.push(new PathChange([key], r));
      }
    }
    return this._proxyGroupChange(group, new Changes(changes), groupsMap);
  }

  static _groupOf(key, groups) {
    if (!isMapLike(groups)) {
      return "";
    }
    return GroupStream.KeyString(groups.get(key));
  }

  static KeyString(val) {
    return JSON.stringify(Encoder.encode(val));
  }

  static _collection(m) {
    return new Dict(m, () => new Dict());
  }
}










/** filter calls the provided fn on all keys of the object and only retains keys for which the fn evalutes to true  */
function filter(store, obj, fn) {
  return field(store, group(store, obj, fn), new Text('{"dotdb.Bool":true}'));
}









/** Store is a dictionary where the
 * default value type is also a dictionary */
class Store extends Dict {
  constructor(map, defaultFn) {
    super(map, defaultFn || (() => new Dict()));
  }
  static typeName() {
    return "dotdb.Store";
  }
}

Decoder.registerValueClass(Store);
















/** Seq represents a sequence of values */
class Seq extends Value {
  constructor(entries) {
    super();
    this.entries = entries || [];
  }

  /**
   * splice splices a replacement sequence
   *
   * @param {Number} offset - where the replacement starts
   * @param {Number} count - number of items to remove
   * @param {Text|String} replacement - what to replace with
   *
   * @return {Text}
   */
  splice(offset, count, replacement) {
    const before = this.slice(offset, offset + count);
    return this.appendChange(new Splice(offset, before, replacement)).version;
  }

  /**
   * move shifts the sub-sequence by the specified distance.
   * If distance is positive, the sub-sequence shifts over to the
   * right by as many characters as specified in distance. Negative
   * distance shifts left.
   *
   * @param {Number} offset - start of sub-sequence to shift
   * @param {Number} count - size of sub-sequence to shift
   * @param {Number} distance - distance to shift
   *
   * @return {Text}
   */
  move(offset, count, distance) {
    return this.appendChange(new Move(offset, count, distance)).version;
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new Seq(this.entries);
  }

  slice(start, end) {
    return new Seq(this.entries.slice(start, end));
  }

  _concat(...args) {
    const entries = [];
    for (let arg of args) {
      entries.push(arg.entries);
    }
    return new Seq(this.entries.concat(...entries));
  }

  get length() {
    return this.entries.length;
  }

  get(idx) {
    return this.entries[idx].clone().setStream(new Substream(this.stream, idx));
  }

  _set(idx, val) {
    const slice = this.entries.slice(0);
    slice[idx] = val;
    return new Seq(slice);
  }

  apply(c) {
    return applySeq(this, c);
  }

  *[SeqIterator]() {
    for (let kk = 0; kk < this.entries.length; kk++) {
      yield this.get(kk);
    }
  }

  toJSON() {
    return Encoder.encodeArrayValue(this.entries);
  }

  static typeName() {
    return "dotdb.Seq";
  }

  static fromJSON(decoder, json) {
    return new Seq((json || []).map(x => decoder.decodeValue(x)));
  }
}

Decoder.registerValueClass(Seq);



function applySeq(obj, c) {
  if (c == null) {
    return obj.clone();
  }

  if (c instanceof Replace) {
    return c.after;
  }

  if (c instanceof PathChange) {
    if (c.path === null || c.path.length === 0) {
      return obj.apply(c.change);
    }
    const pc = new PathChange(c.path.slice(1), c.change);
    return obj._set(c.path[0], obj.get(c.path[0]).apply(pc));
  }

  if (c instanceof Splice) {
    const left = obj.slice(0, c.offset);
    const right = obj.slice(c.offset + c.before.length);
    return left._concat(c.after, right);
  }

  if (c instanceof Move) {
    let { offset: off, count, distance: dist } = c;
    if (dist < 0) {
      [off, count, dist] = [off + dist, -dist, count];
    }
    const l1 = obj.slice(0, off);
    const l2 = obj.slice(off, off + count);
    const l3 = obj.slice(off + count, off + count + dist);
    const l4 = obj.slice(off + count + dist);
    return l1._concat(l3, l2, l4);
  }

  return c.applyTo(obj);
}









/** Num represents a generic numeric type */
class Num extends Value {
  constructor(num) {
    super();
    this.n = parseFloat(+num);
    if (isNaN(this.n) || !isFinite(this.n)) {
      throw new Error("not a number: " + num);
    }
  }

  valueOf() {
    return this.n;
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new Num(this.n);
  }

  toJSON() {
    return this.n;
  }

  static typeName() {
    return "dotdb.Num";
  }

  static fromJSON(decoder, json) {
    return new Num(json);
  }
}

Decoder.registerValueClass(Num);












/** Ref represents a reference to a path */
class Ref extends Value {
  constructor(path) {
    super();
    this._path = path;
  }

  /** clone makes a copy but with stream set to null */
  clone() {
    return new Ref(this._path);
  }

  /** run returns the underlying value at the path */
  run(store) {
    let result = store;
    for (let elt of this._path) {
      result = field(store, result, new Text(elt));
    }
    return result;
  }

  toJSON() {
    return JSON.stringify(this._path);
  }

  static typeName() {
    return "dotdb.Ref";
  }

  static fromJSON(decoder, json) {
    return new Ref(JSON.parse(json));
  }
}

Decoder.registerValueClass(Ref);












/** Transformer wraps a {@link Conn} object, transforming all incoming ops */
class Transformer {
  /**
   * @param {Conn} conn -- the connection to wrap.
   * @param {Object} [cache] -- an optional ops cache.
   * @param {Object} cache.untransformed -- a map of version => raw operation.
   * @param {Object} cache.transformed - a map of version => transformed op.
   * @param {Object} cache.merge - a map of version to array of merge ops.
   */
  constructor(conn, cache) {
    this._c = conn;
    this._cache = cache || { untransformed: {}, transformed: {}, merge: {} };
  }

  /** write passes through to the underlying {@link Conn} */
  write(ops) {
    return this._c.write(ops);
  }

  /** read is the work horse, fetching ops from {@link Conn} and transforming it as needed */
  async read(version, limit, duration) {
    const transformed = this._cache.transformed[version];
    let ops = [];
    if (transformed) {
      for (let count = 0; count < limit; count++) {
        const op = this._cache.transformed[version + count];
        if (!op) break;
        ops.push(op);
      }
      return ops;
    }

    const raw = this._cache.untransformed[version];
    if (!raw) {
      ops = await this._c.read(version, limit, duration);
    } else {
      for (let count = 0; count < limit; count++) {
        const op = this._cache.untransformed[version + count];
        if (!op) break;
        ops.push(op);
      }
    }

    const result = [];
    for (let op of ops || []) {
      this._cache.untransformed[op.version] = op;
      const { xform } = await this._transformAndCache(op);
      result.push(xform);
    }
    return result;
  }

  async _transformAndCache(op) {
    if (!this._cache.transformed[op.version]) {
      const { xform, merge } = await this._transform(op);
      this._cache.transformed[op.version] = xform;
      this._cache.merge[op.version] = merge;
    }

    const xform = this._cache.transformed[op.version];
    const merge = this._cache.merge[op.version].slice(0);
    return { xform, merge };
  }

  async _transform(op) {
    const gap = op.version - op.basis - 1;
    if (gap === 0) {
      // no interleaved op, so no special transformation needed.
      return { xform: op, merge: [] };
    }

    // fetch all ops since basis
    const ops = await this.read(op.basis + 1, gap);

    let xform = op;
    let merge = [];

    if (op.parentId) {
      // skip all those before the parent if current op has parent
      while (!Transformer._equal(ops[0].id, op.parentId)) {
        ops.shift();
      }
      const parent = ops[0];
      ops.shift();

      // The current op is meant to be applied on top of the parent op.
      // The parent op has a merge chain which corresponds to the set of
      // operation were accepted by the server before the parent operation
      // but which were not known to the parent op.
      //
      // The current op may have factored in a few but those in the
      // merge chain that were not factored would contribute to its own
      // merge chain.
      ({ xform, merge } = await this._getMergeChain(op, parent));
    }

    // The transformed op needs to be merged against all ops that were
    // accepted by the server between the parent and the current op.
    for (let opx of ops) {
      let { xform: x } = await this._transformAndCache(opx);
      [xform, x] = Transformer._merge(x, xform);
      merge.push(x);
    }

    return { xform, merge };
  }

  // getMergeChain gets all operations in the merge chain of the parent
  // that hove not been factored into the current op.  The provided op
  // is transformed against this merge chain to form its own initial merge
  // chain.
  async _getMergeChain(op, parent) {
    const { merge } = await this._transformAndCache(parent);
    while (merge.length > 0 && merge[0].version <= op.basis) {
      merge.shift();
    }

    let xform = op;
    for (let kk = 0; kk < merge.length; kk++) {
      [xform, merge[kk]] = Transformer._merge(merge[kk], xform);
    }

    return { xform, merge };
  }

  static _merge(op1, op2) {
    let [c1, c2] = [op2.changes, op1.changes];
    if (op1.changes) {
      [c1, c2] = op1.changes.merge(op2.changes);
    }

    const op1x = new Operation(
      op2.id,
      op2.parentId,
      op2.version,
      op2.basis,
      c1
    );
    const op2x = new Operation(
      op1.id,
      op1.parentId,
      op1.version,
      op1.basis,
      c2
    );
    return [op1x, op2x];
  }

  static _equal(id1, id2) {
    // IDs can be any type, so to be safe JSON stringify it.
    return JSON.stringify(id1) == JSON.stringify(id2);
  }
}






/**
 * undoable creates an undo stream.
 *
 * All changes to the parent stream are tracked and calls to
 * undo() and redo() on the returned stream correspondingly
 * behaving like global undo/redo: i.e. they revert or reapply
 * the corresponding changes and behave like an undo stack in
 * an editor.
 *
 * This is resilient to interleaving upstream changes, appropriately
 * transforming the local change to preserve the intent of the
 * change.
 *
 * @param {Stream} s - parent stream
 * @returns {Stream}
 */
function undoable(s) {
  return new UndoStream(s, new UndoStack(s));
}

class UndoStream {
  constructor(parent, stack) {
    this.parent = parent;
    this.stack = stack;
  }

  get next() {
    const n = this.parent.next;
    if (!n) {
      return null;
    }

    return { change: n.change, version: new UndoStream(n.version, this.stack) };
  }

  append(c) {
    this.stack.flush();
    return this._append(this.parent && this.parent.append(c));
  }

  reverseAppend(c) {
    this.stack.flush();
    return this._append(this.parent && this.parent.reverseAppend(c));
  }

  _append(n) {
    if (!n) {
      return null;
    }
    this.stack.pickupLocalChanges();
    const version = new UndoStream(n.version, this.stack);
    return {change: n.change, version};
  }

  push() {
    return this.parent.push();
  }

  pull() {
    return this.parent.pull();
  }

  undo() {
    return this.stack.undo();
  }

  redo() {
    return this.stack.redo();
  }
}

class UndoStack {
  constructor(s) {
    this.undos = [];
    this.redos = [];
    this.stream = s;
  }

  flush() {
    for (let next = this.stream && this.stream.next; next; ) {
      this.stream = next.version;
      this.undos = UndoStack.merge(this.undos, next.change);
      this.redos = UndoStack.merge(this.redos, next.change);
      next = this.stream.next;
    }
  }

  pickupLocalChanges() {
    for (let next = this.stream && this.stream.next; next; ) {
      this.stream = next.version;
      const c = next.change;
      if (c) {
        this.undos.push(c.revert());
      }
      this.redos.length = 0;
      next = this.stream.next;
    }
  }

  undo() {
    this.flush();
    if (!this.undos.length) {
      return null;
    }
    const c = this.undos.shift();
    this.redos.unshift(c.revert());
    this.stream = this.stream.append(c).version;
    return c;
  }

  redo() {
    this.flush();
    if (!this.redos.length) {
      return null;
    }
    const c = this.redos.shift();
    this.undos.unshift(c.revert());
    this.stream = this.stream.append(c).version;
    return c;
  }

  static merge(changes, cx) {
    const result = [];
    let updated = null;
    for (let kk = 0; kk < changes.length; kk++) {
      if (!cx) {
        result.push(changes[kk]);
      } else {
        [updated, cx] = cx.merge(changes[kk]);
        if (updated) {
          result.push(updated);
        }
      }
    }
    return result;
  }
}















/** Session implements helpers for creating a session */
class Session {
  /** undoable wraps the object with a undo stack **/
  static undoable(obj) {
    return obj.clone().setStream(undoable(obj.stream));
  }

  /** Serialize serializes a connected value for later
   * use with connect */
  static serialize(obj) {
    const root = Encoder.encode(obj.latest());
    const stream = obj.stream;
    if (!stream || !(stream instanceof SessionStream)) {
      return { root, version: -1, merge: [], pending: [] };
    }

    stream._push();
    stream._pull();
    const result = {
      root: root,
      version: stream._info.version,
      merge: stream._info.merge,
      pending: stream._info.pending
    };
    return JSON.parse(JSON.stringify(result));
  }

  /** connect creates a root object that can sync against
   * the provided URL. If serialized is not provided, a Null
   * initial object is created. */
  static connect(url, serialized) {
    const conn = this._conn(url);
    const { root, version, merge, pending } = this._root(serialized);
    const parent = new Stream();
    const info = {
      conn: conn,
      stream: parent,
      version: version,
      pending: (pending || []).slice(0),
      merge: (merge || []).slice(0),
      pulling: null,
      pushing: null,
      unsent: (pending || []).slice(0),
      unmerged: []
    };
    return root.setStream(new SessionStream(parent, info));
  }

  static _root(serialized) {
    if (!serialized) {
      return { root: new Null(), version: -1 };
    }

    const d = new Decoder();
    const root = d.decodeValue(serialized.root);
    const { version } = serialized;
    const merge = serialized.merge.map(x => Operation.fromJSON(d, x));
    const pending = serialized.pending.map(x => Operation.fromJSON(d, x));

    return { root, version, merge, pending };
  }

  static _conn(url) {
    if (typeof url !== "string") {
      return url;
    }
    // eslint-disable-next-line
    const f = typeof fetch == "function" ? fetch : null;
    return new Transformer(new Conn(url, f));
  }
}



class SessionStream {
  constructor(parent, info) {
    this._parent = parent;
    this._info = info;
  }

  append(c) {
    return this._nextf(this._parent && this._parent.append(c))
  }

  reverseAppend(c) {
    return this._nextf(this._parent && this._parent.reverseAppend(c))
  }

  _nextf(n) {
    if (!n) {
      return null;
    }
    const version = new SessionStream(n.version, this._info)
    return { change: n.change, version};
  }

  undo() {
    return this._parent.undo();
  }

  redo() {
    return this._parent.redo();
  }

  get next() {
    return this._nextf(this._parent.next);
  }

  push() {
    this._push();
    const info = this._info;
    if (!info.pushing) {
      const ops = info.unsent.slice(0);
      if (ops.length === 0) {
        return Promise.resolve(null);
      }
      info.pushing = info.conn
        .write(ops)
        .then(() => {
          info.unsent = info.unsent.slice(ops.length);
        })
        .finally(() => {
          info.pushing = null;
        });
    }
    return info.pushing;
  }

  _push() {
    const s = this._info;
    const len = (s.pending || []).length;
    let pid = len > 0 ? s.pending[len - 1].id : null;
    for (let next = s.stream.next; next; next = next.version.next) {
      const op = new Operation(null, pid, -1, s.version, next.change);
      s.unsent.push(op);
      s.pending.push(op);
      s.stream = next.version;
      pid = op.id;
    }
  }

  pull() {
    this._pull();
    const info = this._info;
    if (!info.pulling) {
      const ver = info.version + 1;
      info.pulling = info.conn
        .read(ver, 1000)
        .then(ops => {
          info.unmerged = info.unmerged.concat(ops || []);
        })
        .finally(() => {
          info.pulling = null;
        });
    }
    return info.pulling;
  }

  _pull() {
    const s = this._info;

    // apply server operations
    for (let op of s.unmerged) {
      if (s.pending.length && s.pending[0].id == op.id) {
        // ack
        s.pending = s.pending.slice(1);
        s.merge = s.merge.slice(1);
      } else {
        for (let kk = 0; kk < s.merge.length; kk++) {
          [s.merge[kk], op] = op.merge(s.merge[kk]);
        }
        s.stream = s.stream.reverseAppend(op.changes).version;
      }
      s.version = op.version;
    }
  }
}














/** Reflect introspects values and returns meta properties */
class Reflect {
  /** Definition returns the definition of the value
   * Calling run(store, def(val)) will produce the value itself.
   * Definitions can be stored.
   */
  static definition(val) {
    const s = val.stream;
    if (s instanceof RunStream) {
      return Reflect.definition(s.obj);
    }
    if (s instanceof FieldStream) {
      return new View(
        new Dict({
          viewFn: new FieldFn(),
          obj: Reflect.definition(s.obj),
          key: Reflect.definition(s.key)
        })
      );
    }
    if (s instanceof InvokeStream) {
      // field(store, this.info, new Text("viewFn"))
      if (s.fn.stream instanceof FieldStream) {
        if (
          s.fn.stream.key instanceof Text &&
          s.fn.stream.key.text == "viewFn"
        ) {
          // this is actually an invoke stream of a View
          return new View(s.fn.stream.obj.clone());
        }
      }
      const fn = Reflect.definition(s.fn);
      const args = Reflect.definition(s.args);
      return new View(extend(args, new Dict({ viewFn: fn() })).clone());
    }

    return val.clone();
  }

  static get FieldFn() {
    return FieldFn;
  }
}

class FieldFn extends Value {
  invoke(store, args) {
    return field(store, args.get("obj"), args.get("key"));
  }

  clone() {
    return new FieldFn();
  }

  static typeName() {
    return "dotdb.FieldFn";
  }
}
Decoder.registerValueClass(FieldFn);

module.exports = {Store, Dict, Seq, Text, Num, Bool, Null, Ref, Field, Conn, Transformer, Stream, DerivedStream, MapIterator, SeqIterator, run, field, map, filter, group, extend}