| FazBrowse GitHub Viewer | Trending | | Home |
| Tools: [Download Repo ZIP] [Original HTTPS Page] |
Sorry, something went wrong.
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.
|
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 scalingWhen 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
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 positivesAn unanchored match can start at a delimiter inside one quoted field and finish in another. For example: sample = '",","",","'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 resultsI 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.
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:
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.
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.
Thanks for updating the pattern and for the credit. I tested the current head 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 TrueConversely, this valid CR-separated CSV contains no doubled quote but reports sample = '"",","\r"",","'
list(csv.reader(io.StringIO(sample, newline="")))
# [['', ','], ['', ',']]This appears to be because ^/$ with re.MULTILINE do not fully represent The empty-delimiter case also remains approximately quadratic: sample = '"a"\n' + ' ' * nOn Windows x64 Release, the current head grows from 2.30 ms at 4 KB to #154865 handles CR/CRLF and the empty delimiter separately. Would you consider |
Sorry, something went wrong.
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.
They cannot be a padding, and skipping them rescans every run of spaces, which makes the search quadratic.
|
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.
|
Sorry, @serhiy-storchaka and @hugovk, I could not cleanly backport this to 3.14 due to a conflict. cherry_picker d52184ba1ed0e7c0fe8afe4928fbb72a0f9526fb 3.14 |
Sorry, something went wrong.
|
Sorry, @serhiy-storchaka and @hugovk, I could not cleanly backport this to 3.13 due to a conflict. cherry_picker d52184ba1ed0e7c0fe8afe4928fbb72a0f9526fb 3.13 |
Sorry, something went wrong.
|
GH-155112 is a backport of this pull request to the 3.14 branch. |
Sorry, something went wrong.
|
GH-155113 is a backport of this pull request to the 3.13 branch. |
Sorry, something went wrong.
⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️Hi! The buildbot AMD64 Android 3.15 (tier-3) has failed when building commit d52184b. What do you need to do:
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 logsremote: 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.
⚠️⚠️⚠️ Buildbot failure ⚠️⚠️⚠️Hi! The buildbot AMD64 Arch Linux Asan 3.14 (tierless) has failed when building commit ca87a0a. What do you need to do:
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 logsNote: 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.
…ed quotes (pythonGH-154868) (pythonGH-155112) (cherry picked from commit d52184b)
…tes (GH-154868) (GH-155113) (#155116) * [3.13] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes (GH-154868) (GH-155113) (cherry picked from commit eaa9bac) Co-authored-by: Serhiy Storchaka <storchaka@gmail.com> (cherry picked from commit d52184b) * Match the body of a quoted field without possessive quantifiers They were added in 3.11. An unrolled loop is unambiguous at every position, so it does not backtrack either. Co-Authored-By: Claude Opus 5 (1M context) <noreply@anthropic.com> --------- Co-authored-by: Serhiy Storchaka <storchaka@gmail.com> Co-authored-by: Claude Opus 5 (1M context) <noreply@anthropic.com> Co-authored-by: Hugo van Kemenade <1324225+hugovk@users.noreply.github.com>
| Back | FazBrowse Home | New Git URL |
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.
The runs now exclude the quote character and are matched possessively, which leaves exactly one way to read any input.
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.