Identifying, Tailoring, and Suggesting Form Template Method
Refactoring Opportunities with Program Dependence Graph
Keisuke Hotta, Yoshiki Higo, Shinji Kusumoto
Graduate School of Information and Science Technology, Osaka University, Japan
1-5, Yamadaoka, Suita, Osaka, 565-0871, Japan{k-hotta, higo, kusumoto}@ist.osaka-u.ac.jp

Abstract—Many research efforts have been performed on
removing code clones. Especially, it is highly expected thatclone removal techniques by applying Form Template Method
have high applicability because they can be applied to code
clones that have some gaps. Consequently some researchers
have proposed techniques to support refactoring with Form
Template Method. However, previous research efforts still havesome issues. In this paper, we propose a new technique with
program dependence graph to resolve these issues. By using
program dependence graph, we can handle trivial differencesthat are unrelated to behavior of a program. Consequently
the proposed method can suggest more appropriate removal
candidates than previously proposed techniques.
Keywords-Code Clones, Refactoring, Form Template
Method, Program Dependence Graph, Software Maintenance

I. I NTRODUCTION
Recently, code clones have received much attention. Codeclones are identical or similar code fragments in sourcecode. Code clones are generated by various reasons suchas copy-and-paste operations. Recent studies have revealed
that a portion of code clones has negative impacts on
software maintenance [1], [2]. The reason is that, if we
modify a code fragment, it is necessary to check whether its
cloned code fragments need the same modifications or not.
Consequently, many research efforts have been performed
on detecting code clones and removing them by applying
some refactorings [3], [4].
Some researchers have proposed code clone removal
techniques by applying Form Template Method [5]. Form
Template Method is one of the refactoring patterns proposedby Fowler et al. [6]. Form Template Method uses Template
Method that is one of the design patterns proposed byGamma et al. [7]. In Template Method, developers write an
outline of the process into the base class and implement
the details of the process in the derived classes. In order toapply this pattern to similar methods that have a commonbase class, duplicated code fragments between the methods
are pulled up to the base class, and non-duplicated codefragments remain in its derived classes. As a result, code
clones in the similar methods are merged into the baseclass. Comparing to other clone removal techniques, thesetechniques are suitable to handle differences between target
methods. However, previously proposed techniques remainsome issues that they cannot suggest code clones as removal
candidates if they have the following differences even if they
have no impact on the behavior of the program.
• Different order of code fragments.
• Different implementation styles (such as for- and whileloops).
In this paper, we propose a new technique to support
applications of Form Template Method with program dependence graph to resolve these issues. The proposed approach
supports identifying the places to be refactored and applying
the refactoring in refactoring activities proposed by Mens etal. [8].
II. M OTIVATION
A. Related Work
Recently, many researchers have proposed techniques
assisting refactorings [8]. Fowler et al. said that duplicationof source code is a “bad smell” on software maintenance[6], and many research efforts have been performed on
removing code clones by applying refactorings in this basis[3], [4], [9], [10]. However, it has been debated in recent
years whether code clones really have negative impacts on
software maintenance or not [1], [2], [11]. At present, there
is no consensus of this issue because the results of thesestudies vary according to research methods or target softwaresystems.
Many research efforts have been performed on searchbased software engineering in recent years [12]. One of theresearch areas in it is search based refactoring [13], [14].
Some researchers have pointed out that the final design after
refactoring can be affected with the order of refactoring activities. Therefore, some techniques are proposed to optimize
refactoring schedules to maximize the benefits and minimize
the efforts of refactorings [15], [16].
The majority of clone removal techniques is based on
Extract Method or Pull-Up Method refactorings, and there
are few techniques based on Form Template Method refactoring. Juillerat et al. proposed a method to automatically
apply Form Template Method to a pair of similar methods
with abstract syntax tree [5]. Their method can show sourcecode after the application of the pattern, and the execution

time and memory space required to the calculation are
not so high. However, their method cannot handle trivial
differences that do not have any impacts on the behavior of programs, such as differences between user-defined
identifiers, different order of code fragments, and different
implementation styles (such as the difference of for- andwhile-loops).

public int calc() {int result = 0;
int dc = getDC(getRegion());
result += dc;

III. P RELIMINARIES
A. Form Template Method
Form Template Method is one of the refactoring patterns

int i = 0;
while (i < getList().size()) {Item item = getList().get(i);s += item.getPrice();points += item.getPoints();i++;}
addPoints(points);
int dc = getDC(getRegion());
result += dc;
result += s * TAX_RATE;

int sum = 0;
int points = 0;
for (int i = 0; i < getList().size(); i++) {Item item = getList().get(i);sum += item.getPrice();points++;gaps}

B. Aim of This Study
There are some techniques that assist developers in applying Form Template Method refactorings [5]. However,they remain some issues that these techniques cannot handle
trivial differences that have no impact on the behavior of
the program such as the order of the program statements
and differences of for- and while-loops. In the example
shown in Figure 1, there is a difference of the orderof code fragments, and there is also a difference of theimplementation style of loop statements. However, thesedifferences do not influence the meanings of the program.
The only meaningful difference is the ways of calculationsof variable points. Nevertheless the previous methods regard
these trivial differences as gaps between the two methods
and suggest only four lines as duplicate statements in thetwo methods. In this study, we aim to improve these issues
by using program dependence graph, and we will suggest 11
lines except the calculation of points as duplicate statements.
In addition, users need to specify target methods for using
the previous techniques. This approach is useful for actual
modifications in source code associated with refactoring
activities. However, this approach cannot reduce efforts for
identifying opportunities on which users want to apply refactorings. Because we think users have to pay many efforts
to identify refactoring candidates, we aim to support both
detection of refactoring candidates and actual modificationsof source code. The proposed method detects refactoring
candidates automatically and suggests all the candidates
to users. Consequently, the proposed method can suggest
refactoring candidates of which users are not aware. The
proposed method also suggests code fragments to be mergedin each of refactoring candidates, which makes it possible
to reduce efforts required to modify source code to apply
Form Template Method refactorings.
Note that the proposed method aim not to suggest candidates that should be refactored but to suggest candidates
that can be refactored. The reason is that there is no strict
and generic standard to judge whether code clones should
be removed, and to judge whether Form Template Methodshould be used to remove code clones. Accordingly, we
leave such decisions to users whether they need to apply
refactorings on each candidate that our method suggests.

public int calc() {int result = 0;
int s = 0;
int points = 0;

result += sum * TAX_RATE;
addPoints(points);
return result;}

DuplicateStatements

return result;}(a) The Proposed Method
public int calc() {int result = 0;

public int calc() {int result = 0;
int s = 0;
int points = 0;

int dc = getDC(getRegion());
result += dc;

int i = 0;
while (i < getList().size()) {Item item = getList().get(i);s += item.getPrice();points += item.getPoints();i++;}
addPoints(points);
int dc = getDC(getRegion());
result += dc;
result += s * TAX_RATE;

int sum = 0;
int points = 0;
for (int i = 0; i < getList().size(); i++) {Item item = getList().get(i);sum += item.getPrice();points++;}result += sum * TAX_RATE;
addPoints(points);
return result;}

DuplicateStatements

gaps

return result;}(b) The Method Proposed by Juillerat et al.[5]Figure 1.

A Motivating Example

proposed by Fowler et al. [6]. In this refactoring pattern,developers write an outline of the process in a base class,and the base class delegates implementations of the details
to each of its derived classes. This pattern can be applied toremove code clones by pulling up code clones into the baseclass as a common process.
Figure 2 shows an example of application of Form Template Method [6]. There are two classes that have the samebase class, Site, and these two classes have the methods thatare similar to each other, getBillableAmount. By applying
Form Template Method to these methods, the common
code fragments are pulled up into the base class, and theunique code fragments in each method are extracted as new
methods, getBaseAmount and getTaxAmount. We call the
new method written in the base class as template method. By
this transformation, code clones in the methods are merged
into the template method, and the unique code fragmentsin each method are handled well by creating new methods
without changing the behavior of the program.
In this paper, we call common code fragments that shouldbe pulled up to base classes as a common process, andSite

before1: x = 0;
2: y = 0;
3: z = MAX;
4: while (y < z) {5:
y = x + 1;
6: }7: println(y);double base = units * rate;
double tax = base * Site.RATE;
return base + tax;
double base = units * rate * 0.5;
double tax = base * Site.RATE * 0.2;
return base + tax;

Residential Site

Lifeline Site

getBillableAmount()

getBillableAmount()

method
enter

<1>

<3>

<2>
<4>

Data Dependence Edge
<5>

Control Dependence Edge<7>

return getBaseAmount() + getTaxAmount();

after

Figure 3.

Site
return units * rate;

getBillableAmount()
getBaseAmount()
getTaxAmount()

An Example of PDG

return base * Site.RATE;
return units * rate * 0.5;
return base * Site.RATE * 0.2;

Residential Site

Lifeline Site

getBaseAmount()
getTaxAmount()

getBaseAmount()
getTaxAmount()

1: Obj o = new Obj();
2: o.changeState(1);3: o.changeState(2);4: o.changeState(3);

<1>

<1>

<3>

<2>

<4>
<2>

Figure 2.

<3>

<4>

An Example of the Application of Form Template Method

without considering state change
Figure 4.

unique code fragments that should remain in each of derived
classes as a unique process instead.
B. Program Dependence Graph
Program Dependence Graph [17] (in short, PDG) is oneof the directed graphs representing dependence between
elements of program (such as statements and conditional
predicates). Dependence in PDG are classified into thefollowing two categories.
Data Dependence: There is data dependence from statement s to statement t, if a value is assigned to variable x ins, and t references x without changing the value of x.
Control Dependence: There is control dependence fromstatement s to statement t, if s is a conditional predicate,and it directly determines whether t is executed or not.
Figure 3 shows an example of PDG. In this example, thereis data dependence from the 2nd, 3rd, and 5th lines to the
4th line because variables y and z are referenced in the 4thline. There is control dependence from the 4th line to the 5thline because the conditional predicate in the 4th line directly
controls the execution of the 5th line. In addition, there isa node labeled “method enter” that means the enter node of
the method. In general, PDG contains a method enter node,
and, in this case, there is control dependence from the enter
node to all nodes that are directly contained by the method.
Moreover, we tailor PDGs to trace state changes ofobjects. The state of an object changes when the values of its
fields change [18]. Figure 4 shows the tailoring. By applying
this tailoring to PDGs, we can get the order of operations
to objects from PDG. This enables us to apply refactorings
with the operation order of objects preserved.
C. Code Clones Detection by Program Dependence Graph
There are many techniques to detect code clones automatically. They can be categorized by its data structuresconsidering
state change

PDG Considering State Changes of Objects[19]. PDG-based detection is one of the categories, and someresearchers have proposed PDG-based detection techniques[20], [21], [22]. This technique detects isomorphic subgraphs
on PDGs as code clones. PDG-based detection can detect
code clones containing different order of statements, andtrivial differences that do not have any impacts on the
behavior of the program such as a difference between forand while-loops.
In this paper, we use Scorpio [22] to detect code clones.
Scorpio is one of the PDG-based detection tools, and it wasdeveloped by our research member. Scorpio can detect code
clones that have differences of user-defined identifiers.
IV. P ROPOSED M ETHOD
A. Inputs and Outputs
The proposed method takes the source code of the target
software systems as its input. Then, the proposed method
detects all the candidates that can be refactored with Form
Template Method and suggests them to users. Note that
we regard a pair of methods as a candidate of refactoring
likewise the previous method. For each of refactoring candidates, the proposed method also suggests program statements that can be merged into the base class as the common
process, and program statements that should be remain in thederived classes as the unique process. Additionally, for theunique process, the proposed method suggests the following
two information.
Sets of program statements that should be extracted asa single method.
• Pairwise relationships of new methods created in thepair of the derived classes between the couple of the•methods. Note that the new methods in a pairwise relationship can be extracted as methods whose signatures
are the same as each other.
B. Definitions

ClonePairs(G1 , G2 ) :=In this subsection, we describe definitions of terms referenced in the following explanations.
A directed graph G is represented as G = (f, V, E),
where V is a set of nodes, E is a set of edges, and f is a
map from edges to ordered pairs of nodes (f : E → V ×V ).
In this paper, we write the set of nodes in G as VG , the set ofedges in G as EG , and the map between edges and orderedpairs of nodes in G as fG respectively.
A PDG of a program is one of the directed graphs. Givena PDG G = (f, V, E), a node of G corresponds to anelement of the program, and an edge of G corresponds to
a dependence between two elements. Note that we builda PDG in each of methods, therefore every method has acorresponding PDG.
As described above, there are two types of dependence in
PDGs.
Definition 4.1 (Dependence between Elements):
We write data dependence as data, and control
dependence as control. We define type as a map
from edges to the types of dependence that theedges represent (type : E → EdgeType), where
EdgeType = {data, control }. In addition, a data edge has
information about the variable that the edge represents. We
define var (ed ) as the represented variable by a data edgeed .
In the next, we define a tail of an edge e ∈ EG as tail (e)and a head of e as head (e). The definitions are as follows.
Definition 4.2 (tail (e),head (e)): We define tail (e) as
the first element of fG (e), and head (e) as the last elementof fG (e). In other words, tail (e) := u and head (e) := v,
where fG (e) = (u, v).
Herein, we define sets of edges BackwardEdges(v) and
ForwardEdges(v) for v ∈ VG . BackwardEdges(v) is a setof edges whose head is v defined in the formula (1), andForwardEdges(v) is a set of edges whose tail is v definedin the formula (2).
Definition 4.3 (BackwardEdges(v),ForwardEdges(v)):
BackwardEdges(v) := {e ∈ EG | head (e) = v}
ForwardEdges(v) := {e ∈ EG | tail (e) = v}

Definition 4.4 (ClonePairs(G1 , G2 ) and a clone pair):
We define ClonePairs(G1 , G2 ) with the formula (3), andwe call every element of ClonePairs(G1 , G2 ) “clone pair”.

(1)
(2)

Next, we describe definitions about code clones. We use
Scorpio [22] to detect code clones. We can get isomorphic
subgraphs in two PDGs given as its input data with Scorpio.
We define a set of ordered pairs of isomorphic subgraphs
detected with the technique as ClonePairs(G1 , G2 ), whereG1 and G2 are PDGs given as its input data. The definitionis as follows.

′{(G′1 , G′2 ) | G′1 ⊂ G1 ∧ G′2 ⊂ G2 ∧ G′1 ∼= G2 }(3)

where, G1 and G2 are PDGs given as input data, G′ ⊂ Gindicates G′ is a subgraph of G, and G′ ∼= G′′ indicates G′′′
and G are isomorphic subgraphs to each other.
We also define duplicate relationships on nodes of PDGs
as follows.
Definition 4.5 (Duplication of nodes): We define thetwo nodes v1 ∈ VG1 and v2 ∈ VG2 are duplicated to eachother if they satisfy the formula (4). We represent v1 ∼ v2
if v1 and v2 are duplicated to each other.
∃(G′1 , G′2 ) ∈ ClonePairs(G1 , G2 )[v1 ∈ VG′1 ∧ v2 ∈ VG′2 ∧ φ(v1 ) = v2 ](4)

where, G1 and G2 are PDGs, and φ indicates the isomorphism between G′1 and G′2 (G′1 ∼= G′2 ).
C. Processing Flow
The processing flow of the proposed method is shown
below.
STEP1: Create PDGs, and detect code clones in them.
STEP2: Identify pairs of methods that can be refactoredby Form Template Method.
STEP3: Detect a common process and a unique process
for each of method pairs.
In STEP1, we use the existing techniques. In the following
subsections, we describe STEP2 and STEP3 in detail.
D. Identification of Refactoring Candidates
In this step, we detect pairs of methods that can be
refactored by Form Template Method refactoring patternwith code clones detected by Scorpio. We regard a pair ofmethods as a refactoring candidate if it satisfies the following
two requirements.
Requirement A: Form Template Method can be applied
to the method pair.
Requirement B: There is at least one clone pair between
the method pair.
We describe these requirements in detail in the following
subsections.
1) Requirement A (Applicability of the Pattern): Form
Template Method can be applied to methods whose ownerclasses have the same base class. Accordingly, owner classesof each of two methods in a refactoring candidate must havethe same base class in the proposed method. In addition, we
cannot apply Form Template Method to methods that are
defined in the same class. Therefore, refactoring candidates

Algorithm 1 Removing Redundant Clone Pairs

method m1

Require: ClonePairs(Gm1 , Gm2 )Ensure: ClonePairs(Gm1 , Gm2 ) after repaired
1: for all (G′m1 , G′m2 ) ∈ ClonePairs(Gm1 , Gm2 ) do′′2:
for all (G′′m1 , Gm2 ) ∈ ClonePairs(Gm1 , Gm2 ) do′3:
if ∃v1 ∈ Gm [v1 ∈ G′′
m1 ] then1
4:
if |G′m | < |G′′m1 | then1
5:
ClonePairs(Gm1 , Gm2 ) ← (G′m , G′m )
1
2
6:
else
′′
7:
ClonePairs(Gm1 , Gm2 ) ← (G′′
,
G
m1
m2 )
8:
end if9:
end if10:
if ∃v2 ∈ G′m2 [v2 ∈ G′′
m2 ] then11:
if |G′m | < |G′′m2 | then2
12:
ClonePairs(Gm1 , Gm2 ) ← (G′m , G′m )
1
2
13:
else
′′
14:
ClonePairs(Gm1 , Gm2 ) ← (G′′
,
G
m1
m2 )
15:
end if16:
end if17:
end for
18: end for

a

b

c

A

α
d

B

e

G

I

CommonNodes(m2) ={A, B, C, D, E}

J

An Example of the Redundant Clone Pairs

represents the definition, where Gm1(2) indicates the PDG
of method m1(2) .
CommonNodes(Gm1(2) ) :={v ∈ VGm1(2) | ∃w ∈ VGm2(1) [v ∼ w]}

For each of method pairs, we detect a common process,and a unique process in STEP3.
This step consists of the following three sub-steps.
STEP3-A: Detect a common process and a uniqueprocess in a given method pair.
STEP3-B: Detect sets of program statements, each ofwhich should be extracted as a single method for the uniqueprocess.
STEP3-C: Detect pairwise relations of sets of program
statements detected in STEP3-B in the method pair.
1) STEP3-A: Detection of Common and Unique Processes: In this sub-step, the proposed method detects acommon process and a unique process in a given method
pair. In the proposed method, we regard code clones
in the method pair as the common process. We define
CommonNodes(Gm1(2) ) as a set of nodes in Gm1(2) whosestatements form the common process. The formula (6)(6)

However, a node in Gm1(2) can be duplicated between two
or more nodes in Gm2(1) . In other words, the formula (7)can be satisfied in some cases, considering the two clone
pairs (G′m1 , G′m2 ), (G′′m1 , G′′m2 ) ∈ ClonePairs(Gm1 , Gm2 ).
∃v ∈ VG′m1(2)E. Tailoring Refactoring Candidates

H

CommonNodes(m1) ={a, b, c, d, e}

Figure 5.

D

F

g

(5)

C

E

β

f

in the proposed method must satisfy the following two
requirements.
Requirement A-1: The two methods in the candidates
are defined in different classes.
Requirement A-2: The owner classes of the two methods
have the same base class.
2) Requirement B (Presence of Clone Pairs): If there
is no clone pair between a method pair (m1 , m2 ),ClonePairs(Gm1 , Gm2 ) is empty, where Gm1 and Gm2 are
PDGs of method m1 and m2 . Therefore, we can check
whether there is at least one clone pair by checking whether
ClonePairs(Gm1 , Gm2 ) is empty or not. In other words,
the method pair m1 and m2 in the proposed method mustsatisfy the formula (5).
ClonePairs(Gm1 , Gm2 ) ̸= ∅method m2[v ∈ VG′′m

1(2)

]

(7)

In this case, we cannot merge all the nodes that are duplicate
to other nodes in the other method. We remove some clone
pairs from ClonePairs(Gm1 , Gm2 ) to resolve this problem.
Algorithm 1 shows the algorithm for removing clone pairs.
Note that |R| means the number of elements in a set R andR ← r means the process to remove an element r from R.
By applying this algorithm, we can ensure that there is at
most one duplicate node in the other method for all nodes
in method m1 and m2 . Nodes should be pulled up into thebase class if they are contained in CommonNodes(Gm1(2) )after this processing.
Figure 5 shows an example that contains redundant clone
pairs. There are two clone pairs labeled α and β. The clone
pair α consists of ({a, b, c, d, e}, {A, B, C, D, E}), and theclone pair β consists of ({a, b, d, e}, {F, G, H, I}). In thiscase, the algorithm selects α as the remaining clone pair, andremove β from ClonePairs(Gm1 , Gm2 ) because the numberof elements of α is larger than β’s one. As a result, thecommon code fragments that the proposed method detects inthis method pair (CommonNodes(Gm1(2) )) are {a, b, c, d, e}and {A, B, C, D, E} respectively.
On the other hand, the proposed method regards that
program statements form a unique process in a given method
pair if they are not included in the common process. We
define DiﬀNodes(Gm1(2) ) as a set of nodes whose ownerstatements are not included in the common process. Formula(8) shows the definition of DiﬀNodes(Gm1(2) ).
DiﬀNodes(Gm1(2) ) := {v ∈ VGm1(2) |v∈/ CommonNodes(Gm1(2) )}(8)

Note that nodes contained in DiﬀNodes(Gm1(2) ) need toremain in the class that has method m1(2) .
2) STEP3-B: Detection of Statements Extracted as a Single Method: In this sub-step, the proposed method detects
sets of statements that can be extracted as a single methodin the unique process.
For applying Form Template Method refactorings, nodes
remaining in derived classes have to be extracted as new
methods. Therefore, we have to detect sets of code fragments included in DiﬀNodes(Gm1(2) ), each of which canbe extracted as a single method.
In the proposed method, we regard nodes included in
DiﬀNodes(Gm1(2) ) as a set that should be extracted as asingle method, if there is at least one path that does notinclude nodes in CommonNodes(Gm1(2) ) for any pairs of
the nodes in it. In other words, we regard a set of nodes
Sm1(2) that is a subset of VGm1(2) as a set of nodes thatshould be extracted as a single method, if there is at least
one path that satisfies the formula (9) for any two nodes
v1 , vn (v1 ̸= vn ) in Sm1(2) .
∀i ∈ {1 . . . n}[vi ∈ DiﬀNodes(Gm1(2) )](9)

We call a set of nodes that should be extracted as asingle method an Extract Node Set (in short. ENS). In
the example shown in Figure 6, we can find two ENSs. One
consists of {d, g} and the other consists of {b, c, h, k, l}.
As shown in this example, each of methods in refactoring candidates can contain multiple ENSs. We define
DiﬀNodeSets(Gm1(2) ) as a family of ENSs in method
m1(2) . Any node in DiﬀNodes(Gm1(2) ) must be included
in a ENS in DiﬀNodeSets(Gm1(2) ) (formula (10)).
∀v ∈ DiﬀNodes(Gm1(2) ) ∃S ∈ DiﬀNodeSets(Gm1(2) )[v ∈ S](10)3) STEP3-C: Detection of Pairwise Relationships of
New Methods: In this sub-step, we detect pairwise relationships of ENSs in a given method pair. In otherwords, assuming that ⇀↽ indicates the pairwise relationships and Sm1(2) is an ENS of method m1(2) , for each

a
d

b
e

f

c
h

a
d

g

b
e

f

c
h

g
i

l

j

k

i

m

k
m

Nodes contained DiffNodeSets =in CommonNodes { { d, g } , { b, c, h, k, l } }Figure 6.

l

j

ENSs

An Example of the Detection of ENSs

of Sm1(2) ∈ DiﬀNodeSets(Gm1(2) ) we detect whether
Sm2(1) ∈ DiﬀNodeSets(Gm2(1) ) satisfies Sm1 ⇀↽ Sm2 exists
or not. Note that Sm1 ⇀↽ Sm2 indicates that Sm1 and Sm2
can be extracted as methods whose signatures are the sameas each other. If an ENS S has no correspondent in the othermethod, we have to make an empty method whose signatureis the same as S in the derived class that does not have S.
We regard a pair of ENSs Sm1 and Sm2 as Sm1 ⇀↽ Sm2
if they satisfy the following two requirements.
Requirement 3C-1: The types of return values of Sm1
and Sm2 are the same as each other.
Requirement 3C-2: The conditions to call the new
methods created by extracting Sm1 and Sm2 are the sameas each other.
Requirement of the Return Value: First, we define
OutputDataEdges(G, S) as a set of data edges whose tails
are included in S and whose heads are not included in S,
where G is a PDG and S is an ENS of G. The definition isshown in the formula (11).
OutputDataEdges(G, S) :={e ∈ EG | tail (e) ∈ S ∧ head (e) ∈/ S ∧ type(e) = data}(11)

Now we can define a set of output variables of S byusing this definition. We define OutputVariables(G, S) in
the formula (12).
OutputVariables(G, S) :={p | ∃e ∈ OutputDataEdges(G, S)[p = var (e)]}(12)

We can judge whether ENSs Sm1 and Sm2
have the same types of return values bycomparing
OutputVariables(Gm1 , Sm1 )and
OutputVariables(Gm2 , Sm2 ).
Requirement of the Conditions for Call: Methods
created by extracting ENSs Sm1 and Sm2 are called in thesame conditions if the control dependence into Sm1 and Sm2
are the same as each other. Herein, we describe definitions
to check this requirement.

methodm1

method
m2

a

b

c

d

e

B

E

F

V. I MPLEMENTATIONDγh str(String)gGi(int)ix(int)Cfβα

An Example of Pairwise Relationships of ENSs: Figure
7 shows an example of the detection of pairwise relationships of ENSs between two methods. In this example, we
can get two pairs of ENSs, α ⇀↽ γ and β ⇀
↽ δ.

A

H
I

: Clone Nodes: Control Dependency

α

β

γ

δ

int

Stringint

Stringtext(String)“*” means
Method EnterNode: Non-Clone Nodes: Data Dependency

We have implemented the proposed method as a tool
named Creios (Clone Removal Expediter by Identifying
Opportunities with Scorpio) in Java. Creios can handle
software systems written in Java, because Scorpio, the clone
detection tool used in Creios, can handle only Java. However,the proposed method can be applied to other programming
languages if PDGs are built.
In this section, we describe the functions of Creios.

δInput Control Node
α

β

γ

δ

*

c

*

C

A. Supporting Detection of Refactoring Candidates
Creios suggests all the candidates that can be refactoredwith Form Template Method. Therefore, the function that
supports users to select suitable candidates for refactoring
are required especially in the cases that there are a large
number of candidates. Creios has a filtering function withsome metrics to support users to select candidates (e.g.
similarities between two methods and the number of new
methods created by the refactoring).

c～C
Satisfy Requirement 3C-1

Satisfy Requirement 3C-2

α⇀
，β ⇀
↽δ
↽γ，
Figure 7.

The Detection of the Pairwise Relationships of ENSs

First, we define InputControlEdges(G, S) as a set ofcontrol edges whose heads are included in S and whose
tails are not included S, where G is a PDG and S is an
ENS of G. The definition is shown in the formula (13).
InputControlEdges(G, S) := {e ∈ EG |(tail (e) ∈/ S) ∧ (head (e) ∈ S) ∧ (type(e) = control)}(13)

In addition, we define InputControlNodes(G, S) as a setof nodes that are tails of edges in InputControlEdges(G, S)
in the formula (14).
InputControlNodes(G, S) := {v ∈ VG |∃ec ∈ InputControlEdges(G, S)[v = tail (ec )]}(14)With these definitions, we define Sm1 and Sm2 are calledin the same conditions if they satisfy the following two
formulae (15) and (16).
|InputControlNodes(Gm1 , Sm1 )| =|InputControlNodes(Gm2 , Sm2 )|(15)∀v1 ∈ InputControlNodes(Gm1 , Sm1 )∃v2 ∈ InputControlNodes(Gm2 , Sm2 )[(v1 ∼ v2 )∨(∃S1′ ∈ DiﬀNodeSets(Gm1 )∃S2′ ∈ DiﬀNodeSets(Gm2 )′′′[S1′ ⇀↽ S2 ∧ n1 ∈ S1 ∧ n2 ∈ S2 ])] (16)

B. Supporting Modifications of Source CodeCreios shows the output information of the proposed
method with GUI. Figure 8 shows a snapshot of Creios’s
output. For all the candidates, Creios shows PDGs and its
source code for every candidate. In the source code view,
Creios highlights duplicate statements in red, and draws
color rectangles around the statements for each of ENSs.
Note that the ENSs that are in the pairwise relationships are
surrounded with the same color rectangles.
Creios does not have the function that modifies theactual source code automatically. Accordingly, users need tomodify source code by themselves to apply Form Template
Method refactoring.
VI. E XPERIMENTIn order to evaluate the proposed method, we conducted
an experiment on two open source software systems.Table I
shows the target software systems, the number of detectedcandidates, and elapsed time to execute Creios.
Figure 9 shows a refactoring candidate in Ant detectedby Creios and the result of the refactoring. In this example,
there is a base class, ClearCase, and there are two derived
classes, CCCheckout and CCCheckin.There are also similar
methods in the derived classes, checkOption. By applying
Form Template Method to this target, duplicate statements
are pulled up into in the method checkOption defined in
the base class and new methods checkOther are created to
implement the unique statements in each derived class. Notethat there is a difference of the order of code fragments inCommon Statements(should be extracted into
the base class)

Unique Statements(Extract Node Set 1)

Unique Statements(Extract Node Set 2)

Figure 8.

A Snapshot of the Result of Creios

Table ITARGET S OFTWARE S YSTEMSNameApache-Ant
Apache-Synapse

In Short
Ant
SynapseLOC
212,401
58,418# of Files829
383# of Candidates
226
45

code clones: in CCCheckout the code fragments labeled A,
B, and C are executed in this order, however in CCCheckinthe order of code fragments is B-A-C. Therefore, thisexample is an instance that the previous techniques cannot
detect.
Next, we show the comparison result to the previous
method [5] in Table II. The column “Our method > Juillerat
et al.’s method” indicates the number of candidates thatthe proposed method can handle trivial differences thatthe previous method cannot handle. The proposed method
can recognize more duplicate statements than the previous
method in these candidates, therefore we can say thesecandidates shows superiority of the proposed method compared to the previous method. We cannot found candidates
that have differences of implementation style (e.g. for- andwhile-loops) in this experiment, but we confirmed that the
proposed method can handle these differences with samples
that we made.
In addition, we applied Form Template Method refactoringto all the 45 candidates that the proposed method hadsuggested in Synapse in order to confirm the adequacy andthe efficiency of the proposed method as a technique toTime[s]237
95

Environment
CPU: Xeon 2.67GHz(4 core)CRAM: 4GB

support refactorings. In this experiment, we successfully
refactored all the 45 candidates detected with Creios in
Synapse, and confirmed that the behavior of the programis preserved by using test suites attached to the softwaresystem. Additionally, we measured the time needed to eachof the refactorings. Figure 10 shows the box-plots of thetime needed to apply refactorings. Because Creios suggests
all the candidates that can be refactored at a time, we run
Creios at once and apply refactorings using the output. The
time to execute Creios to Synapse is 95 seconds as shownin Table I. As a result, we could apply refactorings in few
minutes in average nevertheless we are unfamiliar with thesoftware.
VII. D ISCUSSION
As we described in section VI, we applied Form Template
Method refactoring to 45 candidates detected in Synapse. In
some cases, we had to make some modifications that Creios
did not indicate, or we had to make some adjustments to the
output of Creios to apply the pattern. Table III shows themodifications or adjustments needed to apply refactorings,
and the number of candidates that needed them. The termClearCase

if (getComment() != null) {…
} else {…
}ClearCasecheckOption(cmd)checkOther(cmd)pull up
CCCheckout

CCCheckin

CCCheckout

CCCheckincheckOption(cmd)checkOption(cmd)checkOther(cmd)checkOther(cmd)

if (getNoWarn()) {…
}checkOther(cmd);
cmd.createArgument().setValue(getViewPath());
if (getPreserveTime()) {…
}…

extract
if (getReserved()) {cmd.createArgument().setValue(FLAG_RESERVED);} else {cmd.createArgument().setValue(FLAG_UNRESERVED);}…

A

if (getNoWarn()) {cmd.createArgument().setValue(FLAG_NOCOMMENT);}B

if (getComment() != null) {getCommentCommand(cmd);} else {if (getCommentFile() != null) {getCommentFileCommand(cmd);} else {cmd.createArgument().setValue(FLAG_NOWARN);}}C

cmd.createArgument().setValue(getViewPath());

Figure 9.

extractB

if (getComment() != null) {getCommentCommand(cmd);} else {if (getCommentFile() != null) {getCommentFileCommand(cmd);} else {cmd.createArgument().setValue(FLAG_NOCOMMENT);}}A

if (getNoWarn()) {cmd.createArgument().setValue(FLAG_NOWARN);}
if (getPreserveTime()) {cmd.createArgument().setValue(FLAG_PRESERVETIME);}

An Example of Application of Form Template Method with Proposed Method

2000
1500
1000
500

Figure 10.

method : abstract method

cmd.createArgument().setValue(getViewPath());

2500

Whole Time

: Code Clone

…

C

3000

0
[sec]

if (getReserved()) {…
} else {…
}…

Code Modification

The Box-plots of the Time to Apply Refactorings“modify ENS” means the cases in which we had to modify
ENSs or their pairwise relationships between two methods
that Creios suggests, the term “move methods into base classor change their visibility” means the cases in which some

Table II
T HE R ESULT OF THE C OMPARISON E XPERIMENTS# of candidates
Our method > Juillerat et al.’s method-Differences of order of code
-Differences of variable names-Differences of implementation styles
Same result

Ant
226
14
10
4
0
202

Synapse
45
3
1
2
0
42

methods defined in derived classes are used in common
processes and we had to move those methods into the baseclass and/or change their visibilities, and the term “replace
field references to calls of getter methods” indicates thecases in which some fields are used in duplicate statements
and they are not visible from the base class and we had toreplace references of these fields to calls of getter methodsof them.
The proposed method does not consider the visibilityof methods and fields in the source code. Therefore, it
is possible that code fragments that should be pulled up
into template method call methods or reference fields thatare not accessible from the base class. In such cases, weneed additional modifications on the source code to apply
Form Template Method. We can apply the pattern to suchcandidates by changing the visibility of methods and fields.
However, it is not desirable that code clone removal requires
increasing the visibility of methods or fields, because such
Table IIIT HE C ANDIDATES THAT N EED SOME M ODIFICATIONS FOR C REIOS ’ S
O UTPUTS# of candidates that need no modifications# of candidates that need some modifications
modify ENS
move methods into base class and/or change their visibilities
replace field references to calls of getter methods

29
16
12
4
2

changes could cause vulnerability [23]. For fields, if fields
have getters and setters, we can resolve this problem byusing them.

[8] T. Mens and T. Tourwé, “A survey of software refactoring,”
IEEE Transactions on Software Engineering, vol. 30, no. 2,
pp. 126–139, Feb. 2004.

VIII. C ONCLUSION
In this paper, we proposed a new technique to assist
developers to apply Form Template Method refactorings oncode clones. It detects refactoring candidates automaticallyand suggests all the candidates that can be applied Form
Template Method. It uses PDG as its data structure, whichenables us to handle trivial differences that have no impact
on the meaning of the program.
As future work, we are going to make it possible to handle
not only pairs of methods but also sets of them. In addition,
we are going to improve our method for assuring behavior
preservation, and implement a function that suggests thesource code after the application of Form Template Method.

[9] N. Göde, “Clone removal: Fact or fiction?” in Proc. of the
4th International Workshop on Software Clones, 2010.

ACKNOWLEDGMENT
The present research is being conducted as a part of
the Stage Project, the Development of Next Generation
IT Infrastructure, supported by the Ministry of Education,
Culture, Sports, Science, and Technology of Japan. This
study has been supported in part by Grants-in-Aid for
Scientific Research (A) (21240002) and Grant-in-Aid for
Exploratory Research (23650014) from the Japan Society
for the Promotion of Science, and Grand-in-Aid for Young
Scientists (B) (22700031) from Ministry of Education, Science, Sports and Culture.
R EFERENCES[1] N. Göde and R. Koschke, “Frequency and risks of changes
to clones,” 33rd International Conference on Software Engineering, pp. 311–320, May 2011.
[2] N. Bettenburg, W. Shang, W. M. Ibrahim, B. Adams, Y. Zou,
and A. E. Hassan, “An empirical study on inconsistentchanges to code clones at the release level,” Science ofComputer Programming in Press, 2011.
[3] R. Fanta and V. Rajlich, “Removing clones from the code,”
Journal of Software Maintenance, pp. 223–243, 1999.
[4] Y. Higo, T. Kamiya, S. Kusumoto, and K. Inoue, “Aries:
Refactoring support environment based on code clone analysis,” the International Conference on Software Engineeringand Applications, pp. 222–229, 2004.

[10] S. Schulze and M. Kuhlemann, “Advanced analysis for code
clone removal,” in Proc. of the 11th Workshop on Software
Reengineering, 2009.
[11] C. J. Kapser and M. W. Godfrey, ““cloning consideredharmful” considered harmful: Patterns of cloning in software,”
Empirical Software Enginieering, 2008.
[12] M. Harman, “The current state and future of search based
software engineering,” Future of Software Engineering, 2007.
[13] O. Seng, J. Stammel, and D. Burkhart, “Search-based determination of refactorings for improving the class structureof object-oriented systems,” in Proc. of the 8th Annual
Conference on Genetic and Evolutionary Computation, July
2006, pp. 1909–1916.
[14] M. O’Keeffe and M. O. Cinnéide, “Search-based refactoringfor software maintenance,” Journal of Systems and Software,
vol. 81, no. 4, pp. 502–516, Apr. 2008.
[15] S. Lee, G. Bae, H. S. Chae, D.-H. Bae, and Y. R. Kwon,“Automated scheduling for clone-based refactoring using acompetent ga,” Software: Practice and Experience, 2010.
[16] M. F. Zibran and C. K. Roy, “A constraint programming
approach to conflict-aware optimal scheduling of prioritizedcode cloen refactoring,” in Proc. of the 11th International
Working Conference on Source Code Analysis and Manipulation, 2011.
[17] J. Ferrante, K. J. Ottenstein, and J. D. Warren, “The program
dependence graph and its use in optimization,” ACM Transactions on Programming Languages and Systems, vol. 9, no. 3,
pp. 319–349, 1987.
[18] N. Tsantalis and A. Chatzigeorgiou, “Identification of extract
method refactoring opportunities for the decomposition of
methods,” Journal of Systems and Software, vol. 84, no. 10,
pp. 1757–1782, Oct. 2011.
[19] C. K. Roy and J. R. Cordy, “A survey on software clone
detection research,” Technical Report No. 2007-541, Queen’s
University, 2007.
[20] R. Komondoor and S. Horwitz, “Using slicing to identify
duplication in source code,” in 8th International Symposiumon Static Analysis, 2001, pp. 40–56.

[5] N. Juillerat and B. Hirsbrunner, “Toward an implementationof the ”form template method refactoring”,” 7th IEEE International Working Conference on Source Code Analysis andManipulation, pp. 81–90, 2007.

[21] J. Krinke, “Identifying similar code with program dependence
graphs,” In Proc. the 8th Working conference on Reverse
Engineering, pp. 301–309, Oct. 2001.

[6] M. Fowler, K. Beck, J. Brant, W. Opdyke, and D. Roberts,
Refactoring: Improving the Design of Existing Code.
Addison-Wesley Professional, 1999.

[22] Y. Higo and S. Kusumoto, “Code clone detection on specialized pdgs with heuristics,” 15th European Conference on
Software Maintenance and Reengineering, pp. 75–84, 2011.

[7] E. Gamma, R. Helm, R. Johnson, and J. M. Vlissides, Design
Patterns : Elements of Reusable Object-Oriented Software.
Addison-Wesley Professional, 1995.

[23] K. Maruyama and T. Omori, “A security-aware refactoring
tool for java programs,” Proc. of the 4th Workshop on
Refactoring Tools, pp. 22–28, 2011.