Fix DoubleLinkedQueue so that appending to entries also update the queue length.

sdk/lib/collection/queue.dart

Index: sdk/lib/collection/queue.dart
diff --git a/sdk/lib/collection/queue.dart b/sdk/lib/collection/queue.dart
index f515392bf8cb4b44cae9598e5e417fe8344dd72d..8156a48fc111f1f7a19e46a56a38be9712aa6b70 100644
--- a/sdk/lib/collection/queue.dart
+++ b/sdk/lib/collection/queue.dart
@@ -96,24 +96,34 @@ abstract class Queue<E> implements Iterable<E>, EfficientLength {
 }
 
 
+class _DoubleLink {
+  _DoubleLink _previous;
+  _DoubleLink _next;
+
+  void _link(_DoubleLink previous,
+             _DoubleLink next) {
+    _next = next;
+    _previous = previous;
+    if (previous != null) previous._next = this;
+    if (next != null) next._previous = this;
+  }
+
+  void _unlink() {
+    if (_previous != null) _previous._next = _next;
+    if (_next != null) _next._previous = _previous;
+    _next = null;
+    _previous = null;
+  }
+}
+
 /**
  * An entry in a doubly linked list. It contains a pointer to the next
  * entry, the previous entry, and the boxed element.
  */
-class DoubleLinkedQueueEntry<E> {
-  DoubleLinkedQueueEntry<E> _previous;
-  DoubleLinkedQueueEntry<E> _next;
-  E _element;
+class DoubleLinkedQueueEntry<E> extends _DoubleLink {
+  E element;
 
-  DoubleLinkedQueueEntry(E e) : _element = e;
-
-  void _link(DoubleLinkedQueueEntry<E> previous,
-             DoubleLinkedQueueEntry<E> next) {
-    _next = next;
-    _previous = previous;
-    previous._next = this;
-    next._previous = this;
-  }
+  DoubleLinkedQueueEntry(this.element);
 
   void append(E e) {
     new DoubleLinkedQueueEntry<E>(e)._link(this, _next);
@@ -124,31 +134,91 @@ class DoubleLinkedQueueEntry<E> {
   }
 
   E remove() {
-    _previous._next = _next;
-    _next._previous = _previous;
-    _next = null;
-    _previous = null;
-    return _element;
+    _unlink();
+    return element;
   }
 
-  DoubleLinkedQueueEntry<E> _asNonSentinelEntry() {
-    return this;
+  DoubleLinkedQueueEntry<E> previousEntry() {
+    return _previous;
   }
 
-  DoubleLinkedQueueEntry<E> previousEntry() {
-    return _previous._asNonSentinelEntry();
+  DoubleLinkedQueueEntry<E> nextEntry() {
+    return _next;
+  }
+}
+
+/**
+ * Interface for the link classes used by [DoubleLinkedQueue].
+ *
+ * Both the [_DoubleLinkedQueueElement] and [_DoubleLinkedQueueSentinel]
+ * implements this interface.
+ * The entry contains a link back to the queue, so calling `append`
+ * or `prepend` can correctly update the element count.
+ */
+abstract class _DoubleLinkedQueueEntry<E> extends _DoubleLink {
+  DoubleLinkedQueue<E> _queue;
+  _DoubleLinkedQueueEntry(this._queue);
+
+  _DoubleLinkedQueueElement _asNonSentinelEntry();
+
+  void _append(E e) {
+    new _DoubleLinkedQueueElement<E>(e, _queue)._link(this, _next);
   }
 
+  void _prepend(E e) {
+    new _DoubleLinkedQueueElement<E>(e, _queue)._link(_previous, this);
+  }
+
+  E _remove();
+
+  E get element;
+
   DoubleLinkedQueueEntry<E> nextEntry() {
-    return _next._asNonSentinelEntry();
+    _DoubleLinkedQueueEntry next = _next;
+    return next._asNonSentinelEntry();
   }
 
-  E get element {
-    return _element;
+  DoubleLinkedQueueEntry<E> previousEntry() {
+    _DoubleLinkedQueueEntry previous = _previous;
+    return previous._asNonSentinelEntry();
+  }
+}
+
+/**
+ * The actual entry type used by the [DoubleLinkedQueue].
+ *
+ * The entry contains a reference to the queue, allowing
+ * [append]/[prepend] to update the list length.
+ */
+class _DoubleLinkedQueueElement<E> extends _DoubleLinkedQueueEntry<E>
+                                   implements DoubleLinkedQueueEntry<E> {
+  E element;
+  _DoubleLinkedQueueElement(this.element, DoubleLinkedQueue<E> queue)
+      : super(queue);
+
+  void append(E e) {
+    _append(e);
+    if (_queue != null) _queue._elementCount++;
+  }
+
+  void prepend(E e) {
+    _prepend(e);
+    if (_queue != null) _queue._elementCount++;
+  }
+
+  E _remove() {
+    _queue = null;
+    _unlink();
+    return element;
   }
 
-  void set element(E e) {
-    _element = e;
+  E remove() {
+    if (_queue != null) _queue._elementCount--;
+    return _remove();
+  }
+
+  _DoubleLinkedQueueElement _asNonSentinelEntry() {
+    return this;
   }
 }
 
@@ -160,25 +230,22 @@ class DoubleLinkedQueueEntry<E> {
  * Initially, a sentinel has its next and previous entry point to itself.
  * A sentinel does not box any user element.
  */
-class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {
-  _DoubleLinkedQueueEntrySentinel() : super(null) {
-    _link(this, this);
-  }
-
-  E remove() {
-    throw IterableElementError.noElement();
+class _DoubleLinkedQueueSentinel<E> extends _DoubleLinkedQueueEntry<E> {
+  _DoubleLinkedQueueSentinel(DoubleLinkedQueue queue) : super(queue) {
+    _previous = this;
+    _next = this;
   }
 
-  DoubleLinkedQueueEntry<E> _asNonSentinelEntry() {
+  _DoubleLinkedQueueElement _asNonSentinelEntry() {
     return null;
   }
 
-  void set element(E e) {
-    // This setter is unreachable.
-    // TODO(lrn): Don't inherit the field if we don't use it.
-    assert(false);
+  /** Hit by, e.g., [DoubleLinkedQueue.removeFirst] if the queue is empty. */
+  E _remove() {
+    throw IterableElementError.noElement();
   }
 
+  /** Hit by, e.g., [DoubleLinkedQueue.first] if the queue is empty. */
   E get element {
     throw IterableElementError.noElement();
   }
@@ -190,11 +257,11 @@ class _DoubleLinkedQueueEntrySentinel<E> extends DoubleLinkedQueueEntry<E> {
  * Allows constant time add, remove-at-ends and peek operations.
  */
 class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
-  _DoubleLinkedQueueEntrySentinel<E> _sentinel;
+  _DoubleLinkedQueueSentinel<E> _sentinel;
   int _elementCount = 0;
 
   DoubleLinkedQueue() {
-    _sentinel = new _DoubleLinkedQueueEntrySentinel<E>();
+    _sentinel = new _DoubleLinkedQueueSentinel<E>(this);
   }
 
   /**
@@ -204,7 +271,7 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
    * [addLast] in the order provided by [elements.iterator].
    */
   factory DoubleLinkedQueue.from(Iterable elements) {
-    Queue<E> list = new DoubleLinkedQueue();
+    Queue<E> list = new DoubleLinkedQueue<E>();
     for (final E e in elements) {
       list.addLast(e);
     }
@@ -214,44 +281,46 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
   int get length => _elementCount;
 
   void addLast(E value) {
-    _sentinel.prepend(value);
+    _sentinel._prepend(value);
     _elementCount++;
   }
 
   void addFirst(E value) {
-    _sentinel.append(value);
+    _sentinel._append(value);
     _elementCount++;
   }
 
   void add(E value) {
-    _sentinel.prepend(value);
+    _sentinel._prepend(value);
     _elementCount++;
   }
 
   void addAll(Iterable<E> iterable) {
     for (final E value in iterable) {
-      _sentinel.prepend(value);
+      _sentinel._prepend(value);
       _elementCount++;
     }
   }
 
   E removeLast() {
-    E result = _sentinel._previous.remove();
+    _DoubleLinkedQueueEntry lastEntry = _sentinel._previous;
+    E result = lastEntry._remove();
     _elementCount--;
     return result;
   }
 
   E removeFirst() {
-    E result = _sentinel._next.remove();
+    _DoubleLinkedQueueEntry firstEntry = _sentinel._next;
+    E result = firstEntry._remove();
     _elementCount--;
     return result;
   }
 
   bool remove(Object o) {
-    DoubleLinkedQueueEntry<E> entry = _sentinel._next;
+    _DoubleLinkedQueueEntry<E> entry = _sentinel._next;
     while (!identical(entry, _sentinel)) {
       if (entry.element == o) {
-        entry.remove();
+        entry._remove();
         _elementCount--;
         return true;
       }
@@ -261,11 +330,11 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
   }
 
   void _filter(bool test(E element), bool removeMatching) {
-    DoubleLinkedQueueEntry<E> entry = _sentinel._next;
+    _DoubleLinkedQueueEntry<E> entry = _sentinel._next;
     while (!identical(entry, _sentinel)) {
-      DoubleLinkedQueueEntry<E> next = entry._next;
+      _DoubleLinkedQueueEntry<E> next = entry._next;
       if (identical(removeMatching, test(entry.element))) {
-        entry.remove();
+        entry._remove();
         _elementCount--;
       }
       entry = next;
@@ -281,17 +350,21 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
   }
 
   E get first {
-    return _sentinel._next.element;
+    _DoubleLinkedQueueEntry firstEntry = _sentinel._next;
+    return firstEntry.element;
   }
 
   E get last {
-    return _sentinel._previous.element;
+    _DoubleLinkedQueueEntry lastEntry = _sentinel._previous;
+    return lastEntry.element;
   }
 
   E get single {
-    // Note that this throws correctly if the queue is empty.
+    // Note that this throws correctly if the queue is empty
+    // because reading element on the sentinel throws.
     if (identical(_sentinel._next, _sentinel._previous)) {
-      return _sentinel._next.element;
+      _DoubleLinkedQueueEntry entry = _sentinel._next;
+      return entry.element;
     }
     throw IterableElementError.tooMany();
   }
@@ -331,23 +404,27 @@ class DoubleLinkedQueue<E> extends IterableBase<E> implements Queue<E> {
 }
 
 class _DoubleLinkedQueueIterator<E> implements Iterator<E> {
-  _DoubleLinkedQueueEntrySentinel<E> _sentinel;
-  DoubleLinkedQueueEntry<E> _nextEntry = null;
+  _DoubleLinkedQueueSentinel<E> _sentinel;
+  _DoubleLinkedQueueEntry<E> _nextEntry = null;
   E _current;
 
-  _DoubleLinkedQueueIterator(_DoubleLinkedQueueEntrySentinel<E> sentinel)
+  _DoubleLinkedQueueIterator(_DoubleLinkedQueueSentinel<E> sentinel)
       : _sentinel = sentinel, _nextEntry = sentinel._next;
 
   bool moveNext() {
-    // When [_currentEntry] it is set to [:null:] then it is at the end.
-    if (!identical(_nextEntry, _sentinel)) {
-      _current = _nextEntry._element;
-      _nextEntry = _nextEntry._next;
-      return true;
+    if (identical(_nextEntry, _sentinel)) {
+      _current = null;
+      _nextEntry = null;
+      _sentinel = null;
+      return false;
     }
-    _current = null;
-    _nextEntry = _sentinel = null;  // Still identical.
-    return false;
+    _DoubleLinkedQueueElement elementEntry = _nextEntry;
+    if (elementEntry._queue == null) {
+      throw new ConcurrentModificationError(_sentinel._queue);
+    }
+    _current = elementEntry.element;
+    _nextEntry = elementEntry._next;
+    return true;
   }
 
   E get current => _current;