FazBrowse GitHub Viewer | Trending |
URL:
| Home
Tools: [Download Repo ZIP]   [Original HTTPS Page]

gh-109638: Fix for significant backtracking in csv.Sniffer by sg3-141-592 · Pull Request #109639 · python/cpython · GitHub

/ cpython Public

gh-109638: Fix for significant backtracking in csv.Sniffer - #109639

Closed
sg3-141-592 wants to merge 5 commits into
python:mainfrom
sg3-141-592:main
ConversationCommits (5)ChecksFiles changed
Closed

gh-109638: Fix for significant backtracking in csv.Sniffer#109639
sg3-141-592 wants to merge 5 commits into
python:mainfrom
sg3-141-592:main

Conversation

sg3-141-592 commented Sep 21, 2023 •
edited
Loading

Copy link
Copy Markdown

#109638 it is possible to get significant backtracking in csv.Sniffer() inside the doublequote checking regex. This change introduces a zero-length lookahead assertion to reduce the amount of backtracking.

This yields a significant improvement in testing

import csv
import time

for NUM_ITERATIONS in range(10,70,10):

    test_str = '"",'*NUM_ITERATIONS + '"'*NUM_ITERATIONS + '0' + '"'*NUM_ITERATIONS + '0'

    t0 = time.time()

    dialect = csv.Sniffer().sniff(test_str)

    t1 = time.time()
    print(f"{NUM_ITERATIONS}, {t1-t0}")
NUM_ITERATIONS | Before           | After Regex Fix
10  | 0.002374649 | 0.000935555
20  | 0.051596165 | 0.003250599
30  | 0.371201515 | 0.017635345
40  | 1.477169752 | 0.054927588
50  | 4.845417738 | 0.120140076
60  | 11.52993703 | 0.252950668

This comment was marked as resolved.

Sign in to view

This comment was marked as resolved.

Sign in to view
bedevere-app Bot mentioned this pull request Sep 21, 2023
Closed
sg3-141-592 marked this pull request as ready for review September 22, 2023 15:01
AA-Turner reviewed Sep 22, 2023
View reviewed changes
Comment thread Lib/csv.py Outdated

# if we see an extra quote between delimiters, we've got a
# double quoted format
# in future Python versions this zero width look-ahead assert can be replaced with atomic groups

AA-Turner Sep 22, 2023

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Please may you explain this comment?

sg3-141-592 Sep 23, 2023

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Sure, this zero-width lookahead assertion change in the Regex can be done with an atomic group which is cleaner and more concise.

# Current change
(,|^)\W*"(?=(?P<zero>[^,|"\n]*))(?P=zero)"[^,|\n]*"\W*(,|$)
# Atomic Group
(,|^)\W*"(?>[^,|"\n]*)"[^,|\n]*"\W*(,|$)

But atomic groups are only supported in Python 3.11 onwards so I avoided using them here.

AA-Turner Sep 23, 2023

Copy link
Copy Markdown
Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Thanks Sean. This PR (if merged) would be part of Python 3.13, so let's use the better atomic group method.

A

sg3-141-592 Sep 23, 2023

Copy link
Copy Markdown
Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

Sure, I've switched us to the simpler atomic group setup. Performance is identical to the previous fix.

aterrel approved these changes May 20, 2025
View reviewed changes

aterrel left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Choose a reason Spam Abuse Off Topic Outdated Duplicate Resolved Low Quality

This looks like a good quick fix for the problem.

Ultimately though, these regexs are hard to read and cause a few problems with lists and other items. I think we should be thinking about how to replace the sniffer to have a higher accuracy. (See https://github.com/ws-garcia/CSVsniffer which shows that only 67.54% accuracy). I've posted to dpo on this topic here: https://discuss.python.org/t/rewrite-csv-sniffer

github-actions Bot commented Apr 14, 2026

Copy link
Copy Markdown

This PR is stale because it has been open for 30 days with no activity.

github-actions Bot added the stale Stale PR or inactive for long period of time. label Apr 14, 2026
serhiy-storchaka mentioned this pull request Jul 14, 2026
Merged

serhiy-storchaka commented Jul 21, 2026

Copy link
Copy Markdown
Member

Thank you for the patch, but I am afraid it does not work.

[^%(delim)s\n] includes the quote character, so the atomic group consumes everything up to the delimiter, the line break or the end of data, and the quote character which follows it in the pattern can never match there. The regular expression became unmatchable, so doublequote is now always false: it is fast because it no longer checks anything, and test_doublequote fails.

These regular expressions are gone on the main branch now (gh-83273), but a fix is still needed for the maintenance branches. Excluding the quote character from the character class, as the lookahead variant in the issue does, keeps the detection working and is enough to reduce the time for your example with 60 iterations from 11 s to 0.3 s (the growth is still superlinear, but much slower).

Punisheroot mentioned this pull request Jul 29, 2026
Closed
serhiy-storchaka mentioned this pull request Jul 29, 2026
Merged
pikammmmm mentioned this pull request Jul 29, 2026
Closed
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode characters
Show hidden characters
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

AA-Turner AA-Turner left review comments
+1 more reviewer
aterrel aterrel approved these changes
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

awaiting core review skip news stale Stale PR or inactive for long period of time.

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

4 participants

Back | FazBrowse Home | New Git URL