Initial new index implementation.

pkg/analysis_server/lib/src/services/index2/index2.dart

Index: pkg/analysis_server/lib/src/services/index2/index2.dart
diff --git a/pkg/analysis_server/lib/src/services/index2/index2.dart b/pkg/analysis_server/lib/src/services/index2/index2.dart
new file mode 100644
index 0000000000000000000000000000000000000000..55feaea60f627d86565e169f98ffba9a6df38eef
--- /dev/null
+++ b/pkg/analysis_server/lib/src/services/index2/index2.dart
@@ -0,0 +1,268 @@
+// 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.
+
+import 'dart:async';
+
+import 'package:analyzer/dart/ast/ast.dart';
+import 'package:analyzer/dart/element/element.dart';
+import 'package:analyzer/src/generated/source.dart';
+import 'package:analyzer/src/summary/format.dart';
+import 'package:analyzer/src/summary/idl.dart';
+import 'package:analyzer/src/summary/index_unit.dart';
+import 'package:collection/collection.dart';
+
+/**
+ * Interface for storing and requesting relations.
+ */
+class Index2 {
+  final PackageIndexStore _store;
+
+  Index2(this._store);
+
+  /**
+   * Complete with a list of locations where the given [element] has relation
+   * of the given [kind].
+   */
+  Future<List<Location>> getRelations(
+      Element element, IndexRelationKind kind) async {
+    List<Location> locations = <Location>[];
+    Iterable<PackageIndexId> ids = await _store.getIds();
+    for (PackageIndexId id in ids) {
+      PackageIndex index = await _store.getIndex(id);
+      _PackageIndexRequester requester = new _PackageIndexRequester(index);
+      List<Location> packageLocations = requester.getRelations(element, kind);
+      locations.addAll(packageLocations);
+    }
+    return locations;
+  }
+
+  /**
+   * Index the given fully resolved [unit].
+   */
+  void indexUnit(CompilationUnit unit) {
+    PackageIndexAssembler assembler = new PackageIndexAssembler();
+    assembler.index(unit);
+    PackageIndexBuilder indexBuilder = assembler.assemble();
+    String unitLibraryUri = unit.element.library.source.uri.toString();
+    String unitUnitUri = unit.element.source.uri.toString();
+    _store.putIndex(unitLibraryUri, unitUnitUri, indexBuilder);
+  }
+}
+
+/**
+ * Information about location of a single relation in the index.
+ *
+ * The location is expressed as a library specific unit containing the index
+ * relation, offset within this [Source] and  length.
+ *
+ * Clients may not extend, implement or mix-in this class.
+ */
+class Location {
+  /**
+   * The URI of the source of the library containing this location.
+   */
+  final String libraryUri;
+
+  /**
+   * The URI of the source of the unit containing this location.
+   */
+  final String unitUri;
+
+  /**
+   * The offset of this location within the [unitUri].
+   */
+  final int offset;
+
+  /**
+   * The length of this location.
+   */
+  final int length;
+
+  /**
+   * Is `true` if this location is qualified.
+   */
+  final bool isQualified;
+
+  Location(this.libraryUri, this.unitUri, this.offset, this.length,
+      this.isQualified);
+
+  @override
+  String toString() => 'Location{librarySourceUri: $libraryUri, '
+      'unitSourceUri: $unitUri, offset: $offset, length: $length, '
+      'isQualified: $isQualified}';
+}
+
+/**
+ * Opaque identifier of a [PackageIndex].
+ */
+abstract class PackageIndexId {}
+
+/**
+ * Storage of [PackageIndex] objects.
+ */
+abstract class PackageIndexStore {
+  /**
+   * Complete with identifiers of all [PackageIndex] objects.
+   */
+  Future<Iterable<PackageIndexId>> getIds();
+
+  /**
+   * Complete with the [PackageIndex] with the given [id].
+   */
+  Future<PackageIndex> getIndex(PackageIndexId id);
+
+  /**
+   * Put the given [indexBuilder] into the store.
+   */
+  void putIndex(String unitLibraryUri, String unitUnitUri,
+      PackageIndexBuilder indexBuilder);
+}
+
+/**
+ * Helper for requesting information from a single [PackageIndex].
+ */
+class _PackageIndexRequester {
+  final PackageIndex index;
+
+  _PackageIndexRequester(this.index);
+
+  /**
+   * Return the [element]'s identifier in the [index] or `null` if the
+   * [element] is not referenced in the [index].
+   */
+  int findElementId(Element element) {
+    int unitId = getUnitId(element);
+    int offset = element.nameOffset;
+    if (element is LibraryElement || element is CompilationUnitElement) {
+      offset = 0;
+    }
+    IndexSyntheticElementKind kind =
+        PackageIndexAssembler.getIndexElementKind(element);
+    for (int elementId = 0;
+        elementId < index.elementUnits.length;
+        elementId++) {
+      if (index.elementUnits[elementId] == unitId &&
+          index.elementOffsets[elementId] == offset &&
+          index.elementKinds[elementId] == kind) {
+        return elementId;
+      }
+    }
+    return null;
+  }
+
+  /**
+   * Complete with a list of locations where the given [element] has relation
+   * of the given [kind].
+   */
+  List<Location> getRelations(Element element, IndexRelationKind kind) {
+    int elementId = findElementId(element);
+    if (elementId == null) {
+      return const <Location>[];
+    }
+    List<Location> locations = <Location>[];
+    for (UnitIndex unitIndex in index.units) {
+      _UnitIndexRequester requester = new _UnitIndexRequester(this, unitIndex);
+      List<Location> unitLocations = requester.getRelations(elementId, kind);
+      locations.addAll(unitLocations);
+    }
+    return locations;
+  }
+
+  /**
+   * Return the identifier of [str] in the [index] or `-1` if [str] is not used
+   * in the [index].
+   */
+  int getStringId(String str) {
+    return index.strings.indexOf(str);
+  }
+
+  /**
+   * Return the identifier of the [CompilationUnitElement] containing the
+   * [element] in the [index] or `-1` if not found.
+   */
+  int getUnitId(Element element) {
+    CompilationUnitElement unitElement =
+        PackageIndexAssembler.getUnitElement(element);
+    int libraryUriId = getUriId(unitElement.library.source.uri);
+    int unitUriId = getUriId(unitElement.source.uri);
+    for (int i = 0; i < index.unitLibraryUris.length; i++) {
+      if (index.unitLibraryUris[i] == libraryUriId &&
+          index.unitUnitUris[i] == unitUriId) {
+        return i;
+      }
+    }
+    return -1;
+  }
+
+  /**
+   * Return the URI of the library source of the library specific [unit].
+   */
+  String getUnitLibraryUri(int unit) {
+    int id = index.unitLibraryUris[unit];
+    return index.strings[id];
+  }
+
+  /**
+   * Return the URI of the unit source of the library specific [unit].
+   */
+  String getUnitUnitUri(int unit) {
+    int id = index.unitUnitUris[unit];
+    return index.strings[id];
+  }
+
+  /**
+   * Return the identifier of the [uri] in the [index] or `-1` if the [uri] is
+   * not used in the [index].
+   */
+  int getUriId(Uri uri) {
+    String str = uri.toString();
+    return getStringId(str);
+  }
+}
+
+/**
+ * Helper for requesting information from a single [UnitIndex].
+ */
+class _UnitIndexRequester {
+  final _PackageIndexRequester packageRequester;
+  final UnitIndex unitIndex;
+
+  _UnitIndexRequester(this.packageRequester, this.unitIndex);
+
+  /**
+   * Return a list of locations where an element with the given [elementId] has
+   * relation of the given [kind].
+   */
+  List<Location> getRelations(int elementId, IndexRelationKind kind) {
+    // Find a usage of the element.
+    int i = binarySearch(unitIndex.usedElements, elementId);
+    if (i == -1) {
+      return const <Location>[];
+    }
+    // Find the first usage of the element.
+    while (i > 0 && unitIndex.usedElements[i - 1] == elementId) {
+      i--;
+    }
+    // Create locations for every usage of the element.
+    List<Location> locations = <Location>[];
+    String unitLibraryUri = null;
+    String unitUnitUri = null;
+    for (;
+        i < unitIndex.usedElements.length &&
+            unitIndex.usedElements[i] == elementId;
+        i++) {
+      if (unitIndex.usedElementKinds[i] == kind) {
+        unitLibraryUri ??= packageRequester.getUnitLibraryUri(unitIndex.unit);
+        unitUnitUri ??= packageRequester.getUnitUnitUri(unitIndex.unit);
+        locations.add(new Location(
+            unitLibraryUri,
+            unitUnitUri,
+            unitIndex.usedElementOffsets[i],
+            unitIndex.usedElementLengths[i],
+            unitIndex.usedElementIsQualifiedFlags[i]));
+      }
+    }
+    return locations;
+  }
+}