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