Cloudflare的HTML解析歷史（下）

上文我們引出了一個雙解析器架構(gòu)的思路，下面就讓我們詳細介紹一下雙解析器架構(gòu)。

雙解析器架構(gòu)

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

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

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

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

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

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

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

對于同一語法使用兩種不同的解析器實現(xiàn)將增加開發(fā)成本，并且由于實現(xiàn)的不一致性而容易出錯。我們通過實現(xiàn)一個小型的基于Rust宏的DSL來最小化這些風(fēng)險，該DSL在本質(zhì)上類似于Ragel，DSL程序描述了不確定的有限自動機狀態(tài)以及與每個狀態(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程序擴展為不那么漂亮，但效率極高的Rust代碼。

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

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

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

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

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

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

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

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

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

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

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

對于選擇器匹配，我們?nèi)匀豢梢栽谠季幋a表示形式上進行操作，這是因為我們提前知道了輸入編碼，所以我們可以預(yù)先將選擇器中的值轉(zhuǎn)換為頁面的字符編碼，這樣就可以在不解碼每個令牌字段的情況下進行比較。

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

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

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

CSS選擇器匹配的VM

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

它不能與我們的雙重解析器體系結(jié)構(gòu)一起很好地工作。我們首先需要只匹配標記掃描器中的標記名稱，然后，如果失敗，則在詞法分析器中查詢屬性。選擇器庫的設(shè)計沒有考慮到這種體系結(jié)構(gòu)，因此，如果信息不足，我們需要一些黑客技術(shù)來防止匹配。它是低效的，因為我們需要在救助之后重新開始匹配。另外還有其他問題，例如lazy字符解碼的集成和使用標記名哈希的標記名比較的集成。

匹配的方向

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

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

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

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

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

每個組件都很容易匹配開始標記標記，只需將標記字段與組件中的值進行比較即可，讓我們想象一下，每一個這樣的組成部分都是所有可能組成部分的無限字母表中的一個字符：

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

a > b c > b d

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

ab.*cb.*d

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

實現(xiàn)虛擬機

接下來，我們開始研究正則表達式的非回溯算法，虛擬機方法似乎適合我們的任務(wù)要求，因為可能有一個非回溯實現(xiàn)，該實現(xiàn)足夠靈活，可以解決字符串上的正則表達式匹配與抽象之間的差異。

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

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

例如，以下VM指令：

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

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

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

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

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

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

讓我們嘗試從前面看到的選擇器中轉(zhuǎn)換正則表達式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

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

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

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

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

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

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

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

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

0| expect 1| expect 2| hereditary_jmp 3

3| expect 4| match

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

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

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

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

我們在前面提到過，如果我們只有來自標記掃描程序的標記名稱，并且需要通過運行l(wèi)exer獲得更多信息，那么我們可以退出匹配過程。使用VM方法很簡單，只需停止當前指令的執(zhí)行，并在獲得所需信息后恢復(fù)執(zhí)行即可。

選擇器的匹配

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

例如，以下選擇器：

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

我們將獲得以下AST：

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

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

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