Change ListIterator to only check for concurrent modification at each iteration

lrhn · lrhn · commit 5a79c03e09ce · 2015-04-16T09:07:58.000Z
in checked mode. It also checks at the end in all cases. Iteration only goes from 0 to the original length of the list. This ensures that iterating a list while adding to it (like by x.addAll(x)) is caught instead of growing until out-of-memory. For well-behaved programs this makes no difference since length and original length stay the same. Also, it means that calling moveNext again later, after increasing the length, will not make iteration continue. After returning false, iteration is always done. However, it means that reducing the length causes an out-of-range read before reaching the end, and before a concurrent modification error can happen. R=sra@google.com Review URL: https://codereview.chromium.org//1024843002 git-svn-id: https://dart.googlecode.com/svn/branches/bleeding_edge/dart@45198 260f80e4-7a28-3924-810f-c04153c831b5
diff --git a/CHANGELOG.md b/CHANGELOG.md
@@ -2,6 +2,10 @@
 
 ### Core library changes
 
+* List iterators may not throw ConcurrentModificationError as eagerly in
+  release mode. In checked mode, the modification check is still as eager
+  as possible.
+  [r45198](https://code.google.com/p/dart/source/detail?r=45198),
 * Update experimental Isolate API:
   - Make priorty parameters of `Isolate.ping` and `Isolate.kill` methods
     a named parameter.
diff --git a/sdk/lib/_internal/compiler/js_lib/js_array.dart b/sdk/lib/_internal/compiler/js_lib/js_array.dart
@@ -605,34 +605,31 @@ class JSExtendableArray<E> extends JSMutableArray<E> {}
 
 
 /// An [Iterator] that iterates a JSArray.
-///
 class ArrayIterator<E> implements Iterator<E> {
   final JSArray<E> _iterable;
-  final int _length;
+  final int _originalLength;
   int _index;
   E _current;
 
   ArrayIterator(JSArray<E> iterable)
-      : _iterable = iterable, _length = iterable.length, _index = 0;
+      : _iterable = iterable, _originalLength = 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) {
+    // Check for concurrent modifiction at each step in checked mode.
+    assert((_originalLength == _iterable.length) ||
+           (throw new ConcurrentModificationError(_iterable)));
+    if (_index < _iterable.length) {
+      _current = _iterable.elementAt(_index);
+      _index++;
+      return true;
+    }
+    // Check for concurrent modification only at the end in production mode.
+    if (_originalLength != _iterable.length) {
       throw new ConcurrentModificationError(_iterable);
     }
-
-    if (_index >= length) {
-      _current = null;
-      return false;
-    }
-    _current = _iterable[_index];
-    _index++;
-    return true;
+    _current = null;
+    return false;
   }
 }
diff --git a/sdk/lib/internal/iterable.dart b/sdk/lib/internal/iterable.dart
@@ -320,27 +320,30 @@ class SubListIterable<E> extends ListIterable<E> {
  */
 class ListIterator<E> implements Iterator<E> {
   final Iterable<E> _iterable;
-  final int _length;
+  final int _originalLength;
   int _index;
   E _current;
 
   ListIterator(Iterable<E> iterable)
-      : _iterable = iterable, _length = iterable.length, _index = 0;
+      : _iterable = iterable, _originalLength = iterable.length, _index = 0;
 
   E get current => _current;
 
   bool moveNext() {
-    int length = _iterable.length;
-    if (_length != length) {
-      throw new ConcurrentModificationError(_iterable);
+    // Check for concurrent modifiction at each step in checked mode.
+    assert((_originalLength == _iterable.length) ||
+           (throw new ConcurrentModificationError(_iterable)));
+    if (_index < _iterable.length) {
+      _current = _iterable.elementAt(_index);
+      _index++;
+      return true;
     }
-    if (_index >= length) {
-      _current = null;
-      return false;
+    // Check for concurrent modification only at the end in production mode.
+    if (_originalLength != _iterable.length) {
+      throw new ConcurrentModificationError(_iterable);
     }
-    _current = _iterable.elementAt(_index);
-    _index++;
-    return true;
+    _current = null;
+    return false;
   }
 }
 
diff --git a/tests/corelib/iterable_fold_test.dart b/tests/corelib/iterable_fold_test.dart
@@ -123,7 +123,8 @@ main() {
     }, (e) => e is ConcurrentModificationError);
   }
 
-  void add4(collection) { collection.add(4); }
+  void add4(collection) { if (collection.length < 10) collection.add(4); }
+  void addList4(collection) { if (collection.length < 10) collection.add([4]); }
   void put4(map) { map[4] = 4; }
 
   testModification([1, 2, 3], add4, id);
@@ -134,7 +135,7 @@ main() {
 
   testModification([0, 1, 2, 3], add4, (x) => x.where((x) => x > 0));
   testModification([0, 1, 2], add4, (x) => x.map((x) => x + 1));
-  testModification([[1, 2], [3]], add4, (x) => x.expand((x) => x));
+  testModification([[1, 2], [3]], addList4, (x) => x.expand((x) => x));
   testModification([3, 2, 1], add4, (x) => x.reversed);
   testModification({1: 1, 2: 2, 3: 3}, put4, (x) => x.keys);
   testModification({1: 1, 2: 2, 3: 3}, put4, (x) => x.values);
diff --git a/tests/corelib/iterable_reduce_test.dart b/tests/corelib/iterable_reduce_test.dart
@@ -125,7 +125,9 @@ main() {
     }, (e) => e is ConcurrentModificationError);
   }
 
-  void add4(collection) { collection.add(4); }
+  // Add elements, but not infinitely often.
+  void add4(collection) { if (collection.length < 10) collection.add(4); }
+  void addList4(collection) { if (collection.length < 10) collection.add([4]); }
   void put4(map) { map[4] = 4; }
 
   testModification([1, 2, 3], add4, id);
@@ -136,7 +138,7 @@ main() {
 
   testModification([0, 1, 2, 3], add4, (x) => x.where((x) => x > 0));
   testModification([0, 1, 2], add4, (x) => x.map((x) => x + 1));
-  testModification([[1, 2], [3]], add4, (x) => x.expand((x) => x));
+  testModification([[1, 2], [3]], addList4, (x) => x.expand((x) => x));
   testModification([3, 2, 1], add4, (x) => x.reversed);
   testModification({1: 1, 2: 2, 3: 3}, put4, (x) => x.keys);
   testModification({1: 1, 2: 2, 3: 3}, put4, (x) => x.values);
diff --git a/tests/corelib/json_map_test.dart b/tests/corelib/json_map_test.dart
@@ -162,7 +162,7 @@ void testConcurrentModifications() {
   void testIterate(Map map, Iterable iterable, Function f) {
     Iterator iterator = iterable.iterator;
     f(map);
-    iterator.moveNext();
+    while (iterator.moveNext());
   }
 
   void testKeys(Map map, Function f) => testIterate(map, map.keys, f);
diff --git a/tests/corelib/list_test.dart b/tests/corelib/list_test.dart
@@ -376,23 +376,34 @@ void testGrowableListOperations(List list) {
   list.replaceRange(6, 8, []);
   Expect.listEquals([1, 2, 6, 6, 5, 0, 2, 3, 2, 1], list);
 
-  // Operations that change the length cause ConcurrentModificationError.
+  // Operations that change the length may cause ConcurrentModificationError.
+  // Reducing the length may cause a RangeError before the
+  // ConcurrentModificationError in production mode.
+  bool checkedMode = false;
+  assert((checkedMode = true));
+
   void testConcurrentModification(action()) {
     testIterator(int when) {
       list.length = 4;
       list.setAll(0, [0, 1, 2, 3]);
       Expect.throws(() {
         for (var element in list) {
-          if (element == when) action();
+          if (element == when) {
+            when = -1;  // Prevent triggering more than once.
+            action();
+          }
         }
-      }, (e) => e is ConcurrentModificationError);
+      }, (e) => !checkedMode || e is ConcurrentModificationError);
     }
     testForEach(int when) {
       list.length = 4;
       list.setAll(0, [0, 1, 2, 3]);
       Expect.throws(() {
         list.forEach((var element) {
-          if (element == when) action();
+          if (element == when) {
+            when = -1;
+            action();
+          }
         });
       }, (e) => e is ConcurrentModificationError);
     }

Original file line number	Diff line number	Diff line change
`@@ -162,7 +162,7 @@ void testConcurrentModifications() {`
`162`	`162`	`void testIterate(Map map, Iterable iterable, Function f) {`
`163`	`163`	`Iterator iterator = iterable.iterator;`
`164`	`164`	`f(map);`
`165`		`- iterator.moveNext();`
	`165`	`+ while (iterator.moveNext());`
`166`	`166`	`}`
`167`	`167`
`168`	`168`	`void testKeys(Map map, Function f) => testIterate(map, map.keys, f);`