[markdown] Make Document._parseInlineContent iterative by jonasfj · Pull Request #2750 · dart-lang/tools

jonasfj · 2026-10-29T12:59:04Z

Rewrite Document._parseInlineContent in document.dart using an explicit
stack of (List<Node>, int) frames instead of recursing on node.children.

Why this change is necessary

During Document.parseLines, after BlockParser builds the block-level AST,
Document._parseInlineContent(List<Node> nodes) walks the block tree to replace
UnparsedContent placeholders with parsed inline AST nodes, recursing into
node.children for every block Element.

On deeply nested block structures (or custom block syntaxes that produce deep
Element trees), recursing on node.children grows the call stack
proportionally to tree depth.

How this change works

We replace the recursive _parseInlineContent(node.children!) call with an
explicit work stack final stack = <(List<Node>, int)>[(nodes, 0)];, where each
frame holds the current List<Node> and the index i at which to resume:

While stack.isNotEmpty, we pop final (currentNodes, startIndex) = stack.removeLast(); and iterate for (var i = startIndex; i < currentNodes.length; i++):
- If node is UnparsedContent, we parse its inline nodes via
  parseInline(node.textContent), replace currentNodes[i] via removeAt(i)
  and insertAll(i, inlineNodes), and advance i += inlineNodes.length - 1.
- If node is Element && node.children != null, we push (currentNodes, i + 1)
  followed by (node.children!, 0) onto stack and break out of the for
  loop so children are processed in the exact same depth-first pre-order as the
  original recursive implementation while using O(1) call-stack frames.

Rewrite `Document._parseInlineContent` in `document.dart` using an explicit `stack` of `(List<Node>, int)` frames instead of recursing on `node.children`. ---- ### Why this change is necessary During `Document.parseLines`, after `BlockParser` builds the block-level AST, `Document._parseInlineContent(List<Node> nodes)` walks the block tree to replace `UnparsedContent` placeholders with parsed inline AST nodes, recursing into `node.children` for every block `Element`. On deeply nested block structures (or custom block syntaxes that produce deep `Element` trees), recursing on `node.children` grows the call stack proportionally to tree depth. ### How this change works We replace the recursive `_parseInlineContent(node.children!)` call with an explicit work stack `final stack = <(List<Node>, int)>[(nodes, 0)];`, where each frame holds the current `List<Node>` and the index `i` at which to resume: - While `stack.isNotEmpty`, we pop `final (currentNodes, startIndex) = stack.removeLast();` and iterate `for (var i = startIndex; i < currentNodes.length; i++)`: - If `node is UnparsedContent`, we parse its inline nodes via `parseInline(node.textContent)`, replace `currentNodes[i]` via `removeAt(i)` and `insertAll(i, inlineNodes)`, and advance `i += inlineNodes.length - 1`. - If `node is Element && node.children != null`, we push `(currentNodes, i + 1)` followed by `(node.children!, 0)` onto `stack` and `break` out of the `for` loop so children are processed in the exact same depth-first pre-order as the original recursive implementation while using O(1) call-stack frames.

gemini-code-assist

Code Review

This pull request refactors the _parseInlineContent method in pkgs/markdown/lib/src/document.dart to use an iterative approach with an explicit stack instead of recursion, preventing stack overflow errors on deeply nested blocks. The feedback suggests an optimization to avoid pushing redundant parent states onto the stack when there are no remaining elements left to process in the current node list.

gemini-code-assist · 2026-10-29T13:00:11Z

+        } else if (node is Element && node.children != null) {
+          stack.add((currentNodes, i + 1));
+          stack.add((node.children!, 0));
+          break;
+        }


When i + 1 is equal to currentNodes.length, there are no more elements left to process in currentNodes. Pushing (currentNodes, i + 1) onto the stack in this case is redundant because when it is popped, the loop condition i < currentNodes.length will immediately fail and the frame will be discarded.

We can optimize this by only pushing the parent state back onto the stack if there are actually remaining elements to process (i.e., i + 1 < currentNodes.length). This avoids unnecessary record allocations and stack operations.

} else if (node is Element && node.children != null) { if (i + 1 < currentNodes.length) { stack.add((currentNodes, i + 1)); } stack.add((node.children!, 0)); break; }

github-actions · 2026-10-29T13:00:58Z

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/document.dart	💚 93 %

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.

szakarias

Looks good, could we perhaps have some tests to accompany this and the others in this line of changes?

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]>

jonasfj requested a review from srawlins as a code owner October 29, 2026 12:59

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

gemini-code-assist Bot reviewed Oct 29, 2026

View reviewed changes

szakarias approved these changes Oct 29, 2026

View reviewed changes

Merge branch 'main' into markdown_parse_inline_content_iterative

438f416

jonasfj merged commit 4f2718a into main Oct 29, 2026
16 checks passed

jonasfj deleted the markdown_parse_inline_content_iterative branch October 29, 2026 13:36

Navigation Menu

Repository navigation

[markdown] Make Document._parseInlineContent iterative - #2750

[markdown] Make Document._parseInlineContent iterative#2750
jonasfj merged 2 commits into
mainfrom
markdown_parse_inline_content_iterative

jonasfj commented Oct 29, 2026

Uh oh!

gemini-code-assist Bot left a comment

Uh oh!

gemini-code-assist Bot Oct 29, 2026

Uh oh!

github-actions Bot commented Oct 29, 2026 •

edited

Loading

Uh oh!

szakarias left a comment

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

Conversation

jonasfj commented Oct 29, 2026

Why this change is necessary

How this change works

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 29, 2026

Choose a reason for hiding this comment

Uh oh!

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

Uh oh!

PR Health

Uh oh!

szakarias left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

github-actions Bot commented Oct 29, 2026 •

edited

Loading