Add navigation support in plugins

pkg/analyzer_plugin/lib/src/utilities/navigation.dart

Index: pkg/analyzer_plugin/lib/src/utilities/navigation.dart
diff --git a/pkg/analyzer_plugin/lib/src/utilities/navigation.dart b/pkg/analyzer_plugin/lib/src/utilities/navigation.dart
new file mode 100644
index 0000000000000000000000000000000000000000..08560cba8995fee7b61604c801191387ec845e6b
--- /dev/null
+++ b/pkg/analyzer_plugin/lib/src/utilities/navigation.dart
@@ -0,0 +1,83 @@
+// Copyright (c) 2017, 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 'package:analyzer/src/generated/source.dart' show SourceRange;
+import 'package:analyzer_plugin/protocol/protocol_common.dart';
+import 'package:analyzer_plugin/utilities/navigation.dart';
+import 'package:analyzer_plugin/utilities/pair.dart';
+
+/**
+ * A concrete implementation of [NavigationCollector].
+ */
+class NavigationCollectorImpl implements NavigationCollector {
+  /**
+   * A list of navigation regions.
+   */
+  final List<NavigationRegion> regions = <NavigationRegion>[];
+  final Map<SourceRange, List<int>> regionMap = <SourceRange, List<int>>{};
+
+  /**
+   * All the unique targets referenced by [regions].
+   */
+  final List<NavigationTarget> targets = <NavigationTarget>[];
+  final Map<Pair<ElementKind, Location>, int> targetMap =
+      <Pair<ElementKind, Location>, int>{};
+
+  /**
+   * All the unique files referenced by [targets].
+   */
+  final List<String> files = <String>[];
+  final Map<String, int> fileMap = <String, int>{};
+
+  @override
+  void addRegion(
+      int offset, int length, ElementKind targetKind, Location targetLocation) {
+    SourceRange range = new SourceRange(offset, length);
+    // add new target
+    List<int> targets = regionMap.putIfAbsent(range, () => <int>[]);
+    int targetIndex = _addTarget(targetKind, targetLocation);
+    targets.add(targetIndex);
+  }
+
+  void createRegions() {
+    regionMap.forEach((range, targets) {
+      NavigationRegion region =
+          new NavigationRegion(range.offset, range.length, targets);
+      regions.add(region);
+    });
+    regions.sort((NavigationRegion first, NavigationRegion second) {
+      return first.offset - second.offset;
+    });
+  }
+
+  int _addFile(String file) {
+    int index = fileMap[file];
+    if (index == null) {
+      index = files.length;
+      files.add(file);
+      fileMap[file] = index;
+    }
+    return index;
+  }
+
+  int _addTarget(ElementKind kind, Location location) {
+    var pair = new Pair<ElementKind, Location>(kind, location);
+    int index = targetMap[pair];
+    if (index == null) {
+      String file = location.file;
+      int fileIndex = _addFile(file);
+      index = targets.length;
+      NavigationTarget target = new NavigationTarget(
+          kind,
+          fileIndex,
+          location.offset,
+          location.length,
+          location.startLine,
+          location.startColumn);
+      targets.add(target);
+      targetMap[pair] = index;
+    }
+    return index;
+  }
+}