代碼編輯器系列 #2 文本的存儲 遠古篇
來自專欄千里冰封被吊打的日常
原文鏈接
ice1000.org在上一篇文章中我介紹了提到了兩種代碼編輯器—— LSP 式和 JB 式的區別，並表明以後的文章會是關於 JB 式的編輯器的。那麼這篇文章先說點別的吧。
我自己的實驗項目里是直接使用 Java 的StringBuilder 作為文本存儲工具的（由於 Swing 的 API 看起來更低效，所以我直接在這個地方棄療了），
因為 Java 的 String 是 immutable 的，對大規模的讀寫、插入刪除、拼接拆分非常不友好，於是我就使用了相對高效的、使用數組作為 buffer 的 StringBuilder（至少比拿 String 拼來拆去好一些）。
StringBuilder 應該是眾多支持簡單插入刪除的字元串存儲數據結構中最蠢的了（和 ArrayList<Character> 差不多），這裡用只是因為這並不是當時寫編輯器時關心的重點。
這個東西學問非常大，這裡就先聊聊遠古編輯器 Vim 和 Emacs 各自所使用的字元串存儲數據結構吧。
Emacs
Emacs 使用的數據結構相當簡單，叫做『gap buffer』。
這種數據結構的優點有很多，顯而易見的是它的簡單性（易於實現），以及針對小文件的性能很不錯（是 piece table 的論文說的，其實我不太明白為什麼）。
它的缺點也很明顯，遇到大文件的時候非常崩潰，以及難以應付大規模的插入刪除（比如刪除或者粘貼大段文本），並且對惰性地、部分地讀寫文件非常不友好。它的實現有很多，比如 Flexichain（04 年的論文，比較簡單，至少我感覺讀下來沒太多收穫，不過列舉了不少編輯器的實現，還算可以）.
簡易實現
舉個例子，比如我們有這麼一個字元串 Hi, world!，然後游標在 , 前面，用 IntelliJ 的測試框架的數據集表示方法的話就是 Hi<cursor>, world!。
xx 表示 ASCII 碼為 16 進位數 xx 的字元）：
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d]H i 0 0 0 0 , w o r l d !
然後當用戶刪除一個字元後，變成這樣：
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d]H 0 0 0 0 0 , w o r l d !
然後用戶輸入 ello，變成這樣：
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d]H e l l o 0 , w o r l d !
然後用戶右移了一下游標，變成這樣：
[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [a] [b] [c] [d]H e l l o , 0 w o r l d !
大概就是這樣了，如果遇到 buffer 滿了的情況就需要重新分配內存然後複製數據，所以面對大文件就比較蛋疼了。
我們用這種方式表示整個編輯流程：
Hi<cursor>[ ], world!H<cursor>[ ], world!Hello<cursor>[ ], world!Hello,<cursor>[ ] world!
Variations
有個我覺得很可取的做法，來自 Hemlock 編輯器（論文， 1989 的）。
它把文本按行分成一個鏈表，游標所在的那一行是 gap buffer ，其他行是直接存的字元串。
它很明顯可以有效緩解巨大的、每行其實不怎麼長的文本的編輯時的內存和時間開銷，但單行大文件依然無解，不過這是個比較少見的情況，因此它還是能解決一些問題的。順帶一提，這個 30 年前的文本編輯器有一股挺濃的 Emacs 的味道，不知道是誰先來的，反正已經變成這樣了。
Vim
Vim 使用的數據結構相對 Emacs 要複雜一些，但是對於 OI/ACM 選手來說依然是小兒科。
名字叫做『rope』，又名『cord』，本質就是對字元串特化的平衡樹（應該和具體哪種平衡樹沒關係，論文里說的是 Splay，但我感覺其他的平衡樹也可以做到一樣的效果）。論文是 1995 年的，比 Flexichain 那個還老，有偽代碼實現和一個比較嚴謹的 benchmark ，算是一些有趣的內容。
裡面提到了不少現在已經是歷史的眼淚的編程語言，比如活躍於 60 年代、已經被 90 年代的 Python、Ruby 之流取代的已經被 70 年代的 Perl、AWK 之流取代的 Cedar 編程語言和 SNOBOL 編程語言（這個似乎還有好幾代）。簡易實現
由於它真的就只是對字元串特化的平衡樹，所以插入刪除查詢之類的操作就不講了（我覺得你們應該都會寫平衡樹），這裡討論一下它對最小粒度的字元串的抽象。
由於這個平衡樹是對字元串特化的而不是對字元特化（不然就是BalancedTree<Character> 了，就沒意思了）的，它在處理不同量級的、不同來源（來自文件（中等成本讀寫）、內存（低成本讀寫）、網路（極高成本讀寫）、壓縮文件（較高成本讀寫））的文本的時候可以使用不同的『字元串』。
這裡的字元串是個抽象概念，它可以是：
- 一個
std::string或者java.lang.String這類東西的實例 - 一個返回上述實例的函數，比如惰性的字元串，或者文件解壓的 callback
- 另一種對這一小段文本更適合的字元串存取數據結構的實例
所以這個平衡樹其實可以只作為一個上層抽象，然後把細粒度的字元串用其他更優的數據結構表示出來。
Benchmark
自己看論文去
更深層次的抽象
受 Rope 的啟發我們可以想到，字元串並不一定需要是 List<Character>，我們應該視之為 List<Item>，然後這個 Item 應該可以有多種實現，
Character 或者 String。字元串也可以以惰性的形式存儲，這種惰性的字元串也可以是一種 Item。這種抽象思路同樣適用於 gap buffer 一類的數據結構。
再往上我們可以抽象文件的概念了——這個留到以後講虛擬文件系統（IntelliJ Platform 的一個東西）的時候再討論。
推薦閱讀：