https://github.com/python/cpython/commit/9c9dda6625a2a90d2a06c657eee021d6be19842d commit: 9c9dda6625a2a90d2a06c657eee021d6be19842d branch: 3.12 author: Miss Islington (bot) <[email protected]> committer: Yhg1s <[email protected]> date: 2025-12-22T14:48:49+01:00 summary:
[3.12] gh-142145: Remove quadratic behavior in node ID cache clearing (GH-142146) (#142211) * gh-142145: Remove quadratic behavior in node ID cache clearing (GH-142146) * gh-142754: Ensure that Element & Attr instances have the ownerDocument attribute (GH-142794) (cherry picked from commit 1cc7551b3f9f71efbc88d96dce90f82de98b2454) (cherry picked from commit 08d8e18ad81cd45bc4a27d6da478b51ea49486e4) (cherry picked from commit 8d2d7bb2e754f8649a68ce4116271a4932f76907) Co-authored-by: Jacob Walls <[email protected]> Co-authored-by: Seth Michael Larson <[email protected]> Co-authored-by: Petr Viktorin <[email protected]> Co-authored-by: Hugo van Kemenade <[email protected]> Co-authored-by: Gregory P. Smith <[email protected]> Co-authored-by: Hugo van Kemenade <[email protected]> Co-authored-by: Gregory P. Smith <[email protected]> Co-authored-by: Gregory P. Smith <[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 699265ccadc7f9..ab4823c8315e57 100644 --- a/Lib/test/test_minidom.py +++ b/Lib/test/test_minidom.py @@ -2,13 +2,14 @@ import copy import pickle +import time import io from test import support import unittest import xml.dom.minidom -from xml.dom.minidom import parse, Attr, Node, Document, parseString +from xml.dom.minidom import parse, Attr, Node, Document, Element, parseString from xml.dom.minidom import getDOMImplementation from xml.parsers.expat import ExpatError @@ -176,6 +177,36 @@ def testAppendChild(self): self.confirm(dom.documentElement.childNodes[-1].data == "Hello") dom.unlink() + @support.requires_resource('cpu') + 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.monotonic() + for child in children: + element.appendChild(child) + element = child + end = time.monotonic() + + # This example used to take at least 30 seconds. + # Conservative assertion due to the wide variety of systems and + # build configs timing based tests wind up run under. + # A --with-address-sanitizer --with-pydebug build on a rpi5 still + # completes this loop in <0.5 seconds. + self.assertLess(end - start, 4) + + def testSetAttributeNodeWithoutOwnerDocument(self): + # regression test for gh-142754 + elem = Element("test") + attr = Attr("id") + attr.value = "test-id" + elem.setAttributeNode(attr) + self.assertEqual(elem.getAttribute("id"), "test-id") + 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 ef8a159833bbc0..cada981f39f3ee 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, data): "Writes datachars to writer." @@ -355,6 +348,7 @@ class Attr(Node): def __init__(self, qName, namespaceURI=EMPTY_NAMESPACE, localName=None, prefix=None): self.ownerElement = None + self.ownerDocument = None self._name = qName self.namespaceURI = namespaceURI self._prefix = prefix @@ -680,6 +674,7 @@ class Element(Node): def __init__(self, tagName, namespaceURI=EMPTY_NAMESPACE, prefix=None, localName=None): + self.ownerDocument = None self.parentNode = None self.tagName = self.nodeName = tagName self.prefix = prefix @@ -1539,7 +1534,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..05c7df35d14bef --- /dev/null +++ b/Misc/NEWS.d/next/Security/2025-12-01-09-36-45.gh-issue-142145.tcAUhg.rst @@ -0,0 +1,6 @@ +Remove quadratic behavior in ``xml.minidom`` node ID cache clearing. In order +to do this without breaking existing users, we also add the *ownerDocument* +attribute to :mod:`xml.dom.minidom` elements and attributes created by directly +instantiating the ``Element`` or ``Attr`` class. Note that this way of creating +nodes is not supported; creator functions like +:py:meth:`xml.dom.Document.documentElement` should be used instead. _______________________________________________ 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]
