Source-linked AI summary
Do the Fix Ingredients Already Exist? An Empirical Inquiry into the Redundancy Assumptions of Program Repair Approaches
Matias Martinez, Westley Weimer, Martin Monperrus
TL;DR
Program-repair research has extensively evaluated patch-finding performance, but less work has examined the techniques’ underlying assumptions. This paper formalizes temporal redundancy and measures it in software histories, finding that many commits reuse previously existing code and supporting redundancy-based repair approaches.
Problem
Although repair techniques have been extensively evaluated, less work has examined or validated their foundational assumptions about whether existing code can supply fixes.
Source: §1 · p. 1Method
Results
Takeaways & Limitations
For line-level repairs, searches can focus on a single file, reducing search space without substantially reducing repair success potential.
Source: §1 · p. 1The study leaves measurement on bug-fix commits and granularities beyond lines and tokens, such as AST elements, for future work.
Source: §6 · p. 4
Abstract
from arXiv · showhide
Much initial research on automatic program repair has focused on experimental results to probe their potential to find patches and reduce development effort. Relatively less effort has been put into understanding the hows and whys of such approaches. For example, a critical assumption of the GenProg technique is that certain bugs can be fixed by copying and re-arranging existing code. In other words, GenProg assumes that the fix ingredients already exist elsewhere in the code. In this paper, we formalize these assumptions around the concept of ''temporal redundancy''. A temporally redundant commit is only composed of what has already existed in previous commits. Our experiments show that a large proportion of commits that add existing code are temporally redundant. This validates the fundamental redundancy assumption of GenProg.
1. INTRODUCTION
Program-repair techniques rely on assumptions about where fixes come from, but their foundational assumptions have received less scrutiny than their bug-fixing performance. This paper formalizes and measures temporal redundancy, finding substantial reuse and identifying repair-search choices with practical consequences.
1. INTRODUCTION
- GenProg assumes large programs contain repair seeds, while four of PAR’s ten templates also rely on redundancy.The shared premise is that rearranging existing statements can fix bugs.Source: §1 · p. 1
- Despite extensive evaluations of repair performance and cost, less work has examined or validated the techniques’ fundamental assumptions.Source: §1 · p. 1
- The paper defines temporal redundancy as a commit composed only of code rearranged from material present in earlier commits.It analyzes existing code by granularity, such as lines or tokens, and locality, such as the same file or anywhere in the program.Source: §1 · p. 1
- 31–52% of commits were temporally redundant at token level across six open-source Java applications.The authors describe this as evidence that a substantial fraction of software evolution occurs without creating new material.Source: §1 · p. 1
- How code is selected from elsewhere changes the search space’s size and potential for success; local line-level repair could reduce repair time without similar loss of success potential.Source: §1 · p. 1
2. SOFTWARE TEMPORAL REDUNDANCY
The paper defines temporal redundancy for source-code changes by checking whether added fragments have appeared earlier in a program’s history. It distinguishes historical reuse from current-state redundancy and considers both fragment granularity and scope.
2. SOFTWARE TEMPORAL REDUNDANCY
- Fragments are source-code substrings measured at line or token granularity, and commits are analyzed as source-code additions and deletions.An update is treated as a deletion plus an addition; changes to non-source artifacts are excluded.Source: §2 · p. 2
- Snapshot redundancy checks whether a fragment exists elsewhere in the program now; temporal redundancy also incorporates software history.Snapshot redundancy was studied by Gabel and Su and used by GenProg.Source: §2 · p. 2
- Temporal redundancy counts a fragment as reusable if it appeared at any earlier time, even if it was later removed and then reused.The first program version is treated as insertions into an empty initial program.Source: §2 · p. 2
- A commit is temporally redundant when every added fragment has appeared in an earlier commit; it introduces no new fragments.The paper treats added fragments as the commit’s “ingredients.”Source: §2 · p. 2
- Global redundancy ignores where a fragment previously appeared, whereas local redundancy requires its prior use in the same file.A fragment present in another file can be globally, but not locally, redundant.Source: §2 · p. 2
3. MEASURING REDUNDANCY
The authors measure temporal redundancy by processing version histories at a chosen granularity and scope, then calculating the fraction of acceptable commits that are redundant. Their dataset comprises six open-source Java projects, filtered from 16,071 commits to 7,076 acceptable commits.
3. MEASURING REDUNDANCY
- The protocol retrieves commits, keeps executable-code changes, splits files into fragments, and uses Myers differencing to identify additions.Source: §3 · p. 2
- Whitespace and comments are removed, and fragments are indexed in temporal order at the selected scope before redundancy is measured.Source: §3 · p. 2
- Temporal redundancy is the fraction of acceptable commits that are redundant, where acceptable commits add at least one fragment after filtering.Source: §3 · p. 2
- The dataset contains six open-source Java projects; filtering 16,071 commits yielded 7,076 acceptable commits.The projects include Apache Log4j, JUnit, Picocontainer, Apache Commons Collections, Apache Commons Math, and Apache Commons Lang.Source: §3 · pp. 2–3
4. EMPIRICAL RESULTS
Across the studied projects, token-level temporal redundancy exceeds line-level redundancy, and local-scope reuse remains substantial. The results expose trade-offs among how many commits can be synthesized and the size of the repair search space.
4.1 Line-Level Temporal Redundancy
- At line level, 3–17% of accepted commits are temporally redundant, though the reasons for variation across projects are unclear.Different project commit conventions are one possible explanation, and deeper analysis is left for future work.Source: §4.1 · p. 3
4.2 Token-Level Temporal Redundancy
- The token-level result follows because line-redundant commits are also token-redundant, while new lines may consist entirely of existing tokens.Source: §4.2 · p. 3
- At token level, 29–52% of commits are temporally redundant, exceeding line-level redundancy in every project.The authors say this agrees with their analytical argument and supports the experiment’s construct validity.Source: §4.2 · p. 3
- For 29–52% of accepted commits, token-level repair or synthesis need not invent a new token, implying a smaller search space.The paper illustrates this with arithmetic code recombined from existing literals and operations.Source: §4.2 · p. 3
- The repair search space comprises a pool of fragments and the space of their combinations; the pool counts fragments seen up to a point in time.The experiment measures the fragment pool separately at each granularity.Source: §4.2 · p. 3
- For every application studied, the token pool at the final commit is much smaller than the line pool.For log4j, the reported pools contain 14,294 tokens and 43,313 lines.Source: §4.2 · p. 3
- Line pools enable synthesis of fewer commits (about 10%) with smaller combination spaces, while token pools enable about 40% at the cost of larger spaces.Source: §4.2 · pp. 3–4
4.3 Redundancy Scope Experiment
- At line level, local redundancy ranges from 2% to 16%, and more than half of redundant commits have local reuse; local pools can seed a similar order of magnitude of commits with a smaller search space.For log4j, the median local line pool is 57 lines versus 43,313 globally; token reuse is also substantial within the same file.Source: §4.3 · p. 4
5. RELATED WORK
Related work studies redundancy spatially, across code clones, or as repetition in changes, whereas this paper measures whether commits contain previously existing code. Its commit-level focus treats rearranged combinations of fragments as distinct from clones and preserves actual code values.
5. RELATED WORK
- Code-clone work studies line- and token-level redundancy or links clones across versions, while this paper asks whether changes contain existing code.A commit of redundant fragments need not itself be a clone because fragments may come from unrelated locations or be rearranged.Source: §5 · p. 4
- Earlier work examined repair-space topology and navigation; this paper instead relates commits to the repair space.Source: §5 · p. 4
- Spatial redundancy measures concern code uniqueness or repetitiveness, whereas temporal redundancy tracks reuse across program history and cannot be inferred from those experiments.Source: §5 · p. 4
- Nguyen et al. abstracted over commits and literals to measure change repetitiveness, while this study measures real commit-level code, including actual literal values.Source: §5 · p. 4
6. CONCLUSION
The paper defines software temporal redundancy and measures its presence in source code. It reports that searches for line-level repairs can focus on one file, while identifying bug-fix commits and additional granularities as future work.
6. CONCLUSION
- As many as 52% of commits are composed entirely of previously existing tokens.Source: §6 · p. 4
- For line-level repairs, searches can focus on one file, reducing the search space without substantially reducing repair success potential.Source: §6 · p. 4
- Future work will measure temporal redundancy on bug-fix commits and study granularities beyond lines and tokens, such as AST elements.Source: §6 · p. 4