  The source code of successful projects is evolving all the time, resulting in
hundreds of thousands of code changes stored in source code repositories. This
wealth of data can be useful, e.g., to find changes similar to a planned code
change or examples of recurring code improvements. This paper presents
DiffSearch, a search engine that, given a query that describes a code change,
returns a set of changes that match the query. The approach is enabled by three
key contributions. First, we present a query language that extends the
underlying programming language with wildcards and placeholders, providing an
intuitive way of formulating queries that is easy to adapt to different
programming languages. Second, to ensure scalability, the approach indexes code
changes in a one-time preprocessing step, mapping them into a feature space,
and then performs an efficient search in the feature space for each query.
Third, to guarantee precision, i.e., that any returned code change indeed
matches the given query, we present a tree-based matching algorithm that checks
whether a query can be expanded to a concrete code change. We present
implementations for Java, JavaScript, and Python, and show that the approach
responds within seconds to queries across one million code changes, has a
recall of 80.7% for Java, 89.6% for Python, and 90.4% for JavaScript, enables
users to find relevant code changes more effectively than a regular
expression-based search, and is helpful for gathering a large-scale dataset of
real-world bug fixes.
