Skip to content

[markdown] Avoid quadratic backtracking in headerPattern - #2754

Merged
jonasfj merged 4 commits into
mainfrom
markdown_header_pattern_backtracking
Oct 30, 2026
Merged

jonasfj merged 4 commits into
mainfrom
markdown_header_pattern_backtracking

Conversation

@jonasfj

@jonasfj jonasfj commented Oct 29, 2026 •

Copy link
Copy Markdown
Member

Change the optional closing hash capture group in headerPattern
(pkgs/markdown/lib/src/patterns.dart) from (#*) to (#+), and enable
dotAll: true:

  • Before: RegExp(r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#*)\s*)?$')
  • After: 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 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 (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:

  • 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().

dotAll: true makes . match U+2028 (LINE SEPARATOR) and U+2029
(PARAGRAPH SEPARATOR), which LineSplitter leaves 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+2028 matched 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.js 0.31 and markdown-it 14).

  1. 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 some
    cases, for example:

    Input Before After commonmark.js / markdown-it
    ###\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.

  2. ATX headings may contain U+2028 / U+2029. CommonMark line endings are
    only \n, \r, and \r\n, so these separators are ordinary characters
    inside a line and do not prevent a line from being a heading. On main a
    trailing separator happened to work and a mid-line one did not; both work
    now:

    Input Before After commonmark.js markdown-it
    ### 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> same same
    # 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-it keeps it. That is unchanged by this
    PR.) The trailing case occurs in real documents: the price_text README on
    pub.dev has such a heading, and it regressed to a paragraph when dotAll
    was missing.

Tests

  • test/original/headers.unit: ###\t#\t, a heading with many spaces before
    the text, a heading with a trailing U+2028, a heading with U+2028 and
    U+2029 in the text, and a closing # sequence after U+2028.
  • CommonMark spec examples for ATX headings (test/common_mark/atx_headings.unit)
    continue to pass unchanged.

Differential testing

Rendered every input with origin/main and with this branch (GFM extension
set, 30 s per-file timeout) and compared the HTML. Sources:

  • pub.dev: 367,926 Markdown files from 93,452 packages
  • Real-world docs: 116,231 files from 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 Wikipedia
  • Parser test suites: 6,458 cases from cmark, cmark-gfm, commonmark.js,
    pulldown-cmark, md4c, goldmark, markdown-it, comrak, marked,
    pandoc, and pathological generators
  • OSS-Fuzz: 57,716 inputs from the cmark, md4c, and markdown-it-py fuzzers

OSS-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:

  • No HTML differences in pub.dev, the real-world docs, or the parser test
    suites. (A run of the first commit alone, without dotAll: true, turned the
    price_text README heading ### Use Currency locale for using formatting
    followed by U+2028 into a paragraph; with the second commit that document
    renders identically to main again.)
  • Rendered HTML differs for 28 OSS-Fuzz inputs, all closing # sequences that
    the old empty (#*) let the heading text swallow, e.g. ### # :
    <h3>#</h3> → <h3></h3>, which is what CommonMark §4.2, commonmark.js,
    and markdown-it produce.
  • No new exceptions; 9 OSS-Fuzz timeouts resolved; cumulative parse time −3.5%.

@github-actions

github-actions Bot commented Oct 29, 2026 •

Copy link
Copy Markdown

PR Health

Breaking changes ✔️
Package Change Current Version New Version Needed Version Looking good?
markdown Non-Breaking 7.3.1 7.4.1-wip 7.4.1-wip ✔️

This check can be disabled by tagging the PR with skip-breaking-check.

Coverage ✔️
File Coverage
pkgs/markdown/lib/src/patterns.dart 💚 100 %

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 skip-coverage-check.

Changelog Entry ✔️
Package Changed Files

Changes to files need to be accounted for in their respective changelogs.

This check can be disabled by tagging the PR with skip-changelog-check (for example, for non-user-visible changes when the package version is already at -wip).

License Headers ✔️
// Copyright (c) 2026, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.

Files
no missing headers

All source files should start with a license header.

Unrelated files missing license headers
Files
pkgs/html/test/differential_test.dart
pkgs/html/test/dom_parsing_test.dart
pkgs/html/test/mxss_test.dart
pkgs/html/test/noah_ark_clause_limit_test.dart

This check can be disabled by tagging the PR with skip-license-check.

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.

Package Leaked API symbol Leaking sources

This check can be disabled by tagging the PR with skip-leaking-check.

Unused Dependencies ✔️
Package Status
markdown ✔️ All dependencies utilized correctly.

For details on how to fix these, see dependency_validator.

This check can be disabled by tagging the PR with skip-unused-dependencies-check.

@gemini-code-assist gemini-code-assist Bot left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

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*)?$',

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

high

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.

Suggested change
r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c].*?)?(?:\s(#+)\s*)?$',
r'^ {0,3}(#{1,6})(?:[ \x09\x0b\x0c][^\r\n]*?)?(?:\s(#+)\s*)?$',

@jonasfj
jonasfj force-pushed the markdown_header_pattern_backtracking branch from 7cb0ac2 to 0eb3b0b Compare October 30, 2026 08:37
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.
@jonasfj
jonasfj force-pushed the markdown_header_pattern_backtracking branch from 0d9e48f to 9be0fb6 Compare October 30, 2026 09:22
@jonasfj
jonasfj force-pushed the markdown_header_pattern_backtracking branch from 9be0fb6 to 4bd13bb Compare October 30, 2026 09:26
@jonasfj
jonasfj requested a review from szakarias October 30, 2026 09:42
@jonasfj
jonasfj marked this pull request as ready for review October 30, 2026 09:42
@jonasfj
jonasfj requested a review from srawlins as a code owner October 30, 2026 09:42
@jonasfj
jonasfj removed the request for review from srawlins October 30, 2026 09:44
@jonasfj jonasfj changed the title [WIP] [markdown] Avoid quadratic backtracking in headerPattern [markdown] Avoid quadratic backtracking in headerPattern Oct 30, 2026

@szakarias szakarias left a comment

Copy link
Copy Markdown
Contributor

Choose a reason for hiding this comment

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

LGTM

Comment thread pkgs/markdown/lib/src/patterns.dart Resolved
Co-authored-by: Sarah Zakarias <[email protected]>
@jonasfj
jonasfj merged commit 86ed0f9 into main Oct 30, 2026
15 of 16 checks passed
@jonasfj
jonasfj deleted the markdown_header_pattern_backtracking branch October 30, 2026 10:08
copybara-service Bot pushed a commit to dart-lang/sdk that referenced this pull request Nov 3, 2026
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]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Projects

None yet

Development

Successfully merging this pull request may close these issues.

2 participants