https://github.com/python/cpython/commit/ddcd2acd85d891a53e281c773b3093f9db953964 commit: ddcd2acd85d891a53e281c773b3093f9db953964 branch: 3.13 author: Miss Islington (bot) <[email protected]> committer: gpshead <[email protected]> date: 2025-12-05T15:24:38Z summary:
[3.13] gh-142145: Remove quadratic behavior in node ID cache clearing (GH-142146) (#142210) gh-142145: Remove quadratic behavior in node ID cache clearing (GH-142146) * Remove quadratic behavior in node ID cache clearing * Add news fragment --------- (cherry picked from commit 08d8e18ad81cd45bc4a27d6da478b51ea49486e4) Co-authored-by: Seth Michael Larson <[email protected]> Co-authored-by: Jacob Walls <[email protected]> files: A Misc/NEWS.d/next/Security/2025-12-01-09-36-45.gh-issue-142145.tcAUhg.rst M Lib/test/test_minidom.py M Lib/xml/dom/minidom.py diff --git a/Lib/test/test_minidom.py b/Lib/test/test_minidom.py index 4f25e9c2a03cb4..48f6f2a253797d 100644 --- a/Lib/test/test_minidom.py +++ b/Lib/test/test_minidom.py @@ -2,6 +2,7 @@ import copy import pickle +import time import io from test import support import unittest @@ -173,6 +174,23 @@ def testAppendChild(self): self.assertEqual(dom.documentElement.childNodes[-1].data, "Hello") dom.unlink() + def testAppendChildNoQuadraticComplexity(self): + impl = getDOMImplementation() + + newdoc = impl.createDocument(None, "some_tag", None) + top_element = newdoc.documentElement + children = [newdoc.createElement(f"child-{i}") for i in range(1, 2 ** 15 + 1)] + element = top_element + + start = time.time() + for child in children: + element.appendChild(child) + element = child + end = time.time() + + # This example used to take at least 30 seconds. + self.assertLess(end - start, 10) + def testAppendChildFragment(self): dom, orig, c1, c2, c3, frag = self._create_fragment_test_nodes() dom.documentElement.appendChild(frag) diff --git a/Lib/xml/dom/minidom.py b/Lib/xml/dom/minidom.py index db51f350ea0153..0a2ccc00f1857d 100644 --- a/Lib/xml/dom/minidom.py +++ b/Lib/xml/dom/minidom.py @@ -292,13 +292,6 @@ def _append_child(self, node): childNodes.append(node) node.parentNode = self -def _in_document(node): - # return True iff node is part of a document tree - while node is not None: - if node.nodeType == Node.DOCUMENT_NODE: - return True - node = node.parentNode - return False def _write_data(writer, text, attr): "Writes datachars to writer." @@ -1555,7 +1548,7 @@ def _clear_id_cache(node): if node.nodeType == Node.DOCUMENT_NODE: node._id_cache.clear() node._id_search_stack = None - elif _in_document(node): + elif node.ownerDocument: node.ownerDocument._id_cache.clear() node.ownerDocument._id_search_stack= None diff --git a/Misc/NEWS.d/next/Security/2025-12-01-09-36-45.gh-issue-142145.tcAUhg.rst b/Misc/NEWS.d/next/Security/2025-12-01-09-36-45.gh-issue-142145.tcAUhg.rst new file mode 100644 index 00000000000000..440bc7794c69ef --- /dev/null +++ b/Misc/NEWS.d/next/Security/2025-12-01-09-36-45.gh-issue-142145.tcAUhg.rst @@ -0,0 +1 @@ +Remove quadratic behavior in ``xml.minidom`` node ID cache clearing. _______________________________________________ Python-checkins mailing list -- [email protected] To unsubscribe send an email to [email protected] https://mail.python.org/mailman3//lists/python-checkins.python.org Member address: [email protected]
