分享一篇关于历代 Emacs 中 buffer 实现的论文。

Emacs-general
1

最近在研究如何写编辑器。

另外可能是因为后来才出现，Emacs 似乎没有用 rope 的。 有点好奇 GNU/Emacs 的 undo 是如何实现的。

当然 GNU/Emacs 长行卡顿不是 buffer 实现有问题，主要原因似乎是因为字体渲染需要遍历计算每行高度

6 个赞
2

这一篇着重介绍了 piece table，这种实现是 VSC 所使用的。优点是能够高效编辑极大文件，以及快速的 unto/redo 功能。

另外有一篇比较通俗的比较上面 gap buffer, rope, piece table 三种实现的文章。

3

学术帝你好. 学术帝再见

1 个赞
4

其實一开始能选合适的算法比后面搞优化强多了

1 个赞
5

心得：

Advanced editable history manage on top of piece table and flexichain

:warning: Warning: :warning: 理解本文需要先理解上面的论文提到的 flexichain 和 piece table。并对编辑器实現有一定了解。

Fleixchain 是用 Common Lisp 实現的 Gap buffer，比較其他实現它特有一個 cursor 功能：

Whenever an object is inserted before the position of a cursor, the position of the cursor will be incremented. Conversely, whenever an element is deleted from a position below that of a cursor, the position of the cursor is decremented.

而且：

There can be a very large number of cursors in a chain without any negative impact on performance.

标准的 Piece Table 是 one read only array of original text, one append only array for inserted text, a table of reference to arrays of beg & end.

如果我們将它实現成：two flexichains (gap buffers) of text, a table of reference to flexichains of beg & end cursors.

那麼我們就可以做出一个有极其强大 Undo 功能的编辑器，它將在无较大性能損失前提下轻易实現如下特点：

  1. Command History represents Buffer content，Buffer content is intact Command History
  2. Edit Command History is edit Buffer content

如果我們实現一個基于指令的文本编辑，用三個指令写出 This looks good：

1. Insert This is good.
S(creen): This is good

2. Jump 3. Insert looks
S: This looks is good.

3. Jump 11. Delete 3
S: This looks good.

然后直接编辑命令历史：

+1. Insert This is not good.
-1. Insert This is good.

屏幕上就会变成 This looks not good。

还有个更厉害的。

1. Insert foo
S: foo

2. Copy 0-2 3 times
S: foofoofoo

然后修改第一个命令：

+1. Insert barz
-1. Insert foo

屏幕上显示的就是 barzbarzbarz 了！

ps. 实际上我用做例子语言有些误导性，历史记录中表述移动光标用的不应该是绝对位置，而是要相对位置。

1 个赞