代码完成如何工作？

Question

许多编辑器和IDE都有代码完成.其中一些非常"聪明",其他人则不是.我对更智能的类型感兴趣.例如,我已经看到IDE只提供一个函数,如果它是a)在当前范围内可用b)它的返回值是有效的.(例如在"5 + foo [tab]"之后它只提供返回可以添加到正确类型的整数或变量名称的东西的函数.)我还看到他们将更常用或更长的选项放在前面的清单.

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

还有时间限制.如果需要几秒钟来完成列表,则完成是无用的.有时,完成算法处理数千个类.

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

Answer 1

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

在我的语言服务中,它的布局如下:

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

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

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

智能感知"前端"

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

• 一个救赎因素是我的解析器很快.它可以在150ms内处理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#)
• 语义正确查找所有引用

Answer 2

我不能确切地说出任何特定实现使用的算法,但我可以做一些有根据的猜测.一个线索是这个问题的一个非常有用的数据结构:IDE可以保持在所有项目中的符号的一个大的内存线索,在每个节点的一些额外的元数据.

当您键入一个字符时,它会沿着trie中的路径向下走.特定trie节点的所有后代都是可能的完成.然后,IDE只需要在当前上下文中对那些有意义的那些进行过滤,但它只需要计算在tab-completion弹出窗口中可以显示的数量.

更高级的制表完成需要更复杂的特里.例如,Visual Assist X有一个功能,您只需要键入CamelCase符号的大写字母 - 例如,如果键入SFN,它会SomeFunctionName在其选项卡完成窗口中显示符号.

计算trie(或其他数据结构)确实需要解析所有代码以获取项目中所有符号的列表.Visual Studio将其存储在IntelliSense数据库中,这是一个.ncb存储在项目旁边的文件,因此每次关闭并重新打开项目时都不需要重新解析所有内容.第一次打开一个大型项目(例如,一个刚刚同步的源代码控制),VS将花时间解析所有内容并生成数据库.

我不知道它如何处理增量变化.正如你所说,当你编写代码时,它在90%的时间内都是无效的语法,并且每当你闲置时重新解析所有内容都会对你的CPU造成巨大的负担,但收效甚微,特别是当你修改包含的头文件时大量的源文件.

我怀疑它是(a)只在你实际构建项目时(或者可能在你关闭/打开它时)进行重新分析,或者(b)它进行某种局部解析,它只解析你刚才所在的代码以某种有限的方式编辑,只是为了得到相关符号的名称.由于C++具有如此非常复杂的语法,如果你使用大量的模板元编程等,它可能在黑暗的角落表现得很奇怪.