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

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

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

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

6 个赞

https://www.cs.unm.edu/~crowley/papers/sds.pdf

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

http://www.averylaird.com/programming/the%20text%20editor/2017/09/30/the-piece-table

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

学术帝你好. 学术帝再见

1 个赞

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

1 个赞

心得:

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 个赞