Share VTable(s) in FlatBuffers.

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

 // Copyright (c) 2016, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 library analyzer.src.summary.flat_buffers;
 
 import 'dart:collection';
 import 'dart:convert';
 import 'dart:typed_data';
 
@@ skipping 47 matching lines @@
     }
   }
 }
 
 /**
  * Class that helps building flat buffers.
  */
 class Builder {
   final int initialSize;
 
+  /**
+   * The list of existing VTable(s).
+   */
+  final List<_VTable> _vTables = <_VTable>[];
+
   ByteData _buf;
 
   /**
    * The maximum alignment that has been seen so far.  If [_buf] has to be
    * reallocated in the future (to insert room at its start for more bytes) the
    * reallocation will need to be a multiple of this many bytes.
    */
   int _maxAlign;
 
   /**
    * The number of bytes that have been written to the buffer so far.  The
    * most recently written byte is this many bytes from the end of [_buf].
    */
   int _tail;
 
   /**
    * The location of the end of the current table, measured in bytes from the
    * end of [_buf], or `null` if a table is not currently being built.
    */
   int _currentTableEndTail;
 
-  _VTableBuilder _currentVTableBuilder;
+  _VTable _currentVTable;
 
   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) {
+    if (_currentVTable == null) {
       throw new StateError('Start a table before adding values.');
     }
     if (value != def) {
       int size = 4;
       _prepare(size, 1);
       _trackField(field);
       _setInt32AtTail(_buf, _tail, value);
     }
   }
 
   /**
    * 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) {
+    if (_currentVTable == null) {
       throw new StateError('Start a table before adding values.');
     }
     if (value != def) {
       int size = 1;
       _prepare(size, 1);
       _trackField(field);
       _buf.setInt8(_buf.lengthInBytes - _tail, value);
     }
   }
 
   /**
    * Add the [field] referencing an object with the given [offset].
    */
   void addOffset(int field, Offset offset) {
-    if (_currentVTableBuilder == null) {
+    if (_currentVTable == null) {
       throw new StateError('Start a table before adding values.');
     }
     if (offset != null) {
       _prepare(4, 1);
       _trackField(field);
       _setUint32AtTail(_buf, _tail, _tail - offset._tail);
     }
   }
 
   /**
    * End the current table and return its offset.
    */
   Offset endTable() {
-    if (_currentVTableBuilder == null) {
+    if (_currentVTable == null) {
       throw new StateError('Start a table before ending it.');
     }
     // Prepare the size of the current table.
-    int tableSize = _tail - _currentTableEndTail;
+    _currentVTable.tableSize = _tail - _currentTableEndTail;
     // Prepare for writing the VTable.
     _prepare(4, 1);
     int tableTail = _tail;
-    // Write the VTable.
-    // TODO(scheglov) implement VTable(s) sharing
-    _prepare(2, _currentVTableBuilder.numOfUint16);
-    _currentVTableBuilder.output(
-        _buf, _buf.lengthInBytes - _tail, tableTail, tableSize);
+    // Prepare the VTable to use for the current table.
+    int vTableTail;
+    {
+      _currentVTable.computeFieldOffsets(tableTail);
+      // Try to find an existing compatible VTable.
+      for (_VTable vTable in _vTables) {

[Paul Berry, 2016/01/08 18:31:35]

If this linear search proves too expensive, I have some ideas about ways we
could be more efficient.  But I think it's good for now--no point in optimizing
it unless it proves to be a problem :)

+        if (_currentVTable.canUseExistingVTable(vTable)) {
+          vTableTail = vTable.tail;
+        }
+      }
+      // Write a new VTable.
+      if (vTableTail == null) {
+        _prepare(2, _currentVTable.numOfUint16);
+        vTableTail = _tail;
+        _currentVTable.tail = vTableTail;
+        _currentVTable.output(_buf, _buf.lengthInBytes - _tail);
+        _vTables.add(_currentVTable);
+      }
+    }
     // Set the VTable offset.
-    _setInt32AtTail(_buf, tableTail, _tail - tableTail);
+    _setInt32AtTail(_buf, tableTail, vTableTail - tableTail);
     // Done with this table.
-    _currentVTableBuilder = null;
+    _currentVTable = null;
     return new Offset(tableTail);
   }
 
   /**
    * Finish off the creation of the buffer.  The given [offset] is used as the
    * root object offset, and usually references directly or indirectly every
    * written object.
    */
   Uint8List finish(Offset offset) {
     _prepare(4, 1);
@@ skipping 35 matching lines @@
     _buf.setUint8(_buf.lengthInBytes - _tail, value);
   }
 
   /**
    * Reset the builder and make it ready for filling a new buffer.
    */
   void reset() {
     _buf = new ByteData(initialSize);
     _maxAlign = 1;
     _tail = 0;
-    _currentVTableBuilder = null;
+    _currentVTable = null;
   }
 
   /**
    * Start a new table.  Must be finished with [endTable] invocation.
    */
   void startTable() {
-    if (_currentVTableBuilder != null) {
+    if (_currentVTable != null) {
       throw new StateError('Inline tables are not supported.');
     }
-    _currentVTableBuilder = new _VTableBuilder();
+    _currentVTable = new _VTable();
     _currentTableEndTail = _tail;
   }
 
   /**
    * Write the given list of [values].
    */
   Offset writeList(List<Offset> values) {
-    if (_currentVTableBuilder != null) {
+    if (_currentVTable != null) {
       throw new StateError(
           'Cannot write a non-scalar value while writing a table.');
     }
     _prepare(4, 1 + values.length);
     Offset result = new Offset(_tail);
     int tail = _tail;
     _setUint32AtTail(_buf, tail, values.length);
     tail -= 4;
     for (Offset value in values) {
       _setUint32AtTail(_buf, tail, tail - value._tail);
       tail -= 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) {
+    if (_currentVTable != null) {
       throw new StateError(
           'Cannot write a non-scalar value while writing a table.');
     }
     if (value != def) {
       // TODO(scheglov) optimize for ASCII strings
       List<int> bytes = UTF8.encode(value);
       int length = bytes.length;
       _prepare(4, 1, additionalBytes: length);
       Offset<String> result = new Offset(_tail);
       _setUint32AtTail(_buf, _tail, length);
@@ skipping 36 matching lines @@
       }
     }
     // Update the tail pointer.
     _tail += bufSize;
   }
 
   /**
    * Record the offset of the given [field].
    */
   void _trackField(int field) {
-    _currentVTableBuilder.addField(field, _tail);
+    _currentVTable.addField(field, _tail);
   }
 
   static void _setInt32AtTail(ByteData _buf, int tail, int x) {
     _buf.setInt32(_buf.lengthInBytes - tail, x, Endianness.LITTLE_ENDIAN);
   }
 
   static void _setUint32AtTail(ByteData _buf, int tail, int x) {
     _buf.setUint32(_buf.lengthInBytes - tail, x, Endianness.LITTLE_ENDIAN);
   }
 }
@@ skipping 143 matching lines @@
     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 that describes the structure of a table.
  */
-class _VTableBuilder {
+class _VTable {
   final List<int> fieldTails = <int>[];
+  final List<int> fieldOffsets = <int>[];
+
+  /**
+   * The size of the table that uses this VTable.
+   */
+  int tableSize;
+
+  /**
+   * The tail of this VTable.  It is used to share the same VTable between
+   * multiple tables of identical structure.
+   */
+  int tail;
 
   int get numOfUint16 => 1 + 1 + fieldTails.length;
 
   void addField(int field, int offset) {
     while (fieldTails.length <= field) {
       fieldTails.add(null);
     }
     fieldTails[field] = offset;
   }
 
   /**
+   * Return `true` if the [existing] VTable can be used instead of this.
+   */
+  bool canUseExistingVTable(_VTable existing) {
+    assert(tail == null);
+    assert(existing.tail != null);
+    if (tableSize == existing.tableSize &&
+        fieldOffsets.length == existing.fieldOffsets.length) {
+      for (int i = 0; i < fieldOffsets.length; i++) {
+        if (fieldOffsets[i] != existing.fieldOffsets[i]) {
+          return false;
+        }
+      }
+      return true;
+    }
+    return false;
+  }
+
+  /**
+   * Fill the [fieldOffsets] field.
+   */
+  void computeFieldOffsets(int tableTail) {
+    assert(fieldOffsets.isEmpty);
+    for (int fieldTail in fieldTails) {
+      int fieldOffset = fieldTail == null ? 0 : tableTail - fieldTail;
+      fieldOffsets.add(fieldOffset);
+    }
+  }
+
+  /**
    * Outputs this VTable to [buf], which is is expected to be aligned to 16-bit
    * and have at least [numOfUint16] 16-bit words available.
    */
-  void output(ByteData buf, int bufOffset, int tableTail, int tableSize) {
+  void output(ByteData buf, int bufOffset) {
     // VTable size.
     buf.setUint16(bufOffset, numOfUint16 * 2, Endianness.LITTLE_ENDIAN);
     bufOffset += 2;
     // Table size.
     buf.setUint16(bufOffset, tableSize, Endianness.LITTLE_ENDIAN);
     bufOffset += 2;
     // Field offsets.
-    for (int fieldTail in fieldTails) {
-      int fieldOffset = fieldTail == null ? 0 : tableTail - fieldTail;
+    for (int fieldOffset in fieldOffsets) {
       buf.setUint16(bufOffset, fieldOffset, Endianness.LITTLE_ENDIAN);
       bufOffset += 2;
     }
   }
 }