Bug report

Bug description:

xml.dom.minidom.parse() and parseString() take time quadratic in the number of pieces in which Expat delivers a run of character data. xml.dom.expatbuilder extends the current Text node with node.data = node.data + data on every CharacterDataHandler call, and pyexpat flushes its text buffer before every other handler, so markup that adds no node (an empty CDATA section, a reference to an external entity) splits one text node into many callbacks. With the pieces placed in an internal entity that is referenced repeatedly, a few kilobytes of input are enough.

Whoever supplies the document controls this; a program that parses XML from an untrusted source with minidom's default arguments can be made to spend about a minute of CPU on a 7 kB document.

import time
from xml.dom import minidom

def make(k):
    return ('<!DOCTYPE r [<!ENTITY x "%s">]><r>%s</r>'
            % ('ab<![CDATA[]]>' * k, '&x;' * k))

for k in 100, 200, 400:
    doc = make(k)
    t = time.process_time()
    dom = minidom.parseString(doc)
    t = time.process_time() - t
    print(f'{len(doc)} bytes -> {len(dom.documentElement.firstChild.data)} chars of text, {t:.2f} s')

Output on a debug build of main:

1736 bytes -> 20000 chars of text, 0.44 s
3436 bytes -> 80000 chars of text, 3.25 s
6836 bytes -> 320000 chars of text, 68.81 s

The time should grow with the amount of text (4x per step here), not with its square. The code is unchanged since Python 2.3. gh-158860 is the same pattern in Node.normalize(); gh-142145 was a similar issue elsewhere in minidom.

CPython versions tested on:

CPython main branch

Operating systems tested on:

Linux

Linked PRs

• gh-160525: Fix quadratic text concatenation in xml.dom.expatbuilder #160526