[Python-checkins] cpython: Issue #14178: Problem deleting slices with steps != +1 in the _elementtree
eli.bendersky
python-checkins at python.org
Fri Mar 9 12:39:15 CET 2012
http://hg.python.org/cpython/rev/1a721b9a4039
changeset: 75505:1a721b9a4039
user: Eli Bendersky <eliben at gmail.com>
date: Fri Mar 09 13:38:15 2012 +0200
summary:
Issue #14178: Problem deleting slices with steps != +1 in the _elementtree module.
Fixed the problem and added some tests. Closes #14178
files:
Lib/test/test_xml_etree.py | 91 ++++++++++++++++++++++++-
Modules/_elementtree.c | 70 +++++++++++++++++++-
2 files changed, 153 insertions(+), 8 deletions(-)
diff --git a/Lib/test/test_xml_etree.py b/Lib/test/test_xml_etree.py
--- a/Lib/test/test_xml_etree.py
+++ b/Lib/test/test_xml_etree.py
@@ -1,10 +1,13 @@
# xml.etree test. This file contains enough tests to make sure that
# all included components work as they should.
# Large parts are extracted from the upstream test suite.
-
-# IMPORTANT: the same doctests are run from "test_xml_etree_c" in
-# order to ensure consistency between the C implementation and the
-# Python implementation.
+#
+# PLEASE write all new tests using the standard unittest infrastructure and
+# not doctest.
+#
+# IMPORTANT: the same tests are run from "test_xml_etree_c" in order
+# to ensure consistency between the C implementation and the Python
+# implementation.
#
# For this purpose, the module-level "ET" symbol is temporarily
# monkey-patched when running the "test_xml_etree_c" test suite.
@@ -1948,6 +1951,81 @@
self.assertEqual(pyET.Element.__module__, 'xml.etree.ElementTree')
self.assertEqual(pyET.SubElement.__module__, 'xml.etree.ElementTree')
+
+class ElementSlicingTest(unittest.TestCase):
+ def _elem_tags(self, elemlist):
+ return [e.tag for e in elemlist]
+
+ def _subelem_tags(self, elem):
+ return self._elem_tags(list(elem))
+
+ def _make_elem_with_children(self, numchildren):
+ """Create an Element with a tag 'a', with the given amount of children
+ named 'a0', 'a1' ... and so on.
+
+ """
+ e = ET.Element('a')
+ for i in range(numchildren):
+ ET.SubElement(e, 'a%s' % i)
+ return e
+
+ def test_getslice_single_index(self):
+ e = self._make_elem_with_children(10)
+
+ self.assertEqual(e[1].tag, 'a1')
+ self.assertEqual(e[-2].tag, 'a8')
+
+ self.assertRaises(IndexError, lambda: e[12])
+
+ def test_getslice_range(self):
+ e = self._make_elem_with_children(6)
+
+ self.assertEqual(self._elem_tags(e[3:]), ['a3', 'a4', 'a5'])
+ self.assertEqual(self._elem_tags(e[3:6]), ['a3', 'a4', 'a5'])
+ self.assertEqual(self._elem_tags(e[3:16]), ['a3', 'a4', 'a5'])
+ self.assertEqual(self._elem_tags(e[3:5]), ['a3', 'a4'])
+ self.assertEqual(self._elem_tags(e[3:-1]), ['a3', 'a4'])
+ self.assertEqual(self._elem_tags(e[:2]), ['a0', 'a1'])
+
+ def test_getslice_steps(self):
+ e = self._make_elem_with_children(10)
+
+ self.assertEqual(self._elem_tags(e[8:10:1]), ['a8', 'a9'])
+ self.assertEqual(self._elem_tags(e[::3]), ['a0', 'a3', 'a6', 'a9'])
+ self.assertEqual(self._elem_tags(e[::8]), ['a0', 'a8'])
+ self.assertEqual(self._elem_tags(e[1::8]), ['a1', 'a9'])
+
+ def test_getslice_negative_steps(self):
+ e = self._make_elem_with_children(4)
+
+ self.assertEqual(self._elem_tags(e[::-1]), ['a3', 'a2', 'a1', 'a0'])
+ self.assertEqual(self._elem_tags(e[::-2]), ['a3', 'a1'])
+
+ def test_delslice(self):
+ e = self._make_elem_with_children(4)
+ del e[0:2]
+ self.assertEqual(self._subelem_tags(e), ['a2', 'a3'])
+
+ e = self._make_elem_with_children(4)
+ del e[0:]
+ self.assertEqual(self._subelem_tags(e), [])
+
+ e = self._make_elem_with_children(4)
+ del e[::-1]
+ self.assertEqual(self._subelem_tags(e), [])
+
+ e = self._make_elem_with_children(4)
+ del e[::-2]
+ self.assertEqual(self._subelem_tags(e), ['a0', 'a2'])
+
+ e = self._make_elem_with_children(4)
+ del e[1::2]
+ self.assertEqual(self._subelem_tags(e), ['a0', 'a2'])
+
+ e = self._make_elem_with_children(2)
+ del e[::2]
+ self.assertEqual(self._subelem_tags(e), ['a1'])
+
# --------------------------------------------------------------------
@@ -1997,7 +2075,10 @@
# The same doctests are used for both the Python and the C implementations
test_xml_etree.ET = module
- test_classes = [ElementTreeTest, TreeBuilderTest]
+ test_classes = [
+ ElementSlicingTest,
+ ElementTreeTest,
+ TreeBuilderTest]
if module is pyET:
# Run the tests specific to the Python implementation
test_classes += [NoAcceleratorTest]
diff --git a/Modules/_elementtree.c b/Modules/_elementtree.c
--- a/Modules/_elementtree.c
+++ b/Modules/_elementtree.c
@@ -1343,9 +1343,74 @@
return -1;
}
- if (value == NULL)
- newlen = 0;
+ if (value == NULL) {
+ /* Delete slice */
+ size_t cur;
+ Py_ssize_t i;
+
+ if (slicelen <= 0)
+ return 0;
+
+ /* Since we're deleting, the direction of the range doesn't matter,
+ * so for simplicity make it always ascending.
+ */
+ if (step < 0) {
+ stop = start + 1;
+ start = stop + step * (slicelen - 1) - 1;
+ step = -step;
+ }
+
+ assert((size_t)slicelen <= PY_SIZE_MAX / sizeof(PyObject *));
+
+ /* recycle is a list that will contain all the children
+ * scheduled for removal.
+ */
+ if (!(recycle = PyList_New(slicelen))) {
+ PyErr_NoMemory();
+ return -1;
+ }
+
+ /* This loop walks over all the children that have to be deleted,
+ * with cur pointing at them. num_moved is the amount of children
+ * until the next deleted child that have to be "shifted down" to
+ * occupy the deleted's places.
+ * Note that in the ith iteration, shifting is done i+i places down
+ * because i children were already removed.
+ */
+ for (cur = start, i = 0; cur < (size_t)stop; cur += step, ++i) {
+ /* Compute how many children have to be moved, clipping at the
+ * list end.
+ */
+ Py_ssize_t num_moved = step - 1;
+ if (cur + step >= (size_t)self->extra->length) {
+ num_moved = self->extra->length - cur - 1;
+ }
+
+ PyList_SET_ITEM(recycle, i, self->extra->children[cur]);
+
+ memmove(
+ self->extra->children + cur - i,
+ self->extra->children + cur + 1,
+ num_moved * sizeof(PyObject *));
+ }
+
+ /* Leftover "tail" after the last removed child */
+ cur = start + (size_t)slicelen * step;
+ if (cur < (size_t)self->extra->length) {
+ memmove(
+ self->extra->children + cur - slicelen,
+ self->extra->children + cur,
+ (self->extra->length - cur) * sizeof(PyObject *));
+ }
+
+ self->extra->length -= slicelen;
+
+ /* Discard the recycle list with all the deleted sub-elements */
+ Py_XDECREF(recycle);
+ return 0;
+ }
else {
+ /* A new slice is actually being assigned */
seq = PySequence_Fast(value, "");
if (!seq) {
PyErr_Format(
@@ -1367,7 +1432,6 @@
return -1;
}
-
/* Resize before creating the recycle bin, to prevent refleaks. */
if (newlen > slicelen) {
if (element_resize(self, newlen - slicelen) < 0) {
--
Repository URL: http://hg.python.org/cpython
More information about the Python-checkins
mailing list