圖形編輯器：歷史記錄設計
大家好，我是前端西瓜哥。今天講一下圖形編輯器如何實現歷史記錄，做到撤銷重做。
其實就是版本號的更替。每個版本保存一個狀態。
數據結構
要記錄圖形編輯器的歷史記錄，支持撤銷重做功能，需要兩個棧：撤銷（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。
但第二種方式用戶體驗會更好些，用戶能實時看到一個圖形的變化，判斷是不是自己需要的效果，而不是看到一個 “通往未來的幻影”。
