Rust in Everything
基于 pulldown-cmark 0.13.5

链接与图片

主线位置：行内主线第一趟。handle_inline_pass1 遇到 [、![ 就压进 LinkStack，遇到 ] 就弹出栈顶，依次试内联链接 (...)、完整引用 [label]、折叠引用 []、快捷引用；引用类的去第一遍收好的 refdefs 里查，查不到再问 BrokenLinkCallback。例子文档里的 [CommonMark 规范][spec] 就在这里变成 Link { link_type: Reference, .. }。

flowchart TB
  open["左方括号"] --> push["压进 LinkStack"]
  close["右方括号"] --> pop["弹出栈顶"]
  pop --> dis{"已被禁用"}
  dis -->|是| txt["留作文本"]
  dis -->|否| inl{"后面是圆括号"}
  inl -->|是| mk["Link 或 Image"]
  inl -->|否| ref{"引用 折叠 快捷"}
  ref --> look["查 refdefs"]
  look -->|找到| mk
  look -->|没找到| cb["BrokenLinkCallback"]
  cb -->|给了地址| mk
  cb -->|None| txt
  mk --> off["禁用外层链接"]

实验平台同按需解析：inline-probe（带计数器的本地拷贝）打印事件；inline-run135 / inline-run134 用 crates.io 上的原版做分配计数和版本对照；inline-cmp 把同一份输入交给 pulldown-cmark 0.13.5、comrak 0.59、markdown-rs 1.0（默认设置）。

链接栈

第一遍把 [ 记成 MaybeLinkOpen，![ 记成 MaybeImage，] 记成 MaybeLinkClose(true)。第一趟走到它们时（handle_inline_pass1 的 MaybeLinkOpen 一支从第 603 行起），先把节点改成 Text，再把下标压进 LinkStack。先改成文本是为了省事：配不上时什么都不用再做，[ 本来就是文本；配上了再把开括号节点改写成 Link 或 Image。

] 弹出栈顶，对应规范附录里的「look for link or image」：「Starting at the top of the delimiter stack, we look backwards through the stack for an opening [ or ![ delimiter」。然后：

  • 栈顶是 Disabled（规范叫 inactive）：留作文本。CommonMark 规定链接不能嵌套链接，一个链接成立之后，LinkStack::disable_all_links 把栈里所有类型为 Link 的开括号改成 Disabled，Image 不动。它记着 disabled_ix，下一次只改新压进来的部分，整条链上的禁用总共是线性的。
  • 否则依次试内联、完整引用、折叠、快捷，任何一种成立就改写节点：开括号节点变成 Link(LinkIndex) 或 Image(LinkIndex)，child 指向括号里的第一个节点，next 跳到整个链接之后；地址、标题、标签存进 Allocations 的 links 表，节点只存下标。规范的算法在这一步还要对链接里的内容跑一遍强调处理；pulldown-cmark 推迟到 next 走进链接时再做（按需解析的动脑筋）。

里层的链接先闭合，所以里层赢：

0..17 Start(Paragraph)
0..1 Text(Borrowed("["))
1..3 Text(Borrowed("a "))
3..10 Start(Link { link_type: Inline, dest_url: Borrowed("/u"), title: Borrowed(""), id: Borrowed("") })
4..5 Text(Borrowed("b"))
3..10 End(Link)
10..12 Text(Borrowed(" c"))
12..13 Text(Borrowed("]"))
13..17 Text(Borrowed("(/v)"))
0..17 End(Paragraph)

这是 [a [b](/u) c](/v)。换成 ![a [b](/u) c](/v)，外层是图片，不会被禁用，得到一个 Image 包着一个 Link。

四种写法

[a](/u "t") [b][R] [r][] [r]

[r]: /x

0..11 Start(Link { link_type: Inline, dest_url: Borrowed("/u"), title: Boxed("t"), id: Borrowed("") })
12..18 Start(Link { link_type: Reference, dest_url: Borrowed("/x"), title: Borrowed(""), id: Borrowed("R") })
19..22 Start(Link { link_type: Collapsed, dest_url: Borrowed("/x"), title: Borrowed(""), id: Borrowed("r") })
25..28 Start(Link { link_type: Shortcut, dest_url: Borrowed("/x"), title: Borrowed(""), id: Borrowed("r") })

（只留 Start(Link)。）id 是使用处写的标签原文，不是规范化之后的，[b][R] 的 id 是 R。

内联：地址、标题和括号上限

scan_inline_link 从 ] 后面一个字节开始，要求是 (，然后：空白（最多跨一个换行，换行后跳过容器前缀，比如引用块的 > ），地址，空白，可选的标题，空白，)。地址由 scan_link_dest 扫：<...> 形式里可以有空格，裸地址遇到空白或控制字符就停，圆括号必须配平。配平要计数，计数就有上限：

// Allowing arbitrary depth nested parentheses inside link destinations
// can create denial of service vulnerabilities if we're not careful.
// The simplest countermeasure is to limit their depth, which is
// explicitly allowed by the spec as long as the limit is at least 3:
// https://spec.commonmark.org/0.29/#link-destination
pub(crate) const LINK_MAX_NESTED_PARENS: usize = 32;

（LINK_MAX_NESTED_PARENS，2019 年的 cbd3b73「Guard against unbounded paren nesting inside links」加入，#237，首次发布于 0.4.1；链接定义从 8d598a8 起用同一个上限。）scan_link_dest 里的判断是 if nest > max_next { return None; }，写在 nest += 1 之前，所以实际允许的层数比常量多一层。[a]( 加 n 个 (、n 个 ) 再加 )，三个库对比（inline-cmp parens n，每行截断）：

== parens 32
pulldown: <p><a href="((((((((
comrak:   <p><a href="((((((((
mdrs:     <p><a href="((((((((
== parens 33
pulldown: <p><a href="((((((((
comrak:   <p>[a]((((((((((((((
mdrs:     <p>[a]((((((((((((((
== parens 34
pulldown: <p>[a]((((((((((((((
comrak:   <p>[a]((((((((((((((
mdrs:     <p>[a]((((((((((((((

规范只要求「at least three levels」，33 层不违反规范，只是和常量名差一。

地址交给 unescape 去掉反斜杠转义、解出实体，有改动时分配。标题由 scan_link_title 扫，mark == 1 那一行让借用的分支永远走不到，CowStr 一页讲过原因。这里用计数分配器把第二遍的分配单独数出来（inline-run135 alloc，Parser::new 之后才开始计数）：

"[a](/u)\n": second-pass allocs=1 bytes=64
    title = Borrowed("")
"[a](/u \"\")\n": second-pass allocs=1 bytes=64
    title = Boxed("")
"[a](/u \"t\")\n": second-pass allocs=3 bytes=73
    title = Boxed("t")
"[a](/u \"a longer title here\")\n": second-pass allocs=2 bytes=83
    title = Boxed("a longer title here")
"[a][r]\n\n[r]: /u \"t\"\n": second-pass allocs=1 bytes=64
    title = Borrowed("t")
...

每个链接例子都有的那 1 次 64 字节和标题无关，没有标题的 [a](/u)、引用链接 [a][r] 也有。去掉它，结论比「总是分配」更细一点：

  • 内联链接的标题总是 Boxed；非空时分配 1 到 2 次（String 第一次 push_str，into_boxed_str 容量不等于长度时再缩一次，"t" 就是 8 字节缩成 1 字节）。
  • 空标题 "" 也是 Boxed("")，但空的 String 和空的 Box<str> 都不分配。
  • 引用链接的标题来自 refdefs，是 Borrowed；没有标题是 Borrowed("")。

这一行 if mark == 1 从 2019 年 acb5fb6「Get rid of InlineScanner and unescape for link title scanning」（#279，首次发布于 0.5.1）把标题扫描改成按绝对下标工作时就是这样，到 main 也没有变。

引用：完整、折叠、快捷

内联不成立时，scan_reference 看 ] 后面：紧跟 [] 是折叠引用，紧跟 [label] 是完整引用，都不是就当快捷引用，标签取两个方括号之间的原文。完整引用的第二个 ] 在扫描时被改成 MaybeLinkClose(false)：

                                    self.tree[reference_close_node].item.body =
                                        ItemBody::MaybeLinkClose(false);

注释说这样做是为了「we won't call the broken link callback twice on one reference」：[foo][bar] 查不到 bar 时，第二个 ] 走到时还会再弹一次栈，false 让它不再被当成快捷引用 [bar] 去查一遍。

标签：在使用的一侧

使用处的标签和定义处的标签走同一个函数 scan_link_label_rest：连续空白（含至多一个换行）折成一个空格，去掉首尾空白，没有改动时借用原文；大小写交给 UniCase。定义一侧的折叠规则和实测见表格与脚注，这里只补一个上限。规范说「A link label can have at most 999 characters inside the square brackets」，代码里的计数器是这样加的：

            b => {
                only_white_space = false;
                ix += 1;
                if b & 0b1000_0000 != 0 {
                    codepoints += 1;
                }
            }

b & 0b1000_0000 != 0 对 UTF-8 的每个非 ASCII 字节都成立，包括后续字节；ASCII 字母一个都不计。结果是中文按字节算、英文不限长。定义和使用都写同一个标签 n 个字符，三个库对比（inline-cmp ascii_label n / cjk_label n，每行截断）：

== ascii_label 999
pulldown: <p><a href="/u">aaaaaaaaaaaaaa
comrak:   <p><a href="/u">aaaaaaaaaaaaaa
mdrs:     <p><a href="/u">aaaaaaaaaaaaaa
== ascii_label 1000
pulldown: <p><a href="/u">aaaaaaaaaaaaaa
comrak:   <p><a href="/u">aaaaaaaaaaaaaa
mdrs:     <p>[aaaaaaaaaaaaaaaaaaaaaaaaaa
== ascii_label 1001
pulldown: <p><a href="/u">aaaaaaaaaaaaaa
comrak:   <p>[aaaaaaaaaaaaaaaaaaaaaaaaaa
mdrs:     <p>[aaaaaaaaaaaaaaaaaaaaaaaaaa
== ascii_label 100000
pulldown: <p><a href="/u">aaaaaaaaaaaaaa
comrak:   <p>[aaaaaaaaaaaaaaaaaaaaaaaaaa
mdrs:     <p>[aaaaaaaaaaaaaaaaaaaaaaaaaa
== cjk_label 333
pulldown: <p><a href="/u">中中中中
comrak:   <p><a href="/u">中中中中
mdrs:     <p><a href="/u">中中中中
== cjk_label 334
pulldown: <p>[中中中中中中中中中中中中中中中中
comrak:   <p>[中中中中中中中中中中中中中中中中
mdrs:     <p>[中中中中中中中中中中中中中中中中

10 万个 ASCII 字母的标签在 pulldown-cmark 里仍然是链接；中文标签 334 个字（1002 字节）就不是了，这一点三个库一致，都按字节算。这个计数写法来自 2019 年的 fb7f57f「Only accept ascii whitespace in link labels as per spec」（首次发布于 0.5.2），之前的版本按 char 逐个计数；main 上的 linklabel.rs 这几行没有改。扫描本身是线性的，没有上限也不会变成平方，影响的只是「什么算链接」。

查定义与 BrokenLinkCallback

引用类的链接都经过 fetch_link_type_url_title：

        if self.link_ref_expansion_limit == 0 {
            return None;
        }

        let (link_type, url, title) = self
            .allocs
            .refdefs
            .get(link_label.as_ref())
            .map(|matching_def| {
                // found a matching definition!
                let title = matching_def
                    .title
                    .as_ref()
                    .cloned()
                    .unwrap_or_else(|| "".into());
                let url = matching_def.dest.clone();
                (link_type, url, title)
            })
            .or_else(|| {
                match self.broken_link_callback.as_mut() {
                    Some(callback) => {
                        // Construct a BrokenLink struct, which will be passed to the callback
                        let broken_link = BrokenLink {
                            span,
                            link_type,
                            reference: link_label,
                        };

                        callback
                            .handle_broken_link(broken_link)
                            .map(|(url, title)| (link_type.to_unknown(), url, title))
                    }
                    None => None,
                }
            })?;

        // Limit expansion from link references.
        // ...
        self.link_ref_expansion_limit = self
            .link_ref_expansion_limit
            .saturating_sub(url.len() + title.len());
  • 找到定义就 clone 地址和标题。refdefs 里大多是 Borrowed，克隆不分配。
  • 找不到就构造 BrokenLink（源码范围、链接类型、标签原文）交给回调。回调返回 Some((url, title)) 时链接成立，类型换成 ...Unknown（LinkType::to_unknown），消费方能分辨这个地址是回调给的；返回 None 时方括号留作文本。
  • 回调通过 Parser::new_with_broken_link_callback 传入，类型参数 F: BrokenLinkCallback<'input>；BrokenLinkCallback 对所有 FnMut(BrokenLink<'input>) -> Option<(CowStr<'input>, CowStr<'input>)> 自动实现，默认的 DefaultBrokenLinkCallback 永远返回 None。

一个把所有未定义的引用指向 /wiki/<小写标签>、但对 baz 返回 None 的回调（inline-run135 broken，输入是 [Foo] [bar][Missing Label] [baz][] [x](/u) [[w]]，没开 wikilink）：

callback: 0..5 Shortcut Borrowed("Foo")
callback: 6..26 Reference Borrowed("Missing Label")
callback: 27..32 Collapsed Borrowed("baz")
callback: 44..47 Shortcut Borrowed("w")
link: ShortcutUnknown Boxed("/wiki/foo") id=Borrowed("Foo")
link: ReferenceUnknown Boxed("/wiki/missing label") id=Borrowed("Missing Label")
link: Inline Borrowed("/u") id=Borrowed("")
link: ShortcutUnknown Boxed("/wiki/w") id=Borrowed("w")

每个引用只问一次；内联链接 [x](/u) 不问；没开 wikilink 时 [[w]] 里的 [w] 是一个快捷引用，回调照样会被问到。回调在 next 里同步执行，走到哪个块才问哪个块里的引用；消费方提前停下，后面的引用就不会被问到。

❗IMPORTANT
动脑筋：下面这份 4208 字节的文档里有几个链接？

第一行是一个链接定义，地址是 / 加 199 个 u（200 字节）；空一行后是一个段落，[x] 重复 1000 次。没有开任何选项。答案在文末。

link_ref_expansion_limit 在构造 Parser 时设为 text.len().max(100_000)，每次查到定义就减去地址和标题的长度，减到 0 之后 fetch_link_type_url_title 直接返回 None，连回调都不调。

📝NOTE
冷知识：引用链接的展开有预算

预算是 2024 年的 d30d4ef「Limit link def expansion」加的，提交说明只有一行「Fixes #844」。这个提交同时在 Parser 结构体上加了注释，举的例子是一个很长的地址定义一次、引用很多次，输出的 HTML 里每个 <a href> 都带一份完整地址：「This is quadratic growth, because it's filling in the area of a square. To prevent this, track how much it's expanded and limit it.」之前展开量没有限制。同一个 PR 里的 6a37830「Check link expansions against the limit before cloning anything」把检查挪到克隆之前，就是上面函数开头那个 == 0 的判断。两个提交都在 #845，首次发布于 0.10.2。

预算按输入长度给，至少 100 000 字节：正常文档的总展开量不会超过它本身的长度太多，超出部分才被截断。脚注不受限，源码注释的解释是「multiple references to the same one reuse the same node」。

脚注引用

开了 ENABLE_FOOTNOTES 时，scan_link_label 看到 [^ 就按脚注标签扫，得到 ReferenceLabel::Footnote。] 闭合时如果标签是脚注，节点变成 FootnoteReference(CowIndex)，产出 Event::FootnoteReference。GFM 风格的脚注（默认）要求定义存在，否则留作文本；旧风格（ENABLE_OLD_FOOTNOTES）不查。![^1] 里的 ! 不属于脚注，开括号节点被改成 SynthesizeChar('!')。脚注定义的两种风格见表格与脚注。

0.13.5 摘进来的 #1136 修的是脚注的块一侧：段落里每一行开头的 [^ 都要试一下是不是脚注定义（能不能打断段落），0.13.4 的这个探测对剩余的整个输入做 UTF-8 校验，「making UTF-8 validation O(n) per line and O(n^2) overall」。改法是把 &[u8] 参数换成 &str，直接用文档本身。[^x]\n 重复 n 行、开 ENABLE_FOOTNOTES，原版 crate 各 3 次取最小：

== 0.13.4
footdef n=   2000 bytes=   10000 events=   8001 min_ms=     0.579
footdef n=   8000 bytes=   40000 events=  32001 min_ms=     5.975
footdef n=  32000 bytes=  160000 events= 128001 min_ms=    82.495
footdef n=  64000 bytes=  320000 events= 256001 min_ms=   330.577
== 0.13.5
footdef n=   2000 bytes=   10000 events=   8001 min_ms=     0.244
footdef n=   8000 bytes=   40000 events=  32001 min_ms=     0.928
footdef n=  32000 bytes=  160000 events= 128001 min_ms=     3.641
footdef n=  64000 bytes=  320000 events= 256001 min_ms=     7.788

开了 ENABLE_WIKILINKS 时，[[ 除了照常压 link_stack，还压一份进 wikilink_stack；]] 先交给 handle_wikilink。两个方括号之间的原文就是地址，有 | 时前半是地址、后半是显示文本（has_pothole: true）。wikilink 优先于引用链接和内联链接（specs/wikilinks.txt），成立后同样禁用外层的普通链接：

0..7 Start(Link { link_type: WikiLink { has_pothole: false }, dest_url: Borrowed("foo"), title: Borrowed(""), id: Borrowed("") })
2..5 Text(Borrowed("foo"))
0..7 End(Link)
7..8 Text(Borrowed(" "))
8..19 Start(Link { link_type: WikiLink { has_pothole: true }, dest_url: Borrowed("bar"), title: Borrowed(""), id: Borrowed("") })
14..17 Text(Borrowed("baz"))
8..19 End(Link)
19..20 Text(Borrowed(" "))
20..32 Start(Image { link_type: WikiLink { has_pothole: false }, dest_url: Borrowed("img.png"), title: Borrowed(""), id: Borrowed("") })
23..30 Text(Borrowed("img.png"))
20..32 End(Image)

（[[foo]] [[bar|baz]] ![[img.png]]，略去段落事件。）没有 | 的 wikilink 要新建一个文本节点当孩子（create_node），这是第二遍少数几处追加节点的地方之一。

0.13.5 的 8 个摘取里有两个落在这个函数上。#1102「Fix: wikilink with pipe separator leaks child node's next chain into sibling content」：带 | 的 wikilink 复用原有节点当孩子，却没有截断那个节点的 next，链一直接到 ]] 之后的内容，next 走树时同一段内容既当孩子又当兄弟被访问一遍。PR 里加的测试 wikilink_no_event_blowup 的注释说「Adversarial repeated [[|]] patterns compounded exponentially」。用那个测试的输入重复 n 行，数事件个数：

== 0.13.4
wikiblowup n=  1 bytes=   22 events=       30 ms=    0.017
wikiblowup n=  2 bytes=   44 events=       88 ms=    0.004
wikiblowup n=  4 bytes=   88 events=      436 ms=    0.008
wikiblowup n=  8 bytes=  176 events=     7396 ms=    0.061
wikiblowup n= 16 bytes=  352 events=  1900516 ms=   14.464
== 0.13.5
wikiblowup n=  1 bytes=   22 events=       18 ms=    0.019
wikiblowup n=  2 bytes=   44 events=       35 ms=    0.004
wikiblowup n=  4 bytes=   88 events=       69 ms=    0.002
wikiblowup n=  8 bytes=  176 events=      137 ms=    0.006
wikiblowup n= 16 bytes=  352 events=      273 ms=    0.012

352 字节在 0.13.4 上产出 190 万个事件，0.13.5 上是 273 个，事件数和输入成正比。#1111「Fix subtract-overflow panic in handle_wikilink on malformed input」修的是另一种畸形输入：链接体的起点落在闭合 ]] 之后，end_ix - start_ix 下溢。现在函数开头先判断 if end_ix <= start_ix { return None; }。回归用例（specs/regression.txt 里的 issue 1108）是 ![[] ]()]]，在 0.13.4 的 release 构建上：

thread 'main' (7476249) panicked at .../pulldown-cmark-0.13.4/src/parse.rs:911:47:
byte range starts at 9 but ends at 8

release 构建关了溢出检查，减法本身不报错，崩在随后的切片上；0.13.5 正常产出 9 个事件。

动脑筋答案

500 个。inline-probe events 的输出里数 Start(Link：

$ grep -c 'Start(Link' expansion.events.txt
500

最后一个链接和它后面的事件：

2203..2206 Start(Link { link_type: Shortcut, dest_url: Borrowed("/uuuuuuuuuuuuuu...
2204..2205 Text(Borrowed("x"))
2203..2206 End(Link)
2206..2207 Text(Borrowed(" "))
2207..2208 Text(Borrowed("["))
2208..2209 Text(Borrowed("x"))
2209..2210 Text(Borrowed("]"))

文档只有 4208 字节，预算取下限 100 000；每次展开扣 200（地址 200 字节，标题为空），500 次正好扣完。第 501 个 [x] 起，fetch_link_type_url_title 一进来就返回 None，方括号退成文本，没有任何警告，也不会调用 BrokenLinkCallback。

小结

  • [、![ 压进 LinkStack，] 弹出栈顶；链接成立后外层的普通链接全部禁用，图片不禁用，所以里层链接赢、图片里可以有链接。
  • 依次试内联、完整引用、折叠、快捷；id 是使用处的标签原文，MaybeLinkClose(false) 保证一个引用只查一次。
  • 三个上限：括号嵌套常量 32 实际放行 33 层；标签的 999 字符只按非 ASCII 字节计，ASCII 标签不限长；引用展开预算是输入长度和 100 000 取大，用完后的引用静默变成文本。
  • 内联链接的标题总是 Boxed，非空才分配；引用链接的标题借用 refdefs。
  • 查不到定义时 BrokenLinkCallback 每个引用只被问一次，给出的链接类型带 Unknown。
  • 0.13.5 摘进来的 #1136 让每行一个 [^ 的脚注探测变回线性，#1102 和 #1111 修了 wikilink 的事件爆炸和 panic。

💬 关联讨论

发起讨论
加载中...