Source-linked AI summary
A Syntax-Guided Edit Decoder for Neural Program Repair
Qihao Zhu, Zeyu Sun, Yuan-an Xiao, Wenjie Zhang, Kang Yuan, Yingfei Xiong, Lu Zhang
TL;DR
Standard DL-based APR decoders struggle with syntactic correctness, efficient small-edit representation, and project-specific identifiers. Recoder addresses these gaps with syntax-guided edit decoding, a provider/decider architecture, and placeholder generation. It repairs 53 Defects4J v1.2 bugs and 19 additional Defects4J v2.0 bugs, with results indicating better generalizability than existing approaches.
Problem
Standard DL-based APR decoders generate replacement statements token by token, causing syntactic, small-edit representation, and project-specific identifier limitations.
Method
Recoder uses a syntax-guided edit decoder with provider/decider architecture and generates placeholders later instantiated as feasible project-specific identifiers.
Results
Recoder correctly repairs 53 bugs on Defects4J v1.2 and 19 additional bugs on Defects4J v2.0, outperforming the cited state-of-the-art APR approaches.
Takeaways & Limitations
Recoder is the first DL-based APR approach reported to outperform traditional APR techniques on Defects4J v1.2 and shows better generalizability than some state-of-the-art approaches.
Takeaways & Limitations
The evaluation implements and assesses Recoder only on Java, and its generalization to different datasets remains unknown.
Abstract
from arXiv · showhide
Automated Program Repair (APR) helps improve the efficiency of software development and maintenance. Recent APR techniques use deep learning, particularly the encoder-decoder architecture, to generate patches. Though existing DL-based APR approaches have proposed different encoder architectures, the decoder remains to be the standard one, which generates a sequence of tokens one by one to replace the faulty statement. This decoder has multiple limitations: 1) allowing to generate syntactically incorrect programs, 2) inefficiently representing small edits, and 3) not being able to generate project-specific identifiers. In this paper, we propose Recoder, a syntax-guided edit decoder with placeholder generation. Recoder is novel in multiple aspects: 1) Recoder generates edits rather than modified code, allowing efficient representation of small edits; 2) Recoder is syntax-guided, with the novel provider/decider architecture to ensure the syntactic correctness of the patched program and accurate generation; 3) Recoder generates placeholders that could be instantiated as project-specific identifiers later. We conduct experiments to evaluate Recoder on 395 bugs from Defects4J v1.2 and 420 additional bugs from Defects4J v2.0. Our results show that Recoder repairs 53 bugs on Defects4J v1.2, which achieves 21.4% improvement over the previous state-of-the-art approach for single-hunk bugs (TBar). Importantly, to our knowledge, Recoder is the first DL-based APR approach that has outperformed the traditional APR approaches on this dataset. Furthermore, Recoder also repairs 19 bugs on the additional bugs from Defects4J v2.0, which is 137.5% more than TBar (8 bugs) and 850% more than SimFix (2 bugs). This result suggests that Recoder has better generalizability than existing APR approaches.
1 INTRODUCTION
Recoder addresses three limitations of standard DL-based APR decoders by generating syntax-guided edits and project-specific identifier placeholders. Its provider/decider architecture supports accurate, syntactically correct patch generation, and experiments show improved repair performance and generalizability across benchmarks.
- Limitations of Existing Decoders: Standard DL-based APR decoders generate replacement statements token by token, which can include syntactically incorrect programs and enlarge the patch space.The approach also struggles to represent small edits efficiently and to generate identifiers specific to the repaired project.
- Limitations of Existing Decoders: A one-token change in Closure-14 is represented as a 13-token sequence, yielding a program space of roughly n^13 when n is the number of tokens.This illustrates why regenerating an entire statement is inefficient for small edits.
- Limitations of Existing Decoders: Existing DL-based APR approaches may exclude patches requiring project-specific identifiers, such as the method name “availableLocaleSet” in Lang-57.Such identifiers are unlikely to appear in the training set, preventing existing approaches from generating patches like this.
- Recoder: Recoder generates edits rather than complete replacement statements and uses syntax-guided decoding with a provider/decider architecture.Providers offer expansion choices and probabilities, while the decider estimates which provider to use.
- Recoder: Recoder generates placeholders for project-specific identifiers and instantiates them with feasible identifiers when applying edits.Feasibility is constrained by programming-language requirements such as the type system.
- Evaluation: Recoder correctly repairs 53 of 395 Defects4J v1.2 bugs and 19 additional Defects4J v2.0 bugs, outperforming the cited single-hunk APR baselines.The evaluation also covers IntroClassJava and QuixBugs, where Recoder repairs 35 and 17 bugs respectively.
2 EDITS
Recoder represents repairs as syntax-guided edits rather than regenerated statements, using providers and a decider to constrain choices and support copying, subtree replacement, and placeholders.
- Edit syntax: Recoder defines edits as a sequence of insert or modify operations terminated by end.Insert adds a statement before the faulty statement, while modify replaces an AST subtree.
- Edit syntax: Modify replaces a subtree while preserving its root non-terminal symbol, ensuring syntactic correctness.The replacement target is identified by its root node’s preorder-traversal ID.
- Copy operations: Copy operations reuse AST subtrees from the faulty statement or surrounding method when the copied root symbol matches the expanded symbol.This mechanism reduces the patch space for edits that are partly copied from the original program.
- Placeholders: Placeholders let the neural network defer project-specific identifier generation until edit application, when feasible identifiers are instantiated.Feasibility is filtered using programming-language constraints and local accessibility.
- Correctness: Theorem 2.1 states that edited programs are syntactically correct.The proof relies on host-language insertion requirements, unchanged modification roots, and grammar-based or root-compatible copied subtrees.
- Provider/decider architecture: Providers supply choices for grammar expansion, subtree copying, and subtree location, while the decider assigns provider probabilities and disables inapplicable providers.The three providers are the rule predictor, tree copier, and subtree locator.
3 MODEL ARCHITECTURE
Recoder adapts TreeGen into a syntax-guided architecture that reads faulty code and partial edits, then predicts expansions for edit generation.
- Architecture: Recoder replaces TreeGen’s natural-language encoder and program decoder because its inputs are faulty code and context and its output is an edit sequence.The architecture retains TreeGen-derived AST and tree-path readers while introducing a code reader and edit decoder.
- Architecture: At each generation step, the model predicts probabilities for expanding a non-terminal, and beam search selects combinations forming complete edits.The architecture comprises code, AST, and tree-path readers plus an edit decoder.
- Code reader: The code reader encodes the faulty statement and its surrounding method using AST traversal, tag embeddings, and an AST-based graph.Its sub-layers use self-attention, gating, and a graph neural network.
- Self-attention: Self-attention captures long dependencies in the AST traversal sequence, while multi-head attention extracts nonlinear features.The heads are combined through a fully connected layer.
- Structural encoding: The gating layer integrates self-attention outputs with tag embeddings, and the graph layer incorporates neighboring AST-node information.These representations provide structural features for later readers and the decoder.
3.2 AST Reader
The AST reader encodes the partially generated edit AST, while the associated code-reader representation is integrated through attention and gating.
- AST Reader: The AST reader encodes the partial generated AST of the edit using the same structure as TreeGen.The code-reader representation is processed with self-attention and combined through a gating layer before further attention and tree convolution.
3.3 Tree Path Reader
The tree path reader represents the expansion target as a root-to-node path, and the edit decoder combines this context with code and partial-AST information to score provider choices.
- Tree Path Reader: The tree path reader represents the non-terminal to expand as a path from the AST root and transforms its nodes into vectors.Attention layers and fully connected layers extract features for the edit decoder.
- Edit Decoder: The edit decoder receives vectors encoding the faulty statement, surrounding method, partial generated AST, and target tree path.These vectors describe all available inputs when expanding a non-terminal.
- Providers: The rule predictor estimates probabilities for grammar production rules and masks rules whose left-hand sides do not match the current non-terminal.Masked rules receive zero probability after softmax normalization.
- Providers: The tree copier scores compatible AST subtrees from the surrounding method, while the subtree locator scores replaceable subtrees in the faulty statement.The subtree locator considers faulty-statement subtrees larger than one node.
- Decider: The decider estimates provider probabilities and masks providers that are not responsible for the current non-terminal.For Modify, rule predictor and tree copier probabilities are reset to zero.
3.5 Training and Inference
Recoder trains on oracle edit sequences and generates syntactically valid edits through recursive grammar expansion and beam search. Placeholder combinations are constrained, and generated candidates are validated against compilation and tests.
- Training: During training, Recoder maximizes the negative log-likelihood of oracle edit sequences without provider and decider logic components.The logic components are omitted during training so the model learns distributions for rules handled by them.
- Inference: Inference recursively expands start into Edits until every predicted AST leaf is terminal, using beam search with size 100.This produces multiple candidate edits rather than a single output.
- Inference: Patches containing more than one placeholder are discarded during beam search because combinations of multiple placeholders can be large.A single placeholder has relatively few choices, but their combinations increase search complexity.
- Patch generation: For each suspicious statement, Recoder generates 100 valid patch candidates and continues until the candidate quota is reached.Fault localization determines which statements receive patch generation.
- Validation: The test suite filters generated patches that fail compilation or any test case, and validation continues until a plausible patch is found.A plausible patch is one that passes all test cases.
4 EXPERIMENT SETUP
The evaluation measures Recoder on four Java APR benchmarks, under both unknown and provided fault locations, against traditional and learning-based baselines. Its training data contains 103,585 filtered single-statement or single-insertion patches, and experiments use a five-hour limit.
- Benchmarks: Recoder is implemented for Java and evaluated across Defects4J v1.2, Defects4J v2.0, QuixBugs, and IntroClassJava.The benchmarks contain 395, 420, 40, and 297 bugs respectively, with 18 Gson bugs excluded from Defects4J v2.0.
- Research questions: The evaluation asks about Recoder’s performance, component contributions, and generalizability across additional APR benchmarks.The generalizability study includes Defects4J v2.0, QuixBugs, and IntroClassJava.
- Dataset: 103,585 valid patches remained after filtering 1,083,185 GitHub commits for supported edit types and data leakage, then splitting them 80% for training and 20% for validation.Supported patches modify one statement or insert one statement; projects and methods overlapping Defects4J were removed.
- Evaluation settings: Fault localization is evaluated both with unknown locations using Ochiai and with the actual faulty location supplied.The second setting isolates patch-generation capability from fault-localization effects.
- Baselines: Recoder is compared with ten traditional single-hunk APR approaches and learning-based baselines, including TBar and SimFix.The baseline set reflects Recoder’s restriction to single-hunk patches.
- Correctness assessment: Patch correctness is manually checked independently by two authors, requiring agreement, with a kappa score of 0.98.Patches are judged correct when identical or semantically equivalent to the Defects4J patch.
- Implementation: Recoder uses embedding size 256, hidden sizes following TreeGen, dropout rate 0.1, and a five-hour running-time limit.The encoder and decoder stacks contain 5, 9, and 2 blocks for the code reader, AST reader, and decoder respectively.
5 EXPERIMENTAL RESULTS
Recoder outperforms existing single-hunk APR approaches on Defects4J v1.2, remains strongest with perfect fault localization, and repairs complementary bugs. It also retains an advantage on Defects4J v2.0, QuixBugs, and IntroClassJava, while ablations show its components matter.
- Performance: 51 bugs were correctly repaired without perfect fault localization, 21.4% (9 bugs) more than TBar, making Recoder the first DL-based approach to outperform traditional APR on this setting.The comparison uses Defects4J v1.2 and existing single-hunk APR techniques.
- Performance: With the actual faulty location provided, Recoder still outperforms existing APR approaches, and performance improves 35.3% over Recoder using Ochiai.The result indicates better performance with better fault localization techniques.
- Complementarity: Recoder fixes 19 bugs unique against TBar, SimFix, and DLFix, with 34, 28, and 27 unique bugs against SimFix, TBar, and DLFix respectively.The overlap analysis supports complementarity with the three existing approaches.
- Ablation: Removing modify, copy, insert, or placeholder generation causes a significant performance drop in the Defects4J v1.2 ablation.The ablation was conducted under the Ochiai fault-localization scenario.
- Generalizability: 19 bugs were repaired on Defects4J v2.0, representing 137.5% (11 bugs) more than TBar and 850.0% (17 bugs) more than SimFix.All three approaches repair a smaller proportion of bugs on this additional benchmark.
- Generalizability: Recoder repaired 775% (31 bugs) more bugs on IntroClassJava and 30.8% (4 bugs) more on QuixBugs than the baselines.These results further confirm the reported effectiveness and generalizability of Recoder.
6 DISCUSSION
Training-data size affects Recoder’s loss and diversity, while the approach remains subject to common APR requirements and distribution-shift limitations from deep learning.
- Training-data adequacy: As the training subset grows, both loss and diversity decrease in Recoder’s sensitivity analysis.The analysis trains five models with different random seeds for each subset size and evaluates loss on Defects4J v1.2 single-hunk bugs.
- Limitations: Recoder requires bugs to be reproducible by failing tests and effective fault localization to identify the faulty statement.These constraints are shared with most APR approaches.
- Limitations: Recoder’s performance can degrade when training and testing sets have different distributions.This limitation is shared with DL-based approaches.
7 RELATED WORK
Prior APR work applies heuristics, semantic analysis, repair patterns, source-code learning, and deep learning, while Recoder extends syntax-guided generation to program edits. Its approach differs from earlier edit-generation methods by combining syntax guidance with provider/decider architecture and placeholder generation.
- APR research spans heuristic search, semantic analysis, mined repair patterns, and learning from source code.
- Deep-learning APR commonly treats repair as statistical machine translation, generating fixed code from faulty code with sequence-to-sequence models and copy mechanisms.
- Recoder is the first work in this line to improve the decoder through syntax-guided edit generation, provider/decider architecture, and placeholder generation.
- Recoder significantly extends TreeGen to generate edit sequences for program repair.
- Earlier program-edit approaches generate token, node, subtree, or graph edits, but are not syntax-guided and treat edit scripts as token sequences.
8 THREATS TO VALIDITY
The main validity concerns involve the evaluation setting and manual patch assessment. Although Recoder was tested on several benchmarks, its performance beyond Java and the evaluated datasets remains uncertain.
- Evaluation was implemented and conducted only on Java, leaving performance on other programming languages for future study.
- Generalization to datasets beyond Defects4J v2.0, QuixBugs, and IntroClassJava remains unknown.
- Manual patch-correctness assessment was independently performed by two authors, and patches were deemed correct only when both agreed.
9 CONCLUSION
The paper proposes Recoder, a syntax-guided edit decoder with placeholder generation for automated program repair. It reports improved repair performance and generalizability relative to existing approaches.
- Recoder combines syntax-guided edit decoding with placeholder generation for automated program repair.
- 21.4% improvement (9 bugs) over the existing state-of-the-art APR approach was achieved for single-hunk bugs on Defects4J v1.2.
- Evaluation on three other benchmarks shows better generalizability than some state-of-the-art APR approaches.