Thesis: changing todoin behavior

[ifi-stolz-refaktor.git] / thesis / master-thesis-erlenkr.tex

\documentclass[USenglish]{ifimaster}
\usepackage{import}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc,url}
\usepackage{lmodern} % using Latin Modern to be able to use bold typewriter font
\urlstyle{sf}
\usepackage{listings}
\usepackage{tabularx}
\usepackage{tikz}
\usepackage{tikz-qtree}
\usetikzlibrary{shapes,snakes,trees,arrows,shadows,positioning,calc}
\usepackage{babel,textcomp,csquotes,ifimasterforside,varioref}
\usepackage[hidelinks]{hyperref}
\usepackage{cleveref}
\usepackage[style=alphabetic,backend=bibtex]{biblatex}
\usepackage{amsthm}
\usepackage{graphicx}
% use 'disable' before printing:
\usepackage[]{todonotes}
\usepackage{xspace}
\usepackage{he-she}
\usepackage{verbatim}
\usepackage{minted}
\usepackage{multicol}
\usemintedstyle{bw}
\usepackage{perpage} %the perpage package
\MakePerPage{footnote} %the perpage package command

\theoremstyle{definition}
\newtheorem*{wordDef}{Definition}

\graphicspath{ {./figures/} }

\newcommand{\citing}[1]{~\cite{#1}}
\newcommand{\myref}[1]{\cref{#1} on \cpageref{#1}}

\newcommand{\definition}[1]{\begin{wordDef}#1\end{wordDef}}
\newcommand{\see}[1]{(see \myref{#1})}
\newcommand{\See}[1]{(See \myref{#1}.)}
\newcommand{\explanation}[3]{\noindent\textbf{\textit{#1}}\\*\emph{When:} 
#2\\*\emph{How:} #3\\*[-7px]}

%\newcommand{\type}[1]{\lstinline{#1}}
\newcommand{\code}[1]{\texttt{\textbf{#1}}}
\newcommand{\type}[1]{\code{#1}}
\newcommand{\typeref}[1]{\footnote{\type{#1}}}
\newcommand{\typewithref}[2]{\type{#2}\typeref{#1.#2}}
\newcommand{\method}[1]{\type{#1}}
\newcommand{\methodref}[2]{\footnote{\type{#1}\method{\##2()}}}
\newcommand{\methodwithref}[2]{\method{#2}\footnote{\type{#1}\method{\##2()}}}
\newcommand{\var}[1]{\type{#1}}

\newcommand{\refactoring}[1]{\emph{#1}}
\newcommand{\ExtractMethod}{\refactoring{Extract Method}\xspace}
\newcommand{\MoveMethod}{\refactoring{Move Method}\xspace}
\newcommand{\ExtractAndMoveMethod}{\refactoring{Extract and Move Method}\xspace}

\newcommand\todoin[2][]{\todo[inline, caption={#2}, #1]{
\begin{minipage}{\textwidth-4pt}#2\end{minipage}}}

\title{Refactoring}
\subtitle{An essay}
\author{Erlend Kristiansen}

\bibliography{bibliography/master-thesis-erlenkr-bibliography}

  % UML comment in TikZ:
  % ref: https://tex.stackexchange.com/questions/103688/folded-paper-shape-tikz
\makeatletter
\pgfdeclareshape{umlcomment}{
  \inheritsavedanchors[from=rectangle] % this is nearly a rectangle
  \inheritanchorborder[from=rectangle]
  \inheritanchor[from=rectangle]{center}
  \inheritanchor[from=rectangle]{north}
  \inheritanchor[from=rectangle]{south}
  \inheritanchor[from=rectangle]{west}
  \inheritanchor[from=rectangle]{east}
  % ... and possibly more
  \backgroundpath{% this is new
  % store lower right in xa/ya and upper right in xb/yb
  \southwest \pgf@xa=\pgf@x \pgf@ya=\pgf@y
  \northeast \pgf@xb=\pgf@x \pgf@yb=\pgf@y
  % compute corner of ‘‘flipped page’’
  \pgf@xc=\pgf@xb \advance\pgf@xc by-10pt % this should be a parameter
  \pgf@yc=\pgf@yb \advance\pgf@yc by-10pt
  % construct main path
  \pgfpathmoveto{\pgfpoint{\pgf@xa}{\pgf@ya}}
  \pgfpathlineto{\pgfpoint{\pgf@xa}{\pgf@yb}}
  \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yb}}
  \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@yc}}
  \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@ya}}
  \pgfpathclose
  % add little corner
  \pgfpathmoveto{\pgfpoint{\pgf@xc}{\pgf@yb}}
  \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yc}}
  \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@yc}}
  \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yc}}
  }
}
\makeatother

\tikzstyle{comment}=[%
  draw,
  drop shadow,
  fill=white,
  align=center,
  shape=document,
  minimum width=20mm,
  minimum height=10mm,
  shape=umlcomment,
  inner sep=2ex,
  font=\ttfamily,
]

\begin{document}
\ififorside
\frontmatter{}


\chapter*{Abstract}
\todoin{\textbf{Remove all todos (including list) before delivery/printing!!!  
Can be done by removing ``draft'' from documentclass.}}
\todoin{Write abstract}

\tableofcontents{}
\listoffigures{}
\listoftables{}

\chapter*{Preface}

The discussions in this report must be seen in the context of object oriented 
programming languages, and Java in particular, since that is the language in 
which most of the examples will be given. All though the techniques discussed 
may be applicable to languages from other paradigms, they will not be the 
subject of this report.

\mainmatter

\chapter{What is Refactoring?}

This question is best answered by first defining the concept of a 
\emph{refactoring}, what it is to \emph{refactor}, and then discuss what aspects 
of programming make people want to refactor their code.

\section{Defining refactoring}
Martin Fowler, in his classic book on refactoring\citing{refactoring}, defines a 
refactoring like this:

\begin{quote}
  \emph{Refactoring} (noun): a change made to the internal 
  structure\footnote{The structure observable by the programmer.} of software to 
  make it easier to understand and cheaper to modify without changing its 
  observable behavior.~\cite[p.~53]{refactoring}
\end{quote}

\noindent This definition assigns additional meaning to the word 
\emph{refactoring}, beyond the composition of the prefix \emph{re-}, usually 
meaning something like ``again'' or ``anew'', and the word \emph{factoring}, 
that can mean to isolate the \emph{factors} of something. Here a \emph{factor} 
would be close to the mathematical definition of something that divides a 
quantity, without leaving a remainder. Fowler is mixing the \emph{motivation} 
behind refactoring into his definition. Instead it could be more refined, formed 
to only consider the \emph{mechanical} and \emph{behavioral} aspects of 
refactoring.  That is to factor the program again, putting it together in a 
different way than before, while preserving the behavior of the program. An 
alternative definition could then be: 

\definition{A \emph{refactoring} is a transformation
done to a program without altering its external behavior.}

From this we can conclude that a refactoring primarily changes how the 
\emph{code} of a program is perceived by the \emph{programmer}, and not the 
\emph{behavior} experienced by any user of the program. Although the logical 
meaning is preserved, such changes could potentially alter the program's 
behavior when it comes to performance gain or -penalties. So any logic depending 
on the performance of a program could make the program behave differently after 
a refactoring.

In the extreme case one could argue that such a thing as \emph{software 
obfuscation} is refactoring. Software obfuscation is to make source code harder 
to read and analyze, while preserving its semantics. It could be done composing 
many, more or less randomly chosen, refactorings. Then the question arise 
whether it can be called a \emph{composite refactoring} 
\see{compositeRefactorings} or not?  The answer is not obvious.  First, there is 
no way to describe \emph{the} mechanics of software obfuscation, beacause there 
are infinitely many ways to do that. Second, \emph{obfuscation} can be thought 
of as \emph{one operation}: Either the code is obfuscated, or it is not. Third, 
it makes no sense to call software obfuscation \emph{a} refactoring, since it 
holds different meaning to different people. The last point is important, since 
one of the motivations behind defining different refactorings is to build up a 
vocabulary for software professionals to reason and discuss about programs, 
similar to the motivation behind design patterns\citing{designPatterns}.  So for 
describing \emph{software obfuscation}, it might be more appropriate to define 
what you do when performing it rather than precisely defining its mechanics in 
terms of other refactorings.

\section{The etymology of 'refactoring'}
It is a little difficult to pinpoint the exact origin of the word 
``refactoring'', as it seems to have evolved as part of a colloquial 
terminology, more than a scientific term. There is no authoritative source for a 
formal definition of it. 

According to Martin Fowler\citing{etymology-refactoring}, there may also be more 
than one origin of the word. The most well-known source, when it comes to the 
origin of \emph{refactoring}, is the Smalltalk\footnote{\emph{Smalltalk}, 
object-oriented, dynamically typed, reflective programming language. See 
\url{http://www.smalltalk.org}} community and their infamous \emph{Refactoring 
Browser}\footnote{\url{http://st-www.cs.illinois.edu/users/brant/Refactory/RefactoringBrowser.html}} 
described in the article \emph{A Refactoring Tool for 
Smalltalk}\citing{refactoringBrowser1997}, published in 1997.  
Allegedly\citing{etymology-refactoring}, the metaphor of factoring programs was 
also present in the Forth\footnote{\emph{Forth} -- stack-based, extensible 
programming language, without type-checking. See \url{http://www.forth.org}} 
community, and the word ``refactoring'' is mentioned in a book by Leo Brodie, 
called \emph{Thinking Forth}\citing{brodie2004}, first published in 
1984\footnote{\emph{Thinking Forth} was first published in 1984 by the 
\emph{Forth Interest Group}.  Then it was reprinted in 1994 with minor 
typographical corrections, before it was transcribed into an electronic edition 
typeset in \LaTeX\ and published under a Creative Commons licence in 2004. The 
edition cited here is the 2004 edition, but the content should essentially be as 
in 1984.}. The exact word is only printed one place~\cite[p.~232]{brodie2004}, 
but the term \emph{factoring} is prominent in the book, that also contains a 
whole chapter dedicated to (re)factoring, and how to keep the (Forth) code clean 
and maintainable.

\begin{quote}
  \ldots good factoring technique is perhaps the most important skill for a 
  Forth programmer.~\cite[p.~172]{brodie2004}
\end{quote}

\noindent Brodie also express what \emph{factoring} means to him:

\begin{quote}
  Factoring means organizing code into useful fragments. To make a fragment 
  useful, you often must separate reusable parts from non-reusable parts. The  
  reusable parts become new definitions. The non-reusable parts become arguments 
  or parameters to the definitions.~\cite[p.~172]{brodie2004}
\end{quote}

Fowler claims that the usage of the word \emph{refactoring} did not pass between 
the \emph{Forth} and \emph{Smalltalk} communities, but that it emerged 
independently in each of the communities.

\section{Motivation -- Why people refactor}
There are many reasons why people want to refactor their programs. They can for 
instance do it to remove duplication, break up long methods or to introduce 
design patterns\citing{designPatterns} into their software systems. The shared 
trait for all these are that peoples intentions are to make their programs 
\emph{better}, in some sense. But what aspects of their programs are becoming 
improved?

As already mentioned, people often refactor to get rid of duplication. Moving 
identical or similar code into methods, and maybe pushing methods up or down in 
their class hierarchies. Making template methods for overlapping 
algorithms/functionality and so on. It is all about gathering what belongs 
together and putting it all in one place. The resulting code is then easier to 
maintain. When removing the implicit coupling\footnote{When duplicating code, 
the code might not be coupled in other ways than that it is supposed to 
represent the same functionality. So if this functionality is going to change, 
it might need to change in more than one place, thus creating an implicit 
coupling between the multiple pieces of code.} between code snippets, the 
location of a bug is limited to only one place, and new functionality need only 
to be added to this one place, instead of a number of places people might not 
even remember.

A problem you often encounter when programming, is that a program contains a lot 
of long and hard-to-grasp methods. It can then help to break the methods into 
smaller ones, using the \ExtractMethod refactoring\citing{refactoring}. Then you 
may discover something about a program that you were not aware of before; 
revealing bugs you did not know about or could not find due to the complex 
structure of your program. \todo{Proof?} Making the methods smaller and giving 
good names to the new ones clarifies the algorithms and enhances the 
\emph{understandability} of the program \see{magic_number_seven}. This makes 
refactoring an excellent method for exploring unknown program code, or code that 
you had forgotten that you wrote.

Most primitive refactorings are simple. Their true power is first revealed when 
they are combined into larger --- higher level --- refactorings, called 
\emph{composite refactorings} \see{compositeRefactorings}. Often the goal of 
such a series of refactorings is a design pattern. Thus the \emph{design} can be 
evolved throughout the lifetime of a program, as opposed to designing up-front.  
It is all about being structured and taking small steps to improve a program's 
design.

Many software design pattern are aimed at lowering the coupling between 
different classes and different layers of logic. One of the most famous is 
perhaps the \emph{Model-View-Controller}\citing{designPatterns} pattern. It is 
aimed at lowering the coupling between the user interface and the business logic 
and data representation of a program. This also has the added benefit that the 
business logic could much easier be the target of automated tests, increasing 
the productivity in the software development process.  Refactoring is an 
important tool on the way to something greater.

Another effect of refactoring is that with the increased separation of concerns 
coming out of many refactorings, the \emph{performance} can be improved. When 
profiling programs, the problematic parts are narrowed down to smaller parts of 
the code, which are easier to tune, and optimization can be performed only where 
needed and in a more effective way.

Last, but not least, and this should probably be the best reason to refactor, is 
to refactor to \emph{facilitate a program change}. If one has managed to keep 
one's code clean and tidy, and the code is not bloated with design patterns that 
are not ever going to be needed, then some refactoring might be needed to 
introduce a design pattern that is appropriate for the change that is going to 
happen.

Refactoring program code --- with a goal in mind --- can give the code itself 
more value. That is in the form of robustness to bugs, understandability and 
maintainability. Having robust code is an obvious advantage, but 
understandability and maintainability are both very important aspects of 
software development. By incorporating refactoring in the development process, 
bugs are found faster, new functionality is added more easily and code is easier 
to understand by the next person exposed to it, which might as well be the 
person who wrote it. The consequence of this, is that refactoring can increase 
the average productivity of the development process, and thus also add to the 
monetary value of a business in the long run. The perspective on productivity 
and money should also be able to open the eyes of the many nearsighted managers 
that seldom see beyond the next milestone.

\section{The magical number seven}\label{magic_number_seven}
The article \emph{The magical number seven, plus or minus two: some limits on 
our capacity for processing information}\citing{miller1956} by George A.  
Miller, was published in the journal \emph{Psychological Review} in 1956.  It 
presents evidence that support that the capacity of the number of objects a 
human being can hold in its working memory is roughly seven, plus or minus two 
objects. This number varies a bit depending on the nature and complexity of the 
objects, but is according to Miller ``\ldots never changing so much as to be 
unrecognizable.''

Miller's article culminates in the section called \emph{Recoding}, a term he 
borrows from communication theory. The central result in this section is that by 
recoding information, the capacity of the amount of information that a human can 
process at a time is increased. By \emph{recoding}, Miller means to group 
objects together in chunks and give each chunk a new name that it can be 
remembered by. By organizing objects into patterns of ever growing depth, one 
can memorize and process a much larger amount of data than if it were to be 
represented as its basic pieces. This grouping and renaming is analogous to how 
many refactorings work, by grouping pieces of code and give them a new name.  
Examples are the fundamental \ExtractMethod and \refactoring{Extract Class} 
refactorings\citing{refactoring}.

\begin{quote}
  \ldots recoding is an extremely powerful weapon for increasing the amount of 
  information that we can deal with.~\cite[p.~95]{miller1956}
\end{quote}

An example from the article addresses the problem of memorizing a sequence of 
binary digits. Let us say we have the following sequence\footnote{The example 
  presented here is slightly modified (and shortened) from what is presented in 
  the original article\citing{miller1956}, but it is essentially the same.} of 
16 binary digits: ``1010001001110011''. Most of us will have a hard time 
memorizing this sequence by only reading it once or twice. Imagine if we instead 
translate it to this sequence: ``A273''. If you have a background from computer 
science, it will be obvious that the latest sequence is the first sequence 
recoded to be represented by digits with base 16. Most people should be able to 
memorize this last sequence by only looking at it once.

Another result from the Miller article is that when the amount of information a 
human must interpret increases, it is crucial that the translation from one code 
to another must be almost automatic for the subject to be able to remember the 
translation, before \heshe is presented with new information to recode.  Thus 
learning and understanding how to best organize certain kinds of data is 
essential to efficiently handle that kind of data in the future. This is much 
like when humans learn to read. First they must learn how to recognize letters.  
Then they can learn distinct words, and later read sequences of words that form 
whole sentences. Eventually, most of them will be able to read whole books and 
briefly retell the important parts of its content. This suggest that the use of 
design patterns\citing{designPatterns} is a good idea when reasoning about 
computer programs. With extensive use of design patterns when creating complex 
program structures, one does not always have to read whole classes of code to 
comprehend how they function, it may be sufficient to only see the name of a 
class to almost fully understand its responsibilities.

\begin{quote}
  Our language is tremendously useful for repackaging material into a few chunks 
  rich in information.~\cite[p.~95]{miller1956}
\end{quote}

Without further evidence, these results at least indicate that refactoring 
source code into smaller units with higher cohesion and, when needed, 
introducing appropriate design patterns, should aid in the cause of creating 
computer programs that are easier to maintain and has code that is easier (and 
better) understood.

\section{Notable contributions to the refactoring literature}
\todoin{Update with more contributions}

\begin{description}
  \item[1992] William F. Opdyke submits his doctoral dissertation called 
    \emph{Refactoring Object-Oriented Frameworks}\citing{opdyke1992}. This 
    work defines a set of refactorings, that are behavior preserving given that 
    their preconditions are met. The dissertation is focused on the automation 
    of refactorings.
  \item[1999] Martin Fowler et al.: \emph{Refactoring: Improving the Design of 
    Existing Code}\citing{refactoring}. This is maybe the most influential text 
    on refactoring. It bares similarities with Opdykes thesis\citing{opdyke1992} 
    in the way that it provides a catalog of refactorings. But Fowler's book is 
    more about the craft of refactoring, as he focuses on establishing a 
    vocabulary for refactoring, together with the mechanics of different 
    refactorings and when to perform them. His methodology is also founded on 
  the principles of test-driven development.
  \item[2005] Joshua Kerievsky: \emph{Refactoring to 
    Patterns}\citing{kerievsky2005}. This book is heavily influenced by Fowler's 
    \emph{Refactoring}\citing{refactoring} and the ``Gang of Four'' \emph{Design 
    Patterns}\citing{designPatterns}. It is building on the refactoring 
    catalogue from Fowler's book, but is trying to bridge the gap between 
    \emph{refactoring} and \emph{design patterns} by providing a series of 
    higher-level composite refactorings, that makes code evolve toward or away 
    from certain design patterns. The book is trying to build up the readers 
    intuition around \emph{why} one would want to use a particular design 
    pattern, and not just \emph{how}. The book is encouraging evolutionary 
    design.  \See{relationToDesignPatterns}
\end{description}

\section{Tool support (for Java)}\label{toolSupport}
This section will briefly compare the refatoring support of the three IDEs 
\emph{Eclipse}\footnote{\url{http://www.eclipse.org/}}, \emph{IntelliJ 
IDEA}\footnote{The IDE under comparison is the \emph{Community Edition}, 
\url{http://www.jetbrains.com/idea/}} and 
\emph{NetBeans}\footnote{\url{https://netbeans.org/}}. These are the most 
popular Java IDEs\citing{javaReport2011}.

All three IDEs provide support for the most useful refactorings, like the 
different extract, move and rename refactorings. In fact, Java-targeted IDEs are 
known for their good refactoring support, so this did not appear as a big 
surprise.

The IDEs seem to have excellent support for the \ExtractMethod refactoring, so 
at least they have all passed the first refactoring 
rubicon\citing{fowlerRubicon2001,secondRubicon2012}.

Regarding the \MoveMethod refactoring, the \emph{Eclipse} and \emph{IntelliJ} 
IDEs do the job in very similar manners. In most situations they both do a 
satisfying job by producing the expected outcome. But they do nothing to check 
that the result does not break the semantics of the program \see{correctness}.
The \emph{NetBeans} IDE implements this refactoring in a somewhat 
unsophisticated way. For starters, its default destination for the move is 
itself, although it refuses to perform the refactoring if chosen. But the worst 
part is, that if moving the method \method{f} of the class \type{C} to the class 
\type{X}, it will break the code. The result is shown in 
\myref{lst:moveMethod_NetBeans}.

\begin{listing}
\begin{multicols}{2}
\begin{minted}[samepage]{java}
public class C {
    private X x;
    ...
    public void f() {
        x.m();
        x.n();
    }
}
\end{minted}

\columnbreak

\begin{minted}[samepage]{java}
public class X {
    ...
    public void f(C c) {
        c.x.m();
        c.x.n();
    }
}
\end{minted}
\end{multicols}
\caption{Moving method \method{f} from \type{C} to \type{X}.}
\label{lst:moveMethod_NetBeans}
\end{listing}

NetBeans will try to make code that call the methods \method{m} and \method{n} 
of \type{X} by accessing them through \var{c.x}, where \var{c} is a parameter of 
type \type{C} that is added the method \method{f} when it is moved. (This is 
seldom the desired outcome of this refactoring, but ironically, this ``feature'' 
keeps NetBeans from breaking the code in the example from \myref{correctness}.) 
If \var{c.x} for some reason is inaccessible to \type{X}, as in this case, the 
refactoring breaks the code, and it will not compile. NetBeans presents a 
preview of the refactoring outcome, but the preview does not catch it if the IDE 
is about break the program. 

The IDEs under investigation seems to have fairly good support for primitive 
refactorings, but what about more complex ones, such as the \refactoring{Extract 
Class}\citing{refactoring}? The \refactoring{Extract Class} refactoring works by 
creating a class, for then to move members to that class and access them from 
the old class via a reference to the new class. \emph{IntelliJ} handles this in 
a fairly good manner, although, in the case of private methods, it leaves unused 
methods behind. These are methods that delegate to a field with the type of the 
new class, but are not used anywhere. \emph{Eclipse} has added (or withdrawn) 
its own quirk to the Extract Class refactoring, and only allows for 
\emph{fields} to be moved to a new class, \emph{not methods}. This makes it 
effectively only extracting a data structure, and calling it 
\refactoring{Extract Class} is a little misleading.  One would often be better 
off with textual extract and paste than using the Extract Class refactoring in 
Eclipse. When it comes to \emph{NetBeans}, it does not even seem to have made an 
attempt on providing this refactoring. (Well, it probably has, but it does not 
show in the IDE.) 

\todoin{Visual Studio (C++/C\#), Smalltalk refactoring browser?,
second refactoring rubicon?}

\section{The relation to design patterns}\label{relationToDesignPatterns}

\emph{Refactoring} and \emph{design patterns} have at least one thing in common, 
they are both promoted by advocates of \emph{clean code}\citing{cleanCode} as 
fundamental tools on the road to more maintanable and extendable source code.

\begin{quote}
  Design patterns help you determine how to reorganize a design, and they can 
  reduce the amount of refactoring you need to do 
  later.~\cite[p.~353]{designPatterns}
\end{quote}

Although sometimes associated with 
over-engineering\citing{kerievsky2005,refactoring}, design patterns are in 
general assumed to be good for maintainability of source code.  That may be 
because many of them are designed to support the \emph{open/closed principle} of 
object-oriented programming. The principle was first formulated by Bertrand 
Meyer, the creator of the Eiffel programming language, like this: ``Modules 
should be both open and closed.''\citing{meyer1988} It has been popularized, 
with this as a common version: 

\begin{quote}
  Software entities (classes, modules, functions, etc.) should be open for 
  extension, but closed for modification.\footnote{See 
    \url{http://c2.com/cgi/wiki?OpenClosedPrinciple} or  
    \url{https://en.wikipedia.org/wiki/Open/closed_principle}}
\end{quote} 

Maintainability is often thought of as the ability to be able to introduce new 
functionality without having to change too much of the old code. When 
refactoring, the motivation is often to facilitate adding new functionality. It 
is about factoring the old code in a way that makes the new functionality being 
able to benefit from the functionality already residing in a software system, 
without having to copy old code into new. Then, next time someone shall add new 
functionality, it is less likely that the old code has to change. Assuming that 
a design pattern is the best way to get rid of duplication and assist in 
implementing new functionality, it is reasonable to conclude that a design 
pattern often is the target of a series of refactorings. Having a repertoire of 
design patterns can also help in knowing when and how to refactor a program to 
make it reflect certain desired characteristics.

\begin{quote}
  There is a natural relation between patterns and refactorings. Patterns are 
  where you want to be; refactorings are ways to get there from somewhere 
  else.~\cite[p.~107]{refactoring}
\end{quote}

This quote is wise in many contexts, but it is not always appropriate to say 
``Patterns are where you want to be\ldots''. \emph{Sometimes}, patterns are 
where you want to be, but only because it will benefit your design. It is not 
true that one should always try to incorporate as many design patterns as 
possible into a program. It is not like they have intrinsic value. They only add 
value to a system when they support its design. Otherwise, the use of design 
patterns may only lead to a program that is more complex than necessary.

\begin{quote}
  The overuse of patterns tends to result from being patterns happy. We are 
  \emph{patterns happy} when we become so enamored of patterns that we simply 
  must use them in our code.~\cite[p.~24]{kerievsky2005}
\end{quote}

This can easily happen when relying largely on up-front design. Then it is 
natural, in the very beginning, to try to build in all the flexibility that one 
believes will be necessary throughout the lifetime of a software system.  
According to Joshua Kerievsky ``That sounds reasonable --- if you happen to be 
psychic.''~\cite[p.~1]{kerievsky2005} He is advocating what he believes is a 
better approach: To let software continually evolve. To start with a simple 
design that meets today's needs, and tackle future needs by refactoring to 
satisfy them. He believes that this is a more economic approach than investing 
time and money into a design that inevitably is going to change. By relying on 
continuously refactoring a system, its design can be made simpler without 
sacrificing flexibility. To be able to fully rely on this approach, it is of 
utter importance to have a reliable suit of tests to lean on. \See{testing} This 
makes the design process more natural and less characterized by difficult 
decisions that has to be made before proceeding in the process, and that is 
going to define a project for all of its unforeseeable future.

\begin{comment}

\section{Classification of refactorings} 
% only interesting refactorings
% with 2 detailed examples? One for structured and one for intra-method?
% Is replacing Bubblesort with Quick Sort considered a refactoring?

\subsection{Structural refactorings}

\subsubsection{Primitive refactorings}

% Composing Methods
\explanation{Extract Method}{You have a code fragment that can be grouped 
together.}{Turn the fragment into a method whose name explains the purpose of 
the method.}

\explanation{Inline Method}{A method's body is just as clear as its name.}{Put 
the method's body into the body of its callers and remove the method.}

\explanation{Inline Temp}{You have a temp that is assigned to once with a simple 
expression, and the temp is getting in the way of other refactorings.}{Replace 
all references to that temp with the expression}

% Moving Features Between Objects
\explanation{Move Method}{A method is, or will be, using or used by more 
features of another class than the class on which it is defined.}{Create a new 
method with a similar body in the class it uses most. Either turn the old method 
into a simple delegation, or remove it altogether.}

\explanation{Move Field}{A field is, or will be, used by another class more than 
the class on which it is defined}{Create a new field in the target class, and 
change all its users.}

% Organizing Data
\explanation{Replace Magic Number with Symbolic Constant}{You have a literal 
number with a particular meaning.}{Create a constant, name it after the meaning, 
and replace the number with it.}

\explanation{Encapsulate Field}{There is a public field.}{Make it private and 
provide accessors.}

\explanation{Replace Type Code with Class}{A class has a numeric type code that 
does not affect its behavior.}{Replace the number with a new class.}

\explanation{Replace Type Code with Subclasses}{You have an immutable type code 
that affects the behavior of a class.}{Replace the type code with subclasses.}

\explanation{Replace Type Code with State/Strategy}{You have a type code that 
affects the behavior of a class, but you cannot use subclassing.}{Replace the 
type code with a state object.}

% Simplifying Conditional Expressions
\explanation{Consolidate Duplicate Conditional Fragments}{The same fragment of 
code is in all branches of a conditional expression.}{Move it outside of the 
expression.}

\explanation{Remove Control Flag}{You have a variable that is acting as a 
control flag fro a series of boolean expressions.}{Use a break or return 
instead.}

\explanation{Replace Nested Conditional with Guard Clauses}{A method has 
conditional behavior that does not make clear the normal path of 
execution.}{Use guard clauses for all special cases.}

\explanation{Introduce Null Object}{You have repeated checks for a null 
value.}{Replace the null value with a null object.}

\explanation{Introduce Assertion}{A section of code assumes something about the 
state of the program.}{Make the assumption explicit with an assertion.}

% Making Method Calls Simpler
\explanation{Rename Method}{The name of a method does not reveal its 
purpose.}{Change the name of the method}

\explanation{Add Parameter}{A method needs more information from its 
caller.}{Add a parameter for an object that can pass on this information.}

\explanation{Remove Parameter}{A parameter is no longer used by the method 
body.}{Remove it.}

%\explanation{Parameterize Method}{Several methods do similar things but with 
%different values contained in the method.}{Create one method that uses a 
%parameter for the different values.}

\explanation{Preserve Whole Object}{You are getting several values from an 
object and passing these values as parameters in a method call.}{Send the whole 
object instead.}

\explanation{Remove Setting Method}{A field should be set at creation time and 
never altered.}{Remove any setting method for that field.}

\explanation{Hide Method}{A method is not used by any other class.}{Make the 
method private.}

\explanation{Replace Constructor with Factory Method}{You want to do more than 
simple construction when you create an object}{Replace the constructor with a 
factory method.}

% Dealing with Generalization
\explanation{Pull Up Field}{Two subclasses have the same field.}{Move the field 
to the superclass.}

\explanation{Pull Up Method}{You have methods with identical results on 
subclasses.}{Move them to the superclass.}

\explanation{Push Down Method}{Behavior on a superclass is relevant only for 
some of its subclasses.}{Move it to those subclasses.}

\explanation{Push Down Field}{A field is used only by some subclasses.}{Move the 
field to those subclasses}

\explanation{Extract Interface}{Several clients use the same subset of a class's 
interface, or two classes have part of their interfaces in common.}{Extract the 
subset into an interface.}

\explanation{Replace Inheritance with Delegation}{A subclass uses only part of a 
superclasses interface or does not want to inherit data.}{Create a field for the 
superclass, adjust methods to delegate to the superclass, and remove the 
subclassing.}

\explanation{Replace Delegation with Inheritance}{You're using delegation and 
are often writing many simple delegations for the entire interface}{Make the 
delegating class a subclass of the delegate.}

\subsubsection{Composite refactorings}

% Composing Methods
% \explanation{Replace Method with Method Object}{}{}

% Moving Features Between Objects
\explanation{Extract Class}{You have one class doing work that should be done by 
two}{Create a new class and move the relevant fields and methods from the old 
class into the new class.}

\explanation{Inline Class}{A class isn't doing very much.}{Move all its features 
into another class and delete it.}

\explanation{Hide Delegate}{A client is calling a delegate class of an 
object.}{Create Methods on the server to hide the delegate.}

\explanation{Remove Middle Man}{A class is doing to much simple delegation.}{Get 
the client to call the delegate directly.}

% Organizing Data
\explanation{Replace Data Value with Object}{You have a data item that needs 
additional data or behavior.}{Turn the data item into an object.}

\explanation{Change Value to Reference}{You have a class with many equal 
instances that you want to replace with a single object.}{Turn the object into a 
reference object.}

\explanation{Encapsulate Collection}{A method returns a collection}{Make it 
return a read-only view and provide add/remove methods.}

% \explanation{Replace Array with Object}{}{}

\explanation{Replace Subclass with Fields}{You have subclasses that vary only in 
methods that return constant data.}{Change the methods to superclass fields and 
eliminate the subclasses.}

% Simplifying Conditional Expressions
\explanation{Decompose Conditional}{You have a complicated conditional 
(if-then-else) statement.}{Extract methods from the condition, then part, an 
else part.}

\explanation{Consolidate Conditional Expression}{You have a sequence of 
conditional tests with the same result.}{Combine them into a single conditional 
expression and extract it.}

\explanation{Replace Conditional with Polymorphism}{You have a conditional that 
chooses different behavior depending on the type of an object.}{Move each leg 
of the conditional to an overriding method in a subclass. Make the original 
method abstract.}

% Making Method Calls Simpler
\explanation{Replace Parameter with Method}{An object invokes a method, then 
passes the result as a parameter for a method. The receiver can also invoke this 
method.}{Remove the parameter and let the receiver invoke the method.}

\explanation{Introduce Parameter Object}{You have a group of parameters that 
naturally go together.}{Replace them with an object.}

% Dealing with Generalization
\explanation{Extract Subclass}{A class has features that are used only in some 
instances.}{Create a subclass for that subset of features.}

\explanation{Extract Superclass}{You have two classes with similar 
features.}{Create a superclass and move the common features to the 
superclass.}

\explanation{Collapse Hierarchy}{A superclass and subclass are not very 
different.}{Merge them together.}

\explanation{Form Template Method}{You have two methods in subclasses that 
perform similar steps in the same order, yet the steps are different.}{Get the 
steps into methods with the same signature, so that the original methods become 
the same. Then you can pull them up.}


\subsection{Functional refactorings}

\explanation{Substitute Algorithm}{You want to replace an algorithm with one 
that is clearer.}{Replace the body of the method with the new algorithm.}

\end{comment}

\section{The impact on software quality}

\subsection{What is software quality?}
The term \emph{software quality} has many meanings. It all depends on the 
context we put it in. If we look at it with the eyes of a software developer, it 
usually means that the software is easily maintainable and testable, or in other 
words, that it is \emph{well designed}. This often correlates with the 
management scale, where \emph{keeping the schedule} and \emph{customer 
satisfaction} is at the center. From the customers point of view, in addition to 
good usability, \emph{performance} and \emph{lack of bugs} is always 
appreciated, measurements that are also shared by the software developer. (In 
addition, such things as good documentation could be measured, but this is out 
of the scope of this document.)

\subsection{The impact on performance}
\begin{quote}
  Refactoring certainly will make software go more slowly\footnote{With todays 
  compiler optimization techniques and performance tuning of e.g. the Java 
virtual machine, the penalties of object creation and method calls are 
debatable.}, but it also makes the software more amenable to performance 
tuning.~\cite[p.~69]{refactoring}
\end{quote}

\noindent There is a common belief that refactoring compromises performance, due 
to increased degree of indirection and that polymorphism is slower than 
conditionals.

In a survey, Demeyer\citing{demeyer2002} disproves this view in the case of 
polymorphism. He did an experiment on, what he calls, ``Transform Self Type 
Checks'' where you introduce a new polymorphic method and a new class hierarchy 
to get rid of a class' type checking of a ``type attribute``. He uses this kind 
of transformation to represent other ways of replacing conditionals with 
polymorphism as well. The experiment is performed on the C++ programming 
language and with three different compilers and platforms. Demeyer concludes 
that, with compiler optimization turned on, polymorphism beats middle to large 
sized if-statements and does as well as case-statements.  (In accordance with 
his hypothesis, due to similarities between the way C++ handles polymorphism and 
case-statements.)

\begin{quote}
  The interesting thing about performance is that if you analyze most programs, 
  you find that they waste most of their time in a small fraction of the 
  code.~\cite[p.~70]{refactoring}
\end{quote}

\noindent So, although an increased amount of method calls could potentially 
slow down programs, one should avoid premature optimization and sacrificing good 
design, leaving the performance tuning until after profiling\footnote{For and 
  example of a Java profiler, check out VisualVM: 
  \url{http://visualvm.java.net/}} the software and having isolated the actual 
  problem areas.

\section{Composite refactorings}\label{compositeRefactorings}
\todo{motivation, examples, manual vs automated?, what about refactoring in a 
very large code base?}
Generally, when thinking about refactoring, at the mechanical level, there are 
essentially two kinds of refactorings. There are the \emph{primitive} 
refactorings, and the \emph{composite} refactorings. 

\definition{A \emph{primitive refactoring} is a refactoring that cannot be 
expressed in terms of other refactorings.}

\noindent Examples are the \refactoring{Pull Up Field} and \refactoring{Pull Up 
Method} refactorings\citing{refactoring}, that move members up in their class 
hierarchies.

\definition{A \emph{composite refactoring} is a refactoring that can be 
expressed in terms of two or more other refactorings.}

\noindent An example of a composite refactoring is the \refactoring{Extract 
Superclass} refactoring\citing{refactoring}. In its simplest form, it is composed 
of the previously described primitive refactorings, in addition to the 
\refactoring{Pull Up Constructor Body} refactoring\citing{refactoring}.  It works 
by creating an abstract superclass that the target class(es) inherits from, then 
by applying \refactoring{Pull Up Field}, \refactoring{Pull Up Method} and 
\refactoring{Pull Up Constructor Body} on the members that are to be members of 
the new superclass. For an overview of the \refactoring{Extract Superclass} 
refactoring, see \myref{fig:extractSuperclass}.

\begin{figure}[h]
  \centering
  \includegraphics[angle=270,width=\linewidth]{extractSuperclassItalic.pdf}
  \caption{The Extract Superclass refactoring}
  \label{fig:extractSuperclass}
\end{figure}

\section{Manual vs. automated refactorings}
Refactoring is something every programmer does, even if \heshe does not known 
the term \emph{refactoring}. Every refinement of source code that does not alter 
the program's behavior is a refactoring. For small refactorings, such as 
\ExtractMethod, executing it manually is a manageable task, but is still prone 
to errors. Getting it right the first time is not easy, considering the method 
signature and all the other aspects of the refactoring that has to be in place.  

Take for instance the renaming of classes, methods and fields. For complex 
programs these refactorings are almost impossible to get right.  Attacking them 
with textual search and replace, or even regular expressions, will fall short on 
these tasks. Then it is crucial to have proper tool support that can perform 
them automatically. Tools that can parse source code and thus have semantic 
knowledge about which occurrences of which names belong to what construct in the 
program. For even trying to perform one of these complex task manually, one 
would have to be very confident on the existing test suite \see{testing}.

\section{Correctness of refactorings}\label{correctness}
For automated refactorings to be truly useful, they must show a high degree of 
behavior preservation. This last sentence might seem obvious, but there are 
examples of refactorings in existing tools that break programs. I will now 
present an example of an \ExtractMethod refactoring followed by a \MoveMethod 
refactoring that breaks a program in both the \emph{Eclipse} and \emph{IntelliJ} 
IDEs\footnote{The NetBeans IDE handles this particular situation without 
  altering the program's beavior, mainly because its Move Method refactoring 
  implementation is a bit flawed in other ways \see{toolSupport}.}. The 
  following piece of code shows the target for the composed refactoring:

\begin{minted}[linenos,samepage]{java}
public class C {
    public X x = new X();

    public void f() {
        x.m(this);
        x.n();
    }
}
\end{minted}

\noindent The next piece of code shows the destination of the refactoring. Note 
that the method \method{m(C c)} of class \type{C} assigns to the field \var{x} 
of the argument \var{c} that has type \type{C}:

\begin{minted}[samepage]{java}
public class X {
    public void m(C c) {
        c.x = new X();
    }
    public void n() {}
}
\end{minted}

The refactoring sequence works by extracting line 5 and 6 from the original 
class \type{C} into a method \method{f} with the statements from those lines as 
its method body. The method is then moved to the class \type{X}. The result is 
shown in the following two pieces of code:

\begin{minted}[linenos,samepage]{java}
public class C {
    public X x = new X();

    public void f() {
        x.f(this);
    }
}
\end{minted}

\begin{minted}[linenos,samepage]{java}
public class X {
    public void m(C c) {
        c.x = new X();
    }
    public void n() {}
    public void f(C c) {
        m(c);
        n();
    }
}
\end{minted}

After the refactoring, the method \method{f} of class \type{C} is calling the 
method \method{f} of class \type{X}, and the program now behaves different than 
before. (See line 5 of the version of class \type{C} after the refactoring.) 
Before the refactoring, the methods \method{m} and \method{n} of class \type{X} 
are called on different object instances (see line 5 and 6 of the original class 
\type{C}).  After, they are called on the same object, and the statement on line 
3 of class \type{X} (the version after the refactoring) no longer have any 
  effect in our example.

The bug introduced in the previous example is of such a nature\footnote{Caused 
  by aliasing. See \url{https://en.wikipedia.org/wiki/Aliasing_(computing)}} 
  that it is very difficult to spot if the refactored code is not covered by 
  tests.  It does not generate compilation errors, and will thus only result in 
  a runtime error or corrupted data, which might be hard to detect.

\section{Refactoring and the importance of testing}\label{testing}
\begin{quote}
  If you want to refactor, the essential precondition is having solid 
  tests.\citing{refactoring}
\end{quote}

When refactoring, there are roughly three classes of errors that can be made.  
The first class of errors are the ones that make the code unable to compile.  
These \emph{compile-time} errors are of the nicer kind. They flash up at the 
moment they are made (at least when using an IDE), and are usually easy to fix.  
The second class are the \emph{runtime} errors. Although they take a bit longer 
to surface, they usually manifest after some time in an illegal argument 
exception, null pointer exception or similar during the program execution.  
These kind of errors are a bit harder to handle, but at least they will show, 
eventually. Then there are the \emph{behavior-changing} errors. These errors are 
of the worst kind. They do not show up during compilation and they do not turn 
on a blinking red light during runtime either. The program can seem to work 
perfectly fine with them in play, but the business logic can be damaged in ways 
that will only show up over time.

For discovering runtime errors and behavior changes when refactoring, it is 
essential to have good test coverage. Testing in this context means writing 
automated tests. Manual testing may have its uses, but when refactoring, it is 
automated unit testing that dominate. For discovering behavior changes it is 
especially important to have tests that cover potential problems, since these 
kind of errors does not reveal themselves.

Unit testing is not a way to \emph{prove} that a program is correct, but it is a 
way to make you confindent that it \emph{probably} works as desired.  In the 
context of test driven development (commonly known as TDD), the tests are even a 
way to define how the program is \emph{supposed} to work.  It is then, by 
definition, working if the tests are passing.  

If the test coverage for a code base is perfect, then it should, theoretically, 
be risk-free to perform refactorings on it. This is why automated tests and 
refactoring are such a great match.

\subsection{Testing the code from correctness section}
The worst thing that can happen when refactoring is to introduce changes to the 
behavior of a program, as in the example on \myref{correctness}. This example 
may be trivial, but the essence is clear. The only problem with the example is 
that it is not clear how to create automated tests for it, without changing it 
in intrusive ways.

Unit tests, as they are known from the different xUnit frameworks around, are 
only suitable to test the \emph{result} of isolated operations. They can not 
easily (if at all) observe the \emph{history} of a program.

This problem is still open.

\todoin{Write?}
\begin{comment}

Assuming a sequential (non-concurrent) program:

\begin{minted}{java}
tracematch (C c, X x) {
  sym m before:
    call(* X.m(C)) && args(c) && cflow(within(C));
  sym n before:
    call(* X.n()) && target(x) && cflow(within(C));
  sym setCx after:
    set(C.x) && target(c) && !cflow(m);

  m n

  { assert x == c.x; }
}
\end{minted}

%\begin{minted}{java}
%tracematch (X x1, X x2) {
%  sym m before:
%    call(* X.m(C)) && target(x1);
%  sym n before:
%    call(* X.n()) && target(x2);
%  sym setX after:
%    set(C.x) && !cflow(m) && !cflow(n);
%
%  m n
%
%  { assert x1 != x2; }
%}
%\end{minted}
\end{comment}

\section{The project}
The aim of this master project will be to investigate the relationship between a 
composite refactoring composed of the \ExtractMethod and \MoveMethod 
refactorings, and its impact on one or more software metrics.

The composition of the \ExtractMethod and \MoveMethod refactorings springs 
naturally out of the need to move procedures closer to the data they manipulate.  
This composed refactoring is not well described in the literature, but it is 
implemented in at least one tool called 
\emph{CodeRush}\footnote{\url{https://help.devexpress.com/\#CodeRush/CustomDocument3519}}, 
that is an extension for \emph{MS Visual 
Studio}\footnote{\url{http://www.visualstudio.com/}}. In CodeRush it is called 
\emph{Extract Method to 
Type}\footnote{\url{https://help.devexpress.com/\#CodeRush/CustomDocument6710}}, 
but I choose to call it \ExtractAndMoveMethod, since I feel it better 
communicates which primitive refactorings it is composed of. 

For the metrics, I will at least measure the \emph{Coupling between object 
classes} (CBO) metric that is described by Chidamber and Kemerer in their 
article \emph{A Metrics Suite for Object Oriented 
Design}\citing{metricsSuite1994}.

The project will then consist in implementing the \ExtractAndMoveMethod 
refactoring, as well as executing it over a larger code base. Then the effect of 
the change must be measured by calculating the chosen software metrics both 
before and after the execution. To be able to execute the refactoring 
automatically I have to make it analyze code to determine the best selections to 
extract into new methods.


%\part{The project}
%\chapter{Planning the project}
%\part{Conclusion}
%\chapter{Results}                   



\chapter{The Project}

\section{The problem statement}
\todoin{write/move}

\section{Choosing the target language}
Choosing which programming language the code that shall be manipulated shall be 
written in, is not a very difficult task. We choose to limit the possible 
languages to the object-oriented programming languages, since most of the 
terminology and literature regarding refactoring comes from the world of 
object-oriented programming. In addition, the language must have existing tool 
support for refactoring.

The \emph{Java} programming language\footnote{\url{https://www.java.com/}} is 
the dominating language when it comes to example code in the literature of 
refactoring, and is thus a natural choice. Java is perhaps, currently the most 
influential programming language in the world, with its \emph{Java Virtual 
Machine} that runs on all of the most popular architectures and also supports 
dozens of other programming languages\footnote{They compile to java bytecode.}, 
with \emph{Scala}, \emph{Clojure} and \emph{Groovy} as the most prominent ones.  
Java is currently the language that every other programming language is compared 
against. It is also the primary programming language for the author of this 
thesis.

\section{Choosing the tools}
When choosing a tool for manipulating Java, there are certain criterias that 
have to be met. First of all, the tool should have some existing refactoring 
support that this thesis can build upon. Secondly it should provide some kind of 
framework for parsing and analyzing Java source code. Third, it should itself be 
open source. This is both because of the need to be able to browse the code for 
the existing refactorings that is contained in the tool, and also because open 
source projects hold value in them selves. Another important aspect to consider 
is that open source projects of a certain size, usually has large communities of 
people connected to them, that are commited to answering questions regarding the 
use and misuse of the products, that to a large degree is made by the cummunity 
itself.

There is a certain class of tools that meet these criterias, namely the class of 
\emph{IDEs}\footnote{\emph{Integrated Development Environment}}. These are 
proagrams that is ment to support the whole production cycle of a cumputer 
program, and the most popular IDEs that support Java, generally have quite good 
refactoring support.

The main contenders for this thesis is the \emph{Eclipse IDE}, with the 
\emph{Java development tools} (JDT), the \emph{IntelliJ IDEA Community Edition} 
and the \emph{NetBeans IDE}. \See{toolSupport} Eclipse and NetBeans are both 
free, open source and community driven, while the IntelliJ IDEA has an open 
sourced community edition that is free of charge, but also offer an 
\emph{Ultimate Edition} with an extended set of features, at additional cost.  
All three IDEs supports adding plugins to extend their functionality and tools 
that can be used to parse and analyze Java source code. But one of the IDEs 
stand out as a favorite, and that is the \emph{Eclipse IDE}. This is the most 
popular\citing{javaReport2011} among them and seems to be de facto standard IDE 
for Java development regardless of platform.

\section{Organizing the project}
All the parts of this master project is under version control with 
\emph{Git}\footnote{\url{http://git-scm.com/}}.

The software written is organized as some Eclipse plugins. Writing a plugin is 
the natural way to utilize the API of Eclipse. This also makes it possible to 
provide a user interface to manually run operations on selections in program 
source code or whole projects/packages.

When writing a plugin in Eclipse, one has access to resources such as the 
current workspace, the open editor and the current selection.

\section{Continuous integration}
The continuous integration server 
\emph{Jenkins}\footnote{\url{http://jenkins-ci.org/}} has been set up for the 
project\footnote{A work mostly done by the supervisor.}. It is used as a way to 
run tests and perform code coverage analysis. 

To be able to build the Eclipse plugins and run tests for them with Jenkins, the 
component assembly project 
\emph{Buckminster}\footnote{\url{http://www.eclipse.org/buckminster/}} is used, 
through its plugin for Jenkins. Buckminster provides for a way to specify the 
resources needed for building a project and where and how to find them.  
Buckminster also handles the setup of a target environment to run the tests in.  
All this is needed because the code to build depends on an Eclipse installation 
with various plugins.

\subsection{Problems with AspectJ}
The Buckminster build worked fine until introducing AspectJ into the project.  
When building projects using AspectJ, there are some additional steps that needs 
to be performed. First of all, the aspects themselves must be compiled. Then the 
aspects needs to be woven with the classes they affect. This demands a process 
that does multiple passes over the source code.

When using AspectJ with Eclipse, the specialized compilation and the weaving can 
be handled by the \emph{AspectJ Development 
Tools}\footnote{\url{https://www.eclipse.org/ajdt/}}. This works all fine, but 
it complicates things when trying to build a project depending on Eclipse 
plugins outside of Eclipse. There is supposed to be a way to specify a compiler 
adapter for javac, together with the file extensions for the file types it shall 
operate. The AspectJ compiler adapter is called 
\typewithref{org.aspectj.tools.ant.taskdefs}{Ajc11CompilerAdapter}, and it works 
with files that has the extensions \code{*.java} and \code{*.aj}. I tried to 
setup this in the build properties file for the project containing the aspects, 
but to no avail. The project containing the aspects does not seem to be built at 
all, and the projects that depends on it complains that they cannot find certain 
classes.

I then managed to write an \emph{Ant}\footnote{\url{https://ant.apache.org/}} 
build file that utilizes the AspectJ compiler adapter, for the 
\code{no.uio.ifi.refaktor} plugin. The problem was then that it could no longer 
take advantage of the environment set up by Buckminster. The solution to this 
particular problem was of a ``hacky'' nature. It involves exporting the plugin 
dependencies for the project to an Ant build file, and copy the exported path 
into the existing build script. But then the Ant script needs to know where the 
local Eclipse installation is located. This is no problem when building on a 
local machine, but to utilize the setup done by Buckminster is a problem still 
unsolved. To get the classpath for the build setup correctly, and here comes the 
most ``hacky'' part of the solution, the Ant script has a target for copying the 
classpath elements into a directory relative to the project directory and 
checking it into Git. When no \code{ECLIPSE\_HOME} property is set while running 
Ant, the script uses the copied plugins instead of the ones provided by the 
Eclipse installation when building the project. This obviously creates some 
problems with maintaining the list of dependencies in the Ant file, as well as 
remembering to copy the plugins every time the list of dependencies change.

The Ant script described above is run by Jenkins before the Buckminster setup 
and build. When setup like this, the Buckminster build succeeds for the projects 
not using AspectJ, and the tests are run as normal. This is all good, but it 
feels a little scary, since the reason for Buckminster not working with AspectJ 
is still unknown.

The problems with building with AspectJ on the Jenkins server lasted for a 
while, before they were solved. This is reflected in the ``Test Result Trend'' 
and ``Code Coverage Trend'' reported by Jenkins.


\chapter{Refactorings in Eclipse JDT: Design, Shortcomings and Wishful 
Thinking}\label{ch:jdt_refactorings}

This chapter will deal with some of the design behind refactoring support in 
Eclipse, and the JDT in specific. After which it will follow a section about 
shortcomings of the refactoring API in terms of composition of refactorings. The 
chapter will be concluded with a section telling some of the ways the 
implementation of refactorings in the JDT could have worked to facilitate 
composition of refactorings.

\section{Design}
The refactoring world of Eclipse can in general be separated into two parts: The 
language independent part and the part written for a specific programming 
language -- the language that is the target of the supported refactorings.  
\todo{What about the language specific part?}

\subsection{The Language Toolkit}
The Language Toolkit\footnote{The content of this section is a mixture of 
  written material from 
  \url{https://www.eclipse.org/articles/Article-LTK/ltk.html} and 
  \url{http://www.eclipse.org/articles/article.php?file=Article-Unleashing-the-Power-of-Refactoring/index.html}, 
the LTK source code and my own memory.}, or LTK for short, is the framework that 
is used to implement refactorings in Eclipse.  It is language independent and 
provides the abstractions of a refactoring and the change it generates, in the 
form of the classes \typewithref{org.eclipse.ltk.core.refactoring}{Refactoring} 
and \typewithref{org.eclipse.ltk.core.refactoring}{Change}.

There are also parts of the LTK that is concerned with user interaction, but 
they will not be discussed here, since they are of little value to us and our 
use of the framework. We are primarily interested in the parts that can be 
automated.

\subsubsection{The Refactoring Class}
The abstract class \type{Refactoring} is the core of the LTK framework. Every 
refactoring that is going to be supported by the LTK have to end up creating an 
instance of one of its subclasses. The main responsibilities of subclasses of 
\type{Refactoring} is to implement template methods for condition checking 
(\methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{checkInitialConditions} 
and 
\methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{checkFinalConditions}), 
in addition to the 
\methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{createChange} 
method that creates and returns an instance of the \type{Change} class.

If the refactoring shall support that others participate in it when it is 
executed, the refactoring has to be a processor-based 
refactoring\typeref{org.eclipse.ltk.core.refactoring.participants.ProcessorBasedRefactoring}.  
It then delegates to its given 
\typewithref{org.eclipse.ltk.core.refactoring.participants}{RefactoringProcessor} 
for condition checking and change creation. Participating in a refactoring can 
be useful in cases where the changes done to programming source code affects 
other related resources in the workspace. This can be names or paths in 
configuration files, or maybe one would like to perform additional logging of 
changes done in the workspace.

\subsubsection{The Change Class}
This class is the base class for objects that is responsible for performing the 
actual workspace transformations in a refactoring. The main responsibilities for 
its subclasses is to implement the 
\methodwithref{org.eclipse.ltk.core.refactoring.Change}{perform} and 
\methodwithref{org.eclipse.ltk.core.refactoring.Change}{isValid} methods. The 
\method{isValid} method verifies that the change object is valid and thus can be 
executed by calling its \method{perform} method. The \method{perform} method 
performs the desired change and returns an undo change that can be executed to 
reverse the effect of the transformation done by its originating change object. 

\subsubsection{Executing a Refactoring}\label{executing_refactoring}
The life cycle of a refactoring generally follows two steps after creation: 
condition checking and change creation. By letting the refactoring object be 
handled by a 
\typewithref{org.eclipse.ltk.core.refactoring}{CheckConditionsOperation} that
in turn is handled by a 
\typewithref{org.eclipse.ltk.core.refactoring}{CreateChangeOperation}, it is 
assured that the change creation process is managed in a proper manner.

The actual execution of a change object has to follow a detailed life cycle.  
This life cycle is honored if the \type{CreateChangeOperation} is handled by a 
\typewithref{org.eclipse.ltk.core.refactoring}{PerformChangeOperation}. If also 
an undo manager\typeref{org.eclipse.ltk.core.refactoring.IUndoManager} is set 
for the \type{PerformChangeOperation}, the undo change is added into the undo 
history.

\section{Shortcomings}
This section is introduced naturally with a conclusion: The JDT refactoring 
implementation does not facilitate composition of refactorings. 
\todo{refine}This section will try to explain why, and also identify other 
shortcomings of both the usability and the readability of the JDT refactoring 
source code.

I will begin at the end and work my way toward the composition part of this 
section.

\subsection{Absence of Generics in Eclipse Source Code}
This section is not only concerning the JDT refactoring API, but also large 
quantities of the Eclipse source code. The code shows a striking absence of the 
Java language feature of generics. It is hard to read a class' interface when 
methods return objects or takes parameters of raw types such as \type{List} or 
\type{Map}. This sometimes results in having to read a lot of source code to 
understand what is going on, instead of relying on the available interfaces. In 
addition, it results in a lot of ugly code, making the use of typecasting more 
of a rule than an exception.

\subsection{Composite Refactorings Will Not Appear as Atomic Actions}

\subsubsection{Missing Flexibility from JDT Refactorings}
The JDT refactorings are not made with composition of refactorings in mind. When 
a JDT refactoring is executed, it assumes that all conditions for it to be 
applied successfully can be found by reading source files that have been 
persisted to disk. They can only operate on the actual source material, and not 
(in-memory) copies thereof. This constitutes a major disadvantage when trying to 
compose refactorings, since if an exception occurs in the middle of a sequence 
of refactorings, it can leave the project in a state where the composite 
refactoring was only partially executed. It makes it hard to discard the changes 
done without monitoring and consulting the undo manager, an approach that is not 
bullet proof.

\subsubsection{Broken Undo History}
When designing a composed refactoring that is to be performed as a sequence of 
refactorings, you would like it to appear as a single change to the workspace.  
This implies that you would also like to be able to undo all the changes done by 
the refactoring in a single step. This is not the way it appears when a sequence 
of JDT refactorings is executed. It leaves the undo history filled up with 
individual undo actions corresponding to every single JDT refactoring in the 
sequence. This problem is not trivial to handle in Eclipse.  
\See{hacking_undo_history}

\section{Wishful Thinking}
\todoin{???}

\chapter{Composite Refactorings in Eclipse}

\section{A Simple Ad Hoc Model}
As pointed out in \myref{ch:jdt_refactorings}, the Eclipse JDT refactoring model 
is not very well suited for making composite refactorings. Therefore a simple 
model using changer objects (of type \type{RefaktorChanger}) is used as an 
abstraction layer on top of the existing Eclipse refactorings, instead of 
extending the \typewithref{org.eclipse.ltk.core.refactoring}{Refactoring} class.  

The use of an additional abstraction layer is a deliberate choice. It is due to 
the problem of creating a composite 
\typewithref{org.eclipse.ltk.core.refactoring}{Change} that can handle text 
changes that interfere with each other. Thus, a \type{RefaktorChanger} may, or 
may not, take advantage of one or more existing refactorings, but it is always 
intended to make a change to the workspace.

\subsection{A typical \type{RefaktorChanger}}
The typical refaktor changer class has two responsibilities, checking 
preconditions and executing the requested changes. This is not too different 
from the responsibilities of an LTK refactoring, with the distinction that a 
refaktor changer also executes the change, while an LTK refactoring is only 
responsible for creating the object that can later be used to do the job.

Checking of preconditions is typically done by an 
\typewithref{no.uio.ifi.refaktor.analyze.analyzers}{Analyzer}. If the 
preconditions validate, the upcoming changes are executed by an 
\typewithref{no.uio.ifi.refaktor.change.executors}{Executor}.

\section{The Extract and Move Method Refactoring}
%The Extract and Move Method Refactoring is implemented mainly using these 
%classes:
%\begin{itemize}
%  \item \type{ExtractAndMoveMethodChanger}
%  \item \type{ExtractAndMoveMethodPrefixesExtractor}
%  \item \type{Prefix}
%  \item \type{PrefixSet}
%\end{itemize}

\subsection{The Building Blocks}
This is a composite refactoring, and hence is built up using several primitive 
refactorings. These basic building blocks are, as its name implies, the 
\ExtractMethod refactoring\citing{refactoring} and the \MoveMethod 
refactoring\citing{refactoring}. In Eclipse, the implementations of these 
refactorings are found in the classes 
\typewithref{org.eclipse.jdt.internal.corext.refactoring.code}{ExtractMethodRefactoring} 
and 
\typewithref{org.eclipse.jdt.internal.corext.refactoring.structure}{MoveInstanceMethodProcessor}, 
where the last class is designed to be used together with the processor-based 
\typewithref{org.eclipse.ltk.core.refactoring.participants}{MoveRefactoring}.

\subsubsection{The ExtractMethodRefactoring Class}
This class is quite simple in its use. The only parameters it requires for 
construction is a compilation 
unit\typeref{org.eclipse.jdt.core.ICompilationUnit}, the offset into the source 
code where the extraction shall start, and the length of the source to be 
extracted. Then you have to set the method name for the new method together with 
its visibility and some not so interesting parameters.

\subsubsection{The MoveInstanceMethodProcessor Class}
For the Move Method, the processor requires a little more advanced input than  
the class for the Extract Method. For construction it requires a method 
handle\typeref{org.eclipse.jdt.core.IMethod} for the method that is to be moved. 
Then the target for the move have to be supplied as the variable binding from a 
chosen variable declaration. In addition to this, one have to set some 
parameters regarding setters/getters, as well as delegation.

To make a working refactoring from the processor, one have to create a 
\type{MoveRefactoring} with it.

\subsection{The ExtractAndMoveMethodChanger}

The \typewithref{no.uio.ifi.refaktor.changers}{ExtractAndMoveMethodChanger} 
class is a subclass of the class 
\typewithref{no.uio.ifi.refaktor.changers}{RefaktorChanger}. It is responsible 
for analyzing and finding the best target for, and also executing, a composition 
of the Extract Method and Move Method refactorings. This particular changer is 
the one of my changers that is closest to being a true LTK refactoring. It can 
be reworked to be one if the problems with overlapping changes are resolved. The 
changer requires a text selection and the name of the new method, or else a 
method name will be generated. The selection has to be of the type
\typewithref{no.uio.ifi.refaktor.utils}{CompilationUnitTextSelection}. This 
class is a custom extension to 
\typewithref{org.eclipse.jface.text}{TextSelection}, that in addition to the 
basic offset, length and similar methods, also carry an instance of the 
underlying compilation unit handle for the selection.

\subsubsection{The \type{ExtractAndMoveMethodAnalyzer}}
The analysis and precondition checking is done by the 
\typewithref{no.uio.ifi.refaktor.analyze.analyzers}{ExtractAnd\-MoveMethodAnalyzer}.  
First is check whether the selection is a valid selection or not, with respect 
to statement boundaries and that it actually contains any selections. Then it 
checks the legality of both extracting the selection and also moving it to 
another class. This checking of is performed by a range of checkers 
\see{checkers}.  If the selection is approved as legal, it is analyzed to find 
the presumably best target to move the extracted method to.

For finding the best suitable target the analyzer is using a 
\typewithref{no.uio.ifi.refaktor.analyze.collectors}{PrefixesCollector} that 
collects all the possible candidates for the refactoring. All the non-candidates 
is found by an 
\typewithref{no.uio.ifi.refaktor.analyze.collectors}{UnfixesCollector} that 
collects all the targets that will give some kind of error if used.  (For 
details about the property collectors, se \myref{propertyCollectors}.) All 
prefixes (and unfixes) are represented by a 
\typewithref{no.uio.ifi.refaktor.extractors}{Prefix}, and they are collected 
into sets of prefixes. The safe prefixes is found by subtracting from the set of 
candidate prefixes the prefixes that is enclosing any of the unfixes.  A prefix 
is enclosing an unfix if the unfix is in the set of its sub-prefixes.  As an 
example, \texttt{``a.b''} is enclosing \texttt{``a''}, as is \texttt{``a''}. The 
safe prefixes is unified in a \type{PrefixSet}. If a prefix has only one 
occurrence, and is a simple expression, it is considered unsuitable as a move 
target. This occurs in statements such as \texttt{``a.foo()''}. For such 
statements it bares no meaning to extract and move them. It only generates an 
extra method and the calling of it. 

The most suitable target for the refactoring is found by finding the prefix with 
the most occurrences. If two prefixes have the same occurrence count, but they 
differ in length, the longest of them is chosen.

\todoin{Clean up sections/subsections.}

\subsubsection{The \type{ExtractAndMoveMethodExecutor}}
If the analysis finds a possible target for the composite refactoring, it is 
executed by an 
\typewithref{no.uio.ifi.refaktor.change.executors}{ExtractAndMoveMethodExecutor}.  
It is composed of the two executors known as 
\typewithref{no.uio.ifi.refaktor.change.executors}{ExtractMethodRefactoringExecutor} 
and 
\typewithref{no.uio.ifi.refaktor.change.executors}{MoveMethodRefactoringExecutor}.  
The \type{ExtractAndMoveMethodExecutor} is responsible for gluing the two 
together by feeding the \type{MoveMethod\-RefactoringExecutor} with the 
resources needed after executing the extract method refactoring.  
\See{postExtractExecution}

\subsubsection{The \type{ExtractMethodRefactoringExecutor}}
This executor is responsible for creating and executing an instance of the 
\type{ExtractMethodRefactoring} class. It is also responsible for collecting 
some post execution resources that can be used to find the method handle for the 
extracted method, as well as information about its parameters, including the 
variable they originated from.

\subsubsection{The \type{MoveMethodRefactoringExecutor}}
This executor is responsible for creating and executing an instance of the 
\type{MoveRefactoring}. The move refactoring is a processor-based refactoring, 
and for the Move Method refactoring it is the \type{MoveInstanceMethodProcessor} 
that is used.

The handle for the method to be moved is found on the basis of the information 
gathered after the execution of the Extract Method refactoring. The only 
information the \type{ExtractMethodRefactoring} is sharing after its execution, 
regarding find the method handle, is the textual representation of the new 
method signature. Therefore it must be parsed, the strings for types of the 
parameters must be found and translated to a form that can be used to look up 
the method handle from its type handle. They have to be on the unresolved 
form.\todo{Elaborate?} The name for the type is found from the original 
selection, since an extracted method must end up in the same type as the 
originating method.

When analyzing a selection prior to performing the Extract Method refactoring, a 
target is chosen. It has to be a variable binding, so it is either a field or a 
local variable/parameter. If the target is a field, it can be used with the 
\type{MoveInstanceMethodProcessor} as it is, since the extracted method still is 
in its scope. But if the target is local to the originating method, the target 
that is to be used for the processor must be among its parameters. Thus the 
target must be found among the extracted method's parameters. This is done by 
finding the parameter information object that corresponds to the parameter that 
was declared on basis of the original target's variable when the method was 
extracted. (The extracted method must take one such parameter for each local 
variable that is declared outside the selection that is extracted.) To match the 
original target with the correct parameter information object, the key for the 
information object is compared to the key from the original target's binding.  
The source code must then be parsed to find the method declaration for the 
extracted method. The new target must be found by searching through the 
parameters of the declaration and choose the one that has the same type as the 
old binding from the parameter information object, as well as the same name that 
is provided by the parameter information object.


\subsection{The 
SearchBasedExtractAndMoveMethodChanger}\label{searchBasedExtractAndMoveMethodChanger}
\todoin{Write\ldots}

\subsection{Finding the IMethod}\label{postExtractExecution}
\todoin{Rename section. Write??}


\subsection{The Prefix Class}
This class exists mainly for holding data about a prefix, such as the expression 
that the prefix represents and the occurrence count of the prefix within a 
selection. In addition to this, it has some functionality such as calculating 
its sub-prefixes and intersecting it with another prefix. The definition of the 
intersection between two prefixes is a prefix representing the longest common 
expression between the two.

\subsection{The PrefixSet Class}
A prefix set holds elements of type \type{Prefix}. It is implemented with the 
help of a \typewithref{java.util}{HashMap} and contains some typical set 
operations, but it does not implement the \typewithref{java.util}{Set} 
interface, since the prefix set does not need all of the functionality a 
\type{Set} requires to be implemented. In addition It needs some other 
functionality not found in the \type{Set} interface. So due to the relatively 
limited use of prefix sets, and that it almost always needs to be referenced as 
such, and not a \type{Set<Prefix>}, it remains as an ad hoc solution to a 
concrete problem.

There are two ways adding prefixes to a \type{PrefixSet}. The first is through 
its \method{add} method. This works like one would expect from a set. It adds 
the prefix to the set if it does not already contain the prefix. The other way 
is to \emph{register} the prefix with the set. When registering a prefix, if the 
set does not contain the prefix, it is just added. If the set contains the 
prefix, its count gets incremented. This is how the occurrence count is handled.

The prefix set also computes the set of prefixes that is not enclosing any 
prefixes of another set. This is kind of a set difference operation only for 
enclosing prefixes.

\subsection{Hacking the Refactoring Undo 
History}\label{hacking_undo_history}
\todoin{Where to put this section?}

As an attempt to make multiple subsequent changes to the workspace appear as a 
single action (i.e. make the undo changes appear as such), I tried to alter 
the undo changes\typeref{org.eclipse.ltk.core.refactoring.Change} in the history 
of the refactorings.  

My first impulse was to remove the, in this case, last two undo changes from the 
undo manager\typeref{org.eclipse.ltk.core.refactoring.IUndoManager} for the 
Eclipse refactorings, and then add them to a composite 
change\typeref{org.eclipse.ltk.core.refactoring.CompositeChange} that could be 
added back to the manager. The interface of the undo manager does not offer a 
way to remove/pop the last added undo change, so a possible solution could be to 
decorate\citing{designPatterns} the undo manager, to intercept and collect the 
undo changes before delegating to the \method{addUndo} 
method\methodref{org.eclipse.ltk.core.refactoring.IUndoManager}{addUndo} of the 
manager. Instead of giving it the intended undo change, a null change could be 
given to prevent it from making any changes if run. Then one could let the 
collected undo changes form a composite change to be added to the manager.

There is a technical challenge with this approach, and it relates to the undo 
manager, and the concrete implementation 
UndoManager2\typeref{org.eclipse.ltk.internal.core.refactoring.UndoManager2}.  
This implementation is designed in a way that it is not possible to just add an 
undo change, you have to do it in the context of an active 
operation\typeref{org.eclipse.core.commands.operations.TriggeredOperations}.  
One could imagine that it might be possible to trick the undo manager into 
believing that you are doing a real change, by executing a refactoring that is 
returning a kind of null change that is returning our composite change of undo 
refactorings when it is performed.

Apart from the technical problems with this solution, there is a functional 
problem: If it all had worked out as planned, this would leave the undo history 
in a dirty state, with multiple empty undo operations corresponding to each of 
the sequentially executed refactoring operations, followed by a composite undo 
change corresponding to an empty change of the workspace for rounding of our 
composite refactoring. The solution to this particular problem could be to 
intercept the registration of the intermediate changes in the undo manager, and 
only register the last empty change.

Unfortunately, not everything works as desired with this solution. The grouping 
of the undo changes into the composite change does not make the undo operation 
appear as an atomic operation. The undo operation is still split up into 
separate undo actions, corresponding to the change done by its originating
refactoring. And in addition, the undo actions has to be performed separate in 
all the editors involved. This makes it no solution at all, but a step toward 
something worse.

There might be a solution to this problem, but it remains to be found. The 
design of the refactoring undo management is partly to be blamed for this, as it 
it is to complex to be easily manipulated.




\chapter{Analyzing Source Code in Eclipse}

\section{The Java model}\label{javaModel}
The Java model of Eclipse is its internal representation of a Java project. It 
is light-weight, and has only limited possibilities for manipulating source 
code. It is typically used as a basis for the Package Explorer in Eclipse.

The elements of the Java model is only handles to the underlying elements. This 
means that the underlying element of a handle does not need to actually exist.  
Hence the user of a handle must always check that it exist by calling the 
\method{exists} method of the handle.

The handles with descriptions is listed in \myref{tab:javaModel}.

\begin{table}[h]
  \centering

  \newcolumntype{L}[1]{>{\hsize=#1\hsize\raggedright\arraybackslash}X}%
  % sum must equal number of columns (3)
  \begin{tabularx}{\textwidth}{| L{0.7} | L{1.1} | L{1.2} |} 
    \hline
    \textbf{Project Element} & \textbf{Java Model element} & 
    \textbf{Description} \\
    \hline
    Java project & \type{IJavaProject} & The Java project which contains all other objects. \\
    \hline
    Source folder /\linebreak[2] binary folder /\linebreak[3] external library & 
    \type{IPackageFragmentRoot} & Hold source or binary files, can be a folder 
    or a library (zip / jar file). \\
    \hline
    Each package & \type{IPackageFragment} & Each package is below the 
    \type{IPackageFragmentRoot}, sub-packages are not leaves of the package, 
    they are listed directed under \type{IPackageFragmentRoot}. \\
    \hline
    Java Source file & \type{ICompilationUnit} & The Source file is always below 
    the package node. \\
    \hline
    Types /\linebreak[2] Fields /\linebreak[3] Methods & \type{IType} / 
    \linebreak[0]
    \type{IField} /\linebreak[3] \type{IMethod} & Types, fields and methods. \\
    \hline
  \end{tabularx}
  \caption{The elements of the Java Model. {\footnotesize Taken from 
    \url{http://www.vogella.com/tutorials/EclipseJDT/article.html}}}
  \label{tab:javaModel}
\end{table}

The hierarchy of the Java Model is shown in \myref{fig:javaModel}.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[%
  grow via three points={one child at (0,-0.7) and
  two children at (0,-0.7) and (0,-1.4)},
  edge from parent path={(\tikzparentnode.south west)+(0.5,0) |- 
  (\tikzchildnode.west)}]
  \tikzstyle{every node}=[draw=black,thick,anchor=west]
  \tikzstyle{selected}=[draw=red,fill=red!30]
  \tikzstyle{optional}=[dashed,fill=gray!50]
  \node {\type{IJavaProject}}
    child { node {\type{IPackageFragmentRoot}}
      child { node {\type{IPackageFragment}}
        child { node {\type{ICompilationUnit}}
          child { node {\type{IType}}
            child { node {\type{\{ IType \}*}}
              child { node {\type{\ldots}}}
            }
            child [missing] {}
            child { node {\type{\{ IField \}*}}}
            child { node {\type{IMethod}}
              child { node {\type{\{ IType \}*}}
                child { node {\type{\ldots}}}
              }
            }
            child [missing] {}
            child [missing] {}
            child { node {\type{\{ IMethod \}*}}}
          }
          child [missing] {}
          child [missing] {}
          child [missing] {}
          child [missing] {}
          child [missing] {}
          child [missing] {}
          child [missing] {}
          child { node {\type{\{ IType \}*}}}
        }
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child [missing] {}
        child { node {\type{\{ ICompilationUnit \}*}}}
      }
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child [missing] {}
      child { node {\type{\{ IPackageFragment \}*}}}
    }
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child [missing] {}
    child { node {\type{\{ IPackageFragmentRoot \}*}}}
    ;
  \end{tikzpicture}
  \caption{The Java model of Eclipse. ``\type{\{ SomeElement \}*}'' means 
  \type{SomeElement} zero or more times. For recursive structures, 
  ``\type{\ldots}'' is used.}
  \label{fig:javaModel}
\end{figure}

\section{The Abstract Synax Tree}
Eclipse is following the common paradigm of using an abstract syntaxt tree for 
source code analysis and manipulation.

When parsing program source code into something that can be used as a foundation 
for analysis, the start of the process follows the same steps as in a compiler.  
This is all natural, because the way a compiler anayzes code is no different 
from how source manipulation programs would do it, except for some properties of 
code that is analyzed in the parser, and that they may be differing in what 
kinds of properties they analyze.  Thus the process of translation source code 
into a structure that is suitable for analyzing, can be seen as a kind of 
interrupted compilation process \see{fig:interruptedCompilationProcess}.

\begin{figure}[h]
  \centering
  \tikzset{
    base/.style={anchor=north, align=center, rectangle, minimum height=1.4cm},
    basewithshadow/.style={base, drop shadow, fill=white},
    outlined/.style={basewithshadow, draw, rounded corners, minimum 
    width=0.4cm},
    primary/.style={outlined, font=\bfseries},
    dashedbox/.style={outlined, dashed},
    arrowpath/.style={black, align=center, font=\small},
    processarrow/.style={arrowpath, ->, >=angle 90, shorten >=1pt},
  }
  \begin{tikzpicture}[node distance=1.3cm and 3cm, scale=1, every 
    node/.style={transform shape}]
    \node[base](AuxNode1){\small source code};
    \node[primary, right=of AuxNode1, xshift=-2.5cm](Scanner){Scanner};
    \node[primary, right=of Scanner, xshift=0.5cm](Parser){Parser};
    \node[dashedbox, below=of Parser](SemanticAnalyzer){Semantic\\Analyzer};
    \node[dashedbox, left=of SemanticAnalyzer](SourceCodeOptimizer){Source 
    Code\\Optimizer};
    \node[dashedbox, below=of SourceCodeOptimizer
    ](CodeGenerator){Code\\Generator};
    \node[dashedbox, right=of CodeGenerator](TargetCodeOptimizer){Target 
    Code\\Optimizer};
    \node[base, right=of TargetCodeOptimizer](AuxNode2){};

    \draw[processarrow](AuxNode1) -- (Scanner);

    \path[arrowpath] (Scanner) -- node [sloped](tokens){tokens}(Parser);
    \draw[processarrow](Scanner) -- (tokens) -- (Parser);

    \path[arrowpath] (Parser) -- node (syntax){syntax 
    tree}(SemanticAnalyzer);
    \draw[processarrow](Parser) -- (syntax) -- (SemanticAnalyzer);

    \path[arrowpath] (SemanticAnalyzer) -- node 
    [sloped](annotated){annotated\\tree}(SourceCodeOptimizer);
    \draw[processarrow, dashed](SemanticAnalyzer) -- (annotated) -- 
    (SourceCodeOptimizer);

    \path[arrowpath] (SourceCodeOptimizer) -- node 
    (intermediate){intermediate code}(CodeGenerator);
    \draw[processarrow, dashed](SourceCodeOptimizer) -- (intermediate) --
    (CodeGenerator);

    \path[arrowpath] (CodeGenerator) -- node [sloped](target1){target 
    code}(TargetCodeOptimizer);
    \draw[processarrow, dashed](CodeGenerator) -- (target1) --
    (TargetCodeOptimizer);

    \path[arrowpath](TargetCodeOptimizer) -- node [sloped](target2){target 
    code}(AuxNode2);
    \draw[processarrow, dashed](TargetCodeOptimizer) -- (target2) (AuxNode2);
  \end{tikzpicture}
  \caption{Interrupted compilation process. {\footnotesize (Full compilation 
    process borrowed from \emph{Compiler construction: principles and practice} 
    by Kenneth C.  Louden\citing{louden1997}.)}}
  \label{fig:interruptedCompilationProcess}
\end{figure}

The process starts with a \emph{scanner}, or lexer. The job of the scanner is to 
read the source code and divide it into tokens for the parser. Therefore, it is 
also sometimes called a tokenizer. A token is a logical unit, defined in the 
language specification, consisting of one or more consecutive characters.  In 
the java language the tokens can for instance be the \var{this} keyword, a curly 
bracket \var{\{} or a \var{nameToken}. It is recognized by the scanner on the 
basis of something eqivalent of a regular expression. This part of the process 
is often implemented with the use of a finite automata. In fact, it is common to 
specify the tokens in regular expressions, that in turn is translated into a 
finite automata lexer. This process can be automated.

The program component used to translate a a stream of tokens into something 
meaningful, is called a parser. A parser is fed tokens from the scanner and 
performs an analysis of the structure of a program. It verifies that the syntax 
is correct according to the grammar rules of a language, that is usually 
specified in a context-free grammar, and often in a variant of the 
\emph{Backus--Naur 
Form}\footnote{\url{https://en.wikipedia.org/wiki/Backus-Naur\_Form}}. The 
result coming from the parser is in the form of an \emph{Abstract Syntax Tree}, 
AST for short. It is called \emph{abstract}, because the structure does not 
contain all of the tokens produced by the scanner. It only contain logical 
constructs, and because it forms a tree, all kinds of parentheses and brackets 
are implicit in the structure. It is this AST that is used when performing the 
semantic analysis of the code.

As an example we can think of the expression \code{(5 + 7) * 2}. The root of 
this tree would in Eclipse be an \type{InfixExpression} with the operator
\var{TIMES}, and a left operand that is also an \type{InfixExpression} with the 
operator \var{PLUS}. The left operand \type{InfixExpression}, has in turn a left 
operand of type \type{NumberLiteral} with the value \var{``5''} and a right 
operand \type{NumberLiteral} with the value \var{``7''}.  The root will have a 
right operand of type \type{NumberLiteral} and value \var{``2''}. The AST for 
this expression is illustrated in \myref{fig:astInfixExpression}.

Contrary to the Java Model, an abstract syntaxt tree is a heavy-weight 
representation of source code. It contains information about propertes like type 
bindings for variables and variable bindings for names. 


\begin{figure}[h]
  \centering
  \begin{tikzpicture}[scale=0.8]
  \tikzset{level distance=40pt}
  \tikzset{sibling distance=5pt}
  \tikzstyle{thescale}=[scale=0.8]
  \tikzset{every tree node/.style={align=center}}
  \tikzset{edge from parent/.append style={thick}}
  \tikzstyle{inode}=[rectangle,rounded corners,draw,fill=lightgray,drop 
  shadow,align=center]
  \tikzset{every internal node/.style={inode}}
  \tikzset{every leaf node/.style={draw=none,fill=none}}

  \Tree [.\type{InfixExpression} [.\type{InfixExpression}
    [.\type{NumberLiteral} \var{``5''} ]  [.\type{Operator} \var{PLUS} ] 
    [.\type{NumberLiteral} \var{``7''} ] ]
  [.\type{Operator} \var{TIMES} ]
    [.\type{NumberLiteral} \var{``2''} ] 
  ]
  \end{tikzpicture}
  \caption{The abstract syntax tree for the expression \code{(5 + 7) * 2}.}
  \label{fig:astInfixExpression}
\end{figure}

\subsection{The AST in Eclipse}
In Eclipse, every node in the AST is a child of the abstract superclass 
\typewithref{org.eclipse.jdt.core.dom}{ASTNode}. Every \type{ASTNode}, among a 
lot of other things, provides information about its position and length in the 
source code, as well as a reference to its parent and to the root of the tree.

The root of the AST is always of type \type{CompilationUnit}. It is not the same 
as an instance of an \type{ICompilationUnit}, which is the compilation unit 
handle of the Java model. The children of a \type{CompilationUnit} is an 
optional \type{PackageDeclaration}, zero or more nodes of type 
\type{ImportDecaration} and all its top-level type declarations that has node 
types \type{AbstractTypeDeclaration}.

An \type{AbstractType\-Declaration} can be one of the types 
\type{AnnotationType\-Declaration}, \type{Enum\-Declaration} or 
\type{Type\-Declaration}. The children of an \type{AbstractType\-Declaration} 
must be a subtype of a \type{BodyDeclaration}. These subtypes are: 
\type{AnnotationTypeMember\-Declaration}, \type{EnumConstant\-Declaration}, 
\type{Field\-Declaration}, \type{Initializer} and \type{Method\-Declaration}.

Of the body declarations, the \type{Method\-Declaration} is the most interesting 
one. Its children include lists of modifiers, type parameters, parameters and 
exceptions. It has a return type node and a body node. The body, if present, is 
of type \type{Block}. A \type{Block} is itself a \type{Statement}, and its 
children is a list of \type{Statement} nodes.

There are too many types of the abstract type \type{Statement} to list up, but 
there exists a subtype of \type{Statement} for every statement type of Java, as 
one would expect. This also applies to the abstract type \type{Expression}.  
However, the expression \type{Name} is a little special, since it is both used 
as an operand in compound expressions, as well as for names in type declarations 
and such.

There is an overview of some of the structure of an Eclipse AST in 
\myref{fig:astEclipse}.

\begin{figure}[h]
  \centering
  \begin{tikzpicture}[scale=0.8]
  \tikzset{level distance=50pt}
  \tikzset{sibling distance=5pt}
  \tikzstyle{thescale}=[scale=0.8]
  \tikzset{every tree node/.style={align=center}}
  \tikzset{edge from parent/.append style={thick}}
  \tikzstyle{inode}=[rectangle,rounded corners,draw,fill=lightgray,drop 
  shadow,align=center]
  \tikzset{every internal node/.style={inode}}
  \tikzset{every leaf node/.style={draw=none,fill=none}}

  \Tree [.\type{CompilationUnit} [.\type{[ PackageDeclaration ]} [.\type{Name} ] 
  [.\type{\{ Annotation \}*} ] ]
  [.\type{\{ ImportDeclaration \}*} [.\type{Name} ] ]
    [.\type{\{ AbstractTypeDeclaration \}+} [.\node(site){\type{\{ 
    BodyDeclaration \}*}}; ] [.\type{SimpleName} ] ]
  ]
  \begin{scope}[shift={(0.5,-6)}]
    \node[inode,thescale](root){\type{MethodDeclaration}};
    \node[inode,thescale](modifiers) at (4.5,-5){\type{\{ IExtendedModifier \}*} 
    \\ {\footnotesize (Of type \type{Modifier} or \type{Annotation})}};
    \node[inode,thescale](typeParameters) at (-6,-3.5){\type{\{ TypeParameter 
    \}*}};
    \node[inode,thescale](parameters) at (-5,-5){\type{\{ 
    SingleVariableDeclaration \}*} \\ {\footnotesize (Parameters)}};
    \node[inode,thescale](exceptions) at (5,-3){\type{\{ Name \}*} \\ 
    {\footnotesize (Exceptions)}};
    \node[inode,thescale](return) at (-6.5,-2){\type{Type} \\ {\footnotesize 
    (Return type)}};
    \begin{scope}[shift={(0,-5)}]
      \Tree [.\node(body){\type{[ Block ]} \\ {\footnotesize (Body)}};
      [.\type{\{ Statement \}*} [.\type{\{ Expression \}*} ]
        [.\type{\{ Statement \}*} [.\type{\ldots} ]]
      ]
      ]
    \end{scope}
  \end{scope}
  \draw[->,>=triangle 90,shorten >=1pt](root.east)..controls +(east:2) and 
  +(south:1)..(site.south);

  \draw (root.south) -- (modifiers);
  \draw (root.south) -- (typeParameters);
  \draw (root.south) -- ($ (parameters.north) + (2,0) $);
  \draw (root.south) -- (exceptions);
  \draw (root.south) -- (return);
  \draw (root.south) -- (body);

  \end{tikzpicture}
  \caption{The format of the abstract syntax tree in Eclipse.}
  \label{fig:astEclipse}
\end{figure}
\todoin{Add more to the AST format tree? \myref{fig:astEclipse}}

\section{The ASTVisitor}\label{astVisitor}
So far, the only thing that has been adressed is how the the data that is going 
to be the basis for our analysis is structured. Another aspect of it is how we 
are going to traverse the AST to gather the information we need, so we can 
conclude about the properties we are analysing. It is of course possible to 
start at the top of the tree, and manually search through its nodes for the ones 
we are looking for, but that is a bit inconvenient. To be able to efficiently 
utilize such an approach, we would need to make our own framework for traversing 
the tree and visiting only the types of nodes we are after. Luckily, this 
functionality is already provided in Eclipse, by its 
\typewithref{org.eclipse.jdt.core.dom}{ASTVisitor}.

The Eclipse AST, together with its \type{ASTVisitor}, follows the \emph{Visitor} 
pattern\citing{designPatterns}. The intent of this design pattern is to 
facilitate extending the functionality of classes without touching the classes 
themselves.

Let us say that there is a class hierarchy of \emph{Elements}. These elements 
all have a method \method{accept(Visitor visitor)}. In its simplest form, the 
\method{accept} method just calls the \method{visit} method of the visitor with 
itself as an argument, like this: \code{visitor.visit(this)}.  For the visitors 
to be able to extend the functionality of all the classes in the elements 
hierarchy, each \type{Visitor} must have one visit method for each concrete 
class in the hierarchy. Say the hierarchy consists of the concrete classes 
\type{ConcreteElementA} and \type{ConcreteElementB}. Then each visitor must have 
the (possibly empty) methods \method{visit(ConcreteElementA element)} and 
\method{visit(ConcreteElementB element)}. This scenario is depicted in 
\myref{fig:visitorPattern}.

\begin{figure}[h]
  \centering
  \tikzstyle{abstract}=[rectangle, draw=black, fill=white, drop shadow, text 
  centered, anchor=north, text=black, text width=6cm, every one node 
part/.style={align=center, font=\bfseries\itshape}]
  \tikzstyle{concrete}=[rectangle, draw=black, fill=white, drop shadow, text 
  centered, anchor=north, text=black, text width=6cm]
  \tikzstyle{inheritarrow}=[->, >=open triangle 90, thick]
  \tikzstyle{commentarrow}=[->, >=angle 90, dashed]
  \tikzstyle{line}=[-, thick]
  \tikzset{every one node part/.style={align=center, font=\bfseries}}
  \tikzset{every second node part/.style={align=center, font=\ttfamily}}
        
  \begin{tikzpicture}[node distance=1cm, scale=0.8, every node/.style={transform 
    shape}]
    \node (Element) [abstract, rectangle split, rectangle split parts=2]
        {
          \nodepart{one}{Element}
          \nodepart{second}{+accept(visitor: Visitor)}
        };
    \node (AuxNode01) [text width=0, minimum height=2cm, below=of Element] {};
    \node (ConcreteElementA) [concrete, rectangle split, rectangle split 
    parts=2, left=of AuxNode01]
        {
          \nodepart{one}{ConcreteElementA}
          \nodepart{second}{+accept(visitor: Visitor)}
        };
    \node (ConcreteElementB) [concrete, rectangle split, rectangle split 
    parts=2, right=of AuxNode01]
        {
          \nodepart{one}{ConcreteElementB}
          \nodepart{second}{+accept(visitor: Visitor)}
        };

    \node[comment, below=of ConcreteElementA] (CommentA) {visitor.visit(this)};

    \node[comment, below=of ConcreteElementB] (CommentB) {visitor.visit(this)};

    \node (AuxNodeX) [text width=0, minimum height=1cm, below=of AuxNode01] {};

    \node (Visitor) [abstract, rectangle split, rectangle split parts=2, 
    below=of AuxNodeX]
        {
          \nodepart{one}{Visitor}
          \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
        };
    \node (AuxNode02) [text width=0, minimum height=2cm, below=of Visitor] {};
    \node (ConcreteVisitor1) [concrete, rectangle split, rectangle split 
    parts=2, left=of AuxNode02]
        {
          \nodepart{one}{ConcreteVisitor1}
          \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
        };
    \node (ConcreteVisitor2) [concrete, rectangle split, rectangle split 
    parts=2, right=of AuxNode02]
        {
          \nodepart{one}{ConcreteVisitor2}
          \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
        };

    
    \draw[inheritarrow] (ConcreteElementA.north) -- ++(0,0.7) -| 
    (Element.south);
    \draw[line] (ConcreteElementA.north) -- ++(0,0.7) -| 
    (ConcreteElementB.north);

    \draw[inheritarrow] (ConcreteVisitor1.north) -- ++(0,0.7) -| 
    (Visitor.south);
    \draw[line] (ConcreteVisitor1.north) -- ++(0,0.7) -| 
    (ConcreteVisitor2.north);

    \draw[commentarrow] (CommentA.north) -- (ConcreteElementA.south);
    \draw[commentarrow] (CommentB.north) -- (ConcreteElementB.south);

    
  \end{tikzpicture}
  \caption{The Visitor Pattern.}
  \label{fig:visitorPattern}
\end{figure}

The use of the visitor pattern can be appropriate when the hierarchy of elements 
is mostly stable, but the family of operations over its elements is constantly 
growing. This is clearly the cas for the Eclipse AST, since the hierarchy of 
type \type{ASTNode} is very stable, but the functionality of its elements is 
extended every time someone needs to operate on the AST. Another aspect of the 
Eclipse implementation is that it is a public API, and the visitor pattern is an 
easy way to provide access to the nodes in the tree.

The version of the visitor pattern implemented for the AST nodes in Eclipse also 
provides an elegant way to traverse the tree. It does so by following the 
convention that every node in the tree first let the visitor visit itself, 
before it also makes all its children accept the visitor. The children are only 
visited if the visit method of their parent returns \var{true}. This pattern 
then makes for a prefix traversal of the AST. If postfix traversal is desired, 
the visitors also has \method{endVisit} methods for each node type, that is 
called after the \method{visit} method for a node. In addition to these visit 
methods, there are also the methods \method{preVisit(ASTNode)}, 
\method{postVisit(ASTNode)} and \method{preVisit2(ASTNode)}. The 
\method{preVisit} method is called before the type-specific \method{visit} 
method. The \method{postVisit} method is called after the type-specific 
\method{endVisit}. The type specific \method{visit} is only called if 
\method{preVisit2} returns \var{true}. Overriding the \method{preVisit2} is also 
altering the behavior of \method{preVisit}, since the default implementation is 
responsible for calling it.

An example of a trivial \type{ASTVisitor} is shown in 
\myref{lst:astVisitorExample}.

\begin{listing}
\begin{minted}{java}
public class CollectNamesVisitor extends ASTVisitor {
    Collection<Name> names = new LinkedList<Name>();

    @Override
    public boolean visit(QualifiedName node) {
      names.add(node);
      return false;
    }

    @Override
    public boolean visit(SimpleName node) {
        names.add(node);
        return true;
    }
} 
\end{minted}
\caption{An \type{ASTVisitor} that visits all the names in a subtree and adds 
them to a collection, except those names that are children of any 
\type{QualifiedName}.}
\label{lst:astVisitorExample}
\end{listing}

\section{Property collectors}\label{propertyCollectors}
The prefixes and unfixes are found by property 
collectors\typeref{no.uio.ifi.refaktor.extractors.collectors.PropertyCollector}.  
A property collector is of the \type{ASTVisitor} type, and thus visits nodes of 
type \type{ASTNode} of the abstract syntax tree \see{astVisitor}.

\subsection{The PrefixesCollector}
The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{PrefixesCollector} 
finds prefixes that makes up the basis for calculating move targets for the 
Extract and Move Method refactoring. It visits expression 
statements\typeref{org.eclipse.jdt.core.dom.ExpressionStatement} and creates 
prefixes from its expressions in the case of method invocations. The prefixes 
found is registered with a prefix set, together with all its sub-prefixes.

\subsection{The UnfixesCollector}\label{unfixes}
The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{UnfixesCollector} 
finds unfixes within a selection. That is prefixes that cannot be used as a 
basis for finding a move target in a refactoring.

An unfix can be a name that is assigned to within a selection. The reason that 
this cannot be allowed, is that the result would be an assignment to the 
\type{this} keyword, which is not valid in Java \see{eclipse_bug_420726}.

Prefixes that originates from variable declarations within the same selection 
are also considered unfixes. This is because when a method is moved, it needs to 
be called through a variable. If this variable is also within the method that is 
to be moved, this obviously cannot be done.

Also considered as unfixes are variable references that are of types that is not 
suitable for moving a methods to. This can be either because it is not 
physically possible to move the method to the desired class or that it will 
cause compilation errors by doing so.

If the type binding for a name is not resolved it is considered and unfix. The 
same applies to types that is only found in compiled code, so they have no 
underlying source that is accessible to us. (E.g. the \type{java.lang.String} 
class.)

Interfaces types are not suitable as targets. This is simply because interfaces 
in java cannot contain methods with bodies. (This thesis does not deal with 
features of Java versions later than Java 7. Java 8 has interfaces with default 
implementations of methods.) Neither are local types allowed. This accounts for 
both local and anonymous classes. Anonymous classes are effectively the same as 
interface types with respect to unfixes. Local classes could in theory be used 
as targets, but this is not possible due to limitations of the implementation of 
the Extract and Move Method refactoring. The problem is that the refactoring is 
done in two steps, so the intermediate state between the two refactorings would 
not be legal Java code. In the case of local classes, the problem is that, in 
the intermediate step, a selection referencing a local class would need to take 
the local class as a parameter if it were to be extracted to a new method. This 
new method would need to live in the scope of the declaring class of the 
originating method. The local class would then not be in the scope of the 
extracted method, thus bringing the source code into an illegal state. One could 
imagine that the method was extracted and moved in one operation, without an 
intermediate state. Then it would make sense to include variables with types of 
local classes in the set of legal targets, since the local classes would then be 
in the scopes of the method calls. If this makes any difference for software 
metrics that measure coupling would be a different discussion.

\begin{listing}
\begin{multicols}{2}
\begin{minted}[]{java}
// Before
void declaresLocalClass() {
  class LocalClass {
    void foo() {}
    void bar() {}
  }

  LocalClass inst =
    new LocalClass();
  inst.foo();
  inst.bar();
}
\end{minted}

\columnbreak

\begin{minted}[]{java}
// After Extract Method
void declaresLocalClass() {
  class LocalClass {
    void foo() {}
    void bar() {}
  }

  LocalClass inst =
    new LocalClass();
  fooBar(inst);
}

// Intermediate step
void fooBar(LocalClass inst) {
  inst.foo();
  inst.bar();
}
\end{minted}
\end{multicols}
\caption{When Extract and Move Method tries to use a variable with a local type 
as the move target, an intermediate step is taken that is not allowed. Here: 
\type{LocalClass} is not in the scope of \method{fooBar} in its intermediate 
location.}
\label{lst:extractMethod_LocalClass}
\end{listing}

The last class of names that are considered unfixes is names used in null tests.  
These are tests that reads like this: if \texttt{<name>} equals \var{null} then 
do something. If allowing variables used in those kinds of expressions as 
targets for moving methods, we would end up with code containing boolean 
expressions like \texttt{this == null}, which would not be meaningful, since 
\var{this} would never be \var{null}.


\subsection{The ContainsReturnStatementCollector}
The 
\typewithref{no.uio.ifi.refaktor.analyze.collectors}{ContainsReturnStatementCollector} 
is a very simple property collector. It only visits the return statements within 
a selection, and can report whether it encountered a return statement or not.

\subsection{The LastStatementCollector}
The \typewithref{no.uio.ifi.refaktor.analyze.collectors}{LastStatementCollector} 
collects the last statement of a selection. It does so by only visiting the top 
level statements of the selection, and compares the textual end offset of each 
encuntered statement with the end offset of the previous statement found.

\section{Checkers}\label{checkers}
The checkers are a range of classes that checks that selections complies with 
certian criterias. If a 
\typewithref{no.uio.ifi.refaktor.analyze.analyzers}{Checker} fails, it throws a 
\type{CheckerException}. The checkers are managed by the 
\type{LegalStatementsChecker}, which does not, in fact, implement the 
\type{Checker} interface. It does, however, run all the checkers registered with 
it, and reports that all statements are considered legal if no 
\type{CheckerException} is thrown. Many of the checkers either extends the 
\type{PropertyCollector} or utilizes one or more property collectors to verify 
some criterias. The checkers registered with the \type{LegalStatementsChecker} 
are described next. They are run in the order presented below.

\subsection{The EnclosingInstanceReferenceChecker}
The purpose of this checker is to verify that the names in a selection is not 
referencing any enclosing instances. This is for making sure that all references 
is legal in a method that is to be moved. Theoretically, some situations could 
be easily solved my passing a reference to the referenced class with the moved 
method (e.g. when calling public methods), but the dependency on the 
\type{MoveInstanceMethodProcessor} prevents this.

The 
\typewithref{no.uio.ifi.refaktor.analyze.analyzers}{EnclosingInstanceReferenceChecker} 
is a modified version of the 
\typewithref{org.eclipse.jdt.internal.corext.refactoring.structure.MoveInstanceMethodProcessor}{EnclosingInstanceReferenceFinder} 
from the \type{MoveInstanceMethodProcessor}. Wherever the 
\type{EnclosingInstanceReferenceFinder} would create a fatal error status, the 
checker throws a \type{CheckerException}.

It works by first finding all of the enclosing types of a selection. Thereafter 
it visits all its simple names to check that they are not references to 
variables or methods declared in any of the enclosing types. In addition the 
checker visits \var{this}-expressions to verify that no such expressions is 
qualified with any name.

\subsection{The ReturnStatementsChecker}\label{returnStatementsChecker}
\todoin{Write\ldots/change implementation/use control flow graph?}

\subsection{The AmbiguousReturnValueChecker}
This checker verifies that there are no \emph{ambiguous return statements} in a 
selection. The problem with ambiguous return statements arise when a selection 
is chosen to be extracted into a new method, but it needs to return more than 
one value from that method.  This problem occurs in two situations.  The first 
situation arise when there is more than one local variable that is both assigned 
to within a selection and also referenced after the selection. The other 
situation occur when there is only one such assignment, but there is also one or 
more return statements in the selection.

First the checker needs to collect some data. Those data are the binding keys 
for all simple names that are assigned to within the selection, including 
variable declarations, but excluding fields. The checker also collects whether 
there exists a return statement in the selection or not. No further checks of 
return statements are needed, since, at this point, the selection is already 
checked for illegal return statements \see{returnStatementsChecker}.

After the binding keys of the assignees are collected, the checker searches the 
part of the enclosing method that is after the selection for references whose 
binding keys are among the the collected keys. If more than one unique referral 
is found, or only one referral is found, but the selection also contains a 
return statement, we have a situation with an ambiguous return value, and an 
exception is thrown.

%\todoin{Explain why we do not need to consider variables assigned inside 
%local/anonymous classes. (The referenced variables need to be final and so 
%on\ldots)}

\subsection{The IllegalStatementsChecker}
This checker is designed to check for illegal statements.

Any use of the \var{super} keyword is prohibited, since its meaning is altered 
when moving a method to another class.

For a \emph{break} statement, there is two situations to consider: A break 
statement with or without a label. If the break statement has a label, it is 
checked that whole of the labeled statement is inside the selection. Since a 
label does not have any binding information, we have to search upwards in the 
AST to find the \type{LabeledStatement} that corresponds to the label from the 
break statement, and check that it is contained in the selection. If the break 
statement does not have a label attached to it, it is checked that its innermost 
enclosing loop or switch statement also is inside the selection.

The situation for a \emph{continue} statement is the same as for a break 
statement, except that it is not allowed inside switch statements.

Regarding \emph{assignments}, two types of assignments is allowed: Assignment to 
a non-final variable and assignment to an array access. All other assignments is 
regarded illegal.

\todoin{Finish\ldots}


\chapter{Benchmarking}
\todoin{Better name than ``benchmarking''?}
This part of the master project is located in the Eclipse project 
\code{no.uio.ifi.refaktor.benchmark}. The purpose of it is to run the equivalent 
of the \type{SearchBasedExtractAndMoveMethodChanger} 
\see{searchBasedExtractAndMoveMethodChanger} over a larger software project, 
both to test its roubustness but also its effect on different software metrics.

\section{The benchmark setup}
The benchmark itself is set up as a \emph{JUnit} test case. This is a convenient 
setup, and utilizes the \emph{JUnit Plugin Test Launcher}. This provides us a 
with a fully functional Eclipse workbench. Most importantly, this gives us 
access to the Java Model of Eclipse \see{javaModel}.

\subsection{The ProjectImporter}
The Java project that is going to be used as the data for the benchmark, must be 
imported into the JUnit workspace. This is done by the 
\typewithref{no.uio.ifi.refaktor.benchmark}{ProjectImporter}. The importer 
require the absolute path to the project description file. It is named 
\code{.project} and is located at the root of the project directory.

The project description is loaded to find the name of the project to be 
imported. The project that shall be the destination for the import is created in 
the workspace, on the base of the name from the description. Then an import 
operation is created, based on both the source and destination information. The 
import operation is run to perform the import.

I have found no simple API call to accomplish what the importer does, which 
tells me that it may not be too many people performing this particular action. 
The solution to the problem was found on \emph{Stack 
Overflow}\footnote{\url{https://stackoverflow.com/questions/12401297}}. It 
contains enough dirty details to be considered unconvenient to use, if not 
wrapping it in a class like my \type{ProjectImporter}. One would probably have 
to delve into the source code for the import wizard to find out how the import 
operation works, if no one had already done it.

\section{Statistics}
Statistics for the analysis and changes is captured by the 
\typewithref{no.uio.ifi.refaktor.aspects}{StatisticsAspect}. This an 
\emph{aspect} written in \emph{AspectJ}.

\subsection{AspectJ}
\emph{AspectJ}\footnote{\url{http://eclipse.org/aspectj/}} is an extension to 
the Java language, and facilitates combining aspect-oriented programming with 
the object-oriented programming in Java.

Aspect-oriented programming is a programming paradigm that is meant to isolate 
so-called \emph{cross-cutting concerns} into their own modules. These 
cross-cutting concerns are functionalities that spans over multiple classes, but 
may not belong naturally in any of them. It can be functionality that does not 
concern the business logic of an application, and thus may be a burden when 
entangled with parts of the source code it does not really belong. Examples 
include logging, debugging, optimization and security.

Aspects are interacting with other modules by defining advices. The concept of 
an \emph{advice} is known from both aspect-oriented and functional 
programming\citing{wikiAdvice2014}. It is a function that modifies another 
function when the latter is run. An advice in AspectJ is somewhat similar to a 
method in Java. It is meant to alter the behavior of other methods, and contains 
a body that is executed when it is applied.

An advice can be applied at a defined \emph{pointcut}. A pointcut picks out one 
or more \emph{join points}. A join point is a well-defined point in the 
execution of a program. It can occur when calling a method defined for a 
particular class, when calling all methods with the same name, 
accessing/assigning to a particular field of a given class and so on. An advice 
can be declared to run both before, after returning from a pointcut, when there 
is thrown an exception in the pointcut or after the pointcut either returns or 
throws an exception.  In addition to picking out join points, a pointcut can 
also bind variables from its context, so they can be accessed in the body of an 
advice. An example of a pointcut and an advice is found in 
\myref{lst:aspectjExample}.

\begin{listing}[h]
\begin{minted}{java}
pointcut methodAnalyze(
  SearchBasedExtractAndMoveMethodAnalyzer analyzer) :
    call(* SearchBasedExtractAndMoveMethodAnalyzer.analyze()) 
      && target(analyzer);

after(SearchBasedExtractAndMoveMethodAnalyzer analyzer) : 
    methodAnalyze(analyzer) {
  statistics.methodCount++;
  debugPrintMethodAnalysisProgress(analyzer.method);
}
\end{minted}
\caption{An example of a pointcut named \method{methodAnalyze}, 
and an advice defined to be applied after it has occurred.}
\label{lst:aspectjExample}
\end{listing}

\subsection{The Statistics class}
The statistics aspect stores statistical information in an object of type 
\type{Statistics}. As of now, the aspect needs to be initialized at the point in 
time where it is desired that it starts its data gathering. At any point in time 
the statistics aspect can be queried for a snapshot of the current statistics.

The \type{Statistics} class also include functionality for generating a report 
of its gathered statistics. The report can be given either as a string or it can 
be written to a file.

\subsection{Advices}
The statistics aspect contains advices for gathering statistical data from 
different parts of the benchmarking process. It captures statistics from both 
the analysis part and the execution part of the composite \ExtractAndMoveMethod 
refactoring.

For the analysis part, there are advices to count the number of text selections 
analyzed and the number of methods, types, compilation units and packages 
analyzed. There are also advices that counts for how many of the methods there 
is found a selection that is a candidate for the refactoring, and for how many 
ethods there is not.

There exists advices for counting both the successful and unsuccessful 
executions of all the refactorings. Both for the \ExtractMethod and \MoveMethod 
refactorings in isolation, as well as for the combination of them.

\section{Optimizations}
When looking for optimizations to make for the benchmarking process, I used the 
\emph{VisualVM}\footnote{\url{http://visualvm.java.net/}} for the Java Virtual 
Machine to both profile the application and also to make memory dumps of its 
heap.

\subsection{Caching}
When profiling the benchmark process before making any optimizations, it early 
became apparent that the parsing of source code was a place to direct attention 
towards. This discovery was done when only \emph{analyzing} source code, before 
trying to do any \emph{manipulation} of it. Caching of the parsed ASTs seemed 
like the best way to save some time, as expected. With only a simple cache of 
the most recently used AST, the analysis time was speeded up by a factor of 
around 
20.  This number depends a little upon which type of system the analysis was 
run.

The caching is managed by a cache manager, that now, by default, utilizes the 
not so well known feature of Java called a \emph{soft reference}. Soft 
references are best explained in the context of weak references. A \emph{weak 
reference} is a reference to an object instance that is only guaranteed to 
persist as long as there is a \emph{strong reference} or a soft reference 
referring the same object. If no such reference is found, its referred object is 
garbage collected. A strong reference is basically the same as a regular Java 
reference. A soft reference has the same guarantees as a week reference when it 
comes to its relation to strong references, but it is not necessarily garbage 
collected whenever there exists no strong references to it. A soft reference 
\emph{may} reside in memory as long as the JVM has enough free memory in the 
heap. A soft reference will therefore usually perform better than a weak 
reference when used for simple caching and similar tasks. The way to use a 
soft/weak reference is to as it for its referent. The return value then has to 
be tested to check that it is not \var{null}. For the basic usage of soft 
references, see \myref{lst:softReferenceExample}. For a more thorough 
explanation of weak references in general, see\citing{weakRef2006}.

\begin{listing}[h]
\begin{minted}{java}
// Strong reference
Object strongRef = new Object();

// Soft reference
SoftReference<Object> softRef =
    new SoftReference<Object>(new Object());

// Using the soft reference
Object obj = softRef.get();
if (obj != null) {
    // Use object here
}
\end{minted}
\caption{Showing the basic usage of soft references. Weak references is used the 
  same way. {\footnotesize (The references are part of the \code{java.lang.ref} 
package.)}}
\label{lst:softReferenceExample}
\end{listing}

The cache based on soft references has no limit for how many ASTs it caches. It 
is generally not advisable to keep references to ASTs for prolonged periods of
time, since they are expensive structures to hold on to. For regular plugin
development, Eclipse recommends not creating more than one AST at a time to 
limit memory consumption. Since the benchmarking has nothing to do with user 
experience, and throughput is everything, these advices are intentionally 
ignored. This means that during the benchmarking process, the target Eclipse 
application may very well work close to its memory limit for the heap space for 
long periods during the benchmark.

\subsection{Memento}

\chapter{Eclipse Bugs Found}
\todoin{Add other things and change headline?}

\section{Eclipse bug 420726: Code is broken when moving a method that is 
assigning to the parameter that is also the move 
destination}\label{eclipse_bug_420726}
This bug\footnote{\url{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=420726}}  
was found when analyzing what kinds of names that was to be considered as 
\emph{unfixes} \see{unfixes}.

\subsection{The bug}
The bug emerges when trying to move a method from one class to another, and when 
the target for the move (must be a variable, local or field) is both a parameter 
variable and also is assigned to within the method body. Eclipse allows this to 
happen, although it is the sure path to a compilation error. This is because we 
would then have an assignment to a \var{this} expression, which is not allowed 
in Java.

\subsection{The solution}
The solution to this problem is to add all simple names that are assigned to in 
a method body to the set of unfixes.

\section{Eclipse bug 429416: IAE when moving method from anonymous class}
I 
discovered\footnote{\url{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429416}} 
this bug during a batch change on the \type{org.eclipse.jdt.ui} project.

\subsection{The bug}
This bug surfaces when trying to use the Move Method refactoring to move a 
method from an anonymous class to another class. This happens both for my 
simulation as well as in Eclipse, through the user interface. It only occurs 
when Eclipse analyzes the program and finds it necessary to pass an instance of 
the originating class as a parameter to the moved method. I.e. it want to pass a 
\var{this} expression. The execution ends in an 
\typewithref{java.lang}{IllegalArgumentException} in 
\typewithref{org.eclipse.jdt.core.dom}{SimpleName} and its 
\method{setIdentifier(String)} method. The simple name is attempted created in 
the method
\methodwithref{org.eclipse.jdt.internal.corext.refactoring.structure.\\MoveInstanceMethodProcessor}{createInlinedMethodInvocation} 
so the \type{MoveInstanceMethodProcessor} was early a clear suspect.

The \method{createInlinedMethodInvocation} is the method that creates a method 
invocation where the previous invocation to the method that was moved was. From 
its code it can be read that when a \var{this} expression is going to be passed 
in to the invocation, it shall be qualified with the name of the original 
method's declaring class, if the declaring class is either an anonymous clas or 
a member class. The problem with this, is that an anonymous class does not have 
a name, hence the term \emph{anonymous} class! Therefore, when its name, an 
empty string, is passed into 
\methodwithref{org.eclipse.jdt.core.dom.AST}{newSimpleName} it all ends in an 
\type{IllegalArgumentException}.

\subsection{How I solved the problem}
Since the \type{MoveInstanceMethodProcessor} is instantiated in the 
\typewithref{no.uio.ifi.refaktor.change.executors}{MoveMethod\-RefactoringExecutor}, 
and only need to be a 
\typewithref{org.eclipse.ltk.core.refactoring.participants}{MoveProcessor}, I 
was able to copy the code for the original move processor and modify it so that 
it works better for me. It is now called 
\typewithref{no.uio.ifi.refaktor.refactorings.processors}{ModifiedMoveInstanceMethodProcessor}.  
The only modification done (in addition to some imports and suppression of 
warnings), is in the \method{createInlinedMethodInvocation}. When the declaring 
class of the method to move is anonymous, the \var{this} expression in the 
parameter list is not qualified with the declaring class' (empty) name.

\section{Eclipse bug 429954: Extracting statement with reference to local type 
breaks code}\label{eclipse_bug_429954}
The bug\footnote{\url{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429954}} 
was discovered when doing some changes to the way unfixes is computed.

\subsection{The bug}
The problem is that Eclipse is allowing selections that references variables of 
local types to be extracted. When this happens the code is broken, since the 
extracted method must take a parameter of a local type that is not in the 
methods scope. The problem is illustrated in 
\myref{lst:extractMethod_LocalClass}, but there in another setting.

\subsection{Actions taken}
There are no actions directly springing out of this bug, since the Extract 
Method refactoring cannot be meant to be this way. This is handled on the 
analysis stage of our Extract and Move Method refactoring. So names representing 
variables of local types is considered unfixes \see{unfixes}.
\todoin{write more when fixing this in legal statements checker}

\chapter{Related Work}

\section{The compositional paradigm of refactoring}
This paradigm builds upon the observation of Vakilian et 
al.\citing{vakilian2012}, that of the many automated refactorings existing in 
modern IDEs, the simplest ones are dominating the usage statistics. The report 
mainly focuses on \emph{Eclipse} as the tool under investigation.

The paradigm is described almost as the opposite of automated composition of 
refactorings \see{compositeRefactorings}. It works by providing the programmer 
with easily accessible primitive refactorings. These refactorings shall be 
accessed via keyboard shortcuts or quick-assist menus\footnote{Think 
quick-assist with Ctrl+1 in Eclipse} and be promptly executed, opposed to in the 
currently dominating wizard-based refactoring paradigm. They are ment to 
stimulate composing smaller refactorings into more complex changes, rather than 
doing a large upfront configuration of a wizard-based refactoring, before 
previewing and executing it. The compositional paradigm of refactoring is 
supposed to give control back to the programmer, by supporting \himher with an 
option of performing small rapid changes instead of large changes with a lesser 
degree of control. The report authors hope this will lead to fewer unsuccessful 
refactorings. It also could lower the bar for understanding the steps of a 
larger composite refactoring and thus also help in figuring out what goes wrong 
if one should choose to op in on a wizard-based refactoring.

Vakilian and his associates have performed a survey of the effectiveness of the 
compositional paradigm versus the wizard-based one. They claim to have found 
evidence of that the \emph{compositional paradigm} outperforms the 
\emph{wizard-based}. It does so by reducing automation, which seem 
counterintuitive. Therefore they ask the question ``What is an appropriate level 
of automation?'', and thus questions what they feel is a rush toward more 
automation in the software engineering community.


\backmatter{}
\printbibliography
\listoftodos
\end{document}