de.uds.cs.st.dd.core
Class DD

java.lang.Object
  |
  +--de.uds.cs.st.dd.core.DD

public class DD

extends Object

Main Delta Debugging class. Provides functionality to apply the Delta Debugging algorithm to any configuration.

Author:

Philipp Bouillon

Field Summary

static int	ADD Resolving direction: Adds more deltas.
private boolean	assumeAxiomsHold If set to true, c[initialfail] == fail and c[initialpass] == pass.
private boolean	cacheOutcomes If set to true, test results are stored in a cache.
private TConfiguration	cc Used to store a temporary configuration.
static int	FAIL Delta Debugging test outcome: the test has failed.
private TConfiguration	failingSubset Used to store the failing subset of the ddDiff algorithm.
private static int	INITIAL_PARTITION_SIZE Initial partition size of the Delta Debugging algorithm.
private int	lastReportedLength Helper variable to indicate the last state of the algorithm that has been displayed on screen.
private boolean	maximize Maximize the input.
private boolean	minimize Minimize the input.
private boolean	monotony If set to true, Delta Debugging assumes that any subset of a passing test also passes and any superset of a failing test also fails.
static int	NONE Delta Debugging test outcome: no outcome exists (the test has not been performed, yet).
private Object[]	originalConfig An array containing the original configuration data.
private OutcomeCache	outcomeCache The outcome cache stores all previously calculated test outcomes.
static int	PASS Delta Debugging test outcome: the test has successfully passed.
private TConfiguration	passingSubset Used to store the passing subset of the ddDiff algorithm.
static int	REMOVE Resolving direction: Removes some deltas.
private Resolver	resolver Resolving functionality.
private int	resolveType Currently not used.
private boolean	resolving Is set to true as soon as the algorithm is resolving a configuration.
private Splitter	splitter Splitting functionality.
private TConfiguration	temporary Used to store a temporary configuration.
private Tester	tester Testing functionality.
static int	UNRESOLVED Delta Debugging test outcome: the test had an unresolved outcome.
private Vector	viewers Stores all registered ISimpleViewers.

Constructor Summary

DD(Tester tester)
Creates a new DD object and initializes the variables to defaults.

DD(Tester tester, ISimpleViewer viewer)
Creates a new DD object and initializes the variables to defaults.

Method Summary

void	addViewer(ISimpleViewer viewer) Adds a viewer to the registered viewers of this class.
private void	createOriginalConfig(TConfiguration c, TConfiguration c2) Creates a copy of the original configurations and stores the elements in an array.
private TConfiguration	dd(TConfiguration c, int n) The main Delta Debugging algorithm: This function applies Delta Debugging to the specified configuration.
TConfiguration	ddDiff(TConfiguration c) Calculates a 1-minimal failure-inducing difference by applying the Delta Debugging algorithm.
TConfiguration	ddDiff(TConfiguration pass, TConfiguration fail) Calculates a 1-minimal failure-inducing difference by applying the * Delta Debugging algorithm.
private TConfiguration	ddGen(TConfiguration c, boolean minimize, boolean maximize) Calls the Delta Debugging algorithm with initialized minimizing and maximizing parameters.
TConfiguration	ddMax(TConfiguration c) Calls the Delta Debugging algorithm.
TConfiguration	ddMin(TConfiguration c) Calls the Delta Debugging algorithm.
TConfiguration	ddMix(TConfiguration c) Calls the Delta Debugging algorithm.
private TConfiguration	ddResolve(TConfiguration csub, TConfiguration c, int direction) Resolves a configuration that produced an unresolved test outcome.
private TConfiguration	ddSplit(TConfiguration c, int n) Splits the given configuration into n subsets by calling the split method of the attached Splitter object.
private int	ddTest(TConfiguration c) Testing functionality of the Delta Debugging algorithm.
private TConfiguration	diff(TConfiguration c1, TConfiguration c2, int n) The Delta Debbuging algorithm to calculate a 1-minimal failure-inducing difference.
ISimpleViewer[]	getAttachedViewers() Returns all currently attached viewers as an array or null if no viewers * are attached.
TConfiguration	getFailingSubset() Returns the failing subset of a 1-minimal failure inducing difference.
TConfiguration	getPassingSubset() Returns the passing subset of a 1-minimal failure-inducing difference.
private TConfiguration	getRealConfig(TConfiguration indexc) Retrieves the original elements of the test case according to the specified index configuration.
Resolver	getResolver() Returns the current resolver object of this DD object.
Splitter	getSplitter() Returns the current splitter object of this DD object.
Tester	getTester() Returns the current tester object of this DD object.
private void	initialize() Initializes the class fields with default values.
boolean	isAssumingAxiomsHold() Returns true if the algorithm assumes that axioms hold, false otherwise.
boolean	isCachingOutcomes() Returns if test outcomes are cached.
boolean	isMonotone() Returns if the algorithm assumes monotony.
boolean	isResolving() Checks, if the algorithm is currently resolving.
private void	reportProgress(TConfiguration c, String title) Reports a progress information to all registered viewers.
private void	sendText(String message) Convenience method to send the specified message to all attached viewers.
void	setAssumeAxiomsHold(boolean assumeAxiomsHold) Sets assumeAxiomsHold.
void	setCacheOutcomes(boolean cacheOutcomes) Sets the cacheOutcomes variables.
void	setMonotony(boolean monotony) Sets the monotony.
void	setResolver(Resolver resolver) Sets the current resolver of this DD object.
void	setSplitter(Splitter splitter) Sets the current splitter of this DD object.
void	setTester(Tester tester) Sets the current tester of this DD object.
private int	testAndResolve(TConfiguration csub, TConfiguration r, TConfiguration c, int direction) Tests a configuration as long as its test outcome is unresolved.
private int	testMix(TConfiguration csub, TConfiguration c, int direction) Performs a testing of subsets.

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Field Detail

PASS

public static final int PASS

Delta Debugging test outcome: the test has successfully passed.

See Also:

Constant Field Values

FAIL

public static final int FAIL

Delta Debugging test outcome: the test has failed.

See Also:

Constant Field Values

UNRESOLVED

public static final int UNRESOLVED

Delta Debugging test outcome: the test had an unresolved outcome.

See Also:

Constant Field Values

NONE

public static final int NONE

Delta Debugging test outcome: no outcome exists (the test has not been performed, yet).

See Also:

Constant Field Values

ADD

public static final int ADD

Resolving direction: Adds more deltas.

See Also:

Constant Field Values

REMOVE

public static final int REMOVE

Resolving direction: Removes some deltas.

See Also:

Constant Field Values

INITIAL_PARTITION_SIZE

private static final int INITIAL_PARTITION_SIZE

Initial partition size of the Delta Debugging algorithm. First, the deltas are split into two.

See Also:

Constant Field Values

minimize

private boolean minimize

Minimize the input.

maximize

private boolean maximize

Maximize the input.

monotony

private boolean monotony

If set to true, Delta Debugging assumes that any subset of a passing test also passes and any superset of a failing test also fails.

cacheOutcomes

private boolean cacheOutcomes

If set to true, test results are stored in a cache. Therefore, duplicate calculation of tests will not occur.

assumeAxiomsHold

private boolean assumeAxiomsHold

If set to true, c[initialfail] == fail and c[initialpass] == pass.

resolving

private boolean resolving

Is set to true as soon as the algorithm is resolving a configuration. Is set to false again, as soon as the resolving terminates.

lastReportedLength

private int lastReportedLength

Helper variable to indicate the last state of the algorithm that has been displayed on screen.

resolveType

private int resolveType

Currently not used.

originalConfig

private Object[] originalConfig

An array containing the original configuration data.

failingSubset

private TConfiguration failingSubset

Used to store the failing subset of the ddDiff algorithm.

passingSubset

private TConfiguration passingSubset

Used to store the passing subset of the ddDiff algorithm.

temporary

private TConfiguration temporary

Used to store a temporary configuration.

cc

private TConfiguration cc

Used to store a temporary configuration.

resolver

private Resolver resolver

Resolving functionality.

splitter

private Splitter splitter

Splitting functionality.

tester

private Tester tester

Testing functionality.

outcomeCache

private OutcomeCache outcomeCache

The outcome cache stores all previously calculated test outcomes.

viewers

private Vector viewers

Stores all registered ISimpleViewers. All output messages are sent to * all registered viewers.

Constructor Detail

DD

public DD(Tester tester)

Creates a new DD object and initializes the variables to defaults. No viewer is attached to this object, so no output of this class * can be observed (unless a viewer is attached later on). * * @param tester test class that will be used to execute tests.

DD

public DD(Tester tester,
          ISimpleViewer viewer)

Creates a new DD object and initializes the variables to defaults. The specified viewer will be attached to this object. More viewers may * be attached later on.

Parameters:

tester - test class that will be used to execute tests. * @param viewer a viewer that will be used to display information.

Method Detail

initialize

private void initialize()

Initializes the class fields with default values.

createOriginalConfig

private void createOriginalConfig(TConfiguration c,
                                  TConfiguration c2)

Creates a copy of the original configurations and stores the elements in an array.

Parameters:

c - the initial configuration of the passing test. * @param c2 the initial configuration of the failing test.

getRealConfig

private TConfiguration getRealConfig(TConfiguration indexc)

Retrieves the original elements of the test case according to the specified index configuration. So, each element contained in indexc specifies an index to the real configuration.

Parameters:

indexc - indices into the real configuration.

Returns:

TConfiguration a configuration filled with the original elements.

ddTest

private int ddTest(TConfiguration c)

Testing functionality of the Delta Debugging algorithm. If outcomes are cached, it will be checked if the current configuration has already been tested. If so, the saved result is returned. If monotony is also set to true, it is checked, if anything can be derived from previously calculated tests (i.e. if a subset or a superset of the current configuration has been calculated already). Furthermore, this method calls the test method of the attached Tester object. Its result is returned.

Parameters:

c - configuration to test.

Returns:

int outcome of the test.

ddSplit

private TConfiguration ddSplit(TConfiguration c,
                               int n)

Splits the given configuration into n subsets by calling the split method of the attached Splitter object.

Parameters:

c - configuration to split.

n - number of subsets to create.

Returns:

TConfiguration that holds the generated subsets.

ddResolve

private TConfiguration ddResolve(TConfiguration csub,
                                 TConfiguration c,
                                 int direction)

Resolves a configuration that produced an unresolved test outcome. Calls the resolve method of the attached Resolver object.

Parameters:

csub - subset of the configuration to start the resolving process.

c - configuration to be resolved.

direction - add or remove deltas to resolve the problem.

Returns:

TConfiguration resolved configuration.

testAndResolve

private int testAndResolve(TConfiguration csub,
                           TConfiguration r,
                           TConfiguration c,
                           int direction)

Tests a configuration as long as its test outcome is unresolved. Calls ddResolve to resolve the configurations. Stops, if either resolving returns null or the test outcome is no longer unresolved.

Parameters:

csub - initial test subset of the configuration.

r - subset that is added to the initial subset.

c - r and c form the "upper baseline".

direction - add or remove deltas.

Returns:

int test outcome.

isResolving

public boolean isResolving()

Checks, if the algorithm is currently resolving.

Returns:

boolean true if the algorithm is currently resolving, false otherwise.

sendText

private void sendText(String message)

Convenience method to send the specified message to all attached viewers. * The message is sent to all viewers by calling their sendTextMessage * method. * * @param message the message to send.

reportProgress

private void reportProgress(TConfiguration c,
                            String title)

Reports a progress information to all registered viewers.

Parameters:

c - current configuration.

title - title of the information.

testMix

private int testMix(TConfiguration csub,
                    TConfiguration c,
                    int direction)

Performs a testing of subsets.

Parameters:

csub - subset of the current configuration. Will be tested.

c - complete set of subsets.

direction - add or remove deltas from the subset.

Returns:

int test outcome.

ddGen

private TConfiguration ddGen(TConfiguration c,
                             boolean minimize,
                             boolean maximize)

Calls the Delta Debugging algorithm with initialized minimizing and maximizing parameters.

Parameters:

c - configuration to test.

minimize - true, if deltas are to be removed from c, false otherwise.

maximize - true, if deltas are to be added to c, false otherwise.

Returns:

TConfiguration a 1-minimal failing subset of c.

dd

private TConfiguration dd(TConfiguration c,
                          int n)

The main Delta Debugging algorithm: This function applies Delta Debugging to the specified configuration. In each run, a subset of c (or initially, c itself) is tested against a specified test function. Depending on the outcome of this function, new subsets of c are created. In the best case, each subset is split into 2 new subsets. However, if there are unresolved or only passing tests, the granularity is increased, thereby producing 4 or more subsets. The algorithm terminates, when no more subsets can be found.

Parameters:

c - configuration to test.

n - granularity of the splitting

Returns:

TConfiguration a 1-minimal failing subset of c.

ddMin

public TConfiguration ddMin(TConfiguration c)

Calls the Delta Debugging algorithm. The passed configuration will only be minimized. So, if you pass a failing configuration, it will be minimized until no more elements of it can be removed without making the failure go away.

Parameters:

c - configuration to analyze.

Returns:

TConfiguration a 1-minimal failing subset of c.

ddMax

public TConfiguration ddMax(TConfiguration c)

Calls the Delta Debugging algorithm. The passed configuration will only be maximized. So, if you pass a failing configuration, it will be maximized until it contains all the elements that do not pass.

Parameters:

c - configuration to analyze.

Returns:

TConfiguration a configuration containing all the failing elements of the original configuration.

ddMix

public TConfiguration ddMix(TConfiguration c)

Calls the Delta Debugging algorithm. The passed configuration will be minimized and maximized. So, a failing configuration will be minimized until no further element of the configuration can be removed. At the same time, any passing subset which has been found during the algorithm will be maximized. The result is a 1-minimal failure-inducing difference.

Parameters:

c - configuration to analyze.

Returns:

TConfiguration a 1-minimal failure-inducing difference.

ddDiff

public TConfiguration ddDiff(TConfiguration c)

Calculates a 1-minimal failure-inducing difference by applying the Delta Debugging algorithm. The original configuration is minimized and maximized (as in ddMix) and additionaly, the failing and passing configurations are stored.

Parameters:

c - failing configuration to analyze.

Returns:

TConfiguration a 1-minimal failure-inducing difference.

ddDiff

public TConfiguration ddDiff(TConfiguration pass,
                             TConfiguration fail)

Calculates a 1-minimal failure-inducing difference by applying the * Delta Debugging algorithm. The original configuration is minimized * and maximized (as in ddMix) and additionaly, the failing and * passing configurations are stored. * * @param pass passing configuration to analyze. * @param fail failing configuration to analyze. * @return TConfiguration a 1-minimal failure-inducing difference.

diff

private TConfiguration diff(TConfiguration c1,
                            TConfiguration c2,
                            int n)

The Delta Debbuging algorithm to calculate a 1-minimal failure-inducing difference.

Parameters:

c1 - initial passing configuration.

c2 - initial failing configuration.

n - initial split size.

Returns:

TConfiguration a 1-minimal failure-inducing difference.

isAssumingAxiomsHold

public boolean isAssumingAxiomsHold()

Returns true if the algorithm assumes that axioms hold, false otherwise.

Returns:

boolean current assuming status of axioms.

isCachingOutcomes

public boolean isCachingOutcomes()

Returns if test outcomes are cached.

Returns:

boolean true, if outcomes of tests are cached, false otherwise.

isMonotone

public boolean isMonotone()

Returns if the algorithm assumes monotony.

Returns:

boolean true, if monotony holds, false otherwise.

getAttachedViewers

public ISimpleViewer[] getAttachedViewers()

Returns all currently attached viewers as an array or null if no viewers * are attached.

Returns:

ISimpleViewer [] all currently attached viewers.

setAssumeAxiomsHold

public void setAssumeAxiomsHold(boolean assumeAxiomsHold)

Sets assumeAxiomsHold. If set to true, the initial set a is assumed to produce a passing test outcome, while the initial set b is assumed to produce a failing test outcome. If set to false, each set is tested (including the initial sets).

Parameters:

assumeAxiomsHold - the value to set.

setCacheOutcomes

public void setCacheOutcomes(boolean cacheOutcomes)

Sets the cacheOutcomes variables. If set to true, all test configurations and their test outcome are stored in an OutcomeCache. Thereby preventing equal configurations from being tested several times. If set to false, no caching does occur.

Parameters:

cacheOutcomes - the value to set.

setMonotony

public void setMonotony(boolean monotony)

Sets the monotony. If set to true, Delta Debugging assumes that any subset of a passing test also passes and any superset of a failing test also fails.

Parameters:

monotony - the value to set.

addViewer

public void addViewer(ISimpleViewer viewer)

Adds a viewer to the registered viewers of this class.

Parameters:

viewer - the viewer to add.

getPassingSubset

public TConfiguration getPassingSubset()

Returns the passing subset of a 1-minimal failure-inducing difference. Note: The return value is null, unless the algorithm ddDiff has been called before.

Returns:

TConfiguration passing subset of the previously analyzed configuration.

getFailingSubset

public TConfiguration getFailingSubset()

Returns the failing subset of a 1-minimal failure inducing difference. Note: The return value is null, unless the algorithm ddDiff has been called before.

Returns:

TConfiguration failing subset of the previously analyzed configuration.

getTester

public Tester getTester()

Returns the current tester object of this DD object.

Returns:

Tester current tester.

setTester

public void setTester(Tester tester)

Sets the current tester of this DD object.

Parameters:

tester - current tester.

getSplitter

public Splitter getSplitter()

Returns the current splitter object of this DD object.

Returns:

Splitter current splitter.

setSplitter

public void setSplitter(Splitter splitter)

Sets the current splitter of this DD object.

Parameters:

splitter - current splitter.

getResolver

public Resolver getResolver()

Returns the current resolver object of this DD object.

Returns:

Resolver current resolver.

setResolver

public void setResolver(Resolver resolver)

Sets the current resolver of this DD object.

Parameters:

resolver - current resolver.