Flexeme: Untangling Commits Using Lexical Flows
Profir-Petru Pârt, achi

Santanu Kumar Dashprofir-petru.partachi.16@ucl.ac.uk
University College London
London, United Kingdom

s.dash@surrey.ac.uk
University of Surrey
Guildford, Surrey, United Kingdom

Miltiadis Allamanis

Earl T. Barrmiallama@microsoft.com
Microsoft Research
Cambridge, Cambridgeshire, United Kingdom

e.barr@ucl.ac.uk
University College London
London, United Kingdom

ABSTRACT

1

Today, most developers bundle changes into commits that they submit to a shared code repository. Tangled commits intermix distinct
concerns, such as a bug fix and a new feature. They cause issues
for developers, reviewers, and researchers alike: they restrict theusability of tools such as git bisect, make patch comprehension
more difficult, and force researchers who mine software repositories to contend with noise. We present a novel data structure,the 𝛿-NFG, a multiversion Program Dependency Graph augmented
with name flows. A 𝛿-NFG directly and simultaneously encodes different program versions, thereby capturing commits, and annotates
data flow edges with the names/lexemes that flow across them. Our
technique, Flexeme, builds a 𝛿-NFG from commits, then applies
Agglomerative Clustering using Graph Similarity to that 𝛿-NFG tountangle its commits. At the untangling task on a C# corpus, ourimplementation, Heddle, improves the state-of-the-art on accuracy
by 0.14, achieving 0.81, in a fraction of the time: Heddle is 32 times
faster than the previous state-of-the-art.

Separation of concerns is fundamental to managing complexity.
Ideally, a commit to code repositories obeys this principle andfocuses on a single concern. However, in practice, many commits
tangle concerns [2, 6]. Time pressure is one reason. Another isthat the boundaries between concerns are often unclear. MurphyHill et al. [21] found that refactoring tasks are often committed
together with code for other tasks and that even multiple bug fixes
are committed together.
Tangled commits introduce multiple problems. They make searching for fault inducing commits imprecise. Tao et al. [27] found thattangled changesets (commits) hamper comprehension and thatdevelopers need untangling (changeset decomposition) tools. Barnett et al. [2] confirmed this need. Herzig et al. [6, 7] studied thebias tangled commits introduce to classification and regression
tasks that use version histories. They found that up to 15% of bug
fixes in Java systems consisted of multiple fixes in a single commit.
They also found that using a tangled version history significantly
impacts regression model accuracy. In short, tangled commits harm
developer productivity two ways: directly, when a developer mustsearch a version history and indirectly by slowing the creation oftools that exploit version histories.
Version histories permit a multiversion view of code, one inwhich multiple versions of the code co-exist simultaneously. Le et al.
built on principles described by Kim and Notkin [12] for multiversion analysis: they constructed a multiversion intraprocedural control flow graph and used it to determine whether a commit fixes all𝑛 versions [16]. This task is important when multiple versions areactive, as in software product lines, and the patch fixes a vulnerability. Inspired by Le et al., we define a 𝛿-PDG, a multiversion program
dependence graph (PDG), a graph that combines a program’s dataand control graphs [5].
We hypothesise that identifiers differentiate concerns. We harvest names that are used together in a program’s execution, as
in this statement «takehome:=tax * salary» to augment our 𝛿PDG and produce a 𝛿-NFG. A desirable property of our 𝛿-NFG
is its modularity. It allows projecting any combination of data,
control, or lexeme. Consequently, we could effortlessly reproduce
Barnett et al.’s and Herzig et al.’s methods [2, 6] to explore thedesign space in tooling for concern separation in commits.
We introduce Flexeme, a novel approach to concern separationthat uses the 𝛿-NFG. We group edits into concerns using the graphsimilarity of their neighbourhoods. We base this on the intuition

CCS CONCEPTS• Software and its engineering → Software version control; •Mathematics of computing → Graph algorithms; • Computing
methodologies → Kernel methods; • General and reference →General conference proceedings.

KEYWORDS
graph kernels, clustering, commint untangling
ACM Reference Format:
Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T.
Barr. 2020. Flexeme: Untangling Commits Using Lexical Flows. In Proceedings of the 28th ACM Joint European Software Engineering Conference andSymposium on the Foundations of Software Engineering (ESEC/FSE ’20), November 8–13, 2020, Virtual Event, USA. ACM, New York, NY, USA, 12 pages.
https://doi.org/10.1145/3368089.3409693
Permission to make digital or hard copies of all or part of this work for personal orclassroom use is granted without fee provided that copies are not made or distributedfor profit or commercial advantage and that copies bear this notice and the full citationon the first page. Copyrights for components of this work owned by others than theauthor(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or
republish, to post on servers or to redistribute to lists, requires prior specific permission
and/or a fee. Request permissions from permissions@acm.org.
ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA© 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM.
ACM ISBN 978-1-4503-7043-1/20/11. . . $15.00
https://doi.org/10.1145/3368089.3409693

INTRODUCTION

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

that nodes are defined by the company they keep (their neighbourhoods) and cluster them accordingly. Thus, we reduce the concern
separation problem to a graph clustering task. For clustering, westart by considering each edit in a commit as an separate concern,then use graph similarity to agglomeratively cluster them. We compute this similarity using the Weisfeiler-Lehman Graph Kernel [25].
We realised Flexeme in a tool we call Heddle1 . Developers canrun Heddle to detect tangled commits prior to pushing them orreviewers can use it to ask developers to untangle commits before
branch promotion. We show that heddle improves the state-of-theart accuracy by 0.14, and run-time by 32 times or 3 ′ 10 ′′ . We also
demonstrate the utility and expressivity of our 𝛿-PDG construct byadapting Herzig et al.’s confidence voters (CV) to use the 𝛿-PDG
rather than diff-regions; the resulting novel combination, which wecall 𝛿-PDG+CV improves the performance and lowers the run-timeof Herzig et al.’s unmodified approach.
In summary, we present(1) Two novel data-structures, the 𝛿-PDG, a multiversion program dependence graph, and 𝛿-NFG, which augments a 𝛿PDG with lexemes;(2) The Flexeme approach for untangling commits that buildsa 𝛿-NFG from a version history then uses graph similarity
and agglomerative clustering to segment it; and(3) Heddle, a tool that realises Flexeme and advances the stateof art in commit untangling in both accuracy and run-time.
All of the tooling and artefacts needed to reproduce this work
are available at https://pppi.github.io/Flexeme/.

2

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr@@ -127,31 +137,32 @@ namespace Terminal {{this.barItems = barItems;
this.host = host;1a+ ColorScheme = Colors.Menu;
CanFocus = true;}
public override void Redraw(Rect region){- Driver.SetAttribute(Colors.Menu.Normal);- DrawFrame(region, true);+ Driver.SetAttribute(ColorScheme.Normal);+ DrawFrame(region, padding: 0, fill: true);for (int i = 0;i < barItems.Children.Length;i++){
var item = barItems.Children [i];Move(1, i+1);- Driver.SetAttribute(1c- item == null ? Colors.Base.Focus :- i == current ? Colors.Menu.Focus :- Colors.Menu.Normal- );+ Driver.SetAttribute(+ item == null ? Colors.Base.Focus :+ i == current ? ColorScheme.Focus :+ ColorScheme.Normal+ );for (int p = 0; p < Frame.Width-2; p++)if (item == null)

EXAMPLE

Localising a bug with git bisect to determine a bug inducing
commit, or reviewing a changeset during code review in presenceof tangled commits can make the task unnecessarily difficult oreven impossible [27]. Further, as Herzig et al. [6] found, tangledcommits have a statistically significant impact on the performanceof regressions methods used for defect prediction. Barnett et al. [2],determined that developer productivity benefits from tools that canpropose changeset decompositions. In light of this, it is natural to
ask how do different code entities co-occur within a concern?
The code entities of a concern tend to be in close proximitywith each other in both the control- and data-flow graphs. Barnett
et al. [2] exploited this by using def-use chains, which offer a shortrange view of these connections. However, as shown in Figure 1,
connectivity through the data-flow graphs on its own is insufficient
to demarcate concerns. Indeed, this observation is reflected in therelatively lower accuracy rates on concern separation reported inBarnett et al. [2] compared to Herzig et al. [6], the concerns 1 and
2 consisting of the hunks 1a-1d and 2a-2b, respectively, could
be conflated as they are method invocations of the same Driverclass. The conflation might occur even though hunks 1b, 1c and 1d
are connected via the use of the Colors.Menu and ColorScheme which
provides counterweight to conflating concerns 1 and 2.
Control-flow can help delineate regions or constructs that handle
specific types of concerns. For example, a loop could be performing
1 A heddle is wire or cords with eyelets that hold warp yarns in a place in a loom.
While it does not untangle, a heddle prevents tangles, so we have named our tanglepreventing tool after it.

1b- Driver.AddSpecial(SpecialChar.HLine);+ Driver.AddRune(Driver.HLine);
else

2a

2b
- Driver.AddCh(' ');+ Driver.AddRune(' ');if (item == null)continue;Move(2, i + 1);
DrawHotString(item.Title,- i == current? Colors.Menu.HotFocus :- Colors.Menu.HotNormal,- i == current ? Colors.Menu.Focus :- Colors.Menu.Normal);+ i == current? ColorScheme.HotFocus :+ ColorScheme.HotNormal,+ i == current ? ColorScheme.Focus :+ ColorScheme.Normal);

1d

Figure 1: A diff with two tangled concerns: (a) the changeof the drawing API (all other changes) and (b) the migrationfrom using chars and special chars to runes (the two changes
related to AddRune). Attempting to disentangle this diff withstate-of-the-art tools relying on DU-chains fails because thetangled changes are connected in the def-use chain pertaining to Driver and are in close proximity in the file. Using a
PDG allows us to additionally exploit control flow information to aid untangling.

Flexeme: Untangling Commits Using Lexical Flowsa specialised computation that forms a single concern on its own.
We see an example of such a loop in Figure 1. The for loop captures
the process by which a screen line is generated and is strongly
related to how on screen characters are handled (1a and 1b). Thissuggests that using a Program Dependency Graph (PDG), which
encapsulates both control- and data-flow, as a basis for performing
commit untangling overcomes some of the shortcomings of using
the data-flow alone. The PDG provides evidence that 1a and 1b
could be a part of the same concern because of control-flow. Additionally, the PDG also tells us that 1c and 1d could be a part ofthe same concern by virtue of data-flow through Colors.Menu andColorScheme. However, it may be observed that the link with 2a-2b
is still strong due to flows through Driver.
Lexemes in the two concerns in Figure 1 provide strong evidence for their separation. While concern 1 uses Set* methods inDriver, concern 2 uses Add* methods. This evidence is missed by
PDGs which discard lexical information. Developers tend to use
dissimilar names for different tasks. Dash et al. [3] leveraged thisobservation to augment data-flow with lexical information to successfully identify type refinements. In our work, we take a similar
approach and use lexical information to separate concerns. Our approach to introducing lexemes in our PDG representation is similar
to the name-flows construct of Dash et al. [3]. While they augmented
data-flow with lexemes, we augment PDGs and a description of
how we achieve this follows.

3

CONCERNS AS LEXICAL COMMUNITIESGiven consecutive versions of some code, Flexeme constructs their
PDGs and overlays them adding name-flows [3] to build a 𝛿-NFG.
We feed the 𝛿-NFG to a graph clustering procedure to reconstructatomic commits. A 𝛿-NFG naturally captures flows that bind concerns together such as data- and control-flows. Additionally, it also
captures natural correlation in names that developers choose whenaddressing a given concern.
Figure 2 overviews how flexeme constructs and uses a 𝛿-NFG.
For a sequence of contiguous versions, we generate a PDG firstwith the help of a compiler. We then combine these PDGs to form
a multi-version PDG which we call a 𝛿-PDG. We then decorate
the 𝛿-PDG with version specific name-flow information to obtaina 𝛿-NFG. We feed the 𝛿-NFG to agglomerative clustering. We use
graph similarity to separate concerns across the original set of contiguous versions. We discuss the details of the 𝛿-NFG construction
in Section 3.1, Section 3.2 and Section 3.3. We discuss the graphclustering approach in Section 3.4.

3.1

Multi-Version Name Flow Graphs

We now formally define the PDG, 𝛿-PDG and 𝛿-NFG in order tobootstrap discussion on the 𝛿-NFG construction.
Definition 3.1. Program Dependency Graph (PDG). Flexeme’s PDG
is a directed graph with node set 𝑁 and edge set 𝐸 s.t. each node𝑛 ∈ 𝑁 is annotated with either a program statement or a conditional
expression; each edge 𝑒 ∈ 𝐸 has an optional annotation representing
the name or the data that flows along it, and a kind that describes
the relationship type: data or control.

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

Definition 3.2. Multi-version Program Dependency Graph (𝛿-PDG).
A 𝛿-PDG 𝑝,𝑞 is the disjoint union of all nodes and edges across all
versions in [𝑝, 𝑞]. 𝛿-PDG 𝑝,𝑝 is the PDG at version 𝑝.
Definition 3.3. Name Flow Graph (NFG). Flexeme’s NFG is a standard dataflow graph 𝐺 = (𝑁 , 𝐸), augmented with name flows, theraw lexemes of the literals and identifiers in a program text thatoriginate at some node flow across edges and collect in downstream
nodes. A name flow labels an edge with those lexemes that flow
across it and a node with those that either originate at it or flow
into it.
We re-use NFG from Dash et al.’s Refinym [3]. To a first approximation, lexemes flow along def-use chains and collect in thevariables on the LHS of assignments.
Definition 3.4. Multi-version Name Flow Graphs (𝛿-NFG).
A 𝛿-NFG 𝑝,𝑞 is the 𝛿-PDG 𝑝,𝑞 , augmented with name flows: If anedge exists in both the PDG and the NFG of a version, we augment
the PDG edge with the corresponding name flow.
Inspired by Le and Pattison [16]’s multiversion intraprocedural graphs, we are the first to propose and construct 𝛿-PDGs. To
construct a 𝛿-PDG, we start from the initial version considered.
For each subsequent version, we make use of line-span information in the PDG and UNIX diff on the source-files to determinechanged and unchanged nodes, making Flexeme language agnostic.
Changed nodes are introduced to the 𝛿-PDG as they appear in the
new version. 𝛿-PDGs retain nodes deleted across the versions a 𝛿PDG spans. Deletion becomes a label. We match unchanged nodes
between the nodes of the 𝛿-PDG and the new version. To match, we
use string similarity to filter candidates and we use line-span proximity to rank them (Section 3.2). For nodes the new version deletes,
we backpropagate the delete label to edges flowing into them. To
add edges, we consider all unmatched edges in the new version,then match their source and target either to existing 𝛿-PDG nodes,
or, when a either the source or target does not exist in input 𝛿-PDG,
match it to a fresh node (Section 3.3). Finally, to obtain a 𝛿-NFG,
we endow the 𝛿-PDG with name flow information for each of theversions considered by matching nodes using their line-spans.

3.2

Anchoring Nodes Across Versions

To integrate a fresh PDG 𝐺 𝑗 , we start with the patch 𝑃𝑖 𝑗 . We vieweach hunk ℎ ∈ 𝑃𝑖 𝑗 as a pair of snippets (𝑠𝑖−, 𝑠 +𝑗 ) where version 𝑖deletes 𝑠𝑖− and version 𝑗 adds 𝑠 +𝑗 . Snippets 𝑠𝑖− and 𝑠 +𝑗 do not exist
for hunks that only add or only delete; 𝜙 represents these patches.
Accounting for 𝑠𝑖− is straightforward: we do not update the nodes
in the 𝐺 1−𝑖 that fall into 𝑠𝑖− . Accounting for 𝑠 +𝑗 is non-trivial; much
like patching utilities, we need a notion of context.
For all 𝑠 +𝑗 , we introduce fresh nodes in the 𝛿-PDG. However,
we cannot anchor these nodes until we identify counterparts fornodes in 𝐺 𝑗 that were untouched by 𝑃𝑖 𝑗 . Identifying untouchednodes in 𝐺 𝑖 is straightforward; we can simple check locations in
𝑃𝑖 𝑗 against the location of each node in 𝐺 𝑗 . All touched nodes from𝐺 𝑗 are treated as new added nodes and need to be introduced inthe 𝛿-PDG. Identifying the counterpart in 𝐺 𝑖 of an untouched nodein 𝐺 𝑗 requires a notion of node equivalence.

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr

Figure 2: Overview of flexeme’s 𝛿-NFG construction and concern separation.
Definition 3.5. Node Equivalence. Given a node 𝑣 𝑗 in a 𝐺 𝑗 and acandidate node 𝑣𝑖 in 𝐺 1,𝑖 ,𝑣 𝑗 ≡ 𝑣𝑖 ⇐⇒ ∀(𝑝, 𝑞) ∈ 𝑅(𝐴[𝑣 𝑗 ], 𝐴[𝑣𝑖 ]).𝐹 (𝑝, 𝑞) ≥ 𝑇
Here, 𝐴[𝑘] returns all nodes adjacent to the node 𝑘 in a graph.
𝑅 is a variant of the Stable Roommates Problem [9] where nodes
drawn from 𝐴[𝑣𝑖 ] are matched with nodes drawn from 𝐴[𝑣 𝑗 ]. Eachnode in 𝐴[𝑣 𝑗 ] has an affinity for nodes in 𝐴[𝑣𝑖 ] proportional to
the similarity of lexemes at the nodes. The operator 𝑅 considers
these affinities and tries to match each node with the one it has
the highest affinity for. By construction, 𝑅 always returns a oneto-one match even though two different nodes 𝑎 and 𝑏 may have astrong affinity to a third node 𝑐. In such a case, either 𝑎 or 𝑏 will
be matched with 𝑐 but not both; the one that is not matched to its
highest preference (defined in terms of affinity) is matched to thenext node from its preference list. We further require that lexical
similarity, computed by the function 𝐹 , is above the threshold 𝑇 .
This lets us control the level of fuzziness while matching nodes.
In this work, we have chosen 𝐹 to be string edit distance and set
𝑇 = 1.0 thus requiring exact matches.

3.3

Integrating Nodes Across Versions

Once counterpart nodes are identified using a notion of node equivalence, the next task is to store the location information for theuntouched nodes in 𝐺 𝑗 at theirs counterpart and mark the location with version 𝑗. Finally we add all the nodes 𝑃𝑖 𝑗 adds to the𝛿-PDG and create edges between them and the counterparts of theirparents and children.
We demonstrate the 𝛿-PDG construction in Figure 3. We show
the PDG for two versions of an application — 1 and 2. Since version 1 is our initial version in this example, it is also our 𝛿-PDG
𝐺 1 . We have omitted the data-flows in the PDG for brevity. Eachnode in the PDG contains a list of location-version tuple; the location information has been supressed for simplicity. The patch
above the two PDGs is the diff of the two versions. We have twosnippets in the patch: 𝑠 1− for the snippet that is to be deleted in
1 and 𝑠 2+ the snippet that is to be added in 2. Accounting for thedeleted line comes for free as we store locations for snippets acrossversions. All we need to do is to check the location information
for 𝑠 2− against the span of the nodes in the 𝐺 1 . For 𝑠 2+ , we needto search for equivalent nodes across the two versions. We perform fuzzy matching on lexemes in nodes shortlisted using location
information as detailed above. In the case of 𝑠 2+ , we identify thecall expressions Move and Driver.AddCh(...) as parents and children,

respectively, for 𝑠 2+ . Merging 𝑠 2+ into the 𝛿-PDG shown on the rightis then a straightforward task of drawing edges between nodes andtheir parents/children. Once we obtain this 𝛿-PDG representation,
we perform the untangling task in a reconstructive manner.

3.4

Identifying Concerns

We start by assuming each change is atomic, and iteratively mergechanges that are similar enough. At a high-level, we expect similar
nodes to have similar “neighbourhoods”. To measure this, we build
the 𝑘-hop neighbourhood2 , for each node. We then cluster by similarity of these neighbourhoods. To compute graph similarity, we
use the Weisfeiler-Lehman graph kernel [25] which builds on topof the Weisfeiler-Lehman graph isomorphism test [30]. For a pairof graphs, the test iteratively generates multi-set labels. When two
graphs are isomorphic, then all the sets are identical.
Formally, let the initial vertex labelling function of the graphbe 𝑙 0 : 𝑉 (𝐺) → L, where L is the space of all node labels. At
step 𝑖, let 𝑙𝑖 (𝑣) = {{𝑙𝑖−1 (𝑣 ′ )} | 𝑣 ′ ∈ 𝑁 (𝑣)}, where 𝑁 (𝑣) is the set ofneighbours of vertex 𝑣. At each iteration 𝑖, this process labels thenode 𝑣 with a set comprising the labels of all of 𝑣’s neighbours. Thisset becomes the new label of that node. Since isomorphism testing
can diverge, we bound it to 𝑛 iterations and obtain the sequence⟨𝐺 0, 𝐺 1, . . . , 𝐺𝑛 ⟩.
A positive semi-definite kernel on the non-empty set 𝑋 is asymmetric function
𝑘 :𝑋 ×𝑋 → R
𝑛 Õ
𝑛
Õ
s.t.
𝑐𝑖 𝑐 𝑗 𝑘 (𝑥𝑖 , 𝑥 𝑗 ) ≥ 0,
𝑖=1 𝑗=1∀𝑛 ∈ N, 𝑥 1, . . . , 𝑥𝑛 ∈ 𝑋, 𝑐 1, . . . , 𝑐𝑛 ∈ R.
This function can take the arguments in either order and, for any
parametrization by real constants, has non-negative weighted sum
over all inputs. A graph kernel is a positive semi-definite kernel on
a set of graphs. When a kernel takes a set of graphs (G) as input, we
define the 𝐾 (G)𝑖 𝑗 = 𝑘 (𝐺𝑖 , 𝐺 𝑗 ), 𝐺𝑖 , 𝐺 𝑗 ∈ G to compute the matrixof pairwise kernel values.
Let G be the set of graphs over which we wish to compute graphbased similarity, and let 𝐾 : G → R | G | × R | G | be a graph kernel.
Then the WL Graph Kernel becomes: 𝐾𝑊 𝐿 (G) = 𝐾 (G0 ) + 𝐾 (G1 ) +. . .+𝐾 (G𝑛 );, where ⟨G0, G1, . . . , G𝑛 ⟩ is obtained by applying 𝑛 stepsof the isomorphism test to each graph in G
2 In our experiments we consider the 𝑘 = 1-hop neighbourhoods.

Flexeme: Untangling Commits Using Lexical Flows

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA
hot_pos != -1@@ -85,4 +85,4 @@- Driver.SetAttribute (HasFocus? Colors.Base.HotFocus: Colors.Base.HotNormal)+ Driver.SetAttribute (HasFocus? ColorScheme.HotFocus: ColorScheme.HotNormal)

hot_pos != -1

1

Move(4 + hot_pos, 0)

hot_pos != -1

1

Drivers.SetAttribute(
HasFocus?
ColorScheme.HotFocus :ColorScheme.HotNormal)

Driver.AddCh(hot_key)

Move(4 + hot_pos, 0)

1

1

Exit Redraw(Terminal.Rect)

2

Drivers.SetAttribute(
HasFocus?
Colors.Base.HotFocus :Colors.Base.HotNormal)

Driver.AddCh(hot_key)

1

2

2

Move(4 + hot_pos, 0)

2

12

Drivers.SetAttribute(
HasFocus?
ColorScheme.HotFocus :ColorScheme.HotNormal)

1

Drivers.SetAttribute(
HasFocus?
Colors.Base.HotFocus :Colors.Base.HotNormal)

2

Driver.AddCh(hot_key)

2

Exit Redraw(Terminal.Rect)

12

12

Exit Redraw(Terminal.Rect)

12

Figure 3: Construction of a 𝛿-PDG from two versions — 1 and 2 — of a program. Version 2 is obtained from version 1 byapplication of the patch shown in the program. Each node is annotated with the version number it is present in.
The WL Graph Kernel 𝐾 is a meta-kernel that extends an underlying kernel. We want a Subtree WL Graph Kernel that counts thenumber of identical rooted subtrees for each node in the graph ofthe same depth as the iteration. In our case, this maps to identical
downstream behaviour from each node in terms of each of the flows
considered. To achieve this behaviour, we set 𝐾 to be the Vertex
Label Histogram Kernel and encode outgoing flow types in the label
function. This kernel is defined as follows: Let Ψ be a function thatembeds the graph into a vector space, often called a feature map inliterature, and let ⟨·, ·⟩ be the inner product, thenΨ(𝐺) = f;f𝑖 = |{𝑣 | 𝑣 ∈ 𝑉 (𝐺), 𝑙𝑖 ∈ L, 𝑙𝑣 (𝑣) = 𝑙𝑖 }| ;𝐾 (G)𝑖 𝑗 = ⟨Ψ(𝐺𝑖 ), Ψ(𝐺 𝑗 )⟩;For clustering, we opt for agglomerative clustering, like Herzig
et al. [6], Herzig and Zeller [7]. With node-neighbourhood pairwise
similarity information, we can build an affinity, i.e. a pair-wise
distance, matrix for clustering trivially by simply inverting thevalue, i.e. 1 − similarity. Section 4.2 details the implementation.

4

HEDDLE

Heddle realises Flexeme. Heddle first constructs a 𝛿-PDG for each
input file, and combines them into a 𝛿-NFG. Heddle then decomposes the 𝛿-NFG into a forest, and uses graph kernels to compute
distance matrices which we input into agglomerative clustering.
We close by describing how a project could adopt Heddle.

4.1 𝛿-PDG Construction
We implement both name flow extraction and PDG extraction in
Roslyn [20], the open-source compiler for C# and Visual Basic fromMicrosoft. We store the PDG in GraphViz Dot format. We thenimplement the PDG merging procedure as described above overthe dot files. This allows us to reuse the merging procedure; it islanguage agnostic. One need only provide PDGs (and optionallyname flows) as ‘dot’ files. To enable the merging process, we store
the origin line-span3 and method membership information in thenodes along with the usual data associated with such graphs, i.e.
expression information and edge kind. To obtain textual diffs neededfor 𝛿-NFG construction, we make use of the UNIX ‘diff’ tool.
By default, Heddle constructs one 𝛿-NFGs per file. To mitigate
the problems cross-file dependencies cause and reduce the cost ofuntangling, Heddle merges all graphs associated with a commit,
into a single structure. This merge uses node equivalence (Definition 3.5) when operating on files that share a namespace. A key
difference in the same-version, cross-file setting is that we need tocopy over both types of changed nodes and add the edges similar
to the added nodes scenario described in Section 3.
To simplify our code, our implementation of PDG extraction
does not consider goto statements in the Control Flow Graph; thisdoes not matter much in practice, as goto statements are very rarein our corpus.

4.2

Graph Node Clustering

We use GraKeL [26] for the Weisfeiler-Lehman (WL) Graph Kernel [25] implementation and leave the number of iterations of theisomorphism tests at the library’s default of 10. We set the underlying kernel to Vertex Histogram Graph Kernel to obtain the same
behaviour as the Subtree WL Graph Kernel.
For agglomerative clustering, we use SciPy [10]. We precomputethe affinity matrix by using the WL kernel similarity. We call theclustering method with the linkage parameter set to “complete”,
which mimics the behaviour described in Herzig et al. [7], i.e. when
two groups are merged, the maximal distance from any member ofthe group to any other group is kept as the new distance. We stop
merging groups when they are less than 0.5 similar to any othergroup instead of providing oracle information to the method. This
3 We consider code snippets at line granularity.

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USAmodels the fact that, in practice, developers do not know how many
concerns a commit contains.
Code for both 𝛿-PDG construction and node clustering is available online4 .

4.3

Deployability

Heddle takes ten seconds on average to untangle a commit (Section 6.2), and 45s on average to construct and merge the PDG for acommit into a 𝛿-PDG. This is beyond the one second limit suggested
by Nielsen [22] for processes that allow a user to feel like operating
directly on data, which suggests that our tools should be onboarded
into a process that is out-of-band with regards to developer attention. An example of such a process is the build automation within
continuous deployment. Heddle could be added as an additional
pass at the end of the build process providing an untangle reportfor the code reviewers, ready to be inspected when the review process starts. Further, on-boarding Heddle in such a manner makes
it independent of the workflow and tooling choices made by thedevelopers; the system would only need to be deployed on the build
servers. The report provided would allow reviewers to better focus
on the different parts of the patch and aid patch comprehension.
There is an initial onboarding cost requiring generating NFGs forall source files in the code-base. However, our construction is incremental and for any fresh patch that needs integration into the
𝛿-NFG, we only need to consider the files touched by the patch.

5

EXPERIMENTAL DESIGNIn this section, we discuss how we constructed a dataset, measure untangling performance and our reproduction of two baseline
methods.

5.1

Corpus Construction

To construct our corpus, we reuse Herzig et al. [6] methodology
who artificially tangle atomic commits. Therefore, we consider
commits that:(1) Have been committed by the same developer within 14 daysof each other with no other commit by the same developer
in between them.
(2) Change namespaces whose names have a large prefix match.
(3) Contain files that are frequently changed together.
(4) Do not contain certain keywords (such as ‘fix’, ‘bug’, ‘feature’,‘implement’) multiple times.
The first criterion mimics the process by which a developer forgets to commit their working directory before picking up a newtask. The next criterion is an adaptation of Herzig et al.’s ‘Change
close packages’ criterion to the C# environment. The third considers files that are coupled in the version history, thus creatinga tangled commit not too dissimilar from commits that naturally
occurred. The intuition being that if commit 𝐴 touches file 𝑓𝐴 andcommit 𝐵 touches file 𝑓𝐵 , s.t. 𝑓𝐴 and 𝑓𝐵 are frequently changed
before(coupling) [31], then 𝐴 and 𝐵 should be tangled. The final
criterion is a heuristic to ensure that we do not consider tangling
commits that we are certain are not atomic. We add this condition
to mitigate the problem of tangling actually tangled commits which
4 https://pppi.github.io/Flexeme/

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr

Table 1: Project statistics. The last revision indicates the commit at which we performed the ‘git clone’.
Project
Commandline
CommonMark
Hangfire
Humanizer
Lean
Nancy
Newtonsoft.Json
Ninject
RestSharp

LOC
11602
14613
40263
56357
242974
79192
71704
13656
16233

# of Commits
1556
418
2889
1647
7086
5497
299
784
1440

Last revision
67f77e1
f3d5453
175207c604ebcc
71bc0fa
dbdbe94
4f8832a6a7ed2bb52b9bewould cause an issue when computing ground truth. Overall, thisartificially created corpus mimics some of the tangled commits we
expect developers to make; specifically, it captures the intuition ofa developer committing multiple consecutive work units as a single
patch. Section 7 discusses the threat this poses to Heddle’s validity.
Following the above procedure, we obtain a shortlist of chainsof SHAs of varying length for nine C# systems; we show project
statistics in Table 1. These SHAs refer to atomic commits. We sanity check that they are atomic by uniformly sampling 30 commits
from our corpus and examining each commit for up to five minutes.
We found 27/30 to be atomic, 2 of the tangled commits refactor
comments (which are invisible and therefore atomic to Heddle),
and 1 tangled commit due to merging content from a different
versioning system (SVN) in a single commit. From this study, we
extracted two heuristics that we used to filter out non-atomic commits. Specifically, we excluded all merge commits and those thatgenerate 𝛿-PDGs that have no changed nodes.
We attempt to create tangled commits by selecting the SHAs in
the tail of these chains and git cherry-picking them onto the head.
We then mark the originating commit in the tangled diff using theindividual atomic diffs as not all selections are successful. Some ofthe successful selections may not have changes from all tangledcommits as later commits may shadow them. Therefore, we performa final pass to learn the actual number of surviving concerns. In
the end, we built two sets of tangled commits: those that tangle 2
and those that tangle 3. This models the most common numbers oftangled concerns in the wild [6, Figure 7].
Table 2 shows the final statistics for our corpus, where the number of concerns is the count of surviving concerns at the end of theselection process. We report all successfully generated data-points
and detail, in Section 6, the subsets on which we compared any
two methods when at least one of them did not run on the full
corpus due to time-outs. We do not treat time-outs as a zero accuracy result, but drop them from consideration. We remark that the
primary source of time-outs is the computational cost of running
our reproduction of Herzig et al..

5.2

Experimental Setup

Our experiments assess how well our method recovers the original commits compared to the baseline methods proposed by Barnett et al. [2] and Herzig et al. [6]. Additionally, we measure theruntime cost of the different methods. For this, all methods are runFlexeme: Untangling Commits Using Lexical Flows

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

Table 2: Successfully tangled commits.
Project
Commandline
CommonMark
Hangfire
Humanizer
Lean
Nancy
Newtonsoft.Json
Ninject
RestSharp
Overall

2
308
52
229
85
154
284
84
82
95
1373

Concerns
3 Overall
32
340
0
52
87
316
4
89
24
178
67
351
7
91
0
82
18
113
239
1612

in isolation on the same high-end laptop (i7-8750H @ 3.20 GHz, 16
GB RAM @ 2666 MHz) and we compute accuracy for all methods
as follows:
𝐴=#Correctly labeled nodes.
#Nodes in graph(1)

Both baselines, as well as Heddle, may recover an arbitrary permutation of the ground truth labels. To avoid artificially penalisingthem, we first use the Hungarian Algorithm [15] to find the permutation that maximises accuracy. Consider the ground truth ‘[01122]’,
should a tool output ‘[20011]’, a naïve approach would award it
0.0 accuracy, while a trivial permutation of the labelling function
reveals that this is indeed 1.0 accuracy. We report this maximal
accuracy for each method.
For the purpose of timing, we perform one burn-in run of commit segmentation followed by 10 repeats that are used to computethe runtime cost. We then obtain the speed-up factor as a nonparametric pairwise comparison between the methods. Notably,
we do not include the cost of the static analysis required for eachmethod, rather only the cost of segmentation. This is due to deriving the required program representations for each method as aprojection from the 𝛿-NFG.

5.3

Reproducing Barnett et al. and Herzig et al.

In order to use Barnett et al.’s method as a baseline, we had to reimplement it, because its source is not public. Their method rests
on def-use chains. They retain all def-use chains that intersect adiff hunk in a commit. To obtain this, we first recover the dataflow
graph and then we separate the flows by ‘kill’ statements, such as assignments. In a 𝛿-PDG, this becomes a def-use chain projected onto
a diff hunk. Two chains are equivalent if (a) they are both changed
and are both uses of the same definition or (b) they are a changed
use of a changed definition. Under this partition, they divide theparts into trivial and nontrivial. All diff-regions in a trivial part fallwithin a single method. To avoid overwhelming developers withchains that are highly likely to be atomic, they do not show trivial
parts; implicitly, they are assuming that developers can see andavoid method-granular tangling. In contrast, we, like Herzig et al.,consider method-granular tangling, so our re-implementation does
not distinguish trivial and non-trivial parts.

To reproduce Herzig et al.’s method, we reconstruct the callgraph by collapsing into hypernodes by method membership, werecover the dataflow from the 𝛿-PDG, and we additionally generate
an occurrence matrix specifying the files changed by a commit, as
well as file sizes in terms of number of lines. Finally, we computea diff-region granular corpus for all the successful tangles, as the
Herzig et al. algorithm works at a diff-region granularity. Using thisinformation, we construct a distance matrix for each tangled commit. This distance matrix is populated by the sum of the distancesfrom each individual voter. All confidence voters are identical tothe original paper with one exception. We replaced package distance by namespace distance; we do, however, compute it in thesame manner. At evaluation time, we also provide the number ofconcerns to be untangled. This is known by construction, as in
the original paper. We perform agglomerative clustering on the
resultant matrix using complete linkage, i.e. taking the maximum
distance over all diff-regions within a cluster.
We also create a version of Herzig et al.’s confidence votersmethod that operates directly on 𝛿-PDGs, which we call 𝛿-PDG+CV.
The last stage here is not dissimilar to flexeme, with the remarkthat we still provide Herzig et al.’s approach with oracle access tothe number of concerns while flexeme requires only a similarity
threshold. We implemented the voters so that only file distanceand change coupling require auxiliary information. This is precomputed from the git history of the project under analysis. Everyother voter — call graph distance, data dependency and namespace
distance — are computed on demand only for the nodes that we
consider for merging.
For both baselines, as well as Heddle, we measure only the time
taken to untangle and not the construction of auxiliary structures.
We exclude the construction time as we derive the DU-chains, callgraphs and dataflow-graphs from our 𝛿-PDG.

6

RESULTSIn this section, we compare Heddle against our two baselines, interms of accuracy and runtime. To implement our baselines, we
reproduced the methodology and tooling from Herzig et al. [6]and Barnett et al. [2]. We show that Heddle outperforms, in bothaccuracy and run-time, our reproduction of Herzig et al.’s method.
We report comparisons between tools only on the subset of datapoints on which both tools run to completion.

6.1

Untangling Accuracy

When recovering the original partition of the 𝛿-NFG from our artificial tangle of code concerns, Heddle achieves a median accuracyof 0.81 and a high of 0.84 on the project Nancy; it outperforms
Herzig et al. by 0.14 and trails 𝛿-PDG+CV only by 0.02 while scaling better to big patches. Unlike Herzig et al., Heddle achieves thisresult without resorting to heuristics or manual feature construction.
Heddle outperforms both baselines in accuracy, the difference
being statistically significant at 𝑝 < 0.001 (Wilcoxon pair-wise test),
and matches the performance of 𝛿-PDG+CV, the new technique
we have built from grafting Herzig et al.’s confidence voters on topof our 𝛿-NFG (𝑝 = 0.76, Wilcoxon pair-wise test). Unlike Heddle,
the other approaches consider file-granular features. Specifically,

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr

Table 3: Median performance of untangling commits for each method by project and number of tangled concerns. The performance differences are significant to 𝑝 < 0.001 for all overall results according to a two-tailed Wilcoxon pair-wise test on thecommon set of data-points, except 𝛿-PDG+CV vs heddle, which is significant to 𝑝 < 0.001. Entries indicated by a ‘*’ signifythat there was no relevant data point to report the performance on and those indicated by ‘x’ indicate time-outs.
Project Name
Commandline
CommonMark
Hangfire
Humanizer
Lean
Nancy
Newtonsoft.Json
Ninject
RestSharp
Overall

2
0.18
0.20
0.16
0.18
0.19
0.09
0.15
0.14
0.12
0.14

Barnett et al. [2]3Overall
0.21
0.19
*
0.20
0.13
0.15
0.31
0.18
0.12
0.18
0.08
0.09
0.11
0.15
*
0.14
0.14
0.12
0.11
0.13

2
0.67
0.65
0.70
0.64
0.69
0.70
0.71
0.57
0.71
0.69

Herzig et al. [6]3Overall
0.48
0.64
*
0.65
0.54
0.64
0.42
0.62
0.62
0.69
0.56
0.67
0.56
0.71
*
0.57
0.69
0.70
0.62
0.67

2
0.77
0.90
0.84
0.69
0.84
0.86
0.86
0.94
0.74
0.83

𝛿-PDG+CV3
Overall
0.84
0.80
*
0.90
0.88
0.87
x
0.69
0.71
0.84
0.80
0.86
0.69
0.82
*
0.94
0.53
0.70
0.84
0.83

Heddle (𝛿-NFG + WL)
2
3
Overall
0.82
0.92
0.82
0.70
*
0.70
0.86
0.68
0.79
0.83
0.57
0.81
0.77
0.82
0.80
0.81
0.92
0.84
0.71
0.52
0.71
0.80
*
0.80
0.82
0.89
0.82
0.81
0.84
0.81

Table 4: Median time taken (s) to untangling commits for each method by project and number of tangled concerns up to 3
sig figs. The runtime cost differences are significant to 𝑝 < 0.001 for all overall results according to a two-tailed Wilcoxon
pair-wise test, except 𝛿-PDG+CV vs Heddle, where the difference is not statistically significant (𝑝 = 0.51). Entries indicated bya ‘*’ signify that there was no relevant data point to report the performance on and those indicated by ‘x’ indicate time-outs.
Project Name
Commandline
CommonMark
Hangfire
Humanizer
Lean
Nancy
Newtonsoft.Json
Ninject
RestSharp
Overall

2
0.10
2.56
1.15
0.44
1.00
2.06
2.14
1.25
0.74
1.02

Barnett et al. [2]3Overall
8.51
0.12
*
2.56
4.97
1.95
0.23
0.41
1.59
1.28
5.63
2.42
6.42
2.35
*
1.25
1.25
0.78
5.02
1.41

Herzig et al. [6]𝛿-PDG+CV2
3
Overall 2
3
Overall
10.51
8.56
9.26
0.42
153.55 0.59
1.96×103 *1.96×103 10.38
*
10.38
4
4
1.30×10 5.57×10 1.72×104 10.61
123.99 13.84
40.62
49.53
44.44
9.24
x
9.24
345.05 173.58 288.35 19.28
17.08
19.28
570.57 1.29×103 600.16 22.04
20.52
21.96
225.62 510.77 230.49 20.04
51.54
20.32
81.53
*
81.53
4.52
*
4.52
46.22
222.98 72.09
7.80
1.01
4.99
81.53
647.99 117.35 7.17
70.35
10.27

they compute a probability that two files are changed together, and,by proxy, tackle the same concern, from the version history. This
allows them to better cluster related changes that span multiple
files. Heddle, in such cases, relies only on the existence of call edges
between the different files when projected onto a 𝛿-NFG. Further,
Herzig et al. has oracle access to the number of concerns while
heddle has not. Despite the lack of explicit file-level relationships
or oracle access, Heddle’s accuracy matches confidence voterswhen applied to 𝛿-NFGs, and outperforms them when they areapplied to diff-regions.
Of the four methods we consider, our re-implementation of Barnett et al.’s method (Section 5.3) produces the lowest median accuracy — 0.13. We believe that two reasons account for this accuracy.
First, we evaluate our re-implementation on trivial parts. Second,
Barnett et al. speculate that their high FN rate is due to relations,like method calls, that def-use chains miss [2, §VI.A]. We emphasisethat Barnett et al. performed much better in its native setting. They
built their approach for Microsoft developers and the commits theyhandle on a daily basis. Section 7 details the threats to Heddle’s

Heddle (𝛿-NFG + WL)
2
3
Overall
0.85
182.62 1.04
14.95
*
14.95
8.06
45.29
11.64
4.86
2.56
4.58
18.07
24.07
18.23
18.38
85.55
21.78
8.01
11.98
8.58
14.99
*
14.99
9.86
26.25
10.11
7.99
43.29
9.56

validity this difference in methodology incurs. Section 8.2 further
details their approach and evaluation and its differences to Heddle.
When considering accuracy for an increasing number of concerns (See Figure 4), only Barnett et al. and Herzig et al. reportstatistically significant performance drops (𝑝 < 0.01 and 𝑝 < 0.001
according to a Mann-Whitney U test). Barnett et al.’s drop is, however, not observable at two decimal points, while Herzig et al.’sdrop is by 0.07. Both 𝛿-NFGs-based tools report statistically indistinguishable results as the number of concerns increases.
As heddle is not privy to the number of concerns, its behaviouron atomic commits is interesting. When we apply heddle to atomic
commits, they are correctly identified as atomic with 0.63 accuracy.
This results is when we ask the the yes/no question ‘Is this commit
atomic?’. We also want to determine how wrong heddle is whencreating spurious partitions. For this, we consider the node-levelaccuracy of heddle. The result is 0.93, suggesting that heddle
often mislabels a small number of changed nodes.
Table 3 shows detailed per project results broken down by projectand number of concerns for each of the four untangling techniques.

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

1.0

107

0.8

105

0.6

103

Time (s)Accuracy

Flexeme: Untangling Commits Using Lexical Flows

0.4

0.2

Concepts23

0.0
Barnett et al.

Herzig et al.

δ-PDG + CV

Concepts
2
3

101

10−1

10−3

Heddle (δ-NFG + WL)

MethodBarnett et al.

Herzig et al.

δ-PDG + CV

Heddle (δ-NFG + WL)

Method(a) Accuracy(b) Runtime

Figure 4: Boxplot comparing the accuracy of the baseline and Heddle (Figure 4a) as well as time taken (s) to segment acommit (Figure 4b) for all projects. The drop in accuracy for Herzig et al.’s approach as the number of concerns increases issignificant to 𝑝 < 0.001 and Barnett et al.’s to 𝑝 < 0.01 according to a Mann-Whitney U test. The results of the same test for
𝛿-PDG+CV and Heddle indicate that there is no statistically significant difference (𝑝 = 0.28 and 𝑝 = 0.76 respectively). All
increases in time taken to segment are statistically significant (𝑝 < 0.001, Mann-Whitney U test).

6.2

Untangling Running Time

Figure 4b shows that Barnett et al. [2]’s def-use chain technique isby far the fastest. This result is expected because the algorithm is,
at its core, strongly connected components detection over a sparsegraph, and is therefore linear in the number of nodes in def-use
chains that contain at least one addition. However, as we havepreviously seen in Table 3, its accuracy is considerably worse.
Heddle is 32 times faster than Herzig et al. in a pair-wise ratio test. Where 𝑛 is the number of diff-regions, the Herzig et al.
technique requires 𝑛 2 shortest path computations, each requiring
the solution of 𝑛 2 reachability queries over the dataflow graph.
Consider the sparse occurrence matrix that encodes which commit
touched which file; its dimensions are the number of commits by
number of files that ever existed in the repository. Herzig et al.’stechnique also sums each row of this matrix. Although their technique needs these steps only to populate the distance matrix before
agglomerative clustering, these operations are expensive and must
be computed for all diff-regions within a patch. The fact that theirtechnique is heavy weight is unsurprising.
When compared to 𝛿-PDG+CV, the performance on graphs tangling only two concerns is comparable; however, Heddle scales
better as the number of concerns, and the number of changed nodes
increases. We estimate the runtime of both Heddle and 𝛿-PDG+CV
using a robust linear model regression and fitting a second orderpolynomial in the number of changed nodes (𝑛). We find Heddle
to scale with 𝑡 = 0.3371 − 0.0041𝑛 + 0.0015𝑛 2 , 𝑅 2 = 1.00 and 𝛿PDG+CV with 𝑡 = 0.8794 − 0.0528𝑛 + 0.0019𝑛 2 , 𝑅 2 = 0.99. At 500
nodes changed, which is common in our dataset, this would accountfor a difference of 68 seconds.

Finally, we compute the pair-wise ratio of runtimes and find that
Heddle is, over the median of these ratios, 9 times slower thanBarnett et al. and 32 times faster than Herzig et al. at untangling
commits, taking, on average, ten seconds per commit.

7

THREATS TO VALIDITY

Heddle faces the usual threat to its external validity: the degree towhich its corpus of commits across a set of projects is representative. The fact that we construct tangled commits exacerbates thisthreat and introduces the construct validity threat that commitsthat we assume are atomic, are not, in fact, atomic. To address
the latter threat, we validated the atomicity of the commits, fromwhich we built tangled commits, on a small, uniform sample of
30 commits across our corpus. As is conventional, we choose 30
because this is typically when the central limit theorem starts toapply [8]. We did not validate the representativeness of our corpus
against a real-world sample of tangled commits. Ground truth inreal-world samples can be hard to identify, so we opted to use themethodology from Herzig et al. [6] to create an artificial corpusthat mimics some tangled commits we expect developers to make;it captures the intuition of a developer committing multiple consecutive work units as a single patch. This decision restricts our results
only to the type of tangled commits we mimic, which generalise
only in so far as our algorithmically tangled commits generalise.
Further, like Barnett et al., we evaluated Heddle only on C# files,
so, despite Flexeme’s language-agnosticism, Heddle’s result may
not generalise to other languages.
Our re-implementations of Herzig et al.’s and of Barnett et al.
may contain errors. Section 5.3 details these re-implementations

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

and where they differ from their authors’ descriptions of the original
implementations. Finally, we published these re-implementations
at https://pppi.github.io/Flexeme/, so other researchers can vet ourwork.
We borrowed Herzig et al.’s commit untangling evaluation strategy wholesale, as Section 5.1 and Section 5.2 detail. Thus, we wereable to directly compare our work with theirs. Barnett et al. opted
for a different evaluation strategy (Section 8.2), because obtaininga ground truth for their evaluation is too time-consuming in their
setting. Thus, we can neither directly compare Heddle against
their approach, nor assess our re-implementation relative to theirtool. They also conducted a user study showing both a developer
need for such tooling and that their suggestions are useful. Because
we did not conduct a user study, our results lack the sanction ofdeveloper approval.

8

RELATED WORK

We first discuss the impact of tangled commits both on developers
and researchers. We then discuss approaches to untangling suchcommits followed by a discussion of multiversion representations.
We conclude with a discussion of graph kernels.

8.1

Impact of Tangled Commits

Tao et al. [27] were amongst the first to highlight the problem ofchange decomposition in their study on code comprehension; theyhighlight the need for decomposition when many files are touched,multiple features implemented, or multiple bug fixes committed.
The latter is diagnosed by Murphy-Hill et al. [21] as a deliberate
practice to improve programmer productivity. Tao et al. conclude
that decomposition is required to aid developer understanding ofcode changes.
Independently, Herzig et al. [6, 7] investigate the impact of tangled commits on classification and regression tasks within software
engineering research. The authors manually classify a corpora ofreal-world changesets as atomic, tangled or unknown, and findthat the fraction of tangled commits in a series of version histories
ranges from 7% to 20%; they also find that most projects containa maximum of four tangled concerns per commit, which is consistent with previous findings by Kawrykow and Robillard [11].
They find non-atomic commits significantly impact the accuracy ofclassification and regression tasks such as fault localisation.

8.2

Untangling Commits into Atomic Patches

It is natural to think of identification of communities in the 𝛿-NFG asa slicing problem [28]. However, boundaries across concerns do notnaturally map to a slicing criterion; it is unclear how to seed a slicing
algorithm and when to terminate it. This is because concerns arelinked with multiple edges which makes their separation difficult
to specify with a slicing criterion. In the rest of this section, we
discuss the literature around the problem of tangled commits andthe theoretical foundations of flexeme.
Research on the impact of both tangled commits and non-essential
code changes prompted an investigation into changeset decomposition. Herzig et al. [6, 7] apply confidence voters in concert withagglomerative clustering to decompose changesets with promising

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr

results, achieving an accuracy of 0.58-0.80 on an artificially constructed dataset that mimics common causes of tangled commits.
In contrast, Kirinuki et al. [13, 14] compile a database of atomic
patterns to aid the identification of tangled commits; they manuallyclassify the resulting decompositions as True, False, or Unclear,and find more than half of the commits are correctly identified astangled. The authors recognise that employing a database introduces bias into the system and may necessitate moderation via
heuristics, such as ignoring changes that are too fine-grained or
add dependencies.
Other approaches rely on dependency graphs and use-define
chains: Roover et al. [23] use a slicing approach to segment commits across a Program Dependency Graph, and correctly classify
commits as (un)tangled in over 90% of the cases for the systems studied, excluding some projects where they are hampered by toolchain
limitations. They propose, but do not implement, the use of System Dependency Graphs to reduce some of the limitations of theirapproach, such as being solely intraprocedural. Flexeme tackles
interprocedural and cross-file dependencies by merging the 𝛿-PDGsof the files touched by a commit.
Barnett et al. [2] implement and evaluate a commit-untangling
prototype. This prototype projects commits onto def-use chains,clusters the results, then classifies the clusters as trivial or nontrivial. A cluster is trivial if its def-use chains all fall into the same
method. Barnett et al. employ a mixed approach to evaluate their
prototype. They manually investigated results with few non-trivial
clusters (0-1), finding that their approach correctly separated 4 of
6 non-atomic commits, or many non-trivial clusters (> 5), finding
that, in all cases, their prototype’s sole reliance on def-use chainslead to excessive clustering. For results containing 2–5 clusters,
they conducted a user-study. They found that 16 out of the 20 developers surveyed agreed that the presented clusters were correctand complete. This result is strong evidence that their lightweightand elegant approach is useful, especially to the tangled commitsthat Microsoft developers encounter day-to-day. During the interviews, multiple developers agreed that the changeset analysed did
indeed tangle two different tasks, sometimes even confirming thatdevelopers had themselves separated the commit in question after
review. In addition to validating their prototype, their interviews
also found evidence for the need for commit decomposition tools.
Because they use def-use chains and ignore trivial clusters, Barnett et al.’s approach can miss tangled concerns that Flexeme candiscern. Barnett et al.’s user study itself shows that this can matter:it reports that some developers disagreed with the classification ofsome changesets as trivial.
Dias et al. [4] take a more developer-centric approach and propose the EpiceaUntangler tool. They instrument the Eclipse IDE anduse confidence voters over fine-grained IDE events that are later
converted into a similarity score via a Random Forest Regressor.
This score is used similarly to Herzig et al. [6]’s metrics, i.e. to perform agglomerative clustering. They take an instrumentation-based
approach to harvest information that would otherwise be lost, suchas changes that override earlier ones. This approach also avoids
relying on static analysis. They report a high median success rateof 91% when used by developers during a two-week study. While
Dias et al. sidestep static analysis, they require developers to use an
instrumented IDE. Heddle is complementary to EpiceaUntangler: itFlexeme: Untangling Commits Using Lexical Flows

allows reviewers to propose untanglings of code that may originate
from development contexts where instrumentation might not be
possible.

8.3

Multiversion Representations of CodeRelated work has considered multiversion representations of programs for static analysis. Kim and Notkin [12] investigate the applicability of different techniques for matching elements between
different versions of a program. They examine different program
representations, such as String, AST, CFG, Binary or a combinationof these as well as the tools that work on them on two hypothetical scenarios. They only consider the ability of the tools to match
elements across versions and leave the compact representation ofa multiversion structure as future work. Some of the conclusions
from the matching challenges presented by Kim and Notkin [12]are echoed in Flexeme as well, we make use of the UNIX diff as it isstored within version histories; however, we also make use of linespan hints from the compilers for each version of the application
to better facilitate matching nodes within a NFG.
Le et al. [16] propose a Multiversion Interprocedural Control
Graph (MVICFG) for efficient and scalable multiversion patch verification over systems such as the PuTTY SSH client. Our 𝛿-PDG is a
generalisation of this approach to a more expressive data structure,with applications beyond traditional static analysis.
Alexandru et al. [1] generalise the Le et al. MVICFG construction
to arbitrary software artefacts by constructing a framework thatcreates a multiversion representation of concrete syntax trees fora git project. They adopt a generic ANTLR parser, allowing them
to be language agnostic, and achieve scalability by state sharing
and storing the multi-revision graph structure in a sparse data
structure. They show the usefulness of such a framework by meansof ‘McCabe’s Complexity’, which they implement in this framework
such that it is language agnostic, does not repeat computations
unnecessarily and reuses the data stores in the sparse graph bypropagating from child to parent node. Sebastian and Harald [24]propose a compact, multiversion AST that cleverly shares stateacross versions. Flexeme, in contrast, rests on PDGs and is wellsuited for the untangling tasks, as our evaluation demonstrates.

8.4

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

the ground up to rewrite commits as developer make history. As
such Flexeme and semantic slicing are complementary: Flexeme
would improve the signal to noise ratio of semantic slicing. Aninteresting direction for future work would be to use Flexeme topreprocess version histories prior to semantically slicing them aswith Definer [18].

8.5Graph Kernels

Real world data is often structured, from social networks, to protein
interactions and even source code. Knowing if a graph instanceis similar to another is useful if we wish to make predictions onsuch data by means that employ either similarity or distance. Vishwanathan et al. [29] provide a unified framework to study graphkernels, bringing previously defined kernels under a common umbrella and offering a new method to compute graph kernels on
unlabelled graphs in a fast manner, reducing the asymptotic costfrom 𝑂 (𝑛 6 ) to 𝑂 (𝑛 3 ). They mainly study the construction of the different graphs and demonstrate the run-time improvement without
applying it to a downstream prediction task. Shervashidze et al. [25]introduce the Weisfeiler-Lehman Graph kernel, which they evaluate with three underlying kernels — subtree, edge histogram, andshortest path — on several chemical and protein graph datasets.
Although code is often represented as a graph structure and themethods presented here are also used by us to compute graph similarity, this literature primarily concerns itself with chemical andsocial network datasets that have become standardised benchmarks.

9

CONCLUSION

We have presented Flexeme— a new approach to commit untangling. Flexeme’s realisation in heddle advances the state-of-the-art:
it is 0.14 more accurate (achieving 0.81) and 32 times faster than theprevious state-of-the-art. This result rests on a novel data structure,𝛿-NFG, which augments a multiversion program dependence graph(also introduced in this paper) with name flows. 𝛿-NFG facilitate
dual-channel reasoning across versions. Thus, we believe that 𝛿NFG will be useful on tasks other than commit untangling, suchas code refactoring, notably renaming, or code summarisation, as
when suggesting docstrings.

Semantic Slicing of Version Histories

Features in a system often co-evolve, which tangles the changes
made for a one high-level feature with others in a version history.
To resurface feature-specific changes, they dynamically slice a target version, then walk backwards in history while they can reverse
the intra-version patch without conflict; at each version they reach,they add any commit that contains a hunk that touches the current
slice to it. The goal of this semantic slicing of version histories
is to find a minimal slice of a version history that captures theevolution of a feature. Li et al. [17, 19] first formulated and introduced this problem. Semantic slicing is a form of commit untangling
backwards through history. This retrospective framing is why theytreat the history as immutable. In this initial solution, Li et al. treat
commits as atomic so their slices may contain noise introducedby tangled commits. To reduce this noise, Li et al., in more recent
work [18], unpack commits into single-file commits into a private,
local history. Flexeme, in contrast, is static and online: built fromACKNOWLEDGEMENTS
This research was supported by the EPSRC Ref. EP/J017515/1 and
EPSRC Ref. EP/P005314/1.

REFERENCES[1] Carol V Alexandru, Sebastiano Panichella, Sebastian Proksch, and Harald C Gall.
2019. Redundancy-free analysis of multi-revision software artifacts. Empirical
Software Engineering 24, 1 (2019), 332–380.
[2] Mike Barnett, Christian Bird, João Brunet, and Shuvendu K. Lahiri. 2015. Helping
developers help themselves: Automatic decomposition of code review changesets.
Proc. - Int. Conf. Softw. Eng. 1, August 2014 (2015), 134–144. https://doi.org/10.
1109/ICSE.2015.35[3] Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr. 2018. RefiNym: Using
Names to Refine Types. In Foundations of Software Engineering (FSE).
[4] Martin Dias, Alberto Bacchelli, Georgios Gousios, Damien Cassou, and Stephane
Ducasse. 2015. Untangling fine-grained code changes. In 2015 IEEE 22nd Int.
Conf. Softw. Anal. Evol. Reengineering, SANER 2015 - Proc. IEEE, 341–350. https://doi.org/10.1109/SANER.2015.7081844 arXiv:1502.06757[5] Jeanne Ferrante, Karl J. Ottenstein, and Joe D Warren. 1984. The program dependence graph and its use in optimization. In Lect. Notes Comput. Sci. (including

ESEC/FSE ’20, November 8–13, 2020, Virtual Event, USA

Subser. Lect. Notes Artif. Intell. Lect. Notes Bioinformatics), Vol. 167 LNCS. 125–132.
https://doi.org/10.1007/3-540-12925-1_33[6] Kim Herzig, Sascha Just, and Andreas Zeller. 2016. The impact of tangled codechanges on defect prediction models. Empir. Softw. Eng. 21, 2 (2016), 303–336.
https://doi.org/10.1007/s10664-015-9376-6[7] Kim Herzig and Andreas Zeller. 2013. The impact of tangled code changes. IEEE
Int. Work. Conf. Min. Softw. Repos. (2013), 121–130. https://doi.org/10.1109/MSR.
2013.6624018[8] Robert V. Hogg, Elliot A. Tanis, and Dale L. Zimmerman. 2020. Probability andstatistical inference. Pearson.
[9] Robert W. Irving and David F. Manlove. 2002. The Stable Roommates Problem
with Ties. J. Algorithms 43, 1 (April 2002), 85–105. https://doi.org/10.1006/jagm.
2002.1219[10] Eric Jones, Travis Oliphant, Pearu Peterson, et al. 2001–. SciPy: Open source
scientific tools for Python. http://www.scipy.org/ [Online; accessed 17.08.2018].
[11] David Kawrykow and Martin P. Robillard. 2011. Non-essential changes in version
histories. Proceeding 33rd Int. Conf. Softw. Eng. - ICSE ’11 (2011), 351. https://doi.org/10.1145/1985793.1985842[12] Miryung Kim and David Notkin. 2006. Program element matching for multiversion program analyses. In Proceedings of the 2006 international workshop on
Mining software repositories. 58–64.
[13] Hiroyuki Kirinuki, Yoshiki Higo, Keisuke Hotta, and Shinji Kusumoto. 2014. Hey!
are you committing tangled changes?. In Proc. 22nd Int. Conf. Progr. Compr. (ICPC2014). ACM Press, New York, New York, USA, 262–265. https://doi.org/10.1145/
2597008.2597798[14] Hiroyuki Kirinuki, Yoshiki Higo, Keisuke Hotta, and Shinji Kusumoto. 2017.
Splitting commits via past code changes. Proc. - Asia-Pacific Softw. Eng. Conf.
APSEC (2017), 129–136. https://doi.org/10.1109/APSEC.2016.028[15] H. W. Kuhn. [n.d.]. The Hungarian method for the assignment problem. Naval
Research Logistics Quarterly 2, 1–2 ([n. d.]), 83–97. https://doi.org/10.1002/nav.
3800020109[16] Wei Le and Shannon D. Pattison. 2014. Patch verification via multiversion
interprocedural control flow graphs. Proc. 36th Int. Conf. Softw. Eng. - ICSE 2014(2014), 1047–1058. https://doi.org/10.1145/2568225.2568304[17] Yi Li, Julia Rubin, and Marsha Chechik. 2015. Semantic slicing of software
version histories. In Proceedings of the 30th IEEE/ACM International Conference
on Automated Software Engineering. 686–696.

Profir-Petru Pârt, achi, Santanu Kumar Dash, Miltiadis Allamanis, and Earl T. Barr[18] Yi Li, Chenguang Zhu, Milos Gligoric, Julia Rubin, and Marsha Chechik. 2019.
Precise semantic history slicing through dynamic delta refinement. Autom. Softw.
Eng. 26, 4 (2019), 757–793. https://doi.org/10.1007/s10515-019-00260-8[19] Yi Li, Chenguang Zhu, Julia Rubin, and Marsha Chechik. 2018. Semantic Slicingof Software Version Histories. IEEE Trans. Softw. Eng. 44, 2 (2018), 182–201.
https://doi.org/10.1109/TSE.2017.2664824[20] Microsoft. [n.d.]. Microsoft Rosyln. https://github.com/dotnet/roslyn. Accessed:
31-05-2018.
[21] Emerson Murphy-Hill, Chris Parnin, and Andrew P. Black. 2012. How we refactor,
and how we know it. IEEE Trans. Softw. Eng. 38, 1 (2012), 5–18. https://doi.org/
10.1109/TSE.2011.41 arXiv:arXiv:1011.1669v3[22] Jakob Nielsen. 1993. Response times: the three important limits. Usability
Engineering (1993).
[23] De Roover and Ward Muylaert. 2017. Untangling Source Code Changes Using
Program Slicing. (2017).
[24] Panichella Sebastian and Proksch Harald. 2018. Redundancy-free Analysis ofMulti-revision Software Artifacts Redundancy-free Analysis of Multi-revision
Software Artifacts. May (2018).
[25] Nino Shervashidze, Pascal Schweitzer, Erik Jan van Leeuwen, Kurt Mehlhorn,
and Karsten M Borgwardt. 2011. Weisfeiler-lehman graph kernels. Journal of
Machine Learning Research 12, Sep (2011), 2539–2561.
[26] Giannis Siglidis, Giannis Nikolentzos, Stratis Limnios, Christos Giatsidis, Konstantinos Skianis, and Michalis Vazirgiannis. 2018. GraKeL: A Graph Kernel
Library in Python. arXiv preprint arXiv:1806.02193 (2018).
[27] Yida Tao, Yingnong Dang, Tao Xie, Dongmei Zhang, and Sunghun Kim. 2012.
How do software engineers understand code changes? Proc. ACM SIGSOFT 20thInt. Symp. Found. Softw. Eng. - FSE ’12 (2012), 1. https://doi.org/10.1145/2393596.
2393656[28] Frank Tip. 1994. A Survey of Program Slicing Techniques. Technical Report.
Amsterdam, The Netherlands, The Netherlands.
[29] S Vichy N Vishwanathan, Nicol N Schraudolph, Risi Kondor, and Karsten M
Borgwardt. 2010. Graph kernels. Journal of Machine Learning Research 11, Apr(2010), 1201–1242.
[30] B. Yu. Weisfeiler and A. A. Leman. 1968. Reduction of a graph to a canonicalform and an algebra arising during this reduction.
[31] Thomas Zimmermann, Andreas Zeller, Peter Weissgerber, and Stephan Diehl.
2005. Mining version histories to guide software changes. IEEE Transactions on
Software Engineering 31, 6 (2005), 429–445.