C++实现富文本控制项: 核心

在实现LongUI时, 一直为文本编辑框苦恼, 感觉需要自己实现一个简单的文本编辑控制项. 本篇就是记录其中相关细节的博客.

根据个人习惯, 将本项目命名为RichED (Riched-Text Edit Deployer). 地址位于:

dustpg/RichED?

github.com图标

本文备份地址: github

简单文本布局

自己将这个称为简单文本布局, 与之对应的自然就是复杂文本布局(Complex text layout), 由于精力等各种原因, 不可能去实现一个CTL, 能够简单胜任文本编辑控制项的能力就行了.

单位

什么东西都离不开单位, 但是文字的单位其实都可以看著相对单位, 所以在实现中使用unit_t作为单位, 可以是float, 也可以是uint32_t作为定点小数.

这里默认使用float作为基础单位, 不过实际上定点小数更好一点(误差是固定的).

编码

编码上自然是建议UTF系列. 可以选择UTF-8, UTF-16 以及UTF-32(UCS4). 不过, 用4位元组编码似乎太奢侈了, UTF-8感觉比较麻烦, 这里选择UTF-16. 不过这又涉及到大小端, 不过作为编辑器不用担心, 内部使用CPU的当前大小端就行.

当然, 这就会出现两个数字表示字元串的长度: 字元串长度, 逻辑字元个数. 这里就用length与count区分.

文字

首先说的自然是文字的度量(Metrics), 在底层还有更基础的一层字形度量(Glyph Metrics), 不过本文并不涉及文字的最底层渲染, 不过相关概念依然可以借鉴.

这里涉及到的就是针对一个文字

  • x-height, x字高, 一般来说就是字母x的高度
  • cap height, 大写字母高度.
  • ascender height, 升高, 一般比大写字母高度要高一点
  • descender height, 降高
  • baseline, 基线, 文字以这根线作为基础参考线.

这些都是参考值, 或者说相对值. 字体设计者并不会严格按照这些规矩设计字体. 比如一个文字大小是100px, 那么设计者会让这个字体看起来差不多就是100px大. 而升高+降高就是一个字体设计上占的高度, 对于我们非常重要.

间距

文字与文字组合起来就成了我们需要的文本, 所以自然需要讨论字间距.

字间距首先是字体设计者所需要考虑的问题, 不过在具体显示时可能需要进行调整, 这里使用css作为参考:

  • letter-spacing, 控制字母间距
  • word-spacing, 控制单词间距

对于我们汉字使用者来说, 需要区分这两个还真是有点烦, 实现较为繁琐, 这里指出是因为有一个css与之相关: text-align

一段文字可以左对齐, 右对齐, 居中对齐以及还有一个特殊的参数: justify: 两侧对齐. 这个参数最重要的用处就是——小学老师教过我们一行不能以逗号句号之类的标点符号开头(当然, 这个规矩对于像自己这种 作文全靠凑的人来说, 是一个毁灭性的打击).

这个是实现的难点, 可以考虑不实现.

间距微调(kerning, 或者译作紧缩), 又是一个搞事的属性, 不过可以看具体API支不支持(以及字体本身支不支持)来确定使用, 而不必自己实现. 特殊文字配对情况下, 可以相互重叠部分, 例如AVATAR:

固定数值

我们可以采用一个ax + b的方式描述一个固定数值, a是相对系数(相当于em), b是绝对系数(相当于px).

行

现在我们可以进行基础排版了!...吗? 前面的Sphinx我们理所当然地认为: 基于基线排列, 从左到右.

css拥有一个vertical-align的属性, 拥有不少值, 其中就有baseline. 我们可以一直假定以基线排列, 让外部控制对齐方式:

  • 假如升高2, 降高1
  • 基线对齐, 测量器返回: 升高2, 降高1
  • 上对齐, 测量器返回: 升高0, 降高3
  • 下对齐, 测量器返回: 升高3, 降高0

减少核心部分的工作量也是一种思路.

从左到右, 这个就被称为阅读方向(Reading Direction), 一般地, 上下左右四个方向都有.

上古可口可乐广告: 右往左阅读, 遇到英文则按左往右阅读

由于按照文字区分方向过于麻烦, 阅读方向是由外部初始化并固定. 特地这样其实是为了支持竖向排列的汉字:

与阅读方向对应的就是行流向(Flow Direction), 与阅读方向垂直(有些特殊的文字系统, 阅读一行就要把载体翻转90度那种除外), 竖向排列的汉栏位落流向就是从右到左.

注音(Ruby)的支持也是类似, 不过注音不一定就是注音, 也有可能是注释什么的. 目前自己接触到的注音大致分为两类: 类字母, 与类汉字.

例图中垂直排版注音的音调显示错了: 不应该旋转90°, 这样看起来像是二声. 可见即便是浏览器这种级别的, 还是有明显的排版BUG. 当然, 也有可能是字体BUG

横著些时一般没有问题, 竖著的时候就有些区别了, 其中汉语注音还有一点区别:

也就是ㄧ和丨, 不过各个地方标准也不一样, 这个还是无视掉算了(手动用ㄧ和丨区分).

换行

说到换行(Line Feed, LF)就不得不提回车(Carriage Return, CR), Windows上默认保留了传统的回车换行
-CRLF, 其他的系统则是简化为
-LF.

作为编辑器自然是: 我全都要.

自动换行

又是一个很烦人的东西, css对此也有非常多的控制属性:

  • white-space
  • overflow-wrap
  • word-break
  • 等等等

不过大体可以分为:

  • 没有自动换行
  • 单词为基础的自动换行
  • 字母为基础的自动换行

同前面的字间距, 在处理中英文时比较麻烦. 汉字可以处处换行, 但是特殊标点符号不能. 对这些细节处理比较麻烦, 可以看自己的情况简化处理.

富文本

自然标题提到了富文本(Rich Text), 自然就是看看这个文本到底能多富. 一般地, 根据自己的需求划分为: 字体属性, 效果, 以及扩展内联对象.

  • 字体属性, 会影响排版的属性. 例如字体大小, 名称之类的.
  • 效果, 不影响排版的属性. 例如下划线, 字体阴影
  • 扩展对象, 这个是必不可少的. 一开始可能就是代指图片之类的, 后期用于扩展.
  • 内联对象长度必须是1个逻辑字元(方便处理)

元胞

如果为每一个字元赋予上面所述的一些属性, 性价比很低: 一个字元也就几个位元组, 属性需要的空间可能是其几十倍. 所以自己将一段文字划分成一个元胞(Cell), 或者说块(Block). 根据个人习惯, 还是称为Cell.

长度这里设置为定长, 有很多优势. 比如方便在栈上处理:

struct Cell {
Node node;
Attr attr;
char16_t buffer[LEN];
};

void foo(Cell& cell) {
char32_t cover[LEN];
utf16_to_utf32(cover, LEN, cell);
bar(cover);
}

或者用于对象缓存减少内存申请(对象大小固定, 很好, 很好).

这个LEN选多少呢? 自己选择的是: debug-9, release-63. debug自然是需要少一点方便调试. 而release选择63(1保留, 原因后述)是因为很多终端一行能够显示80个字元, 于是找个附近的整数.

保留字元

前面提到长度是64, 但是使用了63个. 1作为保留, 是不是认为是处理NUL字元?

答案是否定的, cell中不储存NUL字元, 因为有长度信息了没必要使用NUL. 作为保留是因为UTF-16是使用1~2个UTF-16字元表示一个真正的逻辑字元. 保留一个这样保证使用2个UTF-16字元表示的字元不会分成两个cell储存.

同理, 如果使用UTF-8的话, 由于目前使用1~4个, 所以应该保留3个UTF-8字元. 当然, 这都是建立在Unicode官方不变卦的情况下, 毕竟是有可能打脸的:

UTF-8使用一至六个位元组为每个字元编码（尽管如此，2003年11月UTF-8被RFC 3629重新规范，只能使用原来Unicode定义的区域，U+0000到U+10FFFF，也就是说最多四个位元组。

链式结构

为了方便处理, 我们将cell使用链表串起来, 而不是树. 这是为了简化程序, 方便实现. 同时因为使用的是固定长度的cell, 所以cell对象缓存实现非常简单: cell释放后直接加入缓存栈/队列.

我们把文本分割成一块一块的cell, 最后会合成字元串. 作为一个库, 使用者可能使用各种形式的字元串. 可能是std::string甚至my::string之类的. 这里为了方便描述, 拥有一个外部确定的custom_append方法.

这里假设每个cell为5个utf16字元:

我们为每行最后一个cell打上EOL(END OF LINE)标记. 可以看出除了最后一个cell, 每个EOL会有一个换行字元串:

void custom_append(string_t& str, const char16_t buf[], size_t len);

void gen_string(string_t& output) {
// 使用一个bool以延迟一下, 让最后一个cell不添加换行符
 bool line_mark = false;
for (auto& cell : cells) {
// 这里用
作为示范
 if (line_mark) custom_append(output, u"
", 2);
line_mark = cell.eol;
custom_append(output, cell.buf, cell.len);
}
}

具体的换行符, 比如CRLF(
), 是不用保存在cell里面的. 这样目的是可以随时切换换行符模式.

增量渲染

屏幕渲染有一个优化手段叫做增量渲染, 或者脏渲染: 只需要渲染更新(脏)的区域. 将复杂度O(f(n))的n大幅度降低.

可以打开浏览器的渲染区显示, 用来查看脏区域

同样我们可以推广到节点的更新上, 即增量更新, 或者说脏更新.(其实渲染不一定是指图像图像的渲染, 可以进行推广)

拖延症患者福音

GUI程序很多是一帧内修改多次, 每次修改就重新计算是不明智的, 我们将计算延迟到显示时. 即拖延症患者的福音.

延迟计算很有用, 缺点的话就是很容易出BUG.

元胞休眠

同样, 渲染一个cell可能需要计算并储存相关上下文, 例如可能会生成字体的离屏渲染用点阵图信息. 这些信息在不渲染时完全是占空间的, 所以如果长时间不渲染一个cell, 就可以让其进入休眠, 以节约空间.

元胞相关属性

  • 富有属性, 看起来很有钱的属性(具体有哪些可以后期补充)
  • 排版/度量信息, 包含cell所需要的相关排版/度量信息

属性 | 描述
--------|----------
节点偏移 | 偏移理论坐标的偏移量
边界边框 | 整个cell渲染所需的位置/大小
布局宽度 | 逻辑上cell的宽度
升高降高 | 前面提到过, 用于处理对齐方向

  • 元信息: 保存一些基础信息, 这里就包含了类型、EOL之类的

引入偏移量主要是为了解决一些排版问题:

例如注音, 这个本来应该是父子关系, 不过由于这里简化为链表, 变成了兄弟关系. 不过反正是一家人, 当不了你爹, 做老大哥也行.

垂直排版的时候有些不同.

这条红线, 水平排版一般称为baseline(基线), 垂直排版一般称为vertical axis(纵轴), 几乎就在文字中央. 不过为了简化自然也称为基线.

相关功能

排版

排版自然是最基础的功能, 可以使用矩阵实现cell的排列. 可以看具体实现, 垂直排版时width是表示水平量还是垂直量(使用不同的矩阵就行).

换行也同理:

关于坐标, 这里可以有两种解决方案: 一种是cell储存绝对的坐标; 一种是假定是经典排版的文档空间, 最后显示时再用矩阵乘. 自己权衡了大概3秒, 决定选后者.

文档空间将假定是阅读左到右, 流向上到下(符合屏幕坐标习惯).

定位

一般我们将文本输入中, 一闪一闪的符号称为插入符(caret), 或者称为键盘游标(cursor). 不过游标的话, 可能会和滑鼠游标混淆, 这里就称为插入符, 虽然本身是特指^符号.

我们滑鼠一点, 或者键盘按一下方向键肯定会提示具体位置, 所以我们需要进行定位.

前面提到我们文档结构是使用的链式结构, 查找效率是O(n), 这显然太慢了. 同时为了配合脏数据, 我们使用一个脏数组的简单数据结构.脏数组储存了一个视觉行(visual-line)的一些必要数据:

  • 该行首节点
  • 该行偏移量
  • 等等

脏数组是因为只有一段区间是干净的, 脏的部分的数据是无效的. 脏数组不仅仅是储存行的相关信息, 并且是提供一个支持随机访问的介面.

左边的表示储存每行第一个的脏数组, 干净区域(蓝色数字)是[2, 6). 具体实现中, 起点总为0, 怎么处理, 待定.

  1. 确定位置在干净区内, 否则扩展干净区域
  2. 利用二分查找法定位到指定行
  3. 遍历该行所有cell找到指定cell
  4. 利用cell内部信息计算得出具体位置

这里就是用二分查找法将O(n)复杂度降低至O(log(l) + m), 复杂度大大降低.

固定行高

行距是固定值的话会给人一种美感, 启用这个模式只需要除以固定行高就行.

自动换行

自动换行的话, 由于增量更新, 所以对应的脏数组长度是可能在文档本身没有修改时, 也会产生变化(文档高度自然也是):

黑框表示文档当前(预测的)大小, 蓝框表示当前显示的区域; 绿线表示干净的脏数组区域, 红色表示脏区域. 随著文档浏览, 自动换行可能会引起视觉行脏数组长度, 以及文档(预测)大小 的变化.

...

这里, 自己自动换行简化为四个等级:

  1. 不换行, 这个最简单
  2. 仅空格换行
  3. CJK处处可换行, 或者空格换行
  4. 处处可换行

当然还有很多自动换行的逻辑, 比如智能识别英语单词然后加上连字元-什么的. 这里简化处理, 将修改点局限在一个CELL中, 这样能够较大幅度简化程序, 并且在Release时(cell足够长)大概率不会出现排版BUG:

  1. 在条件允许下尝试合并后面的CELL
  2. 遍历需要换行CELL处(x + w >= W)
  3. (a.)如果是内联之类的特殊CELL, 或者换行处足够靠前: 要么换行, 要么保留(视觉行第一个)
  4. (b.)查询(先从插入点往前, 没有找到再往后),可换行处 并分裂为A, B: B换行

1的条件允许是指一种优化手段, 可以后期考虑, 目的是减少无用的合并. 自己的条件如下:

  • 分奇偶帧, 奇数帧才允许合并
  • 该cell最末尾的位置必须足够靠前才允许合并
  • 后面的cell必须足够短才允许合并

插入

既然叫做插入符就是插入输入文本的:

  1. 仅前面
  2. 仅内部
  3. 两者之间
  4. 仅后面

对于富文本来说, 两者之间可能会出现特殊情况. 可以通过传递一个标志位来确定插入两者之间时插入哪个部分.

可以简单划分成4种:

  1. 插入空的CELL的内部, 行首或者特殊情况
  2. 插入非空CELL的前面, 行首或者特殊情况
  3. 插入非空CELL的中间
  4. 插入非空CELL的后面

当CELL是内联对象时, 只会出现在前面或者后面(因为长度必须是1).

如果插入的CELL足够插入新的字元串, 直接插入就行.其他情况再简化为三种

  • 插入前面: 前创建新CELL[A], 也可以视为分裂
  • 插入中间: 分裂为两个[A, B]
  • 插入后面: 后创建新CELL[B], 也可以视为分裂
  • 通用: 更新行首CELL信息

并将插入的字元串分成三部分:

  1. 字元串(前面)够能插入A的部分
  2. 字元串(后面)能够插入B的部分(可能与1部分重叠, 需要消除重叠)
  3. 中间剩余的部分(可能不存在)

然后执行插入即可. 插入文本后副作用有:

  1. 整体文档尺寸可能改变
  2. 脏数组干净区域可能大幅度变化

当行数变化时, 脏数组大小自然会变化, 并且插入行之后的全部脏了:

void on_line_inserted(uint32_t line) {
if (line >= clean_begin && line < clean_end)
clean_end = line;
else
clean_begin = clean_end = 0;
}

在使用自动换行中, 可能插入一个字元会造成翻天覆地的变化, 不过变化也是局限在该逻辑行中. 视觉行变化和逻辑行的分开处理.

删除, 或者说移除(remove).

  • 找到删除的两个位置所在的cell
  • 两个cell是一个时: 删除文本, 删空则去掉该cell
  • 不一致时: 删除中间文本, 前面一个一定不是EOL, 最后一个cell是EOL则保留
  • 检查最后那个cell那行, 没有cell的话插入一个空的cell作为EOL

比如有两个行文本, 第二行是空的:

CELL AAAAAAAAABBBB[EOL]
1: hello, world!
CELL C[EOL]
2:
^

删除一行最后的EOL的过程:

  1. 删除范围: {0, 13}, {1, 0}
  2. 找到{0, 13}的cell-b
  3. 找到{1, 0}的cell-c
  4. 删除cell-b的后面文本(实际没有)
  5. 取消cell-b的EOL标志
  6. 删除cell-c的文本, 由于删完了, 释放cell-c
  7. 由于cell-c是EOL, 将cell-c前面的cell-b再次设置EOL

修改, 可以是指文本的替换. 不过文本替换就是先删除再插入(或者相反). 这里是特指富文本属性的修改, 可以分为对排版有影响的属性与没有影响的.

  1. 找到起点与终点cell, 根据位置分裂或者标记成A,B - C,D
  2. 其中,因为起点和终点cell相同, 所以应该先分裂后者
  3. [B, D)区间的cell属性修改至指定属性
  4. 脏数组也进行区间修改, 如果是效果之类不修改的, 可以针对ABCD这几个进行增量排版
  5. 没有影响的(比如颜色, 下划线等效果)到此结束
  6. [B, D)区间的cell标记为脏

优化点

后部缓存

在大部分情况都是修改视口中央的部分:

------
------
------
------ <- 上面的在脏数组范围内
ABCDEF <- 修改文档
------ <- 下面会丢失
------
------
------
------

其中逻辑行开始的数据是稳定的, 所以修改逻辑如下:

  • 找到修改点所在行, 获取下一行开始节点A
  • 备份节点A所在行 到 脏数组的行信息
  • 修改文档
  • 重构脏数组, 直到: (1). 遍历到A (2). 或者重构到视口最下方
  • 2的场合中断处理
  • 1的场合, 将备份的数据简单修改后直接添加至脏数组后面

但是, 这这个和延迟计算格格不入, 这里插入就会要求重新计算, 所以可以单独将后面的的数据备份下来, 在具体排版时使用.

休眠

具体休眠演算法待定, 自己想到了两种:

引用计数+循环队列 休眠

  1. 方便循环队列的实现, 队列长度可以是2的幂次方.
  2. 队列长度是动态的, 当全部可视的cell数量过长时扩张队列长度
  3. 当显示区域越大, 说明这个编辑器越重要, 使用更长的休眠队列很合适
  4. 当一个cell进入显示区, 引用计数+1, 入队
  5. 当队列长度超过一个阈值(比如满了), 最后一个出队, 引用计数-1

时间 休眠

  1. 当一个cell由可视转为不可视, 重置时间并进入准休眠状态
  2. 时间归零则进入休眠
  3. 上述的时间不一定是真正的时间, 还可以是修改点——长时间不修改没准儿是AFK
  4. 比如文档被修改5次了, 进入休眠状态

OOM处理

Out of memory这个东西真的很烦人, 自己的应对大致有4个:

  1. 等待恢复. 类似于强异常安全保证, OOM时返回错误码并将现场恢复至调用前. 等待有新的空间就可以继续处理.
  2. 将就著用. 类似与弱异常安全保证, OOM时返回错误码但是没有能力恢复现场. 能够继续安全使用, 但是信息已经丢失. 如果保存的是重要信息, 这时候应该尽可能快地退出程序.
  3. 当场重试. 当场重试比等待恢复要简单得多, 当然不是直接再试. 在之前可以释放一些不必要的缓存, 或者等待系统其他程序关闭.
  4. 强制中断. 使用longjmp或者exit之类不会返回的函数处理

CJK字元检测

根据目前的Unicode布局, CJK字元相关区间为:

  • 2E80-2EFF,中日韩汉字部首补充,CJK Radicals Supplement
  • 3000-303F,中日韩符号和标点,CJK Symbols and Punctuation
  • 31C0-31EF,中日韩笔画,CJK Strokes
  • 3200-32FF,带圈的CJK字元及月份,Enclosed CJK Letters and Months
  • 3300-33FF,中日韩兼容字元,CJK Compatibility
  • 3400-4DBF,中日韩统一表意文字扩展区A,CJK Unified Ideographs Extension A
  • 4DC0-4DFF, 这里空缺的是64卦, 可以算进CJK
  • 4E00-9FFF,中日韩统一表意文字,CJK Unified Ideographs
  • F900-FAFF,中日韩兼容表意文字,CJK Compatibility Ideographs
  • FE30-FE4F,中日韩兼容形式,CJK Compatibility Forms

以上的是用单个UTF-16字元能表示的部分, 其中部分小区间可以考虑舍弃(可以看出中日韩兼容表意文字这区与其他区格格不入). 其中, 汉字〇被放在了标点区. 如何处理, 待定.

  • 20000-2A6DF,中日韩统一表意文字扩展B区,CJK Unified Ideographs Extension B
  • 2A700-2B73F,中日韩统一表意文字扩展C区,CJK Unified Ideographs Extension C
  • 2B740-2B81F,中日韩统一表意文字扩展D区,CJK Unified Ideographs Extension D
  • 2B820-2CEAF,中日韩统一表意文字扩展E区,CJK Unified Ideographs Extension E
  • 2CEB0-2EBEF,中日韩统一表意文字扩展F区,CJK Unified Ideographs Extension F
  • 2F800-2FA1F,中日韩兼容表意文字增补,CJK Compatibility Ideographs Supplement

以上的是用两个UTF-16字元编码的CJK. 这些区间足够分散, 可以实现为查表, 并且简化为只有4个平面(目前是17个, 很多未使用), 再允许一些错误(减少LUT大小以提高缓存命中率):

// 简化为:
// [3200 - 9fff]
// [f900 - faff]
// [20000 - 2ebff]
// [2f800 - 2faff]

// x86 的缓存行是64位元组对齐, c++17可以使用
// std::hardware_destructive_interference_size获取
alignas(64) uint32_t cjk_lut[0x400 / 32] = { /*xxx*/ };

uint32_t is_cjk(uint32_t ch) {
// 假定区域以0x100对齐
 const uint32_t ch2 = (ch & 0x3ffff) >> 8;
const uint32_t index = ch2 >> 5;
const uint32_t mask = 1 << (ch2 & 0x1f);
return cjk_lut[index] & mask;
}

这部分是随著Unicode更新而更新的, 比如目前准备加入第三辅助平面的小篆、甲骨文. 这里判断CJK主要是为了处理自动换行与垂直排版. 这个前提下, 这些显然属于CJK.

REF

  • FreeType Glyph Conventions / III
  • Glyphs and Glyph Runs
  • x-height
  • 注音符号
  • unicode org

推荐阅读：

相关文章