Hello, Stefano Rivera, le sam. 13 déc. 2025 19:27:40 +0000, a ecrit: > I would not jump to the conclusion immediately that this is a serious bug in > python3.13, without more investigation.
I have now bisected the python repository and ended up on this commit. Reverting the minidom.py change by hand indeed does fix the testsuite. Samuel
commit ddcd2acd85d891a53e281c773b3093f9db953964 Author: Miss Islington (bot) <[email protected]> Date: Fri Dec 5 16:24:38 2025 +0100 [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]> diff --git a/Lib/test/test_minidom.py b/Lib/test/test_minidom.py index 4f25e9c..48f6f2a 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 db51f35..0a2ccc0 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 0000000..440bc77 --- /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.
