Port SplitIndexStore to Dart.

pkg/analysis_server/lib/src/index/split_store.dart

Index: pkg/analysis_server/lib/src/index/split_store.dart
diff --git a/pkg/analysis_server/lib/src/index/split_store.dart b/pkg/analysis_server/lib/src/index/split_store.dart
new file mode 100644
index 0000000000000000000000000000000000000000..a850c4abfcbae75725aeb571710b029cc528f1a5
--- /dev/null
+++ b/pkg/analysis_server/lib/src/index/split_store.dart
@@ -0,0 +1,1141 @@
+// Copyright (c) 2014, 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 index.split.store;
+
+import 'dart:async';
+import 'dart:collection';
+import 'dart:io';
+import 'dart:typed_data';
+
+import 'package:analyzer/src/generated/element.dart';
+import 'package:analyzer/src/generated/engine.dart';
+import 'package:analyzer/src/generated/index.dart';
+import 'package:analyzer/src/generated/source.dart';
+
+
+/**
+ * A helper that encodes/decodes [AnalysisContext]s from/to integers.
+ */
+class ContextCodec {
+  /**
+   * A table mapping contexts to their unique indices.
+   */
+  Map<AnalysisContext, int> _contextToIndex = new HashMap<AnalysisContext, int>(

[Paul Berry, 2014/06/20 15:46:01]

The Java version of this class uses weak references to the AnalysisContexts. 
Since we don't have weak references in Dart, I think we're going to need to take
a different approach.

As written, AnalysisContexts can only be added to the ContextCodec, never
removed.  Which means that in effect, AnalysisContexts will never be garbage
collected.

[Brian Wilkerson, 2014/06/20 15:55:30]

I thought we had already added an API to notify the index when a context was
being deleted so that we could remove the context's data from the index. We
should make that same API also remove the context from the codec (and consider
removing the use of weak references on the Java side as well).

[scheglov, 2014/06/20 16:16:56]

You're right.
I plan to do this in the next CL.

+      );
+
+  /**
+   * A table mapping indices to the corresponding contexts.
+   */
+  Map<int, AnalysisContext> _indexToContext = new HashMap<int, AnalysisContext>(
+      );
+
+  /**
+   * Returns the [AnalysisContext] that corresponds to the given index.
+   */
+  AnalysisContext decode(int index) => _indexToContext[index];
+
+  /**
+   * Returns an unique index for the given [AnalysisContext].
+   */
+  int encode(AnalysisContext context) {
+    int index = _contextToIndex[context];
+    if (index == null) {
+      index = _indexToContext.length;
+      _contextToIndex[context] = index;
+      _indexToContext[index] = context;
+    }
+    return index;
+  }
+}
+
+
+/**
+ * A helper that encodes/decodes [Element]s to/from integers.
+ */
+class ElementCodec {
+  /**
+   * A list that works as a mapping of integers to element encodings (in form of integer arrays).
+   */
+  List<List<int>> _indexToPath = [];
+
+  /**
+   * A table mapping element locations (in form of integer arrays) into a single integer.
+   */
+  IntArrayToIntMap _pathToIndex = new IntArrayToIntMap(10000, 0.75);
+
+  final StringCodec _stringCodec;
+
+  ElementCodec(this._stringCodec);
+
+  /**
+   * Returns an [Element] that corresponds to the given location.
+   *
+   * @param context the [AnalysisContext] to find [Element] in
+   * @param index an integer corresponding to the [Element]
+   * @return the [Element] or `null`
+   */
+  Element decode(AnalysisContext context, int index) {
+    List<int> path = _indexToPath[index];
+    List<String> components = _getLocationComponents(path);
+    ElementLocation location = new ElementLocationImpl.con3(components);
+    return context.getElement(location);
+  }
+
+  /**
+   * Returns a unique integer that corresponds to the given [Element].
+   */
+  int encode(Element element) {
+    List<int> path = _getLocationPath(element);
+    int index = _pathToIndex.get(path, -1);
+    if (index == -1) {
+      index = _indexToPath.length;
+      _pathToIndex.put(path, index);
+      _indexToPath.add(path);
+    }
+    return index;
+  }
+
+  List<String> _getLocationComponents(List<int> path) {
+    int length = path.length;
+    List<String> components = new List<String>();
+    for (int i = 0; i < length; i++) {
+      int componentId = path[i];
+      String component = _stringCodec.decode(componentId);
+      if (i < length - 1 && path[i + 1] < 0) {
+        component += "@${(-path[i + 1])}";
+        i++;
+      }
+      components.add(component);
+    }
+    return components;
+  }
+
+  List<int> _getLocationPath(Element element) {
+    List<String> components = element.location.components;
+    int length = components.length;
+    if (_hasLocalOffset(components)) {
+      List<int> path = new List<int>();
+      for (String component in components) {
+        int atOffset = component.indexOf('@');
+        if (atOffset == -1) {
+          path.add(_stringCodec.encode(component));
+        } else {
+          String preAtString = component.substring(0, atOffset);
+          String atString = component.substring(atOffset + 1);
+          path.add(_stringCodec.encode(preAtString));
+          path.add(-1 * int.parse(atString));
+        }
+      }
+      return path;
+    } else {
+      List<int> path = new List<int>.filled(length, 0);
+      for (int i = 0; i < length; i++) {
+        String component = components[i];
+        path[i] = _stringCodec.encode(component);
+      }
+      return path;
+    }
+  }
+
+  bool _hasLocalOffset(List<String> components) {
+    for (String component in components) {
+      if (component.indexOf('@') != -1) {
+        return true;
+      }
+    }
+    return false;
+  }
+}
+
+
+/**
+ * A manager for files content.
+ */
+abstract class FileManager {
+  /**
+   * Removes all files.
+   */
+  void clear();
+
+  /**
+   * Deletes the file with the given name.
+   */
+  void delete(String name);
+
+  /**
+   * Read the entire file contents as a list of bytes.
+   */
+  Future<List<int>> read(String name);
+
+  /**
+   * Write a list of bytes to a file.
+   */
+  Future write(String name, Uint8List bytes);
+}
+
+
+/**
+ * A [FileManager] based [NodeManager].
+ */
+class FileNodeManager implements NodeManager {
+  static int _VERSION = 1;
+
+  final ContextCodec contextCodec;
+
+  final ElementCodec elementCodec;
+
+  final StringCodec stringCodec;
+
+  final FileManager _fileManager;
+
+  int _locationCount = 0;
+
+  final Logger _logger;
+
+  Map<String, int> _nodeLocationCounts = {};
+
+  final RelationshipCodec _relationshipCodec;
+
+  FileNodeManager(this._fileManager, this._logger, this.stringCodec,
+      this.contextCodec, this.elementCodec, this._relationshipCodec);
+
+  @override
+  int get locationCount => _locationCount;
+
+  @override
+  void clear() {
+    _fileManager.clear();
+  }
+
+  @override
+  Future<IndexNode> getNode(String name) {
+    return _fileManager.read(name).then((List<int> bytes) {
+      if (bytes == null) {
+        return null;
+      }
+      _DataInputStream stream = new _DataInputStream(bytes);
+      return _readNode(stream);
+    }).catchError((e) {

[Paul Berry, 2014/06/20 15:46:01]

Should probably log the stack trace as well.

[scheglov, 2014/06/20 16:16:56]

OK, I will use CaughtException.

+      _logger.logError2("Exception during reading index file ${name}", e);
+    });
+  }
+
+  @override
+  IndexNode newNode(AnalysisContext context) => new IndexNode(context,
+      elementCodec, _relationshipCodec);
+
+  @override
+  Future putNode(String name, IndexNode node) {
+    // update location count
+    {
+      _locationCount -= _getLocationCount(name);
+      int nodeLocationCount = node.locationCount;
+      _nodeLocationCounts[name] = nodeLocationCount;
+      _locationCount += nodeLocationCount;
+    }
+    // write the node
+    return new Future.microtask(() {
+      _DataOutputStream stream = new _DataOutputStream();
+      _writeNode(node, stream);
+      var bytes = stream.getBytes();
+      return _fileManager.write(name, bytes);
+    }).catchError((e) {

[Paul Berry, 2014/06/20 15:46:01]

Log the stack trace here too.

[scheglov, 2014/06/20 16:16:56]

OK, I will use CaughtException.

+      _logger.logError2("Exception during writing index file ${name}", e);
+    });
+  }
+
+  @override
+  void removeNode(String name) {
+    // update location count
+    _locationCount -= _getLocationCount(name);
+    _nodeLocationCounts.remove(name);
+    // remove node
+    _fileManager.delete(name);
+  }
+
+  int _getLocationCount(String name) {
+    int locationCount = _nodeLocationCounts[name];
+    return locationCount != null ? locationCount : 0;
+  }
+
+  RelationKeyData _readElementRelationKey(_DataInputStream stream) {
+    int elementId = stream.readInt();
+    int relationshipId = stream.readInt();
+    return new RelationKeyData.forData(elementId, relationshipId);
+  }
+
+  LocationData _readLocationData(_DataInputStream stream) {
+    int elementId = stream.readInt();
+    int offset = stream.readInt();
+    int length = stream.readInt();
+    return new LocationData.forData(elementId, offset, length);
+  }
+
+  IndexNode _readNode(_DataInputStream stream) {
+    // check version
+    {
+      int version = stream.readInt();
+      if (version != _VERSION) {
+        throw new StateError(
+            "Version ${_VERSION} expected, but ${version} found.");
+      }
+    }
+    // context
+    int contextId = stream.readInt();
+    AnalysisContext context = contextCodec.decode(contextId);
+    if (context == null) {
+      return null;
+    }
+    // relations
+    Map<RelationKeyData, List<LocationData>> relations = {};
+    int numRelations = stream.readInt();
+    for (int i = 0; i < numRelations; i++) {
+      RelationKeyData key = _readElementRelationKey(stream);
+      int numLocations = stream.readInt();
+      List<LocationData> locations = new List<LocationData>();
+      for (int j = 0; j < numLocations; j++) {
+        locations.add(_readLocationData(stream));
+      }
+      relations[key] = locations;
+    }
+    // create IndexNode
+    IndexNode node = new IndexNode(context, elementCodec, _relationshipCodec);
+    node.relations = relations;
+    return node;
+  }
+
+  void _writeElementRelationKey(_DataOutputStream stream, RelationKeyData key) {
+    stream.writeInt(key.elementId);
+    stream.writeInt(key.relationshipId);
+  }
+
+  void _writeNode(IndexNode node, _DataOutputStream stream) {
+    // version
+    stream.writeInt(_VERSION);
+    // context
+    {
+      AnalysisContext context = node.context;
+      int contextId = contextCodec.encode(context);
+      stream.writeInt(contextId);
+    }
+    // relations
+    Map<RelationKeyData, List<LocationData>> relations = node.relations;
+    stream.writeInt(relations.length);
+    relations.forEach((key, locations) {
+      _writeElementRelationKey(stream, key);
+      stream.writeInt(locations.length);
+      for (LocationData location in locations) {
+        stream.writeInt(location.elementId);
+        stream.writeInt(location.offset);
+        stream.writeInt(location.length);
+      }
+    });
+  }
+}
+
+
+/**
+ * A single index file in-memory presentation.
+ */
+class IndexNode {
+  final AnalysisContext context;
+
+  final ElementCodec _elementCodec;
+
+  Map<RelationKeyData, List<LocationData>> _relations = {};

[Paul Berry, 2014/06/20 15:46:01]

Should this be a hashmap?

[scheglov, 2014/06/20 16:16:56]

Done.

+
+  final RelationshipCodec _relationshipCodec;
+
+  IndexNode(this.context, this._elementCodec, this._relationshipCodec);
+
+  /**
+   * Returns number of locations in this node.
+   */
+  int get locationCount {
+    int locationCount = 0;
+    for (List<LocationData> locations in _relations.values) {
+      locationCount += locations.length;
+    }
+    return locationCount;
+  }
+
+  /**
+   * Returns the recorded relations.
+   */
+  Map<RelationKeyData, List<LocationData>> get relations => _relations;
+
+  /**
+   * Sets relations data. This method is used during loading data from a storage.
+   */
+  void set relations(Map<RelationKeyData, List<LocationData>> relations) {
+    this._relations.clear();
+    this._relations.addAll(relations);
+  }
+
+  /**
+   * Return the locations of the elements that have the given relationship with the given element.
+   *
+   * @param element the the element that has the relationship with the locations to be returned
+   * @param relationship the [Relationship] between the given element and the locations to be
+   *          returned
+   */
+  List<Location> getRelationships(Element element, Relationship relationship) {
+    // prepare key
+    RelationKeyData key = new RelationKeyData.forObject(_elementCodec,
+        _relationshipCodec, element, relationship);
+    // find LocationData(s)
+    List<LocationData> locationDatas = _relations[key];
+    if (locationDatas == null) {
+      return Location.EMPTY_ARRAY;
+    }
+    // convert to Location(s)
+    List<Location> locations = [];
+    for (LocationData locationData in locationDatas) {
+      Location location = locationData.getLocation(context, _elementCodec);
+      if (location != null) {
+        locations.add(location);
+      }
+    }
+    return new List.from(locations);

[Paul Berry, 2014/06/20 15:46:01]

"return locations;" should be sufficient.  There's no need to make a copy of the
list since it was freshly allocated in this function, so there are no other
references to it.

[scheglov, 2014/06/20 16:16:56]

Done.

+  }
+
+  /**
+   * Records that the given element and location have the given relationship.
+   *
+   * @param element the element that is related to the location
+   * @param relationship the [Relationship] between the element and the location
+   * @param location the [Location] where relationship happens
+   */
+  void recordRelationship(Element element, Relationship relationship,
+      Location location) {
+    RelationKeyData key = new RelationKeyData.forObject(_elementCodec,
+        _relationshipCodec, element, relationship);
+    // prepare LocationData(s)
+    List<LocationData> locationDatas = _relations[key];
+    if (locationDatas == null) {
+      locationDatas = [];
+      _relations[key] = locationDatas;
+    }
+    // add new LocationData
+    locationDatas.add(new LocationData.forObject(_elementCodec, location));
+  }
+}
+
+
+class IntArrayToIntMap {
+  // TODO(scheglov) consider using Int32List
+  final Map<List<int>, int> map = new HashMap<List<int>, int>(equals:
+      _intArrayEquals, hashCode: _intArrayHashCode);
+
+  IntArrayToIntMap(int initialCapacity, double loadFactor);
+
+  int get(List<int> key, int defaultValue) {
+    int value = map[key];
+    if (value == null) {
+      return defaultValue;
+    }
+    return value;
+  }
+
+  void put(List<int> key, int value) {
+    map[key] = value;
+  }
+
+  static bool _intArrayEquals(List<int> a, List<int> b) {
+    int length = a.length;
+    if (length != b.length) {
+      return false;
+    }
+    for (int i = 0; i < length; i++) {
+      if (a[i] != b[i]) {
+        return false;
+      }
+    }
+    return true;
+  }
+
+  static int _intArrayHashCode(List<int> key) {
+    return key.fold(0, (int result, int item) {
+      return 31 * result + item;
+    });
+  }
+}
+
+
+class IntToIntSetMap {
+  // TODO(scheglov) consider using Int32List
+  final Map<int, List<int>> _map = new HashMap<int, List<int>>();

[Paul Berry, 2014/06/20 15:46:01]

Would it be better to use Map<int, HashSet<int>>?  This would make add()
asymptotically faster, since it wouldn't need to scan the entire list to see if
the value was already present.  (However, it would probably be slower if most of
the sets were small).

Another advantage is that we could change the return type of get() to Set<int>,
which would more clearly express the intent.

[scheglov, 2014/06/20 16:16:56]

It is intentional.
At least in Java maps and sets are pretty expensive.
Discussed offline.

+  int _size = 0;
+
+  IntToIntSetMap(int initialCapacity, double loadFactor);
+
+  int get length => _size;
+
+  void add(int key, int value) {
+    List<int> values = _map[key];
+    if (values == null) {
+      values = new List<int>();
+      _map[key] = values;
+    }
+    if (values.indexOf(value) == -1) {
+      values.add(value);
+      _size++;
+    }
+  }
+
+  void clear() {
+    _map.clear();
+    _size = 0;
+  }
+
+  List<int> get(int key) {
+    List<int> values = _map[key];
+    if (values == null) {
+      values = <int>[];
+    }
+    return values;
+  }
+}
+
+
+/**
+ * A container with information about a [Location].
+ */
+class LocationData {
+  final int elementId;
+  final int length;
+  final int offset;
+
+  LocationData.forData(this.elementId, this.offset, this.length);
+
+  LocationData.forObject(ElementCodec elementCodec, Location location)
+      : elementId = elementCodec.encode(location.element),
+        offset = location.offset,
+        length = location.length;
+
+  @override
+  int get hashCode {
+    return 31 * (31 * elementId + offset) + length;
+  }
+
+  @override
+  bool operator ==(Object obj) {
+    if (obj is! LocationData) {
+      return false;
+    }
+    LocationData other = obj;
+    return other.elementId == elementId && other.offset == offset &&
+        other.length == length;
+  }
+
+  /**
+   * Returns a {@link Location} that is represented by this {@link LocationData}.
+   */
+  Location getLocation(AnalysisContext context, ElementCodec elementCodec) {
+    Element element = elementCodec.decode(context, elementId);
+    if (element == null) {
+      return null;
+    }
+    return new Location(element, offset, length);
+  }
+}
+
+
+/**
+ * A manager for [IndexNode]s.
+ */
+abstract class NodeManager {
+  /**
+   * The shared {@link ContextCodec} instance.
+   */
+  ContextCodec get contextCodec;
+
+  /**
+   * The shared {@link ElementCodec} instance.
+   */
+  ElementCodec get elementCodec;
+
+  /**
+   * A number of locations in all nodes.
+   */
+  int get locationCount;
+
+  /**
+   * The shared {@link StringCodec} instance.
+   */
+  StringCodec get stringCodec;
+
+  /**
+   * Removes all nodes.
+   */
+  void clear();
+
+  /**
+   * Returns the {@link IndexNode} with the given name, {@code null} if not found.
+   */
+  Future<IndexNode> getNode(String name);
+
+  /**
+   * Returns a new {@link IndexNode}.
+   */
+  IndexNode newNode(AnalysisContext context);
+
+  /**
+   * Associates the given {@link IndexNode} with the given name.
+   */
+  void putNode(String name, IndexNode node);
+
+  /**
+   * Removes the {@link IndexNode} with the given name.
+   */
+  void removeNode(String name);
+}
+
+
+/**
+ * An [Element] to [Location] relation key.
+ */
+class RelationKeyData {
+  final int elementId;
+  final int relationshipId;
+
+  RelationKeyData.forData(this.elementId, this.relationshipId);
+
+  RelationKeyData.forObject(ElementCodec elementCodec,
+      RelationshipCodec relationshipCodec, Element element, Relationship relationship)
+      : elementId = elementCodec.encode(element),
+        relationshipId = relationshipCodec.encode(relationship);
+
+  @override
+  int get hashCode {
+    return 31 * elementId + relationshipId;
+  }
+
+  @override
+  bool operator ==(Object obj) {
+    if (obj is! RelationKeyData) {
+      return false;
+    }
+    RelationKeyData other = obj;
+    return other.elementId == elementId && other.relationshipId ==
+        relationshipId;
+  }
+}
+
+
+/**
+ * A helper that encodes/decodes [Relationship]s to/from integers.
+ */
+class RelationshipCodec {
+  final StringCodec _stringCodec;
+
+  RelationshipCodec(this._stringCodec);
+
+  Relationship decode(int idIndex) {
+    String id = _stringCodec.decode(idIndex);
+    return Relationship.getRelationship(id);
+  }
+
+  int encode(Relationship relationship) {
+    String id = relationship.identifier;
+    return _stringCodec.encode(id);
+  }
+}
+
+
+/**
+ * An [IndexStore] which keeps index information in separate nodes for each unit.
+ */
+class SplitIndexStore implements IndexStore {
+  /**
+   * The [ContextCodec] to encode/decode [AnalysisContext]s.
+   */
+  ContextCodec _contextCodec;
+
+  /**
+   * Information about "universe" elements. We need to keep them together to avoid loading of all
+   * index nodes.
+   *
+   * Order of keys: contextId, nodeId, Relationship.
+   */
+  Map<int, Map<int, Map<Relationship, List<LocationData>>>>
+      _contextNodeRelations = {};

[Paul Berry, 2014/06/20 15:46:01]

1. Would a HashMap be better here?

2. Initializing this to <int, Map<int, Map<Relationship, List<LocationData>>>>{}
is safer, because it will cause the VM to do more run-time type checking (in
checked mode it will verify that every entry added to the map has the correct
type).

Similar comments apply to _contextToLibraryToUnits and _contextoUnitToLibraries.

[scheglov, 2014/06/20 16:16:56]

Done.

+
+  /**
+   * The mapping of library [Source] to the [Source]s of part units.
+   */
+  Map<AnalysisContext, Map<Source, Set<Source>>> _contextToLibraryToUnits = {};
+
+  /**
+   * The mapping of unit [Source] to the [Source]s of libraries it is used in.
+   */
+  Map<AnalysisContext, Map<Source, Set<Source>>> _contextToUnitToLibraries = {};
+
+  int _currentContextId = 0;
+
+  IndexNode _currentNode;
+
+  String _currentNodeName;
+
+  int _currentNodeNameId = 0;
+
+  /**
+   * The [ElementCodec] to encode/decode [Element]s.
+   */
+  ElementCodec _elementCodec;
+
+  /**
+   * A table mapping element names to the node names that may have relations with elements with
+   * these names.
+   */
+  IntToIntSetMap _nameToNodeNames = new IntToIntSetMap(10000, 0.75);
+
+  /**
+   * The [NodeManager] to get/put [IndexNode]s.
+   */
+  final NodeManager _nodeManager;
+
+  /**
+   * The set of known [Source]s.
+   */
+  Set<Source> _sources = new Set();

[Paul Berry, 2014/06/20 15:46:01]

Would HashSet be better?

[scheglov, 2014/06/20 16:16:56]

Done.

+
+  /**
+   * The [StringCodec] to encode/decode [String]s.
+   */
+  StringCodec _stringCodec;
+
+  SplitIndexStore(this._nodeManager) {
+    this._contextCodec = _nodeManager.contextCodec;
+    this._elementCodec = _nodeManager.elementCodec;
+    this._stringCodec = _nodeManager.stringCodec;
+  }
+
+  @override
+  String get statistics =>
+      "[${_nodeManager.locationCount} locations, ${_sources.length} sources, ${_nameToNodeNames.length} names]";
+
+  @override
+  bool aboutToIndexDart(AnalysisContext context,
+      CompilationUnitElement unitElement) {
+    context = _unwrapContext(context);
+    // may be already disposed in other thread
+    if (context.isDisposed) {
+      return false;
+    }
+    // validate unit
+    if (unitElement == null) {
+      return false;
+    }
+    LibraryElement libraryElement = unitElement.library;
+    if (libraryElement == null) {
+      return false;
+    }
+    CompilationUnitElement definingUnitElement =
+        libraryElement.definingCompilationUnit;
+    if (definingUnitElement == null) {
+      return false;
+    }
+    // prepare sources
+    Source library = definingUnitElement.source;
+    Source unit = unitElement.source;
+    // special handling for the defining library unit
+    if (unit == library) {
+      // prepare new parts
+      Set<Source> newParts = new Set();
+      for (CompilationUnitElement part in libraryElement.parts) {
+        newParts.add(part.source);
+      }
+      // prepare old parts
+      Map<Source, Set<Source>> libraryToUnits =
+          _contextToLibraryToUnits[context];
+      if (libraryToUnits == null) {
+        libraryToUnits = {};
+        _contextToLibraryToUnits[context] = libraryToUnits;
+      }
+      Set<Source> oldParts = libraryToUnits[library];
+      // check if some parts are not in the library now
+      if (oldParts != null) {
+        Set<Source> noParts = oldParts.difference(newParts);
+        for (Source noPart in noParts) {
+          _removeLocations(context, library, noPart);
+        }
+      }
+      // remember new parts
+      libraryToUnits[library] = newParts;
+    }
+    // remember library/unit relations
+    _recordUnitInLibrary(context, library, unit);
+    _recordLibraryWithUnit(context, library, unit);
+    _sources.add(library);
+    _sources.add(unit);
+    // prepare node
+    String libraryName = library.fullName;
+    String unitName = unit.fullName;
+    int libraryNameIndex = _stringCodec.encode(libraryName);
+    int unitNameIndex = _stringCodec.encode(unitName);
+    _currentNodeName = "${libraryNameIndex}_${unitNameIndex}.index";
+    _currentNodeNameId = _stringCodec.encode(_currentNodeName);
+    _currentNode = _nodeManager.newNode(context);
+    _currentContextId = _contextCodec.encode(context);
+    // remove Universe information for the current node
+    for (Map<int, dynamic> nodeRelations in _contextNodeRelations.values) {
+      nodeRelations.remove(_currentNodeNameId);
+    }
+    // done
+    return true;
+  }
+
+  @override
+  bool aboutToIndexHtml(AnalysisContext context, HtmlElement htmlElement) {
+    context = _unwrapContext(context);
+    // may be already disposed in other thread
+    if (context.isDisposed) {
+      return false;
+    }
+    // remove locations
+    Source source = htmlElement.source;
+    _removeLocations(context, null, source);
+    // remember library/unit relations
+    _recordUnitInLibrary(context, null, source);
+    // prepare node
+    String sourceName = source.fullName;
+    int sourceNameIndex = _stringCodec.encode(sourceName);
+    _currentNodeName = "${sourceNameIndex}.index";
+    _currentNodeNameId = _stringCodec.encode(_currentNodeName);
+    _currentNode = _nodeManager.newNode(context);
+    return true;
+  }
+
+  @override
+  void clear() {
+    _nodeManager.clear();
+    _nameToNodeNames.clear();
+  }
+
+  @override
+  void doneIndex() {
+    if (_currentNode != null) {
+      _nodeManager.putNode(_currentNodeName, _currentNode);
+      _currentNodeName = null;
+      _currentNodeNameId = -1;
+      _currentNode = null;
+      _currentContextId = -1;
+    }
+  }
+
+  @override
+  List<Location> getRelationships(Element element, Relationship relationship) {
+    // TODO(scheglov) make IndexStore interface async
+    return <Location>[];
+  }
+
+  Future<List<Location>> getRelationshipsAsync(Element element,
+      Relationship relationship) {
+    // special support for UniverseElement
+    if (identical(element, UniverseElement.INSTANCE)) {
+      List<Location> locations = _getRelationshipsUniverse(relationship);
+      return new Future.value(locations);
+    }
+    // prepare node names
+    String name = _getElementName(element);
+    int nameId = _stringCodec.encode(name);
+    List<int> nodeNameIds = _nameToNodeNames.get(nameId);
+    // prepare Future(s) for reading each IndexNode
+    List<Future<List<Location>>> nodeFutures = <Future<List<Location>>>[];
+    for (int nodeNameId in nodeNameIds) {
+      String nodeName = _stringCodec.decode(nodeNameId);
+      Future<IndexNode> nodeFuture = _nodeManager.getNode(nodeName);
+      Future<List<Location>> locationsFuture = nodeFuture.then((node) {
+        if (node == null) {
+          // TODO(scheglov) remove node
+          return Location.EMPTY_ARRAY;
+        }
+        return node.getRelationships(element, relationship);
+      });
+      nodeFutures.add(locationsFuture);
+    }
+    // return Future that merges separate IndexNode Location(s)
+    return Future.wait(nodeFutures).then((List<List<Location>> locationsList) {
+      List<Location> allLocations = <Location>[];
+      for (List<Location> locations in locationsList) {
+        allLocations.addAll(locations);
+      }
+      return allLocations;
+    });
+  }
+
+  @override
+  void recordRelationship(Element element, Relationship relationship,
+      Location location) {
+    if (element == null || location == null) {
+      return;
+    }
+    // special support for UniverseElement
+    if (identical(element, UniverseElement.INSTANCE)) {
+      _recordRelationshipUniverse(relationship, location);
+      return;
+    }
+    // other elements
+    _recordNodeNameForElement(element);
+    _currentNode.recordRelationship(element, relationship, location);
+  }
+
+  @override
+  void removeContext(AnalysisContext context) {
+    context = _unwrapContext(context);
+    if (context == null) {
+      return;
+    }
+    // remove sources
+    removeSources(context, null);
+    // remove context information
+    _contextToLibraryToUnits.remove(context);
+    _contextToUnitToLibraries.remove(context);
+    _contextNodeRelations.remove(_contextCodec.encode(context));
+  }
+
+  @override
+  void removeSource(AnalysisContext context, Source source) {
+    context = _unwrapContext(context);
+    if (context == null) {
+      return;
+    }
+    // remove nodes for unit/library pairs
+    Map<Source, Set<Source>> unitToLibraries =
+        _contextToUnitToLibraries[context];
+    if (unitToLibraries != null) {
+      Set<Source> libraries = unitToLibraries.remove(source);
+      if (libraries != null) {
+        for (Source library in libraries) {
+          _removeLocations(context, library, source);
+        }
+      }
+    }
+    // remove nodes for library/unit pairs
+    Map<Source, Set<Source>> libraryToUnits = _contextToLibraryToUnits[context];
+    if (libraryToUnits != null) {
+      Set<Source> units = libraryToUnits.remove(source);
+      if (units != null) {
+        for (Source unit in units) {
+          _removeLocations(context, source, unit);
+        }
+      }
+    }
+  }
+
+  @override
+  void removeSources(AnalysisContext context, SourceContainer container) {
+    context = _unwrapContext(context);
+    if (context == null) {
+      return;
+    }
+    // remove nodes for unit/library pairs
+    Map<Source, Set<Source>> unitToLibraries =
+        _contextToUnitToLibraries[context];
+    if (unitToLibraries != null) {
+      List<Source> units = new List<Source>.from(unitToLibraries.keys);
+      for (Source source in units) {
+        if (container == null || container.contains(source)) {
+          removeSource(context, source);
+        }
+      }
+    }
+    // remove nodes for library/unit pairs
+    Map<Source, Set<Source>> libraryToUnits = _contextToLibraryToUnits[context];
+    if (libraryToUnits != null) {
+      List<Source> libraries = new List<Source>.from(libraryToUnits.keys);
+      for (Source source in libraries) {
+        if (container == null || container.contains(source)) {
+          removeSource(context, source);
+        }
+      }
+    }
+  }
+
+  String _getElementName(Element element) => element.name;
+
+  List<Location> _getRelationshipsUniverse(Relationship relationship) {
+    List<Location> locations = [];
+    _contextNodeRelations.forEach((contextId, contextRelations) {
+      AnalysisContext context = _contextCodec.decode(contextId);
+      if (context != null) {
+        for (Map<Relationship, List<LocationData>> nodeRelations in
+            contextRelations.values) {
+          List<LocationData> nodeLocations = nodeRelations[relationship];
+          if (nodeLocations != null) {
+            for (LocationData locationData in nodeLocations) {
+              Location location = locationData.getLocation(context,
+                  _elementCodec);
+              if (location != null) {
+                locations.add(location);
+              }
+            }
+          }
+        }
+      }
+    });
+    return new List.from(locations);

[Paul Berry, 2014/06/20 15:46:01]

Should be just "return locations;"

[scheglov, 2014/06/20 16:16:56]

Done.

+  }
+
+  void _recordLibraryWithUnit(AnalysisContext context, Source library,
+      Source unit) {
+    Map<Source, Set<Source>> libraryToUnits = _contextToLibraryToUnits[context];
+    if (libraryToUnits == null) {
+      libraryToUnits = {};
+      _contextToLibraryToUnits[context] = libraryToUnits;
+    }
+    Set<Source> units = libraryToUnits[library];
+    if (units == null) {
+      units = new Set();
+      libraryToUnits[library] = units;
+    }
+    units.add(unit);
+  }
+
+  void _recordNodeNameForElement(Element element) {
+    String name = _getElementName(element);
+    int nameId = _stringCodec.encode(name);
+    _nameToNodeNames.add(nameId, _currentNodeNameId);
+  }
+
+  void _recordRelationshipUniverse(Relationship relationship,
+      Location location) {
+    // in current context
+    Map<int, Map<Relationship, List<LocationData>>> nodeRelations =
+        _contextNodeRelations[_currentContextId];
+    if (nodeRelations == null) {
+      nodeRelations = {};
+      _contextNodeRelations[_currentContextId] = nodeRelations;
+    }
+    // in current node
+    Map<Relationship, List<LocationData>> relations =
+        nodeRelations[_currentNodeNameId];
+    if (relations == null) {
+      relations = {};
+      nodeRelations[_currentNodeNameId] = relations;
+    }
+    // for the given relationship
+    List<LocationData> locations = relations[relationship];
+    if (locations == null) {
+      locations = [];
+      relations[relationship] = locations;
+    }
+    // record LocationData
+    locations.add(new LocationData.forObject(_elementCodec, location));
+  }
+
+  void _recordUnitInLibrary(AnalysisContext context, Source library,
+      Source unit) {
+    Map<Source, Set<Source>> unitToLibraries =
+        _contextToUnitToLibraries[context];
+    if (unitToLibraries == null) {
+      unitToLibraries = {};
+      _contextToUnitToLibraries[context] = unitToLibraries;
+    }
+    Set<Source> libraries = unitToLibraries[unit];
+    if (libraries == null) {
+      libraries = new Set();
+      unitToLibraries[unit] = libraries;
+    }
+    libraries.add(library);
+  }
+
+  /**
+   * Removes locations recorded in the given library/unit pair.
+   */
+  void _removeLocations(AnalysisContext context, Source library, Source unit) {
+    // remove node
+    String libraryName = library != null ? library.fullName : null;
+    String unitName = unit.fullName;
+    int libraryNameIndex = _stringCodec.encode(libraryName);
+    int unitNameIndex = _stringCodec.encode(unitName);
+    String nodeName = "${libraryNameIndex}_${unitNameIndex}.index";
+    _nodeManager.removeNode(nodeName);
+    // remove source
+    _sources.remove(library);
+    _sources.remove(unit);
+  }
+
+  /**
+   * When logging is on, [AnalysisEngine] actually creates
+   * [InstrumentedAnalysisContextImpl], which wraps [AnalysisContextImpl] used to create
+   * actual [Element]s. So, in index we have to unwrap [InstrumentedAnalysisContextImpl]
+   * when perform any operation.
+   */
+  AnalysisContext _unwrapContext(AnalysisContext context) {
+    if (context is InstrumentedAnalysisContextImpl) {
+      context = (context as InstrumentedAnalysisContextImpl).basis;
+    }
+    return context;
+  }
+}
+
+
+/**
+ * A helper that encodes/decodes [String]s from/to integers.
+ */
+class StringCodec {
+  /**
+   * A table mapping names to their unique indices.
+   */
+  final Map<String, int> nameToIndex = {};
+
+  /**
+   * A table mapping indices to the corresponding strings.
+   */
+  List<String> _indexToName = [];
+
+  /**
+   * Returns the [String] that corresponds to the given index.
+   */
+  String decode(int index) => _indexToName[index];
+
+  /**
+   * Returns an unique index for the given [String].
+   */
+  int encode(String name) {
+    int index = nameToIndex[name];
+    if (index == null) {
+      index = _indexToName.length;
+      nameToIndex[name] = index;
+      _indexToName.add(name);
+    }
+    return index;
+  }
+}
+
+
+class _DataInputStream {
+  ByteData _byteData;
+  int _byteOffset = 0;
+
+  _DataInputStream(List<int> bytes) {
+    ByteBuffer buffer = new Uint8List.fromList(bytes).buffer;
+    _byteData = new ByteData.view(buffer);
+  }
+
+  int readInt() {
+    int result = _byteData.getInt32(_byteOffset);
+    _byteOffset += 4;
+    return result;
+  }
+}
+
+
+class _DataOutputStream {
+  BytesBuilder _buffer = new BytesBuilder();
+
+  Uint8List getBytes() {
+    return new Uint8List.fromList(_buffer.takeBytes());
+  }
+
+  void writeInt(int value) {
+    _buffer.addByte((value & 0xFF000000) >> 24);
+    _buffer.addByte((value & 0x00FF0000) >> 16);
+    _buffer.addByte((value & 0x0000FF00) >> 8);
+    _buffer.addByte(value & 0xFF);
+  }
+}