Fine-grained and accurate source code differencing
By Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, Monperrus Martin. 2014
615 citations recorded by the source corpus.
At the heart of software evolution is a sequence of edit actions, called an edit script, made to a source code file. Since software systems are stored version by version, the edit script has to be computed from these versions, which is known as a complex task. Existing approaches usually compute edit scripts at the text granularity with only add line and delete line actions. However, inferring syntactic changes from such an edit script is hard. Since moving code is a frequent action performed when editing code, it should also be taken into account. In this paper, we tackle these issues by introducing an algorithm computing edit scripts at the abstract syntax tree granularity including move actions. Our objective is to compute edit scripts that are short and close to the original developer intent. Our algorithm is implemented in a freely-available and extensible tool that has been intensively validated.
Subfields: Information Systems, Software, Program Analysis & Verification, Signal Processing
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Information Systems
- Miltiadis Allamanis
- Charles Sutton
- Eran Yahav
- Uri Alon
- Tien Nhut Nguyen
- Baishakhi Ray
- Michele Tufano
- Gabriele Bavota
In Software
- Charles Sutton
- Miltiadis Allamanis
- Alexey Svyatkovskiy
- Neel Sundaresan
- Tien Nhut Nguyen
- Michele Tufano
- Eran Yahav
- Baishakhi Ray
In Program Analysis & Verification
- Eran Yahav
- Uri Alon
- Shaked Brody
- Charles Sutton
- Miltiadis Allamanis
- Gabriele Bavota
- Nan Duan
- Daya Guo
In Signal Processing
- Eran Yahav
- Uri Alon
- Charles Sutton
- Miltiadis Allamanis
- Baishakhi Ray
- Saikat Chakraborty
- Shaked Brody
- Ge Li
Citations in the corpus
- CodeXGLUE: A Machine Learning Benchmark Dataset for Code Understanding and Generation (2021, methodology): “To achieve this, they employ the GumTree Spoon AST Diff tool [17].”
- An Empirical Study on Learning Bug-Fixing Patches in the Wild via Neural Machine Translation (2018, methodology): “From these commits, we extract method-level AST edit operations using fine-grained source code differencing [16].”
- Learning to Fix Build Errors with Graph2Diff Neural Networks (2019, methodology): “changing a single file. To enable the use of ASTs, we also discard broken code that cannot be parsed, not counting these cases in the results for this paper. We use the GumTree code differencing tool [14] to compute the difference between the broken AST and the fixed AST. We convert the tree differe”
- Getafix: learning to fix bugs automatically (2019, methodology): “To extract edits from a given pair of ASTs, Getafix builds on the GumTree algorithm [Falleri et al. 2014], a tree-based technique to compute fine-grained edit steps that lead from one AST to another.”
- DeepDelta: learning to repair compilation errors (2019, methodology): “Finding the shortest edit action is NP-hard; therefore, heuristics are used to compute a short transformation from asts to astt deterministically [13].”
- Deep Just-In-Time Inconsistency Detection Between Comments and Source Code (2020, methodology): “We use GumTree (Falleri et al. 2014), to compute AST node edits between T old (corresponding to M old ) and T , identifying inserted, deleted, kept, replaced, and moved nodes.”
- On Learning Meaningful Code Changes Via Neural Machine Translation (2019, methodology): “In the first step, we rely on GumTreeDiff [38] to establish the file-to-file mapping, performed using semantic anchors, between pre-and post-PR files and disregarding any file added/removed during the code review process.”
- History Driven Program Repair (2016, methodology): “To this end, we use GumTree,4 an off-the-shelf, state-of-theart tree differencing tool that computes AST-level program modifications [15].”
- Graph-Based Mining of In-the-Wild, Fine-Grained, Semantic Code Change Patterns (2019, methodology): “Second, we conducted a comparative study to evaluate our tool against the syntax-based technique used in the existing approaches [7], [9], [22], [23], [25].”
- CODIT: Code Editing With Tree-Based Neural Models (2018, methodology): “Using GumTree, a tree-based code differencing tool [42], it identifies the edited AST nodes.”
- Shaping program repair space with existing patches and similar code (2018, methodology): “GumTree [9] improves ChangeDistiller by removing the assumption that leaf nodes contains a significant amount of text.”
- TBar: revisiting template-based automated program repair (2019, methodology): “[24] mined fix patterns at the AST level from patches by using code change differentiating tool [14].”
- Neural Edit Completion (2020, methodology): “GumTree [Falleri et al. 2014] breaks the mapping stage into three steps.”
- A Novel Neural Source Code Representation Based on Abstract Syntax Tree (2019, methodology): “Some studies directly use ASTs in token-based methods for source code search [37], program repair [38] and source code differencing [39].”
- When Old Facts Return: Re-Reads, Reverts, and the Limits of Temporal Memory (2026, unknown): “Fine-grained source differencing can identify syntactic changes (Fluri et al., 2007; Falleri et al., 2014); contract-oriented representations can describe selected interface changes (Meyer, 1992).”