Issue 23793: Add deque support for __add__(), __mul__(), and __imul__().

4 files changed, 204 insertions, 10 deletions

diff --git a/Doc/library/collections.rst b/Doc/library/collections.rst
index 2b4e4ba..dd6395d 100644
--- a/Doc/library/collections.rst
+++ b/Doc/library/collections.rst
@@ -526,6 +526,9 @@ the :keyword:`in` operator, and subscript references such as ``d[-1]``.  Indexed
 access is O(1) at both ends but slows to O(n) in the middle.  For fast random
 access, use lists instead.
 
+Starting in version 3.5, deques support ``__add__()``, ``__mul__()``,
+and ``__imul__()``.
+
 Example:
 
 .. doctest::
diff --git a/Lib/test/test_deque.py b/Lib/test/test_deque.py
index 07e5ef9..49d5dcf 100644
--- a/Lib/test/test_deque.py
+++ b/Lib/test/test_deque.py
@@ -192,6 +192,26 @@ class TestBasic(unittest.TestCase):
         d.extend(d)
         self.assertEqual(list(d), list('abcdabcd'))
 
+    def test_add(self):
+        d = deque()
+        e = deque('abc')
+        f = deque('def')
+        self.assertEqual(d + d, deque())
+        self.assertEqual(e + f, deque('abcdef'))
+        self.assertEqual(e + e, deque('abcabc'))
+        self.assertEqual(e + d, deque('abc'))
+        self.assertEqual(d + e, deque('abc'))
+        self.assertIsNot(d + d, deque())
+        self.assertIsNot(e + d, deque('abc'))
+        self.assertIsNot(d + e, deque('abc'))
+
+        g = deque('abcdef', maxlen=4)
+        h = deque('gh')
+        self.assertEqual(g + h, deque('efgh'))
+
+        with self.assertRaises(TypeError):
+            deque('abc') + 'def'
+
     def test_iadd(self):
         d = deque('a')
         d += 'bcd'
@@ -279,6 +299,63 @@ class TestBasic(unittest.TestCase):
             s.insert(i, 'Z')
             self.assertEqual(list(d), s)
 
+    def test_imul(self):
+        for n in (-10, -1, 0, 1, 2, 10, 1000):
+            d = deque()
+            d *= n
+            self.assertEqual(d, deque())
+            self.assertIsNone(d.maxlen)
+
+        for n in (-10, -1, 0, 1, 2, 10, 1000):
+            d = deque('a')
+            d *= n
+            self.assertEqual(d, deque('a' * n))
+            self.assertIsNone(d.maxlen)
+
+        for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
+            d = deque('a', 500)
+            d *= n
+            self.assertEqual(d, deque('a' * min(n, 500)))
+            self.assertEqual(d.maxlen, 500)
+
+        for n in (-10, -1, 0, 1, 2, 10, 1000):
+            d = deque('abcdef')
+            d *= n
+            self.assertEqual(d, deque('abcdef' * n))
+            self.assertIsNone(d.maxlen)
+
+        for n in (-10, -1, 0, 1, 2, 10, 499, 500, 501, 1000):
+            d = deque('abcdef', 500)
+            d *= n
+            self.assertEqual(d, deque(('abcdef' * n)[-500:]))
+            self.assertEqual(d.maxlen, 500)
+
+    def test_mul(self):
+        d = deque('abc')
+        self.assertEqual(d * -5, deque())
+        self.assertEqual(d * 0, deque())
+        self.assertEqual(d * 1, deque('abc'))
+        self.assertEqual(d * 2, deque('abcabc'))
+        self.assertEqual(d * 3, deque('abcabcabc'))
+        self.assertIsNot(d * 1, d)
+
+        self.assertEqual(deque() * 0, deque())
+        self.assertEqual(deque() * 1, deque())
+        self.assertEqual(deque() * 5, deque())
+
+        self.assertEqual(-5 * d, deque())
+        self.assertEqual(0 * d, deque())
+        self.assertEqual(1 * d, deque('abc'))
+        self.assertEqual(2 * d, deque('abcabc'))
+        self.assertEqual(3 * d, deque('abcabcabc'))
+
+        d = deque('abc', maxlen=5)
+        self.assertEqual(d * -5, deque())
+        self.assertEqual(d * 0, deque())
+        self.assertEqual(d * 1, deque('abc'))
+        self.assertEqual(d * 2, deque('bcabc'))
+        self.assertEqual(d * 30, deque('bcabc'))
+
     def test_setitem(self):
         n = 200
         d = deque(range(n))
diff --git a/Misc/NEWS b/Misc/NEWS
index ae08396..76b7ef7 100644
--- a/Misc/NEWS
+++ b/Misc/NEWS
@@ -152,6 +152,7 @@ Library
 - Issue #23704: collections.deque() objects now support methods for index(),
   insert(), and copy().  This allows deques to be registered as a
   MutableSequence and it improves their substitutablity for lists.
+  Deques now also support __add__, __mul__, and __imul__().
 
 - Issue #23715: :func:`signal.sigwaitinfo` and :func:`signal.sigtimedwait` are
   now retried when interrupted by a signal not in the *sigset* parameter, if
diff --git a/Modules/_collectionsmodule.c b/Modules/_collectionsmodule.c
index dbb2f8a..9f6c47f 100644
--- a/Modules/_collectionsmodule.c
+++ b/Modules/_collectionsmodule.c
@@ -110,6 +110,12 @@ static PyTypeObject deque_type;
 #define CHECK_NOT_END(link)
 #endif
 
+/* To prevent len from overflowing PY_SSIZE_T_MAX, we refuse to
+   allocate new blocks if the current len is nearing overflow.
+*/
+
+#define MAX_DEQUE_LEN (PY_SSIZE_T_MAX - 3*BLOCKLEN)
+
 /* A simple freelisting scheme is used to minimize calls to the memory
    allocator.  It accommodates common use cases where new blocks are being
    added at about the same rate as old blocks are being freed.
@@ -122,9 +128,7 @@ static block *freeblocks[MAXFREEBLOCKS];
 static block *
 newblock(Py_ssize_t len) {
     block *b;
-    /* To prevent len from overflowing PY_SSIZE_T_MAX, we refuse to
-     * allocate new blocks if the current len is nearing overflow. */
-    if (len >= PY_SSIZE_T_MAX - 2*BLOCKLEN) {
+    if (len >= MAX_DEQUE_LEN) {
         PyErr_SetString(PyExc_OverflowError,
                         "cannot add more blocks to the deque");
         return NULL;
@@ -498,6 +502,115 @@ deque_inplace_concat(dequeobject *deque, PyObject *other)
     return (PyObject *)deque;
 }
 
+static PyObject *deque_copy(PyObject *deque);
+
+static PyObject *
+deque_concat(dequeobject *deque, PyObject *other)
+{
+    PyObject *new_deque;
+    int rv;
+
+    rv = PyObject_IsInstance(other, (PyObject *)&deque_type);
+    if (rv <= 0) {
+        if (rv == 0) {
+            PyErr_Format(PyExc_TypeError,
+                         "can only concatenate deque (not \"%.200s\") to deque",
+                         other->ob_type->tp_name);
+        }
+        return NULL;
+    }
+
+    new_deque = deque_copy((PyObject *)deque);
+    if (new_deque == NULL)
+        return NULL;
+    return deque_inplace_concat((dequeobject *)new_deque, other);
+}
+
+static void deque_clear(dequeobject *deque);
+
+static PyObject *
+deque_repeat(dequeobject *deque, Py_ssize_t n)
+{
+    dequeobject *new_deque;
+    PyObject *result;
+
+    /* XXX add a special case for when maxlen is defined */
+    if (n < 0)
+        n = 0;
+    else if (n > 0 && Py_SIZE(deque) > MAX_DEQUE_LEN / n)
+        return PyErr_NoMemory();
+
+    new_deque = (dequeobject *)deque_new(&deque_type, (PyObject *)NULL, (PyObject *)NULL);
+    new_deque->maxlen = deque->maxlen;
+
+    for ( ; n ; n--) {
+        result = deque_extend(new_deque, (PyObject *)deque);
+        if (result == NULL) {
+            Py_DECREF(new_deque);
+            return NULL;
+        }
+        Py_DECREF(result);
+    }
+    return (PyObject *)new_deque;
+}
+
+static PyObject *
+deque_inplace_repeat(dequeobject *deque, Py_ssize_t n)
+{
+    Py_ssize_t i, size;
+    PyObject *seq;
+    PyObject *rv;
+
+    size = Py_SIZE(deque);
+    if (size == 0 || n == 1) {
+        Py_INCREF(deque);
+        return (PyObject *)deque;
+    }
+
+    if (n <= 0) {
+        deque_clear(deque);
+        Py_INCREF(deque);
+        return (PyObject *)deque;
+    }
+
+    if (size > MAX_DEQUE_LEN / n) {
+        return PyErr_NoMemory();
+    }
+
+    if (size == 1) {
+        /* common case, repeating a single element */
+        PyObject *item = deque->leftblock->data[deque->leftindex];
+
+        if (deque->maxlen != -1 && n > deque->maxlen)
+            n = deque->maxlen;
+
+        for (i = 0 ; i < n-1 ; i++) {
+            rv = deque_append(deque, item);
+            if (rv == NULL)
+                return NULL;
+            Py_DECREF(rv);
+        }
+        Py_INCREF(deque);
+        return (PyObject *)deque;
+    }
+
+    seq = PySequence_List((PyObject *)deque);
+    if (seq == NULL)
+        return seq;
+
+    for (i = 0 ; i < n-1 ; i++) {
+        rv = deque_extend(deque, seq);
+        if (rv == NULL) {
+            Py_DECREF(seq);
+            return NULL;
+        }
+        Py_DECREF(rv);
+    }
+    Py_INCREF(deque);
+    Py_DECREF(seq);
+    return (PyObject *)deque;
+}
+
 /* The rotate() method is part of the public API and is used internally
 as a primitive for other methods.
 
@@ -1283,6 +1396,9 @@ deque_get_maxlen(dequeobject *deque)
     return PyLong_FromSsize_t(deque->maxlen);
 }
 
+
+/* deque object ********************************************************/
+
 static PyGetSetDef deque_getset[] = {
     {"maxlen", (getter)deque_get_maxlen, (setter)NULL,
      "maximum size of a deque or None if unbounded"},
@@ -1291,15 +1407,15 @@ static PyGetSetDef deque_getset[] = {
 
 static PySequenceMethods deque_as_sequence = {
     (lenfunc)deque_len,                 /* sq_length */
-    0,                                  /* sq_concat */
-    0,                                  /* sq_repeat */
+    (binaryfunc)deque_concat,           /* sq_concat */
+    (ssizeargfunc)deque_repeat,         /* sq_repeat */
     (ssizeargfunc)deque_item,           /* sq_item */
     0,                                  /* sq_slice */
     (ssizeobjargproc)deque_ass_item,    /* sq_ass_item */
     0,                                  /* sq_ass_slice */
     (objobjproc)deque_contains,         /* sq_contains */
     (binaryfunc)deque_inplace_concat,   /* sq_inplace_concat */
-    0,                                  /* sq_inplace_repeat */
+    (ssizeargfunc)deque_inplace_repeat, /* sq_inplace_repeat */
 };
 
 static PyNumberMethods deque_as_number = {
@@ -1316,9 +1432,6 @@ static PyNumberMethods deque_as_number = {
     0,                                  /* nb_invert */
  };
 
-
-/* deque object ********************************************************/
-
 static PyObject *deque_iter(dequeobject *deque);
 static PyObject *deque_reviter(dequeobject *deque);
 PyDoc_STRVAR(reversed_doc,
@@ -1367,7 +1480,7 @@ static PyMethodDef deque_methods[] = {
 PyDoc_STRVAR(deque_doc,
 "deque([iterable[, maxlen]]) --> deque object\n\
 \n\
-Build an ordered collection with optimized access from its endpoints.");
+A list-like sequence optimized for data accesses near its endpoints.");
 
 static PyTypeObject deque_type = {
     PyVarObject_HEAD_INIT(NULL, 0)