markshannon · Apr 10, 2024 · Apr 10, 2024 · Apr 11, 2024 · Apr 11, 2024 · Apr 11, 2024
diff --git a/Include/cpython/tupleobject.h b/Include/cpython/tupleobject.h
@@ -30,6 +30,7 @@ static inline Py_ssize_t PyTuple_GET_SIZE(PyObject *op) {
 static inline void
 PyTuple_SET_ITEM(PyObject *op, Py_ssize_t index, PyObject *value) {
     PyTupleObject *tuple = _PyTuple_CAST(op);
+    assert(value != NULL);
     assert(0 <= index);
     assert(index < Py_SIZE(tuple));
     tuple->ob_item[index] = value;

diff --git a/Include/internal/pycore_list.h b/Include/internal/pycore_list.h
@@ -55,6 +55,7 @@ typedef struct {
 } _PyListIterObject;
 
 PyAPI_FUNC(PyObject *)_PyList_FromArraySteal(PyObject *const *src, Py_ssize_t n);
+PyObject *_PyList_AsTupleStealItems(PyObject *);
 
 #ifdef __cplusplus
 }

diff --git a/Include/internal/pycore_tuple.h b/Include/internal/pycore_tuple.h
@@ -21,7 +21,7 @@ extern PyStatus _PyTuple_InitGlobalObjects(PyInterpreterState *);
 #define _PyTuple_ITEMS(op) _Py_RVALUE(_PyTuple_CAST(op)->ob_item)
 
 extern PyObject *_PyTuple_FromArray(PyObject *const *, Py_ssize_t);
-PyAPI_FUNC(PyObject *)_PyTuple_FromArraySteal(PyObject *const *, Py_ssize_t);
+PyAPI_FUNC(PyObject *)_PyTuple_FromNonEmptyArraySteal(PyObject *const *, Py_ssize_t);
 
 typedef struct {
     PyObject_HEAD

diff --git a/Lib/test/test_tuple.py b/Lib/test/test_tuple.py
@@ -416,6 +416,28 @@ def test_lexicographic_ordering(self):
         self.assertLess(a, b)
         self.assertLess(b, c)
 
+    def test_bug_59313(self):
+        # Until 3.13, the C-API function PySequence_Tuple
+        # would create incomplete tuples which were visible
+        # to the cycle GC
+        TAG = object()
+
+        def monitor():
+            lst = [x for x in gc.get_referrers(TAG)
+                if isinstance(x, tuple)]
+            t = lst[0]   # this *is* the result tuple
+            print(t)     # full of nulls !
+            return t     # Keep it alive for some time
+
+        def my_iter():
+            yield TAG    # 'tag' gets stored in the result tuple
+            t = monitor()
+            for x in range(10):
+                yield x  # SystemError when the tuple needs to be resized
+
+        with self.assertRaises(IndexError):
+            tuple(my_iter())
+
 # Notes on testing hash codes.  The primary thing is that Python doesn't
 # care about "random" hash codes.  To the contrary, we like them to be
 # very regular when possible, so that the low-order bits are as evenly

diff --git a/Misc/NEWS.d/next/Core and Builtins/2024-04-11-09-54-49.gh-issue-59313.ByDzOy.rst b/Misc/NEWS.d/next/Core and Builtins/2024-04-11-09-54-49.gh-issue-59313.ByDzOy.rst
@@ -0,0 +1,3 @@
+Make sure that all tuple elements are valid and never NULL. Ensuring that
+tuples are always valid reduces the risk of cycle GC bugs and prevents
+``gc.get_referrers`` from returning invalid tuples.
diff --git a/Modules/_testbuffer.c b/Modules/_testbuffer.c
@@ -333,10 +333,10 @@ pack_from_list(PyObject *obj, PyObject *items, PyObject *format,
 
     offset = NULL;
     for (i = 0; i < nitems; i++) {
-        /* Loop invariant: args[j] are borrowed references or NULL. */
+        /* Loop invariant: args[j] are borrowed references or None. */
         PyTuple_SET_ITEM(args, 0, obj);
         for (j = 1; j < 2+nmemb; j++)
-            PyTuple_SET_ITEM(args, j, NULL);
+            PyTuple_SET_ITEM(args, j, Py_None);
 
         Py_XDECREF(offset);
         offset = PyLong_FromSsize_t(i*itemsize);

@@ -4473,7 +4473,7 @@ zip_longest_next(ziplongestobject *lz)
         Py_INCREF(result);
         for (i=0 ; i < tuplesize ; i++) {
             it = PyTuple_GET_ITEM(lz->ittuple, i);
-            if (it == NULL) {
+            if (it == Py_None) {
                 item = Py_NewRef(lz->fillvalue);
             } else {
                 item = PyIter_Next(it);
@@ -4485,7 +4485,7 @@ zip_longest_next(ziplongestobject *lz)
                         return NULL;
                     } else {
                         item = Py_NewRef(lz->fillvalue);
-                        PyTuple_SET_ITEM(lz->ittuple, i, NULL);
+                        PyTuple_SET_ITEM(lz->ittuple, i, Py_None);
                         Py_DECREF(it);
                     }
                 }
@@ -4505,7 +4505,7 @@ zip_longest_next(ziplongestobject *lz)
             return NULL;
         for (i=0 ; i < tuplesize ; i++) {
             it = PyTuple_GET_ITEM(lz->ittuple, i);
-            if (it == NULL) {
+            if (it == Py_None) {
                 item = Py_NewRef(lz->fillvalue);
             } else {
                 item = PyIter_Next(it);
@@ -4517,7 +4517,7 @@ zip_longest_next(ziplongestobject *lz)
                         return NULL;
                     } else {
                         item = Py_NewRef(lz->fillvalue);
-                        PyTuple_SET_ITEM(lz->ittuple, i, NULL);
+                        PyTuple_SET_ITEM(lz->ittuple, i, Py_None);
                         Py_DECREF(it);
                     }
                 }
@@ -4542,7 +4542,7 @@ zip_longest_reduce(ziplongestobject *lz, PyObject *Py_UNUSED(ignored))
         return NULL;
     for (i=0; i<PyTuple_GET_SIZE(lz->ittuple); i++) {
         PyObject *elem = PyTuple_GET_ITEM(lz->ittuple, i);
-        if (elem == NULL) {
+        if (elem == Py_None) {
             elem = PyTuple_New(0);
             if (elem == NULL) {
                 Py_DECREF(args);

diff --git a/Objects/abstract.c b/Objects/abstract.c
@@ -2040,8 +2040,6 @@ PySequence_Tuple(PyObject *v)
 {
     PyObject *it;  /* iter(v) */
     Py_ssize_t n;             /* guess for result tuple size */
-    PyObject *result = NULL;
-    Py_ssize_t j;
 
     if (v == NULL) {
         return null_error();
@@ -2067,53 +2065,31 @@ PySequence_Tuple(PyObject *v)
     n = PyObject_LengthHint(v, 10);
     if (n == -1)
         goto Fail;
-    result = PyTuple_New(n);
-    if (result == NULL)
+    PyObject *temp = PyList_New(0);
+    if (temp == NULL)
         goto Fail;
 
-    /* Fill the tuple. */
-    for (j = 0; ; ++j) {
+    /* Fill the temporary list. */
+    for (;;) {
         PyObject *item = PyIter_Next(it);
         if (item == NULL) {
-            if (PyErr_Occurred())
+            if (PyErr_Occurred()) {
+                Py_DECREF(temp);
                 goto Fail;
+            }
             break;
         }
-        if (j >= n) {
-            size_t newn = (size_t)n;
-            /* The over-allocation strategy can grow a bit faster
-               than for lists because unlike lists the
-               over-allocation isn't permanent -- we reclaim
-               the excess before the end of this routine.
-               So, grow by ten and then add 25%.
-            */
-            newn += 10u;
-            newn += newn >> 2;
-            if (newn > PY_SSIZE_T_MAX) {
-                /* Check for overflow */
-                PyErr_NoMemory();
-                Py_DECREF(item);
-                goto Fail;
-            }
-            n = (Py_ssize_t)newn;
-            if (_PyTuple_Resize(&result, n) != 0) {
-                Py_DECREF(item);
-                goto Fail;
-            }
+        if (_PyList_AppendTakeRef((PyListObject *)temp, item)) {
+            Py_DECREF(temp);
+            goto Fail;
         }
-        PyTuple_SET_ITEM(result, j, item);
     }
-
-    /* Cut tuple back if guess was too large. */
-    if (j < n &&
-        _PyTuple_Resize(&result, j) != 0)
-        goto Fail;
-
     Py_DECREF(it);
+    PyObject *result = _PyList_AsTupleStealItems(temp);
+    Py_DECREF(temp);
     return result;
 
 Fail:
-    Py_XDECREF(result);
     Py_DECREF(it);
     return NULL;
 }

diff --git a/Objects/listobject.c b/Objects/listobject.c
@@ -3174,6 +3174,25 @@ PyList_AsTuple(PyObject *v)
     return ret;
 }
 
+PyObject *
+_PyList_AsTupleStealItems(PyObject *v)
+{
+    if (v == NULL || !PyList_Check(v)) {
+        PyErr_BadInternalCall();
+        return NULL;
+    }
+    PyObject *ret;
+    PyListObject *self = (PyListObject *)v;
+    if (Py_SIZE(v) == 0) {
+        return PyTuple_New(0);
+    }
+    Py_BEGIN_CRITICAL_SECTION(self);
+    ret = _PyTuple_FromNonEmptyArraySteal(self->ob_item, Py_SIZE(v));
+    Py_SET_SIZE(v, 0);
+    Py_END_CRITICAL_SECTION();
+    return ret;
+}
+
 PyObject *
 _PyList_FromArraySteal(PyObject *const *src, Py_ssize_t n)
 {

diff --git a/Objects/tupleobject.c b/Objects/tupleobject.c
@@ -34,14 +34,7 @@ static inline int maybe_freelist_push(PyTupleObject *);
 static PyTupleObject *
 tuple_alloc(Py_ssize_t size)
 {
-    if (size < 0) {
-        PyErr_BadInternalCall();
-        return NULL;
-    }
-#ifdef Py_DEBUG
-    assert(size != 0);    // The empty tuple is statically allocated.
-#endif
-
+    assert(size > 0);
     PyTupleObject *op = maybe_freelist_pop(size);
     if (op == NULL) {
         /* Check for overflow */
@@ -78,7 +71,7 @@ PyTuple_New(Py_ssize_t size)
         return NULL;
     }
     for (Py_ssize_t i = 0; i < size; i++) {
-        op->ob_item[i] = NULL;
+        op->ob_item[i] = Py_None;
     }
     _PyObject_GC_TRACK(op);
     return (PyObject *) op;
@@ -205,7 +198,8 @@ tupledealloc(PyTupleObject *op)
 
     Py_ssize_t i = Py_SIZE(op);
     while (--i >= 0) {
-        Py_XDECREF(op->ob_item[i]);
+        assert(op->ob_item[i] != NULL);
+        Py_DECREF(op->ob_item[i]);
     }
     // This will abort on the empty singleton (if there is one).
     if (!maybe_freelist_push(op)) {
@@ -391,11 +385,8 @@ _PyTuple_FromArray(PyObject *const *src, Py_ssize_t n)
 }
 
 PyObject *
-_PyTuple_FromArraySteal(PyObject *const *src, Py_ssize_t n)
+_PyTuple_FromNonEmptyArraySteal(PyObject *const *src, Py_ssize_t n)
 {
-    if (n == 0) {
-        return tuple_get_empty();
-    }
     PyTupleObject *tuple = tuple_alloc(n);
     if (tuple == NULL) {
         for (Py_ssize_t i = 0; i < n; i++) {

@@ -96,7 +96,7 @@ clear_weakref_lock_held(PyWeakReference *self, PyObject **callback)
         self->wr_prev = NULL;
         self->wr_next = NULL;
     }
-    if (callback != NULL) {
+    if (callback != NULL && self->wr_callback != NULL) {
         *callback = self->wr_callback;
         self->wr_callback = NULL;
     }
@@ -999,7 +999,7 @@ PyObject_ClearWeakRefs(PyObject *object)
     for (int done = 0; !done;) {
         LOCK_WEAKREFS(object);
         if (*list != NULL && is_basic_ref_or_proxy(*list)) {
-            PyObject *callback;
+            PyObject *callback = NULL;
             clear_weakref_lock_held(*list, &callback);
             assert(callback == NULL);
         }
@@ -1022,7 +1022,7 @@ PyObject_ClearWeakRefs(PyObject *object)
 
     Py_ssize_t num_items = 0;
     for (int done = 0; !done;) {
-        PyObject *callback = NULL;
+        PyObject *callback = Py_None;
         LOCK_WEAKREFS(object);
         PyWeakReference *cur = *list;
         if (cur != NULL) {
@@ -1032,18 +1032,18 @@ PyObject_ClearWeakRefs(PyObject *object)
                 PyTuple_SET_ITEM(tuple, num_items, (PyObject *) cur);
                 PyTuple_SET_ITEM(tuple, num_items + 1, callback);
                 num_items += 2;
-                callback = NULL;
+                callback = Py_None;
             }
         }
         done = (*list == NULL);
         UNLOCK_WEAKREFS(object);
 
-        Py_XDECREF(callback);
+        Py_DECREF(callback);
     }
 
     for (Py_ssize_t i = 0; i < num_items; i += 2) {
         PyObject *callback = PyTuple_GET_ITEM(tuple, i + 1);
-        if (callback != NULL) {
+        if (callback != Py_None) {
             PyObject *weakref = PyTuple_GET_ITEM(tuple, i);
             handle_callback((PyWeakReference *)weakref, callback);
         }

diff --git a/Python/bytecodes.c b/Python/bytecodes.c
@@ -1587,7 +1587,8 @@ dummy_func(
         }
 
         inst(BUILD_TUPLE, (values[oparg] -- tup)) {
-            tup = _PyTuple_FromArraySteal(values, oparg);
+            assert(oparg != 0);
+            tup = _PyTuple_FromNonEmptyArraySteal(values, oparg);
             ERROR_IF(tup == NULL, error);
         }
 

diff --git a/Python/ceval.c b/Python/ceval.c
@@ -1458,7 +1458,7 @@ initialize_locals(PyThreadState *tstate, PyFunctionObject *func,
         }
         else {
             assert(args != NULL);
-            u = _PyTuple_FromArraySteal(args + n, argcount - n);
+            u = _PyTuple_FromNonEmptyArraySteal(args + n, argcount - n);
         }
         if (u == NULL) {
             goto fail_post_positional;

diff --git a/Python/executor_cases.c.h b/Python/executor_cases.c.h
diff --git a/Python/generated_cases.c.h b/Python/generated_cases.c.h
diff --git a/Python/optimizer.c b/Python/optimizer.c
@@ -369,7 +369,7 @@ uop_item(_PyExecutorObject *self, Py_ssize_t index)
         return NULL;
     }
     PyObject *args[4] = { oname, oparg, target, operand };
-    return _PyTuple_FromArraySteal(args, 4);
+    return _PyTuple_FromNonEmptyArraySteal(args, 4);
 }
 
 PySequenceMethods uop_as_sequence = {

diff --git a/Tools/cases_generator/analyzer.py b/Tools/cases_generator/analyzer.py
@@ -396,7 +396,7 @@ def has_error_without_pop(op: parser.InstDef) -> bool:
     "_PyType_HasFeature",
     "PyUnicode_Concat",
     "_PyList_FromArraySteal",
-    "_PyTuple_FromArraySteal",
+    "_PyTuple_FromNonEmptyArraySteal",
     "PySlice_New",
     "_Py_LeaveRecursiveCallPy",
     "CALL_STAT_INC",