Fix DoubleLinkedListQueue misbehavior on concurrent modification.

sdk/lib/collection/queue.dart

 // Copyright (c) 2011, 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.
 
 part of dart.collection;
 
 /**
  * A [Queue] is a collection that can be manipulated at both ends. One
  * can iterate over the elements of a queue through [forEach] or with
  * an [Iterator].
@@ skipping 304 matching lines @@
   E removeFirst() {
     _DoubleLinkedQueueEntry<E> firstEntry = _sentinel._nextLink;
     E result = firstEntry._remove();
     _elementCount--;
     return result;
   }
 
   bool remove(Object o) {
     _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink;
     while (!identical(entry, _sentinel)) {
-      if (entry._element == o) {
+      bool equals = (entry._element == o);
+      if (!identical(this, entry._queue)) {
+        // Entry must still be in the queue.
+        throw new ConcurrentModificationError(this);
+      }
+      if (equals) {
         entry._remove();
         _elementCount--;
         return true;
       }
       entry = entry._nextLink;
     }
     return false;
   }
 
   void _filter(bool test(E element), bool removeMatching) {
     _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink;
     while (!identical(entry, _sentinel)) {
-      _DoubleLinkedQueueEntry<E> next = entry._nextLink;
-      if (identical(removeMatching, test(entry._element))) {
+      bool matches = test(entry._element);
+      if (!identical(this, entry._queue)) {
+        // Entry must still be in the queue.
+        throw new ConcurrentModificationError(this);
+      }
+      _DoubleLinkedQueueEntry<E> next = entry._nextLink;  // Cannot be null.
+      if (identical(removeMatching, matches)) {
         entry._remove();
         _elementCount--;
       }
       entry = next;
     }
   }
 
   void removeWhere(bool test(E element)) {
     _filter(test, true);
   }
 
   void retainWhere(bool test(E element)) {
     _filter(test, false);
   }
 
   E get first {
     _DoubleLinkedQueueEntry<E> firstEntry = _sentinel._nextLink;
     return firstEntry._element;
   }
 
   E get last {
     _DoubleLinkedQueueEntry<E> lastEntry = _sentinel._previousLink;
     return lastEntry._element;
   }
 
   E get single {
     // Note that this throws correctly if the queue is empty
-    // because reading element on the sentinel throws.
+    // because reading the element of the sentinel throws.
     if (identical(_sentinel._nextLink, _sentinel._previousLink)) {
       _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink;
       return entry._element;
     }
     throw IterableElementError.tooMany();
   }
 
+  /**
+   * The entry object of the first element in the queue.
+   *
+   * Each element of the queue has an associated [DoubleLinkedQueueEntry].
+   * Returns the entry object corresponding to the first element of the queue.
+   *
+   * The entry objects can also be accessed using [lastEntry],
+   * and they can be iterated using [DoubleLinkedQueueEntry.nextEntry()] and
+   * [DoubleLinkedQueueEntry.previousEntry()].
+   */
+  DoubleLinkedQueueEntry<E> firstEntry() {
+    return _sentinel.nextEntry();
+  }
+
+  /**
+   * The entry object of the last element in the queue.
+   *
+   * Each element of the queue has an associated [DoubleLinkedQueueEntry].
+   * Returns the entry object corresponding to the last element of the queue.
+   *
+   * The entry objects can also be accessed using [firstEntry],
+   * and they can be iterated using [DoubleLinkedQueueEntry.nextEntry()] and
+   * [DoubleLinkedQueueEntry.previousEntry()].
+   */
   DoubleLinkedQueueEntry<E> lastEntry() {

[floitsch, 2016/12/01 18:31:09]

not a getter?
argh :(

     return _sentinel.previousEntry();
   }
 
-  DoubleLinkedQueueEntry<E> firstEntry() {
-    return _sentinel.nextEntry();
-  }
-
   bool get isEmpty {
     return (identical(_sentinel._nextLink, _sentinel));
   }
 
   void clear() {
     _sentinel._nextLink = _sentinel;
     _sentinel._previousLink = _sentinel;
     _elementCount = 0;
   }
 
-  void forEachEntry(void f(DoubleLinkedQueueEntry<E> element)) {
+  /**
+   * Calls [action] for each entry object of this double-linked queue.
+   *
+   * Each element of the queue has an associated [DoubleLinkedQueueEntry].
+   * This method iterates the entry objects from first to last and calls
+   * [action] with each object in turn.
+   *
+   * The entry objects can also be accessed using [firstEntry] and [lastEntry],
+   * and iterated using [DoubleLinkedQueueEntry.nextEntry()] and
+   * [DoubleLinkedQueueEntry.previousEntry()].
+   *
+   * The [action] function can use methods on [DoubleLinkedQueueEntry] to remove
+   * the entry or it can insert elements before or after then entry.
+   * If the current entry is removed, iteration continues with the entry that
+   * was following the current entry when [action] was called. Any elements
+   * inserted after the current element before it is removed will not be
+   * visited by the iteration.
+   */
+  void forEachEntry(void action(DoubleLinkedQueueEntry<E> element)) {
     _DoubleLinkedQueueEntry<E> entry = _sentinel._nextLink;
     while (!identical(entry, _sentinel)) {
-      _DoubleLinkedQueueEntry<E> nextEntry = entry._nextLink;
       _DoubleLinkedQueueElement<E> element = entry;
-      f(element);
-      entry = nextEntry;
+      _DoubleLinkedQueueEntry<E> next = element._nextLink;
+      // Remember both entry and entry._nextLink.
+      // If someone calls `element.remove()` we continue from `next`.
+      // Otherwise we use the value of entry._nextLink which may have been
+      // updated.
+      action(element);
+      if (identical(this, entry._queue)) {
+        next = entry._nextLink;
+      } else if (!identical(this, next._queue)) {
+        throw new ConcurrentModificationError(this);
+      }
+      entry = next;
     }
   }
 
   _DoubleLinkedQueueIterator<E> get iterator {
     return new _DoubleLinkedQueueIterator<E>(_sentinel);
   }
 
   String toString() => IterableBase.iterableToFullString(this, '{', '}');
 }
 
 class _DoubleLinkedQueueIterator<E> implements Iterator<E> {
   _DoubleLinkedQueueSentinel<E> _sentinel;
   _DoubleLinkedQueueEntry<E> _nextEntry = null;
   E _current;
 
   _DoubleLinkedQueueIterator(_DoubleLinkedQueueSentinel<E> sentinel)
       : _sentinel = sentinel,
         _nextEntry = sentinel._nextLink;
 
   bool moveNext() {
     if (identical(_nextEntry, _sentinel)) {
       _current = null;
       _nextEntry = null;
       _sentinel = null;
       return false;
     }
     _DoubleLinkedQueueElement<E> elementEntry = _nextEntry;
-    if (elementEntry._queue == null) {
+    if (!identical(_sentinel._queue, elementEntry._queue)) {
       throw new ConcurrentModificationError(_sentinel._queue);
     }
     _current = elementEntry._element;
     _nextEntry = elementEntry._nextLink;
     return true;
   }
 
   E get current => _current;
 }
 
@@ skipping 269 matching lines @@
   void _add(E element) {
     _table[_tail] = element;
     _tail = (_tail + 1) & (_table.length - 1);
     if (_head == _tail) _grow();
     _modificationCount++;
   }
 
   /**
    * Removes the element at [offset] into [_table].
    *
-   * Removal is performed by linerarly moving elements either before or after
+   * Removal is performed by linearly moving elements either before or after
    * [offset] by one position.
    *
    * Returns the new offset of the following element. This may be the same
    * offset or the following offset depending on how elements are moved
    * to fill the hole.
    */
   int _remove(int offset) {
     int mask = _table.length - 1;
     int startDistance = (offset - _head) & mask;
     int endDistance = (_tail - offset) & mask;
@@ skipping 87 matching lines @@
     _queue._checkModification(_modificationCount);
     if (_position == _end) {
       _current = null;
       return false;
     }
     _current = _queue._table[_position];
     _position = (_position + 1) & (_queue._table.length - 1);
     return true;
   }
 }