...

Text file src/github.com/google/flatbuffers/ts/flexbuffers/builder.ts

Documentation: github.com/google/flatbuffers/ts/flexbuffers

     1import { BitWidth } from './bit-width.js'
     2import { paddingSize, iwidth, uwidth, fwidth, toByteWidth, fromByteWidth } from './bit-width-util.js'
     3import { toUTF8Array } from './flexbuffers-util.js'
     4import { ValueType } from './value-type.js'
     5import { isNumber, isTypedVectorElement, toTypedVector } from './value-type-util.js'
     6import { StackValue } from './stack-value.js'
     7
     8interface StackPointer {
     9  stackPosition: number,
    10  isVector: boolean
    11  presorted?: boolean
    12}
    13
    14export class Builder {
    15  buffer: ArrayBuffer
    16  view: DataView
    17
    18  readonly stack: Array<StackValue> = [];
    19  readonly stackPointers: Array<StackPointer> = [];
    20  offset = 0;
    21  finished = false;
    22  readonly stringLookup: Record<string, StackValue> = {};
    23  readonly keyLookup: Record<string, StackValue> = {};
    24  readonly keyVectorLookup: Record<string, StackValue> = {};
    25  readonly indirectIntLookup: Record<number, StackValue> = {};
    26  readonly indirectUIntLookup: Record<number, StackValue> = {};
    27  readonly indirectFloatLookup: Record<number, StackValue> = {};
    28
    29  constructor(size = 2048, private dedupStrings = true, private dedupKeys = true, private dedupKeyVectors = true) {
    30    this.buffer = new ArrayBuffer(size > 0 ? size : 2048);
    31    this.view = new DataView(this.buffer);
    32  }
    33
    34  private align(width: BitWidth) {
    35    const byteWidth = toByteWidth(width);
    36    this.offset += paddingSize(this.offset, byteWidth);
    37    return byteWidth;
    38  }
    39
    40  computeOffset(newValueSize: number): number {
    41    const targetOffset = this.offset + newValueSize;
    42    let size = this.buffer.byteLength;
    43    const prevSize = size;
    44    while (size < targetOffset) {
    45      size <<= 1;
    46    }
    47    if (prevSize < size) {
    48      const prevBuffer = this.buffer;
    49      this.buffer = new ArrayBuffer(size);
    50      this.view = new DataView(this.buffer);
    51      new Uint8Array(this.buffer).set(new Uint8Array(prevBuffer), 0);
    52    }
    53    return targetOffset;
    54  }
    55
    56  pushInt(value: number, width: BitWidth): void {
    57    if (width === BitWidth.WIDTH8) {
    58      this.view.setInt8(this.offset, value);
    59    } else if (width === BitWidth.WIDTH16) {
    60      this.view.setInt16(this.offset, value, true);
    61    } else if (width === BitWidth.WIDTH32) {
    62      this.view.setInt32(this.offset, value, true);
    63    } else if (width === BitWidth.WIDTH64) {
    64      this.view.setBigInt64(this.offset, BigInt(value), true);
    65    } else {
    66      throw `Unexpected width: ${width} for value: ${value}`;
    67    }
    68  }
    69
    70  pushUInt(value: number, width: BitWidth): void {
    71    if (width === BitWidth.WIDTH8) {
    72      this.view.setUint8(this.offset, value);
    73    } else if (width === BitWidth.WIDTH16) {
    74      this.view.setUint16(this.offset, value, true);
    75    } else if (width === BitWidth.WIDTH32) {
    76      this.view.setUint32(this.offset, value, true);
    77    } else if (width === BitWidth.WIDTH64) {
    78      this.view.setBigUint64(this.offset, BigInt(value), true);
    79    } else {
    80      throw `Unexpected width: ${width} for value: ${value}`;
    81    }
    82  }
    83
    84  private writeInt(value: number, byteWidth: number) {
    85    const newOffset = this.computeOffset(byteWidth);
    86    this.pushInt(value, fromByteWidth(byteWidth));
    87    this.offset = newOffset;
    88  }
    89
    90  private writeUInt(value: number, byteWidth: number) {
    91    const newOffset = this.computeOffset(byteWidth);
    92    this.pushUInt(value, fromByteWidth(byteWidth));
    93    this.offset = newOffset;
    94  }
    95
    96  private writeBlob(arrayBuffer: ArrayBuffer) {
    97    const length = arrayBuffer.byteLength;
    98    const bitWidth = uwidth(length);
    99    const byteWidth = this.align(bitWidth);
   100    this.writeUInt(length, byteWidth);
   101    const blobOffset = this.offset;
   102    const newOffset = this.computeOffset(length);
   103    new Uint8Array(this.buffer).set(new Uint8Array(arrayBuffer), blobOffset);
   104    this.stack.push(this.offsetStackValue(blobOffset, ValueType.BLOB, bitWidth));
   105    this.offset = newOffset;
   106  }
   107
   108  private writeString(str: string): void {
   109    if (this.dedupStrings && Object.prototype.hasOwnProperty.call(this.stringLookup, str)) {
   110      this.stack.push(this.stringLookup[str]);
   111      return;
   112    }
   113    const utf8 = toUTF8Array(str);
   114    const length = utf8.length;
   115    const bitWidth = uwidth(length);
   116    const byteWidth = this.align(bitWidth);
   117    this.writeUInt(length, byteWidth);
   118    const stringOffset = this.offset;
   119    const newOffset = this.computeOffset(length + 1);
   120    new Uint8Array(this.buffer).set(utf8, stringOffset);
   121    const stackValue = this.offsetStackValue(stringOffset, ValueType.STRING, bitWidth);
   122    this.stack.push(stackValue);
   123    if (this.dedupStrings) {
   124      this.stringLookup[str] = stackValue;
   125    }
   126    this.offset = newOffset;
   127  }
   128
   129  private writeKey(str: string): void {
   130    if (this.dedupKeys && Object.prototype.hasOwnProperty.call(this.keyLookup, str)) {
   131      this.stack.push(this.keyLookup[str]);
   132      return;
   133    }
   134    const utf8 = toUTF8Array(str);
   135    const length = utf8.length;
   136    const newOffset = this.computeOffset(length + 1);
   137    new Uint8Array(this.buffer).set(utf8, this.offset);
   138    const stackValue = this.offsetStackValue(this.offset, ValueType.KEY, BitWidth.WIDTH8);
   139    this.stack.push(stackValue);
   140    if (this.dedupKeys) {
   141      this.keyLookup[str] = stackValue;
   142    }
   143    this.offset = newOffset;
   144  }
   145
   146  private writeStackValue(value: StackValue, byteWidth: number): void {
   147    const newOffset = this.computeOffset(byteWidth);
   148    if (value.isOffset()) {
   149      const relativeOffset = this.offset - value.offset;
   150      if (byteWidth === 8 || BigInt(relativeOffset) < (BigInt(1) << BigInt(byteWidth * 8))) {
   151        this.writeUInt(relativeOffset, byteWidth);
   152      } else {
   153        throw `Unexpected size ${byteWidth}. This might be a bug. Please create an issue https://github.com/google/flatbuffers/issues/new`
   154      }
   155    } else {
   156      value.writeToBuffer(byteWidth);
   157    }
   158    this.offset = newOffset;
   159  }
   160
   161  private integrityCheckOnValueAddition() {
   162    if (this.finished) {
   163      throw "Adding values after finish is prohibited";
   164    }
   165    if (this.stackPointers.length !== 0 && this.stackPointers[this.stackPointers.length - 1].isVector === false) {
   166      if (this.stack[this.stack.length - 1].type !== ValueType.KEY) {
   167        throw "Adding value to a map before adding a key is prohibited";
   168      }
   169    }
   170  }
   171
   172  private integrityCheckOnKeyAddition() {
   173    if (this.finished) {
   174      throw "Adding values after finish is prohibited";
   175    }
   176    if (this.stackPointers.length === 0 || this.stackPointers[this.stackPointers.length - 1].isVector) {
   177      throw "Adding key before starting a map is prohibited";
   178    }
   179  }
   180
   181  startVector(): void {
   182    this.stackPointers.push({ stackPosition: this.stack.length, isVector: true });
   183  }
   184
   185  startMap(presorted = false): void {
   186    this.stackPointers.push({ stackPosition: this.stack.length, isVector: false, presorted: presorted });
   187  }
   188
   189  private endVector(stackPointer: StackPointer) {
   190    const vecLength = this.stack.length - stackPointer.stackPosition;
   191    const vec = this.createVector(stackPointer.stackPosition, vecLength, 1);
   192    this.stack.splice(stackPointer.stackPosition, vecLength);
   193    this.stack.push(vec);
   194  }
   195
   196  private endMap(stackPointer: StackPointer) {
   197    if (!stackPointer.presorted) {
   198      this.sort(stackPointer);
   199    }
   200    let keyVectorHash = "";
   201    for (let i = stackPointer.stackPosition; i < this.stack.length; i += 2) {
   202      keyVectorHash += `,${this.stack[i].offset}`;
   203    }
   204    const vecLength = (this.stack.length - stackPointer.stackPosition) >> 1;
   205
   206    if (this.dedupKeyVectors && !Object.prototype.hasOwnProperty.call(this.keyVectorLookup, keyVectorHash)) {
   207      this.keyVectorLookup[keyVectorHash] = this.createVector(stackPointer.stackPosition, vecLength, 2);
   208    }
   209    const keysStackValue = this.dedupKeyVectors ? this.keyVectorLookup[keyVectorHash] : this.createVector(stackPointer.stackPosition, vecLength, 2);
   210    const valuesStackValue = this.createVector(stackPointer.stackPosition + 1, vecLength, 2, keysStackValue);
   211    this.stack.splice(stackPointer.stackPosition, vecLength << 1);
   212    this.stack.push(valuesStackValue);
   213  }
   214
   215  private sort(stackPointer: StackPointer) {
   216    const view = this.view
   217    const stack = this.stack
   218
   219    function shouldFlip(v1: StackValue, v2: StackValue) {
   220      if (v1.type !== ValueType.KEY || v2.type !== ValueType.KEY) {
   221        throw `Stack values are not keys ${v1} | ${v2}. Check if you combined [addKey] with add... method calls properly.`
   222      }
   223      let c1, c2;
   224      let index = 0;
   225      do {
   226        c1 = view.getUint8(v1.offset + index);
   227        c2 = view.getUint8(v2.offset + index);
   228        if (c2 < c1) return true;
   229        if (c1 < c2) return false;
   230        index += 1;
   231      } while (c1 !== 0 && c2 !== 0);
   232      return false;
   233    }
   234
   235    function swap(stack: Array<StackValue>, flipIndex: number, i: number) {
   236      if (flipIndex === i) return;
   237      const k = stack[flipIndex];
   238      const v = stack[flipIndex + 1];
   239      stack[flipIndex] = stack[i];
   240      stack[flipIndex + 1] = stack[i + 1];
   241      stack[i] = k;
   242      stack[i + 1] = v;
   243    }
   244
   245    function selectionSort() {
   246      for (let i = stackPointer.stackPosition; i < stack.length; i += 2) {
   247        let flipIndex = i;
   248        for (let j = i + 2; j < stack.length; j += 2) {
   249          if (shouldFlip(stack[flipIndex], stack[j])) {
   250            flipIndex = j;
   251          }
   252        }
   253        if (flipIndex !== i) {
   254          swap(stack, flipIndex, i);
   255        }
   256      }
   257    }
   258
   259    function smaller(v1: StackValue, v2: StackValue) {
   260      if (v1.type !== ValueType.KEY || v2.type !== ValueType.KEY) {
   261        throw `Stack values are not keys ${v1} | ${v2}. Check if you combined [addKey] with add... method calls properly.`
   262      }
   263      if (v1.offset === v2.offset) {
   264        return false;
   265      }
   266      let c1, c2;
   267      let index = 0;
   268      do {
   269        c1 = view.getUint8(v1.offset + index);
   270        c2 = view.getUint8(v2.offset + index);
   271        if (c1 < c2) return true;
   272        if (c2 < c1) return false;
   273        index += 1;
   274      } while (c1 !== 0 && c2 !== 0);
   275      return false;
   276    }
   277
   278    function quickSort(left: number, right: number) {
   279
   280      if (left < right) {
   281        const mid = left + (((right - left) >> 2)) * 2;
   282        const pivot = stack[mid];
   283        let left_new = left;
   284        let right_new = right;
   285
   286        do {
   287          while (smaller(stack[left_new], pivot)) {
   288            left_new += 2;
   289          }
   290          while (smaller(pivot, stack[right_new])) {
   291            right_new -= 2;
   292          }
   293          if (left_new <= right_new) {
   294            swap(stack, left_new, right_new);
   295            left_new += 2;
   296            right_new -= 2;
   297          }
   298        } while (left_new <= right_new);
   299
   300        quickSort(left, right_new);
   301        quickSort(left_new, right);
   302
   303      }
   304    }
   305
   306    let sorted = true;
   307    for (let i = stackPointer.stackPosition; i < this.stack.length - 2; i += 2) {
   308      if (shouldFlip(this.stack[i], this.stack[i + 2])) {
   309        sorted = false;
   310        break;
   311      }
   312    }
   313
   314    if (!sorted) {
   315      if (this.stack.length - stackPointer.stackPosition > 40) {
   316        quickSort(stackPointer.stackPosition, this.stack.length - 2);
   317      } else {
   318        selectionSort();
   319      }
   320    }
   321  }
   322
   323  end(): void {
   324    if (this.stackPointers.length < 1) return;
   325    const pointer = this.stackPointers.pop() as StackPointer;
   326    if (pointer.isVector) {
   327      this.endVector(pointer);
   328    } else {
   329      this.endMap(pointer);
   330    }
   331  }
   332
   333  private createVector(start: number, vecLength: number, step: number, keys: StackValue | null = null) {
   334    let bitWidth = uwidth(vecLength);
   335    let prefixElements = 1;
   336    if (keys !== null) {
   337      const elementWidth = keys.elementWidth(this.offset, 0);
   338      if (elementWidth > bitWidth) {
   339        bitWidth = elementWidth;
   340      }
   341      prefixElements += 2;
   342    }
   343    let vectorType = ValueType.KEY;
   344    let typed = keys === null;
   345    for (let i = start; i < this.stack.length; i += step) {
   346      const elementWidth = this.stack[i].elementWidth(this.offset, i + prefixElements);
   347      if (elementWidth > bitWidth) {
   348        bitWidth = elementWidth;
   349      }
   350      if (i === start) {
   351        vectorType = this.stack[i].type;
   352        typed = typed && isTypedVectorElement(vectorType);
   353      } else {
   354        if (vectorType !== this.stack[i].type) {
   355          typed = false;
   356        }
   357      }
   358    }
   359    const byteWidth = this.align(bitWidth);
   360    const fix = typed && isNumber(vectorType) && vecLength >= 2 && vecLength <= 4;
   361    if (keys !== null) {
   362      this.writeStackValue(keys, byteWidth);
   363      this.writeUInt(1 << keys.width, byteWidth);
   364    }
   365    if (!fix) {
   366      this.writeUInt(vecLength, byteWidth);
   367    }
   368    const vecOffset = this.offset;
   369    for (let i = start; i < this.stack.length; i += step) {
   370      this.writeStackValue(this.stack[i], byteWidth);
   371    }
   372    if (!typed) {
   373      for (let i = start; i < this.stack.length; i += step) {
   374        this.writeUInt(this.stack[i].storedPackedType(), 1);
   375      }
   376    }
   377    if (keys !== null) {
   378      return this.offsetStackValue(vecOffset, ValueType.MAP, bitWidth);
   379    }
   380    if (typed) {
   381      const vType = toTypedVector(vectorType, fix ? vecLength : 0);
   382      return this.offsetStackValue(vecOffset, vType, bitWidth);
   383    }
   384    return this.offsetStackValue(vecOffset, ValueType.VECTOR, bitWidth);
   385  }
   386
   387  private nullStackValue() {
   388    return new StackValue(this, ValueType.NULL, BitWidth.WIDTH8);
   389  }
   390
   391  private boolStackValue(value: boolean) {
   392    return new StackValue(this, ValueType.BOOL, BitWidth.WIDTH8, value);
   393  }
   394
   395  private intStackValue(value: number | bigint) {
   396    return new StackValue(this, ValueType.INT, iwidth(value), value as number);
   397  }
   398
   399  private uintStackValue(value: number) {
   400    return new StackValue(this, ValueType.UINT, uwidth(value), value);
   401  }
   402
   403  private floatStackValue(value: number) {
   404    return new StackValue(this, ValueType.FLOAT, fwidth(value), value);
   405  }
   406
   407  private offsetStackValue(offset: number, valueType: ValueType, bitWidth: BitWidth): StackValue {
   408    return new StackValue(this, valueType, bitWidth, null, offset);
   409  }
   410
   411  private finishBuffer() {
   412    if (this.stack.length !== 1) {
   413      throw `Stack has to be exactly 1, but it is ${this.stack.length}. You have to end all started vectors and maps before calling [finish]`;
   414    }
   415    const value = this.stack[0];
   416    const byteWidth = this.align(value.elementWidth(this.offset, 0));
   417    this.writeStackValue(value, byteWidth);
   418    this.writeUInt(value.storedPackedType(), 1);
   419    this.writeUInt(byteWidth, 1);
   420    this.finished = true;
   421  }
   422
   423  add(value: undefined | null | boolean | bigint | number | DataView | string | Array<unknown> | Record<string, unknown> | unknown): void {
   424    this.integrityCheckOnValueAddition();
   425    if (typeof value === 'undefined') {
   426      throw "You need to provide a value";
   427    }
   428    if (value === null) {
   429      this.stack.push(this.nullStackValue());
   430    } else if (typeof value === "boolean") {
   431      this.stack.push(this.boolStackValue(value));
   432    } else if (typeof value === "bigint") {
   433      this.stack.push(this.intStackValue(value));
   434    } else if (typeof value == 'number') {
   435      if (Number.isInteger(value)) {
   436        this.stack.push(this.intStackValue(value));
   437      } else {
   438        this.stack.push(this.floatStackValue(value));
   439      }
   440    } else if (ArrayBuffer.isView(value)) {
   441      this.writeBlob(value.buffer);
   442    } else if (typeof value === 'string' || value instanceof String) {
   443      this.writeString(value as string);
   444    } else if (Array.isArray(value)) {
   445      this.startVector();
   446      for (let i = 0; i < value.length; i++) {
   447        this.add(value[i]);
   448      }
   449      this.end();
   450    } else if (typeof value === 'object') {
   451      const properties = Object.getOwnPropertyNames(value).sort();
   452      this.startMap(true);
   453      for (let i = 0; i < properties.length; i++) {
   454        const key = properties[i];
   455        this.addKey(key);
   456        this.add((value as Record<string, unknown>)[key]);
   457      }
   458      this.end();
   459    } else {
   460      throw `Unexpected value input ${value}`;
   461    }
   462  }
   463
   464  finish(): Uint8Array {
   465    if (!this.finished) {
   466      this.finishBuffer();
   467    }
   468    const result = this.buffer.slice(0, this.offset);
   469    return new Uint8Array(result);
   470  }
   471
   472  isFinished(): boolean {
   473    return this.finished;
   474  }
   475
   476  addKey(key: string): void {
   477    this.integrityCheckOnKeyAddition();
   478    this.writeKey(key);
   479  }
   480
   481  addInt(value: number, indirect = false, deduplicate = false): void {
   482    this.integrityCheckOnValueAddition();
   483    if (!indirect) {
   484      this.stack.push(this.intStackValue(value));
   485      return;
   486    }
   487    if (deduplicate && Object.prototype.hasOwnProperty.call(this.indirectIntLookup, value)) {
   488      this.stack.push(this.indirectIntLookup[value]);
   489      return;
   490    }
   491    const stackValue = this.intStackValue(value);
   492    const byteWidth = this.align(stackValue.width);
   493    const newOffset = this.computeOffset(byteWidth);
   494    const valueOffset = this.offset;
   495    stackValue.writeToBuffer(byteWidth);
   496    const stackOffset = this.offsetStackValue(valueOffset, ValueType.INDIRECT_INT, stackValue.width);
   497    this.stack.push(stackOffset);
   498    this.offset = newOffset;
   499    if (deduplicate) {
   500      this.indirectIntLookup[value] = stackOffset;
   501    }
   502  }
   503
   504  addUInt(value: number, indirect = false, deduplicate = false): void {
   505    this.integrityCheckOnValueAddition();
   506    if (!indirect) {
   507      this.stack.push(this.uintStackValue(value));
   508      return;
   509    }
   510    if (deduplicate && Object.prototype.hasOwnProperty.call(this.indirectUIntLookup, value)) {
   511      this.stack.push(this.indirectUIntLookup[value]);
   512      return;
   513    }
   514    const stackValue = this.uintStackValue(value);
   515    const byteWidth = this.align(stackValue.width);
   516    const newOffset = this.computeOffset(byteWidth);
   517    const valueOffset = this.offset;
   518    stackValue.writeToBuffer(byteWidth);
   519    const stackOffset = this.offsetStackValue(valueOffset, ValueType.INDIRECT_UINT, stackValue.width);
   520    this.stack.push(stackOffset);
   521    this.offset = newOffset;
   522    if (deduplicate) {
   523      this.indirectUIntLookup[value] = stackOffset;
   524    }
   525  }
   526
   527  addFloat(value: number, indirect = false, deduplicate = false): void {
   528    this.integrityCheckOnValueAddition();
   529    if (!indirect) {
   530      this.stack.push(this.floatStackValue(value));
   531      return;
   532    }
   533    if (deduplicate && Object.prototype.hasOwnProperty.call(this.indirectFloatLookup, value)) {
   534      this.stack.push(this.indirectFloatLookup[value]);
   535      return;
   536    }
   537    const stackValue = this.floatStackValue(value);
   538    const byteWidth = this.align(stackValue.width);
   539    const newOffset = this.computeOffset(byteWidth);
   540    const valueOffset = this.offset;
   541    stackValue.writeToBuffer(byteWidth);
   542    const stackOffset = this.offsetStackValue(valueOffset, ValueType.INDIRECT_FLOAT, stackValue.width);
   543    this.stack.push(stackOffset);
   544    this.offset = newOffset;
   545    if (deduplicate) {
   546      this.indirectFloatLookup[value] = stackOffset;
   547    }
   548  }
   549}

View as plain text