GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — [3.15] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields by serhiy-storchaka · Pull Request #154867 · python/cpython

Conversation

@serhiy-storchaka

@serhiy-storchaka serhiy-storchaka commented Jul 29, 2026 •
edited by bedevere-app Bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Member

The four regular expressions which look for a quoted field match its body lazily. A closing quote which is not followed by a delimiter is therefore retried with every following quote, to the very end of the sample, and findall() repeats that from every start position -- so the search is quadratic. On a single column of quoted fields none of them ever matches, so the whole cost is a failing scan.

>>> sample = '"abcdefghijklmnopqrstuvwxyz"\n' * 30000
>>> csv.Sniffer().sniff(sample, delimiters=',:|\t')   # minutes

The body now ends at the first quote which is not doubled, which is the only closing quote a reader would accept, and is matched possessively.

rows      before      after
 4000    3.1264 s    0.0427 s
30000        --      0.3190 s

A minimal reproducer needs no quoted fields at all -- ',"x' * n is quadratic too, because two of the four patterns are anchored on a delimiter rather than a line.

Being unambiguous is what makes it linear, so a few matches necessarily change: 16 of 560 files in the CSVsniffer corpora. Against their ground truth the net is positive -- delimiter 73.3% -> 74.5%, quotechar 81.3% -> 81.1%, doublequote unchanged.

main is not affected: the sniffer was rewritten there in gh-83273.

  • Issue: csv.Sniffer().sniff() Hangs on Single-Column Data #98820

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
All reactions
@serhiy-storchaka
pythongh-98820: Fix quadratic time in csv.Sniffer for quoted fields
b994f3f 
The regular expressions which look for a quoted field matched its body
lazily, so a closing quote which was not followed by a delimiter was
retried with every following quote, to the end of the sample.  Match
the body possessively instead: it ends at the first quote which is not
doubled, as it does for a reader.
@bedevere-app bedevere-app Bot mentioned this pull request Jul 29, 2026
csv.Sniffer().sniff() Hangs on Single-Column Data #98820
Closed
@bedevere-app bedevere-app Bot added the awaiting core review label Jul 29, 2026
@serhiy-storchaka serhiy-storchaka added needs backport to 3.13 only security fixes needs backport to 3.14 bugs and security fixes labels Jul 29, 2026
serhiy-storchaka and others added 2 commits August 3, 2026 13:33
@serhiy-storchaka
Merge remote-tracking branch 'upstream/3.15' into sniff-315-gh98820
d8f003d 
# Conflicts:
#	Lib/test/test_csv.py
@serhiy-storchaka @claude
Remove the unreachable \r alternatives in the sniffing regexes
a9913ac 
sniff() now replaces \r\n and \r with \n before these regular
expressions are used.

Co-Authored-By: Claude Opus 5 (1M context) <[email protected]>
@serhiy-storchaka
serhiy-storchaka enabled auto-merge (squash) August 3, 2026 11:49
@serhiy-storchaka serhiy-storchaka added the type-security A security issue label Aug 3, 2026
@serhiy-storchaka
serhiy-storchaka merged commit 476fb09 into python:3.15 Aug 3, 2026
147 of 152 checks passed

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the awaiting core review label Aug 3, 2026
@miss-islington-app

miss-islington-app Bot commented Aug 3, 2026

Copy link
Copy Markdown

Thanks @serhiy-storchaka for the PR 🌮🎉.. I'm working now to backport this PR to: 3.13, 3.14.
🐍🍒⛏🤖 I'm not a witch! I'm not a witch!
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app

bedevere-app Bot commented Aug 3, 2026

Copy link
Copy Markdown

GH-155117 is a backport of this pull request to the 3.14 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the needs backport to 3.14 bugs and security fixes label Aug 3, 2026
@bedevere-app

bedevere-app Bot commented Aug 3, 2026

Copy link
Copy Markdown

GH-155118 is a backport of this pull request to the 3.13 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app bedevere-app Bot removed the needs backport to 3.13 only security fixes label Aug 3, 2026
Yhg1s pushed a commit that referenced this pull request Aug 4, 2026
@miss-islington @serhiy-storchaka @claude
[3.13] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (G…
b30c7fa 
…H-154867) (#155118)

[3.15] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (GH-154867)

The regular expressions which look for a quoted field matched its body
lazily, so a closing quote which was not followed by a delimiter was
retried with every following quote, to the end of the sample.  Match
the body possessively instead: it ends at the first quote which is not
doubled, as it does for a reader.
(cherry picked from commit 476fb09)

Co-authored-by: Serhiy Storchaka <[email protected]>
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
@serhiy-storchaka serhiy-storchaka mentioned this pull request Aug 4, 2026
[3.12] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (GH-154867) #155166
Merged
@bedevere-app

bedevere-app Bot commented Aug 4, 2026

Copy link
Copy Markdown

GH-155166 is a backport of this pull request to the 3.12 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
serhiy-storchaka added a commit that referenced this pull request Aug 4, 2026
@miss-islington @serhiy-storchaka @claude
[3.14] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (G…
89f29c7 
…H-154867) (GH-155117)

The regular expressions which look for a quoted field matched its body
lazily, so a closing quote which was not followed by a delimiter was
retried with every following quote, to the end of the sample.  Match
the body possessively instead: it ends at the first quote which is not
doubled, as it does for a reader.
(cherry picked from commit 476fb09)

Co-authored-by: Serhiy Storchaka <[email protected]>
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
Yhg1s pushed a commit that referenced this pull request Aug 4, 2026
@serhiy-storchaka @miss-islington
[3.12] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (G…
063d455 
…H-154867) (#155166)

(cherry picked from commit b30c7fa)

Co-authored-by: Miss Islington (bot) <[email protected]>
deadlovelll pushed a commit to deadlovelll/cpython that referenced this pull request Aug 5, 2026
@miss-islington @serhiy-storchaka
@claude @deadlovelll
[3.14] pythongh-98820: Fix quadratic time in csv.Sniffer for quoted f…
318cc3d 
…ields (pythonGH-154867) (pythonGH-155117)

The regular expressions which look for a quoted field matched its body
lazily, so a closing quote which was not followed by a delimiter was
retried with every following quote, to the end of the sample.  Match
the body possessively instead: it ends at the first quote which is not
doubled, as it does for a reader.
(cherry picked from commit 476fb09)

Co-authored-by: Serhiy Storchaka <[email protected]>
Co-authored-by: Claude Opus 5 (1M context) <[email protected]>
This was referenced Aug 11, 2026
[3.11] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (GH-154867) #155538
Merged
[3.10] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (GH-154867) #155539
Merged
@bedevere-app

bedevere-app Bot commented Aug 11, 2026

Copy link
Copy Markdown

GH-155538 is a backport of this pull request to the 3.11 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
@bedevere-app

bedevere-app Bot commented Aug 11, 2026

Copy link
Copy Markdown

GH-155539 is a backport of this pull request to the 3.10 branch.
All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.
pablogsal pushed a commit that referenced this pull request Aug 11, 2026
@serhiy-storchaka
[3.11] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (G…
b09a67a 
…H-154867) (#155538)
pablogsal pushed a commit that referenced this pull request Aug 11, 2026
@serhiy-storchaka
[3.10] gh-98820: Fix quadratic time in csv.Sniffer for quoted fields (G…
fd78b56 
…H-154867) (#155539)
@serhiy-storchaka
serhiy-storchaka deleted the sniff-315-gh98820 branch August 27, 2026 12:34
icanhasmath pushed a commit to ActiveState/cpython that referenced this pull request Oct 28, 2026
@serhiy-storchaka @icanhasmath
[3.10] pythongh-98820: Fix quadratic time in csv.Sniffer for quoted f…
c1c23f0 
…ields (pythonGH-154867) (python#155539)

(cherry picked from commit fd78b56)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Uh oh!

There was an error while loading. Please reload this page.

Assignees

No one assigned

Labels

type-security A security issue

Projects

None yet

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.

1 participant

@serhiy-storchaka
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.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.