实现和优化一个排版引擎不是一件轻松的事情。甚至描述清楚设计也不轻松。看看这篇讲浏览器实现原理的文章有多长就明白了。
一直以来除了 BlinkOn 系列会议（BlinkOn3，BlinkOn5，BlinkOn6）之外，极少有讨论如何实现 HTML 引擎的文章，趁着在微信读书上实现一个稍微完整的排版引擎，讲一下整体的选型过程和一些关键节点的实现。
在 Web 的场景下，HTML 往往不会一成不变，而在电子书（epub/mobi）的场景下，书籍会经历出版社编辑校验一长串流程之后分发出去，分发出去之后就不太会经常变更，而且书籍的 HTML 一般比较长，多次阅读同一份 HTML 的可能性比较高，频繁建立 DOM 树的开销不容小觑，缓存排版和渲染结果就比较有意义。
排版引擎的缓存实现常见的是图片缓存，即页面经过排版后在画布上的输出，然后把排版渲染优化转为图片优化来做。因为图片本身需要更多的存储空间，写入和读取图片都会增加一定耗时。为此所以我们考虑了另外一种思路，通过两类索引实现：
- 索引 DOM 树（即内容和样式的关系）来实现排版缓存
- 索引排版后元素的位置（即 x/y 和宽高信息）来实现渲染缓存
- 通过二次索引来实现索引和内容分段读取
索引 DOM 树
DOM 树是从 HTML 解析构造出来的，作为 HTML 文件的内存索引，方便查找和修改。而排版引擎一般不需要支持 JS，DOM 树的访问一般是顺序读，即大部分人都是从头读到尾，对于 DOM 树来说，就是深度优先的访问顺序，所以可以不考虑查找的复杂度，而把设计集中到如何实现最快的顺序访问。
DOM 树持久化
DOM 树是最普通的一种树，无线子节点，父节点区间包含所有子节点区间，如下 HTML：
<div class="introduction">
<p>Hello, <strong class="red">World</strong>!</p>
</html>可通过以下树结构表示：
div.introduction
/ | \
"Hello," strong.red "!"
|
"World"最终输出为：
Hello, World!
DOM 树上可以对每个节点记录一下最终输出的区间信息：
[0－12)
div.introduction
/ | \
[0－6) [6-11) [11-12)
"Hello," strong.red "!"
|
[6-11)
"World"这样的区间信息通过深度优先的顺序排序，则可得：
0,12,0,6,6,11,6,11,11,12如上，两个数字为一对区间，左闭右开，记录为一个节点。
DOM 树读取
保存完的数据需要读出来还原成原来的 DOM 树，假设给定这样一组数字：
6,11,0,15,4,6,0,4,11,15,6,15我们按两个数字为单位拆分这个数组，并按第一个数字从小到大排序，第二个数字从大到小排序，得到：
0,15
0,4
4,6
6,15
6,11
11,15然后按顺序读取区间：
- 最近读取的一个区间为当前区间（C）
- 如果下一个区间在当前区间以内则记录为当前区间的子节点（N），然后把当前区间改成新加进来的子节点
- 如果下一个区间不在当前区间以内，则查找当前区间的父节点，重复1,2,3，直到能把区间放进去树为止
这样根据区间包含来判断父子关系，即可还原出来原来的 DOM 树区间结构：
[0,15)
/ | \
[0,4) [4,6) [6,15)
/ \
[6,11)[11,15)这样的实现其实是一种有序线段树（Segment Tree），前提条件是区间不能交叉，然后通过预先排序确定区间包含关系，从而确定父子关系。
DOM 树的内容和样式
单纯记录区间位置没有太大作用，每个区间应该有对应的样式，用以描述这个区间的样式。通过选择器引擎把样式和节点关联起来之后就可以记录对应的关系。
这样我们就把 DOM 树缓存为三个部分：
- 无节点，无样式的内容
- 样式数组（无需保留选择器，选择器的结果已经缓存到了 DOM 树上）
- 带有样式引用的 DOM 树索引
至此排版引擎在排版的过程中只需面向一份 DOM 索引树，根据排版所需加载对应的样式和内容即可。排版的内存能得到较好的控制，内容不变的重新排版（比如更换字体大小）也无需重新建立整一棵 DOM 树。
另外一方面，通过这样的中间格式，排版引擎本身能够更好地扩展到多格式支持。
渲染位置索引
对于单个设备，同一章书的每个元素的位置都是一样的，这是为什么常见的引擎都会将排版结果保存为图片避免重复排版。由于图片本身的大小和读取开销跟机型相关，大屏手机可能会得到比较大的图片，而图片本身也不利于深入压缩存储空间。所以，我们考虑另外一个思路，通过第一次排版的时候保存每个元素的位置，读内容直接套上排版的时候保存下来的位置信息来实现缓存。
数字压缩
这样的话每个字至少对应四个数字，[x, y, width, height]，假设每个数字都是 int 的话，索引的体积差不多膨胀了 5 倍（UTF8常见的中文字符都是 3 byte）。考虑到大部分索引数字都是比较有规律的，其实可以有很大的压缩空间。
数字压缩最常见的领域是搜索引擎的倒排索引压缩，文章讲的非常循序渐进，这里不赘述。我们针对自己的数字特征选定或者组合多种高效的压缩方式。比如：
- 同一行文本的 y 轴是一样的，所以可用 delta 压缩
- 大部分中文字符的宽高都基本一样，可以用 delta 压缩
- 大部分数字都不会大于 65536，可用变长数字编码来处理
- 小范围重新排序使得数字更好压缩
分段读取和二次索引
排版之后，我们记录内容的分页偏移，翻页的过程中仅根据需要加载附近几页的内容，由于压缩索引本身会改变原来的长度，所以需要对这些索引的压缩进行二次索引。
分段的思路来自于 Android 的 CursorWindow，思路可以简单描述为：通过读取二次索引来加载前后N页的索引和内容，而不用每次都加载整章索引。由于我们是通过流读取，可以快速的跳到指定位置读取，所以直接跳到某一个分段完全是一次 seek 调用的开销，使得加载章节的速度跟章节大小无关。
流读取和分段还可以复用缓冲区，控制渲染时的内存开销。
索引流写入
排版过程中的索引数字，一旦一个段落排版完成，是不需要去修改的。所以在适当的时机把这些索引“刷”到磁盘是一个比较可行的做法。
实现上通过 okio 的 Buffer，以段落为单位把产生的索引刷入磁盘。
okio 用双向链表实现了一个能够重复使用的缓冲池，用于在多个数据流中复用缓冲区。对于频繁做流处理的效果非常明显（比如 okhttp），因为不在需要每个数据流都自己管理缓冲区。
通过这样的方式能做到排版过程中的索引部分内存开销仅限于每个段落的索引数据大小，段落排版完成之后内存又可以留出来给新的段落使用，不需要重新申请大块内存也不会轻易触发GC，这在连续排版很多章节（预加载）的时候特别有用。
