Delta Debugging Framework Roadmap

(Back to Delta Debugging Framework)

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.
Test Framework
Test Framework	We ideally need a way to allow users to specify the test(s) to be run easily without them having to modify the delta debugging module.	Richard Chu	Framework completed. Based on my simplistic understanding of the design of the JUnit Framework. Except, no SetUp() or TearDown() capabilities.
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.

Other Information

Other Tasks

These tasks may require being done in every version or may only have to be done only once.

Task	Description	Assigned to	Status
Source Documentation and Licensing
Source Documentation	Unsurprisingly, the source code is not thoroughly documented. Before the end of this semester, by the time the project is due to be submitted, the source code needs to be well documented.	Liz Chak	There is some documentation in the source files but not much. And it's not well documented.
Source License	As per the requirements, the delta debugging framework will be licensed under an open source license. Which one? we don't know yet. Though, before the due date of the project, we must select one and change the source files header comments as per the selected license's requirements.	Richard Chu, Aditya Nanda Kuswanto, Dean William Woodside	Done. Decided to release the source code under the GPL Version 2 license.

Prerequisites to Testing

Task	Description	Assigned to	Status
Obtaination of Testcase 01	We need a program that we could use to test the delta debugging framework. Ideally this program will be small but contain multiple source files. We need two versions of the program: a pristine working copy, and a version that has a regression. Need to know how to build the program.	Aditya Nanda Kuswanto	Done. HelloWorld program has been created using the test modules ripped from Tinderbox. The test checks whether the program runs successfully by checking the log file it produces. The test has been uploaded to: svn://cdot.senecac.on.ca/deltatest
Obtaination of Testcase 02	We need a program that we could use to test the delta debugging framework. Ideally this program will be small but contain multiple source files. We need two versions of the program: a pristine working copy, and a version that has a regression. Need to know how to build the program.	Richard Chu	Done. Going to use a C++ program I wrote in a course in a previous semester to test out the delta debugging framework. The test has been uploaded to: svn://cdot.senecac.on.ca/deltatest
Creation of Test Case(s)	We need test case(s) for the test program that can return whether or not the test passes or fails so that we can test the delta debugger.	Richard Chu	Done. The test case is real simple. It just tests the return code of a function with the expected return code. returns true/test passed if return code is equal to the expected return code.
Creation of the necessary hooks into the framework	The framework must be able to automatically build the test program and run the test case(s). So need to create the necessary hooks between the framework and test program.	Richard Chu	Done. Made real simple because of Build tree and Test framework.
Description of the test cases	The current test case is quite complex. A document is needed to introduce users on how to create test cases and utilize the algorithm.	Aditya Nanda Kuswanto	Done. The document and links to the testcases are located here.
Prerequisites to testing of SVN version of delta debugging framework
Obtaination of test SVN Repository	We have an SVN repository that holds our delta debugging framework source files. We need another SVN repository that we could use to test our framework.	Dean Woodside	Done. The URL to the test SVN repository is: svn://cdot.senecac.on.ca/deltatest
Prerequisites to testing of CVS version of delta debugging framework
Obtaination of test CVS Repository	When the CVS version of the framework is completed, it will be useful to have a test CVS repository that we could use to test our framework.	Dean Woodside	The CVS repository has been created. The URL is hera.senecac.on.ca:43900/deltatest. The web interface to the repository is: here
Creation / Extraction of Test Case(s)	In the future, we would like to test our delta debugging framework on the Mozilla source tree. So it would be nice to find test cases that can test some functionality of the source code.	Aditya Nanda Kuswanto	Done. Ripped some preliminary test modules from Tinderbox. Test modules are currently used to test the HelloWorld testcase. The same modules can be used to test the success of future Mozilla build by testing the presence of Firefox executable.

Legend

Roadmap Status Legend
Task completed	Task started but not complete	Task not started