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