GeezerVison is showing github.com — [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes by serhiy-storchaka · Pull Request #154868 · python/cpython
Conversation
serhiy-storchaka
commented
Jul 29, 2026
•
edited by bedevere-app
Bot
Loading
Uh oh!
There was an error while loading. Please reload this page.
The regular expression which detects a doubled quote character lets its runs match the quote character too, so every quote can be taken either as part of a run or as one of the three matched quotes. With three unbounded quantifiers over a region of quotes and delimiters the search is O(n^5) -- 254 s at n=100 in the report.
>>> sample = '"",' * 100 + '"' * 100 + '0' + '"' * 100 + '0'
>>> csv.Sniffer().sniff(sample) # minutes The runs now exclude the quote character and are matched possessively, which leaves exactly one way to read any input.
n before after
60 6.1300 s 0.0002 s
2000 -- 0.0009 s
The runs also no longer exclude the delimiter and the line break, which the original did for no reason a reader shares -- so a doubled quote is now found in a field containing them as well, e.g. ,"All-Weather Dining Table, Round 48""",. That is the bulk of the behaviour change: 42 of 560 corpus files, and against ground truth doublequote=True improves from 25.8% to 36.7% and doublequote=False from 77.0% to 78.7%, with delimiter and quotechar unchanged.
Note #109639 proposed an atomic group on the first run only. It removes the time but also the detection: doublequote becomes unconditionally False (0 of 126 annotated files, vs 32 for 3.15).
main is not affected: the sniffer was rewritten there in gh-83273.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
The regular expression which looks for a doubled quote character let
its runs match the quote character too, so every quote could be taken
either as a part of a run or as one of the matched quotes. Exclude the
quote character from the runs and match them possessively.
The runs no longer exclude the delimiter and the line break either, so
a doubled quote is now also found in a field which contains them.
|
Note that the widened detection -- a doubled quote is now found in a field which contains the delimiter or a line break -- changes results on 42 of 560 files in the CSVsniffer corpora. Against that corpus's ground truth the change is positive on both sides: doublequote=True 25.4% -> 37.3%, doublequote=False 77.0% -> 78.5%.
There are two alternatives. #154865 changes no results, but leaves the search polynomial (O(n^5) -> O(n^4), still four and a half minutes on a 2 KB sample). Or, since 3.15 is still in beta, the new engine can be backported from main, which fixes this issue along with seven others; it changes results on 122 of 560 files.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
Thanks again for identifying the residual polynomial behavior in my original patch. I reworked and reopened #154865 at a45aca2, using the possessive quote-exclusion approach from this PR as the pre-filter, then tested the current #154868 head (92b3133) against broader correctness and scaling cases.
I found two additional cases not covered by the original reproducer.
Empty-delimiter scaling
When delimiter == '', the left boundary in the current pattern becomes (?:|^). The empty alternative lets re.search() retry the pattern at every position, leaving quadratic behavior on single-column samples.
Post-rebase Windows x64 Release medians for:
sample = '"a"\n' + ' ' * n
| Sample size |
#154868 |
Revised #154865 |
| 4,004 B |
2.000 ms |
0.044 ms |
| 8,004 B |
7.686 ms |
0.088 ms |
| 16,004 B |
29.598 ms |
0.175 ms |
| 32,004 B |
123.973 ms |
0.352 ms |
| 64,004 B |
472.371 ms |
0.710 ms |
The revised patch uses separate non-empty- and empty-delimiter patterns, so the empty case can only start at \A, CR, or LF.
Cross-field false positives
An unanchored match can start at a delimiter inside one quoted field and finish in another. For example:
This is three quoted fields containing ,, an empty string, and ,; it has no doubled quote, but the current #154868 pattern reports doublequote=True.
The revised patch keeps the possessive pre-filter, then uses an anchored linear pattern to rule out a complete well-formed sample without doubled quotes. It also handles CRLF/CR boundaries and literal quote characters in unquoted fields.
Generated-input results
I generated two independent batches of 500,000 semantically labelled samples using seeds 0xA11CE and 0xBADC0DE. Coverage included comma, semicolon, tab, pipe, space, and the Sniffer's internal empty delimiter; both quote characters; LF/CRLF/CR; mixed quoted and unquoted fields; embedded delimiters and line breaks; doubled quotes; and literal quotes in unquoted fields. Ground truth came from the values used to construct and escape each field.
| Implementation |
False negatives |
False positives |
#154868 (92b3133) |
52,905 |
6,208 |
| Revised possessive pre-filter alone |
0 |
742 |
Revised #154865 (a45aca2) |
0 |
0 |
I also exhaustively enumerated 506,996 valid combinations: the revised implementation had 0 false negatives and 0 false positives.
On the 548 corpus files available in my local checkout, newline-normalized input produced no decision differences from #154868. With raw newlines there were three differences: two agreed with the annotations and one did not; I am reporting the last one conservatively as an annotated regression.
The revised implementation remains effectively equivalent to #154868 on the original gh-109638 family:
| Sample size |
#154868 |
Revised #154865 |
| 80,002 B |
0.938 ms |
0.964 ms |
| 160,002 B |
1.865 ms |
1.920 ms |
| 320,002 B |
3.737 ms |
3.861 ms |
| 640,002 B |
7.499 ms |
7.471 ms |
There is one measured trade-off: when the first real doubled quote is very late in a 128 KB comma-delimited sample, #154868 took 1.870 ms and the revision took 2.497 ms because it performs the structural validation pass. Both remain linear.
The complete implementation rationale, rejected alternatives, corpus accounting, and post-rebase validation are documented in the reopening comment on #154865. I would appreciate your thoughts, particularly on the separate empty-delimiter handling and the anchored no-doublequote validation.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
The pattern required a doubled quote character in the middle, so it
could match from a delimiter inside one quoted field to a quote in
another one, and reported a double quoted format for '",","",","'.
Match whole quoted fields instead and test their bodies for a doubled
quote separately. Only look behind the delimiter, because the trailing
one is consumed, so that consecutive fields are all matched.
|
Thanks to @Punisheroot for finding in #154865 that the pattern reported a doubled quote for '",","",","', which is three quoted fields ,, an empty one and ,. It required a doubled quote character in the middle, so it could match from a delimiter inside one quoted field to a quote in another one.
Now whole quoted fields are matched and their bodies are tested separately. No file of 560 in the corpora changes, so the numbers above still hold; nothing in the test suite noticed either, hence the added test.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Thanks to @Punisheroot for finding in #154865 that the pattern reported a doubled quote for '",","",","', which is three quoted fields ,, an empty one and ,. It required a doubled quote character in the middle, so it could match from a delimiter inside one quoted field to a quote in another one.
Now whole quoted fields are matched and their bodies are tested separately. No file of 560 in the corpora changes, so the numbers above still hold; nothing in the test suite noticed either, hence the added test.
Thanks for updating the pattern and for the credit. I tested the current head
(e78bb80) and found two remaining record-boundary cases.
A doubled quote in the last field of a CRLF record is missed:
sample = 'x,"a""b"\r\ny,"c"\r\n'
csv.Sniffer().sniff(sample).doublequote # False, expected True Conversely, this valid CR-separated CSV contains no doubled quote but reports
True:
sample = '"",","\r"",","'
list(csv.reader(io.StringIO(sample, newline="")))
# [['', ','], ['', ',']] This appears to be because ^/$ with re.MULTILINE do not fully represent
CR/CRLF record boundaries, allowing a match to cross records.
The empty-delimiter case also remains approximately quadratic:
sample = '"a"\n' + ' ' * n On Windows x64 Release, the current head grows from 2.30 ms at 4 KB to
432.42 ms at 64 KB.
#154865 handles CR/CRLF and the empty delimiter separately. Would you consider
adding these cases to this PR’s regression tests?
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Normalize the record separators in the sample, so that ^ and $ match
at every record boundary: a doubled quote in the last field of a CRLF
record was not detected, and a match could cross a CR separated record.
Skip the detection if there is no delimiter, because an empty one
matches at every position and makes the search quadratic.
|
All three are fixed in ddb0488, thank you.
The record separators are now normalized in sniff(), which fixes both boundary cases at once -- and this was not a regression, but a 3.15 bug: the main regexps only contain \n, so a CR separated record has no start for them, and 3.15 is wrong there in both directions. This is unrelated to the superlinear complexity, but it was easy to fix.
The detection is skipped when there is no delimiter. Nothing is lost there: without a delimiter sniff() either raises, or returns one taken from inside the quoted fields -- often the quote character itself, which reader() rejects.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
They cannot be a padding, and skipping them rescans every run of
spaces, which makes the search quadratic.
Uh oh!
There was an error while loading. Please reload this page.
|
Thanks @serhiy-storchaka for the PR, and @hugovk for merging it 🌮🎉.. I'm working now to backport this PR to: 3.13, 3.14.
🐍🍒⛏🤖
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
Sorry, @serhiy-storchaka and @hugovk, I could not cleanly backport this to 3.14 due to a conflict.
Please backport using cherry_picker on command line.
cherry_picker d52184ba1ed0e7c0fe8afe4928fbb72a0f9526fb 3.14
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
Sorry, @serhiy-storchaka and @hugovk, I could not cleanly backport this to 3.13 due to a conflict.
Please backport using cherry_picker on command line.
cherry_picker d52184ba1ed0e7c0fe8afe4928fbb72a0f9526fb 3.13
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️
Hi! The buildbot AMD64 Android 3.15 (tier-3) has failed when building commit d52184b.
What do you need to do:
- Don't panic.
- Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
- Go to the page of the buildbot that failed (https://buildbot.python.org/#/builders/2074/builds/341) and take a look at the build logs.
- Check if the failure is related to this commit (d52184b) or if it is a false positive.
- If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.
You can take a look at the buildbot page here:
https://buildbot.python.org/#/builders/2074/builds/341
Summary of the results of the build (if available):
Click to see traceback logs
remote: Enumerating objects: 20, done.
remote: Counting objects: 5% (1/20)
remote: Counting objects: 10% (2/20)
remote: Counting objects: 15% (3/20)
remote: Counting objects: 20% (4/20)
remote: Counting objects: 25% (5/20)
remote: Counting objects: 30% (6/20)
remote: Counting objects: 35% (7/20)
remote: Counting objects: 40% (8/20)
remote: Counting objects: 45% (9/20)
remote: Counting objects: 50% (10/20)
remote: Counting objects: 55% (11/20)
remote: Counting objects: 60% (12/20)
remote: Counting objects: 65% (13/20)
remote: Counting objects: 70% (14/20)
remote: Counting objects: 75% (15/20)
remote: Counting objects: 80% (16/20)
remote: Counting objects: 85% (17/20)
remote: Counting objects: 90% (18/20)
remote: Counting objects: 95% (19/20)
remote: Counting objects: 100% (20/20)
remote: Counting objects: 100% (20/20), done.
remote: Compressing objects: 9% (1/11)
remote: Compressing objects: 18% (2/11)
remote: Compressing objects: 27% (3/11)
remote: Compressing objects: 36% (4/11)
remote: Compressing objects: 45% (5/11)
remote: Compressing objects: 54% (6/11)
remote: Compressing objects: 63% (7/11)
remote: Compressing objects: 72% (8/11)
remote: Compressing objects: 81% (9/11)
remote: Compressing objects: 90% (10/11)
remote: Compressing objects: 100% (11/11)
remote: Compressing objects: 100% (11/11), done.
remote: Total 11 (delta 9), reused 1 (delta 0), pack-reused 0 (from 0)
From https://github.com/python/cpython
* branch 3.15 -> FETCH_HEAD
Note: switching to 'd52184ba1ed0e7c0fe8afe4928fbb72a0f9526fb'.
You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by switching back to a branch.
If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -c with the switch command. Example:
git switch -c <new-branch-name>
Or undo this operation with:
git switch -
Turn off this advice by setting config variable advice.detachedHead to false
HEAD is now at d52184ba1ed [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (#154868)
Switched to and reset branch '3.15'
configure: WARNING: no system libmpdec found; falling back to pure-Python version for the decimal module
In file included from ../../Include/internal/pycore_dict.h:11,
from ../../Objects/typeobject.c:8:
In function ‘Py_DECREF_MORTAL’,
inlined from ‘PyStackRef_CLOSE’ at ../../Include/internal/pycore_stackref.h:682:9,
inlined from ‘_PyThreadState_PopCStackRef’ at ../../Include/internal/pycore_stackref.h:790:5,
inlined from ‘vectorcall_maybe’ at ../../Objects/typeobject.c:3148:9:
../../Include/internal/pycore_object.h:456:8: warning: array subscript 0 is outside array bounds of ‘PyObject[0]’ {aka ‘struct _object[]’} [-Warray-bounds]
456 | if (--op->ob_refcnt == 0) {
| ^
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
100 201k 100 201k 0 0 412k 0 --:--:-- --:--:-- --:--:-- 3058k
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
100 43710 100 43710 0 0 99345 0 --:--:-- --:--:-- --:--:-- 99345
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
100 6254k 100 6254k 0 0 14.3M 0 --:--:-- --:--:-- --:--:-- 156M
% Total % Received % Xferd Average Speed Time Time Time Current
Dload Upload Total Spent Left Speed
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
Warning: Problem : HTTP error. Will retry in 1 seconds. 5 retries left.
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 157k 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
Warning: Problem : HTTP error. Will retry in 2 seconds. 4 retries left.
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 157k 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
Warning: Problem : HTTP error. Will retry in 4 seconds. 3 retries left.
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 157k 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
Warning: Problem : HTTP error. Will retry in 8 seconds. 2 retries left.
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 157k 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
Warning: Problem : HTTP error. Will retry in 16 seconds. 1 retries left.
0 0 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
0 157k 0 0 0 0 0 0 --:--:-- --:--:-- --:--:-- 0
curl: (22) The requested URL returned error: 500
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️
Hi! The buildbot AMD64 Arch Linux Asan 3.14 (tierless) has failed when building commit ca87a0a.
What do you need to do:
- Don't panic.
- Check the buildbot page in the devguide if you don't know what the buildbots are or how they work.
- Go to the page of the buildbot that failed (https://buildbot.python.org/#/builders/1806/builds/447) and take a look at the build logs.
- Check if the failure is related to this commit (ca87a0a) or if it is a false positive.
- If the failure is related to this commit, please, reflect that on the issue and make a new Pull Request with a fix.
You can take a look at the buildbot page here:
https://buildbot.python.org/#/builders/1806/builds/447
Summary of the results of the build (if available):
Click to see traceback logs
Note: switching to 'ca87a0a1f2ca3847d74b1be1073042d413ecccfe'.
You are in 'detached HEAD' state. You can look around, make experimental
changes and commit them, and you can discard any commits you make in this
state without impacting any branches by switching back to a branch.
If you want to create a new branch to retain commits you create, you may
do so (now or later) by using -c with the switch command. Example:
git switch -c <new-branch-name>
Or undo this operation with:
git switch -
Turn off this advice by setting config variable advice.detachedHead to false
HEAD is now at ca87a0a1f2ca3 [3.14] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155112)
Switched to and reset branch '3.14'
ar: unable to copy file 'libpython3.14.a'; reason: Success
make: *** [Makefile:1180: libpython3.14.a] Error 1
find: ‘build’: No such file or directory
find: ‘build’: No such file or directory
find: ‘build’: No such file or directory
find: ‘build’: No such file or directory
make: [Makefile:3398: clean-retain-profile] Error 1 (ignored)
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Reviewers
hugovk
hugovk approved these changes
Uh oh!
There was an error while loading. Please reload this page.
Milestone
No milestone
Development
Successfully merging this pull request may close these issues.
Uh oh!
There was an error while loading. Please reload this page.
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
|