Cloudflare的HTML解析歷史（下）

上文我們引出了一個(gè)雙解析器架構(gòu)的思路，下面就讓我們?cè)敿?xì)介紹一下雙解析器架構(gòu)。

雙解析器架構(gòu)

大多數(shù)開(kāi)發(fā)人員都很熟悉，并且更喜歡將基于CSS選擇器的API（例如在Cheerio，jQuery或DOM本身中）來(lái)完成HTML的修改任務(wù)。我們還決定將我們的API基于CSS選擇器，盡管這意味著額外的實(shí)現(xiàn)復(fù)雜性，但是這個(gè)決定為解析優(yōu)化創(chuàng)造了更多的機(jī)會(huì)。

當(dāng)選擇器定義了應(yīng)重寫內(nèi)容的范圍時(shí)，我們意識(shí)到我們可以跳過(guò)不在這個(gè)范圍內(nèi)的內(nèi)容，并且不會(huì)為它生成標(biāo)記。這不僅大大加快了解析本身的速度，而且還避免了與JavaScript VM的來(lái)回交互帶來(lái)的性能負(fù)擔(dān)。

考慮到所需的任務(wù)，LOL HTML的解析器由兩個(gè)內(nèi)部解析器組成：

1.Lexer—一個(gè)常規(guī)的完整解析器，它為遇到的所有類型的內(nèi)容生成輸出；

2.標(biāo)記掃描器——查找開(kāi)始和結(jié)束標(biāo)記，跳過(guò)對(duì)其余內(nèi)容的解析。標(biāo)記掃描器只解析標(biāo)記名并將其提供給選擇器匹配器，如果需要匹配或關(guān)于標(biāo)記的附加信息(如屬性)，則匹配器將把解析器切換到lexer。

一旦輸入超出所有選擇器匹配的范圍，解析器就切換回標(biāo)記掃描器。標(biāo)記掃描器有時(shí)也可能將解析器切換到Lexer，如果它需要用于解析反饋模擬的其他標(biāo)記信息。

LOL HTML體系結(jié)構(gòu)

對(duì)于同一語(yǔ)法使用兩種不同的解析器實(shí)現(xiàn)將增加開(kāi)發(fā)成本，并且由于實(shí)現(xiàn)的不一致性而容易出錯(cuò)。我們通過(guò)實(shí)現(xiàn)一個(gè)小型的基于Rust宏的DSL來(lái)最小化這些風(fēng)險(xiǎn)，該DSL在本質(zhì)上類似于Ragel，DSL程序描述了不確定的有限自動(dòng)機(jī)狀態(tài)以及與每個(gè)狀態(tài)轉(zhuǎn)換和匹配的輸入字節(jié)關(guān)聯(lián)的操作。

DSL狀態(tài)定義的示例：

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程序擴(kuò)展為不那么漂亮，但效率極高的Rust代碼。

我們不再需要為每個(gè)解析器重新實(shí)現(xiàn)驅(qū)動(dòng)解析過(guò)程的代碼，我們需要做的就是為每個(gè)操作定義不同的操作實(shí)現(xiàn)。對(duì)于標(biāo)記掃描器來(lái)說(shuō)，大多數(shù)操作都是無(wú)操作的，因此Rust編譯器為我們完成了NFA優(yōu)化工作：它使用無(wú)操作操作優(yōu)化了狀態(tài)分支，如果所有分支都有無(wú)操作操作，它甚至?xí)?yōu)化整個(gè)狀態(tài)。

字節(jié)片處理優(yōu)化

Rust具有出色的內(nèi)存安全機(jī)制，但是有時(shí)它們太消耗性能。

解析器的任務(wù)是掃描輸入內(nèi)容，并找到 language - tokens 的詞匯單位的邊界及其內(nèi)部部分。例如，HTML起始標(biāo)記令牌由多個(gè)部分組成，這意味著標(biāo)記名稱的輸入字節(jié)切片和代表屬性和值的多對(duì)輸入切片對(duì)：

struct StartTagToken {
   name: &'i [u8],
   attributes: Vec,
   self_closing: bool
}

由于Rust在內(nèi)存訪問(wèn)上使用了綁定檢查，因此構(gòu)造令牌可能是一個(gè)相對(duì)費(fèi)時(shí)的操作。我們需要能夠在不到一秒的時(shí)間內(nèi)構(gòu)建數(shù)千條這樣的指令，因此每個(gè)CPU指令都非常重要。

遵循高性能低能耗的原則，我們使用令牌的“token outline”表示:我們不使用令牌部分的內(nèi)存片，而是使用數(shù)字范圍，在需要時(shí)將其延遲轉(zhuǎn)換為字節(jié)片。

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

你可能已經(jīng)注意到，通過(guò)這種方法，我們不再受限于輸入塊的運(yùn)行周期，事實(shí)證明這非常有用。如果開(kāi)始標(biāo)記分布在多個(gè)輸入塊中，我們可以輕松地更新當(dāng)前正在構(gòu)造的令牌，因?yàn)橹恍枵{(diào)整整數(shù)索引即可獲得新的輸入塊。這樣一來(lái)，我們就可以避免使用來(lái)自新輸入存儲(chǔ)區(qū)（可能是輸入塊本身或內(nèi)部解析器的緩沖區(qū)）的切片構(gòu)造新的令牌。

這一次我們不能避免輸入字符編碼的轉(zhuǎn)換，我們公開(kāi)了可在JavaScript字符串上運(yùn)行的面向用戶的API，輸入的HTML可以是任何編碼。幸運(yùn)的是，我們?nèi)匀豢梢栽诓唤獯a的情況下進(jìn)行解析，并且只能在請(qǐng)求的令牌范圍內(nèi)進(jìn)行編碼和解碼，盡管我們?nèi)匀徊荒軐?duì)UTF-16進(jìn)行編碼。

因此，當(dāng)用戶在API中請(qǐng)求元素的標(biāo)記名稱時(shí)，在內(nèi)部仍會(huì)在輸入的字符編碼中將其表示為字節(jié)片，但是當(dāng)提供給用戶時(shí)，它將被動(dòng)態(tài)解碼。當(dāng)用戶設(shè)置新標(biāo)記名稱時(shí)，將發(fā)生相反的過(guò)程。

對(duì)于選擇器匹配，我們?nèi)匀豢梢栽谠季幋a表示形式上進(jìn)行操作，這是因?yàn)槲覀兲崆爸懒溯斎刖幋a，所以我們可以預(yù)先將選擇器中的值轉(zhuǎn)換為頁(yè)面的字符編碼，這樣就可以在不解碼每個(gè)令牌字段的情況下進(jìn)行比較。

正如你所看到的，新的解析器架構(gòu)以及所有這些優(yōu)化都產(chǎn)生了非常好的性能結(jié)果：

平均解析時(shí)間取決于輸入大小——越小越好

LOL HTML的標(biāo)記掃描器通常是LazyHTML的兩倍，而詞法分析器具有類似的性能，在較大的輸入量上要優(yōu)于LazyHTML。兩者都比html5ever的令牌生成器快幾倍，html5ever是Mozilla的Servo瀏覽器引擎中使用Rust實(shí)現(xiàn)的另一個(gè)解析器。

CSS選擇器匹配的VM

有了快速解析器，我們只缺少一件事，即CSS選擇器匹配器。最初，我們認(rèn)為我們可以為此目的使用Servo的CSS選擇器匹配引擎。經(jīng)過(guò)幾天的測(cè)試，結(jié)果表明它不太適合我們的任務(wù)。

它不能與我們的雙重解析器體系結(jié)構(gòu)一起很好地工作。我們首先需要只匹配標(biāo)記掃描器中的標(biāo)記名稱，然后，如果失敗，則在詞法分析器中查詢屬性。選擇器庫(kù)的設(shè)計(jì)沒(méi)有考慮到這種體系結(jié)構(gòu)，因此，如果信息不足，我們需要一些黑客技術(shù)來(lái)防止匹配。它是低效的，因?yàn)槲覀冃枰诰戎笾匦麻_(kāi)始匹配。另外還有其他問(wèn)題，例如lazy字符解碼的集成和使用標(biāo)記名哈希的標(biāo)記名比較的集成。

匹配的方向

遇到的主要問(wèn)題是需要回溯所有開(kāi)放元素以進(jìn)行匹配，瀏覽器從右到左匹配選擇器，并遍歷元素的所有源頭。這個(gè)StackOverflow很好地解釋了為什么要這樣做。我們需要存儲(chǔ)有關(guān)所有打開(kāi)的元素及其屬性的信息。不過(guò)在內(nèi)存緊張的情況下，我們無(wú)法做到這一點(diǎn)。在本文的示例中，這種匹配方法效率不高，與瀏覽器不同，我們希望只有幾個(gè)選擇器和許多元素。在本文的示例中，從左到右，匹配選擇器會(huì)變得更有效率。

body > div.foo  img[alt] > div.foo ul

可以將其拆分為歸因于特定元素的各個(gè)組件，并使用介于兩者之間的分層組合器：

body > div.foo img[alt] > div.foo  ul

---    ------- --------   -------  --

每個(gè)組件都很容易匹配開(kāi)始標(biāo)記標(biāo)記，只需將標(biāo)記字段與組件中的值進(jìn)行比較即可，讓我們想象一下，每一個(gè)這樣的組成部分都是所有可能組成部分的無(wú)限字母表中的一個(gè)字符：

將選擇器組件替換為虛構(gòu)字符來(lái)重寫選擇器：

a > b c > b d

有一種非常眾所周知的抽象來(lái)表達(dá)這些關(guān)系，這就是正則表達(dá)式?？梢詫⑦x擇器替換組合器替換為正則表達(dá)式語(yǔ)法：

ab.*cb.*d

我們將CSS選擇器轉(zhuǎn)換為可在開(kāi)始標(biāo)記令牌序列上執(zhí)行的正則表達(dá)式，請(qǐng)注意，并非所有CSS選擇器都可以轉(zhuǎn)換為這種常規(guī)語(yǔ)法，我們匹配的輸入有一些細(xì)節(jié)，稍后我們將討論這些細(xì)節(jié)。然而，這是一個(gè)很好的起點(diǎn)，它允許我們表達(dá)一個(gè)選擇器的重要子集。

實(shí)現(xiàn)虛擬機(jī)

接下來(lái)，我們開(kāi)始研究正則表達(dá)式的非回溯算法，虛擬機(jī)方法似乎適合我們的任務(wù)要求，因?yàn)榭赡苡幸粋€(gè)非回溯實(shí)現(xiàn)，該實(shí)現(xiàn)足夠靈活，可以解決字符串上的正則表達(dá)式匹配與抽象之間的差異。

基于VM的正則表達(dá)式匹配是許多正則表達(dá)式庫(kù)（例如regexp2和Rust的regex）中的引擎之一，基本思想是，與其為正則表達(dá)式構(gòu)建NFA或DFA，不如通過(guò)稍后由虛擬機(jī)執(zhí)行的指令將其轉(zhuǎn)換為DSL匯編語(yǔ)言，正則表達(dá)式被視為接受用于匹配的字符串的程序。

由于VM程序只是具有ε-transitions的NFA的表示形式，因此它可以在執(zhí)行期間同時(shí)處于多個(gè)狀態(tài)，或者換句話說(shuō)，產(chǎn)生多個(gè)線程。如果一個(gè)或多個(gè)狀態(tài)成功，則正則表達(dá)式匹配。

例如，以下VM指令：

1.expect c：等待下一個(gè)輸入字符，如果不等于指令的操作數(shù)，則中止線程；

2.jmp L：跳轉(zhuǎn)到標(biāo)簽‘L’；

3.thread L1, L2：生成標(biāo)簽L1和L2的線程，有效地分割執(zhí)行；

4.match：通過(guò)匹配成功執(zhí)行線程；

例如，使用此指令集，可將正則表達(dá)式 “ab*c” 轉(zhuǎn)換為：

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

讓我們嘗試從前面看到的選擇器中轉(zhuǎn)換正則表達(dá)式ab.*cb.*d：

   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

看起來(lái)很復(fù)雜，盡管此匯編語(yǔ)言通常是為正則表達(dá)式設(shè)計(jì)的，但正則表達(dá)式可能比我們的情況復(fù)雜得多。對(duì)我們而言，唯一重要的重復(fù)是 “.*”。 因此，與其用多個(gè)指令來(lái)表達(dá)它，不如只使用一個(gè)名為hereditary_jmp的指令：

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

該指令告訴VM記住指令的標(biāo)記操作數(shù)，并無(wú)條件地在每個(gè)輸入字符上產(chǎn)生一個(gè)跳轉(zhuǎn)到該標(biāo)簽的線程。

正則表達(dá)式的字符串輸入與提供給VM的輸入之間有一個(gè)重要的區(qū)別，即輸入可以縮小!

常規(guī)字符串只是一個(gè)連續(xù)的字符序列，而我們操作的是一個(gè)開(kāi)放元素序列。隨著新標(biāo)記的到來(lái)，這個(gè)序列可以擴(kuò)大也可以收縮。假設(shè)我們用虛構(gòu)的語(yǔ)言將< div >表示為'a'字符，因此輸入< div > < div > < div >可以將其表示為aaa，如果輸入的下一個(gè)標(biāo)記是，則我們的“字符串”縮小為aa。

你可能會(huì)認(rèn)為此時(shí)我們的抽象無(wú)效，我們應(yīng)該嘗試其他方法。不過(guò)計(jì)算機(jī)輸入的內(nèi)容，是一堆開(kāi)放元素，我們需要一個(gè)類似于棧的結(jié)構(gòu)來(lái)存儲(chǔ)我們的VM迄今為止看到的hereditrary_jmp指令標(biāo)記。那么，為什么不將其存儲(chǔ)在開(kāi)放元素堆棧中呢？如果將下一條指令指針存儲(chǔ)在成功執(zhí)行了預(yù)期指令的每個(gè)堆棧項(xiàng)目上，我們將獲得VM狀態(tài)的完整快照，因此如果堆?？s小，我們可以輕松地回滾到該狀態(tài)。

借助此實(shí)現(xiàn)，我們無(wú)需在堆棧上存儲(chǔ)除標(biāo)記名以外的任何內(nèi)容，并且考慮到我們可以使用標(biāo)記名哈希算法，因此每個(gè)打開(kāi)的元素僅是64位整數(shù)。作為另一個(gè)較小的優(yōu)化，為避免遍歷整個(gè)堆棧以在每個(gè)新輸入上尋找有效的跳躍痕跡，我們要將每個(gè)原先的索引與每個(gè)堆棧項(xiàng)上的跳躍痕跡一起存儲(chǔ)。

例如，使用以下選擇器 “body > div span”，我們將得到以下VM程序（我們?nèi)サ袅藰?biāo)記，只使用指令索引）：

0| expect 1| expect 2| hereditary_jmp 3

3| expect 4| match

輸入“ < body > < di v> < div > < a >”我們將得到以下堆棧：

現(xiàn)在，如果下一個(gè)標(biāo)記是開(kāi)始標(biāo)記，則VM將首先嘗試從頭開(kāi)始執(zhí)行選擇器程序，并在第一條指令上就失敗。但是，它還會(huì)尋找堆棧上任何活躍的跳躍痕跡。我們有一個(gè)跳轉(zhuǎn)到索引3的指令。跳轉(zhuǎn)到該指令后，VM成功地生成了一個(gè)匹配。如果稍后再獲得另一個(gè)開(kāi)始標(biāo)記，則遵循相同的步驟。

如果我們隨后收到一串 “” 結(jié)束標(biāo)記，則我們的堆棧將僅包含一項(xiàng)：

指示VM跳至索引1處的指令，有效回滾以匹配選擇器的div組件。

我們?cè)谇懊嫣岬竭^(guò)，如果我們只有來(lái)自標(biāo)記掃描程序的標(biāo)記名稱，并且需要通過(guò)運(yùn)行l(wèi)exer獲得更多信息，那么我們可以退出匹配過(guò)程。使用VM方法很簡(jiǎn)單，只需停止當(dāng)前指令的執(zhí)行，并在獲得所需信息后恢復(fù)執(zhí)行即可。

選擇器的匹配

由于我們需要為每個(gè)需要匹配的選擇器創(chuàng)建一個(gè)單獨(dú)的程序，我們?nèi)绾尾拍茏柚瓜嗤暮?jiǎn)單組件執(zhí)行相同的任務(wù)呢?我們的選擇器匹配程序的AST是一個(gè)基數(shù)樹(shù)狀結(jié)構(gòu)，它的邊緣標(biāo)簽是簡(jiǎn)單的選擇器組件，節(jié)點(diǎn)是層次組合器。

例如，以下選擇器：

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

我們將獲得以下AST：

如果選擇器有公共前綴，我們可以為所有這些選擇器進(jìn)行匹配。在編譯過(guò)程中，我們將這個(gè)結(jié)構(gòu)壓縮為一個(gè)指令向量。

出于性能原因，已編譯指令是宏指令，它們合并了多個(gè)基本VM指令調(diào)用。這樣，VM只能為每個(gè)輸入令牌執(zhí)行一條宏指令。使用所謂的“[not] JIT-compilation ”編譯每個(gè)宏指令，這與我們的另一個(gè)Rust項(xiàng)目——wirefilter中使用的編譯方法相同。

在內(nèi)部，宏指令包含Expect和后續(xù)的jmp，hereditary_jmp和match基本指令。從這個(gè)意義上講，宏指令類似于微碼，如果我們需要向詞法分析器請(qǐng)求屬性信息，則可以很容易地暫停執(zhí)行宏指令。