configparser: quadratic time in `ParsingError.combine()` when many lines fail to parse

[StanFromIreland]

Bug report

Bug description:

Found by OSS Fuzz in #501627726.

A simplified reproducer:

import time
import configparser

for N in (5000, 10000, 20000, 40000):
    s = '[*]\n' + '=\n' * N
    p = configparser.ConfigParser(strict=False)
    t0 = time.perf_counter()
    try:
        p.read_string(s)
    except configparser.ParsingError:
        pass
    print(f'{N}: {time.perf_counter() - t0}s')

produces:

5000: 0.5495022920076735s
10000: 2.0415573030040832s
20000: 7.589155077002943s
40000: 30.856201829999918s

CPython versions tested on:

CPython main branch

Operating systems tested on:

No response

Linked PRs

• gh-148370: prevent quadratic behavior in configparser.ParsingError.combine #148452
• [3.14] gh-148370: prevent quadratic behavior in configparser.ParsingError.combine (GH-148452) #148532
• [3.13] gh-148370: prevent quadratic behavior in configparser.ParsingError.combine (GH-148452) #148533

[adityakrmishra]

Hey @StanFromIreland I'd love to tackle this one! I suspect the quadratic time is being caused by repeated string concatenation (e.g., += or message = message + ...) in the error builder loop. I can submit a PR to optimize this by collecting the lines in a list and using ''.join(). Let me know if it's okay for me to get a PR up!

[picnixz]

Quadratic time may also arise from the regular expression itself. I would prefer someone more knowledgable taking this issue. The other possibility could also be before we call append().

In addition, we already collecwt the lines in a list.

[picnixz]

In addition, we need to be extra careful with backwards compatibility. message is constructed at every append call. We can't just change how we construct it as downstream consumers may use it a weird way.