| 性能优化

从Chrome源码看浏览器如何构建DOM树

原文链接: https://zhuanlan.zhihu.com/p/24911872

Chrome建DOM源码分析

先画出构建DOM的几个关键的类的UML图，如下所示： image

第一个类HTMLDocumentParser负责解析html文本为tokens，一个token就是一个标签文本的序列化，并借助HTMLTreeBuilder对这些tokens分类处理，根据不同的标签类型、在文档不同位置，调用HTMLConstructionSite不同的函数构建DOM树。而HTMLConstructionSite借助一个工厂类对不同类型的标签创建不同的html元素，并建立起它们的父子兄弟关系，其中它有一个m_document的成员变量，这个变量就是这棵树的根结点，也是js里面的window.document对象。

为作说明，用一个简单的html文件一步步看这个DOM树是如何建立起来的：

1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8">
</head>
<body>
    <div>
        <h1 class="title">demo</h1>
        <input value="hello">
    </div>
</body>
</html>

我们先来研究一下Chrome的加载和解析机制

加载机制

以发http请求去加载html文本做为我们分析的第一步，在此之前的一些初始化就不考虑了。Chrome是在DocumentLoader这个类里面的startLoadingMainResource函数里去加载url返回的数据，如访问一个网站则返回html文本：

1
2
3
4
FetchRequest fetchRequest(m_request, FetchInitiatorTypeNames::document,
                          mainResourceLoadOptions);
m_mainResource =
    RawResource::fetchMainResource(fetchRequest, fetcher(), m_substituteData);

把参数里的m_request打印出来，在这个函数里面加一行代码：

1
LOG(INFO) << "request url is: " << m_request.url().getString()

并重新编译Chrome运行，控制台输出：

1
[22731:775:0107/224014.494114:INFO:DocumentLoader.cpp(719)] request url is: “file:///Users/yincheng/demo.html”

可以看到，这个url确实是我们传进的参数。

发请求后，每次收到的数据块，会通过Blink封装的IPC进程间通信，触发DocumentLoader的dataReceived函数，里面会去调它commitData函数，开始处理具体业务逻辑：

1
2
3
4
5
6
7
8
void DocumentLoader::commitData(const char* bytes, size_t length) {
  ensureWriter(m_response.mimeType());
  if (length)
    m_dataReceived = true;
  m_writer->addData(bytes, length);
}

这个函数关键行是最2行和第7行，ensureWriter这个函数会去初始化上面画的UML图的解析器HTMLDocumentParser(Parser)，并实例化document对象，这些对象都是通过实例m_writer去带动的。也就是说，writer会去实例化Parser之后，第7行writer传递数据给Parser去解析。

检查一下收到的数据bytes是什么东西： image

可以看到bytes就是请求返回的html文本。

在ensureWriter函数里面有个判断：

1
2
3
4
5
6
void DocumentLoader::ensureWriter(const AtomicString& mimeType,
                                  const KURL& overridingURL) {
  if (m_writer)
    return;
}

如果m_writer已经初始化过了，则直接返回。也就是说Parser和document只会初始化一次。

在上面的addData函数里面，会启动一条线程执行Parser的任务：

1
2
if (!m_haveBackgroundParser)
      startBackgroundParser();

并把数据传递给这条线程进行解析，Parser一旦收到数据就会序列成tokens，再构建DOM树。

构建tokens

这里我们只要关注序列化后的token是什么东西就好了，为此，写了一个函数，把tokens的一些关键信息打印出来：

1
2
3
4
5
String getTokenInfo(){
    String tokenInfo = "";
    tokenInfo = "tagName: " + this->m_name + "|type: " + getType() + "|attr:" + getAttributes() + "|text: " + this->m_data;
    return tokenInfo;
  }

打印出来的结果：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
tagName: html  |type: DOCTYPE   |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName: html  |type: startTag  |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName: head  |type: startTag  |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n    "
tagName: meta  |type: startTag  |attr:charset=utf-8 |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName: head  |type: EndTag    |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName: body  |type: startTag  |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n    "
tagName: div   |type: startTag  |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n        "
tagName: h1    |type: startTag  |attr:class=title   |text: "
tagName:       |type: Character |attr:              |text: demo"
tagName: h1    |type: EndTag    |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n        "
tagName: input |type: startTag  |attr:value=hello   |text: "
tagName:       |type: Character |attr:              |text: \n    "
tagName: div   |type: EndTag    |attr:              |text: "
tagName:       |type: Character |attr:              |text:     \n"
tagName: body  |type: EndTag    |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName: html  |type: EndTag    |attr:              |text: "
tagName:       |type: Character |attr:              |text: \n"
tagName:       |type: EndOfFile |attr:              |text: "

这些内容有标签名、类型、属性和innerText，标签之间的文本（换行和空白）也会被当作一个标签处理。Chrome总共定义了7种标签类型：

1
2
3
4
5
6
7
8
9
enum TokenType {
    Uninitialized,
    DOCTYPE,
    StartTag,
    EndTag,
    Comment,
    Character,
    EndOfFile,
  };

有了一个根结点document和一些格式化好的tokens，就可以构建dom树了。

构建DOM树

DOM结点

在研究这个过程之前，先来看一下一个DOM结点的数据结构是怎么样的。以p标签HTMLParagraphElement为例，画出它的UML图，如下所示： image

Node是最顶层的父类，它有三个指针，两个指针分别指向它的前一个结点和后一个结点，一个指针指向它的父结点；

ContainerNode继承于Node，添加了两个指针，一个指向第一个子元素，另一个指向最后一个子元素；

Element又添加了获取dom结点属性、clientWidth、scrollTop等函数;

HTMLElement又继续添加了Translate等控制，最后一级的子类HTMLParagraphElement只有一个创建的函数，但是它继承了所有父类的属性。

需要提到的是每个Node都组合了一个treeScope，这个treeScope记录了它属于哪个document（一个页面可能会嵌入iframe）。

构建DOM最关键的步骤应该是建立起每个结点的父子兄弟关系，即上面提到的成员指针的指向。

浏览器内核

浏览器内核也叫渲染引擎，上面已经看到了Chrome是如何实例化一个P标签的，而从firefox的源码里面P标签的依赖关系是这样的： image

在代码实现上和Chrome没有任何关系。这就好像W3C出了道题，firefox给了一个解法，取名为Gecko，Safari也给了自己的答案，取名Webkit，Chrome觉得Safari的解法比较好直接拿过来用，又结合自身的基础又封装了一层，取名Blink。由于W3C出的这道题”开放性”比较大，出的时间比较晚，导致各家实现各有花样。

明白了这点后，继续DOM构建。下面开始不再说Chrome，叫Webkit或者Blink应该更准确一点

处理开始步骤

Webkit把tokens序列好之后，传递给构建的线程。在HTMLDocumentParser::processTokenizedChunkFromBackgroundParser的这个函数里面会做一个循环，把解析好的tokens做一个遍历，依次调constructTreeFromCompactHTMLToken进行处理。

根据上面的输出，最开始处理的第一个token是docType的那个：

1
"tagName: html  |type: DOCTYPE   |attr:              |text: "

在那个函数里面，首先Parser会调TreeBuilder的函数：

1
m_treeBuilder->constructTree(&token);

然后在TreeBuilder里面根据token的类型做不同的处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void HTMLTreeBuilder::processToken(AtomicHTMLToken* token) {
  if (token->type() == HTMLToken::Character) {
    processCharacter(token);
    return;
  }
  switch (token->type()) {
    case HTMLToken::DOCTYPE:
      processDoctypeToken(token);
      break;
    case HTMLToken::StartTag:
      processStartTag(token);
      break;
    case HTMLToken::EndTag:
      processEndTag(token);
      break;
    //othercode
  }
}

它会对不同类型的结点做相应处理，从上往下依次是文本节点、doctype节点、开标签、闭标签。doctype这个结点比较特殊，单独作为一种类型处理

DOCType处理

在Parser处理doctype的函数里面调了HTMLConstructionSite的插入doctype的函数：

1
2
3
4
void HTMLTreeBuilder::processDoctypeToken(AtomicHTMLToken* token) {
    m_tree.insertDoctype(token);
    setInsertionMode(BeforeHTMLMode);
}

在这个函数里面，它会先创建一个doctype的结点，再创建插dom的task，并设置文档类型：

1
2
3
4
5
6
7
8
void HTMLConstructionSite::insertDoctype(AtomicHTMLToken* token) {
  //const String& publicId = ...
  //const String& systemId = ...
  DocumentType* doctype =
      DocumentType::create(m_document, token->name(), publicId, systemId); //创建DOCType结点
  attachLater(m_attachmentRoot, doctype);  //创建插DOM的task
  setCompatibilityModeFromDoctype(token->name(), publicId, systemId); //设置文档类型
}

我们来看一下不同的doctype对文档类型的设置有什么影响，如下：

1
2
3
4
5
// Check for Quirks Mode.
 if (name != "html" ) {
   setCompatibilityMode(Document::QuirksMode);
   return;
 }

如果tagName不是html，那么文档类型将会是怪异模式，以下两种就会是怪异模式：

1
2
<!DOCType svg>
<!DOCType math>

而常用的html4写法：

1
2
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">

在源码里面这个将是有限怪异模式：

1
2
3
4
5
6
7
// Check for Limited Quirks Mode.
if (!systemId.isEmpty() &&
     publicId.startsWith("-//W3C//DTD HTML 4.01 Transitional//",
                         TextCaseASCIIInsensitive))) {
  setCompatibilityMode(Document::LimitedQuirksMode);
  return;
}

上面的systemId就是” http://www.w3.org/TR/html4/loose.dtd… “，它不是空的，所以判断成立。而如果systemId为空，则它将是怪异模式。如果既不是怪异模式，也不是有限怪异模式，那么它就是标准模式：

1
2
// Otherwise we are No Quirks Mode.
setCompatibilityMode(Document::NoQuirksMode);

常用的html5的写法就是标准模式，如果连DOCType声明也没有呢？那么会默认设置为怪异模式：

1
2
3
void HTMLConstructionSite::setDefaultCompatibilityMode() {
  setCompatibilityMode(Document::QuirksMode);
}

这些模式有什么区别，从源码注释可窥探一二：

1
2
3
4
5
6
7
// There are three possible compatibility modes:
// Quirks - quirks mode emulates WinIE and NS4\. CSS parsing is also relaxed in
// this mode, e.g., unit types can be omitted from numbers.
// Limited Quirks - This mode is identical to no-quirks mode except for its
// treatment of line-height in the inline box model.
// No Quirks - no quirks apply. Web pages will obey the specifications to the
// letter.

大意是说，怪异模式会模拟IE，同时CSS解析会比较宽松，例如数字单位可以省略，而有限怪异模式和标准模式的唯一区别在于在于对inline元素的行高处理不一样。标准模式将会让页面遵守文档规定。

怪异模式下的input和textarea的默认盒模型将会变成border-box： image

标准模式下的文档高度是实际内容的高度： image

而在怪异模式下的文档高度是窗口可视域的高度： image

在有限怪异模式下，div里面的图片下方不会留空白，如下图一所示；而在标准模式下div下方会留点空白，如下图二所示：

image

图一

image

图二

这个空白是div的行高撑起来的，当把div的行高设置成0的时候，就没有下面的空白了。在怪异模和有限怪异模式下，为了计算行内子元素的最小高度，一个块级元素的行高必须被忽略。

这里的叙述虽然跟解读源码没有直接的关系（我们还没解读到CSS处理），但是很有必要提一下。

开标签处理

下一个遇到的开标签是标签，处理这个标签的任务应该是实例化一个HTMLHtmlElement元素，然后把它的父元素指向document。Webkit源码里面使用了一个m_attachmentRoot的变量记录attach的根结点，初始化HTMLConstructionSite也会初始化这个变量，值为document：

1
2
3
4
5
HTMLConstructionSite::HTMLConstructionSite(
    Document& document)
    : m_document(&document),
      m_attachmentRoot(document)) {
}

所以html结点的父结点就是document，实际的操作过程是这样的：

1
2
3
4
5
6
void HTMLConstructionSite::insertHTMLHtmlStartTagBeforeHTML(AtomicHTMLToken* token) {
  HTMLHtmlElement* element = HTMLHtmlElement::create(*m_document);
  attachLater(m_attachmentRoot, element);
  m_openElements.pushHTMLHtmlElement(HTMLStackItem::create(element, token));
  executeQueuedTasks();
}

第二行先创建一个html结点，第三行把它加到一个任务队列里面，传递两个参数，第一个参数是父结点，第二个参数是当前结点，第五行执行队列里面的任务。代码第四行会把它压到一个栈里面，这个栈存放了未遇到闭标签的所有开标签。

第三行attachLater是如何建立一个task的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void HTMLConstructionSite::attachLater(ContainerNode* parent,
                                       Node* child,
                                       bool selfClosing) {
  HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
  task.parent = parent;
  task.child = child;
  task.selfClosing = selfClosing;
  // Add as a sibling of the parent if we have reached the maximum depth
  // allowed.
  if (m_openElements.stackDepth() > maximumHTMLParserDOMTreeDepth &&
      task.parent->parentNode())
    task.parent = task.parent->parentNode();
  queueTask(task);
}

代码逻辑比较简单，比较有趣的是发现DOM树有一个最大的深度：maximumHTMLParserDOMTreeDepth，超过这个最大深度就会把它子元素当作父无素的同级节点，这个最大值是多少呢？512：

1
static const unsigned maximumHTMLParserDOMTreeDepth = 512;

我们重点关注executeQueuedTasks干了些什么，它会根据task的类型执行不同的操作，由于本次是insert的，它会去执行一个插入的函数：

1
2
3
4
5
6
7
void ContainerNode::parserAppendChild(Node* newChild) {
  if (!checkParserAcceptChild(*newChild))
    return;
    AdoptAndAppendChild()(*this, *newChild, nullptr);
  }
  notifyNodeInserted(*newChild, ChildrenChangeSourceParser);
}

在插入里面它会先去检查父元素是否支持子元素，如果不支持，则直接返回，就像video标签不支持子元素。然后再去调具体的插入：

1
2
3
4
5
6
7
8
9
10
void ContainerNode::appendChildCommon(Node& child) {
  child.setParentOrShadowHostNode(this);
  if (m_lastChild) {
    child.setPreviousSibling(m_lastChild);
    m_lastChild->setNextSibling(&child);
  } else {
    setFirstChild(&child);
  }
  setLastChild(&child);
}

上面代码第二行，设置子元素的父结点，也就是会把html结点的父结点指向document，然后如果没有lastChild，会将这个子元素作为firstChild，由于上面已经有一个docype的子结点了，所以已经有lastChild了，因此会把这个子元素的previousSibling指向老的lastChild，老的lastChild的nexSibling指向它。最后倒数第二行再把子元素设置为当前ContainerNode（即document）的lastChild。这样就建立起了html结点的父子兄弟关系。

可以看到，借助上一次的m_lastChild建立起了兄弟关系。

这个时候你可能会有一个问题，为什么要用一个task队列存放将要插入的结点呢，而不是直接插入呢？一个原因是放到task里面方便统一处理，并且有些task可能不能立即执行，要先存起来。不过在我们这个案例里面都是存完后下一步就执行了。

当遇到head标签的token时，也是先创建一个head结点，然后再创建一个task，插到队列里面：

1
2
3
4
5
void HTMLConstructionSite::insertHTMLHeadElement(AtomicHTMLToken* token) {
  m_head = HTMLStackItem::create(createHTMLElement(token), token);
  attachLater(currentNode(), m_head->element());
  m_openElements.pushHTMLHeadElement(m_head);
}

attachLater传参的第一个参数为父结点，这个currentNode为开标签栈里面的最顶的元素：

1
2
3
ContainerNode* currentNode() const {
    return m_openElements.topNode();
}

我们刚刚把html元素压了进去，则栈顶元素为html元素，所以head的父结点就为html。所以每当遇到一个开标签时，就把它压起来，下一次再遇到一个开标签时，它的父元素就是上一个开标签。

所以，初步可以看到，借助一个栈建立起了父子关系。

处理闭标签

当遇到一个闭标签时，会把栈里面的元素一直pop出来，直到pop到第一个和它标签名字一样的：

1
m_tree.openElements()->popUntilPopped(token->name());

我们第一个遇到的是闭标签是head标签，它会把开的head标签pop出来，栈里面就剩下html元素了，所以当再遇到body时，html元素就是body的父元素了。

这个是栈的一个典型应用。

以下面的html为例来研究压栈和出栈的过程：

1
2
3
4
5
6
7
8
9
10
11
12
<!DOCTYPE html>
<html>
<head>
    <meta charset="utf-8"></meta>
</head>
<body>
    <div>
        <p><b>hello</b></p>
        <p>demo</p>
    </div>
</body>
</html>

把push和pop打印出来是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
push "HTML" m_stackDepth = 1
push "HEAD" m_stackDepth = 2
pop "HEAD" m_stackDepth = 1
push "BODY" m_stackDepth = 2
push "DIV" m_stackDepth = 3
push "P" m_stackDepth = 4
push "B" m_stackDepth = 5
pop "B" m_stackDepth = 4
pop "P" m_stackDepth = 3
push "P" m_stackDepth = 4
pop "P" m_stackDepth = 3
pop "DIV" m_stackDepth = 2
"tagName: body  |type: EndTag    |attr:              |text: "
"tagName: html  |type: EndTag    |attr:              |text: "

这个过程确实和上面的描述一致，遇到一个闭标签就把一次的开标签pop出来。

并且可以发现遇到body闭标签后，并不会把body给pop出来，因为如果body闭标签后面又再写了标签的话，就会自动当成body的子元素。

假设上面的b标签的闭标签忘记写了，又会发生什么：

1
<p><b>hello</p>

打印出来的结果是这样的：

1
2
3
4
5
6
7
8
9
10
11
push "P" m_stackDepth = 4
push "B" m_stackDepth = 5
"tagName: p     |type: EndTag    |attr:              |text: "
pop "B" m_stackDepth = 4
pop "P" m_stackDepth = 3
push "B" m_stackDepth = 4
push "P" m_stackDepth = 5
pop "P" m_stackDepth = 4
pop "B" m_stackDepth = 3
pop "DIV" m_stackDepth = 2
push "B" m_stackDepth = 3

同样地，在上面第3行，遇到P闭标签时，会把所有的开标签pop出来，直到遇到P标签。不同的是后续的过程中会不断地插入b标签，最后渲染的页面结构： image

因为b等带有格式化的标签会特殊处理，遇到一个开标签时会它们放到一个列表里面：

1
2
// a, b, big, code, em, font, i, nobr, s, small, strike, strong, tt, and u.
  m_activeFormattingElements.append(currentElementRecord()->stackItem());

遇到一个闭标签时，又会从这个列表里面删掉。每处理一个新标签时就会进行检查和这个列表和栈里的开标签是否对应，如果不对应则会reconstruct：重新插入一个开标签。因此b就不断地被重新插入，直到遇到下一个b的闭标签为止。

如果上面少写的是一个span，那么渲染之后的结果是正常的： image

自定义标签的处理

在浏览器里面可以看到，自定义标签默认不会有任何的样式，并且它默认是一个行内元素： image 初步观察它和span标签的表现是一样的： image 在blink的源码里面，不认识的标签默认会被实例化成一个HTMLUnknownElement，这个类对外提供了一个create函数，这和HTMLSpanElement是一样的，只有一个create函数，并且大家都是继承于HTMLElement。并且创建span标签的时候和unknown一样，并没有做特殊处理，直接调的create。所以从本质上来说，可以把自定义的标签当作一个span看待。然后你可以再设置display: block改成块级元素之类的。

但是你可以用js定义一个自定义标签，定义它的属性等，Webkit会去读它的定义：

1
2
3
4
// "4\. Let definition be the result of looking up a custom element ..." etc.
CustomElementDefinition* definition =
    m_isParsingFragment ? nullptr
                        : lookUpCustomElementDefinition(document, token);

例如给自定义标签创建一个原生属性：

1
<high-school country="China">NO. 2 high school</high-school>

上面定义了一个country，为了可以直接获取这个属性：

1
console.log(document.getElementsByTagName("high-school")[0].country);

注册一个自定义标签：

1
window.customElements.define("high-school", HighSchoolElement);

这个HighSchoolElement继承于HTMLElement：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class HighSchoolElement extends HTMLElement{
    constructor(){
        super();
        this._country = null;
    }
    get country(){
        return this._country;
    }
    set country(country){
        this.setAttribute("country", _country);
    }
    static get observedAttributes() {
        return ["country"];
    }
    attributeChangedCallback(name, oldValue, newValue) {
        this._country = newValue;
        this._updateRender(name, oldValue, newValue);
    }
    _updateRender(name, oldValue, newValue){
        console.log(name + " change from " + oldValue + " " + newValue);
    }
}

就可以直接取到contry这个属性，而不用通过getAttribute的函数，并且可以在属性发生变化时更新元素的渲染，改变color等。

通过这种方式创建的，它就不是一个HTMLUnknownElement了。blink通过V8引擎把js的构造函数转化成C++的函数，实例化一个HTMLElement的对象。

查DOM过程

按ID查找

在页面添加一个script：

1
<script>document.getElementById("text")</script>

Chrome的V8引擎把js代码层层转化，最后会调：

1
DocumentV8Internal::getElementByIdMethodForMainWorld(info);

而这个函数又会调TreeScope的getElementById的函数，TreeScope存储了一个m_map的哈希map，这个map以标签id字符串作为key值，Element为value值，我们可以把这个map打印出来：

1
2
3
4
5
Map::iterator it = m_map.begin();
while(it != m_map.end()){
    LOG(INFO) << it->key << " " << it->value->element->tagName();
    ++it;
}

html结构是这样的：

1
2
3
4
5
<div class="user" id="id-yin">
    <p id="id-name" class="important">yin</p>
    <p id="id-age">20</p>
    <p id="id-sex">mail</p>
</div>

打印出来的结果为：

1
2
3
4
"id-age" "P"
"id-sex" "P"
"id-name" "P"
"id-yin" "DIV"

可以看到， 这个m_map把页面所有有id的标签都存了进来。由于map的查找时间复杂度为O(1)，所以使用ID选择器可以说是最快的。

类选择器

js如下：

1
2
var users = document.getElementsByClassName("user");
users.length;

在执行第一行的时候，Webkit返回了一个ClassCollection的列表：

1
return new ClassCollection(rootNode, classNames);

而这个列表并不是去查DOM获取的，它只是记录了className作为标志。这与我们的认知是一致的，这种HTMLCollection的数据结构都是在使用的时候才去查DOM，所以在上面第二行去获取它的length，就会触发它的查DOM，在nodeCount这个函数里面执行：

1
2
3
4
5
6
7
NodeType* currentNode = collection.traverseToFirst();
unsigned currentIndex = 0;
while (currentNode) {
  m_cachedList.push_back(currentNode);
  currentNode = collection.traverseForwardToOffset(
      currentIndex + 1, *currentNode, currentIndex);
}

第一行先获取符合collection条件的第一个结点，然后不断获取下一个符合条件的结点，直到null，并把它存到一个cachedList里面，下次再获取这个collection的东西时便不用再重复查DOM，只要cached仍然是有效的：

1
2
if (this->isCachedNodeCountValid())
  return this->cachedNodeCount();

怎么样找到有效的节点呢：

1
2
3
4
ElementType* element = Traversal<ElementType>::firstWithin(current);
while (element && !isMatch(*element))
  element = Traversal<ElementType>::next(*element, &current, isMatch);
return element;

第一行先获取第一个节点，如果它没有match，则继续next，直到找到符合条件或者空为止。我们的重点在于，它是怎么遍历的，如何next获取下一个节点，核心代码：

1
2
3
4
5
6
7
if (current.hasChildren())
  return current.firstChild();
if (current == stayWithin)
  return 0;
if (current.nextSibling())
  return current.nextSibling();
return nextAncestorSibling(current, stayWithin);

第一行先判断当前节点有没有子元素，如果有的话返回它的第一个子元素，如果当前节点没有子元素，并且这个节点就是开始找的根元素（用document.getElement*，则为document），则说明没有下一个元素了，直接返回0/null。如果这个节点不是根元素了（例如已经到了子元素这一层），那么看它有没有相邻元素，如果有则返回下一个相邻元素，如果相邻无素也没有了，由于它是一个叶子结点（没有子元素），说明它已经到了最深的一层，并且是当前层的最后一个叶子结点，那么就返回它的父元素的下一个相邻节点，如果这个也没有了，则返回null，查找结束。可以看出这是一个 深度优先的查找。

querySelector

先来看下selector为一个id时发生了什么：

1
document.querySelector("#id-name");

它会调ContainerNode的querySelecotr函数：

1
2
3
4
SelectorQuery* selectorQuery = document().selectorQueryCache().add(
      selectors, document(), exceptionState);
return selectorQuery->queryFirst(*this);

先把输入的selector字符串序列化成一个selectorQuery，然后再queryFirst，通过打断点可以发现，它最后会调的TreeScope的getElementById：

1
rootNode.treeScope().getElementById(idToMatch);

如果selector为一个class：

1
document.querySelector(".user");

它会从document开始遍历：

1
2
3
4
5
6
7
for (Element& element : ElementTraversal::descendantsOf(rootNode)) {
  if (element.hasClass() && element.classNames().contains(className)) {
    SelectorQueryTrait::appendElement(output, element);
    if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
      return;
  }
}

我们重点查看它是怎么遍历，即第一行的for循环。表面上看它好像把所有的元素取出来然后做个循环，其实不然，它是重载++操作符：

1
void operator++() { m_current = TraversalNext::next(*m_current, m_root); }

只要我们看下next是怎么操作的就可以得知它是怎么遍历，而这个next跟上面的讲解class时是调的同一个next。不一样的是match条件判断是：有className，并且className列表里面包含这个class，如上面代码第二行。

复杂选择器

例如写两个class：

1
document.querySelector(".user .important");

最终也会转成一个遍历，只是判断是否match的条件不一样：

1
2
3
4
5
6
7
for (Element& element : ElementTraversal::descendantsOf(*traverseRoot)) {
  if (selectorMatches(selector, element, rootNode)) {
    SelectorQueryTrait::appendElement(output, element);
    if (SelectorQueryTrait::shouldOnlyMatchFirstElement)
      return;
  }
}

怎么判断是否match比较复杂，这里不再展开讨论。

同时在源码可以看到，如果是怪异模式，会调一个executeSlow的查询，并且判断match条件也不一样。不过遍历是一样的。

查看源码确实是一件很费时费力的工作，但是通过一番探索，能够了解浏览器的一些内在机制，至少已经可以回答上面提出来的几个问题。同时知道了Webkit/Blink借助一个栈，结合开闭标签，一步步构建DOM树，并对DOCType的标签、自定义标签的处理有了一定的了解。最后又讨论了查DOM的几种情况，明白了查找的过程。

通过上面的分析，对页面渲染的第一步构建DOM应该会有一个基础的了解。