JavaScript Object to Binary Serializer with key Index

roJson.js

const stringHash = require("string-hash");

// 型識別子
const typeToId = {
  object: 1 * 16,
  denseArray: 2 * 16,
  sparseArray: 3 * 16,
  string: 4 * 16,
  uint4: 5 * 16,
  number: 6 * 16,
  uint8: 6 * 16 + 1,
  int8: 6 * 16 + 2,
  uint16: 6 * 16 + 3,
  int16: 6 * 16 + 4,
  uint32: 6 * 16 + 5,
  int32: 6 * 16 + 6,
  // 以降はenumっぽいシリーズなので上位4bitは共用
  boolTrue: 15 * 16 + 0,
  boolFalse: 15 * 16 + 1,
  null: 15 * 16 + 2
}

// 型識別子逆引き
const idToType = Object.keys(typeToId).reduce((result, key) => {
  const id = typeToId[key];
  result[id] = key;
  return result;
}, {});

// 読み込み関数。numberだけ特殊なので用意しない
const typeToReadFunction = {
  [typeToId.object]: getObjectProxy,
  [typeToId.denseArray]: getArrayProxy,
  [typeToId.sparseArray]: getSparseArrayProxy,
  [typeToId.string]: getString,
  [typeToId.boolTrue]: () => { return true; },
  [typeToId.boolFalse]: () => { return false; },
  [typeToId.null]: () => { return null; },

}

const UINT4_MAX = 2 ** 4 - 1;
const UINT8_MAX = 2 ** 8 - 1;
const INT8_MAX = 2 ** 7 - 1;
const INT8_MIN = -(2 ** 7);
const UINT16_MAX = 2 ** 16 - 1;
const INT16_MAX = 2 ** 15 - 1;
const INT16_MIN = -(2 ** 15);
const UINT32_MAX = 2 ** 32 - 1;
const INT32_MAX = 2 ** 31 - 1;
const INT32_MIN = -(2 ** 31);
// numberの変換関数。戻り値は書き込んだbyte数
function setNumber(num, dataView, offset) {
  // 整数の場合
  if (Number.isInteger(num)) {
    // 正の整数
    if (num > 0) {
      if (num <= UINT4_MAX) {
        dataView.setUint8(offset, typeToId.uint4 + num);
        return 1;
      }
      if (num <= UINT8_MAX) {
        dataView.setUint8(offset, typeToId.uint8);
        dataView.setUint8(offset + 1, num);
        return 2;
      }
      if (num <= UINT16_MAX) {
        dataView.setUint8(offset, typeToId.uint16);
        dataView.setUint16(offset + 1, num);
        return 3;
      }
      if (num <= UINT32_MAX) {
        dataView.setUint8(offset, typeToId.uint32);
        dataView.setUint32(offset + 1, num);
        return 5;
      }
      // 負の整数
    } else {
      if (num >= INT8_MIN) {
        dataView.setUint8(offset, typeToId.uint8);
        dataView.setInt8(offset + 1, num);
        return 2;
      }
      if (num >= INT16_MIN) {
        dataView.setUint8(offset, typeToId.uint16);
        dataView.setInt16(offset + 1, num);
        return 3;
      }
      if (num >= INT32_MIN) {
        dataView.setUint8(offset, typeToId.uint32);
        dataView.setInt32(offset + 1, num);
        return 5;
      }
    }
  }
  // それ以外はFloat64で
  dataView.setUint8(offset, typeToId.number);
  dataView.setFloat64(offset + 1, num);
  return 9;
}

function getNumberFromDataView(dataView, initialOffset) {
  // typeを取得
  const type = dataView.getUint8(initialOffset);
  let offset = initialOffset + 1;

  switch (type) {
    case typeToId.uint8: {
      const num = dataView.getUint8(offset);
      return [num, 2];
    }
    case typeToId.uint16: {
      const num = dataView.getUint16(offset);
      return [num, 3];
    }
    case typeToId.uint32: {
      const num = dataView.getUint32(offset);
      return [num, 5];
    }
    case typeToId.int8: {
      const num = dataView.getInt8(offset);
      return [num, 2];
    }
    case typeToId.int16: {
      const num = dataView.getInt16(offset);
      return [num, 3];
    }
    case typeToId.int32: {
      const num = dataView.getInt32(offset);
      return [num, 5];
    }
    case typeToId.number: {
      const num = dataView.getFloat64(offset);
      return [num, 9];
    }
  }

  // それ以外はuint4とみなす。下位4bitが値
  const num = type - typeToId.uint4;
  return [num, 1]
}

function encode(json, { bufferClass, initialByte, additionByte } = { bufferClass: ArrayBuffer, initialByte: 128, additionByte: 128 }) {
  const buffer = {
    dataView: new DataView(new bufferClass(initialByte)),
    additionByte
  }
  const lastOffset = encodeSub(buffer, 0, json);
  console.log(`encode result length = ${lastOffset}`);
  return buffer.dataView.buffer;
}

function encodeSub(buffer, initialOffset, json) {
  let isSuccess = false;
  while (!isSuccess) {
    try {
      // null or undefined
      if (json == null) {
        return encodeNull(buffer, initialOffset, json);
      }
      else if (Array.isArray(json)) {
        // 疎配列はobjectと同じ方法でエンコードする
        // ちなみにJSON.stringifyは空要素をnullに置き換えてしまうので
        // 厳密にはJSONとは異なる仕様
        if (Object.keys(json).length < json.length) {
          return encodeSparseArray(buffer, initialOffset, json);
        }
        // 密配列
        else {
          return encodeArray(buffer, initialOffset, json);
        }
      }
      else {
        const jsonType = typeof json;
        if (jsonType === "object") {
          return encodeObject(buffer, initialOffset, json);
        }
        else if (jsonType === "number") {
          return encodeNumber(buffer, initialOffset, json);
        }
        else if (jsonType === "string") {
          return encodeString(buffer, initialOffset, json);
        }
        else if (jsonType === "boolean") {
          return encodeBoolean(buffer, initialOffset, json);
        }
      }
    } catch (e) {
      if (e instanceof RangeError) {
        const realBuffer = buffer.dataView.buffer;
        const currentLength = realBuffer.byteLength;
        const newBuffer = new realBuffer.constructor(currentLength + buffer.additionByte);
        const oldView = new Uint8Array(realBuffer);
        const newView = new Uint8Array(newBuffer);
        newView.set(oldView);
        buffer.dataView = new DataView(newBuffer);
      } else {
        throw e;
      }
    }
  }
}

// (密)配列
function encodeArray(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // 0byte目。typeを書き込む
  buffer.dataView.setUint8(offset, typeToId.denseArray);
  offset += 1;

  // 配列長
  const bytelen = setNumber(obj.length, buffer.dataView, offset);
  offset += bytelen;

  // 要素ごとにエンコードしてポイントする
  let pointer = offset + obj.length * 4;
  for (let i = 0; i < obj.length; i++) {
    buffer.dataView.setUint32(offset + i * 4, pointer);
    pointer += encodeSub(buffer, pointer, obj[i]);
  }

  // 最後の要素のvalueの書き終わった位置までがこの要素のサイズ
  return pointer - initialOffset;
}

// object
function encodeObject(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // 0byte目。typeを書き込む
  buffer.dataView.setUint8(offset, typeToId.object);
  offset += 1;

  // objectとsparseArrayの共通関数に任せる
  const valueLen = encodeKeyValueType(buffer, offset, obj);

  return offset + valueLen - initialOffset;
}

// 疎配列
function encodeSparseArray(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // 0byte目。typeを書き込む
  buffer.dataView.setUint8(offset, typeToId.sparseArray);
  offset += 1;

  // 配列長(!=keyの数)
  const byteLen = setNumber(obj.length, buffer.dataView, offset);
  offset += byteLen;

  // objectとsparseArrayの共通関数に任せる
  const valueLen = encodeKeyValueType(buffer, offset, obj);

  return offset + valueLen - initialOffset;
}

// objectとsparseArrayの共通関数
function encodeKeyValueType(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // hash表サイズを計算
  const keys = Object.keys(obj);
  const numberOfBucket = parseInt(keys.length * 1.2);
  const bucket = Array(numberOfBucket);
  for (let i = 0; i < numberOfBucket; i++) {
    bucket[i] = Array(0);
  }

  // hashを計算
  for (let k = 0; k < keys.length; k++) {
    const key = keys[k];
    const rowHash = stringHash(key);
    const hash = rowHash % numberOfBucket;
    bucket[hash].push({ o: k, k: key });
  }

  // 1byte～4byte目。ハッシュテーブルサイズを書き込む
  const byteLen = setNumber(numberOfBucket, buffer.dataView, offset);
  offset += byteLen;

  // 5byte目以降にハッシュ表を書き込む。key情報へのポインタを保持する
  let pointer = offset + numberOfBucket * 4;
  for (let h = 0; h < numberOfBucket; h++) {
    const bucketLen = bucket[h].length;

    // ハッシュ値に該当するキーがない場合は0
    if (bucketLen === 0) {
      buffer.dataView.setUint32(offset, 0);
    }
    // そうでない場合はpointerの値を書き込んで要素数分pointerを移動
    else {
      buffer.dataView.setUint32(offset, pointer);
      // pointerの指す先の情報を書き込む
      // hash値に該当するkeyの数
      const keyLenByteLen = setNumber(bucketLen, buffer.dataView, pointer);
      pointer += keyLenByteLen;
      // key毎の処理
      for (const keyval of bucket[h]) {
        // keyの順序index
        const keyIndexByteLen = setNumber(keyval.o, buffer.dataView, pointer);
        pointer += keyIndexByteLen;
        // key名長
        const keyLengthByteLen = setNumber(keyval.k.length, buffer.dataView, pointer);
        pointer += keyLengthByteLen;
        // key名(uint16*strlen)
        for (let ci = 0; ci < keyval.k.length; ci++) {
          buffer.dataView.setUint16(pointer + ci * 2, keyval.k.charCodeAt(ci));
        }
        pointer += keyval.k.length * 2;
        // value情報へのポインタ(uint32)
        // 後で書き込むので書き込む場所だけ覚えておく
        keyval.v = pointer;
        pointer += 4;
      }
    }
    offset += 4;
  }
  // 最後のpointer位置にoffsetを移動
  offset = pointer;

  // valueをencodeしていく
  for (let h = 0; h < numberOfBucket; h++) {
    // key毎の処理
    for (const keyval of bucket[h]) {
      // keyの参照先として、valueの先頭座標を設定
      buffer.dataView.setUint32(keyval.v, offset);
      // valueのencode
      const valueLen = encodeSub(buffer, offset, obj[keyval.k]);
      // valueのencode後サイズに合わせてoffsetを移動
      offset += valueLen;
    }
  }

  // 自身の(子要素も含む)サイズを返す
  return offset - initialOffset;
}

function encodeNull(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // 書き込むのは型だけ。
  buffer.dataView.setUint8(offset, typeToId.null);
  offset += 1;

  return offset - initialOffset;
}

function encodeBoolean(buffer, initialOffset, obj) {
  let offset = initialOffset;

  // 書き込むのは型だけ。
  if (obj === true) {
    buffer.dataView.setUint8(offset, typeToId.boolTrue);
  }
  else {
    buffer.dataView.setUint8(offset, typeToId.boolFalse);
  }
  offset += 1;

  return offset - initialOffset;
}

function encodeNumber(buffer, initialOffset, obj) {
  let offset = initialOffset;

  const length = setNumber(obj, buffer.dataView, offset);
  return length;
}

function encodeString(buffer, initialOffset, obj) {
  let offset = initialOffset;

  const strLen = obj.length;

  // 型
  buffer.dataView.setUint8(offset, typeToId.string);
  offset += 1;

  // 文字列長
  // 省メモリを突き詰めるなら数値の範囲毎に何でエンコードするか変えるべきだが
  // 手抜きでUint32で済ます
  const byteLen = setNumber(strLen, buffer.dataView, offset);
  offset += byteLen;

  // UTF16にばらして書き込み
  for (let ci = 0; ci < strLen; ci++) {
    buffer.dataView.setUint16(offset + ci * 2, obj.charCodeAt(ci));
  }

  return offset + strLen * 2 - initialOffset;
}

// objectまたはarrayならProxyを返す。それ以外は値そのものを返す
function getProxy(buffer) {
  return getProxySub(buffer, 0);
}

// getProxyの実体
function getProxySub(buffer, offset) {
  try {
    // type値を読み取る
    const head = new DataView(buffer);
    const typeValue = head.getUint8(offset);

    // 読み込み関数取得
    const readFunction = typeToReadFunction[typeValue];
    // 用意がある場合
    if (readFunction !== undefined) {
      return readFunction(buffer, offset);
    }

    // それ以外はnumberとみなす。場合分けがあるので特殊関数
    return getNumber(buffer, offset);
  } catch (e) {
    console.log(offset);
    throw new Error();
  }
}

function getString(buffer, initialOffset) {
  let offset = initialOffset;
  const dataView = new DataView(buffer);

  // typeは分かっているので飛ばす
  offset += 1;

  // 文字列長
  const [strLen, byteLen] = getNumberFromDataView(dataView, offset);
  offset += byteLen;

  // 文字列を読み込む
  let value = "";
  for (let ci = 0; ci < strLen; ci++) {
    value += String.fromCharCode(dataView.getUint16(offset + ci * 2));
  }

  return value;
}

function getNumber(buffer, initialOffset) {
  let offset = initialOffset;
  const dataView = new DataView(buffer);

  const [num, len] = getNumberFromDataView(dataView, initialOffset);
  return num;
}

function getArrayProxy(buffer, initialOffset) {
  let offset = initialOffset;
  const dataView = new DataView(buffer);

  // typeは分かっているので飛ばす
  offset += 1;

  // 長さを取り出す
  const [arrayLen, byteLen] = getNumberFromDataView(dataView, offset);
  offset += byteLen;

  // Proxyのターゲット。処理用の隠し変数を持たせておく
  const initialArray = new Array(arrayLen).fill(undefined);
  initialArray[proxyKey] = Object.assign(Object.create(null),
    {
      buffer,
      initialOffset,
      bodyOffset: offset,
      readedIndex: {}
    });

  return new Proxy(initialArray, {
    get: (target, targetKey) => {
      // lengthだけ特殊
      if (targetKey === "length") {
        return target.length;
      }

      const targetIntKey = Number(targetKey);
      // 数値でないkeyまたは0未満はサポート外。デフォルト動作に任せる
      if (!Number.isInteger(targetIntKey) || targetIntKey < 0) {
        return target[targetKey];
      }
      // 数値だが範囲外
      if (targetIntKey >= target.length) {
        return undefined;
      }

      // 隠し変数から処理用の変数を取り出す。
      const { buffer, initialOffset, bodyOffset, readedIndex } = target[proxyKey];

      // 一度呼ばれたことがあって値がプリミティブ(number, boolean, null)なら即返却
      if (targetIntKey in readedIndex) {
        return target[targetIntKey];
      }

      // typeとarrayLenの分を飛ばす
      let offset = bodyOffset;

      // 値へのポインタを取得
      const dataView = new DataView(buffer);
      const valuePointer = dataView.getUint32(offset + targetIntKey * 4);

      // 値を取得
      const value = getProxySub(buffer, valuePointer);

      // プリミティブなら覚えておく
      if (value == null) { // TODO: 今はundefinedは返ってこないが、nullかundefinedを意図してあえての==
        target[targetIntKey] = value;
        readedIndex[targetIntKey] = true;
      }
      else {
        const valueType = typeof value;
        if (valueType === "number" || valueType === "boolean") {
          target[targetIntKey] = value;
          target[proxyKey].readedIndex[targetIntKey] = true;
        }
      }
      // それ以外(string,object,array)は覚えておかない

      return value;
    }
  });

}

// Proxyのtargetに隠し変数を持つためのkey
const proxyKey = Symbol();

function getProxyKeyAndValueTypeGetCommon(target, targetKey, headerLength) {
  // 隠し変数から処理用の変数を取り出す。
  // isCompleteKeysは参照型でなく更新が必要なので取り出さずに直接アクセスする
  const { buffer, initialOffset, myValuePointers } = target[proxyKey];

  // 一度呼ばれたことがあって値がプリミティブ(number, boolean, null)なら即返却
  if (myValuePointers[targetKey] === 0) {
    return target[targetKey];
  }

  // typeとarrayLen(sparseArrayの場合)の分を飛ばす
  let offset = initialOffset + headerLength;

  // keyがあるかがまだ不明の場合
  if (target[targetKey] === undefined) {
    const dataView = new DataView(buffer);

    // hashテーブルサイズ
    const [hashTableSize, byteLen] = getNumberFromDataView(dataView, offset);
    offset += byteLen;

    // keyのhash値
    const hash = stringHash(targetKey) % hashTableSize;

    // hashテーブルの内容へのポインタ
    const tableValuePointer = dataView.getUint32(offset + hash * 4);
    // hash値に該当するkeyなし
    if (tableValuePointer === 0) {
      return undefined;
    }

    // 引数のkey名長
    const targetKeyLen = targetKey.length;

    // テーブル内容のサイズ
    const [tableValueSize, tableValueSizeByteLen] = getNumberFromDataView(dataView, tableValuePointer);
    // テーブル内容
    let tableEntryPointer = tableValuePointer + tableValueSizeByteLen;
    for (let entry = 0; entry < tableValueSize; entry++) {
      // index値
      const [keyIndex, keyIndexByteLen] = getNumberFromDataView(dataView, tableEntryPointer);
      tableEntryPointer += keyIndexByteLen;
      // key名長
      const [keyLength, keyLengthByteLen] = getNumberFromDataView(dataView, tableEntryPointer);
      tableEntryPointer += keyLengthByteLen;

      // 引数のkeyと長さが違うならスキップ
      if (keyLength !== targetKeyLen) {
        tableEntryPointer += 2 * keyLength + 4;
        continue;
      }

      // key名を一文字ずつチェック
      let key = "";
      let ki = 0;
      for (ki = 0; ki < keyLength; ki++) {
        if (dataView.getUint16(tableEntryPointer + ki * 2) !== targetKey.charCodeAt(ki)) break;
      }
      tableEntryPointer += keyLength * 2;

      // 一致した
      if (ki === keyLength) {
        // 値へのポインタ
        myValuePointers[targetKey] = dataView.getUint32(tableEntryPointer);
        break;
      }
      tableEntryPointer += 4;
    }
  }

  // keyが見つからなかった
  if (myValuePointers[targetKey] === undefined) {
    return undefined;
  }

  // 値を取得
  const value = getProxySub(buffer, myValuePointers[targetKey]);
  if (value == null) { // TODO: 今はundefinedは返ってこないが、nullかundefinedを意図してあえての==
    target[targetKey] = value;
    myValuePointers[targetKey] = 0;
  }
  else {
    const valueType = typeof value;
    if (valueType === "number" || valueType === "boolean") {
      target[targetKey] = value;
      myValuePointers[targetKey] = 0;
    }
  }
  // それ以外(string,object,array)は覚えておかない

  return value;
}

function getProxyKeyAndValueTypeOwnKeysCommon(target, headerLength) {
  // 隠し変数から処理用の変数を取り出す。
  // isCompleteKeysは参照型でなく更新が必要なので取り出さずに直接アクセスする
  const { buffer, initialOffset, myValuePointers } = target[proxyKey];

  // 一度でも呼ばれてたら前の結果を返すだけ
  if (target[proxyKey].isCompleteKeys) {
    return Object.keys(target);
  }

  // keyの順序を維持するための一時的なkey名配列
  const myKeys = [];

  // typeは分かっているので飛ばす
  let offset = initialOffset + headerLength;
  const dataView = new DataView(buffer);

  // hashテーブルサイズ
  const [hashTableSize, byteLen] = getNumberFromDataView(dataView, offset);
  offset += byteLen;

  // hash値でループ
  for (let hash = 0; hash < hashTableSize; hash++) {
    // テーブルの内容へのポインタ
    const tableValuePointer = dataView.getUint32(offset + hash * 4);
    // hash値に該当するkeyなし
    if (tableValuePointer === 0) {
      continue;
    }
    // テーブル内容のサイズ
    const [tableValueSize, tableValueSizeByteLen] = getNumberFromDataView(dataView, tableValuePointer);
    // テーブル内容
    let tableEntryPointer = tableValuePointer + tableValueSizeByteLen;
    for (let entry = 0; entry < tableValueSize; entry++) {
      // index値
      const [keyIndex, keyIndexByteLen] = getNumberFromDataView(dataView, tableEntryPointer);
      tableEntryPointer += keyIndexByteLen;
      // key名長
      const [keyLength, keyLengthByteLen] = getNumberFromDataView(dataView, tableEntryPointer);
      tableEntryPointer += keyLengthByteLen;

      // indexの場所のkey名がすでに分かっていたら飛ばす
      if (myKeys[keyIndex] !== undefined) {
        tableEntryPointer += 2 * keyLength + 4;
        continue;
      }

      // key名
      let key = "";
      for (let ki = 0; ki < keyLength; ki++) {
        key += String.fromCharCode(dataView.getUint16(tableEntryPointer));
        tableEntryPointer += 2;
      }
      myKeys[keyIndex] = key;

      // 値へのポインタ
      // 先にget等が呼ばれている場合はkey-valueがすでにあるので上書きしないようスキップ
      if (myValuePointers[key] === undefined) {
        myValuePointers[key] = dataView.getUint32(tableEntryPointer);
      }
      tableEntryPointer += 4;
    }
  }
  target[proxyKey].isCompleteKeys = true;
  myKeys.reduce((result, key) => {
    // 順序を再生するためにget等によりkeyがあっても一旦消して作り直す
    const value = (myValuePointers[key] === 0) ? result[key] : true;
    delete (result[key]);
    result[key] = value;
    return result;
  }, target);
  return myKeys;
}

function getSparseArrayProxy(buffer, initialOffset) {
  // サイズだけ先に読んでおく
  // typeは飛ばす
  let offset = initialOffset + 1;

  // 配列長(!=key.length)
  const dataView = new DataView(buffer);
  const [arrayLen, byteLen] = getNumberFromDataView(dataView, offset);
  offset += byteLen;

  const headerLen = offset - initialOffset;

  // Proxyのターゲット。処理用の隠し変数を持たせておく
  const initialArray = new Array(arrayLen);
  initialArray[proxyKey] = Object.assign(Object.create(null),
    {
      buffer,
      initialOffset,
      isCompleteKeys: false,
      // 値へのポインタの配列
      myValuePointers: Object.create(null)
    });

  return new Proxy(initialArray, {
    get: (target, targetKey) => {
      // lengthだけ特殊
      if (targetKey === "length") {
        return target.length;
      }
      return getProxyKeyAndValueTypeGetCommon(target, targetKey, headerLen);
    },
    ownKeys: (target) => {
      const result = getProxyKeyAndValueTypeOwnKeysCommon(target, headerLen);
      result.push("length");
      return result;
    }
  });
}

function getObjectProxy(buffer, initialOffset) {
  // Proxyのターゲット。処理用の隠し変数を持たせておく
  const initialObject = {
    [proxyKey]: Object.assign(Object.create(null),
      {
        buffer,
        initialOffset,
        isCompleteKeys: false,
        // 値へのポインタの配列
        myValuePointers: Object.create(null)
      })
  }

  return new Proxy(initialObject, {
    get: (target, targetKey) => {
      return getProxyKeyAndValueTypeGetCommon(target, targetKey, 1);
    },
    ownKeys: (target) => {
      return getProxyKeyAndValueTypeOwnKeysCommon(target, 1);
    }
  });
}

module.exports.encode = encode;
module.exports.getProxy = getProxy;

sample.js

const roJson = require('./roJson');

const buffer = roJson.encode({a: "Hello roJson.", b: 1, c: [0, 100, 200]});
const proxiedObject = roJson.getProxy(buffer);

console.log(proxiedObject.a); // "Hello roJson."
console.log(proxiedObject.c[1]); // 100