[markdown] WIP: Fix quadratic, exponential, and deep-recursion by jonasfj · Pull Request #2737 · dart-lang/tools

jonasfj · 2026-10-28T15:04:45Z

Fixes issues combines the changes from #2728, #2729, and #2730 along with fixes for additional quadratic, exponential, and deep-recursion (StackOverflowError) vectors across package:markdown.

Structured as a series of 28 atomic single-file, single-concern code commits so each commit can be reviewed independently:

Reference links & footnotes (link_syntax.dart, footnote_ref_syntax.dart):
- Enforce the 999-character CommonMark limit in LinkSyntax._parseReferenceLinkLabel
- Defer shortcut reference link label extraction in LinkSyntax.close until tryCreateReferenceLink succeeds
- Defer normalizeLinkLabel and sanitizeLinkAttribute until a reference link definition or linkResolver match is found
- Check footnote ^ prefix and empty footnoteReferences map before scanning, and cache case-folded footnote keys and 1-based positions via Expando
Inline link destinations & titles (link_syntax.dart):
- Reject unescaped < in bracketed inline link destinations (<...>) per CommonMark §6.3
- Enforce parenthesis balance (parenCount < 0) and nesting limit (parenCount > 32) in bare inline link destinations
- Reject unescaped ( in parenthesized inline link titles ((...)) per CommonMark §6.3
InlineParser delimiter stack, tree, and open brackets (inline_parser.dart):
- Avoid removeRange and deep recursion in _combineAdjacentText
- Represent InlineParser._delimiterStack as a LinkedList<_DelimiterNode>
- Represent InlineParser._tree as a LinkedList<_TreeNode>
- Track open [ and ![ brackets in a linked stack (_topBracket / _topActiveLinkBracket) for $O(1)$ lookup and [ deactivation
Inline syntax rescanning & backtracking (autolink_syntax.dart, line_break_syntax.dart, inline_parser.dart, inline_html_syntax.dart, code_syntax.dart, autolink_extension_syntax.dart):
- Reject < inside AutolinkSyntax
- Avoid rescanning failed space runs in LineBreakSyntax
- Avoid rescanning failed plain-text runs in _PlainTextSyntax
- Skip unclosed inline HTML tags (<!, <!--, <?, <![CDATA[) before running InlineHtmlSyntax.pattern
- Avoid quadratic scans on unmatched backtick runs in CodeSyntax
- Avoid rescanning failed domain runs in AutolinkExtensionSyntax
Deep recursion & container block nesting (ast.dart, document.dart, html_block_syntax.dart, block_parser.dart):
- Make Element.accept, Element.textContent, Document._parseInlineContent, and HtmlBlockSyntax.parseChildLines iterative
- Cap container block nesting depth at 512 in BlockParser
Block patterns, LinkParser, CodeBlockSyntax, and HtmlRenderer (patterns.dart, link_parser.dart, code_block_syntax.dart, html_renderer.dart):
- Avoid exponential ($O(2^n)$) and quadratic ($O(n^2)$) backtracking in tablePattern
- Avoid quadratic ($O(n^2)$) backtracking in headerPattern
- Reject unescaped ( in parenthesized link reference titles and avoid quadratic line concatenation in LinkParser
- Avoid quadratic blank-line lookahead in CodeBlockSyntax.parseChildLines
- Avoid quadratic duplicate heading ID probing in HtmlRenderer.uniquifyId
Tests & changelog (test/pathological_test.dart, test/regression_test.dart, CHANGELOG.md):
- Add regression tests, 8 KB vs. 64 KB linear-scaling benchmarks across 55 CommonMark + GFM pathological patterns, deep-nesting tests at depth 10,000, and a 200-seed token-alphabet fuzzer

github-actions · 2026-10-28T15:07:14Z

PR Health

Publish ✔️

Package	Version	Status	Publish tag (post-merge)
package:markdown ⭐	7.4.1-wip	WIP (no publish necessary)

16 already published.
26 WIP (no publish necessary).

Documentation at https://github.com/dart-lang/ecosystem/wiki/Publishing-automation.

This check can be disabled by tagging the PR with skip-publish-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).

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.

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.

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.

Coverage ✔️

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

gemini-code-assist

Code Review

This pull request introduces comprehensive performance optimizations and stack overflow protections to the markdown parser. Key changes include refactoring recursive AST traversals, inline content parsing, and HTML block parsing into iterative stack-based implementations. Additionally, it addresses quadratic time complexity issues in inline parsing by utilizing a LinkedList for the delimiter stack, caching lookups (such as footnotes, HTML closers, and backtick scans), capping container nesting depth, and enforcing limits on link label lengths and parentheses nesting. A review comment suggests a performance improvement in code_syntax.dart to directly return whether a valid closing run exists when the document has already been fully scanned, avoiding redundant scans.

gemini-code-assist · 2026-10-28T15:08:16Z

+    if (state.scannedToEnd && (state.lastRunAt[length] ?? -1) < openEnd) {
+      return false;
+    }


When state.scannedToEnd is true, the entire document has already been scanned, and state.lastRunAt contains the final positions of all backtick runs. Instead of only returning false when no matching run exists and otherwise falling through to re-scan the document, we can directly return whether a valid closing run exists at or after openEnd. This avoids redundant scanning and improves performance.

Suggested change

if (state.scannedToEnd && (state.lastRunAt[length] ?? -1) < openEnd) {

return false;

}

if (state.scannedToEnd) {

return (state.lastRunAt[length] ?? -1) >= openEnd;

}

Add `pkgs/markdown/test/pathological_test.dart`, expand `pkgs/markdown/test/regression_test.dart`, and document the DoS fixes in `pkgs/markdown/CHANGELOG.md`. ---- Each of the preceding commits fixes a quadratic O(n^2), exponential O(2^n), or deep-recursion (`StackOverflowError`) vulnerability in `package:markdown`. Without automated scaling assertions, deep-nesting tests, and fuzz testing over adversarial token combinations, regressions in regexes, delimiter processing, or AST traversal could silently reintroduce super-linear behavior without breaking functional CommonMark/GFM output tests. 1. **`pkgs/markdown/test/pathological_test.dart`**: - **Linear-scaling suite (`_cases`)**: Tests 51 pathological input generators in both CommonMark and GFM (`ExtensionSet.gitHubWeb`) modes at 8 KB and 64 KB (8x size ratio), asserting that the 64 KB render time is within a bounded linear multiple (`3 * _scale`) of the 8 KB render time (where linear growth is ~8x and quadratic growth is ~64x). - **Deep-nesting suite (`_deepCases`)**: Renders 6 deep-nesting generators at depth 32,000 (nested strong emphasis, nested strong emphasis run, nested strong emphasis with trailing text, nested strong emphasis in image alt, nested blockquotes, and nested lists) in both CommonMark and GFM modes to verify that no `StackOverflowError` is thrown. - **Custom `linkBuilder` regression test**: Verifies that a custom `linkBuilder` that does not invoke `getChildren()` produces the expected AST when earlier delimiters resolve into emphasis elements. - **Token-alphabet fuzzer**: Runs 200 deterministic PRNG iterations (`Random(42)`), each picking a random subset of 2–6 tokens from a 23-token Markdown alphabet and generating a 2,000-token string to verify that arbitrary token combinations render in under 2 seconds without hanging or throwing. 2. **`pkgs/markdown/test/regression_test.dart`**: - Adds targeted timing regression tests for unclosed inline link destinations and titles and inline delimiter runs. 3. **`pkgs/markdown/CHANGELOG.md`**: - Documents the security and performance fixes under `7.4.1-wip`.

github-actions Bot added the package:markdown label Oct 28, 2026

gemini-code-assist Bot reviewed Oct 28, 2026

View reviewed changes

jonasfj force-pushed the markdown_all_dos_fixes branch 4 times, most recently from dc6993e to 8352855 Compare October 29, 2026 09:08

jonasfj changed the title ~~[markdown] WIP: Fix quadratic, exponential, and deep-recursion DoS vectors~~ [markdown] WIP: Fix quadratic, exponential, and deep-recursion Oct 29, 2026

jonasfj force-pushed the markdown_all_dos_fixes branch 6 times, most recently from ec0c6ac to 3a4fe38 Compare October 29, 2026 14:30

jonasfj mentioned this pull request Oct 30, 2026

[markdown] Avoid quadratic removeRange in _combineAdjacentText #2758

Merged

jonasfj force-pushed the markdown_all_dos_fixes branch from 3a4fe38 to b75b70c Compare October 30, 2026 13:06

jonasfj mentioned this pull request Oct 30, 2026

[markdown] Require balanced parentheses before bare inline link titles #2768

Merged

avicennaxdev mentioned this pull request Nov 3, 2026

[markdown] A later ** stays literal after a strong nested in an intraword emphasis #2781

Open

jonasfj force-pushed the markdown_all_dos_fixes branch from b75b70c to dd7de15 Compare November 4, 2026 09:07

jonasfj mentioned this pull request Nov 4, 2026

[markdown] Defer shortcut reference link label extraction in LinkSyntax.close #2785

Merged

jonasfj force-pushed the markdown_all_dos_fixes branch 7 times, most recently from 98fee9c to 3dc5181 Compare November 6, 2026 12:35

jonasfj force-pushed the markdown_all_dos_fixes branch from 3dc5181 to d057d0b Compare November 9, 2026 08:53

palmoni5 mentioned this pull request Nov 11, 2026

perf(markdown): flatten nested Element.textContent iteratively Otzaria/tools#39

Merged

palmoni5 mentioned this pull request Nov 11, 2026

[markdown] Compute Element.textContent iteratively #2864

Closed

Navigation Menu

Repository navigation

[markdown] WIP: Fix quadratic, exponential, and deep-recursion - #2737

[markdown] WIP: Fix quadratic, exponential, and deep-recursion#2737
jonasfj wants to merge 1 commit into
mainfrom
markdown_all_dos_fixes

jonasfj commented Oct 28, 2026 •

edited

Loading

Uh oh!

github-actions Bot commented Oct 28, 2026 •

edited

Loading

Uh oh!

gemini-code-assist Bot left a comment

Uh oh!

gemini-code-assist Bot Oct 28, 2026

Uh oh!

This branch has not been deployed

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

Conversation

jonasfj commented Oct 28, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

github-actions Bot commented Oct 28, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR Health

Uh oh!

gemini-code-assist Bot left a comment

Choose a reason for hiding this comment

Code Review

Uh oh!

gemini-code-assist Bot Oct 28, 2026

Choose a reason for hiding this comment

Uh oh!

This branch has not been deployed

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

1 participant

jonasfj commented Oct 28, 2026 •

edited

Loading

github-actions Bot commented Oct 28, 2026 •

edited

Loading