Improve performance by not doing binary searches.

Normally getting the line and column of a SpanScanner or a
SourceLocation needs a binary search through all the line endings in the
source file. This CL avoids those searches by using an eager SpanScanner
which does extra computation to track its current line and column
position, and storing the line and column directly on _SimpleKey
objects.

See dart-lang/yaml#12

R=rnystrom@google.com

Review URL: https://codereview.chromium.org//1325133002 .

pkgs/yaml/lib/src/scanner.dart

diff --git a/pkgs/yaml/lib/src/scanner.dart b/pkgs/yaml/lib/src/scanner.dart
index 512d72e..2e02a8f 100644
--- a/pkgs/yaml/lib/src/scanner.dart
+++ b/pkgs/yaml/lib/src/scanner.dart
@@ -292,7 +292,7 @@
   ///
   /// [sourceUrl] can be a String or a [Uri].
   Scanner(String source, {sourceUrl})
-      : _scanner = new SpanScanner(source, sourceUrl: sourceUrl);
+      : _scanner = new SpanScanner.eager(source, sourceUrl: sourceUrl);
 
   /// Consumes and returns the next token.
   Token scan() {
@@ -485,7 +485,7 @@
       // everything but multiline simple keys in a block context.
       if (!_inBlockContext) continue;
 
-      if (key.location.line == _scanner.line) continue;
+      if (key.line == _scanner.line) continue;
 
       if (key.required) {
         throw new YamlException("Expected ':'.", _scanner.emptySpan);
@@ -513,6 +513,8 @@
     _removeSimpleKey();
     _simpleKeys[_simpleKeys.length - 1] = new _SimpleKey(
         _tokensParsed + _tokens.length,
+        _scanner.line,
+        _scanner.column,
         _scanner.location,
         required: required);
   }
@@ -660,7 +662,7 @@
       _rollIndent(
           _scanner.column,
           TokenType.BLOCK_SEQUENCE_START,
-          _scanner.emptySpan.start);
+          _scanner.location);
     } else {
       // It is an error for the '-' indicator to occur in the flow context, but
       // we let the Parser detect and report it because it's able to point to
@@ -683,7 +685,7 @@
       _rollIndent(
           _scanner.column,
           TokenType.BLOCK_MAPPING_START,
-          _scanner.emptySpan.start);
+          _scanner.location);
     }
 
     // Simple keys are allowed after `?` in a block context.
@@ -703,7 +705,7 @@
       // In the block context, we may need to add the
       // [TokenType.BLOCK_MAPPING_START] token.
       _rollIndent(
-          simpleKey.location.column,
+          simpleKey.column,
           TokenType.BLOCK_MAPPING_START,
           simpleKey.location,
           tokenNumber: simpleKey.tokenNumber);
@@ -1639,10 +1641,23 @@
   /// no longer on the current line.
   final SourceLocation location;
 
+  /// The line on which the key appears.
+  ///
+  /// We could get this from [location], but that requires a binary search
+  /// whereas this is O(1).
+  final int line;
+
+  /// The column on which the key appears.
+  ///
+  /// We could get this from [location], but that requires a binary search
+  /// whereas this is O(1).
+  final int column;
+
   /// Whether this key must exist for the document to be scanned.
   final bool required;
 
-  _SimpleKey(this.tokenNumber, this.location, {bool required})
+  _SimpleKey(this.tokenNumber, this.line, this.column, this.location,
+          {bool required})
       : required = required;
 }
 

pkgs/yaml/pubspec.yaml

diff --git a/pkgs/yaml/pubspec.yaml b/pkgs/yaml/pubspec.yaml
index a25faa6..618f82b 100644
--- a/pkgs/yaml/pubspec.yaml
+++ b/pkgs/yaml/pubspec.yaml
@@ -4,11 +4,12 @@
 homepage: https://github.com/dart-lang/yaml
 description: A parser for YAML.
 dependencies:
+  charcode: "^1.1.0"
   collection: ">=1.1.0 <2.0.0"
   path: ">=1.2.0 <2.0.0"
-  string_scanner: ">=0.1.3 <0.2.0"
+  string_scanner: "^0.1.4"
   source_span: ">=1.0.0 <2.0.0"
 dev_dependencies:
   test: ">=0.12.0 <0.13.0"
 environment:
-  sdk: '>=1.5.0 <2.0.0'
+  sdk: '>=1.8.0 <2.0.0'