-Version control systems (VCS) are widely used to manage the history of code bases. These histories in turn provide opportunities for research. Researchers expect the commits in these version control systems to be atomic. That is, each commit performs one task. This is however not always the case. To remedy this, we propose a commit untangling technique using program slicing. In particular, we posit that all related changes are part of the same program slice. To do so, we perform program slicing on changes. Preliminary results using intra-procedural slicing have proven to be encouraging. We are currently working on expanding our work to be inter-procedural.
Version control systems (VCS) are widely used to manage
the history of code bases. Prominent examples include Git,
SVN, or Mercurial. A developer may “save” their changes
into units called commits. Best practice suggests each commit
should only contain changes related to one task. Such commits
are called atomic commits [
However, developers do not necessarily follow the best
practice of creating only atomic commits [
Tangled commits occur on a regular basis. A study by
Herzig et al. found that up to 15% of Java bug fixes contain
tangled changes [
Tangled commits lead to problems on many fronts. We
provide four examples. A developer will have problems reverting
particular changes if they are a part of a bigger commit.
A developer may also have problems integrating particular
changes from another developer if the desired change is part of
many different changes in a tangled commit. A code reviewer
will have a harder time understanding larger commits of
unrelated changes [
In light of these difficulties, we propose an automated
commit untangling technique. Our technique employs program
slicing around changes. Program slicing is a technique to
answer questions about the influence of program statements
on other program statements [
Our technique consists of four major parts. First, the commit is distilled into fine-grained changes to the program’s abstract syntax tree (AST). Second, a program dependence graph of the program is created. Third, a slice of the program dependence graph is produced for every fine-grained change. Finally, changes are grouped by means of the slices and the commit is partitioned accordingly. We have implemented our technique to work on Java programs. The rest of this section provides further detail into each of the four steps.
For the first step, we make use of ChangeNodes [
For the second step, we make use of TinyPDG [
In the third step, our technique performs forward and
backward slicing on the program dependence graph. This is
done for every distilled fine-grained change obtained in step
one. Thus for every change ci a slice S(ci) is obtained.
We implemented the intra-procedural slicing algorithm as
described by Horwitz et al. [
Finally, our technique considers the following relation R between changes. Changes ci and cj are related (notation: ciRcj ) if and only if ci 2 S(cj ) _ cj 2 S(ci). By definition of how slicing works, this relation is reflexive. The relation is also clearly symmetric due to its symmetric definition. The relation is however not necessarily transitive. We cannot state that if ciRcj and cj Rck, then ciRck. Consider for this the following simplified situation. cj is part of the root node of a PDG with two children. ci is part of one of the child nodes. ck is part of the other child node. Slicing in this situation results in S(ci) = {ci, cj }, S(cj ) = {ci, cj , ck}, and S(ck) = {cj , ck}. Then ciRcj and cj Rck, but ¬(ciRck). The relation R is thus not an equivalence relation. Instead, we partition the set of changes into subsets by means of the following steps. 1) If a change is not in relation with any change in any of the existing subsets, create a new subset with that change in it. 2) If a change is in a relation with (an) element(s) of exactly one existing subset, place the change in that subset. 3) If a change is in a relation with two (or more) elements of different subsets, join the subsets together and add the change to it.
The last step fakes transitivity and effectively “widens” the relation R: more changes are considered related than they would be by our original definition of R. In terms of these subsets, we rephrase our hypothesis as: A commit is atomic if and only if our technique does not split up the commit into different subsets of changes.
To evaluate our hypothesis, we make use of a dataset of
five Java programs as used by Herzig et al. in [
We used this dataset to perform a preliminary evaluation of our hypothesis and technique. This preliminary evaluation has one obvious limitation. Due to the current implementation of our technique being intra-procedural, only atomic and tangled commits affecting just one method could be analysed. This limits the number of commits that can be analysed, the large majority of commits cover more than one method. In the case of the Jaxen project, no commits are left to be analysed. This limitation will be solved by our (current and) future work in which we are expanding the implementation to work interprocedurally. The setup of our evaluation will remain the same for the inter-procedural evaluation.
We apply our technique to every atomic and tangled commit affecting just one method. We consider three separate outcomes for the analysis of a commit, regardless of it being atomic or tangled.
1) The commit is correctly identified as atomic or tangled.
Our technique and the dataset agree on what kind of commit it is. 2) The commit is not correctly identified. Our technique identified the commit as atomic/tangled while the dataset calls the commit tangled/atomic respectively. 3) No result. This happened when the memory overhead made the analysis crash. We have not yet played around with this overhead in order to solve or analyse it.
In the case of atomic commits, the results are promising. For each of the projects except JRuby, the ratio of correctly analysed atomic commits is larger than 90%. For JRuby nearly 20% of commits could not be analysed. Incorrectly identified commits happened largely through statements like throw or catch not being supported by TinyPDG.
Our technique falters on certain types of tangled commits. Except for the GWT project, more tangled commits were incorrectly identified as atomic than they were correctly identified as tangled. However, the large majority of these incorrect identifications are due to formatting changes or changes to comments. Our technique does not take formatting nor comments into account, only code. As such, a commit handling both one code related task and one formatting task would be classified as tangled in the dataset, but identified as atomic by our technique.
We are currently in the process of making the implementation of our technique inter-procedural. To do so, we need to make two major changes.
First, our program dependence graph needs to consider the
entire program. Rather than a procedure dependence graph, we
require a system dependence graph (SDG) or class dependence
graph (ClDG). To achieve this, we need to extend TinyPDG to
work inter-procedurally. The main hurdle here is creating the
summary edges via the algorithm as described in [
Second, our slicer needs to be adjusted to work on the
interprocedural system dependence graph. These adjustments are
also described by [
Once our implementation works inter-procedurally, we will perform the evaluation described in section III again.
V. CONCLUSION
We wanted to untangle commits performing more than one task. For this, we considered the hypothesis that related changes belong to one and the same program slice. We created a first implementation to test this hypothesis. This implementation works intra-procedurally. Despite this limitation, initial results are promising. Incorrect identifications happen largely either due to parts of the program our implementation does not handle (e.g., throw statements) or due to formatting and comment changes which our technique does not consider. We are currently working on expanding the implementation of our technique to work inter-procedurally. Once this is done, we will redo the evaluation with the complete dataset.
Ward Muylaert is an SB PhD fellow at FWO, project number 1S64317N.