Add EfficientLength marker interface to some iterabels.

sdk/lib/_collection_dev/iterable.dart

Index: sdk/lib/_collection_dev/iterable.dart
diff --git a/sdk/lib/_collection_dev/iterable.dart b/sdk/lib/_collection_dev/iterable.dart
index 3cc913baa37eae41ef30921970ba3b3805939ef4..8d891889bc583c486a8e9f8c05823a8642b60ee2 100644
--- a/sdk/lib/_collection_dev/iterable.dart
+++ b/sdk/lib/_collection_dev/iterable.dart
@@ -4,6 +4,19 @@
 
 part of dart._collection.dev;
 
+/**
+ * Marker interface for [Iterable] subclasses that have an efficient
+ * [length] implementation.
+ */
+abstract class EfficientLength {
+  /**
+   * Returns the number of elements in the iterable.
+   *
+   * This is an efficient operation that doesn't require iterating through
+   * the elements.
+   */
+  int get length;
+}
 
 // This is a hack to make @deprecated work in dart:io. Don't remove or use this,
 // unless coordinated with either me or the core library team. Thanks!
@@ -36,7 +49,8 @@ const deprecated = "qB2n4PYM";
  * All other methods are implemented in terms of [length] and [elementAt],
  * including [iterator].
  */
-abstract class ListIterable<E> extends IterableBase<E> {
+abstract class ListIterable<E> extends IterableBase<E>
+                               implements EfficientLength {
   int get length;
   E elementAt(int i);
 
@@ -341,7 +355,14 @@ class MappedIterable<S, T> extends IterableBase<T> {
   final Iterable<S> _iterable;
   final _Transformation<S, T> _f;
 
-  MappedIterable(this._iterable, T this._f(S element));
+  factory MappedIterable(Iterable iterable, T function(S value)) {
+    if (iterable is EfficientLength) {
+      return new EfficientLengthMappedIterable<S, T>(iterable, function);
+    }
+    return new MappedIterable<S, T>._(iterable, function);
+  }
+
+  MappedIterable._(this._iterable, T this._f(S element));
 
   Iterator<T> get iterator => new MappedIterator<S, T>(_iterable.iterator, _f);
 
@@ -356,6 +377,12 @@ class MappedIterable<S, T> extends IterableBase<T> {
   T elementAt(int index) => _f(_iterable.elementAt(index));
 }
 
+class EfficientLengthMappedIterable<S, T> extends MappedIterable<S, T>
+                                          implements EfficientLength {
+  EfficientLengthMappedIterable(Iterable iterable, T function(S value))
+      : super._(iterable, function);
+}
+
 class MappedIterator<S, T> extends Iterator<T> {
   T _current;
   final Iterator<S> _iterator;
@@ -375,8 +402,13 @@ class MappedIterator<S, T> extends Iterator<T> {
   T get current => _current;
 }
 
-/** Specialized alternative to [MappedIterable] for mapped [List]s. */
-class MappedListIterable<S, T> extends ListIterable<T> {
+/**
+ * Specialized alternative to [MappedIterable] for mapped [List]s.
+ *
+ * Expects efficient `length` and `elementAt` on the source iterable.
+ */
+class MappedListIterable<S, T> extends ListIterable<T>
+                               implements EfficientLength {
   final Iterable<S> _source;
   final _Transformation<S, T> _f;
 
@@ -465,17 +497,56 @@ class TakeIterable<E> extends IterableBase<E> {
   final Iterable<E> _iterable;
   final int _takeCount;
 
-  TakeIterable(this._iterable, this._takeCount) {
-    if (_takeCount is! int || _takeCount < 0) {
-      throw new ArgumentError(_takeCount);
+  factory TakeIterable(Iterable<E> iterable, int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new ArgumentError(takeCount);
+    }
+    if (iterable is EfficientLength) {
+      return new EfficientLengthTakeIterable<E>(iterable, takeCount);
+    }
+    return new TakeIterable<E>._(iterable, takeCount);
+  }
+
+  Iterable<E> take(int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new RangeError.value(takeCount);
+    }
+    if (_takeCount < takeCount) {
+      takeCount = _takeCount;
     }
+    return new TakeIterable<E>._(_iterable, takeCount)
   }
 
+  TakeIterable._(this._iterable, this._takeCount);
+
   Iterator<E> get iterator {
     return new TakeIterator<E>(_iterable.iterator, _takeCount);
   }
 }
 
+class EfficientLengthTakeIterable<E> extends TakeIterable<E>
+                                     implements EfficientLength {
+  EfficientLengthTakeIterable(Iterable<E> iterable, int takeCount)
+      : super._(iterable, takeCount);
+
+  Iterable<E> take(int takeCount) {
+    if (takeCount is! int || takeCount < 0) {
+      throw new RangeError.value(takeCount);
+    }
+    if (_takeCount < takeCount) {
+      takeCount = _takeCount;
+    }
+    return new EfficientLengthTakeIterable<E>(_iterable, takeCount)
+  }
+
+  int get length {
+    int iterableLength = _iterable.length;
+    if (iterableLength > _takeCount) return _takeCount;
+    return iterableLength;
+  }
+}
+
+
 class TakeIterator<E> extends Iterator<E> {
   final Iterator<E> _iterator;
   int _remaining;
@@ -536,7 +607,14 @@ class SkipIterable<E> extends IterableBase<E> {
   final Iterable<E> _iterable;
   final int _skipCount;
 
-  SkipIterable(this._iterable, this._skipCount) {
+  factory SkipIterable(Iterable<E> iterable, int skipCount) {
+    if (iterable is EfficientLength) {
+      return new EfficientLengthSkipIterable<E>(iterable, skipCount);
+    }
+    return new SkipIterable<E>._(iterable, skipCount);
+  }
+
+  SkipIterable._(this._iterable, this._skipCount) {
     if (_skipCount is! int || _skipCount < 0) {
       throw new RangeError(_skipCount);
     }
@@ -546,7 +624,7 @@ class SkipIterable<E> extends IterableBase<E> {
     if (n is! int || n < 0) {
       throw new RangeError.value(n);
     }
-    return new SkipIterable<E>(_iterable, _skipCount + n);
+    return new SkipIterable<E>._(_iterable, _skipCount + n);
   }
 
   Iterator<E> get iterator {
@@ -554,6 +632,25 @@ class SkipIterable<E> extends IterableBase<E> {
   }
 }
 
+class EfficientLengthSkipIterable<E> extends SkipIterable<E>
+                                     implements EfficientLength {
+  EfficientLengthSkipIterable(Iterable<E> iterable, int skipCount)
+      : super._(iterable, skipCount);
+
+  Iterable<E> skip(int n) {
+    if (n is! int || n < 0) {
+      throw new RangeError.value(n);
+    }
+    return new EfficientLengthSkipIterable<E>(_iterable, _skipCount + n);
+  }
+
+  int get length {
+    int length = _iterable.length - _skipCount;
+    if (length >= 0) return length;
+    return 0;
+  }
+}
+
 class SkipIterator<E> extends Iterator<E> {
   final Iterator<E> _iterator;
   int _skipCount;
@@ -605,7 +702,7 @@ class SkipWhileIterator<E> extends Iterator<E> {
 /**
  * The always empty [Iterable].
  */
-class EmptyIterable<E> extends IterableBase<E> {
+class EmptyIterable<E> extends IterableBase<E> implements EfficientLength {
   const EmptyIterable();
 
   Iterator<E> get iterator => const EmptyIterator();
@@ -897,7 +994,7 @@ class IterableMixinWorkaround {
     for (int i = 0; i < _toStringList.length; i++) {
       if (identical(_toStringList[i], iterable)) {
         return '$leftDelimiter...$rightDelimiter';
-        }
+      }
     }
 
     StringBuffer result = new StringBuffer();
@@ -1021,9 +1118,28 @@ class IterableMixinWorkaround {
   static void replaceRangeList(List list, int start, int end,
                                Iterable iterable) {
     _rangeCheck(list, start, end);
-    // TODO(floitsch): optimize this.
-    list.removeRange(start, end);
-    list.insertAll(start, iterable);
+    if (iterable is! EfficientLength) {
+      iterable = iterable.toList();
+    }
+    int removeLength = end - start;
+    int insertLength = iterable.length;
+    if (removeLength >= insertLength) {
+      int delta = removeLength - insertLength;
+      int insertEnd = start + insertLength;
+      int newEnd = list.length - delta;
+      list.setRange(start, insertEnd, iterable);
+      if (delta != 0) {
+        list.setRange(insertEnd, newEnd, list, end);
+        list.length = newEnd;
+      }
+    } else {
+      int delta = insertLength - removeLength;
+      int newLength = list.length + delta;
+      int insertEnd = start + insertLength;  // aka. end + delta.
+      list.length = newLength;
+      list.setRange(insertEnd, newLength, list, end);
+      list.setRange(start, insertEnd, iterable);
+    }
   }
 
   static void fillRangeList(List list, int start, int end, fillValue) {
@@ -1037,7 +1153,7 @@ class IterableMixinWorkaround {
     if (index < 0 || index > list.length) {
       throw new RangeError.range(index, 0, list.length);
     }
-    if (iterable is! List && iterable is! Set) {
+    if (iterable is! EfficientLength) {
       iterable = iterable.toList(growable: false);
     }
     int insertionLength = iterable.length;