Graph-Based Approach for Detecting Impure Refactoringfrom Version Commits
Shogo Tsutsumi† , Eunjong Choi‡ , Norihiro Yoshida∗ , and Katsuro Inoue††‡

Graduate School of Information Science and Technology, Osaka University, Japan
Graduate School of Information Science, Nara Institute of Science and Technology, Japan∗
Graduate School of Information Science, Nagoya University, Japan†{s-tutumi,inoue}@ist.osaka-u.ac.jp, ‡ choi@is.naist.ac.jp, ∗ yoshida@ertl.jp

ABSTRACTpublic TarEntry(File file) {this();
this.file = file;
String fileName = file.getPath();…
this.linkName = new StringBuffer(“”);
this.name = new StringBuffer(fileName);…
if (file.isDirectory()) {this.mode = DEFAULT_DIR_MODE;
this.linkFlag = LF_DIR;

Impure refactoring is defined as a refactoring operation thatwas saved together with non-refactoring changes or several
refactoring operations were saved at the same location storedin source code repositories. Many of existing approaches are
not correctly viable for detecting impure refactoring. To
mitigate this problem, we propose an approach that detects
impure refactoring from commits stored in the repositories
using a graph search algorithm. In case study, we applied
our approach to two actual classes in Apache Xerces projectand confirmed the feasibility of the approach.

if (this.name.charAt(this.name.length() - 1) != ‘/’) {this.name.append(“/”);}} else {…
}…

CCS Concepts(a) Previous commit(755230)•Software and its engineering → Maintaining software;

public TarEntry(File file) {this();
this.file = file;
String fileName = normalizeFileName(file.getPath());
this.linkName = new StringBuffer(“”);
this.name = new StringBuffer(fileName);if (file.isDirectory()) {this.mode = DEFAULT_DIR_MODE;
this.linkFlag = LF_DIR;
int nameLength = name.length();if (nameLength == 0 || name.charAt(nameLength - 1) != ‘/’){this.name.append(“/”);}} else {…
}…
}…
private static String normalizeFileName(String fileName) {…

Keywords
impure refactoring; graph search; refactoring detection

1.

INTRODUCTION

Refactoring histories provide insights to not only practitioners but also researchers. In particular, there is anincreasing interest in the relationship between refactoring
operations and source code quality [1, 11]. So far, a number of approaches that detect refactoring operations between
two commits have been proposed [2, 8, 9, 10]. These approaches usually detect each refactoring operation by analyzing source code changes stored at commits in source code
repositories.
Many of the existing approaches are not correctly viable
when a refactoring operation was saved together with nonrefactoring changes or several refactoring operations were
saved at the same location. These refactoring operations
are called impure refactoring [3]. To alleviate this problem, the approaches detecting several refactoring operations
conducted at the same location have been proposed [5, 7].

(b) Revised commit(755231)

Figure1:
Exampleofimpurerefactoring applied to a constructor of a classorg.apache.tools.tar.TarEntry in the Apache
Ant SVN repository.

For instance, Mahouachi et al. proposed a search-based approach that detects a sequence of refactoring operations using structural metrics [7]. Hayashi et al. proposed an approach that detects multiple refactoring operations using agraph search technique [5]. This approach considers a commit of a program as a state and detects the refactoring operations by searching appropriate path between two states (i.e.,
previous and revised commits) and estimating the heuristic
distances.

Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than ACM
must be honored. Abstracting with credit is permitted. To copy otherwise, or republish,
to post on servers or to redistribute to lists, requires prior specific permission and/or afee. Request permissions from Permissions@acm.org.

IWoR’16, September 4, 2016, Singapore, Singapore
c 2016 ACM. 978-1-4503-4509-5/16/09...$15.00
http://dx.doi.org/10.1145/2975945.2975949

13

However, to our knowledge, there is no approach that
detects refactoring operations that are saved together with
non-refactoring changes in the same version. For example,
when ‘Rename Method ’ refactoring and ‘the addition of error
handling’ have been applied to the same method and thensaved at the same commit, existing tools only detect ‘Rename Method ’ operation and fail to detect non-refactoringchanges, the addition of error handling. An example of impure refactoring stored in the Apache Ant Subversion (SVN)
repository is described in Figure 11 . Note that we changed
layouts of this example to save space. Manual investigation of this impure refactoring code fragments reveals thatdevelopers performed ‘Extract Method ’ refactoring (underlined) along with a non-refactoring change (bold) at thesame method in a class named as TarEntry at the samecommit. However, these non-refactoring changes cannot be
detected by existing refactoring detection approaches because existing approaches are only able to detect refactoring
operations.
To tackle this problem, we propose an approach that detects impure refactoring by extending Hayashi and his colleagues’ work. The fundamental difference is that their work
only detects several refactoring operations whereas our approach detects not only several refactoring operations but
also refactoring operations and non-refactoring changes thatwere saved at the same location at the same revision. Our
approach, at first, detects refactoring operations using agraph search algorithm and test cases from previous andrevised versions. Then, it identifies non-refactoring changes
based on structural differences between the version yieldedby the application of the detected refactoring operations andrevised versions. We also applied our approach to actualclasses stored in the Apache Xerces 2 SVN repository andconfirmed the feasibility of the approach. The primary contributions of this paper can be summarized as follows:

FODVV([DPSOH^YRLGH[DPSOH ^LQW D ``
2ULJLQDO6RXUFH&RGH>FODVV([DPSOH^YRLGH[DPSOH ^LQWD ``@
7RNHQVHTXHQFHVGLYLGHGE\FRPPD 

Figure 2: Example of token sequence convert

2.1

This step detects refactoring operations using a graphsearch algorithm, A∗ search [12]. The A∗ search estimates
the total cost of a path involving a state n using a heuristicbased evaluation function. In this study, refactoring detections are formalized as states N (a set of program), initialstate so ∈ N (previous commit), and finial state sm (current commit). Moreover, a next state is generated by thevalue of an evaluation function. The refactoring detection iscomprised of following five steps:
Step1. Initialize priority queue and then enqueue a pair of
initial state and its value of evaluation function hs0 , e0 i
into the queue.
Step2. Dequeue a pair which has the smallest evaluation
value and the dequeued state is defined as si . The
refactoring detection is terminated if the queue is empty.

• We present an approach to automatically detect impure refactoring. To our knowledge, this is the firstattempt to detect impure refactoring from commits.

Step3. Derive the candidates of refactoring operations
δ1 , . . . , δn by comparing the differences between si andsm . If there is no differences between them, the refactoring detection is terminated and then the si value is
output.

• We applied our approach to commits of actual classes
stored in source code repository and confirmed that
our approach can successfully detect impure refactoring.

2.

Detecting Refactoring with Graph Search

Step4. Generate new states δ0 (si ),δ1 (si ),... by applying
refactoring operations δ1 , . . . , δn into si , and then compute the evaluation function of each state.

APPROACH

The proposed approach takes the previous and the revisedcommits and a test suite of previous commit as input, thenoutputs the information of refactoring operations and nonrefactoring changes between the commits. The proposed
approach is comprised of two steps; At first, it detects refactoring operations using a graph search algorithm and a test
suite. Then, it detects non-refactoring changes by computing the structural differences between state yielded by theapplication of the detected refactoring operations and thecurrent commit. The approach assumes a commit of the
program as a state, and a refactoring operation as a transition operator. Furthermore, a new state is generated byapplying refactoring operations to a current state.

Step4. Enqueue the gernated states in the previous stepand values of evaluation function and then revert toStep 2.
Note that if refactoring detection does not finish within 600
seconds, the detection is terminated and then si , which has
the smallest evaluation value, is output.
After the detection is finished, a test suite of initial stateis exercised with si to check the modification of external behaviors of s0 and si . If a test suite is succeed, implies thatexternal behavior of s0 and si was preserved, the approachproceeds to the next step described in Section 2.2. Meanwhile, if external behavior of the program is modified, thedetection is terminated because this means that the refactoring operations are falsely detected.

1
https://svn.apache.org/viewvc?view=revision&revision=
755231
2
http://xerces.apache.org/

14

2.1.1

Computing the Value of Evaluation Function

have the same field name. For methods, they are defined
to be matched if they have the same method name and theparameter type.

This study uses a evaluation function to select the next
state. The value of evaluation function is computed using
Levenshtein distance, which measures the minimal amountof changes necessary to transform one sequence of items into
a second sequence of items [6]. In this study, levenshtein
distance di between token sequences of the methods thatshares the same method name is computed.
Let’s assume that new states (δ0 (si ),δ1 (s1 ),...) generated
in Step 4 is (A1 , A2 , ..., An ) and final states is (B1 , B2 ,..., Bn ), the number of tokens of A1 and A1 is ai and bi ,respectively, then the value of evaluation function is defined
as follows:

3.

3.1

i=1 dimax(ai , bi )i=1

Pn

Note that a value of evaluation function takes [0, 1].

Terminating Duplicated States

If a method A is pulled up after a method B is pulled
and a method B is pulled up after method A is pulled, they
will arrive at the same state. Therefore, the search shouldbe terminated if it arrive at the same state after the second
search. For alleviating this problem, the search is terminatedif the hash value of the source code and the value of theevaluation function are exactly matched.
To compute a hash value of source code, code fragment isdivided into each line of source code, and then a hash value
is generated using method hashCode() in String Classin Java 8 API. For example, when a line is comprised of thefollowing tokens:

3

No
1
2
3
4
5
6
7
8
9
10
11
12
13

The value of hashCode() is computed as follows:

31n−1 s0 + 31n−2 s1 + ... + sn−1

Detecting Non-refactoring Changes

After refactoring detection is successfully performed, thestructural differences between si and sm are regarded as the
non-refactoring changes. In this study, the non-refactoringchanges are detected as follows:

Target member
Hashtable userData
setUserData(NodeImpl, Object)
getUserData(NodeImpl)
Hashtable userData
getUserData(NodeImpl)
Hashtable userData
getUserData(NodeImpl)
Hashtable userData
setUserData(NodeImpl, Object)
Hashtable userData
setUserData(NodeImpl, Object)
setUserData(NodeImpl, Object)
getUserData(NodeImpl)

Motivation types
Addition of import statements
Additions of method bodies
Total

2. Compute levenshtein distance between the token sequences of matched members#Removed
3912#Added000Convert Source Code into Sequence of Tokens
Table 3: Non-Refactoring changes detected from aclass CoreDocumentImpl

Our proposed approach converts the source code of si andsm into token sequences. The purpose of converting sourcecode into token sequences is to ignore comments and whitespace. Figure 2 depicts an example of converting a Javasource code into token sequences.

2.2.2

Refactoring
F
M
M
F
M
F
M
F
M
F
M
M
M

Table 2: Non-Refactoring changes detected from aclass DocumentImpl

1. Convert source code of si and sm into a token sequence,
respectively.

2.2.1

http://svn.apache.org/viewvc/xerces/java/

Table 1: Refactoring operations detected in a class
DocumentImpl(s0 , s1 , ..., sn−1 )2.2

ResultFigure 3 depicts an overview of the search. Note thatthe refactoring operations were only detected in the class
DocumentImpl. In this figure, circles represent searchedstates and the numbers on the circles represent the value ofthe evaluation function. Moreover, arrows represent statetransitions and the search was conducted in the order of
number written on the arrow. The detailed information is

Pn

2.1.2

CASE STUDY

To show the feasibility of our approach, we applied it to
two actual classes DocumentImpl and CoreDocumentImpl
which are stored between two commits ‘318022’ and ‘318023’
in the Apache Xerces SVN repository3 . This section discusses the result of case study and then explains threats tovalidity of the case study.

Motivation types
Addition of import statements
Additions of method bodies
Changes of method bodies
Addition of field declarations
Addition of methods
Total

Match Members

The order of members in the class is not always fixed
between the states. Therefore, this approach only computes
structural differences between the matched members. For
field declarations, they are defined to be matched if they15

#Removed
3
18
12
3
585
621

#Added
0
0
47
0
0
47

4.

We proposed an approach that detects impure refactoring
using a graph search algorithm, a test suite, and structuraldifferences. We applied our approach to two actual classes
in the Apache Xerces SVN repository and confirmed thefeasibility of the approach.
For future work, we are plan to apply our proposed approach to additional open source software systems and industrial software systems.





SUMMARY





5.






ACKNOWLEDGMENTS

This work was supported by JSPS KAKENHI Grant Numbers JP25220003, JP26730036, JP16K16034, JP15H06344.




6.



REFERENCES[1] G. Bavota, A. D. Lucia, M. D. Penta, R. Oliveto, and
F. Palomba. An experimental investigation on the
innate relationship between quality and refactoring. J.
Syst. Softw., 107(C):1–14, Sept. 2015.
[2] B. Biegel, Q. D. Soetens, W. Hornig, S. Diehl, andFigure 3: Overview of the search
S. Demeyer. Comparison of similarity metrics forrefactoring detection. In Proc. of MSR, pages 53–62,
2011.
shown in the Tables 1, 2, and 3. Table 1 illustrates thestate transition diagram on the search. In this table, each[3] C. Gőrg and P. Weissgerber. Detecting and visualizing
number in the column ‘No’ corresponds to the order number
refactorings from software archives. In Proc. of IWPC,
shown in Figure 3 and The column ‘Refactoring’ represents
pages 205–214, 2005.
the detected refactoring operations. In this column, ‘F’ rep[4] A. E. Hassan. The road ahead for mining software
resents ‘Pull Up Field ’ and ‘M’ represents ‘Pull Up Method ’.
repositories. In Proc. of FoSM, pages 48–57, 2008.
As seen in this table, ‘Pull Up Field ” and ‘Pull Up Method ’[5] S. Hayashi, Y. Tsuda, and M. Saeki. Search-based
refactoring operations were detected by our approach.
refactoring detection from source code revisions.
Moreover, Tables 2 and 3 depicts non-refactoring changes
IEICE Trans. Inf. Syst., E93-D(4):754–762, apr 2010.
detected from DocumentImpl and CoreDocumentImpl classes, [6] V. Levenshtein. Binary Codes Capable of Correcting
respectively. In these tables, column ‘#Removed ’ and ‘#Added ’Deletions, Insertions and Reversals. Soviet Physics
represents a number of removed and added tokens, respecDoklady, 10:707, 1966.
tively.
[7] R. Mahouachi, M. Kessentini, and M. Ó Cinnéide.
After the detection, we manually analyzed the source code
Search-based refactoring detection. In Proc. ofof the classes DocumentImpl and CoreDocumentImpl and
GECCO Companion, pages 205–206, 2013.
confirmed that our approach accurately detected ‘Pull Up[8] N. A. Milea, L. Jiang, and S.-C. Khoo. Vector
Field ’ and ‘Pull Up Method ’ refactoring operations. For nonabstraction and concretization for scalable detection of
refactoring changes, we also manually checked the source
refactorings. In Proc. of FSE, pages 86–97, 2014.
code and confirmed that 12 tokens (class DocumentImpl)[9]K.
Prete, N. Rachatasumrit, N. Sudan, and M. Kim.
and 621 tokens (class CoreDocumentImpl) were really deleted
Template-based
reconstruction of complex
and 47 tokens (class CoreDocumentImpl) were really added
refactorings. In Proc. of ICSM, pages 1–10, 2010.
between the commits.
[10] Z. Xing and E. Stroulia. Refactoring detection basedon umldiff change-facts queries. In Proc. of WCRE,
3.2 Threats to Validity
pages 263–274, 2006.
The result of case study might be lack of generalities.
[11]
N.
Yoshida, T. Saika, E. Choi, A. Ouni, and K. Inoue.
Even though our approach accurately detects impure refacRevisiting the relationship between code smells andtoring, the result might change because we only apply ourrefactoring. In Proc. of ICPC, pages 48–57, 2016.
approach to two classes in the Apache Xerces project. As a[12] W. Zeng and R. L. Church. Finding shortest paths on
future work, we plan to apply the approach to other comreal road networks: The case for A*. Int. J. Geogr.
mits and software systems to achieve the generality of ourInf. Sci., 23(4):531–543, Apr. 2009.
proposed approach.




16