Updates for js_array

tool/input_sdk/private/js_array.dart

Index: tool/input_sdk/private/js_array.dart
diff --git a/tool/input_sdk/private/js_array.dart b/tool/input_sdk/private/js_array.dart
index 8d21950e9afbd5e420966ee979b1b8f46693a3d2..83d2c4d9985a95a0d2ea4b9ad11f7cfef896f419 100644
--- a/tool/input_sdk/private/js_array.dart
+++ b/tool/input_sdk/private/js_array.dart
@@ -33,7 +33,7 @@ class JSArray<E> implements List<E>, JSIndexable {
     // the object. We never actually look at the value, but only want
     // to know if the property exists.
     JS('void', r'#.fixed$length = Array', list);
-    return list;
+    return JS('JSFixedArray', '#', list);
   }
 
   static List markUnmodifiableList(List list) {
@@ -63,35 +63,47 @@ class JSArray<E> implements List<E>, JSIndexable {
   }
 
   E removeAt(int index) {
-    if (index is !int) throw new ArgumentError(index);
+    checkGrowable('removeAt');
+    if (index is !int) throw argumentErrorValue(index);
     if (index < 0 || index >= length) {
       throw new RangeError.value(index);
     }
-    checkGrowable('removeAt');
     return JS('-dynamic', r'#.splice(#, 1)[0]', this, index);
   }
 
   void insert(int index, E value) {
-    if (index is !int) throw new ArgumentError(index);
+    checkGrowable('insert');
+    if (index is !int) throw argumentErrorValue(index);
     if (index < 0 || index > length) {
       throw new RangeError.value(index);
     }
-    checkGrowable('insert');
     JS('void', r'#.splice(#, 0, #)', this, index, value);
   }
 
   void insertAll(int index, Iterable<E> iterable) {
     checkGrowable('insertAll');
-    IterableMixinWorkaround.insertAllList(this, index, iterable);
+    RangeError.checkValueInInterval(index, 0, this.length, "index");
+    if (iterable is! EfficientLength) {
+      iterable = iterable.toList();
+    }
+    int insertionLength = iterable.length;
+    this.length += insertionLength;
+    int end = index + insertionLength;
+    this.setRange(end, this.length, this, index);
+    this.setRange(index, end, iterable);
   }
 
   void setAll(int index, Iterable<E> iterable) {
-    IterableMixinWorkaround.setAllList(this, index, iterable);
+    checkMutable('setAll');
+    RangeError.checkValueInInterval(index, 0, this.length, "index");
+    for (var element in iterable) {
+      this[index++] = element;
+    }
   }
 
   E removeLast() {
     checkGrowable('removeLast');
-    if (length == 0) throw new RangeError.value(-1);
+    if (length == 0) throw diagnoseIndexError(this, -1);
     return JS('var', r'#.pop()', this);
   }
 
@@ -106,27 +118,61 @@ class JSArray<E> implements List<E>, JSIndexable {
     return false;
   }
 
+  /**
+   * Removes elements matching [test] from [this] List.
+   */
   void removeWhere(bool test(E element)) {
-    // This could, and should, be optimized.
-    IterableMixinWorkaround.removeWhereList(this, test);
+    checkGrowable('removeWhere');
+    _removeWhere(test, true);
   }
 
   void retainWhere(bool test(E element)) {
-    IterableMixinWorkaround.removeWhereList(this,
-                                            (E element) => !test(element));
+    checkGrowable('retainWhere');
+    _removeWhere(test, false);
+  }
+
+  void _removeWhere(bool test(E element), bool removeMatching) {
+    // Performed in two steps, to avoid exposing an inconsistent state
+    // to the [test] function. First the elements to retain are found, and then
+    // the original list is updated to contain those elements.
+
+    // TODO(sra): Replace this algorthim with one that retains a list of ranges
+    // to be removed.  Most real uses remove 0, 1 or a few clustered elements.
+
+    List retained = [];
+    int end = this.length;
+    for (int i = 0; i < end; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var element = JS('', '#[#]', this, i);
+      // !test() ensures bool conversion in checked mode.
+      if (!test(element) == removeMatching) {
+        retained.add(element);
+      }
+      if (this.length != end) throw new ConcurrentModificationError(this);
+    }
+    if (retained.length == end) return;
+    this.length = retained.length;
+    for (int i = 0; i < retained.length; i++) {
+      this[i] = retained[i];
+    }
   }
 
   Iterable<E> where(bool f(E element)) {
-    return new IterableMixinWorkaround<E>().where(this, f);
+    return new WhereIterable<E>(this, f);
   }
 
-  Iterable/*<T>*/ expand/*<T>*/(Iterable/*<E>*/ /*=Iterable<T>*/f(E element)) {
-    return IterableMixinWorkaround.expand(this, f);
+  Iterable/*<T>*/ expand/*<T>*/(Iterable/*<T>*/ f(E element)) {
+    return new ExpandIterable<E, dynamic/*=T*/>(this, f);
   }
 
   void addAll(Iterable<E> collection) {
+    int i = this.length;
+    checkGrowable('addAll');
     for (E e in collection) {
-      this.add(e);
+      assert(i == this.length || (throw new ConcurrentModificationError(this)));
+      i++;
+      JS('void', r'#.push(#)', this, e);
     }
   }
 
@@ -135,17 +181,18 @@ class JSArray<E> implements List<E>, JSIndexable {
   }
 
   void forEach(void f(E element)) {
-    int length = this.length;
-    for (int i = 0; i < length; i++) {
-      f(JS('', '#[#]', this, i));
-      if (length != this.length) {
-        throw new ConcurrentModificationError(this);
-      }
+    int end = this.length;
+    for (int i = 0; i < end; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      f(element);
+      if (this.length != end) throw new ConcurrentModificationError(this);
     }
   }
 
   Iterable/*<T>*/ map/*<T>*/(/*=T*/ f(E element)) {
-    return IterableMixinWorkaround.mapList(this, f);
+    return new MappedListIterable<E, T>(this, f);
   }
 
   String join([String separator = ""]) {
@@ -157,39 +204,97 @@ class JSArray<E> implements List<E>, JSIndexable {
   }
 
   Iterable<E> take(int n) {
-    return new IterableMixinWorkaround<E>().takeList(this, n);
+    return new SubListIterable<E>(this, 0, n);
   }
 
   Iterable<E> takeWhile(bool test(E value)) {
-    return new IterableMixinWorkaround<E>().takeWhile(this, test);
+    return new TakeWhileIterable<E>(this, test);
   }
 
   Iterable<E> skip(int n) {
-    return new IterableMixinWorkaround<E>().skipList(this, n);
+    return new SubListIterable<E>(this, n, null);
   }
 
   Iterable<E> skipWhile(bool test(E value)) {
-    return new IterableMixinWorkaround<E>().skipWhile(this, test);
+    return new SkipWhileIterable<E>(this, test);
   }
 
-  E reduce(E combine(E value, E element)) {
-    return IterableMixinWorkaround.reduce(this, combine);
+  E reduce(E combine(E previousValue, E element)) {
+    int length = this.length;
+    if (length == 0) throw IterableElementError.noElement();
+    E value = this[0];
+    for (int i = 1; i < length; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      value = combine(value, element);
+      if (length != this.length) throw new ConcurrentModificationError(this);
+    }
+    return value;
   }
 
   /*=T*/ fold/*<T>*/(/*=T*/ initialValue, /*=T*/ combine(/*=T*/ previousValue, E element)) {
-    return IterableMixinWorkaround.fold(this, initialValue, combine);
+    var/*=T*/ value = initialValue;
+    int length = this.length;
+    for (int i = 0; i < length; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      value = combine(value, element);
+      if (this.length != length) throw new ConcurrentModificationError(this);
+    }
+    return value;
   }
 
   E firstWhere(bool test(E value), {E orElse()}) {
-    return IterableMixinWorkaround.firstWhere(this, test, orElse);
+    int end = this.length;
+    for (int i = 0; i < end; ++i) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      if (test(element)) return element;
+      if (this.length != end) throw new ConcurrentModificationError(this);
+    }
+    if (orElse != null) return orElse();
+    throw IterableElementError.noElement();
   }
 
-  E lastWhere(bool test(E value), {E orElse()}) {
-    return IterableMixinWorkaround.lastWhereList(this, test, orElse);
+  E lastWhere(bool test(E element), { E orElse() }) {
+    int length = this.length;
+    for (int i = length - 1; i >= 0; i--) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      if (test(element)) return element;
+      if (length != this.length) {
+        throw new ConcurrentModificationError(this);
+      }
+    }
+    if (orElse != null) return orElse();
+    throw IterableElementError.noElement();
   }
 
-  E singleWhere(bool test(E value)) {
-    return IterableMixinWorkaround.singleWhere(this, test);
+  E singleWhere(bool test(E element)) {
+    int length = this.length;
+    E match = null;
+    bool matchFound = false;
+    for (int i = 0; i < length; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var element = JS('', '#[#]', this, i);
+      if (test(element)) {
+        if (matchFound) {
+          throw IterableElementError.tooMany();
+        }
+        matchFound = true;
+        match = element;
+      }
+      if (length != this.length) {
+        throw new ConcurrentModificationError(this);
+      }
+    }
+    if (matchFound) return match;
+    throw IterableElementError.noElement();
   }
 
   E elementAt(int index) {
@@ -198,16 +303,16 @@ class JSArray<E> implements List<E>, JSIndexable {
 
   List<E> sublist(int start, [int end]) {
     checkNull(start); // TODO(ahe): This is not specified but co19 tests it.
-    if (start is !int) throw new ArgumentError(start);
+    if (start is !int) throw argumentErrorValue(start);
     if (start < 0 || start > length) {
-      throw new RangeError.range(start, 0, length);
+      throw new RangeError.range(start, 0, length, "start");
     }
     if (end == null) {
       end = length;
     } else {
-      if (end is !int) throw new ArgumentError(end);
+      if (end is !int) throw argumentErrorValue(end);
       if (end < start || end > length) {
-        throw new RangeError.range(end, start, length);
+        throw new RangeError.range(end, start, length, "end");
       }
     }
     if (start == end) return <E>[];
@@ -217,75 +322,185 @@ class JSArray<E> implements List<E>, JSIndexable {
 
 
   Iterable<E> getRange(int start, int end) {
-    return new IterableMixinWorkaround<E>().getRangeList(this, start, end);
+    RangeError.checkValidRange(start, end, this.length);
+    return new SubListIterable<E>(this, start, end);
   }
 
   E get first {
     if (length > 0) return this[0];
-    throw new StateError("No elements");
+    throw IterableElementError.noElement();
   }
 
   E get last {
     if (length > 0) return this[length - 1];
-    throw new StateError("No elements");
+    throw IterableElementError.noElement();
   }
 
   E get single {
     if (length == 1) return this[0];
-    if (length == 0) throw new StateError("No elements");
-    throw new StateError("More than one element");
+    if (length == 0) throw IterableElementError.noElement();
+    throw IterableElementError.tooMany();
   }
 
   void removeRange(int start, int end) {
     checkGrowable('removeRange');
-    int receiverLength = this.length;
-    if (start < 0 || start > receiverLength) {
-      throw new RangeError.range(start, 0, receiverLength);
-    }
-    if (end < start || end > receiverLength) {
-      throw new RangeError.range(end, start, receiverLength);
-    }
-    Lists.copy(this,
-               end,
-               this,
-               start,
-               receiverLength - end);
-    this.length = receiverLength - (end - start);
+    RangeError.checkValidRange(start, end, this.length);
+    int deleteCount = end - start;
+    JS('', '#.splice(#, #)', this, start, deleteCount);
   }
 
   void setRange(int start, int end, Iterable<E> iterable, [int skipCount = 0]) {
-    IterableMixinWorkaround.setRangeList(this, start, end, iterable, skipCount);
+    checkMutable('set range');
+
+    RangeError.checkValidRange(start, end, this.length);
+    int length = end - start;
+    if (length == 0) return;
+    RangeError.checkNotNegative(skipCount, "skipCount");
+
+    List/*<E>*/ otherList;
+    int otherStart;
+    // TODO(floitsch): Make this accept more.
+    if (iterable is List) {
+      otherList = iterable;
+      otherStart = skipCount;
+    } else {
+      otherList = iterable.skip(skipCount).toList(growable: false);
+      otherStart = 0;
+    }
+    if (otherStart + length > otherList.length) {
+      throw IterableElementError.tooFew();
+    }
+    if (otherStart < start) {
+      // Copy backwards to ensure correct copy if [from] is this.
+      // TODO(sra): If [from] is the same Array as [this], we can copy without
+      // type annotation checks on the stores.
+      for (int i = length - 1; i >= 0; i--) {
+        // Use JS to avoid bounds check (the bounds check elimination
+        // optimzation is too weak). The 'E' type annotation is a store type
+        // check - we can't rely on iterable, it could be List<dynamic>.
+        E element = otherList[otherStart + i];
+        JS('', '#[#] = #', this, start + i, element);
+      }
+    } else {
+      for (int i = 0; i < length; i++) {
+        E element = otherList[otherStart + i];
+        JS('', '#[#] = #', this, start + i, element);
+      }
+    }
   }
 
   void fillRange(int start, int end, [E fillValue]) {
-    IterableMixinWorkaround.fillRangeList(this, start, end, fillValue);
+    checkMutable('fill range');
+    RangeError.checkValidRange(start, end, this.length);
+    for (int i = start; i < end; i++) {
+      // Store is safe since [fillValue] type has been checked as parameter.
+      JS('', '#[#] = #', this, i, fillValue);
+    }
   }
 
-  void replaceRange(int start, int end, Iterable<E> iterable) {
-    IterableMixinWorkaround.replaceRangeList(this, start, end, iterable);
+  void replaceRange(int start, int end, Iterable<E> replacement) {
+    checkGrowable('replace range');
+    RangeError.checkValidRange(start, end, this.length);
+    if (replacement is! EfficientLength) {
+      replacement = replacement.toList();
+    }
+    int removeLength = end - start;
+    int insertLength = replacement.length;
+    if (removeLength >= insertLength) {
+      int delta = removeLength - insertLength;
+      int insertEnd = start + insertLength;
+      int newLength = this.length - delta;
+      this.setRange(start, insertEnd, replacement);
+      if (delta != 0) {
+        this.setRange(insertEnd, newLength, this, end);
+        this.length = newLength;
+      }
+    } else {
+      int delta = insertLength - removeLength;
+      int newLength = this.length + delta;
+      int insertEnd = start + insertLength;  // aka. end + delta.
+      this.length = newLength;
+      this.setRange(insertEnd, newLength, this, end);
+      this.setRange(start, insertEnd, replacement);
+    }
   }
 
-  bool any(bool f(E element)) => IterableMixinWorkaround.any(this, f);
+  bool any(bool test(E element)) {
+    int end = this.length;
+    for (int i = 0; i < end; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      if (test(element)) return true;
+      if (this.length != end) throw new ConcurrentModificationError(this);
+    }
+    return false;
+  }
 
-  bool every(bool f(E element)) => IterableMixinWorkaround.every(this, f);
+  bool every(bool test(E element)) {
+    int end = this.length;
+    for (int i = 0; i < end; i++) {
+      // TODO(22407): Improve bounds check elimination to allow this JS code to
+      // be replaced by indexing.
+      var/*=E*/ element = JS('', '#[#]', this, i);
+      if (!test(element)) return false;
+      if (this.length != end) throw new ConcurrentModificationError(this);
+    }
+    return true;
+  }
 
-  Iterable<E> get reversed =>
-      new IterableMixinWorkaround<E>().reversedList(this);
+  Iterable<E> get reversed => new ReversedListIterable<E>(this);
 
   void sort([int compare(E a, E b)]) {
-    IterableMixinWorkaround.sortList(this, compare);
+    checkMutable('sort');
+    Sort.sort(this, compare == null ? Comparable.compare : compare);
   }
 
   void shuffle([Random random]) {
-    IterableMixinWorkaround.shuffleList(this, random);
+    checkMutable('shuffle');
+    if (random == null) random = new Random();
+    int length = this.length;
+    while (length > 1) {
+      int pos = random.nextInt(length);
+      length -= 1;
+      var tmp = this[length];
+      this[length] = this[pos];
+      this[pos] = tmp;
+    }
   }
 
   int indexOf(Object element, [int start = 0]) {
-    return IterableMixinWorkaround.indexOfList(this, element, start);
+    if (start >= this.length) {
+      return -1;
+    }
+    if (start < 0) {
+      start = 0;
+    }
+    for (int i = start; i < this.length; i++) {
+      if (this[i] == element) {
+        return i;
+      }
+    }
+    return -1;
   }
 
-  int lastIndexOf(Object element, [int start]) {
-    return IterableMixinWorkaround.lastIndexOfList(this, element, start);
+  int lastIndexOf(Object element, [int startIndex]) {
+    if (startIndex == null) {
+      startIndex = this.length - 1;
+    } else {
+      if (startIndex < 0) {
+        return -1;
+      }
+      if (startIndex >= this.length) {
+        startIndex = this.length - 1;
+      }
+    }
+    for (int i = startIndex; i >= 0; i--) {
+      if (this[i] == element) {
+        return i;
+      }
+    }
+    return -1;
   }
 
   bool contains(Object other) {
@@ -309,34 +524,41 @@ class JSArray<E> implements List<E>, JSIndexable {
 
   Set<E> toSet() => new Set<E>.from(this);
 
-  Iterator<E> get iterator => new ListIterator<E>(this);
+  Iterator<E> get iterator => new ArrayIterator<E>(this);
 
   int get hashCode => Primitives.objectHashCode(this);
 
   int get length => JS('int', r'#.length', this);
 
   void set length(int newLength) {
-    if (newLength is !int) throw new ArgumentError(newLength);
-    if (newLength < 0) throw new RangeError.value(newLength);
     checkGrowable('set length');
+    if (newLength is !int) {
+      throw new ArgumentError.value(newLength, 'newLength');
+    }
+    // TODO(sra): Remove this test and let JavaScript throw an error.
+    if (newLength < 0) {
+      throw new RangeError.range(newLength, 0, null, 'newLength');
+    }
+    // JavaScript with throw a RangeError for numbers that are too big. The
+    // message does not contain the value.
     JS('void', r'#.length = #', this, newLength);
   }
 
   E operator [](int index) {
-    if (index is !int) throw new ArgumentError(index);
-    if (index >= length || index < 0) throw new RangeError.value(index);
+    if (index is !int) throw diagnoseIndexError(this, index);
+    if (index >= length || index < 0) throw diagnoseIndexError(this, index);
     return JS('var', '#[#]', this, index);
   }
 
   void operator []=(int index, E value) {
     checkMutable('indexed set');
-    if (index is !int) throw new ArgumentError(index);
-    if (index >= length || index < 0) throw new RangeError.value(index);
+    if (index is !int) throw diagnoseIndexError(this, index);
+    if (index >= length || index < 0) throw diagnoseIndexError(this, index);
     JS('void', r'#[#] = #', this, index, value);
   }
 
   Map<int, E> asMap() {
-    return new IterableMixinWorkaround<E>().asMapList(this);
+    return new ListMapView<E>(this);
   }
 }
 
@@ -344,8 +566,48 @@ class JSArray<E> implements List<E>, JSIndexable {
  * Dummy subclasses that allow the backend to track more precise
  * information about arrays through their type. The CPA type inference
  * relies on the fact that these classes do not override [] nor []=.
+ *
+ * These classes are really a fiction, and can have no methods, since
+ * getInterceptor always returns JSArray.  We should consider pushing the
+ * 'isGrowable' and 'isMutable' checks into the getInterceptor implementation so
+ * these classes can have specialized implementations. Doing so will challenge
+ * many assuptions in the JS backend.
  */
 class JSMutableArray<E> extends JSArray<E> implements JSMutableIndexable {}
 class JSFixedArray<E> extends JSMutableArray<E> {}
 class JSExtendableArray<E> extends JSMutableArray<E> {}
 class JSUnmodifiableArray<E> extends JSArray<E> {} // Already is JSIndexable.
+
+
+/// An [Iterator] that iterates a JSArray.
+///
+class ArrayIterator<E> implements Iterator<E> {
+  final JSArray<E> _iterable;
+  final int _length;
+  int _index;
+  E _current;
+
+  ArrayIterator(JSArray<E> iterable)
+      : _iterable = iterable, _length = iterable.length, _index = 0;
+
+  E get current => _current;
+
+  bool moveNext() {
+    int length = _iterable.length;
+
+    // We have to do the length check even on fixed length Arrays.  If we can
+    // inline moveNext() we might be able to GVN the length and eliminate this
+    // check on known fixed length JSArray.
+    if (_length != length) {
+      throw throwConcurrentModificationError(_iterable);
+    }
+
+    if (_index >= length) {
+      _current = null;
+      return false;
+    }
+    _current = _iterable[_index];
+    _index++;
+    return true;
+  }
+}