GeezerVison

Summary

Node.normalize() merges adjacent text nodes with node.data = node.data + child.data, once per absorbed node. A run of n text nodes copies the growing string n times, so it's quadratic.

This collects the pieces for each run and joins them once at the end:

 for child in self.childNodes:
     ...
     elif L and L[-1].nodeType == child.nodeType:
-        node.data = node.data + child.data
+        runs[-1][1].append(child.data)   # or start a new run for node
     ...
+for node, data in runs:
+    node.data = ''.join(data)
 self.childNodes[:] = L

Sibling links are still fixed up inline, as before. runs is only created when something actually merges.

Parsing doesn't hit this, because expatbuilder already merges character data into the previous text node. You only get long runs from documents built through the DOM API.

Evidence

One element with n text-node children, 3.16 dev build, macOS arm64:

New test testNormalizeManyTextNodes (100k nodes, with an empty one every third node) takes 1.35 s before and 0.18 s after. Like the other complexity tests, it's slow-before / fast-after, not a hard timing assertion.

Differential check against the old normalize(): 20,000 random DOMs (text, empty text, elements, comments, nested). toxml() output and every parentNode / previousSibling / nextSibling link are identical.

test_minidom, test_pulldom, test_xml_dom_minicompat: 179 run, all pass.

Merge Danger

Door: two-way

Same result and same links. Only how the merged string gets built changes.

Blast Radius: a small slowdown when nothing merges

Normalizing an already-normal parsed document (200 items, 601 normalize() calls) went from about 102 µs to about 106 µs, measured over 10 alternating runs in both orders. That's the cost of the extra runs is None check, roughly 4 ns per call.

AI disclosure: the profiling and the patch were done with AI tools (Codex, Claude).

🤖 Generated with Claude Code

• Issue: xml.dom.minidom: Node.normalize() is quadratic in the number of adjacent text nodes #158860