Cloudflare的HTML解析歷史(下)

來(lái)源: Cloudflare
作者:luochicun編譯
時(shí)間:2020-12-24
16876
上文我們引出了一個(gè)雙解析器架構(gòu)的思路,下面就讓我們?cè)敿?xì)介紹一下雙解析器架構(gòu)。

上文我們引出了一個(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)。

ia_7700000002.png

考慮到所需的任務(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)記信息。

ia_7700000003.png

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é)果:

ia_7700000004.png

平均解析時(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è)字符:

ia_7700000005.jpeg

將選擇器組件替換為虛構(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 >”我們將得到以下堆棧:

ia_7700000006.png

現(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):

ia_7700000007.png

指示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:

ia_7700000008.png

如果選擇器有公共前綴,我們可以為所有這些選擇器進(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í)行宏指令。

立即登錄,閱讀全文
版權(quán)說(shuō)明:
本文內(nèi)容來(lái)自于Cloudflare,本站不擁有所有權(quán),不承擔(dān)相關(guān)法律責(zé)任。文章內(nèi)容系作者個(gè)人觀點(diǎn),不代表快出海對(duì)觀點(diǎn)贊同或支持。如有侵權(quán),請(qǐng)聯(lián)系管理員(zzx@kchuhai.com)刪除!
掃碼登錄
打開(kāi)掃一掃, 關(guān)注公眾號(hào)后即可登錄/注冊(cè)
加載中
二維碼已失效 請(qǐng)重試
刷新
賬號(hào)登錄/注冊(cè)
個(gè)人VIP
小程序
快出海小程序
公眾號(hào)
快出海公眾號(hào)
商務(wù)合作
商務(wù)合作
投稿采訪
投稿采訪
出海管家
出海管家