Skip to content

[markdown] Use linked lists for InlineParser AST and delimiter stack - #2729

Closed
jonasfj wants to merge 4 commits into
mainfrom
fix_markdown_dos_vulnerability
Closed

[markdown] Use linked lists for InlineParser AST and delimiter stack#2729
jonasfj wants to merge 4 commits into
mainfrom
fix_markdown_dos_vulnerability

Conversation

@jonasfj

@jonasfj jonasfj commented Oct 27, 2026

Copy link
Copy Markdown
Member

Replace List-based AST/delimiter searches and removals in InlineParser with doubly-linked lists (_TreeNode, _DelimiterNode) and a linked bracket stack (_topBracket), bound backward emphasis scans by a 6-slot openersBottom table, and compact adjacent Text nodes iteratively in place.

@github-actions

github-actions Bot commented Oct 27, 2026 •
edited
Loading

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/inline_parser.dart 💚 99 % ⬆️ 2 %

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[bot]
gemini-code-assist Bot reviewed Oct 27, 2026
View reviewed changes

@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 inline parsing performance of the markdown parser to prevent quadratic time complexity on lines with many brackets or emphasis delimiters. It replaces the list-based delimiter stack and HTML node tree with custom linked list structures (_DelimiterNode and _TreeNode) and updates the parsing routines accordingly. A regression test is also added to verify the performance improvement. The reviewer suggested optimizing the StringBuffer initialization in _combineAdjacentText to avoid an intermediate string allocation.

Comment thread pkgs/markdown/lib/src/inline_parser.dart
Comment on lines +406 to +408
final buffer = StringBuffer(
'${node.textContent}${nodes[i + 1].textContent}',
);

@gemini-code-assist gemini-code-assist Bot Oct 27, 2026

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.

medium

Using string interpolation inside the StringBuffer constructor creates an intermediate string before passing it to the buffer. Since this is a performance-focused PR, we can optimize this by initializing the StringBuffer with the first string and then writing the second string directly, avoiding the intermediate string allocation.

Suggested change
final buffer = StringBuffer(
'${node.textContent}${nodes[i + 1].textContent}',
);
final buffer = StringBuffer(node.textContent)
..write(nodes[i + 1].textContent);

@jonasfj
jonasfj force-pushed the fix_markdown_dos_vulnerability branch 4 times, most recently from b3ca705 to c3ab156 Compare October 27, 2026 14:35
@jonasfj
jonasfj force-pushed the fix_markdown_dos_vulnerability branch from c3ab156 to 2eaeb88 Compare October 27, 2026 14:57
@jonasfj jonasfj mentioned this pull request Oct 28, 2026
Draft
@jonasfj jonasfj closed this Oct 30, 2026
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

1 more reviewer
@gemini-code-assist gemini-code-assist[bot] gemini-code-assist[bot] left review comments
Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

package:markdown

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

1 participant

@jonasfj