-\documentclass[USenglish]{ifimaster}
+\documentclass[USenglish,11pt]{ifimaster}
\usepackage{import}
\usepackage[utf8]{inputenc}
\usepackage[T1]{fontenc,url}
\usepackage{lmodern} % using Latin Modern to be able to use bold typewriter font
+%\usepackage{mathpazo}
\urlstyle{sf}
\usepackage{listings}
-\usepackage{babel,textcomp,csquotes,ifimasterforside,varioref}
+\usepackage{tabularx}
+\usepackage{tikz}
+\usepackage{tikz-qtree}
+\usetikzlibrary{shapes,snakes,trees,arrows,shadows,positioning,calc}
+\usepackage{babel,textcomp,csquotes,ifimasterforside}
+
+\usepackage{varioref}
\usepackage[hidelinks]{hyperref}
\usepackage{cleveref}
-\usepackage[style=numeric-comp,backend=bibtex]{biblatex}
+\usepackage[xindy,entrycounter]{glossaries}
+
+\usepackage[style=alphabetic,backend=biber]{biblatex}
\usepackage{amsthm}
+\usepackage{mathtools}
\usepackage{graphicx}
% use 'disable' before printing:
\usepackage[]{todonotes}
\theoremstyle{definition}
\newtheorem*{wordDef}{Definition}
+\newtheorem*{theorem}{Theorem}
\graphicspath{ {./figures/} }
\newcommand{\citing}[1]{~\cite{#1}}
-\newcommand{\myref}[1]{\cref{#1} on \cpageref{#1}}
+%\newcommand{\myref}[1]{\cref{#1} on \cpageref{#1}}
+\newcommand{\myref}[1]{\vref{#1}}
+\newcommand{\Myref}[1]{\Vref{#1}}
+
+\newcommand{\glossref}[1]{\textsuperscript{(\glsrefentry{#1})}}
+%\newcommand{\gloss}[1]{\gls{#1}\glossref{#1}}
+%\newcommand{\glosspl}[1]{\glspl{#1}\glossref{#1}}
+\newcommand{\gloss}[1]{\gls{#1}}
+\newcommand{\glosspl}[1]{\glspl{#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{\type}[1]{\texttt{\textbf{#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{\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{\name}[1]{#1}
+\newcommand{\tit}[1]{\emph{#1}}
+\newcommand{\refa}[1]{\emph{#1}}
+\newcommand{\pattern}[1]{\emph{#1}}
+\newcommand{\metr}[1]{\emph{#1}}
+\newcommand{\ExtractMethod}{\refa{Extract Method}\xspace}
+\newcommand{\MoveMethod}{\refa{Move Method}\xspace}
+\newcommand{\ExtractAndMoveMethod}{\refa{Extract and Move Method}\xspace}
-\newcommand\todoin[2][]{\todo[inline, caption={2do}, #1]{
+\newcommand\todoin[2][]{\todo[inline, caption={#2}, #1]{
\begin{minipage}{\textwidth-4pt}#2\end{minipage}}}
-\title{Refactoring}
-\subtitle{An essay}
+\title{Automated Composition of Refactorings}
+\subtitle{Composing the Extract and Move Method refactorings in Eclipse}
\author{Erlend Kristiansen}
+\makeglossaries
+\newglossaryentry{profiling}
+{
+ name=profiling,
+ description={is to run a computer program through a profiler/with a profiler
+ attached}
+}
+\newglossaryentry{profiler}
+{
+ name=profiler,
+ description={A profiler is a program for analyzing performance within an
+ application. It is used to analyze memory consumption, processing time and
+frequency of procedure calls and such.}
+}
+\newglossaryentry{xUnit}
+{
+ name={xUnit framework},
+ description={An xUnit framework is a framework for writing unit tests for a
+ computer program. It follows the patterns known from the JUnit framework for
+ Java\citing{fowlerXunit}
+ },
+ plural={xUnit frameworks}
+}
+\newglossaryentry{softwareObfuscation}
+{
+ name={software obfuscation},
+ description={makes source code harder to read and analyze, while preserving
+ its semantics}
+}
+\newglossaryentry{extractClass}
+{
+ name=\refa{Extract Class},
+ description={The \refa{Extract Class} refactoring works by creating a class,
+for then to move members from another class to that class and access them from
+the old class via a reference to the new class}
+}
+\newglossaryentry{designPattern}
+{
+ name={design pattern},
+ description={A design pattern is a named abstraction, that is meant to solve a
+ general design problem. It describes the key aspects of a common problem and
+identifies its participators and how they collaborate},
+ plural={design patterns}
+}
+\newglossaryentry{extractMethod}
+{
+ name=\refa{Extract Method},
+ description={The \refa{Extract Method} refactoring is used to extract a
+fragment of code from its context and into a new method. A call to the new
+method is inlined where the fragment was before. It is used to break code into
+logical units, with names that explain their purpose}
+}
+\newglossaryentry{moveMethod}
+{
+ name=\refa{Move Method},
+ description={The \refa{Move Method} refactoring is used to move a method from
+ one class to another. This is useful if the method is using more features of
+ another class than of the class which it is currently defined. Then all calls
+ to this method must be updated, or the method must be copied, with the old
+method delegating to the new method}
+}
+
\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,
+]
+
+%\interfootnotelinepenalty=10000
+
\begin{document}
+\pagenumbering{roman}
\ififorside
\frontmatter{}
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.
+In the extreme case one could argue that \gloss{softwareObfuscation} is
+refactoring. It is often used to protect proprietary software. It restrains
+uninvited viewers, so they have a hard time analyzing code that they are not
+supposed to know how works. This could be a problem when using a language that
+is possible to decompile, such as Java.
+
+Obfuscation could be done composing many, more or less randomly chosen,
+refactorings. Then the question arises whether it can be called a
+\emph{composite refactoring} or not \see{compositeRefactorings}? The answer is
+not obvious. First, there is no way to describe the mechanics of software
+obfuscation, because there are infinitely many ways to do that. Second,
+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.
+
+This last point is important, since one of the motivations behind defining
+different refactorings, is to establish a \emph{vocabulary} for software
+professionals to use when reasoning about and discussing programs, similar to
+the motivation behind \glosspl{designPattern}\citing{designPatterns}.
+\begin{comment}
+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.
+\end{comment}
\section{The etymology of 'refactoring'}
It is a little difficult to pinpoint the exact origin of the word
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
+origin of \emph{refactoring}, is the
+Smalltalk\footnote{\label{footNote}Programming language} community and their
+infamous \name{Refactoring
Browser}\footnote{\url{http://st-www.cs.illinois.edu/users/brant/Refactory/RefactoringBrowser.html}}
-described in the article \emph{A Refactoring Tool for
+described in the article \tit{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{brodie1984}, 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]{brodie1984},
-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.
+also present in the Forth\textsuperscript{\ref{footNote}} community, and the
+word ``refactoring'' is mentioned in a book by Leo Brodie, called \tit{Thinking
+Forth}\citing{brodie2004}, first published in 1984\footnote{\tit{Thinking Forth}
+was first published in 1984 by the \name{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]{brodie1984}
+ Forth programmer.~\cite[p.~172]{brodie2004}
\end{quote}
\noindent Brodie also express what \emph{factoring} means to him:
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]{brodie1984}
+ 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
+the \name{Forth} and \name{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
+design patterns 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 just mentioned, people often refactor to get rid of duplication. They are
+moving identical or similar code into methods, and are pushing methods up or
+down in their class hierarchies. They are 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 duplicate pieces of code might not be coupled, apart
+from representing 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 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
+smaller ones, using the \gloss{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
+Most primitive refactorings are simple, and usually involves moving code
+around\citing{kerievsky2005}. The motivation behind them may first be 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.
+such a series of refactorings is a design pattern. Thus the design can
+\emph{evolve} 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.
+perhaps the \pattern{Model-View-Controller}\citing{designPatterns} pattern. It
+is aimed at lowering the coupling between the user interface, the business logic
+and the data representation of a program. This also has the added benefit that
+the business logic could much easier be the target of automated tests, thus
+increasing the productivity in the software development process.
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.
+needed and in a more effective way\citing{refactoring}.
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
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
+The article \tit{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 \name{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}.
+objects together in chunks, and give each chunk a new name that it can be
+remembered by.
\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}
+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 \refa{Extract Class}
+refactorings\citing{refactoring}.
+
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
+binary digits. The example presented here is a slightly modified version of the
+one presented in the original article\citing{miller1956}, but it preserves the
+essence of it. Let us say we have the following sequence 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
+science, it will be obvious that the latter sequence is the first sequence
+recoded to be represented by digits in 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
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.
+design patterns 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
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
+computer programs that are easier to maintain and have code that is easier (and
better) understood.
\section{Notable contributions to the refactoring literature}
-\todoin{Update with more contributions}
+\todoin{Thinking Forth?}
\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
+ \tit{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.: \tit{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
+ the principles of test-driven development.
+ \item[2005] Joshua Kerievsky: \tit{Refactoring to
Patterns}\citing{kerievsky2005}. This book is heavily influenced by Fowler's
- \emph{Refactoring}\citing{refactoring} and the ``Gang of Four'' \emph{Design
+ \tit{Refactoring}\citing{refactoring} and the ``Gang of Four'' \tit{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
+ from certain design patterns. The book is trying to build up the reader's
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}
+ 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},
+This section will briefly compare the refactoring support of the three IDEs
+\name{Eclipse}\footnote{\url{http://www.eclipse.org/}}, \name{IntelliJ
+IDEA}\footnote{The IDE under comparison is the \name{Community Edition},
\url{http://www.jetbrains.com/idea/}} and
-\emph{NetBeans}\footnote{\url{https://netbeans.org/}}. These are the most
+\name{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
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}.
+at least they have all passed the first ``refactoring
+rubicon''\citing{fowlerRubicon2001,secondRubicon2012}.
+
+Regarding the \gloss{moveMethod} refactoring, the \name{Eclipse} and
+\name{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 \name{NetBeans} IDE implements this refactoring in a somewhat
+unsophisticated way. For starters, the refactoring's default destination for the
+move, is the same class as the method already resides in, 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}
\label{lst:moveMethod_NetBeans}
\end{listing}
-NetBeans will try to make code that call the methods \method{m} and \method{n}
+\name{NetBeans} will try to create 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}.)
+keeps \name{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
+refactoring breaks the code, and it will not compile. \name{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
+The IDEs under investigation seem to have fairly good support for primitive
+refactorings, but what about more complex ones, such as
+\gloss{extractClass}\citing{refactoring}? \name{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?}
+new class, but are not used anywhere. \name{Eclipse} has added its own quirk to
+the \refa{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 \refa{Extract Class} is a little
+misleading. One would often be better off with textual extract and paste than
+using the \refa{Extract Class} refactoring in \name{Eclipse}. When it comes to
+\name{NetBeans}, it does not even show an attempt on providing this refactoring.
\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.
+Refactoring and 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 maintainable and extendable source code.
\begin{quote}
Design patterns help you determine how to reorganize a design, and they can
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
+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.
\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.
+design, leaving the performance tuning until after \gloss{profiling} 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
\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
+\noindent Examples are the \refa{Pull Up Field} and \refa{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
+\noindent An example of a composite refactoring is the \refa{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
+\refa{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}
+by applying \refa{Pull Up Field}, \refa{Pull Up Method} and
+\refa{Pull Up Constructor Body} on the members that are to be members of
+the new superclass. If there are multiple classes in play, their interfaces may
+need to be united with the help of some rename refactorings, before extracting
+the superclass. For an overview of the \refa{Extract Superclass}
refactoring, see \myref{fig:extractSuperclass}.
\begin{figure}[h]
\centering
\includegraphics[angle=270,width=\linewidth]{extractSuperclassItalic.pdf}
- \caption{The Extract Superclass refactoring}
+ \caption{The Extract Superclass refactoring, with united interfaces.}
\label{fig:extractSuperclass}
\end{figure}
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}.
+Consider 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 ther program's beavior, mainly because its Move Method refactoring
- implementation is a bit rancid in other ways \see{toolSupport}.}. The
- following piece of code shows the target for the composed refactoring:
-
-\begin{minted}[linenos,samepage]{java}
+behavior preservation. This last sentence might seem obvious, but there are
+examples of refactorings in existing tools that break programs. In an ideal
+world, every automated refactoring would be ``complete'', in the sense that it
+would never break a program. In an ideal world, every program would also be free
+from bugs. In modern IDEs the implemented automated refactorings are working for
+\emph{most} cases, that is enough for making them useful.
+
+I will now present an example of a \emph{corner case} where a program breaks
+when a refactoring is applied. The example shows an \ExtractMethod refactoring
+followed by a \MoveMethod refactoring that breaks a program in both the
+\name{Eclipse} and \name{IntelliJ} IDEs\footnote{The \name{NetBeans} IDE handles this
+ particular situation without altering the program's behavior, mainly because
+ its \refa{Move Method} refactoring implementation is a bit flawed in other ways
+ \see{toolSupport}.}. The target and the destination for the composed
+ refactoring is shown in \myref{lst:correctnessExtractAndMove}. Note that the
+ method \method{m(C c)} of class \type{X} assigns to the field \var{x} of the
+ argument \var{c} that has type \type{C}.
+
+\begin{listing}[h]
+\begin{multicols}{2}
+\begin{minted}[linenos]{java}
+// Refactoring target
public class C {
- public X x = new X();
+ public X x = new X();
- public void f() {
- x.m(this);
- x.n();
- }
+ public void f() {
+ x.m(this);
+ // Not the same x
+ 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}:
+\columnbreak
-\begin{minted}[samepage]{java}
+\begin{minted}[]{java}
+// Method destination
public class X {
- public void m(C c) {
- c.x = new X();
- }
- public void n() {}
+ public void m(C c) {
+ c.x = new X();
+ // If m is called from
+ // c, then c.x no longer
+ // equals 'this'
+ }
+ public void n() {}
}
\end{minted}
+\end{multicols}
+\caption{The target and the destination for the composition of the Extract
+Method and \refa{Move Method} refactorings.}
+\label{lst:correctnessExtractAndMove}
+\end{listing}
+
-The refactoring sequence works by extracting line 5 and 6 from the original
+The refactoring sequence works by extracting line 6 through 8 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:
+its method body (but with the comment left out, since it will no longer hold any
+meaning). The method is then moved to the class \type{X}. The result is shown
+in \myref{lst:correctnessExtractAndMoveResult}.
-\begin{minted}[linenos,samepage]{java}
+Before the refactoring, the methods \method{m} and \method{n} of class \type{X}
+are called on different object instances (see line 6 and 8 of the original class
+\type{C} in \cref{lst:correctnessExtractAndMove}). After the refactoring, they
+are called on the same object, and the statement on line
+3 of class \type{X} (in \cref{lst:correctnessExtractAndMoveResult}) no longer
+ has the desired effect in our example. The method \method{f} of class \type{C}
+ is now calling the method \method{f} of class \type{X} (see line 5 of class
+ \type{C} in \cref{lst:correctnessExtractAndMoveResult}), and the program now
+ behaves different than before.
+
+\begin{listing}[h]
+\begin{multicols}{2}
+\begin{minted}[linenos]{java}
public class C {
public X x = new X();
}
\end{minted}
-\begin{minted}[linenos,samepage]{java}
+\columnbreak
+
+\begin{minted}[linenos]{java}
public class X {
public void m(C c) {
c.x = new X();
}
public void n() {}
+ // Extracted and
+ // moved method
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.
+\end{multicols}
+\caption{The result of the composed refactoring.}
+\label{lst:correctnessExtractAndMoveResult}
+\end{listing}
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)}}
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
+way to make you confident 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.
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
+Unit tests, as they are known from the different \glosspl{xUnit} 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 \ldots}
+\begin{comment}
Assuming a sequential (non-concurrent) program:
% { assert x1 != x2; }
%}
%\end{minted}
+\end{comment}
+
-\section{The project}
-The aim of this project will be to investigate the relationship between a
+\chapter{The Project}
+
+\todoin{Moved from introduction to here. Rewrite and make problem statement from
+it:}
+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 \ExtractMethod and \MoveMethod 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
+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
+\name{CodeRush}\footnote{\url{https://help.devexpress.com/\#CodeRush/CustomDocument3519}},
+that is an extension for \name{MS Visual
Studio}\footnote{\url{http://www.visualstudio.com/}}. In CodeRush it is called
-\emph{Extract Method to
+\refa{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
+For the metrics, I will at least measure the \metr{Coupling between object
classes} (CBO) metric that is described by Chidamber and Kemerer in their
-article \emph{A Metrics Suite for Object Oriented
+article \tit{A Metrics Suite for Object Oriented
Design}\citing{metricsSuite1994}.
The project will then consist in implementing the \ExtractAndMoveMethod
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.
+\section{The problem statement}
+\todoin{write/move}
+
+\section{The primitive refactorings}
+The refactorings presented here are the primitive refactorings used in this
+project. They are the abstract building blocks used by the \ExtractAndMoveMethod
+refactoring.
+
+\subsection{The Extract Method refactoring}
+The \refa{Extract Method} refactoring is used to extract a fragment of code
+from its context and into a new method. A call to the new method is inlined
+where the fragment was before. It is used to break code into logical units, with
+names that explain their purpose.
+
+An example of an \ExtractMethod refactoring is shown in
+\myref{lst:extractMethodRefactoring}. It shows a method containing calls to the
+methods \method{foo} and \method{bar} of a type \type{X}. These statements are
+then extracted into the new method \method{fooBar}.
+
+\begin{listing}[h]
+ \begin{multicols}{2}
+ \begin{minted}[samepage]{java}
+ // Before
+ class C {
+ void method() {
+ X x = new X();
+ x.foo(); x.bar();
+ }
+ }
+ \end{minted}
-\section{Software metrics}
-\todoin{Is this the appropriate place to have this section?}
+ \columnbreak
-%\part{The project}
-%\chapter{Planning the project}
-%\part{Conclusion}
-%\chapter{Results}
+ \begin{minted}[samepage]{java}
+ // After
+ class C {
+ void method() {
+ X x = new X();
+ fooBar(x);
+ }
+ void fooBar(X x) {
+ x.foo(); x.bar();
+ }
+ }
+ \end{minted}
+ \end{multicols}
+ \caption{An example of an \ExtractMethod refactoring.}
+ \label{lst:extractMethodRefactoring}
+\end{listing}
+\subsection{The Move Method refactoring}
+The \refa{Move Method} refactoring is used to move a method from one class to
+another. This can be appropriate if the method is using more features of another
+class than of the class which it is currently defined.
+
+\Myref{lst:moveMethodRefactoring} shows an example of this refactoring. Here a
+method \method{fooBar} is moved from the class \type{C} to the class \type{X}.
+
+\begin{listing}[h]
+ \begin{multicols}{2}
+ \begin{minted}[samepage]{java}
+ // Before
+ class C {
+ void method() {
+ X x = new X();
+ fooBar(x);
+ }
+ void fooBar(X x) {
+ x.foo(); x.bar();
+ }
+ }
+
+ class X {
+ void foo(){/*...*/}
+ void bar(){/*...*/}
+ }
+ \end{minted}
+
+ \columnbreak
+
+ \begin{minted}[samepage]{java}
+ // After
+ class C {
+ void method() {
+ X x = new X();
+ x.fooBar();
+ }
+ }
+ class X {
+ void fooBar() {
+ foo(); bar();
+ }
+ void foo(){/*...*/}
+ void bar(){/*...*/}
+ }
+ \end{minted}
+ \end{multicols}
+ \caption{An example of a \MoveMethod refactoring.}
+ \label{lst:moveMethodRefactoring}
+\end{listing}
+
+\section{The Extract and Move Method refactoring}
+The \ExtractAndMoveMethod refactoring is a composite refactoring composed of the
+primitive \ExtractMethod and \MoveMethod refactorings. The effect of this
+refactoring on source code is the same as when extracting a method and moving it
+to another class. Conseptually, this is done without an intermediate step. In
+practice, as we shall see later, an intermediate step may be necessary.
+
+An example of this composite refactoring is shown in
+\myref{lst:extractAndMoveMethodRefactoring}. The example joins the examples from
+\cref{lst:extractMethodRefactoring} and \cref{lst:moveMethodRefactoring}. This
+means that the selection consisting of the consecutive calls to the methods
+\method{foo} and \method{bar}, is extracted into a new method \method{fooBar}
+located in the class \type{X}.
+
+\begin{listing}[h]
+ \begin{multicols}{2}
+ \begin{minted}[samepage]{java}
+ // Before
+ class C {
+ void method() {
+ X x = new X();
+ x.foo(); x.bar();
+ }
+ }
+
+ class X {
+ void foo(){/*...*/}
+ void bar(){/*...*/}
+ }
+ \end{minted}
+
+ \columnbreak
+
+ \begin{minted}[samepage]{java}
+ // After
+ class C {
+ void method() {
+ X x = new X();
+ x.fooBar();
+ }
+ }
+
+ class X {
+ void fooBar() {
+ foo(); bar();
+ }
+ void foo(){/*...*/}
+ void bar(){/*...*/}
+ }
+ \end{minted}
+ \end{multicols}
+ \caption{An example of the \ExtractAndMoveMethod refactoring.}
+ \label{lst:extractAndMoveMethodRefactoring}
+\end{listing}
-\chapter{\ldots}
-\todoin{write}
-\section{The problem statement}
\section{Choosing the target language}
-Choosing which programming language to use as the target for manipulation is not
-a very difficult task. The language has to be an object-oriented programming
-language, and it 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 examples 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\footnote{They
-compile to java bytecode.} dozens of other programming languages, 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 language of the author of this thesis.
+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 \name{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 \name{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 \name{Scala}, \name{Clojure} and \name{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
+When choosing a tool for manipulating Java, there are certain criteria 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
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
+people connected to them, that are committed to answering questions regarding the
+use and misuse of the products, that to a large degree is made by the community
itself.
-There is a certain class of tools that meet these criterias, namely the class of
+There is a certain class of tools that meet these criteria, 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
+programs that is meant to support the whole production cycle of a computer
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.
+The main contenders for this thesis is the \name{Eclipse IDE}, with the
+\name{Java development tools} (JDT), the \name{IntelliJ IDEA Community Edition}
+and the \name{NetBeans IDE} \see{toolSupport}. \name{Eclipse} and
+\name{NetBeans} are both free, open source and community driven, while the
+\name{IntelliJ IDEA} has an open sourced community edition that is free of
+charge, but also offer an \name{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 \name{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.
\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
+\name{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
+The refactoring world of \name{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, 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 is 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.)
+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 \name{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\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.
+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
\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
+quantities of the \name{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
\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 has been
+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 occur in the middle of a sequence of
-refactorings, it can leave the project in a state where the composite
-refactoring was executed only partly. It makes it hard to discard the changes
+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.
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}
+sequence. This problem is not trivial to handle in \name{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
+As pointed out in \myref{ch:jdt_refactorings}, the \name{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.
+abstraction layer on top of the existing \name{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
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
+refactoring\citing{refactoring}. In \name{Eclipse}, the implementations of these
refactorings are found in the classes
\typewithref{org.eclipse.jdt.internal.corext.refactoring.code}{ExtractMethodRefactoring}
and
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
-which access modifier that shall be used and some not so interesting parameters.
+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} from the Java Model 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 and delegation.
+For the \refa{Move Method}, the processor requires a little more advanced input than
+the class for the \refa{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.
-To make a whole refactoring from the processor, one have to construct a
-\type{MoveRefactoring} from it.
+\subsection{The ExtractAndMoveMethodChanger}
-\subsection{The ExtractAndMoveMethodChanger Class}
The \typewithref{no.uio.ifi.refaktor.changers}{ExtractAndMoveMethodChanger}
-class, that is a subclass of the class
-\typewithref{no.uio.ifi.refaktor.changers}{RefaktorChanger}, is the class
-responsible for composing the \type{ExtractMethodRefactoring} and the
-\type{MoveRefactoring}. Its constructor takes a project
-handle\typeref{org.eclipse.core.resources.IProject}, the method name for the new
-method and a \typewithref{no.uio.ifi.refaktor.utils}{SmartTextSelection}.
-
-A \type{SmartTextSelection} is basically a text
-selection\typeref{org.eclipse.jface.text.ITextSelection} object that enforces
-the providing of the underlying document during creation. I.e. its
-\methodwithref{no.uio.ifi.refaktor.utils.SmartTextSelection}{getDocument} method
-will never return \type{null}.
-
-Before extracting the new method, the possible targets for the move operation is
-found with the help of an
-\typewithref{no.uio.ifi.refaktor.extractors}{ExtractAndMoveMethodPrefixesExtractor}.
-The possible targets is computed from the prefixes that the extractor returns
-from its
-\methodwithref{no.uio.ifi.refaktor.extractors.ExtractAndMoveMethodPrefixesExtractor}{getSafePrefixes}
-method. The changer then choose the most suitable target by finding the most
-frequent occurring prefix among the safe ones. The target is the type of the
-first part of the prefix.
-
-After finding a suitable target, the \type{ExtractAndMoveMethodChanger} first
-creates an \type{ExtractMethodRefactoring} and performs it as explained in
-\myref{executing_refactoring} about the execution of refactorings. Then it
-creates and performs the \type{MoveRefactoring} in the same way, based on the
-changes done by the Extract Method refactoring.
-
-\subsection{The ExtractAndMoveMethodPrefixesExtractor Class}
-This extractor extracts properties needed for building the Extract and Move
-Method refactoring. It searches through the given selection to find safe
-prefixes, and those prefixes form a base that can be used to compute possible
-targets for the move part of the refactoring. It finds both the candidates, in
-the form of prefixes, and the non-candidates, called unfixes. All prefixes (and
-unfixes) are represented by a
+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 \refa{Extract Method} and \refa{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}}\label{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 candidate targets 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, see \myref{propertyCollectors}.) All
+prefixes (and unfixes) are represented by a
\typewithref{no.uio.ifi.refaktor.extractors}{Prefix}, and they are collected
-into prefix sets.\typeref{no.uio.ifi.refaktor.extractors.PrefixSet}.
+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}}\label{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 \refa{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 \refa{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 \refa{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}
+The
+\typewithref{no.uio.ifi.refaktor.change.changers}{SearchBasedExtractAndMoveMethodChanger}
+is a changer whose purpose is to automatically analyze a method, and execute the
+\ExtractAndMoveMethod refactoring on it if it is a suitable candidate for the
+refactoring.
+
+First, the \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{SearchBasedExtractAndMoveMethodAnalyzer} is used
+to analyze the method. If the method is found to be a candidate, the result from
+the analysis is fed to the \type{ExtractAndMoveMethodExecutor}, whose job is to
+execute the refactoring \see{extractAndMoveMethodExecutor}.
+
+\subsubsection{The SearchBasedExtractAndMoveMethodAnalyzer}
+This analyzer is responsible for analyzing all the possible text selections of a
+method and then choose the best result out of the analysis results that is, by
+the analyzer, considered to be the potential candidates for the Extract and Move
+Method refactoring.
+
+Before the analyzer is able to work with the text selections of a method, it
+needs to generate them. To do this, it parses the method to obtain a
+\type{MethodDeclaration} for it \see{astEclipse}. Then there is a statement
+lists creator that creates statements lists of the different groups of
+statements in the body of the method declaration. A text selections generator
+generates text selections of all the statement lists for the analyzer to work
+with.
+
+\paragraph{The statement lists creator}
+is responsible for generating lists of statements for all the possible levels of
+statements in the method. The statement lists creator is implemented as an AST
+visitor \see{astVisitor}. It generates lists of statements by visiting all the
+blocks in the method declaration and stores their statements in a collection of
+statement lists. In addition, it visits all of the other statements that can
+have a statement as a child, such as the different control structures and the
+labeled statement.
+
+The switch statement is the only kind of statement that is not straight forward
+to obtain the child statements from. It stores all of its children in a flat
+list. Its switch case statements are included in this list. This means that
+there are potential statement lists between all of these case statements. The
+list of statements from a switch statement is therefore traversed, and the
+statements between the case statements are grouped as separate lists.
+
+There is an example of how the statement lists creator would generate lists for
+a simple method in \myref{lst:statementListsExample}.
+
+\begin{listing}[h]
+\def\charwidth{5.7pt}
+\def\indent{4*\charwidth}
+\def\lineheight{\baselineskip}
+\def\mintedtop{\lineheight}
+
+\begin{tikzpicture}[overlay, yscale=-1]
+ \tikzstyle{overlaybox}=[fill=lightgray,opacity=0.2]
+ \draw[overlaybox] (0,\mintedtop+\lineheight) rectangle
+ +(22*\charwidth,10*\lineheight);
+ \draw[overlaybox] (\indent,\mintedtop+2*\lineheight) rectangle
+ +(13*\charwidth,\lineheight);
+ \draw[overlaybox] (2*\indent,\mintedtop+6*\lineheight) rectangle
+ +(13*\charwidth,2*\lineheight);
+ \draw[overlaybox] (2*\indent,\mintedtop+9*\lineheight) rectangle
+ +(13*\charwidth,\lineheight);
+\end{tikzpicture}
+\begin{minted}{java}
+void method() {
+ if (bool)
+ b.bar();
+
+ switch (val) {
+ case 1:
+ b.foo();
+ c.foo();
+ default:
+ c.foo();
+ }
+}
+\end{minted}
+\caption{Example of how the statement lists creator would group a simple method
+into lists of statements. Each highlighted rectangle represents a list.}
+\label{lst:statementListsExample}
+\end{listing}
-The prefixes and unfixes are found by property
-collectors\typeref{no.uio.ifi.refaktor.extractors.collectors.PropertyCollector}.
-A property collector follows the visitor pattern\citing{designPatterns} and is
-of the \typewithref{org.eclipse.jdt.core.dom}{ASTVisitor} type. An
-\type{ASTVisitor} visits nodes in an abstract syntax tree that forms the Java
-document object model. The tree consists of nodes of type
-\typewithref{org.eclipse.jdt.core.do}{ASTNode}.
+\paragraph{The text selections generator} generates text selections for each
+list of statements from the statement lists creator. Conceptually, the generator
+generates a text selection for every possible ordered \todo{make clearer}
+combination of statements in a list. For a list of statements, the boundary
+statements span out a text selection. This means that there are many different
+lists that could span out the same selection.
+
+In practice, the text selections are calculated by only one traversal of the
+statement list. There is a set of generated text selections. For each statement,
+there is created a temporary set of selections, in addition to a text selection
+based on the offset and length of the statement. This text selection is added to
+the temporary set. Then the new selection is added with every selection from the
+set of generated text selections. These new selections are added to the
+temporary set. Then the temporary set of selections is added to the set of
+generated text selections. The result of adding two text selections is a new
+text selection spanned out by the two addends.
+
+\begin{listing}[h]
+\def\charwidth{5.7pt}
+\def\indent{4*\charwidth}
+\def\lineheight{\baselineskip}
+\def\mintedtop{\lineheight}
+
+\begin{tikzpicture}[overlay, yscale=-1]
+ \tikzstyle{overlaybox}=[fill=lightgray,opacity=0.2]
+
+ \draw[overlaybox] (2*\charwidth,\mintedtop) rectangle
+ +(18*\charwidth,\lineheight);
+
+ \draw[overlaybox] (2*\charwidth,\mintedtop+\lineheight) rectangle
+ +(18*\charwidth,\lineheight);
+
+ \draw[overlaybox] (2*\charwidth,\mintedtop+3*\lineheight) rectangle
+ +(18*\charwidth,\lineheight);
+
+ \draw[overlaybox] (\indent-3*\charwidth,\mintedtop) rectangle
+ +(20*\charwidth,2*\lineheight);
+
+ \draw[overlaybox] (3*\charwidth,\mintedtop+\lineheight) rectangle
+ +(16*\charwidth,3*\lineheight);
+
+ \draw[overlaybox] (\indent,\mintedtop) rectangle
+ +(14*\charwidth,4*\lineheight);
+\end{tikzpicture}
+\begin{minted}{java}
+ statement one;
+ statement two;
+ ...
+ statement k;
+\end{minted}
+\caption{Example of how the text selections generator would generate text
+ selections based on a lists of statements. Each highlighted rectangle
+represents a text selection.}
+\label{lst:textSelectionsExample}
+\end{listing}
+\todoin{fix \myref{lst:textSelectionsExample}? Text only? All
+sub-sequences\ldots}
+
+\paragraph{Finding the candidate} for the refactoring is done by analyzing all
+the generated text selection with the \type{ExtractAndMoveMethodAnalyzer}
+\see{extractAndMoveMethodAnalyzer}. If the analyzer generates a useful result,
+an \type{ExtractAndMoveMethodCandidate} is created from it, that is kept in a
+list of potential candidates. If no candidates are found, the
+\type{NoTargetFoundException} is thrown.
+
+Since only one of the candidates can be chosen, the analyzer must sort out which
+candidate to choose. The sorting is done by the static \method{sort} method of
+\type{Collections}. The comparison in this sorting is done by an
+\type{ExtractAndMoveMethodCandidateComparator}.
+\todoin{Write about the
+ExtractAndMoveMethodCandidateComparator/FavorNoUnfixesCandidateComparator}
+
+\paragraph{The complexity} of how many text selections that needs to be analyzed
+for a total of $n$ statements is bounded by $O(n^2)$.
+
+\begin{theorem}
+The number of text selections that need to be analyzed for each list of
+statements of length $n$, is exactly
+
+\begin{equation*}
+ \sum_{i=1}^{n} i = \frac{n(n+1)}{2}
+ \label{eq:complexityStatementList}
+\end{equation*}
+\label{thm:numberOfTextSelection}
+\end{theorem}
+
+\begin{proof}
+ For $n=1$ this is trivial: $\frac{1(1+1)}{2} = \frac{2}{2} = 1$. One statement
+ equals one selection.
+
+ For $n=2$, you get one text selection for the first statement. For the second,
+ you get one selection for the statement itself, and one selection for the two
+ of them combined. This equals three selections. $\frac{2(2+1)}{2} =
+ \frac{6}{2} = 3$.
+
+ For $n=3$, you get 3 selections for the two first statements, as in the case
+ where $n=2$. In addition you get one selection for the third statement itself,
+ and two more statements for the combinations of it with the two previous
+ statements. This equals six selections. $\frac{3(3+1)}{2} = \frac{12}{2} = 6$.
+
+ Assume that for $n=k$ there exists $\frac{k(k+1)}{2}$ text selections. Then we
+ want to add selections for another statement, following the previous $k$
+ statements. So, for $n=k+1$, we get one additional selection for the statement
+ itself. Then we get one selection for each pair of the new selection and the
+ previous $k$ statements. So the total number of selections will be the number
+ of already generated selections, plus $k$ for every pair, plus one for the
+ statement itself: $\frac{k(k+1)}{2} + k +
+ 1 = \frac{k(k+1)+2k+2}{2} = \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2} =
+ \frac{(k+1)((k+1)+1)}{2} = \sum_{i=1}^{k+1} i$
+\end{proof}
+
+\begin{theorem}
+ The number of text selections for a body of statements is maximized if all the
+ statements are at the same level.
+ \label{thm:textSelectionsMaximized}
+\end{theorem}
+
+\begin{proof}
+ Assume we have a body of, in total, $k$ statements. Let
+ $l,\cdots,m,(k-l-\cdots-m)$ be the lengths of the lists of statements in the
+ body, with $l+\cdots+m<k \Rightarrow l,\cdots,m<k$.
+
+ Then, the number of text selections that are generated for the $k$ statements
+ is
+
+ {
+ \small
+ \begin{align*}
+ \frac{(k-l-\cdots-m)((k-l-\cdots-m)+ 1)}{2} + \frac{l(l+1)}{2} + \cdots +
+ \frac{m(m+1)}{2} = \\
+ \frac{k^2 - 2kl - \cdots - 2km + l^2 + \cdots + m^2 + k - l - \cdots - m}{2}
+ + \frac{l^2+l}{2} + \cdots + \frac{m^2+m}{2} = \\
+ \frac{k^2 + k + 2l^2 - 2kl + \cdots + 2m^2 - 2km}{2}
+ \end{align*}
+ }
+
+ It then remains to show that this inequality holds:
+
+ \begin{align*}
+ \frac{k^2 + k + 2l^2 - 2kl + \cdots + 2m^2 - 2km}{2} < \frac{k(k+1)}{2} =
+ \frac{k^2 + k}{2}
+ \end{align*}
+
+ By multiplication by $2$ on both sides, and by removing the equal parts, we get
+
+ \begin{align*}
+ 2l^2 - 2kl + \cdots + 2m^2 - 2km < 0
+ \end{align*}
+
+ Since $l,\cdots,m<k$, we have that $\forall i \in \{l,\cdots,m\} : 2ki > 2i^2$,
+ so all the pairs of parts on the form $2i^2-2ki$ are negative. In sum, the
+ inequality holds.
+
+\end{proof}
+
+Therefore, the complexity for the number of selections that needs to be analyzed
+for a body of $n$ statements is $O\bigl(\frac{n(n+1)}{2}\bigr) = O(n^2)$.
-\subsubsection{The PrefixesCollector}
-The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{PrefixesCollector}
-is of type \type{PropertyCollector}. 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.
-\todo{Rewrite in the case of changes to the way prefixes are found}
-\subsubsection{The UnfixesCollector}
-The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{UnfixesCollector}
-finds unfixes within the selection. An unfix is a name that is assigned to
-within the 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.
-
-\subsubsection{Computing Safe Prefixes}
-A safe prefix is a prefix that does not enclose an unfix. 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} and can be fetched calling the
-\method{getSafePrefixes} method of the
-\type{ExtractAndMoveMethodPrefixesExtractor}.
+\begin{comment}
+\subsection{Finding the IMethod}\label{postExtractExecution}
+\todoin{Rename section. Write??}
+\end{comment}
+
\subsection{The Prefix Class}
-\todo{?}
+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}
-\todo{Where to put this section?}
+\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
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
+\name{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
-\chapter{Eclipse Bugs}
-\todoin{Add other things and change headline?}
+
+\chapter{Analyzing Source Code in Eclipse}
+
+\section{The Java model}\label{javaModel}
+The Java model of \name{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 \name{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 \name{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 Syntax Tree}
+\name{Eclipse} is following the common paradigm of using an abstract syntax 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 analyzes 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 equivalent 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 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
+\name{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 \name{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 syntax tree is a heavy-weight
+representation of source code. It contains information about properties 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}\label{astEclipse}
+In \name{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 \name{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 \name{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 addressed is how 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 \name{Eclipse}, by its
+\typewithref{org.eclipse.jdt.core.dom}{ASTVisitor}.
+
+The \name{Eclipse} AST, together with its \type{ASTVisitor}, follows the
+\pattern{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 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 case for the \name{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
+\name{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 \name{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
+\refa{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 \refa{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 \refa{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
+encountered statement with the end offset of the previous statement found.
+
+\section{Checkers}\label{checkers}
+\todoin{Check out ExtractMethodAnalyzer from ExtractMethodRefactoring}
+The checkers are a range of classes that checks that text selections complies
+with certain criteria. All checkers operates under the assumption that the code
+they check is free from compilation errors. 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 criteria. The checkers registered with the \type{LegalStatementsChecker}
+are described next. They are run in the order presented below.
+
+\subsection{The CallToProtectedOrPackagePrivateMethodChecker}
+This checker is designed to prevent an error that can occur in situations where
+a method is declared in one class, but overridden in another. If a text
+selection contains a call to a method like this, and the seletion is extracted
+to a new method, the subsequent movement of this method could cause the code to
+break.
+
+The code breaks in situations where the method call in the selection is to a
+method that has the \code{protected} modifier, or it does not have any access
+modifiers, i.e. it is package-private. The method is not public, so the
+\MoveMethod refactoring must make it public, making the moved method able to
+call it from its new location. The problem is that the, now public, method is
+overridden in a subclass, where it has a protected or package-private status.
+This makes the compiler complain that the subclass is trying to reduce the
+visibility of a method declared in its superclass. This is not allowed in Java,
+and for good reasons. It would make it possible to make a subclass that could
+not be a substitute for its superclass.
+
+The workings of the \type{CallToProtectedOrPackagePrivateMethod\-Checker} is
+therefore very simple. It looks for calls to methods that are either protected
+or package-private within the selection, and throws an
+\type{IllegalExpressionFoundException} if one is found.
+
+The problem this checker helps to avoid, is a little subtle. The problem does
+not arise in the class where the change is done, but in a class derived from it.
+This shows that classes acting as superclasses are especially fragile to
+introducing errors in the context of automated refactoring. This is also shown
+in bug\ldots \todoin{File Eclipse bug report}
+
+\subsection{The InstantiationOfNonStaticInnerClassChecker}
+When a non-static inner class is instatiated, this must happen in the scope of
+its declaring class. This is because it must have access to the members of the
+declaring class. If the inner class is public, it is possible to instantiate it
+through an instance of its declaring class, but this is not handled by the
+\type{MoveInstanceMethodProcessor} in Eclipse when moving a method. Therefore,
+performing a move on a method that instantiates a non-static inner class, will
+break the code if the instantiation is not handled properly. For this reason,
+the \type{InstantiationOfNonStaticInnerClassChecker} does not validate
+selections that contains instantiations of non-static inner classes. This
+problem is also related to bug\ldots \todoin{File Eclipse bug report}
+
+\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.MoveInstanceMethod\-Processor}{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}
+The checker for return statements is meant to verify that if a text selection
+contains a return statement, then every possible execution path within the
+selection ends in a return statement. This property is important regarding the
+\ExtractMethod refactoring. If it holds, it means that a method could be
+extracted from the selection, and a call to it could be substituted for the
+selection. If the method has a non-void return type, then a call to it would
+also be a valid return point for the calling method. If its return value is of
+the void type, then the \type{ExtractMethodRefactoring} of \name{Eclipse}
+appends an empty return statement to the back of the method call. Therefore, the
+analysis does not discriminate on either kinds of return statements, with or
+without a return value.
+
+The property description implies that if the selection is free from return
+statements, then the checker validates. So this is the first thing the checker
+investigates.
+
+If the checker proceedes any further, it is because the selection contains one
+or more return statements. The next test is therefore to check if the last
+statement of the selection ends in either a return or a throw statement. If the
+last statement of the selection ends in a return statement, then all execution
+paths within the selection should end in either this, or another, return
+statement. This is also true for a throw statement, since it causes an immediate
+exit from the current block, together with all outer blocks in its control flow
+that does not catch the thrown exception.
+
+Return statements can be either explicit or implicit. An \emph{explicit} return
+statement is formed by using the \code{return} keyword, while an \emph{implicit}
+return statement is a statement that is not formed by the \code{return} keyword,
+but must be the last statement of a method that can have any side effects. This
+can happen in methods with a void return type. An example is a statement that is
+inside one or more blocks. The last statement of a method could for instance be
+an if-statement, but the last statement that is executed in the method, and that
+can have any side effects, may be located inside the block of the else part of
+the if-statement.
+
+The responsibility for checking that the last statement of the selection
+eventually ends in a return or throw statement, is put on the
+\type{LastStatementOfSelectionEndsInReturnOrThrowChecker}. For every node
+visited, if it is a statement, it does a test to see if the statement is a
+return, a throw or if it is an implicit return statement. If this is the case,
+no further checking is done. This checking is done in the \code{preVisit2}
+method \see{astVisitor}. If the node is not of a type that is being handled by
+its type specific visit method, the checker performs a simple test. If the node
+being visited is not the last statement of its parent that is also enclosed by
+the selection, an \type{IllegalStatementFoundException} is thrown. This ensures
+that all statements are taken care of, one way or the other. It also ensures
+that the checker is conservative in the way it checks for legality of the
+selection.
+
+To examine if a statement is an implicit return statement, the checker first
+finds the last statement declared in its enclosing method. If this statement is
+the same as the one under investigation, it is considered an implicit return
+statement. If the statements are not the same, the checker does a search to see
+if statement examined is also the last statement of the method that can be
+reached. This includes the last statement of a block statement, a labeled
+statement, a synchronized statement or a try statement, that in turn is the last
+statement enclosed by the statement types listed. This search goes through all
+the parents of a statement until a statement is found that is not one of the
+mentioned acceptable parent statements. If the search ends in a method
+declaration, then the statement is considered to be the last reachable statement
+of the method, and thus also an implicit return statement.
+
+There are two kinds of statements that are handled explicitly. It is
+if-statements and try-statements. Block, labeled and do-statements are handled
+by fall-through to the other two. Do-statements are considered equal to blocks
+in this context, since their bodies are always evaluated at least one time. If-
+and try-statements are visited only if they are the last node of their parent
+within the selection.
+
+For if-statements, the rule is that if the then-part does not contain any return
+or throw statements, it is considered illegal. If it does contain a return or
+throw, its else-part is checked. If the else-part is non-existent, or it does
+not contain any return or throw statements, it is considered illegal. If the
+statement is not regarded illegal, its children are visited.
+
+Try-statements are handled much the same way as if-statements. Its body must
+contain a return or throw. The same applies to its catch clauses and finally
+body.
+
+If the checker does not complain at any point, the selection is considered valid
+with respect to return statements.
+
+\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 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 \name{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 robustness but also its effect on different software metrics.
+
+\section{The benchmark setup}
+The benchmark itself is set up as a \name{JUnit} test case. This is a convenient
+setup, and utilizes the \name{JUnit Plugin Test Launcher}. This provides us a
+with a fully functional \name{Eclipse} workbench. Most importantly, this gives
+us access to the Java Model of \name{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 \name{Stack
+Overflow}\footnote{\url{https://stackoverflow.com/questions/12401297}}. It
+contains enough dirty details to be considered inconvenient 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 \name{AspectJ}.
+
+\subsection{AspectJ}
+\name{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}{aspectj}
+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
+methods 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
+\name{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, \name{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 \name{Eclipse}
+application may very well work close to its memory limit for the heap space for
+long periods during the benchmark.
+
+\subsection{Memento}
+\todoin{Write}
+
+
+\chapter{Technicalities}
+
+\section{Source code organization}
+All the parts of this master project is under version control with
+\name{Git}\footnote{\url{http://git-scm.com/}}.
+
+The software written is organized as some \name{Eclipse} plugins. Writing a plugin is
+the natural way to utilize the API of \name{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 \name{Eclipse}, one has access to resources such as the
+current workspace, the open editor and the current selection.
+
+The thesis work is contained in the following Eclipse projects:
+
+\begin{description}
+ \item[no.uio.ifi.refaktor] \hfill \\ This is the main Eclipse plugin
+ project, and contains all of the business logic for the plugin.
+
+ \item[no.uio.ifi.refaktor.tests] \hfill \\
+ This project contains the tests for the main plugin.
+
+ \item[no.uio.ifi.refaktor.examples] \hfill \\
+ Contains example code used in testing. It also contains code for managing
+ this example code, such as creating an Eclipse project from it before a test
+ run.
+
+ \item[no.uio.ifi.refaktor.benchmark] \hfill \\
+ This project contains code for running search based versions of the
+ composite refactoring over selected Eclipse projects.
+
+ \item[no.uio.ifi.refaktor.releng] \hfill \\
+ Contains the rmap, queries and target definitions needed by by Buckminster
+ on the Jenkins continuous integration server.
+
+\end{description}
+
+\subsection{The no.uio.ifi.refaktor project}
+
+\subsubsection{no.uio.ifi.refaktor.analyze}
+This package, and its subpackages, contains code that is used for analyzing Java
+source code. The most important subpackages are presented below.
+
+\begin{description}
+ \item[no.uio.ifi.refaktor.analyze.analyzers] \hfill \\
+ This package contains source code analyzers. These are usually responsible
+ for analyzing text selections or running specialized analyzers for different
+ kinds of entities. Their structure are often hierarchical. This means that
+ you have an analyzer for text selections, that in turn is utilized by an
+ analyzer that analyzes all the selections of a method. Then there are
+ analyzers for analyzing all the methods of a type, all the types of a
+ compilation unit, all the compilation units of a package, and, at last, all
+ of the packages in a project.
+
+ \item[no.uio.ifi.refaktor.analyze.checkers] \hfill \\
+ A package containing checkers. The checkers are classes used to validate
+ that a selection can be further analyzed and chosen as a candidate for a
+ refactoring. Invalidating properties can be such as usage of inner classes
+ or the need for multiple return values.
+
+ \item[no.uio.ifi.refaktor.analyze.collectors] \hfill \\
+ This package contains the property collectors. Collectors are used to gather
+ properties from a text selection. This is mostly properties regarding
+ referenced names and their occurrences. It is these properties that makes up
+ the basis for finding the best candidates for a refactoring.
+\end{description}
+
+\subsubsection{no.uio.ifi.refaktor.change}
+This package, and its subpackages, contains functionality for manipulate source
+code.
+
+\begin{description}
+ \item[no.uio.ifi.refaktor.change.changers] \hfill \\
+ This package contains source code changers. They are used to glue together
+ the analysis of source code and the actual execution of the changes.
+
+ \item[no.uio.ifi.refaktor.change.executors] \hfill \\
+ The executors that are responsible for making concrete changes are found in
+ this package. They are mostly used to create and execute one or more Eclipse
+ refactorings.
+
+ \item[no.uio.ifi.refaktor.change.processors] \hfill \\
+ Contains a refactoring processor for the \MoveMethod refactoring. The code
+ is stolen and modified to fix a bug. The related bug is described in
+ \myref{eclipse_bug_429416}.
+
+\end{description}
+
+\subsubsection{no.uio.ifi.refaktor.handlers}
+This package contains handlers for the commands defined in the plugin manifest.
+
+\subsubsection{no.uio.ifi.refaktor.prefix}
+This package contains the \type{Prefix} type that is the data representation of
+the prefixes found by the \type{PrefixesCollector}. It also contains the prefix
+set for storing and working with prefixes.
+
+\subsubsection{no.uio.ifi.refaktor.statistics}
+The package contains statistics functionality. Its heart is the statistics
+aspect that is responsible for gathering statistics during the execution of the
+\ExtractAndMoveMethod refactoring.
+
+\begin{description}
+ \item[no.uio.ifi.refaktor.statistics.reports] \hfill \\
+ This package contains a simple framework for generating reports from the
+ statistics data generated by the aspect. Currently, the only available
+ report type is a simple text report.
+
+\end{description}
+
+
+\subsubsection{no.uio.ifi.refaktor.textselection}
+This package contains the two custom text selections that are used extensively
+throughout the project. One of them is just a subclass of the other, to support
+the use of the memento pattern to optimize the memory usage during benchmarking.
+
+\subsubsection{no.uio.ifi.refaktor.debugging}
+The package contains a debug utility class. I addition to this, the package
+\code{no.uio.ifi.refaktor.utils.aspects} contains a couple of aspects used for
+debugging purposes.
+
+\subsubsection{no.uio.ifi.refaktor.utils}
+Utility package that contains all the functionality that has to do with parsing
+of source code. It also has utility classes for looking up handles to methods
+and types et cetera.
+
+\begin{description}
+ \item[no.uio.ifi.refaktor.utils.caching] \hfill \\
+ This package contains the caching manager for compilation units, along with
+ classes for different caching strategies.
+
+ \item[no.uio.ifi.refaktor.utils.nullobjects] \hfill \\
+ Contains classes for creating different null objects. Most of the classes is
+ used to represent null objects of different handle types. These null objects
+ are returned from various utility classes instead of returning a \var{null}
+ value when other values are not available.
+
+\end{description}
+
+\section{Continuous integration}
+The continuous integration server
+\name{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 \name{Eclipse} plugins and run tests for them with Jenkins, the
+component assembly project
+\name{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 \name{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 \name{Eclipse}, the specialized compilation and the
+weaving can be handled by the \name{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 \name{Eclipse}
+plugins outside of \name{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 \name{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 \name{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 \name{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{Eclipse Bugs Found}
+\newcommand{\submittedBugReport}[1]{The submitted bug report can be found on
+ \url{#1}.}
\section{Eclipse bug 420726: Code is broken when moving a method that is
-assigning to the parameter that is also the move destination}
-This bug\footnote{\url{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=420726}}
+assigning to the parameter that is also the move
+destination}\label{eclipse_bug_420726}
+This bug
was found when analyzing what kinds of names that was to be considered as
-\emph{unfixes}.\todo{refer to unfixes}
+\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
+variable and also is assigned to within the method body. \name{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.
+in Java.
+\submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=420726}
\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}}
+\section{Eclipse bug 429416: IAE when moving method from anonymous
+class}\label{eclipse_bug_429416}
+I discovered
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
+This bug surfaces when trying to use the \refa{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 analyses the program and finds it necessary to pass an instance of
+simulation as well as in \name{Eclipse}, through the user interface. It only occurs
+when \name{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
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
+method's declaring class, if the declaring class is either an anonymous class 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}.
+\type{IllegalArgumentException}.
+\submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429416}
\subsection{How I solved the problem}
Since the \type{MoveInstanceMethodProcessor} is instantiated in the
\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}.
+\typewithref{no.uio.ifi.refaktor.change.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
+was discovered when doing some changes to the way unfixes is computed.
+
+\subsection{The bug}
+The problem is that \name{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.
+\submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429954}
+
+\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 \refa{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{Conclusions and Future Work}
+\todoin{Write}
+\section{Future work}
+\todoin{Metrics, \ldots}
+
\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.
+mainly focuses on \name{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
+quick-assist with Ctrl+1 in \name{Eclipse}} and be promptly executed, opposed to in the
+currently dominating wizard-based refactoring paradigm. They are meant 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
\backmatter{}
+\printglossaries
\printbibliography
\listoftodos
\end{document}
git://git.uio.no / ifi-stolz-refaktor.git / blobdiff