GeezerVison

Excluding the quote character from the first run lowers the degree, but the second run can still take each quote either as its own content or as one of the matched quotes, so the search stays polynomial.

Measured on the reproducer from the issue:

O(n^5) before, O(n^4) after: a 2 KB sample still takes four and a half minutes, and the test added here takes 1.05 s. #154869 proposed the same change and was closed in favour of #154868, reporting the same limitation.

Excluding the quote character from both runs and matching them possessively makes it linear, at the cost of changing results on 42 of 560 files in the CSVsniffer corpora, where this PR changes none.

3.15 is still in beta, so there is also a third option: backporting the new engine from main, which fixes this issue along with seven others.

Thanks for the analysis. I implemented the quote-exclusion approach suggested in the July 21 issue comment, but I have now reproduced the residual scaling locally on the current 3.15 branch: n=50 took 0.122 s, n=100 1.598 s, and n=150 7.856 s.
I agree that this reduces but does not eliminate the pathological behavior, and that #154868 is the stronger fix. I’m happy to close this in its favor. If useful, I can contribute the Windows validation or help with follow-up work for the maintenance branches.

Reopening with a substantially revised implementation at a45aca2. The PR body describes the superseded first implementation; this comment documents the current patch and its validation.

Thanks to @serhiy-storchaka for showing that the original change only reduced the pathological search from O(n^5) to O(n^4). The previous implementation and its performance claims have been replaced.

Revised design

Doublequote detection now has two linear stages.

1. Possessive pre-filter

The first pattern adopts the core approach from #154868:

• every free run excludes the detected quote character;
• those runs are possessive;
• doubled quotes can occur after delimiters or line boundaries;
• delimiters and line breaks are allowed inside quoted fields.

There are separate patterns for non-empty and empty delimiters. This is necessary because interpolating an empty delimiter into (?:%(delim)s|^) produces (?:|^): the empty alternative lets re.search() retry at every position and leaves quadratic behavior on single-column input.

The empty-delimiter pattern instead starts only at \A, CR, or LF. The non-empty pattern also handles closing quotes followed by CRLF or CR-only record endings.

2. Anchored no-doublequote validation

An unanchored local match can begin at a delimiter inside one quoted field and finish in another field. A minimal example is:

sample = '",","",","'

This is three quoted fields whose values are ,, an empty string, and ,. It contains no doubled quote, but #154868 and the pre-filter alone both report doublequote=True.

After a pre-filter match, the revised code therefore checks whether the complete sample is a well-formed sequence of fields containing no doubled quote. If it is, the result is False; otherwise the pre-filter result is retained.

The validator is anchored at \A and \Z, supports LF/CRLF/CR and the internal empty-delimiter case, permits literal quote characters in unquoted fields when they do not occur at field start, and uses possessive repetition throughout. It does not invoke _csv.reader, so the result is independent of the process-wide csv.field_size_limit().

Generated-input validation

I generated two independent batches of 500,000 semantically labelled samples, using seeds 0xA11CE and 0xBADC0DE.

The generator covered comma, semicolon, tab, pipe, space, and the Sniffer's internal empty delimiter; both quote characters; LF, CRLF, and CR; quoted and unquoted fields; embedded delimiters and line breaks; empty fields; leading spaces; doubled quotes; and literal quote characters in unquoted fields. Ground truth came from the semantic values used to construct and escape each field, not from another detector.

The anchored validation is what removes the remaining 742 pre-filter false positives.

Additional validation:

• 506,996 exhaustively enumerated valid combinations: 0 false negatives, 0 false positives;
• 100,000 end-to-end _guess_quote_and_delimiter() samples: 44,076 inferred the generated delimiter and quote character, with 0 doublequote errors among those cases;
• 250,000 arbitrary/malformed inputs, including NUL and regex-special delimiters: no exceptions;
• 62 ASCII delimiter characters, 372 targeted true/false cases: no errors;
• fields of 100,000, 140,000, and 200,000 characters remained correct with both the default field_size_limit and a deliberately lowered limit of 1,024.

The arbitrary-input run is only a robustness check: malformed CSV has no unique semantic ground truth, so it is not included in the accuracy totals.

Corpus comparison

I tested the 548 files available in my local CSVsniffer corpus checkout.

With newline normalization there were no decision differences from #154868. With raw newlines, three decisions differed: two agreed with the annotations and one did not. I am reporting the latter conservatively as an annotated regression, even though the raw input contains doubled quote characters.

Performance

The following are post-rebase measurements from a Windows x64 Release build. Each value is a median after warm-up.

Original gh-109638 family

sample = '"",' * n + '"' * n + '0' + '"' * n + '0'

Both implementations are linear and effectively equivalent on the original reproducer.

Empty-delimiter family

sample = '"a"\n' + ' ' * n

#154868 is approximately quadratic on this family; the revised implementation is linear.

Repeated cross-field false positives

Repeating the valid ",","","," counterexample produced:

The full-sample validation is also linear.

Known trade-off

When the first real doubled quote occurs very late in a 128 KB comma-delimited sample, #154868 measured 1.870 ms and this revision measured 2.497 ms. This is the cost of the additional structural validation; both remain linear.

Rejected alternatives

• Differential validation with two _csv.reader instances matched normal generated inputs, but introduced false negatives when a field exceeded csv.field_size_limit() or the global limit was lowered.
• A strict anchored grammar alone achieved 0/0 on generated valid inputs but changed five newline-normalized corpus decisions relative to [3.15] gh-109638: Fix exponential time in csv.Sniffer for doubled quotes #154868.
• A Python state-machine validator achieved 0/0 but took roughly 50–65 ms when the first positive match occurred near the end of a 128 KB sample.

The final two-regexp design avoids those problems while keeping the maintenance-branch scope limited to doubled-quote detection.

Post-rebase validation

• full test_csv, Release: 138 tests passed, 4 skipped;
• full test_csv, Debug: 138 tests passed;
• TestSniffer, Debug refleak run with -R 3:3: no measured leaks;
• Tools/patchcheck/patchcheck.py: passed and reports exactly 3 changed files;
• git diff --check upstream/3.15...HEAD: passed.

The new tests cover the gh-109638 reproducer, true and false single-column detection, LF/CRLF/CR boundaries, both quote characters, comma/space/empty delimiters, cross-field false positives, and literal quotes in unquoted fields.

This remains a focused 3.15 maintenance-branch fix; it does not backport the complete Sniffer rewrite from main.

sniff('"a" "b"\n' + ' ' * n) is still quadratic here: 0.0047, 0.0066, 0.0248 and 0.0973 s for n = 4000, 8000, 16000 and 32000. *+ rescans every run of spaces after the delimiter it has just consumed.

Spaces after a space delimiter cannot be a padding, so there is no need to skip them at all.

Thank you, @serhiy-storchaka. You were right. I applied your suggestion in d3c62be: when the delimiter is a space, the pre-filter no longer consumes a run of spaces as padding. I also added regression tests for both the 100,000-space case and a positive case with consecutive space delimiters. The reported case is now linear.

While auditing related inputs, I found a separate pre-existing quadratic path in the first legacy regexp in _guess_quote_and_delimiter, before _detect_doublequote() is called:

sample = ('"a",   ' * n) + '"b"'

For n = 1000, 2000, 4000, 8000, I measure approximately 0.033, 0.131, 0.509, 2.054 seconds in _guess_quote_and_delimiter(). In comparison, _detect_doublequote() alone takes 0.000085, 0.000163, 0.000318, 0.000638 seconds.

This is not introduced by this PR and should probably be tracked separately rather than expanding the scope of this maintenance fix. I can open a separate issue for it.

It's already tracked as #98820.

@hugovk, this is an alternative to #154868 which you merged few hours ago.

Thank you for your effort. @Punisheroot, but other PR was merged instead.