88

许多编辑器和 IDE 都有代码完成功能。其中一些非常“聪明”，而另一些则不是。我对更聪明的类型感兴趣。例如，我看到 IDE 仅在以下情况下提供函数：a) 在当前范围内可用 b) 它的返回值有效。（例如，在 "5 + foo[tab]" 之后，它只提供返回可以添加到正确类型的整数或变量名的函数的函数。）我还看到他们将更常用或最长的选项放在前面的名单。

我意识到你需要解析代码。但通常在编辑当前代码时无效，其中存在语法错误。当它不完整并包含错误时，你如何解析它？

还有时间限制。如果需要几秒钟来完成一个列表，那么完成是没有用的。有时，完成算法会处理数千个类。

什么是好的算法和数据结构？

4

3 回答 3

68

我的 UnrealScript 语言服务产品中的 IntelliSense 引擎很复杂，但我将在此尽可能给出一个概述。VS2008 SP1 中的 C# 语言服务是我的性能目标（有充分的理由）。它还没有，但它足够快/准确，我可以在输入单个字符后安全地提供建议，而无需等待 ctrl+空格或用户输入.（点）。人们 [从事语言服务工作] 获得的关于这个主题的信息越多，我在使用他们的产品时获得的最终用户体验就越好。不幸的是，我使用的许多产品都没有如此密切地关注细节，因此我与 IDE 的斗争比我编码的要多。

在我的语言服务中，它的布局如下：

  1. 获取光标处的表达式。这将从成员访问表达式的开头走到光标所在标识符的结尾。成员访问表达式一般采用 形式aa.bb.cc，但也可以包含方法调用，如aa.bb(3+2).cc.
  2. 获取光标周围的上下文。这非常棘手，因为它并不总是遵循与编译器相同的规则（长篇故事），但在这里假设它确实如此。通常这意味着获取有关游标所在的方法/类的缓存信息。
  3. 假设 context 对象 implements IDeclarationProvider，您可以在其中调用GetDeclarations()以获取IEnumerable<IDeclaration>范围内可见的所有项目中的一个。在我的例子中，这个列表包含局部变量/参数（如果在方法中）、成员（字段和方法，除非在实例方法中，否则只有静态，并且没有基类型的私有成员），全局变量（语言 I 的类型和常量） '正在处理）和关键字。在此列表中将有一个名为 的项目aa。作为评估 #1 中表达式的第一步，我们从上下文枚举中选择名称为 的项目，为下一步aa提供一个。IDeclaration
  4. 接下来，我将运算符应用于IDeclaration表示aa以获得另一个IEnumerable<IDeclaration>包含aa. 由于.运算符与运算符不同->，我调用declaration.GetMembers(".")并期望IDeclaration对象正确应用列出的运算符。
  5. 这一直持续到我点击cc，其中声明列表可能包含也可能不包含具有名称的对象cc。我相信您知道，如果多个项目以 开头cc，它们也应该出现。我通过获取最终枚举并将其传递给我记录的算法来解决这个问题，以便为用户提供最有用的信息。

以下是 IntelliSense 后端的一些附加说明：

  • 我在实现中广泛使用 LINQ 的惰性求值机制GetMembers。我的缓存中的每个对象都能够提供一个计算其成员的函子，因此对树执行复杂的操作几乎是微不足道的。
  • 我不是每个对象都保留List<IDeclaration>其成员的 a ，而是保留 a List<Name>，其中Name是一个结构，其中包含描述该成员的特殊格式字符串的哈希值。有一个巨大的缓存将名称映射到对象。这样，当我重新解析文件时，我可以从缓存中删除文件中声明的所有项目，并用更新的成员重新填充它。由于函子的配置方式，所有表达式都会立即计算为新项目。

智能感知“前端”

当用户键入时，文件的语法错误多于正确。因此，我不想在用户键入时随意删除缓存部分。我有大量的特殊情况规则来尽快处理增量更新。增量缓存仅保留在打开文件的本地，并有助于确保用户不会意识到他们的输入导致后端缓存为文件中的每个方法等内容保存不正确的行/列信息。

  • 一个赎回因素是我的解析器很快。它可以在 150 毫秒内处理 20000 行源文件的完整缓存更新，同时在低优先级后台线程上运行自包含。每当此解析器成功（从语法上）完成对打开文件的传递时，文件的当前状态就会移动到全局缓存中。
  • 如果文件在语法上不正确，我使用ANTLR 过滤器解析器（对链接感到抱歉 - 大多数信息都在邮件列表中或从阅读源代码中收集）来重新解析文件以查找：
    • 变量/字段声明。
    • 类/结构定义的签名。
    • 方法定义的签名。
  • 在本地缓存中，类/结构/方法定义从签名开始，在大括号嵌套级别恢复为偶数时结束。如果到达另一个方法声明（没有嵌套方法），方法也可以结束。
  • 在本地缓存中，变量/字段链接到前一个未关闭的元素。请参阅下面的简短代码片段，了解为什么这很重要。
  • 此外，当用户键入时，我会保留一个重新映射表，标记添加/删除的字符范围。这用于：
    • 确保我可以识别光标的正确上下文，因为方法可以/确实在完整解析之间在文件中移动。
    • 确保 Go To Declaration/Definition/Reference 在打开的文件中正确定位项目。

上一节的代码片段：

class A
{
    int x; // linked to A

    void foo() // linked to A
    {
        int local; // linked to foo()

    // foo() ends here because bar() is starting
    void bar() // linked to A
    {
        int local2; // linked to bar()
    }

    int y; // linked again to A

我想我会添加一个我使用此布局实现的 IntelliSense 功能的列表。每张照片都位于此处。

  • 自动完成
  • 工具提示
  • 方法提示
  • 类视图
  • 代码定义窗口
  • 调用浏览器（VS 2010 终于将它添加到 C# 中）
  • 语义正确的查找所有引用
于 2009-08-02T23:59:54.623 回答
17

我不能确切地说出任何特定实现使用了哪些算法，但我可以做出一些有根据的猜测。对于这个问题， trie是一种非常有用的数据结构：IDE 可以在内存中维护项目中所有符号的大型 trie，每个节点都有一些额外的元数据。

当您键入一个字符时，它会沿着树中的路径走。特定 trie 节点的所有后代都是可能的完成。然后，IDE 只需要通过在当前上下文中有意义的那些过滤掉那些，但它只需要计算尽可能多的可以在选项卡完成弹出窗口中显示的内容。

更高级的 tab-completion 需要更复杂的 trie。例如，Visual Assist X有一个功能，您只需键入 CamelCase 符号的大写字母——例如，如果您键入 SFN，它会SomeFunctionName在其制表符补全窗口中显示该符号。

计算 trie（或其他数据结构）确实需要解析所有代码以获取项目中所有符号的列表。Visual Studio 将其存储在其 IntelliSense 数据库中，这是一个.ncb与项目一起存储的文件，因此它不必在每次关闭和重新打开项目时重新解析所有内容。当你第一次打开一个大项目（比如说，一个你刚刚同步表单源代码控制的项目）时，VS 将花时间解析所有内容并生成数据库。

我不知道它如何处理增量更改。正如您所说，当您编写代码时，90% 的时间它都是无效的语法，并且每当您空闲时重新解析所有内容都会给您的 CPU 带来巨大的负担，而收益却很少，特别是如果您正在修改包含的头文件大量的源文件。

我怀疑它要么（a）仅在您实际构建项目时（或者可能在您关闭/打开它时）重新解析，或者（b）它进行某种本地解析，它仅在您刚刚解析的地方解析代码以某种有限的方式进行编辑，只是为了获取相关符号的名称。由于 C++ 具有如此复杂的语法，如果您使用繁重的模板元编程等，它可能会在黑暗的角落里表现得很奇怪。

于 2009-08-02T23:12:30.043 回答
1

以下链接将进一步帮助您..

语法高亮：用于语法高亮的快速彩色文本框

于 2012-04-01T08:21:43.210 回答