Graph-Based Pattern-Oriented, Context-Sensitive Source Code Completion

小灰灰 2022-03-11 12:42 127阅读 0赞

本文首先阐述目前存在的IDE中，例如eclipse等等，自动补全代码的效率太低。本论文目的在于提高代码自动补全效率，提高程序员编程效率。

**要解决的问题：**

IDE中代码自动补充问题，本文提出了一种新的方法GraPacc来提高IDE代码补全的效率。

**解决了什么难题，用什么方法克服？**

提高了IDE代码补全的效率。

采用基于API模式的方法，结合其他算法的优点，来进行代码补全。

代码补全的一些基础思路，不管是API使用模式，交错模式，基于图的模式这几种都是很不错的方法。使用API的模式，感觉类似于提取文章主题，把跟主题相关的词汇进行汇总，按照相关性进行排序，呈现给用户，供用户使用。

在网络上查找了一下，发现代码补全的论文不是特别多，中文文献没有，研究此方向的不是特别多。类似的基础研究，貌似没太有，比较冷僻。

**第一部分**介绍中，本论文阐述GraPacc方法，可以提高IDE补充代码得效率。经过测试，GraPacc可以达到95%的准确率。

本论文做出的主要贡献有以下几个方面：

1.  提出一种 基于API使用模式的基于图的特征提取，寻找，分级的算法
2.  一种新型的基于图的代码补全算法（简单看了看，以前的算法也有基于图的）
3.  GraPacc在其特点之外，还考虑了正在编码的这个过程。在编码过程中，不断优化代码补全的策略，还考虑到了API的使用情况
4.  一个综合经验方法来测试GraPacc的准确度

**第二部分**简单阐述了API使用模式，替换模式，交错模式，与基于图的模式。四种模式对于GraPacc在处理代码补全的策略上有不同的启发。

**第三部分**中的重要概念，主要讲了模式，Query，Groum与特征的解释与定义。

1.模式包括在敲代码中使用到的类，方法，变量名与整个代码得流程架构。

2.Query我觉得可以理解为正在敲的这一行代码，还没有敲完，着重于正在进行的这个状态。

3.Groum是一种基于图的模型，其中的节点代表函数名，数据变量名称，与控制模块结构等。边就代表点之间的依赖于控制行为。

4.特征分为两种：（1）基于图的特征：在Groum模型中，沿着边走到节点的原文标签 的一个序列。

（2）基于标签（令牌）的特征：是从query提取的词汇的标签

在GraPacc方法中，会对于query进行特征提取，即使query很少。

为了测量两个特征之间的相似度，GraPacc定义了**sim**函数来进行比较，sim函数主要比较二者的文意相似度与他们之间的单词顺序。

同时GraPacc还考虑了query的语境信息。模型通过**context-sensitive weights**来衡量语境信息，

基于以上两点，GraPacc定义了query与模式的相似度测量手段：**fit**函数，fit函数主要用来对于候选模式对于query的分级。具体细节第四部分会说到。

**第四部分**主要讲了对于正在编程的**语句处理**与**特征提取**

Query处理：

1.  将query进行标签化，生成基于标签的特征。
2.  使用PPA工具来将输入的代码将其描述为AST（抽象语法树）
3.  对照着AST建立Groum模型
4.  从Groum收集基于图的特征，再收集基于标签的特征，然后对于提取的特征，进行语境相似敏感权重的判断。

特征提取：

1.  GraPacc将每一个图中节点特征，与之前建立的标签化特征一一对应。
2.  在对照之后，没有在Groum上面对照的节点，会被当做一个基于标签的特征。
3.  从Groum中不同的路径提取出不同的特征。
4.  考虑到有很多路径的存在，我们对于路径进行限制（小于3）。因为大量路径的存在会导致算法效率降低。

特征权重分配：

当特征被提取之后，我们用一个权重来表示其对于当前代码语境的敏感度

原式子在论文中能找到，我就不贴了

等式右边第一个参数，看了看介绍，大意是越长的特征代表的信息越多，给他的权重就越大。

第二个参数，大意是如果一个节点在整个Groum里，具有更高的集中性，就更重要，可以更好地用于匹配。

第三个参数，对于当前的编程环境的依赖关系来看，Wf(q)制作基于用户的因素q。就比如说在编写java图形界面的时候，写一个Button，Button就是核心代码，那么Button.new就比Shell.now重要。因为写了一个Buuton之后，肯定要实例化声明new它。

**第五部分**主要讲了模式管理与搜寻与评级

模式管理：

模式可以从模式挖掘工具（GrouMiner）中进行提取，或者由用户提供。为了支持基于特征的模式搜寻，GraPacc使用一种逆向索引搜寻工具。它能从模式中提取基于图的特征，并对每一个特征，生成一个list来进行存储。并且对于每一个feature，GraPacc使用权重衡量函数s(p,P)来表示特征p在模式中的重要性。

搜寻与评级：

本算法的一个重要步骤就是搜寻与代码相关的模式。有以下两个主要问题：

1.  可能需要模式在本地数据库没存
2.  数据库中模式的存储太大了，计算相似度的话太耗费CPU

针对第一个问题，采用sim函数来解决，设置一个临界值，超过临界值，就认为是相似的，没超过就不相似。针对问题二，设置相似度排名，只查找排名高的。

特征相似度计算与模式匹配简单看了看。用公式计算特征之间与模式之间的相似程度。

第六部分主要讲以模式为导向的代码补全

1.  在模式与语句中进行Groum的匹配
2.  完成query未完成的代码

后面的实验跟目录都没看。