Rust in Everything
基于 pulldown-cmark 0.13.5

代码段、HTML、实体

主线位置：行内主线第一趟的前半，加上第一遍顺手做掉的两件事。代码段、行内 HTML、自动链接在 CommonMark 里优先级最高，handle_inline_pass1 按出现顺序处理 MaybeCode 和 MaybeHtml；实体和反斜杠转义不需要配对，第一遍的 parse_line 当场就解决了。例子文档列表项里的 `Parser::next` 和引用块里的 & 分别走这两条路。

flowchart TB
  pl["parse_line"] --> ent["实体 SynthesizeText"]
  pl --> esc["转义 切开 Text"]
  pl --> mc["MaybeCode"]
  pl --> mh["MaybeHtml"]
  mc --> cd["往后找同长度 或查 CodeDelims"]
  cd --> code["Code"]
  mh --> al{"自动链接"}
  al -->|是| link["Link 加新文本节点"]
  al -->|否| ih{"HTML 标签"}
  ih -->|是| html["InlineHtml"]
  ih -->|否| txt["Text"]
  cd -->|没找到| txt

实验平台同按需解析。inline-probe 的本地拷贝里另有一个开关 NAIVE_CODE：打开后 CodeDelims 永远当作空的，HtmlScanGuard 在每次扫描前清零，用来和原样的代码对照。

代码段

第一遍把一串反引号记成一个 MaybeCode(n, false)，n 是反引号个数；反斜杠后面的反引号记成 MaybeCode(n, true)，节点从反斜杠之后开始。第一趟（handle_inline_pass1 第 551 行起）遇到它：

  • 前面有反斜杠时，第一个反引号被转义掉，要找的长度减一；减到 0 就是一个字面的 `。
  • 否则沿 next 往后找第一个长度正好相等的 MaybeCode，找到就 make_code_span，找不到就把开头这串退成文本。

「往后找」是平方复杂度的来源：如果每个开头都配不上，每个都要走到链尾。CodeDelims 的注释说它「should prevent quadratic scanning behaviours by providing (amortized) constant time lookups」：

struct CodeDelims {
    inner: HashMap<usize, VecDeque<TreeIndex>>,
    seen_first: bool,
}

一次没找到配对的扫描会走到链尾，路上把遇到的每个长度不同的 MaybeCode 按长度记进 inner，值是节点下标组成的队列，按出现顺序排好。之后的开头不再走链，直接查表：

    fn find(&mut self, open_ix: TreeIndex, count: usize) -> Option<TreeIndex> {
        while let Some(ix) = self.inner.get_mut(&count)?.pop_front() {
            if ix > open_ix {
                return Some(ix);
            }
        }
        None
    }

记下标而不是只记「有没有这个长度」，是因为配对要求闭的一方在开的一方之后：队列头上那些在 open_ix 之前的位置已经被用过或者被跳过了，弹掉就是，每个位置最多被弹一次，整条链摊下来是线性的。seen_first 跳过第一次插入，注释说「that delimiter will always be an opener and not a closer」：这次扫描失败后，链上的下一个 MaybeCode 正是它，它会作为开头被处理。一旦配上，code_delims.clear()，下一个开头重新走链。

把表关掉对照（inline-probe patho code，各 3 次取最小）。输入是长度 1 到 500 的反引号串各一个（都配不上），后面跟 n 个 [，让每次「往后找」都要走过 n 个节点：

code pcm   n=  10000 bytes=  135750 events=  11002 min_ms=     0.276 find_match_scanned=0 code_scan_steps=10999 math_scan_steps=0
code naive n=  10000 bytes=  135750 events=  11002 min_ms=    16.487 find_match_scanned=0 code_scan_steps=5250000 math_scan_steps=0
code pcm   n=  20000 bytes=  145750 events=  21002 min_ms=     0.443 find_match_scanned=0 code_scan_steps=20999 math_scan_steps=0
code naive n=  20000 bytes=  145750 events=  21002 min_ms=    29.507 find_match_scanned=0 code_scan_steps=10250000 math_scan_steps=0
code pcm   n=  40000 bytes=  165750 events=  41002 min_ms=     0.814 find_match_scanned=0 code_scan_steps=40999 math_scan_steps=0
code naive n=  40000 bytes=  165750 events=  41002 min_ms=    48.233 find_match_scanned=0 code_scan_steps=20250000 math_scan_steps=0
code pcm   n=  80000 bytes=  205750 events=  81002 min_ms=     1.679 find_match_scanned=0 code_scan_steps=80999 math_scan_steps=0
code naive n=  80000 bytes=  205750 events=  81002 min_ms=    85.367 find_match_scanned=0 code_scan_steps=40250000 math_scan_steps=0

有表时走链的步数等于节点数，只有第一次扫描真的走了；没有表时是 500 × n。这里的增长是「不同长度的个数 × 链长」，不是 n²：要有 k 个互不相同、都配不上的长度，反引号本身就要 k²/2 个字节。按长度做键，本身就让这类输入很难造大（数学与智能标点的冷知识里，上游也说过这一点）。

📝NOTE
冷知识：这张表为什么挂在 Parser 上

code_delims 和 math_delims 是 Parser 的字段，每个块用完 clear()，不重建。2024 年的 914120c「Reuse a couple hash maps across blocks」（#951，首次发布于 0.12.2）之前，它们是每次进行内解析时新建的。提交说明：「I implemented this change after seeing the RandomState in a flame graph. According to criterion, this seems to make tiny test cases about 2% worse, but makes lorem1.md 85% better.」改之前每次 handle_inline_pass1 开头 CodeDelims::new()、MathDelims::new()，各建一个 HashMap，也就各构造一个 RandomState；块多的文档里这笔开销就显出来了。改之后两张表随 Parser 建一次，clear() 还留着容量。

make_code_span 按规范「Code spans」一节处理内容：行尾换成空格（换行后的容器前缀先跳过），首尾各有一个空格且内容不全是空格时各去掉一个；在表格里把 \| 还原成 |。只有跨行或者表格里有 \| 时才要新建 String，其余情况内容就是原文的切片。

0..9 Code(Borrowed("a`b"))
9..11 Text(Borrowed("  "))
11..16 Code(Borrowed("x"))
16..17 Text(Borrowed(" "))
17..21 Code(Borrowed("  "))

（输入是 `` a`b `` 加两个空格、` x `、空格、` `，节选。）两个反引号包着的代码可以含一个反引号；` x ` 去掉了两边的空格；全是空格的不去。`a↵b` 得到 Code(Boxed("a b"))，引用块里跨行的代码段跳过下一行的 > 之后同样是 Boxed("a b")。

❗IMPORTANT
动脑筋：`x\`y` 输出什么？

一个反引号开头，中间有一个反斜杠加反引号，再一个反引号结尾。按 Markdown 的习惯，\` 是转义的反引号；这里是吗？答案在文末。

行内 HTML 与自动链接

第一遍把每个 <（后面不是 \）记成 MaybeHtml。第一趟里它的处理顺序是（第 408 行起）：

  1. 先试自动链接 scan_autolink：URI 形式要求协议名以字母开头、总长 2 到 32 个字符，后面跟 :，再到 > 之间不能有空白和 <；不是 URI 再试邮箱。成立时 MaybeHtml 改成 Link，create_node 新建一个文本节点当孩子（这是第二遍少数几处追加节点的地方之一）。
  2. 再试 HTML（scan_inline_html）：<! 开头的是注释、CDATA 或声明，<? 开头的是处理指令，其余按标签扫（开标签、闭标签、属性）。成立时变成 InlineHtml，范围覆盖整个标签。
  3. 都不是，退成文本。
0..25 Start(Link { link_type: Autolink, dest_url: Borrowed("https://example.com/a?b"), title: Borrowed(""), id: Borrowed("") })
1..24 Text(Borrowed("https://example.com/a?b"))
0..25 End(Link)
25..26 Text(Borrowed(" "))
26..43 Start(Link { link_type: Email, dest_url: Borrowed("foo@bar.example"), title: Borrowed(""), id: Borrowed("") })
27..42 Text(Borrowed("foo@bar.example"))
26..43 End(Link)
43..44 Text(Borrowed(" "))
44..50 Start(Link { link_type: Autolink, dest_url: Borrowed("ab:c"), title: Borrowed(""), id: Borrowed("") })
45..49 Text(Borrowed("ab:c"))
44..50 End(Link)
50..51 Text(Borrowed(" "))
51..52 Text(Borrowed("<"))
52..70 Text(Borrowed("a:b> https://x.com"))

（<https://example.com/a?b> <foo@bar.example> <ab:c> <a:b> https://x.com。）<ab:c> 是合法的自动链接，<a:b> 的协议名只有一个字符，不是；裸的 https://x.com 不会变成链接，pulldown-cmark 没有 GFM 的扩展自动链接（开 ENABLE_GFM 也没有，见容器块）。

HTML 标签可以跨行。引用块里的 > <a 和 > b="c"> 两行，扫描时用 skip_container_prefixes 跳过第二行的 > ，得到的文本不再是原文的连续切片，只能拼出来：InlineHtml(Boxed("<a\nb=\"c\">"))，树里是 OwnedInlineHtml(CowIndex)。不跨容器行的标签是 InlineHtml，直接借原文。行内 HTML 原样进事件、原样写出，pulldown-cmark 不做任何过滤（转义）。

注释、CDATA、声明、处理指令的结尾标记可能很远，也可能根本没有。HtmlScanGuard 有四个字段 cdata、processing、declaration、comment，记着上一次这一类扫描失败时扫到了哪里。scan_inline_html_comment 的注释分支：

        b'-' if ix > scan_guard.comment => {
            // ...
            while let Some(x) = memchr(b'-', &bytes[ix..]) {
                ix += x + 1;
                scan_guard.comment = ix;
                if bytes.get(ix) == Some(&b'-') && bytes.get(ix + 1) == Some(&b'>') {
                    return Some(ix + 2);
                }
            }
            None
        }

起点不超过 scan_guard.comment 的 <!-- 直接判失败：后面已经扫过、确定没有 -->。守卫是 2019 年的 c5a37b9「Guard against pathological inline html」加的（首次发布于 0.5.1）。一个段落里 <!-- a 重复 n 次，没有一个闭合（inline-probe patho html_comment，各 3 次取最小）：

html_comment pcm   n=   5000 bytes=   35002 events=  10003 min_ms=     0.239 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment naive n=   5000 bytes=   35002 events=  10003 min_ms=   174.068 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment pcm   n=  10000 bytes=   70002 events=  20003 min_ms=     0.465 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment naive n=  10000 bytes=   70002 events=  20003 min_ms=   700.853 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment pcm   n=  20000 bytes=  140002 events=  40003 min_ms=     1.027 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment naive n=  20000 bytes=  140002 events=  40003 min_ms=  2818.586 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment pcm   n=  40000 bytes=  280002 events=  80003 min_ms=     1.937 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0
html_comment naive n=  40000 bytes=  280002 events=  80003 min_ms= 11424.230 find_match_scanned=0 code_scan_steps=0 math_scan_steps=0

280 KB 的输入，有守卫 1.9 毫秒，每次清零 11.4 秒。守卫存在 Parser 上，整份文档共用，不随块清零：位置是全文的字节下标，前面的块扫过的地方，后面的块不会再回头。

实体

& 在第一遍就交给 scan_entity：

  • &# 加 1 到 7 位十进制，或 &#x 加 1 到 6 位十六进制，再加 ;。码点是 0 或不是合法的 Unicode 标量值时换成 U+FFFD。结果是一个字符，装进 CowStr::Inlined，不分配。
  • 否则取 & 之后连续的 ASCII 字母数字，要求紧跟 ;，再去表里查名字。

表在 entities.rs，tools/mk_entities.py 从 HTML5 的实体 JSON 生成，只收以 ; 结尾的名字，排好序写成一个常量数组：

const ENTITIES: [(&[u8], &str); 2125] = [
    (b"AElig", "\u{00C6}"),
    (b"AMP", "\u{0026}"),
    // ...
];

pub(crate) fn get_entity(bytes: &[u8]) -> Option<&'static str> {
    ENTITIES
        .binary_search_by_key(&bytes, |&(key, _value)| key)
        .ok()
        .map(|i| ENTITIES[i].1)
}

（get_entity。）按字节序二分，2125 项最多比较 12 次；大小写敏感，AMP 和 amp 是两项。最长的名字 CounterClockwiseContourIntegral 31 个字节，有 93 个实体展开成两个码点。查到的值是 &'static str，CowStr::Borrowed 借的是这张表，所以命名实体也不分配。第一遍把它变成 SynthesizeText(CowIndex)，事件里是一个单独的 Text：

0..5 Text(Borrowed("&"))
5..6 Text(Borrowed(" "))
6..12 Text(Borrowed("©"))
12..13 Text(Borrowed(" "))
13..18 Text(Inlined(InlineStr { inner: [65, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], len: 1 }))
18..19 Text(Borrowed(" "))
19..28 Text(Inlined(InlineStr { inner: [240, 159, 152, 128, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], len: 4 }))
28..29 Text(Borrowed(" "))
29..33 Text(Inlined(InlineStr { inner: [239, 191, 189, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], len: 3 }))
33..34 Text(Borrowed(" "))
34..44 Text(Inlined(InlineStr { inner: [239, 191, 189, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0], len: 3 }))
44..58 Text(Borrowed(" &amp &bogus; "))
58..63 Text(Borrowed("&"))

（&amp; &copy; &#65; &#x1F600; &#0; &#1234567; &amp &bogus; &AMP;，略去段落事件。）&#0; 和超出范围的 &#1234567; 都是 U+FFFD（字节 239 191 189）；没有分号的 &amp 和不认识的 &bogus; 原样是文本。一段文字因为实体被切成几个 Text，是事件模型里说过的现象。代码段和链接地址、标题里的实体另算：代码段里不解，地址和标题由 unescape 解，解了就要分配。

反斜杠转义

反斜杠也在第一遍处理，规则只有一条：后面是 ASCII 标点就转义，否则反斜杠是普通字符。\*a\* \a \\ foo\ 加换行加 bar `x\`y` [a\]b](/c\)d)：

0..42 Start(Paragraph)
1..3 Text(Borrowed("*a"))
4..9 Text(Borrowed("* \\a "))
10..15 Text(Borrowed("\\ foo"))
15..17 HardBreak
17..21 Text(Borrowed("bar "))
21..25 Code(Borrowed("x\\"))
25..26 Text(Borrowed("y"))
26..27 Text(Borrowed("`"))
27..28 Text(Borrowed(" "))
28..41 Start(Link { link_type: Inline, dest_url: Boxed("/c)d"), title: Borrowed(""), id: Borrowed("") })
29..30 Text(Borrowed("a"))
31..33 Text(Borrowed("]b"))
28..41 End(Link)
0..42 End(Paragraph)
  • 转义不复制字符串：parse_line 结束当前文本节点、跳过反斜杠，从下一个字节开始新的 Text，节点标上 backslash_escaped: true。所以 \*a\* 变成 *a 和 * \a 两段，都借原文。被转义的 * 不会成为 MaybeEmphasis，\] 也不会成为 MaybeLinkClose，转义在第一遍就把占位挡住了。
  • \a 不是转义，原样保留；\\ 是一个字面的反斜杠。
  • 行尾的 \ 是硬换行 HardBreak。
  • 链接地址里的 \) 在第一遍还是原文，扫地址时由 unescape 去掉，地址变成 Boxed("/c)d")。

动脑筋答案

<p><code>x\</code>y`</p>。规范「Backslash escapes」一节写明：「Backslash escapes do not work in code spans」。第一遍并不知道哪里是代码段，它照常把 \` 记成「前面有反斜杠」的 MaybeCode(1, true)，反斜杠本身不进任何节点：

== after first pass
Item { start: 0, end: 7, body: Paragraph }
  Item { start: 0, end: 1, body: MaybeCode(1, false) }
  Item { start: 1, end: 2, body: Text { backslash_escaped: false } }
  Item { start: 3, end: 4, body: MaybeCode(1, true) }
  Item { start: 4, end: 5, body: Text { backslash_escaped: false } }
  Item { start: 5, end: 6, body: MaybeCode(1, false) }
== after draining 5 events
Item { start: 0, end: 7, body: Paragraph }
  Item { start: 0, end: 4, body: Code(CowIndex(0)) }
  Item { start: 4, end: 5, body: Text { backslash_escaped: false } }
  Item { start: 5, end: 6, body: Text { backslash_escaped: false } }

第一趟从 0 号开反引号往后找长度为 1 的 MaybeCode，第一个就是 3 号。「前面有反斜杠」只在它自己当开头时才起作用，当闭合时不看。代码内容取原文 text[1..3]，反斜杠就回来了：Code(Borrowed("x\\"))，最后一个反引号没有配对，退成文本。只有在代码段之外，\` 才是转义：单独的 \`x` 得到三个 Text，没有代码段。

小结

  • 代码段：往后找第一个长度相等的反引号串；一次失败的扫描把沿途的串按长度记进 CodeDelims（长度到位置队列），之后查表，失效的位置弹掉，整体线性。关掉这张表，实测走链步数从 n 变成 500 × n。
  • 内容只在跨行或表格 \| 时才复制；首尾空格各去一个；代码段里没有转义。
  • < 先试自动链接（协议名 2 到 32 个字符），再试 HTML；跨容器行的 HTML 拼成 Boxed。HtmlScanGuard 记住失败扫描的终点，280 KB 的未闭合注释有它 1.9 毫秒、没它 11.4 秒。
  • 实体在第一遍查 2125 项的有序表，二分最多 12 次；命名实体借静态表，数字实体内联，都不分配。
  • 反斜杠转义在第一遍切开 Text，挡住后面的占位；地址里的转义由 unescape 处理。

💬 关联讨论

发起讨论
加载中...