# A Novel Refactoring and Semantic Aware Abstract Syntax Tree Differencing
Tool and a Benchmark for Evaluating the Accuracy of Diff Tools

Pouria Alikhanifard<EMAIL_ADDRESS>and  Nikolaos Tsantalis
<EMAIL_ADDRESS>Concordia University1455 De Maisonneuve Blvd.
W.MontrealQuebecCanadaH3G 1M8

(2024)

###### Abstract.

Software undergoes constant changes to support new requirements, address bugs,
enhance performance, and ensure maintainability. Thus, developers spend a
great portion of their workday trying to understand and review the code
changes of their teammates. Abstract Syntax Tree (AST) diff tools were
developed to overcome the limitations of line-based diff tools, which are used
by the majority of developers. Despite the notable improvements brought by AST
diff tools in understanding complex changes, they still suffer from serious
limitations, such as (1) lacking multi-mapping support, (2) matching
semantically incompatible AST nodes, (3) ignoring language clues to guide the
matching process, (4) lacking refactoring awareness, and (5) lacking commit-
level diff support. We propose a novel AST diff tool based on RefactoringMiner
that resolves all aforementioned limitations. First, we improved
RefactoringMiner to increase its statement mapping accuracy, and then we
developed an algorithm that generates AST diff for a given commit or pull
request based on the refactoring instances and pairs of matched program
element declarations provided by RefactoringMiner. To evaluate the accuracy of
our tool and compare it with the state-of-the-art tools, we created the first
benchmark of AST node mappings, including 800 bug-fixing commits and 188
refactoring commits. Our evaluation showed that our tool achieved a
considerably higher precision and recall, especially for refactoring commits,
with an execution time that is comparable with that of the faster tools.

††copyright: acmcopyright††journalyear: 2024††doi:
XXXXXXX.XXXXXXX††conference: ACM Transactions on Software Engineering and
Methodology; ; ††price: 15.00††isbn: 978-1-4503-XXXX-X/18/06

##  1\. Introduction

Source code differencing is an important functionality for both software
engineering practitioners and researchers, as software is changing constantly
and there is a need to understand how and why it changed. Software developers
spend a significant portion of their workday trying to understand and review
the code changes of their teammates. Based on data collected from over 250
thousand developers (McLead, 2022), developers spend 41 minutes per day on
code reviewing and understanding code changes, which is almost as much time as
they spend on coding (52 minutes per day). MacLeod et al. (MacLeod et al.,
2018) surveyed 911 developers at Microsoft and found that the major challenge
faced by code reviewers is finding time to perform all the code reviews
requested of them, as well as understanding the code’s purpose, the
motivations for the change, and how the change was implemented. Ebert et al.
(Ebert et al., 2021) found that long or complex code change is the most
frequently experienced reason causing confusion in code reviews according to
developers. Regarding research, source code differencing is utilized to
extract change patterns that can be used for automated program repair (Le et
al., 2016; Nugroho et al., 2020), automated library migration (Ossendrijver et
al., 2022, 2023; He et al., 2021) and automated type/API migration (Ketkar et
al., 2019, 2022, 2020).

The majority of the diff tools used for code reviews including GitHub Pull
Request (GitHub Docs, 2023), Gerrit (Gerrit Code Review, 2023), as well as in-
house tools used by companies (e.g., the DiffTool used at Meta (Shan et al.,
2022)) are applying the Myers algorithm (Myers, 2023) at the text line
granularity (Nugroho et al., 2020). However, according to Falleri et al.
(Falleri et al., 2014) line-based diff has major limitations, as it only
computes additions and deletions, it does not consider other kinds of edit
actions, such as update and move, and it works at a coarse-grained granularity
(i.e., text line) that is not aligned with the source code structure (i.e.,
the abstract syntax tree). These limitations make it more difficult for code
reviewers to understand the changes intended by the commit authors when
inspecting a pull request, especially when the changes are complex and involve
refactoring operations, which tend to move code to new locations relatively
far from the original code locations (e.g., Extract Method (Fowler, 1999)).

To overcome these limitations Abstract Syntax Tree (AST) diff tools have been
developed. AST differencing aims at computing a sequence of edit actions
(called an edit script) that transform an AST into another (Falleri et al.,
2014). The typical edit actions supported by most tools are AST node updates,
additions, deletions, and moves. The most prominent AST diff tools are
ChangeDistiller (Fluri et al., 2007), GumTree (Falleri et al., 2014), IJM
(Iterative Java Matcher) (Frick et al., 2018), MTDiff (Dotzler and Philippsen,
2016), and CLDiff (Huang et al., 2018). Despite the notable improvements
brought by AST diff in understanding complex code changes, as shown in
experiments with professional developers (Escobar et al., 2022), AST diff
tools have some constraints, which make them generate edit scripts that are
not ideal or optimal from the change comprehension point of view, because they
do not reflect the actual changes intended by the commit author. Fan et al.
(Fan et al., 2021) proposed a differential testing approach that automatically
compares the similarity of mapped program elements by different AST mapping
algorithms, and found that GumTree, MTDiff and IJM generate inaccurate
mappings for 20%–29%, 25%–36% and 21%–30% of the file revisions, respectively.
Fan et al. concluded that based on their experimental results, the state-of-
the-art AST mapping algorithms still need improvements.

###  1.1. Motivation

The current AST diff tools are based on constraints that limit their ability
to generate accurate edit scripts, i.e., edit actions accurately reflecting
the changes intended by the commit author. Some of these constraints were
never addressed in the literature, while others were only partially addressed
with incomplete and non-evaluated solutions.

  1. Constraint 1:

“A given node can only belong to one mapping” (Falleri et al., 2014). This
constraint makes impossible for an AST diff algorithm to generate multi-
mappings (i.e., a node from the left AST having more than one corresponding
node in the right AST and vice versa). However, in reality developers tend to
merge duplicated code fragments into a single one to avoid redundancy (i.e.,
many-to-one multi-mapping) or duplicate a code fragment in multiple places to
reuse it (i.e., one-to-many multi-mapping). Currently, there is not even a
single AST diff tool in the literature supporting multi-mappings.

  2. Constraint 2:

“Mappings involve two nodes with identical labels” (Falleri et al., 2014).
Although this constraint seems sensible as it requires two AST nodes to have
the same AST type to be matched, it ignores the semantic role that an AST node
plays in the program. For example, type references, variable identifiers and
method call names are three semantically different groups of AST nodes, which
are all represented with the same AST type (i.e., SimpleName in the Eclipse
JDT parser). However, it makes no semantic sense to match nodes between these
three different groups.

  3. Constraint 3:

“The AST differencing problem inputs two ASTs and aims at identifying a short
edit script $\sigma$ of edit actions (including move) that transforms a first
AST (named $t_{1}$) into a second one (name $t_{2}$)” (Falleri et al., 2014).
This constraint restricts the AST diff problem to a pair of files, while in
reality a commit (or pull request) may include code being moved between
different files.

  4. Constraint 4:

“The algorithm is independent of any language specificity” (Falleri et al.,
2014). Although being language-independent may be considered a desirable
feature as it makes the algorithm easily extensible to other programming
languages, at the same time it hinders the ability of the algorithm to utilize
language-specific information (i.e., language clues), such as method
signatures, method calls, field accesses and refactorings, to guide more
effectively the AST matching process.

Through extensive experimentation and testing of various AST diff tools with
real case studies (i.e., commits) from open-source projects, we compiled a
catalogue with their limitations (Section 2) to demonstrate the negative
impact of these constraints on the accuracy and comprehensibility of the
generated edit scripts. Our work is the first attempt in the literature to
overcome all aforementioned constraints with the goal of generating highly
accurate edit scripts at commit (or pull request) level, and thus reduce the
time and effort it takes to perform code reviews and change comprehension
tasks, especially in complex change scenarios involving refactorings.

Moreover, the majority of AST diff tools have been evaluated based on the
number of generated mappings and the size of the resulting edit script,
without validating whether the mappings and edit actions are correct and
reflect the actual changes intended by the commit author. The assumption
behind this evaluation approach, as explained by Falleri et al. (Falleri et
al., 2014) is that “the length of the edit script is a proxy to the cognitive
load for a developer to understand the essence of a commit”. Thus, shorter
edit scripts should be easier to understand. However, in Section 2 we
demonstrate through real examples from open-source projects that shorter edit
scripts may confuse and mislead the code reviewers with edit actions that are
inconsistent with the actual changes applied by the commit author. We believe
that the most reliable way to evaluate AST diff tools is based on an
established ground truth of AST node mappings, which would make it possible to
assess the correctness of the mappings generated by the tools, and thus
compute their respective precision and recall. To this end, we created the
first benchmark of AST node mappings with commits from open-source projects.

###  1.2. Approach overview

To overcome all these limitations we propose and implement a refactoring,
semantic, and language-aware solution by extending RefactoringMiner (Tsantalis
et al., 2018, 2022) to generate AST diff at the commit level. RefactoringMiner
(Tsantalis, 2023) is a mature tool maintained over a period of 8 years by
members of our Refactoring Research Group at Concordia University. It
currently supports the detection of 60 different refactoring types and 40
kinds of API changes and has been established as the tool with the highest
accuracy and fastest execution time among competitive tools (Tan and Bockisch,
2019; Silva et al., 2021). RefactoringMiner has been used in numerous
empirical studies to extract refactoring datasets from the commit history of
open-source projects. Moreover, the tool was used in solving various software
evolution analysis problems, such as automatic refactoring-aware commit
merging (Ellis et al., 2023), automatic decomposition of commits into distinct
activities (Shen et al., 2021), automatic source code comment updating (Liu et
al., 2021), refactoring-aware implementation of the SZZ algorithm for
identifying bug-inducing changes (Rosa et al., 2021), automatic extraction of
complete and concise bug-fixing patches cleaned-up from overlapping
refactoring edits (Jiang et al., 2023), and refactoring-aware commit change
history extraction for methods and variables (Jodavi and Tsantalis, 2022a),
just to name a few. Finally, RefactoringMiner is used by tools visualizing
refactoring information in IDEs, such as the RefactorInsight (Kurbatova et
al., 2021) (developed and maintained by JetBrains Research) and Spike (Escobar
et al., 2022) plug-ins for IntelliJ IDEA.

Under the hood, RefactoringMiner applies a statement mapping process
(Tsantalis et al., 2022). The mapped statements and the AST node replacements
found within the mapped statements are then used to infer refactoring
operations. Despite its high accuracy in refactoring detection,
RefactoringMiner needed some significant and novel extensions (Section 3.2) to
be able to generate surgically accurate mappings at statement-level.
Furthermore, we developed an algorithm that generates AST diff (Section 3.3)
using the output of RefactoringMiner (i.e., the detected refactoring instances
and the pairs of matched program element declarations). As explained in
Section 3.4, the combination of RefactoringMiner’s output with our AST diff
generation algorithm overcomes all constraints discussed in Section 1.1

###  1.3. Contributions

  1. (1)

We extend RefactoringMiner to generate AST diff at the commit level.

  2. (2)

We create the first benchmark of AST node mappings from two popular datasets,
namely Defects4J (Just et al., 2014), which includes 835 bug fixes from 17
open-source projects, and Refactoring Oracle (Tsantalis et al., 2022), which
includes over 11K refactorings and code changes found in 546 commits from 187
open-source projects. Both datasets have become the de facto standard for
evaluating automated program repair and refactoring mining tools,
respectively. Our benchmark includes bug-fixing and refactoring commits, to
highlight the fact that most AST diff tools perform reasonably well in bug-
fixing commits as the changes are small, while their accuracy deteriorates in
commits involving larger and more complex changes, such as refactorings.

  3. (3)

We propose a novel framework for the evaluation of AST diff tools covering
multiple diff quality dimensions, including multi-mappings, semantically
compatible mappings, program element mappings, refactoring-related mappings,
and inter-file mappings. Moreover, we utilize our benchmark to compute
precision, recall and F-score, as objective metrics to measure the quality of
the AST diff generated by each tool.

  4. (4)

We develop an infrastructure to execute multiple AST diff tools, including
RefactoringMiner, GumTree 3.0 (greedy and simple), IJM, MTDiff, GumTree 2.1.0,
and compute the aforementioned metrics.

  5. (5)

We evaluate the precision, recall and execution time of the aforementioned
tools on our benchmark.

##  2\. Motivating examples demonstrating the limitations of current AST diff
tools

In this section, we demonstrate the limitations of the current state-of-the-
art AST diff tools with illustrative examples found in open-source project
commits.

###  2.1. Lack of support for multi-mappings

Multi-mapping is the case where a node from the left AST has more than one corresponding node in the right AST, and vice versa. None of the current state-of-the-art AST diff tools supports multi-mappings. However, multi-mappings are quite common in various change scenarios involving duplicated code. For example, developers tend to extract duplicated code from multiple methods into a newly added method, eliminate duplicate code within if-else-if-else or switch-case control structures by merging the duplicated statements and moving them out of the conditionals, eliminate duplicate code within catch blocks handling different exception types by merging the exception handling code into a single catch block using the Union type (i.e., catch(Exception1 | Exception2)). Of course, the reverse scenarios can also occur, e.g., by inlining a method being called by multiple different methods. Another example of one-to-many multi-mapping is the common case where a variable declaration with an initialization expression is split to a variable declaration initialized with a default value, and the initialization is moved to a separate variable assignment statement. Higo et al. (Higo et al., 2017) partially addressed this issue by introducing copy-and-paste as a new kind of edit action. However, their solution is uni-directional as it supports only scenarios in which developers duplicate existing code, but not scenarios in which developers eliminate duplicate code. Aalizadeh (Aalizadeh, 2021) studied 346K instances of Extract Method refactorings mined from 132,897 commits of 325 open-source repositories, and found that 41% of them were intended for reusing the extracted code within the same commit (i.e., avoiding the duplication of pre-existing code), and 25% of them were intended for eliminating pre-existing duplicate code.

Figure 1. AST diff generated by GumTree 3.0 (greedy) for commit
https://github.com/Alluxio/alluxio/commit/9aeefcd.

Figure 1 shows the AST diff generated by GumTree (greedy) for a commit in
which duplicated code within the method allocateBlock() has been extracted to
getCandidateDirInTier(). As GumTree does not support multi-mappings, it
matches correctly one of the duplicated code fragments with the code inside
the body of the extracted method getCandidateDirInTier(). However, the other
duplicated code fragment is forcefully matched with some newly added code in
method allocateBlock() on the right side of the diff. This side-effect is a
result of the lack of multi-mapping support and can cause great confusion to
the code reviewers as it makes it very hard to understand that the actual
intention of the commit author was to extract duplicated code into a single
reusable method.

Figure 2. AST diff generated by RefactoringMiner for commit
https://github.com/Alluxio/alluxio/commit/9aeefcd.

Figure 2 shows the AST diff generated by RefactoringMiner for the same commit.
In contrast to the diff generated by GumTree (Figure 1), the intention of the
commit author to extract duplicated code into a single reusable method is
clearly expressed in the diff. Moreover, this AST diff is more aesthetically
pleasing, less chaotic, and thus less confusing. RefactoringMiner was able to
discover the multi-mappings, because there exist two calls to the extracted
method getCandidateDirInTier() within the body of allocateBlock() on the right
side of the diff. By taking advantage of this language clue, it executes twice
the process of mapping the statements within the body of allocateBlock() on
the left side with the statements within the body of getCandidateDirInTier()
on the right side. Moreover, in each execution the location of the call to the
extracted method is utilized to restrict the scope of the left-side statement
mappings within the parent block mapping under which each call is nested.

###  2.2. Lack of language clue utilization to guide the matching process
(i.e., language agnosticism)

Most AST diff tools are language-agnostic. The premise is that being language-
agnostic, it is possible to devise a solution that can support any programming
language (silver bullet). Therefore, GumTree and its extensions try to
“blindly” find the largest identical (or similar) AST sub-trees in a pair of
files without relying on language clues to guide the matching process. This
approach has negative implications on both the accuracy of the mappings and
the overall execution time. For example, if a relatively large portion of the
code in the body of a method on the left is extracted to a new method on the
right, GumTree erroneously matches the left method declaration with the
extracted method declaration, because the left method shares a larger common
AST subtree with the extracted method compared to the code remaining in the
original method (after extraction) on the right side. However, this gives the
code reviewers the wrong impression that the left method is “renamed” to the
extracted method, which makes it more difficult to understand the actual
change intended by the commit authors (i.e., Extract Method refactoring).

Some examples of language clues that can be used to guide the matching process
are method signatures and method calls. If a method with the same signature
can be found in both the left and right ASTs, the matching process can be
narrowed down to the bodies of these two methods without searching for matches
in the rest of the files. If after matching the bodies of the methods, a
portion of the left method is found as deleted and in its place in the right
method there is a call to a newly added method (i.e., implying the potential
application of an Extract Method refactoring), the matching process can be
guided to match the deleted code from the left with the body of the newly
added method from the right without searching for matches in the rest of the
right file. The only AST diff tool that considers some language clues is IJM,
which applies partial matching by restricting the scope of the matching
process to selected parts of the source code (e.g., when matching method
declarations with identical signatures). However, IJM does not utilize method
calls to further guide the matching process.

Figure 3 shows the AST diff generated by GumTree (greedy) for a commit in
which almost the entire body of method getAllPaths() has been extracted to
getAllPathsWork(). The vast majority of AST diff tools have been designed
under the assumption that the shortest edit script is the most beneficial to
grasp the nature of a change (Falleri et al., 2014; Dotzler and Philippsen,
2016), as the length of the edit script is a proxy to the cognitive load for a
developer to understand the source code changes. For this reason, GumTree
matches getAllPaths() method declaration with getAllPathsWork() method
declaration, as this match minimizes the move edit operations (highlighted in
gray background color), and results in an overall shorter edit script.
However, the diff visualization gives the code reviewers the wrong impression
that getAllPaths() has been renamed to getAllPathsWork(), which makes it
almost impossible to understand that the actual change intended by the commit
author was to extract method getAllPathsWork() in order to provide the same
functionality with a different input parameter type (i.e., Path instead of
Optional<Path>). However, this kind of method extractions are quite common and
Silva et al. (Silva et al., 2016) found that the second most common motivation
for Extract Method refactoring is to introduce an alternative signature for an
existing method (e.g., with additional or different parameters) and make the
original method delegate to the extracted one, as happened in this particular
example.

Figure 3. AST diff generated by GumTree 3.0 (greedy) for commit
https://github.com/facebook/buck/commit/a1525ac. Figure 4. AST diff generated
by RefactoringMiner for commit
https://github.com/facebook/buck/commit/a1525ac.

By taking advantage of language clues, such as method signatures and method
calls, RefactoringMiner generates the AST diff shown in Figure 4. The edit
script corresponding to this diff is actually longer, because the majority of
statements within the body of method getAllPaths() are shown as moved
(highlighted in gray background color) to method getAllPathsWork(). However,
this diff depicts more accurately the intention of the commit author to
extract method getAllPathsWork() in order to provide the same functionality
with a parameter of type Path. Moreover, the mapping for sub-expression
workingDir.get(), which is matched with the argument passed to the
getAllPathsWork() call, accurately reflects the intention of the developer to
change the parameter type from Optional<Path> to Path, as workingDir.get()
returns the value (i.e., Path) present in workingDir (i.e., Optional<Path>).
This example is the proof that a shorter edit script is not necessarily the
best way to convey the intention behind the changes made by a developer, and
may actually confuse and mislead the code reviewers. Moreover, this example
demonstrates that AST diff cannot be properly addressed in a language-agnostic
manner, as language clues (e.g., method signatures, method calls, field
references) are of vital importance for guiding the matching process.

###  2.3. Lack of refactoring awareness

Refactoring is quite common in software evolution, as it facilitates multiple
maintenance activities, such as reusing code, fixing bugs, adding new
features, improving code design, improving testability, improving code
understandability and readability (Silva et al., 2016; Pantiuchina et al.,
2020). Despite its benefits on software maintainability, refactoring may
introduce “noise” in the diff, as refactoring-related edits tend to overlap
with other non-behavior-preserving changes. Negara et al. (Negara et al.,
2012) found that 46% of refactored program entities are also edited or further
refactored in the same commit, a practice commonly referred to as floss
refactoring (Murphy-Hill et al., 2012).

Refactoring information can help to improve the quality of source code diff.
For example, knowing that a variable, field, or method is renamed can help to
improve the mapping of sub-expressions within the statements referencing them.
Knowing that a sub-expression is extracted from a left-side statement and
assigned to a newly added right-side variable declaration (i.e., Extract
Variable refactoring) can help to properly match the pair of statements from
which the variable was extracted, despite any major structural differences
caused by the sub-expression extraction. None of the current state-of-the-art
AST diff tools leverages refactoring information in order to improve the
accuracy of the generated AST node mappings.

Figure 5 shows the AST diff generated by GumTree (simple) for a piece of code
in which two low-level refactorings were applied by the developer. The first
refactoring is the renaming of the enhanced-for loop formal parameter object
to item (i.e., Rename Variable). The second refactoring is the move of the
expression "[" + (count++) + "]" to the initializer of the newly introduced
variable itemKey (i.e., Extract Variable). GumTree correctly matches the
SimpleName AST nodes with values object and item in the enhanced-for loop
formal parameter, but mismatches the SimpleName AST nodes with values object
and itemKey in the argument list of the Collections.singletonMap() invocation.
The reason behind the mismatch is that GumTree tries to find the longest
common subsequence with isomorphic structure and itemKey is the first AST node
having the same AST type (i.e., SimpleName) with object. The resulting diff
visualization might confuse the code reviewers about whether variable object
is actually renamed to item, as there are two inconsistent variable identifier
mappings for object.

Figure 5. AST diff generated by GumTree 3.0 (simple) for commit
https://github.com/spring-projects/spring-boot/commit/20d39f7. Figure 6. AST
diff generated by RefactoringMiner for commit https://github.com/spring-
projects/spring-boot/commit/20d39f7.

Figure 6 shows the AST diff generated by RefactoringMiner, which takes
advantage of the detected Rename Variable and Extract Variable refactorings to
optimize the SimpleName AST node mappings within the argument list of the
Collections.singletonMap() invocation in a post-processing phase. The
resulting diff visualization has no ambiguity regarding the renaming of
variable object to item, and thus makes easier the understanding of the actual
changes applied by the commit author.

###  2.4. Matching semantically incompatible AST nodes (i.e., semantic
ignorance)

As most AST diff tools are language agnostic (Falleri et al., 2014), they can
match any pair of AST nodes, as long as they have the same AST type, ignoring
completely the semantic role these AST nodes play in the program. For example,
a method parameter, the formal parameter of an enhanced-for loop, the
exception declaration of a catch block, and the formal parameter of a lambda
expression, all share the same AST type, which is the
SingleVariableDeclaration type in the AST representation of the Eclipse JDT
parser. GumTree can match any combination of AST nodes from the aforementioned
semantic groups, just because they have the same AST type. However, such
matches make no semantic sense, make the resulting diff look “unnatural”, may
confuse the code reviewers, or even mislead the code reviewers in
comprehending the actual changes intended by the commit authors in a wrong
way. Another example of a semantically incompatible match allowed by GumTree
is the matching of a type reference (i.e., SimpleType AST node with a nested
SimpleName AST node) with a variable reference (i.e., SimpleName AST node), or
the matching of a method name reference (i.e., SimpleName AST node) with a
variable reference. Again, although the AST nodes from the aforementioned
semantic groups share the same AST type (SimpleName), they serve a completely
different semantic purpose in the program. In order to prevent the latter
semantically incompatible matches, IJM (Frick et al., 2018) modifies the AST
structure by merging the value of name nodes (i.e., SimpleName AST nodes) with
their respective parent nodes and deleting the name nodes with redundant
information. The last example occurs when there is a change in the block
structure of a method (i.e., control flow statements being added or deleted).
In such case, GumTree may match the block corresponding to the method body
with a control structure block (e.g., the block corresponding to the body of
an if or for statement). The block corresponding to the method body has a
unique semantic purpose (i.e., enclose the functionality of a method), and
thus should be matched only with a method body block.

Figure 7 shows the AST diff generated by GumTree (greedy) for a piece of code
in which an enhanced-for loop has been migrated to a semantically equivalent
Java Stream API call chain. Although GumTree correctly matched the condition
of the if statement with the lambda expression within the filter method call,
and the statement within the body of the if statement with the lambda
expression within the forEach method call, it incorrectly matches four
semantically incompatible AST nodes: a) the enhanced-for loop body block with
the method body block, b) the type of the enhanced-for loop formal parameter
ExternalResource with variable externalResources, c) the variable resource
with the method call stream, and d) the variable externalResources with the
lambda parameter resource. Semantically incompatible AST node mappings may
cause great confusion to the code reviewers, and in this particular case make
it more difficult to assess whether the migration to a new language feature
(i.e., Stream API) is behavior-preserving.

Figure 7. AST diff generated by GumTree 3.0 (greedy) for commit
https://github.com/checkstyle/checkstyle/commit/de022d2. Figure 8. AST diff
generated by RefactoringMiner for commit
https://github.com/checkstyle/checkstyle/commit/de022d2.

Figure 8 shows the AST diff generated by RefactoringMiner, which is fully
semantic-aware and shows that the enhanced-for loop formal parameter resource
corresponds to the lambda parameters of the filter and forEach method calls
(i.e., multi-mapping). The resulting diff visualization shows clearly that the
applied migration is behavior-preserving and helps the code reviewers to
understand (and possibly learn) the transformation mechanism.

###  2.5. Lack of diff support at the commit level (i.e., commit-level change
ignorance)

All current state-of-the-art AST diff tools accept as input a pair of files,
and thus cannot detect the move of a code fragment to another file modified in
the same commit. This limitation has a further side-effect. It is possible
that a code fragment from the left AST that has not been properly marked as
moved to another file to be forcefully and incorrectly matched with some newly
added code in the right AST. Such incorrect code fragment matches may mislead
code reviewers about the actual code re-organization and design changes
applied by the commit authors. A notable exception is Staged Tree Matching
(Fujimoto et al., 2020), which is a GumTree extension. Staged Tree Matching
first applies the standard GumTree algorithm on the pairs of files modified in
a project. Then, it constructs a project-level AST for each version by
connecting the AST roots corresponding to each file to a pseudo-project-root
node, and runs another matching phase on the project-level ASTs by considering
only the remaining unmatched AST subtrees. However, this is an Early Research
Achievements work and the authors do not provide any experimental results
regarding the accuracy and execution time of the proposed approach.

Figure 9. AST diff generated by GumTree 3.0 (greedy) for commit
https://github.com/crate/crate/commit/72b5348. Figure 10. AST diff generated
by RefactoringMiner for commit https://github.com/crate/crate/commit/72b5348.

Figure 9 shows the AST diff generated by GumTree (greedy) for a commit in
which some methods are moved to other classes. As GumTree can perform a diff
between pairs of files, it is not aware of the changes taking place in other
files modified in the same commit. As a result GumTree forcefully matches the
deleted methods downstreamNodes and downstreamExecutionNodeId (actually pulled
up to superclass AbstractDQLPlanNode) to the added methods leftMergeNode and
rightMergeNode (actually moved from class NestedLoop). The resulting diff
visualization will definitely mislead the code reviewers to think that the
corresponding methods have been renamed.

On the other hand, RefactoringMiner analyzes the changes within all files
modified in a commit and is capable of detecting method moves between files.
As shown in Figure 10, moved methods are specially highlighted with a purple
border, and by hovering over them a tooltip appears showing where each method
is moved from/to.

##  3\. Approach

In Section 3.1, we provide a quick overview of how RefactoringMiner 2.0
(Tsantalis et al., 2022) works, as background information needed to understand
the changes we performed in version 3.0 (Section 3.2) to improve statement
mapping accuracy. In Section 3.3, we explain how we utilize the information
provided by RefactoringMiner 3.0 to generate AST diff.

###  3.1. Background on how RefactoringMiner 2.0 works

Figure 11. Overview of RefactoringMiner’s workflow.

Figure 11 shows the overall workflow of RefactoringMiner. Although this
workflow remained unchanged, since version 2.0 (Tsantalis et al., 2022), we
decided to include it for the sake of completeness, as it will make it easier
for readers who are not familiar with RefactoringMiner to understand better
how it works. RefactoringMiner accepts as input two sets of files from two
versions. It provides APIs that can extract this input from a repository
commit, from two directories containing Java files, or even from raw file
contents provided as strings. The matching process consists of four phases:

  1. Phase 1.

In the first phase, all program elements (i.e., type, method, field
declarations) with identical signatures are getting matched in a top-down
fashion, starting from classes having an identical signature (i.e., package
and class name), and moving on to the fields and methods declared in them.

  2. Phase 2.

For each pair of type declarations that were matched in Phase 1, we collect
any remaining unmatched methods and fields, and provide them as input to Phase
2, which is responsible for matching program elements with changes in their
signatures. For every pair combination of unmatched method declarations, we
compute their statement mappings, which are then passed to a sorting function
that finds the best match among all pairs. This step supports the detection of
method signature changes, such as renames, addition/deletion of parameters,
change of return or parameter types, as well as the detection of merged and
split methods. In the next step, the statement mappings within the matched
method declarations are utilized to infer method-body-level and local field
refactorings. RefactoringMiner does not use a similarity threshold to match a
pair of non-identical statements. Instead, it applies all possible
syntactically valid AST node replacements within a pair of input statements,
and matches these statements only if they become textually identical after the
application of replacements. These AST node replacements within the statement
mappings could be references to renamed/extracted/inlined fields, local
variables, or method parameters. We examine the consistency of these
replacements throughout the methods of a type declaration to ensure that the
detected refactorings are valid.

  3. Phase 3.

For every pair combination of type declarations that were not matched in Phase
1, we compute the intersection of methods and fields based on their
signatures. Then, a sorting function determines the best match among all
pairs. This step supports the detection of type signature changes, such as
class renames, class moves to another package, as well as the detection of
merged and split classes. For each pair of matched type declarations, we
execute Phase 1 and 2, as described above, to compute statement mappings and
infer method-body-level and local field refactorings.

  4. Phase 4.

In the last phase, we collect any remaining unmatched methods and fields from
all type declarations, and for every pair combination of methods, we compute
their statement mappings. Again, a sorting function determines the best match
among all pairs. This step supports the detection of method moves between
previously existing files (if these files are part of the same inheritance
hierarchy then the move is actually a Pull Up or Push Down Method
refactoring), as well as method moves to new files (i.e,. Extract Class or
Extract Superclass refactoring). Finally, the statement mappings within the
matched moved method declarations are examined for references to unmatched
fields in order to infer moved fields along with the moved methods.

###  3.2. Changes in RefactoringMiner 3.0 to improve statement mapping
accuracy

Figure 12. Overview of the statement mapping process highlighting the parts
that are added or modified and the corresponding sections explaining these new
features in detail. Red-color oval shapes e.g., [outer color=red]3.2.2
indicate a change to a previously existing component in RefactoringMiner 2.0.
Green-color oval shapes e.g., [outer color=green]3.2.4 indicate a new
component that did not exist in RefactoringMiner 2.0.

Figure 12 shows the core of RefactoringMiner’s statement mapping process and
highlights the parts that are added or modified to improve the overall
accuracy of our AST diff. This process is executed wherever “compute statement
mappings” appears in Figure 11. In a nutshell, given two code fragments as
input (e.g., method #1 and method #2), first the leaf statements (i.e.,
statements without a body) are matched in three rounds. The first round is
executed only if the input code fragments have an iso-structural control flow
structure. After the completion of each round, the remaining unmatched leaves
are passed to the next round. During the execution of each round, a pair of
statements is matched only if the corresponding matching criterion shown in
Figure 12 is met, and if there are multiple candidate mappings for a given
statement, a sorting function is used to select the “best” one. Next, the
composite statements, i.e., statements with a body containing other nested
statements (for, while, if, do, switch, synchronized, try, catch, finally),
are matched in two rounds, utilizing the previously established leaf statement
mappings. At the end of this process, there might be some inexact mappings
(i.e., non-identical matched statements) and some unmatched statements. These
are then matched with statements of added/removed methods in the same class to
detect instances of Extract/Inline Method refactorings (i.e., methods
extracted from method #1 or methods inlined to method #2). At the end, a
statement mapping optimization process is executed to handle statements that
might be matched two or more times (e.g., once with a statement in the
original method, and once with a statement in an extracted/inlined method).
This process determines which one of the duplicate statement mappings is the
“best” and discards the other ones.

####  3.2.1. Improved sorting of candidate mappings

Originally, RefactoringMiner had a very simplistic approach for sorting leaf
mapping candidates (feature [outer color=red]3.2.1.1 in Figure 12) based on 3
criteria (Tsantalis et al., 2022). First, based on the string edit distance of
the nodes in ascending order (i.e., more textually similar node pairs rank
higher). Second, based on the absolute difference of the nodes’ depth in
ascending order (i.e., node pairs with more similar depth rank higher). Third,
based on the absolute difference of the nodes’ index in their parent’s list of
children in ascending order (i.e., node pairs with more similar position in
their parent’s list of children rank higher). Composite statement mappings
(feature [outer color=red]3.2.1.2 in Figure 12) were sorted with the same
criteria plus an additional one (Tsantalis et al., 2022), namely based on the
ratio of the nodes’ matched children in descending order (i.e., node pairs
with more matched children rank higher).

This simplistic ranking was sufficient for the sake of detecting method-level
refactorings, because the refactoring detection rules simply require the
number of matched statements within a pair of methods to be larger than the
number of unmatched statements. As a result, even if the statement mappings
are not perfectly matched, the refactoring would be still detected. However
from our early experiments, we discovered that the resulting mappings were not
always accurate, especially in some corner cases involving repeated statements
within the body of a method. Therefore, we introduced more fine-grained
sorting criteria to handle properly the ties between candidate mappings. These
new criteria include checking whether the statements that precede/follow the
statement mappings are identical or not, and taking into account the edit
distance of the statement mappings’ parent nodes. The formal definitions of
the sorting criteria for leaf and composite mappings are detailed in sections
3.2.1.1 and 3.2.1.2, respectively.

Given a mapping $M=(m_{1},m_{2})$ with $m_{1}$ being the left-side statement
and $m_{2}$ being the right-side statement,

###### Definition 3.0.

$\textit{edit-distance}(M)$ is the Levenshtein edit distance between $m_{1}$
and $m_{2}$. It should be noted that the bodies of composite statements are
not included in the computation of their edit distance.

###### Definition 3.0.

$\textit{depth}(m)$ is the number of composite statement parents of statement
$m$, until we reach the body of the method declaration containing statement
$m$.

###### Definition 3.0.

$\textit{parent-edit-distance}(M)$ is an array where index $i$ has the
Levenshtein edit distance between the $i$th parent of $m_{1}$ and the $i$th
parent of $m_{2}$ and $i=1,...,\textit{depth}(M)$ where
$\textit{depth}(M)=min(\textit{depth}(m_{1}),\textit{depth}(m_{2}))$. At index
1, we compute the edit distance between the direct parents of $m_{1}$ and
$m_{2}$, at index 2, we compute the edit distance between the parents of the
direct parents of $m_{1}$ and $m_{2}$, and so on, until $i$ becomes equal to
$\textit{depth}(M)$.

###### Definition 3.0.

$\textit{direct-parent-edit-distance}(M)=\textit{parent-edit-distance}(M)[1]$

###### Definition 3.0.

$\textit{parent-edit-distance-sum}(M)=\sum_{i=1}^{n}\textit{parent-edit-
distance}(M)[i]$, where $n=\textit{depth}(M)$

###### Definition 3.0.

$\textit{depth-diff}(M)=|\textit{depth}(m_{1})-\textit{depth}(m_{2})|$

###### Definition 3.0.

$\textit{index-diff}(M)=|\textit{index}(m_{1})-\textit{index}(m_{2})|$, where
$\textit{index}(m)$ is $m$’s index in its parent’s statement list

#####  3.2.1.1 Sorting criteria for leaf statement mappings

Given two leaf mappings (i.e., pairs of matched leaf statements) $M_{a}$ and
$M_{b}$, we check the following rules in the order they are listed and $M_{a}$
is ranked over $M_{b}$ iff (a rule is applicable if its condition holds for
$M_{a}$ but not for $M_{b}$):

  1. (1)

$M_{a}$ is part of a multi-mapping (i.e., a single statement matched to
multiple statements or vice versa). If both $M_{a}$ and $M_{b}$ are part of a
multi-mapping, $M_{a}$ is ranked first only if it involves more statements.

  2. (2)

if $\textit{edit-distance}(M_{a})\neq\textit{edit-distance}(M_{b})$:

    1. (a)

$M_{a}$ becomes textually identical after undoing an overlapping
extract/inline variable refactoring.

    2. (b)

both statement pairs located right before and right after $M_{a}$ are
textually identical.

    3. (c)

the statements in $M_{a}$ have the same nesting depth (i.e., $\textit{depth-
diff}(M_{a})=0$), the same index in their parent’s statement list, and the
same AST type for their first non-block parent.

    4. (d)

if $\textit{depth}(M_{a})>2$ and $\textit{depth}(M_{b})>2$, $\textit{parent-
edit-distance-sum}(M_{a})<\textit{parent-edit-distance-sum}(M_{b})$

    5. (e)

$\textit{edit-distance}(M_{a})<\textit{edit-distance}(M_{b})$

  3. (3)

if $\textit{edit-distance}(M_{a})=\textit{edit-distance}(M_{b})$:

    1. (a)

if $\textit{depth}(M_{a})=\textit{depth}(M_{b})$, $\textit{parent-edit-
distance-sum}(M_{a})=0$ and $\textit{parent-edit-distance-sum}(M_{b})>0$

    2. (b)

if $\textit{depth}(M_{a})\neq\textit{depth}(M_{b})$, $\textit{parent-edit-
distance-sum}(M_{a})<\textit{parent-edit-distance-sum}(M_{b})$

    3. (c)

$\textit{depth-diff}(M_{a})<\textit{depth-diff}(M_{b})$

    4. (d)

$\textit{index-diff}(M_{a})<\textit{index-diff}(M_{b})$

    5. (e)

$\textit{direct-parent-edit-distance}(M_{a})<\textit{direct-parent-edit-
distance}(M_{b})$

#####  3.2.1.2 Sorting criteria for composite statement mappings

Given a composite statement mapping $M=(m_{1},m_{2})$ with $m_{1}$ being the
left-side statement and $m_{2}$ being the right-side statement, and
$\textit{children}(m)$ being the set of statements nested under $m$,

###### Definition 3.0.

$\textit{child-match-ratio}(M)$ is the number of matched child pairs nested
under $m_{1}$ and $m_{2}$, respectively, divided by
$max(|\textit{children}(m_{1})|,|\textit{children}(m_{2})|)$

###### Definition 3.0.

$\textit{identical-composite-children}(M)$ is the number of matched composite
child pairs nested under $m_{1}$ and $m_{2}$, respectively, which are
identical (i.e., have an edit distance equal to zero)

Given two composite statement mappings $M_{a}$ and $M_{b}$, we check the
following rules in the order they are listed and $M_{a}$ is ranked over
$M_{b}$ iff (a rule is applicable if its condition holds for $M_{a}$ but not
for $M_{b}$):

  1. (1)

$\textit{child-match-ratio}(M_{a})\geq 2*\textit{child-match-ratio}(M_{b})$

  2. (2)

if $\textit{edit-distance}(M_{a})\neq\textit{edit-distance}(M_{b})$:

    1. (a)

$M_{a}$ becomes textually identical after undoing an overlapping
extract/inline variable refactoring.

    2. (b)

$\textit{edit-distance}(M_{a})<\textit{edit-distance}(M_{b})$

  3. (3)

if $\textit{edit-distance}(M_{a})=\textit{edit-distance}(M_{b})$:

    1. (a)

$\textit{identical-composite-children}(M_{a})>\textit{identical-composite-
children}(M_{b})$

    2. (b)

$\textit{child-match-ratio}(M_{a})>\textit{child-match-ratio}(M_{b})$

    3. (c)

$\textit{depth-diff}(M_{a})<\textit{depth-diff}(M_{b})$

    4. (d)

$\textit{index-diff}(M_{a})<\textit{index-diff}(M_{b})$

####  3.2.2. Multi-mapping support for duplicated code moved out of or moved
into conditionals

RefactoringMiner was already able to infer multi-mappings for some specific
scenarios based on the refactorings it detects. For example, when some
duplicated code is extracted from the same method or different methods,
RefactoringMiner detects as many Extract Method refactoring instances as the
number of duplicated code fragments. Each Extract Method instance includes its
own mappings between statements on the left side (i.e., one of the duplicated
code fragments) and the right side (i.e., the extracted code fragment). All
these statement mappings refer to exactly the same statements on the right
side, thus naturally forming multi-mappings. Inline Method refactorings can
also form multi-mappings, if the inlined method is called more than once.

However, there are also scenarios in which developers eliminate (or introduce)
duplicated code within the same method. Typically, such duplicated code exists
within the branches of conditional statements, such as if-else-if or switch-
case statements, where the same logic is repeated within each execution branch
with some slight variations. For example, in Figure 13, we can see an if-else-
if statement with identical functionality in each branch with the only
difference being a String passed as an argument when calling method
fetchSyncDLObject(), which creates the syncDLObject. On the right side, we can
see that the developer moved and merged the duplicated statements out of the
if-else-if statement, and introduced a variable named type to store the
varying value passed as an argument when calling method fetchSyncDLObject().
The original if-else-if statement still remains in the method just to assign
the proper value to variable type. Moreover, we can see that some of the
duplicated statements are further extracted to method updateSyncDLObject(),
which is called inside the body of statement if(syncDLObject != null), which
was also moved and merged out of the if-else-if statement, and its condition
was inverted.

Figure 13. AST diff generated by RefactoringMiner for commit
https://github.com/liferay/liferay-plugins/commit/7c7ecf4.

To support such duplication elimination/introduction scenarios, we developed a
simple algorithm (feature [outer color=red]3.2.2 in Figure 12) that is
activated whenever we have many-to-one (i.e., many statements on the left side
are matched with a single statement on the right side) or one-to-many (i.e.,
one statement on the left side is matched with many statements on the right
side) candidate statement mappings. Before passing these candidate mappings to
the sorting function to select the “best” one, we execute our algorithm to
check if we should keep all of them instead. Assuming we have many-to-one
candidate mappings, the algorithm checks if the left-side statements in the
candidate mappings are nested under the same if-else-if or switch-case
statement, and if each one of them belongs to a separate execution branch. If
this is true, next we check if the right-side statement is placed in a
shallower depth in the method’s nesting structure compared to the left-side
statements. Usually, the new nesting depth of the right-side statement becomes
equal to the nesting depth of the if-else-if or switch-case statement from
which it was moved out, as in the example of Figure 13. If all conditions
checked by our algorithm are met, then we keep all many-to-one candidate
mappings and skip the execution of the sorting function. A similar algorithm
is applied for one-to-many candidate mappings.

####  3.2.3. Statement mapping scope based on call sites

This is a language-aware feature (feature [outer color=red]3.2.3 in Figure 12)
that utilizes the location of method calls in order to restrict the scope of
the statement mapping process for the detection of extracted and inlined
methods. The idea comes from the observation that developers tend to extract
consecutive statements, which are located within the body of a control
statement in the origin method. For example, in Figure 2, the developer
extracted duplicated code located within the body of a for and an if
statement, respectively. As we can see in the right side of Figure 2, after
the refactoring, two method calls to the extracted method
getCandidateDirInTier appear in the locations of the duplicated code fragments
within the body of the same for and if statement, respectively. By utilizing
the location and the number of calls to the extracted method, we can achieve
two things. First, the number of calls to the extracted method determines how
many times the statement mapping process should be executed. Since there are
two method calls to the extracted method, we should match the remaining
unmatched statements in the origin method with the statements of the extracted
method two times. Second, the location of the calls helps to narrow down the
scope of the statement mapping process in each execution. In the first
execution, we include only the unmatched statements within the body of the for
loop in the origin method, as the for loop corresponds to the parent mapping
of the first call to the extracted method. In the second execution, we include
only the unmatched statements within the body of the if statement in the
origin method, as the if statement corresponds to the parent mapping of the
second call to the extracted method. Following this approach, we are able to
obtain the multi-mappings shown in Figure 2, without mixing the mappings
corresponding to each duplicated code region.

In the alternative scenario, where the duplicated code fragments are located
within the method body scope, then the calls to the extracted method would be
also located within the method body scope. In this scenario, it is not
possible to use the parent mapping to restrict the unmatched statements
included in each execution of the statement mapping process, as both
duplicated code fragments would have the same parent mapping (i.e., the origin
method body block). For this alternative scenario, in each execution we form a
region expanding from the first to the last identical statement mapping
between the remaining unmatched statements in the origin method and the
statements of the extracted method. In each subsequent execution of the
statement mapping process, we exclude the statements that were matched within
a region in all previous executions. With this approach, it is possible to
obtain accurate multi-mappings, even when the duplicated code fragments follow
each other directly, without any intermediate non-extracted code between them.
Some examples of this scenario can be found in our AST diff gallery
(RefactoringMiner AST Diff Gallery, 2023a, b).

####  3.2.4. Statement mapping optimization

This is a completely new component added in the statement mapping process
(feature [outer color=green]3.2.4 in Figure 12), which is executed right after
the detection of Extract Method and Inline Method refactorings extracted from
or inlined to a given pair of matched methods (e.g., method #1 and method #2
in Figure 12). This component first detects statements that participate in
more than one mappings. For example, a statement in method #1 that is matched
with a statement in method #2, and is also matched with a statement in an
added method (Extract Method scenario), or a statement in method #2 that is
matched with a statement in method #1, and is also matched with a statement in
a removed method (Inline Method scenario). Assuming we have a set of such
mappings, we check the following rules in the order they appear (each rule is
applicable, only if there is at least one mapping in the set not satisfying
the condition of the rule):

  1. (1)

If a mapping in the set includes a call to an extracted method or an inlined
method, then this mapping is discarded, and the others are kept.

  2. (2)

If one or more mappings in the set do not have their parent statements mapped,
then these mappings are discarded, and the others are kept.

  3. (3)

If one or more mappings in the set belong to a nested extracted method (i.e.,
a method extracted from another extracted method) or a nested inlined method
(i.e., a method inlined to another inlined method), then these mappings are
discarded, and the others are kept.

  4. (4)

If one or more mappings are not textually identical (i.e., the statements were
matched by replacing AST sub-expressions that were different), then these
mappings are discarded, and the others are kept.

  5. (5)

We compute the minimum edit distance (i.e., the levenshtein distance between
the two statements of a mapping) among the mappings in the set, and discard
the mappings having an edit-distance larger than the minimum one.

The same optimization process is applied in the case of Extract and Move
Method and Move and Inline Method refactorings, where the extracted/inlined
code is moved to/from another file.

####  3.2.5. Semantic and refactoring-aware import declaration diff

A good quality diff of import declaration statements should help code
reviewers to quickly understand about library migrations (Alrubaye et al.,
2019) and type/API migrations (Ketkar et al., 2020) that took place in the
file. To this end, we introduce the first semantic and refactoring-aware
import declaration AST diff in the literature, which offers three novel
features, namely matching based on package/class refactorings, matching based
on local type changes in the file, and grouping/un-grouping based on import-
on-demand declarations (i.e., import package.*).

After completing the detection of refactorings at commit-level,
RefactoringMiner is aware of changes in the structure and organization of the
project, as reflected by package-level refactorings (e.g., Rename Package,
Move Package) and class-level refactorings (e.g., Rename Class, Move Class).
In a post-processing step, RefactoringMiner goes through each modified Java
file in the commit, and matches pairs of previously unmatched (i.e., removed
and added) import declarations whose types correspond to the fully-qualified
names of moved/renamed classes. In Figure 14, we can see import declaration
statements matched based on Rename Class and Move Class refactoring
information. All five type declarations referenced in the import statements
have been moved from package spdy to framed, and additionally classes
SpdyConnection and SpdyStream have been renamed to FramedConnection and
FramedStream, respectively. RefactoringMiner is able to correctly match the
updated import declarations, despite the re-ordering after applying
alphabetical sorting.

Figure 14. AST diff generated by RefactoringMiner for commit
https://github.com/square/okhttp/commit/c753d2e. Figure 15. AST diff generated
by RefactoringMiner for Cli-1. Figure 16. AST diff generated by
RefactoringMiner for commit https://github.com/apache/dubbo/commit/500434a.

The type changes detected by RefactoringMiner within the scope of a Java file
are also used to match pairs of previously unmatched (i.e., removed and added)
import declarations whose types correspond to the changed type references. In
Figure 15, we can observe that the developer changed the type of field options
from Map to Set and the initializer of field options from HashMap to HashSet.
The modified import declaration statements have been matched accordingly to
reflect the collection migration from Map to Set. It should be noted that only
the consistent type changes within the scope of a Java file are taken into
account. For example, if CommandLine.java included a type change from HashMap
to TreeSet in another part of the code, then the import declaration for
java.util.HashMap would be reported as deleted, as the matching import
declaration on the right-side is ambiguous. Finally, RefactoringMiner can
match a set of single-type-import declarations that are replaced with a type-
import-on-demand declaration and vice-versa by introducing multi-mappings, as
shown in Figure 16. The grouping/un-grouping of import declarations is based
on their common package prefix (e.g., java.util. in the example of Figure 16).

###  3.3. AST diff generation

To generate the AST diff for a given commit, we utilize the following
information provided by RefactoringMiner 3.0:

  * •

Pairs of matched declarations (i.e., import, class/enum, method, field, enum-
constant declarations, initializer blocks)

  * •

Refactoring instances (RefactoringMiner 3.0 supports the detection of 60
different refactoring types)

Table 1 shows the kind(s) of AST node mappings that each refactoring type
contributes to. More specifically, a refactoring may contribute declaration
mappings (i.e., a pair of matched declarations with changed signature), multi-
mappings (i.e., duplicated statements being merged), intra-file-move mappings
(i.e., statements moved within the same file), inter-file-move mappings (i.e.,
statements moved between different files), or sub-expression mappings (i.e.,
expressions matched within larger statements, refer to Section 3.3.1 for more
details).

Table 1. Refactoring types and their contributions in AST node mappings

Refactoring Type | Kinds of AST node mappings
---|---
Rename Class/Method/Field | declaration
Move and Rename Class/Method/Field | declaration, inter-file-move
Move/Pull Up/Push Down Method/Field | inter-file-move
Merge/Split/Extract Class | inter-file-move
Extract and Move Method, Move and Inline Method | multi$\dagger$ , inter-file-move, sub-expression
Extract/Inline Method | multi$\dagger$ , intra-file-move, sub-expression
Merge/Split Method, Parameterize Test | multi$\dagger$ , intra-file-move
Merge/Split/Invert Conditional | sub-expression
Merge Catch | multi, sub-expression
Replace Loop with Pipeline, Replace Pipeline with Loop | sub-expression
Replace Anonymous with Class | inter-file-move
Replace Anonymous with Lambda | intra-file-move, sub-expression
Extract/Inline Variable/Field | sub-expression

  * $\dagger$

only if the refactoring involves duplicated fragments being merged, or single
fragment being duplicated

####  3.3.1. Use of refactoring mechanics to infer sub-expression mappings

As explained before, RefactoringMiner generates mappings at the statement
level. Moreover, for some specific refactoring types listed in Table 1, it
generates sub-expression mappings collected by utilizing the refactoring
mechanics (Fowler, 1999):

  * •

Extract Method: This refactoring provides mappings between arguments passed to
the extracted method call sites on the right side of the diff and sub-
expressions within the statements being extracted on the left side of the
diff. For example, in Figure 4 there is a mapping between the sub-expression
workingDir.get() from statement builder.put(workingDir.get(),
compilationDirectory); on the left side of the diff with the argument passed
to the extracted method call site return getAllPathsWork(workingDir.get()); on
the right side of the diff. This mapping is established because the parameter
workingDir is used in the place of the original sub-expression in statement
builder.put(workingDir, compilationDirectory); within the body of the
extracted method, and RefactoringMiner matched the pair of builder.put()
statements by replacing workingDir.get() with workingDir. By utilizing the
Extract Method mechanics, we know that the argument workingDir.get() passed to
the extracted method corresponds to parameter workingDir, and thus we can
infer the aforementioned sub-expression mapping.

  * •

Inline Method: This refactoring provides mappings between arguments passed to
the inlined method call sites on the left side of the diff and sub-expressions
within the statements being inlined on the right side of the diff.

  * •

Extract Variable/Field: These refactorings provide mappings between the sub-
expression(s) being extracted from statements on the left side of the diff and
the initializer of the extracted variable/field declaration on the right side
of the diff. For example, in Figure 6 there is a mapping between the sub-
expression "[" + (count++) + "]" on the left side of the diff with the
initializer of the newly introduced variable itemKey on the right side of the
diff. This mapping is established because the variable itemKey is used in the
place of the original sub-expression in statement flatten(properties,
Collections.singletonMap(itemKey, item), key); on the right side of the diff,
and RefactoringMiner matched the pair of flatten() statements by replacing "["
+ (count++) + "]" with itemKey. It should be emphasized that the longer (in
number of characters) the extracted expression is, the lower the textual
similarity between the statement originally containing the expression and the
statement referring to the extracted variable becomes. For this reason, we
gave high priority to the rule 2(a) in Section 3.2.1.1, which checks whether a
mapping “becomes textually identical after undoing an overlapping
extract/inline variable refactoring”.

  * •

Inline Variable/Field: These refactorings provide mappings between the sub-
expression(s) being inlined to statements on the right side of the diff and
the initializer of the inlined variable/field declaration on the left side of
the diff.

  * •

Replace Loop with Pipeline: This refactoring appears in the second edition of
Fowler’s book (Fowler, 2018) and is essentially a migration of traditional
loops and conditionals to the Java Stream APIs (Fowler, 2015), as shown in
Figure 8. RefactoringMiner generates mappings between the sub-expressions
within the loops and conditionals on the left side of the diff and the lambda
expressions appearing within Stream API calls on the right side of the diff.
For example, in Figure 8 there are four sub-expression mappings established
based on the refactoring mechanics. The collection externalResources being
iterated by the enhanced-for loop on the left side of the diff becomes the
invoker of the stream() method invocation on the right side of the diff. The
condition !isResourceLocationInCache(resource.location) of the if statement on
the left side of the diff becomes the lambda expression body of the filter()
method invocation on the right side of the diff. The statement
details.setProperty(resource.location, resource.contentHash); within the body
of the if statement on the left side of the diff becomes the lambda expression
body of the forEach() method invocation on the right side of the diff.
Finally, the enhanced-for loop formal parameter resource on the left side of
the diff is matched twice (i.e., multi-mapping) with the lambda expression
parameters of the filter() and forEach() method invocations on the right side
of the diff.

  * •

Replace Pipeline with Loop: This is the reverse refactoring of the previously
discussed one, and the sub-expression mappings are established in the reverse
way.

  * •

Split/Merge Conditionals: These refactorings capture the cases where a
conditional (typically if statement) is split to two or more conditionals, and
cases where two or more conditionals are merged into a single one,
respectively. Typically, these if statements have complex conditional
expressions combined with && and || operators, which are either split into
separate conditional sub-expressions, or merged into a single conditional
super-expression. Before the merge and after the split, typically these if
statements are nested within each other when the operator is &&, and are
sequentially executed when the operator is ||. Both refactorings provide
mappings between the split/merged conditional sub-expressions.

  * •

Merge Catch: This refactoring captures the cases where multiple catch blocks handling different exception types and having identical or similar exception handling code in their bodies, are merged into a single catch block that handles all exception types using the Union type (i.e., catch(Exception1 | Exception2)). The refactoring provides multi-mappings (many-to-one mappings) for the exception handling statements being merged, as well as sub-expression mappings for the exception types being moved from each individual catch to the Union type.

####  3.3.2. From RefactoringMiner output to AST diff

Algorithm 1 shows the process we follow to generate AST node mappings using as
input the list of program element declaration pairs $\mathcal{P}$ and
refactoring instances $\mathcal{R}$ detected by RefactoringMiner, as explained
in Sections 3.1 and 3.2. Each pair $p\in\mathcal{P}$ of program element
declarations may additionally include a set of mappings $p.mappings$. In
particular, if $p_{1}$ and $p_{2}$ are method declarations, $p.mappings$
contains the pairs of statements matched within the method bodies of $p_{1}$
and $p_{2}$. If $p_{1}$ and $p_{2}$ are field or enum constant declarations
$p.mappings$ contains the pairs of statements matched within the initializers
of $p_{1}$ and $p_{2}$. Each refactoring instance $r\in\mathcal{R}$ includes a
set of mappings $r.mappings$, as explained in Table 1.

Lines 2-7 generate the initial AST node mappings in mapping set $\mathcal{M}$
from the list of program element declaration pairs $\mathcal{P}$. Lines 8-12
generate AST node mappings in mapping set $\mathcal{A}$ from the list of
refactorings $\mathcal{R}$. Finally, lines 13-16 examine if there exists a
mapping in $\mathcal{A}$ that has a conflict with a mapping in $\mathcal{M}$.
Two mappings are considered conflicting, if they have the same left AST
subtree, but have a different right AST subtree, and vice versa. In such a
case, the conflicting mapping is removed from $\mathcal{M}$ and is replaced
with the mapping from $\mathcal{A}$. If there is no conflict, the mapping from
$\mathcal{A}$ is added to $\mathcal{M}$, anyways. In this way, we give
priority to all mappings established from refactorings, as their correctness
is guaranteed by the refactoring mechanics. In other words, this last step
makes our algorithm refactoring-aware.

1

Input : List of Refactorings $\mathcal{R}$, List of pairs of mapped program
elements $\mathcal{P}$

Output : Mapping Set $\mathcal{M}$ in which every item is a pair of subtrees

2

3$\mathcal{M}\leftarrow\\{\\}\;$ $\mathcal{A}\leftarrow\\{\\}$

4 foreach  _$p=(p_{1},p_{2})$ in $\mathcal{P}$_ do

5 $\mathcal{M}\leftarrow\mathcal{M}\cup\\{(p_{1},p_{2})\\}$

6 foreach  _$(m_{1},m_{2})$ in $p.mappings$_ do

7 $\mathcal{M}\leftarrow\mathcal{M}\cup SubtreeMatcher(m_{1},m_{2})$

8

9 end foreach

10

11 end foreach

12foreach  _r in $\mathcal{R}$_ do

13 foreach  _$(m_{1},m_{2})$ in $r.mappings$ _ do

14 $\mathcal{A}\leftarrow\mathcal{A}\cup SubtreeMatcher(m_{1},m_{2})$

15 end foreach

16

17 end foreach

18

19foreach  _$(m_{1},m_{2})$ in $\mathcal{A}$_ do

20 $\mathcal{M}\leftarrow\mathcal{M}\setminus\\{(x,y)\in\mathcal{M}\mid
x=m_{1}\lor y=m_{2}\\}$

21 $\mathcal{M}\leftarrow\mathcal{M}\cup\\{(m_{1},m_{2})\\}$

22

23 end foreach

Algorithm 1 Generate AST node mappings from RefactoringMiner output Table 2.
Improvements in sub-expression matching.
(RM = RefactoringMiner, GTG = GumTree Greedy, GTS = GumTree Simple, GT = GumTree Simple or Greedy) Tool | Diff
---|---
| Example 1: nested invocations at the argument level
RM |
GT |
| Example 2: nested invocations at the invoker level
RM |
GTS |
GTG |
| Example 3: nested infix expressions
RM |
GT |

Algorithm 1 calls $SubtreeMatcher$ (Algorithm 2) in lines 5 and 10. Algorithm
2 takes as input a pair of statements or sub-expressions, as provided by
RefactoringMiner, and generates fine-grained AST node mappings by matching the
leaf nodes within the input statements. In line 1, we execute the GumTree 3.0
(simple) algorithm to obtain the initial set of fine-grained mappings in
$\mathcal{M}$. By default, GumTree employs a threshold for the hyperparameter
$minHeight$ (i.e., length of the longest path from one leaf to the root of the
subtree) equal to 2. This is to avoid matching remaining leaf expressions with
height 1 (e.g., SimpleName nodes), which coincidentally have the same value.
However, since we are applying the algorithm on a single pair of statements
(i.e., subtrees with rather shallow depth), we configure a lower threshold for
$minHeight$ equal to 1, and modify the top-down phase of GumTree (see Section
6 for more details) by adding a condition to prevent the matching of
SimpleName nodes with parents having different AST types (i.e., avoid
semantically incompatible mappings for SimpleName nodes).

Lines 2-12 optimize the mappings generated by GumTree, as the lower threshold
for $minHeight$ may result in pairs of matched leaf nodes (i.e., SimpleName
and InfixOperator) with identical labels, whose parent nodes have not been
matched accordingly. Given a pair of matched leaf nodes $(t_{a},t_{b})$, if
$\mathcal{M}$ does not contain a mapping $(p_{a},p_{b})$ for the actual
parents of $t_{a}$ and $t_{b}$ (line 7), then all mismatches for the parent
nodes $p_{a}$ and $p_{b}$ are removed from $\mathcal{M}$ (line 8), and the
pair of actual parent nodes $(p_{a},p_{b})$ is added to $\mathcal{M}$ (line
9). Table 2 includes some illustrative examples involving method invocations
and infix expressions, which visually demonstrate the effect of the
aforementioned mapping optimization.

Input : Two subtrees $st_{1}$ and $st_{2}$

Output : Mapping set $\mathcal{M}$

1

$\mathcal{M}\leftarrow GumTreeSimple(st_{1},st_{2})$

// Running GumTree 3.0 Simple with minHeight = 1

2 foreach  _$(t_{a},t_{b})$ in $\mathcal{M}$_ do

3 $p_{a}\leftarrow parent(t_{a})$, $p_{b}\leftarrow parent(t_{b})$

4 $c1\leftarrow type(t_{a})=\texttt{SimpleName}\land
type(t_{b})=\texttt{SimpleName}\land type(p_{a})=\texttt{Invocation}\land
type(p_{b})=\texttt{Invocation}$

5 $c2\leftarrow type(t_{a})=\texttt{Operator}\land
type(t_{b})=\texttt{Operator}\land type(p_{a})=\texttt{InfixExpr}\land
type(p_{b})=\texttt{InfixExpr}$

6 if  _$c1\lor c2$_ then

7 if  _$\neg\exists(m_{1},m_{2})\in\mathcal{M}\mid m_{1}=p_{a}\land
m_{2}=p_{b}$_ then

8 $\mathcal{M}\leftarrow\mathcal{M}\setminus\\{(m_{1},m_{2})\in\mathcal{M}\mid
m_{1}=p_{a}\lor m_{2}=p_{b}\\}$

9 $\mathcal{M}\leftarrow\mathcal{M}\cup\\{(p_{a},p_{b})\\}$

10

11 end if

12

13 end if

14

15 end foreach

Algorithm 2 SubTreeMatcher

###  3.4. How our approach addresses the limitations of AST diff tools

  1. (1)

Lack of support for multi-mappings: Although Algorithm 2 does not generate
multi-mappings by itself, Algorithm 1 aggregates the mappings coming from
different refactoring instances and program element declaration pairs (as
detected by RefactoringMiner) without discarding new mappings for already
mapped subtrees.

  2. (2)

Lack of language clue utilization: RefactoringMiner is utilizing the program
structure, the program element declaration types, and language clues (e.g.,
method calls, method signatures, field references) to reason about and guide
the matching process on specific parts of the ASTs, instead of trying to
randomly match code fragments between the left and right ASTs based on their
similarity.

  3. (3)

Lack of refactoring awareness: Algorithm 1 (lines 13-16) prioritizes mappings
established from refactorings, as their correctness is guaranteed by the
refactoring mechanics.

  4. (4)

Matching semantically incompatible AST node: Algorithm 2 modifies the top-down
phase of GumTree by adding a condition to prevent the matching of SimpleName
nodes with parents having different AST types. Moreover, RefactoringMiner is
guiding the matching process towards semantically compatible mappings by
avoiding to match subtrees from program element declarations of a different
kind.

  5. (5)

Lack of diff support at the commit level: RefactoringMiner detects
refactorings that contribute inter-file-move mappings (Table 1).

##  4\. Benchmark

In this section, we describe the process we followed to create a publicly
available benchmark (Alikhanifard and Tsantalis, 2023) of AST node mappings.

###  4.1. Datasets

We relied on two popular datasets, namely Defects4J (Just et al., 2014), which
includes 835 bug fixes from 17 open-source projects, and Refactoring Oracle
(Tsantalis et al., 2022), which includes over 11K refactorings and code
changes found in 546 commits from 187 open-source projects. Both datasets have
been extensively validated over a long period of time. Defects4J has 10
releases between 2015-2020 and the Refactoring Oracle has been constantly
updated between 2018-2023 by incorporating results from more tools and
supporting more refactoring types. Both datasets have become the de facto
standard for evaluating automated program repair and refactoring mining tools,
respectively. The reason we selected these two datasets to build our benchmark
is because the characteristics of the changes they include pose different
levels of challenge for AST diff tools. Bug fixing commits are a low barrier
for assessing the accuracy AST diff tools, as most changes are small (a few
lines of code), local (typically located within a single method) and rather
simple and straightforward. On the other hand, refactoring commits are more
challenging for AST diff tools, as most changes are big (many lines of code),
dispersed (located within different methods and files) and rather complex
(overlapping changes and refactorings). Table 3 shows the characteristics of
the two datasets. We can clearly observe that the Refactoring dataset has a
higher percentage of cases with multi-mappings, 8 times higher average churn
and a higher percentage of challenging cases compared to Defects4J (as
explained in Section 4.3 challenge expresses how challenging the construction
of the ground-truth diff is).

Table 3. Benchmark characteristics Property | Defects4J | Refactoring Oracle
---|---|---
# cases | 800 | 188
# total number of diff files | 996 | 287
# cases with multi-mapping (%) | 25 (3.1%) | 52 (27.6%)
# cases with refactoring (%) | 107 (13.4%) | 188 (100%)
average churn | 0.011 | 0.086
# low challenge cases (%) | 732 (91.5%) | 70 (37.2%)
# medium challenge cases (%) | 65 (8.1%) | 87 (46.2%)
# high challenge cases (%) | 3 (0.4%) | 31 (16.4%)

Since generating a benchmark of AST node mappings is a rather tedious and
challenging task, and both datasets are large, we included from the
refactoring oracle only the commits that have 1 or 2 modified files, and from
Defects4J 800 out of the 835 total bug fixes.

###  4.2. Tools

We did our best effort to include as many AST diff tools as possible in order
to do a comprehensive analysis of their strengths and weaknesses. The criteria
we set to select an AST diff tool are the following:

  * •

The tool should be publicly available.

  * •

The tool should be executable and provide an API, so that it can
programatically executed.

  * •

The tool should be able to report at minimum AST mappings at statement-level.

The tools that were considered and eventually selected based on our criteria
are shown in Table 4.

Table 4. Considered and selected AST diff tools Tool | Availability | API | AST mappings
---|---|---|---
RefactoringMiner 3.0 | ✓ | ✓ | ✓
GumTree 3.0 (greedy) (Martinez et al., 2023) | ✓ | ✓ | ✓
GumTree 3.0 (simple) (Martinez et al., 2023) | ✓ | ✓ | ✓
GumTree 2.1.0 (Falleri et al., 2014) | ✓ | ✓ | ✓
IJM (Frick et al., 2018) | ✓ | ✓ | ✓
MTDiff (Dotzler and Philippsen, 2016) | ✓ | ✓ | ✓
srcDiff (Decker et al., 2020) | ✗ | ✗ | ✓

(a) AST generator gumtree.gen.jdt-2.1.0

(b) AST generator gumtree.gen.jdt-3.0.0

Figure 17. AST diff with two different AST generators.

The implementation of MTDiff is included in the IJM repository (Frick, 2023).
Moreover, the API of GumTree changed significantly in version 3.0, and thus it
is no longer compatible with the 2.1 version. To avoid problems with class
name clashes, we had to create a shaded version of IJM by moving its class
files into a folder named “shaded” and referencing the classes corresponding
to IJM, MTDiff, GumTree 2.1 by adding the “shaded.” prefix in their qualified
name. RefactoringMiner is 100% compatible with GumTree 3.0, as it generates
the AST diff in objects extending the GumTree 3.0 APIs. Regarding the AST
structure, RefactoringMiner and GumTree 3.0 utilize the library
gumtree.gen.jdt-3.0.0, which wraps around the Eclipse JDT Generator to
generate ASTs. In contrast, the other tools rely on an older version of this
tree generation library, gumtree.gen.jdt-2.1.0. Consequently, there are
differences in the generated AST structures among these tools. For instance,
in version 2.1, the InfixExpression node includes the operator as a label,
while in version 3.0, there is an additional child node to store the operator.
The implications of these differences are illustrated in Figures 17a and 17b.
Clearly, the tree structure in version 2.1 hinders the algorithm’s ability to
generate fine-grained edit actions. Due to these differences in the AST
structure produced by the generators 2.1 and 3.0, we can compute the precision
and recall of the tools compatible with GumTree 2.1 only at statement level.

###  4.3. Structure and format

There are two possible ways to store the output of AST diff tools. The first
is in the form of the AST node mappings found between two ASTs, and the second
is in the form of a sequence of edit actions (e.g., insert, delete, update,
move) that transforms one AST into the other. We decided to store the ground
truth in the form of AST node mappings, as not all tools support the same
kinds of edit actions, and thus their edit scripts are not 100% compatible.
For example, Higo et al. (Higo et al., 2017) introduced a new kind of edit
action, named copy-and-paste, which is not supported by other AST diff tools.
Moreover, in our work we introduced new kinds of edit actions to support
multi-mappings and multi-moves, which are not supported by other AST diff
tools. We believe in this way our benchmark will be more usable in the future
and facilitate future research, regardless of the new edit actions researchers
might come up with.

Figure 18. A sample of human-readable AST diff with intra-file mappings

Our benchmark is structured as follows. For each commit from the Refactoring
dataset, we create a directory named as organization/project/commitSHA-1. For
each bug from the Defects4J dataset, we create a directory named as
ProjectName-BugId. Within each directory, there is a separate json file
storing mappings between program elements and AST nodes for each modified
compilation unit (i.e., Java file) in the diff. Each json file has a mandatory
section for intra-file mappings (i.e., mappings within the file) and an
optional section for inter-file mappings (i.e., mappings in different files)
in case some code is moved from/to this file.

As shown in Figure 18, intra-file mappings section includes two sub-sections.
In the first section, named “matchedElements”, we store pairs of matched
program element declarations, such as type, method, field and enum
declarations. In the second section, named “mappings”, we store pairs of AST
statements or expressions. Each entry in the json file has three properties,
namely “left”, “right” and “info”. The properties “left” and “right” include a
string representation of the matched element on the left and right side of the
diff, respectively. If the element is a declaration, the string representation
is a short signature of the declaration, including its name, and parameters
(only for method declarations). If the element is an AST statement/expression,
the string representation is the actual code corresponding to the
statement/expression in pretty-printed format. The property “info” encodes AST
type and location information in the format LeftASTType[LeftStartOffset-
LeftEndOffset]:RightASTType[RightStartOffset-RightEndOffset]. We decided to
use this format for two main reasons. First, it is human-readable, which makes
easy to understand and manually edit the file if needed. Second, it
facilitates the evaluation framework we propose for assessing the quality of
the diff generated by each tool, which covers different quality dimensions,
such as statement mapping accuracy, program element mapping accuracy and
semantically incompatible mappings. For instance, based on the
“matchedElements” section, we can compute the program element mapping accuracy
by comparing the pairs of program elements listed in this section with the
pairs of program elements matched by an AST diff tool. Based on the “mappings”
section, we can compute the statement mapping accuracy by comparing the
mappings listed in this section with the mappings generated by an AST diff
tool. Finally, based on the “info” property, we can compute the semantically
incompatible mappings by looking for mappings generated by an AST diff tool
that match only the left or right side of a ground-truth mapping.

The inter-file mappings section has the same format as the intra-file mappings
section, with the only difference being that the mappings are grouped based on
the origin or destination file, as it is possible to have code moved from/to
multiple different files. Finally, we include the following metadata at the
commit level (Refactoring dataset) and bug level (Defects4J dataset) to
provide an overview of the commit changes, and facilitate future research.

  * •

Multi-mappings: This is a boolean variable (true/false) to inform about the
presence of AST node multi-mappings in the diff (i.e., one-to-many, many-to-
one, many-to-many). This is a novel feature in AST diff supported only by
RefactoringMiner.

  * •

Left-side churn: This is a ratio variable defined as $\frac{\text{removed
lines}+\text{modified lines}}{\text{total lines}}$ in the left-side files of
the diff.

  * •

Right-side churn: This is a ratio variable defined as $\frac{\text{added
lines}+\text{modified lines}}{\text{total lines}}$ in the right-side files of
the diff.

  * •

Challenge level: This a categorical variable that can take three possible
values, namely low, medium, high to express how challenging the construction
of the ground-truth diff is, as determined by the time taken to construct it.
The construction time depends on the number and complexity of the changes to
be inspected, and the number of missing or incorrect mappings generated by the
tools, which should be manually fixed in the ground-truth diff.

  * •

Comments: This is free-form text explaining the reason the diff is
challenging, along with some arguments justifying some debatable mappings.

###  4.4. Construction process

The process we followed to construct our benchmark for assessing the accuracy
of AST diff tools is as follows:

Step 1 - Diff tools execution: We execute all selected tools listed in Table
4. We extended the directory diff viewer provided by GumTree to include the
diff results of all selected AST diff tools visualized with the classic and
monaco file diff viewers, as shown in Figure 19. Moreover, we designed factory
APIs that can process input from local files (suitable for the Defects4J
dataset), as well as GitHub commits (suitable for the Refactoring dataset).

Figure 19. AST diff output for all selected AST diff tools (Defects4J dataset,
JacksonCore project, bugID 6).

Step 2 - Diff inspection and validation: We inspect the diff generated by each
tool following the diff assessment criteria listed in Section 4.5 to assess
the correctness of the AST mappings in the diff. If there are no debatable
mappings, only the first author of the paper is involved in the inspection. If
there is at least one debatable mapping that the first author is not sure
about, both paper authors are involved in the inspection and try to reach a
consensus using arguments justifying their opinions. In the vast majority of
the examined cases with debatable mappings the two co-authors were able to
reach a consensus. In the rare cases that this was not possible, the co-
authors asked the opinion of the current members of the Refactoring research
group at Concordia University (listed in the Acknowledgments Section), and the
debate was resolved with a majority vote. As a matter of fact, there were 24
debatable cases in the Defects4J dataset and 9 debatable cases in the
Refactoring dataset, which constitute around 3% of the examined cases.
Overall, the inspection and validation process lasted 6 person-months.

Step 3 - Ground truth generation: There are three possible outcomes after the
inspection and validation of a diff:

  * •

At least one of the tools generates the optimal diff with all mappings
assessed as correct and without any missing mappings. In that case, we use one
of these tools to generate the ground-truth in the human-readable diff format.

  * •

A tool generates a part of the optimal diff, while another tool generates the
remaining part of the optimal diff. In that case, we combine the optimal diff
parts from multiple tools to generate the ground-truth in the human-readable
diff format.

  * •

There are some AST mappings that all tools matched them incorrectly or missed
them. In that case, we programmatically add the correct mappings or missing
mappings to generate the ground-truth in the human-readable diff format.

###  4.5. Diff assessment criteria

When inspecting the AST diff generated by the tools to construct the ground-
truth diff, we check the following criteria (properties) to assess the
correctness of the mappings:

  1. (1)

Statement continuity: Consecutive mapped statements should remain in the same
relative execution order. In many cases, there exist multiple identical
statements (e.g., break, continue, return) within the same method. This
introduces multiple potential matching candidates for approaches that generate
mappings at statement level, such as RefactoringMiner. With the statement
continuity criterion, we check whether statements with multiple matching
candidates have the same corresponding statements around them (i.e., before
and after) on the left and right side of the diff.

  2. (2)

Compliance with developer actions and intent: The diff should comply with the
changes the developer (i.e., commit author) actually performed. The intention
of the developer is often expressed in the commit message or pull request
discussions. By reading the commit message of the example discussed in Section
2.2, it becomes clear that the intention of the developer was not to rename
method getAllPaths to getAllPathsWork, as expressed in the diff shown in
Figure 3, but rather to enhance the functionality of the already existing
method getAllPaths to “cache the values returned by getAllPaths to avoid the
multiple ImmutableBiMap objects being created for the same working directory”,
as expressed in the diff shown in Figure 4 with the new functionality of
getAllPaths being highlighted in green color and the original functionality
being extracted into method getAllPathsWork.

  3. (3)

Aesthetic appeal or Visual appeal has been commonly used in computer graphics
research as a subjective measure to evaluate the quality of a visualization
(South et al., 2022; Eschner et al., 2023). An AST diff can be considered as a
visualization of the changes that took place on the AST of a piece of source
code. Thus, a good quality diff should be aesthetically appealing, intuitive,
natural, clear and easy-to-understand. Incorrect mappings introduce visual
noise or clutter in the diff visualization, and make it look unappealing,
counter-intuitive, unnatural, ambiguous and confusing, as in the examples
shown in Figures 1, 7 and 9.

  4. (4)

Consistent control flow restructuring: In the case of control flow
restructuring (e.g., inverted conditionals, deleted/added conditionals, change
in the nesting level or scope of conditionals, merged/split conditionals) the
diff should reflect the change as being behavior-preserving. For example, in
the diff shown in Figure 20 an if statement is deleted and replaced with a
conditional expression, but at the same time the condition of the if statement
“sf == null || sf.getParam() == null” is inverted in the conditional
expression as “sf != null && sf.getParam() != null”. Since, the condition is
inverted, we see that the execution of the statements is inverted too.
Initially, the body of the if statement included statement “return null;”,
which is now moved to the “else” part of the conditional expression “: null”.
On the other hand, the last statement of the method on the left side “return
sf.getParam()[featureIndex];”, which is executed only if the condition of the
if statement is evaluated as false, is moved to the “then” part of the
conditional expression “? sf.getParam()[featureIndex]”. The way the statements
and sub-expressions are mapped in the diff preserves the program behavior
after the control flow restructuring, and thus gives us the confidence to
consider these mappings as correct.

  5. (5)

Consistent identifier renaming: The mappings should conform to consistent
identifier renames. For example, method call renames within statement mappings
should conform with the corresponding method declaration renames and
field/variable reference renames within statement mappings should conform with
the corresponding field/variable declaration renames. As discussed in Section
2.3, the diff shown in Figure 5 does not conform to consistent identifier
renaming, as the reference to variable object is matched with itemKey, while
the declaration of variable object is renamed to item. On the other hand, the
diff shown in Figure 6 conforms to the consistent identifier renaming
criterion.

  6. (6)

Consistent inline comment location: In many cases, there exist similar
statements that go through similar changes within the same method. This
introduces multiple potential matching candidates for approaches that generate
mappings at statement level, such as RefactoringMiner. Moreover, the
statements around them might also change. Thus, the statement continuity
criterion is not helpful in that case. However, inline comments within the
method might remain unchanged or be slightly changed. With the consistent
inline comment location criterion, we check whether statements with multiple
matching candidates are surrounded by the same inline comments on the left and
right side of the diff. For example, in the diff shown in Figure 21 there are
two assignment statements for variable text, which are identical and change in
exactly the same way on the right side of the diff. Moreover, the assertion
statements that follow are also very similar and change as well. Therefore,
there is some ambiguity about what is the right mapping for these statements.
The way the statements are mapped in the diff makes them surrounded by the
same unchanged inline comments, and thus gives us the confidence to consider
these mappings as correct.

Figure 20. AST diff generated by RefactoringMiner for commit
https://github.com/NLPchina/ansj_seg/commit/913704e. Figure 21. AST diff
generated by RefactoringMiner for commit https://github.com/apache/commons-
lang/commit/5111ae7.

##  5\. Evaluation

Following the template defined by Briand et al. (Briand et al., 1996) for the
Goal-Question-Metric (GQM) paradigm, we define our study as: We analyze six
AST diff tools for the purpose of evaluating their accuracy with respect to
AST node mappings from the viewpoint of code reviewers and developers that
want to understand the changes in a commit or pull request in the context of a
benchmark including bug-fixing and refactoring commits from open-source
projects.

More specifically, we investigate the following research questions:

  1. RQ1.

What is the accuracy of each tool in multi-mappings?

  2. RQ2.

How many semantically incompatible mappings are generated by each tool?

  3. RQ3.

What is the accuracy of each tool in matching program elements (i.e., method,
field declarations)?

  4. RQ4.

How do refactorings affect the accuracy of each tool?

  5. RQ5.

How many mappings are missed or mismatched by each tool due to the lack of
commit-level change analysis?

  6. RQ6.

What is the overall accuracy of each tool?

  7. RQ7.

What is the percentage of perfect diffs generated by each tool?

  8. RQ8.

What is the execution time of each tool?

  9. RQ9.

What is the effect of the changes presented in Section 3.2 on the accuracy of
RefactoringMiner 3.0 over the prior version 2.0?

In many of the subsections that follow we provide precision, recall, and
F-score, which are computed as follows:

###### Definition 5.0.

Given the set of AST node mappings listed in the benchmark $S_{B}$ and the set
of AST node mappings generated by a tool $S_{T}$, $\text{True
Positives}=S_{B}\cap S_{T}$, $\text{False Positives}=S_{T}\setminus S_{B}$ and
$\text{False Negatives}=S_{B}\setminus S_{T}$. Therefore, the precision and
recall of a tool $S_{T}$ is computed as
$\text{Precision}=\frac{|TP|}{|TP|+|FP|}$
$\text{Recall}=\frac{|TP|}{|TP|+|FN|}$
$\text{F-score}=\frac{2\times|TP|}{2\times|TP|+|FP|+|FN|}$

Since all tools are able to match identical AST sub-trees with 100% accuracy,
including all AST node mappings in a file would artificially increase the
computed precision and recall. As a result, we decided to exclude all AST node
mappings nested under unchanged program elements from both $S_{B}$ and $S_{T}$
when computing precision and recall.

###  5.1. RQ1: Multi-mappings

####  5.1.1. Experimental procedure

For this research question, we focus our analysis on multi-mappings, i.e., AST
nodes that have more than one corresponding nodes on the right side of the
diff (one-to-many mappings), or the left side of the diff (many-to-one
mappings). More specifically, we filter all AST node mappings marked as multi-
mappings in our benchmark $S_{B}$, and compute the accuracy of the AST diff
tools on this particular subset of mappings. RefactoringMiner is the only tool
that supports multi-mappings. The other AST diff tools, typically match only
one instance of the duplicated code, and the other duplication instances are
either unmatched (i.e., appear as deleted/added code in the diff) or are
mismatched with irrelevant code, as happened in the case shown in Figure 1.
With this research question, we want to highlight the negative impact that the
lack of support for multi-mappings has on the accuracy of the tools.

####  5.1.2. Results and discussion

Table 5. Precision and recall for multi-mappings in both datasets RM 3.0 | GT 3.0 greedy | GT 3.0 simple | GT 2.1.0 | IJM | MTDiff
---|---|---|---|---|---
Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall
${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{47.0}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{10.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{59.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{10.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{44.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{8.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{18.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{2.6}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{29.6}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{7.5}$ |

As shown in Table 5, IJM is clearly the worst-performing tool on multi-
mappings with the lowest precision and recall, as in many cases it fails to
match even a single instance of the duplicated code. This result is quite
surprising as IJM is essentially an improved version of GumTree 2.1.0, which
has a far better multi-mapping accuracy. Therefore, we performed an in-depth
investigation to find the reason behind IJM’s poor performance. We discovered
that IJM authors modified the structure of AST by merging SimpleName leaf AST
nodes with their parent nodes. This was done to avoid the problem of
semantically incompatible mappings, as explained in Section 2. However, this
change made the depth of the AST shorter. Normally, a method invocation has a
minimum height of 2, as the name of the method is a leaf SimpleName node
nested under the MethodInvocation parent node. After the merging, the height
of the MethodInvocation subtree becomes 1. As a result, the first phase of IJM
that executes GumTree on the entire files to find the largest identical
subtrees, fails to match statements of height equal to 1 (i.e., method
invocation statements with a merged name node), because GumTree employs a
threshold for the hyperparameter $minHeight$ (i.e., length of the longest path
from one leaf to the root of the subtree) equal to 2. For this reason, many of
the duplicated statements that are simple method invocations without arguments
are not getting matched with their corresponding statements in the extracted
methods.

From the remaining tools, RefactoringMiner has by far the highest accuracy
(99.7% precision, 98.4% recall), which is expected as it is the only tool
supporting multi-mappings. GumTree 3.0 (simple) is the second-best performing
tool on multi-mappings with a precision of 59% and a recall of 10%. GumTree
3.0 (greedy) has a similar recall to GumTree 3.0 (simple), but it has a lower
precision by -12%, as due to its greedy nature, it tends to mismatch the
remaining duplication instances with irrelevant (possibly newly added) code.
GumTree 2.1.0 has a very similar performance to GumTree 3.0 (greedy) with a
slightly lower precision and recall (around -2%).

RQ1 findings: As expected all tools that do not support multi-mappings have a
low recall within the range 2-10%. Moreover, the tools that are more greedy in
nature (GumTree 3.0 greedy) have lower precision than their non-greedy
counterparts (GumTree 3.0 simple), because they tend to force incorrect
mappings for the unmatched multi-mappings. Based on their multi-mapping
accuracy, the tools are ranked as follows: (1) RefactoringMiner 3.0
(F-score=99%) (2) GumTree 3.0 simple (F-score=17.5%) (3) GumTree 3.0 greedy
(F-score=17%) (4) GumTree 2.1.0 (F-score=14.5%) (5) MTDiff (F-score=12%) (6)
IJM (F-score=4.5%)

###  5.2. RQ2: Semantically incompatible mappings

####  5.2.1. Experimental procedure

For this research question, we investigate AST node types that can play
different semantic roles in different contexts. In most cases, the different
semantic roles that can be played by an AST type are incompatible with each
other. However, language-agnostic diff tools match AST nodes of the same type,
regardless of their semantic role in the program.

Since all tools use the Eclipse JDT parser for generating ASTs, we analyzed
the Eclipse JDT documentation to find AST types used in multiple contexts.
Below we list the AST types that are involved in multiple contexts and play a
semantically incompatible role in each context:

  * •

Block: This AST type is used in 7 different contexts, namely as (1) the body
of a method declaration, (2) the body of an initializer declaration, (3) the
body of a catch clause, (4) the body of a try statement, (5) the body of a
synchronized statement, (6) the body of a finally block, and (7) the body of
control statements (while, for, if).

  * •

SingleVariableDeclaration: This AST type is used in 5 different contexts,
namely as (1) catch clause exception, (2) enhanced-for formal parameter, (3)
method declaration parameter, (4) lambda expression parameter, and (5) pattern
variable in instanceof expression (Java 17 feature).

  * •

MethodDeclaration: This AST type is used to represent both method and
constructor declarations. A constructor serves the semantic role of creating
instances of a class and initializing its attributes, while a method serves
the semantic role of providing the behavior for an instance of a class based
on its current state. Thus, it makes no semantic sense to match a constructor
with a method.

  * •

Modifier: This AST type is used to represent access modifiers (public,
private, protected), static, abstract, final, native, synchronized, transient,
volatile, strictfp, default, sealed, and non-sealed modifiers. Among these
modifiers, only the access modifiers are semantically compatible with each
other, and the final, sealed, non-sealed modifiers (Java 17 feature) are
semantically compatible with each other. All other modifiers have a unique
semantic role in the program, and thus are not replaceable by another modifier
(i.e., should not be matched with another modifier).

  * •

Type: This AST type is used in 22 different contexts, namely (1) method
declaration return type, (2) receiver type and (3) list of thrown exception
types, (4) record pattern type (Java 19 feature), (5) instanceof expression
right operand, (6) type declaration super class type and (7) list of
implemented interface types, (8) list of permitted types (Java 17 feature) (9)
cast expression type, (10) class instance creation type, (11) creation
reference type, (12) field declaration type, (13) variable declaration type,
(14) method reference parameter type (in Javadoc), (15) type literal type,
(16) type method reference type, (17) annotation type member declaration type,
(18) wildcard-type bound, (19) array-type component and (20) element type,
(21) qualified-type qualifier, and (22) parameterized-type type.

  * •

SimpleName: This AST type is used in 25 different contexts, namely (1) method
declaration name and (2) receiver qualifier, (3) record pattern name (Java 19
feature), (4) variable declaration name, (5) type parameter name, (6-8)
type/super/expression method reference name, (9) field access name, (10) super
field access name, (11) method invocation name, (12) super method invocation
name, (13) method reference parameter name (in Javadoc), (14) method reference
name (in Javadoc), (15) member reference name (in Javadoc), (16) enum constant
declaration name, (17) annotation type member declaration name, (18) type
declaration name, (19) labeled statement label, (20) continue statement label,
(21) break statement label, (22) member value pair name (in annotations), (23)
qualified-type name, (24) qualified-name name, and (25) name-qualified type
name.

###### Definition 5.0.

A mapping $M=(m_{1},m_{2})\in S_{T}$ (i.e., the mappings generated by tool
$T$) is considered as semantically incompatible if $m_{1}$ and $m_{2}$ have
the same AST node type, the parents of $m_{1}$ and $m_{2}$ have a different
AST node type (i.e., different context), and $M\notin S_{B}$, where $S_{B}$ is
our benchmark of mappings.

Based on this definition and the mappings generated by a tool $S_{T}$, we can
compute the number of semantically incompatible mappings for tool $T$.
Especially for modifiers, our definition is slightly modified as semantically
incompatible modifiers can have parents of the same AST type.

###### Definition 5.0.

A modifier mapping $M=(m_{1},m_{2})\in S_{T}$ is considered as semantically
incompatible if $m_{1}$ and $m_{2}$ have the Modifier AST type, but belong to
a different semantic group (i.e., access modifiers, seal modifiers, and each
remaining modifier in its own group).

####  5.2.2. Results and discussion

Table 6. Number of semantically incompatible mappings in both datasets AST node Type | RM 3.0 | GT 3.0 (greedy) | GT 3.0 (simple) | GT 2.1.0 | IJM | MTDiff
---|---|---|---|---|---|---
Block | 0 | 83 | 116 | 79 | 61 | 77
SingleVariableDeclaration | 0 | 4 | 3 | 1 | 0 | 5
MethodDeclaration | 0 | 0 | 0 | 1 | 0 | 6
Modifier | 0 | 6 | 1 | 7 | 6 | 9
Type | 0 | 118 | 94 | 60 | 0 | 398
SimpleName | 0 | 418 | 0 | 356 | 18 | 793
Total | 0 | 629 | 214 | 504 | 85 | 1288

As we can observe from Table 6, RefactoringMiner is the only tool that does
not generate semantically incompatible mappings for the six investigated AST
node types. This can be attributed to its semantic-aware algorithm design that
uses language clues and refactoring information to guide the matching process,
instead of randomly matching AST subtrees based on their similarity,
regardless of their semantic context and relevance. On the other hand, all
other examined tools exhibit semantic violations to a greater or lesser
extent. Below we list the most common semantic violations for each AST node
type, and discuss the individual behavior of each tool.

  * •

Block violations: The most common semantic violation for blocks is matching
the body of a method declaration with the body of and if, for, or try
statements. All tools are affected by this problem with GumTree 3.0 simple
having the largest number of instances (116) and IJM having the smallest
number of instances (61). This usually happens when the body of the control
statement contains a large portion of the code inside the method body, and
there is some control re-structuring (e.g., surrounding the body of a method
within a newly added try block).

  * •

SingleVariableDeclaration violations: The most common semantic violation for
single-variable-declarations is matching the formal parameter of an enhanced-
for with a method parameter. All tools except for IJM and RefactoringMiner
exhibit this behavior. MTDiff is the only tool matching a catch clause
exception declaration with a method parameter or an enhanced-for formal
parameter.

  * •

MethodDeclaration violations: GumTree 2.1.0 and MTDiff are the only tools
matching a constructor with a method. MTDiff has the largest number of
instances (6), while GumTree 2.1 has only one instance of this violation.

  * •

Modifier violations: The most common semantic violation for modifiers is
matching access modifiers (public, private, protected) with the static
modifier. All tools except for RefactoringMiner exhibit this behavior with
MTDiff having the largest number of instances (9) and GumTree 3.0 simple
having only one instance.

  * •

Type violations: The most common semantic violation for types is matching the
type of a field declaration with the return type of a method or the type of a
local variable declaration. Moreover, matching the type of a method parameter
with the type of a local variable declaration is another common semantic
violation. MTDiff, which has the largest number of instances for this
violation tends to match the type within type-literals (i.e., Type.class) with
regular type references as the aforementioned ones.

  * •

SimpleName violations: The most common semantic violation for simple names
(i.e., identifiers) is not matching the three components of a method
invocation (i.e., receiver, name, arguments) accordingly, and also mismatching
these three components with semantically irrelevant simple names, which are
not even within method invocations. As already discussed in Section 5.1, IJM
modified the structure of AST by merging SimpleName leaf AST nodes with their
parent nodes to avoid this semantic violation, which explains the reason it
has only 18 instances of this violation. IJM violations mainly correspond to
method invocation arguments being matched with a method invocation receiver,
as the method names are merged with their parent method invocations, and thus
they cannot be semantically mismatched.

A notable finding is that GumTree 3.0 simple has zero semantic violations for
simple names (i.e., identifiers), while it has 94 for type references, in
contrast to its greedy counterpart, which has semantic violations for both of
these AST types. Both versions of GumTree follow the same top-down phase to
find the largest identical sub-trees with the minHeight hyperparameter
threshold configured equal to 2. As a result, while SimpleName nodes with
identical values cannot be matched in this phase, as their height is equal to
1, Type nodes with identical values can be matched, as their height is at
minimum equal to 2 (e.g., a SimpleType has a SimpleName node as leaf with the
actual name of the type). In the bottom-up phase that follows, the greedy
version applies a non-conservative approach that matches AST subtrees of
height equal to 1 (i.e., leaf AST nodes), while the simple version is more
conservative and avoids this approach. This difference in the bottom-up phase
of the GumTree simple version is responsible for having zero semantic
violations for SimpleName nodes. Another notable but expected finding is that
the tools which are more greedy in nature (i.e., GumTree greedy and MTDiff)
have the largest number of semantically incompatible mappings.

RQ2 findings: RefactoringMiner is the only tool with zero semantic violations
for the six investigated AST node types. The tools that are more greedy in
nature (i.e., GumTree greedy and MTDiff) tend to generate a larger number of
mappings with semantic violations. Based on their number of semantically
incompatible mappings, the tools are ranked as follows: (1) RefactoringMiner
3.0 (0 semantic violations) (2) IJM (85 semantic violations) (3) GumTree 3.0
simple (214 semantic violations) (4) GumTree 2.1.0 (504 semantic violations)
(5) GumTree 3.0 greedy (629 semantic violations) (6) MTDiff (1288 semantic
violations)

###  5.3. RQ3: Program element mappings

####  5.3.1. Experimental procedure

For this research question, we investigate the ability of the tools to match
correctly program elements (i.e., type, method, field declarations). More
specifically, we filter all AST node mappings corresponding to type, method,
and field declarations in our benchmark $S_{B}$, and compute the accuracy of
the AST diff tools on this particular subset of mappings. As most AST diff
tools are language-agnostic, they do not utilize any language clues in order
to guide the matching process. Instead, they try to “blindly” find the largest
identical (or similar) AST sub-trees in a pair of files, and then match the
corresponding method/field declarations containing these AST sub-trees.

However, this approach has some undesired implications. When a relatively
large part of a method is extracted into a new method, the original method
declaration on the left side is matched with the extracted method declaration
on the right side, and thus the remaining method declaration (calling the
extracted method) appears as newly added on the right side of the diff. This
gives the code reviewers the wrong impression that the original method is
“renamed” to the extracted method, which makes it more difficult to understand
the actual change intended by the commit authors (i.e., Extract Method
refactoring). As we will see in the next subsection regarding RQ4, Extract
Method is the most common refactoring in our dataset. Moreover, there is
empirical evidence showing that Extract Method is the most popular method-
related refactoring applied by developers (Negara et al., 2013). Silva et al.
monitored 285 GitHub projects for a period of two months and found that
Extract Method refactoring had the largest number of instances (Silva et al.,
2016). Therefore, the implications of not handling properly Extract Method
refactorings when generating AST diff are rather significant.

Regarding field declarations, RefactoringMiner is the only tool among the
compared ones that uses field references to match renamed fields. More
specifically, in Phase 2 (Figure 11) it first establishes the corresponding
method pairs within a class (including methods with changes in their
signature), and then utilizes the statement mappings within the matched method
pairs to find name-identifier replacements referring to a pair of field
declarations. If these replacements are consistent across all method pairs,
then we have high confidence that the referenced pair of fields should be
matched as renamed. On the other hand, traditional AST diff tools rely only on
the similarity of the field declaration AST sub-trees to match fields.
However, field declarations are in general small sub-trees as they consist
only of a type, a name, a list of modifiers, and an optional initializer
expression, and thus the pairs of matching field declarations are rather
ambiguous when multiple fields have been renamed in a class. In a previous
work (Tsantalis et al., 2022), we showed that GumTree 2.1.2 had 78% precision
and 70% recall in the detection of renamed fields, and 75% precision and 62%
recall in the detection of field type changes. Negara et al. (Negara et al.,
2013) found that Rename Field is the second most popular refactoring manually
applied by developers after Rename Local Variable. Moreover, Ketkar et al.
(Ketkar et al., 2020) 416K commits from 129 open-source projects and found
that field type changes are more commonly and frequently applied by developers
than field renames. They also found that developers who changed the type of a
variable or attribute, they also renamed it in 55% of the examined instances.
Therefore, field type changes and renames tend to co-occur, thus making the
matching of field declarations even more ambiguous for traditional AST diff
tools.

####  5.3.2. Results and discussion

Table 7. Precision and recall for program element mappings in both datasets Prog |  | RM 3.0 | GT 3.0 greedy | GT 3.0 simple | GT 2.1.0 | IJM | MTDiff
---|---|---|---|---|---|---|---
Elem | # | Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall | Precision | Recall
Type | 1431 | $100$ |  | $100$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.3}$ |
Enum | 17 | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |  | $100$ |
Method | 2278 | $100$ |  | $100$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{93.5}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{75.1}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{92.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{77.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{93.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{75.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{82.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{88.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{75.4}$ |
Field | 245 | $100$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.8}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.5}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{52.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{97.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{52.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{97.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{59.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{98.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{44.5}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{97.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{57.6}$ |
Overall | 3971 | $100$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.9}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{96.4}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{82.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{95.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{83.7}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{96.6}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{83.3}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{99.6}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{86.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{93.2}$ |  | ${{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}{}{}{}{}{}}{{}{}{}{}{}}}{82.6}$ |

Table 7 shows the mapping accuracy of the tools per program element type. The
second column in Table 7 shows the number of instances for each program
element type that were considered in the computation of precision and recall,
which corresponds to the number of program elements with changed AST trees. We
would like to emphasize that we excluded the program elements that have
identical AST trees, since all tools can match them with 100% accuracy, and
thus their inclusion would artificially increase the computed precision and
recall. For the sake of providing complete information, the total number of
type, enum, method, and field declarations in our benchmark is 2745, 139,
47795, and 16438, respectively. From the aforementioned numbers, we can infer
that only a small portion of program elements changed in the benchmark commits
(i.e., 52% of the type declarations, 12% of the enum declarations, 4.8% of the
method declarations, and 1.5% of the field declarations).

Based on the results shown in Table 7 all tools can match type and enum
declarations with a high precision and recall. This is an expected outcome, as
type declarations are typically large AST subtrees (i.e., they include methods
and fields), and thus it is very uncommon to have different type declarations
with highly similar AST trees (i.e., there is less ambiguity). Moreover, we
can observe that all GumTree-based tools have a very similar precision
(between 99.2-99.9%) and recall (between 98.3-98.9%) in matching type/enum
declarations. However, RefactoringMiner is the only tool that achieves 100%
accuracy, as it relies on method and field signatures to match renamed/moved
classes (Figure 11, Phase 3), and thus can match classes even if their method
bodies have been extensively modified.

Regarding method declarations, RefactoringMiner has an almost perfect
precision and recall with only one false positive and one false negative. The
second-best performing tool is IJM, which has 99.4% precision and 82.7%
recall. This good performance can be attributed to partial matching, which
restricts the scope of matching to method declarations with the same signature
(i.e., first, IJM attempts to match methods only by their signature, and then
it attempts to match the remaining methods by their signature and by their
method body). All other tools have a quite close performance with a precision
ranging between 88-94% and a recall ranging between 75-77%.

Regarding field declarations, RefactoringMiner has a perfect precision with