Repository navigation
[markdown] Avoid quadratic backtracking in headerPattern - #2754
Conversation
PR HealthBreaking changes ✔️
This check can be disabled by tagging the PR with Coverage ✔️
This check for test coverage is informational (issues shown here will not fail the PR). This check can be disabled by tagging the PR with Changelog Entry ✔️
Changes to files need to be accounted for in their respective changelogs. This check can be disabled by tagging the PR with License Headers ✔️
All source files should start with a license header. Unrelated files missing license headers
This check can be disabled by tagging the PR with API leaks ✔️The following packages contain symbols visible in the public API, but not exported by the library. Export these symbols or remove them from your publicly visible API.
This check can be disabled by tagging the PR with Unused Dependencies ✔️
For details on how to fix these, see dependency_validator. This check can be disabled by tagging the PR with |
There was a problem hiding this comment.
Code Review
This pull request optimizes the headerPattern regular expression in pkgs/markdown/lib/src/patterns.dart to prevent quadratic backtracking on ATX headings with many spaces, and adds relevant unit tests. The review feedback correctly identifies that the updated pattern still fails to support U+2028 and U+2029 as claimed in the CHANGELOG because .*? does not match these characters. A suggestion is provided to use [^\r\n]*? instead to ensure proper support.
| /// non-space character. Line may end with any number of `#` characters,. | ||
| final headerPattern = RegExp( | ||
| r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#*)\s*)?$', | ||
| r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#+)\s*)?$', |
There was a problem hiding this comment.
The CHANGELOG mentions that ATX headings may now contain U+2028 and U+2029. However, because headerPattern uses .*? (where . does not match ECMAScript line terminators like U+2028 and U+2029), any heading containing these characters will fail to match entirely (or have them incorrectly treated as part of the closing marker if followed by #).
To actually support U+2028 and U+2029 within the heading content, we should use [^\r\n]*? instead of .*?. Since BlockParser already splits lines by \r and \n, [^\r\n] safely matches any character within the line, including U+2028 and U+2029.
| r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#+)\s*)?$', | |
| r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c][^\r\n]*?)?(?:\s(#+)\s*)?$', |
7cb0ac2 to
0eb3b0b
Compare
Change the optional closing hash capture group in `headerPattern`
(`pkgs/markdown/lib/src/patterns.dart`) from `(#*)` to `(#+)`:
- Before: `RegExp(r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#*)\s*)?$')`
- After: `RegExp(r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#+)\s*)?$')`
----
### Why this change is necessary
In `headerPattern`, the heading content group `(?:[ \x09\x0b\x0c].*?)?` uses a
lazy `.*?` followed by the optional closing hash sequence `(?:\s(#*)\s*)?$`.
Because `(#*)` allowed *zero* `#` characters, the subpattern `(?:\s(#*)\s*)`
reduced to `\s\s*` whenever `(#*)` matched the empty string.
On an ATX heading line containing many spaces before a non-space character—such
as `'# ${' ' * n}a'`—as the lazy `.*?` advanced one character at a time through
the n spaces, at every space position `i` it attempted to match
`(?:\s(#*)\s*)?$`:
- `\s` matched the space at `i`;
- `(#*)` matched `''`;
- `\s*` consumed all remaining `n - i` spaces up to `a`;
- `$` failed to match `a`, forcing the regex engine to backtrack across all
`n - i` spaces before `.*?` advanced by 1 space to `i + 1`.
Across n spaces, this took 1 + 2 + ... + n = O(n^2) time.
### How this change works
Changing `(#*)` to `(#+)` requires the optional closing group
`(?:\s(#+)\s*)?$` to contain at least one `#` character:
- At any whitespace character not immediately followed by `#`,
`(?:\s(#+)\s*)?$` fails in O(1) after checking a single character (`#`),
so `'# ${' ' * n}a'` is scanned in strictly O(n) time.
- When a closing `#` sequence is present, `match[2]` (`closeMarker`) captures
the exact same non-empty `#+` string as before.
- When no closing `#` sequence is present, trailing whitespace is consumed by
`.*?` and stripped by `HeaderSyntax`'s `.trim()`.
Add `dotAll: true` to `headerPattern` so `.*?` consumes `U+2028` and `U+2029`, which `LineSplitter` leaves in a line's content. Without it, the previous `(#*)` matching empty before `\s` is what accepted a heading ending in `U+2028`; with `(#+)` such a line stopped being a heading.
0d9e48f to
9be0fb6
Compare
9be0fb6 to
4bd13bb
Compare
Co-authored-by: Sarah Zakarias <[email protected]>
Revisions updated by `dart tools/rev_sdk_deps.dart`. core (https://github.com/dart-lang/core/compare/d7bd45c..24e09c4): 24e09c4c Sun Nov 1 21:12:19 2026 +0000 dependabot[bot] Bump the github-actions group with 4 updates (dart-lang/core#1037) 87ac1b4c Fri Oct 30 16:02:43 2026 +0100 Michael Thomsen [os_detect] Deprecate package:os_detect in favor of package:platform (dart-lang/core#1003) 8debf335 Fri Oct 30 01:57:36 2026 +0530 Sahaja Pallapothula Clarify Characters equality and Unicode normalization (dart-lang/core#1031) ecosystem (https://github.com/dart-lang/ecosystem/compare/24b9ba8..f8faabf): f8faabf Sun Nov 1 18:16:20 2026 +0000 dependabot[bot] Bump the github-actions group with 2 updates (dart-lang/ecosystem#481) 27c2fc8 Sat Oct 31 12:36:53 2026 +0100 Moritz Fix publish workflow pins, add tag_prefix to health, and update docs (dart-lang/ecosystem#480) 05641a9 Sat Oct 31 09:56:42 2026 +0100 Moritz Restore deprecated publish.yaml workflow and firehose CLI entrypoint (dart-lang/ecosystem#479) 78abf72 Fri Oct 30 08:24:07 2026 -0700 Kevin Moore fix(repo_manage): use pub_semver for changelog -wip transitions (dart-lang/ecosystem#475) 0bfa654 Fri Oct 30 09:33:57 2026 +0100 Moritz Move publish check to health workflow and use individual package publishing workflows from `setup-dart` (dart-lang/ecosystem#454) adf7979 Thu Oct 29 23:46:49 2026 -0700 Kevin Moore test(firehose): use hasLength, containsPair, and isFalse (dart-lang/ecosystem#477) http (https://github.com/dart-lang/http/compare/c76dfb3..8c0d66a): 8c0d66a Fri Oct 30 09:54:41 2026 -0700 Brian Quinlan chore(cupertino_http): check ffigen generation (dart-lang/http#2044) c8737d1 Fri Oct 30 09:11:46 2026 +0100 Moritz chore(http): run Firefox tests with -headless instead of xvfb-run (dart-lang/http#2033) 05d0b18 Fri Oct 30 07:08:19 2026 +0100 Moritz fix(http2): make StreamException a StreamTransportException and forward ALPN errors to onError (dart-lang/http#2009) i18n (https://github.com/dart-lang/i18n/compare/4c7b4ad..7475ce6): 7475ce64 Sat Oct 31 02:49:28 2026 +0100 Moritz [intl4x] Fix NumberFormat.percent ignoring digits (dart-lang/i18n#1115) shelf (https://github.com/dart-lang/shelf/compare/62d3e4e..9946de5): 9946de5 Sun Nov 1 12:27:59 2026 +0000 dependabot[bot] build(deps): bump the github-actions group with 3 updates (dart-lang/shelf#554) test (https://github.com/dart-lang/test/compare/6d74720..2a9e017): 2a9e0175 Sun Nov 1 03:47:24 2026 +0000 dependabot[bot] Bump the github-actions group with 6 updates (dart-lang/test#2813) 55cd5cd5 Fri Oct 30 13:43:47 2026 -0700 Nate Bosch Migrate publishing workflows from firehose to setup-dart (dart-lang/test#2812) 10dc78c0 Fri Oct 30 11:21:53 2026 -0700 Nate Bosch [checks] Describe what the stream did in failures (dart-lang/test#2811) c11ad06d Fri Oct 30 08:59:57 2026 -0700 Nate Bosch [checks] Add CheckFailure.describeNested (dart-lang/test#2793) 0137b43e Fri Oct 30 05:40:43 2026 +0530 Shriraj Jadhav [checks] Use the Iterable.last member for the last expectation (dart-lang/test#2807) 50c9f454 Thu Oct 29 15:11:39 2026 -0700 Nate Bosch [checks] Collapse clauses for described conditions (dart-lang/test#2794) tools (https://github.com/dart-lang/tools/compare/3980dca..1579f8d): 1579f8d69 Mon Nov 2 02:44:58 2026 +0530 Joshua fix(coverage): reject package: and dart: URIs outside known roots in Resolver (dart-lang/tools#2764) f869fdca4 Sun Nov 1 10:26:34 2026 +0100 dart-ecosystem-bot[bot] [boring] Update BoringSSL to ed9209cf (dart-lang/tools#2774) d10e2b87f Sun Nov 1 10:26:11 2026 +0100 dart-ecosystem-bot[bot] [boring] Pin the prebuilt binaries of boring-binaries-20261101-33e9e69722af (dart-lang/tools#2777) 33e9e6972 Sun Nov 1 05:56:30 2026 +0000 dependabot[bot] build(deps): bump the github-actions group with 4 updates (dart-lang/tools#2775) f84d0d0d2 Sun Nov 1 05:36:12 2026 +0000 dependabot[bot] build(deps): bump ffigen from 22.0.0 to 23.0.0 in /pkgs/boring (dart-lang/tools#2776) 14ad5e515 Fri Oct 30 10:48:58 2026 -0700 Kevin Moore [mime] Harden BoundMultipartStream error routing, headers, and epilogue (dart-lang/tools#2629) 7a780d48c Fri Oct 30 12:57:03 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid rescanning failed plain-text runs in InlineParser (dart-lang/tools#2757) 3671d33a9 Fri Oct 30 12:56:48 2026 +0100 Jonas Finnemann Jensen [markdown] Index footnote definitions and labels on Document for O(1) lookup (dart-lang/tools#2760) 6f38e9fda Fri Oct 30 12:56:09 2026 +0100 Jonas Finnemann Jensen [markdown] Bound the domain of extended URL autolinks to DNS limits (dart-lang/tools#2759) aa0c38544 Fri Oct 30 12:20:40 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid quadratic removeRange in _combineAdjacentText (dart-lang/tools#2758) f425baf46 Fri Oct 30 11:16:28 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid rescanning failed space runs in LineBreakSyntax (dart-lang/tools#2756) c7eafbec3 Fri Oct 30 11:09:45 2026 +0100 Jonas Finnemann Jensen [markdown] Reject '<' in AutolinkSyntax (dart-lang/tools#2755) 86ed0f902 Fri Oct 30 11:08:25 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid quadratic backtracking in headerPattern (dart-lang/tools#2754) 8ea07517f Fri Oct 30 07:45:42 2026 +0100 Moritz [boring] Regenerate the x509-limbo expected failures in the refresh job (dart-lang/tools#2712) 40235c365 Thu Oct 29 14:46:17 2026 +0100 Jonas Finnemann Jensen [markdown] Make HtmlBlockSyntax.parseChildLines iterative (dart-lang/tools#2749) 0ff03f643 Thu Oct 29 14:41:33 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid re-escaping nested image alt text in ImageSyntax.createNode (dart-lang/tools#2752) 784654d01 Thu Oct 29 14:37:11 2026 +0100 Jonas Finnemann Jensen [markdown] Add test cases covering parser and renderer edge cases (dart-lang/tools#2753) 4f2718ad8 Thu Oct 29 14:36:52 2026 +0100 Jonas Finnemann Jensen [markdown] Make Document._parseInlineContent iterative (dart-lang/tools#2750) cac1421d5 Thu Oct 29 14:17:06 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid quadratic duplicate heading ID probing in HtmlRenderer (dart-lang/tools#2748) 66880bcd3 Thu Oct 29 14:11:27 2026 +0100 Jonas Finnemann Jensen [markdown] Check footnote label and empty map before scanning footnote keys (dart-lang/tools#2751) 7f8696523 Thu Oct 29 14:07:06 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid quadratic blank-line lookahead in CodeBlockSyntax (dart-lang/tools#2747) 9da6bb291 Thu Oct 29 14:03:04 2026 +0100 Jonas Finnemann Jensen [markdown] Avoid exponential and quadratic backtracking in tablePattern (dart-lang/tools#2746) dartdoc is held back at db94437, before dart-lang/dartdoc#4312, because its mock SDK version changes conflict in the google3 3-way merge with the hotfix in cl/1005963642. native is held back at e0ca7c6, before dart-lang/native#3742, because deprecating `MacOSCodeConfig(targetVersion: ...)` causes a fatal `deprecated_member_use` diagnostic in `pkg/dartdev/lib/src/native_assets.dart`. web is held back at 4e60e61, before dart-lang/web#596, because it changes `package:web` signatures (e.g. `innerHTML=`, `parseFromString`, `Worker()`) from `JSAny` to `String` in ways that break callers in google3. Change-Id: I53d2cbde741c45b8fd33bca42742549819dd332b Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/572780 Reviewed-by: Brian Quinlan <[email protected]> Commit-Queue: Nate Bosch <[email protected]>
Change the optional closing hash capture group in
headerPattern(
pkgs/markdown/lib/src/patterns.dart) from(#*)to(#+), and enabledotAll: true:RegExp(r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#*)\s*)?$')RegExp(r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#+)\s*)?$', dotAll: true)This fixes quadratic matching time on ATX headings with many spaces before the
text, and changes rendered output in two corner cases described below.
Why this change is necessary
In
headerPattern, the heading content group(?:[ \x09\x0b\x0c].*?)?uses alazy
.*?followed by the optional closing hash sequence(?:\s(#*)\s*)?$.Because
(#*)allowed zero#characters, the subpattern(?:\s(#*)\s*)reduced to
\s\s*whenever(#*)matched the empty string.On an ATX heading line containing many spaces before a non-space character—such
as
'# ${' ' * n}a'—as the lazy.*?advanced one character at a time throughthe n spaces, at every space position
iit attempted to match(?:\s(#*)\s*)?$:\smatched the space ati;(#*)matched'';\s*consumed all remainingn - ispaces up toa;$failed to matcha, forcing the regex engine to backtrack across alln - ispaces before.*?advanced by 1 space toi + 1.Across n spaces, this took 1 + 2 + ... + n = O(n^2) time (32 KB of spaces took
3.7 s; 64 KB over 10 s).
How this change works
Changing
(#*)to(#+)requires the optional closing group(?:\s(#+)\s*)?$to contain at least one#character:#,(?:\s(#+)\s*)?$fails in O(1) after checking a single character (#),so
'# ${' ' * n}a'is scanned in strictly O(n) time.#sequence is present,match[2](closeMarker) capturesthe exact same non-empty
#+string as before.#sequence is present, trailing whitespace is consumed by.*?and stripped byHeaderSyntax's.trim().dotAll: truemakes.matchU+2028(LINE SEPARATOR) andU+2029(PARAGRAPH SEPARATOR), which
LineSplitterleaves inside a line's content.Without it, the old empty
(#*)plus\s(which does match those characters)was the only reason a heading ending in
U+2028matched at all; with(#+)alone such a line would stop being a heading.
Behavior changes
Both changes make the output agree with CommonMark and with the reference
implementations (checked against
commonmark.js0.31 andmarkdown-it14).Closing
#sequences separated by tabs are now recognized.CommonMark §4.2: the optional closing sequence is any number of
#preceded by spaces or tabs and followed only by spaces or tabs. The empty
(#*)let the heading content swallow a real closing sequence in somecases, for example:
###\t#\t<h3>#</h3><h3></h3><h3></h3>In the differential run over 548k documents (pub.dev, github-docs, parser
test suites, OSS-Fuzz) this only affected 27 OSS-Fuzz inputs; no real-world
document changed.
ATX headings may contain
U+2028/U+2029. CommonMark line endings areonly
\n,\r, and\r\n, so these separators are ordinary charactersinside a line and do not prevent a line from being a heading. On
mainatrailing separator happened to work and a mid-line one did not; both work
now:
### Heading\u2028<h3>Heading</h3><h3>Heading</h3><h3>Heading</h3><h3>Heading\u2028</h3>### Heading\u2028 mid\u2029 text<p>### Heading…</p><h3>Heading\u2028 mid\u2029 text</h3># a\u2028 #<p># a\u2028 #</p><h1>a</h1><h1>a</h1><h1>a\u2028</h1>(The trailing separator is dropped by
HeaderSyntax's existing.trim(),matching
commonmark.js;markdown-itkeeps it. That is unchanged by thisPR.) The trailing case occurs in real documents: the
price_textREADME onpub.dev has such a heading, and it regressed to a paragraph when
dotAllwas missing.
Tests
test/original/headers.unit:###\t#\t, a heading with many spaces beforethe text, a heading with a trailing
U+2028, a heading withU+2028andU+2029in the text, and a closing#sequence afterU+2028.test/common_mark/atx_headings.unit)continue to pass unchanged.
Differential testing
Rendered every input with
origin/mainand with this branch (GFM extensionset, 30 s per-file timeout) and compared the HTML. Sources:
mdn/content,github/docs,kubernetes/website,freeCodeCamp,tldr,flutter/website,dart-lang/site-www,microsoft/vscode-docs,withastro/docs,rust-lang/book, GitHub READMEs, and Wikipediacmark,cmark-gfm,commonmark.js,pulldown-cmark,md4c,goldmark,markdown-it,comrak,marked,pandoc, and pathological generatorscmark,md4c, andmarkdown-it-pyfuzzersOSS-Fuzz inputs that sit at the 30 s timeout or the stack limit flip between
runs; every one reported as a new failure was re-run standalone on both trees.
Results:
suites. (A run of the first commit alone, without
dotAll: true, turned theprice_textREADME heading### Use Currency locale for using formattingfollowed by
U+2028into a paragraph; with the second commit that documentrenders identically to
mainagain.)#sequences thatthe old empty
(#*)let the heading text swallow, e.g.### #:<h3>#</h3>→<h3></h3>, which is what CommonMark §4.2,commonmark.js,and
markdown-itproduce.