【论文笔记】Summarizing source code with Heterogeneous Syntax Graph and dual position

Abstract

在本文中，我们提出了一个名为 HetSum 的新颖框架。具体来说，首先通过在 AST 中设计六种类型的增强边来构建异构语法图（HSG），这表明了源代码的异构结构。同时，考虑布局信息，为源代码中的每个标记设计了双重位置。此外，我们在 HetSum 中开发了异构图神经网络来对 HSG 进行编码，同时使用 Transformer 编码器提取代码布局特征。通过将学习到的代码标记向量同化到 HSG 编码器中，HetSum 可以捕获两个编码器之间的关系，以改进代码表示。为了便于生成高质量的摘要，我们在扩展 Transformer 解码子层的同时将复制机制集成到解码过程中。

1. Introduction

在生成高质量的代码摘要方法终仍存在一些局限性：

• AST 的异构性总是被忽略。在学习源代码的语法结构时，大多数基于 GNN 的模型仅将 AST 视为用于编码的同构图。我们认为 AST 的异构性对于保持 AST 的结构独特性至关重要，如图 下图所示，代码片段 A 和 B 通过在 AST 上添加数据流边和兄弟边而具有相同的同构语法图，因为节点 ‘’=‘’ 无法通过同构边区分其右兄弟节点’‘identifier’’ 和左兄弟节点 ‘‘identifier’’ 。事实上，节点 ‘’=‘’ 也无法区分其父节点 ‘‘assignment’’ 和兄弟节点 ‘‘identifier’’ 。因此，边的同构性削弱了 GNN 识别节点之间不同关系的学习能力。
• 源代码标记的位置信息尚未得到很好的研究。迄今为止，那些将源代码编码为纯文本的方法忽略了代码的布局信息，该信息记录了代码标记的精确位置。例如，下图中的代码片段A和C被处理成具有相同顺序位置的相同标记序列，导致它们无法被类似Transformer的模型区分。

解决方法：

• 鉴于上述限制，本文首先将基于 AST 的同构图扩展为具有六种有向边的异构语法图（HSG）。具体地，来自HSG中的节点的边可以到达其子节点、父节点、右兄弟节点、左兄弟节点、下一个DFG节点或前一个DFG节点，这可以很好地保留HSG的结构唯一性。例如，由于节点 ‘’=‘’ 和它的两个兄弟节点（‘‘identifier’’）之间的有向边，上图 中代码片段 A 和 B 的 HSG 是不同的。此外，不同的边类型使得节点 ‘’=‘’ 区分其父节点 ‘‘assignment’’ 和兄弟节点。
• 为了保留源代码的布局信息，我们为原始源代码中的每个代码标记设计了双重位置。通过双重位置，代码令牌可以通过行号和该行中的顺序位置精确定位。例如，上图中的双重位置突出显示了代码片段 A 和 C 之间的布局差异。

2. HSG and dual position

2.1 HSG construction

为了获取给定代码片段的 HSG，我们首先将其解析为 AST。作为源代码的基本层次语法结构，AST仅表示其节点之间的父子关系。因此，为了进一步丰富 AST 节点之间的关系，我们将 AST 增强为同构语法图。在这个阶段，我们在所有兄弟节点之间引入边来表示兄弟关系。此外，我们引入额外的边来构造数据流图（DFG），用来表示数据流。 DFG 指示每个变量来自或去往何处，可以进一步捕获数据依赖性以实现更好的代码表示。例如，在图 1 中的同构语法图中，节点 “=” 通过三个边连接到其两个兄弟节点 ‘‘identifier’’ 和父节点’‘assignment’’ 。此外，两个 ‘‘identifier’’ 节点之间存在数据依赖性。应该注意的是，所有节点实际上都无法通过这些同构边区分其父节点、子节点、兄弟节点和 DFG 邻居节点。

第二步，我们从同构语法图构建 HSG。我们将同构语法图中的边改进为具有方向的异构边。如图 1 中的 HSG 所示，节点的边可能通向其子节点、父节点、右兄弟节点、左兄弟节点、下一个 DFG 节点或前一个 DFG 节点。在本文中，我们定义从当前节点到其下一个DFG节点的边意味着当前节点的数据流向其下一个DFG节点。相反，从当前节点到其前一个DFG节点的边表示当前节点的数据来自其前一个DFG节点。通过明确指定六种类型的边，精确识别节点之间的对应关系，从而很好地保持了HSG的结构唯一性。例如，在代码片段 A 的 HSG 中，左侧 ‘‘identifier’’ 可以准确识别其子节点 “b”、父节点’‘assignment’'、右侧兄弟节点 “=” 以及前一个 DFG 节点 ‘‘identifier’’。

2.2 Code tokens with dual positions

由于自动代码摘要生成严重依赖于源代码标记，因此我们将原始源代码及其 HSG 结合起来，生成具有双重特征的代码标记。增强代码标记表示的位置。为此，首先遍历 HSG 以获取与标记化源代码相关的所有叶节点。与早期将源代码视为自然语言中的纯文本的方法不同，我们考虑了通过为每个代码标记呈现双重位置来显示代码布局信息。双重位置是由两个值组成的元组。第一个值记录行号，第二个值指示当前行中的顺序位置。两个值都从 1 开始。特别是，源代码中的缩进被认为具有连续位置，尽管它不被视为代码标记。例如，在图 1 中，令牌 “c” 的双重位置 {3, 4} 表示考虑到行开头的缩进，该令牌位于第三行的第四个位置。通过指定这样的双重位置，所有代码标记都具有与源代码对应的精确位置信息，这可以保持源代码的布局唯一性，以实现更好的代码表示。

3. HetSum model

3.1 Overview

假设将源代码片段表示成一个 HSG，这个 HSG 具有 $l_n$ 个节点表示为 $T_n=(n_1,n_2,...,n_{l_n})$，还有 $l_c$ 个代码 token 表示为 $T_c=(c_1,c_2,...,c_{l_c})$ 以及具有双重位置表示为 P c = ( { x 1 , y 1 } , { x 2 , y 2 } , . . . , { x l c , y l c } ) P_c = ( \{x_1, y_1\}, \{x_2, y_2\}, ... , \{x_{l_c} , y_{l_c} \}) Pc?=({x1?,y1?},{x2?,y2?},...,{xlc??,ylc??})。基于当前代码摘要的标记表示为 $T_s=(?∕start?,s_1,s_2,...,s_{m?1},?∕pad?,?∕pad?,...)$ ，其具有连续位置 $P_s=(1,2,...,l_s)$，HetSum 尝试通过融合从 HSG 和代码标记中提取的特征来生成下一个摘要标记 $s_m$。请注意，$?∕start?$ 是初始化 $T_s$ 的特殊标签，$?∕pad?$ 用于将 $T_s$ 填充到 HetSum 输入的长度 $l_s$。

图 2 说明了所提出的 HetSum 的框架。它主要由三个组件组成：Code Token Encoder、HSG Encoder 和具有复制机制的 Summary Decoder。在编码过程中，双位置代码标记和 HSG 分别地流入Transformer编码器和 HSGNN 层，用于获取代码标记表示 $E_c^{\prime }\in R^{l_c\times d}$ 和语法图表示 $E_n^{\prime }\in R^{l_n\times d}$ ，其中 $d$ 是嵌入大小。随后，HetSum 执行具有复制机制的基于 Transformer 的解码器，将现有摘要标记作为输入，并融合提取的代码标记和 HSG 特征（即 $E_c^{\prime }$ 和 $E_n^{\prime }$），以预测生成摘要的下一个标记 $s_m$ 。

3.2 Embeddings

在对代码标记、HSG 和摘要文本进行编码之前，需要将它们转换为数值向量。在本研究中，HSG 节点 $T_n$ 直接映射到嵌入向量 $E_n^0\in R^{l_c\times d}$ 中。通过利用可学习的位置嵌入，代码标记 $T_c$ 和摘要标记 $T_s$ 被转换为向量 $E_c^0\in R^{l_c\times d}$ 和 $E_s^0\in R^{l_c\times d}$，分别包含他们的双重位置 $P_c$ 和顺序位置 $P_s$。三个嵌入过程的公式如下：

其中 $Emb$ 表示 $T_n、T_c$ 和 $T_s$ 的共享嵌入操作； $P_{c,x}=(x_1,x_2,...,x_{l_c})$ 和 $P_{c,y}=(y_1,y_2,...,y_{l_c})$ 是双重位置 $P_c$ 的分量。 $XEmb$、$YEmb$ 和 $SEmb$ 对应于位置嵌入操作。

3.3. Code token encoder

图2描绘了Code token 编码器包括两个相同的Transformer层。每层都由多头注意力机制以及全连接的位置前馈网络组成，两者都遵循残差连接和层归一化。残差链接用来缓解多层计算中的梯度消失问题。层归一化可以减轻残差连接期间过多的矢量偏移。第k个Code token编码层的整个流程表述如下：

其中 $E_c^{k?1}\in R^{l_c\times d}$ 表示上一层输出的向量； $FFN$ 表示前馈网络； $LayerNorm$ 表示层归一化； $Att$ 表示多头注意力。前馈网络包含两个由非线性变换的 ReLU 激活分隔的线性变换，其公式如下：

3.4 HSG encoder

鉴于 GraphSAGE 在处理图时的高效率和性能，我们通过改进 GraphSAGE 用于 HSG 表示学习的思想来开发 HSGNN。如图2所示，HSG编码器包括六个相同的HSGNN层。需要强调的是，学习到的代码标记表示被设计为在将 HSG embeddings 放入第一个 HSGNN 层之前集成到 HSG embeddings 中，以对代码标记编码器和 HSG 编码器之间的关系进行建模。为此，对于源代码中的每个 HSG 叶节点及其对应的标记，学习到的代码标记向量将被添加到 HSG 叶嵌入向量中。

在第 k 个 HSGNN 层中，HSG 首先由异构 GraphSAGE 处理。具体来说，对于 HSG 节点 $i$，它的状态通过指向该节点的邻居节点的两个阶段聚合来更新，如图 3 所示。在第一阶段，具有不同边类型的邻居分别被聚合为不同的邻居组。对于边类型 g，聚合公式为：

其中 $N_g(i)$ 表示边类型为 $g$ 的节点 $i$ 的邻居； $e_{g,j}^{k?1}\in R^d$ 表示第 $(k?1)$ 层、边类型为 $g$ 的第 $j$ 个邻居的向量； $Agg{r}_1$ 表示聚合函数。在第二阶段，转换和聚合邻居组以更新节点的状态，其公式如下：

其中 $e_i^{k?1}\in R^d$ 表示上一个 HSGNN 层输出的节点 $i$ 的向量； $g(i)$表示通向节点 $i$ 的边的类型； $Agg{r}_2$ 表示聚合函数； $W_0,W_g\in R^{d\times d}$ 是可学习的权重矩阵。

一旦节点状态全部更新，状态向量就会被连接起来并输入到 $ReLU$ 激活函数中进行非线性变换，其公式如下：

通过更多堆叠的 HSGNN 层，节点可以从更远的距离收集其相邻数据，从而捕获更多异构结构特征。为了减轻多层计算导致的梯度消失和过多的向量偏移，我们在每一层中采用残差连接以及层归一化，其公式为以下：

其中方程中的 $E^{k?1}\in R^{l_n\times d}$ 表示第 $(k?1)$ 个 HSGNN 层输出的 HSG 节点向量。

3.5 Summary decoder

为了利用学习到的代码标记和 HSG 表示来生成摘要，我们通过实现六层扩展 Transformer 解码模块来设计 HetSum 的解码器。每个模块包含四个子层：一个用于自注意力编码的屏蔽多头注意力子层，两个用于两阶段解码的多头注意力子层，以及一个用于非线性变换的 $FFN$ 子层。每个子层后面都是带有层归一化的残差连接。

给定现有的摘要标记，解码器首先基于屏蔽多头注意力对其进行解码。

之后，通过与两个编码器交互，堆叠两个多头注意力模块，基于现有的摘要标记进行两阶段解码。一个模块处理学习到的 HSG 表示以获得第一阶段解码信息，随后将其放入第二阶段解码模块，该模块吸收提取的代码标记特征。接下来，$FFN$ 子层将解码后的向量作为非线性变换的输入。整个过程表述如下：

其中 $E_c^{\prime }\in R^{l_c\times d}$ 和 $E_n^{\prime }\in R^{l_n\times d}$ 分别表示提取的 HSG 和代码 token 的特征。

3.6. Copying mechanism

由于许多代码标记（例如变量和函数名称）可能存在于文本摘要和源代码中，我们根据编码器和解码器实现了复制机制多源指针生成器（MPG）网络，最终确定后续的摘要标记。基于多头注意力，MPG 允许 HetSum 生成更准确的摘要标记，这些标记都是在词汇表中选择的，并且是从输入 HSG 节点和源代码标记复制的。

如上图所示，为了生成第 $i$ 个摘要标记的输出似然，MPG 首先计算对应于摘要词汇表、代码标记和 HSG 节点的三个概率分布 $p_v$、$p_c$ 和 $p_n$。 $pv$ 是通过在解码的摘要标记向量 $e{\prime }_s\in Rd$ 上执行 $Softmax$ 的 $Linear$ 子层导出的，其定义如下：

如果候选标记 $w$ 不在摘要词汇表中，则 $p_v(w)$ 设置为 0。

$p_c$ 和 $p_n$ 是基于摘要解码器以及代码令牌和 HSG 编码器上的两个附加多头注意力子层计算的。具体来说，$p_c$ 是根据第 $i$ 个解码后的摘要标记向量 $e{\prime }_s$ 和编码后的代码标记 $E{\prime }_c$ 进行 $softmax$ 注意力值得出的，其公式如下：

其中 $w_j$ 表示第 $j$ 个源代码标记；${\bar{a}}_c\in R^{l_c}$ 表示注意力值。如果 $w$ 不是代码标记，则 $p_c(w)=0$。具体来说，MPG 中的注意力子层以 $e{\prime }_s$ 作为查询，以 $E{\prime }_c$ 作为键和值来得到 ${\bar{a}}_c$，其公式如下：

其中 $W_j^Q$、$W_j^K$ 和 $W_j^V$ 是可训练矩阵。此外，上下文向量 ${\theta }_c\in R^d$ 对于下一个摘要标记的最终输出似然至关重要，计算如下：

其中 $W^O$ 表示可训练参数，$a_j$ 来自上式

$p_n$ 和 ${\theta }_n$ 的计算过程与 $p_c$ 和 ${\theta }_c$ 的计算过程相同，唯一的区别是 $p_n$ 和 ${\theta }_n$ 的多头注意力中的 key 和 value 是编码后的 HSG $E{\prime }_n$。最后，候选标记 $w$ 的似然 $p_s(w)$ 定义为三个概率 $p_v、p_c$ 和 $p_n$ 的加权和：

其中 ${\eta }_v、{\eta }_c$ 和 ${\eta }_n$ 表示对应于 $p_v、p_c$ 和 $p_n$ 的权重。理论上，标记 $w$ 更有可能被视为具有较高概率 $p_s(w)$ 的下一个摘要标记。

4. Experiment

4.1 Experimental results

4.2 Ablation study

首先设计了四种变体模型来验证 HSG 的异构结构特征和源代码中的布局信息：

1. HSG-SibEdge，排除HSG中兄弟节点之间的边
2. HSG-DFGEdge，排除HSG中的DFG
3. HSG-Hetero，忽略HSG中的异构性，使用同构GraphSAGE进行语法结构学习
4. Code-SeqPos，将源代码标记视为先前工作中的自然语言序列，并将双重位置替换为顺序位置。

为了进一步研究HetSum模型架构的合理性，我们构建了八个变体：

1. 模型-HSGRes，消除了HSG编码器中层归一化的残差连接
2. 模型-HetGCN，用GCN替换HSGNN中使用的GraphSAGE
3. Model-HetGAT 引入 GAT 以取代 HSGNN 中的 GraphSAGE
4. Model-HSGEnc 删除 HSG 编码器
5. Model-CodeEnc删除代码令牌编码器
6. Model-EncRel，不将编码的代码令牌集成到 HSG 嵌入中，以丢弃两个编码器之间的关系
7. Model-DecInv，反转 HSG 和代码令牌特征的解码在摘要解码器中
8. 删除复制机制的模型复制。

请注意，GrapSAGE、GCN 和 GAT 都是常用于图学习任务的典型 GNN。

4.3 Model Size