Use FastUri instead of Uri in analyzer.

pkg/analyzer/lib/src/util/fast_uri.dart

Index: pkg/analyzer/lib/src/util/fast_uri.dart
diff --git a/pkg/analyzer/lib/src/util/fast_uri.dart b/pkg/analyzer/lib/src/util/fast_uri.dart
new file mode 100644
index 0000000000000000000000000000000000000000..5db10540be8123dd1f81927dcb63af7eca6b4363
--- /dev/null
+++ b/pkg/analyzer/lib/src/util/fast_uri.dart
@@ -0,0 +1,238 @@
+// 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:collection';
+
+/**
+ * Implementation of [Uri] that understands only a limited set of valid
+ * URI formats, but works fast. In practice Dart code almost always uses such
+ * limited URI format, so almost always can be processed fast.
+ */
+class FastUri implements Uri {
+  static HashMap<String, Uri> _cache = new HashMap<String, Uri>();
+
+  final String _text;
+  final String _scheme;
+  final String _path;
+  final List<int> _pathSegmentStarts;

[Paul Berry, 2016/05/20 16:18:11]

A doc comment would be helpful here to explain the following subtleties:

- Starts are character indices into [_text] (not [_path], as one might guess).

- The indices in this list point to '/'s, not to the path components themselves
(i.e. for 'foo/bar/baz', the starts are [3, 7], not [4, 8] as I originally
guessed).  Perhaps a better name for this variable would be `_slashIndices` or
something.

- If the path contains two slashes in a row, both slashes are included (even
though a leading '//' is dropped from _path--not sure if this was intentional or
not).

- If the path ends in '/', the final '/' is considered a path segment start.

However, having said all that, it looks like the only element of
[_pathSegmentStarts] that is actually used is the last element.  Consider
changing to an int called `_lastSlashIndex`.

[scheglov, 2016/05/20 16:47:23]

Done.

+
+  /**
+   * The cached hashcode.
+   */
+  int _hashCode;
+
+  Uri _cachedFallbackUri;

[Paul Berry, 2016/05/20 16:18:11]

Seeing the word "fallback" caused me to make an incorrect assumption about this
code: I assumed that it implemented the full functionality of [Uri]; it simply
had a faster implementation of the common use cases.  However, now I see that in
fact the purpose of this field is to allow us to make use of [Uri] for the
methods that are more complex and less in need of a fast implementation.

A doc comment would really have helped make this clearer.  Perhaps something
like "Full [Uri] object computed on demand; we fall back to this for some of the
more complex methods of [Uri] that are less in need of a fast implementation."

[scheglov, 2016/05/20 16:47:23]

Done.

+
+  FastUri(this._text, this._scheme, this._path, this._pathSegmentStarts);
+
+  @override
+  String get authority => '';
+
+  @override
+  UriData get data => null;
+
+  @override
+  String get fragment => '';
+
+  @override
+  bool get hasAbsolutePath => path.startsWith('/');
+
+  @override
+  bool get hasAuthority => false;
+
+  @override
+  bool get hasEmptyPath => _path.isEmpty;
+
+  @override
+  bool get hasFragment => false;
+
+  @override
+  int get hashCode {
+    _hashCode ??= (scheme.hashCode * 31 + path.hashCode) & 0x3FFFFFFF;
+    return _hashCode;
+  }
+
+  @override
+  bool get hasPort => false;
+
+  @override
+  bool get hasQuery => false;
+
+  @override
+  bool get hasScheme => _scheme.isNotEmpty;
+
+  @override
+  String get host => '';
+
+  @override
+  bool get isAbsolute => hasScheme;
+
+  @override
+  String get origin => _fallbackUri.origin;
+
+  @override
+  String get path => _path;
+
+  @override
+  List<String> get pathSegments => _fallbackUri.pathSegments;
+
+  @override
+  int get port => 0;
+
+  @override
+  String get query => '';
+
+  @override
+  Map<String, String> get queryParameters => const <String, String>{};
+
+  @override
+  Map<String, List<String>> get queryParametersAll =>
+      const <String, List<String>>{};
+
+  @override
+  String get scheme => _scheme;
+
+  @override
+  String get userInfo => '';
+
+  Uri get _fallbackUri => _cachedFallbackUri ??= Uri.parse(_text);
+
+  @override
+  bool operator ==(other) {
+    if (other is Uri) {
+      if (other is FastUri) {
+        return _text == other._text;
+      }
+      return _fallbackUri == other;
+    }
+    return false;
+  }
+
+  @override
+  Uri normalizePath() {
+    return this;
+  }
+
+  @override
+  Uri removeFragment() {
+    return this;
+  }
+
+  @override
+  Uri replace(
+      {String scheme,
+      String userInfo,
+      String host,
+      int port,
+      String path,
+      Iterable<String> pathSegments,
+      String query,
+      Map<String, dynamic> queryParameters,
+      String fragment}) {
+    return _fallbackUri.replace(
+        scheme: scheme,
+        userInfo: userInfo,
+        host: host,
+        port: port,
+        path: path,
+        pathSegments: pathSegments,
+        query: query,
+        queryParameters: queryParameters,
+        fragment: fragment);
+  }
+
+  @override
+  Uri resolve(String reference) {
+    // TODO: maybe implement faster
+    return _fallbackUri.resolve(reference);
+  }
+
+  @override
+  Uri resolveUri(Uri reference) {
+    if (reference.hasScheme) {
+      return reference;
+    }
+    String refPath = reference.path;
+    if (refPath.startsWith('./')) {
+      refPath = refPath.substring(2);
+    }
+    if (refPath.startsWith('../') || refPath.contains('/../') || refPath.contains('/./')) {
+      Uri slowResult = _fallbackUri.resolveUri(reference);
+      return FastUri.parse(slowResult.toString());
+    }
+    String newText = _text.substring(0, _pathSegmentStarts.last + 1) + refPath;

[Paul Berry, 2016/05/20 16:18:11]

Bug: this will throw an exception if the URI does not contain any '/'
characters, because [_pathSegmentStarts] will be empty.

[scheglov, 2016/05/20 16:47:23]

Fixed.

+    return FastUri.parse(newText);
+  }
+
+  @override
+  String toFilePath({bool windows}) {
+    return _fallbackUri.toFilePath(windows: windows);
+  }
+
+  @override
+  String toString() => _text;
+
+  static Uri parse(String text) {

[Paul Berry, 2016/05/20 16:18:11]

A doc comment would be helpful here too.  In particular, I don't know whether
this method supports the full URI syntax, or just a subset of it.  (I believe it
supports the full URI syntax because of the call to Uri.parse, but that's not
obvious without reading the implementation, and based on comments alone I would
have assumed the opposite).

Also the doc comment should mention that the function is internally memoized, so
that clients aren't tempted to perform redundant memoization.

[scheglov, 2016/05/20 16:47:23]

Done.

+    Uri uri = _cache[text];
+    if (uri == null) {
+      _UriData data = _parse(text);
+      if (data == null) {
+        uri = Uri.parse(text);
+      } else {
+        uri = new FastUri(text, data.scheme, data.path, data.pathSegmentStarts);
+      }
+      _cache[text] = uri;
+    }
+    return uri;
+  }
+
+  static bool _isAlphabetic(int char) {
+    return char >= 'A'.codeUnitAt(0) && char <= 'Z'.codeUnitAt(0) ||
+        char >= 'a'.codeUnitAt(0) && char <= 'z'.codeUnitAt(0);
+  }
+
+  static bool _isDigit(int char) {
+    return char >= '0'.codeUnitAt(0) && char <= '9'.codeUnitAt(0);
+  }
+
+  static _UriData _parse(String text) {

[Paul Berry, 2016/05/20 16:18:11]

A doc comment would be nice here as well, since there are some subtle behaviors.
 In particular, the comment should explain that if `text` uses URI features that
aren't supported by FastUri, `null` is returned.

[scheglov, 2016/05/20 16:47:23]

Done.

+    int schemeEnd = null;
+    int pathStart = 0;
+    List<int> pathSegmentStarts = <int>[];
+    for (int i = 0; i < text.length; i++) {
+      int char = text.codeUnitAt(i);
+      if (_isAlphabetic(char) ||
+          _isDigit(char) ||
+          char == '.'.codeUnitAt(0) ||
+          char == '-'.codeUnitAt(0) ||
+          char == '_'.codeUnitAt(0)) {
+        // Valid characters.
+      } else if (char == '/'.codeUnitAt(0)) {
+        pathSegmentStarts.add(i);
+      } else if (char == ':'.codeUnitAt(0)) {
+        if (schemeEnd != null) {
+          return null;
+        }
+        schemeEnd = i;
+        pathStart = i + 1;
+      } else {
+        return null;
+      }
+    }
+    String scheme = schemeEnd != null ? text.substring(0, schemeEnd) : '';
+    String path = text.substring(pathStart);
+    if (path.startsWith('//')) {
+      path = path.substring(2);
+    }
+    return new _UriData(scheme, path, pathSegmentStarts);

[Paul Berry, 2016/05/20 16:18:11]

It seems awkward to have to create this intermediate data structure when it will
be immediately consumed (and discarded) by the caller.

How about instead changing the return type of _parse to `Uri`, and replace this
line with `return new FastUri(text, scheme, path, pathSegmentStarts);`.  Then
the intermediate data structure can go away completely, and the `parse` function
above becomes a one-liner:

static Uri parse(String text) => _cache[text] ??= (_parse(text) ??
Uri.parse(text));

[scheglov, 2016/05/20 16:47:23]

Done.

+  }
+}
+
+class _UriData {
+  final String scheme;
+  final String path;
+  final List<int> pathSegmentStarts;
+
+  _UriData(this.scheme, this.path, this.pathSegmentStarts);
+}