Commits

Santoso Wijaya committed 759e56c

Update collections.deque to 2.7 compliance, including supporting
maxlen kwarg. Add synchronization to ensure threadsafety guarantees.

Fixes http://bugs.jython.org/issue1949

Comments (0)

Files changed (3)

Lib/test/test_deque.py

 from collections import deque
 import unittest
 from test import test_support, seq_tests
-from weakref import proxy
+import gc
+import weakref
 import copy
 import cPickle as pickle
-from cStringIO import StringIO
 import random
-import os
+import struct
 
 BIG = 100000
 
 class TestBasic(unittest.TestCase):
 
     def test_basics(self):
-        d = deque(xrange(100))
-        d.__init__(xrange(100, 200))
+        d = deque(xrange(-5125, -5000))
+        d.__init__(xrange(200))
         for i in xrange(200, 400):
             d.append(i)
         for i in reversed(xrange(-200, 0)):
         self.assertEqual(right, range(150, 400))
         self.assertEqual(list(d), range(50, 150))
 
+    def test_maxlen(self):
+        self.assertRaises(ValueError, deque, 'abc', -1)
+        self.assertRaises(ValueError, deque, 'abc', -2)
+        it = iter(range(10))
+        d = deque(it, maxlen=3)
+        self.assertEqual(list(it), [])
+        self.assertEqual(repr(d), 'deque([7, 8, 9], maxlen=3)')
+        self.assertEqual(list(d), range(7, 10))
+        self.assertEqual(d, deque(range(10), 3))
+        d.append(10)
+        self.assertEqual(list(d), range(8, 11))
+        d.appendleft(7)
+        self.assertEqual(list(d), range(7, 10))
+        d.extend([10, 11])
+        self.assertEqual(list(d), range(9, 12))
+        d.extendleft([8, 7])
+        self.assertEqual(list(d), range(7, 10))
+        d = deque(xrange(200), maxlen=10)
+        d.append(d)
+        test_support.unlink(test_support.TESTFN)
+        fo = open(test_support.TESTFN, "wb")
+        try:
+            print >> fo, d,
+            fo.close()
+            fo = open(test_support.TESTFN, "rb")
+            self.assertEqual(fo.read(), repr(d))
+        finally:
+            fo.close()
+            test_support.unlink(test_support.TESTFN)
+
+        d = deque(range(10), maxlen=None)
+        self.assertEqual(repr(d), 'deque([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])')
+        fo = open(test_support.TESTFN, "wb")
+        try:
+            print >> fo, d,
+            fo.close()
+            fo = open(test_support.TESTFN, "rb")
+            self.assertEqual(fo.read(), repr(d))
+        finally:
+            fo.close()
+            test_support.unlink(test_support.TESTFN)
+
+    def test_maxlen_zero(self):
+        it = iter(range(100))
+        deque(it, maxlen=0)
+        self.assertEqual(list(it), [])
+
+        it = iter(range(100))
+        d = deque(maxlen=0)
+        d.extend(it)
+        self.assertEqual(list(it), [])
+
+        it = iter(range(100))
+        d = deque(maxlen=0)
+        d.extendleft(it)
+        self.assertEqual(list(it), [])
+
+    def test_maxlen_attribute(self):
+        self.assertEqual(deque().maxlen, None)
+        self.assertEqual(deque('abc').maxlen, None)
+        self.assertEqual(deque('abc', maxlen=4).maxlen, 4)
+        self.assertEqual(deque('abc', maxlen=2).maxlen, 2)
+        self.assertEqual(deque('abc', maxlen=0).maxlen, 0)
+        with self.assertRaises(AttributeError):
+            d = deque('abc')
+            d.maxlen = 10
+
+    def test_count(self):
+        for s in ('', 'abracadabra', 'simsalabim'*500+'abc'):
+            s = list(s)
+            d = deque(s)
+            for letter in 'abcdefghijklmnopqrstuvwxyz':
+                self.assertEqual(s.count(letter), d.count(letter), (s, d, letter))
+        self.assertRaises(TypeError, d.count)       # too few args
+        self.assertRaises(TypeError, d.count, 1, 2) # too many args
+        class BadCompare:
+            def __eq__(self, other):
+                raise ArithmeticError
+        d = deque([1, 2, BadCompare(), 3])
+        self.assertRaises(ArithmeticError, d.count, 2)
+        d = deque([1, 2, 3])
+        self.assertRaises(ArithmeticError, d.count, BadCompare())
+        class MutatingCompare:
+            def __eq__(self, other):
+                self.d.pop()
+                return True
+        m = MutatingCompare()
+        d = deque([1, 2, 3, m, 4, 5])
+        m.d = d
+        self.assertRaises(RuntimeError, d.count, 3)
+
+        # test issue11004
+        # block advance failed after rotation aligned elements on right side of block
+        d = deque([None]*16)
+        for i in range(len(d)):
+            d.rotate(-1)
+        d.rotate(1)
+        self.assertEqual(d.count(1), 0)
+        self.assertEqual(d.count(None), 16)
+
     def test_comparisons(self):
         d = deque('xabc'); d.popleft()
         for e in [d, deque('abc'), deque('ab'), deque(), list(d)]:
         self.assertRaises(TypeError, d.extend, 1)
         d.extend('bcd')
         self.assertEqual(list(d), list('abcd'))
+        d.extend(d)
+        self.assertEqual(list(d), list('abcdabcd'))
+
+    def test_iadd(self):
+        d = deque('a')
+        d += 'bcd'
+        self.assertEqual(list(d), list('abcd'))
+        d += d
+        self.assertEqual(list(d), list('abcdabcd'))
 
     def test_extendleft(self):
         d = deque('a')
         self.assertRaises(TypeError, d.extendleft, 1)
         d.extendleft('bcd')
         self.assertEqual(list(d), list(reversed('abcd')))
+        d.extendleft(d)
+        self.assertEqual(list(d), list('abcddcba'))
         d = deque()
         d.extendleft(range(1000))
         self.assertEqual(list(d), list(reversed(range(1000))))
             self.assertEqual(len(d), n-i)
             j = random.randrange(-len(d), len(d))
             val = d[j]
-            self.assert_(val in d)
+            self.assertIn(val, d)
             del d[j]
-            self.assert_(val not in d)
+            self.assertNotIn(val, d)
         self.assertEqual(len(d), 0)
 
+    def test_reverse(self):
+        n = 500         # O(n**2) test, don't make this too big
+        data = [random.random() for i in range(n)]
+        for i in range(n):
+            d = deque(data[:i])
+            r = d.reverse()
+            self.assertEqual(list(d), list(reversed(data[:i])))
+            self.assertIs(r, None)
+            d.reverse()
+            self.assertEqual(list(d), data[:i])
+        self.assertRaises(TypeError, d.reverse, 1)          # Arity is zero
+
     def test_rotate(self):
         s = tuple('abcde')
         n = len(s)
         self.assertRaises(RuntimeError, d.remove, 'c')
         for x, y in zip(d, e):
             # verify that original order and values are retained.
-            self.assert_(x is y)
+            self.assertTrue(x is y)
 
         # Handle evil mutator
         for match in (True, False):
         e = eval(repr(d))
         self.assertEqual(list(d), list(e))
         d.append(d)
-        self.assert_('...' in repr(d))
+        self.assertIn('...', repr(d))
 
     def test_print(self):
         d = deque(xrange(200))
         d.append(d)
+        test_support.unlink(test_support.TESTFN)
+        fo = open(test_support.TESTFN, "wb")
         try:
-            fo = open(test_support.TESTFN, "wb")
             print >> fo, d,
             fo.close()
             fo = open(test_support.TESTFN, "rb")
             self.assertEqual(fo.read(), repr(d))
         finally:
             fo.close()
-            os.remove(test_support.TESTFN)
+            test_support.unlink(test_support.TESTFN)
 
     def test_init(self):
-        self.assertRaises(TypeError, deque, 'abc', 2);
+        self.assertRaises(TypeError, deque, 'abc', 2, 3);
         self.assertRaises(TypeError, deque, 1);
 
     def test_hash(self):
 
     def test_pickle(self):
         d = deque(xrange(200))
-        for i in (0, 1, 2):
+        for i in range(pickle.HIGHEST_PROTOCOL + 1):
             s = pickle.dumps(d, i)
             e = pickle.loads(s)
             self.assertNotEqual(id(d), id(e))
             self.assertEqual(list(d), list(e))
 
-    def test_pickle_recursive(self):
-        d = deque('abc')
-        d.append(d)
-        for i in (0, 1, 2):
-            e = pickle.loads(pickle.dumps(d, i))
-            self.assertNotEqual(id(d), id(e))
-            self.assertEqual(id(e), id(e[-1]))
+##    def test_pickle_recursive(self):
+##        d = deque('abc')
+##        d.append(d)
+##        for i in range(pickle.HIGHEST_PROTOCOL + 1):
+##            e = pickle.loads(pickle.dumps(d, i))
+##            self.assertNotEqual(id(d), id(e))
+##            self.assertEqual(id(e), id(e[-1]))
 
     def test_deepcopy(self):
         mut = [10]
             d.append(1)
             gc.collect()
 
+    def test_container_iterator(self):
+        # Bug #3680: tp_traverse was not implemented for deque iterator objects
+        class C(object):
+            pass
+        for i in range(2):
+            obj = C()
+            ref = weakref.ref(obj)
+            if i == 0:
+                container = deque([obj, 1])
+            else:
+                container = reversed(deque([obj, 1]))
+            obj.x = iter(container)
+            del obj, container
+            gc.collect()
+            self.assertTrue(ref() is None, "Cycle was not collected")
+
+    check_sizeof = test_support.check_sizeof
+
+    @test_support.cpython_only
+    def test_sizeof(self):
+        BLOCKLEN = 62
+        basesize = test_support.calcobjsize('2P4PlP')
+        blocksize = struct.calcsize('2P%dP' % BLOCKLEN)
+        self.assertEqual(object.__sizeof__(deque()), basesize)
+        check = self.check_sizeof
+        check(deque(), basesize + blocksize)
+        check(deque('a'), basesize + blocksize)
+        check(deque('a' * (BLOCKLEN // 2)), basesize + blocksize)
+        check(deque('a' * (BLOCKLEN // 2 + 1)), basesize + 2 * blocksize)
+        check(deque('a' * (42 * BLOCKLEN)), basesize + 43 * blocksize)
+
 class TestVariousIteratorArgs(unittest.TestCase):
 
     def test_constructor(self):
 class TestSubclass(unittest.TestCase):
 
     def test_basics(self):
-        d = Deque(xrange(100))
-        d.__init__(xrange(100, 200))
+        d = Deque(xrange(25))
+        d.__init__(xrange(200))
         for i in xrange(200, 400):
             d.append(i)
         for i in reversed(xrange(-200, 0)):
         self.assertEqual(type(d), type(e))
         self.assertEqual(list(d), list(e))
 
-    def test_pickle(self):
-        d = Deque('abc')
-        d.append(d)
+        d = Deque('abcde', maxlen=4)
 
-        e = pickle.loads(pickle.dumps(d))
+        e = d.__copy__()
+        self.assertEqual(type(d), type(e))
+        self.assertEqual(list(d), list(e))
+
+        e = Deque(d)
+        self.assertEqual(type(d), type(e))
+        self.assertEqual(list(d), list(e))
+
+        s = pickle.dumps(d)
+        e = pickle.loads(s)
         self.assertNotEqual(id(d), id(e))
         self.assertEqual(type(d), type(e))
-        dd = d.pop()
-        ee = e.pop()
-        self.assertEqual(id(e), id(ee))
-        self.assertEqual(d, e)
+        self.assertEqual(list(d), list(e))
 
-        d.x = d
-        e = pickle.loads(pickle.dumps(d))
-        self.assertEqual(id(e), id(e.x))
-
-        d = DequeWithBadIter('abc')
-        self.assertRaises(TypeError, pickle.dumps, d)
+##    def test_pickle(self):
+##        d = Deque('abc')
+##        d.append(d)
+##
+##        e = pickle.loads(pickle.dumps(d))
+##        self.assertNotEqual(id(d), id(e))
+##        self.assertEqual(type(d), type(e))
+##        dd = d.pop()
+##        ee = e.pop()
+##        self.assertEqual(id(e), id(ee))
+##        self.assertEqual(d, e)
+##
+##        d.x = d
+##        e = pickle.loads(pickle.dumps(d))
+##        self.assertEqual(id(e), id(e.x))
+##
+##        d = DequeWithBadIter('abc')
+##        self.assertRaises(TypeError, pickle.dumps, d)
 
     def test_weakref(self):
         d = deque('gallahad')
-        p = proxy(d)
+        p = weakref.proxy(d)
         self.assertEqual(str(p), str(d))
         d = None
         if test_support.is_jython:

Lib/test/test_deque_jy.py

+import time
+import random
+import unittest
+import threading
+from test import test_support
+from collections import deque
+
+
+class ThreadSafetyTestCase(unittest.TestCase):
+
+    def run_threads(self, f, num=10):
+        threads = []
+        for i in xrange(num):
+            t = threading.Thread(target=f)
+            t.start()
+            threads.append(t)
+        timeout = 10. # be especially generous
+        for t in threads:
+            t.join(timeout)
+            timeout = 0.
+        for t in threads:
+            self.assertFalse(t.isAlive())
+
+    def test_append_remove(self):
+        # derived from Itamar Shtull-Trauring's test for issue 521701
+        d = deque(['sentinel'])
+        def tester():
+            ct = threading.currentThread()
+            for i in range(1000):
+                d.append(ct)
+                time.sleep(0.0001)
+                d.remove(ct)
+        self.run_threads(tester)
+        self.assertEqual(d, deque(['sentinel']))
+
+    def test_append_pop(self):
+        d = deque(['sentinel'])
+        def tester():
+            ct = threading.currentThread()
+            for i in range(1000):
+                d.append(ct)
+                time.sleep(0.0001)
+                d.pop()
+        self.run_threads(tester)
+        self.assertEqual(d, deque(['sentinel']))
+
+    def test_appendleft_popleft(self):
+        d = deque()
+        def tester():
+            ct = threading.currentThread()
+            for i in range(1000):
+                d.appendleft(ct)
+                time.sleep(0.0001)
+                d.popleft()
+        self.run_threads(tester)
+        self.assertEqual(d, deque())
+
+    def test_count_reverse(self):
+        d = deque([0,1,2,3,4,5,6,7,8,9,10,0])
+        def tester():
+            ct = threading.currentThread()
+            for i in range(1000):
+                self.assertEqual(d[0], 0)
+                if random.random() > 0.5:
+                    time.sleep(0.0001)
+                d.reverse()
+                self.assertEqual(d.count(0), 2)
+                self.assert_(d[1] in (1,10))
+        self.run_threads(tester)
+
+
+def test_main():
+    test_support.run_unittest(ThreadSafetyTestCase)
+
+if __name__ == "__main__":
+    test_main()
+

src/org/python/modules/_collections/PyDeque.java

 package org.python.modules._collections;
 
+import org.python.core.ArgParser;
 import org.python.core.PyIterator;
+import org.python.core.PyList;
 import org.python.core.PyObject;
 import org.python.core.PyTuple;
 import org.python.core.PyType;
 import org.python.core.Py;
 import org.python.core.PyException;
-import org.python.core.PyBuiltinCallable;
 import org.python.core.ThreadState;
+import org.python.expose.ExposedGet;
 import org.python.expose.ExposedMethod;
 import org.python.expose.ExposedNew;
+import org.python.expose.ExposedSet;
 import org.python.expose.ExposedType;
 import org.python.expose.MethodType;
 
  * operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which
  * change both the size and position of the underlying data representation.
  * 
- * collections.deque([iterable]) - returns a new deque object initialized left-to-right (using
- * append()) with data from iterable. If iterable is not specified, the new deque is empty.
+ * collections.deque([iterable[, maxlen]]) - returns a new deque object initialized left-to-right
+ * (using append()) with data from iterable. If iterable is not specified, the new deque is empty.
+ * If maxlen is not specified or is None, deques may grow to an arbitrary length. Otherwise, the
+ * deque is bounded to the specified maximum length. Once a bounded length deque is full, when new
+ * items are added, a corresponding number of items are discarded from the opposite end.
  */
 @ExposedType(name = "collections.deque")
 public class PyDeque extends PyObject {
 
     public static final PyType TYPE = PyType.fromClass(PyDeque.class);
 
+    private long state = 0;
     private int size = 0;
 
-    private Node header = new Node(null, null, null); 
-    
+    private int maxlen = -1;
+
+    private Node header = new Node(null, null, null);
+
     public PyDeque() {
         this(TYPE);
     }
 
     @ExposedNew
     @ExposedMethod
-    final void deque___init__(PyObject[] args, String[] kwds) {
-        if (kwds.length > 0) {
-            throw Py.TypeError("deque() does not take keyword arguments");
+    public synchronized final void deque___init__(PyObject[] args, String[] kwds) {
+        ArgParser ap = new ArgParser("deque", args, kwds, new String[] {"iterable", "maxlen",}, 0);
+
+        PyObject maxlenobj = ap.getPyObject(1, null);
+        if (maxlenobj != null) {
+            if (maxlenobj == Py.None) {
+                maxlen = -1;
+            } else {
+                maxlen = ap.getInt(1);
+                if (maxlen < 0) {
+                    throw Py.ValueError("maxlen must be non-negative");
+                }
+            }
+        } else {
+            maxlen = -1;
         }
-        int nargs = args.length;
-        if (nargs > 1) {
-            throw PyBuiltinCallable.DefaultInfo.unexpectedCall(nargs, false, "deque", 0, 1);
-        } 
-        if (nargs == 0) {
-            return;
+
+        PyObject iterable = ap.getPyObject(0, null);
+        if (iterable != null) {
+            if (size != 0) {
+                // initializing a deque with an iterator when this deque is not empty means that we discard to empty first
+                deque_clear();
+            }
+            deque_extend(iterable);
         }
-        deque_extend(args[0]);
+    }
+
+    /**
+     * If maxlen is not specified or is None, deques may grow to an arbitrary length.
+     * Otherwise, the deque is bounded to the specified maximum length.
+     */
+    @ExposedGet(name = "maxlen")
+    public PyObject getMaxlen() {
+        if (maxlen < 0) {
+            return Py.None;
+        }
+        return Py.newInteger(maxlen);
+    }
+
+    @ExposedSet(name = "maxlen")
+    public void setMaxlen(PyObject o) {
+        // this has to be here because by default, if not defined,
+        // the Jython object model raise a TypeError, where we usually expect
+        // AttributeError here; due to a CPython 2.7 idiosyncracy that has
+        // since been fixed for 3.x in http://bugs.python.org/issue1687163
+        throw Py.AttributeError("attribute 'maxlen' of 'collections.deque' objects is not writable");
     }
 
     /**
      * Add obj to the right side of the deque.
      */	
     @ExposedMethod
-    final void deque_append(PyObject obj) {
-        addBefore(obj, header);		
+    public synchronized final void deque_append(PyObject obj) {
+        if (maxlen >= 0) {
+            assert (size <= maxlen);
+            if (maxlen == 0) {
+                // do nothing; this deque will always be empty
+                return;
+            } else if (size == maxlen) {
+                deque_popleft();
+            }
+        }
+        addBefore(obj, header);
     }
 
     /**
      * Add obj to the left side of the deque.
      */
     @ExposedMethod
-    final void deque_appendleft(PyObject obj) {		
+    public synchronized final void deque_appendleft(PyObject obj) {
+        if (maxlen >= 0) {
+            assert (size <= maxlen);
+            if (maxlen == 0) {
+                // do nothing; this deque will always be empty
+                return;
+            } else if (size == maxlen) {
+                deque_pop();
+            }
+        }
         addBefore(obj, header.right);
     }
 
     private Node addBefore(PyObject obj, Node node) {
+        // should ALWAYS be called inside a synchronized block
         Node newNode = new Node(obj, node, node.left);
         newNode.left.right = newNode;
         newNode.right.left = newNode;
         size++;
+        state++;
         return newNode;
     }
 
      * Remove all elements from the deque leaving it with length 0.
      */
     @ExposedMethod
-    final void deque_clear() {
+    public synchronized final void deque_clear() {
         Node node = header.right;
         while (node != header) {
             Node right = node.right;
             node.right = null;
             node.data = null;
             node = right;
+            state++;
         }
         header.right = header.left = header;
         size = 0;
      * iterable argument.
      */
     @ExposedMethod
-    final void deque_extend(PyObject iterable) {
-        for (PyObject item : iterable.asIterable()) {
-            deque_append(item);			
-        } 
+    public synchronized final void deque_extend(PyObject iterable) {
+        // handle case where iterable == this
+        if (this == iterable) {
+            deque_extend(new PyList(iterable));
+        } else {
+            for (PyObject item : iterable.asIterable()) {
+                deque_append(item);
+            }
+        }
     }
 
     /**
      * elements in the iterable argument.
      */
     @ExposedMethod
-    final void deque_extendleft(PyObject iterable) {
-        for (PyObject item : iterable.asIterable()) {
-            deque_appendleft(item);
+    public synchronized final void deque_extendleft(PyObject iterable) {
+        // handle case where iterable == this
+        if (this == iterable) {
+            deque_extendleft(new PyList(iterable));
+        } else {
+            for (PyObject item : iterable.asIterable()) {
+                deque_appendleft(item);
+            }
         }
     }
 
      * elements are present, raises an IndexError.
      */
     @ExposedMethod
-    final PyObject deque_pop() {
+    public synchronized final PyObject deque_pop() {
         return removeNode(header.left);
     }
 
      * elements are present, raises an IndexError.
      */
     @ExposedMethod
-    final PyObject deque_popleft() {
+    public synchronized final PyObject deque_popleft() {
         return removeNode(header.right);
     }
 
     private PyObject removeNode(Node node) {
+        // should ALWAYS be called inside a synchronized block
         if (node == header) {
             throw Py.IndexError("pop from an empty deque");
         }
         node.left = null;
         node.data = null;
         size--;
+        state++;
         return obj;
     } 
 
      * ValueError.
      */
     @ExposedMethod
-    final PyObject deque_remove(PyObject value) {
+    public synchronized final PyObject deque_remove(PyObject value) {
         int n = size;
         Node tmp = header.right;
         boolean match = false;
+        long startState = state;
         for (int i = 0; i < n; i++) {
-            if (tmp.data.equals(value)) { 
+            if (tmp.data.equals(value)) {
                 match = true;
             }
-            if (n != size) { 
+            if (startState != state) {
                 throw Py.IndexError("deque mutated during remove().");
             }
             if (match) {
     }
 
     /**
+     * Count the number of deque elements equal to x.
+     */
+    @ExposedMethod
+    public synchronized final PyObject deque_count(PyObject x) {
+        int n = size;
+        int count = 0;
+        Node tmp = header.right;
+        long startState = state;
+        for (int i = 0; i < n; i++) {
+            if (tmp.data.equals(x)) {
+                count++;
+            }
+            if (startState != state) {
+                throw Py.RuntimeError("deque mutated during count().");
+            }
+            tmp = tmp.right;
+        }
+        return Py.newInteger(count);
+    }
+
+    /**
      * Rotate the deque n steps to the right. If n is negative, rotate to the 
      * left. Rotating one step to the right is equivalent to: d.appendleft(d.pop()).
      */
     @ExposedMethod(defaults = {"1"})
-    final void deque_rotate(int steps) {
+    public synchronized final void deque_rotate(int steps) {
         if (size == 0) {
             return;
         }
 
-        int halfsize = (size + 1) >> 1; 
+        int halfsize = (size + 1) >> 1;
         if (steps > halfsize || steps < -halfsize) {
             steps %= size;
-            if (steps > halfsize) { 
+            if (steps > halfsize) {
                 steps -= size;
             } else if (steps < -halfsize) {
                 steps += size;
             }
         }
 
-        //rotate right 
+        //rotate right
         for (int i = 0; i < steps; i++) {
             deque_appendleft(deque_pop());
-        } 
+        }
         //rotate left
         for (int i = 0; i > steps; i--) {
             deque_append(deque_popleft());
-        } 
+        }
     }
 
+    /**
+     * Reverse the elements of the deque in-place and then return None.
+     * @return Py.None
+     */
+    @ExposedMethod
+    public synchronized final PyObject deque_reverse() {
+        Node headerRight = header.right;
+        Node headerLeft = header.left;
+        Node node = header.right;
+        while (node != header) {
+            Node right = node.right;
+            Node left = node.left;
+            node.right = left;
+            node.left = right;
+            node = right;
+        }
+        header.right = headerLeft;
+        header.left = headerRight;
+        state++;
+        return Py.None;
+    }
+
+    @Override
     public String toString() {
         return deque_toString();
     }
 
     @ExposedMethod(names = "__repr__")
-    final String deque_toString() {
+    synchronized final String deque_toString() {
         ThreadState ts = Py.getThreadState();
         if (!ts.enterRepr(this)) { 
             return "[...]";
         }
+        long startState = state;
         StringBuilder buf = new StringBuilder("deque").append("([");
         for (Node tmp = header.right; tmp != header; tmp = tmp.right) {
             buf.append(tmp.data.__repr__().toString());
+            if (startState != state) {
+                throw Py.RuntimeError("deque mutated during iteration.");
+            }
             if (tmp.right != header) {
                 buf.append(", ");
             }
         }
-        buf.append("])");
+        buf.append("]");
+        if (maxlen >= 0) {
+            buf.append(", maxlen=");
+            buf.append(maxlen);
+        }
+        buf.append(")");
         ts.exitRepr(this);
         return buf.toString();
     }
 
+    @Override
     public int __len__() {
         return deque___len__();
     }
 
     @ExposedMethod
-    final int deque___len__() {
+    synchronized final int deque___len__() {
         return size;
     }
 
+    @Override
     public boolean __nonzero__() {
         return deque___nonzero__();
     }
 
     @ExposedMethod
-    final boolean deque___nonzero__() {
+    synchronized final boolean deque___nonzero__() {
         return size != 0;
     }
 
+    @Override
     public PyObject __finditem__(PyObject key) {
         try {
             return deque___getitem__(key);
     }
 
     @ExposedMethod
-    final PyObject deque___getitem__(PyObject index) {
-        return getNode(index).data;				
-    }	
+    synchronized final PyObject deque___getitem__(PyObject index) {
+        return getNode(index).data;
+    }
 
+    @Override
     public void __setitem__(PyObject index, PyObject value) {
         deque___setitem__(index, value);
     }
 
     @ExposedMethod
-    final void deque___setitem__(PyObject index, PyObject value) {
+    synchronized final void deque___setitem__(PyObject index, PyObject value) {
         Node node = getNode(index).right;
         removeNode(node.left);
         addBefore(value, node);
-    }	
+    }
 
+    @Override
     public void __delitem__(PyObject key) {
         deque___delitem__(key);
     }
 
     @ExposedMethod
-    final void deque___delitem__(PyObject key) {
-        removeNode(getNode(key));
+    synchronized final void deque___delitem__(PyObject key) {
+            removeNode(getNode(key));
     }
 
     private Node getNode(PyObject index) {
+        // must ALWAYS be called inside a synchronized block
         int pos = 0;
         if (!index.isIndex()) {
             throw Py.TypeError(String.format("sequence index must be integer, not '%.200s'",
         return tmp;
     }
 
+    @Override
     public PyObject __iter__() {
         return deque___iter__();
     }
         return new PyDequeIter();
     }
 
+    @Override
     public synchronized PyObject __eq__(PyObject o) {
         return deque___eq__(o);
     }
         return (i < 0) ? Py.True : Py.False;
     }
 
+    @Override
     public synchronized PyObject __ne__(PyObject o) {
         return deque___ne__(o);
     }
         return (i < 0) ? Py.False : Py.True;
     }
 
+    @Override
     public synchronized PyObject __lt__(PyObject o) {
         return deque___lt__(o);
     }
         return __finditem__(i)._lt(o.__finditem__(i));
     }
 
+    @Override
     public synchronized PyObject __le__(PyObject o) {
         return deque___le__(o);
     }
         return __finditem__(i)._le(o.__finditem__(i));
     }
 
+    @Override
     public synchronized PyObject __gt__(PyObject o) {
         return deque___gt__(o);
     }
         return __finditem__(i)._gt(o.__finditem__(i));
     }
 
+    @Override
     public synchronized PyObject __ge__(PyObject o) {
         return deque___ge__(o);
     }
         return __finditem__(i)._ge(o.__finditem__(i));
     }
 
+    @Override
+    public synchronized PyObject __iadd__(PyObject o) {
+        return deque___iadd__(o);
+    }
+
+    @ExposedMethod(type = MethodType.BINARY)
+    final synchronized PyObject deque___iadd__(PyObject o) {
+        deque_extend(o);
+        return this;
+    }
+
     // Return value >= 0 is the index where the sequences differs.
     // -1: reached the end of o1 without a difference
     // -2: reached the end of both seqeunces without a difference
         return (ol1 < ol2) ? -1 : -3;
     }
 
+    @Override
     public int hashCode() {
         return deque_hashCode();
     }
         throw Py.TypeError("deque objects are unhashable");
     }
 
+    @Override
     public PyObject __reduce__() {
         return deque___reduce__();
     }
     private class PyDequeIter extends PyIterator {
 
         private Node lastReturned = header;
-        private int itersize;
+        private long startState;
 
         public PyDequeIter() {
-            itersize = size;
+            startState = state;
         }
 
-        public PyObject __iternext__() {        	   		
-            if (itersize != size) { 
-                throw Py.RuntimeError("deque changed size during iteration");
+        @Override
+        public PyObject __iternext__() {
+            synchronized (PyDeque.this) {
+                if (startState != state) {
+                    throw Py.RuntimeError("deque changed size during iteration");
+                }
+                if (lastReturned.right != header) {
+                    lastReturned = lastReturned.right;
+                    return lastReturned.data;
+                }
+                return null;
             }
-            if (lastReturned.right != header) {
-                lastReturned = lastReturned.right;
-                return lastReturned.data;
-            }
-            return null;
         }
     }
 }