Extracting Concise Bug-Fixing Patches from Human-Written Patches in Version Control Systems

An overview of the proposed approach is presented in Fig. 2. It takes as input two consecutive versions of a software application, i.e., $V_{n-1}$ and $V_{n}$. The latter version $V_{n}$ is called $V_{fix}$ or fixed version in Defects4J [14], and $V_{n-1}$ is called faulty version. Notably, the two consecutive versions are accompanied by their test cases, noted as $T_{n-1}$ and $T_{n}$, respectively. $T_{n-1}$ and $T_{n}$ exclude such test cases that fail on their associated version of the application. The evolution from $V_{n-1}$ to $V_{n}$ is driven by a bug-fixing commit whose commit message contains an ID of a validated bug report. With such input, the proposed approach BugBuilder works as follows:

• •

  First, it leverages RefactoringMiner [34] to discover refactorings that have been applied to $V_{n-1}$. RefactoringMiner is a state-of-the-art approach to mining software refactorings by comparing two consecutive versions of the same application. It would result in a list of refactorings, noted as $R$.

• •

  Second, if any refactorings have been discovered in the preceding step, i.e., $R$ is not empty, BugBuilder leverages refactoring APIs to apply all of the discovered refactorings to $V_{n-1}$. Applications of such refactorings on $V_{n-1}$ results in a new version $V_{n-1}^{\prime}$ that is different from both $V_{n-1}$ and $V_{n}$. For convenience, we call it refactoring-included version.

• •

  Third, BugBuilder computes the difference between the refactoring-included version ($V_{n-1}^{\prime}$) and the fixed version $V_{n}$. The difference is represented as a sequence of changes (e.g., removing or inserting a token), noted as $Chgs$.

• •

  Fourth, BugBuilder enumerates all possible subsequences of $Chgs$, and validates whether the subsequence represents a candidate patch. To validate a subsequence $schg\subseteq Chgs$, BugBuilder applies all changes in $schg$ to $V_{n-1}^{\prime}$, which results in a new version $V_{n-1}^{\prime\prime}$. $schg$ represents a candidate patch if and only if $V_{n-1}^{\prime\prime}$ passes all test cases in $T_{n-1}$ and passes some test cases in $T_{n}$ that fail on $V_{n-1}$.

• •

  Finally, if only a single candidate patch is generated by BugBuilder, BugBuilder outputs it as a patch for the associated bug report. Otherwise, no patch would be outputted.

Notably, the patches generated by BugBuilder are intended to be applied to $V_{n-1}^{\prime}$ (refactoring-included version) instead of $V_{n-1}$ (the original buggy version). Consequently, applying such patches to the original buggy version may result in compilation errors and may fail to fix the defects. Although we may revise BugBuilder to generate patches that could be directly applied to the original buggy version, we decide to follow the widely used Defects4J whose patches are also intended to be applied to $V_{n-1}^{\prime}$ (called $V_{bug}$ in Defects4J [14]) so that existing tools and algorithms could seamlessly switch from Defects4J to ours.

The key to exclude refactorings from bug-fixing patches is to discover refactorings involved in bug-fixing commits and remove such refactorings before patches are generated. A few automatic approaches[38, 39, 40, 41, 42] have been proposed to discover refactorings from version control systems for various reasons, e.g., to facilitate the evaluation of automatic refactoring recommendation algorithms, empirical studies on code evolution, and library API migration. However, to the best of our knowledge, such approaches have not yet been applied to automatic extraction of patches.

A brief introduction to automatic refactoring detection is presented as follows to make the paper self-contained, and more details are referred to related work [34, 43]. An automatic refactoring detection algorithm takes as input two consecutive versions (noted as $V_{n-1}$ and $V_{n}$, respectively) of the same application, and matches elements (e.g., classes, methods, and variables) across versions. Based on the matched elements, the algorithm identifies which elements in the former version (i,e., $V_{n-1}$) have been removed, which elements in the latter version (i.e., $V_{n}$) have been added, and which elements are kept untouched. The algorithm then defines a list of rules to detect refactorings based on the removed, added, and untouched elements. For example, if a method $m$ in class $C_{1}$ (of version $V_{n-1}$) matches a method $m^{\prime}$ in class $C_{2}$ (of version $V_{n}$) and $C_{1}$ does not match $C_{2}$, the algorithm recognizes the changes as a move method refactoring that moved method $m$ from class $C_{1}$ to class $C_{2}$. The performance of the algorithm depends on the accuracy of the employed element matching algorithms as well as the quality of the employed heuristic rules. RefactoringMiner [34] is more accurate than the alternative algorithms because it leverages an AST-based statement matching algorithm that does not require any user-defined thresholds [43]. To this end, we leverage RefactoringMiner to discover refactorings in bug-fixing code commits (excluding those on test cases).

The proposed approach excludes the discovered refactorings by reapplying such refactorings on the faulty version $V_{n-1}$, and employs the resulting version (called $V_{n-1}^{\prime}$) instead of the original faulty version $V_{n-1}$ to generate patches. The rationale is that we can divide the revision (bug-fixing commit) into two steps: (i) applying refactorings on $V_{n-1}$, which results in an intermediate version $V_{n-1}^{\prime}$; and (ii) fixing bugs and implementing new features (if there is any) on $V_{n-1}^{\prime}$. For convenience, we call the intermediate version $V_{n-1}^{\prime}$ refactoring-included version. Notably, reapplication of the discovered refactorings is accomplished by calling Eclipse refactoring APIs[44]. Such APIs are widely used and well-established. For example, if a bug-fixing commit contains a rename refactoring that changes the name of method $m$ from oldName to newName, we reapply the refactoring as follows:

Invocations of Eclipse refactoring APIs are highlighted with gray background in the code snippet. Notably, we have to customize the code snippet for different categories of refactorings to forward refactoring information from RefactoringMiner to refactoring APIs because the required refactoring information and refactoring APIs vary significantly among different categories of refactorings. Currently, we have customized the code snippet for eight most common refactorings, including rename classes, rename method, rename variables, rename fields, rename parameters, rename packages, extract methods, and extract variables. Such refactorings account for 72%=(284/397) of the refactorings discovered in the bug-fixing commits in Defects4J.

For a given intermediate version $V_{n-1}^{\prime}$ and the bug-fixing version $V_{n}$, the proposed approach generates all possible patches. To this end, it computes the difference between $V_{n-1}^{\prime}$ and $V_{n}$ (excluding their differences in test cases). The difference is represented as a sequence of token-level changes (e.g., removing or inserting a token), noted as $Chgs=<chg_{1},chg_{2},\dots,chg_{k}>$. Each of the token-level changes is composed of three parts: position, token, and edition type. Edition type is either remove or insert.

The proposed approach enumerates all subsequences of $Chgs$. Each subsequence $schg\subseteq Chgs$ represents a potential patch that makes all of the token-level changes in $schg$ on $V_{n-1}^{\prime}$, and ignores other changes in $Chgs$. To reduce the number of potential patches, we also introduce coarse-grained changes: line-level changes. If a whole line of source code has been removed from $V_{n-1}^{\prime}$, we represent it as a line-level change instead of a sequence of token-level changes. Insertion of a new line of source code is handled in the same way as a line-level change. Consequently, a potential patch is finally represented as a sequence of token-level and/or line-level changes.

The validation of a potential patch $pt$ is conducted in two phases. In the first phase, the proposed approach applies this potential patch to the intermediate version $V_{n-1}^{\prime}$, resulting in a new version $V_{n-1}^{\prime\prime}$. If $V_{n-1}^{\prime\prime}$ could not compile successfully, the potential patch is discarded as an illegal patch and its validation terminates. In the second phase, $V_{n-1}^{\prime\prime}$ is further validated with test cases associated with the faulty version (noted as $T_{n-1}$) and those associated with the fixed version (noted as $T_{n}$) as follows:

• •

  If any test case in $T_{n-1}$ fails on $V_{n-1}^{\prime\prime}$, $pt$ is not a valid patch and its validation terminates;

• •

  The proposed approach collects all test cases in $T_{n}$ that fail on $V_{n-1}$, and notes such test cases as potential triggering test cases that may expose the associated bug;

• •

  $pt$ is a candidate patch if $V_{n-1}^{\prime\prime}$ passes at least one potential triggering test cases. Otherwise, $pt$ is not a valid patch and its validation terminates.

If and only if the proposed approach generates exactly a single candidate patch from a bug-fixing code commit, the approach recommends the candidate patch for the associated bug report. Otherwise, no patch would be recommended.

In this section, we evaluate the proposed approach by investigating the following research questions:

• •

  RQ1: How often do bug fixing commits contain bug-irrelevant changes and what percentage of the changes in bug-fixing commits are bug-irreverent?

• •

  RQ2: Is BugBuilder accurate in extracting complete and concise bugs/patches? What percentage of real bugs/patches could be extracted accurately by BugBuilder?

• •

  RQ3: To what extent does the refactoring detection and replication affect the precision and recall of BugBuilder?

• •

  RQ4: Is BugBuilder scalable?

Our evaluation is based on the raw data in Defects4J. Defects4J contains 835 real bugs collected from real-world applications. For each bug, it provides the bug-fixing code commit, the versions immediately following/preceding the bug-fixing commit (called $V_{n}$ and $V_{n-1}$, respectively), and the manually confirmed patch for the bug. $V_{n}$ and $V_{n-1}$ are taken from version control history by Defects4J without any modification. $V_{n-1}$ is different from the faulty version ($V_{bug}$) provided by Defects4J because $V_{bug}$ is manually constructed to exclude refactorings and feature modifications whereas $V_{n-1}$ is an exact copy from the version control history.

Notably, only $V_{n}$ and $V_{n-1}$ are leveraged as the input of BugBuilder, whereas the manually constructed patches provided by Defects4J are leveraged only to assess the performance of BugBuilder, i.e., whether the automatically generated patches are identical to the manually constructed ones. Defects4J contains 835 bug-fixing commits from 17 projects. However, we failed to retrieve the $V_{n-1}$ version for project Chart because the version IDs for this project are invalid. Consequently, this project was excluded from our evaluation. As a result, the evaluation was conducted on 809 bug-fixing commits from 16 projects.

Other bug-patch datasets, like iBUGS and ManyBugs, are not leveraged for the evaluation because they do not exclude bug-irrelevant changes from the final bug-fixing patches.

The primary threat to external validity is the limited number of involved bug-fixing commits. In the evaluation, we evaluated BugBuilder on 809 bug-fixing commits collected by Defects4J. Special characteristics of such commits may bias the conclusions of the evaluation. We selected such commits for evaluation because Defects4J provides manually constructed concise patches that exclude bug-irrelevant changes. As a result, we can leverage such patches as the ground truth to evaluate the quality of automatically generated patches. To the best of our knowledge, Defects4J is the only bug repository that provides manually constructed concise patches for real bugs in open-source applications, and thus the evaluation was confined to the bug-fixing commits in Defects4J. However, to reduce the threat, we should evaluate BugBuilder on more bug-fixing commits in the future.

A threat to construct validity is that the manual checking of the generated patches (and patches in Defects4J) could be inaccurate. During the evaluation, we manually checked the generated patches and their corresponding patches in Defects4J when they did not match each other. Such manual checking could be biased and inaccurate. To reduce the threat, we presented typical examples in Section V-D2, and made all of the generated patches publicly available at [28].

Another threat to construct validity is that the evaluation is based on the assumption that matched patches are complete and concise. If an automatically generated patch is identical to the manually constructed patch (in Defects4J) for the same commit, we simply assumed that they are complete and concise. However, as discussed in Section V-D2, human experts may also make incorrect (especially incomplete) patches occasionally, and thus the assumption may not always hold.

A bug-fixing commit may contain three categories of changes: Bug-fixing changes, refactorings, and functionality-related changes (e.g., implementation of new features). BugBuilder can generate patches for pure bug-fixing commits (without any bug-irrelevant changes) with the potential patch generation (Section IV-C) and validation (Section IV-D). If a bug-fixing commit contains both bug-fixing changes and refactorings, BugBuilder leverages the Refactoring Detection and Reapplication (RDR for short) to turn the commit into a pure bug-fixing commit, and then generates patches from it. Notably, 24%=192/809 of the bug-fixing commits in Defects4J contain refactorings, which quantitatively suggests the importance of RDR (Section IV-B). RDR has the potential to rescue such commits. However, because the current implementation of BugBuilder supports only eight categories of refactorings, which prevents RDR from reaching its maximal potential: It improved recall by 11% only in the evaluation.

Another significant benefit of RDR is the significant improvement on the BugBuilder’s efficiency. Excluding refactorings significantly reduces the size of commits, and thus reduces the number of potential patches. Evaluation results in Section V-D4 suggest that disabling RDR increased BugBuilder’s run time by 24% on refactoring-contained commits.

High precision (99%) of BugBuilder is critical for the success of its future application. We expect it to build high-quality bug repositories without any human intervention, and thus the generated patches should be comparable to manually constructed ones. Otherwise, the resulting bug repositories could be misleading and may bias research and evaluation depending on them. Evaluation results in Section V confirm that the automatically generated patches are comparable to (and sometimes better than) patches manually constructed by human experts. In contrast, a fairish recall (40%) is acceptable because it could be remedied by applying BugBuilder to massive bug-fixing commits outside Defects4J.

BugBuilder succeeds on a substantial part (40%) of the bug-fixing commits, but fails on around 60% of the commits as well. BugBuilder works on a bug-fixing commit only if 1) the commit is composed of bug-fixing changes only or 2) the commit is composed of only bug-fixing changes and refactorings. Notably, if the refactorings within the commit are only applicable after the bug-fixing changes, existing refactoring mining tools like RefactoringMiner [34] cannot identify such refactorings by comparing the bug-fixed version ($v_{n}$) and the original buggy version ($v_{n-1}$). For example, if developers insert a fragment of source code to fix a bug, and then apply extract method refactoring to extract the inserted source code as a new method, RefactoringMiner cannot identify the extract method refactoring because the extracted source code is not available in the original buggy version. As a result, BugBuilder would fail to split the commit accurately into a refactoring patch and a following bug-fixing patch. If the refactorings are required by the bug fix (and thus applied before the fix) or independent of the fix (and thus could be applied before the fix), BugBuilder has the potential to split the bug-fixing commit into a refactoring patch and its following bug-fixing patch. If the commit contains bug-irrelevant and non-refactoring changes (e.g., implementing new features), BugBuilder cannot work either. Take the bug-fixing commit in Fig. 4 as an example. Adding the functionality to print headers of CSVFormat is taken as a bug-fixing action there. However, it could be taken as an implementation of a new feature (printing herders of CSVFormat) as well if this functionality has not been specified in the original requirements. Consequently, it is challenging (even for human experts) to distinguish bug-fixing changes from other functionality-related changes without the help of requirements and bug reports. However, automatic and accurate comprehension of requirements and bug reports in plain texts remains challenging, let alone requirements are often unavailable. Most of the bug-fixing commits where BugBuilder failed contain functionality-related bug-irrelevant changes, and this is the major reason for the low recall of BugBuilder.

Although BugBuilder misses 60% of the bugs/patches, it enables automatic construction of large bug-patch repositories for the following reasons. First, BugBuilder is fully automated with extremely high precision. Second, BugBuilder is not biased by the types of bugs, but affected by only whether the fixes are mixed with other functionality-related changes. Finally, although Defects4J extracts bug-patches from only 17 projects, there are numerous open-source projects to be exploited. Applying BugBuilder to such projects automatically could significantly increase the capacity of bug-patch repositories, thus offsetting BugBuilder’s weakness (low recall).

In theory, BugBuilder should be able to generate complete and concise patches for all pure bug-fixing commits (without any bug-irrelevant changes). However, BugBuilder succeeded on only 281 out of the 400 pure bug-fixing commits (called pure commits for short) in Defects4J. The major reason for the failure is the setting of the maximal time slots: 71%=84/119 of the failed pure commits ran out of the maximal time slots. Increasing the time slots may improve the recall in the future. Another reason for the failure is the redundancy of some patches. For example, rejecting some changes (i.e., changes on Lines 11-12) of the Defects4J patch (publicly available at https://github.com/rjust/defects4j/blob/master/framework/projects/Lang/patches/52.src.patch, but not presented in the paper for space limitation) would not change the semantics of the program. Consequently, BugBuilder generated multiple candidate patches from it, and thus BugBuilder did not known which one should be recommended.

Improving the implementation of the proposed approach to support additional categories of refactorings may also significantly improve recall in future. Notably, 57%=109/192 of the refactoring-containing commits in Defects4J contain some refactorings unsupported by the current implementation. Consequently, supporting all such refactoring in future has the potential to double the effect of RDR (Refactoring Detection and Reapplication) that currently improves recall by 11%.