Changes

[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>in the first release. <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[[Image: 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>Dd_partialclassdiagram2.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 bgcolorProject News =="#FFFF00">There are some unit-like tests that tests parts of the framework. However, 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>

<tr> <td>Retrieval of Change / Change set</td> <td>The Granularity concept''This is where your regular updates will go. A single revision may consist of hundreds In these you should discuss the status or thousands of lines of code that were changedyour work, yet only a couple lines your interactions with other members of the change may be responsible for the regressioncommunity (e. Thus, There must be a method to break the change into smaller manageable chunksg. The different types of chunks we may breaking up a changeset are: Revision, DirectoriesSeneca and Mozilla), Filesproblems you have encountered, Code Blocks, and Linesetc. Put detailed technical information into the Project Details page (i.e.</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, Directoryupdate it as you go), and File. NOT going to complete retrieval of Code Block, Line of Code change setsave this section for news about participation in the project. </td> </tr>''

<tr> <td>Application of Change / Change set</td> <td>OK=== Dec. 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.</td> <td bgcolor22, 2006 ="#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 Revision, Directory, and File Changeset. NOT going to complete application of Code Block or Line changeset. </td> </tr>

<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 bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Can unapply a changeset (specified by array of indices passed I haven't posted an update in) for a Revision, Directory, and File Changeset. NOT going to complete unapplication of Code Block or Line changesetwhile. </td> </tr>So what's been done?

<tr> <td colspan="5"><strong>GNU Make</strong> ([http://wwwHowever, before I get ahead of myself and officially tag and release the delta debugging framework as version 0.gnu1, I would like to test it out on another test program.org/software/make/ http://wwwHopefully, this can be done this weekend.gnu And if all goes well, version 0.1 will be officially released before the end of the year.org/software/make/]) </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 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''Dec. Currently has subroutines for ''commit''13, ''update'', ''diff'', and ''checkout'' commands. May need to wrap other SVN commands.</td> </tr>2006 ===

<tr> <td>Query SVN repository for differences between two revisions</td> <td>Your mission is Created [[Delta_debugging_testcases|Delta Debugging Testcases]] page to find out discuss the nature of the relevant commands that can return test cases created to test the differences between two revisions, algorithm. Included in the meta-data that is kept with each revision, how differences between two revisions page are stored and formatted2 testcases created so far, the '''HelloWorld''' binary test and how this data the '''Sudoku''' test. Both tests can be parsed into a usable form for our project (wrapper?)found in the '''deltatest''' svn repository.</td> <td bgcolor="#8B00FF" style="color: #FFFFFF; font-weight: bold; text-alignThe repository can be checked out using this command: center">High</td> <tdpre>[[Usersvn checkout svn:RichardChu|Richard Chu]]</td> <td bgcolor="#00FF00">Done/cdot.senecac.on.<ca/td> deltatest </trpre>

<tr> <td colspan="5"><strong>CVS/Mozilla Bonsai</strong> ([http://www.mozilla.org/bonsai.html http://www.mozilla.org/bonsai.html], [http://cvsbook.red-bean.com/OSDevWithCVS_3E.pdf CVS Book])<br />In my mind, Bonsai may A roadmap of our vision of the direction of the project will be heading in the future will be too bloated for our needscreated and posted soon. </td> </tr>

<tr> <td>Query CVS repository for differences between two revisions</td> <td>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=== Dec. 11, and how this data can be parsed into a usable form for our project (wrapper?).</td> <td bgcolor2006 ="#0000FF" style="color: #FFFFFF; font-weight: bold; text-align: center">Medium</td> <td>[[User:dwwoodsi|Dean Woodside]]</td> <td bgcolor="#FF0000">Just starting out.</td> </tr>

<tr> <td colspan="5"><strong>Test Case(s)</strong> ([http://wwwUploaded testcase for '''HelloWorld''' binary at '''deltatest svn'''.mozillaThe test simulates the error that may occur when compilation fails due to syntax error.org/tinderboxThe exalted HelloWorld program is located on the HelloWorld directory, while the test definition is at HelloTestCase1.pm. The algorithm detects failed test and reverts the affected file to the version where the test passes.html Tindexbox])</td> </tr>

<tr> <td>Creation / Extraction of Test Case(s)</td> <td>We need test cases that can return whether or not Note for the test passes or fails. 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 bgcolor="#8B00FF" style="colorfuture: #FFFFFF; font-weight: bold; text-align: center">High</td> <td>[[User:Ankuswan|Aditya Nanda Kuswanto]]</td> <td bgcolor="#FFFF00">Work in progress. Found the testsimprove user feedback functions! Now need to figure out how to run them and how they work.</td> </tr>

<tr> <td colspan="5"><strong>Obtaination of Test Repositories</strong></td> </tr>== Dec. 10, 2006 ===

<tr>Where is the CVS/Bonsai work heading? Here is a breakdown of the past 3-4 weeks: <td>Obtaination of test * Initially was going for a straight wrapper around CVS ala the style Richard used for SVN Repository</td>. <td>We have an SVN repository * Tried to find some functionality within Bonsai that holds our delta debugging framework source filescould make it easier. We need another SVN * Talked to Reed Loden, he set up a repository for us to try with. Thanks Reed!* Thought that there may be some additional (read: unpublished) tools that we could use to test our frameworkbe worked with.</td> <td bgcolor= Got in contact with some of the "#8B00FFProject Participants" style="colorlisted on [http: #FFFFFF; font-weight//www.mozilla.org/projects/bonsai/]. Was told the person in particular wasn't a contributor (just submitted a bug report). They in turn pointed me to [irc: bold; text-align: center">High</td>/irc.mozilla.org/#mozwebtools #mozwebtools]. <td>* Lurked on [[Userirc:dwwoodsi|Dean Woodside]]</td> <td bgcolor="/irc.mozilla.org/#mozwebtools #00FF00">Donemozwebtools] for a few weeks. The URL Talked to 'justdave' about Bonsai. Reed Loden chimed up and informed me that Bonsai can output to XML using ?xml=1 on the test SVN repository isquery (score! thanks again).* Researched some PERL parsing utilities. Trying out XML: svn://cdotLibXML for DOM-style parsing.senecac* Hopefully wrap something up by Wednesday.on Failing that, might just go with simple CVS wrapper of some sort.ca/deltatest</td> </tr>

== Points of Confusion = Dec. 09, 2006 ===

When I get confusedWorks. The delta debugger correctly reverts to a previous revision, I draw diagramsbuilds the source code, and runs the test case. The test case returns the proper results on whether or not it passes or fails. The delta debugger correctly stops at revision 4 - the last known good version.

[[Image:Dd_partialclassdiagramIndeterminate. There is only 1 directory in the source repository so that directory should be returned as the minimal failure inducing set of directories. Does it return it? yes and no.PNG]]

The RCS tree is straight forward. It will encapsulate I suspect (or at least hope) that the data and operations related to indeterminate results of finding the revision control systemfailure inducing set of directories is because of a possibly unreliable or inconsistent test case. SVN wraps the operations of the SVN revision control systemHowever, CVS will wrap I can not be sure until I rule out the operations of test case as the CVS revision control system, etcproblem.

The Build tree is straight forward. It wraps '''Finding the build tool used to build the source tree.minimal failure-inducing set of files'''

Indeterminate. There are multiple source files in the repository. Does it return the correct failure-inducing source file? I don'''The Blurry: Current Points of Confusion'''t know. I have the same suspicions for this as for the directory changeset.

RCS's can remember Based on the testing, it seems to be able to cycle through every combination of changes (deltas) that occurred in previous versions of a filethe changeset, apply the history combination of changes that occur between revisions, etcbuild the source code, and run the test case. The test case just seems to not report the correct test results.

A ChangesetFactory is supposed to return a change set based on the type of change set requested=== Dec. To get the requested change set03, one needs to know the type 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 to the ChangesetFactory which would then pass that object to the appropriate Changeset subclass. I don't like that solution but it's the simplest.2006 ===

AlsoCommitted some updated to the SVN repository.* The test framework. There are a couple of files to the framework: Test.pl, TestCase.pl, TestSuite.pl, TestResult.pl, TestRunner.pl. It is loosely based off of the design of the JUnit framework. Why such an elaborate design just for the method need of users to define the test case that can determine whether or not a piece of functionality works or not to get be run? For a change set for SVN few reasons that I may be different from CVSadamant 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. So there may Using the testing framework, this can be a Changeset hierarchy for SVN done by subclassing the TestCase.pl class and another one for CVSoverriding 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 don't like hope to control the idea possible return codes of the tests to either pass or fail only.* testtest.pl that at alltests the functionality of the test framework. There must be another way* updates to DeltaDebugger.pl to make use of the test framework.

* Applying a change in a changesetCrunch time. One week left. Should the Changeset subclasses be able to do The high priority tasks that? Are they the information expert? They know about the changes. Should they know how still need to apply them? How would we go abouts applying a subset be done:# Acquisition of changes in a changeset? For example, there may have been changes in 10 different directories, how would program we apply could use to test the changes from say 4 of the 10 directories and not the others?delta debugging framework. See [[#How_to_Get_Involved|How To Get Involved]] for more info.* Connecting all 3 hierarchies together. Need to be able to connect to SVN, need to be able to get and apply changes# Test, need to be able to build debug the source tree. * The actual delta debugging algorithmframework.

== Project News =Nov. 26, 2006 === Committed some updates to the SVN repository.* Updated the delta debugging algorithm module. I didn't realize this yesterday but the algorithm to find the minimal set of failure inducing files (and code block and line of code changes if those changeset types ever gets dones) is the same (with minor modifications) as the algorithm that can find the minimal set of failure inducing directories. Thus I generalized that algorithm to remove the directory changeset specific code so that it will work with all other types of changesets.* Removed the debugging/test related code from the source files.CVS Repository Setup (thanks to [[user:reed|Reed Loden!]]): '''hera.senecac.on.ca/deltatest'''*[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

''This is where your regular updates will go=== Nov. In these you should discuss the status or your work25, your interactions with other members of the community (e.g., Seneca and Mozilla), problems you have encountered, etc. Put detailed technical information into the Project Details page (i.e., update it as you go), and save this section for news about participation in the project.''2006 ===