WebKit Inside: DOM树的构建

当客户端App主进程创建WKWebView对象时,会创建另外两个子进程:渲染进程与网络进程。主进程WKWebView发起请求时,先将请求转发给渲染进程,渲染进程再转发给网络进程,网络进程请求服务器。如果请求的是一个网页,网络进程会将服务器的响应数据HTML文件字符流吐给渲染进程。渲染进程拿到HTML文件字符流,首先要进行解析,将HTML文件字符流转换成DOM树,然后在DOM树的基础上,进行渲染操作,也就是布局、绘制。最后渲染进程将渲染数据吐给主进程WKWebView,WKWebView根据渲染数据创建对应的View展现视图。整个流程如下图所示:

 

什么是DOM树

渲染进程获取到HTML文件字符流,会将HTML文件字符流转换成DOM树。下图中左侧是一个HTML文件,右边就是转换而成的DOM树。

 

可以看到DOM树的根节点是HTMLDocument,代表整个文档。根节点下面的子节点与HTML文件中的标签是一一对应的,比如HTML中的<head>标签就对应DOM树中的head节点。同时HTML文件中的文本,也成为DOM树中的一个节点,比如文本’Hello, World!’,在DOM树中就成为div节点的子节点。

在DOM树中每一个节点都是具有一定方法与属性的对象,这些对象由对应的类创建出来。比如HTMLDocument节点,它对应的类是class HTMLDocument,下面是HTMLDocument的部分源码:

1 class HTMLDocument : public Document { // 继承自Document
2    ...
3     WEBCORE_EXPORT int width();
4     WEBCORE_EXPORT int height();
5     ...
6  }

从源码中可以看到,HTMLDocument继承自类Document,Document类的部分源码如下:

 1 class Document
 2     : public ContainerNode  // Document继承自ContainerNode,ContainerNode继承自Node
 3     , public TreeScope
 4     , public ScriptExecutionContext
 5     , public FontSelectorClient
 6     , public FrameDestructionObserver
 7     , public Supplementable<Document>
 8     , public Logger::Observer
 9     , public CanvasObserver {
10     WEBCORE_EXPORT ExceptionOr<Ref<Element>> createElementForBindings(const AtomString& tagName);  // 创建Element的方法
11     WEBCORE_EXPORT Ref<Text> createTextNode(const String& data); // 创建文本节点的方法
12     WEBCORE_EXPORT Ref<Comment> createComment(const String& data); // 创建注释的方法
13     WEBCORE_EXPORT Ref<Element> createElement(const QualifiedName&, bool createdByParser); // 创建Element方法
14     ....
15  }

上面源码可以看到Document继承自Node,而且还可以看到前端十分熟悉的createElement、createTextNode等方法,JavaScript对这些方法的调用,最后都转换为对应C++方法的调用。

类Document有这些方法,并不是没有原因的,而是W3C组织给出的标准规定的,这个标准就是DOM(Document Object Model,文档对象模型)。DOM定义了DOM树中每个节点需要实现的接口和属性,下面是HTMLDocument、Document、HTMLDivElment的部分IDL(Interactive Data Language,接口描述语言,与具体平台和语言无关)描述,完整的IDL可以参看W3C

 1 interface HTMLDocument : Document {   // HTMLDocument 
 2     getter (WindowProxy or Element or HTMLCollection) (DOMString name);
 3 };
 4 
 5 
 6 interface Document : Node { // Document
 7    [NewObject, ImplementedAs=createElementForBindings] Element createElement(DOMString localName); // createElement
 8    [NewObject] Text createTextNode(DOMString data); // createTextNode
 9    ...
10  }
11  
12  
13  interface HTMLDivElement : HTMLElement { // HTMLDivElement
14     [CEReactions=NotNeeded, Reflect] attribute DOMString align;
15 };

在DOM树中,每一个节点都继承自类Node,同时Node还有一个子类Element,有的节点直接继承自类Node,比如文本节点,而有的节点继承自类Element,比如div节点。因此针对上面图中的DOM树,执行下面的JavaScript语句返回的结果是不一样的:

1 document.childNodes; // 返回子Node集合,返回DocumentType与HTML节点,都继承自Node
2 document.children; // 返回子Element集合,只返回HTML节点,DocumentType不继承自Element

下图给出部分节点的继承关系图:

 

 

DOM树的构建

DOM树的构建流程可以分位4个步骤: 解码、分词、创建节点、添加节点

1 解码

渲染进程从网络进程接收过来的是HTML字节流,而下一步分词是以字符为单位进行的。由于各种编码规范的存在,比如ISO-8859-1、UTF-8等,一个字符常常可能对应一个或者多个编码后的字节,解码的目的就是将HTML字节流转换成HTML字符流,或者换句话说,就是将原始的HTML字节流转换成字符串。

2 解码类图

从类图上看,类HTMLDocumentParser处于解码的核心位置,由这个类调用解码器将HTML字节流解码成字符流,存储到类HTMLInputStream中。

3 解码流程

整个解码流程当中,最关健的是如何找到正确的编码方式。只有找到了正确的编码方式,才能使用对应的解码器进行解码。解码发生的地方如下面源代码所示,这个方法在上图第3个栈帧被调用:

 1 // HTMLDocumentParser是DecodedDataDocumentParser的子类
 2 void DecodedDataDocumentParser::appendBytes(DocumentWriter& writer, const uint8_t* data, size_t length)
 3 {
 4     if (!length)
 5         return;
 6 
 7     String decoded = writer.decoder().decode(data, length); // 真正解码发生在这里
 8     if (decoded.isEmpty())
 9         return;
10 
11     writer.reportDataReceived();
12     append(decoded.releaseImpl());
13 }

上面代码第7行writer.decoder()返回一个TextResourceDecoder对象,解码操作由TextResourceDecoder::decode方法完成。下面逐步查看TextResourceDecoder::decode方法的源码:

 1 // 只保留了最重要的部分
 2  2 String TextResourceDecoder::decode(const char* data, size_t length)
 3  3 {
 4  4    ...
 5  5 
 6  6    // 如果是HTML文件,就从head标签中寻找字符集
 7  7     if ((m_contentType == HTML || m_contentType == XML) && !m_checkedForHeadCharset) // HTML and XML
 8  8         if (!checkForHeadCharset(data, length, movedDataToBuffer))
 9  9             return emptyString();
10 10     
11 11      ...
12 12    
13 13     // m_encoding存储者从HTML文件中找到的编码名称
14 14     if (!m_codec)
15 15         m_codec = newTextCodec(m_encoding);  // 创建具体的编码器
16 16 
17 17     ...
18 18 
19 19    // 解码并返回
20 20    String result = m_codec->decode(m_buffer.data() + lengthOfBOM, m_buffer.size() - lengthOfBOM, false, m_contentType == XML && !m_useLenientXMLDecoding, m_sawError);
21 21     m_buffer.clear(); // 清空存储的原始未解码的HTML字节流
22 22     return result;
23 23 }

从源码中可以看到,TextResourceDecoder首先从HTML的<head>标签中去找编码方式,因为<head>标签可以包含<meta>标签,<meta>标签可以设置HTML文件的字符集:

1 <head>
2         <meta http-equiv="Content-Type" content="text/html; charset=utf-8" /> <!-- 字符集指定-->
3         <title>DOM Tree</title>
4         <script>window.name = 'Lucy';</script>
5  </head>

如果能找到对应的字符集,TextResourceDeocder将其存储在成员变量m_encoding当中,并且根据对应的编码创建真正的解码器存储在成员变量m_codec中,最终使用m_codec对字节流进行解码,并且返回解码后的字符串。如果带有字符集的<meta>标签没有找到,TextResourceDeocder的m_encoding有默认值windows-1252(等同于ISO-8859-1)。

下面看一下TextResourceDecoder寻找<meta>标签中字符集的流程,也就是上面源码中第8行对checkForHeadCharset函数的调用:

 1 // 只保留了关健代码
 2 bool TextResourceDecoder::checkForHeadCharset(const char* data, size_t len, bool& movedDataToBuffer)
 3 {
 4     ...
 5 
 6     // This is not completely efficient, since the function might go
 7     // through the HTML head several times.
 8 
 9     size_t oldSize = m_buffer.size();
10     m_buffer.grow(oldSize + len);
11     memcpy(m_buffer.data() + oldSize, data, len); // 将字节流数据拷贝到自己的缓存m_buffer里面
12 
13     movedDataToBuffer = true;
14 
15     // Continue with checking for an HTML meta tag if we were already doing so.
16     if (m_charsetParser)
17         return checkForMetaCharset(data, len);  // 如果已经存在了meta标签解析器,直接开始解析
18    
19      ....
20 
21     m_charsetParser = makeUnique<HTMLMetaCharsetParser>(); // 创建meta标签解析器
22     return checkForMetaCharset(data, len);
23 }

上面源代码中第11行,类TextResourceDecoder内部存储了需要解码的HTML字节流,这一步骤很重要,后面会讲到。先看第17行、21行、22行,这3行主要是使用<meta>标签解析器解析字符集,使用了懒加载的方式。下面看下checkForMetaCharset这个函数的实现:

 1 bool TextResourceDecoder::checkForMetaCharset(const char* data, size_t length)
 2 {
 3     if (!m_charsetParser->checkForMetaCharset(data, length))  // 解析meta标签字符集
 4         return false;
 5 
 6     setEncoding(m_charsetParser->encoding(), EncodingFromMetaTag); // 找到后设置字符编码名称
 7     m_charsetParser = nullptr;
 8     m_checkedForHeadCharset = true;
 9     return true;
10 }

上面源码第3行可以看到,整个解析<meta>标签的任务在类HTMLMetaCharsetParser::checkForMetaCharset中完成。

 1 // 只保留了关健代码
 2 bool HTMLMetaCharsetParser::checkForMetaCharset(const char* data, size_t length)
 3 {
 4     if (m_doneChecking) // 标志位,避免重复解析
 5         return true;
 6 
 7 
 8     // We still don't have an encoding, and are in the head.
 9     // The following tags are allowed in <head>:
10     // SCRIPT|STYLE|META|LINK|OBJECT|TITLE|BASE
11     //
12     // We stop scanning when a tag that is not permitted in <head>
13     // is seen, rather when </head> is seen, because that more closely
14     // matches behavior in other browsers; more details in
15     // <//bugs.webkit.org/show_bug.cgi?id=3590>.
16     //
17     // Additionally, we ignore things that looks like tags in <title>, <script>
18     // and <noscript>; see <//bugs.webkit.org/show_bug.cgi?id=4560>,
19     // <//bugs.webkit.org/show_bug.cgi?id=12165> and
20     // <//bugs.webkit.org/show_bug.cgi?id=12389>.
21     //
22     // Since many sites have charset declarations after <body> or other tags
23     // that are disallowed in <head>, we don't bail out until we've checked at
24     // least bytesToCheckUnconditionally bytes of input.
25 
26     constexpr int bytesToCheckUnconditionally = 1024;  // 如果解析了1024个字符还未找到带有字符集的<meta>标签,整个解析也算完成,此时没有解析到正确的字符集,就使用默认编码windows-1252(等同于ISO-8859-1)
27 
28     bool ignoredSawErrorFlag;
29     m_input.append(m_codec->decode(data, length, false, false, ignoredSawErrorFlag)); // 对字节流进行解码
30 
31     while (auto token = m_tokenizer.nextToken(m_input)) { // m_tokenizer进行分词操作,找meta标签也需要进行分词,分词操作后面讲
32         bool isEnd = token->type() == HTMLToken::EndTag;
33         if (isEnd || token->type() == HTMLToken::StartTag) {
34             AtomString tagName(token->name());
35             if (!isEnd) {
36                 m_tokenizer.updateStateFor(tagName);
37                 if (tagName == metaTag && processMeta(*token)) { // 找到meta标签进行处理
38                     m_doneChecking = true;
39                     return true; // 如果找到了带有编码的meta标签,直接返回
40                 }
41             }
42 
43             if (tagName != scriptTag && tagName != noscriptTag
44                 && tagName != styleTag && tagName != linkTag
45                 && tagName != metaTag && tagName != objectTag
46                 && tagName != titleTag && tagName != baseTag
47                 && (isEnd || tagName != htmlTag)
48                 && (isEnd || tagName != headTag)) {
49                 m_inHeadSection = false;
50             }
51         }
52 
53         if (!m_inHeadSection && m_input.numberOfCharactersConsumed() >= bytesToCheckUnconditionally) { // 如果分词已经进入了<body>标签范围,同时分词数量已经超过了1024,也算成功
54             m_doneChecking = true;
55             return true;
56         }
57     }
58 
59     return false;
60 }

上面源码第29行,类HTMLMetaCharsetParser也有一个解码器m_codec,解码器是在HTMLMetaCharsetParser对象创建时生成,这个解码器的真实类型是TextCodecLatin1(Latin1编码也就是ISO-8859-1,等同于windows-1252编码)。之所以可以直接使用TextCodecLatin1解码器,是因为<meta>标签如果设置正确,都是英文字符,完全可以使用TextCodecLatin1进行解析出来。这样就避免了为了找到<meta>标签,需要对字节流进行解码,而要解码就必须要找到<meta>标签这种鸡生蛋、蛋生鸡的问题。

代码第37行对找到的<meta>标签进行处理,这个函数比较简单,主要是解析<meta>标签当中的属性,然后查看这些属性名中有没有charset。

 1 bool HTMLMetaCharsetParser::processMeta(HTMLToken& token)
 2 {
 3     AttributeList attributes;
 4     for (auto& attribute : token.attributes()) { // 获取meta标签属性
 5         String attributeName = StringImpl::create8BitIfPossible(attribute.name);
 6         String attributeValue = StringImpl::create8BitIfPossible(attribute.value);
 7         attributes.append(std::make_pair(attributeName, attributeValue));
 8     }
 9 
10     m_encoding = encodingFromMetaAttributes(attributes); // 从属性中找字符集设置属性charset
11     return m_encoding.isValid();
12 }

上面分析TextResourceDecoder::checkForHeadCharset函数时,讲过第11行TextResourceDecoder类存储HTML字节流的操作很重要。原因是可能整个HTML字节流里面可能确实没有设置charset的<meta>标签,此时TextResourceDecoder::checkForHeadCharset函数就要返回false,导致TextResourceDecoder::decode函数返回空字符串,也就是不进行任何解码。是不是这样呢?真实的情况是,在接收HTML字节流整个过程中由于确实没有找到带有charset属性的<meta>标签,那么整个接收期间都不会解码。但是完整的HTML字节流会被存储在TextResourceDecoder的成员变量m_buffer里面,当整个HTML字节流接收结束的时,会有如下调用栈:

 从调用栈可以看到,当HTML字节流接收完成,最终会调用TextResourceDecoder::flush方法,这个方法会将TextResourceDecoder中有m_buffer存储的HTML字节流进行解码,由于在接收HTML字节流期间未成功找到编码方式,因此m_buffer里面存储的就是所有待解码的HTML字节流,然后在这里使用默认的编码windows-1252对全部字节流进行解码。因此,如果HTML字节流中包含汉字,那么如果不指定字符集,最终页面就会出现乱码。解码完成后,会将解码之后的字符流存储到HTMLDocumentParser中。

1 void DecodedDataDocumentParser::flush(DocumentWriter& writer)
2 {
3     String remainingData = writer.decoder().flush();
4     if (remainingData.isEmpty())
5         return;
6 
7     writer.reportDataReceived();
8     append(remainingData.releaseImpl()); // 解码后的字符流存储到HTMLDocumentParser
9 }

 

4 解码总结

整个解码过程可以分位两种情形: 第一种情形是HTML字节流可以解析出带有charset属性的<meta>标签,这样就可以获取相应的编码方式,那么每接收到一个HML字节流,都可以使用相应的编码方式进行解码,将解码后的字符流添加到HTMLInputStream当中;第二种是HTML字节流不能解析带有charset属性的<meta>标签,这样每接收到一个HTML字节流,都缓存到TextResourceDecoder的m_buffer缓存,等完整的HTML字节流接收完毕,就会使用默认的编码windows-1252进行解码。

 

分词

接收到的HTML字节流经过解码,成为存储在HTMLInputStream中的字符流。分词的过程就是从HTMLInputStream中依次取出每一个字符,然后判断字符是否是特殊的HTML字符'<‘、’/’、’>’、’=’等。根据这些特殊字符的分割,就能解析出HTML标签名以及属性列表,类HTMLToken就是存储分词出来的结果。

1 分词类图

从类图中可以看到,分词最重要的是类HTMLTokenizer和类HTMLToken。下面是类HTMLToken的主要信息:

 1 // 只保留了主要信息
 2  2 class HTMLToken {
 3  3 public:
 4  4     enum Type { // Token的类型
 5  5         Uninitialized, // Token初始化时的类型
 6  6         DOCTYPE, // 代表Token是DOCType标签
 7  7         StartTag, // 代表Token是一个开始标签
 8  8         EndTag, // 代表Token是一个结束标签
 9  9         Comment, // 代表Token是一个注释
10 10         Character, // 代表Token是文本
11 11         EndOfFile, // 代表Token是文件结尾
12 12     };
13 13 
14 14     struct Attribute { // 存储属性的数据结构
15 15         Vector<UChar, 32> name; // 属性名
16 16         Vector<UChar, 64> value; // 属性值
17 17 
18 18         // Used by HTMLSourceTracker.
19 19         unsigned startOffset;
20 20         unsigned endOffset;
21 21     };
22 22 
23 23     typedef Vector<Attribute, 10> AttributeList; // 属性列表
24 24     typedef Vector<UChar, 256> DataVector; // 存储Token名
25 25 
26 26  ...
27 27 
28 28 private:
29 29     Type m_type;
30 30     DataVector m_data;
31 31     // For StartTag and EndTag
32 32     bool m_selfClosing; // Token是注入<img>一样自结束标签
33 33     AttributeList m_attributes;
34 34     Attribute* m_currentAttribute; // 当前正在解析的属性
35 35 };

 

2 分词流程

 

上面分词流程中HTMLDocumentParser::pumpTokenizerLoop方法是最重要的,从方法名字可以看出这个方法里面包含循环逻辑:

 1 // 只保留关健代码
 2 bool HTMLDocumentParser::pumpTokenizerLoop(SynchronousMode mode, bool parsingFragment, PumpSession& session)
 3 {
 4     do { // 分词循环体开始
 5         ...
 6 
 7         if (UNLIKELY(mode == AllowYield && m_parserScheduler->shouldYieldBeforeToken(session))) // 避免长时间处于分词循环中,这里根据条件暂时退出循环
 8             return true;
 9 
10         if (!parsingFragment)
11             m_sourceTracker.startToken(m_input.current(), m_tokenizer);
12 
13         auto token = m_tokenizer.nextToken(m_input.current()); // 进行分词操作,取出一个token
14         if (!token)
15             return false; // 分词没有产生token,就跳出循环
16 
17         if (!parsingFragment)
18             m_sourceTracker.endToken(m_input.current(), m_tokenizer);
19 
20         constructTreeFromHTMLToken(token); // 根据token构建DOM树
21     } while (!isStopped()); 
22 
23     return false;
24 }

上面代码中第7行会有一个yield退出操作,这是为了避免长时间处于分词循环,占用主线程。当退出条件为真时,会从分词循环中返回,返回值为true。下面是退出判断代码:

 1 // 只保留关健代码
 2 bool HTMLParserScheduler::shouldYieldBeforeToken(PumpSession& session)
 3     {
 4         ...
 5 
 6         // numberOfTokensBeforeCheckingForYield是静态变量,定义为4096
 7         // session.processedTokensOnLastCheck表示从上一次退出为止,以及处理过的token个数
 8         // session.didSeeScript表示在分词过程中是否出现过script标签
 9         if (UNLIKELY(session.processedTokens > session.processedTokensOnLastCheck + numberOfTokensBeforeCheckingForYield || session.didSeeScript))
10             return checkForYield(session);
11 
12         ++session.processedTokens;
13         return false;
14     }
15 
16 
17     bool HTMLParserScheduler::checkForYield(PumpSession& session)
18     {
19         session.processedTokensOnLastCheck = session.processedTokens;
20         session.didSeeScript = false;
21 
22         Seconds elapsedTime = MonotonicTime::now() - session.startTime;
23         return elapsedTime > m_parserTimeLimit; // m_parserTimeLimit的值默认是500ms,从分词开始超过500ms就要先yield
24     }

如果命中了上面的yield退出条件,那么什么时候再次进入分词呢?下面的代码展示了再次进入分词的过程:

 1 // 保留关键代码

2 void HTMLDocumentParser::pumpTokenizer(SynchronousMode mode) 3 { 4 ... 5 6 if (shouldResume) // 从pumpTokenizerLoop中yield退出时返回值为true 7 m_parserScheduler->scheduleForResume(); 8 9 } 10 11 12 13 void HTMLParserScheduler::scheduleForResume() 14 { 15 ASSERT(!m_suspended); 16 m_continueNextChunkTimer.startOneShot(0_s); // 触发timer(0s后触发),触发后的响应函数为HTMLParserScheduler::continueNextChunkTimerFired 17 } 18 19 20 // 保留关健代码 21 void HTMLParserScheduler::continueNextChunkTimerFired() 22 { 23 ... 24 25 m_parser.resumeParsingAfterYield(); // 重新Resume分词过程 26 } 27 28 29 void HTMLDocumentParser::resumeParsingAfterYield() 30 { 31 // pumpTokenizer can cause this parser to be detached from the Document, 32 // but we need to ensure it isn't deleted yet. 33 Ref<HTMLDocumentParser> protectedThis(*this); 34 35 // We should never be here unless we can pump immediately. 36 // Call pumpTokenizer() directly so that ASSERTS will fire if we're wrong. 37 pumpTokenizer(AllowYield); // 重新进入分词过程,该函数会调用pumpTokenizerLoop 38 endIfDelayed(); 39 }

从上面代码可以看出,再次进入分词过程是通过触发一个Timer来实现的,虽然这个Timer在0s后触发,但是并不意味着Timer的响应函数会立刻执行。如果在此之前主线程已经有其他任务到达了执行时机,会有被执行的机会。

继续看HTMLDocumentParser::pumpTokenizerLoop函数的第13行,这一行进行分词操作,从解码后的字符流中分出一个token。实现分词的代码位于HTMLTokenizer::processToken:

 1 // 只保留关键代码
 2 bool HTMLTokenizer::processToken(SegmentedString& source)
 3 {
 4    
 5     ...
 6 
 7     if (!m_preprocessor.peek(source, isNullCharacterSkippingState(m_state))) // 取出source内部指向的字符,赋给m_nextInputCharacter
 8         return haveBufferedCharacterToken();
 9     UChar character = m_preprocessor.nextInputCharacter(); // 获取character
10 
11     // //html.spec.whatwg.org/#tokenization
12     switch (m_state) { // 进行状态转换,m_state初始值为DataState
13     ...
14     }
15 
16     return false;
17 }

这个方法由于内部要做很多状态转换,总共有1200多行,后面会有4个例子来解释状态转换的逻辑。

首先来看InputStreamPreprocessor::peek方法:

 1  // Returns whether we succeeded in peeking at the next character.
 2  // The only way we can fail to peek is if there are no more
 3  // characters in |source| (after collapsing \r\n, etc).
 4  ALWAYS_INLINE bool InputStreamPreprocessor::peek(SegmentedString& source, bool skipNullCharacters = false)
 5  {
 6      if (UNLIKELY(source.isEmpty()))
 7          return false;
 8  
 9      m_nextInputCharacter = source.currentCharacter(); // 获取字符流source内部指向的当前字符
10  
11      // Every branch in this function is expensive, so we have a
12      // fast-reject branch for characters that don't require special
13      // handling. Please run the parser benchmark whenever you touch
14      // this function. It's very hot.
15      constexpr UChar specialCharacterMask = '\n' | '\r' | '\0';
16      if (LIKELY(m_nextInputCharacter & ~specialCharacterMask)) {
17          m_skipNextNewLine = false;
18          return true;
19      }
20  
21      return processNextInputCharacter(source, skipNullCharacters); // 跳过空字符,将\r\n换行符合并成\n
22  }
23 
24 
25 bool InputStreamPreprocessor::processNextInputCharacter(SegmentedString& source, bool skipNullCharacters)
26     {
27     ProcessAgain:
28         ASSERT(m_nextInputCharacter == source.currentCharacter());
29 
30         // 针对\r\n换行符,下面if语句处理\r字符并且设置m_skipNextNewLine=true,后面处理\n就直接忽略
31         if (m_nextInputCharacter == '\n' && m_skipNextNewLine) {
32             m_skipNextNewLine = false;
33             source.advancePastNewline(); // 向前移动字符
34             if (source.isEmpty())
35                 return false;
36             m_nextInputCharacter = source.currentCharacter();
37         }
38 
39         // 如果是\r\n连续的换行符,那么第一次遇到\r字符,将\r字符替换成\n字符,同时设置标志m_skipNextNewLine=true
40         if (m_nextInputCharacter == '\r') { 
41             m_nextInputCharacter = '\n';
42             m_skipNextNewLine = true;
43             return true;
44         }
45         m_skipNextNewLine = false;
46         if (m_nextInputCharacter || isAtEndOfFile(source))
47             return true;
48 
49         // 跳过空字符
50         if (skipNullCharacters && !m_tokenizer.neverSkipNullCharacters()) {
51             source.advancePastNonNewline();
52             if (source.isEmpty())
53                 return false;
54             m_nextInputCharacter = source.currentCharacter();
55             goto ProcessAgain; // 跳转到开头
56         }
57         m_nextInputCharacter = replacementCharacter;
58         return true;
59     }

由于peek方法会跳过空字符,同时合并\r\n字符为\n字符,所以一个字符流source如果包含了空格或者\r\n换行符,实际上处理起来如下图所示:

 

HTMLTokenizer::processToken内部定义了一个状态机,下面以四种情形来进行解释。

第一种 <!DCOTYPE>标签

  1 BEGIN_STATE(DataState) // 刚开始解析是DataState状态
  2         if (character == '&')
  3             ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInDataState);
  4         if (character == '<') {// 整个字符流一开始是'<',那么表示是一个标签的开始
  5             if (haveBufferedCharacterToken())
  6                 RETURN_IN_CURRENT_STATE(true);
  7             ADVANCE_PAST_NON_NEWLINE_TO(TagOpenState); // 跳转到TagOpenState状态,并取去下一个字符是'!"
  8         }
  9         if (character == kEndOfFileMarker)
 10             return emitEndOfFile(source);
 11         bufferCharacter(character);
 12         ADVANCE_TO(DataState);
 13 END_STATE()
 14 
 15 // ADVANCE_PAST_NON_NEWLINE_TO定义
 16 #define ADVANCE_PAST_NON_NEWLINE_TO(newState)                   \
 17     do {                                                        \
 18         if (!m_preprocessor.advancePastNonNewline(source, isNullCharacterSkippingState(newState))) { \ // 如果往下移动取不到下一个字符
 19             m_state = newState;                                 \ // 保存状态
 20             return haveBufferedCharacterToken();                \ // 返回
 21         }                                                       \
 22         character = m_preprocessor.nextInputCharacter();        \ // 先取出下一个字符
 23         goto newState;                                          \ // 跳转到指定状态
 24     } while (false)
 25 
 26 
 27 BEGIN_STATE(TagOpenState)
 28         if (character == '!') // 满足此条件
 29             ADVANCE_PAST_NON_NEWLINE_TO(MarkupDeclarationOpenState); // 同理,跳转到MarkupDeclarationOpenState状态,并且取出下一个字符'D'
 30         if (character == '/')
 31             ADVANCE_PAST_NON_NEWLINE_TO(EndTagOpenState);
 32         if (isASCIIAlpha(character)) {
 33             m_token.beginStartTag(convertASCIIAlphaToLower(character));
 34             ADVANCE_PAST_NON_NEWLINE_TO(TagNameState);
 35         }
 36         if (character == '?') {
 37             parseError();
 38             // The spec consumes the current character before switching
 39             // to the bogus comment state, but it's easier to implement
 40             // if we reconsume the current character.
 41             RECONSUME_IN(BogusCommentState);
 42         }
 43         parseError();
 44         bufferASCIICharacter('<');
 45         RECONSUME_IN(DataState);
 46 END_STATE()
 47 
 48 BEGIN_STATE(MarkupDeclarationOpenState)
 49         if (character == '-') {
 50             auto result = source.advancePast("--");
 51             if (result == SegmentedString::DidMatch) {
 52                 m_token.beginComment();
 53                 SWITCH_TO(CommentStartState);
 54             }
 55             if (result == SegmentedString::NotEnoughCharacters)
 56                 RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken());
 57         } else if (isASCIIAlphaCaselessEqual(character, 'd')) { // 由于character == 'D',满足此条件
 58             auto result = source.advancePastLettersIgnoringASCIICase("doctype"); // 看解码后的字符流中是否有完整的"doctype"
 59             if (result == SegmentedString::DidMatch)
 60                 SWITCH_TO(DOCTYPEState); // 如果匹配,则跳转到DOCTYPEState,同时取出当前指向的字符,由于上面source字符流已经移动了"doctype",因此此时取出的字符为'>'
 61             if (result == SegmentedString::NotEnoughCharacters) // 如果不匹配
 62                 RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken()); // 保存状态,直接返回
 63         } else if (character == '[' && shouldAllowCDATA()) {
 64             auto result = source.advancePast("[CDATA[");
 65             if (result == SegmentedString::DidMatch)
 66                 SWITCH_TO(CDATASectionState);
 67             if (result == SegmentedString::NotEnoughCharacters)
 68                 RETURN_IN_CURRENT_STATE(haveBufferedCharacterToken());
 69         }
 70         parseError();
 71         RECONSUME_IN(BogusCommentState);
 72     END_STATE()
 73 
 74 
 75 #define SWITCH_TO(newState)                                     \
 76     do {                                                        \
 77         if (!m_preprocessor.peek(source, isNullCharacterSkippingState(newState))) { \
 78             m_state = newState;                                 \
 79             return haveBufferedCharacterToken();                \
 80         }                                                       \
 81         character = m_preprocessor.nextInputCharacter();        \ // 取出下一个字符
 82         goto newState;                                          \ // 跳转到指定的state
 83     } while (false)
 84 
 85 
 86 #define RETURN_IN_CURRENT_STATE(expression)                     \
 87     do {                                                        \
 88         m_state = currentState;                                 \ // 保存当前状态
 89         return expression;                                      \
 90     } while (false)
 91 
 92 
 93 BEGIN_STATE(DOCTYPEState)
 94     if (isTokenizerWhitespace(character))
 95         ADVANCE_TO(BeforeDOCTYPENameState);
 96     if (character == kEndOfFileMarker) {
 97         parseError();
 98         m_token.beginDOCTYPE();
 99         m_token.setForceQuirks();
100         return emitAndReconsumeInDataState();
101     }
102     parseError();
103     RECONSUME_IN(BeforeDOCTYPENameState);
104 END_STATE()
105 
106 
107 #define RECONSUME_IN(newState)                                  \
108     do {                                                        \ // 直接跳转到指定state
109         goto newState;                                          \
110     } while (false)
111 
112 
113  BEGIN_STATE(BeforeDOCTYPENameState)
114         if (isTokenizerWhitespace(character))
115             ADVANCE_TO(BeforeDOCTYPENameState);
116         if (character == '>') { // character == '>',匹配此处,到此DOCTYPE标签匹配完毕
117             parseError();
118             m_token.beginDOCTYPE();
119             m_token.setForceQuirks();
120             return emitAndResumeInDataState(source);
121         }
122         if (character == kEndOfFileMarker) {
123             parseError();
124             m_token.beginDOCTYPE();
125             m_token.setForceQuirks();
126             return emitAndReconsumeInDataState();
127         }
128         m_token.beginDOCTYPE(toASCIILower(character));
129         ADVANCE_PAST_NON_NEWLINE_TO(DOCTYPENameState);
130     END_STATE()
131 
132 
133 
134 
135 inline bool HTMLTokenizer::emitAndResumeInDataState(SegmentedString& source)
136 {
137     saveEndTagNameIfNeeded();
138     m_state = DataState; // 重置状态为初始状态DataState
139     source.advancePastNonNewline(); // 移动到下一个字符
140     return true;
141 }

DOCTYPE Token经历了6个状态最终被解析出来,整个过程如下图所示:

当Token解析完毕之后,分词状态又被重置为DataState,同时需要注意的时,此时字符流source内部指向的是下一个字符'<‘。

上面代码第61行在用字符流source匹配字符串”doctype”时,可能出现匹配不上的情形。为什么会这样呢?这是因为整个DOM树的构建流程,并不是先要解码完成,解码完成之后获取到完整的字符流才进行分词。从前面解码可以知道,解码可能是一边接收字节流,一边进行解码的,因此分词也是这样,只要能解码出一段字符流,就会立即进行分词。整个流程会出现如下图所示:

由于这个原因,用来分词的字符流可能是不完整的。对于出现不完整情形的DOCTYPE分词过程如下图所示:

上面介绍了解码、分词、解码、分词处理DOCTYPE标签的情形,可以看到从逻辑上这种情形与完整解码再分词是一样的。后续介绍的时都会只针对完整解码再分词的情形,对于一边解码一边分词的情形,只需要正确的认识source字符流内部指针的移动,并不难分析。

 

第二种 html标签

html标签的分词过程和DOCTYPE类似,其相关代码如下:

 1 BEGIN_STATE(TagOpenState)
 2     if (character == '!')
 3         ADVANCE_PAST_NON_NEWLINE_TO(MarkupDeclarationOpenState);
 4     if (character == '/')
 5         ADVANCE_PAST_NON_NEWLINE_TO(EndTagOpenState);
 6     if (isASCIIAlpha(character)) { // 在开标签状态下,当前字符为'h'
 7         m_token.beginStartTag(convertASCIIAlphaToLower(character)); // 将'h'添加到Token名中
 8         ADVANCE_PAST_NON_NEWLINE_TO(TagNameState); // 跳转到TagNameState,并移动到下一个字符't'
 9     }
10     if (character == '?') {
11         parseError();
12         // The spec consumes the current character before switching
13         // to the bogus comment state, but it's easier to implement
14         // if we reconsume the current character.
15         RECONSUME_IN(BogusCommentState);
16     }
17     parseError();
18     bufferASCIICharacter('<');
19     RECONSUME_IN(DataState);
20 END_STATE()
21 
22 
23 BEGIN_STATE(TagNameState)
24     if (isTokenizerWhitespace(character))
25         ADVANCE_TO(BeforeAttributeNameState);
26     if (character == '/')
27         ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);
28     if (character == '>') // 在这个状态下遇到起始标签终止字符
29         return emitAndResumeInDataState(source); // 当前分词结束,重置分词状态为DataState
30     if (m_options.usePreHTML5ParserQuirks && character == '<')
31         return emitAndReconsumeInDataState();
32     if (character == kEndOfFileMarker) {
33         parseError();
34         RECONSUME_IN(DataState);
35     }
36     m_token.appendToName(toASCIILower(character)); // 将当前字符添加到Token名
37     ADVANCE_PAST_NON_NEWLINE_TO(TagNameState); // 继续跳转到当前状态,并移动到下一个字符
38 END_STATE()

 

 

第三种 带有属性的标签div

HTML标签可以带有属性,属性由属性名和属性值组成,属性之间以及属性与标签名之间用空格分隔:

1  <!-- div标签有两个属性,属性名为class和align,它们的值都带有引号 -->
2  <div class="news" align="center">Hello,World!</div>
3  
4  
5  <!-- 属性值也可以不带引号 -->
6  <div class=news align=center>Hello,World!</div>

整个div标签的解析中,标签名div的解析流程和上面的html标签解析一样,当在解析标签名的过程中,碰到了空白字符,说明要开始解析属性了,下面是相关代码:

  1 BEGIN_STATE(TagNameState)
  2     if (isTokenizerWhitespace(character)) // 在解析TagName时遇到空白字符,标志属性开始
  3         ADVANCE_TO(BeforeAttributeNameState);
  4     if (character == '/')
  5         ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);
  6     if (character == '>')
  7         return emitAndResumeInDataState(source);
  8     if (m_options.usePreHTML5ParserQuirks && character == '<')
  9         return emitAndReconsumeInDataState();
 10     if (character == kEndOfFileMarker) {
 11         parseError();
 12         RECONSUME_IN(DataState);
 13     }
 14     m_token.appendToName(toASCIILower(character));
 15     ADVANCE_PAST_NON_NEWLINE_TO(TagNameState);
 16 END_STATE()
 17 
 18 #define ADVANCE_TO(newState)                                    \
 19     do {                                                        \
 20         if (!m_preprocessor.advance(source, isNullCharacterSkippingState(newState))) { \ // 移动到下一个字符
 21             m_state = newState;                                 \
 22             return haveBufferedCharacterToken();                \
 23         }                                                       \
 24         character = m_preprocessor.nextInputCharacter();        \
 25         goto newState;                                          \ // 跳转到指定状态
 26     } while (false)
 27 
 28 
 29 BEGIN_STATE(BeforeAttributeNameState)
 30     if (isTokenizerWhitespace(character)) // 如果标签名后有连续空格,那么就不停的跳过,在当前状态不停循环
 31         ADVANCE_TO(BeforeAttributeNameState);
 32     if (character == '/')
 33         ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);
 34     if (character == '>')
 35         return emitAndResumeInDataState(source);
 36     if (m_options.usePreHTML5ParserQuirks && character == '<')
 37         return emitAndReconsumeInDataState();
 38     if (character == kEndOfFileMarker) {
 39         parseError();
 40         RECONSUME_IN(DataState);
 41     }
 42     if (character == '"' || character == '\'' || character == '<' || character == '=')
 43         parseError();
 44     m_token.beginAttribute(source.numberOfCharactersConsumed()); // Token的属性列表增加一个,用来存放新的属性名与属性值
 45     m_token.appendToAttributeName(toASCIILower(character)); // 添加属性名
 46     ADVANCE_PAST_NON_NEWLINE_TO(AttributeNameState); // 跳转到AttributeNameState,并且移动到下一个字符
 47 END_STATE()
 48 
 49 
 50 BEGIN_STATE(AttributeNameState)
 51     if (isTokenizerWhitespace(character))
 52         ADVANCE_TO(AfterAttributeNameState);
 53     if (character == '/')
 54         ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);
 55     if (character == '=')
 56         ADVANCE_PAST_NON_NEWLINE_TO(BeforeAttributeValueState); // 在解析属性名的过程中如果碰到=,说明属性名结束,属性值就要开始
 57     if (character == '>')
 58         return emitAndResumeInDataState(source);
 59     if (m_options.usePreHTML5ParserQuirks && character == '<')
 60         return emitAndReconsumeInDataState();
 61     if (character == kEndOfFileMarker) {
 62         parseError();
 63         RECONSUME_IN(DataState);
 64     }
 65     if (character == '"' || character == '\'' || character == '<' || character == '=')
 66         parseError();
 67     m_token.appendToAttributeName(toASCIILower(character));
 68     ADVANCE_PAST_NON_NEWLINE_TO(AttributeNameState);
 69 END_STATE()
 70 
 71 
 72 BEGIN_STATE(BeforeAttributeValueState)
 73     if (isTokenizerWhitespace(character))
 74         ADVANCE_TO(BeforeAttributeValueState);
 75     if (character == '"')
 76         ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueDoubleQuotedState); // 有的属性值有引号包围,这里跳转到AttributeValueDoubleQuotedState,并移动到下一个字符
 77     if (character == '&')
 78         RECONSUME_IN(AttributeValueUnquotedState);
 79     if (character == '\'')
 80         ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueSingleQuotedState);
 81     if (character == '>') {
 82         parseError();
 83         return emitAndResumeInDataState(source);
 84     }
 85     if (character == kEndOfFileMarker) {
 86         parseError();
 87         RECONSUME_IN(DataState);
 88     }
 89     if (character == '<' || character == '=' || character == '`')
 90         parseError();
 91     m_token.appendToAttributeValue(character); // 有的属性值没有引号包围,添加属性值字符到Token
 92     ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueUnquotedState); // 跳转到AttributeValueUnquotedState,并移动到下一个字符
 93 END_STATE()
 94 
 95 BEGIN_STATE(AttributeValueDoubleQuotedState)
 96     if (character == '"') { // 在当前状态下如果遇到引号,说明属性值结束
 97         m_token.endAttribute(source.numberOfCharactersConsumed()); // 结束属性解析
 98         ADVANCE_PAST_NON_NEWLINE_TO(AfterAttributeValueQuotedState); // 跳转到AfterAttributeValueQuotedState,并移动到下一个字符
 99     }
100     if (character == '&') {
101         m_additionalAllowedCharacter = '"';
102         ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInAttributeValueState);
103     }
104     if (character == kEndOfFileMarker) {
105         parseError();
106         m_token.endAttribute(source.numberOfCharactersConsumed());
107         RECONSUME_IN(DataState);
108     }
109     m_token.appendToAttributeValue(character); // 将属性值字符添加到Token
110     ADVANCE_TO(AttributeValueDoubleQuotedState); // 跳转到当前状态
111 END_STATE()
112 
113 
114 BEGIN_STATE(AfterAttributeValueQuotedState)
115     if (isTokenizerWhitespace(character))
116         ADVANCE_TO(BeforeAttributeNameState); // 属性值解析完毕,如果后面继续跟着空白字符,说明后续还有属性要解析,调回到BeforeAttributeNameState
117     if (character == '/')
118         ADVANCE_PAST_NON_NEWLINE_TO(SelfClosingStartTagState);
119     if (character == '>')
120         return emitAndResumeInDataState(source); // 属性值解析完毕,如果遇到'>'字符,说明整个标签也要解析完毕了,此时结束当前标签解析,并且重置分词状态为DataState,并移动到下一个字符
121     if (m_options.usePreHTML5ParserQuirks && character == '<')
122         return emitAndReconsumeInDataState();
123     if (character == kEndOfFileMarker) {
124         parseError();
125         RECONSUME_IN(DataState);
126     }
127     parseError();
128     RECONSUME_IN(BeforeAttributeNameState);
129 END_STATE()
130 
131 BEGIN_STATE(AttributeValueUnquotedState)
132     if (isTokenizerWhitespace(character)) { // 当解析不带引号的属性值时遇到空白字符(这与带引号的属性值不一样,带引号的属性值可以包含空白字符),说明当前属性解析完毕,后面还有其他属性,跳转到BeforeAttributeNameState,并且移动到下一个字符
133         m_token.endAttribute(source.numberOfCharactersConsumed());
134         ADVANCE_TO(BeforeAttributeNameState);
135     }
136     if (character == '&') {
137         m_additionalAllowedCharacter = '>';
138         ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInAttributeValueState);
139     }
140     if (character == '>') { // 解析过程中如果遇到'>'字符,说明整个标签也要解析完毕了,此时结束当前标签解析,并且重置分词状态为DataState,并移动到下一个字符
141         m_token.endAttribute(source.numberOfCharactersConsumed());
142         return emitAndResumeInDataState(source);
143     }
144     if (character == kEndOfFileMarker) {
145         parseError();
146         m_token.endAttribute(source.numberOfCharactersConsumed());
147         RECONSUME_IN(DataState);
148     }
149     if (character == '"' || character == '\'' || character == '<' || character == '=' || character == '`')
150         parseError();
151     m_token.appendToAttributeValue(character); // 将遇到的属性值字符添加到Token
152     ADVANCE_PAST_NON_NEWLINE_TO(AttributeValueUnquotedState); // 跳转到当前状态,并且移动到下一个字符
153 END_STATE()

从代码中可以看到,当属性值带引号和不带引号时,解析的逻辑是不一样的。当属性值带有引号时,属性值里面是可以包含空白字符的。如果属性值不带引号,那么一旦碰到空白字符,说明这个属性就解析结束了,会进入下一个属性的解析当中。

 

第四种 纯文本解析

这里的纯文本指起始标签与结束标签之间的任何纯文字,包括脚本文、CSS文本等等,如下图所示:

<!-- div标签中的纯文本 Hello,Word! -->
<div class=news align=center>Hello,World!</div>


<!-- script标签中的纯文本 window.name = 'Lucy'; -->
<script>window.name = 'Lucy';</script>

纯文本的解析过程比较简单,就是不停的在DataState状态上跳转,缓存遇到的字符,直到遇见一个结束标签的'<‘字符,相关代码如下:

 1 BEGIN_STATE(DataState)
 2     if (character == '&')
 3         ADVANCE_PAST_NON_NEWLINE_TO(CharacterReferenceInDataState);
 4     if (character == '<') { // 如果在解析文本的过程中遇到开标签,分两种情况
 5         if (haveBufferedCharacterToken()) // 第一种,如果缓存了文本字符就直接按当前DataState返回,并不移动字符,所以下次再进入分词操作时取到的字符仍为'<'
 6             RETURN_IN_CURRENT_STATE(true);
 7         ADVANCE_PAST_NON_NEWLINE_TO(TagOpenState); // 第二种,如果没有缓存任何文本字符,直接进入TagOpenState状态,进入到起始标签解析过程,并且移动下一个字符
 8     }
 9     if (character == kEndOfFileMarker)
10         return emitEndOfFile(source);
11     bufferCharacter(character); // 缓存遇到的字符
12     ADVANCE_TO(DataState); // 循环跳转到当前DataState状态,并且移动到下一个字符
13 END_STATE()

由于流程比较简单,下面只给出解析div标签中纯文本的结果:

 

创建节点与添加节点

1 相关类图

 

2 创建、添加流程

上面的分词循环中,每分出一个Token,就会根据Token创建对应的Node,然后将Node添加到DOM树上。(HTMLDocumentParser::pumpTokenizerLoop方法在上面分词中有介绍)。

 

 

上面方法中首先看HTMLTreeBuilder::constructTree,代码如下:

 1 // 只保留关健代码
 2 void HTMLTreeBuilder::constructTree(AtomHTMLToken&& token)
 3 {
 4     ...
 5 
 6     if (shouldProcessTokenInForeignContent(token))
 7         processTokenInForeignContent(WTFMove(token));
 8     else
 9         processToken(WTFMove(token)); // HTMLToken在这里被处理
10 
11     ...
12 
13     m_tree.executeQueuedTasks(); // HTMLContructionSiteTask在这里被执行,有时候也直接在创建的过程中直接执行,然后这个方法发现队列为空就会直接返回
14     // The tree builder might have been destroyed as an indirect result of executing the queued tasks.
15 }
16 
17 
18 void HTMLConstructionSite::executeQueuedTasks()
19 {
20     if (m_taskQueue.isEmpty()) // 队列为空,就直接返回
21         return;
22 
23     // Copy the task queue into a local variable in case executeTask
24     // re-enters the parser.
25     TaskQueue queue = WTFMove(m_taskQueue);
26 
27     for (auto& task : queue) // 这里的task就是HTMLContructionSiteTask
28         executeTask(task); // 执行task
29 
30     // We might be detached now.
31 }

上面代码中HTMLTreeBuilder::processToken就是处理Token生成对应Node的地方,代码如下所示:

 1 void HTMLTreeBuilder::processToken(AtomHTMLToken&& token)
 2 {
 3     switch (token.type()) {
 4     case HTMLToken::Uninitialized:
 5         ASSERT_NOT_REACHED();
 6         break;
 7     case HTMLToken::DOCTYPE: // HTML中的DOCType标签
 8         m_shouldSkipLeadingNewline = false;
 9         processDoctypeToken(WTFMove(token));
10         break;
11     case HTMLToken::StartTag: // 起始HTML标签
12         m_shouldSkipLeadingNewline = false;
13         processStartTag(WTFMove(token));
14         break;
15     case HTMLToken::EndTag: // 结束HTML标签
16         m_shouldSkipLeadingNewline = false;
17         processEndTag(WTFMove(token));
18         break;
19     case HTMLToken::Comment: // HTML中的注释
20         m_shouldSkipLeadingNewline = false;
21         processComment(WTFMove(token));
22         return;
23     case HTMLToken::Character: // HTML中的纯文本
24         processCharacter(WTFMove(token));
25         break;
26     case HTMLToken::EndOfFile: // HTML结束标志
27         m_shouldSkipLeadingNewline = false;
28         processEndOfFile(WTFMove(token));
29         break;
30     }
31 }

可以看到上面代码对7类Token做了处理,由于处理的流程都是类似的,这里只给出3种HTML标签的创建添加过程,分别是DOCTYPE标签,html标签,title标签文本,剩下的过程都使用图表示。

2.1 DOCTYPE标签

 1 // 只保留关健代码
 2 void HTMLTreeBuilder::processDoctypeToken(AtomHTMLToken&& token)
 3 {
 4     ASSERT(token.type() == HTMLToken::DOCTYPE);
 5     if (m_insertionMode == InsertionMode::Initial) { // m_insertionMode的初始值就是InsertionMode::Initial
 6         m_tree.insertDoctype(WTFMove(token)); // 插入DOCTYPE标签
 7         m_insertionMode = InsertionMode::BeforeHTML; // 插入DOCTYPE标签之后,m_insertionMode设置为InsertionMode::BeforeHTML,表示下面要开是HTML标签插入
 8         return;
 9     }
10    
11    ...
12 }
13 
14 // 只保留关健代码
15 void HTMLConstructionSite::insertDoctype(AtomHTMLToken&& token)
16 {
17     ...
18 
19     // m_attachmentRoot就是Document对象,文档根节点
20     // DocumentType::create方法创建出DOCTYPE节点
21     // attachLater方法内部创建出HTMLContructionSiteTask
22     attachLater(m_attachmentRoot, DocumentType::create(m_document, token.name(), publicId, systemId));
23 
24     ...
25 }
26 
27 // 只保留关健代码
28 void HTMLConstructionSite::attachLater(ContainerNode& parent, Ref<Node>&& child, bool selfClosing)
29 {
30    ...
31 
32     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert); // 创建HTMLConstructionSiteTask
33     task.parent = &parent; // task持有当前节点的父节点
34     task.child = WTFMove(child); // task持有需要操作的节点
35     task.selfClosing = selfClosing; // 是否自关闭节点
36 
37     // Add as a sibling of the parent if we have reached the maximum depth allowed.
38     // m_openElements就是HTMLElementStack,在这里还看不到它的作用,后面会讲。这里可以看到这个stack里面加入的对象个数是有限制的,最大不超过512个。
39     // 所以如果一个HTML标签嵌套过多的子标签,就会触发这里的操作
40     if (m_openElements.stackDepth() > m_maximumDOMTreeDepth && task.parent->parentNode())
41         task.parent = task.parent->parentNode(); // 满足条件,就会将当前节点添加到爷爷节点,而不是父节点
42 
43     ASSERT(task.parent);
44     m_taskQueue.append(WTFMove(task)); // 将task添加到Queue当中
45 }

从代码可以看到,这里只是创建了DOCTYPE节点,还没有真正添加。真正执行添加的操作,需要执行HTMLContructionSite::executeQueuedTasks,这个方法在一开始有列出来。下面就来看下每个Task如何被执行。

 1 // 方法位于HTMLContructionSite.cpp
 2 static inline void executeTask(HTMLConstructionSiteTask& task)
 3 {
 4     switch (task.operation) { // HTMLConstructionSiteTask存储了自己要做的操作,构建DOM树一般都是Insert操作
 5     case HTMLConstructionSiteTask::Insert:
 6         executeInsertTask(task); // 这里执行insert操作
 7         return;
 8     // All the cases below this point are only used by the adoption agency.
 9     case HTMLConstructionSiteTask::InsertAlreadyParsedChild:
10         executeInsertAlreadyParsedChildTask(task);
11         return;
12     case HTMLConstructionSiteTask::Reparent:
13         executeReparentTask(task);
14         return;
15     case HTMLConstructionSiteTask::TakeAllChildrenAndReparent:
16         executeTakeAllChildrenAndReparentTask(task);
17         return;
18     }
19     ASSERT_NOT_REACHED();
20 }
21 
22 // 只保留关健代码,方法位于HTMLContructionSite.cpp
23 static inline void executeInsertTask(HTMLConstructionSiteTask& task)
24 {
25     ASSERT(task.operation == HTMLConstructionSiteTask::Insert);
26 
27     insert(task); // 继续调用插入方法
28 
29     ...
30 }
31 
32 // 只保留关健代码,方法位于HTMLContructionSite.cpp
33 static inline void insert(HTMLConstructionSiteTask& task)
34 {
35    ...
36 
37     ASSERT(!task.child->parentNode());
38     if (task.nextChild)
39         task.parent->parserInsertBefore(*task.child, *task.nextChild);
40     else
41         task.parent->parserAppendChild(*task.child); // 调用父节点方法继续插入
42 }
43 
44 // 只保留关健代码
45 void ContainerNode::parserAppendChild(Node& newChild)
46 {
47    ...
48 
49     executeNodeInsertionWithScriptAssertion(*this, newChild, ChildChange::Source::Parser, ReplacedAllChildren::No, [&] {
50         if (&document() != &newChild.document())
51             document().adoptNode(newChild);
52 
53         appendChildCommon(newChild); // 在Block回调中调用此方法继续插入
54         
55         ...
56     });
57 }
58 
59 // 最终调用的是这个方法进行插入
60 void ContainerNode::appendChildCommon(Node& child)
61 {
62     ScriptDisallowedScope::InMainThread scriptDisallowedScope;
63 
64     child.setParentNode(this);
65 
66     if (m_lastChild) { // 父节点已经插入子节点,运行在这里
67         child.setPreviousSibling(m_lastChild);
68         m_lastChild->setNextSibling(&child);
69     } else
70         m_firstChild = &child; // 如果父节点是首次插入子节点,运行在这里
71 
72     m_lastChild = &child; // 更新m_lastChild
73 }

经过执行上面方法之后,原来只有一个根节点的DOM树变成了下面的样子:

2.2 html标签

 1 // processStartTag内部有很多状态处理,这里只保留关健代码
 2 void HTMLTreeBuilder::processStartTag(AtomHTMLToken&& token)
 3 {
 4     ASSERT(token.type() == HTMLToken::StartTag);
 5     switch (m_insertionMode) {
 6     case InsertionMode::Initial:
 7         defaultForInitial();
 8         ASSERT(m_insertionMode == InsertionMode::BeforeHTML);
 9         FALLTHROUGH;
10     case InsertionMode::BeforeHTML:
11         if (token.name() == htmlTag) { // html标签在这里处理
12             m_tree.insertHTMLHtmlStartTagBeforeHTML(WTFMove(token));
13             m_insertionMode = InsertionMode::BeforeHead; // 插入完html标签,m_insertionMode = InsertionMode::BeforeHead,表明即将处理head标签
14             return;
15         }
16 
17     ...
18     }
19 }
20 
21 
22 // 只保留关健代码
23 void HTMLConstructionSite::insertHTMLHtmlStartTagBeforeHTML(AtomHTMLToken&& token)
24 {
25     auto element = HTMLHtmlElement::create(m_document); // 创建html节点
26     setAttributes(element, token, m_parserContentPolicy);
27     attachLater(m_attachmentRoot, element.copyRef()); // 同样调用了attachLater方法,与DOCTYPE类似
28     m_openElements.pushHTMLHtmlElement(HTMLStackItem::create(element.copyRef(), WTFMove(token))); // 注意这里,这里向HTMLElementStack中压入了正在插入的html起始标签
29 
30     executeQueuedTasks(); // 这里在插入操作直接执行了task,外面HTMLTreeBuilder::constructTree方法调用的executeQueuedTasks方法就会直接返回
31 
32     ...
33 }

执行上面代码之后,DOM树变成了如下图所示:

当要插入title起始标签之后,DOM树以及HTMLElementStack m_openElements如下图所示:

 

3.3 title标签文本,

title标签的文本作为文本节点插入,生成文本节点的代码如下:

 1 // 只保留关健代码
 2 void HTMLConstructionSite::insertTextNode(const String& characters, WhitespaceMode whitespaceMode)
 3 {
 4     HTMLConstructionSiteTask task(HTMLConstructionSiteTask::Insert);
 5     task.parent = &currentNode(); // 直接取HTMLElementStack m_openElements的栈顶节点,此时节点是title
 6 
 7     ...
 8 
 9     unsigned currentPosition = 0;
10     unsigned lengthLimit = shouldUseLengthLimit(*task.parent) ? Text::defaultLengthLimit : std::numeric_limits<unsigned>::max(); // 限制文本节点最大包含的字符个数为65536
11 
12     ...
13 
14 
15     // 可以看到如果文本过长,会将分割成多个文本节点
16     while (currentPosition < characters.length()) {
17         AtomString charactersAtom = m_whitespaceCache.lookup(characters, whitespaceMode);
18         auto textNode = Text::createWithLengthLimit(task.parent->document(), charactersAtom.isNull() ? characters : charactersAtom.string(), currentPosition, lengthLimit);
19         // If we have a whole string of unbreakable characters the above could lead to an infinite loop. Exceeding the length limit is the lesser evil.
20         if (!textNode->length()) {
21             String substring = characters.substring(currentPosition);
22             AtomString substringAtom = m_whitespaceCache.lookup(substring, whitespaceMode);
23             textNode = Text::create(task.parent->document(), substringAtom.isNull() ? substring : substringAtom.string()); // 生成文本节点
24         }
25 
26         currentPosition += textNode->length(); // 下一个文本节点包含的字符起点
27         ASSERT(currentPosition <= characters.length());
28         task.child = WTFMove(textNode);
29 
30         executeTask(task); // 直接执行Task插入
31     }
32 }

从代码可以看到,如果一个节点后面跟的文本字符过多,会被分割成多个文本节点插入。下面的例子将title节点后面的文本字符个数设置成85248,使用Safari查看确实生成了2个文本节点:

 

 当遇到title结束标签,代码处理如下:

 1 // 代码内部有很多状态处理,这里只保留关健代码
 2 void HTMLTreeBuilder::processEndTag(AtomHTMLToken&& token)
 3 {
 4     ASSERT(token.type() == HTMLToken::EndTag);
 5     switch (m_insertionMode) {
 6     ...
 7 
 8         case InsertionMode::Text: // 由于遇到title结束标签之前插入了文本,因此此时的插入模式就是InsertionMode::Text
 9         
10         m_tree.openElements().pop(); // 因为遇到了title结束标签,整个标签已经处理完毕,从HTMLElementStack栈中弹出栈顶元素title
11         m_insertionMode = m_originalInsertionMode; // 恢复之前的插入模式
12         break;
13     
14     ...
15 }

每当遇到一个标签的结束标签,都会像上面一样将HTMLElementStack m_openElementsStack的栈顶元素弹出。执行上面代码之后,DOM树与HTMLElementStack如下图所示:

 

 当整个DOM树构建完成之后,DOM树和HTMLElementStack m_openElements如下图所示:

从上图可以看到,当构建完DOM,HTMLElementStack m_openElements并没有将栈完全清空,而是保留了2个节点:html节点与body节点。这可以从Xcode的控制台输出看到:

同时可以看到,内存中的DOM树结构和文章开头画的逻辑上的DOM树结构是不一样的。逻辑上的DOM树父节点有多少子节点,就有多少指向子节点的指针,而内存中的DOM树,不管父节点有多少子节点,始终只有2个指针指向子节点:m_firstChild与m_lastChild。同时,内存中的DOM树兄弟节点之间也相互有指针引用,而逻辑上的DOM树结构是没有的。通过这样的数据结构,使得内存中的DOM结构所占用的空间大大减少,同时也能达到遍历整棵树的效果。试想一下,如果一个父节点有100个子节点,那么使用逻辑上的DOM树结构,父节点就需要100个指向子节点的指针,如果一个指针占用8字节,那么总共就要占用800字节。但是使用上面内存中DOM的表示方式,父节点只需要2个指针就可以了,总共占用16字节,内存消耗大大减少。虽然两者实现方式不一样,但是两者是等价的,都可以正确的表示HTML文档。

Tags: