Cloudflare的HTML解析历史（下）

小提示：您能找到这篇{Cloudflare的HTML解析历史（下）}绝对不是偶然，我们能帮您找到潜在客户，解决您的困扰。如果您对本页介绍的Cloudflare的HTML解析历史（下）内容感兴趣，有相关需求意向欢迎拨打我们的服务热线，或留言咨询，我们将第一时间联系您！

< ">上文我们引出了一个双解析器架构的思路，下面就让我们详细介绍一下双解析器架构。

< font-size: 16px;">双解析器架构

< font-size: 16px;">大多数开发人员都很熟悉，并且更喜欢将基于CSS选择器的API（例如在Cheerio，jQuery或DOM本身中）来完成HTML的修改任务。我们还决定将我们的API基于CSS选择器，尽管这意味着额外的实现复杂性，但是这个决定为解析优化创造了更多的机会。

< font-size: 16px;">当选择器定义了应重写内容的范围时，我们意识到我们可以跳过不在这个范围内的内容，并且不会为它生成标记。这不仅大大加快了解析本身的速度，而且还避免了与JavaScript VM的来回交互带来的性能负担。

< font-size: 16px;">

< font-size: 16px;">考虑到所需的引流加粉任务，LOL HTML的解析器由两个内部解析器组成：

< font-size: 16px;">1.Lexer—一个常规的完整解析器，它为遇到的所有类型的内容生成输出；

< font-size: 16px;">2.标记扫描器——查找开始和结束标记，跳过对其余内容的解析。标记扫描器只解析标记名并将其提供给选择器匹配器，如果需要匹配或关于标记的附加信息(如属性)，则匹配器将把解析器切换到lexer。

< font-size: 16px;">一旦输入超出所有选择器匹配的范围，解析器就切换回标记扫描器。标记扫描器有时也可能将解析器切换到Lexer，如果它需要用于解析反馈模拟的其他标记信息。

< font-size: 16px;">

< font-size: 16px;">LOL HTML体系结构

< font-size: 16px;">对于同一语法使用两种不同的解析器实现将增加开发成本，并且由于实现的不一致性而容易出错。我们通过实现一个小型的基于Rust宏的DSL来最小化这些风险，该DSL在本质上类似于Ragel，DSL程序描述了不确定的有限自动机状态以及与每个状态转换和匹配的输入字节关联的操作。

< font-size: 16px;">DSL状态定义的示例：

< font-size: 16px;">

tag_name_state {
   whitespace => ( finish_tag_name?; --> before_attribute_name_state )
   b'/'       => ( finish_tag_name?; --> self_closing_start_tag_state )
   b'>'       => ( finish_tag_name?; emit_tag?; --> data_state )
   eof        => ( emit_raw_without_token_and_eof?; )
   _          => ( update_tag_name_hash; )
}

< ">Rust编译器将DSL程序扩展为不那么漂亮，但效率极高的Rust代码。
< font-size: 16px;">

< font-size: 16px;">我们不再需要为每个解析器重新实现驱动解析过程的代码，我们需要做的就是为每个操作定义不同的操作实现。对于标记扫描器来说，大多数操作都是无操作的，因此Rust编译器为我们完成了NFA优化工作：它使用无操作操作优化了状态分支，如果所有分支都有无操作操作，它甚至会优化整个状态。

< font-size: 16px;">字节片处理优化

< font-size: 16px;">Rust具有出色的内存安全机制，但是有时它们太消耗性能。

< font-size: 16px;">解析器的任务是扫描输入内容，并找到 language - tokens 的词汇单位的边界及其内部部分。例如，HTML起始标记令牌由多个部分组成，这意味着标记名称的输入字节切片和代表属性和值的多对输入切片对：

< font-size: 16px;">

struct StartTagToken {
   name: &'i [u8],
&nb电视广告宣传片制作sp;  attributes: Vec,
   self_closing: bool
}

< ">由于Rust在内存访问上使用了绑定检查，因此构造令牌可能是一个相对费时的操作。我们需要能够在不到一秒的时间内构建数千条这样的指令，因此每个CPU指令都非常重要。
< font-size: 16px;">

< font-size: 16px;">遵循高性能低能耗的原则，我们使用令牌的“token outline”表示:我们不使用令牌部分的内存片，而是使用数字范围，在需要时将其延迟转换为字节片。

< font-size: 16px;">

struct StartTagTokenOutline {
   name: Range,
   attributes: Vec,
   self_closing: bool}

< ">你可能已经注意到，通过这种方法，我们不再受限于输入块的运行周期，事实证明这非常有用。如果开始标记分布在多个输入块中，我们可以轻松地更新当前正在构造的令牌，因为只需调整整数索引即可获得新的输入块。这样一来，我们就可以避免使用来自新输入存储区（可能是输入块本身或内部解析器的缓冲区）的切片构造新的令牌。

< font-size: 16px;">这一次我们不能避免输入字符编码的转换，我们公开了可在JavaScript字符串上运行的面向用户的API，输入的HTML可以是任何编码。幸运的是，我们仍然可以在不解码的情况下进行解析，并且只能在请求的令牌范围内进行编码和解码，尽管我们仍然不能对UTF-16进行编码。

< font-size: 16px;">因此，当用户在API中请求元素的标记名称时，在内部仍会在输入的字符编码中将其表示为字节片，但是当提供给用户时，它将被动态解码。当用户设置新标记名称时，将发生相反的过程。

< font-size: 16px;">对于选择器匹配，我们仍然可以在原始编码表示形式上进行操作，这是因为我们提前知道了输入编码，所以我们可以预先将选择器中的值转换为页面的字符编码，这样就可以在不解码每个令牌字段的情况下进行比较。

< font-size: 16px;">正如你所看到的，新的解析器架构以及所有这些优化都产生了非常好的性能结果：

< font-size: 16px;">

< font-size: 16px;">平均解析时间取决于输入大小——越小越好

< font-size: 16px;">LOL HTML的标记扫描器通常是LazyHTML的两倍，而词法分析器具有类似的性能，在较大的输入量上要优于LazyHTML。两者都比html5ever的令牌生成器快几倍，html5ever是Mozilla的Servo浏览器引擎中使用Rust实现的另一个解析器。

< font-size: 16px;">CSS选择器匹配的VM

< font-size: 16px;">有了快速解析器，我们只缺少一件事，即CSS选择器匹配器。最初，我们认为我们可以为此目的使用Servo的CSS选择器匹配引擎。经过几天的测试，结果表明它不太适合我们的任务。

< font-size: 16px;">它不能与我们的双重解析器体系结构一起很好地工作。我们首先需要只匹配标记扫描器中的标记名称，然后，如果失败，则在词法分析器中查询属性。选择器库的设计没有考虑到这种体系结构，因此，如果信息不足，我们需要一些黑客技术来防止匹配。它是低效的，因为我们需要在救助之后重新开始匹配。另外还有其他问题，例如lazy字符解码的集成和使用标记名哈希的标记名比较的集成。

< font-size: 16px;">匹配的方向

< font-size: 16px;">遇到的主要问题是需要回溯所有开放元素以进行匹配，浏览器从右到左匹配选择器，并遍历元素的所有源头。这个StackOverflow很好地解释了为什么要这样做。我们需要存储有关所有打开的元素及其属性的信息。不过在内存紧张的情况下，我们无法做到这一点。在本文的示例中，这种匹配方法效率不高，与浏览器不同，我们希望只有几个选择器和许多元素。在本文的示例中，从左到右，匹配选择器会变得更有效率。

< font-size: 16px;">body > div.foo  img[alt] > div.foo ul

< font-size: 16px;">可以将其拆分为归因于特定元素的各个组件，并使用介于两者之间的分层组合器：

< font-size: 16px;">body > div.foo img[alt] > div.foo  ul

< font-size: 16px;">---    ------- --------   -------  --

< font-size: 16px;">每个组件都很容易匹配开始标记标记，只需将标记字段与组件中的值进行比较即可，让我们想象一下，每一个这样的组成部分都是所有可能组成部分的无限字母表中的一个字符：

< font-size: 16px;">

< font-size: 16px;">将选择器组件替换为虚构字符来重写选择器：

< font-size: 16px;">a > b c > b d

< font-size: 16px;">有一种非常众所周知的抽象来表达这些关系，这就是正则表达式。可以将选择器替换组合器替换为正则表达式语法：

< font-size: 16px;">ab.*cb.*d

< font-size: 16px;">我们将CSS选择器转换为可在开始标记令牌序列上执行的正则表达式，请注意，并非所有CSS选择器都可以转换为这种常规语法，我们匹配的输入有一些细节，稍后我们将讨论这些细节。然而，这是一个很好的起点，它允许我们表达一个选择器的重要子集。

< font-size: 16px;">实现虚拟机

< font-size: 16px;">接下来，我们开始研究正则表达式的非回溯算法，虚拟机方法似乎适合我们的任务要求，因为可能有一个非回溯实现，该实现足够灵活，可以解决字符串上的正则表达式匹配与抽象之间的差异。

< font-size: 16px;">基于VM的正则表达式匹配是许多正则表达式库（例如regexp2和Rust的regex）中的引擎之一，基本思想是，与其为正则表达式构建NFA或DFA，不如通过稍后由虚拟机执行的指令将其转换为DSL汇编语言，正则表达式被视为接受用于匹配的字符串的程序。

< font-size: 16px;">由于VM程序只是具有-transitions的NFA的表示形式，因此它可以在执行期间同时处于多个状态，或者换句话说，产生多个线程。如果一个或多个状态成功，则正则表达式匹配。

< font-size: 16px;">例如，以下VM指令：

< font-size: 16px;">1.expect c：等待下一个输入字符，如果不等于指令的操作数，则中止线程；

< font-size: 16px;">2.jmp L：跳转到标签‘L’；

< font-size: 16px;">3.thread L1, L2：生成标签L1和L2的线程，有效地分割执行；

< font-size: 16px;">4.match：通过匹配成功执行线程；

< font-size: 16px;">例如，使用此指令集，可将正则表达式 “ab*c” 转换为：

< font-size: 16px;">

    expect a
L1: thread L2, L3
L2: expect b
    jmp L1
L3: expect c
    match

< font-size: 16px;">让我们尝试从前面看到的选择器中转换正则表达式ab.*cb.*d：

< font-size: 16px;">

   expect a
    expect b
L1: thread L2, L3
L2: expect [any]
    jmp L1
L3: expect c
    expect b
L4: thread L5, L6
L5: expect [any]
    jmp L4
L6: expect d
    match

< ">看起来很复杂，尽管此汇编语言通常是为正则表达式设计的，但正则表达式可能比我们的情况复杂得多。对我们而言，唯一重要的重复是 “.*”。 因此，与其用多个指令来表达它，不如只使用一个名为hereditary_jmp的指令：
< font-size: 16px;">

< font-size: 16px;">

    expect a
    expect b
    hereditary_jmp L1
L1: expect c
    expect b
    hereditary_jmp L2
L2: expect d
    match

< font-size: 16px;">该指令告诉VM记住指令的标记操作数，并无条件地在每个输入字符上产生一个跳转到该标签的线程。

< font-size: 16px;">正则表达式的字符串输入与提供给VM的输入之间有一个重要的区别，即输入可以缩小!

< font-size: 16px;">常规字符串只是一个连续的字符序列，而我们操作的是一个开放元素序列。随着新标记的到来，这个序列可以扩大也可以收缩。假设我们用虚构的语言将< div >表示为'a'字符，因此输入< div > < div > < div >可以将其表示为aaa，如果输入的下一个标记是，则我们的“字符串”缩小为aa。

< font-size: 16px;">你可能会认为此时我们的抽象无效，我们应该尝试其他方法。不过计算机输入的内容，是一堆开放元素，我们需要一个类似于栈的结构来存储我们的VM迄今为止看到的hereditrary_jmp指令标记。那么，为什么不将其存储在开放元素堆栈中呢？如果将下一条指令指针存储在成功执行了预期指令的每个堆栈项目上，我们将获得VM状态的完整快照，因此如果堆栈缩小，我们可以轻松地回滚到该状态。

< font-size: 16px;">借助此实现，我们无需在堆栈上存储除标记名以外的任何内容，并且考虑到我们可以使用标记名哈希算法，因此每个打开的元素仅是64位整数。作为另一个较小的优化，为避免遍历整个堆栈以在每个新输入上寻找有效的跳跃痕迹，我们要将每个原先的索引与每个堆栈项上的跳跃痕迹一起存储。

< font-size: 16px;">例如，使用以下选择器 “body > div span”，我们将得到以下VM程序（我们去掉了标记，只使用指令索引）：

< font-size: 16px;">0| expect 1| expect 2| hereditary_jmp 3

< font-size: 16px;">3| expect 4| match

< font-size: 16px;">输入“ < body > < di v> < div > < a >”我们将得到以下堆栈：

< font-size: 16px;">

< font-size: 16px;">现在，如果下一个标记是开始标记，则VM将首先尝试从头开始执行选择器程序，并在第一条指令上就失败。但是，它还会寻找堆栈上任何活跃的跳跃痕迹。我们有一个跳转到索引3的指令。跳转到该指令后，VM成功地生成了一个匹配。如果稍后再获得另一个开始标记，则遵循相同的步骤。

< font-size: 16px;">如果我们随后收到一串 “” 结束标记，则我们的堆栈将仅包含一项：

< font-size: 16px;">

< font-size: 16px;">指示VM跳至索引1处的指令，有效回滚以匹配选择器的div组件。

< font-size: 16px;">我们在前面提到过，如果我们只有来自标记扫描程序的标记名称，并且需要通过运行lexer获得更多信息，那么我们可以退出匹配过程。使用VM方法很简单，只需停止当前指令的执行，并在获得所需信息后恢复执行即可。

< font-size: 16px;">选择器的匹配

< font-size: 16px;">由于我们需要为每个需要匹配的选择器创建一个单独的程序，我们如何才能阻止相同的简单组件执行相同的任务呢?我们的选择器匹配程序的AST是一个基数树状结构，它的边缘标签是简单的选择器组件，节点是层次组合器。

< font-size: 16px;">例如，以下选择器：

< font-size: 16px;">

body > div > link[rel]
body > span
body > span a

< ">我们将获得以下AST：
< font-size: 16px;">

< font-size: 16px;">

< font-size: 16px;">如果选择器有公共前缀，我们可以为所有这些选择器进行匹配。在编译过程中，我们将这个结构压缩为一个指令向量。

< font-size: 16px;">出于性能原因，已编译指令是宏指令，它们合并了多个基本VM指令调用。这样，VM只能为每个输入令牌执行一条宏指令。使用所谓的“[not] JIT-compilation ”编译每个宏指令，这与我们的另一个Rust项目——wirefilter中使用的编译方法相同。

< font-size: 16px;">在内部，宏指令包含Expect和后续的jmp，hereditary_jmp和match基本指令。从这个意义上讲，宏指令类似于微码，如果我们需要向词法分析器请求属性信息，则可以很容易地暂停执行宏指令。