用C++实现富文本控制项: 撤销

本节是关于撤销重做相关实现. 项目地址: Github-RichED 本文备份地址: github

撤销重做

这就被称为UNDO/REDO之类的, 简直是增量的代表. 这也算富文本编辑器实现的一个难点. 虽然叫做撤销栈, 但是不完全是栈:

  • 一般栈只需要栈底、栈顶指针, 撤销栈多一个操作位置
  • 撤销是操作位-1, 栈顶不动, 直到达到栈底
  • 重做是操作位+1, 栈顶不动, 直到达到栈顶
  • 每一个操作(OP)入操作位栈, 操作位+1, 栈顶 = 操作位

具体实现中, 可以使用链表模拟栈. 然后设计上尽量使用可以直接调用free就能释放的Trivial数据, 原因后述.

装饰操作

替换操作很常见:

  • 将范围[2, +2]的泥壕, 替换为长度为2的你好
  • 这个按下撤销键, 会先删除你好再添上泥壕, 可以简化为两个OP:
  • (1). 将范围[2, +2]的泥壕删掉
  • (2). 在位置为2的地方插入长度为2的你好

这样就是将现有问题转换为已知的问题: 删除和插入是最基本的操作(坐下坐下这是基本操作). 但是就有一个问题: 撤销会变成两次.

Scintilla

Scintilla是一个与本项目类似的代码编辑控制项, 作者提到富文本编辑器会把格式的修改也压入栈. 这个特性让他实为烦躁, 于是出现了Scintilla.

以上两点我们可以用一个装饰的标志解决, 将后面的装饰性操作打上标志:

STACK-TOP
OP <- 独立的操作
OP +decorator <- 装饰操作
OP <- 与上面的装饰操作作为一个整体的操作
OP +decorator <- 装饰操作
OP +decorator <- 装饰操作
OP <- 与上面两个装饰操作作为一个整体的操作

例子: 将type替换成class , 然后输入if

STACK-TOP
OP: 输入
OP: [装饰, 词法解析器检测到关键字] 将if设为蓝色
OP: 插入if
OP: [装饰, 词法解析器检测到关键字] 将class设为蓝色
OP: [装饰, 实际是替换操作插入部分] 插入class
OP: 删除type

程序语言级可以用begin_op和end_op之类的函数包裹实现:

void demo(void) {
// 替换type->class
 begin_op();
remove_text(type);
insert_text("class ");
do_parser();
end_op();

// 插入if
 begin_op();
insert_text("if");
do_parser();
end_op();

// 输入
 begin_op();
insert_text(" ");
do_parser();
end_op();
}

void insert_text(const char[]) {
// 具体实现

// 操作记录
 if (op) {
// 撤销栈操作以0开始
 // 0到下一个0, 这个前闭后开区间为一个完整的撤销栈操作
 // 超过0的作为装饰操作
 gui_op.op = op - 1;
op++;
}
}

void begin_op(void) {
op = 1;
}

void end_op(void) {
op = 0;
}

当然, 这是将富文本操作作为装饰的一种实现方式, 实际上还是把富文本操作记录在撤销栈上了.

使用begin_op和end_op之类的函数包裹的话, 还有一种实现就是完全将富文本操作排除在撤销栈操作外, 每次都由词法解析器进行富文本更新.

// 插入if
begin_op();
insert_text("if");
end_op();
do_parser();

好处是不会记录在撤销栈上, 坏处是撤销/重做后还要调用do_parser().

换行符

编辑器是允许中途更换换行符的, 这时候直接使用撤销栈会造成报道上的偏差.解决方法有:

  1. 修改换行符时修改撤销栈上所有OP
  2. 不直接保存绝对长度信息(总偏移), 而是相对信息(行号+行内偏移)

这里选择了后者, 方便全局编写

平平无奇撤销栈

撤销栈储存的OP必须是平平无奇的(trivial), 主要有两个特点:

  1. 没有析构操作, 或者说唯一的析构操作就是释放空间(std::free())
  2. 核心数据没有指针, 全部是偏移量
图中bytes_from_here之后没有指针, 全是连续排列的, 并且对齐RED_RICHED_ALIGNED

这样的好处有:

(1) 无需担心对象所有权. 内联对象, 特别是图片是相当消耗储存空间. 不可能显示保存一份, 撤销栈保存一份. 所以撤销栈上图片保存的仅仅是一种简略信息的引用. 比如引用计数什么的.

不过引用计数之类的会有析构之类的操作, 作为历史保存不太合适: 明明文档中不存在, 但是因为撤销栈存在引用就必须储存在内存中. 所以干脆平凡化: 储存简略信息, 比如uri字元串.

(2) 上面是没有析构操作的好处, 这里是没有指针的好处: 储存偏移量几乎可以不加修改地直接将二进位信息存储在硬碟上, 即可以将撤销栈完整地、简单地存储下来.

(3) 上面这一点可能不太吸引人, 但是可以作为二进位文件编码, 将富文本以二进位形式直接储存下来.

富文本怎么保存? xml? rtf? 这些都是与其他程序交互时使用! 并且还要涉及到解析和标准什么的(光rtf解析就够吃一壶了). 自己用的, 直接储存撤销栈然后重现就行: 完毕后将全部字元串删掉, 将撤销栈最后一步保存下来(当然只是为了方便说明, 实际直接记录就行).

即: 超简单的序列化(Serialization)的实现.

当然, 没有指针的话, 空间的消耗将是最小的, 也算是一大优点. 以及也可以用于相同编辑框数据交换的类型, 例如操作系统的下的复制粘贴. 平平无奇+无指针, 强, 无敌.

大概具体的实现

富文本插入:

  • 撤销: 插入的数据删除, 需要数据: 起点与重点
  • 重做: 将插入的富文本插入回去, 需要数据: 起点, 富文本数据

富文本删除:

  • 撤销: 将插入的富文本插入回去, 需要数据: 起点, 富文本数据
  • 重做: 插入的数据删除, 需要数据: 起点与重点

内联对象插入:

  • 撤销: 将插入的数据删除, 需要数据: 起点(长度假定为1)
  • 重做: 将插入的内联对象插入回去, 需要数据: 起点, 内联对象

内联对象删除:

  • 撤销: 将插入的内联对象插入回去, 需要数据: 起点, 内联对象
  • 重做: 将插入的数据删除, 需要数据: 起点(长度假定为1)

可以看出插入与删除完全就是相反的, 我们将对象进行分解:

  • 内联对象的插入与替换
  • 富属性的修改与回退
  • 纯文本的插入
  • 范围删除
  • 无视

请注意, 这里内联对象的替换并不是真正的意义上的替换. 不会对文本长度造成影响, 完全是为撤销服务的. 所以自己就称之为升阶(Rank-Up), 需要调用RankUpMagic完成替换.

平平无奇的实现

  1. 装饰操作
  2. 平平无奇

综合之前所述的平平无奇撤销栈操作, 没有析构步骤, 以及装饰物. 演算法如下:

删除:

  • 删除操作是不分对象的
  • 将范围内特殊对象按顺序记录, 装饰OP +1
  • 将范围内记录所有富属性, 装饰OP +1
  • 将范围内记录所有纯文本, 装饰OP +1
  • 范围删除

即:

  • 内联对象撤销: 内联对象的的升阶
  • 内联对象重做: 无视
  • 富属性撤销: 富属性的修改
  • 富属性重做: 无视
  • 纯文本撤销: 纯文本的插入
  • 纯文本重做: 范围删除

装饰OP的范围需要给出一个大概范围, 这里可以看出最大是+3. 之所以需要判断范围, 是因为有限撤销栈的实现:

  • 完整记录OP后(调用end_op())检查数量
  • 如果OP数量超过范围, 获取撤销栈(队列)末尾OP
  • 遍历到第二个OP的开头(用装饰OP判断)
  • 如果 当前撤销栈长度 减去 第一个OP的长度, 如果大于等于范围
  • 将第一个完整的OP释放掉, 第二个OP作为新的第一个OP

插入对象

由于插入只能插入一种, 所以后面将会很简单. 插入内联对象则是:

  • 装饰OP +1
  • 撤销: 范围删除
  • 重做: 内联对象的插入

插入文本

由于只能插入纯文本(富属性单独设置), 插入是比较简单的.

  • 装饰OP +1
  • 撤销: 范围删除
  • 重做: 文本的插入

富属性修改

同样, 修改只能将范围内修改为同一个属性, 和删除的差不多.

  • 装饰OP +1
  • 撤销: 富属性的回退
  • 重做: 富属性的修改

替换

之前提到了, 直接组合就行.

附加变化的实现

一般地, 如果连续按退格键, 撤销后会回到第一次退格前的位置. 所以针对输入单个字元和退格删除的实现, 我们需要检查一下是否可以与目前的OP进行合并.

具体实现中, 主动检查有点繁琐, 采用被动检查的方式. 好处就是降低耦合, 坏处就是效率会稍微低一点. 不过由于这些是GUI输入, 不会太频繁, 就如所谓了.

插入符号的变化

上面没有讨论插入符的更新, 这个只需要保存就行. 于是出现了一些专门为撤销栈实现的方法:


推荐阅读：
相关文章