Predicting Next Changes at the Fine-Grained Level
Hiroaki Murakami, Keisuke Hotta, Yoshiki Higo, Shinji Kusumoto
Graduate School of Information Science and Technology, Osaka University, Japan{h-murakm, k-hotta, higo, kusumoto}@ist.osaka-u.ac.jp
Abstract—Changing source code is not an easy task. Developers occasionally change source code incorrectly. Such mistakes
entail additional cost in having to reedit the source code correctly, and repeated changes themselves can be a vulnerability
to software quality. We are conducting research into realizing
automated code changing as a countermeasure for human errors.
As the first step of this research, we propose a technique to predict
the types of program elements deleted and added in a next change
to Java methods. This technique is designed to support developers
in deciding how to change source code after they have identified
a method to be changed. We evaluated predictions using the
proposed technique with two thresholds, which are sizes of sourcecode changes. For predictions with the smaller threshold where
only a single type of program element was added or deleted, theaccuracy of the proposed technique was 74%–85%. However, forthe larger threshold, where 5 or fewer types of program elements
were added or deleted, the accuracy was 44%–48%.
Keywords—Fine-Grained Change Prediction, Automated Code
Evolution, Static Code Analysis

I.

I NTRODUCTION

Changing source code is the most costly activity in software maintenance [1], and it is not an easy task. Developers occasionally change source code incorrectly or forget
to change code fragments. Such mistakes require not only
additional human resources to reedit the code correctly, butalso they can degrade the software quality [2]. Consequently,
facilitating source code changes by introducing automatic
operations would be very beneficial.
A variety of techniques for facilitating source code changes
have been proposed. For example, there are some techniquesthat construct prediction models to predict those modules
having frequent changes [3], [4], [5]. Another technique istailored to interfaces, which are generally stable components
in software systems [6]. Tsantalis et al. proposed a techniqueto calculate the probability that each class will be changed ina future version [7]. By using these techniques, development
projects are able to spend human resources on predicted faultprone modules. For example, if we obtain fault-prone modules,
we can focus on reviewing them.
A hot research topic is identifying pairs or sets of modules
that need to be changed together [8], [9], [10], [11]. After
identifying the modules that need to be changed, developers
can use the available techniques to know which modules need
to be changed together. Such a support mechanism prevents
developers from forgetting to change code fragments in a giventask. Facilitating bug fixes is another particularly hot research
topic. Various techniques are available, such as prioritizing
open bugs for fixing [12], identifying code fragments that cause
specific bugs [13], and validating whether bug fixes have been
performed correctly [14].

Many approaches fix bugs automatically by generating
patches for bug fixes. Perkins et al. developed ClearView,
which analyzes a target program dynamically and generates
patches that satisfy invariants in the program [15]. Wei et al.
proposed a technique that generates patches that satisfy not
only invariants but also preconditions and postconditions [16].
Because Wei’s technique uses preconditions and postconditions, it is able to fix more bugs than can Perkin’s technique.
However, to be analyzed by Wei’s technique, programs musthave descriptions of invariants, preconditions, and postconditions in their source files. In Perkin’s technique, invariants
are automatically identified by using the tool Daikon [17];thus, programs do not need to have descriptions of invariantsin their source files. Jin et al. proposed a technique to fix
bugs that violate the atomicity of parallel procedures [18].
Weimer et al. developed a tool called GenProg that uses
genetic programming to generate patches for fixing bugs [19],[20] and reported that GenProg was able to fix 55 out of 105
bugs automatically [21]. Source code changes are performed
not only to fix bugs but also to add new functionalities andchange/enhance existing functions. Of course, we need to take
into account the requirements for changing/enhancing existing
functions. On the other hand, historical approaches to guess thenext change seem promising because “programs that people
write are mostly simple and somewhat repetitive” [22].
In this research, we first investigated the size of sourcecode changes during software evolution. As a result, we foundthat most of the changes are small and simple. Then, wedeveloped a new technique to predict how a given method
will be modified in the next change. Our technique canpredict any size of changes in source code, but it works
particularly well for small changes. Our technique is beneficial
to individual developers when he/she needs to change sourcecode to complete a given task. Our technique facilitates sourcecode changes by showing (predicting) program elements thatwill be added or deleted in the next version. If the predictedsource code satisfies his/her requirements, he/she can obtain apatch to change the current source code in the next version.
By using the proposed technique,••developers do not need to consider how to change codefragments, andthey do not need to change source code manually.
This paper makes the following contributions.

••

We propose a novel technique that predicts the nextchanges. Currently, our technique predicts the types ofprogram elements that will be added and deleted in thenext change.
We evaluate our technique by conducting an experimenton two open-source software systems. In the experiment,
predictions are performed with two thresholds, which arepublic int min() {if (x <= y) {return x;} else {return y;}}

the size of the source code changes. The smaller threshold is intended to evaluate predictions where sourcecode changes are very small. That is, only a single typeof program elements is added or deleted. The larger
threshold is intended to evaluate predictions where one
program statement is added, deleted, or changed. The
accuracies of the two predictions are 74%–85% and44%–48%, respectively.
The remainder of this paper is organized as follows:
Section II introduces related work and discusses the differences
between them and our technique. Section III provides an
overview of our technique, and Section IV describes how tobuild prediction models. Section V shows how to implement
our technique. Section VI reports the experiment and the experimental result in detail. Section VII discusses the experimental
result by using examples of source code. We present our final
goal and paths to the goal in Section VIII. Section IX describes
the threats to validity. Section X concludes the paper and states
future work.
II.

R ELATED W ORK

A number of approaches use source code metrics to train
prediction models that can lead developers to the change-prone
and fault-prone modules in a software system [3], [4], [5],[6]. Although the experimental results of these approaches arepromising, they do not provide insights into the details of thechanges.
Giger et al. explored prediction models for determining
whether a source file will be affected by certain types ofchanges, such as condition changes, interface modifications,inserts or deletions of methods and attributes, or other kindsof statement changes [23]. Their models output a list of potentially change-prone files ranked according to their changeproneness overall and their change type category. The purposeof their research and ours is the same, which is to provide
insights into details of the changes. However, the methods
used for gaining such insights are different. Giger’s approach
predicts the category of code changes, whereas our current
approach predicts the types of program elements that aredeleted and added.
Goues et al. proposed a technique to repair programs
automatically [19], [20]. Their tool, GenProg, uses genetic
programming to repair a wide range of defect types in C
software (e.g., infinite loops, buffer overflows, segmentation
faults, and integer overflows). GenProg searches for a repair
method that retains the required functionality by generating
variant versions of the program through computational analogsof biological processes. They succeeded in creating a repaired
version of the source code itself. Kim et al. also proposed
learning to fix patterns from human-written patches to improve
the quality of generated patches, because GenProg sometimes
generates nonsensical patches due to the randomness of its
mutation operations [24]. Their techniques are tailored to
repairing bugs. It is difficult to apply their technique to otherkinds of changes, such as adding functionalities or enhancing
functions, because it requires test cases that a given bug passes
and fails. On the other hand, the target of our approach is not
only bug fixes but any kinds of changes in source code, suchas functional addition/enhancement or refactoring.

(a) Source CodeMETHOD_DECLARATIONPRIMITIVE_TYPE

MODIFIERSIMPLE_NAME

BLOCK
IF_STATEMENTINFIX_EXPRESSIONSIMPLE_NAMESIMPLE_NAME

BLOCK

BLOCK

RETURN_STATEMENTRETURN_STATEMENTSIMPLE_NAMESIMPLE_NAME(b) ASTx 80

0 , ... 3 , ... 1 , ... 1 , ... 1 , ... 2 , ... 2 , ... 5 , ... 1 , ... 0
BLOCK

INFIX_EXPRESSION

IF_STATEMENT

Fig. 1.

PRIMITIVE_TYPE

METHOD_DECLARATIONSIMPLE_NAME

RETURN_STATEMENTMODIFIER(c) PE-Vector
Example of a PE-Vector

Gethers et al. proposed a technique to enhance impact
analysis by combining information retrieval, dynamic analysis
and mining software repositories techniques [25], [26]. Theirtechnique identified a set of methods that should be fixed inorder to achieve the given change request (e.g., a bug report).
They showed that their technique provided an improved accuracy over the previously approaches.
III.

OVERVIEW OF O UR T ECHNIQUE

This paper proposes a technique to predict how to change
a given Java method at the program element level. As an
example, it tells us “one if statement, two identifiers, andone assign expression will be added by the next change.” Itlearns past changes from a historical code repository and builds
prediction models. Users of the proposed technique input aJava method that needs a change. The proposed techniquethen predicts the next change on the given method with theprediction models. This section introduces terms that are usedin this paper, followed by an overview of the procedure of the
proposed technique.
A. Terms
Program Element: This paper uses the nodes of an abstract
syntax tree (AST) as program elements. Each type of node istreated as a type of program element. We borrow the definitionsof AST nodes from Java Development Tools (JDT). JDTprovides us with a function to build ASTs from given Javasource files and defines 83 types of AST nodes, including
three related to comments1 . We use 80 types of program
elements because we are not interested in comments. This
paper uses symbols A0 , · · · , A79 to represent the different
types of program element.
1 The types of AST nodes in JDT and this study are defined in the classorg.eclipse.jdt.core.dom.ASTNode. A list of nodes is provided
in the Eclipse documentation. The current status is available from “http://help.
eclipse.org/kepler/index.jsp.” Note that the types of AST nodes might change
due to an update of Java or JDT.

Training Set(0, 2, 1, ... , 5, 0, 1)(0, 3, 1, ... , 4, 0, 0)(3, 0, 0, ... , 0, 2, 2)(6, 0, 1, ... , 0, 1, 1)...

Building the training set

Repository
Building the models
Building the models

Prediction result
1st stagesmall(4, 3, 1, ... , 3, 0, 0)
2nd stage(2, 2, 1, ... , 4, 0, 1)
Prediction target

Fig. 2.

The next change
will be ...

large

unpredictable

Flow ofthe proposed technique
Flow of the prediction

Overview of Proposed Technique

PE-Vector: The proposed technique treats each method asa vector named a Program Element Vector (PE-Vector). A PEVector is a numerical vector that has 80 dimensions, and eachelement of a PE-Vector represents the number of each program
element in the method. This paper describes the PE-Vector of amethod m as v⃗m = (x0 , · · · , x79 ). Here, xi in v⃗m denotes thenumber of the program elements Ai in the method m. Figure 1
shows an example of a PE-Vector. Figure 1(b) shows an AST
for the method shown in Fig. 1(a), and the vector shown in
Fig. 1(c) is the PE-Vector created from the method. The vector
has 80 dimensions; however, due to the space limitation, we
omitted the attributes from the figures whose value is 0, except
for the head and the tail of the vector.
B. Overview of the Procedure
Figure 2 provides an overview of the procedure of the
proposed technique and a prediction made by using it. As thefirst step in the prediction, the technique generates a training
set from a given historical code repository. The training set
has information about past changes in the historical repository.
Each element of the training set is a pair of PE-Vectors vm
and vm′ , where m was changed to m′ . Note that the PEVectors before and after a change might be the same vector.
This means that the change did not alter the numbers of any
program elements. For example, this case occurs when thechange is the renaming of local variables. With the training
set, the proposed technique builds the prediction models. The
models tell us what kind of change will occur next in a given
method. The proposed technique adopts a two-stage prediction,
as described below.
Prediction for Filtering: the proposed technique predicts
whether the next change that a given method undergoes will
be small. This stage filters out methods that are predicted asundergoing large changes in their next revisions.
Prediction of Changes: the proposed technique predicts
the quantity of the next change in terms of AST nodes for agiven method. That is, the proposed technique predicts the next
PE-Vector of a given method m. For example, if we supposethat m becomes m′ in the next change, then the proposed
technique predicts v⃗m′ based on v⃗m . This stage targets only
methods that are predicted as undergoing small changes in thefirst-stage prediction.
The noteworthy point of the proposed technique is that it
excludes methods from prediction targets if they are predicted
as undergoing large changes in the next revision. The rationale
behind this filtering is that it is difficult to predict large changes
accurately. It is necessary for the proposed technique to makeprecise predictions for automated source code changes. The

proposed technique is the first step of automated source codechanges. Hence, the accuracy of a prediction made with theproposed technique is important for the final goal. That is, if
an incorrect prediction is made, this would lead to an incorrectchange. We believe that an incorrect change must be avoided
even though we will lose some candidates that might be able
to be changed automatically. Therefore, we decided to ignore
large changes currently by such filtering. However, we will
improve our technique to be able to predict large changes
correctly as a future task. The above leads to the question,“What is a small change?” This study considers a change
to be small if the number of types of program elementsthat were added/deleted by the change is less than a given
threshold. Suppose a method m is changed and becomes m′ ,and ⃗v = (x0 , . . . , x79 ) is a difference vector from m to m′′ − v⃗ ). The change to m is regarded as small if the(⃗v = v⃗mmfollowing condition holds; otherwise, it is regarded as large.
|changed (⃗v )| ≤ threshold

(1)

where
changed (⃗v ) = {i ∈ 0 . . . 79 | xi ̸= 0}(2)

We use the number of types of program elements instead ofcode churn, which is a common metric for measuring the sizeof a change. Code churn is unsuitable for this study becauseof the granularity of the prediction. The proposed techniqueestimates the number of additions/deletions of program elements. In other words, it can predict only the type of thenext change, not the content of the change. Specifically, theproposed technique can predict that “an if statement will be
added,” but it cannot tell the predicate and the body of theif statement. Code churn is measured based on the contentsof changes, e.g., the number of changed lines or tokens of achange. Therefore, it cannot be measured without the content
of a change. We believe that we should measure the size of achange by a feature we can predict. In this case, we use thetypes of changes instead of their contents.
As mentioned above, the PE-Vectors before and after achange might be the same vector. Hence, it is possible thatthe proposed technique reports the same PE-Vector of a given
method as a prediction result. Such a prediction result indicatesthat the method needs a change that does not change the number of program elements, such as the renaming of variables.
This result does not indicate that the method does not need anychanges. This is because the proposed technique assumes thatits users will input methods that should be changed. Predicting
whether a given method needs any changes is not within thescope of the proposed technique.
C. Restrictions
The proposed technique has the following restrictions.
•••

The target of prediction is limited to code inside Javamethods. Programming languages other than Java, orcode outside Java methods, are outside the scope of the
proposed technique.
The proposed technique cannot predict changes that are
simultaneously performed on multiple methods. It justpredicts the next version of each method.
The proposed technique cannot generate source code.
It just predicts the type of program elements that areadded/deleted in the next change.

Equation (3) states that the value of an attribute Ai is estimatedwith those of all the attributes A0 , . . . , A79 . However, weshould not use all the attributes as explanatory variables
because some of the attributes are correlated. Hence, we haveto select the variables to be used as explanatory variables
to avoid multicollinearity. Therefore, βj will have a nonzero
value if the attribute Aj is selected as an explanatory variable;
otherwise, βj is zero.

small change

large change
prediction target
k=1

k=3
k=5

Fig. 3.

The k-NN Algorithm

IV.

P REDICTION M ODELSThis section describes how to build prediction models byusing the training set. As mentioned above, the proposed
technique adopts a two-stage prediction. The first stage makes
predictions for excluding methods from the prediction target
if they will undergo large changes. The second stage predictsa PE-Vector of the method m′ that a given method m will become by the next change. The following subsections describe
each stage in detail.
A. Prediction for Filtering
The first-stage prediction uses the k-nearest neighbor (kNN) algorithm to predict if the next change in a method
will be small or large. This is a nonparametric algorithm
for classification and regression, and it is the simplest of themachine learning algorithms. We use this algorithm becauseof its high scalability. The k-NN algorithm makes a prediction
for a given object based on the majority vote by its k closest
objects in the training data in vector space. In our case, theobjects are PE-Vectors, and the distance between two objects
is measured by the Euclidean distance between the two PEVectors.
Figure 3 shows the k-NN algorithm. In the case of k = 1,
the algorithm chooses the nearest object to a given object fromthe training set. In the example in Fig. 3, the nearest object ismarked as small, and so the prediction result becomes small.
In the case of k = 3, the prediction result is decided basedon the majority vote by the 3 nearest objects. The prediction
result becomes small because there are 2 small changes and1 large change in the solid circle. The prediction in the caseof k = 5 is made in a similar way. In this case, the algorithm
regards the prediction target as large because the number ofsmall changes is less than that of large changes in the outmost
circle.
B. Prediction of Changes
The second-stage prediction uses linear regression analysis
to predict the next PE-Vector of a given PE-Vector. This stage
builds a regression function for each of the attributes in the PEVector. In other words, it makes predictions on each program
element independently. Hence, this stage generates the same
number of regression functions as the dimension number of
the PE-Vector, which is 80.
Let v⃗m = (x0 , · · · , x79 ) be the target of prediction, and′⃗vm = (y0 , · · · , y79 ) be a PE-Vector created by the prediction
for v⃗m . The proposed technique builds a regression function
for each of the attributes A0 , . . . , A79 . Equation (3) is the formof each regression function.
yi = β +

79
∑
j=0

βj xj

(3)

Note that each of the regression functions should havedifferent explanatory variables because they are built independently. In other words, it is possible that xj is used as an
explanatory variable in the regression function for yi but is
not used in the regression function for yk .
V.

I MPLEMENTATION

We have implemented the proposed technique with Javaand R2 . We assembled a tool to create a PE-Vector from thesource code of a given method and to construct a training set
from the given historical code repository in Java, while we
entrusted a static analysis to build prediction models to the Rfunctions.
To build training sets, it is necessary to detect which
methods were changed in each of the past commits and how
they were changed. We applied the clone tracking techniquedeveloped by our research group to this detection [27]. The
clone tracking technique was originally used to map code
clones between two consecutive revisions, but it can be used tomap methods between two consecutive revisions. It is basedon CRD [28], which is a text representation of the locationof a given code fragment. The clone mapping technique links
two code fragments between two consecutive revisions basedon the similarity of their CRDs, and makes links of code
clones between the two revisions based on the links of the codefragments. The technique can map clones well, even in the casewhere files having clones were moved or renamed because it
uses the similarity of CRDs, not their perfect matching. As in
the clone mapping technique, the proposed technique in thisstudy calculates CRDs from every method and makes links ofthe methods between two consecutive revisions based on thesimilarity of their CRDs.
We used the knn function of R to predict small changes,
and the lm function to perform the linear regression analysis.
In addition, we adopted the method of increasing and decreasing the variables of the step function to select explanatory
variables. The step function makes prediction models thathave the lowest Akaike information criterion (AIC), whichhelps to avoid the problems of overfitting and multicollinearity.
VI.

E XPERIMENTThe purpose of the experiment is to investigate to what
extent the proposed technique can correctly predict the numberof types of program elements in the next change. In thisexperiment, we use ArgoUML and Ant as the target softwaresystems. These systems are written in Java and managed by
Subversion. Table I shows the details of the systems. Thissection consists of the following two experiments.
2 http://www.r-project.org/

100%

Threshold90%

more than 8

80%

8

70%

7

60%

6

50%

(a) Deleting a null Argument from a Method Invocation

5

40%

4

30%

3

20%

2

10%

1

0%
Ant

Fig. 4.

public void actionPerformed(ActionEvent e) {System.out.println("making class...");_cmdCreateNode.doIt(null);+_cmdCreateNode.doIt();}

ArgoUML0

Rates of Small Changes

Investigation of small changes: first, we investigated how
many small changes account for all the changes in the target
software systems. If few small changes are used for building
the prediction models, the proposed technique does not work
well. Therefore, we report the rates of small changes against
all changes and introduce some examples of small changes.

(b) Adding Braces to All if Statements
Examples of Small Changes when Threshold is 1

Fig. 5.

public boolean predicate2(Object dm, Designer dsgr) {if (!(dm instanceof Classifier)) return NO_PROBLEM;...

Prediction of program elements: the proposed technique
predicts whether the next changes are small for the target
software systems. If the next changes are predicted as small,the proposed technique predicts the types and the number ofprogram elements in the next changes.

public void setOwner(Object node) {Object oldOwner = getOwner();- if (oldOwner != null && oldOwner instanceof GraphNodeHooks)+ if (oldOwner != null && oldOwner instanceof GraphNodeHooks) {((GraphNodeHooks)oldOwner).removePropertyChangeListener(this);+ }- if (oldOwner != null && oldOwner instanceof Highlightable)+ if (oldOwner != null && oldOwner instanceof Highlightable) {((Highlightable)oldOwner).removePropertyChangeListener(this);+ }- if (node instanceof GraphNodeHooks)+ if (node instanceof GraphNodeHooks) {((GraphNodeHooks)node).addPropertyChangeListener(this);+ }- else if (node instanceof Highlightable)+ else if (node instanceof Highlightable) {((Highlightable)node).addPropertyChangeListener(this);+ }super.setOwner(node);}if (Name.UNSPEC.equals(aeName)) continue;
String aeNameStr = aeName.getBody();if (aeNameStr.length() == 0) continue;
if (namesSeen.contains(aeNameStr)) return PROBLEM_FOUND;
namesSeen.addElement(aeNameStr);}+

A. Investigation of small changes
We calculated the rates of small changes against all changes
by using various thresholds in Equation (1). Figure 4 shows therates. As this figure shows, in the case of Ant, the percentage
of small changes is approximately 35% when the threshold
is 0 and approximately 39% when the threshold is 1. Whenthe threshold is 0, the number of AST nodes does not change.
Such changes include modifying variable names and reordering
statements. From Fig. 4, the percentages of small changes
exceed 50% when the threshold is 5. It is interesting thatthe number of small changes accounts for over half of allchanges when the threshold is 5. We think 1 is rather strict
as a threshold value. Suppose a statement is changed in amethod, then the change may affect about 5 types of program
elements. However, the prediction model ignores the change
if the threshold is 1. Hence, we decided to use 1 and 5 as
threshold values.
Figure 5 shows two examples of code changes when thenumber of types of changed AST nodes is 1. The examples
were obtained from ArgoUML. In the case of Fig. 5(a), a nullargument is deleted from a method invocation. In terms of
the AST, the change decreases the number of null literal
nodes. In Fig. 5(b), braces are added to all if statements,
which increases the number of block nodes in AST. Figure
6 shows two examples of code changes when the number oftypes of changed AST nodes is 5. Figure 6(a) shows a changethat adds an if statement. This change affects the numberof AST nodes of the continue statement, if statement,
method invocation, number literal, and method name. Figure6(b) shows another change that modifies a return statement
by uncommenting. It increases the number of five types of AST
TABLE I.
Name
Ant
ArgoUMLTARGET S OFTWARE S YSTEMS

Start revision (date)
267,549 (2000/01/13)
1 (1998/01/27)

End revision (date)
1,233,420 (2012/01/20)
19,893 (2012/07/10)# revisions
8,284
3,918

}
return NO_PROBLEM;}(a) Adding an if Statement
public boolean shouldBeEnabled() {ProjectBrowser pb = ProjectBrowser.TheInstance;
Project p = pb.getProject();
Object target = pb.getDetailsTarget();- return super.shouldBeEnabled() && p != null;- // && (target instanceof ModelElement);+ return super.shouldBeEnabled() && p != null &&+(target instanceof ModelElement);}

Fig. 6.

(b) Modifying a return Statement by Uncommenting
Examples of Small Changes when Threshold is 5

nodes: infix expression, instanceof operator, parenthesized
expression, variable name, and type name.
B. Prediction of program elements
In this subsection, we report two types of prediction results.
The first is a prediction of whether the next changes are small.
The second is a prediction of the types and the number ofprogram elements in the next change. Based on the prediction
results, we answer the following two research questions (RQs).
RQ1: how accurately does the proposed technique predictwhether the next change will be small? (Accuracy of the firststage prediction)
RQ2: how accurately does the proposed technique predict
the types and the number of program elements in the nextchanges? (Accuracy of the second-stage prediction)
In preparation for the experiment, the historical code repositories of each target software system were divided into 5 equalparts based on the number of revisions, which we named C1 ,C2 , C3 , C4 , and C5 . In the rest of this subsection, we describe
the steps of the experiment and report the prediction results.

AUC of the first-stage prediction

AUC of the first-stage prediction
PPR of the second-stage prediction

1

1

0.8

0.8

ValuesValuesPPR of the second-stage prediction

0.6
0.4
0.2

0.6
0.4
0.2

0

0
1

2

3

4

5

6

7

8

1

2

3

Thresholds

Fig. 7.

The ROC Curve Obtained from Ant(b) C3
AUC of the first-stage prediction

STEP1: small changes in the target software systems wereextracted from each Cn (1 ≤ n ≤ 4).
STEP2: the proposed technique built second-stage prediction models by using the small changes extracted in STEP1.
These changes occurred in C1 , . . . , Cn−1 (2 ≤ n ≤ 5) andwere used for building models, and the models predicted thenext changes that occurred in Cn .
STEP3: the predicted changes in Cn were compared withthe actual changes in Cn . This step yielded two values. The
first was the rate at which the changes were predicted correctly.
The second was the number of changes predicted correctly. As
n was either 2, 3, 4, or 5, we obtained four results from eachtarget software system.
In this evaluation, we defined P P R (Perfectly Predicted
Ratio). P P R is the ratio of perfectly predicted PE-Vectors
to all the PE-Vectors in each Cn . The perfectly predicted PETABLE II.

Predicted

R ELATIONSHIP AMONG P REDICTED AND ACTUAL VALUES
small
large

Actualsmall
large
True Positives (TP)
False Positives (FP)
False Negatives (FN)
True Negatives (TN)0.8

ValuesValues

0.8
0.6
0.4

0.6
0.4

0
1

2

3

4

5

6

7

8

1

2

3

Thresholds

4

5

6

7

8

Thresholds(c) C4
Prediction Results for Ant(d) C5

AUC of the first-stage prediction

AUC of the first-stage prediction

PPR of the second-stage prediction

PPR of the second-stage prediction

1

1

0.8

0.8

ValuesValues

8

0.2

0

0.6
0.4
0.2

0.6
0.4
0.2

0

0
1

2

3

4

5

6

7

8

1

2

3

Thresholds

4

5

6

7

8

Thresholds(a) C2(b) C3

AUC of the first-stage prediction

AUC of the first-stage prediction

PPR of the second-stage prediction

PPR of the second-stage prediction
1

0.8

0.8

Values

1

0.6
0.4
0.2

0.6

0.4
0.2

0

0
1

2

3

4

5

6

7

8

Thresholds

Fig. 9.

7

PPR of the second-stage prediction
1

0.2

Values2) Prediction of the types and the number of program
elements in the next change: the proposed technique built
second-stage prediction models for predicting the types andthe number of program elements in the next change. In thisexperiment, a predicted change is regarded as correct when
the number of each program element in the predicted change
is equal to the actual change. This prediction was conductedaccording to the following steps.

6(a) C2

1

Fig. 8.

5

AUC of the first-stage prediction
PPR of the second-stage prediction

1) Prediction whether the next changes are small: theproposed technique built first-stage prediction models for predicting whether the next changes are small. The models werebuilt by the training sets C1 , . . . , Cn−1 (2 ≤ n ≤ 5). Then, themodels predicted whether the changes in Cn would be small.
We evaluated the accuracies of the prediction results yieldedfrom the k-NN algorithm by using three k values (k = 1, 3, 5).
However, the results were almost the same. Therefore, we use
k = 1 in this experiment because the k-NN algorithm using
k = 1 can produce results in the shortest time. The outputof the k-NN algorithm was classified into four categories, as
shown in Table II. We obtained a ROC (Receiver Operating
Characteristic) curves from the classification results. The ROC
curve is created by plotting the fraction of true positives out of
the total actual positives (true positive rate) and the fraction offalse positives out of the total actual negatives (false positiverate). Figure 7 shows the ROC curve obtained from Ant inC2 . Moreover, we obtained an AU C (Area Under the Curve)
from the ROC curve. AU C is a commonly used evaluation
scale for binary prediction models.

4

Thresholds(c) C4
Prediction Results for ArgoUML

1

2

3

4

5

6

7

8

Thresholds(d) C5Vectors represent PE-Vectors whose predicted number of typesof program elements is equal to the actual ones in the nextchange. We consider that P P Rs are the performances of thesecond-stage prediction models.
3) Experimental Results: Figures 8 and 9 show AU Cs
and P P Rs for the target software systems. In each graph,the solid lines represent AU Cs and the dashed lines represent
P P Rs. From these graphs, we found that AU Cs change little
as the threshold increases and P P Rs decrease as the thresholdincreases. Specifically, when the threshold is 1, AU C varies
from 89% to 94% for Ant and from 92% to 94% for ArgoUML.
P P R varies from 83% to 90% for Ant and from 92% to
94% for ArgoUML. When the threshold is 5, AU C results
are 87%–92% for Ant and 91%–94% for ArgoUML. P P R
results are 55%–62% for Ant and 48%–58% for ArgoUML.
The product of AU C and P P R is regarded as the performanceof the whole prediction model. Thus, the performance of theprediction model for Ant is 74% (= 89% × 83%), and that for
ArgoUML is 85% (= 92% × 92%) when the threshold is 1.
When the threshold is 5, these percentages are 48% for Ant
and 44% for ArgoUML. Based on the experimental results, weanswer the research questions as follows.

public void testSendReceiveStartNotifyTyping() throws IOException {sess1.sendTypingNotification(OTHERUSR, true);...

assertTrue(sne.isTyping());
assertTrue(sne.getMode()==1);
assertTrue(sne.isOn());
sess1.sendMessage(OTHERUSR, CHATMESSAGE,sess1.getLoginIdentity());+...

assertEquals(event.getEvent().getMessage(), CHATMESSAGE);}

Fig. 10.

+++Prediction Successpublic void testDuplicateLogins() throws Exception {Thread.sleep(500);
final Session<RosterV1> sessionOne = createSession();final Session<RosterV1> sessionTwo = createSession();final Session<T, U> sessionOne = createSession();final Session<T, U> sessionTwo = createSession();assertEquals(SessionState.UNSTARTED, sessionOne.getSessionStatus());

because the change from a large number to another large
number (e.g., from 53 to 57) seldom occurs and the proposed
technique cannot build correct models. In the experiment, wefound that SIMPLE_NAME is the primary cause of prediction
failure. To increase the accuracy of the prediction models, weneed to tackle the problem of SIMPLE_NAME. Currently, we
consider one solution, which is using the AST that treats thevariable name or the method name as separate nodes. The AST
provided by JDT treats the variable name or method name as
the same node, SIMPLE_NAME. If we use the enhanced AST,
the number of SIMPLE_NAME occurrences in the next change
could be predicted correctly.
VIII.

...
assertEquals(SessionState.UNSTARTED, sessionTwo.getSessionStatus());}

Fig. 11.

Prediction Failure

RQ1: the proposed technique predicts whether the nextchange will be small with 89%–94% as AU C for Ant and
92%–94% for ArgoUML when the threshold is 1. When thethreshold is 5, these percentages are 87%–92% for Ant and
91%–94% for ArgoUML.
RQ2: the proposed technique predicts the number ofprogram elements in the next change, with 83%–90% as P P R
for Ant and 92%–94% for ArgoUML when the threshold is 1.
When the threshold is 5, these percentages are 55%–62% for
Ant and 48%–58% for ArgoUML.
VII.

D ISCUSSION

In this section, we discuss two prediction results. One issuccess, and the other is failure.
A. Case of SuccessFigure 10 shows the success case. In this case, the numberof infix expressions changes from 1 to 0, and the numberof number literals changes from 3 to 2. In the training set,a change in the number of infix expressions from 1 to 0
occurred twice, and that of the number of number literals
from 3 to 2 occurred 62 times. However, these changes did
not occur at the same time in the training set. Thus, existing
techniques using a fix pattern (e.g., [24]) cannot find this case.
The reason the proposed technique could find this case is thatthe prediction models were built by learning the changes ofeach of the program elements. This is the largest advantage ofthe proposed technique.
B. Case of Failure
Figure 11 shows the failure case. In this case, thenumber of SIMPLE_NAME nodes changes from 53 to 57.
SIMPLE_NAME represents a user-defined name (e.g., variablename or method name). The added SIMPLE_NAME occurrences are “Thread”, “sleep”, and two “U”. However, suchchanges did not occur in the training set. Therefore, themodel predicted the number of SIMPLE_NAME as 56 and not
as 57. The proposed technique occasionally cannot correctly
detect the next change in a large method. A large method
has many occurrences of SIMPLE_NAME. Predicting correctly
the number of many SIMPLE_NAME occurrences is difficult

O UR GOAL

Our final goal is the realization of automated code changes.
However, at this time, we only achieved predicting the numberof added/deleted AST nodes in the next change. To achieve automated code changes, we have to tackle following problems,(1) where the change should be made and (2) what actual
code is added, deleted and modified. In order to resolve these
problems, we have to expand the proposed technique. For example, we will predict the locations of program elements in thenext change by using a rich PE-Vector that contains locational
information. Moreover, we will convert some elements of the
PE-Vector into an actual code (e.g. if one IF_STATEMENT,
one SIMPLE_NAME and one BLOCK are added, the following
code would be created).
if (var) {}Another solution is applying the idea of the proposed technique
for the existing method. GenProg uses genetic algorithm
to randomly generate bug patches. If it is found that whatkinds of program elements are likely changed by the proposed
technique, the genetic algorithm can focus more program
elements than random generations.
IX.

T HREATS TO VALIDITY

In this section, we describe some threats to validities.
A. Target Software Systems
In this experiment, each of the target repositories was
divided into 5 equal parts based on the number of revisions.
However, if the repositories are divided in different ways (e.g.,based on the version upgrade date or development periods) or
if the number of divided repositories is different from that inthis experiment, we might obtain different results. Moreover,
we used only two software systems for the experiment. Whenother software systems are used, the proposed technique may
yield different results from that reported in the experiment. In
order to get rid of the threat, we have to evaluate the proposed
technique with more than two software systems.
B. Building Models
In this experiment, only the small changes (threshold is 1
or 5) were used for the training set. If the threshold is changed,
different results will be obtained. If the threshold is decreased,a stricter prediction is conducted. However, the number ofmethods that are targets for prediction would be decreased.
Conversely, if the threshold is increased, the number of methods that are targets for prediction are increased; however, theaccuracy of the prediction models would decrease due to largechanges included in the training set.

[3]

[4]

C. Large Changes
The proposed technique classified all changes into smallchanges or large changes. Then, we used only small changes
for this experiment. In other words, we ignored large changes.
The reason is that we consider that small changes makeprediction models more reliable than do large changes. To
achieve a perfect prediction, large changes should not beignored. Prediction using large changes is our future work.

[5]

[6]
[7]

D. Types of Changes[8]

The proposed technique did not consider a context or arequirement of the change. For example, if a change causes
bugs, the proposed technique uses the change for building
the prediction models because the proposed technique did notconsider the context of the change. In that case, the proposed
technique has a risk of predicting the change that causes
bugs. Furthermore, the proposed technique did not consider
a contributor. In the case of predicting the same or similarchange as in the past, if the contributor of the past change andthat of the present change are same, the prediction models arelikely to have high accuracies. On the other hand, if the present
contributor is different from the one of the past change, theprediction may result in failure. Therefore, it is difficult forthe proposed technique to predict the change in the softwaresystems that many people develop within a certain amount oftime. One of the solution for the problem is that the proposed
technique builds prediction models by using only the changes
that the contributor of the changes and the user of the proposed
technique are same.

[9]
[10]

[11]
[12]
[13]

[14]
[15]

[16]

[17]

X.

C ONCLUSIONSIn this paper, we proposed a technique to predict the nextchange in source code. While existing techniques concentrateon changes for fixing bugs, our technique handles all kindsof changes. As an evaluation of the proposed technique, we
conducted an experiment on two open source software systems.
We performed predictions by the proposed technique with two
thresholds in this experiment: one was predicting only verysmall changes, where only a single type of program element
was added or deleted in the next change; the other was intended
to predict changes where 1 program statement was added,
deleted, or changed. The accuracies of the predictions were
74%–85% and 44%–48%, respectively. As the next step inthis research, we are planning to predict (generate) the sourcecode of the next version.

[18]
[19]

[20]

[21]

[22]
[23]
[24]

ACKNOWLEDGMENT
This work was supported by JSPS KAKENHI Grant Numbers 25220003, 24650011, and 24680002.

[25]

[26]

R EFERENCES
[1]

[2]

R. C. Seacord, D. Plakosh, and G. A. Lewis, Modernizing Legacy
Systems: Software Technologies, Engineering Process and Business
Practices. Addison-Wesley Longman Publishing Co., Inc., 2003.
N. Nagappan, A. Zeller, T. Zimmermann, K. Herzig, and B. Murphy,“Change Bursts As Defect Predictors,” in ISSRE’10, pp. 309–318.

[27]
[28]

E. Arisholm, L. C. Briand, and A. Foyen, “Dynamic Coupling Measurement for Object-Oriented Software,” TSE, vol. 30, no. 8, pp. 491–506,
2004.
M. Dagpinar and J. H. Jahnke, “Predicting Maintainability with ObjectOriented Metrics - An Empirical Comparison,” in WCRE’03, pp. 155–
164.
W. Li and S. Henry, “Object-oriented Metrics That Predict Maintainability,” Journal of Systems and Software, vol. 23, no. 2, pp. 111–122,
1993.
D. Romano and M. Pinzger, “Using Source Code Metrics to Predict
Change-prone Java Interfaces,” in ICSM’11, pp. 303–312.
N. Tsantalis, A. Chatzigeorgiou, and G. Stephanides, “Predicting theProbability of Change in Object-Oriented Systems,” TSE, vol. 31, no. 7,
pp. 601–614, 2005.
H. Kagdi, “Improving Change Prediction with Fine-grained Source
Code Mining,” in ASE’07, pp. 559–562.
R. Robbes, D. Pollet, and M. Lanza, “Logical Coupling Based on FineGrained Change Information,” in WCRE’08, pp. 42–46.
A. T. T. Ying, G. C. Murphy, R. Ng, and M. C. Chu-Carroll, “Predicting
Source Code Changes by Mining Change History,” TSE, vol. 30, no. 9,
pp. 574–586, 2004.
T. Zimmermann, P. Weisgerber, S. Diehl, and A. Zeller, “Mining Version
Histories to Guide Software Changes,” in ICSE’04, pp. 563–572.
J. Anvik, L. Hiew, and G. C. Murphy, “Who Should Fix This Bug?” in
ICSE’06, pp. 361–370.
D. Saha, M. G. Nanda, P. Dhoolia, V. K. Nandivada, V. Sinha, and
S. Chandra, “Fault Localization for Data-centric Programs,” in FSE’11,
pp. 157–167.
Z. Yin, D. Yuan, Y. Zhou, S. Pasupathy, and L. Bairavasundaram, “HowDo Fixes Become Bugs?” in FSE’11, pp. 26–36.
J. H. Perkins, S. Kim, S. Larsen, S. Amarasinghe, J. Bachrach,
M. Carbin, C. Pacheco, F. Sherwood, S. Sidiroglou, G. Sullivan, W.-F.
Wong, Y. Zibin, M. D. Ernst, and M. Rinard, “Automatically Patching
Errors in Deployed Software,” in SOSP’09, pp. 87–102.
Y. Wei, Y. Pei, C. A. Furia, L. S. Silva, S. Buchholz, B. Meyer, and
A. Zeller, “Automated Fixing of Programs with Contracts,” in ISSTA’10,
pp. 61–72.
M. D. Ernst, J. H. Perkins, P. J. Guo, S. McCamant, C. Pacheco, M. S.
Tschantz, and C. Xiao, “The Daikon System for Dynamic Detection of
Likely Invariants,” Science of Computer Programming, vol. 69, no. 1-3,
pp. 35–45, 2007.
G. Jin, L. Song, W. Zhang, S. Lu, and B. Liblit, “Automated Atomicityviolation Fixing,” in PLDI’11, pp. 389–400.
C. Le Goues, T. Nguyen, S. Forrest, and W. Weimer, “GenProg: A
Generic Method for Automatic Software Repair,” TSE, vol. 38, no. 1,
pp. 54–72, 2012.
W. Weimer, T. Nguyen, C. Le Goues, and S. Forrest, “AutomaticallyFinding Patches Using Genetic Programming,” in ICSE’09, pp. 364–
374.
C. Le Goues, M. Dewey-Vogt, S. Forrest, and W. Weimer, “A Systematic Study of Automated Program Repair: Fixing 55 out of 105 Bugs
for $8 Each,” in ICSE’12, pp. 3–13.
A. Hindle, E. T. Barr, Z. Su, M. Gabel, and P. Devanbu, “On the
Naturalness of Software,” in ICSE’12, pp. 837–847.
E. Giger, M. Pinzger, and H. C. Gall, “Can We Predict Types of CodeChanges? An Empirical Analysis,” in MSR’12, pp. 217–226.
D. Kim, J. Nam, J. Song, and S. Kim, “Automatic patch generation
learned from human-written patches,” in ICSE’13, pp. 802–811.
M. Gethers, H. H. Kagdi, B. Dit, and D. Poshyvanyk, “An adaptive
approach to impact analysis from change requests to source code,” inASE’11, pp. 540–543.
M. Gethers, B. Dit, H. H. Kagdi, and D. Poshyvanyk, “Integrated impact
analysis for managing software changes,” in ICSE’12, pp. 430–440.
Y. Higo, K. Hotta, and S. Kusumoto, “Enhancement of CRD-based
Clone Tracking,” in IWPSE’13, pp. 28–37.
E. Duala-Ekoko and M. P. Robillard, “Clone Region Descriptors:
Representing and Tracking Duplication in Source Code,” TOSEM,
vol. 20, no. 1, pp. 3:1–3:31, 2010.