A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms

In this step, we tokenize the file before and after a revision. Instead of using punctuation and spaces, we use the parsed AST of the source file to tokenize the file. For example, a string literal containing punctuation and spaces is considered as a single token.

For a Java file, we first use the Eclipse JDT parser to generate a standard JDT AST. Then, we extract the tokens from value of each AST node. Notice that we ignore AST nodes representing comments and Javadocs. Because comments and Javadocs are typically not treated as code [17]. As a result, we retrieve two token lists for a file before and after a revision, respectively. The token lists are not impacted by the used AST by each algorithm

In this step, we separately group mappings of AST nodes along statements for $A_{1}$ and $A_{2}$. In an AST, a statement (e.g., a method declaration) can have descendant statements. For each statement in the source and target ASTs that are being analyzed by an algorithm, we first group the nodes that belong to the statement but do not belong to its descendant statements. For instance, our framework groups $n_{1}$, $n_{2}$, and $n_{3}$ in Fig. 1(b) for the type declaration PublishedAddressPolicy. Then, we find the generated mappings by the algorithm for the grouped nodes. These mappings are grouped for the statement.

In this step, we separately calculate mappings of statements and tokens for $A_{1}$ and $A_{2}$. Among the grouped mappings for each statement, we can directly find the mapping for the statement. For instance, in Fig. 1(b), $n_{1}$ represents the type declaration PublishedAddressPolicy and the mapping of $n_{1}$ is considered as the mapping of the declaration.

For a token, we refer to an AST node whose corresponding program element contains the token as a relevant node of the token. Among the relevant nodes of a token, we refer to the node of the lowest level as the directly relevant node of the token. In return, we refer to the token as a directly relevant token of the node. We take the first HashMap of line 1 in Fig. 1(a) as an example. In the used AST by GT shown in Fig. 1(b), $n_{1}$, $n_{4}$, $n_{6}$, $n_{7}$ and $n_{8}$ are relevant nodes of the token. And the directly relevant node for the token is $n_{8}$. In the used AST by IJM shown in Fig. 2(a), $n_{1}$, $n_{3}$ and $n_{5}$ are relevant nodes of the token. And the directly relevant node for the token is $n_{5}$.

An AST node can have several directly relevant tokens. For instance, the node $n_{5}$ in Fig. 2(a) has three directly relevant tokens including a HashMap and two Integer tokens. Such tokens compose the value of $n_{5}$. Another example is $n_{1}$ in Fig. 2, which has two directly relevant tokens including the class and PublishedAddressPolicy tokens in Fig. 1(a). The PublishedAddressPolicy token is the value of the node, while the class token does not belong to its value.

We observe that a token’s mapping is determined by the mapping of its directly relevant node. We also take the first HashMap of line 1 in Fig. 1(a) as an example. In Fig. 1, GT maps $n_{8}$ to $n_{59}$—indicating that the token is mapped to the HashMap of line 3 in Fig. 1(a). And in Fig. 2, IJM maps $n_{5}$ to $n_{13}$—indicating that the token can only be mapped to a directly relevant token of $n_{13}$.

For each node of the source and target ASTs, we calculate all the directly relevant tokens and list the tokens according to their character positions. Then, for each pair of mapped nodes, we map tokens from the lists of directly relevant tokens of the nodes. If both lists have only one token, we directly map two tokens. Otherwise, we separately map the tokens composing the value of the nodes and other tokens, since tokens composing the value of a node can only be mapped to those composing the value of another node. For the tokens composing the values of the two nodes, we first sequentially map identical tokens between the two lists and then map the tokens (including the first and last tokens) that are surrounded by already mapped pairs of tokens. Mapping program elements surrounded by already mapped pairs is a commonly used heuristic by program element mapping algorithms [20]. After that, our framework applies the same method to map the tokens that do not belong to the value of the two nodes.

For instance, in Fig. 2, $n_{5}$ and $n_{13}$ are mapped. The directly relevant tokens of $n_{5}$ include HashMap, Integer and Integer. And the directly relevant tokens of $n_{13}$ include Map, Integer and Integer. All of the tokens belong to the values of the two nodes. We first sequentially map the two Integer tokens between the two lists. HashMap and Map are surrounded by already mapped tokens and they are further mapped.

As a result, we calculate mappings of tokens using the generated mappings of the AST nodes by $A_{1}$ and $A_{2}$. We further group mappings of tokens along each statement based on the grouped mappings of AST nodes for the statement.

In this step, we calculate statements with inconsistent mappings for comparing $A_{1}$ and $A_{2}$. For each statement in the file before and after the revision, we first calculate whether the two algorithms inconsistently map the statement. Then, for each token in the statement, we calculate whether the two algorithms inconsistently map the token. Finally, we output statements with inconsistent mappings and for each statement, we group the inconsistent mappings of the statement and its tokens by comparing the two algorithms.

In this step, we compare the similarity of mapped statements and tokens across each pair of different algorithms. By performing the comparison, we determine the accuracy of each algorithm in the mapping of a statement or a token. In this section, we introduce how to determine the accuracy of each algorithm by performing the comparison. In Section V-F, we elaborate how to compare the similarity of mapped statements and tokens by different algorithms.

Let us denote the similarity between two program elements $e$ and $\hat{e}$ as $Sim(e,\hat{e})$. The elements can be statements or tokens. Suppose that two algorithms ($A_{0}$ and $A_{1}$) map a program element $e_{0}$ to two different elements $e_{1}$ and $e_{2}$, respectively. We notice that the two algorithms also inconsistently map $e_{1}$ and $e_{2}$. Suppose that $A_{0}$ maps an element $e_{3}$ to $e_{2}$, and $A_{1}$ maps an element $e_{4}$ to $e_{1}$. In other words, $A_{0}$ generates two mappings $\{\langle e_{0},e_{1}\rangle,\langle e_{3},e_{2}\rangle\}$. And $A_{1}$ generates two mappings $\{\langle e_{0},e_{2}\rangle,\langle e_{4},e_{1}\rangle\}$.

Suppose that $Sim(e_{0},e_{1})$ is larger than $Sim(e_{0},e_{2})$, we determine that $A_{0}$ is more accurate than $A_{1}$ in mapping $e_{0}$. However, it is not enough to determine that the mapping of $e_{0}$ to $e_{1}$ is better than the generated mappings by $A_{1}$. We must also check the condition: $Sim(e_{0},e_{1})>Sim(e_{4},e_{1})$, i.e., $A_{0}$ is also more accurate than $A_{1}$ in mapping $e_{1}$. If this condition is also satisfied, we determine that $A_{1}$ inaccurately maps $e_{0}$ and $e_{1}$. Similarly, we can also determine if the two generated mappings by $A_{0}$ are inaccurate.

Given a pair of algorithms and a file revision, we calculate the statements with inconsistent mappings. For each statement with inconsistent mappings, we perform the above comparison for the mappings of the statement and its tokens as generated by the two algorithms that are being compared. Consequently, we calculate statements with inaccurate mappings for each algorithm.

For each studied algorithm, we separately compare it with the other two studied algorithms. Finally, we calculate a union set of statements with inaccurate mappings for any of the algorithms that are being compared.

Our aim is to automatically compare the similarity of mapped statements and tokens by different algorithms. To realize this aim, we perform a manual analysis of statements with inconsistent mappings. Also, we verify if statements with inconsistent mappings can expose the inaccurate mappings as generated by the algorithms.

In this study, we analyze ten open-source Java projects. Table I presents statistics of the ten studied projects. These projects were analyzed by prior studies [17, 12]. We collect the commits of the projects from the creation date of the projects to January 2019.

We can compare three pairs of algorithms, namely GT vs. MTD, GT vs. IJM and MTD vs. IJM. For each pair of algorithms, we sample 50 file revisions for which the two algorithms inconsistently map program elements from the studied projects. For each file revision, we analyze all the statements before and after the revision that involve the inconsistent mappings. We analyze 178, 191 and 206 statements for comparing the three pairs of algorithms, respectively. In total, we analyze 575 statements. For each statement, we determine the accuracy of mappings as generated by each of compared algorithms using Frick et al.’s criteria [12]. In total, we make 1,150 ($575\times 2$) determinations.

The first and second author of this paper separately analyzed the statements with inconsistent mappings. Both authors have at least three years of programming experience in Java. We calculate Fleiss’ Kappa [10] to estimate the agreement of the two annotators’ determination results. The Kappa value is 0.81, which indicates an excellent agreement. Finally, the two annotators compared their determination results to uncover disagreements. For each statement with a disagreement, the annotators further discussed the accuracy of the generated mappings by the two compared algorithms.

We analyze all the statements with inaccurate mappings to design similarity measures to distinguish accurate and inaccurate mappings of statements and tokens. We categorize the statements with inaccurate mappings for the algorithms along each similarity measure. For each statement with inaccurate mappings, we consider if we have designed a measure that can identify the inaccurate mappings. If we have designed such a measure, we categorize the statement to the category of the measure. Otherwise, we try to design a new similarity measure to distinguish the accurate and inaccurate mappings. By doing so, we design hierarchical similarity measures for two statements and two tokens.

From our manual analysis, we have the following findings.

• $\bullet$

  Among the 178 statements for comparing GT and MTD, 71 and 129 statements involve inaccurate mappings as generated by GT and MTD, respectively. Among the 191 statements for comparing GT and IJM, 114 and 91 statements involve inaccurate mappings as generated by GT and IJM, respectively. Among the 206 statements for comparing MTD and IJM, 113 and 117 statements involve inaccurate mappings as generated by MTD and IJM, respectively.

• $\bullet$

  For each statement with inconsistent mappings for comparing two algorithms, at least one algorithm is determined to generate inaccurate mappings. Hence, statements with inconsistent mappings can expose the inaccurate mappings as generated by the algorithms.

• $\bullet$

  There exist cases where two algorithms consistently produce an inaccurate mapping of a statement or a token.

In total, we find 185 ($71+114$), 242 ($129+113$), 208 ($91+117$) statements with inaccurate mappings for GT, MTD and IJM, respectively. Based on our observation, we design two similarity measures for comparing two statements and four similarity measures for comparing two tokens. Table II presents the six measures. Notice that we define two tokens with the same value as identical tokens. We use the six similarity measures collectively to compare the generated mappings by different algorithms. In the remaining part of this section, we first introduce the six measures and our categorization results for the statements with inaccurate mappings. Then we describe the usage of the proposed measures.

The six similarity measures are elaborated below.

NIT is defined as the number of mapped identical tokens between a pair of mapped statements. Two mapped statements with a larger NIT are more similar and an NIT of 0 indicates that the two statements are highly dissimilar. If two statements are mapped with an NIT of 0, we determine the mapping as inaccurate. Otherwise, for a pair of mapped statements, we check if the mapping of one of the statements to another statement can achieve a larger NIT. For instance, in Fig. 5(a), MTD inaccurately maps the statements at lines 1 and 2, and the NIT is 0. In Fig. 5(b), GT maps the statements at lines 1 and 2 with an NIT of five. IJM maps the statements at lines 1 and 3 with an NIT of four. We determine that GT is more accurate than IJM in mapping the statement at line 1.

PM characterizes whether the parent nodes of a pair of mapped statements are also mapped. We observe that statements with mapped parent nodes are more likely to be mapped. For a pair of mapped statements, we check if mapping one of the statements to another statement with mapped parent nodes can achieve the same NIT. For instance, in Fig. 5(c), IJM maps the statements at lines 1 and 2 with mapped parent nodes, while GT maps the statements at lines 1 and 3 with parent nodes not mapped. We determine that IJM is more accurate than GT in mapping the statement at line 1. Furthermore, we notice a special type of statements, i.e., blocks. A block is a group of statements between balanced braces (i.e., “{” and “}”). We observe that a block should be mapped along with its parent nodes, e.g., the “{” following the method testFilterSet in Fig. 5(c) should be mapped along with the method declaration. Thus, mapped blocks with unmapped parent nodes are determined to be inaccurate.

TYPE characterizes whether mapped tokens have the same type. For a token whose directly relevant node is not a name node, we define the type of the token as the label of its directly relevant node. For tokens whose directly relevant node is a name node, we define four types: variable name, type name, method name and declaration name. Following Frick et al. [12], we consider the mapping of tokens with different types as inaccurate. For instance, in Fig. 6(a), GT maps a variable name value to a method name bytevalue, we determine that such a mapping is inaccurate.

STMT characterizes whether mapped tokens belong to a pair of mapped statements. Two tokens from mapped statements are more likely to be mapped. We observe that mapping tokens from mapped statements is better than (1) not mapping the tokens and (2) mapping tokens from unmapped statements. For instance, in Fig. 6(b), the two value tokens are both variable names and they belong to a pair of mapped statements. GT maps the two tokens, while IJM does not map them. We determine that GT is more accurate than IJM in mapping the two tokens. As another example, we find that both GT and IJM map the statement at line 1 to the statement at line 2 in Fig. 6(c). GT maps the two HashMap tokens in unmapped statements, while IJM maps the HashMap to the Map from the mapped statements. Using the STMT measure, we determine that IJM is more accurate in mapping the HashMap at line 1 than GT.

VAL characterizes whether mapped tokens have the same string value. Two identical tokens in a pair of mapped statements are more likely to be mapped. We consider that mapping such two tokens is better than mapping one of the tokens to another token with different values between the two statements. For instance, in Fig. 6(d), GT maps getBytes to writeBytes, while IJM maps the two getBytes tokens. Using the VAL measure, we determine that IJM is more accurate in mapping the getBytes tokens than GT.

LLCS is defined as the length of the longest common subsequence (LCS) [16] that is calculated using the mapped tokens between mapped statements. We observe that the order of tokens is infrequently changed in a statement. We use LLCS to quantify the number of tokens that are sequentially mapped between the mapped statements. For instance, in Fig. 6(e), GT changes the orders of the two Filterable tokens in the statement at line 1. As a result, at most three tokens are sequentially mapped between the statements, i.e., Filterable, = and runner. The LLCS for the mapped tokens is calculated as three. IJM sequentially maps the five tokens between the two statements. The LLCS for the mapped tokens is calculated as five. Using the LLCS measure, we determine that IJM is more accurate in mapping the Filterable tokens than GT.

Table II shows the number of statements that are categorized along the measures. The measures can identify 157 (85%), 208 (86%) and 178 (86%) of the statements with inaccurate mappings for GT, MTD and IJM, respectively. The other statements with inaccurate mappings are categorized into the Other category. For these statements, we find that determining the accuracy of the mappings of statements and tokens requires more comprehension of the changes.

We randomly divide the 200 statements into four groups with each group having 50 statements. We also divide the experts into four groups with each group having three experts. We invite the four groups of experts to analyze the four groups of statements, respectively. For each statement, we provide the mappings of the statement and its tokens as generated by each of the studied algorithms. Notice that we do not provide the algorithm that generates the mappings. We let the experts determine if the mapping of the statement or a token of the statement is inaccurate. For each group of statements, we calculate Fleiss’ Kappa [10] to estimate the agreement of the three experts’ determination results.

For each studied algorithm, we have three determination results on the accuracy of algorithm in mapping each statement and its tokens. For each statement and the generated mappings of the statement and its tokens by an algorithm, we label the mappings as inaccurate if at least two experts determine that inaccurate mappings exist.

Then, we run our approach to determine statements with inaccurate mappings for GT, MTD and IJM from the 200 statements. Finally, we compare the determination results of our approach with the experts’ determination results. We define a true positive as a statement with inaccurate mappings for an algorithm that is determined as such by both our approach and experts. We define a false positive as a statement with inaccurate mappings for an algorithm that is determined as such by our approach but not determined as such by experts. We define a false negative as a statement with inaccurate mappings for an algorithm that is determined as such by experts but not determined as such by our approach. Let us denote the number of true positives, false positives and false negatives as TP, FP and FN. We calculate the precision of our approach as $\frac{TP}{TP+FP}$. And we calculate the recall of our approach as $\frac{TP}{TP+FN}$.

Table III presents the TP, FP, FN, precision and recall of our approach in determining statements with inaccurate mappings for the studied algorithms. As shown in the table, our approach achieves a precision of 0.98–1.00 and a recall of 0.65–0.75. Almost all of the statements with inaccurate mappings as determined by our approach are also determined as such by experts.

For the false positives and false negatives, we further asked the experts why they considered that an algorithm inaccurately maps a statement or tokens of the statement. We analyze cases of false positives and false negatives. For the two false positives, we find that GT and IJM generate the accurate mappings for a statement and its tokens but our approach determines the mapping of a token as inaccurate. We show this case in Fig. 7. As shown in Fig. 7, the code involves a refactoring that extracts the method invocation messageReference.getRegionDestination in the statement at line 1 as a new variable. GT and IJM accurately map the invocation to the statement at line 2, while MTD maps messageReference in the statement at line 1 to the regionDestination in the statement at line 3. In this case, mapping tokens from unmapped statements is better than mapping tokens from mapped statements. However, when comparing the generated mappings by GT, IJM and MTD, our approach considers that MTD generates a better mapping than GT and IJM. This case indicates that our approach can be further improved by considering refactoring changes.

For 11 cases of false negatives, we find that our similarity measures can distinguish the accurate and inaccurate mappings of statements or tokens. However, all three algorithms generate inaccurate mappings. Hence, the inaccurate mappings cannot be detected by comparing the similarity measures of the mapped statements and tokens between different algorithms. We observe 38 cases where an algorithm maps two tokens from unmapped statements and another algorithm separately maps the two tokens to empty elements. We observe 33 cases where an algorithm maps two statements and another algorithm separately maps the two statements to empty elements. We further observe 7 cases where two algorithms map a statement or token to different statements or tokens but our similarity measures cannot distinguish accurate and inaccurate mappings. In these 78 cases, determining the inaccurate algorithm requires more syntactic information to determine if mapping two tokens or two statements helps understand the changes.

As described in Section V-F, two algorithms may generate the same mapping that is inaccurate. Such an inaccurate mapping cannot be detected by comparing the two algorithms. If another algorithm generates the accurate mapping, comparing the third algorithm with the former two algorithms may reveal the inaccurate mapping. Thus, comparing an algorithm with multiple algorithms can detect more inaccurate mappings.

The primary threats to the validity of our experiments are twofold. First, we compare the determination results of our approach and experts on the accuracy of generated mappings by the studied algorithms for 200 statements. The number of analyzed statements is not very large-scale. This is because such a manual analysis is time-consuming, with understanding mappings of each statement and each token. On average, each expert takes 1.5 hours to analyze the allocated 50 statements. The 200 statements are randomly taken from 10 different projects, and they are from different file revisions. Dotzler et al. analyzed only 10 file revisions when evaluating MTD [8]. Our analysis involves much more file revisions than their analysis. Second, when we select the statements, we require that at least two studied algorithms inconsistently map the statement or its tokens. There may exist cases where the studied algorithms consistently map a statement and its tokens, but the mapping of the statement or a token of the statement is inaccurate. The selected statements do not consider such cases, and our approach cannot detect the inaccurate mapping in such cases. We manually analyzed 100 statements for which the studied algorithms generate consistent mappings at both statement and token levels. We did not observe the cases where the three algorithms produce inaccurate mappings. Nevertheless, our code and data are made publicly available [1], and researchers are encouraged to investigate this possibility.

From our experiments, we observe two limitations of our approach. First, as described in our answer to RQ1, refactoring changes may impact the precision of our approach. In refactoring changes, mapping tokens from unmapped statements may be better than mapping tokens from mapped statements. We note that researchers proposed several refactoring detection tools, e.g., [30]. Incorporating such tools into our approach may deal with this limitation. On the other hand, there still exists a considerable number of inaccurate mappings that cannot be detected by our approach. According to our answer to RQ2, comparing an algorithm with more algorithms may detect more inaccurate mappings as generated by the algorithm. Moreover, researchers have proposed various heuristics to map program elements [20]. Additional similarity measures can be derived from these heuristics. Such measures may further improve the recall of our approach. Our code and data are made publicly available [1], and researchers are encouraged to extend our approach.

Many AST mapping algorithms were proposed in prior studies. Yang proposed an AST mapping algorithm using a branch-and-bound implementation of the largest common subtree problem [33]. This algorithm does not consider moved AST nodes. Fluri et al. proposed ChangeDistiller, an AST mapping algorithm that uses a reduced AST, in which code statements are encoded as leaf nodes [11]. Hashimoto et al. proposed Diff/TS, an algorithm that works with raw ASTs and supports multiple languages [14]. Nguyen et al. proposed Jsync, which leverages a classic text-based mapping algorithm to map AST nodes [28]. Recently, researchers proposed GumTree [9], MTDiff [8] and IJM [12]. These algorithms are the state-of-the-art AST mapping algorithms and are analyzed in our paper. Different from them, we focus on evaluating AST mapping algorithms rather than proposing a new AST mapping algorithm.

AST mapping algorithms are widely used in several SE research areas. ChangeDistiller has been used to identify non-essential modifications [19] and automate repetitive edits [26]. Nguyen et al. used Jsync to track cloned code in the software evolution process [28]. Moreover, many studies used GumTree to analyze code patterns of changes such as bug-fixing changes [23, 29, 13, 5, 18, 21], logging changes [22] and changes to online code examples [34]. Also, prior work trained models based on the edit actions of changes that are calculated using GumTree [32, 31, 15, 24, 7]. Such models are used to recommend changes such as patches [32] and logging changes [22]. Different from them, we focus on evaluating AST mapping algorithms instead of using the algorithms to analyze changes.