Traditional algorithms for detecting di erences in source code focus on di erences between lines. As such, little can be learned about abstract changes that occur over time within a project. Structural di erencing on the program's abstract syntax tree reveals changes at the syntactic level within code, which allows us to further process the di erences to understand their meaning. We propose that grouping of changes by some metric of similarity, followed by pattern extraction via antiuni cation will allow us to identify patterns of change within a software project from the sequence of changes contained within a Version Control System (VCS). Tree similarity metrics such as a tree edit distance can be used to group changes in order to identify groupings that may represent a single class of change (e.g., adding a parameter to a function call). By applying antiuni cation within each group we are able to generalize from families of concrete changes to patterns of structural change. Studying patterns of change at the structural level, instead of line-by-line, allows us to gain insight into the evolution of software.
Version control systems (VCS's) track the evolution of software over time in the form of a sequence of changes to the plain text representation of the code. We would like to be able to characterize the changes to les in a software project according to the type of change that they represent. The ability to map these changes to the syntax of the language, instead of its raw text representation, will allow them to be understood in terms of the language constructs themselves. Doing so will allow us to identify patterns of changes at the abstract syntax level, separate from syntax neutral changes to the text such as layout variations. As a result, the interpretation of changes is made unambiguous given the de nition of the abstract syntax of the language.
Finding common patterns for the changes to a source le gives us the ability to understand, at a higher level, what sorts of revisions are happening. Detecting simple changes, such as semaphore handling changes in system-level software, we may think to use a textual search tool, such as grep, to search the source code for functions related to semaphores. Such tools are unable to easily identify more complex patterns though that have no single textual representation, such as instances of semaphore handling calls being made within conditionals where the format of the conditional can vary. Structure aware searching would be necessary in this case, as treating the program as raw text ignores important syntactic structure.
In an even more complicated situation, a programmer may be faced with a code base that they are unfamiliar with. In this case, the programmer may not know a-priori what kinds of structures are important to look for related to a certain kind of change. Here, we would like to use the di erences that are recorded in the VCS during the period of time when the change of interest was being performed to discover the structural patterns that represent the high level structure of the changes. In this way, our goal is to not provide simply a sophisticated search tool, but to provide a method for identifying patterns of code changes over a period of time.
Our contributions towards this goal presented in this paper are:
We show that structural di erencing algorithms that operate on the abstract syntax tree (AST) of a language can be used to map text di erences stored in a VCS to a form where the syntactic meaning of changes can be reasoned about.
We show that the antiuni cation algorithm that seeks the \least general generalization" of a set of trees can be used to map changes considered to be su ciently similar to a meaningful generalized change pattern. We show that a thresholded tree similarity metric derived from a tree edit distance score provides a useful grouping mechanism to de ne the notion of \su ciently similar".
In this paper, we brie y describe the building blocks of our work and show preliminary results of this methodology as applied to version control repositories for open source projects available online. The projects studied in this paper are ANTLR1 and Clojure2, both written in Java. 1.1
We would like to be able to take existing software projects and use the history stored in the VCS to answer questions which may be important to software developers, software project managers, language designers, and static analysis tools.
Language designers may want to know whether speci c syntactic constructs would make the language more productive for users. Taking an example from Java, we might consider the addition of the for-each loop construct. This feature could be partially justi ed by doing an analysis of existing source code to determine that most for-loops iterate over an entire collection. To strengthen this argument, it would be insightful to know what is the impact of maintaining the code without for-each. For example, if refactoring the code commonly leads to editing the bounds to match the collection used, then the argument in favor of adding for-each is strengthened, as now it helps to prevent a class of bugs where programmers forget to update the bounds. We demonstrate the detection of loop patterns within ANTLR in Section 3.2.
Software developers joining a new project or team are expected to learn the source code that they will be working with. We would like to provide these programmers with tools that aid them in this task by allowing them to see what types of changes other team members have made in the past. Software developers may also want to compare the changes that happen in response to related bugs, hoping to nd opportunities to improve software quality, either by searching for buggy patterns in the source code or making a tool to detect the pattern in new code. We demonstrate the detection of generic patterns within the Clojure compiler in Section 3.3.
We believe there are many uses for this approach beyond the ones demonstrated in this paper. Consider a problem that has been faced by many projects in the last decade|the challenge of migrating to utilize multicore processors. A manager who is leading a large software project may want to answer important questions to help inform future development: what sorts of constructs were removed or added? This can reveal patterns of code that were thread unsafe in the pre-multicore code that developers (especially those not participating in the multicore port) should be made aware of in the future. It can also reveal repeated patterns that were added, indicating potential refactorings that may be desirable to apply in order to reduce the proliferation of code clones within the project. 1.2
The use of version control repositories as a source of data to
study changes to code over time is not new, but our approach
to the problem is novel. Neamtiu [
and seek to infer simple abstract rules that encapsulate the
changes that they detect [
This goal of generating abstract rules is similar to our goal
of inferring generic patterns in terms via antiuni cation [
We propose the tool work ow illustrated in Figure 1 for studying software evolution via VCS data. First, each version of all source les in the project are reconstituted from the di erences stored within the VCS such that each version of a le can be parsed by an appropriate language front end. Each front-end is con gured to map the parsed code to an aterm that represents a standardized serialization of the AST. Mapping languages to a common aterm format allows the downstream portions of our work ow to be languageagnostic to a large degree, with minimal language-speci c parameterization.
Once we have code in an aterm format, we can then apply
a structural di erencing algorithm between adjacent versions
of each source le (e.g., version n of le f is compared
to version n + 1 of le f ). The result of this is a forest
of trees that represent the portions of the AST of le f
that changed between versions at the structural level. These
changes can either be code insertions, deletions, or mutations.
Our di erencing is based on the work of Yang [
After reducing the sequence of di erences stored in the VCS, we have a large forest of trees each representing a change that occurred over the evolution of the software. At this point, we seek to relate each of these trees via a tree similarity metric. This is achieved by using Yang's algorithm a second time, but in this case we ignore the sequence of edit operations that it produces and simply consume the quantitative similarity metric that it produces as a rough estimate of how closely related two trees are. A threshold parameter is de ned in which two trees with a similarity above the threshold are considered to be part of the same group of di erence tress.
Finally, once the set of di erences are grouped into groups
of trees that are similar up to the threshold, we perform
antiuni cation on the entire group to distill all members to a
representative code pattern for the group. Antiuni cation of
a set of terms yields the least general generalization of those
terms, which is how we de ne our notion of a code pattern.
The antiuni cation algorithm as described by Bulychev [
forest of diff subtrees group by similarity antiunify
P1 antiunify
P2
antiunify to obtain
patterns
as part of the clonedigger project3 was used, which itself is
an implementation of the classical antiuni cation algorithm
described by both Reynolds [
In the following sections, we describe the steps above in greater detail. 2.1
One of the most challenging aspects of performing this kind of study on arbitrary software packages is the availability of robust language parsing tools. In the absence of a common intermediate representation or abstract syntax representation for popular languages, we adopted a standardized serialization format in the form of annotated terms. Generation of aterms was achieved via language-speci c parsers. In this work, we used the language-java parser available as an open source library accessible via the Haskell programming language.
The structure of aterms is given by this simple syntax: hatermi ::= `AAppl' hstringi haterm-list i j `AList' haterm-list i j `AInt' hint i haterm-list i ::= hatermi haterm-list i
j
This structure is su cient for us to encode typical abstract syntax trees if we allow ourselves to use the string label of the
AAppl portion of the aterm. This is most easily illustrated with an example. Suppose that we have the Java AST for the statement i++;. In a textual form, this portion of the AST would be represented by:
The translation to aterm would give us:
[AAppl "PostIncrement" [AAppl "ExpName" [AAppl "Name" [AList
[AAppl "Ident" [AAppl "\"i\"" []]]]]]]
Notice that for strings, such as identi er names, we place double quotes around the string inside the label portion of the aterm. Implementations of aterms often provide a representation that allows for nodes to be shared within the tree. While this is a useful optimization for saving space, we chose to use the simpler unshared representation in our prototype due to the clearer expression of the tree analysis algorithms over the unshared form of the structure. 2.2
One of the classical algorithms studied in computer science
is that of string similarity and the concept of string edit
distance as a measure of the minimal number of operations
necessary to mutate one string or sequence into another. A
more complex problem is to de ne a similar sequence of
operations to change a non-linear structure like a tree from
one into another. This problem of computing a structural
edit distance has been studied since the 1970s and has yielded
tree di erencing algorithms analogous to string di erencing
algorithms commonly used in text analysis. Many modern
e orts in this area are based on the initial work of Selkow [
Our work is based on Yang's source di erencing
technique [
Ideally, we would like to obtain from the tree di erencing algorithm what can be thought of as the two trees overlaid on each other such that the common structure from the root towards the children is clear, and points where subtrees di er are explicitly identi ed. The details on how this algorithm was implemented are not critical to this paper | instead, we will focus on what the woven trees contain. In the discussion that follows, we adopt the convention that the arguments to the binary tree di erencing function are referred to as the left and right trees.
Changes that occur between the trees are represented by three change types. If the di erence between two trees is the insertion of a subtree in the right tree, then the woven tree will contain a left-hole. Similarly, deletion of a subtree from the left such that it is not present in the right tree will result in a right-hole. If a subtree was determined to be changed, then the woven tree will contain a mismatch point that refers to the both the right and left subtrees that di er. All other points in the tree that match are joined with a match point that contains the corresponding common node to both trees.
Given two edit trees that have been woven together into a tree with explicit holes and mismatches, we can extract the subtrees that correspond to the three types of changes above. Match points also play an important role in extracting changes by retaining the common context that was present in both trees where the change occurred. If we extract only the subtree rooted at the point where the change occurred, the rest of the analysis will be missing the context where the change took place. This information is necessary when constructing understandable patterns.
For example, while it may be true that a code fragment such as i++ is where the change occurred, it is most useful to know whether or not that fragment occurred within an expression, a for-loop, or as a standalone statement. As such, we have chosen for the work presented here to extract the subtree along with the closest enclosing statement. For example, if the subtree was the expression i++; within the statement if(i < 100) i++; we would extract the if-statement with the expression.
This is achieved by including the subtree rooted at the nearest ancestor (which must be a matching point in the woven edit trees) to a change representing an appropriate abstract syntax element. In the future, we would like to explore other ways of extracting context, such as looking at the closest enclosing expression, function (when it exists), or class. This information should also be parameterizable to support di erences in important AST nodes that varies between languages. 2.4
Given two trees t1 and t2, we would like to de ne a similarity metric such that d(t1; t2) 2 [0; 1], where a similarity of 1 means that the trees are identical, and 0 represents maximal dissimilarity. In Yang's algorithm, a similarity score is provided for comparing ta and tb. This metric is order dependent, forcing the maximal score to be the size of the left tree (ta), even if tb is larger. If the trees are identical, the score will be exactly jtaj, the number of nodes in ta. If they di er, it will be strictly less than jtaj. As such, it would be possible to de ne our distance function to be d(ta;tb) , jtaj but this operator is not symmetric, since it is easy to nd instances such that d(tb;ta) 6= d(ta;tb) when the trees are very jtbj jtaj di erent. Instead, we de ne (ta; tb) to be the function (ta; tb) := min(d(ta; tb); d(tb; ta))
max(jtaj; jtbj) where the min and max functions force the calculation to be symmetric.
Once we have the set of changes that were detected from the VCS history, we can generate a forest of trees t1; ; tn obtained from the holes and mismatch points in the woven edit trees. We then compute the n2 distances between all pairs to generate a distance matrix D where Dij = (ti; tj). Given a threshold value , we can produce a boolean matrix D0 where Di0j = (ti; tj) > . An example matrix is shown in Figure 2 for changes observed in the VCS for ANTLR where = 0:9. Note that for large numbers of changes, a sparse representation of the boolean matrix can be computed for a given without requiring the full dense distance matrix to be created. The sparsity of the matrix is dependent both on the types of changes present and the value of chosen.
In our implementation, we create multiple distance matrices such that each represents only related changes of a certain type from the woven tree (left and right holes, and mismatches). The matrix as de ned above is simply the element-wise boolean or of these three matrices. Capturing this information is important as it allows us to further re ne our view of the code evolution to distinguish code changes from the insertion or removal of code that occurs over time. For example, when code is being developed and grown, we expect to see a number of code insertions. Similarly, when a mass refactoring occurs to simplify code, we would expect to see a set of code deletions. When a more subtle re nement occurs, such as transposition of code arguments or the addition of a conditional to re ne control ow, we would expect to see mismatches where the tree changes. 2.5
Once we have groups of related code snippets in the form of related subtrees, we can seek patterns that relate changes. For example, say we have a function call foo() where each invocation of the function uses the same parameters (e.g, foo(x,y), where x and y are always the same). If we add a new parameter at the end of each call where the variable passed in di ers each time (e.g., foo(x,y,a) and foo(x,y,b)), we would like to abstract out this change as foo(x,y, ), where each instance of the change replaces with whatever concrete variable is used at that point. The antiuni cation algorithm is built for this purpose { given two addi-ons dele-ons modifica-ons 0 0.2 0.4 0.6
Threshold trees, it seeks the least-general generalization of the pair and produces a triplet representing the generalized tree with a metavariable introduced where the two di er, as well as a substitution set that allows the metavariable to be replaced with the appropriate concrete subtree necessary to reconstitute the two trees that were antiuni ed. Multiple distinct metavariables ( 1, , n) are used when multiple independent points are necessary to represent a generalized set of trees.
We tested the methodology outlined in Section 2 on the publicly available git repositories for two popular open source projects, the ANTLR parser generator and the Clojure language implementation. Both are implemented in Java, and one (ANTLR) is composed of a mixture of hand-written and automatically generated code. 3.1
The rst experiment that we performed was to investigate the e ect of similarity threshold to the number of groups identi ed, as well as the degree of generality present in the tree that results from all members of each group being antiuni ed together. Our prediction was that at the lowest threshold ( = 0:0), when all trees are considered to be similar, their antiuni cation will yield the most general pattern. This is what was observed, in which the antiuni cation result is a tree composed of a single metavariable node. Similarly, at the highest threshold ( = 1:0), the only groupings that will be present will be single tree sets, or sets containing identical trees for instances of identical changes that occurred in di erent places. This is precisely what we observed, with the antiuni ed trees containing no meta-variables since antiuni cation of a set of identical elements is the element itself. 3.2
We show the number of groups (broken down by type: addition, deletion, or modi cation) as a function of threshold of similarity ( ). Figure 3 shows the number of groups for the Clojure history and Figure 4 shows the number of groups for the ANTLR history. In both cases, we only consider a small portion of the full history of the VCS.
At the maximum = 1:0, the total number of changes is less than the number of trees we started with, because some } } } 0 changes end up being identical. As we can see, as increases, we see more groupings of changes due to changes that were considered similar under a lower threshold being considered dissimilar under the more restrictive threshold. Increases in the group count represent large groups splitting into one or more smaller groups.
As an example, at = 0:15, a single pattern for for-loops is identi ed: for ( = ; < ;
) {
As the threshold is increased to = 0:25, in addition to generic for-loops, a cohort of changes are identi ed to a more speci c instance of the for-loop where the loop counter is initialized to zero: for ( = 0 ; < ;
) {
Increasing to = 0:35, the pattern for the conditional becomes more speci c and we see what appears to be a template for using the eld of an object (e.g., args.length) as the loop termination criterion: for ( = 0 ; < .
;
) {
Similar templates emerge for code patterns such as method invocations, printing the concatenation of two strings, and other common activities. 3.3
Using a portion of the Clojure history, we varied from 0 to 1 with an increment size of 0.01 as shown in Figure 3. Looking at just the number of deletions, we examined the point where the number of deletions goes from 4 to 5 as the threshold changes from 0.35 to 0.36.
The following code, presented in standard style of uni ed di , shows a loop and the lines that were removed. This example comes from a class named PersistentArrayMap: public Object kvreduce(IFn f, Object init){ for(int i=0;i < array.length;i+=2){ init = f.invoke(init, array[i], array[i+1]); if(RT.isReduced(init))
return ((IDeref)init).deref();
Given the low threshold, this deletion was considered to be similar to the following example from PersistentHashMap. Note that whitespace in most languages is syntactically neutral and curly braces are optional for single statement conditional or loop bodies. As a result, the parser used in this work gives the same AST for if (exp) { stmt; } and if (exp) stmt;. Such changes are intermingled with syntactically meaningful changes in the uni ed di format. To clarify the speci c di erence that our tool considers to actually be di erent, we have added a \>" pre x to the appropriate lines of the uni ed di . public Object kvreduce(IFn f, Object init){ for(INode node : array){
if(node != null){ for(INode node : array) { if(node != null) init = node.kvreduce(f,init); if(RT.isReduced(init))
return ((IDeref)init).deref(); } } } return init; + + + >>+ }
In both cases, our tool identi ed for-loops where the same lines are removed. In fact, the code for both of these is very similar perhaps owing to Java's HashMap and ArrayMap classes being very similar in terms of interface. Furthermore, it did this at the statement level, eg., we did not need to consider the similarities of the le names or the method names. The jump in group count as increased corresponds to the di erences in the for-loops that contain the change falling below the necessary threshold of similarity for grouping.
We have shown that patterns of change over the lifetime of a project can be obtained through analysis of its version control history. The use of tree di erencing and tree similarity measures, as well as the antiuni cation algorithm for computing generalized patterns, allows this large volume of di erence data to be distilled into a compact form in which changes can be studied at the level of the base language syntax. Analysis of the size and count of groups of similar changes as a function of a similarity threshold provides a disciplined way to identify generalizations of changes identi ed by the tool.
Our work has been performed using a generic, language neutral term representation allowing the same techniques to be applied to other languages given appropriate parsing infrastructure and a mapping from language-speci c abstract syntax forms to the generic annotated term form. Minimal parameterization of the tool is necessary to then consume these terms, with language-speci c parameters largely focused on speci c nodes within the term that correspond to semantically useful subtree roots for providing context to tree di erences.
In Section 3.1, we showed that our approach can highlight the evolution of code structurally. In fact, our example of the for-loop precisely supports the hypothetical language designer argument laid out in Section 1.1.
In Section 3.3, we were able to nd related changes in di erent les that happened as part of the same commit. Not only were we able to remove noise compared to linebased di , but we were also looking at the Clojure source for the rst time and able to see an important relationship between the internals of the classes in those two les. As programmers who are completely new to the Clojure source we were able to gain valuable insight.
Our experiment relied on a simple replay of the history of a software project. There are other meaningful ways to generate the set of les to analyze. One such example would be to correlate code changes to bug xes and bug reports and then push those changes through our work ow to nd patterns. As mentioned in Section 1.1 this may provide a support to quality assurance practices.
In Section 2.3 we explored one way to extract context. Many di erent heuristics would be suitable here. Studying the trade-o s of di erent heuristics would allow us to ne tune our approach depending on the application and what we wanted to learn about the source code. 4.1
This work was supported in part by the US Department of Energy O ce of Science, Advanced Scienti c Computing Research contract no. DE-SC0004968. Additional support was provided by Galois, Inc. 5.