曹英魁 ,孙泽宇 ,邹艳珍 ,谢 冰
1(北京大学 信息科学技术学院,北京 100871)
2(高可信软件技术教育部重点实验室(北京大学),北京 100871)
在开发过程中,开发人员常常面临着相似的代码修改任务,而完成这些任务不仅需要耗费开发人员大量的时间和精力,同时,开发人员在完成重复的任务时又容易引入新的错误[1,2].得益于不同形式的版本控制系统,软件项目的演化历史得以完整地记录下来.在这些演化历史中,存在着丰富的代码修改场景和修改方案[3-6].基于已有的相似代码修改,研究人员开始关注于相似代码自动转换方法的研究,即:给定一组示例代码修改,通过对修改示例的修改方式进行抽取和表示,并基于表示结果来实现对相似代码的自动修改.
在早期工作中,代码修改的自动转换多是采用人工特征工程的方式[7-11],即人工地提出规则对修改示例中的修改方案的适配条件、修改过程和修改结果进行限定和说明.然而,这些规则的提出往往基于研究人员对特定语言的专家知识,并需要耗费大量的时间精力来总结、提炼.近来,采用基于机器学习的代码转换方法[12,13]不断涌现出来.常见的做法是采用端到端的翻译模式,将待修改的代码“翻译”为修改后的代码.然而,现有的工作尚未对修改示例的结构信息充分加以使用.一方面,一些现有工作利用翻译模型,直接将修改前的代码“翻译”为修改后的代码.然而,在缺失修改示例信息的条件下,试图训练一个全局的翻译模型来处理代码转换任务,无疑是十分困难的.另一方面,相比于自然语言,代码内的信息存在着更为显著的长程依赖.如图1 所示,函数调用fis.close()中的变量名fis,与最初声明的变量名为同一个变量.现有工作在采用时序模型对代码信息建模时,由于两处代码间隔很远,很难捕获两处变量间的依赖关系.
Fig.1 Long dependency among variable names图1 变量名间的长程依赖
针对上述问题,本文提出了一种利用结构信息增强代码转换的方法ExpTrans.一方面,给定修改示例,方法将修改前和修改后的代码解析为抽象语法树,并寻找其节点间的对应关系.基于节点间的对应关系,方法采用图的形式来表示给定的示例代码修改,以增强模型对代码修改中的结构信息的捕获能力;另一方面,方法通过将图卷积网络和Transformer 架构[14]有效地结合来增强模型对代码间的依赖信息,尤其是长程依赖关系的捕获能力.
方法整体上遵循encoder-decoder 的架构设计.其中,编码器分别对待修改代码、修改示例代码以及中间信息进行建模;解码器依据编码器的编码结果,预测转换后的代码.为了保证方法产生的代码的可编译性,方法在预测修改后的代码时,借鉴了Yin 和Sun 等人的工作[15,16],以预测指令序列的方式来产生代码.所谓指令,形如α→β1β2…,其所代表的含义是在代码的抽象语法树中的类型为α的节点上,插入子节点,类型分别为β1、β2….具体地,在产生代码的过程中,方法将维持一棵表示中间结果的抽象语法树,并基于预测的下一条指令,对当前最左的待扩展的节点进行扩充,直至所有的非叶子节点被扩展完毕,所生成的抽象语法树所对应的代码即为转换后的代码.
为了验证方法的有效性,本文在两个数据集上进行了对比实验.第1 个数据集是Yin 等人对外开放的111 724个C#代码修改[13].实验结果表明,对比Yin 的工作(基于深度学习)[13],本文方法在准确率上有11.8%～30.8%的提升.第2 个数据集是从GitHub 上收集整理的6 组Java 语言典型的相似代码修改.在该数据集上,分别将本文方法、GenPat 方法[17](基于人工规则)和ARES 方法[10](基于人工规则)用于自动修改这些代码实例.实验结果表明,在每组数据中,均有实例被ExpTrans 正确修改,并且在一组数据上的实例全部被ExpTrans 正确修改.相比于GenPat 和ARES 方法的结果,ExpTrans 的结果在准确率和正确修改的实例的数量上,均有大幅度提升.
本文的贡献主要表现在:(1) 提出了一种基于图的代码修改表示方法.相比采用单词序列的表示方式,图结构能够更加准确地表示代码修改过程,增强了方法对代码修改中结构信息的捕获能力.(2) 提出了一种基于Transformer 架构的结构信息增强的代码修改自动转换方法.该方法采用特殊的copy 指令显式地表示代码间广泛存在的变量声明与使用的依赖关系,增加了模型对代码中长程依赖信息的捕获能力.(3) 本文在两个数据集上开展了对比实验并将数据全部公开(https://github.com/caoyingkui/ExpTrans).相比于现有的机器学习方法,本文方法ExpTrans 在准确率上提升了11.8%～30.8%.对比基于人工规则的方法,在修改实例的准确率和正确修改的实例数量上均有显著提升.
本文第2 节介绍已有的相关工作.第3 节介绍基于预测指令序列的代码产生方式,以及本文方法的整体框架.第4 节介绍本文方法的具体实现细节.第5 节介绍为了验证方法有效性而开展的实验以及实验设置和实验结果.最后,第6 节对本文工作进行总结.
如前所述,本文的相关工作分为两类:一类是基于人工特征的方法,另一类是基于深度学习的代码修改自动转换方法.
2.1 基于人工特征的方法
该类工作的主要思路是:基于人工提炼的规则,从给定的修改示例中,抽取一个代码转换“脚本”,以对示例中的修改条件、修改模式和修改过程进行说明和约束,并可以按照脚本中所约定的方式自动地适配到符合条件的代码区域并完成代码转换.在现有的工作中,这种脚本呈现出代码编辑序列[7]、模板[8]和特定领域语言(DSL)[11]等多种形式.
在Meng 等人提出的SYDIT 中,利用一组编辑操作序列来表示代码转换的过程[7].序列中的编辑操作共包含4 种类型:增加、删除、修改和移动一个AST 节点,同时利用通配符等方式编辑操作中的类型、位置信息以进行泛化.例如,!config.inValid()被表示为!v2.m5().按照顺序依次执行该序列中的操作,即可将代码修改为修改后的代码.LASE 是Meng 等人提出的另外一种代码转换方法,并依旧利用一组编辑操作序列来表示示例代码中的代码转换[9].与SYDIT 不同,LASE 是从多个相似修改示例中抽取代码转换.
此外,还有一些现有工作采用模板的形式来表示修改示例中的修改模式.如Andersen 等人提出的方法spdiff[8],该方法从修改示例中抽取一个单词替换补丁(term replacement patch)用于刻画示例中的代码修改方法,并将一组修改示例中最长的公共子补丁作为该组示例代码修改中的代码转换.针对LASE 在表示代码修改模式时,无法准确地识别代码语句移动等问题,Dotzler 等人提出方法ARSE.ARSE 同样是一种基于多示例的代码转换方法[10].然而,与LASE 不同,ARSE 以模板的方式来表示修改示例中的修改模式.Jiang 等人提出的方法GENPAT 是一种从单一修改示例中抽取代码转换的方法[17].在该方法中,代码转换最终以树形结构的形式加以表示.在该结构中,每一个节点的信息包括节点ID 和一组属性值.同时,GENPAT 的表示结果中还包含一组操作,其中的每一个操作为一个元组〈id,id＇〉,id 和id＇分别代表了修改前、后代码的AST 中的一个节点并存在对应关系,即节点id 发生修改后变为节点id＇.
在Rolim 等人提出的REFAZER 中,定义了一种特殊的DSL(领域特定语言)[11].其主要功能是定义对代码AST 的操作,以及对符合特定修改的AST 的条件及发生修改的位置和修改类型进行限定.因此,该代码生成任务的目标为:一段基于该DSL 的代码.该代码的输入为一段修改前的代码,输出为修改后的一段代码.
2.2 基于深度学习的方法
该类工作的主要思路是:给定待修改的代码,利用机器学习模型预测修改后的代码.Tufano 等人提出了基于翻译模型完成代码转化方法[12].具体地,给定一段待修改的代码作为模型的输入,并利用翻译模型直接预测一个token 序列,作为转换后的代码.同时,该方法也探索了翻译模型适合何种类型的代码转化场景.例如,缺陷修改、代码重构.代码作为一种高度结构化的文本,其功能和可编译性严格依赖于代码具体的token 序列和token 间的相互位置关系.然而,以预测token 序列方式进行工作的翻译模型,无法从方法层面上保证模型的输出结果是可编译的.为了克服这一问题,在Yin 等人提出的方法中,以预测指令序列的方式来生成代码,从而能够保证模型输出代码的语法正确性[15].基于此工作机制,Yin 等人提出一种基于学习的代码转换模型[13].该模型的输入,除一段待修改的代码外,同时输入一个修改示例的修改前、后的代码,即通过学习修改示例中的代码转换方式,来指导待修改的代码转换过程.
综上,Yin 等人提出的方法是目前现有工作中与本文最为相关的方法.在Yin 等人的方法中,利用了LSTM 时序模型用于处理代码的文本信息.然而,相比于自然语言,代码存在更为显著的长程依赖关系,然而有研究表明,时序模型在处理信息长程依赖时效果并不佳[14].因此,克服代码的信息长程依赖挑战,是提出本文方法的一个主要的动机.
为了保证方法生成代码的可编译性,本文借鉴了Yin 等人的工作[15],采用以预测指令序列的方式来生成代码,而非单词序列.同时,方法在代码指令集合中,增设了特殊的copy 指令,以显式地刻画代码中变量间的依赖关系.在介绍方法框架之前,本节首先详细介绍方法中基于预测指令序列的代码产生方式.
代码指令.在本文中,所谓指令,指的是形如α→β1β2…的产生式.其中,α为非终结符,βi为终结符或非终结符.在代码的抽象语法树上,每个非叶子节点均对应一条指令α→β1β2…,其中,α为该节点的语法类型,βi为其子节点的语法类型(或单词).
指令集的获取.给定一棵代码抽象语法树,假定其中某个节点v的语法类型为α,节点v共有n个子节点,且其语法类型(或单词)分别为β1,…,βn,则依据节点v,可获取指令r:α→β1…βn.按照由上到下、从左至右的顺序依次遍历抽象语法树的所有非叶子节点,即可获取相应的代码指令序列.同时,通过遍历已有数据集中代码的抽象语法树,即可获取指令集{r1,…,rN}.
在代码中,由于开发人员可以采用任何合法的变量名、字符串等,导致代码中存在比自然语言更为显著的OOV(out of vocabulary)问题.因此方法对出现在指令中的单词进行限制和预处理,从而避免所获取的指令集的规模过于庞大,不利于方法进行建模.具体地,在获取指令之前,本文统计了在给定数据集中的代码中出现的所有变量名、字符串、数字常量、字符常量及其出现的次数,只有当出现次数超过阈值的单词,才会将其保留.当代码中某个单词出现次数低于阈值时,本文方法将采用形如type_id 的形式进行替换,其中,type 表示该单词对应的类型,即变量名、字符串、数字常量或字符常量,id 为其编号.通过这样的处理,能够保证所获取的指令规模在有限的范围内.
此外,本文在指令集中额外增设了一类特殊的copy 指令.在代码中,变量声明和使用之间隐含着明确的依赖关系.本文利用增设的copy 指令,显示地标记变量声明与使用间的这种依赖关系.如在图1 中,语句“fis.close();”中的变量名fis 是由语句“FileInputStream fis=new FileInputStream(new File(dir));”声明得来.因此,方法在解析fis.close();时,采用copy 指令,以标记该变量名fis由复制之前定义的fis而得来.采用copy 指令主要有两方面的优势:一方面,显式地标记出变量间依赖关系的方式,有利于增强后续模型对变量间的依赖关系的捕获能力.另一方面,copy 指令的复制变量的范围,是代码已定义的变量名集合.因此,方法在后续的预测过程中,所面临的预测空间即为代码已定义的变量名集合.相比于整个单词空间,copy 指令缩小了在预测变量名时的预测空间,从而能够提升方法的准确率.
预测指令序列的代码产生方式.图2 展示了基于指令序列[r1,…,r7]生成代码“fis.close();”的过程.给定图2(a)的指令序列,方法首先初始一个只有根节点的抽象语法树,其类型为Statement.基于第1 条指令,即Statement→ExpressionStatement,方法为根节点插入一个类型为ExpressionStatement 的子节点.如图2(b)所示,当完成前3 条指令后,当前的抽象语法树最下层将含有2 个待扩展的节点,分别是Expression 和SimpleName.由于“.”“(”和“)”已经是终结符,因此在后续过程中,方法将不会对它们进行扩展.此时,方法将利用下一条指令r4来扩展最左边的待扩展的节点(非终结符),即左侧的Expression 节点.按照上述方式,最终将产生一棵完整的抽象语法树.按照从左至右的方式,获取所有的叶子节点内容,即为所生成的代码.
Fig.2 The rule sequences and generation of fis.close();图2 语句fis.close();对应的指令序列和生成过程
基于上述方式,本文将以预测指令序列的方式,实现代码修改的自动转换.方法的输入为x和xΔ→yΔ,其中,x为待修改的代码,xΔ→yΔ表示一个修改示例(xΔ和yΔ分别为修改前、后的代码).最终的输出为表示代码转换后的结果.在生成代码的过程中,方法将维持一棵表示中间结果的抽象语法树.通过预测下一条指令,并基于该指令对当前的抽象语法树最左边待扩展的节点进行扩展,直至生成最终的代码.本文将生成代码的概率形式化地表示为
其中,r1,…,ri为产生的指令序列.
图3 展示了本文方法ExpTrans 的整体框架.
Fig.3 The neural network of ExpTrans图3 ExpTrans 的网络结构
方法整体上遵从encoder-decoder 的架构模式,主要包含4 个模块:代码差异编码器、代码编码器、AST 编码器和解码器.这4 个子模块均采用了Transformer 的多块(block)架构[14],即每一个子模块均由多个结构相同的块组成.例如,在代码差异编码器中,每一个块均由相同的网络结构组成,包含Graph-conv 层、Self-attention 层、Char-gating 层和Rule-gating 层,并且按照前一块的输出为后一块的输入的方式进行连接.在每一个块的内部结构中,采用残差连接的方式[18],将相邻的网络层(如Graph-conv 层与Self-attention 层之间)进行连接.需要注意的是,图3 只展示了每个模块的一个块.4 个模块的主要功能如下.
代码差异编码器.方法利用该模块,对输入的修改示例xΔ→yΔ的信息进行建模.
代码编码器.方法利用该模块,对输入的待修改代码x的信息进行建模.
AST 编码器.在生成代码时,方法需要维持一棵表示中间状态的抽象语法树.方法利用该模块对该抽象语法树的信息进行建模,以期在预测代码指令时,能够提供语法树的全局信息.
解码器.在生成代码时,解码器将依据已生成的抽象语法树中待扩展的节点,预测一下指令.具体地,方法以待扩展的节点信息作为查询,输入解码器.基于输入的查询,解码器采用注意力机制来结合代码编码器、代码差异编码器和AST 编码器的建模信息.然后根据解码器的输出,方法结合softmax 和指针网络[19]以预测下一条指令.
给定待修改代码x以及修改示例xΔ→yΔ,方法的目标是实现代码转换其中,为转换后的代码.本节将介绍ExpTrans 中不同模块的具体实现.
4.1 代码差异编码器
方法利用代码差异编码器,对修改示例xΔ→yΔ的修改方式、代码结构信息进行建模.基于xΔ→yΔ,分别将修改前、后代码xΔ和yΔ表示为抽象语法树的形式.按照由上到下、从左至右的顺序,获取两棵语法树所对应的节点序列然后将两个序列合并成同一个序列并统一地记为其中,L为方法预设的最大长度,前L(ori)个节点为修改前的节点序列,随后L(mod)个节点为修改后的节点.当修改前、后的节点序列长度小于L时,方法利用特殊的占位符号〈EMPTY〉进行扩充.代码差异编码器将修改示例xΔ→yΔ建模为节点序列[v1,…,vL],代码差异编码器的输出为其中,为节点vi的表示向量,H表示空间纬度(在方法中设定为128).
4.1.1 代码差异的图表示
修改示例xΔ→yΔ,以修改前、后代码分离的形式存在,采用单独对xΔ和yΔ进行建模的方式,将损失修改前、后代码间的关联关系及结构信息.为了更加精确地表示xΔ→yΔ中所蕴含的代码修改方式,本文将xΔ→yΔ表示为一个统一的图G=〈V,E〉,其中,节点集合V包含xΔ和yΔ所对应的抽象语法树节点的集合,E为节点间的连边集合.
为了建立xΔ和yΔ节点间的连边关系,本文利用工具GumTree[20]来获取代码修改前、后节点的对应关系.GumTree 是一种基于代码抽象语法树的代码差异抽取工具.在工作时,GumTree 首先获取修改前、后的代码xΔ和yΔ所对应的抽象语法树treex和treey.然后按照自底向上的顺序,对比treex和treey节点间的类型信息和文本信息,并据此计算节点的相似度,从而获取treex和treey节点间的最佳匹配关系,并据此能够准确地推导出代码的修改过程.
在本文中,当节点vj与节点vi间存在连边,且由vj指向vi时,我们称节点vj为节点vi的父节点.进一步地,vj的父节点为vi的祖父节点.结合工具GumTree 的结果,当节点vi和vj满足下列3 种关系之一时,则建立一条由vj指向vi的连边,并将该边加入集合E中.
(1) 节点vi和vj均为treex上的节点,且vj为vi的父节点.
(2) 节点vi和vj均为treey上的节点,且vj为vi的父节点.
(3) 节点vi为treey上的节点,vj为treex上的节点,并且在GumTree 的结果中,vi和vj存在对应关系.
基于集合E,可以构造节点间的邻接矩阵M,当vj为vi的父节点时,M[i][j]=1;否则,M[i][j]=0.例如,现将代码“fis.close();”修改为“inputFile.close();”,图4 给出了采用图结构表示本处代码修改的过程和结果.如图4(a)所示,首先将修改前、后的代码表示为抽象语法树的形式(这里,省略了‘.’‘(’等符号以方便展示).基于获取的抽象语法树,利用GumTree 来获取修改前、后代码抽象语法树节点间的对应关系.在图4(a)中,节点ni与in＇表示两个节点存在对应关系.最终,该处代码修改的图结构被表示为图4(b)所示的邻接矩阵.
Fig.4 The illustration of construction of code change adjacent matrix图4 代码差异邻接矩阵建立过程示意图
4.1.2 编码信息的抽取
在计算Y(diff)之前,方法首先获取每个节点不同方面的初始信息.
节点的单词信息.在代码的抽象语法树中,每个非叶子节点均有相应的语法类型,每个叶子节点则对应代码中的一个单词.基于图G的节点序列V,可以得到单词序列[w1,…,wL].当vi为非叶子节点时,wi为节点对应的语法类型;当vi为叶子节点时,wi为节点对应的单词.通过embedding 方式,为每个单词wi初始一个表示向量节点序列[v1,…,vL]对应的单词信息为
节点单词字符信息.有些语义相似的单词存在相同的字符序列.例如,同一词根派生的不同类型的单词.而上述将单词作为整体进行信息编码的方式,将丢弃单词的字符信息.为了在节点表示向量中引入单词的字符信息,本文借鉴了Sun 等人对单词的字符信息进行编码的方法[16].具体地,基于获取的单词序列,将每个单词wi切分为字符序列[ci,1,…,ci,L′],其中,L′为模型预设的单词最大长度.类似地,利用embedding 方式为每个字符ci,j初始一个表示向量并利用全连接层,按照公式(2)的方式,计算单词wi的字符表示向量
节点指令信息.在抽象语法树中,每个非叶子节点vi均对应一条指令其中,α(i)为节点vi对应的语法类型,所有β(i)均为节点vi的子节点的语法类型或单词.采用类似公式(2)的方式,方法为每条指令ri:计算表示向量此外,叶子节点所对应的指令,统一采用特殊指令〈EMPTY_RULE〉进行替代.据此,节点序列[v1,…,vL]对应的节点指令信息为
位置信息.在Transformer 的架构中,方法将时序数据(例如代码的节点序列的表示向量)打包成一个向量矩阵,以使得模型能够并行训练.但这样的处理方式会丢失数据的位置(时序)信息.因此,需要额外添加数据的位置信息.在本文中,采用Dehghani 的工作做法[21],利用下列公式人为地构造每个节点的位置信息:
4.1.3 代码差异编码器的网络结构
Graph-conv 层.在将xΔ→yΔ表示为节点序列后,模型将无法捕获节点间的结构信息.因此本文方法利用一层图卷积层来实现在每个节点的表示向量中引入代码的结构信息.
基于构造的图G=〈V,E〉和邻接矩阵M,假定当前节点的表示向量矩阵F=[f1;…;fL],方法将按照公式(5)计算每个节点的父节点的表示向量:
在卷积时,方法预设了卷积窗口K,并按照如下方式进行卷积:
其中,W(conv)为卷积参数,f为Rule 激活函数.
该层的输入为节点的表示向量和节点的位置信息之和,即I=[xb,1+pb,1;…;xb,L+pb,L],该层的输出为
其中,当b=1 时(即为第1 个块),xb,i表示对应节点的单词信息(即);而对于其他块,xb,i则为前一块的输出.
Self-attention 层.该层采用了Transformer 中的self-attention 注意力机制[14],以捕获代码间的长程依赖关系.
在Transformer 中,注意力机制被表述为将查询Q、键值对K和V映射到输出的过程,其中,Q、K和V均为向量矩阵.输出为对V中分量加权求和的结果.而V中每个value 相应的权重将依据Q与相应的关键字K的匹配程度给出,其加权求和的结果为
其中,dk为缩放因子.同时,Transformer 采用multi-head attention 机制,使得模型能够从不同的表示空间的角度来注意到不同位置的信息,即:
特别地,当Q、K和V相同时,即形如Multihead(Q,Q,Q)的形式,则被称为self-attention.该层实现了selfattention 注意力机制,该层的输出为
Char-gating 层.在该层之前,节点序列被表示为向量矩阵Y(self),为了在节点vi的表示向量中引入字符信息方法在该层中采用门机制,使得节点的表示向量矩阵更新为Y(self)和Y(char)的加权和.
门(gating)机制的目的在于对不同表示空间的表示结果进行综合,形成最终的表示向量.给定表示向量f1和f2,门机制的目标是将f1和f2进行加权求和,获取综合f1和f2后的表示向量f(gate).其中,f1和f2的权重按照下列公式进行计算:
为了保证Y(self)依旧为加权后的结果的信息主体,方法首先基于Y(self)通过线性变换的方式获取控制向量C(self).然后按照下列公式来计算Y(self)和Y(char)的加权结果作为该层的输出:
Rule-gating 层.类似地,该层同样采用门机制,使得在节点的表示向量中融合指令字符信息Y(rule),该层的输出为
其中,C(char)为通过Y(char-gate)线性变换得来的控制向量.
最终,代码差异编码器的输出为Y(diff).
4.2 代码编码器
代码编码器的作用是为了实现对待修改代码x的信息建模.如图3 所示,代码编码器和差异编码器的网络结构是一致的,只是在获取该层的输入方式上有所不同.
给定待修改代码x,通过将其解析为抽象语法树treex,并按照由上到下、从左至右的方式,获取节点序列V(x)=基于treex,构造图G(x)=〈V,E〉,其中,V=V(x),E为treex中节点的连边集合.此外,方法同样为G(x)构造其节点间的邻接矩阵M(x).
代码编码器采用与代码差异编码器中相同的数据预处理方式来获取节点序列V(x)对应的单词信息、节点单词字符信息、节点指令信息和位置信息.然后,信息依次经过Graph-conv 层、Self-attention 层、Char-gating层和Rule-gating 层,并记代码编码器的最终输出为Y(x).
4.3 AST编码器
本文方法在产生代码的过程中,需要维持一个由已产生指令序列生成的抽象语法树.方法以当前抽象语法树的最左非叶子节点(待扩展节点)为查询,预测下一条指令,并利用预测的指令对该节点进行扩充.因此,需要对产生代码过程中的抽象语法树的信息进行编码,以在预测下一条指令时,能够为模型提供抽象语法树的全局视图.在AST 编码器中,方法利用已产生的指令序列[r1,…,rp]来表示已产生的抽象语法树.AST 编码器的目标则是:将指令序列最终表示为其中,为指令ri的表示向量,P为方法预设的最大指令序列长度.
4.3.1 编码信息的提取
指令的初始向量.利用embedding 方式,为每条指令r初始一条表示向量因此给定指令序列[r1,…,rR],通过查表的方式,获取指令序列的初始表示向量矩阵
指令的符号信息.在形如α→β1β2…的指令表示形式中,符号α和βi对于表达指令的语义信息十分重要.例如,当待扩展的节点的类型为Statement 时,则下一条预测的指令的非终结符α必须同样为Statement,以保证代码的合法性.然而,上述将指令作为整体进行编码的方式,将忽略指令涉及的符号信息.为了在指令的表示向量中引入指令符号序列的信息,本文采用了Sun 的工作方式[16].具体地,给定指令ri:α→β1β2…,α及所有的βj均为标准单词集中的一个单词.通过查表的方式,可以获取每个单词对应的表示向量α(w)或类似公式(2),利用全连接层,以α(w)和所有作为输入,并将输出记为最后,再次利用全连接层实现如下的编码方式:
其中,W(rule)为网络参数.指令序列[r1,...,rp]对应的符号信息为
位置信息.本文方法同样利用公式(3)和公式(4)来计算指令序列的位置信息其中,为第b个块中的第i条指令的位置信息.
4.3.2 AST 编码器的网络结构
Self-attention 层.方法利用一层Self-attention 层来捕获指令间的依赖关系.该层结构和代码差异编码器中的Self-attention 层的结构是一致的.该层输入为指令表示向量与位置信息之和,即该层的输出为
当b=1 时(即为第1 块),rb,i表示指令ri的初始向量(即);而在其他块中,rb,i为前一块的输出.
Rule-gating 层.如上文所述,指令的符号信息对于表示指令的语义十分重要,因此,本文方法同样利用门机制来实现对指令符号信息的获取.与之前的gating 层相似,首先基于R(self)获取控制变量矩阵C(r-self),然后按照下列公式进行计算:
Code-attention 层.代码转换需要依据待修改代码x进行转换,因此在后续的代码指令预测过程中,模型需要获取待修改代码的信息.本文方法利用该层来实现在指令序列的编码结果中,引入待修改代码x的信息(Y(x)).该层的输出为
Diff-attention 层.针对代码x进行修改时,所修改的方式依赖于给定修改示例xΔ→yΔ.因此,在后续的代码指令预测过程中,模型需要修改示例的差异信息.本文方法利用该层来实现在指令序列的编码结果中,引入xΔ→yΔ的信息(Y(diff)).该层的输出为
Graph-conv 层.由已生成的代码指令可以构造出局部的抽象语法树,而预测的指令均会对应特定的节点,因此,指令(节点)间存在有意义的结构关系.然而,以指令序列的形式表示已生成的抽象语法树,将会遗失指令间的结构信息.因此,本文方法采用一层图卷积层,利用代码的抽象语法树的结构信息来增强指令的编码信息.
依据指令对应节点的邻接关系,可以获得一个指令间的邻接矩阵Mp*p.当M[i][j]=1 时,表示指令rj(对应的节点)为指令ri(对应的节点)的父节点.基于此,该层的输出为
最终AST 编码器的输出为R(ast).
4.4 解码器
解码器以当前待扩展的非叶子节点为输入,即Q(d)=[q1;…;qR],其中,qi为每个待扩展节点的表示向量.由于解码器仍然遵循多块的设计,因此在第1 块中,qi为节点对应的语法类型或单词信息;而在其他块中,qi则为上一个块的输出.解码器的目标是生成查询矩阵其中,为第i个节点相应的查询向量,方法将依据预测第i条指令.解码器首先利用Self-attention 层来获取待扩展节点间的依赖关系.然后,数据流将依次经过AST-attention 层、Code-attention 层和Diff-attention 层,分别用于获取抽象语法树、待修改代码和修改示例的信息.具体地:
Self-attention 层.在上述查询矩阵中,每个查询分量qi均代表抽象语法树中的一个待扩展的节点的信息.在代码的抽象语法树中,不同节点彼此间存在不同程度的依赖关系,因此,我们利用一层Self-attention 层来捕获查询间(即节点间)的依赖关系,该层的输出为
Ast-attention 层.本文方法利用该层实现利用已产生的抽象语法树的信息(即Y(ast))增强查询信息.在该层中,Q=D(self),K=Y(ast),V=Y(ast),输出为
Code-attention 层.本文方法利用该层实现待修改代码x的信息(即Y(x))增强查询信息.在该层中,Q=D(ast),K=Y(x),V=Y(xt).输出为
Diff-attention 层.本文方法利用该层实现利用修改示例xΔ→yΔ的信息(即Y(diff))增强查询信息.在该层中,Q=D(x),K=Y(diff),V=Y(diff),输出为
最终,解码器的输出为D(query).
4.5 指令预测
在预测下一条指令时,模型的预测范围将来自于两种类型的指令.首先,在我们处理数据时,获取了标准数据指令集R={r1,r2,…,rN},该指令集能够满足正常的代码生成需要.然而,在代码中变量名定义和使用存在依赖关系.为了捕获这种依赖关系,方法增设了指令copy(n),表示复制已产生指令中第n条指令中的变量名.在预测第i条指令时,除了计算指令rj的概率p(rj)以外,方法还将依据指针网络计算p(copy(t))的概率.因此,最终的第i条指令预测结果需要从指令rj和copy(t)中进行选择.本文将采用下列公式所示的门机制来对两种类型的指令进行筛选:
其中,g表示当前预测指令属于R的概率,亦即指令为copy 的概率为1-g.最终预测的指令为op=argmaxopp(op).
其中,本文将按照公式(27),计算下一条指令为rj的概率p(rj):
在预测第i条指令时,copy 指令所复制的变量名来自于前i-1 条指令中声明的变量,因此,本文方法将按照下列公式来计算p(copy(t)):
其中,1≤t≤i–1,为已产生的第t条指令的表示向量,W(query)和W(rule)为网络参数.
本文开展了两个实验,分别将本文方法与现有的基于深度学习的方法以及基于人工规则的方法进行对比,以验证方法的有效性.
5.1 实验1
该实验通过与现有的基于深度学习的方法进行对比,以验证本文方法的有效性.
(1) 数据集.该实验在Yin 等人的数据集[13]上来验证本文方法的有效性.在Yin 等人的工作中,他们从Github上收集了54 个C#开源项目,然后从这些软件项目的提交历史中抽取并筛选出111 724 处C#代码修改,其中,91372/10176/10176 条数据分别用于训练/验证/测试.在该数据集中,数据示例均可表示为〈xi,yi〉的形式,其中,xi为修改前的代码,yi为修改后的代码.依据实例〈xi,yi〉,将其转换为数据〈xi,xi→yi,yi〉的形式,并按照模型输入要求进行预处理.具体地,首先将xi和yi解析为抽象语法树的形式,并按照由上至下、从左到右的顺序,获取节点序列此外,依据yi对应的抽象语法树,获取指令序列[r1,…,rR].其中,修改前的代码节点序列作为代码编码器的输入,长度为L(ori);将修改前、后代码的节点序列进行拼接,作为代码差异编码器的输入,长度为L(ori)+L(mod);指令序列作为模型预测目标,长度为P.表1 列出了该数据集中数据的4 种长度的分布情况.如表中第2 行所示,92.2%的实例的长度L(ori)小于100,7.7%的实例的长度L(ori)处于101～200 之间,0.1%的实例的长度L(ori)处于201～300 之间,最大长度为239.此外,本文对预处理后的数据中所包含的单词进行统计,共发现2 931 个独有单词,其中最大字符长度为70,且80.3%的单词的字符长度少于20 个.
(2) 对比方法.Yin 等人的工作是目前与本文工作最为相关的最新工作[13].在该工作中,作者通过表示示例代码中的修改方式,并用于指导代码转换.在该工作中,作者还尝试利用不同的方式来表示代码和修改示例,并验证不同模型的组合的方法效果.
(3) 参数设置.为了获取较优的Transformer 架构的块数设置,方法分别将块数设为4、6 和8,且实验结果表明,当块数为6 时,模型效果最佳(具体结果见表3).因此,方法最终将代码差异编码器、代码编码器、AST 编码器和解码器的块数(即N1/N2/N3/N4)设为6.此外,如表1 所示,由于所有的代码长度都小于300,且超过98%的代码差异长度小于300,因此代码差异编码器和代码编码器的最大输入长度L被设定为300.同时,所有数据实例的指令长度均小于200,且最大长度为185,因此,模型允许最大的指令长度P被设定为200.此外,还有超过80%的单词的字符≤20,且最大长度为70,因此,方法将模型允许单词的最大长度L＇设定为20,意在保证该值能够覆盖到大多数单词的同时,避免引入过多的占位符而影响模型效果.
(4) 实验过程.在与Yin 等人的方法进行对比时,本文沿用了他们的实验设置,并利用其数据集的训练集和验证集来训练本文方法.然后,利用测试集来测试本文方法,即方法是否能够将修改前的代码xi正确地转换为yi.
(5) 评估标准.本文主要采用准确率来量化方法的效果.给定一条数据〈x,xΔ→yΔ,y〉,其中,x为修改前的代码,xΔ→yΔ为修改示例,y为修改后的代码.若方法的预测结果与y完全相同,则称x被正确地修改.本文将方法的准确率定义为
(6) 实验结果.表2 展示了与Yin 等人方法对比后的实验结果.从实验结果来看,较之Yin 等人提出的不同的模型,本文方法在准确率上提升了11.8%～30.8%.在Yin 等人的工作方法中,他们采用了两个不同的子模块分别用于编码待修改代码的信息和修改示例的信息.同时,他们还尝试了两种不同思路以对信息进行建模,即基于单词序列的方式和基于图结构的方式,并探索了信息建模方式的不同组合的实际效果.仅从Yin 等人的工作结果来看,基于单词序列模型(如Seq2Seq-Seq)的结果要比基于图结构模型(如Graph2Tree-Graph)的结果更优.导致这种结果的原因在于实验数据的特殊性.由于模型输入的修改示例包含了待修改代码的修改结果信息,反而更有利于基于单词序列的模型预测修改结果.
反观本文方法ExpTrans 的结果,若单独与Yin 工作中的基于图结构的模型进行对比,ExpTrans 在准确率上提升了23.4%,这表明,ExpTrans 采用图的形式来表示修改示例,并结合卷积神经网络的方式,能够有效增强模型对代码的结构信息的捕获能力,从而使得方法的准确率有了大幅度的提升.与Yin 等人基于单词序列的方法进行对比,ExpTrans 同样具有至少11.8%的提升.这些实验结果表明,本文方法是有效的.
此外,在模型ExpTrans 中,Transformer 架构的块数、copy 指令和模型的不同模块对代码转换效果均有一定程度的影响.因此,基于ExpTrans,本文通过修改模型的架构或参数设置,产生了不同的变体,以此探究上述因素在ExpTrans 转换代码过程中的有效性.表3 列出这些变体的具体设置及实验结果.
首先,为了寻求模型中Transformer 架构层数较优的设置,本文借鉴了Vaswani 等人的工作[14],先后将模型的层数设置为4、6 和8,具体的实验结果如表3 中(A)行所示.从结果可以看出,当层数设置为4 时,方法的准确率为67.37%,较之层数为6 时,下降4.08%.当层数设置为8 时,准确率为64.37%.鉴于上述结果,最终将ExpTrans中Transformer 的层数设置为6 层.
同时,为了验证copy 指令的有效性,本文再次将ExpTrans 应用于Yin 等人提供的数据集上.所不同的是,在处理该数据集时,取消了copy 指令.具体的实验结果如表3 中(B)行所示.如结果显示,当指令集中不含copy 指令时,模型的准确下降为60.12%,该结果表明,增设的copy 指令能够有效地提升模型对代码间长程依赖的捕获能力,并提升方法的准确性.
最后,本文通过分别删除模型中的代码差异编码器以及代码差异编码器和代码编码器中的图卷积层,来验证它们的必要性.具体结果如表3 中(C)行所示.当删除代码差异编码器时,方法的准确率骤降为6.36%.该实验结果充分说明,在代码自动转换时,给定一个或一组实例修改的必要性,同时也说明了ExpTrans 中的代码差异编码器的有效性.另外,当分别删除代码差异编码器和代码编码器中图卷积层后,模型的准确率分别下降为68.01%和65.69%.在取消图卷积层的情况下,模型实际处理输入数据的效果等同于处理线性的单词序列,失去了代码自身的结构信息.这些结果表明,本文方法采用图卷积的方式能够有效地捕获代码的结构信息,并增强模型的转换能力,提升模型效果.
Table 1 Data length distribution in the first experiment表1 实验1 中数据长度分布
Table 2 The comprative results with the work of Yin,et al表2 与Yin 等人方法的对比实验结果
Table 3 Performances of different variations on ExpTrans表3 ExpTrans 的不同变体及实验结果
5.2 实验2
该实验通过与现有的基于人工规则的方法进行对比,来验证本文方法的有效性.
1) 数据集.由于所对比的基于人工规则的方法是针对Java 语言的,因此我们又收集了Java 语言的代码修改数据集.在收集该数据之前,我们查阅了Java 语言在不同版本上新增的功能,选出其中5 种并总结了可能导致的修改模式.表4 列出了所选出的Java 功能和相应的修改模式.基于每种功能,构造相应的查询语句,并在Github上搜索相关的commit.依据搜索结果,人工地为每个查询筛选出10 个具有相应修改模式的代码修改,即为相似代码修改.
2) 对比方法.在本实验中,对比了两种基于人工特征的代码转换方法GenPat 和ARES.
(1) GenPat[17].该方法是一种基于单示例的代码转换方法,其通过将给定的单个修改示例解析为抽象语法树,对抽象语法树上的特定节点的属性进行了泛化或限制,并标注抽象语法树的节点的变化过程.在代码转换时,GenPat 将根据抽取的抽象语法树进行代码匹配,并利用标注的节点的变化过程对代码进行转换.
(2) ARES[10].该方法是一种基于多示例的代码转换方法,其利用模板来表示修改示例中的修改模式.在模板中保留了修改示例中的共有部分,而采用通配符的形式对不同的部分进行泛化.在代码转换时,ARES 将依据抽取的模版对代码进行匹配,并利用模版所刻画的修改结果模式,对匹配成功的代码进行修改.
Table 4 The corresponding query sentences and change patterns of different Java features表4 不同Java 功能对应的查询语句和修改模式
3) 实验过程.在该实验中,本文按照搜集的6 组相似代码修改分别进行实验.具体地,给定一组相似修改集合P={p1,…,p10},其中,代码修改pi=〈xi,yi〉,xi为修改前的代码,yi为修改后的代码.为了训练本文方法,我们基于集合P,进行了如下方式的构造:
其中,1≤i,j≤10,pi,j所代表的含义是利用pj的修改模式对代码xi进行修改,并且按照如下方式将P＇分为:
训练集:{pi,j},1≤i≤10,1≤j≤8;
验证集:{pi,j},1≤i≤10,j=9;
测试集:{pi,j},1≤i≤10,j=10.
在实验时,分别利用3 种方法对测试集中的实例进行修改.由于ARES 是一种基于多示例的代码转换方法,因此,我们将P作为一组相似代码变更提供给ARES,以供ARES 抽取所需的代码修改模式.
参数设置.在该实验中,本文方法中的模型参数沿用了实验1 中的参数设置.
实验结果.我们将方法的输出结果分为4 种.
○ 表示方法无法从给定的修改示例中抽取出统一的修改模式,导致方法无输出.
表5 中展示了方法在6 组数据上的对比实验结果.结果表明,ExpTrans 要明显优于其他两种对比方法.ExpTrans 在所有组别上,均有正确的修改示例,尤其是在第2 组数据上,ExpTrans 能够将全部的代码实例修改成功.我们人工检查了ExpTrans 修改错误的实例,发现这些错误实例主要发生在预测同一个函数的多个参数时.其可能的原因是,ExpTrans 在预测函数的参数时,缺乏参数的序列位置信息,从而导致错误的预测结果.例如,一个预期结果为byteBufferReadCheck(in,buf,11);,而ExpTrans 的预测结果为byteBufferReadCheck(in,11,11);,其中,11为错误预测的参数.
进一步地,我们检查了GenPat 和ARES 的输出结果,以探究导致两种方法结果不理想的原因.
方法GenPat 失效的原因在于:(1) 方法依赖于待修改的代码与修改示例代码的结构和语法类型的相似性.例如,“return new Double(0.0);”→“return new Double.valueOf(0.0);”中的修改方式,由于语法类型不同,导致无法用于修改代码“val=new Double(0.0);”.而在本实验所获取的数据中,无法保证相似的代码修改具有相似的结构和语法特征.因此,导致GenPat 从示例中抽取的修改模式无法适配于待修改的代码(类型).(2) GenPat 需要利用代码中变量的定义信息.然而,由于获取代码修改时,只抽取了发生修改的代码片段,因而无法保证抽取的代码修改中同时包含所有涉及的变量的定义.由于GenPat 无法获取足够的信息,因此在将抽取的模式匹配待修改的代码时,产生错误匹配,从而导致错误修改(类型☒).
Table 5 The comprative results with GenPat and ARES表5 ExpTrans 方法与GenPat 和ARES 方法的对比实验结果
由于ARES 方法是一种基于多示例的代码转换方法,因此,当给定一组相似代码修改示例时,ARES 需要对修改示例中的不同部分进行泛化,以使其表示的修改模式能够拟合给定的修改示例.然而,当给定的修改示例的修改语义相似但结构不同时,容易导致方法无法抽取出统一的修改模式.例如,在实验中我们发现,ARES 无法从组别2、4、6 的数据中抽取统一的修改模式,因此也无法完成对相应代码的修改(类型○).此外,还有一些错误实例是因为ARES 在抽取的模式中,保留了修改示例所特有的变量名.因此,在将抽取的模式适配到待修改的代码时,所修改的结果中引入了这些变量名,导致修改失败(类型☒).
5.3 讨 论
方法适用范围.在本文方法中,我们针对输入的待修改代码x和修改示例xΔ→yΔ,预设了最大长度.当代码长度超过预设长度时,超过预设长度的代码内容将被截取.这在一定程度上影响了方法能够使用的代码修改场景.但在一些频繁发生的相似修改任务中,例如API 版本迁移,所修改的代码往往是局部的、简短的,因此,方法预设最大的长度并不会严重制约本文方法的实用性.尽管如此,在未来的工作中,我们仍需尝试提出不同的网络模型以降低修改代码长度对方法的影响.
数据规模.在收集Java 数据时,依赖于人工对搜索结果的筛选,这限制了本文收集数据的规模和效率,也一定程度地制约了挖掘方法更大的潜力.在未来的工作中,我们将尝试利用自动化的方式来大规模地收集数据,尽量在降低人力代价的情况下,提升方法的效果.
在本文中,我们提出了一种基于深度学习的代码转换方法.通过采用图形式来表示修改示例,并结合卷积网络和Transformer架构,增加了方法捕获代码结构信息的能力.实验结果表明,我们的方法比现有的基于深度学习和基于人工规则的方法,其效果有着较为明显的提升.针对可能影响方法有效性的因素,我们将在未来的工作中,通过提出优化模型和自动化的数据收集方法,来降低这些因素对方法的影响.
猜你喜欢 编码器代码指令 WV3650M/WH3650M 绝对值旋转编码器传感器世界(2022年4期)2022-08-05设定多圈绝对值编码器当前圈数的方法锻压装备与制造技术(2021年5期)2021-11-13转炉系统常用编码器选型及调试科学技术创新(2021年5期)2021-03-17——编码器">舞台机械技术与设备系列谈（二）——编码器演艺科技(2020年7期)2020-08-13《单一形状固定循环指令G90车外圆仿真》教案设计学校教育研究(2020年11期)2020-06-08新机研制中总装装配指令策划研究航空科学技术(2019年2期)2019-09-10关于ARM+FPGA组建PLC高速指令控制器的研究科技与创新(2019年2期)2019-02-14神秘的代码新高考·高二数学(2016年7期)2017-01-23一周机构净增（减）仓股前20名股市动态分析(2016年17期)2016-10-20一行代码玩完19亿元卫星太空探索(2016年6期)2016-07-10