% chapter-03. tex
\chapter{Design}

\section{Requirements}
CSeR is a clone-tracking tool. In this work, clones are assumed to be formed
through copy-and-paste operations. A user may copy and paste either a block of
code or an entire file, creating two forms of clone formation. Copying a file is
treated as a special case of copying a block of code.

\textbf{At a high level, CSeR begins with two identical blocks of code. One or
both blocks may later change as a result of user edits. The goal of CSeR is to
track those changes and present them to the user in a clear and readable way.}

One assumption used throughout the editing scenarios is that CSeR does not
respond until the code reaches a consistent state. A consistent state is a state
in which the code has a well-formed AST. Such a state can exist even when the
code has resolution errors. In other words, CSeR remains active when syntax is
valid, even if names cannot yet be resolved.

The difference between resolution and syntax errors is shown in Figure
\ref{resolutionandASTfig}. In the figure, the error marked ``1'' is a resolution
error, where ``IEditorPart'' cannot be resolved to a type. The error marked ``2''
is a syntax error: ``Syntax error, insert ``\}'' to complete Method Body.''

We analyzed the requirements as a set of use cases, listed below. The use cases,
implementation decisions, and later test cases are based on the
Eclipse\footnote{http://www.Eclipse.org} IDE. Most editing scenarios were
collected from our experiments; \cite{texteditingbib,ccp} also contributed to
the list.

\begin{figure}
\centering
\includegraphics{../images/resolutionandAST.png}
\caption{Difference between Resolution errors and Syntax errors}
\label{resolutionandASTfig}
\end{figure}

\subsection{UC001 Consistent Tracking}
\label{uc001}
This use case requires consistent tracking for the same goal, as defined in
Section \ref{goaldef}, even when the goal is reached through different actions,
as defined in Section \ref{actiondef}. Common actions are listed in Table
\ref{actions}.

\begin{figure}
\centering
\includegraphics{../images/ifupdate.png}
\caption{Consistent Tracking Independent of Actions}
\label{ifupdatefig}
\end{figure}

\begin{table}[h]
\caption{\textbf{Set of common Actions}}\vspace{1ex} 
\centering
\begin{tabular}{l l}
\hline \hline
No & Common Actions \\ [0.5ex] \hline
1 & Inserting Characters at the text caret \\ 
2 & Deleting text selection \\ 
3 & Overwriting text selection \\ 
4 & Backspacing over characters \\ 
5 & Undoing \\
6 & Pasting \\ 
7 & Refactoring Tools \\ 
8 & Code Completion \\ [0.5ex] 
\hline
\end{tabular}
\label{actions}
\end{table}

Stated briefly, CSeR should treat the same change consistently regardless of how
the user makes it. For example, in Figure \ref{ifupdatefig}, ``b'' is updated to
``c''. In an editor such as Eclipse, this can be done in at least two ways:
 \begin{enumerate}
 \item Type ``c'' over the character ``b''.
 \item Delete character ``b'' and then type ``c''.
 \end{enumerate}
This use case therefore states that change tracking should be independent of the
editing action. For the example above, CSeR should show the same change, as in
Figure \ref{ifupdatefig}, regardless of how the user made it. This use case
applies to the use cases in Sections \ref{uc002}, \ref{uc003}, \ref{uc004},
\ref{uc005}, \ref{uc006}, \ref{uc007}, \ref{uc008}, \ref{uc009}, \ref{uc010},
and \ref{uc011}.

\subsection{UC002 Simple Name}
\label{uc002}
This use case corresponds to changing identifiers inside a class. The common
modifications involving identifiers are explained in Table \ref{simplename}.

\begin{table}[h]
\caption{\textbf{Set of Name Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Modification involving identifiers & Example \\ [0.5ex] \hline
1 & Creating a name & \\ 
2 & Replacing a name & i ${\rightarrow}$ count  \\ 
3 & Updating a name & foreColor ${\rightarrow}$
bgColor \\ 
4 & Removing a name & \\ 
5 & Splitting a name & fPosition ${\rightarrow}$ f. Position \\ [0.5ex]
\hline
\end{tabular}
\label{simplename}
\end{table}


\subsection{UC003 Statements}
\label{uc003}
This use case corresponds to changing statements \ref{statementsdef} inside a
Block \ref{blockdef}. Common statement modifications are listed in Table
\ref{statementuc}. Updating a statement is not listed in the table because it is
a broad case handled separately. For example, updating the arguments in a method
call is also an update to the surrounding statement.
\begin{table}[h]
\caption{\textbf{Set of Statement Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Modification involving Statements & Example \\ [0.5ex] \hline
1 & Inserting one or more statements & \\ 
2 & Removing one or more statements& i ${\rightarrow}$ count  \\ 
3 & Merging two statements to make a statement & i=expr1;j=expr2; ${ \rightarrow}$i=expr2; \\  
4 & Moving a statement & i++;j++; ${ \rightarrow}$ j++;i++; \\ [0.5ex]
\hline
\end{tabular}
\label{statementuc}
\end{table}

\subsection{UC004 Arguments}
\label{uc004}
This use case corresponds to changing arguments inside a method call. 
Common argument modifications are explained in Table \ref{arguments}.
\begin{table}[h]
\caption{\textbf{Set of Argument Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Modification involving identifiers & Example \\ [0.5ex] \hline
1 & Inserting an additional argument & print(3) ${\rightarrow}$ print(3, 4) \\ 
2 & Removing an argument & print(3, 4) ${\rightarrow}$ print(3)  \\ 
3 & Merging two arguments to make an argument & print(3, 4) ${\rightarrow}$ print(34)\\  [0.5ex]
\hline
\end{tabular}
\label{arguments}
\end{table}

\subsection{UC005 Parameters}
\label{uc005}
This use case corresponds to changing parameters inside a method declaration node.
Common parameter modifications are given in Table \ref{parameters}.

\begin{table}[h]
\caption{\textbf{Set of Parameter Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l}
\hline \hline
No & Modification involving identifiers & Example \\ [0.5ex] \hline 
1 & Inserting an additional parameter & void print(int i) ${\rightarrow}$ void print(int
i, int j) \\ 
2 & Removing an argument &void print(int i) ${\rightarrow}$ void print()  \\ 
3 & Merging two arguments & void print(int i, int j) ${\rightarrow}$
void print(int ij)\\  [0.5ex]
\hline
\end{tabular}
\label{parameters}
\end{table}

\subsection{UC006 Expressions}
\label{uc006}
This is the most general case because expression changes can take many forms. Our
strategy is to support the most common cases. Common expression modifications are
explained in Table \ref{expressionsuc}.

\begin{table}[h]
\caption{\textbf{Set of Expression Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Modification involving identifiers & Example \\ [0.5ex] \hline
1 & Inserting a new expression & k=4; ${\rightarrow}$ k=4*getValue(j); \\ 
2 & Removing an expression & k=var1*var2*var3 ${\rightarrow}$ k=var1*var3 \\ 
3 & String literal  & k= ``Hello World''; ${\rightarrow}$ k=``Test World''\\ 
4 & Number literal  & k=4. 345;${\rightarrow}$k=4. 548;\\ 
5 & Operator & i=i+3;${\rightarrow}$ i=i-3;\\ [0.5ex]
\hline
\end{tabular}
\label{expressionsuc}
\end{table}


\subsection{UC007 Comments}
\label{uc007}
This use case does not mean that the tool must track the text of comments.
Instead, it refers to AST changes caused by introducing or removing comments. The
most common comment-related modifications are given in Table \ref{comments}.

\begin{table}[h]
\caption{\textbf{Set of Comment related Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Comment related modifications & Example \\ [0.5ex] \hline
1 & Commenting out a statement & k=4; ${\rightarrow}$ // k=4; \\ 
2 & Creating annotations &  @Override \\ 
3 & Inside statement & k= a+2; ${\rightarrow}$ k=a+3;//2;\\ [0.5ex]
\hline
\end{tabular}
\label{comments}
\end{table}

\subsection{UC008 Keywords}
\label{uc008}
Keywords are the reserved words in Java. A complete set of Java keywords is
shown in Table \ref{keywords}. Common keyword-related modifications are given in
Table \ref{keywordsuc}.

\begin{table}[h]
\caption{\textbf{Set of Keyword related Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Keyword related modifications & Example \\ [0.5ex] \hline
1 & Inserting a modifier & int k; ${\rightarrow}$ // private int k; \\ 
2 & Inserting an optional keyword &  ``extends''  \\ 
3 & Removing a modifier or optional keyword & \\ [0.5ex]
\hline
\end{tabular}
\label{keywordsuc}
\end{table}

\begin{table}[h]
\caption{\textbf{Set of Keywords in Java 2}} \vspace{1ex}
\centering
\begin{tabular}{|l|l|l|l|}
\hline
abstract& double& int& strictfp\\ 
boolean& else& interface& super \\  
break& extends& long& switch \\  
byte& final& native& synchronized \\ 
case& finally& new& this \\ 
catch& float& package& throw \\  
char& for& private& throws \\ 
class& goto& protected& transient\\
const& if& public& try\\ 
continue& implements& return& void\\ 
default& import& short& volatile \\ 
do& instanceof& static& while \\
\hline
\end{tabular}
\label{keywords}
\end{table}


\subsection{UC009 Fields}
\label{uc009}
Fields in classes correspond to method declarations and field declarations. In
JDT\footnote{http://www.Eclipse.org/jdt}\ref{jdtdef} terminology, these are
called body declarations \ref{bodydeclarationsdef}. A few cases of field-level
edits are discussed in Table \ref{fields}.

\begin{table}[h]
\caption{\textbf{Set of Field level Modifications}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Field level  modifications & Example \\ [0.5ex] \hline
1 & Inserting new field or method & \\ 
2 & Removing one or more  method(s) or field(s) &  \\ 
3 & Modify a field initializer & int k; ${\rightarrow}$ int k=0; \\ [0.5ex]
\hline
\end{tabular}
\label{fields}
\end{table}

\subsection{UC010 Single Statement with Multiple Changes}
\label{uc010}
These cases include scenarios in which UC002 through UC006 occur together or in
some combination. The tool should show the resulting change consistently and
sensibly. A few cases of multiple edits are discussed in Table
\ref{multipleedit}. This use case applies to the use cases in Sections
\ref{uc002}, \ref{uc003}, \ref{uc004}, \ref{uc005}, and \ref{uc006}.

\begin{table}[h]
\caption{\textbf{Single Statement Multiple Changes}} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No & Multiple Edit modifications & Example \\ [0.5ex] \hline
1 & Simple Names & k=var1+var2; ${\rightarrow}$ k=var3+var4; \\ 
2 & Simple Name and Number literal & k=4+var1;${\rightarrow}$ k=234+var2; \\ 
3 & Parameters and Simple Name & k= a+2+this(); ${\rightarrow}$ k=a+2+that(3);//2;\\ [0.5ex]
\hline
\end{tabular}
\label{multipleedit}
\end{table}

\subsection{UC011 Delete Operation}
\label{uc011}
For all delete operations, the tool should log the code that was removed. This
can be an important source of information when the original programmer reviews
the change later or when another programmer reviews it. Delete operations can
come from any applicable use case above. This use case applies to the use cases
in Sections \ref{uc003}, \ref{uc004}, \ref{uc005}, \ref{uc006}, \ref{uc007},
\ref{uc008}, and \ref{uc009}.

\subsection{UC012 Condition In Conditional Or Loop Statements}
\label{uc012}
In this case, expressions are inserted specifically for ``if'' statements,
although the same idea applies to loop statements. This use case differs from
UC003 because the user is not inserting a full statement, but rather an
expression and a keyword, as listed in Table \ref{expressionstmt}. This use case
applies to the use cases in Sections \ref{uc003} and \ref{uc006}.

\begin{table}[h]
\caption{\textbf{Modification Of Conditions In Statements }} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
No &Conditional And Loop Statement Modifications & Example \\ [0.5ex] \hline
1 & Insert Condition checks & k=var1; ${\rightarrow}$ if(var1!=null)
k=var1; \\ 
2 & remove Condition checks &if(var2 $\geq 3$) k=var1;${\rightarrow}$ k=var1; \\ [0.5ex]
\hline
\end{tabular}
\label{expressionstmt}
\end{table}

\begin{table}[h]
\caption{\textbf{Set of all Use Cases}} \vspace{1ex}
\centering
\begin{tabular}{ l l l l }
\hline \hline
No & Use Case ID & Name & Related Use Cases \\ [0.5ex] \hline
1 & UC001 & Consistent Tracking & ALL \\ 
2 & UC002 & Simple Name  &  \\ 
3 & UC003 & Statements  &  \\ 
4 & UC004 & Arguments  &  \\ 
5 & UC005 & Parameters &   \\ 
6 & UC006 & Expressions & \\ 
7 & UC007 & Comments & \\ 
8 & UC008 & Keywords & \\
9 & UC009 & Fields & \\ 
10 & UC010 & Multiple Edit & UC002, UC003, UC004, UC005, UC006 \\ 
11 & UC011 & Delete Operation & UC003, UC009 \\
12 & UC012 & Conditional Statements & UC003, UC006 \\ [0.5ex]
\hline
\end{tabular}
\label{setofallusecases}
\end{table}

\section{Implementation}

The requirements above led to the design and implementation of CSeR. The current
implementation is an Eclipse plug-in. It includes an editor and a simple view.
CSeREditor \ref{CSeReditordef} is a superset of the default Eclipse Java editor
and the CSeR tools. The editor behaves like the default Java editor until the
programmer performs a copy or paste operation, or explicitly activates CSeR.

The plug-in uses the JDT APIs and the plug-ins that ship with the default Eclipse
installation. The only additional external library is used to compute
Levenshtein distance \ref{levenshteindistancedef}; it comes from the
Apache\footnote{http://wwww.apache.org} library. The simple view lists all clones
collected through copy and paste. Clones can be opened in a difference view to
compare them.

\subsection{Trap ``Copy and Paste''}
To manage clones created by copy and paste, CSeR must intercept copy-and-paste
operations performed in the IDE. In the current implementation, the default JDT
copy-and-paste operation is modified to include the tracking feature.

\begin{code}
 \begin{verbatim}
package com. sample;

public class HelloWorldApp {

	public static void main(String[] args) {

		System. out. println("Hello World");

	}
}
\end{verbatim}
 \caption{The Hello World code in Java. }
\label{helloworld}
\end{code}


\paragraph{What information is deduced when code is copied and pasted inside the editor?}

When the code in \ref{helloworld} is copied and pasted, CSeR parses the AST into
smaller AST nodes, as shown below. As mentioned earlier, CSeR must maintain
correspondence between two ASTs. To do this, it compares nodes and determines
which nodes are identical, similar, or different.

Most user changes are made gradually. This allows CSeR to reduce the comparison
to a smaller scope \ref{scopedef}. Instead of comparing the entire AST after
every edit, CSeR usually needs to find only the AST node relevant to the edit and
compare it with the corresponding node in the original file \ref{contextdef}.

CSeR prefers to compare small AST nodes because the comparison is faster.
However, identifying the relevant small AST node requires tracking positions. As
shown in \ref{rocsmain}, each AST node is defined with a position
\ref{positiondef}. Because AST information is heavy compared with a lightweight
position consisting of an offset and a length, CSeR stores and updates positions.
Even when saving changes to a particular AST node in a file, the change is linked
internally to the position of the AST node.

In short, when code is copied and pasted inside the IDE, positions from both the
copied file and the pasted file are added to the CSeR database. For example,
consider copying and pasting the class in \ref{helloworld}. The positions saved
for ``HelloWorldApp'' are shown in \ref{rocsmain}. A corresponding set of
positions is also associated with the pasted file, ``TestWorldApp.''

The criteria for calculating positions are explained in detail in Sections
\ref{secstatements}, \ref{secnodes}, and \ref{secbodydeclarations}. It may seem
surprising that positions must be calculated separately for two files that are
clones. The reason is that they are not always exact textual clones after the IDE
processes the paste. For example, when a Java file named ``HelloWorldApp.java''
is copied to ``TestWorldApp.java,'' the editor changes occurrences of the class
name ``HelloWorldApp'' inside TestWorldApp.java to ``TestWorldApp.'' That
automatic refactoring changes the positions.

\begin{enumerate}
\label{rocsmain}
\item package com. sample;
[offset: 0, length: 19]
\item com[offset: 8, length: 3]
\item sample[offset: 12, length: 6]
\item 
\begin{verbatim} public class HelloWorldApp {
 public static void main(  String[] args){
 System. out. println(``Hello World'');
 }
\end{verbatim}
[offset: 21, length: 130]
\item HelloWorldApp[offset: 34, length: 19]
\item
\begin{verbatim} public static void main(String[] args){
 System. out. println(``Hello World'');
}
\end{verbatim}
[offset: 60, length: 89]
\item main[offset: 79, length: 4]
\item String[] args[offset: 84, length: 13]
\item String[offset: 84, length: 6]
\item args[offset: 93, length: 4]
\item 
 \begin{verbatim}  {
 System. out. println(``Hello World'');
}
\end{verbatim}
\label{rocs}
[offset: 99, length: 50]
\item System. out. println(``Hello World'');
[offset: 109, length: 34]
\item System. out. println(``Hello World'')[offset: 109, length: 33]
\item System[offset: 109, length: 6]
\item out[offset: 116, length: 3]
\item println[offset: 120, length: 7]
\item ``Hello World''[offset: 128, length: 13]
\end{enumerate}

\subsection{Correspondence}

As mentioned above, positions from both the pasted file and the copied file are
added to the database. CSeR tracks the changes that occur in the current file
relative to the original file. Positions from the current and original files are
stored in a bidirectional map. In other words, given a position in the current
file, CSeR can find the corresponding position in the original file. Using the
JDT API, a position can be converted to an AST node when such a node exists.

\textit{
Consider a pair of clones, $O$ (Original) and $C$ (Current) defined in CSeR. Let $p_1$, $p_2$ be
positions such that $p_1 \in O$ and $p_2 \in C$. $Cor$ is a function defined from $O$ to $C$ such that $Cor(p_1) = p_2$ 
and similarly $Cor^{'}$ is a function defined from $C$ to $O$ such that $Cor^{'}(p_2) = p_1$
}

The implementation of the correspondence relationship is shown in Figure
\ref{testworldfig}. CheckPosition is a data structure that contains two
positions: one from the current file and one from the original file.
CheckPositions stores multiple CheckPosition values. Only selected positions are
shown in the figure for clarity.\\

\begin{figure}[h]
\centering
\includegraphics{../images/testworld.png}
\caption{Implementation details of Correspondence Relationship }
\label{testworldfig}
\end{figure}

\paragraph{Why are there position updaters?\ref{positionupdatersdef}}
Position updaters are listeners that respond to position-change events. Whenever
an event changes positions, CSeR's database must be updated with the new
information. Position updaters perform this task for CSeR.

This can be explained with the earlier example. Consider the operations shown in
\ref{operations1} being performed in the newly created file ``TestWorldApp.'' All
operations are assumed to occur in CSeREditor. After the operations, the class
appears as shown in Code \ref{testworld}. The resulting position changes are
explained in Table \ref{correspond}.

\paragraph{Operations} 
\label{operations1}
\begin{enumerate}
\item Select the text ``Hello World'' inside the TestWorldApp file.
\item Replace ``Hello World'' with ``Test World''.
\end{enumerate}
\begin{code}
 \begin{verbatim}
package com. sample;

public class TestWorldApp {

	public static void main(String[] args) {

		System. out. println("Test World");

	}
}
\end{verbatim}
 \caption{The Test World code in Java. }
\label{testworld}
\end{code}

\begin{table}[h]
\caption{\textbf{Corresponding positions of HelloWorldApp and TestWorldApp}} \vspace{1ex}
\centering
\begin{tabular}{ l l l l l }
\hline \hline
No & Position Description & Original & Current & Recent \\ [0.5ex] \hline
1 & Entire package name - package com. sample& 0, 19 & 0, 19 &  0, 19 \\ 
2 & First part package - com& 8, 3 & 8, 3  &  8, 3 \\ 
3 & Second part package - sample& 12, 6 & 12, 6 & 12, 6 \\ 
4 & Class declaration - public class Hello.. & 21, 124 & 21, 123 & 21, 122 \\ 
5 & Class name - HelloWorldApp& 34, 13 & 34, 12 & 34, 12 \\ 
6 & Method declaration - public static voi.. & 54, 89 & 53, 89 & 53, 88 \\ 
7 & Method name - main & 73, 4 & 72, 4 & 72, 4 \\
8 & Parameters - String[] args & 78, 13 & 77, 13 & 77, 13 \\ 
9 & Parameter Type name - String & 78, 6 & 77, 6 & 77, 6 \\ 
10 & Parameter name - args & 87, 4 & 86, 4 & 86, 4 \\ 
11 & Method block - \{ System. out. println(.. & 93, 50 &  92, 50 &  92, 49 \\ 
12 & Expression statement - Syst..World''); & 103, 34 & 102, 34 & 102, 33 \\ 
13 & Method invocation - Syst..elloWorld'') & 103, 33 & 102, 33 & 102, 32 \\ 
14 & Simple name - System& 103, 6 & 102, 6 & 102, 6 \\ 
15 & Simple name - out & 110, 3 & 109, 3 & 109, 3 \\ 
16 & Simple name -println & 114, 7 & 113, 7 & 113, 7 \\ 
17 & String literal - ``Hello World'' & 122, 13 & 121, 13 & 121, 12 \\ [0.5ex]
\hline
\end{tabular}
\label{correspond}
\end{table}

Table \ref{correspond} shows the corresponding positions. The second column gives
a short description of the AST node from the original file. The other three
columns give positions. The third column specifies the position of the node in
the original file, while the fourth and fifth columns give the position of the
same node in the current file at different editing points. The current position
is before any edit, and the recent position is after the operation specified in
\ref{operations1}. A few inferences from the table are given below.


\paragraph{Inferences from Table \ref{correspond}}
\begin{enumerate}
\item The position of package name node `com. sample` remains unchanged in both the current and original
files.
\item The current position in \ref{contextdef}, before any edits, for the class
declaration differs from the position in the original file by one character. This
is due to the internal refactoring that took place inside TestWorldApp during the
copy-and-paste operation, which changed occurrences of ``HelloWorldApp'' to
``TestWorldApp.'' Since the names differ by one character and there is only one
occurrence of ``HelloWorldApp'' inside the class declaration, the length of the
class declaration in the current file differs from the original file by one
character.
\item The current position for the class declaration after the edit also differs
from the class declaration before the edit by one character. This is because the
operation removed ``Hello World'' (11 characters) and inserted ``Test World'' (10
characters), which is equivalent to removing one character.
\end{enumerate}

\subsection{Trap-Edit Approach}
Every file opened inside the IDE editor is represented by a document
\ref{documentdef} object. The document contains positions. Whenever the document
changes, document listeners are activated and receive specific information about
the change, including the position where the change occurred and the nature of
the change, such as insert, delete, or replace.

Algorithm \ref{trapeditalgo} describes how to find the smallest AST containing
the change when the user edits inside a clone. The algorithm does not define
``Compare'' because its implementation varies by node type. For example,
statements cannot be compared in the same way as identifiers. The functions and
external library calls used in the algorithm are explained in
\ref{functionsalgo1}.

\begin{algorithm} 
\caption{TRAPEDIT - Calculate the editing AST}
\label{trapeditalgo} 
\begin{algorithmic}[1]
\REQUIRE positionOfEdit positionsOfCurrentFile positionsOfOriginalFile 
\ENSURE positionsOfCurrentFile, positionsOfOriginalFile not empty
\FORALL{position in positionsOfCurrentFile}
\IF{$strictlycontains$(position, positionofEdit}
\STATE { unFilteredPositions. $add$(position)}
\ENDIF
\ENDFOR
\STATE ASTPosition $\Leftarrow smallestPosition $(unFilteredPositions) 
\STATE currentNode $\Leftarrow getASTNode$(currentFile, ASTPosition)
\STATE originalPosition $\Leftarrow findImageInCurrentFile$(ASTPosition)
\STATE originalNode $\Leftarrow getASTNode$(parentFile, parentPosition)
\IF{$getType$(currentNode) is Bodydeclaration}
\STATE $X \Leftarrow 1$
\ELSE[$getType$(currentNode) is Block]
\STATE $X \Leftarrow 2$
\ELSE
\STATE $X \Leftarrow 3$
\ENDIF
\STATE $Compare$(currentNode, originalNode, $X$)
\end{algorithmic}
\end{algorithm}

\begin{table}[h]
\caption{\textbf{Functions Used In TRAPEDIT Algorithm }} \vspace{1ex}
\centering
\begin{tabular}{ l l l l }
\hline \hline
Function Name & Input & Output & Description \\ [0.5ex] \hline
$Contains$& Position1, Position2 &  true or false & Is Position2\\
& & & inside Position1 \\ 
$smallestPosition$ & List of positions & Position  &  Find the smallest\\
& & & Position  \\ 
$getASTnode$ & File, Position & AST node & Find AST node\\ 
& & & from Position  \\ 
$FindImageInCurrentFile$ & Position & Position & Find corresponding\\
& & & original position \\
$getType$ & AST node & Type & Return the \\
& & & type of the AST node \\ [0.5ex]
\hline
\end{tabular}
\label{functionsalgo1}
\end{table}

\paragraph{Understanding the TRAPEDIT Algorithm}

Some editing scenarios are explained below to clarify how the algorithm works
using the information in Figure \ref{testworldfig}. Only selected positions are
shown for clarity.

\begin{figure}
\centering
\includegraphics{../images/testworldmethodinsert.png}
\caption{Understanding TRAPEDIT Algorithm with TestWorldApp }
\label{testworldinsertfig}
\end{figure}
\begin{enumerate}

\item
Consider adding a space before the ``Test World'' string. The position of the
edit is ``121, 1.'' Lines 1-5 of the algorithm add all four containing positions
to unFilteredList because each one contains the edit position. In the next step,
line 6 calculates the smallest position. This position is not ``121, 12,'' but
``121, 13,'' because the position updaters in CSeREditor have already updated
the database.

Position updaters update all occurrences of ``121, 12'' to ``121, 13''
throughout the CSeR database. Eclipse calls position updaters before document
listeners, so all positions observed by document listeners are already updated.
Once the smallest position is known, CSeR calculates the current node, ``Test
World.'' Then, using Table \ref{correspond}, it calculates the original position
and the original node.

Once both nodes are known, CSeR checks the node type. In this case, the type is
neither a block nor a type declaration, so control flows to the default case
where the type is ``StringLiteral.'' A message is calculated using the current
node and original node, and then displayed in the editor using annotation
markers. More detail about this comparison is provided in Section
\ref{secnodes}. Figure \ref{testworldinsertfig}, change 1, shows the
representation of this change in CSeREditor.
\item

Consider pasting ``doA();'' after the print statement inside the method. Lines
1-5 of the algorithm add two positions to unFilteredList: the block node and the
class declaration node. These are the only nodes that contain the edit position.
The smallest one, the block node ``92, 49,'' is selected. The current block node
and the original block node are then calculated as described above and passed to
the appropriate comparator. More detail about this comparison is provided in
Section \ref{secstatements}. Figure \ref{testworldinsertfig}, change 2, shows
the representation of this change in CSeREditor.
\item

Consider pasting a declaration for ``doA'' after the ``main'' method. Lines 1-5
of the algorithm add only one position to unFilteredList: the class declaration
node. It is the only node that contains the edit position, so it is also the
smallest node. The class declarations of TestWorldApp and HelloWorldApp are then
passed to the appropriate comparator. More detail about this comparison is
provided in Section \ref{secbodydeclarations}. Figure \ref{testworldinsertfig},
change 3, shows the representation of this change in CSeREditor. Adding a field
is handled similarly.
\end{enumerate}

\textbf{Using the TRAPEDIT algorithm, every edit operation results in an anchor
AST, which can be a TypeDeclaration, a Block, or another node. When the anchor
AST is a TypeDeclaration, CSeR compares body declarations. When the anchor AST is
a Block, CSeR compares statements. In all other cases, CSeR considers expression
nodes.}

The comparison approaches for statements, body declarations, and expressions are
explained in the following sections.

\subsection{Statements}
\label{secstatements}
By design, when the anchor AST, the smallest AST containing the edit position, is
a Block node, CSeR compares statements. Returning to the HelloWorldApp example,
consider adding a new statement, ``int i=0;,'' as the first line inside the main
method.

Insertion can be performed by pasting the entire line, typing character by
character, or combining the two. As a design decision, CSeR does not show any
change until the AST is complete. For example, while the user is typing ``int
i=0;,'' CSeR does not calculate changes until the final semicolon is typed.
Position updaters are not AST-aware, however, so they continue to maintain
position correspondence for every edit.

Once the AST is complete, CSeR starts processing. It first fetches the block from
the current file, finds the corresponding AST (Listing \ref{rocs}) in the other
clone, and then compares the two. If they do not match, CSeR shows a change. In
the TestWorldApp example, the block in the current file is shown in Code
\ref{testworldblock}. The question in this section is therefore how to compare
two AST nodes of type Block: \ref{testworldblock} and \ref{rocs}.


\begin{code}
 \begin{verbatim}
 {
 int i=0;
 System. out. println("Test World");
 }
\end{verbatim}
 \caption{AnchorAST after inserting a new statement in TestWorldApp. }
\label{testworldblock}
\end{code}

\textbf{For Block comparison, CSeR breaks each Block into non-overlapping
statements and expressions, and then compares them individually.}

\paragraph{How to find non-overlapping statements and expressions in a Block}
Using statements exactly as defined by the JLS3
\footnote{http://java.sun.com/docs/books/jls/third\_edition/html/j3IX.html}
grammar can produce overlapping statements, which the current design does not
support. CSeR therefore uses visitors that visit statement nodes and return a
list of non-overlapping statements and expressions. The nodes visited by the
Statement visitor are listed in Table \ref{statementstbl}. For example, only the
expressions are visited for a ``ForStatement,'' because the statements inside the
``for'' loop are visited by other visitor nodes. Figure \ref{forloopnodesfig}
shows how a simple for loop is parsed by the Statement visitor.
 
\begin{figure}[h]
\centering
\includegraphics{../images/forloopnodes.png}
\caption{Statement visitor visiting a for loop }
\label{forloopnodesfig}
\end{figure}

\begin{table}[h]
\caption{\textbf{Statements given from the visitor for TestWorldApp}} \vspace{1ex}
\centering
\begin{tabular}{ l l }
\hline \hline
Original File & Current File \\ [0.5ex] \hline
System. out. println(``Test World''); & int i=0; \\ 
& System. out. println(``Test World''); \\ [0.5ex] \hline
\end{tabular}
\label{statementsbreak}
\end{table}

The output of TestWorldApp and HelloWorldApp after the StatementVisitor is shown
in Table \ref{statementsbreak}. Again, CSeR does not convert the positions to AST
nodes for storage; it keeps them as positions for further processing. The table
shows AST nodes only for clarity.

\begin{table}[h]
\caption{\textbf{Statements visited by Statement Visitor}} \vspace{1ex}
\centering
\begin{tabular}{ l l l l }
\hline \hline
No & Statement Type & Statement & Expression \\ [0.5ex] \hline
 1 	 & ReturnStatement &$\surd$&  \\ 
 2	 & ThrowStatement &$\surd$& \\ 
 3	 & BreakStatement &$\surd$& \\ 
 4	 & ContinueStatement &$\surd$& \\ 
 6	 & ExpressionStatement &$\surd$& \\ 
 7	 & AssertStatement &$\surd$& \\ 
 8	 & VariableDeclarationStatement &$\surd$& \\
 9	 & TypeDeclarationStatement &$\surd$& \\ 
 10	 & ConstructorInvocation &$\surd$& \\ 
 11	 & SuperConstructorInvocation &$\surd$& \\ 
 12	 & ForStatement & & $\surd \surd \surd$ \\ 
 13	 & EnhancedForStatement & & $\surd \surd$ \\ 
 14	 & WhileStatement & & $\surd$ \\ 
 15	 & DoStatement & & $\surd$ \\
 16	 & SwitchStatement & & $\surd$ \\ 
 17	 & LabeledStatement & & $\surd$ \\ [0.5ex] \hline
\end{tabular}
\label{statementstbl}
\end{table}

\paragraph{Initial deleted and inserted node positions}

\begin{figure}[ht]
\centering
\includegraphics[angle=0,width=10cm]{../images/correspondence.png}
\caption{Correspondence Relation}
\label{correspondencefig}
\end{figure}
\textit{
In Figure \ref{correspondencefig}, let $O$ and $C$ represent sets of positions
such that ${p_1}^{'}, {p_2}^{'}, \cdots, {p_N}^{'}$ are positions in the
current file and $p_1, p_2, \cdots, p_M$ are positions in the original file.
Let $P_c$ and $P_o$ be the positions of the current and original Blocks,
respectively.  $P_c\subset p^{'}$ and $P_o \subset p$.
}
\textit{
An initial inserted node position is any position $p_i$ for which
$Cor^{'}(p_i^{'})$, the inverse correspondence function, is not defined.
Similarly, an initial deleted node position is any position $p_j$ for which
$Cor(p_j)$, the correspondence function, is not defined.
}

\begin{table}[hb]
\caption{\textbf{Functions Used In CMPSTATEMENTS Algorithm }} \vspace{1ex}
\centering
\begin{tabular}{ l l l }
\hline \hline
Function Name & Input  & Description \\ [0.5ex] \hline
$getStatementPositions$& ASTnode &find statements inside ASTnode \\ 
$findImagesInCurrentFile$ & PositionList &  Find corresponding PositionList  \\ 
$diff$ &two PositionLists & $(List1 \cup List2) - (List1 \cap List2)$  \\ 
$IsExist$ &Position & returns whether the position really exist \\ [0.5ex]
\hline
\end{tabular}
\label{functionsalgo2}
\end{table}


\begin{algorithm} 
\caption{CMPSTATEMENTS - Comparing statements}
\label{statementcmpalgo} 
\begin{algorithmic}[1]
\REQUIRE currentBlock originalBlock 
\ENSURE currentBlock, originalBlock not null
\STATE currentPositions $\Leftarrow getStatementPositions $(currentBlock) 
\STATE originalPositions $\Leftarrow getStatementPositions $(originalBlock) 
\STATE orgPosWithCorr $\Leftarrow findImagesInCurrentFile$(originalPositions)
\STATE finalPositions $\Leftarrow diff$(originalPositions, orgPoswithCorr)
\FORALL{position in finalPositions}
\IF{$IsExist$(position) }
\PRINT ``$position$ may be deleted''
\STATE { tmpDeletedPositions. $add$(position)}
\ELSE
\PRINT ``$position$ is new''
\STATE { tmpInsertedPositions. $add$(position)}
\ENDIF
\ENDFOR
\STATE PROCESSINSDELNODES(tmpDeletedPositions, tmpInsertedPositions)
\end{algorithmic}
\end{algorithm}
 
Algorithm CMPSTATEMENTS \ref{statementcmpalgo} describes the statement comparison
algorithm. Lines 1-2 fetch the statement positions from both the current file and
the original file. Line 3 finds the corresponding position of each original
position. Line 4 computes the difference between those positions and the original
positions. Finally, ``finalPosition'' may contain two types of positions: those
that exist in the original positions but not in the current positions, which are
deleted positions, and those that exist in the current positions but not in the
original positions, which are newly inserted positions. CSeR marks these as
initial inserted and deleted nodes. The functions used in CMPSTATEMENTS are
explained in Table \ref{functionsalgo2}.

\paragraph{Why are inserted and deleted positions in Algorithm CMPSTATEMENTS not final?}
Initial inserted and deleted node positions are positions without
correspondence. As shown in Figure \ref{correspondencefig}, ${P_3}^{'}$ and
$P_0$ do not have corresponding positions on the other side. This can happen
when a node is inserted or removed, but it can also happen in other situations.
For example, it can happen during an undo operation.

Consider a statement that is removed and then typed back as the same statement.
When an AST node is removed from a file, the position linked to it is removed as
well. The associated position updaters are also removed. Typing or pasting that
AST back does not restore either the original position or the position updaters.
Therefore, a previously deleted node can later appear as an inserted node.

\begin{algorithm}[h] 
\caption{PROCESSINSDELNODES- Process Insert/Delete Nodes}
\label{statementcmpalgoctnd} 
\begin{algorithmic}[1]
\REQUIRE tmpInsertedPositions tmpDeletedPositions 
\ENSURE tmpInsertedPositions, tmpDeletedPositions is not empty 
\STATE {finalInsertedPositions $\Leftarrow$ tmpInsertedPositions}
\STATE {finalDeletedPositions $\Leftarrow$ tmpDeletedPositions}
\FORALL{position1 in tmpInsertedPositions}
	\FORALL{position2 in tmpDeletedPositions}
		\IF{AREMATCH(position1, position2) }
			\PRINT ``$positions$ may be moved or the undo''
			\IF{AREIDENTICAL(position1, position2)}
			\PRINT ``position1 is same as position2- Undo Operation''
			\ELSE
			\PRINT ``position1 is moved to position2''
			\STATE {remove $\Leftarrow true$}
			\ENDIF
		\ELSE[{ISUPDATE(position1, position2)}]
		\PRINT ``position2 is updated to position1''
		\STATE {remove $\Leftarrow true$}
		\ENDIF
		\IF{remove}
		\STATE {finalDeletedPositions. $remove$(position2)}
		\STATE {finalInsertedPositions. $remove$(position1)}
		\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

When deleted nodes are inserted back, inserted and deleted nodes must be
processed further to determine whether they are final inserted or deleted nodes.
Algorithm PROCESSINSDELNODES performs this step for CSeR.

PROCESSINSDELNODES starts by assuming that the final deleted and inserted
positions are the same as the temporary deleted and inserted positions. It then
iterates over insertedPositions and, for each inserted position, iterates over
deletedPositions. For each pair, it checks whether the inserted node and deleted
node match (line 5). The matching algorithm, Algorithm \ref{arematchalgo}, uses
the default ASTMatcher shipped with JDT. Once a match is found, the nodes may be
either identical or similar.

\begin{algorithm}[h] 
\caption{AREMATCH - Utility for AST node match}
\label{arematchalgo} 
\begin{algorithmic}[1]
\REQUIRE Position1, Position2, File1, File2
\ENSURE Position1, Position2, File1, File2  not $NULL$
\STATE {ASTnode1 $\Leftarrow$ getASTNode(File1, Position1)}
\STATE {ASTnode2 $\Leftarrow$ getASTNode(File2, Position2)}
\IF{$defaultJDTASTMatch$(ASTnode1, ASTnode2)}
\PRINT ``Nodes match''
\ELSE
\PRINT ``Nodes do not match''
\ENDIF
\end{algorithmic}
\end{algorithm}

\paragraph{What are ``identical'' statements?}
To define identical nodes in CSeR, we introduce two additional terms for
statement comparison: upper statement and lower statement. The upper statement is
the statement immediately above the current statement, and the lower statement is
the statement immediately below it. For example, ``int i=0;'' is the upper
statement for ``System.out.println(``Test World'');,'' and the lower statement
for that print statement is null. Similarly, the upper statement of ``int i=0;''
is null.

CSeR considers a statement in the current file to be identical to a statement in
the original file if the statements match and their neighbors also match.
Matching neighbors means that the upper statement of the current statement
matches the upper statement of the original statement, and the same condition
holds for the lower statements. This is explained in Algorithm
\ref{areidenticalalgo}. In short, statement-level comparison considers the order
in which statements occur. Undo operations are a common case of identical nodes.

\textbf{CSeR assumes that a statement in the current file with no correspondence
is identical to another statement in the original file with no correspondence if
the statements match and have matching neighbors.}

\begin{algorithm}[h] 
\caption{AREIDENTITCAL - Checking Identical node, Undo Operations }
\label{areidenticalalgo} 
\begin{algorithmic}[1]
\REQUIRE Position1, Position2, PositionList1, PositionList2
\ENSURE Position1, PositionList1 $\in$ originalFile $AND$ Position2, PositionList2 $\in$
currentFile
\IF{AREMATCH($before$(position1), $before$(position2)) }
\IF{AREMATCH($after$(position1), $after$(position2)) }
\PRINT ``Nodes are identical''
\ENDIF
\ELSE
\PRINT ``Nodes are not identical''
\ENDIF
\end{algorithmic}
\end{algorithm}

\paragraph{What are ``moved statements''?} 
If a newly inserted statement in the current file matches a deleted statement in
the original file but is not identical, then the statements occur in different
orders in the current and original files. CSeR treats this as a move operation.
Algorithm PROCESSINSDELNODES \ref{statementcmpalgoctnd} detects moved statements
for CSeR.

\begin{algorithm}[h] 
\caption{ISUPDATE - Checking the current Position is an update of Original Position }
\label{isupdatealgo} 
\begin{algorithmic}[1]
\REQUIRE Position1, Position2, currentFile, OriginalFile
\ENSURE Position1, Position2 not $NULL$
\STATE {ASTnode1 $\Leftarrow$ getASTNode(Position1, currentFile)}
\STATE {ASTnode2 $\Leftarrow$ getASTNode(Position2, originalFile)}
\IF{$getType$(ASTnode1)$==$ $getType$(ASTnode2) }
\IF{LevenshteinDistance(ASTnode1, ASTnode2) $\leq$ CONFIGVALUE} 
\PRINT ``Position1 is an update of Position2 ''
\ENDIF
\ELSE
\PRINT ``Position1 is not an update of Position2''
\ENDIF
\end{algorithmic}
\end{algorithm}

\paragraph{What are ``updated'' statements?}
If a newly inserted statement in the current file has the same type as a deleted
statement, and its Levenshtein distance \ref{levenshteindistancedef} is below the
configured value, but the two statements do not match, then CSeR defines it as an
updated statement. Algorithm PROCESSINSDELNODES \ref{statementcmpalgoctnd}
detects updated statements for CSeR.


\paragraph{An example with statement level changes}
This example is taken from the JDT UI \footnote{http://www.eclipse.org/jdt/ui/index.php} project. The
classes JavaDocContext and JavaContext appear to be very similar. We used CSeR to
modify a method named ``canEvaluate'' in JavaDocContext so that it matched the
corresponding method in JavaContext. The changes that appear in CSeR are shown in
Figure \ref{movechangesfig}. The change marked ``3'' shows the insertion of a
new ``IfStatement,'' the change marked ``2'' shows a move operation, and the
change marked ``1'' shows a delete operation.

\begin{figure}
\centering
\includegraphics{../images/statementwithchanges.png}
\caption{Statement changes in CSeR Editor using ``canEvaluate'' method in JavaContext and JavaDocContext}
\label{movechangesfig}
\end{figure}

\subsection{Body Declarations}
\label{secbodydeclarations}
In the TRAPEDIT algorithm, when the anchor AST is a TypeDeclaration node, CSeR
must compare body declarations \ref{bodydeclarationsdef}. Consider introducing a
change in TestWorldApp. For Code \ref{testworldnewfield}, the anchor AST is the
entire TestWorldApp class.

As with statements, insertion can be performed by pasting a code block or typing
it. CSeR does not show any change until the AST is complete. For example, while
typing ``private int i=0;,'' CSeR does not calculate a change until the final
semicolon is typed. Position updaters still operate for every edit, regardless
of whether the edit occurs in a TypeDeclaration, a Block, or another node.

Once the AST is complete, CSeR starts processing. It first fetches the class
declaration from the current file, finds the corresponding AST from the original
file, and compares the two. If they do not match, CSeR shows a change.

\begin{code}
 \begin{verbatim}
package com. sample;

public class TestWorldApp {

	public static void main(String[] args) {

		System. out. println("Test World");

	}
	private int i=0;//inserted new line.
}
\end{verbatim}
 \caption{The Test World  with new field. }
\label{testworldnewfield}
\end{code}

Once CSeR has the type declaration, it must find the body declarations that occur
inside the class but outside methods. It then performs a field-level comparison
to find the difference. An important distinction from statement comparison is the
order of fields. The order of fields does not change the meaning of a Java class.
Another difference is how fields are calculated in the two classes. Here too,
CSeR needs non-overlapping field positions.

\paragraph{How to find body declarations}

According to JLS3, body declarations in JDT can be any of the nodes listed in
Table \ref{bodydeclarations}. CSeR uses visitors that visit these nodes. The node
from the current file and the corresponding node from the clone are both passed
through the visitor, which returns the list of body declarations. The output of
TestWorldApp is shown in Code \ref{bodydeclarationsbreak}.

\begin{table}[h]
\caption{\textbf{Body declarations specified by JLS3 grammar}} \vspace{1ex}
\centering
\begin{tabular}{ l l }
\hline \hline
No & Statement Type \\ [0.5ex] \hline
 1 & ClassDeclaration \\  
 2 & InterfaceDeclaration \\ 
 3 & EnumDeclaration \\  
 4 & MethodDeclaration \\  
 5 & ConstructorDeclaration \\  
 6 & FieldDeclaration \\ 
 7 & Initializer \\  
 8 & EnumConstantDeclaration \\  
 9 & AnnotationTypeDeclaration \\ 
 10 & AnnotationTypeMemberDeclaration \\ [0.5ex] \hline
\end{tabular}
\label{bodydeclarations}
\end{table}


\begin{code}
\caption{Body declarations given from the visitor for TestWorldApp}
\begin{enumerate}
\item
\begin{verbatim}
public static void main(String[] args){
 System. out. println("Test World");
 }
 \end{verbatim}
 \item private int i=0;
 \end{enumerate}
\label{bodydeclarationsbreak}
\end{code}

\paragraph{How are body declarations compared?}
As mentioned earlier, body declarations \ref{bodydeclarationsdef} differ from
statements because they do not necessarily have to be neighbors to be identical.
The same CMPSTATEMENTS algorithm can be used to find the initial inserted and
deleted fields, but after those fields are calculated, the PROCESSINSDEL
algorithm must be slightly modified by removing the neighbor-checking step.
Apart from this change, body declarations follow the same processing as
statements.

Algorithm \ref{statementcmpalgoctnd} (PROCESSINSDELNODES) is slightly modified
to manage body declarations and is named PROCESSINSDELBDNODES
\ref{bodydeclarationsctnd}.

\begin{algorithm} 
\caption{INSDELBDDLS - Comparing Body Declarations}
\label{bodydeclarationsctnd} 
\begin{algorithmic}[1]
\REQUIRE tmpInsertedPositions tmpDeletedPositions 
\ENSURE tmpInsertedPositions, tmpDeletedPositions is not empty 
\STATE {finalInsertedPositions $\Leftarrow$ tmpInsertedPositions}
\STATE {finalDeletedPositions $\Leftarrow$ tmpDeletedPositions}
\FORALL{position1 in tmpInsertedPositions}
	\FORALL{position2 in tmpDeletedPositions}
		\IF{AREMATCH(position1, position2) }
			\PRINT ``position1 is same as position2- Undo Operation''
			\STATE {finalDeletedPositions. $remove$(position2)}
			\STATE {finalInsertedPositions. $remove$(position1)}
		\ENDIF
	\ENDFOR
\ENDFOR
\end{algorithmic}
\end{algorithm}

\paragraph{An example with BodyDeclaration changes}
This example is also taken from the JDT UI
\footnote{http://www.eclipse.org/jdt/ui/index.php} project. The classes
NewAnnotationWizardPage and NewClassWizardPage appear to be very similar. We used
CSeR to modify the body declarations inside NewClassAnnotationWizardPage to
convert it to NewAnnotationWizardPage. The changes that appear in CSeR are shown
in Figure \ref{bodydeclarationsfig}. The change marked ``2'' shows the insertion
of a new field, and the change marked ``1'' shows a delete operation. The deleted
nodes are shown when the mouse hovers over the marker.

\begin{figure}
\centering
\includegraphics{../images/bodydeclarations.png}
\caption{BodyDeclaration changes in CSeR Editor using NewClassWizardPage and NewAnnotationWizardPage }
\label{bodydeclarationsfig}
\end{figure}


\begin{figure}
\centering
\includegraphics{../images/nodes.png}
\caption{Node changes in CSeR Editor using FieldTag and FileNameTag }
\label{nodesfig}
\end{figure}

\subsection{Nodes}
\label{secnodes}
This is the default case when the anchorAST is neither TypeDeclaration nor Block.

A careful analysis shows that in this case, the anchor AST is one of the values
listed in Table \ref{nodestbl}. For Code \ref{testworldupdate}, it is a
StringLiteral node. In this case, insertion can again be performed either by
pasting a code block or by typing it. CSeR assumes that the developer eventually
brings the AST back to a correct state.

Once the AST is complete, CSeR starts processing. It first fetches the node from
the current file, here ``Test World,'' and then finds the corresponding AST from
the other clone, here ``Hello World.'' Finally, it compares the two. Since they
are not the same, CSeR shows a change.

\paragraph{What if the user is editing in the margin of an ASTNode?}
In this case, the TRAPEDIT algorithm returns the parent of the edited node. In
the example above, it returns ``System.out.println("Test World").'' CSeR then
splits this node into smaller units, in the same way it divides a Block into
statements, and processes each unit separately.

\begin{code}
\begin{verbatim}
package com. sample;

public class TestWorldApp {

	public static void main(String[] args) {

		System. out. println("Test World");
		// String literal changed from Hello World to Test World


	}
	private int i=0;//inserted new line.
}
\end{verbatim}
 \caption{The Test World  with an update. }
\label{testworldupdate}
\end{code}


\paragraph{How to find nodes}
As mentioned earlier, CSeR uses visitors for the nodes specified in Table
\ref{nodestbl}. Passing the nodes through these visitors produces the smaller
non-overlapping units that must be compared.

\begin{table}[h]
\caption{\textbf{Nodes as a result of Test Cases by JLS3 }} \vspace{1ex}
\centering
\begin{tabular}{ l l }
\hline \hline
No & Node Type \\ [0.5ex] \hline
 1	 & ImportDeclaration \\ 
 2	 & MethodInvocation \\  
 3	 & PackageDeclaration \\ 
 4	 & SimpleName \\ 
 5	 & SingleVariableDeclaration \\
 6	 & StringLiteral \\
 7	 & NumberLiteral \\ 
 8	 & VariableDeclarationFragment \\
 9   & ArrayInitializer \\ [0.5ex] \hline
\end{tabular}
\label{nodestbl}
\end{table}

\paragraph{How are nodes compared?}

Node comparison is implemented in the same way as Block comparison, with one
difference in the implementation of the $diff$ function. Consider the example
above, where the user modifies the boundary of `System.out.println(``Test
World'').' There is already a change at ``Test World.'' If CSeR used the same
$diff$ implementation, that node would not appear in the list of initial deleted
or inserted nodes because it already has correspondence. Therefore, the important
change in node comparison is the modified $diff$ implementation. Algorithm
\ref{nodesdiffalgo} shows how this is done. In the algorithm, the function
$undid$ returns all nodes that have correspondence on both sides.

\begin{algorithm} 
\caption{NODEDIFF - diff Implementation for nodes}
\label{nodesdiffalgo} 
\begin{algorithmic}[1]
\REQUIRE currentPositions originalPosWithCorr originalPositions 
\STATE initialdeleteInsertPositions $\Leftarrow diff $(currentPositions,orgPoswithCorr) 
\STATE positionWithCorrespondence $\Leftarrow undid$(currentPositions,orgPosWithCorr) 
\FORALL{position in positionWithCorrespondence}
\IF{$\not match$(getASTNode(currentPositions(position),getASTNode(originalPositions(position)))) }
\PRINT ``$position$ has to included ''
\STATE { initialdeleteInsertPositions. $add$(position)}
\ENDIF
\ENDFOR
\STATE RETURN initialdeletePositions
\end{algorithmic}
\end{algorithm}

\paragraph{An example with Node changes}
This example is also taken from the Javalobby Community Platform project 
\footnote{http://www.ohloh.net/p/ui/gotjava}. The classes FieldTag and
FileNameTag appear to be very similar. We used CSeR to modify the only different
node inside FieldTag to convert it to FileNameTag. The changes that appear in
CSeR are shown in Figure \ref{nodesfig}. The change marked ``1'' shows the node
update, and the old node is shown when the mouse hovers over the marker.

\section{Sample Scenarios}
\subsection{Conditional Statements}
Five different cases of conditional statements are shown below.

\begin{figure}
\centering
\includegraphics{../images/case1.png}
\caption{Conditional Statement Case 1 : Update Expression}
\label{expressionstmtcase1}
\end{figure}

\begin{figure}
\centering
\includegraphics{../images/case2.png}
\caption{Conditional Statement Case 2 : Insert condition}
\label{expressionstmtcase2}
\end{figure}

\begin{figure}
\centering
\includegraphics{../images/case3.png}
\caption{Conditional Statement Case 3 : Remove Condition}
\label{expressionstmtcase3}
\end{figure}

\begin{figure}
\centering
\includegraphics{../images/ifdelete.png}
\caption{Conditional Statement Case 4 : Delete An If Statement}
\label{ifdeletefig1}
\end{figure}

\begin{figure}
\centering
\includegraphics{../images/insertifstmt.png}
\caption{Conditional Statement Case 5 : Inserting A Complete If Statement}
\label{insertifstmtfig}
\end{figure}

\subsection{Arguments}
Parameters and arguments are treated the same way. An example of a parameter
change is shown in Figure \ref{argumentsfig}.

\begin{figure}
\centering
\includegraphics{../images/arguments.png}
\caption{Inserting new arguments }
\label{argumentsfig}
\end{figure}

\begin{figure}
\centering
\includegraphics{../images/flattenlist.png}
\caption{Flattening arguments  }
\label{flattenlistfig}
\end{figure}

\subsection{Array Initializer}
An example of modifying an array initializer statement is shown in Figure
\ref{arrayinitfig}.

\begin{figure}
\centering
\includegraphics{../images/arrayinit.png}
\caption{Modifying an array initializer}
\label{arrayinitfig}
\end{figure}

\subsection{Comments}
An example of commenting code is shown in Figure \ref{commentsfig}.

\begin{figure}
\centering
\includegraphics{../images/comments.png}
\caption{Commenting source code}
\label{commentsfig}
\end{figure}
