Bug report

Bug description:

On main, csv.Sniffer().sniff() takes quadratic time when the sample contains a quote character and a long run of spaces that is not followed by one:

import csv, time

for n in (8000, 16000, 32000, 64000):
    sample = 'a' + ' ' * n + 'x"\n'
    t = time.perf_counter()
    try:
        csv.Sniffer().sniff(sample)
    except csv.Error:
        pass
    print(n, round(time.perf_counter() - t, 4))

Seconds, on macOS 27.0.1 (Apple M3):

The sample ('a,b' + ' ' * 100_000 + 'c"\n') * 4 takes 23.2 s on main and 0.06 s with the fix.

The cause is the regex in Sniffer._split_dormant() (Lib/csv.py):

m = re.compile(fr'(?:^|([\r\n{cls}]))'
               fr' *{quotechar}').search(part, pos)

The space is a delimiter candidate whenever the sample contains one, so it is in cls. The search then tries a match at every space of the run: [...] matches that space, * consumes the rest of the run, and the match fails on the next character. A run of n spaces costs O(n**2).

A match that starts at a space preceded by a space is never the leftmost one: a match with the same group and the same end also starts at the beginning of the run. Adding the lookbehind (?<! ) after the group skips those positions without changing any result.

This was introduced in gh-83273 (25fea6d) and is in 3.16.0a1. 3.15 and older are not affected.

CPython versions tested on:

3.15, CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-160556: Fix quadratic time in csv.Sniffer with long runs of spaces #160557