Delta Debugging Framework Roadmap

Introduction

This page outlines our current vision of the delta debugging framework and a roadmap of the work that needs to be completed to accomplish our vision. This roadmap may be subject to change and/or expanded as our vision expands through feedback and requests from others, our own ideas, etc.

NOTE 1: We are currently on the road to version 0.1

Version 0.1

Vision, Objectives, & Goals

In the beginning, when we began working on the delta debugging framework project, we had big ideas, big plans, and big visions on what the delta debugging framework would be able to do by the time version 0.1 would be release.

We had visions of developing a framework that:

1. is easy to use and just works (tm) for the user with minimal set up.
2. works with CVS and SVN revision control systems.
3. is able to find the minimal set of lines of code that caused a regression.
4. has an efficient algorithm.

Unfortunately, due to our lack of knowledge about delta debugging in the beginning, time constraints, understimation of project requirements and complexity, and our optimistic belief that our code is correct and will just work (tm), everything that we planned to accomplish for version 0.1 was not completed. Therefore, we are now splitting up our vision of features and functionality and work that we hope to accomplish across subsequent versions of the framework.

For version 0.1, we plan to complete the following features, functionality, & work:

1. The delta debugging algorithm: Drives the framework to retrieve changesets, apply a combination of changes, build the source code (if necessary), run user-defined test cases to determine whether or not a piece of the program works or not, and find the minimal set of failure-inducing changes.
2. SVN version: The framework will work with projects where the source is housed in SVN repositories.
3. SVN version File-level Granularity: For the projects housed in SVN repositories, the algorithm will be able to find the minimal set of failure-inducing files that caused the regression.

After version 0.1 is officially released, there may be new versions released under the version 0.1 branch (as 0.1.1, 0.1.2, 0.1.3, etc) that contain bug fixes and minor updates. However, no new features will be introduced within these minor updates.

Roadmap to Version 0.1

Task	Description	Assigned to	Status
SVN Changeset / Change
Retrieval of Change / Change set	The Granularity concept. A single revision may consist of hundreds or thousands of lines of code that were changed, yet only a couple lines of the change may be responsible for the regression. Thus, There must be a method to break the change into smaller manageable chunks. For this version, the different types of chunks we may break up a SVN changeset are: Revision, Directories, and Files.	Richard Chu	Done. Can retrieve change sets of type Revision, Directory, and File.
Application of Change / Change set	OK. Change sets can be retrieved. Now what? You must be able to apply a change or change set or subset of a change set to the source tree. Your mission is to figure out how to do that.	Richard Chu	Can apply a changeset (specified by array of indices passed in) for a Revision, Directory, and File changeset.
Unapplication of Change / Change set	Changesets obviously must be able to be applied. But changesets must also be able to be unapplied. Your mission is to figure out how to do that.	Richard Chu	Can unapply a changeset (specified by array of indices passed in) for a Revision, Directory, and File Changeset.
Wrappers Around Build Systems
Wrapper around the GNU make utility	Mozilla uses the GNU make utility to build their source tree. your mission is to make a wrapper around the GNU make utility so that the make command can be programmatically called to build the source tree.	Richard Chu	Wrapper created: makewrapper.pl. Can execute the make command with options specified by the user.
Subversion (SVN) Repository (http://subversion.tigris.org/, http://svnbook.red-bean.com/nightly/en/index.html)
Wrapper around the necessary SVN commands	For the automated debugging to work, we may need to automatically modify the working copy by reverting to a different revision or updating certain directories and files. It may also need to know the differences between revisions and changesets.	Richard Chu	Wrapper created: svn.pl. Currently has subroutines for commit, update, diff, and checkout commands. May need to wrap other SVN commands.
Query SVN repository for differences between two revisions	Your mission is to find out the relevant commands that can return the differences between two revisions, the meta-data that is kept with each revision, how differences between two revisions are stored and formatted, and how this data can be parsed into a usable form for our project (wrapper?).	Richard Chu	Done.
Implementation of Delta Debugging Algorithm (Yesterday, my program worked. Today, it does not. Why?)
The Algorithm	The delta debugging algorithm. Drives the framework to retrieve change sets, apply changes, build source tree, run test case(s) to find the minimal set of failure inducing changes. The intersection of all other parts of the framework to make them work together. Ideally, should be abstract enough for easy extensibility with little impact.	Richard Chu	Work in progress. Currently, it can theoretically find the failure inducing revision, and the minimal failure inducing set of directories, and the minimal failure inducing set files. It will also easily scale to find the minimal failure inducing set of code blocks and lines of code (when those changeset types get done) with only minor additions to one subroutine. Works in theory. Untested in practice.
Testing, Fixing, & Validation
Test the Correctness of the Framework	Perform a controlled test of the framework to determine whether or not it works. Fix any bugs found that prevented the framework from properly working. Re-run tests. Validate the correctness of the results to ensure that the framework outputs the correct minimal set of failure inducing revision, directories, and files.	Richard Chu	This is a work in progress. It is able to find the last known good revision. I am indeterminate on whether or not it can find the failure inducing directories and files.
Milestone
Version 0.1 is Feature Complete	All of the tasks listed in the Roadmap to Version 0.1 are completed.	---	This should only be marked green when All of the tasks listed in the Roadmap to Version 0.1 are completed.

Version 0.2

Vision, Objectives, & Goals

As version 0.1 was the initial release, our main objective was to build something that works and is scalable however with little regard for robustness, quality or performance. For version 0.2, we plan to increase the robustness of the current framework while also adding more features and functionality to it. While keeping in mind the issues and roadblocks we encountered in version 0.1, the theory of learning, and the possible negative effects to the usefulness of the framework if we stay cautious, here is the features, functionality, & work that we plan to complete for version 0.2:

1. CVS version: The framework will work with projects where the source is housed in CVS repositories.
2. CVS version File-level Granularity (more if possible): For the projects housed in CVS repositories, the algorithm will be able to find the minimal set of failure-inducing files that caused the regression.
3. Increase granularity of SVN version (if possible): For the projects housed in SVN repositories, we plan to increase the algorithms ability from currently being able to find the minimal set of failure-inducing files to being able to find the minimal set of failure-inducing set of blocks of code and/or lines of code.
4. Robustness: We plan to increase the robustness of the current framework so that it properly handles invalid input and unexpected data instead of what it currently does: nothing & exit the program.

For the CVS version of the framework, there is thoughts on interfacing with the Mozilla Bonsai tool. However, there is an inherent limitation to the potential usability of the framework to those project outside of the Mozilla context. That is, for projects that don't make use of Mozilla Bonsai, the CVS version may not work for them if we choose to interface with the Mozilla Bonsai tool to develop the CVS version.

After version 0.2 is officially released, there may be new versions released under the version 0.2 branch (as 0.2.1, 0.2.2, 0.2.3, etc) that contain bug fixes and minor updates. However, no new features will be introduced within these minor updates.

Roadmap to Version 0.2

Task	Description	Assigned to	Status
CVS/Mozilla Bonsai (http://www.mozilla.org/bonsai.html, CVS Book) In my mind, Bonsai may be too bloated for our needs and may limit the usability of the framework on projects outside of the Mozilla context.
Wrapper around the necessary CVS commands	For the automated debugging to work, we may need to automatically modify the working copy by reverting to a different revision or updating certain directories and files. It may also need to know the differences between revisions and changesets.	Dean Woodside	Just starting out.
Query CVS repository for differences between two revisions	Your mission is to find out the relevant commands that can return the differences between two revisions, the meta-data that is kept with each revision, how differences between two revisions are stored and formatted, and how this data can be parsed into a usable form for our project (wrapper?).	Dean Woodside	Just starting out.
CVS Changeset / Change
Retrieval of Change / Change set	The Granularity concept. A single revision may consist of hundreds or thousands of lines of code that were changed, yet only a couple lines of the change may be responsible for the regression. Thus, There must be a method to break the change into smaller manageable chunks. For this version, the different types of chunks we may break up a CVS changeset are: Revision, Directories, and Files.	Nobody.
Application of Change / Change set	OK. Change sets can be retrieved. Now what? You must be able to apply a change or change set or subset of a change set to the source tree. Your mission is to figure out how to do that.	Nobody.
Unapplication of Change / Change set	Changesets obviously must be able to be applied. But changesets must also be able to be unapplied. Your mission is to figure out how to do that.	Nobody.
Increase SVN version granularity
Block of Code level Granularity	For the SVN version of the framework, increase the granularity so that the algorithm can find the minimal set of failure inducing blocks of code.	Nobody.
Line of Code level Granularity	For the SVN version of the framework, increase the granularity so that the algorithm can find the minimal set of failure inducing lines of code.	Nobody.
Robustness
Improve Robustness of Framework	The current framework does minimal checking and validation of input and data passed into the subroutines. Thus, there is no code to handle invalid input in a sensible manner.	Nobody.
Testing, Fixing, & Validation
Test the Correctness of the Framework	Perform a controlled test of the framework to determine whether or not it works. Fix any bugs found that prevented the framework from properly working. Re-run tests. Validate the correctness of the results to ensure that the framework outputs the correct minimal set of changes.	Nobody
Milestone
Version 0.2 is Feature Complete	All of the tasks listed in the Roadmap to Version 0.2 are completed.	---	This should only be marked green when All of the tasks listed in the Roadmap to Version 0.2 are completed.

Version 0.3

Vision, Objectives, & Goals

While versions 0.1 and 0.2 focused mainly on increasing the potential usefulness of the framework via the additions of new features and functionality, this release will focus on increasing the potential usefulness through increases in performance, robustness, and efficiency. Therefore, the work that we plan to accomplish for version 0.3 is:

1. Robustness: We plan to continue to increase the robustness of the current framework so that it properly handles invalid input and unexpected data.
2. Improve delta debugging algorithm: Currently, the algorithm goes through the changesets in a linear manner. This is highly inefficient. To improve the performance of the framework, it should be implemented in a binary search manner.
3. Consistency & Efficiency: Audit the code and classes to see if there is any unnecessary storage of information that could be removed, any code that could be refactored to be made more efficient, make sure all related classes & subroutines work in a consistent manner.

After version 0.3 is officially released, there may be new versions released under the version 0.3 branch (as 0.3.1, 0.3.2, 0.3.3, etc) that contain bug fixes and minor updates. However, no new features will be introduced within these minor updates.

Roadmap to Version 0.3

Task	Description	Assigned to	Status
Improve Robustness of Framework	The current framework does minimal checking and validation of input and data passed into the subroutines. Thus, there is no code to handle invalid input in a sensible manner.	Nobody.
Improve Performance of Algorithm	The current delta debugging algorithm works in a linear manner. This is inherently slow as it must try all combinations. A better algorithm would utilize a binary search technique.	Nobody.
Efficiency & Consistency of Framework	Audit the code and classes to see if there is any unnecessary storage of information that could be removed, any code that could be refactored to be made more efficient, make sure all related classes & subroutines work in a consistent manner.	Nobody.
Testing, Fixing, & Validation
Test the Correctness of the Framework	Perform a controlled test of the framework to determine whether or not it works. Fix any bugs found that prevented the framework from properly working. Re-run tests. Validate the correctness of the results to ensure that the framework outputs the correct minimal set of changes.	Nobody
Milestone
Version 0.3 is Feature Complete	All of the tasks listed in the Roadmap to Version 0.3 are completed.	---	This should only be marked green when All of the tasks listed in the Roadmap to Version 0.3 are completed.