Initial flat buffers implementation.

pkg/analyzer/lib/src/summary/flat_buffers.dart

+library analyzer.src.summary.flat_buffers;
+
+import 'dart:collection';
+import 'dart:convert';
+import 'dart:typed_data';
+
+/**
+ * A pointer to some data.
+ */
+class BufferPointer {
+  final ByteData _buffer;
+  final int _offset;
+
+  factory BufferPointer.fromBytes(List<int> byteList, [int offset = 0]) {
+    ByteBuffer byteBuffer = new Int8List.fromList(byteList).buffer;

[Paul Berry, 2016/01/07 15:55:03]

It seems unfortunate that this constructor always makes a copy of byteList.  In
practice we'll always be creating a BufferPointer from a buffer we've read from
a file (in which case it will already be a Uint8List*), so no copy should be
necessary.

(*Note: this fact is, sadly, not documented in the SDK)

[scheglov, 2016/01/07 22:07:40]

Done.
If Uint8List is given, we create a view on it, without creating a copy.

+    ByteData buf = new ByteData.view(byteBuffer);
+    return new BufferPointer._(buf, offset);
+  }
+
+  BufferPointer._(this._buffer, this._offset);
+
+  BufferPointer derefObject() => _derefSOffset();

[Paul Berry, 2016/01/07 15:55:03]

This is incorrect.  Offsets to objects should be unsigned.  See
http://google.github.io/flatbuffers/md__internals.html, under the heading
"Offsets".

[scheglov, 2016/01/07 22:07:40]

OK, rewritten to use backward building.

+
+  @override
+  String toString() => _offset.toString();
+
+  BufferPointer _advance(int delta) {
+    return new BufferPointer._(_buffer, _offset + delta);
+  }
+
+  BufferPointer _derefSOffset() {
+    int sOffset = _getInt32();
+    return _advance(sOffset);

[Paul Berry, 2016/01/07 15:55:03]

This should be _advance(-sOffset).  Signed offsets are only used for vtables,
and in that case the offset is subtracted rather than added (see section
"tables" of http://google.github.io/flatbuffers/md__internals.html).

+  }
+
+  int _getInt32([int delta = 0]) =>
+      _buffer.getInt32(_offset + delta, Endianness.LITTLE_ENDIAN);
+
+  int _getInt8([int delta = 0]) => _buffer.getInt8(_offset + delta);
+
+  int _getUint16([int delta = 0]) =>
+      _buffer.getUint16(_offset + delta, Endianness.LITTLE_ENDIAN);
+
+  int _getUint32([int delta = 0]) =>
+      _buffer.getUint32(_offset + delta, Endianness.LITTLE_ENDIAN);
+}
+
+/**
+ * Class that helps building flat buffers.
+ */
+class Builder {
+  final int initialSize;
+
+  ByteData _buf;
+  int _offset;
+
+  int _currentTableOffset;
+  _VTableBuilder _currentVTableBuilder;
+
+  Builder({this.initialSize: 1024}) {
+    reset();
+  }
+
+  /**
+   * Add the [field] with the given 32-bit signed integer [value].  The field is
+   * not added if the [value] is equal to [def].
+   */
+  void addInt32(int field, int value, [int def]) {
+    if (_currentVTableBuilder == null) {
+      throw new StateError('Start a table before adding values.');
+    }
+    if (value != def) {
+      int size = 4;
+      _align(size);
+      _trackField(field);
+      _ensure(size);
+      _buf.setInt32(_offset, value, Endianness.LITTLE_ENDIAN);
+      _offset += size;
+    }
+  }
+
+  /**
+   * Add the [field] with the given 8-bit signed integer [value].  The field is
+   * not added if the [value] is equal to [def].
+   */
+  void addInt8(int field, int value, [int def]) {
+    if (_currentVTableBuilder == null) {
+      throw new StateError('Start a table before adding values.');
+    }
+    if (value != def) {
+      int size = 1;
+      _align(size);
+      _trackField(field);
+      _ensure(size);
+      _buf.setInt8(_offset, value);
+      _offset += size;
+    }
+  }
+
+  /**
+   * Add the [field] referencing an object with the given [offset].
+   */
+  void addOffset(int field, Offset offset) {
+    if (_currentVTableBuilder == null) {
+      throw new StateError('Start a table before adding values.');
+    }
+    if (offset != null) {
+      int size = 4;
+      _align(size);
+      _trackField(field);
+      _ensure(size);
+      _buf.setInt32(

[Paul Berry, 2016/01/07 15:55:03]

This isn't right.  Offsets are unsigned and always positive; with your
implementation they will be signed and always negative (because you output the
buffer in forward order and the thing being pointed to is always written before
the pointer).

Would you mind adding a TODO comment to remind us to come back and fix this?

+          _offset, offset._offset - _offset, Endianness.LITTLE_ENDIAN);
+      _offset += size;
+    }
+  }
+
+  /**
+   * End the current table and return its offset.
+   */
+  Offset endTable() {
+    if (_currentVTableBuilder == null) {
+      throw new StateError('Start a table before ending it.');
+    }
+    // Prepare the size of the current table.
+    int tableSize = _offset - _currentTableOffset;
+    // Prepare for writing the VTable.

[Paul Berry, 2016/01/07 15:55:03]

Add a TODO comment to note that we shouldn't output the vtable if it's the same
as a vtable we've output previously.

[scheglov, 2016/01/07 22:07:40]

Done.

+    _align(2);
+    int vTableOffset = _offset;
+    // Write the VTable.
+    int vTableSize = _currentVTableBuilder.size;
+    _ensure(vTableSize);
+    _offset = _currentVTableBuilder.output(_buf, _offset, tableSize);
+    // Set the VTable offset.
+    _buf.setInt32(_currentTableOffset, vTableOffset - _currentTableOffset,

[Paul Berry, 2016/01/07 15:55:03]

This should be _currentTableOffset - vTableOffset.  See section "Tables" of
http://google.github.io/flatbuffers/md__internals.html, which says "This offset
is substracted (not added) from the object start to arrive at the vtable start."

+        Endianness.LITTLE_ENDIAN);
+    // Done with this table.
+    _currentVTableBuilder = null;
+    return new Offset(_currentTableOffset);
+  }
+
+  /**
+   * Finish off the creation of the buffer.  The given [offset] is used as the
+   * root object offset, and usually references directly of indirectly every

[Paul Berry, 2016/01/07 15:55:03]

s/of/or/

[scheglov, 2016/01/07 22:07:39]

Done.

+   * written object.
+   */
+  Uint8List finish(Offset offset) {
+    _buf.setUint32(0, offset._offset, Endianness.LITTLE_ENDIAN);
+    return _buf.buffer.asUint8List(0, _offset);
+  }
+
+  /**
+   * Reset the builder and make it ready for filling a new buffer.
+   */
+  void reset() {
+    _offset = 0;
+    _buf = new ByteData(initialSize);
+    _currentVTableBuilder = null;
+    // Skip the root offset.
+    _align(4);
+    _ensure(4);
+    _buf.setUint32(_offset, -1, Endianness.LITTLE_ENDIAN);

[Paul Berry, 2016/01/07 15:55:03]

It seems weird to pass a literal -1 to setUint32, since it is guaranteed to
underflow.  This is just a placeholder value anyhow--how about just writing 0?

+    _offset += 4;
+  }
+
+  /**
+   * Start a new table.  Must be finished with [endTable] invocation.
+   */
+  void startTable() {
+    if (_currentVTableBuilder != null) {
+      throw new StateError('Inline tables are not supported.');
+    }
+    _currentVTableBuilder = new _VTableBuilder();
+    // Skip the VTable offset.
+    _align(4);
+    _currentTableOffset = _offset;
+    _buf.setUint32(_offset, -1, Endianness.LITTLE_ENDIAN);

[Paul Berry, 2016/01/07 15:55:03]

Similar comment here.

+    _offset += 4;
+  }
+
+  /**
+   * Write the given list of [values].
+   */
+  Offset writeList(List<Offset> values) {
+    if (_currentVTableBuilder != null) {
+      throw new StateError(
+          'Cannot write a non-scalar value while writing a table.');
+    }
+    _align(4);
+    Offset<String> result = new Offset(_offset);
+    _ensure(4 + values.length);
+    _buf.setUint32(_offset, values.length, Endianness.LITTLE_ENDIAN);
+    _offset += 4;
+    for (Offset value in values) {
+      _buf.setInt32(_offset, value._offset - _offset, Endianness.LITTLE_ENDIAN);

[Paul Berry, 2016/01/07 15:55:03]

As with line 112 this disagrees with the flatbuffer spec.  Offsets should be
unsigned and always positive.

+      _offset += 4;
+    }
+    return result;
+  }
+
+  /**
+   * Write the given string [value] and return its [Offset], or `null` if
+   * the [value] is equal to [def].
+   */
+  Offset<String> writeString(String value, [String def]) {
+    if (_currentVTableBuilder != null) {
+      throw new StateError(
+          'Cannot write a non-scalar value while writing a table.');
+    }
+    if (value != def) {
+      List<int> bytes = UTF8.encode(value);
+      _align(4);
+      Offset<String> result = new Offset(_offset);
+      _ensure(4 + bytes.length);
+      _buf.setUint32(_offset, bytes.length, Endianness.LITTLE_ENDIAN);
+      _offset += 4;
+      for (int b in bytes) {

[Paul Berry, 2016/01/07 15:55:03]

In practice UTF8.encode() will always return a Uint8List (sadly, this isn't
documented either), so we ought to be able to do a much more efficient copy than
this.

[scheglov, 2016/01/07 22:07:40]

I measured times to write using this cycle vs. using
_buf.buffer.asUint8List().setAll(offset, bytes) and the cycle is about 10%
faster.

[Paul Berry, 2016/01/07 22:44:53]

Fair enough.  Thanks for checking.

+        _buf.setInt8(_offset++, b);
+      }
+      return result;
+    }
+    return null;
+  }
+
+  /**
+   * Prepare to write an element with the given [size]. The current offset is
+   * aligned to the given [size].
+   */
+  void _align(int size) {
+    int alignDelta = (-_offset) % size;
+    _ensure(alignDelta + size);
+    _offset += alignDelta;
+  }
+
+  /**
+   * Ensure that there is at least the [size] bytes before the buffer end.
+   */
+  void _ensure(int size) {
+    int newSize = _offset + size;
+    int oldCapacity = _buf.lengthInBytes;
+    if (newSize > oldCapacity) {
+      int newCapacity = newSize * 2;
+      ByteData newBuf = new ByteData(newCapacity);
+      newBuf.buffer.asUint8List().setAll(0, _buf.buffer.asUint8List());
+      _buf = newBuf;
+    }
+  }
+
+  /**
+   * Record the offset of the given [field].
+   */
+  void _trackField(int field) {
+    _currentVTableBuilder.addField(field, _offset - _currentTableOffset);
+  }
+}
+
+/**
+ * The reader of 32-bit signed integers.
+ */
+class Int32Reader extends Reader<int> {
+  const Int32Reader() : super();
+
+  @override
+  int get size => 2;
+
+  @override
+  int read(BufferPointer bp) => bp._getInt32();
+}
+
+/**
+ * The reader of 8-bit signed integers.
+ */
+class Int8Reader extends Reader<int> {
+  const Int8Reader() : super();
+
+  @override
+  int get size => 1;
+
+  @override
+  int read(BufferPointer bp) => bp._getInt8();
+}
+
+/**
+ * The reader of object.
+ *
+ * The returned unmodifiable lists lazily read objects on access.
+ */
+class ListReader<E> extends Reader<List<E>> {
+  final Reader<E> _elementReader;
+
+  const ListReader(this._elementReader);
+
+  @override
+  int get size => 4;
+
+  @override
+  List<E> read(BufferPointer bp) =>
+      new _FbList<E>(_elementReader, bp.derefObject());
+}
+
+/**
+ * The absolute offset to a serialized object of the type [T].
+ */
+class Offset<T> {
+  final int _offset;
+
+  Offset(this._offset);
+}
+
+/**
+ * Object that can read a value at a [BufferPointer].
+ */
+abstract class Reader<T> {
+  const Reader();
+
+  /**
+   * The size of the value in bytes.
+   */
+  int get size;
+
+  /**
+   * Read the value at the given pointer.
+   */
+  T read(BufferPointer bp);
+
+  /**
+   * Read the value of the given [field] in the given [object].
+   */
+  T vTableGet(BufferPointer object, int field, [T defaultValue]) {
+    BufferPointer vTable = object._derefSOffset();
+    int vTableSize = vTable._getUint16();
+    int vTableFieldOffset = (1 + 1 + field) * 2;
+    if (vTableFieldOffset < vTableSize) {
+      int fieldOffsetInObject = vTable._getUint16(vTableFieldOffset);
+      if (fieldOffsetInObject != 0) {
+        BufferPointer fieldPointer = object._advance(fieldOffsetInObject);
+        return read(fieldPointer);
+      }
+    }
+    return defaultValue;
+  }
+}
+
+/**
+ * The reader of string values.
+ */
+class StringReader extends Reader<String> {
+  const StringReader() : super();
+
+  @override
+  int get size => 4;
+
+  @override
+  String read(BufferPointer ref) {
+    BufferPointer object = ref.derefObject();
+    int length = object._getUint32();
+    return UTF8
+        .decode(ref._buffer.buffer.asUint8List(object._offset + 4, length));
+  }
+}
+
+/**
+ * An abstract reader for tables.
+ */
+abstract class TableReader<T extends TableReader<T>> extends Reader<T> {
+  const TableReader();
+
+  @override
+  int get size => 4;
+
+  /**
+   * Return the [Reader] for reading fields of the object at [bp].
+   */
+  T createReader(BufferPointer bp);
+
+  @override
+  T read(BufferPointer bp) {
+    bp = bp.derefObject();
+    return createReader(bp);
+  }
+}
+
+class _FbList<E> extends Object with ListMixin<E> implements List<E> {
+  final Reader<E> elementReader;
+  final BufferPointer bp;
+
+  _FbList(this.elementReader, this.bp);
+
+  @override
+  int get length => bp._getUint32();
+
+  @override
+  void set length(int i) =>
+      throw new StateError('Attempt to modify immutable list');
+
+  @override
+  E operator [](int i) {
+    BufferPointer ref = bp._advance(4 + elementReader.size * i);
+    return elementReader.read(ref);
+  }
+
+  @override
+  void operator []=(int i, E e) =>
+      throw new StateError('Attempt to modify immutable list');
+}
+
+/**
+ * Class for building VTable(s).
+ */
+class _VTableBuilder {
+  final List<int> fieldOffsets = <int>[];
+
+  int get size => (1 + 1 + fieldOffsets.length) * 2;
+
+  void addField(int field, int offset) {
+    while (fieldOffsets.length <= field) {
+      fieldOffsets.add(null);
+    }
+    fieldOffsets[field] = offset;
+  }
+
+  /**
+   * Outputs this VTable to [buf], which is is expected to be aligned and
+   * have at least [size] bytes available.  Return the offset directly after
+   * the VTable in [buf].
+   */
+  int output(ByteData buf, int bufOffset, int tableSize) {
+    buf.setUint16(bufOffset, size, Endianness.LITTLE_ENDIAN);
+    bufOffset += 2;
+    buf.setUint16(bufOffset, tableSize, Endianness.LITTLE_ENDIAN);
+    bufOffset += 2;
+    for (int fieldOffset in fieldOffsets) {
+      buf.setUint16(bufOffset, fieldOffset ?? 0, Endianness.LITTLE_ENDIAN);
+      bufOffset += 2;
+    }
+    return bufOffset;
+  }
+}