Android 排版引擎实现 - 游标(Cursor)

Frank Xu
微信读书
Published in
5 min readSep 21, 2016

任何一个排版引擎都需要一个游标接口,他的任务是不断地吐出节点(Node)。节点可能是一个 DOM 节点,一个文本节点,一个图片节点等等。

对于 Webkit/Firefox 这类引擎而言,DOM 树节点和实际绘制用的节点是不完全一样的。前者抽象了解析结果,方便排版引擎迭代和访问数据(DOMTree);后者抽象了绘制目标。方便渲染引擎访问和绘制(RenderTree)。

主流引擎的这种抽象是为了更好的做渲染优化,对于我们目前的设计,这两者的差别或许没有那么大。一方面是大部分数据读取逻辑都是一致的,另外一方面是优化可以放在更低一层(不同的游标)来做。

游标接口(ReaderCursor)

游标是一个吐出节点流(Node)的抽象接口。我们把节点分为两类:

  • 块节点(Paragraph):相当于每个段落,每个节点都会另起一行。
  • 内联节点(CharElement):泛指块节点包含的所有子元素,包括普通的字符/图片/音频/视频等等。

而他们都继承一个通用的 Node 基类,这个类同时包含了排版和绘制逻辑,我们通过不同 Cursor 来区分排版和绘制,区分不同的节点优化策略,甚至更多的事情。

Cursor 的扩展

排版游标(ParserCursor)

对象复用

用于排版的游标,由于排版过程是流式排版,不需要回溯,所以可以采用对象池来复用前面用过的大部分对象。

Paragraph obtainNode(int position) {
return staticNodePool.get();
}

而用于绘制的游标,产生的节点需要传递给渲染层去渲染,交互的时候也需要使用这些对象,所以不能简单的使用对象池,每一个段落都重新创建一个干净的对象。

Paragraph obtainNode(int position) {
return new Paragraph();
}

索引记录

面向排版的游标,主要任务之一,就是在交给排版的同时记录一些关键索引信息,比如保留每一行的偏移有助于排版引擎处理的时候仅需要针对每个段落进行处理,读取原文的每一行文本交给排版引擎,排版引擎只考虑一个段落的排版。

这里不能简单地使用 InputStreamReader#readLine() 这个方法,该方法会吞掉换行符(CR/LF),导致原文长度发生变化,通过修改 InputStreamReader 实现保留换行符。对于排版而言,换行符应该是零宽度,所以不会影响表现。

绘制游标(RenderCursor)

数据窗口(PageCursorWindow)

参考 Android 自身的 CursorWindow ,实现一个数据窗口,提前读取和缓存前后 8 页的内容和索引数据,来实现分段加载。

由于在排版阶段缓存了原文排版后的分页索引,这样的索引是有序的,给定任意位置用二分查找即可快速(O(log(N)))找到所在页的数据和索引,此时前后稍微增大一点范围(8页)读出,同时记录好当前缓存的起点即可。

分段加载数据和索引

区间映射(RangeMap)

View 层的绘制,处理文本的区间要求可能有别于数据,为了方便文本处理,可能会提前吞掉一些无效字符;再比如选区和划线,直观表现都是选中几个富文本字符,但是多平台同步的时候是需要把字符区间转换为实际的 HTML 区间的。

比如以下字符选中 World 划线:

Hello, <b>World</b>!
Hello, World!

应该记录 HTML 里的偏移区间而不是纯文本的区间,同时建立这两者的联系:

[10,15) ←→ [7,12)

其中 [10,15) 是标签内的区间。

要在这样的一个区间映射关系里,左边或右边给定任意一个位置,快速找到他在另外一边的位置。这样的区间结构用 GuavaRangeMap 来建立最合适不过。以 Range 作为 Key 来查找另外一个 Range,然后根据给定位置相对于原区间起点偏移来偏移目标区间的起点,即可得到目标 Range 的位置。

public int txt2html(int txtPos) {
Integer original = posPair.first.get(txtPos);
if (original != null) {
Integer target = posPair.second.get(original);
if (target != null) {
return txtPos - target + original;
}
}
return txtPos;
}

实现 html2txt 也类似。

其他游标

除了以上两个比较关键的游标实现,同样的接口可以扩展到其他实现,比如通过覆盖原翻页逻辑来限制未购买数据的可预览数量,甚至构造一个自定义的样式来绘制 HTML 卡片(只有一页的游标)。

制作漂亮的书签

--

--

Frank Xu
微信读书

WeRead at WeChat. Growth Analyst, Data & Infra Engineer.