Source-linked AI summary
CODIT: Code Editing with Tree-Based Neural Models
Saikat Chakraborty, Yangruibo Ding, Miltiadis Allamanis, Baishakhi Ray
TL;DR
Repetitive code edits often reuse existing code, but prior automation has relied on limited templates or domain-specific knowledge. CODIT models edits with tree-based structural translation followed by token generation. Its evaluation reports stronger patch-suggestion accuracy than the stated baselines and bug-fix suggestions on Defects4J.
Problem
Code edits are conditioned on the previous version and include structural changes, so token-sequence modeling alone does not provide a syntax-aware model of edits.
Source: §1 · p. 1Method
CODIT predicts AST structural changes with a tree-to-tree model, then generates tokens conditioned on the resulting structure and token types.
Source: §1 · p. 1Results
15.94% patch suggestion accuracy in the top 5 suggestions outperforms Copy-Seq2Seq by 63.34% and Tree2Seq by 44.37%.
Source: §1 · p. 2Takeaways & Limitations
The authors conclude that tree-based models can outperform popular seq2seq alternatives and that CODIT can predict bug fixes.
Source: §11 · p. 12CODIT cannot generate new identifiers unless they are in its vocabulary or the input code.
Source: §8 · p. 11
Abstract
from arXiv · showhide
The way developers edit day-to-day code tends to be repetitive, often using existing code elements. Many researchers have tried to automate repetitive code changes by learning from specific change templates which are applied to limited scope. The advancement of deep neural networks and the availability of vast open-source evolutionary data opens up the possibility of automatically learning those templates from the wild. However, deep neural network based modeling for code changes and code in general introduces some specific problems that needs specific attention from research community. For instance, compared to natural language, source code vocabulary can be significantly larger. Further, good changes in code do not break its syntactic structure. Thus, deploying state-of-the-art neural network models without adapting the methods to the source code domain yields sub-optimal results. To this end, we propose a novel tree-based neural network system to model source code changes and learn code change patterns from the wild. Specifically, we propose a tree-based neural machine translation model to learn the probability distribution of changes in code. We realize our model with a change suggestion engine, CODIT, and train the model with more than 24k real-world changes and evaluate it on 5k patches. Our evaluation shows the effectiveness of CODITin learning and suggesting patches. CODIT can also learn specific bug fix pattern from bug fixing patches and can fix 25 bugs out of 80 bugs in Defects4J.
1 INTRODUCTION
Repetitive code edits often reuse existing code elements, yet automating them has relied on limited templates or domain-specific knowledge. CODIT models edits with a tree-based structural stage and a token-generation stage, and is evaluated on real-world patches and bug-fixing tasks.
1 INTRODUCTION
- Automating repetitive edits can reduce the burden of manually applying changes that are tedious and error-prone.Prior work reports that code elements used in edits are often drawn from the existing codebase.Source: §1 · p. 1
- Prior automation either relies on predefined templates or requires domain-specific knowledge, motivating learning general edits from code histories.The paper investigates whether machine-learning models can capture the repetitiveness and statistical characteristics of daily code edits.Source: §1 · p. 1
- CODIT first predicts AST structural changes, then generates tokens conditioned on the generated structure and valid token types.The token stage also respects scope information.Source: §1 · p. 1
- CODIT targets small code fragments and was prototyped for methods in popular Java projects on GitHub.The authors report collecting 32,473 patches from 48 open-source GitHub projects.Source: §1 · p. 2
- 15.94% patch suggestion accuracy in the top 5 suggestions outperforms Copy-Seq2Seq by 63.34% and Tree2Seq by 44.37%.On Pull-Request-Data, CODIT suggests 28.87% of correct patches in the top 5, outperforming Copy-Seq2Seq by 9.26% and Tree2Seq by 22.92%; it also suggests 15 complete and 10 partial fixes among 80 Defects4J bugs.Source: §1 · p. 2
2 BACKGROUND
The background frames code editing as predicting a new version conditioned on the previous version. It introduces grammar-based representations and neural translation models, including attention and copying mechanisms used in this work.
Modeling Code Changes
- NMT models represent code edits as a conditional distribution over the target version given the previous code version.The passage also describes code generation as modeling p(c|κ), with the previous version serving as context.Source: §2 · p. 2
Grammar-based modeling
- A CFG describes language syntax with production rules, while a PCFG associates probabilities with those rules.The background also describes expanding non-terminals to generate a sentence.Source: §2 · p. 2
Neural Machine Translation Models
- Seq2seq encodes input tokens and decodes an output sequence; attention searches the input and copying can transfer its elements to the target.The paper employs both attention and copying.Source: §2 · p. 2
3 MOTIVATING EXAMPLE
The motivating example illustrates CODIT editing a code fragment through changes to its parse tree. A tree translator generates structure first, and a token generator then supplies concrete tokens conditioned on that structure.
3 MOTIVATING EXAMPLE
- CODIT replaces an edited subtree with a new subtree, with deleted and added subtrees shown separately in the example.The depicted edit changes `return super.equals(object)` to `return object == this`.Source: §3 · pp. 2–3
- The example separates structural translation from token generation, with token probabilities conditioned on terminal types.The figure caption identifies the rule sequence and token-generation stages.Source: §3 · pp. 2–3
- The tree translator encodes the previous parse tree and sequentially selects grammar rules to generate the new tree.Tree generation begins at the root and expands the bottom-most, left-most non-terminal at each step.Source: §3 · p. 3
- The token generator predicts concrete tokens for terminal node types produced by the tree translator.It selects from the vocabulary or copies input tokens, while restricting outputs to tokens valid for each predicted type.Source: §3 · p. 3
4 TREE-BASED NEURAL TRANSLATION MODEL
CODIT models a code edit by first predicting the edited syntax tree, then generating concrete code conditioned on that tree and the previous code. Its tree model generates grammar-rule expansions, while its token model produces tokens constrained by type and context.
4 TREE-BASED NEURAL TRANSLATION MODEL
- CODIT factors edit generation into predicting the edited tree and then concretizing code conditioned on that tree and the previous code.The model targets the probability of the new code given the previous version.Source: §4 · p. 3
4.1 Tree Translation Model (Mtree)
- Mtree predicts syntax trees through grammar-rule expansions, producing syntactically correct trees whose rule probabilities depend on the input tree and prior expansions.It generates the tree by applying CFG rules at non-terminal nodes.Source: §4.1 · p. 3
- The Mtree encoder represents the previous tree as a sequence of grammar rules and summarizes the rules processed so far in its hidden state.The decoder uses the encoder output to generate the next version’s rule sequence.Source: §4.1 · p. 3
4.2 Token Generation Model (Mtoken)
- Mtoken generates tokens conditioned on the previous code, earlier generated tokens, and the token type supplied by Mtree.Its decoder produces a token distribution, while grammar- and scope-based masks rule out invalid candidates; an <unknown> name can be replaced by the most-attended source token.Source: §4.2 · p. 4
5 IMPLEMENTATION
CODIT preprocesses method-level patches into bounded parse-tree edit pairs, trains separate tree and token models, and combines their beam-search outputs into ranked code suggestions.
5 IMPLEMENTATION
- CODIT is implemented as a change-recommendation tool that learns from patches and predicts likely edits for an input code fragment.The implementation extends OpenNMT using PyTorch.Source: §5 · p. 4
- CODIT represents each patch as a pair of parse trees for the original and edited method, selecting a minimal subtree that captures the edits and adding connecting context.Changes in comments and literals are excluded, and patches exceeding the maximum change or tree size are discarded.Source: §5 · p. 4
- CODIT extracts grammar rules, tokens, and token types from the parse trees, then trains Mtree and Mtoken separately with cross-entropy objectives.Training uses top-1 suggestion accuracy for validation and early stopping.Source: §5 · pp. 4–5
- At test time, CODIT uses beam search to generate tree-rule sequences, discards infeasible sequences, and generates concrete code for each resulting tree.It ranks the generated fragments by their joint tree-and-code probability and returns the top K suggestions.Source: §5 · p. 5
6 EXPERIMENTAL DESIGN
The experimental design evaluates CODIT on code changes, pull-request edits, and bug repair using exact-patch accuracy and test-passing fixes. It compares against sequence, tree-encoding, copy-context, clone-based, and program-repair baselines.
6 EXPERIMENTAL DESIGN
- CODIT is evaluated on three tasks: code changes from open-source projects, merged pull-request edits, and Defects4J bug repair.The collected code-change data yielded 32,473 patches after filtering and deduplication; the pull-request task yielded 5,546 examples, and the bug-repair task covered 117 patches across 80 bugs.Source: §6 · p. 5
6.1 Evaluation Metric
- For code changes, correctness requires an exact match to the developer’s patch in the top K; for bug repair, a fix must pass all test cases.Exact patch matching is stricter than semantic equivalence, and bug-fix patches are manually checked for similarity to developer patches.Source: §6.1 · p. 5
6.2 Baseline
- Baselines include vanilla attention-based Seq2Seq, identifier-abstraction translation, SequenceR-style copy attention, and tree encoders based on SBT or AST paths.The tree-encoder baselines use DeepCom- and Code2Seq-like representations, respectively.Source: §6.2 · pp. 5–6
- The tested Graph2Seq implementation did not scale to the needed vocabulary, while the modified model failed to converge after three days and made zero correct predictions.The authors report testing on a machine with four Nvidia TitanX GPUs and 256 GB RAM.Source: §6.2 · p. 6
- The comparison also includes code-clone-based edit recommendation for code changes, and SequenceR plus non-NMT repair systems for bug fixing.The clone baseline retrieves similar previous code fragments and suggests their corresponding edited versions.Source: §6.2 · p. 6
7 RESULTS
CODIT generates concrete code patches across code-change and pull-request datasets, and its evaluation also examines component choices, generalization, and bug repair. Results highlight both the value of separating structure from token prediction and limits involving cross-project variation and multi-hunk bugs.
RQ2: Design choices
- CODIT has two potential failure points: an incorrect tree from Mtree prevents Mtoken from producing the correct patch, a proposed explanation for top-1 performance.The authors frame the explanation for top-1 performance as a conjecture.Source: §7 · p. 6
RQ1: Concrete edits
- CODIT generates 820 (15.94%) top-5 patches on Code-Change-Data and 177 (28.87%) on Pull-Request-Data.Table 2 reports concrete-patch performance across model families.Source: §7 · p. 6, Table 2 · p. 7
RQ1: Patch patterns
- Most correctly generated patches have tree distance 1, though CODIT also generates larger edits and examples include long-distance renaming and context-varying exception substitutions.The paper also illustrates abstract-method conversion, where the method body is removed, and other structural transformations.Source: Figure 2 · p. 6, §7 · p. 7
RQ2: Component evaluation
- With true structure known, Mtoken reaches 39.57% and 61.66% top-5 accuracy; Mtree predicts 56.78% and 55.79% of structural changes.On a filtered dataset containing only patches with structural changes, Mtree predicts 33.61% and 30.73% of edited structures.Source: §7 · pp. 7–8, Table 5 · p. 8, Table 6 · p. 8
RQ2: Design choices
- CODIT performs best at Ktree = 2 with Ktoken = 5; increasing max tree size or max change size reduces performance.At Ktree = 2, it generates 10 candidates and selects the top 5; larger trees are still predicted comparably well, with reported accuracy above 30 nodes of 21.97% on Pull-Request-Data and 16.48% on Code-Change-Data.Source: Figure 3 · p. 8, §7 · p. 9, Figure 4 · p. 9
RQ2: Cross-project generalization
- Cross-project evaluation leaves Mtree performance similar to intra-project evaluation, but full CODIT performance deteriorates by 68%, which the authors attribute mainly to differing token names.The results suggest structural change patterns are more ubiquitous across projects than token changes.Source: Table 9 · p. 9, §7 · p. 9
RQ3: Scope
- The bug-repair evaluation assumes bug locations are known, and the current prototype handles multi-hunk bugs as separate inputs without modeling their interaction.The authors leave evaluation as a full-fledged repair tool for future work.Source: §7 · p. 10
RQ3: Bug fixing
- CODIT generates complete bug-fix patches for 15 Defects4J bugs and partial patches for 10; among 51 potential patches, 30 are identical to developer-provided patches and come from 25 bug ids.Source: §7 · p. 10
8 THREATS TO VALIDITY
The validity discussion identifies dataset representativeness as an external-validity assumption and notes internal evaluation limits. The authors mitigate the former with diverse real-world patches, while exact-match scoring makes reported performance a lower bound.
External Validity
- The external-validity claim assumes the training dataset represents real code changes.To mitigate this threat, the authors collected patches across repositories and types of real-world edits.Source: §8 · p. 11
Internal Validity
- Exact-match evaluation misses semantically equivalent but syntactically different patches, so CODIT’s reported performance is a lower bound.The authors also tuned hyperparameters on validation data and probed the implementation for unintended bugs.Source: §8 · p. 11
- Hyperparameters may affect CODIT’s performance, so the authors tuned them on validation data and probed for implementation bugs.Source: §8 · p. 11
9 RELATED WORK
Related work spans source-code modeling, structured representations, program repair, and automatic code edits. CODIT is positioned as a tree-based model that learns general edit patterns from historical changes rather than relying on predefined templates or similar examples.
Modeling source code and machine translation
- CODIT models code edits with a syntactic, tree-based approach, unlike prior work on generic code modeling or source-language translation.The section contrasts edit modeling with both source-code prediction and machine translation between programming languages.Source: §9 · p. 11
Structure Based Modeling of Code
- CODIT’s Mtree models derivation-rule sequences with a probabilistic context-free grammar, distinct from pTSG idiom mining, and graph-based code modeling [78], [59].Source: §9 · p. 11
Program Repair
- CODIT learns transformation patterns probabilistically, unlike program-repair tools based on predefined patterns or mined patterns used to guide mutation,,.The section distinguishes learning a model that generalizes from limited data from mining patterns alone.Source: §9 · p. 11
Automatic Code Changes
- CODIT learns general code edits from historical changes without requiring similar edit examples or contexts, unlike prior pattern- and context-driven tools,,,.It also differs from domain-specific approaches by targeting general code changes.Source: §9 · pp. 11–12
10 DISCUSSION AND FUTURE WORK
The discussion describes ways CODIT narrows code-generation search, notes that one model may miss bug-fixing patterns, and identifies larger edits as future work.
Search Space for Code Generation
- 3.18 · 10^10 effective actions remain in CODIT’s probabilistic-grammar search space, enabling more efficient code search.The passage contrasts this with a grammar-allowed AST space of 1.81 · 10^35 and says CODIT’s space is significantly lower than previous methods.Source: §10 · p. 12
Ensemble Learning for Program Repair
- A single pre-trained model may miss bug-fixing patterns because fixes vary with bug context and type; ensemble learning is proposed for future work.The passage notes that model performance can also vary with architecture and hyperparameters, even on the same training corpus.Source: §10 · p. 12
Larger Code Edits
- CODIT focuses on small edits, while its tree translation and node-type candidates may help generate larger edits that remain future work to investigate.The paper describes larger changes as harder for current automated repair techniques and plans to study CODIT on multi-line and multi-hunk edits.Source: §10 · p. 12
11 CONCLUSION
The conclusion presents CODIT as a tree-based hierarchical model for suggesting source-code changes and reports promising patch-generation and bug-fixing results.
11 CONCLUSION
- CODIT is a tree-based hierarchical model designed to suggest source-code changes resembling patterns observed in the wild.The paper evaluates it against a large number of real-world patches.Source: §11 · p. 12
- The evaluation reports that tree-based models can outperform popular seq2seq alternatives in generating code patches.The conclusion characterizes tree-based models as a promising tool for patch generation.Source: §11 · p. 12
- Program-repair experiments show that CODIT is capable of predicting bug fixes.Source: §11 · p. 12