emacs - 在 Emacs Lisp 中保存大量位置对的最佳方法

Question

我正在将通常的完全重启分词器(从原始语言解析器移植过来，这里的语言无关紧要)转换为更高级的增量分词器。这意味着以下几点:

a) 它必须很快，非常快；

b) 在每次文本更新(无论是插入还是删除)时，它都必须找到损坏的 token 并相应地修复 token 列表。

最初的分词器版本只是在使用正则表达式浏览缓冲区文本时构建一个标记列表；列表中的每个标记都是 4 个元素的向量(['TOKENTYPE "token-lexeme"linum charnum])。 Linum/charnum 是纯数字，指定词法分析完成时缓冲区中的标记位置。简单的馅饼。

现在，切入正题。每当(嗯……不是每次，但经常)用户添加或删除字符(或字符串)时，新的标记器必须找到使用更改位置的文本构建的标记，并且可能是依赖标记以供以后使用删除/更新。

这里有两个问题:

a) 标记位置应该是动态的(即如果用户在缓冲区的开头添加了一些文本 -> 我们不应该费心在缓冲区末尾修复标记)；

b) 一种获取损坏的 token (或一般的大量 token )的方法。

现在我正在尝试使用叠加来完成任务，因为叠加有一个适合我需要的漂亮界面:overlays-at/overlays-in 函数有助于搜索；并以适当的方式覆盖开始/结束移动。

对于较小的文件，我可以很高兴地做到这一点。但事实证明(我不得不承认我被文档警告过)该解决方案无法扩展:即使是平均 1K LOC 文件也可以具有 CONST * LOC 覆盖，这对于 Emacs 来说太多了。

那是我的第一次尝试，并没有成功。我正在考虑替代方案，例如:

1) 使用普通数字管理手写标记搜索树；

2) 同一棵树，但使用标记；

3)某种混合方法，包括普通数字和标记。

提到的方法有什么替代方法吗？或者也许有更好的方法来处理大量叠加？

Answer 1

像 Lindydancer 一样，我建议您使用文本属性而不是叠加层。覆盖缩放像 O(N^2) 而文本属性缩放像 O(N log N)，所以它工作得更好。我不会对其中任何一个使用字体锁定，不过。

当然，另一种解决方案是修复覆盖:可以更改 C 代码以使其成为 O(N log N)。我已经知道如何做有一段时间了，但还没有找到时间(并且在可预见的 future 不太可能找到时间)，所以如果有人感兴趣，我会很乐意帮助他做这件事。