xref: /aosp_15_r20/external/flatbuffers/dart/lib/src/builder.dart (revision 890232f25432b36107d06881e0a25aaa6b473652)
1import 'dart:convert';
2import 'dart:typed_data';
3
4import 'types.dart';
5
6/// The main builder class for creation of a FlexBuffer.
7class Builder {
8  final ByteData _buffer;
9  List<_StackValue> _stack = [];
10  List<_StackPointer> _stackPointers = [];
11  int _offset = 0;
12  bool _finished = false;
13  final Map<String, _StackValue> _stringCache = {};
14  final Map<String, _StackValue> _keyCache = {};
15  final Map<_KeysHash, _StackValue> _keyVectorCache = {};
16  final Map<int, _StackValue> _indirectIntCache = {};
17  final Map<double, _StackValue> _indirectDoubleCache = {};
18
19  /// Instantiate the builder if you intent to gradually build up the buffer by calling
20  /// add... methods and calling [finish] to receive the the resulting byte array.
21  ///
22  /// The default size of internal buffer is set to 2048. Provide a different value in order to avoid buffer copies.
23  Builder({int size = 2048}) : _buffer = ByteData(size);
24
25  /// Use this method in order to turn an object into a FlexBuffer directly.
26  ///
27  /// Use the manual instantiation of the [Builder] and gradual addition of values, if performance is more important than convenience.
28  static ByteBuffer buildFromObject(Object? value) {
29    final builder = Builder();
30    builder._add(value);
31    final buffer = builder.finish();
32    final byteData = ByteData(buffer.lengthInBytes);
33    byteData.buffer.asUint8List().setAll(0, buffer);
34    return byteData.buffer;
35  }
36
37  void _add(Object? value) {
38    if (value == null) {
39      addNull();
40    } else if (value is bool) {
41      addBool(value);
42    } else if (value is int) {
43      addInt(value);
44    } else if (value is double) {
45      addDouble(value);
46    } else if (value is ByteBuffer) {
47      addBlob(value);
48    } else if (value is String) {
49      addString(value);
50    } else if (value is List<dynamic>) {
51      startVector();
52      for (var i = 0; i < value.length; i++) {
53        _add(value[i]);
54      }
55      end();
56    } else if (value is Map<String, dynamic>) {
57      startMap();
58      value.forEach((key, value) {
59        addKey(key);
60        _add(value);
61      });
62      end();
63    } else {
64      throw UnsupportedError('Value of unexpected type: $value');
65    }
66  }
67
68  /// Use this method if you want to store a null value.
69  ///
70  /// Specifically useful when building up a vector where values can be null.
71  void addNull() {
72    _integrityCheckOnValueAddition();
73    _stack.add(_StackValue.withNull());
74  }
75
76  /// Adds a string value.
77  void addInt(int value) {
78    _integrityCheckOnValueAddition();
79    _stack.add(_StackValue.withInt(value));
80  }
81
82  /// Adds a bool value.
83  void addBool(bool value) {
84    _integrityCheckOnValueAddition();
85    _stack.add(_StackValue.withBool(value));
86  }
87
88  /// Adds a double value.
89  void addDouble(double value) {
90    _integrityCheckOnValueAddition();
91    _stack.add(_StackValue.withDouble(value));
92  }
93
94  /// Adds a string value.
95  void addString(String value) {
96    _integrityCheckOnValueAddition();
97    if (_stringCache.containsKey(value)) {
98      _stack.add(_stringCache[value]!);
99      return;
100    }
101    final utf8String = utf8.encode(value);
102    final length = utf8String.length;
103    final bitWidth = BitWidthUtil.uwidth(length);
104    final byteWidth = _align(bitWidth);
105    _writeUInt(length, byteWidth);
106    final stringOffset = _offset;
107    final newOffset = _newOffset(length + 1);
108    _pushBuffer(utf8String);
109    _offset = newOffset;
110    final stackValue =
111        _StackValue.withOffset(stringOffset, ValueType.String, bitWidth);
112    _stack.add(stackValue);
113    _stringCache[value] = stackValue;
114  }
115
116  /// This methods adds a key to a map and should be followed by an add... value call.
117  ///
118  /// It also implies that you call this method only after you called [startMap].
119  void addKey(String value) {
120    _integrityCheckOnKeyAddition();
121    if (_keyCache.containsKey(value)) {
122      _stack.add(_keyCache[value]!);
123      return;
124    }
125    final utf8String = utf8.encode(value);
126    final length = utf8String.length;
127    final keyOffset = _offset;
128    final newOffset = _newOffset(length + 1);
129    _pushBuffer(utf8String);
130    _offset = newOffset;
131    final stackValue =
132        _StackValue.withOffset(keyOffset, ValueType.Key, BitWidth.width8);
133    _stack.add(stackValue);
134    _keyCache[value] = stackValue;
135  }
136
137  /// Adds a byte array.
138  ///
139  /// This method can be used to store any generic BLOB.
140  void addBlob(ByteBuffer value) {
141    _integrityCheckOnValueAddition();
142    final length = value.lengthInBytes;
143    final bitWidth = BitWidthUtil.uwidth(length);
144    final byteWidth = _align(bitWidth);
145    _writeUInt(length, byteWidth);
146    final blobOffset = _offset;
147    final newOffset = _newOffset(length);
148    _pushBuffer(value.asUint8List());
149    _offset = newOffset;
150    final stackValue =
151        _StackValue.withOffset(blobOffset, ValueType.Blob, bitWidth);
152    _stack.add(stackValue);
153  }
154
155  /// Stores int value indirectly in the buffer.
156  ///
157  /// Adding large integer values indirectly might be beneficial if those values suppose to be store in a vector together with small integer values.
158  /// This is due to the fact that FlexBuffers will add padding to small integer values, if they are stored together with large integer values.
159  /// When we add integer indirectly the vector of ints will contain not the value itself, but only the relative offset to the value.
160  /// By setting the [cache] parameter to true, you make sure that the builder tracks added int value and performs deduplication.
161  void addIntIndirectly(int value, {bool cache = false}) {
162    _integrityCheckOnValueAddition();
163    if (_indirectIntCache.containsKey(value)) {
164      _stack.add(_indirectIntCache[value]!);
165      return;
166    }
167    final stackValue = _StackValue.withInt(value);
168    final byteWidth = _align(stackValue.width);
169    final newOffset = _newOffset(byteWidth);
170    final valueOffset = _offset;
171    _pushBuffer(stackValue.asU8List(stackValue.width));
172    final stackOffset = _StackValue.withOffset(
173        valueOffset, ValueType.IndirectInt, stackValue.width);
174    _stack.add(stackOffset);
175    _offset = newOffset;
176    if (cache) {
177      _indirectIntCache[value] = stackOffset;
178    }
179  }
180
181  /// Stores double value indirectly in the buffer.
182  ///
183  /// Double are stored as 8 or 4 byte values in FlexBuffers. If they are stored in a mixed vector, values which are smaller than 4 / 8 bytes will be padded.
184  /// When we add double indirectly, the vector will contain not the value itself, but only the relative offset to the value. Which could occupy only 1 or 2 bytes, reducing the odds for unnecessary padding.
185  /// By setting the [cache] parameter to true, you make sure that the builder tracks already added double value and performs deduplication.
186  void addDoubleIndirectly(double value, {bool cache = false}) {
187    _integrityCheckOnValueAddition();
188    if (cache && _indirectDoubleCache.containsKey(value)) {
189      _stack.add(_indirectDoubleCache[value]!);
190      return;
191    }
192    final stackValue = _StackValue.withDouble(value);
193    final byteWidth = _align(stackValue.width);
194    final newOffset = _newOffset(byteWidth);
195    final valueOffset = _offset;
196    _pushBuffer(stackValue.asU8List(stackValue.width));
197    final stackOffset = _StackValue.withOffset(
198        valueOffset, ValueType.IndirectFloat, stackValue.width);
199    _stack.add(stackOffset);
200    _offset = newOffset;
201    if (cache) {
202      _indirectDoubleCache[value] = stackOffset;
203    }
204  }
205
206  /// This method starts a vector definition and needs to be followed by 0 to n add... value calls.
207  ///
208  /// The vector definition needs to be finished with an [end] call.
209  /// It is also possible to add nested vector or map by calling [startVector] / [startMap].
210  void startVector() {
211    _integrityCheckOnValueAddition();
212    _stackPointers.add(_StackPointer(_stack.length, true));
213  }
214
215  /// This method starts a map definition.
216  ///
217  /// This method call needs to be followed by 0 to n [addKey] +  add... value calls.
218  /// The map definition needs to be finished with an [end] call.
219  /// It is also possible to add nested vector or map by calling [startVector] / [startMap] after calling [addKey].
220  void startMap() {
221    _integrityCheckOnValueAddition();
222    _stackPointers.add(_StackPointer(_stack.length, false));
223  }
224
225  /// Marks that the addition of values to the last vector, or map have ended.
226  void end() {
227    final pointer = _stackPointers.removeLast();
228    if (pointer.isVector) {
229      _endVector(pointer);
230    } else {
231      _sortKeysAndEndMap(pointer);
232    }
233  }
234
235  /// Finish building the FlatBuffer and return array of bytes.
236  ///
237  /// Can be called multiple times, to get the array of bytes.
238  /// After the first call, adding values, or starting vectors / maps will result in an exception.
239  Uint8List finish() {
240    if (_finished == false) {
241      _finish();
242    }
243    return _buffer.buffer.asUint8List(0, _offset);
244  }
245
246  /// Builds a FlatBuffer with current state without finishing the builder.
247  ///
248  /// Creates an internal temporary copy of current builder and finishes the copy.
249  /// Use this method, when the state of a long lasting builder need to be persisted periodically.
250  ByteBuffer snapshot() {
251    final tmp = Builder(size: _offset + 200);
252    tmp._offset = _offset;
253    tmp._stack = List.from(_stack);
254    tmp._stackPointers = List.from(_stackPointers);
255    tmp._buffer.buffer
256        .asUint8List()
257        .setAll(0, _buffer.buffer.asUint8List(0, _offset));
258    for (var i = 0; i < tmp._stackPointers.length; i++) {
259      tmp.end();
260    }
261    final buffer = tmp.finish();
262    final bd = ByteData(buffer.lengthInBytes);
263    bd.buffer.asUint8List().setAll(0, buffer);
264    return bd.buffer;
265  }
266
267  void _integrityCheckOnValueAddition() {
268    if (_finished) {
269      throw StateError('Adding values after finish is prohibited');
270    }
271    if (_stackPointers.isNotEmpty && _stackPointers.last.isVector == false) {
272      if (_stack.last.type != ValueType.Key) {
273        throw StateError(
274            'Adding value to a map before adding a key is prohibited');
275      }
276    }
277  }
278
279  void _integrityCheckOnKeyAddition() {
280    if (_finished) {
281      throw StateError('Adding values after finish is prohibited');
282    }
283    if (_stackPointers.isEmpty || _stackPointers.last.isVector) {
284      throw StateError('Adding key before staring a map is prohibited');
285    }
286  }
287
288  void _finish() {
289    if (_stack.length != 1) {
290      throw StateError(
291          'Stack has to be exactly 1, but is ${_stack.length}. You have to end all started vectors and maps, before calling [finish]');
292    }
293    final value = _stack[0];
294    final byteWidth = _align(value.elementWidth(_offset, 0));
295    _writeStackValue(value, byteWidth);
296    _writeUInt(value.storedPackedType(), 1);
297    _writeUInt(byteWidth, 1);
298    _finished = true;
299  }
300
301  _StackValue _createVector(int start, int vecLength, int step,
302      [_StackValue? keys]) {
303    var bitWidth = BitWidthUtil.uwidth(vecLength);
304    var prefixElements = 1;
305    if (keys != null) {
306      var elemWidth = keys.elementWidth(_offset, 0);
307      if (elemWidth.index > bitWidth.index) {
308        bitWidth = elemWidth;
309      }
310      prefixElements += 2;
311    }
312    var vectorType = ValueType.Key;
313    var typed = keys == null;
314    for (var i = start; i < _stack.length; i += step) {
315      final elemWidth = _stack[i].elementWidth(_offset, i + prefixElements);
316      if (elemWidth.index > bitWidth.index) {
317        bitWidth = elemWidth;
318      }
319      if (i == start) {
320        vectorType = _stack[i].type;
321        typed &= ValueTypeUtils.isTypedVectorElement(vectorType);
322      } else {
323        if (vectorType != _stack[i].type) {
324          typed = false;
325        }
326      }
327    }
328    final byteWidth = _align(bitWidth);
329    final fix = typed & ValueTypeUtils.isNumber(vectorType) &&
330        vecLength >= 2 &&
331        vecLength <= 4;
332    if (keys != null) {
333      _writeStackValue(keys, byteWidth);
334      _writeUInt(1 << keys.width.index, byteWidth);
335    }
336    if (fix == false) {
337      _writeUInt(vecLength, byteWidth);
338    }
339    final vecOffset = _offset;
340    for (var i = start; i < _stack.length; i += step) {
341      _writeStackValue(_stack[i], byteWidth);
342    }
343    if (typed == false) {
344      for (var i = start; i < _stack.length; i += step) {
345        _writeUInt(_stack[i].storedPackedType(), 1);
346      }
347    }
348    if (keys != null) {
349      return _StackValue.withOffset(vecOffset, ValueType.Map, bitWidth);
350    }
351    if (typed) {
352      final vType =
353          ValueTypeUtils.toTypedVector(vectorType, fix ? vecLength : 0);
354      return _StackValue.withOffset(vecOffset, vType, bitWidth);
355    }
356    return _StackValue.withOffset(vecOffset, ValueType.Vector, bitWidth);
357  }
358
359  void _endVector(_StackPointer pointer) {
360    final vecLength = _stack.length - pointer.stackPosition;
361    final vec = _createVector(pointer.stackPosition, vecLength, 1);
362    _stack.removeRange(pointer.stackPosition, _stack.length);
363    _stack.add(vec);
364  }
365
366  void _sortKeysAndEndMap(_StackPointer pointer) {
367    if (((_stack.length - pointer.stackPosition) & 1) == 1) {
368      throw StateError(
369          'The stack needs to hold key value pairs (even number of elements). Check if you combined [addKey] with add... method calls properly.');
370    }
371
372    var sorted = true;
373    for (var i = pointer.stackPosition; i < _stack.length - 2; i += 2) {
374      if (_shouldFlip(_stack[i], _stack[i + 2])) {
375        sorted = false;
376        break;
377      }
378    }
379
380    if (sorted == false) {
381      for (var i = pointer.stackPosition; i < _stack.length; i += 2) {
382        var flipIndex = i;
383        for (var j = i + 2; j < _stack.length; j += 2) {
384          if (_shouldFlip(_stack[flipIndex], _stack[j])) {
385            flipIndex = j;
386          }
387        }
388        if (flipIndex != i) {
389          var k = _stack[flipIndex];
390          var v = _stack[flipIndex + 1];
391          _stack[flipIndex] = _stack[i];
392          _stack[flipIndex + 1] = _stack[i + 1];
393          _stack[i] = k;
394          _stack[i + 1] = v;
395        }
396      }
397    }
398    _endMap(pointer);
399  }
400
401  void _endMap(_StackPointer pointer) {
402    final vecLength = (_stack.length - pointer.stackPosition) >> 1;
403    final offsets = <int>[];
404    for (var i = pointer.stackPosition; i < _stack.length; i += 2) {
405      offsets.add(_stack[i].offset!);
406    }
407    final keysHash = _KeysHash(offsets);
408    _StackValue? keysStackValue;
409    if (_keyVectorCache.containsKey(keysHash)) {
410      keysStackValue = _keyVectorCache[keysHash];
411    } else {
412      keysStackValue = _createVector(pointer.stackPosition, vecLength, 2);
413      _keyVectorCache[keysHash] = keysStackValue;
414    }
415    final vec =
416        _createVector(pointer.stackPosition + 1, vecLength, 2, keysStackValue);
417    _stack.removeRange(pointer.stackPosition, _stack.length);
418    _stack.add(vec);
419  }
420
421  bool _shouldFlip(_StackValue v1, _StackValue v2) {
422    if (v1.type != ValueType.Key || v2.type != ValueType.Key) {
423      throw StateError(
424          'Stack values are not keys $v1 | $v2. Check if you combined [addKey] with add... method calls properly.');
425    }
426
427    late int c1, c2;
428    var index = 0;
429    do {
430      c1 = _buffer.getUint8(v1.offset! + index);
431      c2 = _buffer.getUint8(v2.offset! + index);
432      if (c2 < c1) return true;
433      if (c1 < c2) return false;
434      index += 1;
435    } while (c1 != 0 && c2 != 0);
436    return false;
437  }
438
439  int _align(BitWidth width) {
440    final byteWidth = BitWidthUtil.toByteWidth(width);
441    _offset += BitWidthUtil.paddingSize(_offset, byteWidth);
442    return byteWidth;
443  }
444
445  void _writeStackValue(_StackValue value, int byteWidth) {
446    final newOffset = _newOffset(byteWidth);
447    if (value.isOffset) {
448      final relativeOffset = _offset - value.offset!;
449      if (byteWidth == 8 || relativeOffset < (1 << (byteWidth * 8))) {
450        _writeUInt(relativeOffset, byteWidth);
451      } else {
452        throw StateError(
453            'Unexpected size $byteWidth. This might be a bug. Please create an issue https://github.com/google/flatbuffers/issues/new');
454      }
455    } else {
456      _pushBuffer(value.asU8List(BitWidthUtil.fromByteWidth(byteWidth)));
457    }
458    _offset = newOffset;
459  }
460
461  void _writeUInt(int value, int byteWidth) {
462    final newOffset = _newOffset(byteWidth);
463    _pushUInt(value, BitWidthUtil.fromByteWidth(byteWidth));
464    _offset = newOffset;
465  }
466
467  int _newOffset(int newValueSize) {
468    final newOffset = _offset + newValueSize;
469    var size = _buffer.lengthInBytes;
470    final prevSize = size;
471    while (size < newOffset) {
472      size <<= 1;
473    }
474    if (prevSize < size) {
475      final newBuf = ByteData(size);
476      newBuf.buffer.asUint8List().setAll(0, _buffer.buffer.asUint8List());
477    }
478    return newOffset;
479  }
480
481  void _pushInt(int value, BitWidth width) {
482    switch (width) {
483      case BitWidth.width8:
484        _buffer.setInt8(_offset, value);
485        break;
486      case BitWidth.width16:
487        _buffer.setInt16(_offset, value, Endian.little);
488        break;
489      case BitWidth.width32:
490        _buffer.setInt32(_offset, value, Endian.little);
491        break;
492      case BitWidth.width64:
493        _buffer.setInt64(_offset, value, Endian.little);
494        break;
495    }
496  }
497
498  void _pushUInt(int value, BitWidth width) {
499    switch (width) {
500      case BitWidth.width8:
501        _buffer.setUint8(_offset, value);
502        break;
503      case BitWidth.width16:
504        _buffer.setUint16(_offset, value, Endian.little);
505        break;
506      case BitWidth.width32:
507        _buffer.setUint32(_offset, value, Endian.little);
508        break;
509      case BitWidth.width64:
510        _buffer.setUint64(_offset, value, Endian.little);
511        break;
512    }
513  }
514
515  void _pushBuffer(List<int> value) {
516    _buffer.buffer.asUint8List().setAll(_offset, value);
517  }
518}
519
520class _StackValue {
521  late Object _value;
522  int? _offset;
523  final ValueType _type;
524  final BitWidth _width;
525
526  _StackValue.withNull()
527      : _type = ValueType.Null,
528        _width = BitWidth.width8;
529
530  _StackValue.withInt(int value)
531      : _type = ValueType.Int,
532        _width = BitWidthUtil.width(value),
533        _value = value;
534
535  _StackValue.withBool(bool value)
536      : _type = ValueType.Bool,
537        _width = BitWidth.width8,
538        _value = value;
539
540  _StackValue.withDouble(double value)
541      : _type = ValueType.Float,
542        _width = BitWidthUtil.width(value),
543        _value = value;
544
545  _StackValue.withOffset(int value, ValueType type, BitWidth width)
546      : _offset = value,
547        _type = type,
548        _width = width;
549
550  BitWidth storedWidth({BitWidth width = BitWidth.width8}) {
551    return ValueTypeUtils.isInline(_type)
552        ? BitWidthUtil.max(_width, width)
553        : _width;
554  }
555
556  int storedPackedType({BitWidth width = BitWidth.width8}) {
557    return ValueTypeUtils.packedType(_type, storedWidth(width: width));
558  }
559
560  BitWidth elementWidth(int size, int index) {
561    if (ValueTypeUtils.isInline(_type)) return _width;
562    final offset = _offset!;
563    for (var i = 0; i < 4; i++) {
564      final width = 1 << i;
565      final bitWidth = BitWidthUtil.uwidth(size +
566          BitWidthUtil.paddingSize(size, width) +
567          index * width -
568          offset);
569      if (1 << bitWidth.index == width) {
570        return bitWidth;
571      }
572    }
573    throw StateError(
574        'Element is of unknown. Size: $size at index: $index. This might be a bug. Please create an issue https://github.com/google/flatbuffers/issues/new');
575  }
576
577  List<int> asU8List(BitWidth width) {
578    if (ValueTypeUtils.isNumber(_type)) {
579      if (_type == ValueType.Float) {
580        if (width == BitWidth.width32) {
581          final result = ByteData(4);
582          result.setFloat32(0, _value as double, Endian.little);
583          return result.buffer.asUint8List();
584        } else {
585          final result = ByteData(8);
586          result.setFloat64(0, _value as double, Endian.little);
587          return result.buffer.asUint8List();
588        }
589      } else {
590        switch (width) {
591          case BitWidth.width8:
592            final result = ByteData(1);
593            result.setInt8(0, _value as int);
594            return result.buffer.asUint8List();
595          case BitWidth.width16:
596            final result = ByteData(2);
597            result.setInt16(0, _value as int, Endian.little);
598            return result.buffer.asUint8List();
599          case BitWidth.width32:
600            final result = ByteData(4);
601            result.setInt32(0, _value as int, Endian.little);
602            return result.buffer.asUint8List();
603          case BitWidth.width64:
604            final result = ByteData(8);
605            result.setInt64(0, _value as int, Endian.little);
606            return result.buffer.asUint8List();
607        }
608      }
609    }
610    if (_type == ValueType.Null) {
611      final result = ByteData(1);
612      result.setInt8(0, 0);
613      return result.buffer.asUint8List();
614    }
615    if (_type == ValueType.Bool) {
616      final result = ByteData(1);
617      result.setInt8(0, _value as bool ? 1 : 0);
618      return result.buffer.asUint8List();
619    }
620
621    throw StateError(
622        'Unexpected type: $_type. This might be a bug. Please create an issue https://github.com/google/flatbuffers/issues/new');
623  }
624
625  ValueType get type {
626    return _type;
627  }
628
629  BitWidth get width {
630    return _width;
631  }
632
633  bool get isOffset {
634    return !ValueTypeUtils.isInline(_type);
635  }
636
637  int? get offset => _offset;
638
639  bool get isFloat32 {
640    return _type == ValueType.Float && _width == BitWidth.width32;
641  }
642}
643
644class _StackPointer {
645  int stackPosition;
646  bool isVector;
647
648  _StackPointer(this.stackPosition, this.isVector);
649}
650
651class _KeysHash {
652  final List<int> keys;
653
654  const _KeysHash(this.keys);
655
656  @override
657  bool operator ==(Object other) {
658    if (other is _KeysHash) {
659      if (keys.length != other.keys.length) return false;
660      for (var i = 0; i < keys.length; i++) {
661        if (keys[i] != other.keys[i]) return false;
662      }
663      return true;
664    }
665    return false;
666  }
667
668  @override
669  int get hashCode {
670    var result = 17;
671    for (var i = 0; i < keys.length; i++) {
672      result = result * 23 + keys[i];
673    }
674    return result;
675  }
676}
677