Querying the History of Software Projects using
Q WAL K EKO
Reinout Stevens∗ , Coen De Roover†∗∗ Software Languages Lab, Vrije Universiteit Brussel, Brussels, Belgium† Software Engineering Laboratory, Osaka University, Osaka, Japan

Email: resteven—cderoove@vub.ac.be
Abstract—We present the Q WAL K EKO meta-programming
library for Clojure that enables querying the history of versioned
software projects in a declarative manner. Unique to this libraryis its support for regular path expressions within history queries.
Regular path expressions are akin to regular expressions, exceptthat they match a sequence of successive snapshots of a software
project along which user-specified logic conditions must hold.
Such logic conditions can concern the source code within asnapshot, versioning information associated with the snapshot,
as well as patterns of source code changes with respect to othersnapshots. We have successfully used the resulting multi-faceted
queries to detect refactorings in project histories. In this paper,
we discuss how applicative logic meta-programming enabled
combining the heterogenous components of Q WAL K EKO into a
uniform whole. We focus on the applicative logic interface to a
new implementation of a well-known change distilling algorithm.
We use the problem of detecting and categorizing changes madeto S ELENIUM-based test scripts for illustration purposes.

I.

I NTRODUCTION

Software repositories form a large source of information
regarding the development of software projects. Researchers
can use this information for the analysis of the maintainanceand on how software projects are being maintained and evolve.
So far, tool support to extract and query this information on afine-grained level is lacking.
In this paper we present and demonstrate the capabilities
of a history querying tool called Q WAL K EKO. Q WAL K EKO
is an Eclipse plugin to query the history and evolution ofsoftware projects stored in git. A git repository can be viewed
as a graph, in which nodes correspond to commits, andsuccessive commits are connected. A branch results in multiple
successors, while a merge results in multiple predecessors of anode. Q WAL K EKO combines the graph query language Q WAL1
with the logic program querying language E KEKO [7] to reason
over such a graph. Q WAL navigates through the graph, while
E KEKO is used to specify source code characteristics that haveto hold in a specific version. Q WAL K EKO has been applied
successfully to detect refactorings [1] and classify changes
made to S ELENIUM scripts [2]. The source code, installation
instructions2 , code3 and video used in this paper can be foundon Github.
1 https://github.com/ReinoutStevens/damp.qwal
2 http://github.com/ReinoutStevens/damp.qwalkeko
3 http://github.com/ReinoutStevens/damp.qwalkeko/blob/master/src/
qwalkeko/demo/icsme selenium.clj

II.

E KEKOE KEKO [7] is a Clojure library for applicative logic metaprogramming against an Eclipse workspace. It provides alibrary of predicates that can be used to query programs. These
predicates reify the basic structural, control flow and data flow
relations of the queried Eclipse projects, as well as higher-level
relations that are derived from the basic ones.
Throughout this paper we only use predicates thatreify structural relations computed from the Eclipse JDT.
Binary predicate (ast ?kind ?node), for instance, reifies
the relation of all AST nodes of a particular type.
Here, ?kind is a Clojure keyword denoting the capitalized, unqualified name of ?node’s class. Solutions to thequery (ekeko [?inv] (ast :MethodInvocation ?inv)) therefore comprise all method invocations in the source code.
Throughout this paper we prefix logic variables with a ?.
Ternary
predicate(has ?propertyname ?node ?value)
reifies the relation between an AST node and the value of oneof its properties. Here, ?propertyname is a Clojure keyword
denoting the decapitalized name of the property’sorg.eclipse.jdt.core.dom.PropertyDescriptor(e.g.,:modifiers). In general, ?value is either another ASTNode ora wrapper for primitive values and collections. This wrapper
ensures the relationality of the predicate.
III.

Q WAL

Q WAL allows querying graphs using regular path expressions [8]. Regular path expressions are an intuitive formalism
for quantifying over the paths through a graph. They areakin to regular expressions, except that they consist of logic
conditions to which regular expression operators have been
applied. Rather than matching a sequence of characters in astring, they match paths through a graph along which theirconditions holds.
A Q WAL query is launched using the function(qwal graph begin ?end [ & vars ] & goals).
It takes
as arguments a graph object, a begin node, a logical variable
that is unified with the end node of the expression, avector of local variables available inside the query and an
arbitrary amount of goals. The goals in a query either specify
conditions that must hold in the current node of the query, or
they modify the node against which conditions are checked bymoving through the graph. For example, the goal q=> changes
the current node to one of its successors. Table I provides
an excerpt of the available goals. Users are not limited to

q=>
q<=
(qcurrent [curr] & conditions)(q* & goals)(q=>* & goals)(q=>+ & goals)(q? & goals)

Moves the current version to one of its successors.
Moves the current version to one of its predecessors.
Conditions need to hold in the current version, which is bound to curr. Conditions are regular core.logic predicates.
Goals succeed an arbitrary, including zero, amount of times.
Similar to q*, except an implicit q=> is added after goals. If goals is empty this skips an arbitrary number of nodes.
Similar to q=>*, except goals must succeed at least once. If goals is empty this skips an arbitrary, non-zero number of nodes.
Goals can either succeed or fail.

TABLE I.

E XCERPT OF THE AVAILABLE GOALS IN Q WAL

QwalKeko
consults

Converted Graphin-git-info(fileinfo ?file version)(author version)(revision-number
version)(date version)…

1 (qwalkeko*
2

in-source-code(ast ?type ?node)(has ?prop ?node ?result)(child ?prop ?node ?child)…

3
consults

4
5
6

Qwal
navigates

Fig. 1.

q=>
q=>*
q<=
…

Changes(change ?change left right)(change|affects-node c ?node)…

uses

On the first line we call qwalkeko*, which configures thelogic engine and specifies which variables will be the resultof the query. The second line configures the Q WAL engine.
Both graph and root are already bound, while ?end will bebound to the end version. On the third line we skip an arbitrary
number of versions. This pattern is functionally equivalent tomapping the rest of the query over all the versions in thegraph. In the last three lines we specify that we are interested
in a modified file, as denoted by fileinfo|edit, and its
corresponding compilation unit.

ChangeNodes

Overview of Q WAL K EKO’s architecture.

the goals provided by Q WAL, but can easily define their own
goals.
IV.

[?info ?cu ?end](qwal graph root ?end [](q=>*)(in-source-code [curr](fileinfo|edit ?info curr)(fileinfo|compilationunit ?info ?cu curr))))Q WAL K EKO

B. ChangeNodes

Q WAL K EKO combines Q WAL and E KEKO to reason overthe history of a software project. Foremost, it converts a git
repository into a graph of commits. This graph also contains
information such as the author, timestamp, commitmessage
and modified files of each commit. This graph and data isstored in a new Eclipse project, together with a copy of
the repository. Q WAL is used to navigate through this graphand specifies against which commit predicates are checked.
Predicates can either use the metadata stored in the graph, orthey can use source code information from a specific commit.
For the latter, a new Eclipse project containing that particularrevision is created, and predicates written in E KEKO will usethat project as their fact base. Q WAL K EKO also features its
own set of Q WAL and E KEKO predicates that only make sensein the context of history querying. For example, Q WAL K EKO
provides a set of predicates that reason over changes made to
the source code.

Q WAL K EKO provides an implementation of a tree distillingalgorithm based upon the work of Chawathe et. al [10] called
C HANGE N ODES4 . It takes as input two AST nodes and outputs
a minimal edit script that, when applied, transforms the first
AST into the second one. The edit script will contain thefollowing operations:
InsertDeleteMove

A node is inserted in the AST
A node is removed from the AST
A node is moved to a different location in the
AST
Update A node is updated/replaced with a different node
Chawathe’s algorithm has also been used in C HANGE D IS TILLER [4]. The main difference between C HANGE N ODES andC HANGE D ISTILLER is that C HANGE N ODES works directly on
top of the JDT nodes. C HANGE N ODES uses a language-aware
representation, while C HANGE D ISTILLER uses a languageagnostic representation. The heuristics used in C HANGE D IS TILLER are also used in C HANGE N ODES .

A. Overview of the Architecture
Figure 1 depicts how the different components of
Q WAL K EKO interact. Q WAL K EKO defines the following
two Q WAL goals: (in-git-info [c] & conditions) and(in-source-code [c] & conditions). Both evaluate conditions in the current version c. Goal in-git-info only allows
predicates that reason over the metadata stored in the graph.
For example, the predicate (fileinfo|edit ?info version)
unifies its first argument with a representation of a file that was
modified. Goal in-source-code allows reasoning over sourcecode information. To this end, it performs a checkout of thecode to provide AST information.
The following query finds the compilation units (i.e., theroot node of an AST) of every modified file in all the versionsof the queried software project. We assume graph and root arevariables bound to respectively the graph and the root versionof the queried project.

Q WAL K EKO
introducesanewpredicate(change ?change source target), which binds ?change to asingle change operation between the source AST and target
AST. The predicate (changes ?changes source target)binds ?changes to a collection containing all the changes madeto both ASTs.
The following code demonstrates how one can use thechange predicate to retrieve changes made to two Java classes:
1 (qwal
2
3
4
5
6
7

graph root ?end [?left-cu ?right-cu ?change](in-source-code [curr](ast :CompilationUnit ?left-cu))q=>(in-source-code(compilationunit|corresponding ?left-cu ?right-cu)(change ?change ?left-cu ?right-cu)))

4 https://github.com/ReinoutStevens/ChangeNodesscript. This predicate consults this database and will be usedin further examples.

On line 3 it binds ?left-cu to a compilation unit in the root
version of the graph. It moves to one of the successors of thatversion on line 4. On lines 5–6 we retrieve the corresponding compilation unit using compilationunit|corresponding,which looks for a compilation unit in the same package thatdefines the same type. Finally we compute the changes between these two compilation units using the predicate change.
V.

B. Classification of Changes
Having successfully identified the S ELENIUM scripts inthe queried software project, we now need to compute andcategorize changes made to these files. To this end, whenever a change was made to a S ELENIUM script we will
use C HANGE N ODES to compute the differences between thatrevision of the file and its predecessor.

Q WAL K EKO EXPLAINED BY MEANS OF AN E XAMPLE

In the following section we will build the queries needed tocategorize changes made to S ELENIUM scripts. These queries
have been used to perform an earlier study [2]. First, we need
to identify which files are S ELENIUM scripts. Next, we needto compute changes made to these files. Finally, we detect
whether these changes belong to a predetermined category.

The following query computes and classifies changes madeto S ELENIUM scripts. It skips a arbitrary, non-zero number ofversions using the q=>+ predicate on line 4. Next, it binds ?info
to a modified file in the current revision. It ensures this file isa S ELENIUM script. If no S ELENIUM scripts are modified inthis revision no code is checked out. Next, it binds ?right-cu
to the compilation unit of that S ELENIUM script. On line 10of the query it moves to one of the predecessors of the current
revision using the q<= predicate. On line 12 it retrieves thecorresponding compilation unit of ?right-cu and binds it to?left-cu. Note that the way the query is written, ?left-cu isbound to the original script, while ?right-cu contains the more
recent revision of the script. On the last 2 lines it computes
the changes made these files. The predicate classify-change
is responsible for classifying a single change.

A. Identifying Selenium Scripts
First of all we identify which files of our project are
S ELENIUM scripts. To this end, we write a Q WAL K EKO
query that loops over all the revisions of the queried software
project. For each revision, it inspects the newly added files
and identifies whether it is a S ELENIUM script. The latter isdone by looking whether the file imports a package whichname contains “selenium”. Albeit a simple heuristic we havenot found any incorrectly identified files.
The following query returns all the S ELENIUM scripts, thecompilation unit and the revision of the script of the queried
software project. First, it skips an arbitrary (including zero)amount of revisions by using the q=>* operator on line 3. Next,
we bind ?info to a newly added file. This predicate is evaluated
without checking out the code, and thus if no new files areadded no unnecessary operations are performed. Finally, inthe last three lines we retrieve the corresponding compilation
unit of the added file and verify whether it is a S ELENIUM
script.

1 (qwalkeko*
2
3
4
5
6
7
8
9
10
11
12
13
14

1 (qwalkeko*
2
3
4
5
6
7
8

[?info ?cu ?end](qwal graph root ?end [ ](q=>*)(in-git-info [curr](fileinfo|add ?info curr))(in-source-code [curr](fileinfo|compilationunit ?info ?cu curr)(compilationunit|selenium ?cu))))Identifying whether a compilation unit is a S ELENIUM
script is done purely using E KEKO. On line 2 we define three
new logic variables using fresh. Line 3 verifies whether ?cu
unifies with a compilation unit. Line 4 unifies ?imp with oneof the import statements on that compilation unit. Lines 5–
6 retrieve the name of the imported package. The last line
verifies whether the name contains the string “.selenium”.
1 (defn
2
3
4
5
6
7

compilationunit|selenium [?cu](fresh [?imp ?impname ?str](ast :CompilationUnit ?cu)(child :imports ?cu ?imp)(has :name ?imp ?impname)(name|qualified-string ?impname ?str)(string-contains ?str ".selenium")))The results of this query are written to a database so thatthey do not need to be recomputed by other predicates. We introduce a new predicate (fileinfo|selenium file version)
which verifies whether a file corresponds to a S ELENIUM[?left-cu ?right-cu ?info ?end ?change ?category](qwal graph version ?end [](q=>+)(in-git-info [curr](fileinfo|edit ?info curr)(fileinfo|selenium ?info curr))(in-source-code [curr](fileinfo|compilationunit ?info ?right-cu curr))q<=(in-source-code [curr](compilationunit|corresponding ?right-cu ?left-cu)(change ?change ?left-cu ?right-cu)(classify-change ?change ?category))))The following code verifies that a change can be classified as a modification to a locator. To this end it uses(change|affects-node change ?node), which unifies ?node toany parent node of both the original and the target AST
node of the change. This predicate works purely on an ASTlevel, and does not use other sources of information. It thenverifies whether one of the affected nodes resides inside eithera method invocation with the name “By” or an annotation
named “FindBy”. These predicates are once again written
using E KEKO.
1 (defn
2
3
4
5
6change|affects-findBy [change ?find-by](all(change|affects-node change ?find-by)(conde[(methodinvocation|by ?find-by)][(annotation|findBy ?find-by)])))

7 (defn
8
910
11

methodinvocation|by [?x](fresh [?name](ast :MethodInvocation ?x)(child :expression ?x ?name)(name|simple-string ?name "By")))12 (defn
13
14
15
16

annotation|findBy [?x](fresh [?name](ast :NormalAnnotation ?x)(has :typeName ?x ?name)(name|simple-string ?name "FindBy")))Predicates for the remaining categories are analogous.
VI.

R ELATED W ORK

While most VCS provide limited version querying facilities (e.g., to see who touched a file), they do not support
querying the code within a version – let alone across versions. The E VOLIZER platform supports history analyses ofversioned software through dedicated plugins. For instance,
C HANGE D ISTILLER [4] extracts code changes between successive versions through tree differencing. The general-purpose
history querying tools that exist, (i.e., SCQL [5] and VPraxis [6]) do not feature a language dedicated to specifying
the temporal characteristics of fine-grained code evolutions
across multiple versions.
Boa [3] is a query language for large-scale software repositories. It allows answering high-level questions over a plethoraof software repositories. Examples of questions are “Whatare the five most used licenses?”, “How many Java projects
using SVN were active in 2011?” and “What are the projects
that support multiple operating systems?”. Queries for thesequestions do not range over source code but rather high-level
information of the queried software projects. Boa also features
an AST visitor that can be used in queries. This has been used
to detect whether and how new language features are adopted
in programming projects. Boa users are limited to querying the
projects that are made available on their website, and thus noarbitrary projects can be queried. Q WAL K EKO allows querying
any Java project stored in git. It also provides a richer querylanguage to retrieve information from the source code of thequeried projects.
VII.

D ISCUSSIONQ WAL K EKO provides an easy way to query large-scale
software projects in an acceptable time. The REPL provides anice way to gradually build queries until the expected results
are returned. Applying these queries to different data setsrequires no modification.
Q WAL K EKO only provides AST nodes as its source of
information. E KEKO provides other predicates that reason overbindings (i.e.,, type and scoping information) provided by
Eclipse. In order to generate these bindings a project mustcompile successfully in Eclipse. This is not always feasible,
as libraries may be missing, or some revisions only work witha specific version of a library. We have incorporated the Partial
Program Analysis [9] tool in Q WAL K EKO, but the performanceis too slow for large-scale code querying. Thus, queries areeither limited to AST information, or the user needs to ensure
the project compiles properly.
Some recurring patterns have an unexpected poor performance, mainly due to the logic reasoning engine provided by
Clojure. A concrete example is the use of the q=>* predicate at
the beginning of a query. For large projects this pattern must
be rewritten so that it uses Clojure’s map over all the versions
in the graph. An automated rewrite of these patterns would

increase the performance, while keeping the readability of thequery language.
VIII. S UMMARY
We have presented Q WAL K EKO as a tool to queryover the history of software projects stored in Git. To thisend, it combines the programming query language E KEKO
with the regular path expressions language Q WAL. It provides its own set of predicates that only make sense in
the context of history querying. The most important oneis (change ?change left-cu right-cu), which reifies change
operations made to ASTs. It uses C HANGE N ODES, which
implements a tree differencing algorithmn on top of the JDTAST nodes. We have demonstrated the use of Q WAL K EKO by
writing queries that identify S ELENIUM scripts at categorizechanges made to these scripts.
ACKNOWLEDGMENTS
This work has been supported, in part, by the Cha-Q SBO project of
the Flemish agency for Innovation by Science and Technology (IWT), by a
PhD scholarship of the same agency, by the Japan Society for the Promotionof Science, Kakenhi Kiban (S), No.25220003, and by the Osaka University
Program for Promoting International Joint Research.

R EFERENCES
[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]
[9]

[10]

R. Stevens, C. De Roover, C. Noguera, and V. Jonckers, “A history
querying tool and its application to detect multi-version refactorings,” inProceedings of the 17th European Conference on Software Maintenanceand Reengineering (CSMR13), 2013.
L. Christophe, R. Stevens, and C. De Roover, “Prevalence and maintenance of automated functional tests for web applications,” in Proceedings of the 30th Internation Conference on Software Maintenance andEvolution, 2014, to be published.
R. Dyer, H. A. Nguyen, H. Rajan, and T. N. Nguyen, “Boa: A language
and infrastructure for analyzing ultra-large-scale software repositories,”in Proceedings of the 2013 International Conference on Software
Engineering (ICSE), 2013.
B. Fluri, M. Würsch, M. Pinzger, and H. C. Gall, “Change distilling:
Tree differencing for fine-grained source code change extraction,”Transactions on Software Engineering, vol. 33, no. 11, 2007.
A. Hindle and D. M. German, “SCQL: A formal model and a querylanguage for source control repositories,” in Proceedings of the 2005
Working Conference on Mining Software Repositories (MSR05), 2005,
pp. 100–105.
A. Mougenot, X. Blanc, and M.-P. Gervais, “D-Praxis: A peer-topeer collaborative model editing framework,” in Proceedings of the 9thInternational Conference on Distributed Applications and Interoperable
Systems (DAIS09), 2009, pp. 16–29.
C. De Roover and R. Stevens, “Building development tools interactively
using the ekeko meta-programming library,” in Proceedings of the
CSMR-WCRE Software Evolution Week (CSMR-WCRE14), 2014.
O. de Moor, D. Lacey, and E. V. Wyk, “Universal regular path queries,”
Higher-Order and Symbolic Computation, pp. 15–35, 2002.
B. Dagenais and L. Hendren, “Enabling static analysis for partial java
programs,” in In Proceedings of the 23rd ACM SIGPLAN conference
on Object oriented programming systems languages and applications(OOPSLA08), 2008.
S. S. Chawathe, A. Rajaraman, H. Garcia-Molina, and J. Widom,“Change detection in hierarchically structured information,” in Proceedings of the ACM SIGMOD International Conference on Managementof Data (SIGMOD96), 1996, pp. 493–504.