Update of /cvsroot/python/python/dist/src/Objects In directory sc8-pr-cvs1.sourceforge.net:/tmp/cvs-serv7074/Objects Modified Files: listobject.c Log Message: Armin asked for a list_ass_slice review in his checkin, so here's the result. list_resize(): Document the intent. Code is increasingly relying on subtle aspects of its behavior, and they deserve to be spelled out. list_ass_slice(): A bit more simplification, by giving it a common error exit and initializing more values. Be clearer in comments about what "size" means (# of elements? # of bytes?). While the number of elements in a list slice must fit in an int, there's no guarantee that the number of bytes occupied by the slice will. That malloc() and memmove() take size_t arguments is a hint about that <wink>. So changed to use size_t where appropriate. ihigh - ilow should always be >= 0, but we never asserted that. We do now. The loop decref'ing the recycled slice had a subtle insecurity: C doesn't guarantee that a pointer one slot *before* an array will compare "less than" to a pointer within the array (it does guarantee that a pointer one beyond the end of the array compares as expected). This was actually an issue in KSR's C implementation, so isn't purely theoretical. Python probably has other "go backwards" loops with a similar glitch. list_clear() is OK (it marches an integer backwards, not a pointer). Index: listobject.c =================================================================== RCS file: /cvsroot/python/python/dist/src/Objects/listobject.c,v retrieving revision 2.215 retrieving revision 2.216 diff -C2 -d -r2.215 -r2.216 *** listobject.c 30 Jul 2004 11:38:22 -0000 2.215 --- listobject.c 31 Jul 2004 02:24:20 -0000 2.216 *************** *** 9,12 **** --- 9,25 ---- #endif + /* Ensure ob_item has room for at least newsize elements, and set + * ob_size to newsize. If newsize > ob_size on entry, the content + * of the new slots at exit is undefined heap trash; it's the caller's + * responsiblity to overwrite them with sane values. + * The number of allocated elements may grow, shrink, or stay the same. + * Failure is impossible if newsize <= self.allocated on entry, although + * that partly relies on an assumption that the system realloc() never + * fails when passed a number of bytes <= the number of bytes last + * allocated (the C standard doesn't guarantee this, but it's hard to + * imagine a realloc implementation where it wouldn't be true). + * Note that self->ob_item may change, and even if newsize is less + * than ob_size on entry. + */ static int list_resize(PyListObject *self, int newsize) *************** *** 19,23 **** current size, then proceed with the realloc() to shrink the list. */ - if (self->allocated >= newsize && self->ob_size < newsize + 16) { assert(self->ob_item != NULL || newsize == 0); --- 32,35 ---- *************** *** 517,529 **** we temporarily copy the items that are deleted from the list. :-( */ - PyObject **recycle, **p; PyObject *recycled[8]; PyObject **item; PyObject **vitem = NULL; PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */ ! int n; /* Size of replacement list */ int d; /* Change in size */ int k; /* Loop index */ ! int s; #define b ((PyListObject *)v) if (v == NULL) --- 529,543 ---- we temporarily copy the items that are deleted from the list. :-( */ PyObject *recycled[8]; + PyObject **recycle = recycled; /* will allocate more if needed */ PyObject **item; PyObject **vitem = NULL; PyObject *v_as_SF = NULL; /* PySequence_Fast(v) */ ! int n; /* # of elements in replacement list */ ! int norig; /* # of elements in list getting replaced */ int d; /* Change in size */ int k; /* Loop index */ ! size_t s; ! int result = -1; /* guilty until proved innocent */ #define b ((PyListObject *)v) if (v == NULL) *************** *** 532,546 **** if (a == b) { /* Special case "a[i:j] = a" -- copy b first */ - int ret; v = list_slice(b, 0, b->ob_size); if (v == NULL) ! return -1; ! ret = list_ass_slice(a, ilow, ihigh, v); Py_DECREF(v); ! return ret; } v_as_SF = PySequence_Fast(v, "can only assign an iterable"); if(v_as_SF == NULL) ! return -1; n = PySequence_Fast_GET_SIZE(v_as_SF); vitem = PySequence_Fast_ITEMS(v_as_SF); --- 546,559 ---- if (a == b) { /* Special case "a[i:j] = a" -- copy b first */ v = list_slice(b, 0, b->ob_size); if (v == NULL) ! return result; ! result = list_ass_slice(a, ilow, ihigh, v); Py_DECREF(v); ! return result; } v_as_SF = PySequence_Fast(v, "can only assign an iterable"); if(v_as_SF == NULL) ! goto Error; n = PySequence_Fast_GET_SIZE(v_as_SF); vitem = PySequence_Fast_ITEMS(v_as_SF); *************** *** 550,553 **** --- 563,567 ---- else if (ilow > a->ob_size) ilow = a->ob_size; + if (ihigh < ilow) ihigh = ilow; *************** *** 555,559 **** ihigh = a->ob_size; ! d = n - (ihigh-ilow); if (a->ob_size + d == 0) { Py_XDECREF(v_as_SF); --- 569,575 ---- ihigh = a->ob_size; ! norig = ihigh - ilow; ! assert(norig >= 0); ! d = n - norig; if (a->ob_size + d == 0) { Py_XDECREF(v_as_SF); *************** *** 561,578 **** } item = a->ob_item; ! /* recycle the ihigh-ilow items that we are about to remove */ ! s = (ihigh - ilow)*sizeof(PyObject *); if (s > sizeof(recycled)) { recycle = (PyObject **)PyMem_MALLOC(s); if (recycle == NULL) { PyErr_NoMemory(); ! Py_XDECREF(v_as_SF); ! return -1; } } - else - recycle = recycled; - p = recycle + (ihigh - ilow); memcpy(recycle, &item[ilow], s); if (d < 0) { /* Delete -d items */ memmove(&item[ihigh+d], &item[ihigh], --- 577,591 ---- } item = a->ob_item; ! /* recycle the items that we are about to remove */ ! s = norig * sizeof(PyObject *); if (s > sizeof(recycled)) { recycle = (PyObject **)PyMem_MALLOC(s); if (recycle == NULL) { PyErr_NoMemory(); ! goto Error; } } memcpy(recycle, &item[ilow], s); + if (d < 0) { /* Delete -d items */ memmove(&item[ihigh+d], &item[ihigh], *************** *** 583,592 **** else if (d > 0) { /* Insert d items */ s = a->ob_size; ! if (list_resize(a, s+d) == -1) { ! if (recycle != recycled) ! PyMem_FREE(recycle); ! Py_XDECREF(v_as_SF); ! return -1; ! } item = a->ob_item; memmove(&item[ihigh+d], &item[ihigh], --- 596,601 ---- else if (d > 0) { /* Insert d items */ s = a->ob_size; ! if (list_resize(a, s+d) < 0) ! goto Error; item = a->ob_item; memmove(&item[ihigh+d], &item[ihigh], *************** *** 598,607 **** item[ilow] = w; } ! while (--p >= recycle) ! Py_XDECREF(*p); if (recycle != recycled) PyMem_FREE(recycle); Py_XDECREF(v_as_SF); ! return 0; #undef b } --- 607,625 ---- item[ilow] = w; } ! /* Convoluted: there's some obscure reason for wanting to do ! * the decrefs "backwards", but C doesn't guarantee you can compute ! * a pointer to one slot *before* an allocated vector. So checking ! * for item >= recycle is incorrect. ! */ ! for (item = recycle + norig; item > recycle; ) { ! --item; ! Py_XDECREF(*item); ! } ! result = 0; ! Error: if (recycle != recycled) PyMem_FREE(recycle); Py_XDECREF(v_as_SF); ! return result; #undef b }