在Emacs Lisp中保存大量位置对的最佳方法是什么？

Question

我正在将一个普通的全重启分词器（从原始语言解析器移植而来，此处语言无关）转换为更高级的增量分词器。这意味着以下几点：

a) 它必须快，非常快；

b) 每次文本更新（插入或删除）时，它必须查找受损的标记，并相应地修复标记列表。

原始分词器版本只是使用正则表达式遍历缓冲区文本并构建标记列表；列表中的每个标记都是一个由4个元素组成的向量（['TOKENTYPE "token-lexeme" linum charnum']）。Linum/charnum是指在进行词法分析时在缓冲区中的标记位置的纯数字。很容易理解。

现在，重点来了。每当（嗯...不是每次，但经常）用户添加或删除字符（或字符串）时，新分词器都必须找到一个使用更改位置中的文本构建的标记以及可能的依赖标记以供后续删除/更新使用。

这里有两个问题：

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

b) 找到受损标记（或大量标记）的方法。

现在我正在尝试使用覆盖来完成此任务，因为覆盖具有适合我的需求的良好接口：overlay-at/overlay-in函数可帮助搜索；而覆盖的起始/结束位置也可以以适当的方式移动。

对于较小的文件，我可以愉快地这样做。但事实证明（我必须承认，文档中已经警告过我），该解决方案无法扩展：即使是平均1K LOC文件也可能有CONST * LOC个覆盖，这对Emacs来说太多了。

那是我第一次尝试，它并不成功。我正在考虑替代方案，例如：

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

2) 相同的树，但使用标记；

3) 一种混合方法，包括纯数字和标记。

是否有其他替代方法？或者也许有更好的处理大量覆盖的方法？

- Vlad

---

相关：Emacs 中有 Wisent 和 semantic。可能你已经检查过了。还有一些高亮支持，例如 http://www.gnu.org/software/emacs/manual/html_mono/semantic.html#Highlight-Func-Mode。 - Tobias

@Tobias 当然，我确实查看过它们。实际上，很多次，甚至签署了FSF文件并为Java相关代码发送了一两个微小的补丁。这个特定的标记器旨在以不同的方式工作（希望是更好的 :-)），更像是替换字体锁定模式的实验。 - Vlad

Answer 1

像Lindydancer一样，我建议您使用文本属性而不是覆盖。 覆盖范围的缩放为O（N ^ 2），而文本属性的缩放为O（N log N），因此效果更好。 我不会将任何内容用于font-lock，但可以采用另一种解决方案：修复覆盖范围：C代码可以更改为使其为O（N log N）。 我已经知道如何做了一段时间，但是没有找到时间（在可预见的未来也不可能找到时间），因此如果有人感兴趣，我很愿意帮助他完成它。

- Stefan

---

最终，我不需要文本本身，只需要位置和与位置相关的叠加功能。事实证明，在这里使用文本属性将是一种不必要的复杂化...我会采用一些复杂的叠加方法，例如为一组标记使用单个叠加。你提到了叠加性能的改进...我对此很感兴趣，并且通常也想涉足Emacs C代码编写。也就是说，如果没有人急于（我肯定不急），我们如何在这方面合作？ - Vlad

顺便问一下，你知道关于标记实现的任何信息吗？它们是否像覆盖层一样有潜在问题？ - Vlad

标记也存在性能问题，这也是覆盖层运行缓慢的部分原因（由于每个覆盖层内部使用了两个标记）。如果您有兴趣在覆盖层上进行编程，请前往emacs-devel并说明您希望解决此问题的意愿，我们会从那里开始处理。 - Stefan

最近在emacs-devel上有一些关于这个问题的讨论；如果能解决性能问题就太好了 :) - Clément

Answer 2

除了覆盖层，还有一种更有效的选择是“文本属性”，它们以一种覆盖层无法实现的方式附加到文本上。

一个广泛使用文本属性的软件包是“font-lock”。通常，它被用于突出显示缓冲区，但你也可以接管它，用于自己的目的。这样你就能免费获得侦测用户修改缓冲区内容的整个系统。

在你的情况下，你可以用一个搜索限制调用函数替换font-lock中的正则表达式关键字。你所要做的就是扫描相对较短的部分，设置你自己的文本属性，然后完成。 （同时，你必须使用“font-lock-extra-managed-props”告诉font-lock你正在设置哪个属性。）

- Lindydancer

---

问题在于我想避免使用字体锁定模式，并将其替换为增量标记系统，该系统可以以更精细的方式进行语法高亮（与正则表达式字体锁定使用的方式相比）。实际上，我已经检查了字体锁定代码，它也不是太智能。从快速研究中我所理解的就是它只是重新扫描缓冲区，从更改点开始（避免了一些特殊情况）。 - Vlad

没有想过以这种方式考虑文本属性...好的，我可以将一个令牌引用附加到一段文本上。这里出现了另一个问题。如何找到已删除的令牌？也就是说，没有被任何文本指向的令牌？使用覆盖层相当容易。 - Vlad

除了性能之外，使用覆盖属性或文本属性的问题涉及到这个问题：您想将属性及其值与缓冲区中的字符关联还是与缓冲区位置关联。如果是前者，则文本属性是一个自然的选择；如果是后者，则应该使用覆盖。 （您的问题标题表明这是关于缓冲区位置的问题，但这可能只是因为您的第一个实现基于覆盖层。） - Drew

就我所知，在这种情况下为什么要建议使用字体锁定，我并不确定。你可以在没有“font-lock-mode”的情况下使用文本属性（和覆盖）。 - Drew

@Drew 我不需要字符，我是在找到损坏后获取词元（字符）的。叠加层（或我将选择的任何机制）只是识别受损标记的一种方式。编辑后，我只有一个点（或区域），指示发生了更改。这个点必须用于获取相关的标记。在叠加层中，我只需执行“overlays-at”。 - Vlad

通常情况下，Emacs中的文本缓冲区可能会发生变化（移动、替换等）。特别是在这种情况下，人们有时对字符（文本）感兴趣，而不是缓冲区位置。如果您的情况不适用于此，并且您只关心缓冲区位置，而不是当前在这些位置的文本，则覆盖是一个自然的选择。但正如您所注意到的，它们可能很昂贵。 - Drew