Geekly articles weekly

从头开始开发浏览器。 第一部分：HTML


大家好！


我们继续有关浏览器引擎开发的系列文章。


在本文中，我将告诉您如何使用DOM创建最快的HTML解析器。 我们将研究HTML规范，以及为什么在解析HTML时在性能和资源消耗方面不好。


关于这个主题，我报告了过去的HighLoad ++。 并不是每个人都可以参加会议，而且文章还提供了更多详细信息。


我假设读者具有HTML的基本知识：标记，节点，元素，名称空间。


HTML规范


在开始探讨HTML解析器的实现之前，您需要了解要相信的HTML规范。


有两种HTML规范：


  1. 工作组
    • 苹果，Mozilla，谷歌，微软
  2. W3c
    • 公司大名单

自然，选择权就落在了行业领导者WHATWG 。 按生活标准，大公司每个都有自己的浏览器/浏览器引擎。


更新：不幸的是，给定的规范链接没有从俄罗斯打开。 显然，带有电报的“战争回声”。


HTML解析过程


构建HTML树的过程可以分为四个部分：


  1. 解码器
  2. 预处理
  3. 分词器
  4. 建树

我们分别考虑每个阶段。


解码器


分词器接受Unicode字符（代码点）作为输入。 因此，我们需要将当前字节流转换为Unicode字符。 为此，请使用编码规范。


如果我们有一个带有未知编码的HTML（没有HTTP标头），那么我们需要在解码开始之前确定它。 为此，我们将使用编码嗅探算法 。


简单来说，该算法的本质是等待字节流中的500或前1024 ，然后运行预扫描字节流算法以确定其编码 ， 该编码尝试查找具有http-equiv ， content或charset属性的<meta>并尝试了解HTML开发人员指示的编码方式。


Encoding规范规定了浏览器引擎支持的最小编码集（总共21种）：UTF-8，ISO-8859-2，ISO-8859-7，ISO-8859-8，windows-874，windows-1250，windows-1251，windows -1252，Windows-1254，Windows-1255，Windows-1256，Windows-1257，Windows-1258，gb18030，Big5，ISO-2022-JP，Shift_JIS，EUC-KR，UTF-16BE，UTF-16LE和x-user -定义。


预处理


将字节解码为Unicode字符后，我们需要“清理”。 即，将所有回车符（ \r ）替换为换行符（ \n ），再加上回车符（ \r ）。 然后，用换行符（ \n ）替换所有回车符。


如此在规范中描述。 也就是说， \r\n => \r ， \r => \n 。


但是，实际上，没有人这样做。 使其更容易：


如果收到回车符（ \r ），请查看是否有换行符（ \n ）。 如果存在，则将两个字符都更改为换行符（ \n ），如果不存在，则仅将第一个字符（ \r ）更改为换行（ \n ）。


这样就完成了初步的数据处理。 是的，您只需要除去回车符，这样它们就不会落入令牌生成器中。 令牌生成器不期望也不知道如何使用回车符。


解析错误


为了将来没有问题，您应该立即告诉您 什么（ parse error ）。


真的没错。 这听起来很险恶，但实际上这只是警告，我们期待一个警告，但我们有另一个警告。


解析错误不会停止数据处理或树的构建。 这是一条消息，表明我们没有有效的HTML。


对于代理对\0 ，不正确的标记位置，不正确的<!DOCTYPE>以及各种其他内容，可以获得Parsig错误。


顺便说一句，某些解析错误会导致后果。 例如，如果指定“ bad” <!DOCTYPE>则HTML树将被标记为QUIRKS并且某些DOM函数的逻辑将改变。


分词器


如前所述，令牌生成器接受Unicode字符作为输入。 这是一个具有80个状态的状态机。 在每种状态下，Unicode字符的条件。 根据收到的字符，令牌生成器可以：


  1. 改变你的状态
  2. 生成令牌并更改状态
  3. 不执行任何操作，等待下一个字符

令牌生成器创建六种令牌：DOCTYPE，开始标签，结束标签，注释，字符，文件结束。 从而进入建树阶段。


值得注意的是，令牌生成器并不知道其所有状态，而是知道大约40％的位置（例如，从上限得出）。 “为什么还要休息？” -你问。 其余约60％的人知道植树的阶段。


这样做是为了正确解析诸如<textarea> ， <style> ， <script>和<title>标签。 也就是说，通常那些标签中我们不期望其他标签，而只是封闭自己。


例如， <title>不能包含其他标签。 <title>任何标签都将被视为文本，直到遇到自己的结束标签</title>为止。


为什么要这样做？ 毕竟，您可以告诉令牌生成器，如果我们遇到<title>那么我们将遵循“所需的路径”。 如果没有名称空间，那将是正确的！ 是的，名称空间会影响树构建阶段的行为，从而改变令牌生成器的行为。


例如，考虑HTML和SVG名称空间中<title>的行为：


的HTML


 <title><span></span></title>

建立一棵树的结果：


 <title> "<span></span>"

SVG


 <svg><title><span></span></title></svg>

建立一棵树的结果：


 <svg> <title> <span> ""

我们看到在第一种情况（HTML名称空间）中， <span>是文本，没有创建span元素。 在第二种情况下（SVG名称空间），基于<span>标签创建了一个元素。 也就是说，根据名称空间，标签的行为不同。


但这还不是全部。 事实证明，令牌生成器本身必须知道树构建阶段位于哪个命名空间中，这是对“生命的庆祝”的重中之重。 这仅是为了正确处理CDATA所必需的。


考虑两个带有CDATA示例，两个名称空间：


的HTML


 <div><![CDATA[  ]]></div>

建立一棵树的结果：


 <div> <!--[CDATA[  ]]-->

SVG


 <div><svg><![CDATA[  ]]></svg></div>

建立一棵树的结果：


 <div> <svg> "  "

在第一种情况下（HTML名称空间），令牌生成器将CDATA用作注释。 在第二种情况下，令牌生成器分解CDATA结构并从中接收数据。 通常，规则是这样的：如果我们不在HTML名称空间中遇到CDATA ，则将其解析，否则将其视为注释。


这是分词器与树结构之间的紧密联系。 令牌生成器必须知道树构建阶段当前位于哪个名称空间中，并且树构建阶段可以更改令牌生成器的状态。


代币


下面，我们将考虑令牌生成器创建的所有六种令牌类型。 值得一提的是，所有令牌都已准备好数据，即已经处理并“准备使用”。 这意味着所有命名的字符引用（例如© ）都将转换为unicode字符。


DOCTYPE令牌


DOCTYPE令牌具有与其他标签不同的自身结构。 令牌包含：


  1. 名
  2. 公开标识符
  3. 系统识别码

在现代HTML中，唯一有效的/有效的DOCTYPE应该如下所示：


 <!DOCTYPE html>

所有其他<!DOCTYPE>将被视为解析错误。


开始标记令牌


开头标签可能包含：


  1. 标签名称
  2. 属性
  3. 标志

例如


 <div key="value" />

开头标签可以包含一个self-closing标志。 该标志不会影响标签的关闭，但可能会导致非空元素的解析错误。


结束标签令牌


结束标签。 它具有开始标记令牌的所有属性，但标记名称前面带有斜杠/ 。


 </div key="value" />

结束标记可能包含一个self-closing标志，这将导致解析错误。 另外，解析错误将由结束标记的属性引起。 它们将被正确解析，但是在树构建阶段被丢弃。


评论令牌


评论令牌包含整个评论文本。 也就是说，它已完全从流复制到令牌。


例子


 <!--  -->

角色标记


也许是最有趣的标记。 Unicode令牌符号。 可以包含一个（仅一个）字符。


将为HTML中的每个字符创建一个令牌，并将其发送到树构建阶段。 这非常昂贵。
让我们看看它是如何工作的。


取得HTML资料：


 <span> ! &reg;</span>

您认为此示例将创建多少个令牌？ 答：22。


考虑创建的令牌列表：


 Start tag token: <span> Character token:  Character token:  Character token:  Character token:  Character token:  Character token: Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token:  Character token: ! Character token: Character token: End tag token: </span> End-of-file token

不安慰吧？ 但是，当然，许多HTML解析器的创建者实际上在处理过程中只有一个令牌。 循环运行它，并每次都用新数据覆盖它。


让我们继续回答这个问题：为什么要这样做？ 为什么不把这些文本分成一个整体？ 答案在于树的建造阶段。


没有构建HTML树的阶段，令牌生成器是没有用的。 在构建树的阶段，将文本与不同的条件粘合在一起。


条件大致如下：


  1. 如果到达了带有U+0000 （ NULL ）的字符标记，那么我们将导致解析错误并忽略该标记。
  2. 如果U+0009 （ U+000A ）， U+000A （ LINE FEED (LF) ）， U+000C （ FORM FEED (FF) ）或U+0020 （ SPACE ）字符令牌之一出现，则调用算法以恢复活动的格式化元素，并将令牌插入树中。

根据以下算法，将符号令牌添加到树中：


  1. 如果当前插入位置不是文本节点，则创建一个文本节点，将其插入树中，然后将令牌中的数据添加到树中。
  2. 否则，将数据从令牌添加到现有的文本节点。

此行为会带来很多问题。 每个符号都需要创建一个令牌并将其发送到分析以构建树的阶段。 我们不知道文本节点的大小，我们必须预先分配大量内存或进行重新分配。 从内存或时间来看，所有这些都是极其昂贵的。


文件结束令牌


简单明了的令牌。 数据已结束-让我们通知您有关树木建造的阶段。


建树


树构建是一个具有23个状态的状态机，其中包含用于标记（标签，文本）的许多条件。 建造树木的阶段是最大的，占据了规范的重要部分，并且还能够引起昏昏欲睡的睡眠和刺激感。


一切都安排得非常简单。 在输入处接收令牌，并根据令牌切换树结构的状态。 在输出中，我们有一个真实的DOM。


有问题吗？


以下问题似乎很明显：


逐字符复制


每个标记生成器状态在输入处接收一个字符，在需要时将其复制/转换：标记名称，属性，注释，符号。


这在内存和时间上都是非常浪费的。 我们被迫为每个属性，标签名称，注释等预分配未知数量的内存。 因此，这会导致重新部署，而重新部署会导致浪费时间。


并且，如果您想象HTML包含1000个标签，并且每个标签至少具有一个属性，那么我们将得到一个令人讨厌的缓慢解析器。


角色标记


第二个问题是字符令牌。 事实证明，我们为每个符号创建了一个令牌，并给了它以构建一棵树。 建立一棵树不知道我们将拥有多少这些令牌，因此无法立即为所需数量的字符分配内存。 因此，这里所有相同的realoks +常量检查树的当前状态下是否存在文本节点。


单片系统


最大的问题是一切都取决于一切。 即，分词器取决于构建树的状态，并且树的构造可以控制分词器。 一切都归咎于名称空间（名称空间）。


我们将如何解决这些问题？


接下来，我将描述Lexbor项目中HTML解析器的实现，以及解决所有已提出问题的解决方案。


预处理


我们删除了初步的数据处理。 我们将训练令牌生成器以将回车符（ \r ）理解为空格字符。 因此，他将被投入到建造一棵树的阶段，我们将在此阶段进行计算。


代币


轻拂一下手腕，便可以统一所有令牌。 我们将为所有事情拥有一个令牌。 通常，在整个解析过程中将只有一个令牌。


我们的统一令牌将包含以下字段：


  1. 标签编号
  2. 开始
  3. 完结
  4. 属性
  5. 标志

标签编号


我们将不使用标签名称的文字表示。 我们将一切都转化为数字。 这些数字易于比较，更易于使用。


我们根据所有已知标签创建一个静态哈希表。 我们从所有已知标签创建枚举。 也就是说，我们需要严格地为每个标签分配一个标识符。 因此，在哈希表中，关键字是标签的名称，并且该值是从枚举中写入的。


例如：


 typedef enum { LXB_TAG__UNDEF = 0x0000, LXB_TAG__END_OF_FILE = 0x0001, LXB_TAG__TEXT = 0x0002, LXB_TAG__DOCUMENT = 0x0003, LXB_TAG__EM_COMMENT = 0x0004, LXB_TAG__EM_DOCTYPE = 0x0005, LXB_TAG_A = 0x0006, LXB_TAG_ABBR = 0x0007, LXB_TAG_ACRONYM = 0x0008, LXB_TAG_ADDRESS = 0x0009, LXB_TAG_ALTGLYPH = 0x000a, /* ... */ }

从示例中可以看到，我们为END-OF-FILE令牌，文本和文档创建了标签。 所有这些都是为了进一步的方便。 打开帷幕，我将说在节点（ DOM Node Interface ）中，我们将有一个Tag ID 。 这样做是为了不进行两个比较：在节点的类型上和在元素上。 也就是说，如果需要DIV元素，则在节点中进行一次检查：


 if (node->tag_id == LXB_TAG_DIV) { /* Best code */ }

但是，当然，您可以这样做：


 if (node->type == LXB_DOM_NODE_TYPE_ELEMENT && node->tag_id == LXB_TAG_DIV) { /* Oh, code */ }

需要使用LXB_TAG__中的两个下划线将公用标签与系统标签分开。 换句话说，用户可以使用名称text或end-of-file创建标签end-of-file如果我们随后按标签名称进行搜索，则不会发生任何错误。 所有系统标签均以#开头。


但是，节点仍可以存储标签名称的文本表示。 对于98.99999％的节点，此参数将为NULL 。 在某些名称空间中，我们需要使用固定寄存器指定前缀或标记名。 例如，SVG名称空间中的baseProfile 。


工作的逻辑很简单。 如果我们有一个带有明确定义的寄存器的标签，则：


  1. 将其添加到小写标签的常规库中。 获取标签ID。
  2. 在文本表示中将标签标识符和原始标签名称添加到节点。

自定义标签


开发人员可以在HTML中创建任何标签。 由于在静态哈希表中只有我们知道的那些标签，并且用户可以创建任何标签，因此我们需要一个动态哈希表。


一切看起来都很简单。 当标签出现时，我们将看到它是否在静态哈希表中。 如果没有标签，那么让我们看一下动态标签；如果没有标签，那么将标识符计数器增加一，然后将标签添加到动态表中。


所描述的一切都发生在令牌生成器阶段。 在令牌生成器内部，并且所有比较之后都按Tag ID （极少数例外）。


开始和结束


现在，在分词器中，我们将不再进行数据处理。 我们不会复制和转换任何东西。 我们只是将指针指向数据的开头和结尾。


所有数据处理（例如符号链接）都将在构建树的阶段进行。
因此，我们将知道用于后续内存分配的数据大小。


属性


这里的一切都一样简单。 我们不复制任何内容，而只是保存指向名称和属性值的开头/结尾的指针。 所有转换都在构建树时发生。


标志


由于我们拥有统一的令牌，因此我们需要以某种方式告知树结构令牌的类型。 为此，请使用标志位图字段。


该字段可能包含以下值：


 enum { LXB_HTML_TOKEN_TYPE_OPEN = 0x0000, LXB_HTML_TOKEN_TYPE_CLOSE = 0x0001, LXB_HTML_TOKEN_TYPE_CLOSE_SELF = 0x0002, LXB_HTML_TOKEN_TYPE_TEXT = 0x0004, LXB_HTML_TOKEN_TYPE_DATA = 0x0008, LXB_HTML_TOKEN_TYPE_RCDATA = 0x0010, LXB_HTML_TOKEN_TYPE_CDATA = 0x0020, LXB_HTML_TOKEN_TYPE_NULL = 0x0040, LXB_HTML_TOKEN_TYPE_FORCE_QUIRKS = 0x0080, LXB_HTML_TOKEN_TYPE_DONE = 0x0100 };

除了打开或关闭的令牌类型之外，还有数据转换器的值。 只有令牌生成器知道如何正确转换数据。 因此，令牌生成器在令牌中标记应如何处理数据。


角色标记


从前面的描述中，我们可以得出结论，符号令牌已从我们中消失了。 是的，现在我们有了一种新型的令牌： LXB_HTML_TOKEN_TYPE_TEXT 。 现在，我们为标记之间的整个文本创建一个令牌，标记将来应如何处理。


因此，我们将不得不更改树的构造条件。 我们需要训练他不要使用符号标记，而要使用文本标记：转换，删除不必要的字符，跳过空格等等。


但是，没有什么复杂的。 在构建树的阶段，更改将是最小的。 但是，分词器现在根本与单词中的规范不匹配。 但是我们不需要他，这很正常。 我们的任务是获得一个完全符合规范的HTML / DOM树。


分词器阶段


为了确保令牌处理程序中的高速数据处理，我们将迭代器添加到每个阶段。 根据规范，每个阶段都为我们接受一个符号，并根据到达的符号进行决策。 但是，事实是它非常昂贵。


例如，要从ATTRIBUTE_NAME阶段移至ATTRIBUTE_VALUE阶段ATTRIBUTE_VALUE我们需要在属性名称中找到一个空格，以指示其结束。 根据规范，我们应该按字符向阶段ATTRIBUTE_NAME馈送，直到出现空白字符为止，并且此阶段不会切换到另一个阶段。 这非常昂贵，通常是通过对每个字符或回调（例如“ tkz-> next_code_point（）”）进行函数调用来实现的。


我们向ATTRIBUTE_NAME阶段添加一个循环，并传递整个传入缓冲区。 在循环中，我们寻找需要切换的符号并继续在下一阶段工作。 在这里，我们获得了很多收益，甚至是编译器优化。


但是！ 最糟糕的是，我们由此打破了对大块（大块）的支持。 多亏了令牌生成器每个阶段中逐个字符的处理，我们才对块有了支持，现在我们打破了它。


如何解决？ 如何实现对块的支持？ 很简单，我们介绍了传入缓冲区（Incoming Buffer）的概念。


传入缓冲区


HTML通常以块的形式进行解析。 例如，如果我们通过网络接收数据。 为了在等待剩余数据时不会处于空闲状态，我们可以发送已接收的数据进行处理/解析。 自然，数据可以在任何地方被破坏。 例如，我们有两个缓冲区：


首先


 <div clas

第二个


 s="oh-no-oh-no">

由于我们在标记化阶段不复制任何内容，而仅使用指向数据开头和结尾的指针，因此我们遇到了问题。 指向不同用户缓冲区的指针。 考虑到开发人员经常为数据使用相同的缓冲区，我们正在处理一个指向不存在的数据开始的指针。


.
:


  1. (Incoming Buffer).
  2. ( ) , ? , . , . 99% .

" " . .


, . , ( ) . . , , , . .


:


, . , : . . ( ), . .


: . , .



.


, . , .


:



 tree_build_in_body_character(token) { if (token.code_point == '\0') { /* Parse error, ignore token */ } else if (token.code_point == whitespaces) { /* Insert element */' } /* ... */ }

Lexbor HTML


 tree_build_in_body_character(token) { lexbor_str_t str = {0}; lxb_html_parser_char_t pc = {0}; pc.drop_null = true; tree->status = lxb_html_token_parse_data(token, &pc, &str, tree->document->mem->text); if (token->type & LXB_HTML_TOKEN_TYPE_NULL) { /* Parse error */ } /* Insert element if not empty */ }

, . :


 pc.replace_null /*   '\0'    (REPLACEMENT CHARACTER (U+FFFD)) */ pc.drop_null /*   '\0' */ pc.is_attribute /*          " " */ pc.state /*  .        . */

. - \0 , - REPLACEMENT CHARACTER . - , - . .


, . . , <head> . , , : " ". , .


<sarcasm>

HTML ( ) sarcasm . .


 An end tag whose tag name is "sarcasm" Take a deep breath, then act as described in the "any other end tag" entry below.

.



HTML DOM/HTML Interfaces HTML/DOM HTML .


, :


  1. ( )

    • Incoming Buffer
    • Tag ID
    • ̆ : , N+
    • ̆
    • ̈


i7 2012 , , 235MB (Amazon-).


, 1.5/2 , . , . , CSS (Grammar, , Grammar). HTML, CSS , "".


源代码


HTML Lexbor HTML .


聚苯乙烯


CSS Grammar. , . - 6-8 .


,

. , .
( ). .


感谢您的关注！

Source: https://habr.com/ru/post/zh-CN430736/

More articles:


All Articles