图形编辑器：历史记录设计
大家好，我是前端西瓜哥。今天讲一下图形编辑器如何实现历史记录，做到撤销重做。
其实就是版本号的更替。每个版本保存一个状态。
数据结构
要记录图形编辑器的历史记录，支持撤销重做功能，需要两个栈：撤销（undo）栈和重做（redo）栈。
每当用户进行一个操作（比如移动一个图形），就会产生一个新的版本，将这个操作产生的状态保持加入到 undo 栈顶，此外 redo 栈会清空。因为用户可能撤销了几次然后产生了新的操作，无法重做它们了。
当用户撤销，undo 栈出栈，并放到 redo 栈，然后使用 undo 栈顶的状态。当用户重做时，redo 栈出栈，再放到 undo 栈上，并应用 undo 栈顶的状态。
原理大概这样。
浏览器的回退前进的表现其实就是一个很常见的例子。
数据结构还有另一种方案：双向链表加两个指针，一个指针指向当前版本状态，另一个指针指向 redo 最后一次可执行到达的状态。
然后是如果要支持协同的场景，你的撤回不会回到之前的版本，而是将之前的版本的状态拿出来作为一个新的版本。
然后是协同中你不能撤回别人的操作，只能撤回自己的，并且要用协同算法处理和其他协同者的冲突逻辑。
要保存哪些状态
那么我们的状态要保存哪些状态呢？
- 图形树数据
- 图形树需要的引用
- 一些设置
图形树是必要的，我们需要用它渲染画布内容。此外还有游离在图形树之外的被用到的对象，比如图层、被多次引用的图形。你可以也把它们也放到图形树里面去。
最后是一些需要共享的设置，比如表格的行高、筛选条件等。
像是颜色主题、国际化语言设置则不需要历史记录，它是用户自己选择的个性化定制。
我们看具体的几种实现。
全量快照
每次操作的到的新状态，完全拷贝一份保存起来。
因为对象如果只是浅拷贝，其中的引用对象可能会被意外的修改，通常我们会选择 序列化成字符串 保存，即JSON.stringify。撤销重做的时候再解析出来作为当前状态。
优点是实现简单。
缺点是当状态很大的时候，每次生成快照都会比较耗时，且操作很多产生很多版本时，需要大量的内存空间保证这些完整状态。
如果画布上有一万个独立的实体，就意味着每进行一次操作，就要将这个一万个实体深拷贝一份。100 次就是 100w，很恐怖。
仅推荐简单的图形编辑器使用，或者做 demo 用。
补丁（patch）
全量快照让编辑器的上限很低，不是最优解。
一种更好的解法，是 打补丁（patch）。
基于上一个版本 1，打一个补丁，变成下一个版本 2。同时我们记录一个反向的补丁，撤回的时候能通过它从版本 2 回到版本 1。
这个方案对应了设计模式的 命令模式，我们构建 Command 类，这个类有 execute、redo、undo 方法，这些方法会对传入的旧的状态对象打补丁，得到一个新的状态。
比如添加矩形命令，execute 和 redo 时我们会往图形树的末尾加一个矩形对象，undo 就是将这个矩形从图形树中移除。undo 栈和 redo 栈此时记录的就是一个个 command 对象了。
纯纯用朴实无华的命令模式去实现，还是有点坑的。因为要实现的命令太多了，比如添加图形、修改图形属性、删除图形、对几个图形做右对齐等，这些都要自己一个个实现 redo 和 undo。复杂一点就要抓瞎，建议找一些轮子。比如 immer、y.js。
使用补丁方案还有一个好处，就方便实现 “动作” 功能。（当然这不是一个优先级很高的功能）
比如我们想要给一个图形先顺时针旋转 45 度，然后向右移动 10 个单位，我们希望记录这两个操作，给其他图形也应用这些操作。
快照的方式就不好搞，或许我们可以对比新旧状态找不同推断出行为，但不好搞。因为属性的变化可能来自不同的操作，比如移动，可以通过移动工具相对位移产生，也可能直接属性面板改 x 值，也可能是通过对齐操作产生的。
patch 就很适合。
什么时候保存状态
我们需要确认一个操作完成的时刻，将它加入到历史记录中。
我们操作图形，会产生一些 中间状态。比如移动一个图形，拖拽的过程中不生产一个历史版本，直到拖拽结束才记录。
一种方式是：操作图形的替身，操作结束后才更新真正的状态。
一些编辑器，比如 Adobe Illustrator、AutoCAD，我们在操作图形的时候，会看到一个临时的替身，就是将被选中图形的轮廓线或拷贝做鼠标的跟随，释放后才真正修改图形属性。
还比如颜色的修改，在拾色器中挑选颜色时不会立即修改图形，在点击确认才真正修改图形。
另一种方式是：直接操作真正的状态，在操作结束的时候，记录这个时刻的状态。
第一种方式的好处是，状态没有中间状态，替身操作完，计算出新状态应用到真正的状态上就好了。
第二种方式就要额外在操作开始时，保存原始状态的快照，因为之后我们会产生中间状态，然后在操作结束后计算 patch。
但第二种方式用户体验会更好些，用户能实时看到一个图形的变化，判断是不是自己需要的效果，而不是看到一个 “通往未来的幻影”。
结尾
我是前端西瓜哥，关注我，学习前端不迷路。