Skip to content

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

Merged
jonasfj merged 2 commits into
mainfrom
markdown_defer_reference_label
Nov 4, 2026
Merged

[markdown] Defer shortcut reference link label extraction in LinkSyntax.close#2785
jonasfj merged 2 commits into
mainfrom
markdown_defer_reference_label

Conversation

@jonasfj

@jonasfj jonasfj commented Nov 4, 2026 •
edited
Loading

Copy link
Copy Markdown
Member

Move the parser.source.substring(opener.endPos, textEnd) slice and the
999-character length check for shortcut and collapsed reference links into a
helper (_tryCreateShortcutReferenceLink), and for full reference links
([text][label]), only extract text when a custom linkBuilder is used.

Why this change is necessary

Previously, LinkSyntax.close unconditionally executed:

final text = parser.source.substring(opener.endPos, parser.pos);

at the very top of close() whenever a closing ] matched an opening [ or
![. However, text is only needed in two places:

  1. As the link label of a shortcut ([foo]) or collapsed ([foo][]) reference
    link (which CommonMark caps at 999 characters); or
  2. As the second (title) argument passed to a custom linkBuilder callback
    for a full reference link ([text][label]) when the caller supplied a
    non-default linkBuilder to Document.

Inline links ([text](url)) never use text at all (they call createNode
directly), full reference links ([text][label]) do not use text when
linkBuilder == _noBuilder, and unmatched bracket pairs ([[[...]]]) that
exceed 999 characters cannot form a shortcut or collapsed reference link either.

On deeply nested brackets such as '${'[' * n}${'a' * n}${']' * n}' or
'${'[' * n}x${'][a]' * n}', unconditionally calling substring(opener.endPos, parser.pos) on every ] copied O(n) characters n times, taking O(n^2) time and
allocating O(n^2) string memory.

How this change works

  1. At the start of LinkSyntax.close, we record final textEnd = parser.pos;
    (O(1)) instead of slicing parser.source.
  2. For inline links ([text](url)), createNode(link.destination, link.title, getChildren: getChildren) is called directly without ever slicing text.
  3. For collapsed reference links ([text][]), parser.pos advances past []
    and delegates to _tryCreateShortcutReferenceLink(context, textEnd).
  4. For full reference links ([text][label]), label is parsed by
    _parseReferenceLinkLabel(parser) (bounded to 999 chars), and text is only
    sliced (parser.source.substring(opener.endPos, textEnd)) when
    linkBuilder != _noBuilder.
  5. For shortcut/collapsed reference links, _tryCreateShortcutReferenceLink
    checks if (textEnd - opener.endPos > 999) return null; before calling
    parser.source.substring(opener.endPos, textEnd), guaranteeing that each
    substring slice is at most 999 characters (O(1)).

Behavior change

Shortcut ([label]) and collapsed ([label][]) reference links whose label
has more than 999 characters are no longer resolved, and linkResolver /
linkBuilder are no longer invoked for them. CommonMark §4.7 limits link
labels to 999 characters; #2765 applied the limit to full reference links
([text][label]), this applies it to the remaining two forms. Full reference
links are unchanged: the link text passed as the title argument to a custom
linkBuilder is still unbounded, and it is only extracted when such a builder
is configured.

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
  • Repository READMEs: 491,134 unique READMEs across GitHub, PyPI, HuggingFace,
    and npm
  • 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 any source.
  • 3 OSS-Fuzz timeouts resolved; 2 stack-overflow messages changed wording.
  • 4 OSS-Fuzz inputs (131–523 KB) were reported as new timeouts — standalone (three runs each) three of them are flips: 15.4 s / 5.2 s / 3.8 s on main vs 15.4 s / 5.1 s / 3.1 s here. One, a 523 KB md4c input with 120,000 [ and 5,800 ], is consistently slower: 4.0 s on main, 6.3 s on this branch. That is the bracket/delimiter-stack quadratic that is still open on main (the subject of the linked-list commits in [markdown] WIP: Fix quadratic, exponential, and deep-recursion #2737): a few of its […] candidates with labels over 999 characters used to resolve as reference links and be consumed; now they are correctly rejected and their brackets stay on the List-backed delimiter stack, so the existing O(n) scans run more often. For contrast, the input this change is for, '[' * 8000 + 'a' + ']' * 8000 (16 KB), goes from 4.3 s on main to 0.3 s here.
    Cumulative parse time −3.3%.

@jonasfj
[markdown] Defer shortcut reference link label extraction in LinkSynt…
225072a 
…ax.close

Move the `parser.source.substring(opener.endPos, textEnd)` slice and the
999-character length check for shortcut and collapsed reference links into a
helper (`_tryCreateShortcutReferenceLink`), and for full reference links
(`[text][label]`), only extract `text` when a custom `linkBuilder` is used.

----

### Why this change is necessary

Previously, `LinkSyntax.close` unconditionally executed:
```dart
final text = parser.source.substring(opener.endPos, parser.pos);
```
at the very top of `close()` whenever a closing `]` matched an opening `[` or
`![`. However, `text` is only needed in two places:
1. As the link label of a shortcut (`[foo]`) or collapsed (`[foo][]`) reference
   link (which CommonMark caps at 999 characters); or
2. As the second (`title`) argument passed to a custom `linkBuilder` callback
   for a full reference link (`[text][label]`) when the caller supplied a
   non-default `linkBuilder` to `Document`.

Inline links (`[text](url)`) never use `text` at all (they call `createNode`
directly), full reference links (`[text][label]`) do not use `text` when
`linkBuilder == _noBuilder`, and unmatched bracket pairs (`[[[...]]]`) that
exceed 999 characters cannot form a shortcut or collapsed reference link either.

On deeply nested brackets such as `'${'[' * n}${'a' * n}${']' * n}'` or
`'${'[' * n}x${'][a]' * n}'`, unconditionally calling `substring(opener.endPos,
parser.pos)` on every `]` copied O(n) characters n times, taking O(n^2) time and
allocating O(n^2) string memory.

### How this change works

1. At the start of `LinkSyntax.close`, we record `final textEnd = parser.pos;`
   (O(1)) instead of slicing `parser.source`.
2. For inline links (`[text](url)`), `createNode(link.destination, link.title,
   getChildren: getChildren)` is called directly without ever slicing `text`.
3. For collapsed reference links (`[text][]`), `parser.pos` advances past `[]`
   and delegates to `_tryCreateShortcutReferenceLink(context, textEnd)`.
4. For full reference links (`[text][label]`), `label` is parsed by
   `_parseReferenceLinkLabel(parser)` (bounded to 999 chars), and `text` is only
   sliced (`parser.source.substring(opener.endPos, textEnd)`) when
   `linkBuilder != _noBuilder`.
5. For shortcut/collapsed reference links, `_tryCreateShortcutReferenceLink`
   checks `if (textEnd - opener.endPos > 999) return null;` *before* calling
   `parser.source.substring(opener.endPos, textEnd)`, guaranteeing that each
   substring slice is at most 999 characters (O(1)).
gemini-code-assist[bot]
gemini-code-assist Bot reviewed Nov 4, 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 implements the CommonMark limit on link labels, ensuring that shortcut and collapsed reference links with labels exceeding 999 characters are no longer resolved. It introduces a helper method _tryCreateShortcutReferenceLink to enforce this limit and adds comprehensive regression tests. The review feedback suggests a performance optimization to defer the substring slice of text even further by checking if the reference exists in linkReferences first, thereby avoiding unnecessary substring operations for successfully resolved full reference links.

Comment thread pkgs/markdown/lib/src/inline_syntaxes/link_syntax.dart
Comment on lines +110 to +112
final text = linkBuilder == _noBuilder
? null
: parser.source.substring(opener.endPos, textEnd);

@gemini-code-assist gemini-code-assist Bot Nov 4, 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

We can defer the substring slice of text even further. Even if a custom linkBuilder is registered (i.e., linkBuilder != _noBuilder), we only need text if the reference is not found in linkReferences. If the reference is successfully resolved, _resolveReferenceLink returns early and linkBuilder is never called, making the text slice unnecessary.

By checking if the reference exists in linkReferences first, we can completely avoid the substring operation for all successfully resolved full reference links.

        final hasReference = parser.document.linkReferences
            .containsKey(normalizeLinkLabel(label));
        final text = (hasReference || linkBuilder == _noBuilder)
            ? null
            : parser.source.substring(opener.endPos, textEnd);

@github-actions

github-actions Bot commented Nov 4, 2026 •
edited
Loading

Copy link
Copy Markdown

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
pkgs/markdown/lib/src/inline_syntaxes/link_syntax.dart 💚 99 % ⬆️ 0 %

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.

@jonasfj
jonasfj marked this pull request as ready for review November 4, 2026 12:13
@jonasfj
jonasfj requested a review from srawlins as a code owner November 4, 2026 12:13
@jonasfj
jonasfj requested review from sigurdm and removed request for srawlins November 4, 2026 12:13
sigurdm
sigurdm approved these changes Nov 4, 2026
View reviewed changes
Comment thread pkgs/markdown/lib/src/inline_syntaxes/link_syntax.dart
Comment on lines +110 to 113
final text = linkBuilder == _noBuilder
? null
: parser.source.substring(opener.endPos, textEnd);
return _tryCreateReferenceLink(context, label, text, secondary: true);

@sigurdm sigurdm Nov 4, 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.

Optional: in _resolveReferenceLink, if a full reference link [text][label] matches an entry in linkReferences, title (text) is unused even when a custom linkBuilder/linkResolver is provided, and when linkReference == null and linkBuilder == _noBuilder, _resolveReferenceLink still runs the three label.replaceAll(...) calls before calling _noBuilder.

If _resolveReferenceLink checks if (linkBuilder == _noBuilder) return null; in its else branch and only slices parser.source.substring(opener.endPos, textEnd) there (or via textEnd), we avoid both the text slice on resolved [text][label] links when linkResolver is set and the replaceAll allocations when linkBuilder == _noBuilder.

@jonasfj jonasfj Nov 4, 2026

Copy link
Copy Markdown
Member Author

Choose a reason for hiding this comment

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

I care about degenerate complexity, not making it a bit faster.

@jonasfj
jonasfj merged commit b1f6f99 into main Nov 4, 2026
21 checks passed
@jonasfj
jonasfj deleted the markdown_defer_reference_label branch November 4, 2026 13:31
copybara-service Bot pushed a commit to dart-lang/sdk that referenced this pull request Nov 5, 2026
@natebosch dart-scoped@luci-project-accounts.iam.gserviceaccount.com
[deps] rev core, dartdoc, ecosystem, http, native, protobuf, tools, web
cc100c0 
Revisions updated by `dart tools/rev_sdk_deps.dart`.

core (https://github.com/dart-lang/core/compare/24e09c4..36f57a9):
  36f57a99  Tue Nov 3 14:26:17 2026 +0100  Sigurd Meldgaard  [os_detect] Remove bin/os_detect.dart (dart-lang/core#1015)
  86bacfca  Tue Nov 3 05:15:19 2026 -0500  Justin White  [characters] Fix RangeError on an unpaired tail surrogate at range start (dart-lang/core#1033)

dartdoc (https://github.com/dart-lang/dartdoc/compare/db94437..2f6847b):
  2f6847bd  Thu Oct 29 11:47:04 2026 +0200  Sergey G. Grekhov  Add tests for invalid doc comments placement (dart-lang/dartdoc#4301)
  17f2f0a3  Thu Oct 29 10:16:36 2026 +0100  Sarah Zakarias  Compare base elements and unify properties in doc-reference-target-differs (dart-lang/dartdoc#4307)

dartdoc is held back at 2f6847b, before dart-lang/dartdoc#4312, because its
mock SDK version changes conflict in the google3 3-way merge with the hotfix
in cl/1005963642.

ecosystem (https://github.com/dart-lang/ecosystem/compare/f8faabf..54e1673):
  54e1673  Wed Nov 4 09:46:54 2026 +0100  Sigurd Meldgaard  fix(firehose): resolve dartExecutable via package:cli_util (dart-lang/ecosystem#469)
  d754065  Tue Nov 3 10:09:45 2026 -0800  Kevin Moore  refactor(corpus): use path.join and seal closed type hierarchies (dart-lang/ecosystem#476)

http (https://github.com/dart-lang/http/compare/8c0d66a..1f869d0):
  1f869d0  Tue Nov 3 15:51:52 2026 -0800  dependabot[bot]  chore(deps): bump the github-actions group with 8 updates (dart-lang/http#2052)
  6d7f402  Tue Nov 3 14:12:04 2026 -0800  Brian Quinlan  feat(cupertino_http): support custom trust eval (dart-lang/http#2038)
  73f8c36  Tue Nov 3 10:15:16 2026 -0800  Brian Quinlan  chore(cupertino_http): ready 3.1.1 release (dart-lang/http#2056)

native (https://github.com/dart-lang/native/compare/b442038..1838637):
  183863758  Wed Nov 4 09:01:27 2026 -0300  Daco Harkes  [hooks_runner] Add `PKG_CONFIG_PATH` to environment variables allowlist (dart-lang/native#3779)
  c9e8118d4  Wed Nov 4 08:16:20 2026 +1100  Liam Appelbe  [jni] Fix release mode segfault (dart-lang/native#3777)
  5999cf7e4  Wed Nov 4 08:16:16 2026 +1100  Liam Appelbe  [objective_c] Prepare to publish (dart-lang/native#3778)
  d294d9942  Tue Nov 3 15:15:49 2026 +0100  Michael Goderbauer  [hooks_runner] Write recorded_uses.json under directory lock in link() (dart-lang/native#3770)
  33aa5ef04  Tue Nov 3 11:42:38 2026 +1100  Liam Appelbe  [objective_c] Cheaper and safer object/block validity checks (dart-lang/native#3776)

protobuf (https://github.com/dart-lang/protobuf/compare/1d52301..19191c8):
  19191c8  Wed Nov 4 17:14:33 2026 +0100  Sigurd Meldgaard  Use dart.tool.dart2wasm in json.dart so DDC uses json_web.dart (google/protobuf.dart#1108)

tools (https://github.com/dart-lang/tools/compare/1579f8d..a342744):
  a3427446f  Wed Nov 4 15:11:35 2026 +0100  Jonas Finnemann Jensen  Update CODEOWNERS for pkgs/markdown (dart-lang/tools#2795)
  08c9afdc0  Wed Nov 4 14:40:44 2026 +0100  Jonas Finnemann Jensen  [markdown] Check URL boundary before matching in AutolinkExtensionSyntax (dart-lang/tools#2786)
  0fc5edcae  Wed Nov 4 14:35:48 2026 +0100  Jonas Finnemann Jensen  [markdown] Skip unclosed inline HTML tags before matching RegExp (dart-lang/tools#2788)
  b1f6f9956  Wed Nov 4 14:31:55 2026 +0100  Jonas Finnemann Jensen  [markdown] Defer shortcut reference link label extraction in LinkSyntax.close (dart-lang/tools#2785)
  ab135e072  Wed Nov 4 14:30:37 2026 +0100  Jonas Finnemann Jensen  [markdown] Avoid quadratic trailing-paren scan in AutolinkExtensionSyntax (dart-lang/tools#2787)
  f329bf3ea  Wed Nov 4 17:09:34 2026 +0530  Ananya Kaul  [code_builder] Separate chained cascades after nullable casts (dart-lang/tools#2704)
  0a57e3446  Wed Nov 4 05:28:40 2026 +0530  Aman Maurya  fix(coverage): allow empty coverage files from skipped test suites (`#2667`) (dart-lang/tools#2668)
  e95958f6a  Tue Nov 3 21:53:57 2026 +0000  Keerti Parthasarathy  [unified_analytics] Add root_tool and leaf_tool to every event; key consent on root_tool (dart-lang/tools#2784)
  5da06a508  Tue Nov 3 13:11:04 2026 +0100  Jonas Finnemann Jensen  [markdown] Reject unescaped '(' in parenthesized inline link titles (dart-lang/tools#2770)
  f3a5c9277  Tue Nov 3 13:09:32 2026 +0100  Jonas Finnemann Jensen  [markdown] Cap parenthesis nesting in bare inline link destinations (dart-lang/tools#2769)
  820ce5fb7  Tue Nov 3 13:04:35 2026 +0100  Jonas Finnemann Jensen  [markdown] Reject unescaped '(' in parenthesized link reference titles (dart-lang/tools#2771)
  775c5d080  Tue Nov 3 13:03:43 2026 +0100  Jonas Finnemann Jensen  [markdown] Require balanced parentheses before bare inline link titles (dart-lang/tools#2768)
  5ebd52bc5  Tue Nov 3 13:03:08 2026 +0100  Jonas Finnemann Jensen  [markdown] Reject unescaped '<' in bracketed inline link destinations (dart-lang/tools#2767)
  feb7ea928  Tue Nov 3 13:02:15 2026 +0100  Jonas Finnemann Jensen  [markdown] Fix 999-character limit in LinkParser.parseLabel (dart-lang/tools#2766)
  31888a5da  Tue Nov 3 13:01:43 2026 +0100  Jonas Finnemann Jensen  [markdown] Enforce 999-character limit in _parseReferenceLinkLabel (dart-lang/tools#2765)
  e016c5d70  Tue Nov 3 09:26:32 2026 +0100  dart-ecosystem-bot[bot]  [boring] Pin the prebuilt binaries of boring-binaries-20261101-f869fdca423c (dart-lang/tools#2778)
  8c7935573  Mon Nov 2 10:15:24 2026 -0800  Kevin Moore  [html] Move WPT selector fixtures to third_party/wpt-selectors (dart-lang/tools#2772)

web (https://github.com/dart-lang/web/compare/45166fd..f388bf5):
  f388bf5  Sun Nov 1 06:57:22 2026 +0000  dependabot[bot]  Bump the github-actions group with 4 updates (dart-lang/web#611)
  658ce2f  Sat Oct 31 12:47:20 2026 +0100  Moritz  Migrate to ecosystem health publish check and setup-dart publish workflow (dart-lang/web#610)

Change-Id: Ifcae02c4712b4b27a5a8ab1c57d8dcf13a6700cf
Reviewed-on: https://dart-review.googlesource.com/c/sdk/+/574281
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

Reviewers

@sigurdm sigurdm sigurdm approved these changes
+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.

2 participants

@jonasfj @sigurdm