用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輸入, 不會太頻繁, 就如所謂了.

插入符號的變化

上面沒有討論插入符的更新, 這個只需要保存就行. 於是出現了一些專門為撤銷棧實現的方法:


推薦閱讀：
相关文章