Three-way merge tools play crucial roles in modern software development, where a developer forks a branch to make local modifications and requests it to be merged into the main branch via a "pull request." Despite its importance, the task has traditionally been defined in an intuitive manner, and the results of merge tools are often accepted without scrutiny. In this paper, we present a new structural merge tool in comparison with existing tools based on the syntactic criteria we propose for evaluating the merge results. We require the merge result to be both parsable and universal. Being parsable means that the result is syntactically valid according to the grammar of the programming language. Being universal means that the result incorporates all and only the edit operations occurring in each branch while ensuring that edits common to both branches are applied only once. This requirement can be precisely defined using the notion of pushouts in category theory. In a large-scale experiment involving 43,774 file merge scenarios from 76 open-source Java projects, we found a number of incorrect results reported by existing tools such as the Git companion merge tool, whereas our tool reports none. We further compared d3j’s results with 2,582 developer-resolved merges and with 2,459 merge scenarios involving 21 refactoring types. These experiments revealed both the strengths and current limitations of structural merge, and underscore the importance of clear correctness criteria. We expect that the proposed criterion will provide a foundation for developing more reliable and principled merge tools.

In this paper, we apply techniques from phylogenetics for uncovering evolutionary dependencies among software versions. Phylogenetics is a part of computational molecular biology that addresses the inference of evolution among organisms based on differences/similarities in DNA sequences and morphology. We apply a tree differencing technique to abstract syntax trees to calculate a distance matrix, which is then used by a distance-based phylogenetic algorithm to infer an evolution network. Such a network allows us to identify merging and branching among versions without manually looking into the details of the source code. Experiments on ancient versions of the Emacs editor and the open source 3D printer firmware show that we can reproduce the evolution of the software and identify code import/merging across different lineages. We also discuss how the techniques identify the feature models among software variations. To the best of our knowledge, this paper is the first to report on a reticulate phylogenetic analysis of the software. It may offer a helpful method for gaining information on the evolution of the software.

Delta debugging (DD) is an approach to automating the debugging activities based on systematic testing. DD algorithms find the cause of a regression of a program by minimizing the changes applied between a working version and a faulty version of the program. However, it is still an open problem to minimize a huge set of changes while avoiding any invalid subsets that do not result in testable programs, especially in case that no software configuration management system is available. In this paper, we propose a rule-based approach to syntactic and semantic decomposition of changes into independent components to facilitate DD on source code changes, and hence to extract patches automatically. For analyzing changes, we make use of tree differencing on abstract syntax trees instead of common differencing on plain texts. We have developed an experimental implementation for Java programs and applied it to 194 bug fixes from Defects4J and 8 real-life regression bugs from 6 open source Java projects. Compared to a DD tool based on plain text differencing, it extracted patches whose size is reduced by 50% at the cost of 5% more test executions for the former dataset and by 73% at the cost of 40% more test executions for the latter, both on average.

The process of performance tuning is time consuming and costly even if it is carried out automatically. It is crucial to learn from the experience of experts. Our long-term goal is to construct a database of facts extracted from specific performance tuning histories of computation-intensive applications such that we can search the database for promising optimization patterns that fit a given kernel.

To improve performance of large-scale scientific applications, scientists or tuning experts make various empirical attempts to change compiler options, program parameters or even the syntactic structure of programs. Those attempts followed by performance evaluation are repeated until satisfactory results are obtained. The task of performance tuning requires a great deal of time and effort. On account of combinatorial explosion of possible attempts, scientists/tuning experts have a tendency to make decisions on what to be explored just based on their intuition or good sense of tuning. We advocate evidence-based performance tuning (EBT) that facilitates the use of database of facts extracted from tuning histories of applications to guide the exploration of the search space. However, in general, performance tuning is conducted as transient tasks without version control systems. Tuning histories may lack explicit facts about what kind of program transformation contributed to the better performance or even about the chronological order of the source code snapshots. For reconstructing the missing information, we employ a state-of-the-art fine-grained change pattern identification tool for inferring applied transformation patterns only from an unordered set of source code snapshots. The extracted facts are intended to be stored and queried for further data mining. This paper reports on experiments of tuning pattern identification followed by predictive model construction conducted for a few scientific applications tuned for the K supercomputer.

This paper presents a comprehensive method for identifying fine-grained change patterns in the source code of large-scale software projects. Source code changes are computed by differencing abstract syntax trees of adjacent versions and transferred to a set of logical statements called a factbase. A factbase contains information for tracking and relating source code entities across versions and can be used to integrate analysis results of other tools such as call graphs and control flows. Users can obtain a list of change pattern instances by querying the factbase. Experiments conducted on the Linux-2.6 kernel, which involve more than 4 billions of facts, are reported to demonstrate capability of the method.