[http://en.wikipedia.org/wiki/Delta_Debugging Delta debugging] is an automated approach to debugging that isolates failures systematically. Given a failing test that can be mechanically verified (including a browser crash), [http://en.wikipedia.org/wiki/Delta_Debugging delta debugging] is a way of automatically isolating the change that introduced the failure. Having  For developers, the occurrence of a scenario similar to this happens all too often: a developer codes a piece of functionality that works. Then, over a period of time, multiple changes to the program source files are made and that piece of functionality stops working. The cause of the regression could be any of the changes that were made since the time the functionality was last known to work. To isolate the cause of the regression, the developer begins the debugging process. Generally, debugging is a manual process where the developer must walk through the code while trying to keep track of variables and function calls. Sure, there are debuggers that can help you keep track of variables, the call stack, watch certain blocks of code, and execute the code step by step, however debugging is still mainly a manual process. Written in perl, given# that the source code is located in an SVN repository (support for CVS in the future)# a test case that can automatically verify whether or not a piece of functionality of a program works or not# a way to automatically build the program from the source code (if needed)the delta debugging framework aims to automatically isolate the failure-inducing changes to the source code that caused a regression. == Project License == Written in place perl, given a test case that can automatically verify whether or<br />not a piece of functionality of a program works or not, the delta debugging<br />framework aims to pull builds from CVSautomatically isolate the failure-inducing changes to the<br />source code that caused a regression.<br /><br />Copyright (C) 2006 Richard Chu, Aditya Nanda Kuswanto, bisect Dean William Woodside<br /><br />This program is free software; you can redistribute it and/or modify it under<br />the terms of the GNU General Public License as published by date and change set the Free Software<br />Foundation; either version 2 of the License, or (using at your option) any later<br />version.<br /><br />This program is distributed in the hope that it will be useful, but WITHOUT<br />ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS<br />FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.<br /><br />You should have received a copy of the GNU General Public License along with<br />this program; if not, write to the Free Software Foundation, Inc., 59 Temple<br />Place, Suite 330, Boston, MA 02111-1307 USA<br /><br />[http://enwww.wikipediaopensource.org/wikilicenses/Bonsai_CVS_code_management_system bonsai ] data gpl-- remember, CVS doesn't have changesets!license.php The GNU General Public License (GPL)Version 2, and report results would let computers make developers more productiveJune 1991]<br /><br />Contact Information about the authors of the delta debugging framework can be found<br />on our individual profile pages.

== Project Facts and Assumptions Principles ==

 == Project Source Repository Test Cases == The test cases used in this project are located in the [[Delta_debugging_testcases|Delta Debugging Testcases page]]. == Project Roadmap == ([[#top|&uarr; top]]) [[Delta Debugging Framework Roadmap|Delta Debugging Framework Roadmap]] The 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. == Partial Class Diagram ==

Assuming you have [http://subversion.tigrisMost of the classes in blue exist in the source repository.org/ SVN], the projectThe classes in pale yellow are classes that won's source can t be obtained via SVN using completed in the following commandfirst release.  [[Image:Dd_partialclassdiagram2.PNG]]

== Project Task List News ==

<tr> <td>Retrieval of Change / Change set</td> <td>The Granularity concept. A single revision may consist of hundreds or thousands of lines I finally had some time to do a second round of code that were changed, yet only a couple lines testing & debugging of the change may be responsible for the regressiondelta debugging framework. Thus, There must be a method And guess what? It ''seems'' to break the change into smaller manageable chunkswork now. The different types problem? Combination of chunks we may breaking up a changeset are: Revision, Directories, Files, Code Blocks, logical errors when applying and Lines.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td> <table style="width: 100%;" class="standard-table" border="0" cellspacing="0" cellpadding="0"> <tr><td bgcolor="#00FF00">Currently can retrieve change sets of type Revision, Directory, unapplying changes in the framework and Filea bad test case. NOT going to complete retrieval of Code Block, Line of Code change setGo figure.</td></tr> <tr><td bgcolor="#FFFF00">Requires more thorough test suite (ChangesetTest.pl needs more test cases)</td></tr> </table> </td> </tr>

<tr> <td>Application However, before I get ahead of Change / Change set</td> <td>OKmyself and officially tag and release the delta debugging framework as version 0.1, I would like to test it out on another test program. Change sets Hopefully, this can be retrieveddone this weekend. Now what? You must And if all goes well, version 0.1 will be able to apply a change or change set or subset officially released before the end of a change set to the source tree. Your mission is to figure out how to do thatyear.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td>

<tr> <td>Unapplication of Change / Change set</td> <td>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.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#FFFF00"> <table style="width: 100%;" class="standard-table" border="0" cellspacing="0" cellpaddingDec. 13, 2006 ="0"> <tr><td bgcolor="#00FF00">Can unapply a changeset (specified by array of indices passed in) for a Revision, Directory, and File Changeset. NOT going to complete unapplication of Code Block or Line changeset.</td></tr> <tr><td bgcolor="#FFFF00">UNTESTED.</td></tr> </table>

Created [[Delta_debugging_testcases|Delta Debugging Testcases]] page to discuss the nature of the test cases created to test the algorithm. Included in the page are 2 testcases created so far, the '''HelloWorld''' binary test and the '''Sudoku''' test. Both tests can be found in the '''deltatest''' svn repository. The repository can be checked out using this command:<pre> svn checkout svn://cdot.senecac.on.ca/td> deltatest </trpre>

<tr> <td colspan="4"><strong>GNU Make<Unfortunately, we haven't had the time to test the delta debugger much since Dec. 09, 2006 because of exams, other school work; Planning to spend some time this weekend to test the delta debugger and figure out why it currently seems to not be able find the minimal set of failure inducing directories/strong> files ([http://www.gnu.org/software/make/ http://wwwwhether its because of unreliable test case or logical error in the program).gnu.org/software/make/]) </td> </tr>

<tr> <td>Wrapper around A roadmap of our vision of the GNU make utility</td> <td>Mozilla uses direction of the GNU make utility to build their source tree. your mission is to make a wrapper around the GNU make utility so that project will be heading in the make command can future will be programmatically called to build the source tree.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td> <table style="width: 100%;" class="standard-table" border="0" cellspacing="0" cellpadding="0"> <tr><td bgcolor="#00FF00">Wrapper created: ''makewrapper.pl''. Can execute the make command with options specified by the user.</td></tr> <tr><td bgcolor="#FFFF00">Requires more thorough test case (''maketest.pl'' needs more test cases)and posted soon.</td></tr> </table> </td> </tr>

<tr> <td>Wrapper around the necessary SVN commands</td> <td>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.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td> <table style="width: 100%;" class="standard-table" border="0" cellspacingDec. 11, 2006 ="0" cellpadding="0"> <tr><td bgcolor="#00FF00">Wrapper created: ''svn.pl''. Currently has subroutines for ''commit'', ''update'', ''diff'', and ''checkout'' commands. May need to wrap other SVN commands.</td></tr> <tr><td bgcolor="#FFFF00">Requires more thorough test case (''svntest.pl'' needs more test cases).</td></tr> </table> </td> </tr>

<tr> <td>Query SVN repository Uploaded testcase for differences between two revisions</td> <td>Your mission is to find out '''HelloWorld''' binary at '''deltatest svn'''. The test simulates the relevant commands error that can return may occur when compilation fails due to syntax error. The exalted HelloWorld program is located on the differences between two revisionsHelloWorld directory, while the meta-data that test definition is kept with each revision, how differences between two revisions are stored at HelloTestCase1.pm. The algorithm detects failed test and formatted, and how this data can be parsed into a usable form for our project (wrapper?).</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Donereverts the affected file to the version where the test passes.</td> </tr>

<tr> <td colspan="4"><strong>CVS/Mozilla Bonsai</strong> ([http://www.mozilla.org/bonsai.html http://www.mozilla.org/bonsai== Dec.html]10, [http://cvsbook.red-bean.com/OSDevWithCVS_3E.pdf CVS Book])<br />In my mind, Bonsai may be too bloated for our needs. </td> </tr>2006 ===

<tr> <td>Wrapper around Where is the necessary CVS commands</td>Bonsai work heading? Here is a breakdown of the past 3-4 weeks: <td>For * Initially was going for a straight wrapper around CVS ala the automated debugging style Richard used for SVN.* Tried to find some functionality within Bonsai that could make it easier.* Talked to workReed Loden, we he set up a repository for us to try with. Thanks Reed!* Thought that there may need to automatically modify be some additional (read: unpublished) tools that could be worked with. Got in contact with some of the "Project Participants" listed on [http://www.mozilla.org/projects/bonsai/]. Was told the working copy by reverting to person in particular wasn't a contributor (just submitted a different revision or updating certain directories and filesbug report). It may also need They in turn pointed me to know the differences between revisions and changesets[irc://irc.mozilla.<org/td>#mozwebtools #mozwebtools]. <td>* Lurked on [[Userirc:dwwoodsi|Dean Woodside//irc.mozilla.org/#mozwebtools #mozwebtools]]</td>for a few weeks. Talked to 'justdave' about Bonsai. Reed Loden chimed up and informed me that Bonsai can output to XML using ?xml=1 on the query (score! thanks again). <td bgcolor="#FF0000">Just starting * Researched some PERL parsing utilities. Trying outXML::LibXML for DOM-style parsing.</td> </tr>* Hopefully wrap something up by Wednesday. Failing that, might just go with simple CVS wrapper of some sort.

<tr> <td>Creation / Extraction of Test Case(s)</td> <td>We need test cases that can return whether or not the test passes or fails=== Dec. Tinderbox has a couple of tests that are executed after the source is built. Extract those tests from the Tinderbox source code so that we can use them in this project. We also need a test case that can pass/fail consistently so that we can test the delta debugger.</td> <td>[[User:Ankuswan|Aditya Nanda Kuswanto]]</td> <td bgcolor09, 2006 ==="#FFFF00">Work in progress. Found the tests! Now need to figure out how to run them and how they work.</td> </tr>

<tr> <td>Test Framework</td>What has been done since last week? <td>We ideally need * Got a way to allow users to specify the test(s) program and uploaded it to be run easily without them having to modify the delta debugging modulesvn://cdot.senecac.on. <ca/td> <td>TBDdeltatest. The pristine working version is revision 4. The latest committed copy is revision 8.</td> <td bgcolor="#FFA500">There are differences The regressive code was committed somewhere in opinion on how this should be donebetween.</td> </tr>* Started testing the delta debugging framework.

<tr> <td colspan="4"><strong>Implementation of Delta Debugging Algorithm</strong> ([http://www.infosun.fmi.uni-passau.de/st/papers/tr-99-01/ Yesterday, my program worked. Today, it does not. Why?])<br /> </td> </tr> <tr> <td>The Algorithm</td> <td>The delta debugging algorithm. Drives the framework to retrieve change sets, apply changes, build source tree, run test case(s) to find '''Finding the minimal revision 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.</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#FFFF00">Work in progress.</td> </tr></table>last known good revision'''

== Points Indeterminate. There is only 1 directory in the source repository so that directory should be returned as the minimal failure inducing set of Confusion ==directories. Does it return it? yes and no.

[[Bonsai issue]] However, if I force the test case to return the expected result, then the delta debugger correctly returns the directory as the failure-- '''unresolved'''inducing one.

[[Image:Dd_partialclassdiagramBased on the testing, it seems to be able to cycle through every combination of changes in the changeset, apply the combination of changes, build the source code, and run the test case. The test case just seems to not report the correct test results.PNG]]

The RCS tree is straight forward=== Dec. It will encapsulate the data and operations related to the revision control system. SVN wraps the operations of the SVN revision control system03, CVS will wrap the operations of the CVS revision control system, etc.2006 ===

Committed some updated to the SVN repository.* The Build tree test framework. There are a couple of files to the framework: Test.pl, TestCase.pl, TestSuite.pl, TestResult.pl, TestRunner.pl. It is straight forwardloosely based off of the design of the JUnit framework. Why such an elaborate design just for the need of users to define the test case that can determine whether or not a piece of functionality works or not to be run? For a few reasons that I may be adamant about:# To use the delta debugging framework, the user should not have to touch the DeltaDebugger.pl file to define the tests and how to run them. It wraps Using the testing framework, this can be done by subclassing the TestCase.pl class and overriding the run() subroutine.# For the delta debugger to work, it needs to know whether the test case passes or fails. Using the test framework, I hope to control the possible return codes of the tests to either pass or fail only.* testtest.pl that tests the functionality of the build tool used test framework.* updates to DeltaDebugger.pl to build make use of the source treetest framework.

RCS's can remember the changes (deltas) Crunch time. One week left. The high priority tasks that occurred in previous versions still need to be done:# Acquisition of a fileprogram we could use to test the delta debugging framework. See [[#How_to_Get_Involved|How To Get Involved]] for more info.# Test, debug the history of changes that occur between revisions, etcdelta debugging framework.

A Change and its subclasses encapsulate the idea of a single change=== Nov. A change can be a change made within a directory26, change made within a file, change made to block of code, or a change to a line.2006 ===

A ChangesetFactory is supposed Committed some updates to return a change set based on the type of change set requestedSVN repository.* Updated the delta debugging algorithm module. To get I didn't realize this yesterday but the requested change set, one needs algorithm to know find the type minimal set of revision control system failure inducing files (and code block and line of code changes if those changeset types ever gets dones) is the same (SVN, CVS, other, etc.with minor modifications) and/or as the algorithm that can find the data required to connect minimal set of failure inducing directories. Thus I generalized that algorithm to remove the directory changeset specific code so that itwill work with all other types of changesets. So there obviously need a link between RCS and ChangesetFactory/Changeset. The question is how? What is * Removed the properdebugging/best way to link them together? One way is to pass in an RCS object to test related code from the ChangesetFactory which would then pass that object source files.CVS Repository Setup (thanks to the appropriate Changeset subclass[[user:reed|Reed Loden!]]): '''hera.senecac.on. I donca/deltatest''t like that solution but it's *[http://hera.senecac.on.ca:43080/viewvc.cgi/?root=deltatest ViewVC Web Repository Browser]*If you want commit access for whatever reason, email one of the simplest.project members

Also'''Milestone:'''* Even though the test framework is incomplete, I think we can go ahead and begin the initial testing of the method to get delta debugger on a change set for SVN may be different from CVSreal regressive program as I think we are ready. So there may be a Changeset hierarchy for SVN and another one for CVS. I don't like Coincidentally, exactly 2 months after the idea of that at allfirst project news posting on Sept. There must be another way26, 2006.

* Applying a change I haven't posted an update in a changeset. Should the Changeset subclasses be able to do that? Are they the information expert? They know about the changeswhile so here goes. Should they know how to apply them? How would we go abouts applying a subset of changes in a changeset? For example, there may have What's been changes in 10 different directories, how would we apply the changes from say 4 of the 10 directories and not the othersdone since then?* Connecting all 3 hierarchies together. Need to be able to connect to SVN, need to be able to get and apply changes, need to be able to build the source tree. * The actual delta debugging algorithm.

But Committed some updates to the SVN repository.* Modified the Changeset hierarchy of classes. Added a getChange() subroutine that's all for takes an index and retrieves the change from the changeset. Also modified the getChangeset() subroutine to optionally take an array of directories/files to limit the search scope to within the directories/files passed in. These changes are possibly dangerously untested.* Committed the DeltaDebugger.pl file. This file houses the actual delta debugging algorithm. It requires three user-defined pieces of information: a Build object, an RCS object, and the automated test cases. Currently, it can theoretically find the failure inducing revision, and the minimal failure inducing set of directories. * Committed a DeltaDebuggerTest.pl file. It just tests the correctivity of the theoretical.  In the works:* Continue working on the delta debugging algorithm. Need to be able to find the minimal failure inducing set of files.* Test framework. Allow users to plug in test cases/suites without touching the futureDeltaDebugger.pl module.

([[The deadline for a version 0.01 release is looming. 1-2 weeks left to get this done. What needs to be done to accomplish this?* Finish everything that is in the works real soon.* Need a test program that we could use and upload to our test SVN repository to test the delta debugging framework. Ideally, the test program will meet the following requirements:#top|&uarr; top]])Has source files that span multiple directories wide and deep yet be small enough that the delta debugging can be done in a short amount of time so that all aspects of the delta debugger can be tested.# Has a regression. Or can easily be modified so that some functionality will stop working.# Has an automated test case that tests the regressive functionality.* Put theory into practice. So far the delta debugging algorithm has not been tested on a real program. The correctness of the algorithm has only been confirmed in theory. We need to test the algorithm in a production environment real soon.

 *<strike>Found a suitable crash case thanks to the people of [irc://irc.mozilla.org#qa #qa] (in particular, asqueella and Aleksej). For full details on the bug, see [https://bugzilla.mozilla.org/show_bug.cgi?id=354300 Bug #354300].</strike> *Talked to Reed Loden on IRC. He will be setting up a CVS repository for us something this coming week (Tuesday at earliest).