從"算法"角度回答—輸入U(xiǎn)RL后頁面呈現(xiàn)發(fā)生了什么？

猿友 2020-09-02 10:31:12 瀏覽數(shù) (2154)

反饋

文章轉(zhuǎn)載自公眾號：前端三元同學(xué)

老生常談的問題，可以另辟蹊徑來回答！本文不講解 URL 輸入后發(fā)生的網(wǎng)絡(luò)部分，只從算法角度講解拿到頁面后的解析部分，主要分為以下幾個(gè)步驟:

構(gòu)建 DOM樹
樣式計(jì)算
生成布局樹(Layout Tree)

構(gòu)建 DOM 樹

由于瀏覽器無法直接理解 HTML字符串，因此將這一系列的字節(jié)流轉(zhuǎn)換為一種有意義并且方便操作的數(shù)據(jù)結(jié)構(gòu)，這種數(shù)據(jù)結(jié)構(gòu)就是DOM樹。DOM樹本質(zhì)上是一個(gè)以document為根節(jié)點(diǎn)的多叉樹。

那通過什么樣的方式來進(jìn)行解析呢？

HTML文法的本質(zhì)

首先，我們應(yīng)該清楚把握一點(diǎn): HTML 的文法并不是上下文無關(guān)文法。

這里，有必要討論一下什么是上下文無關(guān)文法。

在計(jì)算機(jī)科學(xué)的編譯原理學(xué)科中，有非常明確的定義:

若一個(gè)形式文法G = (N, Σ, P, S) 的產(chǎn)生式規(guī)則都取如下的形式：V-&w，則叫上下文無關(guān)語法。其中 V∈N ，w∈(N∪Σ)* 。

其中把 G = (N, Σ, P, S) 中各個(gè)參量的意義解釋一下:

N 是非終結(jié)符(顧名思義，就是說最后一個(gè)符號不是它, 下面同理)集合。
Σ 是終結(jié)符集合。
P 是開始符，它必須屬于 N ，也就是非終結(jié)符。
S 就是不同的產(chǎn)生式的集合。如 S -> aSb 等等。

通俗一點(diǎn)講，上下文無關(guān)的文法就是說這個(gè)文法中所有產(chǎn)生式的左邊都是一個(gè)非終結(jié)符。

看到這里，如果還有一點(diǎn)懵圈，我舉個(gè)例子你就明白了。

比如:

A -> B

這個(gè)文法中，每個(gè)產(chǎn)生式左邊都會(huì)有一個(gè)非終結(jié)符，這就是上下文無關(guān)的文法。在這種情況下，xBy一定是可以規(guī)約出xAy的。

我們下面看看看一個(gè)反例：

aA -> B
Aa -> B

這種情況就是不是上下文無關(guān)的文法，當(dāng)遇到B的時(shí)候，我們不知道到底能不能規(guī)約出A，取決于左邊或者右邊是否有a存在，也就是說和上下文有關(guān)。

關(guān)于它為什么是非上下文無關(guān)文法，首先需要讓大家注意的是，規(guī)范的 HTML 語法，是符合上下文無關(guān)文法的，能夠體現(xiàn)它非上下文無關(guān)的是不標(biāo)準(zhǔn)的語法。在此我僅舉一個(gè)反例即可證明。

比如解析器掃描到form標(biāo)簽的時(shí)候，上下文無關(guān)文法的處理方式是直接創(chuàng)建對應(yīng) form 的 DOM 對象，而真實(shí)的 HTML5 場景中卻不是這樣，解析器會(huì)查看 form 的上下文，如果這個(gè) form 標(biāo)簽的父標(biāo)簽也是 form, 那么直接跳過當(dāng)前的 form 標(biāo)簽，否則才創(chuàng)建 DOM 對象。

常規(guī)的編程語言都是上下文無關(guān)的，而HTML卻相反，也正是它非上下文無關(guān)的特性，決定了HTML Parser并不能使用常規(guī)編程語言的解析器來完成，需要另辟蹊徑。

解析算法

HTML5 規(guī)范詳細(xì)地介紹了解析算法。這個(gè)算法分為兩個(gè)階段:

標(biāo)記化。
建樹。

對應(yīng)的兩個(gè)過程就是詞法分析和語法分析。

標(biāo)記化算法

這個(gè)算法輸入為 HTML文本，輸出為HTML標(biāo)記，也成為標(biāo)記生成器。其中運(yùn)用有限自動(dòng)狀態(tài)機(jī)來完成。即在當(dāng)當(dāng)前狀態(tài)下，接收一個(gè)或多個(gè)字符，就會(huì)更新到下一個(gè)狀態(tài)。

<html>
  <body>
    Hello sanyuan
  </body>
</html>

通過一個(gè)簡單的例子來演示一下標(biāo)記化的過程。

遇到<, 狀態(tài)為標(biāo)記打開。

接收[a-z]的字符，會(huì)進(jìn)入標(biāo)記名稱狀態(tài)。

這個(gè)狀態(tài)一直保持，直到遇到>，表示標(biāo)記名稱記錄完成，這時(shí)候變?yōu)?strong>數(shù)據(jù)狀態(tài)。

接下來遇到body標(biāo)簽做同樣的處理。

這個(gè)時(shí)候html和body的標(biāo)記都記錄好了。

現(xiàn)在來到<body>中的>，進(jìn)入數(shù)據(jù)狀態(tài)，之后保持這樣狀態(tài)接收后面的字符hello sanyuan。

接著接收 </body> 中的<，回到標(biāo)記打開, 接收下一個(gè)/后，這時(shí)候會(huì)創(chuàng)建一個(gè)end tag的token。

隨后進(jìn)入標(biāo)記名稱狀態(tài), 遇到>回到數(shù)據(jù)狀態(tài)。

接著以同樣的樣式處理 </body>。

建樹算法

之前提到過，DOM 樹是一個(gè)以document為根節(jié)點(diǎn)的多叉樹。因此解析器首先會(huì)創(chuàng)建一個(gè)document對象。標(biāo)記生成器會(huì)把每個(gè)標(biāo)記的信息發(fā)送給建樹器。建樹器接收到相應(yīng)的標(biāo)記時(shí)，會(huì)創(chuàng)建對應(yīng)的 DOM 對象。創(chuàng)建這個(gè)DOM對象后會(huì)做兩件事情:

將DOM對象加入 DOM 樹中。
將對應(yīng)標(biāo)記壓入存放開放(與閉合標(biāo)簽意思對應(yīng))元素的棧中。

還是拿下面這個(gè)例子說:

<html>
  <body>
    Hello sanyuan
  </body>
</html>

首先，狀態(tài)為初始化狀態(tài)。

接收到標(biāo)記生成器傳來的html標(biāo)簽，這時(shí)候狀態(tài)變?yōu)?strong>before html狀態(tài)。同時(shí)創(chuàng)建一個(gè)HTMLHtmlElement的 DOM 元素, 將其加到document根對象上，并進(jìn)行壓棧操作。

接著狀態(tài)自動(dòng)變?yōu)?strong>before head, 此時(shí)從標(biāo)記生成器那邊傳來body，表示并沒有head, 這時(shí)候建樹器會(huì)自動(dòng)創(chuàng)建一個(gè)HTMLHeadElement并將其加入到DOM樹中。

現(xiàn)在進(jìn)入到in head狀態(tài), 然后直接跳到after head。

現(xiàn)在標(biāo)記生成器傳來了body標(biāo)記，創(chuàng)建HTMLBodyElement, 插入到DOM樹中，同時(shí)壓入開放標(biāo)記棧。

接著狀態(tài)變?yōu)?strong>in body，然后來接收后面一系列的字符: Hello sanyuan。接收到第一個(gè)字符的時(shí)候，會(huì)創(chuàng)建一個(gè)Text節(jié)點(diǎn)并把字符插入其中，然后把Text節(jié)點(diǎn)插入到 DOM 樹中body元素的下面。隨著不斷接收后面的字符，這些字符會(huì)附在Text節(jié)點(diǎn)上。

現(xiàn)在，標(biāo)記生成器傳過來一個(gè)body的結(jié)束標(biāo)記，進(jìn)入到after body狀態(tài)。

標(biāo)記生成器最后傳過來一個(gè)html的結(jié)束標(biāo)記, 進(jìn)入到after after body的狀態(tài)，表示解析過程到此結(jié)束。

容錯(cuò)機(jī)制

講到HTML5規(guī)范，就不得不說它強(qiáng)大的寬容策略, 容錯(cuò)能力非常強(qiáng)，雖然大家褒貶不一，不過我想作為一名資深的前端工程師，有必要知道HTML Parser在容錯(cuò)方面做了哪些事情。

接下來是 WebKit 中一些經(jīng)典的容錯(cuò)示例，發(fā)現(xiàn)有其他的也歡迎來補(bǔ)充。

1.使用</br>而不是<br>

if (t->isCloseTag(brTag) && m_document->inCompatMode()) {
  reportError(MalformedBRError);
  t->beginTag = true;
}

全部換為<br>的形式。

2.表格離散

<table>
  <table>
    <tr><td>inner table</td></tr>
  </table>
  <tr><td>outer table</td></tr>
</table>

WebKit會(huì)自動(dòng)轉(zhuǎn)換為:

<table>
    <tr><td>outer table</td></tr>
</table>
<table>
    <tr><td>inner table</td></tr>
</table>

3.表單元素嵌套

這時(shí)候直接忽略里面的form。

樣式計(jì)算

關(guān)于CSS樣式，它的來源一般是三種:

link標(biāo)簽引用
style標(biāo)簽中的樣式
元素的內(nèi)嵌style屬性

格式化樣式表

首先，瀏覽器是無法直接識別 CSS 樣式文本的，因此渲染引擎接收到 CSS 文本之后第一件事情就是將其轉(zhuǎn)化為一個(gè)結(jié)構(gòu)化的對象，即styleSheets。

這個(gè)格式化的過程過于復(fù)雜，而且對于不同的瀏覽器會(huì)有不同的優(yōu)化策略，這里就不展開了。

在瀏覽器控制臺(tái)能夠通過document.styleSheets來查看這個(gè)最終的結(jié)構(gòu)。當(dāng)然，這個(gè)結(jié)構(gòu)包含了以上三種CSS來源，為后面的樣式操作提供了基礎(chǔ)。

標(biāo)準(zhǔn)化樣式屬性

有一些 CSS 樣式的數(shù)值并不容易被渲染引擎所理解，因此需要在計(jì)算樣式之前將它們標(biāo)準(zhǔn)化，如em->px,red->#ff0000,bold->700等等。

計(jì)算每個(gè)節(jié)點(diǎn)的具體樣式

樣式已經(jīng)被格式化和標(biāo)準(zhǔn)化,接下來就可以計(jì)算每個(gè)節(jié)點(diǎn)的具體樣式信息了。

其實(shí)計(jì)算的方式也并不復(fù)雜，主要就是兩個(gè)規(guī)則: 繼承和層疊。

每個(gè)子節(jié)點(diǎn)都會(huì)默認(rèn)繼承父節(jié)點(diǎn)的樣式屬性，如果父節(jié)點(diǎn)中沒有找到，就會(huì)采用瀏覽器默認(rèn)樣式，也叫UserAgent樣式。這就是繼承規(guī)則，非常容易理解。

然后是層疊規(guī)則，CSS 最大的特點(diǎn)在于它的層疊性，也就是最終的樣式取決于各個(gè)屬性共同作用的效果，甚至有很多詭異的層疊現(xiàn)象，看過《CSS世界》的同學(xué)應(yīng)該對此深有體會(huì)，具體的層疊規(guī)則屬于深入 CSS 語言的范疇，這里就不過多介紹了。

不過值得注意的是，在計(jì)算完樣式之后，所有的樣式值會(huì)被掛在到window.computedStyle當(dāng)中，也就是可以通過JS來獲取計(jì)算后的樣式，非常方便。

生成布局樹

現(xiàn)在已經(jīng)生成了DOM樹和DOM樣式，接下來要做的就是通過瀏覽器的布局系統(tǒng)確定元素的位置，也就是要生成一棵布局樹(Layout Tree)。

布局樹生成的大致工作如下:

遍歷生成的 DOM 樹節(jié)點(diǎn)，并把他們添加到布局樹中。
計(jì)算布局樹節(jié)點(diǎn)的坐標(biāo)位置。

值得注意的是，這棵布局樹值包含可見元素，對于 head標(biāo)簽和設(shè)置了display: none的元素，將不會(huì)被放入其中。

有人說首先會(huì)生成Render Tree，也就是渲染樹，其實(shí)這還是 16 年之前的事情，現(xiàn)在 Chrome 團(tuán)隊(duì)已經(jīng)做了大量的重構(gòu)，已經(jīng)沒有生成Render Tree的過程了。而布局樹的信息已經(jīng)非常完善，完全擁有Render Tree的功能。

之所以不講布局的細(xì)節(jié)，是因?yàn)樗^于復(fù)雜，一一介紹會(huì)顯得文章過于臃腫，不過大部分情況下我們只需要知道它所做的工作是什么即可，如果想深入其中的原理，知道它是如何來做的，我強(qiáng)烈推薦你去讀一讀人人FED團(tuán)隊(duì)的文章從Chrome源碼看瀏覽器如何layout布局。

總結(jié)

梳理一下這一節(jié)的主要脈絡(luò):

總結(jié)

以上就是W3Cschool編程獅關(guān)于從"算法"角度回答—輸入U(xiǎn)RL后頁面呈現(xiàn)發(fā)生了什么？的相關(guān)介紹了，希望對大家有所幫助。

前端

0 人點(diǎn)贊