1 \documentclass[USenglish,11pt]{ifimaster}
3 \usepackage[utf8]{inputenc}
4 \usepackage[T1]{fontenc,url}
5 \usepackage{lmodern} % using Latin Modern to be able to use bold typewriter font
11 \usepackage{tikz-qtree}
12 \usetikzlibrary{shapes,snakes,trees,arrows,shadows,positioning,calc}
13 \usepackage{babel,textcomp,csquotes,ifimasterforside}
16 \usepackage[hidelinks]{hyperref}
18 \usepackage[xindy]{glossaries}
20 \usepackage[style=alphabetic,backend=biber]{biblatex}
22 \usepackage{mathtools}
24 % use 'disable' before printing:
25 \usepackage[]{todonotes}
32 \usepackage{perpage} %the perpage package
33 \MakePerPage{footnote} %the perpage package command
35 \theoremstyle{definition}
36 \newtheorem*{wordDef}{Definition}
37 \newtheorem*{theorem}{Theorem}
39 \graphicspath{ {./figures/} }
41 \newcommand{\citing}[1]{~\cite{#1}}
42 %\newcommand{\myref}[1]{\cref{#1} on \cpageref{#1}}
43 \newcommand{\myref}[1]{\vref{#1}}
44 \newcommand{\Myref}[1]{\Vref{#1}}
46 %\newcommand{\glossref}[1]{\textsuperscript{(\glsrefentry{#1})}}
47 %\newcommand{\gloss}[1]{\gls{#1}\glossref{#1}}
48 %\newcommand{\glosspl}[1]{\glspl{#1}\glossref{#1}}
49 \newcommand{\gloss}[1]{\gls{#1}}
50 \newcommand{\glosspl}[1]{\glspl{#1}}
52 \newcommand{\definition}[1]{\begin{wordDef}#1\end{wordDef}}
53 \newcommand{\see}[1]{(see \myref{#1})}
54 \newcommand{\explanation}[3]{\noindent\textbf{\textit{#1}}\\*\emph{When:}
55 #2\\*\emph{How:} #3\\*[-7px]}
57 %\newcommand{\type}[1]{\lstinline{#1}}
58 \newcommand{\code}[1]{\texttt{\textbf{#1}}}
59 \newcommand{\type}[1]{\code{#1}}
60 \newcommand{\typeref}[1]{\footnote{\type{#1}}}
61 \newcommand{\typewithref}[2]{\type{#2}\typeref{#1.#2}}
62 \newcommand{\method}[1]{\type{#1}}
63 \newcommand{\methodref}[2]{\footnote{\type{#1}\method{\##2()}}}
64 \newcommand{\methodwithref}[2]{\method{#2}\footnote{\type{#1}\method{\##2()}}}
65 \newcommand{\var}[1]{\type{#1}}
67 \newcommand{\name}[1]{#1}
68 \newcommand{\tit}[1]{\emph{#1}}
69 \newcommand{\refa}[1]{\emph{#1}}
70 \newcommand{\pattern}[1]{\emph{#1}}
71 \newcommand{\metr}[1]{\emph{#1}}
72 \newcommand{\ExtractMethod}{\refa{Extract Method}\xspace}
73 \newcommand{\MoveMethod}{\refa{Move Method}\xspace}
74 \newcommand{\ExtractAndMoveMethod}{\refa{Extract and Move Method}\xspace}
76 \newcommand\todoin[2][]{\todo[inline, caption={#2}, #1]{
77 \begin{minipage}{\textwidth-4pt}#2\end{minipage}}}
79 \title{Automated Composition of Refactorings}
80 \subtitle{Composing the Extract and Move Method refactorings in Eclipse}
81 \author{Erlend Kristiansen}
84 \newglossaryentry{profiling}
87 description={is to run a computer program through a profiler/with a profiler
90 \newglossaryentry{profiler}
93 description={A profiler is a program for analyzing performance within an
94 application. It is used to analyze memory consumption, processing time and
95 frequency of procedure calls and such.}
97 \newglossaryentry{xUnit}
99 name={xUnit framework},
100 description={An xUnit framework is a framework for writing unit tests for a
101 computer program. It follows the patterns known from the JUnit framework for
102 Java\citing{fowlerXunit}
104 plural={xUnit frameworks}
106 \newglossaryentry{softwareObfuscation}
108 name={software obfuscation},
109 description={makes source code harder to read and analyze, while preserving
112 \newglossaryentry{extractClass}
114 name=\refa{Extract Class},
115 description={The \refa{Extract Class} refactoring works by creating a class,
116 for then to move members from another class to that class and access them from
117 the old class via a reference to the new class}
119 \newglossaryentry{designPattern}
121 name={design pattern},
122 description={A design pattern is a named abstraction, that is meant to solve a
123 general design problem. It describes the key aspects of a common problem and
124 identifies its participators and how they collaborate},
125 plural={design patterns}
127 %\newglossaryentry{extractMethod}
129 % name=\refa{Extract Method},
130 % description={The \refa{Extract Method} refactoring is used to extract a
131 %fragment of code from its context and into a new method. A call to the new
132 %method is inlined where the fragment was before. It is used to break code into
133 %logical units, with names that explain their purpose}
135 %\newglossaryentry{moveMethod}
137 % name=\refa{Move Method},
138 % description={The \refa{Move Method} refactoring is used to move a method from
139 % one class to another. This is useful if the method is using more features of
140 % another class than of the class which it is currently defined. Then all calls
141 % to this method must be updated, or the method must be copied, with the old
142 %method delegating to the new method}
145 \bibliography{bibliography/master-thesis-erlenkr-bibliography}
147 % UML comment in TikZ:
148 % ref: https://tex.stackexchange.com/questions/103688/folded-paper-shape-tikz
150 \pgfdeclareshape{umlcomment}{
151 \inheritsavedanchors[from=rectangle] % this is nearly a rectangle
152 \inheritanchorborder[from=rectangle]
153 \inheritanchor[from=rectangle]{center}
154 \inheritanchor[from=rectangle]{north}
155 \inheritanchor[from=rectangle]{south}
156 \inheritanchor[from=rectangle]{west}
157 \inheritanchor[from=rectangle]{east}
158 % ... and possibly more
159 \backgroundpath{% this is new
160 % store lower right in xa/ya and upper right in xb/yb
161 \southwest \pgf@xa=\pgf@x \pgf@ya=\pgf@y
162 \northeast \pgf@xb=\pgf@x \pgf@yb=\pgf@y
163 % compute corner of ‘‘flipped page’’
164 \pgf@xc=\pgf@xb \advance\pgf@xc by-10pt % this should be a parameter
165 \pgf@yc=\pgf@yb \advance\pgf@yc by-10pt
166 % construct main path
167 \pgfpathmoveto{\pgfpoint{\pgf@xa}{\pgf@ya}}
168 \pgfpathlineto{\pgfpoint{\pgf@xa}{\pgf@yb}}
169 \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yb}}
170 \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@yc}}
171 \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@ya}}
174 \pgfpathmoveto{\pgfpoint{\pgf@xc}{\pgf@yb}}
175 \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yc}}
176 \pgfpathlineto{\pgfpoint{\pgf@xb}{\pgf@yc}}
177 \pgfpathlineto{\pgfpoint{\pgf@xc}{\pgf@yc}}
182 \tikzstyle{comment}=[%
195 %\interfootnotelinepenalty=10000
198 \pagenumbering{roman}
204 \todoin{\textbf{Remove all todos (including list) before delivery/printing!!!
205 Can be done by removing ``draft'' from documentclass.}}
206 \todoin{Write abstract}
214 The discussions in this report must be seen in the context of object oriented
215 programming languages, and Java in particular, since that is the language in
216 which most of the examples will be given. All though the techniques discussed
217 may be applicable to languages from other paradigms, they will not be the
218 subject of this report.
222 \chapter{What is Refactoring?}
224 This question is best answered by first defining the concept of a
225 \emph{refactoring}, what it is to \emph{refactor}, and then discuss what aspects
226 of programming make people want to refactor their code.
228 \section{Defining refactoring}
229 Martin Fowler, in his classic book on refactoring\citing{refactoring}, defines a
230 refactoring like this:
233 \emph{Refactoring} (noun): a change made to the internal
234 structure\footnote{The structure observable by the programmer.} of software to
235 make it easier to understand and cheaper to modify without changing its
236 observable behavior.~\cite[p.~53]{refactoring}
239 \noindent This definition assigns additional meaning to the word
240 \emph{refactoring}, beyond the composition of the prefix \emph{re-}, usually
241 meaning something like ``again'' or ``anew'', and the word \emph{factoring},
242 that can mean to isolate the \emph{factors} of something. Here a \emph{factor}
243 would be close to the mathematical definition of something that divides a
244 quantity, without leaving a remainder. Fowler is mixing the \emph{motivation}
245 behind refactoring into his definition. Instead it could be more refined, formed
246 to only consider the \emph{mechanical} and \emph{behavioral} aspects of
247 refactoring. That is to factor the program again, putting it together in a
248 different way than before, while preserving the behavior of the program. An
249 alternative definition could then be:
251 \definition{A \emph{refactoring} is a transformation
252 done to a program without altering its external behavior.}
254 From this we can conclude that a refactoring primarily changes how the
255 \emph{code} of a program is perceived by the \emph{programmer}, and not the
256 \emph{behavior} experienced by any user of the program. Although the logical
257 meaning is preserved, such changes could potentially alter the program's
258 behavior when it comes to performance gain or -penalties. So any logic depending
259 on the performance of a program could make the program behave differently after
262 In the extreme case one could argue that \gloss{softwareObfuscation} is
263 refactoring. It is often used to protect proprietary software. It restrains
264 uninvited viewers, so they have a hard time analyzing code that they are not
265 supposed to know how works. This could be a problem when using a language that
266 is possible to decompile, such as Java.
268 Obfuscation could be done composing many, more or less randomly chosen,
269 refactorings. Then the question arises whether it can be called a
270 \emph{composite refactoring} or not \see{compositeRefactorings}? The answer is
271 not obvious. First, there is no way to describe the mechanics of software
272 obfuscation, because there are infinitely many ways to do that. Second,
273 obfuscation can be thought of as \emph{one operation}: Either the code is
274 obfuscated, or it is not. Third, it makes no sense to call software obfuscation
275 \emph{a refactoring}, since it holds different meaning to different people.
277 This last point is important, since one of the motivations behind defining
278 different refactorings, is to establish a \emph{vocabulary} for software
279 professionals to use when reasoning about and discussing programs, similar to
280 the motivation behind \glosspl{designPattern}\citing{designPatterns}.
282 So for describing \emph{software obfuscation}, it might be more appropriate to
283 define what you do when performing it rather than precisely defining its
284 mechanics in terms of other refactorings.
287 \section{The etymology of 'refactoring'}
288 It is a little difficult to pinpoint the exact origin of the word
289 ``refactoring'', as it seems to have evolved as part of a colloquial
290 terminology, more than a scientific term. There is no authoritative source for a
291 formal definition of it.
293 According to Martin Fowler\citing{etymology-refactoring}, there may also be more
294 than one origin of the word. The most well-known source, when it comes to the
295 origin of \emph{refactoring}, is the
296 Smalltalk\footnote{\label{footNote}Programming language} community and their
297 infamous \name{Refactoring
298 Browser}\footnote{\url{http://st-www.cs.illinois.edu/users/brant/Refactory/RefactoringBrowser.html}}
299 described in the article \tit{A Refactoring Tool for
300 Smalltalk}\citing{refactoringBrowser1997}, published in 1997.
301 Allegedly\citing{etymology-refactoring}, the metaphor of factoring programs was
302 also present in the Forth\textsuperscript{\ref{footNote}} community, and the
303 word ``refactoring'' is mentioned in a book by Leo Brodie, called \tit{Thinking
304 Forth}\citing{brodie2004}, first published in 1984\footnote{\tit{Thinking Forth}
305 was first published in 1984 by the \name{Forth Interest Group}. Then it was
306 reprinted in 1994 with minor typographical corrections, before it was
307 transcribed into an electronic edition typeset in \LaTeX\ and published under a
308 Creative Commons licence in
309 2004. The edition cited here is the 2004 edition, but the content should
310 essentially be as in 1984.}. The exact word is only printed one
311 place~\cite[p.~232]{brodie2004}, but the term \emph{factoring} is prominent in
312 the book, that also contains a whole chapter dedicated to (re)factoring, and how
313 to keep the (Forth) code clean and maintainable.
316 \ldots good factoring technique is perhaps the most important skill for a
317 Forth programmer.~\cite[p.~172]{brodie2004}
320 \noindent Brodie also express what \emph{factoring} means to him:
323 Factoring means organizing code into useful fragments. To make a fragment
324 useful, you often must separate reusable parts from non-reusable parts. The
325 reusable parts become new definitions. The non-reusable parts become arguments
326 or parameters to the definitions.~\cite[p.~172]{brodie2004}
329 Fowler claims that the usage of the word \emph{refactoring} did not pass between
330 the \name{Forth} and \name{Smalltalk} communities, but that it emerged
331 independently in each of the communities.
333 \section{Motivation -- Why people refactor}
334 There are many reasons why people want to refactor their programs. They can for
335 instance do it to remove duplication, break up long methods or to introduce
336 design patterns into their software systems. The shared trait for all these are
337 that peoples' intentions are to make their programs \emph{better}, in some
338 sense. But what aspects of their programs are becoming improved?
340 As just mentioned, people often refactor to get rid of duplication. They are
341 moving identical or similar code into methods, and are pushing methods up or
342 down in their class hierarchies. They are making template methods for
343 overlapping algorithms/functionality, and so on. It is all about gathering what
344 belongs together and putting it all in one place. The resulting code is then
345 easier to maintain. When removing the implicit coupling\footnote{When
346 duplicating code, the duplicate pieces of code might not be coupled, apart
347 from representing the same functionality. So if this functionality is going to
348 change, it might need to change in more than one place, thus creating an
349 implicit coupling between multiple pieces of code.} between code snippets, the
350 location of a bug is limited to only one place, and new functionality need only
351 to be added to this one place, instead of a number of places people might not
354 A problem you often encounter when programming, is that a program contains a lot
355 of long and hard-to-grasp methods. It can then help to break the methods into
356 smaller ones, using the \ExtractMethod refactoring\citing{refactoring}. Then
357 you may discover something about a program that you were not aware of before;
358 revealing bugs you did not know about or could not find due to the complex
359 structure of your program. \todo{Proof?} Making the methods smaller and giving
360 good names to the new ones clarifies the algorithms and enhances the
361 \emph{understandability} of the program \see{magic_number_seven}. This makes
362 refactoring an excellent method for exploring unknown program code, or code that
363 you had forgotten that you wrote.
365 Most primitive refactorings are simple, and usually involves moving code
366 around\citing{kerievsky2005}. The motivation behind them may first be revealed
367 when they are combined into larger --- higher level --- refactorings, called
368 \emph{composite refactorings} \see{compositeRefactorings}. Often the goal of
369 such a series of refactorings is a design pattern. Thus the design can
370 \emph{evolve} throughout the lifetime of a program, as opposed to designing
371 up-front. It is all about being structured and taking small steps to improve a
374 Many software design pattern are aimed at lowering the coupling between
375 different classes and different layers of logic. One of the most famous is
376 perhaps the \pattern{Model-View-Controller}\citing{designPatterns} pattern. It
377 is aimed at lowering the coupling between the user interface, the business logic
378 and the data representation of a program. This also has the added benefit that
379 the business logic could much easier be the target of automated tests, thus
380 increasing the productivity in the software development process.
382 Another effect of refactoring is that with the increased separation of concerns
383 coming out of many refactorings, the \emph{performance} can be improved. When
384 profiling programs, the problematic parts are narrowed down to smaller parts of
385 the code, which are easier to tune, and optimization can be performed only where
386 needed and in a more effective way\citing{refactoring}.
388 Last, but not least, and this should probably be the best reason to refactor, is
389 to refactor to \emph{facilitate a program change}. If one has managed to keep
390 one's code clean and tidy, and the code is not bloated with design patterns that
391 are not ever going to be needed, then some refactoring might be needed to
392 introduce a design pattern that is appropriate for the change that is going to
395 Refactoring program code --- with a goal in mind --- can give the code itself
396 more value. That is in the form of robustness to bugs, understandability and
397 maintainability. Having robust code is an obvious advantage, but
398 understandability and maintainability are both very important aspects of
399 software development. By incorporating refactoring in the development process,
400 bugs are found faster, new functionality is added more easily and code is easier
401 to understand by the next person exposed to it, which might as well be the
402 person who wrote it. The consequence of this, is that refactoring can increase
403 the average productivity of the development process, and thus also add to the
404 monetary value of a business in the long run. The perspective on productivity
405 and money should also be able to open the eyes of the many nearsighted managers
406 that seldom see beyond the next milestone.
408 \section{The magical number seven}\label{magic_number_seven}
409 The article \tit{The magical number seven, plus or minus two: some limits on our
410 capacity for processing information}\citing{miller1956} by George A. Miller,
411 was published in the journal \name{Psychological Review} in 1956. It presents
412 evidence that support that the capacity of the number of objects a human being
413 can hold in its working memory is roughly seven, plus or minus two objects. This
414 number varies a bit depending on the nature and complexity of the objects, but
415 is according to Miller ``\ldots never changing so much as to be
418 Miller's article culminates in the section called \emph{Recoding}, a term he
419 borrows from communication theory. The central result in this section is that by
420 recoding information, the capacity of the amount of information that a human can
421 process at a time is increased. By \emph{recoding}, Miller means to group
422 objects together in chunks, and give each chunk a new name that it can be
426 \ldots recoding is an extremely powerful weapon for increasing the amount of
427 information that we can deal with.~\cite[p.~95]{miller1956}
430 By organizing objects into patterns of ever growing depth, one can memorize and
431 process a much larger amount of data than if it were to be represented as its
432 basic pieces. This grouping and renaming is analogous to how many refactorings
433 work, by grouping pieces of code and give them a new name. Examples are the
434 fundamental \ExtractMethod and \refa{Extract Class}
435 refactorings\citing{refactoring}.
437 An example from the article addresses the problem of memorizing a sequence of
438 binary digits. The example presented here is a slightly modified version of the
439 one presented in the original article\citing{miller1956}, but it preserves the
440 essence of it. Let us say we have the following sequence of
441 16 binary digits: ``1010001001110011''. Most of us will have a hard time
442 memorizing this sequence by only reading it once or twice. Imagine if we instead
443 translate it to this sequence: ``A273''. If you have a background from computer
444 science, it will be obvious that the latter sequence is the first sequence
445 recoded to be represented by digits in base 16. Most people should be able to
446 memorize this last sequence by only looking at it once.
448 Another result from the Miller article is that when the amount of information a
449 human must interpret increases, it is crucial that the translation from one code
450 to another must be almost automatic for the subject to be able to remember the
451 translation, before \heshe is presented with new information to recode. Thus
452 learning and understanding how to best organize certain kinds of data is
453 essential to efficiently handle that kind of data in the future. This is much
454 like when humans learn to read. First they must learn how to recognize letters.
455 Then they can learn distinct words, and later read sequences of words that form
456 whole sentences. Eventually, most of them will be able to read whole books and
457 briefly retell the important parts of its content. This suggest that the use of
458 design patterns is a good idea when reasoning about computer programs. With
459 extensive use of design patterns when creating complex program structures, one
460 does not always have to read whole classes of code to comprehend how they
461 function, it may be sufficient to only see the name of a class to almost fully
462 understand its responsibilities.
465 Our language is tremendously useful for repackaging material into a few chunks
466 rich in information.~\cite[p.~95]{miller1956}
469 Without further evidence, these results at least indicate that refactoring
470 source code into smaller units with higher cohesion and, when needed,
471 introducing appropriate design patterns, should aid in the cause of creating
472 computer programs that are easier to maintain and have code that is easier (and
475 \section{Notable contributions to the refactoring literature}
476 \todoin{Thinking Forth?}
479 \item[1992] William F. Opdyke submits his doctoral dissertation called
480 \tit{Refactoring Object-Oriented Frameworks}\citing{opdyke1992}. This work
481 defines a set of refactorings, that are behavior preserving given that their
482 preconditions are met. The dissertation is focused on the automation of
484 \item[1999] Martin Fowler et al.: \tit{Refactoring: Improving the Design of
485 Existing Code}\citing{refactoring}. This is maybe the most influential text
486 on refactoring. It bares similarities with Opdykes thesis\citing{opdyke1992}
487 in the way that it provides a catalog of refactorings. But Fowler's book is
488 more about the craft of refactoring, as he focuses on establishing a
489 vocabulary for refactoring, together with the mechanics of different
490 refactorings and when to perform them. His methodology is also founded on
491 the principles of test-driven development.
492 \item[2005] Joshua Kerievsky: \tit{Refactoring to
493 Patterns}\citing{kerievsky2005}. This book is heavily influenced by Fowler's
494 \tit{Refactoring}\citing{refactoring} and the ``Gang of Four'' \tit{Design
495 Patterns}\citing{designPatterns}. It is building on the refactoring
496 catalogue from Fowler's book, but is trying to bridge the gap between
497 \emph{refactoring} and \emph{design patterns} by providing a series of
498 higher-level composite refactorings, that makes code evolve toward or away
499 from certain design patterns. The book is trying to build up the reader's
500 intuition around \emph{why} one would want to use a particular design
501 pattern, and not just \emph{how}. The book is encouraging evolutionary
502 design \see{relationToDesignPatterns}.
505 \section{Tool support (for Java)}\label{toolSupport}
506 This section will briefly compare the refactoring support of the three IDEs
507 \name{Eclipse}\footnote{\url{http://www.eclipse.org/}}, \name{IntelliJ
508 IDEA}\footnote{The IDE under comparison is the \name{Community Edition},
509 \url{http://www.jetbrains.com/idea/}} and
510 \name{NetBeans}\footnote{\url{https://netbeans.org/}}. These are the most
511 popular Java IDEs\citing{javaReport2011}.
513 All three IDEs provide support for the most useful refactorings, like the
514 different extract, move and rename refactorings. In fact, Java-targeted IDEs are
515 known for their good refactoring support, so this did not appear as a big
518 The IDEs seem to have excellent support for the \ExtractMethod refactoring, so
519 at least they have all passed the first ``refactoring
520 rubicon''\citing{fowlerRubicon2001,secondRubicon2012}.
522 Regarding the \MoveMethod refactoring, the \name{Eclipse} and \name{IntelliJ}
523 IDEs do the job in very similar manners. In most situations they both do a
524 satisfying job by producing the expected outcome. But they do nothing to check
525 that the result does not break the semantics of the program \see{correctness}.
526 The \name{NetBeans} IDE implements this refactoring in a somewhat
527 unsophisticated way. For starters, the refactoring's default destination for the
528 move, is the same class as the method already resides in, although it refuses to
529 perform the refactoring if chosen. But the worst part is, that if moving the
530 method \method{f} of the class \type{C} to the class \type{X}, it will break the
531 code. The result is shown in \myref{lst:moveMethod_NetBeans}.
535 \begin{minted}[samepage]{java}
548 \begin{minted}[samepage]{java}
558 \caption{Moving method \method{f} from \type{C} to \type{X}.}
559 \label{lst:moveMethod_NetBeans}
562 \name{NetBeans} will try to create code that call the methods \method{m} and \method{n}
563 of \type{X} by accessing them through \var{c.x}, where \var{c} is a parameter of
564 type \type{C} that is added the method \method{f} when it is moved. (This is
565 seldom the desired outcome of this refactoring, but ironically, this ``feature''
566 keeps \name{NetBeans} from breaking the code in the example from \myref{correctness}.)
567 If \var{c.x} for some reason is inaccessible to \type{X}, as in this case, the
568 refactoring breaks the code, and it will not compile. \name{NetBeans} presents a
569 preview of the refactoring outcome, but the preview does not catch it if the IDE
570 is about break the program.
572 The IDEs under investigation seem to have fairly good support for primitive
573 refactorings, but what about more complex ones, such as
574 \gloss{extractClass}\citing{refactoring}? \name{IntelliJ} handles this in a
575 fairly good manner, although, in the case of private methods, it leaves unused
576 methods behind. These are methods that delegate to a field with the type of the
577 new class, but are not used anywhere. \name{Eclipse} has added its own quirk to
578 the \refa{Extract Class} refactoring, and only allows for \emph{fields} to be
579 moved to a new class, \emph{not methods}. This makes it effectively only
580 extracting a data structure, and calling it \refa{Extract Class} is a little
581 misleading. One would often be better off with textual extract and paste than
582 using the \refa{Extract Class} refactoring in \name{Eclipse}. When it comes to
583 \name{NetBeans}, it does not even show an attempt on providing this refactoring.
585 \section{The relation to design patterns}\label{relationToDesignPatterns}
587 Refactoring and design patterns have at least one thing in common, they are both
588 promoted by advocates of \emph{clean code}\citing{cleanCode} as fundamental
589 tools on the road to more maintainable and extendable source code.
592 Design patterns help you determine how to reorganize a design, and they can
593 reduce the amount of refactoring you need to do
594 later.~\cite[p.~353]{designPatterns}
597 Although sometimes associated with
598 over-engineering\citing{kerievsky2005,refactoring}, design patterns are in
599 general assumed to be good for maintainability of source code. That may be
600 because many of them are designed to support the \emph{open/closed principle} of
601 object-oriented programming. The principle was first formulated by Bertrand
602 Meyer, the creator of the Eiffel programming language, like this: ``Modules
603 should be both open and closed.''\citing{meyer1988} It has been popularized,
604 with this as a common version:
607 Software entities (classes, modules, functions, etc.) should be open for
608 extension, but closed for modification.\footnote{See
609 \url{http://c2.com/cgi/wiki?OpenClosedPrinciple} or
610 \url{https://en.wikipedia.org/wiki/Open/closed_principle}}
613 Maintainability is often thought of as the ability to be able to introduce new
614 functionality without having to change too much of the old code. When
615 refactoring, the motivation is often to facilitate adding new functionality. It
616 is about factoring the old code in a way that makes the new functionality being
617 able to benefit from the functionality already residing in a software system,
618 without having to copy old code into new. Then, next time someone shall add new
619 functionality, it is less likely that the old code has to change. Assuming that
620 a design pattern is the best way to get rid of duplication and assist in
621 implementing new functionality, it is reasonable to conclude that a design
622 pattern often is the target of a series of refactorings. Having a repertoire of
623 design patterns can also help in knowing when and how to refactor a program to
624 make it reflect certain desired characteristics.
627 There is a natural relation between patterns and refactorings. Patterns are
628 where you want to be; refactorings are ways to get there from somewhere
629 else.~\cite[p.~107]{refactoring}
632 This quote is wise in many contexts, but it is not always appropriate to say
633 ``Patterns are where you want to be\ldots''. \emph{Sometimes}, patterns are
634 where you want to be, but only because it will benefit your design. It is not
635 true that one should always try to incorporate as many design patterns as
636 possible into a program. It is not like they have intrinsic value. They only add
637 value to a system when they support its design. Otherwise, the use of design
638 patterns may only lead to a program that is more complex than necessary.
641 The overuse of patterns tends to result from being patterns happy. We are
642 \emph{patterns happy} when we become so enamored of patterns that we simply
643 must use them in our code.~\cite[p.~24]{kerievsky2005}
646 This can easily happen when relying largely on up-front design. Then it is
647 natural, in the very beginning, to try to build in all the flexibility that one
648 believes will be necessary throughout the lifetime of a software system.
649 According to Joshua Kerievsky ``That sounds reasonable --- if you happen to be
650 psychic.''~\cite[p.~1]{kerievsky2005} He is advocating what he believes is a
651 better approach: To let software continually evolve. To start with a simple
652 design that meets today's needs, and tackle future needs by refactoring to
653 satisfy them. He believes that this is a more economic approach than investing
654 time and money into a design that inevitably is going to change. By relying on
655 continuously refactoring a system, its design can be made simpler without
656 sacrificing flexibility. To be able to fully rely on this approach, it is of
657 utter importance to have a reliable suit of tests to lean on \see{testing}. This
658 makes the design process more natural and less characterized by difficult
659 decisions that has to be made before proceeding in the process, and that is
660 going to define a project for all of its unforeseeable future.
664 \section{Classification of refactorings}
665 % only interesting refactorings
666 % with 2 detailed examples? One for structured and one for intra-method?
667 % Is replacing Bubblesort with Quick Sort considered a refactoring?
669 \subsection{Structural refactorings}
671 \subsubsection{Primitive refactorings}
674 \explanation{Extract Method}{You have a code fragment that can be grouped
675 together.}{Turn the fragment into a method whose name explains the purpose of
678 \explanation{Inline Method}{A method's body is just as clear as its name.}{Put
679 the method's body into the body of its callers and remove the method.}
681 \explanation{Inline Temp}{You have a temp that is assigned to once with a simple
682 expression, and the temp is getting in the way of other refactorings.}{Replace
683 all references to that temp with the expression}
685 % Moving Features Between Objects
686 \explanation{Move Method}{A method is, or will be, using or used by more
687 features of another class than the class on which it is defined.}{Create a new
688 method with a similar body in the class it uses most. Either turn the old method
689 into a simple delegation, or remove it altogether.}
691 \explanation{Move Field}{A field is, or will be, used by another class more than
692 the class on which it is defined}{Create a new field in the target class, and
693 change all its users.}
696 \explanation{Replace Magic Number with Symbolic Constant}{You have a literal
697 number with a particular meaning.}{Create a constant, name it after the meaning,
698 and replace the number with it.}
700 \explanation{Encapsulate Field}{There is a public field.}{Make it private and
703 \explanation{Replace Type Code with Class}{A class has a numeric type code that
704 does not affect its behavior.}{Replace the number with a new class.}
706 \explanation{Replace Type Code with Subclasses}{You have an immutable type code
707 that affects the behavior of a class.}{Replace the type code with subclasses.}
709 \explanation{Replace Type Code with State/Strategy}{You have a type code that
710 affects the behavior of a class, but you cannot use subclassing.}{Replace the
711 type code with a state object.}
713 % Simplifying Conditional Expressions
714 \explanation{Consolidate Duplicate Conditional Fragments}{The same fragment of
715 code is in all branches of a conditional expression.}{Move it outside of the
718 \explanation{Remove Control Flag}{You have a variable that is acting as a
719 control flag fro a series of boolean expressions.}{Use a break or return
722 \explanation{Replace Nested Conditional with Guard Clauses}{A method has
723 conditional behavior that does not make clear the normal path of
724 execution.}{Use guard clauses for all special cases.}
726 \explanation{Introduce Null Object}{You have repeated checks for a null
727 value.}{Replace the null value with a null object.}
729 \explanation{Introduce Assertion}{A section of code assumes something about the
730 state of the program.}{Make the assumption explicit with an assertion.}
732 % Making Method Calls Simpler
733 \explanation{Rename Method}{The name of a method does not reveal its
734 purpose.}{Change the name of the method}
736 \explanation{Add Parameter}{A method needs more information from its
737 caller.}{Add a parameter for an object that can pass on this information.}
739 \explanation{Remove Parameter}{A parameter is no longer used by the method
742 %\explanation{Parameterize Method}{Several methods do similar things but with
743 %different values contained in the method.}{Create one method that uses a
744 %parameter for the different values.}
746 \explanation{Preserve Whole Object}{You are getting several values from an
747 object and passing these values as parameters in a method call.}{Send the whole
750 \explanation{Remove Setting Method}{A field should be set at creation time and
751 never altered.}{Remove any setting method for that field.}
753 \explanation{Hide Method}{A method is not used by any other class.}{Make the
756 \explanation{Replace Constructor with Factory Method}{You want to do more than
757 simple construction when you create an object}{Replace the constructor with a
760 % Dealing with Generalization
761 \explanation{Pull Up Field}{Two subclasses have the same field.}{Move the field
764 \explanation{Pull Up Method}{You have methods with identical results on
765 subclasses.}{Move them to the superclass.}
767 \explanation{Push Down Method}{Behavior on a superclass is relevant only for
768 some of its subclasses.}{Move it to those subclasses.}
770 \explanation{Push Down Field}{A field is used only by some subclasses.}{Move the
771 field to those subclasses}
773 \explanation{Extract Interface}{Several clients use the same subset of a class's
774 interface, or two classes have part of their interfaces in common.}{Extract the
775 subset into an interface.}
777 \explanation{Replace Inheritance with Delegation}{A subclass uses only part of a
778 superclasses interface or does not want to inherit data.}{Create a field for the
779 superclass, adjust methods to delegate to the superclass, and remove the
782 \explanation{Replace Delegation with Inheritance}{You're using delegation and
783 are often writing many simple delegations for the entire interface}{Make the
784 delegating class a subclass of the delegate.}
786 \subsubsection{Composite refactorings}
789 % \explanation{Replace Method with Method Object}{}{}
791 % Moving Features Between Objects
792 \explanation{Extract Class}{You have one class doing work that should be done by
793 two}{Create a new class and move the relevant fields and methods from the old
794 class into the new class.}
796 \explanation{Inline Class}{A class isn't doing very much.}{Move all its features
797 into another class and delete it.}
799 \explanation{Hide Delegate}{A client is calling a delegate class of an
800 object.}{Create Methods on the server to hide the delegate.}
802 \explanation{Remove Middle Man}{A class is doing to much simple delegation.}{Get
803 the client to call the delegate directly.}
806 \explanation{Replace Data Value with Object}{You have a data item that needs
807 additional data or behavior.}{Turn the data item into an object.}
809 \explanation{Change Value to Reference}{You have a class with many equal
810 instances that you want to replace with a single object.}{Turn the object into a
813 \explanation{Encapsulate Collection}{A method returns a collection}{Make it
814 return a read-only view and provide add/remove methods.}
816 % \explanation{Replace Array with Object}{}{}
818 \explanation{Replace Subclass with Fields}{You have subclasses that vary only in
819 methods that return constant data.}{Change the methods to superclass fields and
820 eliminate the subclasses.}
822 % Simplifying Conditional Expressions
823 \explanation{Decompose Conditional}{You have a complicated conditional
824 (if-then-else) statement.}{Extract methods from the condition, then part, an
827 \explanation{Consolidate Conditional Expression}{You have a sequence of
828 conditional tests with the same result.}{Combine them into a single conditional
829 expression and extract it.}
831 \explanation{Replace Conditional with Polymorphism}{You have a conditional that
832 chooses different behavior depending on the type of an object.}{Move each leg
833 of the conditional to an overriding method in a subclass. Make the original
836 % Making Method Calls Simpler
837 \explanation{Replace Parameter with Method}{An object invokes a method, then
838 passes the result as a parameter for a method. The receiver can also invoke this
839 method.}{Remove the parameter and let the receiver invoke the method.}
841 \explanation{Introduce Parameter Object}{You have a group of parameters that
842 naturally go together.}{Replace them with an object.}
844 % Dealing with Generalization
845 \explanation{Extract Subclass}{A class has features that are used only in some
846 instances.}{Create a subclass for that subset of features.}
848 \explanation{Extract Superclass}{You have two classes with similar
849 features.}{Create a superclass and move the common features to the
852 \explanation{Collapse Hierarchy}{A superclass and subclass are not very
853 different.}{Merge them together.}
855 \explanation{Form Template Method}{You have two methods in subclasses that
856 perform similar steps in the same order, yet the steps are different.}{Get the
857 steps into methods with the same signature, so that the original methods become
858 the same. Then you can pull them up.}
861 \subsection{Functional refactorings}
863 \explanation{Substitute Algorithm}{You want to replace an algorithm with one
864 that is clearer.}{Replace the body of the method with the new algorithm.}
868 \section{The impact on software quality}
870 \subsection{What is software quality?}
871 The term \emph{software quality} has many meanings. It all depends on the
872 context we put it in. If we look at it with the eyes of a software developer, it
873 usually means that the software is easily maintainable and testable, or in other
874 words, that it is \emph{well designed}. This often correlates with the
875 management scale, where \emph{keeping the schedule} and \emph{customer
876 satisfaction} is at the center. From the customers point of view, in addition to
877 good usability, \emph{performance} and \emph{lack of bugs} is always
878 appreciated, measurements that are also shared by the software developer. (In
879 addition, such things as good documentation could be measured, but this is out
880 of the scope of this document.)
882 \subsection{The impact on performance}
884 Refactoring certainly will make software go more slowly\footnote{With todays
885 compiler optimization techniques and performance tuning of e.g. the Java
886 virtual machine, the penalties of object creation and method calls are
887 debatable.}, but it also makes the software more amenable to performance
888 tuning.~\cite[p.~69]{refactoring}
891 \noindent There is a common belief that refactoring compromises performance, due
892 to increased degree of indirection and that polymorphism is slower than
895 In a survey, Demeyer\citing{demeyer2002} disproves this view in the case of
896 polymorphism. He did an experiment on, what he calls, ``Transform Self Type
897 Checks'' where you introduce a new polymorphic method and a new class hierarchy
898 to get rid of a class' type checking of a ``type attribute``. He uses this kind
899 of transformation to represent other ways of replacing conditionals with
900 polymorphism as well. The experiment is performed on the C++ programming
901 language and with three different compilers and platforms. Demeyer concludes
902 that, with compiler optimization turned on, polymorphism beats middle to large
903 sized if-statements and does as well as case-statements. (In accordance with
904 his hypothesis, due to similarities between the way C++ handles polymorphism and
908 The interesting thing about performance is that if you analyze most programs,
909 you find that they waste most of their time in a small fraction of the
910 code.~\cite[p.~70]{refactoring}
913 \noindent So, although an increased amount of method calls could potentially
914 slow down programs, one should avoid premature optimization and sacrificing good
915 design, leaving the performance tuning until after \gloss{profiling} the
916 software and having isolated the actual problem areas.
918 \section{Composite refactorings}\label{compositeRefactorings}
919 \todo{motivation, examples, manual vs automated?, what about refactoring in a
920 very large code base?}
921 Generally, when thinking about refactoring, at the mechanical level, there are
922 essentially two kinds of refactorings. There are the \emph{primitive}
923 refactorings, and the \emph{composite} refactorings.
925 \definition{A \emph{primitive refactoring} is a refactoring that cannot be
926 expressed in terms of other refactorings.}
928 \noindent Examples are the \refa{Pull Up Field} and \refa{Pull Up
929 Method} refactorings\citing{refactoring}, that move members up in their class
932 \definition{A \emph{composite refactoring} is a refactoring that can be
933 expressed in terms of two or more other refactorings.}
935 \noindent An example of a composite refactoring is the \refa{Extract
936 Superclass} refactoring\citing{refactoring}. In its simplest form, it is composed
937 of the previously described primitive refactorings, in addition to the
938 \refa{Pull Up Constructor Body} refactoring\citing{refactoring}. It works
939 by creating an abstract superclass that the target class(es) inherits from, then
940 by applying \refa{Pull Up Field}, \refa{Pull Up Method} and
941 \refa{Pull Up Constructor Body} on the members that are to be members of
942 the new superclass. If there are multiple classes in play, their interfaces may
943 need to be united with the help of some rename refactorings, before extracting
944 the superclass. For an overview of the \refa{Extract Superclass}
945 refactoring, see \myref{fig:extractSuperclass}.
949 \includegraphics[angle=270,width=\linewidth]{extractSuperclassItalic.pdf}
950 \caption{The Extract Superclass refactoring, with united interfaces.}
951 \label{fig:extractSuperclass}
954 \section{Manual vs. automated refactorings}
955 Refactoring is something every programmer does, even if \heshe does not known
956 the term \emph{refactoring}. Every refinement of source code that does not alter
957 the program's behavior is a refactoring. For small refactorings, such as
958 \ExtractMethod, executing it manually is a manageable task, but is still prone
959 to errors. Getting it right the first time is not easy, considering the method
960 signature and all the other aspects of the refactoring that has to be in place.
962 Consider the renaming of classes, methods and fields. For complex programs these
963 refactorings are almost impossible to get right. Attacking them with textual
964 search and replace, or even regular expressions, will fall short on these tasks.
965 Then it is crucial to have proper tool support that can perform them
966 automatically. Tools that can parse source code and thus have semantic knowledge
967 about which occurrences of which names belong to what construct in the program.
968 For even trying to perform one of these complex task manually, one would have to
969 be very confident on the existing test suite \see{testing}.
971 \section{Correctness of refactorings}\label{correctness}
972 For automated refactorings to be truly useful, they must show a high degree of
973 behavior preservation. This last sentence might seem obvious, but there are
974 examples of refactorings in existing tools that break programs. In an ideal
975 world, every automated refactoring would be ``complete'', in the sense that it
976 would never break a program. In an ideal world, every program would also be free
977 from bugs. In modern IDEs the implemented automated refactorings are working for
978 \emph{most} cases, that is enough for making them useful.
980 I will now present an example of a \emph{corner case} where a program breaks
981 when a refactoring is applied. The example shows an \ExtractMethod refactoring
982 followed by a \MoveMethod refactoring that breaks a program in both the
983 \name{Eclipse} and \name{IntelliJ} IDEs\footnote{The \name{NetBeans} IDE handles this
984 particular situation without altering the program's behavior, mainly because
985 its \refa{Move Method} refactoring implementation is a bit flawed in other ways
986 \see{toolSupport}.}. The target and the destination for the composed
987 refactoring is shown in \myref{lst:correctnessExtractAndMove}. Note that the
988 method \method{m(C c)} of class \type{X} assigns to the field \var{x} of the
989 argument \var{c} that has type \type{C}.
993 \begin{minted}[linenos]{java}
994 // Refactoring target
996 public X x = new X();
1008 \begin{minted}[]{java}
1009 // Method destination
1011 public void m(C c) {
1013 // If m is called from
1014 // c, then c.x no longer
1021 \caption{The target and the destination for the composition of the Extract
1022 Method and \refa{Move Method} refactorings.}
1023 \label{lst:correctnessExtractAndMove}
1027 The refactoring sequence works by extracting line 6 through 8 from the original
1028 class \type{C} into a method \method{f} with the statements from those lines as
1029 its method body (but with the comment left out, since it will no longer hold any
1030 meaning). The method is then moved to the class \type{X}. The result is shown
1031 in \myref{lst:correctnessExtractAndMoveResult}.
1033 Before the refactoring, the methods \method{m} and \method{n} of class \type{X}
1034 are called on different object instances (see line 6 and 8 of the original class
1035 \type{C} in \cref{lst:correctnessExtractAndMove}). After the refactoring, they
1036 are called on the same object, and the statement on line
1037 3 of class \type{X} (in \cref{lst:correctnessExtractAndMoveResult}) no longer
1038 has the desired effect in our example. The method \method{f} of class \type{C}
1039 is now calling the method \method{f} of class \type{X} (see line 5 of class
1040 \type{C} in \cref{lst:correctnessExtractAndMoveResult}), and the program now
1041 behaves different than before.
1044 \begin{multicols}{2}
1045 \begin{minted}[linenos]{java}
1047 public X x = new X();
1057 \begin{minted}[linenos]{java}
1059 public void m(C c) {
1065 public void f(C c) {
1072 \caption{The result of the composed refactoring.}
1073 \label{lst:correctnessExtractAndMoveResult}
1076 The bug introduced in the previous example is of such a nature\footnote{Caused
1077 by aliasing. See \url{https://en.wikipedia.org/wiki/Aliasing_(computing)}}
1078 that it is very difficult to spot if the refactored code is not covered by
1079 tests. It does not generate compilation errors, and will thus only result in
1080 a runtime error or corrupted data, which might be hard to detect.
1082 \section{Refactoring and the importance of testing}\label{testing}
1084 If you want to refactor, the essential precondition is having solid
1085 tests.\citing{refactoring}
1088 When refactoring, there are roughly three classes of errors that can be made.
1089 The first class of errors are the ones that make the code unable to compile.
1090 These \emph{compile-time} errors are of the nicer kind. They flash up at the
1091 moment they are made (at least when using an IDE), and are usually easy to fix.
1092 The second class are the \emph{runtime} errors. Although they take a bit longer
1093 to surface, they usually manifest after some time in an illegal argument
1094 exception, null pointer exception or similar during the program execution.
1095 These kind of errors are a bit harder to handle, but at least they will show,
1096 eventually. Then there are the \emph{behavior-changing} errors. These errors are
1097 of the worst kind. They do not show up during compilation and they do not turn
1098 on a blinking red light during runtime either. The program can seem to work
1099 perfectly fine with them in play, but the business logic can be damaged in ways
1100 that will only show up over time.
1102 For discovering runtime errors and behavior changes when refactoring, it is
1103 essential to have good test coverage. Testing in this context means writing
1104 automated tests. Manual testing may have its uses, but when refactoring, it is
1105 automated unit testing that dominate. For discovering behavior changes it is
1106 especially important to have tests that cover potential problems, since these
1107 kind of errors does not reveal themselves.
1109 Unit testing is not a way to \emph{prove} that a program is correct, but it is a
1110 way to make you confident that it \emph{probably} works as desired. In the
1111 context of test driven development (commonly known as TDD), the tests are even a
1112 way to define how the program is \emph{supposed} to work. It is then, by
1113 definition, working if the tests are passing.
1115 If the test coverage for a code base is perfect, then it should, theoretically,
1116 be risk-free to perform refactorings on it. This is why automated tests and
1117 refactoring are such a great match.
1119 \subsection{Testing the code from correctness section}
1120 The worst thing that can happen when refactoring is to introduce changes to the
1121 behavior of a program, as in the example on \myref{correctness}. This example
1122 may be trivial, but the essence is clear. The only problem with the example is
1123 that it is not clear how to create automated tests for it, without changing it
1126 Unit tests, as they are known from the different \glosspl{xUnit} around, are
1127 only suitable to test the \emph{result} of isolated operations. They can not
1128 easily (if at all) observe the \emph{history} of a program.
1130 This problem is still open.
1134 Assuming a sequential (non-concurrent) program:
1136 \begin{minted}{java}
1137 tracematch (C c, X x) {
1139 call(* X.m(C)) && args(c) && cflow(within(C));
1141 call(* X.n()) && target(x) && cflow(within(C));
1143 set(C.x) && target(c) && !cflow(m);
1147 { assert x == c.x; }
1151 %\begin{minted}{java}
1152 %tracematch (X x1, X x2) {
1154 % call(* X.m(C)) && target(x1);
1156 % call(* X.n()) && target(x2);
1158 % set(C.x) && !cflow(m) && !cflow(n);
1162 % { assert x1 != x2; }
1168 \chapter{The Project}
1170 \section{Project description}
1171 The aim of this master project will be to explore the relationship between the
1172 \ExtractMethod and \MoveMethod refactorings. This will be done by composing the
1173 two into a composite refactoring. The refactoring will be called the
1174 \ExtractAndMoveMethod refactoring.
1176 The composition of the \ExtractMethod and \MoveMethod refactorings springs
1177 naturally out of the need to move procedures closer to the data they manipulate.
1178 This composed refactoring is not well described in the literature, but it is
1179 implemented in at least one tool called
1180 \name{CodeRush}\footnote{\url{https://help.devexpress.com/\#CodeRush/CustomDocument3519}},
1181 that is an extension for \name{MS Visual
1182 Studio}\footnote{\url{http://www.visualstudio.com/}}. In CodeRush it is called
1183 \refa{Extract Method to
1184 Type}\footnote{\url{https://help.devexpress.com/\#CodeRush/CustomDocument6710}},
1185 but I choose to call it \ExtractAndMoveMethod, since I feel this better
1186 communicates which primitive refactorings it is composed of.
1188 The project will consist in implementing the \ExtractAndMoveMethod refactoring,
1189 as well as executing it over a larger code base, as a case study. To be able to
1190 execute the refactoring automatically I have to make it analyze code to
1191 determine the best selections to extract into new methods.
1193 \section{The primitive refactorings}
1194 The refactorings presented here are the primitive refactorings used in this
1195 project. They are the abstract building blocks used by the \ExtractAndMoveMethod
1198 \subsection{The Extract Method refactoring}
1199 The \refa{Extract Method} refactoring is used to extract a fragment of code
1200 from its context and into a new method. A call to the new method is inlined
1201 where the fragment was before. It is used to break code into logical units, with
1202 names that explain their purpose.
1204 An example of an \ExtractMethod refactoring is shown in
1205 \myref{lst:extractMethodRefactoring}. It shows a method containing calls to the
1206 methods \method{foo} and \method{bar} of a type \type{X}. These statements are
1207 then extracted into the new method \method{fooBar}.
1210 \begin{multicols}{2}
1211 \begin{minted}[samepage]{java}
1223 \begin{minted}[samepage]{java}
1236 \caption{An example of an \ExtractMethod refactoring.}
1237 \label{lst:extractMethodRefactoring}
1240 \subsection{The Move Method refactoring}
1241 The \refa{Move Method} refactoring is used to move a method from one class to
1242 another. This can be appropriate if the method is using more features of another
1243 class than of the class which it is currently defined.
1245 \Myref{lst:moveMethodRefactoring} shows an example of this refactoring. Here a
1246 method \method{fooBar} is moved from the class \type{C} to the class \type{X}.
1249 \begin{multicols}{2}
1250 \begin{minted}[samepage]{java}
1270 \begin{minted}[samepage]{java}
1288 \caption{An example of a \MoveMethod refactoring.}
1289 \label{lst:moveMethodRefactoring}
1292 \section{The Extract and Move Method refactoring}
1293 The \ExtractAndMoveMethod refactoring is a composite refactoring composed of the
1294 primitive \ExtractMethod and \MoveMethod refactorings. The effect of this
1295 refactoring on source code is the same as when extracting a method and moving it
1296 to another class. Conseptually, this is done without an intermediate step. In
1297 practice, as we shall see later, an intermediate step may be necessary.
1299 An example of this composite refactoring is shown in
1300 \myref{lst:extractAndMoveMethodRefactoring}. The example joins the examples from
1301 \cref{lst:extractMethodRefactoring} and \cref{lst:moveMethodRefactoring}. This
1302 means that the selection consisting of the consecutive calls to the methods
1303 \method{foo} and \method{bar}, is extracted into a new method \method{fooBar}
1304 located in the class \type{X}.
1307 \begin{multicols}{2}
1308 \begin{minted}[samepage]{java}
1325 \begin{minted}[samepage]{java}
1343 \caption{An example of the \ExtractAndMoveMethod refactoring.}
1344 \label{lst:extractAndMoveMethodRefactoring}
1347 \section{Choosing the target language}
1348 Choosing which programming language the code that shall be manipulated shall be
1349 written in, is not a very difficult task. We choose to limit the possible
1350 languages to the object-oriented programming languages, since most of the
1351 terminology and literature regarding refactoring comes from the world of
1352 object-oriented programming. In addition, the language must have existing tool
1353 support for refactoring.
1355 The \name{Java} programming language\footnote{\url{https://www.java.com/}} is
1356 the dominating language when it comes to example code in the literature of
1357 refactoring, and is thus a natural choice. Java is perhaps, currently the most
1358 influential programming language in the world, with its \name{Java Virtual
1359 Machine} that runs on all of the most popular architectures and also supports
1360 dozens of other programming languages\footnote{They compile to java bytecode.},
1361 with \name{Scala}, \name{Clojure} and \name{Groovy} as the most prominent ones.
1362 Java is currently the language that every other programming language is compared
1363 against. It is also the primary programming language for the author of this
1366 \section{Choosing the tools}
1367 When choosing a tool for manipulating Java, there are certain criteria that
1368 have to be met. First of all, the tool should have some existing refactoring
1369 support that this thesis can build upon. Secondly it should provide some kind of
1370 framework for parsing and analyzing Java source code. Third, it should itself be
1371 open source. This is both because of the need to be able to browse the code for
1372 the existing refactorings that is contained in the tool, and also because open
1373 source projects hold value in them selves. Another important aspect to consider
1374 is that open source projects of a certain size, usually has large communities of
1375 people connected to them, that are committed to answering questions regarding the
1376 use and misuse of the products, that to a large degree is made by the community
1379 There is a certain class of tools that meet these criteria, namely the class of
1380 \emph{IDEs}\footnote{\emph{Integrated Development Environment}}. These are
1381 programs that is meant to support the whole production cycle of a computer
1382 program, and the most popular IDEs that support Java, generally have quite good
1383 refactoring support.
1385 The main contenders for this thesis is the \name{Eclipse IDE}, with the
1386 \name{Java development tools} (JDT), the \name{IntelliJ IDEA Community Edition}
1387 and the \name{NetBeans IDE} \see{toolSupport}. \name{Eclipse} and
1388 \name{NetBeans} are both free, open source and community driven, while the
1389 \name{IntelliJ IDEA} has an open sourced community edition that is free of
1390 charge, but also offer an \name{Ultimate Edition} with an extended set of
1391 features, at additional cost. All three IDEs supports adding plugins to extend
1392 their functionality and tools that can be used to parse and analyze Java source
1393 code. But one of the IDEs stand out as a favorite, and that is the \name{Eclipse
1394 IDE}. This is the most popular\citing{javaReport2011} among them and seems to be
1395 de facto standard IDE for Java development regardless of platform.
1398 \chapter{Refactorings in Eclipse JDT: Design, Shortcomings and Wishful
1399 Thinking}\label{ch:jdt_refactorings}
1401 This chapter will deal with some of the design behind refactoring support in
1402 \name{Eclipse}, and the JDT in specific. After which it will follow a section about
1403 shortcomings of the refactoring API in terms of composition of refactorings. The
1404 chapter will be concluded with a section telling some of the ways the
1405 implementation of refactorings in the JDT could have worked to facilitate
1406 composition of refactorings.
1409 The refactoring world of \name{Eclipse} can in general be separated into two parts: The
1410 language independent part and the part written for a specific programming
1411 language -- the language that is the target of the supported refactorings.
1412 \todo{What about the language specific part?}
1414 \subsection{The Language Toolkit}
1415 The Language Toolkit\footnote{The content of this section is a mixture of
1416 written material from
1417 \url{https://www.eclipse.org/articles/Article-LTK/ltk.html} and
1418 \url{http://www.eclipse.org/articles/article.php?file=Article-Unleashing-the-Power-of-Refactoring/index.html},
1419 the LTK source code and my own memory.}, or LTK for short, is the framework that
1420 is used to implement refactorings in \name{Eclipse}. It is language independent and
1421 provides the abstractions of a refactoring and the change it generates, in the
1422 form of the classes \typewithref{org.eclipse.ltk.core.refactoring}{Refactoring}
1423 and \typewithref{org.eclipse.ltk.core.refactoring}{Change}.
1425 There are also parts of the LTK that is concerned with user interaction, but
1426 they will not be discussed here, since they are of little value to us and our
1427 use of the framework. We are primarily interested in the parts that can be
1430 \subsubsection{The Refactoring Class}
1431 The abstract class \type{Refactoring} is the core of the LTK framework. Every
1432 refactoring that is going to be supported by the LTK have to end up creating an
1433 instance of one of its subclasses. The main responsibilities of subclasses of
1434 \type{Refactoring} is to implement template methods for condition checking
1435 (\methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{checkInitialConditions}
1437 \methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{checkFinalConditions}),
1439 \methodwithref{org.eclipse.ltk.core.refactoring.Refactoring}{createChange}
1440 method that creates and returns an instance of the \type{Change} class.
1442 If the refactoring shall support that others participate in it when it is
1443 executed, the refactoring has to be a processor-based
1444 refactoring\typeref{org.eclipse.ltk.core.refactoring.participants.ProcessorBasedRefactoring}.
1445 It then delegates to its given
1446 \typewithref{org.eclipse.ltk.core.refactoring.participants}{RefactoringProcessor}
1447 for condition checking and change creation. Participating in a refactoring can
1448 be useful in cases where the changes done to programming source code affects
1449 other related resources in the workspace. This can be names or paths in
1450 configuration files, or maybe one would like to perform additional logging of
1451 changes done in the workspace.
1453 \subsubsection{The Change Class}
1454 This class is the base class for objects that is responsible for performing the
1455 actual workspace transformations in a refactoring. The main responsibilities for
1456 its subclasses is to implement the
1457 \methodwithref{org.eclipse.ltk.core.refactoring.Change}{perform} and
1458 \methodwithref{org.eclipse.ltk.core.refactoring.Change}{isValid} methods. The
1459 \method{isValid} method verifies that the change object is valid and thus can be
1460 executed by calling its \method{perform} method. The \method{perform} method
1461 performs the desired change and returns an undo change that can be executed to
1462 reverse the effect of the transformation done by its originating change object.
1464 \subsubsection{Executing a Refactoring}\label{executing_refactoring}
1465 The life cycle of a refactoring generally follows two steps after creation:
1466 condition checking and change creation. By letting the refactoring object be
1468 \typewithref{org.eclipse.ltk.core.refactoring}{CheckConditionsOperation} that
1469 in turn is handled by a
1470 \typewithref{org.eclipse.ltk.core.refactoring}{CreateChangeOperation}, it is
1471 assured that the change creation process is managed in a proper manner.
1473 The actual execution of a change object has to follow a detailed life cycle.
1474 This life cycle is honored if the \type{CreateChangeOperation} is handled by a
1475 \typewithref{org.eclipse.ltk.core.refactoring}{PerformChangeOperation}. If also
1476 an undo manager\typeref{org.eclipse.ltk.core.refactoring.IUndoManager} is set
1477 for the \type{PerformChangeOperation}, the undo change is added into the undo
1480 \section{Shortcomings}
1481 This section is introduced naturally with a conclusion: The JDT refactoring
1482 implementation does not facilitate composition of refactorings.
1483 \todo{refine}This section will try to explain why, and also identify other
1484 shortcomings of both the usability and the readability of the JDT refactoring
1487 I will begin at the end and work my way toward the composition part of this
1490 \subsection{Absence of Generics in Eclipse Source Code}
1491 This section is not only concerning the JDT refactoring API, but also large
1492 quantities of the \name{Eclipse} source code. The code shows a striking absence of the
1493 Java language feature of generics. It is hard to read a class' interface when
1494 methods return objects or takes parameters of raw types such as \type{List} or
1495 \type{Map}. This sometimes results in having to read a lot of source code to
1496 understand what is going on, instead of relying on the available interfaces. In
1497 addition, it results in a lot of ugly code, making the use of typecasting more
1498 of a rule than an exception.
1500 \subsection{Composite Refactorings Will Not Appear as Atomic Actions}
1502 \subsubsection{Missing Flexibility from JDT Refactorings}
1503 The JDT refactorings are not made with composition of refactorings in mind. When
1504 a JDT refactoring is executed, it assumes that all conditions for it to be
1505 applied successfully can be found by reading source files that have been
1506 persisted to disk. They can only operate on the actual source material, and not
1507 (in-memory) copies thereof. This constitutes a major disadvantage when trying to
1508 compose refactorings, since if an exception occurs in the middle of a sequence
1509 of refactorings, it can leave the project in a state where the composite
1510 refactoring was only partially executed. It makes it hard to discard the changes
1511 done without monitoring and consulting the undo manager, an approach that is not
1514 \subsubsection{Broken Undo History}
1515 When designing a composed refactoring that is to be performed as a sequence of
1516 refactorings, you would like it to appear as a single change to the workspace.
1517 This implies that you would also like to be able to undo all the changes done by
1518 the refactoring in a single step. This is not the way it appears when a sequence
1519 of JDT refactorings is executed. It leaves the undo history filled up with
1520 individual undo actions corresponding to every single JDT refactoring in the
1521 sequence. This problem is not trivial to handle in \name{Eclipse}
1522 \see{hacking_undo_history}.
1524 \section{Wishful Thinking}
1528 \chapter{Composite Refactorings in Eclipse}
1530 \section{A Simple Ad Hoc Model}
1531 As pointed out in \myref{ch:jdt_refactorings}, the \name{Eclipse} JDT refactoring model
1532 is not very well suited for making composite refactorings. Therefore a simple
1533 model using changer objects (of type \type{RefaktorChanger}) is used as an
1534 abstraction layer on top of the existing \name{Eclipse} refactorings, instead of
1535 extending the \typewithref{org.eclipse.ltk.core.refactoring}{Refactoring} class.
1537 The use of an additional abstraction layer is a deliberate choice. It is due to
1538 the problem of creating a composite
1539 \typewithref{org.eclipse.ltk.core.refactoring}{Change} that can handle text
1540 changes that interfere with each other. Thus, a \type{RefaktorChanger} may, or
1541 may not, take advantage of one or more existing refactorings, but it is always
1542 intended to make a change to the workspace.
1544 \subsection{A typical \type{RefaktorChanger}}
1545 The typical refaktor changer class has two responsibilities, checking
1546 preconditions and executing the requested changes. This is not too different
1547 from the responsibilities of an LTK refactoring, with the distinction that a
1548 refaktor changer also executes the change, while an LTK refactoring is only
1549 responsible for creating the object that can later be used to do the job.
1551 Checking of preconditions is typically done by an
1552 \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{Analyzer}. If the
1553 preconditions validate, the upcoming changes are executed by an
1554 \typewithref{no.uio.ifi.refaktor.change.executors}{Executor}.
1556 \section{The Extract and Move Method Refactoring}
1557 %The Extract and Move Method Refactoring is implemented mainly using these
1560 % \item \type{ExtractAndMoveMethodChanger}
1561 % \item \type{ExtractAndMoveMethodPrefixesExtractor}
1562 % \item \type{Prefix}
1563 % \item \type{PrefixSet}
1566 \subsection{The Building Blocks}
1567 This is a composite refactoring, and hence is built up using several primitive
1568 refactorings. These basic building blocks are, as its name implies, the
1569 \ExtractMethod refactoring\citing{refactoring} and the \MoveMethod
1570 refactoring\citing{refactoring}. In \name{Eclipse}, the implementations of these
1571 refactorings are found in the classes
1572 \typewithref{org.eclipse.jdt.internal.corext.refactoring.code}{ExtractMethodRefactoring}
1574 \typewithref{org.eclipse.jdt.internal.corext.refactoring.structure}{MoveInstanceMethodProcessor},
1575 where the last class is designed to be used together with the processor-based
1576 \typewithref{org.eclipse.ltk.core.refactoring.participants}{MoveRefactoring}.
1578 \subsubsection{The ExtractMethodRefactoring Class}
1579 This class is quite simple in its use. The only parameters it requires for
1580 construction is a compilation
1581 unit\typeref{org.eclipse.jdt.core.ICompilationUnit}, the offset into the source
1582 code where the extraction shall start, and the length of the source to be
1583 extracted. Then you have to set the method name for the new method together with
1584 its visibility and some not so interesting parameters.
1586 \subsubsection{The MoveInstanceMethodProcessor Class}
1587 For the \refa{Move Method}, the processor requires a little more advanced input than
1588 the class for the \refa{Extract Method}. For construction it requires a method
1589 handle\typeref{org.eclipse.jdt.core.IMethod} for the method that is to be moved.
1590 Then the target for the move have to be supplied as the variable binding from a
1591 chosen variable declaration. In addition to this, one have to set some
1592 parameters regarding setters/getters, as well as delegation.
1594 To make a working refactoring from the processor, one have to create a
1595 \type{MoveRefactoring} with it.
1597 \subsection{The ExtractAndMoveMethodChanger}
1599 The \typewithref{no.uio.ifi.refaktor.changers}{ExtractAndMoveMethodChanger}
1600 class is a subclass of the class
1601 \typewithref{no.uio.ifi.refaktor.changers}{RefaktorChanger}. It is responsible
1602 for analyzing and finding the best target for, and also executing, a composition
1603 of the \refa{Extract Method} and \refa{Move Method} refactorings. This particular changer is
1604 the one of my changers that is closest to being a true LTK refactoring. It can
1605 be reworked to be one if the problems with overlapping changes are resolved. The
1606 changer requires a text selection and the name of the new method, or else a
1607 method name will be generated. The selection has to be of the type
1608 \typewithref{no.uio.ifi.refaktor.utils}{CompilationUnitTextSelection}. This
1609 class is a custom extension to
1610 \typewithref{org.eclipse.jface.text}{TextSelection}, that in addition to the
1611 basic offset, length and similar methods, also carry an instance of the
1612 underlying compilation unit handle for the selection.
1615 \type{ExtractAndMoveMethodAnalyzer}}\label{extractAndMoveMethodAnalyzer}
1616 The analysis and precondition checking is done by the
1617 \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{ExtractAnd\-MoveMethodAnalyzer}.
1618 First is check whether the selection is a valid selection or not, with respect
1619 to statement boundaries and that it actually contains any selections. Then it
1620 checks the legality of both extracting the selection and also moving it to
1621 another class. This checking of is performed by a range of checkers
1622 \see{checkers}. If the selection is approved as legal, it is analyzed to find
1623 the presumably best target to move the extracted method to.
1625 For finding the best suitable target the analyzer is using a
1626 \typewithref{no.uio.ifi.refaktor.analyze.collectors}{PrefixesCollector} that
1627 collects all the possible candidate targets for the refactoring. All the
1628 non-candidates is found by an
1629 \typewithref{no.uio.ifi.refaktor.analyze.collectors}{UnfixesCollector} that
1630 collects all the targets that will give some kind of error if used. (For
1631 details about the property collectors, see \myref{propertyCollectors}.) All
1632 prefixes (and unfixes) are represented by a
1633 \typewithref{no.uio.ifi.refaktor.extractors}{Prefix}, and they are collected
1634 into sets of prefixes. The safe prefixes is found by subtracting from the set of
1635 candidate prefixes the prefixes that is enclosing any of the unfixes. A prefix
1636 is enclosing an unfix if the unfix is in the set of its sub-prefixes. As an
1637 example, \texttt{``a.b''} is enclosing \texttt{``a''}, as is \texttt{``a''}. The
1638 safe prefixes is unified in a \type{PrefixSet}. If a prefix has only one
1639 occurrence, and is a simple expression, it is considered unsuitable as a move
1640 target. This occurs in statements such as \texttt{``a.foo()''}. For such
1641 statements it bares no meaning to extract and move them. It only generates an
1642 extra method and the calling of it.
1644 The most suitable target for the refactoring is found by finding the prefix with
1645 the most occurrences. If two prefixes have the same occurrence count, but they
1646 differ in length, the longest of them is chosen.
1648 \todoin{Clean up sections/subsections.}
1651 \type{ExtractAndMoveMethodExecutor}}\label{extractAndMoveMethodExecutor}
1652 If the analysis finds a possible target for the composite refactoring, it is
1654 \typewithref{no.uio.ifi.refaktor.change.executors}{ExtractAndMoveMethodExecutor}.
1655 It is composed of the two executors known as
1656 \typewithref{no.uio.ifi.refaktor.change.executors}{ExtractMethodRefactoringExecutor}
1658 \typewithref{no.uio.ifi.refaktor.change.executors}{MoveMethodRefactoringExecutor}.
1659 The \type{ExtractAndMoveMethodExecutor} is responsible for gluing the two
1660 together by feeding the \type{MoveMethod\-RefactoringExecutor} with the
1661 resources needed after executing the extract method refactoring.
1662 %\see{postExtractExecution}.
1664 \subsubsection{The \type{ExtractMethodRefactoringExecutor}}
1665 This executor is responsible for creating and executing an instance of the
1666 \type{ExtractMethodRefactoring} class. It is also responsible for collecting
1667 some post execution resources that can be used to find the method handle for the
1668 extracted method, as well as information about its parameters, including the
1669 variable they originated from.
1671 \subsubsection{The \type{MoveMethodRefactoringExecutor}}
1672 This executor is responsible for creating and executing an instance of the
1673 \type{MoveRefactoring}. The move refactoring is a processor-based refactoring,
1674 and for the \refa{Move Method} refactoring it is the \type{MoveInstanceMethodProcessor}
1677 The handle for the method to be moved is found on the basis of the information
1678 gathered after the execution of the \refa{Extract Method} refactoring. The only
1679 information the \type{ExtractMethodRefactoring} is sharing after its execution,
1680 regarding find the method handle, is the textual representation of the new
1681 method signature. Therefore it must be parsed, the strings for types of the
1682 parameters must be found and translated to a form that can be used to look up
1683 the method handle from its type handle. They have to be on the unresolved
1684 form.\todo{Elaborate?} The name for the type is found from the original
1685 selection, since an extracted method must end up in the same type as the
1688 When analyzing a selection prior to performing the \refa{Extract Method} refactoring, a
1689 target is chosen. It has to be a variable binding, so it is either a field or a
1690 local variable/parameter. If the target is a field, it can be used with the
1691 \type{MoveInstanceMethodProcessor} as it is, since the extracted method still is
1692 in its scope. But if the target is local to the originating method, the target
1693 that is to be used for the processor must be among its parameters. Thus the
1694 target must be found among the extracted method's parameters. This is done by
1695 finding the parameter information object that corresponds to the parameter that
1696 was declared on basis of the original target's variable when the method was
1697 extracted. (The extracted method must take one such parameter for each local
1698 variable that is declared outside the selection that is extracted.) To match the
1699 original target with the correct parameter information object, the key for the
1700 information object is compared to the key from the original target's binding.
1701 The source code must then be parsed to find the method declaration for the
1702 extracted method. The new target must be found by searching through the
1703 parameters of the declaration and choose the one that has the same type as the
1704 old binding from the parameter information object, as well as the same name that
1705 is provided by the parameter information object.
1709 SearchBasedExtractAndMoveMethodChanger}\label{searchBasedExtractAndMoveMethodChanger}
1711 \typewithref{no.uio.ifi.refaktor.change.changers}{SearchBasedExtractAndMoveMethodChanger}
1712 is a changer whose purpose is to automatically analyze a method, and execute the
1713 \ExtractAndMoveMethod refactoring on it if it is a suitable candidate for the
1716 First, the \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{SearchBasedExtractAndMoveMethodAnalyzer} is used
1717 to analyze the method. If the method is found to be a candidate, the result from
1718 the analysis is fed to the \type{ExtractAndMoveMethodExecutor}, whose job is to
1719 execute the refactoring \see{extractAndMoveMethodExecutor}.
1721 \subsubsection{The SearchBasedExtractAndMoveMethodAnalyzer}
1722 This analyzer is responsible for analyzing all the possible text selections of a
1723 method and then choose the best result out of the analysis results that is, by
1724 the analyzer, considered to be the potential candidates for the Extract and Move
1727 Before the analyzer is able to work with the text selections of a method, it
1728 needs to generate them. To do this, it parses the method to obtain a
1729 \type{MethodDeclaration} for it \see{astEclipse}. Then there is a statement
1730 lists creator that creates statements lists of the different groups of
1731 statements in the body of the method declaration. A text selections generator
1732 generates text selections of all the statement lists for the analyzer to work
1735 \paragraph{The statement lists creator}
1736 is responsible for generating lists of statements for all the possible levels of
1737 statements in the method. The statement lists creator is implemented as an AST
1738 visitor \see{astVisitor}. It generates lists of statements by visiting all the
1739 blocks in the method declaration and stores their statements in a collection of
1740 statement lists. In addition, it visits all of the other statements that can
1741 have a statement as a child, such as the different control structures and the
1744 The switch statement is the only kind of statement that is not straight forward
1745 to obtain the child statements from. It stores all of its children in a flat
1746 list. Its switch case statements are included in this list. This means that
1747 there are potential statement lists between all of these case statements. The
1748 list of statements from a switch statement is therefore traversed, and the
1749 statements between the case statements are grouped as separate lists.
1751 There is an example of how the statement lists creator would generate lists for
1752 a simple method in \myref{lst:statementListsExample}.
1755 \def\charwidth{5.7pt}
1756 \def\indent{4*\charwidth}
1757 \def\lineheight{\baselineskip}
1758 \def\mintedtop{\lineheight}
1760 \begin{tikzpicture}[overlay, yscale=-1]
1761 \tikzstyle{overlaybox}=[fill=lightgray,opacity=0.2]
1762 \draw[overlaybox] (0,\mintedtop+\lineheight) rectangle
1763 +(22*\charwidth,10*\lineheight);
1764 \draw[overlaybox] (\indent,\mintedtop+2*\lineheight) rectangle
1765 +(13*\charwidth,\lineheight);
1766 \draw[overlaybox] (2*\indent,\mintedtop+6*\lineheight) rectangle
1767 +(13*\charwidth,2*\lineheight);
1768 \draw[overlaybox] (2*\indent,\mintedtop+9*\lineheight) rectangle
1769 +(13*\charwidth,\lineheight);
1771 \begin{minted}{java}
1785 \caption{Example of how the statement lists creator would group a simple method
1786 into lists of statements. Each highlighted rectangle represents a list.}
1787 \label{lst:statementListsExample}
1790 \paragraph{The text selections generator} generates text selections for each
1791 list of statements from the statement lists creator. Conceptually, the generator
1792 generates a text selection for every possible ordered \todo{make clearer}
1793 combination of statements in a list. For a list of statements, the boundary
1794 statements span out a text selection. This means that there are many different
1795 lists that could span out the same selection.
1797 In practice, the text selections are calculated by only one traversal of the
1798 statement list. There is a set of generated text selections. For each statement,
1799 there is created a temporary set of selections, in addition to a text selection
1800 based on the offset and length of the statement. This text selection is added to
1801 the temporary set. Then the new selection is added with every selection from the
1802 set of generated text selections. These new selections are added to the
1803 temporary set. Then the temporary set of selections is added to the set of
1804 generated text selections. The result of adding two text selections is a new
1805 text selection spanned out by the two addends.
1808 \def\charwidth{5.7pt}
1809 \def\indent{4*\charwidth}
1810 \def\lineheight{\baselineskip}
1811 \def\mintedtop{\lineheight}
1813 \begin{tikzpicture}[overlay, yscale=-1]
1814 \tikzstyle{overlaybox}=[fill=lightgray,opacity=0.2]
1816 \draw[overlaybox] (2*\charwidth,\mintedtop) rectangle
1817 +(18*\charwidth,\lineheight);
1819 \draw[overlaybox] (2*\charwidth,\mintedtop+\lineheight) rectangle
1820 +(18*\charwidth,\lineheight);
1822 \draw[overlaybox] (2*\charwidth,\mintedtop+3*\lineheight) rectangle
1823 +(18*\charwidth,\lineheight);
1825 \draw[overlaybox] (\indent-3*\charwidth,\mintedtop) rectangle
1826 +(20*\charwidth,2*\lineheight);
1828 \draw[overlaybox] (3*\charwidth,\mintedtop+\lineheight) rectangle
1829 +(16*\charwidth,3*\lineheight);
1831 \draw[overlaybox] (\indent,\mintedtop) rectangle
1832 +(14*\charwidth,4*\lineheight);
1834 \begin{minted}{java}
1840 \caption{Example of how the text selections generator would generate text
1841 selections based on a lists of statements. Each highlighted rectangle
1842 represents a text selection.}
1843 \label{lst:textSelectionsExample}
1845 \todoin{fix \myref{lst:textSelectionsExample}? Text only? All
1846 sub-sequences\ldots}
1848 \paragraph{Finding the candidate} for the refactoring is done by analyzing all
1849 the generated text selection with the \type{ExtractAndMoveMethodAnalyzer}
1850 \see{extractAndMoveMethodAnalyzer}. If the analyzer generates a useful result,
1851 an \type{ExtractAndMoveMethodCandidate} is created from it, that is kept in a
1852 list of potential candidates. If no candidates are found, the
1853 \type{NoTargetFoundException} is thrown.
1855 Since only one of the candidates can be chosen, the analyzer must sort out which
1856 candidate to choose. The sorting is done by the static \method{sort} method of
1857 \type{Collections}. The comparison in this sorting is done by an
1858 \type{ExtractAndMoveMethodCandidateComparator}.
1859 \todoin{Write about the
1860 ExtractAndMoveMethodCandidateComparator/FavorNoUnfixesCandidateComparator}
1862 \paragraph{The complexity} of how many text selections that needs to be analyzed
1863 for a total of $n$ statements is bounded by $O(n^2)$.
1866 The number of text selections that need to be analyzed for each list of
1867 statements of length $n$, is exactly
1870 \sum_{i=1}^{n} i = \frac{n(n+1)}{2}
1871 \label{eq:complexityStatementList}
1873 \label{thm:numberOfTextSelection}
1877 For $n=1$ this is trivial: $\frac{1(1+1)}{2} = \frac{2}{2} = 1$. One statement
1878 equals one selection.
1880 For $n=2$, you get one text selection for the first statement. For the second,
1881 you get one selection for the statement itself, and one selection for the two
1882 of them combined. This equals three selections. $\frac{2(2+1)}{2} =
1885 For $n=3$, you get 3 selections for the two first statements, as in the case
1886 where $n=2$. In addition you get one selection for the third statement itself,
1887 and two more statements for the combinations of it with the two previous
1888 statements. This equals six selections. $\frac{3(3+1)}{2} = \frac{12}{2} = 6$.
1890 Assume that for $n=k$ there exists $\frac{k(k+1)}{2}$ text selections. Then we
1891 want to add selections for another statement, following the previous $k$
1892 statements. So, for $n=k+1$, we get one additional selection for the statement
1893 itself. Then we get one selection for each pair of the new selection and the
1894 previous $k$ statements. So the total number of selections will be the number
1895 of already generated selections, plus $k$ for every pair, plus one for the
1896 statement itself: $\frac{k(k+1)}{2} + k +
1897 1 = \frac{k(k+1)+2k+2}{2} = \frac{k(k+1)+2(k+1)}{2} = \frac{(k+1)(k+2)}{2} =
1898 \frac{(k+1)((k+1)+1)}{2} = \sum_{i=1}^{k+1} i$
1902 The number of text selections for a body of statements is maximized if all the
1903 statements are at the same level.
1904 \label{thm:textSelectionsMaximized}
1908 Assume we have a body of, in total, $k$ statements. Let
1909 $l,\cdots,m,(k-l-\cdots-m)$ be the lengths of the lists of statements in the
1910 body, with $l+\cdots+m<k \Rightarrow l,\cdots,m<k$.
1912 Then, the number of text selections that are generated for the $k$ statements
1918 \frac{(k-l-\cdots-m)((k-l-\cdots-m)+ 1)}{2} + \frac{l(l+1)}{2} + \cdots +
1919 \frac{m(m+1)}{2} = \\
1920 \frac{k^2 - 2kl - \cdots - 2km + l^2 + \cdots + m^2 + k - l - \cdots - m}{2}
1921 + \frac{l^2+l}{2} + \cdots + \frac{m^2+m}{2} = \\
1922 \frac{k^2 + k + 2l^2 - 2kl + \cdots + 2m^2 - 2km}{2}
1926 It then remains to show that this inequality holds:
1929 \frac{k^2 + k + 2l^2 - 2kl + \cdots + 2m^2 - 2km}{2} < \frac{k(k+1)}{2} =
1933 By multiplication by $2$ on both sides, and by removing the equal parts, we get
1936 2l^2 - 2kl + \cdots + 2m^2 - 2km < 0
1939 Since $l,\cdots,m<k$, we have that $\forall i \in \{l,\cdots,m\} : 2ki > 2i^2$,
1940 so all the pairs of parts on the form $2i^2-2ki$ are negative. In sum, the
1945 Therefore, the complexity for the number of selections that needs to be analyzed
1946 for a body of $n$ statements is $O\bigl(\frac{n(n+1)}{2}\bigr) = O(n^2)$.
1950 \subsection{Finding the IMethod}\label{postExtractExecution}
1951 \todoin{Rename section. Write??}
1955 \subsection{The Prefix Class}
1956 This class exists mainly for holding data about a prefix, such as the expression
1957 that the prefix represents and the occurrence count of the prefix within a
1958 selection. In addition to this, it has some functionality such as calculating
1959 its sub-prefixes and intersecting it with another prefix. The definition of the
1960 intersection between two prefixes is a prefix representing the longest common
1961 expression between the two.
1963 \subsection{The PrefixSet Class}
1964 A prefix set holds elements of type \type{Prefix}. It is implemented with the
1965 help of a \typewithref{java.util}{HashMap} and contains some typical set
1966 operations, but it does not implement the \typewithref{java.util}{Set}
1967 interface, since the prefix set does not need all of the functionality a
1968 \type{Set} requires to be implemented. In addition It needs some other
1969 functionality not found in the \type{Set} interface. So due to the relatively
1970 limited use of prefix sets, and that it almost always needs to be referenced as
1971 such, and not a \type{Set<Prefix>}, it remains as an ad hoc solution to a
1974 There are two ways adding prefixes to a \type{PrefixSet}. The first is through
1975 its \method{add} method. This works like one would expect from a set. It adds
1976 the prefix to the set if it does not already contain the prefix. The other way
1977 is to \emph{register} the prefix with the set. When registering a prefix, if the
1978 set does not contain the prefix, it is just added. If the set contains the
1979 prefix, its count gets incremented. This is how the occurrence count is handled.
1981 The prefix set also computes the set of prefixes that is not enclosing any
1982 prefixes of another set. This is kind of a set difference operation only for
1985 \subsection{Hacking the Refactoring Undo
1986 History}\label{hacking_undo_history}
1987 \todoin{Where to put this section?}
1989 As an attempt to make multiple subsequent changes to the workspace appear as a
1990 single action (i.e. make the undo changes appear as such), I tried to alter
1991 the undo changes\typeref{org.eclipse.ltk.core.refactoring.Change} in the history
1992 of the refactorings.
1994 My first impulse was to remove the, in this case, last two undo changes from the
1995 undo manager\typeref{org.eclipse.ltk.core.refactoring.IUndoManager} for the
1996 \name{Eclipse} refactorings, and then add them to a composite
1997 change\typeref{org.eclipse.ltk.core.refactoring.CompositeChange} that could be
1998 added back to the manager. The interface of the undo manager does not offer a
1999 way to remove/pop the last added undo change, so a possible solution could be to
2000 decorate\citing{designPatterns} the undo manager, to intercept and collect the
2001 undo changes before delegating to the \method{addUndo}
2002 method\methodref{org.eclipse.ltk.core.refactoring.IUndoManager}{addUndo} of the
2003 manager. Instead of giving it the intended undo change, a null change could be
2004 given to prevent it from making any changes if run. Then one could let the
2005 collected undo changes form a composite change to be added to the manager.
2007 There is a technical challenge with this approach, and it relates to the undo
2008 manager, and the concrete implementation
2009 UndoManager2\typeref{org.eclipse.ltk.internal.core.refactoring.UndoManager2}.
2010 This implementation is designed in a way that it is not possible to just add an
2011 undo change, you have to do it in the context of an active
2012 operation\typeref{org.eclipse.core.commands.operations.TriggeredOperations}.
2013 One could imagine that it might be possible to trick the undo manager into
2014 believing that you are doing a real change, by executing a refactoring that is
2015 returning a kind of null change that is returning our composite change of undo
2016 refactorings when it is performed.
2018 Apart from the technical problems with this solution, there is a functional
2019 problem: If it all had worked out as planned, this would leave the undo history
2020 in a dirty state, with multiple empty undo operations corresponding to each of
2021 the sequentially executed refactoring operations, followed by a composite undo
2022 change corresponding to an empty change of the workspace for rounding of our
2023 composite refactoring. The solution to this particular problem could be to
2024 intercept the registration of the intermediate changes in the undo manager, and
2025 only register the last empty change.
2027 Unfortunately, not everything works as desired with this solution. The grouping
2028 of the undo changes into the composite change does not make the undo operation
2029 appear as an atomic operation. The undo operation is still split up into
2030 separate undo actions, corresponding to the change done by its originating
2031 refactoring. And in addition, the undo actions has to be performed separate in
2032 all the editors involved. This makes it no solution at all, but a step toward
2035 There might be a solution to this problem, but it remains to be found. The
2036 design of the refactoring undo management is partly to be blamed for this, as it
2037 it is to complex to be easily manipulated.
2042 \chapter{Analyzing Source Code in Eclipse}
2044 \section{The Java model}\label{javaModel}
2045 The Java model of \name{Eclipse} is its internal representation of a Java project. It
2046 is light-weight, and has only limited possibilities for manipulating source
2047 code. It is typically used as a basis for the Package Explorer in \name{Eclipse}.
2049 The elements of the Java model is only handles to the underlying elements. This
2050 means that the underlying element of a handle does not need to actually exist.
2051 Hence the user of a handle must always check that it exist by calling the
2052 \method{exists} method of the handle.
2054 The handles with descriptions is listed in \myref{tab:javaModel}.
2059 \newcolumntype{L}[1]{>{\hsize=#1\hsize\raggedright\arraybackslash}X}%
2060 % sum must equal number of columns (3)
2061 \begin{tabularx}{\textwidth}{| L{0.7} | L{1.1} | L{1.2} |}
2063 \textbf{Project Element} & \textbf{Java Model element} &
2064 \textbf{Description} \\
2066 Java project & \type{IJavaProject} & The Java project which contains all other objects. \\
2068 Source folder /\linebreak[2] binary folder /\linebreak[3] external library &
2069 \type{IPackageFragmentRoot} & Hold source or binary files, can be a folder
2070 or a library (zip / jar file). \\
2072 Each package & \type{IPackageFragment} & Each package is below the
2073 \type{IPackageFragmentRoot}, sub-packages are not leaves of the package,
2074 they are listed directed under \type{IPackageFragmentRoot}. \\
2076 Java Source file & \type{ICompilationUnit} & The Source file is always below
2077 the package node. \\
2079 Types /\linebreak[2] Fields /\linebreak[3] Methods & \type{IType} /
2081 \type{IField} /\linebreak[3] \type{IMethod} & Types, fields and methods. \\
2084 \caption{The elements of the Java Model. {\footnotesize Taken from
2085 \url{http://www.vogella.com/tutorials/EclipseJDT/article.html}}}
2086 \label{tab:javaModel}
2089 The hierarchy of the Java Model is shown in \myref{fig:javaModel}.
2093 \begin{tikzpicture}[%
2094 grow via three points={one child at (0,-0.7) and
2095 two children at (0,-0.7) and (0,-1.4)},
2096 edge from parent path={(\tikzparentnode.south west)+(0.5,0) |-
2097 (\tikzchildnode.west)}]
2098 \tikzstyle{every node}=[draw=black,thick,anchor=west]
2099 \tikzstyle{selected}=[draw=red,fill=red!30]
2100 \tikzstyle{optional}=[dashed,fill=gray!50]
2101 \node {\type{IJavaProject}}
2102 child { node {\type{IPackageFragmentRoot}}
2103 child { node {\type{IPackageFragment}}
2104 child { node {\type{ICompilationUnit}}
2105 child { node {\type{IType}}
2106 child { node {\type{\{ IType \}*}}
2107 child { node {\type{\ldots}}}
2110 child { node {\type{\{ IField \}*}}}
2111 child { node {\type{IMethod}}
2112 child { node {\type{\{ IType \}*}}
2113 child { node {\type{\ldots}}}
2118 child { node {\type{\{ IMethod \}*}}}
2127 child { node {\type{\{ IType \}*}}}
2138 child { node {\type{\{ ICompilationUnit \}*}}}
2151 child { node {\type{\{ IPackageFragment \}*}}}
2166 child { node {\type{\{ IPackageFragmentRoot \}*}}}
2169 \caption{The Java model of \name{Eclipse}. ``\type{\{ SomeElement \}*}'' means
2170 \type{SomeElement} zero or more times. For recursive structures,
2171 ``\type{\ldots}'' is used.}
2172 \label{fig:javaModel}
2175 \section{The Abstract Syntax Tree}
2176 \name{Eclipse} is following the common paradigm of using an abstract syntax tree for
2177 source code analysis and manipulation.
2179 When parsing program source code into something that can be used as a foundation
2180 for analysis, the start of the process follows the same steps as in a compiler.
2181 This is all natural, because the way a compiler analyzes code is no different
2182 from how source manipulation programs would do it, except for some properties of
2183 code that is analyzed in the parser, and that they may be differing in what
2184 kinds of properties they analyze. Thus the process of translation source code
2185 into a structure that is suitable for analyzing, can be seen as a kind of
2186 interrupted compilation process \see{fig:interruptedCompilationProcess}.
2191 base/.style={anchor=north, align=center, rectangle, minimum height=1.4cm},
2192 basewithshadow/.style={base, drop shadow, fill=white},
2193 outlined/.style={basewithshadow, draw, rounded corners, minimum
2195 primary/.style={outlined, font=\bfseries},
2196 dashedbox/.style={outlined, dashed},
2197 arrowpath/.style={black, align=center, font=\small},
2198 processarrow/.style={arrowpath, ->, >=angle 90, shorten >=1pt},
2200 \begin{tikzpicture}[node distance=1.3cm and 3cm, scale=1, every
2201 node/.style={transform shape}]
2202 \node[base](AuxNode1){\small source code};
2203 \node[primary, right=of AuxNode1, xshift=-2.5cm](Scanner){Scanner};
2204 \node[primary, right=of Scanner, xshift=0.5cm](Parser){Parser};
2205 \node[dashedbox, below=of Parser](SemanticAnalyzer){Semantic\\Analyzer};
2206 \node[dashedbox, left=of SemanticAnalyzer](SourceCodeOptimizer){Source
2208 \node[dashedbox, below=of SourceCodeOptimizer
2209 ](CodeGenerator){Code\\Generator};
2210 \node[dashedbox, right=of CodeGenerator](TargetCodeOptimizer){Target
2212 \node[base, right=of TargetCodeOptimizer](AuxNode2){};
2214 \draw[processarrow](AuxNode1) -- (Scanner);
2216 \path[arrowpath] (Scanner) -- node [sloped](tokens){tokens}(Parser);
2217 \draw[processarrow](Scanner) -- (tokens) -- (Parser);
2219 \path[arrowpath] (Parser) -- node (syntax){syntax
2220 tree}(SemanticAnalyzer);
2221 \draw[processarrow](Parser) -- (syntax) -- (SemanticAnalyzer);
2223 \path[arrowpath] (SemanticAnalyzer) -- node
2224 [sloped](annotated){annotated\\tree}(SourceCodeOptimizer);
2225 \draw[processarrow, dashed](SemanticAnalyzer) -- (annotated) --
2226 (SourceCodeOptimizer);
2228 \path[arrowpath] (SourceCodeOptimizer) -- node
2229 (intermediate){intermediate code}(CodeGenerator);
2230 \draw[processarrow, dashed](SourceCodeOptimizer) -- (intermediate) --
2233 \path[arrowpath] (CodeGenerator) -- node [sloped](target1){target
2234 code}(TargetCodeOptimizer);
2235 \draw[processarrow, dashed](CodeGenerator) -- (target1) --
2236 (TargetCodeOptimizer);
2238 \path[arrowpath](TargetCodeOptimizer) -- node [sloped](target2){target
2240 \draw[processarrow, dashed](TargetCodeOptimizer) -- (target2) (AuxNode2);
2242 \caption{Interrupted compilation process. {\footnotesize (Full compilation
2243 process borrowed from \emph{Compiler construction: principles and practice}
2244 by Kenneth C. Louden\citing{louden1997}.)}}
2245 \label{fig:interruptedCompilationProcess}
2248 The process starts with a \emph{scanner}, or lexer. The job of the scanner is to
2249 read the source code and divide it into tokens for the parser. Therefore, it is
2250 also sometimes called a tokenizer. A token is a logical unit, defined in the
2251 language specification, consisting of one or more consecutive characters. In
2252 the Java language the tokens can for instance be the \var{this} keyword, a curly
2253 bracket \var{\{} or a \var{nameToken}. It is recognized by the scanner on the
2254 basis of something equivalent of a regular expression. This part of the process
2255 is often implemented with the use of a finite automata. In fact, it is common to
2256 specify the tokens in regular expressions, that in turn is translated into a
2257 finite automata lexer. This process can be automated.
2259 The program component used to translate a stream of tokens into something
2260 meaningful, is called a parser. A parser is fed tokens from the scanner and
2261 performs an analysis of the structure of a program. It verifies that the syntax
2262 is correct according to the grammar rules of a language, that is usually
2263 specified in a context-free grammar, and often in a variant of the
2265 Form}\footnote{\url{https://en.wikipedia.org/wiki/Backus-Naur\_Form}}. The
2266 result coming from the parser is in the form of an \emph{Abstract Syntax Tree},
2267 AST for short. It is called \emph{abstract}, because the structure does not
2268 contain all of the tokens produced by the scanner. It only contain logical
2269 constructs, and because it forms a tree, all kinds of parentheses and brackets
2270 are implicit in the structure. It is this AST that is used when performing the
2271 semantic analysis of the code.
2273 As an example we can think of the expression \code{(5 + 7) * 2}. The root of
2274 this tree would in \name{Eclipse} be an \type{InfixExpression} with the operator
2275 \var{TIMES}, and a left operand that is also an \type{InfixExpression} with the
2276 operator \var{PLUS}. The left operand \type{InfixExpression}, has in turn a left
2277 operand of type \type{NumberLiteral} with the value \var{``5''} and a right
2278 operand \type{NumberLiteral} with the value \var{``7''}. The root will have a
2279 right operand of type \type{NumberLiteral} and value \var{``2''}. The AST for
2280 this expression is illustrated in \myref{fig:astInfixExpression}.
2282 Contrary to the Java Model, an abstract syntax tree is a heavy-weight
2283 representation of source code. It contains information about properties like
2284 type bindings for variables and variable bindings for names.
2289 \begin{tikzpicture}[scale=0.8]
2290 \tikzset{level distance=40pt}
2291 \tikzset{sibling distance=5pt}
2292 \tikzstyle{thescale}=[scale=0.8]
2293 \tikzset{every tree node/.style={align=center}}
2294 \tikzset{edge from parent/.append style={thick}}
2295 \tikzstyle{inode}=[rectangle,rounded corners,draw,fill=lightgray,drop
2296 shadow,align=center]
2297 \tikzset{every internal node/.style={inode}}
2298 \tikzset{every leaf node/.style={draw=none,fill=none}}
2300 \Tree [.\type{InfixExpression} [.\type{InfixExpression}
2301 [.\type{NumberLiteral} \var{``5''} ] [.\type{Operator} \var{PLUS} ]
2302 [.\type{NumberLiteral} \var{``7''} ] ]
2303 [.\type{Operator} \var{TIMES} ]
2304 [.\type{NumberLiteral} \var{``2''} ]
2307 \caption{The abstract syntax tree for the expression \code{(5 + 7) * 2}.}
2308 \label{fig:astInfixExpression}
2311 \subsection{The AST in Eclipse}\label{astEclipse}
2312 In \name{Eclipse}, every node in the AST is a child of the abstract superclass
2313 \typewithref{org.eclipse.jdt.core.dom}{ASTNode}. Every \type{ASTNode}, among a
2314 lot of other things, provides information about its position and length in the
2315 source code, as well as a reference to its parent and to the root of the tree.
2317 The root of the AST is always of type \type{CompilationUnit}. It is not the same
2318 as an instance of an \type{ICompilationUnit}, which is the compilation unit
2319 handle of the Java model. The children of a \type{CompilationUnit} is an
2320 optional \type{PackageDeclaration}, zero or more nodes of type
2321 \type{ImportDecaration} and all its top-level type declarations that has node
2322 types \type{AbstractTypeDeclaration}.
2324 An \type{AbstractType\-Declaration} can be one of the types
2325 \type{AnnotationType\-Declaration}, \type{Enum\-Declaration} or
2326 \type{Type\-Declaration}. The children of an \type{AbstractType\-Declaration}
2327 must be a subtype of a \type{BodyDeclaration}. These subtypes are:
2328 \type{AnnotationTypeMember\-Declaration}, \type{EnumConstant\-Declaration},
2329 \type{Field\-Declaration}, \type{Initializer} and \type{Method\-Declaration}.
2331 Of the body declarations, the \type{Method\-Declaration} is the most interesting
2332 one. Its children include lists of modifiers, type parameters, parameters and
2333 exceptions. It has a return type node and a body node. The body, if present, is
2334 of type \type{Block}. A \type{Block} is itself a \type{Statement}, and its
2335 children is a list of \type{Statement} nodes.
2337 There are too many types of the abstract type \type{Statement} to list up, but
2338 there exists a subtype of \type{Statement} for every statement type of Java, as
2339 one would expect. This also applies to the abstract type \type{Expression}.
2340 However, the expression \type{Name} is a little special, since it is both used
2341 as an operand in compound expressions, as well as for names in type declarations
2344 There is an overview of some of the structure of an \name{Eclipse} AST in
2345 \myref{fig:astEclipse}.
2349 \begin{tikzpicture}[scale=0.8]
2350 \tikzset{level distance=50pt}
2351 \tikzset{sibling distance=5pt}
2352 \tikzstyle{thescale}=[scale=0.8]
2353 \tikzset{every tree node/.style={align=center}}
2354 \tikzset{edge from parent/.append style={thick}}
2355 \tikzstyle{inode}=[rectangle,rounded corners,draw,fill=lightgray,drop
2356 shadow,align=center]
2357 \tikzset{every internal node/.style={inode}}
2358 \tikzset{every leaf node/.style={draw=none,fill=none}}
2360 \Tree [.\type{CompilationUnit} [.\type{[ PackageDeclaration ]} [.\type{Name} ]
2361 [.\type{\{ Annotation \}*} ] ]
2362 [.\type{\{ ImportDeclaration \}*} [.\type{Name} ] ]
2363 [.\type{\{ AbstractTypeDeclaration \}+} [.\node(site){\type{\{
2364 BodyDeclaration \}*}}; ] [.\type{SimpleName} ] ]
2366 \begin{scope}[shift={(0.5,-6)}]
2367 \node[inode,thescale](root){\type{MethodDeclaration}};
2368 \node[inode,thescale](modifiers) at (4.5,-5){\type{\{ IExtendedModifier \}*}
2369 \\ {\footnotesize (Of type \type{Modifier} or \type{Annotation})}};
2370 \node[inode,thescale](typeParameters) at (-6,-3.5){\type{\{ TypeParameter
2372 \node[inode,thescale](parameters) at (-5,-5){\type{\{
2373 SingleVariableDeclaration \}*} \\ {\footnotesize (Parameters)}};
2374 \node[inode,thescale](exceptions) at (5,-3){\type{\{ Name \}*} \\
2375 {\footnotesize (Exceptions)}};
2376 \node[inode,thescale](return) at (-6.5,-2){\type{Type} \\ {\footnotesize
2378 \begin{scope}[shift={(0,-5)}]
2379 \Tree [.\node(body){\type{[ Block ]} \\ {\footnotesize (Body)}};
2380 [.\type{\{ Statement \}*} [.\type{\{ Expression \}*} ]
2381 [.\type{\{ Statement \}*} [.\type{\ldots} ]]
2386 \draw[->,>=triangle 90,shorten >=1pt](root.east)..controls +(east:2) and
2387 +(south:1)..(site.south);
2389 \draw (root.south) -- (modifiers);
2390 \draw (root.south) -- (typeParameters);
2391 \draw (root.south) -- ($ (parameters.north) + (2,0) $);
2392 \draw (root.south) -- (exceptions);
2393 \draw (root.south) -- (return);
2394 \draw (root.south) -- (body);
2397 \caption{The format of the abstract syntax tree in \name{Eclipse}.}
2398 \label{fig:astEclipse}
2400 \todoin{Add more to the AST format tree? \myref{fig:astEclipse}}
2402 \section{The ASTVisitor}\label{astVisitor}
2403 So far, the only thing that has been addressed is how the data that is going to
2404 be the basis for our analysis is structured. Another aspect of it is how we are
2405 going to traverse the AST to gather the information we need, so we can conclude
2406 about the properties we are analysing. It is of course possible to start at the
2407 top of the tree, and manually search through its nodes for the ones we are
2408 looking for, but that is a bit inconvenient. To be able to efficiently utilize
2409 such an approach, we would need to make our own framework for traversing the
2410 tree and visiting only the types of nodes we are after. Luckily, this
2411 functionality is already provided in \name{Eclipse}, by its
2412 \typewithref{org.eclipse.jdt.core.dom}{ASTVisitor}.
2414 The \name{Eclipse} AST, together with its \type{ASTVisitor}, follows the
2415 \pattern{Visitor} pattern\citing{designPatterns}. The intent of this design
2416 pattern is to facilitate extending the functionality of classes without touching
2417 the classes themselves.
2419 Let us say that there is a class hierarchy of elements. These elements all have
2420 a method \method{accept(Visitor visitor)}. In its simplest form, the
2421 \method{accept} method just calls the \method{visit} method of the visitor with
2422 itself as an argument, like this: \code{visitor.visit(this)}. For the visitors
2423 to be able to extend the functionality of all the classes in the elements
2424 hierarchy, each \type{Visitor} must have one visit method for each concrete
2425 class in the hierarchy. Say the hierarchy consists of the concrete classes
2426 \type{ConcreteElementA} and \type{ConcreteElementB}. Then each visitor must have
2427 the (possibly empty) methods \method{visit(ConcreteElementA element)} and
2428 \method{visit(ConcreteElementB element)}. This scenario is depicted in
2429 \myref{fig:visitorPattern}.
2433 \tikzstyle{abstract}=[rectangle, draw=black, fill=white, drop shadow, text
2434 centered, anchor=north, text=black, text width=6cm, every one node
2435 part/.style={align=center, font=\bfseries\itshape}]
2436 \tikzstyle{concrete}=[rectangle, draw=black, fill=white, drop shadow, text
2437 centered, anchor=north, text=black, text width=6cm]
2438 \tikzstyle{inheritarrow}=[->, >=open triangle 90, thick]
2439 \tikzstyle{commentarrow}=[->, >=angle 90, dashed]
2440 \tikzstyle{line}=[-, thick]
2441 \tikzset{every one node part/.style={align=center, font=\bfseries}}
2442 \tikzset{every second node part/.style={align=center, font=\ttfamily}}
2444 \begin{tikzpicture}[node distance=1cm, scale=0.8, every node/.style={transform
2446 \node (Element) [abstract, rectangle split, rectangle split parts=2]
2448 \nodepart{one}{Element}
2449 \nodepart{second}{+accept(visitor: Visitor)}
2451 \node (AuxNode01) [text width=0, minimum height=2cm, below=of Element] {};
2452 \node (ConcreteElementA) [concrete, rectangle split, rectangle split
2453 parts=2, left=of AuxNode01]
2455 \nodepart{one}{ConcreteElementA}
2456 \nodepart{second}{+accept(visitor: Visitor)}
2458 \node (ConcreteElementB) [concrete, rectangle split, rectangle split
2459 parts=2, right=of AuxNode01]
2461 \nodepart{one}{ConcreteElementB}
2462 \nodepart{second}{+accept(visitor: Visitor)}
2465 \node[comment, below=of ConcreteElementA] (CommentA) {visitor.visit(this)};
2467 \node[comment, below=of ConcreteElementB] (CommentB) {visitor.visit(this)};
2469 \node (AuxNodeX) [text width=0, minimum height=1cm, below=of AuxNode01] {};
2471 \node (Visitor) [abstract, rectangle split, rectangle split parts=2,
2474 \nodepart{one}{Visitor}
2475 \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
2477 \node (AuxNode02) [text width=0, minimum height=2cm, below=of Visitor] {};
2478 \node (ConcreteVisitor1) [concrete, rectangle split, rectangle split
2479 parts=2, left=of AuxNode02]
2481 \nodepart{one}{ConcreteVisitor1}
2482 \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
2484 \node (ConcreteVisitor2) [concrete, rectangle split, rectangle split
2485 parts=2, right=of AuxNode02]
2487 \nodepart{one}{ConcreteVisitor2}
2488 \nodepart{second}{+visit(ConcreteElementA)\\+visit(ConcreteElementB)}
2492 \draw[inheritarrow] (ConcreteElementA.north) -- ++(0,0.7) -|
2494 \draw[line] (ConcreteElementA.north) -- ++(0,0.7) -|
2495 (ConcreteElementB.north);
2497 \draw[inheritarrow] (ConcreteVisitor1.north) -- ++(0,0.7) -|
2499 \draw[line] (ConcreteVisitor1.north) -- ++(0,0.7) -|
2500 (ConcreteVisitor2.north);
2502 \draw[commentarrow] (CommentA.north) -- (ConcreteElementA.south);
2503 \draw[commentarrow] (CommentB.north) -- (ConcreteElementB.south);
2507 \caption{The Visitor Pattern.}
2508 \label{fig:visitorPattern}
2511 The use of the visitor pattern can be appropriate when the hierarchy of elements
2512 is mostly stable, but the family of operations over its elements is constantly
2513 growing. This is clearly the case for the \name{Eclipse} AST, since the hierarchy of
2514 type \type{ASTNode} is very stable, but the functionality of its elements is
2515 extended every time someone needs to operate on the AST. Another aspect of the
2516 \name{Eclipse} implementation is that it is a public API, and the visitor pattern is an
2517 easy way to provide access to the nodes in the tree.
2519 The version of the visitor pattern implemented for the AST nodes in \name{Eclipse} also
2520 provides an elegant way to traverse the tree. It does so by following the
2521 convention that every node in the tree first let the visitor visit itself,
2522 before it also makes all its children accept the visitor. The children are only
2523 visited if the visit method of their parent returns \var{true}. This pattern
2524 then makes for a prefix traversal of the AST. If postfix traversal is desired,
2525 the visitors also has \method{endVisit} methods for each node type, that is
2526 called after the \method{visit} method for a node. In addition to these visit
2527 methods, there are also the methods \method{preVisit(ASTNode)},
2528 \method{postVisit(ASTNode)} and \method{preVisit2(ASTNode)}. The
2529 \method{preVisit} method is called before the type-specific \method{visit}
2530 method. The \method{postVisit} method is called after the type-specific
2531 \method{endVisit}. The type specific \method{visit} is only called if
2532 \method{preVisit2} returns \var{true}. Overriding the \method{preVisit2} is also
2533 altering the behavior of \method{preVisit}, since the default implementation is
2534 responsible for calling it.
2536 An example of a trivial \type{ASTVisitor} is shown in
2537 \myref{lst:astVisitorExample}.
2540 \begin{minted}{java}
2541 public class CollectNamesVisitor extends ASTVisitor {
2542 Collection<Name> names = new LinkedList<Name>();
2545 public boolean visit(QualifiedName node) {
2551 public boolean visit(SimpleName node) {
2557 \caption{An \type{ASTVisitor} that visits all the names in a subtree and adds
2558 them to a collection, except those names that are children of any
2559 \type{QualifiedName}.}
2560 \label{lst:astVisitorExample}
2563 \section{Property collectors}\label{propertyCollectors}
2564 The prefixes and unfixes are found by property
2565 collectors\typeref{no.uio.ifi.refaktor.extractors.collectors.PropertyCollector}.
2566 A property collector is of the \type{ASTVisitor} type, and thus visits nodes of
2567 type \type{ASTNode} of the abstract syntax tree \see{astVisitor}.
2569 \subsection{The PrefixesCollector}
2570 The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{PrefixesCollector}
2571 finds prefixes that makes up the basis for calculating move targets for the
2572 \refa{Extract and Move Method} refactoring. It visits expression
2573 statements\typeref{org.eclipse.jdt.core.dom.ExpressionStatement} and creates
2574 prefixes from its expressions in the case of method invocations. The prefixes
2575 found is registered with a prefix set, together with all its sub-prefixes.
2577 \subsection{The UnfixesCollector}\label{unfixes}
2578 The \typewithref{no.uio.ifi.refaktor.extractors.collectors}{UnfixesCollector}
2579 finds unfixes within a selection. That is prefixes that cannot be used as a
2580 basis for finding a move target in a refactoring.
2582 An unfix can be a name that is assigned to within a selection. The reason that
2583 this cannot be allowed, is that the result would be an assignment to the
2584 \type{this} keyword, which is not valid in Java \see{eclipse_bug_420726}.
2586 Prefixes that originates from variable declarations within the same selection
2587 are also considered unfixes. This is because when a method is moved, it needs to
2588 be called through a variable. If this variable is also within the method that is
2589 to be moved, this obviously cannot be done.
2591 Also considered as unfixes are variable references that are of types that is not
2592 suitable for moving a methods to. This can be either because it is not
2593 physically possible to move the method to the desired class or that it will
2594 cause compilation errors by doing so.
2596 If the type binding for a name is not resolved it is considered and unfix. The
2597 same applies to types that is only found in compiled code, so they have no
2598 underlying source that is accessible to us. (E.g. the \type{java.lang.String}
2601 Interfaces types are not suitable as targets. This is simply because interfaces
2602 in Java cannot contain methods with bodies. (This thesis does not deal with
2603 features of Java versions later than Java 7. Java 8 has interfaces with default
2604 implementations of methods.) Neither are local types allowed. This accounts for
2605 both local and anonymous classes. Anonymous classes are effectively the same as
2606 interface types with respect to unfixes. Local classes could in theory be used
2607 as targets, but this is not possible due to limitations of the implementation of
2608 the \refa{Extract and Move Method} refactoring. The problem is that the refactoring is
2609 done in two steps, so the intermediate state between the two refactorings would
2610 not be legal Java code. In the case of local classes, the problem is that, in
2611 the intermediate step, a selection referencing a local class would need to take
2612 the local class as a parameter if it were to be extracted to a new method. This
2613 new method would need to live in the scope of the declaring class of the
2614 originating method. The local class would then not be in the scope of the
2615 extracted method, thus bringing the source code into an illegal state. One could
2616 imagine that the method was extracted and moved in one operation, without an
2617 intermediate state. Then it would make sense to include variables with types of
2618 local classes in the set of legal targets, since the local classes would then be
2619 in the scopes of the method calls. If this makes any difference for software
2620 metrics that measure coupling would be a different discussion.
2623 \begin{multicols}{2}
2624 \begin{minted}[]{java}
2626 void declaresLocalClass() {
2641 \begin{minted}[]{java}
2642 // After Extract Method
2643 void declaresLocalClass() {
2654 // Intermediate step
2655 void fooBar(LocalClass inst) {
2661 \caption{When \refa{Extract and Move Method} tries to use a variable with a local type
2662 as the move target, an intermediate step is taken that is not allowed. Here:
2663 \type{LocalClass} is not in the scope of \method{fooBar} in its intermediate
2665 \label{lst:extractMethod_LocalClass}
2668 The last class of names that are considered unfixes is names used in null tests.
2669 These are tests that reads like this: if \texttt{<name>} equals \var{null} then
2670 do something. If allowing variables used in those kinds of expressions as
2671 targets for moving methods, we would end up with code containing boolean
2672 expressions like \texttt{this == null}, which would not be meaningful, since
2673 \var{this} would never be \var{null}.
2676 \subsection{The ContainsReturnStatementCollector}
2678 \typewithref{no.uio.ifi.refaktor.analyze.collectors}{ContainsReturnStatementCollector}
2679 is a very simple property collector. It only visits the return statements within
2680 a selection, and can report whether it encountered a return statement or not.
2682 \subsection{The LastStatementCollector}
2683 The \typewithref{no.uio.ifi.refaktor.analyze.collectors}{LastStatementCollector}
2684 collects the last statement of a selection. It does so by only visiting the top
2685 level statements of the selection, and compares the textual end offset of each
2686 encountered statement with the end offset of the previous statement found.
2688 \section{Checkers}\label{checkers}
2689 \todoin{Check out ExtractMethodAnalyzer from ExtractMethodRefactoring}
2690 The checkers are a range of classes that checks that text selections complies
2691 with certain criteria. All checkers operates under the assumption that the code
2692 they check is free from compilation errors. If a
2693 \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{Checker} fails, it throws a
2694 \type{CheckerException}. The checkers are managed by the
2695 \type{LegalStatementsChecker}, which does not, in fact, implement the
2696 \type{Checker} interface. It does, however, run all the checkers registered with
2697 it, and reports that all statements are considered legal if no
2698 \type{CheckerException} is thrown. Many of the checkers either extends the
2699 \type{PropertyCollector} or utilizes one or more property collectors to verify
2700 some criteria. The checkers registered with the \type{LegalStatementsChecker}
2701 are described next. They are run in the order presented below.
2703 \subsection{The CallToProtectedOrPackagePrivateMethodChecker}
2704 This checker is designed to prevent an error that can occur in situations where
2705 a method is declared in one class, but overridden in another. If a text
2706 selection contains a call to a method like this, and the seletion is extracted
2707 to a new method, the subsequent movement of this method could cause the code to
2710 The code breaks in situations where the method call in the selection is to a
2711 method that has the \code{protected} modifier, or it does not have any access
2712 modifiers, i.e. it is package-private. The method is not public, so the
2713 \MoveMethod refactoring must make it public, making the moved method able to
2714 call it from its new location. The problem is that the, now public, method is
2715 overridden in a subclass, where it has a protected or package-private status.
2716 This makes the compiler complain that the subclass is trying to reduce the
2717 visibility of a method declared in its superclass. This is not allowed in Java,
2718 and for good reasons. It would make it possible to make a subclass that could
2719 not be a substitute for its superclass.
2721 The workings of the \type{CallToProtectedOrPackagePrivateMethod\-Checker} is
2722 therefore very simple. It looks for calls to methods that are either protected
2723 or package-private within the selection, and throws an
2724 \type{IllegalExpressionFoundException} if one is found.
2726 The problem this checker helps to avoid, is a little subtle. The problem does
2727 not arise in the class where the change is done, but in a class derived from it.
2728 This shows that classes acting as superclasses are especially fragile to
2729 introducing errors in the context of automated refactoring. This is also shown
2730 in bug\ldots \todoin{File Eclipse bug report}
2732 \subsection{The InstantiationOfNonStaticInnerClassChecker}
2733 When a non-static inner class is instatiated, this must happen in the scope of
2734 its declaring class. This is because it must have access to the members of the
2735 declaring class. If the inner class is public, it is possible to instantiate it
2736 through an instance of its declaring class, but this is not handled by the
2737 \type{MoveInstanceMethodProcessor} in Eclipse when moving a method. Therefore,
2738 performing a move on a method that instantiates a non-static inner class, will
2739 break the code if the instantiation is not handled properly. For this reason,
2740 the \type{InstantiationOfNonStaticInnerClassChecker} does not validate
2741 selections that contains instantiations of non-static inner classes. This
2742 problem is also related to bug\ldots \todoin{File Eclipse bug report}
2744 \subsection{The EnclosingInstanceReferenceChecker}
2745 The purpose of this checker is to verify that the names in a selection is not
2746 referencing any enclosing instances. This is for making sure that all references
2747 is legal in a method that is to be moved. Theoretically, some situations could
2748 be easily solved my passing a reference to the referenced class with the moved
2749 method (e.g. when calling public methods), but the dependency on the
2750 \type{MoveInstanceMethodProcessor} prevents this.
2753 \typewithref{no.uio.ifi.refaktor.analyze.analyzers}{EnclosingInstanceReferenceChecker}
2754 is a modified version of the
2755 \typewithref{org.eclipse.jdt.internal.corext.refactoring.structure.MoveInstanceMethod\-Processor}{EnclosingInstanceReferenceFinder}
2756 from the \type{MoveInstanceMethodProcessor}. Wherever the
2757 \type{EnclosingInstanceReferenceFinder} would create a fatal error status, the
2758 checker throws a \type{CheckerException}.
2760 It works by first finding all of the enclosing types of a selection. Thereafter
2761 it visits all its simple names to check that they are not references to
2762 variables or methods declared in any of the enclosing types. In addition the
2763 checker visits \var{this}-expressions to verify that no such expressions is
2764 qualified with any name.
2766 \subsection{The ReturnStatementsChecker}\label{returnStatementsChecker}
2767 The checker for return statements is meant to verify that if a text selection
2768 contains a return statement, then every possible execution path within the
2769 selection ends in a return statement. This property is important regarding the
2770 \ExtractMethod refactoring. If it holds, it means that a method could be
2771 extracted from the selection, and a call to it could be substituted for the
2772 selection. If the method has a non-void return type, then a call to it would
2773 also be a valid return point for the calling method. If its return value is of
2774 the void type, then the \type{ExtractMethodRefactoring} of \name{Eclipse}
2775 appends an empty return statement to the back of the method call. Therefore, the
2776 analysis does not discriminate on either kinds of return statements, with or
2777 without a return value.
2779 The property description implies that if the selection is free from return
2780 statements, then the checker validates. So this is the first thing the checker
2783 If the checker proceedes any further, it is because the selection contains one
2784 or more return statements. The next test is therefore to check if the last
2785 statement of the selection ends in either a return or a throw statement. If the
2786 last statement of the selection ends in a return statement, then all execution
2787 paths within the selection should end in either this, or another, return
2788 statement. This is also true for a throw statement, since it causes an immediate
2789 exit from the current block, together with all outer blocks in its control flow
2790 that does not catch the thrown exception.
2792 Return statements can be either explicit or implicit. An \emph{explicit} return
2793 statement is formed by using the \code{return} keyword, while an \emph{implicit}
2794 return statement is a statement that is not formed by the \code{return} keyword,
2795 but must be the last statement of a method that can have any side effects. This
2796 can happen in methods with a void return type. An example is a statement that is
2797 inside one or more blocks. The last statement of a method could for instance be
2798 an if-statement, but the last statement that is executed in the method, and that
2799 can have any side effects, may be located inside the block of the else part of
2802 The responsibility for checking that the last statement of the selection
2803 eventually ends in a return or throw statement, is put on the
2804 \type{LastStatementOfSelectionEndsInReturnOrThrowChecker}. For every node
2805 visited, if it is a statement, it does a test to see if the statement is a
2806 return, a throw or if it is an implicit return statement. If this is the case,
2807 no further checking is done. This checking is done in the \code{preVisit2}
2808 method \see{astVisitor}. If the node is not of a type that is being handled by
2809 its type specific visit method, the checker performs a simple test. If the node
2810 being visited is not the last statement of its parent that is also enclosed by
2811 the selection, an \type{IllegalStatementFoundException} is thrown. This ensures
2812 that all statements are taken care of, one way or the other. It also ensures
2813 that the checker is conservative in the way it checks for legality of the
2816 To examine if a statement is an implicit return statement, the checker first
2817 finds the last statement declared in its enclosing method. If this statement is
2818 the same as the one under investigation, it is considered an implicit return
2819 statement. If the statements are not the same, the checker does a search to see
2820 if statement examined is also the last statement of the method that can be
2821 reached. This includes the last statement of a block statement, a labeled
2822 statement, a synchronized statement or a try statement, that in turn is the last
2823 statement enclosed by the statement types listed. This search goes through all
2824 the parents of a statement until a statement is found that is not one of the
2825 mentioned acceptable parent statements. If the search ends in a method
2826 declaration, then the statement is considered to be the last reachable statement
2827 of the method, and thus also an implicit return statement.
2829 There are two kinds of statements that are handled explicitly. It is
2830 if-statements and try-statements. Block, labeled and do-statements are handled
2831 by fall-through to the other two. Do-statements are considered equal to blocks
2832 in this context, since their bodies are always evaluated at least one time. If-
2833 and try-statements are visited only if they are the last node of their parent
2834 within the selection.
2836 For if-statements, the rule is that if the then-part does not contain any return
2837 or throw statements, it is considered illegal. If it does contain a return or
2838 throw, its else-part is checked. If the else-part is non-existent, or it does
2839 not contain any return or throw statements, it is considered illegal. If the
2840 statement is not regarded illegal, its children are visited.
2842 Try-statements are handled much the same way as if-statements. Its body must
2843 contain a return or throw. The same applies to its catch clauses and finally
2846 If the checker does not complain at any point, the selection is considered valid
2847 with respect to return statements.
2849 \subsection{The AmbiguousReturnValueChecker}
2850 This checker verifies that there are no \emph{ambiguous return statements} in a
2851 selection. The problem with ambiguous return statements arise when a selection
2852 is chosen to be extracted into a new method, but it needs to return more than
2853 one value from that method. This problem occurs in two situations. The first
2854 situation arise when there is more than one local variable that is both assigned
2855 to within a selection and also referenced after the selection. The other
2856 situation occur when there is only one such assignment, but there is also one or
2857 more return statements in the selection.
2859 First the checker needs to collect some data. Those data are the binding keys
2860 for all simple names that are assigned to within the selection, including
2861 variable declarations, but excluding fields. The checker also collects whether
2862 there exists a return statement in the selection or not. No further checks of
2863 return statements are needed, since, at this point, the selection is already
2864 checked for illegal return statements \see{returnStatementsChecker}.
2866 After the binding keys of the assignees are collected, the checker searches the
2867 part of the enclosing method that is after the selection for references whose
2868 binding keys are among the collected keys. If more than one unique referral is
2869 found, or only one referral is found, but the selection also contains a return
2870 statement, we have a situation with an ambiguous return value, and an exception
2873 %\todoin{Explain why we do not need to consider variables assigned inside
2874 %local/anonymous classes. (The referenced variables need to be final and so
2877 \subsection{The IllegalStatementsChecker}
2878 This checker is designed to check for illegal statements.
2880 Any use of the \var{super} keyword is prohibited, since its meaning is altered
2881 when moving a method to another class.
2883 For a \emph{break} statement, there is two situations to consider: A break
2884 statement with or without a label. If the break statement has a label, it is
2885 checked that whole of the labeled statement is inside the selection. Since a
2886 label does not have any binding information, we have to search upwards in the
2887 AST to find the \type{LabeledStatement} that corresponds to the label from the
2888 break statement, and check that it is contained in the selection. If the break
2889 statement does not have a label attached to it, it is checked that its innermost
2890 enclosing loop or switch statement also is inside the selection.
2892 The situation for a \emph{continue} statement is the same as for a break
2893 statement, except that it is not allowed inside switch statements.
2895 Regarding \emph{assignments}, two types of assignments is allowed: Assignment to
2896 a non-final variable and assignment to an array access. All other assignments is
2899 \todoin{Finish\ldots}
2902 \chapter{Benchmarking}
2903 \todoin{Better name than ``benchmarking''?}
2904 This part of the master project is located in the \name{Eclipse} project
2905 \code{no.uio.ifi.refaktor.benchmark}. The purpose of it is to run the equivalent
2906 of the \type{SearchBasedExtractAndMoveMethodChanger}
2907 \see{searchBasedExtractAndMoveMethodChanger} over a larger software project,
2908 both to test its robustness but also its effect on different software metrics.
2910 \section{The benchmark setup}
2911 The benchmark itself is set up as a \name{JUnit} test case. This is a convenient
2912 setup, and utilizes the \name{JUnit Plugin Test Launcher}. This provides us a
2913 with a fully functional \name{Eclipse} workbench. Most importantly, this gives
2914 us access to the Java Model of \name{Eclipse} \see{javaModel}.
2916 \subsection{The ProjectImporter}
2917 The Java project that is going to be used as the data for the benchmark, must be
2918 imported into the JUnit workspace. This is done by the
2919 \typewithref{no.uio.ifi.refaktor.benchmark}{ProjectImporter}. The importer
2920 require the absolute path to the project description file. It is named
2921 \code{.project} and is located at the root of the project directory.
2923 The project description is loaded to find the name of the project to be
2924 imported. The project that shall be the destination for the import is created in
2925 the workspace, on the base of the name from the description. Then an import
2926 operation is created, based on both the source and destination information. The
2927 import operation is run to perform the import.
2929 I have found no simple API call to accomplish what the importer does, which
2930 tells me that it may not be too many people performing this particular action.
2931 The solution to the problem was found on \name{Stack
2932 Overflow}\footnote{\url{https://stackoverflow.com/questions/12401297}}. It
2933 contains enough dirty details to be considered inconvenient to use, if not
2934 wrapping it in a class like my \type{ProjectImporter}. One would probably have
2935 to delve into the source code for the import wizard to find out how the import
2936 operation works, if no one had already done it.
2938 \section{Statistics}
2939 Statistics for the analysis and changes is captured by the
2940 \typewithref{no.uio.ifi.refaktor.aspects}{StatisticsAspect}. This an
2941 \emph{aspect} written in \name{AspectJ}.
2943 \subsection{AspectJ}
2944 \name{AspectJ}\footnote{\url{http://eclipse.org/aspectj/}} is an extension to
2945 the Java language, and facilitates combining aspect-oriented programming with
2946 the object-oriented programming in Java.
2948 Aspect-oriented programming is a programming paradigm that is meant to isolate
2949 so-called \emph{cross-cutting concerns} into their own modules. These
2950 cross-cutting concerns are functionalities that spans over multiple classes, but
2951 may not belong naturally in any of them. It can be functionality that does not
2952 concern the business logic of an application, and thus may be a burden when
2953 entangled with parts of the source code it does not really belong. Examples
2954 include logging, debugging, optimization and security.
2956 Aspects are interacting with other modules by defining advices. The concept of
2957 an \emph{advice} is known from both aspect-oriented and functional
2958 programming\citing{wikiAdvice2014}. It is a function that modifies another
2959 function when the latter is run. An advice in AspectJ is somewhat similar to a
2960 method in Java. It is meant to alter the behavior of other methods, and contains
2961 a body that is executed when it is applied.
2963 An advice can be applied at a defined \emph{pointcut}. A pointcut picks out one
2964 or more \emph{join points}. A join point is a well-defined point in the
2965 execution of a program. It can occur when calling a method defined for a
2966 particular class, when calling all methods with the same name,
2967 accessing/assigning to a particular field of a given class and so on. An advice
2968 can be declared to run both before, after returning from a pointcut, when there
2969 is thrown an exception in the pointcut or after the pointcut either returns or
2970 throws an exception. In addition to picking out join points, a pointcut can
2971 also bind variables from its context, so they can be accessed in the body of an
2972 advice. An example of a pointcut and an advice is found in
2973 \myref{lst:aspectjExample}.
2976 \begin{minted}{aspectj}
2977 pointcut methodAnalyze(
2978 SearchBasedExtractAndMoveMethodAnalyzer analyzer) :
2979 call(* SearchBasedExtractAndMoveMethodAnalyzer.analyze())
2980 && target(analyzer);
2982 after(SearchBasedExtractAndMoveMethodAnalyzer analyzer) :
2983 methodAnalyze(analyzer) {
2984 statistics.methodCount++;
2985 debugPrintMethodAnalysisProgress(analyzer.method);
2988 \caption{An example of a pointcut named \method{methodAnalyze},
2989 and an advice defined to be applied after it has occurred.}
2990 \label{lst:aspectjExample}
2993 \subsection{The Statistics class}
2994 The statistics aspect stores statistical information in an object of type
2995 \type{Statistics}. As of now, the aspect needs to be initialized at the point in
2996 time where it is desired that it starts its data gathering. At any point in time
2997 the statistics aspect can be queried for a snapshot of the current statistics.
2999 The \type{Statistics} class also include functionality for generating a report
3000 of its gathered statistics. The report can be given either as a string or it can
3001 be written to a file.
3003 \subsection{Advices}
3004 The statistics aspect contains advices for gathering statistical data from
3005 different parts of the benchmarking process. It captures statistics from both
3006 the analysis part and the execution part of the composite \ExtractAndMoveMethod
3009 For the analysis part, there are advices to count the number of text selections
3010 analyzed and the number of methods, types, compilation units and packages
3011 analyzed. There are also advices that counts for how many of the methods there
3012 is found a selection that is a candidate for the refactoring, and for how many
3013 methods there is not.
3015 There exists advices for counting both the successful and unsuccessful
3016 executions of all the refactorings. Both for the \ExtractMethod and \MoveMethod
3017 refactorings in isolation, as well as for the combination of them.
3019 \section{Optimizations}
3020 When looking for optimizations to make for the benchmarking process, I used the
3021 \name{VisualVM}\footnote{\url{http://visualvm.java.net/}} for the Java Virtual
3022 Machine to both profile the application and also to make memory dumps of its
3025 \subsection{Caching}
3026 When profiling the benchmark process before making any optimizations, it early
3027 became apparent that the parsing of source code was a place to direct attention
3028 towards. This discovery was done when only \emph{analyzing} source code, before
3029 trying to do any \emph{manipulation} of it. Caching of the parsed ASTs seemed
3030 like the best way to save some time, as expected. With only a simple cache of
3031 the most recently used AST, the analysis time was speeded up by a factor of
3033 20. This number depends a little upon which type of system the analysis was
3036 The caching is managed by a cache manager, that now, by default, utilizes the
3037 not so well known feature of Java called a \emph{soft reference}. Soft
3038 references are best explained in the context of weak references. A \emph{weak
3039 reference} is a reference to an object instance that is only guaranteed to
3040 persist as long as there is a \emph{strong reference} or a soft reference
3041 referring the same object. If no such reference is found, its referred object is
3042 garbage collected. A strong reference is basically the same as a regular Java
3043 reference. A soft reference has the same guarantees as a week reference when it
3044 comes to its relation to strong references, but it is not necessarily garbage
3045 collected whenever there exists no strong references to it. A soft reference
3046 \emph{may} reside in memory as long as the JVM has enough free memory in the
3047 heap. A soft reference will therefore usually perform better than a weak
3048 reference when used for simple caching and similar tasks. The way to use a
3049 soft/weak reference is to as it for its referent. The return value then has to
3050 be tested to check that it is not \var{null}. For the basic usage of soft
3051 references, see \myref{lst:softReferenceExample}. For a more thorough
3052 explanation of weak references in general, see\citing{weakRef2006}.
3055 \begin{minted}{java}
3057 Object strongRef = new Object();
3060 SoftReference<Object> softRef =
3061 new SoftReference<Object>(new Object());
3063 // Using the soft reference
3064 Object obj = softRef.get();
3069 \caption{Showing the basic usage of soft references. Weak references is used the
3070 same way. {\footnotesize (The references are part of the \code{java.lang.ref}
3072 \label{lst:softReferenceExample}
3075 The cache based on soft references has no limit for how many ASTs it caches. It
3076 is generally not advisable to keep references to ASTs for prolonged periods of
3077 time, since they are expensive structures to hold on to. For regular plugin
3078 development, \name{Eclipse} recommends not creating more than one AST at a time to
3079 limit memory consumption. Since the benchmarking has nothing to do with user
3080 experience, and throughput is everything, these advices are intentionally
3081 ignored. This means that during the benchmarking process, the target \name{Eclipse}
3082 application may very well work close to its memory limit for the heap space for
3083 long periods during the benchmark.
3085 \subsection{Memento}
3089 \chapter{Technicalities}
3091 \section{Source code organization}
3092 All the parts of this master project is under version control with
3093 \name{Git}\footnote{\url{http://git-scm.com/}}.
3095 The software written is organized as some \name{Eclipse} plugins. Writing a plugin is
3096 the natural way to utilize the API of \name{Eclipse}. This also makes it possible to
3097 provide a user interface to manually run operations on selections in program
3098 source code or whole projects/packages.
3100 When writing a plugin in \name{Eclipse}, one has access to resources such as the
3101 current workspace, the open editor and the current selection.
3103 The thesis work is contained in the following Eclipse projects:
3106 \item[no.uio.ifi.refaktor] \hfill \\ This is the main Eclipse plugin
3107 project, and contains all of the business logic for the plugin.
3109 \item[no.uio.ifi.refaktor.tests] \hfill \\
3110 This project contains the tests for the main plugin.
3112 \item[no.uio.ifi.refaktor.examples] \hfill \\
3113 Contains example code used in testing. It also contains code for managing
3114 this example code, such as creating an Eclipse project from it before a test
3117 \item[no.uio.ifi.refaktor.benchmark] \hfill \\
3118 This project contains code for running search based versions of the
3119 composite refactoring over selected Eclipse projects.
3121 \item[no.uio.ifi.refaktor.releng] \hfill \\
3122 Contains the rmap, queries and target definitions needed by by Buckminster
3123 on the Jenkins continuous integration server.
3127 \subsection{The no.uio.ifi.refaktor project}
3129 \subsubsection{no.uio.ifi.refaktor.analyze}
3130 This package, and its subpackages, contains code that is used for analyzing Java
3131 source code. The most important subpackages are presented below.
3134 \item[no.uio.ifi.refaktor.analyze.analyzers] \hfill \\
3135 This package contains source code analyzers. These are usually responsible
3136 for analyzing text selections or running specialized analyzers for different
3137 kinds of entities. Their structure are often hierarchical. This means that
3138 you have an analyzer for text selections, that in turn is utilized by an
3139 analyzer that analyzes all the selections of a method. Then there are
3140 analyzers for analyzing all the methods of a type, all the types of a
3141 compilation unit, all the compilation units of a package, and, at last, all
3142 of the packages in a project.
3144 \item[no.uio.ifi.refaktor.analyze.checkers] \hfill \\
3145 A package containing checkers. The checkers are classes used to validate
3146 that a selection can be further analyzed and chosen as a candidate for a
3147 refactoring. Invalidating properties can be such as usage of inner classes
3148 or the need for multiple return values.
3150 \item[no.uio.ifi.refaktor.analyze.collectors] \hfill \\
3151 This package contains the property collectors. Collectors are used to gather
3152 properties from a text selection. This is mostly properties regarding
3153 referenced names and their occurrences. It is these properties that makes up
3154 the basis for finding the best candidates for a refactoring.
3157 \subsubsection{no.uio.ifi.refaktor.change}
3158 This package, and its subpackages, contains functionality for manipulate source
3162 \item[no.uio.ifi.refaktor.change.changers] \hfill \\
3163 This package contains source code changers. They are used to glue together
3164 the analysis of source code and the actual execution of the changes.
3166 \item[no.uio.ifi.refaktor.change.executors] \hfill \\
3167 The executors that are responsible for making concrete changes are found in
3168 this package. They are mostly used to create and execute one or more Eclipse
3171 \item[no.uio.ifi.refaktor.change.processors] \hfill \\
3172 Contains a refactoring processor for the \MoveMethod refactoring. The code
3173 is stolen and modified to fix a bug. The related bug is described in
3174 \myref{eclipse_bug_429416}.
3178 \subsubsection{no.uio.ifi.refaktor.handlers}
3179 This package contains handlers for the commands defined in the plugin manifest.
3181 \subsubsection{no.uio.ifi.refaktor.prefix}
3182 This package contains the \type{Prefix} type that is the data representation of
3183 the prefixes found by the \type{PrefixesCollector}. It also contains the prefix
3184 set for storing and working with prefixes.
3186 \subsubsection{no.uio.ifi.refaktor.statistics}
3187 The package contains statistics functionality. Its heart is the statistics
3188 aspect that is responsible for gathering statistics during the execution of the
3189 \ExtractAndMoveMethod refactoring.
3192 \item[no.uio.ifi.refaktor.statistics.reports] \hfill \\
3193 This package contains a simple framework for generating reports from the
3194 statistics data generated by the aspect. Currently, the only available
3195 report type is a simple text report.
3200 \subsubsection{no.uio.ifi.refaktor.textselection}
3201 This package contains the two custom text selections that are used extensively
3202 throughout the project. One of them is just a subclass of the other, to support
3203 the use of the memento pattern to optimize the memory usage during benchmarking.
3205 \subsubsection{no.uio.ifi.refaktor.debugging}
3206 The package contains a debug utility class. I addition to this, the package
3207 \code{no.uio.ifi.refaktor.utils.aspects} contains a couple of aspects used for
3210 \subsubsection{no.uio.ifi.refaktor.utils}
3211 Utility package that contains all the functionality that has to do with parsing
3212 of source code. It also has utility classes for looking up handles to methods
3213 and types et cetera.
3216 \item[no.uio.ifi.refaktor.utils.caching] \hfill \\
3217 This package contains the caching manager for compilation units, along with
3218 classes for different caching strategies.
3220 \item[no.uio.ifi.refaktor.utils.nullobjects] \hfill \\
3221 Contains classes for creating different null objects. Most of the classes is
3222 used to represent null objects of different handle types. These null objects
3223 are returned from various utility classes instead of returning a \var{null}
3224 value when other values are not available.
3228 \section{Continuous integration}
3229 The continuous integration server
3230 \name{Jenkins}\footnote{\url{http://jenkins-ci.org/}} has been set up for the
3231 project\footnote{A work mostly done by the supervisor.}. It is used as a way to
3232 run tests and perform code coverage analysis.
3234 To be able to build the \name{Eclipse} plugins and run tests for them with Jenkins, the
3235 component assembly project
3236 \name{Buckminster}\footnote{\url{http://www.eclipse.org/buckminster/}} is used,
3237 through its plugin for Jenkins. Buckminster provides for a way to specify the
3238 resources needed for building a project and where and how to find them.
3239 Buckminster also handles the setup of a target environment to run the tests in.
3240 All this is needed because the code to build depends on an \name{Eclipse}
3241 installation with various plugins.
3243 \subsection{Problems with AspectJ}
3244 The Buckminster build worked fine until introducing AspectJ into the project.
3245 When building projects using AspectJ, there are some additional steps that needs
3246 to be performed. First of all, the aspects themselves must be compiled. Then the
3247 aspects needs to be woven with the classes they affect. This demands a process
3248 that does multiple passes over the source code.
3250 When using AspectJ with \name{Eclipse}, the specialized compilation and the
3251 weaving can be handled by the \name{AspectJ Development
3252 Tools}\footnote{\url{https://www.eclipse.org/ajdt/}}. This works all fine, but
3253 it complicates things when trying to build a project depending on \name{Eclipse}
3254 plugins outside of \name{Eclipse}. There is supposed to be a way to specify a
3255 compiler adapter for javac, together with the file extensions for the file types
3256 it shall operate. The AspectJ compiler adapter is called
3257 \typewithref{org.aspectj.tools.ant.taskdefs}{Ajc11CompilerAdapter}, and it works
3258 with files that has the extensions \code{*.java} and \code{*.aj}. I tried to
3259 setup this in the build properties file for the project containing the aspects,
3260 but to no avail. The project containing the aspects does not seem to be built at
3261 all, and the projects that depends on it complains that they cannot find certain
3264 I then managed to write an \name{Ant}\footnote{\url{https://ant.apache.org/}}
3265 build file that utilizes the AspectJ compiler adapter, for the
3266 \code{no.uio.ifi.refaktor} plugin. The problem was then that it could no longer
3267 take advantage of the environment set up by Buckminster. The solution to this
3268 particular problem was of a ``hacky'' nature. It involves exporting the plugin
3269 dependencies for the project to an Ant build file, and copy the exported path
3270 into the existing build script. But then the Ant script needs to know where the
3271 local \name{Eclipse} installation is located. This is no problem when building
3272 on a local machine, but to utilize the setup done by Buckminster is a problem
3273 still unsolved. To get the classpath for the build setup correctly, and here
3274 comes the most ``hacky'' part of the solution, the Ant script has a target for
3275 copying the classpath elements into a directory relative to the project
3276 directory and checking it into Git. When no \code{ECLIPSE\_HOME} property is set
3277 while running Ant, the script uses the copied plugins instead of the ones
3278 provided by the \name{Eclipse} installation when building the project. This
3279 obviously creates some problems with maintaining the list of dependencies in the
3280 Ant file, as well as remembering to copy the plugins every time the list of
3281 dependencies change.
3283 The Ant script described above is run by Jenkins before the Buckminster setup
3284 and build. When setup like this, the Buckminster build succeeds for the projects
3285 not using AspectJ, and the tests are run as normal. This is all good, but it
3286 feels a little scary, since the reason for Buckminster not working with AspectJ
3289 The problems with building with AspectJ on the Jenkins server lasted for a
3290 while, before they were solved. This is reflected in the ``Test Result Trend''
3291 and ``Code Coverage Trend'' reported by Jenkins.
3294 \chapter{Eclipse Bugs Found}
3295 \newcommand{\submittedBugReport}[1]{The submitted bug report can be found on
3298 \section{Eclipse bug 420726: Code is broken when moving a method that is
3299 assigning to the parameter that is also the move
3300 destination}\label{eclipse_bug_420726}
3302 was found when analyzing what kinds of names that was to be considered as
3303 \emph{unfixes} \see{unfixes}.
3305 \subsection{The bug}
3306 The bug emerges when trying to move a method from one class to another, and when
3307 the target for the move (must be a variable, local or field) is both a parameter
3308 variable and also is assigned to within the method body. \name{Eclipse} allows this to
3309 happen, although it is the sure path to a compilation error. This is because we
3310 would then have an assignment to a \var{this} expression, which is not allowed
3312 \submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=420726}
3314 \subsection{The solution}
3315 The solution to this problem is to add all simple names that are assigned to in
3316 a method body to the set of unfixes.
3318 \section{Eclipse bug 429416: IAE when moving method from anonymous
3319 class}\label{eclipse_bug_429416}
3321 this bug during a batch change on the \type{org.eclipse.jdt.ui} project.
3323 \subsection{The bug}
3324 This bug surfaces when trying to use the \refa{Move Method} refactoring to move a
3325 method from an anonymous class to another class. This happens both for my
3326 simulation as well as in \name{Eclipse}, through the user interface. It only occurs
3327 when \name{Eclipse} analyzes the program and finds it necessary to pass an instance of
3328 the originating class as a parameter to the moved method. I.e. it want to pass a
3329 \var{this} expression. The execution ends in an
3330 \typewithref{java.lang}{IllegalArgumentException} in
3331 \typewithref{org.eclipse.jdt.core.dom}{SimpleName} and its
3332 \method{setIdentifier(String)} method. The simple name is attempted created in
3334 \methodwithref{org.eclipse.jdt.internal.corext.refactoring.structure.\\MoveInstanceMethodProcessor}{createInlinedMethodInvocation}
3335 so the \type{MoveInstanceMethodProcessor} was early a clear suspect.
3337 The \method{createInlinedMethodInvocation} is the method that creates a method
3338 invocation where the previous invocation to the method that was moved was. From
3339 its code it can be read that when a \var{this} expression is going to be passed
3340 in to the invocation, it shall be qualified with the name of the original
3341 method's declaring class, if the declaring class is either an anonymous class or
3342 a member class. The problem with this, is that an anonymous class does not have
3343 a name, hence the term \emph{anonymous} class! Therefore, when its name, an
3344 empty string, is passed into
3345 \methodwithref{org.eclipse.jdt.core.dom.AST}{newSimpleName} it all ends in an
3346 \type{IllegalArgumentException}.
3347 \submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429416}
3349 \subsection{How I solved the problem}
3350 Since the \type{MoveInstanceMethodProcessor} is instantiated in the
3351 \typewithref{no.uio.ifi.refaktor.change.executors}{MoveMethod\-RefactoringExecutor},
3352 and only need to be a
3353 \typewithref{org.eclipse.ltk.core.refactoring.participants}{MoveProcessor}, I
3354 was able to copy the code for the original move processor and modify it so that
3355 it works better for me. It is now called
3356 \typewithref{no.uio.ifi.refaktor.change.processors}{ModifiedMoveInstanceMethodProcessor}.
3357 The only modification done (in addition to some imports and suppression of
3358 warnings), is in the \method{createInlinedMethodInvocation}. When the declaring
3359 class of the method to move is anonymous, the \var{this} expression in the
3360 parameter list is not qualified with the declaring class' (empty) name.
3362 \section{Eclipse bug 429954: Extracting statement with reference to local type
3363 breaks code}\label{eclipse_bug_429954}
3365 was discovered when doing some changes to the way unfixes is computed.
3367 \subsection{The bug}
3368 The problem is that \name{Eclipse} is allowing selections that references variables of
3369 local types to be extracted. When this happens the code is broken, since the
3370 extracted method must take a parameter of a local type that is not in the
3371 methods scope. The problem is illustrated in
3372 \myref{lst:extractMethod_LocalClass}, but there in another setting.
3373 \submittedBugReport{https://bugs.eclipse.org/bugs/show\_bug.cgi?id=429954}
3375 \subsection{Actions taken}
3376 There are no actions directly springing out of this bug, since the Extract
3377 Method refactoring cannot be meant to be this way. This is handled on the
3378 analysis stage of our \refa{Extract and Move Method} refactoring. So names representing
3379 variables of local types is considered unfixes \see{unfixes}.
3380 \todoin{write more when fixing this in legal statements checker}
3382 \chapter{Conclusions and Future Work}
3385 \section{Future work}
3386 \todoin{Copied from introduction:}
3387 For the metrics, I will at least measure the \metr{Coupling between object
3388 classes} (CBO) metric that is described by Chidamber and Kemerer in their
3389 article \tit{A Metrics Suite for Object Oriented
3390 Design}\citing{metricsSuite1994}.
3394 Then the effect of the change must be measured by calculating the chosen
3395 software metrics both before and after the execution.
3396 \todoin{Metrics, \ldots}
3398 \chapter{Related Work}
3400 \section{The compositional paradigm of refactoring}
3401 This paradigm builds upon the observation of Vakilian et
3402 al.\citing{vakilian2012}, that of the many automated refactorings existing in
3403 modern IDEs, the simplest ones are dominating the usage statistics. The report
3404 mainly focuses on \name{Eclipse} as the tool under investigation.
3406 The paradigm is described almost as the opposite of automated composition of
3407 refactorings \see{compositeRefactorings}. It works by providing the programmer
3408 with easily accessible primitive refactorings. These refactorings shall be
3409 accessed via keyboard shortcuts or quick-assist menus\footnote{Think
3410 quick-assist with Ctrl+1 in \name{Eclipse}} and be promptly executed, opposed to in the
3411 currently dominating wizard-based refactoring paradigm. They are meant to
3412 stimulate composing smaller refactorings into more complex changes, rather than
3413 doing a large upfront configuration of a wizard-based refactoring, before
3414 previewing and executing it. The compositional paradigm of refactoring is
3415 supposed to give control back to the programmer, by supporting \himher with an
3416 option of performing small rapid changes instead of large changes with a lesser
3417 degree of control. The report authors hope this will lead to fewer unsuccessful
3418 refactorings. It also could lower the bar for understanding the steps of a
3419 larger composite refactoring and thus also help in figuring out what goes wrong
3420 if one should choose to op in on a wizard-based refactoring.
3422 Vakilian and his associates have performed a survey of the effectiveness of the
3423 compositional paradigm versus the wizard-based one. They claim to have found
3424 evidence of that the \emph{compositional paradigm} outperforms the
3425 \emph{wizard-based}. It does so by reducing automation, which seem
3426 counterintuitive. Therefore they ask the question ``What is an appropriate level
3427 of automation?'', and thus questions what they feel is a rush toward more
3428 automation in the software engineering community.