Repository navigation
csv.Sniffer regular expression has significant backtracing #109638
Description
Bug report
Bug description:
You can pass strings to csv.Sniffer that can generate significant Regex backtracing and processing time. For example
import csv
import time
NUM_ITERATIONS=200
# Example test str "","",""0""0
test_str = '"",'*NUM_ITERATIONS + '"'*NUM_ITERATIONS + '0' + '"'*NUM_ITERATIONS + '0'
print(test_str)
t0 = time.time()
dialect = csv.Sniffer().sniff(test_str)
t1 = time.time()
print(f"{t1-t0}")Some example runs
NUM_ITERATIONS Running Time (seconds)
1 0.0008
10 0.0030
100 254.32
I've checked against different versions of Python and they all return similar results.
For input NUM_ITERATIONS 100 above
Version : Running Time (Seconds)
Python 3.8.16 : 254
Python 3.9.16 : 250
Python 3.10.9 : 319
Python 3.11.1 : 236
This issue lies in this Regex for finding double quoted format
Line 274 in b303d3a
I've done some testing and a zero length lookahead assertion (or atomic group) you can get a significant performance improvement
r"((%(delim)s)|^)\W*%(quote)s(?=(?P<zero>[^%(delim)s%(quote)s\n]*))(?P=zero)%(quote)s[^%(delim)s\n]*%(quote)s\W*((%(delim)s)|$)" % \
CPython versions tested on:
3.8, 3.9, 3.10, 3.11
Operating systems tested on:
Linux
Linked PRs
- gh-109638: Fix for significant backtracking in csv.Sniffer #109639
- [3.15] gh-109638: Avoid pathological backtracking in csv.Sniffer (GH-153694) #154865
- [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes #154868
- [3.15] gh-109638: Fix excessive backtracking in csv.Sniffer doublequote detection #154869
- [3.14] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) #155112
- [3.13] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) #155113
- [3.12] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155114
- [3.11] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155115
- [3.10] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) #155116
Activity
serhiy-storchaka commentedon Jul 21, 2026
Fixed in 3.16 by the
csv.Snifferrewrite (gh-83273): these regular expressions no longer exist, and your example is now instant even for 200 iterations. There is a test for it.The maintenance branches are still affected, and a targeted fix for them is welcome. Excluding the quote character from the character class, as the lookahead variant in the first message does, reduces the time for 60 iterations from 11 s to 0.3 s on 3.15. The atomic group proposed in GH-109639 does not work: it makes the regular expression unmatchable and silently disables the doublequote detection.
pikammmmm commentedon Jul 29, 2026
Excluding the quote character from the first class reproduces your n=60 numbers
almost exactly, but the improvement does not hold past them.
Timing
dq_regexp.search()directly on 3.15.0b1 (Windows x86-64, delim,,quote
"), sample'"",' * k + '"' * k + '0' + '"' * k + '0':So the exclusion buys roughly 2.5x in input length rather than removing the
blowup — an 802-byte sample costs the "fixed" pattern about what the
302-byte one cost the unfixed pattern.
The leading
\W*is a second amplifier that the exclusion does not touch:\Wmatches the quote character and every non-word delimiter, so a run ofcommas both supplies start positions for
((delim)|^)and gives\W*moreways to split. With
'"",' * 3 + ',' * k + '"' * (2 * k) + '0'the exclusionvariant is back to 7.6 s at 370 bytes.
GH-154868 stays flat on both shapes — 0.0006 s on a 50 KB sample, about 10^5
times the size at which the others become unusable. I also checked it still
detects the doubled quotes the old pattern detected (
,"a""b","a""b",x,"a""b",y,"x""y"across a newline,1,"He said ""hi""",2,"","a""b")and still declines the ones it declined (
,"",,a,b,c,"plain","fields"):0 disagreements with 3.15 on those.
Mentioning it because I had opened GH-154869 using the exclusion-only change
and have closed it — the measurements above are why I don't think that
approach should land on the maintenance branches either.
pythongh-109638: Avoid pathological backtracking in csv.Sniffer
pythongh-109638: Avoid pathological backtracking in csv.Sniffer
pythongh-109638: Test literal quotes in unquoted fields
pythongh-109638: Avoid pathological backtracking in csv.Sniffer
pythongh-109638: Test literal quotes in unquoted fields
pythongh-109638: Keep space-delimiter matching linear
[3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…
[3.13] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…
[3.14] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…
[3.12] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…
[3.14] pythongh-109638: Fix exponential time in csv.Sniffer for doubl…
[3.11] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…
[3.10] gh-109638: Fix exponential time in csv.Sniffer for doubled quo…