'''[WORK IN PROGRESS: This post will be updated once I gather all of my thoughts. Stay tuned...]'''
Based on the papers on delta debugging that I've sifted through (with [http://www.infosun.fmi.uni-passau.de/st/papers/computer2000/computer.pdf ''From Automated Testing to Automated Debugging''] by Andreas Zeller being the most understandable to non-math wizards, and [http://www.infosun.fmi.uni-passau.de/st/papers/tr-99-01/esec99.pdf ''Yesterday, my program worked. Today, it does not. Why?''] also by Andreas Zeller probably being the most relevant to our project), here is an outline of my understanding of delta debugging and , a summary of the concepts that must be taken into account while working on the delta debugging framework project, and an outline of the conceptual stages of developing the delta debugging framework.
[''Note: The rest of this post contains mathematical concepts that I may not fully understand but am trying to put into terms understandable to non-math wizards. A dangerous combination.'']
With regards to delta debugging algorithm, we must take into account three possible scenarios that may complicate it:
* '''Interference'''. The cause of the regression may be from a combination of changes. That is, each individual change does not cause the program to regress, but applying the changes together causes the regression. Thus, there must be a method to identify the set of changes that cause the regression.
* '''Inconsistency'''. That is, changes in source code may be dependent on other changes in the source code and without them the program cannot be compiled and tested successfully. Thus, there must be a method to identify and handle dependencies (such as a dependency graph).
* '''Granularity'''. A single change may consist of hundreds of lines of code, 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.
* '''Configuration'''. A subset of all changes made to source code since the last known good version and the version with the regression.
* '''Test'''. A test case or function that can determine whether a configuration contains the failure-inducing change (Fails), doesn't contain the failure-inducing change (Passes), or produces indeterminate results (possibly because of interference or inconsistency).
* '''Subset'''. Given two sets (''A'' and ''B''), ''A'' is a subset of ''B'' if and only if all of the elements of set ''A'' are in set ''B''.
* '''Superset'''. Given two sets (''A'' and ''B''), ''B'' is a superset of ''A'' if and only if ''B'' contains all of the elements of ''A''.
There are With regards to the delta debugging algorithm, we must take into account these possible concepts that may complicate it: * '''Interference'''. Each individual change may not cause the program to regress, but applying a combination of changes together causes the regression. Thus, there must be a method to identify the set of changes that cause the regression. <br />In the case of interference, we must recursively test both halves with all changes in one half of the configuration remaining applied. * '''Inconsistency'''. Changes in the source code may be dependent on other changes in the source code and without them the program cannot be compiled and tested successfully. Thus, there must be a method to identify and handle dependencies (such as a dependency graph). <br />[Wild, far left field thought: How can we ensure that when applying a configuration, it is consistent? Well, in the [http://en.wikipedia.org/wiki/Compilers#Compiler_design compiler process], there is a lexical analysis step which breaks the source code into tokens, then there is a dependence analysis step which produces constraints/dependencies between the tokens. Theoretically, if we can harness parts of the compilation process, we could have a method of knowing the dependencies between the changes in the source code.] * '''Granularity'''. A single logical change may consist of hundreds of lines of code, yet only a couple lines of properties the change may be responsible for the regression. Thus, There must be a method to break the change into smaller manageable chunks. *'''Monotony'''. If a change causes a failure, any configuration that includes this change fails as well (makes sense to me). If a configuration does not cause a failure, then all subsets of the configuration do not cause a failure, thus they can decrease be eliminated from the change set (makes some sense to me. However, if my understanding is correct, while a subset of the configuration does not cause the number failure by itself, the concept of tests required interference suggests that the subset combined with another configuration may cause the regression). *'''Unambiguity'''. A failure is caused by only one configuration (No interference). Thus, for efficiency, we do not have to find search the minimal other configuration for more failure-inducing changes. Whether or not a configuration is ambiguous or unambiguous, a failure-inducing change will be produced. However, for completeness with regard to finding all failure-inducing set of changes, it is preferred to search both configurations. While implementing these properties Now that we are aware of the different concepts that we must take into account with regards to delta debugging, the next section will outline some facts and assumptions that are being made, attempt to define the vision and process of the algorithm delta debugging framework. '''Facts and Assumptions:''' # The source code for the Mozilla project is HUGE. With many different source files (C++, JS, XUL) in many different directories.# Failure-induces change(s) will unlikely be localized to a single directory and file. Failure-inducing change(s) may be more difficult than testing all possible combinationsspread across many different directories and source files.# The source files could be of same type, mixed type, same directory, it different directory. It shouldn't matter. The framework should result in be source type and location agnostic.# The failure-inducing changes may not be localized to a single developer. The failure-inducing change may have been caused by another developer's change of a source file they were working on. That is, a single developer's source scope may not be encapsulated but interconnected and interdependent on other developers source code.# The developer's current version of the source code contains the regression.# The developer has a test case that can be used indicate whether the test passes/fails/is indeterminate.# The developer knows the last known good version number or the date of last known good version. The latter will most likely be simpler and more efficient algorithm in certain casesuser friendly.# Bonsai is a tool that can produce a list of differences between versions of a source file. Something I would like (Bonsai's functionality has not been examined closely yet but will have to aim for.as it may be a key component to the framework)
*'''Monotony'''. If a change causes a failure, any configuration that includes this change fails as well (makes sense to me). If a configuration does not cause a failure, then all subsets Possible Vision of the configuration do not cause a failure, thus they can be eliminated from the change set (the proof by contradiction shown in [http://www.infosun.fmi.uni-passau.de/st/papers/tr-99-01/esec99.pdf Delta Debugging Framework''Yesterday, my program worked. Today, it does not. Why?''] makes some sense to me. However, if my understanding is correct, while a subset of the configuration does not cause the failure by itself, the concept of interference suggests that the subset combined with another configuration may cause the regression).:
*'''Unambiguity'''. A configuration is unambiguous if, given two subsets of a configuration, a test on the first subset reports (subject to cause the regression, a test change based on the second subset reports to cause the regression and the intersection of the first and second sets does not pass (reports to cause the regression or produces indeterminate resultsstakeholder consultation/feedback).
*# Since the last time a developer executed a test case that passed, the developer modified some source files. The source files may be of the same type or mixed type, same directory or different directory. It shouldn't matter. The framework should be source type and location agnostic. Upon executing the test case again, the result is now a failure. The developer panics. It's only days before the deadline to submit bug patches before the source tree is supposed to be closed for release and the bug is a blocker. The developer doesn'Consistency''t want to be shamed for delaying the release, and the source code is too complex to find the bug in time, so what should they do? Use the delta debugging framework! that's what. How? you may ask. Well keep reading to find out. <small>* scenario may vary. All subsets </small># The delta debugging framework may require the developer to input two pieces of a configuration produces a determinate result (information. One, the test case/function that used to pass but now fails. It will be used to determine whether the source files with progressive changes passes/fails the test. Two, the date of the last known good version that passed the test case. Because of assumption 4 made above, the source directory and files or fail)name of the developer may not be required.#
In the ideal situation, a configuration will be monotone, unambiguous, and consistent. In which case, a binary algorithm may suffice. The set of changes may be recursively split into two subsets and tested. The result may be that the first or second subset has the failure inducing change or both tests pass as a result of interference. In the case of interference, we must recursively test both halves with all changes in one half of the configuration remaining applied.
'''[WORK IN PROGRESS: This post will be updated once I gather all of my thoughts. Stay tuned...]'''