\Approach: Assessing Semantic Merge Conflicts\\with Dependency Analysis
In software development, version control systems (VCS) provide branching and merging support tools. Such tools are popular among developers to concurrently change a codebase in separate lines and reconcile their changes automatically afterwards. However, two changes that are correct independently can introduce bugs when merged together. We call \Problems{ this kind of bugs. %While VCS merging tools can detect some kinds of conflicts, some conflicts exceed their scope. %For example, the Fragile Base Class Problem shows that a merge can succeed and the resulting codebase can compile without errors, %The symptoms of an merge with semantical conflicts can be evident when the merging process or a test execution fails. %However, the symptoms are not always that evident. %In any case, it requires an effort for the integrator to detect semantical conflicts, and tools do not help. Change impact analysis (CIA) aims at estimating the effects of a change in a codebase. In this paper, we propose to detect \Problems{ using CIA. On a merge, \Approach analyzes and compares the impact of a change in its origin and destination branches. We call the difference between these two impacts the delta-impact. If the delta-impact is empty, then there is no indicator of a \Problem{ and the merge can continue automatically. Otherwise, the delta-impact contains what are the sources of possible conflicts. %There is plenty of research on CIA techniques but, to the best of our knowledge, there is no research for the scenario described. \tincho{fix %In this paper, we propose a CIA technique which analyzes the dependencies source code to detect effects that were unintended by the author in the original codebase. %We describe an implementation of our approach and we do an empirical evaluation.
macros.tex
\newboolean{showcomments}
\setboolean{showcomments}{false}


\ifthenelse{\boolean{showcomments}}
  {\newcommand{\bnote}[2]{
	\fbox{\bfseries\sffamily\scriptsize#1}
    {\sf\small$\blacktriangleright$\textit{#2}$\blacktriangleleft$}
    % \marginpar{\fbox{\bfseries\sffamily#1}}
   }
   \newcommand{\cvsversion}{\emph{\scriptsize$-$Id: macros.tex,v 1.1.1.1 2007/02/28 13:43:36 bergel Exp $-$}}
  }
  {\newcommand{\bnote}[2]{}
   \newcommand{\cvsversion}{}
  } 


\newcommand{\here}{\bnote{***}{CONTINUE HERE}}
\newcommand{\nb}[1]{\bnote{NB}{#1}}

\newcommand{\fix}[1]{\bnote{FIX}{#1}}
%%%% add your own macros 

\newcommand{\sd}[1]{\bnote{Stef}{#1}}
\newcommand{\dc}[1]{\bnote{Damien}{#1}}
\newcommand{\tincho}[1]{\bnote{Martin}{#1}}
\newcommand{\gp}[1]{\bnote{Guille}{#1}}

\graphicspath{{figures/}}
%%% 


\newcommand{\figref}[1]{Figure~\ref{fig:#1}}
\newcommand{\figlabel}[1]{\label{fig:#1}}
\newcommand{\tabref}[1]{Table~\ref{tab:#1}}
\newcommand{\layout}[1]{#1}
\newcommand{\commented}[1]{}
\newcommand{\secref}[1]{Section~\ref{sec:#1}}
\newcommand{\seclabel}[1]{\label{sec:#1}}

\newcommand{\stCode}[1]{\textsf{#1}}
\newcommand{\stMethod}[1]{\textsf{#1}}
\newcommand{\sep}{\texttt{>>}\xspace}
\newcommand{\stAssoc}{\texttt{->}\xspace}

\newcommand{\stBar}{$\mid$}
\newcommand{\stSelector}{$\gg$}
\newcommand{\stRet}{\^{}}
\newcommand{\msup}{$>$}
\newcommand{\infe}{$<$}
\newcommand{\supe}{$\rightarrow$\xspace}
\newcommand{\di}{$\gg$\xspace}

\newcommand{\adhoc}{\textit{ad-hoc}\xspace}
\newcommand{\myparagraph}[1]{\noindent\textbf{#1.}}
\newcommand{\eg}{\emph{e.g.,}\xspace}
\newcommand{\ie}{\emph{i.e.,}\xspace}
\newcommand{\etal}{\emph{et al.}\xspace}
\newcommand{\ct}[1]{{\textsf{#1}}\xspace}


\def\Ring{\ct{Ring}}
\def\Monticello{\ct{Monticello}}
\def\Pharo{\ct{Pharo}}
\def\Smalltalk{\ct{Smalltalk}}
\def\Announcements{\ct{Announcements}}
\def\vm{\ct{VM}}

% EPICEA %%%%%%
\newcommand{\enode}[1]{\tikz[remember picture]\node[fill,circle,scale=0.4] (#1) {};}  
\newcommand{\elink}[2]{\tikz[remember picture,overlay]\path[line width=1pt] (#1.center) edge (#2.center) {};}  
\newcommand{\efork}[2]{\tikz[remember picture,overlay]\path[line width=1pt,out=right,in=up,looseness=0.8] (#1.center) edge (#2.center) {};}  
\newcommand{\emerge}[2]{\tikz[remember picture,overlay]\path[line width=1pt,out=down,in=right,looseness=0.8] (#1.center) edge (#2.center) {};}  

\newcommand{\etag}[1]{\scalebox{0.7}{\sffamily\doublebox{#1}}}
\newcommand{\eheadt}[1]{\scalebox{0.8}{\sffamily\ovalbox{$\lhd$ #1}}}
\newcommand{\ehead}{\eheadt{h}}

\newcommand{\etab}{\hspace{2mm}}

\newcounter{enodecounter}
\newcounter{elastnodecounter}

\newcommand{\efirstnode}{\setcounter{enodecounter}{1}\enode{1}}

\newcommand{\echildnodefrom}[1]{%
\stepcounter{enodecounter}%
\enode{\arabic{enodecounter}}%
\elink{#1}{\arabic{enodecounter}}}

\newcommand{\echildnode}{%
\setcounter{elastnodecounter}{\value{enodecounter}}
\echildnodefrom{\arabic{elastnodecounter}}}

\newcommand{\eforknodefrom}[1]{%
\stepcounter{enodecounter}%
\enode{\arabic{enodecounter}}%
\efork{#1}{\arabic{enodecounter}}}
	

\newcommand\esubcaption[1]{\begin{center}\emph{#1}\end{center}}

\newenvironment{eview}
    {\begin{alltt}\sffamily\small}
    {\end{alltt}}


%%%%%%%%%%%%


\newenvironment{code}
    {\begin{alltt}\sffamily\small}
    {\end{alltt}\normalsize}

\newcommand{\defaultScale}{0.55}
\newcommand{\pic}[3]{
   \begin{figure}[h]
   \begin{center}
   \includegraphics[scale=\defaultScale]{#1}
   \caption{#2}
   \label{#3}
   \end{center}
   \end{figure}
}

\newcommand{\twocolumnpic}[3]{
   \begin{figure*}[!ht]
   \begin{center}
   \includegraphics[scale=\defaultScale]{#1}
   \caption{#2}
   \label{#3}
   \end{center}
   \end{figure*}}

\usepackage{url}            
\makeatletter
\def\url@leostyle{%
  \@ifundefined{selectfont}{\def\UrlFont{\sf}}{\def\UrlFont{\small\sffamily}}}
\makeatother
% Now actually use the newly defined style.
\urlstyle{leo}




main.tex
\documentclass[10pt]{sigplanconf}

\pdfoutput=1

\usepackage[T1]{fontenc} %%%key to get copy and paste for the code
\usepackage[utf8]{inputenc} %%% to support copy and paste with accents
%\usepackage{times}
%\usepackage[scaled=0.85]{helvet}
\usepackage{graphicx}
\usepackage{ifthen}
\usepackage{xspace}
\usepackage{alltt}
\usepackage{latexsym}
\usepackage{url}            
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage{stmaryrd}
\usepackage{enumerate}
%\usepackage{cite}
%\usepackage[pdftex,colorlinks=true,pdfstartview=FitV,linkcolor=blue,citecolor=blue,urlcolor=blue]{hyperref}
\usepackage{xspace}
\usepackage{tikz}
\usepackage{fancybox}

\input{macros}

\newtheorem{definition}{Definition}

\begin{document}

\newcommand{\Approach}{\textsc{DeltaImpactFinder}\xspace}
\newcommand{\Problem}{semantic merge conflict\xspace}
\newcommand{\Problems}{\Problem{}s\xspace}


\conferenceinfo{IWST'15}{July 15 - 16, 2015, Brescia, Italy}
\copyrightyear{2015} 
\copyrightdata{978-1-4503-3857-8/15/07} 
\doi{2811237.2811299}
\exclusivelicense                % ACM gets exclusive license to publish, 
                                  % you retain copyright




\title{\Approach: Assessing Semantic Merge Conflicts\\with Dependency Analysis}

\authorinfo{Mart\'in Dias \and Guillermo Polito \and Damien Cassou \and St\'ephane Ducasse}{
RMoD\\
Inria Lille--Nord Europe --- University of Lille --- CRIStAL, France}


\maketitle

\begin{abstract}

In software development, version control systems (VCS) provide branching and merging support tools. 
Such tools are popular among developers to concurrently change a codebase in separate lines and reconcile their changes automatically afterwards.
However, two changes that are correct independently can introduce bugs when merged together.
We call \emph{\Problems{}} this kind of bugs.
%While VCS merging tools can detect some kinds of conflicts, some conflicts exceed their scope.
%For example, the Fragile Base Class Problem shows that a merge can succeed and the resulting codebase can compile without errors,
%The symptoms of an merge with semantical conflicts can be evident when the merging process or a test execution fails.
%However, the symptoms are not always that evident.
%In any case, it requires an effort for the integrator to detect semantical conflicts, and tools do not help.

Change impact analysis (CIA) aims at estimating the effects of a change in a codebase. 
In this paper, we propose to detect \Problems{} using CIA.
On a merge, \Approach analyzes and compares the impact of a change in its origin and destination branches.
We call the difference between these two impacts the \emph{delta-impact}.
If the delta-impact is empty, then there is no indicator of a \Problem{} and the merge can continue automatically.
Otherwise, the delta-impact contains what are the sources of possible conflicts.

%There is plenty of research on CIA techniques but, to the best of our knowledge, there is no research for the scenario described. \tincho{fix}

%In this paper, we propose a CIA technique which analyzes the dependencies source code to detect effects that were unintended by the author in the original codebase. 
%We describe an implementation of our approach and we do an empirical evaluation.


\end{abstract}




%%%%%%% SECTION %%%%%%%
\section{Introduction}

Software projects are in constant evolution.
Often, developers perform changes concurrently in a codebase, generating separate lines of development.
Version control systems (VCS) support this activity through branches, a widely used feature~\cite{Dias14b, Phil11a} in software development. 
Merge~\cite{Mens02d} (also called integration) is a fundamental operation in VCS that reconciles two (or more) branches. 
VCS can detect syntactical merge conflicts automatically.
Nevertheless, \Problems (\ie at the level of program behavior) exceed the scope of these tools.
%The Fragile Base Class Problem~\cite{Mikh98a} is an example of this kind of semantic conflicts that is present in most object-oriented languages. 
Consider, for example, a branch renaming a template method from \ct{A>>foo} to \ct{A>>bar} and another branch overriding \ct{foo} in a \ct{B} class, subclass of \ct{A}. 
The two branches can be automatically merged but the resulting code will fail to execute as intended: indeed \ct{B>>foo} will never be executed while \ct{B>>bar} is supposed to exist but does not,
Such \emph{\Problems} are not detected by current VCS. 
%In Java, the annotation \ct{@Override} would detect the problem at compile time.

%The most changes a branch has respect to other, the most likely is to have merging conflicts.
%As a consequence, merging as early as possible is considered a best-practice. 
%Nevertheless, sometimes a branch can not be integrated immediately.

%Moreover, normally a software project is not versioned as a monolithic codebase that can be compiled and executed in isolation. 
%Instead, a project depends on other projects, and other projects depend on it. 
%This fact aggravates the mentioned \emph{semantic conflict}, since 

%Moreover, consider a large open-source project that evolves with code changes that must be approved by reviewers of the community before integration.
%A developer creates a code change ($\Delta$) in a branch and requests the community to review it.
%However, since the reviewing process takes some time, when $\Delta$ is approved for integration the codebase evolved with other code change integrations.
%In this evolved codebase, $\Delta$ can have semantic conflicts, \ie effects that were not intended by the authors.
%In such case, we say that $\Delta$ is an \emph{\Problem}. 

Change Impact Analysis~\cite{Bohn96a, Li12} (CIA) is an active research field that aims at identifying the potential consequences of a change in a codebase.
Typically, CIA techniques establish \emph{dependency} relationships between the code entities of the codebase.
These relationships are used afterwards for detecting the set of entities that are impacted by a change.
The rationale is that when a code entity changes, the behavior of the \emph{dependent} entities is impacted.
Many CIA research works use the technique of computing the dependencies of a change in the original codebase where the authors created the change \cite{Petr09a, Canf05b, Hass06a, Anto00b}.

%However, to the best of our knowledge, such technique has not yet been used to solve the problem of \Problem.
%We believe this research path deserves to be explored.

%Robbes~\cite{Robb12b} points that most of the software engineering research focuses on tools and techniques for analyzing individual systems: quality assessment, defect prediction, automated test generation, impact analysis, all are techniques that aim at supporting the developer and improving the resulting software."]


This paper proposes a solution to help integrators in the detection of \Problems{} using CIA.
On a merge, \Approach analyzes and compares the impact of a change in its origin and destination branches.
We call the difference between these two impacts the \emph{delta-impact}.
If the delta-impact is empty, it means that there is no \Problem{} and the merge can continue automatically.
Otherwise, the delta-impact contains what are the sources of possible conflicts.
The contributions of this paper are the following:

\begin{itemize}
\item a description of \Problem with an example (Section \ref{sec:problem});
\item a CIA technique, named \Approach, to detect \Problems (Section \ref{sec:solution});
\item a discussion of usages of this technique (Section \ref{sec:discussion});
\item a prototype of this technique implemented in Pharo (Section \ref{sec:implementation});
\end{itemize}

\newpage
%%%%%%% SECTION %%%%%%%
\section{Problems when Merging: Semantic Conflicts} \label{sec:problem}

To show how semantic conflicts appear when merging, we start by introducing an example of the Fragile Base Class Problem~\cite{Mikh98a} (FBCP).
Consider the following logging library that implements a \ct{Log} class whose API has the methods \ct{log:}, which can record a single message into an internal collection, and \ct{logAll:}, which records multiple messages in one shot using \ct{log:}. 
The logic for adding an element to the collection of logs is only expressed inside the \ct{log:} method.
Following there is the code illustrating the most relevant points of such implementation:

\begin{code}
Object subclass: #Log
   instanceVariableNames: 'messages'.

Log \stSelector log: aMessage  
   messages add: aMessage.

Log \stSelector logAll: someMessages  
   someMessages do: [:each | self log: each ].
\end{code}

We want now to introduce a change in this library.
At some point in time, a developer starts a new branch of the library from version $A$ and implements a new feature: the \ct{FilteredLog}~(Figure~\ref{exampleMerging}). \ct{FilteredLog} is a subclass of \ct{Log} that overrides \ct{log:} to record the message only when it satisfies a filter. 
Note that \ct{FilteredLog} does not need to override \ct{Log\stSelector logAll:}.
We refer to this change as $\Delta_{F}$.
The code illustrating $\Delta_{F}$ is the following:

\begin{code}
\texttt{+} Log subclass: #FilteredLog
\texttt{+}    instanceVariableNames: 'filterBlock'.
\texttt{+}
\texttt{+} FilteredLog \stSelector log: aMessage  
\texttt{+}    (filterBlock value: aMessage) 
\texttt{+}       ifTrue: [ super log: aMessage ].
\end{code}

In parallel, the main branch of the library evolves: the method \ct{Log\stSelector logAll:} no longer uses \ct{self log:} to record each received message, but instead each message is added directly to the internal collection.

\begin{code}
\texttt{ } Log \stSelector logAll: someMessages  
\texttt{-}    someMessages do: [:each | self log: each ].
\texttt{+}    messages addAll: someMessages
\end{code}

When the integrator wants to merge $\Delta_{F}$ in the main branch, the tool does not inform any merging conflicts but the introduced feature does not work as expected. Indeed, \ct{FilteredLog} does not filter any messages when using \ct{logAll:} because this method does not use the \ct{log:} message anymore.

\begin{code}
log := FilteredLog new.
log filterBlock: [ :each | each > 0 ].
log logAll: \#(-5).
log messages isEmpty. "false ---> wrong!"
\end{code}

We can observe from this example that an integrator can merge $\Delta_{F}$ introducing a semantic conflict silently.
To detect such kind of bugs, integrators need to understand the code in a change ($\Delta$) more deeply \eg know the intention of the change, in which version was it developed.
Then, the activity of integration requires a big human effort which new tools can help to alleviate.

In a more general way, we would like a tool that helps the integrator by answering the following questions:

\begin{description}
\item[Q1.] \emph{Does a $\Delta$ produce semantic conflicts if merged in a particular version of the codebase?}
\item[Q2.] \emph{What code entities are involved in a semantic conflict that $\Delta$ produces?}
\item[Q3.] \emph{When was the change that produced a semantic conflict with a $\Delta$ integrated?}
\end{description}


\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.95\columnwidth]{MergingExample1}
\bigskip
\caption{%Overview of the Fragile Base Class Problem example. 
A developer starts a new branch of the library from version $A$ of a logging library and implements a new feature: the \ct{FilteredLog}. We name such change as $\Delta_{F}$. Before $\Delta_{F}$ is integrated into the library, a modification in the method \ct{Log\stSelector logAll:} in $B$ makes $B+\Delta_{F}$ not working.}
\label{exampleMerging}
\end{center}
\end{figure}

In general these questions are hard to answer, specially in large scale projects where developers work in parallel on the same codebase. 
Automated Testing and Continuous Integration practices could help in answering the first question. 
However, these practices depend on the coverage of the testing: the more tested is the code, the more likely the problem can be detected. 
Unfortunately, sometimes test coverage is not good enough and requires an effort that developers do not make.
Then, we pose the following research question:

\begin{center}\emph{Can CIA on origin and destination branches help to answer these questions?}\end{center}

%%%%%%% SECTION %%%%%%%
\section{Our Solution: \Approach} \label{sec:solution}

%Given a change in the codebase, Change Impact Analysis~\cite{Li12} (CIA) estimates its potential effects. 
%The main output is an impact set: a set of code entities that might be affected by the change.
%
%Traditional CIA techniques rely on static analysis of the source code to estimate \emph{dependencies} between code entities.
%If an entity is changed, the behavior of the \emph{dependent} entities can suffer unexpected effects.



% Damien 30th April:
%
%- you need short intro before 3.1
%- "this problem" which problem?
%
%- Definition 1 : you can remove the first "dependency" as the second is
%  emphasized
%
%(x)- "we focus on" no need for "only"
%
%- give an example of "other kind of dependencies"
%
%- what is "environment"
%
%(x)- "following modifications" -> "following dependency modifications"
%
%- for I2. you could add that this is because of polymorphism or late
%  binding
%
%- for I3, you could add that this is because of the super send
%
%- what do you mean by "should be kept" ?
%
%- "on the contrary" to what? Your hypothesis?
%
%- you should try to keep 'E' for Environment. You could replace A and B
%  by E1 and E2
%
%(x) - you should define what you mean by "difference". Maybe "set
%  difference" is enough
%
%(x)- "we compute" -> the algorithm computes
%
%(x)- "make the difference" -> unclear
%
%- I think you should use an enumeration list for the algorithm so we see
%  the steps clearly
%
%- you might want to reference Figure 4 before so that the reader can
%  follow the explanations on the figure

In a nutshell, we propose to detect semantic merge conflicts using CIA.
On a merge, \Approach analyzes and compares the impact of a change in its origin and destination branches.
We call the difference between these two impacts the \emph{delta-impact}.
If the delta-impact is empty, it means that there are no semantic conflicts and the merge can continue automatically.
Otherwise, the delta-impact contains what are the sources of possible conflicts.

In the following we describe our approach. 
First, we define the notions of dependency and impact. 
Then, based in such notions, we explain delta-impact.

\subsection{Dependency and Impact}

Change Impact Analysis~\cite{Bohn96a, Li12} (CIA) aims at identifying the potential consequences of a change in a codebase.
Typically, CIA techniques establish \emph{dependency} relationships between the code entities of the codebase, which they use afterwards for detecting the set of entities that are impacted by a change.
The rationale is that when a code entity changes, the behavior of the \emph{dependent} entities is impacted.
In the context of this paper, we define dependency as follows:

\begin{definition}{Dependency.}
A \emph{dependency} is the relationship between two code entities where one code entity ($source$) requires the other ($target$). We denote it $source \to target$.
%\dc{in your PhD, you will need something more formal such as a mathematical transitive relation}
\end{definition}

In the motivational example we introduced in Section \ref{sec:problem}, the \ct{FilteredLog} class depends on the \ct{Log} class because of the inheritance relationship between them.
In this paper we focus on static dependency analysis, \ie dependencies that are explicit in the source code, however we believe that \Approach can be generalized to other kinds of dependencies. We describe the dependencies of \Approach in more detail in Section~\ref{subsec:dependencies}.

%We can compute the \emph{impact} that a $\Delta$ \dc{define} has in an codebase by considering the dependencies introduced and removed on such codebase. 
%\begin{definition}{Introduced Dependencies.}
%The set of \emph{introduced} dependencies by a change $\Delta$ in a codebase $C$, denoted $D^{+}(C,\Delta)$  ...  is the $\Delta$
%We denote it $source \to target$.
%\end{definition}
Then, we define the impact of a $\Delta$ as follows:

\begin{definition}{Impact.}
The \emph{impact} of a change $\Delta$ in a codebase $C$, denoted $I(\Delta, C)$, is the set of dependencies introduced or removed in $C$ after applying $\Delta$. 
%Formally, $I(\Delta, C) = \{ - s \to t : s \to t \in D(C) \setminus D(C + \Delta) \} \cup \{ +d : d \in D(C + \Delta) \setminus D(C) \}$.
%Formally, $I(\Delta, C) = \{ -d : d \in D(C) \setminus D(C + \Delta) \} \cup \{ +d : d \in D(C + \Delta) \setminus D(C) \}$.
%Formally, $I(\Delta, C) = \{ I^{-}_{d} : d \in D(C) \setminus D(C + \Delta) \} \cup \{ +d : d \in D(C + \Delta) \setminus D(C) \}$
\end{definition}

In the motivational example, the impact of $\Delta$ in its origin branch includes the following dependency modifications (Figure~\ref{exampleMergingDependencies}):

\begin{center}
\begin{minipage}[t]{0.85\columnwidth}
\begin{description}
\item [$i_1$] Introduction of an inheritance dependency from \ct{FilteredLog} to \ct{Log}.
\item [$i_2$] Introduction of a message send dependency from \ct{Log>>logAll:} to \ct{FilteredLog>>log:}.
\item [$i_3$] Introduction of a message send dependency from \ct{FilteredLog>>log:} to \ct{Log>>log:}.
\end{description}
\end{minipage}
\end{center}

\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.72\columnwidth]{MergingExampleDependencies}
\smallskip
\caption{Impact of $\Delta_{F}$ in $A$. In the origin branch, $\Delta_{F}$ introduces three dependencies: one corresponding to an inheritance relationship, and the others corresponding to message sends.}
\label{exampleMergingDependencies}
\end{center}
\end{figure}

\subsection{\Approach}

In the example~(Figure~\ref{exampleDependencies}), the comparison of the impact of $\Delta_{F}$ in origin and destination branches shows that the dependency from \ct{Log>>logAll:} to \ct{FilteredLog>>log:} is missing in the destination branch.
Precisely, the cause of the semantic conflict in the example is the change in \ct{Log>>logAll:}, which no longer invokes \ct{FilteredLog>>log:}.

We observe that the impact of a $\Delta$ contains a set of relationships between code entities in a particular version of code.
Informally, we can think about this impact as a set of constraints that have to be satisfied for the code to work as expected.
Then, we pose the following hypothesis:

\bigskip
\begin{minipage}[t]{0.95\columnwidth}
\begin{center}\emph{A semantic conflict appears when the set of dependencies that a $\Delta$ introduces (or removes) into its origin branch is different from those introduced (or removed) when merging such $\Delta$ in the destination branch.}\end{center}
\end{minipage}
\bigskip

\begin{figure}[ht]
\begin{center}
\smallskip
\includegraphics[width=0.68\columnwidth]{MergingExampleMissingImpact}
\smallskip
\caption{\textbf{Delta-impact of $\Delta_{F}$ from $A$ to $B$.} Comparison of the impact of $\Delta_{F}$ in both $A$ and $B$. The dependency from \ct{Log>>logAll:} to \ct{FilteredLog>>log:} is missing in $B$.}
\label{exampleDependencies}
\end{center}
\end{figure}

In other words, if there are missing or extra dependencies in the destination branch, this could mean that $\Delta$ has a different meaning than the one intended by its author. 
On the contrary, if the dependencies are the same the change may have the same effects.
Then, we define \emph{delta-impact} as follows:
%~(Figure \ref{DeltaImpactBuildOverview}).

%\begin{figure}[ht]
%\begin{center}
%\includegraphics[width=0.6\columnwidth]{DeltaImpactBuildOverview}
%\bigskip
%\caption{\textbf{Calculation of the delta-impact of $\Delta$ from $A$ to $B$.} The algorithm starts by building the environment $A+\Delta$, which is derived from the input. After, the algorithm builds the dependency graphs (DG) of both environments. Finally, the algorithm builds the impact by calculating the difference between both DGs.}
%\label{DeltaImpactBuildOverview}
%\end{center}
%\end{figure}


%In the following section we propose to detect possible issues of merging a $\Delta$ by analyzing its impact in the environment where the author originally developed it, and its impact in the environment where the integrator has to merge it. A difference found between such analyses indicates a possible issue.



\begin{definition}{Delta-Impact.}
The \emph{delta-impact} of a change $\Delta$ with origin branch $A$ and destination branch $B$, denoted $DI(\Delta, A, B)$, is the symmetric difference\footnote{the symmetric difference between two sets includes only the elements that belong to one of such sets but not to both.} between the set of impacts of $\Delta$ in $A$ and the impact of $\Delta$ in $B$.
%Formally, $DI(\Delta, A, B) = \{i \mid (i \in I(\Delta, A) \land i \notin I(\Delta, B))) \lor (i \notin I(\Delta, A) \land i \in I(\Delta, B))) \}$.
\end{definition}

To compute the delta-impact of $\Delta$, we obtain the impact of $\Delta$ in the origin and destination branches, and then we compute the symmetric difference between the two impacts. 
In the example (Figure~\ref{exampleDeltaImpact}), the impact $I(\Delta_{F}, A)$ yields the set $\{i_1, i_2, i_3\}$, while $I(\Delta_{F}, B)$ yields the set $\{i_1, i_3\}$.
Then, $DI(\Delta_{F}, A, B)$ results in the set $\{i_2\}$, because $i_2$ is missing in the destination branch $B$.
In this context, a tool that computes and shows the delta-impact of $\Delta_{F}$ to the integrator would answer the questions Q1 and Q2 that we defined in Section~\ref{sec:problem}.

\begin{figure}[ht]
\small

\[
\begin{array}{ccrclc}
\multicolumn{5}{l}{I(\Delta_{F}, A):}\\
& + & \ct{FilteredLog} & \rightarrow & \ct{Log} & (i_1) \\
& + & \ct{Log>>logAll:} & \rightarrow & \ct{FilteredLog>>log:} & (i_2) \\
& + & \ct{FilteredLog>>log:} & \rightarrow & \ct{Log>>log:} & (i_3) \\
\\
\multicolumn{5}{l}{I(\Delta_{F}, B):}\\
& + & \ct{FilteredLog} & \rightarrow & \ct{Log} & (i_1) \\
& + & \ct{FilteredLog>>log:} & \rightarrow & \ct{Log>>log:} & (i_3) \\
\\
\multicolumn{5}{l}{DI(\Delta_{F}, A, B) = I(\Delta_{F}, A) \ominus I(\Delta_{F}, B):}\\
& + & \ct{Log>>logAll:} & \rightarrow & \ct{FilteredLog>>log:} & (i_2) \\
\end{array}
\]

\caption{\textbf{\Approach} $I(\Delta_{F}, A)$ is the original impact of $\Delta_{F}$, while $I(\Delta_{F}, B)$ is the destination impact. $DI(\Delta_{F}, A, B)$ is the delta-impact of $\Delta_{F}$ in the destination branch, which shows that a dependency introduction is missing ($i_2$).}
\label{exampleDeltaImpact}
\end{figure}



\section{Applicability}
\label{sec:discussion}

In this section we describe concrete scenarios where we would like to validate \Approach (in future works).
Since our plan is to validate our approach with Pharo community,  
we present these scenarios in terms of Pharo.

\subsection{Aged Code Changes}\label{subsec:aged}

The codebase of a large open-source project like Pharo evolves through code changes that developers submit.
When a developer submits a code change, this change must pass a reviewing process before an integrator merges it into the main development branch.
Since this reviewing process takes some time and code changes are integrated every day, when the integrator has to merge an approved code change, the current Pharo codebase may be different than the codebase where the author of the change worked.

In this situation, \Approach can help Pharo integrators to discover semantic conflicts on the merge.
Given a code change $\Delta$ submitted by a developer, \Approach can answer:
\begin{center}
``Is the impact of $\Delta$ in the current Pharo the same as the impact in the Pharo where $\Delta$ was originally created?''
\end{center}

%Requirements: 
%The codebase is the whole set of packages in Pharo. 
%Thus, the tool must manipulate a big number of code entities.

\subsection{Software Migration}\label{subsec:migration}

Often, when the codebase of a project changes, other projects that depend on it need to be migrated.
This change propagation is known as ripple effect~\cite{Yau78}.
Ripple effects are problematic because a small change in a project can have a very large impact on other projects.
Additionally, sometimes a code that needs migration remains undiscovered for a long time due to low test coverage.

%Now, lets think this scenario in terms of our approach, with an example.
%To think this scenario in terms of Pharo, 
We can illustrate this scenario by rephrasing the FBCP example used in Section~\ref{sec:problem}. 
%Let's suppose that a developer, who is working in Pharo version $A$, creates the \ct{FilteredLog} class into his project.
%The superclass of \ct{FilteredLog} is \ct{Log}, a class provided by Pharo.
Let's suppose that a developer works in a project in Pharo version $A$.
The system provides the class \ct{Log}, which the developer extends in his project by creating the subclass \ct{FilteredLog}.
One year later, a new stable version of Pharo is available: version $B$. 
Among plenty of changes in Pharo $B$, the method \ct{Log>>logAll:} has been modified like in the FBCP example. 
As before, a bug appears in the method \ct{logAll:} when invoked in an instance of \ct{FilteredLog}.
Note that when the developer loads the \ct{FilteredLog} class in Pharo $B$, the system does not raise any load or compilation error: it is another form of the \Problem.
The developer will probably have to debug his project to find that the change in \ct{Log>>logAll:} is the responsible.
If a tool would have informed the developer that \ct{Log>>logAll:} changed, then he could save time.

We can pose this problem in terms of our approach. 
When the \ct{FilteredLog} package is loaded in Pharo $A$, some dependencies are introduced between code entities of \ct{FilteredLog} and Pharo.
This is what we have defined as impact.
When the package is loaded in Pharo $B$, the impact is different: $i_{2}$ is missing (Figure~\ref{exampleDeltaImpact}).
%a different impact can help the developers to spot what code entities in the package need an update. 
In general terms, \Approach can help developers to answer the following question:
\begin{center}
%\item ``Is the impact of loading this package the same in Pharo $A$ and $B$?''
%\item[] 
``Which Pharo code entities with impact on my project changed from Pharo $A$ to $B$?''
\end{center}

%\subsection{Other Scenarios}
%
%We think \Approach can also apply in the following scenarios:
%\begin{description}
%\item[Assisting Cherry-picking] Cherrypicking is the merge of a selection of code changes from a branch to another. 
%\item[Pre-Commit Alerts] Cherrypicking is the merge of a selection of code changes from a branch to another. 
%\end{description}

\subsection{Requirements} \label{subsec:requirements}

The main requirement of any CIA technique is a high precision and a high recall~\cite{Li12}. 
A high precision means that a technique finds substantially more relevant results than irrelevant, while high recall means that a technique finds most of the relevant results.

However, we extract some additional requirements for the implementation of \Approach from the scenarios presented above in this section:

\begin{description}
\item[Isolation from tool's environment.]
For supporting ``Software Migration'', the implementation needs to compute dependencies of code entities as if they were loaded in some arbitrary Pharo version, independently of the Pharo version where the tool is actually running.

%\item[Several environments.]
%The implementation needs to compute dependencies of more   should have reasonably good performance in space (of several environments simultaneously).

\item[Usable in real use cases.] Since we aim at building a tool that real developers can evaluate, the implementation should compute the dependencies in a reasonable time.

\end{description}



\section{Implementation}
\label{sec:implementation}

We start this section doing an overview of the main characteristics of our prototype implementation of \Approach.
Some design decisions are consequence of the requirements stated in Section~\ref{subsec:requirements}.
\begin{description}

\item[Static code analysis.] 
We use default Pharo support for performing static code analysis.
For example, the \ct{AST-Core} package provides support for visiting the \emph{abstract syntax tree} of methods and collecting dependencies.

\item[Light-weight and polymorphic code metamodel.]
We implemented \ct{RingFicus}, a metamodel for Pharo code entities.
It provides first-class representations for class, method, instance variable, etc.
RingFicus allows to model code either internal or external to the current Pharo environment to browse them, query them, analyze them, as if they were loaded in the system.

%For example, RingFicus supports importing and browsing Monticello packages as if they were loaded in the system. 
%We can also do some other static code analyses on a RingFicus model.

%RingFicus supports the manipulation of the code entities of several Pharo versions.
%Preliminar tests show that our prototype can read the code entities of several Pharo 5 environments in a Pharo 4.

%Computing the dependencies directly from a Ficus metamodel representation is not compatible with \ct{AST-Core}. 
%RingFicus code entities provide polymorphism with Pharo metamodel entities, like in Ring~\cite{Uqui11a}.

\end{description}

%We built a prototype that works as showed in the example.
%Supports importing from Monticello and Git to this model.

%Figure~\ref{RingFicusInfrastructure}

%In the rest of this section we explain how the prototype computes the dependencies and impact.

%Figure~\ref{RingFicusModel}
%\begin{figure}[ht]
%\begin{center}
%\includegraphics[width=0.95\columnwidth]{RFiModel}
%\bigskip
%\caption{FicusRing metamodel}
%\label{RingFicusModel}
%\end{center}
%\end{figure}

%\begin{figure}[ht]
%\begin{center}
%\includegraphics[width=0.65\columnwidth]{Importing}
%\caption{Support for importing RingFicus objects.}
%\label{RingFicusInfrastructure}
%\end{center}
%\end{figure}

\subsection{Computing Dependencies}\label{subsec:dependencies}

\Approach requires to compute dependencies between source code entities. In our solution such entities are classes, metaclasses, instance and class variables, traits, class-traits and methods.
The relationships that we consider as dependencies in \Approach are the following:

\begin{description}
\item[Inheritance:] A dependency from a class to its superclass.
\item[Trait Usage:] A dependency from a class, metaclass, trait, or class-trait to all traits in its \emph{trait composition}.
\item[Variable Access:] A dependency from a method in a class or metaclass that accesses (read or write) an instance or class variable, to the accessed variable. 
\item[Message Send:] A dependency from a method including a message-send sentence, to all the possible methods that are invoked. 
Due to the absence of type information in the language, in the general case the algorithm uses the selector of a message-send to look up for all the implementors in the codebase.
However, in the case of \ct{self}-sends and \ct{super}-sends the algorithm refines its look up for obtaining more precise dependencies.
\end{description}

For testing our prototype, we implemented \ct{DependencyMiner}, which iterates over all the source code entities of a Pharo environment collecting the dependencies.
Each dependency is an association $source \to target$.

\subsection{Computing Impact and Delta-Impact}

For the computation of the impact of $\Delta$ in an environment (Figure~\ref{ImpactBuildOverview}), the algorithm starts by building the codebase $C+\Delta$.
Then, the prototype computes the dependency sets of each environment using the \ct{DependencyMiner}, described above.
Finally, the prototype the impact and the delta-impact by performing \ct{Collection} operations.

%The impact of applying a change ($\Delta$) in a codebase ($C$), \ie $I(\Delta, C)$, is computed by the \emph{Impact Builder} algorithm.
%Figure~\ref{ImpactBuildOverview} illustrates the process.
%The algorithm starts by building the codebase $C+\Delta$, which is derived from the input. 
%After, the algorithm computes the sets of dependencies of both codebases, using the \emph{Dependencies Miner} described in the previous subsection.
%Finally, the algorithm builds the impact by computing the symmetric difference between such dependency sets.


\begin{figure}[ht]
\begin{center}
\includegraphics[width=0.5\columnwidth]{ImpactBuildOverview}
\bigskip
\caption{\textbf{Computation of the impact of $\Delta$ in $C$.} The algorithm starts by building the codebase $C+\Delta$. After, the algorithm computes the dependency sets of each codebase ($D(C)$ and $D(C+\Delta)$). Finally, the algorithm computes the impact by finding the symmetric difference between $D(E)$ and $D(E+\Delta)$.}
\label{ImpactBuildOverview}
\end{center}
\end{figure}

%Figure~\ref{DependenciesModel}
%
%\begin{figure}[ht]
%\begin{center}
%\includegraphics[width=0.5\columnwidth]{DependenciesModel}
%\bigskip
%\caption{Model of Dependencies}
%\label{DependenciesModel}
%\end{center}
%\end{figure}




%%%%%%% SECTION %%%%%%%
%\section{Discussion}
%\label{sec:discussion}
%
%\subsection{Measuring Impact using Dynamic Dependencies}
%
%usar symmetric diff o no (todo junto / aparte)
%
%\subsection{Alternatives to the \Approach approach}
%-missing/extras 
%- update
%* es un solo salto de dependencias
%

%\subsection{Applicability}
%
%- explicar distintos casos donde creo que podria ser aplicable, explicando siempre que la evaluacion queda para future work.
%
%\begin{description}
%\item[porting] Porting code between platform-version branches (MyProduct-Pharo30 and MyProduct-Pharo40)
%\item[aged bug fixes] Integrating collaborations that can be outdated
%  - slices de pharo, dar ej reales
%  - lo mismo en github con pulllreqs.
%\item[cherrypicking] Cherrypicking changes between long-term forks (Pharo and Squeak).
%\end{description}


%%%%%%% SECTION %%%%%%%
\section{Related Work}

\paragraph{Change Impact Analysis.}
In an exhaustive survey~\cite{Li12} about CIA, Li \etal analyze 30 publications from 1997 to 2010 and identified 23 code-based CIA techniques. 
The study characterizes the CIA techniques, and identifies key applications of CIA techniques in software maintenance.
Typically, CIA techniques establish \emph{dependency} relationships between the code entities of the codebase, which they use afterwards for detecting the set of entities that are impacted by a change.
The rationale is that when a code entity changes, the behavior of the \emph{dependent} entities is impacted. 
The techniques to identify dependencies in a codebase are typically classified into static and dynamic.
The static techniques identify the dependencies using static code analysis~\cite{Wels84a, Sun10a}, while dynamic techniques~\cite{Kore98a, Apiw05a} collect data from program execution.
There are, as well, mixed techniques~\cite{Cai15a} which combine both techniques.
%The principal drawbacks of CIA techniques are low accuracy and/or computationally too expensive.
\Approach is orthogonal to the technique to identify dependencies, besides our prototype works with a static CIA technique. 

%Reenacting. Many CIA research works use the technique of computing the dependencies of a change in the original codebase where the authors created the change. (\eg \cite{Petr09a, Canf05b, Hass06a, Anto00b}).


\paragraph{Merging.}
The \Problems have been studied before under different names.
Mens~\cite{Mens02d} describes this problem in his survey of code merging.
In this work, the author remarks that most approaches to software merging have been validated on imperative programming languages and it is not trivial to port these approaches to the object-oriented paradigm, due to late binding and polymorphism in object-oriented programming languages.
\tincho{add more refs -> Good references in Veronica's PhD}
\tincho{link with our approach}


\paragraph{Ring Metamodel.}% and JET tools}
Ring~\cite{Uqui11a}\cite{Uqui10b} is a source code meta-model that serves as a unified infrastructure for building tools in Pharo.
While Ring has proven efficacy for dependency analysis tools~\cite{Uqui14a, Uqui12b}, we found some limitations that driven us to reimplement our own RingFicus package.
In our early tests, Ring did not fulfill the requirements we described in Section~\ref{sec:discussion}.
Ring code entities did not ensure isolation from tool's environment, and they were not efficient to represent a whole Pharo environment.

%Such limitations are the following:
%\begin{itemize}
%\item Inefficient in space for representing similar environments.
%  Metamodel entities in Pharo have circular references. 
%  For example, a method has a pointer to the behavior that defines it, which, in turn, points to the System Dictionary.
%  Given Ring entities are polymorphic with real metamodel entities, they reproduce the mentioned circular references.
%\item Interference from tool's environment.
%  In many cases, Ring entities access to the tool's environment for resolving some queries. 
%  For example, this is the case in \ct{RGMethodDefinition>>messages}, which answers the tool's environment for answering.
%%  In general, this lack of concept of "closed-universe" in Ring's implementation makes it difficult to ensure that result of queries are not polluted by tool's environment. This was not the original intention of Ring. 
%\end{itemize}

%For example, a \ct{RGClass} represents a Pharo class.
%JET~\cite{Uqui14a}\cite{Uqui12b} is a toolset built on top of Ring that aims at helping  an integrator to understand to dependencies between the changes of the repository.



%\subsection{Jet}
%\tincho{remove?}
%JET~\cite{Uqui14a}\cite{Uqui12b} is a toolset that aims at helping the developer to understand dependencies between commits in the repository of a codebase. 
%"The JET tools offer integrators a means to access their information needs in order to answer questions they ask themselves when integrating changes."
%
%JET presents suffers a drawback in our scenario. 
%It uses the current tools' \emph{system dictionary}["explain?"] for creating an environment.
%For example, the user can compare the source code of a method with the one in the system dictionary.
%The syntax highlighting will mark in in red an instance variable that existed in the original environment[platform?] where the commit was done, but that does not exist in the tool's system dictionary.



%%%%%%% SECTION %%%%%%%
\section{Conclusion and Future Perspectives}

In this paper, we proposed a solution to help integrators in the detection of \Problems{} using CIA.
On a merge, \Approach analyzes and compares the impact of a change in its origin and destination branches.
We call the difference between these two impacts the \emph{delta-impact}.
If the delta-impact is empty, it means that there is no \Problem{} and the merge can continue automatically.
Otherwise, the delta-impact contains what are the sources of possible conflicts.

In short, this paper makes the following contributions:
\begin{itemize}
\item a description of \Problem with an example;
\item a CIA technique, named \Approach, to detect \Problems; \tincho{novel?}
\item a discussion of concrete scenarios to validate this technique in future work;
\item a prototype of this technique implemented in Pharo.
\end{itemize}


%%%%%%% SECTION %%%%%%%
\section*{Acknowledgements} We would like to thank Guille Polito, Santiago Bragagnolo and Lucas Godoy for their support during this work. This work was supported by Ministry of Higher Education and Research, Nord-Pas de Calais Regional Council. 


\bibliographystyle{plain}
\bibliography{rmod,others}

\end{document}


main.bbl
\begin{thebibliography}{10}

\bibitem{Anto00b}
Giuliano Antoniol, Gerardo Canfora, Gerardo Casazza, and Andrea {De Lucia}.
\newblock Identifying the starting impact set of a maintenance request: {A}
  case study.
\newblock In {\em European Conference on Software Maintenance and Reengineering
  (CSMR 2000)}, pages 227--230, 2000.

\bibitem{Apiw05a}
Taweesup Apiwattanapong, Alessandro Orso, and Mary~Jean Harrold.
\newblock Efficient and precise dynamic impact analysis using execute-after
  sequences.
\newblock In {\em Proceedings of the 27th International Conference on Software
  Engineering}, ICSE '05, pages 432--441, New York, NY, USA, 2005. ACM.

\bibitem{Bohn96a}
Shawn~A. Bohner and Robert~S. Arnold.
\newblock {\em Software Change Impact Analysis}.
\newblock IEEE Computer Society Press, 1996.

\bibitem{Cai15a}
Haipeng Cai and Ra{\'{u}}l~A. Santelices.
\newblock A framework for cost-effective dependence-based dynamic impact
  analysis.
\newblock In {\em 22nd {IEEE} International Conference on Software Analysis,
  Evolution, and Reengineering, {SANER} 2015, Montreal, QC, Canada, March 2-6,
  2015}, pages 231--240, 2015.

\bibitem{Canf05b}
Gerardo Canfora and Luigi Cerulo.
\newblock Impact analysis by mining software and change request repositories.
\newblock In {\em Proceedings of the 11th IEEE International Software Metrics
  Symposium}, METRICS '05, pages 29--, Washington, DC, USA, 2005. IEEE Computer
  Society.

\bibitem{Dias14b}
Martin Dias, Ver\'onica Uquillas-Gomez, Damien Cassou, and St\'ephane Ducasse.
\newblock Software integration questions: A quantitative survey.
\newblock Technical report, INRIA Lille, 2014.

\bibitem{Hass06a}
Ahmed~E. Hassan and Richard~C. Holt.
\newblock Replaying development history to assess the effectiveness of change
  propagation tools.
\newblock {\em Empirical Softw. Engg.}, 11(3):335--367, September 2006.

\bibitem{Kore98a}
Bogdan Korel and Juergen Rilling.
\newblock Dynamic program slicing methods.
\newblock {\em Information {\&} Software Technology}, 40(11-12):647--659, 1998.

\bibitem{Li12}
Bixin Li, Xiaobing Sun, Hareton Leung, and Sai Zhang.
\newblock A survey of code-based change impact analysis techniques.
\newblock {\em Software Testing, Verification and Reliability}, 23(8):613--646,
  2013.

\bibitem{Mens02d}
T.~Mens.
\newblock A state-of-the-art survey on software merging.
\newblock {\em IEEE Transactions on Software Engineering}, 28(5):449--462,
  2002.

\bibitem{Mikh98a}
Leonid Mikhajlov and Emil Sekerinski.
\newblock A {Study} of the {Fragile} {Base} {Class} {Problem}.
\newblock In {\em Proceedings of the European Conference on Object-Oriented
  Programming}, number 1445 in Lecture Notes in Computer Science, pages
  355--383. Springer-Verlag, 1998.

\bibitem{Petr09a}
Maksym Petrenko and V\'aclav Rajlich.
\newblock Variable granularity for improving precision of impact analysis.
\newblock In {\em ICPC}, pages 10--19. IEEE Computer Society, 2009.

\bibitem{Phil11a}
Shaun Phillips, Jonathan Sillito, and Rob Walker.
\newblock Branching and merging: An investigation into current version control
  practices.
\newblock In {\em Proceedings of the 4th International Workshop on Cooperative
  and Human Aspects of Software Engineering}, CHASE '11, pages 9--15, New York,
  NY, USA, 2011. ACM.

\bibitem{Sun10a}
Xiaobing Sun, Bixin Li, Chuanqi Tao, Wanzhi Wen, and Sai Zhang.
\newblock Change impact analysis based on a taxonomy of change types.
\newblock In {\em Proceedings of the 34th Annual {IEEE} International Computer
  Software and Applications Conference, {COMPSAC} 2010, Seoul, Korea, 19-23
  July 2010}, pages 373--382, 2010.

\bibitem{Uqui12b}
Ver\'{o}nica Uquillas~G\'{o}mez.
\newblock {\em Supporting Integration Activities in Object-Oriented
  Applications}.
\newblock PhD thesis, Vrije Universiteit Brussel - Belgium \& Universit\'{e}
  Lille 1 - France, October 2012.

\bibitem{Uqui10b}
Ver\'onica Uquillas~G\'omez, St\'ephane Ducasse, and Theo D'Hondt.
\newblock Meta-models and infrastructure for smalltalk omnipresent history.
\newblock In {\em Smalltalks'2010}, 2010.

\bibitem{Uqui11a}
Ver\'onica Uquillas~G\'omez, St\'ephane Ducasse, and Theo D'Hondt.
\newblock Ring: a unifying meta-model and infrastructure for {S}malltalk source
  code analysis tools.
\newblock {\em Journal of Computer Languages, Systems and Structures},
  38(1):44--60, April 2012.

\bibitem{Uqui14a}
Ver\'onica Uquillas~G\'omez, St\'ephane Ducasse, and Andy Kellens.
\newblock Supporting streams of changes during branch integration.
\newblock {\em Journal of Science of Computer Programming}, 2014.

\bibitem{Wels84a}
M.~Welser.
\newblock Program slicing.
\newblock {\em IEEE Transactions on Software Engineering}, pages 352--357,
  1984.

\bibitem{Yau78}
Stephen~S. Yau, J.~S. Collofello, and T.~MacGregor.
\newblock Ripple effect analysis of software maintenance.
\newblock In {\em The IEEE Computer Society's Second International Computer
  Software and Applications Conference}, pages 60--65. IEEE Press, nov 1978.

\end{thebibliography}
