RAP-Gen: Retrieval-Augmented Patch Generation with CodeT5 for Automatic Program Repair

INTRODUCTION

Program repair is one of the most important stages to maintain software quality, which however is a time-consuming and cost-dominating process in modern software development (Weiß et al., 2007; Planning, 2002). Therefore, there have been huge needs for Automatic Program Repair (APR) tools to ease the difficulty and cost of program repair for developers with use cases including search of patches at program development time (Muslu et al., 2012), build time (Urli et al., 2017; Martin et al., 2019) or run time (Perkins et al., 2009; Durieux et al., 2017).

A notable class of conventional techniques for APR is known as search-based (also referred to as generate-and-validate) approach (Goues et al., 2012; Weimer et al., 2009; Qi et al., 2014; Wen et al., 2018; Liu and Zhong, 2018; Jiang et al., 2018). They often search for repairs based on the fix patterns mined via manual heuristic rules (Kim et al., 2013; Qi et al., 2014; Tan and Roychoudhury, 2015) or redundancy-based techniques (Goues et al., 2012; Long and Rinard, 2016, 2015; Wen et al., 2018; Liu and Zhong, 2018; Jiang et al., 2018). The latter group of approaches make a redundancy assumption (White et al., 2019) that the fixed patch can often be found (or reconstructed) from elsewhere in the codebase (a donor code snippet). This hypothesis has been validated empirically by studies (Barr et al., 2014; Martinez et al., 2014) showing that a significant proportion of commits (3%-17%) are indeed composed of existing codebase.

Meanwhile, with the recent advancement in deep learning technologies, numerous deep learning (DL)-based APR approaches (Tufano et al., 2019; Chen et al., 2021a; Lutellier et al., 2020; Jiang et al., 2021; Zhu et al., 2021; Berabi et al., 2021) have been proposed to automate the repair process via parametric models in a purely data-driven manner. In this paradigm, the APR task is typically formulated as a neural machine translation (or sequence-to-sequence learning) problem (Sutskever et al., 2014) in order to translate a buggy (source) program into a correct (target) version. Despite their promising results in software intelligence tasks, their performance is often limited by the fixed set of model parameters to learn the highly complex distributional patterns for program repair, even with several hundreds of million parameters (Jiang et al., 2021; Zhu et al., 2021; Berabi et al., 2021).

To ease such burden on the parametric neural models, in this work, we propose a novel retrieval-augmented patch generation framework called RAP-Gen to additionally leverage relevant fix patterns from a patch retriever. Earlier APR techniques based on the redundancy assumption have shown that mining fix patterns from existing codebase (Goues et al., 2012; Jiang et al., 2018) or even external Q&As from StackOverflow (Liu and Zhong, 2018) can serve as crucial repair ingredients for APR. Our model, which is semi-parametric in nature, aims to combine both benefits of the implicit (parametric) end-to-end program repair learning and the explicit (non-parametric) fix pattern mining. One distinction from prior fix pattern mining work is that we utilize the top relevant bug-fix pair as a guiding fix pattern for a buggy patch instead of clustering the fix templates with hand-crafted heuristics. This retrieval-guiding strategy is also motivated by debugging behaviours of program developers, who often search for relevant bug-fix examples to distill some repair clues for bug fixing. Fig. 1 illustrates a motivating example, where we can find that the retrieved previous repair example informs a fix pattern of wrapping the string with an “Error” object for the “throw” statement, which guides the developer to fix the target bug under consideration.

In addition, we propose to adapt a Transformer-based (Vaswani et al., 2017) encoder-decoder model CodeT5 (Wang et al., 2021) as the unified foundation model of RAP-Gen for both patch retrieval and generation tasks. CodeT5 is a generic code-aware language model pretrained on large source code corpora in eight popular programming languages (including JavaScript and Java) curated from GitHub, achieving state-of-the-art (SoTA) performance in both code understanding and generation tasks. RAP-Gen adopts a stage-wise learning strategy to connect the patch retriever and patch generator: the patch retriever first searches for a relevant bug fix pattern and then pass it to the CodeT5 patch generator to synthesize a ranked list of fix patch candidates based on both the source buggy code and the retrieved external bug fix knowledge. While such retrieval-augmented generation paradigm has been explored in other tasks such as question answering (Karpukhin et al., 2020) and code generation and summarization (Parvez et al., 2021), we are the first to investigate its effectiveness for APR systems based on large-scale pretrained language models for code.

For the retrievers, we propose a hybrid approach that accounts for both lexical and semantic matching through sparse (BM25 (Robertson and Zaragoza, 2009)) and dense (DPR (Karpukhin et al., 2020)) retrieval based on the raw source code. We employ CodeT5’s encoder as our dense DPR retriever and propose to train it with a contrastive learning objective (van den Oord et al., 2018) using previous bug-fix pairs as the fix patch often shares most of semantics with its buggy patch. The dense DPR retriever is expected to capture deeper code semantics while the sparse keyword-based BM25 retriever focuses more on the lexical similarity which is sensitive to the choice of naming for code identifiers. Notably, the hybrid retriever is language-agnostic as it does not require any code-specific features such as abstract syntax trees (ASTs). Experiments reveal that our patch retriever is able to retrieve lexically and semantically relevant fix patterns to guide APR systems.

We investigate the effectiveness of RAP-Gen in different APR scenarios including JavaScript linter-raised diagnostics (TFix (Berabi et al., 2021)), Java bug-fix commits (Code Refinement (Tufano et al., 2019)), and real Java bugs accompanied with test cases in open source projects (Defects4J (Just et al., 2014)). Among these benchmarks, we formulate the APR problem as that given a buggy code patch, the APR model learns to predict a fix patch that repairs the bug from a codebase of previous bug-fix pairs written by developers. The correctness of the predicted fix patches are validated against either static analyzers (TFix) or unit testing (Defects4J), or via a direct comparison with the ground-truth fixes written by developers. Overall, extensive experimental results show that our RAP-Gen significantly outperforms existing DL-based methods on all these three APR benchmarks.

In summary, the paper makes the following contributions:

We propose a novel retrieval-augmented patch generation framework (RAP-Gen) for APR. It is a generic framework that can be easily integrated with any sequence-to-sequence learning models. To the best of our knowledge, this is the first work to leverage the power of retrieval in fix pattern mining for DL-based APR systems.

We present a hybrid patch retriever for fix pattern mining that accounts for both lexical and semantic matching through a combination of sparse and dense retrievers. It is a language-agnostic patch retriever using raw source code which does not require any code-specific features.

We propose to adapt a generic pretrained code-aware language model CodeT5 as a foundation model for RAP-Gen to fix various bugs. Moreover, we leverage it for both patch retrieval and generation task in a unified manner.

We extensively evaluate RAP-Gen on three APR benchmarks in JavaScript and Java. Results show RAP-Gen significantly outperforms SoTA DL-based methods on all benchmarks. Particularly, our best model yields substantial improvements (49.70 $\rightarrow$ 54.15 on exact match accuracy and 69.30 $\rightarrow$ 78.80 on error removal accuracy) on TFix over the previous SoTA T5-large model with a 3.5x larger model size than ours. On Code Refinement, RAP-Gen sets new SoTA exact match results of 24.80 and 15.84 over CodeT5’s 21.61 and 13.96 for the small and medium subsets. On Defects4J, RAP-Gen achieves new SoTA performance, repairing 15 more bugs (110 $\rightarrow$ 125) with perfect FL and 6 more bugs (68 $\rightarrow$ 74) without perfect FL than the previous SoTA models.

RELATED WORKS

In the past decades, automatic program repair (APR) has attracted growing attention and various APR techniques have been proposed to reduce the manual efforts in debugging. A notable class of conventional techniques for APR is known as search-based (or generate-and-validate) approach (Goues et al., 2012; Weimer et al., 2009; Qi et al., 2014; Wen et al., 2018; Liu and Zhong, 2018; Jiang et al., 2018). Earlier search-based APR techniques are often based on program modification or mutation with heuristic algorithm (Qi et al., 2014) or genetic programming (Yuan and Banzhaf, 2020) to produce a large pool of candidate fixes for validating with unit tests. The search strategy has been further extended to adopt fix patterns mined using redundancy-based techniques (Goues et al., 2012; Long and Rinard, 2016, 2015; Le et al., 2016; Wen et al., 2018; Liu and Zhong, 2018; Jiang et al., 2018). These approaches make a redundancy assumption (White et al., 2019) that the fixed patch can often be reconstructed from elsewhere in the codebase, which has been validated empirically by studies (Barr et al., 2014; Martinez et al., 2014) showing that a significant proportion of commits (3%-17%) are indeed composed of existing codebase. More redundancy-based techniques have shown that mining fix patterns from existing codebase (Goues et al., 2012; Jiang et al., 2018) or even external Q&As from StackOverflow (Liu and Zhong, 2018) can largely benefit APR systems.

Recently, with the recent advancement in deep learning (DL) approaches for natural language processing (NLP), many DL-based APR techniques (Tufano et al., 2019; Chen et al., 2021a; Lutellier et al., 2020; Jiang et al., 2021; Zhu et al., 2021; Berabi et al., 2021; Bui et al., 2022) have been proposed to automate the program repair process in an end-to-end data-driven manner. Motivated by the success of Neural Machine Translation (NMT), these techniques often formulate APR as a sequence-to-sequence NMT problem (Sutskever et al., 2014), which is to translate a buggy program into a fixed version. Various neural architectures have been explored in learning-based APR techniques. Earlier techniques (Tufano et al., 2019; Chen et al., 2021a) are based on recurrent neural networks (Hochreiter and Schmidhuber, 1997), which is further extended to convolution neural networks (Gehring et al., 2017) in CoCoNuT (Lutellier et al., 2020) and Transformer-based models (Vaswani et al., 2017) by many recent DL-based models including TFix (Berabi et al., 2021), CURE (Jiang et al., 2021), Recoder (Zhu et al., 2021), RewardRepair (Ye et al., 2022a), and SelfAPR (Ye et al., 2022b). Notably, many of these DL-based approaches explore improving APR by leveraging code-specific features such as abstract syntax trees (ASTs) (Zhu et al., 2021; Li et al., 2022b) and test execution diagnostics (Ye et al., 2022a, b). Specifically, Recoder (Zhu et al., 2021) learns the syntax-guided edits over the ASTs to ensure the syntactic correctness of the generated fix patch, while DEAR (Li et al., 2022b) uses tree-based Long Short-Term Memory (LSTM) model (Tai et al., 2015) to better encode the code structure and constructs a suitable fixing context using surrounding AST subtrees. For the use of test execution information, SelfAPR (Ye et al., 2022b) encodes test execution diagnostics into the input representation, while RewardRepair (Ye et al., 2022a) improves APR with a loss function based on both program compilation and test execution information.

In terms of APR benchmarks, the most popular one would be Defects4J (Just et al., 2014), which contains real bug-fix patches from open source GitHub projects and has been widely adopted by a large body of APR work (Lutellier et al., 2020; Jiang et al., 2021; Zhu et al., 2021; Ye et al., 2022a, b). One notable feature of this benchmark is that it contains a test suite to validate whether the bugs are fixed or not. However, as these APR approaches rely on test cases, they are inapplicable to newly discovered bugs or bugs difficult to test for deterministically (van Tonder and Goues, 2018). Additionally, it remains a key challenge to obtain a large-scale APR dataset with test cases, e.g., one of the largest one Defects4J only contains less than 1000 bugs and another popular one QuixBugs (Lin et al., 2017) only have 40 bugs. To get rid of the requirement of test cases, there is another group of APR research (van Tonder and Goues, 2018; Yoshida et al., 2020; Marcilio et al., 2020; Oh and Oh, 2022; Berabi et al., 2021) focusing on static analysis bugs or violations, which can be flagged by static analysis tools and is easier to curate much more bug-fix data. Besides, another type of APR (Tufano et al., 2019) is based on the bug-fixing commits by checking whether the commit comments contain some keywords such as “repair” and “fix”. We consider all these types of APR use cases in this work.

2. Pretrained Language Models for Code

Pretrained language models (LMs) like GPT (Radford et al., 2018), BERT (Devlin et al., 2019), and T5 (Raffel et al., 2020) have significantly boosted performance in a broad set of NLP tasks. Inspired by their success, much recent work (Feng et al., 2020; Guo et al., 2021; Lu et al., 2021; Phan et al., 2021; Ahmad et al., 2021; Chen et al., 2021b; Wang et al., 2021) attempts to adapt the NLP pretraining methods to programming language. They often rely on either an encoder-only BERT-style models (CodeBERT (Feng et al., 2020) and GraphCodeBERT (Guo et al., 2021)) or decoder-only GPT-style models (CodeGPT (Lu et al., 2021) and Codex (Chen et al., 2021b)), or encoder-decoder models (PLBART (Ahmad et al., 2021) and CodeT5 (Wang et al., 2021, 2023; Le et al., 2022)). Particularly, CodeT5 is a unified language model pretrained with a code-aware pretraining objective on large-scale code corpora covering 8 different programming languages, which has been shown to achieve SoTA performance on a wide range of code understanding and generation tasks (Lu et al., 2021). Compared to previous DL-based APR approaches such as CURE (Jiang et al., 2021) and TFix (Berabi et al., 2021) that utilize LMs pretrained primarily on natural language corpus, we propose to leverage the code-aware LMs of CodeT5 (Wang et al., 2021) for APR with better code understanding capability.

There are recent attempts (Joshi et al., 2022; Prenner et al., 2022) to explore few-shot learning of large language models (LLMs) for APR. According to Prenner et al. (2022), their method based on Codex achieves 46% EM compared to the finetuned T5’s 59% on a random sample of 200 instances from TFix, showing that there is still a gap between few-shot learning and finetuning results. Besides, few-shot learning of LLMs requires more engineering efforts for prompting tuning and post-processing (Joshi et al., 2022), which is labor-intensive. Another concern is that LLMs such as Codex (Chen et al., 2021b) are not open sourced and it might be expensive to use their APIs, e.g., the Davinci version costs $0.02 for every 1K tokenshttps://openai.com/api/pricing/.

3. Retrieval-Augmented Generation

A general retrieval-augmented generation paradigm is comprised of three components including information retrieval, data augmentation and generation model (Li et al., 2022a). It has been widely studied in NLP and shown to achieve SoTA performance in a wide range of NLP tasks including question answering and question generation (Lewis et al., 2020; Izacard and Grave, 2021) and machine translation (Gu et al., 2018). Inspired by their success, much research work adapts this paradigm (also referred as retrieve-and-edit/refine framework) to benefit software intelligence tasks, including code autocompletion (Hashimoto et al., 2018; Lu et al., 2022), code summarization (Parvez et al., 2021; Li et al., 2021), and code generation (Parvez et al., 2021; Wang et al., 2023).

APPROACH

We propose RAP-Gen, a novel retrieval-augmented patch generation framework for APR, which aims to improve APR performance by leveraging a relevant bug fix pattern retrieved from a codebase of previous bug-fix pairs. As shown in Fig. 2, our RAP-Gen framework consists of three stages: 1) a patch retriever training stage to learn a hybrid retriever that can find relevant code patches based on the lexical and semantical similarity; 2) a patch generator training stage to train a CodeT5 model to produce the fix patch based on both buggy input and retrieved bug-fix examples; 3) an inference stage to predict multiple fix patches where the top-ranked one will be passed to developers for verification.

Note that while retrieval-augmented generation techniques have been explored in many NLP tasks (Lewis et al., 2020; Izacard and Grave, 2021), it is not trivial to adapt such techniques to APR tasks and requires systematic adaptation to address some unique challenges. The first challenge is how to retrieve relevant fix patterns for effectively guiding APR, where we build a hybrid retriever based on both lexical and semantic information, which is analyzed and compared with other retrievers in Table 8. The second challenge is how to build a top-performing APR model for various languages and APR scenarios. We leverage a language-agnostic pretrained model CodeT5 for both retrieval and patch generation, which is a more unified approach compared to prior work (Parvez et al., 2021; Lu et al., 2022) requiring a different retriever and generator.

In the remainder of this section, we first introduce the task formulation of the retrieval-augmented patch generation for APR in Section 3.1 and then revisit the backbone model of CodeT5 in Section 3.2, followed by detailing the hybrid patch retriever in Section 3.3 and the retrieval-augmented patch generator in Section 3.4.

Let $\mathcal{D}=\{(X_{i},Y_{i})\}_{i=1}^{|\mathcal{D}|}$ be a program repair dataset consisting of $|\mathcal{D}|$ bug-fix pairs $(X_{i},Y_{i})$, where $X_{i}$ and $Y_{i}$ are the $i$-th buggy and fixed program patch, respectively. Assume that we have a codebase containing a large collection of previous bug-fix pairs $\mathcal{C}=\{(B_{j},F_{j})\}_{j=1}^{|\mathcal{C}|}$, where $(B_{j},F_{j})$ denotes the $j$-th previous bug-fix pair. Given a buggy program patch $X_{i}$ in $\mathcal{D}$, a retriever retrieves the most relevant bug-fix pair $(B_{j},F_{j})$ in the codebase $\mathcal{C}$ based on a relevance scoring function $f_{\phi}(X_{i},B_{j})$ parameterized by $\phi$. Then the original input sequence $X_{i}$ is augmented with the retrieved bug-fix pair to form a new input sequence $\hat{X}_{i}=X_{i}\oplus B_{j}\oplus F_{j}$, where $\oplus$ denotes the concatenation operation. The sequence-to-sequence (seq2seq) generator then generates $Y_{i}$ from $\hat{X}_{i}$ in an autoregressive manner. Formally, we aim to learn the following probability with the patch seq2seq generator parameterized by $\theta$:

where $Y_{i,1}:Y_{i,k-1}$ is the previous sequence before the $k$-th token and $n$ denotes the number of tokens in the target sequence $Y_{i}$. Note that we regard the external codebase $\mathcal{C}$ as a non-parametric memory and the retrieved bug-fix pair as a guiding fix pattern for the generator. In probabilistic terms, the retrieval can be formulated as a latent variable $Z_{j}=(B_{j},F_{j})$, which is approximated by top-1 in our case. Formally, the probability can be decomposed as:

where $Z_{j}^{*}$ is the top-1 retrieved output from the retriever $P_{\phi}(Z_{j}|X_{i})$. We adopt such top-1 approximation as marginalization over large $k$ makes the training and inference complicated and inefficient (Lewis et al., 2020). We also tried to employ top-$k$ ($k=2,3,5$) with the Fusion-in-Decoding or FiD method (Izacard and Grave, 2021) but did not observe a salient performance improvement.

2. Revisiting CodeT5

CodeT5 (Wang et al., 2021) is a unified pretrained Transformer-based encoder-decoder language model that achieves SoTA results in both code understanding and generation tasks. It is pretrained on 8.3 million functions in 8 different programming languages (i.e., Ruby, JavaScript, Go, Python, Java, PHP, C, C#) collected from GitHub. CodeT5 employs a set of identifier-aware pretraining objectives to incorporate the code-specific knowledge into the language model. In this work, we adapt CodeT5 as our dense DPR retriever and patch generator to harness its powerful code understanding capability.

One benefit of using CodeT5 is that it provides a code-specific Byte-Pair Encoding (BPE) (Sennrich et al., 2016) tokenizer. It can avoid the prevalent Out-of-Vocabulary (OoV) problems in the code domain as programmers tend to write arbitrary identifiers (Li et al., 2018) and it is impossible to build a fixed vocabulary to accommodate arbitrary tokens (commonly known as open vocabulary problem (Sennrich et al., 2016)). BPE is an algorithm that learns how to efficiently split tokens into subwords based on their frequency distribution. It can also help reduce the vocabulary size as it will split rare tokens into multiple subwords instead of directly adding the whole tokens into the vocabulary. Additionally, as the CodeT5 tokenizer is pretrained and optimized for eight popular programming languages, the resulting tokenization generalizes well. As pointed out by (Wang et al., 2021), it reduces the tokenized sequence by 30% - 45% on average compared to the default T5 tokenizer (Raffel et al., 2020).

CodeT5 consists of a stack of Transformer layers (Vaswani et al., 2017) for its encoder and decoder. Each Transformer layer contains a multi-head self-attention for feature aggregation followed by a feed forward layer over the output of previous layer. The final layer produces the hidden states for all input tokens, which can be employed as the code presentation for classification or generation tasks. For the CodeT5 encoder, it utilizes bidirectional attention masks to learn better contextualized representation similar to BERT (Devlin et al., 2019), while the CodeT5 decoder employs causal attention masks to ensure each token can only attend to the previous tokens for better sequence generation. In RAP-Gen framework, we adapt the CodeT5 as the patch generator and its encoder specifically for the dense retriever.

3. Hybrid Patch Retriever

The retriever module in RAP-Gen aims to retrieve relevant fix patterns to guide the APR process. It builds on a relevance scoring function $f_{\phi}(X_{i},B_{j})$ to compute the relevance between the (query) bug $X_{i}$ in $\mathcal{D}$ and a previous (key) bug $B_{j}$ in the codebase $\mathcal{C}$. As shown in 2 1, we utilize a hybrid approach to combine a lexical-based BM25 (Robertson and Zaragoza, 2009) retriever and a semantic-based DPR (Karpukhin et al., 2020) retriever to take both lexical and semantic information into account. Prior work like (Karpukhin et al., 2020) show that sparse and dense retriever can complement each other for more robust text retrieval.

We employ BM25 (Robertson and Zaragoza, 2009), a well-known term-based retriever that uses sparse vector representation for lexical matching. BM25 converts each code patch as bag-of-words representation and computes a lexical similarity between the query patch $X_{i}$ and a candidate patch $B_{j}$. The computed similarity score is represented as $f_{\phi}(X_{i},B_{j})=BM25(X_{i},B_{j})$. As a sparse term-based retriever, BM25 is sensitive to the choice of identifier naming in source code which does not impact the code semantics.

We employ Dense Passage Retriever (DPR) (Karpukhin et al., 2020) to retrieve relevant patches via measuring their semantic similarity. To encode the code patch, we use a Transformer-based encoder to map each patch to a fixed-size dense vector. Specifically, we initialize the DPR from a pretrained CodeT5 encoder and train it for a code-to-code retrieval task. For training the DPR, we propose to use the bug-fix pairs in the codebase by considering the buggy code $B_{j}$ as the query and the corresponding fixed code $F_{j}$ as the key. This is based on the assumption that the buggy patch and its fixed patch often shares similar semantics (e.g., identifiers and code structures). This trick avoids the massive manual annotation efforts needed to curate a bug-to-bug search dataset.

For each query patch and candidate patch, we prepend a special token of [CLS] into its tokenized sequence and employ the final layer hidden state of the [CLS] token as the patch representation. We use a shared DPR to separately encode the query patch $X_{i}$ in $\mathcal{D}$ and a candidate patch $B_{j}$ in $\mathcal{C}$ as $CLS_{X_{i}}$ and $CLS_{B_{j}}$, respectively. Then the similarity is computed by the inner product between these two patch representations as the following:

For training the DPR retriever, we leverage the in-batch negatives to optimize an InfoNCE contrastive loss (van den Oord et al., 2018) defined as follows:

where $\mathcal{M}$ is the current minibatch and $N$ denotes the number of positive training examples in the minibatch. This objective aims to maximize the similarity between positive examples while minimizing the similarity between negative examples. Each positive example will have $|\mathcal{M}|-1$ negative samples. Note that we do not adopt the hard negative mining strategy as in (Karpukhin et al., 2020) due to the noisy nature of the training data.

In the inference stage, given a query buggy patch $X_{i}$, the DPR retrieves a relevant bug-fix pair $(B_{j},F_{j})$ by computing the similarity between $X_{i}$ (query) and $B_{j}$ (key). We also tried to base on the similarity between $X_{i}$ and $F_{j}$ but it did not yield better results.

To take both lexical and semantic information into account, we utilize a hybrid approach following (Karpukhin et al., 2020) to combine the BM25 and DPR. The similarity score is computed as $f_{\phi}(X_{i},B_{j})=sim(X_{i},B_{j})+\lambda~{}\text{BM25}(X_{i},B_{j})$, where $\lambda$ is a weight to balance the two retrievers and was empirically set to 1 in our experiment. Based on this combined similarity score, we select the top-1 relevant bug-fix pair $(B_{j},F_{j})$ as a fix pattern to guide the patch generator for bug fixing. The hybrid retriever is expected to be more robust compared to retrievers that rely only on either lexical or semantic information.

4. Retrieval-Augmented Patch Generator

As shown in Fig. 2 2, given a buggy patch $X_{i}$, we search for a top relevant fix pattern $(B_{j},F_{j})$ and pass it to the patch generator to generate a fixed code patch $Y_{i}$. We adopt a simple yet effective strategy to augment $X_{i}$ into $\hat{X}_{i}=X_{i}\oplus B_{j}\oplus F_{j}$ via appending the retrieved bug-fix pair into the source buggy patch. Note that the patch generator module can be any sequence generation model. Different from prior studies that directly adopt a generator optimized on natural language (Berabi et al., 2021), we propose to employ CodeT5, a code-aware programming language model optimized for code.

We prepare the retrieval-augmented input to CodeT5 patch generator as $\hat{X}_{i}$ = “[CLS] Xi [BUG] $B_{j}$ [FIX] $F_{j}$”, where [BUG] and [FIX] are special tokens to separate the retrieved bug-fix pair from the buggy patch. CodeT5’s encoder takes $\hat{X}_{i}$ as input and emits the fixed patch $Y_{i}$ from its decoder in an autoregressive manner (see Section 3.1). We consider two settings of the buggy patch $X_{i}$ where it may or may not contain bug localization information. If it contains error information like error type, error message, and error line, the buggy patch will be augmented to “error information [SEP] $X_{i}$” to incorporate error information to help fix the bugs. To train the patch generator, we adopt teacher forcing (Toomarian and Barhen, 1992) to minimize the cross entropy loss $\mathcal{L}_{ce}$ over all training instances defined as:

In teacher forcing, the decoder uses ground-truth context for faster convergence. We use the training set as the search codebase following (Parvez et al., 2021). To avoid information leakage, we do not allow the retriever to access the ground-truth bug-fix pair, otherwise the training loss would easily drop close to 0 as the generator can directly copy the retrieved fix as the target output. This strategy makes the training and evaluation process more compatible as the evaluation sets are not overlapped with the training set as well.

During inference, as shown in Fig. 2 3, we employ beam search to generate a ranked list of fixed patch candidates for an input buggy patch, where the number of predictions is determined by the beam size $\mathcal{B}$. Concretely, at each decoding timestep, the beam search selects the most $\mathcal{B}$ promising fix candidates with the highest probability using a best-first search strategy. The search process is terminated when an [EOS] token notifying the end of sentence is emitted. The top ranked fix patch will be examined for its correctness by comparing with ground-truth fix patches or by validating against test suites, or by manual verification by software developers.

Experimental Design

We evaluate RAP-Gen on three APR datasets, namely TFix (Berabi et al., 2021) in JavaScript, Code Refinement (Tufano et al., 2019) and Defects4J (v1.2) (Just et al., 2014) in Java. All datasets are originally collected from open source GitHub commits but based on different criteria for bug identification, where TFix is based on diagnostics from a JavaScript static analyzer, Code Refinement is based on repair-related commit message, and Defects4J is based on running the test suites. We report their data statistics in Table 1.

TFix (Berabi et al., 2021) is a large-scale program repair dataset comprising JavaScript code patch pairs curated from 5.5 million GitHub commits. It includes 52 error types (see Table 4) detected by a static analyzer ESLinthttps://eslint.org/ (Tómasdóttir et al., 2017). In addition to error types, it provides rich error annotations such as error message and localized error line so that there is no need for fault localization like prior work (Jiang et al., 2021; Zhu et al., 2021). To prepare the input sequence, as illustrated in Fig. 3(a), we follow (Berabi et al., 2021) to combine all error information together with the buggy code patch into a single piece of text as the following:

where error context consists of the given localized error line and its two neighboring code lines to form a buggy code patch. For the target sequence, it is obtained by replacing the error line into a fixed line in the error context. During data processing, we observed a duplication issue inside each data split and between data splits. Specifically, there are 114, 2, and 4 duplicates in the train, validation, and test split respectively, and 28, 34, and 4 duplicates for inter-split duplicates between train and test, train and test, validation and test splits respectively. We filtered all these 243 duplicates to get a deduplicated version of TFix as shown in Table 1.

Baseline Models. We compare RAP-Gen with existing DL-based APR models including SequenceR (Chen et al., 2021a) and CoCoNuT (Lutellier et al., 2020). Besides, we compare a large pretrained model T5-large (Raffel et al., 2020) which has been finetuned on TFix to achieve the SoTA performance by (Berabi et al., 2021).

Evaluation Metrics. We report Exact Match (EM) accuracy and BLEU-4 score to evaluate program repair performance following (Wang et al., 2021) on TFix. BLEU-4 is a looser metric to evaluate the degree of subword overlapping while EM is a more strict metric requiring the prediction to be identical to the ground-truth patch in a real commit. As a buggy program might have different ways to repair, we further employ Error Removal metric following (Berabi et al., 2021) to take various forms of fixes into account. The prediction is counted as correct for Error Removal if the existing error is removed and no new errors (detected by the static analyzer ESLint) is introduced after the fix. For all metrics, we present their results on a scale of 0-100 (%) and a higher score represents better performance.

1.2. Code Refinement

Code Refinement (Tufano et al., 2019) contains bug-fix pairs at the function level, which are originally collected from public GitHub Archivehttps://www.gharchive.org/ between March 2011 and October 2017. They use Google BigQuery APIs to identify all Java commits having a message containing the patterns: (“fix” or “solve”) and (“bug” or “issue” or “problem” or “error”) to ensure the quality of the collected bug-fix function pairs. They normalized the functions via obfuscating identifiers with indexed tokens such as TYPE1, VAR1, METHOD1, etc. One data example can be found in Fig. 3 (b). The dataset contains two data subsets which are determined by the number of tokens, i.e., # of code tokens $\leq$ 50 for the small set and 50 $<$ # of code tokens $\leq$ 100 for the medium set. Since the bug localization is not provided, the entire code fragment is taken as the source input sequence of our model. The target sequence is the refined version of the whole code snippet.

Baseline and Metrics. We compare our RAP-Gen with pretrained programming language models based on Transformers (Vaswani et al., 2017). One group of these models is the encoder-only models such as RoBERTa (code), CodeBERT (Feng et al., 2020), and GraphCodeBERT (Guo et al., 2021). These encoder-only models require a randomly initialized decoder to generate the fix. Besides, we compare with encoder-decoder Transformer models such as PLBART (Ahmad et al., 2021) and CoTexT (Phan et al., 2021). NSEdit (Hu et al., 2022) is a language model with encoder and decoder initialized from CodeBERT and CodeGPT (Lu et al., 2021) respectively. It is finetuned to generate the fix via a neural-symbolic editing sequence and ranks as the current SoTA model on Code Refinement. We follow (Wang et al., 2021) to apply BLEU-4 and Exact Match to evaluate the Code Refinement datasets.

1.3. Defects4J

Defects4J (Just et al., 2014) has been one of the most widely adopted APR benchmarks, which contains 835 real bug-fix patches in 17 open source GitHub projects. Each bug-fix example is accompanied with test cases to validate the fix. One example of Defects4J bugs can be found in Fig. 3(c), where “-” denotes a buggy line to be fixed and “+” represents the correct fix committed from a developer. A buggy line and its corresponding code context are combined to form the source input sequence while the target sequence is the fixed line. As Defects4J only has the test set, we use the project-specific training data curated by SelfAPR (Ye et al., 2022b) using self-supervised learning methods. Specifically, Ye et al. (2022b) proposes 16 perturbation rules on the correct past version of Defects4J to construct 1,039,873 synthetic bug-fix Java patches. We use a subset of 830,240 training data that is available online.https://github.com/ASSERT-KTH/SelfAPR/tree/main/dataset For testing, we follow their exact settings to evaluate our models on 818 bugs from both Defects4J v1.2 and v2.0 (Table 1), which covers both settings with ground-truth fault localization (perfect FL) and with predicted FLs from spectrum-based FL tools such as Gzoltar (Riboira and Abreu, 2010).

Baselines and Metrics. We compare RAP-Gen with a broad set of SoTA DL-based APR models including SequenceR (Chen et al., 2021a), CoCoNuT (Lutellier et al., 2020), CURE (Jiang et al., 2021), RewardRepair (Ye et al., 2022a), Recoder (Zhu et al., 2021), DLFix (Li et al., 2020), DEAR (Li et al., 2022b), BugLab (Allamanis et al., 2021), and SelfAPR (Ye et al., 2022b). For evaluation, we compute how many bugs can be correctly fixed on Defects4J based on unit testing and manual verification following prior work. We first run test suites to automatically identify plausible correct patches for each bug, followed by manual checking to completely verify its correctness. The correct predictions from our RAP-Gen are included in our artifact. For results of baselines, we cite the results of DLFix and DEAR from DEAR (Li et al., 2022b), and other results from SelfAPR (Ye et al., 2022b).

2. Implementation Details

We adopt CodeT5-base (Wang et al., 2021) that contains 12 encoder layers and 12 decoder layers with the parameter size of 220M for RAP-Gen. We implement RAP-Gen using PyTorch and train it with AdamW (Loshchilov and Hutter, 2019) optimizer. For the training of its neural components, we run these experiments with NVIDIA A100-40G GPUs on the Google Cloud Platform. For each benchmark, we finetune a DPR retriever for 50 epochs using the contrastive loss $\mathcal{L}_{\text{infoNCE}}$ using a batch size of 64 and a learning rate of 2e-5. We finetune RAP-Gen generator for 30 epochs using a sequence generation loss $\mathcal{L}_{ce}$ using a batch size of 32 with a learning rate of 5e-5. These best settings are obtained through a grid search for hyper-parameter tuning: batch size in (16, 32, 64) and learning rate in (1e-4, 5e-5, 2e-5). The training time of DPR retriever is 5-9 hours depending on the training size of the dataset, and the training time of RAP-Gen generator is within 2 days. For lexical-based retrievers, we use an open-sourced Python libraryhttps://pypi.org/project/rank-bm25 of BM25, which can be efficiently trained on CPU within one hour with multi-processing. During inference, we employ beam search with a beam size of 5 for the TFix and Code Refinement, and 100 for the Defects4J.

3. Research Questions

To investigate the effectiveness of RAP-Gen on APR tasks, we seek to answer the following research questions (RQs):

RQ1: Comparative study with DL-based APR models on TFix. How does RAP-Gen perform to repair JavaScript linter-flagged coding errors on TFix compared with other DL-based APR approaches?

RQ2: Analysis of RAP-Gen predictions on TFix. How does RAP-Gen repair TFix bugs for different error types and patch lengths? What fix operations do RAP-Gen adopt in repairing bugs?

RQ3: Comparative study with DL-based APR models on Code Refinement. How does RAP-Gen perform to repair Java commit-related bugs compared with other DL-based APR approaches?

RQ4: Analysis of our hybrid patch retriever. Can our hybrid patch retriever find relevant fix pattern to guide APR?

RQ5: Comparative study with DL-based APR models on Defects4J? How does RAP-Gen perform to repair Java bugs in open source projects compared with other DL-based APR approaches?

EXPERIMENTAL RESULT

The original TFix benchmark employs the direct average of exact match (EM) accuracy across 52 error types as the main metric. However, as shown in the Table 4, these error types have a rather imbalanced distribution, e.g., the major error type “no-invalid-this” has 16,166 instances while the least error type “no-new-symbol” has only 10 instances. As such, it is more reasonable to employ the weighted average to take the error type distribution into account. Besides, we spot another limitation of its exact match evaluation that if the predicted fix contains one more whitespace such as a space or new line than the ground-truth fix, it would be regarded as a wrong exact match. However, extra whitespaces do not impact the correctness for JavaScript programs. Therefore, we propose to use the weighted average of EM w/o spaces, which normalizes the whitespaces before computing the EM to exclude the effects of the mismatch in whitespaces. As we find there is a duplication issue in the TFix dataset, we also report the results on its deduplicated version.

1.2. CodeT5 Results

We compare CodeT5 models with other DL-based baselines on TFix and show results in Table 2. For the original metric of average EM w/ spaces, CodeT5-base (50.88) also yields a better accuracy than T5-large (49.33), given that it has much larger model size ($\sim 3.5\times$ of CodeT5-base: 770M vs. 220M). If we focus on a more reasonable average EM w/o spaces, CodeT5-base significantly boost the performance, with around 5 absolute accuracy improvement (49.35$\rightarrow$54.30) over T5-large. Based on the weighted average EM w/o spaces, both CodeT5-small (50.31) and CodeT5-base (53.57) outperform all the baselines including T5-large (49.70). This shows CodeT5 models with code-aware pretraining on large-scale source code have a better understanding of program. For TFix evaluation, we employ EM to denote the weighted average EM w/o spaces. We perform an ablation study to remove the error information including error type and error message from the input sequence, where we observe both CodeT5-small and CodeT5-base models have a consistent performance downgrade, revealing that it is helpful to inform which types of error they need to fix for APR models.

1.3. RAP-Gen Results

We report the results of our RAP-Gen model on the deduplicated TFix benchmark in Table 3, where the results are slightly different due to data size changes after duplication. Results show that RAP-Gen significantly outperforms T5-large (49.58$\rightarrow$54.15 EM). This indicates retrieval-augmented generation is a viable and effective approach for APR and both semantic information and lexical information are crucial to retrieve relevant fix patterns. We present one case in Fig. 3 (a), where we can observe RAP-gen successfully repairs the bug with the guidance of retrieved fix pattern while CodeT5 without retrieval gives a wrong fix.

1.4. Error Removal Evaluation

Though exact match can ensure correctness of machine-generated patches, it might be a too strict metric to consider other forms of correct fixes. Therefore, we follow (Berabi et al., 2021) to employ the error removal metric, where a fix is counted as correct if the error is removed and no new error is introduced. The error detection is based on a static analyzer ESLint. We report error removal together with EM and BLEU-4 results on a large subset of 6,793 instancesSome source files are unavailable to reproduce this metric on the full test set. in Fig. 4. We observe that RAP-Gen significantly improves error removal accuracy over T5-large (69.30$\rightarrow$78.80). The larger gain compared to EM and BLEU-4 implies that RAP-Gen is more capable of producing various forms of good fixes. Additionally, EM is well aligned with the looser metric of error removal.

2. RQ2: Analysis of RAP-Gen on TFix

We list the performance breakdown for 52 error types on the deduplicated TFix in Table 4. RAP-Gen outperforms the previous SoTA T5-large in 40/52 error types. Especially for the major error type “no-invalid-this”, RAP-Gen improves its exact match from T5-large’s 37.48 to 44.13, i.e. repairing more 107 instances. In total, RAP-Gen correctly repairs more 478 bugs than T5-large with a much smaller model size.

2.2. Fix Operation Analysis

We analyze what fix patterns are performed by our models on TFix. We observe a large proportion of fix consists of deletion operations compared to the code insertion and replacement operations. We find that fix operations consist of code insertion (12.5%), replacement (8.1%), deletion (47.9%), insertion and replacement (6.9%), insertion and deletion (8.2%), replacement and deletion (7.2%), and all three manners (9.2%). Earlier studies (Qi et al., 2015; Tan et al., 2016) also reflect that the deletion operation is one of the most common fix patterns. Besides, we find one dominating fix operation is error line (EL) removal, which is to simply remove the error line from the buggy code and accounts for around 23% in the test set. We show how models perform this operation in Table 5. We observe RAP-Gen achieves the best precision, recall, and F1 scores with a lowest false positive count of 56 compared to CodeT5’s 67 and T5-large’s 71. This indicates that RAP-Gen is able to learn more diverse bug fix patterns instead of over relying on the trivial error line removal pattern.

2.3. Patch Length Analysis

We analyze the impacts of patch length Fig. 5. Fig. 5 (a) shows the cumulative fraction of buggy patches by its patch length grouped based on their outcome. We find the patches successfully repaired by RAP-Gen tend to be shorter than those where it fails. Fig. 5 (b) shows the distribution of correct fixes by its buggy patch length, where RAP-Gen can repair more bugs than T5-large especially for patches with 40 to 60 tokens.

3. RQ3: Comparative study with DL-based APR models on Code Refinement

We report the comparison results on Code Refinement in Table 6. All baseline results are directly obtained from their original papers. We first observe that “Naive Copy” gives a pretty high BLEU-4 score but with a zero exact match, indicating the buggy code and its fix has a large overlap and exact match should be employed as the primary metric. Among the baselines, NSEdit is a very competitive one with a best result (24.04 EM) on the small subset and CodeT5 gives the best result (13.96 EM) on the medium set. The lower results on the medium set compared to the small set indicates that longer buggy functions are more difficult to fix, which is aligned with observations in Fig. 5 (a). Overall, RAP-Gen achieves new SoTA results on two subsets with 24.80 EM for small set and 15.84 EM for medium set. This again confirms that retrieved fix patterns provide helpful signals to guide the program repair and the hybrid retriever is more robust by using both lexical and semantic information. Fig. 3 (b) shows one case where the retrieved fix pattern (error line removal) helps RAP-Gen to successfully fix the bug.

4. RQ4: Analysis of Hybrid Patch Retriever

We investigate how different retrieval modules affect the APR performance in the retrieval-augmented generation setting in Table 7. We first compare with a Random baseline via randomly retrieving bug-fix pairs from the codebase. The consistent performance downgrade compared to “no retriever” implies that randomly retrieved fix patterns cannot provide useful guiding signals for APR. Then we compare our hybrid retriever in RAP-Gen with different retrievers: sparse BM25 retrievers, and dense retrievers based on CodeBERT or CodeT5. We observe that CodeT5-based retrievers outperforms either BM25 or CodeBERT-based retrievers, while our hybrid retriever combining both BM25 and CodeT5 achieves the best APR performance, validating the effectiveness of our retriever module design in RAP-Gen.

We further analyze the performance of our retrievers in terms of lexical and semantic matching between the query and the top retrieved patches. We employ the BLEU-4 score to measure their subtoken overlap for lexical matching, while for semantic matching, we compute the cosine similarity (CosSim) between their dense vectors encoded by our fine-tuned DPR retriever. Table 8 shows the performance of our retrievers on both TFix and Code Refinement benchmarks. The first row indicates the lower-bound performance via randomly retrieving bug-fix pairs from the codebase, where we observe this Random baseline achieves much lower scores in both lexical and semantic matching.

For lexical matching, BM25 outperforms DPR (CodeT5-based) on TFix but underperforms on two Code Refinement subsets. We anticipate that it is due to the data difference between TFix and Code Refinement, where the latter employs obfuscated identifiers (e.g., VAR1, VAR2, …) that hinders the performance of the lexical-based BM25 retriever. The hybrid retriever achieves the best lexical matching on all datasets, revealing the semantic information can complement to the lexical information. For semantic matching, DPR achieves the best results on all datasets, which is not surprising as it is optimized towards the identical objective. Notably, our hybrid retriever achieves slightly lower results than DPR but much better results than BM25, implying it can balance both lexical and semantic information and be more robust than the lexical-based retrievers, which are sensitive to the choices of identifier naming.

5. RQ5: Comparative study with DL-based APR models on Defects4J

We compare RAP-Gen with other SoTA DL-based APR baselines on Defects4J (Just et al., 2014) v1.2 and v2.0 in Table 9. We consider two settings with spectrum-based fault localization (FL) and with the perfect FL. Note that all the baseline results are cited from SelfAPR (Ye et al., 2022b) and DEAR (Li et al., 2022b). For a fair comparison, we follow common practice to adopt the same 5-hour timeout, a beam size of 100, an ensemble strategy as Recoder (Zhu et al., 2021) for RAP-Gen.

As shown in Table 9, our RAP-Gen achieves new SoTA performance under perfect FL by repairing the largest set of bugs (72 bugs in v1.2 and 53 bugs in v2.0) compared to other baselines. Particularly, it repairs 7 and 8 more bugs than the previous SoTA SelfAPR in v1.2 and v2.0 respectively. For the results with spectrum-based FL, RAP-Gen achieves the second-best performance, which are very competitive to the SoTA models on both v1.2 (48 vs. Recoder’s 49) and v2.0 (26 vs. SelfAPR’s 28). Considering both v1.2 and v2.0 bugs, it repairs 74 bugs in total, surpassing either Recoder’s 68 or SelfAPR’s 67 bugs. Overall, both results with or without perfect FL validate the superiority of our RAP-Gen over other DL-based baselines. Notably, compared to many of these models, our RAP-Gen exhibits another advantage of being a language agnostic model that can generalize to other APR use cases. By contrast, Recoder requires to learn edits over AST and SelfAPR requires the test execution diagnostics, making them inapplicable or limited to deal with fragmented code snippets that cannot be parsed into ASTs or other APR scenarios without test cases.

We investigate to what extent RAP-Gen can complement existing APR models, including Recoder (Zhu et al., 2021), RewardRepair (Ye et al., 2022a), and SelfAPR (Ye et al., 2022b). Compared with these SoTA DL-based APR approaches, RAP-Gen repairs 13 and 12 unique bugs for Defects4J v1.2 and v2.0 respectively, which are never correctly addressed by any other DL-based APR approaches, veifying that our RAP-Gen can complement to other top-performing APR approaches. We further show a case in Fig. 3 (c) and find that RAP-Gen successfully fixes the Chart-9 bug but in a different form with the developer’s fix.

5.2. Effects of Retrieval from Various Fix Patterns.

We analyze how retrieving a bug-fix sample from various fix patterns will affect the APR performance. For this analysis, as shown in Fig. 6, we select 39 bugs from Defects4J v1.2 and v2.0 which CodeT5 cannot fix (red) and RAP-Gen can fix (green) under the setting with perfect FL. For the categorization of fix patterns, we base on the 16 perturbation rules devised from SelfAPR (Ye et al., 2022b) and use its training set for each rule as a separate retrieval codebase. We retrieve the top-1 bug-fix sample from the codebase for each rule or fix pattern (denoted as P1 to P16) and examine whether it can improve CodeT5’s performance after using the guiding signals from such retrieval in RAP-Gen.

From Fig. 6, we observe that retrievals from various fix patterns in RAP-Gen are generally helpful in correcting CodeT5’s predictions on Defects4J bugs. We find that most of bugs in v1.2 can be fixed after retrieval from many different patterns, while for v2.0, there are some bugs where only a few fix patterns are applicable, e.g., the P16 for Closure-150 and P5 for JacksonDatabind-54. Across various fix patterns, we find that the P13 of “insert an existing block” and P14 of “delete statement” are applicable to most bugs, indicating these are key fix patterns for repairing Defects4J bugs.

Threats to validity

We evaluated RAP-Gen on three APR benchmarks: TFix in JavaScript, Code Refinement and Defects4J in Java. On TFix, we spotted a duplication issue and removed 243 intra-split or inter-split duplicates out of total 104,804 data instances. This might slightly impact the comparison between our model and the TFix (T5-large) model. We mitigate this threat by reporting the results of our model on the original TFix dataset and also the results of TFix model on the deduplicated test set. On Code Refinement, unlike the pairs in TFix can be validated by a static analyzer, its bug-fix pairs are curated from GitHub commits with a bug-fix related commit message, and only a portion of them are manually verified (Tufano et al., 2019). There is a chance that some pairs are invalid (not related to the bug fix), which brings potential threats to the reliability of the evaluation on this dataset.

The threats to internal validity mainly lie in the hyper-parameter search stage for RAP-Gen. As a neural model, its performance is highly affected by the choice of hyper-parameters. To alleviate such threats, we conduct a grid search to tune a better set of hyper-parameters but we still cannot claim they are the best.

We only evaluated our RAP-Gen model on JavaScript and Java programs and do not study its generalization to other programming languages (PLs). However, our approach is language-agnostic as we do not employ any code-specific features like ASTs and can be applied in a drop-in fashion to other PLs. Besides, our evaluation on three APR datasets in two PLs should be comprehensive enough to verify the effectiveness of our approach.

CONCLUSION

We present a novel retrieval-augmented patch generation (RAP-Gen) framework for automatic program repair, a fundamental task in software engineering to reduce developers’ manual efforts in debugging. RAP-Gen consists of two components: a hybrid patch retriever to retrieve relevant fix patterns for a query buggy patch and a patch generator to synthesize the fixed patch based on both buggy patch and its retrieved guiding fix patterns. In addition, we propose to leverage a powerful code-aware pretrained language model CodeT5 as the backbone of RAP-Gen to facilitate both patch retrieval and generation in a unified manner. Comprehensive results on three diverse APR benchmarks in JavaScript and Java have demonstrated the effectiveness and superiority of our RAP-Gen model over existing deep learning-based APR approaches.

Data Availability

Our code and models can be found in this link (https://figshare.com/s/a4e95baee01bba14bf4b) to reproduce the results in this paper.

References