[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 ==

Assuming you have [http://subversion.tigris.org/ SVN[Delta Debugging Framework Roadmap|Delta Debugging Framework Roadmap]], the project's source can be obtained via SVN using the following command:

svn checkout svn: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//cdotor expanded as our vision expands through feedback and requests from others, our own ideas, etc.senecac.on.ca/deltadbg

== Project Task List Partial Class Diagram ==

<table style="width: 100%;" class="standard-table" border="1" cellpadding="2" cellspacing="0"> <tr><td colspan="4"><strong>Priority Legend</strong></td></tr> <tr style="color: #FFFFFF; font-weight: bold; text-align: center"> <td bgcolor="#8B00FF" style="width: 33%;">High Priority</td> <td bgcolor="#0000FF" style="width: 33%;">Medium Priority</td> <td bgcolor="#008080" style="width: 33%;">Low Priority</td> </tr></table><br /><table style="width: 100%;" class="standard-table" border="1" cellpadding="2" cellspacing="0"> <tr><td colspan="4"><strong>Status Legend</strong></td></tr> <tr style="font-weight: bold; text-align: center"> <td bgcolor="#00FF00" style="width: 33%;">Task Most of the classes in blue exist in the source repository. The classes in pale yellow are classes that won't be completed</td> <td bgcolor="#FFFF00" style="width: 33%;">Task started but not complete</td> <td bgcolor="#FF0000" style="width: 33%;">Task not started</td> </tr></table><br /><table style="width: 100%;" class="standard-table" border="1" cellpadding="0" cellspacing="0"> <tr> <th>Task</th> <th>Description</th> <th>Priority</th> <th>Assigned to</th> <th>Status</th> </tr>in the first release.

<tr> <td>Source Documentation</td> <td>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. </td> <td bgcolor="#008080" style="color[[Image: #FFFFFF; font-weight: bold; text-align: center">Low</td> <td>Nobody</td> <td bgcolor="#FFFF00">There is some documentation in the source files but not much. And it's not well documentedDd_partialclassdiagram2.</td> </tr>PNG]]

<tr> <td>Unit tests for the various parts of the delta debugging framework.</td> <td>It would be nice to have unit tests that thoroughly tests each part of the framework to ensure the correctness of the functions. It would be nice to have unit tests for each different part: # Change/Changeset hierarchy of files#Build-related files#RCS-related files#Test framework related files#Delta Debugging Algorithm module</td> <td bgcolor="#008080" style="color: #FFFFFF; font-weight: bold; text-align: center">Low</td> <td>Nobody</td> <td bgcolor="#FFFF00">There are some unit-like tests that tests parts of the frameworkDec. However22, they are either not thorough or outdated.# ChangesetTest.pl tests some of the functionality of the Change/Changeset hierarchy of classes. However it is not thorough and outdated.# maketest.pl tests some of the functionality of the Build classes. However, it is not thorough.# svntest.pl tests some of the functionality of the RCS classes. However, it is not thorough.# DeltaDebuggerTest.pl tests some of the functionality of the delta debugger module. However, it is not thorough.</td> </tr>2006 ===

<tr> <td>Retrieval of Change / Change set</td> <td>The Granularity concept. A single revision may consist of hundreds or thousands I finally had some time to do a second round of lines 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 bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <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>Application However, before I get ahead of Change / Change set</td> <td>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 myself and officially tag and release the source treedelta debugging framework as version 0. Your mission is 1, I would like to figure test it out how to do thaton another test program.</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Can apply a changeset (specified by array of indices passed in) for a RevisionHopefully, Directorythis can be done this weekend. And if all goes well, and File Changesetversion 0. NOT going to complete application 1 will be officially released before the end of Code Block or Line changesetthe year. </td> </tr>

<tr> <td colspan="5"><strong>GNU Make</strong> ([http://www== Dec.gnu.org/software/make/ http://www.gnu.org/software/make/]) </td> </tr>13, 2006 ===

<tr> <td>Wrapper around Created [[Delta_debugging_testcases|Delta Debugging Testcases]] page to discuss the GNU make utility</td> <td>Mozilla uses nature of the GNU make utility test cases created to build their source treetest the algorithm. your mission is to make a wrapper around Included in the GNU make utility page are 2 testcases created so that far, the make command '''HelloWorld''' binary test and the '''Sudoku''' test. Both tests can be programmatically called to build found in the source tree'''deltatest''' svn repository.</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weightThe repository can be checked out using this command: bold; text-align: center">High</td> <tdpre>[[Usersvn checkout svn:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Wrapper created: ''makewrapper/cdot.pl''senecac. Can execute the make command with options specified by the useron. <ca/td> deltatest </trpre>

<tr> <td colspan="5"><strong>Subversion (SVN) Repository</strong> (Exactly 12 days before Christmas, the delta debugging framework has been released under the [http://subversionwww.tigrisopensource.org/ http:licenses//subversion.tigrisgpl-license.org/php GPL Version 2], [http://svnbook.red-beanLicense.com/nightly/en/index.html http://svnbook.red-bean.com/nightly/en/index.html]) </td> </tr>

<tr> <td>Wrapper around the necessary SVN commands</td> <td>For the automated debugging to workUnfortunately, we may need to automatically modify haven't had the working copy by reverting time to a different revision or updating certain directories and files. It may also need to know test the differences between revisions and changesetsdelta debugger much since Dec.</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Wrapper created: ''svn.pl''. Currently has subroutines for ''commit''09, ''update'', ''diff''2006 because of exams, other school work; Planning to spend some time this weekend to test the delta debugger and ''checkout'' commands. May need figure out why it currently seems to wrap other SVN commandsnot be able find the minimal set of failure inducing directories/files (whether its because of unreliable test case or logical error in the program).</td> </tr>

<tr> <td>Query SVN repository for differences between two revisions</td> <td>Your mission is to find out A roadmap of our vision of the relevant commands that can return direction of the differences between two revisions, project will be heading in the meta-data that is kept with each revision, how differences between two revisions are stored future will be created and formatted, and how this data can be parsed into a usable form for our project (wrapper?).</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Doneposted soon.</td> </tr>

<tr> <td colspan="5"><strong>CVS/Mozilla Bonsai</strong> ([http://wwwUploaded testcase for '''HelloWorld''' binary at '''deltatest svn'''.mozilla.org/bonsai.html http://www.mozilla.org/bonsaiThe test simulates the error that may occur when compilation fails due to syntax error.html]The exalted HelloWorld program is located on the HelloWorld directory, [http://cvsbookwhile the test definition is at HelloTestCase1.red-beanpm.com/OSDevWithCVS_3E.pdf CVS Book])<br />In my mind, Bonsai may be too bloated for our needsThe algorithm detects failed test and reverts the affected file to the version where the test passes. </td> </tr>

<tr> <td>Wrapper around Note for the necessary CVS 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 bgcolor="#0000FF" style="color: #FFFFFF; font-weight: bold; text-align: center">Medium</td> <td>[[Userfuture:dwwoodsi|Dean Woodside]]</td> <td bgcolor="#FF0000">Just starting out.</td> </tr>improve user feedback functions!

<tr> <td colspan="5"><strong>Test Case(s)</strong> ([http://www== Dec.mozilla.org/tinderbox.html Tindexbox])</td> </tr>10, 2006 ===

<tr> <td>Creation Where is the CVS/ Extraction Bonsai work heading? Here is a breakdown of Test Casethe past 3-4 weeks:* Initially was going for a straight wrapper around CVS ala the style Richard used for SVN.* Tried to find some functionality within Bonsai that could make it easier.* Talked to Reed Loden, he set up a repository for us to try with. Thanks Reed!* Thought that there may be some additional (sread: unpublished)</td> <td>We need test cases tools that can return whether or not the test passes or failscould be worked with. Tinderbox has a couple Got in contact with some of tests that are executed after the source is built"Project Participants" listed on [http://www.mozilla.org/projects/bonsai/]. Extract those tests from Was told the Tinderbox source code so that we can use them person in this projectparticular wasn't a contributor (just submitted a bug report). We also need a test case that can pass They in turn pointed me to [irc://fail consistently so that we can test the delta debuggerirc.mozilla.<org/td> <td bgcolor="#8B00FF" style="color: mozwebtools #FFFFFF; font-weight: bold; text-align: center">High</td>mozwebtools]. <td>[* Lurked on [Userirc:Ankuswan|Aditya Nanda Kuswanto]]</td> <td bgcolor="/irc.mozilla.org/#mozwebtools #FFFF00">Work in progressmozwebtools] for a few weeks. Talked to 'justdave' about Bonsai. Found Reed Loden chimed up and informed me that Bonsai can output to XML using ?xml=1 on the testsquery (score! Now need to figure thanks again).* Researched some PERL parsing utilities. Trying out how to run them and how they workXML::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>Obtaination of test SVN Repository</td> <td>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=== Dec.</td> <td bgcolor09, 2006 ="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:dwwoodsi|Dean Woodside]]</td> <td bgcolor="#00FF00">Done. The URL to the test SVN repository is: svn://cdot.senecac.on.ca/deltatest</td> </tr>

<tr>What has been done since last week? <td>Obtaination of * Got a test CVS Repository</td> <td>When the CVS version of the framework is completed, program and uploaded it will be useful to have a test CVS repository that we could use to test our framework.</td> <td bgcolor="#0000FF" style="colorsvn: #FFFFFF; font-weight: bold; text-align: center">Medium</td> <td>[[User:dwwoodsi|Dean Woodside]]</td> <td bgcolor="#FFFF00">Work in progress. The CVS repository has been created. The web interface to the repository is: [http://heracdot.senecac.on.ca:43080/viewvcdeltatest. The pristine working version is revision 4.cgi/?root=deltatest here]The latest committed copy is revision 8. Apparently need to just get some forwarding issues resolvedThe regressive code was committed somewhere in between.</td> </tr>* Started testing the delta debugging framework.

<tr> <td colspan="5"><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 the minimal set of failure inducing changes. The intersection of all other parts results of the framework to make them work together. Ideally, should be abstract enough for easy extensibility with little impact.</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#FFFF00">Work in progress. Currently, it can theoretically find the failure inducing revision, and the minimal failure inducing set of directories.</td> </tr></table>testing?

[[Bonsai issue]] -- '''unresolvedFinding the minimal failure-inducing set of directories'''

When The delta debugger correctly applies all of the changes within that directory. And I get confusedthink it correctly builds the source tree and runs the test case. However, the return code of the test case is not as expected. I draw diagramsexpect the test case to report that the test fails, however, it reports that it passes. Thus, the delta debugger returns no directories as failure inducing.

[[Image:Dd_partialclassdiagramI suspect (or at least hope) that the indeterminate results of finding the failure inducing set of directories is because of a possibly unreliable or inconsistent test case. However, I can not be sure until I rule out the test case as the problem.PNG]]

Indeterminate. There are multiple source files in the repository. Does it return the correct failure-inducing source file? I don'''The Clear: Seemingly Straight Forward'''t know. I have the same suspicions for this as for the directory changeset.

The RCS tree is straight forward. It will encapsulate Based on the data and operations related testing, it seems to be able to cycle through every combination of changes in the revision control system. SVN wraps changeset, apply the operations combination of changes, build the SVN revision control systemsource code, CVS will wrap and run the operations of test case. The test case just seems to not report the CVS revision control system, etccorrect test results.

RCS's can remember the changes (deltas) that occurred in previous versions of a file=== Dec. 03, the history of changes that occur between revisions, etc.2006 ===

A Changeset and its subclasses will encapsulate Committed some updated to the SVN repository.* The test framework. There are a couple of files to the idea framework: Test.pl, TestCase.pl, TestSuite.pl, TestResult.pl, TestRunner.pl. It is loosely based off of a set the design of changesthe JUnit framework. A set 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 changes could functionality works or not to be broken down into various categories such as run? For a specific revisionfew 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. Using the testing framework, a list of directoriesthis can be done by subclassing the TestCase.pl class and overriding the run() subroutine.# For the delta debugger to work, a list of filesit needs to know whether the test case passes or fails. Using the test framework, a list I hope to control the possible return codes of blocks the tests to either pass or fail only.* testtest.pl that tests the functionality of code, and finally a line the test framework.* updates to DeltaDebugger.pl to make use of codethe test framework.

A ChangesetFactory is supposed to return a change set based on the type of change set requestedCrunch time. One week left. To get the requested change set, one needs The high priority tasks that still need to know the type be done:# Acquisition of revision control system (SVN, CVS, other, etc.) and/or the data required to connect to it. So there obviously need a link between RCS and ChangesetFactory/Changeset. The question is how? What is the proper/best way to link them together? One way is to pass in an RCS object program we could use to test the ChangesetFactory which would then pass that object to the appropriate Changeset subclassdelta debugging framework. See [[#How_to_Get_Involved|How To Get Involved]] for more info. I don't like that solution but it's # Test, debug the simplestdelta debugging framework.

Committed some updates to the SVN repository.* Applying a change in a changesetUpdated the delta debugging algorithm module. Should I didn't realize this yesterday but the Changeset subclasses be able algorithm to do that? Are they find the information expert? They know about the changes. Should they know how to apply them? How would we go abouts applying a subset minimal set of failure inducing files (and code block and line of code changes in a if those changeset? For example, there may have been changes in 10 different directories, how would we apply types ever gets dones) is the same (with minor modifications) as the algorithm that can find the changes from say 4 minimal set of the 10 failure inducing directories and not . Thus I generalized that algorithm to remove the others?directory changeset specific code so that it will work with all other types of changesets.* Connecting all 3 hierarchies togetherRemoved the debugging/test related code from the source files. Need CVS Repository Setup (thanks 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[[user:reed|Reed Loden!]]): '''hera.senecac.on. ca/deltatest'''* The actual delta debugging algorithm[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 project members

But that's all for ''Milestone:'''* Even though the test framework is incomplete, I think we can go ahead and begin the initial testing of the delta debugger on a real regressive program as I think we are ready. Coincidentally, exactly 2 months after the futurefirst project news posting on Sept. 26, 2006.

== Project News = Nov. 25, 2006 ===