DOM 树的构建

 关注
发布于: 2020 年 07 月 11 日
DOM 是 HTML 文档的编程接口。它提供了对文档的结构化的表述，并定义了一种方式可以使从程序中对该结构进行访问，从而改变文档的结构，样式和内容。那么浏览器是如何将 HTML 解析成 DOM 树的呢？我们今天来探索一下。
﻿
大体来说，从 HTML 文档到 DOM 树有两大步：
第一步：将 HTML 文档解析成一个个 Token。
第二步：根据 Token 构建 DOM 树。其具体的流程图如下：
﻿
DOM 树构建流程
﻿
首先，浏览器从磁盘或网络读取 HTML 的原始字节，并根据文件的指定编码（例如 UTF-8）将它们转换成各个字符。下一步通过状态机去做分词，将字符串转换成 Token ，每个 Token 都具有特殊含义和一组规则。Token 会被转换成定义了属性等规则的“对象”，同时利用栈构建 DOM 树。下面，我们先来看看 Token 是这么被拆分的。
﻿
Token 的拆分﻿
Token 是编译原理里的一个术语，它表示最小的有意义的单元。 我们来看看一个非常标准的标签，会如何被拆分。
﻿
<p class="a">text text text</p>
﻿
这里第一个 Token 应该是什么呢？显然，作为一个词（Token），整个 p 标签肯定是过大了，甚至它里面还可以嵌套。那么，只用 p 标签的开头呢？`<p class="a">`也不太合适，因为标签里面可能有属性。这里的第一个 Token 应该是 `<p`，那么我们继续拆分，下一个 Token 就是 `class="a"` 属性，然后是 p 标签的结束 `>`。接着是文本 `text text text`，最后是 p 标签的结束标签 `</p>`。我们把一段标签拆分成了几个 Token 。
﻿
﻿
这里面的除了刚才拆分的几个 Token ，还有注释、CDATA数据节点等。
﻿
在chrome里，总共定义了7中 Token 类型：
﻿
enum TokenType {
    StartTag,
    EndTag,
    Comment,
    Character,
    Uninitialized,
    DOCTYPE,
    EndOfFile,
};
﻿
根据这样的分析，浏览器是如何用代码实现的呢？我们知道需要被解析器解析的代码是一点点的从浏览器网络进程接收来的，而且是接收一个字符，解析一个字符。
﻿
那么在接受第一个字符之前，我们完全无法判断这是哪一个 Token 。比如我们接收的第一个字符是 `<` ，这个时候我们能判断它肯定不是一个属性的 Token ，那么它就有可能是开始标签的开始、结束标签、注释等等。那么随着接受的字符越来越多，拼出其他的内容可能性就越来越少。然后我们再继续读一个字符，比如是 `p`，那么我们知道它肯定不是一个注释了。然后就这样一直解析，当解析到了一个空格，这个时候已经匹配到了第一个 Token 了，它的意思就是一个标签的开始。
﻿
实际上，解析器每读入一个字符都要做一次判断，而且这些判断都是跟当前状态有关的。如果我们想去实现将一个个字符解析成 Token，其实就是在这些 Token 的状态中不断的跳转，最后去匹配一个 Token，我们应该怎么做呢？常见的做法是使用状态机。
状态机绝大多数语言的词法部分都是用状态机实现的。我们来把刚才那些判断逻辑画成一个状态机来看看。
﻿
HTML 词法状态机
﻿
当然了，这里的分析还比较粗糙，真正完成的 HTML 词法状态机，比这个要复杂的多。我们可以看看 下面 HTML 官方文档。官方文档里定义了 80 个状态。
﻿
https://html.spec.whatwg.org/multipage/parsing.html#tokenization​html.spec.whatwg.org
﻿
那么我来看看这里面具体的过程。开始从这个红点开始。在初始状态，我们仅仅区分 `<` 和 `非<`。如果这个字符是个`非<`，那么可以认为进入了一个文本节点。如果这个字符是 `<`，那么进入一个标签状态，就是 `tag open` 状态。到了 `tag open` 状态，后面可能有三种情况，它可能是个字母 `[letter]` ，或者是 `！`，或者是 `/`。然后再根据字符去判断下一步的状态。其本质就是将每个词的“特征字符”逐个拆分成独立的状态，然后再把所有词的特征字符合并起来，形成一个连通图。
﻿
有了状态机，我们来看看如何通过代码去实现这个状态机。我们可以先自己想一下，这个实现不太难，就是去做各种判断。我们来看一个用 JS 实现的例子。
function data(c) {
  if (c === '<') {
    return tagOpen;
  } else if (c === EOF) {
    emit({
      type: 'EOF',
    });
    return;
  } else {
    emit({
      type: 'text',
      content: c,
    });
    return data;
  }
}
function tagOpen(c) {
  if (c === '/') {
    return endTagOpen;
  } else if (c.match(/^[a-zA-Z]$/)) {
    currentToken = {
      type: 'startTag',
      tagName: '',
    };
    return tagName(c);
  } else {
    emit({
      type: 'text',
      content: c,
    });
    return;
  }
}
//……
﻿
这里的 data 就是初始状态，比如这个字符是 `< `，下一个字符就要用 tagOpen 函数去处理。如果这个那么已经可以匹配一个 Token了，那么可以用 emitToken 函数来输出解析好的 Token。这里每一个状态就是一个函数，通过函数里的判断来区分下一个字符需要被哪个函数判断，也就是状态的迁移，这个函数也会返回一个状态。这样我们的状态迁移代码就非常的简单：
 let state = data;
 for (let c of html) {
    state = state(c);
 }
﻿
这里我们通过 while 循环去不断的处理传进来的字符流。那么我们来完善一下这个词法分析器：
function parseHTML(html) {
  let state = data;
  for (let c of html) {
    state = state(c);
  }
  state = state(EOF);
}
﻿
至此，我们就把字符流拆成 Token 了。
构建 DOM 树下面就要把这些 Token 变成 DOM 树。我们还是结合一段代码来看具体的过程。
<html>
	<head>
	    <meta charset="utf-8">
	</head>
	<body>
	    <div>
	        <p class="a">text text text</p>
	    </div>
	</body>
</html>
﻿
把这段代码拆成 Token 之后，就是下面这样，我这里省略了里面的换行跟空格。
tagName: html  |  type: startTag   |  attr:                 |  text: ''
tagName: head  |  type: startTag   |  attr:                 |  text: ''
tagName: meta  |  type: startTag   |  attr:charset="utf-8"  |  text: ''
tagName: head  |  type: EndTag     |  attr:                 |  text: ''
tagName: body  |  type: startTag   |  attr:                 |  text: ''
tagName: div   |  type: startTag   |  attr:                 |  text: ''
tagName: p     |  type: startTag   |  attr:class="a"        |  text: ''
tagName:       |  type: Character  |  attr:                 |  text: 'text text text'
tagName: div   |  type: EndTag     |  attr:                 |  text: ''
tagName: body  |  type: EndTag     |  attr:                 |  text: ''
tagName: html  |  type: EndTag     |  attr:                 |  text: ''
tagName:       |  type: EndOfFile  |  attr:                 |  text: ''
﻿
首先我们来看，这里的 Token 中，startTag 和 endTag 通常是需要成对匹配的。对于 `<br/>` 这种自闭合标签，可视为入栈后立马出栈。
﻿
在解析开始的时候，会默认创建一个根为 document 的空 DOM 结构。同时会将一个 startTag document 的 Token 放入栈底。
﻿
﻿
然后经过词法分析后的第一个 Token 会被持续的放入到栈中。同时会创建一个相应的 DOM 节点，用代码实现的话就是实例化一个元素。每生成一个 Token，就把它放入这个栈里面。当下一个 Token 是个 endTag 的时候，就会把栈里的 Token 一直弹出来，直到遇到一个和它的 tagName 一样的 Token 才停止。
﻿
﻿
然后就通过这样不断的入栈出栈，最后生成整个的 DOM 树。
﻿
﻿
这里讲的只是一个最简单的例子。现实情况中，还要处理图片、音频、视频。css、js等，还有容错机制。对于 HTML 文档，你从来没见过它报错。就算胡乱写，它也绝不会吭声。因为 HTML 的标准在演进的过程中走了很多岔路，浏览器需要兼容各种奇怪的写法，所以它有很多的容错机制。
﻿
到此，整个 DOM 树就构建完成了。
﻿
更完整的代码可以看这里：
https://github.com/huyinglin/ToyBrowser/blob/master/html-parser/index.js​github.com
﻿
最后我们再来看几个关于 DOM 树解析的几个常见的问题。
1. JS会阻塞 DOM 树的解析吗？
2. CSS会阻塞 DOM 树的解析吗？
﻿
我们先来看一段代码。
<html>
<body>
    <div>text</div>
    <script>
	    let div1 = document.getElementsByTagName('div')[0];
	    div1.innerText = 'insert text';
    </script>
    <div>test</div>
</body>
</html>
﻿
我在两个 DIV 中插入了一段内联的 JS 代码。这个时候会发生什么呢？此时解析器会停止 DOM 的解析。等待这段 JS 代码的执行，等它执行完了再继续解析下面的 DOM。因为这段代码可能会修改 DOM 的内容。必须执行完了这个修改才能继续下面的解析。
﻿
那么如果这个脚本是外链的呢？
//foo.js
let div1 = document.getElementsByTagName('div')[0];
div1.innerText = 'insert text';
﻿
<html>
<body>
    <div>text</div>
    <script type="text/javascript" src='foo.js'></script>
    <div>test</div>
</body>
</html>
﻿
这个时候，同样会停止 DOM 的解析，先下载这个 JS 文件，然后再执行这个文件。
﻿
我们再来看一种情况。
//theme.css
div {
	color:blue
}
﻿
<html>
    <head>
        <style src='theme.css'></style>
    </head>
<body>
    <div>text</div>
    <script>
        let div1 = document.getElementsByTagName('div')[0];
        div1.innerText = 'insert text'; // 需要DOM
        div1.style.color = 'red';  // 需要CSSOM
    </script>
    <div>test</div>
</body>
</html>
﻿
这个代码里出现了一句 `div1.style.color = 'red'`，它是去修改 DOM 元素的样式。这个时候，如果代码里引用了外部的 CSS 文件，那么在执行 JS 之前，要等待外部的 CSS 文件下载完成，并解析成 CSSOM 之后，才能执行 JS 代码。其实，不管 JS 代码里有没有去操作 style 的代码，都会先下载 CSS 文件，然后等待 CSS 解析完成后，再执行 JS 代码。
﻿
我们再来看看 script 标签两个常见的属性。async 和 defer。
<script async type="text/javascript" src='foo.js'></script>
<script defer type="text/javascript" src='foo.js'></script>
﻿
async 就是可以让这个 JS 代码异步执行。defer 是表明 JS 代码不会操作 DOM 的结构，它会先下载，在 DOM 树解析完之前去执行它。我们来看个图。
﻿
﻿
正常的 script 是同步的，遇到 script 就马上下载、执行。加了 defer 后，会先下载这个 JS 文件，然后在解析完 DOM 之前去执行它，加了 defer 后的表现和把 JS 文件放在 body 底部的效果一样。加了 async 后，它是异步下载 JS 文件，然后下载完就马上执行。
﻿
对于 script 标签，最稳妥的做法就是将其放到 body 底部。
﻿